A Merkle tree is a data structure in blockchain and cryptography that labels leaf nodes with the cryptographic hash of a data block and non-leaf nodes with the hash of their child nodes. Merkle trees, also known as hash trees, were the invention of Ralph Merkle, who patented this creation in 1979.
Merkle trees are a part of the integral structure of blockchain cryptography and underpin its functionality. The structure is part of the security and verifiability of cryptocurrencies. These enable the efficient transaction checking that makes cryptocurrency possible. Merkle trees are also used to verify any kind of data with hashes, whether in storage or in transit.
The hashes in a Merkle tree allow the contents of the data to be verified quickly.
Hashes map out data of an arbitrary size to a standardized size output which makes it possible to verify large volumes of data quickly. Merkle trees can be a generalization of hash tree, in hash lists, where the number of hashes is proportional to the number of leaves. Or hash trees, where demonstrating a leaf node belongs to a specific binary hash tree requires computation of a quantity of hashes proportional to the logarithm of the quantity of leaf nodes in the entire tree.
Fast Merkle trees were brought into use past the first Merkle tree use in Bitcoin, by Satoshi Nakamoto. The original Merkle tree, with a degree of compression per step was found to be excessive.
On its own a Merkle tree does not measure the depth of the tree which creates a vulnerability to second image attacks where the content of the image are faked with a document with the same Merkle hash root. This vulnerability can be mitigated by use of certificates of transparency. A common use of Merkle trees can be found it the Tiger tree hash which is used in p2p protocols such as Gnutella 1 and 2, or Direct Connect P2P. Applications that use the method of hashing include DC++, Shareaza, Limewire, Bearshare and Phex.
While cryptographic hashing can be performed without Merkle trees it is inefficient and un-scalable.