// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

// solhint-disable-next-line interface-starts-with-i
interface AggregatorV3Interface {
  function decimals() external view returns (uint8);

  function description() external view returns (string memory);

  function version() external view returns (uint256);

  function getRoundData(
    uint80 _roundId
  ) external view returns (uint80 roundId, int256 answer, uint256 startedAt, uint256 updatedAt, uint80 answeredInRound);

  function latestRoundData()
    external
    view
    returns (uint80 roundId, int256 answer, uint256 startedAt, uint256 updatedAt, uint80 answeredInRound);
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

// solhint-disable-next-line interface-starts-with-i
interface BlockhashStoreInterface {
  function getBlockhash(uint256 number) external view returns (bytes32);
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

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

/// @title The ConfirmedOwner contract
/// @notice A contract with helpers for basic contract ownership.
contract ConfirmedOwner is ConfirmedOwnerWithProposal {
  constructor(address newOwner) ConfirmedOwnerWithProposal(newOwner, address(0)) {}
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

import {IOwnable} from "../interfaces/IOwnable.sol";

/// @title The ConfirmedOwner contract
/// @notice A contract with helpers for basic contract ownership.
contract ConfirmedOwnerWithProposal is IOwnable {
  address private s_owner;
  address private s_pendingOwner;

  event OwnershipTransferRequested(address indexed from, address indexed to);
  event OwnershipTransferred(address indexed from, address indexed to);

  constructor(address newOwner, address pendingOwner) {
    // solhint-disable-next-line gas-custom-errors
    require(newOwner != address(0), "Cannot set owner to zero");

    s_owner = newOwner;
    if (pendingOwner != address(0)) {
      _transferOwnership(pendingOwner);
    }
  }

  /// @notice Allows an owner to begin transferring ownership to a new address.
  function transferOwnership(address to) public override onlyOwner {
    _transferOwnership(to);
  }

  /// @notice Allows an ownership transfer to be completed by the recipient.
  function acceptOwnership() external override {
    // solhint-disable-next-line gas-custom-errors
    require(msg.sender == s_pendingOwner, "Must be proposed owner");

    address oldOwner = s_owner;
    s_owner = msg.sender;
    s_pendingOwner = address(0);

    emit OwnershipTransferred(oldOwner, msg.sender);
  }

  /// @notice Get the current owner
  function owner() public view override returns (address) {
    return s_owner;
  }

  /// @notice validate, transfer ownership, and emit relevant events
  function _transferOwnership(address to) private {
    // solhint-disable-next-line gas-custom-errors
    require(to != msg.sender, "Cannot transfer to self");

    s_pendingOwner = to;

    emit OwnershipTransferRequested(s_owner, to);
  }

  /// @notice validate access
  function _validateOwnership() internal view {
    // solhint-disable-next-line gas-custom-errors
    require(msg.sender == s_owner, "Only callable by owner");
  }

  /// @notice Reverts if called by anyone other than the contract owner.
  modifier onlyOwner() {
    _validateOwnership();
    _;
  }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

/// @notice: IMPORTANT NOTICE for anyone who wants to use this contract
/// @notice Source: https://github.com/ethereum-optimism/optimism/blob/71b93116738ee98c9f8713b1a5dfe626ce06c1b2/packages/contracts-bedrock/src/libraries/Constants.sol
/// @notice The original code was trimmed down to include only the necessary interface elements required to interact with GasPriceOracle
/// @notice We need this file so that Solidity compiler will not complain because some functions don't exist
/// @notice In reality, we don't embed this code into our own contracts, instead we make cross-contract calls on predeployed GasPriceOracle contract

/// @title Constants
/// @notice Constants is a library for storing constants. Simple! Don't put everything in here, just
///         the stuff used in multiple contracts. Constants that only apply to a single contract
///         should be defined in that contract instead.
library Constants {
  /// @notice Special address to be used as the tx origin for gas estimation calls in the
  ///         OptimismPortal and CrossDomainMessenger calls. You only need to use this address if
  ///         the minimum gas limit specified by the user is not actually enough to execute the
  ///         given message and you're attempting to estimate the actual necessary gas limit. We
  ///         use address(1) because it's the ecrecover precompile and therefore guaranteed to
  ///         never have any code on any EVM chain.
  address internal constant ESTIMATION_ADDRESS = address(1);

  /// @notice Value used for the L2 sender storage slot in both the OptimismPortal and the
  ///         CrossDomainMessenger contracts before an actual sender is set. This value is
  ///         non-zero to reduce the gas cost of message passing transactions.
  address internal constant DEFAULT_L2_SENDER = 0x000000000000000000000000000000000000dEaD;

  /// @notice The storage slot that holds the address of a proxy implementation.
  /// @dev `bytes32(uint256(keccak256('eip1967.proxy.implementation')) - 1)`
  bytes32 internal constant PROXY_IMPLEMENTATION_ADDRESS =
    0x360894a13ba1a3210667c828492db98dca3e2076cc3735a920a3ca505d382bbc;

  /// @notice The storage slot that holds the address of the owner.
  /// @dev `bytes32(uint256(keccak256('eip1967.proxy.admin')) - 1)`
  bytes32 internal constant PROXY_OWNER_ADDRESS = 0xb53127684a568b3173ae13b9f8a6016e243e63b6e8ee1178d6a717850b5d6103;

  /// @notice The address that represents ether when dealing with ERC20 token addresses.
  address internal constant ETHER = 0xEeeeeEeeeEeEeeEeEeEeeEEEeeeeEeeeeeeeEEeE;

  /// @notice The address that represents the system caller responsible for L1 attributes
  ///         transactions.
  address internal constant DEPOSITOR_ACCOUNT = 0xDeaDDEaDDeAdDeAdDEAdDEaddeAddEAdDEAd0001;
}

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.7.0) (utils/structs/EnumerableSet.sol)
// This file was procedurally generated from scripts/generate/templates/EnumerableSet.js.

pragma solidity ^0.8.0;

/**
 * @dev Library for managing
 * https://en.wikipedia.org/wiki/Set_(abstract_data_type)[sets] of primitive
 * types.
 *
 * Sets have the following properties:
 *
 * - Elements are added, removed, and checked for existence in constant time
 * (O(1)).
 * - Elements are enumerated in O(n). No guarantees are made on the ordering.
 *
 * ```
 * contract Example {
 *     // Add the library methods
 *     using EnumerableSet for EnumerableSet.AddressSet;
 *
 *     // Declare a set state variable
 *     EnumerableSet.AddressSet private mySet;
 * }
 * ```
 *
 * As of v3.3.0, sets of type `bytes32` (`Bytes32Set`), `address` (`AddressSet`)
 * and `uint256` (`UintSet`) are supported.
 *
 * [WARNING]
 * ====
 *  Trying to delete such a structure from storage will likely result in data corruption, rendering the structure unusable.
 *  See https://github.com/ethereum/solidity/pull/11843[ethereum/solidity#11843] for more info.
 *
 *  In order to clean an EnumerableSet, you can either remove all elements one by one or create a fresh instance using an array of EnumerableSet.
 * ====
 */
library EnumerableSet {
    // To implement this library for multiple types with as little code
    // repetition as possible, we write it in terms of a generic Set type with
    // bytes32 values.
    // The Set implementation uses private functions, and user-facing
    // implementations (such as AddressSet) are just wrappers around the
    // underlying Set.
    // This means that we can only create new EnumerableSets for types that fit
    // in bytes32.

    struct Set {
        // Storage of set values
        bytes32[] _values;
        // Position of the value in the `values` array, plus 1 because index 0
        // means a value is not in the set.
        mapping(bytes32 => uint256) _indexes;
    }

    /**
     * @dev Add a value to a set. O(1).
     *
     * Returns true if the value was added to the set, that is if it was not
     * already present.
     */
    function _add(Set storage set, bytes32 value) private returns (bool) {
        if (!_contains(set, value)) {
            set._values.push(value);
            // The value is stored at length-1, but we add 1 to all indexes
            // and use 0 as a sentinel value
            set._indexes[value] = set._values.length;
            return true;
        } else {
            return false;
        }
    }

    /**
     * @dev Removes a value from a set. O(1).
     *
     * Returns true if the value was removed from the set, that is if it was
     * present.
     */
    function _remove(Set storage set, bytes32 value) private returns (bool) {
        // We read and store the value's index to prevent multiple reads from the same storage slot
        uint256 valueIndex = set._indexes[value];

        if (valueIndex != 0) {
            // Equivalent to contains(set, value)
            // To delete an element from the _values array in O(1), we swap the element to delete with the last one in
            // the array, and then remove the last element (sometimes called as 'swap and pop').
            // This modifies the order of the array, as noted in {at}.

            uint256 toDeleteIndex = valueIndex - 1;
            uint256 lastIndex = set._values.length - 1;

            if (lastIndex != toDeleteIndex) {
                bytes32 lastValue = set._values[lastIndex];

                // Move the last value to the index where the value to delete is
                set._values[toDeleteIndex] = lastValue;
                // Update the index for the moved value
                set._indexes[lastValue] = valueIndex; // Replace lastValue's index to valueIndex
            }

            // Delete the slot where the moved value was stored
            set._values.pop();

            // Delete the index for the deleted slot
            delete set._indexes[value];

            return true;
        } else {
            return false;
        }
    }

    /**
     * @dev Returns true if the value is in the set. O(1).
     */
    function _contains(Set storage set, bytes32 value) private view returns (bool) {
        return set._indexes[value] != 0;
    }

    /**
     * @dev Returns the number of values on the set. O(1).
     */
    function _length(Set storage set) private view returns (uint256) {
        return set._values.length;
    }

    /**
     * @dev Returns the value stored at position `index` in the set. O(1).
     *
     * Note that there are no guarantees on the ordering of values inside the
     * array, and it may change when more values are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function _at(Set storage set, uint256 index) private view returns (bytes32) {
        return set._values[index];
    }

    /**
     * @dev Return the entire set in an array
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the set grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function _values(Set storage set) private view returns (bytes32[] memory) {
        return set._values;
    }

    // Bytes32Set

    struct Bytes32Set {
        Set _inner;
    }

    /**
     * @dev Add a value to a set. O(1).
     *
     * Returns true if the value was added to the set, that is if it was not
     * already present.
     */
    function add(Bytes32Set storage set, bytes32 value) internal returns (bool) {
        return _add(set._inner, value);
    }

    /**
     * @dev Removes a value from a set. O(1).
     *
     * Returns true if the value was removed from the set, that is if it was
     * present.
     */
    function remove(Bytes32Set storage set, bytes32 value) internal returns (bool) {
        return _remove(set._inner, value);
    }

    /**
     * @dev Returns true if the value is in the set. O(1).
     */
    function contains(Bytes32Set storage set, bytes32 value) internal view returns (bool) {
        return _contains(set._inner, value);
    }

    /**
     * @dev Returns the number of values in the set. O(1).
     */
    function length(Bytes32Set storage set) internal view returns (uint256) {
        return _length(set._inner);
    }

    /**
     * @dev Returns the value stored at position `index` in the set. O(1).
     *
     * Note that there are no guarantees on the ordering of values inside the
     * array, and it may change when more values are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function at(Bytes32Set storage set, uint256 index) internal view returns (bytes32) {
        return _at(set._inner, index);
    }

    /**
     * @dev Return the entire set in an array
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the set grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function values(Bytes32Set storage set) internal view returns (bytes32[] memory) {
        bytes32[] memory store = _values(set._inner);
        bytes32[] memory result;

        /// @solidity memory-safe-assembly
        assembly {
            result := store
        }

        return result;
    }

    // AddressSet

    struct AddressSet {
        Set _inner;
    }

    /**
     * @dev Add a value to a set. O(1).
     *
     * Returns true if the value was added to the set, that is if it was not
     * already present.
     */
    function add(AddressSet storage set, address value) internal returns (bool) {
        return _add(set._inner, bytes32(uint256(uint160(value))));
    }

    /**
     * @dev Removes a value from a set. O(1).
     *
     * Returns true if the value was removed from the set, that is if it was
     * present.
     */
    function remove(AddressSet storage set, address value) internal returns (bool) {
        return _remove(set._inner, bytes32(uint256(uint160(value))));
    }

    /**
     * @dev Returns true if the value is in the set. O(1).
     */
    function contains(AddressSet storage set, address value) internal view returns (bool) {
        return _contains(set._inner, bytes32(uint256(uint160(value))));
    }

    /**
     * @dev Returns the number of values in the set. O(1).
     */
    function length(AddressSet storage set) internal view returns (uint256) {
        return _length(set._inner);
    }

    /**
     * @dev Returns the value stored at position `index` in the set. O(1).
     *
     * Note that there are no guarantees on the ordering of values inside the
     * array, and it may change when more values are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function at(AddressSet storage set, uint256 index) internal view returns (address) {
        return address(uint160(uint256(_at(set._inner, index))));
    }

    /**
     * @dev Return the entire set in an array
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the set grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function values(AddressSet storage set) internal view returns (address[] memory) {
        bytes32[] memory store = _values(set._inner);
        address[] memory result;

        /// @solidity memory-safe-assembly
        assembly {
            result := store
        }

        return result;
    }

    // UintSet

    struct UintSet {
        Set _inner;
    }

    /**
     * @dev Add a value to a set. O(1).
     *
     * Returns true if the value was added to the set, that is if it was not
     * already present.
     */
    function add(UintSet storage set, uint256 value) internal returns (bool) {
        return _add(set._inner, bytes32(value));
    }

    /**
     * @dev Removes a value from a set. O(1).
     *
     * Returns true if the value was removed from the set, that is if it was
     * present.
     */
    function remove(UintSet storage set, uint256 value) internal returns (bool) {
        return _remove(set._inner, bytes32(value));
    }

    /**
     * @dev Returns true if the value is in the set. O(1).
     */
    function contains(UintSet storage set, uint256 value) internal view returns (bool) {
        return _contains(set._inner, bytes32(value));
    }

    /**
     * @dev Returns the number of values in the set. O(1).
     */
    function length(UintSet storage set) internal view returns (uint256) {
        return _length(set._inner);
    }

    /**
     * @dev Returns the value stored at position `index` in the set. O(1).
     *
     * Note that there are no guarantees on the ordering of values inside the
     * array, and it may change when more values are added or removed.
     *
     * Requirements:
     *
     * - `index` must be strictly less than {length}.
     */
    function at(UintSet storage set, uint256 index) internal view returns (uint256) {
        return uint256(_at(set._inner, index));
    }

    /**
     * @dev Return the entire set in an array
     *
     * WARNING: This operation will copy the entire storage to memory, which can be quite expensive. This is designed
     * to mostly be used by view accessors that are queried without any gas fees. Developers should keep in mind that
     * this function has an unbounded cost, and using it as part of a state-changing function may render the function
     * uncallable if the set grows to a point where copying to memory consumes too much gas to fit in a block.
     */
    function values(UintSet storage set) internal view returns (uint256[] memory) {
        bytes32[] memory store = _values(set._inner);
        uint256[] memory result;

        /// @solidity memory-safe-assembly
        assembly {
            result := store
        }

        return result;
    }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

/// @notice: IMPORTANT NOTICE for anyone who wants to use this contract
/// @notice Source: https://github.com/ethereum-optimism/optimism/blob/71b93116738ee98c9f8713b1a5dfe626ce06c1b2/packages/contracts-bedrock/src/libraries/GasPayingToken.sol
/// @notice The original code was trimmed down to include only the necessary interface elements required to interact with GasPriceOracle
/// @notice We need this file so that Solidity compiler will not complain because some functions don't exist
/// @notice In reality, we don't embed this code into our own contracts, instead we make cross-contract calls on predeployed GasPriceOracle contract

import {Storage} from "./Storage.sol";
import {Constants} from "./Constants.sol";
import {LibString} from "../deps/LibString.sol";

/// @title IGasToken
/// @notice Implemented by contracts that are aware of the custom gas token used
///         by the L2 network.
interface IGasToken {
  /// @notice Getter for the ERC20 token address that is used to pay for gas and its decimals.
  function gasPayingToken() external view returns (address, uint8);
  /// @notice Returns the gas token name.
  function gasPayingTokenName() external view returns (string memory);
  /// @notice Returns the gas token symbol.
  function gasPayingTokenSymbol() external view returns (string memory);
  /// @notice Returns true if the network uses a custom gas token.
  function isCustomGasToken() external view returns (bool);
}

/// @title GasPayingToken
/// @notice Handles reading and writing the custom gas token to storage.
///         To be used in any place where gas token information is read or
///         written to state. If multiple contracts use this library, the
///         values in storage should be kept in sync between them.
library GasPayingToken {
  /// @notice The storage slot that contains the address and decimals of the gas paying token
  bytes32 internal constant GAS_PAYING_TOKEN_SLOT = bytes32(uint256(keccak256("opstack.gaspayingtoken")) - 1);

  /// @notice The storage slot that contains the ERC20 `name()` of the gas paying token
  bytes32 internal constant GAS_PAYING_TOKEN_NAME_SLOT = bytes32(uint256(keccak256("opstack.gaspayingtokenname")) - 1);

  /// @notice the storage slot that contains the ERC20 `symbol()` of the gas paying token
  bytes32 internal constant GAS_PAYING_TOKEN_SYMBOL_SLOT =
    bytes32(uint256(keccak256("opstack.gaspayingtokensymbol")) - 1);

  /// @notice Reads the gas paying token and its decimals from the magic
  ///         storage slot. If nothing is set in storage, then the ether
  ///         address is returned instead.
  function getToken() internal view returns (address addr_, uint8 decimals_) {
    bytes32 slot = Storage.getBytes32(GAS_PAYING_TOKEN_SLOT);
    addr_ = address(uint160(uint256(slot) & uint256(type(uint160).max)));
    if (addr_ == address(0)) {
      addr_ = Constants.ETHER;
      decimals_ = 18;
    } else {
      decimals_ = uint8(uint256(slot) >> 160);
    }
  }

  /// @notice Reads the gas paying token's name from the magic storage slot.
  ///         If nothing is set in storage, then the ether name, 'Ether', is returned instead.
  function getName() internal view returns (string memory name_) {
    (address addr, ) = getToken();
    if (addr == Constants.ETHER) {
      name_ = "Ether";
    } else {
      name_ = LibString.fromSmallString(Storage.getBytes32(GAS_PAYING_TOKEN_NAME_SLOT));
    }
  }

  /// @notice Reads the gas paying token's symbol from the magic storage slot.
  ///         If nothing is set in storage, then the ether symbol, 'ETH', is returned instead.
  function getSymbol() internal view returns (string memory symbol_) {
    (address addr, ) = getToken();
    if (addr == Constants.ETHER) {
      symbol_ = "ETH";
    } else {
      symbol_ = LibString.fromSmallString(Storage.getBytes32(GAS_PAYING_TOKEN_SYMBOL_SLOT));
    }
  }

  /// @notice Writes the gas paying token, its decimals, name and symbol to the magic storage slot.
  function set(address _token, uint8 _decimals, bytes32 _name, bytes32 _symbol) internal {
    Storage.setBytes32(GAS_PAYING_TOKEN_SLOT, bytes32((uint256(_decimals) << 160) | uint256(uint160(_token))));
    Storage.setBytes32(GAS_PAYING_TOKEN_NAME_SLOT, _name);
    Storage.setBytes32(GAS_PAYING_TOKEN_SYMBOL_SLOT, _symbol);
  }

  /// @notice Maps a string to a normalized null-terminated small string.
  function sanitize(string memory _str) internal pure returns (bytes32) {
    require(bytes(_str).length <= 32, "GasPayingToken: string cannot be greater than 32 bytes");

    return LibString.toSmallString(_str);
  }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.15;

/// @notice: IMPORTANT NOTICE for anyone who wants to use this contract
/// @notice Source: https://github.com/ethereum-optimism/optimism/blob/71b93116738ee98c9f8713b1a5dfe626ce06c1b2/packages/contracts-bedrock/src/L2/GasPriceOracle.sol
/// @notice The original code was trimmed down to include only the necessary interface elements required to interact with GasPriceOracle
/// @notice We need this file so that Solidity compiler will not complain because some functions don't exist
/// @notice In reality, we don't embed this code into our own contracts, instead we make cross-contract calls on predeployed GasPriceOracle contract

import {ISemver} from "../universal/ISemver.sol";
import {Predeploys} from "../libraries/Predeploys.sol";
import {L1Block} from "../L2/L1Block.sol";
import {Constants} from "../libraries/Constants.sol";
import {LibZip} from "../deps/LibZip.sol";

/// @custom:proxied
/// @custom:predeploy 0x420000000000000000000000000000000000000F
/// @title GasPriceOracle
/// @notice This contract maintains the variables responsible for computing the L1 portion of the
///         total fee charged on L2. Before Bedrock, this contract held variables in state that were
///         read during the state transition function to compute the L1 portion of the transaction
///         fee. After Bedrock, this contract now simply proxies the L1Block contract, which has
///         the values used to compute the L1 portion of the fee in its state.
///
///         The contract exposes an API that is useful for knowing how large the L1 portion of the
///         transaction fee will be. The following events were deprecated with Bedrock:
///         - event OverheadUpdated(uint256 overhead);
///         - event ScalarUpdated(uint256 scalar);
///         - event DecimalsUpdated(uint256 decimals);
contract GasPriceOracle is ISemver {
  /// @notice Number of decimals used in the scalar.
  uint256 public constant DECIMALS = 6;

  /// @notice Semantic version.
  /// @custom:semver 1.3.0
  string public constant version = "1.3.0";

  /// @notice This is the intercept value for the linear regression used to estimate the final size of the
  ///         compressed transaction.
  int32 private constant COST_INTERCEPT = -42_585_600;

  /// @notice This is the coefficient value for the linear regression used to estimate the final size of the
  ///         compressed transaction.
  uint32 private constant COST_FASTLZ_COEF = 836_500;

  /// @notice This is the minimum bound for the fastlz to brotli size estimation. Any estimations below this
  ///         are set to this value.
  uint256 private constant MIN_TRANSACTION_SIZE = 100;

  /// @notice Indicates whether the network has gone through the Ecotone upgrade.
  bool public isEcotone;

  /// @notice Indicates whether the network has gone through the Fjord upgrade.
  bool public isFjord;

  /// @notice Computes the L1 portion of the fee based on the size of the rlp encoded input
  ///         transaction, the current L1 base fee, and the various dynamic parameters.
  /// @param _data Unsigned fully RLP-encoded transaction to get the L1 fee for.
  /// @return L1 fee that should be paid for the tx
  function getL1Fee(bytes memory _data) external view returns (uint256) {
    if (isFjord) {
      return _getL1FeeFjord(_data);
    } else if (isEcotone) {
      return _getL1FeeEcotone(_data);
    }
    return _getL1FeeBedrock(_data);
  }

  /// @notice returns an upper bound for the L1 fee for a given transaction size.
  /// It is provided for callers who wish to estimate L1 transaction costs in the
  /// write path, and is much more gas efficient than `getL1Fee`.
  /// It assumes the worst case of fastlz upper-bound which covers %99.99 txs.
  /// @param _unsignedTxSize Unsigned fully RLP-encoded transaction size to get the L1 fee for.
  /// @return L1 estimated upper-bound fee that should be paid for the tx
  function getL1FeeUpperBound(uint256 _unsignedTxSize) external view returns (uint256) {
    require(isFjord, "GasPriceOracle: getL1FeeUpperBound only supports Fjord");

    // Add 68 to the size to account for unsigned tx:
    uint256 txSize = _unsignedTxSize + 68;
    // txSize / 255 + 16 is the pratical fastlz upper-bound covers %99.99 txs.
    uint256 flzUpperBound = txSize + txSize / 255 + 16;

    return _fjordL1Cost(flzUpperBound);
  }

  /// @notice Set chain to be Ecotone chain (callable by depositor account)
  function setEcotone() external {
    require(
      msg.sender == Constants.DEPOSITOR_ACCOUNT,
      "GasPriceOracle: only the depositor account can set isEcotone flag"
    );
    require(isEcotone == false, "GasPriceOracle: Ecotone already active");
    isEcotone = true;
  }

  /// @notice Set chain to be Fjord chain (callable by depositor account)
  function setFjord() external {
    require(
      msg.sender == Constants.DEPOSITOR_ACCOUNT,
      "GasPriceOracle: only the depositor account can set isFjord flag"
    );
    require(isEcotone, "GasPriceOracle: Fjord can only be activated after Ecotone");
    require(isFjord == false, "GasPriceOracle: Fjord already active");
    isFjord = true;
  }

  /// @notice Retrieves the current gas price (base fee).
  /// @return Current L2 gas price (base fee).
  function gasPrice() public view returns (uint256) {
    return block.basefee;
  }

  /// @notice Retrieves the current base fee.
  /// @return Current L2 base fee.
  function baseFee() public view returns (uint256) {
    return block.basefee;
  }

  /// @custom:legacy
  /// @notice Retrieves the current fee overhead.
  /// @return Current fee overhead.
  function overhead() public view returns (uint256) {
    require(!isEcotone, "GasPriceOracle: overhead() is deprecated");
    return L1Block(Predeploys.L1_BLOCK_ATTRIBUTES).l1FeeOverhead();
  }

  /// @custom:legacy
  /// @notice Retrieves the current fee scalar.
  /// @return Current fee scalar.
  function scalar() public view returns (uint256) {
    require(!isEcotone, "GasPriceOracle: scalar() is deprecated");
    return L1Block(Predeploys.L1_BLOCK_ATTRIBUTES).l1FeeScalar();
  }

  /// @notice Retrieves the latest known L1 base fee.
  /// @return Latest known L1 base fee.
  function l1BaseFee() public view returns (uint256) {
    return L1Block(Predeploys.L1_BLOCK_ATTRIBUTES).basefee();
  }

  /// @notice Retrieves the current blob base fee.
  /// @return Current blob base fee.
  function blobBaseFee() public view returns (uint256) {
    return L1Block(Predeploys.L1_BLOCK_ATTRIBUTES).blobBaseFee();
  }

  /// @notice Retrieves the current base fee scalar.
  /// @return Current base fee scalar.
  function baseFeeScalar() public view returns (uint32) {
    return L1Block(Predeploys.L1_BLOCK_ATTRIBUTES).baseFeeScalar();
  }

  /// @notice Retrieves the current blob base fee scalar.
  /// @return Current blob base fee scalar.
  function blobBaseFeeScalar() public view returns (uint32) {
    return L1Block(Predeploys.L1_BLOCK_ATTRIBUTES).blobBaseFeeScalar();
  }

  /// @custom:legacy
  /// @notice Retrieves the number of decimals used in the scalar.
  /// @return Number of decimals used in the scalar.
  function decimals() public pure returns (uint256) {
    return DECIMALS;
  }

  /// @notice Computes the amount of L1 gas used for a transaction. Adds 68 bytes
  ///         of padding to account for the fact that the input does not have a signature.
  /// @param _data Unsigned fully RLP-encoded transaction to get the L1 gas for.
  /// @return Amount of L1 gas used to publish the transaction.
  /// @custom:deprecated This method does not accurately estimate the gas used for a transaction.
  ///                    If you are calculating fees use getL1Fee or getL1FeeUpperBound.
  function getL1GasUsed(bytes memory _data) public view returns (uint256) {
    if (isFjord) {
      // Add 68 to the size to account for unsigned tx
      // Assume the compressed data is mostly non-zero, and would pay 16 gas per calldata byte
      // Divide by 1e6 due to the scaling factor of the linear regression
      return (_fjordLinearRegression(LibZip.flzCompress(_data).length + 68) * 16) / 1e6;
    }
    uint256 l1GasUsed = _getCalldataGas(_data);
    if (isEcotone) {
      return l1GasUsed;
    }
    return l1GasUsed + L1Block(Predeploys.L1_BLOCK_ATTRIBUTES).l1FeeOverhead();
  }

  /// @notice Computation of the L1 portion of the fee for Bedrock.
  /// @param _data Unsigned fully RLP-encoded transaction to get the L1 fee for.
  /// @return L1 fee that should be paid for the tx
  function _getL1FeeBedrock(bytes memory _data) internal view returns (uint256) {
    uint256 l1GasUsed = _getCalldataGas(_data);
    uint256 fee = (l1GasUsed + L1Block(Predeploys.L1_BLOCK_ATTRIBUTES).l1FeeOverhead()) *
      l1BaseFee() *
      L1Block(Predeploys.L1_BLOCK_ATTRIBUTES).l1FeeScalar();
    return fee / (10 ** DECIMALS);
  }

  /// @notice L1 portion of the fee after Ecotone.
  /// @param _data Unsigned fully RLP-encoded transaction to get the L1 fee for.
  /// @return L1 fee that should be paid for the tx
  function _getL1FeeEcotone(bytes memory _data) internal view returns (uint256) {
    uint256 l1GasUsed = _getCalldataGas(_data);
    uint256 scaledBaseFee = baseFeeScalar() * 16 * l1BaseFee();
    uint256 scaledBlobBaseFee = blobBaseFeeScalar() * blobBaseFee();
    uint256 fee = l1GasUsed * (scaledBaseFee + scaledBlobBaseFee);
    return fee / (16 * 10 ** DECIMALS);
  }

  /// @notice L1 portion of the fee after Fjord.
  /// @param _data Unsigned fully RLP-encoded transaction to get the L1 fee for.
  /// @return L1 fee that should be paid for the tx
  function _getL1FeeFjord(bytes memory _data) internal view returns (uint256) {
    return _fjordL1Cost(LibZip.flzCompress(_data).length + 68);
  }

  /// @notice L1 gas estimation calculation.
  /// @param _data Unsigned fully RLP-encoded transaction to get the L1 gas for.
  /// @return Amount of L1 gas used to publish the transaction.
  function _getCalldataGas(bytes memory _data) internal pure returns (uint256) {
    uint256 total = 0;
    uint256 length = _data.length;
    for (uint256 i = 0; i < length; i++) {
      if (_data[i] == 0) {
        total += 4;
      } else {
        total += 16;
      }
    }
    return total + (68 * 16);
  }

  /// @notice Fjord L1 cost based on the compressed and original tx size.
  /// @param _fastLzSize estimated compressed tx size.
  /// @return Fjord L1 fee that should be paid for the tx
  function _fjordL1Cost(uint256 _fastLzSize) internal view returns (uint256) {
    // Apply the linear regression to estimate the Brotli 10 size
    uint256 estimatedSize = _fjordLinearRegression(_fastLzSize);
    uint256 feeScaled = baseFeeScalar() * 16 * l1BaseFee() + blobBaseFeeScalar() * blobBaseFee();
    return (estimatedSize * feeScaled) / (10 ** (DECIMALS * 2));
  }

  /// @notice Takes the fastLz size compression and returns the estimated Brotli
  /// @param _fastLzSize fastlz compressed tx size.
  /// @return Number of bytes in the compressed transaction
  function _fjordLinearRegression(uint256 _fastLzSize) internal pure returns (uint256) {
    int256 estimatedSize = COST_INTERCEPT + int256(COST_FASTLZ_COEF * _fastLzSize);
    if (estimatedSize < int256(MIN_TRANSACTION_SIZE) * 1e6) {
      estimatedSize = int256(MIN_TRANSACTION_SIZE) * 1e6;
    }
    return uint256(estimatedSize);
  }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.6;

interface IERC677Receiver {
  function onTokenTransfer(address sender, uint256 amount, bytes calldata data) external;
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

interface IOwnable {
  function owner() external returns (address);

  function transferOwnership(address recipient) external;

  function acceptOwnership() external;
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

/// @notice: IMPORTANT NOTICE for anyone who wants to use this contract
/// @notice Source: https://github.com/ethereum-optimism/optimism/blob/71b93116738ee98c9f8713b1a5dfe626ce06c1b2/packages/contracts-bedrock/src/universal/ISemver.sol
/// @notice The original code was trimmed down to include only the necessary interface elements required to interact with GasPriceOracle
/// @notice We need this file so that Solidity compiler will not complain because some functions don't exist
/// @notice In reality, we don't embed this code into our own contracts, instead we make cross-contract calls on predeployed GasPriceOracle contract

/// @title ISemver
/// @notice ISemver is a simple contract for ensuring that contracts are
///         versioned using semantic versioning.
interface ISemver {
  /// @notice Getter for the semantic version of the contract. This is not
  ///         meant to be used onchain but instead meant to be used by offchain
  ///         tooling.
  /// @return Semver contract version as a string.
  function version() external view returns (string memory);
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

import {VRFV2PlusClient} from "../libraries/VRFV2PlusClient.sol";
import {IVRFSubscriptionV2Plus} from "./IVRFSubscriptionV2Plus.sol";

// Interface that enables consumers of VRFCoordinatorV2Plus to be future-proof for upgrades
// This interface is supported by subsequent versions of VRFCoordinatorV2Plus
interface IVRFCoordinatorV2Plus is IVRFSubscriptionV2Plus {
  /**
   * @notice Request a set of random words.
   * @param req - a struct containing following fields for randomness request:
   * keyHash - Corresponds to a particular oracle job which uses
   * that key for generating the VRF proof. Different keyHash's have different gas price
   * ceilings, so you can select a specific one to bound your maximum per request cost.
   * subId  - The ID of the VRF subscription. Must be funded
   * with the minimum subscription balance required for the selected keyHash.
   * requestConfirmations - How many blocks you'd like the
   * oracle to wait before responding to the request. See SECURITY CONSIDERATIONS
   * for why you may want to request more. The acceptable range is
   * [minimumRequestBlockConfirmations, 200].
   * callbackGasLimit - How much gas you'd like to receive in your
   * fulfillRandomWords callback. Note that gasleft() inside fulfillRandomWords
   * may be slightly less than this amount because of gas used calling the function
   * (argument decoding etc.), so you may need to request slightly more than you expect
   * to have inside fulfillRandomWords. The acceptable range is
   * [0, maxGasLimit]
   * numWords - The number of uint256 random values you'd like to receive
   * in your fulfillRandomWords callback. Note these numbers are expanded in a
   * secure way by the VRFCoordinator from a single random value supplied by the oracle.
   * extraArgs - abi-encoded extra args
   * @return requestId - A unique identifier of the request. Can be used to match
   * a request to a response in fulfillRandomWords.
   */
  function requestRandomWords(VRFV2PlusClient.RandomWordsRequest calldata req) external returns (uint256 requestId);
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.4;

// Future versions of VRFCoordinatorV2Plus must implement IVRFCoordinatorV2PlusMigration
// to support migrations from previous versions
interface IVRFCoordinatorV2PlusMigration {
  /**
   * @notice called by older versions of coordinator for migration.
   * @notice only callable by older versions of coordinator
   * @notice supports transfer of native currency
   * @param encodedData - user data from older version of coordinator
   */
  function onMigration(bytes calldata encodedData) external payable;
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

/// @notice The IVRFMigratableConsumerV2Plus interface defines the
/// @notice method required to be implemented by all V2Plus consumers.
/// @dev This interface is designed to be used in VRFConsumerBaseV2Plus.
interface IVRFMigratableConsumerV2Plus {
  event CoordinatorSet(address vrfCoordinator);

  /// @notice Sets the VRF Coordinator address
  /// @notice This method should only be callable by the coordinator or contract owner
  function setCoordinator(address vrfCoordinator) external;
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

/// @notice The IVRFSubscriptionV2Plus interface defines the subscription
/// @notice related methods implemented by the V2Plus coordinator.
interface IVRFSubscriptionV2Plus {
  /**
   * @notice Add a consumer to a VRF subscription.
   * @param subId - ID of the subscription
   * @param consumer - New consumer which can use the subscription
   */
  function addConsumer(uint256 subId, address consumer) external;

  /**
   * @notice Remove a consumer from a VRF subscription.
   * @param subId - ID of the subscription
   * @param consumer - Consumer to remove from the subscription
   */
  function removeConsumer(uint256 subId, address consumer) external;

  /**
   * @notice Cancel a subscription
   * @param subId - ID of the subscription
   * @param to - Where to send the remaining LINK to
   */
  function cancelSubscription(uint256 subId, address to) external;

  /**
   * @notice Accept subscription owner transfer.
   * @param subId - ID of the subscription
   * @dev will revert if original owner of subId has
   * not requested that msg.sender become the new owner.
   */
  function acceptSubscriptionOwnerTransfer(uint256 subId) external;

  /**
   * @notice Request subscription owner transfer.
   * @param subId - ID of the subscription
   * @param newOwner - proposed new owner of the subscription
   */
  function requestSubscriptionOwnerTransfer(uint256 subId, address newOwner) external;

  /**
   * @notice Create a VRF subscription.
   * @return subId - A unique subscription id.
   * @dev You can manage the consumer set dynamically with addConsumer/removeConsumer.
   * @dev Note to fund the subscription with LINK, use transferAndCall. For example
   * @dev  LINKTOKEN.transferAndCall(
   * @dev    address(COORDINATOR),
   * @dev    amount,
   * @dev    abi.encode(subId));
   * @dev Note to fund the subscription with Native, use fundSubscriptionWithNative. Be sure
   * @dev  to send Native with the call, for example:
   * @dev COORDINATOR.fundSubscriptionWithNative{value: amount}(subId);
   */
  function createSubscription() external returns (uint256 subId);

  /**
   * @notice Get a VRF subscription.
   * @param subId - ID of the subscription
   * @return balance - LINK balance of the subscription in juels.
   * @return nativeBalance - native balance of the subscription in wei.
   * @return reqCount - Requests count of subscription.
   * @return owner - owner of the subscription.
   * @return consumers - list of consumer address which are able to use this subscription.
   */
  function getSubscription(
    uint256 subId
  )
    external
    view
    returns (uint96 balance, uint96 nativeBalance, uint64 reqCount, address owner, address[] memory consumers);

  /*
   * @notice Check to see if there exists a request commitment consumers
   * for all consumers and keyhashes for a given sub.
   * @param subId - ID of the subscription
   * @return true if there exists at least one unfulfilled request for the subscription, false
   * otherwise.
   */
  function pendingRequestExists(uint256 subId) external view returns (bool);

  /**
   * @notice Paginate through all active VRF subscriptions.
   * @param startIndex index of the subscription to start from
   * @param maxCount maximum number of subscriptions to return, 0 to return all
   * @dev the order of IDs in the list is **not guaranteed**, therefore, if making successive calls, one
   * @dev should consider keeping the blockheight constant to ensure a holistic picture of the contract state
   */
  function getActiveSubscriptionIds(uint256 startIndex, uint256 maxCount) external view returns (uint256[] memory);

  /**
   * @notice Fund a subscription with native.
   * @param subId - ID of the subscription
   * @notice This method expects msg.value to be greater than or equal to 0.
   */
  function fundSubscriptionWithNative(uint256 subId) external payable;
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.15;

/// @notice: IMPORTANT NOTICE for anyone who wants to use this contract
/// @notice Source: https://github.com/ethereum-optimism/optimism/blob/71b93116738ee98c9f8713b1a5dfe626ce06c1b2/packages/contracts-bedrock/src/L2/L1Block.sol
/// @notice The original code was trimmed down to include only the necessary interface elements required to interact with GasPriceOracle
/// @notice We need this file so that Solidity compiler will not complain because some functions don't exist
/// @notice In reality, we don't embed this code into our own contracts, instead we make cross-contract calls on predeployed GasPriceOracle contract

import {ISemver} from "../universal/ISemver.sol";
import {Constants} from "../libraries/Constants.sol";
import {GasPayingToken, IGasToken} from "../libraries/GasPayingToken.sol";
import "../libraries/L1BlockErrors.sol";

/// @custom:proxied
/// @custom:predeploy 0x4200000000000000000000000000000000000015
/// @title L1Block
/// @notice The L1Block predeploy gives users access to information about the last known L1 block.
///         Values within this contract are updated once per epoch (every L1 block) and can only be
///         set by the "depositor" account, a special system address. Depositor account transactions
///         are created by the protocol whenever we move to a new epoch.
contract L1Block is ISemver, IGasToken {
  /// @notice Event emitted when the gas paying token is set.
  event GasPayingTokenSet(address indexed token, uint8 indexed decimals, bytes32 name, bytes32 symbol);

  /// @notice Address of the special depositor account.
  function DEPOSITOR_ACCOUNT() public pure returns (address addr_) {
    addr_ = Constants.DEPOSITOR_ACCOUNT;
  }

  /// @notice The latest L1 block number known by the L2 system.
  uint64 public number;

  /// @notice The latest L1 timestamp known by the L2 system.
  uint64 public timestamp;

  /// @notice The latest L1 base fee.
  uint256 public basefee;

  /// @notice The latest L1 blockhash.
  bytes32 public hash;

  /// @notice The number of L2 blocks in the same epoch.
  uint64 public sequenceNumber;

  /// @notice The scalar value applied to the L1 blob base fee portion of the blob-capable L1 cost func.
  uint32 public blobBaseFeeScalar;

  /// @notice The scalar value applied to the L1 base fee portion of the blob-capable L1 cost func.
  uint32 public baseFeeScalar;

  /// @notice The versioned hash to authenticate the batcher by.
  bytes32 public batcherHash;

  /// @notice The overhead value applied to the L1 portion of the transaction fee.
  /// @custom:legacy
  uint256 public l1FeeOverhead;

  /// @notice The scalar value applied to the L1 portion of the transaction fee.
  /// @custom:legacy
  uint256 public l1FeeScalar;

  /// @notice The latest L1 blob base fee.
  uint256 public blobBaseFee;

  /// @custom:semver 1.4.1-beta.1
  function version() public pure virtual returns (string memory) {
    return "1.4.1-beta.1";
  }

  /// @notice Returns the gas paying token, its decimals, name and symbol.
  ///         If nothing is set in state, then it means ether is used.
  function gasPayingToken() public view returns (address addr_, uint8 decimals_) {
    (addr_, decimals_) = GasPayingToken.getToken();
  }

  /// @notice Returns the gas paying token name.
  ///         If nothing is set in state, then it means ether is used.
  function gasPayingTokenName() public view returns (string memory name_) {
    name_ = GasPayingToken.getName();
  }

  /// @notice Returns the gas paying token symbol.
  ///         If nothing is set in state, then it means ether is used.
  function gasPayingTokenSymbol() public view returns (string memory symbol_) {
    symbol_ = GasPayingToken.getSymbol();
  }

  /// @notice Getter for custom gas token paying networks. Returns true if the
  ///         network uses a custom gas token.
  function isCustomGasToken() public view returns (bool) {
    (address token, ) = gasPayingToken();
    return token != Constants.ETHER;
  }

  /// @custom:legacy
  /// @notice Updates the L1 block values.
  /// @param _number         L1 blocknumber.
  /// @param _timestamp      L1 timestamp.
  /// @param _basefee        L1 basefee.
  /// @param _hash           L1 blockhash.
  /// @param _sequenceNumber Number of L2 blocks since epoch start.
  /// @param _batcherHash    Versioned hash to authenticate batcher by.
  /// @param _l1FeeOverhead  L1 fee overhead.
  /// @param _l1FeeScalar    L1 fee scalar.
  function setL1BlockValues(
    uint64 _number,
    uint64 _timestamp,
    uint256 _basefee,
    bytes32 _hash,
    uint64 _sequenceNumber,
    bytes32 _batcherHash,
    uint256 _l1FeeOverhead,
    uint256 _l1FeeScalar
  ) external {
    require(msg.sender == DEPOSITOR_ACCOUNT(), "L1Block: only the depositor account can set L1 block values");

    number = _number;
    timestamp = _timestamp;
    basefee = _basefee;
    hash = _hash;
    sequenceNumber = _sequenceNumber;
    batcherHash = _batcherHash;
    l1FeeOverhead = _l1FeeOverhead;
    l1FeeScalar = _l1FeeScalar;
  }

  /// @notice Updates the L1 block values for an Ecotone upgraded chain.
  /// Params are packed and passed in as raw msg.data instead of ABI to reduce calldata size.
  /// Params are expected to be in the following order:
  ///   1. _baseFeeScalar      L1 base fee scalar
  ///   2. _blobBaseFeeScalar  L1 blob base fee scalar
  ///   3. _sequenceNumber     Number of L2 blocks since epoch start.
  ///   4. _timestamp          L1 timestamp.
  ///   5. _number             L1 blocknumber.
  ///   6. _basefee            L1 base fee.
  ///   7. _blobBaseFee        L1 blob base fee.
  ///   8. _hash               L1 blockhash.
  ///   9. _batcherHash        Versioned hash to authenticate batcher by.
  function setL1BlockValuesEcotone() external {
    address depositor = DEPOSITOR_ACCOUNT();
    assembly {
      // Revert if the caller is not the depositor account.
      if xor(caller(), depositor) {
        mstore(0x00, 0x3cc50b45) // 0x3cc50b45 is the 4-byte selector of "NotDepositor()"
        revert(0x1C, 0x04) // returns the stored 4-byte selector from above
      }
      // sequencenum (uint64), blobBaseFeeScalar (uint32), baseFeeScalar (uint32)
      sstore(sequenceNumber.slot, shr(128, calldataload(4)))
      // number (uint64) and timestamp (uint64)
      sstore(number.slot, shr(128, calldataload(20)))
      sstore(basefee.slot, calldataload(36)) // uint256
      sstore(blobBaseFee.slot, calldataload(68)) // uint256
      sstore(hash.slot, calldataload(100)) // bytes32
      sstore(batcherHash.slot, calldataload(132)) // bytes32
    }
  }

  /// @notice Sets the gas paying token for the L2 system. Can only be called by the special
  ///         depositor account. This function is not called on every L2 block but instead
  ///         only called by specially crafted L1 deposit transactions.
  function setGasPayingToken(address _token, uint8 _decimals, bytes32 _name, bytes32 _symbol) external {
    if (msg.sender != DEPOSITOR_ACCOUNT()) revert NotDepositor();

    GasPayingToken.set({_token: _token, _decimals: _decimals, _name: _name, _symbol: _symbol});

    emit GasPayingTokenSet({token: _token, decimals: _decimals, name: _name, symbol: _symbol});
  }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

/// @notice: IMPORTANT NOTICE for anyone who wants to use this contract
/// @notice Source: https://github.com/ethereum-optimism/optimism/blob/71b93116738ee98c9f8713b1a5dfe626ce06c1b2/packages/contracts-bedrock/src/libraries/L1BlockErrors.sol
/// @notice The original code was trimmed down to include only the necessary interface elements required to interact with GasPriceOracle
/// @notice We need this file so that Solidity compiler will not complain because some functions don't exist
/// @notice In reality, we don't embed this code into our own contracts, instead we make cross-contract calls on predeployed GasPriceOracle contract

/// @notice Error returns when a non-depositor account tries to set L1 block values.
error NotDepositor();

/// @notice Error when a chain ID is not in the interop dependency set.
error NotDependency();

/// @notice Error when the interop dependency set size is too large.
error DependencySetSizeTooLarge();

/// @notice Error when a chain ID already in the interop dependency set is attempted to be added.
error AlreadyDependency();

/// @notice Error when the chain's chain ID is attempted to be removed from the interop dependency set.
error CantRemovedDependency();

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.4;

/// @notice: IMPORTANT NOTICE for anyone who wants to use this contract
/// @notice Source: https://github.com/transmissions11/solmate/blob/97bdb2003b70382996a79a406813f76417b1cf90/src/utils/LibString.sol
/// @notice The original code was trimmed down to include only the necessary interface elements required to interact with GasPriceOracle
/// @notice We need this file so that Solidity compiler will not complain because some functions don't exist
/// @notice In reality, we don't embed this code into our own contracts, instead we make cross-contract calls on predeployed GasPriceOracle contract

/// @notice Library for converting numbers into strings and other string operations.
/// @author Solady (https://github.com/vectorized/solady/blob/main/src/utils/LibString.sol)
/// @author Modified from Solmate (https://github.com/transmissions11/solmate/blob/main/src/utils/LibString.sol)
///
/// Note:
/// For performance and bytecode compactness, most of the string operations are restricted to
/// byte strings (7-bit ASCII), except where otherwise specified.
/// Usage of byte string operations on charsets with runes spanning two or more bytes
/// can lead to undefined behavior.
library LibString {
  /// @dev Returns a string from a small bytes32 string.
  /// `s` must be null-terminated, or behavior will be undefined.
  function fromSmallString(bytes32 s) internal pure returns (string memory result) {
    /// @solidity memory-safe-assembly
    assembly {
      result := mload(0x40)
      let n := 0
      for {

      } byte(n, s) {
        n := add(n, 1)
      } {

      } // Scan for '\0'.
      mstore(result, n)
      let o := add(result, 0x20)
      mstore(o, s)
      mstore(add(o, n), 0)
      mstore(0x40, add(result, 0x40))
    }
  }

  /// @dev Returns the string as a normalized null-terminated small string.
  function toSmallString(string memory s) internal pure returns (bytes32 result) {
    /// @solidity memory-safe-assembly
    assembly {
      result := mload(s)
      if iszero(lt(result, 33)) {
        mstore(0x00, 0xec92f9a3) // `TooBigForSmallString()`.
        revert(0x1c, 0x04)
      }
      result := shl(shl(3, sub(32, result)), mload(add(s, result)))
    }
  }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.4;

/// @notice: IMPORTANT NOTICE for anyone who wants to use this contract
/// @notice Source: https://github.com/Vectorized/solady/blob/3e8031b16417154dc2beae71b7b45f415d29566b/src/utils/LibZip.sol
/// @notice The original code was trimmed down to include only the necessary interface elements required to interact with GasPriceOracle
/// @notice We need this file so that Solidity compiler will not complain because some functions don't exist
/// @notice In reality, we don't embed this code into our own contracts, instead we make cross-contract calls on predeployed GasPriceOracle contract

/// @notice Library for compressing and decompressing bytes.
/// @author Solady (https://github.com/vectorized/solady/blob/main/src/utils/LibZip.sol)
/// @author Calldata compression by clabby (https://github.com/clabby/op-kompressor)
/// @author FastLZ by ariya (https://github.com/ariya/FastLZ)
///
/// @dev Note:
/// The accompanying solady.js library includes implementations of
/// FastLZ and calldata operations for convenience.
library LibZip {
    /// @dev Returns the compressed `data`.
    function flzCompress(bytes memory data) internal pure returns (bytes memory result) {
        /// @solidity memory-safe-assembly
        assembly {
            function ms8(d_, v_) -> _d {
                mstore8(d_, v_)
                _d := add(d_, 1)
            }
            function u24(p_) -> _u {
                let w := mload(p_)
                _u := or(shl(16, byte(2, w)), or(shl(8, byte(1, w)), byte(0, w)))
            }
            function cmp(p_, q_, e_) -> _l {
                for { e_ := sub(e_, q_) } lt(_l, e_) { _l := add(_l, 1) } {
                    e_ := mul(iszero(byte(0, xor(mload(add(p_, _l)), mload(add(q_, _l))))), e_)
                }
            }
            function literals(runs_, src_, dest_) -> _o {
                for { _o := dest_ } iszero(lt(runs_, 0x20)) { runs_ := sub(runs_, 0x20) } {
                    mstore(ms8(_o, 31), mload(src_))
                    _o := add(_o, 0x21)
                    src_ := add(src_, 0x20)
                }
                if iszero(runs_) { leave }
                mstore(ms8(_o, sub(runs_, 1)), mload(src_))
                _o := add(1, add(_o, runs_))
            }
            function match(l_, d_, o_) -> _o {
                for { d_ := sub(d_, 1) } iszero(lt(l_, 263)) { l_ := sub(l_, 262) } {
                    o_ := ms8(ms8(ms8(o_, add(224, shr(8, d_))), 253), and(0xff, d_))
                }
                if iszero(lt(l_, 7)) {
                    _o := ms8(ms8(ms8(o_, add(224, shr(8, d_))), sub(l_, 7)), and(0xff, d_))
                    leave
                }
                _o := ms8(ms8(o_, add(shl(5, l_), shr(8, d_))), and(0xff, d_))
            }
            function setHash(i_, v_) {
                let p := add(mload(0x40), shl(2, i_))
                mstore(p, xor(mload(p), shl(224, xor(shr(224, mload(p)), v_))))
            }
            function getHash(i_) -> _h {
                _h := shr(224, mload(add(mload(0x40), shl(2, i_))))
            }
            function hash(v_) -> _r {
                _r := and(shr(19, mul(2654435769, v_)), 0x1fff)
            }
            function setNextHash(ip_, ipStart_) -> _ip {
                setHash(hash(u24(ip_)), sub(ip_, ipStart_))
                _ip := add(ip_, 1)
            }
            codecopy(mload(0x40), codesize(), 0x8000) // Zeroize the hashmap.
            let op := add(mload(0x40), 0x8000)
            let a := add(data, 0x20)
            let ipStart := a
            let ipLimit := sub(add(ipStart, mload(data)), 13)
            for { let ip := add(2, a) } lt(ip, ipLimit) {} {
                let r := 0
                let d := 0
                for {} 1 {} {
                    let s := u24(ip)
                    let h := hash(s)
                    r := add(ipStart, getHash(h))
                    setHash(h, sub(ip, ipStart))
                    d := sub(ip, r)
                    if iszero(lt(ip, ipLimit)) { break }
                    ip := add(ip, 1)
                    if iszero(gt(d, 0x1fff)) { if eq(s, u24(r)) { break } }
                }
                if iszero(lt(ip, ipLimit)) { break }
                ip := sub(ip, 1)
                if gt(ip, a) { op := literals(sub(ip, a), a, op) }
                let l := cmp(add(r, 3), add(ip, 3), add(ipLimit, 9))
                op := match(l, d, op)
                ip := setNextHash(setNextHash(add(ip, l), ipStart), ipStart)
                a := ip
            }
            op := literals(sub(add(ipStart, mload(data)), a), a, op)
            result := mload(0x40)
            let t := add(result, 0x8000)
            let n := sub(op, t)
            mstore(result, n) // Store the length.
            // Copy the result to compact the memory, overwriting the hashmap.
            let o := add(result, 0x20)
            for { let i } lt(i, n) { i := add(i, 0x20) } { mstore(add(o, i), mload(add(t, i))) }
            mstore(add(o, n), 0) // Zeroize the slot after the string.
            mstore(0x40, add(add(o, n), 0x20)) // Allocate the memory.
        }
    }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

// solhint-disable-next-line interface-starts-with-i
interface LinkTokenInterface {
  function allowance(address owner, address spender) external view returns (uint256 remaining);

  function approve(address spender, uint256 value) external returns (bool success);

  function balanceOf(address owner) external view returns (uint256 balance);

  function decimals() external view returns (uint8 decimalPlaces);

  function decreaseApproval(address spender, uint256 addedValue) external returns (bool success);

  function increaseApproval(address spender, uint256 subtractedValue) external;

  function name() external view returns (string memory tokenName);

  function symbol() external view returns (string memory tokenSymbol);

  function totalSupply() external view returns (uint256 totalTokensIssued);

  function transfer(address to, uint256 value) external returns (bool success);

  function transferAndCall(address to, uint256 value, bytes calldata data) external returns (bool success);

  function transferFrom(address from, address to, uint256 value) external returns (bool success);
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.19;

import {ConfirmedOwner} from "../../shared/access/ConfirmedOwner.sol";
import {GasPriceOracle as OVM_GasPriceOracle} from "../../vendor/@eth-optimism/contracts-bedrock/v0.17.3/src/L2/GasPriceOracle.sol";

/// @dev An abstract contract that provides Optimism specific L1 fee calculations.
// solhint-disable-next-line contract-name-camelcase
abstract contract OptimismL1Fees is ConfirmedOwner {
  /// @dev This is the padding size for unsigned RLP-encoded transaction without the signature data
  /// @dev The padding size was estimated based on hypothetical max RLP-encoded transaction size
  uint256 internal constant L1_UNSIGNED_RLP_ENC_TX_DATA_BYTES_SIZE = 71;
  /// @dev Signature data size used in the GasPriceOracle predeploy
  /// @dev reference: https://github.com/ethereum-optimism/optimism/blob/a96cbe7c8da144d79d4cec1303d8ae60a64e681e/packages/contracts-bedrock/contracts/L2/GasPriceOracle.sol#L145
  uint256 internal constant L1_TX_SIGNATURE_DATA_BYTES_SIZE = 68;
  /// @dev L1_FEE_DATA_PADDING includes 71 bytes for L1 data padding for Optimism
  bytes internal constant L1_FEE_DATA_PADDING =
    hex"ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff";
  /// @dev OVM_GASPRICEORACLE_ADDR is the address of the OVM_GasPriceOracle precompile on Optimism.
  /// @dev reference: https://community.optimism.io/docs/developers/build/transaction-fees/#estimating-the-l1-data-fee
  address private constant OVM_GASPRICEORACLE_ADDR = address(0x420000000000000000000000000000000000000F);
  OVM_GasPriceOracle private constant OVM_GASPRICEORACLE = OVM_GasPriceOracle(OVM_GASPRICEORACLE_ADDR);

  /// @dev Option 1: getL1Fee() function from predeploy GasPriceOracle contract with the fulfillment calldata payload
  /// @dev This option is only available for the Coordinator contract
  uint8 internal constant L1_GAS_FEES_MODE = 0;
  /// @dev Option 2: our own implementation of getL1Fee() function (Ecotone version) with projected
  /// @dev fulfillment calldata payload (number of non-zero bytes estimated based on historical data)
  /// @dev This option is available for the Coordinator and the Wrapper contract
  uint8 internal constant L1_CALLDATA_GAS_COST_MODE = 1;
  /// @dev Option 3: getL1FeeUpperBound() function from predeploy GasPriceOracle contract (available after Fjord upgrade)
  /// @dev This option is available for the Coordinator and the Wrapper contract
  uint8 internal constant L1_GAS_FEES_UPPER_BOUND_MODE = 2;

  uint8 public s_l1FeeCalculationMode = L1_GAS_FEES_MODE;

  /// @dev L1 fee coefficient can be applied to options 2 or 3 to reduce possibly inflated gas price
  uint8 public s_l1FeeCoefficient = 100;

  error InvalidL1FeeCalculationMode(uint8 mode);
  error InvalidL1FeeCoefficient(uint8 coefficient);

  event L1FeeCalculationSet(uint8 mode, uint8 coefficient);

  function setL1FeeCalculation(uint8 mode, uint8 coefficient) external virtual onlyOwner {
    _setL1FeeCalculationInternal(mode, coefficient);
  }

  function _setL1FeeCalculationInternal(uint8 mode, uint8 coefficient) internal {
    if (mode >= 3) {
      revert InvalidL1FeeCalculationMode(mode);
    }
    if (coefficient == 0 || coefficient > 100) {
      revert InvalidL1FeeCoefficient(coefficient);
    }

    s_l1FeeCalculationMode = mode;
    s_l1FeeCoefficient = coefficient;

    emit L1FeeCalculationSet(mode, coefficient);
  }

  function _getL1CostWeiForCalldata(bytes calldata data) internal view returns (uint256) {
    if (s_l1FeeCalculationMode == L1_GAS_FEES_MODE) {
      return OVM_GASPRICEORACLE.getL1Fee(bytes.concat(data, L1_FEE_DATA_PADDING));
    }
    return _getL1CostWeiForCalldataSize(data.length);
  }

  function _getL1CostWeiForCalldataSize(uint256 calldataSizeBytes) internal view returns (uint256) {
    uint8 l1FeeCalculationMode = s_l1FeeCalculationMode;
    if (l1FeeCalculationMode == L1_CALLDATA_GAS_COST_MODE) {
      // estimate based on unsigned fully RLP-encoded transaction size so we have to account for paddding bytes as well
      return
        (s_l1FeeCoefficient * _calculateOptimismL1DataFee(calldataSizeBytes + L1_UNSIGNED_RLP_ENC_TX_DATA_BYTES_SIZE)) /
        100;
    } else if (l1FeeCalculationMode == L1_GAS_FEES_UPPER_BOUND_MODE) {
      // getL1FeeUpperBound expects unsigned fully RLP-encoded transaction size so we have to account for paddding bytes as well
      return
        (s_l1FeeCoefficient *
          OVM_GASPRICEORACLE.getL1FeeUpperBound(calldataSizeBytes + L1_UNSIGNED_RLP_ENC_TX_DATA_BYTES_SIZE)) / 100;
    }
    revert InvalidL1FeeCalculationMode(l1FeeCalculationMode);
  }

  function _calculateOptimismL1DataFee(uint256 calldataSizeBytes) internal view returns (uint256) {
    // reference: https://docs.optimism.io/stack/transactions/fees#ecotone
    // also: https://github.com/ethereum-optimism/specs/blob/main/specs/protocol/exec-engine.md#ecotone-l1-cost-fee-changes-eip-4844-da
    // we treat all bytes in the calldata payload as non-zero bytes (cost: 16 gas) because accurate estimation is too expensive
    // we also have to account for the signature data size
    uint256 l1GasUsed = (calldataSizeBytes + L1_TX_SIGNATURE_DATA_BYTES_SIZE) * 16;
    uint256 scaledBaseFee = OVM_GASPRICEORACLE.baseFeeScalar() * 16 * OVM_GASPRICEORACLE.l1BaseFee();
    uint256 scaledBlobBaseFee = OVM_GASPRICEORACLE.blobBaseFeeScalar() * OVM_GASPRICEORACLE.blobBaseFee();
    uint256 fee = l1GasUsed * (scaledBaseFee + scaledBlobBaseFee);
    return fee / (16 * 10 ** OVM_GASPRICEORACLE.decimals());
  }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

/// @notice: IMPORTANT NOTICE for anyone who wants to use this contract
/// @notice Source: https://github.com/ethereum-optimism/optimism/blob/71b93116738ee98c9f8713b1a5dfe626ce06c1b2/packages/contracts-bedrock/src/libraries/Predeploys.sol
/// @notice The original code was trimmed down to include only the necessary interface elements required to interact with GasPriceOracle
/// @notice We need this file so that Solidity compiler will not complain because some functions don't exist
/// @notice In reality, we don't embed this code into our own contracts, instead we make cross-contract calls on predeployed GasPriceOracle contract

/// @title Predeploys
/// @notice Contains constant addresses for protocol contracts that are pre-deployed to the L2 system.
//          This excludes the preinstalls (non-protocol contracts).
library Predeploys {
  /// @notice Number of predeploy-namespace addresses reserved for protocol usage.
  uint256 internal constant PREDEPLOY_COUNT = 2048;

  /// @custom:legacy
  /// @notice Address of the LegacyMessagePasser predeploy. Deprecate. Use the updated
  ///         L2ToL1MessagePasser contract instead.
  address internal constant LEGACY_MESSAGE_PASSER = 0x4200000000000000000000000000000000000000;

  /// @custom:legacy
  /// @notice Address of the L1MessageSender predeploy. Deprecated. Use L2CrossDomainMessenger
  ///         or access tx.origin (or msg.sender) in a L1 to L2 transaction instead.
  ///         Not embedded into new OP-Stack chains.
  address internal constant L1_MESSAGE_SENDER = 0x4200000000000000000000000000000000000001;

  /// @custom:legacy
  /// @notice Address of the DeployerWhitelist predeploy. No longer active.
  address internal constant DEPLOYER_WHITELIST = 0x4200000000000000000000000000000000000002;

  /// @notice Address of the canonical WETH contract.
  address internal constant WETH = 0x4200000000000000000000000000000000000006;

  /// @notice Address of the L2CrossDomainMessenger predeploy.
  address internal constant L2_CROSS_DOMAIN_MESSENGER = 0x4200000000000000000000000000000000000007;

  /// @notice Address of the GasPriceOracle predeploy. Includes fee information
  ///         and helpers for computing the L1 portion of the transaction fee.
  address internal constant GAS_PRICE_ORACLE = 0x420000000000000000000000000000000000000F;

  /// @notice Address of the L2StandardBridge predeploy.
  address internal constant L2_STANDARD_BRIDGE = 0x4200000000000000000000000000000000000010;

  //// @notice Address of the SequencerFeeWallet predeploy.
  address internal constant SEQUENCER_FEE_WALLET = 0x4200000000000000000000000000000000000011;

  /// @notice Address of the OptimismMintableERC20Factory predeploy.
  address internal constant OPTIMISM_MINTABLE_ERC20_FACTORY = 0x4200000000000000000000000000000000000012;

  /// @custom:legacy
  /// @notice Address of the L1BlockNumber predeploy. Deprecated. Use the L1Block predeploy
  ///         instead, which exposes more information about the L1 state.
  address internal constant L1_BLOCK_NUMBER = 0x4200000000000000000000000000000000000013;

  /// @notice Address of the L2ERC721Bridge predeploy.
  address internal constant L2_ERC721_BRIDGE = 0x4200000000000000000000000000000000000014;

  /// @notice Address of the L1Block predeploy.
  address internal constant L1_BLOCK_ATTRIBUTES = 0x4200000000000000000000000000000000000015;

  /// @notice Address of the L2ToL1MessagePasser predeploy.
  address internal constant L2_TO_L1_MESSAGE_PASSER = 0x4200000000000000000000000000000000000016;

  /// @notice Address of the OptimismMintableERC721Factory predeploy.
  address internal constant OPTIMISM_MINTABLE_ERC721_FACTORY = 0x4200000000000000000000000000000000000017;

  /// @notice Address of the ProxyAdmin predeploy.
  address internal constant PROXY_ADMIN = 0x4200000000000000000000000000000000000018;

  /// @notice Address of the BaseFeeVault predeploy.
  address internal constant BASE_FEE_VAULT = 0x4200000000000000000000000000000000000019;

  /// @notice Address of the L1FeeVault predeploy.
  address internal constant L1_FEE_VAULT = 0x420000000000000000000000000000000000001A;

  /// @notice Address of the SchemaRegistry predeploy.
  address internal constant SCHEMA_REGISTRY = 0x4200000000000000000000000000000000000020;

  /// @notice Address of the EAS predeploy.
  address internal constant EAS = 0x4200000000000000000000000000000000000021;

  /// @notice Address of the GovernanceToken predeploy.
  address internal constant GOVERNANCE_TOKEN = 0x4200000000000000000000000000000000000042;

  /// @custom:legacy
  /// @notice Address of the LegacyERC20ETH predeploy. Deprecated. Balances are migrated to the
  ///         state trie as of the Bedrock upgrade. Contract has been locked and write functions
  ///         can no longer be accessed.
  address internal constant LEGACY_ERC20_ETH = 0xDeadDeAddeAddEAddeadDEaDDEAdDeaDDeAD0000;

  /// @notice Address of the CrossL2Inbox predeploy.
  address internal constant CROSS_L2_INBOX = 0x4200000000000000000000000000000000000022;

  /// @notice Address of the L2ToL2CrossDomainMessenger predeploy.
  address internal constant L2_TO_L2_CROSS_DOMAIN_MESSENGER = 0x4200000000000000000000000000000000000023;

  /// @notice Returns the name of the predeploy at the given address.
  function getName(address _addr) internal pure returns (string memory out_) {
    require(isPredeployNamespace(_addr), "Predeploys: address must be a predeploy");
    if (_addr == LEGACY_MESSAGE_PASSER) return "LegacyMessagePasser";
    if (_addr == L1_MESSAGE_SENDER) return "L1MessageSender";
    if (_addr == DEPLOYER_WHITELIST) return "DeployerWhitelist";
    if (_addr == WETH) return "WETH";
    if (_addr == L2_CROSS_DOMAIN_MESSENGER) return "L2CrossDomainMessenger";
    if (_addr == GAS_PRICE_ORACLE) return "GasPriceOracle";
    if (_addr == L2_STANDARD_BRIDGE) return "L2StandardBridge";
    if (_addr == SEQUENCER_FEE_WALLET) return "SequencerFeeVault";
    if (_addr == OPTIMISM_MINTABLE_ERC20_FACTORY) return "OptimismMintableERC20Factory";
    if (_addr == L1_BLOCK_NUMBER) return "L1BlockNumber";
    if (_addr == L2_ERC721_BRIDGE) return "L2ERC721Bridge";
    if (_addr == L1_BLOCK_ATTRIBUTES) return "L1Block";
    if (_addr == L2_TO_L1_MESSAGE_PASSER) return "L2ToL1MessagePasser";
    if (_addr == OPTIMISM_MINTABLE_ERC721_FACTORY) return "OptimismMintableERC721Factory";
    if (_addr == PROXY_ADMIN) return "ProxyAdmin";
    if (_addr == BASE_FEE_VAULT) return "BaseFeeVault";
    if (_addr == L1_FEE_VAULT) return "L1FeeVault";
    if (_addr == SCHEMA_REGISTRY) return "SchemaRegistry";
    if (_addr == EAS) return "EAS";
    if (_addr == GOVERNANCE_TOKEN) return "GovernanceToken";
    if (_addr == LEGACY_ERC20_ETH) return "LegacyERC20ETH";
    if (_addr == CROSS_L2_INBOX) return "CrossL2Inbox";
    if (_addr == L2_TO_L2_CROSS_DOMAIN_MESSENGER) return "L2ToL2CrossDomainMessenger";
    revert("Predeploys: unnamed predeploy");
  }

  /// @notice Returns true if the predeploy is not proxied.
  function notProxied(address _addr) internal pure returns (bool) {
    return _addr == GOVERNANCE_TOKEN || _addr == WETH;
  }

  /// @notice Returns true if the address is a defined predeploy that is embedded into new OP-Stack chains.
  function isSupportedPredeploy(address _addr, bool _useInterop) internal pure returns (bool) {
    return
      _addr == LEGACY_MESSAGE_PASSER ||
      _addr == DEPLOYER_WHITELIST ||
      _addr == WETH ||
      _addr == L2_CROSS_DOMAIN_MESSENGER ||
      _addr == GAS_PRICE_ORACLE ||
      _addr == L2_STANDARD_BRIDGE ||
      _addr == SEQUENCER_FEE_WALLET ||
      _addr == OPTIMISM_MINTABLE_ERC20_FACTORY ||
      _addr == L1_BLOCK_NUMBER ||
      _addr == L2_ERC721_BRIDGE ||
      _addr == L1_BLOCK_ATTRIBUTES ||
      _addr == L2_TO_L1_MESSAGE_PASSER ||
      _addr == OPTIMISM_MINTABLE_ERC721_FACTORY ||
      _addr == PROXY_ADMIN ||
      _addr == BASE_FEE_VAULT ||
      _addr == L1_FEE_VAULT ||
      _addr == SCHEMA_REGISTRY ||
      _addr == EAS ||
      _addr == GOVERNANCE_TOKEN ||
      (_useInterop && _addr == CROSS_L2_INBOX) ||
      (_useInterop && _addr == L2_TO_L2_CROSS_DOMAIN_MESSENGER);
  }

  function isPredeployNamespace(address _addr) internal pure returns (bool) {
    return uint160(_addr) >> 11 == uint160(0x4200000000000000000000000000000000000000) >> 11;
  }

  /// @notice Function to compute the expected address of the predeploy implementation
  ///         in the genesis state.
  function predeployToCodeNamespace(address _addr) internal pure returns (address) {
    require(isPredeployNamespace(_addr), "Predeploys: can only derive code-namespace address for predeploy addresses");
    return
      address(
        uint160((uint256(uint160(_addr)) & 0xffff) | uint256(uint160(0xc0D3C0d3C0d3C0D3c0d3C0d3c0D3C0d3c0d30000)))
      );
  }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

/// @notice: IMPORTANT NOTICE for anyone who wants to use this contract
/// @notice Source: https://github.com/ethereum-optimism/optimism/blob/71b93116738ee98c9f8713b1a5dfe626ce06c1b2/packages/contracts-bedrock/src/libraries/Storage.sol
/// @notice The original code was trimmed down to include only the necessary interface elements required to interact with GasPriceOracle
/// @notice We need this file so that Solidity compiler will not complain because some functions don't exist
/// @notice In reality, we don't embed this code into our own contracts, instead we make cross-contract calls on predeployed GasPriceOracle contract

/// @title Storage
/// @notice Storage handles reading and writing to arbitary storage locations
library Storage {
  /// @notice Returns an address stored in an arbitrary storage slot.
  ///         These storage slots decouple the storage layout from
  ///         solc's automation.
  /// @param _slot The storage slot to retrieve the address from.
  function getAddress(bytes32 _slot) internal view returns (address addr_) {
    assembly {
      addr_ := sload(_slot)
    }
  }

  /// @notice Stores an address in an arbitrary storage slot, `_slot`.
  /// @param _slot The storage slot to store the address in.
  /// @param _address The protocol version to store
  /// @dev WARNING! This function must be used cautiously, as it allows for overwriting addresses
  ///      in arbitrary storage slots.
  function setAddress(bytes32 _slot, address _address) internal {
    assembly {
      sstore(_slot, _address)
    }
  }

  /// @notice Returns a uint256 stored in an arbitrary storage slot.
  ///         These storage slots decouple the storage layout from
  ///         solc's automation.
  /// @param _slot The storage slot to retrieve the address from.
  function getUint(bytes32 _slot) internal view returns (uint256 value_) {
    assembly {
      value_ := sload(_slot)
    }
  }

  /// @notice Stores a value in an arbitrary storage slot, `_slot`.
  /// @param _slot The storage slot to store the address in.
  /// @param _value The protocol version to store
  /// @dev WARNING! This function must be used cautiously, as it allows for overwriting values
  ///      in arbitrary storage slots.
  function setUint(bytes32 _slot, uint256 _value) internal {
    assembly {
      sstore(_slot, _value)
    }
  }

  /// @notice Returns a bytes32 stored in an arbitrary storage slot.
  ///         These storage slots decouple the storage layout from
  ///         solc's automation.
  /// @param _slot The storage slot to retrieve the address from.
  function getBytes32(bytes32 _slot) internal view returns (bytes32 value_) {
    assembly {
      value_ := sload(_slot)
    }
  }

  /// @notice Stores a bytes32 value in an arbitrary storage slot, `_slot`.
  /// @param _slot The storage slot to store the address in.
  /// @param _value The bytes32 value to store.
  /// @dev WARNING! This function must be used cautiously, as it allows for overwriting values
  ///      in arbitrary storage slots.
  function setBytes32(bytes32 _slot, bytes32 _value) internal {
    assembly {
      sstore(_slot, _value)
    }
  }

  /// @notice Stores a bool value in an arbitrary storage slot, `_slot`.
  /// @param _slot The storage slot to store the bool in.
  /// @param _value The bool value to store
  /// @dev WARNING! This function must be used cautiously, as it allows for overwriting values
  ///      in arbitrary storage slots.
  function setBool(bytes32 _slot, bool _value) internal {
    assembly {
      sstore(_slot, _value)
    }
  }

  /// @notice Returns a bool stored in an arbitrary storage slot.
  /// @param _slot The storage slot to retrieve the bool from.
  function getBool(bytes32 _slot) internal view returns (bool value_) {
    assembly {
      value_ := sload(_slot)
    }
  }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.4;

import {EnumerableSet} from "../../vendor/openzeppelin-solidity/v4.7.3/contracts/utils/structs/EnumerableSet.sol";
import {LinkTokenInterface} from "../../shared/interfaces/LinkTokenInterface.sol";
import {ConfirmedOwner} from "../../shared/access/ConfirmedOwner.sol";
import {AggregatorV3Interface} from "../../shared/interfaces/AggregatorV3Interface.sol";
import {IERC677Receiver} from "../../shared/interfaces/IERC677Receiver.sol";
import {IVRFSubscriptionV2Plus} from "./interfaces/IVRFSubscriptionV2Plus.sol";

abstract contract SubscriptionAPI is ConfirmedOwner, IERC677Receiver, IVRFSubscriptionV2Plus {
  using EnumerableSet for EnumerableSet.UintSet;

  /// @dev may not be provided upon construction on some chains due to lack of availability
  LinkTokenInterface public LINK;
  /// @dev may not be provided upon construction on some chains due to lack of availability
  AggregatorV3Interface public LINK_NATIVE_FEED;

  // We need to maintain a list of consuming addresses.
  // This bound ensures we are able to loop over them as needed.
  // Should a user require more consumers, they can use multiple subscriptions.
  uint16 public constant MAX_CONSUMERS = 100;
  error TooManyConsumers();
  error InsufficientBalance();
  error InvalidConsumer(uint256 subId, address consumer);
  error InvalidSubscription();
  error OnlyCallableFromLink();
  error InvalidCalldata();
  error MustBeSubOwner(address owner);
  error PendingRequestExists();
  error MustBeRequestedOwner(address proposedOwner);
  error BalanceInvariantViolated(uint256 internalBalance, uint256 externalBalance); // Should never happen
  event FundsRecovered(address to, uint256 amount);
  event NativeFundsRecovered(address to, uint256 amount);
  error LinkAlreadySet();
  error FailedToSendNative();
  error FailedToTransferLink();
  error IndexOutOfRange();
  error LinkNotSet();

  // We use the subscription struct (1 word)
  // at fulfillment time.
  struct Subscription {
    // There are only 1e9*1e18 = 1e27 juels in existence, so the balance can fit in uint96 (2^96 ~ 7e28)
    uint96 balance; // Common link balance used for all consumer requests.
    // a uint96 is large enough to hold around ~8e28 wei, or 80 billion ether.
    // That should be enough to cover most (if not all) subscriptions.
    uint96 nativeBalance; // Common native balance used for all consumer requests.
    uint64 reqCount;
  }
  // We use the config for the mgmt APIs
  struct SubscriptionConfig {
    address owner; // Owner can fund/withdraw/cancel the sub.
    address requestedOwner; // For safely transferring sub ownership.
    // Maintains the list of keys in s_consumers.
    // We do this for 2 reasons:
    // 1. To be able to clean up all keys from s_consumers when canceling a subscription.
    // 2. To be able to return the list of all consumers in getSubscription.
    // Note that we need the s_consumers map to be able to directly check if a
    // consumer is valid without reading all the consumers from storage.
    address[] consumers;
  }
  struct ConsumerConfig {
    bool active;
    uint64 nonce;
    uint64 pendingReqCount;
  }
  // Note a nonce of 0 indicates the consumer is not assigned to that subscription.
  mapping(address => mapping(uint256 => ConsumerConfig)) /* consumerAddress */ /* subId */ /* consumerConfig */
    internal s_consumers;
  mapping(uint256 => SubscriptionConfig) /* subId */ /* subscriptionConfig */ internal s_subscriptionConfigs;
  mapping(uint256 => Subscription) /* subId */ /* subscription */ internal s_subscriptions;
  // subscription nonce used to construct subId. Rises monotonically
  uint64 public s_currentSubNonce;
  // track all subscription id's that were created by this contract
  // note: access should be through the getActiveSubscriptionIds() view function
  // which takes a starting index and a max number to fetch in order to allow
  // "pagination" of the subscription ids. in the event a very large number of
  // subscription id's are stored in this set, they cannot be retrieved in a
  // single RPC call without violating various size limits.
  EnumerableSet.UintSet internal s_subIds;
  // s_totalBalance tracks the total link sent to/from
  // this contract through onTokenTransfer, cancelSubscription and oracleWithdraw.
  // A discrepancy with this contract's link balance indicates someone
  // sent tokens using transfer and so we may need to use recoverFunds.
  uint96 public s_totalBalance;
  // s_totalNativeBalance tracks the total native sent to/from
  // this contract through fundSubscription, cancelSubscription and oracleWithdrawNative.
  // A discrepancy with this contract's native balance indicates someone
  // sent native using transfer and so we may need to use recoverNativeFunds.
  uint96 public s_totalNativeBalance;
  uint96 internal s_withdrawableTokens;
  uint96 internal s_withdrawableNative;

  event SubscriptionCreated(uint256 indexed subId, address owner);
  event SubscriptionFunded(uint256 indexed subId, uint256 oldBalance, uint256 newBalance);
  event SubscriptionFundedWithNative(uint256 indexed subId, uint256 oldNativeBalance, uint256 newNativeBalance);
  event SubscriptionConsumerAdded(uint256 indexed subId, address consumer);
  event SubscriptionConsumerRemoved(uint256 indexed subId, address consumer);
  event SubscriptionCanceled(uint256 indexed subId, address to, uint256 amountLink, uint256 amountNative);
  event SubscriptionOwnerTransferRequested(uint256 indexed subId, address from, address to);
  event SubscriptionOwnerTransferred(uint256 indexed subId, address from, address to);

  struct Config {
    uint16 minimumRequestConfirmations;
    uint32 maxGasLimit;
    // Reentrancy protection.
    bool reentrancyLock;
    // stalenessSeconds is how long before we consider the feed price to be stale
    // and fallback to fallbackWeiPerUnitLink.
    uint32 stalenessSeconds;
    // Gas to cover oracle payment after we calculate the payment.
    // We make it configurable in case those operations are repriced.
    // The recommended number is below, though it may vary slightly
    // if certain chains do not implement certain EIP's.
    // 21000 + // base cost of the transaction
    // 100 + 5000 + // warm subscription balance read and update. See https://eips.ethereum.org/EIPS/eip-2929
    // 2*2100 + 5000 - // cold read oracle address and oracle balance and first time oracle balance update, note first time will be 20k, but 5k subsequently
    // 4800 + // request delete refund (refunds happen after execution), note pre-london fork was 15k. See https://eips.ethereum.org/EIPS/eip-3529
    // 6685 + // Positive static costs of argument encoding etc. note that it varies by +/- x*12 for every x bytes of non-zero data in the proof.
    // Total: 37,185 gas.
    uint32 gasAfterPaymentCalculation;
    // Flat fee charged per fulfillment in millionths of native.
    // So fee range is [0, 2^32/10^6].
    uint32 fulfillmentFlatFeeNativePPM;
    // Discount relative to fulfillmentFlatFeeNativePPM for link payment in millionths of native
    // Should not exceed fulfillmentFlatFeeNativePPM
    // So fee range is [0, 2^32/10^6].
    uint32 fulfillmentFlatFeeLinkDiscountPPM;
    // nativePremiumPercentage is the percentage of the total gas costs that is added to the final premium for native payment
    // nativePremiumPercentage = 10 means 10% of the total gas costs is added. only integral percentage is allowed
    uint8 nativePremiumPercentage;
    // linkPremiumPercentage is the percentage of total gas costs that is added to the final premium for link payment
    // linkPremiumPercentage = 10 means 10% of the total gas costs is added. only integral percentage is allowed
    uint8 linkPremiumPercentage;
  }
  Config public s_config;

  error Reentrant();
  modifier nonReentrant() {
    _nonReentrant();
    _;
  }

  function _nonReentrant() internal view {
    if (s_config.reentrancyLock) {
      revert Reentrant();
    }
  }

  function _requireSufficientBalance(bool condition) internal pure {
    if (!condition) {
      revert InsufficientBalance();
    }
  }

  function _requireValidSubscription(address subOwner) internal pure {
    if (subOwner == address(0)) {
      revert InvalidSubscription();
    }
  }
  constructor() ConfirmedOwner(msg.sender) {}

  /**
   * @notice set the LINK token contract and link native feed to be
   * used by this coordinator
   * @param link - address of link token
   * @param linkNativeFeed address of the link native feed
   */
  function setLINKAndLINKNativeFeed(address link, address linkNativeFeed) external onlyOwner {
    // Disallow re-setting link token because the logic wouldn't really make sense
    if (address(LINK) != address(0)) {
      revert LinkAlreadySet();
    }
    LINK = LinkTokenInterface(link);
    LINK_NATIVE_FEED = AggregatorV3Interface(linkNativeFeed);
  }

  /**
   * @notice Owner cancel subscription, sends remaining link directly to the subscription owner.
   * @param subId subscription id
   * @dev notably can be called even if there are pending requests, outstanding ones may fail onchain
   */
  function ownerCancelSubscription(uint256 subId) external onlyOwner {
    address subOwner = s_subscriptionConfigs[subId].owner;
    _requireValidSubscription(subOwner);
    _cancelSubscriptionHelper(subId, subOwner);
  }

  /**
   * @notice Recover link sent with transfer instead of transferAndCall.
   * @param to address to send link to
   */
  function recoverFunds(address to) external onlyOwner {
    // If LINK is not set, we cannot recover funds.
    // It is possible that this coordinator address was funded with LINK
    // by accident by a user but the LINK token needs to be set first
    // before we can recover it.
    if (address(LINK) == address(0)) {
      revert LinkNotSet();
    }

    uint256 externalBalance = LINK.balanceOf(address(this));
    uint256 internalBalance = uint256(s_totalBalance);
    if (internalBalance > externalBalance) {
      revert BalanceInvariantViolated(internalBalance, externalBalance);
    }
    if (internalBalance < externalBalance) {
      uint256 amount = externalBalance - internalBalance;
      if (!LINK.transfer(to, amount)) {
        revert FailedToTransferLink();
      }
      emit FundsRecovered(to, amount);
    }
    // If the balances are equal, nothing to be done.
  }

  /**
   * @notice Recover native sent with transfer/call/send instead of fundSubscription.
   * @param to address to send native to
   */
  function recoverNativeFunds(address payable to) external onlyOwner {
    uint256 externalBalance = address(this).balance;
    uint256 internalBalance = uint256(s_totalNativeBalance);
    if (internalBalance > externalBalance) {
      revert BalanceInvariantViolated(internalBalance, externalBalance);
    }
    if (internalBalance < externalBalance) {
      uint256 amount = externalBalance - internalBalance;
      (bool sent, ) = to.call{value: amount}("");
      if (!sent) {
        revert FailedToSendNative();
      }
      emit NativeFundsRecovered(to, amount);
    }
    // If the balances are equal, nothing to be done.
  }

  /*
   * @notice withdraw LINK earned through fulfilling requests
   * @param recipient where to send the funds
   * @param amount amount to withdraw
   */
  function withdraw(address recipient) external nonReentrant onlyOwner {
    if (address(LINK) == address(0)) {
      revert LinkNotSet();
    }
    uint96 amount = s_withdrawableTokens;
    _requireSufficientBalance(amount > 0);
    s_withdrawableTokens = 0;
    s_totalBalance -= amount;
    _requireSufficientBalance(LINK.transfer(recipient, amount));
  }

  /*
   * @notice withdraw native earned through fulfilling requests
   * @param recipient where to send the funds
   * @param amount amount to withdraw
   */
  function withdrawNative(address payable recipient) external nonReentrant onlyOwner {
    uint96 amount = s_withdrawableNative;
    _requireSufficientBalance(amount > 0);
    // Prevent re-entrancy by updating state before transfer.
    s_withdrawableNative = 0;
    s_totalNativeBalance -= amount;
    _mustSendNative(recipient, amount);
  }

  function onTokenTransfer(address /* sender */, uint256 amount, bytes calldata data) external override nonReentrant {
    if (msg.sender != address(LINK)) {
      revert OnlyCallableFromLink();
    }
    if (data.length != 32) {
      revert InvalidCalldata();
    }
    uint256 subId = abi.decode(data, (uint256));
    _requireValidSubscription(s_subscriptionConfigs[subId].owner);
    // We do not check that the sender is the subscription owner,
    // anyone can fund a subscription.
    uint256 oldBalance = s_subscriptions[subId].balance;
    s_subscriptions[subId].balance += uint96(amount);
    s_totalBalance += uint96(amount);
    emit SubscriptionFunded(subId, oldBalance, oldBalance + amount);
  }

  /**
   * @inheritdoc IVRFSubscriptionV2Plus
   */
  function fundSubscriptionWithNative(uint256 subId) external payable override nonReentrant {
    _requireValidSubscription(s_subscriptionConfigs[subId].owner);
    // We do not check that the msg.sender is the subscription owner,
    // anyone can fund a subscription.
    // We also do not check that msg.value > 0, since that's just a no-op
    // and would be a waste of gas on the caller's part.
    uint256 oldNativeBalance = s_subscriptions[subId].nativeBalance;
    s_subscriptions[subId].nativeBalance += uint96(msg.value);
    s_totalNativeBalance += uint96(msg.value);
    emit SubscriptionFundedWithNative(subId, oldNativeBalance, oldNativeBalance + msg.value);
  }

  /**
   * @inheritdoc IVRFSubscriptionV2Plus
   */
  function getSubscription(
    uint256 subId
  )
    public
    view
    override
    returns (uint96 balance, uint96 nativeBalance, uint64 reqCount, address subOwner, address[] memory consumers)
  {
    subOwner = s_subscriptionConfigs[subId].owner;
    _requireValidSubscription(subOwner);
    return (
      s_subscriptions[subId].balance,
      s_subscriptions[subId].nativeBalance,
      s_subscriptions[subId].reqCount,
      subOwner,
      s_subscriptionConfigs[subId].consumers
    );
  }

  /**
   * @inheritdoc IVRFSubscriptionV2Plus
   */
  function getActiveSubscriptionIds(
    uint256 startIndex,
    uint256 maxCount
  ) external view override returns (uint256[] memory ids) {
    uint256 numSubs = s_subIds.length();
    if (startIndex >= numSubs) revert IndexOutOfRange();
    uint256 endIndex = startIndex + maxCount;
    endIndex = endIndex > numSubs || maxCount == 0 ? numSubs : endIndex;
    uint256 idsLength = endIndex - startIndex;
    ids = new uint256[](idsLength);
    for (uint256 idx = 0; idx < idsLength; ++idx) {
      ids[idx] = s_subIds.at(idx + startIndex);
    }
    return ids;
  }

  /**
   * @inheritdoc IVRFSubscriptionV2Plus
   */
  function createSubscription() external override nonReentrant returns (uint256 subId) {
    // Generate a subscription id that is globally unique.
    uint64 currentSubNonce = s_currentSubNonce;
    subId = uint256(
      keccak256(abi.encodePacked(msg.sender, blockhash(block.number - 1), address(this), currentSubNonce))
    );
    // Increment the subscription nonce counter.
    s_currentSubNonce = currentSubNonce + 1;
    // Initialize storage variables.
    address[] memory consumers = new address[](0);
    s_subscriptions[subId] = Subscription({balance: 0, nativeBalance: 0, reqCount: 0});
    s_subscriptionConfigs[subId] = SubscriptionConfig({
      owner: msg.sender,
      requestedOwner: address(0),
      consumers: consumers
    });
    // Update the s_subIds set, which tracks all subscription ids created in this contract.
    s_subIds.add(subId);

    emit SubscriptionCreated(subId, msg.sender);
    return subId;
  }

  /**
   * @inheritdoc IVRFSubscriptionV2Plus
   */
  function requestSubscriptionOwnerTransfer(
    uint256 subId,
    address newOwner
  ) external override onlySubOwner(subId) nonReentrant {
    // Proposing to address(0) would never be claimable so don't need to check.
    SubscriptionConfig storage subscriptionConfig = s_subscriptionConfigs[subId];
    if (subscriptionConfig.requestedOwner != newOwner) {
      subscriptionConfig.requestedOwner = newOwner;
      emit SubscriptionOwnerTransferRequested(subId, msg.sender, newOwner);
    }
  }

  /**
   * @inheritdoc IVRFSubscriptionV2Plus
   */
  function acceptSubscriptionOwnerTransfer(uint256 subId) external override nonReentrant {
    address oldOwner = s_subscriptionConfigs[subId].owner;
    _requireValidSubscription(oldOwner);
    if (s_subscriptionConfigs[subId].requestedOwner != msg.sender) {
      revert MustBeRequestedOwner(s_subscriptionConfigs[subId].requestedOwner);
    }
    s_subscriptionConfigs[subId].owner = msg.sender;
    s_subscriptionConfigs[subId].requestedOwner = address(0);
    emit SubscriptionOwnerTransferred(subId, oldOwner, msg.sender);
  }

  /**
   * @inheritdoc IVRFSubscriptionV2Plus
   */
  function addConsumer(uint256 subId, address consumer) external override onlySubOwner(subId) nonReentrant {
    ConsumerConfig storage consumerConfig = s_consumers[consumer][subId];
    if (consumerConfig.active) {
      // Idempotence - do nothing if already added.
      // Ensures uniqueness in s_subscriptions[subId].consumers.
      return;
    }
    // Already maxed, cannot add any more consumers.
    address[] storage consumers = s_subscriptionConfigs[subId].consumers;
    if (consumers.length == MAX_CONSUMERS) {
      revert TooManyConsumers();
    }
    // consumerConfig.nonce is 0 if the consumer had never sent a request to this subscription
    // otherwise, consumerConfig.nonce is non-zero
    // in both cases, use consumerConfig.nonce as is and set active status to true
    consumerConfig.active = true;
    consumers.push(consumer);

    emit SubscriptionConsumerAdded(subId, consumer);
  }

  function _deleteSubscription(uint256 subId) internal returns (uint96 balance, uint96 nativeBalance) {
    address[] storage consumers = s_subscriptionConfigs[subId].consumers;
    balance = s_subscriptions[subId].balance;
    nativeBalance = s_subscriptions[subId].nativeBalance;
    // Note bounded by MAX_CONSUMERS;
    // If no consumers, does nothing.
    uint256 consumersLength = consumers.length;
    for (uint256 i = 0; i < consumersLength; ++i) {
      delete s_consumers[consumers[i]][subId];
    }
    delete s_subscriptionConfigs[subId];
    delete s_subscriptions[subId];
    s_subIds.remove(subId);
    if (balance != 0) {
      s_totalBalance -= balance;
    }
    if (nativeBalance != 0) {
      s_totalNativeBalance -= nativeBalance;
    }
    return (balance, nativeBalance);
  }

  function _cancelSubscriptionHelper(uint256 subId, address to) internal {
    (uint96 balance, uint96 nativeBalance) = _deleteSubscription(subId);

    // Only withdraw LINK if the token is active and there is a balance.
    if (address(LINK) != address(0) && balance != 0) {
      _requireSufficientBalance(LINK.transfer(to, uint256(balance)));
    }

    // send native to the "to" address using call
    _mustSendNative(to, uint256(nativeBalance));
    emit SubscriptionCanceled(subId, to, balance, nativeBalance);
  }

  modifier onlySubOwner(uint256 subId) {
    _onlySubOwner(subId);
    _;
  }

  function _onlySubOwner(uint256 subId) internal view {
    address subOwner = s_subscriptionConfigs[subId].owner;
    _requireValidSubscription(subOwner);
    if (msg.sender != subOwner) {
      revert MustBeSubOwner(subOwner);
    }
  }

  function _mustSendNative(address to, uint256 amount) internal {
    (bool success, ) = to.call{value: amount}("");
    if (!success) {
      revert FailedToSendNative();
    }
  }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

/** ****************************************************************************
  * @notice Verification of verifiable-random-function (VRF) proofs, following
  * @notice https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vrf-05#section-5.3
  * @notice See https://eprint.iacr.org/2017/099.pdf for security proofs.

  * @dev Bibliographic references:

  * @dev Goldberg, et al., "Verifiable Random Functions (VRFs)", Internet Draft
  * @dev draft-irtf-cfrg-vrf-05, IETF, Aug 11 2019,
  * @dev https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vrf-05

  * @dev Papadopoulos, et al., "Making NSEC5 Practical for DNSSEC", Cryptology
  * @dev ePrint Archive, Report 2017/099, https://eprint.iacr.org/2017/099.pdf
  * ****************************************************************************
  * @dev USAGE

  * @dev The main entry point is _randomValueFromVRFProof. See its docstring.
  * ****************************************************************************
  * @dev PURPOSE

  * @dev Reggie the Random Oracle (not his real job) wants to provide randomness
  * @dev to Vera the verifier in such a way that Vera can be sure he's not
  * @dev making his output up to suit himself. Reggie provides Vera a public key
  * @dev to which he knows the secret key. Each time Vera provides a seed to
  * @dev Reggie, he gives back a value which is computed completely
  * @dev deterministically from the seed and the secret key.

  * @dev Reggie provides a proof by which Vera can verify that the output was
  * @dev correctly computed once Reggie tells it to her, but without that proof,
  * @dev the output is computationally indistinguishable to her from a uniform
  * @dev random sample from the output space.

  * @dev The purpose of this contract is to perform that verification.
  * ****************************************************************************
  * @dev DESIGN NOTES

  * @dev The VRF algorithm verified here satisfies the full uniqueness, full
  * @dev collision resistance, and full pseudo-randomness security properties.
  * @dev See "SECURITY PROPERTIES" below, and
  * @dev https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vrf-05#section-3

  * @dev An elliptic curve point is generally represented in the solidity code
  * @dev as a uint256[2], corresponding to its affine coordinates in
  * @dev GF(FIELD_SIZE).

  * @dev For the sake of efficiency, this implementation deviates from the spec
  * @dev in some minor ways:

  * @dev - Keccak hash rather than the SHA256 hash recommended in
  * @dev   https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vrf-05#section-5.5
  * @dev   Keccak costs much less gas on the EVM, and provides similar security.

  * @dev - Secp256k1 curve instead of the P-256 or ED25519 curves recommended in
  * @dev   https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vrf-05#section-5.5
  * @dev   For curve-point multiplication, it's much cheaper to abuse ECRECOVER

  * @dev - _hashToCurve recursively hashes until it finds a curve x-ordinate. On
  * @dev   the EVM, this is slightly more efficient than the recommendation in
  * @dev   https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vrf-05#section-5.4.1.1
  * @dev   step 5, to concatenate with a nonce then hash, and rehash with the
  * @dev   nonce updated until a valid x-ordinate is found.

  * @dev - _hashToCurve does not include a cipher version string or the byte 0x1
  * @dev   in the hash message, as recommended in step 5.B of the draft
  * @dev   standard. They are unnecessary here because no variation in the
  * @dev   cipher suite is allowed.

  * @dev - Similarly, the hash input in _scalarFromCurvePoints does not include a
  * @dev   commitment to the cipher suite, either, which differs from step 2 of
  * @dev   https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vrf-05#section-5.4.3
  * @dev   . Also, the hash input is the concatenation of the uncompressed
  * @dev   points, not the compressed points as recommended in step 3.

  * @dev - In the calculation of the challenge value "c", the "u" value (i.e.
  * @dev   the value computed by Reggie as the nonce times the secp256k1
  * @dev   generator point, see steps 5 and 7 of
  * @dev   https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vrf-05#section-5.3
  * @dev   ) is replaced by its ethereum address, i.e. the lower 160 bits of the
  * @dev   keccak hash of the original u. This is because we only verify the
  * @dev   calculation of u up to its address, by abusing ECRECOVER.
  * ****************************************************************************
  * @dev   SECURITY PROPERTIES

  * @dev Here are the security properties for this VRF:

  * @dev Full uniqueness: For any seed and valid VRF public key, there is
  * @dev   exactly one VRF output which can be proved to come from that seed, in
  * @dev   the sense that the proof will pass _verifyVRFProof.

  * @dev Full collision resistance: It's cryptographically infeasible to find
  * @dev   two seeds with same VRF output from a fixed, valid VRF key

  * @dev Full pseudorandomness: Absent the proofs that the VRF outputs are
  * @dev   derived from a given seed, the outputs are computationally
  * @dev   indistinguishable from randomness.

  * @dev https://eprint.iacr.org/2017/099.pdf, Appendix B contains the proofs
  * @dev for these properties.

  * @dev For secp256k1, the key validation described in section
  * @dev https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vrf-05#section-5.6
  * @dev is unnecessary, because secp256k1 has cofactor 1, and the
  * @dev representation of the public key used here (affine x- and y-ordinates
  * @dev of the secp256k1 point on the standard y^2=x^3+7 curve) cannot refer to
  * @dev the point at infinity.
  * ****************************************************************************
  * @dev OTHER SECURITY CONSIDERATIONS
  *
  * @dev The seed input to the VRF could in principle force an arbitrary amount
  * @dev of work in _hashToCurve, by requiring extra rounds of hashing and
  * @dev checking whether that's yielded the x ordinate of a secp256k1 point.
  * @dev However, under the Random Oracle Model the probability of choosing a
  * @dev point which forces n extra rounds in _hashToCurve is 2⁻ⁿ. The base cost
  * @dev for calling _hashToCurve is about 25,000 gas, and each round of checking
  * @dev for a valid x ordinate costs about 15,555 gas, so to find a seed for
  * @dev which _hashToCurve would cost more than 2,017,000 gas, one would have to
  * @dev try, in expectation, about 2¹²⁸ seeds, which is infeasible for any
  * @dev foreseeable computational resources. (25,000 + 128 * 15,555 < 2,017,000.)

  * @dev Since the gas block limit for the Ethereum main net is 10,000,000 gas,
  * @dev this means it is infeasible for an adversary to prevent correct
  * @dev operation of this contract by choosing an adverse seed.

  * @dev (See TestMeasureHashToCurveGasCost for verification of the gas cost for
  * @dev _hashToCurve.)

  * @dev It may be possible to make a secure constant-time _hashToCurve function.
  * @dev See notes in _hashToCurve docstring.
*/
contract VRF {
  // See https://www.secg.org/sec2-v2.pdf, section 2.4.1, for these constants.
  // Number of points in Secp256k1
  uint256 private constant GROUP_ORDER = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141;
  // Prime characteristic of the galois field over which Secp256k1 is defined
  uint256 private constant FIELD_SIZE =
    // solium-disable-next-line indentation
    0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F;
  uint256 private constant WORD_LENGTH_BYTES = 0x20;

  // (base^exponent) % FIELD_SIZE
  // Cribbed from https://medium.com/@rbkhmrcr/precompiles-solidity-e5d29bd428c4
  function _bigModExp(uint256 base, uint256 exponent) internal view returns (uint256 exponentiation) {
    uint256 callResult;
    uint256[6] memory bigModExpContractInputs;
    bigModExpContractInputs[0] = WORD_LENGTH_BYTES; // Length of base
    bigModExpContractInputs[1] = WORD_LENGTH_BYTES; // Length of exponent
    bigModExpContractInputs[2] = WORD_LENGTH_BYTES; // Length of modulus
    bigModExpContractInputs[3] = base;
    bigModExpContractInputs[4] = exponent;
    bigModExpContractInputs[5] = FIELD_SIZE;
    uint256[1] memory output;
    assembly {
      callResult := staticcall(
        not(0), // Gas cost: no limit
        0x05, // Bigmodexp contract address
        bigModExpContractInputs,
        0xc0, // Length of input segment: 6*0x20-bytes
        output,
        0x20 // Length of output segment
      )
    }
    if (callResult == 0) {
      // solhint-disable-next-line gas-custom-errors
      revert("bigModExp failure!");
    }
    return output[0];
  }

  // Let q=FIELD_SIZE. q % 4 = 3, ∴ x≡r^2 mod q ⇒ x^SQRT_POWER≡±r mod q.  See
  // https://en.wikipedia.org/wiki/Modular_square_root#Prime_or_prime_power_modulus
  uint256 private constant SQRT_POWER = (FIELD_SIZE + 1) >> 2;

  // Computes a s.t. a^2 = x in the field. Assumes a exists
  function _squareRoot(uint256 x) internal view returns (uint256) {
    return _bigModExp(x, SQRT_POWER);
  }

  // The value of y^2 given that (x,y) is on secp256k1.
  function _ySquared(uint256 x) internal pure returns (uint256) {
    // Curve is y^2=x^3+7. See section 2.4.1 of https://www.secg.org/sec2-v2.pdf
    uint256 xCubed = mulmod(x, mulmod(x, x, FIELD_SIZE), FIELD_SIZE);
    return addmod(xCubed, 7, FIELD_SIZE);
  }

  // True iff p is on secp256k1
  function _isOnCurve(uint256[2] memory p) internal pure returns (bool) {
    // Section 2.3.6. in https://www.secg.org/sec1-v2.pdf
    // requires each ordinate to be in [0, ..., FIELD_SIZE-1]
    // solhint-disable-next-line gas-custom-errors
    require(p[0] < FIELD_SIZE, "invalid x-ordinate");
    // solhint-disable-next-line gas-custom-errors
    require(p[1] < FIELD_SIZE, "invalid y-ordinate");
    return _ySquared(p[0]) == mulmod(p[1], p[1], FIELD_SIZE);
  }

  // Hash x uniformly into {0, ..., FIELD_SIZE-1}.
  function _fieldHash(bytes memory b) internal pure returns (uint256 x_) {
    x_ = uint256(keccak256(b));
    // Rejecting if x >= FIELD_SIZE corresponds to step 2.1 in section 2.3.4 of
    // http://www.secg.org/sec1-v2.pdf , which is part of the definition of
    // string_to_point in the IETF draft
    while (x_ >= FIELD_SIZE) {
      x_ = uint256(keccak256(abi.encodePacked(x_)));
    }
    return x_;
  }

  // Hash b to a random point which hopefully lies on secp256k1. The y ordinate
  // is always even, due to
  // https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vrf-05#section-5.4.1.1
  // step 5.C, which references arbitrary_string_to_point, defined in
  // https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vrf-05#section-5.5 as
  // returning the point with given x ordinate, and even y ordinate.
  function _newCandidateSecp256k1Point(bytes memory b) internal view returns (uint256[2] memory p) {
    unchecked {
      p[0] = _fieldHash(b);
      p[1] = _squareRoot(_ySquared(p[0]));
      if (p[1] % 2 == 1) {
        // Note that 0 <= p[1] < FIELD_SIZE
        // so this cannot wrap, we use unchecked to save gas.
        p[1] = FIELD_SIZE - p[1];
      }
    }
    return p;
  }

  // Domain-separation tag for initial hash in _hashToCurve. Corresponds to
  // vrf.go/hashToCurveHashPrefix
  uint256 internal constant HASH_TO_CURVE_HASH_PREFIX = 1;

  // Cryptographic hash function onto the curve.
  //
  // Corresponds to algorithm in section 5.4.1.1 of the draft standard. (But see
  // DESIGN NOTES above for slight differences.)
  //
  // TODO(alx): Implement a bounded-computation hash-to-curve, as described in
  // "Construction of Rational Points on Elliptic Curves over Finite Fields"
  // http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.831.5299&rep=rep1&type=pdf
  // and suggested by
  // https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-hash-to-curve-01#section-5.2.2
  // (Though we can't used exactly that because secp256k1's j-invariant is 0.)
  //
  // This would greatly simplify the analysis in "OTHER SECURITY CONSIDERATIONS"
  // https://www.pivotaltracker.com/story/show/171120900
  function _hashToCurve(uint256[2] memory pk, uint256 input) internal view returns (uint256[2] memory rv) {
    rv = _newCandidateSecp256k1Point(abi.encodePacked(HASH_TO_CURVE_HASH_PREFIX, pk, input));
    while (!_isOnCurve(rv)) {
      rv = _newCandidateSecp256k1Point(abi.encodePacked(rv[0]));
    }
    return rv;
  }

  /** *********************************************************************
   * @notice Check that product==scalar*multiplicand
   *
   * @dev Based on Vitalik Buterin's idea in ethresear.ch post cited below.
   *
   * @param multiplicand: secp256k1 point
   * @param scalar: non-zero GF(GROUP_ORDER) scalar
   * @param product: secp256k1 expected to be multiplier * multiplicand
   * @return verifies true iff product==scalar*multiplicand, with cryptographically high probability
   */
  function _ecmulVerify(
    uint256[2] memory multiplicand,
    uint256 scalar,
    uint256[2] memory product
  ) internal pure returns (bool verifies) {
    // solhint-disable-next-line gas-custom-errors
    require(scalar != 0, "zero scalar"); // Rules out an ecrecover failure case
    uint256 x = multiplicand[0]; // x ordinate of multiplicand
    uint8 v = multiplicand[1] % 2 == 0 ? 27 : 28; // parity of y ordinate
    // https://ethresear.ch/t/you-can-kinda-abuse-ecrecover-to-do-ecmul-in-secp256k1-today/2384/9
    // Point corresponding to address ecrecover(0, v, x, s=scalar*x) is
    // (x⁻¹ mod GROUP_ORDER) * (scalar * x * multiplicand - 0 * g), i.e.
    // scalar*multiplicand. See https://crypto.stackexchange.com/a/18106
    bytes32 scalarTimesX = bytes32(mulmod(scalar, x, GROUP_ORDER));
    address actual = ecrecover(bytes32(0), v, bytes32(x), scalarTimesX);
    // Explicit conversion to address takes bottom 160 bits
    address expected = address(uint160(uint256(keccak256(abi.encodePacked(product)))));
    return (actual == expected);
  }

  // Returns x1/z1-x2/z2=(x1z2-x2z1)/(z1z2) in projective coordinates on P¹(𝔽ₙ)
  function _projectiveSub(
    uint256 x1,
    uint256 z1,
    uint256 x2,
    uint256 z2
  ) internal pure returns (uint256 x3, uint256 z3) {
    unchecked {
      uint256 num1 = mulmod(z2, x1, FIELD_SIZE);
      // Note this cannot wrap since x2 is a point in [0, FIELD_SIZE-1]
      // we use unchecked to save gas.
      uint256 num2 = mulmod(FIELD_SIZE - x2, z1, FIELD_SIZE);
      (x3, z3) = (addmod(num1, num2, FIELD_SIZE), mulmod(z1, z2, FIELD_SIZE));
    }
    return (x3, z3);
  }

  // Returns x1/z1*x2/z2=(x1x2)/(z1z2), in projective coordinates on P¹(𝔽ₙ)
  function _projectiveMul(
    uint256 x1,
    uint256 z1,
    uint256 x2,
    uint256 z2
  ) internal pure returns (uint256 x3, uint256 z3) {
    (x3, z3) = (mulmod(x1, x2, FIELD_SIZE), mulmod(z1, z2, FIELD_SIZE));
    return (x3, z3);
  }

  /** **************************************************************************
        @notice Computes elliptic-curve sum, in projective co-ordinates

        @dev Using projective coordinates avoids costly divisions

        @dev To use this with p and q in affine coordinates, call
        @dev _projectiveECAdd(px, py, qx, qy). This will return
        @dev the addition of (px, py, 1) and (qx, qy, 1), in the
        @dev secp256k1 group.

        @dev This can be used to calculate the z which is the inverse to zInv
        @dev in isValidVRFOutput. But consider using a faster
        @dev re-implementation such as ProjectiveECAdd in the golang vrf package.

        @dev This function assumes [px,py,1],[qx,qy,1] are valid projective
             coordinates of secp256k1 points. That is safe in this contract,
             because this method is only used by _linearCombination, which checks
             points are on the curve via ecrecover.
        **************************************************************************
        @param px The first affine coordinate of the first summand
        @param py The second affine coordinate of the first summand
        @param qx The first affine coordinate of the second summand
        @param qy The second affine coordinate of the second summand

        (px,py) and (qx,qy) must be distinct, valid secp256k1 points.
        **************************************************************************
        Return values are projective coordinates of [px,py,1]+[qx,qy,1] as points
        on secp256k1, in P²(𝔽ₙ)
        @return sx
        @return sy
        @return sz
    */
  function _projectiveECAdd(
    uint256 px,
    uint256 py,
    uint256 qx,
    uint256 qy
  ) internal pure returns (uint256 sx, uint256 sy, uint256 sz) {
    unchecked {
      // See "Group law for E/K : y^2 = x^3 + ax + b", in section 3.1.2, p. 80,
      // "Guide to Elliptic Curve Cryptography" by Hankerson, Menezes and Vanstone
      // We take the equations there for (sx,sy), and homogenize them to
      // projective coordinates. That way, no inverses are required, here, and we
      // only need the one inverse in _affineECAdd.

      // We only need the "point addition" equations from Hankerson et al. Can
      // skip the "point doubling" equations because p1 == p2 is cryptographically
      // impossible, and required not to be the case in _linearCombination.

      // Add extra "projective coordinate" to the two points
      (uint256 z1, uint256 z2) = (1, 1);

      // (lx, lz) = (qy-py)/(qx-px), i.e., gradient of secant line.
      // Cannot wrap since px and py are in [0, FIELD_SIZE-1]
      uint256 lx = addmod(qy, FIELD_SIZE - py, FIELD_SIZE);
      uint256 lz = addmod(qx, FIELD_SIZE - px, FIELD_SIZE);

      uint256 dx; // Accumulates denominator from sx calculation
      // sx=((qy-py)/(qx-px))^2-px-qx
      (sx, dx) = _projectiveMul(lx, lz, lx, lz); // ((qy-py)/(qx-px))^2
      (sx, dx) = _projectiveSub(sx, dx, px, z1); // ((qy-py)/(qx-px))^2-px
      (sx, dx) = _projectiveSub(sx, dx, qx, z2); // ((qy-py)/(qx-px))^2-px-qx

      uint256 dy; // Accumulates denominator from sy calculation
      // sy=((qy-py)/(qx-px))(px-sx)-py
      (sy, dy) = _projectiveSub(px, z1, sx, dx); // px-sx
      (sy, dy) = _projectiveMul(sy, dy, lx, lz); // ((qy-py)/(qx-px))(px-sx)
      (sy, dy) = _projectiveSub(sy, dy, py, z1); // ((qy-py)/(qx-px))(px-sx)-py

      if (dx != dy) {
        // Cross-multiply to put everything over a common denominator
        sx = mulmod(sx, dy, FIELD_SIZE);
        sy = mulmod(sy, dx, FIELD_SIZE);
        sz = mulmod(dx, dy, FIELD_SIZE);
      } else {
        // Already over a common denominator, use that for z ordinate
        sz = dx;
      }
    }
    return (sx, sy, sz);
  }

  // p1+p2, as affine points on secp256k1.
  //
  // invZ must be the inverse of the z returned by _projectiveECAdd(p1, p2).
  // It is computed off-chain to save gas.
  //
  // p1 and p2 must be distinct, because _projectiveECAdd doesn't handle
  // point doubling.
  function _affineECAdd(
    uint256[2] memory p1,
    uint256[2] memory p2,
    uint256 invZ
  ) internal pure returns (uint256[2] memory) {
    uint256 x;
    uint256 y;
    uint256 z;
    (x, y, z) = _projectiveECAdd(p1[0], p1[1], p2[0], p2[1]);
    // solhint-disable-next-line gas-custom-errors
    require(mulmod(z, invZ, FIELD_SIZE) == 1, "invZ must be inverse of z");
    // Clear the z ordinate of the projective representation by dividing through
    // by it, to obtain the affine representation
    return [mulmod(x, invZ, FIELD_SIZE), mulmod(y, invZ, FIELD_SIZE)];
  }

  // True iff address(c*p+s*g) == lcWitness, where g is generator. (With
  // cryptographically high probability.)
  function _verifyLinearCombinationWithGenerator(
    uint256 c,
    uint256[2] memory p,
    uint256 s,
    address lcWitness
  ) internal pure returns (bool) {
    // Rule out ecrecover failure modes which return address 0.
    unchecked {
      // solhint-disable-next-line gas-custom-errors
      require(lcWitness != address(0), "bad witness");
      uint8 v = (p[1] % 2 == 0) ? 27 : 28; // parity of y-ordinate of p
      // Note this cannot wrap (X - Y % X), but we use unchecked to save
      // gas.
      bytes32 pseudoHash = bytes32(GROUP_ORDER - mulmod(p[0], s, GROUP_ORDER)); // -s*p[0]
      bytes32 pseudoSignature = bytes32(mulmod(c, p[0], GROUP_ORDER)); // c*p[0]
      // https://ethresear.ch/t/you-can-kinda-abuse-ecrecover-to-do-ecmul-in-secp256k1-today/2384/9
      // The point corresponding to the address returned by
      // ecrecover(-s*p[0],v,p[0],c*p[0]) is
      // (p[0]⁻¹ mod GROUP_ORDER)*(c*p[0]-(-s)*p[0]*g)=c*p+s*g.
      // See https://crypto.stackexchange.com/a/18106
      // https://bitcoin.stackexchange.com/questions/38351/ecdsa-v-r-s-what-is-v
      address computed = ecrecover(pseudoHash, v, bytes32(p[0]), pseudoSignature);
      return computed == lcWitness;
    }
  }

  // c*p1 + s*p2. Requires cp1Witness=c*p1 and sp2Witness=s*p2. Also
  // requires cp1Witness != sp2Witness (which is fine for this application,
  // since it is cryptographically impossible for them to be equal. In the
  // (cryptographically impossible) case that a prover accidentally derives
  // a proof with equal c*p1 and s*p2, they should retry with a different
  // proof nonce.) Assumes that all points are on secp256k1
  // (which is checked in _verifyVRFProof below.)
  function _linearCombination(
    uint256 c,
    uint256[2] memory p1,
    uint256[2] memory cp1Witness,
    uint256 s,
    uint256[2] memory p2,
    uint256[2] memory sp2Witness,
    uint256 zInv
  ) internal pure returns (uint256[2] memory) {
    unchecked {
      // Note we are relying on the wrap around here
      // solhint-disable-next-line gas-custom-errors
      require((cp1Witness[0] % FIELD_SIZE) != (sp2Witness[0] % FIELD_SIZE), "points in sum must be distinct");
      // solhint-disable-next-line gas-custom-errors
      require(_ecmulVerify(p1, c, cp1Witness), "First mul check failed");
      // solhint-disable-next-line gas-custom-errors
      require(_ecmulVerify(p2, s, sp2Witness), "Second mul check failed");
      return _affineECAdd(cp1Witness, sp2Witness, zInv);
    }
  }

  // Domain-separation tag for the hash taken in _scalarFromCurvePoints.
  // Corresponds to scalarFromCurveHashPrefix in vrf.go
  uint256 internal constant SCALAR_FROM_CURVE_POINTS_HASH_PREFIX = 2;

  // Pseudo-random number from inputs. Matches vrf.go/_scalarFromCurvePoints, and
  // https://datatracker.ietf.org/doc/html/draft-irtf-cfrg-vrf-05#section-5.4.3
  // The draft calls (in step 7, via the definition of string_to_int, in
  // https://datatracker.ietf.org/doc/html/rfc8017#section-4.2 ) for taking the
  // first hash without checking that it corresponds to a number less than the
  // group order, which will lead to a slight bias in the sample.
  //
  // TODO(alx): We could save a bit of gas by following the standard here and
  // using the compressed representation of the points, if we collated the y
  // parities into a single bytes32.
  // https://www.pivotaltracker.com/story/show/171120588
  function _scalarFromCurvePoints(
    uint256[2] memory hash,
    uint256[2] memory pk,
    uint256[2] memory gamma,
    address uWitness,
    uint256[2] memory v
  ) internal pure returns (uint256 s) {
    return uint256(keccak256(abi.encodePacked(SCALAR_FROM_CURVE_POINTS_HASH_PREFIX, hash, pk, gamma, v, uWitness)));
  }

  // True if (gamma, c, s) is a correctly constructed randomness proof from pk
  // and seed. zInv must be the inverse of the third ordinate from
  // _projectiveECAdd applied to cGammaWitness and sHashWitness. Corresponds to
  // section 5.3 of the IETF draft.
  //
  // TODO(alx): Since I'm only using pk in the ecrecover call, I could only pass
  // the x ordinate, and the parity of the y ordinate in the top bit of uWitness
  // (which I could make a uint256 without using any extra space.) Would save
  // about 2000 gas. https://www.pivotaltracker.com/story/show/170828567
  function _verifyVRFProof(
    uint256[2] memory pk,
    uint256[2] memory gamma,
    uint256 c,
    uint256 s,
    uint256 seed,
    address uWitness,
    uint256[2] memory cGammaWitness,
    uint256[2] memory sHashWitness,
    uint256 zInv
  ) internal view {
    unchecked {
      // solhint-disable-next-line gas-custom-errors
      require(_isOnCurve(pk), "public key is not on curve");
      // solhint-disable-next-line gas-custom-errors
      require(_isOnCurve(gamma), "gamma is not on curve");
      // solhint-disable-next-line gas-custom-errors
      require(_isOnCurve(cGammaWitness), "cGammaWitness is not on curve");
      // solhint-disable-next-line gas-custom-errors
      require(_isOnCurve(sHashWitness), "sHashWitness is not on curve");
      // Step 5. of IETF draft section 5.3 (pk corresponds to 5.3's Y, and here
      // we use the address of u instead of u itself. Also, here we add the
      // terms instead of taking the difference, and in the proof construction in
      // vrf.GenerateProof, we correspondingly take the difference instead of
      // taking the sum as they do in step 7 of section 5.1.)
      // solhint-disable-next-line gas-custom-errors
      require(_verifyLinearCombinationWithGenerator(c, pk, s, uWitness), "addr(c*pk+s*g)!=_uWitness");
      // Step 4. of IETF draft section 5.3 (pk corresponds to Y, seed to alpha_string)
      uint256[2] memory hash = _hashToCurve(pk, seed);
      // Step 6. of IETF draft section 5.3, but see note for step 5 about +/- terms
      uint256[2] memory v = _linearCombination(c, gamma, cGammaWitness, s, hash, sHashWitness, zInv);
      // Steps 7. and 8. of IETF draft section 5.3
      uint256 derivedC = _scalarFromCurvePoints(hash, pk, gamma, uWitness, v);
      // solhint-disable-next-line gas-custom-errors
      require(c == derivedC, "invalid proof");
    }
  }

  // Domain-separation tag for the hash used as the final VRF output.
  // Corresponds to vrfRandomOutputHashPrefix in vrf.go
  uint256 internal constant VRF_RANDOM_OUTPUT_HASH_PREFIX = 3;

  struct Proof {
    uint256[2] pk;
    uint256[2] gamma;
    uint256 c;
    uint256 s;
    uint256 seed;
    address uWitness;
    uint256[2] cGammaWitness;
    uint256[2] sHashWitness;
    uint256 zInv;
  }

  /* ***************************************************************************
     * @notice Returns proof's output, if proof is valid. Otherwise reverts

     * @param proof vrf proof components
     * @param seed  seed used to generate the vrf output
     *
     * Throws if proof is invalid, otherwise:
     * @return output i.e., the random output implied by the proof
     * ***************************************************************************
     */
  function _randomValueFromVRFProof(Proof calldata proof, uint256 seed) internal view returns (uint256 output) {
    _verifyVRFProof(
      proof.pk,
      proof.gamma,
      proof.c,
      proof.s,
      seed,
      proof.uWitness,
      proof.cGammaWitness,
      proof.sHashWitness,
      proof.zInv
    );
    output = uint256(keccak256(abi.encode(VRF_RANDOM_OUTPUT_HASH_PREFIX, proof.gamma)));
    return output;
  }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.4;

import {IVRFCoordinatorV2Plus} from "./interfaces/IVRFCoordinatorV2Plus.sol";
import {IVRFMigratableConsumerV2Plus} from "./interfaces/IVRFMigratableConsumerV2Plus.sol";
import {ConfirmedOwner} from "../../shared/access/ConfirmedOwner.sol";

/** ****************************************************************************
 * @notice Interface for contracts using VRF randomness
 * *****************************************************************************
 * @dev PURPOSE
 *
 * @dev Reggie the Random Oracle (not his real job) wants to provide randomness
 * @dev to Vera the verifier in such a way that Vera can be sure he's not
 * @dev making his output up to suit himself. Reggie provides Vera a public key
 * @dev to which he knows the secret key. Each time Vera provides a seed to
 * @dev Reggie, he gives back a value which is computed completely
 * @dev deterministically from the seed and the secret key.
 *
 * @dev Reggie provides a proof by which Vera can verify that the output was
 * @dev correctly computed once Reggie tells it to her, but without that proof,
 * @dev the output is indistinguishable to her from a uniform random sample
 * @dev from the output space.
 *
 * @dev The purpose of this contract is to make it easy for unrelated contracts
 * @dev to talk to Vera the verifier about the work Reggie is doing, to provide
 * @dev simple access to a verifiable source of randomness. It ensures 2 things:
 * @dev 1. The fulfillment came from the VRFCoordinatorV2Plus.
 * @dev 2. The consumer contract implements fulfillRandomWords.
 * *****************************************************************************
 * @dev USAGE
 *
 * @dev Calling contracts must inherit from VRFConsumerBaseV2Plus, and can
 * @dev initialize VRFConsumerBaseV2Plus's attributes in their constructor as
 * @dev shown:
 *
 * @dev   contract VRFConsumerV2Plus is VRFConsumerBaseV2Plus {
 * @dev     constructor(<other arguments>, address _vrfCoordinator, address _subOwner)
 * @dev       VRFConsumerBaseV2Plus(_vrfCoordinator, _subOwner) public {
 * @dev         <initialization with other arguments goes here>
 * @dev       }
 * @dev   }
 *
 * @dev The oracle will have given you an ID for the VRF keypair they have
 * @dev committed to (let's call it keyHash). Create a subscription, fund it
 * @dev and your consumer contract as a consumer of it (see VRFCoordinatorInterface
 * @dev subscription management functions).
 * @dev Call requestRandomWords(keyHash, subId, minimumRequestConfirmations,
 * @dev callbackGasLimit, numWords, extraArgs),
 * @dev see (IVRFCoordinatorV2Plus for a description of the arguments).
 *
 * @dev Once the VRFCoordinatorV2Plus has received and validated the oracle's response
 * @dev to your request, it will call your contract's fulfillRandomWords method.
 *
 * @dev The randomness argument to fulfillRandomWords is a set of random words
 * @dev generated from your requestId and the blockHash of the request.
 *
 * @dev If your contract could have concurrent requests open, you can use the
 * @dev requestId returned from requestRandomWords to track which response is associated
 * @dev with which randomness request.
 * @dev See "SECURITY CONSIDERATIONS" for principles to keep in mind,
 * @dev if your contract could have multiple requests in flight simultaneously.
 *
 * @dev Colliding `requestId`s are cryptographically impossible as long as seeds
 * @dev differ.
 *
 * *****************************************************************************
 * @dev SECURITY CONSIDERATIONS
 *
 * @dev A method with the ability to call your fulfillRandomness method directly
 * @dev could spoof a VRF response with any random value, so it's critical that
 * @dev it cannot be directly called by anything other than this base contract
 * @dev (specifically, by the VRFConsumerBaseV2Plus.rawFulfillRandomness method).
 *
 * @dev For your users to trust that your contract's random behavior is free
 * @dev from malicious interference, it's best if you can write it so that all
 * @dev behaviors implied by a VRF response are executed *during* your
 * @dev fulfillRandomness method. If your contract must store the response (or
 * @dev anything derived from it) and use it later, you must ensure that any
 * @dev user-significant behavior which depends on that stored value cannot be
 * @dev manipulated by a subsequent VRF request.
 *
 * @dev Similarly, both miners and the VRF oracle itself have some influence
 * @dev over the order in which VRF responses appear on the blockchain, so if
 * @dev your contract could have multiple VRF requests in flight simultaneously,
 * @dev you must ensure that the order in which the VRF responses arrive cannot
 * @dev be used to manipulate your contract's user-significant behavior.
 *
 * @dev Since the block hash of the block which contains the requestRandomness
 * @dev call is mixed into the input to the VRF *last*, a sufficiently powerful
 * @dev miner could, in principle, fork the blockchain to evict the block
 * @dev containing the request, forcing the request to be included in a
 * @dev different block with a different hash, and therefore a different input
 * @dev to the VRF. However, such an attack would incur a substantial economic
 * @dev cost. This cost scales with the number of blocks the VRF oracle waits
 * @dev until it calls responds to a request. It is for this reason that
 * @dev that you can signal to an oracle you'd like them to wait longer before
 * @dev responding to the request (however this is not enforced in the contract
 * @dev and so remains effective only in the case of unmodified oracle software).
 */
abstract contract VRFConsumerBaseV2Plus is IVRFMigratableConsumerV2Plus, ConfirmedOwner {
  error OnlyCoordinatorCanFulfill(address have, address want);
  error OnlyOwnerOrCoordinator(address have, address owner, address coordinator);
  error ZeroAddress();

  // s_vrfCoordinator should be used by consumers to make requests to vrfCoordinator
  // so that coordinator reference is updated after migration
  IVRFCoordinatorV2Plus public s_vrfCoordinator;

  /**
   * @param _vrfCoordinator address of VRFCoordinator contract
   */
  constructor(address _vrfCoordinator) ConfirmedOwner(msg.sender) {
    if (_vrfCoordinator == address(0)) {
      revert ZeroAddress();
    }
    s_vrfCoordinator = IVRFCoordinatorV2Plus(_vrfCoordinator);
  }

  /**
   * @notice fulfillRandomness handles the VRF response. Your contract must
   * @notice implement it. See "SECURITY CONSIDERATIONS" above for important
   * @notice principles to keep in mind when implementing your fulfillRandomness
   * @notice method.
   *
   * @dev VRFConsumerBaseV2Plus expects its subcontracts to have a method with this
   * @dev signature, and will call it once it has verified the proof
   * @dev associated with the randomness. (It is triggered via a call to
   * @dev rawFulfillRandomness, below.)
   *
   * @param requestId The Id initially returned by requestRandomness
   * @param randomWords the VRF output expanded to the requested number of words
   */
  // solhint-disable-next-line chainlink-solidity/prefix-internal-functions-with-underscore
  function fulfillRandomWords(uint256 requestId, uint256[] calldata randomWords) internal virtual;

  // rawFulfillRandomness is called by VRFCoordinator when it receives a valid VRF
  // proof. rawFulfillRandomness then calls fulfillRandomness, after validating
  // the origin of the call
  function rawFulfillRandomWords(uint256 requestId, uint256[] calldata randomWords) external {
    if (msg.sender != address(s_vrfCoordinator)) {
      revert OnlyCoordinatorCanFulfill(msg.sender, address(s_vrfCoordinator));
    }
    fulfillRandomWords(requestId, randomWords);
  }

  /**
   * @inheritdoc IVRFMigratableConsumerV2Plus
   */
  function setCoordinator(address _vrfCoordinator) external override onlyOwnerOrCoordinator {
    if (_vrfCoordinator == address(0)) {
      revert ZeroAddress();
    }
    s_vrfCoordinator = IVRFCoordinatorV2Plus(_vrfCoordinator);

    emit CoordinatorSet(_vrfCoordinator);
  }

  modifier onlyOwnerOrCoordinator() {
    if (msg.sender != owner() && msg.sender != address(s_vrfCoordinator)) {
      revert OnlyOwnerOrCoordinator(msg.sender, owner(), address(s_vrfCoordinator));
    }
    _;
  }
}

// SPDX-License-Identifier: MIT
pragma solidity 0.8.19;

import {BlockhashStoreInterface} from "../interfaces/BlockhashStoreInterface.sol";
import {VRF} from "../../vrf/VRF.sol";
import {VRFTypes} from "../VRFTypes.sol";
import {VRFConsumerBaseV2Plus, IVRFMigratableConsumerV2Plus} from "./VRFConsumerBaseV2Plus.sol";
import {SubscriptionAPI} from "./SubscriptionAPI.sol";
import {VRFV2PlusClient} from "./libraries/VRFV2PlusClient.sol";
import {IVRFCoordinatorV2PlusMigration} from "./interfaces/IVRFCoordinatorV2PlusMigration.sol";
// solhint-disable-next-line no-unused-import
import {IVRFCoordinatorV2Plus, IVRFSubscriptionV2Plus} from "./interfaces/IVRFCoordinatorV2Plus.sol";

// solhint-disable-next-line contract-name-camelcase
contract VRFCoordinatorV2_5 is VRF, SubscriptionAPI, IVRFCoordinatorV2Plus {
  /// @dev should always be available
  // solhint-disable-next-line chainlink-solidity/prefix-immutable-variables-with-i
  BlockhashStoreInterface public immutable BLOCKHASH_STORE;

  // Set this maximum to 200 to give us a 56 block window to fulfill
  // the request before requiring the block hash feeder.
  uint16 public constant MAX_REQUEST_CONFIRMATIONS = 200;
  uint32 public constant MAX_NUM_WORDS = 500;
  // 5k is plenty for an EXTCODESIZE call (2600) + warm CALL (100)
  // and some arithmetic operations.
  uint256 private constant GAS_FOR_CALL_EXACT_CHECK = 5_000;
  // upper bound limit for premium percentages to make sure fee calculations don't overflow
  uint8 private constant PREMIUM_PERCENTAGE_MAX = 155;
  error InvalidRequestConfirmations(uint16 have, uint16 min, uint16 max);
  error GasLimitTooBig(uint32 have, uint32 want);
  error NumWordsTooBig(uint32 have, uint32 want);
  error MsgDataTooBig(uint256 have, uint32 max);
  error ProvingKeyAlreadyRegistered(bytes32 keyHash);
  error NoSuchProvingKey(bytes32 keyHash);
  error InvalidLinkWeiPrice(int256 linkWei);
  error LinkDiscountTooHigh(uint32 flatFeeLinkDiscountPPM, uint32 flatFeeNativePPM);
  error InvalidPremiumPercentage(uint8 premiumPercentage, uint8 max);
  error NoCorrespondingRequest();
  error IncorrectCommitment();
  error BlockhashNotInStore(uint256 blockNum);
  error PaymentTooLarge();
  error InvalidExtraArgsTag();
  error GasPriceExceeded(uint256 gasPrice, uint256 maxGas);

  struct ProvingKey {
    bool exists; // proving key exists
    uint64 maxGas; // gas lane max gas price for fulfilling requests
  }

  mapping(bytes32 => ProvingKey) /* keyHash */ /* provingKey */ public s_provingKeys;
  bytes32[] public s_provingKeyHashes;
  mapping(uint256 => bytes32) /* requestID */ /* commitment */ public s_requestCommitments;
  event ProvingKeyRegistered(bytes32 keyHash, uint64 maxGas);
  event ProvingKeyDeregistered(bytes32 keyHash, uint64 maxGas);

  event RandomWordsRequested(
    bytes32 indexed keyHash,
    uint256 requestId,
    uint256 preSeed,
    uint256 indexed subId,
    uint16 minimumRequestConfirmations,
    uint32 callbackGasLimit,
    uint32 numWords,
    bytes extraArgs,
    address indexed sender
  );

  event RandomWordsFulfilled(
    uint256 indexed requestId,
    uint256 outputSeed,
    uint256 indexed subId,
    uint96 payment,
    bool nativePayment,
    bool success,
    bool onlyPremium
  );

  event L1GasFee(uint256 fee);

  int256 public s_fallbackWeiPerUnitLink;

  event ConfigSet(
    uint16 minimumRequestConfirmations,
    uint32 maxGasLimit,
    uint32 stalenessSeconds,
    uint32 gasAfterPaymentCalculation,
    int256 fallbackWeiPerUnitLink,
    uint32 fulfillmentFlatFeeNativePPM,
    uint32 fulfillmentFlatFeeLinkDiscountPPM,
    uint8 nativePremiumPercentage,
    uint8 linkPremiumPercentage
  );

  event FallbackWeiPerUnitLinkUsed(uint256 requestId, int256 fallbackWeiPerUnitLink);

  constructor(address blockhashStore) SubscriptionAPI() {
    BLOCKHASH_STORE = BlockhashStoreInterface(blockhashStore);
  }

  /**
   * @notice Registers a proving key to.
   * @param publicProvingKey key that oracle can use to submit vrf fulfillments
   */
  function registerProvingKey(uint256[2] calldata publicProvingKey, uint64 maxGas) external onlyOwner {
    bytes32 kh = hashOfKey(publicProvingKey);
    if (s_provingKeys[kh].exists) {
      revert ProvingKeyAlreadyRegistered(kh);
    }
    s_provingKeys[kh] = ProvingKey({exists: true, maxGas: maxGas});
    s_provingKeyHashes.push(kh);
    emit ProvingKeyRegistered(kh, maxGas);
  }

  /**
   * @notice Deregisters a proving key.
   * @param publicProvingKey key that oracle can use to submit vrf fulfillments
   */
  function deregisterProvingKey(uint256[2] calldata publicProvingKey) external onlyOwner {
    bytes32 kh = hashOfKey(publicProvingKey);
    ProvingKey memory key = s_provingKeys[kh];
    if (!key.exists) {
      revert NoSuchProvingKey(kh);
    }
    delete s_provingKeys[kh];
    uint256 s_provingKeyHashesLength = s_provingKeyHashes.length;
    for (uint256 i = 0; i < s_provingKeyHashesLength; ++i) {
      if (s_provingKeyHashes[i] == kh) {
        // Copy last element and overwrite kh to be deleted with it
        s_provingKeyHashes[i] = s_provingKeyHashes[s_provingKeyHashesLength - 1];
        s_provingKeyHashes.pop();
        break;
      }
    }
    emit ProvingKeyDeregistered(kh, key.maxGas);
  }

  /**
   * @notice Returns the proving key hash key associated with this public key
   * @param publicKey the key to return the hash of
   */
  function hashOfKey(uint256[2] calldata publicKey) public pure returns (bytes32) {
    return keccak256(abi.encode(publicKey));
  }

  /**
   * @notice Sets the configuration of the vrfv2 coordinator
   * @param minimumRequestConfirmations global min for request confirmations
   * @param maxGasLimit global max for request gas limit
   * @param stalenessSeconds if the native/link feed is more stale then this, use the fallback price
   * @param gasAfterPaymentCalculation gas used in doing accounting after completing the gas measurement
   * @param fallbackWeiPerUnitLink fallback native/link price in the case of a stale feed
   * @param fulfillmentFlatFeeNativePPM flat fee in native for native payment
   * @param fulfillmentFlatFeeLinkDiscountPPM flat fee discount for link payment in native
   * @param nativePremiumPercentage native premium percentage
   * @param linkPremiumPercentage link premium percentage
   */
  function setConfig(
    uint16 minimumRequestConfirmations,
    uint32 maxGasLimit,
    uint32 stalenessSeconds,
    uint32 gasAfterPaymentCalculation,
    int256 fallbackWeiPerUnitLink,
    uint32 fulfillmentFlatFeeNativePPM,
    uint32 fulfillmentFlatFeeLinkDiscountPPM,
    uint8 nativePremiumPercentage,
    uint8 linkPremiumPercentage
  ) external onlyOwner {
    if (minimumRequestConfirmations > MAX_REQUEST_CONFIRMATIONS) {
      revert InvalidRequestConfirmations(
        minimumRequestConfirmations,
        minimumRequestConfirmations,
        MAX_REQUEST_CONFIRMATIONS
      );
    }
    if (fallbackWeiPerUnitLink <= 0) {
      revert InvalidLinkWeiPrice(fallbackWeiPerUnitLink);
    }
    if (fulfillmentFlatFeeLinkDiscountPPM > fulfillmentFlatFeeNativePPM) {
      revert LinkDiscountTooHigh(fulfillmentFlatFeeLinkDiscountPPM, fulfillmentFlatFeeNativePPM);
    }
    if (nativePremiumPercentage > PREMIUM_PERCENTAGE_MAX) {
      revert InvalidPremiumPercentage(nativePremiumPercentage, PREMIUM_PERCENTAGE_MAX);
    }
    if (linkPremiumPercentage > PREMIUM_PERCENTAGE_MAX) {
      revert InvalidPremiumPercentage(linkPremiumPercentage, PREMIUM_PERCENTAGE_MAX);
    }
    s_config = Config({
      minimumRequestConfirmations: minimumRequestConfirmations,
      maxGasLimit: maxGasLimit,
      stalenessSeconds: stalenessSeconds,
      gasAfterPaymentCalculation: gasAfterPaymentCalculation,
      reentrancyLock: false,
      fulfillmentFlatFeeNativePPM: fulfillmentFlatFeeNativePPM,
      fulfillmentFlatFeeLinkDiscountPPM: fulfillmentFlatFeeLinkDiscountPPM,
      nativePremiumPercentage: nativePremiumPercentage,
      linkPremiumPercentage: linkPremiumPercentage
    });
    s_fallbackWeiPerUnitLink = fallbackWeiPerUnitLink;
    emit ConfigSet(
      minimumRequestConfirmations,
      maxGasLimit,
      stalenessSeconds,
      gasAfterPaymentCalculation,
      fallbackWeiPerUnitLink,
      fulfillmentFlatFeeNativePPM,
      fulfillmentFlatFeeLinkDiscountPPM,
      nativePremiumPercentage,
      linkPremiumPercentage
    );
  }

  /// @dev Convert the extra args bytes into a struct
  /// @param extraArgs The extra args bytes
  /// @return The extra args struct
  function _fromBytes(bytes calldata extraArgs) internal pure returns (VRFV2PlusClient.ExtraArgsV1 memory) {
    if (extraArgs.length == 0) {
      return VRFV2PlusClient.ExtraArgsV1({nativePayment: false});
    }
    if (bytes4(extraArgs) != VRFV2PlusClient.EXTRA_ARGS_V1_TAG) revert InvalidExtraArgsTag();
    return abi.decode(extraArgs[4:], (VRFV2PlusClient.ExtraArgsV1));
  }

  /**
   * @notice Request a set of random words.
   * @param req - a struct containing following fiels for randomness request:
   * keyHash - Corresponds to a particular oracle job which uses
   * that key for generating the VRF proof. Different keyHash's have different gas price
   * ceilings, so you can select a specific one to bound your maximum per request cost.
   * subId  - The ID of the VRF subscription. Must be funded
   * with the minimum subscription balance required for the selected keyHash.
   * requestConfirmations - How many blocks you'd like the
   * oracle to wait before responding to the request. See SECURITY CONSIDERATIONS
   * for why you may want to request more. The acceptable range is
   * [minimumRequestBlockConfirmations, 200].
   * callbackGasLimit - How much gas you'd like to receive in your
   * fulfillRandomWords callback. Note that gasleft() inside fulfillRandomWords
   * may be slightly less than this amount because of gas used calling the function
   * (argument decoding etc.), so you may need to request slightly more than you expect
   * to have inside fulfillRandomWords. The acceptable range is
   * [0, maxGasLimit]
   * numWords - The number of uint256 random values you'd like to receive
   * in your fulfillRandomWords callback. Note these numbers are expanded in a
   * secure way by the VRFCoordinator from a single random value supplied by the oracle.
   * extraArgs - Encoded extra arguments that has a boolean flag for whether payment
   * should be made in native or LINK. Payment in LINK is only available if the LINK token is available to this contract.
   * @return requestId - A unique identifier of the request. Can be used to match
   * a request to a response in fulfillRandomWords.
   */
  function requestRandomWords(
    VRFV2PlusClient.RandomWordsRequest calldata req
  ) external override nonReentrant returns (uint256 requestId) {
    // Input validation using the subscription storage.
    uint256 subId = req.subId;
    _requireValidSubscription(s_subscriptionConfigs[subId].owner);
    // Its important to ensure that the consumer is in fact who they say they
    // are, otherwise they could use someone else's subscription balance.
    mapping(uint256 => ConsumerConfig) storage consumerConfigs = s_consumers[msg.sender];
    ConsumerConfig memory consumerConfig = consumerConfigs[subId];
    if (!consumerConfig.active) {
      revert InvalidConsumer(subId, msg.sender);
    }
    // Input validation using the config storage word.
    if (
      req.requestConfirmations < s_config.minimumRequestConfirmations ||
      req.requestConfirmations > MAX_REQUEST_CONFIRMATIONS
    ) {
      revert InvalidRequestConfirmations(
        req.requestConfirmations,
        s_config.minimumRequestConfirmations,
        MAX_REQUEST_CONFIRMATIONS
      );
    }
    // No lower bound on the requested gas limit. A user could request 0
    // and they would simply be billed for the proof verification and wouldn't be
    // able to do anything with the random value.
    if (req.callbackGasLimit > s_config.maxGasLimit) {
      revert GasLimitTooBig(req.callbackGasLimit, s_config.maxGasLimit);
    }
    if (req.numWords > MAX_NUM_WORDS) {
      revert NumWordsTooBig(req.numWords, MAX_NUM_WORDS);
    }

    // Note we do not check whether the keyHash is valid to save gas.
    // The consequence for users is that they can send requests
    // for invalid keyHashes which will simply not be fulfilled.
    ++consumerConfig.nonce;
    ++consumerConfig.pendingReqCount;
    uint256 preSeed;
    (requestId, preSeed) = _computeRequestId(req.keyHash, msg.sender, subId, consumerConfig.nonce);

    bytes memory extraArgsBytes = VRFV2PlusClient._argsToBytes(_fromBytes(req.extraArgs));
    s_requestCommitments[requestId] = keccak256(
      abi.encode(requestId, _getBlockNumber(), subId, req.callbackGasLimit, req.numWords, msg.sender, extraArgsBytes)
    );
    emit RandomWordsRequested(
      req.keyHash,
      requestId,
      preSeed,
      subId,
      req.requestConfirmations,
      req.callbackGasLimit,
      req.numWords,
      extraArgsBytes,
      msg.sender
    );
    consumerConfigs[subId] = consumerConfig;

    return requestId;
  }

  function _computeRequestId(
    bytes32 keyHash,
    address sender,
    uint256 subId,
    uint64 nonce
  ) internal pure returns (uint256, uint256) {
    uint256 preSeed = uint256(keccak256(abi.encode(keyHash, sender, subId, nonce)));
    return (uint256(keccak256(abi.encode(keyHash, preSeed))), preSeed);
  }

  /**
   * @dev calls target address with exactly gasAmount gas and data as calldata
   * or reverts if at least gasAmount gas is not available.
   */
  function _callWithExactGas(uint256 gasAmount, address target, bytes memory data) private returns (bool success) {
    assembly {
      let g := gas()
      // Compute g -= GAS_FOR_CALL_EXACT_CHECK and check for underflow
      // The gas actually passed to the callee is min(gasAmount, 63//64*gas available).
      // We want to ensure that we revert if gasAmount >  63//64*gas available
      // as we do not want to provide them with less, however that check itself costs
      // gas.  GAS_FOR_CALL_EXACT_CHECK ensures we have at least enough gas to be able
      // to revert if gasAmount >  63//64*gas available.
      if lt(g, GAS_FOR_CALL_EXACT_CHECK) {
        revert(0, 0)
      }
      g := sub(g, GAS_FOR_CALL_EXACT_CHECK)
      // if g - g//64 <= gasAmount, revert
      // (we subtract g//64 because of EIP-150)
      if iszero(gt(sub(g, div(g, 64)), gasAmount)) {
        revert(0, 0)
      }
      // solidity calls check that a contract actually exists at the destination, so we do the same
      if iszero(extcodesize(target)) {
        revert(0, 0)
      }
      // call and return whether we succeeded. ignore return data
      // call(gas,addr,value,argsOffset,argsLength,retOffset,retLength)
      success := call(gasAmount, target, 0, add(data, 0x20), mload(data), 0, 0)
    }
    return success;
  }

  struct Output {
    ProvingKey provingKey;
    uint256 requestId;
    uint256 randomness;
  }

  function _getRandomnessFromProof(
    Proof calldata proof,
    VRFTypes.RequestCommitmentV2Plus calldata rc
  ) internal view returns (Output memory) {
    bytes32 keyHash = hashOfKey(proof.pk);
    ProvingKey memory key = s_provingKeys[keyHash];
    // Only registered proving keys are permitted.
    if (!key.exists) {
      revert NoSuchProvingKey(keyHash);
    }
    uint256 requestId = uint256(keccak256(abi.encode(keyHash, proof.seed)));
    bytes32 commitment = s_requestCommitments[requestId];
    if (commitment == 0) {
      revert NoCorrespondingRequest();
    }
    if (
      commitment !=
      keccak256(abi.encode(requestId, rc.blockNum, rc.subId, rc.callbackGasLimit, rc.numWords, rc.sender, rc.extraArgs))
    ) {
      revert IncorrectCommitment();
    }

    bytes32 blockHash = _getBlockhash(rc.blockNum);
    if (blockHash == bytes32(0)) {
      blockHash = BLOCKHASH_STORE.getBlockhash(rc.blockNum);
      if (blockHash == bytes32(0)) {
        revert BlockhashNotInStore(rc.blockNum);
      }
    }

    // The seed actually used by the VRF machinery, mixing in the blockhash
    uint256 actualSeed = uint256(keccak256(abi.encodePacked(proof.seed, blockHash)));
    uint256 randomness = VRF._randomValueFromVRFProof(proof, actualSeed); // Reverts on failure
    return Output(key, requestId, randomness);
  }

  function _getValidatedGasPrice(bool onlyPremium, uint64 gasLaneMaxGas) internal view returns (uint256 gasPrice) {
    if (tx.gasprice > gasLaneMaxGas) {
      if (onlyPremium) {
        // if only the premium amount needs to be billed, then the premium is capped by the gas lane max
        return uint256(gasLaneMaxGas);
      } else {
        // Ensure gas price does not exceed the gas lane max gas price
        revert GasPriceExceeded(tx.gasprice, gasLaneMaxGas);
      }
    }
    return tx.gasprice;
  }

  function _deliverRandomness(
    uint256 requestId,
    VRFTypes.RequestCommitmentV2Plus calldata rc,
    uint256[] memory randomWords
  ) internal returns (bool success) {
    VRFConsumerBaseV2Plus v;
    bytes memory resp = abi.encodeWithSelector(v.rawFulfillRandomWords.selector, requestId, randomWords);
    // Call with explicitly the amount of callback gas requested
    // Important to not let them exhaust the gas budget and avoid oracle payment.
    // Do not allow any non-view/non-pure coordinator functions to be called
    // during the consumers callback code via reentrancyLock.
    // Note that _callWithExactGas will revert if we do not have sufficient gas
    // to give the callee their requested amount.
    s_config.reentrancyLock = true;
    success = _callWithExactGas(rc.callbackGasLimit, rc.sender, resp);
    s_config.reentrancyLock = false;
    return success;
  }

  /*
   * @notice Fulfill a randomness request.
   * @param proof contains the proof and randomness
   * @param rc request commitment pre-image, committed to at request time
   * @param onlyPremium only charge premium
   * @return payment amount billed to the subscription
   * @dev simulated offchain to determine if sufficient balance is present to fulfill the request
   */
  function fulfillRandomWords(
    Proof calldata proof,
    VRFTypes.RequestCommitmentV2Plus calldata rc,
    bool onlyPremium
  ) external nonReentrant returns (uint96 payment) {
    uint256 startGas = gasleft();
    // fulfillRandomWords msg.data has 772 bytes and with an additional
    // buffer of 32 bytes, we get 804 bytes.
    /* Data size split:
     * fulfillRandomWords function signature - 4 bytes
     * proof - 416 bytes
     *   pk - 64 bytes
     *   gamma - 64 bytes
     *   c - 32 bytes
     *   s - 32 bytes
     *   seed - 32 bytes
     *   uWitness - 32 bytes
     *   cGammaWitness - 64 bytes
     *   sHashWitness - 64 bytes
     *   zInv - 32 bytes
     * requestCommitment - 320 bytes
     *   blockNum - 32 bytes
     *   subId - 32 bytes
     *   callbackGasLimit - 32 bytes
     *   numWords - 32 bytes
     *   sender - 32 bytes
     *   extraArgs - 128 bytes
     * onlyPremium - 32 bytes
     */
    if (msg.data.length > 804) {
      revert MsgDataTooBig(msg.data.length, 804);
    }
    Output memory output = _getRandomnessFromProof(proof, rc);
    uint256 gasPrice = _getValidatedGasPrice(onlyPremium, output.provingKey.maxGas);

    uint256[] memory randomWords;
    uint256 randomness = output.randomness;
    // stack too deep error
    {
      uint256 numWords = rc.numWords;
      randomWords = new uint256[](numWords);
      for (uint256 i = 0; i < numWords; ++i) {
        randomWords[i] = uint256(keccak256(abi.encode(randomness, i)));
      }
    }

    delete s_requestCommitments[output.requestId];
    bool success = _deliverRandomness(output.requestId, rc, randomWords);

    // Increment the req count for the subscription.
    ++s_subscriptions[rc.subId].reqCount;
    // Decrement the pending req count for the consumer.
    --s_consumers[rc.sender][rc.subId].pendingReqCount;

    bool nativePayment = uint8(rc.extraArgs[rc.extraArgs.length - 1]) == 1;

    // stack too deep error
    {
      // We want to charge users exactly for how much gas they use in their callback with
      // an additional premium. If onlyPremium is true, only premium is charged without
      // the gas cost. The gasAfterPaymentCalculation is meant to cover these additional
      // operations where we decrement the subscription balance and increment the
      // withdrawable balance.
      bool isFeedStale;
      (payment, isFeedStale) = _calculatePaymentAmount(startGas, gasPrice, nativePayment, onlyPremium);
      if (isFeedStale) {
        emit FallbackWeiPerUnitLinkUsed(output.requestId, s_fallbackWeiPerUnitLink);
      }
    }

    _chargePayment(payment, nativePayment, rc.subId);

    // Include payment in the event for tracking costs.
    emit RandomWordsFulfilled(output.requestId, randomness, rc.subId, payment, nativePayment, success, onlyPremium);

    return payment;
  }

  function _chargePayment(uint96 payment, bool nativePayment, uint256 subId) internal {
    Subscription storage subcription = s_subscriptions[subId];
    if (nativePayment) {
      uint96 prevBal = subcription.nativeBalance;
      _requireSufficientBalance(prevBal >= payment);
      subcription.nativeBalance = prevBal - payment;
      s_withdrawableNative += payment;
    } else {
      uint96 prevBal = subcription.balance;
      _requireSufficientBalance(prevBal >= payment);
      subcription.balance = prevBal - payment;
      s_withdrawableTokens += payment;
    }
  }

  function _calculatePaymentAmount(
    uint256 startGas,
    uint256 weiPerUnitGas,
    bool nativePayment,
    bool onlyPremium
  ) internal returns (uint96, bool) {
    if (nativePayment) {
      return (_calculatePaymentAmountNative(startGas, weiPerUnitGas, onlyPremium), false);
    }
    return _calculatePaymentAmountLink(startGas, weiPerUnitGas, onlyPremium);
  }

  function _calculatePaymentAmountNative(
    uint256 startGas,
    uint256 weiPerUnitGas,
    bool onlyPremium
  ) internal returns (uint96) {
    // Will return non-zero on chains that have this enabled
    uint256 l1CostWei = _getL1CostWei(msg.data);
    // calculate the payment without the premium
    uint256 baseFeeWei = weiPerUnitGas * (s_config.gasAfterPaymentCalculation + startGas - gasleft());
    // calculate flat fee in native
    uint256 flatFeeWei = 1e12 * uint256(s_config.fulfillmentFlatFeeNativePPM);
    // emit this event only if this is an L2 chain that needs to cover for L1 gas fees
    if (l1CostWei > 0) {
      emit L1GasFee(l1CostWei);
    }
    if (onlyPremium) {
      return uint96((((l1CostWei + baseFeeWei) * (s_config.nativePremiumPercentage)) / 100) + flatFeeWei);
    } else {
      return uint96((((l1CostWei + baseFeeWei) * (100 + s_config.nativePremiumPercentage)) / 100) + flatFeeWei);
    }
  }

  // Get the amount of gas used for fulfillment
  function _calculatePaymentAmountLink(
    uint256 startGas,
    uint256 weiPerUnitGas,
    bool onlyPremium
  ) internal returns (uint96, bool) {
    (int256 weiPerUnitLink, bool isFeedStale) = _getFeedData();
    if (weiPerUnitLink <= 0) {
      revert InvalidLinkWeiPrice(weiPerUnitLink);
    }
    // Will return non-zero on chains that have this enabled
    uint256 l1CostWei = _getL1CostWei(msg.data);
    // (1e18 juels/link) ((wei/gas * gas) + l1wei) / (wei/link) = juels
    uint256 paymentNoFee = (1e18 *
      (weiPerUnitGas * (s_config.gasAfterPaymentCalculation + startGas - gasleft()) + l1CostWei)) /
      uint256(weiPerUnitLink);
    // calculate the flat fee in wei
    uint256 flatFeeWei = 1e12 *
      uint256(s_config.fulfillmentFlatFeeNativePPM - s_config.fulfillmentFlatFeeLinkDiscountPPM);
    uint256 flatFeeJuels = (1e18 * flatFeeWei) / uint256(weiPerUnitLink);
    // emit this event only if this is an L2 chain that needs to cover for L1 gas fees
    if (l1CostWei > 0) {
      emit L1GasFee(l1CostWei);
    }
    uint256 payment;
    if (onlyPremium) {
      payment = ((paymentNoFee * (s_config.linkPremiumPercentage)) / 100 + flatFeeJuels);
    } else {
      payment = ((paymentNoFee * (100 + s_config.linkPremiumPercentage)) / 100 + flatFeeJuels);
    }
    if (payment > 1e27) {
      revert PaymentTooLarge(); // Payment + fee cannot be more than all of the link in existence.
    }
    return (uint96(payment), isFeedStale);
  }

  function _getFeedData() private view returns (int256 weiPerUnitLink, bool isFeedStale) {
    uint32 stalenessSeconds = s_config.stalenessSeconds;
    uint256 timestamp;
    (, weiPerUnitLink, , timestamp, ) = LINK_NATIVE_FEED.latestRoundData();
    // solhint-disable-next-line not-rely-on-time
    isFeedStale = stalenessSeconds > 0 && stalenessSeconds < block.timestamp - timestamp;
    if (isFeedStale) {
      weiPerUnitLink = s_fallbackWeiPerUnitLink;
    }
    return (weiPerUnitLink, isFeedStale);
  }

  /**
   * @notice Returns the block number of the current block by using specific opcode.
   * @notice Override this function in chain specific way if needed (L2 chains).
   */
  function _getBlockNumber() internal view virtual returns (uint256) {
    return block.number;
  }

  /**
   * @notice Returns the blockhash for the given blockNumber by using specific opcode.
   * @notice If the blockNumber is more than 256 blocks in the past, returns the empty string.
   * @notice Override this function in chain specific way if needed (L2 chains).
   */
  function _getBlockhash(uint64 blockNumber) internal view virtual returns (bytes32) {
    return blockhash(blockNumber);
  }

  /**
   * @notice Returns the L1 fee for the calldata payload (always return 0 on L1 chains).
   * @notice Override this function in chain specific way for L2 chains.
   */
  function _getL1CostWei(bytes calldata /* data */) internal view virtual returns (uint256) {
    return 0;
  }

  /**
   * @inheritdoc IVRFSubscriptionV2Plus
   */
  function pendingRequestExists(uint256 subId) public view override returns (bool) {
    address[] storage consumers = s_subscriptionConfigs[subId].consumers;
    uint256 consumersLength = consumers.length;
    for (uint256 i = 0; i < consumersLength; ++i) {
      if (s_consumers[consumers[i]][subId].pendingReqCount > 0) {
        return true;
      }
    }
    return false;
  }

  /**
   * @inheritdoc IVRFSubscriptionV2Plus
   */
  function removeConsumer(uint256 subId, address consumer) external override onlySubOwner(subId) nonReentrant {
    if (pendingRequestExists(subId)) {
      revert PendingRequestExists();
    }
    if (!s_consumers[consumer][subId].active) {
      revert InvalidConsumer(subId, consumer);
    }
    // Note bounded by MAX_CONSUMERS
    address[] storage s_subscriptionConsumers = s_subscriptionConfigs[subId].consumers;
    uint256 consumersLength = s_subscriptionConsumers.length;
    for (uint256 i = 0; i < consumersLength; ++i) {
      if (s_subscriptionConsumers[i] == consumer) {
        // Storage write to preserve last element
        s_subscriptionConsumers[i] = s_subscriptionConsumers[consumersLength - 1];
        // Storage remove last element
        s_subscriptionConsumers.pop();
        break;
      }
    }
    s_consumers[consumer][subId].active = false;
    emit SubscriptionConsumerRemoved(subId, consumer);
  }

  /**
   * @inheritdoc IVRFSubscriptionV2Plus
   */
  function cancelSubscription(uint256 subId, address to) external override onlySubOwner(subId) nonReentrant {
    if (pendingRequestExists(subId)) {
      revert PendingRequestExists();
    }
    _cancelSubscriptionHelper(subId, to);
  }

  /***************************************************************************
   * Section: Migration
   ***************************************************************************/

  address[] internal s_migrationTargets;

  /// @dev Emitted when new coordinator is registered as migratable target
  event CoordinatorRegistered(address coordinatorAddress);

  /// @dev Emitted when new coordinator is deregistered
  event CoordinatorDeregistered(address coordinatorAddress);

  /// @notice emitted when migration to new coordinator completes successfully
  /// @param newCoordinator coordinator address after migration
  /// @param subId subscription ID
  event MigrationCompleted(address newCoordinator, uint256 subId);

  /// @notice emitted when migrate() is called and given coordinator is not registered as migratable target
  error CoordinatorNotRegistered(address coordinatorAddress);

  /// @notice emitted when migrate() is called and given coordinator is registered as migratable target
  error CoordinatorAlreadyRegistered(address coordinatorAddress);

  /// @dev encapsulates data to be migrated from current coordinator
  // solhint-disable-next-line gas-struct-packing
  struct V1MigrationData {
    uint8 fromVersion;
    uint256 subId;
    address subOwner;
    address[] consumers;
    uint96 linkBalance;
    uint96 nativeBalance;
  }

  function _isTargetRegistered(address target) internal view returns (bool) {
    uint256 migrationTargetsLength = s_migrationTargets.length;
    for (uint256 i = 0; i < migrationTargetsLength; ++i) {
      if (s_migrationTargets[i] == target) {
        return true;
      }
    }
    return false;
  }

  function registerMigratableCoordinator(address target) external onlyOwner {
    if (_isTargetRegistered(target)) {
      revert CoordinatorAlreadyRegistered(target);
    }
    s_migrationTargets.push(target);
    emit CoordinatorRegistered(target);
  }

  function deregisterMigratableCoordinator(address target) external onlyOwner {
    uint256 nTargets = s_migrationTargets.length;
    for (uint256 i = 0; i < nTargets; ++i) {
      if (s_migrationTargets[i] == target) {
        s_migrationTargets[i] = s_migrationTargets[nTargets - 1];
        s_migrationTargets.pop();
        emit CoordinatorDeregistered(target);
        return;
      }
    }
    revert CoordinatorNotRegistered(target);
  }

  function migrate(uint256 subId, address newCoordinator) external nonReentrant {
    if (!_isTargetRegistered(newCoordinator)) {
      revert CoordinatorNotRegistered(newCoordinator);
    }
    (uint96 balance, uint96 nativeBalance, , address subOwner, address[] memory consumers) = getSubscription(subId);
    if (subOwner != msg.sender) {
      revert MustBeSubOwner(subOwner);
    }
    if (pendingRequestExists(subId)) {
      revert PendingRequestExists();
    }

    V1MigrationData memory migrationData = V1MigrationData({
      fromVersion: 1,
      subId: subId,
      subOwner: subOwner,
      consumers: consumers,
      linkBalance: balance,
      nativeBalance: nativeBalance
    });
    bytes memory encodedData = abi.encode(migrationData);
    _deleteSubscription(subId);
    IVRFCoordinatorV2PlusMigration(newCoordinator).onMigration{value: nativeBalance}(encodedData);

    // Only transfer LINK if the token is active and there is a balance.
    if (address(LINK) != address(0) && balance != 0) {
      _requireSufficientBalance(LINK.transfer(address(newCoordinator), balance));
    }

    // despite the fact that we follow best practices this is still probably safest
    // to prevent any re-entrancy possibilities.
    s_config.reentrancyLock = true;
    uint256 consumersLength = consumers.length;
    for (uint256 i = 0; i < consumersLength; ++i) {
      IVRFMigratableConsumerV2Plus(consumers[i]).setCoordinator(newCoordinator);
    }
    s_config.reentrancyLock = false;

    emit MigrationCompleted(newCoordinator, subId);
  }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.19;

import {VRFCoordinatorV2_5} from "./VRFCoordinatorV2_5.sol";
import {OptimismL1Fees} from "./OptimismL1Fees.sol";

/// @dev VRFCoordinatorV2_5_Optimism combines VRFCoordinatorV2_5 base contract with
/// @dev Optimism specific opcodes and L1 gas fee calculations.
/// @dev This coordinator contract is used for all chains in the OP stack (e.g. Base).
// solhint-disable-next-line contract-name-camelcase
contract VRFCoordinatorV2_5_Optimism is VRFCoordinatorV2_5, OptimismL1Fees {
  constructor(address blockhashStore) VRFCoordinatorV2_5(blockhashStore) {}

  /// @notice no need to override getBlockhash and getBlockNumber from VRFCoordinatorV2_5
  /// @notice on OP stack, they will work with the default implementation

  /// @notice Override getL1CostWei function from VRFCoordinatorV2_5 to activate Optimism getL1Fee computation
  function _getL1CostWei(bytes calldata data) internal view override returns (uint256) {
    return _getL1CostWeiForCalldata(data);
  }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.6;

/**
 * @title VRFTypes
 * @notice The VRFTypes library is a collection of types that is required to fulfill VRF requests
 * 	on-chain. They must be ABI-compatible with the types used by the coordinator contracts.
 */
library VRFTypes {
  // ABI-compatible with VRF.Proof.
  // This proof is used for VRF V2 and V2Plus.
  struct Proof {
    uint256[2] pk;
    uint256[2] gamma;
    uint256 c;
    uint256 s;
    uint256 seed;
    address uWitness;
    uint256[2] cGammaWitness;
    uint256[2] sHashWitness;
    uint256 zInv;
  }

  // ABI-compatible with VRFCoordinatorV2.RequestCommitment.
  // This is only used for VRF V2.
  struct RequestCommitment {
    uint64 blockNum;
    uint64 subId;
    uint32 callbackGasLimit;
    uint32 numWords;
    address sender;
  }

  // ABI-compatible with VRFCoordinatorV2Plus.RequestCommitment.
  // This is only used for VRF V2Plus.
  struct RequestCommitmentV2Plus {
    uint64 blockNum;
    uint256 subId;
    uint32 callbackGasLimit;
    uint32 numWords;
    address sender;
    bytes extraArgs;
  }
}

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.4;

// End consumer library.
library VRFV2PlusClient {
  // extraArgs will evolve to support new features
  bytes4 public constant EXTRA_ARGS_V1_TAG = bytes4(keccak256("VRF ExtraArgsV1"));
  struct ExtraArgsV1 {
    bool nativePayment;
  }

  struct RandomWordsRequest {
    bytes32 keyHash;
    uint256 subId;
    uint16 requestConfirmations;
    uint32 callbackGasLimit;
    uint32 numWords;
    bytes extraArgs;
  }

  function _argsToBytes(ExtraArgsV1 memory extraArgs) internal pure returns (bytes memory bts) {
    return abi.encodeWithSelector(EXTRA_ARGS_V1_TAG, extraArgs);
  }
}

{
  "compilationTarget": {
    "src/v0.8/vrf/dev/VRFCoordinatorV2_5_Optimism.sol": "VRFCoordinatorV2_5_Optimism"
  },
  "evmVersion": "paris",
  "libraries": {},
  "metadata": {
    "bytecodeHash": "none"
  },
  "optimizer": {
    "enabled": true,
    "runs": 500
  },
  "remappings": [
    ":@eth-optimism/=node_modules/@eth-optimism/",
    ":@openzeppelin/=src/v0.8/vendor/openzeppelin-solidity/v4.9.3/",
    ":@scroll-tech/=node_modules/@scroll-tech/",
    ":forge-std/=src/v0.8/vendor/forge-std/src/",
    ":hardhat/=node_modules/hardhat/"
  ]
}