txoo 0.10.0

use crate::filter::{BlockSpendFilter, ChunkedOctets};
use crate::io::{Error, Read, Write};
use crate::spv::SpvProof;
use crate::SignedAttestation;
use alloc::collections::BTreeSet;
use alloc::sync::Arc;
use alloc::vec::Vec;
use serde_bolt::bitcoin::consensus::{Decodable, Encodable};
use bitcoin::secp256k1::constants::PUBLIC_KEY_SIZE;
use bitcoin::secp256k1::{All, PublicKey, Secp256k1};
use bitcoin::{Block, BlockHash, OutPoint, Transaction};
use bitcoin::blockdata::block::Header as BlockHeader;
use bitcoin::hash_types::FilterHeader;

/// Dummy oracle secret key, for testing
#[cfg(feature = "test-utils")]
pub const DUMMY_ORACLE_SECRET: &[u8; 32] = &[2u8; 32];

/// An exclusion proof and an inclusion proof for a set of outpoints, or the whole block
/// if there was a false positive
#[derive(Clone)]
pub enum ProofType {
    /// There were no false positives, so a compact filter and an SPV
    /// proof are sufficient
    Filter(Arc<ChunkedOctets>, SpvProof),
    /// There was a false positive, so the whole block is necessary
    Block(Block),
    /// There was a false positive, and the block will be provided later
    ExternalBlock(),
}

impl ProofType {
    /// Take the block out of the proof, if there is one.
    /// Used for streaming large proofs that include a block.
    pub fn take_block(self) -> (Self, Option<Block>) {
        match self {
            ProofType::Block(block) => (ProofType::ExternalBlock(), Some(block)),
            _ => (self, None),
        }
    }

    /// Whether the proof is external
    pub fn is_external(&self) -> bool {
        match self {
            ProofType::ExternalBlock() => true,
            _ => false,
        }
    }
}

impl Encodable for ProofType {
    fn consensus_encode<W: Write + ?Sized>(&self, writer: &mut W) -> Result<usize, Error> {
        let mut len = 0;
        match self {
            ProofType::Filter(filter, proof) => {
                len += 0u8.consensus_encode(writer)?;
                len += filter.consensus_encode(writer)?;
                len += proof.consensus_encode(writer)?;
            }
            ProofType::Block(block) => {
                len += 1u8.consensus_encode(writer)?;
                len += block.consensus_encode(writer)?;
            }
            ProofType::ExternalBlock() => {
                len += 2u8.consensus_encode(writer)?;
            }
        }
        Ok(len)
    }
}

impl Decodable for ProofType {
    fn consensus_decode<D: Read + ?Sized>(
        reader: &mut D,
    ) -> Result<Self, bitcoin::consensus::encode::Error> {
        let proof_type = u8::consensus_decode(reader)?;
        match proof_type {
            0 => {
                let filter = ChunkedOctets::consensus_decode(reader)?;
                let proof = SpvProof::consensus_decode(reader)?;
                Ok(ProofType::Filter(Arc::new(filter), proof))
            }
            1 => {
                let block = Block::consensus_decode(reader)?;
                Ok(ProofType::Block(block))
            }
            2 => Ok(ProofType::ExternalBlock()),
            _ => Err(bitcoin::consensus::encode::Error::ParseFailed(
                "invalid proof type",
            )),
        }
    }
}

/// Proof that some transaction outpoints were spent or unspent in a block.
///
/// This includes both a compact filter sub-proof for unspent outpoints, and an SPV sub-proof
/// for matched spending transactions in the block.
///
/// The following transactions are matched and included in the SPV sub-proof:
/// - any transaction spending an outpoint in the watched set
/// - any transaction watched by ID
/// - any transaction spending an output of a previously matched transaction
#[derive(Clone)]
pub struct TxoProof {
    /// The oracle attestations for the relevant block
    pub attestations: Vec<(PublicKey, SignedAttestation)>,
    /// The proof of exclusion and inclusion of the relevant outpoints
    pub proof: ProofType,
}

