openzeppelin_merkle_tree

Fully qualified path: openzeppelin_merkle_tree

Modules

Modules

Modules

hashes

Fully qualified path: openzeppelin_merkle_tree::hashes

Traits

Impls

Traits

Traits

CommutativeHasher

Computes a commutative hash of a sorted pair of felt252 values.

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.

Fully qualified path: openzeppelin_merkle_tree::hashes::CommutativeHasher

pub trait CommutativeHasher

Trait functions

commutative_hash

Fully qualified path: openzeppelin_merkle_tree::hashes::CommutativeHasher::commutative_hash

fn commutative_hash(a: felt252, b: felt252) -> felt252

Impls

Impls

PedersenCHasher

Computes the Pedersen commutative hash of a sorted pair of felt252 values.

Fully qualified path: openzeppelin_merkle_tree::hashes::PedersenCHasher

pub impl PedersenCHasher of CommutativeHasher;

Impl functions

commutative_hash

Computes the Pedersen hash by chaining the two values with the length, sorting the pair first.

Fully qualified path: openzeppelin_merkle_tree::hashes::PedersenCHasher::commutative_hash

fn commutative_hash(a: felt252, b: felt252) -> felt252

PoseidonCHasher

Computes the Poseidon commutative hash of a sorted pair of felt252 values.

Fully qualified path: openzeppelin_merkle_tree::hashes::PoseidonCHasher

pub impl PoseidonCHasher of CommutativeHasher;

Impl functions

commutative_hash

Computes the Poseidon hash of the concatenation of two values, sorting the pair first.

Fully qualified path: openzeppelin_merkle_tree::hashes::PoseidonCHasher::commutative_hash

fn commutative_hash(a: felt252, b: felt252) -> felt252

merkle_proof

Fully qualified path: openzeppelin_merkle_tree::merkle_proof

Free functions

Free functions

Free functions

verify

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.

Fully qualified path: openzeppelin_merkle_tree::merkle_proof::verify

pub fn verify<impl Hasher: CommutativeHasher>(
    proof: Span<felt252>, root: felt252, leaf: felt252,
) -> bool

verify_pedersen

Version of verify using Pedersen as the hashing function.

Fully qualified path: openzeppelin_merkle_tree::merkle_proof::verify_pedersen

pub fn verify_pedersen(proof: Span<felt252>, root: felt252, leaf: felt252) -> bool

verify_poseidon

Version of verify using Poseidon as the hashing function.

Fully qualified path: openzeppelin_merkle_tree::merkle_proof::verify_poseidon

pub fn verify_poseidon(proof: Span<felt252>, root: felt252, leaf: felt252) -> bool

process_proof

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.

Fully qualified path: openzeppelin_merkle_tree::merkle_proof::process_proof

pub fn process_proof<impl Hasher: CommutativeHasher>(proof: Span<felt252>, leaf: felt252) -> felt252

verify_multi_proof

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.

CAUTION: Not all Merkle trees admit multiproofs. See process_multi_proof for details.

NOTE: Consider the case where root == proof.at(0) && leaves.len() == 0 as it will return true.

The leaves must be validated independently. See process_multi_proof.

Fully qualified path: openzeppelin_merkle_tree::merkle_proof::verify_multi_proof

pub fn verify_multi_proof<impl Hasher: CommutativeHasher>(
    proof: Span<felt252>, proof_flags: Span<bool>, root: felt252, leaves: Span<felt252>,
) -> bool

process_multi_proof

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.

CAUTION: 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 than they are in the tree (i.e., as seen from right to left starting at the deepest layer and continuing at the next layer).

NOTE: 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.

Fully qualified path: openzeppelin_merkle_tree::merkle_proof::process_multi_proof

pub fn process_multi_proof<impl Hasher: CommutativeHasher>(
    proof: Span<felt252>, proof_flags: Span<bool>, leaves: Span<felt252>,
) -> felt252