// File: @openzeppelin/contracts/access/IAccessControl.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (access/IAccessControl.sol)

pragma solidity ^0.8.0;

/**
 * @dev External interface of AccessControl declared to support ERC165 detection.
 */
interface IAccessControl {
    /**
     * @dev Emitted when `newAdminRole` is set as ``role``'s admin role, replacing `previousAdminRole`
     *
     * `DEFAULT_ADMIN_ROLE` is the starting admin for all roles, despite
     * {RoleAdminChanged} not being emitted signaling this.
     *
     * _Available since v3.1._
     */
    event RoleAdminChanged(bytes32 indexed role, bytes32 indexed previousAdminRole, bytes32 indexed newAdminRole);

    /**
     * @dev Emitted when `account` is granted `role`.
     *
     * `sender` is the account that originated the contract call, an admin role
     * bearer except when using {AccessControl-_setupRole}.
     */
    event RoleGranted(bytes32 indexed role, address indexed account, address indexed sender);

    /**
     * @dev Emitted when `account` is revoked `role`.
     *
     * `sender` is the account that originated the contract call:
     *   - if using `revokeRole`, it is the admin role bearer
     *   - if using `renounceRole`, it is the role bearer (i.e. `account`)
     */
    event RoleRevoked(bytes32 indexed role, address indexed account, address indexed sender);

    /**
     * @dev Returns `true` if `account` has been granted `role`.
     */
    function hasRole(bytes32 role, address account) external view returns (bool);

    /**
     * @dev Returns the admin role that controls `role`. See {grantRole} and
     * {revokeRole}.
     *
     * To change a role's admin, use {AccessControl-_setRoleAdmin}.
     */
    function getRoleAdmin(bytes32 role) external view returns (bytes32);

    /**
     * @dev Grants `role` to `account`.
     *
     * If `account` had not been already granted `role`, emits a {RoleGranted}
     * event.
     *
     * Requirements:
     *
     * - the caller must have ``role``'s admin role.
     */
    function grantRole(bytes32 role, address account) external;

    /**
     * @dev Revokes `role` from `account`.
     *
     * If `account` had been granted `role`, emits a {RoleRevoked} event.
     *
     * Requirements:
     *
     * - the caller must have ``role``'s admin role.
     */
    function revokeRole(bytes32 role, address account) external;

    /**
     * @dev Revokes `role` from the calling account.
     *
     * Roles are often managed via {grantRole} and {revokeRole}: this function's
     * purpose is to provide a mechanism for accounts to lose their privileges
     * if they are compromised (such as when a trusted device is misplaced).
     *
     * If the calling account had been granted `role`, emits a {RoleRevoked}
     * event.
     *
     * Requirements:
     *
     * - the caller must be `account`.
     */
    function renounceRole(bytes32 role, address account) external;
}

// File: @relicprotocol/contracts/interfaces/IBatchProver.sol



/// SPDX-License-Identifier: MIT
/// (c) Theori, Inc. 2022
/// All rights reserved

import "../lib/Facts.sol";

pragma solidity >=0.8.0;

/**
 * @title IBatchProver
 * @author Theori, Inc.
 * @notice IBatchProver is a standard interface implemented by some Relic provers.
 *         Supports proving multiple facts ephemerally or proving and storing
 *         them in the Reliquary.
 */
interface IBatchProver {
    /**
     * @notice prove multiple facts ephemerally
     * @param proof the encoded proof, depends on the prover implementation
     * @param store whether to store the facts in the reliquary
     * @return facts the proven facts' information
     */
    function proveBatch(bytes calldata proof, bool store)
        external
        payable
        returns (Fact[] memory facts);
}

// File: @relicprotocol/contracts/interfaces/IReliquary.sol



/// SPDX-License-Identifier: MIT

pragma solidity >=0.8.0;

import "@openzeppelin/contracts/access/IAccessControl.sol";
import "../lib/Facts.sol";

/**
 * @title Holder of Relics and Artifacts
 * @author Theori, Inc.
 * @notice The Reliquary is the heart of Relic. All issuers of Relics and Artifacts
 *         must be added to the Reliquary. Queries about Relics and Artifacts should
 *         be made to the Reliquary.
 */
interface IReliquary is IAccessControl {
    /**
     * @notice Issued when a new prover is accepted into the Reliquary
     * @param prover the address of the prover contract
     * @param version the identifier that will always be associated with the prover
     */
    event NewProver(address prover, uint64 version);

    /**
     * @notice Issued when a new prover is placed under consideration for acceptance
     *         into the Reliquary
     * @param prover the address of the prover contract
     * @param version the proposed identifier to always be associated with the prover
     * @param timestamp the earliest this prover can be brought into the Reliquary
     */
    event PendingProverAdded(address prover, uint64 version, uint64 timestamp);

    /**
     * @notice Issued when an existing prover is banished from the Reliquary
     * @param prover the address of the prover contract
     * @param version the identifier that can never be used again
     * @dev revoked provers may not issue new Relics or Artifacts. The meaning of
     *      any previously introduced Relics or Artifacts is implementation dependent.
     */
    event ProverRevoked(address prover, uint64 version);

    struct ProverInfo {
        uint64 version;
        FeeInfo feeInfo;
        bool revoked;
    }

    enum FeeFlags {
        FeeNone,
        FeeNative,
        FeeCredits,
        FeeExternalDelegate,
        FeeExternalToken
    }

    struct FeeInfo {
        uint8 flags;
        uint16 feeCredits;
        // feeWei = feeWeiMantissa * pow(10, feeWeiExponent)
        uint8 feeWeiMantissa;
        uint8 feeWeiExponent;
        uint32 feeExternalId;
    }

    function ADD_PROVER_ROLE() external view returns (bytes32);

    function CREDITS_ROLE() external view returns (bytes32);

    function DELAY() external view returns (uint64);

    function GOVERNANCE_ROLE() external view returns (bytes32);

    function SUBSCRIPTION_ROLE() external view returns (bytes32);

    /**
     * @notice activates a pending prover once the delay has passed. Callable by anyone.
     * @param prover the address of the pending prover
     */
    function activateProver(address prover) external;

