The Byzantine Generals Problem（拜占庭将军问题）

一句话

这篇论文把「分布式系统中有节点会任意作恶（撒谎、发矛盾消息、伪装故障）时如何达成一致」抽象成一则将军围城的寓言，证明了两个奠基性结论：用普通口信（可被篡改转述）时，要容忍 m 个叛徒至少需要 3m+1 个将军（叛徒必须少于三分之一），且给出递归算法 OM(m)；而一旦引入不可伪造的数字签名，则任意多叛徒都可容忍。它定义了「拜占庭故障」这一最强故障模型，是拜占庭容错（BFT）与后来一切区块链共识的思想原点。

Glossary · 术语表

坐标

作者 Leslie Lamport、Robert Shostak、Marshall Pease 来自 SRI International，论文 1982 年发表于 ACM TOPLAS。它是同一批人 1980 年更形式化的论文《Reaching Agreement in the Presence of Faults》的寓言化重述——正是这个「拜占庭将军」的说法让问题家喻户晓。它上承 Lamport 1978 年《Time, Clocks》对分布式事件顺序的思考，下启整个拜占庭容错（BFT）研究：1999 年的 PBFT 让它第一次跑得起来，2008 年的比特币则在开放网络里给了它一个概率化答案。

问题与动机

可靠系统常用「多台冗余、投票取多数」来容错。但这背后藏着一个被忽视的假设：坏掉的部件只会「不工作」，不会「主动使坏」。现实并非如此——一个出故障的传感器可能给不同的询问者报不同的读数，一块坏内存可能间歇性地翻转再翻转回来，一个被攻破的节点会存心发送精心构造的假消息。这类「任意行为、甚至恶意协同」的故障，作者称之为拜占庭故障。

难点在于：诚实节点无法仅凭自己收到的消息，区分「对方在故障 / 撒谎」还是「消息源头本身有问题」。更糟的是，一个叛徒可以对不同的人说不同的话，制造「你看到的世界」和「我看到的世界」不一致，从而让诚实者各自做出不同决定。问题被精炼成两条要求（作者称之为交互一致性）：

• IC1：所有忠诚的将军最终服从同一个命令。
• IC2：如果发令的司令是忠诚的，那么每个忠诚的将军都服从司令实际下的那个命令。

把「将军」换成「计算机 / 副本」，「司令下令」换成「某节点广播一个值」，这就是分布式系统里最硬核的一致性问题。

核心思想 / 方法

寓言：把恶意故障讲成一个人人能懂的故事

论文最大的贡献之一其实是这个比喻本身。把抽象的「节点任意作恶」讲成「围城的将军里有叛徒」，一下让整个领域有了共同语言。为聚焦，作者把「人人平等地商量」化简为一个更基本的子问题：一位司令（commander）向若干副官（lieutenant）下达一个命令，司令或某些副官可能是叛徒。只要能解决这个「单向下令」的版本，把每个将军轮流当一次司令，就能拼出所有人两两一致。

口信版：为什么必须 3m+1 个将军

先看口信（oral message）模型——消息能被正确送达、收信人知道是谁发的、缺失的消息可被察觉，但叛徒可以任意谎报自己「听到了什么」（转述时随口改内容，无从追责）。在这个模型下，作者证明了一个尖锐的下界：要容忍 m 个叛徒，将军总数必须 ≥ 3m+1，也就是叛徒必须少于三分之一。

为什么？看最小的反例：三个将军、一个叛徒，无解。诚实的副官 L1 手里只有两条信息：司令直接下的令，和另一位副官 L2 转告的「司令对我说的令」。当这两条矛盾时，L1 面对两个在他看来完全无法区分的世界——

在场景 A 里 IC2 要求 L1 服从司令的真令「进攻」；但场景 B 里 L1 收到的东西完全一样，若他仍「进攻」，而对称地看，那个忠诚的 L2 收到的是「撤退」并也照办，两位忠诚副官就动作相反，违反 IC1。无论 L1 怎么定规矩，总有一种场景让他做错。再用一个「分组归约」论证把它推广：假如 3m 个将军能容忍 m 个叛徒，就能把将军们三等分、每组用一个「超级将军」模拟，倒推出「三将军容忍一叛徒」的解——而后者已证不存在，矛盾。于是 n ≥ 3m+1 是硬下界。

OM(m)：递归转述 + 多数表决

下界之外，作者给出达到它的算法 OM(m)（Oral Message，口信算法），思路是递归地互相转述、层层做多数表决：

