RNG in contracts.

Haposhi

This is more to reassure myself than anything else, but I didn't see anything about the RNG in the whitepaper.

It seems obvious to me that in order to prevent miners from cheating the RNG, any randomisation used for contracts will have to be based on something the miners cannot manipulate, meaning they cannot affect the result, or know it ahead of time.

As the block has to be verified by everyone, the RNG result has to be deterministic.

The best seed I can think of is the hash of the block. The miner will have spent a long time trying to make a valid block, so they are unlikely to discard this work and try again so that they can have a shot at rerolling the RNG.

The problem with this is that the contents of the block will depend on the results of the RNG roll, because of the effects on contract memory. This creates a recursive loop which is unsolvable.

One solution would be to use the hash of a sub-block for the PoW, where any transactions that use the RNG are excluded. The hash from this sub-block is used as a seed for the RNG to work out the remaining transactions. The whole block is then hashed for verification, but without a difficulty target.

I'm sure something clever is already in the works, but it would be nice to know what.

VitalikButerin

The best source of randomness there is right now is the hash of the parent block, which contracts have access to. We may also consider making the nonce accessible if that proves useful. If you want to implement gambling protocols, the other approach is to require multiple parties to put in numbers, using a commitment scheme (ie. put in H(n[i]) first then n[i]) to ensure honesty, and XORing or modular-adding them together.

Haposhi

Thanks, vitalik.

The commitment scheme should be easy to implement, but it may be limited in suitable uses.

An inbuilt RNG function using the parent block hash would be good, but I think it should include the nonce for the current block. If this isn't done, people will know the outcome of a roll, providing that it occurs in the next block. Miners could place a bet when the parent block meant that they would win if they minted the next block, which seems unfair. If the nonce is included in the seed, this shouldn't be a factor.

phoenix

But if the nonce is used, then the miners have to redo the calculations every time they try a different nonce, since the hash of the block will depend on what happens in the contract.

Haposhi

Good point. I can't think of a good solution right now, other than the awkward split block idea.

Perhaps if transactions were time stamped in some way, say with a hash of the parent block, it could be done where transactions couldn't be included in a block until 1 block after they were created. This would mean that miners couldn't create a transaction that would win a roll based on the current parent block. They would have to create the transaction, and after 1 block they could use it, but the parent block hash would have changed in the meantime. I suppose they could create several transactions ahead of time, and include the one that would let them win, but I don't know if this would be feasible.

phoenix

Maybe you could delay the reaction to a given transaction? So somebody sends a transaction, and the contract makes a note to execute a command in the next block, and the rng could be seeded by the hash of the block that the transaction was first included in. This would make it harder for miners to manipulate the outcomes, but they still could pull it off if they tried

Haposhi

Excellent, thank you. That is as good as a hash requiring the nonce from the submitted block, but doesn't require the basic block signing to be changed.
A contract can only act when a transaction is sent to it though. It would have to wait until it was reactivated, but could look back at the hash of the block from the one after it was submitted.

phoenix

>A contract can only act when a transaction is sent to it though
This would make things more complicated if the contract wasn't extremely popular. Perhaps the first transaction could trigger the contract to send a transaction to activate another contract, which then immediately sends the transaction back the the first contract, which knows that any transactions from the second contract are only for the purpose of activating it, and don't need to be responded to. Since each transaction would take one block to occur, this would ensure that the contract would respond within 3 blocks. This is probably more complicated than necessary, but it could work

Haposhi

The contract could send itself a transaction if there was a 1 block delay. If not, they would execute in the same block so the delay effect wouldn't work. Even if there were several contracts in a chain of communication, they could all execute in the same block if that's the way the system is implemented.

phoenix

This is true, the most efficient way to do this would depend on the implementation. I think there would be a one block delay, so the best method would probably be to have the contract send a transaction to itself. But we'll have to see how things are implemented

PokerPlayer

Here is a thought I am putting together:

In, for example, a profitable sustainable and fair poker environment that fosters and favors intelligent players AND with a mental poker implementation in which each player secretly and securely commits to their own trusted "random" number to create the random number that generates (for example) the deck permutation for a particular hand...

poker then becomes the foundation and security mechanism for the creation, the sustaining, and the securing of an RNG.

In other words you use the intelligence of a free poker market to sustain the integrity of a fair deal, and a fair deal contains always effectively random numbers.

Jasper

Wrote this to refer to when this question comes up.. Not perfect though. You might think collaborating with miners might be difficult... issue is that someone might come up with a contract that somehow figures that out.

In short, use the block hash in a pre-determined future block, cryptographically commit random values; send sha3(R) initially, and R later, or have a RANDAO do that for you.