Tracking Issue for deterministic random number generation

[joboet]

Feature gate: #![feature(deterministic_random_chacha8)]

This is a tracking issue for DeterministicRandomSource, a deterministic random number generation that will always generate the same values for a given seed.

Public API

// core::random;

pub struct DeterministicRandomSource { .. }

impl DeterministicRandomSource {
    pub const fn from_seed(seed: [u8; 32]) -> DeterministicRandomSource;
    pub const fn seed(&self) -> &[u8; 32];
}

impl RandomSource for DeterministicRandomSource { .. }
impl Random for DeterministicRandomSource { .. }

Steps / History

• ACP: Simple seedable insecure random number generation, stable across Rust versions libs-team#394
• Implementation: #...
• Final comment period (FCP)¹
• Stabilization PR

Unresolved Questions

• Is ChaCha8 the right random number generator to use? Given that this RNG should not be used for cryptographic purposes, ChaCha8 might be a bit overkill.
• Does the seed function make sense?

Footnotes

1. https://std-dev-guide.rust-lang.org/feature-lifecycle/stabilization.html ↩

[Noratrieb]

Given that this RNG should not be used for cryptographic purposes, ChaCha8 might be a bit overkill.

https://go.dev/blog/randv2 might be relevant here

[juntyr]

If a counter-based PRNG is chosen instead, exposing the current state (in addition or instead of?) the original seed would be valuable

[juntyr]

Could the source also support seeding from a u64 (e.g. adopting how rand expands the seed), so that there is one well-supported approaches for this very common use case?

[hanna-kruppe]

Is ChaCha8 the right random number generator to use? Given that this RNG should not be used for cryptographic purposes, ChaCha8 might be a bit overkill.

Since it's always supposed to give the same output forever after stabilization, it seems prudent to choose an algorithm that can be expected to last for a decade or more without regrets. It would be awkward to deprecate this part of std because it later turns out to have some flaws that can't be fixed without breaking reproducibility (see the Go math/rand/v2 story). A well-established cipher that's considered secure today almost certainly won't turn out have major flaws as a source of statistical randomness: any feasible way to distinguish the output from random is a big deal for cryptanalysis, and even an "academic break" (say, key recovery in 2^100 time) doesn't necessarily mean anything about the suitability for Monte Carlo simulations. The same can't be said about the myriad of non-cryptographic designs, where it's often only a matter of time and eyeballs until serious flaws are discovered.

For example, AES (Rijndael) is from 1998 and still going strong while the non-cryptographic MT19937 from 1997 was very popular for many years but is now considered flawed and obsolete. ChaCha is from 2008. Several years later, people were still publishing new non-crypto RNGs that fail TestU01, a suite of statistical tests dating to 2007--2009.

[dhardy]

Forgive me, but why re-invent this functionality in the std lib?

Provision of an OS-getrandom API makes sense since much of the code is in std already. Provision of an alternative to rand::rng (aka ThreadRng) may also make sense: it's a single API which may make use of the OS's random source to varying (platform-dependant) extent.

Yes, I get it: rand is complicated, so it's tempting to start fresh. I fear you'd eventually end up in a similar place however, after multiple iterations of additional frequently-requested functionality.

PRNGs

There is no particular best PRNG. ChaCha8 should be fine for this use-case, but it's fundamentally a block-based RNG whereas a word-based PRNG like Xoshiro or PCG will be substantially faster for many use-cases. Since this is explicitly about a user-seeded PRNG with user-managed-state there is no good reason not to let the user choose the algorithm too (from some set of options).

The name DeterministicRandomSource does not imply portable results. rand::rngs::SmallRng is deterministic but not portable for example (different 32-bit and 64-bit impls). If you only want one generator with portable results, name it PortableRandomSource or maybe ReproducibleRandomSource to avoid the confusion.

Random trait

The proposed trait Random appears to be the equivalent of StandardUniform (possibly restricted to primitive integer types). This is only one form of random-value-generation, and while it's mostly easy to support (there may be questions around precision for FP types), it's not that useful on its own.

Uniform ranged sampling is the obvious other application. There are quite a few algorithms for this. If you want reproducible outputs, pick one of these and stick with it (or keep the impl unstable until the algorithm is fixed). Now implement for f32, Duration, char, simd::i16x8 etc.

On the topic of reproducibility, we recently removed support for sampling isize and usize in rand due to multiple reports of it being a portability hazard. Exception: we do support usize sampling for fixed ranges but use 32-bit sampling wherever possible.

Additional scope?

There are several obvious possibilities for scope creep:

• shuffling slices
• choosing one or multiple elements of slices
• choosing one or multiple elements of iterators
• sampling random alphanumeric values
• sampling a bool with a defined probability or ratio
• weighted sampling of sequences

