Merklepuun

Merklepuun, commonly called a Merkle tree, is a hash-based data structure that enables efficient and secure verification of large data sets. It organizes data items into a binary tree where each leaf node is the cryptographic hash of a data block, and each internal node is the hash of the concatenation of its two child hashes. The topmost node, the Merkle root, summarizes the entire dataset and can be used to verify inclusion or integrity without accessing every item.

To prove that a specific block belongs to the tree, a Merkle proof provides the hashes of the siblings along the path from the leaf to the root. By recomputing the hashes up to the root, a verifier can confirm membership with only logarithmic data and computation relative to the dataset size, enabling lightweight verification in distributed systems and networks with limited bandwidth.

Merkle trees were introduced by Ralph Merkle in 1979. They gained widespread use with blockchain technologies, where a block header often contains the Merkle root of all transactions in the block. This structure supports efficient SPV (simplified payment verification) clients, forensic analysis, and tamper-evidence of transaction histories.

Variants and related concepts include Merkle proofs for different tree topologies and, in some systems, Merkle Patricia tries or Merkle DAGs. The security of a Merkle tree rests on the collision and preimage resistance of the underlying hash function; common choices include SHA-256 and other modern cryptographic hashes. Merkle trees are used beyond blockchains in distributed file systems, versioned data stores, and content-addressable storage to ensure data integrity and efficient verification.