LLL question: Random number function?

mode80mode80 ✭✭Member Posts: 64 ✭✭
For fun and practice I want to build a contract that picks a number between 1 and 100, and give a sender their ether back if they can guess it in 7 tries.

I'm quite sure I don't understand enough to know if this is possible, but that's my purpose for trying.

My first snag was generating a "random" number. There's an op-code for blk_nonce which sounds promising, but how is that op-code even possible?

Is that the nonce of the last block? It can't be the nonce of the "current" block -- unless it's the nonce for just the miner running this script, which might be different from miner to miner. But wouldn't that cause a blockchain fork if, for example, a script did something like "if blk_nonce is even then send ether to A, else send ether to B" ?

Clearly there's still big holes in my full understanding of all this. Basic questions for now:

- What is blk_nonce exactly?

- What other way might there be to get a secret random-like number?

Comments

  • mquandallemquandalle ✭✭ FranceMember Posts: 50 ✭✭
    It is unreasonable to trust a miner for choosing a random number. It is a bit better if you rely on the block (the `blk_nonce` as you say) but still, the miner is free to set the value he wants.

    I can't think of any solution for this problem right now.
  • mids106mids106 ✭✭✭ Member Posts: 188 ✭✭✭
    Potentially you can use block.parenthash (in combination with block.timestamp and block.coinbase?) as random number.
  • mquandallemquandalle ✭✭ FranceMember Posts: 50 ✭✭
    But at the time you execute the contract you don't know what it the `block.parenthash`.
  • IVI3T4LIVI3T4L Member Posts: 10
    I would really like to know how to do this also. Could one of the devs chime in. Since all nodes have to execute the code a random number could be generated, but you have a problem where all the nodes would come up with the same number which would mean the number is not random or it would be random and each nodes would have different results for the random number and the contract would act differently on each node. I could easily be missing something here, but a lot of my ideas depend on random numbers.
  • JasperJasper ✭✭✭ Eindhoven, the NetherlandsMember Posts: 514 ✭✭✭
    Future block hashes can be combined with some predetermined value to provide psuedorandom data.

    Afaik that should be fairly good psuedorandom data. *However* block miners could collude; hold back blocks that dont have the winner they want. It lowers their chance of winning a block, so it is costly, but then bets could have a lot at stake too.

    This can be prevented by both parties having a secret S1,S2, initially they reveal H(S1), H(S2), then they wait a block, which has a checksum H(B). After that the 'game' or program can use the number R=H(S1 ... S2 ... H(B)) as random. Since neither knew S1,S2 of the other side, neither can collude with miners to affect R.

    Still have a problem though, one of the two has to release the secret first, and the second one can then figure out what the result of the game is before he gives his secret. This can be fixed by giving forfeitures at this point the 'maximum loss' in the game, and having a time frame for the players to respond.(presumably they can get their transactions in a block by that time)
  • JasperJasper ✭✭✭ Eindhoven, the NetherlandsMember Posts: 514 ✭✭✭
    Btw; better solutions(or point out i am wrong, obviously) would be appreciated, i mean this takes a bunch of steps, and it would be better if you could just call `random()`.
  • chris613chris613 ✭✭ Member Posts: 93 ✭✭
    @mode80? several people have chimed in about random numbers, and I think Jasper is closest to a good answer on that. No one has answered your first question, though.

    "What is blk_nonce exactly?"

    From a reasonably up-to-date version of the source code we see this in VM.h (this is the "code and builds" forum after all ;)

    case Instruction::BLK_NONCE:
    m_stack.push_back(_ext.previousBlock.nonce);

    This is clearly the nonce of the previous block. In case the naming is just wonky (which it is, actually), here is some related code:

    case Instruction::BLK_PREVHASH:
    m_stack.push_back(_ext.previousBlock.hash);
    break;
    case Instruction::BLK_COINBASE:
    m_stack.push_back((u160)_ext.currentBlock.coinbaseAddress);
    break;
    case Instruction::BLK_TIMESTAMP:
    m_stack.push_back(_ext.currentBlock.timestamp);
    break;
    case Instruction::BLK_DIFFICULTY:
    m_stack.push_back(_ext.currentBlock.difficulty);

    So we can see that most of the BLK_ functions are referencing the current block, except for BLK_PREVHASH and BLK_NONCE. I would suggest that BLK_NONCE should really be BLK_PREVNONCE.

    That's the pragmatic answer. You already hit on the theoretical answer via reductio ad absurdum with your question of "how is that op-code even possible?". It's not possible, it has to refer to the previous block.
  • JasperJasper ✭✭✭ Eindhoven, the NetherlandsMember Posts: 514 ✭✭✭
    PoW miners change the nonce, which changes the checksum, and the checksum is related to the score which determines which block wins.(for good reasons Ethereum not plain PoW based)

    It probably refers to the previous nonce so that miners dont have to re-run the code every nonce. The code would have run again because the outcome might change with the nonce, and other full-nodes(and miners) dont accept invalidly run code. (Another use of nonces is against replay attacks, but not here, afaik)

    I agree on that the naming should be BLK_PREVNONCE.
  • mode80mode80 ✭✭ Member Posts: 64 ✭✭
    Thanks. Chris, it seems you're right that BLK_NONCE is really the nonce of the previous block.

    On the larger question of how to get a random number... At first I thought the design would make this impossible on the understanding that different miners running the script with different random numbers would create blockchain forks. But that kind of fork is short-lived and anticipated -- the miner who "wins" the block will also have picked the "winning" random number.

    So I'm back to thinking that a rand() function should be theoretically possible, but I haven't determined how to make one with what's currently available.
  • IVI3T4LIVI3T4L Member Posts: 10
    mode80: while i agree that what you are saying will work if we could trust that each miner would really generate their own random number and wouldn't just create a number that may benefit them if they had a reason to do so. It could be possible that a miner or pool of miners decides that they dont like the contract for whatever reason and calculate which nonrandom number would cause the contract to loose more money and generate that number.

    I think as the network grows this problem may be minimized since there will be so many people mining that it would be difficult to mine the block that benefits the transaction that ran the contract that the "untrustworthy" miner will try to give a non random number to. Even though it will be very difficult it would be nice if we had a full proof verifiable random number generator for our contracts.
  • JasperJasper ✭✭✭ Eindhoven, the NetherlandsMember Posts: 514 ✭✭✭
    Getting psuedorandom values that dont split the blockchain isnt the problem.

    The problem, using a single transaction is that the psuedorandom values are predicatable. Everyone can see how it would turn out, because the random seed(likely block.hash) is known by anyone.

    With two transactions, you can fix it; you could have a 'lottery script' where you buy a ticket, it stores X=H(block.hash .. sender.addr), Y=block.number, then later, if someone pokes it to execute, it can use R= H(X ... blocks_list[Y+5].hash) can be used as random seeds.

    But that one has the problem that miners can affect it. However, only at the cost of not using winning blocks. I'll try to figure out what sort of amounts of bets, and if many tiny bets are also cheatable later..

    And that problem finally is solved by parties deciding on secrets beforehand. Thing that can still be done with just two transactions. If trust is one-way, only one side has to choose a secret. Problem is that i dont think scripts have secrets. Someone would have to run one on a centralized computer somewhere to supply proof-of-secret and the secrets as people come in.
  • kittenkitten Member Posts: 6
    I agree that being able to call random() would be much easier. There's a nice stackexchange question about this here: http://crypto.stackexchange.com/questions/1858/is-there-some-way-to-generate-a-non-predictable-random-number-in-a-decentralised
  • giactgiact Milan, ItalyMember Posts: 5
    I was also pondering about how to best simulate a pseudo-random "dice roll" within a contract.

    The best solution I came up with involves two messages to the contract:

    1. User picks a (possibly huge) random number "A".
    2. User sends message #1 to the contract, containing a cryptographic commitment to the number he just rolled.
    3. Contract stores the user's commitment
    4. Contract computes a pseudo-random number "B" using prevhash and timestamp and coinbase as seed.
    5. Contract stores that pseudo-random number next to the user's commitment.
    6. User send message #2 to the contract, sending the number "A" he initially picked.
    7. Contract verifies that the number "A" the user sent conforms to his previous commitment and uses it together with "B" to compute a random number "C".

    The only problems I can see are:

    1. The user can know the final random number BEFORE he can send message #2, and thus can abort the protocol at that points.
    2. If the user has enough mining power, he can cheat by trying to mine a solution with a coinbase and timestamp so that the resulting random number "C" is favorable to him.
  • mids106mids106 ✭✭✭ Member Posts: 188 ✭✭✭
    See how Dennis has implemented random numbers in his Lottery with a 10 block pre-commit:
    https://github.com/dennismckinnon/Ethereum-Contracts/blob/master/Dennys Lotto/Lottery.lsp#L45
  • JasperJasper ✭✭✭ Eindhoven, the NetherlandsMember Posts: 514 ✭✭✭
    @giact that is exactly what i basically mentioned(here); H(S1), H(S2) are cryptographic commitments for two betting parties.

    You can have a single party give crypto commitments, or both, whoever gives commitments is protected, if it is ensured that forfeitures(never providing your secret) are not to the forfeitings' side benefit.

    Contracts themselves cannot really protect themselves against miner collusion, though perhaps they can solicit help from non-contract parties.
  • JasperJasper ✭✭✭ Eindhoven, the NetherlandsMember Posts: 514 ✭✭✭
    Feel a bit stupid, i dont entirely understand the linked github code. (LLL docs on the wiki disappeared too) Dont see how it solves all problems though. (what are the @ symbols for?)

    Contracts are callable now, so a contract could aim to be a random function. If you can get a single contract to have a psuedorandom function, that cannot be predicted or affected, we have our random function without fuss. That was true when it was EXTRO too, i suppose, although now the contract can get paid for such a service.
  • mode80mode80 ✭✭ Member Posts: 64 ✭✭
    @1 expands to (mload 1)
    @2 expands to (sload 2)
    there's also [1] 0xa and [[2]] 0xb for (mstore 1 0xa) and (sstore 2 0xb) respectively, but I find readability suffers quickly when using those.

    see https://github.com/ethereum/cpp-ethereum/wiki/LLL-PoC-4
    and https://github.com/ethereum/cpp-ethereum/wiki/LLL-Examples-for-PoC-4
  • FrankHoldFrankHold Member Posts: 15
    Hi, if I understand it correctly the block chain is deterministic and slow. Therefore a user can always calculate the ‘random’ number before he acts.

    I think it is necessary to think outside the box to find a solution. On is to have a ‘trusted’ source outside ethereum.

    But what if, we had a second block chain, which is very quick. This chain could be used to provide as example a timestamp. Therefore if the timestamp is not provided by the miner it could be used to create as seed number for the contract.
  • JasperJasper ✭✭✭ Eindhoven, the NetherlandsMember Posts: 514 ✭✭✭
    Future prevhashes! Ohnoes miner collusion! Commitments H(R) by parties! Too much work! RANDAO!
  • FrankHoldFrankHold Member Posts: 15
    Thank you for your responds! The randao approach is the closed solution I have yet seen. As described "last person to submit" is the problem he can calculate the random number and decide not to send his number.

    This would be no big deal, except if he would know which contract requested the number. With the contract he can calculate beforehand whatever the contract will do.
Sign In or Register to comment.