二叉 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α]
规范构造
构造算法确定性地在项目列表上创建树结构。
确定性确保在相同项目上独立构建的树是相同的。
这是相等性和成员资格检查所必需的。
对于任何任意项目列表，规范 树布局由以下不变性定义：
- 每个列表项对应一个叶子节点。
- 列表项的顺序与叶子节点的顺序匹配。
- 每个叶子节点都在最深的树级别。
- 对于任何具有节点数
n(l) 的级别 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>
