EIP-8173: Foundations of EVM Control Flow

Understanding EVM control flow and its relation to Ethereum's scaling roadmap

Abstract

This Informational EIP provides background for understanding control flow in the EVM: the history of control flow in computing, the foundations of control flow analysis, and the impact of static control flow on Ethereum’s scaling roadmap.

This document serves as background material for proposals for static control flow — past and current proposals for subroutines and static jumps, container-format functions, call and return opcodes, and static relative jumps and calls — for discussions around RISC-V migration and ZK verification infrastructure, and for discussions still to come.

Motivation

Historical Context

Babbage 1833: Jumps and Conditional Jumps

In 1833 Charles Babbage began the design of the Analytical Engine: a steam-powered, mechanical, Turing-complete computer. Programs were to be encoded on punched cards that controlled a system of rods, gears, and other machinery to implement arithmetic, storage (for 1,000 40-digit decimal numbers), and conditional jumps. Jumps were supported by cards that shuffled the card deck forwards or backwards a fixed number of cards.

Lovelace 1843: Computer Science and Machine Intelligence

The first published description of the Analytical Engine was in French, by L. F. Menabrea, 1842¹. The English translator, Ada Augusta, Countess of Lovelace, made extensive notes on the science of computer programming, and published her translation in 1843. The notes include her famous program for iteratively computing Bernoulli numbers — arguably the world’s first complete computer program — which used conditional jumps to implement the required nested loops.

In Lady Lovelace’s notes we also find her prescient recognition of the Analytical Engine’s power — “In enabling mechanism to combine together general symbols in successions of unlimited variety and extent, a uniting link is established between the operations of matter and the abstract mental processes of the most abstract branch of mathematical science.”¹ Here also we find what Alan Turing later called “Lady Lovelace’s Objection”² to the possibility of machine intelligence — “It can do whatever we know how to order it to perform. It can follow analysis; but it has no power of anticipating any analytical relations or truths. Its province is to assist us in making available what we are already acquainted with.”¹

Turing, 1946: Calls and Returns

In 1945 Alan Turing began designing his Automatic Computing Engine³ (ACE), completing the proposal in early 1946, in which he introduced the concept of calls and returns: “To start on a subsidiary operation we need only make a note of where we left off the major operation and then apply the first instruction of the subsidiary. When the subsidiary is over we look up the note and continue with the major operation.”

The ACE used mercury delay-line memory, including a return stack holding return addresses. The smaller Pilot ACE was for a time the world’s fastest computer.

Industry Practice: 1945 to present

Call and return facilities of various names … subroutines, procedures, functions, methods … and levels of complexity … link registers, return stacks, stack frames … have proven their worth across a long line of important machines over the last 80 years, including most of the machines I have programmed or implemented: physical machines including the Burroughs B5000, CDC 7600, IBM 360, PDP-11, VAX, Motorola 68000, and Intel x86, and virtual machines including those for Scheme, Forth, Pascal, Java, and WebAssembly.

A few connections show the range. The CDC 7600 had no stack at all: its return jump planted the return in the code itself — self-modifying code, Wheeler’s design for the EDSAC. A call wrote a branch back to the caller into the subroutine’s first word, then jumped to its second; the subroutine returned by jumping to its own first word and executing the planted branch. It was fast, and it made recursion and shared code impossible — each subroutine could hold only one return at a time. The IBM 360 kept the return address in a link register, and returning was a branch through it. The PDP-11, VAX, 68000, and x86 push return addresses onto the same stack as data — the stack-frame design that C made universal, and that stack-smashing exploits have abused ever since, precisely because return addresses live where data can overwrite them. The Burroughs B5000, built for Algol, gave its stack frames hardware protection. And Forth, like Turing’s ACE, keeps a separate return stack, sealed off from data — the design adopted by the proposals discussed below.

Especially relevant to the EVM’s design are the Java, WebAssembly (Wasm), and CLI (.NET) VMs. They share crucial common properties:

• they are represented with portable bytecode
• that can be directly interpreted
• with static control flow
• that can be validated before runtime
• and can be compiled to machine code at runtime
• in linear time.

The static control flow that supports linear-time compilers also supports any other code that needs to traverse the control flow of a program, traversing each edge only once.

Control Flow

Tools that must know what code does have to follow where control can go: walk the code, taking every jump. How much such a walk costs — and whether it is possible at all — depends on the code’s control flow. The EVM makes it cost more than it should.

Control Flow Graphs

A control flow graph (CFG) is a map of where control can go in a program:

• Nodes are the blocks of code — runs of instructions with one entry and one exit, executed together or not at all
• Edges are the possible moves between blocks: each jump to its destinations, each fall-through to the next block

