拜占庭将军问题 — 节点能撒谎时怎么达成一致

是什么

拜占庭将军问题研究的是：一群节点要联合做一个决定，但其中混着会撒谎、会伪造消息、会串谋的叛徒，剩下的忠实节点能不能仍然达成一致？

日常类比：几位将军围攻一座城，必须要么全攻、要么全撤——半攻半撤就全军覆没。他们靠信使互相通信，但有些将军是叛徒，可以给 A 说”攻”、给 B 说”撤”，还能伪造司令的命令。问题：忠实将军之间能不能可靠地达成一致行动？

论文给出一个让人意外的硬边界——只要叛徒比例超过三分之一，光靠口头消息（无签名），无论如何都不可能达成一致。

为什么重要

不理解拜占庭容错（BFT），下面这些事都没法解释：

为什么比特币要 6 个区块确认、以太坊 PoS 要超过 2/3 验证者签名——3f+1 的影子
为什么 PBFT、Tendermint、HotStuff 这些共识协议都要凑够 2f+1 个签名
为什么 etcd / Zookeeper 用 Raft（只防崩溃）而 Hyperledger / Cosmos 用 BFT（防作恶）
为什么”3 个节点容 1 个故障”在 Paxos 里成立、在拜占庭场景里不成立

这是把分布式系统从『节点会死』扩展到『节点会主动作恶』的开山论文。

核心要点

故障模型升级

传统分布式假设崩溃故障（fail-stop）——节点要么正常工作要么直接死掉，不会乱发消息。拜占庭故障允许节点做任何事：

给 A 发”攻”、给 B 发”撤”
伪造其他节点的签名
与其他叛徒串谋
只对部分节点应答（选择性沉默）

这覆盖恶意攻击者，也覆盖硬件 bit-flip、软件 bug 这些”非恶意但行为不符协议”的情况。

3f+1 边界（口头消息）

定理：用普通消息（接收方无法证明消息真伪），要让 n 个节点在 f 个叛徒下达成一致，必须 n ≥ 3f+1。

最有名的反例是 n=3、f=1 不可行：

       司令
       /  \
      /    \
    副A ── 副B

情景 1：司令是叛徒，给副 A 说”攻”、给副 B 说”撤”。副 A 转告 B”司令说攻”，副 B 收到的是 (司令: 撤, A 转告: 攻)。
情景 2：司令忠实说”攻”，副 A 是叛徒转告 B”司令说撤”。副 B 收到的是 (司令: 攻, A 转告: 撤)。

两种情景下 B 看到的消息集合完全对称——它无法分辨自己该攻还是该撤。一致性破产。

OM(m)：递归口头消息算法

把消息递归转发 m 轮，每轮新增一层”我从谁那里听到的”，最后用多数表决。当 n ≥ 3m+1 且最多 m 个叛徒时正确。

代价：通信量 O(n^(m+1))，工程上几乎不可用。这是为什么 1982 到 1999（PBFT）之间 BFT 一直停留在理论。

SM(m)：签名消息算法

如果消息不可伪造（数字签名），边界放宽到 n ≥ f+2。叛徒签的话立刻被任何人识破，所以叛徒只能”沉默”或”重发别人的签名”，破坏力大幅下降。

这条结论是后来所有签名共识（Bitcoin、PBFT、Tendermint）的理论基础。

实践案例

案例 1：n=4、f=1 怎么走过来

司令 → A、B、C：「攻」
A、B、C 互相转告自己收到的命令
最终每个忠实节点持有 (司令的话, A 转告, B 转告, C 转告)
取多数 → 一致

哪怕司令是叛徒（给 4 个不同的话），3 个忠实副官互相一对账就能识破。

案例 2：区块链里的 3f+1

Tendermint / Cosmos / 早期以太坊 PoS：

总验证者权益 = N
容忍恶意权益 = f < N/3
提交一个区块需要 ≥ 2f+1 = 2N/3+1 的签名

这就是论文 1982 边界40 年后直接落到生产共识协议。

案例 3：硬件场景

航天器多 CPU 表决（NASA SIFT、Boeing 777 飞控）：CPU 不会”作恶”，但宇宙射线 bit-flip 后输出乱七八糟，行为模型等价于拜占庭。这也是 Lamport 当年写论文的真实背景之一。

