Guide

Appearance

拜占庭将军问题与 PBFT 算法 ​

故事发生在公元 9 世纪。

拜占庭帝国（东罗马帝国）有一支军队，分布在多个城市，由多位将军指挥。

将军们需要达成共识：进攻还是撤退？

但问题是：这些将军中有叛徒。

叛徒会传递虚假消息，会阻止其他将军达成共识。

这就是著名的拜占庭将军问题——分布式系统领域最经典的思想实验之一。

拜占庭将军问题 ​

问题描述 ​

n 位将军，围攻一座城市
只有当多数将军同时进攻，才能获胜
将军们只能通过信使通信

问题：如何让所有忠诚的将军达成一致的行动计划？

约束：
1. 忠诚将军的行动是一致的
2. 叛徒可以发送任意消息
3. 叛徒可以干扰但不破坏算法

核心结论 ​

**如果存在 m 个叛徒，则至少需要 n >= 3m + 1 位将军，才能容忍 m 个恶意节点。

为什么是 3m + 1？

场景：m = 1（1 个叛徒），需要 n >= 4

将军：A（忠诚）、B（忠诚）、C（叛徒）、D（忠诚）

1. A 发消息给所有人：「进攻」
2. C（叛徒）给 A 发「进攻」，给 B、D 发「撤退」
3. A 收到：进攻=2，撤退=1 → 进攻
4. B 收到：进攻=1，撤退=2 → 撤退（与 A 不一致！）

问题：A 和 B 做出了不同的决定

解决：需要 4 个忠诚将军 + 1 个叛徒 = 5 位将军
这样：
- 消息比例：4 忠诚 vs 1 叛徒
- 多数派是忠诚的

为什么是 3m + 1 的数学推导 ​

假设系统能容忍 m 个恶意节点

总节点数 n，诚实节点 f，恶意节点 m

要达成共识，需要多数派确认：n/2 + 1

最坏情况：
- f 个诚实节点
- m 个恶意节点
- 共识需要 (f + m)/2 + 1 票

诚实节点必须占多数，才能保证共识正确：
f > m

同时，n = f + m

由 f > m 得：
f > (n - f)
2f > n
f > n/2

所以 n < 2f = 2(n - m)
n < 2n - 2m
2m < n
n > 2m

即：n >= 2m + 1

但这是保证活性的最低要求。为了保证安全性：
n >= 3m + 1

PBFT：实用拜占庭容错 ​

PBFT（Practical Byzantine Fault Tolerance）是由 Miguel Castro 和 Barbara Liskov 在 1999 年提出的算法。

目标：在异步网络中，实现能容忍恶意节点的共识。

三阶段协议 ​

PBFT 使用三阶段协议：Pre-prepare、Prepare、Commit

java
/**
 * PBFT 算法简化实现
 * 
 * 三阶段：Pre-prepare、Prepare、Commit
 */
public class PBFT {
    
    private final int f;                    // 能容忍的恶意节点数
    private final View view;                // 当前视图
    private final Map<String, PrePrepared> prePreparedLog = new HashMap<>();
    private final Map<String, Prepared> preparedLog = new HashMap<>();
    private final Map<String, Committed> committedLog = new HashMap<>();
    
    /**
     * 客户端请求
     */
    public void handleRequest(ClientRequest request) {
        // 1. 主节点（Primary）验证请求
        if (!isPrimary()) {
            throw new NotPrimaryException();
        }
        
        // 2. 广播 Pre-Prepare 消息
        broadcastPrePrepare(request);
    }
    
    /**
     * Phase 1: Pre-Prepare
     * 
     * 主节点：
     * - 为请求分配序列号 n
     * - 签名 Pre-Prepare 消息
     * - 发送给所有备份节点
     */
    public void broadcastPrePrepare(ClientRequest request) {
        long viewNumber = view.getViewNumber();
        long sequenceNumber = getNextSequenceNumber();
        
        PrePrepareMessage message = new PrePrepareMessage();
        message.setView(viewNumber);
        message.setSequence(sequenceNumber);
        message.setDigest(hash(request.getOperation()));
        message.setRequest(request);
        
        // 签名并广播
        signAndBroadcast(message);
    }
    
