Patricia Merkle Tries

A Patricia Merkle trie (also called a Merkle Patricia Trie or MPT) combines a radix tree (compressed prefix tree) with Merkle hashing. Each key-value pair is stored at a leaf determined by the key's path through the tree, and every internal node is hashed to produce a root commitment.

Why Patricia?

Standard Merkle trees pack leaves densely and order them by index. Patricia tries organize leaves by key prefix — the tree structure mirrors the key space itself. This gives three properties that standard Merkle trees don't have:

Structure

A Patricia trie has three node types:

Root
  │
  ├── Branch Node (16 children + value)
  │     hex character "a" through "f"
  │     │
  │     ├── Extension Node (compressed path)
  │     │     "bcd" → skip shared prefix
  │     │     │
  │     │     └── Leaf Node (key, value)
  │     │           ("abcd", account_state)
  │     │
  │     └── Leaf Node
  │           ("a", value)

Hex Encoding (Nibbles)

Keys in a Patricia trie are encoded as hex nibbles (4 bits each). Each nibble selects one of the 16 children of a branch node. This means:

• A 32-byte key (SHA-256 hash) produces 64 nibbles → at most 64 branch nodes in the proof path
• Sibling nodes along the path provide the Merkle proof that a key exists
• The root hash commits to the entire key-value set

Where Terp Network Uses Patricia Tries

The Patricia trie is the native state structure of Ethereum, so any IBC connection to Ethereum or an EVM chain requires Patricia proof verification in the light client.

Comparison: Merkle Tree Variants

Interactive Patricia Trie Visualizer

Patricia trie explorer scaffold — an interactive component that accepts key-value pairs, renders the node structure with branch/extension/leaf node types color-coded, and allows clicking a key to see its proof path through the trie. The root hash updates in real-time as entries are added or removed.

┌──────────────────────────────────────────────┐
│  Patricia Trie Explorer                        │
│                                                │
│  Keys: [a] [ab] [abc] [abcd] [b] [bc]         │
│                                                │
│  ┌── Root ─────────────────────────────────┐   │
│  │  Branch (nibble: 0-f)                   │   │
│  │  ├─ a → Extension("") → Branch           │   │
│  │  │      ├─ (leaf) → "value_a"           │   │
│  │  │      └─ b → Extension("c") → Leaf     │   │
│  │  │             └─ d → "value_abcd"       │   │
│  │  └─ b → Extension("c") → Leaf("value_bc")│   │
│  └──────────────────────────────────────────┘   │
│                                                │
│  Root hash: 0x1a2b...                          │
│  [Add Key] [Verify Proof] [Inspect Node]       │
└──────────────────────────────────────────────┘

Proof Verification

To prove a key-value pair exists in a Patricia trie:

1. Walk the key nibble-by-nibble through branch nodes
2. Collect sibling hashes at each branch node
3. The prover provides the leaf value and the proof path
4. The verifier reconstructs the root hash from leaf to root
5. Compare against the known root

Proof for key "abcd":
  Leaf("abcd", value) → hash
  Branch(nibble d) → combines with leaf hash
  Extension("") → hash of branch
  Branch(nibble a) → hash of extension
  Root hash → compare with stored root

Related Concepts

• Merkle Trees — standard Merkle structure
• Jellyfish Merkle Trees — sparse Merkle variant for account state
• Merkle Mountain Ranges — append-only accumulator
• Hash Functions — the primitives powering all Merkle structures
• IBC Concepts — light client verification using Patricia proofs