When random is not actually random enough | Hacker News Reader

When random is not actually random enough

ersc.io

64 pointssteveklabnik27 comments

The blog post doesn't mention the term, but what it describes is commonly known as a "modulo bias" in cryptography.

A Uniform(0, 1) PRNG is the right primitive on which to base a PRNG library for arbitrary real-valued random variables because any real-valued random variable can be represented as an inverse quantile transform of a Uniform(0, 1) random variable. While I agree that only providing this primitive risks footguns as described in the article, I'm skeptical that providing a better UI alone would meaningfully reduce the risk of such footguns because availability and convenience is no guarantee of use if a prevailing attitude of users is that they know better and don't need it. Bisection search is simpler than rejection sampling or inverse transform sampling, yet it's common to see buggy, hand-rolled implementations of bisection search despite wide availability of library implementations with better UI ergonomics than PRNGs. I think wider use of fuzz testing or deterministic simulation testing really is necessary to disabuse people of that notion, along with more articles like the above explaining why hand-rolling an adapter to a uniform PRNG is a false economy compared to proven implementations with vetted statistical properties.

I don't really follow your argument.

> I'm skeptical that providing a better UI alone would meaningfully reduce the risk of such footguns because availability and convenience is no guarantee of use if a prevailing attitude of users is that they know better and don't need it.

If we transfer that argument to other domains it quickly falls apart: We don't need a safety on handguns since some people will opt to not use it properly. We don't need safety belts in cars since some people won't use it. We don't need handrails..

You get the point. This is basically the Nirvana fallacy (also called the perfect solution fallacy): a safety measure not being able to catch 100% of the cases it was meant to prevent is not an argument against it. We could have an argument if that measure would significantly impact usual use cases. Any safety measure needs to be judged both by the benefits and by how practical it is to deploy it (aside from other considerations like maintenance, etc)

In this case having an easier to use API is the opposite of impractical. It both safes developers time and reduces the number of errors. And if you still need to write your own function, you totally can. To me that sounds as close as you can get to the definition of a "no-brainer".

The thing you actually want is rejection sampling: https://en.wikipedia.org/wiki/Rejection_sampling.

That Wiki page makes it sound very complicated but for this purpose our implementation can be laughably simple which has the advantage that you know why it works and can maintain it properly with confidence.

Get suitably large inputs, for example if you're trying to pick integers between 2 and 11 inclusive, a nibble (half a byte) would be fine. Now, is the random input in the range you wanted? If so, you've got your answer. If not, throw this random input away and get more.

Too many programmers act as though random numbers were a precious resource.

Wow that page really gets lost in the weeds of multiple dimensions.

And yeah it's just rerolling when your random number is out of range. If you want it as simple as possible, always generate from 0-n, and grab barely enough random bits for n to fit.

Random numbers aren't precious, but they do take time to generate. Rejection sampling adds a branch and it can matter how often it's taken. In my property-testing framework, generating a large, random array of numbers more efficiently improved performance.

If your RNG outputs a u64 (a getrandom() call can do this, or even a simple RNG like xoshiro), a random int in TFA's range of [0, 10) has a very small (6 in 2⁶⁴ chance, or 3.2e-17%, might as well be 0) chance of needing to redraw.

Obviously, wider ranges will (possibly) reject more often, but unless the range is huge, rejection should be a very cold branch.

You’re throwing a lot of bits away, though. If you used four bits per number then you could pack 16 random digits into one 64-bit draw. But a rejection-sampling branch will be taken much more often.

If you want to split a 64-bit random number into 16 4-bit random numbers, the quality of the RNG that generates the 64-bit random numbers must be extremely high. Only cryptographic RNGs may have such a high quality.

Any non-cryptographic PRNG is useful only if it is much faster than a cryptographic RNG, e.g. one using AES, which in many modern CPUs needs around 10 clock cycles to generate a 128-bit random number (less than that, even less than half of that, in some more recent CPUs).

So non-cryptographic PRNGs must generate a 64-bit number in less than 1 nanosecond to be competitive. Many older PRNGs are not this fast, so they are completely obsolete.

