Abstract

This is the smallest possible change to the EVM to support calls and returns.

This proposal introduces three new control-flow instructions to the EVM:

• CALLSUB transfers control to the destination on the stack.
• ENTERSUB marks a CALLSUB destination.
• RETURNSUB returns to the PC after the most recent CALLSUB.

Code can also be prefixed with MAGIC bytes. The complete control flow of MAGIC code can be traversed in time and space linear in the size of the code, enabling tools for validation, static analysis, and AOT and JIT compilers. On-chain, MAGIC code is validated at CREATE time to ensure that it cannot execute invalid instructions, jump to invalid locations, underflow stack, or, in the absence of recursion, overflow stack.

These changes are backwards-compatible: all instructions behave as specified whether or not they appear in MAGIC code.

Motivation

The EVM currently lacks explicit call and return instructions. Instead, calls and returns must be synthesized using the dynamic JUMP instruction, which takes its destination from the stack. This creates two fundamental problems:

• Inefficiency: Synthesizing calls and returns with jumps wastes bytecode space and gas.
• Complexity: Even more important, dynamic jumps can cause quadratic "path explosions" during control-flow analysis, creating a denial-of-service vulnerability for things like init-time compilation to RISC-V code. They can also trigger exponential "state space explosions" during formal analysis and ZK circuit construction.

For detailed historical context, technical foundations of static control flow, and their impact on Ethereum's scaling roadmap, see EIP xxxx: "Static Control Flow for the EVM — Foundational Concepts & Context."

Specification

The key words MUST and MUST NOT in this Specification are to be interpreted as described in RFC 2119 and RFC 8174.

CALLSUB (0x..)

Transfers control to a subsidiary operation.

1. Pop the destination on top of the stack.
2. Push the current PC + 1 to the return stack.
3. Set PC to destination.

The gas cost is mid (8).

ENTERSUB (0x..)

The destination of every CALLSUB MUST be an ENTERSUB.

RETURNSUB (0x..)

Returns control to the caller of a subsidiary operation.

1. Pop the return stack to PC.

The gas cost is low (5).

MAGIC (0xEF....)

After this EIP has been activated, code beginning with the MAGIC bytes MUST be a valid program. Execution begins immediately after the MAGIC bytes.

Notes:

• Values popped off the return stack do not need to be validated, since they are alterable only by CALLSUB and RETURNSUB.
• The description above lays out the semantics of these instructions in terms of a return stack. But the actual state of the return stack is not observable by EVM code or consensus-critical to the protocol. (For example, a node implementer may code CALLSUB to unobservably push PC on the return stack rather than PC + 1, which is allowed so long as RETURNSUB observably returns control to the PC + 1 location.)
• Opcode and MAGIC values are still to be determined, but the MAGIC bytes will begin with 0xEF.

Costs

A mid cost for CALLSUB is justified by it taking very little more work than the mid cost of JUMP — just pushing an integer to the return stack.

A jumpdest cost for ENTERSUB is justified by it being, like JUMPDEST, a mere label.

A low cost for RETURNSUB is justified by needing only to pop the return stack into the PC — less work than a jump.

Benchmarking will be needed to tell if the costs are well-balanced.

Validity

Execution is defined in the Yellow Paper as a sequence of changes to the EVM state. The conditions on valid code are preserved by state changes. At runtime, if execution of an instruction would violate a condition, the execution is in an exceptional halting state and cannot continue. The Yellow Paper defines six such states:

• State modification during a static call
• Insufficient gas
• More than 1024 stack items
• Insufficient stack items
• Invalid jump destination
• Invalid instruction

We would like to consider EVM code valid if and only if no execution of the program can lead to an exceptional halting state. In practice, we must test at runtime for the first three conditions — we don't know whether we will be called statically, how much gas there will be, or how deep a recursion may go. (However, we can validate that non-recursive programs do not overflow stack.) All of the remaining conditions MUST be validated statically.

To allow for efficient algorithms, our validation considers only the code's control flow and stack use, not its data and computations. This means we will reject programs with invalid code paths, even if those paths are not reachable.

