21 · Inclusion proofs and consistency proofs

We know the 32-byte root "commits" the entire log. But when someone asks, "Was this record really in that log?" — do you hand over millions of records? The real power of a Merkle tree reveals itself here: without the full log, just the root and log n hashes mathematically prove the existence of a record.

Inclusion proof: proving existence without the log

Consider proving that leaf #2 (R2) is included in a tree of n=8. The verifier knows only the root.

Here is the verification procedure. The verifier receives H2 (leaf hash) + proof path [H3, N(01), N(4567)]:

1. node_hash(H2, H3) → recompute N(23)
2. node_hash(N(01), N(23)) → recompute N(0123) (N(01) is provided in the proof)
3. node_hash(N(0123), N(4567)) → recompute the root
4. If the recomputed root matches the published root → H2 is definitely in that tree ✅

For a tree of n leaves, the proof path length is ⌈log₂ n⌉. Even for a million records, the proof path is only 20 hashes — 640 bytes.

Inclusion proof code

crates/quipu-core/src/merkle.rs — inclusion_proof / verify_inclusionpub fn inclusion_proof(leaves: &[Hash], m: usize) -> Vec<Hash> {
    let n = leaves.len();
    if n == 1 { return Vec::new(); }
    let k = split(n);
    if m < k {
        let mut path = inclusion_proof(&leaves[..k], m);
        path.push(mth(&leaves[k..]));  // append right subtree hash
        path
    } else {
        let mut path = inclusion_proof(&leaves[k..], m - k);
        path.push(mth(&leaves[..k]));  // append left subtree hash
        path
    }
}

// Verification runs independently, without the log:
pub fn verify_inclusion(
    leaf: &Hash, leaf_index: usize, tree_size: usize,
    proof: &[Hash], root: &Hash,
) -> bool { /* recompute root by walking the proof path and compare */ }

The recursive structure is intuitive. If the target leaf is on the left (m < k), the right subtree root goes into the path; if on the right, the left subtree root goes in. When the recursion unwinds, the path contains "the roots of all the sibling subtrees," ordered leaf-to-root.

Consistency proof: proving append-only

Where an inclusion proof says "this record exists," a consistency proof says "past root R_m is a prefix of current root R_n — meaning records were only appended after position m, and the original m records are unchanged to the byte."

The core idea of a consistency proof: find the shared subtree of both trees and show that subtree is consistently bound into both roots. In the example above, N(0123) is the root of the m=4 tree and the left child of the n=6 tree. That single node is the evidence connecting both trees.

crates/quipu-core/src/merkle_log.rs — prove_consistencypub fn prove_consistency(
    &mut self,
    first_size: u64,
) -> Result<ConsistencyProof> {
    let leaves = load(&self.path)?;
    let path = consistency_proof(&leaves, first_size as usize);
    Ok(ConsistencyProof {
        first_size,
        second_size: leaves.len() as u64,
        path,
    })
}

Verification is fully independent

For both inclusion and consistency proofs, the verification functions never look at the log. verify_inclusion and verify_consistency receive only the root(s) and the proof path, and compute purely in hashes:

crates/quipu-core/src/merkle.rs — verify_inclusion signaturepub fn verify_inclusion(
    leaf: &Hash,          // hash of the record being verified
    leaf_index: usize,   // position in the tree (0-based)
    tree_size: usize,    // tree size at proof time
    proof: &[Hash],       // audit path (O(log n) hashes)
    root: &Hash,           // the published / anchored root — the only trusted input
) -> bool

This design matters. An external auditor doesn't need to connect to the Quipu-Log server or receive any data from it. They take the root from an external anchor (Ch. 22), pair it with the proof path (generated by the server), and run this function. Any RFC 6962 implementation in any language is compatible.

The API exposed by MerkleLog

Requesting a proof from the MerkleLog struct is straightforward:

crates/quipu-core/src/merkle_log.rs — proof request examplelet mut log = MerkleLog::open(dir)?;
// Inclusion proof: record at leaf_index #42 is in the current tree
let p: InclusionProof = log.prove_inclusion(42)?;
assert!(verify_inclusion(&p.leaf, p.leaf_index as usize,
                         p.tree_size as usize, &p.path, &log.root()));

// Consistency proof: the root when tree_size was 1000 is a prefix of the current tree
let c: ConsistencyProof = log.prove_consistency(1000)?;
assert!(verify_consistency(c.first_size as usize, c.second_size as usize,
                           &first_root, &log.root(), &c.path));

Recap

• Inclusion proof: record hash + ⌈log₂ n⌉ sibling hashes → recompute root → compare root. Proves existence in O(log n) without the full log.
• Consistency proof: shared subtree roots → recompute both roots (past and current) → if both match, append-only is proven.
• Verification functions are fully independent — they work with only the root and the proof, no log required. Compatible with any RFC 6962 external verifier.
• Consistency proofs also catch tail truncation attacks.