miden_crypto/rand/
eidos_coin.rs

1use alloc::string::ToString;
2
3use rand::{
4    Rng,
5    rand_core::{Infallible, TryRng, utils},
6};
7
8use super::{Felt, FeltRng};
9use crate::{
10    Word,
11    field::ExtensionField,
12    hash::eidos::{
13        Eidos,
14        domains::{RANDOM_COIN_OUTPUT, RANDOM_COIN_STATE},
15    },
16    utils::{ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable},
17};
18
19const OUTPUT_FELTS: usize = Word::NUM_ELEMENTS;
20
21/// A reseedable random coin built from Eidos compression.
22///
23/// State derivation and output generation use separate Eidos domains. Output block `i` is the
24/// field hash of the internal state and a non-wrapping `u64` counter. Reseeding replaces the state
25/// with the field hash of the current state, counter, and supplied data, discards buffered output,
26/// and resets the counter. The output path uses only Eidos field elements and is independent of
27/// the compression core's output representation. The stored random-coin state is distinct from
28/// the temporary, domain-specific chaining value constructed by each framed Eidos hash.
29///
30/// This counter-mode construction does not provide backtracking resistance within a reseed
31/// interval: knowledge of the stored state permits recomputing every output block derived from
32/// that state.
33#[derive(Debug, Clone, Copy, PartialEq, Eq)]
34pub struct EidosRandomCoin {
35    state: Word,
36    output: Word,
37    counter: u64,
38    current: usize,
39}
40
41impl EidosRandomCoin {
42    /// Returns a random coin initialized with `seed`.
43    pub fn new(seed: Word) -> Self {
44        let state = Eidos::hash_elements_in_domain(seed.as_elements(), RANDOM_COIN_STATE);
45        Self {
46            state,
47            output: Word::default(),
48            counter: 0,
49            current: OUTPUT_FELTS,
50        }
51    }
52
53    /// Returns a random coin reconstructed from its serialized components.
54    ///
55    /// `counter` is the index of the next output block and therefore the number of blocks generated
56    /// since initialization or the most recent reseed. If `current` is less than four, `output` is
57    /// the block at `counter - 1`, and `current` identifies its next candidate Felt. A value of
58    /// four means that the buffer is exhausted. This
59    /// constructor trusts `output`; it does not recompute the buffered block.
60    ///
61    /// # Panics
62    ///
63    /// Panics if `current` is greater than the number of buffered output elements, or if buffered
64    /// output is supplied before any output block has been generated.
65    pub fn from_parts(state: Word, output: Word, counter: u64, current: usize) -> Self {
66        assert!(current <= OUTPUT_FELTS, "current output index is out of range");
67        assert!(
68            current == OUTPUT_FELTS || counter != 0,
69            "buffered output requires a generated block"
70        );
71        Self { state, output, counter, current }
72    }
73
74    /// Returns `(state, output, counter, current)`.
75    ///
76    /// `counter` is the index of the next output block, and `current` is the next candidate Felt in
77    /// `output`. A `current` value equal to four marks an exhausted buffer.
78    pub fn into_parts(self) -> (Word, Word, u64, usize) {
79        (self.state, self.output, self.counter, self.current)
80    }
81
82    /// Fills `dest` with random bytes.
83    ///
84    /// # Panics
85    ///
86    /// Panics if output generation requires another block after the `u64` block counter is
87    /// exhausted.
88    pub fn fill_bytes(&mut self, dest: &mut [u8]) {
89        <Self as Rng>::fill_bytes(self, dest)
90    }
91
92    /// Draws a uniformly distributed base-field element.
93    ///
94    /// # Panics
95    ///
96    /// Panics if output generation requires another block after the `u64` block counter is
97    /// exhausted.
98    pub fn draw_basefield(&mut self) -> Felt {
99        loop {
100            let candidate =
101                self.try_next_u64().expect("Eidos random-coin generation is infallible");
102            if let Ok(value) = Felt::new(candidate) {
103                return value;
104            }
105        }
106    }
107
108    /// Draws a uniformly distributed base-field element.
109    ///
110    /// # Panics
111    ///
112    /// Panics under the same condition as [`Self::draw_basefield`].
113    pub fn draw(&mut self) -> Felt {
114        self.draw_basefield()
115    }
116
117    /// Draws a uniformly distributed extension-field element.
118    ///
119    /// # Panics
120    ///
121    /// Panics under the same condition as [`Self::draw_basefield`].
122    pub fn draw_ext_field<E: ExtensionField<Felt>>(&mut self) -> E {
123        E::from_basis_coefficients_fn(|_| self.draw_basefield())
124    }
125
126    /// Mixes four additional field elements into the random-coin state.
127    ///
128    /// The current output-block counter is bound into the new state. Any buffered output is
129    /// discarded, and the block counter is reset to zero.
130    pub fn reseed(&mut self, data: Word) {
131        let input = [
132            self.state[0],
133            self.state[1],
134            self.state[2],
135            self.state[3],
136            Felt::from_u32(self.counter as u32),
137            Felt::from_u32((self.counter >> 32) as u32),
138            data[0],
139            data[1],
140            data[2],
141            data[3],
142        ];
143        self.state = Eidos::hash_elements_in_domain(&input, RANDOM_COIN_STATE);
144        self.output = Word::default();
145        self.counter = 0;
146        self.current = OUTPUT_FELTS;
147    }
148
149    fn next_output_u32(&mut self) -> u32 {
150        loop {
151            if self.current == OUTPUT_FELTS {
152                self.refill_output();
153            }
154
155            let value = self.output[self.current].as_canonical_u64();
156            self.current += 1;
157
158            // Masked Eidos outputs already have uniform low-u32 limbs under the pseudorandom-output
159            // assumption. For a uniform Goldilocks-field output, p - 1 is the sole extra preimage
160            // of zero; removing it leaves exactly 2^32 - 1 preimages for every u32 value.
161            if value != Felt::ORDER - 1 {
162                return value as u32;
163            }
164        }
165    }
166
167    fn refill_output(&mut self) {
168        let counter = self.counter;
169        self.counter = counter.checked_add(1).expect("Eidos random-coin counter exhausted");
170
171        let input = [
172            self.state[0],
173            self.state[1],
174            self.state[2],
175            self.state[3],
176            Felt::from_u32(counter as u32),
177            Felt::from_u32((counter >> 32) as u32),
178        ];
179        self.output = Eidos::hash_elements_in_domain(&input, RANDOM_COIN_OUTPUT);
180        self.current = 0;
181    }
182}
183
184impl FeltRng for EidosRandomCoin {
185    fn draw_element(&mut self) -> Felt {
186        self.draw_basefield()
187    }
188
189    fn draw_word(&mut self) -> Word {
190        Word::new(core::array::from_fn(|_| self.draw_basefield()))
191    }
192}
193
194impl TryRng for EidosRandomCoin {
195    type Error = Infallible;
196
197    fn try_next_u32(&mut self) -> Result<u32, Self::Error> {
198        Ok(self.next_output_u32())
199    }
200
201    fn try_next_u64(&mut self) -> Result<u64, Self::Error> {
202        utils::next_u64_via_u32(self)
203    }
204
205    fn try_fill_bytes(&mut self, dest: &mut [u8]) -> Result<(), Self::Error> {
206        utils::fill_bytes_via_next_word(dest, || self.try_next_u32())
207    }
208}
209
210impl Serializable for EidosRandomCoin {
211    fn write_into<W: ByteWriter>(&self, target: &mut W) {
212        self.state.write_into(target);
213        self.output.write_into(target);
214        target.write_u64(self.counter);
215        target.write_u8(self.current as u8);
216    }
217}
218
219impl Deserializable for EidosRandomCoin {
220    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
221        let state = Word::read_from(source)?;
222        let output = Word::read_from(source)?;
223        let counter = source.read_u64()?;
224        let current = source.read_u8()? as usize;
225        if current > OUTPUT_FELTS {
226            return Err(DeserializationError::InvalidValue(
227                "current output index is out of range".to_string(),
228            ));
229        }
230        if current != OUTPUT_FELTS && counter == 0 {
231            return Err(DeserializationError::InvalidValue(
232                "buffered output requires a generated block".to_string(),
233            ));
234        }
235
236        Ok(Self { state, output, counter, current })
237    }
238}
239
240#[cfg(test)]
241mod tests {
242    use rand::RngExt;
243
244    use super::*;
245    use crate::{ONE, ZERO, field::PrimeCharacteristicRing};
246
247    fn seed() -> Word {
248        Word::new([Felt::ONE, Felt::TWO, Felt::from_u8(3), Felt::from_u8(4)])
249    }
250
251    #[test]
252    fn seed_is_framed_under_the_state_domain() {
253        let coin = EidosRandomCoin::new(seed());
254        let expected = Eidos::hash_elements_in_domain(seed().as_elements(), RANDOM_COIN_STATE);
255
256        assert_eq!(coin.state, expected);
257        assert_eq!(coin.counter, 0);
258        assert_eq!(coin.current, OUTPUT_FELTS);
259    }
260
261    #[test]
262    fn output_matches_the_registered_counter_mode_construction() {
263        let mut coin = EidosRandomCoin::new(seed());
264        let initial_state = coin.state;
265        let input = [
266            initial_state[0],
267            initial_state[1],
268            initial_state[2],
269            initial_state[3],
270            ZERO,
271            ZERO,
272        ];
273        let expected = Eidos::hash_elements_in_domain(&input, RANDOM_COIN_OUTPUT);
274
275        let actual: [u32; OUTPUT_FELTS] = core::array::from_fn(|_| coin.random::<u32>());
276
277        assert_eq!(actual, expected.into_elements().map(|value| value.as_canonical_u64() as u32));
278        assert_eq!(coin.state, initial_state);
279        assert_eq!(coin.output, expected);
280        assert_eq!(coin.counter, 1);
281        assert_eq!(actual, [3_343_138_332, 3_182_666_834, 3_956_264_476, 4_003_292_457]);
282    }
283
284    #[test]
285    fn base_field_sampling_rejects_noncanonical_candidates() {
286        let modulus = Felt::ORDER;
287        let output = Word::new([
288            Felt::from_u32(modulus as u32),
289            Felt::from_u32((modulus >> 32) as u32),
290            Felt::from_u32(42),
291            ZERO,
292        ]);
293        let mut coin = EidosRandomCoin::from_parts(Word::default(), output, 1, 0);
294
295        assert_eq!(coin.draw_basefield(), Felt::from_u64(42));
296        assert_eq!(coin.current, 4);
297    }
298
299    #[test]
300    fn u32_sampling_rejects_the_extra_low_limb_preimage() {
301        let output =
302            Word::new([Felt::new_unchecked(Felt::ORDER - 1), Felt::from_u32(42), ZERO, ZERO]);
303        let mut coin = EidosRandomCoin::from_parts(Word::default(), output, 1, 0);
304
305        assert_eq!(coin.random::<u32>(), 42);
306        assert_eq!(coin.current, 2);
307    }
308
309    #[test]
310    fn reseed_uses_the_complete_state_and_input() {
311        let data =
312            Word::new([Felt::from_u8(5), Felt::from_u8(6), Felt::from_u8(7), Felt::from_u8(8)]);
313        let mut coin = EidosRandomCoin::new(seed());
314        let old_state = coin.state;
315        let _ = coin.random::<u32>();
316        assert_eq!(coin.state, old_state);
317        assert_eq!(coin.counter, 1);
318        coin.reseed(data);
319
320        let input = [
321            old_state[0],
322            old_state[1],
323            old_state[2],
324            old_state[3],
325            Felt::ONE,
326            ZERO,
327            data[0],
328            data[1],
329            data[2],
330            data[3],
331        ];
332        let expected = Eidos::hash_elements_in_domain(&input, RANDOM_COIN_STATE);
333        assert_eq!(coin.state, expected);
334        assert_eq!(coin.output, Word::default());
335        assert_eq!(coin.counter, 0);
336        assert_eq!(coin.current, OUTPUT_FELTS);
337    }
338
339    #[test]
340    fn reseed_binds_the_generated_block_count() {
341        let data =
342            Word::new([Felt::from_u8(5), Felt::from_u8(6), Felt::from_u8(7), Felt::from_u8(8)]);
343        let mut first = EidosRandomCoin::new(seed());
344        let mut second = first;
345
346        let _: [u32; OUTPUT_FELTS] = core::array::from_fn(|_| second.random());
347        first.reseed(data);
348        second.reseed(data);
349
350        assert_ne!(first.state, second.state);
351        assert_ne!(first.random::<[u8; 32]>(), second.random::<[u8; 32]>());
352    }
353
354    #[test]
355    fn reseeded_stream_matches_the_frozen_vector() {
356        let data =
357            Word::new([Felt::from_u8(5), Felt::from_u8(6), Felt::from_u8(7), Felt::from_u8(8)]);
358        let mut coin = EidosRandomCoin::new(seed());
359        let _: [u32; OUTPUT_FELTS] = core::array::from_fn(|_| coin.random());
360        coin.reseed(data);
361
362        let actual: [u32; OUTPUT_FELTS] = core::array::from_fn(|_| coin.random());
363        assert_eq!(actual, [3_145_282_389, 2_211_610_295, 3_232_936_185, 3_064_838_016]);
364    }
365
366    #[test]
367    fn felt_rng_methods_follow_the_base_field_stream() {
368        let mut actual = EidosRandomCoin::new(seed());
369        let mut expected = actual;
370
371        assert_eq!(actual.draw_element(), expected.draw_basefield());
372        assert_eq!(
373            actual.draw_word(),
374            Word::new(core::array::from_fn(|_| expected.draw_basefield()))
375        );
376    }
377
378    #[test]
379    fn serialization_preserves_partially_consumed_output() {
380        let mut coin = EidosRandomCoin::new(seed());
381        let _: [u8; 13] = coin.random();
382
383        let bytes = coin.to_bytes();
384        let decoded = EidosRandomCoin::read_from_bytes(&bytes).unwrap();
385        assert_eq!(decoded, coin);
386
387        let mut first = coin;
388        let mut second = decoded;
389        assert_eq!(first.random::<[u8; 64]>(), second.random::<[u8; 64]>());
390    }
391
392    #[test]
393    fn deserialization_rejects_an_invalid_output_index() {
394        let mut bytes = EidosRandomCoin::new(seed()).to_bytes();
395        *bytes.last_mut().unwrap() = (OUTPUT_FELTS + 1) as u8;
396
397        assert!(EidosRandomCoin::read_from_bytes(&bytes).is_err());
398    }
399
400    #[test]
401    fn deserialization_rejects_buffered_output_without_a_generated_block() {
402        let mut bytes = EidosRandomCoin::new(seed()).to_bytes();
403        *bytes.last_mut().unwrap() = 0;
404
405        assert!(EidosRandomCoin::read_from_bytes(&bytes).is_err());
406    }
407
408    #[test]
409    #[should_panic(expected = "current output index is out of range")]
410    fn from_parts_rejects_an_invalid_output_index() {
411        EidosRandomCoin::from_parts(Word::default(), Word::default(), 0, OUTPUT_FELTS + 1);
412    }
413
414    #[test]
415    #[should_panic(expected = "buffered output requires a generated block")]
416    fn from_parts_rejects_buffered_output_without_a_generated_block() {
417        EidosRandomCoin::from_parts(Word::default(), Word::default(), 0, 0);
418    }
419
420    #[test]
421    fn successive_counters_produce_distinct_output_blocks() {
422        let mut coin = EidosRandomCoin::new(seed());
423        let first: [u32; OUTPUT_FELTS] = core::array::from_fn(|_| coin.random());
424        let second: [u32; OUTPUT_FELTS] = core::array::from_fn(|_| coin.random());
425
426        assert_ne!(first, second);
427        assert_eq!(coin.counter, 2);
428    }
429
430    #[test]
431    fn output_binds_both_counter_limbs() {
432        let state = EidosRandomCoin::new(seed()).state;
433        let mut low = EidosRandomCoin::from_parts(state, Word::default(), 0, OUTPUT_FELTS);
434        let mut high =
435            EidosRandomCoin::from_parts(state, Word::default(), 1u64 << 32, OUTPUT_FELTS);
436
437        assert_ne!(low.random::<[u8; 16]>(), high.random::<[u8; 16]>());
438    }
439
440    #[test]
441    #[should_panic(expected = "Eidos random-coin counter exhausted")]
442    fn counter_exhaustion_is_detected() {
443        let mut coin =
444            EidosRandomCoin::from_parts(Word::default(), Word::default(), u64::MAX, OUTPUT_FELTS);
445        let _ = coin.random::<u32>();
446    }
447
448    #[test]
449    fn different_seeds_produce_different_streams() {
450        let mut first = EidosRandomCoin::new(seed());
451        let mut second = EidosRandomCoin::new(Word::new([ONE; Word::NUM_ELEMENTS]));
452
453        assert_ne!(first.random::<[u8; 64]>(), second.random::<[u8; 64]>());
454    }
455}
miden_crypto/rand/eidos_coin.rs

miden_crypto/rand/
eidos_coin.rs
