覆盖第 1–8 讲。每题都给完整解答，不是"答案略"。建议先自己做完再看。

题 1　双花的本质

(a) 构造一个具体的双花场景，说明冲突的两笔交易各自都完全合法。

(b) 由此说明"双花是排序问题而不是验证问题"。

(c) 银行方案里，原子性依赖什么前提？去掉这个前提后哪一步失效？

解答

(a) Alice 余额 30。她同时发出：

Tx₁：Alice → Bob   30
Tx₂：Alice → Carol 30

⭐ 单独看每一笔：签名有效、余额充足（30 ≥ 30）、格式正确。任何验证函数都会通过。

网络延迟导致左半边节点先收到 Tx₁、右半边先收到 Tx₂：

左半边：接受 Tx₁ ⟹ 余额归零 ⟹ 拒绝 Tx₂（余额不足）
右半边：接受 Tx₂ ⟹ 余额归零 ⟹ 拒绝 Tx₁

(b) ⭐ 两边的验证逻辑完全相同且都正确，得到的结论却相反。唯一的差别是它们看到的顺序不同。 ⟹ 问题不在"如何判断一笔交易是否合法"，而在"如何让所有人对顺序达成一致"。

(c) 前提是只有一个写入者。去掉它之后，“检查余额"和"扣款"之间就不再原子——两个写入者可以各自读到同一个余额 30，各自判断"够用”，然后各自扣款。这正是数据库里的经典竞态，而分布式环境下它无法靠加锁解决，因为没有一个共同的锁。

题 2　FLP 与网络模型

(a) FLP 的三个限定词各是什么？分别去掉一个会怎样？

(b) 为什么异步模型下无法区分"崩溃"和"缓慢"？

(c) 比特币是怎么绕过 FLP 的？

解答

(a)

限定词 去掉后
异步 同步/部分同步下共识可解——可以用超时判定故障
确定性 允许随机化即可绕过（Ben-Or）：对手无法预测下一步，构造不出无限延迟序列
同时保证安全性和活性 只保证其中一个是平凡的（永不决定 ⟹ 安全；随便决定 ⟹ 活）

(b) ⭐ 异步的定义是"消息最终会到，但没有时间上界"。既然没有上界，任何超时都不能证明对方死了——它可能只是慢。而崩溃和缓慢在观测上完全相同：都是"没收到消息"。

(c) ⭐ 它换了一个更弱的问题：

① 把"确定性最终性"换成"概率最终性"——⭐ 从不真正"决定"，只是概率递增
② 假设网络同步（10 分钟出块间隔 ≫ 秒级传播时间）

两个前提各自都足以让 FLP 不适用。它不是解决了经典共识问题，而是换了一个问题。

题 3　拜占庭下界

(a) 推导 n > 3f。

(b) 为什么"最多只能等 n−f 个回复"？如果协议要求等 n−f+1 个会怎样？

(c) 有签名的同步网络下门槛降到 n ≥ f+2。为什么区块链仍用 n ≥ 3f+1？

解答

(a)

等待时最多只能等 n − f 个回复      （那 f 个可能永不回话）
这 n − f 个里最多 f 个来自拜占庭节点（回了，但内容是假的）
⟹ 可信的诚实回复至少 (n−f) − f = n − 2f 个

要让诚实的大多数压过可能的谎言：
        n − 2f > f
   ⟹    n > 3f

⭐ f 被减了两次：一次因为它们可能不回话（活性代价），一次因为它们可能说谎（安全性代价）。

(b) 因为 f 个拜占庭节点可以选择永远沉默。⚠️ 若协议要求等 n−f+1 个，那么在这 f 个全部沉默时协议永远阻塞 ⟹ 活性被违反。

(c) 因为区块链运行在部分同步模型下，不是同步模型。签名解决的是"中转者篡改他人消息"，但它无法解决"网络延迟导致无法区分故障"。在部分同步下，即使有签名，n ≥ 3f+1 依然是必要的。

题 4　不可能三角的量化

一条链声称 5,000 TPS，平均交易 500 字节。

(a) 算出年产生的原始数据量。

