EIP-3336 EVM page-based memory allocation (Paged memory allocation for the EVM)

No call decision · EVM & execution · EIP status Stagnant · created 2021-03-06

A proposal to change the EVM's memory-pricing model from treating memory as one contiguous array from address 0 to the end, to dividing it into fixed-size pages and charging only for the pages actually used.

Why it is needed

The current EVM treats memory as a single contiguous array from address 0 to the highest address accessed, and charges gas accordingly. As a result, writing values to just two far-apart addresses causes the entire space between them to be counted as allocated, inflating cost. This forces compilers to pack memory as tightly as possible to save gas, and flexible memory layouts such as separating the stack from the heap waste gas through excessive reallocation and copying. This EIP proposes dividing memory into fixed-size pages, as operating systems do with virtual memory, and charging only for the pages actually touched.

What changes

Today

After EIP-3336

Who is affected

In depth

Page structure and allocation

Of the 256 bits in a memory address, the upper (256 - PAGE_BITS) bits identify the page number, and the lower PAGE_BITS (=10) bits identify the position within the page. In other words, each page is 2**PAGE_BITS = 1024 bytes. Every page starts out filled entirely with zeros, and is allocated only the moment the first byte of that page is read or written. The original recommends that EVM implementations store the page table as a hash table or dictionary keyed by page number.

New memory expansion cost formula

The existing cost function is Cmem(a) = 3*a + floor(a**2/512), where a is the number of words needed up to the highest word accessed so far. This EIP defines a new function based on page count p: Cmem'(p) = max(PAGE_BASE_COST*(p-1) + floor(2*(p-1)**2), 0). PAGE_BASE_COST is 96. If q pages are already allocated and the memory expands further, only Cmem'(p) - Cmem'(q) is charged as the additional cost.

Changes to MLOAD/MSTORE cost

When reading or writing a word, if the page that word spans has not yet been allocated, it is allocated first, and the expansion cost above is charged in addition. If the word lies entirely within one page, it still costs 3 gas as before, but if it spans two pages, it costs 6 gas. The original explains this reflects the extra work of splitting the word at the page boundary and updating two separate pages.

Other memory-accessing instructions

All other instructions that read or write memory, such as CALLDATACOPY, CODECOPY, EXTCODECOPY, CALL, CALLCODE, DELEGATECALL, STATICCALL, CREATE, and MSTORE8, follow the same rule. If a page being accessed has not yet been allocated, it is allocated and gas is charged according to the memory expansion cost formula defined above.

Backward compatibility design

The new cost function is designed to always be equal to or lower than the existing function. A program that writes memory exactly up to a page boundary pays one page less than before, and one that writes one word past the boundary pays one word less. However, MLOAD/MSTORE operations that straddle a page boundary can become more expensive than before. The original expects the number of such programs, and their impact, to be small.

Security considerations

Charging a higher cost for reads and writes that straddle a page boundary is meant to mitigate the CPU-load denial-of-service (DoS) risk this could otherwise create. The memory expansion cost is also designed to asymptotically approach the existing cost, so the new model does not allow allocating substantially more memory than before.

Undetermined items and current status

The FORK_BLOCK value is still TBD, and the Test Cases section is also left empty as TBD. This EIP's status is Stagnant, and no call records addressing fork inclusion have been found. It remains a proposal whose core specification variables have not been finalized.

Original EIP · ← EIPs