Skip to main content

ruvector_retrieval_receipt/
lib.rs

1//! Witness-chained provenance receipts for ANN retrieval results.
2//!
3//! `ruvector-proof-gate` answers "what was written, and can I prove it
4//! hasn't been tampered with?" for the *write* path. This crate addresses
5//! the read path: it commits a query's result set to a receipt so that a
6//! receipt/result pair, once issued, cannot be silently mutated in transit
7//! or in storage without verification failing.
8//!
9//! # Threat model — read this before relying on the receipts
10//!
11//! Receipts are **unsigned commitments produced by the query engine
12//! itself**. What they do and do not guarantee:
13//!
14//! - They **detect post-issuance mutation** of a receipt/result pair. That
15//!   is the guarantee: an auditor holding the receipt can tell whether the
16//!   result set they were handed is the one the engine committed to.
17//! - They do **not** protect against a dishonest query engine. Leaves are
18//!   engine-chosen; nothing binds a leaf's `score` to an actual cosine
19//!   computation, or the committed k-set to the true top-k.
20//! - They do **not** prove write-chain membership. Each leaf commits to
21//!   *copies* of the `WriteReceipt`'s fields; verification never consults
22//!   the write gate, so mutating the ingestion history after a receipt is
23//!   issued leaves that receipt verifying. Binding each result to an
24//!   offline membership proof via `ruvector_proof_gate::MerkleGate`'s MMR
25//!   is the named future-work item that would make the write→read link
26//!   real.
27//!
28//! # Variants
29//!
30//! | Variant         | Per-query build cost | Evidence to verify 1 of k results | Guarantee |
31//! |-----------------|----------------------|-------------------------------------|-----------|
32//! | `NoReceipt`      | 0                    | none (unverifiable)                 | none |
33//! | `PerResultReceipt` | O(k) hashes        | O(idx) bytes, O(idx) work            | sequential tamper-evidence |
34//! | `MerkleReceipt`  | O(k) hashes          | O(log k) bytes, O(log k) work        | membership-proof tamper-evidence |
35//!
36//! # Signed anchoring (origin authentication)
37//!
38//! The variants above are all *unsigned*: they detect tamper but do not
39//! authenticate an issuing key. [`signing`] adds typed, scoped Ed25519
40//! anchoring on top of `PerResultReceipt`/`MerkleReceipt` roots, either
41//! per query ([`signing::Issuer::sign_root`]) or amortized across a batch
42//! of queries under one signature ([`signing::BatchAnchor`]). Binding a
43//! key to an organization remains the responsibility of an external key
44//! registry and revocation policy. See [`RetrievalReceipt::root`] and the
45//! `signing` module docs.
46//!
47//! # Independent state-root anchoring
48//!
49//! Signed receipt roots (above) authenticate what a *specific query*
50//! returned. [`state_anchor`] answers a decoupled question: has
51//! `index_state_root` itself ever been attested, independent of any query
52//! or receipt? See the module docs for the periodic-anchoring tradeoff this
53//! makes measurable.
54
55pub mod batch_fill;
56mod index;
57mod receipt;
58pub mod signing;
59pub mod state_anchor;
60
61pub use batch_fill::{BatchFillPolicy, BatchScheduler, PendingMember};
62pub use index::{synthetic_queries, ResultItem, RetrievalIndex};
63pub use receipt::{query_hash, MerkleReceipt, PerResultReceipt, ReceiptVariant};
64pub use signing::{
65    verify_root, AnchorContext, AnchorError, AnchorPurpose, BatchAnchor, Issuer, RootStatement,
66    SignedRoot, VerifiedRoot, SIGNED_ROOT_VERSION,
67};
68pub use state_anchor::{verify_state_anchor, StateAnchor, StateAnchorLog, StateAnchorPolicy};
69
70/// A built receipt for one query's result set, in whichever variant was
71/// requested. Carries enough state to answer `proof_bytes_for` /
72/// `verify_item` / `verify_full` uniformly across variants for benchmarking.
73pub enum RetrievalReceipt {
74    None,
75    PerResult(PerResultReceipt),
76    Merkle(MerkleReceipt),
77}
78
79impl RetrievalReceipt {
80    pub fn build(
81        variant: ReceiptVariant,
82        qh: [u8; 32],
83        index_root: [u8; 32],
84        results: &[ResultItem],
85    ) -> Self {
86        match variant {
87            ReceiptVariant::None => RetrievalReceipt::None,
88            ReceiptVariant::PerResult => {
89                RetrievalReceipt::PerResult(PerResultReceipt::build(qh, index_root, results))
90            }
91            ReceiptVariant::Merkle => {
92                RetrievalReceipt::Merkle(MerkleReceipt::build(qh, index_root, results))
93            }
94        }
95    }
96
97    pub fn variant(&self) -> ReceiptVariant {
98        match self {
99            RetrievalReceipt::None => ReceiptVariant::None,
100            RetrievalReceipt::PerResult(_) => ReceiptVariant::PerResult,
101            RetrievalReceipt::Merkle(_) => ReceiptVariant::Merkle,
102        }
103    }
104
105    /// The signable root for this receipt: `PerResult`'s chain head or
106    /// `Merkle`'s root. `None` has no root to sign — nothing was
107    /// committed, so nothing can be authenticated by a signature.
108    pub fn root(&self) -> Option<[u8; 32]> {
109        match self {
110            RetrievalReceipt::None => None,
111            RetrievalReceipt::PerResult(r) => Some(r.chain_head),
112            RetrievalReceipt::Merkle(r) => Some(r.root),
113        }
114    }
115
116    /// Bytes of evidence required to verify a single result at `idx`
117    /// without trusting a live index/gate instance. `None` returns `0` —
118    /// by construction there is nothing to verify, which is the point.
119    pub fn proof_bytes_for(&self, idx: usize) -> usize {
120        match self {
121            RetrievalReceipt::None => 0,
122            RetrievalReceipt::PerResult(r) => r.proof_bytes_for(idx),
123            RetrievalReceipt::Merkle(r) => r.proof_bytes_for(idx),
124        }
125    }
126
127    /// Total receipt payload size (all results), independent of which item
128    /// is later spot-checked.
129    pub fn total_bytes(&self) -> usize {
130        match self {
131            RetrievalReceipt::None => 0,
132            RetrievalReceipt::PerResult(r) => r.total_bytes(),
133            RetrievalReceipt::Merkle(r) => r.total_bytes(),
134        }
135    }
136
137    /// Verify a single result item. `NoReceipt` always returns `false`:
138    /// there is no evidence to check, which is intentional and distinct
139    /// from "verification passed."
140    pub fn verify_item(
141        &self,
142        idx: usize,
143        qh: [u8; 32],
144        index_root: [u8; 32],
145        item: &ResultItem,
146    ) -> bool {
147        match self {
148            RetrievalReceipt::None => false,
149            RetrievalReceipt::PerResult(r) => r.verify_item(idx, qh, index_root, item),
150            RetrievalReceipt::Merkle(r) => {
151                let proof = r.proof_for(idx);
152                r.verify_item(idx, qh, index_root, item, r.root, &proof)
153            }
154        }
155    }
156
157    /// Verify a complete result set against the receipt. Empty result sets
158    /// fail closed for every variant: "no evidence" must never be
159    /// reportable as "verified evidence".
160    pub fn verify_full(&self, qh: [u8; 32], index_root: [u8; 32], results: &[ResultItem]) -> bool {
161        match self {
162            RetrievalReceipt::None => false,
163            RetrievalReceipt::PerResult(r) => r.verify_full(qh, index_root, results),
164            RetrievalReceipt::Merkle(r) => r.verify_full(qh, index_root, results),
165        }
166    }
167}
168
169#[cfg(test)]
170mod tests {
171    use super::*;
172
173    fn setup(
174        n: usize,
175        dims: usize,
176        k: usize,
177    ) -> (
178        RetrievalIndex,
179        Vec<f32>,
180        Vec<ResultItem>,
181        [u8; 32],
182        [u8; 32],
183    ) {
184        let index = RetrievalIndex::ingest(n, dims, 0xC0FF_EE01);
185        let query = synthetic_queries(1, dims, 0xA5A5_5A5A)[0].clone();
186        let results = index.search(&query, k);
187        let qh = query_hash(&query);
188        let root = index.index_state_root();
189        (index, query, results, qh, root)
190    }
191
192    #[test]
193    fn ingestion_produces_verifiable_write_history() {
194        let (index, _, _, _, _) = setup(200, 16, 5);
195        assert!(index.verify_write_history());
196        assert_ne!(index.index_state_root(), [0u8; 32]);
197    }
198
199    #[test]
200    fn search_returns_k_results_in_descending_score_order() {
201        let (_, _, results, _, _) = setup(200, 16, 5);
202        assert_eq!(results.len(), 5);
203        for w in results.windows(2) {
204            assert!(w[0].score >= w[1].score);
205        }
206    }
207
208    #[test]
209    fn no_receipt_never_verifies() {
210        let (_, _, results, qh, root) = setup(100, 16, 4);
211        let receipt = RetrievalReceipt::build(ReceiptVariant::None, qh, root, &results);
212        assert_eq!(receipt.proof_bytes_for(0), 0);
213        assert!(!receipt.verify_item(0, qh, root, &results[0]));
214        assert!(!receipt.verify_full(qh, root, &results));
215    }
216
217    #[test]
218    fn per_result_receipt_verifies_honest_results() {
219        let (_, _, results, qh, root) = setup(500, 32, 10);
220        let receipt = RetrievalReceipt::build(ReceiptVariant::PerResult, qh, root, &results);
221        assert!(receipt.verify_full(qh, root, &results));
222        for (i, item) in results.iter().enumerate() {
223            assert!(receipt.verify_item(i, qh, root, item));
224        }
225    }
226
227    #[test]
228    fn merkle_receipt_verifies_honest_results() {
229        let (_, _, results, qh, root) = setup(500, 32, 10);
230        let receipt = RetrievalReceipt::build(ReceiptVariant::Merkle, qh, root, &results);
231        assert!(receipt.verify_full(qh, root, &results));
232        for (i, item) in results.iter().enumerate() {
233            assert!(receipt.verify_item(i, qh, root, item));
234        }
235    }
236
237    #[test]
238    fn per_result_receipt_detects_score_tamper() {
239        let (_, _, results, qh, root) = setup(300, 24, 8);
240        let receipt = RetrievalReceipt::build(ReceiptVariant::PerResult, qh, root, &results);
241        let mut tampered = results.clone();
242        tampered[3].score += 1.0;
243        assert!(!receipt.verify_item(3, qh, root, &tampered[3]));
244    }
245
246    #[test]
247    fn merkle_receipt_detects_score_tamper() {
248        let (_, _, results, qh, root) = setup(300, 24, 8);
249        let receipt = RetrievalReceipt::build(ReceiptVariant::Merkle, qh, root, &results);
250        let mut tampered = results.clone();
251        tampered[3].score += 1.0;
252        assert!(!receipt.verify_item(3, qh, root, &tampered[3]));
253    }
254
255    #[test]
256    fn per_result_receipt_detects_reorder() {
257        let (_, _, results, qh, root) = setup(300, 24, 8);
258        let receipt = RetrievalReceipt::build(ReceiptVariant::PerResult, qh, root, &results);
259        let mut tampered = results.clone();
260        tampered.swap(2, 5);
261        assert!(!receipt.verify_full(qh, root, &tampered));
262    }
263
264    #[test]
265    fn merkle_receipt_detects_reorder() {
266        let (_, _, results, qh, root) = setup(300, 24, 8);
267        let receipt = RetrievalReceipt::build(ReceiptVariant::Merkle, qh, root, &results);
268        let mut tampered = results.clone();
269        tampered.swap(2, 5);
270        assert!(!receipt.verify_full(qh, root, &tampered));
271    }
272
273    #[test]
274    fn merkle_receipt_detects_vector_id_substitution() {
275        let (index, query, results, qh, root) = setup(300, 24, 8);
276        let receipt = RetrievalReceipt::build(ReceiptVariant::Merkle, qh, root, &results);
277        // Substitute a truthful-looking but different vector's write receipt
278        // in place of result 0 — simulates an adversary swapping in evidence
279        // for a different, unretrieved memory.
280        let other = index.search(&query, 9)[8].clone();
281        let mut tampered = results.clone();
282        tampered[0] = other;
283        assert!(!receipt.verify_item(0, qh, root, &tampered[0]));
284    }
285
286    #[test]
287    fn merkle_proof_bytes_are_sublinear_vs_per_result_at_k10() {
288        let (_, _, results, qh, root) = setup(2000, 64, 10);
289        let per_result = RetrievalReceipt::build(ReceiptVariant::PerResult, qh, root, &results);
290        let merkle = RetrievalReceipt::build(ReceiptVariant::Merkle, qh, root, &results);
291        let worst_idx = results.len() - 1;
292        assert!(
293            merkle.proof_bytes_for(worst_idx) < per_result.proof_bytes_for(worst_idx),
294            "merkle worst-case proof ({} bytes) must be smaller than per-result worst-case ({} bytes)",
295            merkle.proof_bytes_for(worst_idx),
296            per_result.proof_bytes_for(worst_idx)
297        );
298    }
299
300    #[test]
301    fn index_state_root_changes_receipts_across_reingestion() {
302        let index_a = RetrievalIndex::ingest(50, 8, 1);
303        let index_b = RetrievalIndex::ingest(50, 8, 2);
304        assert_ne!(index_a.index_state_root(), index_b.index_state_root());
305    }
306
307    #[test]
308    fn empty_result_set_fails_closed_for_all_variants() {
309        let (_, _, _, qh, root) = setup(50, 8, 3);
310        let empty: Vec<ResultItem> = Vec::new();
311        for variant in [
312            ReceiptVariant::None,
313            ReceiptVariant::PerResult,
314            ReceiptVariant::Merkle,
315        ] {
316            let receipt = RetrievalReceipt::build(variant, qh, root, &empty);
317            assert!(
318                !receipt.verify_full(qh, root, &empty),
319                "{variant:?}: an empty result set must not verify vacuously"
320            );
321        }
322    }
323
324    #[test]
325    fn gate_variant_is_bound_into_the_leaf() {
326        use ruvector_proof_gate::GateVariant;
327        let (_, _, results, qh, root) = setup(100, 16, 4);
328        for variant in [ReceiptVariant::PerResult, ReceiptVariant::Merkle] {
329            let receipt = RetrievalReceipt::build(variant, qh, root, &results);
330            let mut tampered = results.clone();
331            // Same (copied) commitment/payload hashes, but claim they came
332            // from a NullGate: must not verify — otherwise an ungated
333            // all-zero receipt would be indistinguishable from a gated one.
334            tampered[0].write_receipt.gate_variant = GateVariant::Null;
335            assert!(!receipt.verify_item(0, qh, root, &tampered[0]));
336        }
337    }
338}