dusk-merkle

一个稀疏的默克尔树，其高度和度是参数化的。

Height 0             h
                    / \
                   /   \
                  /     \
                 /       \
                /         \
Height 1       h           h
              / \         / \
             /   \       /   \
Height 2    h     x     h     h
           / \         / \   / \
Height 3  h   x       x   h h   h
Position  0               5 6   7

Aggregate 特质定义了如何从其子节点计算父节点。对子节点的聚合方式没有限制，可以使用哈希函数或任何其他自定义聚合。空子树（在上面的树中表示为 x）用来自 Aggregate 的常量 EMPTY_SUBTREE 填充。

以下是一个父节点是其子节点总和的例子

用法

use dusk_merkle::{Tree, Aggregate};

#[derive(Debug, Clone, Copy, PartialEq)]
struct U8(u8);

impl From<u8> for U8 {
    fn from(n: u8) -> Self {
        Self(n)
    }
}

const EMPTY_ITEM: U8 = U8(0);

impl Aggregate<A> for U8 {
    const EMPTY_SUBTREE: U8 = EMPTY_ITEM;

    fn aggregate(items: [&Self; A]) -> Self
    {
        items.into_iter().fold(U8(0), |acc, c| U8(acc.0 + c.0))
    }
}

// Set the height and arity of the tree. 
const H: usize = 3;
const A: usize = 2;

let mut tree = Tree::<U8, H, A>::new();

// No elements have been inserted so the root is the empty subtree.
assert_eq!(*tree.root(), U8::EMPTY_SUBTREE);

tree.insert(4, 21);
tree.insert(7, 21);

// After elements have been inserted, the root will be modified.
assert_eq!(*tree.root(), U8(42));

包含一个使用 blake3 哈希算法实现的默克尔树的示例。

包含一个使用 poseidon252 哈希并在 PLONK 中创建零知识证明的默克尔树的另一个实现，作为此工作区 poseidon_merkle 的成员。

基准测试

还包含基准测试，可以使用以下方式运行

对于 blake3 树

cargo bench

cargo bench -p poseidon-merkle

cargo bench -p poseidon-merkle --features zk