Verification of Contract Execution

I believe there may be a weakness in ethereum with the verification of the contract execution. Currently, the only way to verify the execution of a contract is to re-execute the contract.

Let's say there is a rouge miner we think is improperly executing contract code. The miner's execution of any contract seems to always produce transactions that send ether to the same address. As a peer miner, I want to verify this miner's contract execution and resulting transactions. Otherwise, a block that I mint may not be accepted by other miners because it contains invalid transactions. So not only do I have to fully execute the contract, but every miner on the network must also execute the contract to validate my block.

A similar weakness is also present in bitcoin where miners must execute transactions to verify them. However, because bitcoin script is not turing complete there is an upper bound on the time it takes to verify a transaction (max number of instructions in a transaction). But if ethereum is turing complete, there is no upper bound other than the contract's balance. As I pointed out in another post (http://forum.ethereum.org/discussion/485/alternative-to-the-stack-machine-design), the fees may not be a strong enough tool to prevent DDOS attack contracts.

In order to fix this imbalance there would need to be a way for a miner to verify the execution of a contract without re-execution. And the verification run must be bounded.

Probabilistically checkable proofs (http://en.wikipedia.org/wiki/Probabilistically_checkable_proof) provides a foundation on how to build such a verification system into ethereum. And this group's (http://www.scipr-lab.org/) research on SNARKs looks to be very applicable to the verification problem, their latest paper (http://eprint.iacr.org/2013/879.pdf) in particular.

Comments

  • omtalkomtalk Member Posts: 1
    Has this been addressed? This question has been bothering me since a while. What stops a rouge miner to push an invalid transaction in a block? I see no other way than to re-execute the transaction, but that would mean that all or at least 51% miners need to execute a transaction in order to validate it.
  • o0ragman0oo0ragman0o Member, Moderator Posts: 1,253 mod
    @omtalk This was posted 3 years ago, when the protocol itself was still being conceived.
    Ethereum now definitely relies on all nodes verifying each transaction, i.e rerunning all transactions and check them against the new block. Turing complete DOS attacks (i.e. endless loops) are denied by the gas mechanism which forces halting regardless of what the code does.

    The idea of using zk-SNARKs for execution proofs is I think a very tantalising idea. I have no idea whether this is being researched.
Sign In or Register to comment.