分布式算法 #08：Byzantine 容错（BFT/PBFT）

拜占庭容错（Byzantine Fault Tolerance）解决的是更严酷的故障模型：节点不仅可以崩溃，还可以发送错误、矛盾、甚至恶意构造的消息。本文深入 PBFT 的三阶段协议伪代码，分析 7 种拜占庭攻击异常，并证明为什么需要至少 3f+1 个节点才能容忍 f 个拜占庭节点。

相关文章：Paxos 算法 · Raft 共识算法 · Quorum 与 NWR 模型

目录

拜占庭故障 vs 崩溃故障

崩溃故障（Crash Fault）：
  节点要么正常工作，要么停止响应（宕机）
  不会发送错误消息
  Raft / Paxos 处理的故障类型

拜占庭故障（Byzantine Fault）：
  节点可以：
    发送随机错误数据
    向不同节点发送不同消息（矛盾消息）
    选择性不响应某些节点
    串通（多个拜占庭节点协同攻击）
    伪装成其他节点（无签名方案下）

现实中的拜占庭节点：
  软件 bug 导致的错误输出（非恶意但有害）
  被攻击者控制的节点（恶意）
  硬件故障导致的错误计算（如宇宙射线导致位翻转）
  区块链网络中的矿工攻击

关键区别：
  处理崩溃故障只需 Quorum > N/2（f < N/2）
  处理拜占庭故障需要 Quorum > 2N/3（f < N/3）
  代价：消息复杂度从 O(N) 增至 O(N²)

3f+1 节点的必要性证明

为什么 3f 个节点不够容忍 f 个拜占庭节点？

反证法：假设 N=3f 个节点可以容忍 f 个拜占庭节点

场景构造：
  将 3f 个节点分为三组，每组 f 个：
    组1 {F1...Ff}：拜占庭节点（故意发送错误消息）
    组2 {S1...Sf}：正常节点，但被网络分区隔离（对组3不可见）
    组3 {S(f+1)...S(2f)}：正常节点，但被网络分区隔离（对组2不可见）

    组1的拜占庭节点向组2声称值为 A，向组3声称值为 B

此时：
  组2 的节点看到：f 个拜占庭节点说A，f 个组2节点
  组3 的节点看到：f 个拜占庭节点说B，f 个组3节点

  对于组2，无法区分：
    "组3 故障+组1 诚实" 还是 "组1 拜占庭+组3 分区"
  → 组2 可能选定值 A

  对于组3，同理可能选定值 B

  → 系统选出了两个不同的值 A 和 B，违反 Safety！

结论：
  N=3f 时，无法区分"拜占庭节点"和"分区节点"
  必须 N >= 3f+1，才能保证两个 Quorum（各 2f+1）必有至少 1 个正确节点交集

Quorum 交集保证：

N=3f+1，每次决策需要 2f+1 个节点的 Quorum

两个 Quorum Q1 和 Q2 的交集大小：
  |Q1 ∩ Q2| >= |Q1| + |Q2| - N
             = (2f+1) + (2f+1) - (3f+1)
             = f+1

交集中最多有 f 个拜占庭节点
→ 交集中至少有 1 个正确节点

这个正确节点的 "见证" 保证两次决策的一致性 ✅

PBFT 协议

PBFT 中的角色：

Primary（主节点）：接收客户端请求，驱动共识
Replica（副本）：验证并执行请求（共 N=3f+1 个节点，Primary 是其中之一）
Client：发送请求，等待 f+1 个一致的响应

阶段 0：请求接收

Client → Primary:
  request = {
    op:        客户端操作（如"转账100元"）
    timestamp: T    // 防重放
    client_id: c
    sig:       sign(op+T+c, client_privkey)  // 客户端签名
  }

Primary 验证签名后进入 Pre-prepare 阶段

阶段 1：Pre-prepare

Primary → All Replicas:
  pre_prepare = {
    view:      v       // 当前视图编号（类似 Raft 的 term）
    seq:       n       // 序列号（单调递增，全局有序）
    digest:    d(m)    // 请求 m 的哈希摘要
    sig:       sign(v+n+d, primary_privkey)
  }
  // 注意：Primary 将原始请求 m 单独广播或 piggyback

