← COMP5567 全部讲次
L07b · 第 7 周

L07b 3m+1 下界:为什么 3 个人压不住 1 个叛徒

从三将军的两种情形讲起,说明忠诚副官为什么分不清谁在撒谎,再用「每人扮演一组」把结论推广成 n ≥ 3m+1。

一句话版

只靠口头转述时,3 个人里只要有 1 个叛徒,忠诚的人就分不清是谁在撒谎,问题无解。把每个人换成一组 m 个人,结论变成:总人数至少要 3m+1,才可能压住 m 个叛徒。

上一页定好了两个验收条件 Agreement 和 Validity,见 L07a。这一页证明,人数不够时,任何口头消息算法都满足不了它们。

先认识这几个词

词 全称 / 读法 一句人话
口头消息 oral message 内容全由发送者决定,转述时可以随便改,收信人没法验证
m 叛徒个数 最多有几个人会撒谎
n ≥ 3m+1 读「n 大于等于 3m 加 1」 总人数至少是叛徒数的 3 倍再多 1
下界 lower bound 少于这个数,什么算法都不行
不可区分 indistinguishable 两个不同的世界,在某人眼里看到的消息一模一样
反证法 proof by contradiction 先假设结论不成立,推出矛盾

一个类比:两个同事给你传话

你是小林。老板说「明天上线」,同事小王却告诉你:「老板跟我说的是不上线。」

有两种可能。一种是老板两头说了不同的话,小王只是如实转告。另一种是老板说得清清楚楚,小王在编。

你手机里看到的聊天记录,两种可能下一个字都不差。你只能凭这些记录做决定,所以两种可能下你必须做同一个决定。

如果群里有更多同事,你可以多问几个人。多数人说的版本更可信。可是只有你、小王、老板三个人时,你找不到第三个说法来对质。

类比在哪里失效:

  • 现实里你可以打电话给老板核实,本讲的副官只能看收到的消息。
  • 本讲假设消息一定送达、能认出是谁发的,聊天记录也不会丢。
  • 下面的论证还要求对称地考虑小王的处境,日常传话不会这么严格地推。

从零讲起

1. 先补一块:反证法(补充)

它解决什么问题

这一页要证明「不存在任何算法能做到某件事」。算法有无穷多种,没法一个一个试。反证法换个方向:假设有一个算法做到了,然后推出一件不可能的事,于是假设错了。

直觉

你想证明「抽屉里没有红袜子」。先假设有一只。再从别的事实推出:如果有,它一定被洗衣机染过颜色,可是洗衣机这周没开过。矛盾出现了,所以没有红袜子。

本讲用到的矛盾是:同一个副官,在两个他分不清的世界里,被要求做两个不同的决定。

一步一步看

目标:看反证法的五步怎么走,以及本页每一步对应什么。

  1. 写下要证的结论:3 位将军对付 1 个叛徒,没有算法能同时满足 Agreement 和 Validity。
  2. 反过来假设:有这样一个算法。
  3. 用这个算法跑两种情形,看每个忠诚副官被逼着做什么。
  4. 发现某处冲突,比如两位忠诚副官做了不同决定。
  5. 冲突说明第 2 步的假设站不住,原结论成立。
步 做什么 本页里对应什么
1 写结论 3 人对付 1 叛徒无解
2 假设相反 有算法能解
3 推后果 情形 1 和情形 2 里 L1 的决定
4 找矛盾 情形 1 里 L1、L2 分道扬镳
5 下结论 假设错,无解

怎么判断

一个证明是不是反证法,看它开头有没有「假设……成立」,结尾有没有「矛盾,所以假设不成立」。两头都有就是。

常见误解

以为举一个算法失败的例子就证明了无解

举一个算法失败,只说明那个算法不行。要证明「所有算法都不行」,得像反证法这样,假设任意一个算法成功,再推出矛盾。

试一下

用反证法的格式写一句:「两将军问题没有确定能成功的办法」怎么证?

