The World State: A Map of address → account

The previous page opened up one account and found four fields: nonce, balance, storageRoot, codeHash. That is the value half of the ledger. This page assembles the whole ledger — every account there has ever been — into a single structure, and then does something that sounds impossible: it squeezes that entire structure down to 32 bytes that every node on Earth can compare in a microsecond.

That structure is the world state, and those 32 bytes are the state root. Together they are the commitment device that makes “untrusting strangers agree on a shared world” more than a slogan. This page builds both from first principles: why the state is a map, why lookup is by address, and why the root has the almost magical property of changing if and only if a single byte of the world changed.

The world state is one global map

Start with the smallest honest definition. The world state at any instant is:

a single map from a 20-byte address to that account’s record.

Nothing more. Every wallet, every deployed contract, every balance, every nonce, every storage slot, and every byte of code in the entire system is an entry — or lives inside an entry — of that one map. There is no second table, no side ledger, no “system” data hiding elsewhere. When people say “the state of Ethereum,” this map is the referent.

   WORLD STATE  :  Address (20 bytes)  ──▶  Account record

   0x0000…0001 ──▶ { nonce: 3,  balance: 12.4 ETH, code: —,   storage: —        }   (a wallet / EOA)
   0x00a0…f19c ──▶ { nonce: 0,  balance: 0.0 ETH,  code: 0x60…, storage: {…}     }   (a contract)
   0xdead…beef ──▶ { nonce: 1,  balance: 0.5 ETH,  code: —,   storage: —        }   (a wallet / EOA)
              ⋮

Read that picture as the complete memory of the world computer at one instant. Feed a transaction to it and every meaningful change — value moved, a counter bumped, a storage cell written, a new contract born — is a change to some entry in this map. The map is the tape the machine reads and writes; everything else in the book (blocks, gas, consensus) exists only to agree on which edits to make and in what order.

Why a map, and why keyed by address

Why is a map the natural shape — as opposed to Bitcoin’s set of coins, or a list, or a tree of transactions? Because of the access pattern. Ask what the machine actually needs to do a billion times a day, and the answer is always the same shape of question:

“Given this address, what is its account right now?”

A transfer needs the sender’s balance and nonce: two lookups by address. A contract call needs the target’s code and one storage slot: lookups by address (and by storage key inside it). Deriving a new contract’s address, checking replay protection, charging a fee — every one of these is given an address, fetch its record. The dominant operation is keyed retrieval, and the data structure whose whole job is keyed retrieval is a map. Choosing a map is not a stylistic call; it is reading the access pattern off the workload and picking the structure that serves it in one step.

Contrast the alternatives and the fit is obvious:

• A list of accounts would force a linear scan to find “the account at address 0x…” — O(n) per lookup, over tens of millions of accounts, per operation. Unusable.
• A set of coins (Bitcoin’s model, covered in Two Ledgers) has no notion of a stable, addressable identity that persists and mutates — exactly the thing a program needs to remember between calls.
• A map gives O(1)-ish lookup by the key the workload already holds: the address. Given the address, you get the record. That is the whole interface.

This is exactly how our companion crate models it. WorldState is, at heart, a HashMap<Address, Account>:

/// The entire ledger: every account, keyed by address.
pub struct WorldState {
    pub accounts: HashMap<Address, Account>,
}

impl WorldState {
    /// Read an account (returns `None` if it has never been touched).
    pub fn account(&self, addr: &Address) -> Option<&Account> {
        self.accounts.get(addr)
    }
}

Note one subtlety the code makes explicit: an address that has never been touched returns None, which the balance/nonce readers treat as zero. There is no distinction between “an account with zero balance and zero nonce” and “an account that does not exist” — the map’s default is the empty account. That keeps the state finite: the map holds only entries that were actually written, even though its logical domain is all 2^160 possible addresses.

Collapsing the whole world to 32 bytes

Now the hard part. Two nodes on opposite sides of the planet each hold their own copy of this map — tens of millions of entries, gigabytes of data. They do not trust each other. How can they check, cheaply, that their two copies are identical down to the last byte?

Shipping the whole database back and forth is absurd. The answer is a commitment: hash the entire state down to a single fixed-size fingerprint, and compare those.

The state root is a single 32-byte hash of the entire world state. It changes if and only if some byte of the state changed. Two states with the same root are, to cryptographic certainty, the same state; two states with different roots differ somewhere.

That “if and only if” is the whole trick. A good hash is:

• Deterministic — the same input always produces the same output, so two honest nodes with the same state compute the same root.
• Sensitive — flip one bit of one balance and the 32-byte output changes completely (this is the avalanche property). You cannot alter the world and keep the root.
• Collision-resistant — you cannot find two different states that hash to the same root, so a matching root is a reliable proof of a matching state.

