Introduction
A Merkle tree is a binary tree of hashes where each leaf is the hash of a data block and each internal node is the hash of its two children. The root hash commits to all the data in the tree. Merkle trees are used in Bitcoin (block verification), Git (object storage), Certificate Transparency (RFC 6962), and many blockchain systems. The key property is that you can prove a specific leaf is in the tree using only log(n) sibling hashes — a Merkle proof. This tool builds Merkle trees and generates inclusion proofs in your browser.
What this tool does
- Builds a Merkle tree from any list of data items (one per line).
- Computes the root hash, which commits to all data in the tree.
- Generates Merkle inclusion proofs with log(n) sibling hashes.
- Verifies proofs by reconstructing the root from a leaf and its siblings.
- Supports SHA-256, SHA-512, SHA-1, and MD5 hash algorithms.
- Offers Bitcoin-style duplicate-odd or promote-odd handling for unbalanced trees.
- Processes all data locally in your browser with no server calls.
How this tool works
Enter data items (one per line) in the input field. The tool hashes each item to create leaf nodes, then pairs them up and hashes each pair to create the next level. This continues until a single root hash remains. For odd numbers of leaves, the tool either duplicates the last node (Bitcoin style) or promotes it to the next level. To generate a proof, enable the proof option and select a leaf index. The tool collects the sibling hash at each level of the path from the leaf to the root. To verify, it hashes the leaf with each sibling in order and checks if the result matches the root. All computation happens client-side.
How Merkle trees work
Merkle trees were invented by Ralph Merkle in 1979 ('A Certified Digital Signature'). The structure is a binary hash tree: leaves are hashes of data blocks, and internal nodes are hashes of their children concatenated. The root hash is a compact commitment to the entire dataset — any change to any data block changes the root. The most powerful feature is the Merkle proof: to prove that a specific leaf is in the tree, you only need the leaf's hash and one sibling hash per level. For a tree with n leaves, a proof contains log2(n) hashes. This makes verification efficient even for enormous datasets. Bitcoin uses Merkle trees in block headers: the block header contains the Merkle root of all transactions, allowing lightweight (SPV) clients to verify a transaction is in a block without downloading the entire block. Git uses a similar structure: each commit hashes its tree, and each tree hashes its contents. Certificate Transparency (RFC 6962) uses Merkle trees to log all TLS certificates issued by participating CAs, allowing auditors to detect mis-issuance. The standard construction hashes pairs as H(left || right). Some implementations add domain separation (a prefix byte) to prevent second-preimage attacks on internal nodes. Bitcoin uses double-SHA-256 (SHA-256d) for each hash. This tool uses single hashing by default and supports the duplicate-odd strategy used by Bitcoin for trees with an odd number of nodes at any level.
How to use this tool
- Enter data items in the input field, one per line.
- Select a hash algorithm (SHA-256 is the default).
- Choose how to handle odd nodes: duplicate (Bitcoin) or promote.
- The root hash and leaf hashes appear in the output.
- To generate a proof: enable 'Show proof' and enter a leaf index.
- The proof shows the sibling hashes and whether verification succeeds.
Real-world examples
Building a tree from 4 items
Enter 4 items (one per line). The tool creates 4 leaf hashes, pairs them into 2 internal nodes, and hashes those into a root. A proof for any leaf contains 2 sibling hashes (log2(4) = 2).
Detecting tampering
Build a tree, then change one data item. The root hash changes completely. This is the key property: any modification to any leaf propagates to the root, making tampering detectable.
Inclusion proof for leaf 2
With 5 items and proof enabled for index 2, the tool shows 3 sibling hashes (ceil(log2(5)) = 3). Verification reconstructs the root from the leaf and siblings, confirming the leaf is in the tree.
Comparison with similar methods
| Method | Complexity | Typical use |
|---|---|---|
| Merkle Tree | O(n) build, O(log n) proof | Bitcoin, Git, Certificate Transparency |
| Hash List | O(n) build, O(n) proof | Simple integrity checking |
| Merkle Patricia Tree | O(log n) build, O(log n) proof | Ethereum state trie |
| Sparse Merkle Tree | O(log n) proof | Key-value stores, rollups |
Limitations or considerations
This tool uses simple concatenation hashing (H(left || right)) without domain separation. For production use, consider adding a prefix byte to distinguish leaf and internal nodes, as recommended in RFC 6962. The tool does not support double hashing (SHA-256d) as used in Bitcoin. The maximum tree size is limited by browser memory. For very large datasets (millions of items), a streaming implementation would be more appropriate. The keccak256 option falls back to SHA-256 because the Web Crypto API does not expose Keccak.
Frequently asked questions
What is a Merkle proof?
A Merkle proof is a list of sibling hashes needed to reconstruct the root from a specific leaf. For a tree with n leaves, the proof contains log2(n) hashes. The verifier hashes the leaf with each sibling in order and checks if the result matches the known root.
How does Bitcoin use Merkle trees?
Each Bitcoin block contains a Merkle root of all transactions in its header. Lightweight (SPV) clients can request a Merkle proof for a specific transaction and verify it against the block header without downloading the full block.
What is the duplicate-odd strategy?
When a level has an odd number of nodes, the last node is duplicated to create a pair. This is the strategy Bitcoin uses. The alternative is to promote the lone node to the next level without hashing it.
Are Merkle trees resistant to second-preimage attacks?
Standard Merkle trees are vulnerable to second-preimage attacks unless domain separation is used. Adding a prefix byte (0x00 for leaves, 0x01 for internal nodes) prevents an attacker from finding an internal node that hashes to the same value as a leaf. RFC 6962 recommends this practice.
Conclusion
The Merkle tree calculator provides a working implementation of binary hash trees with inclusion proof generation and verification. It is useful for studying blockchain data structures, understanding Certificate Transparency, and testing proof verification logic. The tool supports multiple hash algorithms and both common odd-node handling strategies. For production blockchain applications, consider domain-separated hashing and double-SHA-256.