拜占庭将军问题

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

前言

拜占庭将军问题由 Lamport、Shostak 和 Pease 于 1982 年提出，描述了分布式系统中存在恶意节点（拜占庭故障）时，如何在参与方之间就一个共同决策达成一致的问题。该问题奠定了对抗任意错误（Arbitrary Failures / Byzantine Failures）容错理论的基础，并直接影响了后续共识算法、分布式数据库以及区块链等领域的发展。

与仅考虑节点宕机（Crash Fault）的传统容错模型不同，拜占庭故障允许节点表现出任意行为，例如发送错误消息、向不同节点发送相互矛盾的信息、伪造消息、恶意篡改协议执行过程等。因此，拜占庭容错被认为是最强、最困难的故障模型之一。

---

问题描述

经典的拜占庭将军问题采用一个指挥官（Commander）和若干副将（Lieutenants）的模型。

想象若干将军包围一座城市，他们只能通过信使通信。所有忠诚将军必须在以下两个命令中做出统一选择：

• Attack（进攻）
• Retreat（撤退）

若所有将军同时进攻，则能够取胜；若所有将军同时撤退，则能够安全撤离；但若部分进攻、部分撤退，则可能被敌军逐个击破。因此系统需要满足：

• 一致性（Agreement）：所有忠诚将军最终执行相同命令；
• 有效性（Validity）：如果指挥官是忠诚的，则所有忠诚副将必须执行指挥官发出的命令。

系统中最多允许存在 $f$ 个拜占庭节点。目标是在存在最多 $f$ 个拜占庭故障的情况下，仍然满足一致性与有效性。

---

系统模型与假设

论文讨论了同步分布式系统（Synchronous Distributed System）中的两种通信模型：

• 同步系统：消息能够在已知有限时间内送达；
• 点对点通信：任意两个进程之间都可以直接通信；
• 节点可能出现拜占庭故障。

两种消息模型分别为：

口头消息模型（Oral Messages）

消息没有认证机制。

拜占庭节点可以：

• 发送错误信息；
• 向不同节点发送不同内容；
• 伪造消息来源；
• 丢弃收到的消息。

这是最困难的模型。

签名消息模型（Signed Messages）

签名消息模型增加了三个非常强的假设：

SM1:签名无法伪造。

SM2:任何人都能验证签名。

SM3：签名内容不可修改。

每条消息都带有不可伪造的数字签名。

拜占庭节点仍然可以：

• 拒绝发送消息；
• 转发错误信息；

但不能：

• 伪造其他节点的签名；
• 篡改已经签名的内容。

因此问题会显著简化。

---

基本结论

口头消息模型

若系统允许最多 $f$ 个拜占庭节点，则必须满足：

$$
n \ge 3f + 1
$$

其中：

• $n$ 为系统总节点数；
• $f$ 为最多允许的拜占庭节点数。

同时需要至少：

$$
f+1
$$

轮消息传播才能完成共识。

例如：

最大故障数 $f$	最少节点数 $n$
1	4
2	7
3	10
10	31

---

签名消息模型

若消息带有不可伪造签名，则只需：

$$
n \ge f + 1
$$

即可达成一致。

数字签名使得节点无法伪造他人的消息，因此大幅降低了问题难度。

模型	知道发送者是谁	能证明发送内容未被篡改
OM	Y	N
SM	Y	N

为什么必须满足 $n \ge 3f+1$

这是拜占庭将军问题最著名的结论。

设系统中最多存在：

$$
f
$$

个恶意节点。

那么至少需要：

$$
2f+1
$$

个忠诚节点。

即：

$$
n-f > 2f
$$

整理得到：

$$
n > 3f
$$

因此：

$$
n \ge 3f+1
$$

直观理解为：

忠诚节点数量必须严格超过恶意节点数量的两倍。

这样即使所有恶意节点联合撒谎，忠诚节点之间仍然能够形成稳定多数派。

例如当：

$$
f=1
$$

时，

A（可能是叛徒）
B
C
D

若 A 向不同副将发送不同命令：

A→B：进攻
A→C：撤退
A→D：撤退

B 可以通过向 C、D 询问其收到的信息来形成多数意见：

进攻：1
撤退：2

最终选择撤退。

重要的是：

B 并不需要确定谁是叛徒。

事实上 B 无法判断究竟是 A 在撒谎，还是 C、D 中某个节点在撒谎。

拜占庭容错的目标并不是找出恶意节点，而是在无法识别恶意节点的情况下，仍然让所有忠诚节点得到相同结论。

---

不可达性证明（缩略）

当：

$$
n \le 3f
$$