    /**
     * @notice Add credits to an account. Requires the CREDITS_ROLE.
     * @param user The account to which more credits should be granted
     * @param amount The number of credits to be added
     */
    function addCredits(address user, uint192 amount) external;

    /**
     * @notice Add/propose a new prover to prove facts. Requires the ADD_PROVER_ROLE.
     * @param prover the address of the prover in question
     * @param version the unique version string to associate with this prover
     * @dev Provers and proposed provers must have unique version IDs
     * @dev After the Reliquary is initialized, a review period of 64k blocks
     *      must conclude before a prover may be added. The request must then
     *      be re-submitted to take effect. Before initialization is complete,
     *      the review period is skipped.
     * @dev Emits PendingProverAdded when a prover is proposed for inclusion
     */
    function addProver(address prover, uint64 version) external;

    /**
     * @notice Add/update a subscription. Requires the SUBSCRIPTION_ROLE.
     * @param user The subscriber account to modify
     * @param ts The new block timestamp at which the subscription expires
     */
    function addSubscriber(address user, uint64 ts) external;

    /**
     * @notice Asserts that a particular block had a particular hash
     * @param verifier The block history verifier to use for the query
     * @param hash The block hash in question
     * @param num The block number to query
     * @param proof Any witness information needed by the verifier
     * @dev Reverts if the given block was not proven to have the given hash.
     * @dev A fee may be required based on the block in question
     */
    function assertValidBlockHash(
        address verifier,
        bytes32 hash,
        uint256 num,
        bytes memory proof
    ) external payable;

    /**
     * @notice Asserts that a particular block had a particular hash. Callable only from provers.
     * @param verifier The block history verifier to use for the query
     * @param hash The block hash in question
     * @param num The block number to query
     * @param proof Any witness information needed by the verifier
     * @dev Reverts if the given block was not proven to have the given hash.
     * @dev This function is only for use by provers (reverts otherwise)
     */
    function assertValidBlockHashFromProver(
        address verifier,
        bytes32 hash,
        uint256 num,
        bytes memory proof
    ) external view;

    /**
     * @notice Require that an appropriate fee is paid for proving a fact
     * @param sender The account wanting to prove a fact
     * @dev The fee is derived from the prover which calls this  function
     * @dev Reverts if the fee is not sufficient
     * @dev Only to be called by a prover
     */
    function checkProveFactFee(address sender) external payable;

    /**
     * @notice Helper function to query the status of a prover
     * @param prover the ProverInfo associated with the prover in question
     * @dev reverts if the prover is invalid or revoked
     */
    function checkProver(ProverInfo memory prover) external pure;

    /**
     * @notice Check how many credits a given account possesses
     * @param user The account in question
     * @return The number of credits
     */
    function credits(address user) external view returns (uint192);

    /**
     * @notice Verify if a particular block had a particular hash. Only callable by address(0),
               for debug
     * @param verifier The block history verifier to use for the query
     * @param hash The block hash in question
     * @param num The block number to query
     * @param proof Any witness information needed by the verifier
     * @return boolean indication of whether or not the given block was
     *         proven to have the given hash.
     * @dev This function is for use by off-chain tools only (reverts otherwise)
     */
    function debugValidBlockHash(
        address verifier,
        bytes32 hash,
        uint256 num,
        bytes memory proof
    ) external view returns (bool);

    /**
     * @notice Query for associated information for a fact. Only callable by address(0), for debug
     * @param account The address to which the fact belongs
     * @param factSig The unique signature identifying the fact
     * @return exists whether or not a fact with the given signature
     *         is associated with the queried account
     * @return version the prover version id that proved this fact
     * @return data any associated fact data
     * @dev This function is for use by off-chain tools only (reverts otherwise)
     */
    function debugVerifyFact(address account, FactSignature factSig)
        external
        view
        returns (
            bool exists,
            uint64 version,
            bytes memory data
        );

    function factFees(uint8) external view returns (FeeInfo memory);

    function feeAccounts(address)
        external
        view
        returns (uint64 subscriberUntilTime, uint192 credits);

    function feeExternals(uint256) external view returns (address);

    /**
     * @notice Query for associated information for a fact. Only callable from provers.
     * @param account The address to which the fact belongs
     * @param factSig The unique signature identifying the fact
     * @return exists whether or not a fact with the given signature
     *         is associated with the queried account
     * @return version the prover version id that proved this fact
     * @return data any associated fact data
     * @dev This function is only for use by provers (reverts otherwise)
     */
    function getFact(address account, FactSignature factSig)
        external
        view
        returns (
            bool exists,
            uint64 version,
            bytes memory data
        );

    /**
     * @notice Determine the appropriate ETH fee to prove a fact
     * @param prover The prover of the desired fact
     * @return the fee in wei
     * @dev Reverts if the fee is not to be paid in ETH
     */
    function getProveFactNativeFee(address prover) external view returns (uint256);

    /**
     * @notice Determine the appropriate token fee to prove a fact
     * @param prover The prover of the desired fact
     * @return the fee in wei
     * @dev Reverts if the fee is not to be paid in external tokens
     */
    function getProveFactTokenFee(address prover) external view returns (uint256);

    /**
     * @notice Determine the appropriate ETH fee to query a fact
     * @param factSig The signature of the desired fact
     * @return the fee in wei
     * @dev Reverts if the fee is not to be paid in ETH
     */
    function getVerifyFactNativeFee(FactSignature factSig) external view returns (uint256);

    /**
     * @notice Determine the appropriate token fee to query a fact
     * @param factSig The signature of the desired fact
     * @return the fee in wei
     * @dev Reverts if the fee is not to be paid in external tokens
     */
    function getVerifyFactTokenFee(FactSignature factSig) external view returns (uint256);

    function initialized() external view returns (bool);

    /**
     * @notice Check if an account has an active subscription
     * @param user The account in question
     * @return True if the account is active, otherwise false
     */
    function isSubscriber(address user) external view returns (bool);

    function pendingProvers(address) external view returns (uint64 timestamp, uint64 version);

    function provers(address)
        external
        view
        returns (ProverInfo memory);

