拜占庭容错：口头消息与书面消息

标签

分布式/共识算法

字数

5715 字

阅读时间

23 分钟

前面几篇讨论的都是崩溃故障 —— 失效的节点就是停止响应，不会主动说谎。拜占庭将军问题把故障模型换掉：失效的组件会向系统的不同部分发送相互矛盾的信息。这个模型不是学术假设，它有明确的现实来源：

一个可靠的计算机系统必须能应对一个或多个组件的失效。而失效的组件可能表现出一种常被忽视的行为 —— 向系统的不同部分发送相互矛盾的信息。

换成这个模型，$3m+1$ 那类"多数派即可"的直觉立刻失效：一个说谎的节点可以让两个忠诚节点在信息上产生分歧。这一篇沿着两条线走 —— 先看口头消息（只能靠多数派，界是 $3m+1$），再看书面消息（加了不可伪造的签名，界就消失了）。

从"一致性"化归到"交互一致性"

先把问题形式化。设第 $i$ 个将军观测到的信息是 $v(i)$，每个将军用某个方法把 $v(1),\dots ,v(n)$ 合成一个行动计划。要两个目标同时成立：

• 条件 A：所有忠诚将军决定同一个行动计划；
• 条件 B：少数叛徒不能使忠诚将军采纳一个坏计划。

条件 B 难以形式化（要精确说清"什么是坏计划"），所以换了一条路：不去定义"坏计划"，而是约束将军们怎么达成决定。如果能保证所有忠诚将军拿到同一组 $v(1),\dots ,v(n)$，再用同样的合成方法，条件 A 就自动满足；而用一个"稳健的"合成方法（例如取多数）就能照顾条件 B。

但直接把 $v(i)$ 发给所有人不行 —— 因为叛徒会对不同的将军发不同的值。于是需要：

条件 1：每个忠诚将军必须获得相同的 $v(1),\dots ,v(n)$。

条件 1 带来一个副作用：将军不能用"直接从第 $i$ 个将军那里收到的 $v(i)$"，因为叛徒 $i$ 可能对不同人发不同的值。但也不能因此允许一个忠诚将军发的值被替换掉：

条件 2：若第 $i$ 个将军忠诚，则他发出的值必须被每个忠诚将军用作 $v(i)$。

条件 1 改写成更容易用的形式，问题就收窄到**"一个将军如何把自己的值发给其他人"**：

条件 1'：任意两个忠诚将军使用相同的 $v(i)$。

拜占庭将军问题：一个指挥官必须向 $n-1$ 个副官下达命令，使得

• IC1：所有忠诚副官遵守同一命令；
• IC2：若指挥官忠诚，则每个忠诚副官遵守他发出的命令。

这两条称为交互一致性条件（interactive consistency conditions）。

注意 IC1 与 IC2 的关系：若指挥官忠诚，IC1 由 IC2 直接推出；但指挥官不必忠诚 —— 这正是问题难的地方。原问题的解法是：第 $i$ 个将军用"把 $v(i)$ 当作我的值"作为命令，通过解一次拜占庭将军问题来发出，其他将军当副官。

口头消息：三条假设与 $3m+1$ 界

"口头消息"的定义（这一点很关键）：内容完全由发送者控制，所以叛徒可以传任何可能的消息。这正对应计算机之间正常发送的消息类型 —— 这也是后面要引入签名才能放宽的原因。

口头消息模型建立在三条假设上：

假设	内容	排除的作弊方式
A1	每条发出的消息都被正确投递	—
A2	接收者知道发送者是谁	叛徒引入伪造消息来混淆另外两人的通信
A3	消息的缺失可以被检测到	叛徒靠不发消息来阻止决定

A1 与 A2 合起来排除了"叛徒干扰另外两个将军之间的通信"（按 A1 他改不了他们发出的消息，按 A2 他无法引入伪消息）。本节与下一节的算法还要求每对将军之间能直接通信 —— 去掉这条要求的算法另有一节。

三个将军一个叛徒为什么无解

不可能性结果是：

若只能用口头消息，除非超过三分之二的将军忠诚，否则无解。特别地，三个将军一个叛徒就无解。

两个场景并置来说明。只考虑"attack"/"retreat"两种决定：

• 场景一：指挥官忠诚，发出 "attack"；副官 2 是叛徒，他告诉副官 1 自己收到的是 "retreat"。由 IC2，副官 1 必须服从 attack。
• 场景二：指挥官是叛徒，他向副官 1 发 "attack"、向副官 2 发 "retreat"。副官 2（忠诚）如实告诉副官 1 自己收到 "retreat"。

