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



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.7.0) (access/Ownable.sol)

pragma solidity ^0.8.0;

import "../utils/Context.sol";

/**
 * @dev Contract module which provides a basic access control mechanism, where
 * there is an account (an owner) that can be granted exclusive access to
 * specific functions.
 *
 * By default, the owner account will be the one that deploys the contract. This
 * can later be changed with {transferOwnership}.
 *
 * This module is used through inheritance. It will make available the modifier
 * `onlyOwner`, which can be applied to your functions to restrict their use to
 * the owner.
 */
abstract contract Ownable is Context {
    address private _owner;

    event OwnershipTransferred(address indexed previousOwner, address indexed newOwner);

    /**
     * @dev Initializes the contract setting the deployer as the initial owner.
     */
    constructor() {
        _transferOwnership(_msgSender());
    }

    /**
     * @dev Throws if called by any account other than the owner.
     */
    modifier onlyOwner() {
        _checkOwner();
        _;
    }

    /**
     * @dev Returns the address of the current owner.
     */
    function owner() public view virtual returns (address) {
        return _owner;
    }

    /**
     * @dev Throws if the sender is not the owner.
     */
    function _checkOwner() internal view virtual {
        require(owner() == _msgSender(), "Ownable: caller is not the owner");
    }

    /**
     * @dev Leaves the contract without owner. It will not be possible to call
     * `onlyOwner` functions anymore. Can only be called by the current owner.
     *
     * NOTE: Renouncing ownership will leave the contract without an owner,
     * thereby removing any functionality that is only available to the owner.
     */
    function renounceOwnership() public virtual onlyOwner {
        _transferOwnership(address(0));
    }

    /**
     * @dev Transfers ownership of the contract to a new account (`newOwner`).
     * Can only be called by the current owner.
     */
    function transferOwnership(address newOwner) public virtual onlyOwner {
        require(newOwner != address(0), "Ownable: new owner is the zero address");
        _transferOwnership(newOwner);
    }

    /**
     * @dev Transfers ownership of the contract to a new account (`newOwner`).
     * Internal function without access restriction.
     */
    function _transferOwnership(address newOwner) internal virtual {
        address oldOwner = _owner;
        _owner = newOwner;
        emit OwnershipTransferred(oldOwner, newOwner);
    }
}

// File: @openzeppelin/contracts/utils/Context.sol



// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (utils/Context.sol)

pragma solidity ^0.8.0;

/**
 * @dev Provides information about the current execution context, including the
 * sender of the transaction and its data. While these are generally available
 * via msg.sender and msg.data, they should not be accessed in such a direct
 * manner, since when dealing with meta-transactions the account sending and
 * paying for execution may not be the actual sender (as far as an application
 * is concerned).
 *
 * This contract is only required for intermediate, library-like contracts.
 */
abstract contract Context {
    function _msgSender() internal view virtual returns (address) {
        return msg.sender;
    }

    function _msgData() internal view virtual returns (bytes calldata) {
        return msg.data;
    }
}

// File: contracts/AnteProofOfTransaction.sol



// SPDX-License-Identifier: GPL-3.0-only

// ┏━━━┓━━━━━┏┓━━━━━━━━━┏━━━┓━━━━━━━━━━━━━━━━━━━━━━━
// ┃┏━┓┃━━━━┏┛┗┓━━━━━━━━┃┏━━┛━━━━━━━━━━━━━━━━━━━━━━━
// ┃┗━┛┃┏━┓━┗┓┏┛┏━━┓━━━━┃┗━━┓┏┓┏━┓━┏━━┓━┏━┓━┏━━┓┏━━┓
// ┃┏━┓┃┃┏┓┓━┃┃━┃┏┓┃━━━━┃┏━━┛┣┫┃┏┓┓┗━┓┃━┃┏┓┓┃┏━┛┃┏┓┃
// ┃┃ ┃┃┃┃┃┃━┃┗┓┃┃━┫━┏┓━┃┃━━━┃┃┃┃┃┃┃┗┛┗┓┃┃┃┃┃┗━┓┃┃━┫
// ┗┛ ┗┛┗┛┗┛━┗━┛┗━━┛━┗┛━┗┛━━━┗┛┗┛┗┛┗━━━┛┗┛┗┛┗━━┛┗━━┛
// ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
// ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

pragma solidity ^0.8.0;

import {Ownable} from "@openzeppelin/contracts/access/Ownable.sol";
import {ProofOfTransactionLib} from "./lib/ProofOfTransactionLib.sol";

import {IAxiomV0} from "./IAxiom.sol";

contract AnteProofOfTransaction is Ownable {
    address public constant AXIOM_V0 = 0x01d5b501C1fc0121e1411970fb79c322737025c2;
    mapping(address => bool) private _anteContracts;

    constructor() {}

    function addAnteContracts(address[] memory addresses) external onlyOwner {
        for (uint i = 0; i < addresses.length; i++) {
            _anteContracts[addresses[i]] = true;
        }
    }

    function removeAnteContracts(address[] memory addresses) external onlyOwner {
        for (uint i = 0; i < addresses.length; i++) {
            delete _anteContracts[addresses[i]];
        }
    }

    function isAnteContract(address contractAddress) public view returns (bool) {
        return _anteContracts[contractAddress];
    }

    function verifyAnteUpTransaction(bytes memory transactionInclusionProof) external view returns (bool) {
        (
            IAxiomV0.BlockHashWitness memory blockWitness,
            bytes memory header,
            bytes memory txProof,
            bytes memory txKey,
            bytes32 txHash
        ) = abi.decode(transactionInclusionProof, (IAxiomV0.BlockHashWitness, bytes, bytes, bytes, bytes32));
        if (!ProofOfTransactionLib.verifyBlock(blockWitness, header)) {
            return false;
        }
        (bool isValidTxProof, ProofOfTransactionLib.Transaction memory transaction) = ProofOfTransactionLib
            .verifyTransaction(txProof, txKey, header, txHash);
        if (!isValidTxProof) {
            return false;
        }
        if (!isAnteContract(transaction.to)) {
            return false;
        }
        return true;
    }
}

// File: contracts/IAxiom.sol



// SPDX-License-Identifier: GPL-3.0-only
pragma solidity ^0.8.0;

interface IAxiomV0 {
    function historicalRoots(uint32 startBlockNumber) external view returns (bytes32);

    event UpdateEvent(uint32 startBlockNumber, bytes32 prevHash, bytes32 root, uint32 numFinal);
    struct BlockHashWitness {
        uint32 blockNumber;
        bytes32 claimedBlockHash;
        bytes32 prevHash;
        uint32 numFinal;
        bytes32[10] merkleProof;
    }

    function getEmptyHash(uint256 depth) external pure returns (bytes32);

    function isRecentBlockHashValid(uint32 blockNumber, bytes32 claimedBlockHash) external view returns (bool);

    function isBlockHashValid(BlockHashWitness calldata witness) external view returns (bool);
}

// File: contracts/lib/ECVerify.sol



/// SPDX-License-Identifier: GPL-3.0-only
pragma solidity ^0.8.0;

library ECVerify {
    function ecverify(bytes32 hash, uint8 v, bytes32 r, bytes32 s) internal pure returns (address signature_address) {
        // Version of signature should be 27 or 28, but 0 and 1 are also possible
        if (v < 27) {
            v += 27;
        }

        // EIP 155: 2 * chainId + 35
        if (v > 28) {
            v = v % 2 == 1 ? 27 : 28;
        }

        require(v == 27 || v == 28);

        signature_address = ecrecover(hash, v, r, s);

        // ecrecover returns zero on error
        require(signature_address != address(0x0));

        return signature_address;
    }
}

// File: contracts/lib/merkle-trees/MerklePatricia.sol



pragma solidity ^0.8.17;

import "./trie/Node.sol";
import "./trie/Option.sol";
import "./trie/NibbleSlice.sol";
import "./trie/TrieDB.sol";