A path is one possible route through the code from the start: which blocks, in which order. Every execution follows some path; a program with branches has many.

A complete and sound CFG represents all and only the possible paths of program execution and is a fundamental starting point for many downstream tasks, including many static analyses:

• validating bytecode before execution
• translating bytecode to other representations (virtual register code, machine code)
• automated formal security analysis
• and many more

The graph need not be drawn to be used: many tools simply walk the code, following the edges in place. Drawing the CFG is just such a walk that takes notes.

Dynamic Control Flow

Dynamic jumps make dynamic control flow possible. They also make quadratically complex control flow possible, and can make static analysis of control difficult to impossible. Physical machines run on dynamic jumps: every x86 return pops an address off the stack and jumps to it, and every IBM 360 return is a branch through a register. Hardware only executes — it never analyzes — so its instructions are designed for speed, not post-hoc analysis, which is why recovering the control flow of machine code remains hard to this day. Virtual machines are different: their code is validated when loaded, and is often the source for JITs and other downstream tools — and as we will show below, building and traversing a dynamic control flow graph can take quadratic space and time. So Java and Wasm do not support dynamic jumps, and CLI carefully restricts theirs.

EVM: Calls, Returns, and the Cost of Walking Code

The Ethereum Virtual Machine does not provide explicit facilities for calls and returns. Instead, they must be synthesized using the dynamic JUMP instruction, which takes its destination from the stack — and stores return addresses on the stack. Here is a complete program a compiler might emit this way, with the gas in the comments: a squaring routine, called from two places, computing 2² + 3².

        push RTN_A     ; 3   return address, as ordinary data
        push 2         ; 3
        push SQUARE    ; 3
        jump           ; 8   call SQUARE(2)
RTN_A:  jumpdest       ; 1   back, with 4 on the stack
        push RTN_B     ; 3
        push 3         ; 3
        push SQUARE    ; 3
        jump           ; 8   call SQUARE(3)
RTN_B:  jumpdest       ; 1   back, with 9 on the stack
        add            ; 3
        stop           ; 0   13 on the stack
SQUARE: jumpdest       ; 1
        dup1           ; 3
        mul            ; 5
        swap1          ; 3
        jump           ; 8   return — but to where?

Take a pencil and run it. The values resolve every jump for you: the first call enters SQUARE with 2, squares it, and the swap1 brings RTN_A to the top for the final jump home; the second call brings RTN_B. The program leaves 13 on the stack and consumes 79 gas — 38 for each call (17 through the call, 20 through SQUARE, 1 to land) and 3 for the add. One walk, and both answers: what it computes, and what it costs.

Now consider a tool that must answer “what does a call to SQUARE cost?” for every program, not just this one. It cannot run the code — it has no inputs, and running is what it is trying to price. So it walks the code the way you just did, but computing facts in place of values: this slot holds some argument; that slot holds the constant RTN_A. Walking code and computing facts in place of values is called symbolic execution, and most every tool that must know what code does — analyzers, optimizers, decompilers, provers — does some form of it.

On this program the walk goes through, because the return addresses are pushed constants that can be followed through the dup1 and swap1. But in general the address on the stack can be any value from anywhere — computed, stored, reloaded — and following it is hopeless. Then the walker standing on SQUARE’s final jump cannot tell whose call this walk belongs to: the destination might be RTN_A or RTN_B, and it must walk both returns. Each place that shares the routine doubles the walks. Twenty calls is a million walks — what the literature calls a path explosion. Faced with that, honest tools report what their users know too well: cost unknown.

With explicit calls and returns there is nothing to follow: every return goes back to its call. One walk, one number. Twenty calls, one path.

Nothing here is special to gas: every algorithm that walks the paths of any program computing facts — proving safety, finding bugs, decompiling, translating — splits at the same jumps and pays the same exponential cost, or worse.

EVM: Any Jump, Anywhere

Worse is available. The walker above at least had candidates — two labeled returns to try. When the destination is computed, the walker has no candidates at all, and must assume what the machine allows: any jump may go to any destination in the code. Consider these EVM programs and the easily generated series of longer programs like them … the really long ones make for nice exploits. It’s not important that at runtime gas isn’t random or that the jump will most often fail; what matters is that because the jump destination is taken from the stack it is impossible to know a priori where the jumps go, so every path must be explored.

   jumpdest           jumpdest          jumpdest          ...
   gas                gas               gas               ...
   jump               jump              jump              ...
   jumpdest           jumpdest          jumpdest          ...
   gas                gas               gas               ...
   jump               jump              jump              ...
   jumpdest           jumpdest          jumpdest          ...
   stop               gas               gas               ...
                      jump              jump              ...
                      jumpdest          jumpdest          ...
                      stop              gas               ...
                                        jump              ...
                                        jumpdest          ...
                                        stop              ...
                                                          ...

