6 ms·
Randomness extractors: making fair coins out of biased coins
- leeoniya 2y agomade me think of, "bend entropy towards definable outcomes" https://m.youtube.com/watch?v=2QJjMwBAORw https://m.youtube.com/watch?v=2QJjMwBAORw
- ur-whale 2y agoDoes this work with a guaranteed random bit output bandwidth ? These techniques (eg von neumann) all seem to suffer from that same problem, namely, they crank out uniformly distributed random bits from biased sources, but with no guarantee of how long you may have to wait for a bit to come out.
- cedilla 2y agoIf the coin is biased so that it lands on heads only 1 in a million times it will take a lot of coin throws to get some randomness out of it. This isn't a limit of the technique, just a consequence of the low entropy source.
- remram 2y agoDoes it take a fixed long time or a long random potentially-infinite time?
- deleted 2y ago[deleted]
- big-green-man 2y agoThe latter (except that it doesn't always have to be long; the length of time per bit follows a gaussian distribution). If it were the former then randomness would be predictable in some sense. It's similar to the halting problem.
- remram 2y agoI'm not sure what you mean by "randomness would be predictable". For example, it is possible to do this if you know the bias.
- big-green-man 2y agoIf you can predict precisely how often in an input stream randomness occurs, it's not randomness.
- remram 2y agoKnowing the bias is not knowing exactly how often each results come out... it is still probabilistic...
- big-green-man 2y agoYeah, that's why you can't predict how long you'll wait for a random bit in an entropy extractor.
- remram 2y agoI give up. Thankfully somebody else in this thread gave an answer.
- wakawaka28 2y agoIf you know the bias, then you can surely estimate the bit rate. Of course you could get very unlucky and wait a long time for bits, even with an unbiased underlying source. But that's the nature of these methods.
- ur-whale 2y agoOr you could pump the heavily biased bit stream into a modern cipher and get a - for all intents and purposes - super high quality, completely unbiased random stream with the same bandwidth characteristics as the input. And, as a matter of fact, much faster than the input if required.
- Ar-Curunir 2y agoThings are not so simple: how do you key the cipher? with the same randomness as the input string? If so, then that input distribution could be a bad one for the cipher, in that it might fail to generate a sufficiently scrambled output. This can be mitigated if you use a unkeyed hash function instead, but even for these we don't have any provable guarantees unless you assume the function is a random oracle, which is an ideal object that cannot exist.
- chongli 2y agoYeah, if we’re starting with the “1 in a million” unfair coin then most of the input strings are going to be all 0 or all 1 which means the cipher is going to give the same sequence every time. Not useful!
- ur-whale 2y ago> Not useful! https://en.wikipedia.org/wiki/Fortuna_(PRNG) https://en.wikipedia.org/wiki/Fortuna_(PRNG) [EDIT]: Also: https://words.filippo.io/dispatches/linux-csprng/ https://words.filippo.io/dispatches/linux-csprng/
- LegionMammal978 2y agoFor certain input distributions, a guaranteed output bandwidth is impossible. For instance, suppose that you had a function that, given a vector of N integers chosen uniformly from (0,1,2), returns a single unbiased output bit. Then, exactly half of the 3^N input vectors would correspond to each output bit. But this is impossible, since 3^N is always odd, so this (0,1,2)-function cannot exist for any fixed N. Now, suppose that you had a function that turned N input bits with a 1:2 bias into a single bit with no bias. Then you could use this to implement an (0,1,2)-function as above, by collapsing inputs 1 and 2 into input 1. Since such an (0,1,2)-function is impossible, the 1:2-biased function is similarly impossible. This argument holds for any i.i.d. input source that can be generated from a uniform-integer source with an odd number of possible values.
- Animats 2y agoThat's a good question. You cannot get a non-statistical guarantee of an output rate from the Von Neumann biased coin toss, because you can potentially get a long run of the same toss result, which stalls output bit generation. That might be a generic limitation of all similar de-biasing approaches. Has that been proven or disproven?
- LegionMammal978 2y agoSee my sibling reply [0]: for many input distributions, you can never put a fixed upper bound on the number of inputs you need to get a single output bit. [0] https://news.ycombinator.com/item?id=41549648 https://news.ycombinator.com/item?id=41549648
- bjornsing 2y ago> Interestingly, this is the best possible approach, whether we know the bias of the input bit stream or not. Would love to see a proof of that. It feels a bit unintuitive to me. (But on second thought that might be because I’m thinking of cases of correlated bits.)
- LegionMammal978 2y agoIn general, I think you could show that an 'arithmetic coding' approach is optimal, if the distribution of each bit given the previous bits is known. From there, you'd just have to show that the von Neumann approach for i.i.d. bits is no worse on average.
- Darmani 2y agoThis is correct, and I came to the comments to say the same thing. It takes some work to implement without arbitrary-precision floating point, but arithmetic coding can make use of the full entropy in the input stream, whereas the approach in the article discards a lot of information.
- bjornsing 2y agoI had this thought too. But can you be sure that there won’t be any statistical patterns / correlations in the output bitstream with that approach?
- atq2119 2y agoIt's obviously false. If you know that the bias is 0.5, you can just pass the input stream through unmodified. You can also construct better codes for other biases.
- ralegh 2y agoDepends how you define best, I assume best in the article means ‘output is close to 50/50 and independent’, in which case the 01/10 solution is already optimal given the assumptions. If you define best as the most efficient at converting inputs to outputs as well as the output being 50/50 then there are better ways such as your example.
- sevenoftwelve 2y agoThe article is interesting, but it misses the most practical and unambiguously safe way to generate streams of random data: Use cryptography. To generate a stream of random data, use a hash function with arbitrary-length output (XOF) such as blake2x[^0] or shake256[^1]. Make sure your key contains at least 256 bits of entropy. Absolutely never use a key with less than 128 bits of entropy. Since it's impossible to know how much entropy there is in a key, you probably want to use something like the Fortuna RNG[^2]. Substitute the sha2/AES based construction for your XOF. Bruce Schneier designed Fortuna back when XOFs were harder to come by. If you want more performance, you can use blake2 to compress your input seed into 256 bits and generate the random stream using chacha20[^3]. All of this is usually handled by the Linux kernel[^4], so it's best to just use the getrandom(2)[^5] system call or just read from /dev/urandom[^6]. If you are writing a Rust program, you can use the rand[^7] crate, which uses a mixed approach reading a seed from the operating system and expanding it in-process using chacha[^8]. This is a valid strategy. I am omitting some subtleties[^10] about mathematical definitions of randomness extractors as used by the author of the article. When you are using a cryptographic approach, you are dealing with a complexity-theory based security notion[^9], which does not precisely equate to creating a stream with a specific amount of entropy. Everywhere – except for a physics or a math paper dealing with information theory – I would call this a technicality. For most intents and purposes, cryptographic security notions are the most real-world robust conceptions of randomness available. [^0]: https://www.blake2.net/ https://www.blake2.net/ [^1]: https://csrc.nist.gov/pubs/fips/202/final https://csrc.nist.gov/pubs/fips/202/final (shake256 is part of the SHA-3 standard) [^2]: https://www.schneier.com/academic/fortuna/ https://www.schneier.com/academic/fortuna/ [^3]: https://protonvpn.com/blog/chacha20 https://protonvpn.com/blog/chacha20 [^4]: https://lwn.net/Articles/884875/ https://lwn.net/Articles/884875/ [^5]: https://man.archlinux.org/man/getrandom.2 https://man.archlinux.org/man/getrandom.2 [^6]: https://man.archlinux.org/man/urandom.4 https://man.archlinux.org/man/urandom.4 [^7]: https://crates.io/crates/rand https://crates.io/crates/rand [^8]: https://docs.rs/rand/0.8.5/rand/rngs/struct.StdRng.html https://docs.rs/rand/0.8.5/rand/rngs/struct.StdRng.html [^9]: https://en.wikipedia.org/wiki/Security_of_cryptographic_hash_functions https://en.wikipedia.org/wiki/Security_of_cryptographic_hash... [^10]: In particular, PRFs are not guaranteed to output tokens with a certain amount of entropy – if I recall correctly – because they can map two inputs to the same output. --- I am the main author of the Rosenpass[^11] post-quantum secure key exchange for WireGuard. My expertise comes from developing this protocol, as well as a couple of years of engagement with the real-world cryptography community and from my own scientific research on cryptography and secure implementations of cryptography. [^11]: https://rosenpass.eu/ https://rosenpass.eu/
- travisjungroth 2y agoIt would be interesting to combine this with something that detects bias on a non-deterministic stream. So in one shot, it takes a stream of unknown bias and emits an unbiased stream. The closing paragraph says that’s impossible, but the tradeoff is you are only sure the output is unbiased with some amount of confidence. I think you’d also need a buffer to detect and then output.
- coppsilgold 2y agoIf you know that a source of randomness contains entropy (unpredictable bits) but you don't know how much (ex. digital camera unless heavily processed will contain random sensor noise in the output) the safest thing to do is pipe it into a cryptographic construct such as a hash or a sponge. Once you believe you piped enough you use the state of the cryptographic primitive as the seed for further random bit generation. The Linux kernel uses a sponge (to accumulate), hash function (to consolidate) and a stream cipher (to output) to 'convert' events with some degree of randomness into 'infinite' safe cryptographically secure random bits. To acquire some intuition about this you can imagine taking a raw 1MP photo with a camera sensor and then feeding the lossless file to sha256sum. You acquire a 256 bit string and the sensor noise in the photo will be sufficient to secure the result. An attacker would need to model all the degrees of freedom in taking photos in the world and sensor noise production to build a simulator for your camera and start bruteforcing your sha256 result which will almost certainly (sensor might be compromised or not really be raw) contain far more degrees of freedom than 256 bits.
- yarg 2y agoI remember thinking about something similar to this at university - I was uncomfortable with the use of biases to assign non-zero probabilities to events that fail to occur after some number of trials. If I flip a coin n times and it comes up heads everytime, what's my best estimate of the likelihood of tails? It came out as 1/2^(1/(n + 1)); and the chance of heads = (1 - that). The calculus for results in between seemed intractable to me - or at least well beyond my abilities... So I threw it into a newton-raphson solver and was happy to see that it came out pretty much linear (the most asymmetrical result will be the one for three trials, and since that was basically linear all results for greater n will be as well). But I never went quite this far - for that you'd also need to calculate the standard deviation of the probability estimate (I don't think that it would've been much harder than what I did, but it was outside of my requirements at the time, so it was something I never implemented).
- LegionMammal978 2y agoFor such a question to make sense, don't we have to first define some distribution over how the coin might be biased in the first place?
- ggm 2y agoInteresting question. I would say yes. But, there are subtle biases: * coin always favours H or T. simple bias * coin has some component of behaviour which can be on, off or reset. For example a liquid mercury component, which can bias the H or T outcome but the right kind of "flip" resets it to a known-safe mode so the coin has less to no bias. * coin has bias which only manifests in skilled hands. a particular kind of flip. The point I'm making is that probably, the bias is always assumed to be H or T favouring, but doesn't admit more complex coin bias where it could be 2 or more actors and 2 or more capable of biassing, and a pigeon who can't (or a dummy, and a pigeon: a good con generally has more people involved than you think)
- hervature 2y agoThis is the Bayesian vs. frequentist view point. What the OP is talking about is assigning a Beta(1,1) prior on the distribution and observing n heads in a row would yield a distribution of the bias of Beta(1, 1+n) and the mean of that distribution is 1/(n+2) which means the OP is off by one in the denominator but still good for memory. However, that is if you take the mean as your best estimate of the bias. If you take the mode, then the OP would be satisfied that even the Bayesian approach says that tails would be impossible. The frequentist view would say your best estimate is the average of the observations which would yield a completely unfair coin.
- clircle 2y agoThis is a specific type of general algorithm/research area called Bernoulli Factories if anyone wants to go deep.
- andrewla 2y agoThanks for this pointer -- I had read a Knuth paper ages ago that talked about this, but I couldn't remember the term of find the paper again, and this led me directly to [1] which led me back to [2] [1] https://peteroupc.github.io/bernoulli.html https://peteroupc.github.io/bernoulli.html [2] Knuth, Donald E. and Andrew Chi-Chih Yao. “The complexity of nonuniform random number generation”, in Algorithms and Complexity: New Directions and Recent Results, 1976.
- j7ake 2y agoThe insight here is that you need to emit two signals that has equal probability, even if those two signals are rare in the full distribution. In the full distribution, you’re allowed to add any other kinds of signals that aren’t those two. You then throw out all signals that are not those two signals, and the conditional distribution will renormalise itself to give you a fair coin toss. You pay for this by throwing out many bits that are not these two signals. The less fair the coin, the more coin flips you throw away. In the trivial case of a fair coin, you throw away nothing and keep every coin toss. In a biased coin, you throw away any pairs of HH or TT. Independence is a major assumption underlying any of these models.
- andrewla 2y agoI haven't dug deeper, but the claim that the von Neumann approach is optimal does not seem intuitively correct. It seems like you could squeeze a tiny bit more entropy from it -- basically, if you reject two pairs in a row, the nature of that rejection tells you something. HT xx -> H TH xx -> T HH TT -> H TT HH -> T
- nimish 2y agoYou're correct. There are more sophisticated extractors like Elias' and Peres' that do better, asymptotically achieving the upper bound given infinite data. See https://peteroupc.github.io/randextract.html https://peteroupc.github.io/randextract.html
- Maro 2y agoOP here. Thanks for that, that's obviously better in terms of bitrate, I haven't thought of that. Any two bit sequences with equal probability can be used to emit either a 0 and 1..
- alphazard 2y agoSomething maybe obvious but worth repeating is that there are 2 kinds of errors: predictable and unpredictable. Bias is the predictable error, it's the direction we are likely to be wrong in. In many practical applications unbiased error is not what we want. If the cost of being wrong in different directions is asymmetric then we want to be biased so that our mistakes are less costly. The unpredictable error is noise. In this example we are trying to create something maximally unpredictable, so the goal is to remove all biases, giving pure noise.