Merkle Tree

This crate provides a set of utilities for verifying Merkle Tree proofs on-chain. The tree and the proofs can be generated using this JavaScript library.

This module provides:

  • verify - can prove that some value is part of a Merkle tree.

  • verify_multi_proof - can prove multiple values are part of a Merkle tree.

openzeppelin_merkle_tree doesn’t have dependencies outside of corelib, and can be used in projects that are not Starknet-related.

To use it as a standalone package, you can add it in your Scarb.toml as follows:

openzeppelin_merkle_tree = "0.18.0"

Modules

merkle_proof 

use openzeppelin_merkle_tree::merkle_proof;

These functions deal with verification of Merkle Tree proofs.

The tree and the proofs can be generated using this JavaScript library. You will find a quickstart guide in the readme.

You should avoid using leaf values that are two felt252 long prior to hashing, or use a hash function other than the one used to hash internal nodes for hashing leaves. This is because the concatenation of a sorted pair of internal nodes in the Merkle tree could be reinterpreted as a leaf value. The JavaScript library generates Merkle trees that are safe against this attack out of the box.
Functions

Functions

verify<+CommutativeHasher>(proof: Span<felt252>, root: felt252, leaf: felt252) → bool public

Returns true if a leaf can be proved to be a part of a Merkle tree defined by root.

For this, a proof must be provided, containing sibling hashes on the branch from the leaf to the root of the tree.

Each pair of leaves and each pair of pre-images are assumed to be sorted.

This function expects a CommutativeHasher implementation. See hashes::CommutativeHasher for more information.

verify_pedersen and verify_poseidon already include the corresponding Hasher implementations.

verify_pedersen(proof: Span<felt252>, root: felt252, leaf: felt252) → bool public

Version of verify using Perdersen as the hashing function.

verify_poseidon(proof: Span<felt252>, root: felt252, leaf: felt252) → bool public

Version of verify using Poseidon as the hashing function.

process_proof<+CommutativeHasher>(proof: Span<felt252>, leaf: felt252) → felt252 public

Returns the rebuilt hash obtained by traversing a Merkle tree up from leaf using proof.

A proof is valid if and only if the rebuilt hash matches the root of the tree.

When processing the proof, the pairs of leaves & pre-images are assumed to be sorted.

This function expects a CommutativeHasher implementation. See hashes::CommutativeHasher for more information.

verify_multi_proof<+CommutativeHasher>(proof: Span<felt252>, proof_flags: Span<bool>, root: felt252, leaves: Span<felt252>) → bool public

Returns true if the leaves can be simultaneously proven to be a part of a Merkle tree defined by root, according to proof and proof_flags as described in process_multi_proof.

The leaves must be validated independently.

Not all Merkle trees admit multiproofs. See process_multi_proof for details.
Consider the case where root == proof.at(0) && leaves.len() == 0 as it will return true.
This function expects a CommutativeHasher implementation. See hashes::CommutativeHasher for more information.

process_multi_proof<+CommutativeHasher>(proof: Span<felt252>, proof_flags: Span<bool>, leaves: Span<felt252>) → felt252 public

Returns the root of a tree reconstructed from leaves and sibling nodes in proof.

The reconstruction proceeds by incrementally reconstructing all inner nodes by combining a leaf/inner node with either another leaf/inner node or a proof sibling node, depending on whether each proof_flags item is true or false respectively.

Not all Merkle trees admit multiproofs. To use multiproofs, it is sufficient to ensure that:

  1. The tree is complete (but not necessarily perfect).

  2. The leaves to be proven are in the opposite order they are in the tree. (i.e., as seen from right to left starting at the deepest layer and continuing at the next layer).
The empty set (i.e. the case where proof.len() == 1 && leaves.len() == 0) is considered a no-op, and therefore a valid multiproof (i.e. it returns proof.at(0)). Consider disallowing this case if you’re not validating the leaves elsewhere.
This function expects a CommutativeHasher implementation. See hashes::CommutativeHasher for more information.

hashes 

use openzeppelin_merkle_tree::hashes;

Module providing the trait and default implementations for the commutative hash functions used in merkle_proof.

The PedersenCHasher implementation matches the default node hashing function used in the JavaScript library.
Traits
Impls

Traits

CommutativeHasher trait

Declares a commutative hash function with the following signature:

commutative_hash(a: felt252, b: felt252) → felt252;

which computes a commutative hash of a sorted pair of felt252.

This is usually implemented as an extension of a non-commutative hash function, like Pedersen or Poseidon, returning the hash of the concatenation of the two values by first sorting them.

Frequently used when working with merkle proofs.

The commutative_hash function MUST follow the invariant that commutative_hash(a, b) == commutative_hash(b, a).

Impls

PedersenCHasher impl

Implementation of the CommutativeHasher trait which computes the Pedersen hash of chaining the two input values with the len (2), sorting the pair first.

PoseidonCHasher impl

Implementation of the CommutativeHasher trait which computes the Poseidon hash of the concatenation of two values, sorting the pair first.

← API Reference
Security →