Merkle tree

A hash tree allows efficient and secure verification of the contents of a large data structure.

Demonstrating that a leaf node is a part of a given binary hash tree requires computing a number of hashes proportional to the logarithm of the number of leaf nodes in the tree.

[3][4] Hash trees can be used to verify any kind of data stored, handled and transferred in and between computers.

They can help ensure that data blocks received from other peers in a peer-to-peer network are received undamaged and unaltered, and even to check that the other peers do not lie and send fake blocks.

[11] The initial Bitcoin implementation of Merkle trees by Satoshi Nakamoto applies the compression step of the hash function to an excessive degree, which is mitigated by using Fast Merkle Trees.

If the hash tree only needs to protect against unintentional damage, unsecured checksums such as CRCs can be used.

[citation needed] The Merkle hash root does not indicate the tree depth, enabling a second-preimage attack in which an attacker creates a document other than the original that has the same Merkle hash root.