(b) 全节点还能放在家用机器上吗？

(c) 这条链是提高了 T 还是提高了 R？

解答

(a)

带宽：5,000 × 500 = 2.5 MB/s = 20 Mbps 【持续】
每天：2.5 × 86,400 = 216 GB
每年：216 GB × 365 ≈ 78.8 TB

(b) ⚠️ 不能。 78.8 TB/年意味着：

① 需要多块大容量硬盘，且每年都要加
② ⭐ 更致命的是【同步时间】：新节点要下载 78.8 TB，
   即使千兆网满速（125 MB/s）也要约 7 天，
   而实际还要执行和写状态，只会更慢
⟹ 普通人退出，只剩数据中心

(c) ⭐ 提高的是 R。 它没有改变"每个全节点验证每笔交易"这个架构，只是把对机器的要求抬高了 —— 按第 3 讲的定义，这直接等于降低去中心化。

题 5　生日攻击

(a) 128 位输出的哈希，找碰撞需要多少次尝试？每秒 10¹² 次要多久？

(b) 为什么 SHA-256 只有 128 位碰撞安全性？

(c) “MD5 被破解了，所以用 MD5 存密码不安全”——这句话对吗？

解答

(a)

2^(128/2) = 2⁶⁴ ≈ 1.845 × 10¹⁹ 次

10¹² 次/秒 ⟹ 1.845 × 10⁷ 秒 ≈ 0.585 年

⭐ 不到七个月。这就是为什么 128 位输出的哈希今天不能用于需要抗碰撞的场景。

(b) 因为找碰撞时攻击者可以自由选择两个输入，而生日悖论让这个自由度把成本从 2ⁿ 降到 2^(n/2)。哈希的安全级别必须按最弱的那条性质来标称。

(c) ⚠️ 结论对，但理由错。

⭐ MD5 被攻破的是【抗碰撞性】，而密码哈希依赖的是【抗原像性】——
   后者至今没有被有效攻破。

MD5 存密码不安全的真正原因是：
   ① 它【太快】——攻击者每秒能试几十亿个候选口令
   ② 通常没有加盐 ⟹ 彩虹表可用
⟹ 应该用 bcrypt / scrypt / Argon2 这类【故意很慢】的函数。

题 6　Merkle 树的两个漏洞

(a) 完整推演 [A,B,C] 与 [A,B,C,C] 在比特币构造下的每一层，说明根为何相同。

(b) 攻击者据此能做什么？受害节点在哪一步出错？

(c) 无域分隔时的第二原像攻击怎么做？加上前缀后为何失效？

解答

(a)

[A, B, C]：
  第 0 层：h(A), h(B), h(C)
  ⚠️ 奇数 ⟹ 复制最后一个：h(A), h(B), h(C), h(C)
  第 1 层：H(h(A),h(B)),  H(h(C),h(C))
  根：     H( H(h(A),h(B)), H(h(C),h(C)) )

[A, B, C, C]：
  第 0 层：h(A), h(B), h(C), h(C)     ← 已是偶数，无需复制
  第 1 层：H(h(A),h(B)),  H(h(C),h(C))
  根：     完全相同

(b)

① 攻击者截获合法区块 X = [A,B,C]，构造 Y = [A,B,C,C] 转发
② 受害节点：区块头哈希 ✅、Merkle 根 ✅
   ⚠️ 但验证交易时发现 C 重复 ⟹ 双花 ⟹ 区块无效
③ 节点把【这个区块哈希】记入无效缓存
④ 真正的区块 X 到达时，哈希与 Y 完全相同
   ⟹ 一查缓存，直接丢弃
⟹ 该节点永久停在旧链上（永久 DoS，不需要任何算力）

⭐ 出错的根源：Merkle 构造不是单射的——两个不同的叶子序列给出同一个根。

(c)

无域分隔时：leaf(x) = H(x)，node = H(左‖右)
⟹ ⚠️ 内部节点的值和叶子的值来自【同一个哈希空间】，无法区分。

