[科普中国]-改进型实用拜占庭容错

改进型实用拜占庭容错的共识机制是少数服从多数，根据信息在分布式网络中节点间互相交换后各节点列出所有得到的信息，一个节点代表一票，选择大多数的结果作为解决办法。PBET将容错量控制在全部节点数的1/3，即如只要有超过2/3的正常节点，整个系统便可正常运作。

相关介绍1 拜占庭将军问题
Byzantine Generals Problem/BGP
拜占庭将军问题是指“在存在消息丢失的不可靠信道上试图通过消息传递的方式达到一致性是不可能的”。因此在系统中存在除了消息延迟或不可送达的故障以外的错误，包括消息被篡改、节点不按照协议进行处理等，将会潜在地会对系统造成针对性的破坏。1
2 授权拜占庭容错算法
Delegated Byzantine Fault Tolerance/dBFT
dBFT，是基于持有权益比例来选出专门的记账人（记账节点），然后记账人之间通过拜占庭容错算法（即少数服从多数的投票机制）来达成共识，决定动态参与节点。dBFT可以容忍任何类型的错误，且专门的多个记账人使得每一个区块都有最终性、不会分叉。
3 联邦拜占庭协议
Federated Byzantine Agreement/FBA
联邦拜占庭协议的主要特性是去中心化和任意行为容错，通过分布式的方法，达到法定人数或者节点足够的群体能达成共识，每一个节点不需要依赖相同的参与者就能决定信任的对象来完成共识。

简介1 拜占庭容错背景

面对这些风险的时候，采用什么样的技术可以在成本与风险中取得平衡呢？入侵容忍体系就是这项技术中的核心。入侵容忍就是在这样的假设空间中实现它的价值：个人的公开行为在一定的概率下是可预知的，系统在一定的概率下能够正确完成基本的功能。一定的概率并不是指全部，所以，可以允许有错误，因此，入侵容忍还有对纠错理论的联想：即利用纠错码可以在一个错误百出、但有信道容量的信道中准确无误地传输数据，网络系统就这样在错误中“生存”下来的，这就是我们说的入侵容忍体系，它有两种实现方式：一是攻击响应的入侵容忍方法，它不需要重新设计系统，可通过高效的检测系统发现异常，利用资源配置系统调整系统资源，并对对错误进行修补（修补系统）；二是攻击遮蔽的入侵容忍方法，它需要重新设计整个系统，并通过冗余、容错技术，门槛密码学技术及“拜占庭容错问题”来实现拜占庭问题更为广泛，讨论的是允许存在少数节点作恶（消息可能被伪造）场景下的一致性达成问题。拜占庭算法讨论的是最坏情况下的保障。

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

2 拜占庭问题

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

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

例如，N=3，F=1 时

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

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

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

当提案人是叛变者，会尽量发送相反的提案给（N-F)个合作者，从收到 1 的合作者看来，系统中会存在（N-F)/2个信息 1，以及（N-F)/2个信息 0；从收到 0 的合作者看来，系统中会存在（N-F)/2个信息 0，以及（N-F)/2个信息

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

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

多于1/3的叛变者时有没有可能有解决方案呢？设想 f 个叛变者和 g 个忠诚者，叛变者故意使坏，可以给出错误的结果，也可以不响应。某个时候 f 个叛变者都不响应，则 g 个忠诚者取多数既能得到正确结果。当 f 个叛变者都给出一个恶意的提案，并且 g 个忠诚者中有 f 个离线时，剩下的 g - f 个忠诚者此时无法分别是否混入了叛变者，仍然要确保取多数能得到正确结果，因此，，即，所以系统整体规模要大于 3f。

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

3 Byzantine Fault Tolerant 算法

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

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

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

4 新的解决思路

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

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

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

本词条内容贡献者为:

李岳阳 - 副教授 - 江南大学