    /**
     * @notice Remove credits from an account. Requires the CREDITS_ROLE.
     * @param user The account from which credits should be removed
     * @param amount The number of credits to be removed
     */
    function removeCredits(address user, uint192 amount) external;

    /**
     * @notice Remove a subscription. Requires the SUBSCRIPTION_ROLE.
     * @param user The subscriber account to modify
     */
    function removeSubscriber(address user) external;

    /**
     * @notice Deletes the fact from the Reliquary. Only callable from provers.
     * @param account The account to which this information is bound (may be
     *        the null account for information bound to no specific address)
     * @param factSig The unique signature of the particular fact being deleted
     * @dev May only be called by non-revoked provers
     */
    function resetFact(address account, FactSignature factSig) external;

    /**
     * @notice Stop accepting proofs from this prover. Requires the GOVERNANCE_ROLE.
     * @param prover The prover to banish from the reliquary
     * @dev Emits ProverRevoked
     * @dev Note: existing facts proved by the prover may still stand
     */
    function revokeProver(address prover) external;

    function setCredits(address user, uint192 amount) external;

    /**
     * @notice Adds the given information to the Reliquary. Only callable from provers.
     * @param account The account to which this information is bound (may be
     *        the null account for information bound to no specific address)
     * @param factSig The unique signature of the particular fact being proven
     * @param data Associated data to store with this item
     * @dev May only be called by non-revoked provers
     */
    function setFact(
        address account,
        FactSignature factSig,
        bytes memory data
    ) external;

    /**
     * @notice Sets the FeeInfo for a particular fee class. Requires the GOVERNANCE_ROLE.
     * @param cls The fee class
     * @param feeInfo The FeeInfo to use for the class
     * @param feeExternal An external fee provider (token or delegate). If
     *        none is required, this should be set to 0.
     */
    function setFactFee(
        uint8 cls,
        FeeInfo memory feeInfo,
        address feeExternal
    ) external;

    /**
     * @notice Initialize the Reliquary, enforcing the time lock for new provers. Requires the
               ADD_PROVER_ROLE.
     */
    function setInitialized() external;

    /**
     * @notice Sets the FeeInfo for a particular prover. Requires the GOVERNANCE_ROLE.
     * @param prover The prover in question
     * @param feeInfo The FeeInfo to use for the class
     * @param feeExternal An external fee provider (token or delegate). If
     *        none is required, this should be set to 0.
     */
    function setProverFee(
        address prover,
        FeeInfo memory feeInfo,
        address feeExternal
    ) external;

    /**
     * @notice Sets the FeeInfo for block verification. Requires the GOVERNANCE_ROLE.
     * @param feeInfo The FeeInfo to use for the class
     * @param feeExternal An external fee provider (token or delegate). If
     *        none is required, this should be set to 0.
     */
    function setValidBlockFee(FeeInfo memory feeInfo, address feeExternal) external;

    /**
     * @notice Verify if a particular block had a particular hash
     * @param verifier The block history verifier to use for the query
     * @param hash The block hash in question
     * @param num The block number to query
     * @param proof Any witness information needed by the verifier
     * @return boolean indication of whether or not the given block was
     *         proven to have the given hash.
     * @dev A fee may be required based on the block in question
     */
    function validBlockHash(
        address verifier,
        bytes32 hash,
        uint256 num,
        bytes memory proof
    ) external payable returns (bool);

    /**
     * @notice Verify if a particular block had a particular hash. Only callable from provers.
     * @param verifier The block history verifier to use for the query
     * @param hash The block hash in question
     * @param num The block number to query
     * @param proof Any witness information needed by the verifier
     * @return boolean indication of whether or not the given block was
     *         proven to have the given hash.
     * @dev This function is only for use by provers (reverts otherwise)
     */
    function validBlockHashFromProver(
        address verifier,
        bytes32 hash,
        uint256 num,
        bytes memory proof
    ) external view returns (bool);

    /**
     * @notice FeeInfo struct for block hash queries
     */
    function verifyBlockFeeInfo() external view returns (FeeInfo memory);

    /**
     * @notice Query for associated information for a fact
     * @param account The address to which the fact belongs
     * @param factSig The unique signature identifying the fact
     * @return exists whether or not a fact with the given signature
     *         is associated with the queried account
     * @return version the prover version id that proved this fact
     * @return data any associated fact data
     * @dev A fee may be required based on the factSig
     */
    function verifyFact(address account, FactSignature factSig)
        external
        payable
        returns (
            bool exists,
            uint64 version,
            bytes memory data
        );

    /**
     * @notice Query for associated information for a fact which requires no query fee.
     * @param account The address to which the fact belongs
     * @param factSig The unique signature identifying the fact
     * @return exists whether or not a fact with the given signature
     *         is associated with the queried account
     * @return version the prover version id that proved this fact
     * @return data any associated fact data
     * @dev This function is for use by anyone
     * @dev This function reverts if the fact requires a fee to query
     */
    function verifyFactNoFee(address account, FactSignature factSig)
        external
        view
        returns (
            bool exists,
            uint64 version,
            bytes memory data
        );

    /**
     * @notice Query for the prover version for a fact
     * @param account The address to which the fact belongs
     * @param factSig The unique signature identifying the fact
     * @return exists whether or not a fact with the given signature
     *         is associated with the queried account
     * @return version the prover version id that proved this fact
     * @dev A fee may be required based on the factSig
     */
    function verifyFactVersion(address account, FactSignature factSig)
        external
        payable
        returns (bool exists, uint64 version);

    /**
     * @notice Query for the prover version for a fact which requires no query fee.
     * @param account The address to which the fact belongs
     * @param factSig The unique signature identifying the fact
     * @return exists whether or not a fact with the given signature
     *         is associated with the queried account
     * @return version the prover version id that proved this fact
     * @dev This function is for use by anyone
     * @dev This function reverts if the fact requires a fee to query
     */
    function verifyFactVersionNoFee(address account, FactSignature factSig)
        external
        view
        returns (bool exists, uint64 version);

    /**
     * @notice Reverse mapping of version information to the unique prover able
     *         to issue statements with that version
     */
    function versions(uint64) external view returns (address);

