Contract Source Code (Solidity Standard Json-Input format)

IDE

• Blockscan IDE

More Options

• Is this a proxy?
• Similar
• Sol2Uml
• Submit Audit
• Compare

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

import {StatelessMmr} from "solidity-mmr/lib/StatelessMmr.sol";
import {Lib_SecureMerkleTrie as SecureMerkleTrie} from "../lib/external/trie/Lib_SecureMerkleTrie.sol";
import {Lib_RLPReader as RLPReader} from "../lib/external/rlp/Lib_RLPReader.sol";

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

import {Types} from "../lib/Types.sol";
import {Bitmap16} from "../lib/Bitmap16.sol";
import {EVMHeaderRLP} from "../lib/EVMHeaderRLP.sol";
import {NullableStorageSlot} from "../lib/NullableStorageSlot.sol";

contract FactsRegistry {
    using EVMHeaderRLP for bytes;
    using Bitmap16 for uint16;

    using RLPReader for bytes;
    using RLPReader for RLPReader.RLPItem;

    event AccountProven(address account, uint256 blockNumber, uint256 nonce, uint256 balance, bytes32 codeHash, bytes32 storageHash);
    event StorageSlotProven(address account, uint256 blockNumber, bytes32 slot, bytes32 slotValue);

    uint8 private constant ACCOUNT_NONCE_INDEX = 0;
    uint8 private constant ACCOUNT_BALANCE_INDEX = 1;
    uint8 private constant ACCOUNT_STORAGE_ROOT_INDEX = 2;
    uint8 private constant ACCOUNT_CODE_HASH_INDEX = 3;

    bytes32 private constant EMPTY_TRIE_ROOT_HASH = 0x56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421;
    bytes32 private constant EMPTY_CODE_HASH = 0xc5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a470;

    HeadersProcessor public immutable headersProcessor;

    mapping(address => mapping(uint256 => mapping(Types.AccountFields => bytes32))) internal _accountField;
    // address => block number => slot => value
    mapping(address => mapping(uint256 => mapping(bytes32 => bytes32))) internal _accountStorageSlotValues;

    constructor(address _headersProcessor) {
        headersProcessor = HeadersProcessor(_headersProcessor);
    }

    function proveAccount(address account, uint16 accountFieldsToSave, Types.BlockHeaderProof calldata headerProof, bytes calldata accountTrieProof) external {
        // Verify the proof and decode the account fields
        (uint256 nonce, uint256 accountBalance, bytes32 codeHash, bytes32 storageRoot) = verifyAccount(account, headerProof, accountTrieProof);

        // Save the desired account properties to the storage
        if (accountFieldsToSave.readBitAtIndexFromRight(0)) {
            uint256 nonceNullable = NullableStorageSlot.toNullable(nonce);
            _accountField[account][headerProof.blockNumber][Types.AccountFields.NONCE] = bytes32(nonceNullable);
        }

        if (accountFieldsToSave.readBitAtIndexFromRight(1)) {
            uint256 accountBalanceNullable = NullableStorageSlot.toNullable(accountBalance);
            _accountField[account][headerProof.blockNumber][Types.AccountFields.BALANCE] = bytes32(accountBalanceNullable);
        }

        if (accountFieldsToSave.readBitAtIndexFromRight(2)) {
            uint256 codeHashNullable = NullableStorageSlot.toNullable(uint256(codeHash));
            _accountField[account][headerProof.blockNumber][Types.AccountFields.CODE_HASH] = bytes32(codeHashNullable);
        }

        if (accountFieldsToSave.readBitAtIndexFromRight(3)) {
            uint256 storageRootNullable = NullableStorageSlot.toNullable(uint256(storageRoot));
            _accountField[account][headerProof.blockNumber][Types.AccountFields.STORAGE_ROOT] = bytes32(storageRootNullable);
        }

        emit AccountProven(account, headerProof.blockNumber, nonce, accountBalance, codeHash, storageRoot);
    }

    function proveStorage(address account, uint256 blockNumber, bytes32 slot, bytes calldata storageSlotTrieProof) external {
        // Verify the proof and decode the slot value
        uint256 slotValueNullable = NullableStorageSlot.toNullable(uint256(verifyStorage(account, blockNumber, slot, storageSlotTrieProof)));
        _accountStorageSlotValues[account][blockNumber][slot] = bytes32(slotValueNullable);
        emit StorageSlotProven(account, blockNumber, slot, bytes32(NullableStorageSlot.fromNullable(slotValueNullable)));
    }

    function verifyAccount(
        address account,
        Types.BlockHeaderProof calldata headerProof,
        bytes calldata accountTrieProof
    ) public view returns (uint256 nonce, uint256 accountBalance, bytes32 codeHash, bytes32 storageRoot) {
        // Ensure provided header is a valid one by making sure it is committed in the HeadersStore MMR
        _verifyAccumulatedHeaderProof(headerProof);

        // Verify the account state proof
        bytes32 stateRoot = headerProof.provenBlockHeader.getStateRoot();

        (bool doesAccountExist, bytes memory accountRLP) = SecureMerkleTrie.get(abi.encodePacked(account), accountTrieProof, stateRoot);
        // Decode the account fields
        (nonce, accountBalance, storageRoot, codeHash) = _decodeAccountFields(doesAccountExist, accountRLP);
    }

    function verifyStorage(address account, uint256 blockNumber, bytes32 slot, bytes calldata storageSlotTrieProof) public view returns (bytes32 slotValue) {
        bytes32 storageRootRaw = _accountField[account][blockNumber][Types.AccountFields.STORAGE_ROOT];
        // Convert from nullable
        bytes32 storageRoot = bytes32(NullableStorageSlot.fromNullable(uint256(storageRootRaw)));

        (, bytes memory slotValueRLP) = SecureMerkleTrie.get(abi.encode(slot), storageSlotTrieProof, storageRoot);

        slotValue = slotValueRLP.toRLPItem().readBytes32();
    }

    function accountField(address account, uint256 blockNumber, Types.AccountFields field) external view returns (bytes32) {
        bytes32 valueRaw = _accountField[account][blockNumber][field];
        // If value is null revert
        if (NullableStorageSlot.isNull(uint256(valueRaw))) {
            revert("ERR_VALUE_IS_NULL");
        }
        return bytes32(NullableStorageSlot.fromNullable(uint256(valueRaw)));
    }

    function accountStorageSlotValues(address account, uint256 blockNumber, bytes32 slot) external view returns (bytes32) {
        bytes32 valueRaw = _accountStorageSlotValues[account][blockNumber][slot];
        // If value is null revert
        if (NullableStorageSlot.isNull(uint256(valueRaw))) {
            revert("ERR_VALUE_IS_NULL");
        }
        return bytes32(NullableStorageSlot.fromNullable(uint256(valueRaw)));
    }

    function _verifyAccumulatedHeaderProof(Types.BlockHeaderProof memory proof) internal view {
        bytes32 mmrRoot = headersProcessor.getMMRRoot(proof.treeId, proof.mmrTreeSize);
        require(mmrRoot != bytes32(0), "ERR_EMPTY_MMR_ROOT");

        bytes32 blockHeaderHash = keccak256(proof.provenBlockHeader);

        StatelessMmr.verifyProof(proof.blockProofLeafIndex, blockHeaderHash, proof.mmrElementInclusionProof, proof.mmrPeaks, proof.mmrTreeSize, mmrRoot);

        uint256 actualBlockNumber = proof.provenBlockHeader.getBlockNumber();
        require(actualBlockNumber == proof.blockNumber, "ERR_INVALID_BLOCK_NUMBER");
    }

    function _decodeAccountFields(bool doesAccountExist, bytes memory accountRLP) internal pure returns (uint256 nonce, uint256 balance, bytes32 storageRoot, bytes32 codeHash) {
        if (!doesAccountExist) {
            return (0, 0, EMPTY_TRIE_ROOT_HASH, EMPTY_CODE_HASH);
        }

        RLPReader.RLPItem[] memory accountFields = accountRLP.toRLPItem().readList();

        nonce = accountFields[ACCOUNT_NONCE_INDEX].readUint256();
        balance = accountFields[ACCOUNT_BALANCE_INDEX].readUint256();
        codeHash = accountFields[ACCOUNT_CODE_HASH_INDEX].readBytes32();
        storageRoot = accountFields[ACCOUNT_STORAGE_ROOT_INDEX].readBytes32();
    }
}

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

import "./StatelessMmrHelpers.sol";

///    _____       _ _     _ _ _           __  __ __  __ _____
///   / ____|     | (_)   | (_) |         |  \/  |  \/  |  __ \
///  | (___   ___ | |_  __| |_| |_ _   _  | \  / | \  / | |__) |
///   \___ \ / _ \| | |/ _` | | __| | | | | |\/| | |\/| |  _  /
///   ____) | (_) | | | (_| | | |_| |_| | | |  | | |  | | | \ \
///  |_____/ \___/|_|_|\__,_|_|\__|\__, | |_|  |_|_|  |_|_|  \_\
///                                 __/ |
///                                |___/

///
/// @title StatelessMmr -- A Solidity implementation of Merkle Mountain Range
/// @author Herodotus Ltd
/// @notice Library for appending bytes32 values (i.e., acting as an accumulator)
///         and verifying Merkle inclusion proofs
///
library StatelessMmr {
    error InvalidProof();
    error IndexOutOfBounds();
    error InvalidRoot();
    error InvalidPeaksArrayLength();

    ///
    /// @notice Append a new element to the MMR
    /// @param elem Element to append
    /// @param peaks The latest peaks
    /// @param lastElementsCount The latest elements count
    /// @param lastRoot  The latest root
    /// @return The updated elements count and the new root hash of the tree
    ///
    function append(
        bytes32 elem,
        bytes32[] memory peaks,
        uint lastElementsCount,
        bytes32 lastRoot
    ) internal pure returns (uint, bytes32) {
        (uint updatedElementsCount, bytes32 newRoot, ) = doAppend(
            elem,
            peaks,
            lastElementsCount,
            lastRoot
        );

        return (updatedElementsCount, newRoot);
    }

    ///
    /// Same as `append` but also returns the updated peaks
    ///
    function appendWithPeaksRetrieval(
        bytes32 elem,
        bytes32[] memory peaks,
        uint lastElementsCount,
        bytes32 lastRoot
    ) internal pure returns (uint, bytes32, bytes32[] memory) {
        (
            uint updatedElementsCount,
            bytes32 newRoot,
            bytes32[] memory updatedPeaks
        ) = doAppend(elem, peaks, lastElementsCount, lastRoot);

        return (updatedElementsCount, newRoot, updatedPeaks);
    }

    ///
    /// @param elems Elements to append (in order)
    /// @param peaks The latest peaks
    /// @param lastElementsCount The latest elements count
    /// @param lastRoot The latest tree root hash
    /// @return The newest elements count and the newest tree root hash
    ///
    function multiAppend(
        bytes32[] memory elems,
        bytes32[] memory peaks,
        uint lastElementsCount,
        bytes32 lastRoot
    ) internal pure returns (uint, bytes32) {
        uint elementsCount = lastElementsCount;
        bytes32 root = lastRoot;
        bytes32[] memory updatedPeaks = peaks;

        for (uint i = 0; i < elems.length; ++i) {
            (elementsCount, root, updatedPeaks) = appendWithPeaksRetrieval(
                elems[i],
                updatedPeaks,
                elementsCount,
                root
            );
        }
        return (elementsCount, root);
    }

    ///
    /// Same as `multiAppend` but also returns the updated peaks
    ///
    function multiAppendWithPeaksRetrieval(
        bytes32[] memory elems,
        bytes32[] memory peaks,
        uint lastElementsCount,
        bytes32 lastRoot
    ) internal pure returns (uint, bytes32, bytes32[] memory) {
        uint elementsCount = lastElementsCount;
        bytes32 root = lastRoot;
        bytes32[] memory updatedPeaks = peaks;

        for (uint i = 0; i < elems.length; ++i) {
            (elementsCount, root, updatedPeaks) = appendWithPeaksRetrieval(
                elems[i],
                updatedPeaks,
                elementsCount,
                root
            );
        }
        return (elementsCount, root, updatedPeaks);
    }

    ///
    /// @notice Efficient version of `multiAppend` that takes in all the precomputed peaks
    /// @param elems Elements to append (in order)
    /// @param allPeaks All the precomputed peaks computed off-chain (more gas efficient)
    /// @param lastElementsCount The latest elements count
    /// @param lastRoot The latest tree root hash
    /// @return The newest elements count and the newest tree root hash
    ///
    function multiAppendWithPrecomputedPeaks(
        bytes32[] memory elems,
        bytes32[][] memory allPeaks,
        uint lastElementsCount,
        bytes32 lastRoot
    ) internal pure returns (uint, bytes32) {
        uint elementsCount = lastElementsCount;
        bytes32 root = lastRoot;

        for (uint i = 0; i < elems.length; ++i) {
            (elementsCount, root) = append(
                elems[i],
                allPeaks[i],
                elementsCount,
                root
            );
        }
        return (elementsCount, root);
    }

    ///
    /// @notice Verify a Merkle inclusion proof
    /// @dev Reverts if the proof is invalid
    /// @param proof The Merkle inclusion proof
    /// @param peaks The peaks at the time of inclusion
    /// @param elementsCount The element count at the time of inclusion
    /// @param root The tree root hash at the time of inclusion
    ///
    function verifyProof(
        uint index,
        bytes32 value,
        bytes32[] memory proof,
        bytes32[] memory peaks,
        uint elementsCount,
        bytes32 root
    ) internal pure {
        if (index > elementsCount) {
            revert IndexOutOfBounds();
        }
        bytes32 computedRoot = computeRoot(peaks, bytes32(elementsCount));
        if (computedRoot != root) {
            revert InvalidRoot();
        }

        bytes32 topPeak = getProofTopPeak(0, value, index, proof);

        bool isValid = StatelessMmrHelpers.arrayContains(topPeak, peaks);
        if (!isValid) {
            revert InvalidProof();
        }
    }

    ///   _    _      _                   ______                _   _
    ///  | |  | |    | |                 |  ____|              | | (_)
    ///  | |__| | ___| |_ __   ___ _ __  | |__ _   _ _ __   ___| |_ _  ___  _ __  ___
    ///  |  __  |/ _ \ | '_ \ / _ \ '__| |  __| | | | '_ \ / __| __| |/ _ \| '_ \/ __|
    ///  | |  | |  __/ | |_) |  __/ |    | |  | |_| | | | | (__| |_| | (_) | | | \__ \
    ///  |_|  |_|\___|_| .__/ \___|_|    |_|   \__,_|_| |_|\___|\__|_|\___/|_| |_|___/
    ///                | |
    ///                |_|

    ///
    /// @notice Computes the root hash of the given peaks and tree size
    /// @param peaks Peaks to compute the root from
    /// @param size Tree size to to compute the root from
    /// @return The root hash of the following peaks and tree size
    ///
    function computeRoot(
        bytes32[] memory peaks,
        bytes32 size
    ) internal pure returns (bytes32) {
        bytes32 baggedPeaks = bagPeaks(peaks);
        return keccak256(abi.encode(size, baggedPeaks));
    }

    ///
    /// @notice Bag the peaks: recursively hashing peaks together to form a single hash
    /// @param peaks The peaks to bag
    /// @return The bagged peaks
    ///
    function bagPeaks(bytes32[] memory peaks) internal pure returns (bytes32) {
        if (peaks.length < 1) {
            revert InvalidPeaksArrayLength();
        }
        if (peaks.length == 1) {
            return peaks[0];
        }

        uint len = peaks.length;
        bytes32 root0 = keccak256(abi.encode(peaks[len - 2], peaks[len - 1]));
        bytes32[] memory reversedPeaks = new bytes32[](len - 2);
        for (uint i = 0; i < len - 2; i++) {
            reversedPeaks[i] = peaks[len - 3 - i];
        }

        bytes32 bags = root0;
        for (uint i = 0; i < reversedPeaks.length; i++) {
            bags = keccak256(abi.encode(reversedPeaks[i], bags));
        }
        return bags;
    }

    function doAppend(
        bytes32 elem,
        bytes32[] memory peaks,
        uint lastElementsCount,
        bytes32 lastRoot
    ) internal pure returns (uint, bytes32, bytes32[] memory) {
        uint elementsCount = lastElementsCount + 1;
        if (lastElementsCount == 0) {
            bytes32 root0 = elem;
            bytes32 firstRoot = keccak256(abi.encode(uint(1), root0));
            bytes32[] memory newPeaks = new bytes32[](1);
            newPeaks[0] = root0;
            return (elementsCount, firstRoot, newPeaks);
        }

        uint leafCount = StatelessMmrHelpers.mmrSizeToLeafCount(
            elementsCount - 1
        );
        uint numberOfPeaks = StatelessMmrHelpers.countOnes(leafCount);
        if (peaks.length != numberOfPeaks) {
            revert InvalidPeaksArrayLength();
        }

        bytes32 computedRoot = computeRoot(peaks, bytes32(lastElementsCount));
        if (computedRoot != lastRoot) {
            revert InvalidRoot();
        }

        bytes32[] memory appendPeaks = StatelessMmrHelpers.newArrWithElem(
            peaks,
            elem
        );

        uint appendNoMerges = StatelessMmrHelpers.leafCountToAppendNoMerges(leafCount);
        bytes32[] memory updatedPeaks = appendPerformMerging(
            appendPeaks,
            appendNoMerges
        );

        uint updatedElementsCount = elementsCount + appendNoMerges;

        bytes32 newRoot = computeRoot(
            updatedPeaks,
            bytes32(updatedElementsCount)
        );
        return (updatedElementsCount, newRoot, updatedPeaks);
    }

    function appendPerformMerging(
        bytes32[] memory peaks,
        uint noMerges
    ) internal pure returns (bytes32[] memory) {
        uint peaksLen = peaks.length;
        bytes32 accHash = peaks[peaksLen - 1];
        for (uint i = 0; i < noMerges; i++) {
            bytes32 hash = peaks[peaksLen - i - 2];
            accHash = keccak256(abi.encode(hash, accHash));
        }
        bytes32[] memory newPeaks = new bytes32[](peaksLen - noMerges);
        for (uint i = 0; i < peaksLen - noMerges - 1; i++) {
            newPeaks[i] = peaks[i];
        }
        newPeaks[peaksLen - noMerges - 1] = accHash;

        return newPeaks;
    }

    function getProofTopPeak(
        uint height,
        bytes32 hash,
        uint elementsCount,
        bytes32[] memory proof
    ) internal pure returns (bytes32) {
        uint leafIndex = StatelessMmrHelpers.mmrIndexToLeafIndex(elementsCount);
        for (uint i = 0; i < proof.length; ++i) {
            bytes32 currentSibling = proof[i];

            bool isRightChild = leafIndex % 2 == 1;
            if (isRightChild) {
                bytes32 hashed = keccak256(abi.encode(currentSibling, hash));
                elementsCount += 1;

                hash = hashed;
            } else {
                bytes32 hashed = keccak256(abi.encode(hash, currentSibling));
                elementsCount += 2 << height;

                hash = hashed;
            }
            ++height;
            leafIndex /= 2;
        }
        return hash;
    }
}

