Ethereum Merkle Patricia Tries Explained

13 Oct 2026 cryptocurrencycryptography

An Ethereum Merkle Patricia trie (MPT) is a key-value tree whose paths are derived from keys and whose root hash commits to every value below it. Ethereum uses these tries to organize account state and contract storage, while allowing another node to verify a value without storing the whole tree.

The problem it solves

Ethereum needs a compact answer to two related questions:

• What was the state at a particular block?
• How can a node prove that a claimed account balance or storage value belongs to that state?

A plain database can answer the first question, but its contents do not naturally produce a short, independently checkable commitment. Sending the entire database to a verifier would be expensive, too.

An MPT addresses both problems. Ethereum puts one root hash in a block header. That small value represents the complete state at that block. Given the root and a path through the tree, a verifier can check a value by hashing only the nodes included in a proof.

The root hash is a commitment, not the state itself. It lets a verifier detect changes to the state, but the verifier still needs the relevant proof nodes to recover a particular value.

Keys become paths

Ethereum’s state trie is a key-value map. Its keys are not used directly as ordinary strings. For an account, Ethereum computes the Keccak-256 hash of the account address. That 256-bit result becomes the trie path.

The path is read as nibbles, where a nibble is a four-bit value from 0 through 15. A 256-bit hash therefore gives a path of 64 nibbles. Hashing the address spreads accounts throughout the tree instead of grouping them by their original address prefixes.

Each account value contains four fields, encoded with Ethereum’s Recursive Length Prefix (RLP) encoding, a compact binary encoding for nested byte strings and lists:

An externally owned account still has an account record; its storage trie is empty and its code hash represents no contract code.

A contract’s persistent storage is a second trie beneath that account. A storage slot is represented by its 32-byte slot key, and Ethereum hashes that key with Keccak-256 before using the result as the storage-trie path. The value at that path is the slot’s 32-byte value, with zero-valued slots generally omitted rather than stored explicitly.

This gives Ethereum a two-step lookup:

1. Use keccak256(address) to find the account in the global state trie.
2. Read its storageRoot, then use keccak256(slot) to find a value in that contract’s storage trie.

The state root in the block header commits to the global trie, which in turn commits to each account’s storageRoot.

How the trie stores paths

An MPT combines three ideas:

• A Merkle tree stores hashes so a parent commits to its children.
• A Patricia trie follows key symbols and compresses paths where there is no branching.
• A radix-16 trie has up to 16 children at each branching point, one for each nibble.

Ethereum’s nodes have three relevant shapes:

• A branch node has 16 child positions, one for each nibble, plus a value position. It is used when paths diverge.
• An extension node stores a shared sequence of nibbles and points to the next node. It compresses a path that has no divergence.
• A leaf node stores the remaining path and the value associated with the complete key.

The path in an extension or leaf is compactly encoded with a hex-prefix format. That format records both whether the path is a leaf or extension and whether it contains an odd or even number of nibbles. The detail matters because the encoded bytes must be reproduced exactly when checking hashes.

Every node is RLP-encoded. A parent refers to a child either by embedding the child’s encoding when it is short enough, or by storing the Keccak-256 hash of the child encoding. In the usual case, the reference is a hash. Consequently, changing a value changes its leaf, then the hashes of its ancestors, and finally the root hash.

Ethereum implementations commonly update these structures with copy-on-write behavior: modified nodes are created along the changed path, while untouched subtrees can be reused. This produces a new root for the new state without rewriting every account.

What a proof contains

Suppose a light client wants to verify an account balance. It receives:

• the state root from a trusted block header,
• the account address and claimed account value, and
• the encoded nodes along the path for keccak256(address).

The verifier starts at the leaf or branch relevant to that key. It checks each node’s RLP encoding, follows the nibble path, and hashes each node exactly as Ethereum does. It then works upward, checking that each parent contains the expected child reference. If the calculation ends at the supplied state root, the account value is proven to belong to that committed state.

To verify a contract storage slot, the verifier performs the same process twice: first for the account in the state trie, then for the slot in the storage trie whose root was found in the account record.

Proofs can also prove non-existence. For example, the path may reach an empty branch position, or a leaf whose remaining path does not match the requested key. The verifier checks that this terminating structure is itself connected to the trusted root, showing that the key is absent rather than merely missing from the proof.

A verifier therefore does not need the entire trie. It needs the root commitment, the query key, and the small set of nodes on the relevant path. A full node can generate those nodes; a light client or other constrained system can validate them independently. The proof is not trusted because it came from a particular server—the hashes and path rules make an incorrect value fail to reconstruct the known root.

When an error mentions a “state root mismatch,” “invalid account proof,” or “missing trie node,” it is usually describing this machinery: either the supplied nodes do not lead to the expected root, or the local node lacks a trie node needed to construct or verify the path.