    /**
     * @notice Extract accumulated fees. Requires the GOVERNANCE_ROLE.
     * @param token The ERC20 token from which to extract fees. Or the 0 address for
     *        native ETH
     * @param dest The address to which fees should be transferred
     */
    function withdrawFees(address token, address dest) external;
}

// File: @relicprotocol/contracts/lib/BytesCalldata.sol



/// SPDX-License-Identifier: MIT

pragma solidity >=0.8.0;

// custom bytes calldata pointer storing (length | offset) in one word,
// also allows calldata pointers to be stored in memory
type BytesCalldata is uint256;

/**
 * @author Theori, Inc
 * @title BytesCalldataOps
 * @notice Common operations for bytes calldata, implemented for both the builtin
 *         type and our BytesCalldata type. These operations are heavily optimized
 *         and omit safety checks, so this library should only be used when memory
 *         safety is not a security issue.
 */
library BytesCalldataOps {
    // each consumer should add the following lines:
    using BytesCalldataOps for BytesCalldata;
    using BytesCalldataOps for bytes;

    function length(BytesCalldata bc) internal pure returns (uint256 result) {
        assembly {
            result := shr(128, shl(128, bc))
        }
    }

    function offset(BytesCalldata bc) internal pure returns (uint256 result) {
        assembly {
            result := shr(128, bc)
        }
    }

    function convert(BytesCalldata bc) internal pure returns (bytes calldata value) {
        assembly {
            value.offset := shr(128, bc)
            value.length := shr(128, shl(128, bc))
        }
    }

    function convert(bytes calldata inp) internal pure returns (BytesCalldata bc) {
        assembly {
            bc := or(shl(128, inp.offset), inp.length)
        }
    }

    function slice(
        BytesCalldata bc,
        uint256 start,
        uint256 len
    ) internal pure returns (BytesCalldata result) {
        assembly {
            result := shl(128, add(shr(128, bc), start)) // add to the offset and clear the length
            result := or(result, len) // set the new length
        }
    }

    function slice(
        bytes calldata value,
        uint256 start,
        uint256 len
    ) internal pure returns (bytes calldata result) {
        assembly {
            result.offset := add(value.offset, start)
            result.length := len
        }
    }

    function prefix(BytesCalldata bc, uint256 len) internal pure returns (BytesCalldata result) {
        assembly {
            result := shl(128, shr(128, bc)) // clear out the length
            result := or(result, len) // set it to the new length
        }
    }

    function prefix(bytes calldata value, uint256 len)
        internal
        pure
        returns (bytes calldata result)
    {
        assembly {
            result.offset := value.offset
            result.length := len
        }
    }

    function suffix(BytesCalldata bc, uint256 start) internal pure returns (BytesCalldata result) {
        assembly {
            result := add(bc, shl(128, start)) // add to the offset
            result := sub(result, start) // subtract from the length
        }
    }

    function suffix(bytes calldata value, uint256 start)
        internal
        pure
        returns (bytes calldata result)
    {
        assembly {
            result.offset := add(value.offset, start)
            result.length := sub(value.length, start)
        }
    }

    function split(BytesCalldata bc, uint256 start)
        internal
        pure
        returns (BytesCalldata, BytesCalldata)
    {
        return (prefix(bc, start), suffix(bc, start));
    }

    function split(bytes calldata value, uint256 start)
        internal
        pure
        returns (bytes calldata, bytes calldata)
    {
        return (prefix(value, start), suffix(value, start));
    }
}

// File: @relicprotocol/contracts/lib/CoreTypes.sol



/// SPDX-License-Identifier: MIT

pragma solidity >=0.8.0;

import "./BytesCalldata.sol";
import "./RLP.sol";

/**
 * @title CoreTypes
 * @author Theori, Inc.
 * @notice Data types and parsing functions for core types, including block headers
 *         and account data.
 */
