拜占庭问题（Byzantine Problem）更为广泛，讨论的是允许存在少数节点作恶（消息可能被伪造）场景下的一致性达成问题。拜占庭容错（Byzantine Fault Tolerant，BFT）算法讨论的是在拜占庭情况下对系统如何达成共识。

1.两将军问题

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

2.拜占庭问题

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

论文中指出，对于拜占庭问题来说，假如节点总数为N，叛变将军数为F，则当N≥3F+1时，问题才有解，由BFT算法进行保证。

例如，N=3，F=1时。

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

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

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

当提案人是叛变者，会尽量发送相反的提案给N-F个合作者，从收到1的合作者看来，系统中会存在（N-F）/2个信息 1，以及（N-F）/2个信息0；从收到0的合作者看来，系统中会存在（N-F）/2个信息0，以及（N-F）/2个信息1；另外存在F-1个不确定的信 息。合作者要想达成一致，必须进一步对所获得的消息进行判定，询问其他人某个被怀疑对象的消息值，并通过取多数来作为被怀疑者的信息值。这个过程可以进一 步递归下去。

Leslie Lamport等人在论文《Reaching agreement in the presence of faults》中证明，当叛变者不超过1/3时，存在有效的拜占庭容错算法（最坏需要F+1轮交互）。反之，如果叛变者过多，超过1/3，则无法保证一定 能达到一致结果。

那么，当存在多于1/3的叛变者时，有没有可能存在解决方案呢？

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

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

3.拜占庭容错算法

拜占庭容错算法（Byzantine Fault Tolerant，BFT）是面向拜占庭问题的容错算法，解决的是在网络通信可靠但节点可能故障情况下如何达成共识。拜占庭容错算法最早的讨论在1980 年Leslie Lamport等人发表的论文《Polynomial Algorithms for Byzantine Agreement》，之后出现了大量的改进工作。长期以来，拜占庭问题的解决方案都存在复杂度过高的问题，直到PBFT算法的提出。

1999年，Castro和Liskov于论文《Practical Byzantine Fault Tolerance and Proactive Recovery》中提出的Practical Byzantine Fault Tolerant（PBFT）算法，基于前人工作进行了优化，首次将拜占庭容错算法复杂度从指数级降低到了多项式级，目前已得到广泛应用。其可以在失效节 点不超过总数1/3的情况下同时保证Safety和Liveness。

PBFT算法采用密码学相关技术（RSA签名算法、消息验证编码和摘要）确保消息传递过程无法被篡改和破坏。

算法的基本过程如下：

·首先通过轮换或随机算法选出某个节点为主节点，此后只要主节点不切换，则称为一个视图（View）；

·在某个视图中，客户端将请求<REQUEST，operation，timestamp，client>发送给主节点，主节点负责广播请求到所有其他副本节点；

·所有节点处理完成请求，将处理结果<REPLY，view，timestamp，client，id_node，response>返回给客户端。客户端检查是否收到了至少f+1个来自不同节点的相同结果，作为最终结果。

主节点广播过程包括三个阶段的处理：预准备（pre-prepare）阶段、准备（prepare）阶段和提交（commit）阶段。预准备和准备阶段确保在同一个视图内请求发送的顺序正确；准备和提交阶段则确保在不同视图之间的确认请求是保序的：

·预准备阶段： 主节点为从客户端收到的请求分配提案编号，然后发出预准备消息<<PRE-PREPARE，view，n，digest>，message>给各副本节点，其中message是客户端的请求消息，digest是消息的摘要；

·准备阶段： 副本节点收到预准备消息后，检查消息合法，如检查通过则向其他节点发送准备消息<PREPARE，view，n，digest，id>，带上 自己的id信息，同时接收来自其他节点的准备消息。收到准备消息的节点对消息同样进行合法性检查。验证通过则把这个准备消息写入消息日志中。集齐至少2 f+1个验证过的消息才进入准备状态；

·提交阶段： 广播commit消息，告诉其他节点某个提案n在视图v里已经处于准备状态。如果集齐至少2 f+1个验证过的commit消息，则说明提案通过。

具体实现上还包括视图切换、checkpoint机制等，读者可自行参考论文内容，在此不再赘述。

4.新的解决思路

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

比特币的区块链网络在设计时提出了创新的PoW（Proof of Work）概率算法思路，针对这两个环节进行了改进。

首先，限制一段时间内整个网络中出现提案的个数（通过增加提案成本）；其次是放宽对最终一致性确认的需求，约定好大家都 确认并沿着已知最长的链进行拓展。系统的最终确认是概率意义上的存在。这样，即便有人试图恶意破坏，也会付出相应的经济代价（超过整体系统一半的计算 力）。

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

来源：我是码农，转载请保留出处和链接！

本文链接：http://www.54manong.com/?id=967

• 8.5　贡献代码2018-09-29 16:58
• 未来互联网金融环境基于区块链技术的蜕变2018-09-25 15:47
• 原版引言2018-09-12 15:20
• 1.6　知识点导图2018-08-25 22:37