// SPDX-License-Identifier: MIT
pragma solidity >0.5.0 <=0.8.24;
pragma experimental ABIEncoderV2;

/* Library Imports */
import {Lib_MerkleTrie} from "./Lib_MerkleTrie.sol";

/**
 * @title Lib_SecureMerkleTrie
 */
library Lib_SecureMerkleTrie {
    /**********************
     * Internal Functions *
     **********************/

    /**
     * @notice Verifies a proof that a given key/value pair is present in the
     * Merkle trie.
     * @param _key Key of the node to search for, as a hex string.
     * @param _value Value of the node to search for, as a hex string.
     * @param _proof Merkle trie inclusion proof for the desired node. Unlike
     * traditional Merkle trees, this proof is executed top-down and consists
     * of a list of RLP-encoded nodes that make a path down to the target node.
     * @param _root Known root of the Merkle trie. Used to verify that the
     * included proof is correctly constructed.
     * @return _verified `true` if the k/v pair exists in the trie, `false` otherwise.
     */
    function verifyInclusionProof(bytes memory _key, bytes memory _value, bytes memory _proof, bytes32 _root) internal pure returns (bool _verified) {
        bytes memory key = _getSecureKey(_key);
        return Lib_MerkleTrie.verifyInclusionProof(key, _value, _proof, _root);
    }

    /**
     * @notice Verifies a proof that a given key is *not* present in
     * the Merkle trie.
     * @param _key Key of the node to search for, as a hex string.
     * @param _proof Merkle trie inclusion proof for the node *nearest* the
     * target node.
     * @param _root Known root of the Merkle trie. Used to verify that the
     * included proof is correctly constructed.
     * @return _verified `true` if the key is not present in the trie, `false` otherwise.
     */
    function verifyExclusionProof(bytes memory _key, bytes memory _proof, bytes32 _root) internal pure returns (bool _verified) {
        bytes memory key = _getSecureKey(_key);
        return Lib_MerkleTrie.verifyExclusionProof(key, _proof, _root);
    }

    /**
     * @notice Updates a Merkle trie and returns a new root hash.
     * @param _key Key of the node to update, as a hex string.
     * @param _value Value of the node to update, as a hex string.
     * @param _proof Merkle trie inclusion proof for the node *nearest* the
     * target node. If the key exists, we can simply update the value.
     * Otherwise, we need to modify the trie to handle the new k/v pair.
     * @param _root Known root of the Merkle trie. Used to verify that the
     * included proof is correctly constructed.
     * @return _updatedRoot Root hash of the newly constructed trie.
     */
    function update(bytes memory _key, bytes memory _value, bytes memory _proof, bytes32 _root) internal pure returns (bytes32 _updatedRoot) {
        bytes memory key = _getSecureKey(_key);
        return Lib_MerkleTrie.update(key, _value, _proof, _root);
    }

    /**
     * @notice Retrieves the value associated with a given key.
     * @param _key Key to search for, as hex bytes.
     * @param _proof Merkle trie inclusion proof for the key.
     * @param _root Known root of the Merkle trie.
     * @return _exists Whether or not the key exists.
     * @return _value Value of the key if it exists.
     */
    function get(bytes memory _key, bytes memory _proof, bytes32 _root) internal pure returns (bool _exists, bytes memory _value) {
        bytes memory key = _getSecureKey(_key);
        return Lib_MerkleTrie.get(key, _proof, _root);
    }

    /**
     * Computes the root hash for a trie with a single node.
     * @param _key Key for the single node.
     * @param _value Value for the single node.
     * @return _updatedRoot Hash of the trie.
     */
    function getSingleNodeRootHash(bytes memory _key, bytes memory _value) internal pure returns (bytes32 _updatedRoot) {
        bytes memory key = _getSecureKey(_key);
        return Lib_MerkleTrie.getSingleNodeRootHash(key, _value);
    }

    /*********************
     * Private Functions *
     *********************/

    /**
     * Computes the secure counterpart to a key.
     * @param _key Key to get a secure key from.
     * @return _secureKey Secure version of the key.
     */
    function _getSecureKey(bytes memory _key) private pure returns (bytes memory _secureKey) {
        return abi.encodePacked(keccak256(_key));
    }
}

// SPDX-License-Identifier: MIT
pragma solidity >0.5.0 <=0.8.24;

/**
 * @title Lib_RLPReader
 * @dev Adapted from "RLPReader" by Hamdi Allam ([email protected]).
 */
library Lib_RLPReader {
    /*************
     * Constants *
     *************/

    uint256 internal constant MAX_LIST_LENGTH = 32;

    /*********
     * Enums *
     *********/

    enum RLPItemType {
        DATA_ITEM,
        LIST_ITEM
    }

    /***********
     * Structs *
     ***********/

    struct RLPItem {
        uint256 length;
        uint256 ptr;
    }

    /**********************
     * Internal Functions *
     **********************/

    /**
     * Converts bytes to a reference to memory position and length.
     * @param _in Input bytes to convert.
     * @return Output memory reference.
     */
    function toRLPItem(bytes memory _in) internal pure returns (RLPItem memory) {
        uint256 ptr;
        assembly {
            ptr := add(_in, 32)
        }

        return RLPItem({length: _in.length, ptr: ptr});
    }

    /**
     * Reads an RLP list value into a list of RLP items.
     * @param _in RLP list value.
     * @return Decoded RLP list items.
     */
    function readList(RLPItem memory _in) internal pure returns (RLPItem[] memory) {
        (uint256 listOffset, , RLPItemType itemType) = _decodeLength(_in);

        require(itemType == RLPItemType.LIST_ITEM, "Invalid RLP list value.");

        // Solidity in-memory arrays can't be increased in size, but *can* be decreased in size by
        // writing to the length. Since we can't know the number of RLP items without looping over
        // the entire input, we'd have to loop twice to accurately size this array. It's easier to
        // simply set a reasonable maximum list length and decrease the size before we finish.
        RLPItem[] memory out = new RLPItem[](MAX_LIST_LENGTH);

        uint256 itemCount = 0;
        uint256 offset = listOffset;
        while (offset < _in.length) {
            require(itemCount < MAX_LIST_LENGTH, "Provided RLP list exceeds max list length.");

            (uint256 itemOffset, uint256 itemLength, ) = _decodeLength(RLPItem({length: _in.length - offset, ptr: _in.ptr + offset}));

            out[itemCount] = RLPItem({length: itemLength + itemOffset, ptr: _in.ptr + offset});

            itemCount += 1;
            offset += itemOffset + itemLength;
        }

        // Decrease the array size to match the actual item count.
        assembly {
            mstore(out, itemCount)
        }

        return out;
    }

    /**
     * Reads an RLP list value into a list of RLP items.
     * @param _in RLP list value.
     * @return Decoded RLP list items.
     */
    function readList(bytes memory _in) internal pure returns (RLPItem[] memory) {
        return readList(toRLPItem(_in));
    }

    /**
     * Reads an RLP bytes value into bytes.
     * @param _in RLP bytes value.
     * @return Decoded bytes.
     */
    function readBytes(RLPItem memory _in) internal pure returns (bytes memory) {
        (uint256 itemOffset, uint256 itemLength, RLPItemType itemType) = _decodeLength(_in);

        require(itemType == RLPItemType.DATA_ITEM, "Invalid RLP bytes value.");

        return _copy(_in.ptr, itemOffset, itemLength);
    }

    /**
     * Reads an RLP bytes value into bytes.
     * @param _in RLP bytes value.
     * @return Decoded bytes.
     */
    function readBytes(bytes memory _in) internal pure returns (bytes memory) {
        return readBytes(toRLPItem(_in));
    }

    /**
     * Reads an RLP string value into a string.
     * @param _in RLP string value.
     * @return Decoded string.
     */
    function readString(RLPItem memory _in) internal pure returns (string memory) {
        return string(readBytes(_in));
    }

    /**
     * Reads an RLP string value into a string.
     * @param _in RLP string value.
     * @return Decoded string.
     */
    function readString(bytes memory _in) internal pure returns (string memory) {
        return readString(toRLPItem(_in));
    }

    /**
     * Reads an RLP bytes32 value into a bytes32.
     * @param _in RLP bytes32 value.
     * @return Decoded bytes32.
     */
    function readBytes32(RLPItem memory _in) internal pure returns (bytes32) {
        require(_in.length <= 33, "Invalid RLP bytes32 value.");

        (uint256 itemOffset, uint256 itemLength, RLPItemType itemType) = _decodeLength(_in);

        require(itemType == RLPItemType.DATA_ITEM, "Invalid RLP bytes32 value.");

        uint256 ptr = _in.ptr + itemOffset;
        bytes32 out;
        assembly {
            out := mload(ptr)

            // Shift the bytes over to match the item size.
            if lt(itemLength, 32) {
                out := div(out, exp(256, sub(32, itemLength)))
            }
        }

        return out;
    }

    /**
     * Reads an RLP bytes32 value into a bytes32.
     * @param _in RLP bytes32 value.
     * @return Decoded bytes32.
     */
    function readBytes32(bytes memory _in) internal pure returns (bytes32) {
        return readBytes32(toRLPItem(_in));
    }

    /**
     * Reads an RLP uint256 value into a uint256.
     * @param _in RLP uint256 value.
     * @return Decoded uint256.
     */
    function readUint256(RLPItem memory _in) internal pure returns (uint256) {
        return uint256(readBytes32(_in));
    }

    /**
     * Reads an RLP uint256 value into a uint256.
     * @param _in RLP uint256 value.
     * @return Decoded uint256.
     */
    function readUint256(bytes memory _in) internal pure returns (uint256) {
        return readUint256(toRLPItem(_in));
    }

    /**
     * Reads an RLP bool value into a bool.
     * @param _in RLP bool value.
     * @return Decoded bool.
     */
    function readBool(RLPItem memory _in) internal pure returns (bool) {
        require(_in.length == 1, "Invalid RLP boolean value.");

        uint256 ptr = _in.ptr;
        uint256 out;
        assembly {
            out := byte(0, mload(ptr))
        }

        require(out == 0 || out == 1, "Lib_RLPReader: Invalid RLP boolean value, must be 0 or 1");

        return out != 0;
    }

    /**
     * Reads an RLP bool value into a bool.
     * @param _in RLP bool value.
     * @return Decoded bool.
     */
    function readBool(bytes memory _in) internal pure returns (bool) {
        return readBool(toRLPItem(_in));
    }

    /**
     * Reads an RLP address value into a address.
     * @param _in RLP address value.
     * @return Decoded address.
     */
    function readAddress(RLPItem memory _in) internal pure returns (address) {
        if (_in.length == 1) {
            return address(0);
        }

        require(_in.length == 21, "Invalid RLP address value.");

        return address(uint160(readUint256(_in)));
    }

    /**
     * Reads an RLP address value into a address.
     * @param _in RLP address value.
     * @return Decoded address.
     */
    function readAddress(bytes memory _in) internal pure returns (address) {
        return readAddress(toRLPItem(_in));
    }

    /**
     * Reads the raw bytes of an RLP item.
     * @param _in RLP item to read.
     * @return Raw RLP bytes.
     */
    function readRawBytes(RLPItem memory _in) internal pure returns (bytes memory) {
        return _copy(_in);
    }

    /*********************
     * Private Functions *
     *********************/

    /**
     * Decodes the length of an RLP item.
     * @param _in RLP item to decode.
     * @return Offset of the encoded data.
     * @return Length of the encoded data.
     * @return RLP item type (LIST_ITEM or DATA_ITEM).
     */
    function _decodeLength(RLPItem memory _in) private pure returns (uint256, uint256, RLPItemType) {
        unchecked {
            require(_in.length > 0, "RLP item cannot be null.");

            uint256 ptr = _in.ptr;
            uint256 prefix;
            assembly {
                prefix := byte(0, mload(ptr))
            }

            if (prefix <= 0x7f) {
                // Single byte.

                return (0, 1, RLPItemType.DATA_ITEM);
            } else if (prefix <= 0xb7) {
                // Short string.

                uint256 strLen = prefix - 0x80;

                require(_in.length > strLen, "Invalid RLP short string.");

                return (1, strLen, RLPItemType.DATA_ITEM);
            } else if (prefix <= 0xbf) {
                // Long string.
                uint256 lenOfStrLen = prefix - 0xb7;

                require(_in.length > lenOfStrLen, "Invalid RLP long string length.");

                uint256 strLen;
                assembly {
                    // Pick out the string length.
                    strLen := div(mload(add(ptr, 1)), exp(256, sub(32, lenOfStrLen)))
                }

                require(_in.length > lenOfStrLen + strLen, "Invalid RLP long string.");

                return (1 + lenOfStrLen, strLen, RLPItemType.DATA_ITEM);
            } else if (prefix <= 0xf7) {
                // Short list.
                uint256 listLen = prefix - 0xc0;

                require(_in.length > listLen, "Invalid RLP short list.");

                return (1, listLen, RLPItemType.LIST_ITEM);
            } else {
                // Long list.
                uint256 lenOfListLen = prefix - 0xf7;

                require(_in.length > lenOfListLen, "Invalid RLP long list length.");

                uint256 listLen;
                assembly {
                    // Pick out the list length.
                    listLen := div(mload(add(ptr, 1)), exp(256, sub(32, lenOfListLen)))
                }

                require(_in.length > lenOfListLen + listLen, "Invalid RLP long list.");

                return (1 + lenOfListLen, listLen, RLPItemType.LIST_ITEM);
            }
        }
    }

    /**
     * Copies the bytes from a memory location.
     * @param _src Pointer to the location to read from.
     * @param _offset Offset to start reading from.
     * @param _length Number of bytes to read.
     * @return Copied bytes.
     */
    function _copy(uint256 _src, uint256 _offset, uint256 _length) private pure returns (bytes memory) {
        unchecked {
            bytes memory out = new bytes(_length);
            if (out.length == 0) {
                return out;
            }

            uint256 src = _src + _offset;
            uint256 dest;
            assembly {
                dest := add(out, 32)
            }

            // Copy over as many complete words as we can.
            for (uint256 i = 0; i < _length / 32; i++) {
                assembly {
                    mstore(dest, mload(src))
                }

                src += 32;
                dest += 32;
            }

            // Pick out the remaining bytes.
            uint256 mask = 256 ** (32 - (_length % 32)) - 1;
            assembly {
                mstore(dest, or(and(mload(src), not(mask)), and(mload(dest), mask)))
            }

            return out;
        }
    }

    /**
     * Copies an RLP item into bytes.
     * @param _in RLP item to copy.
     * @return Copied bytes.
     */
    function _copy(RLPItem memory _in) private pure returns (bytes memory) {
        return _copy(_in.ptr, 0, _in.length);
    }
}

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

import {EVMHeaderRLP} from "../lib/EVMHeaderRLP.sol";

import {StatelessMmr} from "solidity-mmr/lib/StatelessMmr.sol";

interface IHeadersProcessor {
    function mmrsCount() external view returns (uint256);

    function receivedParentHashes(uint256 blockNumber) external view returns (bytes32);

    function receiveParentHash(uint256 blockNumber, bytes32 parentHash) external;

    function createBranchFromMessage(bytes32 mmrRoot, uint256 mmrSize, uint256 aggregatorId) external;

    function createBranchSingleElement(
        uint256 fromMmrId,
        uint256 mmrSize,
        uint256 elementIndex,
        bytes32 initialBlockHash,
        bytes32[] calldata mmrPeaks,
        bytes32[] calldata mmrInclusionProof
    ) external;

    function createBranchFromExisting(uint256 mmrId, uint256 mmrSize) external;

    function processBlocksBatch(bool isReferenceHeaderAccumulated, uint256 mmrId, bytes calldata ctx, bytes[] calldata headersSerialized) external;

    function getMMRRoot(uint256 mmrId, uint256 mmrSize) external view returns (bytes32);

    function getLatestMMRRoot(uint256 mmrId) external view returns (bytes32);

    function getLatestMMRSize(uint256 mmrId) external view returns (uint256);
}

