Truebit: Creating a Market for Verifiable Computing
Decentralized applications paint us a rosy picture of the future. They are transparent and tamper-resistant, running non-stop, unleashing incentives and solving coordination problems on a global scale.
But there are obstacles along the way.
first level title
The Hard Problem: Decentralized Computing
Code written in Solidity is compiled to bytecode in the EVM (Ethereum Virtual Machine) and then packaged into the blockchain. Since then, every transaction sent to the contract address storing the bytecode will trigger the code to run. It can be seen from this that there is redundancy in the design of the blockchain consensus mechanism: all miners perform the same calculation and then reach a consensus on the result.
Computation is quantified, and accordingly the cost is determined by the complexity of the code execution. Each operation in the blockchain virtual machine instruction set is marked with a price (called "Gas"), and the sender of the transaction will pay according to the calculation amount every time an instruction is executed.
Any complex business logic will always bring high costs.
More than that, the total amount of calculations performed on the network will be affected by the upper limit of Gas. Gas upper limit refers to the total amount of Gas that can be consumed by all transactions in a block. Unfortunately, we cannot simply increase the gas limit due to the verifier's dilemma; once a miner receives a newly formed block, they need to verify that the block is valid before they can start looking for the next block, but Such verification is free labor. Profit-driven miners are in a dilemma: verify the block or skip it. And when the gas limit of the block increases, the impact of this dilemma also becomes larger.
So computation is expensive and limited.
Truebit aims to solve this problem.
first level title
The Solution: Verifiable Computing Off-Chain
When a dApp (decentralized application) wants to run calculations that are expensive or exceed the upper limit of Gas, instead of running calculations directly on Ethereum, it is better to hand over to the Truebit protocol.
Truebit contract
The API for interacting with the Truebit protocol is very simple: it's just a function called createTask on the Truebit smart contract.
The process of calling the createTask function by dApp needs to send the following content:
program: program code. Truebit uses WebAssembly virtual machine technology, so dApp can directly send the bytecode of the program code to the WebAssembly virtual machine, or send the hash value of the program code on IPFS or other content-based addressing systems.
Input value: Input value for the program. A dApp can send these inputs directly, or a hash of those inputs on a content-addressed system.
image description
A dApp creates a Truebit task
To further illustrate this process, let's look at two examples.
Livepeer is a decentralized computing platform, which needs to check whether the transcoder is working properly. So it calls the createTask function, sending FFmpeg as the program and a video as the input value to the function.
Aragon is a platform for anonymous organizations that want to do the work of counting votes. Cycling large batches of voting work on the chain is expensive, and if too many votes are counted, the gas cap will hinder this work. So Aragon called Truebit's createTask function, and sent the vote counting function as a program and the array of votes as an input value to the function.
This function will generate a new task in the Truebit contract.
Truebit Network
Truebit is a marketplace for computing tasks.
Anyone can install the Truebit client, join the unrestricted network, and get paid by running computing tasks.
image description
Truebit miners monitor computing tasks
Once a new task is generated, Truebit miners can download its code, run the program in the local Truebit WebAssembly virtual machine using the input provided by the task publisher, and then send their results to the smart contract.
image description
The task handler submits the result
secondary title
Case 1: No challenger
image description
secondary title
Second case: there is a challenger
image description
A validator initiated a challenge
secondary title
verify game
image description
A simple C program (left) and its compiled WebAssembly text form (right)
The challenger initiates the verification game.
Both the task handler and the challenger have an initial state of 0, they each start an empty virtual machine, run the same input with the same program (as specified in the task description on the blockchain). When the state is 0, they are consistent.
image description
image description
image description
The challenger queries the status of the task handler
image description
Task handlers and challengers play a verification game
Now it is the challenger's turn to locally compute the Merkle root of its own state and compare the result with the task handler's result.
If the two are equal, it can be judged that the position where they diverge is in the second half of the calculation instruction set. If the two are not equal, then their divergence occurred in the first half of the set.
image description
The state root of the challenger and the task handler is equal when the state is 7
image description
The challenger asks the state root of the second midpoint in the set
The task handler responds accordingly.
image description
The challenger queries the state root of the third midpoint
The interactive verification game continues.
image description
Argument: The instruction when transitioning from state 12 to state 13
image description
On-chain WebAssembly interpreter runs controversial instructions
If the calculated Merkle root of the state is different from the state root provided by the task handler, the latter's deposit will be forfeited.
That's it for the whole process!
We move all calculations off-chain and only use Ethereum to calculate that one-step instruction to prevent disputes.
first level title
Cryptoeconomics
Truebit's incentives include task rewards, deposits, challenge mechanisms between task handlers and challengers, and the economic design of the computing market.
Recently we announced the upgrade plan of Truebit tokens, the following are two solutions currently under consideration:
Incentive layer 1: Mandatory error & cumulative prize pool
Carefully studying this protocol, some astute readers may spot a problem.
Task handlers know that their calculations will be checked, and if they make a mistake, their deposit will be forfeited, so they will not cheat. In the long run, it is extremely difficult for validators to find bugs, earn no income, and eventually disappear in the computing market. After the verifier disappears, the task handler will start cheating. Then, the verifier will reappear and catch the error.
The system is not in a stable equilibrium, but is constantly flipping up and down.
In order to solve this problem, Truebit proposed a concept of forced error and jackpot in the white paper. The Truebit protocol will force the task handler to provide wrong calculation results under a certain probability. Any validator who finds such bugs and succeeds in the challenge will automatically receive a jackpot. This windfall is drawn from the rewards of all tasks, so it is huge, providing validators with a substantial expected return. Verification tasks are profitable even if the task handler always provides correct computation results.
Incentive Layer 2: Multiple Task Handlers and Pair Verification Challenge
Another alternative comes from the specific implementation process. Task handlers and verifiers always do the same job: they download the same program, run it locally, and get the computation. So instead of specifying one task handler and multiple challengers according to the timing rules, why not change the protocol to allow everyone to submit their calculation results at the same time?
The smart contract checks that all calculations are consistent. If they agree, the result is considered correct. If it is inconsistent and several types of calculation results are generated, the smart contract will organize different types of task processors to perform pair verification.
This improved protocol can better guarantee timeliness because the verification challenges are parallelized. This improvement can also replace forced errors and jackpots. But the disadvantage is that it increases the complexity of how much the task initiator should pay and how to distribute the reward among multiple task handlers.
first level title
modular architecture
image description
Trubit's modular architecture
Computing layer: that is, the WebAssembly virtual machine (or a finite state machine, like we used in designing the Doge-Ethereum conversion bridge using interactive scrypt), which requires both on-chain and off-chain construction.
Truebit's WebAssembly interpreter is deterministic and scalable, capable of generating Merkle trees of internal state.
Dispute resolution layer: This is an interactive verification game between two parties, including multiple interactive question-and-answer sessions between task handlers and verifiers.
Incentive layer: This layer includes rewards, deposits, challenge mechanisms between task handlers and challengers, and token mechanisms.
epilogue
epilogue
Our engineering direction is currently focused on the computation and dispute resolution layers. Our research focuses on incentive layers and token mechanisms.
Recently we announced the Truebit solution for Scrypt authentication, which is implemented in the Doge-Ethereum conversion bridge.
You can watch our demo video here, or check out our code on Github.
Stay tuned!
Stay tuned!
Original link: https://medium.com/truebit/truebit-the-marketplace-for-verifiable-computation-f51d1726798f
Author: Sina Habibian
Translator & Proofreader: Anzi Clint & Min Min