Such PRNGs do not offer any guarantee that if you take more than one piece of a generated number they will not be correlated. So the rule is that you can not make 2 or more random numbers from 1 random number provided by a PRNG.

Rejection is unavoidable if you want a uniform distribution for a number of choices that is not a power of two.

Nonetheless, the rejection can be done either before or after the multiplication or division that does most of the job for passing from the input range to the output range.

The place where rejection is done can be chosen to minimize the amount of values that are rejected, making thus unlikely that the branch is taken, so it will be correctly predicted most of the time.

For maximum speed, it is preferable to use multiplication instead of division, i.e. the input is seen as a fraction less than 1 and after multiplication only the integer part is retained. Taking care to use multiplication is normally more important than worrying that rejection may decrease the performance.

I got lost when OP talked about using 10 integers to choose from 3 choices. I think I figured out what was missing in the explanation.

random_u64() Mod 3 does indeed have a single bucket that is oversized. This overweights one option by about 5×10^-20.

rand() Itself has only 32767 possible values, so it's also common for a bucket to be overweighted depending on the number of buckets.

Makes you wonder at what point overweighting by about 5×10^-20 is something you'd want to care about.

Picking that from the noise would take quite a while.

this is what has always baffled me about statistics...having the opportunity to make things exact, with little effort, it is dismissed just because the small error

It's basic engineering to do what is necessary for solving a problem. Not more.

Not unless of your definition for "what is neccessary for solving a problem" already includes tolerances for the unforseen.

> rand() Itself has only 32767 possible values

For MingW maybe (due to MSVCRT). I think most libraries such as glibc have RAND_MAX at 2147483647.

I think this is interesting theory and fun to read about. If I was actually working with cryptography this would seem immensely important. I would also be arguing vehemently online about the std implementation of Mersenne twister and worrying about people analyzing bulk traffic with advanced scripts scraping a hundredth of a bit per sample.

But, I make games.

After finding out that trig/transcendental was basically not guaranteed to be equivalent across kernels (libc/musl), which caused the dreaded “only fails in CI” problem for me when I was trying to generate nonflat distributions of drng’s, I ended up creating https://github.com/pmarreck/random to solve it, which it did

Curious why you used Box-Muller for normal PRNGs instead of Ziggurat.

Ziggurat is badass. It’s also one of those algorithms (like “Metropolis-Hastings”) that has a fantastic name to go along with cool mathematical and practical properties.

https://heliosphan.org/zigguratalgorithm/zigguratalgorithm.h...

I don’t think the “random uint” api is too low-level, or lacks a pit of success - I think you’re just reaching for the wrong api. The problem of “make n bits pseudo randomly set to either 1 or 0” is nearby to your problem of “choose an element according to a probability distribution”, but it’s a separate problem in its own right.

I think actually this is an argument for language designers to include a “std.choice” in their standard library that consumes random bytes and correctly performs common ergonomic operations like “get one element at random from this collection”.

(If your standard library tries to make a distinction between “regular random number generators” and “cryptographically secured random number generators”, I think this distinction between “generate random bits” and “make probabilistic choices” is about equally important.)

The modulo operator is not a uniform mapping; use Lemire's nearly divisionless method or simple rejection sampling and move on.

so it's not really *random* that isn't random enough - it's the operator% that worsens it

Exactly. There's many a page on random which explains why taking the modulus of rand is the wrong choice, but it's also the easiest one, which makes it all to common.

Yes, but that wouldn’t work as clickbait.

Randomness test > Specific tests for randomness: https://en.wikipedia.org/wiki/Randomness_test

Which NIST SP-800-22 implementation instead of the now-archived paranoid_crypto randomness tests?

paranoid_crypto/docs/randomness_tests.md : https://github.com/google/paranoid_crypto/blob/main/docs/ran...

/? NIST SP-800-22 Rust: https://www.google.com/search?q=NIST+SP-800-22+rust&oq=NIST+...

Sometimes it's possible to whiten random to make it uniform random or normal random;

Whitening transformation: https://en.wikipedia.org/wiki/Whitening_transformation

Reply on news.ycombinator.com