The Three Node Types — Leaf, Extension, Branch

The previous page gave us the two encoding primitives the trie is built from: RLP, the byte-serialisation every node is packed with before it is hashed, and nibbles, the 4-bit half-bytes that a key is chopped into so the tree can branch sixteen ways at each step. We also know from Why a Trie, Not a Plain Merkle Tree why Ethereum wants a key-indexed structure: it must map an arbitrary 256-bit key to a value, prove that mapping to someone holding only a root hash, and update the root cheaply when one value changes.

This page assembles the machine that does it. A Merkle-Patricia trie is built from exactly three node types — leaf, extension, and branch — glued together by one small encoding trick, the hex-prefix flag. Once you can name the three shapes and read the flag, the whole structure — and the single 32-byte root that fingerprints it — falls out. This is the page that turns “a trie is a tree keyed by the path” into something you could implement.

The path is the key

Start from the one idea everything else serves: in a trie, the key is not stored in a node — it is the path you walk to reach the value. To look up a key, you convert it to nibbles and follow those nibbles down from the root, one hop per nibble, until you arrive at the value.

   key  0xa711...  →  nibbles  a 7 1 1 ...
                                │ │ │ │
   root ── a ──▶ node ── 7 ──▶ node ── 1 ──▶ node ── 1 ──▶ ... ──▶ value

A pure version of this idea — one node per nibble, each node a 16-way fork — is called a radix trie. It works, but it is wasteful: most Ethereum keys are hashes, so they share almost no prefix and diverge almost immediately, leaving long chains of nodes that each have a single child. The Patricia (“Practical Algorithm To Retrieve Information Coded In Alphanumeric”) optimisation collapses those single-child chains. The three node types are exactly the pieces you need to express both the forks and the collapses.

The branch node — forking one nibble at a time

A branch node is where the path can go sixteen different ways. It is a 17-slot array:

• Slots 0–15 — one per possible next nibble (0x0 through 0xf). Each slot holds either the reference to the child you reach by taking that nibble, or is empty.
• Slot 16 — the value slot. It holds a value if, and only if, a key ends exactly here (its nibbles are fully consumed at this node).

   branch node = [ c0, c1, c2, ..., cf, value ]
                    │   │            │     │
              nibble 0  nibble 1  nibble f   "a key terminates here"

The value slot is the subtle part. Because keys can be prefixes of other keys, a node that is a fork for some keys can also be the end of another key. Slot 16 is where that terminating value lives. Each of the 16 child references is not the child node inline — it is the 32-byte Keccak-256 hash of the (RLP-encoded) child. That is the “Merkle” half of Merkle-Patricia: every parent commits to its children by hash, so the root hash transitively commits to the entire tree.

A branch node is the only node type that forks. Whenever two keys diverge — differ in some nibble — a branch node is what expresses the divergence.

The leaf node — the end of a path

A leaf node ends a path and holds a value. It is a two-element node:

   leaf = [ encoded_path , value ]

• encoded_path — the remaining key nibbles from this point down to the value (hex-prefix encoded; see below).
• value — the payload (for the state trie, the RLP of an account; for a storage trie, the RLP of a slot value).

The leaf’s job is compression at the tail. Once a key has diverged from every other key in the trie, there is no more forking to do — the rest of its nibbles are unique to it. Rather than spend one branch node per remaining nibble (each with a single child), a leaf swallows the whole remaining path in one node and parks the value at the end. A trie with a single key is just one leaf whose path is the entire key.

The extension node — sharing a prefix once

An extension node does for a shared middle what the leaf does for a unique tail: it collapses a run of single-child branch nodes into one node.

Consider two keys that agree on the nibbles a 7 1 and only then diverge. In a raw radix trie that shared run would be three branch nodes in a row, each with exactly one non-empty child — pure overhead. An extension node stores that shared prefix once:

   extension = [ shared_nibbles , next ]

• shared_nibbles — the run of nibbles common to everything below it (hex-prefix encoded).
• next — the hash of the node the shared prefix leads to, which is always a branch node (that is where the paths finally fork).

   without extension            with extension
   (one branch per nibble)      (prefix stored once)

   B─a─▶ B─7─▶ B─1─▶ Branch     Extension["a 7 1"] ─▶ Branch
   (each B has 1 child)                                (the real fork)

An extension node is structurally a two-element node [path, next] — exactly the same shape as a leaf. That is a problem: given two elements, how does a reader know whether it is holding a leaf (whose next is a value) or an extension (whose next is a hash to descend into)? That is the one question the hex-prefix flag answers.

The hex-prefix flag — leaf vs extension, odd vs even

Both leaf and extension nodes are [path, next] pairs, so the trie needs an in-band signal that says which one this is. There is a second problem too: nibbles are half-bytes, but RLP serialises whole bytes. If a path has an odd number of nibbles, you cannot pack it into bytes without either losing a nibble or padding ambiguously.

Hex-prefix (HP) encoding solves both at once. It prepends a single prefix nibble to the path, carrying two bits of information:

It is a…	Nibble count	Prefix nibble	Then…
Extension	even	0x0	one padding nibble 0 follows, then the path
Extension	odd	0x1	the first path nibble rides in the same byte
Leaf	even	0x2	one padding nibble 0 follows, then the path
Leaf	odd	0x3	the first path nibble rides in the same byte

Read the prefix nibble as two flags:

• Bit 1 (value 2) — is this a leaf? 2 or 3 → leaf; 0 or 1 → extension. This is the leaf-vs-extension disambiguation.
• Bit 0 (value 1) — is the nibble count odd? An odd count means the first real nibble can share the prefix’s byte, so no padding is needed. An even count needs a padding 0 nibble to keep the whole thing byte-aligned.

   path nibbles:  a 7 1        (odd, 3 nibbles), it's a LEAF
   HP prefix:     3            (leaf=+2, odd=+1)
   packed bytes:  [3a] [71]    prefix rides with first nibble, no padding

   path nibbles:  a 7 1 5      (even, 4 nibbles), it's an EXTENSION
   HP prefix:     0            (extension=+0, even=+0)
   packed bytes:  [00] [a7] [15]   prefix + padding nibble, then the path

The whole flag is one nibble, and yet it carries exactly the two facts a reader cannot otherwise recover from the bytes: what kind of node am I and did the path have an odd length. This is why the RLP and nibbles page insisted on treating nibbles and bytes as distinct — the HP flag is the seam where the two meet.

A worked example — two keys sharing a prefix

Nothing makes the three nodes concrete like inserting real keys. We’ll use tiny nibble-strings rather than full 64-nibble hashes so the shapes are visible. Insert two key/value pairs whose nibble paths share a prefix:

   key K1 nibbles:  a 7 1 3   →  value V1
   key K2 nibbles:  a 7 f 5   →  value V2

Step 1 — insert K1 alone. One key means one leaf. The whole path is the key:

   root  →  Leaf[ path = "a7 13", value = V1 ]      (HP-encoded, leaf, even length)

Step 2 — insert K2. Now walk K1 and K2 together. They agree on a 7, then diverge: K1’s next nibble is 1, K2’s is f. Three things must appear:

1. an extension node for the shared prefix a 7;
2. a branch node at the point of divergence, using the diverging nibbles (1 and f) as slot indices;
3. two leaf nodes for the two now-unique tails (3 and 5).

   root
    │
    ▼
   Extension[ shared = "a 7" ]
    │
    ▼
   Branch [ slot1 → Leaf["3", V1] , ... , slotf → Leaf["5", V2] , value = (empty) ]
            ▲                                      ▲
        nibble 1 of K1                         nibble f of K2

Read the lookup of K2 (a 7 f 5) against this trie: consume a 7 through the extension, arrive at the branch, take slot f, land on Leaf["5", V2], consume the final 5, read V2. Exactly four nibbles, exactly the key. Notice the branch’s value slot (16) is empty here — neither key ends at the branch, they only pass through it.

Computing the root hash, bottom-up

The root is not stored; it is derived, and it is derived from the leaves upward. Each node is RLP-encoded, then Keccak-256 hashed; a parent embeds its children by hash, so you must know the children’s hashes before you can hash the parent.

   h(Leaf["3", V1]) = keccak256(rlp([HP("3"), V1]))   ── call it  L1
   h(Leaf["5", V2]) = keccak256(rlp([HP("5"), V2]))   ── call it  L2

   branch = [ _, L1, _, _, _, _, _, _, _, _, _, _, _, _, _, L2, "" ]
             0   1                                          f   16
   h(branch) = keccak256(rlp(branch))                 ── call it  B

   extension = [ HP("a7", is_extension), B ]
   ROOT = keccak256(rlp(extension))

Two consequences fall straight out of “parents commit to children by hash”:

• Any change re-hashes only one path. Change V2, and you must recompute L2, then B (because it embeds L2), then the root (because it embeds B) — but not L1, and not any subtree K2 does not pass through. That is the O(depth) incremental update the flat sort-and-hash root of our companion ethmini crate could not offer.
• The root commits to everything. Flip a single byte of V1, and L1 changes, so B changes, so the root changes. Two nodes with identical tries compute the identical 32-byte root; two with any difference compute different roots. That is the whole point of the structure — one hash that distrusting strangers can compare to agree on the entire state of the shared world.

By the numbers — why compression matters at hash scale

Ethereum keys in the state and storage tries are Keccak-256 hashes: 32 bytes, so 64 nibbles deep if stored naively. Because hashes are uniformly random, any two keys almost always diverge within the first few nibbles.

   naive radix trie:  up to 64 single-child levels per key  →  ~64 node reads
   Patricia trie:     shared middle → 1 extension           →  a handful of hops

   Two random 256-bit keys share, on average, well under 2 leading nibbles
   before diverging — so the branching happens near the top, and the long
   unique tails collapse into single leaf nodes.

Extension nodes and leaf tails are what keep a 64-nibble key space from becoming a 64-deep tree. The compression is not a nicety; without it, every state read would chase dozens of single-child nodes, and every proof would carry dozens of useless hashes.

