Merkle trees: inclusion and consistency proofs (RFC 6962)

RFC 6962 (Certificate Transparency) / RFC 9162 (CT 2.0) Merkle-tree hash and proof-verification core: the load-bearing primitive a static-CT client, a Merkle-Tree-Certificates relying party, and a sigstore / Rekor inclusion check all compose. Every verb is strict verification over SHA-256: zero new crypto.

leafHash / nodeHash / emptyRootHash build the tree hashes with the two domain-separation prefixes fixed by the spec: a leaf is SHA-256(0x00 || entry), an interior node is SHA-256(0x01 || left || right), the empty tree is SHA-256(""). Those 0x00 / 0x01 prefixes are the second-preimage defense: without them a leaf whose bytes equal a valid interior node's preimage could be smuggled in as present.

verifyInclusion folds an audit path back to a root and constant-time- compares it to a trusted checkpoint root; verifyConsistency reconstructs both the old and the new root from a consistency proof (the append-only guarantee lives in the old-root leg). Both are fail-closed: a malformed coordinate, an out-of-range index, an inverted window, a wrong hash length, or a proof whose node count does not match the tree geometry throws a typed merkle/* error; the one boolean-false result is the final root comparison ("root matched" vs "did not"). A false from verifyInclusion means "not proven present against this root", never "validly absent": an inclusion proof cannot express absence. Tree coordinates are uint64, carried as BigInt so a large index is never Number-narrowed. This is not a DER format. Like pki.ct it is a companion module reached explicitly, never routed by the detect-and-parse orchestrator.

pki.merkle.leafHash

since 0.1.28 stable
pki.merkle.leafHash(entry) -> Buffer

The Merkle leaf hash MTH({d}) = SHA-256(0x00 || entry). The 0x00 prefix is the leaf-domain second-preimage separation and is applied unconditionally. Throws merkle/bad-input if entry is not a Buffer / Uint8Array.

Example

pki.merkle.leafHash(Buffer.from("leaf data")); // -> <Buffer 32-byte leaf hash>

See also: pki.merkle.nodeHash, pki.merkle.verifyInclusion

References

pki.merkle.nodeHash

since 0.1.28 stable
pki.merkle.nodeHash(left, right) -> Buffer

The Merkle interior-node hash SHA-256(0x01 || left || right). Both operands must be 32-byte hashes; the 0x01 prefix is applied unconditionally. Throws merkle/bad-input on a non-buffer operand, merkle/bad-hash-length on an operand that is not exactly 32 bytes.

Example

var l = pki.merkle.leafHash(Buffer.from([0]));
var r = pki.merkle.leafHash(Buffer.from([1]));
pki.merkle.nodeHash(l, r); // -> <Buffer 32-byte node hash>

See also: pki.merkle.leafHash

References

pki.merkle.emptyRootHash

since 0.1.28 stable
pki.merkle.emptyRootHash() -> Buffer

The Merkle tree head of the empty tree, MTH({}) = SHA-256("") (e3b0c442...b855). A fresh Buffer each call.

Example

pki.merkle.emptyRootHash(); // -> <Buffer e3 b0 c4 42 ...>

See also: pki.merkle.verifyConsistency

References

pki.merkle.verifyInclusion

since 0.1.28 stable
pki.merkle.verifyInclusion(opts) -> boolean

Verify an RFC 6962 / RFC 9162 audit (inclusion) proof: fold leafHash up the audit path and constant-time-compare the reconstructed root to rootHash. Returns true iff the proof binds the leaf to the root; a well-formed proof that does not match returns false, meaning "not proven present against this root" and never "validly absent". A malformed input throws a typed merkle/* error: a coordinate that is not a non-negative integer (or a Number >= 2^53), treeSize 0, leafIndex >= treeSize, a non-32-byte hash, or a proof whose node count does not match the tree geometry.

Options

leafIndex:  number | bigint,  // 0-based leaf position (uint64; pass BigInt above 2^53)
treeSize:   number | bigint,  // total leaf count of the tree the root commits to
leafHash:   Buffer,           // 32-byte leaf hash (e.g. from pki.merkle.leafHash)
proof:      Buffer[],         // the audit path, each node a 32-byte hash
rootHash:   Buffer,           // 32-byte trusted checkpoint root

Example

var lh = pki.merkle.leafHash(Buffer.from([0]));
pki.merkle.verifyInclusion({ leafIndex: 0, treeSize: 1, leafHash: lh, proof: [], rootHash: lh }); // -> true

See also: pki.merkle.leafHash, pki.merkle.verifyConsistency

References

pki.merkle.verifyConsistency

since 0.1.28 stable
pki.merkle.verifyConsistency(opts) -> boolean

Verify an RFC 6962 / RFC 9162 consistency proof between an older tree of oldSize leaves (root oldRoot) and a newer tree of newSize leaves (root newRoot). Reconstructs both roots from the proof and constant-time-compares each; returns true iff both match. The append-only guarantee lives in the old-root leg: a proof that yields a valid newRoot but the wrong oldRoot is a rewritten history and returns false. Equal non-zero sizes require an empty proof and oldRoot == newRoot.

An oldSize of 0 with a non-empty newer tree is refused as merkle/no-consistency-claim. RFC 6962 sec. 2.1.2 defines the proof for 0 < oldSize < newSize: the empty tree is a prefix of every tree by definition, so there is no proof to check and nothing at all binds newRoot. Two empty trees are still answered: that is the degenerate identity case, and both roots must be emptyRootHash().

A malformed input throws a typed merkle/* error: oldSize > newSize, a non-empty proof where the geometry requires none (or empty where it requires one), a non-32-byte hash, or a wrong node count.

Options

oldSize:  number | bigint,  // leaf count of the older tree (uint64)
newSize:  number | bigint,  // leaf count of the newer tree (>= oldSize)
oldRoot:  Buffer,           // 32-byte root of the older tree
newRoot:  Buffer,           // 32-byte root of the newer tree
proof:    Buffer[],         // the consistency proof, each node a 32-byte hash

Example

var r = pki.merkle.leafHash(Buffer.from([0]));
pki.merkle.verifyConsistency({ oldSize: 1, newSize: 1, oldRoot: r, newRoot: r, proof: [] }); // -> true

See also: pki.merkle.verifyInclusion, pki.merkle.emptyRootHash

References