在副官 1 看来这两个场景完全一样 —— 都是"指挥官说 attack，副官 2 说 retreat"。而场景一要求他攻击、场景二要求他撤退，所以不存在一个算法能同时满足两种情形。这和 FLP 那个"不可区分性"论证是同一手法（见 01-不可能性结果：FLP 与部分同步）。

两个场景并置，箭头表示"谁对谁说"：

场景一：指挥官忠诚，副官 2 是叛徒
   指挥官 ──"attack"──▶ 副官 1
   指挥官 ──"attack"──▶ 副官 2
   副官 2 ──"他说的是 retreat"──▶ 副官 1        ← 叛徒撒谎
   ⇒ 由 IC2，副官 1 必须服从 attack

场景二：指挥官是叛徒，两个副官都忠诚
   指挥官 ──"attack"──▶ 副官 1
   指挥官 ──"retreat"──▶ 副官 2
   副官 2 ──"他说的是 retreat"──▶ 副官 1        ← 如实转告
   ⇒ 副官 2 这边：收到 retreat 就必须服从它

   在副官 1 眼里两幕完全相同 ⇒ 没有一个算法能同时满足这两种要求 ⇒ 三将军一叛徒无解

$3m+1$ 界的证明：模拟手法

把"三个将军一个叛徒无解"推广成"少于 $3m+1$ 个将军无法容忍 $m$ 个叛徒"，用的是反证 + 模拟（simulation）：

1. 假设存在一个算法，能让 $3m$ 个或更少的将军容忍 $m$ 个叛徒；
2. 用它构造出"3 个将军容忍 1 个叛徒"的解法 —— 而后者已证不可能；
3. 构造的方式是模拟：让每个 Byzantine 将军模拟约三分之一的 Albanian 将军（两组人分别叫作 Albanian generals 与 Byzantine generals 以免混淆），使每个 Byzantine 将军至多模拟 $m$ 个 Albanian。具体分工是：
   • Byzantine 指挥官模拟 Albanian 指挥官 + 至多 $m-1$ 个 Albanian 副官；
   • 两个 Byzantine 副官各模拟至多 $m$ 个 Albanian 副官。
4. 因为只有一个 Byzantine 将军可能是叛徒，而他至多模拟 $m$ 个 Albanian，所以至多 $m$ 个 Albanian 是叛徒 —— 落在假设算法的容错能力内，于是 Albanian 侧的 IC1/IC2 成立；
5. 由 IC1，被一个忠诚 Byzantine 副官模拟的所有 Albanian 副官遵守同一命令，而这个命令正是该 Byzantine 副官要服从的命令 —— 于是把 Albanian 侧的性质"搬运"回了 Byzantine 侧，构造出了三将军解法，矛盾。

这类算法上"非形式推理最容易出错" —— 这句被特地点出，三将军情形的严格不可能性证明指向参考文献。

模拟构造把两拨人对应起来（Albanian 侧是假设存在的算法，Byzantine 侧是要被模拟出的三将军问题）：

     Albanian 侧（≤3m 个将军，容忍 m 个叛徒）      Byzantine 侧（3 个将军，容忍 1 个叛徒）

       Albanian 指挥官                              Byzantine 指挥官（至多 1 个是叛徒）
       ＋至多 m−1 个 Albanian 副官                        │
              ▲                                          │ 由他模拟
              └──────────────────────────────────────────┘
       Albanian 副官（各至多 m 个）                  Byzantine 副官 1、副官 2
              ▲                                          │
              └──────────────────────────────────────────┘ 各自由他们模拟

   计数：只有 1 个 Byzantine 可能是叛徒，而他至多模拟 m 个 Albanian
        ⇒ Albanian 侧至多 m 个叛徒 ⇒ 落在假设算法的容错能力内 ⇒ IC1/IC2 成立
        ⇒ 由 IC1 把 Albanian 侧的性质搬回 Byzantine 侧 ⇒ 三将军有解，与前述矛盾

OM(m)：能工作的递归算法

先定义一个函数 majority，只要求它满足一条性质：若多数 $v_i$ 等于 $v$，则 $\mathrm{majority}(v_1,\dots ,v_{n-1})=v$。两种自然选择：

1. 取 $v_i$ 中的多数值；不存在多数时取 RETREAT；
2. 取 $v_i$ 的中位数（假设取值来自有序集）。

算法本身只依赖上面那条性质，不依赖具体选哪种。

Algorithm OM(0)

1. 指挥官把值发给每个副官；
2. 每个副官使用他从指挥官收到的值；没收到就用 RETREAT。

Algorithm OM(m), $m>0$

