Hong Life CalculatorsUnderstanding the Merkle tree size and proof length calculator — concept and principle
A Merkle tree hashes data in pairs, level by level, until a single root hash remains. That one root commits to every item in the set. This calculator tells you how tall the tree is for a given number of leaves and how many hashes, and how many bytes, an inclusion proof needs. It is used when designing blockchains, certificate transparency logs, file-sync systems and any setup where someone must prove that one item belongs to a large set without sending the whole set.
How it is calculated
For N leaves in a binary Merkle tree:
- Tree height = ⌈log₂ N⌉, the number of levels above the leaves.
- Proof hashes = ⌈log₂ N⌉, one sibling hash per level.
- Proof size = ⌈log₂ N⌉ × 32 bytes for a 32-byte hash such as SHA-256.
⌈x⌉ means rounding up to the next whole number, because a partial level still needs a full step.
The principle
Each level halves the number of nodes, so after k levels at most 2ᵏ leaves are covered; the height is the smallest k with 2ᵏ ≥ N. To prove a leaf is included, the prover sends the sibling hash at each level. The verifier hashes the leaf with the first sibling, then the result with the next sibling, and so on up to the top. If the final value equals the trusted root, the leaf must be in the tree, because forging a different path would require finding a hash collision. The proof grows with the logarithm of N, so a million items need only 20 hashes.
Worked example
- Input: N = 1,000,000 leaves.
- log₂ 1,000,000 ≈ 19.93; rounding up gives a height of 20 (2²⁰ = 1,048,576 ≥ 1,000,000).
- Proof hashes needed: 20.
- Proof size: 20 × 32 = 640 bytes.
| Number of leaves | Tree height |
|---|---|
| 250,000 | 18 |
| 500,000 | 19 |
| 750,000 | 20 |
| 1e+06 | 20 |
| 1.25e+06 | 21 |
| 1.5e+06 | 21 |
| 2e+06 | 21 |
How to read the result
Doubling the number of leaves adds only one hash (32 bytes) to the proof. For comparison, sending all one million 32-byte leaf hashes would take 32 MB. The full tree stores about 2N − 1 nodes, so storage is linear while proofs are logarithmic.
Common mistakes
- Counting the root or the leaf itself as part of the proof; the proof is only the siblings.
- Forgetting that the verifier needs the leaf position (left or right at each level) to hash in the right order.
- Hashing leaves and inner nodes the same way; standards such as RFC 6962 prefix them differently to block second-preimage tricks.
Frequently asked questions
Who invented Merkle trees?
Ralph Merkle, in work on digital signatures from 1979.
Why does Bitcoin use Merkle trees?
So lightweight wallets can check that a transaction is in a block using only the block header and a short proof.
What hash size should I use?
32 bytes (256 bits), as with SHA-256, is the common choice.
Sources: R. C. Merkle, "A Digital Signature Based on a Conventional Encryption Function", CRYPTO '87 · IETF RFC 6962, Certificate Transparency