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

阅读数:3 2019 年 12 月 25 日 18:07

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

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

评论

发布