Overview — State & the Merkle-Patricia Trie

In the Accounts & State part we said something that sounds almost too bold to be true: at any moment, the entire Ethereum world — every account’s balance and nonce, every contract’s code, every storage slot of every contract — is committed by a single 32-byte number in each block header, the stateRoot. Change one wei in one account and that number changes. Change nothing and it stays byte-for-byte identical. That property is what lets untrusting strangers agree not just on a list of transactions, but on the exact world those transactions produce.

This part answers the question that a bold claim like that demands: how can 32 bytes commit to gigabytes of state — and why does the data structure hiding behind the root matter at all? The short answer is that the root is the top of a hash tree, and the shape of that tree decides whether the commitment is cheap to maintain and cheap to prove. Ethereum’s choice is the Merkle-Patricia Trie (MPT). By the end of the part you will be able to build a small one, update it, and hand a light client a proof that some account holds exactly what you claim — without shipping the whole state.

Where we left off: the right meaning, the wrong structure

Our companion crate ethmini already computes a state root. Look at how it does it:

/// The state root: a hash over the entire world state, serialised in a
/// fixed, sorted order. Change anything and the root changes.
pub fn state_root(&self) -> [u8; 32] {
    // Sort accounts by address for a canonical serialisation.
    let mut sorted: Vec<(&Address, &Account)> = self.accounts.iter().collect();
    sorted.sort_by_key(|(addr, _)| **addr);
    // Serialise the sorted pairs, then hash the whole blob.
    let bytes = serde_json::to_vec(&sorted).expect("serialisable");
    Sha256::digest(&bytes).into()
}

This is honest, and its meaning is exactly right: it is a deterministic fingerprint of the whole world. Two nodes with the same state get the same 32 bytes; any difference shows up as a different root. For a teaching model that is enough.

But as the world’s commitment it is the wrong data structure, for two concrete reasons:

• Updates are O(n). A single transfer touches two accounts, yet state_root re-serialises and re-hashes every account to get the new root. On a chain with hundreds of millions of accounts, recomputing the root from scratch after every transaction — thousands per block — is a non-starter.
• There are no proofs. The root is one opaque hash of one big blob. To convince someone that Alice’s balance is 5 ETH, you must hand them the entire blob so they can re-hash it and check. There is no way to prove one account without revealing all of them. A phone wallet cannot download all of state, so with this structure it can never verify anything for itself.

A flat sort-and-hash root has the right semantics and the wrong ergonomics. Fixing the ergonomics without losing the semantics is the whole job of this part.

The two properties Ethereum actually needs

State the requirements as design constraints, and the trie almost designs itself:

1. Cheap incremental root updates. Applying a block changes a small fraction of state. Recomputing the root should cost work proportional to what changed, not to the size of the whole world — roughly O(log n) hashing per touched key, not O(n).
2. Compact Merkle proofs. For any single key (an account, or a storage slot), a node must be able to produce a short proof — again roughly O(log n) hashes — that a light client can check against just the 32-byte root, with no access to the rest of state. This is what makes light clients, and later fraud/validity proofs and cross-chain bridges, possible.

   flat sort-and-hash          Merkle-Patricia trie
   ┌───────────────────┐       ┌───────────────────┐
   │ update a key:      │       │ update a key:      │
   │   rehash ALL  O(n) │  vs.  │   rehash path O(log n)
   │ prove a key:       │       │ prove a key:       │
   │   ship ALL state   │       │   ship path  O(log n)
   └───────────────────┘       └───────────────────┘

A Merkle tree of the sorted key-value pairs already buys property 2 (compact proofs). But a plain balanced Merkle tree does not buy property 1 cheaply, because inserting a new key can reshuffle the leaves and disturb many hashes. The next page, Why a Trie, Not a Plain Merkle Tree, shows exactly where a plain Merkle tree falls down and why keying the tree by the path of the key itself (a trie) is what makes both incremental updates and stable proofs fall out at once.

The cast of characters

The rest of the part introduces the machinery in dependency order. Meet the players now so the roadmap reads as a story rather than a glossary:

• RLP and nibbles — the encoding primitives. Before you can hash a node you must turn it into a canonical byte string. RLP (Recursive Length Prefix) is Ethereum’s one serialisation format for everything the protocol hashes. Nibbles are 4-bit half-bytes: the trie walks a key one nibble at a time, so a 32-byte key becomes a 64-step path.
• The three node types — leaf, extension, branch. A trie is built from just three kinds of node. A branch is a 16-way fork (one slot per nibble value 0–f) plus a value. An extension compresses a long shared run of nibbles into one node so the trie does not degenerate into a chain of single-child branches. A leaf holds the final key remainder and its value.
• The four tries. Ethereum does not have one trie; it has four, and they nest. The state trie maps address → account. Each contract account’s storageRoot is itself the root of a storage trie mapping slot → value. Every block also commits a transactions trie and a receipts trie over its own body. One idea, applied four times.
• Proofs and light clients. With the structure in place, a Merkle proof is just the list of sibling hashes along the path from a leaf up to the root — the payload behind eth_getProof, and the foundation of every trust-minimised client that cannot store all of state.

