Gas: Pricing Every Step So Strangers Can Run Your Code

The tiny stack VM turned our ledger into a computer: it decodes bytecode, walks a stack, and — crucially — can loop. JUMP lets a program send its program counter backwards, and the moment a language can loop it can loop forever. That is the power we wanted, and it is also a live grenade. This chain promised to run anyone’s code. What happens when someone deploys JUMPDEST; PUSH 0; JUMP — three bytes that jump to themselves and never stop?

This page adds the one mechanism that makes exposing a Turing-complete VM to untrusting strangers safe instead of suicidal: gas. Every step costs a metered amount; the caller supplies a budget; when the meter hits zero the machine halts and throws away everything the run did. By the end you will have a VM that can never hang, that reverts cleanly on failure, and that prices each operation in proportion to the burden it puts on every node that must re-run it. Gas is, quite literally, the answer to the book’s second question: what does it cost to run the shared world computer?

The trap a programmable chain walks into

Bitcoin never faced this problem. Its Script language has no general loops on purpose, so every script is bounded by construction — it always terminates, and Bitcoin needs no meter. Ethereum wanted the opposite: a Turing-complete machine that can express arbitrary logic. That expressiveness is exactly what reintroduces an old, famous danger.

The halting problem. Given an arbitrary program, will it ever stop? Alan Turing proved in 1936 that no algorithm can decide this for every possible program. It is provably undecidable.

So a public chain cannot screen out infinite loops by inspecting the bytecode. You cannot, in general, look at a contract and decide whether it halts — that is not a gap in our cleverness, it is a theorem. If your validation rule were “reject code that loops forever,” you could never implement it.

Gas does not solve this. It sidesteps it by changing the question:

   undecidable:  "does this program halt?"              ← can't answer, ever (Turing 1936)
   decidable:    "does this program halt within N gas?" ← always answer: run it, count down

You do not need to know whether a program halts if you can guarantee it halts within a budget. Attach a finite amount of gas to every execution, charge for each step, and force a halt when the meter reaches zero. Now every run has exactly two endings — it finishes on its own, or it is stopped by the meter — and never a third ending called “hang.” The undecidable question becomes a counted-down certainty. That, before it is ever a fee, is what gas is for.

The gas meter: charge before you act

The whole discipline of gas fits in one rule: each operation pays its cost before it executes. Charge first, act second. If the budget cannot cover the next step, the machine halts before doing it, so the meter can never go negative and no one ever gets a free instruction.

In ethmini the meter is a single u64 that counts down from the caller’s gas_limit. Before running an op, we ask it to pay:

// Charge `cost` or fail. Every op pays before it acts, so the meter can never
// go negative. An exceptional halt (out of gas) consumes *all* the gas — just
// as real EVM does — so we report `used = gas_limit`.
let charge = |gas: &mut u64, cost: u64| -> Result<(), VmError> {
    if *gas < cost {
        Err(VmError::OutOfGas { used: gas_limit, limit: gas_limit })
    } else {
        *gas -= cost;
        Ok(())
    }
};

The interpreter loop wires it in at exactly one place — right after decoding an instruction and right before executing it:

let (op, next) = Op::decode(code, pc)?;   // what's the next instruction?
charge(&mut gas, op.gas_cost())?;         // pay for it, or halt out-of-gas
match op { /* ...now, and only now, run it... */ }

Because the charge happens before the match, an op that cannot be paid for never runs. This is the invariant that makes the whole thing airtight: at every point in execution, gas is the exact amount of budget still available, and it never underflows.

   loop:
     ┌─ pc past end of code? ── yes ──▶ clean halt (implicit STOP)
     │  no
     ├─ decode instruction at pc
     ├─ CHARGE gas_cost(op) ──── can't pay? ──▶ VmError::OutOfGas  (exceptional halt)
     ├─ execute op (may push/pop, read/write storage, jump)
     └─ advance pc, repeat

