← COMP5567 全部讲次
R02

Lab Test 复习资料 2|PBFT 与 Lab 4

非官方复习:PBFT 的法定人数、prepare 失败例、commit 的必要性、视图切换与检查点,附 Lab 4 程序九个情形的实测计票。

手机上宽表格可左右滑动;自测答案默认收起,点击题目下方按钮查看。

2026-11-10 · L09 讲义与 Lab 4 实测版

范围与读法

非官方 Lab Test 复习资料,不是 Midterm 真题。 考试安排与范围以讲师通知为准。本页接复习资料 1,覆盖 L09 的 PBFT 和 PBFT 实验(Lab 4)。Lab 4 的结论分三种来源:实测(按课件步骤在程序里跑过)、读代码、未实测,表里逐项标出。页码均为 PDF 页序。

答题时协议规则按 L09 写;问到程序输出时按 Lab 4 的计票规则手算,两边不一致就两边都写。

PBFT:三阶段、换视图与检查点

PBFT(Castro & Liskov 1999)用 n=3f+1 个副本容忍 f 个拜占庭副本,消息量 O(n²)(L09 p.6、p.23)。三个子协议:正常操作走 Request → Pre-prepare → Prepare → Commit → Reply,怀疑主节点出故障时走 View change → New view,另有定期运行的检查点(p.9)。n 个副本最多容忍 f=⌊(n−1)/3⌋,n=4、5、6 都只容忍 1 个,n=7 才容忍 2 个(p.6)。L07 p.19 的预告图里副本 0 是主节点、副本 3 故障,五段箭头数为 1+3+6+9+3=22。

门槛 通式 f=1(n=4) f=2(n=7) L09 依据
进入 prepared 2f+1 个匹配 prepare 3 5 p.13
执行操作 2f+1 个匹配 commit 3 5 p.13 页底
客户端采纳结果 f+1 个相同回复 2 3 p.13
新主节点发 NEW-VIEW 2f+1 个 VIEW-CHANGE 3 5 p.15–16
检查点稳定 2f+1 个匹配 CHECKPOINT 3 5 p.18–19

L09 p.13 让主节点也多播 PREPARE,凑满 2f+1 个匹配 prepare。原论文里主节点不发 PREPARE,条件写成 pre-prepare 加 2f 个来自不同 backup 的匹配 prepare。两种数法都是 2f+1 票,答题按课件写,被问原论文时写后一种。

为什么取 2f+1:两组 2f+1 在 3f+1 个副本中至少重叠 2(2f+1)−(3f+1)=f+1 个,扣掉最多 f 个故障节点仍至少剩 1 个诚实节点,而诚实节点对同一序号只认一个值,两组不可能认定互相冲突的结果。f=1、2、3 时 n=4、7、10,2f+1=3、5、7,重叠下界 2、3、4。客户端等 f+1 个相同回复,因为最多 f 个是假的,f+1 个里至少 1 个来自诚实副本。原论文还说明 PBFT 的安全性不依赖同步,只有活性需要。

prepare 凑不齐(p.14)。 n=4,R2 发匹配的 PREPARE(X, d),R3 沉默,R4 是拜占庭副本,发摘要冲突的 PREPARE(X, d′)。R1 手上匹配 (X, d) 的只有自己和 R2,2 < 3,进不了 prepared,也就进不了 commit,本轮不回复客户端,等重传或视图切换。一个沉默加一个作恶,超过了 f=1 的预算,系统停住但不出错:safety 保住,liveness 暂时丢失。

为什么需要 commit(p.21)。 A、B、C、D 四个副本,A 是拜占庭主节点。假设改成 prepared 就执行、跳过 commit:A 让只有 C 收齐 seq 10 上 x 的 prepared 证书,C 执行 x;随后换视图,新主节点 B 收到 A、B、D 的 VIEW-CHANGE,C 的被延迟,证据里没有 x 的证书,于是 seq 10 被分给 y,B、D 执行 y。C 和 B、D 在同一序号执行了不同操作,safety violation。真实规则要 3 个匹配 COMMIT 才执行,其中至少 2 个来自已 prepared 的诚实副本;新主节点收的 3 份 VIEW-CHANGE 与它们至少重叠 2 个,其中至少 1 个诚实且带着 x 的证书,新视图必须在 seq 10 保留 x。本例中 B、D 没 prepared、不发 COMMIT,C 只有自己和 A 两票,不会执行 x。可以这样记:prepare 保证同一视图内一个序号只有一个值,commit 保证这个值换视图后还在。