library CoreTypes {
    using BytesCalldataOps for BytesCalldata;
    using BytesCalldataOps for bytes;

    struct BlockHeaderData {
        bytes32 ParentHash;
        address Coinbase;
        bytes32 Root;
        bytes32 TxHash;
        bytes32 ReceiptHash;
        uint256 Number;
        uint256 GasLimit;
        uint256 GasUsed;
        uint256 Time;
        bytes32 MixHash;
        uint256 BaseFee;
    }

    struct AccountData {
        uint256 Nonce;
        uint256 Balance;
        bytes32 StorageRoot;
        bytes32 CodeHash;
    }

    struct LogData {
        address Address;
        bytes32[] Topics;
        bytes Data;
    }

    function parseHash(bytes calldata buf) internal pure returns (bytes32 result, uint256 offset) {
        uint256 value;
        (value, offset) = RLP.parseUint(buf);
        result = bytes32(value);
    }

    function parseAddress(bytes calldata buf)
        internal
        pure
        returns (address result, uint256 offset)
    {
        uint256 value;
        (value, offset) = RLP.parseUint(buf);
        result = address(uint160(value));
    }

    function parseBlockHeader(bytes calldata header)
        internal
        pure
        returns (BlockHeaderData memory data)
    {
        (uint256 listSize, uint256 offset) = RLP.parseList(header);
        header = header.slice(offset, listSize);

        (data.ParentHash, offset) = parseHash(header); // ParentHash
        header = header.suffix(offset);
        header = RLP.skip(header); // UncleHash
        (data.Coinbase, offset) = parseAddress(header); // Coinbase
        header = header.suffix(offset);
        (data.Root, offset) = parseHash(header); // Root
        header = header.suffix(offset);
        (data.TxHash, offset) = parseHash(header); // TxHash
        header = header.suffix(offset);
        (data.ReceiptHash, offset) = parseHash(header); // ReceiptHash
        header = header.suffix(offset);
        header = RLP.skip(header); // Bloom
        header = RLP.skip(header); // Difficulty
        (data.Number, offset) = RLP.parseUint(header); // Number
        header = header.suffix(offset);
        (data.GasLimit, offset) = RLP.parseUint(header); // GasLimit
        header = header.suffix(offset);
        (data.GasUsed, offset) = RLP.parseUint(header); // GasUsed
        header = header.suffix(offset);
        (data.Time, offset) = RLP.parseUint(header); // Time
        header = header.suffix(offset);
        header = RLP.skip(header); // Extra
        (data.MixHash, offset) = parseHash(header); // MixHash
        header = header.suffix(offset);
        header = RLP.skip(header); // Nonce

        if (header.length > 0) {
            (data.BaseFee, offset) = RLP.parseUint(header); // BaseFee
        }
    }

    function getBlockHeaderHashAndSize(bytes calldata header)
        internal
        pure
        returns (bytes32 blockHash, uint256 headerSize)
    {
        (uint256 listSize, uint256 offset) = RLP.parseList(header);
        unchecked {
            headerSize = offset + listSize;
        }
        blockHash = keccak256(header.prefix(headerSize));
    }

    function parseAccount(bytes calldata account) internal pure returns (AccountData memory data) {
        (, uint256 offset) = RLP.parseList(account);
        account = account.suffix(offset);

        (data.Nonce, offset) = RLP.parseUint(account); // Nonce
        account = account.suffix(offset);
        (data.Balance, offset) = RLP.parseUint(account); // Balance
        account = account.suffix(offset);
        (data.StorageRoot, offset) = parseHash(account); // StorageRoot
        account = account.suffix(offset);
        (data.CodeHash, offset) = parseHash(account); // CodeHash
        account = account.suffix(offset);
    }

    function parseLog(bytes calldata log) internal pure returns (LogData memory data) {
        (, uint256 offset) = RLP.parseList(log);
        log = log.suffix(offset);

        uint256 tmp;
        (tmp, offset) = RLP.parseUint(log); // Address
        data.Address = address(uint160(tmp));
        log = log.suffix(offset);

        (tmp, offset) = RLP.parseList(log); // Topics
        bytes calldata topics = log.slice(offset, tmp);
        log = log.suffix(offset + tmp);

        require(topics.length % 33 == 0);
        data.Topics = new bytes32[](tmp / 33);
        uint256 i = 0;
        while (topics.length > 0) {
            (data.Topics[i], offset) = parseHash(topics);
            topics = topics.suffix(offset);
            unchecked {
                i++;
            }
        }

        (data.Data, ) = RLP.splitBytes(log);
    }

    function extractLog(bytes calldata receiptValue, uint256 logIdx)
        internal
        pure
        returns (LogData memory)
    {
        // support EIP-2718: Currently all transaction types have the same
        // receipt RLP format, so we can just skip the receipt type byte
        if (receiptValue[0] < 0x80) {
            receiptValue = receiptValue.suffix(1);
        }

        (, uint256 offset) = RLP.parseList(receiptValue);
        receiptValue = receiptValue.suffix(offset);

        // pre EIP-658, receipts stored an intermediate state root in this field
        // post EIP-658, the field is a tx status (0 for failure, 1 for success)
        uint256 statusOrIntermediateRoot;
        (statusOrIntermediateRoot, offset) = RLP.parseUint(receiptValue);
        require(statusOrIntermediateRoot != 0, "tx did not succeed");
        receiptValue = receiptValue.suffix(offset);

        receiptValue = RLP.skip(receiptValue); // GasUsed
        receiptValue = RLP.skip(receiptValue); // LogsBloom

        uint256 length;
        (length, offset) = RLP.parseList(receiptValue); // Logs
        receiptValue = receiptValue.slice(offset, length);

        // skip the earlier logs
        for (uint256 i = 0; i < logIdx; i++) {
            require(receiptValue.length > 0, "log index does not exist");
            receiptValue = RLP.skip(receiptValue);
        }

        return parseLog(receiptValue);
    }
}

// File: @relicprotocol/contracts/lib/FactSigs.sol



/// SPDX-License-Identifier: MIT

pragma solidity >=0.8.0;

import "./Facts.sol";

/**
 * @title FactSigs
 * @author Theori, Inc.
 * @notice Helper functions for computing fact signatures
 */
library FactSigs {
    /**
     * @notice Produce the fact signature data for birth certificates
     */
    function birthCertificateFactSigData() internal pure returns (bytes memory) {
        return abi.encode("BirthCertificate");
    }

    /**
     * @notice Produce the fact signature for a birth certificate fact
     */
    function birthCertificateFactSig() internal pure returns (FactSignature) {
        return Facts.toFactSignature(Facts.NO_FEE, birthCertificateFactSigData());
    }

    /**
     * @notice Produce the fact signature data for an account's storage root
     * @param blockNum the block number to look at
     * @param storageRoot the storageRoot for the account
     */
    function accountStorageFactSigData(uint256 blockNum, bytes32 storageRoot)
        internal
        pure
        returns (bytes memory)
    {
        return abi.encode("AccountStorage", blockNum, storageRoot);
    }

    /**
     * @notice Produce a fact signature for an accoun't storage root
     * @param blockNum the block number to look at
     * @param storageRoot the storageRoot for the account
     */
    function accountStorageFactSig(uint256 blockNum, bytes32 storageRoot)
        internal
        pure
        returns (FactSignature)
    {
        return
            Facts.toFactSignature(Facts.NO_FEE, accountStorageFactSigData(blockNum, storageRoot));
    }

    /**
     * @notice Produce the fact signature data for a storage slot
     * @param slot the account's slot
     * @param blockNum the block number to look at
     */
    function storageSlotFactSigData(bytes32 slot, uint256 blockNum)
        internal
        pure
        returns (bytes memory)
    {
        return abi.encode("StorageSlot", slot, blockNum);
    }

    /**
     * @notice Produce a fact signature for a storage slot
     * @param slot the account's slot
     * @param blockNum the block number to look at
     */
    function storageSlotFactSig(bytes32 slot, uint256 blockNum)
        internal
        pure
        returns (FactSignature)
    {
        return Facts.toFactSignature(Facts.NO_FEE, storageSlotFactSigData(slot, blockNum));
    }

    /**
     * @notice Produce the fact signature data for a log
     * @param blockNum the block number to look at
     * @param txIdx the transaction index in the block
     * @param logIdx the log index in the transaction
     */
    function logFactSigData(
        uint256 blockNum,
        uint256 txIdx,
        uint256 logIdx
    ) internal pure returns (bytes memory) {
        return abi.encode("Log", blockNum, txIdx, logIdx);
    }

    /**
     * @notice Produce a fact signature for a log
     * @param blockNum the block number to look at
     * @param txIdx the transaction index in the block
     * @param logIdx the log index in the transaction
     */
    function logFactSig(
        uint256 blockNum,
        uint256 txIdx,
        uint256 logIdx
    ) internal pure returns (FactSignature) {
        return Facts.toFactSignature(Facts.NO_FEE, logFactSigData(blockNum, txIdx, logIdx));
    }

    /**
     * @notice Produce the fact signature data for a block header
     * @param blockNum the block number
     */
    function blockHeaderSigData(uint256 blockNum) internal pure returns (bytes memory) {
        return abi.encode("BlockHeader", blockNum);
    }

    /**
     * @notice Produce the fact signature data for a block header
     * @param blockNum the block number
     */
    function blockHeaderSig(uint256 blockNum) internal pure returns (FactSignature) {
        return Facts.toFactSignature(Facts.NO_FEE, blockHeaderSigData(blockNum));
    }

    /**
     * @notice Produce the fact signature data for an event fact
     * @param eventId The event in question
     */
    function eventFactSigData(uint64 eventId) internal pure returns (bytes memory) {
        return abi.encode("EventAttendance", "EventID", eventId);
    }

    /**
     * @notice Produce a fact signature for a given event
     * @param eventId The event in question
     */
    function eventFactSig(uint64 eventId) internal pure returns (FactSignature) {
        return Facts.toFactSignature(Facts.NO_FEE, eventFactSigData(eventId));
    }
}
// File: @relicprotocol/contracts/lib/Facts.sol