The control flow graphs for these programs make the problem clear. Each node is a block from the programs above — one entry (a jumpdest), one exit (a jump, or the final stop) — and each edge is a move the machine might make. Edges on the left are backwards branches; edges on the right are forwards branches. See how the tangle of edges goes up fast, faster than the programs get longer.

Merely drawing this graph costs the square of the code size: every block’s jump might reach every block, so the edges number the blocks times one less than the blocks — O(N²) — and any tool that must consider where jumps can go pays that price whether it draws the graph or not. Walking the graph costs far more. A walk that never revisits a block chooses among all the remaining blocks at every step, so the routes multiply by a growing factor each time:

Forking between two known returns doubles the walks — exponential. Forking among everything multiplies them by a number that grows with the code — factorial, which outruns every exponential. The edge count is what building or validating pays, and with dynamic jumps it is already quadratic; the walk count is what every deeper analysis pays — formal verification must consider the paths — and it is astronomical before the code is twenty blocks long.

In Java, Wasm, and CLI it is simply impossible to have programs like these.

For Ethereum, these behaviors are a denial-of-service vulnerability for any online static analysis, including bytecode validation and AOT compilation at contract creation time, and JIT compilation at runtime.

Even offline, dynamic jumps (and the lack of calls and returns) can cause static analyses of many contracts to become quadratically impractical, exponentially intractable, or even mathematically impossible. For further examples, consider these abstracts from a few recent papers on the problem. The last paper brings neural networks to bear, and still disassembles only most Solidity programs. There is an entire academic literature of complex, incomplete solutions to problems that static control flow renders trivial.

“Ethereum smart contracts are distributed programs running on top of the Ethereum blockchain. Since program flaws can cause significant monetary losses and can hardly be fixed due to the immutable nature of the blockchain, there is a strong need of automated analysis tools which provide formal security guarantees. Designing such analyzers, however, proved to be challenging and error-prone.”⁴

“The EVM language is a simple stack-based language … with one significant difference between the EVM and other virtual machine languages (like Java bytecode or CLI for .Net programs): the use of the stack for saving the jump addresses instead of having it explicit in the code of the jumping instructions. Static analyzers need the complete control flow graph (CFG) of the EVM program in order to be able to represent all its execution paths.”⁵

“Static analysis approaches mostly face the challenge of analyzing compiled Ethereum bytecode… However, due to the intrinsic complexity of Ethereum bytecode (especially in jump resolution), static analysis encounters significant obstacles.”⁶

“Analyzing contract binaries is vital … comprising function entry identification and detecting its boundaries… Unfortunately, it is challenging to identify functions … due to the lack of internal function call statements.”⁷

In my experience, to avoid the problems of dynamic control flow, VMs use static jumps, calls, and returns.

Static Control Flow and Ethereum Scaling

As laid out above, static control flow means that the destination of every jump or call is determinable a priori, before execution. This has concrete implications for Ethereum’s scaling roadmap, particularly around ZK verification, rollups, and future execution layer changes.

Static Control Flow and Rollups

ZK-Rollups

To understand why static control flow matters for ZK-Rollups⁸, we need to briefly understand how ZK systems verify computation:

• Execution Traces: When a transaction executes, it produces an execution trace: a concrete, step-by-step record of every opcode executed, with the values of the stack, memory, and storage at each step. The trace records what actually happened — including exactly where every jump went — so it is always linear in the number of steps executed.
• Circuits: A circuit is a mathematical model of a computation. For a ZK system, the circuit encodes the rules of the EVM: what states can follow from what prior states, how gas is consumed, which memory accesses are valid, etc. The circuit is a set of polynomial constraints that must all be satisfied. Crucially, the circuit encodes the rules for each opcode type (including the rule for JUMP), not the specific paths taken by any particular execution.
• Witnesses: The witness is the private data the prover supplies to demonstrate that a specific execution was correct. It includes the execution trace itself plus auxiliary data. The public inputs are the pre- and post-state roots — what the state was before and after the transaction.
• Proofs: A ZK proof is a cryptographic proof that the witness satisfies the circuit’s constraints, without revealing the witness itself.

A ZK-Rollup sequencer or prover batches many transactions, generates a ZK proof that all transactions executed correctly, and submits that proof to L1, where it is quickly verified. The prover works from the actual execution trace — it does not explore or enumerate possible paths. The jump destinations are already known because they were recorded when the transaction ran.

The benefits of static control flow for ZK proving are therefore not about path exploration, but about the efficiency of the code being proven and the tractability of the analyses that surround it:

