L10c 为什么非得三轮投票:锁早了卡死,锁晚了分叉
从零讲 HotStuff 为什么要 Prepare、Pre-Commit、Commit 三轮投票:课件 p.16 锁在 Commit 丢活性,p.17 锁挪到 Decide 丢安全性,三阶段靠 2f+1 份证据和 f+1 的重叠两头都顾上。
一句话版
一个副本要「上锁」,承诺以后不给冲突的块投票。锁上得太早,别人手里没证据,新 leader 说服不了它,系统卡死;锁上得太晚,没人被约束,坏 leader 能让诚实节点执行两个不同的块。HotStuff 用三轮投票把「存证据」「上锁」「执行」分开,两头都顾上。
这一页接着上一页 L10b 的换 leader 讲。新 leader 挑最高 QC 的规则,要和这里的锁配合才完整。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 安全性 | safety | 坏事不会发生:诚实节点不会执行冲突的块 |
| 活性 | liveness | 好事终将发生:系统总能继续出块 |
| lockedQC | 锁 | 副本承诺「以后只给从这个块延伸的提案投票」 |
| prepareQC | 证据 | 证明一个块拿到过 2f+1 张 Prepare 票 |
| 冲突的块 | conflicting block | 和已有块在同一高度、不在同一条链上的块 |
| safeNode | 投票规则 | 副本决定投不投一个提案的判断条件 |
一个类比:订会议室
一间会议室,大家要商量出同一个预订时段。有个人先在门口贴了「已订」,从此不让别人改时段,这就是上锁。
如果他贴得太早,其他人根本不知道这个时段被提过。新的组织者来了,提了另一个时段,贴条的人死活不同意,其他人又凑不够数,会议一直订不下来。
如果大家等到最后一刻才贴,中间谁都可以反悔。捣乱的人分头告诉不同的人不同时段,最后两拨人去了两个时间,各开各的会。
三轮投票的做法是:先让多数人都把「这个时段被提过」记下来,再贴「已订」,最后才真的去开会。
类比在哪里失效:
- 会议室里大家能当面对质,协议里的节点只能看消息,消息还会迟到。
- 协议里的「记下来」是一张门限签名的 QC,伪造不了;纸条可以伪造。
- 捣乱的人在协议里最多 f 个,类比里没有这个上限。
从零讲起
1. 安全性与活性
它解决什么问题
后面两个反例,一个说「丢活性」,一个说「丢安全性」。先把这两个词分清楚,才知道每个反例坏在哪里。
从哪来(补充)
这对词的提法是「坏事不会发生」与「好事终将发生」。Leslie Lamport 在 1977 年的论文里用了它们,论文名是「Proving the correctness of multiprocess programs」。
出处:Wikipedia: Safety and liveness properties
直觉
安全性看「做没做错事」。只要有一刻两个诚实节点执行了冲突的块,安全性就破了,事后没法补救。
活性看「有没有往前走」。系统暂时卡住、等一会儿又恢复,不算破坏安全性,但如果永远卡住,活性就没了。
共识协议两样都要。只要安全性很容易:什么都不做,就永远不会做错。只要活性也很容易:谁提什么都接受。难的是两样同时有。
一步一步看
目标:学会看一个反例的结局,判断坏掉的是活性还是安全性。
-
拿到一个反例,先找最后的结局:系统是卡住了,还是有节点执行了不同的块。
-
如果结局是「凑不够票、视图卡住」,坏掉的是活性。
-
如果结局是「诚实节点 B 执行 X,诚实节点 C 执行 Y」,坏掉的是安全性。
结局 坏掉的性质 能不能事后补救 凑不够票、视图卡住 活性 换 leader 后可能恢复 诚实节点执行冲突的块 安全性 不能,已经执行了 -
只看诚实节点。拜占庭节点自己执行什么不算数。
怎么判断
问两个问题:
- 有没有两个诚实节点执行了冲突的块?有 → 安全性被破坏。
- 系统是否可能永远凑不出新的 QC?是 → 活性被破坏。
意思是:先看「做错」,再看「不动」,两个问题分开问。
常见误解
以为系统卡住就是不安全
卡住时没有人执行错误的块,安全性还在,坏掉的是活性。不安全指的是诚实节点执行了冲突的块。
以为拜占庭节点执行了别的块也算破坏安全性
安全性只约束诚实节点。拜占庭节点本来就可能乱来,协议保证的是诚实节点之间一致。
试一下
四个节点里 A 是拜占庭,A 执行了 Y,B、C、D 都执行 X。安全性破了吗?
没破。诚实的 B、C、D 执行的是同一个块。
某个视图里只凑到 2 票,下一个视图换了诚实 leader 后又正常出块。这算丢活性吗?
不算。暂时卡住后能恢复,活性还在。下一节的「锁太早」反例说的是会一直卡住的情形。
2. 锁上得太早:两阶段锁在 Commit,丢活性
它解决什么问题
最直接的想法是省掉一轮:Prepare 凑出 QC 后,下一轮就上锁。课件用一个反例说明这样会卡死。
直觉
B 锁在 X,可是全网能证明 X 的 QC 只在 A 和 B 手里。A 是坏人,把 QC 藏起来;B 的消息又迟到了。新 leader 看不到 X,提了一个冲突的块,B 不肯投,A 也不投,剩下的票凑不够。
问题出在 B 锁的时候,「X 被认可过」这件事还没有扩散到足够多的人手里。
一步一步看
目标:看锁在 Commit 就上时,坏 leader 怎样让视图卡住、丢掉活性。
设定:n = 4,f = 1,A 是拜占庭 leader。流程只有两轮:Prepare → Commit,收到 Commit 就上锁。
-
A 用 A、B、C 的票凑出 prepareQC(X)。
-
A 只把 Commit 发给 B,B 锁在 X。C、D 什么也没收到。
-
换到 D 当 leader。D 收到 A、C、D 的 New-View:A 藏起了 QC,B 的消息迟到。D 不知道 X,提出冲突的 Y。
-
B 锁在 X,拒绝 Y;A 故意不投。只有 C、D 两票,凑不出 QC,视图卡住。
怎么判断
一个锁会不会卡死系统,看上锁那一刻有多少诚实节点存了对应的 QC:
- 如果能保证新 leader 收的 n−f 份 New-View 里一定有人交出这张 QC,新 leader 就能提延伸 X 的块,锁住的人会投票。
- 如果像这里一样,QC 只在坏人和锁住的人手里,新 leader 可能完全看不到,锁住的人就会一直拒绝。
意思是:锁本身没错,错在上锁前证据没扩散够。
常见误解
以为 D 是坏人,故意提冲突的块
D 是诚实的,它照规矩挑了收到的最高 QC。只是它收到的 3 份里没有 prepareQC(X),所以不知道 X。
以为这里破坏的是安全性
没有诚实节点执行冲突的块,Y 根本凑不出 QC。坏掉的是活性:系统卡住了。
试一下
如果第 3 步里 B 的 New-View 没有迟到,D 收到的是 B、C、D 三份,会怎样?
B 会交出 prepareQC(X),D 看到它就会提延伸 X 的块,B 能投票,系统不卡。反例靠的正是 B 的消息迟到。
这个反例里,A 一共做了几件坏事?
两件:只把 Commit 发给 B,以及在 New-View 里藏起 QC、不给 Y 投票。
3. 锁上得太晚:锁挪到 Decide,丢安全性
它解决什么问题
既然锁早了会卡死,那就晚点锁,等到最后的 Decide 才锁。课件的第二个反例说明,这样又会让诚实节点执行不同的块。
直觉
锁挪到 Decide 后,中间那一轮的 QC 只是证据,谁也不受它约束。C 手里明明有 prepareQC(X),但它没上锁,坏 leader 再来提一个同高度的 Y,C 照样投。
B 已经执行了 X,C、D 又执行了 Y,账本分叉。
一步一步看
目标:看锁挪到 Decide 后,诚实节点怎样在同一高度执行两个不同的块。
设定:n = 4,f = 1,A 是拜占庭 leader。流程:Prepare → Precommit → Decide,收到 Decide 才上锁。
-
prepareQC(X) 形成,B、C 存下它。这张 QC 现在只是证据。
-
B、C 投了 precommit,A 凑出 precommitQC(X),只把 Decide 发给 B。B 这时才上锁,并且执行 X。
-
A 之后再当 leader,在同一高度提 Y,justify 用旧父块的 QC。C 没锁,可以投;A、D 也投,Y 一路拿到 prepareQC(Y) 和 precommitQC(Y)。
-
C、D 执行 Y。B 执行的是 X。同一高度上,诚实节点执行了两个不同的块。
怎么判断
检查一个设计会不会丢安全性:在某个块被执行之前,是否已经有足够多的诚实节点被锁住?
- 被锁住的人不会给冲突的块投票。只要锁住的诚实节点够多,冲突的块就凑不出 2f+1 票。
- 这里执行 X 时只有 B 一个人锁了,C、D 都自由,冲突的 Y 轻松凑够 3 票。
意思是:执行之前必须先有一轮「上锁」扩散到多数人手里。
常见误解
以为 C 存了 prepareQC(X) 就不会投 Y
存 QC 只是保留证据,不是承诺。只有 lockedQC 才会限制以后的投票。
以为 A 提 Y 时用旧父块的 QC 是违规的
旧父块的 QC 是真的,A 只是没拿出更新的那张。C、D 没有被锁,按规则可以接受。
试一下
如果第 2 步里 Decide 也发给了 C,C 上了锁,第 3 步的 Y 还能凑够票吗?
不能。C 锁在 X,会拒绝 Y;只剩 A、D 两票,少于 3 票。
「锁太早」和「锁太晚」这两个反例,哪个坏的是安全性?
锁太晚那个。B 执行 X,C、D 执行 Y。
4. 三阶段怎样两头都顾上
它解决什么问题
前两个反例给出两条要求:上锁前证据要扩散到足够多的人,执行前锁要扩散到足够多的人。三阶段用多出来的一轮同时满足它们。
直觉
三轮投票的顺序是这样的。Prepare 凑出 prepareQC,大家存下证据。Pre-Commit 凑出 precommitQC,大家上锁。Commit 凑出 commitQC,大家执行。
B 一旦锁在 X,说明 precommitQC(X) 已经形成,至少 2f+1 个副本投过 precommit 票。投这一票的前提是存了 prepareQC(X)。新 leader 收的 n−f 份 New-View 一定和这 2f+1 个人有交集,交集里至少有一个诚实节点会交出 prepareQC(X)。
一步一步看
目标:看三阶段怎样先存证据、再上锁、最后执行,换 leader 时新 leader 为什么不会卡住。
-
先存证据:Prepare 阶段凑出 prepareQC(X),副本在 Pre-Commit 阶段收到它并存下。
-
再上锁:Pre-Commit 阶段凑出 precommitQC(X),副本在 Commit 阶段收到它,设 lockedQC。
-
最后执行:Commit 阶段凑出 commitQC(X),副本在 Decide 阶段收到它,执行 X。
-
换 leader 时数一下交集:存了证据的 2f+1 个,和新 leader 收的 n−f 份 New-View,至少重叠 f+1 个。
-
f+1 个里坏人最多 f 个,至少 1 个诚实,新 leader 一定拿得到 prepareQC(X),提案要么延伸 X,要么带着更高的 QC。B 能投票,系统不卡。
怎么算
两个集合的重叠下限:
重叠 ≥ (2f+1) + (n−f) − n = f+1
意思是:存了证据的 2f+1 个人和交了 New-View 的 n−f 个人加起来超过 n。多出来的那部分就是两边都有的人,至少 f+1 个。坏人最多 f 个,所以至少 1 个诚实。
副本投票前用 safeNode 规则判断,满足其一就投:
| 条件 | 叫法 | 保证什么 |
|---|---|---|
| 提案从 lockedQC 指向的块延伸出来 | 安全规则 | 不给冲突的块投票 |
| 提案的 justify QC 视图号比 lockedQC 更高 | 活性规则 | 有更新的证据时可以解锁 |
意思是:第一条守住安全,第二条让锁住的人在看到更新的证据时愿意跟着走,守住活性。
常见误解
以为加一轮只是为了多一次确认,更保险
加的这一轮有具体分工:把「存证据」和「上锁」拆到两轮,保证上锁时证据已在 2f+1 人手里。少了它就回到锁太早的反例。
以为锁住之后永远不能解开
safeNode 的第二条允许解锁:提案带着视图号更高的 QC 时,即使不延伸锁住的块,也可以投票。
试一下
n = 4 时,存了 prepareQC(X) 的至少几个,New-View 至少几份,至少重叠几个?
3 个、3 份,重叠至少 3 + 3 − 4 = 2 个。
B 锁在视图 5 的块 X,新提案 Y 不延伸 X,但带了视图 6 的 QC。B 投不投?
投。满足 safeNode 的活性规则:justify 的视图号 6 比锁的 5 高。
把它们串起来
上一页讲新 leader 挑最高的 QC 往下接,这一页回答为什么这样接不会出问题。
锁是副本的承诺:以后不给冲突的块投票。
第一个反例锁在第二轮。上锁时证据只在少数人手里,新 leader 看不到,锁住的人拒绝投票,系统卡死,丢的是活性。
第二个反例锁挪到最后。执行前几乎没人被约束,坏 leader 让诚实节点执行了两个不同的块,丢的是安全性。
三阶段把顺序排成存证据、上锁、执行。上锁前已有 2f+1 人存了 prepareQC。新 leader 收的 n−f 份 New-View 必定和他们重叠 f+1 个,至少一个诚实节点会把证据交出来。safeNode 规则再给锁留一个出口:看到更高的 QC 就可以跟着走。
三轮投票每个块要走三遍,能不能省?下一页的 Chained HotStuff 把三轮叠成流水线。
课件里的坑
- [读图提醒] 两阶段反例里其实有两轮投票(Prepare-Vote 和 Commit-Vote),只是锁放在第二轮。「两阶段」指的是投票轮数,不要和四个阶段名混着数(p.16)。
- [读图提醒] 反例最后写「2 < 3」,意思是只有 C、D 两票,少于 quorum 3(p.16)。
- [课件没单列] 副本投票的 safeNode 规则课件没有单独一页,是从原论文补的。答「为什么三阶段能保住活性」时要用到它(p.16–17)。
课后 10 分钟:考点复习
这 10 分钟怎么用:先合上页面,各用一句话说出 p.16 和 p.17 的结局分别坏了哪个性质;再写出重叠下限的算式;然后做完整例题和变式题。
必背
- 安全性(safety)是坏事不会发生,比如诚实节点不会执行冲突的块;活性(liveness)是好事终将发生,比如系统总能继续出块
- 两阶段锁在 Commit 会丢活性(锁住的副本拒绝新提案,凑不够票);锁挪到 Decide 会丢安全性(不同副本执行不同块)
- 三阶段顺序:先存 prepareQC(证据)→ 再设 lockedQC(锁)→ 再执行,lock restricts future conflicting votes
- safeNode 规则:提案从 lockedQC 指向的块延伸出来,或提案的 justify QC 视图号比 lockedQC 更高,二者满足其一就投票
- 上锁前已有 2f+1 个副本存了 prepareQC(X),新 leader 收的 n−f 个 New-View 与之至少重叠 f+1 个,其中至少 1 个诚实
课件例题
例 1(课件 p.16):两阶段版为什么卡死
流程 Prepare → Prepare-Vote → Commit(带 prepareQC)→ Commit-Vote → Decide,A 是拜占庭 leader。说出卡死的步骤和原因。
提示
数一下 B 上锁时,有几个诚实节点手里有 prepareQC(X)。
解答
A 用 A、B、C 的票形成 prepareQC(X),只把 Commit 发给 B,B 锁在 X。新 leader D 收 A、C、D 的 New-View,A 藏起 QC,B 的消息迟到,D 提出冲突的 Y。B 因锁在 X 拒绝,A 不投,只有 C、D 两票,少于 3,视图卡住,是活性问题。原因:B 锁了,但别人手里没有能说服新 leader 的 QC。
例 2(课件 p.17):锁挪到 Decide 为什么分叉
流程 Prepare → Prepare-Vote → Precommit → Precommit-Vote → Decide。说出分叉的步骤。
提示
C 存了 prepareQC(X),它受约束吗?
解答
prepareQC(X) 形成;B、C precommit,A 形成 precommitQC(X),此时还没人上锁。Decide 只发给 B,B 上锁并执行 X。A 之后再当 leader,在同一高度提 Y,justify 用旧父块的 QC。C 手里的 prepareQC(X) 不是锁,A、C、D 投票,形成 prepareQC(Y) 和 precommitQC(Y),C、D 执行 Y。B 执行 X、C 和 D 执行 Y,安全性被破坏。
完整例题
题目:把 p.17 的攻击放到真正的三阶段 HotStuff 里重演。A 是拜占庭 leader,n = 4。A 凑出 precommitQC(X) 后只把 Commit 发给 B,B 锁在 X。之后 A 想在同一高度提冲突的 Y,justify 用旧父块的 QC。攻击能成功吗?如果换成诚实的新 leader D,B 会不会卡住?
解法:
第一步,看谁存了证据。precommitQC(X) 形成,说明至少 3 个副本投了 precommit 票,它们都存了 prepareQC(X)。设为 A、B、C。
第二步,看 Y 能拿到几票。Y 不延伸 X,justify 的视图号比 X 那轮旧。B 锁在 X,按 safeNode 两条都不满足,拒绝。C 没锁,可以投;D 也可以投。加上 A,最多 3 票。
第三步,看谁会执行 X。X 要被执行需要 commitQC(X),也就是 3 张 Commit 票,投 Commit 票的前提是收到 precommitQC(X) 并锁在 X。现在只有 B 收到了,加上 A 自己最多 2 票,commitQC(X) 凑不出来,没有诚实节点执行 X。所以 Y 即使靠 A、C、D 三票一路走到被 C、D 执行,也不会出现「B 执行 X、C 和 D 执行 Y」的分叉,攻击不成功。
反过来,如果 A 把 Commit 发给了足够多的人,commitQC(X) 已经形成,就有 3 个节点锁在 X,其中至少 2 个诚实。它们都会拒绝 Y,Y 最多拿到 A 和剩下那个诚实节点的 2 票,凑不出 QC。两种情况都不分叉。
第四步,换成诚实 leader D。D 收 3 份 New-View,至少 2 份来自存了 prepareQC(X) 的 A、B、C,其中至少 1 个诚实,D 一定看到 prepareQC(X),提延伸 X 的块,B 能投票。
要点:三阶段下,执行前锁已扩散到多数,冲突的块凑不够票;上锁前证据已扩散到多数,诚实新 leader 一定看到最高 QC。
答题格式:谁存了证据 → 谁上了锁 → 冲突提案能拿几票 → 诚实新 leader 能否看到证据。
变式题(先自己做)
1. n = 7。已有 5 个副本存了 prepareQC(X),新 leader 收 5 份 New-View。至少重叠几个?其中至少几个诚实?(改编自课件 p.16–17 的论证)
提示
先算 f,再用重叠下限公式。
判分点与答案(非官方评分标准)
f = 2,2f+1 = 5,n−f = 5。重叠 ≥ 5 + 5 − 7 = 3 = f+1。坏人最多 2 个,至少 1 个诚实。判分点:算出 f = 2;写出重叠公式;结论至少 1 个诚实,新 leader 一定拿得到 prepareQC(X)。
2. 自编情境:副本 C 锁在视图 4 的块 X。下面两个提案它投不投?(a) Y 延伸 X,justify 是视图 4 的 QC;(b) Z 不延伸 X,justify 是视图 3 的 QC。
提示
逐条对 safeNode 的两个条件。
判分点与答案(非官方评分标准)
(a) 投,满足安全规则(延伸锁住的块)。(b) 不投,不延伸 X,且视图 3 不高于锁的视图 4,两条都不满足。判分点:两个条件各对一次;(b) 说清两条都不满足。
闪卡自测
1. 安全性和活性各是什么?
安全性:坏事不会发生;活性:好事终将发生(Lamport 1977 的提法)。
2. p.16 的两阶段版坏了哪个性质?
活性:B 锁在 X 拒绝 Y,A 不投,只剩 2 票(p.16)。
3. p.16 的反例里,D 为什么看不到 X?
A 藏起了 QC,B 的 New-View 迟到(p.16)。
4. p.17 锁挪到 Decide 坏了哪个性质?
安全性:B 执行 X,C、D 执行 Y(p.17)。
5. p.17 里 C 存了 prepareQC(X),为什么还会投 Y?
存 QC 只是证据,不是锁(p.17)。
6. 三阶段的顺序是什么?
先存 prepareQC,再设 lockedQC,再执行。
7. safeNode 的两个条件是什么?
提案延伸 lockedQC 指向的块;或提案 justify 的视图号比 lockedQC 高。
8. 重叠下限 f+1 是怎么来的?
(2f+1) + (n−f) − n = f+1。
下一讲
下一页是 L10d 门限签名:一张 QC 里的 2f+1 份部分签名,是怎样合成一个签名的。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。