Prove Merkle Tree Membership

Let's walk through an example of a merkle membership proof in Noir that proves that a given leaf is in a merkle tree.

use dep::std;

fn main(message : [Field; 62], index : Field, hashpath : [Field; 40], root : Field) {
    let leaf = std::hash::hash_to_field(message.as_slice());
    let merkle_root = std::merkle::compute_merkle_root(leaf, index, hashpath);
    assert(merkle_root == root);
}

The message is hashed using hash_to_field. The specific hash function that is being used is chosen by the backend. The only requirement is that this hash function can heuristically be used as a random oracle. If only collision resistance is needed, then one can call std::hash::pedersen_hash instead.

let leaf = std::hash::hash_to_field(message.as_slice());

The leaf is then passed to a compute_merkle_root function with the root, index and hashpath. The returned root can then be asserted to be the same as the provided root.

let merkle_root = std::merkle::compute_merkle_root(leaf, index, hashpath);
assert (merkle_root == root);

Note: It is possible to re-implement the merkle tree implementation without standard library. However, for most usecases, it is enough. In general, the standard library will always opt to be as conservative as possible, while striking a balance with efficiency.

An example, the merkle membership proof, only requires a hash function that has collision resistance, hence a hash function like Pedersen is allowed, which in most cases is more efficient than the even more conservative sha256.

View an example on the starter repo