6 ms·
PCG: a family of better random number generators
- lucb1e 8y agoThat table seems as if PCG has no downsides, and yet I've never heard of it and we're not all using it. The paper is from 2014, which is fairly recent as far as these things go I suppose. I'm not well-versed enough in each topic they mention in the table, but it's definitely questionable to equate CSPRNGs with PCG and label them both green under "prediction difficulty". Without saying so outright, on /predictability.html it is made clear that this is not a CSPRNG. The columns are not very well explained, either. I would assume that anything whose source is not a TRNG would have "Reproducible Results", yet arc4random supposedly does not have that. How an algorithm can be non-deterministic given the same inputs, I would be very curious to learn, as it seems like the holy grail of CSPRNGs. I'm a little skeptical, but it looks like something to keep an eye on. They claim to have both simpler code, faster code and better randomness than the standard Mersenne Twister (which was my go-to RNG for non-cryptographic purposes). Edit: It seems the page hardly changed since 2015. Maybe add (2015) to the title? Source: https://web.archive.org/web/20151030045740/http://www.pcg-random.org/ https://web.archive.org/web/20151030045740/http://www.pcg-ra...
- badrabbit 8y agoI must agree. They don't make it clear that it shouldn't be used for secure computing(cryptography) purposes. They compare chacha20 and mersene twister in the same table,isn't it obvious that chacha20 isn't ideal for non-crypto use?
- clarry 8y agoChacha20 is plenty good for most non-crypto uses.
- __s 8y agoI recently switched from Mersenne to PCG, was considering xoroshiro. Use case is a card game. Mersenne was weighing down the AI because the AI does a lot of cloning so my need was a minimal amount of intermediate state
- jerf 8y agoIf that's your use case, pregenerate more of the raw stream and use that, then you can avoid the RNG running at all a lot more. What you do to that stream may vary depending on path, but the stream of random numbers is, ahem, constant.
- pletnes 8y agoEven if it’s 100 timed better than Mersenne Twister, a lot of people just throw MT at the problem and it’s solved. Why research new algorithms when old ones are good enough in your use case? Usage is not proof of quality.
- myWindoonn 8y agoDisclaimer: My pet programming language has PCG as one of its available RNGs. It also has xorshift. PCG doesn't have many downsides, and indeed is slowly but surely outcompeting the other hashes in the fast general RNG niche, like MT, xoroshiro, and xorshift. Your "label them both green" complaint is misleading. The descriptive word "Challenging" is used to describe PCG, while "Secure" is used to describe the CSPRNGs. In this context, it's pretty easy to understand that the "Secure" in the description is the same as the "Secure" in "CSPRNG". The author admits in the PCG paper [0] that PCG isn't meant to stand up to cryptographic scrutiny and that it hasn't been reviewed as such, while also demonstrating that, by construction, the predictability of PCG is pretty challenging, especially compared to some other RNGs still in popular use! From NetBSD's man page on arc4random: "There is no way to get deterministic, reproducible results out of arc4random for testing purposes." Other implementations of arc4random don't have the ability to control the initial entropy. Ultimately, as far as whether or not the code is simpler or faster than MT, you can judge for yourself [1]. It is not a hard read. [0] http://www.pcg-random.org/paper.html http://www.pcg-random.org/paper.html [1] http://www.pcg-random.org/download.html http://www.pcg-random.org/download.html
- lucb1e 8y ago> The descriptive word "Challenging" is used to describe PCG, while "Secure" is used to describe the CSPRNGs. In this context, it's pretty easy to understand that the "Secure" in the description is the same as the "Secure" in "CSPRNG". I would say that the same color should mean that it is of equal value. In this case, even after comparing the chosen descriptive words, it was not clear to me that this was not supposed to be a CSPRNG. It seemed so, but it could have been that it's just too new to make such a claim, or perhaps that an attack was found. The information is there when you look for it, but it's not obvious from this first impression. I see where you're coming from, but I was not trying to be misleading. I think it's genuinely confusing for someone who knows what a CSPRNG is (me), let alone the average developer who wants to generate private keys fast and finds this. Edit: and then there's this, as pointed out in another comment: http://pcg.di.unimi.it/pcg.php#false http://pcg.di.unimi.it/pcg.php#false Apparently it can be predicted with only 3 outputs. If memory serves, even good ol' MT does much better than that.
- dgacmu 8y agoNever use it for anything involving security. Ever. It's just inviting pain. It's not what it was designed for. With that said, PCG is my go-to for testing things that need fast random generators (such as prototyping ideas about hashing-based data structures). It's fast and I haven't encountered situations in practice yet where it causes failures that a stronger random source doesn't. Mersenne Twister, in contrast, can easily be the bottleneck for testing small/fast structures.
- IncRnd 8y agoIs this just an LCG that feeds into a markov chain? This seems more like marketing material than any new technical material.
- joseraul 8y agoOne author of Xoroshiro has written a detailed (and harsh) analysis of PCG. http://pcg.di.unimi.it/pcg.php http://pcg.di.unimi.it/pcg.php
- lucb1e 8y agoOuch. I did not know this was a competitive field: this description you linked is very harsh, while the table on the front page (from OP) is the exact opposite. As if both are trying to sell their product by trying to discredit the competition.
- slavik81 8y agoThere's more, too. That seems to be a response to this: http://www.pcg-random.org/posts/implausible-output-from-xoshiro256.html http://www.pcg-random.org/posts/implausible-output-from-xosh... And there's a response to the response: http://www.pcg-random.org/posts/on-vignas-pcg-critique.html http://www.pcg-random.org/posts/on-vignas-pcg-critique.html
- cmrx64 8y agoprevious discussion https://news.ycombinator.com/item?id=9887548 https://news.ycombinator.com/item?id=9887548 https://news.ycombinator.com/item?id=8590816 https://news.ycombinator.com/item?id=8590816 https://news.ycombinator.com/item?id=11836520 https://news.ycombinator.com/item?id=11836520 https://news.ycombinator.com/item?id=15019071 https://news.ycombinator.com/item?id=15019071
- SeanLuke 8y agoThis is the Nth time this website has been promoted on HN. As far as I know, a peer-reviewed academic paper has not yet been published; one was withdrawn for strange reasons. The algorithm, and claims made on this website, have garnered some significant criticism. Getting an RNG right is important. I'd not trust this method until other people in the field have verified that the author's claims are true and critics have been satisfied. The accepted method for this is peer review.
- tptacek 8y agoGetting a secure RNG right is important. PCG isn't a secure RNG; neither is xorshiro, xorshift, or MT. You can't use them anywhere security relies on not predicting future outputs from past ones. If you have to ask, don't use them. The most confusing thing about PCG's documentation is its "challenging" level of prediction difficulty. That's not a thing. The PCG authors should not have compared ChaCha or Arc4random with their generator. Other than that, I'm a little confused why anyone would care how good PCG is. We have adequate insecure RNGs already, and secure RNGs are already so cheap that they make a reasonable default. But, whatever. If people want to golf who can make the best insecure random number generator, seems fine.
- alfalfasprout 8y agoI think all these people complaining about PCG not being secure or the existence of a new insecure PRNG have never worked in simulations or HPC. Absurdly fast PRNGs that are reasonably well behaved are super useful in things like monte-carlo simulations and black-box optimization algorithms. The AVX-512 version of PCG runs at around 4 bytes / CPU cycle. That's pretty hard to beat.
- tptacek 8y agoThere are secure AEAD constructions that are <1cpb today, and they do extra MAC work that a simple PRF in a CSPRNG doesn't need to do. I'm sure PCG is faster, but for the overwhelming majority of applications, it's not so much faster as to matter; meanwhile, a fast CSPRNG also gives you security, which you might find you need later on.
- ufo 8y agoDoes PCG need to use 128-bit arithmetic to generate 64-bit random numbers?
- nnx 8y agoRob Pike is discussing Go’s math/rand update to PCG for Go2 at https://github.com/golang/go/issues/21835 https://github.com/golang/go/issues/21835
- drallison 8y agoMelissa O'Neill gave a talk in the Stanford EE380 Computer Systems Colloquium series. See http://ee380.stanford.edu/Abstracts/150218.html http://ee380.stanford.edu/Abstracts/150218.html for the abstract and https://www.youtube.com/watch?v=45Oet5qjlms https://www.youtube.com/watch?v=45Oet5qjlms for the YouTube video.
- jedisct1 8y agoFor a fast and secure RNG, take a look at Google Randen instead: https://github.com/google/randen https://github.com/google/randen