// SPDX-License-Identifier: MIT
pragma solidity >0.7.5;
pragma experimental ABIEncoderV2;
/* Interface Imports */
import {IL1CrossDomainMessenger} from './IL1CrossDomainMessenger.sol';
/* Library Imports */
import {Lib_AddressResolver} from '../../libraries/resolver/Lib_AddressResolver.sol';
/**
 * @title L1MultiMessageRelayer
 * @dev The L1 Multi-Message Relayer contract is a gas efficiency optimization which enables the
 * relayer to submit multiple messages in a single transaction to be relayed by the L1 Cross Domain
 * Message Sender.
 *
 * Compiler used: solc
 * Runtime target: EVM
 */
contract L1MultiMessageRelayer is Lib_AddressResolver {
  /***************
   * Structure *
   ***************/
  struct L2ToL1Message {
    address target;
    address sender;
    bytes message;
    uint256 messageNonce;
    IL1CrossDomainMessenger.L2MessageInclusionProof proof;
  }
  /***************
   * Constructor *
   ***************/
  /**
   * @param _libAddressManager Address of the Address Manager.
   */
  constructor(address _libAddressManager)
    Lib_AddressResolver(_libAddressManager)
  {}
  /**********************
   * Function Modifiers *
   **********************/
  modifier onlyBatchRelayer() {
    require(
      msg.sender == resolve('L2BatchMessageRelayer'),
      // solhint-disable-next-line max-line-length
      'L1MultiMessageRelayer: Function can only be called by the L2BatchMessageRelayer'
    );
    _;
  }
  /********************
   * Public Functions *
   ********************/
  /**
   * @notice Forwards multiple cross domain messages to the L1 Cross Domain Messenger for relaying
   * @param _messages An array of L2 to L1 messages
   */
  function batchRelayMessages(L2ToL1Message[] calldata _messages)
    external
    onlyBatchRelayer
  {
    IL1CrossDomainMessenger messenger = IL1CrossDomainMessenger(
      resolve('Proxy__L1CrossDomainMessenger')
    );
    for (uint256 i = 0; i < _messages.length; i++) {
      L2ToL1Message memory message = _messages[i];
      messenger.relayMessage(
        message.target,
        message.sender,
        message.message,
        message.messageNonce,
        message.proof
      );
    }
  }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/* Library Imports */
import {Lib_OVMCodec} from '../../libraries/codec/Lib_OVMCodec.sol';
/* Interface Imports */
import {ICrossDomainMessenger} from '../../libraries/bridge/ICrossDomainMessenger.sol';
/**
 * @title IL1CrossDomainMessenger
 */
interface IL1CrossDomainMessenger is ICrossDomainMessenger {
  /*******************
   * Data Structures *
   *******************/
  struct L2MessageInclusionProof {
    bytes32 stateRoot;
    Lib_OVMCodec.ChainBatchHeader stateRootBatchHeader;
    Lib_OVMCodec.ChainInclusionProof stateRootProof;
    bytes stateTrieWitness;
    bytes storageTrieWitness;
  }
  /********************
   * Public Functions *
   ********************/
  /**
   * Relays a cross domain message to a contract.
   * @param _target Target contract address.
   * @param _sender Message sender address.
   * @param _message Message to send to the target.
   * @param _messageNonce Nonce for the provided message.
   * @param _proof Inclusion proof for the given message.
   */
  function relayMessage(
    address _target,
    address _sender,
    bytes memory _message,
    uint256 _messageNonce,
    L2MessageInclusionProof memory _proof
  ) external;
  /**
   * Replays a cross domain message to the target messenger.
   * @param _target Target contract address.
   * @param _sender Original sender address.
   * @param _message Message to send to the target.
   * @param _queueIndex CTC Queue index for the message to replay.
   * @param _oldGasLimit Original gas limit used to send the message.
   * @param _newGasLimit New gas limit to be used for this message.
   */
  function replayMessage(
    address _target,
    address _sender,
    bytes memory _message,
    uint256 _queueIndex,
    uint32 _oldGasLimit,
    uint32 _newGasLimit
  ) external;
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/* Library Imports */
import {Lib_AddressManager} from './Lib_AddressManager.sol';
/**
 * @title Lib_AddressResolver
 */
abstract contract Lib_AddressResolver {
  /*************
   * Variables *
   *************/
  Lib_AddressManager public libAddressManager;
  /***************
   * Constructor *
   ***************/
  /**
   * @param _libAddressManager Address of the Lib_AddressManager.
   */
  constructor(address _libAddressManager) {
    libAddressManager = Lib_AddressManager(_libAddressManager);
  }
  /********************
   * Public Functions *
   ********************/
  /**
   * Resolves the address associated with a given name.
   * @param _name Name to resolve an address for.
   * @return Address associated with the given name.
   */
  function resolve(string memory _name) public view returns (address) {
    return libAddressManager.getAddress(_name);
  }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/* Library Imports */
import {Lib_RLPReader} from '../rlp/Lib_RLPReader.sol';
import {Lib_RLPWriter} from '../rlp/Lib_RLPWriter.sol';
import {Lib_BytesUtils} from '../utils/Lib_BytesUtils.sol';
import {Lib_Bytes32Utils} from '../utils/Lib_Bytes32Utils.sol';
/**
 * @title Lib_OVMCodec
 */
library Lib_OVMCodec {
  /*********
   * Enums *
   *********/
  enum QueueOrigin {
    SEQUENCER_QUEUE,
    L1TOL2_QUEUE
  }
  /***********
   * Structs *
   ***********/
  struct EVMAccount {
    uint256 nonce;
    uint256 balance;
    bytes32 storageRoot;
    bytes32 codeHash;
  }
  struct ChainBatchHeader {
    uint256 batchIndex;
    bytes32 batchRoot;
    uint256 batchSize;
    uint256 prevTotalElements;
    bytes extraData;
  }
  struct ChainInclusionProof {
    uint256 index;
    bytes32[] siblings;
  }
  struct Transaction {
    uint256 timestamp;
    uint256 blockNumber;
    QueueOrigin l1QueueOrigin;
    address l1TxOrigin;
    address entrypoint;
    uint256 gasLimit;
    bytes data;
  }
  struct TransactionChainElement {
    bool isSequenced;
    uint256 queueIndex; // QUEUED TX ONLY
    uint256 timestamp; // SEQUENCER TX ONLY
    uint256 blockNumber; // SEQUENCER TX ONLY
    bytes txData; // SEQUENCER TX ONLY
  }
  struct QueueElement {
    bytes32 transactionHash;
    uint40 timestamp;
    uint40 blockNumber;
  }
  /**********************
   * Internal Functions *
   **********************/
  /**
   * Encodes a standard OVM transaction.
   * @param _transaction OVM transaction to encode.
   * @return Encoded transaction bytes.
   */
  function encodeTransaction(Transaction memory _transaction)
    internal
    pure
    returns (bytes memory)
  {
    return
      abi.encodePacked(
        _transaction.timestamp,
        _transaction.blockNumber,
        _transaction.l1QueueOrigin,
        _transaction.l1TxOrigin,
        _transaction.entrypoint,
        _transaction.gasLimit,
        _transaction.data
      );
  }
  /**
   * Hashes a standard OVM transaction.
   * @param _transaction OVM transaction to encode.
   * @return Hashed transaction
   */
  function hashTransaction(Transaction memory _transaction)
    internal
    pure
    returns (bytes32)
  {
    return keccak256(encodeTransaction(_transaction));
  }
  /**
   * @notice Decodes an RLP-encoded account state into a useful struct.
   * @param _encoded RLP-encoded account state.
   * @return Account state struct.
   */
  function decodeEVMAccount(bytes memory _encoded)
    internal
    pure
    returns (EVMAccount memory)
  {
    Lib_RLPReader.RLPItem[] memory accountState = Lib_RLPReader.readList(
      _encoded
    );
    return
      EVMAccount({
        nonce: Lib_RLPReader.readUint256(accountState[0]),
        balance: Lib_RLPReader.readUint256(accountState[1]),
        storageRoot: Lib_RLPReader.readBytes32(accountState[2]),
        codeHash: Lib_RLPReader.readBytes32(accountState[3])
      });
  }
  /**
   * Calculates a hash for a given batch header.
   * @param _batchHeader Header to hash.
   * @return Hash of the header.
   */
  function hashBatchHeader(Lib_OVMCodec.ChainBatchHeader memory _batchHeader)
    internal
    pure
    returns (bytes32)
  {
    return
      keccak256(
        abi.encode(
          _batchHeader.batchRoot,
          _batchHeader.batchSize,
          _batchHeader.prevTotalElements,
          _batchHeader.extraData
        )
      );
  }
}
// SPDX-License-Identifier: MIT
pragma solidity >0.5.0 <0.9.0;
/**
 * @title ICrossDomainMessenger
 */
interface ICrossDomainMessenger {
  /**********
   * Events *
   **********/
  event SentMessage(
    address indexed target,
    address sender,
    bytes message,
    uint256 messageNonce,
    uint256 gasLimit
  );
  event RelayedMessage(bytes32 indexed msgHash);
  event FailedRelayedMessage(bytes32 indexed msgHash);
  /*************
   * Variables *
   *************/
  function xDomainMessageSender() external view returns (address);
  /********************
   * Public Functions *
   ********************/
  /**
   * Sends a cross domain message to the target messenger.
   * @param _target Target contract address.
   * @param _message Message to send to the target.
   * @param _gasLimit Gas limit for the provided message.
   */
  function sendMessage(
    address _target,
    bytes calldata _message,
    uint32 _gasLimit
  ) external;
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/**
 * @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
    )
  {
    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) {
    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;
    unchecked {
      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: MIT
pragma solidity ^0.8.9;
/**
 * @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 The RLP encoded string in bytes.
   */
  function writeBytes(bytes memory _in) internal pure returns (bytes memory) {
    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 The RLP encoded list of items in bytes.
   */
  function writeList(bytes[] memory _in) internal pure returns (bytes memory) {
    bytes memory list = _flatten(_in);
    return abi.encodePacked(_writeLength(list.length, 192), list);
  }
  /**
   * RLP encodes a string.
   * @param _in The string to encode.
   * @return The RLP encoded string in bytes.
   */
  function writeString(string memory _in) internal pure returns (bytes memory) {
    return writeBytes(bytes(_in));
  }
  /**
   * RLP encodes an address.
   * @param _in The address to encode.
   * @return The RLP encoded address in bytes.
   */
  function writeAddress(address _in) internal pure returns (bytes memory) {
    return writeBytes(abi.encodePacked(_in));
  }
  /**
   * RLP encodes a uint.
   * @param _in The uint256 to encode.
   * @return The RLP encoded uint256 in bytes.
   */
  function writeUint(uint256 _in) internal pure returns (bytes memory) {
    return writeBytes(_toBinary(_in));
  }
  /**
   * RLP encodes a bool.
   * @param _in The bool to encode.
   * @return The RLP encoded bool in bytes.
   */
  function writeBool(bool _in) internal pure returns (bytes memory) {
    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 RLP encoded bytes.
   */
  function _writeLength(uint256 _len, uint256 _offset)
    private
    pure
    returns (bytes memory)
  {
    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 RLP encoded bytes.
   */
  function _toBinary(uint256 _x) private pure returns (bytes memory) {
    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;
    unchecked {
      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 The flattened byte string.
   */
  function _flatten(bytes[] memory _list) private pure returns (bytes memory) {
    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;
  }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/**
 * @title Lib_BytesUtils
 */
library Lib_BytesUtils {
  /**********************
   * Internal Functions *
   **********************/
  function slice(
    bytes memory _bytes,
    uint256 _start,
    uint256 _length
  ) internal pure returns (bytes memory) {
    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)
  {
    if (_start >= _bytes.length) {
      return bytes('');
    }
    return slice(_bytes, _start, _bytes.length - _start);
  }
  function toBytes32(bytes memory _bytes) internal pure returns (bytes32) {
    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 toNibbles(bytes memory _bytes) internal pure returns (bytes memory) {
    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)
  {
    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.8.9;
/**
 * @title Lib_Byte32Utils
 */
library Lib_Bytes32Utils {
  /**********************
   * Internal Functions *
   **********************/
  /**
   * Converts a bytes32 value to a boolean. Anything non-zero will be converted to "true."
   * @param _in Input bytes32 value.
   * @return Bytes32 as a boolean.
   */
  function toBool(bytes32 _in) internal pure returns (bool) {
    return _in != 0;
  }
  /**
   * Converts a boolean to a bytes32 value.
   * @param _in Input boolean value.
   * @return Boolean as a bytes32.
   */
  function fromBool(bool _in) internal pure returns (bytes32) {
    return bytes32(uint256(_in ? 1 : 0));
  }
  /**
   * Converts a bytes32 value to an address. Takes the *last* 20 bytes.
   * @param _in Input bytes32 value.
   * @return Bytes32 as an address.
   */
  function toAddress(bytes32 _in) internal pure returns (address) {
    return address(uint160(uint256(_in)));
  }
  /**
   * Converts an address to a bytes32.
   * @param _in Input address value.
   * @return Address as a bytes32.
   */
  function fromAddress(address _in) internal pure returns (bytes32) {
    return bytes32(uint256(uint160(_in)));
  }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/* External Imports */
import {Ownable} from '@openzeppelin/contracts/access/Ownable.sol';
/**
 * @title Lib_AddressManager
 */
contract Lib_AddressManager is Ownable {
  /**********
   * Events *
   **********/
  event AddressSet(
    string indexed _name,
    address _newAddress,
    address _oldAddress
  );
  /*************
   * Variables *
   *************/
  mapping(bytes32 => address) private addresses;
  /********************
   * Public Functions *
   ********************/
  /**
   * Changes the address associated with a particular name.
   * @param _name String name to associate an address with.
   * @param _address Address to associate with the name.
   */
  function setAddress(string memory _name, address _address)
    external
    onlyOwner
  {
    bytes32 nameHash = _getNameHash(_name);
    address oldAddress = addresses[nameHash];
    addresses[nameHash] = _address;
    emit AddressSet(_name, _address, oldAddress);
  }
  /**
   * Retrieves the address associated with a given name.
   * @param _name Name to retrieve an address for.
   * @return Address associated with the given name.
   */
  function getAddress(string memory _name) external view returns (address) {
    return addresses[_getNameHash(_name)];
  }
  /**********************
   * Internal Functions *
   **********************/
  /**
   * Computes the hash of a name.
   * @param _name Name to compute a hash for.
   * @return Hash of the given name.
   */
  function _getNameHash(string memory _name) internal pure returns (bytes32) {
    return keccak256(abi.encodePacked(_name));
  }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
import "../utils/Context.sol";
/**
 * @dev Contract module which provides a basic access control mechanism, where
 * there is an account (an owner) that can be granted exclusive access to
 * specific functions.
 *
 * By default, the owner account will be the one that deploys the contract. This
 * can later be changed with {transferOwnership}.
 *
 * This module is used through inheritance. It will make available the modifier
 * `onlyOwner`, which can be applied to your functions to restrict their use to
 * the owner.
 */
abstract contract Ownable is Context {
    address private _owner;
    event OwnershipTransferred(address indexed previousOwner, address indexed newOwner);
    /**
     * @dev Initializes the contract setting the deployer as the initial owner.
     */
    constructor() {
        _setOwner(_msgSender());
    }
    /**
     * @dev Returns the address of the current owner.
     */
    function owner() public view virtual returns (address) {
        return _owner;
    }
    /**
     * @dev Throws if called by any account other than the owner.
     */
    modifier onlyOwner() {
        require(owner() == _msgSender(), "Ownable: caller is not the owner");
        _;
    }
    /**
     * @dev Leaves the contract without owner. It will not be possible to call
     * `onlyOwner` functions anymore. Can only be called by the current owner.
     *
     * NOTE: Renouncing ownership will leave the contract without an owner,
     * thereby removing any functionality that is only available to the owner.
     */
    function renounceOwnership() public virtual onlyOwner {
        _setOwner(address(0));
    }
    /**
     * @dev Transfers ownership of the contract to a new account (`newOwner`).
     * Can only be called by the current owner.
     */
    function transferOwnership(address newOwner) public virtual onlyOwner {
        require(newOwner != address(0), "Ownable: new owner is the zero address");
        _setOwner(newOwner);
    }
    function _setOwner(address newOwner) private {
        address oldOwner = _owner;
        _owner = newOwner;
        emit OwnershipTransferred(oldOwner, newOwner);
    }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
/**
 * @dev Provides information about the current execution context, including the
 * sender of the transaction and its data. While these are generally available
 * via msg.sender and msg.data, they should not be accessed in such a direct
 * manner, since when dealing with meta-transactions the account sending and
 * paying for execution may not be the actual sender (as far as an application
 * is concerned).
 *
 * This contract is only required for intermediate, library-like contracts.
 */
abstract contract Context {
    function _msgSender() internal view virtual returns (address) {
        return msg.sender;
    }
    function _msgData() internal view virtual returns (bytes calldata) {
        return msg.data;
    }
}

// SPDX-License-Identifier: MIT
pragma solidity >0.5.0 <0.8.0;
import { iL1ChugSplashDeployer } from "./interfaces/iL1ChugSplashDeployer.sol";
/**
 * @title L1ChugSplashProxy
 * @dev Basic ChugSplash proxy contract for L1. Very close to being a normal proxy but has added
 * functions `setCode` and `setStorage` for changing the code or storage of the contract. Nifty!
 *
 * Note for future developers: do NOT make anything in this contract 'public' unless you know what
 * you're doing. Anything public can potentially have a function signature that conflicts with a
 * signature attached to the implementation contract. Public functions SHOULD always have the
 * 'proxyCallIfNotOwner' modifier unless there's some *really* good reason not to have that
 * modifier. And there almost certainly is not a good reason to not have that modifier. Beware!
 */
contract L1ChugSplashProxy {
    /*************
     * Constants *
     *************/
    // "Magic" prefix. When prepended to some arbitrary bytecode and used to create a contract, the
    // appended bytecode will be deployed as given.
    bytes13 constant internal DEPLOY_CODE_PREFIX = 0x600D380380600D6000396000f3;
    // bytes32(uint256(keccak256('eip1967.proxy.implementation')) - 1)
    bytes32 constant internal IMPLEMENTATION_KEY = 0x360894a13ba1a3210667c828492db98dca3e2076cc3735a920a3ca505d382bbc;
    // bytes32(uint256(keccak256('eip1967.proxy.admin')) - 1)
    bytes32 constant internal OWNER_KEY = 0xb53127684a568b3173ae13b9f8a6016e243e63b6e8ee1178d6a717850b5d6103;
    /***************
     * Constructor *
     ***************/
    
    /**
     * @param _owner Address of the initial contract owner.
     */
    constructor(
        address _owner
    ) {
        _setOwner(_owner);
    }
    /**********************
     * Function Modifiers *
     **********************/
    /**
     * Blocks a function from being called when the parent signals that the system should be paused
     * via an isUpgrading function.
     */
    modifier onlyWhenNotPaused() {
        address owner = _getOwner();
        // We do a low-level call because there's no guarantee that the owner actually *is* an
        // L1ChugSplashDeployer contract and Solidity will throw errors if we do a normal call and
        // it turns out that it isn't the right type of contract.
        (bool success, bytes memory returndata) = owner.staticcall(
            abi.encodeWithSelector(
                iL1ChugSplashDeployer.isUpgrading.selector
            )
        );
        // If the call was unsuccessful then we assume that there's no "isUpgrading" method and we
        // can just continue as normal. We also expect that the return value is exactly 32 bytes
        // long. If this isn't the case then we can safely ignore the result.
        if (success && returndata.length == 32) {
            // Although the expected value is a *boolean*, it's safer to decode as a uint256 in the
            // case that the isUpgrading function returned something other than 0 or 1. But we only
            // really care about the case where this value is 0 (= false).
            uint256 ret = abi.decode(returndata, (uint256));
            require(
                ret == 0,
                "L1ChugSplashProxy: system is currently being upgraded"
            );
        }
        _;
    }
    /**
     * Makes a proxy call instead of triggering the given function when the caller is either the
     * owner or the zero address. Caller can only ever be the zero address if this function is
     * being called off-chain via eth_call, which is totally fine and can be convenient for
     * client-side tooling. Avoids situations where the proxy and implementation share a sighash
     * and the proxy function ends up being called instead of the implementation one.
     *
     * Note: msg.sender == address(0) can ONLY be triggered off-chain via eth_call. If there's a
     * way for someone to send a transaction with msg.sender == address(0) in any real context then
     * we have much bigger problems. Primary reason to include this additional allowed sender is
     * because the owner address can be changed dynamically and we do not want clients to have to
     * keep track of the current owner in order to make an eth_call that doesn't trigger the
     * proxied contract.
     */
    modifier proxyCallIfNotOwner() {
        if (msg.sender == _getOwner() || msg.sender == address(0)) {
            _;
        } else {
            // This WILL halt the call frame on completion.
            _doProxyCall();
        }
    }
    /*********************
     * Fallback Function *
     *********************/
    fallback()
        external
        payable
    {
        // Proxy call by default.
        _doProxyCall();
    }
    /********************
     * Public Functions *
     ********************/
    /**
     * Sets the code that should be running behind this proxy. Note that this scheme is a bit
     * different from the standard proxy scheme where one would typically deploy the code
     * separately and then set the implementation address. We're doing it this way because it gives
     * us a lot more freedom on the client side. Can only be triggered by the contract owner.
     * @param _code New contract code to run inside this contract.
     */
    function setCode(
        bytes memory _code
    )
        proxyCallIfNotOwner
        public
    {
        // Get the code hash of the current implementation.
        address implementation = _getImplementation();
        // If the code hash matches the new implementation then we return early.
        if (keccak256(_code) == _getAccountCodeHash(implementation)) {
            return;
        }
        // Create the deploycode by appending the magic prefix.
        bytes memory deploycode = abi.encodePacked(
            DEPLOY_CODE_PREFIX,
            _code
        );
        // Deploy the code and set the new implementation address.
        address newImplementation;
        assembly {
            newImplementation := create(0x0, add(deploycode, 0x20), mload(deploycode))
        }
        // Check that the code was actually deployed correctly. I'm not sure if you can ever
        // actually fail this check. Should only happen if the contract creation from above runs
        // out of gas but this parent execution thread does NOT run out of gas. Seems like we
        // should be doing this check anyway though.
        require(
            _getAccountCodeHash(newImplementation) == keccak256(_code),
            "L1ChugSplashProxy: code was not correctly deployed."
        );
        _setImplementation(newImplementation);
    }
    /**
     * Modifies some storage slot within the proxy contract. Gives us a lot of power to perform
     * upgrades in a more transparent way. Only callable by the owner.
     * @param _key Storage key to modify.
     * @param _value New value for the storage key.
     */
    function setStorage(
        bytes32 _key,
        bytes32 _value
    )
        proxyCallIfNotOwner
        public
    {
        assembly {
            sstore(_key, _value)
        }
    }
    /**
     * Changes the owner of the proxy contract. Only callable by the owner.
     * @param _owner New owner of the proxy contract.
     */
    function setOwner(
        address _owner
    )
        proxyCallIfNotOwner
        public
    {
        _setOwner(_owner);
    }
    /**
     * Queries the owner of the proxy contract. Can only be called by the owner OR by making an
     * eth_call and setting the "from" address to address(0).
     * @return Owner address.
     */
    function getOwner()
        proxyCallIfNotOwner
        public
        returns (
            address
        )
    {
        return _getOwner();
    }
    /**
     * Queries the implementation address. Can only be called by the owner OR by making an
     * eth_call and setting the "from" address to address(0).
     * @return Implementation address.
     */
    function getImplementation()
        proxyCallIfNotOwner
        public
        returns (
            address
        )
    {
        return _getImplementation();
    }
    /**********************
     * Internal Functions *
     **********************/
    /**
     * Sets the implementation address.
     * @param _implementation New implementation address.
     */
    function _setImplementation(
        address _implementation
    )
        internal
    {
        assembly {
            sstore(IMPLEMENTATION_KEY, _implementation)
        }
    }
    /**
     * Queries the implementation address.
     * @return Implementation address.
     */
    function _getImplementation()
        internal
        view
        returns (
            address
        )
    {
        address implementation;
        assembly {
            implementation := sload(IMPLEMENTATION_KEY)
        }
        return implementation;
    }
    /**
     * Changes the owner of the proxy contract.
     * @param _owner New owner of the proxy contract.
     */
    function _setOwner(
        address _owner
    )
        internal
    {
        assembly {
            sstore(OWNER_KEY, _owner)
        }
    }
    /**
     * Queries the owner of the proxy contract.
     * @return Owner address.
     */
    function _getOwner()
        internal
        view 
        returns (
            address
        )
    {
        address owner;
        assembly {
            owner := sload(OWNER_KEY)
        }
        return owner;
    }
    /**
     * Gets the code hash for a given account.
     * @param _account Address of the account to get a code hash for.
     * @return Code hash for the account.
     */
    function _getAccountCodeHash(
        address _account
    )
        internal
        view
        returns (
            bytes32
        )
    {
        bytes32 codeHash;
        assembly {
            codeHash := extcodehash(_account)
        }
        return codeHash;
    }
    /**
     * Performs the proxy call via a delegatecall.
     */
    function _doProxyCall()
        onlyWhenNotPaused
        internal
    {
        address implementation = _getImplementation();
        require(
            implementation != address(0),
            "L1ChugSplashProxy: implementation is not set yet"
        );
        assembly {
            // Copy calldata into memory at 0x0....calldatasize.
            calldatacopy(0x0, 0x0, calldatasize())
            // Perform the delegatecall, make sure to pass all available gas.
            let success := delegatecall(gas(), implementation, 0x0, calldatasize(), 0x0, 0x0)
            // Copy returndata into memory at 0x0....returndatasize. Note that this *will*
            // overwrite the calldata that we just copied into memory but that doesn't really
            // matter because we'll be returning in a second anyway.
            returndatacopy(0x0, 0x0, returndatasize())
            
            // Success == 0 means a revert. We'll revert too and pass the data up.
            if iszero(success) {
                revert(0x0, returndatasize())
            }
            // Otherwise we'll just return and pass the data up.
            return(0x0, returndatasize())
        }
    }
}
// SPDX-License-Identifier: MIT
pragma solidity >0.5.0 <0.8.0;
/**
 * @title iL1ChugSplashDeployer
 */
interface iL1ChugSplashDeployer {
    function isUpgrading()
        external
        view
        returns (
            bool
        );
}

pragma solidity ^0.4.17;

/**
 * @title SafeMath
 * @dev Math operations with safety checks that throw on error
 */
library SafeMath {
    function mul(uint256 a, uint256 b) internal pure returns (uint256) {
        if (a == 0) {
            return 0;
        }
        uint256 c = a * b;
        assert(c / a == b);
        return c;
    }

    function div(uint256 a, uint256 b) internal pure returns (uint256) {
        // assert(b > 0); // Solidity automatically throws when dividing by 0
        uint256 c = a / b;
        // assert(a == b * c + a % b); // There is no case in which this doesn't hold
        return c;
    }

    function sub(uint256 a, uint256 b) internal pure returns (uint256) {
        assert(b <= a);
        return a - b;
    }

    function add(uint256 a, uint256 b) internal pure returns (uint256) {
        uint256 c = a + b;
        assert(c >= a);
        return c;
    }
}

/**
 * @title Ownable
 * @dev The Ownable contract has an owner address, and provides basic authorization control
 * functions, this simplifies the implementation of "user permissions".
 */
contract Ownable {
    address public owner;

    /**
      * @dev The Ownable constructor sets the original `owner` of the contract to the sender
      * account.
      */
    function Ownable() public {
        owner = msg.sender;
    }

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

    /**
    * @dev Allows the current owner to transfer control of the contract to a newOwner.
    * @param newOwner The address to transfer ownership to.
    */
    function transferOwnership(address newOwner) public onlyOwner {
        if (newOwner != address(0)) {
            owner = newOwner;
        }
    }

}

/**
 * @title ERC20Basic
 * @dev Simpler version of ERC20 interface
 * @dev see https://github.com/ethereum/EIPs/issues/20
 */
contract ERC20Basic {
    uint public _totalSupply;
    function totalSupply() public constant returns (uint);
    function balanceOf(address who) public constant returns (uint);
    function transfer(address to, uint value) public;
    event Transfer(address indexed from, address indexed to, uint value);
}

/**
 * @title ERC20 interface
 * @dev see https://github.com/ethereum/EIPs/issues/20
 */
contract ERC20 is ERC20Basic {
    function allowance(address owner, address spender) public constant returns (uint);
    function transferFrom(address from, address to, uint value) public;
    function approve(address spender, uint value) public;
    event Approval(address indexed owner, address indexed spender, uint value);
}

/**
 * @title Basic token
 * @dev Basic version of StandardToken, with no allowances.
 */
contract BasicToken is Ownable, ERC20Basic {
    using SafeMath for uint;

    mapping(address => uint) public balances;

    // additional variables for use if transaction fees ever became necessary
    uint public basisPointsRate = 0;
    uint public maximumFee = 0;

    /**
    * @dev Fix for the ERC20 short address attack.
    */
    modifier onlyPayloadSize(uint size) {
        require(!(msg.data.length < size + 4));
        _;
    }

    /**
    * @dev transfer token for a specified address
    * @param _to The address to transfer to.
    * @param _value The amount to be transferred.
    */
    function transfer(address _to, uint _value) public onlyPayloadSize(2 * 32) {
        uint fee = (_value.mul(basisPointsRate)).div(10000);
        if (fee > maximumFee) {
            fee = maximumFee;
        }
        uint sendAmount = _value.sub(fee);
        balances[msg.sender] = balances[msg.sender].sub(_value);
        balances[_to] = balances[_to].add(sendAmount);
        if (fee > 0) {
            balances[owner] = balances[owner].add(fee);
            Transfer(msg.sender, owner, fee);
        }
        Transfer(msg.sender, _to, sendAmount);
    }

    /**
    * @dev Gets the balance of the specified address.
    * @param _owner The address to query the the balance of.
    * @return An uint representing the amount owned by the passed address.
    */
    function balanceOf(address _owner) public constant returns (uint balance) {
        return balances[_owner];
    }

}

/**
 * @title Standard ERC20 token
 *
 * @dev Implementation of the basic standard token.
 * @dev https://github.com/ethereum/EIPs/issues/20
 * @dev Based oncode by FirstBlood: https://github.com/Firstbloodio/token/blob/master/smart_contract/FirstBloodToken.sol
 */
contract StandardToken is BasicToken, ERC20 {

    mapping (address => mapping (address => uint)) public allowed;

    uint public constant MAX_UINT = 2**256 - 1;

    /**
    * @dev Transfer tokens from one address to another
    * @param _from address The address which you want to send tokens from
    * @param _to address The address which you want to transfer to
    * @param _value uint the amount of tokens to be transferred
    */
    function transferFrom(address _from, address _to, uint _value) public onlyPayloadSize(3 * 32) {
        var _allowance = allowed[_from][msg.sender];

        // Check is not needed because sub(_allowance, _value) will already throw if this condition is not met
        // if (_value > _allowance) throw;

        uint fee = (_value.mul(basisPointsRate)).div(10000);
        if (fee > maximumFee) {
            fee = maximumFee;
        }
        if (_allowance < MAX_UINT) {
            allowed[_from][msg.sender] = _allowance.sub(_value);
        }
        uint sendAmount = _value.sub(fee);
        balances[_from] = balances[_from].sub(_value);
        balances[_to] = balances[_to].add(sendAmount);
        if (fee > 0) {
            balances[owner] = balances[owner].add(fee);
            Transfer(_from, owner, fee);
        }
        Transfer(_from, _to, sendAmount);
    }

    /**
    * @dev Approve the passed address to spend the specified amount of tokens on behalf of msg.sender.
    * @param _spender The address which will spend the funds.
    * @param _value The amount of tokens to be spent.
    */
    function approve(address _spender, uint _value) public onlyPayloadSize(2 * 32) {

        // To change the approve amount you first have to reduce the addresses`
        //  allowance to zero by calling `approve(_spender, 0)` if it is not
        //  already 0 to mitigate the race condition described here:
        //  https://github.com/ethereum/EIPs/issues/20#issuecomment-263524729
        require(!((_value != 0) && (allowed[msg.sender][_spender] != 0)));

        allowed[msg.sender][_spender] = _value;
        Approval(msg.sender, _spender, _value);
    }

    /**
    * @dev Function to check the amount of tokens than an owner allowed to a spender.
    * @param _owner address The address which owns the funds.
    * @param _spender address The address which will spend the funds.
    * @return A uint specifying the amount of tokens still available for the spender.
    */
    function allowance(address _owner, address _spender) public constant returns (uint remaining) {
        return allowed[_owner][_spender];
    }

}


/**
 * @title Pausable
 * @dev Base contract which allows children to implement an emergency stop mechanism.
 */
contract Pausable is Ownable {
  event Pause();
  event Unpause();

  bool public paused = false;


  /**
   * @dev Modifier to make a function callable only when the contract is not paused.
   */
  modifier whenNotPaused() {
    require(!paused);
    _;
  }

  /**
   * @dev Modifier to make a function callable only when the contract is paused.
   */
  modifier whenPaused() {
    require(paused);
    _;
  }

  /**
   * @dev called by the owner to pause, triggers stopped state
   */
  function pause() onlyOwner whenNotPaused public {
    paused = true;
    Pause();
  }

  /**
   * @dev called by the owner to unpause, returns to normal state
   */
  function unpause() onlyOwner whenPaused public {
    paused = false;
    Unpause();
  }
}

contract BlackList is Ownable, BasicToken {

    /////// Getters to allow the same blacklist to be used also by other contracts (including upgraded Tether) ///////
    function getBlackListStatus(address _maker) external constant returns (bool) {
        return isBlackListed[_maker];
    }

    function getOwner() external constant returns (address) {
        return owner;
    }

    mapping (address => bool) public isBlackListed;
    
    function addBlackList (address _evilUser) public onlyOwner {
        isBlackListed[_evilUser] = true;
        AddedBlackList(_evilUser);
    }

    function removeBlackList (address _clearedUser) public onlyOwner {
        isBlackListed[_clearedUser] = false;
        RemovedBlackList(_clearedUser);
    }

    function destroyBlackFunds (address _blackListedUser) public onlyOwner {
        require(isBlackListed[_blackListedUser]);
        uint dirtyFunds = balanceOf(_blackListedUser);
        balances[_blackListedUser] = 0;
        _totalSupply -= dirtyFunds;
        DestroyedBlackFunds(_blackListedUser, dirtyFunds);
    }

    event DestroyedBlackFunds(address _blackListedUser, uint _balance);

    event AddedBlackList(address _user);

    event RemovedBlackList(address _user);

}

contract UpgradedStandardToken is StandardToken{
    // those methods are called by the legacy contract
    // and they must ensure msg.sender to be the contract address
    function transferByLegacy(address from, address to, uint value) public;
    function transferFromByLegacy(address sender, address from, address spender, uint value) public;
    function approveByLegacy(address from, address spender, uint value) public;
}

contract TetherToken is Pausable, StandardToken, BlackList {

    string public name;
    string public symbol;
    uint public decimals;
    address public upgradedAddress;
    bool public deprecated;

    //  The contract can be initialized with a number of tokens
    //  All the tokens are deposited to the owner address
    //
    // @param _balance Initial supply of the contract
    // @param _name Token Name
    // @param _symbol Token symbol
    // @param _decimals Token decimals
    function TetherToken(uint _initialSupply, string _name, string _symbol, uint _decimals) public {
        _totalSupply = _initialSupply;
        name = _name;
        symbol = _symbol;
        decimals = _decimals;
        balances[owner] = _initialSupply;
        deprecated = false;
    }

    // Forward ERC20 methods to upgraded contract if this one is deprecated
    function transfer(address _to, uint _value) public whenNotPaused {
        require(!isBlackListed[msg.sender]);
        if (deprecated) {
            return UpgradedStandardToken(upgradedAddress).transferByLegacy(msg.sender, _to, _value);
        } else {
            return super.transfer(_to, _value);
        }
    }

    // Forward ERC20 methods to upgraded contract if this one is deprecated
    function transferFrom(address _from, address _to, uint _value) public whenNotPaused {
        require(!isBlackListed[_from]);
        if (deprecated) {
            return UpgradedStandardToken(upgradedAddress).transferFromByLegacy(msg.sender, _from, _to, _value);
        } else {
            return super.transferFrom(_from, _to, _value);
        }
    }

    // Forward ERC20 methods to upgraded contract if this one is deprecated
    function balanceOf(address who) public constant returns (uint) {
        if (deprecated) {
            return UpgradedStandardToken(upgradedAddress).balanceOf(who);
        } else {
            return super.balanceOf(who);
        }
    }

    // Forward ERC20 methods to upgraded contract if this one is deprecated
    function approve(address _spender, uint _value) public onlyPayloadSize(2 * 32) {
        if (deprecated) {
            return UpgradedStandardToken(upgradedAddress).approveByLegacy(msg.sender, _spender, _value);
        } else {
            return super.approve(_spender, _value);
        }
    }

    // Forward ERC20 methods to upgraded contract if this one is deprecated
    function allowance(address _owner, address _spender) public constant returns (uint remaining) {
        if (deprecated) {
            return StandardToken(upgradedAddress).allowance(_owner, _spender);
        } else {
            return super.allowance(_owner, _spender);
        }
    }

    // deprecate current contract in favour of a new one
    function deprecate(address _upgradedAddress) public onlyOwner {
        deprecated = true;
        upgradedAddress = _upgradedAddress;
        Deprecate(_upgradedAddress);
    }

    // deprecate current contract if favour of a new one
    function totalSupply() public constant returns (uint) {
        if (deprecated) {
            return StandardToken(upgradedAddress).totalSupply();
        } else {
            return _totalSupply;
        }
    }

    // Issue a new amount of tokens
    // these tokens are deposited into the owner address
    //
    // @param _amount Number of tokens to be issued
    function issue(uint amount) public onlyOwner {
        require(_totalSupply + amount > _totalSupply);
        require(balances[owner] + amount > balances[owner]);

        balances[owner] += amount;
        _totalSupply += amount;
        Issue(amount);
    }

    // Redeem tokens.
    // These tokens are withdrawn from the owner address
    // if the balance must be enough to cover the redeem
    // or the call will fail.
    // @param _amount Number of tokens to be issued
    function redeem(uint amount) public onlyOwner {
        require(_totalSupply >= amount);
        require(balances[owner] >= amount);

        _totalSupply -= amount;
        balances[owner] -= amount;
        Redeem(amount);
    }

    function setParams(uint newBasisPoints, uint newMaxFee) public onlyOwner {
        // Ensure transparency by hardcoding limit beyond which fees can never be added
        require(newBasisPoints < 20);
        require(newMaxFee < 50);

        basisPointsRate = newBasisPoints;
        maximumFee = newMaxFee.mul(10**decimals);

        Params(basisPointsRate, maximumFee);
    }

    // Called when new token are issued
    event Issue(uint amount);

    // Called when tokens are redeemed
    event Redeem(uint amount);

    // Called when contract is deprecated
    event Deprecate(address newAddress);

    // Called if contract ever adds fees
    event Params(uint feeBasisPoints, uint maxFee);
}

// SPDX-License-Identifier: MIT
pragma solidity >0.5.0 <0.8.0;
/* Contract Imports */
import { Ownable } from "./Lib_Ownable.sol";
/**
 * @title Lib_AddressManager
 */
contract Lib_AddressManager is Ownable {
    /**********
     * Events *
     **********/
    event AddressSet(
        string _name,
        address _newAddress
    );
    /*******************************************
     * Contract Variables: Internal Accounting *
     *******************************************/
    mapping (bytes32 => address) private addresses;
    /********************
     * Public Functions *
     ********************/
    function setAddress(
        string memory _name,
        address _address
    )
        public
        onlyOwner
    {
        emit AddressSet(_name, _address);
        addresses[_getNameHash(_name)] = _address;
    }
    function getAddress(
        string memory _name
    )
        public
        view
        returns (address)
    {
        return addresses[_getNameHash(_name)];
    }
    /**********************
     * Internal Functions *
     **********************/
    function _getNameHash(
        string memory _name
    )
        internal
        pure
        returns (
            bytes32 _hash
        )
    {
        return keccak256(abi.encodePacked(_name));
    }
}
// SPDX-License-Identifier: MIT
pragma solidity >0.5.0 <0.8.0;
/**
 * @title Ownable
 * @dev Adapted from https://github.com/OpenZeppelin/openzeppelin-contracts/blob/master/contracts/access/Ownable.sol
 */
abstract contract Ownable {
    /*************
     * Variables *
     *************/
    address public owner;
    /**********
     * Events *
     **********/
    event OwnershipTransferred(
        address indexed previousOwner,
        address indexed newOwner
    );
    /***************
     * Constructor *
     ***************/
    constructor() {
        owner = msg.sender;
        emit OwnershipTransferred(address(0), owner);
    }
    /**********************
     * Function Modifiers *
     **********************/
    modifier onlyOwner() {
        require(
            owner == msg.sender,
            "Ownable: caller is not the owner"
        );
        _;
    }
    /********************
     * Public Functions *
     ********************/
    function renounceOwnership()
        public
        virtual
        onlyOwner
    {
        emit OwnershipTransferred(owner, address(0));
        owner = address(0);
    }
    function transferOwnership(address _newOwner)
        public
        virtual
        onlyOwner
    {
        require(
            _newOwner != address(0),
            "Ownable: new owner cannot be the zero address"
        );
        emit OwnershipTransferred(owner, _newOwner);
        owner = _newOwner;
    }
}
// SPDX-License-Identifier: MIT
pragma solidity >0.5.0 <0.8.0;
/* Library Imports */
import { Lib_AddressManager } from "./Lib_AddressManager.sol";
/**
 * @title Lib_ResolvedDelegateProxy
 */
contract Lib_ResolvedDelegateProxy {
    /*************
     * Variables *
     *************/
    // Using mappings to store fields to avoid overwriting storage slots in the
    // implementation contract. For example, instead of storing these fields at
    // storage slot `0` & `1`, they are stored at `keccak256(key + slot)`.
    // See: https://solidity.readthedocs.io/en/v0.7.0/internals/layout_in_storage.html
    // NOTE: Do not use this code in your own contract system. 
    //      There is a known flaw in this contract, and we will remove it from the repository
    //      in the near future. Due to the very limited way that we are using it, this flaw is
    //      not an issue in our system. 
    mapping (address => string) private implementationName;
    mapping (address => Lib_AddressManager) private addressManager;
    /***************
     * Constructor *
     ***************/
    /**
     * @param _libAddressManager Address of the Lib_AddressManager.
     * @param _implementationName implementationName of the contract to proxy to.
     */
    constructor(
        address _libAddressManager,
        string memory _implementationName
    )
    {
        addressManager[address(this)] = Lib_AddressManager(_libAddressManager);
        implementationName[address(this)] = _implementationName;
    }
    /*********************
     * Fallback Function *
     *********************/
    fallback()
        external
        payable
    {
        address target = addressManager[address(this)].getAddress(
            (implementationName[address(this)])
        );
        require(
            target != address(0),
            "Target address must be initialized."
        );
        (bool success, bytes memory returndata) = target.delegatecall(msg.data);
        if (success == true) {
            assembly {
                return(add(returndata, 0x20), mload(returndata))
            }
        } else {
            assembly {
                revert(add(returndata, 0x20), mload(returndata))
            }
        }
    }
}

// SPDX-License-Identifier: MIT
pragma solidity >=0.6.0 <0.8.0;
import "../utils/Context.sol";
/**
 * @dev Contract module which provides a basic access control mechanism, where
 * there is an account (an owner) that can be granted exclusive access to
 * specific functions.
 *
 * By default, the owner account will be the one that deploys the contract. This
 * can later be changed with {transferOwnership}.
 *
 * This module is used through inheritance. It will make available the modifier
 * `onlyOwner`, which can be applied to your functions to restrict their use to
 * the owner.
 */
abstract contract Ownable is Context {
    address private _owner;
    event OwnershipTransferred(address indexed previousOwner, address indexed newOwner);
    /**
     * @dev Initializes the contract setting the deployer as the initial owner.
     */
    constructor () internal {
        address msgSender = _msgSender();
        _owner = msgSender;
        emit OwnershipTransferred(address(0), msgSender);
    }
    /**
     * @dev Returns the address of the current owner.
     */
    function owner() public view virtual returns (address) {
        return _owner;
    }
    /**
     * @dev Throws if called by any account other than the owner.
     */
    modifier onlyOwner() {
        require(owner() == _msgSender(), "Ownable: caller is not the owner");
        _;
    }
    /**
     * @dev Leaves the contract without owner. It will not be possible to call
     * `onlyOwner` functions anymore. Can only be called by the current owner.
     *
     * NOTE: Renouncing ownership will leave the contract without an owner,
     * thereby removing any functionality that is only available to the owner.
     */
    function renounceOwnership() public virtual onlyOwner {
        emit OwnershipTransferred(_owner, address(0));
        _owner = address(0);
    }
    /**
     * @dev Transfers ownership of the contract to a new account (`newOwner`).
     * Can only be called by the current owner.
     */
    function transferOwnership(address newOwner) public virtual onlyOwner {
        require(newOwner != address(0), "Ownable: new owner is the zero address");
        emit OwnershipTransferred(_owner, newOwner);
        _owner = newOwner;
    }
}
// SPDX-License-Identifier: MIT
pragma solidity >=0.6.0 <0.8.0;
/*
 * @dev Provides information about the current execution context, including the
 * sender of the transaction and its data. While these are generally available
 * via msg.sender and msg.data, they should not be accessed in such a direct
 * manner, since when dealing with GSN meta-transactions the account sending and
 * paying for execution may not be the actual sender (as far as an application
 * is concerned).
 *
 * This contract is only required for intermediate, library-like contracts.
 */
abstract contract Context {
    function _msgSender() internal view virtual returns (address payable) {
        return msg.sender;
    }
    function _msgData() internal view virtual returns (bytes memory) {
        this; // silence state mutability warning without generating bytecode - see https://github.com/ethereum/solidity/issues/2691
        return msg.data;
    }
}
// SPDX-License-Identifier: MIT
pragma solidity >0.5.0 <0.8.0;
/* External Imports */
import { Ownable } from "@openzeppelin/contracts/access/Ownable.sol";
/**
 * @title Lib_AddressManager
 */
contract Lib_AddressManager is Ownable {
    /**********
     * Events *
     **********/
    event AddressSet(
        string indexed _name,
        address _newAddress,
        address _oldAddress
    );
    /*************
     * Variables *
     *************/
    mapping (bytes32 => address) private addresses;
    /********************
     * Public Functions *
     ********************/
    /**
     * Changes the address associated with a particular name.
     * @param _name String name to associate an address with.
     * @param _address Address to associate with the name.
     */
    function setAddress(
        string memory _name,
        address _address
    )
        external
        onlyOwner
    {
        bytes32 nameHash = _getNameHash(_name);
        address oldAddress = addresses[nameHash];
        addresses[nameHash] = _address;
        emit AddressSet(
            _name,
            _address,
            oldAddress
        );
    }
    /**
     * Retrieves the address associated with a given name.
     * @param _name Name to retrieve an address for.
     * @return Address associated with the given name.
     */
    function getAddress(
        string memory _name
    )
        external
        view
        returns (
            address
        )
    {
        return addresses[_getNameHash(_name)];
    }
    /**********************
     * Internal Functions *
     **********************/
    /**
     * Computes the hash of a name.
     * @param _name Name to compute a hash for.
     * @return Hash of the given name.
     */
    function _getNameHash(
        string memory _name
    )
        internal
        pure
        returns (
            bytes32
        )
    {
        return keccak256(abi.encodePacked(_name));
    }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/* Library Imports */
import {AddressAliasHelper} from '../../standards/AddressAliasHelper.sol';
import {Lib_AddressResolver} from '../../libraries/resolver/Lib_AddressResolver.sol';
import {Lib_OVMCodec} from '../../libraries/codec/Lib_OVMCodec.sol';
import {Lib_AddressManager} from '../../libraries/resolver/Lib_AddressManager.sol';
import {Lib_SecureMerkleTrie} from '../../libraries/trie/Lib_SecureMerkleTrie.sol';
import {Lib_DefaultValues} from '../../libraries/constants/Lib_DefaultValues.sol';
import {Lib_PredeployAddresses} from '../../libraries/constants/Lib_PredeployAddresses.sol';
import {Lib_CrossDomainUtils} from '../../libraries/bridge/Lib_CrossDomainUtils.sol';
/* Interface Imports */
import {IL1CrossDomainMessenger} from './IL1CrossDomainMessenger.sol';
import {ICanonicalTransactionChain} from '../rollup/ICanonicalTransactionChain.sol';
import {IStateCommitmentChain} from '../rollup/IStateCommitmentChain.sol';
/* External Imports */
import {OwnableUpgradeable} from '@openzeppelin/contracts-upgradeable/access/OwnableUpgradeable.sol';
import {PausableUpgradeable} from '@openzeppelin/contracts-upgradeable/security/PausableUpgradeable.sol';
import {ReentrancyGuardUpgradeable} from '@openzeppelin/contracts-upgradeable/security/ReentrancyGuardUpgradeable.sol';
/**
 * @title L1CrossDomainMessenger
 * @dev The L1 Cross Domain Messenger contract sends messages from L1 to L2, and relays messages
 * from L2 onto L1. In the event that a message sent from L1 to L2 is rejected for exceeding the L2
 * epoch gas limit, it can be resubmitted via this contract's replay function.
 *
 * Runtime target: EVM
 */
contract L1CrossDomainMessenger is
  IL1CrossDomainMessenger,
  Lib_AddressResolver,
  OwnableUpgradeable,
  PausableUpgradeable,
  ReentrancyGuardUpgradeable
{
  /**********
   * Events *
   **********/
  event MessageBlocked(bytes32 indexed _xDomainCalldataHash);
  event MessageAllowed(bytes32 indexed _xDomainCalldataHash);
  /**********************
   * Contract Variables *
   **********************/
  mapping(bytes32 => bool) public blockedMessages;
  mapping(bytes32 => bool) public relayedMessages;
  mapping(bytes32 => bool) public successfulMessages;
  mapping(bytes32 => bool) public failedMessages;
  address internal xDomainMsgSender = Lib_DefaultValues.DEFAULT_XDOMAIN_SENDER;
  /***************
   * Constructor *
   ***************/
  /**
   * This contract is intended to be behind a delegate proxy.
   * We pass the zero address to the address resolver just to satisfy the constructor.
   * We still need to set this value in initialize().
   */
  constructor() Lib_AddressResolver(address(0)) {}
  /********************
   * Public Functions *
   ********************/
  /**
   * @param _libAddressManager Address of the Address Manager.
   */
  function initialize(address _libAddressManager) public initializer {
    require(
      address(libAddressManager) == address(0),
      'L1CrossDomainMessenger already intialized.'
    );
    libAddressManager = Lib_AddressManager(_libAddressManager);
    xDomainMsgSender = Lib_DefaultValues.DEFAULT_XDOMAIN_SENDER;
    // Initialize upgradable OZ contracts
    __Context_init_unchained(); // Context is a dependency for both Ownable and Pausable
    __Ownable_init_unchained();
    __Pausable_init_unchained();
    __ReentrancyGuard_init_unchained();
  }
  /**
   * Pause relaying.
   */
  function pause() external onlyOwner {
    _pause();
  }
  /**
   * Block a message.
   * @param _xDomainCalldataHash Hash of the message to block.
   */
  function blockMessage(bytes32 _xDomainCalldataHash) external onlyOwner {
    blockedMessages[_xDomainCalldataHash] = true;
    emit MessageBlocked(_xDomainCalldataHash);
  }
  /**
   * Allow a message.
   * @param _xDomainCalldataHash Hash of the message to block.
   */
  function allowMessage(bytes32 _xDomainCalldataHash) external onlyOwner {
    blockedMessages[_xDomainCalldataHash] = false;
    emit MessageAllowed(_xDomainCalldataHash);
  }
  function xDomainMessageSender() public view returns (address) {
    require(
      xDomainMsgSender != Lib_DefaultValues.DEFAULT_XDOMAIN_SENDER,
      'xDomainMessageSender is not set'
    );
    return xDomainMsgSender;
  }
  /**
   * Sends a cross domain message to the target messenger.
   * @param _target Target contract address.
   * @param _message Message to send to the target.
   * @param _gasLimit Gas limit for the provided message.
   */
  function sendMessage(
    address _target,
    bytes memory _message,
    uint32 _gasLimit
  ) public {
    address ovmCanonicalTransactionChain = resolve('CanonicalTransactionChain');
    // Use the CTC queue length as nonce
    uint40 nonce = ICanonicalTransactionChain(ovmCanonicalTransactionChain)
      .getQueueLength();
    bytes memory xDomainCalldata = Lib_CrossDomainUtils.encodeXDomainCalldata(
      _target,
      msg.sender,
      _message,
      nonce
    );
    _sendXDomainMessage(
      ovmCanonicalTransactionChain,
      xDomainCalldata,
      _gasLimit
    );
    emit SentMessage(_target, msg.sender, _message, nonce, _gasLimit);
  }
  /**
   * Relays a cross domain message to a contract.
   * @inheritdoc IL1CrossDomainMessenger
   */
  function relayMessage(
    address _target,
    address _sender,
    bytes memory _message,
    uint256 _messageNonce,
    L2MessageInclusionProof memory _proof
  ) public nonReentrant whenNotPaused {
    bytes memory xDomainCalldata = Lib_CrossDomainUtils.encodeXDomainCalldata(
      _target,
      _sender,
      _message,
      _messageNonce
    );
    require(
      _verifyXDomainMessage(xDomainCalldata, _proof) == true,
      'Provided message could not be verified.'
    );
    bytes32 xDomainCalldataHash = keccak256(xDomainCalldata);
    require(
      successfulMessages[xDomainCalldataHash] == false,
      'Provided message has already been received.'
    );
    require(
      blockedMessages[xDomainCalldataHash] == false,
      'Provided message has been blocked.'
    );
    require(
      _target != resolve('CanonicalTransactionChain'),
      'Cannot send L2->L1 messages to L1 system contracts.'
    );
    xDomainMsgSender = _sender;
    (bool success, ) = _target.call(_message);
    xDomainMsgSender = Lib_DefaultValues.DEFAULT_XDOMAIN_SENDER;
    // Mark the message as received if the call was successful. Ensures that a message can be
    // relayed multiple times in the case that the call reverted.
    if (success == true) {
      successfulMessages[xDomainCalldataHash] = true;
      emit RelayedMessage(xDomainCalldataHash);
    } else {
      failedMessages[xDomainCalldataHash] = true;
      emit FailedRelayedMessage(xDomainCalldataHash);
    }
    // Store an identifier that can be used to prove that the given message was relayed by some
    // user. Gives us an easy way to pay relayers for their work.
    bytes32 relayId = keccak256(
      abi.encodePacked(xDomainCalldata, msg.sender, block.number)
    );
    relayedMessages[relayId] = true;
  }
  /**
   * Replays a cross domain message to the target messenger.
   * @inheritdoc IL1CrossDomainMessenger
   */
  function replayMessage(
    address _target,
    address _sender,
    bytes memory _message,
    uint256 _queueIndex,
    uint32 _oldGasLimit,
    uint32 _newGasLimit
  ) public {
    // Verify that the message is in the queue:
    address canonicalTransactionChain = resolve('CanonicalTransactionChain');
    Lib_OVMCodec.QueueElement memory element = ICanonicalTransactionChain(
      canonicalTransactionChain
    ).getQueueElement(_queueIndex);
    // Compute the calldata that was originally used to send the message.
    bytes memory xDomainCalldata = Lib_CrossDomainUtils.encodeXDomainCalldata(
      _target,
      _sender,
      _message,
      _queueIndex
    );
    // Compute the transactionHash
    bytes32 transactionHash = keccak256(
      abi.encode(
        AddressAliasHelper.applyL1ToL2Alias(address(this)),
        Lib_PredeployAddresses.L2_CROSS_DOMAIN_MESSENGER,
        _oldGasLimit,
        xDomainCalldata
      )
    );
    // Now check that the provided message data matches the one in the queue element.
    require(
      transactionHash == element.transactionHash,
      'Provided message has not been enqueued.'
    );
    // Send the same message but with the new gas limit.
    _sendXDomainMessage(
      canonicalTransactionChain,
      xDomainCalldata,
      _newGasLimit
    );
  }
  /**********************
   * Internal Functions *
   **********************/
  /**
   * Verifies that the given message is valid.
   * @param _xDomainCalldata Calldata to verify.
   * @param _proof Inclusion proof for the message.
   * @return Whether or not the provided message is valid.
   */
  function _verifyXDomainMessage(
    bytes memory _xDomainCalldata,
    L2MessageInclusionProof memory _proof
  ) internal view returns (bool) {
    return (_verifyStateRootProof(_proof) &&
      _verifyStorageProof(_xDomainCalldata, _proof));
  }
  /**
   * Verifies that the state root within an inclusion proof is valid.
   * @param _proof Message inclusion proof.
   * @return Whether or not the provided proof is valid.
   */
  function _verifyStateRootProof(L2MessageInclusionProof memory _proof)
    internal
    view
    returns (bool)
  {
    IStateCommitmentChain ovmStateCommitmentChain = IStateCommitmentChain(
      resolve('StateCommitmentChain')
    );
    return (ovmStateCommitmentChain.insideFraudProofWindow(
      _proof.stateRootBatchHeader
    ) ==
      false &&
      ovmStateCommitmentChain.verifyStateCommitment(
        _proof.stateRoot,
        _proof.stateRootBatchHeader,
        _proof.stateRootProof
      ));
  }
  /**
   * Verifies that the storage proof within an inclusion proof is valid.
   * @param _xDomainCalldata Encoded message calldata.
   * @param _proof Message inclusion proof.
   * @return Whether or not the provided proof is valid.
   */
  function _verifyStorageProof(
    bytes memory _xDomainCalldata,
    L2MessageInclusionProof memory _proof
  ) internal view returns (bool) {
    bytes32 storageKey = keccak256(
      abi.encodePacked(
        keccak256(
          abi.encodePacked(
            _xDomainCalldata,
            Lib_PredeployAddresses.L2_CROSS_DOMAIN_MESSENGER
          )
        ),
        uint256(0)
      )
    );
    (
      bool exists,
      bytes memory encodedMessagePassingAccount
    ) = Lib_SecureMerkleTrie.get(
        abi.encodePacked(Lib_PredeployAddresses.L2_TO_L1_MESSAGE_PASSER),
        _proof.stateTrieWitness,
        _proof.stateRoot
      );
    require(
      exists == true,
      'Message passing predeploy has not been initialized or invalid proof provided.'
    );
    Lib_OVMCodec.EVMAccount memory account = Lib_OVMCodec.decodeEVMAccount(
      encodedMessagePassingAccount
    );
    return
      Lib_SecureMerkleTrie.verifyInclusionProof(
        abi.encodePacked(storageKey),
        abi.encodePacked(uint8(1)),
        _proof.storageTrieWitness,
        account.storageRoot
      );
  }
  /**
   * Sends a cross domain message.
   * @param _canonicalTransactionChain Address of the CanonicalTransactionChain instance.
   * @param _message Message to send.
   * @param _gasLimit OVM gas limit for the message.
   */
  function _sendXDomainMessage(
    address _canonicalTransactionChain,
    bytes memory _message,
    uint256 _gasLimit
  ) internal {
    ICanonicalTransactionChain(_canonicalTransactionChain).enqueue(
      Lib_PredeployAddresses.L2_CROSS_DOMAIN_MESSENGER,
      _gasLimit,
      _message
    );
  }
}
// SPDX-License-Identifier: Apache-2.0
/*
 * Copyright 2019-2021, Offchain Labs, Inc.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *    http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
pragma solidity ^0.8.7;
library AddressAliasHelper {
  uint160 constant offset = uint160(0x1111000000000000000000000000000000001111);
  /// @notice Utility function that converts the address in the L1 that submitted a tx to
  /// the inbox to the msg.sender viewed in the L2
  /// @param l1Address the address in the L1 that triggered the tx to L2
  /// @return l2Address L2 address as viewed in msg.sender
  function applyL1ToL2Alias(address l1Address)
    internal
    pure
    returns (address l2Address)
  {
    unchecked {
      l2Address = address(uint160(l1Address) + offset);
    }
  }
  /// @notice Utility function that converts the msg.sender viewed in the L2 to the
  /// address in the L1 that submitted a tx to the inbox
  /// @param l2Address L2 address as viewed in msg.sender
  /// @return l1Address the address in the L1 that triggered the tx to L2
  function undoL1ToL2Alias(address l2Address)
    internal
    pure
    returns (address l1Address)
  {
    unchecked {
      l1Address = address(uint160(l2Address) - offset);
    }
  }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/* Library Imports */
import {Lib_AddressManager} from './Lib_AddressManager.sol';
/**
 * @title Lib_AddressResolver
 */
abstract contract Lib_AddressResolver {
  /*************
   * Variables *
   *************/
  Lib_AddressManager public libAddressManager;
  /***************
   * Constructor *
   ***************/
  /**
   * @param _libAddressManager Address of the Lib_AddressManager.
   */
  constructor(address _libAddressManager) {
    libAddressManager = Lib_AddressManager(_libAddressManager);
  }
  /********************
   * Public Functions *
   ********************/
  /**
   * Resolves the address associated with a given name.
   * @param _name Name to resolve an address for.
   * @return Address associated with the given name.
   */
  function resolve(string memory _name) public view returns (address) {
    return libAddressManager.getAddress(_name);
  }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/* Library Imports */
import {Lib_RLPReader} from '../rlp/Lib_RLPReader.sol';
import {Lib_RLPWriter} from '../rlp/Lib_RLPWriter.sol';
import {Lib_BytesUtils} from '../utils/Lib_BytesUtils.sol';
import {Lib_Bytes32Utils} from '../utils/Lib_Bytes32Utils.sol';
/**
 * @title Lib_OVMCodec
 */
library Lib_OVMCodec {
  /*********
   * Enums *
   *********/
  enum QueueOrigin {
    SEQUENCER_QUEUE,
    L1TOL2_QUEUE
  }
  /***********
   * Structs *
   ***********/
  struct EVMAccount {
    uint256 nonce;
    uint256 balance;
    bytes32 storageRoot;
    bytes32 codeHash;
  }
  struct ChainBatchHeader {
    uint256 batchIndex;
    bytes32 batchRoot;
    uint256 batchSize;
    uint256 prevTotalElements;
    bytes extraData;
  }
  struct ChainInclusionProof {
    uint256 index;
    bytes32[] siblings;
  }
  struct Transaction {
    uint256 timestamp;
    uint256 blockNumber;
    QueueOrigin l1QueueOrigin;
    address l1TxOrigin;
    address entrypoint;
    uint256 gasLimit;
    bytes data;
  }
  struct TransactionChainElement {
    bool isSequenced;
    uint256 queueIndex; // QUEUED TX ONLY
    uint256 timestamp; // SEQUENCER TX ONLY
    uint256 blockNumber; // SEQUENCER TX ONLY
    bytes txData; // SEQUENCER TX ONLY
  }
  struct QueueElement {
    bytes32 transactionHash;
    uint40 timestamp;
    uint40 blockNumber;
  }
  /**********************
   * Internal Functions *
   **********************/
  /**
   * Encodes a standard OVM transaction.
   * @param _transaction OVM transaction to encode.
   * @return Encoded transaction bytes.
   */
  function encodeTransaction(Transaction memory _transaction)
    internal
    pure
    returns (bytes memory)
  {
    return
      abi.encodePacked(
        _transaction.timestamp,
        _transaction.blockNumber,
        _transaction.l1QueueOrigin,
        _transaction.l1TxOrigin,
        _transaction.entrypoint,
        _transaction.gasLimit,
        _transaction.data
      );
  }
  /**
   * Hashes a standard OVM transaction.
   * @param _transaction OVM transaction to encode.
   * @return Hashed transaction
   */
  function hashTransaction(Transaction memory _transaction)
    internal
    pure
    returns (bytes32)
  {
    return keccak256(encodeTransaction(_transaction));
  }
  /**
   * @notice Decodes an RLP-encoded account state into a useful struct.
   * @param _encoded RLP-encoded account state.
   * @return Account state struct.
   */
  function decodeEVMAccount(bytes memory _encoded)
    internal
    pure
    returns (EVMAccount memory)
  {
    Lib_RLPReader.RLPItem[] memory accountState = Lib_RLPReader.readList(
      _encoded
    );
    return
      EVMAccount({
        nonce: Lib_RLPReader.readUint256(accountState[0]),
        balance: Lib_RLPReader.readUint256(accountState[1]),
        storageRoot: Lib_RLPReader.readBytes32(accountState[2]),
        codeHash: Lib_RLPReader.readBytes32(accountState[3])
      });
  }
  /**
   * Calculates a hash for a given batch header.
   * @param _batchHeader Header to hash.
   * @return Hash of the header.
   */
  function hashBatchHeader(Lib_OVMCodec.ChainBatchHeader memory _batchHeader)
    internal
    pure
    returns (bytes32)
  {
    return
      keccak256(
        abi.encode(
          _batchHeader.batchRoot,
          _batchHeader.batchSize,
          _batchHeader.prevTotalElements,
          _batchHeader.extraData
        )
      );
  }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/* External Imports */
import {Ownable} from '@openzeppelin/contracts/access/Ownable.sol';
/**
 * @title Lib_AddressManager
 */
contract Lib_AddressManager is Ownable {
  /**********
   * Events *
   **********/
  event AddressSet(
    string indexed _name,
    address _newAddress,
    address _oldAddress
  );
  /*************
   * Variables *
   *************/
  mapping(bytes32 => address) private addresses;
  /********************
   * Public Functions *
   ********************/
  /**
   * Changes the address associated with a particular name.
   * @param _name String name to associate an address with.
   * @param _address Address to associate with the name.
   */
  function setAddress(string memory _name, address _address)
    external
    onlyOwner
  {
    bytes32 nameHash = _getNameHash(_name);
    address oldAddress = addresses[nameHash];
    addresses[nameHash] = _address;
    emit AddressSet(_name, _address, oldAddress);
  }
  /**
   * Retrieves the address associated with a given name.
   * @param _name Name to retrieve an address for.
   * @return Address associated with the given name.
   */
  function getAddress(string memory _name) external view returns (address) {
    return addresses[_getNameHash(_name)];
  }
  /**********************
   * Internal Functions *
   **********************/
  /**
   * Computes the hash of a name.
   * @param _name Name to compute a hash for.
   * @return Hash of the given name.
   */
  function _getNameHash(string memory _name) internal pure returns (bytes32) {
    return keccak256(abi.encodePacked(_name));
  }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/* 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 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.8.9;
/**
 * @title Lib_DefaultValues
 */
library Lib_DefaultValues {
  // The default x-domain message sender being set to a non-zero value makes
  // deployment a bit more expensive, but in exchange the refund on every call to
  // `relayMessage` by the L1 and L2 messengers will be higher.
  address internal constant DEFAULT_XDOMAIN_SENDER =
    0x000000000000000000000000000000000000dEaD;
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/**
 * @title Lib_PredeployAddresses
 */
library Lib_PredeployAddresses {
  // solhint-disable max-line-length
  address internal constant L2_TO_L1_MESSAGE_PASSER =
    0x4200000000000000000000000000000000000000;
  address internal constant L1_MESSAGE_SENDER =
    0x4200000000000000000000000000000000000001;
  address internal constant DEPLOYER_WHITELIST =
    0x4200000000000000000000000000000000000002;
  address payable internal constant OVM_ETH =
    payable(0x4200000000000000000000000000000000000006);
  // solhint-disable-next-line max-line-length
  address internal constant L2_CROSS_DOMAIN_MESSENGER =
    0x4200000000000000000000000000000000000007;
  address internal constant LIB_ADDRESS_MANAGER =
    0x4200000000000000000000000000000000000008;
  address internal constant PROXY_EOA =
    0x4200000000000000000000000000000000000009;
  address internal constant L2_STANDARD_BRIDGE =
    0x4200000000000000000000000000000000000010;
  address internal constant SEQUENCER_FEE_WALLET =
    0x4200000000000000000000000000000000000011;
  address internal constant L2_STANDARD_TOKEN_FACTORY =
    0x4200000000000000000000000000000000000012;
  address internal constant L1_BLOCK_NUMBER =
    0x4200000000000000000000000000000000000013;
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/* Library Imports */
import {Lib_RLPReader} from '../rlp/Lib_RLPReader.sol';
/**
 * @title Lib_CrossDomainUtils
 */
library Lib_CrossDomainUtils {
  /**
   * Generates the correct cross domain calldata for a message.
   * @param _target Target contract address.
   * @param _sender Message sender address.
   * @param _message Message to send to the target.
   * @param _messageNonce Nonce for the provided message.
   * @return ABI encoded cross domain calldata.
   */
  function encodeXDomainCalldata(
    address _target,
    address _sender,
    bytes memory _message,
    uint256 _messageNonce
  ) internal pure returns (bytes memory) {
    return
      abi.encodeWithSignature(
        'relayMessage(address,address,bytes,uint256)',
        _target,
        _sender,
        _message,
        _messageNonce
      );
  }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/* Library Imports */
import {Lib_OVMCodec} from '../../libraries/codec/Lib_OVMCodec.sol';
/* Interface Imports */
import {ICrossDomainMessenger} from '../../libraries/bridge/ICrossDomainMessenger.sol';
/**
 * @title IL1CrossDomainMessenger
 */
interface IL1CrossDomainMessenger is ICrossDomainMessenger {
  /*******************
   * Data Structures *
   *******************/
  struct L2MessageInclusionProof {
    bytes32 stateRoot;
    Lib_OVMCodec.ChainBatchHeader stateRootBatchHeader;
    Lib_OVMCodec.ChainInclusionProof stateRootProof;
    bytes stateTrieWitness;
    bytes storageTrieWitness;
  }
  /********************
   * Public Functions *
   ********************/
  /**
   * Relays a cross domain message to a contract.
   * @param _target Target contract address.
   * @param _sender Message sender address.
   * @param _message Message to send to the target.
   * @param _messageNonce Nonce for the provided message.
   * @param _proof Inclusion proof for the given message.
   */
  function relayMessage(
    address _target,
    address _sender,
    bytes memory _message,
    uint256 _messageNonce,
    L2MessageInclusionProof memory _proof
  ) external;
  /**
   * Replays a cross domain message to the target messenger.
   * @param _target Target contract address.
   * @param _sender Original sender address.
   * @param _message Message to send to the target.
   * @param _queueIndex CTC Queue index for the message to replay.
   * @param _oldGasLimit Original gas limit used to send the message.
   * @param _newGasLimit New gas limit to be used for this message.
   */
  function replayMessage(
    address _target,
    address _sender,
    bytes memory _message,
    uint256 _queueIndex,
    uint32 _oldGasLimit,
    uint32 _newGasLimit
  ) external;
}
// SPDX-License-Identifier: MIT
pragma solidity >0.5.0 <0.9.0;
/* Library Imports */
import {Lib_OVMCodec} from '../../libraries/codec/Lib_OVMCodec.sol';
/* Interface Imports */
import {IChainStorageContainer} from './IChainStorageContainer.sol';
/**
 * @title ICanonicalTransactionChain
 */
interface ICanonicalTransactionChain {
  /**********
   * Events *
   **********/
  event L2GasParamsUpdated(
    uint256 l2GasDiscountDivisor,
    uint256 enqueueGasCost,
    uint256 enqueueL2GasPrepaid
  );
  event TransactionEnqueued(
    address indexed _l1TxOrigin,
    address indexed _target,
    uint256 _gasLimit,
    bytes _data,
    uint256 indexed _queueIndex,
    uint256 _timestamp
  );
  event QueueBatchAppended(
    uint256 _startingQueueIndex,
    uint256 _numQueueElements,
    uint256 _totalElements
  );
  event SequencerBatchAppended(
    uint256 _startingQueueIndex,
    uint256 _numQueueElements,
    uint256 _totalElements
  );
  event TransactionBatchAppended(
    uint256 indexed _batchIndex,
    bytes32 _batchRoot,
    uint256 _batchSize,
    uint256 _prevTotalElements,
    bytes _extraData
  );
  /***********
   * Structs *
   ***********/
  struct BatchContext {
    uint256 numSequencedTransactions;
    uint256 numSubsequentQueueTransactions;
    uint256 timestamp;
    uint256 blockNumber;
  }
  /*******************************
   * Authorized Setter Functions *
   *******************************/
  /**
   * Allows the Burn Admin to update the parameters which determine the amount of gas to burn.
   * The value of enqueueL2GasPrepaid is immediately updated as well.
   */
  function setGasParams(uint256 _l2GasDiscountDivisor, uint256 _enqueueGasCost)
    external;
  /********************
   * Public Functions *
   ********************/
  /**
   * Accesses the batch storage container.
   * @return Reference to the batch storage container.
   */
  function batches() external view returns (IChainStorageContainer);
  /**
   * Accesses the queue storage container.
   * @return Reference to the queue storage container.
   */
  function queue() external view returns (IChainStorageContainer);
  /**
   * Retrieves the total number of elements submitted.
   * @return _totalElements Total submitted elements.
   */
  function getTotalElements() external view returns (uint256 _totalElements);
  /**
   * Retrieves the total number of batches submitted.
   * @return _totalBatches Total submitted batches.
   */
  function getTotalBatches() external view returns (uint256 _totalBatches);
  /**
   * Returns the index of the next element to be enqueued.
   * @return Index for the next queue element.
   */
  function getNextQueueIndex() external view returns (uint40);
  /**
   * Gets the queue element at a particular index.
   * @param _index Index of the queue element to access.
   * @return _element Queue element at the given index.
   */
  function getQueueElement(uint256 _index)
    external
    view
    returns (Lib_OVMCodec.QueueElement memory _element);
  /**
   * Returns the timestamp of the last transaction.
   * @return Timestamp for the last transaction.
   */
  function getLastTimestamp() external view returns (uint40);
  /**
   * Returns the blocknumber of the last transaction.
   * @return Blocknumber for the last transaction.
   */
  function getLastBlockNumber() external view returns (uint40);
  /**
   * Get the number of queue elements which have not yet been included.
   * @return Number of pending queue elements.
   */
  function getNumPendingQueueElements() external view returns (uint40);
  /**
   * Retrieves the length of the queue, including
   * both pending and canonical transactions.
   * @return Length of the queue.
   */
  function getQueueLength() external view returns (uint40);
  /**
   * Adds a transaction to the queue.
   * @param _target Target contract to send the transaction to.
   * @param _gasLimit Gas limit for the given transaction.
   * @param _data Transaction data.
   */
  function enqueue(
    address _target,
    uint256 _gasLimit,
    bytes memory _data
  ) external;
  /**
   * Allows the sequencer to append a batch of transactions.
   * @dev This function uses a custom encoding scheme for efficiency reasons.
   * .param _shouldStartAtElement Specific batch we expect to start appending to.
   * .param _totalElementsToAppend Total number of batch elements we expect to append.
   * .param _contexts Array of batch contexts.
   * .param _transactionDataFields Array of raw transaction data.
   */
  function appendSequencerBatch(
    // uint40 _shouldStartAtElement,
    // uint24 _totalElementsToAppend,
    // BatchContext[] _contexts,
    // bytes[] _transactionDataFields
  ) external;
}
// SPDX-License-Identifier: MIT
pragma solidity >0.5.0 <0.9.0;
/* Library Imports */
import {Lib_OVMCodec} from '../../libraries/codec/Lib_OVMCodec.sol';
/**
 * @title IStateCommitmentChain
 */
interface IStateCommitmentChain {
  /**********
   * Events *
   **********/
  event StateBatchAppended(
    uint256 indexed _batchIndex,
    bytes32 _batchRoot,
    uint256 _batchSize,
    uint256 _prevTotalElements,
    bytes _extraData
  );
  event StateBatchDeleted(uint256 indexed _batchIndex, bytes32 _batchRoot);
  /********************
   * Public Functions *
   ********************/
  /**
   * Retrieves the total number of elements submitted.
   * @return _totalElements Total submitted elements.
   */
  function getTotalElements() external view returns (uint256 _totalElements);
  /**
   * Retrieves the total number of batches submitted.
   * @return _totalBatches Total submitted batches.
   */
  function getTotalBatches() external view returns (uint256 _totalBatches);
  /**
   * Retrieves the timestamp of the last batch submitted by the sequencer.
   * @return _lastSequencerTimestamp Last sequencer batch timestamp.
   */
  function getLastSequencerTimestamp()
    external
    view
    returns (uint256 _lastSequencerTimestamp);
  /**
   * Appends a batch of state roots to the chain.
   * @param _batch Batch of state roots.
   * @param _shouldStartAtElement Index of the element at which this batch should start.
   */
  function appendStateBatch(
    bytes32[] calldata _batch,
    uint256 _shouldStartAtElement
  ) external;
  /**
   * Deletes all state roots after (and including) a given batch.
   * @param _batchHeader Header of the batch to start deleting from.
   */
  function deleteStateBatch(Lib_OVMCodec.ChainBatchHeader memory _batchHeader)
    external;
  /**
   * Verifies a batch inclusion proof.
   * @param _element Hash of the element to verify a proof for.
   * @param _batchHeader Header of the batch in which the element was included.
   * @param _proof Merkle inclusion proof for the element.
   */
  function verifyStateCommitment(
    bytes32 _element,
    Lib_OVMCodec.ChainBatchHeader memory _batchHeader,
    Lib_OVMCodec.ChainInclusionProof memory _proof
  ) external view returns (bool _verified);
  /**
   * Checks whether a given batch is still inside its fraud proof window.
   * @param _batchHeader Header of the batch to check.
   * @return _inside Whether or not the batch is inside the fraud proof window.
   */
  function insideFraudProofWindow(
    Lib_OVMCodec.ChainBatchHeader memory _batchHeader
  ) external view returns (bool _inside);
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
import "../utils/ContextUpgradeable.sol";
import "../proxy/utils/Initializable.sol";
/**
 * @dev Contract module which provides a basic access control mechanism, where
 * there is an account (an owner) that can be granted exclusive access to
 * specific functions.
 *
 * By default, the owner account will be the one that deploys the contract. This
 * can later be changed with {transferOwnership}.
 *
 * This module is used through inheritance. It will make available the modifier
 * `onlyOwner`, which can be applied to your functions to restrict their use to
 * the owner.
 */
abstract contract OwnableUpgradeable is Initializable, ContextUpgradeable {
    address private _owner;
    event OwnershipTransferred(address indexed previousOwner, address indexed newOwner);
    /**
     * @dev Initializes the contract setting the deployer as the initial owner.
     */
    function __Ownable_init() internal initializer {
        __Context_init_unchained();
        __Ownable_init_unchained();
    }
    function __Ownable_init_unchained() internal initializer {
        _setOwner(_msgSender());
    }
    /**
     * @dev Returns the address of the current owner.
     */
    function owner() public view virtual returns (address) {
        return _owner;
    }
    /**
     * @dev Throws if called by any account other than the owner.
     */
    modifier onlyOwner() {
        require(owner() == _msgSender(), "Ownable: caller is not the owner");
        _;
    }
    /**
     * @dev Leaves the contract without owner. It will not be possible to call
     * `onlyOwner` functions anymore. Can only be called by the current owner.
     *
     * NOTE: Renouncing ownership will leave the contract without an owner,
     * thereby removing any functionality that is only available to the owner.
     */
    function renounceOwnership() public virtual onlyOwner {
        _setOwner(address(0));
    }
    /**
     * @dev Transfers ownership of the contract to a new account (`newOwner`).
     * Can only be called by the current owner.
     */
    function transferOwnership(address newOwner) public virtual onlyOwner {
        require(newOwner != address(0), "Ownable: new owner is the zero address");
        _setOwner(newOwner);
    }
    function _setOwner(address newOwner) private {
        address oldOwner = _owner;
        _owner = newOwner;
        emit OwnershipTransferred(oldOwner, newOwner);
    }
    uint256[49] private __gap;
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
import "../utils/ContextUpgradeable.sol";
import "../proxy/utils/Initializable.sol";
/**
 * @dev Contract module which allows children to implement an emergency stop
 * mechanism that can be triggered by an authorized account.
 *
 * This module is used through inheritance. It will make available the
 * modifiers `whenNotPaused` and `whenPaused`, which can be applied to
 * the functions of your contract. Note that they will not be pausable by
 * simply including this module, only once the modifiers are put in place.
 */
abstract contract PausableUpgradeable is Initializable, ContextUpgradeable {
    /**
     * @dev Emitted when the pause is triggered by `account`.
     */
    event Paused(address account);
    /**
     * @dev Emitted when the pause is lifted by `account`.
     */
    event Unpaused(address account);
    bool private _paused;
    /**
     * @dev Initializes the contract in unpaused state.
     */
    function __Pausable_init() internal initializer {
        __Context_init_unchained();
        __Pausable_init_unchained();
    }
    function __Pausable_init_unchained() internal initializer {
        _paused = false;
    }
    /**
     * @dev Returns true if the contract is paused, and false otherwise.
     */
    function paused() public view virtual returns (bool) {
        return _paused;
    }
    /**
     * @dev Modifier to make a function callable only when the contract is not paused.
     *
     * Requirements:
     *
     * - The contract must not be paused.
     */
    modifier whenNotPaused() {
        require(!paused(), "Pausable: paused");
        _;
    }
    /**
     * @dev Modifier to make a function callable only when the contract is paused.
     *
     * Requirements:
     *
     * - The contract must be paused.
     */
    modifier whenPaused() {
        require(paused(), "Pausable: not paused");
        _;
    }
    /**
     * @dev Triggers stopped state.
     *
     * Requirements:
     *
     * - The contract must not be paused.
     */
    function _pause() internal virtual whenNotPaused {
        _paused = true;
        emit Paused(_msgSender());
    }
    /**
     * @dev Returns to normal state.
     *
     * Requirements:
     *
     * - The contract must be paused.
     */
    function _unpause() internal virtual whenPaused {
        _paused = false;
        emit Unpaused(_msgSender());
    }
    uint256[49] private __gap;
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
import "../proxy/utils/Initializable.sol";
/**
 * @dev Contract module that helps prevent reentrant calls to a function.
 *
 * Inheriting from `ReentrancyGuard` will make the {nonReentrant} modifier
 * available, which can be applied to functions to make sure there are no nested
 * (reentrant) calls to them.
 *
 * Note that because there is a single `nonReentrant` guard, functions marked as
 * `nonReentrant` may not call one another. This can be worked around by making
 * those functions `private`, and then adding `external` `nonReentrant` entry
 * points to them.
 *
 * TIP: If you would like to learn more about reentrancy and alternative ways
 * to protect against it, check out our blog post
 * https://blog.openzeppelin.com/reentrancy-after-istanbul/[Reentrancy After Istanbul].
 */
abstract contract ReentrancyGuardUpgradeable is Initializable {
    // Booleans are more expensive than uint256 or any type that takes up a full
    // word because each write operation emits an extra SLOAD to first read the
    // slot's contents, replace the bits taken up by the boolean, and then write
    // back. This is the compiler's defense against contract upgrades and
    // pointer aliasing, and it cannot be disabled.
    // The values being non-zero value makes deployment a bit more expensive,
    // but in exchange the refund on every call to nonReentrant will be lower in
    // amount. Since refunds are capped to a percentage of the total
    // transaction's gas, it is best to keep them low in cases like this one, to
    // increase the likelihood of the full refund coming into effect.
    uint256 private constant _NOT_ENTERED = 1;
    uint256 private constant _ENTERED = 2;
    uint256 private _status;
    function __ReentrancyGuard_init() internal initializer {
        __ReentrancyGuard_init_unchained();
    }
    function __ReentrancyGuard_init_unchained() internal initializer {
        _status = _NOT_ENTERED;
    }
    /**
     * @dev Prevents a contract from calling itself, directly or indirectly.
     * Calling a `nonReentrant` function from another `nonReentrant`
     * function is not supported. It is possible to prevent this from happening
     * by making the `nonReentrant` function external, and make it call a
     * `private` function that does the actual work.
     */
    modifier nonReentrant() {
        // On the first call to nonReentrant, _notEntered will be true
        require(_status != _ENTERED, "ReentrancyGuard: reentrant call");
        // Any calls to nonReentrant after this point will fail
        _status = _ENTERED;
        _;
        // By storing the original value once again, a refund is triggered (see
        // https://eips.ethereum.org/EIPS/eip-2200)
        _status = _NOT_ENTERED;
    }
    uint256[49] private __gap;
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
import "../utils/Context.sol";
/**
 * @dev Contract module which provides a basic access control mechanism, where
 * there is an account (an owner) that can be granted exclusive access to
 * specific functions.
 *
 * By default, the owner account will be the one that deploys the contract. This
 * can later be changed with {transferOwnership}.
 *
 * This module is used through inheritance. It will make available the modifier
 * `onlyOwner`, which can be applied to your functions to restrict their use to
 * the owner.
 */
abstract contract Ownable is Context {
    address private _owner;
    event OwnershipTransferred(address indexed previousOwner, address indexed newOwner);
    /**
     * @dev Initializes the contract setting the deployer as the initial owner.
     */
    constructor() {
        _setOwner(_msgSender());
    }
    /**
     * @dev Returns the address of the current owner.
     */
    function owner() public view virtual returns (address) {
        return _owner;
    }
    /**
     * @dev Throws if called by any account other than the owner.
     */
    modifier onlyOwner() {
        require(owner() == _msgSender(), "Ownable: caller is not the owner");
        _;
    }
    /**
     * @dev Leaves the contract without owner. It will not be possible to call
     * `onlyOwner` functions anymore. Can only be called by the current owner.
     *
     * NOTE: Renouncing ownership will leave the contract without an owner,
     * thereby removing any functionality that is only available to the owner.
     */
    function renounceOwnership() public virtual onlyOwner {
        _setOwner(address(0));
    }
    /**
     * @dev Transfers ownership of the contract to a new account (`newOwner`).
     * Can only be called by the current owner.
     */
    function transferOwnership(address newOwner) public virtual onlyOwner {
        require(newOwner != address(0), "Ownable: new owner is the zero address");
        _setOwner(newOwner);
    }
    function _setOwner(address newOwner) private {
        address oldOwner = _owner;
        _owner = newOwner;
        emit OwnershipTransferred(oldOwner, newOwner);
    }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
/**
 * @dev Provides information about the current execution context, including the
 * sender of the transaction and its data. While these are generally available
 * via msg.sender and msg.data, they should not be accessed in such a direct
 * manner, since when dealing with meta-transactions the account sending and
 * paying for execution may not be the actual sender (as far as an application
 * is concerned).
 *
 * This contract is only required for intermediate, library-like contracts.
 */
abstract contract Context {
    function _msgSender() internal view virtual returns (address) {
        return msg.sender;
    }
    function _msgData() internal view virtual returns (bytes calldata) {
        return msg.data;
    }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/**
 * @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
    )
  {
    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) {
    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;
    unchecked {
      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: MIT
pragma solidity ^0.8.9;
/**
 * @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 The RLP encoded string in bytes.
   */
  function writeBytes(bytes memory _in) internal pure returns (bytes memory) {
    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 The RLP encoded list of items in bytes.
   */
  function writeList(bytes[] memory _in) internal pure returns (bytes memory) {
    bytes memory list = _flatten(_in);
    return abi.encodePacked(_writeLength(list.length, 192), list);
  }
  /**
   * RLP encodes a string.
   * @param _in The string to encode.
   * @return The RLP encoded string in bytes.
   */
  function writeString(string memory _in) internal pure returns (bytes memory) {
    return writeBytes(bytes(_in));
  }
  /**
   * RLP encodes an address.
   * @param _in The address to encode.
   * @return The RLP encoded address in bytes.
   */
  function writeAddress(address _in) internal pure returns (bytes memory) {
    return writeBytes(abi.encodePacked(_in));
  }
  /**
   * RLP encodes a uint.
   * @param _in The uint256 to encode.
   * @return The RLP encoded uint256 in bytes.
   */
  function writeUint(uint256 _in) internal pure returns (bytes memory) {
    return writeBytes(_toBinary(_in));
  }
  /**
   * RLP encodes a bool.
   * @param _in The bool to encode.
   * @return The RLP encoded bool in bytes.
   */
  function writeBool(bool _in) internal pure returns (bytes memory) {
    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 RLP encoded bytes.
   */
  function _writeLength(uint256 _len, uint256 _offset)
    private
    pure
    returns (bytes memory)
  {
    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 RLP encoded bytes.
   */
  function _toBinary(uint256 _x) private pure returns (bytes memory) {
    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;
    unchecked {
      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 The flattened byte string.
   */
  function _flatten(bytes[] memory _list) private pure returns (bytes memory) {
    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;
  }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/**
 * @title Lib_BytesUtils
 */
library Lib_BytesUtils {
  /**********************
   * Internal Functions *
   **********************/
  function slice(
    bytes memory _bytes,
    uint256 _start,
    uint256 _length
  ) internal pure returns (bytes memory) {
    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)
  {
    if (_start >= _bytes.length) {
      return bytes('');
    }
    return slice(_bytes, _start, _bytes.length - _start);
  }
  function toBytes32(bytes memory _bytes) internal pure returns (bytes32) {
    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 toNibbles(bytes memory _bytes) internal pure returns (bytes memory) {
    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)
  {
    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.8.9;
/**
 * @title Lib_Byte32Utils
 */
library Lib_Bytes32Utils {
  /**********************
   * Internal Functions *
   **********************/
  /**
   * Converts a bytes32 value to a boolean. Anything non-zero will be converted to "true."
   * @param _in Input bytes32 value.
   * @return Bytes32 as a boolean.
   */
  function toBool(bytes32 _in) internal pure returns (bool) {
    return _in != 0;
  }
  /**
   * Converts a boolean to a bytes32 value.
   * @param _in Input boolean value.
   * @return Boolean as a bytes32.
   */
  function fromBool(bool _in) internal pure returns (bytes32) {
    return bytes32(uint256(_in ? 1 : 0));
  }
  /**
   * Converts a bytes32 value to an address. Takes the *last* 20 bytes.
   * @param _in Input bytes32 value.
   * @return Bytes32 as an address.
   */
  function toAddress(bytes32 _in) internal pure returns (address) {
    return address(uint160(uint256(_in)));
  }
  /**
   * Converts an address to a bytes32.
   * @param _in Input address value.
   * @return Address as a bytes32.
   */
  function fromAddress(address _in) internal pure returns (bytes32) {
    return bytes32(uint256(uint160(_in)));
  }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/* 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 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,
      _key,
      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 != pathRemainder.length) {
            // Our extension node is not identical to the remainder.
            // 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 _key Full original key.
   * @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 _key,
    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;
    // solhint-disable-next-line max-line-length
    // Reference: https://github.com/ethereumjs/merkle-patricia-tree/blob/c0a10395aab37d42c175a47114ebfcbd7efcf059/src/baseTrie.ts#L294-L313
    bool matchLeaf = false;
    if (lastNodeType == NodeType.LeafNode) {
      uint256 l = 0;
      if (_path.length > 0) {
        for (uint256 i = 0; i < _path.length - 1; i++) {
          if (_getNodeType(_path[i]) == NodeType.BranchNode) {
            l++;
          } else {
            l += _getNodeKey(_path[i]).length;
          }
        }
      }
      if (
        _getSharedNibbleLength(
          _getNodeKey(lastNode),
          Lib_BytesUtils.slice(Lib_BytesUtils.toNibbles(_key), l)
        ) ==
        _getNodeKey(lastNode).length &&
        keyRemainder.length == 0
      ) {
        matchLeaf = true;
      }
    }
    if (matchLeaf) {
      // 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 = _editExtensionNodeValue(currentNode, 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);
  }
  /**
   * Creates a new extension node with the same key but a different value.
   * @param _node Extension node to copy and modify.
   * @param _value New value for the extension node.
   * @return New node with the same key and different value.
   */
  function _editExtensionNodeValue(TrieNode memory _node, bytes memory _value)
    private
    pure
    returns (TrieNode memory)
  {
    bytes[] memory raw = new bytes[](2);
    bytes memory key = _addHexPrefix(_getNodeKey(_node), false);
    raw[0] = Lib_RLPWriter.writeBytes(Lib_BytesUtils.fromNibbles(key));
    if (_value.length < 32) {
      raw[1] = _value;
    } else {
      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.9.0;
/**
 * @title ICrossDomainMessenger
 */
interface ICrossDomainMessenger {
  /**********
   * Events *
   **********/
  event SentMessage(
    address indexed target,
    address sender,
    bytes message,
    uint256 messageNonce,
    uint256 gasLimit
  );
  event RelayedMessage(bytes32 indexed msgHash);
  event FailedRelayedMessage(bytes32 indexed msgHash);
  /*************
   * Variables *
   *************/
  function xDomainMessageSender() external view returns (address);
  /********************
   * Public Functions *
   ********************/
  /**
   * Sends a cross domain message to the target messenger.
   * @param _target Target contract address.
   * @param _message Message to send to the target.
   * @param _gasLimit Gas limit for the provided message.
   */
  function sendMessage(
    address _target,
    bytes calldata _message,
    uint32 _gasLimit
  ) external;
}
// SPDX-License-Identifier: MIT
pragma solidity >0.5.0 <0.9.0;
/**
 * @title IChainStorageContainer
 */
interface IChainStorageContainer {
  /********************
   * Public Functions *
   ********************/
  /**
   * Sets the container's global metadata field. We're using `bytes27` here because we use five
   * bytes to maintain the length of the underlying data structure, meaning we have an extra
   * 27 bytes to store arbitrary data.
   * @param _globalMetadata New global metadata to set.
   */
  function setGlobalMetadata(bytes27 _globalMetadata) external;
  /**
   * Retrieves the container's global metadata field.
   * @return Container global metadata field.
   */
  function getGlobalMetadata() external view returns (bytes27);
  /**
   * Retrieves the number of objects stored in the container.
   * @return Number of objects in the container.
   */
  function length() external view returns (uint256);
  /**
   * Pushes an object into the container.
   * @param _object A 32 byte value to insert into the container.
   */
  function push(bytes32 _object) external;
  /**
   * Pushes an object into the container. Function allows setting the global metadata since
   * we'll need to touch the "length" storage slot anyway, which also contains the global
   * metadata (it's an optimization).
   * @param _object A 32 byte value to insert into the container.
   * @param _globalMetadata New global metadata for the container.
   */
  function push(bytes32 _object, bytes27 _globalMetadata) external;
  /**
   * Retrieves an object from the container.
   * @param _index Index of the particular object to access.
   * @return 32 byte object value.
   */
  function get(uint256 _index) external view returns (bytes32);
  /**
   * Removes all objects after and including a given index.
   * @param _index Object index to delete from.
   */
  function deleteElementsAfterInclusive(uint256 _index) external;
  /**
   * Removes all objects after and including a given index. Also allows setting the global
   * metadata field.
   * @param _index Object index to delete from.
   * @param _globalMetadata New global metadata for the container.
   */
  function deleteElementsAfterInclusive(uint256 _index, bytes27 _globalMetadata)
    external;
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
import "../proxy/utils/Initializable.sol";
/**
 * @dev Provides information about the current execution context, including the
 * sender of the transaction and its data. While these are generally available
 * via msg.sender and msg.data, they should not be accessed in such a direct
 * manner, since when dealing with meta-transactions the account sending and
 * paying for execution may not be the actual sender (as far as an application
 * is concerned).
 *
 * This contract is only required for intermediate, library-like contracts.
 */
abstract contract ContextUpgradeable is Initializable {
    function __Context_init() internal initializer {
        __Context_init_unchained();
    }
    function __Context_init_unchained() internal initializer {
    }
    function _msgSender() internal view virtual returns (address) {
        return msg.sender;
    }
    function _msgData() internal view virtual returns (bytes calldata) {
        return msg.data;
    }
    uint256[50] private __gap;
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
/**
 * @dev This is a base contract to aid in writing upgradeable contracts, or any kind of contract that will be deployed
 * behind a proxy. Since a proxied contract can't have a constructor, it's common to move constructor logic to an
 * external initializer function, usually called `initialize`. It then becomes necessary to protect this initializer
 * function so it can only be called once. The {initializer} modifier provided by this contract will have this effect.
 *
 * TIP: To avoid leaving the proxy in an uninitialized state, the initializer function should be called as early as
 * possible by providing the encoded function call as the `_data` argument to {ERC1967Proxy-constructor}.
 *
 * CAUTION: When used with inheritance, manual care must be taken to not invoke a parent initializer twice, or to ensure
 * that all initializers are idempotent. This is not verified automatically as constructors are by Solidity.
 */
abstract contract Initializable {
    /**
     * @dev Indicates that the contract has been initialized.
     */
    bool private _initialized;
    /**
     * @dev Indicates that the contract is in the process of being initialized.
     */
    bool private _initializing;
    /**
     * @dev Modifier to protect an initializer function from being invoked twice.
     */
    modifier initializer() {
        require(_initializing || !_initialized, "Initializable: contract is already initialized");
        bool isTopLevelCall = !_initializing;
        if (isTopLevelCall) {
            _initializing = true;
            _initialized = true;
        }
        _;
        if (isTopLevelCall) {
            _initializing = false;
        }
    }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/* Library Imports */
import {Lib_OVMCodec} from '../../libraries/codec/Lib_OVMCodec.sol';
import {Lib_AddressResolver} from '../../libraries/resolver/Lib_AddressResolver.sol';
import {Lib_MerkleTree} from '../../libraries/utils/Lib_MerkleTree.sol';
/* Interface Imports */
import {IStateCommitmentChain} from './IStateCommitmentChain.sol';
import {ICanonicalTransactionChain} from './ICanonicalTransactionChain.sol';
import {IBondManager} from '../verification/IBondManager.sol';
import {IChainStorageContainer} from './IChainStorageContainer.sol';
/**
 * @title StateCommitmentChain
 * @dev The State Commitment Chain (SCC) contract contains a list of proposed state roots which
 * Proposers assert to be a result of each transaction in the Canonical Transaction Chain (CTC).
 * Elements here have a 1:1 correspondence with transactions in the CTC, and should be the unique
 * state root calculated off-chain by applying the canonical transactions one by one.
 *
 * Runtime target: EVM
 */
contract StateCommitmentChain is IStateCommitmentChain, Lib_AddressResolver {
  /*************
   * Constants *
   *************/
  uint256 public FRAUD_PROOF_WINDOW;
  uint256 public SEQUENCER_PUBLISH_WINDOW;
  /***************
   * Constructor *
   ***************/
  /**
   * @param _libAddressManager Address of the Address Manager.
   */
  constructor(
    address _libAddressManager,
    uint256 _fraudProofWindow,
    uint256 _sequencerPublishWindow
  ) Lib_AddressResolver(_libAddressManager) {
    FRAUD_PROOF_WINDOW = _fraudProofWindow;
    SEQUENCER_PUBLISH_WINDOW = _sequencerPublishWindow;
  }
  /********************
   * Public Functions *
   ********************/
  /**
   * Accesses the batch storage container.
   * @return Reference to the batch storage container.
   */
  function batches() public view returns (IChainStorageContainer) {
    return IChainStorageContainer(resolve('ChainStorageContainer-SCC-batches'));
  }
  /**
   * @inheritdoc IStateCommitmentChain
   */
  function getTotalElements() public view returns (uint256 _totalElements) {
    (uint40 totalElements, ) = _getBatchExtraData();
    return uint256(totalElements);
  }
  /**
   * @inheritdoc IStateCommitmentChain
   */
  function getTotalBatches() public view returns (uint256 _totalBatches) {
    return batches().length();
  }
  /**
   * @inheritdoc IStateCommitmentChain
   */
  function getLastSequencerTimestamp()
    public
    view
    returns (uint256 _lastSequencerTimestamp)
  {
    (, uint40 lastSequencerTimestamp) = _getBatchExtraData();
    return uint256(lastSequencerTimestamp);
  }
  /**
   * @inheritdoc IStateCommitmentChain
   */
  function appendStateBatch(
    bytes32[] memory _batch,
    uint256 _shouldStartAtElement
  ) public {
    // Fail fast in to make sure our batch roots aren't accidentally made fraudulent by the
    // publication of batches by some other user.
    require(
      _shouldStartAtElement == getTotalElements(),
      'Actual batch start index does not match expected start index.'
    );
    // Proposers must have previously staked at the BondManager
    require(
      IBondManager(resolve('BondManager')).isCollateralized(msg.sender),
      'Proposer does not have enough collateral posted'
    );
    require(_batch.length > 0, 'Cannot submit an empty state batch.');
    require(
      getTotalElements() + _batch.length <=
        ICanonicalTransactionChain(resolve('CanonicalTransactionChain'))
          .getTotalElements(),
      'Number of state roots cannot exceed the number of canonical transactions.'
    );
    // Pass the block's timestamp and the publisher of the data
    // to be used in the fraud proofs
    _appendBatch(_batch, abi.encode(block.timestamp, msg.sender));
  }
  /**
   * @inheritdoc IStateCommitmentChain
   */
  function deleteStateBatch(Lib_OVMCodec.ChainBatchHeader memory _batchHeader)
    public
  {
    require(
      msg.sender == resolve('OVM_FraudVerifier'),
      'State batches can only be deleted by the OVM_FraudVerifier.'
    );
    require(_isValidBatchHeader(_batchHeader), 'Invalid batch header.');
    require(
      insideFraudProofWindow(_batchHeader),
      'State batches can only be deleted within the fraud proof window.'
    );
    _deleteBatch(_batchHeader);
  }
  /**
   * @inheritdoc IStateCommitmentChain
   */
  function verifyStateCommitment(
    bytes32 _element,
    Lib_OVMCodec.ChainBatchHeader memory _batchHeader,
    Lib_OVMCodec.ChainInclusionProof memory _proof
  ) public view returns (bool) {
    require(_isValidBatchHeader(_batchHeader), 'Invalid batch header.');
    require(
      Lib_MerkleTree.verify(
        _batchHeader.batchRoot,
        _element,
        _proof.index,
        _proof.siblings,
        _batchHeader.batchSize
      ),
      'Invalid inclusion proof.'
    );
    return true;
  }
  /**
   * @inheritdoc IStateCommitmentChain
   */
  function insideFraudProofWindow(
    Lib_OVMCodec.ChainBatchHeader memory _batchHeader
  ) public view returns (bool _inside) {
    (uint256 timestamp, ) = abi.decode(
      _batchHeader.extraData,
      (uint256, address)
    );
    require(timestamp != 0, 'Batch header timestamp cannot be zero');
    return (timestamp + FRAUD_PROOF_WINDOW) > block.timestamp;
  }
  /**********************
   * Internal Functions *
   **********************/
  /**
   * Parses the batch context from the extra data.
   * @return Total number of elements submitted.
   * @return Timestamp of the last batch submitted by the sequencer.
   */
  function _getBatchExtraData() internal view returns (uint40, uint40) {
    bytes27 extraData = batches().getGlobalMetadata();
    // solhint-disable max-line-length
    uint40 totalElements;
    uint40 lastSequencerTimestamp;
    assembly {
      extraData := shr(40, extraData)
      totalElements := and(
        extraData,
        0x000000000000000000000000000000000000000000000000000000FFFFFFFFFF
      )
      lastSequencerTimestamp := shr(
        40,
        and(
          extraData,
          0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF0000000000
        )
      )
    }
    // solhint-enable max-line-length
    return (totalElements, lastSequencerTimestamp);
  }
  /**
   * Encodes the batch context for the extra data.
   * @param _totalElements Total number of elements submitted.
   * @param _lastSequencerTimestamp Timestamp of the last batch submitted by the sequencer.
   * @return Encoded batch context.
   */
  function _makeBatchExtraData(
    uint40 _totalElements,
    uint40 _lastSequencerTimestamp
  ) internal pure returns (bytes27) {
    bytes27 extraData;
    assembly {
      extraData := _totalElements
      extraData := or(extraData, shl(40, _lastSequencerTimestamp))
      extraData := shl(40, extraData)
    }
    return extraData;
  }
  /**
   * Appends a batch to the chain.
   * @param _batch Elements within the batch.
   * @param _extraData Any extra data to append to the batch.
   */
  function _appendBatch(bytes32[] memory _batch, bytes memory _extraData)
    internal
  {
    address sequencer = resolve('OVM_Proposer');
    (
      uint40 totalElements,
      uint40 lastSequencerTimestamp
    ) = _getBatchExtraData();
    if (msg.sender == sequencer) {
      lastSequencerTimestamp = uint40(block.timestamp);
    } else {
      // We keep track of the last batch submitted by the sequencer so there's a window in
      // which only the sequencer can publish state roots. A window like this just reduces
      // the chance of "system breaking" state roots being published while we're still in
      // testing mode. This window should be removed or significantly reduced in the future.
      require(
        lastSequencerTimestamp + SEQUENCER_PUBLISH_WINDOW < block.timestamp,
        'Cannot publish state roots within the sequencer publication window.'
      );
    }
    // For efficiency reasons getMerkleRoot modifies the `_batch` argument in place
    // while calculating the root hash therefore any arguments passed to it must not
    // be used again afterwards
    Lib_OVMCodec.ChainBatchHeader memory batchHeader = Lib_OVMCodec
      .ChainBatchHeader({
        batchIndex: getTotalBatches(),
        batchRoot: Lib_MerkleTree.getMerkleRoot(_batch),
        batchSize: _batch.length,
        prevTotalElements: totalElements,
        extraData: _extraData
      });
    emit StateBatchAppended(
      batchHeader.batchIndex,
      batchHeader.batchRoot,
      batchHeader.batchSize,
      batchHeader.prevTotalElements,
      batchHeader.extraData
    );
    batches().push(
      Lib_OVMCodec.hashBatchHeader(batchHeader),
      _makeBatchExtraData(
        uint40(batchHeader.prevTotalElements + batchHeader.batchSize),
        lastSequencerTimestamp
      )
    );
  }
  /**
   * Removes a batch and all subsequent batches from the chain.
   * @param _batchHeader Header of the batch to remove.
   */
  function _deleteBatch(Lib_OVMCodec.ChainBatchHeader memory _batchHeader)
    internal
  {
    require(
      _batchHeader.batchIndex < batches().length(),
      'Invalid batch index.'
    );
    require(_isValidBatchHeader(_batchHeader), 'Invalid batch header.');
    batches().deleteElementsAfterInclusive(
      _batchHeader.batchIndex,
      _makeBatchExtraData(uint40(_batchHeader.prevTotalElements), 0)
    );
    emit StateBatchDeleted(_batchHeader.batchIndex, _batchHeader.batchRoot);
  }
  /**
   * Checks that a batch header matches the stored hash for the given index.
   * @param _batchHeader Batch header to validate.
   * @return Whether or not the header matches the stored one.
   */
  function _isValidBatchHeader(
    Lib_OVMCodec.ChainBatchHeader memory _batchHeader
  ) internal view returns (bool) {
    return
      Lib_OVMCodec.hashBatchHeader(_batchHeader) ==
      batches().get(_batchHeader.batchIndex);
  }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/* Library Imports */
import {Lib_RLPReader} from '../rlp/Lib_RLPReader.sol';
import {Lib_RLPWriter} from '../rlp/Lib_RLPWriter.sol';
import {Lib_BytesUtils} from '../utils/Lib_BytesUtils.sol';
import {Lib_Bytes32Utils} from '../utils/Lib_Bytes32Utils.sol';
/**
 * @title Lib_OVMCodec
 */
library Lib_OVMCodec {
  /*********
   * Enums *
   *********/
  enum QueueOrigin {
    SEQUENCER_QUEUE,
    L1TOL2_QUEUE
  }
  /***********
   * Structs *
   ***********/
  struct EVMAccount {
    uint256 nonce;
    uint256 balance;
    bytes32 storageRoot;
    bytes32 codeHash;
  }
  struct ChainBatchHeader {
    uint256 batchIndex;
    bytes32 batchRoot;
    uint256 batchSize;
    uint256 prevTotalElements;
    bytes extraData;
  }
  struct ChainInclusionProof {
    uint256 index;
    bytes32[] siblings;
  }
  struct Transaction {
    uint256 timestamp;
    uint256 blockNumber;
    QueueOrigin l1QueueOrigin;
    address l1TxOrigin;
    address entrypoint;
    uint256 gasLimit;
    bytes data;
  }
  struct TransactionChainElement {
    bool isSequenced;
    uint256 queueIndex; // QUEUED TX ONLY
    uint256 timestamp; // SEQUENCER TX ONLY
    uint256 blockNumber; // SEQUENCER TX ONLY
    bytes txData; // SEQUENCER TX ONLY
  }
  struct QueueElement {
    bytes32 transactionHash;
    uint40 timestamp;
    uint40 blockNumber;
  }
  /**********************
   * Internal Functions *
   **********************/
  /**
   * Encodes a standard OVM transaction.
   * @param _transaction OVM transaction to encode.
   * @return Encoded transaction bytes.
   */
  function encodeTransaction(Transaction memory _transaction)
    internal
    pure
    returns (bytes memory)
  {
    return
      abi.encodePacked(
        _transaction.timestamp,
        _transaction.blockNumber,
        _transaction.l1QueueOrigin,
        _transaction.l1TxOrigin,
        _transaction.entrypoint,
        _transaction.gasLimit,
        _transaction.data
      );
  }
  /**
   * Hashes a standard OVM transaction.
   * @param _transaction OVM transaction to encode.
   * @return Hashed transaction
   */
  function hashTransaction(Transaction memory _transaction)
    internal
    pure
    returns (bytes32)
  {
    return keccak256(encodeTransaction(_transaction));
  }
  /**
   * @notice Decodes an RLP-encoded account state into a useful struct.
   * @param _encoded RLP-encoded account state.
   * @return Account state struct.
   */
  function decodeEVMAccount(bytes memory _encoded)
    internal
    pure
    returns (EVMAccount memory)
  {
    Lib_RLPReader.RLPItem[] memory accountState = Lib_RLPReader.readList(
      _encoded
    );
    return
      EVMAccount({
        nonce: Lib_RLPReader.readUint256(accountState[0]),
        balance: Lib_RLPReader.readUint256(accountState[1]),
        storageRoot: Lib_RLPReader.readBytes32(accountState[2]),
        codeHash: Lib_RLPReader.readBytes32(accountState[3])
      });
  }
  /**
   * Calculates a hash for a given batch header.
   * @param _batchHeader Header to hash.
   * @return Hash of the header.
   */
  function hashBatchHeader(Lib_OVMCodec.ChainBatchHeader memory _batchHeader)
    internal
    pure
    returns (bytes32)
  {
    return
      keccak256(
        abi.encode(
          _batchHeader.batchRoot,
          _batchHeader.batchSize,
          _batchHeader.prevTotalElements,
          _batchHeader.extraData
        )
      );
  }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/* Library Imports */
import {Lib_AddressManager} from './Lib_AddressManager.sol';
/**
 * @title Lib_AddressResolver
 */
abstract contract Lib_AddressResolver {
  /*************
   * Variables *
   *************/
  Lib_AddressManager public libAddressManager;
  /***************
   * Constructor *
   ***************/
  /**
   * @param _libAddressManager Address of the Lib_AddressManager.
   */
  constructor(address _libAddressManager) {
    libAddressManager = Lib_AddressManager(_libAddressManager);
  }
  /********************
   * Public Functions *
   ********************/
  /**
   * Resolves the address associated with a given name.
   * @param _name Name to resolve an address for.
   * @return Address associated with the given name.
   */
  function resolve(string memory _name) public view returns (address) {
    return libAddressManager.getAddress(_name);
  }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/**
 * @title Lib_MerkleTree
 * @author River Keefer
 */
library Lib_MerkleTree {
  /**********************
   * Internal Functions *
   **********************/
  /**
   * Calculates a merkle root for a list of 32-byte leaf hashes.  WARNING: If the number
   * of leaves passed in is not a power of two, it pads out the tree with zero hashes.
   * If you do not know the original length of elements for the tree you are verifying, then
   * this may allow empty leaves past _elements.length to pass a verification check down the line.
   * Note that the _elements argument is modified, therefore it must not be used again afterwards
   * @param _elements Array of hashes from which to generate a merkle root.
   * @return Merkle root of the leaves, with zero hashes for non-powers-of-two (see above).
   */
  function getMerkleRoot(bytes32[] memory _elements)
    internal
    pure
    returns (bytes32)
  {
    require(
      _elements.length > 0,
      'Lib_MerkleTree: Must provide at least one leaf hash.'
    );
    if (_elements.length == 1) {
      return _elements[0];
    }
    uint256[16] memory defaults = [
      0x290decd9548b62a8d60345a988386fc84ba6bc95484008f6362f93160ef3e563,
      0x633dc4d7da7256660a892f8f1604a44b5432649cc8ec5cb3ced4c4e6ac94dd1d,
      0x890740a8eb06ce9be422cb8da5cdafc2b58c0a5e24036c578de2a433c828ff7d,
      0x3b8ec09e026fdc305365dfc94e189a81b38c7597b3d941c279f042e8206e0bd8,
      0xecd50eee38e386bd62be9bedb990706951b65fe053bd9d8a521af753d139e2da,
      0xdefff6d330bb5403f63b14f33b578274160de3a50df4efecf0e0db73bcdd3da5,
      0x617bdd11f7c0a11f49db22f629387a12da7596f9d1704d7465177c63d88ec7d7,
      0x292c23a9aa1d8bea7e2435e555a4a60e379a5a35f3f452bae60121073fb6eead,
      0xe1cea92ed99acdcb045a6726b2f87107e8a61620a232cf4d7d5b5766b3952e10,
      0x7ad66c0a68c72cb89e4fb4303841966e4062a76ab97451e3b9fb526a5ceb7f82,
      0xe026cc5a4aed3c22a58cbd3d2ac754c9352c5436f638042dca99034e83636516,
      0x3d04cffd8b46a874edf5cfae63077de85f849a660426697b06a829c70dd1409c,
      0xad676aa337a485e4728a0b240d92b3ef7b3c372d06d189322bfd5f61f1e7203e,
      0xa2fca4a49658f9fab7aa63289c91b7c7b6c832a6d0e69334ff5b0a3483d09dab,
      0x4ebfd9cd7bca2505f7bef59cc1c12ecc708fff26ae4af19abe852afe9e20c862,
      0x2def10d13dd169f550f578bda343d9717a138562e0093b380a1120789d53cf10
    ];
    // Reserve memory space for our hashes.
    bytes memory buf = new bytes(64);
    // We'll need to keep track of left and right siblings.
    bytes32 leftSibling;
    bytes32 rightSibling;
    // Number of non-empty nodes at the current depth.
    uint256 rowSize = _elements.length;
    // Current depth, counting from 0 at the leaves
    uint256 depth = 0;
    // Common sub-expressions
    uint256 halfRowSize; // rowSize / 2
    bool rowSizeIsOdd; // rowSize % 2 == 1
    while (rowSize > 1) {
      halfRowSize = rowSize / 2;
      rowSizeIsOdd = rowSize % 2 == 1;
      for (uint256 i = 0; i < halfRowSize; i++) {
        leftSibling = _elements[(2 * i)];
        rightSibling = _elements[(2 * i) + 1];
        assembly {
          mstore(add(buf, 32), leftSibling)
          mstore(add(buf, 64), rightSibling)
        }
        _elements[i] = keccak256(buf);
      }
      if (rowSizeIsOdd) {
        leftSibling = _elements[rowSize - 1];
        rightSibling = bytes32(defaults[depth]);
        assembly {
          mstore(add(buf, 32), leftSibling)
          mstore(add(buf, 64), rightSibling)
        }
        _elements[halfRowSize] = keccak256(buf);
      }
      rowSize = halfRowSize + (rowSizeIsOdd ? 1 : 0);
      depth++;
    }
    return _elements[0];
  }
  /**
   * Verifies a merkle branch for the given leaf hash.  Assumes the original length
   * of leaves generated is a known, correct input, and does not return true for indices
   * extending past that index (even if _siblings would be otherwise valid.)
   * @param _root The Merkle root to verify against.
   * @param _leaf The leaf hash to verify inclusion of.
   * @param _index The index in the tree of this leaf.
   * @param _siblings Array of sibline nodes in the inclusion proof, starting from depth 0
   * (bottom of the tree).
   * @param _totalLeaves The total number of leaves originally passed into.
   * @return Whether or not the merkle branch and leaf passes verification.
   */
  function verify(
    bytes32 _root,
    bytes32 _leaf,
    uint256 _index,
    bytes32[] memory _siblings,
    uint256 _totalLeaves
  ) internal pure returns (bool) {
    require(
      _totalLeaves > 0,
      'Lib_MerkleTree: Total leaves must be greater than zero.'
    );
    require(_index < _totalLeaves, 'Lib_MerkleTree: Index out of bounds.');
    require(
      _siblings.length == _ceilLog2(_totalLeaves),
      'Lib_MerkleTree: Total siblings does not correctly correspond to total leaves.'
    );
    bytes32 computedRoot = _leaf;
    for (uint256 i = 0; i < _siblings.length; i++) {
      if ((_index & 1) == 1) {
        computedRoot = keccak256(abi.encodePacked(_siblings[i], computedRoot));
      } else {
        computedRoot = keccak256(abi.encodePacked(computedRoot, _siblings[i]));
      }
      _index >>= 1;
    }
    return _root == computedRoot;
  }
  /*********************
   * Private Functions *
   *********************/
  /**
   * Calculates the integer ceiling of the log base 2 of an input.
   * @param _in Unsigned input to calculate the log.
   * @return ceil(log_base_2(_in))
   */
  function _ceilLog2(uint256 _in) private pure returns (uint256) {
    require(_in > 0, 'Lib_MerkleTree: Cannot compute ceil(log_2) of 0.');
    if (_in == 1) {
      return 0;
    }
    // Find the highest set bit (will be floor(log_2)).
    // Borrowed with <3 from https://github.com/ethereum/solidity-examples
    uint256 val = _in;
    uint256 highest = 0;
    for (uint256 i = 128; i >= 1; i >>= 1) {
      if (val & (((uint256(1) << i) - 1) << i) != 0) {
        highest += i;
        val >>= i;
      }
    }
    // Increment by one if this is not a perfect logarithm.
    if ((uint256(1) << highest) != _in) {
      highest += 1;
    }
    return highest;
  }
}
// SPDX-License-Identifier: MIT
pragma solidity >0.5.0 <0.9.0;
/* Library Imports */
import {Lib_OVMCodec} from '../../libraries/codec/Lib_OVMCodec.sol';
/**
 * @title IStateCommitmentChain
 */
interface IStateCommitmentChain {
  /**********
   * Events *
   **********/
  event StateBatchAppended(
    uint256 indexed _batchIndex,
    bytes32 _batchRoot,
    uint256 _batchSize,
    uint256 _prevTotalElements,
    bytes _extraData
  );
  event StateBatchDeleted(uint256 indexed _batchIndex, bytes32 _batchRoot);
  /********************
   * Public Functions *
   ********************/
  /**
   * Retrieves the total number of elements submitted.
   * @return _totalElements Total submitted elements.
   */
  function getTotalElements() external view returns (uint256 _totalElements);
  /**
   * Retrieves the total number of batches submitted.
   * @return _totalBatches Total submitted batches.
   */
  function getTotalBatches() external view returns (uint256 _totalBatches);
  /**
   * Retrieves the timestamp of the last batch submitted by the sequencer.
   * @return _lastSequencerTimestamp Last sequencer batch timestamp.
   */
  function getLastSequencerTimestamp()
    external
    view
    returns (uint256 _lastSequencerTimestamp);
  /**
   * Appends a batch of state roots to the chain.
   * @param _batch Batch of state roots.
   * @param _shouldStartAtElement Index of the element at which this batch should start.
   */
  function appendStateBatch(
    bytes32[] calldata _batch,
    uint256 _shouldStartAtElement
  ) external;
  /**
   * Deletes all state roots after (and including) a given batch.
   * @param _batchHeader Header of the batch to start deleting from.
   */
  function deleteStateBatch(Lib_OVMCodec.ChainBatchHeader memory _batchHeader)
    external;
  /**
   * Verifies a batch inclusion proof.
   * @param _element Hash of the element to verify a proof for.
   * @param _batchHeader Header of the batch in which the element was included.
   * @param _proof Merkle inclusion proof for the element.
   */
  function verifyStateCommitment(
    bytes32 _element,
    Lib_OVMCodec.ChainBatchHeader memory _batchHeader,
    Lib_OVMCodec.ChainInclusionProof memory _proof
  ) external view returns (bool _verified);
  /**
   * Checks whether a given batch is still inside its fraud proof window.
   * @param _batchHeader Header of the batch to check.
   * @return _inside Whether or not the batch is inside the fraud proof window.
   */
  function insideFraudProofWindow(
    Lib_OVMCodec.ChainBatchHeader memory _batchHeader
  ) external view returns (bool _inside);
}
// SPDX-License-Identifier: MIT
pragma solidity >0.5.0 <0.9.0;
/* Library Imports */
import {Lib_OVMCodec} from '../../libraries/codec/Lib_OVMCodec.sol';
/* Interface Imports */
import {IChainStorageContainer} from './IChainStorageContainer.sol';
/**
 * @title ICanonicalTransactionChain
 */
interface ICanonicalTransactionChain {
  /**********
   * Events *
   **********/
  event L2GasParamsUpdated(
    uint256 l2GasDiscountDivisor,
    uint256 enqueueGasCost,
    uint256 enqueueL2GasPrepaid
  );
  event TransactionEnqueued(
    address indexed _l1TxOrigin,
    address indexed _target,
    uint256 _gasLimit,
    bytes _data,
    uint256 indexed _queueIndex,
    uint256 _timestamp
  );
  event QueueBatchAppended(
    uint256 _startingQueueIndex,
    uint256 _numQueueElements,
    uint256 _totalElements
  );
  event SequencerBatchAppended(
    uint256 _startingQueueIndex,
    uint256 _numQueueElements,
    uint256 _totalElements
  );
  event TransactionBatchAppended(
    uint256 indexed _batchIndex,
    bytes32 _batchRoot,
    uint256 _batchSize,
    uint256 _prevTotalElements,
    bytes _extraData
  );
  /***********
   * Structs *
   ***********/
  struct BatchContext {
    uint256 numSequencedTransactions;
    uint256 numSubsequentQueueTransactions;
    uint256 timestamp;
    uint256 blockNumber;
  }
  /*******************************
   * Authorized Setter Functions *
   *******************************/
  /**
   * Allows the Burn Admin to update the parameters which determine the amount of gas to burn.
   * The value of enqueueL2GasPrepaid is immediately updated as well.
   */
  function setGasParams(uint256 _l2GasDiscountDivisor, uint256 _enqueueGasCost)
    external;
  /********************
   * Public Functions *
   ********************/
  /**
   * Accesses the batch storage container.
   * @return Reference to the batch storage container.
   */
  function batches() external view returns (IChainStorageContainer);
  /**
   * Accesses the queue storage container.
   * @return Reference to the queue storage container.
   */
  function queue() external view returns (IChainStorageContainer);
  /**
   * Retrieves the total number of elements submitted.
   * @return _totalElements Total submitted elements.
   */
  function getTotalElements() external view returns (uint256 _totalElements);
  /**
   * Retrieves the total number of batches submitted.
   * @return _totalBatches Total submitted batches.
   */
  function getTotalBatches() external view returns (uint256 _totalBatches);
  /**
   * Returns the index of the next element to be enqueued.
   * @return Index for the next queue element.
   */
  function getNextQueueIndex() external view returns (uint40);
  /**
   * Gets the queue element at a particular index.
   * @param _index Index of the queue element to access.
   * @return _element Queue element at the given index.
   */
  function getQueueElement(uint256 _index)
    external
    view
    returns (Lib_OVMCodec.QueueElement memory _element);
  /**
   * Returns the timestamp of the last transaction.
   * @return Timestamp for the last transaction.
   */
  function getLastTimestamp() external view returns (uint40);
  /**
   * Returns the blocknumber of the last transaction.
   * @return Blocknumber for the last transaction.
   */
  function getLastBlockNumber() external view returns (uint40);
  /**
   * Get the number of queue elements which have not yet been included.
   * @return Number of pending queue elements.
   */
  function getNumPendingQueueElements() external view returns (uint40);
  /**
   * Retrieves the length of the queue, including
   * both pending and canonical transactions.
   * @return Length of the queue.
   */
  function getQueueLength() external view returns (uint40);
  /**
   * Adds a transaction to the queue.
   * @param _target Target contract to send the transaction to.
   * @param _gasLimit Gas limit for the given transaction.
   * @param _data Transaction data.
   */
  function enqueue(
    address _target,
    uint256 _gasLimit,
    bytes memory _data
  ) external;
  /**
   * Allows the sequencer to append a batch of transactions.
   * @dev This function uses a custom encoding scheme for efficiency reasons.
   * .param _shouldStartAtElement Specific batch we expect to start appending to.
   * .param _totalElementsToAppend Total number of batch elements we expect to append.
   * .param _contexts Array of batch contexts.
   * .param _transactionDataFields Array of raw transaction data.
   */
  function appendSequencerBatch(
    // uint40 _shouldStartAtElement,
    // uint24 _totalElementsToAppend,
    // BatchContext[] _contexts,
    // bytes[] _transactionDataFields
  ) external;
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/**
 * @title IBondManager
 */
interface IBondManager {
  /********************
   * Public Functions *
   ********************/
  function isCollateralized(address _who) external view returns (bool);
}
// SPDX-License-Identifier: MIT
pragma solidity >0.5.0 <0.9.0;
/**
 * @title IChainStorageContainer
 */
interface IChainStorageContainer {
  /********************
   * Public Functions *
   ********************/
  /**
   * Sets the container's global metadata field. We're using `bytes27` here because we use five
   * bytes to maintain the length of the underlying data structure, meaning we have an extra
   * 27 bytes to store arbitrary data.
   * @param _globalMetadata New global metadata to set.
   */
  function setGlobalMetadata(bytes27 _globalMetadata) external;
  /**
   * Retrieves the container's global metadata field.
   * @return Container global metadata field.
   */
  function getGlobalMetadata() external view returns (bytes27);
  /**
   * Retrieves the number of objects stored in the container.
   * @return Number of objects in the container.
   */
  function length() external view returns (uint256);
  /**
   * Pushes an object into the container.
   * @param _object A 32 byte value to insert into the container.
   */
  function push(bytes32 _object) external;
  /**
   * Pushes an object into the container. Function allows setting the global metadata since
   * we'll need to touch the "length" storage slot anyway, which also contains the global
   * metadata (it's an optimization).
   * @param _object A 32 byte value to insert into the container.
   * @param _globalMetadata New global metadata for the container.
   */
  function push(bytes32 _object, bytes27 _globalMetadata) external;
  /**
   * Retrieves an object from the container.
   * @param _index Index of the particular object to access.
   * @return 32 byte object value.
   */
  function get(uint256 _index) external view returns (bytes32);
  /**
   * Removes all objects after and including a given index.
   * @param _index Object index to delete from.
   */
  function deleteElementsAfterInclusive(uint256 _index) external;
  /**
   * Removes all objects after and including a given index. Also allows setting the global
   * metadata field.
   * @param _index Object index to delete from.
   * @param _globalMetadata New global metadata for the container.
   */
  function deleteElementsAfterInclusive(uint256 _index, bytes27 _globalMetadata)
    external;
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/**
 * @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
    )
  {
    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) {
    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;
    unchecked {
      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: MIT
pragma solidity ^0.8.9;
/**
 * @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 The RLP encoded string in bytes.
   */
  function writeBytes(bytes memory _in) internal pure returns (bytes memory) {
    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 The RLP encoded list of items in bytes.
   */
  function writeList(bytes[] memory _in) internal pure returns (bytes memory) {
    bytes memory list = _flatten(_in);
    return abi.encodePacked(_writeLength(list.length, 192), list);
  }
  /**
   * RLP encodes a string.
   * @param _in The string to encode.
   * @return The RLP encoded string in bytes.
   */
  function writeString(string memory _in) internal pure returns (bytes memory) {
    return writeBytes(bytes(_in));
  }
  /**
   * RLP encodes an address.
   * @param _in The address to encode.
   * @return The RLP encoded address in bytes.
   */
  function writeAddress(address _in) internal pure returns (bytes memory) {
    return writeBytes(abi.encodePacked(_in));
  }
  /**
   * RLP encodes a uint.
   * @param _in The uint256 to encode.
   * @return The RLP encoded uint256 in bytes.
   */
  function writeUint(uint256 _in) internal pure returns (bytes memory) {
    return writeBytes(_toBinary(_in));
  }
  /**
   * RLP encodes a bool.
   * @param _in The bool to encode.
   * @return The RLP encoded bool in bytes.
   */
  function writeBool(bool _in) internal pure returns (bytes memory) {
    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 RLP encoded bytes.
   */
  function _writeLength(uint256 _len, uint256 _offset)
    private
    pure
    returns (bytes memory)
  {
    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 RLP encoded bytes.
   */
  function _toBinary(uint256 _x) private pure returns (bytes memory) {
    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;
    unchecked {
      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 The flattened byte string.
   */
  function _flatten(bytes[] memory _list) private pure returns (bytes memory) {
    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;
  }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/**
 * @title Lib_BytesUtils
 */
library Lib_BytesUtils {
  /**********************
   * Internal Functions *
   **********************/
  function slice(
    bytes memory _bytes,
    uint256 _start,
    uint256 _length
  ) internal pure returns (bytes memory) {
    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)
  {
    if (_start >= _bytes.length) {
      return bytes('');
    }
    return slice(_bytes, _start, _bytes.length - _start);
  }
  function toBytes32(bytes memory _bytes) internal pure returns (bytes32) {
    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 toNibbles(bytes memory _bytes) internal pure returns (bytes memory) {
    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)
  {
    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.8.9;
/**
 * @title Lib_Byte32Utils
 */
library Lib_Bytes32Utils {
  /**********************
   * Internal Functions *
   **********************/
  /**
   * Converts a bytes32 value to a boolean. Anything non-zero will be converted to "true."
   * @param _in Input bytes32 value.
   * @return Bytes32 as a boolean.
   */
  function toBool(bytes32 _in) internal pure returns (bool) {
    return _in != 0;
  }
  /**
   * Converts a boolean to a bytes32 value.
   * @param _in Input boolean value.
   * @return Boolean as a bytes32.
   */
  function fromBool(bool _in) internal pure returns (bytes32) {
    return bytes32(uint256(_in ? 1 : 0));
  }
  /**
   * Converts a bytes32 value to an address. Takes the *last* 20 bytes.
   * @param _in Input bytes32 value.
   * @return Bytes32 as an address.
   */
  function toAddress(bytes32 _in) internal pure returns (address) {
    return address(uint160(uint256(_in)));
  }
  /**
   * Converts an address to a bytes32.
   * @param _in Input address value.
   * @return Address as a bytes32.
   */
  function fromAddress(address _in) internal pure returns (bytes32) {
    return bytes32(uint256(uint160(_in)));
  }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/* External Imports */
import {Ownable} from '@openzeppelin/contracts/access/Ownable.sol';
/**
 * @title Lib_AddressManager
 */
contract Lib_AddressManager is Ownable {
  /**********
   * Events *
   **********/
  event AddressSet(
    string indexed _name,
    address _newAddress,
    address _oldAddress
  );
  /*************
   * Variables *
   *************/
  mapping(bytes32 => address) private addresses;
  /********************
   * Public Functions *
   ********************/
  /**
   * Changes the address associated with a particular name.
   * @param _name String name to associate an address with.
   * @param _address Address to associate with the name.
   */
  function setAddress(string memory _name, address _address)
    external
    onlyOwner
  {
    bytes32 nameHash = _getNameHash(_name);
    address oldAddress = addresses[nameHash];
    addresses[nameHash] = _address;
    emit AddressSet(_name, _address, oldAddress);
  }
  /**
   * Retrieves the address associated with a given name.
   * @param _name Name to retrieve an address for.
   * @return Address associated with the given name.
   */
  function getAddress(string memory _name) external view returns (address) {
    return addresses[_getNameHash(_name)];
  }
  /**********************
   * Internal Functions *
   **********************/
  /**
   * Computes the hash of a name.
   * @param _name Name to compute a hash for.
   * @return Hash of the given name.
   */
  function _getNameHash(string memory _name) internal pure returns (bytes32) {
    return keccak256(abi.encodePacked(_name));
  }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
import "../utils/Context.sol";
/**
 * @dev Contract module which provides a basic access control mechanism, where
 * there is an account (an owner) that can be granted exclusive access to
 * specific functions.
 *
 * By default, the owner account will be the one that deploys the contract. This
 * can later be changed with {transferOwnership}.
 *
 * This module is used through inheritance. It will make available the modifier
 * `onlyOwner`, which can be applied to your functions to restrict their use to
 * the owner.
 */
abstract contract Ownable is Context {
    address private _owner;
    event OwnershipTransferred(address indexed previousOwner, address indexed newOwner);
    /**
     * @dev Initializes the contract setting the deployer as the initial owner.
     */
    constructor() {
        _setOwner(_msgSender());
    }
    /**
     * @dev Returns the address of the current owner.
     */
    function owner() public view virtual returns (address) {
        return _owner;
    }
    /**
     * @dev Throws if called by any account other than the owner.
     */
    modifier onlyOwner() {
        require(owner() == _msgSender(), "Ownable: caller is not the owner");
        _;
    }
    /**
     * @dev Leaves the contract without owner. It will not be possible to call
     * `onlyOwner` functions anymore. Can only be called by the current owner.
     *
     * NOTE: Renouncing ownership will leave the contract without an owner,
     * thereby removing any functionality that is only available to the owner.
     */
    function renounceOwnership() public virtual onlyOwner {
        _setOwner(address(0));
    }
    /**
     * @dev Transfers ownership of the contract to a new account (`newOwner`).
     * Can only be called by the current owner.
     */
    function transferOwnership(address newOwner) public virtual onlyOwner {
        require(newOwner != address(0), "Ownable: new owner is the zero address");
        _setOwner(newOwner);
    }
    function _setOwner(address newOwner) private {
        address oldOwner = _owner;
        _owner = newOwner;
        emit OwnershipTransferred(oldOwner, newOwner);
    }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
/**
 * @dev Provides information about the current execution context, including the
 * sender of the transaction and its data. While these are generally available
 * via msg.sender and msg.data, they should not be accessed in such a direct
 * manner, since when dealing with meta-transactions the account sending and
 * paying for execution may not be the actual sender (as far as an application
 * is concerned).
 *
 * This contract is only required for intermediate, library-like contracts.
 */
abstract contract Context {
    function _msgSender() internal view virtual returns (address) {
        return msg.sender;
    }
    function _msgData() internal view virtual returns (bytes calldata) {
        return msg.data;
    }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/* Library Imports */
import {Lib_Buffer} from '../../libraries/utils/Lib_Buffer.sol';
import {Lib_AddressResolver} from '../../libraries/resolver/Lib_AddressResolver.sol';
/* Interface Imports */
import {IChainStorageContainer} from './IChainStorageContainer.sol';
/**
 * @title ChainStorageContainer
 * @dev The Chain Storage Container provides its owner contract with read, write and delete
 * functionality. This provides gas efficiency gains by enabling it to overwrite storage slots which
 * can no longer be used in a fraud proof due to the fraud window having passed, and the associated
 * chain state or transactions being finalized.
 * Three distinct Chain Storage Containers will be deployed on Layer 1:
 * 1. Stores transaction batches for the Canonical Transaction Chain
 * 2. Stores queued transactions for the Canonical Transaction Chain
 * 3. Stores chain state batches for the State Commitment Chain
 *
 * Runtime target: EVM
 */
contract ChainStorageContainer is IChainStorageContainer, Lib_AddressResolver {
  /*************
   * Libraries *
   *************/
  using Lib_Buffer for Lib_Buffer.Buffer;
  /*************
   * Variables *
   *************/
  string public owner;
  Lib_Buffer.Buffer internal buffer;
  /***************
   * Constructor *
   ***************/
  /**
   * @param _libAddressManager Address of the Address Manager.
   * @param _owner Name of the contract that owns this container (will be resolved later).
   */
  constructor(address _libAddressManager, string memory _owner)
    Lib_AddressResolver(_libAddressManager)
  {
    owner = _owner;
  }
  /**********************
   * Function Modifiers *
   **********************/
  modifier onlyOwner() {
    require(
      msg.sender == resolve(owner),
      'ChainStorageContainer: Function can only be called by the owner.'
    );
    _;
  }
  /********************
   * Public Functions *
   ********************/
  /**
   * @inheritdoc IChainStorageContainer
   */
  function setGlobalMetadata(bytes27 _globalMetadata) public onlyOwner {
    return buffer.setExtraData(_globalMetadata);
  }
  /**
   * @inheritdoc IChainStorageContainer
   */
  function getGlobalMetadata() public view returns (bytes27) {
    return buffer.getExtraData();
  }
  /**
   * @inheritdoc IChainStorageContainer
   */
  function length() public view returns (uint256) {
    return uint256(buffer.getLength());
  }
  /**
   * @inheritdoc IChainStorageContainer
   */
  function push(bytes32 _object) public onlyOwner {
    buffer.push(_object);
  }
  /**
   * @inheritdoc IChainStorageContainer
   */
  function push(bytes32 _object, bytes27 _globalMetadata) public onlyOwner {
    buffer.push(_object, _globalMetadata);
  }
  /**
   * @inheritdoc IChainStorageContainer
   */
  function get(uint256 _index) public view returns (bytes32) {
    return buffer.get(uint40(_index));
  }
  /**
   * @inheritdoc IChainStorageContainer
   */
  function deleteElementsAfterInclusive(uint256 _index) public onlyOwner {
    buffer.deleteElementsAfterInclusive(uint40(_index));
  }
  /**
   * @inheritdoc IChainStorageContainer
   */
  function deleteElementsAfterInclusive(uint256 _index, bytes27 _globalMetadata)
    public
    onlyOwner
  {
    buffer.deleteElementsAfterInclusive(uint40(_index), _globalMetadata);
  }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/**
 * @title Lib_Buffer
 * @dev This library implements a bytes32 storage array with some additional gas-optimized
 * functionality. In particular, it encodes its length as a uint40, and tightly packs this with an
 * overwritable "extra data" field so we can store more information with a single SSTORE.
 */
library Lib_Buffer {
  /*************
   * Libraries *
   *************/
  using Lib_Buffer for Buffer;
  /***********
   * Structs *
   ***********/
  struct Buffer {
    bytes32 context;
    mapping(uint256 => bytes32) buf;
  }
  struct BufferContext {
    // Stores the length of the array. Uint40 is way more elements than we'll ever reasonably
    // need in an array and we get an extra 27 bytes of extra data to play with.
    uint40 length;
    // Arbitrary extra data that can be modified whenever the length is updated. Useful for
    // squeezing out some gas optimizations.
    bytes27 extraData;
  }
  /**********************
   * Internal Functions *
   **********************/
  /**
   * Pushes a single element to the buffer.
   * @param _self Buffer to access.
   * @param _value Value to push to the buffer.
   * @param _extraData Global extra data.
   */
  function push(
    Buffer storage _self,
    bytes32 _value,
    bytes27 _extraData
  ) internal {
    BufferContext memory ctx = _self.getContext();
    _self.buf[ctx.length] = _value;
    // Bump the global index and insert our extra data, then save the context.
    ctx.length++;
    ctx.extraData = _extraData;
    _self.setContext(ctx);
  }
  /**
   * Pushes a single element to the buffer.
   * @param _self Buffer to access.
   * @param _value Value to push to the buffer.
   */
  function push(Buffer storage _self, bytes32 _value) internal {
    BufferContext memory ctx = _self.getContext();
    _self.push(_value, ctx.extraData);
  }
  /**
   * Retrieves an element from the buffer.
   * @param _self Buffer to access.
   * @param _index Element index to retrieve.
   * @return Value of the element at the given index.
   */
  function get(Buffer storage _self, uint256 _index)
    internal
    view
    returns (bytes32)
  {
    BufferContext memory ctx = _self.getContext();
    require(_index < ctx.length, 'Index out of bounds.');
    return _self.buf[_index];
  }
  /**
   * Deletes all elements after (and including) a given index.
   * @param _self Buffer to access.
   * @param _index Index of the element to delete from (inclusive).
   * @param _extraData Optional global extra data.
   */
  function deleteElementsAfterInclusive(
    Buffer storage _self,
    uint40 _index,
    bytes27 _extraData
  ) internal {
    BufferContext memory ctx = _self.getContext();
    require(_index < ctx.length, 'Index out of bounds.');
    // Set our length and extra data, save the context.
    ctx.length = _index;
    ctx.extraData = _extraData;
    _self.setContext(ctx);
  }
  /**
   * Deletes all elements after (and including) a given index.
   * @param _self Buffer to access.
   * @param _index Index of the element to delete from (inclusive).
   */
  function deleteElementsAfterInclusive(Buffer storage _self, uint40 _index)
    internal
  {
    BufferContext memory ctx = _self.getContext();
    _self.deleteElementsAfterInclusive(_index, ctx.extraData);
  }
  /**
   * Retrieves the current global index.
   * @param _self Buffer to access.
   * @return Current global index.
   */
  function getLength(Buffer storage _self) internal view returns (uint40) {
    BufferContext memory ctx = _self.getContext();
    return ctx.length;
  }
  /**
   * Changes current global extra data.
   * @param _self Buffer to access.
   * @param _extraData New global extra data.
   */
  function setExtraData(Buffer storage _self, bytes27 _extraData) internal {
    BufferContext memory ctx = _self.getContext();
    ctx.extraData = _extraData;
    _self.setContext(ctx);
  }
  /**
   * Retrieves the current global extra data.
   * @param _self Buffer to access.
   * @return Current global extra data.
   */
  function getExtraData(Buffer storage _self) internal view returns (bytes27) {
    BufferContext memory ctx = _self.getContext();
    return ctx.extraData;
  }
  /**
   * Sets the current buffer context.
   * @param _self Buffer to access.
   * @param _ctx Current buffer context.
   */
  function setContext(Buffer storage _self, BufferContext memory _ctx)
    internal
  {
    bytes32 context;
    uint40 length = _ctx.length;
    bytes27 extraData = _ctx.extraData;
    assembly {
      context := length
      context := or(context, extraData)
    }
    if (_self.context != context) {
      _self.context = context;
    }
  }
  /**
   * Retrieves the current buffer context.
   * @param _self Buffer to access.
   * @return Current buffer context.
   */
  function getContext(Buffer storage _self)
    internal
    view
    returns (BufferContext memory)
  {
    bytes32 context = _self.context;
    uint40 length;
    bytes27 extraData;
    assembly {
      // solhint-disable-next-line max-line-length
      length := and(
        context,
        0x000000000000000000000000000000000000000000000000000000FFFFFFFFFF
      )
      // solhint-disable-next-line max-line-length
      extraData := and(
        context,
        0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF0000000000
      )
    }
    return BufferContext({length: length, extraData: extraData});
  }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/* Library Imports */
import {Lib_AddressManager} from './Lib_AddressManager.sol';
/**
 * @title Lib_AddressResolver
 */
abstract contract Lib_AddressResolver {
  /*************
   * Variables *
   *************/
  Lib_AddressManager public libAddressManager;
  /***************
   * Constructor *
   ***************/
  /**
   * @param _libAddressManager Address of the Lib_AddressManager.
   */
  constructor(address _libAddressManager) {
    libAddressManager = Lib_AddressManager(_libAddressManager);
  }
  /********************
   * Public Functions *
   ********************/
  /**
   * Resolves the address associated with a given name.
   * @param _name Name to resolve an address for.
   * @return Address associated with the given name.
   */
  function resolve(string memory _name) public view returns (address) {
    return libAddressManager.getAddress(_name);
  }
}
// SPDX-License-Identifier: MIT
pragma solidity >0.5.0 <0.9.0;
/**
 * @title IChainStorageContainer
 */
interface IChainStorageContainer {
  /********************
   * Public Functions *
   ********************/
  /**
   * Sets the container's global metadata field. We're using `bytes27` here because we use five
   * bytes to maintain the length of the underlying data structure, meaning we have an extra
   * 27 bytes to store arbitrary data.
   * @param _globalMetadata New global metadata to set.
   */
  function setGlobalMetadata(bytes27 _globalMetadata) external;
  /**
   * Retrieves the container's global metadata field.
   * @return Container global metadata field.
   */
  function getGlobalMetadata() external view returns (bytes27);
  /**
   * Retrieves the number of objects stored in the container.
   * @return Number of objects in the container.
   */
  function length() external view returns (uint256);
  /**
   * Pushes an object into the container.
   * @param _object A 32 byte value to insert into the container.
   */
  function push(bytes32 _object) external;
  /**
   * Pushes an object into the container. Function allows setting the global metadata since
   * we'll need to touch the "length" storage slot anyway, which also contains the global
   * metadata (it's an optimization).
   * @param _object A 32 byte value to insert into the container.
   * @param _globalMetadata New global metadata for the container.
   */
  function push(bytes32 _object, bytes27 _globalMetadata) external;
  /**
   * Retrieves an object from the container.
   * @param _index Index of the particular object to access.
   * @return 32 byte object value.
   */
  function get(uint256 _index) external view returns (bytes32);
  /**
   * Removes all objects after and including a given index.
   * @param _index Object index to delete from.
   */
  function deleteElementsAfterInclusive(uint256 _index) external;
  /**
   * Removes all objects after and including a given index. Also allows setting the global
   * metadata field.
   * @param _index Object index to delete from.
   * @param _globalMetadata New global metadata for the container.
   */
  function deleteElementsAfterInclusive(uint256 _index, bytes27 _globalMetadata)
    external;
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/* External Imports */
import {Ownable} from '@openzeppelin/contracts/access/Ownable.sol';
/**
 * @title Lib_AddressManager
 */
contract Lib_AddressManager is Ownable {
  /**********
   * Events *
   **********/
  event AddressSet(
    string indexed _name,
    address _newAddress,
    address _oldAddress
  );
  /*************
   * Variables *
   *************/
  mapping(bytes32 => address) private addresses;
  /********************
   * Public Functions *
   ********************/
  /**
   * Changes the address associated with a particular name.
   * @param _name String name to associate an address with.
   * @param _address Address to associate with the name.
   */
  function setAddress(string memory _name, address _address)
    external
    onlyOwner
  {
    bytes32 nameHash = _getNameHash(_name);
    address oldAddress = addresses[nameHash];
    addresses[nameHash] = _address;
    emit AddressSet(_name, _address, oldAddress);
  }
  /**
   * Retrieves the address associated with a given name.
   * @param _name Name to retrieve an address for.
   * @return Address associated with the given name.
   */
  function getAddress(string memory _name) external view returns (address) {
    return addresses[_getNameHash(_name)];
  }
  /**********************
   * Internal Functions *
   **********************/
  /**
   * Computes the hash of a name.
   * @param _name Name to compute a hash for.
   * @return Hash of the given name.
   */
  function _getNameHash(string memory _name) internal pure returns (bytes32) {
    return keccak256(abi.encodePacked(_name));
  }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
import "../utils/Context.sol";
/**
 * @dev Contract module which provides a basic access control mechanism, where
 * there is an account (an owner) that can be granted exclusive access to
 * specific functions.
 *
 * By default, the owner account will be the one that deploys the contract. This
 * can later be changed with {transferOwnership}.
 *
 * This module is used through inheritance. It will make available the modifier
 * `onlyOwner`, which can be applied to your functions to restrict their use to
 * the owner.
 */
abstract contract Ownable is Context {
    address private _owner;
    event OwnershipTransferred(address indexed previousOwner, address indexed newOwner);
    /**
     * @dev Initializes the contract setting the deployer as the initial owner.
     */
    constructor() {
        _setOwner(_msgSender());
    }
    /**
     * @dev Returns the address of the current owner.
     */
    function owner() public view virtual returns (address) {
        return _owner;
    }
    /**
     * @dev Throws if called by any account other than the owner.
     */
    modifier onlyOwner() {
        require(owner() == _msgSender(), "Ownable: caller is not the owner");
        _;
    }
    /**
     * @dev Leaves the contract without owner. It will not be possible to call
     * `onlyOwner` functions anymore. Can only be called by the current owner.
     *
     * NOTE: Renouncing ownership will leave the contract without an owner,
     * thereby removing any functionality that is only available to the owner.
     */
    function renounceOwnership() public virtual onlyOwner {
        _setOwner(address(0));
    }
    /**
     * @dev Transfers ownership of the contract to a new account (`newOwner`).
     * Can only be called by the current owner.
     */
    function transferOwnership(address newOwner) public virtual onlyOwner {
        require(newOwner != address(0), "Ownable: new owner is the zero address");
        _setOwner(newOwner);
    }
    function _setOwner(address newOwner) private {
        address oldOwner = _owner;
        _owner = newOwner;
        emit OwnershipTransferred(oldOwner, newOwner);
    }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
/**
 * @dev Provides information about the current execution context, including the
 * sender of the transaction and its data. While these are generally available
 * via msg.sender and msg.data, they should not be accessed in such a direct
 * manner, since when dealing with meta-transactions the account sending and
 * paying for execution may not be the actual sender (as far as an application
 * is concerned).
 *
 * This contract is only required for intermediate, library-like contracts.
 */
abstract contract Context {
    function _msgSender() internal view virtual returns (address) {
        return msg.sender;
    }
    function _msgData() internal view virtual returns (bytes calldata) {
        return msg.data;
    }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/* Interface Imports */
import {IL1StandardBridge} from './IL1StandardBridge.sol';
import {IL1ERC20Bridge} from './IL1ERC20Bridge.sol';
import {IL2ERC20Bridge} from '../../L2/messaging/IL2ERC20Bridge.sol';
import {IERC20} from '@openzeppelin/contracts/token/ERC20/IERC20.sol';
/* Library Imports */
import {CrossDomainEnabled} from '../../libraries/bridge/CrossDomainEnabled.sol';
import {Lib_PredeployAddresses} from '../../libraries/constants/Lib_PredeployAddresses.sol';
import {Address} from '@openzeppelin/contracts/utils/Address.sol';
import {SafeERC20} from '@openzeppelin/contracts/token/ERC20/utils/SafeERC20.sol';
/**
 * @title L1StandardBridge
 * @dev The L1 ETH and ERC20 Bridge is a contract which stores deposited L1 funds and standard
 * tokens that are in use on L2. It synchronizes a corresponding L2 Bridge, informing it of deposits
 * and listening to it for newly finalized withdrawals.
 *
 * Runtime target: EVM
 */
contract L1StandardBridge is IL1StandardBridge, CrossDomainEnabled {
  using SafeERC20 for IERC20;
  /********************************
   * External Contract References *
   ********************************/
  address public l2TokenBridge;
  // Maps L1 token to L2 token to balance of the L1 token deposited
  mapping(address => mapping(address => uint256)) public deposits;
  bytes32 public priorDepositInfoHash;
  bytes32 public currentDepositInfoHash;
  uint256 public lastHashUpdateBlock;
  /***************
   * Constructor *
   ***************/
  // This contract lives behind a proxy, so the constructor parameters will go unused.
  constructor() CrossDomainEnabled(address(0)) {}
  /******************
   * Initialization *
   ******************/
  /**
   * @param _l1messenger L1 Messenger address being used for cross-chain communications.
   * @param _l2TokenBridge L2 standard bridge address.
   */
  function initialize(address _l1messenger, address _l2TokenBridge) public {
    require(messenger == address(0), 'Contract has already been initialized.');
    messenger = _l1messenger;
    l2TokenBridge = _l2TokenBridge;
  }
  /**************
   * Depositing *
   **************/
  /** @dev Modifier requiring sender to be EOA.  This check could be bypassed by a malicious
   *  contract via initcode, but it takes care of the user error we want to avoid.
   */
  modifier onlyEOA() {
    // Used to stop deposits from contracts (avoid accidentally lost tokens)
    require(!Address.isContract(msg.sender), 'Account not EOA');
    _;
  }
  /**
   * @dev This function can be called with no data
   * to deposit an amount of ETH to the caller's balance on L2.
   * Since the receive function doesn't take data, a conservative
   * default amount is forwarded to L2.
   */
  receive() external payable onlyEOA {
    _initiateETHDeposit(msg.sender, msg.sender, 1_300_000, bytes(''));
  }
  /**
   * @inheritdoc IL1StandardBridge
   */
  function depositETH(uint32 _l2Gas, bytes calldata _data)
    external
    payable
    onlyEOA
  {
    _initiateETHDeposit(msg.sender, msg.sender, _l2Gas, _data);
  }
  /**
   * @inheritdoc IL1StandardBridge
   */
  function depositETHTo(
    address _to,
    uint32 _l2Gas,
    bytes calldata _data
  ) external payable {
    _initiateETHDeposit(msg.sender, _to, _l2Gas, _data);
  }
  /**
   * @dev Performs the logic for deposits by storing the ETH and informing the L2 ETH Gateway of
   * the deposit.
   * @param _from Account to pull the deposit from on L1.
   * @param _to Account to give the deposit to on L2.
   * @param _l2Gas Gas limit required to complete the deposit on L2.
   * @param _data Optional data to forward to L2. This data is provided
   *        solely as a convenience for external contracts. Aside from enforcing a maximum
   *        length, these contracts provide no guarantees about its content.
   */
  function _initiateETHDeposit(
    address _from,
    address _to,
    uint32 _l2Gas,
    bytes memory _data
  ) internal {
    // Construct calldata for finalizeDeposit call
    bytes memory message = abi.encodeWithSelector(
      IL2ERC20Bridge.finalizeDeposit.selector,
      address(0),
      Lib_PredeployAddresses.OVM_ETH,
      _from,
      _to,
      msg.value,
      _data
    );
    // Send calldata into L2
    sendCrossDomainMessage(l2TokenBridge, _l2Gas, message);
    // compute and update deposit hash
    _updateDepositHash(
      address(0),
      Lib_PredeployAddresses.OVM_ETH,
      _from,
      _to,
      msg.value
    );
    emit ETHDepositInitiated(_from, _to, msg.value, _data);
  }
  /**
   * @inheritdoc IL1ERC20Bridge
   */
  function depositERC20(
    address _l1Token,
    address _l2Token,
    uint256 _amount,
    uint32 _l2Gas,
    bytes calldata _data
  ) external virtual onlyEOA {
    _initiateERC20Deposit(
      _l1Token,
      _l2Token,
      msg.sender,
      msg.sender,
      _amount,
      _l2Gas,
      _data
    );
  }
  /**
   * @inheritdoc IL1ERC20Bridge
   */
  function depositERC20To(
    address _l1Token,
    address _l2Token,
    address _to,
    uint256 _amount,
    uint32 _l2Gas,
    bytes calldata _data
  ) external virtual {
    _initiateERC20Deposit(
      _l1Token,
      _l2Token,
      msg.sender,
      _to,
      _amount,
      _l2Gas,
      _data
    );
  }
  /**
   * @dev Performs the logic for deposits by informing the L2 Deposited Token
   * contract of the deposit and calling a handler to lock the L1 funds. (e.g. transferFrom)
   *
   * @param _l1Token Address of the L1 ERC20 we are depositing
   * @param _l2Token Address of the L1 respective L2 ERC20
   * @param _from Account to pull the deposit from on L1
   * @param _to Account to give the deposit to on L2
   * @param _amount Amount of the ERC20 to deposit.
   * @param _l2Gas Gas limit required to complete the deposit on L2.
   * @param _data Optional data to forward to L2. This data is provided
   *        solely as a convenience for external contracts. Aside from enforcing a maximum
   *        length, these contracts provide no guarantees about its content.
   */
  function _initiateERC20Deposit(
    address _l1Token,
    address _l2Token,
    address _from,
    address _to,
    uint256 _amount,
    uint32 _l2Gas,
    bytes calldata _data
  ) internal {
    // When a deposit is initiated on L1, the L1 Bridge transfers the funds to itself for future
    // withdrawals. safeTransferFrom also checks if the contract has code, so this will fail if
    // _from is an EOA or address(0).
    IERC20(_l1Token).safeTransferFrom(_from, address(this), _amount);
    // Construct calldata for _l2Token.finalizeDeposit(_to, _amount)
    bytes memory message = abi.encodeWithSelector(
      IL2ERC20Bridge.finalizeDeposit.selector,
      _l1Token,
      _l2Token,
      _from,
      _to,
      _amount,
      _data
    );
    // Send calldata into L2
    sendCrossDomainMessage(l2TokenBridge, _l2Gas, message);
    deposits[_l1Token][_l2Token] = deposits[_l1Token][_l2Token] + _amount;
    _updateDepositHash(_l1Token, _l2Token, _from, _to, _amount);
    emit ERC20DepositInitiated(_l1Token, _l2Token, _from, _to, _amount, _data);
  }
  function _updateDepositHash(
    address _l1Token,
    address _l2Token,
    address _from,
    address _to,
    uint256 _amount
  ) internal {
    // if block number is different only then update prior
    if (block.number > lastHashUpdateBlock) {
      priorDepositInfoHash = currentDepositInfoHash;
    }
    currentDepositInfoHash = keccak256(
      abi.encode(
        currentDepositInfoHash,
        _l1Token,
        _l2Token,
        _from,
        _to,
        _amount
      )
    );
    lastHashUpdateBlock = block.number;
  }
  /*************************
   * Cross-chain Functions *
   *************************/
  /**
   * @inheritdoc IL1StandardBridge
   */
  function finalizeETHWithdrawal(
    address _from,
    address _to,
    uint256 _amount,
    bytes calldata _data
  ) external onlyFromCrossDomainAccount(l2TokenBridge) {
    (bool success, ) = _to.call{value: _amount}(new bytes(0));
    require(success, 'TransferHelper::safeTransferETH: ETH transfer failed');
    emit ETHWithdrawalFinalized(_from, _to, _amount, _data);
  }
  /**
   * @inheritdoc IL1ERC20Bridge
   */
  function finalizeERC20Withdrawal(
    address _l1Token,
    address _l2Token,
    address _from,
    address _to,
    uint256 _amount,
    bytes calldata _data
  ) external onlyFromCrossDomainAccount(l2TokenBridge) {
    deposits[_l1Token][_l2Token] = deposits[_l1Token][_l2Token] - _amount;
    // When a withdrawal is finalized on L1, the L1 Bridge transfers the funds to the withdrawer
    IERC20(_l1Token).safeTransfer(_to, _amount);
    emit ERC20WithdrawalFinalized(
      _l1Token,
      _l2Token,
      _from,
      _to,
      _amount,
      _data
    );
  }
  /*****************************
   * Temporary - Migrating ETH *
   *****************************/
  /**
   * @dev Adds ETH balance to the account. This is meant to allow for ETH
   * to be migrated from an old gateway to a new gateway.
   * NOTE: This is left for one upgrade only so we are able to receive the migrated ETH from the
   * old contract
   */
  function donateETH() external payable {}
}
// SPDX-License-Identifier: MIT
pragma solidity >0.5.0 <0.9.0;
import './IL1ERC20Bridge.sol';
/**
 * @title IL1StandardBridge
 */
interface IL1StandardBridge is IL1ERC20Bridge {
  /**********
   * Events *
   **********/
  event ETHDepositInitiated(
    address indexed _from,
    address indexed _to,
    uint256 _amount,
    bytes _data
  );
  event ETHWithdrawalFinalized(
    address indexed _from,
    address indexed _to,
    uint256 _amount,
    bytes _data
  );
  /********************
   * Public Functions *
   ********************/
  /**
   * @dev Deposit an amount of the ETH to the caller's balance on L2.
   * @param _l2Gas Gas limit required to complete the deposit on L2.
   * @param _data Optional data to forward to L2. This data is provided
   *        solely as a convenience for external contracts. Aside from enforcing a maximum
   *        length, these contracts provide no guarantees about its content.
   */
  function depositETH(uint32 _l2Gas, bytes calldata _data) external payable;
  /**
   * @dev Deposit an amount of ETH to a recipient's balance on L2.
   * @param _to L2 address to credit the withdrawal to.
   * @param _l2Gas Gas limit required to complete the deposit on L2.
   * @param _data Optional data to forward to L2. This data is provided
   *        solely as a convenience for external contracts. Aside from enforcing a maximum
   *        length, these contracts provide no guarantees about its content.
   */
  function depositETHTo(
    address _to,
    uint32 _l2Gas,
    bytes calldata _data
  ) external payable;
  /*************************
   * Cross-chain Functions *
   *************************/
  /**
   * @dev Complete a withdrawal from L2 to L1, and credit funds to the recipient's balance of the
   * L1 ETH token. Since only the xDomainMessenger can call this function, it will never be called
   * before the withdrawal is finalized.
   * @param _from L2 address initiating the transfer.
   * @param _to L1 address to credit the withdrawal to.
   * @param _amount Amount of the ERC20 to deposit.
   * @param _data Optional data to forward to L2. This data is provided
   *        solely as a convenience for external contracts. Aside from enforcing a maximum
   *        length, these contracts provide no guarantees about its content.
   */
  function finalizeETHWithdrawal(
    address _from,
    address _to,
    uint256 _amount,
    bytes calldata _data
  ) external;
}
// SPDX-License-Identifier: MIT
pragma solidity >0.5.0 <0.9.0;
/**
 * @title IL1ERC20Bridge
 */
interface IL1ERC20Bridge {
  /**********
   * Events *
   **********/
  event ERC20DepositInitiated(
    address indexed _l1Token,
    address indexed _l2Token,
    address indexed _from,
    address _to,
    uint256 _amount,
    bytes _data
  );
  event ERC20WithdrawalFinalized(
    address indexed _l1Token,
    address indexed _l2Token,
    address indexed _from,
    address _to,
    uint256 _amount,
    bytes _data
  );
  /********************
   * Public Functions *
   ********************/
  /**
   * @dev get the address of the corresponding L2 bridge contract.
   * @return Address of the corresponding L2 bridge contract.
   */
  function l2TokenBridge() external returns (address);
  /**
   * @dev deposit an amount of the ERC20 to the caller's balance on L2.
   * @param _l1Token Address of the L1 ERC20 we are depositing
   * @param _l2Token Address of the L1 respective L2 ERC20
   * @param _amount Amount of the ERC20 to deposit
   * @param _l2Gas Gas limit required to complete the deposit on L2.
   * @param _data Optional data to forward to L2. This data is provided
   *        solely as a convenience for external contracts. Aside from enforcing a maximum
   *        length, these contracts provide no guarantees about its content.
   */
  function depositERC20(
    address _l1Token,
    address _l2Token,
    uint256 _amount,
    uint32 _l2Gas,
    bytes calldata _data
  ) external;
  /**
   * @dev deposit an amount of ERC20 to a recipient's balance on L2.
   * @param _l1Token Address of the L1 ERC20 we are depositing
   * @param _l2Token Address of the L1 respective L2 ERC20
   * @param _to L2 address to credit the withdrawal to.
   * @param _amount Amount of the ERC20 to deposit.
   * @param _l2Gas Gas limit required to complete the deposit on L2.
   * @param _data Optional data to forward to L2. This data is provided
   *        solely as a convenience for external contracts. Aside from enforcing a maximum
   *        length, these contracts provide no guarantees about its content.
   */
  function depositERC20To(
    address _l1Token,
    address _l2Token,
    address _to,
    uint256 _amount,
    uint32 _l2Gas,
    bytes calldata _data
  ) external;
  /*************************
   * Cross-chain Functions *
   *************************/
  /**
   * @dev Complete a withdrawal from L2 to L1, and credit funds to the recipient's balance of the
   * L1 ERC20 token.
   * This call will fail if the initialized withdrawal from L2 has not been finalized.
   *
   * @param _l1Token Address of L1 token to finalizeWithdrawal for.
   * @param _l2Token Address of L2 token where withdrawal was initiated.
   * @param _from L2 address initiating the transfer.
   * @param _to L1 address to credit the withdrawal to.
   * @param _amount Amount of the ERC20 to deposit.
   * @param _data Data provided by the sender on L2. This data is provided
   *   solely as a convenience for external contracts. Aside from enforcing a maximum
   *   length, these contracts provide no guarantees about its content.
   */
  function finalizeERC20Withdrawal(
    address _l1Token,
    address _l2Token,
    address _from,
    address _to,
    uint256 _amount,
    bytes calldata _data
  ) external;
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/**
 * @title IL2ERC20Bridge
 */
interface IL2ERC20Bridge {
  /**********
   * Events *
   **********/
  event WithdrawalInitiated(
    address indexed _l1Token,
    address indexed _l2Token,
    address indexed _from,
    address _to,
    uint256 _amount,
    bytes _data
  );
  event DepositFinalized(
    address indexed _l1Token,
    address indexed _l2Token,
    address indexed _from,
    address _to,
    uint256 _amount,
    bytes _data
  );
  event DepositFailed(
    address indexed _l1Token,
    address indexed _l2Token,
    address indexed _from,
    address _to,
    uint256 _amount,
    bytes _data
  );
  /********************
   * Public Functions *
   ********************/
  /**
   * @dev get the address of the corresponding L1 bridge contract.
   * @return Address of the corresponding L1 bridge contract.
   */
  function l1TokenBridge() external returns (address);
  /**
   * @dev initiate a withdraw of some tokens to the caller's account on L1
   * @param _l2Token Address of L2 token where withdrawal was initiated.
   * @param _amount Amount of the token to withdraw.
   * param _l1Gas Unused, but included for potential forward compatibility considerations.
   * @param _data Optional data to forward to L1. This data is provided
   *        solely as a convenience for external contracts. Aside from enforcing a maximum
   *        length, these contracts provide no guarantees about its content.
   */
  function withdraw(
    address _l2Token,
    uint256 _amount,
    uint32 _l1Gas,
    bytes calldata _data
  ) external;
  /**
   * @dev initiate a withdraw of some token to a recipient's account on L1.
   * @param _l2Token Address of L2 token where withdrawal is initiated.
   * @param _to L1 adress to credit the withdrawal to.
   * @param _amount Amount of the token to withdraw.
   * param _l1Gas Unused, but included for potential forward compatibility considerations.
   * @param _data Optional data to forward to L1. This data is provided
   *        solely as a convenience for external contracts. Aside from enforcing a maximum
   *        length, these contracts provide no guarantees about its content.
   */
  function withdrawTo(
    address _l2Token,
    address _to,
    uint256 _amount,
    uint32 _l1Gas,
    bytes calldata _data
  ) external;
  /*************************
   * Cross-chain Functions *
   *************************/
  /**
   * @dev Complete a deposit from L1 to L2, and credits funds to the recipient's balance of this
   * L2 token. This call will fail if it did not originate from a corresponding deposit in
   * L1StandardTokenBridge.
   * @param _l1Token Address for the l1 token this is called with
   * @param _l2Token Address for the l2 token this is called with
   * @param _from Account to pull the deposit from on L2.
   * @param _to Address to receive the withdrawal at
   * @param _amount Amount of the token to withdraw
   * @param _data Data provider by the sender on L1. This data is provided
   *        solely as a convenience for external contracts. Aside from enforcing a maximum
   *        length, these contracts provide no guarantees about its content.
   */
  function finalizeDeposit(
    address _l1Token,
    address _l2Token,
    address _from,
    address _to,
    uint256 _amount,
    bytes calldata _data
  ) external;
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
/**
 * @dev Interface of the ERC20 standard as defined in the EIP.
 */
interface IERC20 {
    /**
     * @dev Returns the amount of tokens in existence.
     */
    function totalSupply() external view returns (uint256);
    /**
     * @dev Returns the amount of tokens owned by `account`.
     */
    function balanceOf(address account) external view returns (uint256);
    /**
     * @dev Moves `amount` tokens from the caller's account to `recipient`.
     *
     * Returns a boolean value indicating whether the operation succeeded.
     *
     * Emits a {Transfer} event.
     */
    function transfer(address recipient, uint256 amount) external returns (bool);
    /**
     * @dev Returns the remaining number of tokens that `spender` will be
     * allowed to spend on behalf of `owner` through {transferFrom}. This is
     * zero by default.
     *
     * This value changes when {approve} or {transferFrom} are called.
     */
    function allowance(address owner, address spender) external view returns (uint256);
    /**
     * @dev Sets `amount` as the allowance of `spender` over the caller's tokens.
     *
     * Returns a boolean value indicating whether the operation succeeded.
     *
     * IMPORTANT: Beware that changing an allowance with this method brings the risk
     * that someone may use both the old and the new allowance by unfortunate
     * transaction ordering. One possible solution to mitigate this race
     * condition is to first reduce the spender's allowance to 0 and set the
     * desired value afterwards:
     * https://github.com/ethereum/EIPs/issues/20#issuecomment-263524729
     *
     * Emits an {Approval} event.
     */
    function approve(address spender, uint256 amount) external returns (bool);
    /**
     * @dev Moves `amount` tokens from `sender` to `recipient` using the
     * allowance mechanism. `amount` is then deducted from the caller's
     * allowance.
     *
     * Returns a boolean value indicating whether the operation succeeded.
     *
     * Emits a {Transfer} event.
     */
    function transferFrom(
        address sender,
        address recipient,
        uint256 amount
    ) external returns (bool);
    /**
     * @dev Emitted when `value` tokens are moved from one account (`from`) to
     * another (`to`).
     *
     * Note that `value` may be zero.
     */
    event Transfer(address indexed from, address indexed to, uint256 value);
    /**
     * @dev Emitted when the allowance of a `spender` for an `owner` is set by
     * a call to {approve}. `value` is the new allowance.
     */
    event Approval(address indexed owner, address indexed spender, uint256 value);
}
// SPDX-License-Identifier: MIT
pragma solidity >0.5.0 <0.9.0;
/* Interface Imports */
import {ICrossDomainMessenger} from './ICrossDomainMessenger.sol';
/**
 * @title CrossDomainEnabled
 * @dev Helper contract for contracts performing cross-domain communications
 *
 * Compiler used: defined by inheriting contract
 * Runtime target: defined by inheriting contract
 */
contract CrossDomainEnabled {
  /*************
   * Variables *
   *************/
  // Messenger contract used to send and recieve messages from the other domain.
  address public messenger;
  /***************
   * Constructor *
   ***************/
  /**
   * @param _messenger Address of the CrossDomainMessenger on the current layer.
   */
  constructor(address _messenger) {
    messenger = _messenger;
  }
  /**********************
   * Function Modifiers *
   **********************/
  /**
   * Enforces that the modified function is only callable by a specific cross-domain account.
   * @param _sourceDomainAccount The only account on the originating domain which is
   *  authenticated to call this function.
   */
  modifier onlyFromCrossDomainAccount(address _sourceDomainAccount) {
    require(
      msg.sender == address(getCrossDomainMessenger()),
      'OVM_XCHAIN: messenger contract unauthenticated'
    );
    require(
      getCrossDomainMessenger().xDomainMessageSender() == _sourceDomainAccount,
      'OVM_XCHAIN: wrong sender of cross-domain message'
    );
    _;
  }
  /**********************
   * Internal Functions *
   **********************/
  /**
   * Gets the messenger, usually from storage. This function is exposed in case a child contract
   * needs to override.
   * @return The address of the cross-domain messenger contract which should be used.
   */
  function getCrossDomainMessenger()
    internal
    virtual
    returns (ICrossDomainMessenger)
  {
    return ICrossDomainMessenger(messenger);
  }
  /**q
   * Sends a message to an account on another domain
   * @param _crossDomainTarget The intended recipient on the destination domain
   * @param _message The data to send to the target (usually calldata to a function with
   *  `onlyFromCrossDomainAccount()`)
   * @param _gasLimit The gasLimit for the receipt of the message on the target domain.
   */
  function sendCrossDomainMessage(
    address _crossDomainTarget,
    uint32 _gasLimit,
    bytes memory _message
  ) internal {
    getCrossDomainMessenger().sendMessage(
      _crossDomainTarget,
      _message,
      _gasLimit
    );
  }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.9;
/**
 * @title Lib_PredeployAddresses
 */
library Lib_PredeployAddresses {
  // solhint-disable max-line-length
  address internal constant L2_TO_L1_MESSAGE_PASSER =
    0x4200000000000000000000000000000000000000;
  address internal constant L1_MESSAGE_SENDER =
    0x4200000000000000000000000000000000000001;
  address internal constant DEPLOYER_WHITELIST =
    0x4200000000000000000000000000000000000002;
  address payable internal constant OVM_ETH =
    payable(0x4200000000000000000000000000000000000006);
  // solhint-disable-next-line max-line-length
  address internal constant L2_CROSS_DOMAIN_MESSENGER =
    0x4200000000000000000000000000000000000007;
  address internal constant LIB_ADDRESS_MANAGER =
    0x4200000000000000000000000000000000000008;
  address internal constant PROXY_EOA =
    0x4200000000000000000000000000000000000009;
  address internal constant L2_STANDARD_BRIDGE =
    0x4200000000000000000000000000000000000010;
  address internal constant SEQUENCER_FEE_WALLET =
    0x4200000000000000000000000000000000000011;
  address internal constant L2_STANDARD_TOKEN_FACTORY =
    0x4200000000000000000000000000000000000012;
  address internal constant L1_BLOCK_NUMBER =
    0x4200000000000000000000000000000000000013;
  address internal constant OVM_GAS_PRICE_ORACLE =
    0x420000000000000000000000000000000000000F;
  address internal constant PROXY__BOBA_TURING_PREPAY =
    0x4200000000000000000000000000000000000020;
  address internal constant BOBA_TURING_PREPAY =
    0x4200000000000000000000000000000000000021;
  address internal constant BOBA_TURING_HELPER =
    0x4200000000000000000000000000000000000022;
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
/**
 * @dev Collection of functions related to the address type
 */
library Address {
    /**
     * @dev Returns true if `account` is a contract.
     *
     * [IMPORTANT]
     * ====
     * It is unsafe to assume that an address for which this function returns
     * false is an externally-owned account (EOA) and not a contract.
     *
     * Among others, `isContract` will return false for the following
     * types of addresses:
     *
     *  - an externally-owned account
     *  - a contract in construction
     *  - an address where a contract will be created
     *  - an address where a contract lived, but was destroyed
     * ====
     */
    function isContract(address account) internal view returns (bool) {
        // This method relies on extcodesize, which returns 0 for contracts in
        // construction, since the code is only stored at the end of the
        // constructor execution.
        uint256 size;
        assembly {
            size := extcodesize(account)
        }
        return size > 0;
    }
    /**
     * @dev Replacement for Solidity's `transfer`: sends `amount` wei to
     * `recipient`, forwarding all available gas and reverting on errors.
     *
     * https://eips.ethereum.org/EIPS/eip-1884[EIP1884] increases the gas cost
     * of certain opcodes, possibly making contracts go over the 2300 gas limit
     * imposed by `transfer`, making them unable to receive funds via
     * `transfer`. {sendValue} removes this limitation.
     *
     * https://diligence.consensys.net/posts/2019/09/stop-using-soliditys-transfer-now/[Learn more].
     *
     * IMPORTANT: because control is transferred to `recipient`, care must be
     * taken to not create reentrancy vulnerabilities. Consider using
     * {ReentrancyGuard} or the
     * https://solidity.readthedocs.io/en/v0.5.11/security-considerations.html#use-the-checks-effects-interactions-pattern[checks-effects-interactions pattern].
     */
    function sendValue(address payable recipient, uint256 amount) internal {
        require(address(this).balance >= amount, "Address: insufficient balance");
        (bool success, ) = recipient.call{value: amount}("");
        require(success, "Address: unable to send value, recipient may have reverted");
    }
    /**
     * @dev Performs a Solidity function call using a low level `call`. A
     * plain `call` is an unsafe replacement for a function call: use this
     * function instead.
     *
     * If `target` reverts with a revert reason, it is bubbled up by this
     * function (like regular Solidity function calls).
     *
     * Returns the raw returned data. To convert to the expected return value,
     * use https://solidity.readthedocs.io/en/latest/units-and-global-variables.html?highlight=abi.decode#abi-encoding-and-decoding-functions[`abi.decode`].
     *
     * Requirements:
     *
     * - `target` must be a contract.
     * - calling `target` with `data` must not revert.
     *
     * _Available since v3.1._
     */
    function functionCall(address target, bytes memory data) internal returns (bytes memory) {
        return functionCall(target, data, "Address: low-level call failed");
    }
    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`], but with
     * `errorMessage` as a fallback revert reason when `target` reverts.
     *
     * _Available since v3.1._
     */
    function functionCall(
        address target,
        bytes memory data,
        string memory errorMessage
    ) internal returns (bytes memory) {
        return functionCallWithValue(target, data, 0, errorMessage);
    }
    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
     * but also transferring `value` wei to `target`.
     *
     * Requirements:
     *
     * - the calling contract must have an ETH balance of at least `value`.
     * - the called Solidity function must be `payable`.
     *
     * _Available since v3.1._
     */
    function functionCallWithValue(
        address target,
        bytes memory data,
        uint256 value
    ) internal returns (bytes memory) {
        return functionCallWithValue(target, data, value, "Address: low-level call with value failed");
    }
    /**
     * @dev Same as {xref-Address-functionCallWithValue-address-bytes-uint256-}[`functionCallWithValue`], but
     * with `errorMessage` as a fallback revert reason when `target` reverts.
     *
     * _Available since v3.1._
     */
    function functionCallWithValue(
        address target,
        bytes memory data,
        uint256 value,
        string memory errorMessage
    ) internal returns (bytes memory) {
        require(address(this).balance >= value, "Address: insufficient balance for call");
        require(isContract(target), "Address: call to non-contract");
        (bool success, bytes memory returndata) = target.call{value: value}(data);
        return verifyCallResult(success, returndata, errorMessage);
    }
    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
     * but performing a static call.
     *
     * _Available since v3.3._
     */
    function functionStaticCall(address target, bytes memory data) internal view returns (bytes memory) {
        return functionStaticCall(target, data, "Address: low-level static call failed");
    }
    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-string-}[`functionCall`],
     * but performing a static call.
     *
     * _Available since v3.3._
     */
    function functionStaticCall(
        address target,
        bytes memory data,
        string memory errorMessage
    ) internal view returns (bytes memory) {
        require(isContract(target), "Address: static call to non-contract");
        (bool success, bytes memory returndata) = target.staticcall(data);
        return verifyCallResult(success, returndata, errorMessage);
    }
    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
     * but performing a delegate call.
     *
     * _Available since v3.4._
     */
    function functionDelegateCall(address target, bytes memory data) internal returns (bytes memory) {
        return functionDelegateCall(target, data, "Address: low-level delegate call failed");
    }
    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-string-}[`functionCall`],
     * but performing a delegate call.
     *
     * _Available since v3.4._
     */
    function functionDelegateCall(
        address target,
        bytes memory data,
        string memory errorMessage
    ) internal returns (bytes memory) {
        require(isContract(target), "Address: delegate call to non-contract");
        (bool success, bytes memory returndata) = target.delegatecall(data);
        return verifyCallResult(success, returndata, errorMessage);
    }
    /**
     * @dev Tool to verifies that a low level call was successful, and revert if it wasn't, either by bubbling the
     * revert reason using the provided one.
     *
     * _Available since v4.3._
     */
    function verifyCallResult(
        bool success,
        bytes memory returndata,
        string memory errorMessage
    ) internal pure returns (bytes memory) {
        if (success) {
            return returndata;
        } else {
            // Look for revert reason and bubble it up if present
            if (returndata.length > 0) {
                // The easiest way to bubble the revert reason is using memory via assembly
                assembly {
                    let returndata_size := mload(returndata)
                    revert(add(32, returndata), returndata_size)
                }
            } else {
                revert(errorMessage);
            }
        }
    }
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
import "../IERC20.sol";
import "../../../utils/Address.sol";
/**
 * @title SafeERC20
 * @dev Wrappers around ERC20 operations that throw on failure (when the token
 * contract returns false). Tokens that return no value (and instead revert or
 * throw on failure) are also supported, non-reverting calls are assumed to be
 * successful.
 * To use this library you can add a `using SafeERC20 for IERC20;` statement to your contract,
 * which allows you to call the safe operations as `token.safeTransfer(...)`, etc.
 */
library SafeERC20 {
    using Address for address;
    function safeTransfer(
        IERC20 token,
        address to,
        uint256 value
    ) internal {
        _callOptionalReturn(token, abi.encodeWithSelector(token.transfer.selector, to, value));
    }
    function safeTransferFrom(
        IERC20 token,
        address from,
        address to,
        uint256 value
    ) internal {
        _callOptionalReturn(token, abi.encodeWithSelector(token.transferFrom.selector, from, to, value));
    }
    /**
     * @dev Deprecated. This function has issues similar to the ones found in
     * {IERC20-approve}, and its usage is discouraged.
     *
     * Whenever possible, use {safeIncreaseAllowance} and
     * {safeDecreaseAllowance} instead.
     */
    function safeApprove(
        IERC20 token,
        address spender,
        uint256 value
    ) internal {
        // safeApprove should only be called when setting an initial allowance,
        // or when resetting it to zero. To increase and decrease it, use
        // 'safeIncreaseAllowance' and 'safeDecreaseAllowance'
        require(
            (value == 0) || (token.allowance(address(this), spender) == 0),
            "SafeERC20: approve from non-zero to non-zero allowance"
        );
        _callOptionalReturn(token, abi.encodeWithSelector(token.approve.selector, spender, value));
    }
    function safeIncreaseAllowance(
        IERC20 token,
        address spender,
        uint256 value
    ) internal {
        uint256 newAllowance = token.allowance(address(this), spender) + value;
        _callOptionalReturn(token, abi.encodeWithSelector(token.approve.selector, spender, newAllowance));
    }
    function safeDecreaseAllowance(
        IERC20 token,
        address spender,
        uint256 value
    ) internal {
        unchecked {
            uint256 oldAllowance = token.allowance(address(this), spender);
            require(oldAllowance >= value, "SafeERC20: decreased allowance below zero");
            uint256 newAllowance = oldAllowance - value;
            _callOptionalReturn(token, abi.encodeWithSelector(token.approve.selector, spender, newAllowance));
        }
    }
    /**
     * @dev Imitates a Solidity high-level call (i.e. a regular function call to a contract), relaxing the requirement
     * on the return value: the return value is optional (but if data is returned, it must not be false).
     * @param token The token targeted by the call.
     * @param data The call data (encoded using abi.encode or one of its variants).
     */
    function _callOptionalReturn(IERC20 token, bytes memory data) private {
        // We need to perform a low level call here, to bypass Solidity's return data size checking mechanism, since
        // we're implementing it ourselves. We use {Address.functionCall} to perform this call, which verifies that
        // the target address contains contract code and also asserts for success in the low-level call.
        bytes memory returndata = address(token).functionCall(data, "SafeERC20: low-level call failed");
        if (returndata.length > 0) {
            // Return data is optional
            require(abi.decode(returndata, (bool)), "SafeERC20: ERC20 operation did not succeed");
        }
    }
}
// SPDX-License-Identifier: MIT
pragma solidity >0.5.0 <0.9.0;
/**
 * @title ICrossDomainMessenger
 */
interface ICrossDomainMessenger {
  /**********
   * Events *
   **********/
  event SentMessage(
    address indexed target,
    address sender,
    bytes message,
    uint256 messageNonce,
    uint256 gasLimit
  );
  event RelayedMessage(bytes32 indexed msgHash);
  event FailedRelayedMessage(bytes32 indexed msgHash);
  /*************
   * Variables *
   *************/
  function xDomainMessageSender() external view returns (address);
  /********************
   * Public Functions *
   ********************/
  /**
   * Sends a cross domain message to the target messenger.
   * @param _target Target contract address.
   * @param _message Message to send to the target.
   * @param _gasLimit Gas limit for the provided message.
   */
  function sendMessage(
    address _target,
    bytes calldata _message,
    uint32 _gasLimit
  ) external;
}