Verify a Merkle inclusion proof (RFC 9162)

#What an inclusion proof shows

A transparency log keeps its records as the leaves of a Merkle tree and publishes the tree's root. An inclusion proof, also called an audit path, is the short list of sibling hashes you need to climb from one leaf to that root. For a log of about three billion entries the path has up to 32 hashes, because the tree is about 32 levels deep.

If your recomputed root equals a root you trust, the record is in the tree that root describes. Anyone who changed, removed or reordered a leaf would have changed the root. The proof is small, and checking it needs no access to any other record.

#How the check works

RFC 9162, the current version of Certificate Transparency, defines the tree and the check. It obsoletes RFC 6962; deployed logs still use 6962's identical hashing.

Hash the leaf with a leading zero byte: leaf = SHA-256(0x00 ‖ record).
Hash each pair with a leading one byte: node = SHA-256(0x01 ‖ left ‖ right). The two different first bytes keep a leaf from ever being mistaken for an inner node.
Walk the path. First reject an index that is not smaller than the tree size. Start with fn = the leaf's index (counting from zero) and sn = tree size minus one. For each sibling hash: if fn is odd, or fn equals sn, the sibling sits on the left; otherwise it sits on the right. After a left step with an even fn, shift both numbers right until fn is odd or zero, which skips levels where the rightmost node had no sibling. Then shift both right once.
Compare. At the end sn must be zero, and the result must equal the trusted root.

The whole check fits in a short function. This version runs in a browser and in Node 20 or later:

async function verifyInclusion(leafHex, index, size, path, rootHex) {
  const hex = (b) => [...b].map((x) => x.toString(16).padStart(2, "0")).join("");
  const bytes = (h) => Uint8Array.from(h.match(/../g), (x) => parseInt(x, 16));
  const node = async (l, r) => new Uint8Array(await crypto.subtle.digest("SHA-256", new Uint8Array([1, ...l, ...r])));
  if (BigInt(index) >= BigInt(size)) return false;
  let fn = BigInt(index), sn = BigInt(size) - 1n, r = bytes(leafHex);
  for (const p of path.map(bytes)) {
    if (sn === 0n) return false;
    if (fn & 1n || fn === sn) {
      r = await node(p, r);
      while (!(fn & 1n) && fn !== 0n) { fn >>= 1n; sn >>= 1n; }
    } else {
      r = await node(r, p);
    }
    fn >>= 1n; sn >>= 1n;
  }
  return sn === 0n && hex(r) === rootHex;
}

We ran it against Sigstore entry 500,000,000, with the leaf computed from the entry's body, and it returned true. The tool at the top of this page uses the same steps and shows each one.

#Where the trusted root comes from

The check is only as good as the root you compare with. If the same server sends you the proof and the root, a dishonest server can send a root made for you. Logs deal with this in three ways:

Signed roots. The log signs each root together with the tree size, often as a short text called a checkpoint. Verify that signature with the log's published key.
Consistency proofs. A second kind of proof shows that a newer tree contains an older one unchanged. Keep the last root you saw and ask for this proof before accepting a newer one.
Witnesses. Independent parties fetch and cosign roots, so a log can't show different versions to different people without being noticed.

The tool on this page checks the path. It does not check the signature on the root.

#Common mistakes

Leaving out the 0x00 and 0x01 bytes. Without them, an inner node can be passed off as a leaf, and the proof no longer means what you think.
Duplicating the last node. Some older Merkle designs copy the last hash when a level has an odd count. That made two different lists produce the same root (CVE-2012-2459 in Bitcoin). RFC 9162 trees never duplicate; an odd node moves up a level unchanged.
Using 32-bit numbers. JavaScript's & and >> work on 32-bit integers, and real logs have passed 2³¹ entries. Use BigInt, as above, or plain division.
Mixing up two indexes. Sigstore's log is split into shards. An entry's top-level logIndex counts across all shards, while inclusionProof.logIndex is the position in its shard's tree. The proof uses the second.
Hashing the wrong bytes. For a Sigstore entry the leaf is the base64-decoded body, not the JSON you received. Its hash is also the last 64 characters of the entry's UUID, which makes a quick cross-check.

#Questions

Do I need to download the whole log?

No. You need the leaf, its index, the tree size, the path and a root you trust. The path grows with the logarithm of the log's size: up to 32 hashes for about three billion entries.

What does an inclusion proof not show?

It shows that a record is in the tree, nothing about whether the record is true. It also says nothing about records that are absent. Showing that a log never dropped an entry later needs consistency proofs between roots.

Why does the tool flag a single changed character?

Every step feeds into the next, so changing any bit of any sibling hash changes every result above it. Tick the box in the tool to see the root drift from that step upward.

Can I check a proof from another log?

Yes, if the log follows RFC 6962 or RFC 9162 hashing. Paste the leaf hash, index, tree size, path and root as JSON. Logs that use other prefixes or other hash functions need a matching version of the check.

#How Upvera does it

Upvera Day Roots seals Upvera's activity into minute blocks. Each block's records form a Merkle tree with the same shape as RFC 9162, using short text labels instead of the single bytes 0x00 and 0x01, and each day publishes one root built over that day's blocks. Day files hold roots only, so the public can check the chain of days but not read the records.

A member can take an inclusion proof for one of their own public actions on app.upvera.co, under Settings › Security › Proofs, and check it at upvera.co/dogrula, which fetches the day file from GitHub and runs the check in the browser. The design is written up in the Day Roots report.

#Sources

RFC 9162: Certificate Transparency Version 2.0: the tree, the leaf and node prefixes, and the inclusion and consistency proofs.
RFC 6962: Certificate Transparency: the original version, with the same hashing.
Sigstore Rekor overview: the transparency log used in the example.
Rekor log API: the current tree size and root, open to browsers.
CVE-2012-2459: the duplicate-node problem in an older Merkle design.
transparency.dev: background on logs, checkpoints and witnesses.