Merkle Patricia Trie

What Is a Merkle Patricia Trie?

A Merkle Patricia trie (MPT), sometimes called a modified Merkle Patricia trie, is a cryptographically authenticated key-value data structure. It merges three computer science concepts into one:

• Merkle tree verification: every node is referenced by its Keccak-256 hash, so changing any value propagates hash changes all the way up to a single root hash
• Patricia trie (radix trie) compression: common key prefixes are collapsed into shared paths, reducing depth and storage cost for sparse keyspaces
• Key-value storage: the MPT maps arbitrary keys to arbitrary values, functioning as a verifiable dictionary rather than a simple ordered list

Ethereum adopted the MPT as its core state storage mechanism because it needed a data structure that could store every account balance, contract state, and transaction record while allowing any participant to verify the correctness of any claim about that state. Unlike Bitcoin's UTXO model, Ethereum's account model requires maintaining a global state database that changes with every transaction. The MPT makes this possible while preserving cryptographic integrity.

How It Works

The MPT organizes data using four node types, with keys traversed one nibble (4 bits, or one hex character) at a time. A 32-byte key becomes 64 nibbles, and each nibble selects one of 16 possible branches at each level.

Node Types

The Ethereum Yellow Paper defines four node types:

• Branch node: a 17-element array where the first 16 slots correspond to hex nibbles 0 through F, each pointing to a child node. The 17th slot holds a value if a key terminates at this branch.
• Leaf node: a 2-element array containing an encoded path (the remaining key nibbles) and the stored value. Leaf nodes mark the end of a key path.
• Extension node: a 2-element array containing a shared path prefix and a pointer to the next node. When multiple keys share a common prefix, the extension node compresses that shared segment into a single hop instead of traversing one nibble at a time.
• Null node: an empty string representing the absence of data. Unused slots in a branch node point to null.

Hex-Prefix Encoding

Leaf and extension nodes are both 2-element arrays, so the MPT uses hex-prefix (HP) encoding to distinguish them. The first nibble of the encoded path acts as a flag:

Bit 1 is the termination flag (0 for extension, 1 for leaf). Bit 0 is the oddness flag. For even-length paths, a padding nibble follows the flag so the data aligns to byte boundaries.

RLP Serialization

All trie nodes are serialized using Recursive Length Prefix (RLP) encoding before storage. RLP is a binary encoding scheme for nested arrays of bytes. Nodes are referenced by keccak256(rlp(node)) when the RLP-encoded output is 32 bytes or longer. Shorter nodes are stored inline within their parent, reducing storage overhead:

// Simplified MPT node referencing
if (rlpEncode(node).length >= 32) {
  reference = keccak256(rlpEncode(node));  // store in DB, reference by hash
} else {
  reference = rlpEncode(node);             // embed inline in parent
}

Path Construction

Keys are constructed differently depending on which trie they belong to:

• State trie: keccak256(ethereumAddress) hashes each 20-byte address to a 32-byte key, producing a uniform distribution across the trie
• Storage trie: keccak256(storageSlotPosition) hashes each contract storage slot to a 32-byte key
• Transaction and receipts tries: rlp(transactionIndex) uses the transaction index directly without hashing

Ethereum's Trie Architecture

Every Ethereum block header contains three root hashes, each committing to a complete trie:

State Trie (World State)

The state trie is a single global structure mapping every Ethereum address to its account state. Each account value is an RLP-encoded object with four fields:

• nonce: transaction count for externally owned accounts, or contract creation count for contracts
• balance: the amount of wei held by the account
• storageRoot: root hash of the account's own storage trie (for smart contracts)
• codeHash: Keccak-256 hash of the account's EVM bytecode (empty for externally owned accounts)

The state trie is mutable: it updates after every transaction execution. The resulting root hash (stateRoot) in the block header commits to the entire world state at that point in time.

Storage Trie

