The goal of this lecture was to give examples on how bitcoin could be used as a public randomness protocol. This lecture builds on the previous such that instead of each person generating their own randomness and combing it together, you have more convincing randomness to the public.
- What is public randomness?
- What are examples in the real world of public randomness?
- What is the NIST beacon and Bitcoin beacon?
- How can Bitcoin be used as public randomness?
Public Randomness
Public randomness in cryptography seems to not have been formally introduced until 1992. Randomness is super useful to create simpler, or more efficient algorithms. It’s also useful in the construction of cryptographic primitives. Public randomness seems to mean that the random bits are accessible to all parties enacting the primitive and to any adversary trying to break the primitive.
The proper definition I found from this paper, Public Randomness in Cryptography is “A source of random bits is public for a primitive if it can be read by all the parties enacting the primitive and any adversary trying to break the primitive. The public random string is always chosen uniformly. This line from the paper, i found a bit contradictory, “Although the public random bits are known to an adversary, it turns out that these bits often plays a crucial role in ensuring that the primitive is secure”.
NBA Draft Lottery
The lecturer then transitions to talking about the NBA draft lottery. Honestly this was completely irrelevant segment though highly entertaining. 30 teams come together and randomly choose some weighting based on teams past performance the year prior who has first pick to draft top amateur player in the country. This began in 1985 with the Knicks getting Patrick Ewing. Prior a coin toss was used to get the first pick. Apparently people saw this as a conspiracy and that it wasn’t truly random. I google “conspiracy theory Knicks Patrick Ewing” and have shared some of the results. There was some deliberation over the envelope could have been tampered with. It’s strange that May 14, 2019 many of the news media posted new articles about this, guessing this was due to an anniversary of sorts. It’s interesting that the entire draft lottery was actually full televised as the NBA were trying to get publicity. The lottery is still done every year and people still cal foul but perhaps not to the same degree as 1985.
1969 Vietnam Conscription Lottery
This was a higher stakes lottery though isolated to the United States as before. The lottery was to determine which men would be sent off to ware with Vietnam. Congressional people dropped all dates in blue plastic capsules into a metal drum and took turns reaching in to remove blue capsules out. Based on the date drawn, it would indicate priority of being conscripted. These numbers wold be broadcast on live TV and radio broadcasts to share with the American public. That to me seems terrifying. This was seen as fair as birthdays were being chosen at random.
Though looking at the results, it was unfortunately botched. Birthdays that were late in the year had lower priority than those found earlier. The cause was explained how they were rotating the drum and even number of times so that the capsules initially put on the top were still more likely to be picked.
Cryptographic Beacons
The two example showed that this problem is actually needed. Getting the public onboard is difficult and people will always come out if they don’t think its fair. This reduces to a more abstract idea.
The idea is cryptographic beacons, which is a service to regularly publish random data As discussed above, it must follow the features of public randomness. Thus the applications could help for lotteries, auditing, ZKP, and cut and choose protocols. The beacons must be cheap, easy, and simple to understand. Though it’s difficult to make this trustless. So the public lottery may not work remotely and distributed, and thus the lecturer provides some modern day solutions
NIST Beacon
NIST does something similar where they have quantum-mechanical randomness that they give to the public. Interoperable Randomness Beacons is what’s on their website and was started in 2011. In 2019 they have a reference for randomness beacons that they’ve published. I’ve provided the diagram reference similar to what the lecturer showed: https://www.nist.gov/image/belltestillo900png. I don’t know what a loophole-free Bell test but that’s what the NIST beacon uses. Full taken from wikipedia, “Bell’s theorem, also referred to as the Bell inequality or Bell test in actual experimentation,[1] proposes a testable construct for resolving the disparity in causality and locality that exists between quantum mechanics and classical physics models, specifically the concept of quantum entanglement.” Every 60 seconds they publish random data (512 bit) and sign it. Downside to trying to use this, is that one must trust NIST. They could be lying to you… was the one con for this. It’s interesting they have a warning on their website about WARNING: Do NOT use Beacon generated values as cryptographic secret keys! This is line with the the lecturer as you want ot use the public randomness for other mechanisms but not secret key generation.
Natural Phenomena instead
Thus the idea is instead of using one person who needs to be trusted to produce data, one uses natural phenomena instead. Examples of natural phenomena were sun sports, cosmic background radiation, and weather data. Because they can be read all over the world publicly, these are observable but also random data that nature produces. The issues the lecturer brought up was that this data was slow and needed a trusted observer as collecting this data isn’t that easy.
Stock-market beacon
Thus the next idea is to use stock market prices as a beacon. Prices are generated regularly, and the claim is they are costly to manipulate. Though, there could be slow insider attacks though. This was fairly short section and I could only find one academic source about this. The paper covered that these random bits were sound for post-election audits in E2E elections so there was a very specific use case for this data.
Remove central trust: Bitcoin nonces
Nonces are somewhat random. Thus minders finding the random nonce could be that source of randomness. One benefit is these nonces are found every 10 minutes and published pubicly to all miners. At this point, there is no way to predict the next nonce with significant probability as that would give people a mining shortcut. Current there are about 66 bits of randomness which is difficult to predict. Then we discuss how this acually works.
Using the blocks to become a beacon isn’t too difficult. Each time a block is published, the block header data is run through an extractor function that essentially hashes all the data into a unique output. This unique output is a uniform string which anyone could compute. Then we examine the potential security vulnerabilities. The vulnerability would depend on the cost of manipulation which is this case would be the block reward. The attack vector would be manipulating a miner to either throw out a computed block or nonce and not get their block reward. Thus you don’t want to use this randomness beacon on say a NBA lottery where its impact is more expensive then an outputted block reward. The cost of manipulation was pretty simple match.
Bernoulli Trial: forcing a beacon outcome with probability p requires discarding 1/p-1 blocks and discarding a block costs the block reward (12.5 BTC). Thus for an N-party lottery it’s (block_reward) (n-1).
The downsides are those key features to BTC. Timing is slightly imprecise as every 10 minutes isn’t actually true. If you’ve ever looked at block times leading up to or after a fork they tend to fluctuate. Also, this way of randomness is only temporary. As the block reward halves at each section, the randomness mechanism will likely only to be done for cheaper and cheaper lotteries. That said, it could be useful and at least provides a manner of how a public blockchain could be used.
Beacon support using Bitcoin script
New idea is chosen to try to resolve the previous constraints. This one adds an opcode to BTC for a beacon call. The advantage is that it can build multi-party lotteries in only one round without any bonds and no time delays for refunds. So this beacon call would use the previous block’s randomness within its input.