pub struct WinterRandomCoin<H>where
H: ElementHasher,{ /* private fields */ }
Expand description
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 acounter
. At instantiation time, theseed
is set to a hash of the provided bytes, and thecounter
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§
source§impl<B, H> RandomCoin for DefaultRandomCoin<H>where
B: StarkField,
H: ElementHasher<BaseField = B>,
impl<B, H> RandomCoin for DefaultRandomCoin<H>where
B: StarkField,
H: ElementHasher<BaseField = B>,
source§fn new(
seed: &[<DefaultRandomCoin<H> as RandomCoin>::BaseField],
) -> DefaultRandomCoin<H>
fn new( seed: &[<DefaultRandomCoin<H> as RandomCoin>::BaseField], ) -> DefaultRandomCoin<H>
Returns a new random coin instantiated with the provided seed
.
source§fn reseed(&mut self, data: <H as Hasher>::Digest)
fn reseed(&mut self, data: <H as Hasher>::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);
source§fn check_leading_zeros(&self, value: u64) -> u32
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.
source§fn draw<E>(&mut self) -> Result<E, RandomCoinError>where
E: FieldElement,
fn draw<E>(&mut self) -> Result<E, RandomCoinError>where
E: FieldElement,
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.
source§fn draw_integers(
&mut self,
num_values: usize,
domain_size: usize,
nonce: u64,
) -> Result<Vec<usize>, RandomCoinError>
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 todomain_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);
}