📑 本页目录（点开跳转）
12 · Merkle 树
⏱ 22 分钟 ｜ ⭐ 一个哈希值，承诺一整个数据集
🎯 一句话
用一个 32 字节的根哈希，锁定任意大的数据集； 而证明"某条数据在里面"只需要 log n 个哈希。 区块链的轻节点、证书透明性、Git、IPFS ——全都靠它。
🌳 一、结构
结构就是一棵二叉哈希树：叶子 H₁=H(D₁)…H₄=H(D₄) 是每条实际数据 D₁…D₄ 的哈希，相邻两个拼起来再哈希（H₁₂ = H(H₁‖H₂)、H₃₄ = H(H₃‖H₄)），一层层合并到唯一的 Root = H(H₁₂ ‖ H₃₄) —— 只需要公开这一个值。
两个关键性质：
| 性质 | 说明 |
|---|---|
| 承诺 | 根哈希一旦公布，整个数据集就被锁死了 —— 改任何一个字节，根就变 ⭐ |
| 高效证明 | 证明 Dᵢ 在树里，只需要 log₂n 个哈希，不需要整个数据集 ⭐ |
🔍 二、Merkle 证明怎么工作
要证明 D₃ 在树里：
给验证者：D₃ + 【兄弟路径】= [H₄, H₁₂] ← 只要 2 个哈希
验证者自己算：
① H₃' = H(D₃)
② H₃₄' = H(H₃' ‖ H₄)
③ Root' = H(H₁₂ ‖ H₃₄')
④ 检查 Root' == 已知的 Root ✅
数据量 证明大小
1,000 条 → 10 个哈希 = 320 字节
100 万条 → 20 个哈希 = 640 字节
10 亿条 → 30 个哈希 = 960 字节 ⭐ 仍然不到 1KB
🔑 这就是它的价值：验证成本从 O(n) 降到 O(log n)。 一个手机可以在不下载整条区块链的情况下，验证"我这笔交易确实在第 80 万个区块里"。
import hashlib
def h(b): return hashlib.sha256(b).digest()
def verify(leaf, proof, root, index):
"""proof: [(兄弟哈希, 是否在左边), ...] 自底向上"""
cur = h(leaf)
for sibling, sibling_is_left in proof:
cur = h(sibling + cur) if sibling_is_left else h(cur + sibling)
return cur == root # ⭐ 就这么简单
⚠️ 三、三个真实的坑
坑 ① 第二原像攻击：叶子和内部节点必须区分
💥 如果叶子和内部节点用【同样的方式】哈希：
攻击者可以把一个【内部节点的两个子哈希拼起来】当作一条"数据"
→ 它算出来的哈希和那个内部节点一样
→ 伪造出一条不存在的"数据"及其合法证明 💀
✅ 解法：加【域分隔】
叶子： H(0x00 ‖ data)
内部： H(0x01 ‖ left ‖ right) ⭐
💡 证书透明性（RFC 6962）标准里明确规定了这个前缀 —— 就是为了堵这个洞。
坑 ② 叶子数不是 2 的幂时怎么补
❌ 危险做法：复制最后一个叶子来凑满
💥 后果：[A, B, C] 和 [A, B, C, C] 会产生【相同的根】
→ 比特币早期版本就有这个缺陷（CVE-2012-2459）⭐
→ 可以构造出两个不同的区块却有相同的 Merkle 根
✅ 解法：把叶子数编进根里，或用不平衡树（RFC 6962 的做法）
坑 ③ 证明"不存在"要另想办法
Merkle 树天然能证明"X 在里面"（包含证明）
❌ 但证明"X 【不】在里面"需要额外结构
✅ 解法：
├─ 【排序 Merkle 树】：证明相邻的两个元素 A < X < B 都在树里
│ → 说明 X 不在（因为如果在，它必须排在 A 和 B 之间）⭐
└─ 稀疏 Merkle 树：为每个可能的 key 都留位置，证明那个位置是空的
🌍 四、它在哪些地方支撑着现代系统
| 系统 | 怎么用的 |
|---|---|
| 比特币 / 以太坊 | 区块头存 Merkle 根，轻节点（SPV）靠证明验证交易 ⭐ |
| 证书透明性 CT | 所有签发的证书进入公开的 Merkle 日志，CA 无法偷偷发证 ⭐ |
| Git | 每个 commit 是一棵 Merkle 树（tree/blob 对象），commit hash 锁定整个快照 |
| IPFS / BitTorrent | 内容寻址 + 分块校验 |
| ZFS / Btrfs | 文件系统的数据完整性校验 |
| Certificate Revocation | 证明某证书未被吊销 |
💡 证书透明性值得单独说
问题：一个被攻破的 CA 可以给 google.com 偷偷签发证书
→ 中间人攻击，而 Google 自己都不知道
CT 的解法：
① 所有证书必须提交到【公开的 Merkle 日志】
② 日志给出签名的"包含承诺"（SCT），浏览器会检查
③ 任何人可以监控日志 → Google 能发现"有人给我签了证书" ⭐
⭐ Merkle 树在这里提供两件事：
· 包含证明（这张证书确实进了日志）
· 【一致性证明】：证明新日志是旧日志的【追加】，
没有偷偷删改历史 ⭐⭐
🔑 "一致性证明"是 Merkle 树的另一个杀手级用法： 用 O(log n) 个哈希，证明版本 n 的树是版本 m 的树的纯追加扩展。 这让"仅追加日志"变成可验证的。
🔗 和站内其他章的关系
| 相关的地方 | 和这一章的关系 |
|---|---|
| 第 9 章 抗碰撞 | Merkle 树的安全性完全建立在它上面 |
| 第 9 章 承诺方案 | 根哈希就是对整个数据集的承诺 |
| 第 20 章 区块链 | SPV 轻节点 |
| 第 18 章 PKI | 证书透明性 |
| 推荐算法的向量检索 | 有意思的对照：都是"用结构把 O(n) 降下来" |
✅ 检查点
- Merkle 树的两个关键性质是什么？
- 证明一条数据在 10 亿条里，需要多大的证明？
- 为什么叶子和内部节点必须用不同的方式哈希？不这么做会怎样？
- 叶子数不是 2 的幂时，复制最后一个叶子有什么问题？
- 怎么证明某条数据"不在"树里？
- 证书透明性解决了什么问题？Merkle 树在其中提供哪两件事？
- 什么是一致性证明？它让什么变得可验证？
👀 答案
- ①承诺：根哈希一旦公布，整个数据集被锁死，改任何一个字节根就变 ②高效证明：证明某条数据在里面只需 log₂n 个哈希。
- 30 个哈希 ≈ 960 字节，不到 1KB。
- 否则攻击者可以把一个内部节点的两个子哈希拼起来当作一条"数据"，它的哈希和那个内部节点相同，从而伪造出一条不存在的数据及其合法证明。解法：域分隔——叶子 H(0x00‖data)，内部 H(0x01‖left‖right)。
- [A,B,C] 和 [A,B,C,C] 会产生相同的根，可以构造两个不同的区块却有相同 Merkle 根。比特币早期的 CVE-2012-2459 就是这个。解法：把叶子数编进根，或用不平衡树。
- 用排序 Merkle 树：证明相邻的 A < X < B 都在树里，说明 X 不在（若在则必须排在两者之间）。或用稀疏 Merkle 树证明对应位置是空的。
- 解决被攻破的 CA 可以偷偷给 google.com 签发证书的问题。Merkle 树提供：①包含证明（这张证书确实进了公开日志）②一致性证明（新日志是旧日志的纯追加，没有偷偷删改历史）。
- 用 O(log n) 个哈希证明版本 n 的树是版本 m 的树的纯追加扩展。它让"仅追加日志"变成可验证的。
🛑 可以停在这里
⚡ 走神救援
Merkle 树：用一个 32 字节的根哈希锁定任意大的数据集，叶子是数据哈希、父节点是子节点拼接再哈希。两性质：⭐承诺（改任何一字节根就变）+ ⭐证明只需 log₂n 个哈希（10 亿条数据的证明也不到 1KB）→ 验证成本从 O(n) 降到 O(log n)，手机不下载整条链就能验证交易。验证方法：拿兄弟路径自底向上重算到根，比对。三个真实的坑：①⭐叶子和内部节点必须域分隔（叶子 H(0x00‖data)、内部 H(0x01‖l‖r)）——否则攻击者把内部节点的两个子哈希拼起来当"数据"就能伪造不存在的数据及其合法证明（RFC 6962 明确规定了前缀）②叶子数不是2的幂时不能复制最后一个叶子——[A,B,C] 和 [A,B,C,C] 根相同，💥比特币早期 CVE-2012-2459 ③证明"不存在"要另想办法：⭐排序 Merkle 树（证明相邻的 A<X<B 都在树里 ⟹ X 不在）或稀疏 Merkle 树。应用：比特币 SPV 轻节点、证书透明性 CT、Git（每个 commit 就是一棵 Merkle 树）、IPFS、ZFS。⭐CT 解决"被攻破的 CA 偷偷给 google.com 签证书"：所有证书进公开 Merkle 日志，Merkle 树提供包含证明 + ⭐⭐一致性证明（用 O(log n) 个哈希证明新日志是旧日志的纯追加，没删改历史）——这让"仅追加日志"变成可验证的。
下一节 👉 13-数论工具箱.md