This EIP replaces the quadratic memory model in the EVM with a linear, page-based costing model. Memory is virtually addressable. Page allocation is included in the cost model. After applying this EIP, memory limits are invariant to the state of the message call stack.
The EVM currently uses a quadratic pricing model for its memory. This was originally put in place to defend against DoS attacks. However, the memory model has several drawbacks.
This EIP proposes a linear costing model which more closely reflects the hardware of today, which is hierarchical ("hot" memory is much faster to access than "cold" memory), and virtually addressed (memory does not need to be allocated contiguously, but is rather served "on-demand" by the operating system).
First, some preliminaries. A page is 4096 bytes on most architectures. Given a memory address, its page is simple to compute by masking out the rightmost 12 bits.
There are two factors which contribute to "cold" memory (i.e. not-recently-used) being slower: CPU cache and TLB (Translation Lookaside Buffer) cache. The CPU cache is a least-recently-used memory cache, which is significantly faster than fetching all the way from RAM. The TLB is usually some hash table which maps virtual pages (used by the user) to physical pages in RAM. "Thrashing", or accessing a lot of different memory addresses, does two things: it pushes memory out of the hot cache and into cold memory, and it pushes pages out of the TLB cache. For this reason, it is worth limiting the amount of memory that is available to a transaction to memory which can be held in the hot set.
This EIP uses a virtual addressing scheme so that memory pages are not allocated until they are actually accessed.
Notably, the data structures used for costing memory do not need to be part of the memory implementation itself, which suggests an elegant implementation using the POSIX mmap syscall (or, its counterpart on Windows, VirtualAlloc).
The implementation can be approached in two ways. The first way is to implement the virtual addressing "manually". This is intended for systems without mmap or a virtual addressing capability. The implementation needs to maintain a map from map[page_id -> char[4096]], where page_id is an integer, computed as memory_address >> 12. (On reads or writes which cross page boundaries, the implementation needs to load both pages and combine the result of the read or write across both pages).
The other implementation is easier, for systems with mmap or a similar facility. To hold the actual data of the memory, the implementation mmaps a 2**32 byte region of memory. Then, memory operations can be implemented simply as reads or writes against this buffer. (With an anonymous mmap, the operating system will not allocate the entire buffer up-front, rather, it will allocate pages "on demand", as they are touched). The pages map is still necessary, but it doesn't hold any data, it is just to track which pages have been allocated, for pricing purposes. In this implementation, there are two data structures: memory char[2**32] and allocated_pages set[page_id]. The memory data structure is only used for memory reads and writes. The allocated_pages is only used for gas costing.
Consider the following constants:
The memory costing algorithm is changed as follows:
ALLOCATE_PAGE_COST gas if it has not been touched before in this message call.MLOAD and MSTORE, remains the same, at 3.The behavior of msize remains the same. It returns the maximum byte touched by any memory instruction, rounded up by 32.
Memory addresses are restricted to 32-bits. If an address is larger than 2**32 - 1, an exceptional halt should be raised.
A transaction-global memory limit is imposed. If the number of pages allocated in a transaction exceeds MAXIMUM_MEMORY_SIZE // PAGE_SIZE (i.e., 16384), an exceptional halt should be raised.
Benchmarks were performed on a 2019-era CPU, with the ability to keccak256 around 256MB/s, giving it a gas-to-ns ratio of 20 ns per 1 gas (given that keccak256 costs 6 gas per 32 bytes). The following benchmarks were performed:
mmap syscall: 230nsThese suggest the following prices:
Note that the cost to execute mmap (~11 gas) is already well-paid for by the base cost of the CALL series of instructions (100 gas).
There is a desire among client implementations to be able to enforce global limits separately from the gas limit due to DoS reasons. For example, RPC providers may be designed to allow many concurrent eth_call computations with a much higher gas limit than on mainnet. Not implicitly tying the memory limit to the gas limit results in one less vector for misconfiguration. That is not to say that in the future, a clean formula cannot be created which allows the memory limit to scale with future hardware improvements (e.g., proportional to the sqrt of the gas limit), but to limit the scope of things that need to be reasoned about for this EIP, the hard limit is introduced.
The hard limit is specified as a transaction-global limit rather than a message-call limit. That is, a reasonable alternative could be to limit the number of pages that can be allocated in a given message call, e.g., to 2MB, but it doesn't significantly improve implementation complexity.
On keeping the semantics of MSIZE the same:
With users expected to use the full address space instead of growing it linearly, the rationale for keeping MSIZE semantics the same is to avoid breaking backwards compatibility with existing contracts which expect it to grow linearly. New contracts taking advantage of the new virtual addressing scheme should not rely on MSIZE for memory allocation.
A hard limit of 2**32 bytes was imposed on the addressing. This makes it simpler for modern 64-bit computers to allocate that much virtual address space, given that clients run on a diverse set of operating systems and architectures which have different virtual memory limits per process. This could be revisited in the future, for instance if gas limits or client memory sizes substantially increase.
Addressed in Security Considerations section. No backwards compatibility is broken, although some contracts that previously ran out of gas may now successfully complete.
A ~60-line reference implementation is provided below. It is implemented as a patch against the py-evm codebase at commit ethereum/py-evm@fec63b8c4b9dad9fcb1022c48c863bdd584820c6. (This is a reference implementation, it does not, for example, contain fork choice rules).
There are two primary security considerations regarding this EIP.
One, does it break existing contracts? That is, do existing contracts depend on memory being restricted?
Outside of gas costing, existing contracts may simply execute to completion rather than running out of gas.
Two, does this enable memory-based DoS attacks against clients?
This requires a maximum-memory usage analysis. Based on a gas limit today of 30mm gas, recursively calling a contract that allocates 256KB of memory in each call stack can allocate 54MB of total memory, which is not substantially different than the 64MB limit proposed in this EIP. Note that the transaction-global memory limit proposed in this EIP provides a useful invariant, which is that future changes to call stack limits will not affect the total amount of memory that can be allocated in a given transaction.
Copyright and related rights waived via CC0.