Day 17 · The UTXO Model

Day 16 gave us a tamper-evident chain — a history nobody can quietly rewrite. But a chain of hashes says nothing about coins: who owns what, and what counts as a legal spend. Today we build the ledger’s actual state, and we make a design choice that turns the double-spend from “a rule we enforce” into “a thing the data structure can’t represent.” That choice is the UTXO model, and it’s Bitcoin’s real answer to the problem from Day 16.

There are no balances

The surprising part first: a UTXO chain stores no account balances anywhere. There is no row that says “Alice: 70.” Instead the entire state is a set of unspent transaction outputs — discrete coins, each with an amount and a lock. Your “balance” is just the sum of the unspent coins locked to you, computed on demand. It’s physical cash, not a bank account: you don’t have a balance, you have a pocket of specific bills.

A transaction consumes some existing coins and creates new ones:

   inputs (point at past outputs)        outputs (new, unspent coins)
   ┌───────────────────────────┐         ┌──────────────────────────┐
   │ prev: (txid, vout) + key  │   ───▶  │ amount + address (lock)  │
   │ prev: (txid, vout) + sig  │         │ amount + address (lock)  │
   └───────────────────────────┘         └──────────────────────────┘
     Σ inputs  ≥  Σ outputs   (the difference is the miner's fee)

Each input points at a specific earlier output by (txid, index) and carries a witness proving you may spend it (the key and signature — that’s Day 18). Each output is a fresh coin: an amount locked to an address. From rust/btcmini/src/tx.rs:

pub struct OutPoint { pub txid: Hash256, pub index: u32 }   // names one past output

pub struct TxInput  { pub prev: OutPoint, /* + pubkey, sig */ }
pub struct TxOutput { pub amount: u64, pub address: Address }

pub struct Transaction {
    pub inputs: Vec<TxInput>,
    pub outputs: Vec<TxOutput>,
    pub coinbase_tag: Vec<u8>,   // only the coinbase uses this
}

The UTXO set: spending is deletion

The ledger’s live state is the UTXO set — a map from every unspent output to the coin sitting there. In rust/btcmini/src/utxo.rs it’s exactly that:

pub struct UtxoSet {
    map: HashMap<OutPoint, TxOutput>,
}

Now the double-spend dissolves. To spend a coin you must name an OutPoint that is in this set, and applying the transaction removes it:

   UTXO set (the only state that matters)
   ┌──────────────────────────────┬─────────────────────┐
   │ OutPoint (txid, vout)        │ TxOutput (amt, addr)│
   ├──────────────────────────────┼─────────────────────┤
   │ (a1b2…, 0)                   │ 50  → alice         │
   │ (c3d4…, 1)                   │ 12  → bob           │
   └──────────────────────────────┴─────────────────────┘
     spend  = remove a row.   create = add a row.
     a double-spend names a row that is already gone → rejected.

The first spend of coin (a1b2…, 0) succeeds and deletes that row. A second transaction trying to spend (a1b2…, 0) looks it up, finds nothing, and is rejected. You didn’t need a special “have I seen this before?” check — the absence of the row is the check. That’s the elegance: double-spend protection isn’t a rule bolted on top, it’s a consequence of modeling coins as removable entries.

validate_tx enforces the full set of spend rules and returns the fee:

pub fn validate_tx(&self, tx: &Transaction) -> Result<u64> {
    // 1. has inputs   2. no input named twice
    // 3. every input's OutPoint is STILL in the set   ← the double-spend check
    // 4. the right key   5. a valid signature   (Day 18)
    // 6. Σ outputs ≤ Σ inputs                          ← conservation
    // returns Σ inputs − Σ outputs = the fee
}

Under the hood — why OutPoint is the perfect map key, and why we clone the set

OutPoint is (Hash256, u32) and derives Copy, Eq, Hash — so it drops straight into a HashMap key with O(1) lookup, and the txid’s collision resistance (Day 16) means two different coins can’t accidentally share a key. That’s the whole reason a transaction references outputs by hash, not by position in some global list: the reference is globally unique and unforgeable.

The second trick is in how a block is validated. You can’t apply a half-checked block to the real ledger and then discover transaction five is bad — you’d have corrupted state. So connect (in rust/btcmini/src/chain.rs) clones the UTXO set into a working copy, applies the whole block there, and only swaps it in if every check passes:

let mut working = self.utxo.clone();   // a scratch copy
for tx in block.txs.iter().skip(1) {
    let fee = working.validate_tx(tx)?; // ? bails out on the first bad tx...
    working.apply_tx(tx);
}
// ...so we only reach here, and assign self.utxo = working, if ALL passed

This is ownership doing transactional bookkeeping for you: the working copy is a separate owned value, the real set is untouched until the assignment, and ? guarantees a failed block leaves zero trace. What is the compiler protecting you from? Applying an invalid state transition halfway — the kind of partial-write corruption that, in a ledger, is indistinguishable from theft.

The coinbase: where coins come from

If every transaction consumes existing coins, where does the first coin come from? The coinbase — the one special transaction, first in every block, that has no real inputs and mints new value:

pub fn coinbase(miner: Address, reward: u64, tag: &[u8]) -> Transaction {
    Transaction {
        inputs: vec![TxInput::spending(OutPoint::null())], // points at nothing
        outputs: vec![TxOutput::new(reward, miner)],       // mints `reward` to the miner
        coinbase_tag: tag.to_vec(),                        // block height → unique txid
    }
}

It’s recognizable because its single input points at the null outpoint (zero txid, max index), which refers to nothing. The reward is the subsidy (new coins, the miner’s incentive) plus the fees of the other transactions in the block. The coinbase_tag carries the block height for a subtle but important reason: two coinbases paying the same miner the same amount would otherwise have identical bytes and thus identical txids, and their outputs would collide in the UTXO set. Folding the height into the encoding makes every coinbase’s id unique — a real bug Bitcoin fixed with BIP 30/34.

By the numbers — conservation, and the coins that don’t exist

The conservation rule is one line — outputs may not exceed inputs — but it’s the rule that makes the money real. Our validate_tx sums inputs and outputs with checked_add and rejects Σ outputs > Σ inputs. The integration test pins the consequence exactly:

   genesis subsidy        50   (to the unspendable zero address)
   5 mined blocks    5 ×  50 = 250
   ─────────────────────────────
   total supply            300   ← and not one satoshi more

No transaction can increase that total; only a coinbase adds the fixed subsidy, and only by removing fees from the pool that spends paid. The supply is an emergent fact of the rules, checked block by block — which is precisely the property that failed, catastrophically, the one time the check had a hole in it.

It actually happened — the day Bitcoin minted 184 billion coins

On 15 August 2010, block 74638 contained a transaction whose outputs summed to more than 2^63 satoshis — overflowing the signed 64-bit integer used to total them. The overflowed sum wrapped around to a small number, so the “outputs ≤ inputs” check passed, and the transaction created about 184 billion BTC out of nothing, split across two outputs — in a system whose entire supply is capped at 21 million. This is the value overflow incident (CVE-2010-5139). Within about five hours Satoshi and others released a patched client, and the network converged on a corrected chain that erased the bad transaction — one of the only times Bitcoin’s history was deliberately rewritten. The fix was, in essence, the checked_add and the range checks our validate_tx does today. It is the single best argument for the playbook’s thread: an unchecked arithmetic overflow is not a glitch here, it’s counterfeiting — and Rust’s checked_add (and its debug-build overflow panics) exists exactly so that “the number wrapped” can’t silently become “the money is fake.”

Build it

In rust/btcmini:

1. Read src/utxo.rs and run cargo test utxo. Watch spending_a_missing_output_is_a_double_spend: it applies a spend, then replays the same transaction and gets DoubleSpend — because the row is gone.
2. Run cargo run -- demo and follow the balances: Alice mines 50, pays Bob 30 with a fee of 1, and her balance moves to 70 (the 19 of change plus a fresh 50 from mining block 2).
3. Try to break conservation: in a scratch test, build a transaction whose outputs exceed its inputs and confirm validate_tx returns InsufficientFunds. Then overflow the sum deliberately and confirm checked_add catches it rather than wrapping.

Where this leaves us

The ledger now knows what a coin is, tracks every unspent one, and makes double-spending a missing-row error. But there’s a gaping hole: nothing yet stops you from spending my coins. validate_tx mentions “the right key” and “a valid signature,” but we haven’t built ownership. Tomorrow we do — secp256k1 keypairs, signing a transaction, and addresses as the hash of a public key, so that “owning a coin” means, precisely, “being able to produce a signature the chain will accept.”

→ Next: Day 18 · Keys and Signatures · Prev: Day 16 · Blocks and Hashing · Back to the Project 5 overview

Check your understanding

1. A UTXO chain stores no account balances. What does it store, and how is a wallet’s balance computed?
2. Explain precisely how the UTXO model turns a double-spend into a non-event. Why is no separate “seen-before” check needed?
3. Why does connect validate a block against a cloned working copy of the UTXO set instead of the real one? What does that protect against, and how does ? make it watertight?
4. What is the coinbase transaction, how is it recognized, and why does the crate fold the block height into it via coinbase_tag?
5. Describe the 2010 value overflow incident. Which one-line rule (and which Rust tool) is the defense, and why does the chapter call an unchecked overflow “counterfeiting”?

Show answers

1. It stores the UTXO set: a map from each unspent output (OutPoint) to its coin (TxOutput = amount
   • address). A balance isn’t stored; it’s computed on demand by summing the amounts of every unspent output locked to that address.
2. To spend a coin, a transaction’s input must name an OutPoint that is currently in the set, and applying the transaction removes it. A second spend of the same outpoint finds nothing there and is rejected. The absence of the row is the check — double-spend protection falls out of modeling coins as removable entries, so no extra bookkeeping is required.
3. Because a block must apply all-or-nothing: if transaction five is invalid, you must not have already mutated the real set for transactions one through four. Cloning gives an owned scratch copy; every validate_tx(tx)? bails on the first failure, so the real self.utxo = working assignment is reached only if the entire block was valid — no partial-write corruption.
4. The coinbase is the first transaction in each block; it has no real inputs (its single input points at the null outpoint) and mints the subsidy + fees to the miner. It’s recognized by that null input. The height tag makes otherwise-identical coinbases (same miner, same amount) have distinct txids, so their outputs don’t collide in the UTXO set.
5. On 15 August 2010 (block 74638), a transaction’s output total overflowed a signed 64-bit integer and wrapped to a small value, so the “outputs ≤ inputs” check passed and ~184 billion BTC were created from nothing (CVE-2010-5139), fixed within hours by a patched client and a chain reorg. The defense is the conservation check plus checked_add (which returns None/errors instead of wrapping). It’s “counterfeiting” because the bug literally created money the rules forbid — the failure mode of a ledger is theft, not a crash.