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::{rand_core::UnwrapErr, rngs::SysRng, CryptoRng};
8#[stability(ALPHA)]
9use rand::{rngs::StdRng, SeedableRng, TryCryptoRng, TryRng};
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/// Applies a SplitMix64-style finalizer to a deterministic input word.
74///
75/// This is useful for cheaply decorrelating derived deterministic seeds while
76/// preserving reproducibility.
77#[inline]
78#[stability(ALPHA)]
79pub const fn mix64(mut word: u64) -> u64 {
80    word ^= word >> 30;
81    word = word.wrapping_mul(0xbf58_476d_1ce4_e5b9);
82    word ^= word >> 27;
83    word = word.wrapping_mul(0x94d0_49bb_1331_11eb);
84    word ^ (word >> 31)
85}
86
87/// Width of each source window in bytes.
88#[stability(ALPHA)]
89const BLOCK_BYTES: usize = size_of::<u64>();
90
91/// An RNG that expands a fuzzer byte slice into an infinite deterministic stream.
92///
93/// # Design
94///
95/// `FuzzRng` maps a fuzzer-controlled byte slice to output blocks.
96///
97/// For each block counter `ctr`, it:
98/// 1. Reads a wrapping `u64`-wide window from the input bytes.
99/// 2. Xors in `ctr` and a domain constant.
100/// 3. Applies a SplitMix64-style finalizer.
101///
102/// ```text
103/// input bytes (len = N):
104///   [b0 b1 b2 ... b(N-1)]
105///
106/// block ctr = i:
107///   word_i bytes = [b(i+0)%N, b(i+1)%N, ... b(i+7)%N]
108///   word_i       = big-endian u64 of those bytes
109///   out_i        = mix64(word_i ^ i ^ DOMAIN)
110/// ```
111///
112/// # Why this mapping
113///
114/// Hashing the full input once and then seeding a PRNG makes tiny input changes
115/// look globally unrelated. This adapter avoids that by using a sliding window
116/// keyed by the block counter.
117///
118/// ```text
119/// byte k affects anchors:
120///   i in [k-(BLOCK_BYTES-1), ..., k] (mod N)
121/// ```
122///
123/// # Worked Example
124///
125/// With `N = 4`, input bytes repeat inside each block:
126///
127/// ```text
128/// input: [a b c d]
129///
130/// ctr=0: word bytes [a b c d a b c d]
131/// ctr=1: word bytes [b c d a b c d a]
132/// ctr=2: word bytes [c d a b c d a b]
133/// ...
134/// ```
135///
136/// Even for low-entropy input like `[0 0 0 0]`, output still changes because
137/// `ctr` is mixed into every block before finalization.
138///
139/// `fill_bytes` serves output from cached block bytes so callers get a stable
140/// byte stream regardless of whether they request randomness as `next_u64`,
141/// `next_u32`, or arbitrary byte slices.
142#[stability(ALPHA)]
143pub struct FuzzRng {
144    bytes: Vec<u8>,
145    ctr: u64,
146    cache: [u8; BLOCK_BYTES],
147    cache_pos: usize,
148}
149
150#[stability(ALPHA)]
151impl FuzzRng {
152    /// Creates a new `FuzzRng` from a byte buffer.
153    pub const fn new(bytes: Vec<u8>) -> Self {
154        Self {
155            bytes,
156            ctr: 0,
157            cache: [0u8; BLOCK_BYTES],
158            cache_pos: BLOCK_BYTES,
159        }
160    }
161
162    /// Generates the next mixed `u64` block from the fuzz input.
163    ///
164    /// Conceptually:
165    /// 1. Build `word` from a wrapping `BLOCK_BYTES` window anchored at `ctr`.
166    /// 2. Compute `mixed = mix64(word ^ ctr ^ GOLDEN_RATIO)`.
167    /// 3. Increment `ctr`.
168    ///
169    /// This keeps the output deterministic while preserving local mutation
170    /// influence: one input-byte mutation only affects nearby anchor counters.
171    #[inline]
172    fn next_block_u64(&mut self) -> u64 {
173        // Build a wrapping u64-width source word anchored at this block counter.
174        // A single fuzz-byte mutation only impacts nearby anchors.
175        let mut bytes = [0u8; BLOCK_BYTES];
176        if !self.bytes.is_empty() {
177            let len = self.bytes.len() as u64;
178            for (i, byte) in bytes.iter_mut().enumerate() {
179                *byte = self.bytes[(self.ctr.wrapping_add(i as u64) % len) as usize];
180            }
181        }
182        let word = u64::from_be_bytes(bytes);
183
184        // Mix the structured word into a high-quality output block without
185        // hashing the entire seed into an avalanche-style global state.
186        let ctr = self.ctr;
187        self.ctr = self.ctr.wrapping_add(1);
188        mix64(word ^ ctr ^ crate::GOLDEN_RATIO)
189    }
190
191    fn fill_bytes_stream(&mut self, dest: &mut [u8]) {
192        let mut written = 0;
193        while written < dest.len() {
194            if self.cache_pos == self.cache.len() {
195                // Cache block bytes so outputs are stable regardless of whether
196                // callers pull randomness as bytes or words:
197                //
198                // next_u64() stream bytes == fill_bytes() stream bytes.
199                self.cache = self.next_block_u64().to_be_bytes();
200                self.cache_pos = 0;
201            }
202
203            let available = self.cache.len() - self.cache_pos;
204            let need = dest.len() - written;
205            let take = available.min(need);
206            dest[written..written + take]
207                .copy_from_slice(&self.cache[self.cache_pos..self.cache_pos + take]);
208            self.cache_pos += take;
209            written += take;
210        }
211    }
212}
213
214#[stability(ALPHA)]
215impl TryRng for FuzzRng {
216    type Error = Infallible;
217
218    fn try_next_u32(&mut self) -> Result<u32, Self::Error> {
219        let mut buf = [0u8; 4];
220        self.fill_bytes_stream(&mut buf);
221        Ok(u32::from_be_bytes(buf))
222    }
223
224    fn try_next_u64(&mut self) -> Result<u64, Self::Error> {
225        let mut buf = [0u8; BLOCK_BYTES];
226        self.fill_bytes_stream(&mut buf);
227        Ok(u64::from_be_bytes(buf))
228    }
229
230    fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Self::Error> {
231        self.fill_bytes_stream(dest);
232        Ok(())
233    }
234}
235
236// SAFETY: FuzzRng is not cryptographically secure. It implements CryptoRng
237// only because the consensus fuzzer requires CryptoRng-bounded RNG. This type
238// must never be used outside of fuzz/test contexts.
239#[stability(ALPHA)]
240impl TryCryptoRng for FuzzRng {}
241
242#[cfg(test)]
243mod tests {
244    use super::*;
245    use rand::Rng;
246
247    #[test]
248    fn test_empty_bytes_not_constant() {
249        let mut rng = FuzzRng::new(vec![]);
250
251        let values: Vec<_> = (0..BLOCK_BYTES).map(|_| rng.next_u64()).collect();
252        assert!(values.windows(2).any(|w| w[0] != w[1]));
253    }
254
255    #[test]
256    fn test_empty_bytes_deterministic() {
257        let mut rng1 = FuzzRng::new(vec![]);
258        let mut rng2 = FuzzRng::new(vec![]);
259
260        for _ in 0..256 {
261            assert_eq!(rng1.next_u64(), rng2.next_u64());
262        }
263    }
264
265    #[test]
266    fn test_all_zero_bytes_not_constant() {
267        let bytes = vec![0; BLOCK_BYTES];
268        let mut rng = FuzzRng::new(bytes);
269        let values: Vec<_> = (0..BLOCK_BYTES).map(|_| rng.next_u64()).collect();
270        assert!(values.windows(2).any(|w| w[0] != w[1]));
271    }
272
273    #[test]
274    fn test_deterministic_with_same_input() {
275        let bytes = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
276
277        let mut rng1 = FuzzRng::new(bytes.clone());
278        let mut rng2 = FuzzRng::new(bytes);
279
280        for _ in 0..1000 {
281            assert_eq!(rng1.next_u64(), rng2.next_u64());
282        }
283    }
284
285    #[test]
286    fn test_short_input_wraparound() {
287        for len in 1..=3 {
288            let bytes = vec![0xAB; len];
289            let mut rng1 = FuzzRng::new(bytes.clone());
290            let mut rng2 = FuzzRng::new(bytes);
291            let out1: Vec<_> = (0..32).map(|_| rng1.next_u64()).collect();
292            let out2: Vec<_> = (0..32).map(|_| rng2.next_u64()).collect();
293            assert_eq!(out1, out2);
294            assert!(out1.windows(2).any(|w| w[0] != w[1]));
295        }
296    }
297
298    #[test]
299    fn test_small_mutation_locality() {
300        let mut base = vec![0u8; 64];
301        for (i, byte) in base.iter_mut().enumerate() {
302            *byte = i as u8;
303        }
304        let mut mutated = base.clone();
305        let mutated_pos = 20usize;
306        mutated[mutated_pos] ^= 0x01;
307
308        let mut rng_a = FuzzRng::new(base);
309        let mut rng_b = FuzzRng::new(mutated);
310
311        let draws = 40usize;
312        let mut diff_indices = Vec::new();
313        for i in 0..draws {
314            if rng_a.next_u64() != rng_b.next_u64() {
315                diff_indices.push(i);
316            }
317        }
318
319        let expected: Vec<usize> = ((mutated_pos - 7)..=mutated_pos).collect();
320        assert_eq!(diff_indices, expected);
321    }
322
323    #[test]
324    fn test_small_mutation_locality_wraparound() {
325        let mut base = vec![0u8; 64];
326        for (i, byte) in base.iter_mut().enumerate() {
327            *byte = i as u8;
328        }
329        let mut mutated = base.clone();
330        let mutated_pos = 2usize;
331        mutated[mutated_pos] ^= 0x01;
332
333        let mut rng_a = FuzzRng::new(base);
334        let mut rng_b = FuzzRng::new(mutated);
335
336        let draws = 64usize;
337        let mut diff_indices = Vec::new();
338        for i in 0..draws {
339            if rng_a.next_u64() != rng_b.next_u64() {
340                diff_indices.push(i);
341            }
342        }
343
344        assert_eq!(diff_indices, vec![0, 1, 2, 59, 60, 61, 62, 63]);
345    }
346
347    #[test]
348    fn test_fill_bytes_shape_stability() {
349        let bytes: Vec<u8> = (0..32u8).collect();
350
351        let mut from_u64_rng = FuzzRng::new(bytes.clone());
352        let mut from_u64 = Vec::with_capacity(128);
353        for _ in 0..16 {
354            from_u64.extend_from_slice(&from_u64_rng.next_u64().to_be_bytes());
355        }
356
357        let mut from_fill_rng = FuzzRng::new(bytes);
358        let mut from_fill = vec![0u8; from_u64.len()];
359        let chunk_sizes = [3usize, 1, 7, 2, 11, 5, 13, 17];
360        let mut offset = 0;
361        let mut idx = 0;
362        while offset < from_fill.len() {
363            let chunk = chunk_sizes[idx % chunk_sizes.len()].min(from_fill.len() - offset);
364            from_fill_rng.fill_bytes(&mut from_fill[offset..offset + chunk]);
365            offset += chunk;
366            idx += 1;
367        }
368        assert_eq!(from_u64, from_fill);
369    }
370
371    #[test]
372    fn test_next_u32_consistency_with_fill_bytes() {
373        let bytes: Vec<u8> = (0..16u8).collect();
374
375        let mut from_u32_rng = FuzzRng::new(bytes.clone());
376        let mut from_u32 = Vec::with_capacity(64);
377        for _ in 0..16 {
378            from_u32.extend_from_slice(&from_u32_rng.next_u32().to_be_bytes());
379        }
380
381        let mut from_fill_rng = FuzzRng::new(bytes);
382        let mut from_fill = vec![0u8; from_u32.len()];
383        from_fill_rng.fill_bytes(&mut from_fill);
384        assert_eq!(from_u32, from_fill);
385    }
386
387    #[test]
388    fn test_try_fill_bytes_consistency_with_fill_bytes() {
389        let bytes: Vec<u8> = (0..16u8).collect();
390
391        let mut fill_rng = FuzzRng::new(bytes.clone());
392        let mut try_fill_rng = FuzzRng::new(bytes);
393
394        let mut fill_out = vec![0u8; 257];
395        fill_rng.fill_bytes(&mut fill_out);
396
397        let mut try_out = vec![0u8; 257];
398        try_fill_rng
399            .try_fill_bytes(&mut try_out)
400            .expect("try_fill_bytes should never fail");
401
402        assert_eq!(fill_out, try_out);
403    }
404
405    #[test]
406    fn test_next_u64_includes_counter_in_mix_input() {
407        // Use a constant source window so any change between blocks comes from
408        // counter mixing, not from different window bytes.
409        let bytes = vec![0xAA; BLOCK_BYTES];
410        let mut rng = FuzzRng::new(bytes.clone());
411
412        let mut source = [0u8; BLOCK_BYTES];
413        source.copy_from_slice(&bytes[..BLOCK_BYTES]);
414        let word = u64::from_be_bytes(source);
415
416        let mix = |mut x: u64| {
417            x ^= x >> 30;
418            x = x.wrapping_mul(0xbf58476d1ce4e5b9);
419            x ^= x >> 27;
420            x = x.wrapping_mul(0x94d049bb133111eb);
421            x ^= x >> 31;
422            x
423        };
424
425        #[allow(clippy::identity_op)]
426        let expected0 = mix(word ^ 0 ^ crate::GOLDEN_RATIO);
427        let expected1 = mix(word ^ 1 ^ crate::GOLDEN_RATIO);
428
429        assert_eq!(rng.next_u64(), expected0);
430        assert_eq!(rng.next_u64(), expected1);
431    }
432
433    #[cfg(feature = "arbitrary")]
434    mod conformance {
435        use super::*;
436        use commonware_conformance::Conformance;
437        use rand::RngExt as _;
438
439        /// Conformance wrapper for FuzzRng that tests output stability.
440        ///
441        /// Derives both the input length and content from a seeded RNG so
442        /// conformance covers variable-length inputs including non-aligned
443        /// lengths that exercise wrapping.
444        struct FuzzRngConformance;
445
446        impl Conformance for FuzzRngConformance {
447            async fn commit(seed: u64) -> Vec<u8> {
448                let mut seed_rng = TestRng::new(seed);
449                let len = seed_rng.random_range(1..=64);
450                let mut input = vec![0u8; len];
451                seed_rng.fill_bytes(&mut input);
452
453                let mut rng = FuzzRng::new(input);
454                const CONFORMANCE_BLOCKS: usize = 32;
455
456                // Generate enough output to exercise wrapping and mixing.
457                let mut output = Vec::with_capacity(CONFORMANCE_BLOCKS * BLOCK_BYTES);
458                for _ in 0..CONFORMANCE_BLOCKS {
459                    output.extend_from_slice(&rng.next_u64().to_be_bytes());
460                }
461                output
462            }
463        }
464
465        commonware_conformance::conformance_tests! {
466            FuzzRngConformance => 1024,
467        }
468    }
469}
commonware_utils/rng.rs

commonware_utils/
rng.rs