假设有一个办法发 k 条信就能保证一致。最后一条可能丢,收信人不能依赖它,于是 k−1 条也够。一路倒推到 0 条,两人不发信也能一致,矛盾。所以这样的办法不存在。

2. 三将军:L1 为什么分不清

它解决什么问题

最小的有意思的情形是 3 个人:一位指挥官 C、两位副官 L1 和 L2,其中 1 个是叛徒。这一节证明,这种情形下没有口头消息算法能满足两个条件。

一个人自己和自己当然一致。两个人里有一个叛徒,就只剩一个忠诚者,两个条件自动满足,谈不上难。真正的不可能从 3 个人开始。

直觉

站在 L1 的位置看。L1 手里永远只有两样东西:C 直接给它的命令,和 L2 转述的「C 跟我说的是……」。

叛徒可能是 C,也可能是 L2。两种情况下,只要叛徒做得巧,L1 收到的东西可以一模一样。L1 分不清,就只能在两种情况下做同一个决定。麻烦在于,两个条件在两种情况下要的东西不一样。

一步一步看

目标:看 L1 在两种情形里收到的消息为什么一模一样,并由此推出三将军无解。

  1. 情形 1:C 是叛徒(虚线圈)。C 对 L1 说 attack,对 L2 说 retreat。L2 忠诚,照实告诉 L1「C 说 retreat」。

    三将军情形 1:上方虚线圈 C 是叛徒,向 L1 发 attack、向 L2 发 retreat,忠诚的 L2 向 L1 转告 C 说 retreat;底部框写 L1 手里的两条消息

  2. 情形 2:C 忠诚,对两人都说 attack。L2 是叛徒,它把 attack 改成 retreat,告诉 L1「C 说 retreat」。

    三将军情形 2:C 忠诚,向 L1 和 L2 都发 attack,叛徒 L2 画成虚线圈,向 L1 谎报 C 说 retreat;底部框写 L1 手里同样是这两条消息

  3. 把两种情形里 L1 收到的东西并排放。两边都是「C 说 attack」加「L2 说 C 说 retreat」,一字不差。

    两栏并排:情形 1 撒谎的是 C,情形 2 撒谎的是 L2,两栏里 L1 收到的都是 C 到 L1 的 attack 和 L2 转告的 C 说 retreat,中间用青绿等号连起来

  4. 看情形 2。C 忠诚、下令 attack,Validity 要求忠诚的 L1 执行 attack。

  5. L1 分不清两种情形,所以在情形 1 里也只能 attack。

  6. 对称地看 L2。把 L1 和 L2 的角色互换,同样的论证说明:L2 收到 C 的 retreat 时必须执行 retreat。

  7. 回到情形 1:L1 attack,L2 retreat。两位忠诚副官做了不同决定,违反 Agreement。

怎么判断

想判断「某个人数下有没有解」,这一节给了一个可复用的检查:

  1. 找一位忠诚副官,列出他在某个世界里收到的全部消息。
  2. 再构造另一个世界,换一个人当叛徒,让这位副官收到同样的消息。
  3. 如果两个世界对他的要求不同,比如一个世界 Validity 要他 attack,另一个世界 Agreement 要他跟着别人 retreat,就说明无解。

关键词是不可区分。忠诚节点只能根据自己看到的消息做决定,看到的一样,决定就必须一样。

常见误解

以为让 L1 多问几轮就能分清

L2 是叛徒时,它每一轮都可以一致地撒同样的谎;C 是叛徒时,它也可以一致地两头说。轮数加多,L1 看到的两个世界依然一样。

以为 L1 可以随便选一个,碰运气

协议要在叛徒采取最坏做法时也成立。只要存在一种叛徒的做法让条件失败,这个人数下就算无解。

试一下

把情形 1 改成 C 对 L1 说 retreat、对 L2 说 attack,L2 如实转告。再构造一个让 L1 分不清的情形 2。

