EIP-2315 "Simple Subroutines for the EVM" - Analysis

EIPs
, ,
41

Subroutine map with capped executable code size

Current max size of deployable code is 24576 (0x6000). We propose to also limit the size of executable code to 2x the above limit, i.e. 49152 (0xc000).

This gives nice properties:

  • instruction offset in code fits 16-bit value,
  • code size fits 16-bit value.

Possible implementations of subroutine maps

Shadow array

Max memory footprint: 0xc000

We create a byte array of the size of the code shadowing the instructions in the code. The array is initially filled with zeros.

  • a JUMPDEST instruction is indicated by 0x80 mask in the shadow array.
    To validate jump destination: (shadow_array[location] & 0x80) != 0.
  • a BEGINSUB instruction is indicated by 0x40 mask in the shadow array.
  • the size of a subroutine is encoded in the remaining 6-bits using variable-length encoding analogous to LEB128. Examples:
    • 40 - subroutine of length zero,
    • 5f - subroutine of length 31 (0x1f), the max length that fits single byte encoding,
    • 6001 - subroutine of length 32 (0x00 + 2^5 * 0x01)
    • 7f - subroutine of length 1023 (0x1f + 2^5 * 0x1f), the max length that fits two-byte encoding,
    • 6081 - subroutine of length 32 followed by a JUMPDEST instruction.

Bitset with linear search

Max memory footprint: 0xc000 / 4 == 12288

We create a bitset indicating an instruction is JUMPDEST and another bitset indicating an instruction is BEGINSUB. During execution we keep track of where the current subroutine starts.

To validate if a jump stays within a subroutine:

  • when jumping backwards, just check if juspdest_location >= current_subroutine_begin,
  • when jumping forward, find the beginning of the next subroutine starting from current PC (where the jump is). This is done by linear search in subroutine bitset. We can process 64 bits at a time by using 64-bit load and checking if value is not zero. This may be optimized further using SSE2 (128-bit) or AVX (256-bit).

In worst case we need 0xc000 / 64 == 768 comparisons.

Span map

Max memory footprint: 0xc000 * 2 == 98304 + jumpdest map.

We keep an array of all BEGINSUB instructions offsets. Single value is uint16 and values are already sorted.

To verify JUMPSUB check if location is in the array using binary search.

When entering a subroutine remember subroutines begin and end location. The end location is the next value in the array.

To verify if a jump stays within a subroutine check if jumpdest_location is between subroutine’s begin and end.

I’m not able to prove it, but that was exactly my intention.