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。
直觉
每位将军有一把只有自己知道的私钥,和一把公开的公钥。用私钥签过的消息,谁都能用公钥验证它确实来自这个人、内容没被改过。
转发时不拆原来的签名,在外面再包一层自己的签名。这样消息走过的每一个人都留下了记录。
一步一步看
目标:看签名一层层嵌套后,收信人怎样核出原命令是谁签的,中间人又为什么改不了内容。
-
指挥官 C 用自己的私钥给「进攻」签名,得到 (A)_C。
-
C 把 (A)_C 发给 L1。L1 用 C 的公钥验证,确认这条命令确实是 C 签的。
-
L1 要转发给别人,就在外面再签一次,得到 ((A)_C)_L1。
-
收到 ((A)_C)_L1 的人,先验外层,知道是 L1 转来的;再验里层,知道原命令是 C 签的 A。
-
如果 L1 把里面的 A 改成 R,C 的签名就验不过。L1 只能原样转发,或者干脆不转。
怎么判断
拿到一条带签名的消息,按下面的顺序判断:
- 从外往里,逐层用对应的公钥验签名。
- 任何一层验不过,整条消息作废。
- 全部验过,最里层就是原始命令,括号外的名字依次是经手人。
课件把签名后的新假设写成三条「证明的力量」:叛徒不能谎报别人说过什么;忠诚者的消息无法伪造;指挥官给不同人发不同命令,会留下自己签名的矛盾证据。
原论文把这条假设记为 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 是叛徒。这正是上一页三将军反证里让口头消息无解的场景,只是加上了签名。
-
C 给 L1 签发 (A)_C,给 L2 签发 (R)_C。两条都带 C 的真签名。
-
两位副官各自加签转发。L1 把 ((A)_C)_L1 发给 L2,L2 把 ((R)_C)_L2 发给 L1。
-
L2 手里有 (R)_C 和 ((A)_C)_L1,两条都带 C 的签名,内容相反。这证明 C 是叛徒,L2 没法编造其中任何一条。
-
L1 和 L2 的集合都是 {A, R}。用同一个 choice 规则,两人做出同一个决定。
对比口头消息版:同样的消息流,口头消息下 L1 分不清「C 撒谎」和「L2 撒谎」;有签名时,L2 转来的 R 上有 C 的签名,只可能是 C 发了两种命令。
怎么判断
SM(m) 三步:
- 指挥官签名后,把命令发给所有副官。
- 副官 i 收到一条命令:如果它不在 Vᵢ 里,就放进 Vᵢ;签名还不到 m+1 层,就加签转给还没签过的副官。已经在 Vᵢ 里的命令不再转发。
- 等不会再有新消息时(靠超时判断),执行 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,在门槛和复杂度上换来了什么。
- 看假设:OM 要同步网络;SM 要同步网络加 PKI。
- 看门槛:OM 要 n ≥ 3m+1;SM 要 n ≥ m+1。
- 看复杂度:OM 是 O(nᵐ),老师在旁边写了「exponential」;SM 一格写「Polynomial」。
- 看叛徒能做什么:OM 下可以随意撒谎;SM 下无法伪造消息。
- 看实用性: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 的对照表。
必背
- 签名消息让叛徒无法伪造忠诚者的消息,叛徒指挥官签发矛盾命令会被识破
- SM 每转发一次追加一层签名,副官维护命令集合 Vᵢ,最后用同一个 choice 规则做决定
- choice 规则:Vᵢ 只有一个元素 v 时取 v,Vᵢ 为空时取 RETREAT
- OM 需 n ≥ 3m+1,SM 需 n ≥ m+1,两者都假设同步网络;SM 还需要 PKI
- 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 轮:C 发出 (A)_C 给 L1、L2、L3。
- L1、L2 把 A 放进集合,签名只有 1 层,不到 m+1 = 2 层,于是各自加签转发:L1 发 ((A)_C)_L1 给 L2、L3;L2 发 ((A)_C)_L2 给 L1、L3。
- L3 能做的:不转发;或者原样加签转发 ((A)_C)_L3。
- L3 不能做的:伪造 (R)_C。它手里没有 C 签的撤退命令,把 A 改成 R,C 的签名就验不过。
- L1 的集合:C 直发的 A,L2 转来的 A,L3 转不转都只可能是 A,所以 V₁ = {A}。L2 同理 V₂ = {A}。
- 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。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。