用 Merkle Tree 做增量校验：根哈希、包含证明与工程边界

当文件很多、数据来自不可信节点，或客户端只想验证其中一条记录时，逐字节下载并重新计算全部内容既慢又昂贵。Merkle Tree（默克尔树）把大量叶子摘要压缩成一个根哈希，让系统能用短小的证明回答“这条数据属于这份集合吗”，也能快速定位哪一块发生了变化。

从叶子到根哈希

Merkle Tree 是一棵二叉哈希树。先对每个数据块计算叶子哈希，再把相邻两个哈希拼接后继续哈希，直到只剩一个根节点：

leaf[i] = H(0x00 || data[i])
parent  = H(0x01 || left || right)
root    = reduce(parent nodes)

给叶子和内部节点加不同前缀，是为了避免“某段数据的哈希”和“两个子节点拼接后的哈希”落入同一个语义空间。H 可以是 SHA-256 等稳定哈希；算法、编码、块大小和奇数节点处理规则必须写进协议，不能只靠实现者记忆。

如果叶子数量不是 2 的幂，常见做法是把最后一个节点复制一次，或让最后一个节点直接与前一个内部节点合并。两种方式都能工作，但生成方和验证方必须完全一致。更稳妥的协议会把叶子数量、树高和规则作为版本化元数据保存。

一次包含证明需要什么

假设客户端要验证第 i 个叶子，不需要拿到整棵树。服务端只需返回该叶子、从叶子到根路径上每层的兄弟哈希，以及每个兄弟位于左侧还是右侧。验证者按同样的拼接规则逐层计算，最后比较得到的根哈希：

import hashlib

def digest(tag: bytes, *parts: bytes) -> bytes:
    h = hashlib.sha256()
    h.update(tag)
    for part in parts:
        h.update(part)
    return h.digest()

def verify(leaf: bytes, siblings: list[tuple[bytes, bool]], expected: bytes) -> bool:
    current = digest(b"\x00", leaf)
    for sibling, sibling_is_left in siblings:
        current = (digest(b"\x01", sibling, current)
                   if sibling_is_left
                   else digest(b"\x01", current, sibling))
    return current == expected

证明大小与树高成正比。集合从一千条增长到一百万条时，证明只从约十层增长到约二十层；客户端不用信任传输路径，只要通过可信渠道拿到根哈希即可。根哈希本身通常会被签名、写入区块头、发布到透明日志，或和版本号一起存入受保护的数据库。只传根哈希而没有可信来源，无法阻止攻击者替换根和整套数据。

更新与差异定位

单个叶子改变后，只需重算它到根路径上的节点，计算量是 O(log n)；这适合内容寻址存储、软件包镜像、备份清单和区块同步。若双方各自持有一棵同形树，可以从根开始比较：根不同就比较两个子节点，递归进入不同的分支，直到找到变化的叶子。

目标	需要的数据	适合的证明
证明记录属于集合	叶子、兄弟哈希、根	Inclusion proof
证明记录不属于集合	有序树的相邻边界或专门结构	Non-membership proof
找出两份数据的差异	双方同形树的节点摘要	Tree diff
防止版本回退	根哈希、版本号、签名	Signed checkpoint

普通 Merkle Tree 天然擅长证明“存在”，不自动提供高效的“不存在”证明。若业务需要后者，应使用有序 Merkle Tree、稀疏 Merkle Tree 等结构，并明确空节点哈希、键编码和路径规则，不能把“没查到”误当成密码学证明。

工程落地的边界

首先固定块边界。按文件大小切块实现简单，但中间插入少量字节会让后续所有叶子移动；内容定义分块能减少增量同步的范围，却需要额外的滚动哈希和参数管理。其次区分完整性与机密性：Merkle Tree 能发现篡改，不能隐藏内容，也不能替代访问控制和加密。

还要防止哈希拼接歧义。长度可变字段应编码长度，叶子和内部节点使用不同标签；跨语言实现要用明确的字节序和 UTF-8 规则。测试时准备空集合、单叶、奇数叶、重复数据和错误方向位等向量，并让至少两种语言互相验证。

上线后应记录根哈希版本、树高、叶子数量、块大小、生成时间和签名状态。遇到校验失败，先比较根和版本，再定位第一处不同的分支；不要只报“hash mismatch”而丢失可复现的输入。把根哈希当作可审计的版本指针，把证明当作可独立验证的接口，Merkle Tree 才能从一个漂亮的数据结构变成可靠的完整性边界。