Struct Verifier

pub struct Verifier<B = KeccakBuilder>(/* private fields */)
where
    B: BuildHasher;

Verify merkle proofs.

Implementations

impl Verifier<KeccakBuilder>

pub fn verify(proof: &[[u8; 32]], root: [u8; 32], leaf: [u8; 32]) -> bool

Verify that leaf is part of a Merkle tree defined by root by using proof and the default keccak256 hashing algorithm.

A new root is rebuilt by traversing up the Merkle tree. The proof provided must contain sibling hashes on the branch starting from the leaf to the root of the tree. Each pair of leaves and each pair of pre-images are assumed to be sorted.

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

Arguments

• proof - A slice of hashes that constitute the merkle proof.
• root - The root of the merkle tree, in bytes.
• leaf - The leaf of the merkle tree to proof, in bytes.

Examples

use openzeppelin_crypto::merkle::Verifier;
use hex_literal::hex;

let root  = hex!("0000000000000000000000000000000000000000000000000000000000000000");
let leaf  = hex!("0000000000000000000000000000000000000000000000000000000000000000");
let proof = hex!("0000000000000000000000000000000000000000000000000000000000000000");

let verification = Verifier::verify(&[proof], root, leaf);
assert!(!verification);

pub fn verify_multi_proof( proof: &[[u8; 32]], proof_flags: &[bool], root: [u8; 32], leaves: &[[u8; 32]], ) -> Result<bool, MultiProofError>

Verify multiple leaves can be simultaneously proven to be a part of a Merkle tree defined by root by using a proof with proof_flags and a hasher.

The proof must contain the sibling hashes one would need to rebuild the root starting from leaves. proof_flags represents whether a hash must be computed using a proof member. A new root is rebuilt by starting from the leaves and traversing up the Merkle tree.

The procedure incrementally reconstructs all inner nodes by combining a leaf/inner node with either another leaf/inner node or a proof sibling node, depending on each proof flag being true or false respectively, i.e., the i-th hash must be computed using the proof if proof_flags[i] == false.

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

• The tree is complete (but not necessarily perfect).
• The leaves to be proven are in the opposite order they appear in the tree (i.e., as seen from right to left starting at the deepest layer and continuing at the next layer).

NOTE: This implementation is not equivalent to it’s Solidity counterpart. In Rust, access to uninitialized memory panics, which means we don’t need to check that the whole proof array has been processed. Both implementations will revert for the same inputs, but for different reasons. See https://github.com/OpenZeppelin/openzeppelin-contracts/security/advisories/GHSA-wprv-93r4-jj2p

Arguments

• proof - A slice of hashes that constitute the merkle proof.
• proof_flags - A slice of booleans that determine whether to hash leaves or the proof.
• root - The root of the merkle tree, in bytes.
• leaves - A slice of hashes that constitute the leaves of the merkle tree to be proven, each leaf in bytes.

Errors

• MultiProofError - If the arguments are well-formed, but invalid.

Panics

• Will panic with an out-of-bounds error if the proof is malicious. See https://github.com/OpenZeppelin/openzeppelin-contracts/security/advisories/GHSA-wprv-93r4-jj2p

Examples

use openzeppelin_crypto::merkle::Verifier;
use hex_literal::hex;

let root   =  hex!("6deb52b5da8fd108f79fab00341f38d2587896634c646ee52e49f845680a70c8");
let leaves = [hex!("19ba6c6333e0e9a15bf67523e0676e2f23eb8e574092552d5e888c64a4bb3681"),
              hex!("c62a8cfa41edc0ef6f6ae27a2985b7d39c7fea770787d7e104696c6e81f64848"),
              hex!("eba909cf4bb90c6922771d7f126ad0fd11dfde93f3937a196274e1ac20fd2f5b")];
let proof  = [hex!("9a4f64e953595df82d1b4f570d34c4f4f0cfaf729a61e9d60e83e579e1aa283e"),
              hex!("8076923e76cf01a7c048400a2304c9a9c23bbbdac3a98ea3946340fdafbba34f")];

let proof_flags = [false, true, false, true];

let verification =
    Verifier::verify_multi_proof(&proof, &proof_flags, root, &leaves);
assert!(verification.unwrap());

impl<B> Verifier<B>

where B: BuildHasher, B::Hasher: Hasher<Output = [u8; 32]>,

