Thoughts on choice of algorithm

[bakkot]

There's a variety of modern PRNG algorithms we could choose from, with various tradeoffs around speed, memory, predictability, complexity, miscellaneous statistical properties, and also amenability to other things you might want to do like jumping ahead.

I think the main reasonable candidates are ChaCha, PCG or a variant, and Xoshiro/Xoroshiro. Honorable mention to sfc64 and SplitMix64. Wyrand looks interesting but I think it's too new to be the default choice. Dishonorable mention to Mersenne twisters, which require an excessive amount of state with basically no compensating advantages.

Note that Xoshiro/Xoroshiro is an entire family of PRNGs, so we'd have to choose among them; some of the older ones have (what I regard as) notable weaknesses.

Of these I'd lean towards ChaCha, specifically ChaCha12, which is fast enough for almost all practical purposes, has good statistical properties, is extremely difficult to predict (just as much as ChaCha20, but faster), and as a bonus supports jump-ahead (which is only relevant if we expose that capability, which we probably won't). Detailed thoughts below.

---

I regard being able to generate ~hundreds of megabytes per second on old hardware is probably sufficient, so among algorithms which can achieve that I'm inclined to choose based on other attributes rather than continuing to worry about performance. All mentioned algorithms are capable of that. ChaCha is the slowest, being at least an order of magnitude slower than the others.

Then the most important attribute I'd look for is being statistically well-distributed.

• ChaCha is.
• PCG almost certainly is, though the author of Xorshiro has expressed concerns about some details (if I'm reading it correctly, choosing similar seeds gets you similar outputs)
• Xoshiro (at least some members of the family) have some issues written about e.g. here, here, and here.
• SFC I couldn't find much analysis of, though it passes basic tests.
• SplitMix64 people say is low quality, e.g. here, but I'm not sure why offhand - I do note it has a relatively low period and doesn't repeat outputs for its entire cycle, though when generating 64-bit numbers you need to generate billions of values before the absence of repeats starts to be surprising (more here).

Beyond that I'd optimize for being at least somewhat difficult to predict. People probably shouldn't be using seeded RNGs for cryptography, but it's still a useful property in non-cryptographic applications (e.g. games).

• ChaCha is the only option we can attribute actual unpredictability to.
• PCG has seen a relatively recent attack which recovers the internal state using ~20k hours of compute, though it isn't clear that this technique can be applied to the variant linked above.
• Xoshiro is apparently trivially predictable (though this may not apply to all members of the family).

---

Other bits of context you may find helpful:

• some discussion of various choices in the docs for Rust's rand crate
  • ChaCha12 is currently their default
• Go is considering adopting PCG as the default in Go 2 (instead of their ancient plan-9 derived thing); see discussion here and to a lesser extent here
• SplitMix64 is available in Java's stdlib (as SplittableRandom)
• discussion of PCG on the numpy tracker (OP vigna is the author of Xoshiro, responses by imneme are from the author of PCG)
  • in particular this comment from a numpy maintainer
• as you may have noticed there's a great deal of debate between the authors of PCG and Xoshiro; I've left most of it out but you can find the main critique of PCG here and the main critiques of Xoshiro here.
  • see also this response to the critique of PCG.
• this (somewhat dated) comparison of how some options hold up against standard tests - note that this does not include more recent members of the Xoshiro family
  • commentary on the blog, particularly the comments, is worth going through as well to get a sense of some of the pitfalls when interpreting results of analysis like this

[tabatkins]

I haven't walked thru your references yet, but this seems like incredibly useful research. Thank you so much!

[Artoria2e5]

Go math/rand/v2 (https://pkg.go.dev/math/rand/v2) ended up settling with ChaCha8 as the default; it still has PCG as an option. golang/go#61716 is the discussion, I believe. The argument is that it makes misuse-as-cryptographic-randomness less of a big arrow in the knee; I doubt that applies here given we are outputting a number.

(Although getting not just [0,1) numbers out of the bag seems useful too: maybe someone wants a well-implemented dice roll. Tangentials, tangentials...)

[bakkot]

More overview of Go's implementation here.