Constraints on valid code

Code beginning with MAGIC MUST be valid. Constraints on valid code MUST be validated at CREATE time, in time and space linear in the size of the code. The constraints on valid code are as follows:

• All executable opcodes must be valid:
  • They MUST have been defined in the Yellow Paper or a deployed EIP and
  • MUST NOT have been deprecated in a subsequent deployed EIP.
  • The INVALID opcode is valid.
• The JUMP and JUMPI instructions MUST be preceded by a PUSH instruction.
• The JUMP and JUMPI instructions MUST NOT address immediate data, and MUST address a JUMPDEST.
• The CALLSUB instruction MUST be preceded by a PUSH instruction.
• The CALLSUB instruction MUST NOT address immediate data, and MUST address an ENTERSUB.
• The number of items on the data stack MUST always be positive and less than or equal to 1024.
• The number of items on the return stack MUST always be positive and less than or equal to 1024.
• The stack height is the absolute difference between the current stack pointer and the stack pointer at the most recent ENTERSUB.
• During execution, the stack height MUST be the same for every PC.

The guarantee of constant stack height prevents stack underflow, breaks cycles in the control flow, ensures finite stack use for non-recursive programs, enables one-pass recovery of control-flow, and allows virtual stack code to be directly serialized into virtual register code for faster interpretation and compilation to machine code.

Note: The JVM, Wasm, and .NET VMs enforce similar constraints for similar reasons.

Validation

The above is a purely semantic specification, placing no constraints on the syntax of bytecode beyond being an array of opcodes and immediate data. Turing's "subsidiary operations" here are not contiguous sequences of bytecode: they are subgraphs of the bytecode's full control-flow graph. The EVM is a simple state machine, and the control-flow graph for a program represents every possible change of state. Each instruction simply advances the state machine one more step, and the state has no syntactic structure. We only promise that valid code will not, as it were, jam up the gears of the machine.

Rather than enforce semantic constraints via syntax — as is done by higher-level languages — this proposal enforces them via validation: MAGIC code is proven valid at CREATE time. The constraints above MUST be proven true in time and space linear in the size of the code. We provide a simple algorithm below for doing so — there are better ones.

With no syntactic constraints and minimal semantic constraints, we maximize opportunities for optimizations, including tail call elimination, multiple-entry calls, efficient register allocation, and inter-procedural optimizations. Since we want to support online compilation of EVM code to native code, it is crucial that the EVM code be as well optimized as possible by high-level-language compilers — upfront and offline.

Rationale

Why these three opcodes?

This proposal aims to be the smallest possible change to the EVM. We introduce only three industry-standard instructions — CALLSUB, ENTERSUB, and RETURNSUB — sufficient to eliminate the need for dynamic jumps in synthesizing calls and returns and

We do not include:

• Immediate arguments for jump destinations, which would improve performance but increase complexity. See EIP-8013: Static relative jumps and calls for the EVM for a complementary proposal using immediate arguments.

• Code sections or other structural constraints, which would impose syntactic restrictions that inhibit optimization. See EIP-3540: EOF - EVM Object Format and EIP-4750: EOF - Functions for complementary proposals that provide such structure.

By minimizing the scope, this proposal:

• Reduces implementation complexity and deployment risk
• Remains forward-compatible with larger proposals like EIP-8013 and EIP-4750

Why the return-stack mechanism?

Register machines like x86, ARM, and RISC-V typically use a single stack for both data and return addresses, relying on registers and calling conventions. Stack machines like Forth, Java, Wasm, and .NET use a separate data and return stacks. The EVM is a stack machine, and we adopt the same proven approach: a separate return stack isolated from the data stack.

Safety advantages

Return addresses are not accessible to EVM code. They cannot be read, modified, or moved by ordinary stack operations. This eliminates an entire class of vulnerabilities where code could corrupt its own control flow.

Because return addresses are controlled exclusively by CALLSUB and RETURNSUB, they are intrinsically safe to validate. Unlike data-stack values (which may depend on arbitrary computation), return-stack values are guaranteed to be valid PC values — we can validate all return addresses at compile time.

