// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.7.0) (access/Ownable.sol)
pragma solidity ^0.8.0;
import "../utils/Context.sol";
/**
 * @dev Contract module which provides a basic access control mechanism, where
 * there is an account (an owner) that can be granted exclusive access to
 * specific functions.
 *
 * By default, the owner account will be the one that deploys the contract. This
 * can later be changed with {transferOwnership}.
 *
 * This module is used through inheritance. It will make available the modifier
 * `onlyOwner`, which can be applied to your functions to restrict their use to
 * the owner.
 */
abstract contract Ownable is Context {
    address private _owner;
    event OwnershipTransferred(address indexed previousOwner, address indexed newOwner);
    /**
     * @dev Initializes the contract setting the deployer as the initial owner.
     */
    constructor() {
        _transferOwnership(_msgSender());
    }
    /**
     * @dev Throws if called by any account other than the owner.
     */
    modifier onlyOwner() {
        _checkOwner();
        _;
    }
    /**
     * @dev Returns the address of the current owner.
     */
    function owner() public view virtual returns (address) {
        return _owner;
    }
    /**
     * @dev Throws if the sender is not the owner.
     */
    function _checkOwner() internal view virtual {
        require(owner() == _msgSender(), "Ownable: caller is not the owner");
    }
    /**
     * @dev Leaves the contract without owner. It will not be possible to call
     * `onlyOwner` functions anymore. Can only be called by the current owner.
     *
     * NOTE: Renouncing ownership will leave the contract without an owner,
     * thereby removing any functionality that is only available to the owner.
     */
    function renounceOwnership() public virtual onlyOwner {
        _transferOwnership(address(0));
    }
    /**
     * @dev Transfers ownership of the contract to a new account (`newOwner`).
     * Can only be called by the current owner.
     */
    function transferOwnership(address newOwner) public virtual onlyOwner {
        require(newOwner != address(0), "Ownable: new owner is the zero address");
        _transferOwnership(newOwner);
    }
    /**
     * @dev Transfers ownership of the contract to a new account (`newOwner`).
     * Internal function without access restriction.
     */
    function _transferOwnership(address newOwner) internal virtual {
        address oldOwner = _owner;
        _owner = newOwner;
        emit OwnershipTransferred(oldOwner, newOwner);
    }
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.5.0) (interfaces/draft-IERC1822.sol)
pragma solidity ^0.8.0;
/**
 * @dev ERC1822: Universal Upgradeable Proxy Standard (UUPS) documents a method for upgradeability through a simplified
 * proxy whose upgrades are fully controlled by the current implementation.
 */
interface IERC1822Proxiable {
    /**
     * @dev Returns the storage slot that the proxiable contract assumes is being used to store the implementation
     * address.
     *
     * IMPORTANT: A proxy pointing at a proxiable contract should not be considered proxiable itself, because this risks
     * bricking a proxy that upgrades to it, by delegating to itself until out of gas. Thus it is critical that this
     * function revert if invoked through a proxy.
     */
    function proxiableUUID() external view returns (bytes32);
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.3) (interfaces/IERC1967.sol)
pragma solidity ^0.8.0;
/**
 * @dev ERC-1967: Proxy Storage Slots. This interface contains the events defined in the ERC.
 *
 * _Available since v4.9._
 */
interface IERC1967 {
    /**
     * @dev Emitted when the implementation is upgraded.
     */
    event Upgraded(address indexed implementation);
    /**
     * @dev Emitted when the admin account has changed.
     */
    event AdminChanged(address previousAdmin, address newAdmin);
    /**
     * @dev Emitted when the beacon is changed.
     */
    event BeaconUpgraded(address indexed beacon);
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.7.0) (proxy/beacon/BeaconProxy.sol)
pragma solidity ^0.8.0;
import "./IBeacon.sol";
import "../Proxy.sol";
import "../ERC1967/ERC1967Upgrade.sol";
/**
 * @dev This contract implements a proxy that gets the implementation address for each call from an {UpgradeableBeacon}.
 *
 * The beacon address is stored in storage slot `uint256(keccak256('eip1967.proxy.beacon')) - 1`, so that it doesn't
 * conflict with the storage layout of the implementation behind the proxy.
 *
 * _Available since v3.4._
 */