import "./trie/ethereum/EthereumTrieDB.sol";

// SPDX-License-Identifier: Apache2

/**
 * @title A Merkle Patricia library
 * @author Polytope Labs
 * @dev Use this library to verify merkle patricia proofs
 * @dev refer to research for more info. https://research.polytope.technology/state-(machine)-proofs
 */
library MerklePatricia {
    using NibbleSliceOps for NibbleSlice;
    /// @notice libraries in solidity can only have constant variables
    /// @dev MAX_TRIE_DEPTH, we don't explore deeply nested trie keys.
    uint256 internal constant MAX_TRIE_DEPTH = 50;

    /**
     * @notice Verifies ethereum specific merkle patricia proofs as described by EIP-1188.
     * @param root hash of the merkle patricia trie
     * @param proof a list of proof nodes
     * @param keys a list of keys to verify
     * @return bytes[] a list of values corresponding to the supplied keys.
     */
    function VerifyEthereumProof(
        bytes32 root,
        bytes[] memory proof,
        bytes[] memory keys
    ) internal pure returns (bytes[] memory) {
        bytes[] memory values = new bytes[](keys.length);
        TrieNode[] memory nodes = new TrieNode[](proof.length);
        for (uint256 i = 0; i < proof.length; i++) {
            nodes[i] = TrieNode(keccak256(proof[i]), proof[i]);
        }
        for (uint256 i = 0; i < keys.length; i++) {
            NibbleSlice memory keyNibbles = NibbleSlice(keys[i], 0);
            NodeKind memory node = EthereumTrieDB.decodeNodeKind(TrieDB.get(nodes, root));

            // worst case scenario, so we avoid unbounded loops
            for (uint256 j = 0; j < MAX_TRIE_DEPTH; j++) {
                NodeHandle memory nextNode;

                if (TrieDB.isLeaf(node)) {
                    Leaf memory leaf = EthereumTrieDB.decodeLeaf(node);

                    if (NibbleSliceOps.eq(leaf.key, keyNibbles)) {
                        values[i] = TrieDB.load(nodes, leaf.value);
                    }

                    break;
                } else if (TrieDB.isExtension(node)) {
                    Extension memory extension = EthereumTrieDB.decodeExtension(node);
                    if (NibbleSliceOps.startsWith(keyNibbles, extension.key)) {
                        uint256 len = NibbleSliceOps.len(extension.key);
                        keyNibbles = NibbleSliceOps.mid(keyNibbles, len);
                        nextNode = extension.node;
                    } else {
                        break;
                    }
                } else if (TrieDB.isBranch(node)) {
                    Branch memory branch = EthereumTrieDB.decodeBranch(node);

                    if (NibbleSliceOps.isEmpty(keyNibbles)) {
                        if (Option.isSome(branch.value)) {
                            values[i] = TrieDB.load(nodes, branch.value.value);
                        }

                        break;
                    } else {
                        uint256 childIndex = NibbleSliceOps.at(keyNibbles, 0);

                        NodeHandleOption memory handle = branch.children[childIndex];
                        if (Option.isSome(handle)) {
                            keyNibbles = NibbleSliceOps.mid(keyNibbles, 1);

                            nextNode = handle.value;
                        } else {
                            break;
                        }
                    }
                } else if (TrieDB.isEmpty(node)) {
                    break;
                }

                bytes memory nextNodeEncoded = TrieDB.load(nodes, nextNode);

                node = EthereumTrieDB.decodeNodeKind(nextNodeEncoded);
            }
        }

        return values;
    }
}

// File: contracts/lib/merkle-trees/trie/Bytes.sol



pragma solidity ^0.8.17;

// SPDX-License-Identifier: Apache2

import {Memory} from "./Memory.sol";

struct ByteSlice {
    bytes data;
    uint256 offset;
}

library Bytes {
    uint256 internal constant BYTES_HEADER_SIZE = 32;

    // Checks if two `bytes memory` variables are equal. This is done using hashing,
    // which is much more gas efficient then comparing each byte individually.
    // Equality means that:
    //  - 'self.length == other.length'
    //  - For 'n' in '[0, self.length)', 'self[n] == other[n]'
    function equals(bytes memory self, bytes memory other) internal pure returns (bool equal) {
        if (self.length != other.length) {
            return false;
        }
        uint addr;
        uint addr2;
        assembly {
            addr := add(self, /*BYTES_HEADER_SIZE*/ 32)
            addr2 := add(other, /*BYTES_HEADER_SIZE*/ 32)
        }
        equal = Memory.equals(addr, addr2, self.length);
    }

    function readByte(ByteSlice memory self) internal pure returns (uint8) {
        if (self.offset + 1 > self.data.length) {
            revert("Out of range");
        }

        uint8 b = uint8(self.data[self.offset]);
        self.offset += 1;

        return b;
    }

    // Copies 'len' bytes from 'self' into a new array, starting at the provided 'startIndex'.
    // Returns the new copy.
    // Requires that:
    //  - 'startIndex + len <= self.length'
    // The length of the substring is: 'len'
    function read(ByteSlice memory self, uint256 len) internal pure returns (bytes memory) {
        require(self.offset + len <= self.data.length);
        if (len == 0) {
            return "";
        }
        uint256 addr = Memory.dataPtr(self.data);
        bytes memory slice = Memory.toBytes(addr + self.offset, len);
        self.offset += len;
        return slice;
    }

    // Copies a section of 'self' into a new array, starting at the provided 'startIndex'.
    // Returns the new copy.
    // Requires that 'startIndex <= self.length'
    // The length of the substring is: 'self.length - startIndex'
    function substr(bytes memory self, uint256 startIndex) internal pure returns (bytes memory) {
        require(startIndex <= self.length);
        uint256 len = self.length - startIndex;
        uint256 addr = Memory.dataPtr(self);
        return Memory.toBytes(addr + startIndex, len);
    }

    // Copies 'len' bytes from 'self' into a new array, starting at the provided 'startIndex'.
    // Returns the new copy.
    // Requires that:
    //  - 'startIndex + len <= self.length'
    // The length of the substring is: 'len'
    function substr(bytes memory self, uint256 startIndex, uint256 len) internal pure returns (bytes memory) {
        require(startIndex + len <= self.length);
        if (len == 0) {
            return "";
        }
        uint256 addr = Memory.dataPtr(self);
        return Memory.toBytes(addr + startIndex, len);
    }

    // Combines 'self' and 'other' into a single array.
    // Returns the concatenated arrays:
    //  [self[0], self[1], ... , self[self.length - 1], other[0], other[1], ... , other[other.length - 1]]
    // The length of the new array is 'self.length + other.length'
    function concat(bytes memory self, bytes memory other) internal pure returns (bytes memory) {
        bytes memory ret = new bytes(self.length + other.length);
        uint256 src;
        uint256 srcLen;
        (src, srcLen) = Memory.fromBytes(self);
        uint256 src2;
        uint256 src2Len;
        (src2, src2Len) = Memory.fromBytes(other);
        uint256 dest;
        (dest, ) = Memory.fromBytes(ret);
        uint256 dest2 = dest + srcLen;
        Memory.copy(src, dest, srcLen);
        Memory.copy(src2, dest2, src2Len);
        return ret;
    }

    function toBytes32(bytes memory self) internal pure returns (bytes32 out) {
        require(self.length >= 32, "Bytes:: toBytes32: data is to short.");
        assembly {
            out := mload(add(self, 32))
        }
    }

    function toBytes16(bytes memory self, uint256 offset) internal pure returns (bytes16 out) {
        for (uint i = 0; i < 16; i++) {
            out |= bytes16(bytes1(self[offset + i]) & 0xFF) >> (i * 8);
        }
    }

    function toBytes8(bytes memory self, uint256 offset) internal pure returns (bytes8 out) {
        for (uint i = 0; i < 8; i++) {
            out |= bytes8(bytes1(self[offset + i]) & 0xFF) >> (i * 8);
        }
    }

    function toBytes4(bytes memory self, uint256 offset) internal pure returns (bytes4) {
        bytes4 out;

        for (uint256 i = 0; i < 4; i++) {
            out |= bytes4(self[offset + i] & 0xFF) >> (i * 8);
        }
        return out;
    }

    function toBytes2(bytes memory self, uint256 offset) internal pure returns (bytes2) {
        bytes2 out;

        for (uint256 i = 0; i < 2; i++) {
            out |= bytes2(self[offset + i] & 0xFF) >> (i * 8);
        }
        return out;
    }

    function removeLeadingZero(bytes memory data) internal pure returns (bytes memory) {
        uint length = data.length;

        uint startIndex = 0;
        for (uint i = 0; i < length; i++) {
            if (data[i] != 0) {
                startIndex = i;
                break;
            }
        }

        return substr(data, startIndex);
    }

    function removeEndingZero(bytes memory data) internal pure returns (bytes memory) {
        uint length = data.length;

        uint endIndex = 0;
        for (uint i = length - 1; i >= 0; i--) {
            if (data[i] != 0) {
                endIndex = i;
                break;
            }
        }

        return substr(data, 0, endIndex + 1);
    }

    function reverse(bytes memory inbytes) internal pure returns (bytes memory) {
        uint inlength = inbytes.length;
        bytes memory outbytes = new bytes(inlength);

        for (uint i = 0; i <= inlength - 1; i++) {
            outbytes[i] = inbytes[inlength - i - 1];
        }

        return outbytes;
    }
}

