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.
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:
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."
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.
destination on top of the stack.PC + 1 to the return stack.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.
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:
return stack do not need to be validated, since they are alterable only by CALLSUB and RETURNSUB.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.)MAGIC values are still to be determined, but the MAGIC bytes will begin with 0xEF.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.
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:
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.
valid codeCode 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:
valid:
INVALID opcode is valid.JUMP and JUMPI instructions MUST be preceded by a PUSH instruction.JUMP and JUMPI instructions MUST NOT address immediate data, and MUST address a JUMPDEST.CALLSUB instruction MUST be preceded by a PUSH instruction.CALLSUB instruction MUST NOT address immediate data, and MUST address an ENTERSUB.data stack MUST always be positive and less than or equal to 1024.return stack MUST always be positive and less than or equal to 1024.stack height is the absolute difference between the current stack pointer and the stack pointer at the most recent ENTERSUB.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.
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.
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:
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.
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.
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.
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.
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.
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.
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.
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.
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.
(Note: these tests are known to be outdated and incorrect.)
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
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
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
return stackThis 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
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
(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.
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 and related rights waived via CC0.