Merkle tree - Wikipedia
Wikipedia's reference article on Merkle (hash) trees: leaf and parent hashing, the root hash, logarithmic inclusion verification, Ralph Merkle's 1979 patent, the second-preimage attack, and uses in Bitcoin, Git, ZFS, and Certificate Transparency.
Overview
The Wikipedia article on the Merkle tree (also called a hash tree) describes a cryptographic data structure in which every leaf node holds the hash of a data block and every non-leaf node holds the hash of the concatenation of its child nodes. Hashing proceeds upward through the tree until it produces a single root hash (top hash) that acts as a compact commitment to the entire dataset. The article covers the structure’s mechanics, its history, its known security weaknesses, and its widespread use across blockchains, distributed version control, file systems, and peer-to-peer networks.
Key points
- Structure: leaves are hashes of data blocks; each parent is the hash of its children’s hashes; a single root hash summarizes the whole tree.
- Efficient verification: proving a leaf belongs to the tree requires only a number of hashes proportional to the logarithm of the leaf count, rather than rehashing all data.
- History: Ralph Merkle invented the concept and patented it in 1979 (U.S. Patent 4,309,569), building on his digital-signature research.
- Second-preimage attack: because the plain root hash does not encode tree depth or node role, an attacker can construct a different structure yielding the same root; Certificate Transparency mitigates this by prefixing 0x00 to leaf hashes and 0x01 to internal-node hashes.
- Advantage over flat hash lists: a Merkle tree lets a verifier check an individual branch before downloading the full dataset, which suits large files in peer-to-peer distribution.
- Applications: Bitcoin and Ethereum (transaction verification), Git, IPFS, BitTorrent, and Apache Cassandra (distributed systems), ZFS and OpenZFS (file-system integrity), and Certificate Transparency (certificate auditing).
Relevance to Truestamp
Truestamp uses an RFC 6962 style Merkle tree with the same 0x00 leaf / 0x01 interior domain separation this article cites, so the second-preimage mitigation described here is foundational to Truestamp’s Merkle construction and its inclusion proofs. The logarithmic verification property is what makes compact, offline proofs of item inclusion practical.
Citations
- Merkle tree - Wikipedia. Wikipedia contributors; based on Ralph Merkle’s 1979 work (U.S. Patent 4,309,569).