EOSCommunity.org Forums

Random Number Generator

#1

The idea below is one that has been imagined and conceptualized by several members of our team and with this forum becoming more widely used and our “Uncategorized” category still missing it’s first post, I figured that now would be a good time to share a simple post that I wrote about it a while back.

With the rise of Decentralized Application platforms such as EOS, one can imagine that having a reliable source of random numbers would be useful. After all, a lot of the apps in use today need to have a way to generate random numbers in order to function.

However, developing a way to generate random numbers reliably is much more of a challenge than one might think. With the following article, we will attempt to explain these challenges and then propose a system that overcomes them. It is our hope that this system, or a similar one, will be adopted by the EOSIO community as we believe that it will increase the chances of crypto mass-adoption.

This article makes the assumption that the reader understands:

  • The general idea of how smart contracts work and how they are executed on a DPOS-based Blockchain;
  • The role that Random Number Generators play in many modern high-traffic apps, such as gambling apps and some video games;
  • The implications of not having a truly random outcome when playing dApp games on a decentralized Smart-Contract platform.

Nomenclature:

  • Centralized: Which is controlled solely by a single entity or company.

  • Decentralized: Which is not controlled in any way by a single entity or company.

  • Random Number: A number for which the value was not determined or influenced by any single party.

  • Seed Numbers: Numbers that are used to generate a random number.

The Challenge

As mentioned above, a big number of modern applications have a random component to them however to generate true random outcomes is not an easy task. To illustrate this, let us look at one of the simplest application examples that we can think of. A dice game where two players (players A and B) who do not know nor trust each other wish to bet on a dice rolling outcome. A simple way to build such an application is to let both players select a dice number and let a trusted third party keep track of the bets and decide what the winning roll of the dice should be for each round. That is essentially how the great majority of applications such as this one have been functioning for a while now. The result here is a centralized system where a lot of power is given to that third party entity.

If we wanted the above process to be decentralized though, a different mechanism would need to be used. For the above example, a smart contract could be conceived to let both players contribute number seeds by each committing a hash of a number while they place their bet. Then once both hashes have been committed, both players can reveal their respective numbers that can then be used by the smart contract to determine the outcome of the roll of dice. This will probably work fine since, assuming that both players are not working together, player A will not be able to affect the outcome as he does not know the number that player B will reveal, and vice-versa. The result is therefore a random number.

The above scenario had two players directly competing against each other at the same instant that were able to provide number seeds. However, this is not always the case. To illustrate this, let us take the example of an on-chain lottery system. Let’s imagine a system where participants would be able to buy lottery numbers during a certain period of time, at the end of which, a winning number would be revealed and the funds would be automatically transferred to whoever selected the correct number. In this case, we cannot count on user-provided number seeds like in the last example and we therefore need a third party mechanism to generate random numbers for us.

One solution for this that is being widely adopted in the Blockchain community is the Signidice Algorithm which essentially works by having both the player and the smart contract owner sign a transaction and using the resulting signature to determine the outcome. The following strategy is efficient and might be good enough for a big number of dApps, however it assumes that the contract owner and the player are not working together which we believe is not an assumption that one can always make.

Our Solution

We propose a smart contract that can be deployed to any EOSIO Blockchain and that would allow oracles to contribute number seeds at whichever interval they want to. The contract would make randomly generated numbers available directly on-chain which would make them directly usable by third-party contracts. For simplicity, this contract will be referred to as the RNG contract in the rest of this article.

The process for an oracle to contribute number seeds would be as follows:

  1. An account would register as an oracle on the RNG contract.
  2. An interval of time after having registered, the oracle would be allowed to start committing numbers.
  3. At whichever interval he chooses, the oracle would commit:
    • A hash of a 64-bit integer salted with a 64-bit representation of the oracle’s account name.
    • A three seconds reveal period during which the integer will be revealed.
  4. During the reveal period, the oracle will then reveal the number allowing him to commit a new number and therefore restarting the cycle.
  5. If the oracle fails to reveal during the predefined period, he will be banned from committing numbers for a period of time. That period of time will get longer every time he doesn’t reveal a committed number.

All the revealed numbers of a given period are used to compute a random number which is added to a table. If more than a certain number of oracles have participated, then the random number for that period is flagged as valid and can be used by any third-party contract (like the lottery contract that we imagined in the above example).

We believe that these three conditions are required to make such a system robust:

  1. The reveal period must be short. The reveal period cannot be too long. If it was, it would be much easier for a dishonest oracle to always wait until all the other oracles have revealed their numbers and then decide if they want to reveal or not. We can imagine scenarios where if an oracle is also placing bets on a third-party contract, then he would be at an advantage in that situation.

  2. The oracles must be punished for not revealing. As previously mentioned, we can reduce the risk of a dishonest oracle revealing after everyone else by reducing the reveal period length. However, being that transactions can take a second or two to be broadcasted, it would be challenging to make the period length shorter than three seconds as it might result in some oracles missing their reveal time. This means that although it might be difficult, an oracle located close to a node geographically could still be in a position to affect the outcome to his advantage by being the last to reveal. To make it unlikely that an oracle would attempt the above process, we propose to punish oracles that miss a reveal period. This is done by preventing them from recommitting for a certain period of time and making that amount of time longer every time they repeat the infraction.

  3. The contract must generate a huge number of possible random numbers (using int64 with salting). Another thing to consider is that because the oracles use hashes to commit to numbers before revealing them, the number of possible generated numbers has to be very high. If not, someone could use a rainbow table to map each possible number to a hash and just do a simple table lookup to know what number each oracle is about to reveal before everyone else. Because of this, we propose using an int64 data type for the seed numbers. Furthermore, we propose to use the user’s 64 bit account name as a salt. This would mean that a bad actor would need to have 4.25e+28 Gigabytes of storage space available to be able to host the required rainbow table, making it basically impossible.

To conclude, we believe that our solution will be a welcome addition to the EOSIO ecosystem and that it’s usage will make third-party smart contracts more decentralized and therefore safer. We invite anyone that is interested, to take a look at an alpha version of the RNG smart contract described above on github.

Please let us know your thoughts by leaving some comments below.

2 Likes