Merkle认证树 | Codeboy's Blog

形式陈述

被认证的是位置和值

固定高度 $h\ge0$ 、叶数 $N=2^h$ ，有序列表为 $v_0,\ldots,v_{N-1}$ 。每个值是有限字节串；一份打开声称“索引 i 保存值 v”，而不只是“某处出现过 v”。验证者预先持有可信的高度与根摘要 $(h,r)$ 。本页不处理任意叶数的补齐规则，也不由服务器自行提供的新根判断真伪。

令 H 是输出 n 字节的公开哈希。下面的教学编码使用不同首字节区分叶与内部节点，并使用规范字段编码：

L_i=H(\mathtt{00}\Vert\operatorname{u32}(i)\Vert\operatorname{u32}(|v_i|)\Vert v_i),

T_{j,p}=H(\mathtt{01}\Vert\operatorname{u8}(j)\Vert T_{j-1,2p}\Vert T_{j-1,2p+1}),\qquad T_{0,i}=L_i.

u32、u8 是指定宽度的大端无符号整数，长度按字节计；教学实现限制 $0\le h\le31$ 、值长小于 $2^{32}$ ，摘要固定32字节。叶的索引和长度不能省略后再靠注释解释。内部两个摘要等长，因此拼接边界已确定；左右顺序不能交换。根为 $r=T_{h,0}$ 。

认证路径由 h 个兄弟摘要组成，顺序从叶向根：

\pi_j=T_{j,\,(\lfloor i/2^j\rfloor)\mathbin{\mathrm{xor}}1},\qquad 0\le j<h.

验证先拒绝越界索引、错误摘要长度以及路径长度不等于 h 的输入。然后算 z=L(i,v)，令 p=i。第 j 层按 p 的最低位决定左右：p偶数算 $z\leftarrow H(\mathtt{01}\Vert\operatorname{u8}(j+1)\Vert z\Vert\pi_j)$ ，奇数交换两个孩子；最后令 $p\leftarrow\lfloor p/2\rfloor$ 。恰好做完 h 层后，仅在 z=r 时接受。h=0 时路径为空，但仍须验证唯一叶的哈希。

直觉

验证者不需要重新拿到整个列表。它已经有当前小树的一侧摘要，只缺同层另一侧，两个合起来就能向上走一层。一路带上这些“缺失的兄弟”，最后应到达事先信任的同一个根。

路径不是一袋可以任意排序的哈希。索引的二进制位告诉我们每一步站在左边还是右边；高度告诉我们还要走几步。两者与根共同定义本次要检查的声明。内部节点和叶采用不同前缀，则一段“值的字节”不会直接被当作“两棵子树的摘要对”。

八叶树中索引2的路径依次需要叶3、叶0至1的子树和叶4至7的子树；主路径为蓝色，补充兄弟为灰色 — 只传当前路径缺失的一侧

例子与边界

八个字母的三项路径

令列表为 ASCII 字节 A、B、C、D、E、F、G、H，索引从0开始。验证 C 位于索引2，二进制为010。所需摘要依次是 $T_{0,3}$ 、 $T_{1,0}$ 、 $T_{2,1}$ ：先把 C 放在 D 左边，再把得到的 CD 放在 AB 右边，最后把 ABCD 放在 EFGH 左边。

用 SHA-256 执行上述完整编码，根为：

text

f024263693113d02f6123e0261af76188412417fc377c1360bfcac0413b59de7

这不是字符串 ABCDEFGH 的一次普通哈希。完整的三个兄弟摘要与逐项复算入口见HASH-6任务。本例验证用1次叶哈希加3次内部哈希，传输3个32字节摘要，共96字节；值、索引和外围编码另计。

把索引2改成3而保持值C和路径，叶编码及第一步方向都变了，验证失败。逆转路径顺序，或把高度改成2并截去最后一项，也失败。只比较某个中间摘要、不检查完整高度，会把子树根误当作整个列表的根。

根不自行证明来源或保密

攻击者完全可以自己编一棵树，生成正确路径，再把自己的根一起发来。路径验证只能说明它与那个根相容，不能说明根属于哪位发布者。根的身份认证与版本新鲜性必须由外部已明确的机制提供；本页没有给它们免费保证。

这个确定性摘要也不满足承诺方案的消息隐藏实验。若整个列表只可能是两个已知候选，观察者可分别算根来区分。常见说法“Merkle承诺”通常强调位置绑定；它不自动同时拥有隐藏性、零知识或不可延展性。

推论与应用

正确性与错误打开的碰撞见证

正确性对层数归纳。初始 z 等于真正的第 i 片叶摘要；若第 j 层 z 已是路径上真正节点，正确兄弟和索引方向便恢复它的父节点。h 次后 z 必为真实根。

可靠性依赖抗碰撞性。固定一棵正确构建的树，假设某个 $v\ne v_i$ 的打开仍获接受。若两份叶摘要已经相同，两个不同的规范叶输入立即给出 H 碰撞。否则，从叶向上比较真假路径：起点摘要不同，终点相同，必有第一次由不同变相同的层。在该层，两个父节点的输入字节不同，却得到同一摘要，又给出一个实际碰撞。固定标签、高度及左右宽度，使“输入不同”不是含糊的语义判断。

归约者可保存真实树并复算伪路径，在线性于路径长度的额外工作中找到这对哈希输入，不需要猜哪一层。因而若一个高效对手经常提交错误打开，也就能经常找到底层哈希碰撞。这个论证证明计算绑定，未声称碰撞数学上不存在。

成本和迁移

建满树需 N 次叶哈希及 N−1 次内部哈希，保存全部摘要占 $O(Nn)$ 字节，另计原始值。已有树上取路径只读 h 个摘要；验证需 h+1 次哈希及读取值的字节成本，工作空间可为 O(n+log N) 字节，包含摘要与索引；输入路径占 O(hn)。改变一个叶值只需重算该叶及其 h 个祖先。

终点任务：不运行脚本，列出索引5的兄弟坐标与左右次序，答案应为 $(0,4),(1,3),(2,0)$ ，方向为右、左、右。再把F改成小写f，指出受影响的节点是 $T_{0,5},T_{1,2},T_{2,1},T_{3,0}$ ；其他子树摘要仍可复用。若想同时打开多个位置，继续用多重证明共享这些兄弟；要证明某键不存在，则需稀疏树提供明确的键位置与空叶。

参考资料

RFC 9162，§2.1.1、§2.1.3：叶/内部节点分域与包含路径。该规范支持非二幂大小的树；本文刻意固定满树，并额外编码索引与层数，二者字节格式不兼容。
Dan Boneh、Victor Shoup，A Graduate Course in Applied Cryptography, v0.6，§8.9，树哈希与成员证明。本文字母例、标签、逐层碰撞提取及成本表按自己的接口独立展开。

形式陈述 ​

被认证的是位置和值 ​

八个字母的三项路径 ​

根不自行证明来源或保密 ​

正确性与错误打开的碰撞见证 ​

成本和迁移 ​