拜占庭将军问题深入探讨

了解过比特币和区块链的人，都听说过拜占庭将军问题，或者听说过比特币(或区块链)的一个重要成果就是解决了拜占庭将军问题。但真正了解这个问题的人并不多，甚至知道这个问题本质的人也不多见。本文是一篇技术科普，将重点分析拜占庭一般问题本身的本质和经典算法，并讨论一些相关问题。作者参考了很多文献，掺杂了很多私货，却没有提出新的算法来解决这个问题，这不是本文的目的。

拜占庭将军问题是一个共识问题：由莱斯利兰波特和另外两人于1982年首次提出，被称为拜占庭将军问题或拜占庭失败。核心描述是军队中可能有叛徒，但攻击要一致，扩展到计算领域，发展成容错理论。随着比特币的出现和兴起，这个著名的问题重新进入公众视野。

对拜占庭将军问题的简单非正式描述如下：

拜占庭帝国想进攻一个强大的敌人，于是派出10支军队包围敌人。虽然这个敌人不比拜占庭帝国强多少，但足以抵挡五支常规拜占庭军队的同时进攻。由于某些原因，这10支军队不可能聚在一起进行单项突破，必须在单独的包围状态下同时进攻。他们没有机会单独攻击任何一支军队，除非至少有六支军队同时攻击以夺取敌国。他们分散在敌国各地，依靠通信兵之间的通信来协商攻击意图和攻击时间。困扰这些将领的问题是，他们不确定其中是否有汉奸，汉奸可能会擅自改变进攻意图或进攻时间。在这种状态下，拜占庭的将军们能不能找到一个分布式的协议，让他们远程协商，赢得战斗？这就是著名的拜占庭将军问题。

需要明确的是，拜占庭将军的问题是不考虑信号兵会不会被截获或者无法传达信息的，也就是从来不问消息传递的渠道。Lamport已经证明，在消息可能丢失的不可靠通道上，试图通过消息传递来实现一致性是不可能的。因此，在研究拜占庭一般问题时，我们已经假设通道没有问题，在这个前提下，我们将做一致性和容错性的相关研究。如果非要考虑渠道有问题，那就涉及到另一个相关的问题：两军的问题。

前面提到了，拜占庭将军问题和两军问题是有本质区别的。国内大量解释拜占庭将军的文章混淆了两个问题，实际上混淆了两个问题的本质，从而造成了很多误解。这两个问题看起来确实有点像，但是问题的前提和研究方向完全不同。

(图1:两军之间的问题举例说明)

如图1所示，白军驻扎在壕沟里，而蓝军分散在壕沟两边。白军比任何蓝军都强，但如果蓝军能同时一起进攻，就能打败白军。他们无法远程通信，只能派通信兵越过壕沟通知对方蓝军商议进攻时间。有没有能让蓝军赢的通信协议，是两军的问题。

你可能会发现两军的问题和拜占庭将军的问题差不多，但是一定要注意，通信兵要经过敌人的壕沟，在这个过程中他可能会被抓，也就是说两军问题中的通道是不可靠的，里面没有叛徒。这是两军问题和拜占庭将军问题的根本区别。可见，大量混淆拜占庭将领和两军的文章，并没有完全了解这两者。

两军问题的根本问题在于通道的不可靠性。相反，如果传递信息的渠道是可靠的，两军问题就可以解决 但是没有这样的渠道，所以两军的问题在经典情况下是无法解决的。为什么？

如果蓝军1号(以下简称1)给蓝军2号(以下简称2)发了一个信号兵，如果1想知道2是否收到了自己的信息，1必须让2给自己发一个收条，说“我收到了你的信息，我同意你的提议，明天上午10: 09准时进攻。”

但是，即使2已经发了这条消息，2也不确定1会在这个时候攻击，因为2发的回执1可能收不到。因此，1必须向2发送另一个收据，说“我收到了”，但1不知道2是否收到了这样的收据，因此1将期待2的收据。

虽然看起来很可笑，但是这个系统里总有一张收条，对双方来说可能都不完全确定。更何况我们还没有考虑到通信兵的信息可能被篡改。由此可尚力财经小编2022见，两军之间的问题在经典情况下是不可解的，不存在可以让蓝军获胜的通信协议。

