RANDAO: A DAO working as RNG

tomliontomlion ShanghaiMember Posts: 10
edited April 2015 in Smart Contracts and Dapps
https://github.com/tomlion/randao/blob/master/README.en.md

Feedback is welcome!
I'm grateful for any help making better expression of this article!

--------------------------------------------

Random number in programming is very important!

RNG in a deterministic system is very difficult.

Miners can't be trusted!

Solutions:

A DAO that anyone can participate, and the random number is generated by all participants together!
First of all, we need to create a RANDAO contract in the blockchain, which defines the participation rules.
Then the basic process of generating a random number can be divided into three phases:

The first phase: collecting valid sha3(s)

Anyone who want to participate in the random number generation needs to send a transaction to the contract C with m ETH as pledge in a specified time period (e.g, 6 block period, approximately 72s), accompanied by the result of sha3(s), s is the secret number respective picked by participant.

The second phase: collecting valid s

After the first phase, anyone who comitted sha3(s) successfully needs to send a transaction with the secret number s in the first stage to contract C in a specified time period. Contract C will check if s is valid by running sha3 against s and comparing the result with previous committed data. Valid s will be saved to the collection of seeds to finally generate the random number.

The third phase: calculating a random number, refund pledged ETH and bonus

After completion of the collection of all secret numbers, contract C will calculate the random number from the function f(s1,s2,...,sn), the result will be written to the storage of C, and the result will be send to all other contracts that request to the random number before.
Contract C will send back the pledge to the participants in the first phase, and the profit divided into equal parts will be sent to all participants as bonus too. The profit comes from the fees that payed by other contracts that consume the random number.

Additional rules

In order to ensure the RNG can't be manipulated, and considering the safety and efficiency, the contract C has following additional rules:

1. The first phase, if two or more same sha3(s) are committed in sequence, only accept the first one.
2. The first phase, there is a requirement for minimum number of participants, if it fails to collect enough sha3(s) within the time period, then RNG at this block height will fail.
3. If a participant commit the sha3(s) and it accepted by contract C, he must reveal the s in the second phase.
3.1 If the participant fails to reveal s in the second phase, then the m ETH sent in the first phase will be confiscated, no return.
3.2 If one or more s isn't revealed in the second phase, RNG at this block height will fail. Confiscated ETHs will be divided equally and send to other participants who revealed s at the second phase. The fees paid by other contracts will be refund.

Incentive

RNG cycle is very short, let's say 20 cycles in one hour, if one cycle's profit is 0.001% , the monthly rate of return is up to 0.00001 * 20 * 24 * 30 = 0.144. Targeting to 14.4% monthly rate of return, and RNG has n participants in average, the running costs of contract is n * 3 * 500 * gasPrice + Ccost. (Ccost is gas consumed by contract internally, including computing and storage, etc. ) Assuming each random numbers has r time requests in average, the call price is p ETH, the income is r * p. So each participant will get (rp - 1500n * gasPrice - Ccost) / n from one time participation. The current gasPrice is 10 szabo, and estimate of contract consumption is 1500n gas, so estimate of net income is (rp / n - 0.03) ETH. Assuming each RNG has 10 participation, and the pledge is 1000ETH, the minimum required income is 0.4 ETH, which over 0.001% profit in this case. So if the RNG requested only once, the service price is 0.4 ETH, and if it is requested 10 times, the price is just 0.04 ETH each request.

The RANDAO acts as an infrastructure in Ethereum system. It called by other contracts. Contract for different purposes require different random numbers: some need high security, such as lottery; some need stable and timely, the request should be responded immediately, these contracts normally do not involve with interest; some need a callback, they want to receive a notification with random numbers when numbers are ready.

Obviously it's impossible to meet different requirements in various scenarios with only one RNG contract, so a lot of contracts will be created with different initial parameters, but the basic rules are same.

For example, if we need high security, we can substantially increase the pledge of the first phase. Thus, the cost to lead to failure of RNG process by not revealing s is greatly increased. And for the contracts without much interest involved, the minimum number of participants and the ledge can be lower.

Let's say a dApp betting on odd or even of a number, we'll show how to adjust contract's parameters to meet the desired security level, by making the cost of cheating higher than expected earning. Assuming the bet is 1000 ETH, the betting contract calls RNG contract C1, if C1 failed to generate random number at requested block height, then betting contract waits for the next random number of C1, until there is one generated.