Proven track record

This mechanism has been used effectively in numerous machines over the last eight decades since Alan Turing introduced it (ACE, 1945). It has been implemented, tested, and even ready to ship in multiple Ethereum clients over the last nine years.

Code size and gas savings

The difference these instructions make can be seen in this very simple code for calling a routine that squares a number. The distinct opcodes make it easier for both people and tools to understand the code, and there are modest savings in code size and gas costs as well.

SQUARE:                           |       SQUARE:
    jumpdest       ; 1 gas        |           entersub       ; 1 gas
    dup            ; 3 gas        |           dup            : 5 gas
    mul            ; 5 gas        |           mul            ; 5 gas
    swap1          ; 3 gas        |           returnsub      ; 5 gas
    jump           ; 8 gas        |
                                  |
CALL_SQUARE:                      |       CALL_SQUARE:
    jumpdest       ; 1 gas        |           entersub       ; 1 gas
    push RTN_CALL  ; 3 gas        |           push 2         ; 3 gas
    push 2         ; 3 gas        |           push SQUARE    ; 3 gas
    push SQUARE    ; 3 gas        |           callsub        ; 8 gas
    jump           ; 8 gas        |           returnsub      ; 5 gas
RTN_CALL:                         |
    swap1          ; 3 gas        |
    jump           ; 8 gas        |
                                  |
Size in bytes: 18                 |      Size in bytes: 13
Consumed gas:  49                 |      Consumed gas:  38

That's 32% fewer bytes and 30% less gas using CALLSUB versus using JUMP. So we can see that these instructions provide a simpler, more efficient mechanism. As code becomes larger and better optimized the gains become smaller, but code using CALLSUB always takes less space and gas than equivalent code without it.

Real-time performance

Some real-time interpreter performance gains are reflected in the lower gas costs. But larger gains come from AOT and JIT compilers. The constraint that stack depths be constant means that in MAGIC code, a JIT can traverse the control flow in one pass, generating machine code on the fly, and an AOT can emit better code in linear time (The Wasm, JVM, and .NET VMs share this property.)

The EVM is a stack machine, but most real machines are register machines. Generating virtual register code for a faster interpreter yields significant gains (4X speedups are possible on JVM code), and generating good machine code yields orders of magnitude improvements. However, for most transactions, storage dominates execution time, and gas counting and other overhead always take their toll. So such gains would be most visible in contexts where this overhead is absent, such as L1 precompiles, some L2s, and some EVM-compatible chains.

ZK and scaling performance

Static control flow enables the construction of simpler, more efficient circuits for ZK verification. See EIP xxxx for details on how static control flow improves ZK-Rollup and optimistic rollup efficiency, and enables future migrations to other execution environments like RISC-V.

How can dynamic jumps cause quadratic control flow?

Static analysis of a program without executing it — such as recovering its control-flow graph — is a fundamental first step for many analyses. When all jumps are static, the number of analysis steps is linear in the number of instructions: a fixed number of paths must be explored for each jump. With dynamic jumps, every possible destination must be explored at every jump; at worst, the number of steps can be quadratic in the number of instructions.

For a detailed explanation and examples of pathological programs, see EIP xxxx.

The quadratic behavior is not merely a theoretical concern. For Ethereum, it represents a denial-of-service vulnerability for any online static analysis tool — including bytecode validation and AOT or JIT compilation at runtime.

Backwards Compatibility

These changes are backwards compatible.

There are no changes to the semantics of existing EVM code. (With the caveat that code with unspecified behavior might behave in different, unspecified ways. Such code was always broken.)

Opcode semantics are not affected by whether the contract is MAGIC. So valid code MUST execute identically in any contract, but in MAGIC contracts the code MUST be valid.

This proposal does not require maintaining two interpreters.

These changes do not foreclose EOF, RISC-V, or other changes. Neither do these changes preclude running the EVM in zero knowledge; as explained in EIP xxxx they can instead be a big win.