Notice where the loop’s back-edge is: a JUMP that sends pc backwards re-enters the loop, re-decodes, and charges again. An infinite loop is not infinite here — it is a finite loop that runs exactly as many times as the budget affords, and then trips OutOfGas. The companion crate proves this with a test:

#[test]
fn infinite_loop_is_bounded_by_gas() {
    // JUMPDEST ; PUSH 0 ; JUMP  -> jumps back to pc 0 forever.
    // Without gas this never returns. With gas it must halt as OutOfGas.
    let code = assemble(&[Op::JumpDest, Op::Push(0), Op::Jump]);
    let err = run(&code, &empty(), 1000).unwrap_err();
    assert!(matches!(err, VmError::OutOfGas { limit: 1000, .. }));
}

The deliberate infinite loop terminates. The meter converted “does this halt?” into “it halts by step N,” and it did.

The gas schedule and why it is ordered as it is

Every op declares its price in one place, Op::gas_cost. Read the numbers as a ranking, not as gospel — the ordering carries the lesson:

pub fn gas_cost(&self) -> u64 {
    match self {
        Op::Stop | Op::Return => 0,              // halting is free
        Op::JumpDest         => 1,               // a landing pad; nearly free
        Op::Push(_) | Op::Pop | Op::Add | Op::Sub => 3,   // stack + arithmetic: cheap
        Op::Mul  => 5,                           // a touch more work than add
        Op::Jump => 8,
        Op::JumpI => 10,
        Op::SLoad  => 100,                        // read persistent state: dear
        Op::SStore => 200,                        // write persistent state: dearest
    }
}

The prices are not arbitrary; they track the burden each op places on every node in the network, because every node must re-run this exact computation to agree on the result. Line the three tiers up:

  cheap    ADD, PUSH, POP (3)   — touch only this call's stack; vanish when the call ends
  dearer   SLOAD (100)          — read state that persists across nodes, forever
  dearest  SSTORE (200)         — WRITE state every full node must store, forever

• Arithmetic is cheap because an ADD touches only the transient stack. When the call ends, the stack is gone; it cost the network a few CPU cycles and nothing else.
• A storage read (SLOAD) is dearer because storage is not scratch memory — it is the durable state of the world that lives in the chain, replicated on every node. Reading it means every node must have kept it and must look it up.
• A storage write (SSTORE) is dearest of all because it grows the state that every full node must keep forever. One write is not a one-time cost; it is a permanent tax on every future participant who ever syncs the chain. Pricing writes highest is how gas makes the person who imposes that forever-cost pay for it, rather than externalising it onto everyone else.

That price ranking — transient compute cheap, persistent reads dear, persistent writes dearest — is the entire economic argument of gas in miniature. It is why storing data on-chain is expensive by design: you are asking thousands of strangers to remember something on your behalf, indefinitely.

By the numbers — what one counter increment costs

The counter contract we build next runs PUSH 0; SLOAD; PUSH 1; ADD; PUSH 0; SSTORE; STOP. Under ethmini’s schedule:

  PUSH 0    3 gas
  SLOAD   100 gas      (read state that persists across nodes — dear)
  PUSH 1    3 gas
  ADD       3 gas
  PUSH 0    3 gas
  SSTORE  200 gas      (write grows state every node keeps forever — dearest)
  STOP      0 gas
  ─────────────────
  total   312 gas per call, out of a 100_000 budget

Two ops — the SLOAD and the SSTORE — account for 300 of the 312. The four stack-and-arithmetic ops together cost 12. That lopsidedness is the point: touching persistent state dwarfs everything else, because persistent state is the expensive, shared, forever thing. (Real EVM’s SSTORE is far pricier and far more nuanced — it charges differently for setting a zero slot to non-zero, refunds for clearing, and more — but the shape of the incentive is exactly this.)

Two ways to stop: clean halt vs. exceptional halt

Give the VM a budget and every execution ends in one of exactly two categories. The distinction governs what happens to the state changes the run made.

A clean halt is a successful, intentional stop. The program reached STOP or RETURN (or simply ran off the end of the code, which we treat as an implicit STOP). It commits its work and reports the gas it actually used:

Op::Stop => return Ok(Execution {
    gas_used: gas_limit - gas,   // only what you spent
    return_value: None,
    storage: working,            // hand back the mutated storage to commit
}),

An exceptional halt is a failure inside the run. The code blew up: it ran out of gas, underflowed the stack, hit a byte that is not an opcode, or jumped somewhere illegal. Our VmError enumerates exactly these:

pub enum VmError {
    OutOfGas { used: u64, limit: u64 },          // the meter hit zero
    StackUnderflow { op, wanted, had },          // an op wanted operands that weren't there
    StackOverflow { max },                        // ran past the 1024-word stack cap
    InvalidOpcode(u8),                            // a byte the decoder doesn't know
    TruncatedPush { pc },                         // a PUSH whose immediate ran off the end
    InvalidJump { dest },                         // jumped somewhere that isn't a JUMPDEST
}

Every one of these returns Err, and every one discards all state changes the call made. Note one deliberate rule for OutOfGas: it reports used = gas_limit. Running out of gas burns the entire budget, not just the gas spent up to the point of failure. That is not spite; it is a defence. If a failed, budget-exhausting run were cheap, an attacker could spam the network with heavy computations that do a lot of work, fail on purpose, and pay almost nothing. Charging the full budget makes wasting the network’s time cost exactly as much as using it.

   clean halt (STOP / RETURN / fell off end)   exceptional halt (any VmError)
   ─────────────────────────────────────────   ──────────────────────────────
   returns Ok(Execution)                        returns Err(VmError)
   commits the mutated storage                  discards ALL state changes
   charges only gas actually used               out-of-gas burns the WHOLE budget

One subtlety worth carrying to the next part: an exceptional halt is not the same as rejecting the transaction. A reverted call still counts — the transaction is still mined and the sender’s nonce still advances — it just leaves no state behind except that nonce bump. Rejection (bad nonce, can’t afford the value) means the transaction was never valid to include at all. That reject-versus-revert line is the subject of the state-transition function; here we only need to know that a VmError triggers the revert path.

Under the hood — revert is structural, not a rollback log

How does a failed run “undo” its writes? Not by recording each change and replaying it in reverse. The trick is simpler and impossible to get wrong: the VM never mutates the real storage in the first place. It runs against a clone, and only a clean halt hands the clone back to be committed.

pub fn run(
    code: &[u8],
    storage: &BTreeMap<u64, u64>,   // borrowed, read-only
    gas_limit: u64,
) -> Result<Execution, VmError> {
    let mut working = storage.clone();   // ← mutate a COPY, never the original
    // ... SSTORE writes into `working`, SLOAD reads from `working` ...
    // clean halt: Ok(Execution { storage: working, .. })  → caller commits it
    // exceptional halt: Err(..)                            → `working` is dropped
}

Because run only borrows the caller’s storage and does all its writes into working, an Err return drops working on the floor and the original map is provably untouched — the type system guarantees the function never had a mutable handle to the real thing. There is nothing to roll back because nothing real was ever written. The companion crate pins this down:

#[test]
fn out_of_gas_reverts_storage() {
    let mut storage = BTreeMap::new();
    storage.insert(0, 7);
    // Writes storage, then runs dry: SSTORE costs 200 but the budget is 10.
    let code = assemble(&[Op::Push(123), Op::Push(0), Op::SStore]);
    let err = run(&code, &storage, 10).unwrap_err();
    assert!(matches!(err, VmError::OutOfGas { .. }));
    assert_eq!(storage.get(&0), Some(&7));   // original untouched — revert is structural
}

The run tried to overwrite slot 0, ran out of gas mid-write, and returned Err. The caller’s storage still reads 7. State changes are all-or-nothing: either the whole call commits, or none of it does. Rust’s ownership model makes “commit the new state or drop it entirely, never half” the natural shape of the code rather than a discipline you have to remember.

The architect’s lens

