Why a Trie, Not a Plain Merkle Tree

The overview left us holding a single 32-byte state root — a cryptographic commitment to the entire world: every account’s balance, nonce, storage, and code. The root’s job is to let untrusting strangers compare 32 bytes instead of shipping each other a multi-gigabyte database, and to make “did the state change?” a question you answer by comparing two hashes.

That much a Bitcoin-style Merkle tree already gives us. So the obvious first question — the one this page exists to answer — is: why doesn’t Ethereum just build a plain Merkle tree over its accounts and call it done? The answer is that Ethereum’s state is mutable and keyed, and a plain Merkle tree is neither. It commits to a fixed, ordered list; Ethereum needs to commit to a changing map. Closing that gap is what forces the structure of the next few pages: a Merkle tree fused with a radix trie.

What a plain Merkle tree actually gives you

Recall the construction from first principles. Take an ordered list of items [L0, L1, L2, L3]. Hash each leaf. Then hash pairs together, level by level, until one hash remains — the root.

                 root = H( H01 ‖ H23 )
                 /                    \
        H01 = H(H0‖H1)          H23 = H(H2‖H3)
         /        \               /        \
     H0=H(L0)  H1=H(L1)      H2=H(L2)   H3=H(L3)
        │         │              │          │
        L0        L1             L2         L3

This buys exactly one thing, and it buys it beautifully: membership proofs over a fixed ordered list. To convince someone holding only the root that L2 is in the tree, you hand them L2 plus the sibling hashes along L2’s path — here H3 and H01. They recompute H2 = H(L2), then H23 = H(H2‖H3), then H(H01‖H23), and check it equals the root. That is O(log n) hashes to prove one item out of n, without revealing the other n−1. Bitcoin uses precisely this to let a light wallet verify “my transaction is in this block” from an 80-byte header and a short proof.

Hold onto the shape of what that proof answers, because it is narrower than it first looks. A Merkle proof answers “is this leaf, at this position, in this list?” It does not answer “what is the value associated with key X?” — because in a plain Merkle tree there is no key. There is only position.

Failure mode 1 — there is no key

Ethereum’s state is a map: address → account. The two operations that define a map are:

Look up the account for address X.
Prove to a stranger what X’s value is, given only the root.

Neither is a natural operation on a plain Merkle tree. The tree knows leaf positions (L0, L1, …), not keys. To find address X you would have to know which slot X was placed in — which means keeping a separate index (address → slot number) entirely outside the tree. And that index is not covered by the root, so it is exactly the thing an adversary can lie about: “oh, X is at slot 5,” they say, and hand you a perfectly valid membership proof for slot 5, which holds someone else’s account.

   plain Merkle tree over accounts:
     slot 0 → Account(0xAAAA…, bal 10)
     slot 1 → Account(0xF00D…, bal  7)      "prove me 0xF00D's balance"
     slot 2 → Account(0x1234…, bal  0)         → prover must first tell you
     ...                                          WHICH slot — and you cannot
                                                  check that claim against the root.

A commitment you cannot query by key is close to useless for state. We do not want to prove “some leaf exists at position 5”; we want to prove “the account for address 0xF00D… has balance 7, and there is exactly one such account.” A plain Merkle tree cannot bind a key to a leaf, so it cannot make that statement.

Failure mode 2 — insertion order changes the root

The second failure is subtler and, for a consensus system, fatal.

A plain Merkle tree is built over a list, and a list has an order. Insert a new account, and you must decide where it goes. Append it? Then the tree’s shape — and therefore its root — depends on the history of insertions, not on the contents of the state. Two nodes that ended up with the identical set of accounts, reached by different transaction orderings, would build differently shaped trees and compute different roots.

   Node A adds accounts in order:  X, Y, Z        Node B adds:  Z, X, Y
     [X, Y, Z]  → root_A                             [Z, X, Y] → root_B
                                        root_A ≠ root_B
                    ...yet both hold the SAME three accounts.

That breaks the one property the root exists for. The whole point of the state root is that it is a function of the state and nothing else — identical worlds must yield identical roots, on every machine, forever. A commitment that depends on insertion order is not a commitment to the state; it is a commitment to a journal of how you got there, which two honest nodes will never share.

You can patch this by sorting the list before you build the tree — and that is exactly what our companion chain ethmini does in its state_root: it sorts accounts by address, then hashes. That restores determinism. But sorting exposes the third weakness, and it is the one that finally forces the trie.

Under the hood — why sort-and-hash still isn’t enough

The ethmini teaching chain is honest about being a simplification. Its root is a flat hash over the sorted accounts:

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. Deterministic in, deterministic out.
    let bytes = serde_json::to_vec(&sorted).expect("serialisable");
    Sha256::digest(&bytes).into()
}

