Merkle Patricia trie

The Merkle Patricia Trie (MPT) is Ethereum's data structure for committing the entire world state — every account's balance, nonce, code hash, and storage — to a single 32-byte root hash that lives in each block header. Change one byte of state anywhere and the root changes, so the header authenticates everything.

It fuses three ideas. A trie (radix tree) is keyed by the hex nibbles of the key, so a lookup simply follows the key path down the tree. 'Patricia' path compression collapses long single-child chains into one extension node, avoiding deep, sparse, wasteful trees. And Merkleization references every node by the keccak256 of its RLP encoding, so the root hash transitively authenticates the whole map. The three node types are branch (a 17-element array: 16 child slots plus a value), extension (a shared key prefix), and leaf (the final key remainder plus value).

Because keys are hashed with keccak256 before insertion, the tree stays roughly balanced and resists adversaries trying to force deep paths. Any node can prove a single key's value with a Merkle branch from leaf to root, which is what the eth_getProof RPC and light clients rely on. Ethereum maintains four such structures: one state trie, one storage trie per contract, plus per-block transactions and receipts tries. The design is slated to be replaced by Verkle tries (using KZG vector commitments) to shrink proofs enough for stateless clients.