library MerkleProof {
  /// @dev Returns true if a `leaf` can be proved to be a part of a Merkle tree defined by `root`.
  function verify(
    bytes32[] memory proof,
    bytes32 root,
    bytes32 leaf
  ) internal pure returns (bool) {
    return processProof(proof, leaf) == root;
  }

  /// @dev Returns the rebuilt hash obtained by traversing a Merklee tree up from `leaf` using `proof`.
  function processProof(bytes32[] memory proof, bytes32 leaf) internal pure returns (bytes32) {
    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));
      }
    }
    return computedHash;
  }
}
/// ============ Libraries ============
/// @notice OpenZeppelin: MerkleProof
/// @dev The hashing algorithm should be keccak256 and pair sorting should be enabled.
function verify(
  bytes32[] memory proof,
  bytes32 root,
  bytes32 leaf
) internal pure returns (bool) {
  return processProof(proof, leaf) == root;
}

/// @dev Returns true if a `leaf` can be proved to be a part of a Merkle tree defined by `root`.