Sorting fixes determinism — same accounts, same bytes, same root, regardless of insertion order. But it leaves two costs that grow with the state:

Every write re-hashes the whole world. Change one balance and you must re-serialise and re-hash all accounts — O(n) work per transaction. On a chain with hundreds of millions of accounts, that is not a rounding error; it is the difference between a chain that keeps up and one that doesn’t.
You still cannot prove one account cheaply. A flat hash proves nothing short of revealing the entire state. There is no O(log n) “here’s your account and its path” proof, because there is no tree of intermediate hashes to walk.

So sort-and-hash gives us determinism but throws away the two things a Merkle tree was good at: cheap incremental updates and compact proofs. We want all three at once. That is the tension the trie resolves.

The radix trie idea — structure from the key itself

Here is the move. Instead of choosing where a key goes (append? sort?), let the key choose its own place by walking the tree according to the digits of the key. This is a radix trie (and its space-optimised variant, a Patricia trie).

Think of a key — an address, say 0xf00d… — as a string of digits. Starting at the root, you follow the branch labelled by the first digit, then the branch labelled by the second digit, and so on, until the path spells out the whole key. The value lives at the end of that path.

   key "f00d..."  read digit by digit:

        root
         └─ f ─┐
               └─ 0 ─┐
                     └─ 0 ─┐
                           └─ d ─ ... ─▶  Account(0xf00d…)

   key "f012..."  shares the prefix "f0", then diverges at the 3rd digit:

        root
         └─ f ─ 0 ─┬─ 0 ─ d ─▶ Account(0xf00d…)
                   └─ 1 ─ 2 ─▶ Account(0xf012…)

Two consequences fall out immediately, and they are exactly the two failures cured:

It is keyed by construction. “Look up X” is the traversal: read X’s digits, walk the path, arrive at the value. There is no external index to lie about — the position of a leaf is its key. Proving X’s value means proving the path spelled by X’s digits, which no adversary can redirect to a different account.
It is canonical, independent of insertion order. A key’s path is determined by the key, not by when it was inserted. Add X, Y, Z in any order and each lands in the one place its digits dictate. Two nodes with the same set of keys build the same-shaped trie — so, once we make it Merkle (next section), the same root. Determinism comes for free from the structure, not from a sorting step bolted on afterward.

The “Patricia” refinement — which the node-types page develops — collapses the long single-child chains you can see above (f → 0 → 0 → d …) into one compressed node, so the trie doesn’t waste a level per digit on sparse keys. But the core idea is already here: the key path is the address in the tree.

The synthesis — a Merkle-Patricia trie

Now fuse the two ideas. Take the radix trie — keyed, canonical structure — and make it Merkle by having each node commit to its children by their hashes, so that a single root hash covers the whole structure exactly as in a plain Merkle tree.

   radix/Patricia trie   →  keyed lookup + canonical structure
                              (fixes: no key, order-dependence)
   +  Merkle hashing      →  hash-linked nodes, one root, O(log n) proofs
                              (keeps: 32-byte commitment, membership proofs)
   ─────────────────────────────────────────────────────────────
   =  Merkle-Patricia Trie (MPT)   →  all three properties at once

Each of the three failure modes maps to exactly one ingredient:

Requirement	Plain Merkle tree	Radix trie	Merkle-Patricia trie
Keyed lookup / keyed proof	no	yes	yes
Deterministic under insertions	no (needs sorting)	yes	yes
`O(log n)` incremental root update	no (`O(n)` re-hash)	—	yes
Compact membership/exclusion proof from root	yes	—	yes
Single 32-byte root commitment	yes	—	yes

The radix trie supplies the two columns a plain Merkle tree missed; the Merkle hashing keeps the two a plain Merkle tree already had; and because a change now touches only the nodes along one key’s path, updating the root costs O(log n) re-hashes instead of re-hashing the world. That is the whole design in one sentence: a Merkle-Patricia trie marries a radix trie’s keyed, canonical structure with a Merkle tree’s hash-linked proofs.

Everything remaining in this Part is how Ethereum builds that object concretely: the encoding of keys and values, the three node types that make it efficient, the four separate tries Ethereum actually maintains, and the proofs this structure hands to light clients.

Take a state of n ≈ 3 × 10⁸ accounts and ask what it costs to (a) update the root after one write, and (b) prove one account to a stranger holding only the root.

                        update after 1 write     prove 1 account
  flat sort-and-hash    ~n  hashes  (≈3e8)        must reveal all n leaves
  plain Merkle tree     ~n  (rebuild on insert)   log₂ n ≈ 28 sibling hashes*
  Merkle-Patricia trie  ~depth ≈ 8–9 nodes        ~depth ≈ 8–9 nodes on the path

  * but a plain Merkle tree can't answer "prove account X" at all —
    only "prove the leaf at position i" — so the 28 hashes prove the
    wrong question.

