Ethereum PRNG Challenge

ETHAppsETHApps Member Posts: 11
There has been a lot of discussion about the impossibility to generate secure randomness inside ethereum smart contracts, and general consensus is that theoretically miners could easily manipulate the results. But maybe it's worth to perform a small reality check... here comes the Ethereum PRNG Challenge!

PRNG_Challenge: 0x4ed65e408439a7f6459b5cfbd364f373bd6ed5f7

Balance of above contract is currently 10 ETH: when you send 0.1 ETH or more to it (with a gas limit of 100000, unused gas will be returned) a 256 bit random number generator is triggered, and if the generated value matches with a predefined lucky number the entire balance is paid back.

Let's see if someone manage to cash it out, of course there's always a very small probability of hitting the correct number out of pure luck (theoretically 1 out of 10^77 - the entire universe is estimated to contain about 10^80 atoms).

Here you can check the source code and interact with the contract:

PRNG_Challenge: 0x4ed65e408439a7f6459b5cfbd364f373bd6ed5f7
https://live.ether.camp/account/4ed65e408439a7f6459b5cfbd364f373bd6ed5f7
https://etherscan.io/address/0x4ed65e408439a7f6459b5cfbd364f373bd6ed5f7
https://etherchain.org/account/0x4ed65e408439a7f6459b5cfbd364f373bd6ed5f7

Interface:

[{"constant":true,"inputs":[],"name":"lucky_number","outputs":[{"name":"","type":"uint256"}],"type":"function"},{"constant":true,"inputs":[],"name":"attempts","outputs":[{"name":"","type":"uint256"}],"type":"function"},{"constant":true,"inputs":[],"name":"last_number","outputs":[{"name":"","type":"uint256"}],"type":"function"},{"constant":false,"inputs":[],"name":"admin_kill","outputs":[],"type":"function"},{"constant":true,"inputs":[],"name":"winner","outputs":[{"name":"","type":"address"}],"type":"function"},{"inputs":[],"type":"constructor"},{"anonymous":false,"inputs":[{"indexed":false,"name":"Participant","type":"address"},{"indexed":false,"name":"Number","type":"uint256"}],"name":"Attempt","type":"event"},{"anonymous":false,"inputs":[{"indexed":false,"name":"Winner_Address","type":"address"},{"indexed":false,"name":"Amount","type":"uint256"}],"name":"Winner","type":"event"}]
lucky_number(): returns the predefined lucky number.
last_number(): returns the last random number generated.
attempts(): returns the total number of attempts.
winner(): returns the winner address (if any).
Attempt(Participant, Number): event triggered at each attempt.
Winner(Winner_Address, Amount): event triggered in case of win.

Good luck! :)