/// SPDX-License-Identifier: MIT

pragma solidity >=0.8.0;

type FactSignature is bytes32;

struct Fact {
    address account;
    FactSignature sig;
    bytes data;
}

/**
 * @title Facts
 * @author Theori, Inc.
 * @notice Helper functions for fact classes (part of fact signature that determines fee).
 */
library Facts {
    uint8 internal constant NO_FEE = 0;

    /**
     * @notice construct a fact signature from a fact class and some unique data
     * @param cls the fact class (determines the fee)
     * @param data the unique data for the signature
     */
    function toFactSignature(uint8 cls, bytes memory data) internal pure returns (FactSignature) {
        return FactSignature.wrap(bytes32((uint256(keccak256(data)) << 8) | cls));
    }

    /**
     * @notice extracts the fact class from a fact signature
     * @param factSig the input fact signature
     */
    function toFactClass(FactSignature factSig) internal pure returns (uint8) {
        return uint8(uint256(FactSignature.unwrap(factSig)));
    }
}

// File: @relicprotocol/contracts/lib/RLP.sol



/// SPDX-License-Identifier: MIT

pragma solidity >=0.8.0;

/**
 * @title RLP
 * @author Theori, Inc.
 * @notice Gas optimized RLP parsing code. Note that some parsing logic is
 *         duplicated because helper functions are oddly expensive.
 */