情形 2:C 忠诚,对两人都说 retreat;L2 是叛徒,谎报「C 说 attack」。两种情形下 L1 收到的都是「C 说 retreat」加「L2 说 C 说 attack」,L1 分不清。情形 2 里 Validity 要 L1 retreat,于是情形 1 里 L1 也 retreat,而 L2 执行 attack,违反 Agreement。

3. 推广:3m 个人压不住 m 个叛徒

它解决什么问题

三将军只说明了 1 个叛徒的情形。真实系统要对付的叛徒可能有好几个。这一节把结论推广:总人数是 3m 或更少时,压不住 m 个叛徒。

直觉

把三将军里的每个人,换成一组 m 个人。

假设真有一个算法,能让 3m 位将军对付 m 个叛徒。那就让三位将军每人在脑子里模拟一组:一个人扮演 m 个人,替他们收发消息、做决定。

叛徒那一组恰好对应一位叛徒将军。于是这个算法就变成了「3 个人对付 1 个叛徒」的算法。上一节已经证明这种算法不存在,所以开头那个算法也不存在。

一步一步看

目标:看把每个人换成一组 m 人后,3m 人对 m 个叛徒怎样退回三将军的情形。

  1. 把 3m 位将军分成三组,每组 m 人:上组含指挥官,另外是左下组和右下组。

  2. 让上组整组叛变(图里虚线),向左下组发一个值,向右下组发另一个值。

  3. 右下组忠诚,把收到的值如实转告左下组。

    三个椭圆各装 m 个小圆:上组整组用虚线画成叛徒,箭头指向左下组和右下组,右下组再向左下组转告;底部写着每组当成一个人看就回到三将军的情形 1

  4. 把每组当成一个人看,这就是三将军的情形 1。换成右下组叛变、上组忠诚,就是情形 2。左下组在两种情形下收到的消息一样,分不清。

  5. 课件的图画的是 m = 6:每组 6 个人,共 18 位将军。叛徒组 6 人,正好是总数的三分之一。

怎么算

下界写成式子:

  • 口头消息下可解,当且仅当 n ≥ 3m+1

意思是:总人数要比叛徒数的 3 倍还多至少 1 个。换个说法,忠诚的人要超过三分之二。

n > 3m 和 n ≥ 3m+1 是同一个条件。人数是整数,大于 3m 就是至少 3m+1。

反过来,已知人数 n,最多能容忍几个叛徒?从 3m+1 ≤ n 解出 m:

  • 3m ≤ n − 1,所以 m ≤ (n − 1) / 3,再向下取整

意思是:先减 1,再除以 3,舍掉小数。

几个例子:

  • n = 4:(4 − 1) / 3 = 1,容忍 1 个
  • n = 7:(7 − 1) / 3 = 2,容忍 2 个
  • n = 10:(10 − 1) / 3 = 3,容忍 3 个
  • n = 18:(18 − 1) / 3 = 5.67,向下取整为 5;所以 18 人对 6 个叛徒不够,要 3 × 6 + 1 = 19 人

常见误解

以为忠诚者过半就够了

课件有一页写的是「忠诚将军占多数」。口头消息下过半不够,要超过三分之二。答题按 n ≥ 3m+1 写。

以为 3m+1 是某个算法的要求,换个算法也许能少几个人

3m+1 是下界:少于它,任何口头消息算法都不行。换算法降不下来,要降只能换假设,比如加上签名,见本讲最后一页。

试一下

13 位将军最多容忍几个叛徒?再多 1 个叛徒,至少要几位将军?

(13 − 1) / 3 = 4,最多容忍 4 个。5 个叛徒要 3 × 5 + 1 = 16 位将军。

把它们串起来

论证从最小的情形开始。3 个人里 1 个叛徒,忠诚的 L1 只能看到两条消息,而叛徒是 C 还是 L2,这两条消息可以一模一样。

L1 分不清,就只能在两个世界里做同一个决定。Validity 在一个世界里逼它 attack,Agreement 在另一个世界里要它跟 L2 一致。两头没法同时满足,于是无解。