This is most of what we elected to keep in rand (vs rand_distr). If some alternative to ThreadRng (now rand::rng()) were to be implemented within std, then rand could be shrunk down to almost just this (we'd no longer need the getrandom dependency, we could merge a simpler RNG trait from rand_core).

Proposal

What I'd propose therefore is:

• Stabilise trait RandomSource and DefaultRandomSource from Tracking Issue for secure random data generation in std #130703. These serve cryptography applications and other needs for a random-byte-generator Edit: this trait may not be the best design; see discussion below
• We drop ThreadRng along with rand::rngs::OsRng, ReseedingRng and likely StdRng, thus removing everything "cryptographic" from rand
• We merge a simpler RngCore trait into rand, possibly just with next_u32 and next_u64, and remove the rand_core dependency
• We implement rand::rngs::RngCore for all RandomSource and make rand::rng a wrapper over DefaultRandomSource
• We also provide deterministic and portable PRNGs in rand::rngs
• Publish a new rand version with significantly less code and dependencies

I believe this would reduce many people's issues with rand, namely that it's quite large and complex. (Not completely though; there would still be significant code involved in impls for Uniform etc.)

By itself, this wouldn't remove all usages of unsafe in rand; that is another issue which I believe is addressable (though possibly not without performance impact), if people care sufficiently about usage of unsafe outside std.

[hanna-kruppe]

Under your proposal, why even have the RandomSource trait at all? It wouldn't even work very well as a vocabulary type if rand::RngCore would still exist and there's a impl<T: RandomSource> rand::RngCore for T. That blanket impl rules out directly implementing both traits for any given generator, and many generators will want to implement next_{u32,u64} directly instead of the detour through RandomSource::fill_bytes.

And if std drops the trait, then DefaultRandomSource could be simplified down to std::random::fill_bytes(). That's also the primary interface of the getrandom crate, modulo fallibility.

---

I can see how this would remove some of the most tricky parts of rand's internals/dependency tree. But it would not address the stated motivation of rust-lang/libs-team#394 - practically every use of randomness still requires a third-party crate, or manually re-implementing non-trivial parts of such a crate (likely in worse ways). Even getting a uniformly random usize from a byte stream has subtle portability/reproducibility pitfalls, as you point out. There is a risk of slippery-sloping the standard library into re-inventing all of rand in the limit. But the other extreme also has a risk: if you give people who want to limit themselves to the standard library just a raw byte stream, then many will implement basic operations like "pick an element from a slice" roughly like this:

let mut buf = [0; size_of::<usize>()];
DefaultRandomSouce::default().fill_bytes(&mut buf);
// ^ or a hand-rolled seedable PRNG of choice
let r = usize::from_ne_bytes(buf);
let elem = slice[r % slice.len()];

... and that's a worse outcome than std providing std::random::range(0..slice.len()) or something at roughly that level of abstraction.

[dhardy]

Under your proposal, why even have the RandomSource trait at all? It wouldn't even work very well as a vocabulary type if rand::RngCore would still exist and there's a impl<T: RandomSource> rand::RngCore for T. That blanket impl rules out directly implementing both traits for any given generator, and many generators will want to implement next_{u32,u64} directly instead of the detour through RandomSource::fill_bytes.

This is a good point, but I think it's workable (though there is possibly reason to keep RngCore::fill_bytes too).

For block-based PRNGs like ChaCha as well as for OsRng / DefaultRandomSource (whether or not this uses a local cache), I see no reason to implement next_{u32,u64} directly.

For word-based PRNGs, it's questionable whether these should implement the RandomSource trait. Firstly, is there any implication regarding security of the output as there is with rand::CryptoRng? Second, the only reasons to use a word-based PRNG are simplicity of implementation, small state size, and performance of word-sized outputs. I can think of some cases where it might be useful having a fill_bytes type interface on such a PRNG (we use this in rand's SIMD implementations, and it might be used to seed another PRNG, though one needs to be careful to avoid correlations there), but for the most part I would expect a block-based PRNG to be a better choice when significant usage of byte-output is required. Thus, I think it is reasonable for word-based PRNGs not to implement RandomSource.

But it would not address the stated motivation of rust-lang/libs-team#394 - practically every use of randomness still requires a third-party crate, or manually re-implementing non-trivial parts of such a crate (likely in worse ways).

This goes for some other areas too, e.g. std::time can only tell you relative time, not local time, because that's complicated (though I suspect most uses of chrono will only use a small subset of its functionality like Local and NaiveDateTime). Similarly, I think an interface for seeding a randomised hash state or cryptographic key fits well within std, but that including machinery for generating random values is a slippery slope.

But the other extreme also has a risk: if you give people who want to limit themselves to the standard library just a raw byte stream, then many will implement basic operations like "pick an element from a slice" roughly like this:

I mean, we can tell them they shouldn't do that. But if you do want such functionality, then:

// surely it's better to support this:
let elt = slice.choose(&mut rng);
// instead of expecting people to write this:
let elt = slice[rng.random_range(..slice.len())];

? (This doesn't remove the need for fn random_range but is an obvious extension.)

And even if the above functionality is in std, I still don't see much need for trait Random, except possibly as a helper to implement the above. Random is easy to implement but most of the time not what people actually want to use (except possibly fuzzing, but arguably that might also want a different API).

[newpavlov]

I believe only the following things should be in std/core:

• Secure "system" source.
• Insecure "system" source used for stuff like seeding HashMaps and non-security-critical PRNGs.
• ThreadRng, i.e. cryptographically strong and reasonably fast RNG periodically reseeded from the secure "system" source. It's implementation could benefit from the unstable #[thread_local] feature.
• RNG traits to generalize over the previous items.

The "system" sources should allow registration of an alternative implementation similarly to #[global_allocator]. The latter 3 items can be considered "optional", but I think it's reasonable to have them as part of std. It also may be worth to add a weaker version of ThreadRng (i.e. SmallRng periodically reseeded from the "insecure" source), but its benefits are less clear.

Everything else should be just part of a third-party crate like rand.