commonware_utils/
rng.rs

1//! Utilities for random number generation.
2
3use commonware_macros::stability;
4#[stability(ALPHA)]
5use core::{convert::Infallible, mem::size_of};
6#[stability(BETA)]
7use rand::{CryptoRng, rand_core::UnwrapErr, rngs::SysRng};
8#[stability(ALPHA)]
9use rand::{SeedableRng, TryCryptoRng, TryRng, rngs::StdRng};
10
11/// Returns an infallible handle to the operating system's entropy source.
12///
13/// Use this whenever randomness must come directly from the OS (e.g. key
14/// generation) rather than from a seeded or userspace RNG.
15///
16/// # Panics
17///
18/// Panics if the operating system fails to provide randomness.
19#[stability(BETA)]
20pub fn sys_rng() -> impl CryptoRng {
21    UnwrapErr(SysRng)
22}
23
24/// A deterministic RNG for testing.
25///
26/// Like [FuzzRng], this is a named type so tests and helpers can refer to it
27/// in signatures. The underlying generator is private, so consumers can only
28/// interact with it through the RNG traits. Construct it with [test_rng] or
29/// [TestRng::new].
30#[stability(ALPHA)]
31#[derive(Debug)]
32pub struct TestRng(StdRng);
33
34#[stability(ALPHA)]
35impl TryRng for TestRng {
36    type Error = Infallible;
37
38    fn try_next_u32(&mut self) -> Result<u32, Self::Error> {
39        self.0.try_next_u32()
40    }
41
42    fn try_next_u64(&mut self) -> Result<u64, Self::Error> {
43        self.0.try_next_u64()
44    }
45
46    fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Self::Error> {
47        self.0.try_fill_bytes(dest)
48    }
49}
50
51#[stability(ALPHA)]
52impl TryCryptoRng for TestRng {}
53
54#[stability(ALPHA)]
55impl TestRng {
56    /// Returns a deterministic RNG seeded with the provided value.
57    ///
58    /// Use this when you need multiple independent RNG streams in the same test,
59    /// or when a helper function needs its own RNG that won't collide with the caller's.
60    pub fn new(seed: u64) -> Self {
61        Self(StdRng::seed_from_u64(seed))
62    }
63}
64
65/// Returns a seeded RNG for deterministic testing.
66///
67/// Uses seed 0 by default to ensure reproducible test results.
68#[stability(ALPHA)]
69pub fn test_rng() -> TestRng {
70    TestRng::new(0)
71}
72
73/// A bounded deterministic RNG that returns a caller-supplied sequence of `u64` samples.
74///
75/// Each `u32` consumes one sample and returns its low 32 bits. Byte fills encode samples in
76/// little-endian order and discard unused bytes from the final sample.
77///
78/// Sampling beyond the supplied sequence panics.
79#[stability(ALPHA)]
80#[derive(Debug)]
81pub struct ScriptedRng {
82    samples: std::vec::IntoIter<u64>,
83}
84
85#[stability(ALPHA)]
86impl ScriptedRng {
87    /// Creates a bounded RNG from the provided samples.
88    pub fn new(samples: impl IntoIterator<Item = u64>) -> Self {
89        Self {
90            samples: samples.into_iter().collect::<Vec<_>>().into_iter(),
91        }
92    }
93}
94
95#[stability(ALPHA)]
96impl TryRng for ScriptedRng {
97    type Error = Infallible;
98
99    fn try_next_u32(&mut self) -> Result<u32, Self::Error> {
100        Ok(self.try_next_u64()? as u32)
101    }
102
103    fn try_next_u64(&mut self) -> Result<u64, Self::Error> {
104        Ok(self
105            .samples
106            .next()
107            .expect("scripted RNG consumed more samples than expected"))
108    }
109
110    fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Self::Error> {
111        rand::rand_core::utils::fill_bytes_via_next_word(dest, || self.try_next_u64())
112    }
113}
114
115/// Boxes the rng for runtimes that take a dynamic rng (e.g. the deterministic runtime's
116/// `Config::with_rng`).
117#[stability(ALPHA)]
118impl From<ScriptedRng> for Box<dyn CryptoRng + Send + 'static> {
119    fn from(rng: ScriptedRng) -> Self {
120        Box::new(rng)
121    }
122}
123
124// SAFETY: ScriptedRng is not cryptographically secure. It implements CryptoRng only because test
125// runtimes require CryptoRng-bounded RNGs. This type must never be used outside tests.
126#[stability(ALPHA)]
127impl TryCryptoRng for ScriptedRng {}
128
129/// Applies a SplitMix64-style finalizer to a deterministic input word.
130///
131/// This is useful for cheaply decorrelating derived deterministic seeds while
132/// preserving reproducibility.
133#[inline]
134#[stability(ALPHA)]
135pub const fn mix64(mut word: u64) -> u64 {
136    word ^= word >> 30;
137    word = word.wrapping_mul(0xbf58_476d_1ce4_e5b9);
138    word ^= word >> 27;
139    word = word.wrapping_mul(0x94d0_49bb_1331_11eb);
140    word ^ (word >> 31)
141}
142
143/// Width of each source window in bytes.
144#[stability(ALPHA)]
145const BLOCK_BYTES: usize = size_of::<u64>();
146
147/// An RNG that expands a fuzzer byte slice into an infinite deterministic stream.
148///
149/// # Design
150///
151/// `FuzzRng` maps a fuzzer-controlled byte slice to output blocks.
152///
153/// For each block counter `ctr`, it:
154/// 1. Reads a wrapping `u64`-wide window from the input bytes.
155/// 2. Xors in `ctr` and a domain constant.
156/// 3. Applies a SplitMix64-style finalizer.
157///
158/// ```text
159/// input bytes (len = N):
160///   [b0 b1 b2 ... b(N-1)]
161///
162/// block ctr = i:
163///   word_i bytes = [b(i+0)%N, b(i+1)%N, ... b(i+7)%N]
164///   word_i       = big-endian u64 of those bytes
165///   out_i        = mix64(word_i ^ i ^ DOMAIN)
166/// ```
167///
168/// # Why this mapping
169///
170/// Hashing the full input once and then seeding a PRNG makes tiny input changes
171/// look globally unrelated. This adapter avoids that by using a sliding window
172/// keyed by the block counter.
173///
174/// ```text
175/// byte k affects anchors:
176///   i in [k-(BLOCK_BYTES-1), ..., k] (mod N)
177/// ```
178///
179/// # Worked Example
180///
181/// With `N = 4`, input bytes repeat inside each block:
182///
183/// ```text
184/// input: [a b c d]
185///
186/// ctr=0: word bytes [a b c d a b c d]
187/// ctr=1: word bytes [b c d a b c d a]
188/// ctr=2: word bytes [c d a b c d a b]
189/// ...
190/// ```
191///
192/// Even for low-entropy input like `[0 0 0 0]`, output still changes because
193/// `ctr` is mixed into every block before finalization.
194///
195/// `fill_bytes` serves output from cached block bytes so callers get a stable
196/// byte stream regardless of whether they request randomness as `next_u64`,
197/// `next_u32`, or arbitrary byte slices.
198#[stability(ALPHA)]
199pub struct FuzzRng {
200    bytes: Vec<u8>,
201    ctr: u64,
202    cache: [u8; BLOCK_BYTES],
203    cache_pos: usize,
204}
205
206/// Fuzzer-provided entropy backing a [FuzzRng].
207///
208/// Its `Arbitrary` implementation consumes the input's remaining bytes, so declare it as
209/// the LAST field of a fuzz input struct. Every [FuzzRng] converted from the same entropy
210/// yields an identical stream.
211#[stability(ALPHA)]
212#[derive(Clone, Debug)]
213pub struct Entropy(Vec<u8>);
214
215#[cfg(feature = "arbitrary")]
216#[stability(ALPHA)]
217impl<'a> arbitrary::Arbitrary<'a> for Entropy {
218    fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
219        Ok(Self(u.bytes(u.len())?.to_vec()))
220    }
221}
222
223#[stability(ALPHA)]
224impl From<Entropy> for FuzzRng {
225    fn from(entropy: Entropy) -> Self {
226        Self::new(entropy.0)
227    }
228}
229
230/// Boxes the rng for runtimes that take a dynamic rng (e.g. the deterministic runtime's
231/// `Config::with_rng`).
232#[stability(ALPHA)]
233impl From<Entropy> for Box<dyn CryptoRng + Send + 'static> {
234    fn from(entropy: Entropy) -> Self {
235        Box::new(FuzzRng::from(entropy))
236    }
237}
238
239/// Boxes the rng for runtimes that take a dynamic rng (e.g. the deterministic runtime's
240/// `Config::with_rng`).
241#[stability(ALPHA)]
242impl From<FuzzRng> for Box<dyn CryptoRng + Send + 'static> {
243    fn from(rng: FuzzRng) -> Self {
244        Box::new(rng)
245    }
246}
247
248#[stability(ALPHA)]
249impl FuzzRng {
250    /// Creates a new `FuzzRng` from a byte buffer.
251    pub const fn new(bytes: Vec<u8>) -> Self {
252        Self {
253            bytes,
254            ctr: 0,
255            cache: [0u8; BLOCK_BYTES],
256            cache_pos: BLOCK_BYTES,
257        }
258    }
259
260    /// Generates the next mixed `u64` block from the fuzz input.
261    ///
262    /// Conceptually:
263    /// 1. Build `word` from a wrapping `BLOCK_BYTES` window anchored at `ctr`.
264    /// 2. Compute `mixed = mix64(word ^ ctr ^ GOLDEN_RATIO)`.
265    /// 3. Increment `ctr`.
266    ///
267    /// This keeps the output deterministic while preserving local mutation
268    /// influence: one input-byte mutation only affects nearby anchor counters.
269    #[inline]
270    fn next_block_u64(&mut self) -> u64 {
271        // Build a wrapping u64-width source word anchored at this block counter.
272        // A single fuzz-byte mutation only impacts nearby anchors.
273        let mut bytes = [0u8; BLOCK_BYTES];
274        if !self.bytes.is_empty() {
275            let len = self.bytes.len() as u64;
276            for (i, byte) in bytes.iter_mut().enumerate() {
277                *byte = self.bytes[(self.ctr.wrapping_add(i as u64) % len) as usize];
278            }
279        }
280        let word = u64::from_be_bytes(bytes);
281
282        // Mix the structured word into a high-quality output block without
283        // hashing the entire seed into an avalanche-style global state.
284        let ctr = self.ctr;
285        self.ctr = self.ctr.wrapping_add(1);
286        mix64(word ^ ctr ^ crate::GOLDEN_RATIO)
287    }
288
289    fn fill_bytes_stream(&mut self, dest: &mut [u8]) {
290        let mut written = 0;
291        while written < dest.len() {
292            if self.cache_pos == self.cache.len() {
293                // Cache block bytes so outputs are stable regardless of whether
294                // callers pull randomness as bytes or words:
295                //
296                // next_u64() stream bytes == fill_bytes() stream bytes.
297                self.cache = self.next_block_u64().to_be_bytes();
298                self.cache_pos = 0;
299            }
300
301            let available = self.cache.len() - self.cache_pos;
302            let need = dest.len() - written;
303            let take = available.min(need);
304            dest[written..written + take]
305                .copy_from_slice(&self.cache[self.cache_pos..self.cache_pos + take]);
306            self.cache_pos += take;
307            written += take;
308        }
309    }
310}
311
312#[stability(ALPHA)]
313impl TryRng for FuzzRng {
314    type Error = Infallible;
315
316    fn try_next_u32(&mut self) -> Result<u32, Self::Error> {
317        let mut buf = [0u8; 4];
318        self.fill_bytes_stream(&mut buf);
319        Ok(u32::from_be_bytes(buf))
320    }
321
322    fn try_next_u64(&mut self) -> Result<u64, Self::Error> {
323        let mut buf = [0u8; BLOCK_BYTES];
324        self.fill_bytes_stream(&mut buf);
325        Ok(u64::from_be_bytes(buf))
326    }
327
328    fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Self::Error> {
329        self.fill_bytes_stream(dest);
330        Ok(())
331    }
332}
333
334// SAFETY: FuzzRng is not cryptographically secure. It implements CryptoRng
335// only because the consensus fuzzer requires CryptoRng-bounded RNG. This type
336// must never be used outside of fuzz/test contexts.
337#[stability(ALPHA)]
338impl TryCryptoRng for FuzzRng {}
339
340#[cfg(test)]
341mod tests {
342    use super::*;
343    use rand::Rng;
344
345    #[test]
346    fn test_scripted_rng_output_forms() {
347        let mut rng = ScriptedRng::new([
348            0x0123_4567_89ab_cdef,
349            0xfedc_ba98_7654_3210,
350            0x0807_0605_0403_0201,
351        ]);
352
353        assert_eq!(rng.try_next_u64().unwrap(), 0x0123_4567_89ab_cdef);
354        assert_eq!(rng.try_next_u32().unwrap(), 0x7654_3210);
355
356        let mut bytes = [0; 5];
357        rng.try_fill_bytes(&mut bytes).unwrap();
358        assert_eq!(bytes, [1, 2, 3, 4, 5]);
359    }
360
361    #[test]
362    fn test_empty_bytes_not_constant() {
363        let mut rng = FuzzRng::new(vec![]);
364
365        let values: Vec<_> = (0..BLOCK_BYTES).map(|_| rng.next_u64()).collect();
366        assert!(values.windows(2).any(|w| w[0] != w[1]));
367    }
368
369    #[test]
370    fn test_empty_bytes_deterministic() {
371        let mut rng1 = FuzzRng::new(vec![]);
372        let mut rng2 = FuzzRng::new(vec![]);
373
374        for _ in 0..256 {
375            assert_eq!(rng1.next_u64(), rng2.next_u64());
376        }
377    }
378
379    #[test]
380    fn test_all_zero_bytes_not_constant() {
381        let bytes = vec![0; BLOCK_BYTES];
382        let mut rng = FuzzRng::new(bytes);
383        let values: Vec<_> = (0..BLOCK_BYTES).map(|_| rng.next_u64()).collect();
384        assert!(values.windows(2).any(|w| w[0] != w[1]));
385    }
386
387    #[test]
388    fn test_deterministic_with_same_input() {
389        let bytes = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
390
391        let mut rng1 = FuzzRng::new(bytes.clone());
392        let mut rng2 = FuzzRng::new(bytes);
393
394        for _ in 0..1000 {
395            assert_eq!(rng1.next_u64(), rng2.next_u64());
396        }
397    }
398
399    #[test]
400    fn test_short_input_wraparound() {
401        for len in 1..=3 {
402            let bytes = vec![0xAB; len];
403            let mut rng1 = FuzzRng::new(bytes.clone());
404            let mut rng2 = FuzzRng::new(bytes);
405            let out1: Vec<_> = (0..32).map(|_| rng1.next_u64()).collect();
406            let out2: Vec<_> = (0..32).map(|_| rng2.next_u64()).collect();
407            assert_eq!(out1, out2);
408            assert!(out1.windows(2).any(|w| w[0] != w[1]));
409        }
410    }
411
412    #[test]
413    fn test_small_mutation_locality() {
414        let mut base = vec![0u8; 64];
415        for (i, byte) in base.iter_mut().enumerate() {
416            *byte = i as u8;
417        }
418        let mut mutated = base.clone();
419        let mutated_pos = 20usize;
420        mutated[mutated_pos] ^= 0x01;
421
422        let mut rng_a = FuzzRng::new(base);
423        let mut rng_b = FuzzRng::new(mutated);
424
425        let draws = 40usize;
426        let mut diff_indices = Vec::new();
427        for i in 0..draws {
428            if rng_a.next_u64() != rng_b.next_u64() {
429                diff_indices.push(i);
430            }
431        }
432
433        let expected: Vec<usize> = ((mutated_pos - 7)..=mutated_pos).collect();
434        assert_eq!(diff_indices, expected);
435    }
436
437    #[test]
438    fn test_small_mutation_locality_wraparound() {
439        let mut base = vec![0u8; 64];
440        for (i, byte) in base.iter_mut().enumerate() {
441            *byte = i as u8;
442        }
443        let mut mutated = base.clone();
444        let mutated_pos = 2usize;
445        mutated[mutated_pos] ^= 0x01;
446
447        let mut rng_a = FuzzRng::new(base);
448        let mut rng_b = FuzzRng::new(mutated);
449
450        let draws = 64usize;
451        let mut diff_indices = Vec::new();
452        for i in 0..draws {
453            if rng_a.next_u64() != rng_b.next_u64() {
454                diff_indices.push(i);
455            }
456        }
457
458        assert_eq!(diff_indices, vec![0, 1, 2, 59, 60, 61, 62, 63]);
459    }
460
461    #[test]
462    fn test_fill_bytes_shape_stability() {
463        let bytes: Vec<u8> = (0..32u8).collect();
464
465        let mut from_u64_rng = FuzzRng::new(bytes.clone());
466        let mut from_u64 = Vec::with_capacity(128);
467        for _ in 0..16 {
468            from_u64.extend_from_slice(&from_u64_rng.next_u64().to_be_bytes());
469        }
470
471        let mut from_fill_rng = FuzzRng::new(bytes);
472        let mut from_fill = vec![0u8; from_u64.len()];
473        let chunk_sizes = [3usize, 1, 7, 2, 11, 5, 13, 17];
474        let mut offset = 0;
475        let mut idx = 0;
476        while offset < from_fill.len() {
477            let chunk = chunk_sizes[idx % chunk_sizes.len()].min(from_fill.len() - offset);
478            from_fill_rng.fill_bytes(&mut from_fill[offset..offset + chunk]);
479            offset += chunk;
480            idx += 1;
481        }
482        assert_eq!(from_u64, from_fill);
483    }
484
485    #[test]
486    fn test_next_u32_consistency_with_fill_bytes() {
487        let bytes: Vec<u8> = (0..16u8).collect();
488
489        let mut from_u32_rng = FuzzRng::new(bytes.clone());
490        let mut from_u32 = Vec::with_capacity(64);
491        for _ in 0..16 {
492            from_u32.extend_from_slice(&from_u32_rng.next_u32().to_be_bytes());
493        }
494
495        let mut from_fill_rng = FuzzRng::new(bytes);
496        let mut from_fill = vec![0u8; from_u32.len()];
497        from_fill_rng.fill_bytes(&mut from_fill);
498        assert_eq!(from_u32, from_fill);
499    }
500
501    #[test]
502    fn test_try_fill_bytes_consistency_with_fill_bytes() {
503        let bytes: Vec<u8> = (0..16u8).collect();
504
505        let mut fill_rng = FuzzRng::new(bytes.clone());
506        let mut try_fill_rng = FuzzRng::new(bytes);
507
508        let mut fill_out = vec![0u8; 257];
509        fill_rng.fill_bytes(&mut fill_out);
510
511        let mut try_out = vec![0u8; 257];
512        try_fill_rng
513            .try_fill_bytes(&mut try_out)
514            .expect("try_fill_bytes should never fail");
515
516        assert_eq!(fill_out, try_out);
517    }
518
519    #[test]
520    fn test_next_u64_includes_counter_in_mix_input() {
521        // Use a constant source window so any change between blocks comes from
522        // counter mixing, not from different window bytes.
523        let bytes = vec![0xAA; BLOCK_BYTES];
524        let mut rng = FuzzRng::new(bytes.clone());
525
526        let mut source = [0u8; BLOCK_BYTES];
527        source.copy_from_slice(&bytes[..BLOCK_BYTES]);
528        let word = u64::from_be_bytes(source);
529
530        let mix = |mut x: u64| {
531            x ^= x >> 30;
532            x = x.wrapping_mul(0xbf58476d1ce4e5b9);
533            x ^= x >> 27;
534            x = x.wrapping_mul(0x94d049bb133111eb);
535            x ^= x >> 31;
536            x
537        };
538
539        #[allow(clippy::identity_op)]
540        let expected0 = mix(word ^ 0 ^ crate::GOLDEN_RATIO);
541        let expected1 = mix(word ^ 1 ^ crate::GOLDEN_RATIO);
542
543        assert_eq!(rng.next_u64(), expected0);
544        assert_eq!(rng.next_u64(), expected1);
545    }
546
547    #[cfg(feature = "arbitrary")]
548    mod conformance {
549        use super::*;
550        use commonware_conformance::Conformance;
551        use rand::RngExt as _;
552
553        /// Conformance wrapper for FuzzRng that tests output stability.
554        ///
555        /// Derives both the input length and content from a seeded RNG so
556        /// conformance covers variable-length inputs including non-aligned
557        /// lengths that exercise wrapping.
558        struct FuzzRngConformance;
559
560        impl Conformance for FuzzRngConformance {
561            async fn commit(seed: u64) -> Vec<u8> {
562                let mut seed_rng = TestRng::new(seed);
563                let len = seed_rng.random_range(1..=64);
564                let mut input = vec![0u8; len];
565                seed_rng.fill_bytes(&mut input);
566
567                let mut rng = FuzzRng::new(input);
568                const CONFORMANCE_BLOCKS: usize = 32;
569
570                // Generate enough output to exercise wrapping and mixing.
571                let mut output = Vec::with_capacity(CONFORMANCE_BLOCKS * BLOCK_BYTES);
572                for _ in 0..CONFORMANCE_BLOCKS {
573                    output.extend_from_slice(&rng.next_u64().to_be_bytes());
574                }
575                output
576            }
577        }
578
579        commonware_conformance::conformance_tests! {
580            FuzzRngConformance => 1024,
581        }
582    }
583}
commonware_utils/rng.rs

commonware_utils/
rng.rs
