← COMP5567 全部讲次
L10c · 第 10 周

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

直觉

安全性看「做没做错事」。只要有一刻两个诚实节点执行了冲突的块,安全性就破了,事后没法补救。

活性看「有没有往前走」。系统暂时卡住、等一会儿又恢复,不算破坏安全性,但如果永远卡住,活性就没了。

共识协议两样都要。只要安全性很容易:什么都不做,就永远不会做错。只要活性也很容易:谁提什么都接受。难的是两样同时有。

一步一步看

目标:学会看一个反例的结局,判断坏掉的是活性还是安全性。

  1. 拿到一个反例,先找最后的结局:系统是卡住了,还是有节点执行了不同的块。

  2. 如果结局是「凑不够票、视图卡住」,坏掉的是活性。

  3. 如果结局是「诚实节点 B 执行 X,诚实节点 C 执行 Y」,坏掉的是安全性。

    结局 坏掉的性质 能不能事后补救
    凑不够票、视图卡住 活性 换 leader 后可能恢复
    诚实节点执行冲突的块 安全性 不能,已经执行了
  4. 只看诚实节点。拜占庭节点自己执行什么不算数。

怎么判断

问两个问题:

  • 有没有两个诚实节点执行了冲突的块?有 → 安全性被破坏。
  • 系统是否可能永远凑不出新的 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 就上锁。

  1. A 用 A、B、C 的票凑出 prepareQC(X)。

    两阶段版第 1 步:A 是拜占庭 leader,用 A、B、C 三票凑出 prepareQC(X);B、C 投了 X,D 没投,此时 QC 只在 A 手里

  2. A 只把 Commit 发给 B,B 锁在 X。C、D 什么也没收到。

    第 2 步:A 只把 Commit 发给 B,B 用青绿框标出,锁在 X;C、D 手里没有 QC,能证明 X 的 QC 只在 A 和 B 手里

  3. 换到 D 当 leader。D 收到 A、C、D 的 New-View:A 藏起了 QC,B 的消息迟到。D 不知道 X,提出冲突的 Y。

    第 3 步:新 leader D 收 A、C、D 的 New-View,A 藏起 QC,B 迟到用虚线画;D 不知道 X,提出冲突的 Y,用青绿框标出

  4. B 锁在 X,拒绝 Y;A 故意不投。只有 C、D 两票,凑不出 QC,视图卡住。

    第 4 步:B 拒绝冲突的 Y,A 不投,只有 C、D 两票,少于 3 票,凑不出 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 才上锁。

  1. prepareQC(X) 形成,B、C 存下它。这张 QC 现在只是证据。

    锁挪到 Decide 的版本第 1 步:prepareQC(X) 形成,B、C 存下它,A 是拜占庭 leader,D 没有,这张 QC 谁也不约束

  2. B、C 投了 precommit,A 凑出 precommitQC(X),只把 Decide 发给 B。B 这时才上锁,并且执行 X。

    第 2 步:A 凑出 precommitQC(X),只把 Decide 发给 B,B 用青绿框标出,锁在 X 并执行 X;C 只存了 prepareQC(X),不算锁

  3. A 之后再当 leader,在同一高度提 Y,justify 用旧父块的 QC。C 没锁,可以投;A、D 也投,Y 一路拿到 prepareQC(Y) 和 precommitQC(Y)。

    第 3 步:A 再当 leader,在同一高度提 Y,用旧父块的 QC;C 没锁,A、C、D 三票投给 Y,Y 拿到 prepareQC 和 precommitQC

  4. C、D 执行 Y。B 执行的是 X。同一高度上,诚实节点执行了两个不同的块。

    第 4 步:最后 B 执行 X,C 和 D 执行 Y,C、D 用青绿框标出,同一高度执行了两个块,账本分叉,安全性被破坏

怎么判断

检查一个设计会不会丢安全性:在某个块被执行之前,是否已经有足够多的诚实节点被锁住?

  • 被锁住的人不会给冲突的块投票。只要锁住的诚实节点够多,冲突的块就凑不出 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 为什么不会卡住。

  1. 先存证据:Prepare 阶段凑出 prepareQC(X),副本在 Pre-Commit 阶段收到它并存下。

  2. 再上锁:Pre-Commit 阶段凑出 precommitQC(X),副本在 Commit 阶段收到它,设 lockedQC。

  3. 最后执行:Commit 阶段凑出 commitQC(X),副本在 Decide 阶段收到它,执行 X。

  4. 换 leader 时数一下交集:存了证据的 2f+1 个,和新 leader 收的 n−f 份 New-View,至少重叠 f+1 个。

    四个节点 R1 到 R4,实线框圈住 R1、R2、R3 表示存了 prepareQC(X) 的 2f+1 个副本,虚线框圈住 R2、R3、R4 表示新 leader 收到的 n−f 份 New-View,重叠的 R2、R3 用青绿框标出,共 f+1 个

  5. 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 的结局分别坏了哪个性质;再写出重叠下限的算式;然后做完整例题和变式题。

必背

  1. 安全性(safety)是坏事不会发生,比如诚实节点不会执行冲突的块;活性(liveness)是好事终将发生,比如系统总能继续出块
  2. 两阶段锁在 Commit 会丢活性(锁住的副本拒绝新提案,凑不够票);锁挪到 Decide 会丢安全性(不同副本执行不同块)
  3. 三阶段顺序:先存 prepareQC(证据)→ 再设 lockedQC(锁)→ 再执行,lock restricts future conflicting votes
  4. safeNode 规则:提案从 lockedQC 指向的块延伸出来,或提案的 justify QC 视图号比 lockedQC 更高,二者满足其一就投票
  5. 上锁前已有 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 份部分签名,是怎样合成一个签名的。

下一讲 →
L10d L10d 门限签名:2f+1 份部分签名合成一个签名

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