impl Encodable for TxoProof {
    fn consensus_encode<W: Write + ?Sized>(&self, w: &mut W) -> Result<usize, Error> {
        let mut len = 0;
        let num_attestations = self.attestations.len() as u32;
        len += num_attestations.consensus_encode(w)?;
        for (pk, attestation) in &self.attestations {
            len += pk.serialize().consensus_encode(w)?;
            len += attestation.consensus_encode(w)?;
        }
        len += self.proof.consensus_encode(w)?;
        Ok(len)
    }
}

impl Decodable for TxoProof {
    fn consensus_decode<R: Read + ?Sized>(
        reader: &mut R,
    ) -> Result<Self, bitcoin::consensus::encode::Error> {
        let num_attestations = u32::consensus_decode(reader)?;
        if num_attestations == 0 {
            return Err(bitcoin::consensus::encode::Error::ParseFailed(
                "no attestations",
            ));
        }
        let mut attestations = Vec::with_capacity(num_attestations as usize);
        for _ in 0..num_attestations {
            let pk_ser: [u8; PUBLIC_KEY_SIZE] = Decodable::consensus_decode(reader)?;
            let pk = PublicKey::from_slice(&pk_ser)
                .map_err(|_| bitcoin::consensus::encode::Error::ParseFailed("invalid pubkey"))?;
            let attestation = Decodable::consensus_decode(reader)?;
            attestations.push((pk, attestation));
        }
        let proof = Decodable::consensus_decode(reader)?;
        Ok(TxoProof {
            attestations,
            proof,
        })
    }
}

impl TxoProof {
    /// Create a proof for the given watched outpoints and tx IDs,
    /// given the attestations and the block.
    /// See struct documentation for details on what is included in the proof.
    #[cfg(feature = "prover")]
    pub fn prove(
        attestations: Vec<(PublicKey, SignedAttestation)>,
        prev_filter_header: &FilterHeader,
        block: &Block,
        block_height: u32,
        outpoint_watches: &[OutPoint],
        txid_watches: &[bitcoin::Txid],
    ) -> Self {
        // sanity checks
        if attestations.is_empty() {
            panic!("no attestations provided");
        }

        let filter = BlockSpendFilter::from_block(block);
        let filter_header = filter.filter_header(prev_filter_header);
        let block_hash = block.block_hash();

        for (_, attestation) in attestations.iter() {
            if attestation.attestation.block_hash != block_hash {
                panic!("attestation for wrong block");
            }
            if attestation.attestation.block_height != block_height {
                panic!("attestation for wrong block height");
            }
            if attestation.attestation.filter_header != filter_header {
                panic!(
                    "attestation for wrong filter header {} != {} prev {}",
                    attestation.attestation.filter_header, filter_header, prev_filter_header
                );
            }
        }

        // first construct an SPV sub-proof for all matched transactions and their descendants
        let (spv_proof, _spent, unspent) = SpvProof::build(block, txid_watches, outpoint_watches);

        // the SPV proof may have adjusted the set of outpoints to consider, use the new set

        // if there was a false positive, we need to return the whole block
        // check for `is_empty()`, to work around a bug in match_any with empty query
        let proof = if !unspent.is_empty() && filter.match_any(&block_hash, &mut unspent.iter()) {
            ProofType::Block(block.clone())
        } else {
            ProofType::Filter(filter.content, spv_proof)
        };

        Self {
            attestations,
            proof,
        }
    }