不幸的是，作为现代通信系统中必须解决的问题，我们现在还不能完全解决，这意味着你我在传输时仍然可能丢失、监听或篡改信息。但是我们能以相对可靠的方式解决大多数情况吗？这需要说说TCP协议。其实你可以通过搜索“两军三交”找到很多与TCP协议相关的内容。如果你是传播学专家，你应该认为作者是在班门弄斧。这里只用最简单的方式来普及一下TCP协议的原理和局限性，可能会有一些毛刺。请原谅我。

？？？？？？？？尚力财经小编2022？？？？？(图2:TCP协议的基本原理)[X] [X]在TCP协议中，A先发送一个随机数X给B，B收到X后，再发送另一个随机数Y和x 1给A作为回复，这样A就知道B收到了，因为破解随机数X的可能性不大；然后A把y 1发回给B，这样B就知道A收到了。这样，A和B就可以建立可靠的连接，彼此相信对方已经收到并确认了信息。

其实A并不知道B是否收到了y ^ 1；此外，由于信道的不可靠性，X或Y可能被截取。这些问题说明即使是三方握手也不能完全解决两军的问题，但是我们在实际成本可控的情况下，把TCP协议作为两军问题的现实解决方案。

？？？？？？？？？？？？(图3:量子隐形传态示意图)

那么，我们能否找到一种理论方法，真正解决两军之间的问题呢？答案是肯定的，量子通信协议，作者不能够找出这个相当深刻的问题。据我所知，处于量子纠缠态的两个粒子，无论相距多远，都可以相互同步。只是直观上，这种效应可以用来实现安全通信。

但是由于测不准原理，一个粒子的状态一被测量就会发生变化，所以通信时必须通过不可靠的信道发送另一个消息。虽然这个“另一条消息”不可靠，但是因为已经有了一个绝对可靠的通道(量子纠缠)，所以保证了另一个通道即使不可靠也能可靠，否则被偷了也会被发现。

因此，我们可以相信，至少在理论上，这两个军事问题是可解的，即存在一种即使使用不可靠的信道也能保证信息传输可靠性的方法。所以在保证渠道可靠性的基础上，我们可以回到拜占庭将军的问题上继续讨论。

Part2:问题的本质和形式化

2.1。拜占庭将军问题的本质

但是一致性本身就能解决问题吗？想想看，如果万事俱备，客观上每一个忠诚的将军只要进攻就会胜利，但是因为汉奸的存在，他们都“一致”没有进攻；相反，将军们不应该因为条件不利而进攻，而是因为叛徒的存在，大家“一致”进攻

可以发现，仅仅“一致”不足以解决拜占庭将军的问题，我们还需要提出一个“正确”的要求。这个要求值得考虑，因为客观上可能存在一个“绝对正确”的判断，但对于每一个将军，每个人的判断可能都不一样。我们如何定义“正确”？我们不妨简单地说，正确就是每个忠诚的将军都正确地表达了自己的意思，不会因为叛徒让其他将军认为忠诚的将军是叛徒而拒绝使用他传达的信息。

到目前为止，我们已经把拜占庭将军的问题简化为：所有忠诚的将军都可以让其他将军收到自己的真实意图，最终统一行动；形式化的要求是“一致性”和“正确性”。

如果将问题一般化，可以发现一致性和正确性的算法并不要求命令必须是“攻击/撤退”或“1/0”，而是“发送消息1/发送消息2/待机”或“x/y/z/w”，这意味着拜占庭通用问题算法可以为许多分布式系统，如电力系统或网络系统提供启发。

可见这个问题归根结底是一个关于一致性和正确性的算法问题。这个算法针对的是忠诚的将领，因为叛徒可以做出协议之外的任何判断。我们只是想在汉奸的干扰下找到一个抗干扰的算法。为了解决这个算法问题，我们需要将形式需求具体化。

2.2。形式条件的推演

1)一致性

条件1:每个忠诚的将军必须得到相同的(v1，v2，…，vn)指令向量或指令集。

这就意味着忠诚的将军不一定把I将军发来的信息当成vi，I将军也有可能是叛徒。但仅凭这个条件，忠臣将军发出的信息也可能被修改，会影响正确性。