Comments

  • ETHAppsETHApps Member Posts: 11
    10.1 ETH are still there... taking it as a good sign ;)
  • HippoClipHippoClip Member Posts: 16
    I am not sure if this test is very interesting.

    First of all, note that, essentially, what you are trying to do is make the miner try to guess a preimage of a specific hash function. It is not really surprising that no one has done that. Sha3 is not yet broken.

    Second, when talking about miners being able to influence a PRNG the problem is not necessarily that we are afraid that the miner has complete control over the output. Consider, for example, a contract implementing a coin flip. It would only need a single bit of the PRNG output, let say it uses the last bit. When generating the block determining an output of your PRNG the entropy sources are either fixed or can be manipulated by the miner (participant, participant.balance, block.timestamp, msg.value, block.number, all more or less fall into the later category). Thus by trail an error the miner could probably easily fix the last bit (or even the last few bits) of the PRNG output.
  • ETHAppsETHApps Member Posts: 11
    HippoClip said:


    Consider, for example, a contract implementing a coin flip. It would only need a single bit of the PRNG output, let say it uses the last bit. When generating the block determining an output of your PRNG the entropy sources are either fixed or can be manipulated by the miner (participant, participant.balance, block.timestamp, msg.value, block.number, all more or less fall into the later category). Thus by trail an error the miner could probably easily fix the last bit (or even the last few bits) of the PRNG output.

    Thanks for taking the the time to analyze it. Of course when the possible results are only 2, a miner can always discard the blocks leading to the result he don't like, at the end we are talking about a 50% probability of hitting the desired result in any case. I would not consider this a real and viable manipulation, it's more similar to a brute force attack on passwords for example.

    When the possible results are more than 2 (a lottery for example), this brute force attack is more and more time consuming... moreover the seeds of the hash are partially coming from the sender and partially from the miner, and this should add an additional layer of complexity
  • HippoClipHippoClip Member Posts: 16
    First of all, it does not matter that the seed is "partially coming from the sender and partially from the miner". A miner who wishes to influence the PRNG can make his own transaction using any address he generates himself as the sender. But that even is not very important, because there are other things in the seed the miner can choose more or less freely (like the timestamp).

    The problem is that using this the miner could win 100% of all coin flips and he never has to discard an otherwise valid block. In this case you would be much better off simply using the last bit of the current block (and no other values). To fix this bit would make it twice as hard for the miner to mine blocks. I.e., he would half his expected reward in mining which he is strongly motivated not to do.

    You may think that it does not matter if the miner can fix a single bit of your PRNG, but consider your own lottery example. If the miner can fix a single bit of the lottery outcome, that means that he is twice as likely to win than he is supposed to be. That can make a huge difference in whether or not your lottery is profitable.
  • ETHAppsETHApps Member Posts: 11
    HippoClip said:

    A miner who wishes to influence the PRNG can make his own transaction using any address he generates himself as the sender.

    Could you please elaborate on this? Is this similar to randomly generate private keys with the hope that related addresses are already used by someone (and with a good balance ;) )?
    HippoClip said:

    The problem is that using this the miner could win 100% of all coin flips and he never has to discard an otherwise valid block. In this case you would be much better off simply using the last bit of the current block (and no other values). To fix this bit would make it twice as hard for the miner to mine blocks. I.e., he would half his expected reward in mining which he is strongly motivated not to do.

    This is interesting. How can the miner influence least significant bit without discarding blocks with following logic:

    // Take least significant bit:
    sha3(msg.value,participant,participant.balance,block.blockhash(block.number-1),block.timestamp,block.number)

    But NOT (if I understood correctly) with following logic:

    // Take least significant bit:
    block.blockhash(block.number-1)

    Thanks!
  • drinkcoffee2016drinkcoffee2016 Member Posts: 5
    I agree with HippoClip, solving your contract requires breaking the pre-image resistance of SHA3.

    I think how a miner could influence the output "without discarding blocks" is this:

    The miner could on a trial basis include a transaction for the contract in the current block. If the output wasn't what they wanted, they could alter block.timestamp, moving the timestamp forwards or backwards a number of seconds. Once they had the value they were happy with, they could then attempt to mine that block.

    Another possible thing the miner could do is have many addresses. They could on a trial basis send transactions from all of the addresses to the contract. Given the address (participant) is included as an input to the PRNG, the miner could choose to mine a variant of the block which includes a transaction from an address which yielded the result that best suited them.

    See this link here for a discussion on the value of the block timestamp: http://ethereum.stackexchange.com/questions/413/can-a-contract-safely-rely-on-block-timestamp


    The big thing to reinforce is, the miner may not be able to guess the output value, but they will be able to influence it.
  • tad88devtad88dev Member Posts: 6
    If you keep the source code then no one going to trust you.
  • ETHAppsETHApps Member Posts: 11


    The miner could on a trial basis include a transaction for the contract in the current block. If the output wasn't what they wanted, they could alter block.timestamp, moving the timestamp forwards or backwards a number of seconds. Once they had the value they were happy with, they could then attempt to mine that block.

    How much time would the miner have for this brute force attack? Because if the possible outcomes are more than 2 (i.e. head/tails) maybe it's not so fast to find a winning combination.


    Another possible thing the miner could do is have many addresses. They could on a trial basis send transactions from all of the addresses to the contract. Given the address (participant) is included as an input to the PRNG, the miner could choose to mine a variant of the block which includes a transaction from an address which yielded the result that best suited them.

    You mean real transactions or simulated transactions, and then they can include in the block only the successful one? In any case they need to have a pool of addresses (with private keys) prepared in advance.
    tad88dev said:

    If you keep the source code then no one going to trust you.

    Not sure what you mean, source code is available and verified on both etherscan and etherchain.
  • tad88devtad88dev Member Posts: 6
    @ETHApps I have review source code, good developer but it isn't a good contract to deal. It's totally a fishing.
  • ETHAppsETHApps Member Posts: 11
    tad88dev said:

    @ETHApps I have review source code, good developer but it isn't a good contract to deal. It's totally a fishing.

    Clearly you didn't understood the aim of the contract. Review it again and, if still unclear, I suggest you to forget Solidity and go fishing for real ;)
  • HippoClipHippoClip Member Posts: 16
    ETHApps said:



    This is interesting. How can the miner influence least significant bit without discarding blocks with following logic:

    // Take least significant bit:
    sha3(msg.value,participant,participant.balance,block.blockhash(block.number-1),block.timestamp,block.number)

    But NOT (if I understood correctly) with following logic:

    // Take least significant bit:
    block.blockhash(block.number-1)

    Thanks!

    Lets say the miner wants the least significant bit to be 1.

    While mining the current block the miner can evaluate sha3(msg.value,participant,participant.balance,block.blockhash(block.number-1),block.timestamp,block.number) with as many values of, e.g., block.timestamp as he want untill he gets a result with least significant bit 1. He only has to try a very few time before this should succeed (expected 2 times). So he can do this very quickly! Much faster than it will take him to generate a valid block.

    However, in order to force block.blockhash(block.number-1) to have least significant bit 1 the miner needs to find a valid block with the least signigicant bit 1. Generating a valid block is hard and takes a long time (that is what the whole proof-of-work is about). If the first valid block he generates has least significant bit 0 he has to discard this block and start over. (or wait and try the attack on the next block).

    Just a quick question is "block.blockhash(block.number-1)" the blockhash of the current or the last block? I am just interested, it does not matter much for the argument above.
  • ETHAppsETHApps Member Posts: 11
    HippoClip said:

    However, in order to force block.blockhash(block.number-1) to have least significant bit 1 the miner needs to find a valid block with the least signigicant bit 1. Generating a valid block is hard and takes a long time (that is what the whole proof-of-work is about). If the first valid block he generates has least significant bit 0 he has to discard this block and start over. (or wait and try the attack on the next block).

    This is a textbook example of "less is more". Got it now.

    BUT (see below)...
    HippoClip said:

    Just a quick question is "block.blockhash(block.number-1)" the blockhash of the current or the last block? I am just interested, it does not matter much for the argument above.

    It's the previous block hash. The current block hash cannot be accessed, for the simple reason that it doesn't exist yet (the current transaction will be part of it).

    Does this change anything? I'm thinking that previous block hash is know to everyone in advance, maybe could the miner refuse to mine the transaction if not good for him?
Sign In or Register to comment.