    /// For testing, a proof that includes all the transactions in the block,
    /// and no attestations.
    #[cfg(feature = "test-utils")]
    pub fn prove_unchecked(
        block: &Block,
        prev_filter_header: &FilterHeader,
        block_height: u32,
    ) -> Self {
        use crate::util::sign_attestation;
        use bitcoin::secp256k1;
        use secp256k1::{Keypair, SecretKey};

        let secp = Secp256k1::new();
        let dummy_key = SecretKey::from_slice(DUMMY_ORACLE_SECRET).unwrap();
        let dummy_keypair = Keypair::from_secret_key(&secp, &dummy_key);
        let dummy_pubkey = PublicKey::from_secret_key(&secp, &dummy_key);
        let filter = BlockSpendFilter::from_block(block);
        let filter_header = filter.filter_header(prev_filter_header);
        let attestation = crate::Attestation {
            block_hash: block.block_hash(),
            block_height,
            filter_header,
            time: 0,
        };
        let signed_attestation = sign_attestation(attestation, &dummy_keypair, &secp);
        let txid_watches: Vec<_> = block.txdata.iter().map(|tx| tx.compute_txid()).collect();
        let (spv_proof, _spent, _unspent) = SpvProof::build(block, &txid_watches, &[]);

        let proof = ProofType::Filter(filter.content, spv_proof);

        Self {
            attestations: vec![(dummy_pubkey, signed_attestation)],
            proof,
        }
    }

    /// Verify the proof.
    /// For each of the watched outpoints, check that it was proven as unspent or that
    /// a matched spending transaction was included in the SPV sub-proof.
    /// For each matched transaction, also check that its outputs were proven as unspent
    /// or that a further spending transaction was included in the SPV sub-proof.
    ///
    /// After calling this, you can securely use [`get_spending_transaction()`]
    /// for outputs in [`outpoint_watches`] or for outputs of matched spending transactions.
    ///
    /// `external_block_hash` is the block hash of the block that was provided externally
    /// to the proof.  It must be provided iff the proof is an external block proof.
    ///
    /// Correctness argument:
    /// - the attestation proves that the block hash was the tip of the chain at the time of the
    ///   attestation
    /// - the attestation covers the compact filter
    /// - if there is a false positive, the whole block is included, and it can be verified via its hash
    /// - if a spending transaction is omitted, a watched outpoint will match the compact filter and
    ///   verification will fail
    /// - if an incorrect spending transaction is included, the SPV proof will fail
    pub fn verify(
        &self,
        block_height: u32,
        block_header: &BlockHeader,
        external_block_hash: Option<&BlockHash>,
        prev_filter_header: &FilterHeader,
        outpoint_watches: &[OutPoint],
        secp: &Secp256k1<All>,
    ) -> Result<(), VerifyError> {
        assert_eq!(
            self.proof.is_external(),
            external_block_hash.is_some(),
            "block hash must be provided iff proof is external"
        );
        if self.attestations.is_empty() {
            return Err(VerifyError::MissingAttestations);
        }

        let block_hash = block_header.block_hash();

        let filter_header = match &self.proof {
            ProofType::Block(block) => {
                if block.block_hash() != block_hash {
                    return Err(VerifyError::InvalidBlock);
                }
                None
            }
            ProofType::Filter(filter_vec, spv_proof) => {
                if !spv_proof.verify(block_header) {
                    return Err(VerifyError::InvalidSpvProof);
                }

                let filter = BlockSpendFilter::new(filter_vec.clone());

                // construct the set of outpoints to consider
                let mut outpoints = BTreeSet::from_iter(outpoint_watches.iter().cloned());

                for tx in spv_proof.txs.iter() {
                    // any spent outpoints can be removed from consideration
                    for input in tx.input.iter() {
                        outpoints.remove(&input.previous_output);
                    }
                    // outputs of matched txs must be considered
                    for vout in 0..tx.output.len() {
                        let outpoint = OutPoint::new(tx.compute_txid(), vout as u32);
                        outpoints.insert(outpoint);
                    }
                }

                // check that the filter doesn't match any of the outpoints
                // work around a bug in match_any with empty query
                if !outpoints.is_empty() && filter.match_any(&block_hash, &mut outpoints.iter()) {
                    return Err(VerifyError::UnspentIsSpent);
                }

                Some(filter.filter_header(prev_filter_header))
            }
            ProofType::ExternalBlock() => {
                if external_block_hash != Some(&block_hash) {
                    return Err(VerifyError::InvalidBlock);
                }
                None
            }
        };

        for (pubkey, attestation) in self.attestations.iter() {
            if !attestation.verify(pubkey, secp) {
                return Err(VerifyError::InvalidSignature);
            }
            if attestation.attestation.block_height != block_height {
                return Err(VerifyError::InvalidAttestation);
            }
            if attestation.attestation.block_hash != block_hash {
                return Err(VerifyError::InvalidAttestation);
            }
            if let Some(filter_header) = filter_header {
                if attestation.attestation.filter_header != filter_header {
                    return Err(VerifyError::InvalidAttestation);
                }
            }
        }

        Ok(())
    }

