2025 期末真题解析(三)|Q21–Q23:OM 与 SM、PBFT 计票、PoW 与 PoS
非官方参考解答:2025 年期末卷 Part C 的 Q21 口头消息与签名消息算法、Q22 PBFT 七节点计票、Q23 PoW 与 PoS 的出块权、回滚、51% 双花与长程攻击,题面中文转述,附英文答题骨架和讲义页码。
手机上宽表格可左右滑动;自测答案默认收起,点击题目下方按钮查看。
非官方参考解答,不是讲师给的标准答案;今年的考试安排与范围以讲师通知为准。 先自己写一遍,再展开对照。
范围与作答约定
本页收 2025 年期末卷 Part C 的最后三题,题目按卷面原题中文转述,关键术语保留英文。前五题见真题解析(一)和真题解析(二)。
Q21、Q23 是简答题,卷面要求「briefly and accurately」,解析末尾附英文答题骨架,考场上照着骨架展开即可。Q22 是画图计票题,票数取决于怎么数,解析里先写明数法;遇到题面没说清的地方,答题时也先写一句自己的数法。
题目与解析
Q21 · OM and SM with a faulty primary
n 个节点里有 f 个恶意节点。主节点 P 是恶意的,另有三个忠诚副本 R1、R2、R3。
(1) 用口头消息算法 OM,n 为 4、f 为 1:P 把 v1 发给 R1、R2,把 v2 发给 R3。写出三个副本达成共识的详细步骤和最终值。
(2) 用签名消息算法 SM:P 把签了名的 v1 发给 R1,把签了名的 v2 发给 R2、R3。忠诚副本怎样发现主节点作恶?发现之后能怎么办?
(3) 为什么 OM 需要 n > 3f,而 SM 只需要 n > f?
复习课课件的截图只截到第 (2) 问,第 (3) 问在卷子原件上。
Q21 · 查看答案与解析
参考解答,非官方答案。
(1) 跑 OM(1),两轮:
| R1 | R2 | R3 | |
|---|---|---|---|
| 第 1 轮:P 发令 | v1 | v1 | v2 |
| 第 2 轮:把收到的值转给另外两人 | 转 v1 | 转 v1 | 转 v2 |
| 手里的三个值 | P 的 v1、R2 的 v1、R3 的 v2 | P 的 v1、R1 的 v1、R3 的 v2 | P 的 v2、R1 的 v1、R2 的 v1 |
| 取多数 | v1 | v1 | v1 |
三个忠诚副本都决定 v1,满足一致性;P 是叛徒,「指挥官忠诚时听它的」这一条不约束。消息数是第 1 轮 3 条加第 2 轮 6 条,共 9 条。
(2) 每个副本把收到的命令加上自己的签名转给另外两人。R1 先拿到 P 签的 v1,又从 R2、R3 拿到 P 签的 v2;R2、R3 反过来也拿到 R1 转来的、P 签的 v1。三人手里的命令集合都是 {v1, v2}。
发现:同一个主节点在同一轮签了两个不同的值,签名伪造不了,这两条消息本身就证明 P 作恶。
处理:三人的集合相同,用同一个确定的选择规则就会得到同一个结果,例如约定「集合里不止一个值就取默认的 RETREAT」,一致性仍然成立(L07 p.23 的练习是同一个结构)。还可以拿这两条签名消息当证据,把 P 换掉,发起换主节点。讲义没有限定选择规则,这一问的「怎么办」答法不唯一。
(3) OM 里,一个节点转述「主节点对我说了 X」,接收者没法判断是主节点在撒谎还是转述的人在撒谎(L07 p.12 的不可区分论证),所以 3 个节点容不下 1 个叛徒,一般要 n ≥ 3f + 1。SM 里转述带着主节点的原签名,改内容会被发现,叛徒最多少发,或者发出自相矛盾的签名命令反而暴露自己,只要还有忠诚节点就能达成一致,所以 n > f 就够。两种算法都假设同步网络,SM 还需要公钥基础设施(L07 p.24)。
English answer skeleton
(1) Round 1: P sends v1 to R1 and R2, and v2 to R3. Round 2, OM(0): each lieutenant relays what it received to the other two. R1 holds {v1, v1, v2}, R2 holds {v1, v1, v2}, R3 holds {v2, v1, v1}. Majority gives v1 at every loyal replica, so they agree on v1. Total 9 messages.
(2) Each replica countersigns and forwards what it received, so every loyal replica ends with V = {v1, v2}, both signed by P. Two conflicting values under P’s signature prove that P is faulty. All loyal replicas hold the same set and apply the same deterministic choice function (e.g. default RETREAT), so they still agree; the signed messages can also be used as evidence to replace P via a view change.
(3) With oral messages a receiver cannot tell whether the commander or the relaying lieutenant lied, so n ≥ 3f + 1 is needed. With signed messages forgery is detectable, so traitors can only withhold messages or expose themselves; agreement needs only n > f. Both assume a synchronous network; SM also needs a PKI.
Q22 · PBFT vote counting
系统运行 PBFT(Request、PrePrepare、Prepare、Commit、Reply 五个阶段),有一个 Client、主节点 P0 和副本 P1–P6;P3 是唯一的拜占庭节点。
(1) 画出一次有效请求的完整共识过程,并写出每个节点收到多少个「Yes」和多少个「Commit」。
(2) 同 (1),但 P1 在 Prepare 阶段一开始就崩溃。
Q22 · 查看答案与解析
参考解答,非官方答案。 先定参数:7 个节点是 3f+1,所以 f 为 2;Prepare、Commit 的门槛都是 2f+1,即 5 个匹配票;Client 要等 f+1,即 3 个相同的回复(L09 p.6、p.13)。
数法。 按 L09 p.13 课件的口径:每个节点(含主节点)都多播 Prepare,计数含自己的那一票。课件例子里的「3 Yes 1 No」就是 4 个节点中含自己的 3 张 Yes,加拜占庭节点的 1 张 No。P3 画成发 No(或发摘要对不上的票)。
图上的箭头太多,下面用步骤表代替,考场上按表画箭头即可。
(1)
| 步 | 消息 | 每个诚实节点的计数 |
|---|---|---|
| 1 | Client → P0:Request | |
| 2 | P0 → P1–P6:PrePrepare | |
| 3 | P0、P1、P2、P4、P5、P6 互相多播 Prepare(Yes),P3 发 No | 6 Yes 1 No,6 ≥ 5,进入 prepared |
| 4 | 6 个诚实节点互相多播 Commit | 6 Commit,6 ≥ 5,执行 |
| 5 | 6 个诚实节点 → Client:Reply | Client 收到 6 个相同结果,≥ 3,接受 |
(2)
| 步 | 消息 | 每个存活诚实节点的计数 |
|---|---|---|
| 1 | Request、PrePrepare 同 (1),P1 收到了 PrePrepare | |
| 2 | Prepare 一开始 P1 崩溃,一票不发 | |
| 3 | P0、P2、P4、P5、P6 多播 Prepare(Yes),P3 发 No | 5 Yes 1 No,5 ≥ 5,刚好 prepared |
| 4 | 5 个存活诚实节点多播 Commit | 5 Commit,5 ≥ 5,执行 |
| 5 | 5 个 Reply 到 Client | ≥ 3,接受 |
这时故障数是 1 个拜占庭加 1 个崩溃,正好等于 f,门槛刚好够,没有余量。再有一个节点失联就凑不齐 5 票,这一轮停住,丢的是活性,安全性不受影响(L09 p.14)。
数法的歧义。 题面没说「Yes」含不含自己、主节点发不发 Prepare。此处按课件 L09 p.13 的口径读。若按原论文的口径读(主节点不发 Prepare,副本要 PrePrepare 加 2f 个来自其他副本的匹配 Prepare),每个副本收到的他人 Yes 在 (1) 里是 4 个、(2) 里是 3 个,门槛是 2f 即 4,(2) 会卡住。两种数法在 (2) 上结论不同,答题按课件口径写,并注明数法。
Q23 · Consensus and security in major blockchains
(1) 比较比特币的 PoW 和以太坊的 PoS:出块权怎么分配?已经确认的区块能不能被回滚?
(2) 掌握超过 50% 算力的攻击者,怎样在 PoW 链上实施双花(double-spending)?
(3) PoS 里的长程攻击(Long-Range Attack)怎样进行?给出一种常见的缓解办法。
复习课课件的截图只截到第 (2) 问,第 (3) 问在卷子原件上。
Q23 · 查看答案与解析
参考解答,非官方答案。
(1)
| 比特币 PoW | 以太坊 PoS | |
|---|---|---|
| 出块权 | 谁先找到让区块头哈希不超过目标值的 nonce 谁出块,概率正比于算力(L05 p.7–8) | 每个 slot 伪随机选一个出块者,被选中的概率按有效质押加权(L05 p.12、p.24) |
| 能否回滚 | 概率性最终性:最长链规则下任何块理论上都能被更长的链替换,等 6 个确认只是让被反超的概率很小(L04 p.41) | 链头还没敲定的块可能随 LMD GHOST 重组;经 Casper FFG 敲定(finalized)的检查点,正常约 2 个 epoch、12.8 分钟,要推翻它就得出现冲突的敲定,这会让至少 1/3 质押可被罚没(L05 p.28–30) |
(2) 双花步骤(L04 p.43–44):
- 攻击者在公开链上付款给商家。
- 同时从付款之前的块开始私下挖一条分支,在里面不放这笔付款(或把同一笔币转给自己),不广播。
- 商家等够确认后发货。
- 攻击者算力过半,私链最终会比公开链长,这时公布私链。
- 全网按最长链规则切到私链,含付款的分支被丢掉,付款失效,攻击者拿回了币,商家的货已经发出。
攻击者能回滚、能审查交易,但花不了别人的币,也造不出新币:没有别人的私钥,节点也会独立检查交易规则。算力过半时,等多少个确认都挡不住。
(3) 这一问超出 L05 课件范围,课件没有出现「长程攻击」这个词,下面是补充。
- 攻击者收集一批早已退出质押的旧验证者私钥。这些人的押金已经取回,卖掉私钥没有损失,也罚没不到。
- 用这些私钥从很久以前的某个块开始重签一条平行链。签名几乎不花成本,很快就能造出很长的一段假历史。
- 新加入或长期离线的节点只看协议规则,分不清哪条才是真历史。
缓解:弱主观性检查点(weak subjectivity checkpoint)。新节点或长期离线的节点从一个近期的、可信的检查点开始同步,客户端也不回滚已经敲定的块,超出这个窗口的平行历史一律不认。
English answer skeleton
(1) Proposal rights: in PoW, whoever first finds a nonce whose block hash is below the target proposes the block, so the chance is proportional to hash power. In Ethereum PoS, one proposer per slot is chosen pseudo-randomly, weighted by effective stake. Reversibility: PoW has probabilistic finality; a longer chain can replace any block, and waiting for 6 confirmations only makes this unlikely. PoS has economic finality: un-finalized head blocks may reorg, but reverting a Casper FFG finalized checkpoint needs conflicting finalization, which makes at least 1/3 of the stake slashable.
(2) The attacker pays a merchant on the public chain while privately mining a fork that omits the payment. After the merchant releases the goods, the attacker publishes its longer private chain; nodes switch by the longest-chain rule, the payment disappears, and the coins can be spent again. With more than half of the hash power the private fork eventually wins, regardless of the number of confirmations.
(3) Long-range attack: the attacker obtains old keys of validators who have already withdrawn their stake, so they have nothing to lose and cannot be slashed, and uses them to build an alternative chain from far back in history. Signing is cheap, so a long fake history can be produced quickly, and a new node cannot tell it from the real one. Mitigation: weak subjectivity; new or long-offline nodes start from a recent trusted checkpoint and never revert finalized blocks.
回讲义:L05a PoW 与 PoS、L05b-2 检查点与最终性、L04b 分叉、双花与 51% 攻击、L05a-2 Nothing at Stake 与罚没
这组材料已读完,可以回课程页选择配套资料或练习:COMP5567 课程页。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。