silent-tweak-sdk 0.1.0

//! BIP158-style compact block filters for pre-filtering.
//!
//! Clients download compact filters to identify which blocks *might*
//! contain Silent Payment outputs for their spend key, before fetching
//! the heavier tweak data.  This is pure bandwidth optimisation — false
//! positives are harmless.
//!
//! ## Filter encoding
//!
//! We use Golomb-Rice coding (P=19, M=784931) — the same parameters as
//! BIP158 basic (type 0) filters.

use std::io::{self, Cursor, Read};

/// GCS (Golomb-Coded Set) P parameter matching BIP158 type 0.
pub const GCS_P: u8 = 19;
/// GCS M parameter matching BIP158 type 0 (false positive rate ≈ 1/784931).
pub const GCS_M: u64 = 784_931;

/// A decoded compact block filter.
#[derive(Debug, Clone)]
pub struct BlockFilter {
    /// Block height this filter covers.
    pub height: u32,
    /// Block hash (32 bytes).
    pub block_hash: [u8; 32],
    /// Underlying Golomb-coded set (GCS).
    gcs: GcsFilter,
}

impl BlockFilter {
    /// Construct a filter from raw GCS bytes (as served by the server).
    ///
    /// # Errors
    /// Returns an error if the GCS bytes are malformed.
    pub fn from_bytes(height: u32, block_hash: [u8; 32], raw: &[u8]) -> crate::Result<Self> {
        let gcs = GcsFilter::decode(raw, block_hash)?;
        Ok(Self {
            height,
            block_hash,
            gcs,
        })
    }

    /// Test whether a scriptPubKey *might* be in this block.
    ///
    /// Returns `true` on match (possible hit) or `false` (definite miss).
    #[must_use]
    pub fn match_script(&self, script: &[u8]) -> bool {
        self.gcs.match_element(script)
    }

    /// Test a batch of scripts — returns `true` if *any* might match.
    #[must_use]
    pub fn match_any_script(&self, scripts: &[&[u8]]) -> bool {
        scripts.iter().any(|s| self.match_script(s))
    }
}

// ── Golomb-Coded Set ────────────────────────────────────────────────────────

#[derive(Debug, Clone)]
struct GcsFilter {
    /// Pre-hashed, sorted element hashes stored in the filter.
    elements: Vec<u64>,
    /// Element count — needed to reproduce the modulus `GCS_M * n` for matching.
    n: u64,
    /// Key for `SipHash` (derived from block hash).
    key: [u8; 16],
}

impl GcsFilter {
    fn decode(raw: &[u8], block_hash: [u8; 32]) -> crate::Result<Self> {
        let key = derive_filter_key(&block_hash);
        let (n, elements) = gcs_decode_elements(raw, GCS_P)
            .map_err(|e| crate::Error::Crypto(format!("GCS decode: {e}")))?;
        Ok(Self { elements, n, key })
    }

    fn match_element(&self, data: &[u8]) -> bool {
        if self.n == 0 {
            return false;
        }
        let h = sip_hash_element(data, &self.key, GCS_M * self.n);
        self.elements.binary_search(&h).is_ok()
    }
}

/// Derive a 16-byte `SipHash` key from a block hash (BIP158 §Construction).
fn derive_filter_key(block_hash: &[u8; 32]) -> [u8; 16] {
    let mut key = [0u8; 16];
    key.copy_from_slice(&block_hash[..16]);
    key
}

/// `SipHash`-2-4 based element hash mapped to `[0, modulus)` using BIP158 method:
/// `floor(siphash64(data, key) * modulus / 2^64)`.
fn sip_hash_element(data: &[u8], key: &[u8; 16], modulus: u64) -> u64 {
    use std::hash::Hasher;
    let mut h = siphasher::sip::SipHasher24::new_with_keys(
        u64::from_le_bytes(key[..8].try_into().unwrap()),
        u64::from_le_bytes(key[8..].try_into().unwrap()),
    );
    h.write(data);
    let hval = h.finish();
    // BIP158-correct 128-bit multiply: maps uniformly to [0, modulus)
    ((u128::from(hval) * u128::from(modulus)) >> 64) as u64
}

/// Encode a list of scriptPubKeys into a GCS filter.
#[must_use]
pub fn gcs_encode<S: AsRef<[u8]>>(scripts: &[S], block_hash: &[u8; 32]) -> Vec<u8> {
    let key = derive_filter_key(block_hash);
    let n = scripts.len() as u64;
    if n == 0 {
        return vec![];
    }
    let mut hashes: Vec<u64> = scripts
        .iter()
        .map(|s| sip_hash_element(s.as_ref(), &key, GCS_M * n))
        .collect();
    hashes.sort_unstable();
    hashes.dedup();

    let mut out = Vec::new();
    write_varint(&mut out, hashes.len() as u64);
    let mut prev = 0u64;
    let mut bit_writer = BitWriter::new(&mut out);
    for &h in &hashes {
        let delta = h - prev;
        prev = h;
        golomb_rice_encode(&mut bit_writer, delta, GCS_P);
    }
    bit_writer.flush();
    out
}

