ZKEVM - Random Thoughts

EVM Caveat

Memory Expansion

There are several opcodes that expand memory:

The psuedo code of memory expansion:

from math import ceil

MEMORY_SIZE_MAX = 32 * (2**32 - 1) # 0x1FFFFFFFE0

# returns (new_memory_size, is_overflow)
def expand_memory(memory_size: int, off1: int, len1: int, off2: int, len2: int) -> int, bool:
    def m(off: int, len: int) -> int, bool:
        if len is None or len == 0:
            return 0, False

        new_memory_size = 32 * ceil(off + len / 32)

        if new_memory_size > MEMORY_SIZE_MAX:
            return 0, True

        return new_memory_size, False

    new_memory_size1, is_overflow1 = m(off1, len1)
    new_memory_size2, is_overflow2 = m(off2, len2)

    if is_overflow1 or is_overflow2:
        return 0, True

    return max(memory_size, new_memory_size1, new_memory_size2), False

Ideally we can verify the OOG caused only by memory expansion in a single branch, by lookup the offset and length in stack position with the opcode, and verify the new memory size indeed exceeds the max value.

Access List (EIP2929)

To support EIP2929, we add 2 extra revertable targets tx_access_list_account and tx_access_list_storage_slot in State circuit to maintain, their value is constraint to only be 0 or 1, and lazily initialied to be 0. Then in EVM circuit, we will always write it to 1, and see the different between current and previous value to see if it's a warm or cold access.

Precompiles

Note: If we are reading returndata directly from last callee's memory, we need to be careful when handling precompile 0x04 DataCopy since the last callee would be caller itself. We should explicitly copy calldata to precompile's memory and treat it as a call.

Possible Upgrade of EVM

SELFDESTRUCT Neutralization

The SELFDESTRUCT opcode is renamed to SENDALL, and now only immediately moves all ETH in the account to the target; it no longer destroys code or storage or alters the nonce
quotes from <a href="https://notes.ethereum.org/-fJSOrnYQl-mqoWKpaTIsQ#Miscellaneous">Statelessness gas cost changes EIP draft #Miscellaneous</a>

If so, we can get rid of a bunch of consideration of the destroy of code and storage.

Reference

• Statelessness gas cost changes EIP draft

EOF - EVM Object Format

After EIP3670 - EOF - Code Validation:

• Create transaction, CREATE* becomes more complicated, we need to verify creation code and also returned runtime code.
• Opcode lookup becomes easier since no any implict behavior (implict PUSH* data padding, implicit STOP in the end).

After EIP4200 - Static relative jumps:

• JUMP* becomes easier since no any invalid jump at runtime.

Reference

• Everything about the EVM Object Format (EOF)
• The future of EVM - EVM Object Format

Statelessness

• Merkle (Hexary) Patricia Trie becomes Verkle Trie
• Trie-access-aware gas cost calculation
• Chunkified contract bytecode

Reference

• Ethereum statelessness roadmap

EIP4488 - Transaction calldata gas cost reduction with total calldata limit

EIP4488 specification:

Reduce the gas cost of transaction calldata to NEW_CALLDATA_GAS_COST per byte, regardless of whether the byte is zero or nonzero.

Add a rule that a block is only valid if sum(len(tx.calldata) for tx in block.txs) <= BASE_MAX_CALLDATA_PER_BLOCK + len(block.txs) * CALLDATA_PER_TX_STIPEND.

Misc

• Sparse Representation Trick on Keccak
• Multi-Limbs Multiplication
• ZKEVM - Call and Call State
• ZKEVM - EVM Circuit Layout and Branching
• ZKEVM - EVM Circuit Design Rationale
• ZKEVM - Consideration on Transaction
• ZKEVM - RLP Encoding
• ZKEVM - State Circuit Extension - StateDB