contract HeadersProcessor is IHeadersProcessor {
    using EVMHeaderRLP for bytes;

    /// @notice This struct represents a Merkle Mountain Range accumulating provably valid block hash
    /// @dev each MMR is mapped to a unique ID also referred to as mmrId
    struct MMRInfo {
        /// @notice latestSize represents the latest size of the MMR
        uint256 latestSize;
        /// @notice mmrSizeToRoot maps the MMR size to the MMR root, that way we have automatic versioning
        mapping(uint256 => bytes32) mmrSizeToRoot;
    }

    /// @notice emitted when a new MMR is created from a single element
    /// @param newMMRId the ID of the new MMR
    /// @param newMMRRoot the root of the new MMR
    /// @param newMMRSize the size of the new MMR
    /// @param detachedFromMmrId the ID of the MMR from which the new MMR was created
    /// @param detachedFromMmrIdAtSize the size of the MMR from which the new MMR was created
    event BranchCreatedFromElement(uint256 newMMRId, bytes32 newMMRRoot, uint256 newMMRSize, uint256 detachedFromMmrId, uint256 detachedFromMmrIdAtSize);

    /// @notice emitted when a new MMR is created from an existing MMR
    /// @param newMMRId the ID of the new MMR
    /// @param detachedFromRoot the root of the MMR from which the new MMR was created
    /// @param detachedFromMmrId the ID of the MMR from which the new MMR was created
    /// @param detachedFromMmrIdAtSize the size of the MMR from which the new MMR was created
    event BranchCreatedClone(uint256 newMMRId, bytes32 detachedFromRoot, uint256 detachedFromMmrId, uint256 detachedFromMmrIdAtSize);

    /// @notice emitted when a new MMR is created from an L1 message
    /// @param newMMRId the ID of the new MMR
    /// @param mmrSize the size of the new MMR
    /// @param mmrRoot the root of the new MMR
    /// @param aggregatorId the ID of the L1 aggregator that is the origin of the message content
    event BranchCreatedFromL1Message(uint256 newMMRId, uint256 mmrSize, bytes32 mmrRoot, uint256 aggregatorId);

    /// @notice emitted when a new batch of blocks is processed
    /// @param startBlockHigh the block number of the first block in the batch
    /// @param endBlockLow the block number of the last block in the batch
    /// @param newMMRRoot the root of the new MMR
    /// @param newMMRSize the size of the new MMR
    /// @param updatedMMRId the ID of the MMR that was updated
    event ProcessedBatch(uint256 startBlockHigh, uint256 endBlockLow, bytes32 newMMRRoot, uint256 newMMRSize, uint256 updatedMMRId);

    /// @notice address of the MessagesInbox contract allowed to forward messages to this contract
    address public immutable messagesInboxAddr;

    /// @notice mapping of block number to the block parent hash
    mapping(uint256 => bytes32) public receivedParentHashes;

    /// @dev counter for the number of MMRs created
    uint256 public mmrsCount;

    /// @dev mapping of MMR ID to MMR info
    mapping(uint256 => MMRInfo) public mmrs;

    event ParentHashReceived(uint256 blockNumber, bytes32 parentHash);

    /// @param _messagesInboxAddr address of the MessagesInbox contract allowed to forward messages to this contract
    constructor(address _messagesInboxAddr) {
        messagesInboxAddr = _messagesInboxAddr;
    }

    /// @notice modifier to ensure the caller is the MessagesInbox contract
    modifier onlyMessagesInbox() {
        require(msg.sender == messagesInboxAddr, "ERR_ONLY_INBOX");
        _;
    }

    /// @notice Called when a message is sent from L1 to L2
    /// @notice saves the parent hash of the block number in the contract storage
    function receiveParentHash(uint256 blockNumber, bytes32 parentHash) external onlyMessagesInbox {
        receivedParentHashes[blockNumber] = parentHash;
        emit ParentHashReceived(blockNumber, parentHash);
    }

    /// @notice Creates a new branch from an L1 message, the sent MMR info comes from an L1 aggregator
    /// @param mmrRoot the root of the MMR
    /// @param mmrSize the size of the MMR
    /// @param aggregatorId the ID of the L1 aggregator that is the origin of the message content
    function createBranchFromMessage(bytes32 mmrRoot, uint256 mmrSize, uint256 aggregatorId) external onlyMessagesInbox {
        // 1. Assign an ID to the new MMR
        uint256 currentMMRsCount = mmrsCount;
        uint256 newMMRId = currentMMRsCount + 1;

        // 2. Create a new MMR
        mmrs[newMMRId].latestSize = mmrSize;
        mmrs[newMMRId].mmrSizeToRoot[mmrSize] = mmrRoot;

        // 3. Update the MMRs count
        mmrsCount++;

        // 4. Emit the event
        emit BranchCreatedFromL1Message(newMMRId, mmrSize, mmrRoot, aggregatorId);
    }

    /// @notice Creates a new branch with only one element taken from an existing MMR
    /// @param fromMmrId the ID of the MMR from which the new MMR will be created
    /// @param mmrSize the size of the MMR from which the new MMR will be created
    /// @param elementIndex the index of the element to take from the existing MMR
    /// @param initialBlockHash the block hash of the first block in the new MMR
    /// @param mmrPeaks the peaks of the new MMR
    /// @param mmrInclusionProof the inclusion proof of the element in the existing MMR
    function createBranchSingleElement(
        uint256 fromMmrId,
        uint256 mmrSize,
        uint256 elementIndex,
        bytes32 initialBlockHash,
        bytes32[] calldata mmrPeaks,
        bytes32[] calldata mmrInclusionProof
    ) external {
        // Verify that the given MMR at the given size has a non zero root
        bytes32 root = mmrs[fromMmrId].mmrSizeToRoot[mmrSize];
        require(root != bytes32(0), "ERR_MMR_DOES_NOT_EXIST");

        // Verify that the given element is in the MMR
        StatelessMmr.verifyProof(elementIndex, initialBlockHash, mmrInclusionProof, mmrPeaks, mmrSize, root);

        // === Create a new MMR === //

        // 1. Assign an ID to the new MMR
        uint256 currentMMRsCount = mmrsCount;
        uint256 newMMRId = currentMMRsCount + 1;

        // 2. Create a new MMR
        bytes32[] memory emptyPeaks = new bytes32[](0);
        (uint256 newMMRSize, bytes32 newMMRRoot) = StatelessMmr.append(initialBlockHash, emptyPeaks, 0, bytes32(0));

        // 3. Update the MMRs mapping
        mmrs[newMMRId].latestSize = newMMRSize;
        mmrs[newMMRId].mmrSizeToRoot[newMMRSize] = newMMRRoot;

        // 4. Update the MMRs count
        mmrsCount++;

        // 5. Emit the event
        emit BranchCreatedFromElement(newMMRId, newMMRRoot, newMMRSize, fromMmrId, mmrSize);
    }

    /// @notice Creates a new branch from an existing MMR, effectively cloning it
    /// @param mmrId the ID of the MMR from which the new MMR will be created
    /// @param mmrSize size at which the MMR will be copied
    function createBranchFromExisting(uint256 mmrId, uint256 mmrSize) external {
        // 1. Load existing MMR data
        bytes32 root = mmrs[mmrId].mmrSizeToRoot[mmrSize];

        // 2. Ensure the given MMR is not empty
        require(root != bytes32(0), "ERR_MMR_DOES_NOT_EXIST");

        // 3. Assign an ID to the new MMR
        uint256 currentMMRsCount = mmrsCount;
        uint256 newMMRId = currentMMRsCount + 1;

        // 4. Copy the existing MMR data to the new MMR
        mmrs[newMMRId].latestSize = mmrSize;
        mmrs[newMMRId].mmrSizeToRoot[mmrSize] = root;

        // 5. Update the MMRs count
        mmrsCount++;

        // 6. Emit the event
        emit BranchCreatedClone(newMMRId, root, mmrId, mmrSize);
    }

    /// @notice Processes a batch of blocks
    /// @param isReferenceHeaderAccumulated whether the reference header is accumulated or not
    /// @param mmrId the ID of the MMR to update
    /// @param ctx the context of the batch, encoded as bytes.
    ///    If the reference header is accumulated, the context contains the MMR proof and peaks.
    ///    If the reference header is not accumulated, the context contains the block number of the reference header and the MMR peaks.
    /// @param headersSerialized the serialized headers of the batch
    function processBlocksBatch(bool isReferenceHeaderAccumulated, uint256 mmrId, bytes calldata ctx, bytes[] calldata headersSerialized) external {
        require(headersSerialized.length > 0, "ERR_EMPTY_BATCH");
        require(mmrs[mmrId].latestSize != 0, "ERR_MMR_DOES_NOT_EXIST");

        uint256 firstBlockInBatch;
        uint256 newMMRSize;
        bytes32 newMMRRoot;

        if (isReferenceHeaderAccumulated) {
            (firstBlockInBatch, newMMRSize, newMMRRoot) = _processBlocksBatchAccumulated(mmrId, ctx, headersSerialized);
        } else {
            (firstBlockInBatch, newMMRSize, newMMRRoot) = _processBlocksBatchNotAccumulated(mmrId, ctx, headersSerialized);
        }
        emit ProcessedBatch(firstBlockInBatch, firstBlockInBatch - headersSerialized.length + 1, newMMRRoot, newMMRSize, mmrId);
    }

    /// ========================= Internal functions ========================= //

    function _processBlocksBatchAccumulated(
        uint256 treeId,
        bytes memory ctx,
        bytes[] memory headersSerialized
    ) internal returns (uint256 firstBlockInBatch, uint256 newMMRSize, bytes32 newMMRRoot) {
        (uint256 referenceProofLeafIndex, bytes32[] memory referenceProof, bytes32[] memory mmrPeaks, bytes memory referenceHeaderSerialized) = abi.decode(
            ctx,
            (uint256, bytes32[], bytes32[], bytes)
        );

        _validateParentBlockAndProofIntegrity(treeId, referenceProofLeafIndex, referenceProof, mmrPeaks, referenceHeaderSerialized);

        require(referenceHeaderSerialized.getParentHash() == keccak256(headersSerialized[0]), "ERR_NON_CONSECUTIVE_ELEMENT");

        bytes32[] memory headersHashes = new bytes32[](headersSerialized.length);
        headersHashes[0] = referenceHeaderSerialized.getParentHash();
        for (uint256 i = 1; i < headersSerialized.length; ++i) {
            bytes32 parentHash = headersSerialized[i - 1].getParentHash();
            require(_isHeaderValid(parentHash, headersSerialized[i]), "ERR_INVALID_CHAIN_ELEMENT");
            headersHashes[i] = parentHash;
        }
        (newMMRSize, newMMRRoot) = _appendMultipleBlockhashesToMMR(headersHashes, mmrPeaks, treeId);
        firstBlockInBatch = headersSerialized[0].getBlockNumber();
    }

    function _processBlocksBatchNotAccumulated(
        uint256 treeId,
        bytes memory ctx,
        bytes[] memory headersSerialized
    ) internal returns (uint256 firstBlockInBatch, uint256 newMMRSize, bytes32 newMMRRoot) {
        (uint256 blockNumber, bytes32[] memory mmrPeaks) = abi.decode(ctx, (uint256, bytes32[]));

        bytes32 expectedHash = receivedParentHashes[blockNumber + 1];
        require(expectedHash != bytes32(0), "ERR_NO_REFERENCE_HASH");

        bytes32[] memory headersHashes = new bytes32[](headersSerialized.length);
        for (uint256 i = 0; i < headersSerialized.length; i++) {
            require(_isHeaderValid(expectedHash, headersSerialized[i]), "ERR_INVALID_CHAIN_ELEMENT");
            headersHashes[i] = expectedHash;
            expectedHash = headersSerialized[i].getParentHash();
        }

        (newMMRSize, newMMRRoot) = _appendMultipleBlockhashesToMMR(headersHashes, mmrPeaks, treeId);
        firstBlockInBatch = blockNumber;
    }

    function _appendMultipleBlockhashesToMMR(bytes32[] memory blockhashes, bytes32[] memory lastPeaks, uint256 mmrId) internal returns (uint256 newSize, bytes32 newRoot) {
        // Getting current mmr state for the treeId
        newSize = mmrs[mmrId].latestSize;
        newRoot = mmrs[mmrId].mmrSizeToRoot[newSize];

        // Allocate temporary memory for the next peaks
        bytes32[] memory nextPeaks = lastPeaks;

        for (uint256 i = 0; i < blockhashes.length; ++i) {
            (newSize, newRoot, nextPeaks) = StatelessMmr.appendWithPeaksRetrieval(blockhashes[i], nextPeaks, newSize, newRoot);
        }

        // Update the contract storage
        mmrs[mmrId].mmrSizeToRoot[newSize] = newRoot;
        mmrs[mmrId].latestSize = newSize;
    }

    function _isHeaderValid(bytes32 hash, bytes memory header) internal pure returns (bool) {
        return keccak256(header) == hash;
    }

    function _validateParentBlockAndProofIntegrity(
        uint256 mmrId,
        uint256 referenceProofLeafIndex,
        bytes32[] memory referenceProof,
        bytes32[] memory mmrPeaks,
        bytes memory referenceHeaderSerialized
    ) internal view {
        // Verify the reference block is in the MMR and the proof is valid
        uint256 mmrSize = mmrs[mmrId].latestSize;
        bytes32 root = mmrs[mmrId].mmrSizeToRoot[mmrSize];
        StatelessMmr.verifyProof(referenceProofLeafIndex, keccak256(referenceHeaderSerialized), referenceProof, mmrPeaks, mmrSize, root);
    }

    function getMMRRoot(uint256 mmrId, uint256 mmrSize) external view returns (bytes32) {
        return mmrs[mmrId].mmrSizeToRoot[mmrSize];
    }

    function getLatestMMRRoot(uint256 mmrId) external view returns (bytes32) {
        uint256 latestSize = mmrs[mmrId].latestSize;
        return mmrs[mmrId].mmrSizeToRoot[latestSize];
    }

    function getLatestMMRSize(uint256 mmrId) external view returns (uint256) {
        return mmrs[mmrId].latestSize;
    }
}

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

library Types {
    struct BlockHeaderProof {
        uint256 treeId;
        uint256 mmrTreeSize;
        uint256 blockNumber;
        uint256 blockProofLeafIndex;
        bytes32[] mmrPeaks;
        bytes32[] mmrElementInclusionProof;
        bytes provenBlockHeader;
    }

    enum AccountFields {
        NONCE,
        BALANCE,
        STORAGE_ROOT,
        CODE_HASH
    }
}

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

library Bitmap16 {
    function readBitAtIndexFromRight(uint16 bitmap, uint256 index) public pure returns (bool value) {
        require(15 >= index, "ERR_OUR_OF_RANGE");
        return (bitmap & (1 << index)) > 0;
    }
}

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

// This library extracts data from Block header encoded in RLP format.
// 0    RLP length              1+2
// 1    parentHash              1+32
// 2    ommersHash              1+32
// 3    beneficiary             1+20
// 4    stateRoot               1+32
// 5    TransactionRoot         1+32
// 6    receiptsRoot            1+32
//      logsBloom length        1+2
// 7    logsBloom               256
//  Total static elements size: 448 bytes
// 8	difficulty  - starts at pos 448
// 9	number      - blockNumber
// 10	gasLimit
// 11	gasUsed
// 12	timestamp
// 13	extraData
// 14	mixHash
// 15	nonce
// 16	baseFee
// 17   withdrawalsRoot

library EVMHeaderRLP {
    function nextElementJump(uint8 prefix) public pure returns (uint8) {
        if (prefix <= 128) {
            return 1;
        } else if (prefix <= 183) {
            return prefix - 128 + 1;
        }
        revert("EVMHeaderRLP.nextElementJump: Given element length not implemented");
    }

    // no loop saves ~300 gas
    function getBlockNumberPositionNoLoop(bytes memory rlp) public pure returns (uint256) {
        uint256 pos;
        //jumpting straight to the 1st dynamic element at pos 448 - difficulty
        pos = 448;
        //2nd element - block number
        pos += nextElementJump(uint8(rlp[pos]));

        return pos;
    }

    // no loop saves ~300 gas
    function getGasLimitPositionNoLoop(bytes memory rlp) public pure returns (uint256) {
        uint256 pos;
        //jumpting straight to the 1st dynamic element at pos 448 - difficulty
        pos = 448;
        //2nd element - block number
        pos += nextElementJump(uint8(rlp[pos]));
        //3rd element - gas limit
        pos += nextElementJump(uint8(rlp[pos]));

        return pos;
    }

    // no loop saves ~300 gas
    function getTimestampPositionNoLoop(bytes memory rlp) public pure returns (uint256) {
        uint256 pos;
        //jumpting straight to the 1st dynamic element at pos 448 - difficulty
        pos = 448;
        //2nd element - block number
        pos += nextElementJump(uint8(rlp[pos]));
        //3rd element - gas limit
        pos += nextElementJump(uint8(rlp[pos]));
        //4th element - gas used
        pos += nextElementJump(uint8(rlp[pos]));
        //timestamp - jackpot!
        pos += nextElementJump(uint8(rlp[pos]));

        return pos;
    }

    function getMixHashPositionNoLoop(bytes memory rlp) public pure returns (uint256) {
        uint256 pos;
        //jumpting straight to the 1st dynamic element at pos 448 - difficulty
        pos = 448;
        //2nd element - block number
        pos += nextElementJump(uint8(rlp[pos]));
        //3rd element - gas limit
        pos += nextElementJump(uint8(rlp[pos]));
        //4th element - gas used
        pos += nextElementJump(uint8(rlp[pos]));
        // 5th element - timestamp
        pos += nextElementJump(uint8(rlp[pos]));
        // 6th element - extradata
        pos += nextElementJump(uint8(rlp[pos]));
        // 7th element - mixhash
        pos += nextElementJump(uint8(rlp[pos]));

        return pos;
    }

    function getBaseFeePositionNoLoop(bytes memory rlp) public pure returns (uint256) {
        //jumping straight to the 1st dynamic element at pos 448 - difficulty
        uint256 pos = 448;

        // 2nd element - block number
        pos += nextElementJump(uint8(rlp[pos]));
        // 3rd element - gas limit
        pos += nextElementJump(uint8(rlp[pos]));
        // 4th element - gas used
        pos += nextElementJump(uint8(rlp[pos]));
        // timestamp
        pos += nextElementJump(uint8(rlp[pos]));
        // extradata
        pos += nextElementJump(uint8(rlp[pos]));
        // mixhash
        pos += nextElementJump(uint8(rlp[pos]));
        // nonce
        pos += nextElementJump(uint8(rlp[pos]));
        // nonce
        pos += nextElementJump(uint8(rlp[pos]));

        return pos;
    }

    function extractFromRLP(bytes calldata rlp, uint256 elementPosition) public pure returns (uint256 element) {
        // RLP hint: If the byte is less than 128 - than this byte IS the value needed - just return it.
        if (uint8(rlp[elementPosition]) < 128) {
            return uint256(uint8(rlp[elementPosition]));
        }

        // RLP hint: Otherwise - this byte stores the length of the element needed (in bytes).
        uint8 elementSize = uint8(rlp[elementPosition]) - 128;

        // ABI Encoding hint for dynamic bytes element:
        //  0x00-0x04 (4 bytes): Function signature
        //  0x05-0x23 (32 bytes uint): Offset to raw data of RLP[]
        //  0x24-0x43 (32 bytes uint): Length of RLP's raw data (in bytes)
        //  0x44-.... The RLP raw data starts here
        //  0x44 + elementPosition: 1 byte stores a length of our element
        //  0x44 + elementPosition + 1: Raw data of the element

        // Copies the element from calldata to uint256 stored in memory
        assembly {
            calldatacopy(
                add(mload(0x40), sub(32, elementSize)), // Copy to: Memory 0x40 (free memory pointer) + 32bytes (uint256 size) - length of our element (in bytes)
                add(0x44, add(elementPosition, 1)), // Copy from: Calldata 0x44 (RLP raw data offset) + elementPosition + 1 byte for the size of element
                elementSize
            )
            element := mload(mload(0x40)) // Load the 32 bytes (uint256) stored at memory 0x40 pointer - into return value
        }
        return element;
    }

    function getBlockNumber(bytes calldata rlp) public pure returns (uint256) {
        return extractFromRLP(rlp, getBlockNumberPositionNoLoop(rlp));
    }

    function getTimestamp(bytes calldata rlp) public pure returns (uint256) {
        return extractFromRLP(rlp, getTimestampPositionNoLoop(rlp));
    }

    function getDifficulty(bytes calldata rlp) public pure returns (uint256) {
        return extractFromRLP(rlp, 448);
    }

    function getGasLimit(bytes calldata rlp) public pure returns (uint256) {
        return extractFromRLP(rlp, getGasLimitPositionNoLoop(rlp));
    }

    function getBaseFee(bytes calldata rlp) public pure returns (uint256) {
        return extractFromRLP(rlp, getBaseFeePositionNoLoop(rlp));
    }

    function getParentHash(bytes calldata rlp) public pure returns (bytes32) {
        return bytes32(extractFromRLP(rlp, 3));
    }

    function getUnclesHash(bytes calldata rlp) public pure returns (bytes32) {
        return bytes32(extractFromRLP(rlp, 36));
    }

    function getBeneficiary(bytes calldata rlp) public pure returns (address) {
        return address(uint160(extractFromRLP(rlp, 70)));
    }

    function getStateRoot(bytes calldata rlp) public pure returns (bytes32) {
        return bytes32(extractFromRLP(rlp, 90));
    }

    function getTransactionsRoot(bytes calldata rlp) public pure returns (bytes32) {
        return bytes32(extractFromRLP(rlp, 123));
    }

    function getReceiptsRoot(bytes calldata rlp) public pure returns (bytes32) {
        return bytes32(extractFromRLP(rlp, 156));
    }

    function getMixHash(bytes calldata rlp) public pure returns (bytes32) {
        return bytes32(extractFromRLP(rlp, getMixHashPositionNoLoop(rlp)));
    }
}

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

