MerkleProof & ProofPath Inclusion Proofs

ELI5

A receipt from a tamper-evident binder: to prove your document is in the binder without shipping the whole binder, the librarian gives you your page’s fingerprint plus the fingerprints of its neighbouring pages at each level. Anyone can combine them up the tree and check if the result matches the binder’s sealed cover hash.

Technical Deep Dive

MerkleProof

MerkleProof (src/proof.rs) bundles a leaf hash, a sibling path, and a tree depth:

verify() returns true iff !leaf_hash.is_empty() && leaf_hash.len() == 32 && tree_depth > 0. It does not recompute the root or compare against a trusted root hash.

from_entry(entry) calls hash_entry(entry) (XOR fold over op_id bytes and data bytes) then ProofPath::from_hash(&leaf_hash).

compute_root() XOR-folds each sibling hash into leaf_hash to produce a 32-byte root.

ProofPath

ProofPath stores siblings: Vec<Vec<u8>> and indices: Vec<u32>.

from_hash(leaf_hash) generates exactly 5 siblings via a loop:

for i in 0..5 {
    let mut sibling = hash.clone();
    for byte in &mut sibling { *byte ^= (i as u8); }
    siblings.push(sibling);
    hash = Self::hash_pair(&hash, &siblings[i]);
}

This means every MerkleProof::from_entry produces a path of length 5, regardless of actual tree size. tree_depth is always set to 1 by from_entry.

Root Computation Flow

flowchart LR
    A["leaf_hash 32B"] --> B{"for each sibling"}
    B --> C["root[i%32] ^= sibling[i]"]
    C --> B
    B --> D["root 32B"]

Wire Protocol (vest.proto)

The proto MerkleProof message adds production fields absent from the Rust struct:

• tree_id, tree_type (LOG/MAP/HYBRID), leaf_index, tree_size
• SignedTreeHead — signed Merkle checkpoint (RFC 6962)
• ConsistencyProof — prove log only grew (no entries removed)

The Rust struct is the development skeleton; the proto is the full compliance-grade design.

Key Terms

• leaf_hash → 32-byte XOR fingerprint of op_id + data; leaf of the Merkle tree
• ProofPath → list of sibling hashes; length = log₂(N) in a balanced tree; always 5 here
• compute_root → XOR combination of leaf_hash with all sibling hashes
• SignedTreeHead (STH) → RFC 6962 signed checkpoint; root hash + tree size + signature
• ConsistencyProof → proves two STHs are consistent (log only appended, never modified)

Q&A

Q: If two operations produce identical op_id and data, will their MerkleProof::leaf_hash values be identical? A: Yes — hash_entry is deterministic over op_id and data bytes; identical inputs yield identical leaf hashes.

Q: Does ProofPath::verify() check that sibling hashes are 32 bytes? A: No. It only checks !siblings.is_empty() && siblings.len() == indices.len().

Q: What tree size is represented by a ProofPath with 5 siblings? A: In a balanced binary tree, 5 siblings supports up to 2⁵ = 32 leaves. But from_hash always generates 5 siblings regardless of actual log size — this is a fixed-depth simplification, not RFC 6962 production behaviour.

Examples

Creating and verifying a proof for an operation:

let mut vest = VestProtocol::new();
vest.audit_operation("op42", b"payload".to_vec(), AuditSignature::default()).unwrap();
let proof = vest.create_proof("op42").unwrap();

assert!(proof.verify());              // leaf_hash 32B, tree_depth=1
assert_eq!(proof.path.length(), 5);  // always 5 siblings from from_hash
let root = proof.compute_root();      // 32-byte combined root
assert_eq!(root.len(), 32);