绝大多数区块链都被设计为去中心化的、由分布式计算机节点网络维护的数字账本。因此，区块链技术允许创建去信任的经济系统，即，可以在不需要中介的情况下执行透明和可靠的金融交易。

就像大多数分布式计算系统一样，加密货币网络的参与者需要定期就区块链的当前状态达成一致，这就是我们所说的达成共识。然而，以安全有效的方式就分布式网络达成共识绝非易事。

那么，如果某些节点可能出现故障或不诚实行为，分布式计算机节点网络如何就决策达成一致呢？这是所谓拜占庭将军问题，由此产生了拜占庭容错的概念。

拜占庭将军问题

问题假设拜占庭邻邦的将军们要攻打拜占庭，每个将军都有自己的军队，并且每个军队都位于拜占庭周围的不同位置。将军们需要就进攻或撤退达成一致。进攻或撤退都无所谓，只要所有将领达成共识就好——即一致同意一个共同的决定，以便协调执行。 因此，我们需要考虑以下要求：

• 每个将军必须决定：进攻还是撤退
• 决定一经作出，不得更改
• 所有将军必须就同一决定达成一致，并以同步方式执行

由于每位将军都只能通过信使与另一位将军进行沟通，因此，消息很可能会以某种方式延迟、破坏或丢失。

此外，即使消息传递成功，别的将军可能会选择恶意行事，并发送欺诈性消息以混淆其他将军，从而导致兵败。

如果我们将困境应用到区块链的上下文中，每个将军代表一个网络节点，节点需要就系统的当前状态达成共识。换句话说，分布式网络中的大多数参与者必须同意并执行相同的操作。

我们使用更加 formal 的语言来定义这一问题：

给定一个包含 \(n\) 个节点的系统，其中 \(t\) 个是不诚实的，并假设所有节点之间只有点对点通道。 每当一个节点 A 尝试广播一个值 \(x\) 时，允许其他节点相互讨论并验证 A 广播的一致性，并最终确定一个共同的值 \(y\)。拜占庭容错系统遵循以下原则：

• 在 A 是诚实的情况下，所有诚实的节点都同意 \(x\) 的值
• 在所有情况下，所有诚实的节点都同意相同的值 \(y\)

拜占庭容错只关心广播一致性，即当一个节点向其他节点广播相同的值时，它们都接收到完全相同的值；而在广播不一致的情况下，其他节点同意一个共同的值。这种容错不能验证值本身的正确性。

拜占庭容错

解决方案要求超过 \(\frac{2}{3}\) 或者一半的节点都同意一个相同的消息，也就是大多数原则。它考虑了可能伪造消息的场景，只要不忠的将军的数量少于将军的三分之一，它就会是拜占庭容错的。

但是，假设我们有一个叛国的指挥官A，和两个中尉B和C：当A告诉B进攻，却让C撤退，那么当B和C互相确认时，B和C都不能找出谁是叛徒，因为另一个中尉可能伪造了据称来自 A 的消息。可以证明，如果 \(n\) 是将军总数，\(t\) 是叛徒的数量，那么只有当 \(n > 3t\) 并且通信同步时，才能够实现拜占庭容错。51% 攻击就是利用的这个原理。

此外，解决方案需要不可伪造的消息签名（通常是非堆成公钥密码体制）。事实上，即使是 CRC 也是一种高效且有效的拜占庭容错机制。

PBFT

拜占庭将军问题最早是由 Leslie Lamport 在The Byzantine Generals Problem 中提出的。若将军总数 \(n>3f\) ，背叛者为 \(f\) 或者更少时，忠诚的将军可以达成命令上的一致，即 \(3f+1\leq n\) 。算法复杂度为 \(O(n^{f+1})\)。

Miguel Castro 和 Barbara Liskov 的 Practical Byzantine Fault Tolerance 提出 PBFT 算法，该算法将复杂度降低到了 \(O(n^2)\)。

我们首先定义几个量：

• v：view，也就是当前主节点编号
• n：客户端对主节点请求的编号
• d：消息内容摘要
• m：消息
• i：节点编号
• checkpoint：某节点正在处理的请求的编号
• stable checkpoint：当前所有节点达成共识的消息的最大编号，也称 low level
• high level：low level + L，L 是一个设定的值

PBFT 主要有以下几步：

• 客户端发送请求给主节点
• pre-prepare：主节点广播请求 ((pre-prepare,v,n,d),m) 给其它节点，其它节点收到请求后有两种选择：
  • 拒绝：如果 v 和 n 之前出现过，但 d 和 m 却不同，节点就会拒绝。因为主节点不会发送这样的消息。或者，这个消息的编号不在 low level 和 high level 之间，则也直接拒绝。
  • 接受：其余情况，节点执行下一步
• prepare：节点向其它节点发送 (prepare,v,n,d,i) 同时接收其它节点发送的消息，当收到 \(2f\) 个不同消息（不包括自己）后，停止发送。如果未能收到足够的消息，则验证失败。
• commit：节点向其它节点发送 (commit,v,n,d,i) 同时接收其它节点发送的消息，当收到 \(2f+1\) 个消息（包括自己）后，停止发送，达成共识，执行请求。如果未能收到足够的消息，则验证失败。

如果主节点挂了或者不受信任了，则需要更换主节点。我们先定义几个量：

• v：上一个 view 的编号
• n：stable checkpoint 编号
• C：\(2f+1\) 个节点的 checkpoint 集合
• P：编号大于 \(n\) 且完成 prepare 步骤的消息集合
• V：新的主节点接收到的 view 为 \(v+1\) 的 view-change 消息集合
• O：pre-prepare 消息集合

此时会执行以下步骤：

• view-change：某节点发现主节点挂了，于是向其它节点广播 (view-change,v+1,n,C,P,i)同时接收其它节点发送的消息，当收到 \(2f\) 个不同消息（不包括自己）后，停止发送。如果未能收到足够的消息，则验证失败。
• new-view：向其它节点广播 (new-view,v+1,V,O)同时接收其它节点发送的消息，验证 O 是否正确。
• v=v+1，处理 O 中的消息

综上，PBFT 其实是这么一个过程：将军向士兵发送命令时，当士兵认为将军的命令是有问题时，士兵会拒绝执行。就算士兵认为将军的命令是对的，士兵还会问下其它士兵将军的命令是否是对的，只有大多数士兵都认为将军的命令是对的时候，士兵才会去执行命令。如果将军挂了，或者大多数士兵都认为将军不诚实时，士兵们也会重新选择将军。

reference

1. Lamport L, Shostak R, Pease M. The Byzantine generals problem[M]//Concurrency: the Works of Leslie Lamport. 2019: 203-226.
2. Castro M, Liskov B. Practical byzantine fault tolerance[C]//OSDI. 1999, 99(1999): 173-186.
3. Byzantine Fault Tolerance Explained. academy.binance.com,Dec. 2018, https://academy.binance.com/en/articles/byzantine-fault-tolerance-explained.