稀疏默克尔树

文档

优化的稀疏默克尔树。

特性

• 多叶存在/非存在默克尔证明
• 可自定义的哈希函数
• 后端存储无关
• Rust no_std 支持

本文描述了此数据结构的算法 一个优化的紧凑型稀疏默克尔树

构造

稀疏默克尔树是一个完全平衡的树，包含 2 ^ N 个叶子

# N = 256 sparse merkle tree
height:
                   0
                /     \
255            0        1

.............................

           /   \          /  \
1         0     1        0    1
         / \   / \      / \   / \
0       0   1 0  1 ... 0   1 0   1
       0x00..00 0x00..01   ...   0x11..11

上面的图演示了一个包含 2 ^ 256 个叶子的稀疏默克尔树，可以将每个可能的 H256 值映射到叶子。树的高度是 256，从上到下，我们用 0 表示每个左分支，用 1 表示每个右分支，因此我们可以得到一个256位的路径，这也代表一个 H256，我们使用路径作为叶子的键，最左边的叶子的键是 0x00..00，下一个键是 0x00..01，最右边的键是 0x11..11。