If I recall, we sample the tranche zero assignments in ELVES using a partial run of Durstenfeld's algorithm for the Fisher–Yates shuffle, much like https://docs.rs/rand/latest/src/rand/seq/slice.rs.html#481-510 Or maybe we simplified this?
Internally, Durstenfeld's algorithm uses unbiased sampling aka rejection sampling, but rand::RngExt has some chaos in their rejection sampling, using different methods for different versions or rand, and even different methods for different identical looking calls:
rust-random/rand#1287 (comment)
Daniel Lemire's Fast Random Integer Generation in an Interval (2018) provides afaik the overall fastest method of rejection sampling (Algorithm 5) from similarly sized random numbers. As linked above, rand claimed the adopted Lemire in v0.9, but really rand runs the OpenBSD algorithm 3 from Lemire's paper, which should've the same output as Lemire's Algorithm 5, just slightly different performance.
A real implementation of Lemire exists in the urandom crate, but urandom should be avoided because it seals its Rng trait. We could fork that one file into an extension trait of rand::Rng if one required, but..
What do we even need here? We'll only have 30-1000 cores anyways, before going to parallel relay chains, so that's only 11 bits.
We care firstly about stability here. We care secondarily about simplicity, maybe in multiple languages. We can ignore the speed improvements over naive rejection sampling methods, but they are not the simplest things either.
This is the prefix to Lemire's algorithm that's used repeatedly in rand:
fn sample_mul_shr(seed: &[u8: 32], cores: u16) -> u16 {
let mut b = [0u8; $uhalf::BITS/8];
ChaCha20Rng::from_seed(..).fill_bytes(b);
(($uhalf::from_le_bytes(b) as $ufull) * (cores as $ufull) >> $uhalf::BITS) as u16
}
If $ufull = u256 and $uhalf = u128 then any bias would be negligible in cryptographic terms, but requires puling in u256 from urandom or somewhere, so maybe that's unnecessary complexity.
If $ufull = u128 and $uhalf = u64 then bias only occurs with odds 2^-53, or really even lower. At 1000 validators and 1000 cores that's one biased assignment every 19 billion RC blocks, but we only have like 3 million RC blocks per year. This seems fine, no?
Alternatively, this would've negligible bias but uses a u128 modulo:
fn sample_mod(seed: &[u8: 32], cores: u16) -> u16 {
let mut b = [0u8; 16];
ChaCha20Rng::from_seed(seed).fill_bytes(b);
(u128::from_le_bytes(b) % (core as u128)) as u16
}
Also, Go might use roughly Daniel Lemire's algorithm, would could be a pessimisation & complexity elsewhere if run on u16s directly, and could agree with sample_mul_shr almost all the time if someone just used their regular unbiased sampling, but cause chaos once every several years. If folks care then they could check what implementation exists in their ecosystems, and fill in the gaps.
If I recall, we sample the tranche zero assignments in ELVES using a partial run of Durstenfeld's algorithm for the Fisher–Yates shuffle, much like https://docs.rs/rand/latest/src/rand/seq/slice.rs.html#481-510 Or maybe we simplified this?
Internally, Durstenfeld's algorithm uses unbiased sampling aka rejection sampling, but
rand::RngExthas some chaos in their rejection sampling, using different methods for different versions or rand, and even different methods for different identical looking calls:rust-random/rand#1287 (comment)
Daniel Lemire's Fast Random Integer Generation in an Interval (2018) provides afaik the overall fastest method of rejection sampling (Algorithm 5) from similarly sized random numbers. As linked above, rand claimed the adopted Lemire in v0.9, but really rand runs the OpenBSD algorithm 3 from Lemire's paper, which should've the same output as Lemire's Algorithm 5, just slightly different performance.
A real implementation of Lemire exists in the urandom crate, but urandom should be avoided because it seals its
Rngtrait. We could fork that one file into an extension trait ofrand::Rngif one required, but..What do we even need here? We'll only have 30-1000 cores anyways, before going to parallel relay chains, so that's only 11 bits.
We care firstly about stability here. We care secondarily about simplicity, maybe in multiple languages. We can ignore the speed improvements over naive rejection sampling methods, but they are not the simplest things either.
This is the prefix to Lemire's algorithm that's used repeatedly in rand:
If
$ufull = u256and$uhalf = u128then any bias would be negligible in cryptographic terms, but requires puling inu256from urandom or somewhere, so maybe that's unnecessary complexity.If
$ufull = u128and$uhalf = u64then bias only occurs with odds 2^-53, or really even lower. At 1000 validators and 1000 cores that's one biased assignment every 19 billion RC blocks, but we only have like 3 million RC blocks per year. This seems fine, no?Alternatively, this would've negligible bias but uses a u128 modulo:
Also, Go might use roughly Daniel Lemire's algorithm, would could be a pessimisation & complexity elsewhere if run on u16s directly, and could agree with
sample_mul_shralmost all the time if someone just used their regular unbiased sampling, but cause chaos once every several years. If folks care then they could check what implementation exists in their ecosystems, and fill in the gaps.