pub fn verify_with_builder( proof: &[[u8; 32]], root: [u8; 32], leaf: [u8; 32], builder: &B, ) -> bool

Verify that leaf is part of a Merkle tree defined by root by using proof and a custom hashing algorithm defined by builder. See BuildHasher for more information on how to construct a builder.

WARNING: This is a lower-level function. For most use cases, Verifier::verify, which uses keccak256 as a hashing algorithm, should be enough. Using other hashing algorithm may have unexpected results.

Arguments

• proof - A slice of hashes that constitute the merkle proof.
• root - The root of the merkle tree, in bytes.
• leaf - The leaf of the merkle tree to proof, in bytes.
• builder - A BuildHasher that represents a hashing algorithm.

Examples

use openzeppelin_crypto::{merkle::Verifier, KeccakBuilder};
use hex_literal::hex;

let root  = hex!("0000000000000000000000000000000000000000000000000000000000000000");
let leaf  = hex!("0000000000000000000000000000000000000000000000000000000000000000");
let proof = hex!("0000000000000000000000000000000000000000000000000000000000000000");

let verification = Verifier::verify_with_builder(&[proof], root, leaf, &KeccakBuilder);
assert!(!verification);

pub fn verify_multi_proof_with_builder( proof: &[[u8; 32]], proof_flags: &[bool], root: [u8; 32], leaves: &[[u8; 32]], builder: &B, ) -> Result<bool, MultiProofError>

Verify multiple leaves can be simultaneously proven to be a part of a Merkle tree defined by root by using a proof with proof_flags and a custom hashing algorithm defined by builder. See BuildHasher for more information on how to construct a builder.

WARNING: This is a lower-level function. For most use cases, Verifier::verify_multi_proof, which uses keccak256 as a hashing algorithm, should be enough. Using other hashing algorithm may have unexpected results.

The proof must contain the sibling hashes one would need to rebuild the root starting from leaves. proof_flags represents whether a hash must be computed using a proof member. A new root is rebuilt by starting from the leaves and traversing up the Merkle tree.

The procedure incrementally reconstructs all inner nodes by combining a leaf/inner node with either another leaf/inner node or a proof sibling node, depending on each proof flag being true or false respectively, i.e., the i-th hash must be computed using the proof if proof_flags[i] == false.

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

• The tree is complete (but not necessarily perfect).
• The leaves to be proven are in the opposite order they appear in the tree (i.e., as seen from right to left starting at the deepest layer and continuing at the next layer).

NOTE: This implementation is not equivalent to it’s Solidity counterpart. In Rust, access to uninitialized memory panics, which means we don’t need to check that the whole proof array has been processed. Both implementations will revert for the same inputs, but for different reasons. See https://github.com/OpenZeppelin/openzeppelin-contracts/security/advisories/GHSA-wprv-93r4-jj2p

Arguments

• proof - A slice of hashes that constitute the merkle proof.
• proof_flags - A slice of booleans that determine whether to hash leaves or the proof.
• root - The root of the merkle tree, in bytes.
• leaves - A slice of hashes that constitute the leaves of the merkle tree to be proven, each leaf in bytes.
• builder - A BuildHasher that represents a hashing algorithm.

Errors

• MultiProofError - If the arguments are well-formed, but invalid.

Examples

use openzeppelin_crypto::{merkle::Verifier, KeccakBuilder};
use hex_literal::hex;

let root   =  hex!("6deb52b5da8fd108f79fab00341f38d2587896634c646ee52e49f845680a70c8");
let leaves = [hex!("19ba6c6333e0e9a15bf67523e0676e2f23eb8e574092552d5e888c64a4bb3681"),
              hex!("c62a8cfa41edc0ef6f6ae27a2985b7d39c7fea770787d7e104696c6e81f64848"),
              hex!("eba909cf4bb90c6922771d7f126ad0fd11dfde93f3937a196274e1ac20fd2f5b")];
let proof  = [hex!("9a4f64e953595df82d1b4f570d34c4f4f0cfaf729a61e9d60e83e579e1aa283e"),
              hex!("8076923e76cf01a7c048400a2304c9a9c23bbbdac3a98ea3946340fdafbba34f")];
let proof_flags = [false, true, false, true];

let verification =
    Verifier::verify_multi_proof_with_builder(&proof, &proof_flags, root, &leaves, &KeccakBuilder);
assert!(verification.unwrap());