Replica on receive Pre-prepare(v, n, d, m):
  验证：
    1. primary 签名有效
    2. v == currentView
    3. n 在合法范围内（水印 [h, H] 内，防止序列号溢出）
    4. d == hash(m)（摘要匹配）
    5. 未接受过相同 (v, n) 但不同 d 的 pre-prepare
  
  if 验证通过:
    记录 pre-prepare 状态
    广播 Prepare 消息

阶段 2：Prepare

Replica_i → All Replicas:
  prepare = {
    view:   v
    seq:    n
    digest: d(m)
    node:   i
    sig:    sign(v+n+d+i, replica_i_privkey)
  }

Replica on receive Prepare(v, n, d, j):
  验证签名和字段
  记录 prepare 消息

// Prepared 状态：当节点收集到 2f 个来自不同节点的有效 Prepare
// （加上自己的 Pre-prepare，共 2f+1 个）
isPrepared(v, n, d) = 
  hasPrePrepare(v, n, d) AND
  count(validPrepare(v, n, d)) >= 2f

阶段 3：Commit

// 节点进入 Prepared 状态后，广播 Commit

Replica_i → All Replicas:
  commit = {
    view:   v
    seq:    n
    digest: d(m)
    node:   i
    sig:    sign(v+n+d+i, replica_i_privkey)
  }

// Committed 状态：收到 2f+1 个有效 Commit
isCommitLocal(v, n, d) =
  isPrepared(v, n, d) AND
  count(validCommit(v, n, d)) >= 2f+1

if isCommitLocal(v, n, d):
  按序列号 n 的顺序执行操作（如果 n-1 已执行）
  reply = {
    view:      v
    timestamp: T（来自请求）
    client_id: c
    node:      i
    result:    执行结果
    sig:       sign(result, replica_privkey)
  }
  发送 Reply 给 Client

// Client 等待 f+1 个来自不同 Replica 的一致 Reply
// f+1 保证至少有 1 个正确节点的回复

7 种拜占庭异常分析

异常 1：拜占庭 Primary 发送不一致的 Pre-prepare

攻击：Primary 向不同 Replica 发送相同序列号 n 但不同摘要 d1≠d2 的 Pre-prepare

防御机制：
  Prepare 阶段，每个 Replica 广播 Prepare(v, n, d) 给所有人
  正确节点只 Prepare 自己收到的摘要

  正确节点 R1 发 Prepare(v, n, d1)
  正确节点 R2 发 Prepare(v, n, d2)

  要达到 Prepared(d1)，需要 2f+1 个 Prepare(v,n,d1)
    最多 f 个拜占庭节点发 d1，f 个正确节点发 d1
    总计 2f < 2f+1 → 无法达到 Prepared ✅

  d1 和 d2 都无法同时达到 Prepared → 共识无法推进
  正确节点检测到异常 → 触发视图变更（替换 Primary）

异常 2：拜占庭节点选择性不响应

攻击：拜占庭节点 B1 收到某节点 Ri 的请求后，故意不回复

影响：
  Ri 等待 B1 的 Prepare/Commit 超时
  但 Ri 只需要 2f+1 个响应（不需要 B1）
  剩余 2f 个正确节点 + 0 个拜占庭节点 = 2f < 2f+1？

分析：
  N=3f+1，f 个拜占庭节点，2f+1 个正确节点
  即使所有 f 个拜占庭节点都不响应
  仍有 2f+1 个正确节点的响应
  2f+1 >= 2f+1 → 协议正常推进 ✅

异常 3：拜占庭节点发送错误的 Prepare

攻击：拜占庭节点发送带有错误摘要或错误视图号的 Prepare 消息

防御：
  每条消息都有发送者的数字签名
  正确节点验证签名后才处理消息
  伪造签名 = 计算上不可行（在公钥密码体系下）
  → 错误消息被识别并丢弃 ✅

异常 4：f 个拜占庭节点串通

攻击：f 个拜占庭节点协调行动，统一对正确节点谎报状态

最坏情况分析：
  N=3f+1，f 个拜占庭节点全部串通撒谎
  Quorum = 2f+1 个，其中至多 f 个是拜占庭节点
  → 至少 f+1 个正确节点必须同意

  如果正确节点不同意（看到不同的 Pre-prepare）
  → 无法形成 Quorum → 共识阻塞（牺牲 Liveness）
  但不会选出错误的值（Safety 保证）✅

