Lab — Merkle tree inclusion proof

Build a small Merkle tree, produce an inclusion proof for one leaf, verify it against the root, then forge a proof and watch verification reject it — seeing how a short list of sibling hashes certifies membership in a set you never fully receive.

Track

Engineering

Module

7 · Labs & experiments

Prerequisites

Hash functions · Merkle trees · Node.js 16+ (built-in crypto)

This teaching exercise, offline and synthetic, builds a Merkle tree over eight items, proves one of them is included using only log2(8) = 3 sibling hashes, and verifies the proof against the root. You then forge a proof and see it rejected. The takeaway: given a trusted root, a tiny proof certifies membership without the rest of the set — but membership is not validity.

Leaves are H(0x00 || item); internal nodes are H(0x01 || left || right). The distinct domain tags (0x00 for leaves, 0x01 for nodes) stop an attacker from passing an internal node off as a leaf. An inclusion proof is the ordered list of sibling hashes from the leaf up to the root, each tagged with whether the sibling sits on the left or the right.

Leaf hash

H(0x00 || item). The leaf-domain tag distinguishes leaves from internal nodes.

Inclusion proof

The ~log2(n) sibling hashes along the path from one leaf to the root, each with its side (left/right).

Verify

Recompute upward from the leaf using the siblings; accept only if the recomputed root equals the trusted root.

1. 1Hash each of 8 items into a leaf with the 0x00 tag.
2. 2Hash adjacent pairs with the 0x01 tag, level by level, up to a single root.
3. 3For a chosen index, collect the sibling hash at each level and record whether it is the left or right child.
4. 4Verify by folding the siblings into the leaf hash in order and comparing the result to the trusted root.
5. 5Forge: swap one sibling in the proof and confirm verification fails.

lab5.js — synthetic Merkle inclusion proof (Node.js crypto)
const crypto = require('crypto');
const H = (buf) => crypto.createHash('sha256').update(buf).digest();
const LEAF = Buffer.from([0x00]), NODE = Buffer.from([0x01]);

const hashLeaf = (item) => H(Buffer.concat([LEAF, Buffer.from(item)]));
const hashNode = (l, r) => H(Buffer.concat([NODE, l, r]));

function build(items) {
  let level = items.map(hashLeaf);
  const levels = [level];
  while (level.length > 1) {
    const next = [];
    for (let i = 0; i < level.length; i += 2) {
      const l = level[i];
      const r = i + 1 < level.length ? level[i + 1] : level[i]; // duplicate last if odd
      next.push(hashNode(l, r));
    }
    levels.push(next);
    level = next;
  }
  return { root: level[0], levels };
}

function proof(levels, index) {
  const path = [];
  let idx = index;
  for (let lvl = 0; lvl < levels.length - 1; lvl++) {
    const level = levels[lvl];
    const isRight = idx % 2 === 1;
    const sibIdx = isRight ? idx - 1 : Math.min(idx + 1, level.length - 1);
    path.push({ hash: level[sibIdx], side: isRight ? 'left' : 'right' });
    idx = Math.floor(idx / 2);
  }
  return path;
}

function verify(item, path, trustedRoot) {
  let h = hashLeaf(item);
  for (const { hash, side } of path) {
    h = side === 'left' ? hashNode(hash, h) : hashNode(h, hash);
  }
  return h.equals(trustedRoot);
}

const items = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'];
const { root, levels } = build(items);
const p = proof(levels, 2); // prove 'c' (index 2)

console.log('proof length:', p.length);
console.log('verify genuine:', verify('c', p, root));

// Forge: corrupt the first sibling hash in the proof.
const forged = p.map((n, i) => (i === 0 ? { ...n, hash: H(Buffer.from('x')) } : n));
console.log('verify forged :', verify('c', forged, root));

expected console output
proof length: 3
verify genuine: true
verify forged : false

The proof is 3 hashes for 8 leaves (log2(8) = 3). Folding the genuine siblings into the leaf hash for "c" reproduces the trusted root exactly, so verification accepts. The forged proof replaces one sibling, so the recomputed root diverges from the trusted root and verification rejects — there is no near-match, any wrong sibling anywhere breaks the climb to the root.

• ▸Omitting domain tags (0x00/0x01): without them an internal node can be reinterpreted as a leaf, a second-preimage-style confusion.
• ▸Verifying against a root pulled from the same source as the proof. The root must be trusted independently (signed or published); otherwise a forged root makes forged proofs pass.
• ▸Assuming an inclusion proof can prove absence. A plain unsorted tree proves membership only; non-membership needs a sorted tree or trie.
• ▸Reading a valid proof as approval. It shows the item was part of a committed set, not that including it was correct or authorized.

Expected direction: An inclusion proof only demonstrates a path from one existing leaf up to the root; there is no path to show for an item that is not a leaf, and you cannot prove the absence of a matching leaf without revealing all leaves. To prove non-membership you must build a sorted/ordered Merkle tree (or a Merkle-Patricia trie) over canonically ordered items, then prove inclusion of the two adjacent leaves that would bracket where "z" belongs, showing there is no gap for it.

Why is a Merkle inclusion proof only about log2(n) hashes?

It carries one sibling hash per level along the path from the leaf to the root, and a balanced tree over n leaves has about log2(n) levels.

Why must each proof element record whether the sibling is on the left or right?

Because hashing is order-sensitive: H(0x01||left||right) differs from H(0x01||right||left), so the side determines how each sibling is folded in during verification.

What does a valid inclusion proof establish, and what does it not?

It establishes that the item was committed under the trusted root. It does not establish that including the item was correct, authorized, or that the root itself is trustworthy — the root must be authenticated separately.