拜占庭将军问题深入探讨

## 拜占庭将军问题深入探讨  了解过比特币和区块链的人，多少都听说过拜占庭将军问题，或听说过比特币（或区块链）的一个重要成就正是解决了拜占庭将军问题。但真正明白这个问题的人并不多，甚至知道这个问题实质的人都很罕见。本文是一篇技术科普，将重点提供了拜占庭将军问题本身对本质及经典算法的解析，并探讨与之相关的一些问题。笔者参考了不少文献，夹杂了大量私货，但并没有提出解决该问题的新算法，这也不是本文的目的。 ## Part1：拜占庭将军问题是什么 拜占庭将军问题是一个共识问题: 首先由Leslie Lamport与另外两人在1982年提出，被称为The Byzantine Generals Problem或者Byzantine Failure。核心描述是军中可能有叛徒，却要保证进攻一致，由此引申到计算领域，发展成了一种容错理论。随着比特币的出现和兴起，这个著名问题又重入大众视野。 ### 1.1\. 拜占庭将军问题场景 关于拜占庭将军问题，一个简易的非正式描述如下： 拜占庭帝国想要进攻一个强大的敌人，为此派出了10支军队去包围这个敌人。这个敌人虽不比拜占庭帝国，但也足以抵御5支常规拜占庭军队的同时袭击。基于一些原因，这10支军队不能集合在一起单点突破，必须在分开的包围状态下同时攻击。他们任一支军队单独进攻都毫无胜算，除非有至少6支军队同时袭击才能攻下敌国。他们分散在敌国的四周，依靠通信兵相互通信来协商进攻意向及进攻时间。困扰这些将军的问题是，他们不确定他们中是否有叛徒，叛徒可能擅自变更进攻意向或者进攻时间。在这种状态下，拜占庭将军们能否找到一种分布式的协议来让他们能够远程协商，从而赢取战斗？这就是著名的拜占庭将军问题。 应该明确的是，拜占庭将军问题中并不去考虑通信兵是否会被截获或无法传达信息等问题，即消息传递的信道绝无问。Lamport已经证明了在消息可能丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的。所以，在研究拜占庭将军问题的时候，我们已经假定了信道是没有问题的，并在这个前提下，去做一致性和容错性相关研究。如果需要考虑信道是有问题的，这涉及到了另一个相关问题：两军问题。 ### 1.2.与拜占庭将军相关问题：两军问题 正如前文所说，拜占庭将军问题和两军问题实质是不一样的。国内大量解释拜占庭将军问题的文章将两者混为一谈，其实是混淆了两个问题的实质，由此造成了许多误解。这两个问题看起来的确有点相似，但是问题的前提和研究方向都截然不同。 （**图1：两军问题图示**） 如图1所示，白军驻扎在沟渠里，蓝军则分散在沟渠两边。白军比任何一支蓝军都更为强大，但是蓝军若能同时合力进攻则能够打败白军。他们不能够远程的沟通，只能派遣通信兵穿过沟渠去通知对方蓝军协商进攻时间。是否存在一个能使蓝军必胜的通信协议，这就是两军问题。 看到这里您可能发现两军问题和拜占庭将军问题有一定的相似性，但我们必须注意的是，通信兵得经过敌人的沟渠，在这过程中他可能被捕，也就是说，两军问题中信道是不可靠的，并且其中没有叛徒之说，这就是两军问题和拜占庭将军问题的根本性不同。由此可见，大量混淆了拜占庭将军问题和两军问题的文章并没有充分理解两者。 两军问题的根本问题在于信道的不可靠，反过来说，如果传递消息的信道是可靠的，两军问题可解。然而，并不存在这样一种信道，所以两军问题在经典情境下是不可解的，为什么呢？ 倘若1号蓝军（简称1）向2号蓝军（简称2）派出了通信兵，若1要知道2是否收到了自己的信息，1必须要求2给自己传输一个回执，说“你的信息我已经收到了，我同意你提议的明天早上10点9分准时进攻”。 然而，就算2已经送出了这条信息，2也不能确定1就一定会在这个时间进攻，因为2发出的回执1并不一定能够收到。所以，1必须再给2发出一个回执说“我收到了”，但是1也不会知道2是否收到了这样一个回执，所以1还会期待一个2的回执。 虽然看似很可笑，但在这个系统中永远需要存在一个回执，这对于两方来说都并不一定能够达成十足的确信。更要命的是，我们还没有考虑，通信兵的信息还有可能被篡改。由此可见，经典情形下两军问题是不可解的，并不存在一个能使蓝军一定胜利的通信协议。 不幸的是，两军问题作为现代通信系统中必须解决的问题，我们尚不能将之完全解决，这意味着你我传输信息时仍然可能出现丢失、监听或篡改的情况。但我们能不能通过一种相对可靠的方式来解决大部分情形呢？这需要谈到TCP协议。事实上，搜索“两军问题与三次握手”，您一定可以找到大量与TCP协议相关的内容。若您是通信方面的专家，权当笔者是班门弄斧，这里仅用最浅显易懂的方式科普TCP协议的原理和局限，可能存在一些毛刺，请多包涵。                                                                                                                                                                                                   **（图2：TCP协议的基本原理）** TCP协议中，A先向B发出一个随机数x，B收到x了以后，发给A另一个随机数y以及x+1作为答复，这样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.形式化条件的推演 定义一个变量vi（为不失一般性，并不要求vi是布尔值），作为其他将军收到的第i个将军的命令值；i将军会将把自己的判断作为vi。可以想象，由于叛徒的存在，各个将军收到的vi值不一定是相同的。之后，定义一个函数来处理向量(v1,v2,…,vn)，代表了多数人的意见，各将军用这个函数的结果作为自己最终采用的命令。至此，我们可以利用这些定义来形式化这个问题，用以匹配一致性和正确性。 **1）一致性** 条件1：每一个忠诚的将军必须得到相同的(v1,v2,…,vn)指令向量或者指令集合。 这意味着，忠诚的将军并不一定使用i将军送来的信息作为vi，i将军也可能是叛徒。但是仅靠这个条件，忠诚的将军的信息送来的信息也可能被修改，这将影响到正确性。 **2）正确性** 条件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，就代表这个算法可以切实有效的解决拜占庭将军问题。 在经典的情形下，我们可以找到两种办法，`口头协议`和`书面协议`。笔者将会逐一探讨两种算法的推演和证明，其中证明部分并不会采用纯推理，而以介绍证明思路为主。 事实上，若完整进行了算法推演，对算法已经能够有一个大致的了解。口头协议和书面协议会有很多不同的启发，口头协议的实现起来简单，但是算法复杂，同时需要克服的困难更多；书面协议的算法本身很简单，却能够克服很多问题，但是实现算法并不容易。这些不同让两者有了不同的使用场景和具体实现。 ## Part3：口头协议 首先，我们明确什么是口头协议。我们将满足以下三个条件的方式称为口头协议： **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）**对于任意k3m的情况下，使得： **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 ';