← COMP5521 全部讲次
Q03

2025 Final 真题解析(中)|Q19-Q21 ECDSA、比特币共识与三明治攻击

COMP5521 2025 年期末卷 Part 3 中间三题的非官方参考解答:玩具曲线上的 ECDSA 签名与验签、PoW 与同时出块、DEX 三明治攻击。

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

非官方参考解答,不是讲师给的标准答案;今年的考试安排与范围以讲师通知为准。 先自己在纸上做一遍,再展开对照。

范围与作答约定

本页是 2025 年期末卷 Part 3 的 Q19–21。前三题见上篇,后三题见下篇,卷面结构见期末复习(上)。

本页有两处讲义没有直接材料:Q20 第 (2) 问(两块同时广播)和整道 Q21(三明治攻击)。解析里会标「课件未直接覆盖,按 X 推」,答案的评分口径无法核对,仅供参考。Q21 第 (2) 问只出现在扫描版试卷上,复习讲义的截图里没有。

题目与解析

Q19 · ECDSA on a toy curve

11 分。曲线 y² ≡ x³ + x + 4 (mod 23),基点 G = (0, 2),阶 n = 29。私钥 d = 16,随机数 k = 8,H(m) = 15。卷面给出 1G 到 28G 的倍点表:

倍数 点 倍数 点 倍数 点 倍数 点
1G (0,2) 8G (14,5) 15G (18,14) 22G (15,17)
2G (13,12) 9G (4,7) 16G (8,8) 23G (9,12)
3G (11,9) 10G (22,5) 17G (17,14) 24G (7,3)
4G (1,12) 11G (10,5) 18G (10,18) 25G (1,11)
5G (7,20) 12G (17,9) 19G (22,18) 26G (11,14)
6G (9,11) 13G (8,15) 20G (4,16) 27G (13,11)
7G (15,6) 14G (18,9) 21G (14,18) 28G (0,21)

卷面给的步骤。签名:kG = (x1, y1),r ≡ x1 mod n,s ≡ k⁻¹(H(m) + d·r) mod n。验证:先查 1 ≤ r, s ≤ n − 1,再算 w ≡ s⁻¹,u1 ≡ H(m)·w,u2 ≡ r·w(都 mod n),P = u1·G + u2·Q,横坐标 x2 ≡ r 则有效。

  1. 用表求公钥 Q = dG。(3 分)
  2. 求签名 (r, s)。(4 分)
  3. 验证签名,说明接受还是拒绝。(4 分)
Q19 · 查看答案与解析

参考解答,非官方答案。

(1) Q = 16G,查表得 Q = (8, 8)。

(2)

  • kG = 8G = (14, 5),r = 14 mod 29 = 14。
  • k⁻¹ = 8⁻¹ mod 29 = 11,因为 8 × 11 = 88 = 3 × 29 + 1。
  • H(m) + d·r = 15 + 16 × 14 = 239,239 − 232 = 7。
  • s = 11 × 7 = 77 ≡ 19(mod 29)。
  • 签名 (r, s) = (14, 19)。

(3)

  • 范围检查:14 和 19 都在 1 到 28 之间。
  • w = 19⁻¹ mod 29 = 26(19 × 26 = 494 = 17 × 29 + 1)。
  • u1 = 15 × 26 = 390 ≡ 13;u2 = 14 × 26 = 364 ≡ 16。
  • u1·G = 13G = (8, 15)。
  • u2·Q = 16 · 16G = 256G。256 mod 29 = 24,所以 u2·Q = 24G = (7, 3)。
  • 两点相加:λ = (3 − 15)/(7 − 8) = 12;x2 = 144 − 8 − 7 = 129 ≡ 14;y2 = 12 × (8 − 14) − 15 = −87 ≡ 5。P = (14, 5)。
  • x2 = 14 = r,接受。

自查捷径:u1 + u2·d = 13 + 256 = 269 ≡ 8 (mod 29),P 就是 8G = kG,横坐标必然等于 r。考场上可以用它核对,正式作答仍按卷面步骤写出点加法。

验算:python 用点加法从 G 逐个推出表中 28 个点,全部吻合;曲线连无穷远点共 29 个点,29G = O;签名与验签每一步结果同上。

记号对照:讲义里私钥写 k、公钥 U、随机数 j、基点 P、哈希 e;卷面私钥 d、公钥 Q、随机数 k、基点 G、哈希 H(m)。公式结构一样。卷面把验证得到的点也叫 P,和模数 p 同字母,别看混。

