区块链原理 / 系统课时

怎样用默克尔证明验证交易存在

怎样用默克尔证明验证交易存在

给定一笔交易、少量兄弟节点哈希和区块头中的默克尔根,就能检查这笔交易是否被该区块承诺,而不必下载区块内的全部交易。本篇通过四笔模拟交易构造包含证明,用 Python 重建默克尔根,并验证交易内容被修改后为什么会校验失败。

学习目标

  • 识别默克尔包含证明需要的交易哈希、兄弟哈希、左右路径和可信根。
  • 使用 Python 构造并验证交易包含证明,理解每一层的哈希拼接顺序。
  • 判断证明成功所依赖的信任前提,并估算证明大小与验证成本。

为什么只需要少量兄弟节点哈希

默克尔树把交易哈希放在叶节点,每两个相邻哈希按固定左右顺序拼接,再计算父节点哈希。重复这一过程,最终得到一个默克尔根。根承诺了整棵树的叶节点内容和排列顺序,任何交易内容变化通常都会改变根。

假设某区块只有四笔交易 T0、T1、T2、T3,分别得到叶哈希 h0、h1、h2、h3。相邻叶节点合成 h01、h23,最后合成根 R。这里的哈希计算采用双 SHA-256,父节点输入是左右两个原始 32 字节哈希的拼接结果。

现在要证明 T2 存在于这棵树中。验证者已经持有 T2 和可信根 R,只需要补充两项信息:

  1. h3:T2 在叶节点层的右侧兄弟哈希。
  2. h01:T2 所在子树在上一层的左侧兄弟哈希。

证明还必须记录兄弟节点的位置。验证者先计算 T2 的哈希 h2,再按照左 h2、右 h3 的次序计算 h23;随后按照左 h01、右 h23 的次序重建 R。只要最终结果等于可信根,就完成了包含性验证。

四笔交易的默克尔树与 T2 包含证明路径

这个例子中,完整区块有四笔交易,但证明只携带两个兄弟哈希和相应的方向信息。验证者不需要知道 T0、T1、T3 的交易正文,也不需要从头重新构建整棵树。

用 Python 构造并验证包含证明

下面使用 Python 3.9 或更新版本,只依赖标准库 hashlib。为方便直接运行,用 ASCII 字符串模拟交易字节;示例采用双 SHA-256 构造哈希树,但没有实现真实比特币交易序列化、签名验证或交易标识符的显示字节序转换。

代码分为三个主要操作:从全部交易计算根、根据目标交易索引提取证明、由目标交易和证明独立重建根。实际系统中,前两项通常由持有区块数据的节点完成,验证者只需执行第三项。

python
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))

预期输出:

text
root: 6ee0ee556b5f19d23c1959289d45f323d193d12a2fa4ffe6e5f0f84f32770b07
siblings: [('right', '4a8ee8fd3f66'), ('left', '98f56ec8e5e3')]
verified: True
tampered: False
hashes: 2

输出中的兄弟哈希只显示前 12 个十六进制字符,便于观察;实际证明保存的是完整的 32 字节哈希。根则完整显示为 64 个十六进制字符。

verified: True 表示 T2 使用这两段兄弟哈希成功重建了预期根。把金额从 1 改为 9 后,交易字节不同,叶哈希随之变化,因此 tampered: False。这说明原证明不能直接拿来证明另一笔内容不同的交易。

验证通过之前需要确认哪些前提

包含证明本身只能证明目标交易与给定根之间的哈希关系。假如证明提供者同时随意指定根,攻击者完全可以构造另一棵自洽的树,使虚假交易的包含证明也返回 True。因此,根不能只来自未经验证的同一条证明消息。

实际核验时,应按以下顺序检查:

  1. 获取目标交易的原始字节,或在仅验证交易标识符时获取符合协议定义的交易哈希。
  2. 获取兄弟哈希及每层的左右方向,并按照协议规定的哈希规则计算。
  3. 将重建的根与对应区块头中的默克尔根比较,而不是与证明提供者任意给出的根比较。
  4. 验证该区块头与所采用的可信链视图一致,再根据确认数、累计工作量等信息判断重组风险。

对比特币而言,普通交易默克尔树的叶节点使用交易的 txid;存在隔离见证时,还应区分 txid 与 wtxid。实现真实协议时必须按规定处理哈希字节序,不能简单地把展示用的十六进制字符串直接拼接后再计算哈希。

证明大小、特殊情况与检查方法

如果一棵二叉默克尔树有 nn 个叶节点,其包含证明的兄弟哈希数量约为 ⌈log⁡2n⌉\lceil\log_2 n\rceil。在双 SHA-256 方案中,每段哈希固定为 32 字节,因此交易数量增加时,证明大小增长得很慢。

区块内交易数量 兄弟哈希数量 哈希数据大小
4 2 64 字节
8 3 96 字节
1024 10 320 字节
约 100 万 20 640 字节

表中仅统计兄弟哈希本身,不包含交易、根、方向信息和协议封装开销。验证一笔交易还需要计算叶哈希,并沿证明路径逐层计算父哈希,因此路径验证的时间复杂度为 O(log⁡n)O(\log n),不必对全部交易逐一哈希。

还需要注意以下边界:

  • 拼接方向错误:把左兄弟放到右边,通常会重建出不同的根。证明必须保留左右方向,或提供可以推导方向的交易索引。
  • 奇数个节点:比特币式默克尔树在某层出现奇数个节点时,复制最后一个哈希与自身配对。示例中的 next_level 已实现这一规则,但完整协议验证还可能需要交易数量等上下文检查,不能仅凭最终根识别所有异常树结构。
  • 哈希规则不一致:若构造端使用双 SHA-256,验证端却只做一次 SHA-256,即使交易和路径完全相同,也无法得到同一个根。
  • 区块重组:包含证明可以针对某个区块成立,但如果该区块后来脱离被接受的主链,就不能继续把这份证明解释为交易仍在当前主链上。

可以把示例增加到五笔交易,选择索引 4 构造证明。由于树的高度增加,预期得到三个兄弟哈希;再修改目标交易字节,验证结果应由 True 变为 False。检查这两个条件,可以同时确认奇数叶节点配对规则和交易内容绑定是否正确。

在生产环境中,判断包含证明是否可信,应同时检查交易哈希计算、路径方向、可信区块头和链状态。默克尔树能够显著减少验证包含关系所需的数据量,但不会替代区块和交易的完整有效性验证。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

怎样用默克尔证明验证交易存在

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通