拜占庭将军的难题

古老的“拜占庭将军问题”

让人生，让人死，让人痴迷，让人疯狂。

这就是传说中繁华与没落，绝望与救赎并存的东罗马帝国首都，拜占庭。

在2013年获得计算机科学领域最高奖项图灵奖的31年前，1972年，莱斯利·兰伯特（Leslie Lamport）搬到湾区。此时，他仍然是一个寂寂无闻的美国小伙。他充当Compass（马萨诸塞州计算机合伙人公司）西海岸计划前哨基地的先锋，不幸的是，这个分支机构最终未能落实。在长达5年的时间里，他曾是Compass总部派驻加州的唯一员工。最后，他却收到撤回东海岸的指令。于是，他决定加入斯坦福国际研究院（SRI）。在那段岁月里，SRI有一个项目，要在美国航空航天局建立容错型航电计算机系统。考虑到系统的工作性质，故障是不允许发生的。这段经历孕育了两篇旨在解决一种特殊故障的论文，由兰伯特和SRI同事马歇尔·皮斯（Marshall Pies）及罗伯特·肖斯塔克（Robert Shostak）合作完成。用计算学术语说，普通故障可能会导致信息丢失或进程停止，但系统不会遭到破坏，因为这种普通故障属于一出错就会停下来的故障类型，剩下的备份的、正常的部分照样可以运转，发挥作用。就像战场上的士兵，他们一旦受伤或阵亡就停止战斗，但并不妨碍他人继续作战。

然而一旦发生“拜占庭故障”，就会非常麻烦，因为它们不会停下来，还会继续运转，并且给出错误讯息。就像战争中有人成了叛徒，会继续假传军情，惑乱人心。当时为了解决这个问题，常常使用的技术被称为“三重模块冗余”：也就是说使用三台计算机进行万一出错的备份工作，三台独立的计算机按照少数服从多数的原则“投票”。这样，即使其中一台机器提供了错误结果，其他两台仍然会提供正确答案。但是为了证明这种方法的有效性，必须拿出证据。而在编写证据的过程中，研究人员遇到了一个问题：“错误”计算机可能给其他两台计算机发送互不相同的错误值，而后者却不会知道。这就需要使用第四台计算机来应对这个故障。

兰伯特说：“如果你使用数字签名，就可以用三台机器达成目的，因为如果‘坏了’的计算机向一台计算机发送了带签名的错误值，并向另一台发送了不同的带签名错误值，另外两台计算机就能够交换消息，以检查究竟发生了什么情况，因为两个不同的值都是签名发送的。”兰伯特还听吉姆·格雷谈论过另一个性质大体相同的问题，人们称之为“中国将军问题”。这引起了兰伯特有关司令将军和叛徒将军的联想，于是他将这个问题及其解决方案命名为“拜占庭将军问题”。

“我记得，与我的朋友怀特·迪菲（White Duffy）坐在伯克利的一间咖啡馆里，当时他描述了一个构建数字签名的问题。”兰伯特回忆说，“他说：‘如果能办到的话，会非常有用。’我说：‘这听起来并不很困难。’于是在一张餐巾纸上，我为他勾画出了第一种数字签名算法。虽然当时并不很实用，但目前已经变得切实可行。”只可惜那张餐巾纸已经消逝在时间的流沙中。在后来1982年正式出版的拜占庭将军论文的序言中，他这样写道：

“我一直觉得正是因为通过用一组围坐在圆桌旁的哲学家来表述，Dijkstra（迪克斯塔）的‘哲学家就餐问题’才变得如此让人关注（比如在理论界，它可能比‘读者/作者’问题都引人注目，尽管读者/作者问题可能更具实际意义）。我认为Reaching Agreement in the Presence of Faults（达成共识的缺陷）中所描述的问题十分重要，值得计算机科学家们去关注。‘哲学家就餐问题’使我认识到，把问题以讲故事的形式表达出来更能引起人们的关注。在分布式计算领域有一个被称作‘中国将军问题’的问题。在这个问题中，两个将军必须在进攻还是撤退上达成一致，但是相互只能通过信使传送消息，而且这个信使可能永远都无法到达。我借用了这里的将军的叫法，并把它扩展成一组将军，同时这些将军中有些是叛徒，他们需要达成一致的决定。同时我想给这些将军赋予一个国家，同时不能得罪任何读者。那时候，阿尔巴尼亚还是一个完全封闭的国家，我觉得应该不会有阿尔巴尼亚人看到这篇文章，所以最初的时候这篇论文题目实际是The Albanian Generals Problem（阿尔巴尼亚将军问题）。但是Jack Goldberg（杰克·古登博格）后来提醒我，在这个世界上除了阿尔巴尼亚之外还有很多阿尔巴尼亚移民，所以建议我换个名字。于是就想到了这一更合适的叫法——Byzantine generals（拜占庭将军）。”

