Proof-of-Randomness: UltraYOLO’s Random Number Generation (RNG) on the Blockchain
Importance of Randomness in Blockchain
Generating a secure source of randomness could be the single most fundamental technical challenge in the blockchain space. The best way to understand this is through a thought exercise using the Bitcoin blockchain.
A Bitcoin Thought Experiment
Let’s suppose that Bitcoin’s Proof-of-Work system has no randomness built-in and that each block’s producer could be predetermined. In that case, an attacker could simply DoS the winning miner and put the Bitcoin blockchain in limbo. If we take this thought-exercise one step further, it is not too farfetched to imagine that this attacker, using a similar method of prediction, could also make himself the leader of every block to win the block reward and manipulate transactions. Even if the attacker is not capable to that extent, he can at least “bribe” the leader to influence the system. It could be said that the integrity of the Bitcoin blockchain relies upon the temporary random leader of the system.
Another key characteristic to Bitcoin ecosystem is the hash puzzle. It is totally verifiable, as in if a miner claims to have solved the hash puzzle, all the other miners could verify that he has indeed solved the puzzle. This type of provably random number generation is what makes Bitcoin special in the first place, but comes with the expense of heavy electricity usage[1]. Whether there is a way to generate Bitcoin level randomness on the blockchain without using so much electricity becomes the topic of discussion.
A Look into Existing RNG Methods
After much research, the UltraYOLO team has come with a solution at the protocol level called “Proof-of-Randomness”, which utilizes the BLS signature scheme as the source of randomness. We’ll explore and compare a few options that different projects and see how they hold up under our standards of “random” and “verifiable”.
BlockHash
There has been a number of projects in the gaming space that use the block-hash or transaction-hash of Bitcoin and Ethereum, namely the infamous SatoshiDice (Bitcoin Transaction Hash), SmartBillions (Ethereum Block Hash) and Ethereum Lottery (Bitcoin BlockHash). The good thing about using the blockhash is that it is deterministic, meaning anyone can double check the result of the RNG using a block explorer and some simple math. However the obvious drawback is “they are not beyond the reach of tampering”[2] as described by the Ethereum Lottery team themselves. It could be imagined that miners will start colluding with each other and tamper with the result of the random number once the potential reward is larger than the block reward + transaction fees. There is an incentive to behave dishonestly.
Oraclize
OraclizeIt has implemented a Ledger hardware-based RNG and Ledger Proof[3], and could be argued as the method with the most amount of entropy. It is unique given that it is a hardware-based random number generation method compared the other software-based methods. Hardware based methods are often thought of higher levels of entropy[4], because they do not depend on the algorithm and seeding. Hardware-based RNG are “truly random” as opposed to software-based ones which are often regarded as “pseudo-random”. And with the proof that is built into the Oraclize code that guarantees the application code is what really was ran, so the random result is verifiable, Oraclize matches both requirements of “entropy” and “tamper-proof”. However, the issue is that it is a centralized service which goes directly against the fundamentals of blockchain and decentralization. No one really has information of where this Ledger device is stored and who ultimately has control over it. Given the reputation of the OraclizeIt team and the number of projects that already depend on their solution, UltraYOLO will initially use their platform while Proof-of-Randomness is being developed, and will move off their platform on a later date.
RanDAO
One method that has gained much popularity in the Ethereum community is RanDAO[5]. RanDAO was first designed to be a better deterministic source of randomness on the blockchain because “miners cannot be trusted”. RanDAO is a 2-phase commit-and-reveal scheme, where participants first commit a hashed version of their seed and then reveal the original seed at a later time. All seeds committed and revealed by the participants will be used to generate the final random number. The integrity of this scheme relies on the assumption that not all parties of the commit-and-reveal process are from the same cartel and colluding with one another.
In a perfect smart-contract platform with fast transactions and low fees, RanDAO could be a very sound RNG method. However, the current blockchain space does not favor a dApp level RNG scheme. The process of committing and revealing all random seeds is simply too time-consuming and costly for all participants. Potentially after Ethereum’s lightening network (Raiden) is implemented, RanDAO will be more feasible once transactions become faster and cheaper.
If UltraYOLO team were to utilize RanDAO, we would have to use a smart-contract (SC) platform, such as NEO, EOS Cardano, or implement our own. However, all SC platforms currently require scaling solutions, and the UltraYOLO is focused on designing technical systems closer to our core business instead of a heavy-handed SC platform. Thus the RanDAO solution was forgone, and the decision made to build our own lottery protocol: “Proof-of-Randomness”.
State Channels
State channels are mentioned because they are used by a few projects in the blockchain gaming space, ie: Trueflip. It follows a similar idea as the Lightening Network. Basically 2 parties that are participating in a gambling game will pre-generate a chain of, say 1,000 numbers with each number being the SHA-3 hash of the previous number: X[1000] = SHA-3(X[999]), X[999] = SHA-3(X[998]), etc. The game progresses as they communicate the SHA-3(X[1000]) to each other. At each round of betting, the players would reveal of the pre-image of the value to each other. So for the first round they would reveal X[1000] to each other. Now that they each know SHA-3(X[999]), and the random number would be the two X[1000]s XOR-ed together. They would repeat the operation in the next round until all values are used. This is a valid RNG scheme for a 2-party or potentially a multi-party gambling game, but for the purpose of a lottery, this is not extremely applicable. There are too many participants and the communication would be too costly. It would be better to cut down the communication cost amongst all parties, which leads us to our final option and ultimately what the UltraYOLO team has decided to implement.
BLS Signature Scheme
The BLS is a pairing-based signature scheme that offers comparable level of security to RSA-based signature schemes. It has strong academic backing and is based on research from Stanford professors, Boneh, Lynn and Shacham (BLS)[6]. The signature scheme uses a bilinear pairing for verification and signatures shares are elements an elliptic curve group. These signature shares have 2 profound properties. First is if enough of these signature shares are gathered passed a threshold, the signature shares form a signature aggregate that’s publicly verifiable:
If m is the message, and H(m) is the hashed message, then H(m) signed by private key g^x produces signature σ. It is verifiable that e(σ, g) = e(H(m), g^x).
If enough of these signature shares are gathered passed a threshold, the signature shares form a signature aggregate that’s publicly verifiable
The next important property this signature scheme yields is that the aggregated signature is a random number. The BLS signature scheme is fundamentally a consensus protocol — multiple miners sign the same message and generate an aggregate signature that is a deterministic random number. This makes it a perfect seed for a lottery or casino styled game. This consensus protocol is also also fairly fast, allowing consensus to be reached every 5 seconds, since all a block needs to do is sign the hashed message H(m) with its private key g^x.
This signature scheme yields is that the aggregated signature is a random number since there is no way to predict it beforehand
The greatest advantage of all, is that the BLS signature scheme gives the UltraYOLO team a means to roll out its own blockchain with randomness built into the core of the protocol, which the team coins “Proof-of-Randomness” (PoR). In PoR, randomness is not a second-class citizen. It is not the type of pseudo-randomness that is built on top of other platforms. The UltraYOLO platform is built specifically for fast random number generation for lotteries and games. The integrity of the protocol will be guaranteed by its own network using the “UltraYOLO-styled” Masternodes. Each node will have a key-share and generate a signature share that is part of the final consensus and final random number. PoR will be the state-of-the-art protocol for lottery and gaming on the blockchain.
Proof-of-Randomness Implementation
In terms of implementation, the main focus will be on initial key distribution and facilitating the signing of messages. Fortunately, much research has been done by the Dfinity team. The Dfinity team is attempting to embrace a challenge far more ambitious than lottery games - they are attempting to leverage this BLS signature scheme to implement services like Uber, Google and AirBnB on the blockchain. They are designing systems such as “Blockchain Nervous Systems” and “validation trees”. Their work on the BLS signature scheme and threshold relay is used extensively by the UltraYOLO team. A more detailed technical implementation will be discussed in a separate article.
The purpose of this article is to discuss outstanding methods of random number generation on the blockchain. Among Blockhash, Oraclize, RanDAO, State Channels and BLS Signature Scheme, BLS is the clear winner. It is a state-of-the-art technology published in 2003[6] and is the basis of the technology developed by the UltraYOLO team. In a following article, we will discuss the implementation details, our research, and the UltraYOLO product roadmap.
Please stay tuned for our next post.
References
[1] Bitcoin Could Consume as Much Electricity as Denmark by 2020 https://goo.gl/PfroXE
[2] Ethereum Lottery Main Page https://ethereumlottery.io/
[3] The random datasource — chapter 2: OraclizeIt Blog https://blog.oraclize.it/the-random-datasource-chapter-2-779946e54f49
[4] Software vs Hardware RNGs: http://www.tstglobal.com/assets/downloads/1268986797a16.pdf
[5] RanDAO: Github https://github.com/randao/randao
[6] Short signatures from the Weil pairing https://www.iacr.org/archive/asiacrypt2001/22480516.pdf
Note: A cryptography expert on the UltraYOLO team clarifies that a truly random number cannot be “deterministic”. Thus, the random number that BLS signature generates could be understood as a NP-hard number that is not predictable. However, this has the same effect as a random number for all intents and purposes.
