Merkle Tree
OpenZeppelin Contracts for Cairo provides a merkle_tree
package with a set of utilities for verifying Merkle Tree proofs onchain. 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 Starknetrelated.

To use it as a standalone package, you can add it in your

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. 
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 preimages are assumed to be sorted.
This function expects a

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 & preimages 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:

The empty set (i.e. the case where proof.len() == 1 && leaves.len() == 0 ) is
considered a noop, 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.

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 noncommutative 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) .
