Struct winter_crypto::DefaultRandomCoin

pub struct DefaultRandomCoin<H: ElementHasher> { /* private fields */ }

Pseudo-random element generator for finite fields, which is a default implementation of the RandomCoin trait.

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 H type parameter), to draw elements from the field. The coin works roughly as follows:

• The internal state of the coin consists of a seed and a counter. At instantiation time, the seed is set to a hash of the provided bytes, and the counter is set to 0.
• To draw the next element, we increment the counter and compute hash(seed || counter). If the resulting value is a valid field element, we return the result; otherwise we try again until a valid element is found or the number of allowed tries is exceeded.
• We can also re-seed the coin with a new value. During the reseeding procedure, the seed is set to hash(old_seed || new_seed), and the counter is reset to 0.

Examples

// initial elements for seeding the random coin
let seed = &[BaseElement::new(1), BaseElement::new(2), BaseElement::new(3), BaseElement::new(4)];

// instantiate a random coin using BLAKE3 as the hash function
let mut coin = DefaultRandomCoin::<Blake3_256<BaseElement>>::new(seed);

// should draw different elements each time
let e1 = coin.draw::<BaseElement>().unwrap();;
let e2 = coin.draw::<BaseElement>().unwrap();;
assert_ne!(e1, e2);

let e3 = coin.draw::<BaseElement>().unwrap();;
assert_ne!(e1, e3);
assert_ne!(e2, e3);

// should draw same elements for the same seed
let mut coin2 = DefaultRandomCoin::<Blake3_256<BaseElement>>::new(seed);
let mut coin1 = DefaultRandomCoin::<Blake3_256<BaseElement>>::new(seed);
let e1 = coin1.draw::<BaseElement>().unwrap();;
let e2 = coin2.draw::<BaseElement>().unwrap();;
assert_eq!(e1, e2);

// should draw different elements based on seed
let mut coin1 = DefaultRandomCoin::<Blake3_256<BaseElement>>::new(seed);
let seed = &[BaseElement::new(2), BaseElement::new(3), BaseElement::new(4), BaseElement::new(5)];
let mut coin2 = DefaultRandomCoin::<Blake3_256<BaseElement>>::new(seed);
let e1 = coin1.draw::<BaseElement>().unwrap();;
let e2 = coin2.draw::<BaseElement>().unwrap();;
assert_ne!(e1, e2);

Trait Implementations

impl<B: StarkField, H: ElementHasher<BaseField = B>> RandomCoin for DefaultRandomCoin<H>

fn new(seed: &[Self::BaseField]) -> Self

Returns a new random coin instantiated with the provided seed.

fn reseed(&mut self, data: H::Digest)

Reseeds the coin with the specified data by setting the new seed to hash(seed || data).

Examples

// initial elements for seeding the random coin
let seed = &[BaseElement::new(1), BaseElement::new(2), BaseElement::new(3), BaseElement::new(4)];

let mut coin1 = DefaultRandomCoin::<Blake3_256<BaseElement>>::new(seed);
let mut coin2 = DefaultRandomCoin::<Blake3_256<BaseElement>>::new(seed);

// should draw the same element form both coins
let e1 = coin1.draw::<BaseElement>().unwrap();
let e2 = coin2.draw::<BaseElement>().unwrap();;
assert_eq!(e1, e2);

// after reseeding should draw different elements
coin2.reseed(Blake3_256::<BaseElement>::hash(&[2, 3, 4, 5]));
let e1 = coin1.draw::<BaseElement>().unwrap();;
let e2 = coin2.draw::<BaseElement>().unwrap();;
assert_ne!(e1, e2);

fn check_leading_zeros(&self, value: u64) -> u32

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 draw<E: FieldElement>(&mut self) -> Result<E, RandomCoinError>

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_integers( &mut self, num_values: usize, domain_size: usize, nonce: u64 ) -> Result<Vec<usize>, RandomCoinError>

Returns a vector of integers selected from the range [0, domain_size) after reseeding the PRNG with the specified nonce by setting the new seed to hash(seed || 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.

Examples

// initial elements for seeding the random coin
let seed = &[BaseElement::new(1), BaseElement::new(2), BaseElement::new(3), BaseElement::new(4)];

let mut coin = DefaultRandomCoin::<Blake3_256<BaseElement>>::new(seed);

let num_values = 20;
let domain_size = 64;
let nonce = 0;
let values = coin.draw_integers(num_values, domain_size, nonce).unwrap();

assert_eq!(num_values, values.len());

for value in values {
    assert!(value < domain_size);
}

type BaseField = B

Base field for random elements which can be generated by this random coin.

type Hasher = H

Hash function which is used by the random coin to generate random field elements.