bellscoin/
bip158.rs

1// SPDX-License-Identifier: CC0-1.0
2
3// This module was largely copied from https://github.com/rust-bitcoin/murmel/blob/master/src/blockfilter.rs
4// on 11. June 2019 which is licensed under Apache, that file specifically
5// was written entirely by Tamas Blummer, who is re-licensing its contents here as CC0.
6
7//! BIP 158 Compact Block Filters for Light Clients.
8//!
9//! This module implements a structure for compact filters on block data, for
10//! use in the BIP 157 light client protocol. The filter construction proposed
11//! is an alternative to Bloom filters, as used in BIP 37, that minimizes filter
12//! size by using Golomb-Rice coding for compression.
13//!
14//! ### Relevant BIPS
15//!
16//! * [BIP 157 - Client Side Block Filtering](https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki)
17//! * [BIP 158 - Compact Block Filters for Light Clients](https://github.com/bitcoin/bips/blob/master/bip-0158.mediawiki)
18//!
19//! # Examples
20//!
21//! ```ignore
22//! fn get_script_for_coin(coin: &OutPoint) -> Result<ScriptBuf, BlockFilterError> {
23//!   // get utxo ...
24//! }
25//!
26//! // create a block filter for a block (server side)
27//! let filter = BlockFilter::new_script_filter(&block, get_script_for_coin)?;
28//!
29//! // or create a filter from known raw data
30//! let filter = BlockFilter::new(content);
31//!
32//! // read and evaluate a filter
33//!
34//! let query: Iterator<Item=ScriptBuf> = // .. some scripts you care about
35//! if filter.match_any(&block_hash, &mut query.map(|s| s.as_bytes())) {
36//!   // get this block
37//! }
38//!  ```
39//!
40
41use core::cmp::{self, Ordering};
42use core::convert::TryInto;
43use core::fmt::{self, Display, Formatter};
44
45use hashes::{siphash24, Hash};
46use internals::write_err;
47
48use crate::blockdata::block::Block;
49use crate::blockdata::script::Script;
50use crate::blockdata::transaction::OutPoint;
51use crate::consensus::encode::VarInt;
52use crate::consensus::{Decodable, Encodable};
53use crate::hash_types::{BlockHash, FilterHash, FilterHeader};
54use crate::io;
55use crate::prelude::*;
56
57/// Golomb encoding parameter as in BIP-158, see also https://gist.github.com/sipa/576d5f09c3b86c3b1b75598d799fc845
58const P: u8 = 19;
59const M: u64 = 784931;
60
61/// Errors for blockfilter.
62#[derive(Debug)]
63#[non_exhaustive]
64pub enum Error {
65    /// Missing UTXO, cannot calculate script filter.
66    UtxoMissing(OutPoint),
67    /// IO error reading or writing binary serialization of the filter.
68    Io(io::Error),
69}
70
71impl Display for Error {
72    fn fmt(&self, f: &mut Formatter) -> Result<(), fmt::Error> {
73        use Error::*;
74
75        match *self {
76            UtxoMissing(ref coin) => write!(f, "unresolved UTXO {}", coin),
77            Io(ref e) => write_err!(f, "IO error"; e),
78        }
79    }
80}
81
82#[cfg(feature = "std")]
83impl std::error::Error for Error {
84    fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
85        use Error::*;
86
87        match *self {
88            UtxoMissing(_) => None,
89            Io(ref e) => Some(e),
90        }
91    }
92}
93
94impl From<io::Error> for Error {
95    fn from(io: io::Error) -> Self {
96        Error::Io(io)
97    }
98}
99
100/// A block filter, as described by BIP 158.
101#[derive(Debug, Clone, PartialEq, Eq)]
102pub struct BlockFilter {
103    /// Golomb encoded filter
104    pub content: Vec<u8>,
105}
106
107impl FilterHash {
108    /// Computes the filter header from a filter hash and previous filter header.
109    pub fn filter_header(&self, previous_filter_header: &FilterHeader) -> FilterHeader {
110        let mut header_data = [0u8; 64];
111        header_data[0..32].copy_from_slice(&self[..]);
112        header_data[32..64].copy_from_slice(&previous_filter_header[..]);
113        FilterHeader::hash(&header_data)
114    }
115}
116
117impl BlockFilter {
118    /// Creates a new filter from pre-computed data.
119    pub fn new(content: &[u8]) -> BlockFilter {
120        BlockFilter { content: content.to_vec() }
121    }
122
123    /// Computes a SCRIPT_FILTER that contains spent and output scripts.
124    pub fn new_script_filter<M, S>(block: &Block, script_for_coin: M) -> Result<BlockFilter, Error>
125    where
126        M: Fn(&OutPoint) -> Result<S, Error>,
127        S: Borrow<Script>,
128    {
129        let mut out = Vec::new();
130        let mut writer = BlockFilterWriter::new(&mut out, block);
131
132        writer.add_output_scripts();
133        writer.add_input_scripts(script_for_coin)?;
134        writer.finish()?;
135
136        Ok(BlockFilter { content: out })
137    }
138
139    /// Computes this filter's ID in a chain of filters (see [BIP 157]).
140    ///
141    /// [BIP 157]: <https://github.com/bitcoin/bips/blob/master/bip-0157.mediawiki#Filter_Headers>
142    pub fn filter_header(&self, previous_filter_header: &FilterHeader) -> FilterHeader {
143        let filter_hash = FilterHash::hash(self.content.as_slice());
144        filter_hash.filter_header(previous_filter_header)
145    }
146
147    /// Returns true if any query matches against this [`BlockFilter`].
148    pub fn match_any<I>(&self, block_hash: &BlockHash, query: I) -> Result<bool, Error>
149    where
150        I: Iterator,
151        I::Item: Borrow<[u8]>,
152    {
153        let filter_reader = BlockFilterReader::new(block_hash);
154        filter_reader.match_any(&mut self.content.as_slice(), query)
155    }
156
157    /// Returns true if all queries match against this [`BlockFilter`].
158    pub fn match_all<I>(&self, block_hash: &BlockHash, query: I) -> Result<bool, Error>
159    where
160        I: Iterator,
161        I::Item: Borrow<[u8]>,
162    {
163        let filter_reader = BlockFilterReader::new(block_hash);
164        filter_reader.match_all(&mut self.content.as_slice(), query)
165    }
166}
167
168/// Compiles and writes a block filter.
169pub struct BlockFilterWriter<'a, W> {
170    block: &'a Block,
171    writer: GcsFilterWriter<'a, W>,
172}
173
174impl<'a, W: io::Write> BlockFilterWriter<'a, W> {
175    /// Creates a new [`BlockFilterWriter`] from `block`.
176    pub fn new(writer: &'a mut W, block: &'a Block) -> BlockFilterWriter<'a, W> {
177        let block_hash_as_int = block.block_hash().to_byte_array();
178        let k0 = u64::from_le_bytes(block_hash_as_int[0..8].try_into().expect("8 byte slice"));
179        let k1 = u64::from_le_bytes(block_hash_as_int[8..16].try_into().expect("8 byte slice"));
180        let writer = GcsFilterWriter::new(writer, k0, k1, M, P);
181        BlockFilterWriter { block, writer }
182    }
183
184    /// Adds output scripts of the block to filter (excluding OP_RETURN scripts).
185    pub fn add_output_scripts(&mut self) {
186        for transaction in &self.block.txdata {
187            for output in &transaction.output {
188                if !output.script_pubkey.is_op_return() {
189                    self.add_element(output.script_pubkey.as_bytes());
190                }
191            }
192        }
193    }
194
195    /// Adds consumed output scripts of a block to filter.
196    pub fn add_input_scripts<M, S>(&mut self, script_for_coin: M) -> Result<(), Error>
197    where
198        M: Fn(&OutPoint) -> Result<S, Error>,
199        S: Borrow<Script>,
200    {
201        for script in self
202            .block
203            .txdata
204            .iter()
205            .skip(1) // skip coinbase
206            .flat_map(|t| t.input.iter().map(|i| &i.previous_output))
207            .map(script_for_coin)
208        {
209            match script {
210                Ok(script) => self.add_element(script.borrow().as_bytes()),
211                Err(e) => return Err(e),
212            }
213        }
214        Ok(())
215    }
216
217    /// Adds an arbitrary element to filter.
218    pub fn add_element(&mut self, data: &[u8]) {
219        self.writer.add_element(data);
220    }
221
222    /// Writes the block filter.
223    pub fn finish(&mut self) -> Result<usize, io::Error> {
224        self.writer.finish()
225    }
226}
227
228/// Reads and interprets a block filter.
229pub struct BlockFilterReader {
230    reader: GcsFilterReader,
231}
232
233impl BlockFilterReader {
234    /// Creates a new [`BlockFilterReader`] from `block_hash`.
235    pub fn new(block_hash: &BlockHash) -> BlockFilterReader {
236        let block_hash_as_int = block_hash.to_byte_array();
237        let k0 = u64::from_le_bytes(block_hash_as_int[0..8].try_into().expect("8 byte slice"));
238        let k1 = u64::from_le_bytes(block_hash_as_int[8..16].try_into().expect("8 byte slice"));
239        BlockFilterReader { reader: GcsFilterReader::new(k0, k1, M, P) }
240    }
241
242    /// Returns true if any query matches against this [`BlockFilterReader`].
243    pub fn match_any<I, R>(&self, reader: &mut R, query: I) -> Result<bool, Error>
244    where
245        I: Iterator,
246        I::Item: Borrow<[u8]>,
247        R: io::Read + ?Sized,
248    {
249        self.reader.match_any(reader, query)
250    }
251
252    /// Returns true if all queries match against this [`BlockFilterReader`].
253    pub fn match_all<I, R>(&self, reader: &mut R, query: I) -> Result<bool, Error>
254    where
255        I: Iterator,
256        I::Item: Borrow<[u8]>,
257        R: io::Read + ?Sized,
258    {
259        self.reader.match_all(reader, query)
260    }
261}
262
263/// Golomb-Rice encoded filter reader.
264pub struct GcsFilterReader {
265    filter: GcsFilter,
266    m: u64,
267}
268
269impl GcsFilterReader {
270    /// Creates a new [`GcsFilterReader`] with specific seed to siphash.
271    pub fn new(k0: u64, k1: u64, m: u64, p: u8) -> GcsFilterReader {
272        GcsFilterReader { filter: GcsFilter::new(k0, k1, p), m }
273    }
274
275    /// Returns true if any query matches against this [`GcsFilterReader`].
276    pub fn match_any<I, R>(&self, reader: &mut R, query: I) -> Result<bool, Error>
277    where
278        I: Iterator,
279        I::Item: Borrow<[u8]>,
280        R: io::Read + ?Sized,
281    {
282        let mut decoder = reader;
283        let n_elements: VarInt = Decodable::consensus_decode(&mut decoder).unwrap_or(VarInt(0));
284        let reader = &mut decoder;
285        // map hashes to [0, n_elements << grp]
286        let nm = n_elements.0 * self.m;
287        let mut mapped =
288            query.map(|e| map_to_range(self.filter.hash(e.borrow()), nm)).collect::<Vec<_>>();
289        // sort
290        mapped.sort_unstable();
291        if mapped.is_empty() {
292            return Ok(true);
293        }
294        if n_elements.0 == 0 {
295            return Ok(false);
296        }
297
298        // find first match in two sorted arrays in one read pass
299        let mut reader = BitStreamReader::new(reader);
300        let mut data = self.filter.golomb_rice_decode(&mut reader)?;
301        let mut remaining = n_elements.0 - 1;
302        for p in mapped {
303            loop {
304                match data.cmp(&p) {
305                    Ordering::Equal => return Ok(true),
306                    Ordering::Less => {
307                        if remaining > 0 {
308                            data += self.filter.golomb_rice_decode(&mut reader)?;
309                            remaining -= 1;
310                        } else {
311                            return Ok(false);
312                        }
313                    }
314                    Ordering::Greater => break,
315                }
316            }
317        }
318        Ok(false)
319    }
320
321    /// Returns true if all queries match against this [`GcsFilterReader`].
322    pub fn match_all<I, R>(&self, reader: &mut R, query: I) -> Result<bool, Error>
323    where
324        I: Iterator,
325        I::Item: Borrow<[u8]>,
326        R: io::Read + ?Sized,
327    {
328        let mut decoder = reader;
329        let n_elements: VarInt = Decodable::consensus_decode(&mut decoder).unwrap_or(VarInt(0));
330        let reader = &mut decoder;
331        // map hashes to [0, n_elements << grp]
332        let nm = n_elements.0 * self.m;
333        let mut mapped =
334            query.map(|e| map_to_range(self.filter.hash(e.borrow()), nm)).collect::<Vec<_>>();
335        // sort
336        mapped.sort_unstable();
337        mapped.dedup();
338        if mapped.is_empty() {
339            return Ok(true);
340        }
341        if n_elements.0 == 0 {
342            return Ok(false);
343        }
344
345        // figure if all mapped are there in one read pass
346        let mut reader = BitStreamReader::new(reader);
347        let mut data = self.filter.golomb_rice_decode(&mut reader)?;
348        let mut remaining = n_elements.0 - 1;
349        for p in mapped {
350            loop {
351                match data.cmp(&p) {
352                    Ordering::Equal => break,
353                    Ordering::Less => {
354                        if remaining > 0 {
355                            data += self.filter.golomb_rice_decode(&mut reader)?;
356                            remaining -= 1;
357                        } else {
358                            return Ok(false);
359                        }
360                    }
361                    Ordering::Greater => return Ok(false),
362                }
363            }
364        }
365        Ok(true)
366    }
367}
368
369/// Fast reduction of hash to [0, nm) range.
370fn map_to_range(hash: u64, nm: u64) -> u64 {
371    ((hash as u128 * nm as u128) >> 64) as u64
372}
373
374/// Golomb-Rice encoded filter writer.
375pub struct GcsFilterWriter<'a, W> {
376    filter: GcsFilter,
377    writer: &'a mut W,
378    elements: BTreeSet<Vec<u8>>,
379    m: u64,
380}
381
382impl<'a, W: io::Write> GcsFilterWriter<'a, W> {
383    /// Creates a new [`GcsFilterWriter`] wrapping a generic writer, with specific seed to siphash.
384    pub fn new(writer: &'a mut W, k0: u64, k1: u64, m: u64, p: u8) -> GcsFilterWriter<'a, W> {
385        GcsFilterWriter { filter: GcsFilter::new(k0, k1, p), writer, elements: BTreeSet::new(), m }
386    }
387
388    /// Adds data to the filter.
389    pub fn add_element(&mut self, element: &[u8]) {
390        if !element.is_empty() {
391            self.elements.insert(element.to_vec());
392        }
393    }
394
395    /// Writes the filter to the wrapped writer.
396    pub fn finish(&mut self) -> Result<usize, io::Error> {
397        let nm = self.elements.len() as u64 * self.m;
398
399        // map hashes to [0, n_elements * M)
400        let mut mapped: Vec<_> = self
401            .elements
402            .iter()
403            .map(|e| map_to_range(self.filter.hash(e.as_slice()), nm))
404            .collect();
405        mapped.sort_unstable();
406
407        // write number of elements as varint
408        let mut wrote = VarInt::from(mapped.len()).consensus_encode(&mut self.writer)?;
409
410        // write out deltas of sorted values into a Golonb-Rice coded bit stream
411        let mut writer = BitStreamWriter::new(self.writer);
412        let mut last = 0;
413        for data in mapped {
414            wrote += self.filter.golomb_rice_encode(&mut writer, data - last)?;
415            last = data;
416        }
417        wrote += writer.flush()?;
418        Ok(wrote)
419    }
420}
421
422/// Golomb Coded Set Filter.
423struct GcsFilter {
424    k0: u64, // sip hash key
425    k1: u64, // sip hash key
426    p: u8,
427}
428
429impl GcsFilter {
430    /// Creates a new [`GcsFilter`].
431    fn new(k0: u64, k1: u64, p: u8) -> GcsFilter {
432        GcsFilter { k0, k1, p }
433    }
434
435    /// Golomb-Rice encodes a number `n` to a bit stream (parameter 2^k).
436    fn golomb_rice_encode<W>(
437        &self,
438        writer: &mut BitStreamWriter<'_, W>,
439        n: u64,
440    ) -> Result<usize, io::Error>
441    where
442        W: io::Write,
443    {
444        let mut wrote = 0;
445        let mut q = n >> self.p;
446        while q > 0 {
447            let nbits = cmp::min(q, 64);
448            wrote += writer.write(!0u64, nbits as u8)?;
449            q -= nbits;
450        }
451        wrote += writer.write(0, 1)?;
452        wrote += writer.write(n, self.p)?;
453        Ok(wrote)
454    }
455
456    /// Golomb-Rice decodes a number from a bit stream (parameter 2^k).
457    fn golomb_rice_decode<R>(&self, reader: &mut BitStreamReader<R>) -> Result<u64, io::Error>
458    where
459        R: io::Read,
460    {
461        let mut q = 0u64;
462        while reader.read(1)? == 1 {
463            q += 1;
464        }
465        let r = reader.read(self.p)?;
466        Ok((q << self.p) + r)
467    }
468
469    /// Hashes an arbitrary slice with siphash using parameters of this filter.
470    fn hash(&self, element: &[u8]) -> u64 {
471        siphash24::Hash::hash_to_u64_with_keys(self.k0, self.k1, element)
472    }
473}
474
475/// Bitwise stream reader.
476pub struct BitStreamReader<'a, R> {
477    buffer: [u8; 1],
478    offset: u8,
479    reader: &'a mut R,
480}
481
482impl<'a, R: io::Read> BitStreamReader<'a, R> {
483    /// Creates a new [`BitStreamReader`] that reads bitwise from a given `reader`.
484    pub fn new(reader: &'a mut R) -> BitStreamReader<'a, R> {
485        BitStreamReader { buffer: [0u8], reader, offset: 8 }
486    }
487
488    /// Reads nbit bits, returning the bits in a `u64` starting with the rightmost bit.
489    ///
490    /// # Examples
491    /// ```
492    /// # use bitcoin::bip158::BitStreamReader;
493    /// # let data = vec![0xff];
494    /// # let mut input = data.as_slice();
495    /// let mut reader = BitStreamReader::new(&mut input); // input contains all 1's
496    /// let res = reader.read(1).expect("read failed");
497    /// assert_eq!(res, 1_u64);
498    /// ```
499    pub fn read(&mut self, mut nbits: u8) -> Result<u64, io::Error> {
500        if nbits > 64 {
501            return Err(io::Error::new(
502                io::ErrorKind::Other,
503                "can not read more than 64 bits at once",
504            ));
505        }
506        let mut data = 0u64;
507        while nbits > 0 {
508            if self.offset == 8 {
509                self.reader.read_exact(&mut self.buffer)?;
510                self.offset = 0;
511            }
512            let bits = cmp::min(8 - self.offset, nbits);
513            data <<= bits;
514            data |= ((self.buffer[0] << self.offset) >> (8 - bits)) as u64;
515            self.offset += bits;
516            nbits -= bits;
517        }
518        Ok(data)
519    }
520}
521
522/// Bitwise stream writer.
523pub struct BitStreamWriter<'a, W> {
524    buffer: [u8; 1],
525    offset: u8,
526    writer: &'a mut W,
527}
528
529impl<'a, W: io::Write> BitStreamWriter<'a, W> {
530    /// Creates a new [`BitStreamWriter`] that writes bitwise to a given `writer`.
531    pub fn new(writer: &'a mut W) -> BitStreamWriter<'a, W> {
532        BitStreamWriter { buffer: [0u8], writer, offset: 0 }
533    }
534
535    /// Writes nbits bits from data.
536    pub fn write(&mut self, data: u64, mut nbits: u8) -> Result<usize, io::Error> {
537        if nbits > 64 {
538            return Err(io::Error::new(
539                io::ErrorKind::Other,
540                "can not write more than 64 bits at once",
541            ));
542        }
543        let mut wrote = 0;
544        while nbits > 0 {
545            let bits = cmp::min(8 - self.offset, nbits);
546            self.buffer[0] |= ((data << (64 - nbits)) >> (64 - 8 + self.offset)) as u8;
547            self.offset += bits;
548            nbits -= bits;
549            if self.offset == 8 {
550                wrote += self.flush()?;
551            }
552        }
553        Ok(wrote)
554    }
555
556    /// flush bits not yet written.
557    pub fn flush(&mut self) -> Result<usize, io::Error> {
558        if self.offset > 0 {
559            self.writer.write_all(&self.buffer)?;
560            self.buffer[0] = 0u8;
561            self.offset = 0;
562            Ok(1)
563        } else {
564            Ok(0)
565        }
566    }
567}
bellscoin/bip158.rs

bellscoin/
bip158.rs
