SCRY技术分享拜占庭将军问题的简述

拜占庭的简述

本文将用于介绍著名的拜占庭将军问题。在介绍拜占庭将军问题之前，先简单说一下拜占庭。拜占庭帝国，在古代西欧也被称之为东罗马帝国。是一个位于欧亚交界处的封建君主制国家，其领土包括现在的欧洲南部，西亚和北非。公元四世纪左右，罗马帝国开始分列为罗马东部和罗马西部，这两个国家都被视为罗马正统，大概到公元十世纪，罗马西部陷落，随着神圣罗马帝国的建立，罗马东部失去了罗马这个单词的独占权，开始被称之为东罗马帝国。大概在16世纪之后，开始出现了拜占庭帝国的说法。值得一提的是，拜占庭帝国的首府君士坦丁堡被第四次十字军东征攻陷，从此一蹶不振。1453年5月29日，君士坦丁堡被强大的奥斯曼帝国攻陷，末代皇帝君士坦丁十一世战死。东罗马帝国就此终结。当然，此文不是介绍东罗马帝国历史的文章，在此仅简述拜占庭帝国的历史。

拜占庭将军问题是什么

拜占庭将军问题和拜占庭的历史其实并无关联，拜占庭将军问题也不是历史上真实存在的问题，他是著名计算机大神兰伯特于1982年提出的。拜占庭问题描述的是如下的场景：

假设有一座城堡，拜占庭帝国想攻陷这座城堡。所以派出了很多支军队，因为通讯条件很落后，军队和军队之间必须经过信使来传递作战命令。城堡十分坚固，可以抵御一两只军队的进攻。只有所有军队同时进攻，才可以攻陷城堡。为了保证作战命令的统一，提出一个办法，投票。超过半数投票决定作战命令。比如：决定明天早上进攻，如果有半数的军队同意这个作战计划。则在明日早晨开始一起进攻。反之，如果一大半人都不同意明天早上进攻，则明早就不进攻。现在存在的问题是：军队中有叛徒。叛徒会随意调整作战命令。

我们现在用图一来表示这种困境，在图示中，我们用黄色的小人代表正常的部队，粉色的小人代表判叛徒。A表示进攻Attack，R代表拒绝Reject。因为正直的的部队会忠实的执行命令，所以我们把A和R标记在他们身上。

如图所示，身上标记A的三位将军表示他们决定“明早发动进攻”，身上标记R的三位将军决定明早不应该发动进攻，现在叛徒至关重要。叛徒的这一票将决定明早是否决定进攻。这时候叛徒给三位决定进攻的将军传递的消息是明早发动进攻，给三位不进攻的将军发送的消息是明早不发动进攻。所以三位决定进攻的将军知道了，有4票发动进攻的，那么大多数人决定进攻那我明早就发动攻势。三位不进攻的将军则知道，有四票不发动进攻的，那我明早不进攻。所以拜占庭难度就产生了，这些部队有的进攻有的撤退，战斗就失败了。

以上的图示和背景就是拜占庭问题或者称之为拜占庭容错问题。

兰波特之问

所以兰波特提出这个问题是为什么呢？

兰波特描述的是：世界上有很多个计算机，分布在世界上不同的位置。这些分布在不同地理位置的计算机，就像是驻扎在不同城市的将军们一样。但是计算机会出故障，也有可能会有黑客攻击，或者直接加入恶意节点。这些坏掉的计算就相当于叛徒。在这种状况下，我们如何保持一致性，就是指这些忠诚的计算机，他们的结果是一样的。另外我们关心的问题是，如何保持正确性。这里对正确性作出解释：如果大多数将军说要进攻，那我们就应该进攻，如果大多数将军说撤退，那我们就该撤退。尽管系统中存在故障和恶意节点，但是我们大多数节点都可以保持一致性和正确性，我们的系统还是正常的。这个问题发展至今，已经有四十余年的历史了。

为此也提出了分布式系统的原则

一致性

正确性

兰波特针对这个问题提出了自己的解法。

口头协议

书面协议

为了描述口头协议，我们提出了一个将军副官模型，其实哪个人是将军，哪个人是副官并不重要。所谓将军就是第一个发起命令的人：比如将军做出决定明早进攻，然后传递给其他人。其他人都叫做副官，副官可以执行将军的命令。为此我们需要两个假设：

忠诚副官，所有忠诚的副官必须执行同一个命令。比如一起进攻，一起撤退。

忠诚将军，如果将军是忠诚的，所有忠诚的副官必须执行他的命令。

以上的假设的前提是忠诚，因为无论是司令还是副官，他们都有可能是叛徒，叛徒的行为不可预测。以上两个原则分别对应分布式协议的基本原则，一致性，准确性。

怎么做到这一点呢？

兰波特提出，假如一共有n个将军，其中有m个叛徒。当n>3m时，这个问题是可解的。

比如我们有10个将军，有2个是恶意的10>3*2，这个问题是可解的。但是有三个人，其中有一个是叛徒，那这个问题是不可解的。因为没有满足n>3m。

举个栗子：

假定有3个将军1个叛徒，n = 3, m =1

如上图所示，身上带有c标志的为commander，表示为发起命令的人。其他人副官，身上标记1，2。继续用粉色表示叛徒。现在将军给副官1，2发送进攻命令。忠诚副官1接到进攻命令之后并不会决定发起进攻，因为他也不知道将军是否是忠诚的，所以他继续询问2，是否发动进攻。但是2是叛徒，他自己接受到c的进攻命令，他传递给1的命令是不进攻。这时1会收到两个消息，进攻和不进攻，1比1。所以他就没办法决定自己是进攻还是不进攻。

