-
Notifications
You must be signed in to change notification settings - Fork 11.8k
/
MerkleProof.sol
43 lines (38 loc) · 1.55 KB
/
MerkleProof.sol
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
/**
* @dev These functions deal with verification of Merkle Trees proofs.
*
* The proofs can be generated using the JavaScript library
* https://github.com/miguelmota/merkletreejs[merkletreejs].
* Note: the hashing algorithm should be keccak256 and pair sorting should be enabled.
*
* See `test/utils/cryptography/MerkleProof.test.js` for some examples.
*/
library MerkleProof {
/**
* @dev 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.
*/
function verify(
bytes32[] memory proof,
bytes32 root,
bytes32 leaf
) internal pure returns (bool) {
bytes32 computedHash = leaf;
for (uint256 i = 0; i < proof.length; i++) {
bytes32 proofElement = proof[i];
if (computedHash <= proofElement) {
// Hash(current computed hash + current element of the proof)
computedHash = keccak256(abi.encodePacked(computedHash, proofElement));
} else {
// Hash(current element of the proof + current computed hash)
computedHash = keccak256(abi.encodePacked(proofElement, computedHash));
}
}
// Check if the computed hash (root) is equal to the provided root
return computedHash == root;
}
}