Other meanings of Merkle tree
Cryptography
A Merkle tree is a cryptographic hash tree data structure invented by Ralph Merkle in 1979. It is a binary tree where each leaf node contains the hash of a data block, and each internal node contains the hash of its two child nodes. The root hash summarizes the entire set of data, enabling efficient and secure verification of data integrity. Merkle trees form the backbone of Bitcoin's blockchain, certificate transparency, and many distributed systems, allowing any participant to verify that a particular data block belongs to a larger set without revealing the entire set.
A Merkle tree is a complete binary tree of hashes, typically used to verify the integrity of large data sets. Ralph Merkle described the concept in his 1979 patent and later in a 1980 paper on public-key cryptosystems1. The tree is constructed by hashing each data block to produce leaves, then pairwise hashing those hashes up to a single root hash. Changing any data block causes a different root hash, immediately revealing tampering. The data structure allows a Merkle proof: a path of sibling hashes from a leaf to the root, needing only O(log n) hashes to verify that a block belongs to the set. This property makes Merkle trees fundamental to blockchain technology, where they enable light clients to verify transactions without downloading the full chain2.
Merkle trees are most famously used in Bitcoin and other cryptocurrencies to represent all transactions in a block as a single hash3. This allows any node to verify that a transaction is included in a block using only a Merkle proof, without needing the entire block. Beyond blockchain, the Certificate Transparency system uses Merkle trees to provide an audit log of SSL/TLS certificates, enabling anyone to detect misissued certificates4. File systems such as ZFS, Git, and IPFS also employ hash trees (often Merkle trees) to detect data corruption and ensure consistency. The Merkle-Damgård construction for hash functions is conceptually related but distinct, as it chains blocks rather than building a tree.
In a standard Merkle tree, the leaf nodes are cryptographic hashes of data blocks (e.g., SHA-256 outputs). Each internal node is the hash of the concatenation of its two children. The root hash is the final hash after all layers. The tree is typically balanced, with all leaves at the same depth. A Merkle proof for a leaf consists of the leaf's hash and the sibling hashes along the path to the root; the verifier recomputes hashes up the tree and checks if the computed root matches the known root. This requires O(log n) hashes and is secure against tampering as long as the hash function is collision-resistant. Variants include sparse Merkle trees, which efficiently handle large key-value stores by representing non-existent branches with a null hash, and patricia/merkle tries used in Ethereum5.
Ralph Merkle's original 1979 patent (US4309569A) entitled “Apparatus and method for providing security for digital data” predates his well-known 1980 conference paper and describes the tree structure in the context of digital signatures and key distribution1. The term “Merkle tree” was later popularized by the Bitcoin whitepaper, but the concept had already been used in the hash tree form for one-time signature schemes. A subtle point: while the root hash is often called the “Merkle root”, the tree itself is not necessarily binary; it can be generalized to k-ary trees, though binary is most common. In the field of post-quantum cryptography, Merkle trees appear in hash-based signature schemes like XMSS and SPHINCS+, which rely on the security of Merkle trees against quantum adversaries2. Also, the concept of “Merkle orchestration” or “Merkleized” data structures is used in verifiable computation and transparency logs, showing the tree's versatility beyond finance.
Help improve the encyclopedia. Reports go straight to the site manager.