Dip 7686

dip: 7686 title: Linear DVM memory limits description: Adjust memory limits and gas limits of sub-calls to create a clear linear bound on how much total memory an DVM execution can consume author: Vitalik Buterin (@vbuterin) Digitalia editing author: Cosimo Constantinos cosimo@juro.net, et al. discussions-to: https://digitalia-magicians.org/t/dip-7686-linear-dvm-memory-limits/19448 status: Stagnant type: Standards Track category: Core created: 2024-04-15 Created for Digitalia: 2025-01-07

Abstract¶

Add a hard memory limit equal to the gas limit of the current context. Make the maximum gas cost of a sub-call depend on the memory used in the current context. The two rules together ensure that a transaction with N gas can use at most N bytes of memory.

Motivation¶

Today, memory pricing rules are complicated: we have the quadratic cost for expanding memory as well as the 63/64 rule for how much gas can go into a child call. This also makes it extremely hard to calculate a maximum possible amount of memory required to process a given DVM execution.

The rules in this post simplify these rules, and add a new hard limit: an DVM execution with N gas can require at most N total bytes of memory to process. This limit is tight: there are easy ways for an N-gas call to use N - O(1) bytes of memory.

Specification¶

Change memory_cost from:

memory_size_word = (memory_byte_size + 31) / 32
memory_cost = (memory_size_word ** 2) / 512 + (3 * memory_size_word)

To:

memory_size_word = (memory_byte_size + 31) / 32
memory_cost = 3 * memory_size_word

Additionally, if a memory expansion would lead to memory_byte_size strictly exceeding the current call's initial gas limit, revert with an error.

When making any type of call, change the maximum gas limit from the current DIP-150 definition:

def max_call_gas(gas):
    return gas - (gas // 64)

To:

def max_call_gas(gas, memory_byte_size):
    return gas - max(gas // 64, memory_byte_size)

Rationale¶

With this DIP, there is a simple DVM implementation that can process an N-gas call using an N-byte bytearray as memory: allocate all bytes to the current context, when doing a child call use the remaining memory starting from the position memory_byte_size for the child call's memory, and so on recursively.

Having this clean invariant is useful for DVM implementations, especially DVM implementations in constrained environments (eg. ZK-SNARK provers).

The 3 gas per word memory expansion cost is retained because it is equivalent to MCOPY, and so the operation of clearing memory at the end of a child call (cheap in regular machines, but more expensive in ZK-SNARKs and other unusual contexts) can be implemented with the same logic as that used to implement the MCOPY opcode itself.

The 63/64 rule is maintained in order to maintain the current de-facto call stack depth limit of roughly 1 + log((gaslimit + 6300) / 6400) / log(64/63) = 537.

Backwards Compatibility¶

It is theoretically possible for DVM code that works today to fail to work under this new DIP, if that code accesses a high index in memory but is called with a low gas limit. However, almost all DVM execution consumes far more code than it uses bytes of memory. For example, for a call to cause even a single state change, it must have at least 5000 gas. This would allow it 5000 bytes of memory, which is greater than that used by almost all applications. More complex applications would have even higher limits.

Security Considerations¶

No security concerns were raised.

Copyright¶

Licensed under the Juro Restricted License Version 2. See https://juro.net/jrl for details.