• Leaner bytecode: Static jumps, explicit subroutine calls, and better stack discipline (eliminating SWAP/DUP workarounds) produce significantly smaller and simpler bytecode. Because the prover must process every opcode in the execution trace, fewer opcodes mean less work.
• Deployment-time validation: With static control flow, bytecode can be fully validated once at deployment in linear time — including stack underflow, static stack depths, and reachability — rather than requiring expensive per-execution checks or quadratic offline analysis. This is where the O(N²) CFG problem described above directly impacts ZK infrastructure: building and analyzing the CFG of legacy EVM code before constructing a circuit or a formal model requires quadratic work; static control flow reduces this to linear.
• Faster proof generation and lower hardware requirements follow directly from the above: fewer opcodes to prove and cheaper analysis reduce the compute and memory demands on rollup provers.

Optimistic Rollups

Optimistic Rollups assume transactions are valid but allow fraud proofs to dispute invalid state roots. A fraud proof re-executes the contested transaction and demonstrates that the submitted state root was wrong. Key implications of static control flow include:

• Bytecode validation: Static control flow allows contract bytecode to be fully validated at deployment in linear time, establishing safety properties that can be relied on during dispute resolution.
• Dispute resolution: When a fraud dispute arises, the dispute system must re-execute the contested transaction. The re-execution itself is deterministic regardless of control flow style, but static control flow makes the surrounding machinery — validators, formal checkers, and the interactive verification game — simpler to implement correctly and easier to reason about.
• Interactive verification: Some optimistic rollup designs use multi-round interactive verification games that bisect execution to identify the disputed step. Clear, structured control flow makes the bisection protocol more tractable and reduces the risk of edge cases in the dispute game implementation.

Static Control Flow and Code Generation

As already discussed, static control flow enables contracts to be compiled to machine code before execution, just-in-time or ahead-of-time. This is an obvious win for non-ZK clients, whether on L1, L2, or EVM-compatible chains.

Static Control Flow and RISC-V Migration

There are ongoing discussions within the Ethereum research community about potentially replacing the EVM with a RISC-V execution environment. RISC-V has a standard instruction set architecture that is seeing increasing use in the ZK community. One current strategy for creating a ZK-EVM is to compile an EVM interpreter like revm to RISC-V for use in a ZK-VM. Supporting RISC-V directly eliminates the overhead of the EVM interpreter. An EVM with static control flow opens up another strategy — compile the EVM code to RISC-V code. That gives good RISC-V code in one linear-time pass, and better code in multiple passes, altogether linear time.

A missing piece in this puzzle is that RISC-V is a 32-bit or 64-bit architecture, but the current EVM is a 256-bit architecture. For that purpose there are current proposals for 64-bit EVM opcodes. It’s also the case that the prover has the actual trace, and can tell how many bits are actually in use at each step of the computation, so the 256-bit registers might not be that big a problem.

Specification

Several EIPs, past and current, specify new EVM opcodes and semantics for static control flow: subroutines and static jumps, container-format functions, call and return opcodes, and static relative jumps and calls. They are all implemented with the standard Turing return stack architecture, and are for the most part compatible with each other. In particular, the simplest of them — three call and return opcodes — can be used to implement all of the others.

Rationale

Static control flow has been a cornerstone of efficient computation since Babbage and Turing. The EVM’s reliance on dynamic jumps is an anomaly among virtual machines and a significant barrier to analysis, compilation, and scaling. Proposals to introduce explicit call/return opcodes and enforce static control flow bring the EVM in line with industry best practices and unlock a range of optimizations critical to Ethereum’s scaling roadmap.

Static control flow is not a silver bullet. But it is a foundational piece that enables:

• Better tooling and security analysis for language developers and auditors
• Faster execution via compilation for non-ZK clients
• Future migrations to other execution environments (RISC-V, etc.)
• Efficient ZK proof generation for ZK-Rollups
• Cleaner fraud proofs for Optimistic Rollups

By making control flow explicit and enforceable, the EVM becomes compatible with the full ecosystem of optimization and analysis techniques that other VMs and processor designs have relied on for decades.

Security Considerations

This Informational proposal itself specifies no changes to the protocol. Therefore it has no direct security implications. It does not affect the security considerations of the proposals it describes; rather, it helps to motivate and contextualize them.

Copyright

Copyright and related rights waived via CC0.

Citation

Please cite this document as:

Greg Colvin (@gcolvin), "EIP-8173: Foundations of EVM Control Flow [DRAFT]," Ethereum Improvement Proposals, no. 8173, February 2026. Available: https://eips.ethereum.org/EIPS/eip-8173.