EIP-7686 Linear EVM memory limit (Linear EVM memory limits)
No call decision · EVM & execution · EIP status Stagnant · created 2024-04-15
A proposal that changes EVM memory expansion cost from quadratic to linear, and reduces the gas passed to sub-calls based on memory usage, so that an execution running with N gas can use at most N bytes of memory.
Why it is needed
Under the EVM's current memory pricing rules, the cost of expanding memory is calculated quadratically, and the gas that can be passed to a child call (sub-call) is determined solely by EIP-150's 63/64 rule. Because these two rules overlap, it is very difficult to precompute the maximum total memory an execution can use overall. This is especially problematic in constrained environments, such as ZK-SNARK provers, that must preallocate memory of a precise size in advance. This proposal changes the memory expansion cost to a simple linear formula and ties the sub-call gas limit to the current context's memory usage, creating a tight, clear upper bound: an execution using N gas can use at most N bytes of memory.
What changes
Today
- Memory expansion cost is calculated quadratically (word^2/512 + 3*word)
- The maximum sub-call gas is governed solely by EIP-150's 63/64 rule, independent of memory usage
- It is difficult to precompute the maximum total memory an execution will use overall
- There is no hard limit on memory usage
After EIP-7686
- Memory expansion cost changes to a simple linear formula (3 * word)
- If the memory size exceeds the current context's initial gas limit, execution reverts
- The maximum sub-call gas is calculated as gas - max(gas//64, memory_byte_size), which decreases as more memory is used
- A linear limit is guaranteed: an execution using N gas can use at most N bytes of memory overall
Who is affected
- Client and EVM implementation teams: The memory pricing rule becomes simpler, and the EVM can be implemented by preallocating an N-byte byte array and dividing it among child calls.
- ZK-SNARK prover developers: They benefit from being able to know the clear upper bound on memory usage in advance when proving execution in constrained environments.
- Smart contract developers: Existing code that is called with low gas and accesses memory at a high index could theoretically fail, but the author explains that since the minimum gas required for any state change (5000) already secures 5000 bytes of memory, there is mostly no impact.
- Users: The way gas costs are calculated changes, but for typical transactions there is almost no practical difference in cost.
In depth
Memory cost formula change
Previously, memory_cost = (memory_size_word ** 2) / 512 + (3 * memory_size_word), which included a term proportional to the square of the word count. This proposal changes it to memory_cost = 3 * memory_size_word, making it fully linear. Removing the quadratic term makes the cost increase from memory usage predictable and makes it easier to compute the upper bound on memory usage for an entire execution.
Hard memory limit
If memory expansion causes memory_byte_size to exceed the current call's initial gas limit, the execution reverts with an error. In other words, a context with N gas cannot request more than N bytes of memory. This rule, combined with the linear cost formula, creates an absolute upper bound on memory usage.
Sub-call maximum gas formula change
Instead of the existing max_call_gas(gas) = gas - (gas // 64) defined by EIP-150, this proposal uses max_call_gas(gas, memory_byte_size) = gas - max(gas // 64, memory_byte_size). If the current context is already using a lot of memory, the gas that can be passed to a child call is reduced accordingly, which also limits how much memory the child can use.
The meaning of the linear limit and its tightness
Combining these two rules establishes the invariant that a call executed with N gas (the parent plus all child calls combined) can use at most N bytes of memory overall. The author describes this limit as tight rather than loose, because there exists a simple way for a call with N gas to actually use up to N - O(1) bytes of memory.
Benefits for ZK-SNARK provers
This invariant makes it possible to implement the EVM such that a single N-byte byte array represents the memory for an entire execution. When the current context is allocated all the bytes and makes a child call, the remaining space starting from the memory_byte_size position is recursively handed over as the child's memory. This clean structure is useful for EVM implementations in constrained environments, such as ZK-SNARK provers, that must preallocate memory precisely in advance.
Why 3 gas per word is kept
The reason 3 gas per word is kept as the memory expansion cost is that this figure matches the cost of the MCOPY operation. Cleaning up memory after a child call finishes is cheap on typical computers, but more costly in special environments like ZK-SNARKs, and this cost can be handled with the same logic used in the MCOPY implementation.
Why the 63/64 rule is kept
The 63/64 rule introduced in EIP-150 (which allows passing at most 63/64 of total gas to a child call) is kept unchanged. This is to preserve the current effective call stack depth limit, approximately 1 + log((gaslimit + 6300) / 6400) / log(64/63) ≈ 537.
Backward compatibility and current status
The author acknowledges that existing code called with a low gas limit and accessing memory at a high index could theoretically be affected, but explains that since changing even a single piece of state requires at least 5000 gas, which already allows 5000 bytes of memory, most applications should be unaffected. On the security front, no concerns have been raised. However, since this EIP's current status is Stagnant with no active ongoing discussion, whether it will be adopted or changed in the future cannot be determined from the original text alone.