contract BeaconProxy is Proxy, ERC1967Upgrade {
    /**
     * @dev Initializes the proxy with `beacon`.
     *
     * If `data` is nonempty, it's used as data in a delegate call to the implementation returned by the beacon. This
     * will typically be an encoded function call, and allows initializing the storage of the proxy like a Solidity
     * constructor.
     *
     * Requirements:
     *
     * - `beacon` must be a contract with the interface {IBeacon}.
     */
    constructor(address beacon, bytes memory data) payable {
        _upgradeBeaconToAndCall(beacon, data, false);
    }
    /**
     * @dev Returns the current beacon address.
     */
    function _beacon() internal view virtual returns (address) {
        return _getBeacon();
    }
    /**
     * @dev Returns the current implementation address of the associated beacon.
     */
    function _implementation() internal view virtual override returns (address) {
        return IBeacon(_getBeacon()).implementation();
    }
    /**
     * @dev Changes the proxy to use a new beacon. Deprecated: see {_upgradeBeaconToAndCall}.
     *
     * If `data` is nonempty, it's used as data in a delegate call to the implementation returned by the beacon.
     *
     * Requirements:
     *
     * - `beacon` must be a contract.
     * - The implementation returned by `beacon` must be a contract.
     */
    function _setBeacon(address beacon, bytes memory data) internal virtual {
        _upgradeBeaconToAndCall(beacon, data, false);
    }
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (proxy/beacon/IBeacon.sol)
pragma solidity ^0.8.0;
/**
 * @dev This is the interface that {BeaconProxy} expects of its beacon.
 */
interface IBeacon {
    /**
     * @dev Must return an address that can be used as a delegate call target.
     *
     * {BeaconProxy} will check that this address is a contract.
     */
    function implementation() external view returns (address);
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (proxy/beacon/UpgradeableBeacon.sol)
pragma solidity ^0.8.0;
import "./IBeacon.sol";
import "../../access/Ownable.sol";
import "../../utils/Address.sol";
/**
 * @dev This contract is used in conjunction with one or more instances of {BeaconProxy} to determine their
 * implementation contract, which is where they will delegate all function calls.
 *
 * An owner is able to change the implementation the beacon points to, thus upgrading the proxies that use this beacon.
 */
contract UpgradeableBeacon is IBeacon, Ownable {
    address private _implementation;
    /**
     * @dev Emitted when the implementation returned by the beacon is changed.
     */
    event Upgraded(address indexed implementation);
    /**
     * @dev Sets the address of the initial implementation, and the deployer account as the owner who can upgrade the
     * beacon.
     */
    constructor(address implementation_) {
        _setImplementation(implementation_);
    }
    /**
     * @dev Returns the current implementation address.
     */
    function implementation() public view virtual override returns (address) {
        return _implementation;
    }
    /**
     * @dev Upgrades the beacon to a new implementation.
     *
     * Emits an {Upgraded} event.
     *
     * Requirements:
     *
     * - msg.sender must be the owner of the contract.
     * - `newImplementation` must be a contract.
     */
    function upgradeTo(address newImplementation) public virtual onlyOwner {
        _setImplementation(newImplementation);
        emit Upgraded(newImplementation);
    }
    /**
     * @dev Sets the implementation contract address for this beacon
     *
     * Requirements:
     *
     * - `newImplementation` must be a contract.
     */
    function _setImplementation(address newImplementation) private {
        require(Address.isContract(newImplementation), "UpgradeableBeacon: implementation is not a contract");
        _implementation = newImplementation;
    }
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.7.0) (proxy/ERC1967/ERC1967Proxy.sol)
pragma solidity ^0.8.0;
import "../Proxy.sol";
import "./ERC1967Upgrade.sol";
/**
 * @dev This contract implements an upgradeable proxy. It is upgradeable because calls are delegated to an
 * implementation address that can be changed. This address is stored in storage in the location specified by
 * https://eips.ethereum.org/EIPS/eip-1967[EIP1967], so that it doesn't conflict with the storage layout of the
 * implementation behind the proxy.
 */
contract ERC1967Proxy is Proxy, ERC1967Upgrade {
    /**
     * @dev Initializes the upgradeable proxy with an initial implementation specified by `_logic`.
     *
     * If `_data` is nonempty, it's used as data in a delegate call to `_logic`. This will typically be an encoded
     * function call, and allows initializing the storage of the proxy like a Solidity constructor.
     */
    constructor(address _logic, bytes memory _data) payable {
        _upgradeToAndCall(_logic, _data, false);
    }
    /**
     * @dev Returns the current implementation address.
     */
    function _implementation() internal view virtual override returns (address impl) {
        return ERC1967Upgrade._getImplementation();
    }
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.3) (proxy/ERC1967/ERC1967Upgrade.sol)
pragma solidity ^0.8.2;
import "../beacon/IBeacon.sol";
import "../../interfaces/IERC1967.sol";
import "../../interfaces/draft-IERC1822.sol";
import "../../utils/Address.sol";
import "../../utils/StorageSlot.sol";
/**
 * @dev This abstract contract provides getters and event emitting update functions for
 * https://eips.ethereum.org/EIPS/eip-1967[EIP1967] slots.
 *
 * _Available since v4.1._
 *
 * @custom:oz-upgrades-unsafe-allow delegatecall
 */
abstract contract ERC1967Upgrade is IERC1967 {
    // This is the keccak-256 hash of "eip1967.proxy.rollback" subtracted by 1
    bytes32 private constant _ROLLBACK_SLOT = 0x4910fdfa16fed3260ed0e7147f7cc6da11a60208b5b9406d12a635614ffd9143;
    /**
     * @dev Storage slot with the address of the current implementation.
     * This is the keccak-256 hash of "eip1967.proxy.implementation" subtracted by 1, and is
     * validated in the constructor.
     */
    bytes32 internal constant _IMPLEMENTATION_SLOT = 0x360894a13ba1a3210667c828492db98dca3e2076cc3735a920a3ca505d382bbc;
    /**
     * @dev Returns the current implementation address.
     */
    function _getImplementation() internal view returns (address) {
        return StorageSlot.getAddressSlot(_IMPLEMENTATION_SLOT).value;
    }
    /**
     * @dev Stores a new address in the EIP1967 implementation slot.
     */
    function _setImplementation(address newImplementation) private {
        require(Address.isContract(newImplementation), "ERC1967: new implementation is not a contract");
        StorageSlot.getAddressSlot(_IMPLEMENTATION_SLOT).value = newImplementation;
    }
    /**
     * @dev Perform implementation upgrade
     *
     * Emits an {Upgraded} event.
     */
    function _upgradeTo(address newImplementation) internal {
        _setImplementation(newImplementation);
        emit Upgraded(newImplementation);
    }
    /**
     * @dev Perform implementation upgrade with additional setup call.
     *
     * Emits an {Upgraded} event.
     */
    function _upgradeToAndCall(
        address newImplementation,
        bytes memory data,
        bool forceCall
    ) internal {
        _upgradeTo(newImplementation);
        if (data.length > 0 || forceCall) {
            Address.functionDelegateCall(newImplementation, data);
        }
    }
    /**
     * @dev Perform implementation upgrade with security checks for UUPS proxies, and additional setup call.
     *
     * Emits an {Upgraded} event.
     */
    function _upgradeToAndCallUUPS(
        address newImplementation,
        bytes memory data,
        bool forceCall
    ) internal {
        // Upgrades from old implementations will perform a rollback test. This test requires the new
        // implementation to upgrade back to the old, non-ERC1822 compliant, implementation. Removing
        // this special case will break upgrade paths from old UUPS implementation to new ones.
        if (StorageSlot.getBooleanSlot(_ROLLBACK_SLOT).value) {
            _setImplementation(newImplementation);
        } else {
            try IERC1822Proxiable(newImplementation).proxiableUUID() returns (bytes32 slot) {
                require(slot == _IMPLEMENTATION_SLOT, "ERC1967Upgrade: unsupported proxiableUUID");
            } catch {
                revert("ERC1967Upgrade: new implementation is not UUPS");
            }
            _upgradeToAndCall(newImplementation, data, forceCall);
        }
    }
    /**
     * @dev Storage slot with the admin of the contract.
     * This is the keccak-256 hash of "eip1967.proxy.admin" subtracted by 1, and is
     * validated in the constructor.
     */
    bytes32 internal constant _ADMIN_SLOT = 0xb53127684a568b3173ae13b9f8a6016e243e63b6e8ee1178d6a717850b5d6103;
    /**
     * @dev Returns the current admin.
     */
    function _getAdmin() internal view returns (address) {
        return StorageSlot.getAddressSlot(_ADMIN_SLOT).value;
    }
    /**
     * @dev Stores a new address in the EIP1967 admin slot.
     */
    function _setAdmin(address newAdmin) private {
        require(newAdmin != address(0), "ERC1967: new admin is the zero address");
        StorageSlot.getAddressSlot(_ADMIN_SLOT).value = newAdmin;
    }
    /**
     * @dev Changes the admin of the proxy.
     *
     * Emits an {AdminChanged} event.
     */
    function _changeAdmin(address newAdmin) internal {
        emit AdminChanged(_getAdmin(), newAdmin);
        _setAdmin(newAdmin);
    }
    /**
     * @dev The storage slot of the UpgradeableBeacon contract which defines the implementation for this proxy.
     * This is bytes32(uint256(keccak256('eip1967.proxy.beacon')) - 1)) and is validated in the constructor.
     */
    bytes32 internal constant _BEACON_SLOT = 0xa3f0ad74e5423aebfd80d3ef4346578335a9a72aeaee59ff6cb3582b35133d50;
    /**
     * @dev Returns the current beacon.
     */
    function _getBeacon() internal view returns (address) {
        return StorageSlot.getAddressSlot(_BEACON_SLOT).value;
    }
    /**
     * @dev Stores a new beacon in the EIP1967 beacon slot.
     */
    function _setBeacon(address newBeacon) private {
        require(Address.isContract(newBeacon), "ERC1967: new beacon is not a contract");
        require(
            Address.isContract(IBeacon(newBeacon).implementation()),
            "ERC1967: beacon implementation is not a contract"
        );
        StorageSlot.getAddressSlot(_BEACON_SLOT).value = newBeacon;
    }
    /**
     * @dev Perform beacon upgrade with additional setup call. Note: This upgrades the address of the beacon, it does
     * not upgrade the implementation contained in the beacon (see {UpgradeableBeacon-_setImplementation} for that).
     *
     * Emits a {BeaconUpgraded} event.
     */
    function _upgradeBeaconToAndCall(
        address newBeacon,
        bytes memory data,
        bool forceCall
    ) internal {
        _setBeacon(newBeacon);
        emit BeaconUpgraded(newBeacon);
        if (data.length > 0 || forceCall) {
            Address.functionDelegateCall(IBeacon(newBeacon).implementation(), data);
        }
    }
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.6.0) (proxy/Proxy.sol)
pragma solidity ^0.8.0;
/**
 * @dev This abstract contract provides a fallback function that delegates all calls to another contract using the EVM
 * instruction `delegatecall`. We refer to the second contract as the _implementation_ behind the proxy, and it has to
 * be specified by overriding the virtual {_implementation} function.
 *
 * Additionally, delegation to the implementation can be triggered manually through the {_fallback} function, or to a
 * different contract through the {_delegate} function.
 *
 * The success and return data of the delegated call will be returned back to the caller of the proxy.
 */
abstract contract Proxy {
    /**
     * @dev Delegates the current call to `implementation`.
     *
     * This function does not return to its internal call site, it will return directly to the external caller.
     */
    function _delegate(address implementation) internal virtual {
        assembly {
            // Copy msg.data. We take full control of memory in this inline assembly
            // block because it will not return to Solidity code. We overwrite the
            // Solidity scratch pad at memory position 0.
            calldatacopy(0, 0, calldatasize())
            // Call the implementation.
            // out and outsize are 0 because we don't know the size yet.
            let result := delegatecall(gas(), implementation, 0, calldatasize(), 0, 0)
            // Copy the returned data.
            returndatacopy(0, 0, returndatasize())
            switch result
            // delegatecall returns 0 on error.
            case 0 {
                revert(0, returndatasize())
            }
            default {
                return(0, returndatasize())
            }
        }
    }
    /**
     * @dev This is a virtual function that should be overridden so it returns the address to which the fallback function
     * and {_fallback} should delegate.
     */
    function _implementation() internal view virtual returns (address);
    /**
     * @dev Delegates the current call to the address returned by `_implementation()`.
     *
     * This function does not return to its internal call site, it will return directly to the external caller.
     */
    function _fallback() internal virtual {
        _beforeFallback();
        _delegate(_implementation());
    }
    /**
     * @dev Fallback function that delegates calls to the address returned by `_implementation()`. Will run if no other
     * function in the contract matches the call data.
     */
    fallback() external payable virtual {
        _fallback();
    }
    /**
     * @dev Fallback function that delegates calls to the address returned by `_implementation()`. Will run if call data
     * is empty.
     */
    receive() external payable virtual {
        _fallback();
    }
    /**
     * @dev Hook that is called before falling back to the implementation. Can happen as part of a manual `_fallback`
     * call, or as part of the Solidity `fallback` or `receive` functions.
     *
     * If overridden should call `super._beforeFallback()`.
     */
    function _beforeFallback() internal virtual {}
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.3) (proxy/transparent/ProxyAdmin.sol)
pragma solidity ^0.8.0;
import "./TransparentUpgradeableProxy.sol";
import "../../access/Ownable.sol";
/**
 * @dev This is an auxiliary contract meant to be assigned as the admin of a {TransparentUpgradeableProxy}. For an
 * explanation of why you would want to use this see the documentation for {TransparentUpgradeableProxy}.
 */
contract ProxyAdmin is Ownable {
    /**
     * @dev Returns the current implementation of `proxy`.
     *
     * Requirements:
     *
     * - This contract must be the admin of `proxy`.
     */
    function getProxyImplementation(ITransparentUpgradeableProxy proxy) public view virtual returns (address) {
        // We need to manually run the static call since the getter cannot be flagged as view
        // bytes4(keccak256("implementation()")) == 0x5c60da1b
        (bool success, bytes memory returndata) = address(proxy).staticcall(hex"5c60da1b");
        require(success);
        return abi.decode(returndata, (address));
    }
    /**
     * @dev Returns the current admin of `proxy`.
     *
     * Requirements:
     *
     * - This contract must be the admin of `proxy`.
     */
    function getProxyAdmin(ITransparentUpgradeableProxy proxy) public view virtual returns (address) {
        // We need to manually run the static call since the getter cannot be flagged as view
        // bytes4(keccak256("admin()")) == 0xf851a440
        (bool success, bytes memory returndata) = address(proxy).staticcall(hex"f851a440");
        require(success);
        return abi.decode(returndata, (address));
    }
    /**
     * @dev Changes the admin of `proxy` to `newAdmin`.
     *
     * Requirements:
     *
     * - This contract must be the current admin of `proxy`.
     */
    function changeProxyAdmin(ITransparentUpgradeableProxy proxy, address newAdmin) public virtual onlyOwner {
        proxy.changeAdmin(newAdmin);
    }
    /**
     * @dev Upgrades `proxy` to `implementation`. See {TransparentUpgradeableProxy-upgradeTo}.
     *
     * Requirements:
     *
     * - This contract must be the admin of `proxy`.
     */
    function upgrade(ITransparentUpgradeableProxy proxy, address implementation) public virtual onlyOwner {
        proxy.upgradeTo(implementation);
    }
    /**
     * @dev Upgrades `proxy` to `implementation` and calls a function on the new implementation. See
     * {TransparentUpgradeableProxy-upgradeToAndCall}.
     *
     * Requirements:
     *
     * - This contract must be the admin of `proxy`.
     */
    function upgradeAndCall(
        ITransparentUpgradeableProxy proxy,
        address implementation,
        bytes memory data
    ) public payable virtual onlyOwner {
        proxy.upgradeToAndCall{value: msg.value}(implementation, data);
    }
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.3) (proxy/transparent/TransparentUpgradeableProxy.sol)
pragma solidity ^0.8.0;
import "../ERC1967/ERC1967Proxy.sol";
/**
 * @dev Interface for {TransparentUpgradeableProxy}. In order to implement transparency, {TransparentUpgradeableProxy}
 * does not implement this interface directly, and some of its functions are implemented by an internal dispatch
 * mechanism. The compiler is unaware that these functions are implemented by {TransparentUpgradeableProxy} and will not
 * include them in the ABI so this interface must be used to interact with it.
 */
interface ITransparentUpgradeableProxy is IERC1967 {
    function admin() external view returns (address);
    function implementation() external view returns (address);
    function changeAdmin(address) external;
    function upgradeTo(address) external;
    function upgradeToAndCall(address, bytes memory) external payable;
}
/**
 * @dev This contract implements a proxy that is upgradeable by an admin.
 *
 * To avoid https://medium.com/nomic-labs-blog/malicious-backdoors-in-ethereum-proxies-62629adf3357[proxy selector
 * clashing], which can potentially be used in an attack, this contract uses the
 * https://blog.openzeppelin.com/the-transparent-proxy-pattern/[transparent proxy pattern]. This pattern implies two
 * things that go hand in hand:
 *
 * 1. If any account other than the admin calls the proxy, the call will be forwarded to the implementation, even if
 * that call matches one of the admin functions exposed by the proxy itself.
 * 2. If the admin calls the proxy, it can access the admin functions, but its calls will never be forwarded to the
 * implementation. If the admin tries to call a function on the implementation it will fail with an error that says
 * "admin cannot fallback to proxy target".
 *
 * These properties mean that the admin account can only be used for admin actions like upgrading the proxy or changing
 * the admin, so it's best if it's a dedicated account that is not used for anything else. This will avoid headaches due
 * to sudden errors when trying to call a function from the proxy implementation.
 *
 * Our recommendation is for the dedicated account to be an instance of the {ProxyAdmin} contract. If set up this way,
 * you should think of the `ProxyAdmin` instance as the real administrative interface of your proxy.
 *
 * NOTE: The real interface of this proxy is that defined in `ITransparentUpgradeableProxy`. This contract does not
 * inherit from that interface, and instead the admin functions are implicitly implemented using a custom dispatch
 * mechanism in `_fallback`. Consequently, the compiler will not produce an ABI for this contract. This is necessary to
 * fully implement transparency without decoding reverts caused by selector clashes between the proxy and the
 * implementation.
 *
 * WARNING: It is not recommended to extend this contract to add additional external functions. If you do so, the compiler
 * will not check that there are no selector conflicts, due to the note above. A selector clash between any new function
 * and the functions declared in {ITransparentUpgradeableProxy} will be resolved in favor of the new one. This could
 * render the admin operations inaccessible, which could prevent upgradeability. Transparency may also be compromised.
 */
contract TransparentUpgradeableProxy is ERC1967Proxy {
    /**
     * @dev Initializes an upgradeable proxy managed by `_admin`, backed by the implementation at `_logic`, and
     * optionally initialized with `_data` as explained in {ERC1967Proxy-constructor}.
     */
    constructor(
        address _logic,
        address admin_,
        bytes memory _data
    ) payable ERC1967Proxy(_logic, _data) {
        _changeAdmin(admin_);
    }
    /**
     * @dev Modifier used internally that will delegate the call to the implementation unless the sender is the admin.
     *
     * CAUTION: This modifier is deprecated, as it could cause issues if the modified function has arguments, and the
     * implementation provides a function with the same selector.
     */
    modifier ifAdmin() {
        if (msg.sender == _getAdmin()) {
            _;
        } else {
            _fallback();
        }
    }
    /**
     * @dev If caller is the admin process the call internally, otherwise transparently fallback to the proxy behavior
     */
    function _fallback() internal virtual override {
        if (msg.sender == _getAdmin()) {
            bytes memory ret;
            bytes4 selector = msg.sig;
            if (selector == ITransparentUpgradeableProxy.upgradeTo.selector) {
                ret = _dispatchUpgradeTo();
            } else if (selector == ITransparentUpgradeableProxy.upgradeToAndCall.selector) {
                ret = _dispatchUpgradeToAndCall();
            } else if (selector == ITransparentUpgradeableProxy.changeAdmin.selector) {
                ret = _dispatchChangeAdmin();
            } else if (selector == ITransparentUpgradeableProxy.admin.selector) {
                ret = _dispatchAdmin();
            } else if (selector == ITransparentUpgradeableProxy.implementation.selector) {
                ret = _dispatchImplementation();
            } else {
                revert("TransparentUpgradeableProxy: admin cannot fallback to proxy target");
            }
            assembly {
                return(add(ret, 0x20), mload(ret))
            }
        } else {
            super._fallback();
        }
    }
    /**
     * @dev Returns the current admin.
     *
     * TIP: To get this value clients can read directly from the storage slot shown below (specified by EIP1967) using the
     * https://eth.wiki/json-rpc/API#eth_getstorageat[`eth_getStorageAt`] RPC call.
     * `0xb53127684a568b3173ae13b9f8a6016e243e63b6e8ee1178d6a717850b5d6103`
     */
    function _dispatchAdmin() private returns (bytes memory) {
        _requireZeroValue();
        address admin = _getAdmin();
        return abi.encode(admin);
    }
    /**
     * @dev Returns the current implementation.
     *
     * TIP: To get this value clients can read directly from the storage slot shown below (specified by EIP1967) using the
     * https://eth.wiki/json-rpc/API#eth_getstorageat[`eth_getStorageAt`] RPC call.
     * `0x360894a13ba1a3210667c828492db98dca3e2076cc3735a920a3ca505d382bbc`
     */
    function _dispatchImplementation() private returns (bytes memory) {
        _requireZeroValue();
        address implementation = _implementation();
        return abi.encode(implementation);
    }
    /**
     * @dev Changes the admin of the proxy.
     *
     * Emits an {AdminChanged} event.
     */
    function _dispatchChangeAdmin() private returns (bytes memory) {
        _requireZeroValue();
        address newAdmin = abi.decode(msg.data[4:], (address));
        _changeAdmin(newAdmin);
        return "";
    }
    /**
     * @dev Upgrade the implementation of the proxy.
     */
    function _dispatchUpgradeTo() private returns (bytes memory) {
        _requireZeroValue();
        address newImplementation = abi.decode(msg.data[4:], (address));
        _upgradeToAndCall(newImplementation, bytes(""), false);
        return "";
    }
    /**
     * @dev Upgrade the implementation of the proxy, and then call a function from the new implementation as specified
     * by `data`, which should be an encoded function call. This is useful to initialize new storage variables in the
     * proxied contract.
     */
    function _dispatchUpgradeToAndCall() private returns (bytes memory) {
        (address newImplementation, bytes memory data) = abi.decode(msg.data[4:], (address, bytes));
        _upgradeToAndCall(newImplementation, data, true);
        return "";
    }
    /**
     * @dev Returns the current admin.
     */
    function _admin() internal view virtual returns (address) {
        return _getAdmin();
    }
    /**
     * @dev To keep this contract fully transparent, all `ifAdmin` functions must be payable. This helper is here to
     * emulate some proxy functions being non-payable while still allowing value to pass through.
     */
    function _requireZeroValue() private {
        require(msg.value == 0);
    }
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.0) (utils/Address.sol)
pragma solidity ^0.8.1;
/**
 * @dev Collection of functions related to the address type
 */
library Address {
    /**
     * @dev Returns true if `account` is a contract.
     *
     * [IMPORTANT]
     * ====
     * It is unsafe to assume that an address for which this function returns
     * false is an externally-owned account (EOA) and not a contract.
     *
     * Among others, `isContract` will return false for the following
     * types of addresses:
     *
     *  - an externally-owned account
     *  - a contract in construction
     *  - an address where a contract will be created
     *  - an address where a contract lived, but was destroyed
     * ====
     *
     * [IMPORTANT]
     * ====
     * You shouldn't rely on `isContract` to protect against flash loan attacks!
     *
     * Preventing calls from contracts is highly discouraged. It breaks composability, breaks support for smart wallets
     * like Gnosis Safe, and does not provide security since it can be circumvented by calling from a contract
     * constructor.
     * ====
     */
    function isContract(address account) internal view returns (bool) {
        // This method relies on extcodesize/address.code.length, which returns 0
        // for contracts in construction, since the code is only stored at the end
        // of the constructor execution.
        return account.code.length > 0;
    }
    /**
     * @dev Replacement for Solidity's `transfer`: sends `amount` wei to
     * `recipient`, forwarding all available gas and reverting on errors.
     *
     * https://eips.ethereum.org/EIPS/eip-1884[EIP1884] increases the gas cost
     * of certain opcodes, possibly making contracts go over the 2300 gas limit
     * imposed by `transfer`, making them unable to receive funds via
     * `transfer`. {sendValue} removes this limitation.
     *
     * https://diligence.consensys.net/posts/2019/09/stop-using-soliditys-transfer-now/[Learn more].
     *
     * IMPORTANT: because control is transferred to `recipient`, care must be
     * taken to not create reentrancy vulnerabilities. Consider using
     * {ReentrancyGuard} or the
     * https://solidity.readthedocs.io/en/v0.5.11/security-considerations.html#use-the-checks-effects-interactions-pattern[checks-effects-interactions pattern].
     */
    function sendValue(address payable recipient, uint256 amount) internal {
        require(address(this).balance >= amount, "Address: insufficient balance");
        (bool success, ) = recipient.call{value: amount}("");
        require(success, "Address: unable to send value, recipient may have reverted");
    }
    /**
     * @dev Performs a Solidity function call using a low level `call`. A
     * plain `call` is an unsafe replacement for a function call: use this
     * function instead.
     *
     * If `target` reverts with a revert reason, it is bubbled up by this
     * function (like regular Solidity function calls).
     *
     * Returns the raw returned data. To convert to the expected return value,
     * use https://solidity.readthedocs.io/en/latest/units-and-global-variables.html?highlight=abi.decode#abi-encoding-and-decoding-functions[`abi.decode`].
     *
     * Requirements:
     *
     * - `target` must be a contract.
     * - calling `target` with `data` must not revert.
     *
     * _Available since v3.1._
     */
    function functionCall(address target, bytes memory data) internal returns (bytes memory) {
        return functionCallWithValue(target, data, 0, "Address: low-level call failed");
    }
    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`], but with
     * `errorMessage` as a fallback revert reason when `target` reverts.
     *
     * _Available since v3.1._
     */
    function functionCall(
        address target,
        bytes memory data,
        string memory errorMessage
    ) internal returns (bytes memory) {
        return functionCallWithValue(target, data, 0, errorMessage);
    }
    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
     * but also transferring `value` wei to `target`.
     *
     * Requirements:
     *
     * - the calling contract must have an ETH balance of at least `value`.
     * - the called Solidity function must be `payable`.
     *
     * _Available since v3.1._
     */
    function functionCallWithValue(
        address target,
        bytes memory data,
        uint256 value
    ) internal returns (bytes memory) {
        return functionCallWithValue(target, data, value, "Address: low-level call with value failed");
    }
    /**
     * @dev Same as {xref-Address-functionCallWithValue-address-bytes-uint256-}[`functionCallWithValue`], but
     * with `errorMessage` as a fallback revert reason when `target` reverts.
     *
     * _Available since v3.1._
     */
    function functionCallWithValue(
        address target,
        bytes memory data,
        uint256 value,
        string memory errorMessage
    ) internal returns (bytes memory) {
        require(address(this).balance >= value, "Address: insufficient balance for call");
        (bool success, bytes memory returndata) = target.call{value: value}(data);
        return verifyCallResultFromTarget(target, success, returndata, errorMessage);
    }
    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
     * but performing a static call.
     *
     * _Available since v3.3._
     */
    function functionStaticCall(address target, bytes memory data) internal view returns (bytes memory) {
        return functionStaticCall(target, data, "Address: low-level static call failed");
    }
    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-string-}[`functionCall`],
     * but performing a static call.
     *
     * _Available since v3.3._
     */
    function functionStaticCall(
        address target,
        bytes memory data,
        string memory errorMessage
    ) internal view returns (bytes memory) {
        (bool success, bytes memory returndata) = target.staticcall(data);
        return verifyCallResultFromTarget(target, success, returndata, errorMessage);
    }
    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
     * but performing a delegate call.
     *
     * _Available since v3.4._
     */
    function functionDelegateCall(address target, bytes memory data) internal returns (bytes memory) {
        return functionDelegateCall(target, data, "Address: low-level delegate call failed");
    }
    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-string-}[`functionCall`],
     * but performing a delegate call.
     *
     * _Available since v3.4._
     */
    function functionDelegateCall(
        address target,
        bytes memory data,
        string memory errorMessage
    ) internal returns (bytes memory) {
        (bool success, bytes memory returndata) = target.delegatecall(data);
        return verifyCallResultFromTarget(target, success, returndata, errorMessage);
    }
    /**
     * @dev Tool to verify that a low level call to smart-contract was successful, and revert (either by bubbling
     * the revert reason or using the provided one) in case of unsuccessful call or if target was not a contract.
     *
     * _Available since v4.8._
     */
    function verifyCallResultFromTarget(
        address target,
        bool success,
        bytes memory returndata,
        string memory errorMessage
    ) internal view returns (bytes memory) {
        if (success) {
            if (returndata.length == 0) {
                // only check isContract if the call was successful and the return data is empty
                // otherwise we already know that it was a contract
                require(isContract(target), "Address: call to non-contract");
            }
            return returndata;
        } else {
            _revert(returndata, errorMessage);
        }
    }
    /**
     * @dev Tool to verify that a low level call was successful, and revert if it wasn't, either by bubbling the
     * revert reason or using the provided one.
     *
     * _Available since v4.3._
     */
    function verifyCallResult(
        bool success,
        bytes memory returndata,
        string memory errorMessage
    ) internal pure returns (bytes memory) {
        if (success) {
            return returndata;
        } else {
            _revert(returndata, errorMessage);
        }
    }
    function _revert(bytes memory returndata, string memory errorMessage) private pure {
        // Look for revert reason and bubble it up if present
        if (returndata.length > 0) {
            // The easiest way to bubble the revert reason is using memory via assembly
            /// @solidity memory-safe-assembly
            assembly {
                let returndata_size := mload(returndata)
                revert(add(32, returndata), returndata_size)
            }
        } else {
            revert(errorMessage);
        }
    }
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (utils/Context.sol)
pragma solidity ^0.8.0;
/**
 * @dev Provides information about the current execution context, including the
 * sender of the transaction and its data. While these are generally available
 * via msg.sender and msg.data, they should not be accessed in such a direct
 * manner, since when dealing with meta-transactions the account sending and
 * paying for execution may not be the actual sender (as far as an application
 * is concerned).
 *
 * This contract is only required for intermediate, library-like contracts.
 */
abstract contract Context {
    function _msgSender() internal view virtual returns (address) {
        return msg.sender;
    }
    function _msgData() internal view virtual returns (bytes calldata) {
        return msg.data;
    }
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.7.0) (utils/StorageSlot.sol)
pragma solidity ^0.8.0;
/**
 * @dev Library for reading and writing primitive types to specific storage slots.
 *
 * Storage slots are often used to avoid storage conflict when dealing with upgradeable contracts.
 * This library helps with reading and writing to such slots without the need for inline assembly.
 *
 * The functions in this library return Slot structs that contain a `value` member that can be used to read or write.
 *
 * Example usage to set ERC1967 implementation slot:
 * ```
 * contract ERC1967 {
 *     bytes32 internal constant _IMPLEMENTATION_SLOT = 0x360894a13ba1a3210667c828492db98dca3e2076cc3735a920a3ca505d382bbc;
 *
 *     function _getImplementation() internal view returns (address) {
 *         return StorageSlot.getAddressSlot(_IMPLEMENTATION_SLOT).value;
 *     }
 *
 *     function _setImplementation(address newImplementation) internal {
 *         require(Address.isContract(newImplementation), "ERC1967: new implementation is not a contract");
 *         StorageSlot.getAddressSlot(_IMPLEMENTATION_SLOT).value = newImplementation;
 *     }
 * }
 * ```
 *
 * _Available since v4.1 for `address`, `bool`, `bytes32`, and `uint256`._
 */
library StorageSlot {
    struct AddressSlot {
        address value;
    }
    struct BooleanSlot {
        bool value;
    }
    struct Bytes32Slot {
        bytes32 value;
    }
    struct Uint256Slot {
        uint256 value;
    }
    /**
     * @dev Returns an `AddressSlot` with member `value` located at `slot`.
     */
    function getAddressSlot(bytes32 slot) internal pure returns (AddressSlot storage r) {
        /// @solidity memory-safe-assembly
        assembly {
            r.slot := slot
        }
    }
    /**
     * @dev Returns an `BooleanSlot` with member `value` located at `slot`.
     */
    function getBooleanSlot(bytes32 slot) internal pure returns (BooleanSlot storage r) {
        /// @solidity memory-safe-assembly
        assembly {
            r.slot := slot
        }
    }
    /**
     * @dev Returns an `Bytes32Slot` with member `value` located at `slot`.
     */
    function getBytes32Slot(bytes32 slot) internal pure returns (Bytes32Slot storage r) {
        /// @solidity memory-safe-assembly
        assembly {
            r.slot := slot
        }
    }
    /**
     * @dev Returns an `Uint256Slot` with member `value` located at `slot`.
     */
    function getUint256Slot(bytes32 slot) internal pure returns (Uint256Slot storage r) {
        /// @solidity memory-safe-assembly
        assembly {
            r.slot := slot
        }
    }
}

// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.9.0) (access/AccessControl.sol)
pragma solidity ^0.8.0;
import "./IAccessControlUpgradeable.sol";
import "../utils/ContextUpgradeable.sol";
import "../utils/StringsUpgradeable.sol";
import "../utils/introspection/ERC165Upgradeable.sol";
import "../proxy/utils/Initializable.sol";
/**
 * @dev Contract module that allows children to implement role-based access
 * control mechanisms. This is a lightweight version that doesn't allow enumerating role
 * members except through off-chain means by accessing the contract event logs. Some
 * applications may benefit from on-chain enumerability, for those cases see
 * {AccessControlEnumerable}.
 *
 * Roles are referred to by their `bytes32` identifier. These should be exposed
 * in the external API and be unique. The best way to achieve this is by
 * using `public constant` hash digests:
 *
 * ```solidity
 * bytes32 public constant MY_ROLE = keccak256("MY_ROLE");
 * ```
 *
 * Roles can be used to represent a set of permissions. To restrict access to a
 * function call, use {hasRole}:
 *
 * ```solidity
 * function foo() public {
 *     require(hasRole(MY_ROLE, msg.sender));
 *     ...
 * }
 * ```
 *
 * Roles can be granted and revoked dynamically via the {grantRole} and
 * {revokeRole} functions. Each role has an associated admin role, and only
 * accounts that have a role's admin role can call {grantRole} and {revokeRole}.
 *
 * By default, the admin role for all roles is `DEFAULT_ADMIN_ROLE`, which means
 * that only accounts with this role will be able to grant or revoke other
 * roles. More complex role relationships can be created by using
 * {_setRoleAdmin}.
 *
 * WARNING: The `DEFAULT_ADMIN_ROLE` is also its own admin: it has permission to
 * grant and revoke this role. Extra precautions should be taken to secure
 * accounts that have been granted it. We recommend using {AccessControlDefaultAdminRules}
 * to enforce additional security measures for this role.
 */
abstract contract AccessControlUpgradeable is Initializable, ContextUpgradeable, IAccessControlUpgradeable, ERC165Upgradeable {
    function __AccessControl_init() internal onlyInitializing {
    }
    function __AccessControl_init_unchained() internal onlyInitializing {
    }
    struct RoleData {
        mapping(address => bool) members;
        bytes32 adminRole;
    }
    mapping(bytes32 => RoleData) private _roles;
    bytes32 public constant DEFAULT_ADMIN_ROLE = 0x00;
    /**
     * @dev Modifier that checks that an account has a specific role. Reverts
     * with a standardized message including the required role.
     *
     * The format of the revert reason is given by the following regular expression:
     *
     *  /^AccessControl: account (0x[0-9a-f]{40}) is missing role (0x[0-9a-f]{64})$/
     *
     * _Available since v4.1._
     */
    modifier onlyRole(bytes32 role) {
        _checkRole(role);
        _;
    }
    /**
     * @dev See {IERC165-supportsInterface}.
     */
    function supportsInterface(bytes4 interfaceId) public view virtual override returns (bool) {
        return interfaceId == type(IAccessControlUpgradeable).interfaceId || super.supportsInterface(interfaceId);
    }
    /**
     * @dev Returns `true` if `account` has been granted `role`.
     */
    function hasRole(bytes32 role, address account) public view virtual override returns (bool) {
        return _roles[role].members[account];
    }
    /**
     * @dev Revert with a standard message if `_msgSender()` is missing `role`.
     * Overriding this function changes the behavior of the {onlyRole} modifier.
     *
     * Format of the revert message is described in {_checkRole}.
     *
     * _Available since v4.6._
     */
    function _checkRole(bytes32 role) internal view virtual {
        _checkRole(role, _msgSender());
    }
    /**
     * @dev Revert with a standard message if `account` is missing `role`.
     *
     * The format of the revert reason is given by the following regular expression:
     *
     *  /^AccessControl: account (0x[0-9a-f]{40}) is missing role (0x[0-9a-f]{64})$/
     */
    function _checkRole(bytes32 role, address account) internal view virtual {
        if (!hasRole(role, account)) {
            revert(
                string(
                    abi.encodePacked(
                        "AccessControl: account ",
                        StringsUpgradeable.toHexString(account),
                        " is missing role ",
                        StringsUpgradeable.toHexString(uint256(role), 32)
                    )
                )
            );
        }
    }
    /**
     * @dev Returns the admin role that controls `role`. See {grantRole} and
     * {revokeRole}.
     *
     * To change a role's admin, use {_setRoleAdmin}.
     */
    function getRoleAdmin(bytes32 role) public view virtual override returns (bytes32) {
        return _roles[role].adminRole;
    }
    /**
     * @dev Grants `role` to `account`.
     *
     * If `account` had not been already granted `role`, emits a {RoleGranted}
     * event.
     *
     * Requirements:
     *
     * - the caller must have ``role``'s admin role.
     *
     * May emit a {RoleGranted} event.
     */
    function grantRole(bytes32 role, address account) public virtual override onlyRole(getRoleAdmin(role)) {
        _grantRole(role, account);
    }
    /**
     * @dev Revokes `role` from `account`.
     *
     * If `account` had been granted `role`, emits a {RoleRevoked} event.
     *
     * Requirements:
     *
     * - the caller must have ``role``'s admin role.
     *
     * May emit a {RoleRevoked} event.
     */
    function revokeRole(bytes32 role, address account) public virtual override onlyRole(getRoleAdmin(role)) {
        _revokeRole(role, account);
    }
    /**
     * @dev Revokes `role` from the calling account.
     *
     * Roles are often managed via {grantRole} and {revokeRole}: this function's
     * purpose is to provide a mechanism for accounts to lose their privileges
     * if they are compromised (such as when a trusted device is misplaced).
     *
     * If the calling account had been revoked `role`, emits a {RoleRevoked}
     * event.
     *
     * Requirements:
     *
     * - the caller must be `account`.
     *
     * May emit a {RoleRevoked} event.
     */
    function renounceRole(bytes32 role, address account) public virtual override {
        require(account == _msgSender(), "AccessControl: can only renounce roles for self");
        _revokeRole(role, account);
    }
    /**
     * @dev Grants `role` to `account`.
     *
     * If `account` had not been already granted `role`, emits a {RoleGranted}
     * event. Note that unlike {grantRole}, this function doesn't perform any
     * checks on the calling account.
     *
     * May emit a {RoleGranted} event.
     *
     * [WARNING]
     * ====
     * This function should only be called from the constructor when setting
     * up the initial roles for the system.
     *
     * Using this function in any other way is effectively circumventing the admin
     * system imposed by {AccessControl}.
     * ====
     *
     * NOTE: This function is deprecated in favor of {_grantRole}.
     */
    function _setupRole(bytes32 role, address account) internal virtual {
        _grantRole(role, account);
    }
    /**
     * @dev Sets `adminRole` as ``role``'s admin role.
     *
     * Emits a {RoleAdminChanged} event.
     */
    function _setRoleAdmin(bytes32 role, bytes32 adminRole) internal virtual {
        bytes32 previousAdminRole = getRoleAdmin(role);
        _roles[role].adminRole = adminRole;
        emit RoleAdminChanged(role, previousAdminRole, adminRole);
    }
    /**
     * @dev Grants `role` to `account`.
     *
     * Internal function without access restriction.
     *
     * May emit a {RoleGranted} event.
     */
    function _grantRole(bytes32 role, address account) internal virtual {
        if (!hasRole(role, account)) {
            _roles[role].members[account] = true;
            emit RoleGranted(role, account, _msgSender());
        }
    }
    /**
     * @dev Revokes `role` from `account`.
     *
     * Internal function without access restriction.
     *
     * May emit a {RoleRevoked} event.
     */
    function _revokeRole(bytes32 role, address account) internal virtual {
        if (hasRole(role, account)) {
            _roles[role].members[account] = false;
            emit RoleRevoked(role, account, _msgSender());
        }
    }
    /**
     * @dev This empty reserved space is put in place to allow future versions to add new
     * variables without shifting down storage in the inheritance chain.
     * See https://docs.openzeppelin.com/contracts/4.x/upgradeable#storage_gaps
     */
    uint256[49] private __gap;
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (access/IAccessControl.sol)
pragma solidity ^0.8.0;
/**
 * @dev External interface of AccessControl declared to support ERC165 detection.
 */
interface IAccessControlUpgradeable {
    /**
     * @dev Emitted when `newAdminRole` is set as ``role``'s admin role, replacing `previousAdminRole`
     *
     * `DEFAULT_ADMIN_ROLE` is the starting admin for all roles, despite
     * {RoleAdminChanged} not being emitted signaling this.
     *
     * _Available since v3.1._
     */
    event RoleAdminChanged(bytes32 indexed role, bytes32 indexed previousAdminRole, bytes32 indexed newAdminRole);
    /**
     * @dev Emitted when `account` is granted `role`.
     *
     * `sender` is the account that originated the contract call, an admin role
     * bearer except when using {AccessControl-_setupRole}.
     */
    event RoleGranted(bytes32 indexed role, address indexed account, address indexed sender);
    /**
     * @dev Emitted when `account` is revoked `role`.
     *
     * `sender` is the account that originated the contract call:
     *   - if using `revokeRole`, it is the admin role bearer
     *   - if using `renounceRole`, it is the role bearer (i.e. `account`)
     */
    event RoleRevoked(bytes32 indexed role, address indexed account, address indexed sender);
    /**
     * @dev Returns `true` if `account` has been granted `role`.
     */
    function hasRole(bytes32 role, address account) external view returns (bool);
    /**
     * @dev Returns the admin role that controls `role`. See {grantRole} and
     * {revokeRole}.
     *
     * To change a role's admin, use {AccessControl-_setRoleAdmin}.
     */
    function getRoleAdmin(bytes32 role) external view returns (bytes32);
    /**
     * @dev Grants `role` to `account`.
     *
     * If `account` had not been already granted `role`, emits a {RoleGranted}
     * event.
     *
     * Requirements:
     *
     * - the caller must have ``role``'s admin role.
     */
    function grantRole(bytes32 role, address account) external;
    /**
     * @dev Revokes `role` from `account`.
     *
     * If `account` had been granted `role`, emits a {RoleRevoked} event.
     *
     * Requirements:
     *
     * - the caller must have ``role``'s admin role.
     */
    function revokeRole(bytes32 role, address account) external;
    /**
     * @dev Revokes `role` from the calling account.
     *
     * Roles are often managed via {grantRole} and {revokeRole}: this function's
     * purpose is to provide a mechanism for accounts to lose their privileges
     * if they are compromised (such as when a trusted device is misplaced).
     *
     * If the calling account had been granted `role`, emits a {RoleRevoked}
     * event.
     *
     * Requirements:
     *
     * - the caller must be `account`.
     */
    function renounceRole(bytes32 role, address account) external;
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.9.0) (proxy/utils/Initializable.sol)
pragma solidity ^0.8.2;
import "../../utils/AddressUpgradeable.sol";
/**
 * @dev This is a base contract to aid in writing upgradeable contracts, or any kind of contract that will be deployed
 * behind a proxy. Since proxied contracts do not make use of a constructor, it's common to move constructor logic to an
 * external initializer function, usually called `initialize`. It then becomes necessary to protect this initializer
 * function so it can only be called once. The {initializer} modifier provided by this contract will have this effect.
 *
 * The initialization functions use a version number. Once a version number is used, it is consumed and cannot be
 * reused. This mechanism prevents re-execution of each "step" but allows the creation of new initialization steps in
 * case an upgrade adds a module that needs to be initialized.
 *
 * For example:
 *
 * [.hljs-theme-light.nopadding]
 * ```solidity
 * contract MyToken is ERC20Upgradeable {
 *     function initialize() initializer public {
 *         __ERC20_init("MyToken", "MTK");
 *     }
 * }
 *
 * contract MyTokenV2 is MyToken, ERC20PermitUpgradeable {
 *     function initializeV2() reinitializer(2) public {
 *         __ERC20Permit_init("MyToken");
 *     }
 * }
 * ```
 *
 * TIP: To avoid leaving the proxy in an uninitialized state, the initializer function should be called as early as
 * possible by providing the encoded function call as the `_data` argument to {ERC1967Proxy-constructor}.
 *
 * CAUTION: When used with inheritance, manual care must be taken to not invoke a parent initializer twice, or to ensure
 * that all initializers are idempotent. This is not verified automatically as constructors are by Solidity.
 *
 * [CAUTION]
 * ====
 * Avoid leaving a contract uninitialized.
 *
 * An uninitialized contract can be taken over by an attacker. This applies to both a proxy and its implementation
 * contract, which may impact the proxy. To prevent the implementation contract from being used, you should invoke
 * the {_disableInitializers} function in the constructor to automatically lock it when it is deployed:
 *
 * [.hljs-theme-light.nopadding]
 * ```
 * /// @custom:oz-upgrades-unsafe-allow constructor
 * constructor() {
 *     _disableInitializers();
 * }
 * ```
 * ====
 */
abstract contract Initializable {
    /**
     * @dev Indicates that the contract has been initialized.
     * @custom:oz-retyped-from bool
     */
    uint8 private _initialized;
    /**
     * @dev Indicates that the contract is in the process of being initialized.
     */
    bool private _initializing;
    /**
     * @dev Triggered when the contract has been initialized or reinitialized.
     */
    event Initialized(uint8 version);
    /**
     * @dev A modifier that defines a protected initializer function that can be invoked at most once. In its scope,
     * `onlyInitializing` functions can be used to initialize parent contracts.
     *
     * Similar to `reinitializer(1)`, except that functions marked with `initializer` can be nested in the context of a
     * constructor.
     *
     * Emits an {Initialized} event.
     */
    modifier initializer() {
        bool isTopLevelCall = !_initializing;
        require(
            (isTopLevelCall && _initialized < 1) || (!AddressUpgradeable.isContract(address(this)) && _initialized == 1),
            "Initializable: contract is already initialized"
        );
        _initialized = 1;
        if (isTopLevelCall) {
            _initializing = true;
        }
        _;
        if (isTopLevelCall) {
            _initializing = false;
            emit Initialized(1);
        }
    }
    /**
     * @dev A modifier that defines a protected reinitializer function that can be invoked at most once, and only if the
     * contract hasn't been initialized to a greater version before. In its scope, `onlyInitializing` functions can be
     * used to initialize parent contracts.
     *
     * A reinitializer may be used after the original initialization step. This is essential to configure modules that
     * are added through upgrades and that require initialization.
     *
     * When `version` is 1, this modifier is similar to `initializer`, except that functions marked with `reinitializer`
     * cannot be nested. If one is invoked in the context of another, execution will revert.
     *
     * Note that versions can jump in increments greater than 1; this implies that if multiple reinitializers coexist in
     * a contract, executing them in the right order is up to the developer or operator.
     *
     * WARNING: setting the version to 255 will prevent any future reinitialization.
     *
     * Emits an {Initialized} event.
     */
    modifier reinitializer(uint8 version) {
        require(!_initializing && _initialized < version, "Initializable: contract is already initialized");
        _initialized = version;
        _initializing = true;
        _;
        _initializing = false;
        emit Initialized(version);
    }
    /**
     * @dev Modifier to protect an initialization function so that it can only be invoked by functions with the
     * {initializer} and {reinitializer} modifiers, directly or indirectly.
     */
    modifier onlyInitializing() {
        require(_initializing, "Initializable: contract is not initializing");
        _;
    }
    /**
     * @dev Locks the contract, preventing any future reinitialization. This cannot be part of an initializer call.
     * Calling this in the constructor of a contract will prevent that contract from being initialized or reinitialized
     * to any version. It is recommended to use this to lock implementation contracts that are designed to be called
     * through proxies.
     *
     * Emits an {Initialized} event the first time it is successfully executed.
     */
    function _disableInitializers() internal virtual {
        require(!_initializing, "Initializable: contract is initializing");
        if (_initialized != type(uint8).max) {
            _initialized = type(uint8).max;
            emit Initialized(type(uint8).max);
        }
    }
    /**
     * @dev Returns the highest version that has been initialized. See {reinitializer}.
     */
    function _getInitializedVersion() internal view returns (uint8) {
        return _initialized;
    }
    /**
     * @dev Returns `true` if the contract is currently initializing. See {onlyInitializing}.
     */
    function _isInitializing() internal view returns (bool) {
        return _initializing;
    }
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.9.0) (security/ReentrancyGuard.sol)
pragma solidity ^0.8.0;
import "../proxy/utils/Initializable.sol";
/**
 * @dev Contract module that helps prevent reentrant calls to a function.
 *
 * Inheriting from `ReentrancyGuard` will make the {nonReentrant} modifier
 * available, which can be applied to functions to make sure there are no nested
 * (reentrant) calls to them.
 *
 * Note that because there is a single `nonReentrant` guard, functions marked as
 * `nonReentrant` may not call one another. This can be worked around by making
 * those functions `private`, and then adding `external` `nonReentrant` entry
 * points to them.
 *
 * TIP: If you would like to learn more about reentrancy and alternative ways
 * to protect against it, check out our blog post
 * https://blog.openzeppelin.com/reentrancy-after-istanbul/[Reentrancy After Istanbul].
 */
abstract contract ReentrancyGuardUpgradeable is Initializable {
    // Booleans are more expensive than uint256 or any type that takes up a full
    // word because each write operation emits an extra SLOAD to first read the
    // slot's contents, replace the bits taken up by the boolean, and then write
    // back. This is the compiler's defense against contract upgrades and
    // pointer aliasing, and it cannot be disabled.
    // The values being non-zero value makes deployment a bit more expensive,
    // but in exchange the refund on every call to nonReentrant will be lower in
    // amount. Since refunds are capped to a percentage of the total
    // transaction's gas, it is best to keep them low in cases like this one, to
    // increase the likelihood of the full refund coming into effect.
    uint256 private constant _NOT_ENTERED = 1;
    uint256 private constant _ENTERED = 2;
    uint256 private _status;
    function __ReentrancyGuard_init() internal onlyInitializing {
        __ReentrancyGuard_init_unchained();
    }
    function __ReentrancyGuard_init_unchained() internal onlyInitializing {
        _status = _NOT_ENTERED;
    }
    /**
     * @dev Prevents a contract from calling itself, directly or indirectly.
     * Calling a `nonReentrant` function from another `nonReentrant`
     * function is not supported. It is possible to prevent this from happening
     * by making the `nonReentrant` function external, and making it call a
     * `private` function that does the actual work.
     */
    modifier nonReentrant() {
        _nonReentrantBefore();
        _;
        _nonReentrantAfter();
    }
    function _nonReentrantBefore() private {
        // On the first call to nonReentrant, _status will be _NOT_ENTERED
        require(_status != _ENTERED, "ReentrancyGuard: reentrant call");
        // Any calls to nonReentrant after this point will fail
        _status = _ENTERED;
    }
    function _nonReentrantAfter() private {
        // By storing the original value once again, a refund is triggered (see
        // https://eips.ethereum.org/EIPS/eip-2200)
        _status = _NOT_ENTERED;
    }
    /**
     * @dev Returns true if the reentrancy guard is currently set to "entered", which indicates there is a
     * `nonReentrant` function in the call stack.
     */
    function _reentrancyGuardEntered() internal view returns (bool) {
        return _status == _ENTERED;
    }
    /**
     * @dev This empty reserved space is put in place to allow future versions to add new
     * variables without shifting down storage in the inheritance chain.
     * See https://docs.openzeppelin.com/contracts/4.x/upgradeable#storage_gaps
     */
    uint256[49] private __gap;
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.9.0) (utils/Address.sol)
pragma solidity ^0.8.1;
/**
 * @dev Collection of functions related to the address type
 */
library AddressUpgradeable {
    /**
     * @dev Returns true if `account` is a contract.
     *
     * [IMPORTANT]
     * ====
     * It is unsafe to assume that an address for which this function returns
     * false is an externally-owned account (EOA) and not a contract.
     *
     * Among others, `isContract` will return false for the following
     * types of addresses:
     *
     *  - an externally-owned account
     *  - a contract in construction
     *  - an address where a contract will be created
     *  - an address where a contract lived, but was destroyed
     *
     * Furthermore, `isContract` will also return true if the target contract within
     * the same transaction is already scheduled for destruction by `SELFDESTRUCT`,
     * which only has an effect at the end of a transaction.
     * ====
     *
     * [IMPORTANT]
     * ====
     * You shouldn't rely on `isContract` to protect against flash loan attacks!
     *
     * Preventing calls from contracts is highly discouraged. It breaks composability, breaks support for smart wallets
     * like Gnosis Safe, and does not provide security since it can be circumvented by calling from a contract
     * constructor.
     * ====
     */
    function isContract(address account) internal view returns (bool) {
        // This method relies on extcodesize/address.code.length, which returns 0
        // for contracts in construction, since the code is only stored at the end
        // of the constructor execution.
        return account.code.length > 0;
    }
    /**
     * @dev Replacement for Solidity's `transfer`: sends `amount` wei to
     * `recipient`, forwarding all available gas and reverting on errors.
     *
     * https://eips.ethereum.org/EIPS/eip-1884[EIP1884] increases the gas cost
     * of certain opcodes, possibly making contracts go over the 2300 gas limit
     * imposed by `transfer`, making them unable to receive funds via
     * `transfer`. {sendValue} removes this limitation.
     *
     * https://consensys.net/diligence/blog/2019/09/stop-using-soliditys-transfer-now/[Learn more].
     *
     * IMPORTANT: because control is transferred to `recipient`, care must be
     * taken to not create reentrancy vulnerabilities. Consider using
     * {ReentrancyGuard} or the
     * https://solidity.readthedocs.io/en/v0.8.0/security-considerations.html#use-the-checks-effects-interactions-pattern[checks-effects-interactions pattern].
     */
    function sendValue(address payable recipient, uint256 amount) internal {
        require(address(this).balance >= amount, "Address: insufficient balance");
        (bool success, ) = recipient.call{value: amount}("");
        require(success, "Address: unable to send value, recipient may have reverted");
    }
    /**
     * @dev Performs a Solidity function call using a low level `call`. A
     * plain `call` is an unsafe replacement for a function call: use this
     * function instead.
     *
     * If `target` reverts with a revert reason, it is bubbled up by this
     * function (like regular Solidity function calls).
     *
     * Returns the raw returned data. To convert to the expected return value,
     * use https://solidity.readthedocs.io/en/latest/units-and-global-variables.html?highlight=abi.decode#abi-encoding-and-decoding-functions[`abi.decode`].
     *
     * Requirements:
     *
     * - `target` must be a contract.
     * - calling `target` with `data` must not revert.
     *
     * _Available since v3.1._
     */
    function functionCall(address target, bytes memory data) internal returns (bytes memory) {
        return functionCallWithValue(target, data, 0, "Address: low-level call failed");
    }
    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`], but with
     * `errorMessage` as a fallback revert reason when `target` reverts.
     *
     * _Available since v3.1._
     */
    function functionCall(
        address target,
        bytes memory data,
        string memory errorMessage
    ) internal returns (bytes memory) {
        return functionCallWithValue(target, data, 0, errorMessage);
    }
    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
     * but also transferring `value` wei to `target`.
     *
     * Requirements:
     *
     * - the calling contract must have an ETH balance of at least `value`.
     * - the called Solidity function must be `payable`.
     *
     * _Available since v3.1._
     */
    function functionCallWithValue(address target, bytes memory data, uint256 value) internal returns (bytes memory) {
        return functionCallWithValue(target, data, value, "Address: low-level call with value failed");
    }
    /**
     * @dev Same as {xref-Address-functionCallWithValue-address-bytes-uint256-}[`functionCallWithValue`], but
     * with `errorMessage` as a fallback revert reason when `target` reverts.
     *
     * _Available since v3.1._
     */
    function functionCallWithValue(
        address target,
        bytes memory data,
        uint256 value,
        string memory errorMessage
    ) internal returns (bytes memory) {
        require(address(this).balance >= value, "Address: insufficient balance for call");
        (bool success, bytes memory returndata) = target.call{value: value}(data);
        return verifyCallResultFromTarget(target, success, returndata, errorMessage);
    }
    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
     * but performing a static call.
     *
     * _Available since v3.3._
     */
    function functionStaticCall(address target, bytes memory data) internal view returns (bytes memory) {
        return functionStaticCall(target, data, "Address: low-level static call failed");
    }
    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-string-}[`functionCall`],
     * but performing a static call.
     *
     * _Available since v3.3._
     */
    function functionStaticCall(
        address target,
        bytes memory data,
        string memory errorMessage
    ) internal view returns (bytes memory) {
        (bool success, bytes memory returndata) = target.staticcall(data);
        return verifyCallResultFromTarget(target, success, returndata, errorMessage);
    }
    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
     * but performing a delegate call.
     *
     * _Available since v3.4._
     */
    function functionDelegateCall(address target, bytes memory data) internal returns (bytes memory) {
        return functionDelegateCall(target, data, "Address: low-level delegate call failed");
    }
    /**
     * @dev Same as {xref-Address-functionCall-address-bytes-string-}[`functionCall`],
     * but performing a delegate call.
     *
     * _Available since v3.4._
     */
    function functionDelegateCall(
        address target,
        bytes memory data,
        string memory errorMessage
    ) internal returns (bytes memory) {
        (bool success, bytes memory returndata) = target.delegatecall(data);
        return verifyCallResultFromTarget(target, success, returndata, errorMessage);
    }
    /**
     * @dev Tool to verify that a low level call to smart-contract was successful, and revert (either by bubbling
     * the revert reason or using the provided one) in case of unsuccessful call or if target was not a contract.
     *
     * _Available since v4.8._
     */
    function verifyCallResultFromTarget(
        address target,
        bool success,
        bytes memory returndata,
        string memory errorMessage
    ) internal view returns (bytes memory) {
        if (success) {
            if (returndata.length == 0) {
                // only check isContract if the call was successful and the return data is empty
                // otherwise we already know that it was a contract
                require(isContract(target), "Address: call to non-contract");
            }
            return returndata;
        } else {
            _revert(returndata, errorMessage);
        }
    }
    /**
     * @dev Tool to verify that a low level call was successful, and revert if it wasn't, either by bubbling the
     * revert reason or using the provided one.
     *
     * _Available since v4.3._
     */
    function verifyCallResult(
        bool success,
        bytes memory returndata,
        string memory errorMessage
    ) internal pure returns (bytes memory) {
        if (success) {
            return returndata;
        } else {
            _revert(returndata, errorMessage);
        }
    }
    function _revert(bytes memory returndata, string memory errorMessage) private pure {
        // Look for revert reason and bubble it up if present
        if (returndata.length > 0) {
            // The easiest way to bubble the revert reason is using memory via assembly
            /// @solidity memory-safe-assembly
            assembly {
                let returndata_size := mload(returndata)
                revert(add(32, returndata), returndata_size)
            }
        } else {
            revert(errorMessage);
        }
    }
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (utils/Context.sol)
pragma solidity ^0.8.0;
import "../proxy/utils/Initializable.sol";
/**
 * @dev Provides information about the current execution context, including the
 * sender of the transaction and its data. While these are generally available
 * via msg.sender and msg.data, they should not be accessed in such a direct
 * manner, since when dealing with meta-transactions the account sending and
 * paying for execution may not be the actual sender (as far as an application
 * is concerned).
 *
 * This contract is only required for intermediate, library-like contracts.
 */
abstract contract ContextUpgradeable is Initializable {
    function __Context_init() internal onlyInitializing {
    }
    function __Context_init_unchained() internal onlyInitializing {
    }
    function _msgSender() internal view virtual returns (address) {
        return msg.sender;
    }
    function _msgData() internal view virtual returns (bytes calldata) {
        return msg.data;
    }
    /**
     * @dev This empty reserved space is put in place to allow future versions to add new
     * variables without shifting down storage in the inheritance chain.
     * See https://docs.openzeppelin.com/contracts/4.x/upgradeable#storage_gaps
     */
    uint256[50] private __gap;
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (utils/introspection/ERC165.sol)
pragma solidity ^0.8.0;
import "./IERC165Upgradeable.sol";
import "../../proxy/utils/Initializable.sol";
/**
 * @dev Implementation of the {IERC165} interface.
 *
 * Contracts that want to implement ERC165 should inherit from this contract and override {supportsInterface} to check
 * for the additional interface id that will be supported. For example:
 *
 * ```solidity
 * function supportsInterface(bytes4 interfaceId) public view virtual override returns (bool) {
 *     return interfaceId == type(MyInterface).interfaceId || super.supportsInterface(interfaceId);
 * }
 * ```
 *
 * Alternatively, {ERC165Storage} provides an easier to use but more expensive implementation.
 */
abstract contract ERC165Upgradeable is Initializable, IERC165Upgradeable {
    function __ERC165_init() internal onlyInitializing {
    }
    function __ERC165_init_unchained() internal onlyInitializing {
    }
    /**
     * @dev See {IERC165-supportsInterface}.
     */
    function supportsInterface(bytes4 interfaceId) public view virtual override returns (bool) {
        return interfaceId == type(IERC165Upgradeable).interfaceId;
    }
    /**
     * @dev This empty reserved space is put in place to allow future versions to add new
     * variables without shifting down storage in the inheritance chain.
     * See https://docs.openzeppelin.com/contracts/4.x/upgradeable#storage_gaps
     */
    uint256[50] private __gap;
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts v4.4.1 (utils/introspection/IERC165.sol)
pragma solidity ^0.8.0;
/**
 * @dev Interface of the ERC165 standard, as defined in the
 * https://eips.ethereum.org/EIPS/eip-165[EIP].
 *
 * Implementers can declare support of contract interfaces, which can then be
 * queried by others ({ERC165Checker}).
 *
 * For an implementation, see {ERC165}.
 */
interface IERC165Upgradeable {
    /**
     * @dev Returns true if this contract implements the interface defined by
     * `interfaceId`. See the corresponding
     * https://eips.ethereum.org/EIPS/eip-165#how-interfaces-are-identified[EIP section]
     * to learn more about how these ids are created.
     *
     * This function call must use less than 30 000 gas.
     */
    function supportsInterface(bytes4 interfaceId) external view returns (bool);
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.9.0) (utils/math/Math.sol)
pragma solidity ^0.8.0;
/**
 * @dev Standard math utilities missing in the Solidity language.
 */
library MathUpgradeable {
    enum Rounding {
        Down, // Toward negative infinity
        Up, // Toward infinity
        Zero // Toward zero
    }
    /**
     * @dev Returns the largest of two numbers.
     */
    function max(uint256 a, uint256 b) internal pure returns (uint256) {
        return a > b ? a : b;
    }
    /**
     * @dev Returns the smallest of two numbers.
     */
    function min(uint256 a, uint256 b) internal pure returns (uint256) {
        return a < b ? a : b;
    }
    /**
     * @dev Returns the average of two numbers. The result is rounded towards
     * zero.
     */
    function average(uint256 a, uint256 b) internal pure returns (uint256) {
        // (a + b) / 2 can overflow.
        return (a & b) + (a ^ b) / 2;
    }
    /**
     * @dev Returns the ceiling of the division of two numbers.
     *
     * This differs from standard division with `/` in that it rounds up instead
     * of rounding down.
     */
    function ceilDiv(uint256 a, uint256 b) internal pure returns (uint256) {
        // (a + b - 1) / b can overflow on addition, so we distribute.
        return a == 0 ? 0 : (a - 1) / b + 1;
    }
    /**
     * @notice Calculates floor(x * y / denominator) with full precision. Throws if result overflows a uint256 or denominator == 0
     * @dev Original credit to Remco Bloemen under MIT license (https://xn--2-umb.com/21/muldiv)
     * with further edits by Uniswap Labs also under MIT license.
     */
    function mulDiv(uint256 x, uint256 y, uint256 denominator) internal pure returns (uint256 result) {
        unchecked {
            // 512-bit multiply [prod1 prod0] = x * y. Compute the product mod 2^256 and mod 2^256 - 1, then use
            // use the Chinese Remainder Theorem to reconstruct the 512 bit result. The result is stored in two 256
            // variables such that product = prod1 * 2^256 + prod0.
            uint256 prod0; // Least significant 256 bits of the product
            uint256 prod1; // Most significant 256 bits of the product
            assembly {
                let mm := mulmod(x, y, not(0))
                prod0 := mul(x, y)
                prod1 := sub(sub(mm, prod0), lt(mm, prod0))
            }
            // Handle non-overflow cases, 256 by 256 division.
            if (prod1 == 0) {
                // Solidity will revert if denominator == 0, unlike the div opcode on its own.
                // The surrounding unchecked block does not change this fact.
                // See https://docs.soliditylang.org/en/latest/control-structures.html#checked-or-unchecked-arithmetic.
                return prod0 / denominator;
            }
            // Make sure the result is less than 2^256. Also prevents denominator == 0.
            require(denominator > prod1, "Math: mulDiv overflow");
            ///////////////////////////////////////////////
            // 512 by 256 division.
            ///////////////////////////////////////////////
            // Make division exact by subtracting the remainder from [prod1 prod0].
            uint256 remainder;
            assembly {
                // Compute remainder using mulmod.
                remainder := mulmod(x, y, denominator)
                // Subtract 256 bit number from 512 bit number.
                prod1 := sub(prod1, gt(remainder, prod0))
                prod0 := sub(prod0, remainder)
            }
            // Factor powers of two out of denominator and compute largest power of two divisor of denominator. Always >= 1.
            // See https://cs.stackexchange.com/q/138556/92363.
            // Does not overflow because the denominator cannot be zero at this stage in the function.
            uint256 twos = denominator & (~denominator + 1);
            assembly {
                // Divide denominator by twos.
                denominator := div(denominator, twos)
                // Divide [prod1 prod0] by twos.
                prod0 := div(prod0, twos)
                // Flip twos such that it is 2^256 / twos. If twos is zero, then it becomes one.
                twos := add(div(sub(0, twos), twos), 1)
            }
            // Shift in bits from prod1 into prod0.
            prod0 |= prod1 * twos;
            // Invert denominator mod 2^256. Now that denominator is an odd number, it has an inverse modulo 2^256 such
            // that denominator * inv = 1 mod 2^256. Compute the inverse by starting with a seed that is correct for
            // four bits. That is, denominator * inv = 1 mod 2^4.
            uint256 inverse = (3 * denominator) ^ 2;
            // Use the Newton-Raphson iteration to improve the precision. Thanks to Hensel's lifting lemma, this also works
            // in modular arithmetic, doubling the correct bits in each step.
            inverse *= 2 - denominator * inverse; // inverse mod 2^8
            inverse *= 2 - denominator * inverse; // inverse mod 2^16
            inverse *= 2 - denominator * inverse; // inverse mod 2^32
            inverse *= 2 - denominator * inverse; // inverse mod 2^64
            inverse *= 2 - denominator * inverse; // inverse mod 2^128
            inverse *= 2 - denominator * inverse; // inverse mod 2^256
            // Because the division is now exact we can divide by multiplying with the modular inverse of denominator.
            // This will give us the correct result modulo 2^256. Since the preconditions guarantee that the outcome is
            // less than 2^256, this is the final result. We don't need to compute the high bits of the result and prod1
            // is no longer required.
            result = prod0 * inverse;
            return result;
        }
    }
    /**
     * @notice Calculates x * y / denominator with full precision, following the selected rounding direction.
     */
    function mulDiv(uint256 x, uint256 y, uint256 denominator, Rounding rounding) internal pure returns (uint256) {
        uint256 result = mulDiv(x, y, denominator);
        if (rounding == Rounding.Up && mulmod(x, y, denominator) > 0) {
            result += 1;
        }
        return result;
    }
    /**
     * @dev Returns the square root of a number. If the number is not a perfect square, the value is rounded down.
     *
     * Inspired by Henry S. Warren, Jr.'s "Hacker's Delight" (Chapter 11).
     */
    function sqrt(uint256 a) internal pure returns (uint256) {
        if (a == 0) {
            return 0;
        }
        // For our first guess, we get the biggest power of 2 which is smaller than the square root of the target.
        //
        // We know that the "msb" (most significant bit) of our target number `a` is a power of 2 such that we have
        // `msb(a) <= a < 2*msb(a)`. This value can be written `msb(a)=2**k` with `k=log2(a)`.
        //
        // This can be rewritten `2**log2(a) <= a < 2**(log2(a) + 1)`
        // → `sqrt(2**k) <= sqrt(a) < sqrt(2**(k+1))`
        // → `2**(k/2) <= sqrt(a) < 2**((k+1)/2) <= 2**(k/2 + 1)`
        //
        // Consequently, `2**(log2(a) / 2)` is a good first approximation of `sqrt(a)` with at least 1 correct bit.
        uint256 result = 1 << (log2(a) >> 1);
        // At this point `result` is an estimation with one bit of precision. We know the true value is a uint128,
        // since it is the square root of a uint256. Newton's method converges quadratically (precision doubles at
        // every iteration). We thus need at most 7 iteration to turn our partial result with one bit of precision
        // into the expected uint128 result.
        unchecked {
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            result = (result + a / result) >> 1;
            return min(result, a / result);
        }
    }
    /**
     * @notice Calculates sqrt(a), following the selected rounding direction.
     */
    function sqrt(uint256 a, Rounding rounding) internal pure returns (uint256) {
        unchecked {
            uint256 result = sqrt(a);
            return result + (rounding == Rounding.Up && result * result < a ? 1 : 0);
        }
    }
    /**
     * @dev Return the log in base 2, rounded down, of a positive value.
     * Returns 0 if given 0.
     */
    function log2(uint256 value) internal pure returns (uint256) {
        uint256 result = 0;
        unchecked {
            if (value >> 128 > 0) {
                value >>= 128;
                result += 128;
            }
            if (value >> 64 > 0) {
                value >>= 64;
                result += 64;
            }
            if (value >> 32 > 0) {
                value >>= 32;
                result += 32;
            }
            if (value >> 16 > 0) {
                value >>= 16;
                result += 16;
            }
            if (value >> 8 > 0) {
                value >>= 8;
                result += 8;
            }
            if (value >> 4 > 0) {
                value >>= 4;
                result += 4;
            }
            if (value >> 2 > 0) {
                value >>= 2;
                result += 2;
            }
            if (value >> 1 > 0) {
                result += 1;
            }
        }
        return result;
    }
    /**
     * @dev Return the log in base 2, following the selected rounding direction, of a positive value.
     * Returns 0 if given 0.
     */
    function log2(uint256 value, Rounding rounding) internal pure returns (uint256) {
        unchecked {
            uint256 result = log2(value);
            return result + (rounding == Rounding.Up && 1 << result < value ? 1 : 0);
        }
    }
    /**
     * @dev Return the log in base 10, rounded down, of a positive value.
     * Returns 0 if given 0.
     */
    function log10(uint256 value) internal pure returns (uint256) {
        uint256 result = 0;
        unchecked {
            if (value >= 10 ** 64) {
                value /= 10 ** 64;
                result += 64;
            }
            if (value >= 10 ** 32) {
                value /= 10 ** 32;
                result += 32;
            }
            if (value >= 10 ** 16) {
                value /= 10 ** 16;
                result += 16;
            }
            if (value >= 10 ** 8) {
                value /= 10 ** 8;
                result += 8;
            }
            if (value >= 10 ** 4) {
                value /= 10 ** 4;
                result += 4;
            }
            if (value >= 10 ** 2) {
                value /= 10 ** 2;
                result += 2;
            }
            if (value >= 10 ** 1) {
                result += 1;
            }
        }
        return result;
    }
    /**
     * @dev Return the log in base 10, following the selected rounding direction, of a positive value.
     * Returns 0 if given 0.
     */
    function log10(uint256 value, Rounding rounding) internal pure returns (uint256) {
        unchecked {
            uint256 result = log10(value);
            return result + (rounding == Rounding.Up && 10 ** result < value ? 1 : 0);
        }
    }
    /**
     * @dev Return the log in base 256, rounded down, of a positive value.
     * Returns 0 if given 0.
     *
     * Adding one to the result gives the number of pairs of hex symbols needed to represent `value` as a hex string.
     */
    function log256(uint256 value) internal pure returns (uint256) {
        uint256 result = 0;
        unchecked {
            if (value >> 128 > 0) {
                value >>= 128;
                result += 16;
            }
            if (value >> 64 > 0) {
                value >>= 64;
                result += 8;
            }
            if (value >> 32 > 0) {
                value >>= 32;
                result += 4;
            }
            if (value >> 16 > 0) {
                value >>= 16;
                result += 2;
            }
            if (value >> 8 > 0) {
                result += 1;
            }
        }
        return result;
    }
    /**
     * @dev Return the log in base 256, following the selected rounding direction, of a positive value.
     * Returns 0 if given 0.
     */
    function log256(uint256 value, Rounding rounding) internal pure returns (uint256) {
        unchecked {
            uint256 result = log256(value);
            return result + (rounding == Rounding.Up && 1 << (result << 3) < value ? 1 : 0);
        }
    }
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.8.0) (utils/math/SignedMath.sol)
pragma solidity ^0.8.0;
/**
 * @dev Standard signed math utilities missing in the Solidity language.
 */
library SignedMathUpgradeable {
    /**
     * @dev Returns the largest of two signed numbers.
     */
    function max(int256 a, int256 b) internal pure returns (int256) {
        return a > b ? a : b;
    }
    /**
     * @dev Returns the smallest of two signed numbers.
     */
    function min(int256 a, int256 b) internal pure returns (int256) {
        return a < b ? a : b;
    }
    /**
     * @dev Returns the average of two signed numbers without overflow.
     * The result is rounded towards zero.
     */
    function average(int256 a, int256 b) internal pure returns (int256) {
        // Formula from the book "Hacker's Delight"
        int256 x = (a & b) + ((a ^ b) >> 1);
        return x + (int256(uint256(x) >> 255) & (a ^ b));
    }
    /**
     * @dev Returns the absolute unsigned value of a signed value.
     */
    function abs(int256 n) internal pure returns (uint256) {
        unchecked {
            // must be unchecked in order to support `n = type(int256).min`
            return uint256(n >= 0 ? n : -n);
        }
    }
}
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.9.0) (utils/Strings.sol)
pragma solidity ^0.8.0;
import "./math/MathUpgradeable.sol";
import "./math/SignedMathUpgradeable.sol";
/**
 * @dev String operations.
 */
library StringsUpgradeable {
    bytes16 private constant _SYMBOLS = "0123456789abcdef";
    uint8 private constant _ADDRESS_LENGTH = 20;
    /**
     * @dev Converts a `uint256` to its ASCII `string` decimal representation.
     */
    function toString(uint256 value) internal pure returns (string memory) {
        unchecked {
            uint256 length = MathUpgradeable.log10(value) + 1;
            string memory buffer = new string(length);
            uint256 ptr;
            /// @solidity memory-safe-assembly
            assembly {
                ptr := add(buffer, add(32, length))
            }
            while (true) {
                ptr--;
                /// @solidity memory-safe-assembly
                assembly {
                    mstore8(ptr, byte(mod(value, 10), _SYMBOLS))
                }
                value /= 10;
                if (value == 0) break;
            }
            return buffer;
        }
    }
    /**
     * @dev Converts a `int256` to its ASCII `string` decimal representation.
     */
    function toString(int256 value) internal pure returns (string memory) {
        return string(abi.encodePacked(value < 0 ? "-" : "", toString(SignedMathUpgradeable.abs(value))));
    }
    /**
     * @dev Converts a `uint256` to its ASCII `string` hexadecimal representation.
     */
    function toHexString(uint256 value) internal pure returns (string memory) {
        unchecked {
            return toHexString(value, MathUpgradeable.log256(value) + 1);
        }
    }
    /**
     * @dev Converts a `uint256` to its ASCII `string` hexadecimal representation with fixed length.
     */
    function toHexString(uint256 value, uint256 length) internal pure returns (string memory) {
        bytes memory buffer = new bytes(2 * length + 2);
        buffer[0] = "0";
        buffer[1] = "x";
        for (uint256 i = 2 * length + 1; i > 1; --i) {
            buffer[i] = _SYMBOLS[value & 0xf];
            value >>= 4;
        }
        require(value == 0, "Strings: hex length insufficient");
        return string(buffer);
    }
    /**
     * @dev Converts an `address` with fixed length of 20 bytes to its not checksummed ASCII `string` hexadecimal representation.
     */
    function toHexString(address addr) internal pure returns (string memory) {
        return toHexString(uint256(uint160(addr)), _ADDRESS_LENGTH);
    }
    /**
     * @dev Returns true if the two strings are equal.
     */
    function equal(string memory a, string memory b) internal pure returns (bool) {
        return keccak256(bytes(a)) == keccak256(bytes(b));
    }
}
// SPDX-License-Identifier: Apache-2.0
pragma solidity 0.8.19;
interface IGenericErrors {
  /**
   * @dev Thrown when a parameter is the zero address.
   */
  error ZeroAddressNotAllowed();
}
// SPDX-License-Identifier: Apache-2.0
pragma solidity 0.8.19;
interface IL1MessageManager {
  /**
   * @dev Emitted when L2->L1 message hashes have been added to L1 storage.
   */
  event L2L1MessageHashAddedToInbox(bytes32 indexed messageHash);
  /**
   * @dev Emitted when L1->L2 messages have been anchored on L2 and updated on L1.
   */
  event L1L2MessagesReceivedOnL2(bytes32[] messageHashes);
  /**
   * @dev Thrown when the message has been already sent.
   */
  error MessageAlreadySent();
  /**
   * @dev Thrown when the message has already been claimed.
   */
  error MessageDoesNotExistOrHasAlreadyBeenClaimed();
  /**
   * @dev Thrown when the message has already been received.
   */
  error MessageAlreadyReceived(bytes32 messageHash);
  /**
   * @dev Thrown when the L1->L2 message has not been sent.
   */
  error L1L2MessageNotSent(bytes32 messageHash);
}
// SPDX-License-Identifier: Apache-2.0
pragma solidity 0.8.19;
interface IMessageService {
  /**
   * @dev Emitted when a message is sent.
   * @dev We include the message hash to save hashing costs on the rollup.
   */
  event MessageSent(
    address indexed _from,
    address indexed _to,
    uint256 _fee,
    uint256 _value,
    uint256 _nonce,
    bytes _calldata,
    bytes32 indexed _messageHash
  );
  /**
   * @dev Emitted when a message is claimed.
   */
  event MessageClaimed(bytes32 indexed _messageHash);
  /**
   * @dev Thrown when fees are lower than the minimum fee.
   */
  error FeeTooLow();
  /**
   * @dev Thrown when fees are lower than value.
   */
  error ValueShouldBeGreaterThanFee();
  /**
   * @dev Thrown when the value sent is less than the fee.
   * @dev Value to forward on is msg.value - _fee.
   */
  error ValueSentTooLow();
  /**
   * @dev Thrown when the destination address reverts.
   */
  error MessageSendingFailed(address destination);
  /**
   * @dev Thrown when the destination address reverts.
   */
  error FeePaymentFailed(address recipient);
  /**
   * @notice Sends a message for transporting from the given chain.
   * @dev This function should be called with a msg.value = _value + _fee. The fee will be paid on the destination chain.
   * @param _to The destination address on the destination chain.
   * @param _fee The message service fee on the origin chain.
   * @param _calldata The calldata used by the destination message service to call the destination contract.
   */
  function sendMessage(address _to, uint256 _fee, bytes calldata _calldata) external payable;
  /**
   * @notice Deliver a message to the destination chain.
   * @notice Is called automatically by the Postman, dApp or end user.
   * @param _from The msg.sender calling the origin message service.
   * @param _to The destination address on the destination chain.
   * @param _value The value to be transferred to the destination address.
   * @param _fee The message service fee on the origin chain.
   * @param _feeRecipient Address that will receive the fees.
   * @param _calldata The calldata used by the destination message service to call/forward to the destination contract.
   * @param _nonce Unique message number.
   */
  function claimMessage(
    address _from,
    address _to,
    uint256 _fee,
    uint256 _value,
    address payable _feeRecipient,
    bytes calldata _calldata,
    uint256 _nonce
  ) external;
  /**
   * @notice Returns the original sender of the message on the origin layer.
   * @return The original sender of the message on the origin layer.
   */
  function sender() external view returns (address);
}
// SPDX-License-Identifier: Apache-2.0
pragma solidity 0.8.19;
interface IPauseManager {
  /**
   * @dev Thrown when a specific pause type is paused.
   */
  error IsPaused(bytes32 pauseType);
  /**
   * @dev Thrown when a specific pause type is not paused and expected to be.
   */
  error IsNotPaused(bytes32 pauseType);
  /**
   * @dev Emitted when a pause type is paused.
   */
  event Paused(address messageSender, bytes32 pauseType);
  /**
   * @dev Emitted when a pause type is unpaused.
   */
  event UnPaused(address messageSender, bytes32 pauseType);
}
// SPDX-License-Identifier: Apache-2.0
pragma solidity 0.8.19;
/**
 * @title Contract to manage cross-chain messaging on L1 and rollup proving
 * @author ConsenSys Software Inc.
 */
interface IPlonkVerifier {
  /**
   * @notice Interface for verifier contracts.
   * @param _proof The proof used to verify.
   * @param _public_inputs The computed public inputs for the proof verification.
   */
  function Verify(bytes calldata _proof, uint256[] calldata _public_inputs) external returns (bool);
}
// SPDX-License-Identifier: Apache-2.0
pragma solidity 0.8.19;
interface IRateLimiter {
  /**
   * @dev Thrown when an amount breaches the limit in the period.
   */
  error RateLimitExceeded();
  /**
   * @dev Thrown when the period is initialised to zero.
   */
  error PeriodIsZero();
  /**
   * @dev Thrown when the limit is initialised to zero.
   */
  error LimitIsZero();
  /**
   * @dev Emitted when the amount in the period is reset to zero.
   */
  event AmountUsedInPeriodReset(address indexed resettingAddress);
  /**
   * @dev Emitted when the limit is changed.
   * @dev If the current used amount is higher than the new limit, the used amount is lowered to the limit.
   */
  event LimitAmountChanged(
    address indexed amountChangeBy,
    uint256 amount,
    bool amountUsedLoweredToLimit,
    bool usedAmountResetToZero
  );
  /**
   * @notice Resets the rate limit amount to the amount specified.
   * @param _amount New message hashes.
   */
  function resetRateLimitAmount(uint256 _amount) external;
  /**
   * @notice Resets the amount used in the period to zero.
   */
  function resetAmountUsedInPeriod() external;
}
// SPDX-License-Identifier: Apache-2.0
pragma solidity 0.8.19;
interface IZkEvmV2 {
  struct BlockData {
    bytes32 blockRootHash;
    uint32 l2BlockTimestamp;
    bytes[] transactions;
    bytes32[] l2ToL1MsgHashes;
    bytes fromAddresses;
    uint16[] batchReceptionIndices;
  }
  /**
   * @dev Emitted when a L2 block has been finalized on L1
   */
  event BlockFinalized(uint256 indexed blockNumber, bytes32 indexed stateRootHash);
  /**
   * @dev Emitted when a L2 blocks have been finalized on L1
   */
  event BlocksVerificationDone(uint256 indexed lastBlockFinalized, bytes32 startingRootHash, bytes32 finalRootHash);
  /**
   * @dev Emitted when a verifier is set for a particular proof type
   */
  event VerifierAddressChanged(
    address indexed verifierAddress,
    uint256 indexed proofType,
    address indexed verifierSetBy
  );
  /**
   * @dev Thrown when l2 block timestamp is not correct
   */
  error BlockTimestampError();
  /**
   * @dev Thrown when the starting rootHash does not match the existing state
   */
  error StartingRootHashDoesNotMatch();
  /**
   * @dev Thrown when blockData is empty
   */
  error EmptyBlockDataArray();
  /**
   * @dev Thrown when block contains zero transactions
   */
  error EmptyBlock();
  /**
   * @dev Thrown when zk proof is empty bytes
   */
  error ProofIsEmpty();
  /**
   * @dev Thrown when zk proof type is invalid
   */
  error InvalidProofType();
  /**
   * @dev Thrown when zk proof is invalid
   */
  error InvalidProof();
  /**
   * @notice Adds or updated the verifier contract address for a proof type
   * @dev DEFAULT_ADMIN_ROLE is required to execute
   * @param _newVerifierAddress The address for the verifier contract
   * @param _proofType The proof type being set/updated
   **/
  function setVerifierAddress(address _newVerifierAddress, uint256 _proofType) external;
  /**
   * @notice Finalizes blocks without using a proof
   * @dev DEFAULT_ADMIN_ROLE is required to execute
   * @param _calldata The full BlockData collection - block, transaction and log data
   **/
  function finalizeBlocksWithoutProof(BlockData[] calldata _calldata) external;
  /**
   * @notice Finalizes blocks without using a proof
   * @dev OPERATOR_ROLE is required to execute
   * @dev If the verifier based on proof type is not found, it defaults to the default verifier type
   * @param _calldata The full BlockData collection - block, transaction and log data
   * @param _proof The proof to verified with the proof type verifier contract
   * @param _proofType The proof type to determine which verifier contract to use
   * @param _parentStateRootHash The beginning roothash to start with
   **/
  function finalizeBlocks(
    BlockData[] calldata _calldata,
    bytes calldata _proof,
    uint256 _proofType,
    bytes32 _parentStateRootHash
  ) external;
}
// SPDX-License-Identifier: AGPL-3.0
pragma solidity 0.8.19;
import { IL1MessageManager } from "../../interfaces/IL1MessageManager.sol";
/**
 * @title Contract to manage cross-chain message hashes storage and status on L1.
 * @author ConsenSys Software Inc.
 */
abstract contract L1MessageManager is IL1MessageManager {
  uint8 public constant INBOX_STATUS_UNKNOWN = 0;
  uint8 public constant INBOX_STATUS_RECEIVED = 1;
  uint8 public constant OUTBOX_STATUS_UNKNOWN = 0;
  uint8 public constant OUTBOX_STATUS_SENT = 1;
  uint8 public constant OUTBOX_STATUS_RECEIVED = 2;
  /// @dev There is a uint216 worth of storage layout here.
  /// @dev Mapping to store L1->L2 message hashes status.
  /// @dev messageHash => messageStatus (0: unknown, 1: sent, 2: received).
  mapping(bytes32 => uint256) public outboxL1L2MessageStatus;
  /// @dev Mapping to store L2->L1 message hashes status.
  /// @dev messageHash => messageStatus (0: unknown, 1: received).
  mapping(bytes32 => uint256) public inboxL2L1MessageStatus;
  /// @dev Keep free storage slots for future implementation updates to avoid storage collision.
  // *******************************************************************************************
  // NB: THIS GAP HAS BEEN PUSHED OUT IN FAVOUR OF THE GAP INSIDE THE REENTRANCY CODE
  //uint256[50] private __gap;
  // NB: DO NOT USE THIS GAP
  // *******************************************************************************************
  /**
   * @notice Add a cross-chain L2->L1 message hash in storage.
   * @dev Once the event is emitted, it should be ready for claiming (post block finalization).
   * @param  _messageHash Hash of the message.
   */
  function _addL2L1MessageHash(bytes32 _messageHash) internal {
    if (inboxL2L1MessageStatus[_messageHash] != INBOX_STATUS_UNKNOWN) {
      revert MessageAlreadyReceived(_messageHash);
    }
    inboxL2L1MessageStatus[_messageHash] = INBOX_STATUS_RECEIVED;
    emit L2L1MessageHashAddedToInbox(_messageHash);
  }
  /**
   * @notice Update the status of L2->L1 message when a user claims a message on L1.
   * @dev The L2->L1 message is removed from storage.
   * @dev Due to the nature of the rollup, we should not get a second entry of this.
   * @param  _messageHash Hash of the message.
   */
  function _updateL2L1MessageStatusToClaimed(bytes32 _messageHash) internal {
    if (inboxL2L1MessageStatus[_messageHash] != INBOX_STATUS_RECEIVED) {
      revert MessageDoesNotExistOrHasAlreadyBeenClaimed();
    }
    delete inboxL2L1MessageStatus[_messageHash];
  }
  /**
   * @notice Add L1->L2 message hash in storage when a message is sent on L1.
   * @param  _messageHash Hash of the message.
   */
  function _addL1L2MessageHash(bytes32 _messageHash) internal {
    outboxL1L2MessageStatus[_messageHash] = OUTBOX_STATUS_SENT;
  }
  /**
   * @notice Update the status of L1->L2 messages as received when messages has been stored on L2.
   * @dev The expectation here is that the rollup is limited to 100 hashes being added here - array is not open ended.
   * @param  _messageHashes List of message hashes.
   */
  function _updateL1L2MessageStatusToReceived(bytes32[] memory _messageHashes) internal {
    uint256 messageHashArrayLength = _messageHashes.length;
    for (uint256 i; i < messageHashArrayLength; ) {
      bytes32 messageHash = _messageHashes[i];
      uint256 existingStatus = outboxL1L2MessageStatus[messageHash];
      if (existingStatus == OUTBOX_STATUS_UNKNOWN) {
        revert L1L2MessageNotSent(messageHash);
      }
      if (existingStatus != OUTBOX_STATUS_RECEIVED) {
        outboxL1L2MessageStatus[messageHash] = OUTBOX_STATUS_RECEIVED;
      }
      unchecked {
        i++;
      }
    }
    emit L1L2MessagesReceivedOnL2(_messageHashes);
  }
}
// SPDX-License-Identifier: AGPL-3.0
pragma solidity 0.8.19;
import { Initializable } from "@openzeppelin/contracts-upgradeable/proxy/utils/Initializable.sol";
import { ReentrancyGuardUpgradeable } from "@openzeppelin/contracts-upgradeable/security/ReentrancyGuardUpgradeable.sol";
import { IMessageService } from "../../interfaces/IMessageService.sol";
import { IGenericErrors } from "../../interfaces/IGenericErrors.sol";
import { PauseManager } from "../lib/PauseManager.sol";
import { RateLimiter } from "../lib/RateLimiter.sol";
import { L1MessageManager } from "./L1MessageManager.sol";
/**
 * @title Contract to manage cross-chain messaging on L1.
 * @author ConsenSys Software Inc.
 */
abstract contract L1MessageService is
  Initializable,
  RateLimiter,
  L1MessageManager,
  ReentrancyGuardUpgradeable,
  PauseManager,
  IMessageService,
  IGenericErrors
{
  // @dev This is initialised to save user cost with existing slot.
  uint256 public nextMessageNumber;
  address private _messageSender;
  // Keep free storage slots for future implementation updates to avoid storage collision.
  uint256[50] private __gap;
  // @dev adding these should not affect storage as they are constants and are store in bytecode
  uint256 private constant REFUND_OVERHEAD_IN_GAS = 42000;
  /**
   * @notice Initialises underlying message service dependencies.
   * @dev _messageSender is initialised to a non-zero value for gas efficiency on claiming.
   * @param _limitManagerAddress The address owning the rate limiting management role.
   * @param _pauseManagerAddress The address owning the pause management role.
   * @param _rateLimitPeriod The period to rate limit against.
   * @param _rateLimitAmount The limit allowed for withdrawing the period.
   **/
  function __MessageService_init(
    address _limitManagerAddress,
    address _pauseManagerAddress,
    uint256 _rateLimitPeriod,
    uint256 _rateLimitAmount
  ) internal onlyInitializing {
    if (_limitManagerAddress == address(0)) {
      revert ZeroAddressNotAllowed();
    }
    if (_pauseManagerAddress == address(0)) {
      revert ZeroAddressNotAllowed();
    }
    __ERC165_init();
    __Context_init();
    __AccessControl_init();
    __RateLimiter_init(_rateLimitPeriod, _rateLimitAmount);
    _grantRole(RATE_LIMIT_SETTER_ROLE, _limitManagerAddress);
    _grantRole(PAUSE_MANAGER_ROLE, _pauseManagerAddress);
    nextMessageNumber = 1;
    _messageSender = address(123456789);
  }
  /**
   * @notice Adds a message for sending cross-chain and emits MessageSent.
   * @dev The message number is preset (nextMessageNumber) and only incremented at the end if successful for the next caller.
   * @dev This function should be called with a msg.value = _value + _fee. The fee will be paid on the destination chain.
   * @param _to The address the message is intended for.
   * @param _fee The fee being paid for the message delivery.
   * @param _calldata The calldata to pass to the recipient.
   **/
  function sendMessage(
    address _to,
    uint256 _fee,
    bytes calldata _calldata
  ) external payable whenTypeNotPaused(L1_L2_PAUSE_TYPE) whenTypeNotPaused(GENERAL_PAUSE_TYPE) {
    if (_to == address(0)) {
      revert ZeroAddressNotAllowed();
    }
    if (_fee > msg.value) {
      revert ValueSentTooLow();
    }
    uint256 messageNumber = nextMessageNumber;
    uint256 valueSent = msg.value - _fee;
    bytes32 messageHash = keccak256(abi.encode(msg.sender, _to, _fee, valueSent, messageNumber, _calldata));
    // @dev Status check and revert is in the message manager
    _addL1L2MessageHash(messageHash);
    nextMessageNumber++;
    emit MessageSent(msg.sender, _to, _fee, valueSent, messageNumber, _calldata, messageHash);
  }
  /**
   * @notice Claims and delivers a cross-chain message.
   * @dev _feeRecipient can be set to address(0) to receive as msg.sender.
   * @dev _messageSender is set temporarily when claiming and reset post. Used in sender().
   * @dev _messageSender is reset to address(123456789) to be more gas efficient.
   * @param _from The address of the original sender.
   * @param _to The address the message is intended for.
   * @param _fee The fee being paid for the message delivery.
   * @param _value The value to be transferred to the destination address.
   * @param _feeRecipient The recipient for the fee.
   * @param _calldata The calldata to pass to the recipient.
   * @param _nonce The unique auto generated nonce used when sending the message.
   **/
  function claimMessage(
    address _from,
    address _to,
    uint256 _fee,
    uint256 _value,
    address payable _feeRecipient,
    bytes calldata _calldata,
    uint256 _nonce
  ) external nonReentrant distributeFees(_fee, _to, _calldata, _feeRecipient) {
    _requireTypeNotPaused(L2_L1_PAUSE_TYPE);
    _requireTypeNotPaused(GENERAL_PAUSE_TYPE);
    bytes32 messageHash = keccak256(abi.encode(_from, _to, _fee, _value, _nonce, _calldata));
    // @dev Status check and revert is in the message manager.
    _updateL2L1MessageStatusToClaimed(messageHash);
    _addUsedAmount(_fee + _value);
    _messageSender = _from;
    (bool callSuccess, bytes memory returnData) = _to.call{ value: _value }(_calldata);
    if (!callSuccess) {
      if (returnData.length > 0) {
        assembly {
          let data_size := mload(returnData)
          revert(add(32, returnData), data_size)
        }
      } else {
        revert MessageSendingFailed(_to);
      }
    }
    _messageSender = address(123456789);
    emit MessageClaimed(messageHash);
  }
  /**
   * @notice Claims and delivers a cross-chain message.
   * @dev _messageSender is set temporarily when claiming.
   **/
  function sender() external view returns (address) {
    return _messageSender;
  }
  /**
   * @notice Function to receive funds for liquidity purposes.
   **/
  receive() external payable virtual {}
  /**
   * @notice The unspent fee is refunded if applicable.
   * @param _feeInWei The fee paid for delivery in Wei.
   * @param _to The recipient of the message and gas refund.
   * @param _calldata The calldata of the message.
   **/
  modifier distributeFees(
    uint256 _feeInWei,
    address _to,
    bytes calldata _calldata,
    address _feeRecipient
  ) {
    //pre-execution
    uint256 startingGas = gasleft();
    _;
    //post-execution
    // we have a fee
    if (_feeInWei > 0) {
      // default postman fee
      uint256 deliveryFee = _feeInWei;
      // do we have empty calldata?
      if (_calldata.length == 0) {
        bool isDestinationEOA;
        assembly {
          isDestinationEOA := iszero(extcodesize(_to))
        }
        // are we calling an EOA
        if (isDestinationEOA) {
          // initial + cost to call and refund minus gasleft
          deliveryFee = (startingGas + REFUND_OVERHEAD_IN_GAS - gasleft()) * tx.gasprice;
          if (_feeInWei > deliveryFee) {
            payable(_to).send(_feeInWei - deliveryFee);
          } else {
            deliveryFee = _feeInWei;
          }
        }
      }
      address feeReceiver = _feeRecipient == address(0) ? msg.sender : _feeRecipient;
      bool callSuccess = payable(feeReceiver).send(deliveryFee);
      if (!callSuccess) {
        revert FeePaymentFailed(feeReceiver);
      }
    }
  }
}
// SPDX-License-Identifier: AGPL-3.0
pragma solidity 0.8.19;
/**
 * @title Decoding functions for message service anchoring and bytes slicing.
 * @author ConsenSys Software Inc.
 * @notice You can use this to slice bytes and extract anchoring hashes from calldata.
 **/
library CodecV2 {
  /**
   * @notice Decodes a collection of bytes32 (hashes) from the calldata of a transaction.
   * @dev Extracts and decodes skipping the function selector (selector is expected in the input).
   * @dev A check beforehand must be performed to confirm this is the correct type of transaction.
   * @param _calldataWithSelector The calldata for the transaction.
   * @return bytes32[] - array of message hashes.
   **/
  function _extractXDomainAddHashes(bytes memory _calldataWithSelector) internal pure returns (bytes32[] memory) {
    assembly {
      let len := sub(mload(_calldataWithSelector), 4)
      _calldataWithSelector := add(_calldataWithSelector, 0x4)
      mstore(_calldataWithSelector, len)
    }
    return abi.decode(_calldataWithSelector, (bytes32[]));
  }
}
// SPDX-License-Identifier: AGPL-3.0
pragma solidity 0.8.19;
import { Initializable } from "@openzeppelin/contracts-upgradeable/proxy/utils/Initializable.sol";
import { AccessControlUpgradeable } from "@openzeppelin/contracts-upgradeable/access/AccessControlUpgradeable.sol";
import { IPauseManager } from "../../interfaces/IPauseManager.sol";
/**
 * @title Contract to manage cross-chain function pausing.
 * @author ConsenSys Software Inc.
 */
abstract contract PauseManager is Initializable, IPauseManager, AccessControlUpgradeable {
  bytes32 public constant PAUSE_MANAGER_ROLE = keccak256("PAUSE_MANAGER_ROLE");
  bytes32 public constant GENERAL_PAUSE_TYPE = keccak256("GENERAL_PAUSE_TYPE");
  bytes32 public constant L1_L2_PAUSE_TYPE = keccak256("L1_L2_PAUSE_TYPE");
  bytes32 public constant L2_L1_PAUSE_TYPE = keccak256("L2_L1_PAUSE_TYPE");
  bytes32 public constant PROVING_SYSTEM_PAUSE_TYPE = keccak256("PROVING_SYSTEM_PAUSE_TYPE");
  mapping(bytes32 => bool) public pauseTypeStatuses;
  uint256[10] private _gap;
  /**
   * @dev Modifier to make a function callable only when the type is not paused.
   *
   * Requirements:
   *
   * - The type must not be paused.
   */
  modifier whenTypeNotPaused(bytes32 _pauseType) {
    _requireTypeNotPaused(_pauseType);
    _;
  }
  /**
   * @dev Modifier to make a function callable only when the type is paused.
   *
   * Requirements:
   *
   * - The type must not be paused.
   */
  modifier whenTypePaused(bytes32 _pauseType) {
    _requireTypePaused(_pauseType);
    _;
  }
  /**
   * @dev Throws if the type is not paused.
   * @param _pauseType The keccak256 pause type being checked,
   */
  function _requireTypePaused(bytes32 _pauseType) internal view virtual {
    if (!pauseTypeStatuses[_pauseType]) {
      revert IsNotPaused(_pauseType);
    }
  }
  /**
   * @dev Throws if the type is paused.
   * @param _pauseType The keccak256 pause type being checked,
   */
  function _requireTypeNotPaused(bytes32 _pauseType) internal view virtual {
    if (pauseTypeStatuses[_pauseType]) {
      revert IsPaused(_pauseType);
    }
  }
  /**
   * @notice Pauses functionality by specific type.
   * @dev Requires PAUSE_MANAGER_ROLE.
   * @param _pauseType keccak256 pause type.
   **/
  function pauseByType(bytes32 _pauseType) external whenTypeNotPaused(_pauseType) onlyRole(PAUSE_MANAGER_ROLE) {
    pauseTypeStatuses[_pauseType] = true;
    emit Paused(_msgSender(), _pauseType);
  }
  /**
   * @notice Unpauses functionality by specific type.
   * @dev Requires PAUSE_MANAGER_ROLE.
   * @param _pauseType keccak256 pause type.
   **/
  function unPauseByType(bytes32 _pauseType) external whenTypePaused(_pauseType) onlyRole(PAUSE_MANAGER_ROLE) {
    pauseTypeStatuses[_pauseType] = false;
    emit UnPaused(_msgSender(), _pauseType);
  }
}
// SPDX-License-Identifier: AGPL-3.0
pragma solidity 0.8.19;
import { Initializable } from "@openzeppelin/contracts-upgradeable/proxy/utils/Initializable.sol";
import { AccessControlUpgradeable } from "@openzeppelin/contracts-upgradeable/access/AccessControlUpgradeable.sol";
import { IRateLimiter } from "../../interfaces/IRateLimiter.sol";
/**
 * @title Rate Limiter by period and amount using the block timestamp.
 * @author ConsenSys Software Inc.
 * @notice You can use this control numeric limits over a period using timestamp.
 **/
contract RateLimiter is Initializable, IRateLimiter, AccessControlUpgradeable {
  bytes32 public constant RATE_LIMIT_SETTER_ROLE = keccak256("RATE_LIMIT_SETTER_ROLE");
  uint256 public periodInSeconds; // how much time before limit resets.
  uint256 public limitInWei; // max ether to withdraw per period.
  // @dev Public for ease of consumption.
  // @notice The time at which the current period ends at.
  uint256 public currentPeriodEnd;
  // @dev Public for ease of consumption.
  // @notice Amounts already withdrawn this period.
  uint256 public currentPeriodAmountInWei;
  uint256[10] private _gap;
  /**
   * @notice Initialises the limits and period for the rate limiter.
   * @param _periodInSeconds The length of the period in seconds.
   * @param _limitInWei The limit allowed in the period in Wei.
   **/
  function __RateLimiter_init(uint256 _periodInSeconds, uint256 _limitInWei) internal onlyInitializing {
    if (_periodInSeconds == 0) {
      revert PeriodIsZero();
    }
    if (_limitInWei == 0) {
      revert LimitIsZero();
    }
    periodInSeconds = _periodInSeconds;
    limitInWei = _limitInWei;
    currentPeriodEnd = block.timestamp + _periodInSeconds;
  }
  /**
   * @notice Increments the amount used in the period.
   * @dev The amount determining logic is external to this (e.g. fees are included when calling here).
   * @dev Reverts if the limit is breached.
   * @param _usedAmount The amount used to be added.
   **/
  function _addUsedAmount(uint256 _usedAmount) internal {
    uint256 currentPeriodAmountTemp;
    if (currentPeriodEnd < block.timestamp) {
      currentPeriodEnd = block.timestamp + periodInSeconds;
      currentPeriodAmountTemp = _usedAmount;
    } else {
      currentPeriodAmountTemp = currentPeriodAmountInWei + _usedAmount;
    }
    if (currentPeriodAmountTemp > limitInWei) {
      revert RateLimitExceeded();
    }
    currentPeriodAmountInWei = currentPeriodAmountTemp;
  }
  /**
   * @notice Resets the rate limit amount.
   * @dev If the used amount is higher, it is set to the limit to avoid confusion/issues.
   * @dev Only the RATE_LIMIT_SETTER_ROLE is allowed to execute this function.
   * @dev Emits the LimitAmountChanged event.
   * @dev usedLimitAmountToSet will use the default value of zero if period has expired
   * @param _amount The amount to reset the limit to.
   **/
  function resetRateLimitAmount(uint256 _amount) external onlyRole(RATE_LIMIT_SETTER_ROLE) {
    uint256 usedLimitAmountToSet;
    bool amountUsedLoweredToLimit;
    bool usedAmountResetToZero;
    if (currentPeriodEnd < block.timestamp) {
      currentPeriodEnd = block.timestamp + periodInSeconds;
      usedAmountResetToZero = true;
    } else {
      if (_amount < currentPeriodAmountInWei) {
        usedLimitAmountToSet = _amount;
        amountUsedLoweredToLimit = true;
      }
    }
    limitInWei = _amount;
    if (usedAmountResetToZero || amountUsedLoweredToLimit) {
      currentPeriodAmountInWei = usedLimitAmountToSet;
    }
    emit LimitAmountChanged(_msgSender(), _amount, amountUsedLoweredToLimit, usedAmountResetToZero);
  }
  /**
   * @notice Resets the amount used to zero.
   * @dev Only the RATE_LIMIT_SETTER_ROLE is allowed to execute this function.
   * @dev Emits the AmountUsedInPeriodReset event.
   **/
  function resetAmountUsedInPeriod() external onlyRole(RATE_LIMIT_SETTER_ROLE) {
    currentPeriodAmountInWei = 0;
    emit AmountUsedInPeriodReset(_msgSender());
  }
}
// SPDX-License-Identifier: Apache-2.0
/**
 * @author Hamdi Allam hamdi.allam97@gmail.com
 * @notice Please reach out with any questions or concerns.
 */
pragma solidity 0.8.19;
error NotList();
error WrongBytesLength();
error NoNext();
error MemoryOutOfBounds(uint256 inde);
library RLPReader {
  uint8 internal constant STRING_SHORT_START = 0x80;
  uint8 internal constant STRING_LONG_START = 0xb8;
  uint8 internal constant LIST_SHORT_START = 0xc0;
  uint8 internal constant LIST_LONG_START = 0xf8;
  uint8 internal constant LIST_SHORT_START_MAX = 0xf7;
  uint8 internal constant WORD_SIZE = 32;
  struct RLPItem {
    uint256 len;
    uint256 memPtr;
  }
  struct Iterator {
    RLPItem item; // Item that's being iterated over.
    uint256 nextPtr; // Position of the next item in the list.
  }
  /**
   * @dev Returns the next element in the iteration. Reverts if it has no next element.
   * @param _self The iterator.
   * @return nextItem The next element in the iteration.
   */
  function _next(Iterator memory _self) internal pure returns (RLPItem memory nextItem) {
    if (!_hasNext(_self)) {
      revert NoNext();
    }
    uint256 ptr = _self.nextPtr;
    uint256 itemLength = _itemLength(ptr);
    _self.nextPtr = ptr + itemLength;
    nextItem.len = itemLength;
    nextItem.memPtr = ptr;
  }
  /**
   * @dev Returns the number 'skiptoNum' element in the iteration.
   * @param _self The iterator.
   * @param _skipToNum Element position in the RLP item iterator to return.
   * @return item The number 'skipToNum' element in the iteration.
   */
  function _skipTo(Iterator memory _self, uint256 _skipToNum) internal pure returns (RLPItem memory item) {
    uint256 lenX;
    uint256 memPtrStart = _self.item.memPtr;
    uint256 endPtr;
    uint256 byte0;
    uint256 byteLen;
    assembly {
      // get first byte to know if it is a short/long list
      byte0 := byte(0, mload(memPtrStart))
      // yul has no if/else so if it a short list ( < long list start )
      switch lt(byte0, LIST_LONG_START)
      case 1 {
        // the length is just the difference in bytes
        lenX := sub(byte0, 0xc0)
      }
      case 0 {
        // at this point we care only about lists, so this is the default
        // get how many next bytes indicate the list length
        byteLen := sub(byte0, 0xf7)
        // move one over to the list length start
        memPtrStart := add(memPtrStart, 1)
        // shift over grabbing the bytelen elements
        lenX := div(mload(memPtrStart), exp(256, sub(32, byteLen)))
      }
      // get the end
      endPtr := add(memPtrStart, lenX)
    }
    uint256 ptr = _self.nextPtr;
    uint256 itemLength = _itemLength(ptr);
    _self.nextPtr = ptr + itemLength;
    for (uint256 i; i < _skipToNum - 1; ) {
      ptr = _self.nextPtr;
      if (ptr > endPtr) revert MemoryOutOfBounds(endPtr);
      itemLength = _itemLength(ptr);
      _self.nextPtr = ptr + itemLength;
      unchecked {
        i++;
      }
    }
    item.len = itemLength;
    item.memPtr = ptr;
  }
  /**
   * @dev Returns true if the iteration has more elements.
   * @param _self The iterator.
   * @return True if the iteration has more elements.
   */
  function _hasNext(Iterator memory _self) internal pure returns (bool) {
    RLPItem memory item = _self.item;
    return _self.nextPtr < item.memPtr + item.len;
  }
  /**
   * @param item RLP encoded bytes.
   * @return newItem The RLP item.
   */
  function _toRlpItem(bytes memory item) internal pure returns (RLPItem memory newItem) {
    uint256 memPtr;
    assembly {
      memPtr := add(item, 0x20)
    }
    newItem.len = item.length;
    newItem.memPtr = memPtr;
  }
  /**
   * @dev Creates an iterator. Reverts if item is not a list.
   * @param _self The RLP item.
   * @return iterator 'Iterator' over the item.
   */
  function _iterator(RLPItem memory _self) internal pure returns (Iterator memory iterator) {
    if (!_isList(_self)) {
      revert NotList();
    }
    uint256 ptr = _self.memPtr + _payloadOffset(_self.memPtr);
    iterator.item = _self;
    iterator.nextPtr = ptr;
  }
  /**
   * @param _item The RLP item.
   * @return (memPtr, len) Tuple: Location of the item's payload in memory.
   */
  function _payloadLocation(RLPItem memory _item) internal pure returns (uint256, uint256) {
    uint256 offset = _payloadOffset(_item.memPtr);
    uint256 memPtr = _item.memPtr + offset;
    uint256 len = _item.len - offset; // data length
    return (memPtr, len);
  }
  /**
   * @param _item The RLP item.
   * @return Indicator whether encoded payload is a list.
   */
  function _isList(RLPItem memory _item) internal pure returns (bool) {
    if (_item.len == 0) return false;
    uint8 byte0;
    uint256 memPtr = _item.memPtr;
    assembly {
      byte0 := byte(0, mload(memPtr))
    }
    if (byte0 < LIST_SHORT_START) return false;
    return true;
  }
  /**
   * @param _item The RLP item.
   * @return result Returns the item as an address.
   */
  function _toAddress(RLPItem memory _item) internal pure returns (address) {
    // 1 byte for the length prefix
    if (_item.len != 21) {
      revert WrongBytesLength();
    }
    return address(uint160(_toUint(_item)));
  }
  /**
   * @param _item The RLP item.
   * @return result Returns the item as a uint256.
   */
  function _toUint(RLPItem memory _item) internal pure returns (uint256 result) {
    if (_item.len == 0 || _item.len > 33) {
      revert WrongBytesLength();
    }
    (uint256 memPtr, uint256 len) = _payloadLocation(_item);
    assembly {
      result := mload(memPtr)
      // Shfit to the correct location if neccesary.
      if lt(len, 32) {
        result := div(result, exp(256, sub(32, len)))
      }
    }
  }
  /**
   * @param _item The RLP item.
   * @return result Returns the item as bytes.
   */
  function _toBytes(RLPItem memory _item) internal pure returns (bytes memory result) {
    if (_item.len == 0) {
      revert WrongBytesLength();
    }
    (uint256 memPtr, uint256 len) = _payloadLocation(_item);
    result = new bytes(len);
    uint256 destPtr;
    assembly {
      destPtr := add(0x20, result)
    }
    _copy(memPtr, destPtr, len);
  }
  /*
   * Private Helpers
   */
  /**
   * @param _memPtr Item memory pointer.
   * @return Entire RLP item byte length.
   */
  function _itemLength(uint256 _memPtr) private pure returns (uint256) {
    uint256 itemLen;
    uint256 dataLen;
    uint256 byte0;
    assembly {
      byte0 := byte(0, mload(_memPtr))
    }
    if (byte0 < STRING_SHORT_START) itemLen = 1;
    else if (byte0 < STRING_LONG_START) itemLen = byte0 - STRING_SHORT_START + 1;
    else if (byte0 < LIST_SHORT_START) {
      assembly {
        let byteLen := sub(byte0, 0xb7) // # Of bytes the actual length is.
        _memPtr := add(_memPtr, 1) // Skip over the first byte.
        /* 32 byte word size */
        dataLen := div(mload(_memPtr), exp(256, sub(32, byteLen))) // Right shifting to get the len.
        itemLen := add(dataLen, add(byteLen, 1))
      }
    } else if (byte0 < LIST_LONG_START) {
      itemLen = byte0 - LIST_SHORT_START + 1;
    } else {
      assembly {
        let byteLen := sub(byte0, 0xf7)
        _memPtr := add(_memPtr, 1)
        dataLen := div(mload(_memPtr), exp(256, sub(32, byteLen))) // Right shifting to the correct length.
        itemLen := add(dataLen, add(byteLen, 1))
      }
    }
    return itemLen;
  }
  /**
   * @param _memPtr Item memory pointer.
   * @return Number of bytes until the data.
   */
  function _payloadOffset(uint256 _memPtr) private pure returns (uint256) {
    uint256 byte0;
    assembly {
      byte0 := byte(0, mload(_memPtr))
    }
    if (byte0 < STRING_SHORT_START) return 0;
    else if (byte0 < STRING_LONG_START || (byte0 >= LIST_SHORT_START && byte0 < LIST_LONG_START)) return 1;
    else if (byte0 < LIST_SHORT_START)
      // being explicit
      return byte0 - (STRING_LONG_START - 1) + 1;
    else return byte0 - (LIST_LONG_START - 1) + 1;
  }
  /**
   * @param _src Pointer to source.
   * @param _dest Pointer to destination.
   * @param _len Amount of memory to copy from the source.
   */
  function _copy(uint256 _src, uint256 _dest, uint256 _len) private pure {
    if (_len == 0) return;
    // copy as many word sizes as possible
    for (; _len >= WORD_SIZE; _len -= WORD_SIZE) {
      assembly {
        mstore(_dest, mload(_src))
      }
      _src += WORD_SIZE;
      _dest += WORD_SIZE;
    }
    if (_len > 0) {
      // Left over bytes. Mask is used to remove unwanted bytes from the word.
      uint256 mask = 256 ** (WORD_SIZE - _len) - 1;
      assembly {
        let srcpart := and(mload(_src), not(mask)) // Zero out src.
        let destpart := and(mload(_dest), mask) // Retrieve the bytes.
        mstore(_dest, or(destpart, srcpart))
      }
    }
  }
}
// SPDX-License-Identifier: AGPL-3.0
pragma solidity 0.8.19;
import { RLPReader } from "./Rlp.sol";
using RLPReader for RLPReader.RLPItem;
using RLPReader for RLPReader.Iterator;
using RLPReader for bytes;
/*
 * dev Thrown when the transaction data length is too short.
 */
error TransactionShort();
/*
 * dev Thrown when the transaction type is unknown.
 */
error UnknownTransactionType();
/**
 * @title Contract to decode RLP formatted transactions.
 * @author ConsenSys Software Inc.
 */
library TransactionDecoder {
  /**
   * @notice Decodes the transaction extracting the calldata.
   * @param _transaction The RLP transaction.
   * @return data Returns the transaction calldata as bytes.
   */
  function decodeTransaction(bytes calldata _transaction) internal pure returns (bytes memory) {
    if (_transaction.length < 1) {
      revert TransactionShort();
    }
    bytes1 version = _transaction[0];
    if (version == 0x01) {
      return _decodeEIP2930Transaction(_transaction);
    }
    if (version == 0x02) {
      return _decodeEIP1559Transaction(_transaction);
    }
    if (version >= 0xc0) {
      return _decodeLegacyTransaction(_transaction);
    }
    revert UnknownTransactionType();
  }
  /**
   * @notice Decodes the EIP1559 transaction extracting the calldata.
   * @param _transaction The RLP transaction.
   * @return data Returns the transaction calldata as bytes.
   */
  function _decodeEIP1559Transaction(bytes calldata _transaction) private pure returns (bytes memory data) {
    bytes memory txData = _transaction[1:]; // skip the version byte
    RLPReader.RLPItem memory rlp = txData._toRlpItem();
    RLPReader.Iterator memory it = rlp._iterator();
    data = it._skipTo(8)._toBytes();
  }
  /**
   * @notice Decodes the EIP29230 transaction extracting the calldata.
   * @param _transaction The RLP transaction.
   * @return data Returns the transaction calldata as bytes.
   */
  function _decodeEIP2930Transaction(bytes calldata _transaction) private pure returns (bytes memory data) {
    bytes memory txData = _transaction[1:]; // skip the version byte
    RLPReader.RLPItem memory rlp = txData._toRlpItem();
    RLPReader.Iterator memory it = rlp._iterator();
    data = it._skipTo(7)._toBytes();
  }
  /**
   * @notice Decodes the legacy transaction extracting the calldata.
   * @param _transaction The RLP transaction.
   * @return data Returns the transaction calldata as bytes.
   */
  function _decodeLegacyTransaction(bytes calldata _transaction) private pure returns (bytes memory data) {
    bytes memory txData = _transaction;
    RLPReader.RLPItem memory rlp = txData._toRlpItem();
    RLPReader.Iterator memory it = rlp._iterator();
    data = it._skipTo(6)._toBytes();
  }
}
// SPDX-License-Identifier: AGPL-3.0
pragma solidity 0.8.19;
import { Initializable } from "@openzeppelin/contracts-upgradeable/proxy/utils/Initializable.sol";
import { AccessControlUpgradeable } from "@openzeppelin/contracts-upgradeable/access/AccessControlUpgradeable.sol";
import { L1MessageService } from "./messageService/l1/L1MessageService.sol";
import { TransactionDecoder } from "./messageService/lib/TransactionDecoder.sol";
import { IZkEvmV2 } from "./interfaces/IZkEvmV2.sol";
import { IPlonkVerifier } from "./interfaces/IPlonkVerifier.sol";
import { CodecV2 } from "./messageService/lib/Codec.sol";
/**
 * @title Contract to manage cross-chain messaging on L1 and rollup proving.
 * @author ConsenSys Software Inc.
 */
contract ZkEvmV2 is IZkEvmV2, Initializable, AccessControlUpgradeable, L1MessageService {
  using TransactionDecoder for *;
  using CodecV2 for *;
  uint256 private constant MODULO_R = 21888242871839275222246405745257275088548364400416034343698204186575808495617;
  bytes32 public constant OPERATOR_ROLE = keccak256("OPERATOR_ROLE");
  uint256 public currentTimestamp;
  uint256 public currentL2BlockNumber;
  mapping(uint256 => bytes32) public stateRootHashes;
  mapping(uint256 => address) public verifiers;
  uint256[50] private __gap;
  /// @custom:oz-upgrades-unsafe-allow constructor
  constructor() {
    _disableInitializers();
  }
  /**
   * @notice Initializes zkEvm and underlying service dependencies.
   * @dev DEFAULT_ADMIN_ROLE is set for the security council.
   * @dev OPERATOR_ROLE is set for operators.
   * @param _initialStateRootHash The initial hash at migration used for proof verification.
   * @param _initialL2BlockNumber The initial block number at migration.
   * @param _defaultVerifier The default verifier for rollup proofs.
   * @param _securityCouncil The address for the security council performing admin operations.
   * @param _operators The allowed rollup operators at initialization.
   * @param _rateLimitPeriodInSeconds The period in which withdrawal amounts and fees will be accumulated.
   * @param _rateLimitAmountInWei The limit allowed for withdrawing in the period.
   **/
  function initialize(
    bytes32 _initialStateRootHash,
    uint256 _initialL2BlockNumber,
    address _defaultVerifier,
    address _securityCouncil,
    address[] calldata _operators,
    uint256 _rateLimitPeriodInSeconds,
    uint256 _rateLimitAmountInWei
  ) public initializer {
    if (_defaultVerifier == address(0)) {
      revert ZeroAddressNotAllowed();
    }
    for (uint256 i; i < _operators.length; ) {
      if (_operators[i] == address(0)) {
        revert ZeroAddressNotAllowed();
      }
      _grantRole(OPERATOR_ROLE, _operators[i]);
      unchecked {
        i++;
      }
    }
    _grantRole(DEFAULT_ADMIN_ROLE, _securityCouncil);
    __MessageService_init(_securityCouncil, _securityCouncil, _rateLimitPeriodInSeconds, _rateLimitAmountInWei);
    verifiers[0] = _defaultVerifier;
    currentL2BlockNumber = _initialL2BlockNumber;
    stateRootHashes[_initialL2BlockNumber] = _initialStateRootHash;
  }
  /**
   * @notice Adds or updates the verifier contract address for a proof type.
   * @dev DEFAULT_ADMIN_ROLE is required to execute.
   * @param _newVerifierAddress The address for the verifier contract.
   * @param _proofType The proof type being set/updated.
   **/
  function setVerifierAddress(address _newVerifierAddress, uint256 _proofType) external onlyRole(DEFAULT_ADMIN_ROLE) {
    if (_newVerifierAddress == address(0)) {
      revert ZeroAddressNotAllowed();
    }
    emit VerifierAddressChanged(_newVerifierAddress, _proofType, msg.sender);
    verifiers[_proofType] = _newVerifierAddress;
  }
  /**
   * @notice Finalizes blocks without using a proof.
   * @dev DEFAULT_ADMIN_ROLE is required to execute.
   * @dev _blocksData[0].fromAddresses is a temporary workaround to pass bytes calldata
   * @param _blocksData The full BlockData collection - block, transaction and log data.
   **/
  function finalizeBlocksWithoutProof(
    BlockData[] calldata _blocksData
  ) external whenTypeNotPaused(GENERAL_PAUSE_TYPE) onlyRole(DEFAULT_ADMIN_ROLE) {
    _finalizeBlocks(_blocksData, _blocksData[0].fromAddresses, 0, bytes32(0), false);
  }
  /**
   * @notice Finalizes blocks using a proof.
   * @dev OPERATOR_ROLE is required to execute.
   * @dev If the verifier based on proof type is not found, it reverts.
   * @param _blocksData The full BlockData collection - block, transaction and log data.
   * @param _proof The proof to be verified with the proof type verifier contract.
   * @param _proofType The proof type to determine which verifier contract to use.
   * @param _parentStateRootHash The starting roothash for the last known block.
   **/
  function finalizeBlocks(
    BlockData[] calldata _blocksData,
    bytes calldata _proof,
    uint256 _proofType,
    bytes32 _parentStateRootHash
  )
    external
    whenTypeNotPaused(PROVING_SYSTEM_PAUSE_TYPE)
    whenTypeNotPaused(GENERAL_PAUSE_TYPE)
    onlyRole(OPERATOR_ROLE)
  {
    if (stateRootHashes[currentL2BlockNumber] != _parentStateRootHash) {
      revert StartingRootHashDoesNotMatch();
    }
    _finalizeBlocks(_blocksData, _proof, _proofType, _parentStateRootHash, true);
  }
  /**
   * @notice Finalizes blocks with or without using a proof depending on _shouldProve
   * @dev If the verifier based on proof type is not found, it reverts.
   * @param _blocksData The full BlockData collection - block, transaction and log data.
   * @param _proof The proof to be verified with the proof type verifier contract.
   * @param _proofType The proof type to determine which verifier contract to use.
   * @param _parentStateRootHash The starting roothash for the last known block.
   **/
  function _finalizeBlocks(
    BlockData[] calldata _blocksData,
    bytes calldata _proof,
    uint256 _proofType,
    bytes32 _parentStateRootHash,
    bool _shouldProve
  ) private {
    if (_blocksData.length == 0) {
      revert EmptyBlockDataArray();
    }
    uint256 currentBlockNumberTemp = currentL2BlockNumber;
    uint256 firstBlockNumber;
    unchecked {
      firstBlockNumber = currentBlockNumberTemp + 1;
    }
    uint256[] memory timestamps = new uint256[](_blocksData.length);
    bytes32[] memory blockHashes = new bytes32[](_blocksData.length);
    bytes32[] memory hashOfRootHashes;
    unchecked {
      hashOfRootHashes = new bytes32[](_blocksData.length + 1);
    }
    hashOfRootHashes[0] = _parentStateRootHash;
    bytes32 hashOfTxHashes;
    bytes32 hashOfMessageHashes;
    for (uint256 i; i < _blocksData.length; ) {
      BlockData calldata blockInfo = _blocksData[i];
      if (blockInfo.l2BlockTimestamp >= block.timestamp) {
        revert BlockTimestampError();
      }
      hashOfTxHashes = _processBlockTransactions(blockInfo.transactions, blockInfo.batchReceptionIndices);
      hashOfMessageHashes = _processMessageHashes(blockInfo.l2ToL1MsgHashes);
      unchecked {
        ++currentBlockNumberTemp;
      }
      blockHashes[i] = keccak256(
        abi.encodePacked(
          hashOfTxHashes,
          hashOfMessageHashes,
          keccak256(abi.encodePacked(blockInfo.batchReceptionIndices)),
          keccak256(blockInfo.fromAddresses)
        )
      );
      timestamps[i] = blockInfo.l2BlockTimestamp;
      unchecked {
        hashOfRootHashes[i + 1] = blockInfo.blockRootHash;
      }
      emit BlockFinalized(currentBlockNumberTemp, blockInfo.blockRootHash);
      unchecked {
        i++;
      }
    }
    unchecked {
      uint256 arrayIndex = _blocksData.length - 1;
      stateRootHashes[currentBlockNumberTemp] = _blocksData[arrayIndex].blockRootHash;
      currentTimestamp = _blocksData[arrayIndex].l2BlockTimestamp;
      currentL2BlockNumber = currentBlockNumberTemp;
    }
    if (_shouldProve) {
      uint256 publicInput = uint256(
        keccak256(
          abi.encode(
            keccak256(abi.encodePacked(blockHashes)),
            firstBlockNumber,
            keccak256(abi.encodePacked(timestamps)),
            keccak256(abi.encodePacked(hashOfRootHashes))
          )
        )
      );
      assembly {
        publicInput := mod(publicInput, MODULO_R)
      }
      _verifyProof(publicInput, _proofType, _proof, _parentStateRootHash);
    }
  }
  /**
   * @notice Hashes all transactions individually and then hashes the packed hash array.
   * @dev Updates the outbox status on L1 as received.
   * @param _transactions The transactions in a particular block.
   * @param _batchReceptionIndices The indexes where the transaction type is the L1->L2 achoring message hashes transaction.
   **/
  function _processBlockTransactions(
    bytes[] calldata _transactions,
    uint16[] calldata _batchReceptionIndices
  ) internal returns (bytes32 hashOfTxHashes) {
    bytes32[] memory transactionHashes = new bytes32[](_transactions.length);
    if (_transactions.length == 0) {
      revert EmptyBlock();
    }
    for (uint256 i; i < _batchReceptionIndices.length; ) {
      _updateL1L2MessageStatusToReceived(
        TransactionDecoder.decodeTransaction(_transactions[_batchReceptionIndices[i]])._extractXDomainAddHashes()
      );
      unchecked {
        i++;
      }
    }
    for (uint256 i; i < _transactions.length; ) {
      transactionHashes[i] = keccak256(_transactions[i]);
      unchecked {
        i++;
      }
    }
    hashOfTxHashes = keccak256(abi.encodePacked(transactionHashes));
  }
  /**
   * @notice Anchors message hashes and hashes the packed hash array.
   * @dev Also adds L2->L1 sent message hashes for later claiming.
   * @param _messageHashes The hashes in the message sent event logs.
   **/
  function _processMessageHashes(bytes32[] calldata _messageHashes) internal returns (bytes32 hashOfLogHashes) {
    for (uint256 i; i < _messageHashes.length; ) {
      _addL2L1MessageHash(_messageHashes[i]);
      unchecked {
        i++;
      }
    }
    hashOfLogHashes = keccak256(abi.encodePacked(_messageHashes));
  }
  /**
   * @notice Verifies the proof with locally computed public inputs.
   * @dev If the verifier based on proof type is not found, it reverts with InvalidProofType.
   * @param _publicInputHash The full BlockData collection - block, transaction and log data.
   * @param _proofType The proof type to determine which verifier contract to use.
   * @param _proof The proof to be verified with the proof type verifier contract.
   * @param _parentStateRootHash The beginning roothash to start with.
   **/
  function _verifyProof(
    uint256 _publicInputHash,
    uint256 _proofType,
    bytes calldata _proof,
    bytes32 _parentStateRootHash
  ) private {
    uint256[] memory input = new uint256[](1);
    input[0] = _publicInputHash;
    address verifierToUse = verifiers[_proofType];
    if (verifierToUse == address(0)) {
      revert InvalidProofType();
    }
    bool success = IPlonkVerifier(verifierToUse).Verify(_proof, input);
    if (!success) {
      revert InvalidProof();
    }
    emit BlocksVerificationDone(currentL2BlockNumber, _parentStateRootHash, stateRootHashes[currentL2BlockNumber]);
  }
}

// SPDX-License-Identifier: Apache-2.0
// Copyright 2023 Consensys Software Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
// Code generated by gnark DO NOT EDIT
pragma solidity 0.8.19;
/// @custom:security-contact security-report@linea.build
contract PlonkVerifierFull {
  uint256 private constant R_MOD = 21888242871839275222246405745257275088548364400416034343698204186575808495617;
  uint256 private constant P_MOD = 21888242871839275222246405745257275088696311157297823662689037894645226208583;
  uint256 private constant G2_SRS_0_X_0 = 11559732032986387107991004021392285783925812861821192530917403151452391805634;
  uint256 private constant G2_SRS_0_X_1 = 10857046999023057135944570762232829481370756359578518086990519993285655852781;
  uint256 private constant G2_SRS_0_Y_0 = 4082367875863433681332203403145435568316851327593401208105741076214120093531;
  uint256 private constant G2_SRS_0_Y_1 = 8495653923123431417604973247489272438418190587263600148770280649306958101930;
  uint256 private constant G2_SRS_1_X_0 = 15805639136721018565402881920352193254830339253282065586954346329754995870280;
  uint256 private constant G2_SRS_1_X_1 = 19089565590083334368588890253123139704298730990782503769911324779715431555531;
  uint256 private constant G2_SRS_1_Y_0 = 9779648407879205346559610309258181044130619080926897934572699915909528404984;
  uint256 private constant G2_SRS_1_Y_1 = 6779728121489434657638426458390319301070371227460768374343986326751507916979;
  uint256 private constant G1_SRS_X = 14312776538779914388377568895031746459131577658076416373430523308756343304251;
  uint256 private constant G1_SRS_Y = 11763105256161367503191792604679297387056316997144156930871823008787082098465;
  // ----------------------- vk ---------------------
  uint256 private constant VK_DOMAIN_SIZE = 33554432;
  uint256 private constant VK_INV_DOMAIN_SIZE =
    21888242219518804655518433051623070663413851959604507555939307129453691614729;
  uint256 private constant VK_OMEGA = 19200870435978225707111062059747084165650991997241425080699860725083300967194;
  uint256 private constant VK_QL_COM_X = 10446052147746697412559683759538649426290181956631733467139353561163453700224;
  uint256 private constant VK_QL_COM_Y = 15313223445996065579722945825801846873429305267027028162791049009353319405619;
  uint256 private constant VK_QR_COM_X = 4877397415708227272405575965534231106974901475570932516051744663704508231277;
  uint256 private constant VK_QR_COM_Y = 20179121660200663580844024253765721800515493721165785997611401898473813567491;
  uint256 private constant VK_QM_COM_X = 7523778281064055405385956372686428313035774644723618626532752434153767923966;
  uint256 private constant VK_QM_COM_Y = 12130217548763901121576911865066270947160011595911834304588556694304396653164;
  uint256 private constant VK_QO_COM_X = 17450182488321469742082496209983670342212255167102994061039440621659979053736;
  uint256 private constant VK_QO_COM_Y = 14939458223572766589829952083798517155169536342310870996749970795362072329038;
  uint256 private constant VK_QK_COM_X = 1519862851017521984724458901879876795363632645464740628205844910454538246927;
  uint256 private constant VK_QK_COM_Y = 5315499283572682834667760846627242815126177328677429020353263962859617925427;
  uint256 private constant VK_S1_COM_X = 16039161498106344819025426776567233478978580093937559279983969689933735985131;
  uint256 private constant VK_S1_COM_Y = 148102320207284854063465359762911107358052328375832763616531684104163828563;
  uint256 private constant VK_S2_COM_X = 17222223998135532150537091416840566449734233201799865858841530631784955956287;
  uint256 private constant VK_S2_COM_Y = 10463900706059628613775065660448641729045260243072593783306623698260102823776;
  uint256 private constant VK_S3_COM_X = 2503702965425667055301933416345995064882037813614672509289644812512722118260;
  uint256 private constant VK_S3_COM_Y = 18637248125677620369943295414462138691074411588673937987551862216128071554357;
  uint256 private constant VK_COSET_SHIFT = 5;
  uint256 private constant VK_QCP_0_X = 7486378754358300143079007316105442927715247332265421307791532633293137390056;
  uint256 private constant VK_QCP_0_Y = 7221362263941134072999176102524572311034576738179410483316096845330388259602;
  uint256 private constant VK_INDEX_COMMIT_API0 = 16806320;
  uint256 private constant VK_NB_CUSTOM_GATES = 1;
  // ------------------------------------------------
  // offset proof
  uint256 private constant PROOF_L_COM_X = 0x00;
  uint256 private constant PROOF_L_COM_Y = 0x20;
  uint256 private constant PROOF_R_COM_X = 0x40;
  uint256 private constant PROOF_R_COM_Y = 0x60;
  uint256 private constant PROOF_O_COM_X = 0x80;
  uint256 private constant PROOF_O_COM_Y = 0xa0;
  // h = h_0 + x^{n+2}h_1 + x^{2(n+2)}h_2
  uint256 private constant PROOF_H_0_X = 0xc0;
  uint256 private constant PROOF_H_0_Y = 0xe0;
  uint256 private constant PROOF_H_1_X = 0x100;
  uint256 private constant PROOF_H_1_Y = 0x120;
  uint256 private constant PROOF_H_2_X = 0x140;
  uint256 private constant PROOF_H_2_Y = 0x160;
  // wire values at zeta
  uint256 private constant PROOF_L_AT_ZETA = 0x180;
  uint256 private constant PROOF_R_AT_ZETA = 0x1a0;
  uint256 private constant PROOF_O_AT_ZETA = 0x1c0;
  //uint256[STATE_WIDTH-1] permutation_polynomials_at_zeta; // Sσ1(zeta),Sσ2(zeta)
  uint256 private constant PROOF_S1_AT_ZETA = 0x1e0; // Sσ1(zeta)
  uint256 private constant PROOF_S2_AT_ZETA = 0x200; // Sσ2(zeta)
  //Bn254.G1Point grand_product_commitment;                 // [z(x)]
  uint256 private constant PROOF_GRAND_PRODUCT_COMMITMENT_X = 0x220;
  uint256 private constant PROOF_GRAND_PRODUCT_COMMITMENT_Y = 0x240;
  uint256 private constant PROOF_GRAND_PRODUCT_AT_ZETA_OMEGA = 0x260; // z(w*zeta)
  uint256 private constant PROOF_QUOTIENT_POLYNOMIAL_AT_ZETA = 0x280; // t(zeta)
  uint256 private constant PROOF_LINEARISED_POLYNOMIAL_AT_ZETA = 0x2a0; // r(zeta)
  // Folded proof for the opening of H, linearised poly, l, r, o, s_1, s_2, qcp
  uint256 private constant PROOF_BATCH_OPENING_AT_ZETA_X = 0x2c0; // [Wzeta]
  uint256 private constant PROOF_BATCH_OPENING_AT_ZETA_Y = 0x2e0;
  uint256 private constant PROOF_OPENING_AT_ZETA_OMEGA_X = 0x300;
  uint256 private constant PROOF_OPENING_AT_ZETA_OMEGA_Y = 0x320;
  uint256 private constant PROOF_OPENING_QCP_AT_ZETA = 0x340;
  uint256 private constant PROOF_COMMITMENTS_WIRES_CUSTOM_GATES = 0x360;
  // -> next part of proof is
  // [ openings_selector_commits || commitments_wires_commit_api]
  // -------- offset state
  // challenges to check the claimed quotient
  uint256 private constant STATE_ALPHA = 0x00;
  uint256 private constant STATE_BETA = 0x20;
  uint256 private constant STATE_GAMMA = 0x40;
  uint256 private constant STATE_ZETA = 0x60;
  // reusable value
  uint256 private constant STATE_ALPHA_SQUARE_LAGRANGE_0 = 0x80;
  // commitment to H
  uint256 private constant STATE_FOLDED_H_X = 0xa0;
  uint256 private constant STATE_FOLDED_H_Y = 0xc0;
  // commitment to the linearised polynomial
  uint256 private constant STATE_LINEARISED_POLYNOMIAL_X = 0xe0;
  uint256 private constant STATE_LINEARISED_POLYNOMIAL_Y = 0x100;
  // Folded proof for the opening of H, linearised poly, l, r, o, s_1, s_2, qcp
  uint256 private constant STATE_FOLDED_CLAIMED_VALUES = 0x120;
  // folded digests of H, linearised poly, l, r, o, s_1, s_2, qcp
  uint256 private constant STATE_FOLDED_DIGESTS_X = 0x140;
  uint256 private constant STATE_FOLDED_DIGESTS_Y = 0x160;
  uint256 private constant STATE_PI = 0x180;
  uint256 private constant STATE_ZETA_POWER_N_MINUS_ONE = 0x1a0;
  uint256 private constant STATE_GAMMA_KZG = 0x1c0;
  uint256 private constant STATE_SUCCESS = 0x1e0;
  uint256 private constant STATE_CHECK_VAR = 0x200; // /!\\ this slot is used for debugging only
  uint256 private constant STATE_LAST_MEM = 0x220;
  // -------- errors
  uint256 private constant ERROR_STRING_ID = 0x08c379a000000000000000000000000000000000000000000000000000000000; // selector for function Error(string)
  // -------- utils (for hash_fr)
  uint256 private constant HASH_FR_BB = 340282366920938463463374607431768211456; // 2**128
  uint256 private constant HASH_FR_ZERO_UINT256 = 0;
  uint8 private constant HASH_FR_LEN_IN_BYTES = 48;
  uint8 private constant HASH_FR_SIZE_DOMAIN = 11;
  uint8 private constant HASH_FR_ONE = 1;
  uint8 private constant HASH_FR_TWO = 2;
  /// Verify a Plonk proof.
  /// Reverts if the proof or the public inputs are malformed.
  /// @param proof serialised plonk proof (using gnark's MarshalSolidity)
  /// @param public_inputs (must be reduced)
  /// @return success true if the proof passes false otherwise
  function Verify(bytes calldata proof, uint256[] calldata public_inputs) public view returns (bool success) {
    assembly {
      let mem := mload(0x40)
      let freeMem := add(mem, STATE_LAST_MEM)
      // sanity checks
      check_inputs_size(public_inputs.length, public_inputs.offset)
      check_proof_size(proof.length)
      check_proof_openings_size(proof.offset)
      // compute the challenges
      let prev_challenge_non_reduced
      prev_challenge_non_reduced := derive_gamma(proof.offset, public_inputs.length, public_inputs.offset)
      prev_challenge_non_reduced := derive_beta(prev_challenge_non_reduced)
      prev_challenge_non_reduced := derive_alpha(proof.offset, prev_challenge_non_reduced)
      derive_zeta(proof.offset, prev_challenge_non_reduced)
      // evaluation of Z=Xⁿ-1 at ζ, we save this value
      let zeta := mload(add(mem, STATE_ZETA))
      let zeta_power_n_minus_one := addmod(pow(zeta, VK_DOMAIN_SIZE, freeMem), sub(R_MOD, 1), R_MOD)
      mstore(add(mem, STATE_ZETA_POWER_N_MINUS_ONE), zeta_power_n_minus_one)
      // public inputs contribution
      let l_pi := sum_pi_wo_api_commit(public_inputs.offset, public_inputs.length, freeMem)
      let l_wocommit := sum_pi_commit(proof.offset, public_inputs.length, freeMem)
      l_pi := addmod(l_wocommit, l_pi, R_MOD)
      mstore(add(mem, STATE_PI), l_pi)
      compute_alpha_square_lagrange_0()
      verify_quotient_poly_eval_at_zeta(proof.offset)
      fold_h(proof.offset)
      compute_commitment_linearised_polynomial(proof.offset)
      compute_gamma_kzg(proof.offset)
      fold_state(proof.offset)
      batch_verify_multi_points(proof.offset)
      success := mload(add(mem, STATE_SUCCESS))
      // Beginning errors -------------------------------------------------
      /// Called when an operation on Bn254 fails
      /// @dev for instance when calling EcMul on a point not on Bn254.
      function error_ec_op() {
        let ptError := mload(0x40)
        mstore(ptError, ERROR_STRING_ID) // selector for function Error(string)
        mstore(add(ptError, 0x4), 0x20)
        mstore(add(ptError, 0x24), 0x12)
        mstore(add(ptError, 0x44), "error ec operation")
        revert(ptError, 0x64)
      }
      /// Called when one of the public inputs is not reduced.
      function error_inputs_size() {
        let ptError := mload(0x40)
        mstore(ptError, ERROR_STRING_ID) // selector for function Error(string)
        mstore(add(ptError, 0x4), 0x20)
        mstore(add(ptError, 0x24), 0x18)
        mstore(add(ptError, 0x44), "inputs are bigger than r")
        revert(ptError, 0x64)
      }
      /// Called when the size proof is not as expected
      /// @dev to avoid overflow attack for instance
      function error_proof_size() {
        let ptError := mload(0x40)
        mstore(ptError, ERROR_STRING_ID) // selector for function Error(string)
        mstore(add(ptError, 0x4), 0x20)
        mstore(add(ptError, 0x24), 0x10)
        mstore(add(ptError, 0x44), "wrong proof size")
        revert(ptError, 0x64)
      }
      /// Called when one the openings is bigger than r
      /// The openings are the claimed evalutions of a polynomial
      /// in a Kzg proof.
      function error_proof_openings_size() {
        let ptError := mload(0x40)
        mstore(ptError, ERROR_STRING_ID) // selector for function Error(string)
        mstore(add(ptError, 0x4), 0x20)
        mstore(add(ptError, 0x24), 0x16)
        mstore(add(ptError, 0x44), "openings bigger than r")
        revert(ptError, 0x64)
      }
      function error_verify() {
        let ptError := mload(0x40)
        mstore(ptError, ERROR_STRING_ID) // selector for function Error(string)
        mstore(add(ptError, 0x4), 0x20)
        mstore(add(ptError, 0x24), 0xc)
        mstore(add(ptError, 0x44), "error verify")
        revert(ptError, 0x64)
      }
      function error_random_generation() {
        let ptError := mload(0x40)
        mstore(ptError, ERROR_STRING_ID) // selector for function Error(string)
        mstore(add(ptError, 0x4), 0x20)
        mstore(add(ptError, 0x24), 0x14)
        mstore(add(ptError, 0x44), "error random gen kzg")
        revert(ptError, 0x64)
      }
      // end errors -------------------------------------------------
      // Beginning checks -------------------------------------------------
      /// Checks that the public inputs are < R_MOD.
      /// @param s number of public inputs
      /// @param p pointer to the public inputs array
      function check_inputs_size(s, p) {
        let input_checks := 1
        for {
          let i
        } lt(i, s) {
          i := add(i, 1)
        } {
          input_checks := and(input_checks, lt(calldataload(p), R_MOD))
          p := add(p, 0x20)
        }
        if iszero(input_checks) {
          error_inputs_size()
        }
      }
      /// Checks if the proof is of the correct size
      /// @param actual_proof_size size of the proof (not the expected size)
      function check_proof_size(actual_proof_size) {
        let expected_proof_size := add(0x340, mul(VK_NB_CUSTOM_GATES, 0x60))
        if iszero(eq(actual_proof_size, expected_proof_size)) {
          error_proof_size()
        }
      }
      /// Checks if the multiple openings of the polynomials are < R_MOD.
      /// @param aproof pointer to the beginning of the proof
      /// @dev the 'a' prepending proof is to have a local name
      function check_proof_openings_size(aproof) {
        let openings_check := 1
        // linearised polynomial at zeta
        let p := add(aproof, PROOF_LINEARISED_POLYNOMIAL_AT_ZETA)
        openings_check := and(openings_check, lt(calldataload(p), R_MOD))
        // quotient polynomial at zeta
        p := add(aproof, PROOF_QUOTIENT_POLYNOMIAL_AT_ZETA)
        openings_check := and(openings_check, lt(calldataload(p), R_MOD))
        // PROOF_L_AT_ZETA
        p := add(aproof, PROOF_L_AT_ZETA)
        openings_check := and(openings_check, lt(calldataload(p), R_MOD))
        // PROOF_R_AT_ZETA
        p := add(aproof, PROOF_R_AT_ZETA)
        openings_check := and(openings_check, lt(calldataload(p), R_MOD))
        // PROOF_O_AT_ZETA
        p := add(aproof, PROOF_O_AT_ZETA)
        openings_check := and(openings_check, lt(calldataload(p), R_MOD))
        // PROOF_S1_AT_ZETA
        p := add(aproof, PROOF_S1_AT_ZETA)
        openings_check := and(openings_check, lt(calldataload(p), R_MOD))
        // PROOF_S2_AT_ZETA
        p := add(aproof, PROOF_S2_AT_ZETA)
        openings_check := and(openings_check, lt(calldataload(p), R_MOD))
        // PROOF_GRAND_PRODUCT_AT_ZETA_OMEGA
        p := add(aproof, PROOF_GRAND_PRODUCT_AT_ZETA_OMEGA)
        openings_check := and(openings_check, lt(calldataload(p), R_MOD))
        // PROOF_OPENING_QCP_AT_ZETA
        p := add(aproof, PROOF_OPENING_QCP_AT_ZETA)
        for {
          let i := 0
        } lt(i, VK_NB_CUSTOM_GATES) {
          i := add(i, 1)
        } {
          openings_check := and(openings_check, lt(calldataload(p), R_MOD))
          p := add(p, 0x20)
        }
        if iszero(openings_check) {
          error_proof_openings_size()
        }
      }
      // end checks -------------------------------------------------
      // Beginning challenges -------------------------------------------------
      /// Derive gamma as Sha256(<transcript>)
      /// @param aproof pointer to the proof
      /// @param nb_pi number of public inputs
      /// @param pi pointer to the array of public inputs
      /// @return the challenge gamma, not reduced
      /// @notice The transcript is the concatenation (in this order) of:
      /// * the word "gamma" in ascii, equal to [0x67,0x61,0x6d, 0x6d, 0x61] and encoded as a uint256.
      /// * the commitments to the permutation polynomials S1, S2, S3, where we concatenate the coordinates of those points
      /// * the commitments of Ql, Qr, Qm, Qo, Qk
      /// * the public inputs
      /// * the commitments of the wires related to the custom gates (commitments_wires_commit_api)
      /// * commitments to L, R, O (proof_<l,r,o>_com_<x,y>)
      /// The data described above is written starting at mPtr. "gamma" lies on 5 bytes,
      /// and is encoded as a uint256 number n. In basis b = 256, the number looks like this
      /// [0 0 0 .. 0x67 0x61 0x6d, 0x6d, 0x61]. The first non zero entry is at position 27=0x1b
      /// Gamma reduced (the actual challenge) is stored at add(state, state_gamma)
      function derive_gamma(aproof, nb_pi, pi) -> gamma_not_reduced {
        let state := mload(0x40)
        let mPtr := add(state, STATE_LAST_MEM)
        // gamma
        // gamma in ascii is [0x67,0x61,0x6d, 0x6d, 0x61]
        // (same for alpha, beta, zeta)
        mstore(mPtr, 0x67616d6d61) // "gamma"
        mstore(add(mPtr, 0x20), VK_S1_COM_X)
        mstore(add(mPtr, 0x40), VK_S1_COM_Y)
        mstore(add(mPtr, 0x60), VK_S2_COM_X)
        mstore(add(mPtr, 0x80), VK_S2_COM_Y)
        mstore(add(mPtr, 0xa0), VK_S3_COM_X)
        mstore(add(mPtr, 0xc0), VK_S3_COM_Y)
        mstore(add(mPtr, 0xe0), VK_QL_COM_X)
        mstore(add(mPtr, 0x100), VK_QL_COM_Y)
        mstore(add(mPtr, 0x120), VK_QR_COM_X)
        mstore(add(mPtr, 0x140), VK_QR_COM_Y)
        mstore(add(mPtr, 0x160), VK_QM_COM_X)
        mstore(add(mPtr, 0x180), VK_QM_COM_Y)
        mstore(add(mPtr, 0x1a0), VK_QO_COM_X)
        mstore(add(mPtr, 0x1c0), VK_QO_COM_Y)
        mstore(add(mPtr, 0x1e0), VK_QK_COM_X)
        mstore(add(mPtr, 0x200), VK_QK_COM_Y)
        mstore(add(mPtr, 0x220), VK_QCP_0_X)
        mstore(add(mPtr, 0x240), VK_QCP_0_Y)
        // public inputs
        let _mPtr := add(mPtr, 0x260)
        let size_pi_in_bytes := mul(nb_pi, 0x20)
        calldatacopy(_mPtr, pi, size_pi_in_bytes)
        _mPtr := add(_mPtr, size_pi_in_bytes)
        // commitments to l, r, o
        let size_commitments_lro_in_bytes := 0xc0
        calldatacopy(_mPtr, aproof, size_commitments_lro_in_bytes)
        _mPtr := add(_mPtr, size_commitments_lro_in_bytes)
        // total size is :
        // sizegamma(=0x5) + 11*64(=0x2c0)
        // + nb_public_inputs*0x20
        // + nb_custom gates*0x40
        let size := add(0x2c5, size_pi_in_bytes)
        size := add(size, mul(VK_NB_CUSTOM_GATES, 0x40))
        let l_success := staticcall(gas(), 0x2, add(mPtr, 0x1b), size, mPtr, 0x20) //0x1b -> 000.."gamma"
        if iszero(l_success) {
          error_verify()
        }
        gamma_not_reduced := mload(mPtr)
        mstore(add(state, STATE_GAMMA), mod(gamma_not_reduced, R_MOD))
      }
      /// derive beta as Sha256<transcript>
      /// @param gamma_not_reduced the previous challenge (gamma) not reduced
      /// @return beta_not_reduced the next challenge, beta, not reduced
      /// @notice the transcript consists of the previous challenge only.
      /// The reduced version of beta is stored at add(state, state_beta)
      function derive_beta(gamma_not_reduced) -> beta_not_reduced {
        let state := mload(0x40)
        let mPtr := add(mload(0x40), STATE_LAST_MEM)
        // beta
        mstore(mPtr, 0x62657461) // "beta"
        mstore(add(mPtr, 0x20), gamma_not_reduced)
        let l_success := staticcall(gas(), 0x2, add(mPtr, 0x1c), 0x24, mPtr, 0x20) //0x1b -> 000.."gamma"
        if iszero(l_success) {
          error_verify()
        }
        beta_not_reduced := mload(mPtr)
        mstore(add(state, STATE_BETA), mod(beta_not_reduced, R_MOD))
      }
      /// derive alpha as sha256<transcript>
      /// @param aproof pointer to the proof object
      /// @param beta_not_reduced the previous challenge (beta) not reduced
      /// @return alpha_not_reduced the next challenge, alpha, not reduced
      /// @notice the transcript consists of the previous challenge (beta)
      /// not reduced, the commitments to the wires associated to the QCP_i,
      /// and the commitment to the grand product polynomial
      function derive_alpha(aproof, beta_not_reduced) -> alpha_not_reduced {
        let state := mload(0x40)
        let mPtr := add(mload(0x40), STATE_LAST_MEM)
        let full_size := 0x65 // size("alpha") + 0x20 (previous challenge)
        // alpha
        mstore(mPtr, 0x616C706861) // "alpha"
        let _mPtr := add(mPtr, 0x20)
        mstore(_mPtr, beta_not_reduced)
        _mPtr := add(_mPtr, 0x20)
        // Bsb22Commitments
        let proof_bsb_commitments := add(aproof, PROOF_COMMITMENTS_WIRES_CUSTOM_GATES)
        let size_bsb_commitments := mul(0x40, VK_NB_CUSTOM_GATES)
        calldatacopy(_mPtr, proof_bsb_commitments, size_bsb_commitments)
        _mPtr := add(_mPtr, size_bsb_commitments)
        full_size := add(full_size, size_bsb_commitments)
        // [Z], the commitment to the grand product polynomial
        calldatacopy(_mPtr, add(aproof, PROOF_GRAND_PRODUCT_COMMITMENT_X), 0x40)
        let l_success := staticcall(gas(), 0x2, add(mPtr, 0x1b), full_size, mPtr, 0x20)
        if iszero(l_success) {
          error_verify()
        }
        alpha_not_reduced := mload(mPtr)
        mstore(add(state, STATE_ALPHA), mod(alpha_not_reduced, R_MOD))
      }
      /// derive zeta as sha256<transcript>
      /// @param aproof pointer to the proof object
      /// @param alpha_not_reduced the previous challenge (alpha) not reduced
      /// The transcript consists of the previous challenge and the commitment to
      /// the quotient polynomial h.
      function derive_zeta(aproof, alpha_not_reduced) {
        let state := mload(0x40)
        let mPtr := add(mload(0x40), STATE_LAST_MEM)
        // zeta
        mstore(mPtr, 0x7a657461) // "zeta"
        mstore(add(mPtr, 0x20), alpha_not_reduced)
        calldatacopy(add(mPtr, 0x40), add(aproof, PROOF_H_0_X), 0xc0)
        let l_success := staticcall(gas(), 0x2, add(mPtr, 0x1c), 0xe4, mPtr, 0x20)
        if iszero(l_success) {
          error_verify()
        }
        let zeta_not_reduced := mload(mPtr)
        mstore(add(state, STATE_ZETA), mod(zeta_not_reduced, R_MOD))
      }
      // END challenges -------------------------------------------------
      // BEGINNING compute_pi -------------------------------------------------
      /// sum_pi_wo_api_commit computes the public inputs contributions,
      /// except for the public inputs coming from the custom gate
      /// @param ins pointer to the public inputs
      /// @param n number of public inputs
      /// @param mPtr free memory
      /// @return pi_wo_commit public inputs contribution (except the public inputs coming from the custom gate)
      function sum_pi_wo_api_commit(ins, n, mPtr) -> pi_wo_commit {
        let state := mload(0x40)
        let z := mload(add(state, STATE_ZETA))
        let zpnmo := mload(add(state, STATE_ZETA_POWER_N_MINUS_ONE))
        let li := mPtr
        batch_compute_lagranges_at_z(z, zpnmo, n, li)
        let tmp := 0
        for {
          let i := 0
        } lt(i, n) {
          i := add(i, 1)
        } {
          tmp := mulmod(mload(li), calldataload(ins), R_MOD)
          pi_wo_commit := addmod(pi_wo_commit, tmp, R_MOD)
          li := add(li, 0x20)
          ins := add(ins, 0x20)
        }
      }
      /// batch_compute_lagranges_at_z computes [L_0(z), .., L_{n-1}(z)]
      /// @param z point at which the Lagranges are evaluated
      /// @param zpnmo ζⁿ-1
      /// @param n number of public inputs (number of Lagranges to compute)
      /// @param mPtr pointer to which the results are stored
      function batch_compute_lagranges_at_z(z, zpnmo, n, mPtr) {
        let zn := mulmod(zpnmo, VK_INV_DOMAIN_SIZE, R_MOD) // 1/n * (ζⁿ - 1)
        let _w := 1
        let _mPtr := mPtr
        for {
          let i := 0
        } lt(i, n) {
          i := add(i, 1)
        } {
          mstore(_mPtr, addmod(z, sub(R_MOD, _w), R_MOD))
          _w := mulmod(_w, VK_OMEGA, R_MOD)
          _mPtr := add(_mPtr, 0x20)
        }
        batch_invert(mPtr, n, _mPtr)
        _mPtr := mPtr
        _w := 1
        for {
          let i := 0
        } lt(i, n) {
          i := add(i, 1)
        } {
          mstore(_mPtr, mulmod(mulmod(mload(_mPtr), zn, R_MOD), _w, R_MOD))
          _mPtr := add(_mPtr, 0x20)
          _w := mulmod(_w, VK_OMEGA, R_MOD)
        }
      }
      /// @notice Montgomery trick for batch inversion mod R_MOD
      /// @param ins pointer to the data to batch invert
      /// @param number of elements to batch invert
      /// @param mPtr free memory
      function batch_invert(ins, nb_ins, mPtr) {
        mstore(mPtr, 1)
        let offset := 0
        for {
          let i := 0
        } lt(i, nb_ins) {
          i := add(i, 1)
        } {
          let prev := mload(add(mPtr, offset))
          let cur := mload(add(ins, offset))
          cur := mulmod(prev, cur, R_MOD)
          offset := add(offset, 0x20)
          mstore(add(mPtr, offset), cur)
        }
        ins := add(ins, sub(offset, 0x20))
        mPtr := add(mPtr, offset)
        let inv := pow(mload(mPtr), sub(R_MOD, 2), add(mPtr, 0x20))
        for {
          let i := 0
        } lt(i, nb_ins) {
          i := add(i, 1)
        } {
          mPtr := sub(mPtr, 0x20)
          let tmp := mload(ins)
          let cur := mulmod(inv, mload(mPtr), R_MOD)
          mstore(ins, cur)
          inv := mulmod(inv, tmp, R_MOD)
          ins := sub(ins, 0x20)
        }
      }
      /// Public inputs (the ones coming from the custom gate) contribution
      /// @param aproof pointer to the proof
      /// @param nb_public_inputs number of public inputs
      /// @param mPtr pointer to free memory
      /// @return pi_commit custom gate public inputs contribution
      function sum_pi_commit(aproof, nb_public_inputs, mPtr) -> pi_commit {
        let state := mload(0x40)
        let z := mload(add(state, STATE_ZETA))
        let zpnmo := mload(add(state, STATE_ZETA_POWER_N_MINUS_ONE))
        let p := add(aproof, PROOF_COMMITMENTS_WIRES_CUSTOM_GATES)
        let h_fr, ith_lagrange
        h_fr := hash_fr(calldataload(p), calldataload(add(p, 0x20)), mPtr)
        ith_lagrange := compute_ith_lagrange_at_z(z, zpnmo, add(nb_public_inputs, VK_INDEX_COMMIT_API0), mPtr)
        pi_commit := addmod(pi_commit, mulmod(h_fr, ith_lagrange, R_MOD), R_MOD)
        p := add(p, 0x40)
      }
      /// Computes L_i(zeta) =  ωⁱ/n * (ζⁿ-1)/(ζ-ωⁱ) where:
      /// @param z zeta
      /// @param zpmno ζⁿ-1
      /// @param i i-th lagrange
      /// @param mPtr free memory
      /// @return res = ωⁱ/n * (ζⁿ-1)/(ζ-ωⁱ)
      function compute_ith_lagrange_at_z(z, zpnmo, i, mPtr) -> res {
        let w := pow(VK_OMEGA, i, mPtr) // w**i
        i := addmod(z, sub(R_MOD, w), R_MOD) // z-w**i
        w := mulmod(w, VK_INV_DOMAIN_SIZE, R_MOD) // w**i/n
        i := pow(i, sub(R_MOD, 2), mPtr) // (z-w**i)**-1
        w := mulmod(w, i, R_MOD) // w**i/n*(z-w)**-1
        res := mulmod(w, zpnmo, R_MOD)
      }
      /// @dev https://tools.ietf.org/html/draft-irtf-cfrg-hash-to-curve-06#section-5.2
      /// @param x x coordinate of a point on Bn254(𝔽_p)
      /// @param y y coordinate of a point on Bn254(𝔽_p)
      /// @param mPtr free memory
      /// @return res an element mod R_MOD
      function hash_fr(x, y, mPtr) -> res {
        // [0x00, .. , 0x00 || x, y, || 0, 48, 0, dst, HASH_FR_SIZE_DOMAIN]
        // <-  64 bytes  ->  <-64b -> <-       1 bytes each     ->
        // [0x00, .., 0x00] 64 bytes of zero
        mstore(mPtr, HASH_FR_ZERO_UINT256)
        mstore(add(mPtr, 0x20), HASH_FR_ZERO_UINT256)
        // msg =  x || y , both on 32 bytes
        mstore(add(mPtr, 0x40), x)
        mstore(add(mPtr, 0x60), y)
        // 0 || 48 || 0 all on 1 byte
        mstore8(add(mPtr, 0x80), 0)
        mstore8(add(mPtr, 0x81), HASH_FR_LEN_IN_BYTES)
        mstore8(add(mPtr, 0x82), 0)
        // "BSB22-Plonk" = [42, 53, 42, 32, 32, 2d, 50, 6c, 6f, 6e, 6b,]
        mstore8(add(mPtr, 0x83), 0x42)
        mstore8(add(mPtr, 0x84), 0x53)
        mstore8(add(mPtr, 0x85), 0x42)
        mstore8(add(mPtr, 0x86), 0x32)
        mstore8(add(mPtr, 0x87), 0x32)
        mstore8(add(mPtr, 0x88), 0x2d)
        mstore8(add(mPtr, 0x89), 0x50)
        mstore8(add(mPtr, 0x8a), 0x6c)
        mstore8(add(mPtr, 0x8b), 0x6f)
        mstore8(add(mPtr, 0x8c), 0x6e)
        mstore8(add(mPtr, 0x8d), 0x6b)
        // size domain
        mstore8(add(mPtr, 0x8e), HASH_FR_SIZE_DOMAIN)
        let l_success := staticcall(gas(), 0x2, mPtr, 0x8f, mPtr, 0x20)
        if iszero(l_success) {
          error_verify()
        }
        let b0 := mload(mPtr)
        // [b0         || one || dst || HASH_FR_SIZE_DOMAIN]
        // <-64bytes ->  <-    1 byte each      ->
        mstore8(add(mPtr, 0x20), HASH_FR_ONE) // 1
        mstore8(add(mPtr, 0x21), 0x42) // dst
        mstore8(add(mPtr, 0x22), 0x53)
        mstore8(add(mPtr, 0x23), 0x42)
        mstore8(add(mPtr, 0x24), 0x32)
        mstore8(add(mPtr, 0x25), 0x32)
        mstore8(add(mPtr, 0x26), 0x2d)
        mstore8(add(mPtr, 0x27), 0x50)
        mstore8(add(mPtr, 0x28), 0x6c)
        mstore8(add(mPtr, 0x29), 0x6f)
        mstore8(add(mPtr, 0x2a), 0x6e)
        mstore8(add(mPtr, 0x2b), 0x6b)
        mstore8(add(mPtr, 0x2c), HASH_FR_SIZE_DOMAIN) // size domain
        l_success := staticcall(gas(), 0x2, mPtr, 0x2d, mPtr, 0x20)
        if iszero(l_success) {
          error_verify()
        }
        // b1 is located at mPtr. We store b2 at add(mPtr, 0x20)
        // [b0^b1      || two || dst || HASH_FR_SIZE_DOMAIN]
        // <-64bytes ->  <-    1 byte each      ->
        mstore(add(mPtr, 0x20), xor(mload(mPtr), b0))
        mstore8(add(mPtr, 0x40), HASH_FR_TWO)
        mstore8(add(mPtr, 0x41), 0x42) // dst
        mstore8(add(mPtr, 0x42), 0x53)
        mstore8(add(mPtr, 0x43), 0x42)
        mstore8(add(mPtr, 0x44), 0x32)
        mstore8(add(mPtr, 0x45), 0x32)
        mstore8(add(mPtr, 0x46), 0x2d)
        mstore8(add(mPtr, 0x47), 0x50)
        mstore8(add(mPtr, 0x48), 0x6c)
        mstore8(add(mPtr, 0x49), 0x6f)
        mstore8(add(mPtr, 0x4a), 0x6e)
        mstore8(add(mPtr, 0x4b), 0x6b)
        mstore8(add(mPtr, 0x4c), HASH_FR_SIZE_DOMAIN) // size domain
        let offset := add(mPtr, 0x20)
        l_success := staticcall(gas(), 0x2, offset, 0x2d, offset, 0x20)
        if iszero(l_success) {
          error_verify()
        }
        // at this point we have mPtr = [ b1 || b2] where b1 is on 32byes and b2 in 16bytes.
        // we interpret it as a big integer mod r in big endian (similar to regular decimal notation)
        // the result is then 2**(8*16)*mPtr[32:] + mPtr[32:48]
        res := mulmod(mload(mPtr), HASH_FR_BB, R_MOD) // <- res = 2**128 * mPtr[:32]
        let b1 := shr(128, mload(add(mPtr, 0x20))) // b1 <- [0, 0, .., 0 ||  b2[:16] ]
        res := addmod(res, b1, R_MOD)
      }
      // END compute_pi -------------------------------------------------
      /// @notice compute α² * 1/n * (ζ{n}-1)/(ζ - 1) where
      /// *  α = challenge derived in derive_gamma_beta_alpha_zeta
      /// * n = vk_domain_size
      /// * ω = vk_omega (generator of the multiplicative cyclic group of order n in (ℤ/rℤ)*)
      /// * ζ = zeta (challenge derived with Fiat Shamir)
      function compute_alpha_square_lagrange_0() {
        let state := mload(0x40)
        let mPtr := add(mload(0x40), STATE_LAST_MEM)
        let res := mload(add(state, STATE_ZETA_POWER_N_MINUS_ONE))
        let den := addmod(mload(add(state, STATE_ZETA)), sub(R_MOD, 1), R_MOD)
        den := pow(den, sub(R_MOD, 2), mPtr)
        den := mulmod(den, VK_INV_DOMAIN_SIZE, R_MOD)
        res := mulmod(den, res, R_MOD)
        let l_alpha := mload(add(state, STATE_ALPHA))
        res := mulmod(res, l_alpha, R_MOD)
        res := mulmod(res, l_alpha, R_MOD)
        mstore(add(state, STATE_ALPHA_SQUARE_LAGRANGE_0), res)
      }
      /// @notice follows alg. p.13 of https://eprint.iacr.org/2019/953.pdf
      /// with t₁ = t₂ = 1, and the proofs are ([digest] + [quotient] +purported evaluation):
      /// * [state_folded_state_digests], [proof_batch_opening_at_zeta_x], state_folded_evals
      /// * [proof_grand_product_commitment], [proof_opening_at_zeta_omega_x], [proof_grand_product_at_zeta_omega]
      /// @param aproof pointer to the proof
      function batch_verify_multi_points(aproof) {
        let state := mload(0x40)
        let mPtr := add(state, STATE_LAST_MEM)
        // derive a random number. As there is no random generator, we
        // do an FS like challenge derivation, depending on both digests and
        // ζ to ensure that the prover cannot control the random numger.
        // Note: adding the other point ζω is not needed, as ω is known beforehand.
        mstore(mPtr, mload(add(state, STATE_FOLDED_DIGESTS_X)))
        mstore(add(mPtr, 0x20), mload(add(state, STATE_FOLDED_DIGESTS_Y)))
        mstore(add(mPtr, 0x40), calldataload(add(aproof, PROOF_BATCH_OPENING_AT_ZETA_X)))
        mstore(add(mPtr, 0x60), calldataload(add(aproof, PROOF_BATCH_OPENING_AT_ZETA_Y)))
        mstore(add(mPtr, 0x80), calldataload(add(aproof, PROOF_GRAND_PRODUCT_COMMITMENT_X)))
        mstore(add(mPtr, 0xa0), calldataload(add(aproof, PROOF_GRAND_PRODUCT_COMMITMENT_Y)))
        mstore(add(mPtr, 0xc0), calldataload(add(aproof, PROOF_OPENING_AT_ZETA_OMEGA_X)))
        mstore(add(mPtr, 0xe0), calldataload(add(aproof, PROOF_OPENING_AT_ZETA_OMEGA_Y)))
        mstore(add(mPtr, 0x100), mload(add(state, STATE_ZETA)))
        mstore(add(mPtr, 0x120), mload(add(state, STATE_GAMMA_KZG)))
        let random := staticcall(gas(), 0x2, mPtr, 0x140, mPtr, 0x20)
        if iszero(random) {
          error_random_generation()
        }
        random := mod(mload(mPtr), R_MOD) // use the same variable as we are one variable away from getting stack-too-deep error...
        let folded_quotients := mPtr
        mPtr := add(folded_quotients, 0x40)
        mstore(folded_quotients, calldataload(add(aproof, PROOF_BATCH_OPENING_AT_ZETA_X)))
        mstore(add(folded_quotients, 0x20), calldataload(add(aproof, PROOF_BATCH_OPENING_AT_ZETA_Y)))
        point_acc_mul_calldata(folded_quotients, add(aproof, PROOF_OPENING_AT_ZETA_OMEGA_X), random, mPtr)
        let folded_digests := add(state, STATE_FOLDED_DIGESTS_X)
        point_acc_mul_calldata(folded_digests, add(aproof, PROOF_GRAND_PRODUCT_COMMITMENT_X), random, mPtr)
        let folded_evals := add(state, STATE_FOLDED_CLAIMED_VALUES)
        fr_acc_mul_calldata(folded_evals, add(aproof, PROOF_GRAND_PRODUCT_AT_ZETA_OMEGA), random)
        let folded_evals_commit := mPtr
        mPtr := add(folded_evals_commit, 0x40)
        mstore(folded_evals_commit, G1_SRS_X)
        mstore(add(folded_evals_commit, 0x20), G1_SRS_Y)
        mstore(add(folded_evals_commit, 0x40), mload(folded_evals))
        let check_staticcall := staticcall(gas(), 7, folded_evals_commit, 0x60, folded_evals_commit, 0x40)
        if iszero(check_staticcall) {
          error_verify()
        }
        let folded_evals_commit_y := add(folded_evals_commit, 0x20)
        mstore(folded_evals_commit_y, sub(P_MOD, mload(folded_evals_commit_y)))
        point_add(folded_digests, folded_digests, folded_evals_commit, mPtr)
        let folded_points_quotients := mPtr
        mPtr := add(mPtr, 0x40)
        point_mul_calldata(
          folded_points_quotients,
          add(aproof, PROOF_BATCH_OPENING_AT_ZETA_X),
          mload(add(state, STATE_ZETA)),
          mPtr
        )
        let zeta_omega := mulmod(mload(add(state, STATE_ZETA)), VK_OMEGA, R_MOD)
        random := mulmod(random, zeta_omega, R_MOD)
        point_acc_mul_calldata(folded_points_quotients, add(aproof, PROOF_OPENING_AT_ZETA_OMEGA_X), random, mPtr)
        point_add(folded_digests, folded_digests, folded_points_quotients, mPtr)
        let folded_quotients_y := add(folded_quotients, 0x20)
        mstore(folded_quotients_y, sub(P_MOD, mload(folded_quotients_y)))
        mstore(mPtr, mload(folded_digests))
        mstore(add(mPtr, 0x20), mload(add(folded_digests, 0x20)))
        mstore(add(mPtr, 0x40), G2_SRS_0_X_0) // the 4 lines are the canonical G2 point on BN254
        mstore(add(mPtr, 0x60), G2_SRS_0_X_1)
        mstore(add(mPtr, 0x80), G2_SRS_0_Y_0)
        mstore(add(mPtr, 0xa0), G2_SRS_0_Y_1)
        mstore(add(mPtr, 0xc0), mload(folded_quotients))
        mstore(add(mPtr, 0xe0), mload(add(folded_quotients, 0x20)))
        mstore(add(mPtr, 0x100), G2_SRS_1_X_0)
        mstore(add(mPtr, 0x120), G2_SRS_1_X_1)
        mstore(add(mPtr, 0x140), G2_SRS_1_Y_0)
        mstore(add(mPtr, 0x160), G2_SRS_1_Y_1)
        check_pairing_kzg(mPtr)
      }
      /// @notice check_pairing_kzg checks the result of the final pairing product of the batched
      /// kzg verification. The purpose of this function is to avoid exhausting the stack
      /// in the function batch_verify_multi_points.
      /// @param mPtr pointer storing the tuple of pairs
      function check_pairing_kzg(mPtr) {
        let state := mload(0x40)
        // TODO test the staticcall using the method from audit_4-5
        let l_success := staticcall(gas(), 8, mPtr, 0x180, 0x00, 0x20)
        let res_pairing := mload(0x00)
        let s_success := mload(add(state, STATE_SUCCESS))
        res_pairing := and(and(res_pairing, l_success), s_success)
        mstore(add(state, STATE_SUCCESS), res_pairing)
      }
      /// @notice Fold the opening proofs at ζ:
      /// * at state+state_folded_digest we store: [H] + γ[Linearised_polynomial]+γ²[L] + γ³[R] + γ⁴[O] + γ⁵[S₁] +γ⁶[S₂] + ∑ᵢγ⁶⁺ⁱ[Pi_{i}]
      /// * at state+state_folded_claimed_values we store: H(ζ) + γLinearised_polynomial(ζ)+γ²L(ζ) + γ³R(ζ)+ γ⁴O(ζ) + γ⁵S₁(ζ) +γ⁶S₂(ζ) + ∑ᵢγ⁶⁺ⁱPi_{i}(ζ)
      /// @param aproof pointer to the proof
      /// acc_gamma stores the γⁱ
      function fold_state(aproof) {
        let state := mload(0x40)
        let mPtr := add(mload(0x40), STATE_LAST_MEM)
        let mPtr20 := add(mPtr, 0x20)
        let mPtr40 := add(mPtr, 0x40)
        let l_gamma_kzg := mload(add(state, STATE_GAMMA_KZG))
        let acc_gamma := l_gamma_kzg
        let state_folded_digests := add(state, STATE_FOLDED_DIGESTS_X)
        mstore(add(state, STATE_FOLDED_DIGESTS_X), mload(add(state, STATE_FOLDED_H_X)))
        mstore(add(state, STATE_FOLDED_DIGESTS_Y), mload(add(state, STATE_FOLDED_H_Y)))
        mstore(add(state, STATE_FOLDED_CLAIMED_VALUES), calldataload(add(aproof, PROOF_QUOTIENT_POLYNOMIAL_AT_ZETA)))
        point_acc_mul(state_folded_digests, add(state, STATE_LINEARISED_POLYNOMIAL_X), acc_gamma, mPtr)
        fr_acc_mul_calldata(
          add(state, STATE_FOLDED_CLAIMED_VALUES),
          add(aproof, PROOF_LINEARISED_POLYNOMIAL_AT_ZETA),
          acc_gamma
        )
        acc_gamma := mulmod(acc_gamma, l_gamma_kzg, R_MOD)
        point_acc_mul_calldata(add(state, STATE_FOLDED_DIGESTS_X), add(aproof, PROOF_L_COM_X), acc_gamma, mPtr)
        fr_acc_mul_calldata(add(state, STATE_FOLDED_CLAIMED_VALUES), add(aproof, PROOF_L_AT_ZETA), acc_gamma)
        acc_gamma := mulmod(acc_gamma, l_gamma_kzg, R_MOD)
        point_acc_mul_calldata(state_folded_digests, add(aproof, PROOF_R_COM_X), acc_gamma, mPtr)
        fr_acc_mul_calldata(add(state, STATE_FOLDED_CLAIMED_VALUES), add(aproof, PROOF_R_AT_ZETA), acc_gamma)
        acc_gamma := mulmod(acc_gamma, l_gamma_kzg, R_MOD)
        point_acc_mul_calldata(state_folded_digests, add(aproof, PROOF_O_COM_X), acc_gamma, mPtr)
        fr_acc_mul_calldata(add(state, STATE_FOLDED_CLAIMED_VALUES), add(aproof, PROOF_O_AT_ZETA), acc_gamma)
        acc_gamma := mulmod(acc_gamma, l_gamma_kzg, R_MOD)
        mstore(mPtr, VK_S1_COM_X)
        mstore(mPtr20, VK_S1_COM_Y)
        point_acc_mul(state_folded_digests, mPtr, acc_gamma, mPtr40)
        fr_acc_mul_calldata(add(state, STATE_FOLDED_CLAIMED_VALUES), add(aproof, PROOF_S1_AT_ZETA), acc_gamma)
        acc_gamma := mulmod(acc_gamma, l_gamma_kzg, R_MOD)
        mstore(mPtr, VK_S2_COM_X)
        mstore(mPtr20, VK_S2_COM_Y)
        point_acc_mul(state_folded_digests, mPtr, acc_gamma, mPtr40)
        fr_acc_mul_calldata(add(state, STATE_FOLDED_CLAIMED_VALUES), add(aproof, PROOF_S2_AT_ZETA), acc_gamma)
        let poscaz := add(aproof, PROOF_OPENING_QCP_AT_ZETA)
        acc_gamma := mulmod(acc_gamma, l_gamma_kzg, R_MOD)
        mstore(mPtr, VK_QCP_0_X)
        mstore(mPtr20, VK_QCP_0_Y)
        point_acc_mul(state_folded_digests, mPtr, acc_gamma, mPtr40)
        fr_acc_mul_calldata(add(state, STATE_FOLDED_CLAIMED_VALUES), poscaz, acc_gamma)
        poscaz := add(poscaz, 0x20)
      }
      /// @notice generate the challenge (using Fiat Shamir) to fold the opening proofs
      /// at ζ.
      /// The process for deriving γ is the same as in derive_gamma but this time the inputs are
      /// in this order (the [] means it's a commitment):
      /// * ζ
      /// * [H] ( = H₁ + ζᵐ⁺²*H₂ + ζ²⁽ᵐ⁺²⁾*H₃ )
      /// * [Linearised polynomial]
      /// * [L], [R], [O]
      /// * [S₁] [S₂]
      /// * [Pi_{i}] (wires associated to custom gates)
      /// Then there are the purported evaluations of the previous committed polynomials:
      /// * H(ζ)
      /// * Linearised_polynomial(ζ)
      /// * L(ζ), R(ζ), O(ζ), S₁(ζ), S₂(ζ)
      /// * Pi_{i}(ζ)
      /// * Z(ζω)
      /// @param aproof pointer to the proof
      function compute_gamma_kzg(aproof) {
        let state := mload(0x40)
        let mPtr := add(mload(0x40), STATE_LAST_MEM)
        mstore(mPtr, 0x67616d6d61) // "gamma"
        mstore(add(mPtr, 0x20), mload(add(state, STATE_ZETA)))
        mstore(add(mPtr, 0x40), mload(add(state, STATE_FOLDED_H_X)))
        mstore(add(mPtr, 0x60), mload(add(state, STATE_FOLDED_H_Y)))
        mstore(add(mPtr, 0x80), mload(add(state, STATE_LINEARISED_POLYNOMIAL_X)))
        mstore(add(mPtr, 0xa0), mload(add(state, STATE_LINEARISED_POLYNOMIAL_Y)))
        calldatacopy(add(mPtr, 0xc0), add(aproof, PROOF_L_COM_X), 0xc0)
        mstore(add(mPtr, 0x180), VK_S1_COM_X)
        mstore(add(mPtr, 0x1a0), VK_S1_COM_Y)
        mstore(add(mPtr, 0x1c0), VK_S2_COM_X)
        mstore(add(mPtr, 0x1e0), VK_S2_COM_Y)
        let offset := 0x200
        mstore(add(mPtr, offset), VK_QCP_0_X)
        mstore(add(mPtr, add(offset, 0x20)), VK_QCP_0_Y)
        offset := add(offset, 0x40)
        mstore(add(mPtr, offset), calldataload(add(aproof, PROOF_QUOTIENT_POLYNOMIAL_AT_ZETA)))
        mstore(add(mPtr, add(offset, 0x20)), calldataload(add(aproof, PROOF_LINEARISED_POLYNOMIAL_AT_ZETA)))
        mstore(add(mPtr, add(offset, 0x40)), calldataload(add(aproof, PROOF_L_AT_ZETA)))
        mstore(add(mPtr, add(offset, 0x60)), calldataload(add(aproof, PROOF_R_AT_ZETA)))
        mstore(add(mPtr, add(offset, 0x80)), calldataload(add(aproof, PROOF_O_AT_ZETA)))
        mstore(add(mPtr, add(offset, 0xa0)), calldataload(add(aproof, PROOF_S1_AT_ZETA)))
        mstore(add(mPtr, add(offset, 0xc0)), calldataload(add(aproof, PROOF_S2_AT_ZETA)))
        let _mPtr := add(mPtr, add(offset, 0xe0))
        let _poscaz := add(aproof, PROOF_OPENING_QCP_AT_ZETA)
        for {
          let i := 0
        } lt(i, VK_NB_CUSTOM_GATES) {
          i := add(i, 1)
        } {
          mstore(_mPtr, calldataload(_poscaz))
          _poscaz := add(_poscaz, 0x20)
          _mPtr := add(_mPtr, 0x20)
        }
        mstore(_mPtr, calldataload(add(aproof, PROOF_GRAND_PRODUCT_AT_ZETA_OMEGA)))
        let start_input := 0x1b // 00.."gamma"
        let size_input := add(0x17, mul(VK_NB_CUSTOM_GATES, 3)) // number of 32bytes elmts = 0x17 (zeta+2*7+7 for the digests+openings) + 2*VK_NB_CUSTOM_GATES (for the commitments of the selectors) + VK_NB_CUSTOM_GATES (for the openings of the selectors)
        size_input := add(0x5, mul(size_input, 0x20)) // size in bytes: 15*32 bytes + 5 bytes for gamma
        let check_staticcall := staticcall(
          gas(),
          0x2,
          add(mPtr, start_input),
          size_input,
          add(state, STATE_GAMMA_KZG),
          0x20
        )
        if iszero(check_staticcall) {
          error_verify()
        }
        mstore(add(state, STATE_GAMMA_KZG), mod(mload(add(state, STATE_GAMMA_KZG)), R_MOD))
      }
      function compute_commitment_linearised_polynomial_ec(aproof, s1, s2) {
        let state := mload(0x40)
        let mPtr := add(mload(0x40), STATE_LAST_MEM)
        mstore(mPtr, VK_QL_COM_X)
        mstore(add(mPtr, 0x20), VK_QL_COM_Y)
        point_mul(
          add(state, STATE_LINEARISED_POLYNOMIAL_X),
          mPtr,
          calldataload(add(aproof, PROOF_L_AT_ZETA)),
          add(mPtr, 0x40)
        )
        mstore(mPtr, VK_QR_COM_X)
        mstore(add(mPtr, 0x20), VK_QR_COM_Y)
        point_acc_mul(
          add(state, STATE_LINEARISED_POLYNOMIAL_X),
          mPtr,
          calldataload(add(aproof, PROOF_R_AT_ZETA)),
          add(mPtr, 0x40)
        )
        let rl := mulmod(calldataload(add(aproof, PROOF_L_AT_ZETA)), calldataload(add(aproof, PROOF_R_AT_ZETA)), R_MOD)
        mstore(mPtr, VK_QM_COM_X)
        mstore(add(mPtr, 0x20), VK_QM_COM_Y)
        point_acc_mul(add(state, STATE_LINEARISED_POLYNOMIAL_X), mPtr, rl, add(mPtr, 0x40))
        mstore(mPtr, VK_QO_COM_X)
        mstore(add(mPtr, 0x20), VK_QO_COM_Y)
        point_acc_mul(
          add(state, STATE_LINEARISED_POLYNOMIAL_X),
          mPtr,
          calldataload(add(aproof, PROOF_O_AT_ZETA)),
          add(mPtr, 0x40)
        )
        mstore(mPtr, VK_QK_COM_X)
        mstore(add(mPtr, 0x20), VK_QK_COM_Y)
        point_add(
          add(state, STATE_LINEARISED_POLYNOMIAL_X),
          add(state, STATE_LINEARISED_POLYNOMIAL_X),
          mPtr,
          add(mPtr, 0x40)
        )
        let commits_api_at_zeta := add(aproof, PROOF_OPENING_QCP_AT_ZETA)
        let commits_api := add(aproof, PROOF_COMMITMENTS_WIRES_CUSTOM_GATES)
        for {
          let i := 0
        } lt(i, VK_NB_CUSTOM_GATES) {
          i := add(i, 1)
        } {
          mstore(mPtr, calldataload(commits_api))
          mstore(add(mPtr, 0x20), calldataload(add(commits_api, 0x20)))
          point_acc_mul(
            add(state, STATE_LINEARISED_POLYNOMIAL_X),
            mPtr,
            calldataload(commits_api_at_zeta),
            add(mPtr, 0x40)
          )
          commits_api_at_zeta := add(commits_api_at_zeta, 0x20)
          commits_api := add(commits_api, 0x40)
        }
        mstore(mPtr, VK_S3_COM_X)
        mstore(add(mPtr, 0x20), VK_S3_COM_Y)
        point_acc_mul(add(state, STATE_LINEARISED_POLYNOMIAL_X), mPtr, s1, add(mPtr, 0x40))
        mstore(mPtr, calldataload(add(aproof, PROOF_GRAND_PRODUCT_COMMITMENT_X)))
        mstore(add(mPtr, 0x20), calldataload(add(aproof, PROOF_GRAND_PRODUCT_COMMITMENT_Y)))
        point_acc_mul(add(state, STATE_LINEARISED_POLYNOMIAL_X), mPtr, s2, add(mPtr, 0x40))
      }
      /// @notice Compute the commitment to the linearized polynomial equal to
      ///\tL(ζ)[Qₗ]+r(ζ)[Qᵣ]+R(ζ)L(ζ)[Qₘ]+O(ζ)[Qₒ]+[Qₖ]+Σᵢqc'ᵢ(ζ)[BsbCommitmentᵢ] +
      ///\tα*( Z(μζ)(L(ζ)+β*S₁(ζ)+γ)*(R(ζ)+β*S₂(ζ)+γ)[S₃]-[Z](L(ζ)+β*id_{1}(ζ)+γ)*(R(ζ)+β*id_{2(ζ)+γ)*(O(ζ)+β*id_{3}(ζ)+γ) ) +
      ///\tα²*L₁(ζ)[Z]
      /// where
      /// * id_1 = id, id_2 = vk_coset_shift*id, id_3 = vk_coset_shift^{2}*id
      /// * the [] means that it's a commitment (i.e. a point on Bn254(F_p))
      /// @param aproof pointer to the proof
      function compute_commitment_linearised_polynomial(aproof) {
        let state := mload(0x40)
        let l_beta := mload(add(state, STATE_BETA))
        let l_gamma := mload(add(state, STATE_GAMMA))
        let l_zeta := mload(add(state, STATE_ZETA))
        let l_alpha := mload(add(state, STATE_ALPHA))
        let u := mulmod(calldataload(add(aproof, PROOF_GRAND_PRODUCT_AT_ZETA_OMEGA)), l_beta, R_MOD)
        let v := mulmod(l_beta, calldataload(add(aproof, PROOF_S1_AT_ZETA)), R_MOD)
        v := addmod(v, calldataload(add(aproof, PROOF_L_AT_ZETA)), R_MOD)
        v := addmod(v, l_gamma, R_MOD)
        let w := mulmod(l_beta, calldataload(add(aproof, PROOF_S2_AT_ZETA)), R_MOD)
        w := addmod(w, calldataload(add(aproof, PROOF_R_AT_ZETA)), R_MOD)
        w := addmod(w, l_gamma, R_MOD)
        let s1 := mulmod(u, v, R_MOD)
        s1 := mulmod(s1, w, R_MOD)
        s1 := mulmod(s1, l_alpha, R_MOD)
        let coset_square := mulmod(VK_COSET_SHIFT, VK_COSET_SHIFT, R_MOD)
        let betazeta := mulmod(l_beta, l_zeta, R_MOD)
        u := addmod(betazeta, calldataload(add(aproof, PROOF_L_AT_ZETA)), R_MOD)
        u := addmod(u, l_gamma, R_MOD)
        v := mulmod(betazeta, VK_COSET_SHIFT, R_MOD)
        v := addmod(v, calldataload(add(aproof, PROOF_R_AT_ZETA)), R_MOD)
        v := addmod(v, l_gamma, R_MOD)
        w := mulmod(betazeta, coset_square, R_MOD)
        w := addmod(w, calldataload(add(aproof, PROOF_O_AT_ZETA)), R_MOD)
        w := addmod(w, l_gamma, R_MOD)
        let s2 := mulmod(u, v, R_MOD)
        s2 := mulmod(s2, w, R_MOD)
        s2 := sub(R_MOD, s2)
        s2 := mulmod(s2, l_alpha, R_MOD)
        s2 := addmod(s2, mload(add(state, STATE_ALPHA_SQUARE_LAGRANGE_0)), R_MOD)
        // at this stage:
        // * s₁ = α*Z(μζ)(l(ζ)+β*s₁(ζ)+γ)*(r(ζ)+β*s₂(ζ)+γ)*β
        // * s₂ = -α*(l(ζ)+β*ζ+γ)*(r(ζ)+β*u*ζ+γ)*(o(ζ)+β*u²*ζ+γ) + α²*L₁(ζ)
        compute_commitment_linearised_polynomial_ec(aproof, s1, s2)
      }
      /// @notice compute H₁ + ζᵐ⁺²*H₂ + ζ²⁽ᵐ⁺²⁾*H₃ and store the result at
      /// state + state_folded_h
      /// @param aproof pointer to the proof
      function fold_h(aproof) {
        let state := mload(0x40)
        let n_plus_two := add(VK_DOMAIN_SIZE, 2)
        let mPtr := add(mload(0x40), STATE_LAST_MEM)
        let zeta_power_n_plus_two := pow(mload(add(state, STATE_ZETA)), n_plus_two, mPtr)
        point_mul_calldata(add(state, STATE_FOLDED_H_X), add(aproof, PROOF_H_2_X), zeta_power_n_plus_two, mPtr)
        point_add_calldata(add(state, STATE_FOLDED_H_X), add(state, STATE_FOLDED_H_X), add(aproof, PROOF_H_1_X), mPtr)
        point_mul(add(state, STATE_FOLDED_H_X), add(state, STATE_FOLDED_H_X), zeta_power_n_plus_two, mPtr)
        point_add_calldata(add(state, STATE_FOLDED_H_X), add(state, STATE_FOLDED_H_X), add(aproof, PROOF_H_0_X), mPtr)
      }
      /// @notice check that
      ///\tL(ζ)Qₗ(ζ)+r(ζ)Qᵣ(ζ)+R(ζ)L(ζ)Qₘ(ζ)+O(ζ)Qₒ(ζ)+Qₖ(ζ)+Σᵢqc'ᵢ(ζ)BsbCommitmentᵢ(ζ) +
      ///  α*( Z(μζ)(l(ζ)+β*s₁(ζ)+γ)*(r(ζ)+β*s₂(ζ)+γ)*β*s₃(X)-Z(X)(l(ζ)+β*id_1(ζ)+γ)*(r(ζ)+β*id_2(ζ)+γ)*(o(ζ)+β*id_3(ζ)+γ) ) )
      /// + α²*L₁(ζ) =
      /// (ζⁿ-1)H(ζ)
      /// @param aproof pointer to the proof
      function verify_quotient_poly_eval_at_zeta(aproof) {
        let state := mload(0x40)
        // (l(ζ)+β*s1(ζ)+γ)
        let s1 := add(mload(0x40), STATE_LAST_MEM)
        mstore(s1, mulmod(calldataload(add(aproof, PROOF_S1_AT_ZETA)), mload(add(state, STATE_BETA)), R_MOD))
        mstore(s1, addmod(mload(s1), mload(add(state, STATE_GAMMA)), R_MOD))
        mstore(s1, addmod(mload(s1), calldataload(add(aproof, PROOF_L_AT_ZETA)), R_MOD))
        // (r(ζ)+β*s2(ζ)+γ)
        let s2 := add(s1, 0x20)
        mstore(s2, mulmod(calldataload(add(aproof, PROOF_S2_AT_ZETA)), mload(add(state, STATE_BETA)), R_MOD))
        mstore(s2, addmod(mload(s2), mload(add(state, STATE_GAMMA)), R_MOD))
        mstore(s2, addmod(mload(s2), calldataload(add(aproof, PROOF_R_AT_ZETA)), R_MOD))
        // _s2 := mload(s2)
        // (o(ζ)+γ)
        let o := add(s1, 0x40)
        mstore(o, addmod(calldataload(add(aproof, PROOF_O_AT_ZETA)), mload(add(state, STATE_GAMMA)), R_MOD))
        //  α*(Z(μζ))*(l(ζ)+β*s1(ζ)+γ)*(r(ζ)+β*s2(ζ)+γ)*(o(ζ)+γ)
        mstore(s1, mulmod(mload(s1), mload(s2), R_MOD))
        mstore(s1, mulmod(mload(s1), mload(o), R_MOD))
        mstore(s1, mulmod(mload(s1), mload(add(state, STATE_ALPHA)), R_MOD))
        mstore(s1, mulmod(mload(s1), calldataload(add(aproof, PROOF_GRAND_PRODUCT_AT_ZETA_OMEGA)), R_MOD))
        let computed_quotient := add(s1, 0x60)
        // linearizedpolynomial + pi(zeta)
        mstore(
          computed_quotient,
          addmod(calldataload(add(aproof, PROOF_LINEARISED_POLYNOMIAL_AT_ZETA)), mload(add(state, STATE_PI)), R_MOD)
        )
        mstore(computed_quotient, addmod(mload(computed_quotient), mload(s1), R_MOD))
        mstore(
          computed_quotient,
          addmod(mload(computed_quotient), sub(R_MOD, mload(add(state, STATE_ALPHA_SQUARE_LAGRANGE_0))), R_MOD)
        )
        mstore(
          s2,
          mulmod(
            calldataload(add(aproof, PROOF_QUOTIENT_POLYNOMIAL_AT_ZETA)),
            mload(add(state, STATE_ZETA_POWER_N_MINUS_ONE)),
            R_MOD
          )
        )
        mstore(add(state, STATE_SUCCESS), eq(mload(computed_quotient), mload(s2)))
      }
      // BEGINNING utils math functions -------------------------------------------------
      /// @param dst pointer storing the result
      /// @param p pointer to the first point
      /// @param q pointer to the second point
      /// @param mPtr pointer to free memory
      function point_add(dst, p, q, mPtr) {
        let state := mload(0x40)
        mstore(mPtr, mload(p))
        mstore(add(mPtr, 0x20), mload(add(p, 0x20)))
        mstore(add(mPtr, 0x40), mload(q))
        mstore(add(mPtr, 0x60), mload(add(q, 0x20)))
        let l_success := staticcall(gas(), 6, mPtr, 0x80, dst, 0x40)
        if iszero(l_success) {
          error_ec_op()
        }
      }
      /// @param dst pointer storing the result
      /// @param p pointer to the first point (calldata)
      /// @param q pointer to the second point (calladata)
      /// @param mPtr pointer to free memory
      function point_add_calldata(dst, p, q, mPtr) {
        let state := mload(0x40)
        mstore(mPtr, mload(p))
        mstore(add(mPtr, 0x20), mload(add(p, 0x20)))
        mstore(add(mPtr, 0x40), calldataload(q))
        mstore(add(mPtr, 0x60), calldataload(add(q, 0x20)))
        let l_success := staticcall(gas(), 6, mPtr, 0x80, dst, 0x40)
        if iszero(l_success) {
          error_ec_op()
        }
      }
      /// @parma dst pointer storing the result
      /// @param src pointer to a point on Bn254(𝔽_p)
      /// @param s scalar
      /// @param mPtr free memory
      function point_mul(dst, src, s, mPtr) {
        let state := mload(0x40)
        mstore(mPtr, mload(src))
        mstore(add(mPtr, 0x20), mload(add(src, 0x20)))
        mstore(add(mPtr, 0x40), s)
        let l_success := staticcall(gas(), 7, mPtr, 0x60, dst, 0x40)
        if iszero(l_success) {
          error_ec_op()
        }
      }
      /// @parma dst pointer storing the result
      /// @param src pointer to a point on Bn254(𝔽_p) on calldata
      /// @param s scalar
      /// @param mPtr free memory
      function point_mul_calldata(dst, src, s, mPtr) {
        let state := mload(0x40)
        mstore(mPtr, calldataload(src))
        mstore(add(mPtr, 0x20), calldataload(add(src, 0x20)))
        mstore(add(mPtr, 0x40), s)
        let l_success := staticcall(gas(), 7, mPtr, 0x60, dst, 0x40)
        if iszero(l_success) {
          error_ec_op()
        }
      }
      /// @notice dst <- dst + [s]src (Elliptic curve)
      /// @param dst pointer accumulator point storing the result
      /// @param src pointer to the point to multiply and add
      /// @param s scalar
      /// @param mPtr free memory
      function point_acc_mul(dst, src, s, mPtr) {
        let state := mload(0x40)
        mstore(mPtr, mload(src))
        mstore(add(mPtr, 0x20), mload(add(src, 0x20)))
        mstore(add(mPtr, 0x40), s)
        let l_success := staticcall(gas(), 7, mPtr, 0x60, mPtr, 0x40)
        mstore(add(mPtr, 0x40), mload(dst))
        mstore(add(mPtr, 0x60), mload(add(dst, 0x20)))
        l_success := and(l_success, staticcall(gas(), 6, mPtr, 0x80, dst, 0x40))
        if iszero(l_success) {
          error_ec_op()
        }
      }
      /// @notice dst <- dst + [s]src (Elliptic curve)
      /// @param dst pointer accumulator point storing the result
      /// @param src pointer to the point to multiply and add (on calldata)
      /// @param s scalar
      /// @mPtr free memory
      function point_acc_mul_calldata(dst, src, s, mPtr) {
        let state := mload(0x40)
        mstore(mPtr, calldataload(src))
        mstore(add(mPtr, 0x20), calldataload(add(src, 0x20)))
        mstore(add(mPtr, 0x40), s)
        let l_success := staticcall(gas(), 7, mPtr, 0x60, mPtr, 0x40)
        mstore(add(mPtr, 0x40), mload(dst))
        mstore(add(mPtr, 0x60), mload(add(dst, 0x20)))
        l_success := and(l_success, staticcall(gas(), 6, mPtr, 0x80, dst, 0x40))
        if iszero(l_success) {
          error_ec_op()
        }
      }
      /// @notice dst <- dst + src*s (Fr) dst,src are addresses, s is a value
      /// @param dst pointer storing the result
      /// @param src pointer to the scalar to multiply and add (on calldata)
      /// @param s scalar
      function fr_acc_mul_calldata(dst, src, s) {
        let tmp := mulmod(calldataload(src), s, R_MOD)
        mstore(dst, addmod(mload(dst), tmp, R_MOD))
      }
      /// @param x element to exponentiate
      /// @param e exponent
      /// @param mPtr free memory
      /// @return res x ** e mod r
      function pow(x, e, mPtr) -> res {
        mstore(mPtr, 0x20)
        mstore(add(mPtr, 0x20), 0x20)
        mstore(add(mPtr, 0x40), 0x20)
        mstore(add(mPtr, 0x60), x)
        mstore(add(mPtr, 0x80), e)
        mstore(add(mPtr, 0xa0), R_MOD)
        let check_staticcall := staticcall(gas(), 0x05, mPtr, 0xc0, mPtr, 0x20)
        if eq(check_staticcall, 0) {
          error_verify()
        }
        res := mload(mPtr)
      }
    }
  }
}