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 则有效。
- 用表求公钥 Q = dG。(3 分)
- 求签名 (r, s)。(4 分)
- 验证签名,说明接受还是拒绝。(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 分,两问。
- 描述挖出一个有效区块的 Proof-of-Work 过程。(4 分)
- 如果两个区块同时被广播,会发生什么?共识机制怎样处理?(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 分,两问。
- 描述去中心化交易所(DEX)上 Sandwich Attack 的执行过程。(6 分)
- 攻击者怎样获利?(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)
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。