How to use the merkle tree builder
- Enter the items, one per line. Each line is hashed as UTF-8 text with SHA-256.
- Choose how to treat an odd node at a level: hash it with itself, or carry it up unchanged. Tick the box for the 00 and 01 prefixes to follow the RFC 6962 style.
- Pick the number of the item to prove. To see a failed check, type different text in the box for an item to check instead.
- Read the root, the levels of hashes and the proof path, and whether the proof rebuilds the root.
Formula
leaf = SHA-256(item)
parent = SHA-256(left + right)
with prefixes: leaf = SHA-256(00 + item), parent = SHA-256(01 + left + right)
proof = the sibling hash at every level, with its side
Carrying an odd node up unchanged, with the prefixes on, gives the same tree as the Merkle hash of RFC 6962; the tests confirm this against a separate recursive version for 1 to 33 items.
Five items
The items tx1 to tx5 give 5 leaves, then 3 nodes (the last item hashed with itself), then 2, then the root, so there are 4 levels. With the duplicate rule the root is e005b5664946b94dcae30e856ab0058930eb5ec65ca113c90331454335612140.
The proof for item 3 has 3 hashes: its neighbor tx4, the hash of the pair tx1 and tx2, and the branch that holds only tx5. Hashing tx3 and combining it with those on the stated sides rebuilds the root. Changing the item to "tx3 (edited)" gives a different root, so the proof fails.
What a Merkle tree is good for
A single root hash stands for a whole list. Anyone holding the root can check that one item belongs to the list from a short proof, whose length grows with the logarithm of the list size, without seeing the other items. Version control systems, certificate logs, some databases and blockchains use this idea.
The odd node rule matters. Hashing the last node with itself makes the lists a b c and a b c c share a root, a flaw that has been exploited in practice. Marking leaves and inner nodes with different prefixes also stops an inner hash from being passed off as an item. See the Hash Generator to check a single hash and the HMAC Generator for keyed hashes.
Matching other systems
Real systems fix many details: how items are encoded, the order of left and right, how odd nodes are handled and what the prefixes are. A root built here matches another system only when its rules are exactly these.
Assumptions and limits
- SHA-256 is used and each non-empty line is one item; blank lines are skipped.
- Items are encoded as UTF-8 text, not as hex or raw bytes.
- Up to 128 items are accepted and the item number to prove counts from 1.
- Hashes in the tables are shortened to the first 8 or 16 hex digits; the root is shown in full.
- The page builds and verifies in your browser and nothing is uploaded.
Frequently asked questions
Why does a proof not need the other items?
The sibling hashes already contain the other items' information. Combining your item's hash with them in order reproduces every parent up to the root.
Why add the 00 and 01 prefixes?
They separate leaf hashes from inner hashes, so a pair of leaves can never be mistaken for a single leaf. Without them, some attacks become possible.
What does carry it up as is mean?
An odd last node is copied to the next level unchanged, instead of being hashed with itself. No two different lists then share a root.
Is this the Merkle tree Bitcoin uses?
Bitcoin hashes the last node with itself when a level is odd, and uses double SHA-256 on binary data. The duplicate setting has the tree shape, but not the double hashing.