于是一棵 4 叶子树的两个内部节点值 (h₀‖h₁) 和 (h₂‖h₃)，
可以被冒充成一棵 2 叶子树的两个【叶子】，
   两者算出的根完全相同 ⟹ 对同一个根给出了另一个"原像"。

加上前缀后：
   leaf = H(0x00 ‖ x)，node = H(0x01 ‖ 左 ‖ 右)
⟹ 两类哈希的输入前缀不同，落在【不相交】的空间里
⟹ 冒充需要找到跨前缀的哈希碰撞 —— 不可行

题 7　ECDSA 随机数重用：完整演算

某系统用 ECDSA，群阶 n = 101（为便于手算取的小素数）。观察到同一私钥的两个签名，且 r 相同：

r = 40
签名一：s₁ = 55，消息哈希 z₁ = 20
签名二：s₂ = 33，消息哈希 z₂ = 91

(a) r 相同意味着什么？

(b) 解出 k。

(c) 解出私钥 d，并验算。

解答

(a) r = (k·G).x mod n，它只依赖 k。所以 r 相同 ⟹ 两次用了同一个 k。

(b)

s₁ = k⁻¹(z₁ + r·d)
s₂ = k⁻¹(z₂ + r·d)
相减：s₁ − s₂ = k⁻¹(z₁ − z₂)

⟹ k = (z₁ − z₂) · (s₁ − s₂)⁻¹ mod 101
     = (20 − 91) · (55 − 33)⁻¹
     = (−71) · 22⁻¹
     = 30 · 22⁻¹          （−71 ≡ 30 mod 101）

求 22⁻¹：22 × 23 = 506 = 5×101 + 1  ⟹ 22⁻¹ = 23

⟹ k = 30 × 23 = 690 ≡ 690 − 6×101 = ⭐ 84

(c)

由 s₁·k = z₁ + r·d
⟹ d = (s₁·k − z₁) · r⁻¹ mod 101
     = (55 × 84 − 20) × 40⁻¹
     = (4620 − 20) × 40⁻¹
     = 4600 × 40⁻¹
     4600 ≡ 4600 − 45×101 = 55

求 40⁻¹：40 × 48 = 1920 = 19×101 + 1 ⟹ 40⁻¹ = 48

⟹ d = 55 × 48 = 2640 ≡ 2640 − 26×101 = ⭐ 14

验算： k⁻¹：17 × 6 = 102 ≡ 1，而 84 ≡ −17，所以 k⁻¹ = −6 ≡ 95。

签名一：z₁ + r·d = 20 + 40×14 = 580 ≡ 75
        s₁ = 95 × 75 = 7125 ≡ 7125 − 70×101 = 55  ✅

签名二：z₂ + r·d = 91 + 560 = 651 ≡ 45
        s₂ = 95 × 45 = 4275 ≡ 4275 − 42×101 = 33  ✅

⭐ 两个签名都对上了，私钥 d = 14 被完全恢复。

⚠️ 注意这个计算的成本：几次模乘。而 r 是公开在链上的——攻击者只需扫描全链找 r 重复的签名对。这就是 Sony PS3 私钥被算出来的全部过程。

题 8　Schnorr 聚合与恶意密钥

(a) 用线性性推导两方签名聚合。

(b) Bob 声称 Q₂ = Q' − Q₁（Q' 是他自己选的）。他能做什么？

(c) 持有证明为什么能挡住它？

解答

(a)

Alice: s₁ = k₁ + e·d₁
Bob:   s₂ = k₂ + e·d₂        （同一个挑战 e）
────────────────────────────
s = s₁ + s₂ = (k₁+k₂) + e·(d₁+d₂)

⭐ 这是对聚合公钥 Q = Q₁ + Q₂ = (d₁+d₂)·G、
   聚合承诺 R = R₁ + R₂ 的一个合法 Schnorr 签名。

(b)

