Bitcoin's Deliberate Limits

The previous page showed that a ledger is already a state machine: a shared world, a set of rules, and a transition function that untrusting strangers replay to agree on what happened. Bitcoin is the first system that made this work at planetary scale. But it did so by making a choice that looks, at first, like a weakness — its scripting language cannot loop, cannot recurse without bound, and cannot hold evolving state.

This page argues that the weakness is the point. Bitcoin’s restraint is a direct, deliberate answer to the book’s throughline — how do untrusting strangers agree on the state of a shared world, and what does it cost to run one? — because the cheapest, safest way for thousands of independent nodes to agree is to only ever run programs that are guaranteed to finish. Understanding exactly what Bitcoin gave up here is the setup for the whole rest of the book: the next page shows Ethereum deliberately giving that guarantee back in exchange for expressiveness, and paying for it with ether as fuel.

What Bitcoin Script actually is

Every Bitcoin coin (a UTXO — an unspent transaction output) is locked by a small program. To spend the coin, you must supply inputs that make that program evaluate to “true.” That program is written in Script: a tiny, stack-based, Forth-like language with no variables, no functions, and — crucially — no loops.

Script is not a general programming language. It is a language for expressing spending conditions. That is the entire job:

   A coin is locked by a predicate.  To spend it, satisfy the predicate.

   locking script (the lock)     +    unlocking script (the key)
   ─────────────────────────          ────────────────────────────
   "the spender must present a        <signature>  <public key>
    signature valid under the
    public key that hashes to H"

   The node concatenates key + lock, runs it on a stack,
   and checks that the final result is TRUE.

Within that narrow remit, Script is genuinely useful. It can express:

• Signature checks — the ordinary case: prove you hold the private key for this coin (OP_CHECKSIG).
• Multisig — require m of n signatures before the coin moves (OP_CHECKMULTISIG). This is how a company treasury or a 2-of-3 escrow is built.
• Timelocks — a coin that cannot be spent until block height N or timestamp T (OP_CHECKLOCKTIMEVERIFY, OP_CHECKSEQUENCEVERIFY). This is the backbone of payment channels and the Lightning Network.
• Hashlocks — a coin spendable only by whoever reveals a preimage x such that hash(x) = H (OP_HASH160 + OP_EQUAL). Combine a hashlock with a timelock and you get an HTLC, the atomic-swap primitive.

That is a rich vocabulary of conditions. What it is not is a vocabulary of computation. Script can ask “did you sign this?” and “is it late enough?” and “do you know the secret?” — but it cannot count, cannot iterate, and cannot remember anything between one spend and the next.

Under the hood — a lock evaluated on a stack

Run the canonical “pay to public key hash” through the interpreter and you can watch it halt. The stack starts with the key material, and each opcode pops its inputs and pushes its result:

   script:  <sig> <pubKey>  OP_DUP  OP_HASH160  <H>  OP_EQUALVERIFY  OP_CHECKSIG

   op              stack (top on the right)
   ───────────     ─────────────────────────────
   <sig>           [ sig ]
   <pubKey>        [ sig, pubKey ]
   OP_DUP          [ sig, pubKey, pubKey ]
   OP_HASH160      [ sig, pubKey, hash(pubKey) ]
   <H>             [ sig, pubKey, hash(pubKey), H ]
   OP_EQUALVERIFY  [ sig, pubKey ]          ← aborts if hash(pubKey) ≠ H
   OP_CHECKSIG     [ TRUE ]                 ← verifies sig against pubKey

There is no jump backward in that list. The interpreter starts at the first opcode, walks forward, and stops when it runs off the end. The program counter only ever increases. That single structural fact — the counter never goes backward — is what the rest of this page is about.

The halting problem, informally

Here is the deep reason loops are dangerous. Suppose Script did allow loops. A node receiving a transaction would want to know, before running it: will this program ever finish, or will it spin forever? If it spins forever, running it hangs the node.

You might hope for a clever pre-check: a function will_it_halt(program, input) that inspects any program and answers yes or no without running it. In 1936 Alan Turing proved that no such function can exist for a general (Turing-complete) language. This is the halting problem, and it is not a matter of “we haven’t found the algorithm yet” — it is provably impossible.

The informal shape of the proof is worth carrying in your head:

   Suppose halts(p, x) exists and always answers correctly.
   Build a program TROUBLE(p):
       if halts(p, p) is TRUE:   loop forever
       else:                     stop

   Now ask: does TROUBLE(TROUBLE) halt?
     - If halts says YES → TROUBLE loops forever → it does NOT halt.  Contradiction.
     - If halts says NO  → TROUBLE stops         → it DOES halt.      Contradiction.

   Either answer is wrong, so halts() cannot exist.