// File: contracts/lib/merkle-trees/trie/ethereum/EthereumTrieDB.sol



// SPDX-License-Identifier: Apache2
pragma solidity ^0.8.17;

import "../Node.sol";
import "../Bytes.sol";
import {NibbleSliceOps, NibbleSlice} from "../NibbleSlice.sol";

import {RLPReader} from "../../../RLPReader.sol";
import {RLPEncode} from "../../../RLPEncode.sol";

library EthereumTrieDB {
    using RLPReader for RLPReader.RLPItem;

    function decodeNodeKind(bytes memory encoded) internal pure returns (NodeKind memory) {
        NodeKind memory node;

        RLPReader.RLPItem memory rlpItem = RLPReader.toRlpItem(encoded);

        if (rlpItem.isList()) {
            if (rlpItem.numItems() == 17) {
                // branch node
                node.isBranch = true;
                node.data = ByteSlice(encoded, 0);
            } else if (rlpItem.numItems() == 2) {
                RLPReader.RLPItem[] memory items = rlpItem.toList();
                bytes memory key = items[0].toBytes();

                if (uint8(key[0]) > 1) {
                    // terminator
                    node.isLeaf = true;
                } else {
                    // extension node
                    node.isExtension = true;
                }
                node.nibbleSize = key.length;
                node.data = ByteSlice(encoded, 0);
            } else {
                revert("Invalid node kind");
            }
        }

        return node;
    }

    function decodeLeaf(NodeKind memory node) internal pure returns (Leaf memory) {
        Leaf memory leaf;
        ByteSlice memory input = node.data;

        RLPReader.RLPItem[] memory items = RLPReader.toRlpItem(input.data).toList();

        bytes memory key = items[0].toBytes();

        bytes memory value = items[1].toBytes();

        leaf.value = NodeHandle({isHash: false, hash: bytes32(0), isInline: true, inLine: value});

        if (uint8(key[0]) % 2 == 1) {
            leaf.key = NibbleSlice(key, 1);
        } else {
            // remove first two bytes

            leaf.key = NibbleSlice(key, 2);
        }

        //leaf.key = NibbleSlice(key, 0);

        return leaf;
    }

    function decodeExtension(NodeKind memory node) internal pure returns (Extension memory) {
        Extension memory extension;
        ByteSlice memory input = node.data;

        RLPReader.RLPItem[] memory items = RLPReader.toRlpItem(input.data).toList();

        bytes memory key = items[0].toBytes();

        if (uint8(key[0]) % 2 == 1) {
            extension.key = NibbleSlice(key, 1);
        } else {
            // remove first two bytes

            extension.key = NibbleSlice(key, 2);
        }

        extension.node = NodeHandle({
            isHash: true,
            hash: bytes32(items[1].toBytes()),
            isInline: false,
            inLine: new bytes(0)
        });

        return extension;
    }

    function decodeBranch(NodeKind memory node) internal pure returns (Branch memory) {
        Branch memory branch;
        ByteSlice memory input = node.data;

        RLPReader.RLPItem[] memory items = RLPReader.toRlpItem(input.data).toList();

        branch.value = NodeHandleOption(
            false,
            NodeHandle({
                isHash: false,
                hash: bytes32(0),
                isInline: true,
                inLine: RLPEncode.encodeBytes(items[16].toBytes())
            })
        );

        for (uint256 i = 0; i < items.length - 1; i++) {
            if (items[i].toBytes().length == 0) {
                continue;
            }

            branch.children[i] = NodeHandleOption(
                true,
                NodeHandle({isHash: true, hash: bytes32(items[i].toBytes()), isInline: false, inLine: new bytes(0)})
            );
        }

        return branch;
    }
}

// File: contracts/lib/merkle-trees/trie/Memory.sol



pragma solidity ^0.8.17;

// SPDX-License-Identifier: Apache2

library Memory {
    uint internal constant WORD_SIZE = 32;

    // Compares the 'len' bytes starting at address 'addr' in memory with the 'len'
    // bytes starting at 'addr2'.
    // Returns 'true' if the bytes are the same, otherwise 'false'.
    function equals(uint addr, uint addr2, uint len) internal pure returns (bool equal) {
        assembly {
            equal := eq(keccak256(addr, len), keccak256(addr2, len))
        }
    }

    // Compares the 'len' bytes starting at address 'addr' in memory with the bytes stored in
    // 'bts'. It is allowed to set 'len' to a lower value then 'bts.length', in which case only
    // the first 'len' bytes will be compared.
    // Requires that 'bts.length >= len'

    function equals(uint addr, uint len, bytes memory bts) internal pure returns (bool equal) {
        require(bts.length >= len);
        uint addr2;
        assembly {
            addr2 := add(bts, /*BYTES_HEADER_SIZE*/ 32)
        }
        return equals(addr, addr2, len);
    }

    // Returns a memory pointer to the data portion of the provided bytes array.
    function dataPtr(bytes memory bts) internal pure returns (uint addr) {
        assembly {
            addr := add(bts, /*BYTES_HEADER_SIZE*/ 32)
        }
    }

    // Creates a 'bytes memory' variable from the memory address 'addr', with the
    // length 'len'. The function will allocate new memory for the bytes array, and
    // the 'len bytes starting at 'addr' will be copied into that new memory.
    function toBytes(uint addr, uint len) internal pure returns (bytes memory bts) {
        bts = new bytes(len);
        uint btsptr;
        assembly {
            btsptr := add(bts, /*BYTES_HEADER_SIZE*/ 32)
        }
        copy(addr, btsptr, len);
    }

    // Copies 'self' into a new 'bytes memory'.
    // Returns the newly created 'bytes memory'
    // The returned bytes will be of length '32'.
    function toBytes(bytes32 self) internal pure returns (bytes memory bts) {
        bts = new bytes(32);
        assembly {
            mstore(add(bts, /*BYTES_HEADER_SIZE*/ 32), self)
        }
    }

    // Copy 'len' bytes from memory address 'src', to address 'dest'.
    // This function does not check the or destination, it only copies
    // the bytes.
    function copy(uint src, uint dest, uint len) internal pure {
        // Copy word-length chunks while possible
        for (; len >= WORD_SIZE; len -= WORD_SIZE) {
            assembly {
                mstore(dest, mload(src))
            }
            dest += WORD_SIZE;
            src += WORD_SIZE;
        }

        // Copy remaining bytes
        uint mask = len == 0
            ? 0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff
            : 256 ** (WORD_SIZE - len) - 1;
        assembly {
            let srcpart := and(mload(src), not(mask))
            let destpart := and(mload(dest), mask)
            mstore(dest, or(destpart, srcpart))
        }
    }

    // This function does the same as 'dataPtr(bytes memory)', but will also return the
    // length of the provided bytes array.
    function fromBytes(bytes memory bts) internal pure returns (uint addr, uint len) {
        len = bts.length;
        assembly {
            addr := add(bts, /*BYTES_HEADER_SIZE*/ 32)
        }
    }
}

