BitcoinPIR
Contents 09 Merkle for inclusion AND exclusion

Merkle proofs — for inclusion AND exclusion

A PIR response is just bytes. How does the client know the server didn't lie and hand back a fake bin? BitcoinPIR publishes a Merkle root over the entire cuckoo-table dataset. Every response is verified against this public commitment by fetching the siblings along the path from the returned bin up to the root — where "the siblings" are themselves PIR-queried so the server still can't tell which bin you were actually verifying.

The tree depth is log₂(num_leaves). At UTXO-set scale, that's around 25 levels for the INDEX table — which translates to 25 sibling PIR queries, one per level, all padded: 

// pir-core/src/merkle.rs:165
let depth = (num_leaves as f64).log2() as usize;

The "not found" case — why it's harder than "found"

Proving a scripthash is in the database is easy: the client finds the matching tag inside the returned bin and shows the Merkle path. Proving it isn't is trickier. An empty slot could be genuinely empty — or a lying server could have quietly omitted Alice's item. So the client must check both in-group cuckoo positions (INDEX_CUCKOO_NUM_HASHES = 2), Merkle-verify each bin's contents against the public root, and only then conclude absence.

FOUND — verify h₀ bin root found one path · one proof · done NOT FOUND — verify h₀ AND h₁ bins root h₀ empty h₁ empty both paths · both proofs · then absent The rule, in one line: INDEX_CUCKOO_NUM_HASHES = 2 means every "not found" answer must carry 2 Merkle-verified empty bins. Verifying just one empty bin is not enough: the item could still be sitting in the other bin. A lying server can't fake a bin, because the bin's hash has to match the public Merkle root.
Inclusion: one bin found, one Merkle path. Exclusion: both candidate bins empty, both Merkle-verified — only then is 'not found' sound.