miden-crypto/src/rand/rpx.rs
src/rand/rpx.rsRaw
1use super::{Felt, FeltRng, FieldElement, RandomCoin, RandomCoinError, RngCore, Word, ZERO};
2use crate::{
3 hash::rpx::{Rpx256, RpxDigest},
4 utils::{ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable},
5};
6use alloc::{string::ToString, vec::Vec};
7use rand_core::impls;
8
9// CONSTANTS
10// ================================================================================================
11
12const STATE_WIDTH: usize = Rpx256::STATE_WIDTH;
13const RATE_START: usize = Rpx256::RATE_RANGE.start;
14const RATE_END: usize = Rpx256::RATE_RANGE.end;
15const HALF_RATE_WIDTH: usize = (Rpx256::RATE_RANGE.end - Rpx256::RATE_RANGE.start) / 2;
16
17// RPX RANDOM COIN
18// ================================================================================================
19/// A simplified version of the `SPONGE_PRG` reseedable pseudo-random number generator algorithm
20/// described in <https://eprint.iacr.org/2011/499.pdf>.
21///
22/// The simplification is related to the following facts:
23/// 1. A call to the reseed method implies one and only one call to the permutation function.
24/// This is possible because in our case we never reseed with more than 4 field elements.
25/// 2. As a result of the previous point, we don't make use of an input buffer to accumulate seed
26/// material.
27#[derive(Debug, Clone, Copy, PartialEq, Eq)]
28pub struct RpxRandomCoin {
29 state: [Felt; STATE_WIDTH],
30 current: usize,
31}
32
33impl RpxRandomCoin {
34 /// Returns a new [RpxRandomCoin] initialize with the specified seed.
35 pub fn new(seed: Word) -> Self {
36 let mut state = [ZERO; STATE_WIDTH];
37
38 for i in 0..HALF_RATE_WIDTH {
39 state[RATE_START + i] += seed[i];
40 }
41
42 // Absorb
43 Rpx256::apply_permutation(&mut state);
44
45 RpxRandomCoin { state, current: RATE_START }
46 }
47
48 /// Returns an [RpxRandomCoin] instantiated from the provided components.
49 ///
50 /// # Panics
51 /// Panics if `current` is smaller than 4 or greater than or equal to 12.
52 pub fn from_parts(state: [Felt; STATE_WIDTH], current: usize) -> Self {
53 assert!(
54 (RATE_START..RATE_END).contains(¤t),
55 "current value outside of valid range"
56 );
57 Self { state, current }
58 }
59
60 /// Returns components of this random coin.
61 pub fn into_parts(self) -> ([Felt; STATE_WIDTH], usize) {
62 (self.state, self.current)
63 }
64
65 /// Fills `dest` with random data.
66 pub fn fill_bytes(&mut self, dest: &mut [u8]) {
67 <Self as RngCore>::fill_bytes(self, dest)
68 }
69
70 fn draw_basefield(&mut self) -> Felt {
71 if self.current == RATE_END {
72 Rpx256::apply_permutation(&mut self.state);
73 self.current = RATE_START;
74 }
75
76 self.current += 1;
77 self.state[self.current - 1]
78 }
79}
80
81// RANDOM COIN IMPLEMENTATION
82// ------------------------------------------------------------------------------------------------
83
84impl RandomCoin for RpxRandomCoin {
85 type BaseField = Felt;
86 type Hasher = Rpx256;
87
88 fn new(seed: &[Self::BaseField]) -> Self {
89 let digest: Word = Rpx256::hash_elements(seed).into();
90 Self::new(digest)
91 }
92
93 fn reseed(&mut self, data: RpxDigest) {
94 // Reset buffer
95 self.current = RATE_START;
96
97 // Add the new seed material to the first half of the rate portion of the RPX state
98 let data: Word = data.into();
99
100 self.state[RATE_START] += data[0];
101 self.state[RATE_START + 1] += data[1];
102 self.state[RATE_START + 2] += data[2];
103 self.state[RATE_START + 3] += data[3];
104
105 // Absorb
106 Rpx256::apply_permutation(&mut self.state);
107 }
108
109 fn check_leading_zeros(&self, value: u64) -> u32 {
110 let value = Felt::new(value);
111 let mut state_tmp = self.state;
112
113 state_tmp[RATE_START] += value;
114
115 Rpx256::apply_permutation(&mut state_tmp);
116
117 let first_rate_element = state_tmp[RATE_START].as_int();
118 first_rate_element.trailing_zeros()
119 }
120
121 fn draw<E: FieldElement<BaseField = Felt>>(&mut self) -> Result<E, RandomCoinError> {
122 let ext_degree = E::EXTENSION_DEGREE;
123 let mut result = vec![ZERO; ext_degree];
124 for r in result.iter_mut().take(ext_degree) {
125 *r = self.draw_basefield();
126 }
127
128 let result = E::slice_from_base_elements(&result);
129 Ok(result[0])
130 }
131
132 fn draw_integers(
133 &mut self,
134 num_values: usize,
135 domain_size: usize,
136 nonce: u64,
137 ) -> Result<Vec<usize>, RandomCoinError> {
138 assert!(domain_size.is_power_of_two(), "domain size must be a power of two");
139 assert!(num_values < domain_size, "number of values must be smaller than domain size");
140
141 // absorb the nonce
142 let nonce = Felt::new(nonce);
143 self.state[RATE_START] += nonce;
144 Rpx256::apply_permutation(&mut self.state);
145
146 // reset the buffer
147 self.current = RATE_START;
148
149 // determine how many bits are needed to represent valid values in the domain
150 let v_mask = (domain_size - 1) as u64;
151
152 // draw values from PRNG until we get as many unique values as specified by num_queries
153 let mut values = Vec::new();
154 for _ in 0..1000 {
155 // get the next pseudo-random field element
156 let value = self.draw_basefield().as_int();
157
158 // use the mask to get a value within the range
159 let value = (value & v_mask) as usize;
160
161 values.push(value);
162 if values.len() == num_values {
163 break;
164 }
165 }
166
167 if values.len() < num_values {
168 return Err(RandomCoinError::FailedToDrawIntegers(num_values, values.len(), 1000));
169 }
170
171 Ok(values)
172 }
173}
174
175// FELT RNG IMPLEMENTATION
176// ------------------------------------------------------------------------------------------------
177
178impl FeltRng for RpxRandomCoin {
179 fn draw_element(&mut self) -> Felt {
180 self.draw_basefield()
181 }
182
183 fn draw_word(&mut self) -> Word {
184 let mut output = [ZERO; 4];
185 for o in output.iter_mut() {
186 *o = self.draw_basefield();
187 }
188 output
189 }
190}
191
192// RNGCORE IMPLEMENTATION
193// ------------------------------------------------------------------------------------------------
194
195impl RngCore for RpxRandomCoin {
196 fn next_u32(&mut self) -> u32 {
197 self.draw_basefield().as_int() as u32
198 }
199
200 fn next_u64(&mut self) -> u64 {
201 impls::next_u64_via_u32(self)
202 }
203
204 fn fill_bytes(&mut self, dest: &mut [u8]) {
205 impls::fill_bytes_via_next(self, dest)
206 }
207
208 fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), rand::Error> {
209 self.fill_bytes(dest);
210 Ok(())
211 }
212}
213
214// SERIALIZATION
215// ------------------------------------------------------------------------------------------------
216
217impl Serializable for RpxRandomCoin {
218 fn write_into<W: ByteWriter>(&self, target: &mut W) {
219 self.state.iter().for_each(|v| v.write_into(target));
220 // casting to u8 is OK because `current` is always between 4 and 12.
221 target.write_u8(self.current as u8);
222 }
223}
224
225impl Deserializable for RpxRandomCoin {
226 fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
227 let state = [
228 Felt::read_from(source)?,
229 Felt::read_from(source)?,
230 Felt::read_from(source)?,
231 Felt::read_from(source)?,
232 Felt::read_from(source)?,
233 Felt::read_from(source)?,
234 Felt::read_from(source)?,
235 Felt::read_from(source)?,
236 Felt::read_from(source)?,
237 Felt::read_from(source)?,
238 Felt::read_from(source)?,
239 Felt::read_from(source)?,
240 ];
241 let current = source.read_u8()? as usize;
242 if !(RATE_START..RATE_END).contains(¤t) {
243 return Err(DeserializationError::InvalidValue(
244 "current value outside of valid range".to_string(),
245 ));
246 }
247 Ok(Self { state, current })
248 }
249}
250
251// TESTS
252// ================================================================================================
253
254#[cfg(test)]
255mod tests {
256 use super::{Deserializable, FeltRng, RpxRandomCoin, Serializable, ZERO};
257 use crate::ONE;
258
259 #[test]
260 fn test_feltrng_felt() {
261 let mut rpxcoin = RpxRandomCoin::new([ZERO; 4]);
262 let output = rpxcoin.draw_element();
263
264 let mut rpxcoin = RpxRandomCoin::new([ZERO; 4]);
265 let expected = rpxcoin.draw_basefield();
266
267 assert_eq!(output, expected);
268 }
269
270 #[test]
271 fn test_feltrng_word() {
272 let mut rpxcoin = RpxRandomCoin::new([ZERO; 4]);
273 let output = rpxcoin.draw_word();
274
275 let mut rpocoin = RpxRandomCoin::new([ZERO; 4]);
276 let mut expected = [ZERO; 4];
277 for o in expected.iter_mut() {
278 *o = rpocoin.draw_basefield();
279 }
280
281 assert_eq!(output, expected);
282 }
283
284 #[test]
285 fn test_feltrng_serialization() {
286 let coin1 = RpxRandomCoin::from_parts([ONE; 12], 5);
287
288 let bytes = coin1.to_bytes();
289 let coin2 = RpxRandomCoin::read_from_bytes(&bytes).unwrap();
290 assert_eq!(coin1, coin2);
291 }
292}