Struct winter_crypto::RandomCoin
source · pub struct RandomCoin<B, H>where
B: StarkField,
H: Hasher,{ /* private fields */ }
Expand description
Pseudo-random element generator for finite fields.
A random coin can be used to draws elements uniformly at random from the specified 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
// instantiate a random coin using BLAKE3 as the hash function
let mut coin = RandomCoin::<BaseElement, Blake3_256<BaseElement>>::new(&[1, 2, 3, 4]);
// 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 coin1 = RandomCoin::<BaseElement, Blake3_256<BaseElement>>::new(&[1, 2, 3, 4]);
let mut coin2 = RandomCoin::<BaseElement, Blake3_256<BaseElement>>::new(&[1, 2, 3, 4]);
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 = RandomCoin::<BaseElement, Blake3_256<BaseElement>>::new(&[1, 2, 3, 4]);
let mut coin2 = RandomCoin::<BaseElement, Blake3_256<BaseElement>>::new(&[2, 3, 4, 5]);
let e1 = coin1.draw::<BaseElement>().unwrap();;
let e2 = coin2.draw::<BaseElement>().unwrap();;
assert_ne!(e1, e2);
Implementations
sourceimpl<B: StarkField, H: Hasher> RandomCoin<B, H>
impl<B: StarkField, H: Hasher> RandomCoin<B, H>
sourcepub fn reseed(&mut self, data: H::Digest)
pub fn reseed(&mut self, data: H::Digest)
Reseeds the coin with the specified data by setting the new seed to hash(seed
|| data
).
Examples
let mut coin1 = RandomCoin::<BaseElement, Blake3_256<BaseElement>>::new(&[1, 2, 3, 4]);
let mut coin2 = RandomCoin::<BaseElement, Blake3_256<BaseElement>>::new(&[1, 2, 3, 4]);
// 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);
sourcepub fn reseed_with_int(&mut self, value: u64)
pub 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
let mut coin1 = RandomCoin::<BaseElement, Blake3_256<BaseElement>>::new(&[1, 2, 3, 4]);
let mut coin2 = RandomCoin::<BaseElement, Blake3_256<BaseElement>>::new(&[1, 2, 3, 4]);
// 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);
sourcepub fn leading_zeros(&self) -> u32
pub 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
let mut coin = RandomCoin::<BaseElement, Blake3_256<BaseElement>>::new(&[1, 2, 3, 4]);
let mut value = 0;
while coin.check_leading_zeros(value) < 2 {
value += 1;
}
coin.reseed_with_int(value);
assert!(coin.leading_zeros() >= 2);
sourcepub fn check_leading_zeros(&self, value: u64) -> u32
pub 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.
sourcepub fn draw<E>(&mut self) -> Result<E, RandomCoinError>where
E: FieldElement<BaseField = B>,
pub fn draw<E>(&mut self) -> Result<E, RandomCoinError>where
E: FieldElement<BaseField = B>,
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.
sourcepub fn draw_pair<E>(&mut self) -> Result<(E, E), RandomCoinError>where
E: FieldElement<BaseField = B>,
pub fn draw_pair<E>(&mut self) -> Result<(E, E), RandomCoinError>where
E: FieldElement<BaseField = B>,
Returns the next pair of pseudo-random field elements.
Errors
Returns an error if any of the field elements could not be generated after 100 calls to the PRNG;
sourcepub fn draw_triple<E>(&mut self) -> Result<(E, E, E), RandomCoinError>where
E: FieldElement<BaseField = B>,
pub fn draw_triple<E>(&mut self) -> Result<(E, E, E), RandomCoinError>where
E: FieldElement<BaseField = B>,
Returns the next triplet of pseudo-random field elements.
Errors
Returns an error if any of the field elements could not be generated after 100 calls to the PRNG;
sourcepub fn draw_integers(
&mut self,
num_values: usize,
domain_size: usize
) -> Result<Vec<usize>, RandomCoinError>
pub 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
let mut coin = RandomCoin::<BaseElement, Blake3_256<BaseElement>>::new(&[1, 2, 3, 4]);
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));
}