// Contract: DerpDAO
// Target function: function processProof(bytes32[] memory proof, bytes32 leaf) internal pure returns (bytes32)
 address that signed a hashed message (`hash`) with
        * `signature` or error string. This address can then be used for verification purposes.
        *
        * The `ecrecover` EVM opcode allows for malleable (non-unique) signatures:
        * this function rejects them by requiring the `s` value to be in the lower
        * half order, and the `v` value to be either 27 or 28.
        *
        * IMPORTANT: `hash` _must_ be the result of a hash operation for the
        * verification to be secure: it is possible to craft signatures that
        * recover to arbitrary addresses for non-hashed data. A safe way to ensure
        * this is by receiving a hash of the original message (which may otherwise
        * be too long), and then calling {toEthSignedMessageHash} on it.
        *
        * Documentation for signature generation:
        * - with https://web3js.readthedocs.io/en/v1.3.4/web3-eth-accounts.html#sign[Web3.js]
        * - with https://docs.ethers.io/v5/api/signer/#Signer-signMessage[ethers]
        *
        * _Available since v4.3._
        */
        function tryRecover(bytes32 hash, bytes memory signature) internal pure returns (address, RecoverError) {
            // Check the signature length
            // - case 65: r,s,v signature (standard)
            // - case 64: r,vs signature (cf https://eips.ethereum.org/EIPS/eip-2098) _Available since v4.1._
            if (signature.length == 65) {
                bytes32 r;
                bytes32 s;
                uint8 v;
                // ecrecover takes the signature parameters, and the only way to get them
                // currently is to use assembly.
                assembly {
                    r := mload(add(signature, 0x20))
                    s := mload(add(signature, 0x40))
                    v := byte(0, mload(add(signature, 0x60)))
                }
                return tryRecover(hash, v, r, s);
            } else if (signature.length == 64) {
                bytes32 r;
                bytes32 vs;
                // ecrecover takes the signature parameters, and the only way to get them
                // currently is to use assembly.
                assembly {
                    r := mload(add(signature, 0x20))
                    vs := mload(add(signature, 0x40))
                }
                return tryRecover(hash, r, vs);
            } else {
                return (address(0), RecoverError.InvalidSignatureLength);
            }
        }

        /**
        * @dev Returns the address that signed a hashed message (`hash`) with
        * `signature`. This address can then be used for verification purposes.
        *
        * The `ecrecover` EVM opcode allows for malleable (non-unique) signatures:
        * this function rejects them by requiring the `s` value to be in the lower
        * half order, and the `v` value to be either 27 or 28.
        *
        * IMPORTANT: `hash` _must_ be the result of a hash operation for the
        * verification to be secure: it is possible to craft signatures that
        * recover to arbitrary addresses for non-hashed data. A safe way to ensure
        * this is by receiving a hash of the original message (which may otherwise
        * be too long), and then calling {toEthSignedMessageHash} on it.
        */
        function recover(bytes32 hash, bytes memory signature) internal pure returns (address) {
            (address recovered, RecoverError error) = tryRecover(hash, signature);
            _throwError(error);
            return recovered;
        }

        /**
        * @dev Overload of {ECDSA-tryRecover} that receives the `r` and `vs` short-signature fields separately.
        *
        * See https://eips.ethereum.org/EIPS/eip-2098[EIP-2098 short signatures]
        *
        * _Available since v4.3._
        */
        function tryRecover(
            bytes32 hash,
            bytes32 r,
            bytes32 vs
        ) internal pure returns (address, RecoverError) {
            bytes32 s;
            uint8 v;
            assembly {
                s := and(vs, 0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff)
                v := add(shr(255, vs), 27)
            }
            return tryRecover(hash, v, r, s);
        }

        /**
        * @dev Overload of {ECDSA-recover} that receives the `r and `vs` short-signature fields separately.
        *
        * _Available since v4.2._
        */
        function recover(
            bytes32 hash,
            bytes32 r,
            bytes32 vs
        ) internal pure returns (address) {
            (address recovered, RecoverError error) = tryRecover(hash, r, vs);
            _throwError(error);
            return recovered;
        }

        /**
        * @dev Overload of {ECDSA-tryRecover} that receives the `v`,
        * `r` and `s` signature fields separately.
        *
        * _Available since v4.3._
        */
        function tryRecover(
            bytes32 hash,
            uint8 v,
            bytes32 r,
            bytes32 s
        ) internal pure returns (address, RecoverError) {
            // EIP-2 still allows signature malleability for ecrecover(). Remove this possibility and make the signature
            // unique. Appendix F in the Ethereum Yellow paper (https://ethereum.github.io/yellowpaper/paper.pdf), defines
            // the valid range for s in (301): 0 < s < secp256k1n ÷ 2 + 1, and for v in (302): v ∈ {27, 28}. Most
            // signatures from current libraries generate a unique signature with an s-value in the lower half order.
            //
            // If your library generates malleable signatures, such as s-values in the upper range, calculate a new s-value
            // with 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 - s1 and flip v from 27 to 28 or
            // vice versa. If your library also generates signatures with 0/1 for v instead 27/28, add 27 to v to accept
            // these malleable signatures as well.
            if (uint256(s) > 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0) {
                return (address(0), RecoverError.InvalidSignatureS);
            }
            if (v != 27 && v != 28) {
                return (address(0), RecoverError.InvalidSignatureV);
            }

            // If the signature is valid (and not malleable), return the signer address
            address signer = ecrecover(hash, v, r, s);
            if (signer == address(0)) {
                return (address(0), RecoverError.InvalidSignature);
            }

            return (signer, RecoverError.NoError);
        }

        /**
        * @dev Overload of {ECDSA-recover} that receives the `v`,
        * `r` and `s` signature fields separately.
        */
        function recover(
            bytes32 hash,
            uint8 v,
            bytes32 r,
            bytes32 s
        ) internal pure returns (address) {
            (address recovered, RecoverError error) = tryRecover(hash, v, r, s);
            _throwError(error);
            return recovered;
        }

        /**
        * @dev Returns an Ethereum Signed Message, created from a `hash`. This
        * produces hash corresponding to the one signed with the
        * https://eth.wiki/json-rpc/API#eth_sign[`eth_sign`]
        * JSON-RPC method as part of EIP-191.
        *
        * See {recover}.
        */
        function toEthSignedMessageHash(bytes32 hash) internal pure returns (bytes32) {
            // 32 is the length in bytes of hash,
            // enforced by the type signature above
            return keccak256(abi.encodePacked("\x19Ethereum Signed Message:\n32", hash));
        }

        /**
        * @dev Returns an Ethereum Signed Message, created from `s`. This
        * produces hash corresponding to the one signed with the
        * https://eth.wiki/json-rpc/API#eth_sign[`eth_sign`]
        * JSON-RPC method as part of EIP-191.
        *
        * See {recover}.
        */
        function toEthSignedMessageHash(bytes memory s) internal pure returns (bytes32) {
            return keccak256(abi.encodePacked("\x19Ethereum Signed Message:\n", Strings.toString(s.length), s));
        }

        /**
        * @dev Returns an Ethereum Signed Typed Data, created from a
        * `domainSeparator` and a `structHash`. This produces hash corresponding
        * to the one signed with the
        * https://eips.ethereum.org/EIPS/eip-712[`eth_signTypedData`]
        * JSON-RPC method as part of EIP-712.
        *
        * See {recover}.
        */
        function toTypedDataHash(bytes32 domainSeparator, bytes32 structHash) internal pure returns (bytes32) {
            return keccak256(abi.encodePacked("\x19\x01", domainSeparator, structHash));
        }
    }

    pragma solidity ^0.8.0;


    /**
    * @dev https://eips.ethereum.org/EIPS/eip-712[EIP 712] is a standard for hashing and signing of typed structured data.
    *
    * The encoding specified in the EIP is very generic, and such a generic implementation in Solidity is not feasible,
    * thus this contract does not implement the encoding itself. Protocols need to implement the type-specific encoding
    * they need in their contracts using a combination of `abi.encode` and `keccak256`.
    *
    * This contract implements the EIP 712 domain separator ({_domainSeparatorV4}) that is used as part of the encoding
    * scheme, and the final step of the encoding to obtain the message digest that is then signed via ECDSA
    * ({_hashTypedDataV4}).
    *
    * The implementation of the domain separator was designed to be as efficient as possible while still properly updating
    * the chain id to protect against replay attacks on an eventual fork of the chain.
    *
    * NOTE: This contract implements the version of the encoding known as "v4", as implemented by the JSON RPC method
    * https://docs.metamask.io/guide/signing-data.html[`eth_signTypedDataV4` in MetaMask].
    *
    * _Available since v3.4._
    */
    abstract contract EIP712 {
        /* solhint-disable var-name-mixedcase */
        // Cache the domain separator as an immutable value, but also store the chain id that it corresponds to, in order to
        // invalidate the cached domain separator if the chain id changes.
        bytes32 private immutable _CACHED_DOMAIN_SEPARATOR;
        uint256 private immutable _CACHED_CHAIN_ID;
        address private immutable _CACHED_THIS;

        bytes32 private immutable _HASHED_NAME;
        bytes32 private immutable _HASHED_VERSION;
        bytes32 private immutable _TYPE_HASH;

        /* solhint-enable var-name-mixedcase */

        /**
        * @dev Initializes the domain separator and parameter caches.
        *
        * The meaning of `name` and `version` is specified in
        * https://eips.ethereum.org/EIPS/eip-712#definition-of-domainseparator[EIP 712]:
        *
        * - `name`: the user readable name of the signing domain, i.e. the name of the DApp or the protocol.
        * - `version`: the current major version of the signing domain.
        *
        * NOTE: These parameters cannot be changed except through a xref:learn::upgrading-smart-contracts.adoc[smart
        * contract upgrade].
        */
        constructor(string memory name, string memory version) {
            bytes32 hashedName = keccak256(bytes(name));
            bytes32 hashedVersion = keccak256(bytes(version));
            bytes32 typeHash = keccak256(
                "EIP712Domain(string name,string version,uint256 chainId,address verifyingContract)"
            );
            _HASHED_NAME = hashedName;
            _HASHED_VERSION = hashedVersion;
            _CACHED_CHAIN_ID = block.chainid;
            _CACHED_DOMAIN_SEPARATOR = _buildDomainSeparator(typeHash, hashedName, hashedVersion);
            _CACHED_THIS = address(this);
            _TYPE_HASH = typeHash;
        }

        /**
        * @dev Returns the domain separator for the current chain.
        */
        function _domainSeparatorV4() internal view returns (bytes32) {
            if (address(this) == _CACHED_THIS && block.chainid == _CACHED_CHAIN_ID) {
                return _CACHED_DOMAIN_SEPARATOR;
            } else {
                return _buildDomainSeparator(_TYPE_HASH, _HASHED_NAME, _HASHED_VERSION);
            }
        }

        function _buildDomainSeparator(
            bytes32 typeHash,
            bytes32 nameHash,
            bytes32 versionHash
        ) private view returns (bytes32) {
            return keccak256(abi.encode(typeHash, nameHash, versionHash, block.chainid, address(this)));
        }

        /**
        * @dev Given an already https://eips.ethereum.org/EIPS/eip-712#definition-of-hashstruct[hashed struct], this
        * function returns the hash of the fully encoded EIP712 message for this domain.
        *
        * This hash can be used together with {ECDSA-recover} to obtain the signer of a message. For example:
        *
        * ```solidity
        * bytes32 digest = _hashTypedDataV4(keccak256(abi.encode(
        *     keccak256("Mail(address to,string contents)"),
        *     mailTo,
        *     keccak256(bytes(mailContents))
        * )));
        * address signer = ECDSA.recover(digest, signature);
        * ```
        */
        function _hashTypedDataV4(bytes32 structHash) internal view virtual returns (bytes32) {
            return ECDSA.toTypedDataHash(_domainSeparatorV4(), structHash);
        }
    }

    pragma solidity ^0.8.0;

    /**
    * @dev Interface of the ERC20 Permit extension allowing approvals to be made via signatures, as defined in
    * https://eips.ethereum.org/EIPS/eip-2612[EIP-2612].
    *
    * Adds the {permit} method, which can be used to change an account's ERC20 allowance (see {IERC20-allowance}) by
    * presenting a message signed by the account. By not relying on {IERC20-approve}, the token holder account doesn't
    * need to send a transaction, and thus is not required to hold Ether at all.
    */
    interface IERC20Permit {
        /**
        * @dev Sets `value` as the allowance of `spender` over ``owner``'s tokens,
        * given ``owner``'s signed approval.
        *
        * IMPORTANT: The same issues {IERC20-approve} has related to transaction
        * ordering also apply here.
        *
        * Emits an {Approval} event.
        *
        * Requirements:
        *
        * - `spender` cannot be the zero address.
        * - `deadline` must be a timestamp in the future.
        * - `v`, `r` and `s` must be a valid `secp256k1` signature from `owner`
        * over the EIP712-formatted function arguments.
        * - the signature must use ``owner``'s current nonce (see {nonces}).
        *
        * For more information on the signature format, see the
        * https://eips.ethereum.org/EIPS/eip-2612#specification[relevant EIP
        * section].
        */
        function permit(
            address owner,
            address spender,
            uint256 value,
            uint256 deadline,
            uint8 v,
            bytes32 r,
            bytes32 s
        ) external;

        /**
        * @dev Returns the current nonce for `owner`. This value must be
        * included whenever a signature is generated for {permit}.
        *
        * Every successful call to {permit} increases ``owner``'s nonce by one. This
        * prevents a signature from being used multiple times.
        */
        function nonces(address owner) external view returns (uint256);

        /**
        * @dev Returns the domain separator used in the encoding of the signature for {permit}, as defined by {EIP712}.
        */
        // solhint-disable-next-line func-name-mixedcase
        function DOMAIN_SEPARATOR() external view returns (bytes32);
    }

    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) {
            return processProof(proof, leaf) == root;
        }