Every other tree on this site answers some version of "where is this key, and how fast can I get there." A Merkle tree answers a completely different question: does this one item really belong to this dataset, and can you prove it without handing over the whole dataset? The naive alternative — hash the entire dataset as one blob — can tell you that something changed, but not what, and proving one item's membership means shipping every other item right along with it so the verifier can re-hash the whole thing. A Merkle tree hashes the data in a binary tree instead: each leaf is the hash of one data block, each internal node is the hash of its two children's hashes, and the single hash at the root summarizes everything beneath it. Change one byte anywhere in the dataset and the root changes — but proving any one leaf belongs under that root only costs the hashes along one path to the top, not the rest of the tree.
Six log entries are loaded below, each independently hashed as a leaf and combined pairwise up to one root hash — all real SHA-256 via the browser's own Web Crypto API, not a toy hash. Edit any entry's text and click Rebuild: only the nodes on the path from that entry up to the root actually change hash (outlined below), everything off that path stays exactly as it was — the whole point of building the hashes this way instead of as one flat hash over everything. Then pick an entry from the dropdown and click Prove & Verify: it reads whatever text is currently in that entry's box, walks the sibling hashes needed to recompute the root from just that one leaf (dashed outline), and checks the result against the root shown in the stats line — independently of the rest of the tree. Edit an entry's text but don't rebuild, then prove that same entry: the proof still walks the same sibling hashes, but the freshly typed text no longer combines up to the displayed root, and verification correctly fails. That's tamper detection in miniature — the same mechanism a Certificate Transparency log or a Bitcoin light client relies on.
The obvious first design — hash a leaf as H(data) and an internal node as
H(left || right) — has a real flaw: nothing stops the two kinds of input from
colliding. If some leaf's raw data happens to equal the concatenation of two other nodes' hashes,
that leaf's hash and that internal node's hash are the same computation, and an attacker
who can choose the data being committed to can potentially present an internal node's two children
as if they were a single leaf's contents, or vice versa, forging a proof for data that was never
actually in the tree. Certificate Transparency's specification (RFC 6962) closes this with one extra byte:
every leaf hash is SHA-256(0x00 || data) and every internal node hash is
SHA-256(0x01 || left || right). The prefix byte puts leaf hashes and internal-node
hashes in disjoint spaces — no leaf hash can ever equal a node hash, because they were never
computed the same way to begin with. This page's demo and reference implementation use the same two
prefixes, for the same reason.
Pairing hashes level by level works cleanly when the leaf count is a power of two. When it isn't, something has to give at the odd level. Bitcoin's original merkle-root algorithm picked the simplest fix: if a level has an odd number of hashes, duplicate the last one and pair it with itself. That choice turned out to be exploitable — CVE-2012-2459, reported in 2012 and fixed before it was ever exploited in the wild, showed that a block with a duplicated transaction (or certain other repeating sequences) could produce the same merkle root as a legitimately different block, letting a malicious peer serve an invalid block that hashed identically to a valid one and get a node to cache it as permanently invalid — an eclipse-attack vector against nodes that hadn't yet seen the real block. The structural cause: duplicating a hash to pad an odd level throws away the guarantee that a given root has exactly one honest set of leaves that produces it.
RFC 6962 avoids the problem by never padding at all. Instead of pairing adjacent hashes bottom-up,
it builds top-down by recursive split: for n leaves, the left subtree gets the largest
power of two strictly less than n, and the right subtree gets the rest, recursively.
Every leaf still ends up under exactly one well-defined path to the root, but the tree is
deliberately unbalanced when n isn't a power of two — some leaves sit closer to
the root than others, so their inclusion proofs are shorter. Building a 5-leaf tree this way splits
it 4-and-1: leaves 0–3 form a balanced little tree three levels deep, and leaf 4 attaches directly to
the root as its sibling, one level deep. Leaf 4's proof needs one hash; leaves 0–3 each need three.
Both are still O(log n), just not identical for every leaf — the price this
design pays to avoid ever duplicating a hash. This page's reference implementation and demo build
the tree this exact way, not Bitcoin's padded version.
const enc = new TextEncoder();
function concatBytes(...arrays) {
const total = arrays.reduce((s, a) => s + a.length, 0);
const out = new Uint8Array(total);
let offset = 0;
for (const a of arrays) { out.set(a, offset); offset += a.length; }
return out;
}
function hexToBytes(hex) {
const out = new Uint8Array(hex.length / 2);
for (let i = 0; i < out.length; i++) out[i] = parseInt(hex.substr(i * 2, 2), 16);
return out;
}
async function sha256Hex(bytes) {
const digest = await crypto.subtle.digest('SHA-256', bytes);
return Array.from(new Uint8Array(digest)).map((b) => b.toString(16).padStart(2, '0')).join('');
}
async function leafHash(data) {
return sha256Hex(concatBytes(new Uint8Array([0x00]), enc.encode(data)));
}
async function nodeHash(leftHex, rightHex) {
return sha256Hex(concatBytes(new Uint8Array([0x01]), hexToBytes(leftHex), hexToBytes(rightHex)));
}
// RFC 6962-style recursive power-of-two split -- no padding, no duplication.
async function build(leaves, lo, hi) {
if (hi - lo === 1) {
const hash = await leafHash(leaves[lo]);
return { hash, lo, hi, isLeaf: true };
}
const n = hi - lo;
let k = 1;
while (k * 2 < n) k *= 2; // largest power of two strictly less than n
const left = await build(leaves, lo, lo + k);
const right = await build(leaves, lo + k, hi);
const hash = await nodeHash(left.hash, right.hash);
return { hash, lo, hi, left, right, isLeaf: false };
}
function buildTree(leaves) {
return leaves.length === 0 ? null : build(leaves, 0, leaves.length);
}
// root-to-leaf order: {hash, dir} where dir is which side the SIBLING sits on
function auditPath(root, index) {
const path = [];
let cur = root;
while (!cur.isLeaf) {
if (index < cur.left.hi) {
path.push({ hash: cur.right.hash, dir: 'right' });
cur = cur.left;
} else {
path.push({ hash: cur.left.hash, dir: 'left' });
cur = cur.right;
}
}
return path;
}
async function verifyProof(leafData, path, rootHash) {
let hash = await leafHash(leafData);
for (let i = path.length - 1; i >= 0; i--) {
const { hash: sib, dir } = path[i];
hash = dir === 'right' ? await nodeHash(hash, sib) : await nodeHash(sib, hash);
}
return hash === rootHash;
}The demo above wraps these exact five functions (leafHash, nodeHash,
build/buildTree, auditPath, verifyProof) with UI
bookkeeping — rendering the tree, tracking which nodes changed since the last build, wiring up the
Rebuild and Prove & Verify buttons — but the hashing and proof logic is unchanged from what's
shown here, run through the real Web Crypto API rather than a hand-rolled hash.
Prototyped and stress-tested standalone in Node (which has the same Web Crypto API under
require('crypto').webcrypto) before writing any page content. Building trees for every
leaf count from 1 to 40 with random leaf data and generating+verifying every single leaf's inclusion
proof against the real root came back clean: 820 proof round-trips, zero failures. Tampering with
any one leaf (appending a character) and rebuilding changed the root every time across 209
single-leaf-tamper trials at leaf counts 2 through 20, and a proof generated for the original
leaf value correctly failed to verify when handed the tampered value instead, across the same 209
trials — zero forged proofs wrongly accepted. Editing leaf 0 in an 8-leaf tree and rebuilding left
the untouched right half's root-child hash byte-for-byte identical before and after, confirming the
"only the path to the edited leaf changes" claim isn't just visually plausible on this page's own
diagram but actually true of the hashes. Two independent builds of the same leaf data produced
identical roots (determinism). The exact functions shown in Reference implementation above were then
extracted from the shipped page and driven through a fake-DOM click harness (Node's vm,
no real browser available in this environment) simulating Rebuild and Prove & Verify clicks on
the page's own default six entries: rebuilding after editing entry 2 lit up exactly the three nodes
on entry 2's own path to the root and no others; proving an untouched entry passed; editing an
entry's text without rebuilding and then proving that same entry correctly failed. See
/tmp/merkle/ref.js, /tmp/merkle/stress.js, and
/tmp/merkle/shape.js, scratch, not committed.
A Merkle proof only proves inclusion under a root you already trust — it says nothing about how you came to trust that root. The whole scheme's security rests on the root hash arriving through some channel the data itself can't tamper with: burned into a block header signed by proof-of-work, published by a log operator under public audit, baked into a release artifact signed with a separate key. A Merkle proof that verifies correctly against a root the attacker also controls proves nothing at all — it's a consistency check, not a trust anchor by itself.
Proof length isn't uniform across leaves once the leaf count isn't a power of two —
measured above, not just asserted. The 5-leaf example in "Odd leaf counts" needs one sibling
hash to prove leaf 4 and three to prove any of leaves 0 through 3; a real deployment with a growing,
non-power-of-two dataset (most of them) will have some proofs cheaper than others by design, not by
accident. Still O(log n) for every leaf, just not identical — worth knowing before
assuming every proof in a given tree costs the same.
Domain separation has to be enforced by the hash construction itself, not layered on as an afterthought. It's tempting to add the 0x00/0x01 prefix only where it's convenient and skip it somewhere that "obviously" can't be reached by an attacker — but the whole guarantee is that leaf-space and node-space never overlap, for any input, not just the inputs a particular implementation happens to generate. See "Domain separation" above for what breaks without it.
Time: building the tree from n leaves takes O(n) hash
computations (n leaf hashes plus n-1 internal-node hashes for any binary
tree with n leaves). Generating or verifying an inclusion proof costs
O(log n) hashes — the depth of the leaf being proven, which can vary by leaf when
n isn't a power of two (see Pitfalls). Updating a single leaf and recomputing the root
touches only the O(log n) nodes on that leaf's path to the root, not the other
n-1 leaves. Space: O(n) for the full tree (2n-1
nodes total); an inclusion proof itself is only O(log n) hashes, the entire point of
building the structure this way instead of shipping the whole dataset to prove one thing about
it.
This site's guide, Choosing a Search Tree, sets this entry aside from the seven it actually compares, the same way the Range Query guide sets Binary Heap aside before comparing its own five: it isn't about ordering or lookup by key at all, only "does this one item belong to this dataset," provable without the rest of the dataset.