Skip to main content

rustbinary/
ibl.rs

1//! Invertible Bloom Lookup Tables (IBLT) for set reconciliation.
2//!
3//! An IBLT encodes a set into a fixed-size array of cells. Two peers encode
4//! their sets, exchange the tables (or their difference), and one side
5//! subtracts and peels the difference to recover exactly the elements in
6//! `mine \ theirs` and `theirs \ mine`. Unlike delta frames, which assume an
7//! ordered stream and a shared baseline, IBLT reconciles **unordered sets**
8//! and needs only the difference table on the wire.
9//!
10//! This is a from-scratch implementation (Goodrich & Mitzenmacher, 2011) with
11//! three deterministic splitmix64 hash functions; it is `no_std` + `alloc` and
12//! has no external dependencies. The difference-set size must be small
13//! relative to the table size for decoding to complete; an undersized table
14//! reports [`Error::Iblt`] with `"decode incomplete"`.
15//!
16//! Combine IBLT with [`crate::delta`] to cover both unordered set diffs and
17//! ordered baseline-relative frames in one gossip layer.
18
19use alloc::vec;
20use alloc::vec::Vec;
21
22use crate::{Error, Result};
23
24/// Number of hash functions (cell positions per key).
25const HASH_COUNT: usize = 3;
26/// Seeds for the three cell-position hashes.
27const POSITION_SEEDS: [u64; HASH_COUNT] = [
28    0x9e37_79b9_7f4a_7c15,
29    0xbf58_476d_1ce4_e5b9,
30    0x94d0_49bb_1331_11eb,
31];
32
33/// Deterministic splitmix64: a strong, dependency-free integer hash.
34pub fn splitmix64(mut value: u64) -> u64 {
35    value = value.wrapping_add(0x9e37_79b9_7f4a_7c15);
36    value = (value ^ (value >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
37    value = (value ^ (value >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
38    value ^ (value >> 31)
39}
40
41/// One IBLT cell: an XOR-accumulating bucket.
42#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
43pub struct Cell {
44    /// Insertions minus deletions landing in this cell.
45    pub count: i32,
46    /// XOR of all keys landing in this cell.
47    pub key_sum: u64,
48    /// XOR of all values landing in this cell.
49    pub value_sum: u64,
50    /// XOR of all key hashes landing in this cell.
51    pub hash_sum: u64,
52}
53
54/// One recovered difference entry from [`Iblt::decode`].
55#[derive(Clone, Copy, Debug, Eq, PartialEq)]
56pub struct IbltEntry {
57    /// The key of the recovered element.
58    pub key: u64,
59    /// The associated value (an application payload for the key).
60    pub value: u64,
61    /// `true` if the element was in `self` but not the subtracted table.
62    pub present_in_self: bool,
63}
64
65/// Invertible Bloom Lookup Table.
66#[derive(Clone, Debug, Eq, PartialEq)]
67pub struct Iblt {
68    cells: Vec<Cell>,
69}
70
71impl Iblt {
72    /// Creates an empty table with `num_cells` cells.
73    ///
74    /// Decoding completes when the difference-set size is a small fraction of
75    /// `num_cells` (practically up to ~`num_cells / 3` differences with three
76    /// hash functions).
77    pub fn new(num_cells: usize) -> Self {
78        Self {
79            cells: vec![Cell::default(); num_cells.max(1)],
80        }
81    }
82
83    /// Number of cells in the table.
84    pub fn num_cells(&self) -> usize {
85        self.cells.len()
86    }
87
88    /// Number of cells with a non-zero count (an estimate of the set size).
89    pub fn occupied(&self) -> usize {
90        self.cells.iter().filter(|cell| cell.count != 0).count()
91    }
92
93    /// Whether every cell is empty.
94    pub fn is_empty(&self) -> bool {
95        self.cells.iter().all(|cell| cell.count == 0)
96    }
97
98    /// Inserts `(key, value)` into the table.
99    pub fn insert(&mut self, key: u64, value: u64) {
100        let hash = splitmix64(key);
101        for seed in POSITION_SEEDS {
102            let position = (splitmix64(key ^ seed) as usize) % self.cells.len();
103            let cell = &mut self.cells[position];
104            cell.count += 1;
105            cell.key_sum ^= key;
106            cell.value_sum ^= value;
107            cell.hash_sum ^= hash;
108        }
109    }
110
111    /// Deletes `(key, value)` from the table (must have been inserted).
112    pub fn delete(&mut self, key: u64, value: u64) {
113        let hash = splitmix64(key);
114        for seed in POSITION_SEEDS {
115            let position = (splitmix64(key ^ seed) as usize) % self.cells.len();
116            let cell = &mut self.cells[position];
117            cell.count -= 1;
118            cell.key_sum ^= key;
119            cell.value_sum ^= value;
120            cell.hash_sum ^= hash;
121        }
122    }
123
124    /// Subtracts `other` in place. Both tables must have the same size.
125    ///
126    /// The result encodes `self \ other` (positive cells) and `other \ self`
127    /// (negative cells) when `other` covers a disjoint difference set.
128    pub fn subtract(&mut self, other: &Iblt) -> Result<()> {
129        if self.cells.len() != other.cells.len() {
130            return Err(Error::Iblt("IBLT size mismatch in subtract"));
131        }
132        for (left, right) in self.cells.iter_mut().zip(&other.cells) {
133            left.count -= right.count;
134            left.key_sum ^= right.key_sum;
135            left.value_sum ^= right.value_sum;
136            left.hash_sum ^= right.hash_sum;
137        }
138        Ok(())
139    }
140
141    /// Peels the table and recovers the difference set.
142    ///
143    /// Returns the recovered entries, or an error when the table cannot be
144    /// fully decoded (too many differences for the table size, or a corrupt
145    /// cell whose hash does not verify).
146    pub fn decode(&self) -> Result<Vec<IbltEntry>> {
147        let mut table = self.clone();
148        let mut entries = Vec::new();
149        loop {
150            let mut progress = false;
151            for position in 0..table.cells.len() {
152                let count = table.cells[position].count;
153                if count == 1 || count == -1 {
154                    let key = table.cells[position].key_sum;
155                    let value = table.cells[position].value_sum;
156                    if splitmix64(key) != table.cells[position].hash_sum {
157                        return Err(Error::Iblt("IBLT cell hash does not verify"));
158                    }
159                    if count == 1 {
160                        table.delete(key, value);
161                        entries.push(IbltEntry {
162                            key,
163                            value,
164                            present_in_self: true,
165                        });
166                    } else {
167                        table.insert(key, value);
168                        entries.push(IbltEntry {
169                            key,
170                            value,
171                            present_in_self: false,
172                        });
173                    }
174                    progress = true;
175                    break;
176                }
177            }
178            if !progress {
179                break;
180            }
181        }
182        if !table.is_empty() {
183            return Err(Error::Iblt("IBLT decode incomplete (table too small?)"));
184        }
185        Ok(entries)
186    }
187
188    /// Returns the raw cells (for serialization over the wire).
189    pub fn cells(&self) -> &[Cell] {
190        &self.cells
191    }
192}
193
194/// Encodes a set of `(key, value)` pairs into a table of `num_cells` cells.
195pub fn encode_set(entries: &[(u64, u64)], num_cells: usize) -> Iblt {
196    let mut table = Iblt::new(num_cells);
197    for &(key, value) in entries {
198        table.insert(key, value);
199    }
200    table
201}
202
203/// Reconciles two tables and returns the difference set.
204///
205/// `mine` and `theirs` are expected to share a large common subset. The
206/// returned entries carry `present_in_self = true` for `mine \ theirs` and
207/// `false` for `theirs \ mine`.
208pub fn reconcile(mine: &Iblt, theirs: &Iblt) -> Result<Vec<IbltEntry>> {
209    let mut difference = mine.clone();
210    difference.subtract(theirs)?;
211    difference.decode()
212}
213
214#[cfg(test)]
215mod tests {
216    use super::*;
217
218    fn random_pairs(seed: u64, count: usize) -> Vec<(u64, u64)> {
219        let mut state = seed;
220        let mut pairs = Vec::with_capacity(count);
221        for index in 0..count {
222            state = splitmix64(state);
223            let key = state ^ (index as u64).wrapping_mul(0x9e37_79b9);
224            pairs.push((key, state.wrapping_mul(3) + index as u64));
225        }
226        pairs
227    }
228
229    #[test]
230    fn insert_delete_roundtrips_and_decodes_empty() {
231        let mut table = Iblt::new(16);
232        let pairs = random_pairs(0x1234, 8);
233        for &(key, value) in &pairs {
234            table.insert(key, value);
235        }
236        assert!(!table.is_empty());
237        for &(key, value) in &pairs {
238            table.delete(key, value);
239        }
240        assert!(table.is_empty());
241        assert_eq!(table.decode().unwrap(), Vec::new());
242    }
243
244    #[test]
245    fn reconcile_recovers_exact_difference() {
246        let common = random_pairs(0xabcd, 200);
247        let mut mine_set = common.clone();
248        mine_set.extend(random_pairs(0x1111, 10));
249        let mut theirs_set = common.clone();
250        theirs_set.extend(random_pairs(0x2222, 7));
251
252        let mine = encode_set(&mine_set, 256);
253        let theirs = encode_set(&theirs_set, 256);
254        let difference = reconcile(&mine, &theirs).unwrap();
255
256        let only_mine: Vec<(u64, u64)> = difference
257            .iter()
258            .filter(|entry| entry.present_in_self)
259            .map(|entry| (entry.key, entry.value))
260            .collect();
261        let only_theirs: Vec<(u64, u64)> = difference
262            .iter()
263            .filter(|entry| !entry.present_in_self)
264            .map(|entry| (entry.key, entry.value))
265            .collect();
266
267        let mut expected_mine = random_pairs(0x1111, 10);
268        expected_mine.sort_unstable();
269        let mut expected_theirs = random_pairs(0x2222, 7);
270        expected_theirs.sort_unstable();
271        let mut actual_mine = only_mine;
272        actual_mine.sort_unstable();
273        let mut actual_theirs = only_theirs;
274        actual_theirs.sort_unstable();
275        assert_eq!(actual_mine, expected_mine);
276        assert_eq!(actual_theirs, expected_theirs);
277    }
278
279    #[test]
280    fn undersized_table_reports_incomplete_decode() {
281        // 30 differences in an 8-cell table cannot be peeled.
282        let mine_set = random_pairs(0x3333, 30);
283        let theirs_set: Vec<(u64, u64)> = Vec::new();
284        let mine = encode_set(&mine_set, 8);
285        let theirs = encode_set(&theirs_set, 8);
286        assert!(matches!(
287            reconcile(&mine, &theirs),
288            Err(Error::Iblt("IBLT decode incomplete (table too small?)"))
289        ));
290    }
291
292    #[test]
293    fn identical_sets_reconcile_to_empty() {
294        let pairs = random_pairs(0x5555, 64);
295        let mine = encode_set(&pairs, 128);
296        let theirs = encode_set(&pairs, 128);
297        assert!(reconcile(&mine, &theirs).unwrap().is_empty());
298    }
299}