Under the hood — the ≤32-byte inlining rule

There is one more wrinkle real Ethereum adds, and it is worth naming because it surprises people reading a trie for the first time. A parent normally references a child by its 32-byte hash. But if a child’s RLP encoding is shorter than 32 bytes, storing its hash (32 bytes) would be larger than storing the child itself. So the rule is: if a node’s RLP is fewer than 32 bytes, it is embedded inline in its parent rather than by hash. Only nodes whose encoding is 32 bytes or longer are referenced by their Keccak-256 hash.

This is a pure space optimisation and does not change the meaning of the root — the root is still Keccak-256 of the (RLP of the) root node, and it still transitively commits to every value. But it explains why a real trie serialisation contains a mix of raw sub-arrays and 32-byte hash references, rather than hashes all the way down. Our mental model — “parent commits to child by hash” — stays correct; the implementation just skips the indirection when the hash would cost more than the thing it points at.

The architect’s lens

• Why does it exist? The three node types exist to express, in a hash-linked tree, both the two operations a key-value store over 256-bit keys needs — fork where keys differ and compress where they agree — while keeping the tree shallow enough that lookups, updates, and proofs are all O(depth).
• What problem does it solve? They turn “map any key to a value, and commit to the whole map in one hash” into a concrete structure: branch nodes fork, leaf nodes end unique tails, extension nodes fold shared prefixes, and every parent-by-hash link makes the root a fingerprint of the entire state.
• What are the trade-offs? Three node shapes plus the hex-prefix flag is more machinery than a plain Merkle tree, and each lookup may touch a chain of nodes (each a database read). You pay complexity and read amplification to buy cheap incremental roots and compact proofs.
• When should I avoid it? When you don’t need key-indexed proofs or cheap single-value updates — a small, wholly-in-memory map that you re-hash entirely (like our ethmini sort-and-hash root) is simpler and correct. Newer designs also move toward flatter verkle structures precisely to shrink proof size.
• What breaks if I remove it? Remove the branch node and you cannot fork, so you cannot hold two keys that differ. Remove extension/leaf compression and a 64-nibble key space becomes a 64-deep tree, wrecking read and proof cost. Remove the hex-prefix flag and a reader cannot tell a leaf from an extension, or recover an odd-length path — the trie becomes unreadable.

Check your understanding

1. A branch node has 17 slots. What does each of the first 16 slots index, and what specifically lives in slot 16 — when is it non-empty?
2. Leaf and extension nodes are both two-element [path, next] pairs. What are the two things the hex-prefix flag must tell a reader that the raw bytes cannot, and which prefix-nibble bit carries each?
3. In the worked example, inserting the second key a 7 f 5 alongside a 7 1 3 produced an extension node, a branch node, and two leaf nodes. Explain why each of those four nodes had to appear.
4. You change the value of one key deep in a large trie. Which nodes must be re-hashed, and which are untouched? Why does that make the root cheap to update?
5. Why does the Patricia (prefix-compression) optimisation matter especially for Ethereum, given that state and storage keys are Keccak-256 hashes?

Show answers

1. Each of slots 0–15 corresponds to one possible next nibble (0x0–0xf) and holds the reference (normally the Keccak-256 hash) of the child reached by taking that nibble, or is empty. Slot 16 is the value slot: it is non-empty only when a key ends exactly at this node — that is, when some key’s nibbles are fully consumed at the branch. It lets a node be both a fork (for longer keys) and a terminus (for a key that is a prefix of the others).
2. First, leaf vs extension: both are [path, next], so the reader cannot otherwise tell whether next is a value (leaf) or a hash to descend into (extension). Second, odd vs even nibble count: nibbles are half-bytes but RLP stores whole bytes, so an odd-length path needs a signal (and a padding nibble when even) to be packed unambiguously. In the prefix nibble, bit 1 (value 2) encodes leaf-vs-extension; bit 0 (value 1) encodes odd-vs-even length.
3. The two keys agree on a 7, so an extension node stores that shared prefix once instead of two single-child branches. At the third nibble they diverge (1 vs f), which is a fork — only a branch node can express divergence, and it uses 1 and f as slot indices. Below each diverging slot the remaining tail is unique (3 for K1, 5 for K2), so each becomes a leaf node carrying its tail plus its value.
4. Only the nodes on the path from the changed leaf up to the root are re-hashed: the leaf itself, then each ancestor (branch, extension) in turn, because each parent embeds its child by hash, then the root. Every node not on that path — sibling subtrees — is untouched and keeps its old hash. So an update is O(depth) re-hashing rather than re-hashing the whole state, which is what makes committing a new root cheap.
5. Because Keccak-256 keys are 32 bytes (64 nibbles) and uniformly random, a naive radix trie would be up to 64 levels deep with long single-child chains, and random keys diverge within the first nibble or two. Prefix compression folds the (rare) shared middles into extension nodes and the long unique tails into single leaf nodes, keeping the tree shallow — so reads chase a handful of hops instead of dozens, and proofs stay compact.