Revision — State & the Merkle-Patricia Trie

This part answered one half of the book’s throughline — how do untrusting strangers agree on the state of a shared world computer? — by pinning down what “the state” actually is and how it gets squeezed into a single number. A block header is a few hundred bytes, yet it commits every account balance, every contract’s code, and every storage slot on Ethereum. The trick that makes that possible is the Merkle-Patricia trie (MPT), and this recap ties the six pages together into the one mental model you should walk away with.

The short version: Ethereum’s world is a giant key-value map, that map is stored in a trie, the trie hashes up to one 32-byte stateRoot, and that root is the fingerprint against which anyone — from a full node to a phone — can prove any fact about the chain. Everything below is the why underneath that sentence.

The problem the part solved

The overview set the stage. Ethereum’s state is not a list of transactions or unspent coins the way Bitcoin’s is; it is a snapshot — a live mapping from 20-byte address to an account object. The state-transition function takes stateₙ and a transaction and produces stateₙ₊₁. Consensus, blocks, and the peer-to-peer network all exist only to agree on which transactions feed that function and in what order.

But agreeing on a multi-gigabyte map is hopeless if peers have to ship the whole thing around and re-hash it byte by byte. So the real requirement is a commitment: a small value that (a) changes if and only if the state changes, (b) is identical for everyone who holds the same state, and (c) lets you prove one entry without revealing or downloading the rest. The rest of the part is the construction that delivers all three at once.

   whole world state (GBs)          one commitment (32 bytes)
   ┌───────────────────────┐        ┌───────────────┐
   │ addr → { nonce,       │        │               │
   │          balance,     │  ───▶  │   stateRoot   │
   │          codeHash,    │        │  0x a7f3 …    │
   │          storageRoot }│        │               │
   └───────────────────────┘        └───────────────┘
     millions of entries              in the block header

Why a trie, not a plain Merkle tree

The second page is the load-bearing “why.” A plain Merkle tree — the kind Bitcoin uses for transactions — is a fine membership proof over a fixed, ordered list. Ethereum’s state is neither fixed nor a list: it is a mutable map whose keys arrive in no particular order and get updated thousands of times per block. Four properties made a trie the right tool where a plain Merkle tree is not:

Keyed, not positional. In a Merkle tree an item is found by its index; in a trie an item is found by following its key down the branches. The address (or storage key) literally spells out the path to its own leaf, so lookup needs no side index.
Canonical. Two nodes holding the same set of key-value pairs build the bit-identical trie and therefore the same root — regardless of the order the pairs were inserted. A plain Merkle tree’s root depends on ordering; the trie’s does not. That determinism is what lets strangers compare a single 32-byte number and know they agree.
Cheap to update. Changing one account touches only the nodes on the path from that leaf to the root — O(log n) re-hashes — not the whole structure. Since nodes are content-addressed by hash, every unchanged node is shared with the previous state for free, which is exactly how a client keeps a history of roots without storing a fresh full copy per block.
Provable. The path from root to leaf is the Merkle proof. You get inclusion proofs for free, and — because the key structure is fixed and canonical — you also get exclusion proofs: you can prove an account does not exist.

In our companion ethmini crate, WorldState cheats and stores the map in a plain HashMap, then sorts by address before hashing to fake canonicality:

pub fn state_root(&self) -> [u8; 32] {
    // HashMap iteration order is randomised, so sort for a canonical hash.
    let mut sorted: Vec<(&Address, &Account)> = self.accounts.iter().collect();
    sorted.sort_by_key(|(addr, _)| **addr);
    // ... serialise the sorted pairs and hash them ...
}

That honest simplification gets you canonicality but throws away cheap updates and proofs — you must re-serialise and re-hash the entire map on every change. The MPT exists precisely to keep the good property (a deterministic root) while also delivering incremental updates and O(log n) proofs. Reading state.rs’s own comment on that trade-off is the fastest way to feel why the real trie earns its complexity.

The encoding stack

The third page covered the three primitives that turn abstract “nodes and paths” into concrete bytes. Get these three straight and the node types stop being mysterious.

RLP (Recursive Length Prefix) is Ethereum’s canonical serialization. It encodes exactly two things — byte strings and lists of items — with a length-prefix scheme that has one and only one valid encoding per value. That one-encoding property is not a nicety; it is required for the root to be canonical. If two encoders could serialize the same node two ways, they’d hash to two roots and consensus would fracture. RLP is deliberately dumber than JSON or Protobuf: no field names, no types, no schema — just “bytes” and “lists of bytes,” which is all a hash function needs.
Nibbles are half-bytes: the 4-bit chunks you get by splitting each byte in two. A key is walked one nibble at a time, and since a nibble has 16 possible values (0–f), the trie branches 16 ways at each step. That is the “hexary” in a hexary Patricia trie, and it is why paths are short: a 32-byte key is 64 nibbles deep at most.
keccak256 is the hash that names every node. Ethereum uses the original Keccak (not the later NIST SHA-3 with its changed padding), and it is the hash of the platform — the same function that derives addresses and event topics. A node’s identity is keccak256(rlp(node)), so the encoding and the hash are welded together: change any nibble of any value and the change avalanches up every node on its path to a completely different root.

key byte  0xA7        →  nibble 'A' (1010) , nibble '7' (0111)
                          ┌── one branch step ──┐  ┌── next step ──┐
state-trie key = keccak256(address) (32 bytes) = 64 nibbles  →  at most 64 levels deep

There is one wrinkle worth re-remembering: leaf and extension nodes carry a path fragment of nibbles, and a fragment can have an odd length. RLP works in whole bytes, so the encoding prepends a hex-prefix (HP) nibble that records (a) parity — is the fragment odd or even? — and (b) a flag distinguishing a leaf from an extension. That single prefix nibble is what lets an odd path survive a byte-oriented encoder without ambiguity.

