karyon_p2p/
bloom.rs

1use std::{hash::Hasher, sync::Arc};
2
3use bincode::{Decode, Encode};
4use parking_lot::RwLock;
5use siphasher::sip::SipHasher13;
6
7/// Shared handle to the local bloom. Readers snapshot via `*b.read()`;
8/// writers (`attach_protocol`, swarm joins, ...) update in place. Cheap
9/// to clone (Arc) and lock-free for short reads (parking_lot RwLock).
10pub type BloomRef = Arc<RwLock<Bloom>>;
11
12/// Two 128-bit bloom filters (k=2 hashes) bundled into one wire type.
13///
14/// `mandatory` holds items the local node REQUIRES peers to also support.
15///
16/// `optional` holds items the local node would LIKE peers to support
17/// but doesn't require.
18///
19/// Content-agnostic: items can be protocol ids, swarm keys, or any
20/// other identifier hashable as bytes. Discovery-layer hint, not
21#[derive(Encode, Decode, Clone, Copy, Debug, Default, PartialEq, Eq)]
22pub struct Bloom {
23    pub mandatory: u128,
24    pub optional: u128,
25}
26
27impl Bloom {
28    /// Empty filter.
29    pub fn empty() -> Self {
30        Self {
31            mandatory: 0,
32            optional: 0,
33        }
34    }
35
36    /// Insert a mandatory item.
37    pub fn add_mandatory<I: AsRef<[u8]>>(&mut self, item: I) {
38        let (a, b) = bit_indices(item.as_ref());
39        self.mandatory |= (1u128 << a) | (1u128 << b);
40    }
41
42    /// Insert an optional item.
43    pub fn add_optional<I: AsRef<[u8]>>(&mut self, item: I) {
44        let (a, b) = bit_indices(item.as_ref());
45        self.optional |= (1u128 << a) | (1u128 << b);
46    }
47
48    /// Union of mandatory + optional bits (every item the peer claims).
49    pub fn all(&self) -> u128 {
50        self.mandatory | self.optional
51    }
52
53    /// True if this filter might contain `item` in either set.
54    pub fn may_contain<I: AsRef<[u8]>>(&self, item: I) -> bool {
55        let (a, b) = bit_indices(item.as_ref());
56        let mask = (1u128 << a) | (1u128 << b);
57        (self.all() & mask) == mask
58    }
59
60    /// True if this peer's full set of items covers every bit in
61    /// `mine.mandatory`.
62    pub fn covers_mandatory(&self, mine: &Self) -> bool {
63        (self.all() & mine.mandatory) == mine.mandatory
64    }
65
66    /// True if this peer's full set of items shares at least one bit
67    /// with `mine.optional`. Trivially false if `mine.optional` is empty.
68    pub fn intersects_optional(&self, mine: &Self) -> bool {
69        (self.all() & mine.optional) != 0
70    }
71
72    /// True if neither mandatory nor optional has any bit set.
73    pub fn is_empty(&self) -> bool {
74        self.mandatory == 0 && self.optional == 0
75    }
76}
77
78/// Pick two bit positions in 0..128 from siphash-1-3(item). The two
79/// halves of the 64-bit output give the two bloom hashes.
80/// Fixed zero keys: the bloom is a public, deterministic identifier
81/// every peer must compute the same way - this is not a hash table
82/// where seed randomization helps.
83fn bit_indices(bytes: &[u8]) -> (u32, u32) {
84    let mut hasher = SipHasher13::new_with_keys(0, 0);
85    hasher.write(bytes);
86    let h = hasher.finish();
87    let a = (h as u32) % 128;
88    let b = ((h >> 32) as u32) % 128;
89    (a, b)
90}
91
92#[cfg(test)]
93mod tests {
94    use super::*;
95
96    #[test]
97    fn empty_filter_contains_nothing() {
98        let b = Bloom::empty();
99        assert!(b.is_empty());
100        assert!(!b.may_contain("X"));
101    }
102
103    #[test]
104    fn add_mandatory_then_contains() {
105        let mut b = Bloom::empty();
106        b.add_mandatory("ChatProto");
107        assert!(b.may_contain("ChatProto"));
108    }
109
110    #[test]
111    fn add_optional_then_contains() {
112        let mut b = Bloom::empty();
113        b.add_optional("ChatProto");
114        assert!(b.may_contain("ChatProto"));
115    }
116
117    #[test]
118    fn covers_mandatory_subset() {
119        let mut peer = Bloom::empty();
120        peer.add_optional("X");
121        peer.add_optional("Y");
122
123        let mut mine = Bloom::empty();
124        mine.add_mandatory("X");
125        assert!(peer.covers_mandatory(&mine));
126
127        mine.add_mandatory("Z");
128        assert!(!peer.covers_mandatory(&mine));
129    }
130
131    #[test]
132    fn intersects_optional_when_overlap() {
133        let mut peer = Bloom::empty();
134        peer.add_optional("Y");
135
136        let mut mine = Bloom::empty();
137        mine.add_optional("Y");
138        assert!(peer.intersects_optional(&mine));
139
140        let mut other = Bloom::empty();
141        other.add_optional("Q");
142        assert!(!peer.intersects_optional(&other));
143    }
144
145    #[test]
146    fn covers_mandatory_uses_union_of_peer_sets() {
147        let mut peer = Bloom::empty();
148        peer.add_mandatory("X");
149        peer.add_optional("Y");
150
151        let mut mine = Bloom::empty();
152        mine.add_mandatory("X");
153        mine.add_mandatory("Y");
154        assert!(peer.covers_mandatory(&mine));
155    }
156
157    #[test]
158    fn empty_mandatory_is_always_covered() {
159        let peer = Bloom::empty();
160        let mine = Bloom::empty();
161        assert!(peer.covers_mandatory(&mine));
162    }
163
164    #[test]
165    fn deterministic_across_instances() {
166        let mut a = Bloom::empty();
167        a.add_mandatory("SomeProto");
168        let mut b = Bloom::empty();
169        b.add_mandatory("SomeProto");
170        assert_eq!(a, b);
171    }
172}
karyon_p2p/bloom.rs

karyon_p2p/
bloom.rs
