Skip to content
Ethereum · First Principles

A Tiny Stack VM: Opcodes, Bytecode, and the Interpreter Loop

The last four pages built a ledger. Accounts replaced Bitcoin’s coins with mutable balances, the world state and its transition function gave us a rule for moving value from one account to another, and the state root compressed the whole world into one hash that untrusting strangers can compare byte-for-byte. That is already a real thing to agree on. But so far the only program the world knows how to run is “transfer value.” A ledger can answer who owns what; it cannot answer run this code and let everyone agree on the result.

This page builds the piece that closes the gap: a virtual machine that runs arbitrary bytecode stored inside an account. It is a stack machine — the simplest kind to build and to reason about — and it is where the book’s throughline stops meaning “agree on a list of balances” and starts meaning “agree on the output of a program written by a stranger.” We build the opcodes, the bridge between opcodes and raw bytes, and the interpreter loop that executes them. We keep the machine safe-but-incomplete here; the next page adds gas, the discipline that makes it safe to expose to the public.

Everything below is grounded in the companion crate, rust/ethmini/src/vm.rs.

Two views of the same code

Section titled “Two views of the same code”

A contract’s code is a flat Vec<u8> — raw bytecode, exactly how Ethereum stores it on-chain and exactly how it travels the network. But raw bytes are miserable to write and reason about, so ethmini keeps two views of the same program and converts between them:

   Op enum  ──assemble()──▶  bytecode  ──Op::decode()──▶  Op enum
  (how we                    Vec<u8>                      (one instruction
   write & match)         (how it's stored)                at a time, at run)
  • The Op enum is “opcodes as a Rust type.” It is how we build programs by hand, and — crucially — it is what the interpreter matches on to decide what each instruction does.
  • The raw bytes are the on-chain representation: what lives in an account’s code field and what a full node downloads and executes.

assemble turns a slice of ops into bytes; Op::decode turns bytes back into a single op plus the position of the next instruction. Here is the enum:

/// One instruction of the mini-EVM. The interpreter decodes a byte into one
/// of these and matches on it.
pub enum Op {
    Push(u64),   // push a literal word (carries an 8-byte immediate)
    Pop,         // discard the top of the stack
    Add, Sub, Mul, // pop b, pop a, push a∘b  (wrapping)
    SStore,      // pop key, pop value  → storage[key] = value   (persistent!)
    SLoad,       // pop key             → push storage[key]      (0 if unset)
    JumpDest,    // a legal jump target (a no-op landing pad)
    Jump,        // pop dest            → continue at dest
    JumpI,       // pop dest, pop cond  → if cond != 0, jump to dest
    Stop,        // halt OK, commit storage
    Return,      // pop one word, halt OK, return it
}

The opcode numbers are real Ethereum

Section titled “The opcode numbers are real Ethereum”

The one thing assemble does not simplify is the byte values. Each op encodes to the same number real Ethereum uses, so the bytecode you build here would be recognisable to anyone who has read the yellow paper:

   Op          byte     Op          byte
   ───────────────────  ───────────────────
   STOP        0x00     SSTORE      0x55
   ADD         0x01     JUMP        0x56
   MUL         0x02     JUMPI       0x57
   SUB         0x03     JUMPDEST    0x5b
   POP         0x50     PUSH8       0x67
   SLOAD       0x54     RETURN      0xf3

The one liberty is word size. Real EVM operates on 256-bit words (wide enough to hold a Keccak-256 hash or an address without splitting) and has PUSH1..PUSH32 at 0x60..0x7f, each carrying that many immediate bytes. We expose a single PUSH carrying a full 8-byte (u64) word, so we reuse PUSH8 (0x60 + 7 = 0x67). Real shape, simplified width: every mechanism — push, pop, wrapping overflow — is identical; only the number of bits shrinks.

Encoding is a one-op-at-a-time affair, and assemble just concatenates:

pub fn assemble(ops: &[Op]) -> Vec<u8> {
    let mut out = Vec::new();
    for op in ops {
        op.encode(&mut out);   // Push writes 0x67 + 8 bytes; others write 1 byte
    }
    out
}

A stack machine, by example

Section titled “A stack machine, by example”

A stack machine has no registers. Operands live on a single last-in-first-out stack of words, and each opcode pops its inputs off the top and pushes its output back. There is no a = b + c — only “pop two, push their sum.” Watch the machine compute (2 + 3) * 4:

   instruction   stack (top on the right)
   ───────────   ────────────────────────
   PUSH 2        [ 2 ]
   PUSH 3        [ 2, 3 ]
   ADD           [ 5 ]          ← pop 3, pop 2, push 2+3
   PUSH 4        [ 5, 4 ]
   MUL           [ 20 ]         ← pop 4, pop 5, push 5*4
   RETURN        [ ]   → returns 20

That is the entire computational model. Real EVM has around 140 opcodes; ours has about a dozen, but the loop that runs them is identical in shape.

The stack is bounded. Real EVM caps it at 1024 words, and we mirror that exactly:

/// The largest stack we allow, mirroring real EVM's 1024-word limit.
pub const STACK_LIMIT: usize = 1024;

The bound matters for the same reason gas will: it stops a hostile program — say one that pushes forever — from exhausting a node’s memory. A push into a full stack is a StackOverflow error, which (like every other error) halts the machine rather than letting it run wild.

SLOAD and SSTORE: reading and writing the world

Section titled “SLOAD and SSTORE: reading and writing the world”

Arithmetic ops only move words around the stack. SLOAD and SSTORE are the two opcodes that reach outside the stack, into the account’s persistent key→value storage:

Op::SStore => {
    let key = pop(&mut stack, "SSTORE")?;
    let value = pop(&mut stack, "SSTORE")?;
    working.insert(key, value);     // writes a CLONE of storage
    pc = next;
}
Op::SLoad => {
    let key = pop(&mut stack, "SLOAD")?;
    let value = working.get(&key).copied().unwrap_or(0);  // unset slot = 0
    push(&mut stack, value)?;
    pc = next;
}

Two properties to notice. First, an unset slot reads as zero — there is no “does this key exist” in EVM storage; every one of the astronomically many slots is defined, and unwritten ones are simply 0. Second, SSTORE writes to working, a clone of the account’s storage that run mutates and only hands back on a clean halt. That clone is the revert mechanism in miniature, and it is why a failed call leaves the real storage untouched — a point we return to on the next page and lean on hard when we deploy and call a real contract.

The interpreter loop

Section titled “The interpreter loop”

The heart of the VM is a loop: decode the instruction at the program counter (pc), execute it, advance to the next instruction. Stripped to its spine:

pub fn run(code: &[u8], storage: &BTreeMap<u64, u64>, gas_limit: u64)
    -> Result<Execution, VmError>
{
    let dests = jumpdests(code);       // scan once for legal jump targets
    let mut working = storage.clone(); // mutate a COPY
    let mut stack: Vec<u64> = Vec::new();
    let mut pc = 0usize;


    loop {
        // Running off the end of the code is an IMPLICIT STOP, just like EVM.
        if pc >= code.len() { break; }


        let (op, next) = Op::decode(code, pc)?;  // op + where the NEXT one starts


        match op {
            Op::Push(v) => { push(&mut stack, v)?; pc = next; }
            Op::Add => {
                let b = pop(&mut stack, "ADD")?;
                let a = pop(&mut stack, "ADD")?;
                push(&mut stack, a.wrapping_add(b))?;
                pc = next;
            }
            Op::SStore => { /* pop key, pop value, working.insert(..) */ pc = next; }
            Op::Jump  => { let d = pop(&mut stack, "JUMP")?; pc = checked_jump(d, &dests)?; }
            Op::Stop   => return Ok(/* commit `working` */),
            Op::Return => { let v = pop(&mut stack, "RETURN")?; return Ok(/* + value */); }
            // ...the rest...
        }
    }
    Ok(/* fell off the end: a clean, successful halt with no return value */)
}

Three design choices each carry a lesson.

  1. decode returns the next pc. Instructions are variable-length: a PUSH is 9 bytes (opcode + 8 immediate), everything else is 1. By having the decoder report where the next instruction begins, the loop can never accidentally interpret a PUSH’s 8 literal bytes as opcodes. It walks instruction to instruction, never stepping into immediate data. Real EVM has the same hazard and the same defence.
  2. Running off the end is an implicit STOP. If pc reaches code.len() without hitting an explicit STOP/RETURN, the loop breaks and the run succeeds with no return value. You do not have to terminate your bytecode with STOP; walking past the last byte is halt enough.
  3. Wrapping arithmetic, by choice. a.wrapping_add(b) mirrors EVM’s modular math (real EVM is mod 2²⁵⁶; ours mod 2⁶⁴). A plain a + b would panic on overflow in a debug build — and a VM that a crafted input can make panic is a denial-of-service waiting to happen. Choosing wrapping_add is the compiler forcing you to decide what overflow means instead of inheriting a panic an attacker could trigger.

Under the hood — decode returns “the next pc”

Section titled “Under the hood — decode returns “the next pc””

It is worth seeing exactly why the “next pc” trick keeps the loop honest. Consider the assembled bytes for PUSH 5; ADD:

   byte index:   0     1  2  3  4  5  6  7  8     9
   byte value:  0x67  00 00 00 00 00 00 00 05    0x01
                └─┬─┘ └──────────┬──────────┘    └─┬─┘
               PUSH8       immediate: 5           ADD

The value 5 occupies bytes 1..9. If the loop naively advanced pc by 1 each step, it would land on byte 1 (0x00 = STOP), byte 2 (0x00), and so on — reading the number five as a string of opcodes. Nonsense, and worse, an attacker could hide a malicious byte inside a PUSH literal and jump to it.

decode prevents this by construction: when it reads a PUSH8 at index 0, it consumes the 8 immediate bytes and returns next = 9. The loop sets pc = 9 and reads ADD. The immediate data is never mistaken for code because the decoder, not a fixed stride, decides where the next instruction starts.

Jumps, and why you can only land on a JUMPDEST

Section titled “Jumps, and why you can only land on a JUMPDEST”

Straight-line arithmetic is not a computer — you need branches and loops, which means jumps. JUMP pops a destination and continues execution there; JUMPI pops a destination and a condition and jumps only if the condition is nonzero:

Op::Jump => {
    let dest = pop(&mut stack, "JUMP")?;
    pc = checked_jump(dest, &dests)?;         // must be a real JUMPDEST
}
Op::JumpI => {
    let dest = pop(&mut stack, "JUMPI")?;
    let cond = pop(&mut stack, "JUMPI")?;
    if cond != 0 { pc = checked_jump(dest, &dests)?; } else { pc = next; }
}

Both funnel through checked_jump, and here is the safety property that makes jumps trustworthy: you may only jump to a JUMPDEST opcode (0x5b). Not the middle of a PUSH immediate, not a byte halfway through another instruction — only a byte that is a real, decodable JUMPDEST instruction. Enforcing this needs a pre-pass called jumpdest analysis: before execution, scan the whole program once and collect the byte positions of every legal landing pad.

/// Scan the code once and collect the byte positions that are valid jump
/// targets: every JUMPDEST that is a real instruction, NOT a byte sitting
/// inside a PUSH immediate. This is exactly the "jumpdest analysis" real
/// EVM does, and it is why you can't smuggle a jump into the middle of a push.
fn jumpdests(code: &[u8]) -> HashSet<usize> {
    let mut set = HashSet::new();
    let mut pc = 0;
    while pc < code.len() {
        match Op::decode(code, pc) {
            Ok((Op::JumpDest, next)) => { set.insert(pc); pc = next; }
            Ok((_, next)) => pc = next,   // skip PUSH immediates correctly
            Err(_) => break,
        }
    }
    set
}

Because the scan decodes rather than steps byte-by-byte, a 0x5b byte that happens to sit inside a PUSH literal is never added to the set — the scan skipped over it as immediate data. So at run time, checked_jump accepts a destination only if it is in dests; any other target is an InvalidJump error that halts the machine:

fn checked_jump(dest: u64, dests: &HashSet<usize>) -> Result<usize, VmError> {
    let d = dest as usize;
    if dests.contains(&d) { Ok(d) } else { Err(VmError::InvalidJump { dest }) }
}

The point is worth stating plainly: jump targets are validated against a pre-scanned set, so you can never jump into a PUSH immediate or land mid-instruction. It closes exactly the hole the “next pc” trick closed for straight-line code, but for control flow.

Halting: STOP and RETURN

Section titled “Halting: STOP and RETURN”

A program stops in one of three ways, and all three are successful halts that commit the working storage:

  • STOP (0x00) — halt with no return value.
  • RETURN (0xf3) — pop one word off the stack and halt, returning it as the call’s result.
  • Falling off the end — reaching pc >= code.len() behaves exactly like STOP.

The successful outcome is an Execution, which carries the returned word (if any) and the new storage for the caller to commit:

pub struct Execution {
    pub gas_used: u64,             // (metered on the next page)
    pub return_value: Option<u64>,
    pub storage: BTreeMap<u64, u64>,
}

Everything other than these three exits — a stack underflow, a stack overflow, a bad opcode, an illegal jump — is an error that returns Err(VmError::..). Because run mutated only a clone of storage, an error means the caller never replaces the original: the write is silently thrown away. That is the atomic, all-or-nothing revert we build on next, and it is the same “commit-or-drop” discipline the state transition function used one level up.

Notice what is conspicuously missing from this page: there is nothing yet stopping a program whose code is JUMPDEST; PUSH 0; JUMP — an infinite loop. The interpreter as written would spin forever. That is not an oversight; it is the cliffhanger. The one idea that makes a public VM safe — every step costs gas, and when the meter hits zero the machine halts and reverts — is the whole of the next page.

The architect’s lens

Section titled “The architect’s lens”
  • Why does it exist? Because a ledger that can only transfer value is not programmable. A stack machine is the smallest general-purpose computer you can build and reason about, so it is the natural core for a VM that untrusting strangers must all execute identically — the piece that upgrades “agree on who owns what” to “agree on what a program computed.”
  • What problem does it solve? Turning inert on-chain bytes into a deterministic computation. It gives a shared, register-free machine that anyone can deploy code to, where every honest node decoding the same bytecode reaches the same word — the prerequisite for consensus over programs, not just balances.
  • What are the trade-offs? A stack machine is simple and easy to make deterministic, but awkward to program by hand (no named variables, everything is push/pop juggling) and a poor fit for a physical CPU, so it runs far slower than native code. The 1024-word bound and jumpdest analysis add safety at the cost of expressiveness and a mandatory pre-scan.
  • When should I avoid it? For any computation that does not need trustless global agreement. Heavy arithmetic, private data, and low-latency work belong off-chain; only the small amount of logic that genuinely must be verifiable by everyone should ever touch this machine.
  • What breaks if I remove it? Ethereum collapses back into the payments ledger of the previous four pages. Accounts, balances, and a state root remain, but every contract, token, and application vanishes — because “programmable money” is the network running this machine over stored bytecode.

Check your understanding

Section titled “Check your understanding”
  1. The VM keeps two views of a contract’s code — the Op enum and the raw Vec<u8> bytecode. What is each view good for, and which two functions bridge them?
  2. Why does Op::decode return the position of the next instruction rather than letting the loop advance pc by a fixed amount? Walk through what would go wrong for PUSH 5; ADD without it.
  3. What is jumpdest analysis, when does it run, and what specific attack does validating JUMP/JUMPI targets against the pre-scanned set prevent?
  4. Distinguish the stack from storage: how do their lifetimes differ, which opcodes touch each, and why is SLOAD of an unset slot defined to return 0?
  5. Name the three ways a program halts successfully and what each commits. Given the code JUMPDEST; PUSH 0; JUMP, what does the interpreter as built on this page do, and what will fix that on the next page?
Show answers
  1. The Op enum is for writing and reasoning about programs and for the interpreter to match on; the raw bytes are how code is stored on-chain and transmitted across the network. assemble turns ops into bytes; Op::decode turns bytes back into one op plus the next pc.
  2. Instructions are variable-length — a PUSH is 9 bytes (opcode + 8 immediate), everything else is 1 — so a fixed stride cannot know where the next instruction begins. For PUSH 5; ADD, advancing by 1 would land pc on the immediate bytes of 5 (which are 0x00 = STOP, etc.) and read the number five as a string of opcodes. decode reads PUSH8 at index 0, consumes the 8 immediate bytes, and returns next = 9, so the loop reads ADD next and never mistakes literal data for code.
  3. Jumpdest analysis is a single pre-execution scan of the whole program that decodes instruction by instruction and records the byte position of every JUMPDEST (0x5b) that is a real instruction — not a 0x5b byte sitting inside a PUSH immediate. It runs once before the interpreter loop starts. Validating jump targets against that set prevents jumping into the middle of a PUSH immediate or landing mid-instruction, which would let an attacker execute smuggled bytes as code.
  4. The stack is transient scratch space that is born and dies inside a single run, holds operands mid-calculation, and is pushed/popped by nearly every opcode; storage is the account’s persistent key→value map that survives the call and changes the state root, touched only by SLOAD/SSTORE. SLOAD of an unset slot returns 0 because EVM storage has no notion of “does this key exist” — every slot is defined, and unwritten ones are simply zero.
  5. STOP (halt, no return value), RETURN (pop one word and halt, returning it), and falling off the end of the code (an implicit STOP) — all three are successful halts that commit the working storage. For JUMPDEST; PUSH 0; JUMP, the interpreter as built here loops forever: it jumps back to pc = 0 every iteration and never terminates. The next page fixes this with gas — every step costs from a budget, and when the meter hits zero the machine halts with an out-of-gas error and reverts.