Let's build the RNG contract C1, and pledged ETH of C1 is 2000. The gambler G plays betting dApp also participates in contract C1. When he finds himself in a disadvantageous position before he reveals his secret number, he can choose not to reveal s, so that the RNG failed and he got another chance. But he will lost 2000 pledged ETH, although he can get 1000 ETH expected return, it is still a bad deal. However, G can reduce loss on C1 by some means, such as participates in C1 using two accounts, sending two sha3(s). if in a disadvantageous position, G will keep only one account's secret, and if only one participant expect G participate in C1, G will only lose 1000 ETH in C1, but G will get 1000 ETH as expected return, which is a worthy try.

It can be fixed up by confiscating the pledged ETH, and not returns them to participants as bonus. so a contract with 1000 pledged ETH will meet the requirement of betting dApp.

Besides confiscation, another scheme can prevent such attacks by introducing an additional system: RANDAO membership. To become a member you must pay dues, anyone paid their dues is a member. Members have different levels according to the dues they paid. Membership does not belong to a contract, but are passport to participate in some RANDAO contracts. If breach of any contract happens, that person's membership will be ended and the dues will be confiscated. Now we can add an additional agreement to C1, C1 will only accept numbers committed by members whose level are high enough (membership dues over 1000 ETH). This will ensure that nobody has motive to attack.

QA:

Q: Why not let the miners participate in RNG? Why not use tx hash, nonce and other blockchain data?
A: Miners have the ability to manipulate these blockchain data, and thus can indirectly affect RNG. If RNG contains blockchain data, it will give the miners capacity to construct random numbers in their favor.

Q: the miners can ignore certain transactions that contain random number they dislike, how to deal with that?
A: That's why we need a time window period. A reasonable period should be greater than 6 blocks, we believe that nobody can produce 6 blocks in succession. So if the participant is honest, and he send numbers immediately as long as each time window open, he doesn't need to worry about being excluded.

Q: Why use all numbers of all participants, rather than a subset?
A: The rule to pick a subset is deterministic, so participants will try to take specified position of the collection by various means, if they succeed, they will know in advance what the random number is generating from subsets. If the rule to pick a subset is randomisation, we can not ..., uh, how to pick a subset randomly?

Q: Where pledged dues go?
A: It will be donated to a charity, or RANDAO as maintain funding.

Note: f(s1, s2, ..., sn) is a function with multiple inputs, for example r = s1 xor s2 xor s3 ... xor sn, or r = sha3(sn + sha3(sn-1 + ... (sha3(s2 + s1))))

