#tree #merkle #poseidon #data #structure

no-std poseidon-merkle

Crate implementing Dusk Network's Merkle tree

5 unstable releases

0.3.0 Oct 12, 2023
0.2.1 Aug 9, 2023
0.2.1-rc.0 Jun 30, 2023
0.2.0 Jun 28, 2023
0.1.0 Jun 28, 2023

#1037 in Data structures

Download history 123/week @ 2023-08-06 47/week @ 2023-08-13 71/week @ 2023-08-20 79/week @ 2023-08-27 40/week @ 2023-09-03 63/week @ 2023-09-10 57/week @ 2023-09-17 93/week @ 2023-09-24 116/week @ 2023-10-01 165/week @ 2023-10-08 40/week @ 2023-10-15 64/week @ 2023-10-22 64/week @ 2023-10-29 211/week @ 2023-11-05 106/week @ 2023-11-12 86/week @ 2023-11-19

470 downloads per month
Used in 3 crates

MPL-2.0 license

53KB
928 lines

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.

Dependencies

~6MB
~127K SLoC