borg_mesh/
recon.rs

1//! Range-based set reconciliation of two hash sets: the cost grows with the difference, not with
2//! the history (the Negentropy / iroh-docs idea, in its simplest lock-step form).
3//!
4//! The hash space is split by nibbles into a 16-ary tree of ranges. Both sides hold the same list
5//! of *open* ranges and, per round, send a fingerprint (blake3 of the sorted hashes, and the count)
6//! of each. Equal ranges close. A differing range splits into its 16 children for the next round,
7//! unless either side holds at most `LEAF` hashes in it: then both send their hashes of that range
8//! and it closes. Both sides decide from the same two messages, so they stay in step without a
9//! leader. Nothing differs: one round of one fingerprint. `d` lines differ among `n`: about
10//! `log16(n / LEAF)` rounds, with at most `16·d` fingerprints and `LEAF·d` hashes per round.
11
12use std::collections::{BTreeMap, BTreeSet};
13
14use serde::{Deserialize, Serialize};
15
16use crate::lines::Hash;
17use crate::{from_hex, to_hex};
18
19/// At or below this many hashes in a differing range, the hashes themselves are exchanged. Method:
20/// trades rounds against message size (`log16(n / LEAF)` rounds, `LEAF·d` hashes per round); both
21/// sides must use the same value, so it is part of the protocol (borg/mesh/<version>).
22pub const LEAF: usize = 8;
23/// A peer that keeps claiming differences beyond this is broken or hostile. Guard: bounds the open
24/// ranges one session holds in memory (65 536, far past what two honest stores of a team differ by).
25const MAX_OPEN: usize = 1 << 16;
26
27#[derive(Debug, Clone, Copy, PartialEq, Eq)]
28struct Range {
29    lo: Hash,
30    /// Exclusive; `None` is the end of the hash space.
31    hi: Option<Hash>,
32    /// Nibbles fixed by `lo`.
33    depth: usize,
34}
35
36impl Range {
37    fn children(&self) -> Vec<Range> {
38        let (byte, shift) = (self.depth / 2, if self.depth.is_multiple_of(2) { 4 } else { 0 });
39        let with = |k: u8| {
40            let mut h = self.lo;
41            h[byte] |= k << shift;
42            h
43        };
44        (0..16u8).map(|k| Range { lo: with(k), hi: if k < 15 { Some(with(k + 1)) } else { self.hi }, depth: self.depth + 1 }).collect()
45    }
46
47    fn contains(&self, h: &Hash) -> bool {
48        *h >= self.lo && self.hi.is_none_or(|hi| *h < hi)
49    }
50}
51
52/// One round's message: fingerprints of the open ranges, hashes of the leaf ranges (both in the
53/// order both sides share).
54#[derive(Debug, Clone, Serialize, Deserialize)]
55pub struct Round {
56    pub fps: Vec<(String, u32)>,
57    pub leaves: Vec<Vec<String>>,
58}
59
60/// What one side exchanged: rounds, fingerprints and hashes it sent.
61#[derive(Debug, Default, Clone, Copy, PartialEq, Eq)]
62pub struct Cost {
63    pub rounds: usize,
64    pub fps: usize,
65    pub hashes: usize,
66}
67
68pub struct Recon<'a, V> {
69    set: &'a BTreeMap<Hash, V>,
70    open: Vec<Range>,
71    leaves: Vec<Range>,
72    /// Hashes the peer holds and this side lacks / this side holds and the peer lacks.
73    pub want: BTreeSet<Hash>,
74    pub give: BTreeSet<Hash>,
75    pub cost: Cost,
76}
77
78impl<'a, V> Recon<'a, V> {
79    pub fn new(set: &'a BTreeMap<Hash, V>) -> Self {
80        Recon {
81            set,
82            open: vec![Range { lo: [0; 32], hi: None, depth: 0 }],
83            leaves: Vec::new(),
84            want: BTreeSet::new(),
85            give: BTreeSet::new(),
86            cost: Cost::default(),
87        }
88    }
89
90    fn keys(&self, r: &Range) -> impl Iterator<Item = &Hash> {
91        let range = match r.hi {
92            Some(hi) => self.set.range(r.lo..hi),
93            None => self.set.range(r.lo..),
94        };
95        range.map(|(k, _)| k)
96    }
97
98    fn fingerprint(&self, r: &Range) -> (String, u32) {
99        let mut h = blake3::Hasher::new();
100        let mut n = 0u32;
101        for k in self.keys(r) {
102            h.update(k);
103            n += 1;
104        }
105        (if n == 0 { "0".into() } else { to_hex(h.finalize().as_bytes()) }, n)
106    }
107
108    /// This side's message for the current round.
109    pub fn message(&mut self) -> Round {
110        let fps: Vec<(String, u32)> = self.open.iter().map(|r| self.fingerprint(r)).collect();
111        let leaves: Vec<Vec<String>> = self.leaves.iter().map(|r| self.keys(r).map(|k| to_hex(k)).collect()).collect();
112        self.cost.rounds += 1;
113        self.cost.fps += fps.len();
114        self.cost.hashes += leaves.iter().map(Vec::len).sum::<usize>();
115        Round { fps, leaves }
116    }
117
118    /// Takes the peer's message for the round this side just sent; true once nothing is open.
119    pub fn absorb(&mut self, mine: &Round, theirs: Round) -> Result<bool, String> {
120        if theirs.fps.len() != self.open.len() || theirs.leaves.len() != self.leaves.len() {
121            return Err("reconciliation: peer is out of step".into());
122        }
123        for (r, hashes) in self.leaves.iter().zip(theirs.leaves) {
124            let theirs: BTreeSet<Hash> = hashes.iter().map(|h| from_hex::<32>(h)).collect::<Result<_, _>>()?;
125            if !theirs.iter().all(|h| r.contains(h)) {
126                return Err("reconciliation: peer sent a hash outside its range".into());
127            }
128            for k in self.keys(r).copied().collect::<Vec<_>>() {
129                if !theirs.contains(&k) {
130                    self.give.insert(k);
131                }
132            }
133            self.want.extend(theirs.into_iter().filter(|h| !self.set.contains_key(h)));
134        }
135        let (mut open, mut leaves) = (Vec::new(), Vec::new());
136        for ((r, my), their) in self.open.iter().zip(&mine.fps).zip(&theirs.fps) {
137            if my == their {
138                continue;
139            }
140            if (my.1 as usize) <= LEAF || (their.1 as usize) <= LEAF || r.depth >= 63 {
141                leaves.push(*r);
142            } else {
143                open.extend(r.children());
144            }
145        }
146        if open.len() > MAX_OPEN {
147            return Err("reconciliation: too many differing ranges".into());
148        }
149        (self.open, self.leaves) = (open, leaves);
150        Ok(self.open.is_empty() && self.leaves.is_empty())
151    }
152}
153
154#[cfg(test)]
155mod tests {
156    use super::*;
157
158    fn set(range: std::ops::Range<u32>) -> BTreeMap<Hash, ()> {
159        range.map(|i| (*blake3::hash(&i.to_le_bytes()).as_bytes(), ())).collect()
160    }
161
162    /// Runs both sides to the end; returns (a's want, a's give, a's cost + b's cost).
163    fn run(a: &BTreeMap<Hash, ()>, b: &BTreeMap<Hash, ()>) -> (BTreeSet<Hash>, BTreeSet<Hash>, Cost) {
164        let (mut ra, mut rb) = (Recon::new(a), Recon::new(b));
165        loop {
166            let (ma, mb) = (ra.message(), rb.message());
167            let da = ra.absorb(&ma, mb.clone()).unwrap();
168            let db = rb.absorb(&mb, ma).unwrap();
169            assert_eq!(da, db, "both sides stay in step");
170            if da {
171                break;
172            }
173        }
174        assert_eq!((&ra.want, &ra.give), (&rb.give, &rb.want));
175        let cost = Cost { rounds: ra.cost.rounds, fps: ra.cost.fps + rb.cost.fps, hashes: ra.cost.hashes + rb.cost.hashes };
176        (ra.want, ra.give, cost)
177    }
178
179    #[test]
180    fn equal_sets_cost_one_fingerprint() {
181        let a = set(0..5000);
182        let (want, give, cost) = run(&a, &a.clone());
183        assert!(want.is_empty() && give.is_empty());
184        assert_eq!(cost, Cost { rounds: 1, fps: 2, hashes: 0 });
185    }
186
187    #[test]
188    fn finds_exactly_the_difference_at_a_cost_bounded_by_it() {
189        let common = set(0..20_000);
190        let (mut a, mut b) = (common.clone(), common.clone());
191        a.extend(set(100_000..100_003));
192        b.extend(set(200_000..200_004));
193        let (want, give, cost) = run(&a, &b);
194        assert_eq!(want, set(200_000..200_004).into_keys().collect());
195        assert_eq!(give, set(100_000..100_003).into_keys().collect());
196        // 7 differences among 20k: a few rounds, hashes ≤ 2·LEAF·d, nowhere near 20k.
197        assert!(cost.hashes <= 2 * LEAF * 7 && cost.fps <= 2 * (1 + 16 * 7 * cost.rounds), "{cost:?}");
198        assert!(cost.rounds <= 6, "{cost:?}");
199    }
200
201    #[test]
202    fn one_side_empty_and_disjoint_small_sets() {
203        let a = set(0..5);
204        let (want, give, _) = run(&a, &BTreeMap::new());
205        assert_eq!((want.len(), give.len()), (0, 5));
206        let (want, give, _) = run(&set(0..300), &set(300..600));
207        assert_eq!((want.len(), give.len()), (300, 300));
208    }
209}
borg_mesh/recon.rs

borg_mesh/
recon.rs