So instead of exchanging gigabytes, two nodes exchange 32 bytes. Equal roots → agreement, verified. Unequal roots → someone is on a different state, and they know it instantly. The state root turns “do our entire worlds match?” into a 32-byte integer comparison. That is the mechanism that lets distrusting strangers agree without re-sending the world.

By the numbers — 32 bytes vs. the whole database

Full Ethereum state (order of magnitude, as of 2024):   ~10s of GB, ~200M+ accounts
A state root:                                            32 bytes (256 bits)

To check "are our states identical?":
  naive  : exchange & diff ~10s of GB     ← infeasible per block, for every peer
  root   : compare 32 bytes               ← a single machine-word-scale comparison

Compression ratio (state → commitment):   ~10^9 : 1 (tens of GB → 32 bytes)
Distinct roots representable by 32 bytes:  2^256  ≈ 1.16 × 10^77

32 bytes cannot contain the state — that would violate information theory. It commits to the state: it is a one-way fingerprint that no feasible adversary can forge or collide, so a matching root is proof of a matching world.

Canonical ordering: the same world must produce the same bytes

There is a trap hiding in “hash the whole map.” A hash takes a byte string, but a map is a set of key→value pairs with no inherent order. If node A serialises its accounts in one order and node B in another, they feed different byte strings to the hash and get different roots — even though they hold the identical world. Agreement would fail not because the states differ, but because the serialisation did.

So before hashing, the state must be laid out in a canonical (deterministic) order — an ordering that depends only on the state’s contents, never on insertion history, memory layout, or which node you ask. The obvious canonical order is sorted by address. Our companion crate does exactly this, and it comments on why:

/// The state root: a hash over the entire world state, serialised in a
/// *fixed, sorted* order. Change anything and the root changes; change
/// nothing and it stays identical.
pub fn state_root(&self) -> [u8; 32] {
    // A HashMap's iteration order is randomised per run, so we MUST sort
    // by address first — otherwise the same state hashes to different bytes.
    let mut sorted: Vec<(&Address, &Account)> = self.accounts.iter().collect();
    sorted.sort_by_key(|(addr, _)| **addr);

    // ...serialise the sorted pairs to bytes, then SHA-256 the result.
    let bytes = serialize(&sorted);
    sha256(&bytes)
}

The HashMap gives fast lookup but randomises iteration order per run on purpose (to resist denial-of-service attacks). That randomness is poison for a commitment: two runs over the same state would serialise differently and hash to different roots. Sorting by address neutralises it — the root becomes a pure function of the state and nothing else. Even the account’s own storage, one level down, must serialise in a fixed order for the same reason, which is why the record’s storage is a sorted BTreeMap rather than a HashMap.

The lesson generalises: a commitment is only as trustworthy as the determinism of the bytes it commits to. Canonicalisation is not a detail — it is what makes the root mean “same world” instead of “same world, serialised the same way, on the same build.”

From sort-and-hash to a Merkle-Patricia trie

Our teaching model sorts the whole map and hashes it in one shot. That is honest and correct — it gives a deterministic root — but it is blunt. Two costs make it unworkable at Ethereum’s scale, and fixing them is why real Ethereum uses a Merkle-Patricia trie for the state root instead.

Cost 1 — recomputation. Every block changes only a handful of accounts. With sort-and-hash, changing one balance forces you to re-serialise and re-hash the entire map — tens of millions of accounts — just to learn the new root. That is O(n) work per block for an O(1) change. A trie stores the state as a tree of hashes: changing one account rehashes only the nodes on the path from that leaf up to the root — O(log n) — and leaves the rest untouched. Cheap incremental updates.

Cost 2 — proofs. A light client (a phone, a browser wallet) cannot hold the whole state. It wants to ask a full node “what is Alice’s balance?” and verify the answer without downloading gigabytes. A flat hash can prove nothing about a single entry short of revealing everything. A Merkle tree can: the full node returns Alice’s account plus a short list of sibling hashes (a Merkle proof), and the light client re-hashes just that path. If it lands on the state root it already trusts, the answer is proven — from an untrusted server. Merkle proofs to light clients.

   SORT-AND-HASH (our model)          MERKLE-PATRICIA TRIE (real Ethereum)

   [ entire sorted state ]            state root
          │                              ├── branch ── … ── leaf: Alice
       sha256                           ├── branch ── … ── leaf: Bob
          │                             └── branch ── … ── leaf: contract
      state root                     ┌──────────────────────────────────┐
                                     │ change 1 account → rehash 1 PATH  │
   change 1 account →                │ prove 1 account → send 1 PATH     │
   rehash EVERYTHING (O(n))          └──────────────────────────────────┘