    /// Get the filter header for the block
    pub fn filter_header(&self) -> FilterHeader {
        let header = self.attestations[0].1.attestation.filter_header;
        // sanity check that all attestations have the same filter header
        for attestation in self.attestations.iter().skip(1) {
            if attestation.1.attestation.filter_header != header {
                panic!("filter header mismatch");
            }
        }
        header
    }

    /// Get the matched transaction that spends this outpoint, if it is spent in the block.
    /// You must call [`verify()`] first.
    pub fn spending_transaction(&self, outpoint: &OutPoint) -> Option<Transaction> {
        match &self.proof {
            ProofType::Block(block) => {
                for tx in block.txdata.iter() {
                    for input in tx.input.iter() {
                        if input.previous_output == *outpoint {
                            return Some(tx.clone());
                        }
                    }
                }
                None
            }
            ProofType::Filter(_, spv_proof) => {
                for tx in spv_proof.txs.iter() {
                    for input in tx.input.iter() {
                        if input.previous_output == *outpoint {
                            return Some(tx.clone());
                        }
                    }
                }
                None
            }
            ProofType::ExternalBlock() => {
                // external block must be handled separately
                None
            }
        }
    }

    /// Take the block out of the proof, if there is one.
    /// Used for streaming large proofs that include a block.
    pub fn take_block(self) -> (Self, Option<Block>) {
        let (proof, block) = self.proof.take_block();
        (Self { proof, ..self }, block)
    }
}

/// Errors that can occur during proof verification
#[derive(Debug, PartialEq)]
pub enum VerifyError {
    /// the proof is missing attestations
    MissingAttestations,
    /// the attestation does not match the block
    InvalidAttestation,
    /// attestation signature is invalid
    InvalidSignature,
    /// the full block provided as proof does not match the block hash
    InvalidBlock,
    /// a spent outpoint is missing the spending transaction
    UnspentIsSpent,
    /// the SPV proof is invalid
    InvalidSpvProof,
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::filter::BlockSpendFilter;
    use crate::spv::SpvProof;
    use crate::util::sign_attestation;
    use crate::{Attestation, SignedAttestation};
    use bitcoin::absolute::LockTime;
    use bitcoin::transaction::Version;
    use bitcoin::consensus::{Decodable, Encodable};
    use bitcoin::hashes::Hash;
    use bitcoin::secp256k1::{All, PublicKey, Secp256k1, SecretKey};
    use bitcoin::{Amount, Block, BlockHash, CompactTarget, OutPoint, Transaction, TxIn, Txid};
    use bitcoin::hash_types::TxMerkleNode;
    use bitcoin::merkle_tree::PartialMerkleTree;
    use bitcoin::key::Keypair;
    use bitcoin::TxOut;