1. 指挥官把值发给每个副官；
2. 对每个 $i$：令 $v_i$ 是副官 $i$ 从指挥官收到的值（没收到则记 RETREAT）。副官 $i$ 以指挥官的姿态执行 OM($m-1$)，把 $v_i$ 发给另外 $n-2$ 个副官；
3. 对每个 $i$ 与每个 $j\ne i$：令 $v_{ij}$ 是副官 $i$ 在 step (2) 从副官 $j$ 收到的值（没收到则记 RETREAT）。副官 $i$ 取

$$\mathrm{majority}(v_{i1},\dots ,v_{i,n-1})$$

用 $m=1,n=4$ 走一遍 两种情形：

• 副官 3 是叛徒：step 1 指挥官把 $v$ 发给三个副官；step 2 副官 1 用 OM(0) 把 $v$ 发给副官 2，叛徒副官 3 给副官 2 发另一个值 $x$；step 3 副官 2 手上是 $v_{21}=v$、$v_{22}=v$、$v_{23}=x$，于是得到正确的 $\mathrm{majority}(v,v,x)=v$。
• 指挥官是叛徒：他给三个副官发三个任意值 $x,y,z$。每个副官分别得到 $x$、$y$、$z$，于是 step 3 里三个人都得到 $\mathrm{majority}(x,y,z)$ —— 不管这三个值是否有相等的。

递归带来的实现细节：OM($m$) 会发起 $n-1$ 次 OM($m-1$)，每次再发起 $n-2$ 次 OM($m-2$)……所以 $m>1$ 时，一个副官要给每个其他副官发很多条消息。一条消除歧义的办法：

每个副官在 step (2) 发出的值 $v_i$ 前面加上自己的编号 $i$。

这样随着递归展开，OM($m-k$) 会被调用 $(n-1)\cdots (n-k)$ 次，发出的值带着一列 $k$ 个副官编号作为前缀。

$m=1$、$n=4$ 的两遍（$v$ 是指挥官的值，$x/y/z$ 是叛徒给的任意值）：

情形一：副官 3 是叛徒
   指挥官 ──v──▶ 副官 1、副官 2、副官 3
   副官 1 ──v──▶ 副官 2                （用 OM(0) 转发自己收到的值）
   副官 3 ──x──▶ 副官 2                （叛徒发别的值）
   副官 2 手上：v₂₁ = v、v₂₂ = v、v₂₃ = x
   ⇒ majority(v, v, x) = v             结论正确

情形二：指挥官是叛徒
   指挥官 ──x──▶ 副官 1     ──y──▶ 副官 2     ──z──▶ 副官 3     （三个任意值）
   各副官在 step (2) 用 OM(0) 互相转发自己收到的值
   每个副官最终都拿到 {x, y, z} ⇒ 三人都得 majority(x, y, z)
   ⇒ 无论 x、y、z 是否彼此相等，三人取到同一个值 —— IC1 成立

OM(m) 的证明

引理 1：IC2 的成立条件

引理 1：对任意 $m$ 与 $k$，若将军数多于 $2k+m$、叛徒至多 $k$ 个，则 OM($m$) 满足 IC2。

对 $m$ 归纳。IC2 只规定"指挥官忠诚时"必须怎样。

• $m=0$：由 A1，指挥官忠诚时平凡的 OM(0) 直接成立。
• 归纳步：忠诚指挥官在 step (1) 把 $v$ 发给全部 $n-1$ 个副官。step (2) 里每个忠诚副官用 $n-1$ 个将军执行 OM($m-1$)。由假设 $n>2k+m$ 得 $n-1>2k+(m-1)$，于是可对 OM($m-1$) 用归纳假设，推出每个忠诚副官对每个忠诚副官 $j$ 都得到 $v_{ij}=v$。 又因为叛徒至多 $k$ 个而 $n-1>2k+(m-1)\ge 2k$，所以 $n-1$ 个副官里多数是忠诚的。于是每个忠诚副官手上的 $v_{ij}$ 中有多数等于 $v$，由 majority 的性质得 $\mathrm{majority}(v_{i1},\dots ,v_{i,n-1})=v$，即 IC2 成立。$◻$

定理 1

定理 1：对任意 $m$，若将军数多于 $3m$、叛徒至多 $m$ 个，则 OM($m$) 满足 IC1 与 IC2。

对 $m$ 归纳。

• 无叛徒时 OM(0) 容易看出满足 IC1 与 IC2。
• 归纳步，设 OM($m-1$) 已成立，证 OM($m$)：