Test Cases

(Note: these tests are known to be outdated and incorrect.)

Simple routine

This should jump into a subroutine, back out and stop.

Bytecode: 0x60045e005c5d (PUSH1 0x04, CALLSUB, STOP, ENTERSUB, RETURNSUB)

Pc	Op	Cost	Stack	RStack
0	PUSH1	3	[]	[]
2	CALLSUB	8	[4]	[]
4	ENTERSUB	1	[]	[3]
5	RETURNSUB	5	[]	[3]
3	STOP	0	[]	[]

Output: 0x Consumed gas: 17

Two levels of subroutines

This should execute fine, going into two depths of subroutines.

Bytecode: 0x6800000000000000000c5e005c60115e5d5c5d (PUSH9 0x00000000000000000c, CALLSUB, STOP, ENTERSUB, PUSH1 0x11, CALLSUB, RETURNSUB, ENTERSUB, RETURNSUB)

Pc	Op	Cost	Stack	RStack
0	PUSH9	3	[]	[]
10	CALLSUB	8	[12]	[]
12	ENTERSUB	1	[]	[10]
13	PUSH1	3	[]	[10]
15	CALLSUB	8	[17]	[10]
17	ENTERSUB	1	[]	[10,15]
18	RETURNSUB	5	[]	[10,15]
16	RETURNSUB	5	[]	[10]
11	STOP	0	[]	[]

Consumed gas: 36

Failure 1: invalid jump

This should fail, since the given location is outside of the code-range. The code is the same as the previous example, except that the pushed location is 0x01000000000000000c instead of 0x0c.

Bytecode: 0x6801000000000000000c5e005c60115e5d5c5d (PUSH9 0x01000000000000000c, CALLSUB, STOP, ENTERSUB, PUSH1 0x11, CALLSUB, RETURNSUB, ENTERSUB, RETURNSUB)

Pc	Op	Cost	Stack	RStack
0	PUSH9	3	[]	[]
10	CALLSUB	8	[18446744073709551628]	[]

Error: at pc=10, op=CALLSUB: invalid jump destination

Failure 2: shallow return stack

This should fail at first opcode, due to shallow return_stack.

Bytecode: 0x5d5858 (RETURNSUB, PC, PC)

Pc	Op	Cost	Stack	RStack
0	RETURNSUB	5	[]	[]

Error: at pc=0, op=RETURNSUB: invalid retsub

Subroutine at end of code

In this example, the CALLSUB is on the last byte of code. When the subroutine returns, it should hit the 'virtual stop' after the bytecode, and not exit with error.

Bytecode: 0x6005565c5d5b60035e (PUSH1 0x05, JUMP, ENTERSUB, RETURNSUB, JUMPDEST, PUSH1 0x03, CALLSUB)

Pc	Op	Cost	Stack	RStack
0	PUSH1	3	[]	[]
2	JUMP	8	[5]	[]
5	JUMPDEST	1	[]	[]
6	PUSH1	3	[]	[]
8	CALLSUB	8	[3]	[]
3	ENTERSUB	1	[]	[8]
4	RETURNSUB	5	[]	[8]
9	STOP	0	[]	[]

Consumed gas: 29

Reference Implementation

(Note: this AI-generated implementation is likely incomplete and incorrect.)

The following is a Python implementation of an algorithm for validating EVM bytecode. This algorithm uses a stack of continuations to traverse the code, emulating its control flow and stack use, and checking for violations of the rules above. It runs in time proportional to the size of the code, and the size of the stack is at most proportional to the size of the code. An equivalent validation MUST be run at CREATE time.

from enum import Enum, auto
from typing import Optional, Tuple, List, Dict, Set

class ValidationResult:
    def __init__(self, is_valid: bool, error_type: Optional[str] = None, error_details: Optional[str] = None):
        self.is_valid = is_valid
        self.error_type = error_type
        self.error_details = error_details