    #[test]
    fn round_trip_encode_test() {
        let (secp, pubkey, keypair) = make_keypair();
        let (block, filter_header) = make_block(vec![]);
        let signed_attestation = make_attestation(&secp, &keypair, &block, filter_header);
        let proof = TxoProof::prove(
            vec![(pubkey, signed_attestation)],
            &FilterHeader::all_zeros(),
            &block,
            100,
            &[],
            &[],
        );
        let mut buf = Vec::new();
        let len = proof.consensus_encode(&mut buf).unwrap();
        assert_eq!(len, buf.len());
        let decoded = TxoProof::consensus_decode(&mut &buf[..]).unwrap();
        assert_eq!(
            proof.attestations[0].1.signature,
            decoded.attestations[0].1.signature
        );

        let mut proof1 = proof.clone();
        proof1.attestations = vec![];
        let mut buf = Vec::new();
        proof1.consensus_encode(&mut buf).unwrap();
        assert!(TxoProof::consensus_decode(&mut &buf[..]).is_err());
    }

    #[test]
    #[should_panic]
    fn no_attestation_test() {
        let (block, _) = make_block(vec![]);
        let _ = TxoProof::prove(vec![], &FilterHeader::all_zeros(), &block, 100, &[], &[]);
    }

    #[test]
    #[should_panic]
    fn wrong_block_height_test() {
        let (secp, pubkey, keypair) = make_keypair();
        let (block, filter_header) = make_block(vec![]);
        let signed_attestation = make_attestation(&secp, &keypair, &block, filter_header);
        let _ = TxoProof::prove(
            vec![(pubkey, signed_attestation)],
            &FilterHeader::all_zeros(),
            &block,
            101,
            &[],
            &[],
        );
    }

    #[test]
    #[should_panic]
    fn wrong_block_test() {
        let (secp, pubkey, keypair) = make_keypair();
        let (mut block, filter_header) = make_block(vec![]);
        let signed_attestation = make_attestation(&secp, &keypair, &block, filter_header);
        block.header.nonce = 1;
        let _ = TxoProof::prove(
            vec![(pubkey, signed_attestation)],
            &FilterHeader::all_zeros(),
            &block,
            100,
            &[],
            &[],
        );
    }

    #[test]
    #[should_panic]
    fn wrong_filter_test() {
        let (secp, pubkey, keypair) = make_keypair();
        let (block, _) = make_block(vec![]);
        let signed_attestation =
            make_attestation(&secp, &keypair, &block, FilterHeader::all_zeros());
        let _ = TxoProof::prove(
            vec![(pubkey, signed_attestation)],
            &FilterHeader::all_zeros(),
            &block,
            100,
            &[],
            &[],
        );
    }

    #[test]
    fn verify_trivial_test() {
        let (secp, pubkey, keypair) = make_keypair();
        let (block, filter_header) = make_block(vec![]);
        let signed_attestation = make_attestation(&secp, &keypair, &block, filter_header);
        let proof = TxoProof::prove(
            vec![(pubkey, signed_attestation)],
            &FilterHeader::all_zeros(),
            &block,
            100,
            &[],
            &[],
        );
        if let ProofType::Filter(_, spv_proof_model) = proof.proof.clone() {
            let proof: SpvProof = spv_proof_model.try_into().unwrap();
            assert_eq!(proof.txs.len(), 0);
        } else {
            panic!("unexpected proof type");
        }
        proof
            .verify(
                100,
                &block.header,
                None,
                &FilterHeader::all_zeros(),
                &[],
                &secp,
            )
            .expect("proof should be valid");
        assert_eq!(proof.filter_header(), filter_header);

        assert_eq!(
            proof.verify(
                101,
                &block.header,
                None,
                &FilterHeader::all_zeros(),
                &[],
                &secp
            ),
            Err(VerifyError::InvalidAttestation)
        );

        let wrong_header = BlockHeader {
            version: bitcoin::block::Version::ONE,
            prev_blockhash: BlockHash::all_zeros(),
            merkle_root: TxMerkleNode::all_zeros(),
            time: 0,
            bits: CompactTarget::from_consensus(0),
            nonce: 0,
        };

        assert_eq!(
            proof.verify(
                100,
                &wrong_header,
                None,
                &FilterHeader::all_zeros(),
                &[],
                &secp
            ),
            Err(VerifyError::InvalidAttestation)
        );

        let mut proof1 = proof.clone();
        proof1.attestations = vec![];

        assert_eq!(
            proof1.verify(
                100,
                &block.header,
                None,
                &FilterHeader::all_zeros(),
                &[],
                &secp
            ),
            Err(VerifyError::MissingAttestations)
        );
    }