情形一：指挥官忠诚。 在引理 1 里取 $k=m$，得 OM($m$) 满足 IC2；而指挥官忠诚时 IC1 由 IC2 推出。这一情形无需额外验证。

情形二：指挥官是叛徒。 此时只需验证 IC1，而且可以用一条"余量"论证：

• 叛徒至多 $m$ 个，其中一个是指挥官，所以至多 $m-1$ 个副官是叛徒；
• 将军数多于 $3m$，所以副官数多于 $3m-1$；
• 而 $3m-1>3(m-1)$，恰好满足对 OM($m-1$) 用归纳假设的条件。

于是对每个 $j$，任意两个忠诚副官在 step (3) 得到相同的 $v_{ij}$ —— 论证要分两种情况：若两个副官里有一个就是副官 $j$ 本人，由 IC2；否则由 IC1。

由此，任意两个忠诚副官得到完全相同的向量 $v_1,\dots ,v_{n-1}$，因此在 step (3) 得到相同的 $\mathrm{majority}(v_1,\dots ,v_{n-1})$ —— 即 IC1 成立。$◻$

书面消息：加一条假设，界就消失了

困难的归因很直接：是叛徒"能说谎"这个能力让拜占庭将军问题变难。限制这个能力，问题就变简单。办法是让将军能发不可伪造的签名消息，即加一条假设：

A4 (a) 忠诚将军的签名不可伪造，其签名消息的内容被改动可被检测； (b) 任何人都能验证将军签名的真实性。

注意 (A4) 对叛徒的签名不做任何假设 —— 这里特别允许一个叛徒的签名被另一个叛徒伪造，也就是允许叛徒串通（collusion）。

加了 A4 之后，前面"容忍一个叛徒需要四个将军"的论证不再成立 —— 事实上三个将军的解存在。有一个对任意数量将军都能容忍 $m$ 个叛徒的算法（将军数少于 $m+2$ 时问题无意义）。

先定义一个归约函数 choice，只要求两条：

1. 若集合 $V$ 只含单个元素 $v$，则 $\mathrm{choice}(V)=v$；
2. $\mathrm{choice}(\mathrm{\varnothing })=\text{RETREAT}$。

一种可用的定义是取 $V$ 的中位数（假设元素有序）。

Algorithm SM(m)

记号 $x:i$ 表示"被将军 $i$ 签名的 $x$"。设将军 0 是指挥官。每个副官 $i$ 维护一个集合 $V_i$，装他收到的所有正确签名的命令。

注意区分：$V_i$ 是收到的命令集合，不是消息集合 —— 同一个命令可能对应很多条不同的消息。

初始化：$V_i=\mathrm{\varnothing }$。

(1) 指挥官签名并把他的值发给每个副官。

(2) 对每个 $i$：

• (A) 若副官 $i$ 收到形如 $v:0$ 的消息，且他还没收到过任何命令，则 (i) 令 $V_i=\{v\}$；(ii) 把消息 $v:0:i$ 发给其他每个副官。
• (B) 若副官 $i$ 收到形如 $v:0:j_1:\cdots :j_k$ 的消息，且 $v\notin V_i$，则 (i) 把 $v$ 加入 $V_i$；(ii) 若 $k<m$，则把 $v:0:j_1:\cdots :j_k:i$ 发给除 $j_1,\dots ,j_k$ 之外的每个副官。

(3) 当副官 $i$ 不会再收到更多消息时，他服从 $\mathrm{choice}(V_i)$。

三个关键点：

• step (2) 里副官忽略任何含"已在 $V_i$ 中的命令 $v$"的消息 —— 这是防止无限转发（同一命令不会被反复签名转发）。
• 签名链长度到 $m$ 就停（(B) 的 $k<m$ 条件）—— 因为至多 $m$ 个叛徒，再长的链不可能由忠诚节点产生。
• 终止怎么判定：按 $k$ 归纳可以证明，对每个长度 $k\le m$ 的副官序列，副官在 step (2) 至多收到一条形如 $v:0:j_1:\cdots :j_k$ 的消息。因此只要要求最后一个副官要么发这条消息、要么发一条"我不会发"的报告，就能判定所有消息都已收到 —— 而由 A3，副官能判断出叛徒既没发这个、也没发那个。另一种做法是用超时。

为什么副官能识破指挥官

用 $m=1$、三个将军、指挥官是叛徒的情形展示效果：指挥官给一个副官发 attack、给另一个发 retreat。两个副官在 step (2) 都会收到两条命令，于是

$$V_1=V_2=\{\text{attack},\text{retreat}\}$$

两人都服从 $\mathrm{choice}(\{\text{attack},\text{retreat}\})$。

