MerkleProof.sol 9.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227
  1. // SPDX-License-Identifier: MIT
  2. // OpenZeppelin Contracts (last updated v4.9.2) (utils/cryptography/MerkleProof.sol)
  3. pragma solidity ^0.8.0;
  4. /**
  5. * @dev These functions deal with verification of Merkle Tree proofs.
  6. *
  7. * The tree and the proofs can be generated using our
  8. * https://github.com/OpenZeppelin/merkle-tree[JavaScript library].
  9. * You will find a quickstart guide in the readme.
  10. *
  11. * WARNING: You should avoid using leaf values that are 64 bytes long prior to
  12. * hashing, or use a hash function other than keccak256 for hashing leaves.
  13. * This is because the concatenation of a sorted pair of internal nodes in
  14. * the merkle tree could be reinterpreted as a leaf value.
  15. * OpenZeppelin's JavaScript library generates merkle trees that are safe
  16. * against this attack out of the box.
  17. */
  18. library MerkleProof {
  19. /**
  20. * @dev Returns true if a `leaf` can be proved to be a part of a Merkle tree
  21. * defined by `root`. For this, a `proof` must be provided, containing
  22. * sibling hashes on the branch from the leaf to the root of the tree. Each
  23. * pair of leaves and each pair of pre-images are assumed to be sorted.
  24. */
  25. function verify(bytes32[] memory proof, bytes32 root, bytes32 leaf) internal pure returns (bool) {
  26. return processProof(proof, leaf) == root;
  27. }
  28. /**
  29. * @dev Calldata version of {verify}
  30. *
  31. * _Available since v4.7._
  32. */
  33. function verifyCalldata(bytes32[] calldata proof, bytes32 root, bytes32 leaf) internal pure returns (bool) {
  34. return processProofCalldata(proof, leaf) == root;
  35. }
  36. /**
  37. * @dev Returns the rebuilt hash obtained by traversing a Merkle tree up
  38. * from `leaf` using `proof`. A `proof` is valid if and only if the rebuilt
  39. * hash matches the root of the tree. When processing the proof, the pairs
  40. * of leafs & pre-images are assumed to be sorted.
  41. *
  42. * _Available since v4.4._
  43. */
  44. function processProof(bytes32[] memory proof, bytes32 leaf) internal pure returns (bytes32) {
  45. bytes32 computedHash = leaf;
  46. for (uint256 i = 0; i < proof.length; i++) {
  47. computedHash = _hashPair(computedHash, proof[i]);
  48. }
  49. return computedHash;
  50. }
  51. /**
  52. * @dev Calldata version of {processProof}
  53. *
  54. * _Available since v4.7._
  55. */
  56. function processProofCalldata(bytes32[] calldata proof, bytes32 leaf) internal pure returns (bytes32) {
  57. bytes32 computedHash = leaf;
  58. for (uint256 i = 0; i < proof.length; i++) {
  59. computedHash = _hashPair(computedHash, proof[i]);
  60. }
  61. return computedHash;
  62. }
  63. /**
  64. * @dev Returns true if the `leaves` can be simultaneously proven to be a part of a merkle tree defined by
  65. * `root`, according to `proof` and `proofFlags` as described in {processMultiProof}.
  66. *
  67. * CAUTION: Not all merkle trees admit multiproofs. See {processMultiProof} for details.
  68. *
  69. * _Available since v4.7._
  70. */
  71. function multiProofVerify(
  72. bytes32[] memory proof,
  73. bool[] memory proofFlags,
  74. bytes32 root,
  75. bytes32[] memory leaves
  76. ) internal pure returns (bool) {
  77. return processMultiProof(proof, proofFlags, leaves) == root;
  78. }
  79. /**
  80. * @dev Calldata version of {multiProofVerify}
  81. *
  82. * CAUTION: Not all merkle trees admit multiproofs. See {processMultiProof} for details.
  83. *
  84. * _Available since v4.7._
  85. */
  86. function multiProofVerifyCalldata(
  87. bytes32[] calldata proof,
  88. bool[] calldata proofFlags,
  89. bytes32 root,
  90. bytes32[] memory leaves
  91. ) internal pure returns (bool) {
  92. return processMultiProofCalldata(proof, proofFlags, leaves) == root;
  93. }
  94. /**
  95. * @dev Returns the root of a tree reconstructed from `leaves` and sibling nodes in `proof`. The reconstruction
  96. * proceeds by incrementally reconstructing all inner nodes by combining a leaf/inner node with either another
  97. * leaf/inner node or a proof sibling node, depending on whether each `proofFlags` item is true or false
  98. * respectively.
  99. *
  100. * CAUTION: Not all merkle trees admit multiproofs. To use multiproofs, it is sufficient to ensure that: 1) the tree
  101. * is complete (but not necessarily perfect), 2) the leaves to be proven are in the opposite order they are in the
  102. * tree (i.e., as seen from right to left starting at the deepest layer and continuing at the next layer).
  103. *
  104. * _Available since v4.7._
  105. */
  106. function processMultiProof(
  107. bytes32[] memory proof,
  108. bool[] memory proofFlags,
  109. bytes32[] memory leaves
  110. ) internal pure returns (bytes32 merkleRoot) {
  111. // This function rebuilds the root hash by traversing the tree up from the leaves. The root is rebuilt by
  112. // consuming and producing values on a queue. The queue starts with the `leaves` array, then goes onto the
  113. // `hashes` array. At the end of the process, the last hash in the `hashes` array should contain the root of
  114. // the merkle tree.
  115. uint256 leavesLen = leaves.length;
  116. uint256 proofLen = proof.length;
  117. uint256 totalHashes = proofFlags.length;
  118. // Check proof validity.
  119. require(leavesLen + proofLen - 1 == totalHashes, "MerkleProof: invalid multiproof");
  120. // The xxxPos values are "pointers" to the next value to consume in each array. All accesses are done using
  121. // `xxx[xxxPos++]`, which return the current value and increment the pointer, thus mimicking a queue's "pop".
  122. bytes32[] memory hashes = new bytes32[](totalHashes);
  123. uint256 leafPos = 0;
  124. uint256 hashPos = 0;
  125. uint256 proofPos = 0;
  126. // At each step, we compute the next hash using two values:
  127. // - a value from the "main queue". If not all leaves have been consumed, we get the next leaf, otherwise we
  128. // get the next hash.
  129. // - depending on the flag, either another value from the "main queue" (merging branches) or an element from the
  130. // `proof` array.
  131. for (uint256 i = 0; i < totalHashes; i++) {
  132. bytes32 a = leafPos < leavesLen ? leaves[leafPos++] : hashes[hashPos++];
  133. bytes32 b = proofFlags[i]
  134. ? (leafPos < leavesLen ? leaves[leafPos++] : hashes[hashPos++])
  135. : proof[proofPos++];
  136. hashes[i] = _hashPair(a, b);
  137. }
  138. if (totalHashes > 0) {
  139. require(proofPos == proofLen, "MerkleProof: invalid multiproof");
  140. unchecked {
  141. return hashes[totalHashes - 1];
  142. }
  143. } else if (leavesLen > 0) {
  144. return leaves[0];
  145. } else {
  146. return proof[0];
  147. }
  148. }
  149. /**
  150. * @dev Calldata version of {processMultiProof}.
  151. *
  152. * CAUTION: Not all merkle trees admit multiproofs. See {processMultiProof} for details.
  153. *
  154. * _Available since v4.7._
  155. */
  156. function processMultiProofCalldata(
  157. bytes32[] calldata proof,
  158. bool[] calldata proofFlags,
  159. bytes32[] memory leaves
  160. ) internal pure returns (bytes32 merkleRoot) {
  161. // This function rebuilds the root hash by traversing the tree up from the leaves. The root is rebuilt by
  162. // consuming and producing values on a queue. The queue starts with the `leaves` array, then goes onto the
  163. // `hashes` array. At the end of the process, the last hash in the `hashes` array should contain the root of
  164. // the merkle tree.
  165. uint256 leavesLen = leaves.length;
  166. uint256 proofLen = proof.length;
  167. uint256 totalHashes = proofFlags.length;
  168. // Check proof validity.
  169. require(leavesLen + proofLen - 1 == totalHashes, "MerkleProof: invalid multiproof");
  170. // The xxxPos values are "pointers" to the next value to consume in each array. All accesses are done using
  171. // `xxx[xxxPos++]`, which return the current value and increment the pointer, thus mimicking a queue's "pop".
  172. bytes32[] memory hashes = new bytes32[](totalHashes);
  173. uint256 leafPos = 0;
  174. uint256 hashPos = 0;
  175. uint256 proofPos = 0;
  176. // At each step, we compute the next hash using two values:
  177. // - a value from the "main queue". If not all leaves have been consumed, we get the next leaf, otherwise we
  178. // get the next hash.
  179. // - depending on the flag, either another value from the "main queue" (merging branches) or an element from the
  180. // `proof` array.
  181. for (uint256 i = 0; i < totalHashes; i++) {
  182. bytes32 a = leafPos < leavesLen ? leaves[leafPos++] : hashes[hashPos++];
  183. bytes32 b = proofFlags[i]
  184. ? (leafPos < leavesLen ? leaves[leafPos++] : hashes[hashPos++])
  185. : proof[proofPos++];
  186. hashes[i] = _hashPair(a, b);
  187. }
  188. if (totalHashes > 0) {
  189. require(proofPos == proofLen, "MerkleProof: invalid multiproof");
  190. unchecked {
  191. return hashes[totalHashes - 1];
  192. }
  193. } else if (leavesLen > 0) {
  194. return leaves[0];
  195. } else {
  196. return proof[0];
  197. }
  198. }
  199. function _hashPair(bytes32 a, bytes32 b) private pure returns (bytes32) {
  200. return a < b ? _efficientHash(a, b) : _efficientHash(b, a);
  201. }
  202. function _efficientHash(bytes32 a, bytes32 b) private pure returns (bytes32 value) {
  203. /// @solidity memory-safe-assembly
  204. assembly {
  205. mstore(0x00, a)
  206. mstore(0x20, b)
  207. value := keccak256(0x00, 0x40)
  208. }
  209. }
  210. }