    #[test]
    fn verify_one_unspent_test() {
        let (secp, pubkey, keypair) = make_keypair();
        let (block, filter_header) = make_block(vec![make_transaction(1)]);
        let signed_attestation = make_attestation(&secp, &keypair, &block, filter_header);
        let outpoint_watches = [OutPoint {
            txid: Txid::all_zeros(),
            vout: 2,
        }];
        let proof = TxoProof::prove(
            vec![(pubkey, signed_attestation)],
            &FilterHeader::all_zeros(),
            &block,
            100,
            &outpoint_watches,
            &[],
        );

        assert!(proof.spending_transaction(&outpoint_watches[0]).is_none());

        if let ProofType::Filter(_, spv_proof_model) = proof.proof.clone() {
            let proof: SpvProof = spv_proof_model.try_into().unwrap();
            assert_eq!(proof.txs.len(), 0);
        } else {
            panic!("unexpected proof type");
        }

        proof
            .verify(
                100,
                &block.header,
                None,
                &FilterHeader::all_zeros(),
                &outpoint_watches,
                &secp,
            )
            .expect("proof should be valid");
    }

    #[test]
    fn verify_one_spent_test() {
        let (secp, pubkey, keypair) = make_keypair();
        let (block, filter_header) = make_block(vec![make_transaction(1)]);
        let signed_attestation = make_attestation(&secp, &keypair, &block, filter_header);
        let outpoint_watches = [OutPoint {
            txid: Txid::all_zeros(),
            vout: 1,
        }];
        let proof = TxoProof::prove(
            vec![(pubkey, signed_attestation)],
            &FilterHeader::all_zeros(),
            &block,
            100,
            &outpoint_watches,
            &[],
        );

        assert_eq!(
            proof.spending_transaction(&outpoint_watches[0]),
            Some(block.txdata[0].clone())
        );

        if let ProofType::Filter(_, spv_proof_model) = proof.proof.clone() {
            let proof: SpvProof = spv_proof_model.try_into().unwrap();
            assert_eq!(proof.txs.len(), 1);
        } else {
            panic!("unexpected proof type");
        }
        proof
            .verify(
                100,
                &block.header,
                None,
                &FilterHeader::all_zeros(),
                &outpoint_watches,
                &secp,
            )
            .expect("proof should be valid");

        let mut bad1 = proof.clone();
        match &mut bad1.proof {
            ProofType::Filter(_, spv_proof) => {
                let mut v = Vec::new();
                spv_proof
                    .proof
                    .as_ref()
                    .unwrap()
                    .consensus_encode(&mut v)
                    .unwrap();
                v[0] ^= 1;
                let dec = PartialMerkleTree::consensus_decode(&mut v.as_slice()).unwrap();
                spv_proof.proof = Some(dec);
            }
            _ => panic!(),
        }
        assert_eq!(
            bad1.verify(
                100,
                &block.header,
                None,
                &FilterHeader::all_zeros(),
                &outpoint_watches,
                &secp
            ),
            Err(VerifyError::InvalidSpvProof)
        );

        let mut bad2 = proof.clone();
        match &mut bad2.proof {
            ProofType::Filter(filt, _) => {
                let mut f = ChunkedOctets::new();
                f.write(&filt.to_vec()).unwrap();
                f[0] ^= 1;
                *filt = Arc::new(f);
            }
            _ => panic!(),
        }
        assert_eq!(
            bad2.verify(
                100,
                &block.header,
                None,
                &FilterHeader::all_zeros(),
                &outpoint_watches,
                &secp
            ),
            Err(VerifyError::InvalidAttestation)
        );
    }

