hopr_protocol_hopr/
tbf.rs

1use hopr_api::types::{crypto::types::PacketTag, crypto_random::random_bytes};
2
3/// Bloom filter for packet tags to detect packet replays.
4///
5/// In addition, this structure also holds the number of items in the filter
6/// to determine if the filter needs to be refreshed. Once this happens, packet replays
7/// of past packets might be possible.
8#[derive(Debug)]
9pub struct TagBloomFilter {
10    bloom: bloomfilter::Bloom<PacketTag>,
11    count: usize,
12    capacity: usize,
13}
14
15impl TagBloomFilter {
16    // The default maximum number of packet tags this Bloom filter can hold.
17    // After these many packets, the Bloom filter resets and packet replays are possible.
18    const DEFAULT_MAX_ITEMS: usize = 10_000_000;
19    // Allowed false positive rate. This amounts to 0.001% chance
20    const FALSE_POSITIVE_RATE: f64 = 0.00001_f64;
21
22    /// Returns the current number of items in this Bloom filter.
23    #[allow(dead_code)]
24    pub fn count(&self) -> usize {
25        self.count
26    }
27
28    pub fn capacity(&self) -> usize {
29        self.capacity
30    }
31
32    /// Puts a packet tag into the Bloom filter
33    pub fn set(&mut self, tag: &PacketTag) {
34        if self.count == self.capacity {
35            tracing::warn!("maximum number of items in the Bloom filter reached!");
36            self.bloom.clear();
37            self.count = 0;
38        }
39
40        self.bloom.set(tag);
41        self.count += 1;
42    }
43
44    /// Check if the packet tag is in the Bloom filter.
45    ///
46    /// Returns `true` if the given `tag` was already present in the filter.
47    /// False positives are possible.
48    pub fn check(&self, tag: &PacketTag) -> bool {
49        self.bloom.check(tag)
50    }
51
52    /// Checks and sets a packet tag (if not present) in a single operation.
53    ///
54    /// Returns `true` if the given `tag` was already present in the filter.
55    /// False positives are possible.
56    #[allow(dead_code)]
57    pub fn check_and_set(&mut self, tag: &PacketTag) -> bool {
58        // If we're at full capacity, we do only "check" and conditionally reset with the new entry
59        if self.count == self.capacity {
60            let is_present = self.bloom.check(tag);
61            if !is_present {
62                // There cannot be false negatives, so we can reset the filter
63                tracing::warn!("maximum number of items in the Bloom filter reached!");
64                self.bloom.clear();
65                self.bloom.set(tag);
66                self.count = 1;
67            }
68            is_present
69        } else {
70            // If not at full capacity, we can do check_and_set
71            let was_present = self.bloom.check_and_set(tag);
72            if !was_present {
73                self.count += 1;
74            }
75            was_present
76        }
77    }
78
79    fn with_capacity(size: usize) -> Self {
80        Self {
81            bloom: bloomfilter::Bloom::new_for_fp_rate_with_seed(size, Self::FALSE_POSITIVE_RATE, &random_bytes())
82                .expect("bloom filter with the specified capacity is constructible"),
83            count: 0,
84            capacity: size,
85        }
86    }
87}
88
89impl Default for TagBloomFilter {
90    fn default() -> Self {
91        Self::with_capacity(Self::DEFAULT_MAX_ITEMS)
92    }
93}
94
95#[cfg(test)]
96mod tests {
97    use hopr_api::types::crypto::types::PACKET_TAG_LENGTH;
98
99    #[allow(unused_imports)]
100    use super::*;
101
102    #[allow(dead_code)]
103    const ZEROS_TAG: [u8; PACKET_TAG_LENGTH] = [0; PACKET_TAG_LENGTH];
104    #[allow(dead_code)]
105    const ONES_TAG: [u8; PACKET_TAG_LENGTH] = [1; PACKET_TAG_LENGTH];
106
107    #[test]
108    fn tag_bloom_filter_count() {
109        let mut filter = TagBloomFilter::default();
110        assert!(!filter.check_and_set(&ZEROS_TAG));
111        assert_eq!(1, filter.count());
112
113        assert!(filter.check_and_set(&ZEROS_TAG));
114        assert_eq!(1, filter.count());
115
116        assert!(!filter.check_and_set(&ONES_TAG));
117        assert_eq!(2, filter.count());
118
119        assert!(filter.check_and_set(&ZEROS_TAG));
120        assert_eq!(2, filter.count());
121    }
122
123    #[test]
124    fn tag_bloom_filter_wrap_around() {
125        let mut filter = TagBloomFilter::with_capacity(1000);
126        for _ in 1..filter.capacity() {
127            let mut tag: PacketTag = hopr_api::types::crypto_random::random_bytes();
128            tag[0] = 0xaa; // ensure it's not all zeroes
129            assert!(!filter.check_and_set(&tag));
130        }
131        // Not yet at full capacity
132        assert_eq!(filter.capacity() - 1, filter.count());
133
134        // This entry is not there yet
135        assert!(!filter.check_and_set(&ZEROS_TAG));
136
137        // Now the filter is at capacity and contains the previously inserted entry
138        assert_eq!(filter.capacity(), filter.count());
139        assert!(filter.check(&ZEROS_TAG));
140
141        // This will not clear out the filter, since the entry is there
142        assert!(filter.check_and_set(&ZEROS_TAG));
143        assert_eq!(filter.capacity(), filter.count());
144
145        // This will clear out the filter, since this other entry is definitely not there
146        assert!(!filter.check_and_set(&ONES_TAG));
147        assert_eq!(1, filter.count());
148        assert!(filter.check(&ONES_TAG));
149    }
150
151    #[test]
152    fn tag_bloom_filter_set_method() {
153        let mut filter = TagBloomFilter::with_capacity(2);
154        filter.set(&ZEROS_TAG);
155        assert_eq!(1, filter.count());
156        assert!(filter.check(&ZEROS_TAG));
157
158        filter.set(&ONES_TAG);
159        assert_eq!(2, filter.count());
160        assert!(filter.check(&ONES_TAG));
161
162        // This should trigger reset
163        let another_tag: PacketTag = [0x42; PACKET_TAG_LENGTH];
164        filter.set(&another_tag);
165        assert_eq!(1, filter.count());
166        assert!(filter.check(&another_tag));
167        // Bloom filter might still have other tags due to nature of bloom filter,
168        // but it was cleared, so for a small capacity they should likely be gone
169        // (unless there is a collision).
170    }
171}
hopr_protocol_hopr/tbf.rs

hopr_protocol_hopr/
tbf.rs
