winter_crypto/random/
mod.rs

1// Copyright (c) Facebook, Inc. and its affiliates.
2//
3// This source code is licensed under the MIT license found in the
4// LICENSE file in the root directory of this source tree.
5
6use alloc::vec::Vec;
7
8use math::{FieldElement, StarkField};
9
10use crate::{errors::RandomCoinError, ElementHasher, Hasher};
11
12mod default;
13pub use default::DefaultRandomCoin;
14
15// RANDOM COIN TRAIT
16// ================================================================================================
17
18/// Pseudo-random element generator for finite fields.
19///
20/// A random coin can be used to draw elements uniformly at random from the specified base field
21/// or from any extension of the base field.
22///
23/// Internally we use a cryptographic hash function (which is specified via the `Hasher` associated
24/// type), to draw elements from the field.
25pub trait RandomCoin: Sync {
26    /// Base field for random elements which can be generated by this random coin.
27    type BaseField: StarkField;
28
29    /// Hash function which is used by the random coin to generate random field elements.
30    type Hasher: ElementHasher<BaseField = Self::BaseField>;
31
32    // REQUIRED METHODS
33    // --------------------------------------------------------------------------------------------
34
35    /// Returns a new random coin instantiated with the provided `seed`.
36    fn new(seed: &[Self::BaseField]) -> Self;
37
38    /// Reseeds the coin with the specified data by setting the new seed to hash(`seed` || `data`).
39    fn reseed(&mut self, data: <Self::Hasher as Hasher>::Digest);
40
41    /// Computes hash(`seed` || `value`) and returns the number of leading zeros in the resulting
42    /// value if it is interpreted as an integer in big-endian byte order.
43    fn check_leading_zeros(&self, value: u64) -> u32;
44
45    /// Returns the next pseudo-random field element.
46    ///
47    /// # Errors
48    /// Returns an error if a valid field element could not be generated after 1000 calls to the
49    /// PRNG.
50    fn draw<E: FieldElement<BaseField = Self::BaseField>>(&mut self) -> Result<E, RandomCoinError>;
51
52    /// Returns a vector of integers selected from the range [0, domain_size) after it reseeds
53    /// the coin with a nonce.
54    ///
55    /// # Errors
56    /// Returns an error if the specified number of integers could not be generated after 1000
57    /// calls to the PRNG.
58    ///
59    /// # Panics
60    /// Panics if:
61    /// - `domain_size` is not a power of two.
62    /// - `num_values` is greater than or equal to `domain_size`.
63    fn draw_integers(
64        &mut self,
65        num_values: usize,
66        domain_size: usize,
67        nonce: u64,
68    ) -> Result<Vec<usize>, RandomCoinError>;
69}
winter_crypto/random/mod.rs

winter_crypto/random/
mod.rs
