Merklepuuhun

Merklepuu, or Merkle tree, is a cryptographic data structure used to efficiently verify the integrity of large data sets. In a Merkle tree, each leaf node contains a hash of a data block, and each internal node contains the hash of the concatenation of its two child nodes. The root hash summarizes the entire set.

Construction and verification are based on hashing pairs of nodes to form successive parent levels until a single root remains. To prove that a particular block is part of the tree, a Merkle proof provides the sibling hashes along the path from the leaf to the root. By hashing the block with these siblings, one can reproduce the root and verify membership without accessing all data.

Common uses include efficient data verification in distributed systems and blockchains. In Bitcoin, for example, the Merkle root is included in the block header, and transactions within a block are hashed in pairs to form the root. Merkle proofs allow light clients to verify specific transactions without downloading every block.

Merkle trees offer tamper-evidence and logarithmic verification time. They are well suited for batching updates, as changes propagate only along the path to the root. However, they do not inherently provide proofs of non-membership and may require additional structures for such queries.

Historically, the concept was introduced by Ralph Merkle in 1979 and has since become a foundational technique in cryptography and distributed systems, enabling scalable and secure data verification across various protocols.