Skip to main content

hns_cache/
lib.rs

1//! Bounded positive and negative cache for HNS browser resolution.
2//!
3//! Keys are session-secret-derived SHA-256 values rather than qnames. Entries
4//! are bound to runtime generation, policy generation, and exact Handshake
5//! chain anchor. Expired or mismatched entries are removed before use.
6
7#![forbid(unsafe_code)]
8#![allow(
9    clippy::doc_markdown,
10    clippy::missing_errors_doc,
11    clippy::module_name_repetitions,
12    reason = "HNS and DNS protocol names are intentional"
13)]
14
15use std::collections::HashMap;
16use std::fmt;
17use std::hash::Hash;
18
19use hns_dns_wire::{Name, RecordType};
20use sha2::{Digest, Sha256};
21use thiserror::Error;
22
23const CACHE_KEY_DOMAIN: &[u8] = b"hns-browser-cache-key-v1";
24
25/// Bounds for one cache instance.
26#[derive(Clone, Copy, Debug, Eq, PartialEq)]
27pub struct CacheLimits {
28    /// Maximum resident entries.
29    pub max_entries: usize,
30    /// Maximum caller-reported bytes across resident values.
31    pub max_total_value_bytes: usize,
32    /// Maximum caller-reported bytes for one value.
33    pub max_value_bytes: usize,
34    /// Maximum positive TTL in seconds.
35    pub max_positive_ttl: u32,
36    /// Maximum negative TTL in seconds.
37    pub max_negative_ttl: u32,
38}
39
40impl Default for CacheLimits {
41    fn default() -> Self {
42        Self {
43            max_entries: 4_096,
44            max_total_value_bytes: 16 * 1024 * 1024,
45            max_value_bytes: 256 * 1024,
46            max_positive_ttl: 86_400,
47            max_negative_ttl: 3_600,
48        }
49    }
50}
51
52impl CacheLimits {
53    fn validate(self) -> Result<Self, CacheError> {
54        if self.max_entries == 0
55            || self.max_total_value_bytes == 0
56            || self.max_value_bytes == 0
57            || self.max_value_bytes > self.max_total_value_bytes
58            || self.max_positive_ttl == 0
59            || self.max_negative_ttl == 0
60        {
61            return Err(CacheError::InvalidLimits);
62        }
63        Ok(self)
64    }
65}
66
67/// Exact authority state under which an entry was produced.
68#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
69pub struct CacheGeneration {
70    /// Runtime generation.
71    pub runtime_generation: u64,
72    /// Policy generation.
73    pub policy_generation: u64,
74    /// Validated Handshake height.
75    pub chain_height: u32,
76    /// Exact committed Handshake name-tree root.
77    pub tree_root: [u8; 32],
78}
79
80impl CacheGeneration {
81    fn validate(self) -> Result<Self, CacheError> {
82        if self.runtime_generation == 0 || self.policy_generation == 0 {
83            return Err(CacheError::InvalidGeneration);
84        }
85        Ok(self)
86    }
87}
88
89/// Negative cache result.
90#[repr(u8)]
91#[derive(Clone, Copy, Debug, Eq, PartialEq)]
92pub enum NegativeKind {
93    /// DNSSEC-authenticated name error.
94    NameError = 0,
95    /// DNSSEC-authenticated no-data result.
96    NoData = 1,
97    /// Current HNS Urkel non-inclusion.
98    HnsNameAbsent = 2,
99}
100
101/// Positive or authenticated-negative cache disposition.
102#[derive(Clone, Copy, Debug, Eq, PartialEq)]
103pub enum CacheDisposition {
104    /// Positive validated data.
105    Positive,
106    /// Cryptographically authenticated absence.
107    Negative(NegativeKind),
108}
109
110/// Metadata checked when admitting one cache value.
111#[derive(Clone, Copy, Debug, Eq, PartialEq)]
112pub struct CacheAdmission {
113    /// Conservative encoded/in-memory value byte estimate.
114    pub value_bytes: usize,
115    /// Positive or authenticated-negative result.
116    pub disposition: CacheDisposition,
117    /// Exact runtime, policy, and chain authority.
118    pub generation: CacheGeneration,
119    /// Current monotonic or Unix time in seconds.
120    pub now: u64,
121    /// Requested TTL in seconds.
122    pub ttl_seconds: u32,
123}
124
125/// Opaque per-session query key.
126#[derive(Clone, Copy, Eq, Hash, PartialEq)]
127pub struct CacheKey([u8; 32]);
128
129impl CacheKey {
130    /// Derive a key from a secret runtime salt and canonical query identity.
131    pub fn derive(
132        session_secret: &[u8; 32],
133        network_id: u8,
134        generation: CacheGeneration,
135        name: &Name,
136        record_type: RecordType,
137    ) -> Result<Self, CacheError> {
138        if session_secret == &[0; 32] {
139            return Err(CacheError::WeakSessionSecret);
140        }
141        let generation = generation.validate()?;
142        let mut wire_name = Vec::with_capacity(name.wire_len());
143        name.encode(&mut wire_name)?;
144        let mut hasher = Sha256::new();
145        hasher.update(CACHE_KEY_DOMAIN);
146        hasher.update(session_secret);
147        hasher.update([network_id]);
148        hasher.update(generation.runtime_generation.to_be_bytes());
149        hasher.update(generation.policy_generation.to_be_bytes());
150        hasher.update(generation.chain_height.to_be_bytes());
151        hasher.update(generation.tree_root);
152        hasher.update(record_type.code().to_be_bytes());
153        hasher.update(
154            u16::try_from(wire_name.len())
155                .map_err(|_| CacheError::InvalidQuery)?
156                .to_be_bytes(),
157        );
158        hasher.update(&wire_name);
159        Ok(Self(hasher.finalize().into()))
160    }
161}
162
163impl fmt::Debug for CacheKey {
164    fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
165        formatter.write_str("CacheKey([redacted])")
166    }
167}
168
169/// Name-free cache counters.
170#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
171pub struct CacheStats {
172    /// Resident entries.
173    pub entries: usize,
174    /// Caller-reported resident value bytes.
175    pub value_bytes: usize,
176    /// Successful current-generation reads.
177    pub hits: u64,
178    /// Absent, expired, or generation-mismatched reads.
179    pub misses: u64,
180    /// Capacity-driven removals.
181    pub evictions: u64,
182    /// TTL-driven removals.
183    pub expirations: u64,
184    /// Generation-mismatch removals.
185    pub stale_removals: u64,
186}
187
188#[derive(Clone, Debug)]
189struct Entry<Value> {
190    value: Value,
191    value_bytes: usize,
192    disposition: CacheDisposition,
193    generation: CacheGeneration,
194    expires_at: u64,
195    last_access: u64,
196}
197
198/// Bounded LRU cache with explicit TTL and authority-generation binding.
199#[derive(Clone, Debug)]
200pub struct SecureCache<Value> {
201    limits: CacheLimits,
202    entries: HashMap<CacheKey, Entry<Value>>,
203    sequence: u64,
204    stats: CacheStats,
205}
206
207impl<Value> SecureCache<Value> {
208    /// Create an empty cache after validating all bounds.
209    pub fn new(limits: CacheLimits) -> Result<Self, CacheError> {
210        let limits = limits.validate()?;
211        Ok(Self {
212            limits,
213            entries: HashMap::with_capacity(limits.max_entries),
214            sequence: 0,
215            stats: CacheStats::default(),
216        })
217    }
218
219    /// Insert one positive or authenticated-negative result.
220    ///
221    /// `value_bytes` is the caller's conservative encoded/in-memory estimate.
222    pub fn insert(
223        &mut self,
224        key: CacheKey,
225        value: Value,
226        admission: CacheAdmission,
227    ) -> Result<(), CacheError> {
228        let generation = admission.generation.validate()?;
229        let value_bytes = admission.value_bytes;
230        if value_bytes == 0
231            || value_bytes > self.limits.max_value_bytes
232            || value_bytes > self.limits.max_total_value_bytes
233        {
234            return Err(CacheError::ValueLimit);
235        }
236        let maximum_ttl = match admission.disposition {
237            CacheDisposition::Positive => self.limits.max_positive_ttl,
238            CacheDisposition::Negative(_) => self.limits.max_negative_ttl,
239        };
240        if admission.ttl_seconds == 0 || admission.ttl_seconds > maximum_ttl {
241            return Err(CacheError::TtlLimit);
242        }
243        let expires_at = admission
244            .now
245            .checked_add(u64::from(admission.ttl_seconds))
246            .ok_or(CacheError::TimeOverflow)?;
247        let sequence = self.next_sequence()?;
248        self.remove_expired(admission.now);
249        self.remove_internal(&key);
250        while self.entries.len() >= self.limits.max_entries
251            || self
252                .stats
253                .value_bytes
254                .checked_add(value_bytes)
255                .is_none_or(|bytes| bytes > self.limits.max_total_value_bytes)
256        {
257            self.evict_lru().ok_or(CacheError::ValueLimit)?;
258        }
259        self.stats.value_bytes = self
260            .stats
261            .value_bytes
262            .checked_add(value_bytes)
263            .ok_or(CacheError::ValueLimit)?;
264        self.entries.insert(
265            key,
266            Entry {
267                value,
268                value_bytes,
269                disposition: admission.disposition,
270                generation,
271                expires_at,
272                last_access: sequence,
273            },
274        );
275        self.stats.entries = self.entries.len();
276        Ok(())
277    }
278
279    /// Read one current entry and update its LRU position.
280    pub fn get(
281        &mut self,
282        key: &CacheKey,
283        generation: CacheGeneration,
284        now: u64,
285    ) -> Result<Option<(&Value, CacheDisposition)>, CacheError> {
286        let generation = generation.validate()?;
287        let Some(metadata) = self
288            .entries
289            .get(key)
290            .map(|entry| (entry.generation, entry.expires_at, entry.disposition))
291        else {
292            self.stats.misses = self.stats.misses.saturating_add(1);
293            return Ok(None);
294        };
295        if metadata.0 != generation {
296            self.remove_internal(key);
297            self.stats.stale_removals = self.stats.stale_removals.saturating_add(1);
298            self.stats.misses = self.stats.misses.saturating_add(1);
299            return Ok(None);
300        }
301        if now >= metadata.1 {
302            self.remove_internal(key);
303            self.stats.expirations = self.stats.expirations.saturating_add(1);
304            self.stats.misses = self.stats.misses.saturating_add(1);
305            return Ok(None);
306        }
307        let sequence = self.next_sequence()?;
308        let entry = self
309            .entries
310            .get_mut(key)
311            .ok_or(CacheError::InternalInvariant)?;
312        entry.last_access = sequence;
313        self.stats.hits = self.stats.hits.saturating_add(1);
314        Ok(Some((&entry.value, metadata.2)))
315    }
316
317    /// Remove every entry on a generation, policy, or chain-anchor transition.
318    pub fn clear(&mut self) {
319        self.entries.clear();
320        self.stats.entries = 0;
321        self.stats.value_bytes = 0;
322    }
323
324    /// Remove one opaque key.
325    pub fn remove(&mut self, key: &CacheKey) -> bool {
326        self.remove_internal(key).is_some()
327    }
328
329    /// Name-free counters.
330    #[must_use]
331    pub const fn stats(&self) -> CacheStats {
332        self.stats
333    }
334
335    /// Configured hard bounds.
336    #[must_use]
337    pub const fn limits(&self) -> CacheLimits {
338        self.limits
339    }
340
341    fn next_sequence(&mut self) -> Result<u64, CacheError> {
342        self.sequence = self
343            .sequence
344            .checked_add(1)
345            .ok_or(CacheError::SequenceExhausted)?;
346        Ok(self.sequence)
347    }
348
349    fn remove_expired(&mut self, now: u64) {
350        let expired = self
351            .entries
352            .iter()
353            .filter_map(|(key, entry)| (now >= entry.expires_at).then_some(*key))
354            .collect::<Vec<_>>();
355        for key in expired {
356            if self.remove_internal(&key).is_some() {
357                self.stats.expirations = self.stats.expirations.saturating_add(1);
358            }
359        }
360    }
361
362    fn evict_lru(&mut self) -> Option<()> {
363        let key = self
364            .entries
365            .iter()
366            .min_by_key(|(_, entry)| entry.last_access)
367            .map(|(key, _)| *key)?;
368        self.remove_internal(&key)?;
369        self.stats.evictions = self.stats.evictions.saturating_add(1);
370        Some(())
371    }
372
373    fn remove_internal(&mut self, key: &CacheKey) -> Option<Entry<Value>> {
374        let entry = self.entries.remove(key)?;
375        self.stats.value_bytes = self.stats.value_bytes.saturating_sub(entry.value_bytes);
376        self.stats.entries = self.entries.len();
377        Some(entry)
378    }
379}
380
381/// Cache configuration, key, bound, or invariant failure.
382#[derive(Debug, Error)]
383#[non_exhaustive]
384pub enum CacheError {
385    /// DNS name encoding failed.
386    #[error("DNS query encoding failed: {0}")]
387    Wire(#[from] hns_dns_wire::Error),
388    /// A configured cache bound is zero or inconsistent.
389    #[error("invalid cache limits")]
390    InvalidLimits,
391    /// Runtime or policy generation is zero.
392    #[error("invalid cache generation")]
393    InvalidGeneration,
394    /// Runtime cache-key secret is all zero.
395    #[error("cache session secret must be randomly generated")]
396    WeakSessionSecret,
397    /// Canonical query identity cannot be represented.
398    #[error("invalid cache query identity")]
399    InvalidQuery,
400    /// Caller-reported value size exceeds a bound.
401    #[error("cache value exceeds its bound")]
402    ValueLimit,
403    /// TTL is zero or exceeds its positive/negative bound.
404    #[error("cache TTL exceeds its bound")]
405    TtlLimit,
406    /// Expiration time overflowed.
407    #[error("cache expiration time overflow")]
408    TimeOverflow,
409    /// LRU sequence cannot advance.
410    #[error("cache LRU sequence exhausted")]
411    SequenceExhausted,
412    /// Internal entry disappeared during one exclusive operation.
413    #[error("cache internal invariant failed")]
414    InternalInvariant,
415}
416
417#[cfg(test)]
418#[allow(
419    clippy::unwrap_used,
420    reason = "tests fail immediately on invalid local cache fixtures"
421)]
422mod tests {
423    use super::*;
424
425    fn cache_generation(value: u8) -> CacheGeneration {
426        CacheGeneration {
427            runtime_generation: u64::from(value),
428            policy_generation: 1,
429            chain_height: 100,
430            tree_root: [value; 32],
431        }
432    }
433
434    fn key(secret: u8, name: &str, generation: CacheGeneration) -> CacheKey {
435        CacheKey::derive(
436            &[secret; 32],
437            0,
438            generation,
439            &Name::from_ascii(name).unwrap(),
440            RecordType::Tlsa,
441        )
442        .unwrap()
443    }
444
445    #[test]
446    fn keys_are_qname_free_session_and_generation_specific() {
447        let generation = cache_generation(1);
448        let first = key(7, "_443._tcp.alpha.", generation);
449        let same = key(7, "_443._tcp.alpha.", generation);
450        let other_secret = key(8, "_443._tcp.alpha.", generation);
451        let other_generation = key(7, "_443._tcp.alpha.", cache_generation(2));
452        assert_eq!(first, same);
453        assert_ne!(first, other_secret);
454        assert_ne!(first, other_generation);
455        assert_eq!(format!("{first:?}"), "CacheKey([redacted])");
456        assert!(matches!(
457            CacheKey::derive(
458                &[0; 32],
459                0,
460                generation,
461                &Name::from_ascii("alpha.").unwrap(),
462                RecordType::A,
463            ),
464            Err(CacheError::WeakSessionSecret)
465        ));
466    }
467
468    #[test]
469    fn expiration_and_generation_mismatch_remove_before_use() {
470        let generation = cache_generation(1);
471        let cache_key = key(7, "alpha.", generation);
472        let mut cache = SecureCache::new(CacheLimits::default()).unwrap();
473        cache
474            .insert(
475                cache_key,
476                "secure",
477                CacheAdmission {
478                    value_bytes: 6,
479                    disposition: CacheDisposition::Positive,
480                    generation,
481                    now: 100,
482                    ttl_seconds: 10,
483                },
484            )
485            .unwrap();
486        assert_eq!(
487            cache.get(&cache_key, generation, 109).unwrap(),
488            Some((&"secure", CacheDisposition::Positive))
489        );
490        assert_eq!(cache.get(&cache_key, generation, 110).unwrap(), None);
491        assert_eq!(cache.stats().expirations, 1);
492
493        cache
494            .insert(
495                cache_key,
496                "negative",
497                CacheAdmission {
498                    value_bytes: 8,
499                    disposition: CacheDisposition::Negative(NegativeKind::NoData),
500                    generation,
501                    now: 200,
502                    ttl_seconds: 10,
503                },
504            )
505            .unwrap();
506        assert_eq!(
507            cache.get(&cache_key, cache_generation(2), 201).unwrap(),
508            None
509        );
510        assert_eq!(cache.stats().stale_removals, 1);
511    }
512
513    #[test]
514    fn entry_and_byte_bounds_evict_least_recently_used() {
515        let limits = CacheLimits {
516            max_entries: 2,
517            max_total_value_bytes: 8,
518            max_value_bytes: 8,
519            max_positive_ttl: 100,
520            max_negative_ttl: 10,
521        };
522        let generation = cache_generation(1);
523        let first = key(7, "one.", generation);
524        let second = key(7, "two.", generation);
525        let third = key(7, "three.", generation);
526        let mut cache = SecureCache::new(limits).unwrap();
527        for (key, value) in [(first, "1111"), (second, "2222")] {
528            cache
529                .insert(
530                    key,
531                    value,
532                    CacheAdmission {
533                        value_bytes: 4,
534                        disposition: CacheDisposition::Positive,
535                        generation,
536                        now: 0,
537                        ttl_seconds: 100,
538                    },
539                )
540                .unwrap();
541        }
542        assert!(cache.get(&first, generation, 1).unwrap().is_some());
543        cache
544            .insert(
545                third,
546                "3333",
547                CacheAdmission {
548                    value_bytes: 4,
549                    disposition: CacheDisposition::Positive,
550                    generation,
551                    now: 2,
552                    ttl_seconds: 100,
553                },
554            )
555            .unwrap();
556        assert!(cache.get(&second, generation, 3).unwrap().is_none());
557        assert!(cache.get(&first, generation, 3).unwrap().is_some());
558        assert!(cache.get(&third, generation, 3).unwrap().is_some());
559        assert_eq!(cache.stats().evictions, 1);
560        assert_eq!(cache.stats().entries, 2);
561        assert_eq!(cache.stats().value_bytes, 8);
562    }
563
564    #[test]
565    fn invalid_limits_sizes_and_ttls_fail_without_insertion() {
566        assert!(matches!(
567            SecureCache::<()>::new(CacheLimits {
568                max_entries: 0,
569                ..CacheLimits::default()
570            }),
571            Err(CacheError::InvalidLimits)
572        ));
573        let mut cache = SecureCache::new(CacheLimits {
574            max_entries: 1,
575            max_total_value_bytes: 8,
576            max_value_bytes: 4,
577            max_positive_ttl: 10,
578            max_negative_ttl: 2,
579        })
580        .unwrap();
581        let generation = cache_generation(1);
582        let cache_key = key(7, "alpha.", generation);
583        assert!(matches!(
584            cache.insert(
585                cache_key,
586                (),
587                CacheAdmission {
588                    value_bytes: 5,
589                    disposition: CacheDisposition::Positive,
590                    generation,
591                    now: 0,
592                    ttl_seconds: 1,
593                },
594            ),
595            Err(CacheError::ValueLimit)
596        ));
597        assert!(matches!(
598            cache.insert(
599                cache_key,
600                (),
601                CacheAdmission {
602                    value_bytes: 1,
603                    disposition: CacheDisposition::Negative(NegativeKind::NameError),
604                    generation,
605                    now: 0,
606                    ttl_seconds: 3,
607                },
608            ),
609            Err(CacheError::TtlLimit)
610        ));
611        assert_eq!(cache.stats().entries, 0);
612    }
613}