Merklepuut

Merklepuut is the Estonian term for the Merkle tree, a cryptographic data structure used to efficiently verify the contents of large data sets. It is named after Ralph C. Merkle, who introduced the concept in the 1980s. A Merklepuut provides a compact summary of many data blocks and enables proofs of inclusion that require only a small amount of information.

A Merklepuut is organized as a binary tree where the leaves contain the hashes of individual data blocks. Each internal node stores the hash of the concatenation of its two child node hashes, and this process continues up to the root, which holds a single hash that represents the entire dataset. If a level has an odd number of nodes, the last node is typically duplicated to maintain the binary structure. The root hash serves as a compact fingerprint of all leaves.

Verification and integrity are the main strengths of a Merklepuut. To prove that a particular block is part of the tree, one provides the hashes of the sibling nodes along the path from that leaf to the root. With this Merkle proof, a verifier can recompute the root hash and confirm inclusion without accessing every block. This property also helps detect tampering, since any change to a leaf alters the root hash.

Applications of Merklepuud include blockchains (where the Merkle root is stored in the block header and all transactions in a block can be verified with proofs), distributed storage, and content-addressable systems. Git and related version-control technologies use a related idea (Merkle DAG) to track changes efficiently. Overall, Merklepuud enable scalable, tamper-evident verification in distributed environments.