← COMP5567 全部讲次
L07e · 第 7 周

L07e 签名消息算法 SM:叛徒没法冒充别人

从数字签名讲起,看签名怎样一层层嵌套;走一遍三将军的 SM,看叛徒指挥官怎样被自己的签名揭穿;最后把 OM 和 SM 放进一张表对照。

一句话版

给每条命令加上不可伪造的签名,转述时原签名必须跟着走。叛徒没法再谎报别人说过什么,指挥官发矛盾命令也会留下证据,于是人数门槛从 3m+1 降到 m+1。

前一页算了 OM 的代价,见 L07d。这一页回到本讲的第二种解法:签名消息,简称 SM。

先认识这几个词

词 全称 / 读法 一句人话
数字签名 digital signature 只有签名者能签、谁都能验的电子印章
私钥 / 公钥 private / public key 私钥自己藏着用来签,公钥公开给别人验
PKI Public Key Infrastructure 公钥基础设施,让大家确认某个公钥属于谁
(A)_C 读作「C 签的 A」 指挥官 C 对命令 A 签了名
SM(m) Signed Messages 带签名转发、能容忍 m 个叛徒的算法
Vᵢ 副官 i 的命令集合 副官 i 收到过的所有不同命令
choice 选择函数 对命令集合做最终决定的固定规则

一个类比:盖了章的公文

口头传话时,下属说「老板让我们撤」,你没法核实。换成老板盖章的公文,下属转交时只能原样转,改了内容,章就对不上。

假如老板给甲一份「进攻」、给乙一份「撤退」,两份都盖了他的章。乙把两份摆在一起,谁都能看出是老板自己出尔反尔。

类比在哪里失效:

  • 真实的公章能被仿刻,数字签名的前提是没人能伪造忠诚者的签名。
  • 公文可以当众摆出来,SM 里的「出示证据」是通过点对点转发完成的。
  • 叛徒之间可以互相伪造签名、串通作假,这一点公章类比体现不出来。

从零讲起

1. 数字签名(补充)

它解决什么问题

OM 的麻烦在于,副官 j 说「指挥官跟我说的是 R」,别人没法核实。只要能让「谁说了什么」变得可验证,叛徒就失去了最重要的武器。数字签名就是这样一个工具。

从哪来(补充)

Whitfield Diffie 和 Martin Hellman 在 1976 年首次描述了数字签名方案的概念。签名算法用私钥,验证算法用公钥,任何持有公钥的人都能验证。出处:Wikipedia: Digital signature。

直觉

每位将军有一把只有自己知道的私钥,和一把公开的公钥。用私钥签过的消息,谁都能用公钥验证它确实来自这个人、内容没被改过。

转发时不拆原来的签名,在外面再包一层自己的签名。这样消息走过的每一个人都留下了记录。

一步一步看

目标:看签名一层层嵌套后,收信人怎样核出原命令是谁签的,中间人又为什么改不了内容。

  1. 指挥官 C 用自己的私钥给「进攻」签名,得到 (A)_C。

  2. C 把 (A)_C 发给 L1。L1 用 C 的公钥验证,确认这条命令确实是 C 签的。

  3. L1 要转发给别人,就在外面再签一次,得到 ((A)_C)_L1。

    签名嵌套示意:左边框里是 C 签的进攻 (A)_C,箭头写着 L1 转发;右边青绿框写着 L1 在外面再签一次,里面是 ((A)_C)_L1,并注明里面仍是 C 的原签名

  4. 收到 ((A)_C)_L1 的人,先验外层,知道是 L1 转来的;再验里层,知道原命令是 C 签的 A。

  5. 如果 L1 把里面的 A 改成 R,C 的签名就验不过。L1 只能原样转发,或者干脆不转。

怎么判断

拿到一条带签名的消息,按下面的顺序判断:

  1. 从外往里,逐层用对应的公钥验签名。
  2. 任何一层验不过,整条消息作废。
  3. 全部验过,最里层就是原始命令,括号外的名字依次是经手人。