fn gcs_decode_elements(raw: &[u8], param: u8) -> io::Result<(u64, Vec<u64>)> {
    if raw.is_empty() {
        return Ok((0, vec![]));
    }
    let mut cursor = Cursor::new(raw);
    let n = read_varint(&mut cursor)?;
    #[allow(clippy::cast_possible_truncation)]
    let mut elements = Vec::with_capacity(n as usize);
    let mut prev = 0u64;
    let remaining = {
        #[allow(clippy::cast_possible_truncation)]
        let pos = cursor.position() as usize;
        &raw[pos..]
    };
    let mut bit_reader = BitReader::new(remaining);
    for _ in 0..n {
        let delta = golomb_rice_decode(&mut bit_reader, param)?;
        prev += delta;
        elements.push(prev);
    }
    Ok((n, elements))
}

// ── Varint helpers ──────────────────────────────────────────────────────────

fn write_varint(out: &mut Vec<u8>, mut n: u64) {
    while n >= 0x80 {
        #[allow(clippy::cast_possible_truncation)]
        out.push((n as u8) | 0x80);
        n >>= 7;
    }
    #[allow(clippy::cast_possible_truncation)]
    out.push(n as u8);
}

fn read_varint<R: Read>(r: &mut R) -> io::Result<u64> {
    let mut n = 0u64;
    let mut shift = 0u32;
    loop {
        let mut buf = [0u8; 1];
        r.read_exact(&mut buf)?;
        let b = buf[0];
        n |= u64::from(b & 0x7f) << shift;
        if b & 0x80 == 0 {
            break;
        }
        shift += 7;
    }
    Ok(n)
}

// ── Golomb-Rice bit-level codec ─────────────────────────────────────────────

struct BitWriter<'a> {
    buf: &'a mut Vec<u8>,
    current: u8,
    bits: u8,
}

impl<'a> BitWriter<'a> {
    fn new(buf: &'a mut Vec<u8>) -> Self {
        Self {
            buf,
            current: 0,
            bits: 0,
        }
    }

    fn write_bit(&mut self, bit: bool) {
        self.current = (self.current << 1) | u8::from(bit);
        self.bits += 1;
        if self.bits == 8 {
            self.buf.push(self.current);
            self.current = 0;
            self.bits = 0;
        }
    }

    fn flush(&mut self) {
        if self.bits > 0 {
            self.current <<= 8 - self.bits;
            self.buf.push(self.current);
            self.current = 0;
            self.bits = 0;
        }
    }
}

struct BitReader<'a> {
    data: &'a [u8],
    byte_pos: usize,
    bit_pos: u8,
}

impl<'a> BitReader<'a> {
    fn new(data: &'a [u8]) -> Self {
        Self {
            data,
            byte_pos: 0,
            bit_pos: 0,
        }
    }

    fn read_bit(&mut self) -> io::Result<bool> {
        if self.byte_pos >= self.data.len() {
            return Err(io::Error::new(
                io::ErrorKind::UnexpectedEof,
                "GCS bit underflow",
            ));
        }
        let bit = (self.data[self.byte_pos] >> (7 - self.bit_pos)) & 1;
        self.bit_pos += 1;
        if self.bit_pos == 8 {
            self.bit_pos = 0;
            self.byte_pos += 1;
        }
        Ok(bit == 1)
    }
}

fn golomb_rice_encode(writer: &mut BitWriter, value: u64, param: u8) {
    let quotient = value >> param;
    let remainder = value & ((1u64 << param) - 1);
    for _ in 0..quotient {
        writer.write_bit(true);
    }
    writer.write_bit(false);
    for i in (0..param).rev() {
        writer.write_bit((remainder >> i) & 1 == 1);
    }
}

fn golomb_rice_decode(reader: &mut BitReader, param: u8) -> io::Result<u64> {
    let mut quotient = 0u64;
    while reader.read_bit()? {
        quotient += 1;
    }
    let mut remainder = 0u64;
    for _ in 0..param {
        remainder = (remainder << 1) | u64::from(reader.read_bit()?);
    }
    Ok((quotient << param) | remainder)
}

/// Build a GCS compact block filter from a list of scriptPubKeys.
///
/// Used by the server indexer to store per-block filters.
#[must_use]
pub fn build_block_filter(scripts: &[&[u8]], block_hash: &[u8; 32]) -> Vec<u8> {
    gcs_encode(scripts, block_hash)
}

