how do you verify miners perform the correct calculations on contracts?

cobordismcobordism Member Posts: 6
Hi everyone,
I've been following ethereum since the very beginning silently. This is my first post. I am not a computer scientist, please bear this in mind when replying. thanks. -I am however a mathematician so feel free to get technical ;)

From the start I was confused as to how to assign ether/gas to contract execution. How do we determine how much computation something took? Surely there are many ways to calculate the same result? ... but nobody seemed to raise this issue so I put it down to my own inexperience.
But now I saw the recent blog post on long range attacks ( http://blog.ethereum.org/2014/05/15/long-range-attacks-the-serious-problem-with-adaptive-proof-of-work/ ) and this reawakened my question. The example given is instructive:

i = 0
while sha3(i) != 0x8ff5b6afea3c68b6cd68bd429b9b64a708fa2273a93ea9f9e3c763257affee1f:
i = i + 1

one way to solve this is brute force, the other is knowing the answer beforehand. There is no way to know how long someone took to solve this.

It has also been noted in discussions about "usefull POW" that we cannot use things like [email protected] or [email protected] or similar because we cannot easily verify the results without repeating the work entirely. It is not mathematical enough like sha256 or finding prime numbers is. So here is another question:

If we wanted to avoid the problem sketched above we might want to have everyone do the same calculations in-the-exact-same-way (this is how I understand the comment in the blog about "requiring a tree-hashed computational stack trace") but then are we not in [email protected] type territory where the only way to verify someone's work is to repeat it?
In bitcoin it takes long to find a block, but a new block's validity is quick to check. Here, how would I be able to check the validity of the work without repeating all of it?

Maybe I am getting POW confused with state transition or something, but can someone help clarify this in my head?

many thanks,

cobordism.

Comments

  • JasperJasper Eindhoven, the NetherlandsMember Posts: 514 ✭✭✭
    The transaction is valid if you have enough if the address sending the transaction has enough ether for the amount sent and the gas bought. If a transaction is valid, you will always pay the transaction fee, and call gas. Gas is turned back into ethers and refunded if not used.

    The message a transaction sends are valid if they do not run out of gas. If they do run out, the gas is not refunded,(protecting miners against attack) but otherwise the message is treated as if not sent.

    Infact the miners dont even need to run the contracts, of the block they intend to mine, because if they computed the contracts of the previous blocks, they know the balances, and can immediately check in the transactions are valid.

    So contract computations, are 'not part of PoW by default'. However, there was an idea to add it. And it has the problem with that 'secret for shortcut' idea. Now... actually you could consider it as an attack with normal contract execution too. What if a rich miner does this.. If he wins a block, he puts in this. He can calculate the outcome immediately, giving him a head start in mining the next block. However, it wouldnt work, because there is a maximum amount of gas that may be used in a block, and probably that amount of gas doesnt slow the other miners down enough. Still, i would prefer if at least part of the gas is not paid to the miner, so if the miner puts stuff like this in his own block, it is costly. (not sure what happens to gas right now..)
  • cobordismcobordism Member Posts: 6
    how do you know how much gas is required? Is it not possible that one miner will run out of gas executing a contract but another miner (executing the same contract) will not simply because they use different steps to perform the same calculation?

    If this cannot happen - for example because everyone has to perform all calculations in exactly the same way - then the question still remains, how do you verify a block without repeating the contract execution in full? And if a miner claims that this execution ran out of gas, or this execution left X gas to be refunded, how would you validate this without going through all the calculations again yourself?

    "Infact the miners dont even need to run the contracts, of the block they intend to mine, because if they computed the contracts of the previous blocks, they know the balances, and can immediately check in the transactions are valid." ---- This I do not understand at all. How can you mine a block without executing the contracts in it?

    sorry if I'm being dense.
    -c
  • JasperJasper Eindhoven, the NetherlandsMember Posts: 514 ✭✭✭
    You dont really know how much gas is required. You can simulate the transaction it or estimate it. Although if the message you are sending depends on some state that other messages may affect you cannot assume that wont happen. But you can send the maximum you expect, and just get it refunded if it doesnt use all the gas.

    All full nodes do do all computations! This is the No.1. problem in cryptocurrencies. The system is intended for computation with consensus, not high computation power.

    The whole system depends on full nodes, given the same block with the same transactions, doing all the computations identically.

    The block is essentially determined the same way as in Bitcoin. Miners basically have a competition, each attempt has a 'score' and if you score below a value, and all transactions on the block are valid and the signatures check out, then it is a valid transaction. The idea is that because the competition is hard, there will just be one block. If there are two the hardest(longest) one wins. Full nodes may then have to rewind and calculate the alternative chain if they find a harder one.

    The 'game' of the competition needs to have the property that it is different each block and each attempt. I.e. you cant re-use earlier information. Bitcoin and derivatives use checksums of a combination of nonce, so you change the nonce to find something with a low checksum; a high score. PoS use a combination of the pubkey, and the balance to score, so there hardware to find nonces dont help much. (and have to solve another problem to work, btw) Ethereum will actually probably do it a bit more complicated, also involving PoS.
    This I do not understand at all. How can you mine a block without executing the contracts in it?
    Because the validity of transactions does not depend on contract execution. If a correctly signed transaction comes from an pubkey with enough ethers to pay the gas and send the ethers it indicates, it is valid. (probably also comes with blocknumber/range)

    When the message of the transaction is run it may run out of gas, and have no effect other than burning the gas, but that is just an outcome of a valid act on the blockchain. (however wasteful that is for the guy that did it!) Of course, a miner does have to execute preceeding messages, because they may have consequences causing public keys not to have enough ethers.

    Hmm, though i know it to be possible, i am not entirely sure if it is implemented that way..
Sign In or Register to comment.