# Proposals to adjust memory gas costs Currently, we limit the memory consumption of the EVM in two ways: a _quadratic memory expansion cost_ and a _de-facto call stack depth limit_ enforced with the [EIP-150](https://eips.ethereum.org/EIPS/eip-150) "63/64 rule". These mechanisms are reasonably effective at their desired goal, but are both needlessly complicated and _inefficient_, punishing regular users too much and DoS attackers too little. This post proposes some alternative designs that better meet the key goal of limiting EVM memory usage. ## How does memory gas pricing work today? ### Quadratic memory expansion cost Extending memory in a callframe to $L$ chunks (so, $L * 32$ bytes) requires paying $\lfloor \frac{L^2}{512} \rfloor + 3L$ gas. This is charged in real time. For example, if memory is currently 16 chunks long, and a `MSTORE` op fills bytes `682...713`, then memory is extended to 23 chunks, and $(\lfloor \frac{23^2}{512} \rfloor + 3 * 23) - (\lfloor \frac{16^2}{512} \rfloor + 3 * 16) =$ $(1 + 69) - (0 + 48) = 22$ extra memory expansion gas is charged. See [implementation here](https://github.com/ethereum/pyethereum/blob/develop-snapshot/ethereum/vm.py#L129). Note that this is on a _per-call-frame_ basis: if a call makes a child call, memory in the child call is initialized as empty and pricing for it starts from zero. ### The 63/64 rule To prevent excessive memory consumption by having a contract recursively call itself and fill many callframes with a medium amount of memory where the quadratic costs do not yet seriously kick in for each frame, there is a limit on how many callframes can be made. When a contract makes a call, the child is only allowed to receive up to $\frac{63}{64}$ of the remaining gas. This means that a call frame $d$ levels deep can receive at most $G * (\frac{63}{64})^d$ gas (where $G$ is the transaction gas limit). Given that making a call requires at least 114 gas (100 for the `CALL` post-[EIP-2929](https://eips.ethereum.org/EIPS/eip-2929) plus 14 to fill the stack arguments), and a block can have at most 30 million gas, naively we can compute that the call stack depth cannot exceed $log(\frac{114}{30000000}) \div log(\frac{63}{64}) = 792$ calls. If we take a more sophisticated calculation and include the gas cost of all those calls, this goes down to 528. In reality, 114 gas is almost certainly not enough and the true limit is under 500. There is also an explicit call stack depth limit of 1024. The 63/64 mechanism was implemented to supersede it (the limit exists in code but is not reachable) both to reduce the de-facto limit to weaken DoS attacks and to prevent scenarios where malicious contracts self-call 1023 times before calling another contract, causing that contract to behave in an unexpected way. ### How much memory can you fill? With 30 million gas, you can fill 123169 chunks (3941408 bytes) of memory in a single callframe, as 123169 is the highest $L$ that satisfies $\lfloor \frac{L^2}{512} \rfloor + 3L \le 30000000$. You could make many callframes and fill each callframe with N bytes. Here, the optimum is 88 callframes with 8374 chunks each, which would fill a total of 736912 chunks (23581184 bytes). A more clever strategy is to put more memory into outer call frames, as inner call frames have a higher cost due to the repeated application of the $\frac{63}{64}$ rule. For example, you could fill the i'th call frame with $k_1 * (1 + \frac{1}{k_2})^i$ bytes. The optimum here is $k_1 = 798$ and $k_2 = 54$, for a total of 166 calls filling 839602 chunks = 26867264 bytes (note: these numbers are slightly wrong due to using a simplified model, but at most by a couple percent). Code for this model is here: ```python= def get_max_chunks(chunks_per_depth, inv_growth_rate): tot = 0 next_call = 0 depth = 0 while next_call < 30000000: depth += 1 tot += chunks_per_depth chunks_per_depth += chunks_per_depth // inv_growth_rate next_call = int( (next_call * 64/63) + 120 + (3 * chunks_per_depth + chunks_per_depth**2 / 512) ) return tot ``` **The most important conclusion from all this is that the current memory pricing mechanism has weird dynamics and is dumb. We don't even have a good clear way to calculate the max memory that can be used in a block.** ## What are some specific weaknesses of this model? Some major issues with the model in its current form are: * Inconsistent and unprincipled different handling of how memory pricing works between expanding memory within a call frame vs between call frames * The concept of *charging* gas to expand memory is suboptimal, because it doesn't actually cost any resources to use memory. We want to bound, but we gain nothing from a particular transaction using 10% of this bound instead of 90% * Lack of a clear formula to compute theoretical max memory usage * Legitimate applications generally use few call frames, and so legitimate applications have a much lower max memory they can use than attackers ## Parameters and helpers (shared by proposals below) | Parameter | Value | Notes | | - | - | - | | `GAS_PER_MEMORY_BYTE` | 1 | 30m bytes for a 30m gas transaction. ~12% higher than status quo theoretical max | | `BASE_CALLFRAME_BYTES` | 1024 | Assume an overhead of 1024 bytes per callframe. | This function returns our estimate of the number of bytes required to store the current call frame in memory: ```python= def get_callframe_byte_size(callframe: CallFrame): return ( len(callframe.memory) + 32 * len(callframe.stack) + BASE_CALLFRAME_BYTES ) ``` Add this code to quickly test code samples in python: ```python= from dataclasses import dataclass @dataclass class CallFrame(): memory: bytes stack: list def integer_squareroot(x): return int(x**0.5) ``` ## Proposal 1: cap memory by gas 1. Remove memory expansion pricing and the 63/64 rule. 2. Every call frame, when initialized, gets a limit of memory equal to `call_gas // GAS_PER_MEMORY_BYTE` bytes. Attempts to extend memory to greater than that limit exit with an error. 3. In a call, the child call frame gets at most `gas - get_callframe_byte_size(parent_callframe) * GAS_PER_MEMORY_BYTE` gas. 4. Charge gas for copying data when returning from a call, at the same rate as `CALLDATACOPY` (so, 3 gas per 32 byte chunk) This creates two hard invariants: 1. Total memory usage, across all active call frames, is capped at `30m / GAS_PER_MEMORY_BYTE`. 2. We get a de-facto max callstack depth of `30000000 // 1024 = 29296` We solve many key problems: * We cap total memory usage across call frames, and memory expansion within and between call frames is treated the same. * We don't charge gas for memory expansion. * We get a very clear formula for computing theoretical max memory usage. Because this proposal removes the quadratic rule, it is weaker than it could be in one way. Transactions that specify a low amount of gas get a smaller amount of memory that they can access: while a 3m gas transaction would get 3m bytes of memory instead of 1229792, a 100k gas transaction would get 100000 bytes instead off 205696. However, this is much less bad than it seems, because in the status quo the transaction has to pay for all this gas, whereas in this new proposal it does not. ## Proposal 2: cap total memory to 30m separately from gas 1. Remove memory expansion pricing and the 63/64 rule. 2. A call frame gets a `max_memory` parameter; memory expansion beyond that value is forbidden. The outermost call frame gets `max_memory = block.gaslimit // GAS_PER_MEMORY_BYTE` 3. The child call frame gets `max_memory = parent_callframe.max_memory - get_callframe_byte_size(parent_callframe)` 4. Charge gas for copying data when returning from a call, at the same rate as `CALLDATACOPY` (so, 3 gas per 32 byte chunk) This gives us the same invariants as above, but ensures that each transaction gets 30m bytes. The main weakness of this approach is that it adds another parameter to calls, and it brings back the security issue that motivated the replacement of call stack depth with the 63/64 rule in the first place: it means that gas would once again no longer be a sufficient guarantee of what computation a call frame can do. An attacker could expand to 29.9m memory in an outer call frame, with the goal of crashing inner call frames. ## Proposal 3: cap memory by sqrt(gas) | Parameter | Value | Notes | | - | - | - | | `MEMORY_BYTES_PER_SQRT_GAS` | 4096 | Theoretical max of 22434715 bytes in a transaction | Remove the 63/64 rule, and charge 3 gas per 32 byte chunk for copying data when returning from a call. Set the max memory of a call frame to `integer_squareroot(gas * MEMORY_BYTES_PER_SQRT_GAS**2)`. Set the max gas of a child based on the following formula: ```python= def get_max_child_gas(current_gas, parent_callframe): adjusted_sqrt_current_gas = integer_squareroot( current_gas * MEMORY_BYTES_PER_SQRT_GAS**2 ) subtract_bytes = get_callframe_byte_size(parent_callframe) if adjusted_sqrt_current_gas < subtract_bytes: raise Exception("Parent call frame used more memory than allowed!") adjusted_sqrt_remaining_gas = adjusted_sqrt_current_gas - subtract_bytes return ( adjusted_sqrt_remaining_gas**2 // MEMORY_BYTES_PER_SQRT_GAS**2 ) ``` This is a version of proposal 1 that is more friendly to low-gas transactions: a 100k gas transaction would get 1295268 bytes (compare: 100k in proposal 1), and a 3m gas transaction would get 7094480 bytes (compare: 3m in proposal 1). It works by using `sqrt(gas)` as the "tracker" of allowed remaining memory instead of `gas`. Its main weakness is simply the fact that it is somewhat less intuitive and more complicated; you have to think a bit harder to make sure that it actually satisfies the invariant that `total_bytes <= sqrt(gas) * 4096`.