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

中国将军问题

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

拜占庭问题

又叫拜占庭将军(Byzantine Generals Problem)问题,是 Leslie Lamport 1982 年提出用来解释一致性问题的一个虚构模型。拜占庭是古代东罗马帝国的首都,由于地域宽广,守卫边境的多个将军(系统中的多个节点)需要通过信使来传递消息,达成某些一致的决定。但由于将军中可能存在叛徒(系统中节点出错),这些叛徒将努力向不同的将军发送不同的消 息,试图会干扰一致性的达成。

拜占庭问题

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

对于拜占庭问题来说,假如节点总数为 N,叛变将军数为 F,则当时,问题才有解,即

Byzantine Fault Tolerant (BFT) 算法。例如,N=3,F=1 时。

提案人不是叛变者,提案人发送一个提案出来,叛变者可以宣称收到的是相反的命令。则对

于第三个人(忠诚者)收到两个相反的消息,无法判断谁是叛变者,则系统无法达到一致。

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

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

当提案人是叛变者,会尽量发送相反的提案给个合作者,从收到 1 的合作者看来, 系统中会存在   个信息 1,以及个信息 0;从收到 0 的合作者看来,系统中会存在信息 0,以及个信息 1;

另外存在 F?1 个不确定的信息。合作者要想达成一致,必须进一步的对所获得的消息进行判定,询问其他人某个被怀疑对象的消息值,并通过取多数来作为被怀疑者的信息值。这个过程可以进一步递归下去。

Leslie Lamport 证明,当叛变者不超过时,存在有效的算法,不论叛变者如何折腾,忠诚的将军们总能达成一致的结果。如果叛变者过多,则无法保证一定能达到一致性。

能确保达成一致的拜占庭系统节点数至少为4,允许出现1个坏的节点。

Byzantine Fault Tolerant 算法

面向拜占庭问题的容错算法,解决的是网络通信可靠,但节点可能故障情况下的一致性达成。

最早由 Castro 和 Liskov 在 1999 年提出的 Practical Byzantine Fault Tolerant(PBFT)是第一个得到广泛应用的 BFT 算法。只要系统中有的节点是正常工作的,则可以保证一致 性。

PBFT 算法包括三个阶段来达成共识:Pre-Prepare、Prepare 和 Commit。

Byzantine Fault Tolerant 算法

新的解决思路

拜占庭问题之所以难解,在于任何时候系统中都可能存在多个提案(提案成本为 0),并且要完成最终的一致性确认过程十分困难,容易受干扰。但是一旦确认,即为最终确认。

比特币的区块链网络在设计时提出了创新的 PoW(Proof of Work) 算法思路。一个是限制一段时间内整个网络中出现提案的个数,另外一个是放宽对最终一致性确认的需求,约定好大家都确认并沿着已知最长的链进行拓宽。系统的最终确认是概率意义上的存在。这样,即便有人试图恶意破坏,也会付出很大的经济代价(付出超过系统一半的算力)。

后来的各种 PoX 系列算法,也都是沿着这个思路进行改进,采用经济上的惩罚来制约破坏这者。

玖壹区块链声明

加微信:469649885区块链培训教程
还可免费获取区块链培训班试学名额

分享:

扫一扫在手机阅读、分享本文

区块链评论

玖壹区块链培训

玖壹区块链培训学院简称(玖壹学院http://www.91xiubbs.com/)提供区块链技术培训资料、区块链开发培训视频教程等下载,不过网上自学区块链技术课程必然存在一些缺陷:遇到问题易卡壳、学习周期漫长、无针对性等。区块链培训机构现场面对面的讲授区块链培训课程可以让您和团队在最短时间内掌握正确、系统、高效的区块链实战技术。