Roadmap for this part

Read these in order. Each page uses only ideas from the pages above it.

#	Page	What it builds	Depends on
2	Why a Trie, Not a Plain Merkle Tree	The design argument: why a plain sorted Merkle tree gives proofs but not cheap updates, and how keying by the key’s own path fixes both.	This overview; Merkle trees from Cryptography
3	RLP and Nibbles — The Encoding Primitives	RLP as Ethereum’s universal serialisation, and nibbles as the 4-bit path alphabet the trie walks.	Hashing; byte encoding
4	The Three Node Types — Leaf, Extension, Branch	The full node vocabulary, the hex-prefix encoding that distinguishes leaf from extension, and how a lookup and an insert walk the nodes.	RLP & nibbles (page 3)
5	The Four Tries — State, Storage, Transactions, Receipts	How one trie design is instantiated four times, and how the storage trie nests inside the state trie via each account’s storageRoot.	Node types (page 4); accounts
6	Merkle Proofs and Light Clients	Building and verifying a proof against a root, what eth_getProof returns, and why this is the bedrock of light clients and bridges.	All of the above
900	Revision — State & the Merkle-Patricia Trie	A one-page recap of the whole part, ready for self-testing.	—

By the numbers — why O(n) per block does not scale

Rough figures, to feel the two structures apart. As of 2024 Ethereum’s state holds on the order of hundreds of millions of accounts and storage slots, and a block packs on the order of hundreds of transactions, each touching a handful of keys.

Flat sort-and-hash, per block:
  work  ≈ (keys in whole state) × (txs per block)
        ≈ 3×10^8 × 300              ≈ 9×10^10 hash-sized ops   ← re-hash the world, 300 times

Merkle-Patricia trie, per block:
  work  ≈ (keys touched) × (depth)   × (txs per block)
        ≈ 5 × 8                       × 300 ≈ 1.2×10^4 node hashes  ← only the touched paths

Ratio ≈ 9×10^10 / 1.2×10^4  ≈  7 million×  less work

The exact constants are illustrative, not measured — but the shape is the point: flat scales with the size of the world, the trie scales with the size of the change. That gap is the entire reason the trie exists.

The thread

Tie it back to the book’s one question — how do untrusting strangers agree on the state of a shared world computer, and what does it cost to run one? This part is the “agree on the state” half, made mechanical. The stateRoot is how a stranger can commit to the whole world in 32 bytes; the trie is what makes that commitment cheap enough to update every 12 seconds and provable enough that a phone can check a single balance against it. The cost half shows up too: the trie’s shape is why full nodes must keep a large, randomly-accessed database, and why state growth — not raw transaction throughput — is one of the deepest long-run pressures on the “world computer.” Keep both halves in view: the trie is simultaneously what makes trust-minimised agreement possible and one of the things that makes running a node expensive.

Start with Why a Trie, Not a Plain Merkle Tree →

Check your understanding

1. Ethereum commits its whole world state to one 32-byte stateRoot per block. What does it mean, precisely, to say two nodes “agree on the state” in terms of this number?
2. The ethmini flat sort-and-hash root has “the right meaning but the wrong data structure.” Name the right meaning it gets, and the two specific things it gets wrong.
3. State the two properties Ethereum needs from its state commitment, and for each say what a flat sort-and-hash root fails to provide.
4. Why can a plain balanced Merkle tree over sorted key-value pairs give you compact proofs but still fail the cheap-incremental-update requirement? (One sentence is enough — the next page proves it.)
5. Ethereum has four tries, not one. Name them, and explain the sense in which the storage trie is “nested inside” the state trie.

Show answers

1. It means both nodes, applying the same ordered transactions to the same starting state, computed the identical stateRoot. Because the root changes if and only if some part of the state changed, matching roots is a compact proof that two independently-maintained copies of the world are bit-for-bit identical — without comparing the states directly.
2. Right meaning: it is a deterministic, canonical fingerprint of the entire world — the same state always hashes to the same 32 bytes, and any difference changes the root. Wrong structure, two ways: (a) updates are O(n) — it re-serialises and re-hashes every account to reflect a change to one, and (b) it supports no per-key proofs — proving one account requires shipping the whole blob so the verifier can re-hash it.
3. (1) Cheap incremental root updates — work proportional to what changed, not to the whole state; the flat root is O(n) per change. (2) Compact Merkle proofs — a short O(log n) proof of a single key checkable against just the root; the flat root offers no way to prove one key without revealing all of them.
4. Because inserting or deleting a key in a tree keyed by sorted position can shift where later leaves sit and disturb many hashes, so an “incremental” update is not actually cheap; keying the tree by the path of the key itself (a trie) keeps each key at a fixed location, so only the path to that key needs re-hashing.
5. The state trie (address → account), the storage trie (slot → value, one per contract), the transactions trie, and the receipts trie (both over a block’s body). The storage trie is nested because each contract account stored in the state trie contains a storageRoot field — which is itself the 32-byte root of that contract’s own storage trie — so the single top-level stateRoot transitively commits to every contract’s storage as well.