PBFT 实用拜占庭容错算法

PBFT 将拜占庭容错算法从指数级复杂度降到多项式级，使得拜占庭容错在实际系统中变得可行。它的核心是**三阶段协议 + 视图变更**。

背景

PBFT（Practical Byzantine Fault Tolerance）由 Miguel Castro 和 Barbara Liskov 于 1999 年在 OSDI'99 提出。Liskov 正是里氏替换原则（LSP）的提出者、2008 年图灵奖得主。

早期的拜占庭容错算法或基于同步系统假设，或因性能太低无法实用。PBFT 的贡献：

1. 首次提出在**异步网络环境**下使用状态机副本复制协议
2. 多种优化使性能提升一个数量级以上
3. 在 NFS 系统上验证，仅比标准 NFS 慢 3%

系统模型

• 网络模型：异步分布式，消息可能丢失、延迟、重复、乱序
• 节点失效：独立发生（不同代码/OS/管理员）
• 加密假设：大魔王算力有限，无法破解签名/哈希
• 容错上限：\(f\) 个失效节点需要至少 \(3f+1\) 个副本

容错公式推导：同 \(n-f\) 个节点通讯后必须做正确判断。\(f\) 个正常节点可能不发响应，\(f\) 个发响应的可能是失效节点。需要 \(n-2f > f\)，即 \(n > 3f\)。

三阶段协议（核心主线）

角色设定

• 视图（View）：连续编号的整数，主节点 \(p = v \bmod |R|\)
• 主节点（Primary）：负责排序请求
• 备份节点（Backups）：验证并执行

阶段流程

客户端 → 主节点 → 所有副本 → 客户端
        ↓
   三阶段协议：
   1. Pre-Prepare（预准备）
   2. Prepare（准备）  
   3. Commit（确认）

Pre-Prepare：主节点分配序列号 \(n\)，广播 <<PRE-PREPARE,v,n,d>,m>

Prepare：备份节点验证后广播 <PREPARE,v,n,d,i>，收集到 \(2f\) 个一致消息后进入下一阶段

Commit：当 \(prepared(m,v,n,i)\) 为真，广播 <COMMIT,v,n,D(m),i>，收集到 \(2f+1\) 个确认后执行请求

阶段设计原理

客户端确认

客户端等待 \(f+1\) 个不同副本返回相同结果，即可信任——因为失效节点不超过 \(f\) 个。

视图变更（View Change）

当主节点失效（超时未广播），备份节点触发视图变更：

1. 广播 <VIEW-CHANGE,v+1,...> 给所有副本
2. 新主节点收集 \(2f+1\) 个视图变更消息
3. 广播 <NEW-VIEW> 进入新视图

检查点（Checkpoint）与垃圾回收

每执行 \(k\) 个请求（如 100）生成一个检查点，\(2f+1\) 个副本确认后成为**稳定检查点**，之前的日志可安全删除。同时更新水线 \([h, H]\)，防止序号空间被恶意消耗。

关键数字速记

延伸阅读

• PBFT 共识算法（博客原文）
• 分布式系统核心问题
• PBFT 论文 (OSDI'99)

维护人：yiiewang · 最后更新：2026-07-01