Comments

  • StephanTualStephanTual mod London, EnglandMember, Moderator Posts: 1,282 mod
    Nice to see an early draft of something like this in .sol - good work Youcai!
  • tomliontomlion ShanghaiMember Posts: 10
    Thanks for encouragement, Stephan!

    I'm writing .sol, there is a lot to do in my plan, a Dapp for beginners and a bot for professionals, but first of all, I need enough feedbacks.

    AMA and I will make it better.
  • darkmatterdarkmatter mod Member Posts: 12 mod
    This is interesting. Have you tried constructing a proof and analysis of this processes randomness? Another thing to look into would be some of these blockchain dice sites which have used clever ways to find in-chain pseudorandomness.
  • tomliontomlion ShanghaiMember Posts: 10
    Hi Darkmatter, it's still under discussion and I have wrote codes a little.

    Can these in-chain pseudorandomness be affected by miners? If so, the RNG built on that can't be used in lottery.
  • TalkingAntColonyTalkingAntColony Member Posts: 9
    tomlion, if you believe no miner(s) can produce 6 blocks in a row, why is RANDAO better than the following scheme:

    Blockheight t0: contract call needs random number, enters wait period
    Blockheight t0 + 6: contract wake function is called, calculates random number as the sha3 of XOR'ed sha3'ed blockhashes:
    sha3(sha3(block.blockhash[t0])^sha3(block.blockhash[t0+1])^...sha3(block.blockhash[t0+5]))
  • MarioFortierMarioFortier Boston, MAMember Posts: 30
    edited April 2015

    tomlion, if you believe no miner(s) can produce 6 blocks in a row, why is RANDAO better than the following scheme:

    Blockheight t0: contract call needs random number, enters wait period
    Blockheight t0 + 6: contract wake function is called, calculates random number as the sha3 of XOR'ed sha3'ed blockhashes:
    sha3(sha3(block.blockhash[t0])^sha3(block.blockhash[t0+1])^...sha3(block.blockhash[t0+5]))

    With this scheme the end result can be manipulated by the miner at t0 + 6 (at low, but not null probability). It does not matter how you combine with previous hashes, the last hash submitted has a final say on the generated number.

    With a proper commit/reveal scheme from multiple participant... the end result cannot be manipulated by the hash submitted at a single particular block.
  • tomliontomlion ShanghaiMember Posts: 10
    Yes, there is always a last miner if we use blocks data, although he can't determine what the random number is, but he has a chance to not submit result that may let him lost in a lottery.

    If he bet a lot in that lottery, and he didn't submit his result, it equals he earned another chance but the cost is only mining reward.

    The same manipulation exists even in commit/reveal scheme. The participant intent to not submit if his lost in a game is bigger than the pledge.
  • TalkingAntColonyTalkingAntColony Member Posts: 9
    interesting, so why do you have to throw away a whole round of secret collection if someone doesnt reveal theirs? Why not calculate the random num only from those who do reveal? For example, min submissions is 5. 10 people commit sha3s. Then only 5 people reveal s. Since it meets the min submissions the random num is still calculated from the revealers. Otherwise, there seems to be a DoS attack whereby someone prevents a RANDAO contract from generating new numbers by witholding their s. Of course it would get expensive quickly, but there could be some financial incentive to do the attack.
  • tomliontomlion ShanghaiMember Posts: 10
    Same reason as previous, people will prefer not to reveal s, they watched the network traffic and sniffed other participants revealed s, and they will know the result even before the random number are actually generated and stored in the blockchain. The manipulation is easier if we use part of secret collection.

    The cost of DoS attack is high, they will lost their pledge. But if the incentive is high enough, it's still be possible. That's why there will be a lot RANDAO contracts but with different amount of ETH as pledge.

    The key point to the games like lottery is to limit the value that a random number backed, we need to change the game rules a bit to adapt to the security of the random number.
  • SmithgiftSmithgift Member Posts: 64
    I'm considering the possibilities of using randomness in an Ethereum game. Currently (it's very early in the design) the only randomness is directly taken from block hashes for solar system generation, on the basis that miners have better things to do than manipulate hashes to move around virtual rocks.

    Unfortunately, ship to ship combat seems inevitably more and more likely to be deterministic. There seems no good time to get the randomness.

    Suppose I get the random number immediately from wherever. The player can do exactly the same, and see if his attack will succeed to his satisfaction before committing.

    (In fact, this is why any RNG must never ever resolve in the same block as the initial request.)

    So I have to wait at least one block, so that the attacker can't change his mind after seeing the result. This may strain things a little, as the ships will have be locked in battle so that no ship can do inappropriate things before resolution. But so far it's acceptable.

    But when does it resolve? There needs to be enough randomness for a unique resolution of every battle in the game. If I just naively take the next blockhash, for example, then every battle will essentially use the exact same roll of the die. If the attacker "rolls" well, every attack everywhere goes well. This is too much.

    (I also realize now my system generation code is broken, because currently two systems made at the same time will be identical.)

    Or suppose I wait until there's enough randomness for everyone. This leads to potentially weird situation where players start battles deliberately to stall the resolution of other battles. Even resolving them one by one still allows players to start absurd numbers of pointless battles to lock some specific enemy ships in battle until the RNG can catch up.

    At least deterministic systems are clear, quick and fair. There's just no possible luck for either side.
  • SmithgiftSmithgift Member Posts: 64
    LATER ADDENDUM TO THE ABOVE:

    I realize it's possible to SHA3 one random seed with some relevant part of the roll, therefore getting new random numbers for the different rolls.
  • tomliontomlion ShanghaiMember Posts: 10
    The repo has been moved to https://github.com/randao/randao

    And I start to work on it again.

    There're some improvements but the basic idea is same.

    If you're interesting in it, please join the chat at gitter: https://gitter.im/randao/randao
Sign In or Register to comment.