1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

// Copyright (c) Facebook, Inc. and its affiliates.
//
// This source code is licensed under the MIT license found in the
// LICENSE file in the root directory of this source tree.

use alloc::vec::Vec;

use math::{FieldElement, StarkField};

use crate::{errors::RandomCoinError, ElementHasher, Hasher};

mod default;
pub use default::DefaultRandomCoin;

// RANDOM COIN TRAIT
// ================================================================================================

/// Pseudo-random element generator for finite fields.
///
/// A random coin can be used to draw elements uniformly at random from the specified base field
/// or from any extension of the base field.
///
/// Internally we use a cryptographic hash function (which is specified via the `Hasher` associated
/// type), to draw elements from the field.
pub trait RandomCoin: Sync {
    /// Base field for random elements which can be generated by this random coin.
    type BaseField: StarkField;

    /// Hash function which is used by the random coin to generate random field elements.
    type Hasher: ElementHasher<BaseField = Self::BaseField>;

    // REQUIRED METHODS
    // --------------------------------------------------------------------------------------------

    /// Returns a new random coin instantiated with the provided `seed`.
    fn new(seed: &[Self::BaseField]) -> Self;

    /// Reseeds the coin with the specified data by setting the new seed to hash(`seed` || `data`).
    fn reseed(&mut self, data: <Self::Hasher as Hasher>::Digest);

    /// Computes hash(`seed` || `value`) and returns the number of leading zeros in the resulting
    /// value if it is interpreted as an integer in big-endian byte order.
    fn check_leading_zeros(&self, value: u64) -> u32;

    /// Returns the next pseudo-random field element.
    ///
    /// # Errors
    /// Returns an error if a valid field element could not be generated after 1000 calls to the
    /// PRNG.
    fn draw<E: FieldElement<BaseField = Self::BaseField>>(&mut self) -> Result<E, RandomCoinError>;

    /// Returns a vector of integers selected from the range [0, domain_size) after it reseeds
    /// the coin with a nonce.
    ///
    /// # Errors
    /// Returns an error if the specified number of integers could not be generated after 1000
    /// calls to the PRNG.
    ///
    /// # Panics
    /// Panics if:
    /// - `domain_size` is not a power of two.
    /// - `num_values` is greater than or equal to `domain_size`.
    fn draw_integers(
        &mut self,
        num_values: usize,
        domain_size: usize,
        nonce: u64,
    ) -> Result<Vec<usize>, RandomCoinError>;
}