Repository: OpenZeppelin/cairo-contracts (language: python)

Issue:
Merkle proof verifier
See [MerkleProof.sol](https://github.com/OpenZeppelin/openzeppelin-contracts/blob/7417c5946f8a213a8e61eca8d3c5247bf3854249/contracts/utils/cryptography/MerkleProof.sol)


Discussion / hints:

Fix patch:
diff --git a/CHANGELOG.md b/CHANGELOG.md
index b86f9f432..87545db3c 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -12,6 +12,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 ### Added
 
 - ERC2981 (NFT Royalty Standard) component (#1091)
+- `merkle_tree` package with utilities to verify proofs and multi proofs (#1101)
 
 ### Changed
 
@@ -22,6 +23,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0
 - Changed ABI suffix to Trait in dual case account and eth account modules (#1096).
   - `DualCaseAccountABI` renamed to `DualCaseAccountTrait`
   - `DualCaseEthAccountABI` renamed to `DualCaseEthAccountTrait`
+- Bump scarb to v2.7.1 (#1025)
 
 ## 0.15.1 (2024-08-13)
 
diff --git a/Scarb.lock b/Scarb.lock
index 3e044ff3f..7e5374192 100644
--- a/Scarb.lock
+++ b/Scarb.lock
@@ -9,6 +9,7 @@ dependencies = [
  "openzeppelin_account",
  "openzeppelin_governance",
  "openzeppelin_introspection",
+ "openzeppelin_merkle_tree",
  "openzeppelin_presets",
  "openzeppelin_security",
  "openzeppelin_test_common",
@@ -58,6 +59,13 @@ dependencies = [
  "snforge_std",
 ]
 
+[[package]]
+name = "openzeppelin_merkle_tree"
+version = "0.15.1"
+dependencies = [
+ "snforge_std",
+]
+
 [[package]]
 name = "openzeppelin_presets"
 version = "0.15.1"
diff --git a/Scarb.toml b/Scarb.toml
index 414893774..f7b94f96a 100644
--- a/Scarb.toml
+++ b/Scarb.toml
@@ -4,6 +4,7 @@ members = [
     "packages/account",
     "packages/governance",
     "packages/introspection",
+    "packages/merkle_tree",
     "packages/presets",
     "packages/security",
     "packages/token",
@@ -20,8 +21,8 @@ version.workspace = true
 [workspace.package]
 version = "0.15.1"
 edition = "2023_11"
-cairo-version = "2.7.0"
-scarb-version = "2.7.0"
+cairo-version = "2.7.1"
+scarb-version = "2.7.1"
 authors = ["OpenZeppelin Community <maintainers@openzeppelin.org>"]
 description = "OpenZeppelin Contracts written in Cairo for Starknet, a decentralized ZK Rollup"
 documentation = "https://docs.openzeppelin.com/contracts-cairo"
@@ -34,11 +35,11 @@ keywords = [
     "cairo",
     "contracts",
     "security",
-    "standards",
+    "standards"
 ]
 
 [workspace.dependencies]
-starknet = "2.7.0"
+starknet = "2.7.1"
 snforge_std = { git = "https://github.com/foundry-rs/starknet-foundry.git", tag = "v0.27.0" }
 
 [dependencies]
@@ -47,6 +48,7 @@ openzeppelin_access = { path = "packages/access" }
 openzeppelin_account = { path = "packages/account" }
 openzeppelin_governance = { path = "packages/governance" }
 openzeppelin_introspection = { path = "packages/introspection" }
+openzeppelin_merkle_tree = { path = "packages/merkle_tree" }
 openzeppelin_presets = { path = "packages/presets" }
 openzeppelin_security = { path = "packages/security" }
 openzeppelin_token = { path = "packages/token" }
diff --git a/_typos.toml b/_typos.toml
new file mode 100644
index 000000000..e05c33bd2
--- /dev/null
+++ b/_typos.toml
@@ -0,0 +1,4 @@
+[default]
+extend-ignore-identifiers-re = [
+    "e288874ba",
+]
diff --git a/docs/modules/ROOT/nav.adoc b/docs/modules/ROOT/nav.adoc
index d74be18aa..b005c159f 100644
--- a/docs/modules/ROOT/nav.adoc
+++ b/docs/modules/ROOT/nav.adoc
@@ -24,6 +24,8 @@
 *** xref:/guides/src5-migration.adoc[Migrating ERC165 to SRC5]
 *** xref:/api/introspection.adoc[API Reference]
 
+** xref:/api/merkle-tree.adoc[Merkle Tree]
+
 ** xref:security.adoc[Security]
 *** xref:/api/security.adoc[API Reference]
 
diff --git a/docs/modules/ROOT/pages/api/merkle-tree.adoc b/docs/modules/ROOT/pages/api/merkle-tree.adoc
new file mode 100644
index 000000000..563a33208
--- /dev/null
+++ b/docs/modules/ROOT/pages/api/merkle-tree.adoc
@@ -0,0 +1,208 @@
+:github-icon: pass:[<svg class="icon"><use href="#github-icon"/></svg>]
+:strk-merkle-tree: https://github.com/ericnordelo/strk-merkle-tree[JavaScript library]
+:verify: xref:#merkle_proof-verify[verify]
+:verify_pedersen: xref:#merkle_proof-verify_perdersen[verify_pedersen]
+:verify_poseidon: xref:#merkle_proof-verify_poseidon[verify_poseidon]
+:verify_multi_proof: xref:#merkle_proof-verify_multi_proof[verify_multi_proof]
+:process_multi_proof: xref:#merkle_proof-process_multi_proof[process_multi_proof]
+
+= Merkle Tree
+
+OpenZeppelin Contracts for Cairo provides a `merkle_tree` package with a set of utilities for verifying Merkle Tree proofs on-chain. The tree and the proofs can be generated using this {strk-merkle-tree}.
+
+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.
+
+NOTE: `openzeppelin_merkle_tree` doesn't have dependencies outside of `corelib`, and can be used in projects that are not Starknet-related.
+
+[TIP]
+====
+To use it as a standalone package, you can add it in your `Scarb.toml` as follows:
+
+`openzeppelin_merkle_tree = { git = "https://github.com/openzeppelin/cairo-contracts.git", tag = "v0.X.X" }`
+====
+
+== Modules
+
+[.contract]
+[[merkle_proof]]
+=== `++merkle_proof++` link:https://github.com/OpenZeppelin/cairo-contracts/blob/release-v0.15.1/packages/merkle_tree/src/merkle_proof.cairo[{github-icon},role=heading-link]
+
+```cairo
+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 {strk-merkle-tree}. You will find a quickstart guide in the readme.
+
+WARNING: 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.
+
+[.contract-index]
+.Functions
+--
+* xref:#merkle_proof-verify[`++verify<Hasher>(proof, root, leaf)++`]
+* xref:#merkle_proof-verify_pedersen[`++verify_pedersen(proof, root, leaf)++`]
+* xref:#merkle_proof-verify_poseidon[`++verify_poseidon(proof, root, leaf)++`]
+* xref:#merkle_proof-process_proof[`++process_proof<Hasher>(proof, leaf)++`]
+* xref:#merkle_proof-verify_multi_proof[`++verify_multi_proof<Hasher>(proof, proof_flags, root, leaves)++`]
+* xref:#merkle_proof-process_multi_proof[`++process_multi_proof<Hasher>(proof, proof_flags, leaf)++`]
+--
+
+[#merkle_proof-Functions]
+==== Functions
+
+[.contract-item]
+[[merkle_proof-verify]]
+==== `[.contract-item-name]#++verify<+CommutativeHasher>++#++(proof: Span<felt252>, root: felt252, leaf: felt252) → bool++` [.item-kind]#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.
+
+[NOTE]
+====
+This function expects a `CommutativeHasher` implementation. See xref:#hashes-CommutativeHasher[hashes::CommutativeHasher] for more information.
+
+`{verify_pedersen}` and `{verify_poseidon}` already include the corresponding `Hasher` implementations.
+====
+
+[.contract-item]
+[[merkle_proof-verify_pedersen]]
+==== `[.contract-item-name]#++verify_pedersen++#++(proof: Span<felt252>, root: felt252, leaf: felt252) → bool++` [.item-kind]#public#
+
+Version of `{verify}` using Perdersen as the hashing function.
+
+[.contract-item]
+[[merkle_proof-verify_poseidon]]
+==== `[.contract-item-name]#++verify_poseidon++#++(proof: Span<felt252>, root: felt252, leaf: felt252) → bool++` [.item-kind]#public#
+
+Version of `{verify}` using Poseidon as the hashing function.
+
+[.contract-item]
+[[merkle_proof-process_proof]]
+==== `[.contract-item-name]#++process_proof<+CommutativeHasher>++#++(proof: Span<felt252>, leaf: felt252) → felt252++` [.item-kind]#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.
+
+NOTE: This function expects a `CommutativeHasher` implementation. See xref:#hashes-CommutativeHasher[hashes::CommutativeHasher] for more information.
+
+[.contract-item]
+[[merkle_proof-verify_multi_proof]]
+==== `[.contract-item-name]#++verify_multi_proof<+CommutativeHasher>++#++(proof: Span<felt252>, proof_flags: Span<bool>, root: felt252, leaves: Span<felt252>) → bool++` [.item-kind]#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.
+
+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`.
+
+NOTE: This function expects a `CommutativeHasher` implementation. See xref:#hashes-CommutativeHasher[hashes::CommutativeHasher] for more information.
+
+[.contract-item]
+[[merkle_proof-process_multi_proof]]
+==== `[.contract-item-name]#++process_multi_proof<+CommutativeHasher>++#++(proof: Span<felt252>, proof_flags: Span<bool>, leaves: Span<felt252>) → felt252++` [.item-kind]#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.
+
+[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 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.
+
+NOTE: This function expects a `CommutativeHasher` implementation. See xref:#hashes-CommutativeHasher[hashes::CommutativeHasher] for more information.
+
+
+[.contract]
+[[hashes]]
+=== `++hashes++` link:https://github.com/OpenZeppelin/cairo-contracts/blob/release-v0.15.1/packages/merkle_tree/src/hashes.cairo[{github-icon},role=heading-link]
+
+```cairo
+use openzeppelin_merkle_tree::hashes;
+```
+
+:pedersen-hasher: xref:#hashes-PedersenCHasher[PedersenCHasher]
+:poseidon-hasher: xref:#hashes-PoseidonCHasher[PoseidonCHasher]
+
+Module providing the trait and default implementations for the commutative hash functions used in
+xref:#merkle_proof[`merkle_proof`].
+
+NOTE: The `{pedersen-hasher}` implementation matches the default node hashing function used in the {strk-merkle-tree}.
+
+[.contract-index]
+.Traits
+--
+* xref:#hashes-CommutativeHasher[`++CommutativeHasher++`]
+--
+
+[.contract-index]
+.Impls
+--
+* xref:#hashes-PedersenCHasher[`++PedersenCHasher++`]
+* xref:#hashes-PoseidonCHasher[`++PoseidonCHasher++`]
+--
+
+[#hashes-Traits]
+==== Traits
+
+[.contract-item]
+[[hashes-CommutativeHasher]]
+==== `[.contract-item-name]#++CommutativeHasher++#` [.item-kind]#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.
+
+NOTE: The `commutative_hash` function MUST follow the invariant that `commutative_hash(a, b) == commutative_hash(b, a)`.
+
+[#hashes-Impls]
+==== Impls
+
+[.contract-item]
+[[hashes-PedersenCHasher]]
+==== `[.contract-item-name]#++PedersenCHasher++#` [.item-kind]#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.
+
+[.contract-item]
+[[hashes-PoseidonCHasher]]
+==== `[.contract-item-name]#++PoseidonCHasher++#` [.item-kind]#impl#
+
+Implementation of the `CommutativeHasher` trait which computes the Poseidon hash of the concatenation of two values, sorting the pair first.
diff --git a/docs/modules/ROOT/pages/guides/snip12.adoc b/docs/modules/ROOT/pages/guides/snip12.adoc
index 2cf8e9b88..190c66456 100644
--- a/docs/modules/ROOT/pages/guides/snip12.adoc
+++ b/docs/modules/ROOT/pages/guides/snip12.adoc
@@ -351,7 +351,7 @@ mod CustomERC20 {
         let is_valid_signature_felt = DualCaseAccount { contract_address: owner }
             .is_valid_signature(hash, signature);
 
-        // Check either 'VALID' or True for backwards compatibility
+        // Check either 'VALID' or true for backwards compatibility
         let is_valid_signature = is_valid_signature_felt == starknet::VALIDATED
             || is_valid_signature_felt == 1;
         assert(is_valid_signature, 'Invalid signature');
diff --git a/docs/modules/ROOT/pages/index.adoc b/docs/modules/ROOT/pages/index.adoc
index 0099eb284..01ba6ad81 100644
--- a/docs/modules/ROOT/pages/index.adoc
+++ b/docs/modules/ROOT/pages/index.adoc
@@ -21,8 +21,8 @@ before proceeding, and run the following command to check that the installation
 ----
 $ scarb --version
 
-scarb 2.7.0 (e9a2b8716 2024-08-01)
-cairo: 2.7.0 (https://crates.io/crates/cairo-lang-compiler/2.7.0)
+scarb 2.7.1 (e288874ba 2024-08-13)
+cairo: 2.7.1 (https://crates.io/crates/cairo-lang-compiler/2.7.1)
 sierra: 1.6.0
 ----
 
diff --git a/packages/merkle_tree/Scarb.toml b/packages/merkle_tree/Scarb.toml
new file mode 100644
index 000000000..39472084f
--- /dev/null
+++ b/packages/merkle_tree/Scarb.toml
@@ -0,0 +1,21 @@
+
+[package]
+name = "openzeppelin_merkle_tree"
+version.workspace = true
+edition.workspace = true
+cairo-version.workspace = true
+scarb-version.workspace = true
+authors.workspace = true
+description.workspace = true
+documentation.workspace = true
+readme.workspace = true
+repository.workspace = true
+license-file.workspace = true
+keywords.workspace = true
+
+[tool]
+fmt.workspace = true
+
+[dev-dependencies]
+starknet.workspace = true
+snforge_std.workspace = true
diff --git a/packages/merkle_tree/src/hashes.cairo b/packages/merkle_tree/src/hashes.cairo
new file mode 100644
index 000000000..d65a8029d
--- /dev/null
+++ b/packages/merkle_tree/src/hashes.cairo
@@ -0,0 +1,68 @@
+// SPDX-License-Identifier: MIT
+// OpenZeppelin Contracts for Cairo v0.15.1 (merkle_tree/hashes.cairo)
+
+use core::hash::HashStateTrait;
+use core::pedersen::PedersenTrait;
+use core::poseidon::PoseidonTrait;
+use core::traits::PartialOrd;
+
+/// 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.
+pub trait CommutativeHasher {
+    fn commutative_hash(a: felt252, b: felt252) -> felt252;
+}
+
+/// Computes Pedersen's commutative hash of a sorted pair of felt252.
+pub impl PedersenCHasher of CommutativeHasher {
+    /// Computes the Pedersen hash of chaining the two values
+    /// with the len, sorting the pair first.
+    fn commutative_hash(a: felt252, b: felt252) -> felt252 {
+        let hash_state = PedersenTrait::new(0);
+        if a < b {
+            hash_state.update(a).update(b).update(2).finalize()
+        } else {
+            hash_state.update(b).update(a).update(2).finalize()
+        }
+    }
+}
+
+/// Computes Poseidon's commutative hash of a sorted pair of felt252.
+pub impl PoseidonCHasher of CommutativeHasher {
+    /// Computes the Poseidon hash of the concatenation of two values, sorting the pair first.
+    fn commutative_hash(a: felt252, b: felt252) -> felt252 {
+        let hash_state = PoseidonTrait::new();
+        if a < b {
+            hash_state.update(a).update(b).finalize()
+        } else {
+            hash_state.update(b).update(a).finalize()
+        }
+    }
+}
+
+impl Felt252AsIntPartialOrd of PartialOrd<felt252> {
+    #[inline(always)]
+    fn le(lhs: felt252, rhs: felt252) -> bool {
+        let lhs: u256 = lhs.into();
+        lhs <= rhs.into()
+    }
+    #[inline(always)]
+    fn ge(lhs: felt252, rhs: felt252) -> bool {
+        let lhs: u256 = lhs.into();
+        lhs >= rhs.into()
+    }
+    #[inline(always)]
+    fn lt(lhs: felt252, rhs: felt252) -> bool {
+        let lhs: u256 = lhs.into();
+        lhs < rhs.into()
+    }
+    #[inline(always)]
+    fn gt(lhs: felt252, rhs: felt252) -> bool {
+        let lhs: u256 = lhs.into();
+        lhs > rhs.into()
+    }
+}
diff --git a/packages/merkle_tree/src/lib.cairo b/packages/merkle_tree/src/lib.cairo
new file mode 100644
index 000000000..c09b1787e
--- /dev/null
+++ b/packages/merkle_tree/src/lib.cairo
@@ -0,0 +1,5 @@
+pub mod hashes;
+pub mod merkle_proof;
+
+#[cfg(test)]
+mod tests;
diff --git a/packages/merkle_tree/src/merkle_proof.cairo b/packages/merkle_tree/src/merkle_proof.cairo
new file mode 100644
index 000000000..250a67842
--- /dev/null
+++ b/packages/merkle_tree/src/merkle_proof.cairo
@@ -0,0 +1,145 @@
+// SPDX-License-Identifier: MIT
+// OpenZeppelin Contracts for Cairo v0.15.1 (merkle_tree/merkle_proof.cairo)
+
+/// These functions deal with verification of Merkle Tree proofs.
+///
+/// WARNING: You should avoid using leaf values that are two felt252 long prior to
+/// hashing, or use a different hash function for hashing leaves and pre-images.
+/// This is because the concatenation of a sorted pair of internal nodes in
+/// the Merkle tree could be reinterpreted as a leaf value.
+///
+/// NOTE: This library supports proof verification for merkle trees built using
+/// custom _commutative_ hashing functions (i.e. `H(a, b) == H(b, a)`). Proving
+/// leaf inclusion in trees built using non-commutative hashing functions requires
+/// additional logic that is not supported by this library.
+
+use openzeppelin_merkle_tree::hashes::{CommutativeHasher, PedersenCHasher, PoseidonCHasher};
+
+/// 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.
+pub fn verify<impl Hasher: CommutativeHasher>(
+    proof: Span<felt252>, root: felt252, leaf: felt252
+) -> bool {
+    process_proof::<Hasher>(proof, leaf) == root
+}
+
+/// Version of `verify` using Perdersen as the hashing function.
+pub fn verify_pedersen(proof: Span<felt252>, root: felt252, leaf: felt252) -> bool {
+    verify::<PedersenCHasher>(proof, root, leaf)
+}
+
+/// Version of `verify` using Poseidon as the hashing function.
+pub fn verify_poseidon(proof: Span<felt252>, root: felt252, leaf: felt252) -> bool {
+    verify::<PoseidonCHasher>(proof, root, leaf)
+}
+
+/// 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.
+pub fn process_proof<impl Hasher: CommutativeHasher>(
+    proof: Span<felt252>, leaf: felt252
+) -> felt252 {
+    let mut computed_hash = leaf;
+    for hash in proof {
+        computed_hash = Hasher::commutative_hash(computed_hash, *hash);
+    };
+    computed_hash
+}
+
+/// 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`.
+pub fn verify_multi_proof<impl Hasher: CommutativeHasher>(
+    proof: Span<felt252>, proof_flags: Span<bool>, root: felt252, leaves: Span<felt252>
+) -> bool {
+    process_multi_proof::<Hasher>(proof, proof_flags, leaves) == root
+}
+
+/// 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 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.
+pub fn process_multi_proof<impl Hasher: CommutativeHasher>(
+    proof: Span<felt252>, proof_flags: Span<bool>, leaves: Span<felt252>
+) -> felt252 {
+    // This function rebuilds the root hash by traversing the tree up from the leaves. The root is
+    // rebuilt by consuming and producing values on a queue. The queue starts with the `leaves`
+    // span, then goes onto the `hashes` span. At the end of the process, the last hash in the
+    // `hashes` span should contain the root of the Merkle tree.
+    let leaves_len = leaves.len();
+    let proof_flags_len = proof_flags.len();
+
+    // Check proof validity.
+    if (leaves_len + proof.len() != proof_flags_len + 1) {
+        panic!("MerkleProof: invalid multi proof");
+    }
+
+    // The x_pos values are "pointers" to the next value to consume in each array.
+    // By incrementing the value we simulate a queue's pop operation.
+    let mut hashes = array![];
+    let mut leaf_pos = 0;
+    let mut hash_pos = 0;
+    let mut proof_pos = 0;
+    let mut i = 0;
+
+    // At each step, we compute the next hash using two values:
+    // - a value from the "main queue". If not all leaves have been consumed, we get the next leaf,
+    // otherwise we get the next hash.
+    // - depending on the flag, either another value from the "main queue" (merging branches) or an
+    // element from the `proof` array.
+    while i < proof_flags_len {
+        let a = if leaf_pos < leaves_len {
+            leaf_pos += 1;
+            leaves.at(leaf_pos - 1)
+        } else {
+            hash_pos += 1;
+            hashes.at(hash_pos - 1)
+        };
+
+        let b = if *proof_flags.at(i) {
+            if leaf_pos < leaves_len {
+                leaf_pos += 1;
+                leaves.at(leaf_pos - 1)
+            } else {
+                hash_pos += 1;
+                hashes.at(hash_pos - 1)
+            }
+        } else {
+            proof_pos += 1;
+            proof.at(proof_pos - 1)
+        };
+
+        hashes.append(Hasher::commutative_hash(*a, *b));
+        i += 1;
+    };
+
+    let root = if proof_flags_len > 0 {
+        hashes.at(proof_flags_len - 1)
+    } else if leaves_len > 0 {
+        // If `proof_flags_len` is zero, and `leaves_len` is greater then zero,
+        // then `leaves_len` can only be 1, because of the proof validity check.
+        leaves.at(0)
+    } else {
+        proof.at(0)
+    };
+
+    *root
+}
diff --git a/packages/token/src/erc20/extensions/erc20_votes.cairo b/packages/token/src/erc20/extensions/erc20_votes.cairo
index b13cd160d..d30a937ba 100644
--- a/packages/token/src/erc20/extensions/erc20_votes.cairo
+++ b/packages/token/src/erc20/extensions/erc20_votes.cairo
@@ -163,7 +163,7 @@ pub mod ERC20VotesComponent {
             let is_valid_signature_felt = DualCaseAccount { contract_address: delegator }
                 .is_valid_signature(hash, signature);
 
-            // Check either 'VALID' or True for backwards compatibility.
+            // Check either 'VALID' or true for backwards compatibility.
             let is_valid_signature = is_valid_signature_felt == starknet::VALIDATED
                 || is_valid_signature_felt == 1;
 
diff --git a/packages/utils/src/deployments.cairo b/packages/utils/src/deployments.cairo
index 4662c10dc..da19648c8 100644
--- a/packages/utils/src/deployments.cairo
+++ b/packages/utils/src/deployments.cairo
@@ -18,8 +18,8 @@ pub const CONTRACT_ADDRESS_PREFIX: felt252 = 'STARKNET_CONTRACT_ADDRESS';
 /// Returns the contract address from a `deploy_syscall`.
 /// `deployer_address` should be the zero address if the deployment is origin-independent (deployed
 /// from zero).
-/// For more information, see
 ///
+/// For more information, see
 /// https://docs.starknet.io/documentation/architecture_and_concepts/Smart_Contracts/contract-address/
 pub fn calculate_contract_address_from_deploy_syscall(
     salt: felt252,
diff --git a/packages/utils/src/lib.cairo b/packages/utils/src/lib.cairo
index 6d8ad3972..8892e3b70 100644
--- a/packages/utils/src/lib.cairo
+++ b/packages/utils/src/lib.cairo
@@ -1,5 +1,5 @@
 // SPDX-License-Identifier: MIT
-// OpenZeppelin Contracts for Cairo v0.15.1 (utils.cairo)
+// OpenZeppelin Contracts for Cairo v0.15.1 (utils/lib.cairo)
 
 pub mod cryptography;
 pub mod deployments;
diff --git a/src/lib.cairo b/src/lib.cairo
index 9c8fdf03a..d0a2993ff 100644
--- a/src/lib.cairo
+++ b/src/lib.cairo
@@ -2,6 +2,7 @@ pub use openzeppelin_access as access;
 pub use openzeppelin_account as account;
 pub use openzeppelin_governance as governance;
 pub use openzeppelin_introspection as introspection;
+pub use openzeppelin_merkle_tree as merkle_tree;
 pub use openzeppelin_presets as presets;
 pub use openzeppelin_security as security;
 pub use openzeppelin_token as token;


Test patch:
diff --git a/packages/merkle_tree/src/tests.cairo b/packages/merkle_tree/src/tests.cairo
new file mode 100644
index 000000000..982f48c1e
--- /dev/null
+++ b/packages/merkle_tree/src/tests.cairo
@@ -0,0 +1,2 @@
+mod merkle_proof;
+mod test_hashes;
diff --git a/packages/merkle_tree/src/tests/merkle_proof.cairo b/packages/merkle_tree/src/tests/merkle_proof.cairo
new file mode 100644
index 000000000..c1327c921
--- /dev/null
+++ b/packages/merkle_tree/src/tests/merkle_proof.cairo
@@ -0,0 +1,4 @@
+pub(crate) mod common;
+
+mod test_with_pedersen;
+mod test_with_poseidon;
diff --git a/packages/merkle_tree/src/tests/merkle_proof/common.cairo b/packages/merkle_tree/src/tests/merkle_proof/common.cairo
new file mode 100644
index 000000000..d3dc09939
--- /dev/null
+++ b/packages/merkle_tree/src/tests/merkle_proof/common.cairo
@@ -0,0 +1,36 @@
+use starknet::{ContractAddress, contract_address_const};
+
+#[derive(Serde, Copy, Drop, Hash)]
+pub(crate) struct Leaf {
+    pub address: ContractAddress,
+    pub amount: u128,
+}
+
+pub(crate) fn LEAVES() -> Span<Leaf> {
+    [
+        Leaf {
+            address: contract_address_const::<
+                0x7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc8
+            >(),
+            amount: 0xfc104e31d098d1ab488fc1acaeb0269
+        },
+        Leaf {
+            address: contract_address_const::<
+                0x7ffffffffffffffffffffffffffffffffffffffffffffffffffffc66ca5c000
+            >(),
+            amount: 0xfc104e31d098d1ab488fc1acaeb0269
+        },
+        Leaf {
+            address: contract_address_const::<
+                0x6a1f098854799debccf2d3c4059ff0f02dbfef6673dc1fcbfffffffffffffc8
+            >(),
+            amount: 0xfc104e31d098d1ab488fc1acaeb0269
+        },
+        Leaf {
+            address: contract_address_const::<
+                0xfa6541b7909bfb5e8585f1222fcf272eea352c7e0e8ed38c988bd1e2a85e82
+            >(),
+            amount: 0xaa8565d732c2c9fa5f6c001d89d5c219
+        },
+    ].span()
+}
diff --git a/packages/merkle_tree/src/tests/merkle_proof/test_with_pedersen.cairo b/packages/merkle_tree/src/tests/merkle_proof/test_with_pedersen.cairo
new file mode 100644
index 000000000..11eae6183
--- /dev/null
+++ b/packages/merkle_tree/src/tests/merkle_proof/test_with_pedersen.cairo
@@ -0,0 +1,198 @@
+use core::hash::{HashStateTrait, HashStateExTrait};
+use core::pedersen::{PedersenTrait, pedersen};
+use openzeppelin_merkle_tree::hashes::PedersenCHasher;
+use openzeppelin_merkle_tree::merkle_proof::{
+    process_proof, process_multi_proof, verify, verify_multi_proof, verify_pedersen
+};
+use starknet::{ContractAddress, contract_address_const};
+use super::common::{Leaf, LEAVES};
+
+// `ROOT`, `PROOF`, and `MULTI_PROOF` were computed using @ericnordelo/strk-merkle-tree
+const ROOT: felt252 = 0x02a40717603180fa52f40a55508cd360d301840f3e502665cf0132ef412911de;
+const PROOF: [
+    felt252
+    ; 2] = [
+    0x044fdc540a81d0189ed30b49d64136f9e8bd499c942ba170404ef0b9406e524c,
+    0x02b0ee474cf2ab27501e54a661d17ac1dc162571c111fe2455d09fe23471099e
+];
+const MULTI_PROOF: [
+    felt252
+    ; 2] = [
+    0x044fdc540a81d0189ed30b49d64136f9e8bd499c942ba170404ef0b9406e524c,
+    0x05fb6a626bb2c1e12fc2d6fa7f218ec06928ba5febf4d5677c2c5060827e383b
+];
+
+//
+// verify
+//
+
+#[test]
+fn test_valid_merkle_proof() {
+    let leaves = LEAVES();
+    let hash = leaf_hash(*leaves.at(0));
+    let proof = PROOF.span();
+
+    assert_eq!(process_proof::<PedersenCHasher>(proof, hash), ROOT);
+    assert!(verify::<PedersenCHasher>(proof, ROOT, hash));
+    assert!(verify_pedersen(proof, ROOT, hash));
+
+    // For demonstration, it is also possible to create valid
+    // proofs for certain values *NOT* in elements:
+    let no_such_leaf = PedersenCHasher::commutative_hash(hash, *proof.at(0));
+    let second_proof = [0x02b0ee474cf2ab27501e54a661d17ac1dc162571c111fe2455d09fe23471099e].span();
+
+    assert_eq!(process_proof::<PedersenCHasher>(second_proof, no_such_leaf), ROOT);
+    assert!(verify::<PedersenCHasher>(second_proof, ROOT, no_such_leaf));
+    assert!(verify_pedersen(second_proof, ROOT, no_such_leaf));
+}
+
+#[test]
+fn test_invalid_merkle_proof() {
+    let leaves = LEAVES();
+    let hash = leaf_hash(*leaves.at(0));
+    let invalid_proof = [
+        0x044fdc540a81d0189ed30b49d64136f9e8bd499c942ba170404ef0b9406e524c, 'invalid'
+    ].span();
+
+    assert!(process_proof::<PedersenCHasher>(invalid_proof, hash) != ROOT);
+    assert!(!verify::<PedersenCHasher>(invalid_proof, ROOT, hash));
+    assert!(!verify_pedersen(invalid_proof, ROOT, hash));
+}
+
+//
+// multi_proof_verify
+//
+
+#[test]
+fn test_valid_merkle_multi_proof() {
+    let leaves = LEAVES();
+    let leaves_to_prove = [leaf_hash(*leaves.at(0)), leaf_hash(*leaves.at(1))].span();
+    let proof = MULTI_PROOF.span();
+    let proof_flags = [false, false, true].span();
+
+    assert_eq!(process_multi_proof::<PedersenCHasher>(proof, proof_flags, leaves_to_prove), ROOT);
+    assert!(verify_multi_proof::<PedersenCHasher>(proof, proof_flags, ROOT, leaves_to_prove));
+}
+
+#[test]
+fn test_invalid_merkle_multi_proof() {
+    let leaves = LEAVES();
+    let leaves_to_prove = [leaf_hash(*leaves.at(0)), leaf_hash(*leaves.at(1))].span();
+    let invalid_proof = [
+        0x044fdc540a81d0189ed30b49d64136f9e8bd499c942ba170404ef0b9406e524c, 'invalid'
+    ].span();
+    let proof_flags = [false, false, true].span();
+
+    assert!(
+        process_multi_proof::<PedersenCHasher>(invalid_proof, proof_flags, leaves_to_prove) != ROOT
+    );
+    assert!(
+        !verify_multi_proof::<PedersenCHasher>(invalid_proof, proof_flags, ROOT, leaves_to_prove)
+    );
+}
+
+#[test]
+fn test_invalid_merkle_multi_proof_flags() {
+    let leaves = LEAVES();
+    let leaves_to_prove = [leaf_hash(*leaves.at(0)), leaf_hash(*leaves.at(1))].span();
+    let proof = MULTI_PROOF.span();
+    let proof_flags = [false, true, false].span();
+
+    assert!(process_multi_proof::<PedersenCHasher>(proof, proof_flags, leaves_to_prove) != ROOT);
+    assert!(!verify_multi_proof::<PedersenCHasher>(proof, proof_flags, ROOT, leaves_to_prove));
+}
+
+#[test]
+#[should_panic(expected: ("MerkleProof: invalid multi proof",))]
+fn test_process_multi_proof_invalid_len_proof_flags_panics() {
+    let leaves = LEAVES();
+    let leaves_to_prove = [leaf_hash(*leaves.at(0)), leaf_hash(*leaves.at(1))].span();
+    let proof = MULTI_PROOF.span();
+
+    // `proof_flags.len()` is not equal to `proof.len() + leaves_to_prove.len() + 1`
+    let proof_flags = [true, false].span();
+
+    process_multi_proof::<PedersenCHasher>(proof, proof_flags, leaves_to_prove);
+}
+
+#[test]
+#[should_panic(expected: ("MerkleProof: invalid multi proof",))]
+fn test_verify_multi_proof_invalid_len_proof_flags_panics() {
+    let leaves = LEAVES();
+    let leaves_to_prove = [leaf_hash(*leaves.at(0)), leaf_hash(*leaves.at(1))].span();
+    let proof = MULTI_PROOF.span();
+
+    // `proof_flags.len()` is not equal to `proof.len() + leaves_to_prove.len() + 1`
+    let proof_flags = [true, false].span();
+
+    verify_multi_proof::<PedersenCHasher>(proof, proof_flags, ROOT, leaves_to_prove);
+}
+
+#[test]
+#[should_panic(expected: ('Index out of bounds',))]
+fn test_process_multi_proof_flags_extra_leaves_expected() {
+    let leaves = LEAVES();
+    let leaves_to_prove = [
+        leaf_hash(*leaves.at(0)), leaf_hash(*leaves.at(1)), leaf_hash(*leaves.at(2))
+    ].span();
+    let proof = MULTI_PROOF.span();
+
+    // For each true one leaf is expected
+    let proof_flags = [true, true, true, true].span();
+
+    process_multi_proof::<PedersenCHasher>(proof, proof_flags, leaves_to_prove);
+}
+
+#[test]
+#[should_panic(expected: ('Index out of bounds',))]
+fn test_process_multi_proof_flags_extra_proofs_expected() {
+    let leaves = LEAVES();
+    let leaves_to_prove = [
+        leaf_hash(*leaves.at(0)), leaf_hash(*leaves.at(1)), leaf_hash(*leaves.at(2))
+    ].span();
+    let proof = MULTI_PROOF.span();
+
+    // For each false one proof is expected
+    let proof_flags = [true, false, false, false].span();
+
+    process_multi_proof::<PedersenCHasher>(proof, proof_flags, leaves_to_prove);
+}
+
+#[test]
+#[should_panic(expected: ('Index out of bounds',))]
+fn test_verify_multi_proof_flags_extra_leaves_expected() {
+    let leaves = LEAVES();
+    let leaves_to_prove = [
+        leaf_hash(*leaves.at(0)), leaf_hash(*leaves.at(1)), leaf_hash(*leaves.at(2))
+    ].span();
+    let proof = MULTI_PROOF.span();
+
+    // For each true one leaf is expected
+    let proof_flags = [true, true, true, true].span();
+
+    verify_multi_proof::<PedersenCHasher>(proof, proof_flags, ROOT, leaves_to_prove);
+}
+
+#[test]
+#[should_panic(expected: ('Index out of bounds',))]
+fn test_verify_multi_proof_flags_extra_proofs_expected() {
+    let leaves = LEAVES();
+    let leaves_to_prove = [
+        leaf_hash(*leaves.at(0)), leaf_hash(*leaves.at(1)), leaf_hash(*leaves.at(2))
+    ].span();
+    let proof = MULTI_PROOF.span();
+
+    // For each false one proof is expected
+    let proof_flags = [true, false, false, false].span();
+
+    verify_multi_proof::<PedersenCHasher>(proof, proof_flags, ROOT, leaves_to_prove);
+}
+
+//
+// Helpers
+//
+
+fn leaf_hash(leaf: Leaf) -> felt252 {
+    let hash_state = PedersenTrait::new(0);
+    pedersen(0, hash_state.update_with(leaf).update(2).finalize())
+}
diff --git a/packages/merkle_tree/src/tests/merkle_proof/test_with_poseidon.cairo b/packages/merkle_tree/src/tests/merkle_proof/test_with_poseidon.cairo
new file mode 100644
index 000000000..00938ede1
--- /dev/null
+++ b/packages/merkle_tree/src/tests/merkle_proof/test_with_poseidon.cairo
@@ -0,0 +1,198 @@
+use core::poseidon::poseidon_hash_span;
+use openzeppelin_merkle_tree::hashes::PoseidonCHasher;
+use openzeppelin_merkle_tree::merkle_proof::{
+    process_proof, process_multi_proof, verify, verify_multi_proof, verify_poseidon
+};
+use starknet::{ContractAddress, contract_address_const};
+use super::common::{Leaf, LEAVES};
+
+// `ROOT`, `PROOF`, and `MULTI_PROOF` were computed using @ericnordelo/strk-merkle-tree
+const ROOT: felt252 = 0x013f43fdca44b32f5334414b385b46aa1016d0172a1f066eab4cc93636426fcc;
+const PROOF: [
+    felt252
+    ; 2] = [
+    0x05b151ebb9201ce27c56a70f5d0571ccfb9d9d62f12b8ccab7801ba87ec21a2f,
+    0x2b7d689bd2ff488fd06dfb8eb22f5cdaba1e5d9698d3fabff2f1801852dbb2
+];
+const MULTI_PROOF: [
+    felt252
+    ; 2] = [
+    0x044fdc540a81d0189ed30b49d64136f9e8bd499c942ba170404ef0b9406e524c,
+    0x05fb6a626bb2c1e12fc2d6fa7f218ec06928ba5febf4d5677c2c5060827e383b
+];
+
+//
+// verify
+//
+
+#[test]
+fn test_valid_merkle_proof() {
+    let leaves = LEAVES();
+    let hash = leaf_hash(*leaves.at(0));
+    let proof = PROOF.span();
+
+    assert_eq!(process_proof::<PoseidonCHasher>(proof, hash), ROOT);
+    assert!(verify::<PoseidonCHasher>(proof, ROOT, hash));
+    assert!(verify_poseidon(proof, ROOT, hash));
+
+    // For demonstration, it is also possible to create valid
+    // proofs for certain values *NOT* in elements:
+    let no_such_leaf = PoseidonCHasher::commutative_hash(hash, *proof.at(0));
+    let second_proof = [0x2b7d689bd2ff488fd06dfb8eb22f5cdaba1e5d9698d3fabff2f1801852dbb2].span();
+
+    assert_eq!(process_proof::<PoseidonCHasher>(second_proof, no_such_leaf), ROOT);
+    assert!(verify::<PoseidonCHasher>(second_proof, ROOT, no_such_leaf));
+    assert!(verify_poseidon(second_proof, ROOT, no_such_leaf));
+}
+
+#[test]
+fn test_invalid_merkle_proof() {
+    let leaves = LEAVES();
+    let hash = leaf_hash(*leaves.at(0));
+    let invalid_proof = [
+        0x044fdc540a81d0189ed30b49d64136f9e8bd499c942ba170404ef0b9406e524c, 'invalid'
+    ].span();
+
+    assert!(process_proof::<PoseidonCHasher>(invalid_proof, hash) != ROOT);
+    assert!(!verify::<PoseidonCHasher>(invalid_proof, ROOT, hash));
+    assert!(!verify_poseidon(invalid_proof, ROOT, hash));
+}
+
+//
+// multi_proof_verify
+//
+
+#[test]
+fn test_valid_merkle_multi_proof() {
+    let leaves = LEAVES();
+    let leaves_to_prove = [leaf_hash(*leaves.at(0)), leaf_hash(*leaves.at(1))].span();
+    let proof = [0x2b7d689bd2ff488fd06dfb8eb22f5cdaba1e5d9698d3fabff2f1801852dbb2].span();
+    let proof_flags = [true, false].span();
+
+    assert_eq!(process_multi_proof::<PoseidonCHasher>(proof, proof_flags, leaves_to_prove), ROOT);
+    assert!(verify_multi_proof::<PoseidonCHasher>(proof, proof_flags, ROOT, leaves_to_prove));
+}
+
+#[test]
+fn test_invalid_merkle_multi_proof() {
+    let leaves = LEAVES();
+    let leaves_to_prove = [leaf_hash(*leaves.at(0)), leaf_hash(*leaves.at(1))].span();
+    let invalid_proof = [
+        0x044fdc540a81d0189ed30b49d64136f9e8bd499c942ba170404ef0b9406e524c, 'invalid'
+    ].span();
+    let proof_flags = [false, false, true].span();
+
+    assert!(
+        process_multi_proof::<PoseidonCHasher>(invalid_proof, proof_flags, leaves_to_prove) != ROOT
+    );
+    assert!(
+        !verify_multi_proof::<PoseidonCHasher>(invalid_proof, proof_flags, ROOT, leaves_to_prove)
+    );
+}
+
+#[test]
+fn test_invalid_merkle_multi_proof_flags() {
+    let leaves = LEAVES();
+    let leaves_to_prove = [leaf_hash(*leaves.at(0)), leaf_hash(*leaves.at(1))].span();
+    let proof = MULTI_PROOF.span();
+    let proof_flags = [false, true, false].span();
+
+    assert!(process_multi_proof::<PoseidonCHasher>(proof, proof_flags, leaves_to_prove) != ROOT);
+    assert!(!verify_multi_proof::<PoseidonCHasher>(proof, proof_flags, ROOT, leaves_to_prove));
+}
+
+#[test]
+#[should_panic(expected: ("MerkleProof: invalid multi proof",))]
+fn test_process_multi_proof_invalid_len_proof_flags_panics() {
+    let leaves = LEAVES();
+    let leaves_to_prove = [leaf_hash(*leaves.at(0)), leaf_hash(*leaves.at(1))].span();
+    let proof = MULTI_PROOF.span();
+
+    // `proof_flags.len()` is not equal to `proof.len() + leaves_to_prove.len() + 1`
+    let proof_flags = [true, false].span();
+
+    process_multi_proof::<PoseidonCHasher>(proof, proof_flags, leaves_to_prove);
+}
+
+#[test]
+#[should_panic(expected: ("MerkleProof: invalid multi proof",))]
+fn test_verify_multi_proof_invalid_len_proof_flags_panics() {
+    let leaves = LEAVES();
+    let leaves_to_prove = [leaf_hash(*leaves.at(0)), leaf_hash(*leaves.at(1))].span();
+    let proof = MULTI_PROOF.span();
+
+    // `proof_flags.len()` is not equal to `proof.len() + leaves_to_prove.len() + 1`
+    let proof_flags = [true, false].span();
+
+    verify_multi_proof::<PoseidonCHasher>(proof, proof_flags, ROOT, leaves_to_prove);
+}
+
+#[test]
+#[should_panic(expected: ('Index out of bounds',))]
+fn test_process_multi_proof_flags_extra_leaves_expected() {
+    let leaves = LEAVES();
+    let leaves_to_prove = [
+        leaf_hash(*leaves.at(0)), leaf_hash(*leaves.at(1)), leaf_hash(*leaves.at(2))
+    ].span();
+    let proof = MULTI_PROOF.span();
+
+    // For each true one leaf is expected
+    let proof_flags = [true, true, true, true].span();
+
+    process_multi_proof::<PoseidonCHasher>(proof, proof_flags, leaves_to_prove);
+}
+
+#[test]
+#[should_panic(expected: ('Index out of bounds',))]
+fn test_process_multi_proof_flags_extra_proofs_expected() {
+    let leaves = LEAVES();
+    let leaves_to_prove = [
+        leaf_hash(*leaves.at(0)), leaf_hash(*leaves.at(1)), leaf_hash(*leaves.at(2))
+    ].span();
+    let proof = MULTI_PROOF.span();
+
+    // For each false one proof is expected
+    let proof_flags = [true, false, false, false].span();
+
+    process_multi_proof::<PoseidonCHasher>(proof, proof_flags, leaves_to_prove);
+}
+
+#[test]
+#[should_panic(expected: ('Index out of bounds',))]
+fn test_verify_multi_proof_flags_extra_leaves_expected() {
+    let leaves = LEAVES();
+    let leaves_to_prove = [
+        leaf_hash(*leaves.at(0)), leaf_hash(*leaves.at(1)), leaf_hash(*leaves.at(2))
+    ].span();
+    let proof = MULTI_PROOF.span();
+
+    // For each true one leaf is expected
+    let proof_flags = [true, true, true, true].span();
+
+    verify_multi_proof::<PoseidonCHasher>(proof, proof_flags, ROOT, leaves_to_prove);
+}
+
+#[test]
+#[should_panic(expected: ('Index out of bounds',))]
+fn test_verify_multi_proof_flags_extra_proofs_expected() {
+    let leaves = LEAVES();
+    let leaves_to_prove = [
+        leaf_hash(*leaves.at(0)), leaf_hash(*leaves.at(1)), leaf_hash(*leaves.at(2))
+    ].span();
+    let proof = MULTI_PROOF.span();
+
+    // For each false one proof is expected
+    let proof_flags = [true, false, false, false].span();
+
+    verify_multi_proof::<PoseidonCHasher>(proof, proof_flags, ROOT, leaves_to_prove);
+}
+
+//
+// Helpers
+//
+
+fn leaf_hash(leaf: Leaf) -> felt252 {
+    poseidon_hash_span(
+        [poseidon_hash_span([leaf.address.into(), leaf.amount.into()].span())].span()
+    )
+}
diff --git a/packages/merkle_tree/src/tests/test_hashes.cairo b/packages/merkle_tree/src/tests/test_hashes.cairo
new file mode 100644
index 000000000..ebe43866e
--- /dev/null
+++ b/packages/merkle_tree/src/tests/test_hashes.cairo
@@ -0,0 +1,42 @@
+use core::hash::HashStateTrait;
+use core::pedersen::PedersenTrait;
+use core::poseidon::poseidon_hash_span;
+use openzeppelin_merkle_tree::hashes::{PedersenCHasher, PoseidonCHasher};
+
+#[test]
+fn test_pedersen_commutative_hash_is_commutative() {
+    let a = 'a';
+    let b = 'b';
+    let hash = PedersenCHasher::commutative_hash(a, b);
+    assert_eq!(hash, PedersenCHasher::commutative_hash(b, a));
+}
+
+#[test]
+fn test_pedersen_commutative_hash_smaller_first() {
+    let a = 'a';
+    let b = 'b';
+
+    let hash_state = PedersenTrait::new(0);
+    let expected = hash_state.update(a).update(b).update(2).finalize();
+
+    let hash = PedersenCHasher::commutative_hash(b, a);
+    assert_eq!(hash, expected);
+}
+
+#[test]
+fn test_poseidon_commutative_hash_is_commutative() {
+    let a = 'a';
+    let b = 'b';
+    let hash = PoseidonCHasher::commutative_hash(a, b);
+    assert_eq!(hash, PoseidonCHasher::commutative_hash(b, a));
+}
+
+
+#[test]
+fn test_poseidon_commutative_hash_smaller_first() {
+    let a = 'a';
+    let b = 'b';
+
+    let hash = PoseidonCHasher::commutative_hash(b, a);
+    assert_eq!(hash, poseidon_hash_span([a, b].span()));
+}