Each smart contract has its own storage trie, referenced by the storageRoot field in the account object. It maps 256-bit storage slot keys to 256-bit values representing the contract's persistent variables. This nested structure means the state trie root indirectly commits to every variable in every contract on the network.

Transaction and Receipts Tries

Each block also includes a transaction trie (mapping transaction indices to transaction data) and a receipts trie (mapping indices to execution results, including status codes and event logs). Both are immutable once the block is finalized, and their root hashes (transactionsRoot and receiptsRoot) appear in the block header.

Proof Verification

One of the MPT's most valuable properties is efficient proof generation. A Merkle proof in the MPT context works as follows:

1. A full node provides the target key, the claimed value, the state root hash, and every node along the path from root to the target leaf
2. The verifier (such as a light client) reconstructs the path by hashing each provided node and checking that child references match
3. If the final computed root hash matches the trusted state root from a block header, the proof is valid

Non-inclusion proofs are also possible: a prover can demonstrate that a key does not exist by showing that the path terminates or diverges before reaching the expected leaf. This allows light clients to verify account balances and contract states without downloading the full state.

Use Cases

• Light client verification: mobile wallets and lightweight clients can verify account balances by requesting a Merkle proof against a trusted block header, rather than downloading the entire state
• Cross-chain bridges: protocols can verify Ethereum state on other blockchains by validating MPT proofs against relayed block headers
• Storage proofs: decentralized applications can prove the value of specific contract storage slots to external systems, enabling trustless oracles and cross-chain data reads
• Block validation: every full node validates blocks by re-executing transactions and checking that the resulting state root matches the block header's stateRoot field
• Historical state queries: archive nodes can reconstruct the state at any historical block by loading the state root from that block's header

Risks and Considerations

State Bloat

The most significant challenge with Ethereum's MPT is monotonic state growth. Every new account, contract, and storage slot adds data permanently. As of 2025, Ethereum has over 335 million cumulative unique addresses, and the execution client database requires approximately 0.9 to 1.3 TB of storage. This grows at roughly 7 to 8 GB per week.

The cost of running a full node has risen to $2,000 to $10,000 in hardware, threatening decentralization as fewer participants can afford to validate the network independently. There is no built-in mechanism to remove abandoned accounts or expired contract state.

Proof Size

Because branch nodes have 16 children, a Merkle proof must include up to 15 sibling hashes per level. For the MPT's maximum depth of 64 nibbles, proofs can become large. A witness covering 1,000 state items in the current MPT requires approximately 3.5 MB, making stateless validation impractical.

Verkle Trees: The Planned Replacement

Verkle trees (from "vector commitment" + "Merkle") are designed to replace the MPT on Ethereum. Instead of hash-based child references, Verkle trees use polynomial commitments where a proof of any single element is constant-size regardless of the tree's width. This allows a branching factor of 256 children per node while keeping proofs small.

The impact is dramatic: the same 1,000-item witness that requires approximately 3.5 MB in the MPT shrinks to roughly 150 KB with Verkle trees. This 23x reduction enables stateless validation, where nodes can verify blocks without storing the full state locally.

Ethereum's Verkle tree implementation uses Pedersen commitments with Inner Product Arguments (IPA) over the Bandersnatch elliptic curve. The specification is defined in EIP-6800, and the transition is targeted for the Hegota upgrade. The migration requires touching every existing account and contract in the state.

Comparison with Other Approaches

Bitcoin takes a fundamentally different approach to state management. Rather than maintaining a global state trie, Bitcoin tracks unspent transaction outputs (UTXOs) and uses Merkle trees only for transaction inclusion proofs within blocks. This avoids the state bloat problem but limits programmability. Layer 2 protocols like Spark operate off-chain and avoid the state overhead of maintaining a global trie entirely, enabling faster and cheaper transactions while anchoring security to Bitcoin's base layer.

This glossary entry is for informational purposes only and does not constitute financial or investment advice. Always do your own research before using any protocol or technology.