// File: contracts/lib/merkle-trees/trie/NibbleSlice.sol



pragma solidity ^0.8.17;

// SPDX-License-Identifier: Apache2

struct NibbleSlice {
    bytes data;
    uint256 offset;
}

library NibbleSliceOps {
    uint256 public constant NIBBLE_PER_BYTE = 2;
    uint256 public constant BITS_PER_NIBBLE = 4;

    function len(NibbleSlice memory nibble) internal pure returns (uint256) {
        return nibble.data.length * NIBBLE_PER_BYTE - nibble.offset;
    }

    function mid(NibbleSlice memory self, uint256 i) internal pure returns (NibbleSlice memory) {
        return NibbleSlice(self.data, self.offset + i);
    }

    function isEmpty(NibbleSlice memory self) internal pure returns (bool) {
        return len(self) == 0;
    }

    function eq(NibbleSlice memory self, NibbleSlice memory other) internal pure returns (bool) {
        return len(self) == len(other) && startsWith(self, other);
    }

    function at(NibbleSlice memory self, uint256 i) internal pure returns (uint256) {
        uint256 ix = (self.offset + i) / NIBBLE_PER_BYTE;
        uint256 pad = (self.offset + i) % NIBBLE_PER_BYTE;
        uint8 data = uint8(self.data[ix]);
        return (pad == 1) ? data & 0x0F : data >> BITS_PER_NIBBLE;
    }

    function startsWith(NibbleSlice memory self, NibbleSlice memory other) internal pure returns (bool) {
        return commonPrefix(self, other) == len(other);
    }

    function commonPrefix(NibbleSlice memory self, NibbleSlice memory other) internal pure returns (uint256) {
        uint256 self_align = self.offset % NIBBLE_PER_BYTE;
        uint256 other_align = other.offset % NIBBLE_PER_BYTE;

        if (self_align == other_align) {
            uint256 self_start = self.offset / NIBBLE_PER_BYTE;
            uint256 other_start = other.offset / NIBBLE_PER_BYTE;
            uint256 first = 0;

            if (self_align != 0) {
                if ((self.data[self_start] & 0x0F) != (other.data[other_start] & 0x0F)) {
                    return 0;
                }
                ++self_start;
                ++other_start;
                ++first;
            }
            bytes memory selfSlice = bytesSlice(self.data, self_start);
            bytes memory otherSlice = bytesSlice(other.data, other_start);
            return biggestDepth(selfSlice, otherSlice) + first;
        } else {
            uint256 s = min(len(self), len(other));
            uint256 i = 0;
            while (i < s) {
                if (at(self, i) != at(other, i)) {
                    break;
                }
                ++i;
            }
            return i;
        }
    }

    function biggestDepth(bytes memory a, bytes memory b) internal pure returns (uint256) {
        uint256 upperBound = min(a.length, b.length);
        uint256 i = 0;
        while (i < upperBound) {
            if (a[i] != b[i]) {
                return i * NIBBLE_PER_BYTE + leftCommon(a[i], b[i]);
            }
            ++i;
        }
        return i * NIBBLE_PER_BYTE;
    }

    function leftCommon(bytes1 a, bytes1 b) internal pure returns (uint256) {
        if (a == b) {
            return 2;
        } else if (uint8(a) & 0xF0 == uint8(b) & 0xF0) {
            return 1;
        } else {
            return 0;
        }
    }

    function bytesSlice(bytes memory _bytes, uint256 _start) internal pure returns (bytes memory) {
        uint256 bytesLength = _bytes.length;
        uint256 _length = bytesLength - _start;
        require(bytesLength >= _start, "slice_outOfBounds");

        bytes memory tempBytes;

        assembly {
            switch iszero(_length)
            case 0 {
                tempBytes := mload(0x40) // load free memory pointer
                let lengthmod := and(_length, 31)

                let mc := add(add(tempBytes, lengthmod), mul(0x20, iszero(lengthmod)))
                let end := add(mc, _length)

                for {
                    let cc := add(add(add(_bytes, lengthmod), mul(0x20, iszero(lengthmod))), _start)
                } lt(mc, end) {
                    mc := add(mc, 0x20)
                    cc := add(cc, 0x20)
                } {
                    mstore(mc, mload(cc))
                }

                mstore(tempBytes, _length)

                mstore(0x40, and(add(mc, 31), not(31)))
            }
            default {
                tempBytes := mload(0x40)
                mstore(tempBytes, 0)

                mstore(0x40, add(tempBytes, 0x20))
            }
        }
        return tempBytes;
    }

    function min(uint256 a, uint256 b) private pure returns (uint256) {
        return (a < b) ? a : b;
    }
}

// File: contracts/lib/merkle-trees/trie/Node.sol



pragma solidity ^0.8.17;

// SPDX-License-Identifier: Apache2

import "./NibbleSlice.sol";
import "./Bytes.sol";

/// This is an enum for the different node types.
struct NodeKind {
    bool isEmpty;
    bool isLeaf;
    bool isHashedLeaf;
    bool isNibbledValueBranch;
    bool isNibbledHashedValueBranch;
    bool isNibbledBranch;
    bool isExtension;
    bool isBranch;
    uint256 nibbleSize;
    ByteSlice data;
}

struct NodeHandle {
    bool isHash;
    bytes32 hash;
    bool isInline;
    bytes inLine;
}

struct Extension {
    NibbleSlice key;
    NodeHandle node;
}

struct Branch {
    NodeHandleOption value;
    NodeHandleOption[16] children;
}

struct NibbledBranch {
    NibbleSlice key;
    NodeHandleOption value;
    NodeHandleOption[16] children;
}

struct ValueOption {
    bool isSome;
    bytes value;
}

struct NodeHandleOption {
    bool isSome;
    NodeHandle value;
}

struct Leaf {
    NibbleSlice key;
    NodeHandle value;
}

struct TrieNode {
    bytes32 hash;
    bytes node;
}

// File: contracts/lib/merkle-trees/trie/Option.sol



pragma solidity ^0.8.17;

import "./Node.sol";

// SPDX-License-Identifier: Apache2

library Option {
    function isSome(ValueOption memory val) internal pure returns (bool) {
        return val.isSome == true;
    }

    function isSome(NodeHandleOption memory val) internal pure returns (bool) {
        return val.isSome == true;
    }
}

// File: contracts/lib/merkle-trees/trie/TrieDB.sol



// SPDX-License-Identifier: Apache2
pragma solidity ^0.8.17;

import "./Node.sol";

