EIP-4762: Statelessness gas cost changes
Changes the gas schedule to reflect the costs of creating a witness by requiring clients update their database layout to match.
Abstract
This EIP introduces changes in the gas schedule to reflect the costs of creating a witness. It requires clients to update their database layout to match this, so as to avoid potential DoS attacks.
Motivation
The introduction of Verkle trees into Ethereum requires fundamental changes and as a preparation, this EIP is targeting the fork coming right before the verkle tree fork, in order to incentivize Dapp developers to adopt the new storage model, and ample time to adjust to it. It also incentivizes client developers to migrate their database format ahead of the verkle fork.
Specification
Helper functions
Access events
Whenever the state is read, one or more of the access events of the form(address, sub_key, leaf_key)
take place, determining what data is being accessed. We define access events as follows:
Access events for account headers
When:
- a non-precompile which is also not a system contract is the target of a
*CALL
,SELFDESTRUCT
,EXTCODESIZE
, orEXTCODECOPY
opcode, - a non-precompile which is also not a system contract is the target address of a contract creation whose initcode starts execution,
- any address is the target of the
BALANCE
opcode - a deployed contract calls
CODECOPY
process this access event:
Note: a non-value-bearing SELFDESTRUCT
or *CALL
, targetting a precompile or a system contract, will not cause the BASIC_DATA_LEAF_KEY
to be added to the witness.
If a *CALL
or SELFDESTRUCT
is value-bearing (ie. it transfers nonzero wei), whether or not the callee
is a precompile or a system contract, process this additional access event:
Note: when checking for the existence of the callee
, the existence check is done by validating that there is an extension-and-suffix tree at the corresponding stem, and does not rely on CODEHASH_LEAF_KEY
.
When calling EXTCODEHASH
, process the access event:
Note that precompiles and system contracts are excluded, as their hashes are known to the client.
When a contract is created, process these access events:
Access events for storage
SLOAD
and SSTORE
opcodes with a given address and key process an access event of the form
Where tree_key
and sub_key
are computed as tree_key, sub_key = get_storage_slot_tree_keys(address, key)
Access events for code
In the conditions below, “chunk chunk_id is accessed” is understood to mean an access event of the form
- At each step of EVM execution, if and only if
PC < len(code)
, chunkPC // CHUNK_SIZE
(wherePC
is the current program counter) of the callee is accessed. In particular, note the following corner cases:- The destination of a
JUMP
(or positively evaluatedJUMPI
) is considered to be accessed, even if the destination is not a jumpdest or is inside pushdata - The destination of a
JUMPI
is not considered to be accessed if the jump conditional isfalse
. - The destination of a jump is not considered to be accessed if the execution gets to the jump opcode but does not have enough gas to pay for the gas cost of executing the
JUMP
opcode (including chunk access cost if theJUMP
is the first opcode in a not-yet-accessed chunk) - The destination of a jump is not considered to be accessed if it is beyond the code (
destination >= len(code)
) - If code stops execution by walking past the end of the code,
PC = len(code)
is not considered to be accessed
- The destination of a
- If the current step of EVM execution is a
PUSH{n}
, all chunks(PC // CHUNK_SIZE) <= chunk_index <= ((PC + n) // CHUNK_SIZE)
of the callee are accessed. - If a nonzero-read-size
CODECOPY
orEXTCODECOPY
read bytesx...y
inclusive, all chunks(x // CHUNK_SIZE) <= chunk_index <= (min(y, code_size - 1) // CHUNK_SIZE)
of the accessed contract are accessed.- Example 1: for a
CODECOPY
with start position 100, read size 50,code_size = 200
,x = 100
andy = 149
- Example 2: for a
CODECOPY
with start position 600, read size 0, no chunks are accessed - Example 3: for a
CODECOPY
with start position 1500, read size 2000,code_size = 3100
,x = 1500
andy = 3099
- Example 1: for a
CODESIZE
,EXTCODESIZE
andEXTCODEHASH
do NOT access any chunks. When a contract is created, access chunks0 ... (len(code)+30)//31
Write Events
We define write events as follows. Note that when a write takes place, an access event also takes place (so the definition below should be a subset of the definition of access events). A write event is of the form (address, sub_key, leaf_key)
, determining what data is being written to.
Write events for account headers
When a nonzero-balance-sending *CALL
or SELFDESTRUCT
with a given sender and recipient takes place, process these write events:
if no account exists at callee_address
, also process:
When a contract creation is initialized, process these write events:
Write events for storage
SSTORE
opcodes with a given address
and key
process a write event of the form
Where tree_key
and sub_key
are computed as tree_key, sub_key = get_storage_slot_tree_keys(address, key)
Write events for code
When a contract is created, process the write events:
For i
in 0 ... (len(code)+30)//31
.
Note: since no access list existed for code up until this EIP, note that no warm costs are charged for code accesses.
Transaction
Access events
For a transaction, make these access events:
Write events
If value
is non-zero:
Witness gas costs
Remove the following gas costs:
- Increased gas cost of
CALL
if it is nonzero-value-sending - EIP-2200
SSTORE
gas costs except for theSLOAD_GAS
- 200 per byte contract code cost
Reduce gas cost:
CREATE
/CREATE2
to 1000
Constant | Value |
---|---|
WITNESS_BRANCH_COST | 1900 |
WITNESS_CHUNK_COST | 200 |
SUBTREE_EDIT_COST | 3000 |
CHUNK_EDIT_COST | 500 |
CHUNK_FILL_COST | 6200 |
When executing a transaction, maintain four sets:
accessed_subtrees: Set[Tuple[address, int]]
accessed_leaves: Set[Tuple[address, int, int]]
edited_subtrees: Set[Tuple[address, int]]
edited_leaves: Set[Tuple[address, int, int]]
When an access event of (address, sub_key, leaf_key)
occurs, perform the following checks:
- Perform the following steps unless event is a Transaction access event;
- If
(address, sub_key)
is not inaccessed_subtrees
, chargeWITNESS_BRANCH_COST
gas and add that tuple toaccessed_subtrees
. - If
leaf_key
is notNone
and(address, sub_key, leaf_key)
is not inaccessed_leaves
, chargeWITNESS_CHUNK_COST
gas and add it toaccessed_leaves
When a write event of (address, sub_key, leaf_key)
occurs, perform the following checks:
- If event is Transaction write event, skip the following steps.
- If
(address, sub_key)
is not inedited_subtrees
, chargeSUBTREE_EDIT_COST
gas and add that tuple toedited_subtrees
. - If
leaf_key
is notNone
and(address, sub_key, leaf_key)
is not inedited_leaves
, chargeCHUNK_EDIT_COST
gas and add it toedited_leaves
- Additionally, if there was no value stored at
(address, sub_key, leaf_key)
(ie. the state heldNone
at that position), chargeCHUNK_FILL_COST
- Additionally, if there was no value stored at
Note that tree keys can no longer be emptied: only the values 0...2**256-1
can be written to a tree key, and 0 is distinct from None
. Once a tree key is changed from None
to not-None
, it can never go back to None
.
Note that values should only be added to the witness if there is sufficient gas to cover their associated event costs.
CREATE*
and *CALL
reserve 1/64th of the gas before the nested execution. In order to match the behavior of this charge with the pre-fork behavior of access lists:
- this minimum 1/64th gas reservation is checked AFTER charging the witness costs when performing a
CALL
,CODECALL
,DELEGATECALL
orSTATICCALL
- this 1/64th of the gas is subtracted BEFORE charging the witness costs when performing a
CREATE
orCREATE2
Block-level operations
None of:
- Precompile accounts, system contract accounts and slots of a system contract that are accessed during a system call,
- The coinbase account
- Withdrawal accounts
are warm at the start of a transaction.
System contracts
When (and only when) calling a system contract either
- via a system call or
- to resolve a precompile/opcode,
the system contract's code chunks and account headers accesses should not appear in the witness as these should be known/cached in the clients. However any other accesses and all writes should appear in the witness.
Also corresponding witness costs need to be charged for precompile/opcode resolution but are not charged in the system call.
Account abstraction
TODO : still waiting on a final decision between 7702 and 3074
Rationale
Gas reform
Gas costs for reading storage and code are reformed to more closely reflect the gas costs under the new Verkle tree design. WITNESS_CHUNK_COST
is set to charge 6.25 gas per byte for chunks, and WITNESS_BRANCH_COST
is set to charge ~13,2 gas per byte for branches on average (assuming 144 byte branch length) and ~2.5 gas per byte in the worst case if an attacker fills the tree with keys deliberately computed to maximize proof length.
The main differences from gas costs in Berlin are:
- 200 gas charged per 31 byte chunk of code. This has been estimated to increase average gas usage by ~6-12% suggesting 10-20% gas usage increases at a 350 gas per chunk level).
- Cost for accessing adjacent storage slots (
key1 // 256 == key2 // 256
) decreases from 2100 to 200 for all slots after the first in the group, - Cost for accessing storage slots 0…63 decreases from 2100 to 200, including the first storage slot. This is likely to significantly improve performance of many existing contracts, which use those storage slots for single persistent variables.
Gains from the latter two properties have not yet been analyzed, but are likely to significantly offset the losses from the first property. It’s likely that once compilers adapt to these rules, efficiency will increase further.
The precise specification of when access events take place, which makes up most of the complexity of the gas repricing, is necessary to clearly specify when data needs to be saved to the period 1 tree.
Backwards Compatibility
This EIP requires a hard fork, since it modifies consensus rules.
The main backwards-compatibility-breaking changes is the gas costs for code chunk access making some applications less economically viable. It can be mitigated by increasing the gas limit at the same time as implementing this EIP, reducing the risk that applications will no longer work at all due to transaction gas usage rising above the block gas limit.
Security Considerations
This EIP will mean that certain operations, mostly reading and writing several elements in the same suffix tree, become cheaper. If clients retain the same database structure as they have now, this would result in a DOS vector.
So some adaptation of the database is required in order to make this work:
- In all possible futures, it is important to logically separate the commitment scheme from data storage. In particular, no traversal of the commitment scheme tree should be necessary to find any given state element
- In order to make accesses to the same stem cheap as required for this EIP, the best way is probably to store each stem in the same location in the database. Basically the 256 leaves of 32 bytes each would be stored in an 8kB BLOB. The overhead of reading/writing this BLOB is small because most of the cost of disk access is seeking and not the amount transferred.
Copyright
Copyright and related rights waived via CC0.