dusk-merkle

A sparsely populated dusk_merkle merkle tree, which uses the poseidon hash algorithm for level aggregation and is parametrized over its height and arity.

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

Additionally to the tree itself, this crate defines an opening gadget that can be used to create a merkle opening circuit for zero-knowledge applications under the "zk" feature.

The type Item<T> has the aggregation of the hash part with the poseidon hash pre-defined and additionally allows for a custom data type with custom aggregation.

Benchmarks

There are benchmarks for the poseidon tree calculation available with

cargo bench

and additional benchmarks for the opening proof generation with PLONK

cargo bench --features zk

This requires a nightly toolchain.

License

This project is licensed under the Mozilla Public License, version 2.0. See the license file for more details.