Skip to main content

hopr_protocol_hopr/
replay_filter.rs

1//! Replay detection for incoming HOPR packets.
2//!
3//! A packet is replayed when the same wire bytes are delivered twice. Recognising that matters: the alternative is
4//! a header MAC verification, a payload permutation and a message parse for every duplicate an attacker cares to
5//! send.
6//!
7//! The token is the packet's Sphinx authentication tag, derived from the shared secret with the local node. That
8//! secret requires the elliptic-curve Diffie-Hellman, which cannot be avoided - but everything after it can, which
9//! is why the tag is handed to the filter from inside the Sphinx decode rather than after it (see
10//! [`HoprPacket::from_incoming_checked`](hopr_crypto_packet::prelude::HoprPacket::from_incoming_checked)).
11//!
12//! Keying on the derived tag rather than on the wire `alpha` matters because the tag depends on the node's
13//! private key. Anybody can *compute* a tag from a chosen alpha and the node's public key, so the early
14//! [`TagReplayFilter::contains`] check is not a proof of anything; what costs an attacker a well-formed packet is
15//! getting a token *recorded*, which [`TagReplayFilter::commit`] does only after the header MAC has verified.
16//! Rotating the filter out therefore needs packets the sender could actually authenticate, not merely bytes whose
17//! first field the attacker chose.
18//!
19//! # Why a rolling filter rather than one Bloom filter that resets
20//!
21//! A Bloom filter is sized for a fixed number of items and cannot grow. The previous implementation answered
22//! overflow by clearing the entire bitmap, which forgets *every* packet at once. It cleared once per capacity: the
23//! insertion that found the filter full of other tags reset it, so the history of all peers was dropped on a
24//! single packet.
25//!
26//! Instead, each shard keeps two generations. When the current one fills it becomes the previous one and a fresh
27//! current is allocated, so a token is remembered for at least one full generation *of its shard* - a floor that no
28//! insertion pattern can take away, where the old design had none. The floor is per shard rather than global: a
29//! token's shard is chosen by a keyed hash and ages out with that shard alone, so the configured count is a bound on
30//! total retention only when traffic spreads evenly across shards (see [`ReplayFilterConfig::max_tracked_packets`]).
31//!
32//! Aging out is proportional to insert volume (a packet count, not wall time). The cost of shortening the window is
33//! *authenticated* packets, not paid ones: a token is committed once the header MAC verifies, which still precedes
34//! ticket validation, so a direct neighbour can rotate generations with packets it does not pay for. Each must
35//! still authenticate under the shared secret, which costs it the same elliptic-curve work a legitimate sender
36//! pays, and the window it shortens is bounded below by one full generation.
37//!
38//! The shard a token lands in is chosen by a hash keyed per filter instance, so a sender - who computes the tag -
39//! cannot aim its packets at one shard and evict only that shard's history.
40//!
41//! # Why sharded
42//!
43//! The filter is consulted by every concurrent decode task. A single mutex serialized them on one cache line;
44//! sharding by token hash divides that contention by the shard count without changing the semantics, because the
45//! filter is a set either way.
46//!
47//! The namespace is deliberately global rather than per previous hop: the token names the packet, not the sender,
48//! so a replay injected through a different peer ID is still caught. The cost is that one high-volume peer
49//! advances rotations for everyone; that residual is bounded by the generation floor rather than eliminated.
50
51use hopr_api::types::crypto_random::random_bytes;
52
53/// The token a replay filter is keyed on: the packet's Sphinx authentication tag.
54///
55/// The tag is derived from the shared secret with the local node, so only a party that can derive that secret can
56/// produce one - an attacker cannot insert arbitrary tokens to age the filter out without paying the same
57/// elliptic-curve work per packet that a legitimate sender does.
58pub type ReplayToken = hopr_api::types::crypto::types::PacketTag;
59
60/// Configuration of the [`TagReplayFilter`].
61///
62/// The two fields are validated together: `shards` must be a power of two in range, `max_tracked_packets` must be
63/// at least [`MIN_TRACKED_PACKETS`], and the capacity must leave every shard at least [`MIN_CAPACITY_PER_SHARD`]
64/// slots, i.e. `max_tracked_packets >= shards * MIN_CAPACITY_PER_SHARD`. That last condition is what the field-wise
65/// ranges cannot express on their own - the floor capacity together with the shard ceiling satisfies both of them
66/// yet leaves a shard with a single slot, which rotates on every distinct token.
67#[derive(Clone, Copy, Debug, PartialEq, Eq, smart_default::SmartDefault, validator::Validate)]
68#[cfg_attr(
69    feature = "serde",
70    derive(serde::Serialize, serde::Deserialize),
71    serde(deny_unknown_fields)
72)]
73#[validate(schema(function = "validate_capacity_per_shard"))]
74pub struct ReplayFilterConfig {
75    /// Number of tokens the filter remembers per generation, across all shards.
76    ///
77    /// This is the capacity of one generation, split evenly across the shards, and retention is **per shard**: a
78    /// token stays known until its shard has taken `max_tracked_packets / shards` further distinct tokens, twice
79    /// over (once to retire it, once more to drop the retired generation). So a token survives roughly this many
80    /// *total* inserts only if traffic spreads evenly across shards - which a keyed shard hash makes the expected
81    /// case, but it is not a hard global bound. Must leave every shard at least [`MIN_CAPACITY_PER_SHARD`] slots,
82    /// i.e. be at least `shards * MIN_CAPACITY_PER_SHARD` (and at least [`MIN_TRACKED_PACKETS`]).
83    ///
84    /// At the default false-positive rate the bitmap costs roughly three bytes per token per generation, so a
85    /// decoder ultimately holds about this many megabytes, twice over once a shard has rotated. Generations are
86    /// allocated on first insertion, so the footprint grows with traffic rather than being paid at construction;
87    /// at the default it reaches a little under 32 MB per decoder, rising to about 63 MB after every shard has
88    /// rotated once.
89    ///
90    /// Default is 10 000 000.
91    #[default(default_max_tracked_packets())]
92    // Concrete numbers in the message: `validator` takes a literal, so the constants cannot be interpolated here.
93    // The test `the_tracked_packet_floor_agrees_with_the_validator` keeps them in step.
94    #[validate(
95        range(
96            min = MIN_TRACKED_PACKETS,
97            max = MAX_TRACKED_PACKETS,
98            message = "max_tracked_packets must be between 4096 and 100000000"
99        )
100    )]
101    #[cfg_attr(feature = "serde", serde(default = "default_max_tracked_packets"))]
102    pub max_tracked_packets: usize,
103    /// Number of independent shards.
104    ///
105    /// Each shard has its own generation state and lock, so this divides both the memory high-water mark and the
106    /// lock contention. It must be a power of two, which the validator enforces so that shard selection is a mask
107    /// rather than a division.
108    ///
109    /// Default is 64.
110    #[default(default_shards())]
111    #[validate(custom(function = "validate_shards"))]
112    #[cfg_attr(feature = "serde", serde(default = "default_shards"))]
113    pub shards: usize,
114}
115
116/// Lower bound on the number of tokens a single shard holds per generation, enforced by the validator.
117///
118/// The check and the insertion are two separate lock acquisitions with the whole decode between them, so a token
119/// committed by one decode can be lost to a second one only if the shard rotates *twice* in that window - that is,
120/// if two full generations are inserted into one shard while a single packet is being decoded. One slot per shard
121/// would make that two packets; this floor keeps the window at the same order as the default configuration's.
122pub const MIN_CAPACITY_PER_SHARD: usize = 64;
123/// Lower bound on [`ReplayFilterConfig::max_tracked_packets`], enforced by the validator.
124///
125/// Sized so that the default shard count gets [`MIN_CAPACITY_PER_SHARD`] slots each.
126pub const MIN_TRACKED_PACKETS: usize = MIN_CAPACITY_PER_SHARD * DEFAULT_SHARDS;
127/// Lower bound on [`ReplayFilterConfig::shards`], enforced by the validator.
128pub const MIN_SHARDS: usize = 1;
129/// Upper bound on [`ReplayFilterConfig::shards`], enforced by the validator.
130pub const MAX_SHARDS: usize = 4096;
131/// Upper bound on [`ReplayFilterConfig::max_tracked_packets`], enforced by the validator.
132///
133/// The bound exists because generations are allocated lazily: without it, a typo in the capacity would surface as a
134/// failed allocation inside the decode path on the first packet for a shard, rather than as a rejected
135/// configuration at startup. One hundred million tokens is about 320 MB per generation at the default rate, which
136/// is the point past which a node's own memory, not its traffic, is the constraint.
137pub const MAX_TRACKED_PACKETS: usize = 100_000_000;
138/// Default for [`ReplayFilterConfig::shards`].
139const DEFAULT_SHARDS: usize = 64;
140/// Default for [`ReplayFilterConfig::max_tracked_packets`].
141const DEFAULT_MAX_TRACKED_PACKETS: usize = 10_000_000;
142/// False-positive rate of a single generation.
143///
144/// [`TagReplayFilter::contains`] consults two generations, so the rate a caller observes is the union of the two.
145/// Halving the per-generation rate keeps that union at the 1e-5 the single-filter design used; because the bitmap
146/// size grows with `ln(1/p)`, halving `p` costs only a few percent per generation. Holding two generations is what
147/// doubles the total: a decoder now allocates roughly twice the bitmap it did, against a retention floor that is no
148/// longer zero.
149const GENERATION_FALSE_POSITIVE_RATE: f64 = 0.000_005;
150
151/// Keyed hash over `token`, used to pick a shard.
152///
153/// `SipHasher13` with an explicit key, not `std::hash::DefaultHasher`: the latter's keys are fixed, so a sender who
154/// computes the tag could predict the shard exactly as well as with no hash at all.
155fn keyed_hash(key: &[u8; 16], token: &ReplayToken) -> u64 {
156    use std::hash::Hasher as _;
157    let mut hasher = siphasher::sip::SipHasher13::new_with_key(key);
158    hasher.write(token);
159    hasher.finish()
160}
161
162/// `serde`/`SmartDefault` default for [`ReplayFilterConfig::max_tracked_packets`].
163fn default_max_tracked_packets() -> usize {
164    DEFAULT_MAX_TRACKED_PACKETS
165}
166
167/// `serde`/`SmartDefault` default for [`ReplayFilterConfig::shards`].
168fn default_shards() -> usize {
169    DEFAULT_SHARDS
170}
171
172/// Rejects a configuration whose capacity does not give every shard [`MIN_CAPACITY_PER_SHARD`] slots.
173///
174/// The field-wise ranges cannot express this: `max_tracked_packets` has a floor and `shards` has a ceiling, but
175/// nothing stops the ceiling from exceeding the floor divided by the shard count. [`TagReplayFilter::new`] would
176/// otherwise have to clamp, silently remembering fewer tokens than the configuration asked for.
177///
178/// The per-shard floor is more than "at least one": a shard with a single slot rotates on every distinct token, and
179/// since the check and the commit are separate lock acquisitions, two rotations during one decode would let the
180/// same packet through twice. See [`MIN_CAPACITY_PER_SHARD`].
181fn validate_capacity_per_shard(cfg: &ReplayFilterConfig) -> Result<(), validator::ValidationError> {
182    if cfg.shards == 0 {
183        return Ok(());
184    }
185
186    let per_shard = cfg.max_tracked_packets / cfg.shards;
187    if per_shard < MIN_CAPACITY_PER_SHARD {
188        let required = cfg.shards * MIN_CAPACITY_PER_SHARD;
189        let mut err = validator::ValidationError::new("max_tracked_packets");
190        err.message = Some(
191            format!(
192                "max_tracked_packets must be at least {required} for {} shards ({} per shard), got {}",
193                cfg.shards, MIN_CAPACITY_PER_SHARD, cfg.max_tracked_packets
194            )
195            .into(),
196        );
197        return Err(err);
198    }
199    Ok(())
200}
201
202/// Rejects a shard count that is out of range or not a power of two.
203///
204/// Power of two so [`TagReplayFilter::shard_for`] can mask rather than divide, and so every shard stays addressable.
205fn validate_shards(shards: usize) -> Result<(), validator::ValidationError> {
206    if !(MIN_SHARDS..=MAX_SHARDS).contains(&shards) || !shards.is_power_of_two() {
207        let mut err = validator::ValidationError::new("shards");
208        err.message = Some(format!("shards must be a power of two between {MIN_SHARDS} and {MAX_SHARDS}").into());
209        return Err(err);
210    }
211    Ok(())
212}
213
214#[cfg(all(feature = "telemetry", not(test)))]
215lazy_static::lazy_static! {
216    /// Counts shard rotations, i.e. how often a generation of replay history was dropped.
217    ///
218    /// Initialised lazily on first use; a sustained rate here means the replay window is shrinking faster than the
219    /// configured capacity suggests it should.
220    static ref METRIC_REPLAY_FILTER_ROTATIONS: hopr_api::types::telemetry::SimpleCounter =
221        hopr_api::types::telemetry::SimpleCounter::new(
222            "hopr_replay_filter_rotations_total",
223            "Replay filter generations dropped because their shard filled; each rotation shortens the window in which a packet is still recognised as a replay",
224        )
225        .unwrap();
226}
227
228/// One generation pair of a shard.
229#[derive(Debug)]
230struct ReplayShard {
231    /// The generation currently accepting insertions.
232    ///
233    /// Allocated on the first insertion, not when the filter is built: at the default configuration a generation
234    /// is tens of megabytes, and a node that has not yet received a packet should not have paid for every shard of
235    /// it - nor should every `HoprDecoder` construction in a test or a bench.
236    current: Option<bloomfilter::Bloom<ReplayToken>>,
237    /// The generation that was current until the last rotation, if any.
238    ///
239    /// Allocated lazily too: a shard that never fills its first generation never pays for a second bitmap.
240    previous: Option<bloomfilter::Bloom<ReplayToken>>,
241    /// Number of tokens inserted into [`Self::current`].
242    count: usize,
243    /// Number of tokens a single generation holds before the shard rotates.
244    capacity: usize,
245}
246
247impl ReplayShard {
248    /// Creates an empty shard that will hold `capacity` tokens per generation.
249    fn new(capacity: usize) -> Self {
250        Self {
251            current: None,
252            previous: None,
253            count: 0,
254            capacity,
255        }
256    }
257
258    /// Allocates one generation sized for `capacity` tokens.
259    fn generation(capacity: usize) -> bloomfilter::Bloom<ReplayToken> {
260        bloomfilter::Bloom::new_for_fp_rate_with_seed(capacity, GENERATION_FALSE_POSITIVE_RATE, &random_bytes())
261            .expect("bloom filter with the specified capacity is constructible")
262    }
263
264    /// Whether either generation holds `token`.
265    fn contains(&self, token: &ReplayToken) -> bool {
266        self.current.as_ref().is_some_and(|current| current.check(token))
267            || self.previous.as_ref().is_some_and(|previous| previous.check(token))
268    }
269
270    /// Inserts `token` unless it is already known. Returns `true` if it was already known.
271    fn check_and_set(&mut self, token: &ReplayToken) -> bool {
272        // Both generations are consulted *before* any rotation. Checking them after would mis-handle the exact
273        // case where it matters most: a duplicate that is the token which filled the generation is in the
274        // outgoing `current`, which the rotation is about to move into `previous` - so a check made before the
275        // rotation would miss it and re-admit it into the fresh generation as a brand-new packet.
276        if self.contains(token) {
277            return true;
278        }
279
280        if self.count == self.capacity {
281            // The current generation is full. The oldest one goes, the current one becomes the previous one, and
282            // the token is recorded in a fresh generation.
283            //
284            // A rotation is normal in this design, so it is `debug`: at the default capacity a busy node rotates
285            // every few tens of seconds, and warning on each would be noise. The counter is the signal an operator
286            // alerts on; this line is for chasing a single rotation, and it is logged while the shard is locked.
287            tracing::debug!(
288                capacity = self.capacity,
289                "replay filter shard rotated; its oldest generation was dropped"
290            );
291            #[cfg(all(feature = "telemetry", not(test)))]
292            METRIC_REPLAY_FILTER_ROTATIONS.increment();
293            self.previous = Some(std::mem::replace(
294                self.current.get_or_insert_with(|| Self::generation(self.capacity)),
295                Self::generation(self.capacity),
296            ));
297            self.count = 0;
298        }
299
300        self.current
301            .get_or_insert_with(|| Self::generation(self.capacity))
302            .set(token);
303        self.count += 1;
304        false
305    }
306}
307
308/// Replay-detecting filter over packet replay tokens.
309///
310/// Each of the shards keeps two generations of a Bloom filter. When the current one fills it becomes the previous
311/// one and a fresh current is allocated, so a token is remembered for at least one full generation of its shard -
312/// the floor the previous single-filter design did not have, since it answered overflow by clearing every tag at
313/// once. See [`ReplayFilterConfig::max_tracked_packets`] for what that means for the configured total.
314///
315/// Sharding by token divides both the lock contention of the decode path and the memory high-water mark. The
316/// namespace is global rather than per previous hop: the token names the packet, not the sender, so a replay
317/// injected through a different peer ID is still caught.
318#[derive(Debug)]
319pub struct TagReplayFilter {
320    /// Shards, each independently locked. The count is a power of two, so selection is a mask.
321    shards: Box<[parking_lot::Mutex<ReplayShard>]>,
322    /// Key for shard selection, derived per filter instance.
323    ///
324    /// The tag is computed by the packet's creator, so indexing shards on its raw bytes would let a sender aim
325    /// every packet at one shard - 1/64 of the traffic would evict that shard's history. Hashing with a
326    /// per-instance key makes the shard unpredictable until a token has been seen, which restores the spread.
327    shard_key: [u8; 16],
328}
329
330impl TagReplayFilter {
331    /// Creates a filter holding `cfg.max_tracked_packets` tokens per generation, split evenly across `cfg.shards`.
332    ///
333    /// A validated configuration gives every shard at least [`MIN_CAPACITY_PER_SHARD`] slots, and the total is then
334    /// `capacity / shards * shards`, i.e. within `shards - 1` of the configured value. Only an unvalidated
335    /// configuration can land here with a smaller share, which the `.max(1)` below keeps from producing a
336    /// zero-sized Bloom filter.
337    pub fn new(cfg: &ReplayFilterConfig) -> Self {
338        // Clamped first, because an unvalidated `shards` - `new` is public and `HoprDecoder::new` does not
339        // validate - could otherwise overflow `next_power_of_two` (panic in debug, zero in release) or try to
340        // allocate an unbounded number of shards.
341        //
342        // Then rounded up to a power of two: `shard_for`'s mask addresses only the first `2^k` shards, so an odd
343        // count would silently waste the rest of the configured capacity.
344        let shards = cfg.shards.clamp(MIN_SHARDS, MAX_SHARDS).next_power_of_two();
345        // A validated configuration is already in range; an unvalidated one - `new` is public and the decoder does
346        // not validate - is clamped here rather than left to fail allocating a generation inside the decode path.
347        let capacity_per_shard = (cfg.max_tracked_packets.min(MAX_TRACKED_PACKETS) / shards).max(1);
348
349        Self {
350            shards: (0..shards)
351                .map(|_| parking_lot::Mutex::new(ReplayShard::new(capacity_per_shard)))
352                .collect(),
353            shard_key: random_bytes(),
354        }
355        .with_metrics_registered()
356    }
357
358    /// Registers this type's telemetry at construction, so the series exists before the first rotation.
359    ///
360    /// Registering lazily on first use would leave `hopr_replay_filter_rotations_total` absent until a rotation
361    /// happened - and `rate()`/`increase()` do not count the first increment of a series that did not exist before
362    /// it - and would run the registration, and its `unwrap`, inside the decode path while a shard is locked.
363    fn with_metrics_registered(self) -> Self {
364        #[cfg(all(feature = "telemetry", not(test)))]
365        lazy_static::initialize(&METRIC_REPLAY_FILTER_ROTATIONS);
366        self
367    }
368
369    /// Number of shards, for tests and telemetry.
370    pub fn shards(&self) -> usize {
371        self.shards.len()
372    }
373
374    /// Total number of tokens the filter remembers per generation.
375    pub fn capacity(&self) -> usize {
376        self.shards.iter().map(|shard| shard.lock().capacity).sum()
377    }
378
379    /// Number of tokens inserted into the current generations, summed across shards, for tests and telemetry.
380    pub fn count(&self) -> usize {
381        self.shards.iter().map(|shard| shard.lock().count).sum()
382    }
383
384    /// Returns `true` if `token` is known to the filter. False positives are possible, false negatives are not
385    /// until the token's generation rotates out.
386    ///
387    /// A hit here means "seen before" up to the filter's false-positive rate; a miss means "new" without exception.
388    /// The value is only meaningful once a header MAC has verified it - a tag is computable by anyone from the
389    /// node's public key, so an *unrecorded* tag proves nothing.
390    pub fn contains(&self, token: &ReplayToken) -> bool {
391        self.shard_for(token).lock().contains(token)
392    }
393
394    /// Records `token` and returns whether it was already known.
395    ///
396    /// A `true` return means the token was inserted by a concurrent decode of the same packet between the
397    /// [`Self::contains`] check and this call, so the caller holds the duplicate.
398    pub fn commit(&self, token: &ReplayToken) -> bool {
399        self.shard_for(token).lock().check_and_set(token)
400    }
401
402    /// The shard `token` is assigned to, under the instance's keyed hash.
403    fn shard_for(&self, token: &ReplayToken) -> &parking_lot::Mutex<ReplayShard> {
404        // Keyed hash, so the sender - who computes the tag - cannot choose the shard. The mask is enough because
405        // the shard count is a power of two.
406        let index = keyed_hash(&self.shard_key, token) as usize & (self.shards.len() - 1);
407        &self.shards[index]
408    }
409}
410
411impl Default for TagReplayFilter {
412    /// A filter at the default configuration.
413    fn default() -> Self {
414        Self::new(&ReplayFilterConfig::default())
415    }
416}
417
418#[cfg(test)]
419mod tests {
420    use std::collections::HashSet;
421
422    use anyhow::Context;
423
424    use super::*;
425
426    /// Builds a config from the two raw fields.
427    fn config(max_tracked_packets: usize, shards: usize) -> ReplayFilterConfig {
428        ReplayFilterConfig {
429            max_tracked_packets,
430            shards,
431        }
432    }
433
434    /// Commits exactly `inserts` distinct fresh tokens into a single-shard filter, skipping Bloom false positives.
435    ///
436    /// A false positive makes `commit` report a fresh token as known, which would leave the generation short of
437    /// full and silently skip the rotation a test depends on. Skipping such tokens keeps the arithmetic exact.
438    /// Returns the token of the final successful insert.
439    fn commit_exactly(filter: &TagReplayFilter, inserts: usize) -> ReplayToken {
440        let mut candidate = 0u64;
441        let mut inserted = 0;
442        let mut last = token(0);
443
444        while inserted < inserts {
445            let t = token(candidate);
446            candidate += 1;
447            if filter.commit(&t) {
448                continue; // false positive: already "known", so it did not take a slot
449            }
450            last = t;
451            inserted += 1;
452        }
453
454        last
455    }
456
457    /// A deterministic synthetic token whose bytes vary with `value`.
458    fn token(value: u64) -> ReplayToken {
459        // Spread the counter across the token so that shard selection and the Bloom hashes both see variety.
460        let mut token: ReplayToken = hopr_api::types::crypto::types::PacketTag::default();
461        for (i, byte) in token.iter_mut().enumerate() {
462            *byte = ((value >> (i % 8 * 8)) as u8).wrapping_add((i as u8).wrapping_mul(31));
463        }
464        token
465    }
466
467    #[test]
468    fn a_committed_token_is_then_known() {
469        let filter = TagReplayFilter::new(&config(1024, 4));
470        let t = token(1);
471
472        assert!(!filter.contains(&t));
473        assert!(!filter.commit(&t), "first commit must see a new token");
474        assert!(filter.contains(&t));
475        assert!(filter.commit(&t), "second commit must see the token");
476        assert_eq!(1, filter.count(), "a duplicate must not be counted twice");
477    }
478
479    /// The property the old clear-on-overflow design lacked: after a shard rotates, a token from the generation
480    /// just retired is still known.
481    #[test]
482    fn a_token_survives_exactly_one_rotation() {
483        // A single shard, so every token lands in it and the generations turn over deterministically.
484        let filter = TagReplayFilter::new(&config(MIN_TRACKED_PACKETS, 1));
485        let capacity = filter.capacity();
486
487        let target = token(0);
488        assert!(!filter.commit(&target), "the target is fresh");
489
490        // Fill the generation, which rotates it once. Counting successful inserts keeps a Bloom false positive
491        // from leaving the generation short and skipping the rotation.
492        commit_exactly(&filter, capacity);
493        assert!(filter.contains(&target), "the retired generation still remembers it");
494
495        // Fill again, which rotates the retired generation out.
496        commit_exactly(&filter, capacity);
497        assert!(
498            !filter.contains(&target),
499            "after two rotations the token may age out; the floor is one generation"
500        );
501    }
502
503    #[test]
504    fn rotation_does_not_lose_the_newest_tokens() {
505        let filter = TagReplayFilter::new(&config(MIN_TRACKED_PACKETS, 1));
506
507        // Two generations' worth, so at least one rotation happens mid-run.
508        let mut recent = Vec::new();
509        for i in 0..(2 * filter.capacity() as u64) {
510            let t = token(i);
511            if filter.commit(&t) {
512                continue; // a false positive; it did not take a slot, so it does not count as recent
513            }
514            recent.push(t);
515            if recent.len() > 100 {
516                recent.remove(0);
517            }
518        }
519        assert!(!recent.is_empty(), "the run must have inserted tokens");
520
521        for t in recent {
522            assert!(
523                filter.contains(&t),
524                "the current generation must remember its own inserts"
525            );
526        }
527    }
528
529    #[test]
530    fn commit_is_a_single_winner_under_concurrency() {
531        let filter = std::sync::Arc::new(TagReplayFilter::new(&config(1024, 4)));
532        let t = token(7);
533
534        let winners = std::sync::Arc::new(std::sync::atomic::AtomicUsize::new(0));
535        std::thread::scope(|scope| {
536            for _ in 0..16 {
537                let filter = filter.clone();
538                let winners = winners.clone();
539                scope.spawn(move || {
540                    if !filter.commit(&t) {
541                        winners.fetch_add(1, std::sync::atomic::Ordering::SeqCst);
542                    }
543                });
544            }
545        });
546
547        assert_eq!(
548            1,
549            winners.load(std::sync::atomic::Ordering::SeqCst),
550            "exactly one commit may see a fresh token"
551        );
552    }
553
554    /// The token that fills a generation must be reported by the next `commit`, not re-admitted.
555    ///
556    /// It sits in the outgoing `current` at that moment, so a check made only against `previous` - or made after
557    /// the rotation using a stale view - misses it, rotates it into the retired generation, and inserts it into the
558    /// fresh one as a new packet. That is the boundary at which two concurrent decodes of one packet could both
559    /// succeed with a single rotation.
560    #[test]
561    fn a_token_that_filled_the_generation_must_not_be_readmitted() {
562        let filter = TagReplayFilter::new(&config(MIN_TRACKED_PACKETS, 1));
563        let filling = commit_exactly(&filter, filter.capacity());
564        assert_eq!(filter.capacity(), filter.count(), "the generation is exactly full");
565
566        assert!(
567            filter.commit(&filling),
568            "the token that filled the generation must be reported, not re-admitted"
569        );
570        assert_eq!(
571            filter.capacity(),
572            filter.count(),
573            "a duplicate must neither rotate the shard nor add to it"
574        );
575    }
576
577    /// A token that lives only in the retired generation must still be reported by `commit`, not just by
578    /// `contains`. The decoder calls `commit` directly, so this is the path a duplicate takes there.
579    #[test]
580    fn commit_should_report_a_token_from_the_retired_generation() {
581        // One shard, so every token lands in it and the rotation is deterministic.
582        let filter = TagReplayFilter::new(&config(MIN_TRACKED_PACKETS, 1));
583        let ours = token(0);
584        filter.commit(&ours);
585
586        // Fill the generation so that `ours` is retired into `previous`.
587        commit_exactly(&filter, filter.capacity());
588        assert!(filter.contains(&ours), "the retired generation still knows it");
589
590        assert!(
591            filter.commit(&ours),
592            "commit must report a token only the retired generation knows"
593        );
594        assert_eq!(
595            filter.count(),
596            1,
597            "a commit that found the token in the retired generation must not also insert it"
598        );
599    }
600
601    /// `count` reports the current generations only: it is reset by a rotation and never includes the retired one.
602    #[test]
603    fn count_should_track_the_current_generation_only() {
604        let filter = TagReplayFilter::new(&config(MIN_TRACKED_PACKETS, 1));
605        assert_eq!(0, filter.count(), "a new filter has inserted nothing");
606
607        let capacity = filter.capacity();
608        commit_exactly(&filter, capacity);
609        assert_eq!(capacity, filter.count(), "a full generation is counted");
610
611        // One more distinct token rotates the shard and starts a fresh generation.
612        filter.commit(&token(u64::MAX));
613        assert_eq!(1, filter.count(), "the count restarts with the new generation");
614        assert_eq!(capacity, filter.capacity(), "capacity is unaffected by rotation");
615    }
616
617    #[test]
618    fn shard_selection_spreads_tokens() {
619        let filter = TagReplayFilter::new(&config(1024, 64));
620        let mut used = HashSet::new();
621        for i in 0..10_000u64 {
622            used.insert(filter.shard_for(&token(i)) as *const _ as usize);
623        }
624        assert!(used.len() > 32, "tokens must reach most shards, saw {}", used.len());
625    }
626
627    /// A shard count that is not a power of two is rounded up rather than leaving part of the filter unaddressed,
628    /// since `TagReplayFilter::new` is public and the decoder does not validate its configuration.
629    #[test]
630    fn an_odd_shard_count_should_still_use_the_whole_filter() {
631        let filter = TagReplayFilter::new(&config(MIN_TRACKED_PACKETS, 3));
632        assert_eq!(4, filter.shards(), "3 shards must round up to 4");
633
634        let mut used = HashSet::new();
635        for i in 0..10_000u64 {
636            used.insert(filter.shard_for(&token(i)) as *const _ as usize);
637        }
638        assert_eq!(4, used.len(), "every shard must be addressable, saw {}", used.len());
639    }
640
641    /// The bounds and their message are spelled out as literals in the `range` validator, because `validator`
642    /// cannot interpolate constants. This keeps the exported constants, the enforced bounds and the numbers an
643    /// operator reads in the error message from drifting apart.
644    #[test]
645    fn the_tracked_packet_bounds_agree_with_the_validator() -> anyhow::Result<()> {
646        let mut cfg = config(MIN_TRACKED_PACKETS, 64);
647        validator::Validate::validate(&cfg).context("the floor itself must be accepted")?;
648
649        cfg.max_tracked_packets = MIN_TRACKED_PACKETS - 1;
650        let err = validator::Validate::validate(&cfg)
651            .err()
652            .context("one below the exported floor must be rejected")?;
653        let message = format!("{}", err.field_errors()["max_tracked_packets"][0]);
654        assert!(
655            message.contains(&MIN_TRACKED_PACKETS.to_string()),
656            "the message must state the real lower bound, got: {message}"
657        );
658
659        cfg.max_tracked_packets = MAX_TRACKED_PACKETS + 1;
660        let err = validator::Validate::validate(&cfg)
661            .err()
662            .context("one above the exported ceiling must be rejected")?;
663        let message = format!("{}", err.field_errors()["max_tracked_packets"][0]);
664        assert!(
665            message.contains(&MAX_TRACKED_PACKETS.to_string()),
666            "the message must state the real upper bound, got: {message}"
667        );
668        Ok(())
669    }
670
671    /// The field-wise ranges accept the floor capacity together with the shard ceiling, yet that leaves far fewer
672    /// slots per shard than [`MIN_CAPACITY_PER_SHARD`]. The config-level check is what rejects it - and it must not
673    /// reject a configuration whose capacity merely does not divide evenly.
674    #[test]
675    fn a_configuration_with_too_little_capacity_per_shard_must_be_rejected() {
676        assert!(
677            validator::Validate::validate(&config(MIN_TRACKED_PACKETS, MAX_SHARDS)).is_err(),
678            "the floor capacity split across the shard ceiling leaves too few slots per shard"
679        );
680        assert!(
681            validator::Validate::validate(&config(MIN_CAPACITY_PER_SHARD * 63, 64)).is_err(),
682            "one below the per-shard floor must be rejected"
683        );
684        assert!(
685            validator::Validate::validate(&config(MIN_CAPACITY_PER_SHARD * 64, 64)).is_ok(),
686            "exactly the per-shard floor must be accepted"
687        );
688        assert!(
689            validator::Validate::validate(&config(MIN_CAPACITY_PER_SHARD * 64 + 1, 64)).is_ok(),
690            "an uneven split must still be accepted"
691        );
692    }
693
694    /// Every accepted configuration gives each shard the per-shard floor, so the filter's capacity is the configured
695    /// value up to the shard count, and never larger than it.
696    #[test]
697    fn an_accepted_configuration_never_widens_the_capacity() -> anyhow::Result<()> {
698        for (packets, shards) in [
699            (MIN_TRACKED_PACKETS, 64),
700            (MIN_TRACKED_PACKETS + 1, 64),
701            (MIN_CAPACITY_PER_SHARD * MAX_SHARDS, MAX_SHARDS),
702        ] {
703            let cfg = config(packets, shards);
704            validator::Validate::validate(&cfg).context("must be a valid configuration")?;
705            let filter = TagReplayFilter::new(&cfg);
706            assert_eq!(
707                packets / shards * shards,
708                filter.capacity(),
709                "unexpected capacity for {cfg:?}"
710            );
711        }
712        Ok(())
713    }
714
715    #[test]
716    fn shard_count_must_be_a_power_of_two() -> anyhow::Result<()> {
717        // The capacity is generous in both cases, so only the shard rule can decide.
718        let err = validator::Validate::validate(&config(65_536, 3))
719            .err()
720            .context("3 shards must be rejected")?;
721        assert!(err.field_errors().contains_key("shards"));
722        validator::Validate::validate(&config(65_536, 64)).context("64 shards must be accepted")?;
723        Ok(())
724    }
725
726    #[test]
727    fn capacity_is_shared_evenly_across_shards() {
728        let filter = TagReplayFilter::new(&config(1024, 64));
729        assert_eq!(1024, filter.capacity());
730        assert_eq!(64, filter.shards());
731    }
732
733    /// A token this filter accepts must be reported as a replay the next time it is offered, however much traffic
734    /// has passed through in between.
735    ///
736    /// This is the property a per-peer insertion allowance broke: past its allowance a peer's packets were accepted
737    /// without being recorded, so the same packet was accepted again. Exercised through the whole filter rather than
738    /// a single shard, over several rotations.
739    #[test]
740    fn a_token_accepted_now_must_be_a_replay_later() {
741        let filter = TagReplayFilter::new(&config(MIN_TRACKED_PACKETS, 4));
742
743        // Far more than a generation's worth, so several rotations happen before the token of interest.
744        for i in 0..(3 * filter.capacity() as u64) {
745            filter.commit(&token(i));
746        }
747
748        let recent = token(3 * filter.capacity() as u64 + 1);
749        assert!(!filter.commit(&recent), "the token is fresh");
750        assert!(
751            filter.commit(&recent),
752            "a token that was just accepted must be reported as a replay when repeated"
753        );
754    }
755
756    /// An unvalidated `shards` must not overflow or allocate unboundedly: `new` is public and the decoder does not
757    /// validate its configuration.
758    #[test]
759    fn an_unvalidated_shard_count_is_clamped() {
760        assert_eq!(
761            MAX_SHARDS,
762            TagReplayFilter::new(&config(MIN_TRACKED_PACKETS, usize::MAX)).shards(),
763            "an oversized shard count must clamp to the ceiling, not overflow"
764        );
765        assert_eq!(
766            MIN_SHARDS,
767            TagReplayFilter::new(&config(MIN_TRACKED_PACKETS, 0)).shards(),
768            "a zero shard count must clamp to the floor"
769        );
770    }
771
772    #[test]
773    fn a_new_filter_knows_nothing() {
774        let filter = TagReplayFilter::default();
775        assert_eq!(0, filter.count());
776        assert!(!filter.contains(&token(0)));
777    }
778}