课件把签名后的新假设写成三条「证明的力量」:叛徒不能谎报别人说过什么;忠诚者的消息无法伪造;指挥官给不同人发不同命令,会留下自己签名的矛盾证据。

原论文把这条假设记为 A4:忠诚将军的签名无法伪造,内容被改能被发现,任何人都能验证签名。

常见误解

以为有了签名,叛徒唯一能做的就是不转发

课件里「叛徒只能拒绝转发」这句话说得过满。叛徒还能选择性地转发,叛徒指挥官能签发互相矛盾的命令,原论文也允许叛徒之间互相伪造对方的签名。准确的说法是:叛徒无法伪造忠诚者的消息。

试一下

L2 收到 ((R)_C)_L1。这条消息说明了什么?L1 能不能把它改成 ((A)_C)_L1?

说明 L1 转来了一条 C 签的撤退命令。L1 改不了:里面那层是 C 的签名,内容改成 A 后,用 C 的公钥验证会失败。

2. SM 算法:签名转发加命令集合

它解决什么问题

有了签名,还需要一套规则:谁转发、转发几次、最后怎么决定。SM 算法回答这三件事,并且只要 n ≥ m+1 就能工作。

直觉

每个副官手里放一个命令集合 Vᵢ,只记收到过的不同命令。收到新命令就放进去,加签转给还没签过的人。

签名保证所有忠诚副官最后拿到同一个集合。集合一样,再用同一个规则做决定,结果自然一致。

一步一步看

目标:看叛徒指挥官发两种命令时,签名怎样让两位忠诚副官拿到同一个集合、做出同一个决定。

课件用 n = 3、m = 1 演示,指挥官 C 是叛徒。这正是上一页三将军反证里让口头消息无解的场景,只是加上了签名。

  1. C 给 L1 签发 (A)_C,给 L2 签发 (R)_C。两条都带 C 的真签名。

    签名消息第 1 步:上方虚线圈 C 标为叛徒,两条青绿箭头分别写着 (A)_C 指向 L1、(R)_C 指向 L2,L1 和 L2 都忠诚

  2. 两位副官各自加签转发。L1 把 ((A)_C)_L1 发给 L2,L2 把 ((R)_C)_L2 发给 L1。

    签名消息第 2 步:第 1 步的两条箭头变浅,L1 和 L2 之间两条青绿箭头分别写着 ((A)_C)_L1 和 ((R)_C)_L2

  3. L2 手里有 (R)_C 和 ((A)_C)_L1,两条都带 C 的签名,内容相反。这证明 C 是叛徒,L2 没法编造其中任何一条。

    签名消息第 3 步:L2 描成青绿,下方青绿框写着 (R)_C 和 ((A)_C)_L1,说明两条命令都有 C 的签名、内容相反

  4. L1 和 L2 的集合都是 {A, R}。用同一个 choice 规则,两人做出同一个决定。

对比口头消息版:同样的消息流,口头消息下 L1 分不清「C 撒谎」和「L2 撒谎」;有签名时,L2 转来的 R 上有 C 的签名,只可能是 C 发了两种命令。

怎么判断

SM(m) 三步:

  1. 指挥官签名后,把命令发给所有副官。
  2. 副官 i 收到一条命令:如果它不在 Vᵢ 里,就放进 Vᵢ;签名还不到 m+1 层,就加签转给还没签过的副官。已经在 Vᵢ 里的命令不再转发。
  3. 等不会再有新消息时(靠超时判断),执行 choice(Vᵢ)。

choice 只需满足两条:Vᵢ 只有一个元素 v 时,结果是 v;Vᵢ 为空时,结果是 RETREAT。

意思是:集合里只有一种命令就照办,什么都没收到就撤退。集合里有两种命令时用什么规则,只要所有人约定同一个即可,常见的约定是撤退。

常见误解

以为 SM 最后也是对消息条数取多数

课件算法第 3 步写了「majority rule」。原论文用的是对命令集合的 choice 函数。签名保证忠诚副官拿到同一个集合,不需要数票。

以为 Vᵢ 记的是收到的消息条数

