MerkleProof

These functions deal with verification of Merkle Tree proofs. The tree and the proofs can be generated using our https://github.com/OpenZeppelin/merkle-tree[JavaScript library]. You will find a quickstart guide in the readme. WARNING: You should avoid using leaf values that are 64 bytes long prior to hashing, or use a hash function other than keccak256 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. OpenZeppelin's JavaScript library generates Merkle trees that are safe against this attack out of the box. IMPORTANT: Consider memory side-effects when using custom hashing functions that access memory in an unsafe way. 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.

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. This version handles proofs in memory with the default hashing function.

function verify(bytes32[] memory proof, bytes32 root, bytes32 leaf) internal pure returns (bool);

processProof

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. This version handles proofs in memory with the default hashing function.

function processProof(bytes32[] memory proof, bytes32 leaf) internal pure returns (bytes32);

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. This version handles proofs in memory with a custom hashing function.

function verify(
    bytes32[] memory proof,
    bytes32 root,
    bytes32 leaf,
    function(bytes32, bytes32) view returns (bytes32) hasher
) internal view returns (bool);

processProof

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. This version handles proofs in memory with a custom hashing function.

function processProof(bytes32[] memory proof, bytes32 leaf, function(bytes32, bytes32) view returns (bytes32) hasher)
    internal
    view
    returns (bytes32);

verifyCalldata

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. This version handles proofs in calldata with the default hashing function.

function verifyCalldata(bytes32[] calldata proof, bytes32 root, bytes32 leaf) internal pure returns (bool);

processProofCalldata

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. This version handles proofs in calldata with the default hashing function.

function processProofCalldata(bytes32[] calldata proof, bytes32 leaf) internal pure returns (bytes32);

verifyCalldata

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. This version handles proofs in calldata with a custom hashing function.

function verifyCalldata(
    bytes32[] calldata proof,
    bytes32 root,
    bytes32 leaf,
    function(bytes32, bytes32) view returns (bytes32) hasher
) internal view returns (bool);

processProofCalldata

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. This version handles proofs in calldata with a custom hashing function.

function processProofCalldata(
    bytes32[] calldata proof,
    bytes32 leaf,
    function(bytes32, bytes32) view returns (bytes32) hasher
) internal view returns (bytes32);

multiProofVerify

Returns true if the leaves can be simultaneously proven to be a part of a Merkle tree defined by root, according to proof and proofFlags as described in processMultiProof. This version handles multiproofs in memory with the default hashing function. CAUTION: Not all Merkle trees admit multiproofs. See {processMultiProof} for details. NOTE: Consider the case where root == proof[0] && leaves.length == 0 as it will return true. The leaves must be validated independently. See {processMultiProof}.

function multiProofVerify(bytes32[] memory proof, bool[] memory proofFlags, bytes32 root, bytes32[] memory leaves)
    internal
    pure
    returns (bool);

processMultiProof

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 proofFlags item is true or false respectively. This version handles multiproofs in memory with the default hashing function. 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.length == 1 && leaves.length == 0) is considered a no-op, and therefore a valid multiproof (i.e. it returns proof[0]). Consider disallowing this case if you're not validating the leaves elsewhere.

function processMultiProof(bytes32[] memory proof, bool[] memory proofFlags, bytes32[] memory leaves)
    internal
    pure
    returns (bytes32 merkleRoot);

multiProofVerify

Returns true if the leaves can be simultaneously proven to be a part of a Merkle tree defined by root, according to proof and proofFlags as described in processMultiProof. This version handles multiproofs in memory with a custom hashing function. CAUTION: Not all Merkle trees admit multiproofs. See {processMultiProof} for details. NOTE: Consider the case where root == proof[0] && leaves.length == 0 as it will return true. The leaves must be validated independently. See {processMultiProof}.

function multiProofVerify(
    bytes32[] memory proof,
    bool[] memory proofFlags,
    bytes32 root,
    bytes32[] memory leaves,
    function(bytes32, bytes32) view returns (bytes32) hasher
) internal view returns (bool);

processMultiProof

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 proofFlags item is true or false respectively. This version handles multiproofs in memory with a custom hashing function. 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.length == 1 && leaves.length == 0) is considered a no-op, and therefore a valid multiproof (i.e. it returns proof[0]). Consider disallowing this case if you're not validating the leaves elsewhere.

function processMultiProof(
    bytes32[] memory proof,
    bool[] memory proofFlags,
    bytes32[] memory leaves,
    function(bytes32, bytes32) view returns (bytes32) hasher
) internal view returns (bytes32 merkleRoot);

multiProofVerifyCalldata

Returns true if the leaves can be simultaneously proven to be a part of a Merkle tree defined by root, according to proof and proofFlags as described in processMultiProof. This version handles multiproofs in calldata with the default hashing function. CAUTION: Not all Merkle trees admit multiproofs. See {processMultiProof} for details. NOTE: Consider the case where root == proof[0] && leaves.length == 0 as it will return true. The leaves must be validated independently. See {processMultiProofCalldata}.

function multiProofVerifyCalldata(
    bytes32[] calldata proof,
    bool[] calldata proofFlags,
    bytes32 root,
    bytes32[] memory leaves
) internal pure returns (bool);

processMultiProofCalldata

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 proofFlags item is true or false respectively. This version handles multiproofs in calldata with the default hashing function. 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.length == 1 && leaves.length == 0) is considered a no-op, and therefore a valid multiproof (i.e. it returns proof[0]). Consider disallowing this case if you're not validating the leaves elsewhere.

function processMultiProofCalldata(bytes32[] calldata proof, bool[] calldata proofFlags, bytes32[] memory leaves)
    internal
    pure
    returns (bytes32 merkleRoot);

multiProofVerifyCalldata

Returns true if the leaves can be simultaneously proven to be a part of a Merkle tree defined by root, according to proof and proofFlags as described in processMultiProof. This version handles multiproofs in calldata with a custom hashing function. CAUTION: Not all Merkle trees admit multiproofs. See {processMultiProof} for details. NOTE: Consider the case where root == proof[0] && leaves.length == 0 as it will return true. The leaves must be validated independently. See {processMultiProofCalldata}.

function multiProofVerifyCalldata(
    bytes32[] calldata proof,
    bool[] calldata proofFlags,
    bytes32 root,
    bytes32[] memory leaves,
    function(bytes32, bytes32) view returns (bytes32) hasher
) internal view returns (bool);

processMultiProofCalldata

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 proofFlags item is true or false respectively. This version handles multiproofs in calldata with a custom hashing function. 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.length == 1 && leaves.length == 0) is considered a no-op, and therefore a valid multiproof (i.e. it returns proof[0]). Consider disallowing this case if you're not validating the leaves elsewhere.

function processMultiProofCalldata(
    bytes32[] calldata proof,
    bool[] calldata proofFlags,
    bytes32[] memory leaves,
    function(bytes32, bytes32) view returns (bytes32) hasher
) internal view returns (bytes32 merkleRoot);

Errors

MerkleProofInvalidMultiproof

The multiproof provided is not valid.

error MerkleProofInvalidMultiproof();