Call and Return Opcodes for the EVM

Abstract

This is the smallest possible change to the EVM interpreter 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. 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.

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, automated proofs of correctness, and ahead-of-time and just-in-time compilers.

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 runrime compilation to machine 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-8173: "Static Control Flow for the EVM."

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:

1. All executable opcodes must be valid:

• They MUST have been defined in the Yellow Paper or a deployed EIP, they
• MUST NOT have been deprecated in a subsequent deployed EIP, and
• The INVALID opcode is valid.

2. The JUMP and JUMPI instructions

• MUST address a JUMPDEST,
• MUST NOT address immediate data, and
• MUST be preceded by a PUSH instruction, .

3. The CALLSUB instruction

• MUST address an ENTERSUB,
• MUST NOT address immediate data, and
• MUST be preceded by a PUSH instruction,

4. The number of items on the data stack and on the return stack

• MUST always be positive and less than or equal to 1024.

5. For all paths from a CALLSUB to a RETURNSUB

• the absolute difference between
  • the current stack pointer and
  • the stack pointer at the previous ENTERSUB
• MUST remain constant.

We provide a simple algorithm below for validating these constraints.

The guarantee of constant stack height prevents stack underflow, prevents stack overflow for non-recursive programs, breaks cycles in the control flow, and enables one-pass traversal of control-flow.

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. Subroutines 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 industry-standard instructions — CALLSUB, ENTERSUB, and RETURNSUB — sufficient to eliminate the need for dynamic jumps in synthesizing calls and returns.

Why no immediate arguments or code sections?

Primarily backwards compatability. Other reasons include:

• Immediate arguments for jump destinations 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, would impose syntactic restrictions that inhibit optimization. See EIP-3540: EOF - EVM Object Format and EIP-4750: EOF - Functions for complementary proposals that provide more structure.

Why the return-stack mechanism?

Register machines like x86, ARM, and RISC-V typically use a single stack for both data and return addresses. Stack machines from Turing's ACE through Forth, Java, Wasm, .NET and others use 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.

Are there 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.

Are there real-time performance gains?

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.

Does ZK-rollup efficiency improve?

Static control flow enables the construction of simpler, more efficient circuits for ZK verification. See EIP-8173 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?

Recovering a program's 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. Intuitively, the number of possible paths through code just explodes. At worst, the number of steps paths can go up as the square of the number of instructions. See EIP-8173 for a more detailed explanation and example exploit.

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

Backwards Compatibility

These changes are backwards compatible. Opcode semantics are not affected by whether the contract is MAGIC. So valid code MUST execute identically in any contract.

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.)

Therefore this proposal does not require maintaining two interpreters -- validation is done before the interpreter runs, and the interpreter is not required to care whether the code is valid.

These changes do not preclude running the EVM in zero knowledge; neither do they foreclose EOF, RISC-V, or other changes. They can instead be a 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 a recursive algorithm for validating that EVM bytecode satisfies the constraints given above. This algorithm traverses the code, emulating its control flow and stack use, and checking for violations of the rules. It runs in time proportional to the size of the code, and the depth of the stack is at most proportional to the size of the code. An equivalent algorithm MUST be run at CREATE time, and has been implemented by many of our clients in the past.

from typing import Optional, Tuple

class EVMOpcode:
    PUSH0 = 0x60
    PUSH32 = 0x7f
    JUMP = 0x56
    JUMPI = 0x57
    CALLSUB = 0xB0
    JUMPSUB = 0xB1

class Validator:
    def __init__(self, code: bytes):
        self.code = code
        self.stack_heights = {}
        self.visited_pcs = set()
        self.current_heights = []
        self.data_stack_height = 0
        self.return_stack_height = 0

    def validate(self) -> bool:
        """Validate EVM bytecode. Returns True for valid code."""
        return self._validate_recursive(0, 0, None)

    def _validate_recursive(self, pc: int, height: int, last_push: Optional[int]) -> bool:
        # Check if we are out of bounds
        if pc >= len(self.code):
            return False

        # Check for stack height consistency
        if pc in self.stack_heights:
            if self.stack_heights[pc] != height:
                return False
            return True  # Already processed this PC with correct height

        # 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 False

        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 False

        # Check stack depth limits
        if self.data_stack_height < 1 or self.data_stack_height > 1024:
            return False
        if self.return_stack_height < 1 or self.return_stack_height > 1024:
            return False

        # Handle subroutine calls
        if op == EVMOpcode.CALLSUB:
            self.current_heights.append(height)  # Track height for this CALLSUB
            if not self._validate_recursive(last_push, new_height, None):
                return False
            self.current_heights.pop()  # Restore height on return

        # Handle jump-related instructions
        if op in (EVMOpcode.JUMP, EVMOpcode.JUMPI, EVMOpcode.JUMPSUB):
            if last_push is None:
                return False
            
            if not self._validate_recursive(last_push, new_height, None):
                return False

            if op == EVMOpcode.JUMPI:
                if not self._validate_recursive(pc + size, new_height, None):
                    return False

        # For non-terminating instructions, prepare next instruction
        elif not is_term:
            val = (
                int.from_bytes(self.code[pc + 1:pc + size], 'big')
                if size > 1
                else 0
            )
            push_val = val if EVMOpcode.PUSH0 <= op <= EVMOpcode.PUSH32 else None

            if not self._validate_recursive(pc + size, new_height, push_val):
                return False

        return True  # Processed instruction successfully

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, underflow stack, or, in the absence of recursion, overflow stack.

Copyright

Copyright and related rights waived via CC0.