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