Vᵢ 是不同命令的集合。L3 转来的 R 如果已经在集合里,就不再处理,集合大小不变。

试一下

n = 3、m = 1,C 忠诚,给 L1、L2 都签发 R。L2 是叛徒,想告诉 L1「C 跟我说的是 A」。它做得到吗?L1 怎么决定?

做不到。L2 手里只有 (R)_C,伪造不出 C 签的 A。L2 只能转发 ((R)_C)_L2 或者不发。L1 的集合是 {R},choice 结果为 R,和忠诚的指挥官一致。

3. OM 和 SM 对照

它解决什么问题

考试常让你把两种算法并排比较。课件给了一张对照表,这一节把它读懂,重点是两个门槛数和两条共同假设。

直觉

OM 下叛徒能随意撒谎,所以要靠人数压:忠诚者必须超过三分之二。SM 下叛徒没法伪造忠诚者的话,只要还有忠诚者在,他的签名消息就能和伪造的区分开。

代价是 SM 多要了一套密码学基础设施。两者都还要同步网络,靠超时判断「对方没发」。

一步一步看

目标:逐项对照 OM 和 SM,看 SM 多要一套 PKI,在门槛和复杂度上换来了什么。

  1. 看假设:OM 要同步网络;SM 要同步网络加 PKI。
  2. 看门槛:OM 要 n ≥ 3m+1;SM 要 n ≥ m+1。
  3. 看复杂度:OM 是 O(nᵐ),老师在旁边写了「exponential」;SM 一格写「Polynomial」。
  4. 看叛徒能做什么:OM 下可以随意撒谎;SM 下无法伪造消息。
  5. 看实用性:OM 代价高,实用性低;SM 较高,但需要密码学基础设施。
维度 OM SM
假设 同步网络 同步网络 + PKI
容错 n ≥ 3m+1 n ≥ m+1
复杂度 O(nᵐ) 多项式
叛徒能力 可以随意撒谎 无法伪造消息
实用性 低(代价高) 较高(需要密码学基础设施)

怎么判断

问「m 个叛徒至少要几位将军」时,先看是口头消息还是签名消息:

  • 口头消息:n ≥ 3m+1。
  • 签名消息:n ≥ m+1。

意思是:签名消息下,叛徒之外只要还有将军,问题就有意义。原论文的说法是 SM(m) 对任意数量的叛徒都成立,少于 m+2 位将军时问题是空的,叛徒之外最多只剩一个人。

常见误解

以为签名能去掉同步网络的假设

不能。SM 仍要靠超时判断「不会再有新消息」,课件的对照表里两者都写了 Synchronous Network。

以为「Polynomial」是原论文的结论

1982 年原论文的 SM(m) 允许消息逐层带最多 m 层副官签名转发,副本数也随层数连乘增长。表里的「多项式」应理解为签名方案经后续改进能做到的复杂度。答题照课件写「Polynomial」即可。

试一下

要容忍 2 个叛徒,口头消息和签名消息各至少要几位将军?

口头消息 3 × 2 + 1 = 7 位;签名消息 2 + 1 = 3 位。

把它们串起来

数字签名让「谁说了什么」变成能验证的事实。每次转发在外面加一层签名,里面的原签名不变,叛徒只能原样转或者不转。

SM 用这一点改掉了 OM 的多数表决。每个副官只记不同命令的集合,签名保证忠诚副官最后拿到同一个集合,再用同一个 choice 规则,结果必然一致。叛徒指挥官发矛盾命令时,集合里会出现两种都带他签名的命令,证据自己暴露出来。

所以门槛从 3m+1 降到 m+1。代价是要一套 PKI,同步网络的假设也还在。

