Contract Name:
EthBlockUpdater
Contract Source Code:
// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v4.9.0) (access/Ownable.sol)
pragma solidity ^0.8.0;
import "../utils/ContextUpgradeable.sol";
import "../proxy/utils/Initializable.sol";
/**
* @dev Contract module which provides a basic access control mechanism, where
* there is an account (an owner) that can be granted exclusive access to
* specific functions.
*
* By default, the owner account will be the one that deploys the contract. This
* can later be changed with {transferOwnership}.
*
* This module is used through inheritance. It will make available the modifier
* `onlyOwner`, which can be applied to your functions to restrict their use to
* the owner.
*/
abstract contract OwnableUpgradeable is Initializable, ContextUpgradeable {
address private _owner;
event OwnershipTransferred(address indexed previousOwner, address indexed newOwner);
/**
* @dev Initializes the contract setting the deployer as the initial owner.
*/
function __Ownable_init() internal onlyInitializing {
__Ownable_init_unchained();
}
function __Ownable_init_unchained() internal onlyInitializing {
_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. Can only be called by the current owner.
*
* NOTE: Renouncing ownership will leave the contract without an owner,
* thereby disabling 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);
}
/**
* @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) (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) (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
pragma solidity ^0.8.14;
import "@openzeppelin/contracts-upgradeable/proxy/utils/Initializable.sol";
import "@openzeppelin/contracts-upgradeable/access/OwnableUpgradeable.sol";
import "contracts/interface/IBlockUpdater.sol";
import "contracts/interface/ICircuitVerifierV2.sol";
import "contracts/libraries/ScaleCodec.sol";
import "./MerkleProof.sol";
import "./EthBlockVerifier.sol";
import "./EthLightClientVerifier.sol";
contract EthBlockUpdater is IBlockUpdater, MerkleProof, Initializable, OwnableUpgradeable {
event ImportSyncCommitteeRoot(uint64 indexed period, bytes32 indexed syncCommitteeRoot);
event ModBlockConfirmation(uint256 oldBlockConfirmation, uint256 newBlockConfirmation);
struct SyncCommitteeInput {
uint64 period;
bytes32 syncCommitteeRoot;
bytes32 nextSyncCommitteeRoot;
}
struct BlockInput {
uint64 slot;
uint256 blockConfirmation;
bytes32 syncCommitteeRoot;
bytes32 receiptHash;
bytes32 blockHash;
}
struct SyncCommitteeProof {
uint256[8] proof;
uint256[3] inputs;
}
struct BlockProof {
uint256[8] proof;
uint256[7] inputs;
}
struct Chain {
uint64 slot;
uint64 proposerIndex;
bytes32 parentRoot;
bytes32 stateRoot;
bytes32 bodyRoot;
bytes32 domain;
bytes32 blockHash;
bytes32 receiptRoot;
bytes32 payloadHash;
bytes32[] receiptBranch;
bytes32[] payloadBranch;
bytes32[] bodyBranch;
bytes32[] headerBranch;
bytes32[] blockHashBranch;
}
// period=>syncCommitteeRoot
mapping(uint64 => bytes32) public syncCommitteeRoots;
// blockHash=>receiptsRoot =>BlockConfirmation
mapping(bytes32 => mapping(bytes32 => uint256)) public blockInfos;
ICircuitVerifierV2 public blockVerifier;
ICircuitVerifierV2 public lightClientVerifier;
IBlockUpdater public oldBlockUpdater;
uint256 public minBlockConfirmation;
uint64 public currentPeriod;
function initialize(uint64 period, bytes32 syncCommitteeRoot, uint256 _minBlockConfirmation) public initializer {
__Ownable_init();
currentPeriod = period;
syncCommitteeRoots[period] = syncCommitteeRoot;
minBlockConfirmation = _minBlockConfirmation;
}
function importNextSyncCommittee(bytes calldata _proof) external {
require(address(lightClientVerifier) != address(0), "Not set committeeVerifier");
SyncCommitteeProof memory proofData;
(proofData.proof, proofData.inputs) = abi.decode(_proof, (uint256[8], uint256[3]));
SyncCommitteeInput memory input = _parseSyncCommitteeInput(proofData.inputs);
uint64 nextPeriod = input.period + 1;
require(syncCommitteeRoots[input.period] == input.syncCommitteeRoot, "invalid syncCommitteeRoot");
require(syncCommitteeRoots[nextPeriod] == bytes32(0), "nextSyncCommitteeRoot already exist");
uint256[1] memory compressInput;
compressInput[0] = _hashSyncCommitteeInput(proofData.inputs);
lightClientVerifier.verifyProof(proofData.proof, compressInput);
syncCommitteeRoots[nextPeriod] = input.nextSyncCommitteeRoot;
currentPeriod = nextPeriod;
emit ImportSyncCommitteeRoot(nextPeriod, input.nextSyncCommitteeRoot);
}
function importBlock(bytes calldata _proof) external {
require(address(blockVerifier) != address(0), "Not set blockVerifier");
BlockProof memory proofData;
(proofData.proof, proofData.inputs) = abi.decode(_proof, (uint256[8], uint256[7]));
BlockInput memory parsedInput = _parseBlockInput(proofData.inputs);
require(parsedInput.blockConfirmation >= minBlockConfirmation, "Not enough block confirmations");
(bool exist,uint256 blockConfirmation) = _checkBlock(parsedInput.blockHash, parsedInput.receiptHash);
if (exist && parsedInput.blockConfirmation <= blockConfirmation) {
revert("already exist");
}
uint64 period = _computePeriod(parsedInput.slot + 1);
require(syncCommitteeRoots[period] == parsedInput.syncCommitteeRoot, "invalid committeeRoot");
uint256[1] memory compressInput;
compressInput[0] = _hashBlockInput(proofData.inputs);
blockVerifier.verifyProof(proofData.proof, compressInput);
blockInfos[parsedInput.blockHash][parsedInput.receiptHash] = parsedInput.blockConfirmation;
emit ImportBlock(parsedInput.slot, parsedInput.blockHash, parsedInput.receiptHash);
}
function checkBlock(bytes32 _blockHash, bytes32 _receiptHash) external view returns (bool) {
(bool exist,) = _checkBlock(_blockHash, _receiptHash);
return exist;
}
function checkBlockConfirmation(bytes32 _blockHash, bytes32 _receiptHash) external view returns (bool, uint256) {
return _checkBlock(_blockHash, _receiptHash);
}
function submitBlockChain(Chain[] calldata blockChains) external {
require(blockChains.length > 1, "invalid chain length");
uint256 firstBlockConfirmation;
for (uint i = 0; i < blockChains.length; i++) {
Chain memory blockChain = blockChains[i];
bytes32[] memory leaves = new bytes32[](5);
leaves[0] = bytes32(_toLittleEndian64(blockChain.slot));
leaves[1] = bytes32(_toLittleEndian64(blockChain.proposerIndex));
leaves[2] = blockChain.parentRoot;
leaves[3] = blockChain.stateRoot;
leaves[4] = blockChain.bodyRoot;
bytes32 headerHash = merkleRoot(leaves);
if (i == 0) {
(bool exist,uint256 blockConfirmation) = _checkBlock(blockChain.blockHash, blockChain.receiptRoot);
require(exist, "invalid proof");
firstBlockConfirmation = blockConfirmation;
} else {
require(headerHash == blockChains[i - 1].parentRoot, "invalid proof");
}
require(isValidMerkleBranch(blockChain.receiptBranch, blockChain.receiptRoot, blockChain.payloadHash, 3, 5), "invalid receiptBranch");
require(isValidMerkleBranch(blockChain.payloadBranch, blockChain.payloadHash, blockChain.bodyRoot, 9, 4), "invalid payloadBranch");
require(isValidMerkleBranch(blockChain.blockHashBranch, blockChain.blockHash, blockChain.payloadHash, 12, 5), "invalid headerBranch");
if (i != 0) {
blockInfos[blockChain.blockHash][blockChain.receiptRoot] = firstBlockConfirmation + i;
emit ImportBlock(blockChain.slot, blockChain.blockHash, blockChain.receiptRoot);
}
}
}
function _checkBlock(bytes32 _blockHash, bytes32 _receiptHash) internal view returns (bool, uint256) {
uint256 blockConfirmation = blockInfos[_blockHash][_receiptHash];
if (blockConfirmation > 0) {
return (true, blockConfirmation);
}
if (address(oldBlockUpdater) != address(0)) {
if (oldBlockUpdater.checkBlock(_blockHash, _receiptHash)) {
return (true, minBlockConfirmation);
}
}
return (false, 0);
}
function _toLittleEndian64(uint64 value) internal pure returns (bytes8) {
return ScaleCodec.encode64(value);
}
function _parseSyncCommitteeInput(uint256[3] memory _inputs) internal pure returns (SyncCommitteeInput memory) {
SyncCommitteeInput memory result;
result.syncCommitteeRoot = bytes32(_inputs[0]);
result.nextSyncCommitteeRoot = bytes32(_inputs[1]);
result.period = uint64(_inputs[2]);
return result;
}
function _parseBlockInput(uint256[7] memory _inputs) internal pure returns (BlockInput memory) {
BlockInput memory result;
result.slot = uint64(_inputs[0]);
result.syncCommitteeRoot = bytes32(_inputs[1]);
result.receiptHash = bytes32((_inputs[2] << 128) | _inputs[3]);
result.blockHash = bytes32((_inputs[4] << 128) | _inputs[5]);
result.blockConfirmation = _inputs[6];
return result;
}
function _hashSyncCommitteeInput(uint256[3] memory _inputs) internal pure returns (uint256) {
uint256 computedHash = uint256(keccak256(abi.encodePacked(_inputs[0], _inputs[1], _inputs[2])));
return computedHash / 256;
}
function _hashBlockInput(uint256[7] memory _inputs) internal pure returns (uint256) {
uint256 computedHash = uint256(keccak256(abi.encodePacked(_inputs[0], _inputs[1], _inputs[2], _inputs[3], _inputs[4], _inputs[5], _inputs[6])));
return computedHash / 256;
}
function _computePeriod(uint64 slot) internal pure returns (uint64) {
return slot / 32 / 256;
}
//----------------------------------------------------------------------------------
// onlyOwner
function setBlockConfirmation(uint256 _minBlockConfirmation) external onlyOwner {
emit ModBlockConfirmation(minBlockConfirmation, _minBlockConfirmation);
minBlockConfirmation = _minBlockConfirmation;
}
function setOldBlockUpdater(address _oldBlockUpdater) external onlyOwner {
oldBlockUpdater = IBlockUpdater(_oldBlockUpdater);
}
function setBlockVerifier(address _blockVerifier) external onlyOwner {
require(_blockVerifier != address(0), "Zero address");
blockVerifier = ICircuitVerifierV2(_blockVerifier);
}
function setLightClientVerifier(address _lightClientVerifier) external onlyOwner {
require(_lightClientVerifier != address(0), "Zero address");
lightClientVerifier = ICircuitVerifierV2(_lightClientVerifier);
}
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
/// @title Groth16 verifier template.
/// @author Remco Bloemen
/// @notice Supports verifying Groth16 proofs. Proofs can be in uncompressed
/// (256 bytes) and compressed (128 bytes) format. A view function is provided
/// to compress proofs.
/// @notice See <https://2π.com/23/bn254-compression> for further explanation.
contract EthBlockVerifier {
/// Some of the provided public input values are larger than the field modulus.
/// @dev Public input elements are not automatically reduced, as this is can be
/// a dangerous source of bugs.
error PublicInputNotInField();
/// The proof is invalid.
/// @dev This can mean that provided Groth16 proof points are not on their
/// curves, that pairing equation fails, or that the proof is not for the
/// provided public input.
error ProofInvalid();
// Addresses of precompiles
uint256 constant PRECOMPILE_MODEXP = 0x05;
uint256 constant PRECOMPILE_ADD = 0x06;
uint256 constant PRECOMPILE_MUL = 0x07;
uint256 constant PRECOMPILE_VERIFY = 0x08;
// Base field Fp order P and scalar field Fr order R.
// For BN254 these are computed as follows:
// t = 4965661367192848881
// P = 36⋅t⁴ + 36⋅t³ + 24⋅t² + 6⋅t + 1
// R = 36⋅t⁴ + 36⋅t³ + 18⋅t² + 6⋅t + 1
uint256 constant P = 0x30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47;
uint256 constant R = 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001;
// Extension field Fp2 = Fp[i] / (i² + 1)
// Note: This is the complex extension field of Fp with i² = -1.
// Values in Fp2 are represented as a pair of Fp elements (a₀, a₁) as a₀ + a₁⋅i.
// Note: The order of Fp2 elements is *opposite* that of the pairing contract, which
// expects Fp2 elements in order (a₁, a₀). This is also the order in which
// Fp2 elements are encoded in the public interface as this became convention.
// Constants in Fp
uint256 constant FRACTION_1_2_FP = 0x183227397098d014dc2822db40c0ac2ecbc0b548b438e5469e10460b6c3e7ea4;
uint256 constant FRACTION_27_82_FP = 0x2b149d40ceb8aaae81be18991be06ac3b5b4c5e559dbefa33267e6dc24a138e5;
uint256 constant FRACTION_3_82_FP = 0x2fcd3ac2a640a154eb23960892a85a68f031ca0c8344b23a577dcf1052b9e775;
// Exponents for inversions and square roots mod P
uint256 constant EXP_INVERSE_FP = 0x30644E72E131A029B85045B68181585D97816A916871CA8D3C208C16D87CFD45; // P - 2
uint256 constant EXP_SQRT_FP = 0xC19139CB84C680A6E14116DA060561765E05AA45A1C72A34F082305B61F3F52; // (P + 1) / 4;
// Groth16 alpha point in G1
uint256 constant ALPHA_X = 18706090515532268669306462660553024134477705920043257579441938818805082009818;
uint256 constant ALPHA_Y = 17557632119056352457111782472723388037385895044829340323015773143735948735682;
// Groth16 beta point in G2 in powers of i
uint256 constant BETA_NEG_X_0 = 13925536520389883470910755942445961965080418120462415389483395736085490403039;
uint256 constant BETA_NEG_X_1 = 6169318415162071034212937204507408834519962418258944689275533170511816681876;
uint256 constant BETA_NEG_Y_0 = 15489281818443468872224174890041270186738017124876707539747092246107745429665;
uint256 constant BETA_NEG_Y_1 = 6685056051900934617572429436072891336591325700487406222922650474634970436574;
// Groth16 gamma point in G2 in powers of i
uint256 constant GAMMA_NEG_X_0 = 16114015195043152450696551447003447948971828029095524092253396204890494587387;
uint256 constant GAMMA_NEG_X_1 = 4186970639836610133950983218006065436689117661780959853486841271289064308452;
uint256 constant GAMMA_NEG_Y_0 = 16789114681695789940637751169089199660149478008721958118714899722969038953262;
uint256 constant GAMMA_NEG_Y_1 = 17214119412865344381331019673402639353059424267568972747654789069057196502981;
// Groth16 delta point in G2 in powers of i
uint256 constant DELTA_NEG_X_0 = 21018054191429934347907672551581170055135302012240035497978301599004179758263;
uint256 constant DELTA_NEG_X_1 = 12067267522108993166489302866104010575657811454789713735737049403962484490647;
uint256 constant DELTA_NEG_Y_0 = 1919516289945285450728027447098381352705383942006962939970882442552264063501;
uint256 constant DELTA_NEG_Y_1 = 17723683668125034984904748216204304875654955476848842655963497696688775740971;
// Constant and public input points
uint256 constant CONSTANT_X = 521757382115963247345430064325460522047585398378853597874094927440142386729;
uint256 constant CONSTANT_Y = 15607660637548039292193994254175787114108503001424323266277180198330571344892;
uint256 constant PUB_0_X = 8554846107040077773207564754743092395763523709838222255764878496452908137710;
uint256 constant PUB_0_Y = 8876272673664821281424442929390789139857632415876403956707375484943867834939;
/// Negation in Fp.
/// @notice Returns a number x such that a + x = 0 in Fp.
/// @notice The input does not need to be reduced.
/// @param a the base
/// @return x the result
function negate(uint256 a) internal pure returns (uint256 x) {
unchecked {
x = (P - (a % P)) % P; // Modulo is cheaper than branching
}
}
/// Exponentiation in Fp.
/// @notice Returns a number x such that a ^ e = x in Fp.
/// @notice The input does not need to be reduced.
/// @param a the base
/// @param e the exponent
/// @return x the result
function exp(uint256 a, uint256 e) internal view returns (uint256 x) {
bool success;
assembly ("memory-safe") {
let f := mload(0x40)
mstore(f, 0x20)
mstore(add(f, 0x20), 0x20)
mstore(add(f, 0x40), 0x20)
mstore(add(f, 0x60), a)
mstore(add(f, 0x80), e)
mstore(add(f, 0xa0), P)
success := staticcall(gas(), PRECOMPILE_MODEXP, f, 0xc0, f, 0x20)
x := mload(f)
}
if (!success) {
// Exponentiation failed.
// Should not happen.
revert ProofInvalid();
}
}
/// Invertsion in Fp.
/// @notice Returns a number x such that a * x = 1 in Fp.
/// @notice The input does not need to be reduced.
/// @notice Reverts with ProofInvalid() if the inverse does not exist
/// @param a the input
/// @return x the solution
function invert_Fp(uint256 a) internal view returns (uint256 x) {
x = exp(a, EXP_INVERSE_FP);
if (mulmod(a, x, P) != 1) {
// Inverse does not exist.
// Can only happen during G2 point decompression.
revert ProofInvalid();
}
}
/// Square root in Fp.
/// @notice Returns a number x such that x * x = a in Fp.
/// @notice Will revert with InvalidProof() if the input is not a square
/// or not reduced.
/// @param a the square
/// @return x the solution
function sqrt_Fp(uint256 a) internal view returns (uint256 x) {
x = exp(a, EXP_SQRT_FP);
if (mulmod(x, x, P) != a) {
// Square root does not exist or a is not reduced.
// Happens when G1 point is not on curve.
revert ProofInvalid();
}
}
/// Square test in Fp.
/// @notice Returns wheter a number x exists such that x * x = a in Fp.
/// @notice Will revert with InvalidProof() if the input is not a square
/// or not reduced.
/// @param a the square
/// @return x the solution
function isSquare_Fp(uint256 a) internal view returns (bool) {
uint256 x = exp(a, EXP_SQRT_FP);
return mulmod(x, x, P) == a;
}
/// Square root in Fp2.
/// @notice Fp2 is the complex extension Fp[i]/(i^2 + 1). The input is
/// a0 + a1 ⋅ i and the result is x0 + x1 ⋅ i.
/// @notice Will revert with InvalidProof() if
/// * the input is not a square,
/// * the hint is incorrect, or
/// * the input coefficents are not reduced.
/// @param a0 The real part of the input.
/// @param a1 The imaginary part of the input.
/// @param hint A hint which of two possible signs to pick in the equation.
/// @return x0 The real part of the square root.
/// @return x1 The imaginary part of the square root.
function sqrt_Fp2(uint256 a0, uint256 a1, bool hint) internal view returns (uint256 x0, uint256 x1) {
// If this square root reverts there is no solution in Fp2.
uint256 d = sqrt_Fp(addmod(mulmod(a0, a0, P), mulmod(a1, a1, P), P));
if (hint) {
d = negate(d);
}
// If this square root reverts there is no solution in Fp2.
x0 = sqrt_Fp(mulmod(addmod(a0, d, P), FRACTION_1_2_FP, P));
x1 = mulmod(a1, invert_Fp(mulmod(x0, 2, P)), P);
// Check result to make sure we found a root.
// Note: this also fails if a0 or a1 is not reduced.
if (a0 != addmod(mulmod(x0, x0, P), negate(mulmod(x1, x1, P)), P)
|| a1 != mulmod(2, mulmod(x0, x1, P), P)) {
revert ProofInvalid();
}
}
/// Compress a G1 point.
/// @notice Reverts with InvalidProof if the coordinates are not reduced
/// or if the point is not on the curve.
/// @notice The point at infinity is encoded as (0,0) and compressed to 0.
/// @param x The X coordinate in Fp.
/// @param y The Y coordinate in Fp.
/// @return c The compresed point (x with one signal bit).
function compress_g1(uint256 x, uint256 y) internal view returns (uint256 c) {
if (x >= P || y >= P) {
// G1 point not in field.
revert ProofInvalid();
}
if (x == 0 && y == 0) {
// Point at infinity
return 0;
}
// Note: sqrt_Fp reverts if there is no solution, i.e. the x coordinate is invalid.
uint256 y_pos = sqrt_Fp(addmod(mulmod(mulmod(x, x, P), x, P), 3, P));
if (y == y_pos) {
return (x << 1) | 0;
} else if (y == negate(y_pos)) {
return (x << 1) | 1;
} else {
// G1 point not on curve.
revert ProofInvalid();
}
}
/// Decompress a G1 point.
/// @notice Reverts with InvalidProof if the input does not represent a valid point.
/// @notice The point at infinity is encoded as (0,0) and compressed to 0.
/// @param c The compresed point (x with one signal bit).
/// @return x The X coordinate in Fp.
/// @return y The Y coordinate in Fp.
function decompress_g1(uint256 c) internal view returns (uint256 x, uint256 y) {
// Note that X = 0 is not on the curve since 0³ + 3 = 3 is not a square.
// so we can use it to represent the point at infinity.
if (c == 0) {
// Point at infinity as encoded in EIP196 and EIP197.
return (0, 0);
}
bool negate_point = c & 1 == 1;
x = c >> 1;
if (x >= P) {
// G1 x coordinate not in field.
revert ProofInvalid();
}
// Note: (x³ + 3) is irreducible in Fp, so it can not be zero and therefore
// y can not be zero.
// Note: sqrt_Fp reverts if there is no solution, i.e. the point is not on the curve.
y = sqrt_Fp(addmod(mulmod(mulmod(x, x, P), x, P), 3, P));
if (negate_point) {
y = negate(y);
}
}
/// Compress a G2 point.
/// @notice Reverts with InvalidProof if the coefficients are not reduced
/// or if the point is not on the curve.
/// @notice The G2 curve is defined over the complex extension Fp[i]/(i^2 + 1)
/// with coordinates (x0 + x1 ⋅ i, y0 + y1 ⋅ i).
/// @notice The point at infinity is encoded as (0,0,0,0) and compressed to (0,0).
/// @param x0 The real part of the X coordinate.
/// @param x1 The imaginary poart of the X coordinate.
/// @param y0 The real part of the Y coordinate.
/// @param y1 The imaginary part of the Y coordinate.
/// @return c0 The first half of the compresed point (x0 with two signal bits).
/// @return c1 The second half of the compressed point (x1 unmodified).
function compress_g2(uint256 x0, uint256 x1, uint256 y0, uint256 y1)
internal view returns (uint256 c0, uint256 c1) {
if (x0 >= P || x1 >= P || y0 >= P || y1 >= P) {
// G2 point not in field.
revert ProofInvalid();
}
if ((x0 | x1 | y0 | y1) == 0) {
// Point at infinity
return (0, 0);
}
// Compute y^2
// Note: shadowing variables and scoping to avoid stack-to-deep.
uint256 y0_pos;
uint256 y1_pos;
{
uint256 n3ab = mulmod(mulmod(x0, x1, P), P-3, P);
uint256 a_3 = mulmod(mulmod(x0, x0, P), x0, P);
uint256 b_3 = mulmod(mulmod(x1, x1, P), x1, P);
y0_pos = addmod(FRACTION_27_82_FP, addmod(a_3, mulmod(n3ab, x1, P), P), P);
y1_pos = negate(addmod(FRACTION_3_82_FP, addmod(b_3, mulmod(n3ab, x0, P), P), P));
}
// Determine hint bit
// If this sqrt fails the x coordinate is not on the curve.
bool hint;
{
uint256 d = sqrt_Fp(addmod(mulmod(y0_pos, y0_pos, P), mulmod(y1_pos, y1_pos, P), P));
hint = !isSquare_Fp(mulmod(addmod(y0_pos, d, P), FRACTION_1_2_FP, P));
}
// Recover y
(y0_pos, y1_pos) = sqrt_Fp2(y0_pos, y1_pos, hint);
if (y0 == y0_pos && y1 == y1_pos) {
c0 = (x0 << 2) | (hint ? 2 : 0) | 0;
c1 = x1;
} else if (y0 == negate(y0_pos) && y1 == negate(y1_pos)) {
c0 = (x0 << 2) | (hint ? 2 : 0) | 1;
c1 = x1;
} else {
// G1 point not on curve.
revert ProofInvalid();
}
}
/// Decompress a G2 point.
/// @notice Reverts with InvalidProof if the input does not represent a valid point.
/// @notice The G2 curve is defined over the complex extension Fp[i]/(i^2 + 1)
/// with coordinates (x0 + x1 ⋅ i, y0 + y1 ⋅ i).
/// @notice The point at infinity is encoded as (0,0,0,0) and compressed to (0,0).
/// @param c0 The first half of the compresed point (x0 with two signal bits).
/// @param c1 The second half of the compressed point (x1 unmodified).
/// @return x0 The real part of the X coordinate.
/// @return x1 The imaginary poart of the X coordinate.
/// @return y0 The real part of the Y coordinate.
/// @return y1 The imaginary part of the Y coordinate.
function decompress_g2(uint256 c0, uint256 c1)
internal view returns (uint256 x0, uint256 x1, uint256 y0, uint256 y1) {
// Note that X = (0, 0) is not on the curve since 0³ + 3/(9 + i) is not a square.
// so we can use it to represent the point at infinity.
if (c0 == 0 && c1 == 0) {
// Point at infinity as encoded in EIP197.
return (0, 0, 0, 0);
}
bool negate_point = c0 & 1 == 1;
bool hint = c0 & 2 == 2;
x0 = c0 >> 2;
x1 = c1;
if (x0 >= P || x1 >= P) {
// G2 x0 or x1 coefficient not in field.
revert ProofInvalid();
}
uint256 n3ab = mulmod(mulmod(x0, x1, P), P-3, P);
uint256 a_3 = mulmod(mulmod(x0, x0, P), x0, P);
uint256 b_3 = mulmod(mulmod(x1, x1, P), x1, P);
y0 = addmod(FRACTION_27_82_FP, addmod(a_3, mulmod(n3ab, x1, P), P), P);
y1 = negate(addmod(FRACTION_3_82_FP, addmod(b_3, mulmod(n3ab, x0, P), P), P));
// Note: sqrt_Fp2 reverts if there is no solution, i.e. the point is not on the curve.
// Note: (X³ + 3/(9 + i)) is irreducible in Fp2, so y can not be zero.
// But y0 or y1 may still independently be zero.
(y0, y1) = sqrt_Fp2(y0, y1, hint);
if (negate_point) {
y0 = negate(y0);
y1 = negate(y1);
}
}
/// Compute the public input linear combination.
/// @notice Reverts with PublicInputNotInField if the input is not in the field.
/// @notice Computes the multi-scalar-multiplication of the public input
/// elements and the verification key including the constant term.
/// @param input The public inputs. These are elements of the scalar field Fr.
/// @return x The X coordinate of the resulting G1 point.
/// @return y The Y coordinate of the resulting G1 point.
function publicInputMSM(uint256[1] calldata input)
internal view returns (uint256 x, uint256 y) {
// Note: The ECMUL precompile does not reject unreduced values, so we check this.
// Note: Unrolling this loop does not cost much extra in code-size, the bulk of the
// code-size is in the PUB_ constants.
// ECMUL has input (x, y, scalar) and output (x', y').
// ECADD has input (x1, y1, x2, y2) and output (x', y').
// We call them such that ecmul output is already in the second point
// argument to ECADD so we can have a tight loop.
bool success = true;
assembly ("memory-safe") {
let f := mload(0x40)
let g := add(f, 0x40)
let s
mstore(f, CONSTANT_X)
mstore(add(f, 0x20), CONSTANT_Y)
mstore(g, PUB_0_X)
mstore(add(g, 0x20), PUB_0_Y)
s := calldataload(input)
mstore(add(g, 0x40), s)
success := and(success, lt(s, R))
success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40))
success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40))
x := mload(f)
y := mload(add(f, 0x20))
}
if (!success) {
// Either Public input not in field, or verification key invalid.
// We assume the contract is correctly generated, so the verification key is valid.
revert PublicInputNotInField();
}
}
/// Compress a proof.
/// @notice Will revert with InvalidProof if the curve points are invalid,
/// but does not verify the proof itself.
/// @param proof The uncompressed Groth16 proof. Elements are in the same order as for
/// verifyProof. I.e. Groth16 points (A, B, C) encoded as in EIP-197.
/// @return compressed The compressed proof. Elements are in the same order as for
/// verifyCompressedProof. I.e. points (A, B, C) in compressed format.
function compressProof(uint256[8] calldata proof)
public view returns (uint256[4] memory compressed) {
compressed[0] = compress_g1(proof[0], proof[1]);
(compressed[2], compressed[1]) = compress_g2(proof[3], proof[2], proof[5], proof[4]);
compressed[3] = compress_g1(proof[6], proof[7]);
}
/// Verify a Groth16 proof with compressed points.
/// @notice Reverts with InvalidProof if the proof is invalid or
/// with PublicInputNotInField the public input is not reduced.
/// @notice There is no return value. If the function does not revert, the
/// proof was successfully verified.
/// @param compressedProof the points (A, B, C) in compressed format
/// matching the output of compressProof.
/// @param input the public input field elements in the scalar field Fr.
/// Elements must be reduced.
function verifyCompressedProof(
uint256[4] calldata compressedProof,
uint256[1] calldata input
) public view {
(uint256 Ax, uint256 Ay) = decompress_g1(compressedProof[0]);
(uint256 Bx0, uint256 Bx1, uint256 By0, uint256 By1) = decompress_g2(
compressedProof[2], compressedProof[1]);
(uint256 Cx, uint256 Cy) = decompress_g1(compressedProof[3]);
(uint256 Lx, uint256 Ly) = publicInputMSM(input);
// Verify the pairing
// Note: The precompile expects the F2 coefficients in big-endian order.
// Note: The pairing precompile rejects unreduced values, so we won't check that here.
uint256[24] memory pairings;
// e(A, B)
pairings[ 0] = Ax;
pairings[ 1] = Ay;
pairings[ 2] = Bx1;
pairings[ 3] = Bx0;
pairings[ 4] = By1;
pairings[ 5] = By0;
// e(C, -δ)
pairings[ 6] = Cx;
pairings[ 7] = Cy;
pairings[ 8] = DELTA_NEG_X_1;
pairings[ 9] = DELTA_NEG_X_0;
pairings[10] = DELTA_NEG_Y_1;
pairings[11] = DELTA_NEG_Y_0;
// e(α, -β)
pairings[12] = ALPHA_X;
pairings[13] = ALPHA_Y;
pairings[14] = BETA_NEG_X_1;
pairings[15] = BETA_NEG_X_0;
pairings[16] = BETA_NEG_Y_1;
pairings[17] = BETA_NEG_Y_0;
// e(L_pub, -γ)
pairings[18] = Lx;
pairings[19] = Ly;
pairings[20] = GAMMA_NEG_X_1;
pairings[21] = GAMMA_NEG_X_0;
pairings[22] = GAMMA_NEG_Y_1;
pairings[23] = GAMMA_NEG_Y_0;
// Check pairing equation.
bool success;
uint256[1] memory output;
assembly ("memory-safe") {
success := staticcall(gas(), PRECOMPILE_VERIFY, pairings, 0x300, output, 0x20)
}
if (!success || output[0] != 1) {
// Either proof or verification key invalid.
// We assume the contract is correctly generated, so the verification key is valid.
revert ProofInvalid();
}
}
/// Verify an uncompressed Groth16 proof.
/// @notice Reverts with InvalidProof if the proof is invalid or
/// with PublicInputNotInField the public input is not reduced.
/// @notice There is no return value. If the function does not revert, the
/// proof was successfully verified.
/// @param proof the points (A, B, C) in EIP-197 format matching the output
/// of compressProof.
/// @param input the public input field elements in the scalar field Fr.
/// Elements must be reduced.
function verifyProof(
uint256[8] calldata proof,
uint256[1] calldata input
) public view {
(uint256 x, uint256 y) = publicInputMSM(input);
// Note: The precompile expects the F2 coefficients in big-endian order.
// Note: The pairing precompile rejects unreduced values, so we won't check that here.
bool success;
assembly ("memory-safe") {
let f := mload(0x40) // Free memory pointer.
// Copy points (A, B, C) to memory. They are already in correct encoding.
// This is pairing e(A, B) and G1 of e(C, -δ).
calldatacopy(f, proof, 0x100)
// Complete e(C, -δ) and write e(α, -β), e(L_pub, -γ) to memory.
// OPT: This could be better done using a single codecopy, but
// Solidity (unlike standalone Yul) doesn't provide a way to
// to do this.
mstore(add(f, 0x100), DELTA_NEG_X_1)
mstore(add(f, 0x120), DELTA_NEG_X_0)
mstore(add(f, 0x140), DELTA_NEG_Y_1)
mstore(add(f, 0x160), DELTA_NEG_Y_0)
mstore(add(f, 0x180), ALPHA_X)
mstore(add(f, 0x1a0), ALPHA_Y)
mstore(add(f, 0x1c0), BETA_NEG_X_1)
mstore(add(f, 0x1e0), BETA_NEG_X_0)
mstore(add(f, 0x200), BETA_NEG_Y_1)
mstore(add(f, 0x220), BETA_NEG_Y_0)
mstore(add(f, 0x240), x)
mstore(add(f, 0x260), y)
mstore(add(f, 0x280), GAMMA_NEG_X_1)
mstore(add(f, 0x2a0), GAMMA_NEG_X_0)
mstore(add(f, 0x2c0), GAMMA_NEG_Y_1)
mstore(add(f, 0x2e0), GAMMA_NEG_Y_0)
// Check pairing equation.
success := staticcall(gas(), PRECOMPILE_VERIFY, f, 0x300, f, 0x20)
// Also check returned value (both are either 1 or 0).
success := and(success, mload(f))
}
if (!success) {
// Either proof or verification key invalid.
// We assume the contract is correctly generated, so the verification key is valid.
revert ProofInvalid();
}
}
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
/// @title Groth16 verifier template.
/// @author Remco Bloemen
/// @notice Supports verifying Groth16 proofs. Proofs can be in uncompressed
/// (256 bytes) and compressed (128 bytes) format. A view function is provided
/// to compress proofs.
/// @notice See <https://2π.com/23/bn254-compression> for further explanation.
contract EthLightClientVerifier {
/// Some of the provided public input values are larger than the field modulus.
/// @dev Public input elements are not automatically reduced, as this is can be
/// a dangerous source of bugs.
error PublicInputNotInField();
/// The proof is invalid.
/// @dev This can mean that provided Groth16 proof points are not on their
/// curves, that pairing equation fails, or that the proof is not for the
/// provided public input.
error ProofInvalid();
// Addresses of precompiles
uint256 constant PRECOMPILE_MODEXP = 0x05;
uint256 constant PRECOMPILE_ADD = 0x06;
uint256 constant PRECOMPILE_MUL = 0x07;
uint256 constant PRECOMPILE_VERIFY = 0x08;
// Base field Fp order P and scalar field Fr order R.
// For BN254 these are computed as follows:
// t = 4965661367192848881
// P = 36⋅t⁴ + 36⋅t³ + 24⋅t² + 6⋅t + 1
// R = 36⋅t⁴ + 36⋅t³ + 18⋅t² + 6⋅t + 1
uint256 constant P = 0x30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47;
uint256 constant R = 0x30644e72e131a029b85045b68181585d2833e84879b9709143e1f593f0000001;
// Extension field Fp2 = Fp[i] / (i² + 1)
// Note: This is the complex extension field of Fp with i² = -1.
// Values in Fp2 are represented as a pair of Fp elements (a₀, a₁) as a₀ + a₁⋅i.
// Note: The order of Fp2 elements is *opposite* that of the pairing contract, which
// expects Fp2 elements in order (a₁, a₀). This is also the order in which
// Fp2 elements are encoded in the public interface as this became convention.
// Constants in Fp
uint256 constant FRACTION_1_2_FP = 0x183227397098d014dc2822db40c0ac2ecbc0b548b438e5469e10460b6c3e7ea4;
uint256 constant FRACTION_27_82_FP = 0x2b149d40ceb8aaae81be18991be06ac3b5b4c5e559dbefa33267e6dc24a138e5;
uint256 constant FRACTION_3_82_FP = 0x2fcd3ac2a640a154eb23960892a85a68f031ca0c8344b23a577dcf1052b9e775;
// Exponents for inversions and square roots mod P
uint256 constant EXP_INVERSE_FP = 0x30644E72E131A029B85045B68181585D97816A916871CA8D3C208C16D87CFD45; // P - 2
uint256 constant EXP_SQRT_FP = 0xC19139CB84C680A6E14116DA060561765E05AA45A1C72A34F082305B61F3F52; // (P + 1) / 4;
// Groth16 alpha point in G1
uint256 constant ALPHA_X = 13915974525930517690322341382812560344339850691734118749616288831098950058163;
uint256 constant ALPHA_Y = 13500098445284936478142887888884769993288022215699771563522590287881098936433;
// Groth16 beta point in G2 in powers of i
uint256 constant BETA_NEG_X_0 = 3283456248526982517061549611209469236990636628302796304099417261752977679483;
uint256 constant BETA_NEG_X_1 = 11444070759846841187121133979892214095940328037778046748005841143556161662806;
uint256 constant BETA_NEG_Y_0 = 37697604019079956554568916303867646163151724622998777428382684960256063635;
uint256 constant BETA_NEG_Y_1 = 12171818244487606374881326712070217564120863569870573977017655633488982515723;
// Groth16 gamma point in G2 in powers of i
uint256 constant GAMMA_NEG_X_0 = 21132860686204535507223204111378929055078534704844414371003925991107858452647;
uint256 constant GAMMA_NEG_X_1 = 13447347558131306964718391450959658472636090449199444542075711846191141974511;
uint256 constant GAMMA_NEG_Y_0 = 11459652819867784997308202928253400887378181048793215876397055290057740922467;
uint256 constant GAMMA_NEG_Y_1 = 19753531265629440704729135782013882807072377249219320616990915011467963588105;
// Groth16 delta point in G2 in powers of i
uint256 constant DELTA_NEG_X_0 = 18188378713053789633092635367789801832415451885910071078726991261382582020717;
uint256 constant DELTA_NEG_X_1 = 1548153404053598897033256107194489389299151595240674537203224032612038968460;
uint256 constant DELTA_NEG_Y_0 = 15500365996148567969579386470346029547659690931596110579534167164406678713016;
uint256 constant DELTA_NEG_Y_1 = 3900957038542401124201678561408257427298271286758218567313778016374257094349;
// Constant and public input points
uint256 constant CONSTANT_X = 14151862387428222102727873608359289850196001386945258221176944397972818829970;
uint256 constant CONSTANT_Y = 14757853030521513093138720157949101609941847861763725624086335407141208957451;
uint256 constant PUB_0_X = 3738918475066631164062891590109399056353393487665051913685917960729048174952;
uint256 constant PUB_0_Y = 4758214283323418382163439447569281675912465178056842668302208941047387019454;
/// Negation in Fp.
/// @notice Returns a number x such that a + x = 0 in Fp.
/// @notice The input does not need to be reduced.
/// @param a the base
/// @return x the result
function negate(uint256 a) internal pure returns (uint256 x) {
unchecked {
x = (P - (a % P)) % P; // Modulo is cheaper than branching
}
}
/// Exponentiation in Fp.
/// @notice Returns a number x such that a ^ e = x in Fp.
/// @notice The input does not need to be reduced.
/// @param a the base
/// @param e the exponent
/// @return x the result
function exp(uint256 a, uint256 e) internal view returns (uint256 x) {
bool success;
assembly ("memory-safe") {
let f := mload(0x40)
mstore(f, 0x20)
mstore(add(f, 0x20), 0x20)
mstore(add(f, 0x40), 0x20)
mstore(add(f, 0x60), a)
mstore(add(f, 0x80), e)
mstore(add(f, 0xa0), P)
success := staticcall(gas(), PRECOMPILE_MODEXP, f, 0xc0, f, 0x20)
x := mload(f)
}
if (!success) {
// Exponentiation failed.
// Should not happen.
revert ProofInvalid();
}
}
/// Invertsion in Fp.
/// @notice Returns a number x such that a * x = 1 in Fp.
/// @notice The input does not need to be reduced.
/// @notice Reverts with ProofInvalid() if the inverse does not exist
/// @param a the input
/// @return x the solution
function invert_Fp(uint256 a) internal view returns (uint256 x) {
x = exp(a, EXP_INVERSE_FP);
if (mulmod(a, x, P) != 1) {
// Inverse does not exist.
// Can only happen during G2 point decompression.
revert ProofInvalid();
}
}
/// Square root in Fp.
/// @notice Returns a number x such that x * x = a in Fp.
/// @notice Will revert with InvalidProof() if the input is not a square
/// or not reduced.
/// @param a the square
/// @return x the solution
function sqrt_Fp(uint256 a) internal view returns (uint256 x) {
x = exp(a, EXP_SQRT_FP);
if (mulmod(x, x, P) != a) {
// Square root does not exist or a is not reduced.
// Happens when G1 point is not on curve.
revert ProofInvalid();
}
}
/// Square test in Fp.
/// @notice Returns wheter a number x exists such that x * x = a in Fp.
/// @notice Will revert with InvalidProof() if the input is not a square
/// or not reduced.
/// @param a the square
/// @return x the solution
function isSquare_Fp(uint256 a) internal view returns (bool) {
uint256 x = exp(a, EXP_SQRT_FP);
return mulmod(x, x, P) == a;
}
/// Square root in Fp2.
/// @notice Fp2 is the complex extension Fp[i]/(i^2 + 1). The input is
/// a0 + a1 ⋅ i and the result is x0 + x1 ⋅ i.
/// @notice Will revert with InvalidProof() if
/// * the input is not a square,
/// * the hint is incorrect, or
/// * the input coefficents are not reduced.
/// @param a0 The real part of the input.
/// @param a1 The imaginary part of the input.
/// @param hint A hint which of two possible signs to pick in the equation.
/// @return x0 The real part of the square root.
/// @return x1 The imaginary part of the square root.
function sqrt_Fp2(uint256 a0, uint256 a1, bool hint) internal view returns (uint256 x0, uint256 x1) {
// If this square root reverts there is no solution in Fp2.
uint256 d = sqrt_Fp(addmod(mulmod(a0, a0, P), mulmod(a1, a1, P), P));
if (hint) {
d = negate(d);
}
// If this square root reverts there is no solution in Fp2.
x0 = sqrt_Fp(mulmod(addmod(a0, d, P), FRACTION_1_2_FP, P));
x1 = mulmod(a1, invert_Fp(mulmod(x0, 2, P)), P);
// Check result to make sure we found a root.
// Note: this also fails if a0 or a1 is not reduced.
if (a0 != addmod(mulmod(x0, x0, P), negate(mulmod(x1, x1, P)), P)
|| a1 != mulmod(2, mulmod(x0, x1, P), P)) {
revert ProofInvalid();
}
}
/// Compress a G1 point.
/// @notice Reverts with InvalidProof if the coordinates are not reduced
/// or if the point is not on the curve.
/// @notice The point at infinity is encoded as (0,0) and compressed to 0.
/// @param x The X coordinate in Fp.
/// @param y The Y coordinate in Fp.
/// @return c The compresed point (x with one signal bit).
function compress_g1(uint256 x, uint256 y) internal view returns (uint256 c) {
if (x >= P || y >= P) {
// G1 point not in field.
revert ProofInvalid();
}
if (x == 0 && y == 0) {
// Point at infinity
return 0;
}
// Note: sqrt_Fp reverts if there is no solution, i.e. the x coordinate is invalid.
uint256 y_pos = sqrt_Fp(addmod(mulmod(mulmod(x, x, P), x, P), 3, P));
if (y == y_pos) {
return (x << 1) | 0;
} else if (y == negate(y_pos)) {
return (x << 1) | 1;
} else {
// G1 point not on curve.
revert ProofInvalid();
}
}
/// Decompress a G1 point.
/// @notice Reverts with InvalidProof if the input does not represent a valid point.
/// @notice The point at infinity is encoded as (0,0) and compressed to 0.
/// @param c The compresed point (x with one signal bit).
/// @return x The X coordinate in Fp.
/// @return y The Y coordinate in Fp.
function decompress_g1(uint256 c) internal view returns (uint256 x, uint256 y) {
// Note that X = 0 is not on the curve since 0³ + 3 = 3 is not a square.
// so we can use it to represent the point at infinity.
if (c == 0) {
// Point at infinity as encoded in EIP196 and EIP197.
return (0, 0);
}
bool negate_point = c & 1 == 1;
x = c >> 1;
if (x >= P) {
// G1 x coordinate not in field.
revert ProofInvalid();
}
// Note: (x³ + 3) is irreducible in Fp, so it can not be zero and therefore
// y can not be zero.
// Note: sqrt_Fp reverts if there is no solution, i.e. the point is not on the curve.
y = sqrt_Fp(addmod(mulmod(mulmod(x, x, P), x, P), 3, P));
if (negate_point) {
y = negate(y);
}
}
/// Compress a G2 point.
/// @notice Reverts with InvalidProof if the coefficients are not reduced
/// or if the point is not on the curve.
/// @notice The G2 curve is defined over the complex extension Fp[i]/(i^2 + 1)
/// with coordinates (x0 + x1 ⋅ i, y0 + y1 ⋅ i).
/// @notice The point at infinity is encoded as (0,0,0,0) and compressed to (0,0).
/// @param x0 The real part of the X coordinate.
/// @param x1 The imaginary poart of the X coordinate.
/// @param y0 The real part of the Y coordinate.
/// @param y1 The imaginary part of the Y coordinate.
/// @return c0 The first half of the compresed point (x0 with two signal bits).
/// @return c1 The second half of the compressed point (x1 unmodified).
function compress_g2(uint256 x0, uint256 x1, uint256 y0, uint256 y1)
internal view returns (uint256 c0, uint256 c1) {
if (x0 >= P || x1 >= P || y0 >= P || y1 >= P) {
// G2 point not in field.
revert ProofInvalid();
}
if ((x0 | x1 | y0 | y1) == 0) {
// Point at infinity
return (0, 0);
}
// Compute y^2
// Note: shadowing variables and scoping to avoid stack-to-deep.
uint256 y0_pos;
uint256 y1_pos;
{
uint256 n3ab = mulmod(mulmod(x0, x1, P), P-3, P);
uint256 a_3 = mulmod(mulmod(x0, x0, P), x0, P);
uint256 b_3 = mulmod(mulmod(x1, x1, P), x1, P);
y0_pos = addmod(FRACTION_27_82_FP, addmod(a_3, mulmod(n3ab, x1, P), P), P);
y1_pos = negate(addmod(FRACTION_3_82_FP, addmod(b_3, mulmod(n3ab, x0, P), P), P));
}
// Determine hint bit
// If this sqrt fails the x coordinate is not on the curve.
bool hint;
{
uint256 d = sqrt_Fp(addmod(mulmod(y0_pos, y0_pos, P), mulmod(y1_pos, y1_pos, P), P));
hint = !isSquare_Fp(mulmod(addmod(y0_pos, d, P), FRACTION_1_2_FP, P));
}
// Recover y
(y0_pos, y1_pos) = sqrt_Fp2(y0_pos, y1_pos, hint);
if (y0 == y0_pos && y1 == y1_pos) {
c0 = (x0 << 2) | (hint ? 2 : 0) | 0;
c1 = x1;
} else if (y0 == negate(y0_pos) && y1 == negate(y1_pos)) {
c0 = (x0 << 2) | (hint ? 2 : 0) | 1;
c1 = x1;
} else {
// G1 point not on curve.
revert ProofInvalid();
}
}
/// Decompress a G2 point.
/// @notice Reverts with InvalidProof if the input does not represent a valid point.
/// @notice The G2 curve is defined over the complex extension Fp[i]/(i^2 + 1)
/// with coordinates (x0 + x1 ⋅ i, y0 + y1 ⋅ i).
/// @notice The point at infinity is encoded as (0,0,0,0) and compressed to (0,0).
/// @param c0 The first half of the compresed point (x0 with two signal bits).
/// @param c1 The second half of the compressed point (x1 unmodified).
/// @return x0 The real part of the X coordinate.
/// @return x1 The imaginary poart of the X coordinate.
/// @return y0 The real part of the Y coordinate.
/// @return y1 The imaginary part of the Y coordinate.
function decompress_g2(uint256 c0, uint256 c1)
internal view returns (uint256 x0, uint256 x1, uint256 y0, uint256 y1) {
// Note that X = (0, 0) is not on the curve since 0³ + 3/(9 + i) is not a square.
// so we can use it to represent the point at infinity.
if (c0 == 0 && c1 == 0) {
// Point at infinity as encoded in EIP197.
return (0, 0, 0, 0);
}
bool negate_point = c0 & 1 == 1;
bool hint = c0 & 2 == 2;
x0 = c0 >> 2;
x1 = c1;
if (x0 >= P || x1 >= P) {
// G2 x0 or x1 coefficient not in field.
revert ProofInvalid();
}
uint256 n3ab = mulmod(mulmod(x0, x1, P), P-3, P);
uint256 a_3 = mulmod(mulmod(x0, x0, P), x0, P);
uint256 b_3 = mulmod(mulmod(x1, x1, P), x1, P);
y0 = addmod(FRACTION_27_82_FP, addmod(a_3, mulmod(n3ab, x1, P), P), P);
y1 = negate(addmod(FRACTION_3_82_FP, addmod(b_3, mulmod(n3ab, x0, P), P), P));
// Note: sqrt_Fp2 reverts if there is no solution, i.e. the point is not on the curve.
// Note: (X³ + 3/(9 + i)) is irreducible in Fp2, so y can not be zero.
// But y0 or y1 may still independently be zero.
(y0, y1) = sqrt_Fp2(y0, y1, hint);
if (negate_point) {
y0 = negate(y0);
y1 = negate(y1);
}
}
/// Compute the public input linear combination.
/// @notice Reverts with PublicInputNotInField if the input is not in the field.
/// @notice Computes the multi-scalar-multiplication of the public input
/// elements and the verification key including the constant term.
/// @param input The public inputs. These are elements of the scalar field Fr.
/// @return x The X coordinate of the resulting G1 point.
/// @return y The Y coordinate of the resulting G1 point.
function publicInputMSM(uint256[1] calldata input)
internal view returns (uint256 x, uint256 y) {
// Note: The ECMUL precompile does not reject unreduced values, so we check this.
// Note: Unrolling this loop does not cost much extra in code-size, the bulk of the
// code-size is in the PUB_ constants.
// ECMUL has input (x, y, scalar) and output (x', y').
// ECADD has input (x1, y1, x2, y2) and output (x', y').
// We call them such that ecmul output is already in the second point
// argument to ECADD so we can have a tight loop.
bool success = true;
assembly ("memory-safe") {
let f := mload(0x40)
let g := add(f, 0x40)
let s
mstore(f, CONSTANT_X)
mstore(add(f, 0x20), CONSTANT_Y)
mstore(g, PUB_0_X)
mstore(add(g, 0x20), PUB_0_Y)
s := calldataload(input)
mstore(add(g, 0x40), s)
success := and(success, lt(s, R))
success := and(success, staticcall(gas(), PRECOMPILE_MUL, g, 0x60, g, 0x40))
success := and(success, staticcall(gas(), PRECOMPILE_ADD, f, 0x80, f, 0x40))
x := mload(f)
y := mload(add(f, 0x20))
}
if (!success) {
// Either Public input not in field, or verification key invalid.
// We assume the contract is correctly generated, so the verification key is valid.
revert PublicInputNotInField();
}
}
/// Compress a proof.
/// @notice Will revert with InvalidProof if the curve points are invalid,
/// but does not verify the proof itself.
/// @param proof The uncompressed Groth16 proof. Elements are in the same order as for
/// verifyProof. I.e. Groth16 points (A, B, C) encoded as in EIP-197.
/// @return compressed The compressed proof. Elements are in the same order as for
/// verifyCompressedProof. I.e. points (A, B, C) in compressed format.
function compressProof(uint256[8] calldata proof)
public view returns (uint256[4] memory compressed) {
compressed[0] = compress_g1(proof[0], proof[1]);
(compressed[2], compressed[1]) = compress_g2(proof[3], proof[2], proof[5], proof[4]);
compressed[3] = compress_g1(proof[6], proof[7]);
}
/// Verify a Groth16 proof with compressed points.
/// @notice Reverts with InvalidProof if the proof is invalid or
/// with PublicInputNotInField the public input is not reduced.
/// @notice There is no return value. If the function does not revert, the
/// proof was successfully verified.
/// @param compressedProof the points (A, B, C) in compressed format
/// matching the output of compressProof.
/// @param input the public input field elements in the scalar field Fr.
/// Elements must be reduced.
function verifyCompressedProof(
uint256[4] calldata compressedProof,
uint256[1] calldata input
) public view {
(uint256 Ax, uint256 Ay) = decompress_g1(compressedProof[0]);
(uint256 Bx0, uint256 Bx1, uint256 By0, uint256 By1) = decompress_g2(
compressedProof[2], compressedProof[1]);
(uint256 Cx, uint256 Cy) = decompress_g1(compressedProof[3]);
(uint256 Lx, uint256 Ly) = publicInputMSM(input);
// Verify the pairing
// Note: The precompile expects the F2 coefficients in big-endian order.
// Note: The pairing precompile rejects unreduced values, so we won't check that here.
uint256[24] memory pairings;
// e(A, B)
pairings[ 0] = Ax;
pairings[ 1] = Ay;
pairings[ 2] = Bx1;
pairings[ 3] = Bx0;
pairings[ 4] = By1;
pairings[ 5] = By0;
// e(C, -δ)
pairings[ 6] = Cx;
pairings[ 7] = Cy;
pairings[ 8] = DELTA_NEG_X_1;
pairings[ 9] = DELTA_NEG_X_0;
pairings[10] = DELTA_NEG_Y_1;
pairings[11] = DELTA_NEG_Y_0;
// e(α, -β)
pairings[12] = ALPHA_X;
pairings[13] = ALPHA_Y;
pairings[14] = BETA_NEG_X_1;
pairings[15] = BETA_NEG_X_0;
pairings[16] = BETA_NEG_Y_1;
pairings[17] = BETA_NEG_Y_0;
// e(L_pub, -γ)
pairings[18] = Lx;
pairings[19] = Ly;
pairings[20] = GAMMA_NEG_X_1;
pairings[21] = GAMMA_NEG_X_0;
pairings[22] = GAMMA_NEG_Y_1;
pairings[23] = GAMMA_NEG_Y_0;
// Check pairing equation.
bool success;
uint256[1] memory output;
assembly ("memory-safe") {
success := staticcall(gas(), PRECOMPILE_VERIFY, pairings, 0x300, output, 0x20)
}
if (!success || output[0] != 1) {
// Either proof or verification key invalid.
// We assume the contract is correctly generated, so the verification key is valid.
revert ProofInvalid();
}
}
/// Verify an uncompressed Groth16 proof.
/// @notice Reverts with InvalidProof if the proof is invalid or
/// with PublicInputNotInField the public input is not reduced.
/// @notice There is no return value. If the function does not revert, the
/// proof was successfully verified.
/// @param proof the points (A, B, C) in EIP-197 format matching the output
/// of compressProof.
/// @param input the public input field elements in the scalar field Fr.
/// Elements must be reduced.
function verifyProof(
uint256[8] calldata proof,
uint256[1] calldata input
) public view {
(uint256 x, uint256 y) = publicInputMSM(input);
// Note: The precompile expects the F2 coefficients in big-endian order.
// Note: The pairing precompile rejects unreduced values, so we won't check that here.
bool success;
assembly ("memory-safe") {
let f := mload(0x40) // Free memory pointer.
// Copy points (A, B, C) to memory. They are already in correct encoding.
// This is pairing e(A, B) and G1 of e(C, -δ).
calldatacopy(f, proof, 0x100)
// Complete e(C, -δ) and write e(α, -β), e(L_pub, -γ) to memory.
// OPT: This could be better done using a single codecopy, but
// Solidity (unlike standalone Yul) doesn't provide a way to
// to do this.
mstore(add(f, 0x100), DELTA_NEG_X_1)
mstore(add(f, 0x120), DELTA_NEG_X_0)
mstore(add(f, 0x140), DELTA_NEG_Y_1)
mstore(add(f, 0x160), DELTA_NEG_Y_0)
mstore(add(f, 0x180), ALPHA_X)
mstore(add(f, 0x1a0), ALPHA_Y)
mstore(add(f, 0x1c0), BETA_NEG_X_1)
mstore(add(f, 0x1e0), BETA_NEG_X_0)
mstore(add(f, 0x200), BETA_NEG_Y_1)
mstore(add(f, 0x220), BETA_NEG_Y_0)
mstore(add(f, 0x240), x)
mstore(add(f, 0x260), y)
mstore(add(f, 0x280), GAMMA_NEG_X_1)
mstore(add(f, 0x2a0), GAMMA_NEG_X_0)
mstore(add(f, 0x2c0), GAMMA_NEG_Y_1)
mstore(add(f, 0x2e0), GAMMA_NEG_Y_0)
// Check pairing equation.
success := staticcall(gas(), PRECOMPILE_VERIFY, f, 0x300, f, 0x20)
// Also check returned value (both are either 1 or 0).
success := and(success, mload(f))
}
if (!success) {
// Either proof or verification key invalid.
// We assume the contract is correctly generated, so the verification key is valid.
revert ProofInvalid();
}
}
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
contract Math {
/// Get the power of 2 for given input, or the closest higher power of 2 if the input is not a power of 2.
/// Commonly used for "how many nodes do I need for a bottom tree layer fitting x elements?"
/// Example: 0->1, 1->1, 2->2, 3->4, 4->4, 5->8, 6->8, 7->8, 8->8, 9->16.
function getPowerOfTwoCeil(uint256 x) internal pure returns (uint256) {
if (x <= 1) return 1;
else if (x == 2) return 2;
uint256 nextX = (x + 1) >> 1;
uint256 powerOfTwoCeil = getPowerOfTwoCeil(nextX);
if (powerOfTwoCeil > (type(uint256).max >> 1)) {
revert("overflow");
}
return 2 * powerOfTwoCeil;
}
function log_2(uint256 x) internal pure returns (uint256 pow) {
require(0 < x && x < 0x8000000000000000000000000000000000000000000000000000000000000001, "invalid");
uint256 a = 1;
while (a < x) {
a <<= 1;
pow++;
}
}
function _max(uint x, uint y) internal pure returns (uint z) {
return x >= y ? x : y;
}
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
import "./Math.sol";
contract MerkleProof is Math {
// Check if ``leaf`` at ``index`` verifies against the Merkle ``root`` and ``branch``.
function isValidMerkleBranch(
bytes32[] memory branch,
bytes32 leaf,
bytes32 root,
uint64 index,
uint64 depth
) internal pure returns (bool) {
bytes32 value = leaf;
for (uint i = 0; i < depth; ++i) {
if ((index / (2 ** i)) % 2 == 1) {
value = hashNode(branch[i], value);
} else {
value = hashNode(value, branch[i]);
}
}
return value == root;
}
function merkleRoot(bytes32[] memory leaves) internal pure returns (bytes32) {
uint len = leaves.length;
if (len == 0) return bytes32(0);
else if (len == 1) return hash(abi.encodePacked(leaves[0]));
else if (len == 2) return hashNode(leaves[0], leaves[1]);
uint bottomLength = getPowerOfTwoCeil(len);
bytes32[] memory o = new bytes32[](bottomLength * 2);
for (uint i = 0; i < len; ++i) {
o[bottomLength + i] = leaves[i];
}
for (uint i = bottomLength - 1; i > 0; --i) {
o[i] = hashNode(o[i * 2], o[i * 2 + 1]);
}
return o[1];
}
function hashNode(bytes32 left, bytes32 right)
internal
pure
returns (bytes32)
{
return hash(abi.encodePacked(left, right));
}
function hash(bytes memory value) internal pure returns (bytes32) {
return sha256(value);
}
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
interface IBlockUpdater {
event ImportBlock(uint256 identifier, bytes32 blockHash, bytes32 receiptHash);
function importBlock(bytes calldata _proof) external;
function checkBlock(bytes32 _blockHash, bytes32 _receiptsRoot) external view returns (bool);
function checkBlockConfirmation(bytes32 _blockHash, bytes32 _receiptsRoot) external view returns (bool, uint256);
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
interface ICircuitVerifierV2 {
function verifyProof(
uint256[8] memory proof,
uint256[1] memory input
) external;
}
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;
library ScaleCodec {
// Decodes a SCALE encoded uint256 by converting bytes (bid endian) to little endian format
function decodeUint256(bytes memory data) internal pure returns (uint256) {
uint256 number;
for (uint256 i = data.length; i > 0; i--) {
number = number + uint256(uint8(data[i - 1])) * (2**(8 * (i - 1)));
}
return number;
}
// Decodes a SCALE encoded compact unsigned integer
function decodeUintCompact(bytes memory data)
internal
pure
returns (uint256 v)
{
uint8 b = readByteAtIndex(data, 0); // read the first byte
uint8 mode = b & 3; // bitwise operation
if (mode == 0) {
// [0, 63]
return b >> 2; // right shift to remove mode bits
} else if (mode == 1) {
// [64, 16383]
uint8 bb = readByteAtIndex(data, 1); // read the second byte
uint64 r = bb; // convert to uint64
r <<= 6; // multiply by * 2^6
r += b >> 2; // right shift to remove mode bits
return r;
} else if (mode == 2) {
// [16384, 1073741823]
uint8 b2 = readByteAtIndex(data, 1); // read the next 3 bytes
uint8 b3 = readByteAtIndex(data, 2);
uint8 b4 = readByteAtIndex(data, 3);
uint32 x1 = uint32(b) | (uint32(b2) << 8); // convert to little endian
uint32 x2 = x1 | (uint32(b3) << 16);
uint32 x3 = x2 | (uint32(b4) << 24);
x3 >>= 2; // remove the last 2 mode bits
return uint256(x3);
} else if (mode == 3) {
// [1073741824, 4503599627370496]
// solhint-disable-next-line
uint8 l = b >> 2; // remove mode bits
require(
l > 32,
"Not supported: number cannot be greater than 32 bytes"
);
} else {
revert("Code should be unreachable");
}
}
// Read a byte at a specific index and return it as type uint8
function readByteAtIndex(bytes memory data, uint8 index)
internal
pure
returns (uint8)
{
return uint8(data[index]);
}
// Sources:
// * https://ethereum.stackexchange.com/questions/15350/how-to-convert-an-bytes-to-address-in-solidity/50528
// * https://graphics.stanford.edu/~seander/bithacks.html#ReverseParallel
function reverse256(uint256 input) internal pure returns (uint256 v) {
v = input;
// swap bytes
v = ((v & 0xFF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00) >> 8) |
((v & 0x00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF00FF) << 8);
// swap 2-byte long pairs
v = ((v & 0xFFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000) >> 16) |
((v & 0x0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF0000FFFF) << 16);
// swap 4-byte long pairs
v = ((v & 0xFFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000) >> 32) |
((v & 0x00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF00000000FFFFFFFF) << 32);
// swap 8-byte long pairs
v = ((v & 0xFFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF0000000000000000) >> 64) |
((v & 0x0000000000000000FFFFFFFFFFFFFFFF0000000000000000FFFFFFFFFFFFFFFF) << 64);
// swap 16-byte long pairs
v = (v >> 128) | (v << 128);
}
function reverse128(uint128 input) internal pure returns (uint128 v) {
v = input;
// swap bytes
v = ((v & 0xFF00FF00FF00FF00FF00FF00FF00FF00) >> 8) |
((v & 0x00FF00FF00FF00FF00FF00FF00FF00FF) << 8);
// swap 2-byte long pairs
v = ((v & 0xFFFF0000FFFF0000FFFF0000FFFF0000) >> 16) |
((v & 0x0000FFFF0000FFFF0000FFFF0000FFFF) << 16);
// swap 4-byte long pairs
v = ((v & 0xFFFFFFFF00000000FFFFFFFF00000000) >> 32) |
((v & 0x00000000FFFFFFFF00000000FFFFFFFF) << 32);
// swap 8-byte long pairs
v = (v >> 64) | (v << 64);
}
function reverse64(uint64 input) internal pure returns (uint64 v) {
v = input;
// swap bytes
v = ((v & 0xFF00FF00FF00FF00) >> 8) |
((v & 0x00FF00FF00FF00FF) << 8);
// swap 2-byte long pairs
v = ((v & 0xFFFF0000FFFF0000) >> 16) |
((v & 0x0000FFFF0000FFFF) << 16);
// swap 4-byte long pairs
v = (v >> 32) | (v << 32);
}
function reverse32(uint32 input) internal pure returns (uint32 v) {
v = input;
// swap bytes
v = ((v & 0xFF00FF00) >> 8) |
((v & 0x00FF00FF) << 8);
// swap 2-byte long pairs
v = (v >> 16) | (v << 16);
}
function reverse16(uint16 input) internal pure returns (uint16 v) {
v = input;
// swap bytes
v = (v >> 8) | (v << 8);
}
function encode256(uint256 input) internal pure returns (bytes32) {
return bytes32(reverse256(input));
}
function encode128(uint128 input) internal pure returns (bytes16) {
return bytes16(reverse128(input));
}
function encode64(uint64 input) internal pure returns (bytes8) {
return bytes8(reverse64(input));
}
function encode32(uint32 input) internal pure returns (bytes4) {
return bytes4(reverse32(input));
}
function encode16(uint16 input) internal pure returns (bytes2) {
return bytes2(reverse16(input));
}
function encode8(uint8 input) internal pure returns (bytes1) {
return bytes1(input);
}
}