3.3 拜占庭将军问题

在分布式系统中的一致性问题，即共识问题，被抽象成一个著名的问题：拜占庭将军问题。这个问题由Lamport于1982年提出，其描述如下。

一组拜占庭将军分别率领一支军队计划向某一城市进攻或者撤退，因为部分军队进攻而部分军队撤退的情况会造成灾难性后果，所以所有将军之间必须通过投票来达成一致的进攻或者撤退的决策。由于将军们在地理上是分隔开来的，因此他们之间只能通过信使进行通信。此处的问题在于将军中存在叛徒，叛徒可以传达一个误导的信息。例如有5个将军进行投票，其中有1名叛徒。4名忠诚的将军中2人投票进攻、2人投票撤退，叛徒给投票进攻的2个将军表示自己投票进攻，而给投票撤退的2个将军表示自己投票撤退。在这种情况下，在投票进攻的将军看来5个将军中有3个将军选择进攻，从而发起进攻；在投票撤退的将军看来5个将军中有3个将军选择撤退，从而发起撤退，这样一致性就遭到了破坏，如图3-2所示。

那么出现拜占庭将军问题时该如何解决呢？在区块链出现之前有两种解决方案：“口头消息”协议与“书面消息”协议。为了解释得更清楚，我们将将军分为司令和副官，司令是用来发送第一个命令的。

对于拜占庭将军问题，所有的解决方案必须遵守以下两个要求：

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

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

3.3.1 通过口头消息

只通过口头的方式来传递消息，可以达成一致的前提为：如果有 m 个叛徒，那么将军的总数必须大于3 m 个。下面是口头消息传递过程中一些预定义的条件：

●A1：每个发送的消息都会被正确传递。

●A2：信息接收者知道是谁发送的消息。

●A3：能够知道缺少的消息。

假设一共有 n 个将军参与共识，算法具体过程如下：

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

2）对于第 i 个副官而言， v _i 是第 i 个副官从司令处收到的命令，并将 v _i 命令发送给其余 n -2个副官。

3）对于第 i 个副官而言， v _j （ j ≠ i ）是第 i 个副官收到第 j 个副官发送来的命令。最后第 i 个副官使用majority（ v ₁ ,…, v _{n -1} ）得到最终命令。其中majority（ v ₁ ,…, v _{n -1} ）表示重复次数最多的命令。

下面考虑 n =4且其中叛徒人数为1的情况。

1.副官3是叛徒

第一步：司令向3个副官传达进攻的指令，如图3-3所示。

第二步：每个副官都将自己收到的指令发送给其他副官，由于副官3是叛徒，因此他给副官1与副官2发送的消息可能是假消息。

第三步：每个副官使用majority函数得出自己最终要做的指令，因此副官3无法干扰司令的决定，忠诚的副官都执行进攻指令，如图3-4所示。

2.司令是叛徒

第一步：司令向3个副官传达不同的指令，如图3-5所示，企图扰乱副官做出一致的决定。

第二步：每个副官都将自己收到的指令发送给其他副官，通过多数胜出函数majority，可以看出，副官最终仍然可以达成一致的命令，如图3-6所示。

3.3.2 通过书面消息

通过上述的口头传递协议可以看出，该方式最大的缺点是消息不能溯源，所以提出了书面消息协议。

在口头消息要求A1～A3的基础上，加入新的条件A4：

●签名不可伪造，一旦篡改即可被发现。

●任何人都可以验证司令签名的可靠性。

在书面带签名的方法中，对于存在任意 m 个背叛者，该方法都能使忠诚的将军达成一致（这个一致的结果不一定是正确的动作）。所以不管将军的总数 n 和叛徒的数量 m 是多少，只要采用该算法，忠诚的将军总能达成一致。

V _i 表示第 i 个副官收到的命令集。choice( V )表示副官决定采取何种行动的选择函数，这个函数需要满足以下三个条件。

●如果集合 V 中只存在一个元素 v ，那么choice( V )= v 。

●choice( O )=撤退，其中 O 代表空集。

●如果 V = V ′，那么choice( V )=choice( V ′)。

书面签名消息协议的算法如下所示：

1）对于每一个副官 i ，初始化集合 V _i =空集。

2）司令将带有签名的命令发送给每个副官。

3）对于每一个副官 i ：

●如果副官 i 从司令处收到指令 v :0且没收到其他命令，那么

■使 V _i ={ v }。

■发送 v :0: i 给其他所有副官。

●如果副官收到消息 v :0:( j ₁ : j ₂ :…: j _k )且 v 不在集合 V _i 中，则：

■添加 v 到 V _i 。

■如果 k ＜ n -1，那么发送 v :0:( j ₁ : j ₂ :…: j _k ): i 给每个不在 j ₁ ,…, j _k 中的副官。

4）对于副官 i ，当不再收到消息时，则遵循choice（ V _i ）的命令。

例如，在图3-7中司令是叛徒，所以司令给两个副官的指令是不同的。但是由于副官1和副官2得到的指令集相同{撤退，进攻}，因此忠诚的副官最终使用choice函数仍会遵循相同的指令。