接下来，我们转换视角，考虑将军是叛徒的问题。将军分别给1下达了进攻指令，给2下达了撤退指令。此时1收到进攻指令后，继续询问2。2忠诚的传递了自己收到的命令不进攻。此时1收到的信息又是一票进攻一票撤退，无法决定。2面临的也是同样的问题。所以在n=3，m=1的情况下，这个问题是无解的。

下面我们来看有解的状况。

下一种状况下，n=4，m=1。即一共有四个将军，一个叛徒。

还是依照之前图例表示各种部队的性质。将军c给副官1，2，3，4发送进攻的通知。1接到进攻的通知之后再询问2，到底接了什么命令。因为2是忠诚的，所以如实的传递自己得到是进攻A。然后再询问副官3。副官3因为是叛徒，告诉1自己得到的是撤退。这时，1一共接到3个消息，两个进攻一个撤退。按照多数原则，他就可以确定第二天可以进行进攻。如果我们按照同样的方法去分析2，他得到结果是类似的。所以决策之后，所有忠诚的副官均进行一样的命令进攻，而且在司令官为忠诚的情况下，所有副官执行和司令官一样的命令进攻。刚好符合前面定下来的原则。

接下来我们看更加复杂的状况，将军是叛徒的情况。假设将军给1，2，3号分别发送了进攻，进攻和撤退三个命令。

我们站在1的角度，接受到司令的进攻命令，然后和2交换信息得到一个进攻，再和3交换信息。得到两个进攻和一个撤退，所以可以决定执行进攻。

从2的视角出发，2接到司令官的进攻信息，从1得到进攻信息，从3得到撤退信息。所以可以执行进攻。

从3的视角出发，3从司令官那里接到撤退信息，从1得到进攻，从2得到进攻。所以可以执行进攻。

总体来看，因为司令官不是忠诚的，所以不用顾虑司令官忠诚的条理。同时123都是忠诚的，他们同时执行进攻。也符合假设。所以这种情况下，是可解的。

我们再次提升复杂度，探讨有两个叛徒的情况，即便m=2。根据公式，要想问题有解，我们必须要有七个人。n=7

情况较为复杂，就不在图上标注各位副官之间的信息交互情况，仅标注司令官给各位副官下达的命令。在描述这个情况情况之前，先强调一下这里分析需要的思路：递归。递归简单来说就是套娃，比如你照镜子的时候，再拿第二面镜子对着镜子中的自己。或者你在直播的时候，用摄像头对着自己的屏幕。这里不是专门的算法分析介绍，不再强调递归。

回到图上，我们假设司令官是忠诚的，其中5和6号副官是叛徒。他给每个副官都下达了进攻命令。

下面我们来列一个表格表述现在的状况

我们从1出发来看这个表格，看看一号副官是如何决策的。1毫无疑问接到了将军的进攻命令。但是他不可能接受到将军的命令就进攻，还是要交流，确定别人都接受到的是什么命令。

首先他要确定2接受的是什么命令。

第一重分析，他直接问V2，V2接受到了什么命令。2是忠诚的自然是说：2接受的是进攻。然后1开始问V3：V2接受的是什么命令。依次类推。因为5号和6号是叛徒，他说什么都可能，随意用无关字母小写的a,b来表表示。根据多数原则，1可以确定一件事，2号接受的确实是进攻命令。

接下来他开始确定v3到底接受的是什么命令。忠诚副官其实得到的信息分析都是类似的，我们不再重复。

我们直接开始决策V5和V6，即开始确定5号和6号得到的是什么命令。以5为例，因为2是叛徒，所以我们直接用不同的字母表示他给别人说自己得到的是什么。最终我们其实不清楚他所说的大多数命令是什么，所以用X表示，他可能是进攻也可能是撤退。

每一类的问题分析完之后，1不难得出结论，2，3，4号得到命令是进攻。至于5和6他们得到什么样的命令并不会影响最终决定。所以再分析完A的决策状况之后，他的决策就确定下来了：进攻。

有兴趣的话们可以自行填充上面的表格，也可以站在2，3，4，5，6的角度上再次进行分析。总而言之，这种状况下，拜占庭将军问题是有解的。

最终结论，1，2，3，4会选择进攻，而且忠诚的将军下发的进攻命令也会被忠诚的副官执行。

有兴趣的话，也可以推演一下将军和6号是叛徒的情况。

通过以上的分析不难看出，这个算法的复杂度相当之高。而且波兰特提出这个问题的时候是不考虑网络延迟的，所以这个方法在计算机中并不会被使用。后来又有人提出了更加高效的PBFT算法。有兴趣的话可以阅读相关的论文。

结尾

拜占庭容错问题和区块链息息相关。区块链的问题也是要解决一致性问题。简单来说，以比特币为首的区块链提出了POW算例证明。需要节点都参与解决数学题，如果率先解决数学难题，则有记账的权利。无疑增加了恶意节点的成本，你必须别其他节点做的更快才有作恶的权利。后来还有也陆续提出了POS算法，DPOS算法等。也是为了解决本文开始提到的一致性和正确性问题。希望本文可以帮大家建立对于拜占庭容错问题的基本概念。

—-

编译者/作者：scry

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。