> For the complete documentation index, see [llms.txt](https://yeasy.gitbook.io/blockchain_guide/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://yeasy.gitbook.io/blockchain_guide/04_distributed_system/bft.md). # 拜占庭问题与算法 拜占庭问题（Byzantine Problem）又叫拜占庭将军（Byzantine Generals Problem）问题，讨论的是在少数节点有可能作恶（消息可能被伪造）的场景下，如何达成共识问题。拜占庭容错（Byzantine Fault Tolerant，BFT）讨论的是容忍拜占庭错误的共识算法。 ## 两将军问题 拜占庭问题之前，早在 1975 年，学术界就已经开始两将军问题的讨论（《Some constraints and tradeoffs in the design of network communications》）：两个将军要通过信使来达成进攻还是撤退的约定，但信使可能迷路或被敌军阻拦（消息丢失），如何达成一致？这是不可靠通信下双方无法获得共同知识的典型模型；它与 FLP 不可能原理同属共识边界问题，但 FLP 的正式结论针对的是完全异步、可靠消息且允许一个崩溃进程的确定性共识模型。 ## 拜占庭问题 拜占庭问题最早由 Leslie Lamport 等学者于 1982 年在论文《The Byzantine Generals Problem》中正式提出，是用来解释异步系统中共识问题的一个虚构模型。拜占庭是古代东罗马帝国的首都，由于地域宽广，假设其守卫边境的多个将军（系统中的多个节点）需要通过信使来传递消息，达成某些一致决定。但由于将军中可能存在叛徒（系统中节点出错），这些叛徒将向不同的将军发送不同的消息，试图干扰共识的达成。 拜占庭问题即讨论在此情况下，如何让忠诚的将军们能达成行动的一致。 一般分布式场景下，拜占庭需求并不多见，但在特定场景下会有较大意义。例如容易匿名参与的系统（如比特币），或是出现欺诈可能造成巨大损失的情况（金融系统）。 ## 问题的解决 论文中指出，对于拜占庭问题来说，假如节点总数为 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 个不确定的信息。合作者要想达成一致，必须进一步的对所获得的消息进行判定，询问其他人某个被怀疑对象的消息值，并通过取多数来作为被怀疑者的信息值。这个过程可以进一步递归下去。 1980 年，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 个坏的节点。 ## 拜占庭容错算法 拜占庭容错算法（Byzantine Fault Tolerant）是面向拜占庭问题的容错算法，解决的是在网络通信可靠，但节点可能故障和作恶情况下如何达成共识。 拜占庭容错算法最早的讨论可以追溯到 Leslie Lamport 等人 1982 年 发表的论文《The Byzantine Generals Problem》，之后出现了大量的改进工作，代表性成果包括《Optimal Asynchronous Byzantine Agreement》（1992 年）、《Fully Polynomial Byzantine Agreement for n>3t Processors in t+1 Rounds》（1998 年）等。长期以来，拜占庭问题的解决方案都存在运行过慢，或复杂度过高的问题，直到“实用拜占庭容错算法”（Practical Byzantine Fault Tolerance，PBFT） 算法的提出。 1999 年，PBFT 算法由 Miguel Castro 和 Barbara Liskov 于论文《Practical Byzantine Fault Tolerance》中提出。该算法基于前人工作（特别是 Paxos 相关算法，因此也被称为 Byzantine Paxos）进行了优化，首次将拜占庭容错算法复杂度从指数级降低到了多项式（平方）级，目前已得到广泛应用。PBFT 在副本数 n >= 3f + 1、拜占庭故障副本数不超过 f 的条件下保证 Safety；Liveness 还需要网络最终满足有界延迟、视图切换能够选出非故障主节点等部分同步条件。 PBFT 算法采用密码学相关技术（RSA 签名算法、消息验证编码和摘要）确保消息传递过程无法被篡改和破坏。 算法的基本过程如下： * 首先，通过轮换或随机算法选出某个节点为主节点，此后只要主节点不切换，则称为一个视图（View）。 * 在某个视图中，客户端将请求 `` 发送给主节点（如果客户端发给从节点，从节点可以转发给主节点），主节点负责广播请求到所有其它从节点并完成共识。 * 所有节点处理完成请求，将处理结果 `` 返回给客户端。客户端检查是否收到了至少 f+1 个来自不同节点的相同结果，作为最终结果。 主节点广播过程包括三个阶段的处理：预准备（Pre-Prepare）、准备（Prepare）和提交（Commit）。预准备和准备阶段确保在同一个视图内请求发送的顺序正确；准备和提交阶段则确保在不同视图之间的确认请求是保序的。 * 预准备阶段：主节点为从客户端收到的请求分配提案编号，然后发出预准备消息 `<,message>` 给各从节点，主节点需要对预准备消息进行签名。其中 n 是主节点为这个请求分配的序号，message 是客户端的请求消息，digest 是消息的摘要。这一步的目的是为请求分配序号并通知其他节点，因此可以不包括原始的请求消息，可以通过其他方式将请求同步到从节点。 * 准备阶段：从节点收到预准备消息后，检查消息（包括核对签名、视图、编号）。如消息合法，则向其它节点发送准备消息 ``，带上自己的 id 信息，并添加签名。收到准备消息的节点同样对消息进行合法性检查。节点拥有合法的预准备消息，并集齐来自不同副本的 2f 个匹配准备消息后，等价于已有 2f+1 个副本对该视图、序号和摘要达成准备状态。这一步是为了确认大多数节点已经对序号达成共识，本节点已经准备好进行提交了。 * 提交阶段：广播 commit 消息 `` 并添加自己签名，告诉其它节点某个编号为 n 的提案在视图 v 里已经处于提交状态。如果集齐至少 2f+1 个来自不同副本且验证通过的 commit 消息，则说明本节点可以执行该请求。 PBFT 算法和 Raft 算法都通过领导者简化正常路径，但故障模型不同。Raft 只处理崩溃故障；PBFT 不假设主节点一定可靠，因此增加了从节点之间的准备、提交和视图切换交互。当主节点作恶、停顿或网络在足够长时间后仍无法推进时，副本通过视图切换选出新的主节点以恢复 Liveness。 具体实现上还包括 checkpoint（同步节点状态和清理本地日志数据）、视图切换（重新选举主节点）等机制，读者可自行参考论文内容，在此不再赘述。 拜占庭容错类的算法因为要考虑最恶意的存在“捣乱”者的情况，在大规模场景下共识性能往往会受到影响。 ## 新的解决思路 拜占庭问题之所以难解，在于任何时候系统中都可能存在多个提案（因为提案成本很低），并且在大规模场景下要完成最终确认的过程容易受干扰，难以达成共识。 2014 年，斯坦福大学的 Christopher Copeland 和 Hongxia Zhong 在论文《Tangaroa: a byzantine fault tolerant raft》中提出在 Raft 算法基础上借鉴 PBFT 算法的一些特性（包括签名、恶意领导探测、选举校验等）来实现拜占庭容错性，兼顾可实现性和鲁棒性。该论文也启发了 Kadena 等项目的出现，实现更好性能的拜占庭算法。 2017 年，MIT 计算机科学与人工智能实验室（CSAIL）的 Yossi Gilad 和 Silvio Micali 等人在论文《Algorand: Scaling Byzantine Agreements for Cryptocurrencies》中针对 PBFT 算法在很多节点情况下性能不佳的问题，提出先选出少量记账节点，然后再利用可验证随机函数（Verifiable Random Function，VRF）来随机选取领导节点，避免全网直接做共识，将拜占庭算法扩展到了支持较大规模的应用场景，同时保持较好的性能（1000+ tps）。 此外，康奈尔大学的 Rafael Pass 和 Elaine Shi 在论文《The Sleepy Model of Consensus》中探讨了在动态场景（大量节点离线情况）下如何保障共识的安全性，提出的 Sleepy Consensus 算法可以在活跃诚实节点达到一半以上时确保完成拜占庭共识。 2018 年，清华大学的 Chenxing Li 等在论文《Scaling Nakamoto Consensus to Thousands of Transactions per Second》中提出了 Conflux 共识协议。该协议在 GHOST 算法基础上改善了安全性，面向公有区块链场景，理论上能达到 6000+ tps。 2019 年，康奈尔大学和 VMWare 研究院的 Maofan Yin 等在论文《HotStuff: BFT Consensus with Linearity and Responsiveness》中对 PBFT 算法进行了改进：利用主节点来简化通信量，将通信复杂度从 PBFT 的 O(n²) 降低到 O(n)，同时将视图切换与共识操作进行统一。值得一提的是，Facebook Libra 白皮书中采用了该成果；Libra 后更名为 Diem，Diem 项目已于 2022 年出售核心资产并停止推进。 比特币网络在设计时使用了 PoW（Proof of Work）的概率型算法思路，从如下两个角度解决大规模场景下的拜占庭容错问题。 首先，限制一段时间内整个网络中出现提案的个数（通过工作量证明来增加提案成本）；其次是丢掉最终确认的约束，约定好始终沿着已知最长的链进行拓展。共识的最终确认是概率意义上的存在。这样，即便有人试图恶意破坏，也会付出相应的经济代价（超过整体系统一半的工作量）。后来的各种 PoX 系列算法，也都是沿着这个思路进行改进，采用经济博弈来制约攻击者。 ## Tendermint BFT Tendermint（由 Jae Kwon 于 2014 年提出）是最早将 BFT 共识应用于区块链的实用方案之一。它借鉴了 PBFT 的核心思想，但针对区块链场景进行了重要优化： * **确定性最终性**：区块一旦被提交即为最终确认，无需等待多个区块确认，这与中本聪共识的概率性最终性形成鲜明对比。 * **基于轮次的提议**：验证者按照确定性轮转方式提议区块，简化了领导者选举。 * **应用区块链接口（ABCI）**：将共识引擎与应用逻辑解耦，使得开发者可以用任意编程语言构建区块链应用。 * **容错能力**：容忍不超过 1/3 的拜占庭节点，通信复杂度为 O(n²)。 Tendermint 是 Cosmos 生态的核心共识引擎（现已更名为 CometBFT），支撑了数百条应用链的运行。 ## 共识算法对比 | 算法 | 容错类型 | 容错节点比例 | 通信复杂度 | 最终性 | 典型吞吐量 | 代表应用 | | -------------- | ----- | ------ | ------ | ----- | ---------------- | ------------ | | Paxos/Raft | 崩溃容错 | < 1/2 | O(n) | 确定性 | 10,000+ tps | etcd, Fabric | | PBFT | 拜占庭容错 | < 1/3 | O(n²) | 确定性 | 1,000-3,000 tps | Hyperledger | | Tendermint | 拜占庭容错 | < 1/3 | O(n²) | 确定性 | 1,000-10,000 tps | Cosmos | | HotStuff | 拜占庭容错 | < 1/3 | O(n) | 确定性 | 3,000-10,000 tps | Diem/Aptos | | Nakamoto (PoW) | 拜占庭容错 | < 1/2 | O(1)广播 | 概率性 | 7 tps | Bitcoin | | Gasper (PoS) | 拜占庭容错 | < 1/3 | O(n) | 概率→确定 | 15-30 tps | Ethereum | *注：吞吐量数据为典型场景下的参考值，实际性能受网络规模、交易复杂度等因素影响。* 另外，由于要处理的场景比较苛刻，BFT 类算法的吞吐量往往不高。除了可以放宽约束外（例如通常情况下信任主节点，出现问题再回滚），还可以引入多个互不影响的主节点进行并行处理（如 Narwhal+Tusk/Bullshark 等 DAG-based BFT 方案）。