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 behave identically in validated and ordinary code.
Note: Significant assistance from AI is acknowledged, primarily for the reference implementation and its tests.
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 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.
The key words MUST and MUST NOT in this Specification are to be interpreted as described in RFC 2119 and RFC 8174.
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.
Note: MAGIC values are still to be determined, but the MAGIC bytes will begin with 0xEF.
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 position 0 that tells instructions from PUSH immediate data — and proves more:
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:
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 4. 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?" 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.
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 position 0 — JUMPDEST analysis —
determines.
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
PC 0; 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. In valid code every reachable instruction belongs 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 an implicit outermost frame. 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.
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.
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 keeps both stacks safe from underflow.
Constraint 5 gives every instruction one stack offset, and makes a
single linear traversal sufficient.
Every reachable instruction MUST be a valid opcode:
it MUST have been defined in the Yellow Paper or a deployed EIP,
the INVALID opcode is valid.
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.
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.
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.
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 — and
A subroutine is validated once, in terms of stack offsets, no matter how many call sites — CALLSUBs that target it — invoke it at different absolute depths, and no matter how many jumps enter it without a call. 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.
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. At CREATE, code beginning with MAGIC MUST have a header naming the validation rules of the creating fork, and MUST pass them; either failure — a wrong header, or invalid code — is a validation failure. Contracts created under earlier forks remain deployed, their headers 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?" in the Rationale.
The layout of the MAGIC header is explicitly deferred to a follow-on specification: other EIPs also need to carry information in the header, and the layouts will need to be reconciled. Only the encoding is deferred: what the header identifies — the validation rules that admitted the code — is fixed above.
Clients MUST implement validation, natively or by any equivalent means. The requirement is modest — the validate() function of the executable reference below is circa 150 lines, with shared test vectors.
Note: The Java Virtual Machine, WebAssembly, and .NET's Common Language Runtime 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. 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.
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, on benchmark kernels bracketing arithmetic-heavy and call-heavy code: a register intermediate code, interpreted, runs in 1.5x to 2.1x fewer machine instructions than interpreted bytecode, and 3.2x to 3.3x composed with 64-bit arithmetic instructions; RISC-V machine code runs in 4.7x to 7x fewer, and 19x to 51x composed. The same 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.
Backwards compatibility. We cannot require existing code to become valid, and in a large, open ecosystem we cannot force an adoption schedule.
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.
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.
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" 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.
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. Within a subroutine, jumps go to JUMPDESTs; 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 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.
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 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.
Validation is opt-in and changes no semantics. No deployed contract begins with the MAGIC bytes — EIP-3541 reserved them — so no existing code is affected. 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.
Note: the bytecode strings in these tests use placeholder opcode values
0xB0=CALLSUB, 0xB1=CALLDEST, 0xB2=RETURNSUB, which are to be
confirmed when final opcode assignments are made.
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?".
The runtime test cases of EIP-7979
| Test | Bytecode | Valid |
|---|---|---|
| simple routine | 0x6004B000B1B2 |
yes |
| two levels of subroutines | 0x6004B000B16009B0B2B1B2 |
yes |
| destination outside code | 0x60FFB000B1B2 |
no |
bare RETURNSUB |
0xB2 |
no |
| subroutine at end of code | 0x600556B1B25B6003B0 |
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 | 0x6004B021B1B2 |
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 |
0x6004B060B100 |
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 |
0x6004B0005B |
no |
Constraint 4: underflow and the return stack
| Test | Bytecode | Valid |
|---|---|---|
ADD on empty stack |
0x01 |
no |
POP on empty stack |
0x50 |
no |
| subroutine consumes caller argument | 0x6002600BB06003600BB000B18002B2 |
yes |
| subroutine underflows caller | 0x6004B000B15050B2 |
no |
fall into subroutine, then RETURNSUB |
0xB1B2 |
no |
Constraint 5: offsets and net effects
| Test | Bytecode | Valid |
|---|---|---|
JUMPI arms disagree at join |
0x366005575F5B00 |
no |
JUMPI diamond, consistent |
0x366006575F005B5F00 |
yes |
two RETURNSUBs disagree |
0x6004B000B136600A57B25B5FB2 |
no |
two RETURNSUBs agree |
0x6004B000B136600A57B25B5F50B2 |
yes |
| stack-neutral loop | 0x5B600056 |
yes |
Reuse and multiple entry points
| Test | Bytecode | Valid |
|---|---|---|
| called at two depths | 0x6002600BB06003600BB000B18002B2 |
yes |
| fall-through second entry | 0x6008B05F600AB000B15FB150B2 |
yes |
Recursion
| Test | Bytecode | Valid |
|---|---|---|
| recursion, no base case | 0x6004B000B16004B0B2 |
yes |
| recursion eats caller stack | 0x6004B000B1506004B0 |
no |
Jumps to a CALLDEST (call elimination)
| Test | Bytecode | Valid |
|---|---|---|
jump to a CALLDEST |
0x6004B000B15F600956B150B2 |
yes |
conditional jump to a CALLDEST |
0x6004B000B136600A57B2B1B2 |
yes |
jump to a CALLDEST, net effects disagree |
0x6004B000B15F36600B57B2B150B2 |
no |
| unframed jump to a called subroutine | 0x6006B0600656B1B2 |
no |
Overflow is not validated
| Test | Bytecode | Valid |
|---|---|---|
| 17 pushes | 17 × PUSH0, STOP |
yes |
| stack growth amplified by two calls | 0x6007B06007B000B15F5F5F5F5F5F5F5F5FB2 |
yes |
| call chain, depth 17 | call_chain(17) in the test file |
yes |
| growing recursion | 0x6004B000B15F6004B0 |
yes |
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 195 lines — the validate() function itself is circa 150.
It is embedded here so that this EIP reads as a single document, and provided as a separate file, validator.py. Beside it are its opcode table, opcodes.py; the test suite test_validator.py, which runs all the validation test cases above; 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?".
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 PC 0, 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 CALLSUBs that invoke it,
however deep their stacks, and checking it once covers them all.
Constraint 5 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.
Each step of the traversal visits one instruction, knowing five 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; a
framed flag, saying whether an unreturned CALLSUB is on the path;
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, the subroutine,
and the framed flag; every later arrival must match all three, or the
code is invalid. Offsets must match by Constraint 5. Subroutines
must match because the net stack effects are kept per subroutine: if
paths from two different CALLDESTs could rejoin, there would be no
one subroutine to charge the instructions to. And the framed flags
must match because a RETURNSUB reached without a CALLSUB on the
path would underflow the return stack — which is also why
RETURNSUB requires the flag to be set at all.
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.
"""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, framed returns,
no underflow, and one static stack offset per instruction."""
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, framed) 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
work_items = [(0, 0, OUTER, False, 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 5: one net per entry
continue
net_effect[e] = v
for ret_pc, offset, caller, framed in pending.pop(e, ()):
work_items.append((ret_pc, offset + v, caller, framed, None))
for parent, d in enter_parents[e]:
settle.append((parent, d + v))
return True
while work_items:
pc, offset, entry, framed, 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))
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 5: paths must agree.
if visited[pc] != (offset, entry, framed):
return False
continue
visited[pc] = (offset, entry, framed)
# 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 4: 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, True, 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, framed, None))
else:
pending[dest].append((nxt, offset, entry, framed))
elif op == RETURNSUB:
if not framed:
return False # no CALLSUB to return from
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, framed, None))
if op == JUMPI: # and the fall-through arm
work_items.append((nxt, offset, entry, framed, 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, framed, value))
# 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
Space first: every table has one row per instruction or one per entry, and the parent lists hold one record per call and per entrance the traversal finds — a few numbers each. 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, and a CALLSUB one for
the callee and one for the return point — 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 demand checking — "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) — still linear in the size of the code, because 1024 is the protocol's constant, not the adversary's choice. Only code built to pump demands around a recursive cycle — subroutines in a ring, each drawing items from the next, so each round of checking raises every demand by one — approaches the bound: 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?" in the Rationale
prices these numbers.
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, like the header layout. (Fork-driven changes to validity — see 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?". An attacker cannot impose more validation work on the network than they pay for.
Copyright and related rights waived via CC0.