视图切换(p.15–17)。 新主节点按 p = v mod n 轮转,副本从 0 编号:n=4 时 view 0、1、2、3、4 的主节点依次是 R1、R2、R3、R4、R1。p.10 写「v=1 是第一个当选的主节点」,与 p.15–17 从 view 0 起算不一致,按 p.15。主节点不响应时 backup 超时,向下一任主节点发 ⟨VIEWCHANGE, v+1, n, s, C, P, i⟩:n 和 s、C 是最近稳定检查点的序号、状态与 2f+1 证书,P 是本副本的 prepared 证书(p.12)。新主节点收齐 2f+1 个后发 ⟨NEWVIEW, v+1, V, O⟩,V 是这批 VIEW-CHANGE,O 是新视图要处理的 pre-prepare;已 prepared 的请求被带进新视图,没 prepared 的要客户端重发(p.16)。

Exercise 1(p.17):作恶的 R1 在 view 0 只给 R2、R3 发 PRE-PREPARE(X, seq=5)。R2、R3 各自凑到 R1、R2、R3 三票,进入 prepared;题设 R2、R3 已提交,说明 R1 对它们照常发了 COMMIT。R4 收不到 pre-prepare,不 prepare 也不 commit。换到 view 1,1 mod 4 = 1,新主节点是 R2。R2、R3 的 VIEW-CHANGE 带 seq=5 上 X 的 prepared 证书,R4 只带检查点。R2 发 NEW-VIEW(1, V, O),O 里 seq=5 必须仍是 X;R4 执行 X 追上进度,R2、R3 不重复执行。

检查点(p.18–19)。 副本定期做检查点,例如每 1000 次共识一次,消息为 ⟨CHECKPOINT, n, d, i⟩,d 是执行完第 n 号请求后状态的摘要。收到 2f+1 个序号和摘要都相同的消息后检查点稳定,可以丢弃之前的日志;崩溃或掉队的副本从最新稳定检查点取状态,再向其他副本补齐之后的日志。Example 2:上一个检查点在 10,各副本执行到 20,f=1,R1、R2、R3 摘要一致就稳定,第 4 个不影响。课件写丢弃「序号 20 之前」的日志,原论文是丢弃序号 ≤ 20 的消息。p.11 把 d 定义成数字签名,p.14、p.18 又把 d 当摘要用,读题时按摘要理解。

f=2 而只有 5 个节点(p.20)。 5 < 3f+1 = 7。按 2f+1=5 的门槛走要全员投票,R4、R5 有一个沉默或作恶就永远凑不齐,活性丢失;把门槛降到 n−f=3,两组 3 个在 5 个里只保证重叠 1 个,那 1 个可能正是作恶节点,安全性没有保证。

对照(p.23–25):BFT(L07 的 OM)没有固定 leader,消息量 O(nᶠ);PBFT 有 leader 选择协议,O(n²);两者都是 3f+1 容忍 f 个拜占庭故障。VR、Basic Paxos、Multi-Paxos 都是 2f+1 容忍 f 个崩溃,法定人数 f+1。

PBFT 实验(Lab 4)

程序有一个主节点 P0(python primary_node.py,端口 5000)和三个副本(python pbft_node.py P1 5001 等),P3 固定是拜占庭节点,客户端是 python pbft_client.py 7000(Lab 4 p.14–18)。只有 P3 能用 prepare to P1 yes、ack to P2 abort 这类命令给单个节点投不同的票(p.17)。客户端的 send 只把请求打印到 P0 上,主节点还要敲 tx 再手动输入一遍数据。每个节点各自敲 progress,按自己手上的票数推进。程序取 f=⌊(N−1)/3⌋=1,prepare 和 commit 门槛都是 3。在 macOS 上 5000 端口可能被隔空播放接收器占用,P0 启动失败时先查这一点。

计票方式(读代码,实测数字吻合):主节点数别人的 yes,再加自己 1 票;副本数别人的 yes 和自己的票,再把主节点的 pre-prepare 算作 1 票。P3 用 to 定向发出的票不计入它自己的计数。progress 时票数不够立即 abort,不会等后到的票。按这个规则可以手算每个节点打印的「YES(total): k/4」。

Lab 4 情形 各节点计数(实测) 结果(实测)
Case 1:存 100,全 yes、全 commit P0–P2 prepare 4/4、commit 4/4;P3 两阶段都是 3/4 全部提交,alice 100
Case 2:取 20,P3 对 P1、P2 投 no 和 abort P0 4/4、4/4;P1–P3 3/4、3/4 全部提交,alice 80
Case 3:取 100,P1、P2 投 no,P3 对 P0、P1 投 yes prepare P0 2/4、P1 2/4、P2 1/4、P3 1/4 全部中止,余额不变
Case 4:取 100,prepare 全 yes,P1、P2 ack abort prepare P0–P2 4/4、P3 3/4;commit P0–P2 2/4、P3 1/4 全部中止,余额不变
Case 5:P3 崩溃后存 100 prepare 3/4;commit 见下文 按课件步骤中止
Case 6:四个主节点依次崩溃 每轮 3 张 VIEW-CHANGE 够门槛 主节点依次 P1、P2、P3、P0,最后 view 4
Case 7:P0 敲 checkpoint P0 收齐 4 份报告 写出 final_checkpoint 文件,四个节点交易记录一致
练习 1:取 50,P1、P2 投 no,P3 只对 P2 投 yes prepare P0 1/4、P1 1/4、P2 2/4、P3 1/4 全部中止
练习 2:取 20,P3 对 P0、P2 投 no,之后全 commit prepare P0 3/4、P1 4/4、P2 3/4、P3 3/4;commit P0–P2 4/4、P3 3/4 全部提交,余额减 20

