共识算法？拜占庭将军问题之区块链

零度财经

拜占庭问题更为广泛，讨论的是允许存在少数节点作恶（消息可能被伪造）场景下的一致性达成问题。拜占庭算法讨论的是最坏情况下的保障。

中国将军问题

拜占庭将军问题之前，就已经存在中国将军问题：两个将军要通过信使来达成进攻还是撤退的约定，但信使可能迷路或被敌军阻拦（消息丢失或伪造），如何达成一致。根据 FLP 不可能原理，这个问题无解。

拜占庭问题

又叫拜占庭将军（Byzantine Generals Problem）问题，是 Leslie Lamport 1982 年提出用来解释一致性问题的一个虚构模型。

拜占庭是古代东罗马帝国的首都，由于地域宽广，守卫边境的多个将军（系统中的多个节点）需要通过信使来传递消息，达成某些一致的决定。但由于将军中可能存在叛徒（系统中节点出错），这些叛徒将努力向不同的将军发送不同的消息，试图会干扰一致性的达成。

拜占庭问题即为在此情况下，如何让忠诚的将军们能达成行动的一致。

对于拜占庭问题来说，假如节点总数为 N，叛变将军数为 F，则当 $$ N ge 3F+1 $$ 时，问题才有解，即 Byzantine Fault Tolerant (BFT) 算法。

例如，N=3，F=1 时。

提案人不是叛变者，提案人发送一个提案出来，叛变者可以宣称收到的是相反的命令。则对于第三个人（忠诚者）收到两个相反的消息，无法判断谁是叛变者，则系统无法达到一致。

提案人是叛变者，发送两个相反的提案分别给另外两人，另外两人都收到两个相反的消息，无法判断究竟谁是叛变者，则系统无法达到一致。

更一般的，当提案人不是叛变者，提案人提出提案信息 1，则对于合作者来看，系统中会有 N-F 份确定的信息 1，和 F 份不确定的信息（假设叛变者会尽量干扰一致的达成），$$ N−F gt F $$，即 $$N gt 2F$$ 情况下才能达成一致。

问题复杂度分析

假设11位拜占庭将军去打仗，他们各自根据敌情做出行动计划，然后把行动计划广播给其他将军，然后投票取多数的原则决定最终行动决策。

这11位将军中有9位忠诚的将军, 5位判断进攻, 4位判断撤退, 还有2个叛徒恶意破坏状态一致性,他们跟5位判断进攻的将军说, 我们支持进攻, 那么这5位将军统计发现7位支持进攻, 4位支持撤退, 将发动进攻. 又跟4位撤退的将军说, 我们支持撤退, 撤退的将军一统计, 5票进攻, 6票撤退, 立马撤退。

叛徒发送前后不一致的进攻提议，导致拜占庭问题非常复杂。

中本聪的解决方案

区块链中通过引入『工作量证明机制』来提升做叛徒的成本，在工作量证明下，只有第一个完成证明的节点才能广播区块，大家都别忙着发起消息，都来做个题，看谁最聪明，谁就有资格第一个发起消息。

通过工作量证明就增加了发送信息的成本，降低节点发送消息的速率，这样就以保证在一个时间只有一个节点或是很少的节点进行广播，同时在广播时会附上自己的签名，由于签名是不可伪造的，所以就保证了消息来源的可追溯性。

这个过程就像一位将军A在向其他的将军（B、C、D…）发起一个进攻提议一样，将军B、C、D…看到将军A签过名的进攻提议书，如果是诚实的将军就会立刻同意进攻提议，而不会发起自己新的进攻提议。

这就是比特币网络中是单个区块达成共识的方法。

假设攻下一个城堡需要多次的进攻，每次进攻的提议必须基于之前最多次数的胜利进攻下提出的，这样约定之后，将军A在收到进攻提议时，就会检查一下这个提议是不是基于最多的胜利提出的，如果不是（基于最多的胜利）将军A就不会同意这样的提议，如果是的，将军A就会把这次提议记下来。这就是比特币网络最长链选择机制。

如果不同的将军先后解出了题，各自先后向这个网络发布消息，于是各个节点都会收到来自不同节点发起的进攻或者不进攻的消息，那怎么办的？只有时间最早的发起者才是有效的。中本聪巧妙的设计了一个时间戳的东西，为每个将军在解好题的时间（出块时间）盖上时间印章。

将军们那又凭什么要一起做工作量证明呢？

中本聪也完全可以设置一个奖励机制，比特币的奖励机制是每打包一个块，奖励一定数量的比特币，这样将军们就会尽最大努力维护系统的稳定性。

伟大的创新往往是站在前人的肩膀上，中本聪就是各种前沿技术的整合者，古老的疑难杂症在这种整合创新下，就变得不再是问题了。

工作量证明机制也造成了大量的电力浪费，只是这种浪费在巨大的革新面前还是值得的。

注： FLP impossibility

FLP Impossibility（FLP不可能性）是分布式领域中一个非常著名的结果，该结果在专业领域被称为“定理”，其地位之高可见一斑。该定理的论文是由Fischer, Lynch and Patterson三位作者于1985年发表,之后该论文毫无疑问得获得了Dijkstra奖。

FLP给出了一个令人吃惊的结论：在异步通信场景，即使只有一个进程失败，也没有任何算法能保证非失败进程达到一致性！

因为同步通信中的一致性被证明是可以达到的，因此在之前一直有人尝试各种算法解决以异步环境的一致性问题，有个FLP的结果，这样的尝试终于有了答案。