踩过的坑

3f+1 是必要条件不是充分条件：还要至少 m≥f 轮通信。一轮搞定是不可能的。
签名不是免费：SM(m) 假设签名不可伪造，现实里要密钥分发、撤销、性能成本——这是 PBFT 之前迟迟没落地的原因之一。
拜占庭 ≠ 恶意：很多人把拜占庭节点等同于黑客，其实包括硬件 bug、内存损坏、软件版本不一致这种”无意作恶”。
同步 vs 异步：原论文假设同步网络（消息在已知时限内到达）。1985 FLP 定理证明纯异步下连崩溃容错都做不到，更别说拜占庭——所以现实协议要么部分同步要么用随机化。

适用 vs 不适用场景

适用：

多方互不信任的协作（区块链、跨组织联盟链）
高安全要求的关键系统（航天、金融清算、军用）
硬件容错（多副本表决，防 bit-flip）

不适用：

数据中心内部、节点同属一个组织——用 Raft / Paxos 就够，崩溃容错足以
性能优先、容错弱要求的场景——BFT 通信开销远高于 CFT
节点数极少（< 4）——3f+1 边界让小集群无法容错

历史小故事（可跳过）

1980 年：Pease、Shostak、Lamport 发表 Reaching Agreement in the Presence of Faults，给出 3f+1 边界的最初证明。
1982 年：三人重写为本文，加入”拜占庭将军”这个比喻。Lamport 后来回忆：取这个名字是为了避开当时另一个研究小组用的”中国将军”——他不想让论文牵涉冷战时期的外交敏感词。
1985 年：Fischer-Lynch-Paterson（FLP）定理证明纯异步下连崩溃容错都不可能——把”必须做某种同步假设”钉死。
1999 年：Castro-Liskov 的 PBFT 把 BFT 从 O(n^(m+1)) 降到 O(n²)，BFT 第一次有了实用版本。
2008 年：中本聪用 PoW + 经济激励绕开 BFT 的通信复杂度，让公链规模拜占庭成为可能。

学到什么

故障模型决定一切：先想清楚节点会怎么坏，再选协议。Raft 防崩溃，PBFT 防作恶，混了就出事。
三分之一是个魔数：n ≥ 3f+1 是无签名 BFT 的物理上限，不是算法 trick——它由”叛徒角色对称无法区分”的几何论证给出。
签名是降复杂度的关键：不可伪造把”叛徒能撒任意谎”压成”叛徒只能沉默或重放”，边界从 3f+1 降到 f+2。
理论 → 工程隔几十年：1982 边界证出来 → 1999 PBFT 第一次工程化 → 2014 区块链工业落地。每一步隔约 15 年。

关联

lamport-1978 —— 同作者，逻辑时钟与因果序，BFT 协议的时序前置
paxos-1998 —— 崩溃容错共识，与 BFT 形成对照（n ≥ 2f+1 vs 3f+1）
raft —— Paxos 的工程化版本，同样只防崩溃
bitcoin —— 用 PoW + 激励机制绕过 BFT 通信复杂度的拜占庭共识
chandy-lamport-1985 —— 同作者，分布式快照算法

反向链接

bitcoin —— Bitcoin 白皮书
chandy-lamport-1985 —— Chandy-Lamport 1985 — 分布式系统不停机也能拍一张全家福
farsite-2002 —— Farsite — 把一群不可信桌面 PC 拼成一台可信文件服务器
ironfleet-2015 —— IronFleet — 把分布式协议证到一行 bug 都没有
kairouz-advances-fl-2019 —— 联邦学习综述 — 60+ 作者合写的联邦学习百科与 58 道开放题
lamport-1978 —— Lamport 1978 — 分布式系统里没有”绝对的同时”
mills-ntp-1991 —— NTP 1991 — 用四个时间戳和一棵服务器树，让全互联网的钟差几毫秒
paxos-1998 —— Paxos 1998 — 古希腊议会寓言里藏的共识协议
raft —— Raft — 易理解的共识算法
saltzer-1984-e2e —— End-to-End Arguments — 把功能尽量推到端上做