// SPDX-License-Identifier: MIT
pragma solidity >=0.8.0;
/// @notice Gas optimized merkle proof verification library.
/// @author Solmate (https://github.com/transmissions11/solmate/blob/main/src/utils/MerkleProofLib.sol)
/// @author Modified from Solady (https://github.com/Vectorized/solady/blob/main/src/utils/MerkleProofLib.sol)
library MerkleProofLib {
function verify(
bytes32[] calldata proof,
bytes32 root,
bytes32 leaf
) internal pure returns (bool isValid) {
assembly {
if proof.length {
// Left shifting by 5 is like multiplying by 32.
let end := add(proof.offset, shl(5, proof.length))
// Initialize offset to the offset of the proof in calldata.
let offset := proof.offset
// Iterate over proof elements to compute root hash.
// prettier-ignore
for {} 1 {} {
// Slot where the leaf should be put in scratch space. If
// leaf > calldataload(offset): slot 32, otherwise: slot 0.
let leafSlot := shl(5, gt(leaf, calldataload(offset)))
// Store elements to hash contiguously in scratch space.
// The xor puts calldataload(offset) in whichever slot leaf
// is not occupying, so 0 if leafSlot is 32, and 32 otherwise.
mstore(leafSlot, leaf)
mstore(xor(leafSlot, 32), calldataload(offset))
// Reuse leaf to store the hash to reduce stack operations.
leaf := keccak256(0, 64) // Hash both slots of scratch space.
offset := add(offset, 32) // Shift 1 word per cycle.
// prettier-ignore
if iszero(lt(offset, end)) { break }
}
}
isValid := eq(leaf, root) // The proof is valid if the roots match.
}
}
}