A sparsely populated Merkle Tree, 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
The Aggregate
trait defines how to calculate a parent from its children.
There is no restrictions on the way the children are aggregated, it can be done
with a hash function or any other custom aggregation.
Empty subtrees (noted as x
in the tree above) are filled with the constant
EMPTY_SUBTREE
from Aggregate
.
Here an example where the parent is the sum of its children:
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));
An implementation of a Merkle tree using the blake3
hash algorithm is included
as an example.
Another implementation of a Merkle tree with the poseidon252
hash and the
creation of the opening proof in zero-knowledge using PLONK is included as a
member of this workspace poseidon_merkle
.
Benchmarks are also included and can be run using:
For the blake3
tree:
cargo bench
For the poseidon
tree:
cargo bench -p poseidon-merkle
For the opening proof creation in zero-knowledge:
cargo bench -p poseidon-merkle --features zk
This requires a nightly toolchain.
A merkle tree using the poseidon hash function for aggregation and plonk to generate an opening proof in zero-knowledge can be found in the same workspace under 'poseidon-merkle'.
This project is licensed under the Mozilla Public License, version 2.0. See the license file for more details.