共识算法——不想当将军的数学家不是好程序员

01 解决拜占庭将军问题的 PBFT 算法

拜占庭将军问题是图灵奖得主 Leslie Lamport 于 1982 年提出的一种信息交互的构想——古罗马战争时，拜占庭军队内所有将军和副官必须达成一致，根据机会大小决定进攻还是防守。但在军队内可能有叛徒和敌军间谍左右将军们的决定，导致在进行决策时，结果并不代表大多数人的真实意见。此时，在已知有成员叛变的情况下，其余忠诚的将军如何不受叛徒影响，达成正确且一致的共识，拜占庭将军问题就此形成。

随着密码学的发展，1999 年另一位图灵奖得主 Barbara Liskov 提出了实际生产可用的 PBFT 算法。

至此在计算机领域便诞生了一项联系战场将军、数学家、程序员三种不同角色的“跨界黑科技”——共识算法。

我们先用一个比较简单的方式来理解 PBFT 算法。

假设在战场上，大哥是一位将军，他有小 1、小 2、小 3 这三位副官。律法规定，只有所有人意见一致，军队才能行动。假定这次战役选择“打”的赢面更大。这四个人中包括将军本人，有一个是敌军的特务，目标是捣乱让军队无法达成一致开始战斗。

这种状况下，大家发明了一种方法来达成一致。

情况一

大哥是忠臣，副官小 3 是叛徒

大哥分别给小 1、小 2、小 3 发密函，上面写着“打”；然后小 1、小 2、小 3 做同样的动作也给所有人发密函，以此类推。其中的叛徒可能给其他人错误的答案，也就是“不打”。一番往复后，把所有人得到的密函摊在一起，可能是这个样子，不打占比很小：

情况二 大哥是叛徒

倘若大哥是叛徒，那么他的任务就是不给大家发送一致的消息，他可能会给其余三人中两个“打”、一个“不打”；或者两个“不打”和一个“打”。那么摊开密函后，可能是以下两种状况：

或者

密函摊开，一目了然，每个人都享受了一次当“大哥”的权利给其他人发令，所以其中的不和谐因素一定是叛徒提供的，轮流“当大哥”（或称换主）后，我们发现，无论间谍是谁，最后密函摊开结果最多的永远是“打”，也就是正确忠诚的决策。这种多次交互后的“少数服从多数”，就是 PBFT 算法的基本工作原理。

换句话说，PBFT 算法是一种主（将军）备（副官）模型，存在一个主节点和多个备份节点（大哥和他的 123 们）。主节点将客户端请求（打）广播发送给其他备份节点，然后经过后续几轮交互，最终所有忠诚节点达成一致。当主节点异常时，其他备份节点检测到超时并发起换主操作，选出一个新的主节点，然后继续提供服务。

02 蚂蚁区块链做了啥？

OK，在理解这个原理的基础上，我们把模型放到数据世界中来。

传统的 PBFT 算法有什么短板呢？

不断传递“密函”的过程耗时费力，要真是只有 4 个人参与交流还好，一旦将军和副官多起来，这个方法就变得不实用了：既要保证环境的稳定性，不要把密函搞丢搞乱，又要保证这个过程迅速，每次出征得带几万个飞毛腿去负责传“密函”，另外等密函结果摊开，说不定仗都打完了。

换句话讲，区块链技术要面对的是数以千亿计的数据，然而 PBFT 算法存在主节点的网络开销过大、对网络稳定性要求较高等问题。且 PBFT 算法复杂度比较高，操作成本大，所以很多区块链项目都在努力优化这个算法，降低复杂度，让传来传去的“密函”不要这么麻烦。

蚂蚁区块链最初同样基于 PBFT 算法实现，但随着业务的扩展、集群规模的增大、网络环境的复杂，PBFT 算法的缺点逐渐暴露出来。为了解决这些新问题，蚂蚁区块链团队调研了业界最新的技术，包括同步、半同步、异步拜占庭算法，并结合各个算法的特点，选择了半同步拜占庭算法用于中小规模网络场景，异步拜占庭算法用于大规模网络场景。

半同步拜占庭算法非常典型的就是上面讨论的 PBFT 算法，传来传去的“密函”放在中小规模的网络场景里，还是扛得住的。

那用于大规模网络场景的异同步拜占庭算法厉害在哪呢？

首先它对网络延迟没有依赖，哪怕网络抖动很严重也能正常工作。一个很典型的例子是 HoneyBadgerBFT（也是蚂蚁区块链优化共识算法时的参考对象）。

在 HoneyBadgerBFT 中，所有节点都是对等的，没有主备之分，就是没有了将军大哥，换主这个过程也就不需要了。接下来只需要在收到客户端的请求后，每个节点各自对数据进行纠删码编码。没错！就是这个神奇的纠删码！让算法的容量迅速变大。

通过纠删码这个黑科技，能把 1GB 的共识数据压到 1MB 以内；让“密函”传递这个过程迅速压缩，原本需要很长时间你来我往，有了“纠删码”就可以快进 1000 倍，嗖嗖嗖瞬间完成任务。每个节点的出口带宽需求也就变得非常小，整个系统可以支持大规模的集群部署。

其次，为了实现异步网络中消息最终到达的理论前提，蚂蚁区块链采用独有的专利技术，对共识消息进行存储优化，对算法设计和实现的各个方面进行优化，确保了系统支持大规模节点和高吞吐量。

最后，我们还专门引入了 Jepsen 分布式测试框架，增加了严格的测试场景，如网络分区、节点重启、拜占庭错误注入等。蚂蚁区块链通过了全部的测试场景，确保了系统在任何异常场景下安全可靠的工作。

本文转载自蚂蚁区块链公众号。

原文链接：https://mp.weixin.qq.com/s/uE_3NhH0mlEejJoUCfEchQ