• Why does it exist? Because a Turing-complete VM can loop forever, and the halting problem says you can never decide by inspection whether a given contract halts. Gas exists to make termination guaranteed without needing it to be decidable: bound every run by a budget and it must stop.
• What problem does it solve? Running untrusted code on a shared machine. Every node re-executes every call; without a meter, one malicious or buggy contract could hang or grind the entire network. Gas caps the work any single call — and, via the block gas limit, any single block — can demand.
• What are the trade-offs? Metering adds a charge before every instruction, and it forces developers to reason about cost, not just correctness. It also makes on-chain storage deliberately expensive, which pushes data off-chain. The upside is worth it: you keep full expressiveness and a guarantee that every program stops.
• When should I avoid it? When your execution environment is not Turing-complete or not adversarial. A loop-free language (like Bitcoin Script) terminates by construction and needs no meter; a private VM running only your own vetted code has no untrusted strangers to defend against. Gas is the price of expressiveness plus openness — drop either and you may not need it.
• What breaks if I remove it? The safety guarantee, entirely. Without gas, JUMPDEST; PUSH 0; JUMP runs forever, every node executing it hangs, and no one can safely accept a call from a stranger. The chain stops being a shared computer anyone can use and becomes one only its operators dare run.

Check your understanding

1. State the halting problem and Turing’s 1936 result. Explain precisely how gas sidesteps it rather than solving it.
2. What does “charge before you act” mean, and why is it the rule that guarantees the gas meter can never go negative or hand out a free instruction?
3. ethmini prices ADD at 3 gas, SLOAD at 100, and SSTORE at 200. Explain the ordering from first principles — what real burden does each tier place on the network, and why is a write the most expensive of all?
4. Distinguish a clean halt from an exceptional halt. Name three VmError variants that cause an exceptional halt, and explain why out-of-gas burns the entire budget rather than only the gas spent.
5. The VM “reverts” a failed call without keeping any undo log. Describe the structural mechanism that makes this work, and say what the out_of_gas_reverts_storage test proves about the caller’s original storage.

Show answers

1. The halting problem asks whether an arbitrary program will ever stop; Turing proved in 1936 that no algorithm can decide this for all programs — it is undecidable. Gas does not answer “does it halt?” (still undecidable). It makes the different, decidable question “does it halt within N gas?” the one that matters: meter each step, count the budget down, and force a halt at zero. Every run then either finishes or is stopped by the meter — never hangs.
2. “Charge before you act” means each op subtracts its cost from the budget before it executes; the interpreter calls charge(...)? right after decoding and before the match that runs the op. If the budget can’t cover the cost, the op halts out-of-gas and never runs. Because payment always precedes execution, gas is never decremented below zero and no instruction ever runs unpaid.
3. Prices track the burden each op puts on every node, since every node re-runs the code. ADD (3) touches only this call’s transient stack and vanishes when the call ends — cheap. SLOAD (100) reads state that persists across all nodes forever, so every node must have kept it — dearer. SSTORE (200) grows the persistent state every full node must store forever, imposing a permanent cost on every future participant — dearest. Pricing writes highest makes whoever imposes that forever-cost pay for it.
4. A clean halt is an intentional, successful stop (STOP, RETURN, or falling off the end of the code): it commits the mutated storage and charges only the gas actually used. An exceptional halt is a failure inside the run that returns Err(VmError) and discards all state changes. Three variants: OutOfGas, StackUnderflow, InvalidOpcode (also StackOverflow, TruncatedPush, InvalidJump). Out-of-gas burns the whole budget so that failing on purpose is never cheap — otherwise an attacker could impose heavy computation on every node, fail deliberately, and pay almost nothing.
5. run only borrows the caller’s storage read-only and does every write into a working clone. A clean halt returns that clone for the caller to commit; an exceptional halt returns Err, and working is simply dropped — there is nothing to undo because the real storage was never mutated. The out_of_gas_reverts_storage test writes into a call that runs dry mid-SSTORE, gets an OutOfGas error, and confirms the caller’s original storage still reads its pre-call value (7): state changes are all-or-nothing, and the revert is structural.