State & the trie: one hash for the whole world
The EVM computes over storage — but where does that storage actually live, and how does a network of strangers agree it's byte-for-byte identical without shipping gigabytes to each other? This chapter derives the Merkle-Patricia trie: the structure that squeezes all of world state into a single 32-byte root you can update cheaply and prove against.
- the EVM & storage
- hashing (keccak256)
Chapter 2 left a thread hanging. The EVM’s storage — the only place a contract’s data survives — is, we said, “committed to the state trie and held on every node’s disk.” But what is that trie, and why that shape? The real problem underneath it is stark: hundreds of thousands of machines, run by strangers, each hold all of Ethereum’s state — every account balance, nonce, contract, and storage slot — and they have to agree it’s exactly the same, block after block. You can’t do that by emailing each other gigabytes and diffing. This chapter derives the structure that makes it possible, the same way we derive everything: start with the dumbest thing that could work and fix what breaks.
The problem: prove two worlds are identical, cheaply
The world state The complete mapping from every account address to its state — balance, nonce, and for contracts the code hash and storage. This is what a block's execution transforms; every full node holds all of it. is enormous and always changing. Two nodes need a way to check they hold the identical state without shipping it all — and, separately, to prove a single fact (“account 0xa7… holds 12 ETH”) to someone who doesn’t have the state at all. Both needs point at the same tool: a cryptographic fingerprint. Hash the whole state into one 32-byte number, and if two nodes’ numbers match, their states match; change one wei anywhere and the number flips.
→ Step 2: earn the structure, one fix at a time.
From a plain map to a Merkle-Patricia trie
Watch the structure build itself. Each stage below fixes the previous one’s flaw — a plain map has no commitment at all; hashing it into one number commits but can’t prove or update cheaply; hashing in a tree means a change only re-hashes one path and any leaf can be proven by its branch; making the key itself the route down the tree makes the shape canonical (everyone builds the identical tree); and collapsing long single-child runs removes the wasted nodes. What falls out is the Merkle-Patricia trie Ethereum's state structure: a radix trie keyed by the path through the data, where every node also commits to the hash of its children (Merkle), and unbranched paths are compressed (Patricia). Gives a single root hash, O(log n) updates, and compact inclusion proofs. .
Deriving the Merkle-Patricia trie
Two properties are worth naming, because everything downstream leans on them. A Merkle root The hash at the top of a tree of hashes, where each node hashes its children. Because the hash propagates upward, the single root commits to every leaf beneath it — and a short list of sibling hashes (a branch) proves any one leaf. commits to every leaf through a chain of child-hashes, so one root fixes the entire dataset. And because the key determines the path, the tree is canonical: given the same accounts, every client independently builds the byte-for-byte same trie and therefore the same root. No ordering choices, no ambiguity.
→ Step 3: the three kinds of node.
Leaf, extension, branch — and why exactly three
A key is first hashed and then read four bits at a time. Each 4-bit chunk is a nibble Half a byte — one hex digit, 0–f. Trie keys are traversed one nibble at a time, so every branch point has 16 possible directions, one per nibble value. , so at any branch point there are sixteen possible directions. That fixes the node types you need: a branch node A 17-slot node — one child pointer per nibble (0–f) plus a value slot. Used wherever paths actually diverge. for where paths genuinely diverge, an extension node A node that stores a shared sequence of nibbles and a single child pointer — the Patricia compression that collapses a long non-branching run into one node. to collapse a shared run of nibbles into one node, and a leaf node A node holding the remaining nibbles of a key plus its value — the end of a path. to hold the tail of the key and its value.
That “each node also stores its children’s hashes” is the quiet load-bearing detail: it’s what fuses a plain routing trie (Patricia) with a hash tree (Merkle). The route makes lookups deterministic; the hashes make the whole thing tamper-evident up to the root.
- 1 split into 4-bit chunks; each nibble picks one of a branch's 16 directions
- 2 hash the key first — spreads keys evenly so the trie stays shallow and balanced
→ Step 4: change one balance and watch it propagate.
One balance changes; only its path re-hashes
Here’s the payoff for all that structure. Change a single account’s balance and you don’t touch the rest of the trie. You rewrite the leaf, then walk up its path re-hashing each parent — because a node’s hash depends on its children, a changed child forces a new hash all the way to the root. Every node not on that path keeps its old hash untouched and is simply reused. Scroll through it:
0xa7c1→- 01 / 06
An account is a path
Alice's key 0xa7c1 isn't stored in a row somewhere — it's a route. Read it one nibble at a time, a → 7 → c → 1, and each nibble picks the next turn down the tree until you reach her leaf.
- 02 / 06
Three kinds of node
The route is built from just three parts. A branch is a 16-way fork. An extension is a shortcut that swallows a run of shared nibbles. A leaf is the end of the road, holding the value.
- 03 / 06
Change one balance
Alice spends some ETH: 12.0 → 99.0. Only her leaf is touched — its bytes change, so its hash must change. Nothing else in the tree has moved yet.
- 04 / 06
Re-hash, bottom-up
A node's hash is built from its children's hashes. So the new leaf hash forces its parent to re-hash, which forces its parent… a wave of recomputation travels straight up Alice's path — and only her path.
- 05 / 06
A brand-new state root
The wave reaches the top. The root node emits a fresh 32-byte hash: the new state root. Every node on Earth, fed the same edit, computes this exact same number.
- 06 / 06
It lands in the header
That root drops into the block header's stateRoot slot. One changed balance has changed the block's identity — this is where state and consensus are welded together.
So an update is O(depth), not O(state size): a handful of hashes, not millions. That same path — the leaf plus the sibling hashes along the way — is exactly a Merkle proof The leaf plus the sibling hashes on the path to the root. Anyone holding only the root can recompute upward and confirm the leaf is included — proving one account without the rest of the state. : hand it to someone who has only the root and they can verify that one account, without the rest of the state. Cheap updates and compact proofs are the same property, read in two directions.
→ Step 5: where the root actually goes.
The state root in the block header
The whole point of collapsing state to one hash is what you can now do with it. The state root The hash of the state trie's root node — a single 32-byte commitment to all of world state after a block executes. It's stored in the block header alongside the transactions and receipts roots. becomes a single field in the block header, sitting beside the transactions root and receipts root. Execute the block, compute the new state root, and drop it in. Now agreeing on a header is identical to agreeing on all of world state — a few hundred bytes stand in for the entire chain’s memory. And because each header also names its parent’s hash, changing any past state would change that block’s root, its hash, and every hash after it.