聚合公钥变成 Q = Q₁ + Q₂ = Q₁ + (Q' − Q₁) = ⭐ Q'

而 Q' 是 Bob 自己选的，他知道对应的私钥 d'。
⟹ Bob 可以【单独】为聚合公钥签名，
   完全不需要 Alice 参与。
⟹ 一个"2-of-2 多签"实际上被 Bob 一个人控制了。

(c) ⭐ 持有证明要求：注册公钥时，必须附上一个用该公钥对应私钥、对公钥自身的签名。

Bob 声称的 Q₂ = Q' − Q₁：
   ⚠️ 他不知道 Q₂ 对应的私钥（那需要知道 d' − d₁，而 d₁ 是 Alice 的）
⟹ 他签不出这个证明 ⟹ 公钥注册被拒

题 9　承诺方案

(a) 一个链上密封拍卖用 c = keccak256(出价)，出价范围 0–1000 整数。写出攻破它的完整步骤。

(b) 修复方案。修复后隐藏性依赖什么假设？

(c) 修复后仍然存在什么问题？无法靠加大保证金根治的原因是什么？

解答

(a)

① 攻击者本地计算 keccak256(0), keccak256(1), ..., keccak256(1000)
   ⭐ 一共 1001 次哈希，毫秒级完成
② 建一张 哈希 → 出价 的查找表
③ 从链上读取所有人提交的承诺，逐个查表
⟹ 所有人的出价被完全还原，隐藏性为零

⚠️ 根因：x 的熵只有约 10 比特，而承诺方案的隐藏性要求输入不可枚举。

(b)

c = keccak256(出价 ‖ r)，r 是 32 字节随机数
揭示时同时公布 出价 和 r

隐藏性依赖的假设：哈希的抗原像性 + r 有足够熵。注意这两条缺一不可——如果 r 用 block.timestamp 生成，熵仍然很低，攻击照样成立。

(c) ⚠️ 最后揭示者优势（第 8 讲第三节）：

最后一个揭示的人，能先算出"我揭示会导致什么结果"。
若结果不利，他可以选择【不揭示】（认赔保证金）。
⟹ ⭐ 他获得了一次对最终结果的"重掷"机会。

加大保证金不能根治，因为这是一个比较关系：只要操纵收益 > 保证金，放弃保证金就仍然划算。而操纵收益取决于奖池大小，是可以任意大的。真正的解法是 VRF 或 VDF——用密码学消除"选择权"本身。

题 10　链上随机数

(a) 一个 NFT 合约用 blockhash(block.number - 1) 决定稀有度。矿工/验证者能做什么？普通用户能做什么？

(b) VRF 的"唯一性"为什么是要害？

(c) RANDAO 仍有偏置。VDF 是怎么消除它的？

解答

(a)

出块者：
   ⭐ 他能看到自己出的块会导致什么结果。
   若抽到的不是稀有 NFT，他可以【丢弃这个块重挖】。
   代价只是一个区块奖励——只要稀有 NFT 价值更高，攻击就划算。

普通用户：
   他能【预先模拟】：在一笔交易里先读 blockhash，
      算出结果，若不利就 revert 整笔交易。
   ⟹ 由于 EVM 的原子性，这等于免费重试无限次
      （只损失 Gas）

⭐ 第二条常被忽略，但它不需要任何特权，人人可做。

(b) 唯一性意味着：给定 sk 和 input，输出唯一确定，持有者没有任何选择空间。

⚠️ 如果不唯一（比如允许多个有效输出），
   持有者就能算出多个候选、挑一个对自己有利的公布
⟹ 退化成"最后揭示者优势"

⭐ 所以唯一性把"可以选择"变成了"只能公布或不公布"——把一个连续的选择空间压缩成了一个二元决定。

(c)

RANDAO 的问题：出块者能预见自己出块对种子的影响，
⚠️ 可以选择不出块来"重掷"（代价是放弃区块奖励）。

VDF 的性质：必须【串行】计算 T 步，无法并行加速，但结果可快速验证。

把 RANDAO 输出再过一遍 VDF：
   ⟹ 出块者在决定"出不出这个块"的几秒钟内，
      根本【来不及】算出 VDF 结果
   ⟹ 他无从判断这个块对自己有没有利
   ⟹ 操纵的【信息优势】被物理时间消灭了

关键在于：VDF 不是让操纵变难，而是让操纵者在做决定时"不知道该往哪边操纵"。

相关：第 1–8 讲