BFT 协议：PBFT 与 Tendermint

Lamport、Shostak 和 Pease 于 1982 年提出的拜占庭将军问题提出了这样一个问题：当部分参与者发送相互矛盾的消息时，分布式系统能否达成共识？这个问题以必须协调发动攻击、但其中可能有发送相互冲突命令的叛徒的拜占庭将军命名。如果一个系统在总数为 3f+1 的节点中，即使最多有 f 个恶意节点，仍能达成正确共识，那么它就是拜占庭容错（BFT）的。BFT 是要求在对抗性条件下保证安全性的区块链共识的黄金标准。

PBFT（Castro 和 Liskov，1999 年）是第一个实用的 BFT 协议，证明了 BFT 可以在真实系统中高效运行。PBFT 按视图（任期）运行，每个视图都有指定的主节点（领导者）。正常运行包含三个阶段：预准备（主节点广播客户端请求和序列号）、准备（副本广播带有序列号的一致意见）以及提交（副本广播提交确认）。副本收集到 2f+1 条匹配的提交消息后，就会执行请求。在少于 1/3 的副本为拜占庭节点的前提下，PBFT 能够提供安全性和活性。

PBFT 的主要限制是每个请求具有 O(n^2) 的消息复杂度：n 个副本中的每个副本都会在准备和提交阶段向所有其他副本发送消息。当 n=100 个副本时，每个请求大约会产生 10,000 条消息。这使 PBFT 不适合大型验证者集合。BFT 研究界用了二十年时间来改进这一点：BFT-SMART 降低了常数项，HotStuff 通过领导者中继模型实现了线性消息复杂度，而 Tendermint 则调整 PBFT 的思想以用于公有区块链。

当 PBFT 主节点被怀疑发生故障（超时）时，副本会触发视图更改。每个副本都会广播一条视图更改消息，其中包含自身状态（旧视图中已准备的值）。新主节点收集 2f+1 条视图更改消息，构造一条新视图消息，以证明状态转换与之前已提交的值保持一致，然后将其广播出去。视图更改代价高昂——需要 O(n^3) 条消息——曾是实际应用中的瓶颈。PBFT 的视图更改证书和 HotStuff 的流水线式设计等优化措施解决了这一问题。

Tendermint（2014 年由 Kwon 提出；2019 年在 Cosmos 中投入生产）针对公有区块链环境调整了 PBFT。Tendermint 的每个区块包含三个阶段：提议（领导者广播提议的区块）、预投票（验证者为提议投票）和预提交（验证者看到 2/3 的预投票后投票提交）。当验证者收集到 2/3 的预提交投票（即法定人数证书）时，区块就会提交。验证者按照由质押权益加权的轮询顺序轮流担任提议者。如果某一轮超时仍未提交，验证者会带着空投票进入下一轮。

Tendermint 提供强安全性：只要少于 1/3 的质押权益属于拜占庭节点，已提交的区块就是最终确定的，无法被回滚。这是同步最终性——提交后不会再出现分叉。活性要求网络是部分同步的：消息延迟有界后，协议就能继续推进，但不要求网络始终保持同步。活性与安全性之间的权衡是根本性的：Tendermint 牺牲活性（网络分区时可能停止）来保证安全性；而比特币等链则牺牲安全性（允许临时分叉）来保证活性。

Tendermint 的一个关键机制是投票锁定。当验证者在第 r 轮为某个区块发送预提交时，就会锁定在该区块上。在后续轮次中，已锁定的验证者只能为自己锁定的区块进行预投票（或者在收到该区块未被提交的证明后进行空投票）。这可以防止不同轮次之间出现相互矛盾的提交。只有当验证者在后续轮次收到另一个区块的多数票证明（2/3 的预投票），证明原区块未被提交时，才能解除锁定。

Cosmos 的区块链间通信（IBC）依赖 Tendermint 的即时最终性来进行跨链转账。Tendermint 轻客户端会跟踪验证者集合和最新提交（区块头加上 2/3 的预提交签名）。要验证来自链 A 的数据包，链 B 的 IBC 模块会验证法定人数证书——也就是链 A 的 2/3 验证者是否签署了相关区块头。因此，IBC 的安全性取决于 Tendermint 的 BFT 保证：源区块一经提交，跨链转账就会立即最终确定。

HotStuff（Yin 等人，2018 年；Facebook 的 LibraBFT/DiemBFT 的基础，如今也用于 Aptos 和 Sui）采用星型拓扑，使每个共识轮次的消息复杂度达到 O(n)：所有验证者向领导者发送投票，领导者将投票聚合为阈值签名（QC，即法定人数证书），然后广播 QC。HotStuff 使用三阶段链式设计，使安全性证明跨越连续三个 QC，从而支持流水线处理。线性复杂度使 HotStuff 适用于 100—300 个验证者，Aptos 和 Sui 就采用了这种部署方式。

企业区块链（Hyperledger Fabric、Besu、Quorum）在许可网络中使用 BFT 共识，因为这些网络中的验证者身份是已知的。Hyperledger Fabric 基于 Raft 的排序服务为受信任的联盟提供崩溃容错（而非拜占庭容错）。Fabric 计划中的 BFT 里程碑以 SmartBFT 这一基于库的实现为目标。R3 Corda 使用配备 BFT-SMART 的公证人集群来防止双重支付。CFT 与 BFT 之间的选择反映了信任假设：当验证者可能具有对抗性时需要 BFT；当验证者只是可能不可靠时，CFT 就足够了。

要理解 BFT，就必须了解它能抵御哪些攻击，以及无法抵御哪些攻击。BFT 能够处理发送相互矛盾消息给不同对等节点的模棱两可验证者，也能处理崩溃或保持沉默的验证者。但它无法处理女巫攻击——攻击者通过创建虚假身份控制 1/3 的验证者后，就能破坏安全性。这就是公有 BFT 链采用按质押权益加权的权益证明的原因：获取 1/3 的质押权益需要付出真实资金，从而提供女巫攻击抵抗能力。BFT 还假设消息最终能够送达（部分同步）——持续时间超过活性超时的网络分区可能会使链停止运行。

在保持安全性的同时，标准 BFT 协议最多允许多少比例的验证者为拜占庭节点？

BFT 协议即使面对最多 1/3 的恶意验证者，也能确保共识。PBFT（1999 年）证明了 BFT 的实用性，但具有 O(n^2) 的消息复杂度。Tendermint 通过即时最终性和投票锁定将 PBFT 调整为适用于区块链的协议。HotStuff 通过阈值签名 QC 实现 O(n) 复杂度，并用于 Aptos 和 Sui。Cosmos 的 IBC 使用 Tendermint 的即时最终性来实现经过验证的跨链转账。企业区块链会根据预期面对的是拜占庭故障还是单纯的崩溃故障，选择 BFT-SMART 或 Raft。