miden_crypto/rand/
eidos_coin.rs

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

miden_crypto/rand/
eidos_coin.rs
