【分布式系统百科】Viewstamped Replication 与 PBFT：从 CFT 到 BFT

2013 年，Diego Ongaro 发表了 Raft 论文，让共识算法变得”可理解”。这篇论文影响深远，以至于今天很多工程师提到共识就想到 Raft，提到 Raft 就想到”Leader 选举 + 日志复制”这套范式。

但如果你翻开 Raft 论文的参考文献，会发现一个名字反复出现：Viewstamped Replication。Ongaro 在论文中明确承认，Raft 的很多设计决策——Leader 驱动的日志复制、通过 term 编号检测过时 Leader、多数派投票——与 Viewstamped Replication（以下简称 VR）高度相似。区别在于 VR 比 Raft 早了整整 25 年。

VR 由 Brian Oki 和 Barbara Liskov 在 1988 年提出。是的，就是那个发明了 Liskov 替换原则（Liskov Substitution Principle）的 Barbara Liskov。2012 年，Liskov 和 James Cowling 发表了 VR 的现代重述版本”Viewstamped Replication Revisited”，用更清晰的语言重新描述了这个协议。如果你已经理解了 Raft，读 VR Revisited 会有一种”似曾相识”的感觉——两者的结构惊人地相似，但在细节上各有取舍。

然而 VR 和 Raft 都有一个根本性的局限：它们只能容忍崩溃故障（Crash Fault Tolerance, CFT）。节点要么正常工作，要么彻底停机。如果一个节点被入侵了，开始发送伪造的消息呢？如果一个节点的内存被宇宙射线翻转了一个比特，导致它返回错误的计算结果呢？CFT 协议对此无能为力。

1999 年，Miguel Castro 和 Barbara Liskov（又是她）提出了 Practical Byzantine Fault Tolerance（PBFT），第一次将拜占庭容错（Byzantine Fault Tolerance, BFT）从理论带入了工程可行的范畴。PBFT 的核心思想是：通过增加副本数量（从 2f+1 到 3f+1）和增加通信轮次（从两阶段到三阶段），让系统即使在 f 个节点任意行为异常的情况下仍能达成正确的共识。

这篇文章从 VR 讲起，深入其协议细节，然后过渡到 PBFT，最后分析从 CFT 到 BFT 的本质代价。你会看到，拜占庭容错不是简单地”加几个节点”就能解决的问题——它改变了协议的结构、消息模式和复杂度量级。

一、Viewstamped Replication：被低估的先驱

历史背景

1988 年，分布式系统领域还在 Lamport 的逻辑时钟和拜占庭将军问题的理论框架中摸索。Paxos 论文虽然在 1989 年写成，但直到 1998 年才正式发表。在这个时间窗口里，Oki 和 Liskov 独立地提出了一个基于 Leader（他们称之为 Primary）的状态机复制协议。

VR 的核心思路很直接：在一组副本（Replica）中选出一个主节点（Primary），所有客户端请求都发给 Primary，Primary 负责确定请求的全局顺序，然后将这个顺序复制到其他副本（Backup）。如果 Primary 崩溃了，通过视图切换（View Change）选出新的 Primary 继续服务。

这个思路在今天看来平淡无奇——Raft 不就是这么干的吗？但在 1988 年，这是一个重要的设计决策。当时的主流思路是去中心化的协调（如 Paxos 的多提案者模型），VR 选择了中心化的 Leader 模型，以简化正常操作的流程，代价是需要一个更复杂的 Leader 切换机制。

2012 年的 VR Revisited 论文是理解 VR 的最佳入口。它去掉了 1988 年原始论文中的一些历史包袱，用现代术语重新描述了协议的三个子协议：正常操作（Normal Operation）、视图切换（View Change）和恢复（Recovery）。

VR 的系统模型

VR 运行在以下假设之上：

• 异步网络：消息可能延迟任意长时间，但不会丢失（通过底层的重传机制保证）。
• 崩溃-恢复故障模型（Crash-Recovery）：节点可能崩溃并重启，但不会发送伪造的消息。崩溃期间磁盘上的持久化数据不会损坏。
• 副本数量：总共 2f+1 个副本，可以容忍最多 f 个同时崩溃的副本。
• 确定性状态机：所有副本从相同的初始状态出发，按相同顺序执行相同的操作，最终达到相同的状态。

这里的关键数字是 2f+1。为什么是这个数？因为在崩溃故障模型下，一个崩溃的节点不会干扰共识过程——它只是沉默了。所以你需要的是：即使 f 个节点不响应，剩下的 f+1 个节点仍然构成多数派（majority），能够做出决策。f+1 > (2f+1)/2，多数派的基本算术。

VR 的配置

VR 使用一个配置（Configuration）来描述系统中的副本集合。配置是一个有序列表，包含所有副本的网络地址。副本按它们在配置中的位置编号：0, 1, 2, …, 2f。

视图编号（View Number）：VR 中最重要的概念之一。视图编号是一个单调递增的整数，每次视图切换时加 1。当前视图编号为 v 时，Primary 是编号为 v mod (2f+1) 的副本。这意味着 Primary 的角色在副本之间轮转——视图 0 的 Primary 是副本 0，视图 1 的 Primary 是副本 1，以此类推。

这和 Raft 的 term 概念非常相似，但有一个重要区别：Raft 的 Leader 是通过选举产生的，任何候选者都可能成为 Leader；VR 的 Primary 是通过视图编号确定性地计算出来的，不需要选举投票。

操作编号（Op-number）：类似于 Raft 的日志索引（log index），用于标识每个客户端请求在全局顺序中的位置。

提交编号（Commit-number）：已经被提交（即被 f+1 个副本接受）的最大操作编号。

正常操作协议

VR 的正常操作流程如下（假设当前视图编号为 v，Primary 为 p）：

步骤 1：客户端发送请求。 客户端将请求 <REQUEST op, c, s> 发送给 Primary。其中 op 是操作内容，c 是客户端标识，s 是客户端的请求编号（用于去重和保证幂等性）。

步骤 2：Primary 分配编号并广播。 Primary 将操作编号 n 加 1，把请求追加到自己的日志中，然后向所有 Backup 发送 <PREPARE v, m, n, k> 消息。其中 v 是当前视图编号，m 是客户端请求，n 是新分配的操作编号，k 是当前的提交编号。

步骤 3：Backup 接受并确认。 每个 Backup 收到 PREPARE 消息后，检查视图编号是否匹配。如果匹配，将请求追加到自己的日志中，然后向 Primary 发送 <PREPARE-OK v, n, i> 确认消息，其中 i 是该 Backup 的编号。

步骤 4：Primary 提交。 Primary 收集到 f 个 PREPARE-OK（加上自己就是 f+1 个副本已接受），此时该请求被视为已提交。Primary 执行该操作，更新提交编号，将结果返回给客户端。

步骤 5：Backup 延迟提交。 Backup 并不立即执行已接受的操作。它们通过后续 PREPARE 消息中携带的提交编号 k 来得知哪些操作已经提交，然后按序执行这些操作。

用伪代码描述 Primary 的正常操作：

class VRPrimary:
    def __init__(self, replica_id, config):
        self.view_number = 0
        self.op_number = 0
        self.commit_number = 0
        self.log = []
        self.client_table = {}  # 记录每个客户端的最新请求和结果
        self.replica_id = replica_id
        self.config = config
        self.f = (len(config) - 1) // 2

    def handle_request(self, client_id, request_number, operation):
        # 去重检查：如果已处理过该请求，直接返回缓存的结果
        if client_id in self.client_table:
            last_req, last_result = self.client_table[client_id]
            if request_number <= last_req:
                return last_result  # 幂等性保证

        # 分配操作编号
        self.op_number += 1
        entry = LogEntry(
            op_number=self.op_number,
            operation=operation,
            client_id=client_id,
            request_number=request_number
        )
        self.log.append(entry)

        # 向所有 Backup 发送 PREPARE
        prepare_msg = PrepareMessage(
            view=self.view_number,
            message=operation,
            op_number=self.op_number,
            commit_number=self.commit_number
        )
        ack_count = 1  # 算上自己
        for backup in self.get_backups():
            send(backup, prepare_msg)

        return None  # 等待 PREPARE-OK

    def handle_prepare_ok(self, view, op_number, backup_id):
        if view != self.view_number:
            return  # 忽略旧视图的消息

        # 统计该操作的确认数
        self.ack_counts[op_number] += 1

        if self.ack_counts[op_number] >= self.f:
            # 已收集到 f 个 PREPARE-OK（加上自己是 f+1）
            # 按序提交并执行所有可提交的操作
            while self.commit_number < self.op_number:
                next_commit = self.commit_number + 1
                if self.ack_counts.get(next_commit, 0) >= self.f:
                    result = self.state_machine.apply(self.log[next_commit - 1].operation)
                    self.commit_number = next_commit
                    # 更新客户端表
                    entry = self.log[next_commit - 1]
                    self.client_table[entry.client_id] = (entry.request_number, result)
                    # 向客户端返回结果
                    reply_to_client(entry.client_id, result)
                else:
                    break