The consequence for a shared ledger is severe. If your language is expressive enough to loop arbitrarily, you cannot look at an incoming transaction and decide in advance whether verifying it will terminate. Every node is exposed: a single crafted transaction could make every validator on the network spin forever, doing no useful work. That is a global denial-of-service, and it is baked into the mathematics of general computation, not into any particular implementation bug.

Forbidding loops makes halting provable

Bitcoin sidesteps the halting problem by refusing to play the game. It removes the one construct that makes halting undecidable — the backward jump.

A Script program is a finite, straight-line list of opcodes with no loops and no unbounded recursion. Evaluation begins at the first opcode and the program counter only moves forward. Therefore:

   #opcodes in the script  =  N   (a fixed, known number, bounded by size limits)
   each opcode executes at most once, in order
   ────────────────────────────────────────────
   the program runs in AT MOST N steps, then halts.  ALWAYS.

You do not need a clever halts() oracle, because you already know the answer for every Script program: it halts, in at most as many steps as it has opcodes. Termination is not decided at runtime; it is guaranteed by construction. And Bitcoin adds belt-and-braces limits on top — a script and its stack are size-bounded (historically a 10,000-byte script limit and a 1,000-element stack cap), so even the length of that straight line is capped.

This is the property that lets a Bitcoin node be safe. Before it has run a single opcode, a node knows the transaction cannot hang it. Verification is:

• Guaranteed to finish — no program can loop forever, because the language has no way to loop at all.
• Cheap and predictable — the cost of verifying is bounded by the script’s size, which is bounded by consensus rules. A node can budget its work in advance.
• Universal — every node reaches the same verdict in a bounded number of steps, with no meter, no fuel, and no accounting. The rule is simply “run it to the end and read the top of the stack.”

By the numbers — why Bitcoin needs no gas meter

Ethereum charges ether as fuel precisely because its programs can loop, so it must meter every step and cut a program off when the fuel runs out. Bitcoin needs none of that machinery. Compare what each node must reason about before running a program:

                          Bitcoin Script          Ethereum EVM
   Can it loop?           No                       Yes
   Provably halts?        Yes, in ≤ N opcodes      Only because gas runs out
   Halt guaranteed by     language structure       an economic meter (gas)
   Cost to bound work     free — count opcodes      run a metered interpreter
   Worst-case DoS         impossible by design     priced, not prevented

The entire gas system — a running counter, a per-opcode price list, an out-of-gas exceptional halt that reverts state — is the cost Ethereum pays to allow the loops Bitcoin forbids. Bitcoin buys the same safety for free by giving up the loops.

It actually happened — the value-overflow that halting could not save

Halting is only one class of hazard, not all of them. On 15 August 2010, block 74638 contained a transaction that exploited an integer-overflow bug (CVE-2010-5139): its outputs summed to over 184 billion BTC, far beyond the 21-million cap, because the sum wrapped around and defeated the check that outputs must not exceed inputs. The chain was rescued by a patched client and a manual fork within hours. The lesson sharpens today’s point: a bounded, always-halting language stops one entire category of attack — the program that never finishes — but it does not stop logic bugs in the verification rules themselves. Restraint in the language is necessary, not sufficient; the surrounding rules must still be correct.

The trade-off: expressiveness for verifiability

Nothing is free. Script buys guaranteed, cheap, universal verification by giving up the ability to compute. State the bargain plainly:

	Bitcoin Script	A general (Turing-complete) language
Loops / recursion	None	Yes
Halts?	Always, by construction	Undecidable in advance
Verifier hangs?	Impossible	Possible without a meter
Holds evolving state?	No	Yes
Cost to verify	Bounded by script size, free to budget	Must be metered at runtime
Optimized for	Being checked by everyone, cheaply	Being expressive for the author

Script optimizes for the verifier, not the author. It assumes the important actor is one of the thousands of untrusting nodes who must independently re-check the program and must never be tricked into working forever. For that actor, “this program provably finishes cheaply” is worth more than “this program can express anything.”

That is the correct choice for a system whose only job is moving a scarce digital coin between keys under stated conditions. You do not need loops to check a signature, count votes in a multisig, or compare a hash. Bitcoin looked at its problem — let strangers hold and transfer value without trusting each other or a middleman — and picked the least powerful language that could express it. Least power is a feature: the less a language can do, the more you can prove about it, and the safer it is to hand a copy to every node on Earth.

The gap: Script cannot remember

Now the limitation that opens the next page. Because a locking script runs fresh each time and leaves nothing behind, Script has no evolving state. It cannot hold a counter that goes up by one on each call. It cannot hold a market whose price moves as people trade. It cannot hold a loan whose balance accrues interest over time.

