区块链原理 / 系统课时
怎样用默克尔证明验证交易存在
怎样用默克尔证明验证交易存在
给定一笔交易、少量兄弟节点哈希和区块头中的默克尔根,就能检查这笔交易是否被该区块承诺,而不必下载区块内的全部交易。本篇通过四笔模拟交易构造包含证明,用 Python 重建默克尔根,并验证交易内容被修改后为什么会校验失败。
学习目标
- 识别默克尔包含证明需要的交易哈希、兄弟哈希、左右路径和可信根。
- 使用 Python 构造并验证交易包含证明,理解每一层的哈希拼接顺序。
- 判断证明成功所依赖的信任前提,并估算证明大小与验证成本。
为什么只需要少量兄弟节点哈希
默克尔树把交易哈希放在叶节点,每两个相邻哈希按固定左右顺序拼接,再计算父节点哈希。重复这一过程,最终得到一个默克尔根。根承诺了整棵树的叶节点内容和排列顺序,任何交易内容变化通常都会改变根。
假设某区块只有四笔交易 T0、T1、T2、T3,分别得到叶哈希 h0、h1、h2、h3。相邻叶节点合成 h01、h23,最后合成根 R。这里的哈希计算采用双 SHA-256,父节点输入是左右两个原始 32 字节哈希的拼接结果。
现在要证明 T2 存在于这棵树中。验证者已经持有 T2 和可信根 R,只需要补充两项信息:
- h3:T2 在叶节点层的右侧兄弟哈希。
- h01:T2 所在子树在上一层的左侧兄弟哈希。
证明还必须记录兄弟节点的位置。验证者先计算 T2 的哈希 h2,再按照左 h2、右 h3 的次序计算 h23;随后按照左 h01、右 h23 的次序重建 R。只要最终结果等于可信根,就完成了包含性验证。

