Instruction metering

Deep dive

How it works

In: program with a per-instruction cost table, initial fuel · Out: result, or trap OutOfFuel · State: fuel counter (one integer) and per-block totals computed at load · Cost: O(1) per charge point, one charge point per basic block

1. At load, find leaders: instruction 0, every jump target, every instruction after a jump. A basic block runs from a leader to the next one.
2. Sum the cost table over each block and store the total at the leader's index; other indices store 0.
3. At run time, on every instruction fetch do fuel -= block_cost[pc] (zero except at leaders). A JIT or Wasm rewriter injects one check at each block entry instead; generated code stays under W^X rules either way.
4. If the subtraction would go below zero, trap before the block executes.
5. Back-edges and calls start blocks, so every loop iteration pays and an infinite loop must trap.
6. On normal exit the consumed fuel is initial - fuel; replicated hosts record it (gas used).

Charging at entry is conservative: a block that would trap mid-way (division by zero, bad memory access) has already paid for its whole length. Hosts accept that or split blocks at instructions that can trap.

Alternatives. Count hook: the interpreter calls a callback every N instructions (Lua debug.sethook with a count: the hook is called after the interpreter executes every count instructions). Interrupt/epoch: a timer or another thread bumps a counter, compiled code only compares the counter to a deadline at loop headers and function entries. Static limit: the eBPF verifier bounds how many instructions it will simulate and rejects the program at load, so nothing is metered at run time.

Code

Tiny stack VM. Program::load precomputes the block table; run can charge per instruction or per block, and the tests check that both give the same total, that a finite program uses exactly its expected fuel, and that an infinite loop traps.

#[derive(Clone, Copy)]
enum Op { Push(i64), Add, Dup, Jnz(usize), Halt }

#[derive(Debug, PartialEq)]
enum Trap { OutOfFuel, StackUnderflow }

fn cost(op: &Op) -> u64 {
    match op { Op::Jnz(_) => 2, Op::Halt => 0, _ => 1 }
}

struct Program {
    code: Vec<Op>,
    block_cost: Vec<u64>, // total at a block leader, 0 elsewhere
}

impl Program {
    fn load(code: Vec<Op>) -> Self {
        let n = code.len();
        let mut leader = vec![false; n + 1];
        leader[0] = true;
        for (pc, op) in code.iter().enumerate() {
            if let Op::Jnz(t) = op {
                leader[*t] = true;
                leader[pc + 1] = true;
            }
        }
        let mut block_cost = vec![0; n + 1];
        let mut start = 0;
        for pc in 0..n {
            if leader[pc] { start = pc; }
            block_cost[start] += cost(&code[pc]);
        }
        Program { code, block_cost }
    }

    /// Returns (top of stack, fuel left). per_block=false charges every instruction.
    fn run(&self, mut fuel: u64, per_block: bool) -> Result<(Option<i64>, u64), Trap> {
        let (mut pc, mut st) = (0usize, Vec::<i64>::new());
        loop {
            let charge = if per_block { self.block_cost[pc] } else { cost(&self.code[pc]) };
            fuel = fuel.checked_sub(charge).ok_or(Trap::OutOfFuel)?;
            match self.code[pc] {
                Op::Push(v) => st.push(v),
                Op::Add => {
                    let (b, a) = (st.pop().ok_or(Trap::StackUnderflow)?, st.pop().ok_or(Trap::StackUnderflow)?);
                    st.push(a.wrapping_add(b));
                }
                Op::Dup => { let v = *st.last().ok_or(Trap::StackUnderflow)?; st.push(v); }
                Op::Jnz(t) => {
                    if st.pop().ok_or(Trap::StackUnderflow)? != 0 { pc = t; continue; }
                }
                Op::Halt => return Ok((st.last().copied(), fuel)),
            }
            pc += 1;
        }
    }
}

fn main() {
    use Op::*;
    let p = Program::load(vec![Push(1000), Push(-1), Add, Dup, Jnz(1), Halt]);
    let need = 1 + 5 * 1000; // entry block + 1000 loop blocks of cost 5
    assert_eq!(p.run(need, true), Ok((Some(0), 0)));
    assert_eq!(p.run(need, false), Ok((Some(0), 0))); // same total per instruction
    assert_eq!(p.run(need - 1, true), Err(Trap::OutOfFuel));
    let spin = Program::load(vec![Push(1), Jnz(0)]); // infinite loop
    assert_eq!(spin.run(1_000_000, true), Err(Trap::OutOfFuel));
    assert_eq!(spin.run(1_000_000, false), Err(Trap::OutOfFuel));
}

