(28DW-S8-Day9) 区块链如何对坏节点容错：拜占庭将军问题

坏节点

在去中心的分布式网络中，不同的节点通过通讯交换信息达成共识而按照同一套协作策略行动。但当某些节点坏掉或者是恶意的，它们可能向外界广播错误信息或不广播信息，用于传递信息的通讯网络也可能导致信息损坏，此时：

• 某个节点如何验证信息的准确性。

• 网络整体如何保证一致性。

拜占庭将军问题

场景设定([2])：

多个拜占庭将军分别各率领一支军队共同围困一座城市。

各支军队的行动策略限定为进攻或撤离两种。

部分军队进攻、部分军队撤离可能会造成灾难性后果，因此各位将军必须通过投票来达成一致策略，即所有军队一起进攻或一起撤离。

各位将军分处城市不同方向，他们只能通过信使互相联系。 在投票过程中每位将军都将自己投票给进攻还是撤退的信息通过信使分别通知其他所有将军。 每位将军根据自己的投票和其他所有将军送来的信息就可以知道共同的投票结果而决定行动策略。

核心问题：

将军中存在叛徒，他们不仅可能向较为糟糕的策略投票，还可能选择性地发送投票信息。

也就是会影响到：准确性和一致性。

早期解决方法

莱斯利·兰波特大神给出了递归式解法([2,3])。

• 原理：叛徒数小于 1/3 时就有解，反之无解。

• 假设 总数为 n, 叛徒数为 m, 那么就是 n>3m

简化为 司令-副官问题

可以简化为一个司令(commander)以及若干个副官的模型。

司令来下达命令，副官接收命令并广播给其他副官。

只需要达到如下要求，即为 solution:

• (1)忠诚的副官遵守同一个命令

• (2)若将军是忠诚的，所有忠臣的副官执行他的命令

• (3)若将军是叛徒，则满足(1)即可

m=1，n=4 时

case1: 司令 c 是忠诚的

• 假设副官 g1,g2,g3 中 g3 是叛徒

• 司令向所有副官下达 A(ttack)命令

• g1,g2 收到 A，且对其他副官广播 A。

• g3 收到 A，胡乱对 g1,g2 发送随机命令。

• g1,g2 最少会收到 2 个以上 A 命令(包含 c 的)，因此会选择 Attack

case2: 司令 c 是叛徒

• 副官 g1,g2,g3 都是忠诚的

• 司令 c 向每个副官随机下达命令(Attack/Retreat)， 比如: A->g1, A->g2, R->g3

• g1,g2,g3 分别向其他副官广播自己收到的命令

• 最终：g1 收到(A, A, R)g2 收到(A, A, R)g3 收到(R, A, A)因此，g1,g2,g3 会一致执行 Attack

m=2，n=7 时

大致过程：

• 司令下达命令(如果是叛徒，可能是不一致命令，否则下达一致命令)

• 每个副官收到来自司令的命令

• 每个副官向外广播(如果是叛徒，胡乱广播，否则广播自己收到的命令)

• 每个副官 i 确认逐个确认

• 每个副官 j 给其他所有副官 k 的命令，并取多数项为结果

• 每个副官 i 确定自己的决策

后面三步其实就是一个递归嵌套的 m=1 问题。相当于把每个副官 j 挨个当司令检验一遍。

还有很多其他解法

以上方法没有考虑网络延迟，后来陆续提出了 PBFT 等算法以及一众拜占庭容错（BFT）的通信协议。

比特币的解法

中本聪在比特币中给出的解决方法就是通过增加叛徒的成本，也就是 PoW（工作量证明）来增加传播错误信息的成本，以维护整个系统的运行状态的一致性。

参考文献

• 卓克《密码学原理》

• Byzantine Generals Problem，wikipedia

• 李永乐：《比特币和区块链的原理》视频