Backup 端的逻辑：

class VRBackup:
    def __init__(self, replica_id, config):
        self.view_number = 0
        self.op_number = 0
        self.commit_number = 0
        self.log = []
        self.replica_id = replica_id

    def handle_prepare(self, view, message, op_number, commit_number):
        # 检查视图编号
        if view != self.view_number:
            if view > self.view_number:
                # 需要状态转移（state transfer）
                self.initiate_state_transfer()
            return

        # 检查操作编号是否连续
        if op_number != self.op_number + 1:
            # 日志有空洞，需要状态转移
            self.initiate_state_transfer()
            return

        # 追加日志
        self.op_number = op_number
        self.log.append(LogEntry(op_number=op_number, operation=message))

        # 提交 Primary 已经提交的操作
        while self.commit_number < commit_number:
            self.commit_number += 1
            self.state_machine.apply(self.log[self.commit_number - 1].operation)

        # 回复 PREPARE-OK
        send(self.get_primary(), PrepareOKMessage(
            view=self.view_number,
            op_number=op_number,
            replica_id=self.replica_id
        ))

注意这里有一个重要的设计选择：Backup 的提交是延迟的（lazy commit）。Backup 不是在收到 PREPARE 时就提交，而是在后续收到更新的 commit_number 时才提交之前的操作。这意味着在正常操作中，Backup 的提交进度总是比 Primary 慢一步。这个设计简化了协议，但意味着如果客户端需要读取最新数据，必须从 Primary 读取（或者使用额外的读优化机制）。

VR 与 Raft 的结构对比

在继续讨论视图切换之前，值得暂停一下，对比 VR 和 Raft 的核心结构：

如你所见，两者的正常操作几乎是同构的。最大的结构差异在于视图切换 / Leader 选举的机制。

二、VR 视图切换：比 Raft 选举更精密的换届

VR 的视图切换是整个协议中最精密的部分。当 Backup 怀疑 Primary 已经崩溃时（通过超时检测），它会发起视图切换。

触发条件

每个 Backup 都维护一个 Primary 心跳计时器。如果在超时时间内没有收到 Primary 的 PREPARE 消息（或专门的心跳消息），Backup 就认为 Primary 可能已经崩溃，发起视图切换。

三步走流程

视图切换分为三个阶段：

阶段一：START-VIEW-CHANGE。 检测到超时的 Backup i 将自己的视图编号递增到 v+1，停止接受正常操作的消息，向所有其他副本发送 <START-VIEW-CHANGE v+1, i> 消息。这相当于”我提议进入新视图”。

阶段二：DO-VIEW-CHANGE。 当一个副本收到来自 f 个不同副本的 START-VIEW-CHANGE 消息（包含视图编号 v+1），或者自己也超时了，它就向新视图的 Primary（编号为 (v+1) mod (2f+1) 的副本）发送 <DO-VIEW-CHANGE v+1, l, v', n, k, i> 消息。这个消息携带了关键信息：

• v+1：新视图编号
• l：该副本的日志
• v’：该副本上次正常运行时的视图编号
• n：该副本的操作编号（日志长度）
• k：该副本的提交编号
• i：副本编号

阶段三：START-VIEW。 新 Primary 收到 f+1 个 DO-VIEW-CHANGE 消息后（包含自己的），它需要做一件关键的事情：从所有收到的日志中选出最新的那个。 具体规则是：选择 v’ 最大的日志；如果 v’ 相同，选择 n（操作编号）最大的。这保证了所有已提交的操作都不会丢失。

新 Primary 将自己的状态更新为选出的最新日志，将视图编号设为 v+1，然后向所有副本发送 <START-VIEW v+1, l, n, k> 消息，其中 l 是选出的最新日志。收到 START-VIEW 的 Backup 更新自己的日志和状态，恢复正常操作。

以下时序图展示了 VR 视图切换的完整消息流。从旧 Primary 失联开始，到新 Primary 恢复正常服务结束：