Each of those needs the same structural thing: a program that persists, remembers its previous state, and mutates that state when invoked. In state-machine terms — the frame from the last page — Script can only express a transition function over coins, one that consumes and produces UTXOs. It cannot express a transition function over arbitrary program-defined variables that survive between transactions.

   What Script can express          What it cannot
   ─────────────────────────        ──────────────────────────────
   "spendable if signed by K"       counter += 1  on every call
   "spendable after block N"        a price that drifts as people trade
   "spendable if you reveal x"      a loan balance that grows over time
   (a one-shot predicate on a       (persistent, evolving, program-
    coin, evaluated then gone)       owned state — a running machine)

This is not an accident of Bitcoin’s implementation; it is the shadow of the same design choice that made verification cheap. Statelessness and no-loops travel together: a language with no memory and no iteration is exactly the language you can prove always halts. The two guarantees are one guarantee, seen from two sides.

And that is precisely the gap Ethereum sets out to fill. A general “world computer” needs exactly what Script forbids — persistent state and the ability to iterate over it. The whole question of the next page is: can you give the ledger a memory and a real computer, without losing the guarantee that every node can safely verify every transaction? Ethereum’s answer — keep the computation, but meter it so it still always halts — is why ether behaves as fuel and why the rest of this book has anything to explain.

The architect’s lens

Bitcoin Script is a major technology defined as much by what it refuses to do as by what it does — interrogate the restraint as the deliberate design choice it is:

• Why does it exist? Script exists to let a UTXO carry its own spending conditions — signature checks, multisig, timelocks, hashlocks — so a coin can be locked by a predicate that any node can evaluate, without trusting a central party to enforce the rules.
• What problem does it solve? It lets thousands of untrusting nodes each cheaply and safely verify every transaction. By forbidding loops it dodges the halting problem entirely: every script provably halts in at most N opcodes, so no transaction can ever hang a validator — a whole class of global denial-of-service is impossible by construction.
• What are the trade-offs? Guaranteed, free verifiability is bought with expressiveness. Script cannot loop, cannot recurse without bound, and cannot hold evolving state — no counters, no markets, no loans — so anything needing memory or iteration is simply out of reach.
• When should I avoid it? When your problem genuinely needs a general computer — persistent, program-owned state that changes over time. That is exactly the workload Script cannot express and that pushes you toward a metered VM like the EVM.
• What breaks if I remove it? Replace Script’s bounded, always-halting design with an unmetered general language and you reintroduce the halting problem to consensus: a single crafted transaction could spin every node forever. Remove the restraint and you lose the cheap universal verification that lets untrusting strangers agree at all.

Check your understanding

1. What kind of thing is Bitcoin Script designed to express, and name three spending conditions it can encode.
2. State the halting problem informally. Why does it make an unmetered Turing-complete language dangerous for a shared ledger that every node must verify?
3. Bitcoin forbids loops. Explain precisely why that guarantees every script halts, and why that guarantee is available before a node runs a single opcode.
4. What is the core trade-off Script makes, and who is the “important actor” it optimizes for?
5. Give a concrete example of something Script cannot express, and explain why that missing capability is exactly what a general world computer needs.

Show answers

1. Script is designed to express spending conditions (predicates) on a coin — “under what conditions may this UTXO be spent?” — not general computation. Three examples: multisig (require m of n signatures), timelocks (unspendable until block height N or time T), and hashlocks (spendable only by revealing a preimage x with hash(x) = H). Ordinary single-signature checks (OP_CHECKSIG) are the common case.
2. The halting problem: there is no algorithm that, given an arbitrary program and input, decides in advance whether it will finish or run forever (Turing, 1936 — provably impossible, not merely unsolved). For a shared ledger this is fatal: if the language can loop arbitrarily, a node cannot tell whether verifying an incoming transaction will terminate, so a single crafted transaction could make every validator spin forever — a global denial-of-service baked into the mathematics of general computation.
3. A Script program is a finite, straight-line list of opcodes with no backward jumps; the program counter only moves forward, so each opcode runs at most once and the program halts in at most N steps, where N is the number of opcodes (itself bounded by consensus size limits). Because that bound follows from the script’s structure, a node knows the program halts just by counting opcodes — before executing any of them. No halts() oracle is needed.
4. Script trades expressiveness for verifiability: it gives up loops, recursion, and evolving state in exchange for verification that is guaranteed to finish, cheap to budget, and identical for everyone. It optimizes for the verifier — the thousands of untrusting nodes who must independently re-check every program and must never be tricked into working forever — rather than for the program’s author.
5. Script cannot hold evolving state — e.g. a counter that increments on each call, a market price that drifts as people trade, or a loan balance that accrues interest. Each of those needs a program that persists and mutates its own state between invocations, which is precisely the capability a general world computer must provide (and which Ethereum adds, while keeping halting guaranteed by metering each step instead of forbidding loops).