TrueBit - Off-Chain Computations for Smart Contracts

Tough Tasks for Smart Contracts

How does an Ethereum Smart Contract

• Verify Solidity source code?
• Retrieve data stored in swarm?
• Verify state transition in private chain?
• Become conscious?

All these operations need access to the "external world" or are very expensive.

TrueBit - the Verification Game

Cooperation with Loi Luu (U. Singapore) and Jason Teutsch (U. Alabama), based on "How to verify computation with a rational network".

Interactive verification mechanism proposed by Canetti, Riva, Rothblum: "Practical delegation of computation using multiple servers", 2011

Make this work on a blockchain by adding economic incentives.

TrueBit - Overview

1. Task Giver publishes "question"
2. Solvers provide solutions in commit/reveal manner
3. Disputes are resolved using the Verification Game

Task Giver provides fee, Solvers provide deposit and get rewards. Deposit is slashed if fraud is detected. Many parallels to Casper proof of stake.

Due to incentives, verification game will only be played in case of an attack. Attack is only successful if all attackers join forces. A single honest (and uncensored) actor can prevent any attack (51% attack → 100% attack).

Verification Game - Assumptions

• Actors agree on program for class of task (evaluating neural network, solving proof of work for Dogecoin, ...).
• Solvers first run natively implemented program (fast) to find solution.

If there is disagreement, verification game starts:

Verification Game in Detail

• Both solvers re-run input on special implementation which can generate Merkle-roots for all memory at any step.
• provide root hash of first (match) and last (mismatch) step.
• Binary search until single step from match to mismatch.
• provide Merkle-proofs for memory access inside this step.
• Single step is evaluated on-chain:
  • Merkle-proofs are identical before the step (same state root).
  • Memory only changes locally, so Merkle-proof siblings have to be identical

Where can it be Applied?

• Anything that can be broken into steps ("ethereum computation market")
• Tasks have to be implemented in Solidity and off-chain
• We plan to implement a simple virtual machine in Solidity ("lanai"), so mechanism can work with any code without changes
• swarm as actual filesystem for smart contracts

Numbers

1 hour of computation on 4 GHz processor: 14400000000000 = 14.4 * 10¹² steps
If all agree: Almost no strain on the chain
Disagreement: Cheater found in 10 rounds with 640 bytes messages
Commitment to root hashes plus evaluation of single step only on-chain actions.

Behaviour even better on large pre-Merkelized data (blockchain, data from swarm, ...)

Plans for Completion

• Successfully applied for Wanxiang Blockchain Labs grant (small)
• Looking for further funding and implementation help
• Milestones:
  • Finish verification game for Dogecoin Scrypt
  • Implement and test cryptoeconomics
  • Implement generic verifier using lanai architecture