#merkle-tree #tree #merkle #poseidon #data #structure #data-structures

no-std poseidon-merkle

Crate implementing Dusk Network's Merkle tree with the poseidon hash function

10 releases (6 breaking)

0.7.0 Aug 14, 2024
0.6.0 May 22, 2024
0.5.0 Jan 3, 2024
0.4.0 Dec 13, 2023
0.2.1-rc.0 Jun 30, 2023

#6 in #poseidon

Download history 5/week @ 2024-07-10 5/week @ 2024-07-17 19/week @ 2024-07-24 148/week @ 2024-08-07 250/week @ 2024-08-14 44/week @ 2024-08-21 67/week @ 2024-08-28 313/week @ 2024-09-04 130/week @ 2024-09-11 85/week @ 2024-09-18 217/week @ 2024-09-25 173/week @ 2024-10-02 233/week @ 2024-10-09 229/week @ 2024-10-16

887 downloads per month
Used in 5 crates

MPL-2.0 license

55KB
960 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

~3.5–4.5MB
~101K SLoC