Merkle Tree

A Merkle tree, also called a hash tree, is a tree data structure in which every leaf node stores the Cryptographic Hash Function of a data block and every non-leaf node stores the hash of the concatenation of its child hashes. The hash at the top is the Merkle root, a single fixed-size value that summarizes the entire dataset. The construction was introduced by Ralph Merkle in 1979 in his doctoral work on public-key cryptography and digital signatures and was described in U.S. Patent 4,309,569. Its key practical property is efficient verification: to prove that a particular leaf is part of a dataset committed to by a given root, a verifier only needs the sibling hashes along the path from that leaf to the root — a Merkle proof of size logarithmic in the number of leaves. Any change to any leaf changes the root, so the root acts as a tamper-evident commitment. Merkle trees are pervasive in modern systems. Bitcoin and other blockchains use them to commit to the set of transactions in a block. Certificate Transparency logs use them so that auditors can verify that a certificate was included without downloading the entire log. Peer-to-peer protocols such as BitTorrent and IPFS use Merkle structures (often generalized to a Merkle DAG where nodes can have multiple parents and arbitrary fan-out) to verify blocks as they arrive from untrusted peers, and Content-Addressable Storage systems use the root hash as the address of the entire structure.