回讲义:ECDSA(L08 p.29–31,p.36 Exercise-1 同型)· 模 p 曲线(点加法 L08 p.13)

Q20 · Bitcoin proof of work and simultaneous blocks

8 分,两问。

  1. 描述挖出一个有效区块的 Proof-of-Work 过程。(4 分)
  2. 如果两个区块同时被广播,会发生什么?共识机制怎样处理?(4 分)
Q20 · 查看答案与解析

参考解答,非官方答案。

(1) 按顺序写:

  • 矿工从内存池挑交易(费率高的优先),第一笔放 coinbase 交易,给自己发出块奖励加手续费。
  • 由交易算出 Merkle Root,填好区块头:Version、前一块哈希、Merkle Root、Time、Bits(难度目标)、Nonce,共 80 字节。
  • 从 0 开始改 nonce,反复对区块头做 SHA-256,直到哈希值小于目标值 target,也就是开头有足够多个 0。nonce 试完还没成功,就改 coinbase 或时间戳再试。
  • 找到后广播区块。其他节点只算一次哈希就能验证 PoW,再检查交易有效,通过就接上链。难找易验是 PoW 的要点。
  • 可补一句(讲义原文没有):难度会周期性调整,让出块间隔平均维持在约 10 分钟。

(2) 课件未直接覆盖,按比特币白皮书第 5 节推:

  • 两个矿工几乎同时挖出同一高度的块,网络出现临时分叉。每个节点在先收到的那块上继续挖,另一块也留着,以防那条分支后来变长。
  • 下一个块被挖出时平局打破:它接在哪一支后面,哪一支就更长(严格说是累计工作量更大),全网切换到这条最长链。
  • 被放弃的块成为 stale block,它的出块奖励作废;里面没进主链的交易回到内存池,等待重新打包。
  • 所以交易要等若干个确认才算稳妥。

回讲义:Lab 5 密码原语(PoW,Lab5 p.15–17)· 数字货币概述(区块头,L01 p.63)· 手续费与区块奖励(L09 p.12–13)· Lab 6 比特币(确认数)

Q21 · DeFi security: sandwich attack

8 分,两问。

  1. 描述去中心化交易所(DEX)上 Sandwich Attack 的执行过程。(6 分)
  2. 攻击者怎样获利?(2 分)
Q21 · 查看答案与解析

参考解答,非官方答案。 课件未直接覆盖,按 AMM 恒定乘积 x·y = k 和 L10 讲的 gas price 推。

(1) 四步:

  • 监听:交易广播后先在内存池里等打包,内容公开。攻击者的机器人盯着内存池,发现受害者要在 AMM 型 DEX(如 Uniswap)上大额买入代币 X,滑点容忍度设得较宽。
  • 抢跑(front-run):攻击者发一笔买 X 的交易,出更高的 gas price,让它排在受害者前面。这笔买入把池子里 X 的价格推高。
  • 受害者成交:受害者按被推高的价格成交,只要仍在滑点容忍度内就不会失败,换到的 X 变少,同时把价格推得更高。
  • 尾随(back-run):攻击者紧跟着把刚买的 X 卖回池子,排在受害者后面,按更高的价格卖出。

三笔交易在同一个区块里,受害者被夹在中间。

(2) 低买高卖的差价就是收入,这笔钱实际来自受害者多付的滑点。净利润还要扣掉两笔交易的 gas 和 DEX 手续费。受害者单子越大、滑点设得越宽,攻击者赚得越多。

玩具算例(忽略手续费和 gas):池子 100 ETH 对 200,000 USDC,价格 2,000。

  • 受害者单独用 20,000 USDC 买,能拿 9.09 ETH。
  • 被夹时:攻击者先用 10,000 USDC 买到 4.76 ETH,池价升到 2,205;受害者只拿到 8.28 ETH,池价升到 2,645;攻击者卖回 4.76 ETH,得 11,941 USDC。
  • 攻击者毛赚约 1,941 USDC,受害者少拿约 0.81 ETH。

验算:python 用分数精确计算,结果同上。

题目没问的补充:防御办法有收紧滑点、拆单、走不进公开内存池的私有交易通道。

回讲义:交易与 gas(gas price,L10 p.18)

下一页 →
Q04 2025 Final 真题解析(下)|Q22-Q24 Gas、比特币交易与稳定币

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