--- eip: 8337 title: Validated EVM Code description: Code prefixed with MAGIC bytes is proven at CREATE time to have fully static control flow and to never underflow the data stack. author: Greg Colvin (@gcolvin) , Martin Holst Swende (@holiman), Brooklyn Zelenka (@expede), John Max Skaller discussions-to: https://ethereum-magicians.org/t/eip-8337-validated-evm-code/29013 status: Draft type: Standards Track category: Core created: 2026-07-09 requires: 3541, 7979 --- ## Abstract Code can be prefixed with `MAGIC` bytes. `MAGIC` code is validated at `CREATE` time to ensure that it cannot execute invalid *instructions*, jump to invalid destinations, or underflow the *data stack*, that every return has a call to return from, and that within each *subroutine* the depth of the *data stack* at every *instruction* is the same on every *execution*. Stack overflow remains checked at run time, as the *data stack* is for all code today. The complete *control flow* of `MAGIC` code can be traversed in time and space linear in the size of the code, enabling validation, ahead-of-time (AOT) and just-in-time (JIT) compilation, automated proofs of correctness, formal analysis and more. Validation is optional: the *instructions* of [EIP-7979](./eip-7979.md) behave identically in validated and ordinary code. *Note: Significant assistance from AI is acknowledged, primarily for the reference implementation and its tests.* ## Motivation Dynamic jumps obscure the flow of control. A destination is a runtime value, so analysis must assume that any jump can reach any `JUMPDEST`. The possible control transfers therefore grow as jumps times destinations: quadratic in the size of the code. For tools that run when code deploys or executes, like validators and compilers to machine code, that is a denial-of-service vulnerability. For analyses done offline — formal analysis, even gas estimates — the state space can grow exponentially or worse. [EIP-8173](./eip-8173.md) lays out these foundations, with worked examples and the literature. Validation ends this: code that forgoes dynamic *control flow* is proven safe once, at `CREATE` time, and every downstream tool can rely on the proof. ## Specification > *The key words MUST and MUST NOT in this Specification are to be interpreted as described in RFC 2119 and RFC 8174.* ### `MAGIC (0xEF 0x79)` `MAGIC` is the two bytes `0xEF 0x79`. The byte after them is the *version*: it names the validation rules the code is proven against. `MAGIC` and the *version* together are the *header*. This EIP defines *version* `0x01`: the constraints below, over the instruction set of the adopting fork. After this EIP has been activated, code that begins with `MAGIC` MUST be `valid` under the rules its *version* names. That is the promise `MAGIC` makes: code so marked, if it is deployed, was proven `valid` when it was created. *Execution* begins immediately after the *header*; positions in the code — *PC* values and destinations — count from the first `MAGIC` byte. ### Validity `valid` code has fully static *control flow*: every transfer of control lands where the code says it does. Validation begins with the JUMPDEST analysis clients already run — the sequential scan, from the first byte after the *header*, that tells *instructions* from `PUSH` immediate data — and proves more: * the destination of every jump and call, * that every return has a call to return from, * that within each *subroutine* the depth of the *data stack* at every *instruction* is the same on every *execution*, and * that no *instruction* can find fewer items on the *data stack* than it removes and underflow it. *Execution* is defined in the Yellow Paper as a sequence of changes to the state of the Ethereum Virtual Machine (EVM). Exceptional halting conditions are properties of the machine state, checked before each *instruction* executes: if executing would violate one, *execution* halts instead — as the Yellow Paper puts it (§9.4.2), "no instruction can, through its execution, cause an exceptional halt." Proving that no *reachable* state violates a condition therefore proves that no *execution* can reach an exceptional halting state. That is what validation does — once, at `CREATE` time. The Yellow Paper defines six conditions: * State modification during a static call * Insufficient gas * More than 1024 stack items * Insufficient stack items * Invalid jump destination * Invalid *instruction* Validation proves the last three before the code ever runs: invalid *instructions* by Constraint 1, invalid jump destinations by Constraints 2 and 3, and insufficient stack items by Constraint 5. The first three remain runtime matters: whether the call is static is not knowable from the code, neither is the gas, and with recursion the depth of the stacks depends on data — see ["Why not prove overflow?"](#why-not-prove-overflow) in the Rationale. Validation considers only the code's *control flow* and *stack offsets*, never its data and computations. It follows both arms of every `JUMPI`, so it may traverse *paths* that data values would never let execute, and it rejects code with invalid *paths* even if they could never be taken. #### Definitions Graph theory, compilers, languages, virtual machines, and security all meet here, each with its own names for these ideas; the terms below are plain English, defined once and used exactly. The constraints below, and the discussion that follows, are stated in terms of these definitions. The first three are the machine state of EIP-7979. * ***data stack***: the EVM's stack of 256-bit words, at most 1024 deep. Its *depth* is the number of items on it. * ***return stack***: the stack of return addresses, pushed only by `CALLSUB`, popped only by `RETURNSUB`, and not otherwise accessible to EVM code. * ***PC***: the program counter — the position in the code, the index of the next *instruction* to execute. * ***instruction***: a byte of code that is not `PUSH` immediate data, as the sequential scan from the first byte after the *header* — JUMPDEST analysis — determines. * ***execution***: as the Yellow Paper defines it, a sequence of changes to the EVM state: one *instruction* at a time, beginning at the first *instruction* after the *header*, ending in a halt. * ***control flow***: the possible transfers of control: which *instruction* may execute after which — the next in sequence, or a jump's or call's destination. *Control flow* is *static* when every destination is fixed by the code alone. * ***control-flow graph***: the *control flow* drawn as a map: each *instruction* a node, each possible transfer an edge. * ***path***: a possible sequence of executed *instructions*, starting at the first *instruction*; validation follows both arms of every `JUMPI`, without regard to data values. * ***reachable***: on some *path*. Bytes on no *path* are data, and are ignored. * ***entry***: a `CALLDEST`. Control may arrive at an *entry* by a call, by a jump, or by falling through. * ***subroutine***: the code an *entry* owns: everything *reachable* from it without passing through another *entry*. It is a subgraph of the *control-flow graph*, not a contiguous stretch of bytecode. Constraint 4 requires every *reachable* *instruction* to belong to exactly one *subroutine*. * ***frame***: the span of a *path* from a `CALLSUB` to the `RETURNSUB` that pops the return address it pushed. Every *frame* begun by a `CALLSUB` starts at an *entry*. *Frames* nest; *execution* begins in no *frame* — the top level is *unframed*. A *frame* is one execution of a call, not the code it runs: a *subroutine* called twice gives two *frames*, and, since a jump to a `CALLDEST` pushes no return address, one *frame* may pass through several *subroutines*. * ***unframed entry***: the top level, and any *entry* reached by a jump or fall-through — rather than by a `CALLSUB` — from an *unframed* *entry*. A `CALLSUB` *frames* its callee; a jump does not. In `valid` code no *unframed entry* contains a `RETURNSUB`: there it could find no return address. * ***stack offset***: the depth of the *data stack*, minus its depth at the most recent *entry* in the current *frame* — or at the start of *execution*, if there is none. * ***net stack effect***: of an *entry*, the *stack offset* at the `RETURNSUB` that closes a *frame* begun at that *entry*. Items pushed minus items popped: positive, negative, or zero. * ***demand***: of an *entry*, the deepest the *data stack* can reach below its depth at the *entry*, along the *subroutine*'s *paths*: the items that must already be on the stack when it is entered. #### Constraints on `valid` code Code beginning with `MAGIC` MUST be `valid`. Constraint 1 requires every *instruction* to be defined. Constraints 2 and 3 prove the destinations of jumps and calls. Constraint 4 gives every *instruction* one *stack offset*, and makes a single linear traversal sufficient. Constraint 5 keeps both stacks safe from underflow. 1. Every *reachable* *instruction* MUST be a valid opcode: * it MUST have been defined in the Yellow Paper or a deployed EIP, * it MUST NOT have been deprecated by a subsequent deployed EIP, and * the `INVALID` opcode is `valid`. 2. Every *reachable* `JUMP` and `JUMPI` MUST be immediately preceded by a `PUSH`, whose immediate value is the destination. The destination MUST be a `JUMPDEST` or a `CALLDEST` *instruction* — immediate data is not an *instruction*. A jump to a `CALLDEST` enters the *subroutine*. 3. Every *reachable* `CALLSUB` MUST be immediately preceded by a `PUSH`, whose immediate value is the destination. The destination MUST be a `CALLDEST` *instruction*. A call to a `CALLDEST` enters the *subroutine*. 4. *Stack offsets* MUST be path-independent: * every *path* reaching an *instruction* MUST arrive with the same *stack offset* — its depth above the *subroutine's* *entry*; * every *frame* begun at a given *entry* MUST close with the same *net stack effect* — items pushed minus items popped by the call; and * every *reachable* *instruction* MUST belong to exactly one *subroutine*. 5. On every *path*: each *instruction* MUST find at least as many items on the *data stack* as it removes, and each `RETURNSUB` MUST find a return address on the *return stack*. A *subroutine* is validated once, in terms of *stack offsets*, no matter how many call sites — `CALLSUB`s that target it — invoke it at different absolute depths, and no matter how many jumps enter it without a call. Code that several *subroutines* share is entered as a *subroutine* of its own; a `CALLDEST` costs what a `JUMPDEST` costs. Each *entry*'s *net stack effect* is a constant, so the *stack offset* at every return point is static. Loops must be stack-neutral per iteration — a backward branch arrives at the *stack offset* it left — so each *instruction* need be visited only once. #### Validation `MAGIC` code MUST be validated against the constraints above at `CREATE` time, in time and space linear in the size of the code. Validation MUST be run on the *output* of the initialization code, *before* that output can ever be executed by the interpreter, and *failure of validation is an exceptional halting state of the `CREATE`*. Validity is defined against an instruction set, and instruction sets change. Each fork that changes the *instructions* available MUST define validation over the full instruction set of that fork, and MUST assign the rules a new *version*. At `CREATE`, code beginning with `MAGIC` MUST carry the *version* of the creating fork's rules, and MUST pass them; either failure — a wrong *version*, or invalid code — is a validation failure. Contracts created under earlier forks remain deployed, their *versions* naming the rules that admitted them; reaching an opcode deprecated by a later fork is an exceptional halting state, as reaching an undefined opcode is today. Validation is a one-time cost, charged to the creator: `CREATE` MUST charge `VALIDATION_BYTE_COST` gas for each byte of code. `VALIDATION_BYTE_COST` is provisionally 64, sized to the measured worst case of native validation; the final value is deferred to the gas schedule of the adopting fork. The basis is under ["What does validation cost?"](#what-does-validation-cost) in the Rationale. The *version* is also the *header*'s extension point: an EIP that needs the *header* to carry more defines a *version* whose rules include it. Nothing beyond the three bytes is fixed here. ***Clients MUST implement validation, natively or by any equivalent means.*** The requirement is modest — the `validate()` function of the executable reference below is circa 170 lines, with shared test vectors. *Note: The Java Virtual Machine, WebAssembly, and .NET's Common Language Runtime enforce similar constraints for similar reasons.* ### Semantics versus Syntax 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* are defined as *subgraphs* of the *control-flow graph*, not contiguous sequences of bytecode. The EVM is a simple state machine: each *instruction* advances it one step, and the *control-flow graph* maps where it can step. 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. With no syntactic constraints and minimal semantic constraints, we maximize opportunities for optimization — call elimination, shared epilogues (one exit sequence shared by many *paths*), and other cross-*subroutine* techniques — and for patterns like mutual recursion, multiple *entry*, and state-machine dispatch. Since we want to support compilation of EVM code to native code on the node — as code deploys or runs — it is crucial that the EVM code be as well optimized as possible by high-level-language compilers — upfront and offline. ## Rationale ### Why validation? By marking `MAGIC` contracts as `valid` we are promising that their *control flow* is static, and the many tools that traverse the *control flow* can know this without inspecting the code for themselves. Today each side does the best it can with the machine as it is: compilers synthesize calls and returns from dynamic jumps, and tools work to recover what the compilers synthesized — effort on both sides that no one chose. With this proposal it will at least and at last become possible to write static EVM code, and the workarounds can retire with the problem. As a demonstration, `extract_cfg.py`, provided with the reference implementation, recovers the complete *control-flow graph* of validated code in a single linear pass. It trusts validity and performs no checks of its own. Validation also retires runtime work: for `valid` code, JUMPDEST analysis, the per-jump destination check, and the per-*instruction* underflow check are all unnecessary — each was proven at `CREATE` time. More important, validation makes translation legal: with every destination proven and every *instruction* at one static *stack offset*, `valid` code can be translated — once, at deploy, in linear time — to forms a client executes far more cheaply. Measured with the demonstration compiler and translators among the assets of [EIP-7979](./eip-7979.md), on five kernels — a dependent chain of multiplies, a tree of calls, a shift-and-xor mixer, Euclid's algorithm, and a store-and-sum over memory: a register intermediate code, interpreted, runs in 1.4x to 2.1x fewer machine *instructions* than interpreted bytecode, and 2.8x to 3.3x composed with 64-bit arithmetic *instructions*; RISC-V machine code from a deliberately naive translator runs in 4.2x to 7x fewer, and 19x to 51x composed; the same code through an optimizing compiler, 33x to 971x. The first two kernels' binaries executed in a 64-bit RISC-V zero-knowledge virtual machine (zkVM) cost the prover exactly the measured *instruction* counts, plus a constant startup. Gas metering and the runtime checks this proposal cannot retire — stack overflow, return depth — are included in every measurement. ### Why these bytes? `0xEF` because [EIP-3541](./eip-3541.md) reserved it: no code beginning with it has been deployable since London. The second byte avoids the two values that could collide — `0x00`, the magic of the EOF container format, and `0xF0`, the second byte of one contract deployed before London — and among the rest `0x79` is as good as any. One *version* byte, because validation rules will change a few times a decade, not a few times a year. ### Why is validation optional? **Backwards compatibility**. We cannot require existing code to become `valid`, and in a large, open ecosystem we cannot force an adoption schedule. ### Why not prove overflow? Because in general it cannot be done. With recursion, the depth of the stacks depends on data, so no static proof exists. Without recursion overflow can be proven — the accompanying `overflow_validator.py` proves it — but then every safety claim carries the qualifier "in the absence of recursion", and this proposal prefers unqualified claims. So overflow keeps the runtime check all code has today: a bounds comparison per push, in our estimate a small percent of an interpreter's time, and one comparison per call for the *return stack*. And nothing is lost to tools: each *subroutine's* growth above its *entry* is computable offline, in linear time, so a client can replace the per-push bounds check with one check per call, cached per code hash as JUMPDEST analysis is cached today, with no consensus needed. ### How can you prove underflow? Because, unlike overflow, it is a property of the code alone. Underflow is an *instruction* finding fewer items on the stack than it removes. For a *subroutine*, the items at risk are the ones below its own starting depth — items already on the stack when it is entered: its *demand* counts them, and because *stack offsets* are static, that count is a fixed number. So the validator computes each *subroutine's* *demand*, then checks every way in: each call site, and each jump or fall-through into the *entry*. If the *subroutine* arriving there has pushed enough items of its own, the *demand* is met. If it has pushed too few, the missing count is added to its own *demand*, to be met in turn where *it* is entered — if a *subroutine* needs three items and its caller has pushed only one, the caller now needs two. The checking repeats until nothing changes, and it must stop, recursion or not, because *demands* are counts that never go down and can never exceed 1024. *Execution* begins with an empty stack, so nothing lies below top-level code's start: it validates only if its *demand* is zero. ### Is the validation algorithm sound and complete? A validator is *sound* if it accepts only code that meets the constraints, and *complete* if it accepts all code that does. Throughout this proposal the constraints are read over every *path* of the *control-flow graph*, whether or not data would ever take it. The reference algorithm is both sound and complete, constraint by constraint. * *Constraints 1, 2 and 3* are properties of single *instructions*: the opcode is defined; a `PUSH` immediately precedes each jump and call; and its value is a `JUMPDEST` or `CALLDEST` that is not immediate data. The traversal visits exactly the *reachable* *instructions* and checks each one on the spot, so it accepts precisely the code that satisfies them. * *Constraint 4* is what the traversal records. On first arrival at an *instruction* it records the *stack offset* and the *entry*, and every later arrival must match. On the first `RETURNSUB` that closes a *frame* begun at an *entry* it records the *entry's* *net stack effect*, and every later one must match. A mismatch violates one of the three clauses, and every violation is a mismatch on some arrival, so the check is exact. The third clause is what lets the rest be computed per *subroutine*: nets and *demands* are kept per *entry*, and an *instruction* reached from two *entries* would have no one *entry* to charge it to. * *Constraint 5* has two halves. * *The *data stack*.* With path-independent offsets, an *instruction's* depth relative to its *entry* is a single number. So "finds at least as many items as it removes, on every path" reduces to the *demand* computation: the deepest an *entry's* own code reaches below its base, less the items each parent supplies at the point of entrance, propagated up to the top level, which has nothing to supply. This is a restatement, not an approximation. The limit turns away only *demands* that no stack could satisfy, which underflow on every *path*. * *The *return stack*.* Call an *entry* *unframed* if it is the top level, or is reached by a jump or fall-through from an *unframed entry*. A `CALLSUB` *frames* its callee, and a return point keeps its caller's framing. The algorithm rejects exactly when an *unframed entry* contains a `RETURNSUB`. If it rejects, then a chain of jumps from the top level reaches that *entry* with no `CALLSUB` on it, so some *path* reaches the `RETURNSUB` with every `CALLSUB` already returned: a violation. Conversely, if some *path* reaches a `RETURNSUB` with no unreturned `CALLSUB`, delete its returned call–return pairs. What remains is a chain of jumps and fall-throughs from the start into the *entry* containing the `RETURNSUB`, through *entries* reached the same way, each *unframed* by definition. So that *entry* is *unframed* and contains a `RETURNSUB`, and the algorithm rejects. Code with no `RETURNSUB` may be shared between *framed* and *unframed entries*, as the constraint allows. ### What does validation cost? Little. Measured natively (`native-cost/`) on one 2.6 GHz Intel core, ordinary code validates at 12–14 nanoseconds per byte, the sequential scan included. The worst case is code built to pump *demands* around a recursive cycle — invalid code, paying to be refused — at a measured 587 nanoseconds per byte, bounded as ["Why it is linear"](#why-it-is-linear) argues. `VALIDATION_BYTE_COST` at its provisional 64 covers the worst case with margin: about thirty percent on top of today's roughly 216 gas per byte of deployment, charged by `CREATE` and paid by the creator. There is nothing for an attacker to buy — the worst case is the priced case. A contract that fails validation consumes its gas, as reverting initialization code does. ### Why are the arguments to `JUMP` and `JUMPI` restricted in `MAGIC` code? Constraint 2 requires that `JUMP` and `JUMPI` in `MAGIC` code be immediately preceded by a `PUSH` *instruction*, making their destinations compile-time constants. The destination may be a `JUMPDEST` or a `CALLDEST`. A jump to a `CALLDEST` enters the *subroutine* without a call — call elimination, discussed in [EIP-7979's Rationale](./eip-7979.md#why-may-jump-land-on-a-calldest). Within a *subroutine*, jumps go to `JUMPDEST`s; between *subroutines*, control enters at an *entry*, by call or by jump. Computed jumps stay out: destinations remain compile-time constants, so the *path* explosions [described below](#how-can-dynamic-jumps-explode-control-flow-analysis) cannot occur. A jump into another *subroutine* remains invalid except at an *entry*. Making a point enterable costs one `CALLDEST` byte, and keeps every cross-*subroutine* transfer visible to one-pass analysis. ### How can dynamic jumps explode control flow analysis? Recovering a program's *control flow* is a fundamental first step for many analyses. When all jumps are static, each jump has a fixed set of successors, and the analysis is linear in the size of the code. With dynamic jumps every destination must be considered at every jump: the possible transfers grow quadratically, and analyses that must follow the *paths* through them grow exponentially. [EIP-8173](./eip-8173.md) develops these costs with worked examples. For Ethereum they are a denial-of-service vulnerability for tools that run at `CREATE` time or at runtime, and even offline they render many analyses impractical, intractable, or impossible. ## Backwards Compatibility Validation is opt-in and changes no semantics. No deployed contract begins with `MAGIC`: [EIP-3541](./eip-3541.md) has refused every deployment beginning with `0xEF` since London, and the three deployed before it are `0xEF` alone, twice, and `0xEF 0xF0…`. So no existing code is affected. A chain on which code beginning with `MAGIC` is already deployed MUST NOT activate this EIP. Opcode behavior is not affected by the prefix: the same code runs identically with or without it. Validation of `MAGIC` code is done before the interpreter runs, so the interpreter never sees `MAGIC` code that is not `valid`. Clients need not maintain two interpreters. ## Test Cases *Note: the bytecode strings in these tests use the opcode values `0xBB`=`CALLDEST`, `0xBC`=`CALLSUB`, `0xBF`=`RETURNSUB`.* ### Validation *The following bytecodes exercise the validator itself: the last column is the expected result of `validate()`. They are run by `test_validator.py`, which accompanies the reference implementation, with `STACK_LIMIT` reduced to 16 so that the overflow examples stay small; the algorithm is independent of the limit.* The tables group the cases by the constraint they exercise, and three verdicts carry most of the lessons. The `PUSH`-data impostors — `JUMPDEST` or `CALLDEST` bytes buried in immediate data — are refused whatever their values: the sequential scan already ruled them out. Recursion validates even with no base case, because validation follows *control flow*, not data. And the overflow rows all validate, because overflow is the runtime check — see ["Why not prove overflow?"](#why-not-prove-overflow). **The runtime test cases of EIP-7979** | Test | Bytecode | Valid | |-----------------------------|------------------------------|-------| | simple routine | `0x6004BC00BBBF` | yes | | two levels of subroutines | `0x6004BC00BB6009BCBFBBBF` | yes | | destination outside code | `0x60FFBC00BBBF` | no | | bare `RETURNSUB` | `0xBF` | no | | subroutine at end of code | `0x600556BBBF5B6003BC` | yes | **Constraint 1: opcodes** | Test | Bytecode | Valid | |-----------------------------------|------------------|-------| | lone `STOP` | `0x00` | yes | | undefined opcode | `0x21` | no | | `INVALID` is `valid` | `0xFE` | yes | | undefined opcode at return point | `0x6004BC21BBBF` | no | **Constraints 2 and 3: destinations** | Test | Bytecode | Valid | |--------------------------------|------------------|-------| | `JUMP` into `PUSH` immediate | `0x600156` | no | | `JUMPDEST` byte inside `PUSH` data | `0x600456605B00` | no | | `CALLDEST` byte inside `PUSH` data | `0x6004BC60BB00` | no | | `JUMPDEST` in unreachable code | `0x600456005B00` | yes | | `JUMP` to visited non-`JUMPDEST` | `0x5F5F01600256` | no | | `JUMP` not preceded by `PUSH` | `0x365B56` | no | | `PUSH0`-preceded `JUMP` | `0x5B5F56` | yes | | `CALLSUB` to `JUMPDEST` | `0x6004BC005B` | no | **Constraint 4: offsets and net effects** | Test | Bytecode | Valid | |-------------------------------|----------------------------------|-------| | `JUMPI` arms disagree at join | `0x366005575F5B00` | no | | `JUMPI` diamond, consistent | `0x366006575F005B5F00` | yes | | two `RETURNSUB`s disagree | `0x6004BC00BB36600A57BF5B5FBF` | no | | two `RETURNSUB`s agree | `0x6004BC00BB36600A57BF5B5F50BF` | yes | | stack-neutral loop | `0x5B600056` | yes | **Constraint 5: underflow and the return stack** | Test | Bytecode | Valid | |---------------------------------------|----------------------------------|-------| | `ADD` on empty stack | `0x01` | no | | `POP` on empty stack | `0x50` | no | | subroutine consumes caller argument | `0x6002600BBC6003600BBC00BB8002BF` | yes | | subroutine underflows caller | `0x6004BC00BB5050BF` | no | | fall into subroutine, then `RETURNSUB` | `0xBBBF` | no | **Reuse and multiple entry points** | Test | Bytecode | Valid | |----------------------------|------------------------------------|-------| | called at two depths | `0x6002600BBC6003600BBC00BB8002BF` | yes | | fall-through second entry | `0x6008BC5F600ABC00BB5FBB50BF` | yes | **Recursion** | Test | Bytecode | Valid | |------------------------------|------------------------|-------| | recursion, no base case | `0x6004BC00BB6004BCBF` | yes | | recursion eats caller stack | `0x6004BC00BB506004BC` | no | **Jumps to a `CALLDEST` (call elimination)** | Test | Bytecode | Valid | |-------------------------------|----------------------------------|-------| | jump to a `CALLDEST` | `0x6004BC00BB5F600956BB50BF` | yes | | conditional jump to a `CALLDEST` | `0x6004BC00BB36600A57BFBBBF` | yes | | jump to a `CALLDEST`, net effects disagree | `0x6004BC00BB5F36600B57BFBB50BF` | no | | unframed jump to a called subroutine | `0x6006BC600656BBBF` | no | **Framing is a property of entries** | Test | Bytecode | Valid | |-----------------------------------------------|------------------------------------|-------| | revert block shared by the top level and a subroutine | `0x36600C576008BC00BB600C56BB5F80FD` | yes | | entered by jump and by call, returns | `0x366008576008BC00BBBF` | no | | framed chain: called, jumps on, returns | `0x6004BC00BB600856BBBF` | yes | | unframed chain: jumped to, jumps on, returns | `0x600356BB600756BBBF` | no | | unframed chain of three links, no return | `0x600356BB600756BB600B56BB00` | yes | | unframed chain of three links, returns | `0x600356BB600756BB600B56BBBF` | no | **Overflow is not validated** | Test | Bytecode | Valid | |---------------------------------------|--------------------------------------|-------| | 17 pushes | 17 × `PUSH0`, `STOP` | yes | | stack growth amplified by two calls | `0x6007BC6007BC00BB5F5F5F5F5F5F5F5F5FBF` | yes | | call chain, depth 17 | `call_chain(17)` in `test_overflow.py` | yes | | growing recursion | `0x6004BC00BB5F6004BC` | yes | ## Reference Implementation The reference implementation below is Python: executable and tested. It validates EVM bytecode against the five constraints defined above, in time and space linear in the size of the code, in circa 210 lines — the `validate()` function itself is circa 170. It is embedded here so that this EIP reads as a single document, and provided as a separate file, `validator.py`. The reference and its test vectors carry no *header*; behind one, every position shifts by its three bytes. Beside it are its opcode table, `opcodes.py`; the test suite `test_validator.py`, which runs all the validation test cases above, its vectors shared with `test_overflow.py`; the one-pass control-flow-graph extractor `extract_cfg.py`; and, in `native-cost/`, the C port that measures validation's native cost. The validator that additionally proves overflow for non-recursive code is `overflow_validator.py` — kept for comparison; see ["Why not prove overflow?"](#why-not-prove-overflow). ### Algorithm #### The idea Every client already scans deployed code, before executing it, to tell *instructions* from `PUSH` immediate data: JUMPDEST analysis. Validation runs that scan first, then traverses the code the way *execution* would: starting at the first *instruction*, following every jump and call, except that where *execution* takes one arm of a `JUMPI`, the traversal takes both. The traversal is confined to the *instructions* the scan found — `PUSH` immediate data can never be executed or jumped to, whatever its bytes. Bytes the traversal never reaches are data, just as unreachable bytes are today. The traversal visits every *reachable* *instruction* exactly once. What makes once enough is measuring the *data stack* relative to the *subroutine* being traversed: at a `CALLDEST` the depth count resets to zero, and every check inside is phrased as an offset from that start. A *subroutine* therefore looks the same from all the `CALLSUB`s that invoke it, however deep their stacks, and checking it once covers them all. Constraint 4 completes the argument: every *path* to an *instruction* must arrive at the same offset, so a second arrival adds nothing new. For the same reason a loop is traversed once, since its backward branch must arrive at the offset it left. The *instruction* after a `CALLSUB` is reached when the *frame* begun at the callee returns, at a depth that depends on what the callee did: the call-site offset plus the callee's *net stack effect*. So a return point cannot be visited until its callee's net is known. Return points wait on a pending list until that net is first fixed — by a `RETURNSUB` reached from the callee's *entry*, in whatever *subroutine* it lies. If a callee never returns, its return points are never visited. That is correct: they are unreachable. #### The details Each step of the traversal visits one *instruction*, knowing four things: its position; the *stack offset* on arrival; which *subroutine* it is in — that is, which `CALLDEST` it was reached from, or top-level code; and the value of the immediately preceding `PUSH`, if any, since that is where `JUMP`, `JUMPI`, and `CALLSUB` destinations come from. The first visit to an *instruction* records the offset and the *subroutine*; every later arrival must match both, or the code is invalid. Offsets must match by Constraint 4. *Subroutines* must match because the *net stack effects* are kept per *subroutine*: if *paths* from two different `CALLDEST`s could rejoin, there would be no one *subroutine* to charge the *instructions* to. Whether a `RETURNSUB` will find a return address is a property of the *subroutine* it is in, not of the *path* that reached it. The traversal records the jump and fall-through links between *entries* — a `CALLSUB` makes no such link, since it *frames* its callee — and which *entries* contain a `RETURNSUB`. Afterwards, framing is propagated over those links: the top level is *unframed*, and so is every *entry* that an *unframed entry* jumps or falls into. An *unframed entry* containing a `RETURNSUB` is invalid, since a *path* through the *unframed entry* reaches the `RETURNSUB` with no unreturned `CALLSUB` on it. Code shared between *framed* and *unframed entries* is otherwise unconstrained: a revert block reached both from the top level and from inside *subroutines* is `valid`, since nothing about it touches the *return stack*. Destinations are checked in whichever order the traversal reaches them. If the destination is already visited, its opcode is checked on the spot: a `JUMPDEST` or `CALLDEST` for jumps, a `CALLDEST` for calls. If it is not yet visited, the requirement is recorded and checked when the traversal first arrives there. A destination inside `PUSH` data can never satisfy either check: the scan has already ruled such bytes out, whatever their values. A `CALLDEST` is always visited as the start of its own *subroutine*, at offset zero. Reaching one some other way — by falling through, or by a jump — links the two *subroutines*: whatever the entered *subroutine's* *net stack effect* turns out to be, the entering *subroutine's* is the offset at the entrance plus that, since from there on their fates are the same. The reference implementation below follows this section, and each check in it is annotated with the constraint it enforces. ### Python ```python """Reference validator for EIP-8337 MAGIC code. Abridged: the complete file, validator.py, accompanies this EIP; it imports its opcode table from opcodes.py. """ from collections import defaultdict, deque from opcodes import (JUMP, JUMPI, JUMPDEST, CALLSUB, CALLDEST, RETURNSUB, PUSH0, PUSH32, opcode_info, push_value) STACK_LIMIT = 1024 OUTER = None # stands for the entry of top-level code LABEL = "label" # destination must be a JUMPDEST or a CALLDEST ENTRY = "calldest" # destination must be a CALLDEST def validate(code, stack_limit=STACK_LIMIT): """True iff the code satisfies the five constraints of EIP-8337 validation: valid opcodes, proven destinations, one static stack offset per instruction, framed returns, and no underflow. Framing is a property of entries: no entry reachable by jumps from the top level may contain a RETURNSUB.""" if len(code) == 0: return False # JUMPDEST analysis: the sequential scan from position 0 that every # client runs today. Its instructions are the only bytes that may # be executed or jumped to; PUSH immediate data never qualifies, # whatever its values (Constraints 2 and 3). instructions = set() i = 0 while i < len(code): instructions.add(i) i += 1 + (code[i] - PUSH0 if PUSH0 < code[i] <= PUSH32 else 0) visited = {} # pc -> (offset, entry) at first visit required = {} # pc -> LABEL or ENTRY, set by jumps and calls net_effect = {} # entry -> its *net stack effect*, once known inputs = defaultdict(int) # entry -> its demand: the items it needs from its caller # Two parent lists with different lifetimes. parents is permanent # and complete — every call and enter — for propagating demands in # the demand checking. enter_parents holds only arrivals whose entry's # net is still unknown; each record is consumed exactly once, when # that net is first set. parents = defaultdict(list) # child -> [(parent, offset)] enter_parents = defaultdict(list) # entry -> [(parent, offset)] pending = defaultdict(list) # entry -> return points waiting on its net jump_children = defaultdict(list) # entry -> entries it jumps or falls into returning = set() # entries that contain a RETURNSUB work_items = [(0, 0, OUTER, None)] def resolve(entry, value): """Record an entry's net: release the return points waiting on it, and settle the entries that jump or fall into it, whose nets follow from this one. False on a conflict.""" settle = [(entry, value)] while settle: e, v = settle.pop() if e in net_effect: if net_effect[e] != v: return False # Constraint 4: one net per entry continue net_effect[e] = v for ret_pc, offset, caller in pending.pop(e, ()): work_items.append((ret_pc, offset + v, caller, None)) for parent, d in enter_parents[e]: settle.append((parent, d + v)) return True while work_items: pc, offset, entry, push = work_items.pop() if pc >= len(code): continue # implicit STOP: a valid end if pc not in instructions: return False # Constraints 2, 3: immediate data op = code[pc] size, pops, pushes, term = opcode_info(op) if size == 0: return False # Constraint 1: not a valid opcode # A CALLDEST is visited at offset 0, as its own entry; arriving # any other way first records the link between the subroutines. if op == CALLDEST and (entry != pc or offset != 0): parents[pc].append((entry, offset)) jump_children[entry].append(pc) if pc in net_effect: # settled: the arriving net follows if not resolve(entry, offset + net_effect[pc]): return False else: # each record is consumed exactly once enter_parents[pc].append((entry, offset)) offset, entry = 0, pc if pc in visited: # Constraint 4: paths must agree. if visited[pc] != (offset, entry): return False continue visited[pc] = (offset, entry) # Constraints 2 and 3: a required destination type, if any. if required.get(pc) == LABEL and op not in (JUMPDEST, CALLDEST): return False if required.get(pc) == ENTRY and op != CALLDEST: return False # Constraint 5: items used from below the subroutine's start. need = pops - offset if need > inputs[entry]: if need > stack_limit: return False inputs[entry] = need offset += pushes - pops nxt = pc + size if op == CALLSUB: if push is None: return False # Constraint 3: PUSH before CALLSUB dest = push if dest >= len(code): return False if dest in visited and code[dest] != CALLDEST: return False required[dest] = ENTRY # a jump's LABEL upgrades to ENTRY parents[dest].append((entry, offset)) work_items.append((dest, 0, dest, None)) if dest in net_effect: # Return point: call-site offset plus the callee's net. work_items.append((nxt, offset + net_effect[dest], entry, None)) else: pending[dest].append((nxt, offset, entry)) elif op == RETURNSUB: returning.add(entry) if not resolve(entry, offset): return False elif op in (JUMP, JUMPI): if push is None: return False # Constraint 2: PUSH before JUMP/JUMPI dest = push if dest >= len(code): return False if dest in visited and code[dest] not in (JUMPDEST, CALLDEST): return False required.setdefault(dest, LABEL) work_items.append((dest, offset, entry, None)) if op == JUMPI: # and the fall-through arm work_items.append((nxt, offset, entry, None)) elif not term: # everything else falls through value = push_value(code, pc) if PUSH0 <= op <= PUSH32 else None work_items.append((nxt, offset, entry, value)) # Constraint 5, framing: the top level is unframed, and so is every # entry that an unframed entry jumps or falls into; no unframed entry # may contain a RETURNSUB. A worklist walks each jump link at most # once — a CALLSUB makes no link, since it frames its callee. unframed = {OUTER} work = [OUTER] while work: for e in jump_children[work.pop()]: if e not in unframed: unframed.add(e) work.append(e) if unframed & returning: return False # The demand checking: a subroutine's demand for caller items, less the # depth already on the stack at the entrance, becomes its parent's # demand. Demands only rise and the limit caps them, so this ends. queue = deque(e for e in inputs if inputs[e]) queued = set(queue) while queue: e = queue.popleft() queued.discard(e) for parent, d in parents[e]: need = inputs[e] - d if need > inputs[parent]: if need > stack_limit: return False inputs[parent] = need if parent not in queued: queue.append(parent) queued.add(parent) # Top-level code has no caller to take items from. return inputs[OUTER] == 0 ``` ### Why it is linear Space first. Every table has one row per *instruction* or one per *entry*, and the parent lists hold one record, a few numbers, for each call and each entrance the traversal finds. Space is O(n) for code of n bytes. Time is counted in work items. A work item says: visit this *instruction*, at this *stack offset*, in this *subroutine*. Each costs a bounded amount of work, a few table lookups, so the question is how many items there are. The first visit to an *instruction* creates at most two. A `JUMPI` creates one per arm. A `CALLSUB` creates one for the callee and one for the return point, which is held back until the callee's *net stack effect* is known and released once, when the callee's first `RETURNSUB` fixes it. Fixing a net also settles, once each, the *entries* that jumped or fell into that *subroutine*. A later arrival at a visited *instruction* compares offsets and creates nothing. So the items number at most about twice the *instructions*, and the traversal is O(n). The framing propagation that follows is a worklist over the jump links between *entries*. An *entry* is *unframed* at most once, and its links are walked only then, so each link is visited at most once: O(n) again. The *demand* checking — ["How can you prove underflow?"](#how-can-you-prove-underflow) in the Rationale — repeats. When a *subroutine* comes up short at some entrance, the shortfall raises the *demand* of the code entering there, and that code must be checked again. How much can the repetition cost? A *subroutine* is checked again only because its own *demand* just rose, and a *demand* is a whole number of stack items that never falls and cannot pass 1024. So no *subroutine* is checked more than 1024 times. Each check walks that *subroutine's* entrances once, and the entrances number O(n): one record per call, jump, or fall-through the traversal found. Time is O(1024 × n), which is still linear in the size of the code, because 1024 is the protocol's constant and not the adversary's choice. Only code built to pump *demands* around a recursive cycle approaches the bound: *subroutines* in a ring, each drawing items from the next, so that each round of checking raises every *demand* by one. That is invalid code, paying to be refused. Ordinary code settles in a round or two. Measured on a C port of the validator (`native-cost/`), on one 2.6 GHz Intel core, ordinary patterns — straight-line code, branch-dense code, *subroutines*, deep call chains — cost 12–14 nanoseconds per byte, and the *demand* pump 587. The Python reference runs at 3–4 microseconds per byte on the same ordinary patterns. ["What does validation cost?"](#what-does-validation-cost) in the Rationale prices these numbers. ## Security Considerations Validated contracts cannot execute invalid *instructions*, jump to invalid destinations, or underflow the *data stack*, and their return addresses are isolated from the *data stack*, so code cannot corrupt its own *control flow*. Stack overflow is checked at run time, as the *data stack* is for all code today. Validation is consensus-critical, and this proposal asks every client to implement it. The defenses are an executable specification, shared test vectors, and differential testing; the risks that remain are a divergence between implementations, and a fault in the specification itself admitting code that a later fork must deal with. A remediation mechanism for the latter is deferred. (Fork-driven changes to validity — see [Validation](#validation) — need no such mechanism: contracts validated under earlier forks simply remain deployed.) Validation is linear in the size of the code, its worst case measured and priced — see ["What does validation cost?"](#what-does-validation-cost). An attacker cannot impose more validation work on the network than they pay for. ## Copyright Copyright and related rights waived via [CC0](../LICENSE.md).