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