查看原文
其他

【连载】比特币史话 | 拜占庭将军(1)

刘教链 刘教链 2023-01-30

(圣索菲亚大教堂,伊斯坦布尔。图片来源于网络)
本篇看点:拜占庭将军们的故事是怎样的由来?中本聪一路闯关,开始从密码学跨界进入分布式计算领域,他将面临的又是怎样一副局面呢?

前情回顾:
【连载】比特币史话 | 时间之矢(3)
【连载】比特币史话 | 时间之矢(4)
【连载】比特币史话 | 时间之矢(5)

正文:

在今天的土耳其境内,有一个连接黑海和地中海、横跨亚洲和欧洲因而位居战略要冲的著名城市,伊斯坦布尔(Istanbul)。在罗马帝国时期,她的名字叫做君士坦丁堡(Constantinople),并曾经一度作为东罗马帝国的首都。而在公元前658年始建之际,她的名字叫做拜占庭(Byzantine)。[公众号:刘教链]

在一次围城之战中,拜占庭帝国的将军们兵分几路,分别从不同方向向敌军进攻。将军们之间只能依靠信使传递消息,而信使则有被敌军截获、丢失消息,甚至策反、传递假消息的可能性。更糟糕的是,将军之中据信也有被敌军策反者,不仅可能拒绝呼应其他将军的行动,甚至有可能故意发出假情报,欺骗、干扰其他将军,阻止他们就作战行动达成一致。试问,在这种情况下,这些拜占庭的将军们有什么方法可以就作战计划达成一致呢?[1][公众号:刘教链]

这就是计算机分布式系统领域中著名的“拜占庭将军问题”(Byzantine Generals Problem)。这是一个故事,也是一个比喻。讲这个故事的人正是美国计算机科学家莱斯利·兰伯特(Leslie Lamport)。事实上,莱斯利·兰伯特是先论证的解决方案,然后才提出了这个问题。[公众号:刘教链]

最早意识到拜占庭共识问题的人,其实是美国计算机科学家罗伯特·肖斯塔克(Robert Shostak)。他是在1978年为美国航空航天局(NASA)资助的SIFT项目工作是发现这个问题的,并将其称为交互式一致性问题。后来,1980年4月,他和莱斯利·兰伯特一起发表了对于这个问题的研究论文,指出有算法可以在不超过1/3坏节点的情况下达成共识。但是,解法有了,问题却由于过于复杂而难以被理解。于是莱斯利·兰伯特决定讲一个好故事,以便帮助大家理解这个问题。他最初选择的故事背景发生在另一个城市,后来经别人建议才改到了拜占庭,这才有了1982年的论文《拜占庭将军问题》(The Byzantine Generals Problem)[2]。莱斯利·兰伯特在论文中所给出的解决方案,就是所谓“拜占庭容错”(BFT, Byzantine Fault Tolerant)算法。后人在其基础上,又陆续提出了很多的变种算法,比如1999年由米格尔·卡斯特罗(Miguel Castro)和巴巴拉·里斯科夫(Barbara Liskov)提出的“实用拜占庭容错算法”(PBFT)等。[公众号:刘教链]

莱斯利·兰伯特的故事深入人心。在他讲的故事里,将军就是网络节点,信使就是互联网通信,作战行动就是信息,达成共识就是每个节点都建立相同的全局观(又称全局视图,global view);忠诚的将军就是正常工作的节点,失联的将军就是不工作的、联系不上的节点,被策反的叛徒将军就是主动作恶、作弊的节点。只能容许忠诚将军存在的网络是难以规模化的。随着互联网的发展,节点数量的增加,必然出现节点故障、将军失联的情况。我们都听说过谷歌早年用普通PC机搭建集群,通过软件实现高可用性的故事。谷歌所实现的,就是所谓“崩溃容错”(CFT, Crash Fault Tolerant)算法。如果更进一步,允许网络中出现非受控的作恶节点、叛徒将军,那么网络环境就会进一步恶化为所谓“拜占庭网络”,此时就需要所谓“拜占庭容错”(BFT)算法才能保证系统的稳定、安全运行。[公众号:刘教链]

在2008年中本聪为了发明比特币而提出工作量证明链之前,没有人知道怎么在全球互联网规模(1万至10万数据节点)上实现有效的拜占庭容错。整个互联网行业选择了另外一条技术路线,抛弃互联网创立之初的去中心化理念和构想,走向中心化控制,通过中心化控制权去识别、阻止和驱逐叛徒将军,让所有数据节点工作在一个中心化管控的、安全的环境中,从而把问题降级为更为简单的“崩溃容错”问题。但是即便如此,1985年的一篇著名论文仍然给了计算机科学家和工程师们一记重击...[公众号:刘教链]

【未完待续】(公众号:刘教链)

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存