9019555140

Committed 09 May 2024 03:24PM UTC coverage: 91.041%. Remained the same

Build # 9019555140

Build Type

push

github

Committed by

web-flow

Commit Message

chore: new version 0.20.1 (#228)

Release a new version

Run Details

3516 of 3862 relevant lines covered (91.04%)

58.37 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

87.88

/src/deterministic_randomizer.rs

// Copyright 2022 The Tari Project
// SPDX-License-Identifier: BSD-3-Clause

//! A deterministic randomizer with utility functions for operating on numbers and arrays in a reproducible and
//! platform-indepdent way.

use alloc::vec::Vec;
use core::convert::TryFrom;

use rand_core::{CryptoRng, RngCore, SeedableRng};

/// Error representing a failed shuffle
#[derive(Debug)]
pub struct RandomizerError;

/// A `DeterministicRandomizer` contains utility functions for working with pseudorandom number generators (PRNGs) where
/// reproducibility is important. While the `rand` crate has functionality for things like uniform sampling and
/// shuffling that can be used with PRNGs, there is no guarantee that these functions will always be implemented in the
/// same way across versions, which could lead to incompatibility or dependency troubles. This library has no specific
/// `rand` dependency, and implements deterministic sampling and shuffling that are implemented in straightforward ways
/// that will work identically across platforms. If you provide the same seed to the PRNG, you'll get the same results.
/// This can be useful for cases like consensus applications, when a set of clients need to agree on pseudorandom
/// results.
///
/// To avoid certain pitfalls, you need to choose a cryptographically-secure pseudorandom number generator (CSPRNG) that
/// implements `CryptoRng + RngCore + SeedableRng`; a good choice is something like `ChaCha12Rng` from the `rand_chacha`
/// crate (which happens to be the current `rand` default).
///
/// Once you instantiate the `DeterministicRandomizer` with your CSPRNG and a starting seed, you can start generating
/// bounded pseudorandom numbers or sampling or shuffling arrays deterministically. You can always reseed the randomizer
/// with a different seed, or reset it to the initial seed.
///
/// ```edition2018
/// # use tari_crypto::deterministic_randomizer::DeterministicRandomizer;
/// use rand_chacha::ChaCha12Rng;
///
/// // In consensus-type applications, the seed might come from a hash output whose input is some kind of state
/// // We'll just make one arbitrarily; it must be `[u8; N]` with `N <= 32`
/// let seed = [1u8; 32];
/// let mut randomizer = DeterministicRandomizer::<ChaCha12Rng>::new(seed);
///
/// // Generate bounded numbers in the range `[0, 1000)`
/// // Because it's deterministic, we know exactly what the results should be!
/// assert_eq!(randomizer.next_bounded_u64(1000).unwrap(), 573);
/// assert_eq!(randomizer.next_bounded_u64(1000).unwrap(), 786);
///
/// // Reset the generator, which uses the original seed we provided
/// randomizer.reset();
/// assert_eq!(randomizer.next_bounded_u64(1000).unwrap(), 573);
/// assert_eq!(randomizer.next_bounded_u64(1000).unwrap(), 786);
///
/// // We can also reseed using a new seed
/// // This has the same effect as creating a fresh `DeterministicRandomizer` with the new seed
/// let new_seed = [2u8; 32];
/// randomizer.reseed(new_seed);
///
/// // Shuffle an array in place (which may be of any type or length)
/// // Because it's still deterministic, we know exactly what the result should be!
/// let mut data = [0u32, 1u32, 2u32, 3u32, 4u32];
/// randomizer.shuffle(&mut data).unwrap();
/// assert_eq!(&data, &[2u32, 0u32, 4u32, 3u32, 1u32]);
///
/// // Get a shuffled sample of an array, leaving the original unchanged
/// let data = [0u32, 1u32, 2u32, 3u32, 4u32];
/// let sample = randomizer.sample(&data, 3).unwrap();
/// assert_eq!(&sample, &[3u32, 0u32, 4u32]);
/// ```
///
/// **WARNING**: While `DeterministicRandomizer` requires a cryptographically-secure pseudorandom number generator
/// (CSPRNG), it is _not_ suitable for non-deterministic use cases like key or nonce generation. If you aren't
/// absolutely sure that you need the functionality provided here, you should use a high-entropy non-deterministic
/// generator instead.
pub struct DeterministicRandomizer<R>
where R: SeedableRng
{
    prng: R,
    seed: <R as SeedableRng>::Seed,
}

impl<R> DeterministicRandomizer<R>
where
    R: CryptoRng + RngCore + SeedableRng,
    <R as SeedableRng>::Seed: Clone,
{
    /// Initialize the randomizer with a seed
    pub fn new(seed: <R as SeedableRng>::Seed) -> Self {
        Self {
            prng: R::from_seed(seed.clone()),
            seed,
        }
    }

    /// Reseed the randomizer with a new seed
    pub fn reseed(&mut self, seed: <R as SeedableRng>::Seed) {
        self.prng = R::from_seed(seed.clone());
        self.seed = seed;
    }

    /// Reset the randomizer using the seed last provided by either the constructor or reseeding
    pub fn reset(&mut self) {
        self.reseed(self.seed.clone());
    }

    /// Sample elements without replacement, shuffling their order
    pub fn sample<T>(&mut self, data: &[T], k: usize) -> Result<Vec<T>, RandomizerError>
    where T: Clone {
        // This currently reallocates; it could be made more efficient
        let mut result = data.to_vec();
        self.partial_shuffle(&mut result, k)?;

        Ok(result[(data.len() - k)..].to_vec())
    }

    /// Shuffle an array in place
    pub fn shuffle<T>(&mut self, data: &mut [T]) -> Result<(), RandomizerError> {
        self.partial_shuffle(data, data.len())?;

        Ok(())
    }

    /// Utility function for a partial in-place Fisher-Yates shuffle
    /// The last `n` items are fully shuffled, while the remaining items are not!
    #[allow(clippy::cast_possible_truncation)]
    fn partial_shuffle<T>(&mut self, data: &mut [T], n: usize) -> Result<(), RandomizerError> {
        if n > data.len() {
            return Err(RandomizerError);
        }
        let low = (data.len() - n) as u64;
        let high = data.len() as u64;

        // Perform the Durstenfeld variant of the Fisher-Yates shuffle
        for i in (low..high).rev() {
            // Note that we have to cast from `u64` to `usize`, so we need to ignore the truncation warning (we're fine
            // on 64-bit targets)
            let j = self.next_bounded_u64(i + 1).map(|j| j as usize)?;
            data.swap(i as usize, j);
        }

        Ok(())
    }

    /// Choose a random bounded 64-bit unsigned integer with exclusive upper bound
    pub fn next_bounded_u64(&mut self, upper: u64) -> Result<u64, RandomizerError> {
        // We can't get a `u128` directly from the generator
        let x = u128::from(self.prng.next_u64()) << 64 | u128::from(self.prng.next_u64());

        u64::try_from(x % u128::from(upper)).map_err(|_| RandomizerError)
    }
}

#[cfg(test)]
mod test {
    use rand_chacha::ChaCha12Rng;

    use super::DeterministicRandomizer;

    type R = DeterministicRandomizer<ChaCha12Rng>;

    #[test]
    fn test_shuffle() {
        let seed = [1u8; 32];
        let mut data = [0u8, 1u8, 2u8, 3u8];
        let mut randomizer = R::new(seed);

        randomizer.shuffle(&mut data).unwrap();
        assert_eq!(&data, &[0u8, 2u8, 3u8, 1u8]);
    }

    #[test]
    fn test_bounded_u64() {
        let seed = [1u8; 32];
        let mut randomizer = R::new(seed);

        assert_eq!(randomizer.next_bounded_u64(1000).unwrap(), 573);
        assert_eq!(randomizer.next_bounded_u64(1000).unwrap(), 786);
    }

    #[test]
    fn test_sample() {
        let seed = [1u8; 32];
        let data = [0u8, 1u8, 2u8, 3u8];
        let mut randomizer = R::new(seed);

        let sample = randomizer.sample(&data, 3).unwrap();
        assert_eq!(&sample, &[2u8, 3u8, 1u8]);
    }
}

1	// Copyright 2022 The Tari Project
2	// SPDX-License-Identifier: BSD-3-Clause
3
4	//! A deterministic randomizer with utility functions for operating on numbers and arrays in a reproducible and
5	//! platform-indepdent way.
6
7	use alloc::vec::Vec;
8	use core::convert::TryFrom;
9
10	use rand_core::{CryptoRng, RngCore, SeedableRng};
11
12	/// Error representing a failed shuffle
13	#[derive(Debug)]
14	pub struct RandomizerError;
15
16	/// A `DeterministicRandomizer` contains utility functions for working with pseudorandom number generators (PRNGs) where
17	/// reproducibility is important. While the `rand` crate has functionality for things like uniform sampling and
18	/// shuffling that can be used with PRNGs, there is no guarantee that these functions will always be implemented in the
19	/// same way across versions, which could lead to incompatibility or dependency troubles. This library has no specific
20	/// `rand` dependency, and implements deterministic sampling and shuffling that are implemented in straightforward ways
21	/// that will work identically across platforms. If you provide the same seed to the PRNG, you'll get the same results.
22	/// This can be useful for cases like consensus applications, when a set of clients need to agree on pseudorandom
23	/// results.
24	///
25	/// To avoid certain pitfalls, you need to choose a cryptographically-secure pseudorandom number generator (CSPRNG) that
26	/// implements `CryptoRng + RngCore + SeedableRng`; a good choice is something like `ChaCha12Rng` from the `rand_chacha`
27	/// crate (which happens to be the current `rand` default).
28	///
29	/// Once you instantiate the `DeterministicRandomizer` with your CSPRNG and a starting seed, you can start generating
30	/// bounded pseudorandom numbers or sampling or shuffling arrays deterministically. You can always reseed the randomizer
31	/// with a different seed, or reset it to the initial seed.
32	///
33	/// ```edition2018
34	/// # use tari_crypto::deterministic_randomizer::DeterministicRandomizer;
35	/// use rand_chacha::ChaCha12Rng;
36	///
37	/// // In consensus-type applications, the seed might come from a hash output whose input is some kind of state
38	/// // We'll just make one arbitrarily; it must be `[u8; N]` with `N <= 32`
39	/// let seed = [1u8; 32];
40	/// let mut randomizer = DeterministicRandomizer::<ChaCha12Rng>::new(seed);
41	///
42	/// // Generate bounded numbers in the range `[0, 1000)`
43	/// // Because it's deterministic, we know exactly what the results should be!
44	/// assert_eq!(randomizer.next_bounded_u64(1000).unwrap(), 573);
45	/// assert_eq!(randomizer.next_bounded_u64(1000).unwrap(), 786);
46	///
47	/// // Reset the generator, which uses the original seed we provided
48	/// randomizer.reset();
49	/// assert_eq!(randomizer.next_bounded_u64(1000).unwrap(), 573);
50	/// assert_eq!(randomizer.next_bounded_u64(1000).unwrap(), 786);
51	///
52	/// // We can also reseed using a new seed
53	/// // This has the same effect as creating a fresh `DeterministicRandomizer` with the new seed
54	/// let new_seed = [2u8; 32];
55	/// randomizer.reseed(new_seed);
56	///
57	/// // Shuffle an array in place (which may be of any type or length)
58	/// // Because it's still deterministic, we know exactly what the result should be!
59	/// let mut data = [0u32, 1u32, 2u32, 3u32, 4u32];
60	/// randomizer.shuffle(&mut data).unwrap();
61	/// assert_eq!(&data, &[2u32, 0u32, 4u32, 3u32, 1u32]);
62	///
63	/// // Get a shuffled sample of an array, leaving the original unchanged
64	/// let data = [0u32, 1u32, 2u32, 3u32, 4u32];
65	/// let sample = randomizer.sample(&data, 3).unwrap();
66	/// assert_eq!(&sample, &[3u32, 0u32, 4u32]);
67	/// ```
68	///
69	/// WARNING: While `DeterministicRandomizer` requires a cryptographically-secure pseudorandom number generator
70	/// (CSPRNG), it is _not_ suitable for non-deterministic use cases like key or nonce generation. If you aren't
71	/// absolutely sure that you need the functionality provided here, you should use a high-entropy non-deterministic
72	/// generator instead.
73	pub struct DeterministicRandomizer<R>
74	where R: SeedableRng
75	{
76	prng: R,
77	seed: <R as SeedableRng>::Seed,
78	}
79
80	impl<R> DeterministicRandomizer<R>
81	where
82	R: CryptoRng + RngCore + SeedableRng,
83	<R as SeedableRng>::Seed: Clone,
84	{
85	/// Initialize the randomizer with a seed
86	pub fn new(seed: <R as SeedableRng>::Seed) -> Self {	3✔
87	Self {	3✔
88	prng: R::from_seed(seed.clone()),	3✔
89	seed,	3✔
90	}	3✔
91	}	3✔
92
93	/// Reseed the randomizer with a new seed
94	pub fn reseed(&mut self, seed: <R as SeedableRng>::Seed) {	×
95	self.prng = R::from_seed(seed.clone());	×
96	self.seed = seed;	×
97	}	×
98
99	/// Reset the randomizer using the seed last provided by either the constructor or reseeding
100	pub fn reset(&mut self) {	×
101	self.reseed(self.seed.clone());	×
102	}	×
103
104	/// Sample elements without replacement, shuffling their order
105	pub fn sample<T>(&mut self, data: &[T], k: usize) -> Result<Vec<T>, RandomizerError>	1✔
106	where T: Clone {	1✔
107	// This currently reallocates; it could be made more efficient	1✔
108	let mut result = data.to_vec();	1✔
109	self.partial_shuffle(&mut result, k)?;	1✔
110
111	Ok(result[(data.len() - k)..].to_vec())	1✔
112	}	1✔
113
114	/// Shuffle an array in place
115	pub fn shuffle<T>(&mut self, data: &mut [T]) -> Result<(), RandomizerError> {	1✔
116	self.partial_shuffle(data, data.len())?;	1✔
117
118	Ok(())	1✔
119	}	1✔
120
121	/// Utility function for a partial in-place Fisher-Yates shuffle
122	/// The last `n` items are fully shuffled, while the remaining items are not!
123	#[allow(clippy::cast_possible_truncation)]
124	fn partial_shuffle<T>(&mut self, data: &mut [T], n: usize) -> Result<(), RandomizerError> {	2✔
125	if n > data.len() {	2✔
126	return Err(RandomizerError);	×
127	}	2✔
128	let low = (data.len() - n) as u64;	2✔
129	let high = data.len() as u64;	2✔
130
131	// Perform the Durstenfeld variant of the Fisher-Yates shuffle
132	for i in (low..high).rev() {	7✔
133	// Note that we have to cast from `u64` to `usize`, so we need to ignore the truncation warning (we're fine	7✔
134	// on 64-bit targets)	7✔
135	let j = self.next_bounded_u64(i + 1).map(\|j\| j as usize)?;	7✔
136	data.swap(i as usize, j);	7✔
137	}
138
139	Ok(())	2✔
140	}	2✔
141
142	/// Choose a random bounded 64-bit unsigned integer with exclusive upper bound
143	pub fn next_bounded_u64(&mut self, upper: u64) -> Result<u64, RandomizerError> {	9✔
144	// We can't get a `u128` directly from the generator	9✔
145	let x = u128::from(self.prng.next_u64()) << 64 \| u128::from(self.prng.next_u64());	9✔
146		9✔
147	u64::try_from(x % u128::from(upper)).map_err(\|_\| RandomizerError)	9✔
148	}	9✔
149	}
150
151	#[cfg(test)]
152	mod test {
153	use rand_chacha::ChaCha12Rng;
154
155	use super::DeterministicRandomizer;
156
157	type R = DeterministicRandomizer<ChaCha12Rng>;
158
159	#[test]
160	fn test_shuffle() {	1✔
161	let seed = [1u8; 32];	1✔
162	let mut data = [0u8, 1u8, 2u8, 3u8];	1✔
163	let mut randomizer = R::new(seed);	1✔
164		1✔
165	randomizer.shuffle(&mut data).unwrap();	1✔
166	assert_eq!(&data, &[0u8, 2u8, 3u8, 1u8]);	1✔
167	}	1✔
168
169	#[test]
170	fn test_bounded_u64() {	1✔
171	let seed = [1u8; 32];	1✔
172	let mut randomizer = R::new(seed);	1✔
173		1✔
174	assert_eq!(randomizer.next_bounded_u64(1000).unwrap(), 573);	1✔
175	assert_eq!(randomizer.next_bounded_u64(1000).unwrap(), 786);	1✔
176	}	1✔
177
178	#[test]
179	fn test_sample() {	1✔
180	let seed = [1u8; 32];	1✔
181	let data = [0u8, 1u8, 2u8, 3u8];	1✔
182	let mut randomizer = R::new(seed);	1✔
183		1✔
184	let sample = randomizer.sample(&data, 3).unwrap();	1✔
185	assert_eq!(&sample, &[2u8, 3u8, 1u8]);	1✔
186	}	1✔
187	}

tari-project / tari-crypto / 9019555140

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous