Overview

“An Introduction to Merkle Patricia Trie” is a LambdaClass blog primer (LambdaClass, June 2025) explaining the Merkle Patricia Trie (MPT), the authenticated data structure Ethereum uses to store and verify account state. The article decomposes the MPT into its three constituent ideas: a trie (prefix tree) for key-value lookup, the Patricia optimization for path compression, and Merkle-style cryptographic hashing for tamper evidence. It walks through the concrete node types, the role of the StateRoot as a fingerprint of the entire state, and a step-by-step method for constructing and verifying inclusion proofs.

Key points

• An MPT fuses three structures: a trie stores key-value pairs indexed by shared key prefixes; Patricia compresses chains of single-child nodes into one node with a shared prefix; and Merkle hashing (Keccak-256) hashes every node so any change propagates upward.
• Three node types make up the tree: a branch node is a 17-slot array (one child pointer per hex digit 0 to F, plus a value slot), an extension node holds a shared key prefix and a pointer to the next node, and a leaf node holds the remaining key fragment and its value.
• The StateRoot, the root hash of the trie, is a single cryptographic summary of all accounts; nodes reach consensus by comparing StateRoots after executing a block rather than comparing full state.
• The trie is persistent and versionable: old nodes are never deleted, so Ethereum can revert to a prior state simply by pointing at an earlier root hash.
• MPT proofs are verified top-down: hash the first node and confirm it equals the StateRoot, decode each RLP-encoded node to follow the child pointer selected by the next digit of the target key, confirm each node’s hash matches the parent pointer, and check the final leaf’s remaining key and value.

Relevance to Truestamp

The MPT is a different Merkle variant (a keyed, path-compressed, Keccak-hashed authenticated map) than the RFC 6962 append-only tree Truestamp uses, but both rely on the same core principle: a single root hash commits to a large data set and supports compact inclusion proofs that a verifier can check against that root. Studying the MPT clarifies how root-hash comparison substitutes for full-state comparison, the same substitution that lets Truestamp prove an item’s presence in a committed Merkle tree.

Citations

1. An Introduction to Merkle Patricia Trie. LambdaClass blog, June 2025.