Description:
Proxy contract enabling upgradeable smart contract patterns. Delegates calls to an implementation contract.
Blockchain: Ethereum
Source Code: View Code On The Blockchain
Solidity Source Code:
{{
"language": "Solidity",
"sources": {
"@openzeppelin/contracts/interfaces/IERC5267.sol": {
"content": "// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.0) (interfaces/IERC5267.sol)
pragma solidity ^0.8.20;
interface IERC5267 {
/**
* @dev MAY be emitted to signal that the domain could have changed.
*/
event EIP712DomainChanged();
/**
* @dev returns the fields and values that describe the domain separator used by this contract for EIP-712
* signature.
*/
function eip712Domain()
external
view
returns (
bytes1 fields,
string memory name,
string memory version,
uint256 chainId,
address verifyingContract,
bytes32 salt,
uint256[] memory extensions
);
}
"
},
"@openzeppelin/contracts/metatx/ERC2771Context.sol": {
"content": "// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.1.0) (metatx/ERC2771Context.sol)
pragma solidity ^0.8.20;
import {Context} from "../utils/Context.sol";
/**
* @dev Context variant with ERC-2771 support.
*
* WARNING: Avoid using this pattern in contracts that rely in a specific calldata length as they'll
* be affected by any forwarder whose `msg.data` is suffixed with the `from` address according to the ERC-2771
* specification adding the address size in bytes (20) to the calldata size. An example of an unexpected
* behavior could be an unintended fallback (or another function) invocation while trying to invoke the `receive`
* function only accessible if `msg.data.length == 0`.
*
* WARNING: The usage of `delegatecall` in this contract is dangerous and may result in context corruption.
* Any forwarded request to this contract triggering a `delegatecall` to itself will result in an invalid {_msgSender}
* recovery.
*/
abstract contract ERC2771Context is Context {
/// @custom:oz-upgrades-unsafe-allow state-variable-immutable
address private immutable _trustedForwarder;
/**
* @dev Initializes the contract with a trusted forwarder, which will be able to
* invoke functions on this contract on behalf of other accounts.
*
* NOTE: The trusted forwarder can be replaced by overriding {trustedForwarder}.
*/
/// @custom:oz-upgrades-unsafe-allow constructor
constructor(address trustedForwarder_) {
_trustedForwarder = trustedForwarder_;
}
/**
* @dev Returns the address of the trusted forwarder.
*/
function trustedForwarder() public view virtual returns (address) {
return _trustedForwarder;
}
/**
* @dev Indicates whether any particular address is the trusted forwarder.
*/
function isTrustedForwarder(address forwarder) public view virtual returns (bool) {
return forwarder == trustedForwarder();
}
/**
* @dev Override for `msg.sender`. Defaults to the original `msg.sender` whenever
* a call is not performed by the trusted forwarder or the calldata length is less than
* 20 bytes (an address length).
*/
function _msgSender() internal view virtual override returns (address) {
uint256 calldataLength = msg.data.length;
uint256 contextSuffixLength = _contextSuffixLength();
if (isTrustedForwarder(msg.sender) && calldataLength >= contextSuffixLength) {
return address(bytes20(msg.data[calldataLength - contextSuffixLength:]));
} else {
return super._msgSender();
}
}
/**
* @dev Override for `msg.data`. Defaults to the original `msg.data` whenever
* a call is not performed by the trusted forwarder or the calldata length is less than
* 20 bytes (an address length).
*/
function _msgData() internal view virtual override returns (bytes calldata) {
uint256 calldataLength = msg.data.length;
uint256 contextSuffixLength = _contextSuffixLength();
if (isTrustedForwarder(msg.sender) && calldataLength >= contextSuffixLength) {
return msg.data[:calldataLength - contextSuffixLength];
} else {
return super._msgData();
}
}
/**
* @dev ERC-2771 specifies the context as being a single address (20 bytes).
*/
function _contextSuffixLength() internal view virtual override returns (uint256) {
return 20;
}
}
"
},
"@openzeppelin/contracts/metatx/ERC2771Forwarder.sol": {
"content": "// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.3.0) (metatx/ERC2771Forwarder.sol)
pragma solidity ^0.8.20;
import {ERC2771Context} from "./ERC2771Context.sol";
import {ECDSA} from "../utils/cryptography/ECDSA.sol";
import {EIP712} from "../utils/cryptography/EIP712.sol";
import {Nonces} from "../utils/Nonces.sol";
import {Address} from "../utils/Address.sol";
import {Errors} from "../utils/Errors.sol";
/**
* @dev A forwarder compatible with ERC-2771 contracts. See {ERC2771Context}.
*
* This forwarder operates on forward requests that include:
*
* * `from`: An address to operate on behalf of. It is required to be equal to the request signer.
* * `to`: The address that should be called.
* * `value`: The amount of native token to attach with the requested call.
* * `gas`: The amount of gas limit that will be forwarded with the requested call.
* * `nonce`: A unique transaction ordering identifier to avoid replayability and request invalidation.
* * `deadline`: A timestamp after which the request is not executable anymore.
* * `data`: Encoded `msg.data` to send with the requested call.
*
* Relayers are able to submit batches if they are processing a high volume of requests. With high
* throughput, relayers may run into limitations of the chain such as limits on the number of
* transactions in the mempool. In these cases the recommendation is to distribute the load among
* multiple accounts.
*
* NOTE: Batching requests includes an optional refund for unused `msg.value` that is achieved by
* performing a call with empty calldata. While this is within the bounds of ERC-2771 compliance,
* if the refund receiver happens to consider the forwarder a trusted forwarder, it MUST properly
* handle `msg.data.length == 0`. `ERC2771Context` in OpenZeppelin Contracts versions prior to 4.9.3
* do not handle this properly.
*
* ==== Security Considerations
*
* If a relayer submits a forward request, it should be willing to pay up to 100% of the gas amount
* specified in the request. This contract does not implement any kind of retribution for this gas,
* and it is assumed that there is an out of band incentive for relayers to pay for execution on
* behalf of signers. Often, the relayer is operated by a project that will consider it a user
* acquisition cost.
*
* By offering to pay for gas, relayers are at risk of having that gas used by an attacker toward
* some other purpose that is not aligned with the expected out of band incentives. If you operate a
* relayer, consider whitelisting target contracts and function selectors. When relaying ERC-721 or
* ERC-1155 transfers specifically, consider rejecting the use of the `data` field, since it can be
* used to execute arbitrary code.
*/
contract ERC2771Forwarder is EIP712, Nonces {
using ECDSA for bytes32;
struct ForwardRequestData {
address from;
address to;
uint256 value;
uint256 gas;
uint48 deadline;
bytes data;
bytes signature;
}
bytes32 internal constant _FORWARD_REQUEST_TYPEHASH =
keccak256(
"ForwardRequest(address from,address to,uint256 value,uint256 gas,uint256 nonce,uint48 deadline,bytes data)"
);
/**
* @dev Emitted when a `ForwardRequest` is executed.
*
* NOTE: An unsuccessful forward request could be due to an invalid signature, an expired deadline,
* or simply a revert in the requested call. The contract guarantees that the relayer is not able to force
* the requested call to run out of gas.
*/
event ExecutedForwardRequest(address indexed signer, uint256 nonce, bool success);
/**
* @dev The request `from` doesn't match with the recovered `signer`.
*/
error ERC2771ForwarderInvalidSigner(address signer, address from);
/**
* @dev The `requestedValue` doesn't match with the available `msgValue`.
*/
error ERC2771ForwarderMismatchedValue(uint256 requestedValue, uint256 msgValue);
/**
* @dev The request `deadline` has expired.
*/
error ERC2771ForwarderExpiredRequest(uint48 deadline);
/**
* @dev The request target doesn't trust the `forwarder`.
*/
error ERC2771UntrustfulTarget(address target, address forwarder);
/**
* @dev See {EIP712-constructor}.
*/
constructor(string memory name) EIP712(name, "1") {}
/**
* @dev Returns `true` if a request is valid for a provided `signature` at the current block timestamp.
*
* A transaction is considered valid when the target trusts this forwarder, the request hasn't expired
* (deadline is not met), and the signer matches the `from` parameter of the signed request.
*
* NOTE: A request may return false here but it won't cause {executeBatch} to revert if a refund
* receiver is provided.
*/
function verify(ForwardRequestData calldata request) public view virtual returns (bool) {
(bool isTrustedForwarder, bool active, bool signerMatch, ) = _validate(request);
return isTrustedForwarder && active && signerMatch;
}
/**
* @dev Executes a `request` on behalf of `signature`'s signer using the ERC-2771 protocol. The gas
* provided to the requested call may not be exactly the amount requested, but the call will not run
* out of gas. Will revert if the request is invalid or the call reverts, in this case the nonce is not consumed.
*
* Requirements:
*
* - The request value should be equal to the provided `msg.value`.
* - The request should be valid according to {verify}.
*/
function execute(ForwardRequestData calldata request) public payable virtual {
// We make sure that msg.value and request.value match exactly.
// If the request is invalid or the call reverts, this whole function
// will revert, ensuring value isn't stuck.
if (msg.value != request.value) {
revert ERC2771ForwarderMismatchedValue(request.value, msg.value);
}
if (!_execute(request, true)) {
revert Errors.FailedCall();
}
}
/**
* @dev Batch version of {execute} with optional refunding and atomic execution.
*
* In case a batch contains at least one invalid request (see {verify}), the
* request will be skipped and the `refundReceiver` parameter will receive back the
* unused requested value at the end of the execution. This is done to prevent reverting
* the entire batch when a request is invalid or has already been submitted.
*
* If the `refundReceiver` is the `address(0)`, this function will revert when at least
* one of the requests was not valid instead of skipping it. This could be useful if
* a batch is required to get executed atomically (at least at the top-level). For example,
* refunding (and thus atomicity) can be opt-out if the relayer is using a service that avoids
* including reverted transactions.
*
* Requirements:
*
* - The sum of the requests' values should be equal to the provided `msg.value`.
* - All of the requests should be valid (see {verify}) when `refundReceiver` is the zero address.
*
* NOTE: Setting a zero `refundReceiver` guarantees an all-or-nothing requests execution only for
* the first-level forwarded calls. In case a forwarded request calls to a contract with another
* subcall, the second-level call may revert without the top-level call reverting.
*/
function executeBatch(
ForwardRequestData[] calldata requests,
address payable refundReceiver
) public payable virtual {
bool atomic = refundReceiver == address(0);
uint256 requestsValue;
uint256 refundValue;
for (uint256 i; i < requests.length; ++i) {
requestsValue += requests[i].value;
bool success = _execute(requests[i], atomic);
if (!success) {
refundValue += requests[i].value;
}
}
// The batch should revert if there's a mismatched msg.value provided
// to avoid request value tampering
if (requestsValue != msg.value) {
revert ERC2771ForwarderMismatchedValue(requestsValue, msg.value);
}
// Some requests with value were invalid (possibly due to frontrunning).
// To avoid leaving ETH in the contract this value is refunded.
if (refundValue != 0) {
// We know refundReceiver != address(0) && requestsValue == msg.value
// meaning we can ensure refundValue is not taken from the original contract's balance
// and refundReceiver is a known account.
Address.sendValue(refundReceiver, refundValue);
}
}
/**
* @dev Validates if the provided request can be executed at current block timestamp with
* the given `request.signature` on behalf of `request.signer`.
*/
function _validate(
ForwardRequestData calldata request
) internal view virtual returns (bool isTrustedForwarder, bool active, bool signerMatch, address signer) {
(bool isValid, address recovered) = _recoverForwardRequestSigner(request);
return (
_isTrustedByTarget(request.to),
request.deadline >= block.timestamp,
isValid && recovered == request.from,
recovered
);
}
/**
* @dev Returns a tuple with the recovered the signer of an EIP712 forward request message hash
* and a boolean indicating if the signature is valid.
*
* NOTE: The signature is considered valid if {ECDSA-tryRecover} indicates no recover error for it.
*/
function _recoverForwardRequestSigner(
ForwardRequestData calldata request
) internal view virtual returns (bool isValid, address signer) {
(address recovered, ECDSA.RecoverError err, ) = _hashTypedDataV4(
keccak256(
abi.encode(
_FORWARD_REQUEST_TYPEHASH,
request.from,
request.to,
request.value,
request.gas,
nonces(request.from),
request.deadline,
keccak256(request.data)
)
)
).tryRecover(request.signature);
return (err == ECDSA.RecoverError.NoError, recovered);
}
/**
* @dev Validates and executes a signed request returning the request call `success` value.
*
* Internal function without msg.value validation.
*
* Requirements:
*
* - The caller must have provided enough gas to forward with the call.
* - The request must be valid (see {verify}) if the `requireValidRequest` is true.
*
* Emits an {ExecutedForwardRequest} event.
*
* IMPORTANT: Using this function doesn't check that all the `msg.value` was sent, potentially
* leaving value stuck in the contract.
*/
function _execute(
ForwardRequestData calldata request,
bool requireValidRequest
) internal virtual returns (bool success) {
(bool isTrustedForwarder, bool active, bool signerMatch, address signer) = _validate(request);
// Need to explicitly specify if a revert is required since non-reverting is default for
// batches and reversion is opt-in since it could be useful in some scenarios
if (requireValidRequest) {
if (!isTrustedForwarder) {
revert ERC2771UntrustfulTarget(request.to, address(this));
}
if (!active) {
revert ERC2771ForwarderExpiredRequest(request.deadline);
}
if (!signerMatch) {
revert ERC2771ForwarderInvalidSigner(signer, request.from);
}
}
// Ignore an invalid request because requireValidRequest = false
if (isTrustedForwarder && signerMatch && active) {
// Nonce should be used before the call to prevent reusing by reentrancy
uint256 currentNonce = _useNonce(signer);
uint256 reqGas = request.gas;
address to = request.to;
uint256 value = request.value;
bytes memory data = abi.encodePacked(request.data, request.from);
uint256 gasLeft;
assembly ("memory-safe") {
success := call(reqGas, to, value, add(data, 0x20), mload(data), 0, 0)
gasLeft := gas()
}
_checkForwardedGas(gasLeft, request);
emit ExecutedForwardRequest(signer, currentNonce, success);
}
}
/**
* @dev Returns whether the target trusts this forwarder.
*
* This function performs a static call to the target contract calling the
* {ERC2771Context-isTrustedForwarder} function.
*
* NOTE: Consider the execution of this forwarder is permissionless. Without this check, anyone may transfer assets
* that are owned by, or are approved to this forwarder.
*/
function _isTrustedByTarget(address target) internal view virtual returns (bool) {
bytes memory encodedParams = abi.encodeCall(ERC2771Context.isTrustedForwarder, (address(this)));
bool success;
uint256 returnSize;
uint256 returnValue;
assembly ("memory-safe") {
// Perform the staticcall and save the result in the scratch space.
// | Location | Content | Content (Hex) |
// |-----------|----------|--------------------------------------------------------------------|
// | | | result ↓ |
// | 0x00:0x1F | selector | 0x0000000000000000000000000000000000000000000000000000000000000001 |
success := staticcall(gas(), target, add(encodedParams, 0x20), mload(encodedParams), 0, 0x20)
returnSize := returndatasize()
returnValue := mload(0)
}
return success && returnSize >= 0x20 && returnValue > 0;
}
/**
* @dev Checks if the requested gas was correctly forwarded to the callee.
*
* As a consequence of https://eips.ethereum.org/EIPS/eip-150[EIP-150]:
* - At most `gasleft() - floor(gasleft() / 64)` is forwarded to the callee.
* - At least `floor(gasleft() / 64)` is kept in the caller.
*
* It reverts consuming all the available gas if the forwarded gas is not the requested gas.
*
* IMPORTANT: The `gasLeft` parameter should be measured exactly at the end of the forwarded call.
* Any gas consumed in between will make room for bypassing this check.
*/
function _checkForwardedGas(uint256 gasLeft, ForwardRequestData calldata request) private pure {
// To avoid insufficient gas griefing attacks, as referenced in https://ronan.eth.limo/blog/ethereum-gas-dangers/
//
// A malicious relayer can attempt to shrink the gas forwarded so that the underlying call reverts out-of-gas
// but the forwarding itself still succeeds. In order to make sure that the subcall received sufficient gas,
// we will inspect gasleft() after the forwarding.
//
// Let X be the gas available before the subcall, such that the subcall gets at most X * 63 / 64.
// We can't know X after CALL dynamic costs, but we want it to be such that X * 63 / 64 >= req.gas.
// Let Y be the gas used in the subcall. gasleft() measured immediately after the subcall will be gasleft() = X - Y.
// If the subcall ran out of gas, then Y = X * 63 / 64 and gasleft() = X - Y = X / 64.
// Under this assumption req.gas / 63 > gasleft() is true if and only if
// req.gas / 63 > X / 64, or equivalently req.gas > X * 63 / 64.
// This means that if the subcall runs out of gas we are able to detect that insufficient gas was passed.
//
// We will now also see that req.gas / 63 > gasleft() implies that req.gas >= X * 63 / 64.
// The contract guarantees Y <= req.gas, thus gasleft() = X - Y >= X - req.gas.
// - req.gas / 63 > gasleft()
// - req.gas / 63 >= X - req.gas
// - req.gas >= X * 63 / 64
// In other words if req.gas < X * 63 / 64 then req.gas / 63 <= gasleft(), thus if the relayer behaves honestly
// the forwarding does not revert.
if (gasLeft < request.gas / 63) {
// We explicitly trigger invalid opcode to consume all gas and bubble-up the effects, since
// neither revert or assert consume all gas since Solidity 0.8.20
// https://docs.soliditylang.org/en/v0.8.20/control-structures.html#panic-via-assert-and-error-via-require
assembly ("memory-safe") {
invalid()
}
}
}
}
"
},
"@openzeppelin/contracts/utils/Address.sol": {
"content": "// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.2.0) (utils/Address.sol)
pragma solidity ^0.8.20;
import {Errors} from "./Errors.sol";
/**
* @dev Collection of functions related to the address type
*/
library Address {
/**
* @dev There's no code at `target` (it is not a contract).
*/
error AddressEmptyCode(address target);
/**
* @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.20/security-considerations.html#use-the-checks-effects-interactions-pattern[checks-effects-interactions pattern].
*/
function sendValue(address payable recipient, uint256 amount) internal {
if (address(this).balance < amount) {
revert Errors.InsufficientBalance(address(this).balance, amount);
}
(bool success, bytes memory returndata) = recipient.call{value: amount}("");
if (!success) {
_revert(returndata);
}
}
/**
* @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 or custom error, it is bubbled
* up by this function (like regular Solidity function calls). However, if
* the call reverted with no returned reason, this function reverts with a
* {Errors.FailedCall} error.
*
* 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.
*/
function functionCall(address target, bytes memory data) internal returns (bytes memory) {
return functionCallWithValue(target, data, 0);
}
/**
* @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`.
*/
function functionCallWithValue(address target, bytes memory data, uint256 value) internal returns (bytes memory) {
if (address(this).balance < value) {
revert Errors.InsufficientBalance(address(this).balance, value);
}
(bool success, bytes memory returndata) = target.call{value: value}(data);
return verifyCallResultFromTarget(target, success, returndata);
}
/**
* @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
* but performing a static call.
*/
function functionStaticCall(address target, bytes memory data) internal view returns (bytes memory) {
(bool success, bytes memory returndata) = target.staticcall(data);
return verifyCallResultFromTarget(target, success, returndata);
}
/**
* @dev Same as {xref-Address-functionCall-address-bytes-}[`functionCall`],
* but performing a delegate call.
*/
function functionDelegateCall(address target, bytes memory data) internal returns (bytes memory) {
(bool success, bytes memory returndata) = target.delegatecall(data);
return verifyCallResultFromTarget(target, success, returndata);
}
/**
* @dev Tool to verify that a low level call to smart-contract was successful, and reverts if the target
* was not a contract or bubbling up the revert reason (falling back to {Errors.FailedCall}) in case
* of an unsuccessful call.
*/
function verifyCallResultFromTarget(
address target,
bool success,
bytes memory returndata
) internal view returns (bytes memory) {
if (!success) {
_revert(returndata);
} else {
// only check if target is a contract if the call was successful and the return data is empty
// otherwise we already know that it was a contract
if (returndata.length == 0 && target.code.length == 0) {
revert AddressEmptyCode(target);
}
return returndata;
}
}
/**
* @dev Tool to verify that a low level call was successful, and reverts if it wasn't, either by bubbling the
* revert reason or with a default {Errors.FailedCall} error.
*/
function verifyCallResult(bool success, bytes memory returndata) internal pure returns (bytes memory) {
if (!success) {
_revert(returndata);
} else {
return returndata;
}
}
/**
* @dev Reverts with returndata if present. Otherwise reverts with {Errors.FailedCall}.
*/
function _revert(bytes memory returndata) 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
assembly ("memory-safe") {
let returndata_size := mload(returndata)
revert(add(32, returndata), returndata_size)
}
} else {
revert Errors.FailedCall();
}
}
}
"
},
"@openzeppelin/contracts/utils/Context.sol": {
"content": "// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.0.1) (utils/Context.sol)
pragma solidity ^0.8.20;
/**
* @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;
}
function _contextSuffixLength() internal view virtual returns (uint256) {
return 0;
}
}
"
},
"@openzeppelin/contracts/utils/cryptography/ECDSA.sol": {
"content": "// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.1.0) (utils/cryptography/ECDSA.sol)
pragma solidity ^0.8.20;
/**
* @dev Elliptic Curve Digital Signature Algorithm (ECDSA) operations.
*
* These functions can be used to verify that a message was signed by the holder
* of the private keys of a given address.
*/
library ECDSA {
enum RecoverError {
NoError,
InvalidSignature,
InvalidSignatureLength,
InvalidSignatureS
}
/**
* @dev The signature derives the `address(0)`.
*/
error ECDSAInvalidSignature();
/**
* @dev The signature has an invalid length.
*/
error ECDSAInvalidSignatureLength(uint256 length);
/**
* @dev The signature has an S value that is in the upper half order.
*/
error ECDSAInvalidSignatureS(bytes32 s);
/**
* @dev Returns the address that signed a hashed message (`hash`) with `signature` or an error. This will not
* return address(0) without also returning an error description. Errors are documented using an enum (error type)
* and a bytes32 providing additional information about the error.
*
* If no error is returned, then the address can be used for verification purposes.
*
* The `ecrecover` EVM precompile allows for malleable (non-unique) signatures:
* this function rejects them by requiring the `s` value to be in the lower
* half order, and the `v` value to be either 27 or 28.
*
* IMPORTANT: `hash` _must_ be the result of a hash operation for the
* verification to be secure: it is possible to craft signatures that
* recover to arbitrary addresses for non-hashed data. A safe way to ensure
* this is by receiving a hash of the original message (which may otherwise
* be too long), and then calling {MessageHashUtils-toEthSignedMessageHash} on it.
*
* Documentation for signature generation:
* - with https://web3js.readthedocs.io/en/v1.3.4/web3-eth-accounts.html#sign[Web3.js]
* - with https://docs.ethers.io/v5/api/signer/#Signer-signMessage[ethers]
*/
function tryRecover(
bytes32 hash,
bytes memory signature
) internal pure returns (address recovered, RecoverError err, bytes32 errArg) {
if (signature.length == 65) {
bytes32 r;
bytes32 s;
uint8 v;
// ecrecover takes the signature parameters, and the only way to get them
// currently is to use assembly.
assembly ("memory-safe") {
r := mload(add(signature, 0x20))
s := mload(add(signature, 0x40))
v := byte(0, mload(add(signature, 0x60)))
}
return tryRecover(hash, v, r, s);
} else {
return (address(0), RecoverError.InvalidSignatureLength, bytes32(signature.length));
}
}
/**
* @dev Returns the address that signed a hashed message (`hash`) with
* `signature`. This address can then be used for verification purposes.
*
* The `ecrecover` EVM precompile allows for malleable (non-unique) signatures:
* this function rejects them by requiring the `s` value to be in the lower
* half order, and the `v` value to be either 27 or 28.
*
* IMPORTANT: `hash` _must_ be the result of a hash operation for the
* verification to be secure: it is possible to craft signatures that
* recover to arbitrary addresses for non-hashed data. A safe way to ensure
* this is by receiving a hash of the original message (which may otherwise
* be too long), and then calling {MessageHashUtils-toEthSignedMessageHash} on it.
*/
function recover(bytes32 hash, bytes memory signature) internal pure returns (address) {
(address recovered, RecoverError error, bytes32 errorArg) = tryRecover(hash, signature);
_throwError(error, errorArg);
return recovered;
}
/**
* @dev Overload of {ECDSA-tryRecover} that receives the `r` and `vs` short-signature fields separately.
*
* See https://eips.ethereum.org/EIPS/eip-2098[ERC-2098 short signatures]
*/
function tryRecover(
bytes32 hash,
bytes32 r,
bytes32 vs
) internal pure returns (address recovered, RecoverError err, bytes32 errArg) {
unchecked {
bytes32 s = vs & bytes32(0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff);
// We do not check for an overflow here since the shift operation results in 0 or 1.
uint8 v = uint8((uint256(vs) >> 255) + 27);
return tryRecover(hash, v, r, s);
}
}
/**
* @dev Overload of {ECDSA-recover} that receives the `r and `vs` short-signature fields separately.
*/
function recover(bytes32 hash, bytes32 r, bytes32 vs) internal pure returns (address) {
(address recovered, RecoverError error, bytes32 errorArg) = tryRecover(hash, r, vs);
_throwError(error, errorArg);
return recovered;
}
/**
* @dev Overload of {ECDSA-tryRecover} that receives the `v`,
* `r` and `s` signature fields separately.
*/
function tryRecover(
bytes32 hash,
uint8 v,
bytes32 r,
bytes32 s
) internal pure returns (address recovered, RecoverError err, bytes32 errArg) {
// EIP-2 still allows signature malleability for ecrecover(). Remove this possibility and make the signature
// unique. Appendix F in the Ethereum Yellow paper (https://ethereum.github.io/yellowpaper/paper.pdf), defines
// the valid range for s in (301): 0 < s < secp256k1n ÷ 2 + 1, and for v in (302): v ∈ {27, 28}. Most
// signatures from current libraries generate a unique signature with an s-value in the lower half order.
//
// If your library generates malleable signatures, such as s-values in the upper range, calculate a new s-value
// with 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 - s1 and flip v from 27 to 28 or
// vice versa. If your library also generates signatures with 0/1 for v instead 27/28, add 27 to v to accept
// these malleable signatures as well.
if (uint256(s) > 0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF5D576E7357A4501DDFE92F46681B20A0) {
return (address(0), RecoverError.InvalidSignatureS, s);
}
// If the signature is valid (and not malleable), return the signer address
address signer = ecrecover(hash, v, r, s);
if (signer == address(0)) {
return (address(0), RecoverError.InvalidSignature, bytes32(0));
}
return (signer, RecoverError.NoError, bytes32(0));
}
/**
* @dev Overload of {ECDSA-recover} that receives the `v`,
* `r` and `s` signature fields separately.
*/
function recover(bytes32 hash, uint8 v, bytes32 r, bytes32 s) internal pure returns (address) {
(address recovered, RecoverError error, bytes32 errorArg) = tryRecover(hash, v, r, s);
_throwError(error, errorArg);
return recovered;
}
/**
* @dev Optionally reverts with the corresponding custom error according to the `error` argument provided.
*/
function _throwError(RecoverError error, bytes32 errorArg) private pure {
if (error == RecoverError.NoError) {
return; // no error: do nothing
} else if (error == RecoverError.InvalidSignature) {
revert ECDSAInvalidSignature();
} else if (error == RecoverError.InvalidSignatureLength) {
revert ECDSAInvalidSignatureLength(uint256(errorArg));
} else if (error == RecoverError.InvalidSignatureS) {
revert ECDSAInvalidSignatureS(errorArg);
}
}
}
"
},
"@openzeppelin/contracts/utils/cryptography/EIP712.sol": {
"content": "// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.3.0) (utils/cryptography/EIP712.sol)
pragma solidity ^0.8.20;
import {MessageHashUtils} from "./MessageHashUtils.sol";
import {ShortStrings, ShortString} from "../ShortStrings.sol";
import {IERC5267} from "../../interfaces/IERC5267.sol";
/**
* @dev https://eips.ethereum.org/EIPS/eip-712[EIP-712] is a standard for hashing and signing of typed structured data.
*
* The encoding scheme specified in the EIP requires a domain separator and a hash of the typed structured data, whose
* encoding is very generic and therefore its implementation in Solidity is not feasible, thus this contract
* does not implement the encoding itself. Protocols need to implement the type-specific encoding they need in order to
* produce the hash of their typed data using a combination of `abi.encode` and `keccak256`.
*
* This contract implements the EIP-712 domain separator ({_domainSeparatorV4}) that is used as part of the encoding
* scheme, and the final step of the encoding to obtain the message digest that is then signed via ECDSA
* ({_hashTypedDataV4}).
*
* The implementation of the domain separator was designed to be as efficient as possible while still properly updating
* the chain id to protect against replay attacks on an eventual fork of the chain.
*
* NOTE: This contract implements the version of the encoding known as "v4", as implemented by the JSON RPC method
* https://docs.metamask.io/guide/signing-data.html[`eth_signTypedDataV4` in MetaMask].
*
* NOTE: In the upgradeable version of this contract, the cached values will correspond to the address, and the domain
* separator of the implementation contract. This will cause the {_domainSeparatorV4} function to always rebuild the
* separator from the immutable values, which is cheaper than accessing a cached version in cold storage.
*
* @custom:oz-upgrades-unsafe-allow state-variable-immutable
*/
abstract contract EIP712 is IERC5267 {
using ShortStrings for *;
bytes32 private constant TYPE_HASH =
keccak256("EIP712Domain(string name,string version,uint256 chainId,address verifyingContract)");
// Cache the domain separator as an immutable value, but also store the chain id that it corresponds to, in order to
// invalidate the cached domain separator if the chain id changes.
bytes32 private immutable _cachedDomainSeparator;
uint256 private immutable _cachedChainId;
address private immutable _cachedThis;
bytes32 private immutable _hashedName;
bytes32 private immutable _hashedVersion;
ShortString private immutable _name;
ShortString private immutable _version;
// slither-disable-next-line constable-states
string private _nameFallback;
// slither-disable-next-line constable-states
string private _versionFallback;
/**
* @dev Initializes the domain separator and parameter caches.
*
* The meaning of `name` and `version` is specified in
* https://eips.ethereum.org/EIPS/eip-712#definition-of-domainseparator[EIP-712]:
*
* - `name`: the user readable name of the signing domain, i.e. the name of the DApp or the protocol.
* - `version`: the current major version of the signing domain.
*
* NOTE: These parameters cannot be changed except through a xref:learn::upgrading-smart-contracts.adoc[smart
* contract upgrade].
*/
constructor(string memory name, string memory version) {
_name = name.toShortStringWithFallback(_nameFallback);
_version = version.toShortStringWithFallback(_versionFallback);
_hashedName = keccak256(bytes(name));
_hashedVersion = keccak256(bytes(version));
_cachedChainId = block.chainid;
_cachedDomainSeparator = _buildDomainSeparator();
_cachedThis = address(this);
}
/**
* @dev Returns the domain separator for the current chain.
*/
function _domainSeparatorV4() internal view returns (bytes32) {
if (address(this) == _cachedThis && block.chainid == _cachedChainId) {
return _cachedDomainSeparator;
} else {
return _buildDomainSeparator();
}
}
function _buildDomainSeparator() private view returns (bytes32) {
return keccak256(abi.encode(TYPE_HASH, _hashedName, _hashedVersion, block.chainid, address(this)));
}
/**
* @dev Given an already https://eips.ethereum.org/EIPS/eip-712#definition-of-hashstruct[hashed struct], this
* function returns the hash of the fully encoded EIP712 message for this domain.
*
* This hash can be used together with {ECDSA-recover} to obtain the signer of a message. For example:
*
* ```solidity
* bytes32 digest = _hashTypedDataV4(keccak256(abi.encode(
* keccak256("Mail(address to,string contents)"),
* mailTo,
* keccak256(bytes(mailContents))
* )));
* address signer = ECDSA.recover(digest, signature);
* ```
*/
function _hashTypedDataV4(bytes32 structHash) internal view virtual returns (bytes32) {
return MessageHashUtils.toTypedDataHash(_domainSeparatorV4(), structHash);
}
/**
* @inheritdoc IERC5267
*/
function eip712Domain()
public
view
virtual
returns (
bytes1 fields,
string memory name,
string memory version,
uint256 chainId,
address verifyingContract,
bytes32 salt,
uint256[] memory extensions
)
{
return (
hex"0f", // 01111
_EIP712Name(),
_EIP712Version(),
block.chainid,
address(this),
bytes32(0),
new uint256[](0)
);
}
/**
* @dev The name parameter for the EIP712 domain.
*
* NOTE: By default this function reads _name which is an immutable value.
* It only reads from storage if necessary (in case the value is too large to fit in a ShortString).
*/
// solhint-disable-next-line func-name-mixedcase
function _EIP712Name() internal view returns (string memory) {
return _name.toStringWithFallback(_nameFallback);
}
/**
* @dev The version parameter for the EIP712 domain.
*
* NOTE: By default this function reads _version which is an immutable value.
* It only reads from storage if necessary (in case the value is too large to fit in a ShortString).
*/
// solhint-disable-next-line func-name-mixedcase
function _EIP712Version() internal view returns (string memory) {
return _version.toStringWithFallback(_versionFallback);
}
}
"
},
"@openzeppelin/contracts/utils/cryptography/MessageHashUtils.sol": {
"content": "// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.3.0) (utils/cryptography/MessageHashUtils.sol)
pragma solidity ^0.8.20;
import {Strings} from "../Strings.sol";
/**
* @dev Signature message hash utilities for producing digests to be consumed by {ECDSA} recovery or signing.
*
* The library provides methods for generating a hash of a message that conforms to the
* https://eips.ethereum.org/EIPS/eip-191[ERC-191] and https://eips.ethereum.org/EIPS/eip-712[EIP 712]
* specifications.
*/
library MessageHashUtils {
/**
* @dev Returns the keccak256 digest of an ERC-191 signed data with version
* `0x45` (`personal_sign` messages).
*
* The digest is calculated by prefixing a bytes32 `messageHash` with
* `"\x19Ethereum Signed Message:\
32"` and hashing the result. It corresponds with the
* hash signed when using the https://ethereum.org/en/developers/docs/apis/json-rpc/#eth_sign[`eth_sign`] JSON-RPC method.
*
* NOTE: The `messageHash` parameter is intended to be the result of hashing a raw message with
* keccak256, although any bytes32 value can be safely used because the final digest will
* be re-hashed.
*
* See {ECDSA-recover}.
*/
function toEthSignedMessageHash(bytes32 messageHash) internal pure returns (bytes32 digest) {
assembly ("memory-safe") {
mstore(0x00, "\x19Ethereum Signed Message:\
32") // 32 is the bytes-length of messageHash
mstore(0x1c, messageHash) // 0x1c (28) is the length of the prefix
digest := keccak256(0x00, 0x3c) // 0x3c is the length of the prefix (0x1c) + messageHash (0x20)
}
}
/**
* @dev Returns the keccak256 digest of an ERC-191 signed data with version
* `0x45` (`personal_sign` messages).
*
* The digest is calculated by prefixing an arbitrary `message` with
* `"\x19Ethereum Signed Message:\
" + len(message)` and hashing the result. It corresponds with the
* hash signed when using the https://ethereum.org/en/developers/docs/apis/json-rpc/#eth_sign[`eth_sign`] JSON-RPC method.
*
* See {ECDSA-recover}.
*/
function toEthSignedMessageHash(bytes memory message) internal pure returns (bytes32) {
return
keccak256(bytes.concat("\x19Ethereum Signed Message:\
", bytes(Strings.toString(message.length)), message));
}
/**
* @dev Returns the keccak256 digest of an ERC-191 signed data with version
* `0x00` (data with intended validator).
*
* The digest is calculated by prefixing an arbitrary `data` with `"\x19\x00"` and the intended
* `validator` address. Then hashing the result.
*
* See {ECDSA-recover}.
*/
function toDataWithIntendedValidatorHash(address validator, bytes memory data) internal pure returns (bytes32) {
return keccak256(abi.encodePacked(hex"19_00", validator, data));
}
/**
* @dev Variant of {toDataWithIntendedValidatorHash-address-bytes} optimized for cases where `data` is a bytes32.
*/
function toDataWithIntendedValidatorHash(
address validator,
bytes32 messageHash
) internal pure returns (bytes32 digest) {
assembly ("memory-safe") {
mstore(0x00, hex"19_00")
mstore(0x02, shl(96, validator))
mstore(0x16, messageHash)
digest := keccak256(0x00, 0x36)
}
}
/**
* @dev Returns the keccak256 digest of an EIP-712 typed data (ERC-191 version `0x01`).
*
* The digest is calculated from a `domainSeparator` and a `structHash`, by prefixing them with
* `\x19\x01` and hashing the result. It corresponds to the hash signed by the
* https://eips.ethereum.org/EIPS/eip-712[`eth_signTypedData`] JSON-RPC method as part of EIP-712.
*
* See {ECDSA-recover}.
*/
function toTypedDataHash(bytes32 domainSeparator, bytes32 structHash) internal pure returns (bytes32 digest) {
assembly ("memory-safe") {
let ptr := mload(0x40)
mstore(ptr, hex"19_01")
mstore(add(ptr, 0x02), domainSeparator)
mstore(add(ptr, 0x22), structHash)
digest := keccak256(ptr, 0x42)
}
}
}
"
},
"@openzeppelin/contracts/utils/Errors.sol": {
"content": "// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.1.0) (utils/Errors.sol)
pragma solidity ^0.8.20;
/**
* @dev Collection of common custom errors used in multiple contracts
*
* IMPORTANT: Backwards compatibility is not guaranteed in future versions of the library.
* It is recommended to avoid relying on the error API for critical functionality.
*
* _Available since v5.1._
*/
library Errors {
/**
* @dev The ETH balance of the account is not enough to perform the operation.
*/
error InsufficientBalance(uint256 balance, uint256 needed);
/**
* @dev A call to an address target failed. The target may have reverted.
*/
error FailedCall();
/**
* @dev The deployment failed.
*/
error FailedDeployment();
/**
* @dev A necessary precompile is missing.
*/
error MissingPrecompile(address);
}
"
},
"@openzeppelin/contracts/utils/math/Math.sol": {
"content": "// SPDX-License-Identifier: MIT
// OpenZeppelin Contracts (last updated v5.3.0) (utils/math/Math.sol)
pragma solidity ^0.8.20;
import {Panic} from "../Panic.sol";
import {SafeCast} from "./SafeCast.sol";
/**
* @dev Standard math utilities missing in the Solidity language.
*/
library Math {
enum Rounding {
Floor, // Toward negative infinity
Ceil, // Toward positive infinity
Trunc, // Toward zero
Expand // Away from zero
}
/**
* @dev Return the 512-bit addition of two uint256.
*
* The result is stored in two 256 variables such that sum = high * 2²⁵⁶ + low.
*/
function add512(uint256 a, uint256 b) internal pure returns (uint256 high, uint256 low) {
assembly ("memory-safe") {
low := add(a, b)
high := lt(low, a)
}
}
/**
* @dev Return the 512-bit multiplication of two uint256.
*
* The result is stored in two 256 variables such that product = high * 2²⁵⁶ + low.
*/
function mul512(uint256 a, uint256 b) internal pure returns (uint256 high, uint256 low) {
// 512-bit multiply [high low] = x * y. Compute the product mod 2²⁵⁶ and mod 2²⁵⁶ - 1, then use
// the Chinese Remainder Theorem to reconstruct the 512 bit result. The result is stored in two 256
// variables such that product = high * 2²⁵⁶ + low.
assembly ("memory-safe") {
let mm := mulmod(a, b, not(0))
low := mul(a, b)
high := sub(sub(mm, low), lt(mm, low))
}
}
/**
* @dev Returns the addition of two unsigned integers, with a success flag (no overflow).
*/
function tryAdd(uint256 a, uint256 b) internal pure returns (bool success, uint256 result) {
unchecked {
uint256 c = a + b;
success = c >= a;
result = c * SafeCast.toUint(success);
}
}
/**
* @dev Returns the subtraction of two unsigned integers, with a success flag (no overflow).
*/
function trySub(uint256 a, uint256 b) internal pure returns (bool success, uint256 result) {
unchecked {
uint256 c = a - b;
success = c <= a;
result = c * SafeCast.toUint(success);
}
}
/**
* @dev Returns the multiplication of two unsigned integers, with a success flag (no overflow).
*/
function tryMul(uint256 a, uint256 b) internal pure returns (bool success, uint256 result) {
unchecked {
uint256 c = a * b;
assembly ("memory-safe") {
// Only true when the multiplication doesn't overflow
// (c / a == b) || (a == 0)
success := or(eq(div(c, a), b), iszero(a))
}
// equivalent to: success ? c : 0
result = c * SafeCast.toUint(success);
}
}
/**
* @dev Returns the division of two unsigned integers, with a success flag (no division by zero).
*/
function tryDiv(uint256 a, uint256 b) internal pure returns (bool success, uint256 result) {
unchecked {
success = b > 0;
assembly ("memory-safe") {
// The `DIV` opcode returns zero when the denominator is 0.
result := div(a, b)
}
}
}
/**
* @dev Returns the remainder of dividing two unsigned integers, with a success flag (no division by zero).
*/
function tryMod(uint256 a, uint256 b) internal pure returns (bool success, uint256 result) {
unchecked {
success = b > 0;
assembly ("memory-safe") {
// The `MOD` opcode returns zero when the denominator is 0.
result := mod(a, b)
}
}
}
/**
* @dev Unsigned saturating addition, bounds to `2²⁵⁶ - 1` instead of overflowing.
*/
function saturatingAdd(uint256 a, uint256 b) internal pure returns (uint256) {
(bool success, uint256 result) = tryAdd(a, b);
return ternary(success, result, type(uint256).max);
}
/**
* @dev Unsigned saturating subtraction, bounds to zero instead of overflowing.
*/
function saturatingSub(uint256 a, uint256 b) internal pure returns (uint256) {
(, uint256 result) = trySub(a, b);
return result;
}
/**
* @dev Unsigned saturating multiplication, bounds to `2²⁵⁶ - 1` instead of overflowing.
*/
function saturatingMul(uint256 a, uint256 b) internal pure returns (uint256) {
(bool success, uint256 result) = tryMul(a, b);
return ternary(success, result, type(uint256).max);
}
/**
* @dev Branchless ternary evaluation for `a ? b : c`. Gas costs are constant.
*
* IMPORTANT: This function may reduce bytecode size and consume less gas when used standalone.
* However, the compiler may optimize Solidity ternary operations (i.e. `a ? b : c`) to only compute
* one branch when needed, making this function more expensive.
*/
function ternary(bool condition, uint256 a, uint256 b) internal pure returns (uint256) {
unchecked {
// branchless ternary works because:
// b ^ (a ^ b) == a
// b ^ 0 == b
return b ^ ((a ^ b) * SafeCast.toUint(condition));
}
}
/**
* @dev Returns the largest of two numbers.
*/
function max(uint256 a, uint256 b) internal pure returns (uint256) {
return ternary(a > b, a, b);
}
/**
* @dev Returns the smallest of two numbers.
*/
function min(uint256 a, uint256 b) internal pure returns (uint256) {
return ternary(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 towards infinity instead
* of rounding towards zero.
*/
function ceilDiv(uint256 a, uint256 b) internal pure returns (uint256) {
if (b == 0) {
// Guarantee the same behavior as in a regular Solidity division.
Panic.panic(Panic.DIVISION_BY_ZERO);
}
// The following calculation ensures accurate ceiling division without overflow.
// Since a is non-zero, (a - 1) / b will not overflow.
// The largest possible result occurs when (a - 1) / b is type(uint256).max,
// but the largest value we can obtain is type(uint256).max - 1, which happens
// when a = type(uint256).max and b = 1.
unchecked {
return SafeCast.toUint(a > 0) * ((a - 1) / b + 1);
}
}
/**
* @dev Calculates floor(x * y / denominator) with full precision. Throws if result overflows a uint256 or
* denominator == 0.
*
* 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 {
(uint256 high, uint256 low) = mul512(x, y);
// Handle non-overflow cases, 256 by 256 division.
if (high == 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 low / denominator;
}
// Make sure the result is less than 2²⁵⁶. Also prevents denominator == 0.
if (denominator <= high) {
Panic.panic(ternary(denominator == 0, Panic.DIVISION_BY_ZERO, Panic.UNDER_OVERFLOW));
}
///////////////////////////////////////////////
// 512 by 256 division.
///////////////////////////////////////////////
// Make division exact by subtracting the remainder from [high low].
uint256 remainder;
assembly ("memory-safe") {
// Compute remainder using mulmod.
remainder := mulmod(x, y, denominator)
// Subtract 256 bit number from 512 bit number.
high := sub(high, gt(remainder, low))
low := sub(low, 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.
uint256 twos = denominator & (0 - denominator);
assembly ("memory-safe") {
// Divide denominator by twos.
denominator := div(denominator, twos)
// Divide [high low] by twos.
low := div(low, twos)
// Flip twos such that it is 2²⁵⁶ / twos. If twos is zero, then it becomes one.
twos := add(div(sub(0, twos), twos), 1)
}
// Shift in bits from high into low.
low |= high * twos;
// Invert denominator mod 2²⁵⁶. Now that denominator is an odd number, it has an inverse modulo 2²⁵⁶ such
// that denominator * inv ≡ 1 mod 2²⁵⁶. Compute the inverse by starting with a seed that is correct for
// four bits. That is, denominator * inv ≡ 1 mod 2⁴.
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⁸
inverse *= 2 - denominator * inverse; // inverse mod 2¹⁶
inverse *= 2 - denominator * inverse; // inverse mod 2³²
inverse *= 2 - denominator * inverse; // inverse mod 2⁶⁴
inverse *= 2 - denominator * inverse; // inverse mod 2¹²⁸
inverse *= 2 - denominator * inverse; // inverse mod 2²⁵⁶
// 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²⁵⁶. Since the preconditions guarantee that the outcome is
// less than 2²⁵⁶, this is the final result. We don't need to compute the high bits of the result and high
// is no longer required.
result = low * inverse;
return result;
}
}
/**
* @dev 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) {
return mulDiv(x, y, denominator) + SafeCast.toUint(unsignedRoundsUp(rounding) && mulmod(x, y, denominator) > 0);
}
/**
* @dev Calculates floor(x * y >> n) with full precision. Throws if result overflows a uint256.
*/
function mulShr(uint256 x, uint256 y, uint8 n) internal pure returns (uint256 result) {
unchecked {
(uint256 high, uint256 low) = mul512(x, y);
if (high >= 1 << n) {
Panic.panic(Panic.UNDER_OVERFLOW);
}
return (high << (256 - n)) | (low >> n);
}
}
/**
* @dev Calculates x * y >> n with full precision, following the selected rounding direction.
*/
function mulShr(uint256 x, uint256 y, uint8 n, Rounding rounding) internal pure returns (uint256) {
return mulShr(x, y, n) + SafeCast.toUint(unsignedRoundsUp(rounding) && mulmod(x, y, 1 << n) > 0);
}
/**
* @dev Calculate the modular multiplicative inverse of a number in Z/nZ.
*
* If n is a prime, then Z/nZ is a field. In that case all elements are inversible, except 0.
* If n is not a prime, then Z/nZ is not a field, and some elements might not be inversible.
*
* If the input value is not inversible, 0 is returned.
*
* NOTE: If you know for sure that n is (big) a prime, it may be cheaper to use Fermat's little theorem and get the
* inverse using `Math.modExp(a, n - 2, n)`. See {invModPrime}.
*/
function invMod(uint256 a, uint256 n) internal pure returns (uint256) {
unchecked {
if (n == 0) return 0;
// The inverse modulo is calculated using the Extended Euclidean Algorithm (iterative version)
// Used to compute integers x and y such that: ax + ny = gcd(a, n).
// When the gcd is 1, then the inverse of a modulo n exists and it's x.
// ax + ny = 1
// ax = 1 + (-y)n
// ax ≡ 1 (mod n) # x is the inverse of a modulo n
// If the remainder is 0 the gcd is n right away.
uint256 remainder = a % n;
uint256 gcd = n;
// Therefore the initial coefficients are:
// ax + ny = gcd(a, n) = n
// 0a + 1n = n
int256 x = 0;
int256 y = 1;
while (remainder != 0) {
uint256 quotient = gcd / remainder;
(gcd, remainder) = (
// The old remainder is the next gcd to try.
remainder,
// Compute the next remainder.
// Can't overflow given that (a % gcd) * (gcd // (a % gcd)) <= gcd
// where gcd is at most n (capped to type(uint256).max)
gcd - remainder * quotient
);
(x, y) = (
// Increment the coefficient of a.
y,
// Decrement the coefficient of n.
// Can overflow, but the result is casted to uint256 so that the
// next value of y is "wrapped around" to a value between 0 and n - 1.
x - y * int256(quotient)
);
}
if (gcd != 1) return 0; // No inverse exists.
return ternary(x < 0, n - uint256(-x), uint256(x)); // Wrap the result if it's negative.
}
}
/**
* @dev Variant of {invMod}. More efficient, but only works if `p` is known to be a prime greater than `2`.
*
* From https://en.wikipedia.org/wiki/Fermat%27s_little_theorem[Fermat's little theorem], we know that if p is
* prime, then `a**(p-1) ≡ 1 mod p`. As a consequence, we have `a * a**(p-2) ≡ 1 mod p`, which means that
* `a**(p-2)` is the modular multiplicative inverse of a in Fp.
*
* NOTE: this function does NOT check that `p` is a prime greater than `2`.
*/
funSubmitted on: 2025-09-22 16:01:31
Comments
Log in to comment.
No comments yet.