The three node types

The fourth page is the mechanical heart. The MPT gets its efficiency from exactly three node shapes, each solving a different situation on the path:

Leaf — the end of the road. It stores the remaining nibbles of the key (the part not already consumed on the way down) plus the RLP-encoded value. One leaf per stored entry.
Extension — a shortcut. When a long run of keys all share the same sequence of nibbles, the trie collapses that shared run into a single extension node holding those nibbles and a pointer to the node where they finally diverge. This is the “Patricia” (path-compression) idea: don’t waste a full 16-way branch node on a step where everyone goes the same way.
Branch — a fork. A 17-slot array: sixteen slots (one per nibble 0–f) pointing to child nodes, plus a seventeenth slot for a value that terminates exactly here (i.e., when one key is a prefix of another). Branches are where paths actually diverge.

       [Extension: "a7" ]          shared prefix compressed
              │
        [Branch @ nibble]          keys fork here
         ╱   │        ╲
   slot 1  slot 3   slot f
      │       │        │
   [Leaf]  [Leaf]   [Ext…]         each tail finished off

The mental model: extension = “everyone goes this way for a while,” branch = “here we split sixteen ways,” leaf = “here is your value.” Inserting a key that diverges from an existing leaf mid-path splits that leaf into an extension (for the shared part) leading to a branch (at the divergence) leading to two leaves. Delete the second key and the trie collapses back to exactly the shape it had before — which is another face of canonicality: the structure is a pure function of its contents, never of its history.

The four tries

The fifth page zoomed out from one trie to the four that a block actually commits. Ethereum does not have a single monolithic trie; it has one state trie plus, per block, three more, and their roots live in the block header:

Trie	Key	Value	Root lives in
State	`keccak256(address)`	RLP-encoded account	`stateRoot` (header)
Storage	`keccak256(slot)`	RLP-encoded slot value	each account’s `storageRoot`
Transactions	`rlp(index)`	RLP-encoded transaction	`transactionsRoot` (header)
Receipts	`rlp(index)`	RLP-encoded receipt	`receiptsRoot` (header)

Two structural facts are worth burning in. First, the state trie is a trie of tries. Each account leaf is a four-field object — nonce, balance, codeHash, and storageRoot — and that storageRoot is itself the root of a separate Merkle-Patricia trie holding that one contract’s storage slots. Change a single storage slot in one contract and the effect ripples up: the storage trie’s root changes → the account’s storageRoot field changes → the account leaf’s hash changes → the stateRoot changes. One 32-byte number at the top of the header genuinely commits every slot of every contract.

block header
 ├─ stateRoot ───────▶ state trie
 │                      └─ account leaf { nonce, balance, codeHash, storageRoot }
 │                                                                    │
 │                                                          ▶ storage trie (per contract)
 ├─ transactionsRoot ─▶ transactions trie   (this block only)
 └─ receiptsRoot ─────▶ receipts trie        (this block only)

Second, the state trie persists; the transaction and receipt tries are per-block. The state trie carries the world forward from block to block, sharing unchanged subtrees across roots. The transactions and receipts tries are built fresh for each block from that block’s ordered list — they exist so the header can commit what happened in this block the same way it commits what the world looks like now. The receiptsRoot in particular is what lets a light client trust a log or event it never executed: the receipt is provable against a root in a header it already trusts.

Proofs and light clients

The final page is where the whole construction pays off — and where it reconnects to the throughline’s second half, what does it cost to run one? A Merkle proof against any of these tries is just the ordered list of nodes along the path from the root to the value you care about. To verify it you don’t need the state; you need one thing you already trust — the root — and then you re-hash the supplied nodes back up and check that you land on that root.

verify(value, proof, trustedRoot):
    node ← last node in proof            # the leaf holding `value`
    for each parent up the path:
        assert child_hash appears in parent
        node ← parent
    assert keccak256(rlp(node)) == trustedRoot

The cost is the point. A proof is O(log n) nodes — for a state trie of hundreds of millions of accounts, that is a couple dozen nodes and a handful of kilobytes, not gigabytes. This is what makes a light client possible: a device that holds only block headers (each carrying the four roots) can ask a full node “what is account X’s balance?”, receive an eth_getProof response, and verify the answer itself. It never has to trust the responder — a lying full node cannot fabricate a path of nodes that hashes to the trusted root, because doing so would require finding a keccak256 collision. The trie turns “trust me” into “check it yourself for a few kilobytes,” and that is the same move the whole book keeps making: replace a trusted party with an independently verifiable proof.

Because the trie is canonical and keyed, these proofs also cover the negative case. An exclusion proof shows the path where a key would live and demonstrates it dead-ends — proving an account has never been touched, or that a storage slot is genuinely zero, without downloading the state to confirm the absence.

The takeaway

Hold onto one chain of reasoning and the whole part reconstructs from it: the world is a key-value map → a map needs a canonical, cheaply-updatable, provable commitment, which a plain Merkle tree can’t give → so it lives in a Merkle-Patricia trie, built from RLP (one canonical encoding), nibbles (16-way keyed paths), and keccak256 (node hashes) → assembled from leaf, extension, and branch nodes that compress shared paths and fork at divergences → arranged as four tries (state, storage, transactions, receipts) whose roots sit in the block header → and read back via O(log n) Merkle proofs that let a phone verify any fact against a single trusted root.

That single 32-byte stateRoot is how millions of untrusting machines confirm they are looking at the identical world. With the shape of the state settled, the next part turns to what actually moves it — the transactions and the EVM execution that carry stateₙ to stateₙ₊₁.