    #[test]
    fn verify_inter_block_dependency_test() {
        // create a block with two transactions, one dependent on the other
        let (secp, pubkey, keypair) = make_keypair();
        let tx0 = make_transaction(1);
        let (block, filter_header) = make_block(vec![
            tx0.clone(),
            make_transaction_with_inputs(vec![OutPoint {
                txid: tx0.compute_txid(),
                vout: 1,
            }]),
        ]);
        let signed_attestation = make_attestation(&secp, &keypair, &block, filter_header);

        let outpoint_watches = [OutPoint {
            txid: Txid::all_zeros(),
            vout: 1,
        }];
        let proof = TxoProof::prove(
            vec![(pubkey, signed_attestation)],
            &FilterHeader::all_zeros(),
            &block,
            100,
            &outpoint_watches,
            &[],
        );

        assert_eq!(
            proof.spending_transaction(&outpoint_watches[0]),
            Some(block.txdata[0].clone())
        );
        assert_eq!(
            proof.spending_transaction(&OutPoint {
                txid: tx0.compute_txid(),
                vout: 1
            }),
            Some(block.txdata[1].clone())
        );

        let filter_proof = if let ProofType::Filter(filt, spv) = &proof.proof {
            assert_eq!(spv.txs.len(), 2);
            (filt, spv)
        } else {
            panic!("should not have sent the whole block")
        };

        proof
            .verify(
                100,
                &block.header,
                None,
                &FilterHeader::all_zeros(),
                &outpoint_watches,
                &secp,
            )
            .expect("proof should be valid");

        // try to hide the second spending tx
        let txids = block.txdata.iter().map(|tx| tx.compute_txid()).collect::<Vec<_>>();
        let bad_proof = PartialMerkleTree::from_txids(&txids, &[true, false]);
        let bad_spv = SpvProof {
            proof: Some(bad_proof),
            txs: vec![tx0.clone()],
        };
        let bad_proof = TxoProof {
            attestations: proof.attestations.clone(),
            proof: ProofType::Filter(filter_proof.0.clone(), bad_spv.into()),
        };
        assert_eq!(
            bad_proof.verify(
                100,
                &block.header,
                None,
                &FilterHeader::all_zeros(),
                &outpoint_watches,
                &secp
            ),
            Err(VerifyError::UnspentIsSpent)
        );
    }

    #[test]
    #[ignore]
    fn find_false_positive() {
        let (block, _) = make_block(vec![make_transaction(1)]);
        let filter = BlockSpendFilter::from_block(&block);
        for i in 2..1000000 {
            let outpoints = vec![OutPoint {
                txid: Txid::all_zeros(),
                vout: i,
            }];
            if filter.match_any(&block.block_hash(), &mut outpoints.iter()) {
                println!("found false positive at {}", i);
                // see `FALSE_POSITIVE_VOUT`
                break;
            }
        }
    }

    const FALSE_POSITIVE_VOUT: u32 = 798937;