library TrieDB {
    function get(TrieNode[] memory nodes, bytes32 hash) internal pure returns (bytes memory) {
        for (uint256 i = 0; i < nodes.length; i++) {
            if (nodes[i].hash == hash) {
                return nodes[i].node;
            }
        }
        revert("Incomplete Proof!");
    }

    function load(TrieNode[] memory nodes, NodeHandle memory node) internal pure returns (bytes memory) {
        if (node.isInline) {
            return node.inLine;
        } else if (node.isHash) {
            return get(nodes, node.hash);
        }

        return bytes("");
    }

    function isNibbledBranch(NodeKind memory node) internal pure returns (bool) {
        return (node.isNibbledBranch || node.isNibbledHashedValueBranch || node.isNibbledValueBranch);
    }

    function isExtension(NodeKind memory node) internal pure returns (bool) {
        return node.isExtension;
    }

    function isBranch(NodeKind memory node) internal pure returns (bool) {
        return node.isBranch;
    }

    function isLeaf(NodeKind memory node) internal pure returns (bool) {
        return (node.isLeaf || node.isHashedLeaf);
    }

    function isEmpty(NodeKind memory node) internal pure returns (bool) {
        return node.isEmpty;
    }

    function isHash(NodeHandle memory node) internal pure returns (bool) {
        return node.isHash;
    }

    function isInline(NodeHandle memory node) internal pure returns (bool) {
        return node.isInline;
    }
}

// File: contracts/lib/ProofOfTransactionLib.sol



/// SPDX-License-Identifier: GPL-3.0-only

pragma solidity ^0.8.0;
import {RLPReader} from "./RLPReader.sol";
import {RLPEncode} from "./RLPEncode.sol";
import {ECVerify} from "./ECVerify.sol";
import {IAxiomV0} from "../IAxiom.sol";
import "./merkle-trees/MerklePatricia.sol";

library ProofOfTransactionLib {
    struct AccessListItem {
        address addressToPreload;
        bytes32[] storageKeysToPreload;
    }

    struct Transaction {
        uint256 txType;
        uint256 chainId;
        uint256 nonce;
        uint256 gasPrice;
        uint256 maxPriorityFeePerGas;
        uint256 maxFeePerGas;
        uint256 gasLimit;
        address to;
        uint256 value;
        bytes data;
        AccessListItem[] accessList;
        uint256 v;
        uint256 r;
        uint256 s;
        bytes32 txHash;
        address from;
    }
    using RLPReader for RLPReader.RLPItem;

    function copyBytes(bytes memory source, uint256 start, uint256 end) internal pure returns (bytes memory) {
        if (end == 0) {
            end = source.length;
        }
        bytes memory result = new bytes(end - start);
        for (uint256 i = start; i < end; i++) {
            result[i - start] = source[i];
        }
        return result;
    }

    function copyBytes(bytes memory source, uint256 start) internal pure returns (bytes memory) {
        return copyBytes(source, start, source.length);
    }

    function getTransactionUnsignedBytesLegacy(Transaction memory transaction) internal pure returns (bytes memory) {
        bytes[] memory items = new bytes[](9);
        items[0] = RLPEncode.encodeUint(transaction.nonce);
        items[1] = RLPEncode.encodeUint(transaction.gasPrice);
        items[2] = RLPEncode.encodeUint(transaction.gasLimit);
        items[3] = RLPEncode.encodeAddress(transaction.to);
        items[4] = RLPEncode.encodeUint(transaction.value);
        items[5] = RLPEncode.encodeBytes(transaction.data);
        items[6] = RLPEncode.encodeUint(1);
        items[7] = RLPEncode.encodeUint(0);
        items[8] = RLPEncode.encodeUint(0);
        bytes memory txSerialized = RLPEncode.encodeList(items);
        return txSerialized;
    }

    function getTransactionUnsignedBytesNonLegacy(Transaction memory transaction) internal pure returns (bytes memory) {
        uint256 itemsCount = transaction.txType == 2 ? 9 : 8;
        bytes[] memory items = new bytes[](itemsCount);
        uint256 itemIndex = 0;
        items[itemIndex++] = RLPEncode.encodeUint(transaction.chainId);
        items[itemIndex++] = RLPEncode.encodeUint(transaction.nonce);
        if (transaction.txType == 2) {
            items[itemIndex++] = RLPEncode.encodeUint(transaction.maxPriorityFeePerGas);
            items[itemIndex++] = RLPEncode.encodeUint(transaction.maxFeePerGas);
        } else {
            items[itemIndex++] = RLPEncode.encodeUint(transaction.gasPrice);
        }
        items[itemIndex++] = RLPEncode.encodeUint(transaction.gasLimit);
        items[itemIndex++] = RLPEncode.encodeAddress(transaction.to);
        items[itemIndex++] = RLPEncode.encodeUint(transaction.value);
        items[itemIndex++] = RLPEncode.encodeBytes(transaction.data);
        bytes[] memory accessListItems = new bytes[](transaction.accessList.length);
        for (uint256 i = 0; i < transaction.accessList.length; i++) {
            bytes[] memory accessListItem = new bytes[](2);
            accessListItem[0] = RLPEncode.encodeAddress(transaction.accessList[i].addressToPreload);
            bytes[] memory storageKeysToPreload = new bytes[](transaction.accessList[i].storageKeysToPreload.length);
            for (uint256 j = 0; j < transaction.accessList[i].storageKeysToPreload.length; j++) {
                storageKeysToPreload[j] = RLPEncode.encodeUint(
                    uint256(transaction.accessList[i].storageKeysToPreload[j])
                );
            }
            accessListItem[1] = RLPEncode.encodeList(storageKeysToPreload);
            accessListItems[i] = RLPEncode.encodeList(accessListItem);
        }
        items[itemIndex++] = RLPEncode.encodeList(accessListItems);
        bytes memory txSerialized = RLPEncode.encodeList(items);
        bytes[] memory enveloped = new bytes[](2);
        enveloped[0] = abi.encodePacked(uint8(transaction.txType));
        enveloped[1] = txSerialized;
        return abi.encodePacked(enveloped[0], enveloped[1]);
    }

    function getTransactionUnsignedBytes(Transaction memory transaction) internal pure returns (bytes memory) {
        if (transaction.txType == 0) {
            return getTransactionUnsignedBytesLegacy(transaction);
        } else if (transaction.txType == 1 || transaction.txType == 2) {
            return getTransactionUnsignedBytesNonLegacy(transaction);
        }
        return new bytes(0);
    }

    function decodeTransactionFromAddress(Transaction memory transaction) internal pure returns (address) {
        return
            ECVerify.ecverify(
                keccak256(getTransactionUnsignedBytes(transaction)),
                uint8(transaction.v),
                bytes32(transaction.r),
                bytes32(transaction.s)
            );
    }

    function decodeLegacyTransactionFromBytes(bytes memory transactionData) internal pure returns (Transaction memory) {
        Transaction memory transaction;
        transaction.txType = 0;
        RLPReader.RLPItem[] memory rlpTx = RLPReader.toRlpItem(transactionData).toList();
        transaction.nonce = rlpTx[0].toUint();
        transaction.gasPrice = rlpTx[1].toUint();
        transaction.gasLimit = rlpTx[2].toUint();
        transaction.to = rlpTx[3].toAddress();
        transaction.value = rlpTx[4].toUint();
        transaction.data = rlpTx[5].toBytes();
        transaction.v = rlpTx[6].toUint();
        transaction.r = rlpTx[7].toUint();
        transaction.s = rlpTx[8].toUint();
        transaction.txHash = keccak256(transactionData);
        transaction.from = decodeTransactionFromAddress(transaction);
        return transaction;
    }

    function decodeAccessListFromRlpItem(
        RLPReader.RLPItem memory rlpItem
    ) internal pure returns (AccessListItem[] memory) {
        RLPReader.RLPItem[] memory accessListItems = rlpItem.toList();
        AccessListItem[] memory accessList = new AccessListItem[](accessListItems.length);
        for (uint256 i = 0; i < accessListItems.length; i++) {
            RLPReader.RLPItem[] memory accessListItem = accessListItems[i].toList();
            accessList[i].addressToPreload = accessListItem[0].toAddress();
            RLPReader.RLPItem[] memory storageKeys = accessListItem[1].toList();
            accessList[i].storageKeysToPreload = new bytes32[](storageKeys.length);
            for (uint256 j = 0; j < storageKeys.length; j++) {
                accessList[i].storageKeysToPreload[j] = bytes32(storageKeys[j].toUint());
            }
        }
        return accessList;
    }

    function decodeEIP1559TransactionFromBytes(
        bytes memory transactionData
    ) internal pure returns (Transaction memory) {
        Transaction memory transaction;
        transaction.txType = uint256(uint8(transactionData[0]));

        RLPReader.RLPItem[] memory rlpTx = RLPReader.toRlpItem(copyBytes(transactionData, 1)).toList();
        transaction.txType = 2;
        transaction.chainId = rlpTx[0].toUint();
        transaction.nonce = rlpTx[1].toUint();
        transaction.maxPriorityFeePerGas = rlpTx[2].toUint();
        transaction.maxFeePerGas = rlpTx[3].toUint();
        transaction.gasLimit = rlpTx[4].toUint();
        transaction.to = rlpTx[5].toAddress();
        transaction.value = rlpTx[6].toUint();
        transaction.data = rlpTx[7].toBytes();
        transaction.accessList = decodeAccessListFromRlpItem(rlpTx[8]);
        transaction.v = rlpTx[9].toUint();
        transaction.r = rlpTx[10].toUint();
        transaction.s = rlpTx[11].toUint();
        transaction.txHash = keccak256(transactionData);
        transaction.from = decodeTransactionFromAddress(transaction);
        return transaction;
    }

    function decodeEIP2930TransactionFromBytes(
        bytes memory transactionData
    ) internal pure returns (Transaction memory) {
        Transaction memory transaction;
        transaction.txType = uint256(uint8(transactionData[0]));

        RLPReader.RLPItem[] memory rlpTx = RLPReader.toRlpItem(copyBytes(transactionData, 1)).toList();
        transaction.txType = 1;
        transaction.chainId = rlpTx[0].toUint();
        transaction.nonce = rlpTx[1].toUint();
        transaction.gasPrice = rlpTx[2].toUint();
        transaction.gasLimit = rlpTx[3].toUint();
        transaction.to = rlpTx[4].toAddress();
        transaction.value = rlpTx[5].toUint();
        transaction.data = rlpTx[6].toBytes();
        transaction.accessList = decodeAccessListFromRlpItem(rlpTx[7]);
        transaction.v = rlpTx[8].toUint();
        transaction.r = rlpTx[9].toUint();
        transaction.s = rlpTx[10].toUint();
        transaction.txHash = keccak256(transactionData);
        transaction.from = decodeTransactionFromAddress(transaction);
        return transaction;
    }

    function decodeTransactionFromProof(
        bytes memory rlpEncodedTransactionBytes
    ) internal pure returns (Transaction memory) {
        uint256 transactionType = 0;
        transactionType = uint256(uint8(rlpEncodedTransactionBytes[0]));
        if (transactionType == 2) {
            return decodeEIP1559TransactionFromBytes(rlpEncodedTransactionBytes);
        }
        if (transactionType == 1) {
            return decodeEIP2930TransactionFromBytes(rlpEncodedTransactionBytes);
        }
        return decodeLegacyTransactionFromBytes(rlpEncodedTransactionBytes);
    }

    function getTransactionsTrieRootFromHeader(bytes memory header) internal pure returns (bytes32) {
        RLPReader.RLPItem[] memory headerRLP = RLPReader.toRlpItem(header).toList();
        return bytes32(headerRLP[4].toUint());
    }

    function verifyBlock(IAxiomV0.BlockHashWitness memory witness, bytes memory header) internal view returns (bool) {
        address axiomAddress = 0x01d5b501C1fc0121e1411970fb79c322737025c2;
        if (witness.blockNumber >= 17034240) {
            axiomAddress = 0xF990f9CB1A0aa6B51c0720a6f4cAe577d7AbD86A;
        }
        if (witness.blockNumber == 0) {
            return false;
        }
        if (witness.blockNumber < block.number - 256) {
            try IAxiomV0(axiomAddress).isBlockHashValid(witness) returns (bool blockValidation) {
                if (!blockValidation) {
                    return false;
                }
            } catch {
                return false;
            }
        } else {
            try IAxiomV0(axiomAddress).isRecentBlockHashValid(witness.blockNumber, witness.claimedBlockHash) returns (
                bool blockValidation
            ) {
                if (!blockValidation) {
                    return false;
                }
            } catch {
                return false;
            }
        }
        bytes32 blockHashFromHeader = keccak256(header);
        if (blockHashFromHeader != witness.claimedBlockHash) {
            return false;
        }
        return true;
    }

    function emptyTransaction() internal pure returns (Transaction memory) {
        Transaction memory transaction;
        transaction.txType = 0;
        transaction.chainId = 0;
        transaction.nonce = 0;
        transaction.gasPrice = 0;
        transaction.gasLimit = 0;
        transaction.to = address(0);
        transaction.value = 0;
        transaction.data = new bytes(0);
        transaction.accessList = new AccessListItem[](0);
        transaction.v = 0;
        transaction.r = 0;
        transaction.s = 0;
        transaction.txHash = bytes32(0);
        transaction.from = address(0);
        return transaction;
    }

    function verifyTransaction(
        bytes memory txProof,
        bytes memory key,
        bytes memory header,
        bytes32 transactionHash
    ) internal pure returns (bool verification, Transaction memory) {
        bytes32 transactionsRoot = getTransactionsTrieRootFromHeader(header);

        bytes[] memory keysToVerify = new bytes[](1);
        keysToVerify[0] = key;
        bytes[] memory proof = abi.decode(txProof, (bytes[]));
        bytes[] memory verifiedValuesForKeys = MerklePatricia.VerifyEthereumProof(
            transactionsRoot,
            proof,
            keysToVerify
        );

        if (verifiedValuesForKeys.length != 1) {
            return (false, emptyTransaction());
        } else {
            if (transactionHash != keccak256(verifiedValuesForKeys[0])) {
                return (false, emptyTransaction());
            }
        }

        return (true, ProofOfTransactionLib.decodeTransactionFromProof(verifiedValuesForKeys[0]));
    }
}