推广只用一个技巧:每个人扮演一组 m 个人。3m 人对 m 个叛徒的算法,会变成 3 人对 1 个叛徒的算法,而后者不存在。所以口头消息下至少要 3m+1 人。

下界只说人少了不行,没说人够了就行。下一页的 OM 算法证明:人数达到 3m+1,确实能做到。

课件里的坑

  • [读图提醒] p.12「2 generals, 1 traitor, no consensus」:原论文脚注说两位将军的情形是平凡的,只剩一位忠诚者时两个条件自动满足。真正的不可能性从 3 个人开始(p.12)。
  • [读图提醒] p.10 末行只说「忠诚将军占多数」,口头消息下要超过 2/3,以 p.11 和 p.13 为准(p.10–11)。
  • [读图提醒] p.13 的图里,点的颜色表示身份(红 = 叛徒、蓝 = 忠诚),箭头颜色表示传的值(蓝 = 1、红 = 0)。两种颜色含义不同,读图时别混(p.13)。
  • [等价写法] 老师课上写了「n > 3m ⇔ n ≥ 3m+1」,两种写法等价,后一种更常用(p.14)。

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,在纸上画出 p.12 的两张三角图,标出谁是叛徒、每条箭头传什么;然后口述一遍「L1 分不清 → Validity 逼它 attack → 违反 Agreement」;最后用 (n − 1) / 3 算几个人数能容忍多少叛徒。

必背

  1. 口头消息下可解当且仅当超过 2/3 忠诚,即 n ≥ 3m+1;3 人对付 1 个叛徒无解,因为 L1 分不清谁在撒谎
  2. 三将军论证:情形 1 指挥官叛变,情形 2 副官 L2 叛变,L1 两次收到的消息完全一样(不可区分)
  3. Validity 逼 L1 在情形 2 选 attack,于是情形 1 里 L1 也 attack、L2 retreat,违反 Agreement
  4. 推广:少于 3m+1 位将军无法应对 m 个叛徒,证法是让 3 人各模拟一组 m 人,归约回三将军
  5. n > 3m 和 n ≥ 3m+1 是同一个条件;10 位将军最多容忍 3 个叛徒,18 位将军对 6 个叛徒无解

课件例题

例 1(课件 p.12):3 个将军、1 个叛徒

情形 1 指挥官叛变,给 L1 发 attack、给 L2 发 retreat,L2 转告 L1「retreat」;情形 2 指挥官忠诚发 attack,L2 叛变转告 L1「retreat」。L1 能分辨吗?

两张三角消息图。Case 1: Source process is faulty,灰色的 Commander 给 L1 发 attack、给 L2 发 retreat,L2 向 L1 转告 retreat;Case 2: Process L2 is faulty,Commander 给 L1、L2 都发 attack,灰色的 L2 向 L1 转告 retreat。两张图里 L1 收到的消息完全相同
图片来源:COMP5567 Lecture_7-BFT.pdf, p.12
提示

把两种情形里 L1 收到的消息逐条列出来比一比。

解答

两种情形下 L1 收到的都是「指挥官说 attack、L2 说 retreat」,无法分辨谁在撒谎。情形 2 里 Validity 要 L1 attack,所以情形 1 里 L1 也 attack;对称地 L2 retreat,违反 Agreement。所以 3 人对付 1 个叛徒无解。

例 2(课件 p.13):18 位将军、6 个叛徒

课件的图画了三个椭圆,每个装 6 位将军。为什么这 18 位将军对付不了 6 个叛徒?

左右两张图,各有三个椭圆,每个椭圆里 6 个圆点代表 6 位将军,红点是叛徒、蓝点是忠诚者。左图顶部椭圆全红,向左下发蓝箭头 1、向右下发红箭头 0,右下椭圆再向左下椭圆发红箭头 0;右图顶部全蓝,向两边都发 1,右下椭圆全红,向左下椭圆发红箭头 0
图片来源:COMP5567 Lecture_7-BFT.pdf, p.13
提示

