Merge rust-bitcoin/rust-bitcoin#6786: fuzz: Add bip158 fuzz_targets for BasicFilter

### Cargo-minimal.lock
@@ -176,6 +176,7 @@ dependencies = [
  "arbitrary",
  "bitcoin 0.32.102",
  "bitcoin 0.33.0-beta",
+ "bitcoin-bip158",
  "bitcoin-consensus-encoding 1.2.0",
  "bitcoin-p2p-messages",
  "libfuzzer-sys",

### Cargo-recent.lock
@@ -170,6 +170,7 @@ dependencies = [
  "arbitrary",
  "bitcoin 0.32.102",
  "bitcoin 0.33.0-beta",
+ "bitcoin-bip158",
  "bitcoin-consensus-encoding 1.2.0",
  "bitcoin-p2p-messages",
  "libfuzzer-sys",

### fuzz/Cargo.toml
@@ -17,6 +17,7 @@ cargo-fuzz = true
 # choke on it otherwise. See https://github.com/nix-community/crate2nix/issues/373
 bitcoin = { path = "../bitcoin", version = "0.33.0-beta", features = [ "serde", "arbitrary" ] }
 bitcoin_0_32 = { version = "0.32.102", package = "bitcoin", features = [ "encoding", "serde" ] }
+bitcoin_bip158 = { path = "../bip158", package = "bitcoin-bip158" }
 bitcoin_consensus_encoding = { path = "../consensus_encoding", package = "bitcoin-consensus-encoding" }
 p2p = { path = "../p2p", package = "bitcoin-p2p-messages", features = ["arbitrary"] }
 
@@ -52,6 +53,20 @@ allowed_duplicates = [
     "secp256k1-sys",
 ]
 
+[[bin]]
+name = "bip158_build_filter"
+path = "fuzz_targets/bip158/build_filter.rs"
+test = false
+doc = false
+bench = false
+
+[[bin]]
+name = "bip158_parse_filter"
+path = "fuzz_targets/bip158/parse_filter.rs"
+test = false
+doc = false
+bench = false
+
 [[bin]]
 name = "bitcoin_arbitrary_block"
 path = "fuzz_targets/bitcoin/arbitrary_block.rs"

### fuzz/fuzz_targets/bip158/build_filter.rs
@@ -0,0 +1,89 @@
+#![cfg_attr(fuzzing, no_main)]
+#![cfg_attr(not(fuzzing), allow(unused))]
+
+use core::convert::Infallible;
+use std::collections::BTreeSet;
+
+use bitcoin::absolute::LockTime;
+use bitcoin::block::{Block, Header, Version as BlockVersion};
+use bitcoin::transaction::Version as TransactionVersion;
+use bitcoin::{
+    Amount, BlockHash, BlockTime, CompactTarget, OutPoint, ScriptPubKeyBuf, ScriptSigBuf, Sequence,
+    Transaction, TxIn, TxMerkleNode, TxOut, Txid, Witness,
+};
+use bitcoin_bip158::BasicFilter;
+use bitcoin_consensus_encoding::{CompactSizeEncoder, Encoder};
+use libfuzzer_sys::fuzz_target;
+
+#[cfg(not(fuzzing))]
+fn main() {}
+
+fn do_test((outputs, prevouts): (Vec<ScriptPubKeyBuf>, Vec<ScriptPubKeyBuf>)) {
+    let coinbase = Transaction {
+        version: TransactionVersion::TWO,
+        lock_time: LockTime::ZERO,
+        inputs: vec![TxIn {
+            previous_output: OutPoint::COINBASE_PREVOUT,
+            script_sig: ScriptSigBuf::new(),
+            sequence: Sequence::MAX,
+            witness: Witness::new(),
+        }],
+        outputs: outputs
+            .iter()
+            .cloned()
+            .map(|script_pubkey| TxOut { amount: Amount::ZERO, script_pubkey })
+            .collect(),
+    };
+    let spending = Transaction {
+        version: TransactionVersion::TWO,
+        lock_time: LockTime::ZERO,
+        inputs: (0..prevouts.len())
+            .map(|index| TxIn {
+                previous_output: OutPoint {
+                    txid: Txid::from_byte_array([0; 32]),
+                    vout: index as u32,
+                },
+                script_sig: ScriptSigBuf::new(),
+                sequence: Sequence::MAX,
+                witness: Witness::new(),
+            })
+            .collect(),
+        outputs: Vec::new(),
+    };
+    let header = Header {
+        version: BlockVersion::ONE,
+        prev_blockhash: BlockHash::GENESIS_PREVIOUS_BLOCK_HASH,
+        merkle_root: TxMerkleNode::from_byte_array([0; 32]),
+        time: BlockTime::from_u32(0),
+        bits: CompactTarget::from_consensus(0),
+        nonce: 0,
+    };
+    let block = Block::new_unchecked(header, vec![coinbase, spending]).assume_checked(None);
+    let block_hash = block.block_hash();
+    let filter = BasicFilter::from_block(&block, |outpoint| {
+        Ok::<_, Infallible>(&*prevouts[outpoint.vout as usize])
+    })
+    .expect("infallible prevout lookup");
+
+    let reparsed = BasicFilter::from_bytes(filter.as_bytes()).expect("constructed filter is valid");
+    assert_eq!(reparsed.as_bytes(), filter.as_bytes());
+    assert_eq!(reparsed.filter_hash(), filter.filter_hash());
+
+    let eligible_scripts = outputs
+        .iter()
+        .filter(|script| !script.is_empty() && !script.is_op_return())
+        .chain(prevouts.iter().filter(|script| !script.is_empty()))
+        .map(|script| script.as_bytes())
+        .collect::<BTreeSet<_>>();
+    let expected_count = CompactSizeEncoder::new(eligible_scripts.len());
+    assert!(filter.as_bytes().starts_with(expected_count.current_chunk()));
+
+    assert!(filter.match_all(block_hash, eligible_scripts.iter().copied()));
+    for script in eligible_scripts {
+        assert!(filter.match_any(block_hash, [script]));
+    }
+}
+
+fuzz_target!(|data: (Vec<ScriptPubKeyBuf>, Vec<ScriptPubKeyBuf>)| {
+    do_test(data);
+});

### fuzz/fuzz_targets/bip158/parse_filter.rs
@@ -0,0 +1,33 @@
+#![cfg_attr(fuzzing, no_main)]
+#![cfg_attr(not(fuzzing), allow(unused))]
+
+use bitcoin::BlockHash;
+use bitcoin_bip158::BasicFilter;
+use libfuzzer_sys::fuzz_target;
+
+#[cfg(not(fuzzing))]
+fn main() {}
+
+fn do_test(data: &[u8]) {
+    let Ok(filter) = BasicFilter::from_bytes(data) else { return };
+    assert_eq!(filter.as_bytes(), data);
+
+    let mut hash_bytes = [0u8; 32];
+    let hash_len = data.len().min(hash_bytes.len());
+    hash_bytes[..hash_len].copy_from_slice(&data[..hash_len]);
+    let block_hash = BlockHash::from_byte_array(hash_bytes);
+    let queries = data.chunks(8).take(8).collect::<Vec<_>>();
+
+    assert_eq!(
+        filter.match_any(block_hash, &queries),
+        queries.iter().any(|query| filter.match_any(block_hash, [query]))
+    );
+    assert_eq!(
+        filter.match_all(block_hash, &queries),
+        queries.iter().all(|query| filter.match_all(block_hash, [query]))
+    );
+}
+
+fuzz_target!(|data: &[u8]| {
+    do_test(data);
+});