A comprehensive guide to understanding Ethereum's Merkle Patricia Trie as implemented in reth.
A trie (prefix tree) stores keys by their shared prefixes:
Storing keys: "cat", "car", "card", "dog", "do"
[root]
/ \
c d
/ \
a o
/ / \
t g ∅ ← "do" ends here
/ \ ↑
∅ r "dog"
↑ / \
"cat" ∅ d
↑ \
"car" ∅
↑
"card"
A nibble = 4 bits = half a byte.
1 byte = 8 bits
┌───────────────────────────────┐
│ 1 byte (8 bits) │
│ │
│ 0xa5 = 1010 0101 │
│ ────│──── │
│ │ │ │
│ │ └── low nibble (0x5 = 0101)
│ │ │
│ └────── high nibble (0xa = 1010)
└───────────────────────────────┘
4 bits can represent 2^4 = 16 possible values (0x0 - 0xf):
0000 = 0x0 0100 = 0x4 1000 = 0x8 1100 = 0xc
0001 = 0x1 0101 = 0x5 1001 = 0x9 1101 = 0xd
0010 = 0x2 0110 = 0x6 1010 = 0xa 1110 = 0xe
0011 = 0x3 0111 = 0x7 1011 = 0xb 1111 = 0xf
Ethereum keys are 32 bytes (from keccak256), and each byte has 2 nibbles:
32 bytes × 8 bits/byte = 256 bits
256 bits ÷ 4 bits/nibble = 64 nibbles
In the Merkle Patricia Trie, "key" = the path used to look up data.
| Trie | Key | Value |
|---|---|---|
| Account Trie | keccak256(address) | Account data |
| Storage Trie | keccak256(storage_slot) | Storage value |
| Transaction Trie | rlp(tx_index) | Transaction |
| Receipt Trie | rlp(tx_index) | Receipt |
keccak256 always outputs 32 bytes (256 bits), providing:
- Uniform distribution (balanced trie)
- Fixed-length paths (simplifies traversal)
- Privacy (can't enumerate addresses from trie structure)
Address: 0x742d35Cc6634C0532925a3b844Bc9e7595f... (20 bytes)
│
▼ keccak256()
Key: 0xabc123def456... (32 bytes = 64 nibbles)
│
▼ lookup in trie
Value: Account { nonce, balance, storageRoot, codeHash }
Ethereum's Merkle Patricia Trie uses 3 node types:
┌─────────────────────────────────────────────────────────────────┐
│ 1. BRANCH NODE - 16 children (one per nibble) + value slot │
│ 2. EXTENSION NODE - compressed path + single child │
│ 3. LEAF NODE - remaining path + value │
└─────────────────────────────────────────────────────────────────┘
16 slots, one per nibble:
[Branch Node]
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 1 │ 2 │ 3 │ 4 │ 5 │ 6 │ 7 │ 8 │ 9 │ a │ b │ c │ d │ e │ f │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
│ │ │ │
▼ ▼ ▼ ▼
child child child child
Storing accounts at:
0x1234... → Account A
0x1256... → Account B
0x1289... → Account C
0x5678... → Account D
[Root Branch]
0 1 2 3 4 5 6 7 8 9 a b c d e f
│ │
▼ ▼
[Extension] [Extension]
key: "2" key: "678..."
│ │
▼ ▼
[Branch @ 0x12] [Leaf]
│ │ │ value: Account D
▼ ▼ ▼
[L] [L] [L]
A B C
Only stores revealed paths; the rest are "blinded" hash stubs:
[Root Branch] ◄── revealed
│
┌─────────┼─────────┐
▼ ▼ ▼
Hash(...) [Ext] Hash(...) ◄── blinded (just 32-byte hash)
│ │ │
? ▼ ? ◄── unknown, not in memory
[Branch]
│
┌────┼────┐
▼ ▼ ▼
[Leaf] ... [Leaf] ◄── revealed (we have the actual data)
This saves memory: only load nodes you need for current block's state changes.
nodes map: path (any length) → SparseNode (Branch/Extension/Leaf/Hash)
values map: path (always 64) → actual data (account RLP, storage value)
Values are always at 64 nibbles because they're at the end of the full key path.
For concurrent processing, the trie is split into subtries:
┌─────────────────────┐
│ UPPER SUBTRIE │ ← paths with len < 2 nibbles
│ (1 subtrie) │ Single-threaded
│ │
│ [Root] │
│ │ │
│ [0][1][2]...[f] │ (up to 16 children)
│ │ │ │ │ │
└────┼──┼──┼─────┼────┘
│ │ │ │
▼ ▼ ▼ ▼
┌─────────────────────────┐
│ LOWER SUBTRIES │ ← paths >= 2 nibbles
│ (256 subtries) │ Multi-threaded
│ │
│ [00][01]...[fe][ff] │
└─────────────────────────┘
2 nibbles × 16 values each = 16 × 16 = 256 combinations (0x00 - 0xff)
0─┬─0 → [0x00] 1─┬─0 → [0x10] ... f─┬─0 → [0xf0]
├─1 → [0x01] ├─1 → [0x11] ├─1 → [0xf1]
├─2 → [0x02] ├─2 → [0x12] ├─2 → [0xf2]
│... │... │...
└─f → [0x0f] └─f → [0x1f] └─f → [0xff]
Parallelism. Lower subtries can be processed independently:
Thread 1: subtries 0x00-0x3f (64 subtries)
Thread 2: subtries 0x40-0x7f (64 subtries)
Thread 3: subtries 0x80-0xbf (64 subtries)
Thread 4: subtries 0xc0-0xff (64 subtries)
Then the upper subtrie combines all results sequentially.
| Path | Location |
|---|---|
[] |
upper subtrie (root) |
[a] |
upper subtrie |
[a, b] |
lower subtrie 0xab |
[a, b, c, d...] |
lower subtrie 0xab |
Pruning replaces nodes beyond max_depth with hash stubs to save memory.
Upper Subtrie Lower Subtrie (root: 0x12)
───────────── ─────────────────────────
[Root]
│
Extension
(0x1)
│
▼
Branch ──────────────────────► [Branch 0x12] ◄── subtrie root
(0x1) │
┌┴┐
[Leaf] [Leaf]
0x123 0x124
│ │
val1 val2
Upper Subtrie Lower Subtrie
───────────── ─────────────
[Root]
│
Extension
(0x1)
│
▼
Hash(0xabc...) ◄── "root hash stub" Blind(None) ◄── CLEARED!
(32 bytes only) │
└── nodes: {}
values: {}
If a prune root is a prefix of a subtrie's root path, the entire subtrie is cleared:
Prune root: 0x1
Subtrie root: 0x12 (starts_with 0x1 = true)
→ Entire subtrie replaced with Blind(None)
→ Only the HASH remains in the parent
At max_depth, there can be up to 16^(max_depth+1) pruned roots:
max_depth = 0 → up to 16^1 = 16 pruned roots
max_depth = 1 → up to 16^2 = 256 pruned roots
max_depth = d → up to 16^(d+1) pruned roots
In practice, real tries are sparse, so actual counts are much lower.
| Concept | Value | Why |
|---|---|---|
| Nibble | 4 bits | Half a byte, one hex digit |
| Nibble values | 0-15 (0x0-0xf) | 2^4 = 16 |
| Key length | 64 nibbles | keccak256 = 32 bytes = 64 nibbles |
| Branch children | 16 | One per nibble value |
| Lower subtries | 256 | 16 × 16 (2 nibble prefix) |
| Upper subtrie | 1 | Coordination point for parallelism |