课件里的坑

  • [读图提醒] p.20「The only malicious action is to refuse to forward」说得过满,叛徒指挥官还能签发矛盾命令,叛徒之间也能互相伪造签名(p.20)。
  • [读图提醒] p.22 第 3 步写「majority rule」;原论文对命令集合用 choice 函数。签名保证忠诚副官拿到同一集合,同一规则下结果自然一致(p.22)。
  • [读图提醒] p.24 SM 复杂度一格写「Polynomial」,不是 1982 年原论文给出的结论,答题照课件写即可(p.24)。
  • [对照记忆] p.21 是 p.12 的「签名版」:同样 3 个人、叛徒指挥官发矛盾命令,口头消息下分不清,签名消息下立刻暴露(p.12、p.21)。

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先把 p.12 和 p.21 的三将军图并排画出来,写清两者差在哪;再按 p.23 的题目写出三位副官的命令集合;最后默写 OM 和 SM 的对照表。

必背

  1. 签名消息让叛徒无法伪造忠诚者的消息,叛徒指挥官签发矛盾命令会被识破
  2. SM 每转发一次追加一层签名,副官维护命令集合 Vᵢ,最后用同一个 choice 规则做决定
  3. choice 规则:Vᵢ 只有一个元素 v 时取 v,Vᵢ 为空时取 RETREAT
  4. OM 需 n ≥ 3m+1,SM 需 n ≥ m+1,两者都假设同步网络;SM 还需要 PKI
  5. p.23 Exercise 1:L1、L2、L3 的集合都是 {ATTACK, RETREAT},按同一 choice 规则得到同一结果

课件例题

例 1(课件 p.21):签名让叛徒指挥官暴露

n = 3、f = 1,C 是叛徒,给 L1 签发 A、给 L2 签发 R,L1 把带签名的 A 转给 L2,L2 把 R 转给 L1。L2 能得出什么结论?

提示

对比 p.12:同样的消息流,看 L2 手里两条命令的签名分别是谁的。

解答

L2 手里有 (R)_C 和 ((A)_C)_L1,两条都带 C 的签名、内容相反,证明 C 是叛徒,L2 可以把证据出示给 L1。口头消息下 L1 无法区分「C 撒谎」和「L2 撒谎」;有了签名,L2 编造不出带 C 签名的 R。

例 2(课件 p.23,Exercise 1):补全 SM

C 是叛徒,n = 4(C + L1–L3),给 L1 发 ATTACK,给 L2、L3 发 RETREAT;L1 把带 C、L1 签名的 ATTACK 转给 L2、L3。补全 SM,写出每位副官的命令集合和决定。

提示

L2、L3 收到 C 的 RETREAT 后,也要加签转发给其余两位副官。集合只记不同命令。

解答

L2、L3 把 RETREAT 加签转给其余副官。L1 = {A(C 直发), R(L2、L3 转来)} = {A, R};L2 = {R(C 直发), A(L1 转来)} = {A, R};L3 同理 = {A, R}。L3 转来的 R 已在 L2 集合里,不再处理。三人集合相同,都看到 C 签了两种命令,判定 C 是叛徒;若约定「集合里命令不唯一时撤退」,三人都 RETREAT。

老师的板书记法:L1 的集合列为 (A)_C、((R)_C)_L2、((R)_C)_L3。如果改按 p.22 的「对收到的消息取多数」,L1 收到 (A, R, R)、L2 收到 (R, A, R)、L3 收到 (R, A, R),也都是 R。两种规则在本题结论一致。

例 3(课件 p.24):OM 和 SM 的对照

从假设、容错门槛、复杂度、叛徒能力、实用性五个维度比较 OM 和 SM。

提示

两个必考数是 3m+1 和 m+1;两者共同的假设是同步网络。

解答

假设:OM 同步网络,SM 同步网络 + PKI。容错:OM n ≥ 3m+1,SM n ≥ m+1。复杂度:OM O(nᵐ),SM 课件写 Polynomial。叛徒能力:OM 可随意撒谎,SM 无法伪造消息。实用性:OM 低,SM 较高但需要密码学基础设施。老师在 PKI 旁写了「public key certificate」,在 O(nᵐ) 旁写了「exponential」。

完整例题

题目:n = 4(C + L1–L3)、m = 1,用 SM。C 忠诚,给三位副官都签发 ATTACK。L3 是叛徒,它想让 L1、L2 撤退。写出 L3 能做什么、不能做什么,以及 L1、L2 的命令集合和决定。