• OM(0)（没有叛徒可容忍时）：司令把命令发给每个副官，副官照单接受。
• OM(m)：司令把命令发给 n−1 个副官；然后每个副官把「自己收到的命令」当作新命令，扮演司令，对其余副官跑一次 OM(m−1)；最后每个副官把「直接从原司令收到的」和「经由其他每个副官转来的」共 n−1 个值，取多数（majority）作为最终决定。

直觉是：一条命令被足够多条独立路径反复转述后，叛徒能污染的路径始终是少数，多数表决就能把真值滤出来；而所有忠诚副官对每一个「源头」都算出相同的多数值，于是彼此一致。下图看最小的可解情形——四将军、一叛徒：

代价是昂贵的：OM(m) 需要 m+1 轮通信，消息数随叛徒数指数级增长（每层递归都要 n−1 路展开）。这也是它长期停留在理论、难以直接工程化的原因。

签名版：让谎言无处遁形

口信模型的死穴是「转述可以随口改」。作者的第二把钥匙是不可伪造的数字签名：给每条命令附上发令者的签名，且规定忠诚将军的签名无法被伪造、内容一经改动即被识破，任何人都能验真。这样一来，叛徒再不能篡改别人的话去骗人——他要么如实转发（带着原签名），要么只能就自己的那一份命令撒谎，而后者一验签就露馅。

在签名模型下，算法 SM(m) 让每个副官维护一个「已见命令」的集合：收到带足够签名链的新命令就加进去、再补上自己的签名转发给还没见过的人。由于谎报被签名堵死，所有忠诚副官最终会收到完全相同的命令集合，对这个集合施加同一个「选择函数」（如取唯一值、否则默认撤退）就必然一致。结论极其强：有了签名，无论叛徒有多少，忠诚者都能达成一致，3m+1 的枷锁被打破。代价是要先有一套人人信得过、无法造假的签名基础设施——这正是十几年后公钥密码学与区块链要补的课。

关键结果

这是一篇理论论文，「结果」是定理而非跑分：

• 不可能性下界：口信模型下，当且仅当将军总数 n ≥ 3m+1 时存在容忍 m 个叛徒的解；n = 3, m = 1 已无解。
• 可达性：算法 OM(m) 在 n ≥ 3m+1 时满足 IC1、IC2，用 m+1 轮通信、指数级消息量达到该下界。
• 签名的威力：引入不可伪造签名后，SM(m) 对任意 m 都可解，彻底绕开 3m+1。
• 丢失消息的处理：因为「缺席可被察觉」（同步假设），收不到的命令一律记作默认值「撤退」，保证算法照常收敛。

为什么重要 / 影响

它给整个领域装上了三样东西。第一，一套词汇：「拜占庭故障 / 拜占庭容错」成为「最坏、含恶意」故障模型的通用名，与「崩溃故障」两分天下——今天谈容错必先问「你防的是哪一种」。第二，一条量化红线：3m+1（含恶意时需三分之二诚实多数）成了无数协议的设计常数，从 PBFT 到各种联盟链、乃至 Tendermint / HotStuff，容错阈值都写着「少于三分之一作恶」。第三，一条工程路线：1999 年 Castro & Liskov 的 PBFT 把它做到实用（多项式消息、可跑真实服务），2008 年比特币则在开放、匿名的新场景里用工作量证明给出概率化的拜占庭容错——中本聪要解决的「无信任双花」，本质就是一个开放版拜占庭将军问题。可以说，今天一切「防作恶」的分布式账本，族谱第一格都写着这篇。

局限与批评

• OM(m) 不实用：指数级消息量使原始口信算法只能停在纸面；真正能跑的拜占庭协议（PBFT 及后继）是后来才补上的，且多依赖签名把复杂度压到多项式。
• 强同步假设：算法要求「消息有时间上限、缺席可被察觉」。在真实的异步网络里，这个前提并不总成立——而著名的 FLP 不可能性（1985）证明了纯异步下即便只有一个崩溃故障也无法确定性地达成共识，说明同步假设不是可有可无的装饰。
• 参与者固定且已知：模型假设将军是一个封闭、成员已知的集合（许可制）。它不直接适用于任何人都能匿名加入的开放网络——那需要比特币式的抗女巫（Sybil）机制另作补充。
• 冗余成本高：3m+1 意味着要容忍 m 个坏节点得部署三倍多的机器，代价远高于只防崩溃故障的 2m+1（如 Paxos / Raft）。很多系统因此宁可只假设崩溃故障。
• 签名版把难题外包了：signed-message 方案的强大，建立在「存在无法伪造的签名」之上——而这套密码学基础设施本身的建立与密钥管理，是另一整个难题。

要点