sequenceDiagram
    participant P0 as Primary (v=0)
    participant B1 as Backup-1
    participant B2 as Backup-2
    participant P1 as 新 Primary (v=1)
    participant B3 as Backup-3

    Note over P0: Primary 崩溃或失联
    B1->>B1: 超时检测触发
    B1->>B2: START-VIEW-CHANGE v=1
    B1->>P1: START-VIEW-CHANGE v=1
    B1->>B3: START-VIEW-CHANGE v=1
    B2->>B2: 也超时或收到 f 个 START-VIEW-CHANGE
    B2->>P1: DO-VIEW-CHANGE (v=1, log, v'=0, n, k)
    B1->>P1: DO-VIEW-CHANGE (v=1, log, v'=0, n, k)
    B3->>P1: DO-VIEW-CHANGE (v=1, log, v'=0, n, k)
    Note over P1: 收到 f+1 个 DO-VIEW-CHANGE<br/>选择 v' 最大、n 最大的日志
    P1->>B1: START-VIEW (v=1, 最新 log, n, k)
    P1->>B2: START-VIEW (v=1, 最新 log, n, k)
    P1->>B3: START-VIEW (v=1, 最新 log, n, k)
    Note over P1,B3: 所有副本进入视图 1，恢复正常操作

该时序图的关键在于两阶段结构。第一阶段（START-VIEW-CHANGE）确保足够多的副本知道视图切换正在发生，防止单个副本单方面触发切换。第二阶段（DO-VIEW-CHANGE）将各副本的日志状态汇聚到新 Primary，新 Primary 通过比较 v’ 和 n 选出最完整的日志。这个两阶段设计与 Raft 的一阶段选举（RequestVote）形成鲜明对比，VR 牺牲了选举速度，换取了更严格的状态一致性保证。

class VRViewChange:
    def initiate_view_change(self, replica):
        new_view = replica.view_number + 1
        replica.status = Status.VIEW_CHANGE

        # 向所有副本广播 START-VIEW-CHANGE
        msg = StartViewChangeMessage(view=new_view, replica_id=replica.replica_id)
        broadcast(replica.config, msg)

    def handle_start_view_change(self, replica, view, sender_id):
        if view <= replica.view_number:
            return

        replica.start_view_change_count[view] += 1

        # 收集到 f 个 START-VIEW-CHANGE（含自己的超时触发）
        if replica.start_view_change_count[view] >= replica.f:
            # 向新 Primary 发送 DO-VIEW-CHANGE
            new_primary = view % len(replica.config)
            msg = DoViewChangeMessage(
                view=view,
                log=replica.log,
                latest_normal_view=replica.latest_normal_view,
                op_number=replica.op_number,
                commit_number=replica.commit_number,
                replica_id=replica.replica_id
            )
            send(replica.config[new_primary], msg)

    def handle_do_view_change(self, replica, messages):
        """新 Primary 处理 DO-VIEW-CHANGE 消息"""
        if len(messages) < replica.f + 1:
            return  # 还没收集够

        # 选出最新的日志
        best = max(messages, key=lambda m: (m.latest_normal_view, m.op_number))

        replica.log = best.log
        replica.op_number = best.op_number
        replica.view_number = best.view
        replica.latest_normal_view = best.view
        replica.status = Status.NORMAL

        # 提交所有已知已提交的操作
        max_commit = max(m.commit_number for m in messages)
        while replica.commit_number < max_commit:
            replica.commit_number += 1
            replica.state_machine.apply(replica.log[replica.commit_number - 1].operation)

        # 广播 START-VIEW
        msg = StartViewMessage(
            view=replica.view_number,
            log=replica.log,
            op_number=replica.op_number,
            commit_number=replica.commit_number
        )
        broadcast(replica.config, msg)

视图切换的正确性论证

这个协议为什么是正确的？关键在于两个保证：

保证一：已提交的操作不会丢失。 一个操作被提交意味着它已经被写入至少 f+1 个副本的日志。视图切换需要收集 f+1 个 DO-VIEW-CHANGE 消息。因为总共只有 2f+1 个副本，f+1 + f+1 > 2f+1，所以这两个集合必定有交集。换句话说，在新 Primary 收集到的 f+1 份日志中，至少有一份包含了所有已提交的操作。通过选择”最新”的日志（v’ 最大、n 最大），新 Primary 能保证包含所有已提交的操作。

保证二：未提交的操作可以安全丢弃或保留。 如果一个操作只被写入了不到 f+1 个副本的日志，那么它在视图切换中可能丢失——这是安全的，因为客户端还没有收到确认，它会重试。

这和 Raft 的 Leader 选举中的”Election Safety”保证在本质上是一样的。Raft 通过比较日志的 term 和 index 来选出”最新”的 Leader，VR 通过比较 v’ 和 n 来选出最新的 Primary。机制不同，目标一致。

VR 与 Raft 视图切换 / 选举的差异

尽管目标相同，两者在实现上有几个重要差异：

1. 确定性 vs 随机性。 VR 的新 Primary 是确定性计算出来的（(v+1) mod n），不需要投票选举。Raft 的 Leader 选举依赖随机化的选举超时来避免分裂投票（split vote），引入了不确定性。VR 的确定性方式消除了分裂投票问题，但如果目标 Primary 本身也崩溃了，就需要再次递增视图编号。

2. 日志传输。 VR 的 DO-VIEW-CHANGE 消息需要携带完整的日志——这在日志很大时是个显著的开销。Raft 的选举请求（RequestVote）只需要携带最后一个日志条目的 term 和 index，选举后再通过 AppendEntries 逐步对齐日志。Raft 的方式在大日志场景下效率更高。不过 VR Revisited 论文也讨论了通过日志截断和检查点来缓解这个问题。

3. 两阶段 vs 一阶段。 VR 的视图切换是两阶段的（START-VIEW-CHANGE → DO-VIEW-CHANGE），而 Raft 的选举本质上是一阶段的（RequestVote → 收集选票）。VR 的两阶段设计是为了确保足够多的副本已经知道要进行视图切换，防止出现一个副本单方面发起切换的情况。

三、VR 的恢复协议

当一个崩溃的副本重启后，它的内存状态已经丢失（虽然磁盘上有持久化的数据）。它需要通过恢复协议重新加入集群。

VR 的恢复协议并不复杂。恢复中的副本向所有其他副本发送 <RECOVERY i, x> 消息，其中 x 是一个随机数（nonce），用于防止重放攻击——确保收到的回复确实是针对这次恢复请求的。

其他副本收到 RECOVERY 消息后，回复 <RECOVERY-RESPONSE v, x, l, n, k, j> 消息。只有当前 Primary 会在回复中包含完整的日志 l。

恢复中的副本等待收到 f+1 个 RECOVERY-RESPONSE（确保它连接的是多数派），并且其中必须包含来自当前 Primary 的回复（因为只有 Primary 发送完整日志）。然后它将自己的状态更新为 Primary 提供的状态，恢复正常操作。

恢复协议的一个微妙之处在于：如果在恢复过程中发生了视图切换（Primary 换人了），恢复中的副本可能收到来自旧 Primary 的回复——这种回复应该被忽略，重新发起恢复。nonce 机制在这里起到了关键作用：每次恢复使用新的 nonce，旧的回复会因为 nonce 不匹配而被丢弃。

VR 作为 CFT 协议的局限性

VR 的整个设计建立在一个关键假设上：节点不会撒谎。 一个崩溃的节点可能不回复消息，但它不会发送错误的消息。如果一个节点发送了一个 PREPARE-OK，你可以信任这个消息的内容是正确的。

这个假设在很多实际场景中是合理的：数据中心内部的节点通常不会被恶意控制，硬件故障导致的数据损坏可以通过校验和检测。但在以下场景中，这个假设就不成立了：

• 开放网络：参与共识的节点可能被攻击者控制。
• 多方信任：参与者之间没有完全的信任关系（如区块链场景）。
• 硬件故障：某些硬件故障（如内存位翻转）可能导致节点发送看似合法但实际错误的消息。
• 软件 bug：一个有 bug 的节点可能在特定条件下产生错误的输出，表现得像拜占庭故障。

要在这些场景下达成共识，就需要拜占庭容错协议。而从 CFT 到 BFT 的跨越，远不是简单地”多加几个节点”就能搞定的。

四、拜占庭将军问题：为什么容忍”撒谎”这么难

在进入 PBFT 之前，我们需要理解一个基本问题：为什么拜占庭容错比崩溃容错困难得多？

1982 年，Lamport、Shostak 和 Pease 在经典论文”The Byzantine Generals Problem”中给出了一个下界结果：在同步网络中，要容忍 f 个拜占庭故障节点，至少需要 3f+1 个节点。注意是 3f+1，不是 2f+1。

为什么是 3f+1？直觉解释

让我们先用直觉理解为什么 2f+1 不够。

假设有 3 个节点（2*1+1 = 3），其中 1 个是拜占庭节点（f=1）。假设节点 A 是 Primary，它向节点 B 和 C 发送提案”执行操作 X”。

• 如果 C 是拜占庭节点，它可能向 B 说”我没收到 A 的提案”或者”A 发给我的是操作 Y”。B 收到了 A 的 X 和 C 的矛盾信息，但 B 无法判断是 A 在撒谎还是 C 在撒谎。
• 更糟糕的是，如果 A 是拜占庭节点，它可能给 B 发了操作 X，给 C 发了操作 Y。B 和 C 各自收到不同的提案，但它们彼此无法区分这种情况和 C/B 在撒谎的情况。

3 个节点中有 1 个拜占庭节点时，诚实节点无法达成一致。这不是协议设计的问题，是信息论层面的不可能。

3f+1 的严格论证

让我们用更形式化的方式理解 3f+1 的必要性。考虑一个安全的共识协议需要满足的两个条件：

条件一：法定人数（Quorum）的交集性。 任何两个法定人数必须有足够多的诚实节点的交集。在 BFT 中，一个操作被”确认”需要一个法定人数 Q 的同意。为了保证安全性，任意两个法定人数 Q1 和 Q2 的交集中必须包含至少一个诚实节点。如果交集中只有拜占庭节点，它们可能对 Q1 和 Q2 说了不同的话，导致两个冲突的操作都被”确认”。

条件二：活性要求。 即使 f 个节点完全不响应（拜占庭节点可以选择保持沉默），系统仍需能够做出决策。这意味着法定人数的大小最多为 n-f。

把这两个条件放在一起：

• 法定人数大小 Q <= n - f（因为 f 个节点可能不响应）
• 任意两个法定人数的交集大小 >= f + 1（需要至少一个诚实节点在交集中，而交集中最多有 f 个拜占庭节点）
• 两个法定人数的交集大小 >= 2Q - n（鸽巢原理）

所以：2Q - n >= f + 1，即 2(n-f) - n >= f + 1，化简得 n >= 3f + 1。

这就是 3f+1 的来源。它不是 PBFT 的设计选择，而是拜占庭容错的理论下界。任何 BFT 协议，无论怎么设计，都至少需要 3f+1 个节点。

实际意义：代价有多大？

节点数量的增加不仅意味着更多的硬件成本，还意味着更多的通信开销——特别是在 PBFT 中，消息复杂度是 O(n²)，节点数量的增加会导致通信量呈二次增长。

五、PBFT：让拜占庭容错走进现实

1999 年，Castro 和 Liskov 发表了”Practical Byzantine Fault Tolerance”论文。标题中的”Practical”是刻意的强调：在此之前，BFT 协议的理论已经存在了近 20 年，但没有人展示过它在实际系统中可以高效运行。PBFT 的贡献不是发明了 BFT 的理论，而是将其工程化——展示了一个 BFT 协议可以在性能只比 CFT 协议差 3% 左右的条件下运行。

PBFT 的系统模型

PBFT 运行在以下假设之上：

• 部分同步网络（Partial Synchrony）：安全性（safety）在异步网络中也能保证，但活性（liveness）需要网络最终变得同步（即消息延迟有界）。这和 VR/Raft 的假设一致。
• 拜占庭故障模型：最多 f 个节点可以有任意行为——不响应、发送错误消息、与其他拜占庭节点合谋。
• 副本数量：n = 3f+1。
• 密码学假设：使用消息认证码（MAC）或数字签名来防止消息伪造和篡改。拜占庭节点不能伪造诚实节点的签名。这是一个重要的假设——它让 PBFT 不需要像原始拜占庭将军协议那样需要 f+1 轮通信。

为什么需要三个阶段？

VR 和 Raft 的正常操作本质上是两阶段的：提案（PREPARE/AppendEntries）和确认（PREPARE-OK/响应）。为什么 PBFT 需要三个阶段？

答案在于 BFT 中一个微妙的问题：在 CFT 中，如果你收到了一个节点的确认消息，你可以信任这个消息。但在 BFT 中，你不能——这个节点可能在对你说”确认”的同时，对另一个节点说”拒绝”。

考虑一个只有两阶段的 BFT 协议：Primary 发送提案，副本回复确认，Primary 收集到足够多的确认就提交。问题在于：Primary 自己可能是拜占庭节点。它可能只把”已提交”的消息告诉了部分节点，然后崩溃了。在视图切换时，新 Primary 收集到的信息可能不一致——有的节点认为操作已提交，有的不知道。在 CFT 中这不是问题，因为一个诚实的节点如果说”我确认了”，新 Primary 可以信任它。但在 BFT 中，说”我确认了”的可能是一个在撒谎的拜占庭节点。

第三个阶段（Commit 阶段）的目的是：确保足够多的诚实节点知道”这个操作已经被准备好了”，即使 Primary 在提交后立即崩溃，新 Primary 也能从诚实节点那里恢复出这个信息。

三阶段协议详解

PBFT 的正常操作包含三个阶段：预准备（Pre-prepare）、准备（Prepare）和提交（Commit）。

客户端发送请求。 客户端将请求 <REQUEST, o, t, c> 发送给 Primary。其中 o 是操作，t 是时间戳（用于保证请求的全序性），c 是客户端标识。如果超时没有收到回复，客户端将请求广播给所有副本——这是为了防止 Primary 是拜占庭节点故意丢弃请求。

阶段一：Pre-prepare。 Primary 为请求分配一个序号 n（在当前视图 v 中），然后向所有 Backup 广播 <<PRE-PREPARE, v, n, d>, m> 消息。其中 d 是请求 m 的摘要（digest）。注意这里用的是摘要而不是完整请求——因为 Pre-prepare 消息需要被签名，使用摘要可以减小签名的计算量。

Backup 收到 Pre-prepare 后进行以下验证：

1. 签名正确。
2. 视图编号与自己当前视图一致。
3. 在当前视图中，没有收到过相同序号 n 但不同摘要 d 的 Pre-prepare 消息（防止 Primary 给同一个序号分配不同的请求）。
4. 序号 n 在水位标记（water mark）范围内：h < n <= H（后面详述）。

如果验证通过，Backup 接受这个 Pre-prepare，进入 Prepare 阶段。

阶段二：Prepare。 接受 Pre-prepare 的 Backup 向所有其他副本（包括 Primary）广播 <PREPARE, v, n, d, i> 消息，其中 i 是该副本的编号。同时把 Pre-prepare 和 Prepare 消息写入自己的消息日志。

每个副本收集 Prepare 消息。当一个副本收到了关于 (v, n, d) 的 2f 个来自不同副本的 Prepare 消息（加上对应的 Pre-prepare），并且它们的视图编号、序号和摘要都一致，这个副本就达到了”prepared”状态。形式化地说：

副本 i 对 (m, v, n) 达到 prepared 状态，当且仅当它的消息日志中包含： 1. 请求 m 2. 关于 m 的 Pre-prepare 消息 <PRE-PREPARE, v, n, d> 3. 来自 2f 个不同副本的匹配的 Prepare 消息 <PREPARE, v, n, d, j>

prepared 状态的含义是：至少 f+1 个诚实节点同意在视图 v 中，序号 n 对应请求 m。 为什么？总共收到了 2f+1 个一致的消息（Pre-prepare + 2f 个 Prepare），其中最多 f 个来自拜占庭节点，所以至少 f+1 个来自诚实节点。

阶段三：Commit。 达到 prepared 状态的副本向所有其他副本广播 <COMMIT, v, n, d, i> 消息。

当一个副本收到了 2f+1 个来自不同副本的 Commit 消息（包括自己的），并且它们关于 (v, n) 一致，这个副本就达到了”committed-local”状态。

达到 committed-local 状态的副本等待所有序号小于 n 的请求都执行完毕后，执行序号为 n 的请求，并将结果返回给客户端。

下面的时序图展示了 PBFT 三阶段提交的完整消息流。以 n=4（f=1）的集群为例，注意 Prepare 和 Commit 阶段的全连接广播模式是 O(n^2) 消息复杂度的根源：

sequenceDiagram
    participant C as Client
    participant R0 as R0 (Primary)
    participant R1 as R1
    participant R2 as R2
    participant R3 as R3

    C->>R0: REQUEST (op, t, c)
    Note over R0: 分配序号 n，计算摘要 d

    rect rgb(230, 245, 255)
    Note right of R0: Phase 1: Pre-prepare
    R0->>R1: PRE-PREPARE (v, n, d) + m
    R0->>R2: PRE-PREPARE (v, n, d) + m
    R0->>R3: PRE-PREPARE (v, n, d) + m
    end

    rect rgb(255, 245, 230)
    Note right of R0: Phase 2: Prepare（全连接广播）
    R1->>R0: PREPARE (v, n, d, 1)
    R1->>R2: PREPARE (v, n, d, 1)
    R1->>R3: PREPARE (v, n, d, 1)
    R2->>R0: PREPARE (v, n, d, 2)
    R2->>R1: PREPARE (v, n, d, 2)
    R2->>R3: PREPARE (v, n, d, 2)
    R3->>R0: PREPARE (v, n, d, 3)
    R3->>R1: PREPARE (v, n, d, 3)
    R3->>R2: PREPARE (v, n, d, 3)
    Note over R0,R3: 每个副本收到 2f=2 个 PREPARE<br/>达到 prepared 状态
    end

    rect rgb(230, 255, 230)
    Note right of R0: Phase 3: Commit（全连接广播）
    R0->>R1: COMMIT (v, n, d, 0)
    R0->>R2: COMMIT (v, n, d, 0)
    R0->>R3: COMMIT (v, n, d, 0)
    R1->>R0: COMMIT (v, n, d, 1)
    R1->>R2: COMMIT (v, n, d, 1)
    R1->>R3: COMMIT (v, n, d, 1)
    R2->>R0: COMMIT (v, n, d, 2)
    R2->>R1: COMMIT (v, n, d, 2)
    R2->>R3: COMMIT (v, n, d, 2)
    R3->>R0: COMMIT (v, n, d, 3)
    R3->>R1: COMMIT (v, n, d, 3)
    R3->>R2: COMMIT (v, n, d, 3)
    Note over R0,R3: 每个副本收到 2f+1=3 个 COMMIT<br/>达到 committed-local 状态
    end

    par 各副本独立回复客户端
        R0-->>C: REPLY (v, t, c, 0, result)
        R1-->>C: REPLY (v, t, c, 1, result)
        R2-->>C: REPLY (v, t, c, 2, result)
        R3-->>C: REPLY (v, t, c, 3, result)
    end
    Note over C: 收到 f+1=2 个相同结果<br/>确认操作成功

该时序图清晰地展示了 PBFT 的 O(n^2) 消息模式。Pre-prepare 阶段只有 O(n) 条消息（Primary 单向广播），但 Prepare 和 Commit 两个阶段中每个副本都向所有其他副本广播，各产生 n*(n-1) 条消息。在 n=4 的小规模下总共约 32 条消息尚可接受，但随着 n 增长到 100，每个请求将产生约 2 万条消息。全连接广播的根本原因是 BFT 环境中不能信任 Primary 作为唯一的信息汇聚点，每个副本必须独立收集和验证来自所有其他副本的确认。

客户端收集回复。 客户端等待收到 f+1 个来自不同副本的相同结果。因为最多 f 个节点是拜占庭的，f+1 个一致的结果中至少有一个来自诚实节点，所以结果一定是正确的。

以下是 PBFT 三阶段协议的伪代码：

class PBFTReplica:
    def __init__(self, replica_id, n_replicas):
        self.id = replica_id
        self.n = n_replicas
        self.f = (n_replicas - 1) // 3
        self.view = 0
        self.sequence_number = 0
        self.log = {}           # (v, n) -> LogEntry
        self.prepared_certs = {}  # (v, n) -> set of PREPARE messages
        self.commit_certs = {}    # (v, n) -> set of COMMIT messages
        self.last_executed = 0
        self.low_watermark = 0
        self.high_watermark = self.low_watermark + CHECKPOINT_INTERVAL * 2

    def is_primary(self):
        return self.id == self.view % self.n

    # ---- Primary 行为 ----
    def handle_client_request(self, request):
        if not self.is_primary():
            forward_to_primary(request)
            return

        self.sequence_number += 1
        n = self.sequence_number
        d = digest(request)

        # 创建并广播 PRE-PREPARE
        pre_prepare = PrePrepare(view=self.view, seq=n, digest=d)
        self.log[(self.view, n)] = LogEntry(
            pre_prepare=pre_prepare,
            request=request,
            state='pre-prepared'
        )
        sign_and_broadcast(pre_prepare, request)

    # ---- Backup 收到 PRE-PREPARE ----
    def handle_pre_prepare(self, pre_prepare, request):
        v, n, d = pre_prepare.view, pre_prepare.seq, pre_prepare.digest

        # 验证
        if v != self.view:
            return
        if not verify_signature(pre_prepare, primary_id=v % self.n):
            return
        if (v, n) in self.log and self.log[(v, n)].pre_prepare.digest != d:
            return  # 同一序号不同摘要，Primary 可能是拜占庭的
        if not (self.low_watermark < n <= self.high_watermark):
            return  # 超出水位范围

        # 接受 PRE-PREPARE，广播 PREPARE
        self.log[(v, n)] = LogEntry(
            pre_prepare=pre_prepare,
            request=request,
            state='pre-prepared'
        )
        prepare = Prepare(view=v, seq=n, digest=d, replica_id=self.id)
        sign_and_broadcast(prepare)
        self.check_prepared(v, n, d)

    # ---- 收到 PREPARE ----
    def handle_prepare(self, prepare):
        v, n, d = prepare.view, prepare.seq, prepare.digest

        if v != self.view:
            return
        if not verify_signature(prepare, replica_id=prepare.replica_id):
            return

        if (v, n) not in self.prepared_certs:
            self.prepared_certs[(v, n)] = set()
        self.prepared_certs[(v, n)].add(prepare)

        self.check_prepared(v, n, d)

    def check_prepared(self, v, n, d):
        """检查是否达到 prepared 状态"""
        if (v, n) not in self.log:
            return
        entry = self.log[(v, n)]
        if entry.state != 'pre-prepared':
            return

        prepares = self.prepared_certs.get((v, n), set())
        matching = [p for p in prepares if p.digest == d]

        if len(matching) >= 2 * self.f:
            # 达到 prepared 状态：2f PREPARE + 1 PRE-PREPARE = 2f+1 一致
            entry.state = 'prepared'

            # 广播 COMMIT
            commit = Commit(view=v, seq=n, digest=d, replica_id=self.id)
            sign_and_broadcast(commit)
            self.check_committed(v, n)

    # ---- 收到 COMMIT ----
    def handle_commit(self, commit):
        v, n = commit.view, commit.seq

        if v != self.view:
            return
        if not verify_signature(commit, replica_id=commit.replica_id):
            return

        if (v, n) not in self.commit_certs:
            self.commit_certs[(v, n)] = set()
        self.commit_certs[(v, n)].add(commit)

        self.check_committed(v, n)

    def check_committed(self, v, n):
        """检查是否达到 committed-local 状态"""
        if (v, n) not in self.log:
            return
        entry = self.log[(v, n)]
        if entry.state != 'prepared':
            return

        commits = self.commit_certs.get((v, n), set())
        if len(commits) >= 2 * self.f + 1:
            entry.state = 'committed'
            self.try_execute()

    def try_execute(self):
        """按序执行已提交的请求"""
        while True:
            next_seq = self.last_executed + 1
            key = (self.view, next_seq)
            if key not in self.log:
                break
            entry = self.log[key]
            if entry.state != 'committed':
                break

            result = self.state_machine.apply(entry.request.operation)
            self.last_executed = next_seq

            # 向客户端发送 REPLY
            reply = Reply(
                view=self.view,
                timestamp=entry.request.timestamp,
                client_id=entry.request.client_id,
                replica_id=self.id,
                result=result
            )
            send_to_client(entry.request.client_id, reply)

O(n²) 消息复杂度分析

PBFT 的一个显著特征是其消息复杂度为 O(n²)。让我们精确分析每个阶段的消息数量：

• Pre-prepare 阶段：Primary 向 n-1 个 Backup 发送消息 → n-1 条消息
• Prepare 阶段：每个接受 Pre-prepare 的副本向其他所有副本广播 → 最多 (n-1) × (n-1) ≈ n² 条消息
• Commit 阶段：每个达到 prepared 状态的副本向所有副本广播 → 最多 n × (n-1) ≈ n² 条消息
• Reply 阶段：每个副本向客户端发送回复 → n 条消息

总计：约 2n² 条消息处理一个客户端请求。

当 f=1（n=4）时，这不是问题——大约 32 条消息。但当 f=33（n=100）时，每个请求需要约 20000 条消息。当 f=333（n=1000）时，每个请求需要约 2000000 条消息。这就是为什么 PBFT 在大规模系统中不可行的根本原因。

实际上，PBFT 论文中的实验只测试了 4 个副本（f=1）和 7 个副本（f=2）的情况。在这个规模下，PBFT 的性能确实接近 CFT 协议。但随着副本数量增长，O(n²) 的通信开销会迅速成为瓶颈。

Prepare 和 Commit 两个阶段为何都需要 O(n²)？

一个自然的问题是：为什么 Prepare 和 Commit 两个阶段都需要全副本广播？能不能像 VR/Raft 那样只发给 Primary？

不能。原因在于 BFT 的核心困难：你不能信任 Primary。

在 VR/Raft 中，副本把 PREPARE-OK 发给 Primary 就行了，因为 Primary 如果是诚实的，它会在收集到多数派确认后正确地提交。即使 Primary 崩溃了，这个事实会被检测到，然后通过视图切换选出新 Primary。

但在 PBFT 中，Primary 可能是拜占庭的。如果副本只把 Prepare 消息发给 Primary，Primary 可能声称”我收到了足够多的 Prepare”并提交，但实际上它在撒谎。其他副本无法验证这一点，因为它们没有看到彼此的 Prepare 消息。

所以 Prepare 消息必须广播给所有副本，让每个副本独立地验证是否有足够多的一致确认。Commit 阶段同理——每个副本需要独立确认有足够多的副本已经达到 prepared 状态。

这就是 BFT 的本质代价：因为不能信任任何单一节点来充当信息汇聚点，每个节点都必须独立收集和验证来自所有其他节点的信息。 这天然导致了 O(n²) 的消息模式。

六、PBFT 的视图切换

PBFT 的视图切换比 VR 的复杂得多，原因还是一样的：你不能信任任何单一节点。

触发条件

当一个 Backup 怀疑 Primary 是拜占庭节点时（例如：超时未收到 Pre-prepare、收到了矛盾的 Pre-prepare、多个客户端投诉 Primary 不处理请求），它发起视图切换。

视图切换流程

步骤一： Backup i 停止接受当前视图的消息，将视图编号递增到 v+1，向所有副本广播 <VIEW-CHANGE, v+1, n, C, P, i> 消息。其中：

• n：最近一次稳定检查点（stable checkpoint）的序号
• C：证明检查点正确性的 2f+1 个检查点消息集合
• P：一个集合，包含在序号 n 之后、该副本达到 prepared 状态的所有请求的 prepared 证书（即 Pre-prepare 消息和 2f 个匹配的 Prepare 消息）

这里的 P 集合是关键——它携带了”哪些请求可能已经被提交”的证据。因为在 BFT 中，你不能简单地相信”我的日志是最新的”这种说法。你需要提供密码学证据（签名的消息集合）来证明你的状态。

步骤二： 新 Primary（编号为 (v+1) mod n 的副本）收集到 2f 个来自不同副本的 VIEW-CHANGE 消息后（加上自己的就是 2f+1 个），构造 <NEW-VIEW, v+1, V, O> 消息并广播。其中：

• V：收到的 2f+1 个 VIEW-CHANGE 消息的集合
• O：新 Primary 根据 V 中的 prepared 证书计算出的新 Pre-prepare 消息集合

新 Primary 如何计算 O？对于每个序号 n’（从最低水位到最高水位），如果在 V 中的任何 VIEW-CHANGE 消息中存在序号 n’ 的 prepared 证书，新 Primary 创建一个新的 <PRE-PREPARE, v+1, n', d> 消息（使用原始请求的摘要）。如果没有，创建一个空操作（no-op）的 Pre-prepare。

步骤三： 其他副本收到 NEW-VIEW 后，验证其中的 VIEW-CHANGE 消息和计算出的 Pre-prepare 集合是否正确（即自己按照相同规则计算得到相同的结果）。验证通过后，进入新视图，对每个 Pre-prepare 执行正常的 Prepare/Commit 流程。

class PBFTViewChange:
    def initiate_view_change(self, replica):
        new_view = replica.view + 1
        replica.status = Status.VIEW_CHANGING

        # 构造 prepared 证书集合 P
        P = []
        for (v, n), entry in replica.log.items():
            if n > replica.stable_checkpoint and entry.state in ('prepared', 'committed'):
                cert = PreparedCertificate(
                    pre_prepare=entry.pre_prepare,
                    prepares=list(replica.prepared_certs.get((v, n), set()))
                )
                P.append(cert)

        msg = ViewChangeMessage(
            new_view=new_view,
            last_stable_checkpoint=replica.stable_checkpoint,
            checkpoint_proof=replica.checkpoint_proof,
            prepared_certs=P,
            replica_id=replica.id
        )
        sign_and_broadcast(msg)

    def handle_view_change_as_new_primary(self, replica, view_changes):
        """新 Primary 处理收到的 VIEW-CHANGE 消息"""
        if len(view_changes) < 2 * replica.f + 1:
            return

        new_view = view_changes[0].new_view

        # 确定序号范围
        min_s = max(vc.last_stable_checkpoint for vc in view_changes)
        max_s = max(
            max((cert.pre_prepare.seq for cert in vc.prepared_certs), default=min_s)
            for vc in view_changes
        )

        # 对每个序号计算新的 Pre-prepare
        new_pre_prepares = []
        for n in range(min_s + 1, max_s + 1):
            # 查找是否有任何 VIEW-CHANGE 包含序号 n 的 prepared 证书
            best_cert = None
            for vc in view_changes:
                for cert in vc.prepared_certs:
                    if cert.pre_prepare.seq == n:
                        if best_cert is None or cert.pre_prepare.view > best_cert.pre_prepare.view:
                            best_cert = cert

            if best_cert is not None:
                pp = PrePrepare(view=new_view, seq=n, digest=best_cert.pre_prepare.digest)
            else:
                pp = PrePrepare(view=new_view, seq=n, digest=NULL_DIGEST)

            new_pre_prepares.append(pp)

        # 广播 NEW-VIEW
        new_view_msg = NewViewMessage(
            new_view=new_view,
            view_changes=view_changes,
            pre_prepares=new_pre_prepares
        )
        sign_and_broadcast(new_view_msg)

        # 自己进入新视图
        replica.view = new_view
        replica.status = Status.NORMAL

视图切换的正确性

PBFT 视图切换的核心正确性保证和 VR 一样：已提交的请求不会丢失。

一个请求在序号 n 被提交，意味着 2f+1 个副本达到了 committed-local 状态，这又意味着这些副本中的 2f+1 个达到了 prepared 状态。新 Primary 收集到的 2f+1 个 VIEW-CHANGE 消息必然和这些 prepared 副本有交集（因为 (2f+1) + (2f+1) > 3f+1），所以新 Primary 一定会看到序号 n 的 prepared 证书，并在 NEW-VIEW 中保留它。

但这里有一个 VR/Raft 中不存在的复杂性：VIEW-CHANGE 消息必须携带密码学证据（prepared 证书），而不只是一个日志。 在 VR 中，新 Primary 信任 Backup 发来的日志内容。在 PBFT 中，新 Primary 不信任任何人——它需要验证 prepared 证书中的签名来确认”这个请求确实在视图 v 中达到了 prepared 状态”。

这也是为什么 PBFT 的视图切换消息比 VR 大得多——它需要携带 O(n) 条签名消息作为证据。

七、检查点与水位机制

PBFT 的日志不能无限增长——不仅因为存储空间有限，更因为视图切换时需要携带 prepared 证书。如果日志无限增长，视图切换消息的大小也会无限增长，协议将变得不可行。

检查点（Checkpoint）

PBFT 使用周期性检查点来截断日志。每当一个副本执行了第 K 个请求（K 是检查点间隔，比如每 128 个请求），它就创建一个检查点，包含此时状态机的状态摘要，并向所有副本广播 <CHECKPOINT, n, d, i> 消息，其中 n 是序号，d 是状态摘要，i 是副本编号。

当一个副本收到了 2f+1 个关于同一个 (n, d) 的 CHECKPOINT 消息，这个检查点就成为”稳定检查点（stable checkpoint）“。2f+1 个一致的检查点消息意味着至少 f+1 个诚实节点同意这个检查点是正确的——即使有 f 个拜占庭节点试图伪造检查点状态，它们也无法凑够 2f+1 个一致的消息。

稳定检查点建立后，副本可以安全地丢弃序号小于等于 n 的所有日志条目和相关的消息。

水位标记（Water Mark）

水位标记是 PBFT 中防止拜占庭 Primary 攻击的关键机制。

低水位标记（Low Water Mark, h）：等于最近一次稳定检查点的序号。任何序号小于等于 h 的请求都已经被包含在检查点中，对应的日志可以丢弃。

高水位标记（High Water Mark, H）：等于 h + L，其中 L 是一个常数（通常设为检查点间隔的若干倍，比如 L = 2K，其中 K 是检查点间隔）。

副本只接受序号在 (h, H] 范围内的 Pre-prepare 消息。这个限制的作用是：

防止拜占庭 Primary 的序号攻击。 如果没有高水位限制，一个拜占庭 Primary 可以给请求分配一个巨大的序号（比如 2^64），导致所有副本在视图切换时需要为这个序号之前的所有”空位”创建空操作的 Pre-prepare，视图切换消息的大小会爆炸。

流量控制。 水位机制起到了类似 TCP 滑动窗口的作用——Primary 不能发送太超前的请求，必须等前面的请求被提交并建立检查点后才能继续。这防止了快速 Primary 淹没慢速 Backup。

class PBFTCheckpoint:
    CHECKPOINT_INTERVAL = 128

    def maybe_checkpoint(self, replica):
        """在执行请求后检查是否需要创建检查点"""
        if replica.last_executed % self.CHECKPOINT_INTERVAL != 0:
            return

        n = replica.last_executed
        state_digest = replica.state_machine.digest()

        # 广播 CHECKPOINT 消息
        msg = CheckpointMessage(seq=n, digest=state_digest, replica_id=replica.id)
        sign_and_broadcast(msg)
        replica.checkpoint_msgs[n].add(msg)

        self.check_stable(replica, n)

    def check_stable(self, replica, n):
        """检查检查点是否稳定"""
        msgs = replica.checkpoint_msgs.get(n, set())
        if len(msgs) < 2 * replica.f + 1:
            return

        # 验证所有消息的状态摘要一致
        digests = set(m.digest for m in msgs)
        if len(digests) != 1:
            return  # 不一致，可能有拜占庭节点

        # 建立稳定检查点
        replica.stable_checkpoint = n
        replica.checkpoint_proof = msgs  # 保留证明，视图切换时需要
        replica.low_watermark = n
        replica.high_watermark = n + 2 * self.CHECKPOINT_INTERVAL

        # 垃圾回收：丢弃旧日志
        for key in list(replica.log.keys()):
            if key[1] <= n:
                del replica.log[key]
        for key in list(replica.prepared_certs.keys()):
            if key[1] <= n:
                del replica.prepared_certs[key]
        for key in list(replica.commit_certs.keys()):
            if key[1] <= n:
                del replica.commit_certs[key]

八、PBFT 的实际局限性

尽管 PBFT 在理论上优雅地解决了拜占庭容错问题，它在实际部署中面临了多重挑战，导致它在发表后的十多年里并没有被广泛采用。

1. O(n²) 的通信瓶颈

前面已经分析过，每个请求需要约 2n² 条消息。PBFT 论文中的实验只测试了 n=4 和 n=7 的场景。在这个规模下，消息数量分别约为 32 条和 98 条，完全可以接受。但即使是 n=31（f=10），每个请求的消息数量就超过了 1800 条。对于需要高吞吐量的系统，这个开销是致命的。

PBFT 的作者自己后来也尝试了多种优化：

• 消息认证码（MAC）替代数字签名：MAC 的计算速度比 RSA 签名快几个数量级。PBFT 在正常操作中使用 MAC，只在视图切换等需要不可否认性的场合使用数字签名。
• 批处理（Batching）：将多个客户端请求打包成一个批次，一次三阶段协议处理整批请求。这将每个请求的摊销消息数从 O(n²) 降低到 O(n²/B)，其中 B 是批次大小。
• 推测执行（Speculative Execution）：在 Zyzzyva（2007）中，Castro 等人提出了一种优化——如果所有 3f+1 个副本都一致回复了客户端，客户端可以直接接受结果，跳过 Commit 阶段。这将最好情况下的通信轮次从 3 轮降到 2 轮。但如果有任何不一致，需要回退到完整协议，增加了延迟。

2. 视图切换的复杂性

PBFT 的视图切换协议比正常操作复杂得多——它需要收集和传输大量的密码学证据。在实际实现中，视图切换的正确性很难保证，Bug 频发。

2010 年，Clement 等人在论文”Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults”中指出，PBFT 的原始实现在视图切换过程中存在多个 Bug，其中一些可以被利用来让系统停止服务。他们还指出了一个更根本的问题：PBFT 假设拜占庭节点最多 f 个，但没有考虑如果有超过 f 个节点表现出拜占庭行为（例如由于软件 Bug），协议的行为是不确定的。

3. 性能下降问题

在 PBFT 中，一个拜占庭 Primary 可以通过以下方式降低系统性能而不违反协议的安全性：

• 故意延迟 Pre-prepare 消息的发送。
• 给某些请求分配序号但”忘记”广播对应的 Pre-prepare。
• 选择性地只给部分 Backup 发送 Pre-prepare。

这些行为最终会触发视图切换，但在视图切换完成之前，系统的性能会受到严重影响。Aardvark（2009）等后续工作试图通过更积极的 Primary 切换策略来缓解这个问题。

4. 缺乏实际部署驱动力

在 PBFT 发表的年代（1999 年），绝大多数分布式系统运行在受信任的数据中心环境中。崩溃容错（CFT）协议足以应对大部分故障场景，没有强烈的动力去部署 BFT 系统。BFT 的硬件和通信开销（比 CFT 多 50% 的节点，多一个数量级的消息）在当时的性价比并不好。

这种情况在 2008 年比特币出现后发生了改变——区块链需要在完全不信任的开放网络中达成共识，BFT 变得不可或缺。但比特币选择了 Nakamoto 共识（基于工作量证明的概率性共识），而非 PBFT 风格的确定性共识。直到 2016 年 Tendermint/Cosmos 和后来的 HotStuff/LibraBFT 的出现，PBFT 的思想才在区块链领域得到了真正的工程化应用。

九、从 CFT 到 BFT：本质代价分析

现在我们可以系统地分析从 CFT 到 BFT 的转变带来了哪些本质性的变化。

1. 信任模型的变化

CFT 协议的核心假设是：“节点要么正确工作，要么停机。” 这意味着你可以信任任何你收到的消息——如果一个节点说”我接受了这个提案”，它一定是真的接受了。

BFT 协议的假设是：“节点可能做任何事情。” 这意味着你不能信任任何单一节点的消息。验证一个事实需要来自多个独立节点的密码学证据。

这个信任模型的变化是所有其他差异的根源。

2. 节点数量：从 2f+1 到 3f+1

在 CFT 中，f+1 个节点构成的多数派中一定全是诚实节点（因为只有崩溃的节点不参与，而崩溃节点不会加入多数派——它们保持沉默）。

在 BFT 中，一个 2f+1 的多数派中可能包含 f 个拜占庭节点，只有 f+1 个是诚实的。两个 2f+1 的法定人数的交集可能只有 1 个节点，而这个节点可能是拜占庭的。所以需要更大的法定人数（2f+1 out of 3f+1）来确保交集中至少有 f+1 个节点，其中至少一个是诚实的。

3. 通信模式：从星形到全连接

在 VR/Raft 中，通信是星形拓扑的：

Backup1 ←→ Primary ←→ Backup2
               ↕
           Backup3

所有重要的消息都通过 Primary 中转。Backup 之间不直接通信（至少在正常操作中不需要）。每个操作的消息数量是 O(n)。

在 PBFT 中，通信是全连接的：

R0 ←→ R1
↕  ×  ↕
R2 ←→ R3

每个副本需要向所有其他副本广播消息，每个副本需要独立验证来自所有其他副本的消息。消息数量是 O(n²)。

这个差异的原因在前面已经分析过：在 CFT 中，Primary 是可信的信息汇聚点；在 BFT 中，不存在可信的信息汇聚点。

4. 密码学开销

CFT 协议通常不需要密码学——消息通过 TCP 连接传输，通道的可靠性由网络层保证。

BFT 协议必须使用密码学来防止消息伪造：

• 每条消息需要计算 MAC 或数字签名。
• 每条消息需要验证 MAC 或签名。
• 视图切换需要传输和验证大量的密码学证书。

MAC 的计算和验证相对快速（微秒级），但在高吞吐量场景下，每个请求需要计算和验证 O(n²) 个 MAC，总的密码学开销会变得显著。

5. 视图切换复杂度

VR/Raft 的视图切换 / Leader 选举相对简单：传输日志（VR）或日志元数据（Raft），选出最新的 Leader/Primary，开始新视图。消息数量 O(n)。

PBFT 的视图切换需要传输 prepared 证书（每个证书包含 O(n) 条签名消息），新 Primary 需要验证所有证书，计算新的 Pre-prepare 集合。消息大小 O(n²)，验证成本 O(n²)。

6. 实际中何时需要 BFT？

绝大多数情况下，CFT 就足够了。以下是需要 BFT 的场景：

场景一：开放式参与。 参与共识的节点不受单一组织控制，节点可能被恶意操控。典型例子：公链区块链。

场景二：多方不完全信任。 多个组织共同运行一个系统，各方之间存在利益冲突，不能完全信任对方的诚实性。典型例子：联盟链、跨组织的供应链系统。

场景三：高价值关键系统。 系统处理的数据或交易价值极高，即使是极小概率的拜占庭故障（如硬件故障导致的数据损坏）也不可接受。典型例子：航空航天系统中的飞行控制计算机（通常使用三模冗余 TMR，本质上也是 BFT）。

场景四：防御软件 Bug。 如果所有副本运行完全相同的代码，一个软件 Bug 可能导致所有副本表现出相同的拜占庭行为——这种情况下 BFT 也没用。但如果副本运行不同实现（异构冗余），BFT 可以容忍部分实现有 Bug。

在传统的数据中心场景中（单一组织、受控环境、统一软件），CFT 几乎总是正确的选择。额外的 BFT 开销（33% 更多节点、10-100 倍更多消息、密码学计算）很难被证明是值得的。

真实世界的拜占庭故障

在结束这一部分之前，值得列举一些真实世界中发生过的拜占庭故障案例，以说明这不是纯粹的理论问题：

1. Amazon S3 位翻转事件（2008 年）。 由于硬件故障导致的位翻转（bit flip），Amazon S3 存储的部分数据被静默损坏。校验和检测发现了问题，但在检测和修复之间的窗口期内，读取到损坏数据的客户端收到了错误的结果。这是经典的拜占庭故障——节点没有崩溃，但返回了错误的数据。

2. 网络设备固件 Bug。 2012 年，一次大规模的云服务故障被追溯到网络交换机的固件 Bug。某些特定的数据包模式会导致交换机转发到错误的端口，而不是丢弃数据包。从上层应用的角度看，消息被”修改”了——这是拜占庭行为。

3. CPU 勘误（Errata）。 Intel 的 CPU 定期发布勘误列表，记录在特定条件下可能产生错误计算结果的 Bug。虽然大多数勘误在实际工作负载中极少触发，但在高可靠性场景中不能忽视。

4. NTP 时钟跳变。 错误的 NTP 配置可能导致系统时钟大幅跳变。如果一个依赖时钟的节点突然认为当前时间比实际时间提前了一年，它可能做出违反协议假设的决策——这在效果上等同于拜占庭故障。

这些案例说明，拜占庭故障不需要恶意攻击者——硬件故障、软件 Bug 和配置错误都可能导致节点表现出拜占庭行为。CFT 协议对这些故障的防御能力取决于额外的检测机制（如校验和、断言检查），而 BFT 协议在协议层面就能容忍它们。

十、后 PBFT 时代：性能优化的方向

PBFT 是 BFT 领域的奠基性工作，但它的 O(n²) 消息复杂度严重限制了可扩展性。在 PBFT 之后，研究者提出了多种优化方向：

线性化消息复杂度

2018 年，Yin 等人提出了 HotStuff 协议，将 BFT 共识的消息复杂度从 O(n²) 降低到 O(n)。核心思想是引入一个”聚合签名”机制——Leader 收集到足够多的签名后，将它们聚合成一个 O(1) 大小的证书，然后广播给所有副本。这样每个阶段只需要 O(n) 条消息（Leader 广播 + 副本回复），而不是 O(n²)（全广播）。

但这引入了一个新的信任问题：Leader 成了信息汇聚点，如果 Leader 是拜占庭的呢？HotStuff 的解答是”乐观情况下信任 Leader，异常情况下通过视图切换惩罚 Leader”——和 PBFT 类似，但视图切换也是 O(n) 的。

减少通信轮次

PBFT 需要三轮通信（Pre-prepare → Prepare → Commit）。一些协议尝试减少轮次：

• SBFT（Scaled BFT, 2019）：在乐观情况下（所有节点正常）使用两轮通信，退化情况回退到三轮。
• Tendermint（2014）：也使用三轮（Propose → Prevote → Precommit），但在工程上做了大量优化，成为了第一个在生产环境中广泛部署的 BFT 协议。

分离安全性和活性

Thunderella（2018）提出了一个巧妙的观察：可以把 BFT 协议分为两条路径：

• 快速路径（Fast Path）：在乐观情况下（有一个诚实的 Leader，且 3/4 的节点在线），使用类似 CFT 的简单协议达成共识，延迟只有 1-2 轮。
• 慢速路径（Slow Path）：在悲观情况下（Leader 可能是拜占庭的，或网络有分区），回退到完整的 BFT 协议。

这个思想被后续的很多协议采纳——在大多数时间里使用高效的快速路径，只在检测到异常时切换到更安全但更慢的慢速路径。

PBFT 的历史地位

尽管 PBFT 在实际部署中面临诸多挑战，它的历史地位是无可争议的：

1. 首次证明 BFT 可以高效：PBFT 之前，BFT 协议被认为只是理论上的存在。PBFT 展示了 BFT 可以在只比 CFT 慢 3% 的条件下运行（虽然是在小规模下）。

2. 定义了 BFT 协议的基本结构：三阶段提交、视图切换、检查点、水位标记——这些概念被后续几乎所有的 BFT 协议继承或参考。

3. 启发了整个 BFT 优化方向：从 Zyzzyva 到 SBFT，从 Tendermint 到 HotStuff，都是在 PBFT 的框架上做优化。

4. 为区块链共识奠定基础：虽然比特币没有使用 PBFT，但联盟链和权益证明（PoS）链中广泛使用的共识协议（如 Tendermint、HotStuff/LibraBFT）都是 PBFT 的直接后代。

十一、总结

让我们用一张对比表收束全文：

从 VR 到 PBFT，最核心的变化是信任模型：从”收到的消息都是真的”到”收到的消息可能是假的”。这个变化迫使协议在结构上做出了根本性的调整——更多的副本、更多的通信轮次、更多的密码学验证、更复杂的视图切换。

但无论是 VR 还是 PBFT，它们的核心思想是一脉相承的：通过复制状态机、多数派投票和视图切换，在不可靠的分布式环境中提供可靠的服务。理解了 VR，你就理解了 Raft 的思想源头。理解了 PBFT，你就理解了区块链共识的理论基础。

延伸阅读：

• The Byzantine Generals Problem (Lamport et al., 1982) – 拜占庭将军问题的经典论文
• Viewstamped Replication Revisited (Liskov & Cowling, 2012) – VR 的现代重述，理解 VR 的最佳入口
• PBFT: Practical Byzantine Fault Tolerance (Castro & Liskov, 1999) – PBFT 原始论文
• HotStuff: BFT Consensus with Linearity and Responsiveness (Yin et al., 2019) – O(n) 消息复杂度的 BFT 协议

参考资料：

1. Oki, B. & Liskov, B. (1988). Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems. PODC ’88.
2. Liskov, B. & Cowling, J. (2012). Viewstamped Replication Revisited. MIT-CSAIL-TR-2012-021.
3. Castro, M. & Liskov, B. (1999). Practical Byzantine Fault Tolerance. OSDI ’99.
4. Lamport, L., Shostak, R. & Pease, M. (1982). The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems.
5. Ongaro, D. & Ousterhout, J. (2014). In Search of an Understandable Consensus Algorithm. USENIX ATC ’14.
6. Yin, M. et al. (2019). HotStuff: BFT Consensus with Linearity and Responsiveness. PODC ’19.
7. Kotla, R. et al. (2007). Zyzzyva: Speculative Byzantine Fault Tolerance. SOSP ’07.
8. Clement, A. et al. (2009). Making Byzantine Fault Tolerant Systems Tolerate Byzantine Faults. NSDI ’09.
9. Abraham, I. et al. (2019). SBFT: A Scalable and Decentralized Trust Infrastructure for Blockchains. DSN ’19.
10. Buchman, E. (2016). Tendermint: Byzantine Fault Tolerance in the Age of Blockchains. M.Sc. Thesis, University of Guelph.
11. Pass, R. & Shi, E. (2018). Thunderella: Blockchains with Optimistic Instant Confirmation. EUROCRYPT ’18.

上一篇：EPaxos：无主复制的共识协议 下一篇：HotStuff 与现代 BFT：从三轮到两轮的优化之路