这个例子中,完整区块有四笔交易,但证明只携带两个兄弟哈希和相应的方向信息。验证者不需要知道 T0、T1、T3 的交易正文,也不需要从头重新构建整棵树。
用 Python 构造并验证包含证明
下面使用 Python 3.9 或更新版本,只依赖标准库 hashlib。为方便直接运行,用 ASCII 字符串模拟交易字节;示例采用双 SHA-256 构造哈希树,但没有实现真实比特币交易序列化、签名验证或交易标识符的显示字节序转换。
代码分为三个主要操作:从全部交易计算根、根据目标交易索引提取证明、由目标交易和证明独立重建根。实际系统中,前两项通常由持有区块数据的节点完成,验证者只需执行第三项。
import hashlib
def hash256(data: bytes) -> bytes:
return hashlib.sha256(hashlib.sha256(data).digest()).digest()
def next_level(level: list[bytes]) -> list[bytes]:
# 奇数个节点时复制末节点,使该层能够两两配对。
if len(level) % 2:
level = level + [level[-1]]
return [
hash256(level[i] + level[i + 1])
for i in range(0, len(level), 2)
]
def build_root(txs: list[bytes]) -> bytes:
if not txs:
raise ValueError('交易集合不能为空')
level = [hash256(tx) for tx in txs]
while len(level) > 1:
level = next_level(level)
return level[0]
def make_proof(txs: list[bytes], index: int) -> list[tuple[str, bytes]]:
if not 0 <= index < len(txs):
raise IndexError('交易索引越界')
level = [hash256(tx) for tx in txs]
proof = []
while len(level) > 1:
if len(level) % 2:
level = level + [level[-1]]
# index ^ 1 定位同一父节点下的兄弟。
sibling_index = index ^ 1
side = 'left' if sibling_index < index else 'right'
proof.append((side, level[sibling_index]))
level = next_level(level)
index //= 2
return proof
def verify(tx: bytes, proof: list[tuple[str, bytes]], root: bytes) -> bool:
current = hash256(tx)
for side, sibling in proof:
# 兄弟在左侧时必须放在当前哈希之前拼接。
current = (
hash256(sibling + current)
if side == 'left'
else hash256(current + sibling)
)
return current == root
txs = [
b'tx0:A->B:5',
b'tx1:B->C:2',
b'tx2:C->D:1',
b'tx3:D->A:1',
]
root = build_root(txs)
proof = make_proof(txs, 2)
print('root:', root.hex())
print('siblings:', [(side, node.hex()[:12]) for side, node in proof])
print('verified:', verify(txs[2], proof, root))
print('tampered:', verify(b'tx2:C->D:9', proof, root))
print('hashes:', len(proof))预期输出:
root: 6ee0ee556b5f19d23c1959289d45f323d193d12a2fa4ffe6e5f0f84f32770b07
siblings: [('right', '4a8ee8fd3f66'), ('left', '98f56ec8e5e3')]
verified: True
tampered: False
hashes: 2输出中的兄弟哈希只显示前 12 个十六进制字符,便于观察;实际证明保存的是完整的 32 字节哈希。根则完整显示为 64 个十六进制字符。
verified: True 表示 T2 使用这两段兄弟哈希成功重建了预期根。把金额从 1 改为 9 后,交易字节不同,叶哈希随之变化,因此 tampered: False。这说明原证明不能直接拿来证明另一笔内容不同的交易。
验证通过之前需要确认哪些前提
包含证明本身只能证明目标交易与给定根之间的哈希关系。假如证明提供者同时随意指定根,攻击者完全可以构造另一棵自洽的树,使虚假交易的包含证明也返回 True。因此,根不能只来自未经验证的同一条证明消息。
实际核验时,应按以下顺序检查:
- 获取目标交易的原始字节,或在仅验证交易标识符时获取符合协议定义的交易哈希。
- 获取兄弟哈希及每层的左右方向,并按照协议规定的哈希规则计算。
- 将重建的根与对应区块头中的默克尔根比较,而不是与证明提供者任意给出的根比较。
- 验证该区块头与所采用的可信链视图一致,再根据确认数、累计工作量等信息判断重组风险。
对比特币而言,普通交易默克尔树的叶节点使用交易的 txid;存在隔离见证时,还应区分 txid 与 wtxid。实现真实协议时必须按规定处理哈希字节序,不能简单地把展示用的十六进制字符串直接拼接后再计算哈希。
证明大小、特殊情况与检查方法
如果一棵二叉默克尔树有 个叶节点,其包含证明的兄弟哈希数量约为 。在双 SHA-256 方案中,每段哈希固定为 32 字节,因此交易数量增加时,证明大小增长得很慢。
| 区块内交易数量 | 兄弟哈希数量 | 哈希数据大小 |
|---|---|---|
| 4 | 2 | 64 字节 |
| 8 | 3 | 96 字节 |
| 1024 | 10 | 320 字节 |
| 约 100 万 | 20 | 640 字节 |
表中仅统计兄弟哈希本身,不包含交易、根、方向信息和协议封装开销。验证一笔交易还需要计算叶哈希,并沿证明路径逐层计算父哈希,因此路径验证的时间复杂度为 ,不必对全部交易逐一哈希。
还需要注意以下边界:
- 拼接方向错误:把左兄弟放到右边,通常会重建出不同的根。证明必须保留左右方向,或提供可以推导方向的交易索引。
- 奇数个节点:比特币式默克尔树在某层出现奇数个节点时,复制最后一个哈希与自身配对。示例中的
next_level已实现这一规则,但完整协议验证还可能需要交易数量等上下文检查,不能仅凭最终根识别所有异常树结构。 - 哈希规则不一致:若构造端使用双 SHA-256,验证端却只做一次 SHA-256,即使交易和路径完全相同,也无法得到同一个根。
- 区块重组:包含证明可以针对某个区块成立,但如果该区块后来脱离被接受的主链,就不能继续把这份证明解释为交易仍在当前主链上。
可以把示例增加到五笔交易,选择索引 4 构造证明。由于树的高度增加,预期得到三个兄弟哈希;再修改目标交易字节,验证结果应由 True 变为 False。检查这两个条件,可以同时确认奇数叶节点配对规则和交易内容绑定是否正确。
在生产环境中,判断包含证明是否可信,应同时检查交易哈希计算、路径方向、可信区块头和链状态。默克尔树能够显著减少验证包含关系所需的数据量,但不会替代区块和交易的完整有效性验证。