解:

  1. 第 1 轮:C 发出 (A)_C 给 L1、L2、L3。
  2. L1、L2 把 A 放进集合,签名只有 1 层,不到 m+1 = 2 层,于是各自加签转发:L1 发 ((A)_C)_L1 给 L2、L3;L2 发 ((A)_C)_L2 给 L1、L3。
  3. L3 能做的:不转发;或者原样加签转发 ((A)_C)_L3。
  4. L3 不能做的:伪造 (R)_C。它手里没有 C 签的撤退命令,把 A 改成 R,C 的签名就验不过。
  5. L1 的集合:C 直发的 A,L2 转来的 A,L3 转不转都只可能是 A,所以 V₁ = {A}。L2 同理 V₂ = {A}。
  6. choice 规则:集合只有一个元素 A,结果是 A。

一句话结论:两位忠诚副官都进攻,和忠诚指挥官一致;L3 最多只能沉默,改变不了任何人的集合。

答题格式:先写每一轮谁发了什么(用嵌套签名记法),再写每位忠诚副官的集合,最后写 choice 结果并用 Agreement / Validity 检验。

变式题(先自己做)

(1) n = 3、m = 1,用 SM。C 是叛徒,只给 L1 签发 ATTACK,什么都不发给 L2。L1、L2 的集合和决定分别是什么?

(2) 同一组将军用 OM 能容忍 1 个叛徒吗?用 SM 呢?

提示

(1) L1 会把 C 签的 ATTACK 加签转给 L2。(2) 分别代入 n ≥ 3m+1 和 n ≥ m+1。

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

判分点:① 写出 L1 的转发和两人的集合;② 说明集合相同所以决定相同;③ 两个门槛数代入正确。

(1) L1 收到 (A)_C,放进集合,加签转发 ((A)_C)_L1 给 L2。L2 的集合也是 {A}。V₁ = V₂ = {A},choice 结果都是 A,两人一致进攻,Agreement 成立。指挥官叛变时 Validity 不要求。

(2) OM 要 n ≥ 3 × 1 + 1 = 4,3 位将军不够,不能容忍;SM 要 n ≥ 1 + 1 = 2,3 位将军够了。

闪卡自测

1. 签名消息给叛徒加了什么限制?

叛徒无法伪造忠诚者的消息,转述必须带原签名;叛徒指挥官签发矛盾命令会留下证据(p.20–21)。

2. p.21 里 L2 怎么知道 C 是叛徒?

L2 手里两条命令都带 C 的签名、内容相反,只可能是 C 发了两种命令(p.21)。

3. SM 的 choice 规则只需满足哪两条?

Vᵢ 只有一个元素 v 时结果是 v;Vᵢ 为空时结果是 RETREAT(p.22 补充,来源 1982 年原论文)。

4. 为什么 SM 不需要多数表决?

签名保证所有忠诚副官最终拿到同一个命令集合,同一个确定性规则下结果自然一致(p.22)。

5. p.23 Exercise 1 中三位副官的集合是什么?

都是 {ATTACK, RETREAT};若约定冲突时撤退,三人都 RETREAT(p.23)。

6. 为什么签名能把下界从 3m+1 降到 m+1?

叛徒无法伪造忠诚者的签名,转述内容可验证;只要至少有一位忠诚将军,他的签名消息就能和伪造的区分开(p.20–24)。

7. OM 和 SM 都需要什么网络假设?SM 还多需要什么?

都需要同步网络;SM 还需要 PKI(p.24)。

8. p.24 表里 SM 的「Polynomial」怎么理解?

不是 1982 年原论文给出的结论,理解为签名方案经后续改进能做到的复杂度;答题照课件写即可(p.24)。

下一讲

OM 和 SM 都离不开同步网络。下一讲回到崩溃故障模型,但去掉同步假设:VR 和 Paxos 怎样在异步网络里保证安全。见 L08a。

下一讲 →
Lab2 Lab 2 把 3PC 跑起来:多出来的 PreCommit 和协调者崩溃恢复

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