class EVMOpcode(Enum):
    STOP = 0x00
    JUMP = 0x56
    JUMPI = 0x57
    JUMPSUB = 0x5e
    RETURNSUB = 0x5d
    PUSH0 = 0x5f
    PUSH1 = 0x60
    PUSH32 = 0x7f

class Validator:
    def __init__(self, code: List[int]):
        self.code = list(code)
        self.stack_heights: Dict[int, int] = {}  # PC -> height
        self.visited_pcs: Set[int] = set()

    def get_instr_info(self, pc: int) -> Optional[Tuple[int, int, int, int, bool]]:
        """
        Retrieve instruction information
        Returns: (op, size, pops, pushes, is_terminator)
        """
        if pc >= len(self.code):
            return None

        op = self.code[pc]

        # Determine instruction size
        if op == EVMOpcode.PUSH0.value:
            size = 1
        elif PUSH1 <= op <= PUSH32:
            size = 1 + (op - PUSH1)
        else:
            size = 1

        # Opcode stack deltas and termination status
        deltas = {
            EVMOpcode.STOP.value: (0, 0, True),
            EVMOpcode.JUMP.value: (1, 0, True),
            EVMOpcode.JUMPSUB.value: (1, 0, False),
            EVMOpcode.RETURNSUB.value: (0, 0, True),
            EVMOpcode.PUSH0.value: (0, 1, False)
        }

        # Default to (0, 0, False) if not in special cases
        p, u, t = deltas.get(op, (0, 0, False))
        return op, size, p, u, t

    def validate(self) -> ValidationResult:
        """
        Validate EVM bytecode
        Returns a ValidationResult object
        """
        # Worklist: (PC, height, last_push_val)
        worklist = [(0, 0, None)]

        while worklist:
            pc, height, last_push = worklist.pop()

            # Check for stack height consistency
            if pc in self.stack_heights:
                if self.stack_heights[pc] != height:
                    return ValidationResult(
                        is_valid=False,
                        error_type="STACK_MISMATCH",
                        error_details=f"Inconsistent stack height at PC {pc}"
                    )
                continue

            # Record stack height and visited program counter
            self.stack_heights[pc] = height
            self.visited_pcs.add(pc)

            # Get instruction details
            instr_info = self.get_instr_info(pc)
            if instr_info is None:
                return ValidationResult(
                    is_valid=False,
                    error_type="INVALID_INSTRUCTION",
                    error_details=f"Invalid instruction at PC {pc}"
                )

            op, size, p, u, is_term = instr_info

            # Validate new stack height
            new_height = height - p + u
            if new_height < 0 or new_height > 1024:
                return ValidationResult(
                    is_valid=False,
                    error_type="STACK_OVERFLOW",
                    error_details=f"Invalid stack height {new_height} at PC {pc}"
                )

            # Handle jump-related instructions
            if op in (EVMOpcode.JUMP.value, EVMOpcode.JUMPI.value, EVMOpcode.JUMPSUB.value):
                if last_push is None:
                    return ValidationResult(
                        is_valid=False,
                        error_type="STATIC_JUMP_REQUIRED",
                        error_details=f"Static push required for jump at PC {pc}"
                    )

                worklist.append((last_push, new_height, None))

                # For conditional jump (JUMPI), also add next sequential instruction
                if op == EVMOpcode.JUMPI.value:
                    worklist.append((pc + size, new_height, None))

            # For non-terminating instructions, prepare next instruction
            elif not is_term:
                # Capture PUSH value for next instruction
                val = (
                    int.from_bytes(self.code[pc+1:pc+size], 'big')
                    if size > 1
                    else 0
                )

                # Only propagate value for PUSH instructions
                push_val = val if PUSH0 <= op <= PUSH32 else None
                worklist.append((pc + size, new_height, push_val))

        # If we've processed all instructions without issues contract is valid
        return ValidationResult(is_valid=`True`)

Security Considerations

This proposal introduces no new security considerations beyond those already present in the EVM. Validated contracts will be more secure: they cannot execute invalid instructions, jump to invalid locations, or underflow/overflow the stack.

Copyright

Copyright and related rights waived via CC0.