异常 5：Primary 故意延迟处理某些请求

攻击：拜占庭 Primary 按偏好对请求排序，故意延迟某类请求

影响：
  某些客户端请求长时间无响应
  但 Primary 无法阻止请求最终被执行（只要 Primary 被替换）

防御：
  Client 设置请求超时，超时后广播请求给所有 Replica
  Replica 收到未被处理的请求后：
    等待合理时间（timer）
    如果 Primary 仍未发出 Pre-prepare
    → 触发视图变更，替换拜占庭 Primary

异常 6：拜占庭节点重放旧消息

攻击：重放已执行的旧请求（序列号 n，视图 v）

防御：
  每条请求携带客户端时间戳 T
  节点记录每个客户端最后执行的时间戳 lastTimestamp[c]
  if request.timestamp <= lastTimestamp[c]: 拒绝（重放攻击）✅
  
  同时，节点记录已执行的 (v, n) 对
  重复的 (v, n) 请求直接返回缓存的 Reply ✅

异常 7：拜占庭节点在视图变更时提供错误的状态

攻击：视图变更时，拜占庭节点谎称某个序列号 n 已经 Prepared
     导致新 Primary 使用错误的值

防御：
  视图变更消息（View Change）需要包含节点的 Prepared 证明
  证明 = 2f+1 个有效的 Prepare 消息（可验证的签名集合）
  
  拜占庭节点无法伪造 2f+1 个签名（其中包含正确节点的签名）
  新 Primary 只接受有有效证明的 Prepared 状态 ✅

视图变更（View Change）

触发条件：
  正确节点认为 Primary 是拜占庭节点（超时/错误行为）

触发视图变更：

Replica_i → All Replicas:
  view_change = {
    new_view:  v+1
    seq:       n（当前最高稳定检查点序列号）
    C:         检查点证明（2f+1 个稳定检查点消息）
    P:         所有在 [n, high_seq] 范围内 Prepared 的请求证明
    node:      i
    sig:       sign(...)
  }

新 Primary（节点 (v+1) mod N）收到 2f+1 个 View Change 消息后：

  new_view_msg = {
    new_view: v+1
    V: 收到的 2f+1 个 View Change 消息集合
    O: 新视图中需要重新 Pre-prepare 的消息集合
       （从所有 View Change 消息的 P 集合中推导）
  }
  广播 New View 消息

  // 对于每个在任何 View Change 消息中出现的 Prepared(n, d)
  // 新视图必须包含 Pre-prepare(v+1, n, d)
  // 防止已 Prepared 的请求被丢弃（Safety）

PBFT 的性能与局限

消息复杂度：
  Pre-prepare 阶段：1 条（Primary → All）
  Prepare 阶段：N × N 条（每个节点广播给所有节点）
  Commit 阶段：N × N 条
  总计：O(N²) 条消息

延迟：
  3 轮 RPC（Pre-prepare + Prepare + Commit）
  每轮需要等待 2f+1 个响应

N=100：
  消息数 ≈ 10000 条/请求
  实测 TPS ≈ 数千（局域网）

N=1000：
  消息数 ≈ 100万条/请求
  实际不可用

结论：PBFT 适合小规模（N < 20）、高信任的联盟链场景
     不适合公链（Bitcoin 万级节点）

现代 BFT 变体

HotStuff 的核心优化：

PBFT 的 O(N²) 原因：
  每个节点广播 Prepare/Commit 给所有节点
  所有节点直接相互通信

HotStuff 的解法：
  Leader 作为中枢，收集投票并聚合为门限签名
  其他节点只与 Leader 通信（而非全互联）
  消息数 = O(N)（每轮只有 N 条消息到 Leader + N 条 Leader 广播）

代价：
  引入门限签名（BLS Threshold Signature）
  Leader 成为瓶颈（但 Leader 宕机只触发视图变更，不影响 Safety）

参考资料

• Castro, M. & Liskov, B. (1999). Practical Byzantine Fault Tolerance
• Yin, M. et al. (2019). HotStuff: BFT Consensus with Linearity and Responsiveness
• 《Designing Data-Intensive Applications》Ch.8 — Byzantine Faults
• Lamport, L. et al. (1982). The Byzantine Generals Problem