1#![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
34pub const MAX_BLOOM_FILTER_BYTES: usize = 36_000;
36pub const MAX_BLOOM_HASH_FUNCTIONS: u32 = 50;
38pub const MAX_FILTER_ADD_ELEMENT_BYTES: usize = 520;
40pub const MAX_FILTERED_BLOCK_TRANSACTIONS: usize = 1_000_000 / 60;
42pub const MAX_PARTIAL_MERKLE_FLAG_BYTES: usize = (MAX_FILTERED_BLOCK_TRANSACTIONS * 2).div_ceil(8);
44pub 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#[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 #[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 #[must_use]
85 pub const fn height(self) -> Height {
86 self.height
87 }
88
89 #[must_use]
91 pub const fn hash(self) -> BlockHash {
92 self.hash
93 }
94
95 #[must_use]
97 pub const fn previous_block(self) -> BlockHash {
98 self.previous_block
99 }
100
101 #[must_use]
103 pub const fn tree_root(self) -> TreeRoot {
104 self.tree_root
105 }
106
107 #[must_use]
109 pub const fn merkle_root(self) -> MerkleRoot {
110 self.merkle_root
111 }
112
113 #[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#[repr(u8)]
135#[derive(Clone, Copy, Debug, Eq, PartialEq)]
136pub enum BloomUpdate {
137 None = 0,
139 All = 1,
141 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#[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 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 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 #[must_use]
225 pub fn size_bits(&self) -> usize {
226 self.bytes.len() * 8
227 }
228
229 #[must_use]
231 pub const fn hash_functions(&self) -> u32 {
232 self.hash_functions
233 }
234
235 #[must_use]
237 pub const fn tweak(&self) -> u32 {
238 self.tweak
239 }
240
241 #[must_use]
243 pub const fn update(&self) -> BloomUpdate {
244 self.update
245 }
246
247 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 #[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 #[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 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 #[must_use]
311 pub fn load_packet(&self) -> Packet {
312 Packet::FilterLoad(self.encode())
313 }
314
315 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
327pub 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#[derive(Clone, Copy, Debug, Eq, PartialEq)]
348pub struct MatchedTransaction {
349 hash: TransactionHash,
350 index: u32,
351}
352
353impl MatchedTransaction {
354 #[must_use]
356 pub const fn hash(self) -> TransactionHash {
357 self.hash
358 }
359
360 #[must_use]
362 pub const fn index(self) -> u32 {
363 self.index
364 }
365}
366
367#[derive(Clone, Debug, Eq, PartialEq)]
369pub struct WalletBlockEvidence {
370 header: WalletHeaderAnchor,
371 total_transactions: u32,
372 matches: Vec<MatchedTransaction>,
373}
374
375impl WalletBlockEvidence {
376 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 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 #[must_use]
400 pub const fn header(&self) -> WalletHeaderAnchor {
401 self.header
402 }
403
404 #[must_use]
406 pub const fn total_transactions(&self) -> u32 {
407 self.total_transactions
408 }
409
410 #[must_use]
412 pub fn matches(&self) -> &[MatchedTransaction] {
413 &self.matches
414 }
415
416 pub fn collect(self) -> Result<FilteredBlockCollector, WalletEvidenceError> {
418 FilteredBlockCollector::new(self)
419 }
420}
421
422#[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 #[must_use]
447 pub fn remaining(&self) -> usize {
448 self.pending.len()
449 }
450
451 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 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#[derive(Clone, Debug, Eq, PartialEq)]
478pub struct VerifiedWalletBlock {
479 evidence: WalletBlockEvidence,
480 transactions: Vec<Transaction>,
481}
482
483impl VerifiedWalletBlock {
484 #[must_use]
486 pub const fn evidence(&self) -> &WalletBlockEvidence {
487 &self.evidence
488 }
489
490 #[must_use]
492 pub fn transactions(&self) -> &[Transaction] {
493 &self.transactions
494 }
495
496 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#[derive(Clone, Debug, Eq, Error, PartialEq)]
800#[non_exhaustive]
801pub enum BloomError {
802 #[error("expected bloom-filter item count is zero")]
804 ZeroExpectedItems,
805 #[error("invalid bloom-filter false-positive rate")]
807 InvalidFalsePositiveRate,
808 #[error("bloom filter exceeds HSD policy size")]
810 FilterTooLarge,
811 #[error("bloom filter exceeds HSD hash-function policy")]
813 TooManyHashFunctions,
814 #[error("bloom filter has zero hash functions")]
816 ZeroHashFunctions,
817 #[error("bloom filter is empty")]
819 EmptyFilter,
820 #[error("invalid bloom-filter update mode")]
822 InvalidUpdate,
823 #[error("filteradd element exceeds HSD policy size")]
825 ElementTooLarge,
826 #[error(transparent)]
828 Decode(#[from] DecodeError),
829 #[error("bloom-filter internal invariant failed")]
831 InternalInvariant,
832}
833
834#[derive(Debug, Error)]
836#[non_exhaustive]
837pub enum WalletEvidenceError {
838 #[error("filtered-block request is empty")]
840 EmptyBlockRequest,
841 #[error("filtered-block request exceeds the standard inventory bound")]
843 TooManyBlockRequests,
844 #[error("no verified peer block views were supplied")]
846 EmptyPeerViews,
847 #[error("verified peer block views disagree on the block anchor")]
849 PeerViewHeaderMismatch,
850 #[error("verified peer block view has inconsistent transaction correlation")]
852 PeerViewTransactionMismatch,
853 #[error("verified peer block views contain a conflicting transaction claim")]
855 PeerViewConflict,
856 #[error("MerkleBlock payload exceeds the local allocation bound")]
858 MerkleBlockTooLarge,
859 #[error(transparent)]
861 Decode(#[from] DecodeError),
862 #[error(transparent)]
864 Header(#[from] HeaderError),
865 #[error("MerkleBlock header does not match the requested validated header")]
867 WrongHeader,
868 #[error("MerkleBlock declares zero transactions")]
870 ZeroTransactions,
871 #[error("MerkleBlock declares too many transactions")]
873 TooManyTransactions,
874 #[error("MerkleBlock contains too many hashes")]
876 TooManyHashes,
877 #[error("MerkleBlock flag bitfield is too small")]
879 FlagsTooSmall,
880 #[error("MerkleBlock traversal exhausted flag bits")]
882 ExhaustedFlags,
883 #[error("MerkleBlock traversal exhausted hashes")]
885 ExhaustedHashes,
886 #[error("MerkleBlock contains unused flag bytes")]
888 UnusedFlagBits,
889 #[error("MerkleBlock contains unused hashes")]
891 UnusedHashes,
892 #[error("MerkleBlock root does not match the validated header")]
894 MerkleRootMismatch,
895 #[error("MerkleBlock repeats a matched transaction hash")]
897 DuplicateMatchedTransaction,
898 #[error("transaction was not matched by the current MerkleBlock")]
900 UnexpectedTransaction,
901 #[error("duplicate matched transaction index")]
903 DuplicateTransactionIndex,
904 #[error("matched transaction packets are incomplete")]
906 MissingTransactions,
907 #[error(transparent)]
909 Transaction(#[from] TransactionError),
910 #[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}