DataTerminology.comNEW
Also known as: Hash Tree
A tree of cryptographic hashes enabling efficient and secure verification of large data sets’ integrity and membership.
DESCRIPTION
A Merkle tree labels each leaf with the hash of a data block and internal nodes with hashes of their children. The root hash authenticates the entire dataset. Verifiers can check inclusion with small proofs without downloading all data. Merkle trees underpin blockchains, Git, and Certificate Transparency logs. Variants like sparse Merkle trees and Patricia tries optimize space or address key-value maps.
ALTERNATIVE DEFINITIONS
Wikipedia
A Merkle tree or hash tree is a tree in which every leaf node is labelled with the cryptographic hash of a data block, and every non-leaf node is labelled with the cryptographic hash of the labels of its child nodes.
Defines node labeling precisely using cryptographic hashes.
IETF
The Merkle Tree used for Certificate Transparency is a binary hash tree with leaves as hashes of certificates and nodes computed from their children, enabling efficient proofs of inclusion.
Standards context and binary tree specifics for CT logs.
RELATED TERMS
Cryptographic Hash Function Blockchain Integrity Verification Merkle Root Proof of Inclusion Sparse Merkle Tree Patricia Merkle Trie Certificate Transparency Git Content Addressing
COMPETING TERMS
Authenticated Skip List Hash List
KNOWLEDGE AREAS
Data Security Data Management Software Engineering Data Storage & Operations AI
TARGET AUDIENCE
Software Developer Cybersecurity Engineer Security Architect Data Engineer Data Architect
EXTERNAL SOURCES
- Wikipedia - Merkle tree
- IETF - Certificate Transparency Merkle trees
- Bitcoin.org - Merkle trees in Bitcoin blocks
- Git - Merkle structures in Git objects
TOP QUESTIONS
Why use a Merkle tree?
It enables efficient integrity checks and inclusion proofs with only logarithmic-size proofs, ideal for large datasets.
Category: Relevancy
How does a Merkle proof work?
Provide the leaf and sibling hashes along the path to the root; recomputing verifies inclusion.
Category: How-to
What are common pitfalls?
Using weak or inconsistent hash functions undermines security. Always specify hashing and node ordering.
Category: Mistakes
How do Merkle trees relate to blockchains?
They summarize transactions in a block; the Merkle root commits to all data with efficient verification.
Category: Example
What is a sparse Merkle tree?
A tree over a vast key space with default empty hashes, enabling efficient authenticated key-value maps.
Category: Example
What risks exist with Merkle tree misuse?
Incorrect hashing order or collision-prone hashes can allow forgery of proofs.
Category: Risks
How does a Merkle tree compare to hash lists?
Merkle trees enable logarithmic proofs; hash lists require linear data to verify inclusion.
Category: Alternatives
Where else are Merkle trees used?
Git object graphs, P2P systems, and transparency logs rely on Merkle structures.
Category: Example
How to choose a hash for Merkle trees?
Use collision-resistant hashes like SHA-256; define domain separation and node serialization precisely.
Category: Requirements