Complexity and constants

Run-time overhead is a load of the cost, a subtract and a branch per charge point; with per-block charging the number of charge points is the number of executed blocks, typically 3-6 instructions each. Cost drivers: where the counter lives (register or L1 line versus a memory read-modify-write per charge) and how many charge points execute. Make it cheap: charge per block, keep the counter local, and charge only at loop headers and function entries when exact counts are not needed.

Efficiency

• Cost: one subtract and compare per charge point. Measured here (Apple M4 Pro, release build, the VM above looping 50M times, about 200M executed instructions, single runs, noisy): no metering about 285-300 ms, per-instruction about 330-340 ms, per-block about 260-330 ms. In this interpreter the fuel check is below the noise of dispatch and the stack Vec. Bound: interpreter dispatch.
• Levers:
  • Charge per basic block, not per instruction — fewer checks, same total (measured above; the unit test asserts identical fuel) — whenever blocks have no mid-block exits.
  • Keep the counter in a register or local — avoids a memory round-trip per check (general compiler practice, not measured here) — in compiled/JIT code.
  • Check only at loop back-edges and calls — Wasmtime documents epoch interruption as cheaper than fuel because it avoids "counting and frequently storing a precise metric" (Wasmtime docs, Config::epoch_interruption) — when determinism is not required.
  • Price size-dependent natives by size (Wasmtime's operator_cost adds per-byte/per-element costs) — keeps fuel proportional to real work — for memcpy-like ops.
• Naive → standard → state of the art: wall-clock timer, non-deterministic · per-instruction counter, deterministic, a check on every instruction · per-block fuel or epoch deadline checked only at loop headers, tuned per host.

Implementation notes

• Wasm: Wasmtime Config::consume_fuel(true) instruments the compiled code to consume fuel; a Store starts with no fuel and must be given some; exhaustion raises a trap, or yields if fuel_async_yield_interval is configured. operator_cost sets the cost of each operator.
• Epoch interruption: a global epoch counter on the Engine (increment_epoch) and a per-store deadline; compiled code compares them at certain points. The Wasmtime docs say the interruptions are not deterministic.
• Chains: gas must be identical on all replicas, so the schedule is part of the protocol. The Ethereum documentation gives 21,000 gas for a plain ETH transfer, and a block gas limit bounds total work.
• eBPF: the verifier rejects programs it cannot prove safe; include/linux/bpf.h in the Linux source defines BPF_COMPLEXITY_LIMIT_INSNS as 1000000 ("1M insns"), the cap on instructions the verifier processes. The kernel's BPF design Q&A names BPF_MAXINSNS (4096) as a limit visible to user space.
• Lua: debug.sethook(f, "", n) calls f every n VM instructions; yielding or raising an error in the hook ends a runaway script.
• Use checked_sub on a u64 tank so an oversized charge traps instead of wrapping.

Pitfalls

• Charging at block exit instead of entry lets a malicious block do work before paying.
• Forgetting to charge a loop back-edge or an indirect call: the loop then runs free.
• Native calls priced as one instruction (copy, hash, allocate) let a guest burn minutes for one unit of fuel.
• A fuel trap leaves partial state; discard the instance or roll back.

Variants and alternatives

In production

• Wasmtime fuel and epochs, and Wasmer's metering middleware, in Wasm hosts.
• Ethereum clients: go-ethereum and revm implement EVM gas.
• Wasm contract chains: wasm-instrument injects gas metering into modules.
• Lua embedded in games and servers, bounded via a count hook.
• Linux eBPF verifier limiting program complexity.
• PostgreSQL statement_timeout for queries.

Implementations

Sources

• Wasmtime docs, Config (consume_fuel, epoch_interruption, operator_cost). docs
• Lua 5.4 Reference Manual, debug.sethook and the count hook. manual
• Linux kernel, BPF verifier documentation. docs · BPF design Q&A
• Ethereum.org, Gas and fees. docs
• Wood, Ethereum: A Secure Decentralised Generalised Transaction Ledger (Yellow Paper). pdf
• PostgreSQL docs, statement_timeout. docs