alloy_primitives/bits/
bloom.rs

1//! Bloom type.
2//!
3//! Adapted from <https://github.com/paritytech/parity-common/blob/2fb72eea96b6de4a085144ce239feb49da0cd39e/ethbloom/src/lib.rs>
4
5use crate::{Address, B256, Log, LogData, keccak256};
6
7/// Number of bits to set per input in Ethereum bloom filter.
8pub const BLOOM_BITS_PER_ITEM: usize = 3;
9/// Size of the bloom filter in bytes.
10pub const BLOOM_SIZE_BYTES: usize = 256;
11/// Size of the bloom filter in bits
12pub const BLOOM_SIZE_BITS: usize = BLOOM_SIZE_BYTES * 8;
13
14// BLOOM_SIZE_BYTES must be a power of 2
15#[allow(clippy::assertions_on_constants)]
16const _: () = assert!(BLOOM_SIZE_BYTES.is_power_of_two());
17
18/// Input to the [`Bloom::accrue`] method.
19#[derive(Clone, Copy, Debug)]
20pub enum BloomInput<'a> {
21    /// Raw input to be hashed.
22    Raw(&'a [u8]),
23    /// Already hashed input.
24    Hash(B256),
25}
26
27impl BloomInput<'_> {
28    /// Consume the input, converting it to the hash.
29    #[inline]
30    pub fn into_hash(self) -> B256 {
31        match self {
32            BloomInput::Raw(raw) => keccak256(raw),
33            BloomInput::Hash(hash) => hash,
34        }
35    }
36}
37
38impl From<BloomInput<'_>> for Bloom {
39    #[inline]
40    fn from(input: BloomInput<'_>) -> Self {
41        let mut bloom = Self::ZERO;
42        bloom.accrue(input);
43        bloom
44    }
45}
46
47wrap_fixed_bytes!(
48    /// Ethereum 256 byte bloom filter.
49    #[cfg_attr(feature = "rkyv", derive(rkyv::Archive, rkyv::Serialize, rkyv::Deserialize))]
50    #[cfg_attr(feature = "rkyv", rkyv(derive(Copy, Clone, Hash, PartialEq, Eq)))]
51    pub struct Bloom<256>;
52);
53
54impl<'a> FromIterator<&'a (Address, LogData)> for Bloom {
55    fn from_iter<T: IntoIterator<Item = &'a (Address, LogData)>>(iter: T) -> Self {
56        let mut bloom = Self::ZERO;
57        bloom.extend(iter);
58        bloom
59    }
60}
61
62impl<'a> Extend<&'a (Address, LogData)> for Bloom {
63    fn extend<T: IntoIterator<Item = &'a (Address, LogData)>>(&mut self, iter: T) {
64        for (address, log_data) in iter {
65            self.accrue_raw_log(*address, log_data.topics())
66        }
67    }
68}
69
70impl<'a> FromIterator<&'a Log> for Bloom {
71    #[inline]
72    fn from_iter<T: IntoIterator<Item = &'a Log>>(logs: T) -> Self {
73        let mut bloom = Self::ZERO;
74        bloom.extend(logs);
75        bloom
76    }
77}
78
79impl<'a> Extend<&'a Log> for Bloom {
80    #[inline]
81    fn extend<T: IntoIterator<Item = &'a Log>>(&mut self, logs: T) {
82        for log in logs {
83            self.accrue_log(log)
84        }
85    }
86}
87
88impl<'a, 'b> FromIterator<&'a BloomInput<'b>> for Bloom {
89    #[inline]
90    fn from_iter<T: IntoIterator<Item = &'a BloomInput<'b>>>(inputs: T) -> Self {
91        let mut bloom = Self::ZERO;
92        bloom.extend(inputs);
93        bloom
94    }
95}
96
97impl<'a, 'b> Extend<&'a BloomInput<'b>> for Bloom {
98    #[inline]
99    fn extend<T: IntoIterator<Item = &'a BloomInput<'b>>>(&mut self, inputs: T) {
100        for input in inputs {
101            self.accrue(*input);
102        }
103    }
104}
105
106impl Bloom {
107    /// Returns a reference to the underlying data.
108    #[inline]
109    pub const fn data(&self) -> &[u8; BLOOM_SIZE_BYTES] {
110        &self.0.0
111    }
112
113    /// Returns a mutable reference to the underlying data.
114    #[inline]
115    pub const fn data_mut(&mut self) -> &mut [u8; BLOOM_SIZE_BYTES] {
116        &mut self.0.0
117    }
118
119    /// Returns true if this bloom filter is a possible superset of the other
120    /// bloom filter, admitting false positives.
121    ///
122    /// Note: This method may return false positives. This is inherent to the
123    /// bloom filter data structure.
124    #[inline]
125    pub fn contains_input(&self, input: BloomInput<'_>) -> bool {
126        let hash = input.into_hash();
127        self.contains_m3_2048_hashed(&hash)
128    }
129
130    /// Compile-time version of [`contains`](Self::contains).
131    ///
132    /// Note: This method may return false positives. This is inherent to the
133    /// bloom filter data structure.
134    pub const fn const_contains(self, other: Self) -> bool {
135        self.0.const_covers(other.0)
136    }
137
138    /// Returns true if this bloom filter is a possible superset of the other
139    /// bloom filter, admitting false positives.
140    ///
141    /// Note: This method may return false positives. This is inherent to the
142    /// bloom filter data structure.
143    pub fn contains(&self, other: &Self) -> bool {
144        self.0.covers(&other.0)
145    }
146
147    /// Accrues the input into the bloom filter.
148    pub fn accrue(&mut self, input: BloomInput<'_>) {
149        let hash = input.into_hash();
150        self.m3_2048_hashed(&hash);
151    }
152
153    /// Accrues the input into the bloom filter.
154    pub fn accrue_bloom(&mut self, bloom: &Self) {
155        *self |= *bloom;
156    }
157
158    /// Specialised Bloom filter that sets three bits out of 2048, given an
159    /// arbitrary byte sequence.
160    ///
161    /// See Section 4.3.1 "Transaction Receipt" of the
162    /// [Ethereum Yellow Paper][ref] (page 6).
163    ///
164    /// [ref]: https://ethereum.github.io/yellowpaper/paper.pdf
165    pub fn m3_2048(&mut self, bytes: &[u8]) {
166        self.m3_2048_hashed(&keccak256(bytes));
167    }
168
169    /// [`m3_2048`](Self::m3_2048) but with a pre-hashed input.
170    pub fn m3_2048_hashed(&mut self, hash: &B256) {
171        for i in [0, 2, 4] {
172            let bit = (hash[i + 1] as usize + ((hash[i] as usize) << 8)) & 0x7FF;
173            self[BLOOM_SIZE_BYTES - 1 - bit / 8] |= 1 << (bit % 8);
174        }
175    }
176
177    /// Returns true if this bloom filter contains the bits set by [`m3_2048`](Self::m3_2048).
178    fn contains_m3_2048(&self, bytes: &[u8]) -> bool {
179        self.contains_m3_2048_hashed(&keccak256(bytes))
180    }
181
182    /// [`contains_m3_2048`](Self::contains_m3_2048) but with a pre-hashed input.
183    fn contains_m3_2048_hashed(&self, hash: &B256) -> bool {
184        for i in [0, 2, 4] {
185            // Each adjacent hash byte pair forms one big-endian 11-bit index.
186            // Bloom bytes are stored high-to-low, while bits within a byte are low-to-high.
187            let bit = (hash[i + 1] as usize + ((hash[i] as usize) << 8)) & 0x7FF;
188            if self[BLOOM_SIZE_BYTES - 1 - bit / 8] & (1 << (bit % 8)) == 0 {
189                return false;
190            }
191        }
192        true
193    }
194
195    /// Ingests a raw log into the bloom filter.
196    pub fn accrue_raw_log(&mut self, address: Address, topics: &[B256]) {
197        self.m3_2048(address.as_slice());
198        for topic in topics.iter() {
199            self.m3_2048(topic.as_slice());
200        }
201    }
202
203    /// Ingests a log into the bloom filter.
204    pub fn accrue_log(&mut self, log: &Log) {
205        self.accrue_raw_log(log.address, log.topics())
206    }
207
208    /// Ingests multiple logs into the bloom filter.
209    pub fn accrue_logs(&mut self, logs: &[Log]) {
210        for log in logs {
211            self.accrue_log(log)
212        }
213    }
214
215    /// True if the bloom filter contains a log with given address and topics.
216    ///
217    /// Note: This method may return false positives. This is inherent to the
218    /// bloom filter data structure.
219    pub fn contains_raw_log(&self, address: Address, topics: &[B256]) -> bool {
220        self.contains_m3_2048(address.as_slice())
221            && topics.iter().all(|topic| self.contains_m3_2048(topic.as_slice()))
222    }
223
224    /// True if the bloom filter contains a log with given address and topics.
225    ///
226    /// Note: This method may return false positives. This is inherent to the
227    /// bloom filter data structure.
228    pub fn contains_log(&self, log: &Log) -> bool {
229        self.contains_raw_log(log.address, log.topics())
230    }
231}
232
233#[cfg(test)]
234mod tests {
235    use super::*;
236    use crate::hex;
237
238    #[test]
239    fn works() {
240        let bloom = bloom!(
241            "00000000000000000000000000000000
242             00000000100000000000000000000000
243             00000000000000000000000000000000
244             00000000000000000000000000000000
245             00000000000000000000000000000000
246             00000000000000000000000000000000
247             00000002020000000000000000000000
248             00000000000000000000000800000000
249             10000000000000000000000000000000
250             00000000000000000000001000000000
251             00000000000000000000000000000000
252             00000000000000000000000000000000
253             00000000000000000000000000000000
254             00000000000000000000000000000000
255             00000000000000000000000000000000
256             00000000000000000000000000000000"
257        );
258        let address = hex!("ef2d6d194084c2de36e0dabfce45d046b37d1106");
259        let topic = hex!("02c69be41d0b7e40352fc85be1cd65eb03d40ef8427a0ca4596b1ead9a00e9fc");
260        let address_hash = keccak256(address);
261        let topic_hash = keccak256(topic);
262
263        let mut my_bloom = Bloom::default();
264        assert!(!my_bloom.contains_input(BloomInput::Raw(&address)));
265        assert!(!my_bloom.contains_input(BloomInput::Raw(&topic)));
266        assert!(!my_bloom.contains_input(BloomInput::Hash(address_hash)));
267        assert!(!my_bloom.contains_input(BloomInput::Hash(topic_hash)));
268
269        my_bloom.accrue(BloomInput::Raw(&address));
270        assert!(my_bloom.contains_input(BloomInput::Raw(&address)));
271        assert!(!my_bloom.contains_input(BloomInput::Raw(&topic)));
272        assert!(my_bloom.contains_input(BloomInput::Hash(address_hash)));
273        assert!(!my_bloom.contains_input(BloomInput::Hash(topic_hash)));
274
275        my_bloom.accrue(BloomInput::Raw(&topic));
276        assert!(my_bloom.contains_input(BloomInput::Raw(&address)));
277        assert!(my_bloom.contains_input(BloomInput::Raw(&topic)));
278        assert!(my_bloom.contains_input(BloomInput::Hash(address_hash)));
279        assert!(my_bloom.contains_input(BloomInput::Hash(topic_hash)));
280
281        assert_eq!(my_bloom, bloom);
282    }
283
284    #[test]
285    #[cfg(feature = "arbitrary")]
286    #[cfg_attr(miri, ignore = "proptest is too slow under miri")]
287    fn contains_raw_log_matches_bloom_contains() {
288        use proptest::{arbitrary::any, collection::vec};
289
290        fn contains_via_bloom(bloom: &Bloom, address: Address, topics: &[B256]) -> bool {
291            let mut log_bloom = Bloom::default();
292            log_bloom.accrue_raw_log(address, topics);
293            bloom.contains(&log_bloom)
294        }
295
296        proptest::proptest!(|(bloom: Bloom, address: Address, topics in vec(any::<B256>(), 0..8))| {
297            proptest::prop_assert_eq!(
298                bloom.contains_raw_log(address, &topics),
299                contains_via_bloom(&bloom, address, &topics)
300            );
301        });
302    }
303}
alloy_primitives/bits/bloom.rs

alloy_primitives/bits/
bloom.rs
