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

零度财经

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

中国将军问题

拜占庭将军问题之前,就已经存在中国将军问题:两个将军要通过信使来达成进攻还是撤退的约定,但信使可能迷路或被敌军阻拦(消息丢失或伪造),如何达成一致。根据 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的结果,这样的尝试终于有了答案。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180610G1LC2P00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券