library NullableStorageSlot {
    function toNullable(uint256 value) internal pure returns (uint256) {
        if (value == type(uint256).max) {
            return value;
        }
        return value + 1;
    }

    function fromNullable(uint256 value) internal pure returns (uint256) {
        require(!NullableStorageSlot.isNull(value), "NullableStorageSlot: value is null");
        if (value == type(uint256).max) {
            return value;
        }
        return value - 1;
    }

    function isNull(uint256 value) internal pure returns (bool) {
        return value == 0;
    }
}

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

library StatelessMmrHelpers {
    // Returns the height of a given `index`. The height of the root is 0
    function getHeight(uint index) internal pure returns (uint) {
        require(index >= 1, "index must be at least 1");

        uint bits = bitLength(index);
        uint ones = allOnes(bits);

        if (index != ones) {
            uint shifted = 1 << (bits - 1);
            uint recHeight = getHeight(index - (shifted - 1));
            return recHeight;
        }

        return bits - 1;
    }

    // Returns the number of bits in `num`
    function bitLength(uint256 num) internal pure returns (uint256) {
        require(num >= 0, "num must be greater than or equal to zero");

        uint256 bitPosition = 0;
        uint256 curN = 1;
        while (num >= curN) {
            bitPosition += 1;
            curN <<= 1;
        }
        return bitPosition;
    }

    // Returns a number having all its bits set to 1 for a given `bitsLength`
    function allOnes(uint256 bitsLength) internal pure returns (uint256) {
        require(bitsLength >= 0, "bitsLength must be greater or equal to zero");
        return (1 << bitsLength) - 1;
    }

    // Returns a number of ones in bit representation of a number
    function countOnes(uint256 num) internal pure returns (uint256) {
        uint256 count = 0;
        for (; num > 0; count++) {
            num = num & (num - 1);
        }
        return count;
    }

    // Returns the sibling offset from `height`
    function siblingOffset(uint256 height) internal pure returns (uint256) {
        return (2 << height) - 1;
    }

    // Returns the parent offset from `height`
    function parentOffset(uint256 height) internal pure returns (uint256) {
        return 2 << height;
    }

    // Returns number of leaves for a given mmr size
    function mmrSizeToLeafCount(uint256 mmrSize) internal pure returns (uint256) {
        uint256 leafCount = 0;
        uint256 mountainLeafCount = 1 << bitLength(mmrSize);
        for(; mountainLeafCount > 0; mountainLeafCount /= 2) {
            uint256 mountainSize = 2 * mountainLeafCount - 1;
            if (mountainSize <= mmrSize) {
                leafCount += mountainLeafCount;
                mmrSize -= mountainSize;
            }
        }
        require(mmrSize == 0, "mmrSize can't be associated with a valid MMR size");
        return leafCount;
    }

    // Returns leaf index (0-based) for a given mmr (element) index
    function mmrIndexToLeafIndex(uint256 mmrIndex) internal pure returns (uint256) {
        return mmrSizeToLeafCount(mmrIndex - 1);
    }

    function leafCountToAppendNoMerges(uint256 leafCount) internal pure returns (uint256) {
        uint256 count = 0;
        while(leafCount > 0 && (leafCount & 1) == 1) {
            count += 1;
            leafCount /= 2;
        }
        return count;
    }

    // Creates a new array from source and returns a new one containing all previous elements + `elem`
    function newArrWithElem(
        bytes32[] memory sourceArr,
        bytes32 elem
    ) internal pure returns (bytes32[] memory) {
        bytes32[] memory outputArray = new bytes32[](sourceArr.length + 1);
        uint i = 0;
        for (; i < sourceArr.length; i++) {
            outputArray[i] = sourceArr[i];
        }
        outputArray[i] = elem;
        return outputArray;
    }

    // Returns true if `elem` is in `arr`
    function arrayContains(
        bytes32 elem,
        bytes32[] memory arr
    ) internal pure returns (bool) {
        for (uint i = 0; i < arr.length; ++i) {
            if (arr[i] == elem) {
                return true;
            }
        }
        return false;
    }
}

// SPDX-License-Identifier: MIT
pragma solidity >0.5.0 <=0.8.24;

/* Library Imports */
import {Lib_BytesUtils} from "../utils/Lib_BytesUtils.sol";
import {Lib_RLPReader} from "../rlp/Lib_RLPReader.sol";
import {Lib_RLPWriter} from "../rlp/Lib_RLPWriter.sol";

/**
 * @title Lib_MerkleTrie
 */
