密码学与信息安全 · 12
不下载所有交易,怎样沿几个哈希核对成员证明?
成员证明把一片数据连回承诺的根。核对路径所需的信息很少,但根从哪里可信、数据如何编码仍有前提。
读完能判断:沿叶到根与兄弟节点路径验证成员关系,说明信任锚来自哪里。
📑 本页目录(点开跳转)
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 万个区块里"。
# 固定树形的教学验证器;root 必须来自可信渠道
import hashlib
def leaf_hash(data):
return hashlib.sha256(b"\x00" + data).digest()
def node_hash(left, right):
return hashlib.sha256(b"\x01" + left + right).digest()
def verify(leaf, proof, root, index):
"""proof: [(32字节兄弟哈希, 兄弟是否在左边), ...],由叶向根。"""
if index < 0 or index >= 1 << len(proof):
return False
cur = leaf_hash(leaf)
for sibling, sibling_is_left in proof:
if len(sibling) != 32 or bool(index & 1) != sibling_is_left:
return False
cur = node_hash(sibling, cur) if sibling_is_left else node_hash(cur, sibling)
index >>= 1
return cur == root
# 这不是完整 CT/任意树形解析器;叶子数、路径长度和树形由协议另行验证
⚠️ 三、三个真实的坑
坑 ① 第二原像攻击:叶子和内部节点必须区分
结果对照
💡 证书透明性(RFC 6962)标准里明确规定了这个前缀 —— 就是为了堵这个洞。
坑 ② 叶子数不是 2 的幂时怎么补
结果对照
坑 ③ 证明"不存在"要另想办法
关键信息
- Merkle 树天然能证明"X 在里面"(包含证明)
- ❌ 但证明"X 【不】在里面"需要额外结构
- ✅ 解法:
- 【排序 Merkle 树】:证明相邻的两个元素 A < X < B 都在树里
- → 说明 X 不在(还必须证明 A、B 在承诺排序中相邻,并处理首尾边界;仅有两份包含证明不足以证明不存在)⭐
- 稀疏 Merkle 树:为每个可能的 key 都留位置,证明那个位置是空的
🌍 四、它在哪些地方支撑着现代系统
| 系统 | 怎么用的 |
|---|---|
| 比特币 / 以太坊 | 区块头存 Merkle 根,轻节点(SPV)靠证明验证交易 ⭐ |
| 证书透明性 CT | 所有签发的证书进入公开的 Merkle 日志,可在日志与监控覆盖范围内发现误签发;不自动阻止误签发 ⭐ |
| Git | 每个 commit 是一棵 Merkle 树(tree/blob 对象),commit hash 锁定整个快照 |
| IPFS / BitTorrent | 内容寻址 + 分块校验 |
| ZFS / Btrfs | 文件系统的数据完整性校验 |
| Certificate Revocation | 证明某证书未被吊销 |
💡 证书透明性值得单独说
操作步骤
🔑 "一致性证明"是 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 树把大量数据汇总为根哈希,并用兄弟路径验证某个叶子。
- 验证时从叶子向上重算,最终与可信根比较。
- 节点编码、叶子数量与不存在证明都需要明确规则,不能只画一棵树。
下一节 👉 13-数论工具箱.md
条件与依据
根必须经可信渠道获得,并明确树形、叶子数和编码。下面示例按正文采用 0x00/0x01 域分隔;proof 中左右标志是路径的一部分,index 用于核对方向。证书透明性还需监控、一致性检查与防分视图措施,SCT 是纳入日志的承诺,不等同已取得包含证明。