mod siphasher {
    pub mod sip {
        pub struct SipHasher24 {
            #[allow(dead_code)]
            k0: u64,
            #[allow(dead_code)]
            k1: u64,
            v0: u64,
            v1: u64,
            v2: u64,
            v3: u64,
            buf: [u8; 8],
            buf_len: usize,
            len: usize,
        }

        impl SipHasher24 {
            #[must_use]
            pub fn new_with_keys(k0: u64, k1: u64) -> Self {
                let v0 = k0 ^ 0x736f_6d65_7073_6575;
                let v1 = k1 ^ 0x646f_7261_6e64_6f6d;
                let v2 = k0 ^ 0x6c79_6765_6e65_7261;
                let v3 = k1 ^ 0x7465_6462_7974_6573;
                Self {
                    k0,
                    k1,
                    v0,
                    v1,
                    v2,
                    v3,
                    buf: [0; 8],
                    buf_len: 0,
                    len: 0,
                }
            }

            fn round(v0: &mut u64, v1: &mut u64, v2: &mut u64, v3: &mut u64) {
                *v0 = v0.wrapping_add(*v1);
                *v1 = v1.rotate_left(13);
                *v1 ^= *v0;
                *v0 = v0.rotate_left(32);
                *v2 = v2.wrapping_add(*v3);
                *v3 = v3.rotate_left(16);
                *v3 ^= *v2;
                *v0 = v0.wrapping_add(*v3);
                *v3 = v3.rotate_left(21);
                *v3 ^= *v0;
                *v2 = v2.wrapping_add(*v1);
                *v1 = v1.rotate_left(17);
                *v1 ^= *v2;
                *v2 = v2.rotate_left(32);
            }

            fn compress(&mut self, m: u64) {
                self.v3 ^= m;
                Self::round(&mut self.v0, &mut self.v1, &mut self.v2, &mut self.v3);
                Self::round(&mut self.v0, &mut self.v1, &mut self.v2, &mut self.v3);
                self.v0 ^= m;
            }
        }

        impl std::hash::Hasher for SipHasher24 {
            fn write(&mut self, data: &[u8]) {
                for &byte in data {
                    self.buf[self.buf_len] = byte;
                    self.buf_len += 1;
                    self.len += 1;
                    if self.buf_len == 8 {
                        let m = u64::from_le_bytes(self.buf);
                        self.compress(m);
                        self.buf_len = 0;
                    }
                }
            }

            fn finish(&self) -> u64 {
                let mut v0 = self.v0;
                let mut v1 = self.v1;
                let mut v2 = self.v2;
                let mut v3 = self.v3;
                #[allow(clippy::cast_possible_truncation)]
                let mut last: u64 = (self.len as u64 & 0xff) << 56;
                let buf_len = self.buf_len;
                for i in (0..buf_len).rev() {
                    last |= u64::from(self.buf[i]) << (i * 8);
                }
                v3 ^= last;
                Self::round(&mut v0, &mut v1, &mut v2, &mut v3);
                Self::round(&mut v0, &mut v1, &mut v2, &mut v3);
                v0 ^= last;
                v2 ^= 0xff;
                Self::round(&mut v0, &mut v1, &mut v2, &mut v3);
                Self::round(&mut v0, &mut v1, &mut v2, &mut v3);
                Self::round(&mut v0, &mut v1, &mut v2, &mut v3);
                Self::round(&mut v0, &mut v1, &mut v2, &mut v3);
                v0 ^ v1 ^ v2 ^ v3
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn roundtrip_single_script() {
        let script: &[u8] = b"\x51\x20deadbeef_padding_bytes_here_0000";
        let block_hash = [0xabu8; 32];
        let encoded = gcs_encode(&[script], &block_hash);
        let filter = BlockFilter::from_bytes(0, block_hash, &encoded).unwrap();
        assert!(filter.match_script(script));
    }

    #[test]
    fn no_false_negative() {
        let scripts: Vec<&[u8]> = vec![b"script_alice" as &[u8], b"script_bob", b"script_carol"];
        let block_hash = [0x01u8; 32];
        let encoded = gcs_encode(&scripts, &block_hash);
        let filter = BlockFilter::from_bytes(1, block_hash, &encoded).unwrap();
        for s in &scripts {
            assert!(filter.match_script(s), "false negative for {s:?}");
        }
    }

    #[test]
    fn empty_filter() {
        let block_hash = [0x00u8; 32];
        let encoded = gcs_encode::<&[u8]>(&[], &block_hash);
        let filter = BlockFilter::from_bytes(0, block_hash, &encoded).unwrap();
        assert!(!filter.match_script(b"anything"));
    }
}