表中余额按 Case 1 到 Case 4 在同一次运行里连续执行计算。Case 3 和练习 1 说明一个作恶节点改变不了结果:诚实节点投 no 时,P3 给谁投 yes 都凑不满 3 票。Case 2 和练习 2 反过来,诚实节点全投 yes 时,P3 对谁投 no 都拦不住。Case 4 的 commit 阶段两个诚实副本 abort,P0 只有自己和 P3 两票,交易中止。

Case 5(p.25)课件步骤是 P3 先 crash,再走一笔存 100:P1、P2 prepare yes,commit 阶段写的是 P2 和 P3 各敲 ack commit。崩溃节点忽略所有收到的消息,P3 没收到 pre-prepare,敲 ack commit 只得到「No tx to ack」;P0、P1、P2 的 commit 停在 2/4,全部中止。把第二条 ack 换成 P1,commit 达到 3/4,提交,alice 100。两种都实测过,这一行很可能是把 P1 写成了 P3。P3 recover 后向主节点要状态,主节点把完整交易记录发回,P3 的记录与其他节点一致。这一页客户端那行还漏了 send。

Case 6(p.26)让 P0、P1、P2、P3 依次崩溃,其余三个节点敲 view change,再让崩溃的节点 recover。程序选「当前主节点后面的下一个 ID」当新主节点,逐个换视图时与 p = v mod 4 相同。课件没写的两处程序行为(实测):第一,崩溃节点收不到 NEW-VIEW,恢复时向自己记得的主节点要状态,而被换掉的主节点记得的正是自己,所以拿不到新视图。P0 恢复后停在 view 0,下一轮的 NEW-VIEW 到达才跳到 view 2;最后一轮崩溃的 P3 恢复后仍以为自己是 view 3 的主节点,P0 的 status 显示的却是 view 4、主节点 P0。第二,目标新主节点收到两票再加自己就够 3 票。第三轮按课件顺序 P0、P1、P3 输入,P3 收到 P0、P1 的票时已经当选,它随后敲的 view change 成了请求下一个视图的一票。

Case 7(p.28)只能由主节点发起。程序要等全部 4 个节点报告才拼出最终文件,不比较各节点的摘要(读代码)。L09 的规则是每个副本各自收 2f+1 个匹配 CHECKPOINT、自己判断稳定。按代码推断,有节点崩溃时这个程序的检查点凑不齐,未实测。课件页序上练习 1 在 p.27,排在 Case 7 前面,标题又写成「Case 2」,两道练习不要和演示 Case 2 弄混。

项目 L09 讲义 Lab 4 程序
新主节点 p = v mod n(p.15) 当前主节点后面的下一个 ID,逐个换视图时结果相同(实测)
prepare 计票 2f+1 个匹配 prepare,主节点也发(p.13) 副本把 pre-prepare 当作主节点一票(读代码)
票数不够 等待,之后重传或换视图(p.14) progress 时立即 abort(实测)
触发换视图 backup 超时(p.16) 手动敲 view change,程序里没有计时器(读代码)
VIEW-CHANGE 内容 检查点、证书、prepared 集合;NEW-VIEW 带 V 和 O(p.12、p.16) 只带视图号;新主节点重新广播最近一笔未完成的交易(读代码)
检查点稳定 每个副本各自收 2f+1 个匹配消息(p.19) 主节点收齐全部节点报告,不比摘要(读代码)
客户端 等 f+1 个相同回复(p.13) 打印收到的每个回复,不判断 f+1(实测打印 4 条)
取款 无此细节 不检查余额(读代码)

答题时协议规则按 L09 写,程序输出按上面实测的数字推。程序没有签名和摘要,拜占庭行为只能靠 P3 手动投不同的票来模拟,演示不了 p.14 那种「摘要冲突」的 prepare。

先做题再看答案

英文自测 3:PBFT 与 Lab 4 收 S23–S28;PBFT 门槛的基础题是英文自测 2 的 S15。

下一页 →
R03 Lab Test 复习资料 3|2PC 实验(Lab 1)

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