// File: contracts/lib/RLPEncode.sol



/// SPDX-License-Identifier: GPL-3.0-only
pragma solidity ^0.8.0;

/**
 * @title RLPEncode
 * @dev A simple RLP encoding library.
 * @author Bakaoh
 */
library RLPEncode {
    /*
     * Internal functions
     */

    /**
     * @dev RLP encodes a byte string.
     * @param self The byte string to encode.
     * @return The RLP encoded string in bytes.
     */
    function encodeBytes(bytes memory self) internal pure returns (bytes memory) {
        bytes memory encoded;
        if (self.length == 1 && uint8(self[0]) < 128) {
            encoded = self;
        } else {
            encoded = concat(encodeLength(self.length, 128), self);
        }
        return encoded;
    }

    /**
     * @dev RLP encodes a list of RLP encoded byte byte strings.
     * @param self The list of RLP encoded byte strings.
     * @return The RLP encoded list of items in bytes.
     */
    function encodeList(bytes[] memory self) internal pure returns (bytes memory) {
        bytes memory list = flatten(self);
        return concat(encodeLength(list.length, 192), list);
    }

    /**
     * @dev RLP encodes a string.
     * @param self The string to encode.
     * @return The RLP encoded string in bytes.
     */
    function encodeString(string memory self) internal pure returns (bytes memory) {
        return encodeBytes(bytes(self));
    }

    /**
     * @dev RLP encodes an address.
     * @param self The address to encode.
     * @return The RLP encoded address in bytes.
     */
    function encodeAddress(address self) internal pure returns (bytes memory) {
        bytes memory inputBytes;
        assembly {
            let m := mload(0x40)
            mstore(add(m, 20), xor(0x140000000000000000000000000000000000000000, self))
            mstore(0x40, add(m, 52))
            inputBytes := m
        }
        return encodeBytes(inputBytes);
    }

    /**
     * @dev RLP encodes a uint.
     * @param self The uint to encode.
     * @return The RLP encoded uint in bytes.
     */
    function encodeUint(uint self) internal pure returns (bytes memory) {
        return encodeBytes(toBinary(self));
    }

    /**
     * @dev RLP encodes an int.
     * @param self The int to encode.
     * @return The RLP encoded int in bytes.
     */
    function encodeInt(int self) internal pure returns (bytes memory) {
        return encodeUint(uint(self));
    }

    /**
     * @dev RLP encodes a bool.
     * @param self The bool to encode.
     * @return The RLP encoded bool in bytes.
     */
    function encodeBool(bool self) internal pure returns (bytes memory) {
        bytes memory encoded = new bytes(1);
        encoded[0] = (self ? bytes1(0x01) : bytes1(0x80));
        return encoded;
    }

    /*
     * Private functions
     */

    /**
     * @dev Encode the first byte, followed by the `len` in binary form if `length` is more than 55.
     * @param len The length of the string or the payload.
     * @param offset 128 if item is string, 192 if item is list.
     * @return RLP encoded bytes.
     */
    function encodeLength(uint len, uint offset) private pure returns (bytes memory) {
        bytes memory encoded;
        if (len < 56) {
            encoded = new bytes(1);
            encoded[0] = bytes32(len + offset)[31];
        } else {
            uint lenLen;
            uint i = 1;
            while (len / i != 0) {
                lenLen++;
                i *= 256;
            }

            encoded = new bytes(lenLen + 1);
            encoded[0] = bytes32(lenLen + offset + 55)[31];
            for (i = 1; i <= lenLen; i++) {
                encoded[i] = bytes32((len / (256 ** (lenLen - i))) % 256)[31];
            }
        }
        return encoded;
    }

    /**
     * @dev Encode integer in big endian binary form with no leading zeroes.
     * @notice TODO: This should be optimized with assembly to save gas costs.
     * @param _x The integer to encode.
     * @return RLP encoded bytes.
     */
    function toBinary(uint _x) private pure returns (bytes memory) {
        bytes memory b = new bytes(32);
        assembly {
            mstore(add(b, 32), _x)
        }
        uint i;
        for (i = 0; i < 32; i++) {
            if (b[i] != 0) {
                break;
            }
        }
        bytes memory res = new bytes(32 - i);
        for (uint j = 0; j < res.length; j++) {
            res[j] = b[i++];
        }
        return res;
    }

    /**
     * @dev Copies a piece of memory to another location.
     * @notice From: https://github.com/Arachnid/solidity-stringutils/blob/master/src/strings.sol.
     * @param _dest Destination location.
     * @param _src Source location.
     * @param _len Length of memory to copy.
     */
    function memcpy(uint _dest, uint _src, uint _len) private pure {
        uint dest = _dest;
        uint src = _src;
        uint len = _len;

        for (; len >= 32; len -= 32) {
            assembly {
                mstore(dest, mload(src))
            }
            dest += 32;
            src += 32;
        }

        uint mask = 256 ** (32 - len) - 1;
        assembly {
            let srcpart := and(mload(src), not(mask))
            let destpart := and(mload(dest), mask)
            mstore(dest, or(destpart, srcpart))
        }
    }

    /**
     * @dev Flattens a list of byte strings into one byte string.
     * @notice From: https://github.com/sammayo/solidity-rlp-encoder/blob/master/RLPEncode.sol.
     * @param _list List of byte strings to flatten.
     * @return The flattened byte string.
     */
    function flatten(bytes[] memory _list) private pure returns (bytes memory) {
        if (_list.length == 0) {
            return new bytes(0);
        }

        uint len;
        uint i;
        for (i = 0; i < _list.length; i++) {
            len += _list[i].length;
        }

        bytes memory flattened = new bytes(len);
        uint flattenedPtr;
        assembly {
            flattenedPtr := add(flattened, 0x20)
        }

        for (i = 0; i < _list.length; i++) {
            bytes memory item = _list[i];

            uint listPtr;
            assembly {
                listPtr := add(item, 0x20)
            }

            memcpy(flattenedPtr, listPtr, item.length);
            flattenedPtr += _list[i].length;
        }

        return flattened;
    }

    /**
     * @dev Concatenates two bytes.
     * @notice From: https://github.com/GNSPS/solidity-bytes-utils/blob/master/contracts/BytesLib.sol.
     * @param _preBytes First byte string.
     * @param _postBytes Second byte string.
     * @return Both byte string combined.
     */
    function concat(bytes memory _preBytes, bytes memory _postBytes) private pure returns (bytes memory) {
        bytes memory tempBytes;

        assembly {
            tempBytes := mload(0x40)

            let length := mload(_preBytes)
            mstore(tempBytes, length)

            let mc := add(tempBytes, 0x20)
            let end := add(mc, length)

            for {
                let cc := add(_preBytes, 0x20)
            } lt(mc, end) {
                mc := add(mc, 0x20)
                cc := add(cc, 0x20)
            } {
                mstore(mc, mload(cc))
            }

            length := mload(_postBytes)
            mstore(tempBytes, add(length, mload(tempBytes)))

            mc := end
            end := add(mc, length)

            for {
                let cc := add(_postBytes, 0x20)
            } lt(mc, end) {
                mc := add(mc, 0x20)
                cc := add(cc, 0x20)
            } {
                mstore(mc, mload(cc))
            }

            mstore(0x40, and(add(add(end, iszero(add(length, mload(_preBytes)))), 31), not(31)))
        }

        return tempBytes;
    }
}

