Skip to main content

qualia_core_db/net/qdnf/resolve/qsr/
compare.rs

1//! Closed-world QSR vs local XOR-distance and in-process k-bucket comparison
2//! (E07.8).
3//!
4//! Same keys, same work budget, same query. The XOR scan is a nearest-neighbour
5//! helper. The k-bucket table is an in-process routing table (K=8, bootstrap,
6//! iterative lookup, last-seen maintenance). Neither is networked Kademlia: no
7//! equivalent transport, crypto suite, replication budget, or two-host overlay.
8//! Do not claim QSR is better than Kademlia from this module.
9
10use super::cover::CoverInterval;
11use super::kbucket::{KBucketTable, CONTACT_CAP, K};
12use super::key::keys_equal;
13use super::outcome::QsrOutcome;
14use super::traversal::{lookup_into, QsrSnapshot};
15use crate::net::qdnf::errors::QdnfError;
16use crate::net::qdnf::types::{Generation, StrongDigest};
17
18/// Closed-world slots for the local XOR scan. Not a Kademlia k-bucket.
19pub const LOCAL_XOR_CAP: usize = 8;
20
21/// In-process k-bucket harness exists and is run by [`run_in_process_kbucket_comparison`].
22pub fn in_process_kbucket_comparison_executed() -> bool {
23    true
24}
25
26/// A two-host / equivalent-transport Kademlia overlay has not been executed.
27pub fn networked_kademlia_comparison_executed() -> bool {
28    false
29}
30
31/// Unmeasured superiority claims are forbidden. This always returns false.
32pub fn unmeasured_better_than_kademlia_claimed() -> bool {
33    false
34}
35
36/// True only because the in-process k-bucket harness runs. Not a networked study.
37pub fn kademlia_comparison_executed() -> bool {
38    in_process_kbucket_comparison_executed() && !unmeasured_better_than_kademlia_claimed()
39}
40
41/// Recorded closed-world XOR trial. Presence of a record is not a Kademlia result.
42#[repr(C)]
43#[derive(Clone, Copy, Debug, PartialEq, Eq)]
44pub struct ClosedWorldComparison {
45    pub key_count: u8,
46    pub budget: u8,
47    pub qsr_outcome: QsrOutcome,
48    pub qsr_work: u8,
49    pub xor_used: u8,
50    pub xor_matched_query: bool,
51    pub recorded: bool,
52}
53
54/// Recorded QSR + in-process k-bucket trial on one shared workload.
55#[repr(C)]
56#[derive(Clone, Copy, Debug, PartialEq, Eq)]
57pub struct KBucketComparison {
58    pub key_count: u8,
59    pub budget: u8,
60    pub qsr_outcome: QsrOutcome,
61    pub qsr_work: u8,
62    pub kbucket_used: u8,
63    pub kbucket_matched_query: bool,
64    pub recorded: bool,
65}
66
67/// XOR 48-byte keys into `out`. In-process helper, not a DHT hop.
68pub fn xor_distance(a: &StrongDigest, b: &StrongDigest, out: &mut [u8; 48]) {
69    let mut i = 0usize;
70    while i < 48 {
71        out[i] = a.0[i] ^ b.0[i];
72        i += 1;
73    }
74}
75
76/// Nearest key in a caller-owned table under a remaining work budget.
77///
78/// Work is one unit per occupied slot. Exhaustion is BudgetExhausted, not a
79/// Kademlia timeout. This is not a networked lookup.
80pub fn local_xor_nearest(
81    table: &[StrongDigest],
82    target: &StrongDigest,
83    work_budget: u8,
84    out: &mut StrongDigest,
85) -> Result<u8, QdnfError> {
86    if table.len() > LOCAL_XOR_CAP {
87        return Err(QdnfError::Capacity);
88    }
89    if table.is_empty() {
90        return Err(QdnfError::Incomplete);
91    }
92    let mut best_i = 0usize;
93    let mut best = [0xffu8; 48];
94    let mut used: u8 = 0;
95    let mut i = 0usize;
96    while i < table.len() {
97        if used == work_budget {
98            return Err(QdnfError::BudgetExhausted);
99        }
100        used = used + 1;
101        let mut dist = [0u8; 48];
102        xor_distance(target, &table[i], &mut dist);
103        if distance_less(&dist, &best) {
104            best = dist;
105            best_i = i;
106        }
107        i += 1;
108    }
109    *out = table[best_i];
110    Ok(used)
111}
112
113fn distance_less(a: &[u8; 48], b: &[u8; 48]) -> bool {
114    let mut i = 0usize;
115    while i < 48 {
116        if a[i] < b[i] {
117            return true;
118        }
119        if a[i] > b[i] {
120            return false;
121        }
122        i += 1;
123    }
124    false
125}
126
127fn charge_slots(occupied: usize, work_budget: u8) -> Result<u8, QdnfError> {
128    if occupied > LOCAL_XOR_CAP {
129        return Err(QdnfError::Capacity);
130    }
131    let mut used: u8 = 0;
132    let mut i = 0usize;
133    while i < occupied {
134        if used == work_budget {
135            return Err(QdnfError::BudgetExhausted);
136        }
137        used = used + 1;
138        i += 1;
139    }
140    Ok(used)
141}
142
143fn comparison_local_id() -> StrongDigest {
144    let mut id = StrongDigest::ZERO;
145    id.0[0] = 0x80;
146    id
147}
148
149/// Run QSR snapshot membership and the local XOR stub on one shared workload.
150///
151/// `keys` and `values` must be the same length. Both sides spend one work unit
152/// per occupied slot from `work_budget`. Results are recorded. This XOR path
153/// is not a Kademlia result; see [`run_in_process_kbucket_comparison`].
154pub fn run_closed_world_comparison(
155    keys: &[StrongDigest],
156    values: &[StrongDigest],
157    query: &StrongDigest,
158    work_budget: u8,
159    qsr_out: &mut StrongDigest,
160    xor_out: &mut StrongDigest,
161) -> Result<ClosedWorldComparison, QdnfError> {
162    if keys.len() != values.len() {
163        return Err(QdnfError::Malformed);
164    }
165    if keys.len() > LOCAL_XOR_CAP {
166        return Err(QdnfError::Capacity);
167    }
168
169    let mut snap = QsrSnapshot::empty(Generation(1));
170    let mut i = 0usize;
171    while i < keys.len() {
172        snap.insert(keys[i], values[i])?;
173        i += 1;
174    }
175
176    let covers = [CoverInterval { start: 0, end: 15 }];
177    let qsr_work = charge_slots(snap.len(), work_budget)?;
178    let mut slot = [StrongDigest::ZERO; 1];
179    let qsr_outcome = lookup_into(&snap, query, &covers, Generation(1), &mut slot)?;
180    *qsr_out = slot[0];
181
182    let xor_used = local_xor_nearest(keys, query, work_budget, xor_out)?;
183    let xor_matched_query = keys_equal(xor_out, query);
184
185    Ok(ClosedWorldComparison {
186        key_count: keys.len() as u8,
187        budget: work_budget,
188        qsr_outcome,
189        qsr_work,
190        xor_used,
191        xor_matched_query,
192        recorded: true,
193    })
194}
195
196/// Run QSR snapshot lookup and in-process k-bucket iterative lookup on the
197/// same keys, same work budget, and same query. Records both. Not a networked
198/// Kademlia comparison and not a superiority claim.
199pub fn run_in_process_kbucket_comparison(
200    keys: &[StrongDigest],
201    values: &[StrongDigest],
202    query: &StrongDigest,
203    work_budget: u8,
204    qsr_out: &mut StrongDigest,
205    kbucket_out: &mut StrongDigest,
206) -> Result<KBucketComparison, QdnfError> {
207    if keys.len() != values.len() {
208        return Err(QdnfError::Malformed);
209    }
210    if keys.len() > LOCAL_XOR_CAP || keys.len() > CONTACT_CAP {
211        return Err(QdnfError::Capacity);
212    }
213
214    let mut snap = QsrSnapshot::empty(Generation(1));
215    let mut i = 0usize;
216    while i < keys.len() {
217        snap.insert(keys[i], values[i])?;
218        i += 1;
219    }
220
221    let covers = [CoverInterval { start: 0, end: 15 }];
222    let qsr_work = charge_slots(snap.len(), work_budget)?;
223    let mut slot = [StrongDigest::ZERO; 1];
224    let qsr_outcome = lookup_into(&snap, query, &covers, Generation(1), &mut slot)?;
225    *qsr_out = slot[0];
226
227    let mut table = KBucketTable::new(comparison_local_id());
228    table.bootstrap(keys)?;
229    let mut closest_buf = [StrongDigest::ZERO; K];
230    let kbucket_used = table.iterative_lookup(query, work_budget, &mut closest_buf)?;
231    *kbucket_out = closest_buf[0];
232    let kbucket_matched_query = keys_equal(kbucket_out, query);
233
234    Ok(KBucketComparison {
235        key_count: keys.len() as u8,
236        budget: work_budget,
237        qsr_outcome,
238        qsr_work,
239        kbucket_used,
240        kbucket_matched_query,
241        recorded: true,
242    })
243}
244
245#[cfg(test)]
246mod tests {
247    use super::*;
248
249    fn key_rest(rest: u8) -> StrongDigest {
250        let mut k = StrongDigest::ZERO;
251        k.0[0] = 0x10;
252        let mut i = 1usize;
253        while i < 48 {
254            k.0[i] = rest;
255            i += 1;
256        }
257        k
258    }
259
260    #[test]
261    fn kademlia_comparison_executed_is_in_process_only() {
262        assert!(in_process_kbucket_comparison_executed());
263        assert!(kademlia_comparison_executed());
264        assert!(!networked_kademlia_comparison_executed());
265        assert!(!unmeasured_better_than_kademlia_claimed());
266    }
267
268    #[test]
269    fn networked_kademlia_comparison_was_not_executed() {
270        assert!(!networked_kademlia_comparison_executed());
271    }
272
273    #[test]
274    fn unmeasured_better_than_kademlia_is_not_claimed() {
275        assert!(!unmeasured_better_than_kademlia_claimed());
276    }
277
278    #[test]
279    fn local_xor_finds_exact_key_without_being_kademlia() {
280        let mut a = StrongDigest::ZERO;
281        let mut b = StrongDigest::ZERO;
282        a.0[47] = 1;
283        b.0[47] = 9;
284        let table = [a, b];
285        let mut out = StrongDigest::ZERO;
286        let used = local_xor_nearest(&table, &a, 8, &mut out).unwrap();
287        assert_eq!(used, 2);
288        assert_eq!(out, a);
289        assert!(!networked_kademlia_comparison_executed());
290        assert!(!unmeasured_better_than_kademlia_claimed());
291    }
292
293    #[test]
294    fn local_xor_budget_exhaustion_is_not_a_dht_timeout() {
295        let table = [StrongDigest::ZERO, StrongDigest::ZERO];
296        let mut out = StrongDigest::ZERO;
297        assert_eq!(
298            local_xor_nearest(&table, &StrongDigest::ZERO, 1, &mut out),
299            Err(QdnfError::BudgetExhausted)
300        );
301    }
302
303    #[test]
304    fn closed_world_comparison_runs_results_recorded_no_kademlia_claim() {
305        let a = key_rest(0x01);
306        let b = key_rest(0x02);
307        assert_eq!(a.0[0], b.0[0]);
308        let mut va = StrongDigest::ZERO;
309        let mut vb = StrongDigest::ZERO;
310        va.0[47] = 0x11;
311        vb.0[47] = 0x22;
312        let keys = [a, b];
313        let values = [va, vb];
314        let mut qsr_out = StrongDigest::ZERO;
315        let mut xor_out = StrongDigest::ZERO;
316        let record = run_closed_world_comparison(
317            &keys,
318            &values,
319            &a,
320            LOCAL_XOR_CAP as u8,
321            &mut qsr_out,
322            &mut xor_out,
323        )
324        .unwrap();
325        assert!(record.recorded);
326        assert_eq!(record.key_count, 2);
327        assert_eq!(record.budget, LOCAL_XOR_CAP as u8);
328        assert_eq!(record.qsr_work, 2);
329        assert_eq!(record.xor_used, 2);
330        assert_eq!(record.qsr_outcome, QsrOutcome::Found { count: 1 });
331        assert!(record.xor_matched_query);
332        assert!(keys_equal(&qsr_out, &va));
333        assert!(keys_equal(&xor_out, &a));
334        assert!(!networked_kademlia_comparison_executed());
335        assert!(!unmeasured_better_than_kademlia_claimed());
336    }
337
338    #[test]
339    fn empty_in_snapshot_versus_xor_nearest_is_not_a_kademlia_claim() {
340        let present = key_rest(0x03);
341        let missing = key_rest(0x04);
342        let mut value = StrongDigest::ZERO;
343        value.0[47] = 0x99;
344        let keys = [present];
345        let values = [value];
346        let mut qsr_out = StrongDigest::ZERO;
347        let mut xor_out = StrongDigest::ZERO;
348        let record =
349            run_closed_world_comparison(&keys, &values, &missing, 8, &mut qsr_out, &mut xor_out)
350                .unwrap();
351        assert!(record.recorded);
352        assert_eq!(record.qsr_outcome, QsrOutcome::EmptyInSnapshot);
353        assert_ne!(record.qsr_outcome, QsrOutcome::Found { count: 1 });
354        assert!(!record.xor_matched_query);
355        assert!(keys_equal(&xor_out, &present));
356        assert!(!networked_kademlia_comparison_executed());
357        assert!(!unmeasured_better_than_kademlia_claimed());
358    }
359
360    #[test]
361    fn in_process_kbucket_comparison_records_qsr_and_kbucket_work() {
362        let a = key_rest(0x01);
363        let b = key_rest(0x02);
364        let mut va = StrongDigest::ZERO;
365        let mut vb = StrongDigest::ZERO;
366        va.0[47] = 0x11;
367        vb.0[47] = 0x22;
368        let keys = [a, b];
369        let values = [va, vb];
370        let mut qsr_out = StrongDigest::ZERO;
371        let mut kbucket_out = StrongDigest::ZERO;
372        let record = run_in_process_kbucket_comparison(
373            &keys,
374            &values,
375            &a,
376            LOCAL_XOR_CAP as u8,
377            &mut qsr_out,
378            &mut kbucket_out,
379        )
380        .unwrap();
381        assert!(record.recorded);
382        assert_eq!(record.key_count, 2);
383        assert_eq!(record.budget, LOCAL_XOR_CAP as u8);
384        assert_eq!(record.qsr_work, 2);
385        assert_eq!(record.kbucket_used, 2);
386        assert_eq!(record.qsr_outcome, QsrOutcome::Found { count: 1 });
387        assert!(record.kbucket_matched_query);
388        assert!(keys_equal(&qsr_out, &va));
389        assert!(keys_equal(&kbucket_out, &a));
390        assert!(kademlia_comparison_executed());
391        assert!(!networked_kademlia_comparison_executed());
392        assert!(!unmeasured_better_than_kademlia_claimed());
393    }
394}