Day 22 · World State & Roots

Day 21 gave us the Account record. Today we assemble accounts into the world state, write the function that advances it, and then perform the move that makes a blockchain a blockchain: collapse the entire world into a single 32-byte hash that every node can compare. The headline idea is older and simpler than “blockchain” — a blockchain is just a deterministic state machine, and almost everything else (blocks, consensus, the peer-to-peer network) exists only to make thousands of computers agree on which transactions to feed it, in what order.

A blockchain is a state machine

Formally, you need two things: a current state, and a rule for turning one state into the next given an input. That’s it.

   stateₙ ──apply(tx)──▶ stateₙ₊₁ ──apply(tx)──▶ stateₙ₊₂ ──▶ ...
     │                      │                       │
 state_root            state_root'             state_root''     (a hash, one per state)

The state is our WorldState; the input is a Transaction; the rule is apply. Because the rule is deterministic — same starting state plus same transaction always yields the same next state — every honest node that processes the same ordered list of transactions arrives bit-for-bit at the same world. Consensus (which Project 5 built as proof-of-work, and which Day 25 revisits) is only about agreeing on the order. Once the order is fixed, the state is not a matter of opinion; it’s a pure function. That separation — ordering is hard and political; state is a deterministic function of the order — is the deepest idea in the whole project.

The world state map

   pub struct WorldState {
       pub accounts: HashMap<Address, Account>,
   }

A HashMap from address to account — O(1) lookup, exactly the access pattern a chain needs (given an address, fetch its account). This is the same data structure kvlite was built around, and for the same reason. But the account model adds a wrinkle Bitcoin’s coin-set didn’t have, and it surfaces the instant we try to commit the state.

The state-transition function: apply

apply is the rule, and its whole structure is dictated by the rejection-vs-revert distinction from Day 21. Read it as three phases:

   pub fn apply(&mut self, tx: &Transaction) -> Result<Receipt> {
       // 1. VALIDATE — any failure here REJECTS, touching no state.
       let sender = self.accounts.get(&tx.from).ok_or(EthError::UnknownSender(tx.from))?;
       if sender.nonce != tx.nonce { return Err(/* NonceMismatch */); }
       if sender.balance < tx.kind.value() { return Err(/* InsufficientBalance */); }

       // 2. SNAPSHOT, then consume the nonce no matter what happens next.
       let snapshot = self.accounts.clone();
       self.account_mut(tx.from).nonce += 1;

       // 3. EXECUTE — on a contract throw, ROLL BACK but keep the nonce bump.
       match self.execute(tx) {
           Ok(receipt) => Ok(receipt),
           Err(reverted) => {
               let bumped = self.nonce(&tx.from);
               self.accounts = snapshot;              // undo everything...
               self.account_mut(tx.from).nonce = bumped; // ...except the nonce
               Ok(Receipt { status: Reverted, .. })
           }
       }
   }

The validation phase reads only — if it returns Err, the caller sees an untouched world. Once we commit to including the transaction, we snapshot the whole account map, bump the nonce, and execute. If execution throws, we restore the snapshot and then re-apply only the nonce increment. That’s the precise, faithful model of “a reverted transaction is still mined and still costs the sender its nonce.”

Snapshot-and-restore is the cheap way to be atomic

Cloning the entire HashMap to snapshot it is wasteful at real-Ethereum scale (millions of accounts), and production clients instead keep a journal of individual changes they can unwind. But the semantics we want — “either every change in this transaction lands, or none of them do” — is exactly what a full snapshot gives, with code you can read in one sitting. We take the simple correct thing and name the optimisation. This is also where Rust quietly helps: because WorldState owns its accounts (no shared references escaping), self.accounts = snapshot drops the half-mutated map and installs the saved one with no aliasing hazard — the restore can’t leave a dangling reference to a rolled-back account.

The state root: 32 bytes that fingerprint the world

Now the move that makes nodes able to agree. Two computers each ran the same transactions; how do they check, in one cheap comparison, that they reached the identical state — without shipping the entire account map to each other? They each hash their world down to a single value, the state root, and compare the hashes.

   pub fn state_root(&self) -> [u8; 32] {
       // 1. SORT by address — HashMap order is randomised, so we must canonicalise.
       let mut sorted: Vec<_> = self.accounts.iter().collect();
       sorted.sort_by_key(|(addr, _)| **addr);
       // 2. SERIALISE the sorted pairs to bytes, then SHA-256 them.
       let bytes = serde_json::to_vec(&sorted).expect("serialisable");
       Sha256::digest(&bytes).into()
   }

The non-obvious line is the sort, and it’s where the HashMap choice bites back. A HashMap’s iteration order is deliberately randomised (per run, to thwart hash-flooding attacks). If we hashed the accounts in iteration order, two nodes with the identical state would serialise it in different orders and compute different roots — a catastrophe for a system whose entire job is agreement. So before hashing we sort by address, producing a canonical byte string that is a function of the state and nothing else. (This is exactly why Address derives Ord back on Day 21.) Change any byte of any account — a balance, a nonce, one storage slot — and the root changes; change nothing and it is identical, on every machine, forever.

By the numbers — what 32 bytes buys you

