Day 23 · A Tiny VM

Day 22 gave the world a state and a rule for advancing it — but the only rule so far is “move value.” Today we build the thing that makes Ethereum a computer: a virtual machine that runs arbitrary bytecode stored in an account. It’s a stack machine — the simplest kind to build and to reason about — metered by gas so that even a program designed never to terminate is forced to stop. That last property is not a detail; it is the entire reason a public chain can safely run code it has never seen, and we’ll build straight toward it.

Bytecode, and two views of it

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

   Op enum  ──assemble()──▶  bytecode  ──Op::decode()──▶  Op enum
   (how we                   Vec<u8>                       (one instruction
    reason)               (how it's stored)                 at a time, at run)

The Op enum is “opcodes as a Rust type” — how we build and think about programs. The bytes are how code lives in an account and travels the network. At execution we decode one instruction at a time from the bytes and match on the resulting Op. Here is the enum (trimmed):

   pub enum Op {
       Push(u64),   // push a literal word (carries an 8-byte immediate)
       Pop,
       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]
       JumpDest,    // a legal jump target (a no-op landing pad)
       Jump, JumpI, // unconditional / conditional jump
       Stop,        // halt OK, commit storage
       Return,      // pop one word, halt OK, return it
   }

The opcode numbers are real EVM

assemble encodes each op to the same byte value real Ethereum uses: ADD is 0x01, MUL is 0x02, SUB is 0x03, POP is 0x50, SLOAD is 0x54, SSTORE is 0x55, JUMP is 0x56, JUMPDEST is 0x5b, RETURN is 0xf3. The bytecode you build here would be recognisable to anyone who’s read the Ethereum yellow paper. The one liberty: real EVM has PUSH1..PUSH32 (0x60..0x7f) carrying 1–32 immediate bytes; we expose a single PUSH carrying a full 8-byte word, so we reuse PUSH8 (0x67). Real shape, simplified width.

A stack machine, by example

A stack machine has no registers — operands live on a last-in-first-out stack, and each op pops its inputs and pushes its output. Watch (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’s the whole computational model. Real EVM has ~140 opcodes; ours has a dozen, but the loop that runs them is identical in shape.

Operand order — our SUB, honestly

For SUB we pop b (top) then a, and push a - b — so PUSH 10; PUSH 3; SUB gives 7, which reads the way you’d expect (“subtract the top from what’s beneath it”). Real EVM computes the reverse — top minus second — which would make that sequence 3 - 10 and wrap to a huge number. We document our convention rather than silently inherit a confusing one; the mechanism (pop two, push one) is identical.

The interpreter loop

The heart of the VM is a loop: decode the instruction at the program counter, charge its gas, execute it, advance. Stripped to its spine:

   loop {
       if pc >= code.len() { break; }          // running off the end = implicit STOP
       let (op, next) = Op::decode(code, pc)?;  // never steps into PUSH immediates
       charge(&mut gas, op.gas_cost())?;        // PAY BEFORE YOU ACT — or OutOfGas

       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 => {
               let key = pop(&mut stack, "SSTORE")?;
               let value = pop(&mut stack, "SSTORE")?;
               working.insert(key, value);      // writes a CLONE of storage
               pc = next;
           }
           Op::Jump => { let dest = pop(&mut stack, "JUMP")?; pc = checked_jump(dest, &dests)?; }
           Op::Stop   => return Ok(Execution { /* commit `working` */ }),
           // ...
       }
   }

Three design choices each carry a lesson:

1. decode returns the next pc. A PUSH is 9 bytes (opcode + 8 immediate), everything else is 1. By having the decoder report where the next instruction starts, the loop can never accidentally interpret a PUSH’s literal data as an opcode. Real EVM has the same hazard and the same defence.
2. Charge before you act. Gas is debited before the op runs. The meter can never go negative, and an op that can’t afford its cost simply doesn’t happen — it halts the machine instead.
3. Wrapping arithmetic, by choice. a.wrapping_add(b) mirrors EVM’s modular (mod 2^256; ours mod 2^64) math. In Rust, a plain a + b would panic on overflow in debug builds — and a VM that can be made to panic by a crafted input is a denial-of-service waiting to happen. Choosing wrapping_add is the compiler protecting you: it forced you to decide what overflow means rather than inherit a panic.

Gas: every step has a price

Each Op knows its cost, and the numbers are ordered the way real EVM orders them — cheap arithmetic, dear storage:

   pub fn gas_cost(&self) -> u64 {
       match self {
           Op::Stop | Op::Return => 0,
           Op::JumpDest          => 1,
           Op::Push(_) | Op::Pop | Op::Add | Op::Sub => 3,
           Op::Mul               => 5,
           Op::Jump              => 8,
           Op::JumpI             => 10,
           Op::SLoad             => 100,
           Op::SStore            => 200,   // dearest: it grows state forever
       }
   }

The ratios encode an economic truth: an ADD touches a CPU register and vanishes; an SSTORE writes a value that every full node on Earth must store forever. Pricing storage over 60× an addition is the chain charging you for the lasting burden you impose on everyone else. (Real EVM’s SSTORE is far pricier and far more intricate — different costs for zero→nonzero vs. nonzero→nonzero, with refunds — but the shape of the incentive is exactly this.)

By the numbers — what one counter call costs

The Day 24 counter does storage[0] = storage[0] + 1. Tally its gas:

   PUSH 0    3      ; key
   SLOAD   100      ; load current count
   PUSH 1    3
   ADD       3      ; count + 1
   PUSH 0    3      ; key again
   SSTORE  200      ; write it back
   STOP      0
   ──────────────
   total   312 gas

Run the demo and you’ll see exactly gas used 312 per call — the two storage ops are 300 of it (96%), and the four stack-and-arithmetic ops are the remaining 12. The number isn’t arbitrary; it’s the sum of the path the interpreter actually walked, which is why a gas estimate is an execution trace.

Out of gas → exceptional halt → revert

Now the payoff. What stops a contract whose code is JUMPDEST; PUSH 0; JUMP — an infinite loop? Nothing in the program. The meter does:

   gas = 1000
   loop:  JUMPDEST(1) + PUSH(3) + JUMP(8) = 12 gas per iteration
   ...after ~83 iterations, gas < 12  →  charge() returns Err(OutOfGas)  →  HALT

When charge can’t deduct an op’s cost it returns VmError::OutOfGas, the ? propagates it out of the loop, and run returns Err. This is an exceptional halt: it consumes all the gas the call was given (we report used = gas_limit) and — crucially — it reverts every state change the call made. How does the revert come for free? Look at where storage lives:

   pub fn run(code: &[u8], storage: &BTreeMap<u64,u64>, gas_limit: u64)
       -> Result<Execution, VmError>
   {
       let mut working = storage.clone();   // mutate a COPY
       // ...the loop writes only to `working`...
       // STOP / RETURN  → Ok(Execution { storage: working })  (caller commits it)
       // any error      → Err(..)                              (caller keeps the original)
   }

The VM never touches the real account storage. It mutates a clone, and only a clean halt (STOP / RETURN) hands that clone back for the caller to commit. On any error — out of gas, stack underflow, a bad opcode, an illegal jump — run returns Err and the original storage is simply not replaced. Atomicity isn’t bolted on; it’s a consequence of mutating an owned copy and handing back ownership only on success. That is Rust’s move semantics doing the work the snapshot in apply did one level up: commit the new value or drop it — there is no third state where half the writes escaped.

It actually happened — when underpriced gas became a weapon

In September–October 2016, Ethereum suffered a wave of denial-of-service attacks that spammed transactions calling opcodes whose gas cost was lower than the real work they caused — IO-heavy operations like EXTCODESIZE and the account-touching SUICIDE/SELFDESTRUCT. Because the price didn’t reflect the burden, an attacker could make nodes do enormous work for tiny fees, slowing the whole network to a crawl. The fix was a pair of hard forks — Tangerine Whistle (EIP-150, 18 October 2016) and Spurious Dragon — that repriced the abused opcodes upward and cleaned up the bloat they’d created. The episode is the sharpest possible proof of today’s lesson: gas cost must track real resource use, or the meter stops protecting the network. Our flat SSTORE = 200 is a simplification, but the principle — expensive things must cost more — is the one those forks were defending.

The thread

What does building this force you to understand, and what is Rust’s compiler protecting you from? A VM forces you to confront that untrusted code might never stop, and gas is the answer — a budget that turns “might run forever” into “runs for at most N steps, then halts and reverts.” Rust protected you twice along the way: wrapping_add made you choose overflow semantics instead of inheriting a panic an attacker could trigger, and owning the working storage clone made revert-on-failure the structurally obvious shape rather than a cleanup step you could forget. And the project’s question — what problem did Ethereum solve? — now has its engine: a world computer can run anyone’s program because every program pays per step and is yanked the instant it can’t. Tomorrow we put that engine to work and deploy a real contract.

→ Next: Day 24 · Smart Contracts · Prev: Day 22 · World State & Roots · Back to the Project 6 overview

Check your understanding

1. The VM keeps two views of a contract’s code — the Op enum and raw bytes. What is each view good for, and why does Op::decode return the position of the next instruction?
2. Why does the interpreter charge gas before executing an op rather than after? What guarantee does that ordering give?
3. The arithmetic ops use wrapping_add/wrapping_mul. What would a plain a + b do on overflow in a debug build, and why is that dangerous in a VM running untrusted code?
4. Explain how run achieves “out of gas reverts all storage changes” without any explicit rollback code. What Rust mechanic makes the atomicity automatic?
5. SSTORE costs over 60× an ADD. What real-world cost is that ratio pricing in, and what does the 2016 DoS episode show about getting such prices wrong?

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. decode returns the next pc because instructions are variable-length (a PUSH is 9 bytes, others 1), so reporting where the next instruction begins stops the loop from ever interpreting a PUSH’s immediate data as an opcode.
2. To guarantee the gas meter can never go negative and that an op which can’t afford its cost simply doesn’t run. Charging first means the very act of being unable to pay is the halt — there’s no window where an op executes “on credit.”
3. A plain a + b panics on overflow in debug builds. A VM that a crafted input can make panic is a denial-of-service vector (and a determinism hazard). wrapping_add forces an explicit, well-defined modular result — the compiler made you decide what overflow means.
4. run mutates a clone of the storage (working), never the real account storage. It returns the clone for the caller to commit only on a clean STOP/RETURN; on any error it returns Err and the original is simply never replaced. Rust’s move/ownership semantics make this automatic — you either hand back ownership of the new map or you don’t; there’s no half-committed state.
5. It prices the fact that an SSTORE writes data every full node must store forever, whereas an ADD touches a register and vanishes. The Sept–Oct 2016 DoS attacks exploited opcodes priced below their real cost, letting attackers impose huge work for tiny fees; the Tangerine Whistle/Spurious Dragon forks repriced them — proving gas must track real resource use or it stops protecting the network.