把每个椭圆当成一个人看,图会变成哪一页的哪张图?

解答

18 = 3 × 6,即 n = 3m、m = 6,不满足 n ≥ 3m+1 = 19。左图顶部一组是叛徒,给两组发不同的值,右下组如实转告;右图顶部忠诚、右下组叛变谎报。左下组在两张图里收到的一样,分不清。每组看成一个人,就是 p.12 的情形 1 和情形 2。推广的结论:少于 3m+1 位将军无法应对 m 个叛徒。

完整例题

题目:(1) 课件 p.9 说 10 位将军时「4 个及以上叛徒」就可能出坏计划。用下界验证这句话。(2) 用推广论证说明 9 位将军对付不了 3 个叛徒。

解:

  1. (1) 已知 n = 10,求最大的 m。由 3m+1 ≤ 10 得 m ≤ 3,所以最多容忍 3 个叛徒。
  2. 叛徒有 4 个时,3 × 4 + 1 = 13 > 10,人数不够,可能出坏计划,和课件一致。
  3. (2) 9 = 3 × 3,把 9 人分成三组,每组 3 人。
  4. 假设有算法能让这 9 人对付 3 个叛徒。让三位将军各模拟一组 3 人,叛徒组对应一位叛徒将军。
  5. 这就得到一个「3 人对付 1 个叛徒」的算法,与三将军的结论矛盾。所以 9 人对付不了 3 个叛徒。

要点:算最大叛徒数用 (n − 1) / 3 向下取整;证明无解时说清「每人模拟一组」这一步。

答题格式:先写不等式 n ≥ 3m+1 并代数,再一句话说明归约到三将军。

变式题(先自己做)

(1) 7 位将军最多容忍几个叛徒?如果叛徒有 3 个,至少要几位将军?

(2) 三将军里,叛徒 L2 改成「什么都不转告」。L1 还会分不清吗?结合「能察觉谁没发消息」的假设回答。

提示

(1) 代公式 (n − 1) / 3。(2) 叛徒的最坏做法是哪一种?协议要对最坏做法成立。

判分点与答案(非官方评分标准)

判分点:① (1) 两问都要写出计算式;② (2) 要指出「不转告」不是叛徒的最坏做法,下界论证用的是谎报。

(1) (7 − 1) / 3 = 2,最多 2 个。3 个叛徒要 3 × 3 + 1 = 10 位将军。

(2) 不转告会被察觉,L1 按默认值处理,这种做法反而容易对付。下界论证里叛徒选的是谎报,L1 在两个世界里看到的一样。只要存在一种做法让 L1 分不清,问题就无解。

闪卡自测

1. 口头消息下,可解的条件是什么?

超过 2/3 的将军忠诚,即 n ≥ 3m+1(p.11)。

2. p.12 里 L1 为什么分不清两种情形?

两种情形下 L1 收到的都是「指挥官说进攻」加「L2 说指挥官让撤退」,它看到的消息完全一样(p.12)。

3. 三将军论证最后违反的是哪个条件?

Agreement:情形 1 里 L1 attack、L2 retreat,两位忠诚副官不一致(p.12)。

4. 10 位将军用口头消息最多容忍几个叛徒?

3 个,因为 3m+1 ≤ 10 时 m 最大为 3(p.9)。

5. 怎么把三将军的结论推广到 m 个叛徒?

让 3 位将军各模拟一组 m 人,叛徒组对应一位叛徒,归约回三将军(p.13)。

6. n > 3m 和 n ≥ 3m+1 有区别吗?

没有。n 是整数,两种写法等价,老师课上画了等号(p.14)。

7. 口头消息的含义是什么?

消息内容完全由发送者控制,转述时可以随意改,接收者无法验证「某某确实说过这句话」(p.11)。

下一讲

下界说人少了不行。下一页的 OM 算法说明,人数达到 3m+1 时确实能做到,代价是一层套一层的转述。见 L07c。

下一讲 →
L07c L07c 口头消息算法 OM(m):转述一层套一层,最后数票

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。