The whole world — every account, balance, nonce, storage slot, and contract — collapses to a 256-bit (32-byte) digest. Two nodes comparing states exchange 32 bytes instead of the entire database. The security argument is the collision resistance of the hash: to forge a different world with the same root, an attacker faces roughly 2^128 work (the birthday bound on a 256-bit hash) — about 3.4 × 10^38 operations, comprehensively infeasible. That asymmetry — a gigabyte of state, a 32-byte commitment, 2^128 to cheat — is the entire reason hashes are the load-bearing primitive of every blockchain.

Where the trie comes in (and why ours doesn’t need one yet)

Our sort-and-hash root is correct but blunt: it has two real weaknesses, and naming them tells you exactly why real Ethereum uses something fancier.

   our root:  change ONE storage slot  →  re-serialise & re-hash the WHOLE world
   a trie:    change ONE storage slot  →  re-hash only the O(log n) nodes on its path

1. Incremental updates. With sort-and-hash, touching one account forces re-hashing everything. A tree of hashes (a Merkle tree) lets you re-hash only the path from the changed leaf to the root — O(log n) work instead of O(n).
2. Proofs. A trie can prove “account X has balance B” to someone holding only the root, by handing over the O(log n) sibling hashes along X’s path — a Merkle proof. Our flat hash can prove nothing short of revealing the entire state. This is what lets a light client trust a full node without downloading the chain.

Real Ethereum uses a Merkle-Patricia trie — a Merkle tree married to a radix (Patricia) trie, keyed by address (and, within each contract, by storage slot). It delivers both properties: cheap incremental root updates and compact proofs. We skip it because at our scale neither matters, and a trie would be more code than the lesson. The honest framing for the whole page: our state root has the right meaning (a deterministic commitment to the entire world) but the wrong data structure for production. Same idea, simpler machine.

It actually happened — when a 32-byte mismatch splits the chain

Because the state root is consensus-critical, two clients that disagree on it by a single byte will reject each other’s blocks and fork the network. On 11 November 2020, a long-standing Ethereum client, Geth, processed a particular mainnet block differently from other clients owing to a subtle bug, producing a different state root and causing an unintended chain split that took hours to resolve. Nobody stole anything; the lesson is sharper than theft. The state root is the one number every node must compute identically, so determinism isn’t a nicety — a lone discrepancy in how one client serialises or updates state is enough to break consensus. It’s why we sort before hashing, and why “deterministic” was the first word of this page.

The thread

What does building this force you to understand, and what is Rust’s compiler protecting you from? Today it forced the difference between ordering (hard, the job of consensus) and state (a deterministic function of the order, the job of apply), and it forced atomicity — a transaction’s changes land whole or not at all. Rust carried its weight on both: ownership made snapshot-and-restore a safe whole-value swap with no aliasing into the rolled-back map, and the type system made state_root total over a Serialize-able world. And the project’s question — what problem did Ethereum solve? — gained its sharpest tool: a single 32-byte root that lets a planet of distrusting computers verify they hold the identical world without exchanging it. Tomorrow we give that world the ability to run code.

→ Next: Day 23 · A Tiny VM · Prev: Day 21 · Accounts vs UTXO · Back to the Project 6 overview

Check your understanding

1. The page says a blockchain is “a deterministic state machine” and that “consensus is only about agreeing on the order.” Unpack that: once the order of transactions is fixed, why is the resulting state not a matter of opinion?
2. Trace the three phases of apply for a transaction that is valid but whose contract call runs out of gas. Which state survives, and which is rolled back?
3. Why must state_root sort the accounts before hashing? What concretely goes wrong if it hashes them in HashMap iteration order instead?
4. Name the two capabilities a Merkle-Patricia trie gives real Ethereum that our sort-and-hash root does not, and say what each one is good for.
5. The page claims our state root has “the right meaning but the wrong data structure.” Restate what the root means, and why that meaning is what makes inter-node agreement possible.

Show answers

1. Because apply is a pure, deterministic function: the same starting state plus the same transaction always produces the same next state. So once everyone agrees on the ordered list of transactions, each honest node computes bit-for-bit the same world by replaying them — there’s nothing left to disagree about. All the genuine difficulty (and politics) is in agreeing on the order, which is consensus’s job, not apply’s.
2. Phase 1 (validate) passes — it’s a valid transaction. Phase 2 snapshots the account map and bumps the sender’s nonce. Phase 3 (execute) throws (out of gas), so we restore the snapshot and then re-apply only the nonce bump. Survives: the nonce increment. Rolled back: every other change (the value transfer and any storage writes). Status is Reverted.
3. A HashMap’s iteration order is randomised, so two nodes with the identical state would serialise it in different orders and hash to different roots — breaking the one thing the root exists to do (let nodes agree). Sorting by address produces a canonical byte string that depends only on the state, so identical states always yield identical roots.
4. (a) Incremental updates — re-hash only the O(log n) nodes on a changed leaf’s path instead of re-hashing the whole world; good for performance as state grows. (b) Merkle proofs — prove a single account/slot’s value to someone holding only the root, using O(log n) sibling hashes; good for light clients that trust without downloading the full state.
5. The root means: a single 32-byte cryptographic commitment to the entire world state, identical iff the states are identical. That meaning is what enables agreement — distrusting nodes compare 32 bytes instead of exchanging the whole database, and a collision-resistant hash makes forging a different world with the same root infeasible (~2^128 work).