library RLP {
    function parseUint(bytes calldata buf) internal pure returns (uint256 result, uint256 size) {
        assembly {
            // check that we have at least one byte of input
            if iszero(buf.length) {
                revert(0, 0)
            }
            let first32 := calldataload(buf.offset)
            let kind := shr(248, first32)

            // ensure it's a not a long string or list (> 0xB7)
            // also ensure it's not a short string longer than 32 bytes (> 0xA0)
            if gt(kind, 0xA0) {
                revert(0, 0)
            }

            switch lt(kind, 0x80)
            case true {
                // small single byte
                result := kind
                size := 1
            }
            case false {
                // short string
                size := sub(kind, 0x80)

                // ensure it's not reading out of bounds
                if lt(buf.length, size) {
                    revert(0, 0)
                }

                switch eq(size, 32)
                case true {
                    // if it's exactly 32 bytes, read it from calldata
                    result := calldataload(add(buf.offset, 1))
                }
                case false {
                    // if it's < 32 bytes, we've already read it from calldata
                    result := shr(shl(3, sub(32, size)), shl(8, first32))
                }
                size := add(size, 1)
            }
        }
    }

    function nextSize(bytes calldata buf) internal pure returns (uint256 size) {
        assembly {
            if iszero(buf.length) {
                revert(0, 0)
            }
            let first32 := calldataload(buf.offset)
            let kind := shr(248, first32)

            switch lt(kind, 0x80)
            case true {
                // small single byte
                size := 1
            }
            case false {
                switch lt(kind, 0xB8)
                case true {
                    // short string
                    size := add(1, sub(kind, 0x80))
                }
                case false {
                    switch lt(kind, 0xC0)
                    case true {
                        // long string
                        let lengthSize := sub(kind, 0xB7)

                        // ensure that we don't overflow
                        if gt(lengthSize, 31) {
                            revert(0, 0)
                        }

                        // ensure that we don't read out of bounds
                        if lt(buf.length, lengthSize) {
                            revert(0, 0)
                        }
                        size := shr(mul(8, sub(32, lengthSize)), shl(8, first32))
                        size := add(size, add(1, lengthSize))
                    }
                    case false {
                        switch lt(kind, 0xF8)
                        case true {
                            // short list
                            size := add(1, sub(kind, 0xC0))
                        }
                        case false {
                            let lengthSize := sub(kind, 0xF7)

                            // ensure that we don't overflow
                            if gt(lengthSize, 31) {
                                revert(0, 0)
                            }
                            // ensure that we don't read out of bounds
                            if lt(buf.length, lengthSize) {
                                revert(0, 0)
                            }
                            size := shr(mul(8, sub(32, lengthSize)), shl(8, first32))
                            size := add(size, add(1, lengthSize))
                        }
                    }
                }
            }
        }
    }

    function skip(bytes calldata buf) internal pure returns (bytes calldata) {
        uint256 size = RLP.nextSize(buf);
        assembly {
            buf.offset := add(buf.offset, size)
            buf.length := sub(buf.length, size)
        }
        return buf;
    }

    function parseList(bytes calldata buf)
        internal
        pure
        returns (uint256 listSize, uint256 offset)
    {
        assembly {
            // check that we have at least one byte of input
            if iszero(buf.length) {
                revert(0, 0)
            }
            let first32 := calldataload(buf.offset)
            let kind := shr(248, first32)

            // ensure it's a list
            if lt(kind, 0xC0) {
                revert(0, 0)
            }

            switch lt(kind, 0xF8)
            case true {
                // short list
                listSize := sub(kind, 0xC0)
                offset := 1
            }
            case false {
                // long list
                let lengthSize := sub(kind, 0xF7)

                // ensure that we don't overflow
                if gt(lengthSize, 31) {
                    revert(0, 0)
                }
                // ensure that we don't read out of bounds
                if lt(buf.length, lengthSize) {
                    revert(0, 0)
                }
                listSize := shr(mul(8, sub(32, lengthSize)), shl(8, first32))
                offset := add(lengthSize, 1)
            }
        }
    }

    function splitBytes(bytes calldata buf)
        internal
        pure
        returns (bytes calldata result, bytes calldata rest)
    {
        uint256 offset;
        uint256 size;
        assembly {
            // check that we have at least one byte of input
            if iszero(buf.length) {
                revert(0, 0)
            }
            let first32 := calldataload(buf.offset)
            let kind := shr(248, first32)

            // ensure it's a not list
            if gt(kind, 0xBF) {
                revert(0, 0)
            }

            switch lt(kind, 0x80)
            case true {
                // small single byte
                offset := 0
                size := 1
            }
            case false {
                switch lt(kind, 0xB8)
                case true {
                    // short string
                    offset := 1
                    size := sub(kind, 0x80)
                }
                case false {
                    // long string
                    let lengthSize := sub(kind, 0xB7)

                    // ensure that we don't overflow
                    if gt(lengthSize, 31) {
                        revert(0, 0)
                    }
                    // ensure we don't read out of bounds
                    if lt(buf.length, lengthSize) {
                        revert(0, 0)
                    }
                    size := shr(mul(8, sub(32, lengthSize)), shl(8, first32))
                    offset := add(lengthSize, 1)
                }
            }

            result.offset := add(buf.offset, offset)
            result.length := size

            let end := add(offset, size)
            rest.offset := add(buf.offset, end)
            rest.length := sub(buf.length, end)
        }
    }

    function encodeUint(uint256 value) internal pure returns (bytes memory) {
        // allocate our result bytes
        bytes memory result = new bytes(33);

        if (value == 0) {
            // store length = 1, value = 0x80
            assembly {
                mstore(add(result, 1), 0x180)
            }
            return result;
        }

        if (value < 128) {
            // store length = 1, value = value
            assembly {
                mstore(add(result, 1), or(0x100, value))
            }
            return result;
        }

        if (value > 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff) {
            // length 33, prefix 0xa0 followed by value
            assembly {
                mstore(add(result, 1), 0x21a0)
                mstore(add(result, 33), value)
            }
            return result;
        }

        if (value > 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff) {
            // length 32, prefix 0x9f followed by value
            assembly {
                mstore(add(result, 1), 0x209f)
                mstore(add(result, 33), shl(8, value))
            }
            return result;
        }

        assembly {
            let length := 1
            for {
                let min := 0x100
            } lt(sub(min, 1), value) {
                min := shl(8, min)
            } {
                length := add(length, 1)
            }

            let bytesLength := add(length, 1)

            // bytes length field
            let hi := shl(mul(bytesLength, 8), bytesLength)

            // rlp encoding of value
            let lo := or(shl(mul(length, 8), add(length, 0x80)), value)

            mstore(add(result, bytesLength), or(hi, lo))
        }
        return result;
    }
}

// File: @relicprotocol/contracts/lib/Storage.sol



/// SPDX-License-Identifier: MIT

pragma solidity >=0.8.0;

/**
 * @title Storage
 * @author Theori, Inc.
 * @notice Helper functions for handling storage slot facts and computing storage slots
 */
library Storage {
    /**
     * @notice compute the slot for an element of a mapping
     * @param base the slot of the struct base
     * @param key the mapping key, padded to 32 bytes
     */
    function mapElemSlot(bytes32 base, bytes32 key) internal pure returns (bytes32) {
        return keccak256(abi.encodePacked(key, base));
    }

    /**
     * @notice compute the slot for an element of a static array
     * @param base the slot of the struct base
     * @param idx the index of the element
     * @param slotsPerElem the number of slots per element
     */
    function staticArrayElemSlot(
        bytes32 base,
        uint256 idx,
        uint256 slotsPerElem
    ) internal pure returns (bytes32) {
        return bytes32(uint256(base) + idx * slotsPerElem);
    }

    /**
     * @notice compute the slot for an element of a dynamic array
     * @param base the slot of the struct base
     * @param idx the index of the element
     * @param slotsPerElem the number of slots per element
     */
    function dynamicArrayElemSlot(
        bytes32 base,
        uint256 idx,
        uint256 slotsPerElem
    ) internal pure returns (bytes32) {
        return bytes32(uint256(keccak256(abi.encode(base))) + idx * slotsPerElem);
    }

    /**
     * @notice compute the slot for a struct field given the base slot and offset
     * @param base the slot of the struct base
     * @param offset the slot offset in the struct
     */
    function structFieldSlot(
        bytes32 base,
        uint256 offset
    ) internal pure returns (bytes32) {
        return bytes32(uint256(base) + offset);
    }

    function _parseUint256(bytes memory data) internal pure returns (uint256) {
        return uint256(bytes32(data)) >> (256 - 8 * data.length);
    }

    /**
     * @notice parse a uint256 from storage slot bytes
     * @param data the storage slot bytes
     * @return address the parsed address
     */
    function parseUint256(bytes memory data) internal pure returns (uint256) {
        require(data.length <= 32, 'data is not a uint256');
        return _parseUint256(data);
    }

    /**
     * @notice parse a uint64 from storage slot bytes
     * @param data the storage slot bytes
     */
    function parseUint64(bytes memory data) internal pure returns (uint64) {
        require(data.length <= 8, 'data is not a uint64');
        return uint64(_parseUint256(data));
    }

    /**
     * @notice parse an address from storage slot bytes
     * @param data the storage slot bytes
     */
    function parseAddress(bytes memory data) internal pure returns (address) {
        require(data.length <= 20, 'data is not an address');
        return address(uint160(_parseUint256(data)));
    }
}

