Fair Random Numbers on the Blockchain Are Absolutely Possible
There are two big, known trust problems with generating random numbers on the blockchain in a traditional way.
- They can be manipulated by miners.
- They aren’t secret, and therefore the results can be predicted.
This is especially problematic when we start attaching currency to smart contracts. There becomes an overwhelming incentive to cheat. And with blockchain-based gaming on rise, developers have frequently turned to off-chain oracle services to inject random numbers into their contracts.
While the most popular off-chain oracle, Oraclize, does provide some degree of verifiability through its off-chain TLS proofs, it is not as bulletproof as the blockchain itself, still relying to some degree on external trust. And of course, there are fees to consider.
But I think we can do better than that. There is a lot of disinformation out there on the subject, but it’s well-traveled territory, and we can do this right on the blockchain using some good math and some good rules.
This Article is Unaudited
While I am confident that I do know what I’m talking about, this article has not been audited or vetted by academic experts in the fields of game theory or cryptanalysis. Any code you may write based upon the ideas in this article should be rigorously reviewed not just by engineers, but by mathematicians.
Cutting Out the Oracle
I’m going to show you how to design a cheating-resistant, fair coin toss for the blockchain. No off-chain oracles involved. Here’s a very quick overview of the approach.
- Players commit to secret random numbers.
- They reveal their numbers.
- The numbers, now revealed, provide the basis for a random result that neither player could have predicted.
Depending on your education or experience, you might see where this is headed. Let’s dig a little deeper.
The “Coin Toss”
- There are two players: Alice and Bob.
- Alice chooses a secret integer
Aand Bob chooses a secret integer
B, both in the range
[0,N]. (Use the largest value of
Nyour contract can use, choose a good hash algorithm like SHA3, and use salt to break rainbow table attacks.)
- Alice sends a hash
H(A)of the secret to the contract, but not
Aitself. Bob can see
H(A)and knows that Alice has committed to her number, but he doesn’t know what
- We’re about to start revealing secrets. Bob should wait for the network to confirm Alice’s transaction, or else he risks being cheated.
- Bob holds the last uncommitted secret, so he can skip hashing it and reveal
Bdirectly to the contract. Alice has already committed to her choice and cannot change it. (We could also have Bob follow exactly the same steps as Alice, which might make your contract easier to code and use, but it’s not strictly necessary or useful to the integrity of the game.)
- Alice then reveals her own secret by sending
Ato the contract. The contract independently computes
H(A)and verifies that it matches what Alice previously sent.
- If Alice was honest, the contract proceeds to compute the modular sum
S = A + B (mod N).
- Alice wins when
S <= N / 2. Bob wins when
S > N / 2.
To use an analogy, it’s like each player, in turn, reaching their hand into a black box and turning a wheel. No player knows to what degree the other players have turned this wheel, therefore they cannot predict what position the wheel will be in when the box is opened.
A point of clarification: You can extrapolate this technique to more than two players. Everyone follows the same steps as Alice. Everyone’s secrets are incorporated into the modular sum
S, and everyone is assigned a range of
S values in which they win.
You’ll notice that I never said the secret numbers had to be random. And of course, they don’t. The blockchain has no guarantee that players will send random numbers. So what happens if players don’t send random numbers? Simply: Players who don’t send random numbers open themselves to attack.
If I see that you’ve been sending predictable numbers in previous games, I can adjust my own numbers to the pattern, and I will increase my odds of winning future games against you. If you use random numbers, I can’t do that. The same applies in the opposite direction. We have a mutual incentive to be perfectly random.
Alice doesn’t have to trust Bob, Bob doesn’t have to trust Alice, neither of them has to trust an off-chain oracle, and the contract developer doesn’t have to pay oracle fees.
That having been said, there are attacks. There are always attacks. We need to talk about what they are and how to mitigate them.
Some of these attacks speak of collusion. It is less difficult than the word implies. Remember that, on the blockchain, one interested party could be puppeting several actors on a contract.
Colluders manipulate the result by sharing their secrets off-contract
To mitigate collusion, any party who stakes something of value on the result (be it coin or mere game integrity) should also contribute a secret to be used in the contract. By that, I mean that no one’s balance sheet should be affected by the contract unless they also influence the outcome. It takes just one good actor to spoil the cheating attempt of everyone else. And if everyone with something at stake also turns the “wheel,” there is no incentive for an all-contributors collusion scheme.
A bad actor walks away without revealing their secret
Consider our coin toss game. Bob added his number to the contract. At that point, Alice knows whether she will win or lose. So instead of revealing herself to be the loser, she could simply walk away. To mitigate this, build incentives for timely reveal into the contract. For example, let’s say Alice and Bob stake some ETH on the result. We build in a reward whereby Alice as the loser receives 5% for revealing her secret within 24 hours, and Bob as the winner receives 95%. If she has not revealed her secret after 24 hours, Bob is the de facto winner and can withdraw 100%.
Secrets combined via (xor) can be manipulated to a desired result
Above, I prescribed the use of modular addition to compute the result. Why do I mention
(xor)? Because crypto nerds love
(xor) and may be tempted to use it instead. Without extra steps it is vulnerable to an attack. The reason is:
X (xor X)is, for any value of
X (xor 0)is, for any value of
X, equal to
- If the hash
H(A)is equal to the hash
Ais equal to
If Charlie sees that Alice and Bob both submitted the same hash, Charlie knows that the current value of the “wheel” is
0. He additionally knows that if he submits his hash
H(C), then the new wheel position will be
C. Suppose Bob and Charlie are colluding. They wait for Alice to submit. Bob submits the same hash (with the same salt) in order to place the wheel at
0. Charlie can then pick the outcome. One way to mitigate this might be to use additional hashing steps, but much more simply we use modular addition instead of
(xor), and we avoid this problem altogether.
Barriers to adoption
If math alone can solve the problem and eliminate oracle fees, why is this technique not more widespread in the blockchain world? Why does everyone keep using the oracles instead?
There are probably a few parts to that answer. Firstly, and I promise I understand the irony of saying so, blockchain tech has recently seen a large influx of generalist programmers who may not be aware of some of the cryptography techniques at their disposal. Secondly, convenience. The contract owner’s convenience of not running their own infrastructure to handle the secret reveal lifecycle, and the customer’s convenience in being able to, in some cases though not all, simply interact with the contract via a vanilla wallet rather than a Dapp.
But if you take away one thing from reading, let it be this: We can can create fair, consensus-based “random” numbers on the blockchain without trusting 3rd-party oracles. It is a solved problem.
What do you think? Too much bother? Did I miss an attack vector? Yell at me in the comments.
Edited August 22, 2018 for some extra caution and clarification. Thanks to Arseny Reutov for the feedback.