    #[test]
    fn verify_false_positive_test() {
        let (secp, pubkey, keypair) = make_keypair();
        let (block, filter_header) = make_block(vec![make_transaction(1)]);
        let signed_attestation = make_attestation(&secp, &keypair, &block, filter_header);
        let outpoint_watches = [OutPoint {
            txid: Txid::all_zeros(),
            vout: FALSE_POSITIVE_VOUT,
        }];
        let proof = TxoProof::prove(
            vec![(pubkey, signed_attestation)],
            &FilterHeader::all_zeros(),
            &block,
            100,
            &outpoint_watches,
            &[],
        );

        assert_eq!(proof.spending_transaction(&outpoint_watches[0]), None);
        assert_eq!(
            proof.spending_transaction(&OutPoint::new(Txid::all_zeros(), 1)),
            Some(block.txdata[0].clone())
        );

        if let ProofType::Filter(_, _) = &proof.proof {
            panic!("should have sent the whole block")
        }
        proof
            .verify(
                100,
                &block.header,
                None,
                &FilterHeader::all_zeros(),
                &outpoint_watches,
                &secp,
            )
            .expect("proof should be valid");

        // externalize the block from the proof, and verify it again
        let proof_ext = TxoProof {
            attestations: proof.attestations.clone(),
            proof: ProofType::ExternalBlock(),
        };
        proof_ext
            .verify(
                100,
                &block.header,
                Some(&block.block_hash()),
                &FilterHeader::all_zeros(),
                &outpoint_watches,
                &secp,
            )
            .expect("proof should be valid");
        proof_ext
            .verify(
                100,
                &block.header,
                Some(&BlockHash::all_zeros()),
                &FilterHeader::all_zeros(),
                &outpoint_watches,
                &secp,
            )
            .expect_err("block hash should mismatch");

        let bad_header = BlockHeader {
            version: bitcoin::block::Version::from_consensus(5),
            ..block.header
        };

        let bad_block = Block {
            header: bad_header,
            ..block
        };

        let signed_attestation1 = make_attestation(&secp, &keypair, &bad_block, filter_header);
        let mut proof1 = proof.clone();
        proof1.attestations[0].1 = signed_attestation1;

        assert_eq!(
            proof1.verify(
                100,
                &bad_header,
                None,
                &FilterHeader::all_zeros(),
                &outpoint_watches,
                &secp
            ),
            Err(VerifyError::InvalidBlock)
        );
    }

    fn make_attestation(
        secp: &Secp256k1<All>,
        keypair: &Keypair,
        block: &Block,
        filter_header: FilterHeader,
    ) -> SignedAttestation {
        let attestation = Attestation {
            block_hash: block.block_hash(),
            block_height: 100,
            filter_header,
            time: 1000,
        };
        let signed_attestation = sign_attestation(attestation, &keypair, &secp);
        signed_attestation
    }

    fn make_keypair() -> (Secp256k1<All>, PublicKey, Keypair) {
        let secp = Secp256k1::new();
        let secret = SecretKey::from_slice(&[1; 32]).unwrap();
        let pubkey = PublicKey::from_secret_key(&secp, &secret);
        let keypair = Keypair::from_secret_key(&secp, &secret);
        (secp, pubkey, keypair)
    }

    // make a transaction spending a certain vout of txid zero
    fn make_transaction(vout: u32) -> Transaction {
        make_transaction_with_inputs(vec![OutPoint {
            txid: Txid::all_zeros(),
            vout,
        }])
    }

    fn make_transaction_with_inputs(spends: Vec<OutPoint>) -> Transaction {
        Transaction {
            version: Version::ONE,
            lock_time: LockTime::ZERO,
            input: spends
                .into_iter()
                .map(|spend| TxIn {
                    previous_output: spend,
                    script_sig: Default::default(),
                    sequence: Default::default(),
                    witness: Default::default(),
                })
                .collect(),
            output: vec![
                TxOut {
                    value: Amount::ONE_SAT,
                    script_pubkey: Default::default(),
                },
                TxOut {
                    value: Amount::ONE_SAT,
                    script_pubkey: Default::default(),
                },
            ],
        }
    }

    fn make_block(txs: Vec<Transaction>) -> (Block, FilterHeader) {
        let mut block = Block {
            header: BlockHeader {
                version: bitcoin::block::Version::from_consensus(0),
                prev_blockhash: BlockHash::all_zeros(),
                merkle_root: TxMerkleNode::all_zeros(),
                time: 0,
                bits: CompactTarget::from_consensus(0),
                nonce: 0,
            },
            txdata: txs,
        };
        if !block.txdata.is_empty() {
            block.header.merkle_root = block.compute_merkle_root().expect("merkle root");
        }
        let filter = BlockSpendFilter::from_block(&block);
        let filter_header = filter.filter_header(&FilterHeader::all_zeros());
        (block, filter_header)
    }
}