// File: contracts/UniV2TWAP.sol



/// SPDX-License-Identifier: MIT

pragma solidity >=0.8.0;

import "@relicprotocol/contracts/interfaces/IBatchProver.sol";
import "@relicprotocol/contracts/interfaces/IReliquary.sol";
import "@relicprotocol/contracts/lib/Facts.sol";
import "@relicprotocol/contracts/lib/FactSigs.sol";
import "@relicprotocol/contracts/lib/CoreTypes.sol";
import "@relicprotocol/contracts/lib/Storage.sol";

/**
 * @title UniV2TWAP
 * @author Theori, Inc.
 * @notice A trustless, fully on-chain UniswapV2 TWAP oracle built using Relic.
 */
contract UniV2TWAP {
    bytes32 constant reservesTimeSlot = bytes32(uint256(8));
    bytes32 constant price0CumulativeLastSlot = bytes32(uint256(9));
    bytes32 constant price1CumulativeLastSlot = bytes32(uint256(10));

    IReliquary immutable reliquary;

    struct TWAPParams {
        address pair;
        bool zero;
        uint256 startBlock;
        uint256 endBlock;
    }

    event TWAP(TWAPParams params, uint224 cumulativePrice);

    mapping(bytes32 => uint224) public priceMap;

    constructor(IReliquary _reliquary) {
        reliquary = _reliquary;
    }

    function paramsHash(TWAPParams memory params) public pure returns (bytes32 hash) {
        hash = keccak256(abi.encode(params));
    }

    /**
     * @notice Returns the TWAP price for the given params, or 0 if no such price was proven
     * @dev The returned price is in UQ112x112 format used by Uniswap V2. Many libraries exist
     *      for handing these values, for example
     *      https://github.com/compound-finance/open-oracle/blob/master/contracts/Uniswap/UniswapLib.sol
     * @param params the TWAP params
     */
    function getPrice(TWAPParams memory params) public view returns (uint224) {
        return priceMap[paramsHash(params)];
    }

    function extractReservesSlot(uint256 slot) internal pure returns (
        uint256 reserve0,
        uint256 reserve1,
        uint256 timestamp
    ) {
        reserve0 = uint256(uint112(slot));
        reserve1 = uint256(uint112(slot >> 112));
        timestamp = uint256(uint32(slot >> 224));
    }

    function proveUniV2State(
        IBatchProver prover,
        uint256 blockNum,
        address pair,
        bool zero,
        bytes calldata proof
    ) internal returns (
        uint256 cumulativePrice, uint256 timestamp
    ) {
        bytes32 slot = zero ? price0CumulativeLastSlot : price1CumulativeLastSlot;

        // prove the startBlock fact, forwarding along any proving fee
        Fact[] memory facts = prover.proveBatch(proof, false);
        require(facts.length == 3, "prover returned incorect number of facts");

        require(
            FactSignature.unwrap(facts[0].sig) ==
            FactSignature.unwrap(FactSigs.blockHeaderSig(blockNum)),
            "first fact is not block header"
        );
        bytes memory encoded = facts[0].data;
        CoreTypes.BlockHeaderData memory head;
        assembly {
            // this decoding is safe because BlockHeaderData contains only value types
            head := add(encoded, 0x20)
        }
        timestamp = head.Time;
        require(
            facts[1].account == pair,
            "fact1 account mismatch"
        );
        require(
            FactSignature.unwrap(facts[1].sig) ==
            FactSignature.unwrap(FactSigs.storageSlotFactSig(slot, blockNum)),
            "prover returned unexpected fact signature"
        );
        cumulativePrice = Storage.parseUint256(facts[1].data);

        require(
            facts[2].account == pair,
            "fact2 account mismatch"
        );
        require(
            FactSignature.unwrap(facts[2].sig) ==
            FactSignature.unwrap(FactSigs.storageSlotFactSig(reservesTimeSlot, blockNum)),
            "prover returned unexpected fact signature"
        );
        uint256 reservesSlot = Storage.parseUint256(facts[2].data);

        (uint256 reserve0, uint256 reserve1, uint256 lastTime) = extractReservesSlot(reservesSlot);
        uint256 timeElapsed = timestamp - lastTime;
        uint256 spotPrice = zero ? ((reserve1 << 112) / reserve0) : ((reserve0 << 112) / reserve1);

        cumulativePrice += spotPrice * timeElapsed;
    }

    /**
     * @notice submit a price to oracle's price map
     * @param params the TWAP parameters
     * @param prover the Relic batch prover to use
     * @param startProof the proof to verify the data at startBlock
     * @param endProof the proof to verify the data at endBlock
     */
    function submitPrice(
        TWAPParams memory params,
        address prover,
        bytes calldata startProof,
        bytes calldata endProof
    ) external {
        require(params.startBlock < params.endBlock, "startBlock must be before endBlock");

        // check that it's a valid prover
        IReliquary.ProverInfo memory info = reliquary.provers(prover);
        require(info.version > 0 && !info.revoked, "Invalid prover provided");

        (uint256 startCumulativePrice, uint256 startTime) = proveUniV2State(
            IBatchProver(prover), params.startBlock, params.pair, params.zero, startProof
        );
        (uint256 endCumulativePrice, uint256 endTime) = proveUniV2State(
            IBatchProver(prover), params.endBlock, params.pair, params.zero, endProof
        );
        uint224 cumulativePrice = uint224((endCumulativePrice - startCumulativePrice) / (endTime - startTime));

        emit TWAP(params, cumulativePrice);
        priceMap[paramsHash(params)] = cumulativePrice;
    }
}