// File: contracts/lib/RLPReader.sol



// SPDX-License-Identifier: Apache-2.0
pragma solidity ^0.8.0;

library RLPReader {
    uint8 constant STRING_SHORT_START = 0x80;
    uint8 constant STRING_LONG_START = 0xb8;
    uint8 constant LIST_SHORT_START = 0xc0;
    uint8 constant LIST_LONG_START = 0xf8;
    uint8 constant WORD_SIZE = 32;

    struct RLPItem {
        uint256 len;
        uint256 memPtr;
    }

    struct Iterator {
        RLPItem item; // Item that's being iterated over.
        uint256 nextPtr; // Position of the next item in the list.
    }

    /*
     * @dev Returns the next element in the iteration. Reverts if it has not next element.
     * @param self The iterator.
     * @return The next element in the iteration.
     */
    function next(Iterator memory self) internal pure returns (RLPItem memory) {
        require(hasNext(self));

        uint256 ptr = self.nextPtr;
        uint256 itemLength = _itemLength(ptr);
        self.nextPtr = ptr + itemLength;

        return RLPItem(itemLength, ptr);
    }

    /*
     * @dev Returns true if the iteration has more elements.
     * @param self The iterator.
     * @return true if the iteration has more elements.
     */
    function hasNext(Iterator memory self) internal pure returns (bool) {
        RLPItem memory item = self.item;
        return self.nextPtr < item.memPtr + item.len;
    }

    /*
     * @param item RLP encoded bytes
     */
    function toRlpItem(bytes memory item) internal pure returns (RLPItem memory) {
        uint256 memPtr;
        assembly {
            memPtr := add(item, 0x20)
        }

        return RLPItem(item.length, memPtr);
    }

    /*
     * @dev Create an iterator. Reverts if item is not a list.
     * @param self The RLP item.
     * @return An 'Iterator' over the item.
     */
    function iterator(RLPItem memory self) internal pure returns (Iterator memory) {
        require(isList(self));

        uint256 ptr = self.memPtr + _payloadOffset(self.memPtr);
        return Iterator(self, ptr);
    }

    /*
     * @param the RLP item.
     */
    function rlpLen(RLPItem memory item) internal pure returns (uint256) {
        return item.len;
    }

    /*
     * @param the RLP item.
     * @return (memPtr, len) pair: location of the item's payload in memory.
     */
    function payloadLocation(RLPItem memory item) internal pure returns (uint256, uint256) {
        uint256 offset = _payloadOffset(item.memPtr);
        uint256 memPtr = item.memPtr + offset;
        uint256 len = item.len - offset; // data length
        return (memPtr, len);
    }

    /*
     * @param the RLP item.
     */
    function payloadLen(RLPItem memory item) internal pure returns (uint256) {
        (, uint256 len) = payloadLocation(item);
        return len;
    }

    /*
     * @param the RLP item containing the encoded list.
     */
    function toList(RLPItem memory item) internal pure returns (RLPItem[] memory) {
        require(isList(item));

        uint256 items = numItems(item);
        RLPItem[] memory result = new RLPItem[](items);

        uint256 memPtr = item.memPtr + _payloadOffset(item.memPtr);
        uint256 dataLen;
        for (uint256 i = 0; i < items; i++) {
            dataLen = _itemLength(memPtr);
            result[i] = RLPItem(dataLen, memPtr);
            memPtr = memPtr + dataLen;
        }

        return result;
    }

    // @return indicator whether encoded payload is a list. negate this function call for isData.
    function isList(RLPItem memory item) internal pure returns (bool) {
        if (item.len == 0) return false;

        uint8 byte0;
        uint256 memPtr = item.memPtr;
        assembly {
            byte0 := byte(0, mload(memPtr))
        }

        if (byte0 < LIST_SHORT_START) return false;
        return true;
    }

    /*
     * @dev A cheaper version of keccak256(toRlpBytes(item)) that avoids copying memory.
     * @return keccak256 hash of RLP encoded bytes.
     */
    function rlpBytesKeccak256(RLPItem memory item) internal pure returns (bytes32) {
        uint256 ptr = item.memPtr;
        uint256 len = item.len;
        bytes32 result;
        assembly {
            result := keccak256(ptr, len)
        }
        return result;
    }

    /*
     * @dev A cheaper version of keccak256(toBytes(item)) that avoids copying memory.
     * @return keccak256 hash of the item payload.
     */
    function payloadKeccak256(RLPItem memory item) internal pure returns (bytes32) {
        (uint256 memPtr, uint256 len) = payloadLocation(item);
        bytes32 result;
        assembly {
            result := keccak256(memPtr, len)
        }
        return result;
    }

    /** RLPItem conversions into data types **/

    // @returns raw rlp encoding in bytes
    function toRlpBytes(RLPItem memory item) internal pure returns (bytes memory) {
        bytes memory result = new bytes(item.len);
        if (result.length == 0) return result;

        uint256 ptr;
        assembly {
            ptr := add(0x20, result)
        }

        copy(item.memPtr, ptr, item.len);
        return result;
    }

    // any non-zero byte except "0x80" is considered true
    function toBoolean(RLPItem memory item) internal pure returns (bool) {
        require(item.len == 1);
        uint256 result;
        uint256 memPtr = item.memPtr;
        assembly {
            result := byte(0, mload(memPtr))
        }

        // SEE Github Issue #5.
        // Summary: Most commonly used RLP libraries (i.e Geth) will encode
        // "0" as "0x80" instead of as "0". We handle this edge case explicitly
        // here.
        if (result == 0 || result == STRING_SHORT_START) {
            return false;
        } else {
            return true;
        }
    }

    function toAddress(RLPItem memory item) internal pure returns (address) {
        // 1 byte for the length prefix
        require(item.len == 21);

        return address(uint160(toUint(item)));
    }

    function toUint(RLPItem memory item) internal pure returns (uint256) {
        require(item.len > 0 && item.len <= 33);

        (uint256 memPtr, uint256 len) = payloadLocation(item);

        uint256 result;
        assembly {
            result := mload(memPtr)

            // shift to the correct location if neccesary
            if lt(len, 32) {
                result := div(result, exp(256, sub(32, len)))
            }
        }

        return result;
    }

    // enforces 32 byte length
    function toUintStrict(RLPItem memory item) internal pure returns (uint256) {
        // one byte prefix
        require(item.len == 33);

        uint256 result;
        uint256 memPtr = item.memPtr + 1;
        assembly {
            result := mload(memPtr)
        }

        return result;
    }

    function toBytes(RLPItem memory item) internal pure returns (bytes memory) {
        //require(item.len > 0);

        if (item.len == 0) return new bytes(0);
        (uint256 memPtr, uint256 len) = payloadLocation(item);
        bytes memory result = new bytes(len);

        uint256 destPtr;
        assembly {
            destPtr := add(0x20, result)
        }

        copy(memPtr, destPtr, len);
        return result;
    }

    /*
     * Private Helpers
     */

    // @return number of payload items inside an encoded list.
    function numItems(RLPItem memory item) internal pure returns (uint256) {
        if (item.len == 0) return 0;

        uint256 count = 0;
        uint256 currPtr = item.memPtr + _payloadOffset(item.memPtr);
        uint256 endPtr = item.memPtr + item.len;
        while (currPtr < endPtr) {
            currPtr = currPtr + _itemLength(currPtr); // skip over an item
            count++;
        }

        return count;
    }

    // @return entire rlp item byte length
    function _itemLength(uint256 memPtr) private pure returns (uint256) {
        uint256 itemLen;
        uint256 byte0;
        assembly {
            byte0 := byte(0, mload(memPtr))
        }

        if (byte0 < STRING_SHORT_START) {
            itemLen = 1;
        } else if (byte0 < STRING_LONG_START) {
            itemLen = byte0 - STRING_SHORT_START + 1;
        } else if (byte0 < LIST_SHORT_START) {
            assembly {
                let byteLen := sub(byte0, 0xb7) // # of bytes the actual length is
                memPtr := add(memPtr, 1) // skip over the first byte

                /* 32 byte word size */
                let dataLen := div(mload(memPtr), exp(256, sub(32, byteLen))) // right shifting to get the len
                itemLen := add(dataLen, add(byteLen, 1))
            }
        } else if (byte0 < LIST_LONG_START) {
            itemLen = byte0 - LIST_SHORT_START + 1;
        } else {
            assembly {
                let byteLen := sub(byte0, 0xf7)
                memPtr := add(memPtr, 1)

                let dataLen := div(mload(memPtr), exp(256, sub(32, byteLen))) // right shifting to the correct length
                itemLen := add(dataLen, add(byteLen, 1))
            }
        }

        return itemLen;
    }

    // @return number of bytes until the data
    function _payloadOffset(uint256 memPtr) private pure returns (uint256) {
        uint256 byte0;
        assembly {
            byte0 := byte(0, mload(memPtr))
        }

        if (byte0 < STRING_SHORT_START) {
            return 0;
        } else if (byte0 < STRING_LONG_START || (byte0 >= LIST_SHORT_START && byte0 < LIST_LONG_START)) {
            return 1;
        } else if (byte0 < LIST_SHORT_START) {
            // being explicit
            return byte0 - (STRING_LONG_START - 1) + 1;
        } else {
            return byte0 - (LIST_LONG_START - 1) + 1;
        }
    }

    /*
     * @param src Pointer to source
     * @param dest Pointer to destination
     * @param len Amount of memory to copy from the source
     */
    function copy(uint256 src, uint256 dest, uint256 len) private pure {
        if (len == 0) return;

        // copy as many word sizes as possible
        for (; len >= WORD_SIZE; len -= WORD_SIZE) {
            assembly {
                mstore(dest, mload(src))
            }

            src += WORD_SIZE;
            dest += WORD_SIZE;
        }

        if (len > 0) {
            // left over bytes. Mask is used to remove unwanted bytes from the word
            uint256 mask = 256 ** (WORD_SIZE - len) - 1;
            assembly {
                let srcpart := and(mload(src), not(mask)) // zero out src
                let destpart := and(mload(dest), mask) // retrieve the bytes
                mstore(dest, or(destpart, srcpart))
            }
        }
    }
}