nois/
sub_randomness.rs

1use rand_xoshiro::{rand_core::RngCore, Xoshiro256PlusPlus};
2use xxhash_rust::xxh3::xxh3_128;
3
4use crate::prng::make_prng;
5
6pub struct SubRandomnessProvider {
7    rng: Xoshiro256PlusPlus,
8}
9
10impl SubRandomnessProvider {
11    pub fn provide(&mut self) -> [u8; 32] {
12        let mut out = [0u8; 32];
13        self.rng.fill_bytes(&mut out);
14        out
15    }
16}
17
18impl Iterator for SubRandomnessProvider {
19    type Item = [u8; 32];
20
21    fn next(&mut self) -> Option<Self::Item> {
22        Some(self.provide())
23    }
24}
25
26/// Takes a randomness and a key. Returns an arbitrary number of sub-randomnesses.
27/// The key is mixed into the randomness such that calling this function with different keys
28/// leads to different outputs. Calling it with the same key and randomness leads to the same outputs.
29///
30/// # Examples
31///
32/// Rolling two dice
33///
34/// ```
35/// use nois::{int_in_range, randomness_from_str, sub_randomness_with_key};
36///
37/// let randomness = randomness_from_str("9e8e26615f51552aa3b18b6f0bcf0dae5afbe30321e8d7ea7fa51ebeb1d8fe62").unwrap();
38///
39/// let mut provider = sub_randomness_with_key(randomness, "Key");
40///
41/// let dice1_subrandomness = provider.provide();
42/// let dice2_subrandomness = provider.provide();
43///
44/// let dice1_result = int_in_range(dice1_subrandomness, 1, 6);
45/// let dice2_result = int_in_range(dice2_subrandomness, 1, 6);
46/// ```
47pub fn sub_randomness_with_key(
48    mut randomness: [u8; 32],
49    key: impl AsRef<[u8]>,
50) -> Box<SubRandomnessProvider> {
51    let hashed_key = xxh3_128(key.as_ref()).to_be_bytes();
52    for (pos, byte) in hashed_key.iter().enumerate() {
53        randomness[pos] ^= byte;
54    }
55
56    let rng = make_prng(randomness);
57
58    Box::new(SubRandomnessProvider { rng })
59}
60
61/// Takes a randomness and a key. Returns an arbitrary number of sub-randomnesses.
62///
63/// This is equivalent to calling [`sub_randomness_with_key`] with key `b"_^default^_"`.
64///
65/// # Example
66///
67/// Rolling two dice
68///
69///  ```
70/// use nois::{int_in_range, randomness_from_str, sub_randomness};
71///
72/// let randomness = randomness_from_str("9e8e26615f51552aa3b18b6f0bcf0dae5afbe30321e8d7ea7fa51ebeb1d8fe62").unwrap();
73///
74/// let mut provider = sub_randomness(randomness);
75///
76/// let dice1_subrandomness = provider.provide();
77/// let dice2_subrandomness = provider.provide();
78///
79/// let dice1_result = int_in_range(dice1_subrandomness, 1, 6);
80/// let dice2_result = int_in_range(dice2_subrandomness, 1, 6);
81/// ```
82///
83/// Roll 1200 dice using the iterator interface:
84///
85/// ```
86/// use std::collections::BTreeMap;
87/// use nois::{randomness_from_str, roll_dice, sub_randomness};
88///
89/// let randomness = randomness_from_str("9e8e26615f51552aa3b18b6f0bcf0dae5afbe30321e8d7ea7fa51ebeb1d8fe62").unwrap();
90///
91/// let mut results = BTreeMap::<u8, usize>::new();
92/// for sub_randomness in sub_randomness(randomness).take(1200) {
93///     let number = roll_dice(sub_randomness);
94///     let current = results.get(&number).copied().unwrap_or_default();
95///     results.insert(number, current + 1);
96/// }
97/// let ones = results.get(&1).copied().unwrap_or_default();
98/// let twos = results.get(&2).copied().unwrap_or_default();
99/// let threes = results.get(&3).copied().unwrap_or_default();
100/// let fours = results.get(&4).copied().unwrap_or_default();
101/// let fives = results.get(&5).copied().unwrap_or_default();
102/// let sixes = results.get(&6).copied().unwrap_or_default();
103/// println!("{ones} {twos} {threes} {fours} {fives} {sixes}");
104/// assert!(ones > 160 && ones < 240);
105/// assert!(twos > 160 && twos < 240);
106/// assert!(threes > 160 && threes < 240);
107/// assert!(fours > 160 && fours < 240);
108/// assert!(fives > 160 && fives < 240);
109/// assert!(sixes > 160 && sixes < 240);
110/// assert_eq!(results.values().sum::<usize>(), 1200);
111/// ```
112pub fn sub_randomness(randomness: [u8; 32]) -> Box<SubRandomnessProvider> {
113    sub_randomness_with_key(randomness, b"_^default^_")
114}
115
116#[cfg(test)]
117mod tests {
118    use crate::{coinflip, pick, RANDOMNESS1};
119
120    use super::*;
121
122    #[test]
123    fn sub_randomness_with_key_works() {
124        // outputs are the same for the same randomness and key
125        let mut provider1 = sub_randomness_with_key([0xA6; 32], "A");
126        let mut provider2 = sub_randomness_with_key([0xA6; 32], "A");
127        assert_eq!(provider1.provide(), provider2.provide());
128        assert_eq!(provider1.provide(), provider2.provide());
129        assert_eq!(provider1.provide(), provider2.provide());
130
131        // outputs are different for the same randomness and different key
132        let mut provider1 = sub_randomness_with_key([0xA6; 32], "/my_namespace/ab");
133        let mut provider2 = sub_randomness_with_key([0xA6; 32], "/my_namespace/cd");
134        assert_ne!(provider1.provide(), provider2.provide());
135        assert_ne!(provider1.provide(), provider2.provide());
136        assert_ne!(provider1.provide(), provider2.provide());
137    }
138
139    #[test]
140    fn sub_randomness_works() {
141        let randomness: [u8; 32] = [0x77; 32];
142        let mut provider = sub_randomness(randomness);
143        let v1 = provider.provide();
144        let v2 = provider.provide();
145        let v3 = provider.provide();
146        let v4 = provider.provide();
147        println!("v1 = {v1:?}");
148        println!("v2 = {v2:?}");
149        println!("v3 = {v3:?}");
150        println!("v4 = {v4:?}");
151
152        // outputs are the same for the same randomness
153        let mut provider1 = sub_randomness([0xA6; 32]);
154        let mut provider2 = sub_randomness([0xA6; 32]);
155        assert_eq!(provider1.provide(), provider2.provide());
156        assert_eq!(provider1.provide(), provider2.provide());
157        assert_eq!(provider1.provide(), provider2.provide());
158
159        // outputs differ for different randomness
160        let mut provider1 = sub_randomness([0xA6; 32]);
161        let mut provider2 = sub_randomness([0xCF; 32]);
162        assert_ne!(provider1.provide(), provider2.provide());
163        assert_ne!(provider1.provide(), provider2.provide());
164        assert_ne!(provider1.provide(), provider2.provide());
165
166        // outputs are the same for the same as sub_randomness_with_key with "_^default^_"
167        let mut provider1 = sub_randomness([0xA6; 32]);
168        let mut provider2 = sub_randomness_with_key([0xA6; 32], "_^default^_");
169        assert_eq!(provider1.provide(), provider2.provide());
170        assert_eq!(provider1.provide(), provider2.provide());
171        assert_eq!(provider1.provide(), provider2.provide());
172    }
173
174    #[test]
175    fn sub_randomness_implements_iterator() {
176        let randomness: [u8; 32] = [0x77; 32];
177        let mut provider = sub_randomness(randomness);
178        let v1 = provider.next().unwrap();
179        let v2 = provider.next().unwrap();
180        let v3 = provider.next().unwrap();
181        let v4 = provider.next().unwrap();
182        println!("v1 = {v1:?}");
183        println!("v2 = {v2:?}");
184        println!("v3 = {v3:?}");
185        println!("v4 = {v4:?}");
186    }
187    #[test]
188    fn coinflip_distribution_is_uniform() {
189        /// This test will generate a huge amount  of subrandomness
190        /// and throws a coin with every subrandomness
191        /// then checks that the distribution is expected within a range of 1%
192        use crate::sub_randomness::sub_randomness;
193        use std::collections::HashMap;
194
195        const TEST_SAMPLE_SIZE: usize = 100_000;
196        const ACCURACY: f32 = 0.01;
197
198        let mut result = vec![];
199
200        let mut provider = sub_randomness(RANDOMNESS1);
201
202        for _ in 0..TEST_SAMPLE_SIZE {
203            let flip_is_heads = coinflip(provider.next().unwrap()).is_heads();
204            println!("{}", flip_is_heads);
205            result.push(flip_is_heads);
206        }
207
208        let mut histogram = HashMap::new();
209
210        for element in result {
211            let count = histogram.entry(element).or_insert(0);
212            *count += 1;
213        }
214
215        let estimated_count_for_uniform_distribution = (TEST_SAMPLE_SIZE / 2) as f32;
216        let estimation_min: i32 =
217            (estimated_count_for_uniform_distribution * (1_f32 - ACCURACY)) as i32;
218        let estimation_max: i32 =
219            (estimated_count_for_uniform_distribution * (1_f32 + ACCURACY)) as i32;
220        println!(
221            "estimation {}, max: {}, min: {}",
222            estimated_count_for_uniform_distribution, estimation_max, estimation_min
223        );
224        // This will assert on all the elements of the data 1 by 1 and check if their occurence is within the 1% expected range
225        for (bin, count) in histogram {
226            println!("{}: {}", bin, count);
227            assert!(count >= estimation_min && count <= estimation_max);
228        }
229    }
230
231    #[test]
232    fn pick_distribution_is_uniform() {
233        /// This test will generate a huge amount  of subrandomness and picks n elements from the list
234        /// It will then test that the outcome of every possibility within the picked value falls with 1% close
235        /// To what it should be in a uniform distribution
236        /// For this test to work properly for a 10 element size data consider choosing a TEST_SAMPLE_SIZE higher than 100_000
237        use crate::sub_randomness::sub_randomness;
238        use std::collections::HashMap;
239
240        const TEST_SAMPLE_SIZE: usize = 300_000;
241        const N_PICKED_ELEMENTS: usize = 3;
242        const ACCURACY: f32 = 0.01;
243
244        let data = vec![1, 2, 3, 4, 5, 6, 7, 8, 9];
245
246        let mut result = vec![vec![]];
247
248        let mut provider = sub_randomness(RANDOMNESS1);
249
250        for _ in 0..TEST_SAMPLE_SIZE - 1 {
251            let pick_result = pick(provider.next().unwrap(), N_PICKED_ELEMENTS, data.clone());
252
253            result.push(pick_result);
254        }
255
256        let mut histogram = HashMap::new();
257
258        for row in result {
259            for element in row {
260                let count = histogram.entry(element).or_insert(0);
261                *count += 1;
262            }
263        }
264        let estimated_count_for_uniform_distribution =
265            (TEST_SAMPLE_SIZE * N_PICKED_ELEMENTS / data.len()) as f32;
266        let estimation_min: i32 =
267            (estimated_count_for_uniform_distribution * (1_f32 - ACCURACY)) as i32;
268        let estimation_max: i32 =
269            (estimated_count_for_uniform_distribution * (1_f32 + ACCURACY)) as i32;
270        println!(
271            "estimation {}, max: {}, min: {}",
272            estimated_count_for_uniform_distribution, estimation_max, estimation_min
273        );
274        // This will assert on all the elements of the data 1 by 1 and check if their occurence is within the 1% expected range
275        for (bin, count) in histogram {
276            println!("{}: {}", bin, count);
277            assert!(count >= estimation_min && count <= estimation_max);
278        }
279    }
280}
nois/sub_randomness.rs

nois/
sub_randomness.rs
