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