What applications require unpredictability where you wouldn't go full csprng?
- Statistics,
- Deep Learning,
- Monte-Carlo simulation (finance, reinforcement learning, game AI, raytracing).
- Fuzzing
- Load balancing
- Peer selection (if non adversarial, otherwise use a CSPRNG)
Also non-determinism of CSPRNG (and floating points) would a huge issue for debugging machine learning models:
- https://www.twosigma.com/insights/a-workaround-for-non-deter...
- https://github.com/tensorflow/tensorflow/issues/3103
- https://discuss.pytorch.org/t/deterministic-non-deterministi...
- https://github.com/tensorflow/tensorflow/issues/2732
Chacha8 has a throughput of 2GB/s and xoshiro256++ has a throughput of 8GB/s
For Monte-Carlo, the RNG is definitely the bottleneck. For load balancing of short tasks the RNG is the bottleneck.
You can eek out another 10% or so if you dial it back to the recommendations of the "too much crypto" paper: 9x AES rounds (versus 10).
What is questionable is the "somewhat secure" argument. Either you don't want adversaries to predict your numbers and you should use a good CSPRNG, or you don't care and predictability is not a property that matters.
As for reproducibility, all PRNGs give a reproducible sequence if you know the internal state, including the secure ones. You have to mix in a source of entropy to make them non-deterministic. The predictability we are considering here is when the attacker doesn't have access to the internal state.
What makes PCG attractive for microcontrollers is really that it's of known good quality, its implementation is very small and very simple, and it ends up generating efficient code for 32-bit processors (i.e., ARM Cortex-Ms). That is not, and can not ever be, true for something like a 128-bit shift register. PCG is great for just tossing in when I'm working on a platform that has no built-in library rand() function, or where it's busted, or whether I don't want to bother figure out if/how badly it's busted. (With how easy PCG is to use, that last one covers every embedded platform ever....)
PCG is not the best RNG out there: it's not the highest quality, it's not the fastest, it's not the least predictable, it's not the strongest theoretically. (It isn't the smallest, either, but it's quite small and the smaller RNGs I know of are either code-golfed, which doesn't count, or truly garbage.) But it is a nice equilibrium between all of those things. And did I mention it's simple? Simple is really, really nice to have :)
I'd suspect the majority of random numbers generated in the world don't need crypto, they need speed. The world's supercomputers are not doing crpyto, they're doing simulations. Most people are not doing crypto most of the time - and when they're gaming in any manner, no need to pay csprng tax.
The only place one should use a csprng is for adversarial situations.
Use the right tool for the job, correct?
There is a time and place for non-CS rngs, and it is in randomized methods whos correctness/results does not rely on the RNG.
[1] "Pattern" section here: http://builder.openhmd.net/blender-hmd-viewport-temp/render/...
http://extremelearning.com.au/unreasonable-effectiveness-of-... (yes, no HTTPS, but incredibly illustrative)
Discussed in 2018: https://news.ycombinator.com/item?id=17873284
A good non-cryptographic random number generator like xoshiro256 can generate at 4 times the speed of a chacha20 random number generator. Depending on how many models you need to compute and the desired precision of those models and how many random samples you need per model, this can easily be the difference between hours and days, or days and weeks.
Whenever a post on PRNGs comes up, I'm reminded of this post from a while back about Chrome:
https://medium.com/@betable/tifu-by-using-math-random-f1c308...
Near the end is a Monte Carlo estimate of Pi using 10^10 iterations:
Chrome 3.1418697000 0.0002770464 1301.903s
Firefox 3.1416998084 0.0001071548 249.595s
Safari 3.1416692728 0.0000766192 7172.207s
That's around 30x slower than a decent version of PCG, which also has a lot of variants to cover a lot of use cases.
For MC path tracing (graphics) this is at least an order of magnitude too slow.
Even fairly trivial scenes can require over 20 random floats per sample and more complex scenes over 100. And you want to actually use those random numbers for calculating reflections, intersections etc. In the renderer I worked on the PRNG typically took at most 10% of total CPU time.
So assuming the above those 4GB/s would translate into less than 5k samples/sec, which would be considered quite slow.
Just to refresh my memory I just ran a quick test with a fairly simple scene. There's 6 samples for the camera, at least 3 per path vertex up (depth 32) and another 2 per light (8 in this scene). There might be some more I'm forgetting but lets use that a lower bound. For this scene then that means 6 + 3 * 32 + 2 * 8 = 118 random numbers per sample. On a single core I got 14.04kS/s, so that works out to at least 1.6M random numbers per second.
And this renderer was focusing more on physics and fidelity rather than speed. For animations and similar you'd need a renderer that's at least an order of magnitude faster than the one I worked on.
For reading further you could try PBRT[1]. It's a great book but not free. Luckily enough though the free chapter is about sampling and reconstruction so you can get a feel from that what is needed.
[1]: https://pbrt.org/
I also recall that we tried MT but found a quite noticeable impact on speed compared to what we had, and on the PGC performance page MT is listed in the tens of GB/s. Perhaps our implementation was considerably worse though, I can't recall us testing it alone like that.
As I mentioned though, that renderer was more about physics and fidelity. Typical render times for even a preview would be a minute, for final single-frame stills tens of hours to several days on a single computer was common.
For animations you don't have that kind of time, so you need a orders of magnitude more samples/sec.
Sibling comments are completely correct. Graphics simulations often require quasirandom sequences; the particular sequence is not important, but any correlations in the sequence will be visible in the output as artifacts, so we want a decorrelated sequence.
If this is not enough of a real-world example for you, then Monte Carlo methods also show up in weather modeling, financial planning, and election forecasting. In those predictive systems, there is extreme uncertainty and dependence on initial conditions, which we model with quasirandom sequences and seed numbers respectively. By running many simulations with different random sequences and then examining all of the results statistically, we can get good estimates of future behavior.
Edit: Oh, you're not in good faith. Okay, cool story. Best of luck with whatever imaginary idea of "unpredictability" you're trying to define, but you might want to return to actual maths at some point.
Every other thing in the PCG website and in this thread attempts to be similar to random (with varying degrees of success). No one here is trying to intentionally be different from random.
> Sibling comments are completely correct.
No sibling comment says anything about quasirandom. The sibiling comment mentioning graphics (by Karliss) actually sort of disagrees with you, and says that we want stuff to be as close to random as possible for graphics so that players don't see patterns. Of course there can be multiple types of graphics situations, some where quasirandom would be useful (the blog you linked), some where a real random approximation would be useful (Karliss's situation).
> Wouldn't the second category be more less CSPRNG?
The website says PCG is "Challenging" to predict and ChaCha20 is "Secure". So I think this means that PCG isn't a CSPRNG, but still is harder to predict than Mersenne Twister.
But is this useful at all? I don't know. This thread started by andreareina asking that exact question: "What applications require unpredictability where you wouldn't go full csprng?" People immediately then misunderstood the question because they misunderstood how the word unpredictability is being used.
A player not being able to mentally predict enemies and not seeing visible patterns sounds like it might fall more under the website's definition of "Statistical Quality".
For example you can increase the quality of a RNG sequence r(n) by adding a multiplicative hash, r'(n) = A r(n) for some good constant A. A consumer treating r' as a blackbox expects B r'(n) = AB r(n) to be a good random sequence, but if B is close to the inverse of A, the constant AB may no longer be "good".
There is no need to cryptographic strength, which is costly, and pseudo-randomness is enough and much cheaper.