Designing Random Number Generators
- existing methods: block data, DAO solution, external service, state-channel
- limitations: miner dependency, blocktime dependency, centralization, exception handling
- SlotNSlot design: 2-parties commit&reveal with Whisper p2p messages
Random Number Generators in Gambling
Random number generator(or RNG) is critical in ensuring fairness of gambles, random meaning “equally unpredictable” in the context. In typical computer systems, RNGs are designed to take sufficient entropy from sources such as hard disk drive and use the entropy to generate the numbers. The sources are in many cases the timestamp of the system, which then be encrypted with a one-way function. These kinds of RNGs are used in most of existing games, and is a necessity especially in gambling.
RNG in Ethereum
In blockchain networks, numerous nodes share a consensus of “states”, thus making it a deterministic system. It is impossible to generate randomness solely inside any deterministic system. There might exist contract codes that generate randomness using seeds from the system that commits the code, but this would disrupt the consensus of the blockchain since the resulting value of that randomness will be different depending on who computes it (i.e. nodes will have different states). Blockchain developers have been researching various breakthroughs to this problem.
1. Utilizing Block data
Every block has unique data such as blockhash, timestamp, and any other miner-defined values. Some of such values like blockhash are unpredictable thus leaving usability for seed of randomness. For example, Alex Van De Sande proposed using previous blockhashes as seeds and SHA3 encrypting them to generate random numbers.
As he describes in the comments, this has a vulnerability that the miner can decide whether to publish the block after getting the resulting random number. To describe the problem in short, the resulting random number is block-dependent. Nevertheless, unlike other alternatives this method gives immediate response from the smart contract, and is most straightforward with no requirement for other considerations except for the miner manipulation.
2. DAO Solutions
RANDAO proposed a collective commit&reveal scheme to generate random numbers. It solved the block dependency problem mentioned above by distributing the entropy seeds to a specified number of participants. The RANDAO method flows with two steps.
In the first step, more than N participants commit their encrypted SHA3(s) value to the contract along with a specified amount of ETH as pledge, during a specified period. If the contract received less than N number of commits, this round of RNG fails and the pledged ETH are returned. After receiving more than N encrypted SHA3(s), in the second step, participants reveal their original numbers s to the contract. If all of them are verified, they are used as seeds to generate random numbers to be sent to requesting contracts, and the pledged ETH plus commissions from requesting contracts are rewarded equally to every participant. If any of the participants fails to reveal a valid original number, that participant loses the pledged ETH and other participants are refunded their pledged ETH plus the penalized pledge. The RNG fails in this case as well.
This makes the RANDAO method fragile to DDoS attacks, since a single malignant participant can disrupt the RNG. Furthermore, the RANDAO method can’t achieve an immediate RNG. Video gambling games require a minimum degree of speed in gameplay, which is in SlotNSlot case less than 10s for every play.
Vitalik Buterin suggested a modified DAO solution which doesn’t depend on honest revelation of participants. The idea is to hash-encrypt the seeds for enough rounds, as well as tweaking the seeds by adding the blockhash. According to Vitalik, even a single participant won’t be able to manipulate the result. There’s still limitations that it still suffers from miner manipulation, and requirement of timespan for a specified N blocks confirmation. Moreover, transaction fee would skyrocket if the computation of such enough rounds would take place on-chain. (According to Ethereum yellow paper, Blockhash computation costs 40 gas.)
3. Off-Chain Solutions
Some found a breakthrough on existing RNG services outside blockchain, such as random.org or WolframAlpha by utilizing oraclize.it. When a contract requests random number with oraclize.it API, random numbers generated off-chain are sent via oracle contract to the requesting contract. These will trigger _callback() function inside the contract to finalize the RNG request.
This may sound as simple as the API calls in centralized services. However, there are obvious problems. Fail-proof property of DApps evaporates since these centralized services can be suspended anytime. As mentioned above, requiring some blocks confirmation exists in this implementation as well, thus making it unsuitable for real-time services. Above all, a centralized service can be corrupt at any time. Imagine someone playing the slot machine game while the same person determining the random number for that game. This absolutely doesn’t make sense at all.
4. State-Channel Solution
State channels came out to enable frequent micro transactions between two specific parties with exactly two transactions on-chain. The micro transactions take place off-chain with co-signing of both parties, and final “state” is verified on-chain. A state channel is initialized by pledging certain amount of ETH from both parties on a multi-sig contract. Transactions inside the state channel contain a nonce, each having a greater value than its previous one. A single final state with the largest nonce will be verified by the initializing contract as a final state to be updated to.
Dennis Peterson posted an example code implementing the idea. Each players initialize a chain of hashed values long enough to cover numerous transactions, 10,000 in Dennis’s example(hereafter would refer to this “chain” as X-chain to distinguish from the blockchain). Each value on these X-chains are encrypted value of its previous one. (i.e. X = SHA3( X ) ). For every transaction in the state channel, each player sends the last unused value from the X-chain. These values are preimage of the values sent in previous transaction, thus enabling verification of them. The values are then used as seeds for RNG to run the game. As soon as the whole X-chain is consumed, or either of players requests to quit, the final state will be sent to the initializing contract.
State channel solutions would definitely reduce the cost since they are off-chain, and the time required for each RNG trigger is at worst case less than 2 seconds. However, since SlotNSlot aims to support mobile platforms, which is prone to exceptional disconnections such as battery exhaustion and network disconnection, exception handling came as a significant problem.
Imagine Alice and Bob, as in Dennis’ example, playing a thousand of rounds with their 10,000 numbers X-chain. Bob’s phone suddenly turns off, disconnecting him from the network. Alice still has whole transaction histories from 1st to 1,000th round, corresponding to 10,000th and 9,000th numbers on the X-chain respectively. She then has a decision over those 1,000 “states” to submit to the initializing contract as the final state, since all of them are already co-signed by both Alice and Bob. If Bob couldn’t get connected back for a certain period of time, say 1 hour, the design of the contract must be either i) to accept what Alice submits assuming Bob to be maliciously and intentionally not submitting, or ii) to wait for Bob to also submit. As waiting forever can’t handle the former case, the contract would wait for a specified period, and after this Bob would unfortunately be considered intentionally not submitting. Then the contract must be designed such that it forces Alice to submit the final state, i.e. 1,000th round, because otherwise she would submit one of the states that maximizes her benefits.
This scenario is just one of situations we guess would happen. The SlotNSlot team is aware that there are several developers researching on this implementation. However, the team has planned to implement a distinctive method, which will provide more options to the Ethereum society.
In designing SlotNSlot RNG solution, major considerations were issues mentioned above; no miner dependency, no blocktime dependency, no manipulation of game results, low transaction fee, and exception handling. The team had come up with a commit/reveal scheme, using the Whisper protocol. In the design, both parties will trade their seeds (commit&reveal) off-chain with Whisper, and then the last-to-reveal party will reveal to the chain both seeds. The flow is as follows.
1. [p2p] A player triggers a spin in the slot, calling the banker to send his own encrypted random number N’ (= SHA3(N)) with Whisper protocol.
2. [txn] The player generates his own encrypted random number M’ (=SHA3(M)) which isn’t used previously, and send it to the game contract with N’.
3. [txn] The game contract id is sent to player.
4. [p2p] Player sends his M’ with game contract id to the banker to verify the game.
5. [p2p] The banker verifies the game, and sends his original N to the player.
6. [txn] The player sends both the original numbers (N, M) to the game contract. The contract verifies (N, M), uses XOR(N,M) as a seed to generate the random numbers, and records the result.
As this method utilizes a commit&reveal scheme, there is no manipulation possible nor the miner dependency. Transaction fee and blocktime dependency is minimized by using Whisper, i.e. transferring seeds off-chain. Exception handling is further relieved by recording the game histories in atomic unit.
In a presentation by Timo Hanke, it was mentioned that commit&reveal schemes have an fundamental limitation that the last-to-reveal always have a choice to abort the result, i.e. not revealing the final seed. In SlotNSlot design, it wouldn’t be a problem since the last revealer is always the player of the slot, and the player’s worst case result is always losing the bet on that specific round. Thus, if the game contract failed to receive the last reveal stage, it could just penalize the player by giving the bet to the banker.
SlotNSlot’s current solution has relieved some of existing challenges from RNG on blockchain. There are, however, still much to improve in cost, speed, and exception handling issues. The team will continuously devote to researching possible modifications and/or alternatives for a better RNG design. Keep up with SlotNSlot communication channels to find out what’s more to come up in the near future.
Check out our
WebPage // Whitepaper // Github // Twitter // HipChat
*you can join our hipchat without sign up