写这篇论文的最主要目的是将拜占庭将军这个叫法用在这个问题上。基本的算法文章在1980年的论文中就已经出现了。

起源：拜占庭位于现在土耳其的伊斯坦布尔，是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔，为了防御敌人每个军队都分隔很远，将军与将军之间只能靠信差传消息。在战争时期，拜占庭军队内所有将军和副官必须达成一致共识，决定是否有赢的机会才去攻打敌人的阵营。但是，军队可能有叛徒和敌军间谍，左右将军们的决定，扰乱军队整体的秩序。在达成共识的过程中，有些信息，往往并不代表大多数人的意见。这时候，在已知有成员谋反的情况下，其余忠诚的将军在不受叛徒的影响下如何达成一致的协议，就是“拜占庭将军问题”。

两军问题：军队与军队之间分隔很远，传递信息的信差可能在途中阵亡，或因军队距离不能在得到消息后即时回复，发送方也无法确认消息确实丢失的情形，导致不可能达到一致性。在分布式计算上，试图在异步系统和不可靠的通道上达到一致性是不可能的。因此对一致性的研究一般假设信道是可靠的，或非异步系统上运行。

“拜占庭将军问题”在通信领域的意义

“拜占庭将军问题”并非如传说中那样，源于公元5世纪的东罗马战场，而是产生于1982年一位美国计算机科学家的头脑当中。因此，我们不会使用任何1982年之前的案例来描述这个问题在古老年代的意义，因为再往前追溯，它并未真正、严肃地被提出并加以审视。

在原始的战争年代，将军与将军、将军与下属间只能采用原始的方式——“出行靠走，通讯靠吼”的口头传输。这对应兰伯特论文提出算法中的第一部分的口头消息算法，简称OM（m）算法。这种情形，真伪很难辨别，只有当叛徒的总数不超过将军总数的1/3，成为一个特殊的“拜占庭容错系统”时，才能在很大的消息验证代价后，实现最终的一致行动。这个结果非常令人惊讶，如果将军们只能发送口头消息，除非超过2/3的将军是忠诚的，否则该问题无解。尤其是，如果只有三个将军，其中一个是叛变者，那么此时无解。但这样的错误，这样的有意、无意的“叛徒”却可能经常出现。无论是我们把“叛变的将军”替换成以下哪种，该问题都成立。

• 一个出故障的，向其他计算机不停发出不同错误信息的服务器；

• 一份为获取暴利而做出来的金融票据；

• 一份失效的医疗纠纷合同；

• 一份含混不清的保单；

• 一个可以发出消息，做出行动的错误信息节点。

而这里，每一个错误节点可以做任意事情：不响应；发送错误信息；对不同节点发送不同决定；不同错误节点联合起来攻击其他节点等。没准会出现比这更严重、更荒谬的错误。

如果说“叛变的拜占庭将军”是我们社会中各种类型的信息节点的隐喻，那么“拜占庭将军问题”所描述的情景，这样一个进攻／撤退命令极难验证真伪的中世纪战场，则无疑是我们当今越发缺乏中心化的、难以判别信息与产生信任的社会的极度悲观的隐喻。

用算法解决难题——区块链技术的雏形

构造出一个完美的、可以解决问题的“拜占庭容错系统”是一个不小的挑战。而且构造出来以后，其是否真的有效，能否经得起时间的考验与各方的质疑，这些都关乎着这个系统未来的命运与其创造群体的声誉。

2008年冬季，美国MIT（麻省理工学院）的密码学及密码学政策战略的邮件讨论组中，一位澳大利亚的企业家James A Donald（詹姆斯·A. 唐纳德）就对一位声称构造出了一个点对点的、不需要第三方权威认证的e-cash（电子现金）支付系统提出了质疑。而他的理由就是：对方设计的P2P系统不能够解决“拜占庭将军问题”。