2)正确性

条件二：如果I将军是忠诚的，其他忠诚的将军必须取他送的值为vi。

这样我们得到了一致性和正确性的形式条件(条件1和条件2)，这是充分条件。 考虑到正确性条件是针对单个将军的，一致性条件是针对所有将军的，为方便起见，我们将一致性条件改写为

条件1 '无论将军I是忠诚的还是叛徒，任意两个忠诚的将军使用同一个vi。

条件1和条件1’完全等价。这是一个巧妙的一步转换，所以一致性条件(条件1 ')和正确性条件(条件2)只涉及一个将军I如何帮助其他将军接受他发出的值vi，所以问题可以简化为指挥官-副官模式，即一个指挥官将他的命令传递给n-1个副官，这样：

IC1:所有忠诚的副官都遵守一个命令，即一致性。

IC2:如果指挥官是忠诚的，每个忠诚的副官都遵守他的命令，这意味着正确。

IC1和IC2分别由条件1’和条件2进化而来。指挥官-副官模式只要指挥官遍历将军就可以成为完全问题，他们采用的算法可以完全一致。IC1和IC2构成了解决拜占庭将军问题的充分条件。在这种模式下，以指挥官副官的形式达成的协议，意味着指挥官的命令得到了有效的传达。如果有异议，有异议的将军会以指挥官的身份启动新的指挥官副官模式，征求自己的意见，协商达成一致。

接下来我们可以讨论拜占庭一般问题的算法。只要这个算法能满足IC1和IC2，就说明这个算法能有效解决拜占庭一般问题。

在经典案例中，我们可以找到两种方式，口头约定和书面约定。笔者将对两种算法的推导和证明逐一进行论述，证明部分将不采用纯推理，而主要介绍证明思路。

其实如果把算法推导完整，就能对算法有个大概的了解。口头协议和书面协议会有很多不同的启发。口头协议实现简单，但算法复杂，需要克服的困难更多。书面协议的算法本身很简单，但是可以克服很多问题，但是算法实现起来并不容易。这些差异使得它们有不同的使用场景和具体实现。

第三部分：口头协议

A1:发送的每条消息都能正确送达

A2:信息接收方知道消息是谁发送的

A3:可以知道丢失的消息

简而言之，信道绝对可靠，消息来源已知。不过需要注意的是，口头协议并不会告诉最后的消息来源是谁。

先讲结论：如果通过口头约定，叛徒的数量少于1/3，拜占庭将军的问题就可以解决了。即如果汉奸数量为m，将军总数n至少为3m ^ 1，则问题可以解决(即满足IC1和IC2)。

这个结论说明三模冗余系统只能容忍故障冻结错误，即一个部件发生故障后不能卡死(即知道错误后会出现的结果)，所以三模冗余就足够了。

但是对于拜占庭一般问题，因为叛徒可以做出各种判断，所以需要有一个四模块的冗余系统才能容错。口语协议算法就是把自己的订单告诉别人，拿别人的大部分订单得出自己的结论。但需要注意的是，其他将军的命令是用递归算法确定的。利用这种方法，可以保证忠诚的将军达到一致性和正确性的要求，即在叛徒数量不到1/3的情况下就可以解决问题。

那么，当叛徒数量小于1/3时，口述协议算法是如何实现容错的呢？接下来，作者将介绍Lamport在论文中提出的口语协议OM(m)算法。笔者将逐一介绍口头协议算法的详细内容、实例推导和证明，这部分需要你花一些时间去思考。

3.1。口头协议算法OM (m)

OM (0)算法(1)指挥官把他的命令发给每个副官。

(2)每个副官采纳指挥官发来的命令；如果没有收到命令，默认为撤退命令。

OM(m)计算法

（1）司令将他的命令发送给每个副官。

（2）对于每个i，vi是每个副官i从司令收到的命令，如果没有收到命令，则默认为撤退命令。副官i在OM(m-1) 中作为发令者将之发送给另外n-2 个副官。

（3）对于每个i，和每个j ≠ i，vj 是副官i 从第2步中的副官j （使用OM(m-1)算法）发送过来的命令，如果没有收到第2步中副官j 的命令，则默认为撤退命令。最后副官i 使用majority(v1,…,vn-1)得到命令。

其中，majority(v1,…,vn-1)代表了大多数人的命令，若不存在则默认为撤退命令。

要一遍读懂这个算法并不容易，笔者也是花了不少时间研究这一小段文字才弄明白的。不过您不用担心，笔者将会解释几个值得注意的点，并利用一个不难的实例来帮助您理解这个算法。

（1）算法始终保证了一个更加安全的默认值，这意味着若信息没有传到是可知的，并且传输时间不在考虑范围内。

（2）这个算法是一个递归算法，在OM(m)中需要采用OM(m-1)得到相关结果。m代表的是叛徒数量，从m到0，意味着对于每个将军，需要m+1轮的算法才能完成。

（3）该算法是关于m的，意味着使用该算法必须知道有多少个叛徒。或者说，利用该算法，可以保证叛徒数量在某一个最大值（即总将军数量的1/3）之下时，拜占庭将军问题可解。

（4）对于任意k

这个就是递归的意义，若您觉得笔者表达得不甚清楚，不用担心，您只用记住每一步都会牵涉到接下来很多步骤就可以了，之后将在实例推演中明白算法的核心思路。

3.2.口头协议实例推演

首先，笔者将先举一个m=1，n=3的例子来说明三模冗余的问题所在，并介绍m=1，n=4的时候系统是怎么容错的，这样您就可以明白算法是运行的。但由于m=1的时候并没有体现递归的过程（因为m-1就变成了0），笔者将再举一个m=2，n=7的例子来说明算法递推的过程。 （1）m=1，n=3的情形 n=3，意味着一个司令发送命令给两个副官，m=1意味着他们中有一个叛徒。 首先考虑司令忠诚而副官2是叛徒的情况。

（图4：m=1，n=3中司令忠诚而副官2是叛徒的情形）

司令把进攻命令传给了两个副官1和副官2，但是由于副官2为了不让他们达成一致，将司令的命令改成了撤退。那对于副官1来说，他应该怎么样判断？他无法知道是司令是叛徒还是副官2是叛徒，从而无法判断。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（图5：m=1，n=3中司令是是叛徒的情形）

而如果司令是叛徒，两个副官忠诚，司令会发送两个不同的命令。当两个副官对照命令时，他们又凌乱了，无法判断司令是叛徒或者对方是叛徒，从而又无法判断。这个情形非常简易的说明了三模冗余是无法动态容错的。（2）m=1，n=4的情形 n=4，意味着一个司令发送命令给三个副官，m=1意味着他们中有一个叛徒。 首先考虑司令忠诚而副官3是叛徒的情况。

（图6：m=1，n=4中司令忠诚而副官3是叛徒的情形）

倘若司令在OM(1)中给各副官发送的消息都是进攻（A），之后OM(0)时，叛徒副官3给副官1和副官2说他收到的消息是撤退（R）。那么对于副官1（或副官2）来说，他综合司令、副官3和副官2（或副官1）后得到的消息向量都将会是(A,A,R)，利用majority函数之后，将会采用A，满足了IC1和IC2（回顾IC1：所有忠诚的副官遵守一个命令，IC2：若司令是忠诚的，每一个忠诚的副官遵守他发出的命令）。

? （图7：m=1，n=4中司令是是叛徒的情形）

倘若司令是叛徒，那么我们已经不需要满足IC2。为方便，我们假设叛徒司令在OM(1)会给三个副官发送的信息是(x,y,z)，其中x，y，z都可以是A或R的任意一种。之后，三位忠诚的副官将会按照OM(0)要求的那样，交换他们收到的信息。

对于副官1，他综合司令、副官2和副官3后得到的消息向量将会是(x,y,z)，可以发现对于其他两个忠实的副官，他们得到的消息向量也将是(x,y,z)。不管x，y，z怎么样变化，majority(x,y,z)对于三人来说都是一样的，所以三个副官将会采用一致的行动。

（3）m=2，n=7的情形 接下来，我们将讨论m=2，n=7的情形，虽然只是多了一个叛徒，但是这里会出现递归过程，所以会复杂很多。

首先，我们先讨论司令忠诚的情形，假设叛徒为副官5和副官6。

? （图8：m=2，n=7中司令忠诚而副官5和副官6是叛徒的情形）

在OM(2)中，司令将攻击命令（A）传给各个副官。在OM(1)中，忠诚的副官们将会发送他们收到的消息（A），但由于副官5和副官6是叛徒，他们将会发送别的信息（比如R）。这时，忠诚的副官们将会采用使用OM(1)中的方法来确定各个v1~v6。例如，对于副官1，他收到了司令传来的命令，他会直接采用majority函数综合司令和其他将军传来的信息吗？他不会，因为这还在OM(1)中，他并不知道司令是不是叛徒，他会利用询问别人的方式来确认将军的命令，但是按照算法他会把司令的命令作为v1（即v1=A）并传给其他人。

接下来他会努力取得其他的v2~v6的值，这时已经在OM(1)中了，副官1绝不会轻易相信别人传来的消息，比如副官2给他传来了命令A，但是他会怀疑副官2传来的消息，所以他用OM(1)大法，问其他人副官2传给了他们什么，副官3和副官4诚实的告诉副官1，副官2给他们传的是A，而这时副官5和副官6又要撒谎了，他们又乱说，我们姑且假定他们传来的是x’和y’吧。这样，终于进入到了OM(0)，这时副官1将会综合其他副官对于v2的反馈，得到向量(A,A,A,x’,y’)，再利用majority函数，得到了v2=A。如下图，这是副官1在OM(1)中得到的信息（x，y等表示了不确定的命令）。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（图9：司令忠诚时副官1在OM(1)中得到的信息）

我们就可以得到副官1的v1~v6向量为(A,A,A,A,x,y)，利用majority函数，副官1最终采用的行动会是A。 类似的，我们可以发现，其他几个忠诚的副官得到的命令向量都会是(A,A,A,A,x,y)，利用majority函数后采用的行动都会是A。所以，我们可以发现忠诚的副官采用的命令都是A（满足IC1），并且和忠诚的将军的命令一致（满足IC2）。至此，您应该已经明白了这个算法是怎么递归的，不管m等于多少，都只是一个算法步骤多寡的问题。 至于司令是叛徒的情形，其实是相似的，这里简单的再提一下便于理解。若您已经明白了算法过程，完全可以跳过。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （图10：m=2，n=7中司令和副官6是叛徒的情形）

为方便，我们假定了副官6是叛徒。司令在OM(2)中就很鸡贼的给副官1~副官6发送了不同的命令(A,R,A,R,A,x)。在OM(1)中，各副官把自己收到的命令传出去，而（为方便，假定）副官6则给其他副官分别发送了(A,R,A,R,A)。类似于前文推演的那样，考虑副官1，他将司令传来的命令A作为v1后，还会询问其他人传来的命令，由此去确认v2~v6，类似的，我们将之表达为下图：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（图11：司令反叛时副官1在OM(1)中得到的信息）

如图，我们就可以得到副官1的v1~v6向量为(A,R,A,R,A,A)，利用majority函数，副官1最终采用的行动会是A。类似的，我们可以发现忠诚的副官1~副官5得到的消息向量都是(A,R,A,R,A,A)，最终他们采用的行动都会是A（满足了IC1），而司令是叛徒不需要满足IC2。值得提醒的是，若副官6传递的是(R,A,R,A,R)，那么他们所有人得到的消息向量都是(A,R,A,R,A,R)，此时A和R数量一样多，这并不代表majority不起作用了，他将采用默认值R（回顾前文：majority(v1,…,vn-1)代表了大多数人的命令，若不存在则默认为撤退命令），所有人的行动都会采用R，这同样是满足的。

到此为止，我们已经将口头算法的实例推演进行的很彻底了，若您还有兴趣，可以试一试当n=7，m=3的时候为什么就不能达成一致了，操作是类似的。 3.3.口头协议算法证明 算法的证明思路其实并不复杂，简单的来说，对于一个递归算法，我们使用数学归纳法来证明是最直观而又有效的方法了。我们回顾一下命题：将军总数为n，叛徒数量为m，OM(m)可以实现，在n>3m的情况下，使得：

IC1：所有忠诚的副官遵守一个命令。

IC2：若司令是忠诚的，每一个忠诚的副官遵守他发出的命令。

为了证明整个命题，我们先引入一个针对IC2的引理：

引理：对于任意m和k，如果有超过2k+m 个将军和最多k 个背叛者，那么算法OM(m)满足IC2。

证明：

（1）m=0，而将军是忠诚的，直接满足IC2；

（2）m>0，此时假定OM(m-1)是有效的，那么只需要考虑OM(m)这一轮即可。

n>2k+m，意味着n-1>2k，n-1是除了司令以外的所有副官，而所有副官的数量比叛徒的两倍还多，那他们直接利用majority函数的时候，就可以直接正确得到司令的命令。可以发现，这个引理说明了如果只需要考虑IC2，将军总数是不需要3倍背叛者之多的，接下来我们回归命题。

证明：

首先考虑司令是忠诚的，令引理中的k=m，直接得到OM(m)可以满足IC2。

这时，我们只用考虑司令是叛徒的状况。同样利用数学归纳法。

（1）m=1，之前我们已经推演过OM(1)可以满足1个叛徒司令，3个忠诚副官的情况；

（2）m>1，那么假设n’>3m’的情况下，OM(m-1)能够满足IC1和IC2。

由于司令是叛徒，在OM(m)中司令会把命令发给各个副官，而这些副官中会有m-1个叛徒。在下一轮中，副官的数量至少有3m个，叛徒数为m-1，很显然3m>3(m-1)，也就是说n’>3m’，根据假设，OM(m-1)可以满足IC1和IC2，尽管司令是叛徒，由于OM(m-1)是有效的，OM(m)这一轮中忠诚的副官可以得到相同的(v1,…,vn-1)向量，所以忠诚的副官将会利用majority函数采用相同的命令，得证。

总结一下，口头协议中，我们始终要求的是相同的(v1,…,vn-1)向量，只要这个向量是相同的我们怎么处理都可以。又由于算法是递归的，所以我们一定需要把这个处理方法变得通用而逻辑有效才行，所以我们才选用了majority函数这个算法。这一点至关重要却又没有这么直观，因为我们的第一反应是要得到相同的majority函数值。但是反过来一想，既然算法是递归的，majority函数值相同不就意味着(v1,…,vn-1)向量相同吗？正确理解递归的思想是使用该算法和利用数学归纳法证明该算法的关键点。

至此，我们已经大致明确了口头协议是怎么回事，可以做到什么不能做到什么，以及这个算法的推演和证明。很多系统都会出现口头协议的情况，即各个系统节点可以把自己的消息准确的发送出去，同时可以知道消息的来源于何处。但是，这个方法的消息并不能追本溯源，这使得在口头协议中至少得四模冗余，我们可以试图找到一个方法，让消息能够追本溯源，可以想象这能够拓宽使用条件，这个方法可以是书面协议。

Part4：书面协议

口头协议中我们讨论了很多，揭示了口头协议的缺点是消息不能追本溯源，这使得口头协议必须在四模冗余的情况下才能保证正确。但是，若能引入一种方法让消息能够追本溯源，情况会不会有所改变呢？这就是书面协议引入的灵感。除了A1，A2和A3以外，我们在口头协议之上添加一个条件A4，使之成为书面协议

A4：（a）签名不可伪造，一旦被篡改即可发现，而叛徒的签名可被其他叛徒伪造；（b）任何人都可以验证签名的可靠性。

那么，我们先说结论：对于任意m，最多只有m个背叛者情况下，算法SM(m)能解决拜占庭将军问题。也就是说，在使用签名的情况下，书面协议可以打破三模冗余的僵局，使用了签名的情况下，只要知道了叛徒数量，我们就可以利用SM(m)算法解决拜占庭将军问题。

4.1.书面协议算法SM(m)

口头协议算法我们已经讨论过很多了，所以笔者对书面协议尽量简短的介绍。回顾IC1：所有忠诚的副官遵守一个命令，即一致性。

IC2：若司令是忠诚的，每一个忠诚的副官遵守他发出的命令，即正确性。

我们要找到一个算法SM(m)，不管将军总数n和叛徒数量m，只要采用该算法，忠诚的将军总能达到一致（满足IC1和IC2）。我们用集合Vi来表示i副官收到的命令集，这是一个集合，也就是满足互异性（没有重复的元素）等集合的条件。类似的，我们定义choice(V)函数来决定各个副官的选择，这个函数可以有非常多种形式，他只要满足了以下两个条件：

（1）如果集合V只包含了一个元素v，那么choice(V)=v

（2）choice(o)=RETREAT，其中o是空集

任何满足了这两个条件的函数都可以作为choice()，例如取平均值就可以。我们只需要根据具体情形定义choice()即可，这个非重点，笔者并不加以讨论，您可以自行思考。之后我们会发现SM(m)算法并不是一个递归算法，我们只要让各个副官收到的V集相同，choice(V)也一定能够得到相同的值。

简单解释该算法如下：

初始化Vi=空集合。

（1）将军签署命令并发给每个副官；

（2）对于每个副官i：

（A）如果副官i从发令者收到v:0的消息，且还没有收到其他命令序列，那么他

（i）使Vi为{v}；

（ii）发送v:0:i给其他所有副官。

（B）如果副官i收到了形如v:0:j1:…:jk的消息且v不在集合Vi中，那么他

（i）添加v到Vi；

（ii）如果k

（3）对于每个副官i，当他不再收到任何消息，则遵守命令choive(Vi)。

值得注意的是，如果司令忠诚，由于其签名不可伪造，所有忠诚的副官都将得到一个单点集{v}，他们采用的命令集Vi相同，得到的choive(Vi)也为v，满足了IC1和IC2。

如果司令并非忠诚，只需要满足IC1，但是算法SM(m)使得所有忠诚的副官得到相同的Vi，使用choice()函数后采用的命令也就一定相同。

4.2.书面协议实例推演

司令是叛徒的状况稍难想象，举个例子，n=3，m=1，其中司令是叛徒，这是口头协议不能解决的状况。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（图12：m=1，n=3中司令是叛徒的情形）

很显然，副官1得到的V1={A,R}，副官2得到相同的V2={A,R}。他们采用choice函数后得到的命令一定相同。

相似的，n=4，m=2，其中司令是叛徒，这同样是口头协议不能解决的状况。

（图13：m=2，n=4中司令和副官3是叛徒的情形）

副官1和副官2得到的V1=V2={A,R}，他们采用choice函数后得到的命令也相同。即使命令不是布尔值，经过上面的分析框架，也可以得到相似的结论。至于这个算法的证明，有兴趣的读者可以参考Lamport的原文，笔者就不做过多解释了，如有问题仍可与笔者联系。

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （图14：Lamport在论文中对书面协议算法的证明）

书面协议的本质就是引入了签名系统，这使得所有消息都可追本溯源。这一优势，大大节省了成本，他化解了口头协议中1/3要求，只要采用了书面协议，忠诚的将军就可以达到一致（实现IC1和IC2）。这个效果是惊人的，相较之下口头协议则明显有一些缺陷。

书面协议的结论非常令人兴奋，这不是解决了拜占庭将军问题了吗？但请注意我们在A1~A4中实际上是添加了一些条件的，这使得拜占庭将军问题在这些假设下能够解决，但是在实际状况中却会有一些问题。观察A1~A4，我们做了一些在现实中比较难以完成的假设，比如没考虑传输信息的延迟时间，书面协议的签名体系难以实现，而且签名消息记录的保存难以摆脱一个中心化机构而独立存在。事实上，存在能够完美解决书面协议实际局限的方法，这个方法就是区块链。如果您感兴趣，也可以参考笔者同系列的文章《大材小用——用区块链解决拜占庭将军问题》。

作者：毒毒程审校：初夏虎 村长责编：printemps稿源：资讯

标签： 呈

本文地址： https://www.zesyz.com/news/39571.html

版权声明：本文内容由互联网用户贡献，该文观点仅代表作者本人。本站不拥有所有权，不承担相关法律责任。如发现有侵权/违规的内容， 请联系我们：dudu818907@gmail.com，本站将立刻清除。