The trie’s depth is set by the key length in nibbles (a 32-byte key is 64 nibbles) and the branching factor (16), so a well-filled trie is only a handful of levels deep. A single write re-hashes just that path — single-digit node count — instead of hundreds of millions. That gap, O(n) vs O(depth), is why real Ethereum can advance its state root once per block without re-hashing the planet.

The state root is consensus-critical: every node must compute it identically, or nodes that disagree by a single byte reject each other’s blocks and split the network. On 11 November 2020, the widely-used Ethereum client Geth processed a particular mainnet block differently from other clients because of a subtle bug, producing a different state root and causing an unintended chain split that took hours to resolve. Nobody stole funds — and that is what makes the lesson sharp. The danger wasn’t theft; it was disagreement. It is precisely because the root must be a deterministic function of state — not of insertion order, not of a client’s private index — that Ethereum commits state through a canonical structure like the Merkle-Patricia trie, where the same accounts always produce the same root by construction.

The architect’s lens

Why does it exist? Because Ethereum’s state is a mutable, keyed map, not a fixed list — and a plain Merkle tree commits only to a fixed, ordered list. The MPT exists to commit to a changing map by key while keeping a single hash root.
What problem does it solve? Three at once: keyed lookup and keyed proofs (prove “account X = value” from the root), determinism (identical states → identical roots regardless of insertion order), and cheap updates (re-hash only one key’s path, not the whole world).
What are the trade-offs? It is far more complex than a flat hash or a plain Merkle tree — multiple node types, a nibble encoding, and per-node hashing — and every state read/write touches several hashed nodes, which is why real clients cache aggressively and why state access dominates node I/O.
When should I avoid it? When your data is a fixed, ordered list you only need membership proofs over (like a block’s transaction set) — a plain Merkle tree is simpler and sufficient. And at teaching scale, ethmini’s sort-and-hash is the honest, readable choice; the trie earns its complexity only when n and proofs are large.
What breaks if I remove it? You lose keyed proofs (light clients can no longer verify one account from the root), cheap incremental roots (every write becomes O(n)), or determinism (if you drop the canonical structure) — and a non-deterministic root, as the 2020 Geth incident shows, forks the chain.

Check your understanding

A plain Merkle tree gives you exactly one guarantee about its leaves. State it precisely, and explain why that guarantee is not the same as “look up the value for key X.”
Describe the insertion-order failure mode concretely: two honest nodes end up with the identical set of accounts but different roots. How does it happen, and why is it fatal for consensus?
Sorting the accounts before hashing (as ethmini does) fixes determinism. What two problems does it still leave unsolved, and why does each one matter as the state grows?
Explain how a radix trie makes lookup keyed and structure canonical without any external index or sorting step. What plays the role of “where does this key go?”
Give the one-sentence synthesis: which property does the radix trie half of a Merkle-Patricia trie contribute, and which does the Merkle half contribute?

Show answers

A plain Merkle tree proves membership of a leaf at a given position in a fixed ordered list — “leaf L sits at position i, and this list’s root is R.” It is a statement about position, not key. “Look up value for key X” needs a binding from the key to a leaf, which the tree doesn’t have; you’d need an external key→position index, and that index isn’t covered by the root, so an adversary can point you at the wrong (but validly-proven) leaf.
A plain Merkle tree is built over an ordered list, so inserting accounts in different orders (X,Y,Z vs Z,X,Y) produces differently shaped trees and therefore different roots — even though the contents are identical. It’s fatal because the root’s entire purpose is to be a function of the state; distrusting nodes compare roots to agree, and two honest nodes with the same world would compute different roots and reject each other’s blocks.
(a) Every write re-hashes the whole world — O(n) work per transaction, because a flat hash has no intermediate structure to update incrementally; catastrophic once n is hundreds of millions. (b) You still can’t prove one account cheaply — a flat hash proves nothing short of revealing the entire state, so there’s no O(log n) per-account proof for light clients. Sorting buys determinism but neither of these.
In a radix trie, a key is read digit by digit, and each digit selects the next branch, so the path through the tree literally spells the key. The key’s own digits answer “where does this key go?” — no external index (nothing to lie about) and no sorting step (the path depends on the key, not on insertion time). Lookup is the traversal, and identical key sets build identical-shaped tries.
The radix-trie half contributes keyed, canonical structure (lookup and proofs by key; identical states → identical shape regardless of insertion order); the Merkle half contributes hash-linked nodes with a single root and O(log n) proofs. Together: a keyed, deterministic, cheaply-updatable, provable commitment to a mutable map.