Both structures yield a single 32-byte root with the same meaning — a commitment to the whole state that changes iff the state changes. The trie just earns that root the smart way: incremental updates instead of full recomputation, and per-entry proofs instead of all-or-nothing. The trie’s internals — nibbles, leaf/extension/branch nodes, and why a Patricia trie rather than a plain Merkle tree — are the subject of the State & Tries part; see Why a trie, not a Merkle tree and Proofs and light clients. For this part, hold the property: one root, commits to everything, changes with any change.

Under the hood — where the state root lives and why consensus needs it

The state root is not a loose fact nodes gossip about; it is written into every block header. When a validator proposes a block, it applies that block’s transactions to the previous world state, computes the resulting state root, and stamps it into the header. Every other node re-executes the same transactions against its own copy of the state and checks that its computed root equals the one in the header.

That check is the enforcement mechanism for the entire book’s question. A proposer cannot slip Alice an extra ETH: doing so changes the state, which changes the root, which no longer matches what honest re-execution produces — and the block is rejected. The state root is what makes consensus be about the result of computation, not merely the list of transactions. Everyone agrees on 32 bytes, and those 32 bytes pin down every balance, nonce, slot, and byte of code in the world. (How proposals become final is the Consensus part; how one transaction advances the state in the first place is the next page.)

The architect’s lens

• Why does it exist? Distrusting strangers must confirm they hold the same world without shipping the whole database to each other. The state root exists to compress an entire mutable world into 32 comparable bytes — a commitment, not a copy.
• What problem does it solve? It turns “are our two multi-gigabyte states byte-for-byte identical?” into a 32-byte integer comparison, and (via a Merkle structure) lets a light client prove one account’s value against a root it trusts, from an untrusted server.
• What are the trade-offs? You buy cheap verification and cheap proofs by paying to keep the commitment structure canonical and up to date: every state change must rehash a path to the root, and the whole state must have a deterministic serialisation. Sort-and-hash is simple but O(n) per change; a Merkle-Patricia trie is O(log n) but far more intricate to implement correctly.
• When should I avoid it? When there is no distrust and no need for proofs — a single trusted database with one operator has no reason to pay for a cryptographic commitment on every write. The root earns its keep precisely when many mutually-distrusting parties must agree cheaply.
• What breaks if I remove it? Everything downstream. Without a canonical root, nodes can’t detect that they’ve diverged, light clients can’t verify anything, and a dishonest proposer could hand different “states” to different peers with no way to catch it. Remove the root and “untrusting strangers agree on a shared world” collapses back into “trust me.”

Check your understanding

1. State the one-sentence definition of the world state, including the key type and the value type.
2. Why is the access pattern “given an address, fetch its account” — and why does that pattern make a map the natural structure rather than a list or a set?
3. What is the state root, and what precise property connects it to the state (complete the phrase “changes if and only if…”)?
4. Why must the state be put in a canonical order before hashing? Give a concrete failure that occurs if two nodes serialise the same state in different orders.
5. Give the two concrete advantages a Merkle-Patricia trie has over our blunt sort-and-hash, and say which one a light client on a phone cares about most.

Show answers

1. The world state is a single global map from a 20-byte address to that account’s record (nonce, balance, storageRoot/storage, codeHash/code) — the complete, shared memory of the world computer at one instant.
2. Because nearly every operation the machine performs — read a balance, check a nonce, fetch a contract’s code or a storage slot, derive an address — is of the form given an address, retrieve its record. The dominant operation is keyed retrieval, and a map serves keyed retrieval in one step (≈O(1)); a list would force an O(n) scan per lookup, and a set of coins has no stable, addressable, mutable identity a program can remember between calls.
3. The state root is a single 32-byte hash of the entire world state. It changes if and only if some byte of the state changed — so two states with the same root are (to cryptographic certainty) identical, and two states with different roots differ somewhere. It lets nodes compare 32 bytes instead of exchanging the whole database.
4. A hash consumes an ordered byte string, but a map has no inherent order; without a canonical (e.g. sorted-by-address) serialisation, the same world can be laid out as different bytes and hash to different roots. Concrete failure: two honest nodes holding the identical state — but iterating their maps in different orders (as a HashMap does, randomised per run) — compute different roots and wrongly conclude they disagree. Sorting by address makes the root a pure function of the state’s contents.
5. (1) Cheap incremental updates — changing one account rehashes only the path from that leaf to the root (O(log n)) instead of re-serialising and re-hashing the whole map (O(n)); (2) Merkle proofs — a full node can prove one account’s value with a short sibling-hash path that verifies against the trusted root. A light client on a phone cares most about the proofs: it can verify “Alice’s balance is X” from an untrusted server without downloading the state.