稀疏默克尔树

文档

一个优化的稀疏默克尔树。

特性

• 多叶子成员默克尔证明
• 可定制哈希函数
• Rust no_std 支持

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

注意 此库尚不稳定。API 和证明的格式可能在将来发生变化。在使用此库之前，请确保您知道自己在做什么。

已知问题

此库不支持 非成员 证明。我们采取了一些激进的优化方法，这些方法与非成员证明功能不兼容。

请检查此库以 非成员证明稀疏默克尔树。

构建

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

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

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

           /   \          /  \
2         0     1        0    1
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。

我们使用一个H256根和一个映射map[(usize, H256)] -> (H256, H256)来表示树，映射的键是节点及其高度，映射的值是节点的子节点，一个空树表示为空映射加上一个零H256根。

要更新一个key的value，我们从root遍历到leaf，将每个非零兄弟节点推入merkle_path向量，因为树的高度是N = 256，所以merkle_path包含256个兄弟节点。然后我们从下到上重建树：map[(height, parent)] = merge(lhs, rhs)，经过256次计算后我们得到新的root。

稀疏默克尔树包含少量有效的节点，其他都是零，我们可以为零值专门化merge函数。我们重新定义了merge函数，只有在lhs和rhs都是非零值时才进行实际计算，否则如果其中一个是零，我们只需返回另一个作为结果。

fn merge(lhs: H256, rhs: H256) -> H256 {
    if lhs.is_zero() {
        return rhs;
    } else if rhs.is_zero() {
        return lhs;
    }

    // only do actual computing when lhs and rhs both are non-zero
    merge_hash(lhs, rhs)
}

这个优化的merge函数仍然有一个问题，merge(x, zero)等于merge(zero, x)，这意味着默克尔root已损坏，因为攻击者可以轻松构造默克尔根的冲突。

为了解决这个问题，我们不是用 key 与一个 H256 value 更新，而是使用 hash(key | value) 作为合并的值，因此对于不同的键，无论值是什么，叶子节点的哈希都是唯一的。由于所有叶子都有唯一的哈希，每个高度上的节点要么通过两个不同的哈希合并，要么通过一个与零合并的哈希合并；对于非零父节点，无论哪种情况，我们都会在父节点的高度得到一个唯一的哈希。直到根节点，如果树为空，我们得到零，如果树不为空，根节点必须由两个哈希或一个与零的哈希合并，因为两个子节点的哈希是唯一的，根哈希也是唯一的。因此，攻击者无法构造碰撞攻击。

许可证

MIT