在邮件中他挑剔地说道：“我们的确真的非常非常需要这个系统，但我所担忧的并不是信任的问题，而是如何获取一个全局共享的图景，借由此点而获取一致性的问题。每个人都知道X，这并不足够。我们需要让每个人都知道‘每个人都知道X’。而每个人都知道‘每个人都知道X’就是‘拜占庭将军问题’中，分布式的数据处理最难解决的问题。尤其是当X是非常庞大的数据时……”言下之意，他并不清楚或不确信这个去中心化的系统，如何解决拜占庭将军的难题。

仅仅在一天之后，他就收到了原作者的回复，一封简洁、优雅的邮件解释了在这个系统中，破解“拜占庭将军问题”的算法。

“工作量证明链”（proof-of-work chain）正是我解决“拜占庭将军问题”的方案。我将在那个语境中对它进行重新表述。

一群拜占庭将军，人手一台电脑想用字符串模式匹配的方法，暴力破解国王的Wi-Fi密码，当然他们已经事先获取了组成密码的字符串的长度。一旦他们开始模拟网络发送数据包，他们必须在一个限定的时间内完成破解工作，并清除服务器和电脑上的记录，否则他们就会被发现，那就麻烦了。只有当绝大多数将军在同一时间发起攻击和破解，这样才能有足够的CPU（中央处理器）和计算能力在短时间内完成破解工作。

他们并不特别在乎什么时候开始攻击，只要他们全部同意就好。一开始的时候，大家决定这样搞：任何人觉得时机到了都可以宣布一个攻击时刻。而且，不论是什么时候，只要是第一个被听到的攻击时刻，就将被确定为官方的攻击时刻。这样的话问题又来了，因为网络传达有延迟和干扰，如果有两个将军差不多同一时间公布了两个不同的攻击时刻，那么有的人会最先听到其中一个将军发布的攻击时刻，而又有些人则会最先听到另外一个将军发布的攻击时刻。

他们使用一个“工作量证明链”来解决这个问题。当每个将军接收到任何表达形式的第一个攻击时刻时，他都会设置他的计算机来求解一个极其困难的“工作量证明”问题，对这个问题的解答是一个哈希（Hash）散列，里面也将包含着这次的攻击时刻。由于这个“工作量证明”问题，非常难解，一般而言，就算所有人收到这个问题后同时求解，也至少需要10分钟才能产生解答。一旦一个将军解出了“工作量证明”，他将会把这个算出来的“工作量证明”向整个网络进行传播，每一个接收到的人，将在他们当前正在做的“工作量证明”计算的散列中附加上刚刚被求解出来的那个工作量证明。如果任何人正在计算他收到的其他的一个不同的攻击时刻，他们将会转向新的更新后的“工作量证明”计算当中，因为他现在的“工作量证明链”更长了。

两个小时后，将有一个攻击时刻被散列在一个有12个“工作量证明”的链中。每个将军只要通过验证（这条工作链的）计算难度，就能估算出平均每小时有多少CPU算力耗费在这上面，也就会知道：这一定是在分配的时间段内，绝大多数将军的计算机共同协作才能生成的结果。如果“工作量证明链”中展示出来的算力足够强大，可以破解国王的Wi-Fi密码，那么他们就可以在一致同意的时间内安全地展开攻击。

同步、分布式数据库和一个一致的、全局性的视野的问题如何解决？“工作量证明链”就是答案。

我们可以看到这封邮件解决了下面几个问题：

（1）引入一个困难的、需要10分钟求解的工作量计算，限制了网络中每个时刻中被提出的进攻时刻数目。

（2）将所有求解出的“工作量证明”都逐一加入，形成一个越来越长的链条，一个记录着所有“参与着攻击时刻哈希计算的将军、计算的‘工作量证明’、关于‘工作量证明’的计算的总体名录”。

（3）基于这条长链得出安全的进攻时刻的答案。

最后，请各位读者注意这封解释邮件头上的内容：

日期：2008年11月14日06:56:55（GMT+8）

邮件作者的签名：Satoshi Makamoto