    /**
     * 备份节点处理 Pre-Prepare
     */
    public void onReceivePrePrepare(PrePrepareMessage message) {
        // 验证消息
        if (!verifyMessage(message)) {
            return;
        }
        
        // 检查视图号和序列号
        if (message.getView() != view.getViewNumber()) {
            return;
        }
        if (!isValidSequenceNumber(message.getSequence())) {
            return;
        }
        
        // 检查请求摘要
        if (!checkDigest(message.getDigest())) {
            return;
        }
        
        // 记录 Pre-Prepared 状态
        prePreparedLog.put(getKey(message), new PrePrepared(message));
        
        // 广播 Prepare 消息
        broadcastPrepare(message);
    }
    
    /**
     * Phase 2: Prepare
     * 
     * 所有节点：
     * - 收到 Pre-Prepare 后
     * - 广播 Prepare 消息
     * - 等待 2f 个 Prepare 确认
     * - 进入 Prepared 状态
     */
    public void broadcastPrepare(PrePrepareMessage prePrepare) {
        PrepareMessage message = new PrepareMessage();
        message.setView(prePrepare.getView());
        message.setSequence(prePrepare.getSequence());
        message.setDigest(prePrepare.getDigest());
        message.setNodeId(nodeId);
        
        // 签名并广播
        signAndBroadcast(message);
    }
    
    /**
     * 检查是否收到足够多的 Prepare
     */
    public boolean checkPrepareMessages(PrePrepareMessage prePrepare) {
        String key = getKey(prePrepare);
        Prepared prepared = preparedLog.get(key);
        
        // 需要收到 2f 个 Prepare 消息（包括自己的）
        // f 个恶意节点 + f 个诚实节点 + 自己 = 2f + 1
        return prepared.getCount() >= 2 * f;
    }
    
    /**
     * Phase 3: Commit
     * 
     * 进入 Prepared 状态后：
     * - 广播 Commit 消息
     * - 等待 2f + 1 个 Commit 确认
     * - 执行请求
     */
    public void broadcastCommit(PrePrepareMessage prePrepare) {
        CommitMessage message = new CommitMessage();
        message.setView(prePrepare.getView());
        message.setSequence(prePrepare.getSequence());
        message.setDigest(prePrepare.getDigest());
        message.setNodeId(nodeId);
        
        signAndBroadcast(message);
    }
    
    /**
     * 检查是否收到足够多的 Commit
     */
    public boolean checkCommitMessages(PrePrepareMessage prePrepare) {
        String key = getKey(prePrepare);
        Committed committed = committedLog.get(key);
        
        // 需要收到 2f + 1 个 Commit 消息
        return committed.getCount() >= 2 * f + 1;
    }
    
    /**
     * 执行请求并返回结果
     */
    public byte[] executeRequest(ClientRequest request) {
        // 状态机更新
        byte[] result = stateMachine.execute(request.getOperation());
        
        // 返回结果给客户端
        return result;
    }
}

View Change 机制 ​

当主节点故障时，需要切换视图：

java
/**
 * View Change：当主节点故障时触发
 */
public class ViewChange {
    
    /**
     * 触发条件：节点等待 Pre-Prepare 超时
     */
    public void onTimeout() {
        viewNumber++;
        
        // 1. 停止处理当前视图的消息
        stopProcessing();
        
        // 2. 收集 Checkpoint 证明
        List<CheckpointMessage> checkpoints = collectCheckpoints();
        
        // 3. 构造 View-Change 消息
        ViewChangeMessage message = new ViewChangeMessage();
        message.setView(viewNumber);
        message.setNodeId(nodeId);
        message.setCheckpoints(checkpoints);
        message.setPreparedCertificates(preparedCertificates);
        
        // 4. 发送给新主节点
        sendToPrimary(message);
    }
    
