Struct winter_crypto::DefaultRandomCoin
source · pub struct DefaultRandomCoin<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: StarkField, H: ElementHasher<BaseField = B>> RandomCoin for DefaultRandomCoin<H>
impl<B: StarkField, H: ElementHasher<BaseField = B>> RandomCoin for DefaultRandomCoin<H>
source§fn new(seed: &[Self::BaseField]) -> Self
fn new(seed: &[Self::BaseField]) -> Self
Returns a new random coin instantiated with the provided seed
.
source§fn reseed(&mut self, data: H::Digest)
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);
source§fn reseed_with_int(&mut self, value: u64)
fn reseed_with_int(&mut self, value: u64)
Reseeds the coin with the specified value by setting the new seed to hash(seed
||
value
).
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_with_int(42);
let e1 = coin1.draw::<BaseElement>().unwrap();;
let e2 = coin2.draw::<BaseElement>().unwrap();;
assert_ne!(e1, e2);
source§fn leading_zeros(&self) -> u32
fn leading_zeros(&self) -> u32
Returns the number of leading zeros in the seed if it is interpreted as an integer in big-endian byte order.
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 mut value = 0;
while coin.check_leading_zeros(value) < 2 {
value += 1;
}
coin.reseed_with_int(value);
assert!(coin.leading_zeros() >= 2);
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: FieldElement>(&mut self) -> Result<E, RandomCoinError>
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.
source§fn draw_integers(
&mut self,
num_values: usize,
domain_size: usize
) -> Result<Vec<usize>, RandomCoinError>
fn draw_integers( &mut self, num_values: usize, domain_size: usize ) -> Result<Vec<usize>, RandomCoinError>
Returns a vector of unique integers selected from the range [0, domain_size).
Errors
Returns an error if the specified number of unique 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 values = coin.draw_integers(num_values, domain_size).unwrap();
assert_eq!(num_values, values.len());
let mut value_set = HashSet::new();
for value in values {
assert!(value < domain_size);
assert!(value_set.insert(value));
}