时，不可能同时满足一致性和有效性。

证明思路基于不可区分性（Indistinguishability）。

将系统划分为三组，每组最多包含f个节点。

拜占庭节点可以向不同组发送不同信息，使得两个忠诚节点观察到的系统状态完全不同，但又无法判断究竟是谁在撒谎。

因此会出现：

• 某些忠诚节点认为应该进攻；
• 某些忠诚节点认为应该撤退。

从而违反一致性条件。

---

经典算法：OM(m)

在口头消息模型下，Lamport 等人提出了递归算法 OM(m)（Oral Messages）。

其中：

• OM(0)：容忍 0 个拜占庭节点；
• OM(1)：容忍 1 个拜占庭节点；
• OM(2)：容忍 2 个拜占庭节点；
• …

一般情况下：

$$
OM(f)
$$

能够容忍：

$$
f
$$

个拜占庭节点。

---

OM(0)

指挥官向所有副将发送命令。

每个副将直接采用收到的命令。

若未收到消息，则采用默认值。

---

OM(m)

当：

$$
m > 0
$$

时：

1. 指挥官向每个副将发送命令；
2. 每个副将把自己收到的命令转发给其他副将；
3. 其他副将继续递归执行 OM(m−1)；
4. 每个节点收集所有收到的信息；
5. 对收集到的信息进行多数投票（Majority Voting）。

最终结果作为自己的决策。

---

为什么多数投票有效

例如：

A→B：进攻
A→C：进攻
A→D：撤退

交换消息后：

B 看到：

B收到：进攻
C收到：进攻
D收到：撤退

统计结果：

进攻：2
撤退：1

因此 B 选择进攻。

同理：

C 和 D 最终也会得到相同统计结果。

因此：

B = C = D = 进攻

系统仍然达成一致。

注意：

这里达成一致的原因不是因为大家找出了叛徒，而是因为忠诚节点形成了多数派。

---

正确性结论

OM(m) 能够保证：

• 一致性（Agreement）
• 有效性（Validity）

其成立条件为：

$$
n \ge 3m+1
$$

令：

$$
m=f
$$

即可得到经典结论：

$$
n \ge 3f+1
$$

---

签名消息的情形

若消息带有不可伪造签名，则可以使用签名链（Signature Chain）传播消息。

例如：

Commander
↓
A
↓
B
↓
C

每次转发都附带已有签名。

由于任何节点都无法伪造其他节点的签名，因此消息来源可以被验证。

此时拜占庭节点无法制造多个互相矛盾的“合法消息”，从而显著降低问题难度。

因此只需：

$$
n \ge f+1
$$

即可实现一致性。

---

示例

当：

$$
f=1
$$

时，

根据：

$$
n \ge 3f+1
$$

需要至少：

$$
n=4
$$

个节点。

此时运行 OM(1)：

1. 指挥官发送命令；
2. 副将交换自己收到的命令；
3. 所有副将对结果进行多数投票。

即使存在一个恶意节点，也能够保证所有忠诚节点最终做出相同决定。

为什么 OM 中“可以谎报自己收到的内容”会导致必须要 3f+1，而 SM 中一旦禁止这种谎报，条件立刻下降到 f+1？

OM 里，节点传播的是“声称（claim）”；SM 里，节点传播的是“证据（evidence）”。
诚实节点不再需要靠“人数优势”去盲目投票。只要系统里有 $f+1$ 个节点，扣除掉最多 $f$ 个坏人，至少能保证有 1 个诚实节点。只要这一个诚实节点把带有正确签名的真实消息在网络中广播出去，其他诚实节点由于能验证签名，就一定会采纳这个真实消息。

---

讨论与应用

拜占庭将军问题是现代分布式系统容错理论的基石，对后续研究产生了深远影响。

典型应用包括：

• BFT 共识协议（PBFT、HotStuff 等）；
• 区块链系统中的节点共识；
• 分布式数据库复制协议；
• 高可靠分布式服务。

需要注意的是，现代系统中的共识协议通常不再采用“永久指挥官”模型，而是使用轮换主节点（Leader / Primary）机制。例如 PBFT 中的 Primary 本质上对应原问题中的 Commander，但可以通过 View Change 被替换。

此外，实际工程系统往往会利用：

• 数字签名；
• 消息认证码（MAC）；
• 超时机制；
• 概率性共识；

等技术降低通信复杂度，提高可扩展性，从而使拜占庭容错理论能够应用于大规模分布式环境。

参考文献

• Lamport, L., Shostak, R., & Pease, M. (1982). The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems (TOPLAS).

---