    /**
     * 新主节点处理 View-Change
     */
    public void onReceiveViewChange(ViewChangeMessage message) {
        // 收集 2f 个 View-Change 消息
        viewChangeMessages.add(message);
        
        if (viewChangeMessages.size() >= 2 * f + 1) {
            // 启动新视图
            startNewView(message.getView());
        }
    }
    
    /**
     * 启动新视图
     */
    public void startNewView(long newViewNumber) {
        view.setViewNumber(newViewNumber);
        
        // 1. 从 View-Change 消息中恢复状态
        recoverState();
        
        // 2. 重新广播缺失的消息
        rebroadcastMissingMessages();
        
        // 3. 开始处理新视图的消息
        startProcessing();
    }
}

PBFT vs Raft ​

维度PBFTRaft
容错类型拜占庭故障（恶意节点）崩溃故障（节点宕机）
节点数量n >= 3m + 1奇数节点，多数派即可
通信复杂度O(n²)O(n)
性能较低高
实现难度高中等
适用场景联盟链、敏感系统通用分布式系统

PBFT 的局限 ​

1. 通信复杂度高
   - 每条消息需要 O(n²) 次通信
   - 不适合大规模节点

2. 节点数量受限
   - 节点越多，性能越差
   - 通常只支持几十个节点

3. 同步假设
   - PBFT 假设网络不会无限延迟
   - 如果网络真的异步，性能无法保证

区块链中的 BFT 变体 ​

区块链继承了 BFT 的思想，但做了大量改进：

PoW（工作量证明） ​

比特币的共识算法

特点：
- 不需要事先知道节点
- 任何人都可以加入
- 通过算力竞争达成共识

优点：
- 完全去中心化
- 无需信任任何节点

缺点：
- 耗能巨大
- 确认时间长

PoS（权益证明） ​

以太坊 2.0 的共识算法

特点：
- 根据持币量选择验证者
- 验证者质押代币作为保证金
- 作恶会被惩罚（罚没质押）

优点：
- 能耗低
- 确认时间短

缺点：
- 富者愈富
- 可能存在 Nothing at Stake 问题

BFT 变体在联盟链中的应用 ​

Hyperledger Fabric、PBFT、Raft 等

特点：
- 节点数量有限且已知
- 需要许可才能加入
- 性能高，安全性好

适用场景：
- 企业联盟链
- 私有链
- 需要高性能和确定性的场景

面试追问方向 ​

Q1：PBFT 为什么通信复杂度高？ ​

因为 PBFT 需要三个阶段的确认（Pre-prepare、Prepare、Commit），每个阶段都需要节点之间相互通信：

Pre-prepare：主节点 → 所有备份节点
Prepare：所有节点 → 所有节点（n * (n-1) 次）
Commit：所有节点 → 所有节点（n * (n-1) 次）

总复杂度：O(n²)

Q2：PBFT 适合什么场景？ ​

  1. 联盟链：节点数量有限，性能要求高
  2. 敏感系统：需要容忍恶意节点（如区块链）
  3. 私有链：节点可信但需要容错

不适合：

  • 公有链（节点太多）
  • 追求极致性能（通信开销大）

Q3：Raft 能容忍恶意节点吗？ ​

不能。Raft 只能容忍节点崩溃（Crash Fault），不能容忍恶意节点（Byzantine Fault）。

如果 Raft 节点发送虚假消息，会导致系统不一致。

总结 ​

拜占庭将军问题和 PBFT 算法揭示了分布式系统的深层挑战：

  1. 拜占庭将军问题：n >= 3m + 1 才能容忍 m 个恶意节点
  2. PBFT：三阶段协议实现拜占庭容错
  3. 局限性：O(n²) 通信复杂度，节点数量受限
  4. 工程选择：根据场景选择 PBFT、Raft 或区块链共识

"拜占庭将军问题教会我们：在不可信的环境中达成共识，需要付出代价。PBFT 用通信复杂度换取安全性，这是一笔值得的交易。"

基于 VitePress 构建

Copyright © 2025-2026 Guide