Merklepuu

Merklepuu, or Merkle tree, is a hash-based data structure that provides a compact summary of a large set of data and enables efficient verification of its contents. It is designed to commit to and verify the integrity of many data blocks using a single value, the Merkle lõ root.

Construction begins with a set of data blocks. Each leaf node stores a cryptographic hash of a data block. Internal nodes store the hash of the concatenation of their two child nodes, and this process continues up to the root, which represents a cryptographic commitment to the entire dataset. In some implementations, the tree is binary; other variants use different branching factors.

Key properties include efficient proofs of membership and exclusion. To prove that a specific block is part of the dataset, a verifier only needs the hashes along the path from the leaf to the root, logarithmic in the number of blocks. This enables lightweight verification without transferring the entire data set. Any alteration to a block changes its leaf hash and propagates to the root, making tampering detectable.

Common applications and uses include blockchain protocols, where a block’s Merkle root commits to all transactions in the block; distributed storage systems and content delivery networks, which rely on Merkle proofs to verify data integrity efficiently; and version control and databases that employ similar hash-based structures to enable fast synchronization and integrity checks. Variants exist, such as Merkle Patricia trees used in Ethereum, which combine Merkle trees with prefix trees for efficient state representations.

Merklepuu was introduced by Ralph Merkle in the 1980s and has since become a foundational concept in modern cryptography and distributed systems.