Merkle Tree
Subject: Computer and Technology noun /ˈmɜːr.kəl triː/ 1 definition
- data-structures
- cryptography
- distributed-systems
- data-integrity
-
Definition (noun)
Entry #281 · UpdatedA Merkle Tree (also known as a hash tree) is a hierarchical cryptographic data structure in which every leaf node stores the cryptographic hash of a data block and every internal node stores the hash of its concatenated child hashes. Computing hashes recursively from the leaves upward produces a single top-level digest—the Merkle root—that cryptographically commits to the entire dataset, meaning any modification to a single bit in a leaf cascades into a completely different root hash. To prove that a specific item belongs to the dataset without transferring the full collection, a prover supplies only the target record and an authentication path (Merkle proof) of sibling hashes along the branch to the root, allowing verification in
O(log n)proof size and time for a balanced tree. While a Merkle tree provides tamper-evident integrity and efficient partial synchronization across untrusted peers when paired with a collision-resistant hash function and leaf-versus-node domain separation, it does not encrypt data or authenticate the root's origin without an external digital signature or trusted anchor.Common Types
Binary Merkle Tree: Pairs adjacent child hashes at each level into a binary hierarchy to keep authentication paths compact, serving as the standard structure for verifying transaction sets in blockchains, file chunks in BitTorrent, and entries in Certificate Transparency logs.
Sparse Merkle Tree (SMT): Maps keys across a fixed, vast address space (such as
2^256keys) by collapsing empty subtrees to precomputed default hashes, enabling compact cryptographic proofs of both inclusion and non-inclusion.Merkle Patricia Trie (MPT): Combines a space-compressed radix prefix trie with cryptographic node hashing so keys map deterministically to paths, supporting verifiable key-value lookups and incremental state-root updates in systems like Ethereum.
Merkle Mountain Range (MMR): Organizes append-only data as a forest of full binary Merkle trees ("peaks") of decreasing heights, permitting
O(log n)worst-case appends and historical membership proofs without rebuilding previously finalized subtrees.
Example
When a lightweight blockchain client checks whether transaction
tx_4is included in a block holding 2,048 transactions, it requests an inclusion proof instead of downloading the entire block payload. A peer returnstx_4and an 11-hash SHA-256 authentication path (352 bytes total), which the client hashes upward level by level to verify that the resulting 32-byte digest matches the Merkle root committed in the 80-byte block header.