library Lib_MerkleTrie {
    /*******************
     * Data Structures *
     *******************/

    enum NodeType {
        BranchNode,
        ExtensionNode,
        LeafNode
    }

    struct TrieNode {
        bytes encoded;
        Lib_RLPReader.RLPItem[] decoded;
    }

    /**********************
     * Contract Constants *
     **********************/

    // TREE_RADIX determines the number of elements per branch node.
    uint256 constant TREE_RADIX = 16;
    // Branch nodes have TREE_RADIX elements plus an additional `value` slot.
    uint256 constant BRANCH_NODE_LENGTH = TREE_RADIX + 1;
    // Leaf nodes and extension nodes always have two elements, a `path` and a `value`.
    uint256 constant LEAF_OR_EXTENSION_NODE_LENGTH = 2;

    // Prefixes are prepended to the `path` within a leaf or extension node and
    // allow us to differentiate between the two node types. `ODD` or `EVEN` is
    // determined by the number of nibbles within the unprefixed `path`. If the
    // number of nibbles if even, we need to insert an extra padding nibble so
    // the resulting prefixed `path` has an even number of nibbles.
    uint8 constant PREFIX_EXTENSION_EVEN = 0;
    uint8 constant PREFIX_EXTENSION_ODD = 1;
    uint8 constant PREFIX_LEAF_EVEN = 2;
    uint8 constant PREFIX_LEAF_ODD = 3;

    // Just a utility constant. RLP represents `NULL` as 0x80.
    bytes1 constant RLP_NULL = bytes1(0x80);
    bytes constant RLP_NULL_BYTES = hex"80";
    bytes32 internal constant KECCAK256_RLP_NULL_BYTES = keccak256(RLP_NULL_BYTES);

    /**********************
     * Internal Functions *
     **********************/

    /**
     * @notice Verifies a proof that a given key/value pair is present in the
     * Merkle trie.
     * @param _key Key of the node to search for, as a hex string.
     * @param _value Value of the node to search for, as a hex string.
     * @param _proof Merkle trie inclusion proof for the desired node. Unlike
     * traditional Merkle trees, this proof is executed top-down and consists
     * of a list of RLP-encoded nodes that make a path down to the target node.
     * @param _root Known root of the Merkle trie. Used to verify that the
     * included proof is correctly constructed.
     * @return _verified `true` if the k/v pair exists in the trie, `false` otherwise.
     */
    function verifyInclusionProof(bytes memory _key, bytes memory _value, bytes memory _proof, bytes32 _root) internal pure returns (bool _verified) {
        (bool exists, bytes memory value) = get(_key, _proof, _root);

        return (exists && Lib_BytesUtils.equal(_value, value));
    }

    /**
     * @notice Verifies a proof that a given key is *not* present in
     * the Merkle trie.
     * @param _key Key of the node to search for, as a hex string.
     * @param _proof Merkle trie inclusion proof for the node *nearest* the
     * target node.
     * @param _root Known root of the Merkle trie. Used to verify that the
     * included proof is correctly constructed.
     * @return _verified `true` if the key is absent in the trie, `false` otherwise.
     */
    function verifyExclusionProof(bytes memory _key, bytes memory _proof, bytes32 _root) internal pure returns (bool _verified) {
        (bool exists, ) = get(_key, _proof, _root);

        return exists == false;
    }

    /**
     * @notice Updates a Merkle trie and returns a new root hash.
     * @param _key Key of the node to update, as a hex string.
     * @param _value Value of the node to update, as a hex string.
     * @param _proof Merkle trie inclusion proof for the node *nearest* the
     * target node. If the key exists, we can simply update the value.
     * Otherwise, we need to modify the trie to handle the new k/v pair.
     * @param _root Known root of the Merkle trie. Used to verify that the
     * included proof is correctly constructed.
     * @return _updatedRoot Root hash of the newly constructed trie.
     */
    function update(bytes memory _key, bytes memory _value, bytes memory _proof, bytes32 _root) internal pure returns (bytes32 _updatedRoot) {
        // Special case when inserting the very first node.
        if (_root == KECCAK256_RLP_NULL_BYTES) {
            return getSingleNodeRootHash(_key, _value);
        }

        TrieNode[] memory proof = _parseProof(_proof);
        (uint256 pathLength, bytes memory keyRemainder, ) = _walkNodePath(proof, _key, _root);
        TrieNode[] memory newPath = _getNewPath(proof, pathLength, keyRemainder, _value);

        return _getUpdatedTrieRoot(newPath, _key);
    }

    /**
     * @notice Retrieves the value associated with a given key.
     * @param _key Key to search for, as hex bytes.
     * @param _proof Merkle trie inclusion proof for the key.
     * @param _root Known root of the Merkle trie.
     * @return _exists Whether or not the key exists.
     * @return _value Value of the key if it exists.
     */
    function get(bytes memory _key, bytes memory _proof, bytes32 _root) internal pure returns (bool _exists, bytes memory _value) {
        TrieNode[] memory proof = _parseProof(_proof);
        (uint256 pathLength, bytes memory keyRemainder, bool isFinalNode) = _walkNodePath(proof, _key, _root);

        bool exists = keyRemainder.length == 0;

        require(exists || isFinalNode, "Provided proof is invalid.");

        bytes memory value = exists ? _getNodeValue(proof[pathLength - 1]) : bytes("");

        return (exists, value);
    }

    /**
     * Computes the root hash for a trie with a single node.
     * @param _key Key for the single node.
     * @param _value Value for the single node.
     * @return _updatedRoot Hash of the trie.
     */
    function getSingleNodeRootHash(bytes memory _key, bytes memory _value) internal pure returns (bytes32 _updatedRoot) {
        return keccak256(_makeLeafNode(Lib_BytesUtils.toNibbles(_key), _value).encoded);
    }

    /*********************
     * Private Functions *
     *********************/

    /**
     * @notice Walks through a proof using a provided key.
     * @param _proof Inclusion proof to walk through.
     * @param _key Key to use for the walk.
     * @param _root Known root of the trie.
     * @return _pathLength Length of the final path
     * @return _keyRemainder Portion of the key remaining after the walk.
     * @return _isFinalNode Whether or not we've hit a dead end.
     */
    function _walkNodePath(TrieNode[] memory _proof, bytes memory _key, bytes32 _root) private pure returns (uint256 _pathLength, bytes memory _keyRemainder, bool _isFinalNode) {
        uint256 pathLength = 0;
        bytes memory key = Lib_BytesUtils.toNibbles(_key);

        bytes32 currentNodeID = _root;
        uint256 currentKeyIndex = 0;
        uint256 currentKeyIncrement = 0;
        TrieNode memory currentNode;

        // Proof is top-down, so we start at the first element (root).
        for (uint256 i = 0; i < _proof.length; i++) {
            currentNode = _proof[i];
            currentKeyIndex += currentKeyIncrement;

            // Keep track of the proof elements we actually need.
            // It's expensive to resize arrays, so this simply reduces gas costs.
            pathLength += 1;

            if (currentKeyIndex == 0) {
                // First proof element is always the root node.
                require(keccak256(currentNode.encoded) == currentNodeID, "Invalid root hash");
            } else if (currentNode.encoded.length >= 32) {
                // Nodes 32 bytes or larger are hashed inside branch nodes.
                require(keccak256(currentNode.encoded) == currentNodeID, "Invalid large internal hash");
            } else {
                // Nodes smaller than 31 bytes aren't hashed.
                require(Lib_BytesUtils.toBytes32(currentNode.encoded) == currentNodeID, "Invalid internal node hash");
            }

            if (currentNode.decoded.length == BRANCH_NODE_LENGTH) {
                if (currentKeyIndex == key.length) {
                    // We've hit the end of the key, meaning the value should be within this branch node.
                    break;
                } else {
                    // We're not at the end of the key yet.
                    // Figure out what the next node ID should be and continue.
                    uint8 branchKey = uint8(key[currentKeyIndex]);
                    Lib_RLPReader.RLPItem memory nextNode = currentNode.decoded[branchKey];
                    currentNodeID = _getNodeID(nextNode);
                    currentKeyIncrement = 1;
                    continue;
                }
            } else if (currentNode.decoded.length == LEAF_OR_EXTENSION_NODE_LENGTH) {
                bytes memory path = _getNodePath(currentNode);
                uint8 prefix = uint8(path[0]);
                uint8 offset = 2 - (prefix % 2);
                bytes memory pathRemainder = Lib_BytesUtils.slice(path, offset);
                bytes memory keyRemainder = Lib_BytesUtils.slice(key, currentKeyIndex);
                uint256 sharedNibbleLength = _getSharedNibbleLength(pathRemainder, keyRemainder);

                if (prefix == PREFIX_LEAF_EVEN || prefix == PREFIX_LEAF_ODD) {
                    if (pathRemainder.length == sharedNibbleLength && keyRemainder.length == sharedNibbleLength) {
                        // The key within this leaf matches our key exactly.
                        // Increment the key index to reflect that we have no remainder.
                        currentKeyIndex += sharedNibbleLength;
                    }

                    // We've hit a leaf node, so our next node should be NULL.
                    currentNodeID = bytes32(RLP_NULL);
                    break;
                } else if (prefix == PREFIX_EXTENSION_EVEN || prefix == PREFIX_EXTENSION_ODD) {
                    if (sharedNibbleLength == 0) {
                        // Our extension node doesn't share any part of our key.
                        // We've hit the end of this path, updates will need to modify this extension.
                        currentNodeID = bytes32(RLP_NULL);
                        break;
                    } else {
                        // Our extension shares some nibbles.
                        // Carry on to the next node.
                        currentNodeID = _getNodeID(currentNode.decoded[1]);
                        currentKeyIncrement = sharedNibbleLength;
                        continue;
                    }
                } else {
                    revert("Received a node with an unknown prefix");
                }
            } else {
                revert("Received an unparseable node.");
            }
        }

        // If our node ID is NULL, then we're at a dead end.
        bool isFinalNode = currentNodeID == bytes32(RLP_NULL);
        return (pathLength, Lib_BytesUtils.slice(key, currentKeyIndex), isFinalNode);
    }

    /**
     * @notice Creates new nodes to support a k/v pair insertion into a given
     * Merkle trie path.
     * @param _path Path to the node nearest the k/v pair.
     * @param _pathLength Length of the path. Necessary because the provided
     * path may include additional nodes (e.g., it comes directly from a proof)
     * and we can't resize in-memory arrays without costly duplication.
     * @param _keyRemainder Portion of the initial key that must be inserted
     * into the trie.
     * @param _value Value to insert at the given key.
     * @return _newPath A new path with the inserted k/v pair and extra supporting nodes.
     */
    function _getNewPath(TrieNode[] memory _path, uint256 _pathLength, bytes memory _keyRemainder, bytes memory _value) private pure returns (TrieNode[] memory _newPath) {
        bytes memory keyRemainder = _keyRemainder;

        // Most of our logic depends on the status of the last node in the path.
        TrieNode memory lastNode = _path[_pathLength - 1];
        NodeType lastNodeType = _getNodeType(lastNode);

        // Create an array for newly created nodes.
        // We need up to three new nodes, depending on the contents of the last node.
        // Since array resizing is expensive, we'll keep track of the size manually.
        // We're using an explicit `totalNewNodes += 1` after insertions for clarity.
        TrieNode[] memory newNodes = new TrieNode[](3);
        uint256 totalNewNodes = 0;

        if (keyRemainder.length == 0 && lastNodeType == NodeType.LeafNode) {
            // We've found a leaf node with the given key.
            // Simply need to update the value of the node to match.
            newNodes[totalNewNodes] = _makeLeafNode(_getNodeKey(lastNode), _value);
            totalNewNodes += 1;
        } else if (lastNodeType == NodeType.BranchNode) {
            if (keyRemainder.length == 0) {
                // We've found a branch node with the given key.
                // Simply need to update the value of the node to match.
                newNodes[totalNewNodes] = _editBranchValue(lastNode, _value);
                totalNewNodes += 1;
            } else {
                // We've found a branch node, but it doesn't contain our key.
                // Reinsert the old branch for now.
                newNodes[totalNewNodes] = lastNode;
                totalNewNodes += 1;
                // Create a new leaf node, slicing our remainder since the first byte points
                // to our branch node.
                newNodes[totalNewNodes] = _makeLeafNode(Lib_BytesUtils.slice(keyRemainder, 1), _value);
                totalNewNodes += 1;
            }
        } else {
            // Our last node is either an extension node or a leaf node with a different key.
            bytes memory lastNodeKey = _getNodeKey(lastNode);
            uint256 sharedNibbleLength = _getSharedNibbleLength(lastNodeKey, keyRemainder);

            if (sharedNibbleLength != 0) {
                // We've got some shared nibbles between the last node and our key remainder.
                // We'll need to insert an extension node that covers these shared nibbles.
                bytes memory nextNodeKey = Lib_BytesUtils.slice(lastNodeKey, 0, sharedNibbleLength);
                newNodes[totalNewNodes] = _makeExtensionNode(nextNodeKey, _getNodeHash(_value));
                totalNewNodes += 1;

                // Cut down the keys since we've just covered these shared nibbles.
                lastNodeKey = Lib_BytesUtils.slice(lastNodeKey, sharedNibbleLength);
                keyRemainder = Lib_BytesUtils.slice(keyRemainder, sharedNibbleLength);
            }

            // Create an empty branch to fill in.
            TrieNode memory newBranch = _makeEmptyBranchNode();

            if (lastNodeKey.length == 0) {
                // Key remainder was larger than the key for our last node.
                // The value within our last node is therefore going to be shifted into
                // a branch value slot.
                newBranch = _editBranchValue(newBranch, _getNodeValue(lastNode));
            } else {
                // Last node key was larger than the key remainder.
                // We're going to modify some index of our branch.
                uint8 branchKey = uint8(lastNodeKey[0]);
                // Move on to the next nibble.
                lastNodeKey = Lib_BytesUtils.slice(lastNodeKey, 1);

                if (lastNodeType == NodeType.LeafNode) {
                    // We're dealing with a leaf node.
                    // We'll modify the key and insert the old leaf node into the branch index.
                    TrieNode memory modifiedLastNode = _makeLeafNode(lastNodeKey, _getNodeValue(lastNode));
                    newBranch = _editBranchIndex(newBranch, branchKey, _getNodeHash(modifiedLastNode.encoded));
                } else if (lastNodeKey.length != 0) {
                    // We're dealing with a shrinking extension node.
                    // We need to modify the node to decrease the size of the key.
                    TrieNode memory modifiedLastNode = _makeExtensionNode(lastNodeKey, _getNodeValue(lastNode));
                    newBranch = _editBranchIndex(newBranch, branchKey, _getNodeHash(modifiedLastNode.encoded));
                } else {
                    // We're dealing with an unnecessary extension node.
                    // We're going to delete the node entirely.
                    // Simply insert its current value into the branch index.
                    newBranch = _editBranchIndex(newBranch, branchKey, _getNodeValue(lastNode));
                }
            }

            if (keyRemainder.length == 0) {
                // We've got nothing left in the key remainder.
                // Simply insert the value into the branch value slot.
                newBranch = _editBranchValue(newBranch, _value);
                // Push the branch into the list of new nodes.
                newNodes[totalNewNodes] = newBranch;
                totalNewNodes += 1;
            } else {
                // We've got some key remainder to work with.
                // We'll be inserting a leaf node into the trie.
                // First, move on to the next nibble.
                keyRemainder = Lib_BytesUtils.slice(keyRemainder, 1);
                // Push the branch into the list of new nodes.
                newNodes[totalNewNodes] = newBranch;
                totalNewNodes += 1;
                // Push a new leaf node for our k/v pair.
                newNodes[totalNewNodes] = _makeLeafNode(keyRemainder, _value);
                totalNewNodes += 1;
            }
        }

        // Finally, join the old path with our newly created nodes.
        // Since we're overwriting the last node in the path, we use `_pathLength - 1`.
        return _joinNodeArrays(_path, _pathLength - 1, newNodes, totalNewNodes);
    }

    /**
     * @notice Computes the trie root from a given path.
     * @param _nodes Path to some k/v pair.
     * @param _key Key for the k/v pair.
     * @return _updatedRoot Root hash for the updated trie.
     */
    function _getUpdatedTrieRoot(TrieNode[] memory _nodes, bytes memory _key) private pure returns (bytes32 _updatedRoot) {
        bytes memory key = Lib_BytesUtils.toNibbles(_key);

        // Some variables to keep track of during iteration.
        TrieNode memory currentNode;
        NodeType currentNodeType;
        bytes memory previousNodeHash;

        // Run through the path backwards to rebuild our root hash.
        for (uint256 i = _nodes.length; i > 0; i--) {
            // Pick out the current node.
            currentNode = _nodes[i - 1];
            currentNodeType = _getNodeType(currentNode);

            if (currentNodeType == NodeType.LeafNode) {
                // Leaf nodes are already correctly encoded.
                // Shift the key over to account for the nodes key.
                bytes memory nodeKey = _getNodeKey(currentNode);
                key = Lib_BytesUtils.slice(key, 0, key.length - nodeKey.length);
            } else if (currentNodeType == NodeType.ExtensionNode) {
                // Shift the key over to account for the nodes key.
                bytes memory nodeKey = _getNodeKey(currentNode);
                key = Lib_BytesUtils.slice(key, 0, key.length - nodeKey.length);

                // If this node is the last element in the path, it'll be correctly encoded
                // and we can skip this part.
                if (previousNodeHash.length > 0) {
                    // Re-encode the node based on the previous node.
                    currentNode = _makeExtensionNode(nodeKey, previousNodeHash);
                }
            } else if (currentNodeType == NodeType.BranchNode) {
                // If this node is the last element in the path, it'll be correctly encoded
                // and we can skip this part.
                if (previousNodeHash.length > 0) {
                    // Re-encode the node based on the previous node.
                    uint8 branchKey = uint8(key[key.length - 1]);
                    key = Lib_BytesUtils.slice(key, 0, key.length - 1);
                    currentNode = _editBranchIndex(currentNode, branchKey, previousNodeHash);
                }
            }

            // Compute the node hash for the next iteration.
            previousNodeHash = _getNodeHash(currentNode.encoded);
        }

        // Current node should be the root at this point.
        // Simply return the hash of its encoding.
        return keccak256(currentNode.encoded);
    }

    /**
     * @notice Parses an RLP-encoded proof into something more useful.
     * @param _proof RLP-encoded proof to parse.
     * @return _parsed Proof parsed into easily accessible structs.
     */
    function _parseProof(bytes memory _proof) private pure returns (TrieNode[] memory _parsed) {
        Lib_RLPReader.RLPItem[] memory nodes = Lib_RLPReader.readList(_proof);
        TrieNode[] memory proof = new TrieNode[](nodes.length);

        for (uint256 i = 0; i < nodes.length; i++) {
            bytes memory encoded = Lib_RLPReader.readBytes(nodes[i]);
            proof[i] = TrieNode({encoded: encoded, decoded: Lib_RLPReader.readList(encoded)});
        }

        return proof;
    }

    /**
     * @notice Picks out the ID for a node. Node ID is referred to as the
     * "hash" within the specification, but nodes < 32 bytes are not actually
     * hashed.
     * @param _node Node to pull an ID for.
     * @return _nodeID ID for the node, depending on the size of its contents.
     */
    function _getNodeID(Lib_RLPReader.RLPItem memory _node) private pure returns (bytes32 _nodeID) {
        bytes memory nodeID;

        if (_node.length < 32) {
            // Nodes smaller than 32 bytes are RLP encoded.
            nodeID = Lib_RLPReader.readRawBytes(_node);
        } else {
            // Nodes 32 bytes or larger are hashed.
            nodeID = Lib_RLPReader.readBytes(_node);
        }

        return Lib_BytesUtils.toBytes32(nodeID);
    }

    /**
     * @notice Gets the path for a leaf or extension node.
     * @param _node Node to get a path for.
     * @return _path Node path, converted to an array of nibbles.
     */
    function _getNodePath(TrieNode memory _node) private pure returns (bytes memory _path) {
        return Lib_BytesUtils.toNibbles(Lib_RLPReader.readBytes(_node.decoded[0]));
    }

    /**
     * @notice Gets the key for a leaf or extension node. Keys are essentially
     * just paths without any prefix.
     * @param _node Node to get a key for.
     * @return _key Node key, converted to an array of nibbles.
     */
    function _getNodeKey(TrieNode memory _node) private pure returns (bytes memory _key) {
        return _removeHexPrefix(_getNodePath(_node));
    }

    /**
     * @notice Gets the path for a node.
     * @param _node Node to get a value for.
     * @return _value Node value, as hex bytes.
     */
    function _getNodeValue(TrieNode memory _node) private pure returns (bytes memory _value) {
        return Lib_RLPReader.readBytes(_node.decoded[_node.decoded.length - 1]);
    }

    /**
     * @notice Computes the node hash for an encoded node. Nodes < 32 bytes
     * are not hashed, all others are keccak256 hashed.
     * @param _encoded Encoded node to hash.
     * @return _hash Hash of the encoded node. Simply the input if < 32 bytes.
     */
    function _getNodeHash(bytes memory _encoded) private pure returns (bytes memory _hash) {
        if (_encoded.length < 32) {
            return _encoded;
        } else {
            return abi.encodePacked(keccak256(_encoded));
        }
    }

    /**
     * @notice Determines the type for a given node.
     * @param _node Node to determine a type for.
     * @return _type Type of the node; BranchNode/ExtensionNode/LeafNode.
     */
    function _getNodeType(TrieNode memory _node) private pure returns (NodeType _type) {
        if (_node.decoded.length == BRANCH_NODE_LENGTH) {
            return NodeType.BranchNode;
        } else if (_node.decoded.length == LEAF_OR_EXTENSION_NODE_LENGTH) {
            bytes memory path = _getNodePath(_node);
            uint8 prefix = uint8(path[0]);

            if (prefix == PREFIX_LEAF_EVEN || prefix == PREFIX_LEAF_ODD) {
                return NodeType.LeafNode;
            } else if (prefix == PREFIX_EXTENSION_EVEN || prefix == PREFIX_EXTENSION_ODD) {
                return NodeType.ExtensionNode;
            }
        }

        revert("Invalid node type");
    }

    /**
     * @notice Utility; determines the number of nibbles shared between two
     * nibble arrays.
     * @param _a First nibble array.
     * @param _b Second nibble array.
     * @return _shared Number of shared nibbles.
     */
    function _getSharedNibbleLength(bytes memory _a, bytes memory _b) private pure returns (uint256 _shared) {
        uint256 i = 0;
        while (_a.length > i && _b.length > i && _a[i] == _b[i]) {
            i++;
        }
        return i;
    }

    /**
     * @notice Utility; converts an RLP-encoded node into our nice struct.
     * @param _raw RLP-encoded node to convert.
     * @return _node Node as a TrieNode struct.
     */
    function _makeNode(bytes[] memory _raw) private pure returns (TrieNode memory _node) {
        bytes memory encoded = Lib_RLPWriter.writeList(_raw);

        return TrieNode({encoded: encoded, decoded: Lib_RLPReader.readList(encoded)});
    }

    /**
     * @notice Utility; converts an RLP-decoded node into our nice struct.
     * @param _items RLP-decoded node to convert.
     * @return _node Node as a TrieNode struct.
     */
    function _makeNode(Lib_RLPReader.RLPItem[] memory _items) private pure returns (TrieNode memory _node) {
        bytes[] memory raw = new bytes[](_items.length);
        for (uint256 i = 0; i < _items.length; i++) {
            raw[i] = Lib_RLPReader.readRawBytes(_items[i]);
        }
        return _makeNode(raw);
    }

    /**
     * @notice Creates a new extension node.
     * @param _key Key for the extension node, unprefixed.
     * @param _value Value for the extension node.
     * @return _node New extension node with the given k/v pair.
     */
    function _makeExtensionNode(bytes memory _key, bytes memory _value) private pure returns (TrieNode memory _node) {
        bytes[] memory raw = new bytes[](2);
        bytes memory key = _addHexPrefix(_key, false);
        raw[0] = Lib_RLPWriter.writeBytes(Lib_BytesUtils.fromNibbles(key));
        raw[1] = Lib_RLPWriter.writeBytes(_value);
        return _makeNode(raw);
    }

    /**
     * @notice Creates a new leaf node.
     * @dev This function is essentially identical to `_makeExtensionNode`.
     * Although we could route both to a single method with a flag, it's
     * more gas efficient to keep them separate and duplicate the logic.
     * @param _key Key for the leaf node, unprefixed.
     * @param _value Value for the leaf node.
     * @return _node New leaf node with the given k/v pair.
     */
    function _makeLeafNode(bytes memory _key, bytes memory _value) private pure returns (TrieNode memory _node) {
        bytes[] memory raw = new bytes[](2);
        bytes memory key = _addHexPrefix(_key, true);
        raw[0] = Lib_RLPWriter.writeBytes(Lib_BytesUtils.fromNibbles(key));
        raw[1] = Lib_RLPWriter.writeBytes(_value);
        return _makeNode(raw);
    }

    /**
     * @notice Creates an empty branch node.
     * @return _node Empty branch node as a TrieNode struct.
     */
    function _makeEmptyBranchNode() private pure returns (TrieNode memory _node) {
        bytes[] memory raw = new bytes[](BRANCH_NODE_LENGTH);
        for (uint256 i = 0; i < raw.length; i++) {
            raw[i] = RLP_NULL_BYTES;
        }
        return _makeNode(raw);
    }

    /**
     * @notice Modifies the value slot for a given branch.
     * @param _branch Branch node to modify.
     * @param _value Value to insert into the branch.
     * @return _updatedNode Modified branch node.
     */
    function _editBranchValue(TrieNode memory _branch, bytes memory _value) private pure returns (TrieNode memory _updatedNode) {
        bytes memory encoded = Lib_RLPWriter.writeBytes(_value);
        _branch.decoded[_branch.decoded.length - 1] = Lib_RLPReader.toRLPItem(encoded);
        return _makeNode(_branch.decoded);
    }

    /**
     * @notice Modifies a slot at an index for a given branch.
     * @param _branch Branch node to modify.
     * @param _index Slot index to modify.
     * @param _value Value to insert into the slot.
     * @return _updatedNode Modified branch node.
     */
    function _editBranchIndex(TrieNode memory _branch, uint8 _index, bytes memory _value) private pure returns (TrieNode memory _updatedNode) {
        bytes memory encoded = _value.length < 32 ? _value : Lib_RLPWriter.writeBytes(_value);
        _branch.decoded[_index] = Lib_RLPReader.toRLPItem(encoded);
        return _makeNode(_branch.decoded);
    }

    /**
     * @notice Utility; adds a prefix to a key.
     * @param _key Key to prefix.
     * @param _isLeaf Whether or not the key belongs to a leaf.
     * @return _prefixedKey Prefixed key.
     */
    function _addHexPrefix(bytes memory _key, bool _isLeaf) private pure returns (bytes memory _prefixedKey) {
        uint8 prefix = _isLeaf ? uint8(0x02) : uint8(0x00);
        uint8 offset = uint8(_key.length % 2);
        bytes memory prefixed = new bytes(2 - offset);
        prefixed[0] = bytes1(prefix + offset);
        return abi.encodePacked(prefixed, _key);
    }

    /**
     * @notice Utility; removes a prefix from a path.
     * @param _path Path to remove the prefix from.
     * @return _unprefixedKey Unprefixed key.
     */
    function _removeHexPrefix(bytes memory _path) private pure returns (bytes memory _unprefixedKey) {
        if (uint8(_path[0]) % 2 == 0) {
            return Lib_BytesUtils.slice(_path, 2);
        } else {
            return Lib_BytesUtils.slice(_path, 1);
        }
    }

    /**
     * @notice Utility; combines two node arrays. Array lengths are required
     * because the actual lengths may be longer than the filled lengths.
     * Array resizing is extremely costly and should be avoided.
     * @param _a First array to join.
     * @param _aLength Length of the first array.
     * @param _b Second array to join.
     * @param _bLength Length of the second array.
     * @return _joined Combined node array.
     */
    function _joinNodeArrays(TrieNode[] memory _a, uint256 _aLength, TrieNode[] memory _b, uint256 _bLength) private pure returns (TrieNode[] memory _joined) {
        TrieNode[] memory ret = new TrieNode[](_aLength + _bLength);

        // Copy elements from the first array.
        for (uint256 i = 0; i < _aLength; i++) {
            ret[i] = _a[i];
        }

        // Copy elements from the second array.
        for (uint256 i = 0; i < _bLength; i++) {
            ret[i + _aLength] = _b[i];
        }

        return ret;
    }
}

// SPDX-License-Identifier: MIT
pragma solidity >0.5.0 <=0.8.24;

/**
 * @title Lib_BytesUtils
 */
