本文介绍了二叉Merkle树的结构、算法和安全性。Merkle树通过递归哈希数据块列表来生成唯一的根哈希，用于高效地进行数据一致性验证和成员资格证明。文章详细描述了叶子节点的顺序、层级顺序和规范构建方法，并提供了测试向量。
二叉 Merkle 树
用法
二叉哈希树便于对任意数据 blob 列表进行相等性检查。
每棵树都锚定在一个 32 字节的 根哈希 中，该哈希通过递归地将两棵树节点对哈希为一个节点来构建。
Merkle 证明将任意数据等同于树中的条目，它的大小简洁，与输入数据无关。
结构
- 每个树节点都由 SHA-256 哈希标识。
- 存在两种类型的节点：叶 节点和中间节点。
- 叶节点 的原像是字节
0x00，后跟任意数量的数据。
- 中间节点 的原像是字节
0x01，后跟两个 32 字节的哈希，每个哈希都指向一个节点。
- 每个节点都有一个或零个父中间节点。
- 节点图表示一棵二叉树，因此是无环的，并且有一个 根节点。
算法
叶顺序
树的叶顺序由从根开始的深度优先搜索遍历定义，仅计算叶节点。
示例
图 1 中树的叶顺序是 [Lβ, Lα, Lδ]。
<a id="figure_1"></a>
图 1：具有三个叶节点和两个中间节点的非规范树
Iε
/ \
Iγ Lδ
/ \
Lβ Lα
层顺序
树的层顺序由从根开始的深度优先搜索定义，仅计算具有给定级别的节点。
示例
图 1 中的树具有以下层顺序：
0: [Iε]1: [Iγ, Lδ]2: [Lβ, Lα]
规范构造
构造算法确定性地创建一个基于项目列表的树结构。
确定性确保在相同项目上独立构造的树是相同的。
这是相等性和成员资格检查所必需的。
任何任意项目列表的规范树布局由以下不变性定义：
- 每个列表项对应一个叶节点。
- 列表项的顺序与叶节点的顺序匹配。
- 每个叶节点都位于最深的树级别。
- 对于任何级别
l 且节点数为 n(l)，如果 n(l) % 2 == 1 and n(l) > 1，
则级别 l-1 中的最后一个节点是一个中间节点，其中包含 l 中最后一个节点的哈希两次。
示例
图 2 显示了项目 [L0, L1, L2, L3, L4] 的规范构造。
<a id="figure_2"></a>
图 2：具有 5 个项目的规范树
Iζ
/ \
/ \
Iδ Iε
/ \ \\
/ \ \\
Iα Iβ Iγ
/ \ / \ ||
L0 L1 L2 L3 L4
节点内容：
L0 := sha256(concat(0x00, data[0]))L1 := sha256(concat(0x00, data[1]))L2 := sha256(concat(0x00, data[2]))L3 := sha256(concat(0x00, data[3]))L4 := sha256(concat(0x00, data[4]))Iα := sha256(concat(0x01, hash(L0), hash(L1)))Iβ := sha256(concat(0x01, hash(L2), hash(L3)))Iγ := sha256(concat(0x01, hash(L4), hash(L4)))Iδ := sha256(concat(0x01, hash(Iα), hash(Iβ)))Iε := sha256(concat(0x01, hash(Iγ), hash(Iγ)))Iζ := sha256(concat(0x01, hash(Iδ), hash(Iε)))
列表相等性检查
检查两棵 merkle 树的相等性非常简单：比较任一棵树的根的哈希。
安全性
截至 2022 年 10 月，尚未发现针对 SHA-256 的实际冲突攻击。
抗冲突性对于确保节点图保持无环，并且每个哈希明确地指向一个逻辑节点至关重要。
测试向量
<table>
<caption>规范根测试向量</caption>
<thead>
<tr>
<th>项目 (UTF-8)</th>
<th>根哈希 (十六进制)</th>
</tr>
</thead>
<tbody>
<tr>
<td><code>['test']</code></td>
<td><code>dbebd10e61bc8c28591273feafbbef95d544f874693301d8f7f8e54c6e30058e</code></td>
</tr>
<tr>
<td><code>['my', 'very', 'eager', 'mother', 'just', 'served', 'us', 'nine', 'pizzas', 'make', 'prime']</code></td>
<td><code>b40c847546fdceea166f927fc46c5ca33c3638236a36275c1346d3dffb84e1bc</code></td>
</tr>
</tbody>
</table>