与前面口头消息那个"无法区分"的场景对照：在口头消息那两个场景里，副官分不清是「指挥官叛变」还是「另一个副官叛变」；而在 SM(m) 里副官们直接知道指挥官是叛徒 —— 因为他的签名出现在两个不同的命令上，而 A4 说只有他本人能生成那些签名。

一条实现上的观察：SM(m) 里副官签名是对收到命令的确认。若他是第 $m$ 个给某条命令加签名的，那个签名不会再被转给任何人，因此是多余的。

$m=1$、三个将军、指挥官是叛徒：

   指挥官 ──attack:0──▶ 副官 1          （0 是指挥官的编号，冒号后跟签名）
   指挥官 ──retreat:0──▶ 副官 2
   副官 1 ──attack:0:1──▶ 副官 2
   副官 2 ──retreat:0:2──▶ 副官 1

   两人最终都得到 V₁ = V₂ = {attack, retreat} ⇒ 都服从 choice({attack, retreat})

   关键：指挥官的两条内容不同的命令上带着同一把签名（attack:0 与 retreat:0）
   ⇒ 副官直接断定指挥官是叛徒 —— A4 说他签名的真实性任何人都能验证，
      而只有他本人（或串通的叛徒）能生成它
   口头消息下做不到这一点：副官分不清是谁在撒谎

这条线与工程的距离

这一篇给的是理论边界：口头消息要 $3m+1$，书面消息（有不可伪造签名）对叛徒数量没有限制。把"签名"换成工程上可用的机制、把 $O(n^m)$ 的递归消息量压到可接受的范围，是 Castro 与 Liskov 的 PBFT（1999）做的 —— 它把消息复杂度降到 $O(n^2)$ 量级，代价是要求部分同步（也就不可避免地把活性交给时序，见 01-不可能性结果：FLP 与部分同步）。PBFT 的三阶段协议与它的 $3f+1$ 副本要求值得单独一篇，暂列待建。

判据速查

问题	答案
拜占庭故障与崩溃故障的差别	失效节点会向不同节点发相互矛盾的信息
IC1 / IC2 分别是什么	IC1 所有忠诚副官遵守同一命令；IC2 指挥官忠诚时他们遵守他发的命令
指挥官忠诚时两条的关系	IC1 由 IC2 推出；但指挥官不必忠诚
口头消息的容错界	$n>3m$（超过三分之二忠诚），即少于 $3m+1$ 个将军无解
三将军一叛徒为什么无解	副官无法区分"指挥官叛变"与"另一副官叛变"两种场景
$3m+1$ 界怎么证	反证 + 模拟：用"≤3m 容 $m$"构造出"3 将军容 1 叛徒"
口头消息的三条假设	A1 正确投递、A2 知道发送者、A3 消息缺失可检测
OM(m) 递归里怎么去歧义	每个副官在发值前加上自己的编号作前缀
引理 1 的条件	将军数 $>2k+m$、叛徒至多 $k$ → 满足 IC2
定理 1 两种情形怎么分	指挥官忠诚 → 用引理 1 得 IC2（IC1 随之）；指挥官叛变 → 至多 $m-1$ 个副官叛变，$3m-1>3(m-1)$ 正好够用归纳假设
签名消息的容错界	没有界 —— 对任意将军数都能容忍 $m$ 个叛徒
A4 对叛徒签名怎么假设	不做假设，明确允许叛徒之间伪造彼此签名、串通
副官怎么知道指挥官在撒谎	他的签名出现在两个不同命令上，而 A4 说只有他能生成
SM(m) 里签名链为什么到 m 停	至多 $m$ 个叛徒，更长的链不可能由忠诚节点产生
重复签发怎么防	step (2) 忽略含"已在 $V_i$ 中"的命令的消息

相关

• 01-不可能性结果：FLP 与部分同步 —— 同一个"不可区分性"证明手法；故障模型的层次（崩溃 / 遗漏 / 拜占庭）在那篇的容错表里有对照
• Raft / Paxos —— 都只处理崩溃故障，因此可以只靠多数派；本篇说明换掉故障模型后多数派为什么不够

参考

• Leslie Lamport, Robert Shostak, Marshall Pease. The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems, Vol. 4, No. 3, July 1982, pp. 382–401.
• Miguel Castro, Barbara Liskov. Practical Byzantine Fault Tolerance. OSDI 1999, pp. 173–186.

贡献者

YJ

文件历史

最后编辑于 大约 23 小时前查看完整历史

e7758-累累累，我的token qaq

ae1ee-docs：内容完善

448f1-分布式