library Lib_BytesUtils {
    /**********************
     * Internal Functions *
     **********************/

    function slice(bytes memory _bytes, uint256 _start, uint256 _length) internal pure returns (bytes memory) {
        unchecked {
            require(_length + 31 >= _length, "slice_overflow");
            require(_start + _length >= _start, "slice_overflow");
            require(_bytes.length >= _start + _length, "slice_outOfBounds");

            bytes memory tempBytes;

            assembly {
                switch iszero(_length)
                case 0 {
                    // Get a location of some free memory and store it in tempBytes as
                    // Solidity does for memory variables.
                    tempBytes := mload(0x40)

                    // The first word of the slice result is potentially a partial
                    // word read from the original array. To read it, we calculate
                    // the length of that partial word and start copying that many
                    // bytes into the array. The first word we copy will start with
                    // data we don't care about, but the last `lengthmod` bytes will
                    // land at the beginning of the contents of the new array. When
                    // we're done copying, we overwrite the full first word with
                    // the actual length of the slice.
                    let lengthmod := and(_length, 31)

                    // The multiplication in the next line is necessary
                    // because when slicing multiples of 32 bytes (lengthmod == 0)
                    // the following copy loop was copying the origin's length
                    // and then ending prematurely not copying everything it should.
                    let mc := add(add(tempBytes, lengthmod), mul(0x20, iszero(lengthmod)))
                    let end := add(mc, _length)

                    for {
                        // The multiplication in the next line has the same exact purpose
                        // as the one above.
                        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)

                    //update free-memory pointer
                    //allocating the array padded to 32 bytes like the compiler does now
                    mstore(0x40, and(add(mc, 31), not(31)))
                }
                //if we want a zero-length slice let's just return a zero-length array
                default {
                    tempBytes := mload(0x40)

                    //zero out the 32 bytes slice we are about to return
                    //we need to do it because Solidity does not garbage collect
                    mstore(tempBytes, 0)

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

            return tempBytes;
        }
    }

    function slice(bytes memory _bytes, uint256 _start) internal pure returns (bytes memory) {
        unchecked {
            if (_bytes.length - _start == 0) {
                return bytes("");
            }

            return slice(_bytes, _start, _bytes.length - _start);
        }
    }

    function toBytes32PadLeft(bytes memory _bytes) internal pure returns (bytes32) {
        unchecked {
            bytes32 ret;
            uint256 len = _bytes.length <= 32 ? _bytes.length : 32;
            assembly {
                ret := shr(mul(sub(32, len), 8), mload(add(_bytes, 32)))
            }
            return ret;
        }
    }

    function toBytes32(bytes memory _bytes) internal pure returns (bytes32) {
        unchecked {
            if (_bytes.length < 32) {
                bytes32 ret;
                assembly {
                    ret := mload(add(_bytes, 32))
                }
                return ret;
            }

            return abi.decode(_bytes, (bytes32)); // will truncate if input length > 32 bytes
        }
    }

    function toUint256(bytes memory _bytes) internal pure returns (uint256) {
        return uint256(toBytes32(_bytes));
    }

    function toUint24(bytes memory _bytes, uint256 _start) internal pure returns (uint24) {
        require(_start + 3 >= _start, "toUint24_overflow");
        require(_bytes.length >= _start + 3, "toUint24_outOfBounds");
        uint24 tempUint;

        assembly {
            tempUint := mload(add(add(_bytes, 0x3), _start))
        }

        return tempUint;
    }

    function toUint8(bytes memory _bytes, uint256 _start) internal pure returns (uint8) {
        require(_start + 1 >= _start, "toUint8_overflow");
        require(_bytes.length >= _start + 1, "toUint8_outOfBounds");
        uint8 tempUint;

        assembly {
            tempUint := mload(add(add(_bytes, 0x1), _start))
        }

        return tempUint;
    }

    function toAddress(bytes memory _bytes, uint256 _start) internal pure returns (address) {
        require(_start + 20 >= _start, "toAddress_overflow");
        require(_bytes.length >= _start + 20, "toAddress_outOfBounds");
        address tempAddress;

        assembly {
            tempAddress := div(mload(add(add(_bytes, 0x20), _start)), 0x1000000000000000000000000)
        }

        return tempAddress;
    }

    function toNibbles(bytes memory _bytes) internal pure returns (bytes memory) {
        unchecked {
            bytes memory nibbles = new bytes(_bytes.length * 2);

            for (uint256 i = 0; i < _bytes.length; i++) {
                nibbles[i * 2] = _bytes[i] >> 4;
                nibbles[i * 2 + 1] = bytes1(uint8(_bytes[i]) % 16);
            }

            return nibbles;
        }
    }

    function fromNibbles(bytes memory _bytes) internal pure returns (bytes memory) {
        unchecked {
            bytes memory ret = new bytes(_bytes.length / 2);

            for (uint256 i = 0; i < ret.length; i++) {
                ret[i] = (_bytes[i * 2] << 4) | (_bytes[i * 2 + 1]);
            }

            return ret;
        }
    }

    function equal(bytes memory _bytes, bytes memory _other) internal pure returns (bool) {
        return keccak256(_bytes) == keccak256(_other);
    }
}

// SPDX-License-Identifier: MIT
pragma solidity >0.5.0 <=0.8.24;
pragma experimental ABIEncoderV2;

/* Library Imports */
import {Lib_BytesUtils} from "../utils/Lib_BytesUtils.sol";

/**
 * @title Lib_RLPWriter
 * @author Bakaoh (with modifications)
 */
library Lib_RLPWriter {
    /**********************
     * Internal Functions *
     **********************/

    /**
     * RLP encodes a byte string.
     * @param _in The byte string to encode.
     * @return _out The RLP encoded string in bytes.
     */
    function writeBytes(bytes memory _in) internal pure returns (bytes memory _out) {
        bytes memory encoded;

        if (_in.length == 1 && uint8(_in[0]) < 128) {
            encoded = _in;
        } else {
            encoded = abi.encodePacked(_writeLength(_in.length, 128), _in);
        }

        return encoded;
    }

    /**
     * RLP encodes a list of RLP encoded byte byte strings.
     * @param _in The list of RLP encoded byte strings.
     * @return _out The RLP encoded list of items in bytes.
     */
    function writeList(bytes[] memory _in) internal pure returns (bytes memory _out) {
        bytes memory list = _flatten(_in);
        return abi.encodePacked(_writeLength(list.length, 192), list);
    }

    /**
     * RLP encodes a string.
     * @param _in The string to encode.
     * @return _out The RLP encoded string in bytes.
     */
    function writeString(string memory _in) internal pure returns (bytes memory _out) {
        return writeBytes(bytes(_in));
    }

    /**
     * RLP encodes an address.
     * @param _in The address to encode.
     * @return _out The RLP encoded address in bytes.
     */
    function writeAddress(address _in) internal pure returns (bytes memory _out) {
        return writeBytes(abi.encodePacked(_in));
    }

    /**
     * RLP encodes a uint.
     * @param _in The uint256 to encode.
     * @return _out The RLP encoded uint256 in bytes.
     */
    function writeUint(uint256 _in) internal pure returns (bytes memory _out) {
        return writeBytes(_toBinary(_in));
    }

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

    /*********************
     * Private Functions *
     *********************/

    /**
     * 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 _encoded RLP encoded bytes.
     */
    function _writeLength(uint256 _len, uint256 _offset) private pure returns (bytes memory _encoded) {
        bytes memory encoded;

        if (_len < 56) {
            encoded = new bytes(1);
            encoded[0] = bytes1(uint8(_len) + uint8(_offset));
        } else {
            uint256 lenLen;
            uint256 i = 1;
            while (_len / i != 0) {
                lenLen++;
                i *= 256;
            }

            encoded = new bytes(lenLen + 1);
            encoded[0] = bytes1(uint8(lenLen) + uint8(_offset) + 55);
            for (i = 1; i <= lenLen; i++) {
                encoded[i] = bytes1(uint8((_len / (256 ** (lenLen - i))) % 256));
            }
        }

        return encoded;
    }

    /**
     * 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 _binary RLP encoded bytes.
     */
    function _toBinary(uint256 _x) private pure returns (bytes memory _binary) {
        bytes memory b = abi.encodePacked(_x);

        uint256 i = 0;
        for (; i < 32; i++) {
            if (b[i] != 0) {
                break;
            }
        }

        bytes memory res = new bytes(32 - i);
        for (uint256 j = 0; j < res.length; j++) {
            res[j] = b[i++];
        }

        return res;
    }

    /**
     * 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(uint256 _dest, uint256 _src, uint256 _len) private pure {
        uint256 dest = _dest;
        uint256 src = _src;
        uint256 len = _len;

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

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

    /**
     * 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 _flattened The flattened byte string.
     */
    function _flatten(bytes[] memory _list) private pure returns (bytes memory _flattened) {
        if (_list.length == 0) {
            return new bytes(0);
        }

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

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

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

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

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

        return flattened;
    }
}

{
  "remappings": [
    "ds-test/=lib/forge-std/lib/ds-test/src/",
    "forge-std/=lib/forge-std/src/",
    "@openzeppelin/=lib/openzeppelin-contracts/",
    "solidity-mmr/=lib/solidity-mmr/src/",
    "@optimism/libraries/=src/lib/external/",
    "@openzeppelin/contracts/=lib/openzeppelin-contracts/contracts/",
    "erc4626-tests/=lib/openzeppelin-contracts/lib/erc4626-tests/",
    "openzeppelin-contracts/=lib/openzeppelin-contracts/"
  ],
  "optimizer": {
    "enabled": true,
    "runs": 200
  },
  "metadata": {
    "useLiteralContent": false,
    "bytecodeHash": "ipfs",
    "appendCBOR": true
  },
  "outputSelection": {
    "*": {
      "*": [
        "evm.bytecode",
        "evm.deployedBytecode",
        "devdoc",
        "userdoc",
        "metadata",
        "abi"
      ]
    }
  },
  "evmVersion": "paris",
  "viaIR": true,
  "libraries": {
    "src/lib/Bitmap16.sol": {
      "Bitmap16": "0xec4F121aA03757102456DcA5C4838b97c1207164"
    },
    "src/lib/EVMHeaderRLP.sol": {
      "EVMHeaderRLP": "0xE2712d15267c29B2c6f6B5127621750F11d51E1C"
    }
  }
}

[{"inputs":[{"internalType":"address","name":"_headersProcessor","type":"address"}],"stateMutability":"nonpayable","type":"constructor"},{"inputs":[],"name":"IndexOutOfBounds","type":"error"},{"inputs":[],"name":"InvalidPeaksArrayLength","type":"error"},{"inputs":[],"name":"InvalidProof","type":"error"},{"inputs":[],"name":"InvalidRoot","type":"error"},{"anonymous":false,"inputs":[{"indexed":false,"internalType":"address","name":"account","type":"address"},{"indexed":false,"internalType":"uint256","name":"blockNumber","type":"uint256"},{"indexed":false,"internalType":"uint256","name":"nonce","type":"uint256"},{"indexed":false,"internalType":"uint256","name":"balance","type":"uint256"},{"indexed":false,"internalType":"bytes32","name":"codeHash","type":"bytes32"},{"indexed":false,"internalType":"bytes32","name":"storageHash","type":"bytes32"}],"name":"AccountProven","type":"event"},{"anonymous":false,"inputs":[{"indexed":false,"internalType":"address","name":"account","type":"address"},{"indexed":false,"internalType":"uint256","name":"blockNumber","type":"uint256"},{"indexed":false,"internalType":"bytes32","name":"slot","type":"bytes32"},{"indexed":false,"internalType":"bytes32","name":"slotValue","type":"bytes32"}],"name":"StorageSlotProven","type":"event"},{"inputs":[{"internalType":"address","name":"account","type":"address"},{"internalType":"uint256","name":"blockNumber","type":"uint256"},{"internalType":"enum Types.AccountFields","name":"field","type":"uint8"}],"name":"accountField","outputs":[{"internalType":"bytes32","name":"","type":"bytes32"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"address","name":"account","type":"address"},{"internalType":"uint256","name":"blockNumber","type":"uint256"},{"internalType":"bytes32","name":"slot","type":"bytes32"}],"name":"accountStorageSlotValues","outputs":[{"internalType":"bytes32","name":"","type":"bytes32"}],"stateMutability":"view","type":"function"},{"inputs":[],"name":"headersProcessor","outputs":[{"internalType":"contract HeadersProcessor","name":"","type":"address"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"address","name":"account","type":"address"},{"internalType":"uint16","name":"accountFieldsToSave","type":"uint16"},{"components":[{"internalType":"uint256","name":"treeId","type":"uint256"},{"internalType":"uint256","name":"mmrTreeSize","type":"uint256"},{"internalType":"uint256","name":"blockNumber","type":"uint256"},{"internalType":"uint256","name":"blockProofLeafIndex","type":"uint256"},{"internalType":"bytes32[]","name":"mmrPeaks","type":"bytes32[]"},{"internalType":"bytes32[]","name":"mmrElementInclusionProof","type":"bytes32[]"},{"internalType":"bytes","name":"provenBlockHeader","type":"bytes"}],"internalType":"struct Types.BlockHeaderProof","name":"headerProof","type":"tuple"},{"internalType":"bytes","name":"accountTrieProof","type":"bytes"}],"name":"proveAccount","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[{"internalType":"address","name":"account","type":"address"},{"internalType":"uint256","name":"blockNumber","type":"uint256"},{"internalType":"bytes32","name":"slot","type":"bytes32"},{"internalType":"bytes","name":"storageSlotTrieProof","type":"bytes"}],"name":"proveStorage","outputs":[],"stateMutability":"nonpayable","type":"function"},{"inputs":[{"internalType":"address","name":"account","type":"address"},{"components":[{"internalType":"uint256","name":"treeId","type":"uint256"},{"internalType":"uint256","name":"mmrTreeSize","type":"uint256"},{"internalType":"uint256","name":"blockNumber","type":"uint256"},{"internalType":"uint256","name":"blockProofLeafIndex","type":"uint256"},{"internalType":"bytes32[]","name":"mmrPeaks","type":"bytes32[]"},{"internalType":"bytes32[]","name":"mmrElementInclusionProof","type":"bytes32[]"},{"internalType":"bytes","name":"provenBlockHeader","type":"bytes"}],"internalType":"struct Types.BlockHeaderProof","name":"headerProof","type":"tuple"},{"internalType":"bytes","name":"accountTrieProof","type":"bytes"}],"name":"verifyAccount","outputs":[{"internalType":"uint256","name":"nonce","type":"uint256"},{"internalType":"uint256","name":"accountBalance","type":"uint256"},{"internalType":"bytes32","name":"codeHash","type":"bytes32"},{"internalType":"bytes32","name":"storageRoot","type":"bytes32"}],"stateMutability":"view","type":"function"},{"inputs":[{"internalType":"address","name":"account","type":"address"},{"internalType":"uint256","name":"blockNumber","type":"uint256"},{"internalType":"bytes32","name":"slot","type":"bytes32"},{"internalType":"bytes","name":"storageSlotTrieProof","type":"bytes"}],"name":"verifyStorage","outputs":[{"internalType":"bytes32","name":"slotValue","type":"bytes32"}],"stateMutability":"view","type":"function"}]

60a03461007257601f61239438819003918201601f19168301916001600160401b038311848410176100775780849260209460405283398101031261007257516001600160a01b0381169081900361007257608052604051612306908161008e8239608051818181609c0152610f6d0152f35b600080fd5b634e487b7160e01b600052604160045260246000fdfe6080604052600436101561001257600080fd5b6000803560e01c9081630de5852f1461008a575080632b8926d314610085578063453f768e146100805780637177899b1461007b57806376bd56ae146100765780637e445a26146100715763c4179a141461006c57600080fd5b6103b2565b61035a565b6102e3565b610224565b610188565b610164565b346100ce57806003193601126100ce577f00000000000000000000000000000000000000000000000000000000000000006001600160a01b03166080908152602090f35b80fd5b600435906001600160a01b03821682036100e757565b600080fd5b9181601f840112156100e7578235916001600160401b0383116100e757602083818601950101116100e757565b9060806003198301126100e7576004356001600160a01b03811681036100e757916024359160443591606435906001600160401b0382116100e757610160916004016100ec565b9091565b346100e757602061018061017736610119565b9392909261086d565b604051908152f35b346100e7576101d37f0845af63ce690e816170dc5feb73d2eef78d834186bca7cbb817ca82a3b2b6de60806101ce6101bf36610119565b908284869a959697949761086d565b610e94565b9460018060a01b03169161020a60009684885260016020526040882084895260205260408820838952602052806040892055610bf7565b91604051938452602084015260408301526060820152a180f35b346100e75760603660031901126100e75761023d6100d1565b60443560048110156100e7576102759160018060a01b031660005260006020526040600020602435600052602052604060002061075e565b54801561029c5761028861029891610bf7565b6040519081529081906020820190565b0390f35b60405162461bcd60e51b815260206004820152601160248201527011549497d59053155157d254d7d3955313607a1b6044820152606490fd5b908160e09103126100e75790565b346100e75760603660031901126100e7576102fc6100d1565b6001600160401b036024358181116100e75761031c9036906004016102d5565b6044359182116100e75760809261033a6103429336906004016100ec565b929091610a09565b91604051938452602084015260408301526060820152f35b346100e75760603660031901126100e75760406103756100d1565b6001600160a01b031660009081526001602090815282822060243583528152828220604435835290522054801561029c5761028861029891610bf7565b346100e75760803660031901126100e7576103cb6100d1565b60243561ffff811681036100e757604435906001600160401b03908183116100e7576103fc600493369085016102d5565b916064359081116100e75761041761041f91369086016100ec565b908487610a09565b9291909173ec4f121aa03757102456dca5c4838b97c1207164976040978851966398e6c7c960e01b9a8b895260209889818061046f86888301602060009193929361ffff60408201951681520152565b0381855af490811561062c5760009161072b575b50610705575b8a518c815261ffff8316848201908152600160208201528a90829081906040010381855af490811561062c576000916106e8575b506106a4575b8a51928c84528984806104ea86858301602060029193929361ffff60408201951681520152565b0381855af49c8d1561062c578c8c6105309f8d97600091610687575b50610631575b50519d8e948593849384528301602060039193929361ffff60408201951681520152565b03915af4801561062c577fb8bebe019326a508bc23d223af9d4b0b39fc6b8d7a12c2a902782e6feaad8c72996105a7976000926105ff575b50506105ac575b8751978897013590879260a094919796959260c0850198600180881b0316855260208501526040840152606083015260808201520152565b0390a1005b6105b585610e94565b6105f96105e96105d78460018060a01b03166000526000602052604060002090565b8b8b0135600052602052604060002090565b6002600052602052604060002090565b5561056f565b61061e9250803d10610625575b61061681836107cc565b810190610b8a565b3880610568565b503d61060c565b6109fd565b61066f61067f916106418d610e94565b9361065e8b60018060a01b03166000526000602052604060002090565b910135600052602052604060002090565b6003600052602052604060002090565b558c8c61050c565b61069e9150883d8a116106255761061681836107cc565b38610506565b8a6106e26106d28c6106b58a610e94565b9361065e8960018060a01b03166000526000602052604060002090565b6001600052602052604060002090565b556104c3565b6106ff91508a3d8c116106255761061681836107cc565b386104bd565b8a6107256107168c6106b589610e94565b60008052602052604060002090565b55610489565b61074291508a3d8c116106255761061681836107cc565b38610483565b634e487b7160e01b600052602160045260246000fd5b90600481101561077657600052602052604060002090565b610748565b634e487b7160e01b600052604160045260246000fd5b604081019081106001600160401b038211176107ac57604052565b61077b565b602081019081106001600160401b038211176107ac57604052565b90601f801991011681019081106001600160401b038211176107ac57604052565b6040519060e082018281106001600160401b038211176107ac57604052565b6040519061081982610791565b565b6001600160401b0381116107ac57601f01601f191660200190565b9291926108428261081b565b9161085060405193846107cc565b8294818452818301116100e7578281602093846000960137010152565b916108cc6108d9946108ae60406108d2966108de999660009160018060a01b0316825281602052828220908252602052818120600282526020522054610bf7565b93604051936020850152602084526108c584610791565b3691610836565b90610c67565b9050610db3565b610e40565b90565b6001600160401b0381116107ac5760051b60200190565b9080601f830112156100e7576020908235610912816108e1565b9361092060405195866107cc565b81855260208086019260051b8201019283116100e757602001905b828210610949575050505090565b8135815290830190830161093b565b9080601f830112156100e7578160206108de93359101610836565b903590601e19813603018212156100e757018035906001600160401b0382116100e7576020019181360383136100e757565b908160209103126100e7575190565b6020808252825181830181905290939260005b8281106109e957505060409293506000838284010152601f8019910116010190565b8181018601518482016040015285016109c7565b6040513d6000823e3d90fd5b9160e0823603126100e757610a1c6107ed565b92823584526020928381013584860152604081013560408601526060810135606086015260808101356001600160401b03908181116100e757610a6290369084016108f8565b608087015260a08201358181116100e757610a8090369084016108f8565b60a087015260c082019586359182116100e757610ad9968693610aba6108c593610ab0610abf9636908501610958565b60c0820152610f38565b610973565b604051809681926374d3f00f60e11b8352600483016109b4565b038173e2712d15267c29b2c6f6b5127621750f11d51e1c5af491821561062c57610b4e95610b4895600094610b53575b506108c56108cc939495610b3a60405196879283016014916bffffffffffffffffffffffff199060601b1681520190565b03601f1981018652856107cc565b906110ba565b919293565b6108cc939450610b7b6108c591873d8911610b83575b610b7381836107cc565b8101906109a5565b949350610b09565b503d610b69565b908160209103126100e7575180151581036100e75790565b634e487b7160e01b600052601160045260246000fd5b600019810191908211610bc757565b610ba2565b600119810191908211610bc757565b600219810191908211610bc757565b91908203918211610bc757565b8015610c1757600019818114610c13578101908111610bc75790565b5090565b60405162461bcd60e51b815260206004820152602260248201527f4e756c6c61626c6553746f72616765536c6f743a2076616c7565206973206e756044820152611b1b60f21b6064820152608490fd5b92919091610c98610c938551602080970120946040519587870152868652610c8e86610791565b610db3565b61172f565b90815192610ca5846108e1565b93610cb360405195866107cc565b808552610cc2601f19916108e1565b018660005b828110610d845750505060005b8351811015610d2a5780610cf3610ced600193876110a6565b51611c6b565b610cff610c9382610db3565b610d0761080c565b91825289820152610d1882886110a6565b52610d2381876110a6565b5001610cd4565b509093610d509550610d3d92508361192c565b9490511580958115610d7c575b5061116a565b8315610d72576108de91610d66610d6c92610bb8565b906110a6565b51611c07565b50506108de6111b6565b905038610d4a565b610d8c611819565b828289010152018790610cc7565b60405190610da782610791565b60006020838281520152565b610dbb610d9a565b50602081519160405192610dce84610791565b835201602082015290565b15610de057565b60405162461bcd60e51b815260206004820152601a60248201527f496e76616c696420524c5020627974657333322076616c75652e0000000000006044820152606490fd5b9060018201809211610bc757565b91908201809211610bc757565b610e4e602182511115610dd9565b610e57816113d6565b9092600282101561077657610e6e60209215610dd9565b0151908101809111610bc757519060208110610e88575090565b6020036101000a900490565b60001981146108de5760018101809111610bc75790565b15610eb257565b60405162461bcd60e51b815260206004820152601260248201527111549497d15354151657d3535497d493d3d560721b6044820152606490fd5b15610ef357565b60405162461bcd60e51b815260206004820152601860248201527f4552525f494e56414c49445f424c4f434b5f4e554d42455200000000000000006044820152606490fd5b80516020808301805160405163fc50b6f360e01b81526004810194909452602484015290929083836044816001600160a01b037f0000000000000000000000000000000000000000000000000000000000000000165afa90811561062c57610fda8592610ff595600091611051575b50610fb3811515610eab565b60c085019283518581519101209060608701519160a08801519060808901519251936114ce565b51604051809481926310862ffb60e11b8352600483016109b4565b038173e2712d15267c29b2c6f6b5127621750f11d51e1c5af491821561062c576108199360009361102d575b50506040015114610eec565b6040929350908161104992903d10610b8357610b7381836107cc565b919038611021565b6110689150843d8611610b8357610b7381836107cc565b38610fa7565b634e487b7160e01b600052603260045260246000fd5b8051156110915760200190565b61106e565b8051600110156110915760400190565b80518210156110915760209160051b010190565b1561111d57610c936110cb91610db3565b6110dd6110d782611084565b51610e40565b916110ea6110d783611096565b91805160031015611091576111026080820151610e40565b9080516002101561109157606061111a910151610e40565b91565b506000906000907f56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421907fc5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a47090565b1561117157565b60405162461bcd60e51b815260206004820152601a60248201527f50726f76696465642070726f6f6620697320696e76616c69642e0000000000006044820152606490fd5b604051906111c3826107b1565b60008252565b156111d057565b60405162461bcd60e51b815260206004820152601860248201527f524c50206974656d2063616e6e6f74206265206e756c6c2e00000000000000006044820152606490fd5b1561121c57565b60405162461bcd60e51b815260206004820152601d60248201527f496e76616c696420524c50206c6f6e67206c697374206c656e6774682e0000006044820152606490fd5b1561126857565b60405162461bcd60e51b815260206004820152601660248201527524b73b30b634b210292628103637b733903634b9ba1760511b6044820152606490fd5b156112ad57565b60405162461bcd60e51b815260206004820152601760248201527f496e76616c696420524c502073686f7274206c6973742e0000000000000000006044820152606490fd5b156112f957565b60405162461bcd60e51b815260206004820152601f60248201527f496e76616c696420524c50206c6f6e6720737472696e67206c656e6774682e006044820152606490fd5b1561134557565b60405162461bcd60e51b815260206004820152601860248201527f496e76616c696420524c50206c6f6e6720737472696e672e00000000000000006044820152606490fd5b1561139157565b60405162461bcd60e51b815260206004820152601960248201527f496e76616c696420524c502073686f727420737472696e672e000000000000006044820152606490fd5b906113e3825115156111c9565b6020820151805160001a90607f8211611403575060009250600191839150565b60b78211611426575061141d90607f19018093511161138a565b60019190600090565b60bf821161146d576114629060b619906114448285018751116112f2565b600160b785602003016101000a91015104945190858401011061133e565b60b519019190600090565b60f7821161148f57506114879060bf1901809351116112a6565b600191908290565b6114c39060f619906114a5828501875111611215565b600160f785602003016101000a910151049451908584010110611261565b60f519019190600190565b95939091949294818711611627576114e586611f32565b91604094604051918261150c60209660208301938460209093929193604081019481520152565b0392611520601f19948581018352826107cc565b519020036116155792969260009161153f61153a86610bb8565b612249565b966000975b82518910156115e15785908861155a8b866110a6565b5160019d8e946115a69385871687036115b35751908101928352602083019190915261159f919061159681604084015b038a81018352826107cc565b51902099610e25565b9896611c27565b9b1c980197999399611544565b51908101918252602082019290925261159f916115d3816040840161158a565b519020996002891b90610e33565b50989450505050506115f992506115fd939150611c36565b1590565b61160357565b6040516309bde33960e01b8152600490fd5b60405163504570e360e01b8152600490fd5b604051634e23d03560e01b8152600490fd5b1561164057565b60405162461bcd60e51b815260206004820152601760248201527f496e76616c696420524c50206c6973742076616c75652e0000000000000000006044820152606490fd5b6040519061042082018281106001600160401b038211176107ac5760405260208083528260005b61040081106116ba57505050565b82906116c4610d9a565b828285010152016116ac565b156116d757565b60405162461bcd60e51b815260206004820152602a60248201527f50726f766964656420524c50206c6973742065786365656473206d6178206c6960448201526939ba103632b733ba341760b11b6064820152608490fd5b611738816113d6565b9290506002831015610776576117516001809414611639565b611759611685565b92600092815b61176c575b505050815290565b82518110156118145761180e9061180860209561178a8782106116d0565b611802611798848851610bea565b916117bf898901936117ab878651610e33565b6117b361080c565b9182528b8201526113d6565b509390996117d8876117d18d88610e33565b9351610e33565b906117e161080c565b9283528201526117f1828c6110a6565b526117fc818b6110a6565b50610e25565b96610e33565b90610e33565b8161175f565b611764565b6040519061182682610791565b60606020838281520152565b1561183957565b60405162461bcd60e51b815260206004820152601a60248201527f496e76616c696420696e7465726e616c206e6f646520686173680000000000006044820152606490fd5b1561188557565b60405162461bcd60e51b815260206004820152601b60248201527f496e76616c6964206c6172676520696e7465726e616c206861736800000000006044820152606490fd5b156118d157565b60405162461bcd60e51b8152602060048201526011602482015270092dcecc2d8d2c840e4dedee840d0c2e6d607b1b6044820152606490fd5b908151811015611091570160200190565b60ff166002039060ff8211610bc757565b9290611939600091611d08565b81948290611945611819565b5083915b8151831015611bf95761196a6119709161196385856110a6565b5199610e33565b94610e25565b9684611bbe5761198987825160208151910120146118ca565b60208101805151909160118203611a0d575050835185036119bb57505050906119b191611dcc565b91600160ff1b1490565b6119ff919296506119f99060ff6119ef6119e96119db89899d9a9d61190a565b516001600160f81b03191690565b60f81c90565b91519116906110a6565b51611edc565b94600180915b019190611949565b9497506002959491939291908603611b7957611a2890611dac565b91611a386119e96119db85611084565b93611a59600194611a53611a4d87891661191b565b60ff1690565b90611dcc565b96611a64878b611dcc565b9460ff611a71878b611e7c565b97169182148015611b6f575b15611ac357505050505081806119b19551149182611ab8575b5050611aa9575b50600160ff1b93611dcc565b611ab291610e33565b38611a9d565b511490508138611a96565b9193959697508092945015918215611b65575b505015611b115783611af557505050506119b190600160ff1b93611dcc565b611b0a6119f960019299969998959851611096565b9691611a05565b60405162461bcd60e51b815260206004820152602660248201527f52656365697665642061206e6f6465207769746820616e20756e6b6e6f776e206044820152650e0e4caccd2f60d31b6064820152608490fd5b1490503880611ad6565b5060038214611a7d565b60405162461bcd60e51b815260206004820152601d60248201527f526563656976656420616e20756e706172736561626c65206e6f64652e0000006044820152606490fd5b80518760208083511015600014611be65783518051910120611be192501461187e565b611989565b50611bf3611be192611d87565b14611832565b505050936119b19194611dcc565b602001518051600019810191908211610bc7576108de91610ced916110a6565b6000198114610bc75760010190565b60005b8251811015611c635781611c4d82856110a6565b5114611c5b57600101611c39565b505050600190565b505050600090565b611c74816113d6565b600281939293101561077657611c915760206108de9301516120fe565b60405162461bcd60e51b815260206004820152601860248201527f496e76616c696420524c502062797465732076616c75652e00000000000000006044820152606490fd5b90611ce08261081b565b611ced60405191826107cc565b8281528092611cfe601f199161081b565b0190602036910137565b611d1a8151600191829160011b611cd6565b92600080925b611d2c575b5050505090565b8151831015611d825783928390600f60f81b611d7a8382611d4d858961190a565b5160041c169284821b93871a611d63858d61190a565b53611d6e858961190a565b5116861a92018961190a565b530192611d20565b611d25565b80519060208210611da3576020806108de9383010191016109a5565b60209150015190565b6020015180511561109157611dc760206108de920151611c6b565b611d08565b9080825114611e675781518180820391611deb83601f81011015612166565b611e06838301611dfd84821015612166565b865110156121a3565b03611e1f57505050604051600081526020810160405290565b60405192601f821692831560051b80858701019484860193010101905b808410611e545750508252601f01601f191660405290565b9092835181526020809101930190611e3c565b5050604051611e75816107b1565b6000815290565b60005b8082511180611ed2575b80611ea8575b15611ea257611e9d90611c27565b611e7f565b91505090565b506001600160f81b031980611ebd838561190a565b511690611eca838661190a565b511614611e8f565b5080835111611e89565b6108de906020815110600014611f015760208101519051611efc91612099565b611d87565b611efc90611c6b565b90611f14826108e1565b611f2160405191826107cc565b8281528092611cfe601f19916108e1565b906001918281511061208757828151146120785782815191611f5c611f5684610bcc565b826110a6565b51611f6f611f6985610bb8565b836110a6565b51604080516020808201948552818301939093528181529093601f19939091611f996060826107cc565b51902090611fae611fa988610bcc565b611f0a565b966000995b612026575b509697509550600094845b611fd1575b50505050505090565b80518610156120215784869761200a612016611fee849a866110a6565b5188518781019182526020820194909452929182906040850190565b038781018352826107cc565b519020970195611fc3565b611fc8565b6120338199989799610bcc565b8a101561206f57888a61205c612056839d612051869e9c9d9e610bdb565b610bea565b856110a6565b51612067828c6110a6565b520199611fb3565b97959697611fb8565b612083919250611084565b5190565b604051638355f42560e01b8152600490fd5b906120a381611cd6565b918251156120f95760209160208401926000905b8260051c82106120e2575050601f60001991166020036101000a019081835116911990511617905290565b9093928180826001935187520194019401906120b7565b505090565b919061210982611cd6565b92835115612160570160209160208401926000905b8260051c8210612149575050601f60001991166020036101000a019081835116911990511617905290565b90939281808260019351875201940194019061211e565b50505090565b1561216d57565b60405162461bcd60e51b815260206004820152600e60248201526d736c6963655f6f766572666c6f7760901b6044820152606490fd5b156121aa57565b60405162461bcd60e51b8152602060048201526011602482015270736c6963655f6f75744f66426f756e647360781b6044820152606490fd5b156121ea57565b60405162461bcd60e51b815260206004820152603160248201527f6d6d7253697a652063616e2774206265206173736f636961746564207769746860448201527020612076616c6964204d4d522073697a6560781b6064820152608490fd5b6000906001825b818310156122bb57600191501b805b61226e57506108de90156121e3565b6001600160ff1b0381168103610bc75761228a8160011b610bb8565b8281111561229d575b5060011c8061225f565b818492939401809211610bc7576122b49193610bea565b9038612293565b60018101809111610bc7579060011b9061225056fea2646970667358221220430455d06558d7a0bb1a96ce01600f0b30e7e04df1ae9c74339ec6aac0ca2f4064736f6c6343000818003300000000000000000000000032d0256c4bff711444f50be6c254114e22029f2c

0x6080604052600436101561001257600080fd5b6000803560e01c9081630de5852f1461008a575080632b8926d314610085578063453f768e146100805780637177899b1461007b57806376bd56ae146100765780637e445a26146100715763c4179a141461006c57600080fd5b6103b2565b61035a565b6102e3565b610224565b610188565b610164565b346100ce57806003193601126100ce577f00000000000000000000000032d0256c4bff711444f50be6c254114e22029f2c6001600160a01b03166080908152602090f35b80fd5b600435906001600160a01b03821682036100e757565b600080fd5b9181601f840112156100e7578235916001600160401b0383116100e757602083818601950101116100e757565b9060806003198301126100e7576004356001600160a01b03811681036100e757916024359160443591606435906001600160401b0382116100e757610160916004016100ec565b9091565b346100e757602061018061017736610119565b9392909261086d565b604051908152f35b346100e7576101d37f0845af63ce690e816170dc5feb73d2eef78d834186bca7cbb817ca82a3b2b6de60806101ce6101bf36610119565b908284869a959697949761086d565b610e94565b9460018060a01b03169161020a60009684885260016020526040882084895260205260408820838952602052806040892055610bf7565b91604051938452602084015260408301526060820152a180f35b346100e75760603660031901126100e75761023d6100d1565b60443560048110156100e7576102759160018060a01b031660005260006020526040600020602435600052602052604060002061075e565b54801561029c5761028861029891610bf7565b6040519081529081906020820190565b0390f35b60405162461bcd60e51b815260206004820152601160248201527011549497d59053155157d254d7d3955313607a1b6044820152606490fd5b908160e09103126100e75790565b346100e75760603660031901126100e7576102fc6100d1565b6001600160401b036024358181116100e75761031c9036906004016102d5565b6044359182116100e75760809261033a6103429336906004016100ec565b929091610a09565b91604051938452602084015260408301526060820152f35b346100e75760603660031901126100e75760406103756100d1565b6001600160a01b031660009081526001602090815282822060243583528152828220604435835290522054801561029c5761028861029891610bf7565b346100e75760803660031901126100e7576103cb6100d1565b60243561ffff811681036100e757604435906001600160401b03908183116100e7576103fc600493369085016102d5565b916064359081116100e75761041761041f91369086016100ec565b908487610a09565b9291909173ec4f121aa03757102456dca5c4838b97c1207164976040978851966398e6c7c960e01b9a8b895260209889818061046f86888301602060009193929361ffff60408201951681520152565b0381855af490811561062c5760009161072b575b50610705575b8a518c815261ffff8316848201908152600160208201528a90829081906040010381855af490811561062c576000916106e8575b506106a4575b8a51928c84528984806104ea86858301602060029193929361ffff60408201951681520152565b0381855af49c8d1561062c578c8c6105309f8d97600091610687575b50610631575b50519d8e948593849384528301602060039193929361ffff60408201951681520152565b03915af4801561062c577fb8bebe019326a508bc23d223af9d4b0b39fc6b8d7a12c2a902782e6feaad8c72996105a7976000926105ff575b50506105ac575b8751978897013590879260a094919796959260c0850198600180881b0316855260208501526040840152606083015260808201520152565b0390a1005b6105b585610e94565b6105f96105e96105d78460018060a01b03166000526000602052604060002090565b8b8b0135600052602052604060002090565b6002600052602052604060002090565b5561056f565b61061e9250803d10610625575b61061681836107cc565b810190610b8a565b3880610568565b503d61060c565b6109fd565b61066f61067f916106418d610e94565b9361065e8b60018060a01b03166000526000602052604060002090565b910135600052602052604060002090565b6003600052602052604060002090565b558c8c61050c565b61069e9150883d8a116106255761061681836107cc565b38610506565b8a6106e26106d28c6106b58a610e94565b9361065e8960018060a01b03166000526000602052604060002090565b6001600052602052604060002090565b556104c3565b6106ff91508a3d8c116106255761061681836107cc565b386104bd565b8a6107256107168c6106b589610e94565b60008052602052604060002090565b55610489565b61074291508a3d8c116106255761061681836107cc565b38610483565b634e487b7160e01b600052602160045260246000fd5b90600481101561077657600052602052604060002090565b610748565b634e487b7160e01b600052604160045260246000fd5b604081019081106001600160401b038211176107ac57604052565b61077b565b602081019081106001600160401b038211176107ac57604052565b90601f801991011681019081106001600160401b038211176107ac57604052565b6040519060e082018281106001600160401b038211176107ac57604052565b6040519061081982610791565b565b6001600160401b0381116107ac57601f01601f191660200190565b9291926108428261081b565b9161085060405193846107cc565b8294818452818301116100e7578281602093846000960137010152565b916108cc6108d9946108ae60406108d2966108de999660009160018060a01b0316825281602052828220908252602052818120600282526020522054610bf7565b93604051936020850152602084526108c584610791565b3691610836565b90610c67565b9050610db3565b610e40565b90565b6001600160401b0381116107ac5760051b60200190565b9080601f830112156100e7576020908235610912816108e1565b9361092060405195866107cc565b81855260208086019260051b8201019283116100e757602001905b828210610949575050505090565b8135815290830190830161093b565b9080601f830112156100e7578160206108de93359101610836565b903590601e19813603018212156100e757018035906001600160401b0382116100e7576020019181360383136100e757565b908160209103126100e7575190565b6020808252825181830181905290939260005b8281106109e957505060409293506000838284010152601f8019910116010190565b8181018601518482016040015285016109c7565b6040513d6000823e3d90fd5b9160e0823603126100e757610a1c6107ed565b92823584526020928381013584860152604081013560408601526060810135606086015260808101356001600160401b03908181116100e757610a6290369084016108f8565b608087015260a08201358181116100e757610a8090369084016108f8565b60a087015260c082019586359182116100e757610ad9968693610aba6108c593610ab0610abf9636908501610958565b60c0820152610f38565b610973565b604051809681926374d3f00f60e11b8352600483016109b4565b038173e2712d15267c29b2c6f6b5127621750f11d51e1c5af491821561062c57610b4e95610b4895600094610b53575b506108c56108cc939495610b3a60405196879283016014916bffffffffffffffffffffffff199060601b1681520190565b03601f1981018652856107cc565b906110ba565b919293565b6108cc939450610b7b6108c591873d8911610b83575b610b7381836107cc565b8101906109a5565b949350610b09565b503d610b69565b908160209103126100e7575180151581036100e75790565b634e487b7160e01b600052601160045260246000fd5b600019810191908211610bc757565b610ba2565b600119810191908211610bc757565b600219810191908211610bc757565b91908203918211610bc757565b8015610c1757600019818114610c13578101908111610bc75790565b5090565b60405162461bcd60e51b815260206004820152602260248201527f4e756c6c61626c6553746f72616765536c6f743a2076616c7565206973206e756044820152611b1b60f21b6064820152608490fd5b92919091610c98610c938551602080970120946040519587870152868652610c8e86610791565b610db3565b61172f565b90815192610ca5846108e1565b93610cb360405195866107cc565b808552610cc2601f19916108e1565b018660005b828110610d845750505060005b8351811015610d2a5780610cf3610ced600193876110a6565b51611c6b565b610cff610c9382610db3565b610d0761080c565b91825289820152610d1882886110a6565b52610d2381876110a6565b5001610cd4565b509093610d509550610d3d92508361192c565b9490511580958115610d7c575b5061116a565b8315610d72576108de91610d66610d6c92610bb8565b906110a6565b51611c07565b50506108de6111b6565b905038610d4a565b610d8c611819565b828289010152018790610cc7565b60405190610da782610791565b60006020838281520152565b610dbb610d9a565b50602081519160405192610dce84610791565b835201602082015290565b15610de057565b60405162461bcd60e51b815260206004820152601a60248201527f496e76616c696420524c5020627974657333322076616c75652e0000000000006044820152606490fd5b9060018201809211610bc757565b91908201809211610bc757565b610e4e602182511115610dd9565b610e57816113d6565b9092600282101561077657610e6e60209215610dd9565b0151908101809111610bc757519060208110610e88575090565b6020036101000a900490565b60001981146108de5760018101809111610bc75790565b15610eb257565b60405162461bcd60e51b815260206004820152601260248201527111549497d15354151657d3535497d493d3d560721b6044820152606490fd5b15610ef357565b60405162461bcd60e51b815260206004820152601860248201527f4552525f494e56414c49445f424c4f434b5f4e554d42455200000000000000006044820152606490fd5b80516020808301805160405163fc50b6f360e01b81526004810194909452602484015290929083836044816001600160a01b037f00000000000000000000000032d0256c4bff711444f50be6c254114e22029f2c165afa90811561062c57610fda8592610ff595600091611051575b50610fb3811515610eab565b60c085019283518581519101209060608701519160a08801519060808901519251936114ce565b51604051809481926310862ffb60e11b8352600483016109b4565b038173e2712d15267c29b2c6f6b5127621750f11d51e1c5af491821561062c576108199360009361102d575b50506040015114610eec565b6040929350908161104992903d10610b8357610b7381836107cc565b919038611021565b6110689150843d8611610b8357610b7381836107cc565b38610fa7565b634e487b7160e01b600052603260045260246000fd5b8051156110915760200190565b61106e565b8051600110156110915760400190565b80518210156110915760209160051b010190565b1561111d57610c936110cb91610db3565b6110dd6110d782611084565b51610e40565b916110ea6110d783611096565b91805160031015611091576111026080820151610e40565b9080516002101561109157606061111a910151610e40565b91565b506000906000907f56e81f171bcc55a6ff8345e692c0f86e5b48e01b996cadc001622fb5e363b421907fc5d2460186f7233c927e7db2dcc703c0e500b653ca82273b7bfad8045d85a47090565b1561117157565b60405162461bcd60e51b815260206004820152601a60248201527f50726f76696465642070726f6f6620697320696e76616c69642e0000000000006044820152606490fd5b604051906111c3826107b1565b60008252565b156111d057565b60405162461bcd60e51b815260206004820152601860248201527f524c50206974656d2063616e6e6f74206265206e756c6c2e00000000000000006044820152606490fd5b1561121c57565b60405162461bcd60e51b815260206004820152601d60248201527f496e76616c696420524c50206c6f6e67206c697374206c656e6774682e0000006044820152606490fd5b1561126857565b60405162461bcd60e51b815260206004820152601660248201527524b73b30b634b210292628103637b733903634b9ba1760511b6044820152606490fd5b156112ad57565b60405162461bcd60e51b815260206004820152601760248201527f496e76616c696420524c502073686f7274206c6973742e0000000000000000006044820152606490fd5b156112f957565b60405162461bcd60e51b815260206004820152601f60248201527f496e76616c696420524c50206c6f6e6720737472696e67206c656e6774682e006044820152606490fd5b1561134557565b60405162461bcd60e51b815260206004820152601860248201527f496e76616c696420524c50206c6f6e6720737472696e672e00000000000000006044820152606490fd5b1561139157565b60405162461bcd60e51b815260206004820152601960248201527f496e76616c696420524c502073686f727420737472696e672e000000000000006044820152606490fd5b906113e3825115156111c9565b6020820151805160001a90607f8211611403575060009250600191839150565b60b78211611426575061141d90607f19018093511161138a565b60019190600090565b60bf821161146d576114629060b619906114448285018751116112f2565b600160b785602003016101000a91015104945190858401011061133e565b60b519019190600090565b60f7821161148f57506114879060bf1901809351116112a6565b600191908290565b6114c39060f619906114a5828501875111611215565b600160f785602003016101000a910151049451908584010110611261565b60f519019190600190565b95939091949294818711611627576114e586611f32565b91604094604051918261150c60209660208301938460209093929193604081019481520152565b0392611520601f19948581018352826107cc565b519020036116155792969260009161153f61153a86610bb8565b612249565b966000975b82518910156115e15785908861155a8b866110a6565b5160019d8e946115a69385871687036115b35751908101928352602083019190915261159f919061159681604084015b038a81018352826107cc565b51902099610e25565b9896611c27565b9b1c980197999399611544565b51908101918252602082019290925261159f916115d3816040840161158a565b519020996002891b90610e33565b50989450505050506115f992506115fd939150611c36565b1590565b61160357565b6040516309bde33960e01b8152600490fd5b60405163504570e360e01b8152600490fd5b604051634e23d03560e01b8152600490fd5b1561164057565b60405162461bcd60e51b815260206004820152601760248201527f496e76616c696420524c50206c6973742076616c75652e0000000000000000006044820152606490fd5b6040519061042082018281106001600160401b038211176107ac5760405260208083528260005b61040081106116ba57505050565b82906116c4610d9a565b828285010152016116ac565b156116d757565b60405162461bcd60e51b815260206004820152602a60248201527f50726f766964656420524c50206c6973742065786365656473206d6178206c6960448201526939ba103632b733ba341760b11b6064820152608490fd5b611738816113d6565b9290506002831015610776576117516001809414611639565b611759611685565b92600092815b61176c575b505050815290565b82518110156118145761180e9061180860209561178a8782106116d0565b611802611798848851610bea565b916117bf898901936117ab878651610e33565b6117b361080c565b9182528b8201526113d6565b509390996117d8876117d18d88610e33565b9351610e33565b906117e161080c565b9283528201526117f1828c6110a6565b526117fc818b6110a6565b50610e25565b96610e33565b90610e33565b8161175f565b611764565b6040519061182682610791565b60606020838281520152565b1561183957565b60405162461bcd60e51b815260206004820152601a60248201527f496e76616c696420696e7465726e616c206e6f646520686173680000000000006044820152606490fd5b1561188557565b60405162461bcd60e51b815260206004820152601b60248201527f496e76616c6964206c6172676520696e7465726e616c206861736800000000006044820152606490fd5b156118d157565b60405162461bcd60e51b8152602060048201526011602482015270092dcecc2d8d2c840e4dedee840d0c2e6d607b1b6044820152606490fd5b908151811015611091570160200190565b60ff166002039060ff8211610bc757565b9290611939600091611d08565b81948290611945611819565b5083915b8151831015611bf95761196a6119709161196385856110a6565b5199610e33565b94610e25565b9684611bbe5761198987825160208151910120146118ca565b60208101805151909160118203611a0d575050835185036119bb57505050906119b191611dcc565b91600160ff1b1490565b6119ff919296506119f99060ff6119ef6119e96119db89899d9a9d61190a565b516001600160f81b03191690565b60f81c90565b91519116906110a6565b51611edc565b94600180915b019190611949565b9497506002959491939291908603611b7957611a2890611dac565b91611a386119e96119db85611084565b93611a59600194611a53611a4d87891661191b565b60ff1690565b90611dcc565b96611a64878b611dcc565b9460ff611a71878b611e7c565b97169182148015611b6f575b15611ac357505050505081806119b19551149182611ab8575b5050611aa9575b50600160ff1b93611dcc565b611ab291610e33565b38611a9d565b511490508138611a96565b9193959697508092945015918215611b65575b505015611b115783611af557505050506119b190600160ff1b93611dcc565b611b0a6119f960019299969998959851611096565b9691611a05565b60405162461bcd60e51b815260206004820152602660248201527f52656365697665642061206e6f6465207769746820616e20756e6b6e6f776e206044820152650e0e4caccd2f60d31b6064820152608490fd5b1490503880611ad6565b5060038214611a7d565b60405162461bcd60e51b815260206004820152601d60248201527f526563656976656420616e20756e706172736561626c65206e6f64652e0000006044820152606490fd5b80518760208083511015600014611be65783518051910120611be192501461187e565b611989565b50611bf3611be192611d87565b14611832565b505050936119b19194611dcc565b602001518051600019810191908211610bc7576108de91610ced916110a6565b6000198114610bc75760010190565b60005b8251811015611c635781611c4d82856110a6565b5114611c5b57600101611c39565b505050600190565b505050600090565b611c74816113d6565b600281939293101561077657611c915760206108de9301516120fe565b60405162461bcd60e51b815260206004820152601860248201527f496e76616c696420524c502062797465732076616c75652e00000000000000006044820152606490fd5b90611ce08261081b565b611ced60405191826107cc565b8281528092611cfe601f199161081b565b0190602036910137565b611d1a8151600191829160011b611cd6565b92600080925b611d2c575b5050505090565b8151831015611d825783928390600f60f81b611d7a8382611d4d858961190a565b5160041c169284821b93871a611d63858d61190a565b53611d6e858961190a565b5116861a92018961190a565b530192611d20565b611d25565b80519060208210611da3576020806108de9383010191016109a5565b60209150015190565b6020015180511561109157611dc760206108de920151611c6b565b611d08565b9080825114611e675781518180820391611deb83601f81011015612166565b611e06838301611dfd84821015612166565b865110156121a3565b03611e1f57505050604051600081526020810160405290565b60405192601f821692831560051b80858701019484860193010101905b808410611e545750508252601f01601f191660405290565b9092835181526020809101930190611e3c565b5050604051611e75816107b1565b6000815290565b60005b8082511180611ed2575b80611ea8575b15611ea257611e9d90611c27565b611e7f565b91505090565b506001600160f81b031980611ebd838561190a565b511690611eca838661190a565b511614611e8f565b5080835111611e89565b6108de906020815110600014611f015760208101519051611efc91612099565b611d87565b611efc90611c6b565b90611f14826108e1565b611f2160405191826107cc565b8281528092611cfe601f19916108e1565b906001918281511061208757828151146120785782815191611f5c611f5684610bcc565b826110a6565b51611f6f611f6985610bb8565b836110a6565b51604080516020808201948552818301939093528181529093601f19939091611f996060826107cc565b51902090611fae611fa988610bcc565b611f0a565b966000995b612026575b509697509550600094845b611fd1575b50505050505090565b80518610156120215784869761200a612016611fee849a866110a6565b5188518781019182526020820194909452929182906040850190565b038781018352826107cc565b519020970195611fc3565b611fc8565b6120338199989799610bcc565b8a101561206f57888a61205c612056839d612051869e9c9d9e610bdb565b610bea565b856110a6565b51612067828c6110a6565b520199611fb3565b97959697611fb8565b612083919250611084565b5190565b604051638355f42560e01b8152600490fd5b906120a381611cd6565b918251156120f95760209160208401926000905b8260051c82106120e2575050601f60001991166020036101000a019081835116911990511617905290565b9093928180826001935187520194019401906120b7565b505090565b919061210982611cd6565b92835115612160570160209160208401926000905b8260051c8210612149575050601f60001991166020036101000a019081835116911990511617905290565b90939281808260019351875201940194019061211e565b50505090565b1561216d57565b60405162461bcd60e51b815260206004820152600e60248201526d736c6963655f6f766572666c6f7760901b6044820152606490fd5b156121aa57565b60405162461bcd60e51b8152602060048201526011602482015270736c6963655f6f75744f66426f756e647360781b6044820152606490fd5b156121ea57565b60405162461bcd60e51b815260206004820152603160248201527f6d6d7253697a652063616e2774206265206173736f636961746564207769746860448201527020612076616c6964204d4d522073697a6560781b6064820152608490fd5b6000906001825b818310156122bb57600191501b805b61226e57506108de90156121e3565b6001600160ff1b0381168103610bc75761228a8160011b610bb8565b8281111561229d575b5060011c8061225f565b818492939401809211610bc7576122b49193610bea565b9038612293565b60018101809111610bc7579060011b9061225056fea2646970667358221220430455d06558d7a0bb1a96ce01600f0b30e7e04df1ae9c74339ec6aac0ca2f4064736f6c63430008180033

00000000000000000000000032d0256c4bff711444f50be6c254114e22029f2c

-----Decoded View---------------
Arg [0] : _headersProcessor (address): 0x32D0256C4bFf711444f50bE6c254114e22029f2c

-----Encoded View---------------
1 Constructor Arguments found :
Arg [0] : 00000000000000000000000032d0256c4bff711444f50be6c254114e22029f2c