Truebit: the marketplace for verifiable computation
Decentralized applications hold promise for the future. They operate in a transparent, tamperproof, unstoppable manner. They leverage incentives and solve coordination problems on a global scale.
But there are obstacles in the way.
Decentralized computation is expensive and bound by the block gas limit, rendering many applications costly or infeasible.
The Problem: decentralized computation
Write some code in Solidity, compile it into EVM (Ethereum Virtual Machine) bytecode, and push it to the blockchain. From then on, the code is executed anytime a transaction is sent to the address. The blockchain consensus mechanism is redundant by design: all miners run the computation and come to agreement on the results.
Computation is metered, so that fees scale with the complexity of code. Each operation in the blockchain virtual machine’s instruction set is assigned a cost (called “gas”). The transaction sender thus pays per executed instruction.
Anything beyond simple business logic has a hefty price tag attached.
Moreover, computation on the network is gated by the block gas limit. This is an upper bound on the total gas consumed by all transactions within a block. Unfortunately, one cannot simply increase the gas limit because of the Verifier’s Dilemma; miners who receive a newly formed block need to first verify that it is correct before beginning their search for the next block; but they receive no fees for such verification. Their incentives pull them in two contradictory directions: to verify, or to skip verification. This is exacerbated with an increased block gas limit.
So computation is expensive and bounded.
Truebit solves this problem.
It does this by moving computation off-chain; and verifying its correctness via an interactive crypteconomic protocol.
The Solution: offchain verifiable computation
A dapp (decentralized application) wants to run computation that would be expensive or is larger than the gas limit.
Instead of running it directly on Ethereum, it passes it to the Truebit protocol.
The Truebit contracts
The API for interacting with the Truebit protocol is simple: a single function on the Truebit smart contract called createTask.
The dapp calls the createTask function, passing in the following:
- program: the program code. Truebit uses the WebAssembly VM; the dapp can pass in the bytecode directly — or more likely include the IPFS hash or another content-addressed location for the code.
- inputs: the inputs to the program. The dapp can provide these directly, or include their content-addressed location.
- reward: a reward, paid to whoever runs this program.
Let’s look at two case-studies for illustrative purposes.
Livepeer, a platform for decentralized computation, wants to check that a transcoder did their job correctly. They call the Truebit createTask function, passing in FFmpeg as the program and a segment of video as the input.
Aragon, a platform for autonomous organizations, wants to tally votes. Iterating through a large array of votes on-chain is expensive and, if there are too many elements, impossible due to the gas limit. They call the Truebit createTask function, passing in a tallying function as the program, and the array of votes as the input.
This function creates a new Task in the Truebit contract.
The Truebit network
Truebit is a computation marketplace.
Anyone can install the Truebit client, join the free-entry network, and earn rewards in return for running tasks.
The client, installed by a Truebit miner, listens for events on the Truebit contract.
Upon creation of a new Task, a Truebit miner can download the code, run it locally through their Truebit WebAssembly VM with the provided inputs, and submit the solution to the contract.
The Solver also includes a deposit, which ensures that they have skin in the game.
A timer begins. Within this challengeTimeout, any Truebit Verifier can submit a challenge to the proposed solution, along with their own deposit.
Case #1: no challenges.
This is the expected case. The Solver ran the program correctly. The solution remains unchallenged for the duration of the challengeTimeout, and is therefore, deemed correct.
The Truebit contract makes a callback to the dapp with the solution.
Case #2: a challenge is submitted.
A Verifier submits a challenge, along with a deposit. There is now a dispute.
The contract is in possession of the original payment provided by the TaskGiver, a deposit from the Solver, and a deposit from the Challenger.
An interactive verification game between the Solver and Challenger begins.
The verification game
Note that a Truebit task is a WebAssembly program, a set of instructions that are executed one after another.
The challenger begins the game.
Both the Solver and the Challenger had the same starting point — at state 0, they booted up an empty VM, had the same program and the same inputs (as dictated by the description of the task on chain). At state 0, they agreed.
At the end of the program, let’s say it has 14 instructions, they got different results. Therefore, at state 14, they disagreed.
The Challenger uses this knowledge and queries the Solver for their state at the half-way mark of program execution, i.e. after 7 instructions.
Using the Truebit WebAssembly VM, the Solver calculates a hash of their state. This is a Merkle Root derived from the stacks, the memory, and the entire state of the Solver’s WebAssembly virtual machine. The Solver submits this root to the contract in a Respond message.
The Challenger now computes their own state Merkle Root locally and compares with the value provided by the Solver.
If the two values are the same, they deduce that the disagreement occurred in the second half of the computation. If the two values are different, they deduce that the disagreement occurred in the first half.
For the sake of illustration, let’s imagine that the two state roots are the same.
The Challenger now sends a Query message, asking for the Solver’s state root at the midpoint of the second half of computation, i.e. after instruction 10.
The Solver responds.
The Challenger observes that they have the same root at state 10. They then query for the right midpoint; i.e. for state 12.
The interactive game continues.
The Challenger forces the Solver towards the first point of disagreement using a binary search. The game takes O(log(n)) steps where n is the total number of instructions in the program.
The disagreement is eventually narrowed down to a single instruction, with the Solver having committed to a state root before and after.
At this point, the computation is small enough that the Truebit contract initializes a VM with the pre-state and runs the disputed instruction on-chain.
The Merkle Root of the state is calculated, and if it differs from the one provided by the Solver, their deposit is slashed.
That’s it!
We move the entire computation off-chain, and use Ethereum to run a single instruction in case of a dispute.
We achieve consensus on the result — but a kind of consensus that is stronger than the honest majority requirement of Nakamoto Consensus or the two-thirds honest requirement of BFT. We have “unanimous consensus”: safety is guaranteed as long as there is one honest verifier.
Cryptoeconomics
Truebit’s incentives include the task rewards, deposits, the selection of the Solver and Challenger, and the economic design of the computation marketplace.
We recently published an update on Truebit’s token mechanics. Here are two solutions currently under consideration:
Incentive Layer #1: forced errors & jackpot
Thinking through the above protocol, the discerning reader will notice a problem.
Knowing that their solution is checked and their deposits slashed in the case of a wrong answer, the Solver always tells the truth. As such, Verifiers never catch an error, never make any money, and eventually stop showing up. At this point, the Solver can begin posting wrong solutions. Then, Verifiers begin showing up again to catch errors.
The system flip flops. It does not have a stable equilibrium.
To resolve this issue, the Truebit whitepaper introduces the concept of a forced error and a jackpot. With some probability, the protocol forces the Solver to provide the wrong answer. In these occasions, any verifiers who challenge automatically receive a jackpot. This windfall payment is so large that, amortized over the total number of tasks, it gives a positive expected return. Verifying tasks is profitable even if Solvers always tell the truth.
Incentive Layer #2: multiple solvers and pairwise verification games
An alternative approach stems from the realization that Solvers and Verifiers are all doing the same work: they download the program, run it locally, and get a solution. What if instead of the sequential nature of having one Solver and many Challengers, the protocol allows everyone to submit their solutions at the same time?
The contract would see whether all solutions agree. If they do, then we have arrived at the truth. If they don’t and there are clusters of solutions, the contract can facilitate pairwise verification games between the different groups.
This protocol achieves better timeliness guarantees, as games happen in parallel. It also does away with the forced error and jackpot. But it has added complexities in determining the cost to the TaskGiver and distributing rewards amongst the many Solvers.
We are actively researching variations of the protocol (and would like to give a shoutout to Zack Lawrence and Ali Yahya for helpful discussions related to these constructions!)
Modular architecture:
Truebit is a modular system and can be thought of in three layers:
The Computation layer: this is a WebAssembly VM (or a more limited state machine, such as in our interactive scrypt construction for the Doge-Etheruem bridge). It requires implementations offchain and onchain.
The Truebit WebAssembly interpreter is deterministic, metered, and has the ability to create Merkle trees of its internal state.
The Dispute Resolution layer: this is an interactive game between two parties; a verification game involving multiple query-response calls between the Solver and Verifier.
The Incentive layer: this involves the rewards, deposits, solver and challenger selection, and token mechanics.
The layers will communicate via well-defined interfaces.
Fin
Our engineering efforts are now focused on the computation and dispute-resolution layers. Our research efforts are focused on the incentive layer and token mechanics.
We recently launched Truebit for Scrypt verification, for use within the Doge-Ethereum bridge. Watch our demo or view the code on Github.
Our next implementation will support the WebAssembly VM.
Stay tuned!
If you want to discuss or say hi, ping me on Twitter!
