Skip to main content

hns_light_wallet/
lib.rs

1//! Locally verified Handshake filtered-block evidence for embedded wallets.
2//!
3//! Peers provide bloom-filter matches, MerkleBlock payloads, and transactions.
4//! This crate treats all of them as untrusted until the partial Merkle tree is
5//! bound to a consensus-validated [`hns_light_chain::HeaderEntry`] or an
6//! authenticated archived [`WalletHeaderAnchor`], and every advertised
7//! transaction hash is exactly correlated. The wallet therefore persists
8//! headers and its own coins, names, and boards rather than a pruned global
9//! transaction or name index.
10
11#![forbid(unsafe_code)]
12#![allow(
13    clippy::cast_possible_truncation,
14    clippy::cast_precision_loss,
15    clippy::cast_sign_loss,
16    clippy::doc_markdown,
17    clippy::missing_errors_doc,
18    clippy::module_name_repetitions,
19    reason = "HSD/BIP37 formulas intentionally convert bounded f64 sizes; HNS, BIP37, and P2P are protocol names"
20)]
21
22use std::collections::{BTreeMap, HashSet};
23
24use blake2::Blake2b;
25use blake2::digest::{Digest, consts::U32};
26use hns_encoding::{DecodeError, Decoder, Encoder};
27use hns_header_consensus::{HEADER_SIZE, Header, HeaderError};
28use hns_light_chain::HeaderEntry;
29use hns_p2p_wire::{Inventory, InventoryKind, MAX_INVENTORY_ITEMS, Packet};
30use hns_primitives::{BlockHash, BlockTime, Height, MerkleRoot, TransactionHash, TreeRoot};
31use hns_transaction::{Transaction, TransactionError};
32use thiserror::Error;
33
34/// HSD/Bitcoin policy maximum bloom-filter byte length.
35pub const MAX_BLOOM_FILTER_BYTES: usize = 36_000;
36/// HSD/Bitcoin policy maximum bloom-filter hash function count.
37pub const MAX_BLOOM_HASH_FUNCTIONS: u32 = 50;
38/// HSD maximum element length accepted by `filteradd`.
39pub const MAX_FILTER_ADD_ELEMENT_BYTES: usize = 520;
40/// HSD's maximum plausible transactions in a one-megabyte base block.
41pub const MAX_FILTERED_BLOCK_TRANSACTIONS: usize = 1_000_000 / 60;
42/// Maximum flags needed by a full partial tree with the transaction bound.
43pub const MAX_PARTIAL_MERKLE_FLAG_BYTES: usize = (MAX_FILTERED_BLOCK_TRANSACTIONS * 2).div_ceil(8);
44/// Strict upper bound for one canonical HSD MerkleBlock payload.
45pub const MAX_MERKLE_BLOCK_PAYLOAD_BYTES: usize =
46    HEADER_SIZE + 4 + 9 + MAX_FILTERED_BLOCK_TRANSACTIONS * 32 + 9 + MAX_PARTIAL_MERKLE_FLAG_BYTES;
47
48const LN_2: f64 = std::f64::consts::LN_2;
49const LN_2_SQUARED: f64 = LN_2 * LN_2;
50const BLOOM_TWEAK_MULTIPLIER: u32 = 0xfba4_c795;
51
52/// Minimal locally validated header fields needed by wallet block evidence.
53///
54/// Unlike a full [`HeaderEntry`], this anchor can be reconstructed from the
55/// wallet's authenticated raw-header archive without inventing historical
56/// chainwork. Construction is intentionally explicit: callers must supply a
57/// header already admitted by their local header authority.
58#[derive(Clone, Copy, Debug, Eq, PartialEq)]
59pub struct WalletHeaderAnchor {
60    height: Height,
61    hash: BlockHash,
62    previous_block: BlockHash,
63    tree_root: TreeRoot,
64    merkle_root: MerkleRoot,
65    time: BlockTime,
66}
67
68impl WalletHeaderAnchor {
69    /// Reconstruct a wallet-evidence anchor from one authenticated archived
70    /// header and its locally bound height.
71    #[must_use]
72    pub fn from_validated_header(height: Height, header: &Header) -> Self {
73        Self {
74            height,
75            hash: header.block_hash(),
76            previous_block: header.previous_block,
77            tree_root: header.tree_root,
78            merkle_root: header.merkle_root,
79            time: header.time,
80        }
81    }
82
83    /// Locally bound height.
84    #[must_use]
85    pub const fn height(self) -> Height {
86        self.height
87    }
88
89    /// Consensus block hash.
90    #[must_use]
91    pub const fn hash(self) -> BlockHash {
92        self.hash
93    }
94
95    /// Previous block hash.
96    #[must_use]
97    pub const fn previous_block(self) -> BlockHash {
98        self.previous_block
99    }
100
101    /// Header Urkel root.
102    #[must_use]
103    pub const fn tree_root(self) -> TreeRoot {
104        self.tree_root
105    }
106
107    /// Header transaction Merkle root.
108    #[must_use]
109    pub const fn merkle_root(self) -> MerkleRoot {
110        self.merkle_root
111    }
112
113    /// Header timestamp.
114    #[must_use]
115    pub const fn time(self) -> BlockTime {
116        self.time
117    }
118}
119
120impl From<HeaderEntry> for WalletHeaderAnchor {
121    fn from(entry: HeaderEntry) -> Self {
122        Self {
123            height: entry.height(),
124            hash: entry.hash(),
125            previous_block: entry.previous_block(),
126            tree_root: entry.tree_root(),
127            merkle_root: entry.merkle_root(),
128            time: entry.time(),
129        }
130    }
131}
132
133/// HSD bloom-filter automatic outpoint update mode.
134#[repr(u8)]
135#[derive(Clone, Copy, Debug, Eq, PartialEq)]
136pub enum BloomUpdate {
137    /// Never add matching output outpoints automatically.
138    None = 0,
139    /// Add every matching output outpoint.
140    All = 1,
141    /// Add only matching pubkey-style output outpoints.
142    PubkeyOnly = 2,
143}
144
145impl TryFrom<u8> for BloomUpdate {
146    type Error = BloomError;
147
148    fn try_from(value: u8) -> Result<Self, Self::Error> {
149        match value {
150            0 => Ok(Self::None),
151            1 => Ok(Self::All),
152            2 => Ok(Self::PubkeyOnly),
153            _ => Err(BloomError::InvalidUpdate),
154        }
155    }
156}
157
158/// Exact HSD-compatible BIP37 bloom filter.
159#[derive(Clone, Debug, Eq, PartialEq)]
160pub struct HsdBloomFilter {
161    bytes: Vec<u8>,
162    hash_functions: u32,
163    tweak: u32,
164    update: BloomUpdate,
165}
166
167impl HsdBloomFilter {
168    /// Construct a policy-bounded filter from its exact bit and hash counts.
169    pub fn new(
170        size_bits: usize,
171        hash_functions: u32,
172        tweak: u32,
173        update: BloomUpdate,
174    ) -> Result<Self, BloomError> {
175        let size_bits = size_bits.max(8);
176        if size_bits > MAX_BLOOM_FILTER_BYTES * 8 {
177            return Err(BloomError::FilterTooLarge);
178        }
179        let hash_functions = hash_functions.max(1);
180        if hash_functions > MAX_BLOOM_HASH_FUNCTIONS {
181            return Err(BloomError::TooManyHashFunctions);
182        }
183        let size_bytes = (size_bits - (size_bits & 7)) / 8;
184        Ok(Self {
185            bytes: vec![0; size_bytes],
186            hash_functions,
187            tweak,
188            update,
189        })
190    }
191
192    /// Construct the same rate-derived shape as HSD `BloomFilter.fromRate`.
193    ///
194    /// The caller supplies a fresh unpredictable tweak; this runtime-independent
195    /// crate intentionally does not own an operating-system RNG.
196    pub fn from_rate(
197        expected_items: usize,
198        false_positive_rate: f64,
199        tweak: u32,
200        update: BloomUpdate,
201    ) -> Result<Self, BloomError> {
202        if expected_items == 0 {
203            return Err(BloomError::ZeroExpectedItems);
204        }
205        if !false_positive_rate.is_finite()
206            || false_positive_rate <= 0.0
207            || false_positive_rate >= 1.0
208        {
209            return Err(BloomError::InvalidFalsePositiveRate);
210        }
211        let expected_items_float = expected_items as f64;
212        let calculated_bits =
213            (-expected_items_float * false_positive_rate.ln() / LN_2_SQUARED).floor();
214        if !calculated_bits.is_finite() || calculated_bits > (MAX_BLOOM_FILTER_BYTES * 8) as f64 {
215            return Err(BloomError::FilterTooLarge);
216        }
217        let size_bits = (calculated_bits as usize).max(8);
218        let hash_functions =
219            ((size_bits as f64 / expected_items_float * LN_2).floor() as u32).max(1);
220        Self::new(size_bits, hash_functions, tweak, update)
221    }
222
223    /// Number of bits in the filter.
224    #[must_use]
225    pub fn size_bits(&self) -> usize {
226        self.bytes.len() * 8
227    }
228
229    /// Number of Murmur3 functions applied to each element.
230    #[must_use]
231    pub const fn hash_functions(&self) -> u32 {
232        self.hash_functions
233    }
234
235    /// Connection-scoped Murmur3 tweak.
236    #[must_use]
237    pub const fn tweak(&self) -> u32 {
238        self.tweak
239    }
240
241    /// Automatic outpoint update mode.
242    #[must_use]
243    pub const fn update(&self) -> BloomUpdate {
244        self.update
245    }
246
247    /// Insert one script, address hash, name hash, transaction hash, or outpoint.
248    pub fn insert(&mut self, value: &[u8]) -> Result<(), BloomError> {
249        let size = self.size_bits();
250        for function in 0..self.hash_functions {
251            let index = bloom_hash(value, function, self.tweak) as usize % size;
252            let byte = self
253                .bytes
254                .get_mut(index >> 3)
255                .ok_or(BloomError::InternalInvariant)?;
256            *byte |= 1_u8 << (index & 7);
257        }
258        Ok(())
259    }
260
261    /// Return false only when the element is definitely absent.
262    #[must_use]
263    pub fn contains(&self, value: &[u8]) -> bool {
264        let size = self.size_bits();
265        (0..self.hash_functions).all(|function| {
266            let index = bloom_hash(value, function, self.tweak) as usize % size;
267            self.bytes
268                .get(index >> 3)
269                .is_some_and(|byte| byte & (1_u8 << (index & 7)) != 0)
270        })
271    }
272
273    /// Canonical HSD `filterload` payload.
274    #[must_use]
275    pub fn encode(&self) -> Vec<u8> {
276        let mut encoder = Encoder::with_capacity(self.bytes.len() + 12);
277        encoder.put_varbytes(&self.bytes);
278        encoder.put_u32_le(self.hash_functions);
279        encoder.put_u32_le(self.tweak);
280        encoder.put_u8(self.update as u8);
281        encoder.into_bytes()
282    }
283
284    /// Decode one complete, canonical, policy-bounded HSD filter payload.
285    pub fn decode_strict(input: &[u8]) -> Result<Self, BloomError> {
286        let mut decoder = Decoder::new(input);
287        let bytes = decoder.read_varbytes(MAX_BLOOM_FILTER_BYTES, "bloom filter")?;
288        let hash_functions = decoder.read_u32_le()?;
289        let tweak = decoder.read_u32_le()?;
290        let update = BloomUpdate::try_from(decoder.read_u8()?)?;
291        decoder.finish()?;
292        if bytes.is_empty() {
293            return Err(BloomError::EmptyFilter);
294        }
295        if hash_functions == 0 {
296            return Err(BloomError::ZeroHashFunctions);
297        }
298        if hash_functions > MAX_BLOOM_HASH_FUNCTIONS {
299            return Err(BloomError::TooManyHashFunctions);
300        }
301        Ok(Self {
302            bytes,
303            hash_functions,
304            tweak,
305            update,
306        })
307    }
308
309    /// Standard P2P packet that installs this complete filter on a peer.
310    #[must_use]
311    pub fn load_packet(&self) -> Packet {
312        Packet::FilterLoad(self.encode())
313    }
314
315    /// Add an element locally and return the matching HSD `filteradd` packet.
316    pub fn add_packet(&mut self, value: &[u8]) -> Result<Packet, BloomError> {
317        if value.len() > MAX_FILTER_ADD_ELEMENT_BYTES {
318            return Err(BloomError::ElementTooLarge);
319        }
320        self.insert(value)?;
321        let mut encoder = Encoder::with_capacity(value.len() + 9);
322        encoder.put_varbytes(value);
323        Ok(Packet::FilterAdd(encoder.into_bytes()))
324    }
325}
326
327/// Request locally known headers as HSD filtered blocks.
328pub fn request_filtered_blocks(headers: &[HeaderEntry]) -> Result<Packet, WalletEvidenceError> {
329    if headers.is_empty() {
330        return Err(WalletEvidenceError::EmptyBlockRequest);
331    }
332    if headers.len() > MAX_INVENTORY_ITEMS {
333        return Err(WalletEvidenceError::TooManyBlockRequests);
334    }
335    Ok(Packet::GetData(
336        headers
337            .iter()
338            .map(|entry| Inventory {
339                kind: InventoryKind::FilteredBlock,
340                hash: entry.hash().into_bytes(),
341            })
342            .collect(),
343    ))
344}
345
346/// One transaction hash proven into the expected header's Merkle root.
347#[derive(Clone, Copy, Debug, Eq, PartialEq)]
348pub struct MatchedTransaction {
349    hash: TransactionHash,
350    index: u32,
351}
352
353impl MatchedTransaction {
354    /// Canonical non-witness transaction hash.
355    #[must_use]
356    pub const fn hash(self) -> TransactionHash {
357        self.hash
358    }
359
360    /// Zero-based transaction index in the block.
361    #[must_use]
362    pub const fn index(self) -> u32 {
363        self.index
364    }
365}
366
367/// Partial-Merkle evidence bound to one locally consensus-validated header.
368#[derive(Clone, Debug, Eq, PartialEq)]
369pub struct WalletBlockEvidence {
370    header: WalletHeaderAnchor,
371    total_transactions: u32,
372    matches: Vec<MatchedTransaction>,
373}
374
375impl WalletBlockEvidence {
376    /// Decode and verify one complete HSD MerkleBlock payload for `header`.
377    pub fn decode_for_header(
378        input: &[u8],
379        header: HeaderEntry,
380    ) -> Result<Self, WalletEvidenceError> {
381        Self::decode_for_anchor(input, header.into())
382    }
383
384    /// Decode and verify a complete HSD MerkleBlock against one authenticated
385    /// raw-header archive anchor.
386    pub fn decode_for_anchor(
387        input: &[u8],
388        header: WalletHeaderAnchor,
389    ) -> Result<Self, WalletEvidenceError> {
390        let decoded = decode_partial_merkle(input, header.hash(), header.merkle_root())?;
391        Ok(Self {
392            header,
393            total_transactions: decoded.total_transactions,
394            matches: decoded.matches,
395        })
396    }
397
398    /// Authenticated local header anchor for this evidence.
399    #[must_use]
400    pub const fn header(&self) -> WalletHeaderAnchor {
401        self.header
402    }
403
404    /// Total transactions committed by the block.
405    #[must_use]
406    pub const fn total_transactions(&self) -> u32 {
407        self.total_transactions
408    }
409
410    /// Bloom-matched transactions proven into the block.
411    #[must_use]
412    pub fn matches(&self) -> &[MatchedTransaction] {
413        &self.matches
414    }
415
416    /// Start exact correlation of the transaction packets following MerkleBlock.
417    pub fn collect(self) -> Result<FilteredBlockCollector, WalletEvidenceError> {
418        FilteredBlockCollector::new(self)
419    }
420}
421
422/// Correlates transaction packets following one verified HSD MerkleBlock.
423#[derive(Clone, Debug, Eq, PartialEq)]
424pub struct FilteredBlockCollector {
425    evidence: WalletBlockEvidence,
426    pending: BTreeMap<TransactionHash, u32>,
427    transactions: BTreeMap<u32, Transaction>,
428}
429
430impl FilteredBlockCollector {
431    fn new(evidence: WalletBlockEvidence) -> Result<Self, WalletEvidenceError> {
432        let mut pending = BTreeMap::new();
433        for matched in &evidence.matches {
434            if pending.insert(matched.hash, matched.index).is_some() {
435                return Err(WalletEvidenceError::DuplicateMatchedTransaction);
436            }
437        }
438        Ok(Self {
439            evidence,
440            pending,
441            transactions: BTreeMap::new(),
442        })
443    }
444
445    /// Number of exact transaction packets still required.
446    #[must_use]
447    pub fn remaining(&self) -> usize {
448        self.pending.len()
449    }
450
451    /// Admit one transaction only when its canonical hash was proven by the tree.
452    pub fn admit(&mut self, transaction: Transaction) -> Result<usize, WalletEvidenceError> {
453        let hash = transaction.transaction_hash()?;
454        let index = self
455            .pending
456            .remove(&hash)
457            .ok_or(WalletEvidenceError::UnexpectedTransaction)?;
458        if self.transactions.insert(index, transaction).is_some() {
459            return Err(WalletEvidenceError::DuplicateTransactionIndex);
460        }
461        Ok(self.pending.len())
462    }
463
464    /// Finish only after every proven match has arrived exactly once.
465    pub fn finish(self) -> Result<VerifiedWalletBlock, WalletEvidenceError> {
466        if !self.pending.is_empty() {
467            return Err(WalletEvidenceError::MissingTransactions);
468        }
469        Ok(VerifiedWalletBlock {
470            evidence: self.evidence,
471            transactions: self.transactions.into_values().collect(),
472        })
473    }
474}
475
476/// Complete matched transaction set for one locally validated block header.
477#[derive(Clone, Debug, Eq, PartialEq)]
478pub struct VerifiedWalletBlock {
479    evidence: WalletBlockEvidence,
480    transactions: Vec<Transaction>,
481}
482
483impl VerifiedWalletBlock {
484    /// Verified partial-tree evidence.
485    #[must_use]
486    pub const fn evidence(&self) -> &WalletBlockEvidence {
487        &self.evidence
488    }
489
490    /// Matched transactions ordered by their position in the block.
491    #[must_use]
492    pub fn transactions(&self) -> &[Transaction] {
493        &self.transactions
494    }
495
496    /// Merge independently verified views of the same block.
497    ///
498    /// Identical Bloom filters should produce identical honest views. Taking
499    /// the conflict-checked union prevents one omitting peer from hiding a
500    /// transaction supplied with valid Merkle evidence by another peer; the
501    /// wallet's exact watch-set relevance filter still decides what persists.
502    pub fn merge_peer_views(blocks: &[Self]) -> Result<Self, WalletEvidenceError> {
503        let first = blocks.first().ok_or(WalletEvidenceError::EmptyPeerViews)?;
504        let header = first.evidence.header;
505        let total_transactions = first.evidence.total_transactions;
506        let mut matches = BTreeMap::<u32, MatchedTransaction>::new();
507        let mut positions = BTreeMap::<TransactionHash, u32>::new();
508        let mut transactions = BTreeMap::<TransactionHash, Transaction>::new();
509        for block in blocks {
510            if block.evidence.header != header
511                || block.evidence.total_transactions != total_transactions
512            {
513                return Err(WalletEvidenceError::PeerViewHeaderMismatch);
514            }
515            if block.transactions.len() != block.evidence.matches.len() {
516                return Err(WalletEvidenceError::PeerViewTransactionMismatch);
517            }
518            let mut block_transactions = BTreeMap::new();
519            for transaction in &block.transactions {
520                let hash = transaction.transaction_hash()?;
521                if block_transactions
522                    .insert(hash, transaction.clone())
523                    .is_some()
524                {
525                    return Err(WalletEvidenceError::PeerViewTransactionMismatch);
526                }
527            }
528            for matched in &block.evidence.matches {
529                let transaction = block_transactions
530                    .remove(&matched.hash)
531                    .ok_or(WalletEvidenceError::PeerViewTransactionMismatch)?;
532                if positions
533                    .insert(matched.hash, matched.index)
534                    .is_some_and(|position| position != matched.index)
535                    || matches
536                        .insert(matched.index, *matched)
537                        .is_some_and(|existing| existing.hash != matched.hash)
538                    || transactions
539                        .insert(matched.hash, transaction.clone())
540                        .is_some_and(|existing| existing != transaction)
541                {
542                    return Err(WalletEvidenceError::PeerViewConflict);
543                }
544            }
545            if !block_transactions.is_empty() {
546                return Err(WalletEvidenceError::PeerViewTransactionMismatch);
547            }
548        }
549        let matches = matches.into_values().collect::<Vec<_>>();
550        let mut merged_transactions = Vec::with_capacity(matches.len());
551        for matched in &matches {
552            merged_transactions.push(
553                transactions
554                    .remove(&matched.hash)
555                    .ok_or(WalletEvidenceError::PeerViewTransactionMismatch)?,
556            );
557        }
558        if !transactions.is_empty() {
559            return Err(WalletEvidenceError::PeerViewTransactionMismatch);
560        }
561        Ok(Self {
562            evidence: WalletBlockEvidence {
563                header,
564                total_transactions,
565                matches,
566            },
567            transactions: merged_transactions,
568        })
569    }
570}
571
572#[derive(Debug)]
573struct DecodedPartialMerkle {
574    total_transactions: u32,
575    matches: Vec<MatchedTransaction>,
576}
577
578fn decode_partial_merkle(
579    input: &[u8],
580    expected_hash: BlockHash,
581    expected_merkle_root: MerkleRoot,
582) -> Result<DecodedPartialMerkle, WalletEvidenceError> {
583    if input.len() > MAX_MERKLE_BLOCK_PAYLOAD_BYTES {
584        return Err(WalletEvidenceError::MerkleBlockTooLarge);
585    }
586    let mut decoder = Decoder::new(input);
587    let header = Header::decode(decoder.read_slice(HEADER_SIZE)?)?;
588    if header.block_hash() != expected_hash || header.merkle_root != expected_merkle_root {
589        return Err(WalletEvidenceError::WrongHeader);
590    }
591    let total_transactions = decoder.read_u32_le()?;
592    let total = total_transactions as usize;
593    if total == 0 {
594        return Err(WalletEvidenceError::ZeroTransactions);
595    }
596    if total > MAX_FILTERED_BLOCK_TRANSACTIONS {
597        return Err(WalletEvidenceError::TooManyTransactions);
598    }
599    let hash_count = decoder.read_compact_usize(total, "partial Merkle hashes")?;
600    let mut hashes = Vec::with_capacity(hash_count);
601    for _ in 0..hash_count {
602        hashes.push(decoder.read_array()?);
603    }
604    let flags = decoder.read_varbytes(MAX_PARTIAL_MERKLE_FLAG_BYTES, "partial Merkle flags")?;
605    decoder.finish()?;
606    if hashes.len() > total {
607        return Err(WalletEvidenceError::TooManyHashes);
608    }
609    if flags.len().saturating_mul(8) < hashes.len() {
610        return Err(WalletEvidenceError::FlagsTooSmall);
611    }
612
613    let mut height = 0_usize;
614    while tree_width(total, height) > 1 {
615        height = height
616            .checked_add(1)
617            .ok_or(WalletEvidenceError::ArithmeticOverflow)?;
618    }
619    let mut reader = PartialTreeReader {
620        total,
621        flags: &flags,
622        hashes: &hashes,
623        bits_used: 0,
624        hashes_used: 0,
625        matches: Vec::new(),
626        matched_hashes: HashSet::new(),
627    };
628    let root = reader.traverse(height, 0)?;
629    if reader.bits_used.div_ceil(8) != flags.len() {
630        return Err(WalletEvidenceError::UnusedFlagBits);
631    }
632    if reader.hashes_used != hashes.len() {
633        return Err(WalletEvidenceError::UnusedHashes);
634    }
635    if root != header.merkle_root.into_bytes() {
636        return Err(WalletEvidenceError::MerkleRootMismatch);
637    }
638    Ok(DecodedPartialMerkle {
639        total_transactions,
640        matches: reader.matches,
641    })
642}
643
644struct PartialTreeReader<'a> {
645    total: usize,
646    flags: &'a [u8],
647    hashes: &'a [[u8; 32]],
648    bits_used: usize,
649    hashes_used: usize,
650    matches: Vec<MatchedTransaction>,
651    matched_hashes: HashSet<TransactionHash>,
652}
653
654impl PartialTreeReader<'_> {
655    fn traverse(
656        &mut self,
657        height: usize,
658        position: usize,
659    ) -> Result<[u8; 32], WalletEvidenceError> {
660        let parent = self.read_bit()?;
661        if height == 0 || !parent {
662            let hash = self.read_hash()?;
663            if height == 0 && parent {
664                let transaction_hash = TransactionHash::new(hash);
665                if !self.matched_hashes.insert(transaction_hash) {
666                    return Err(WalletEvidenceError::DuplicateMatchedTransaction);
667                }
668                let index =
669                    u32::try_from(position).map_err(|_| WalletEvidenceError::ArithmeticOverflow)?;
670                self.matches.push(MatchedTransaction {
671                    hash: transaction_hash,
672                    index,
673                });
674                return Ok(hash_leaf(hash));
675            }
676            return Ok(hash);
677        }
678
679        let child_height = height
680            .checked_sub(1)
681            .ok_or(WalletEvidenceError::ArithmeticOverflow)?;
682        let left_position = position
683            .checked_mul(2)
684            .ok_or(WalletEvidenceError::ArithmeticOverflow)?;
685        let left = self.traverse(child_height, left_position)?;
686        let right = if left_position
687            .checked_add(1)
688            .ok_or(WalletEvidenceError::ArithmeticOverflow)?
689            < tree_width(self.total, child_height)
690        {
691            self.traverse(child_height, left_position + 1)?
692        } else {
693            hash_empty()
694        };
695        Ok(hash_internal(left, right))
696    }
697
698    fn read_bit(&mut self) -> Result<bool, WalletEvidenceError> {
699        let byte = self
700            .flags
701            .get(self.bits_used / 8)
702            .ok_or(WalletEvidenceError::ExhaustedFlags)?;
703        let bit = byte & (1_u8 << (self.bits_used % 8)) != 0;
704        self.bits_used = self
705            .bits_used
706            .checked_add(1)
707            .ok_or(WalletEvidenceError::ArithmeticOverflow)?;
708        Ok(bit)
709    }
710
711    fn read_hash(&mut self) -> Result<[u8; 32], WalletEvidenceError> {
712        let hash = self
713            .hashes
714            .get(self.hashes_used)
715            .copied()
716            .ok_or(WalletEvidenceError::ExhaustedHashes)?;
717        self.hashes_used = self
718            .hashes_used
719            .checked_add(1)
720            .ok_or(WalletEvidenceError::ArithmeticOverflow)?;
721        Ok(hash)
722    }
723}
724
725fn tree_width(total: usize, height: usize) -> usize {
726    let step = 1_usize << height;
727    total.div_ceil(step)
728}
729
730fn hash_empty() -> [u8; 32] {
731    blake2b_256(&[&[]])
732}
733
734fn hash_leaf(hash: [u8; 32]) -> [u8; 32] {
735    blake2b_256(&[&[0], &hash])
736}
737
738fn hash_internal(left: [u8; 32], right: [u8; 32]) -> [u8; 32] {
739    blake2b_256(&[&[1], &left, &right])
740}
741
742fn blake2b_256(parts: &[&[u8]]) -> [u8; 32] {
743    let mut hasher = Blake2b::<U32>::new();
744    for part in parts {
745        hasher.update(part);
746    }
747    hasher.finalize().into()
748}
749
750fn bloom_hash(value: &[u8], function: u32, tweak: u32) -> u32 {
751    let seed = function
752        .wrapping_mul(BLOOM_TWEAK_MULTIPLIER)
753        .wrapping_add(tweak);
754    murmur3(value, seed)
755}
756
757fn murmur3(value: &[u8], seed: u32) -> u32 {
758    const C1: u32 = 0xcc9e_2d51;
759    const C2: u32 = 0x1b87_3593;
760
761    let mut hash = seed;
762    let mut chunks = value.chunks_exact(4);
763    for chunk in &mut chunks {
764        let [first, second, third, fourth] = chunk else {
765            continue;
766        };
767        let mut word = u32::from_le_bytes([*first, *second, *third, *fourth]);
768        word = word.wrapping_mul(C1).rotate_left(15).wrapping_mul(C2);
769        hash ^= word;
770        hash = hash
771            .rotate_left(13)
772            .wrapping_mul(5)
773            .wrapping_add(0xe654_6b64);
774    }
775
776    let remainder = chunks.remainder();
777    let mut tail = 0_u32;
778    if let Some(byte) = remainder.get(2) {
779        tail ^= u32::from(*byte) << 16;
780    }
781    if let Some(byte) = remainder.get(1) {
782        tail ^= u32::from(*byte) << 8;
783    }
784    if let Some(byte) = remainder.first() {
785        tail ^= u32::from(*byte);
786        tail = tail.wrapping_mul(C1).rotate_left(15).wrapping_mul(C2);
787        hash ^= tail;
788    }
789
790    hash ^= value.len() as u32;
791    hash ^= hash >> 16;
792    hash = hash.wrapping_mul(0x85eb_ca6b);
793    hash ^= hash >> 13;
794    hash = hash.wrapping_mul(0xc2b2_ae35);
795    hash ^ (hash >> 16)
796}
797
798/// BIP37 filter construction or encoding failure.
799#[derive(Clone, Debug, Eq, Error, PartialEq)]
800#[non_exhaustive]
801pub enum BloomError {
802    /// Expected item count must be nonzero.
803    #[error("expected bloom-filter item count is zero")]
804    ZeroExpectedItems,
805    /// False-positive rate must be finite and strictly between zero and one.
806    #[error("invalid bloom-filter false-positive rate")]
807    InvalidFalsePositiveRate,
808    /// Filter exceeds HSD's 36,000-byte peer policy.
809    #[error("bloom filter exceeds HSD policy size")]
810    FilterTooLarge,
811    /// Filter exceeds HSD's 50-function peer policy.
812    #[error("bloom filter exceeds HSD hash-function policy")]
813    TooManyHashFunctions,
814    /// A wire filter may not have zero hash functions.
815    #[error("bloom filter has zero hash functions")]
816    ZeroHashFunctions,
817    /// A wire filter may not be empty.
818    #[error("bloom filter is empty")]
819    EmptyFilter,
820    /// Update byte is outside HSD's defined range.
821    #[error("invalid bloom-filter update mode")]
822    InvalidUpdate,
823    /// `filteradd` elements are limited to HSD's script-push bound.
824    #[error("filteradd element exceeds HSD policy size")]
825    ElementTooLarge,
826    /// Canonical little-endian wire decoding failed.
827    #[error(transparent)]
828    Decode(#[from] DecodeError),
829    /// An impossible locally constructed index was out of range.
830    #[error("bloom-filter internal invariant failed")]
831    InternalInvariant,
832}
833
834/// Filtered-block proof or exact transaction-correlation failure.
835#[derive(Debug, Error)]
836#[non_exhaustive]
837pub enum WalletEvidenceError {
838    /// At least one validated header is required per request.
839    #[error("filtered-block request is empty")]
840    EmptyBlockRequest,
841    /// One packet cannot exceed the shared standard inventory bound.
842    #[error("filtered-block request exceeds the standard inventory bound")]
843    TooManyBlockRequests,
844    /// A multi-peer union requires at least one independently verified view.
845    #[error("no verified peer block views were supplied")]
846    EmptyPeerViews,
847    /// Peer views refer to different headers or transaction totals.
848    #[error("verified peer block views disagree on the block anchor")]
849    PeerViewHeaderMismatch,
850    /// A verified peer view's matched hashes and transactions are inconsistent.
851    #[error("verified peer block view has inconsistent transaction correlation")]
852    PeerViewTransactionMismatch,
853    /// Verified views assign different hashes or bytes to one block position.
854    #[error("verified peer block views contain a conflicting transaction claim")]
855    PeerViewConflict,
856    /// MerkleBlock exceeds the strict maximum canonical payload.
857    #[error("MerkleBlock payload exceeds the local allocation bound")]
858    MerkleBlockTooLarge,
859    /// Canonical little-endian wire decoding failed.
860    #[error(transparent)]
861    Decode(#[from] DecodeError),
862    /// Embedded canonical Handshake header was malformed.
863    #[error(transparent)]
864    Header(#[from] HeaderError),
865    /// Embedded header was not the locally validated requested block.
866    #[error("MerkleBlock header does not match the requested validated header")]
867    WrongHeader,
868    /// A block cannot commit zero transactions.
869    #[error("MerkleBlock declares zero transactions")]
870    ZeroTransactions,
871    /// Transaction total exceeds HSD's block-size-derived bound.
872    #[error("MerkleBlock declares too many transactions")]
873    TooManyTransactions,
874    /// Partial tree supplied more hashes than transactions.
875    #[error("MerkleBlock contains too many hashes")]
876    TooManyHashes,
877    /// Flag bitfield cannot describe all supplied hashes.
878    #[error("MerkleBlock flag bitfield is too small")]
879    FlagsTooSmall,
880    /// Traversal exhausted the exact flag bitfield.
881    #[error("MerkleBlock traversal exhausted flag bits")]
882    ExhaustedFlags,
883    /// Traversal exhausted the exact hash vector.
884    #[error("MerkleBlock traversal exhausted hashes")]
885    ExhaustedHashes,
886    /// Canonical traversal did not consume the complete flag byte vector.
887    #[error("MerkleBlock contains unused flag bytes")]
888    UnusedFlagBits,
889    /// Canonical traversal did not consume the complete hash vector.
890    #[error("MerkleBlock contains unused hashes")]
891    UnusedHashes,
892    /// Reconstructed root differs from the committed header root.
893    #[error("MerkleBlock root does not match the validated header")]
894    MerkleRootMismatch,
895    /// Matched transaction hash appeared more than once.
896    #[error("MerkleBlock repeats a matched transaction hash")]
897    DuplicateMatchedTransaction,
898    /// Peer sent a transaction not proven by this MerkleBlock.
899    #[error("transaction was not matched by the current MerkleBlock")]
900    UnexpectedTransaction,
901    /// Two correlated transactions claimed the same block index.
902    #[error("duplicate matched transaction index")]
903    DuplicateTransactionIndex,
904    /// Not every matched transaction packet arrived.
905    #[error("matched transaction packets are incomplete")]
906    MissingTransactions,
907    /// Transaction hashing/encoding failed.
908    #[error(transparent)]
909    Transaction(#[from] TransactionError),
910    /// Bounded index arithmetic overflowed.
911    #[error("filtered-block arithmetic overflow")]
912    ArithmeticOverflow,
913}
914
915#[cfg(test)]
916#[allow(
917    clippy::unwrap_used,
918    reason = "tests fail immediately on invalid deterministic fixtures"
919)]
920mod tests {
921    use hns_header_consensus::Network;
922    use hns_primitives::BlockTime;
923
924    use super::*;
925
926    #[test]
927    fn murmur3_and_hsd_filter_encoding_match_reference_vectors() {
928        assert_eq!(murmur3(b"hello", 0), 0x248b_fa47);
929
930        let mut filter = HsdBloomFilter::new(24, 5, 0, BloomUpdate::All).unwrap();
931        filter
932            .insert(&hex::decode("99108ad8ed9bb6274d3980bab5a85c048f0950c8").unwrap())
933            .unwrap();
934        filter
935            .insert(&hex::decode("b5a2c786d9ef4658287ced5914b37a1b4aa32eee").unwrap())
936            .unwrap();
937        filter
938            .insert(&hex::decode("b9300670b4c5366e95b2699e8b18bc75e5f729c5").unwrap())
939            .unwrap();
940        assert_eq!(hex::encode(filter.encode()), "03614e9b050000000000000001");
941        assert_eq!(
942            HsdBloomFilter::decode_strict(&filter.encode()).unwrap(),
943            filter
944        );
945
946        let shape = HsdBloomFilter::from_rate(20_000, 0.001, 7, BloomUpdate::All).unwrap();
947        assert_eq!(shape.size_bits(), 287_544);
948        assert_eq!(shape.hash_functions(), 9);
949    }
950
951    #[test]
952    fn filter_packets_are_standard_and_policy_bounded() {
953        let mut filter = HsdBloomFilter::new(64, 3, 9, BloomUpdate::All).unwrap();
954        assert!(matches!(filter.load_packet(), Packet::FilterLoad(_)));
955        let add = filter.add_packet(&[4; 32]).unwrap();
956        assert_eq!(add, Packet::FilterAdd([vec![32], vec![4; 32]].concat()));
957        assert!(filter.contains(&[4; 32]));
958        assert!(matches!(
959            filter.add_packet(&vec![0; MAX_FILTER_ADD_ELEMENT_BYTES + 1]),
960            Err(BloomError::ElementTooLarge)
961        ));
962    }
963
964    #[test]
965    fn verifies_genesis_zero_match_tree_against_validated_header() {
966        let now = BlockTime::new(1_700_000_000);
967        let chain = hns_light_chain::LightChain::from_genesis(
968            Network::Regtest,
969            now,
970            hns_light_chain::ChainLimits::default(),
971        )
972        .unwrap();
973        let entry = chain.tip();
974        let header = Network::Regtest.parameters().genesis_header();
975        let mut encoder = Encoder::new();
976        encoder.put_bytes(&header.encode());
977        encoder.put_u32_le(1);
978        encoder.put_compact_size(1);
979        encoder.put_bytes(header.merkle_root.as_bytes());
980        encoder.put_varbytes(&[0]);
981
982        let evidence =
983            WalletBlockEvidence::decode_for_header(&encoder.into_bytes(), entry).unwrap();
984        assert_eq!(evidence.header(), entry.into());
985        assert_eq!(evidence.total_transactions(), 1);
986        assert!(evidence.matches().is_empty());
987        assert!(evidence.collect().unwrap().finish().is_ok());
988    }
989
990    #[test]
991    fn matched_tree_and_collector_require_exact_transaction_hash() {
992        let transaction = Transaction {
993            version: 0,
994            inputs: Vec::new(),
995            outputs: Vec::new(),
996            locktime: 0,
997        };
998        let transaction_hash = transaction.transaction_hash().unwrap();
999        let header = Header {
1000            merkle_root: hash_leaf(transaction_hash.into_bytes()).into(),
1001            ..Header::default()
1002        };
1003        let expected_hash = header.block_hash();
1004        let mut encoder = Encoder::new();
1005        encoder.put_bytes(&header.encode());
1006        encoder.put_u32_le(1);
1007        encoder.put_compact_size(1);
1008        encoder.put_bytes(transaction_hash.as_bytes());
1009        encoder.put_varbytes(&[1]);
1010        let decoded =
1011            decode_partial_merkle(&encoder.into_bytes(), expected_hash, header.merkle_root)
1012                .unwrap();
1013        assert_eq!(decoded.matches.len(), 1);
1014
1015        let chain = hns_light_chain::LightChain::from_genesis(
1016            Network::Regtest,
1017            BlockTime::new(1_700_000_000),
1018            hns_light_chain::ChainLimits::default(),
1019        )
1020        .unwrap();
1021        let evidence = WalletBlockEvidence {
1022            header: chain.tip().into(),
1023            total_transactions: 1,
1024            matches: decoded.matches,
1025        };
1026        let mut collector = evidence.collect().unwrap();
1027        assert_eq!(collector.admit(transaction.clone()).unwrap(), 0);
1028        assert!(matches!(
1029            collector.admit(transaction),
1030            Err(WalletEvidenceError::UnexpectedTransaction)
1031        ));
1032        let complete = collector.finish().unwrap();
1033        assert_eq!(complete.transactions().len(), 1);
1034    }
1035
1036    #[test]
1037    fn merges_conflict_checked_independent_peer_views() {
1038        let chain = hns_light_chain::LightChain::from_genesis(
1039            Network::Regtest,
1040            BlockTime::new(1_700_000_000),
1041            hns_light_chain::ChainLimits::default(),
1042        )
1043        .unwrap();
1044        let header = WalletHeaderAnchor::from(chain.tip());
1045        let first_transaction = Transaction {
1046            version: 0,
1047            inputs: Vec::new(),
1048            outputs: Vec::new(),
1049            locktime: 0,
1050        };
1051        let second_transaction = Transaction {
1052            version: 0,
1053            inputs: Vec::new(),
1054            outputs: Vec::new(),
1055            locktime: 1,
1056        };
1057        let first_hash = first_transaction.transaction_hash().unwrap();
1058        let second_hash = second_transaction.transaction_hash().unwrap();
1059        let first_view = VerifiedWalletBlock {
1060            evidence: WalletBlockEvidence {
1061                header,
1062                total_transactions: 2,
1063                matches: vec![MatchedTransaction {
1064                    index: 0,
1065                    hash: first_hash,
1066                }],
1067            },
1068            transactions: vec![first_transaction.clone()],
1069        };
1070        let second_view = VerifiedWalletBlock {
1071            evidence: WalletBlockEvidence {
1072                header,
1073                total_transactions: 2,
1074                matches: vec![MatchedTransaction {
1075                    index: 1,
1076                    hash: second_hash,
1077                }],
1078            },
1079            transactions: vec![second_transaction.clone()],
1080        };
1081
1082        let merged =
1083            VerifiedWalletBlock::merge_peer_views(&[first_view.clone(), second_view]).unwrap();
1084        assert_eq!(merged.evidence().matches().len(), 2);
1085        assert_eq!(
1086            merged.transactions(),
1087            &[first_transaction, second_transaction.clone()]
1088        );
1089
1090        let conflicting_view = VerifiedWalletBlock {
1091            evidence: WalletBlockEvidence {
1092                header,
1093                total_transactions: 2,
1094                matches: vec![MatchedTransaction {
1095                    index: 0,
1096                    hash: second_hash,
1097                }],
1098            },
1099            transactions: vec![second_transaction],
1100        };
1101        assert!(matches!(
1102            VerifiedWalletBlock::merge_peer_views(&[first_view, conflicting_view]),
1103            Err(WalletEvidenceError::PeerViewConflict)
1104        ));
1105    }
1106
1107    #[test]
1108    fn rejects_wrong_header_root_and_noncanonical_tree_consumption() {
1109        let header = Header {
1110            merkle_root: hash_leaf([3; 32]).into(),
1111            ..Header::default()
1112        };
1113        let expected_hash = header.block_hash();
1114        let mut encoder = Encoder::new();
1115        encoder.put_bytes(&header.encode());
1116        encoder.put_u32_le(1);
1117        encoder.put_compact_size(1);
1118        encoder.put_bytes(&[4; 32]);
1119        encoder.put_varbytes(&[1]);
1120        assert!(matches!(
1121            decode_partial_merkle(&encoder.into_bytes(), expected_hash, header.merkle_root),
1122            Err(WalletEvidenceError::MerkleRootMismatch)
1123        ));
1124
1125        let mut encoder = Encoder::new();
1126        encoder.put_bytes(&header.encode());
1127        encoder.put_u32_le(1);
1128        encoder.put_compact_size(1);
1129        encoder.put_bytes(&[3; 32]);
1130        encoder.put_varbytes(&[0, 0]);
1131        assert!(matches!(
1132            decode_partial_merkle(&encoder.into_bytes(), expected_hash, header.merkle_root),
1133            Err(WalletEvidenceError::UnusedFlagBits)
1134        ));
1135    }
1136}