Decentralized applications paint a bright future for us. They are highly transparent and tamper-proof, and operate non-stop, releasing incentives and solving coordination problems on a global scale.
But there are also obstacles on the road of development.
Decentralized computing is very expensive, and limited by the upper limit of block Gas, many decentralized applications become very expensive and impractical.
The problem: decentralized computing
Code written in Solidity will be compiled into bytecode in EVM (Ethereum Virtual Machine) and then packaged into the blockchain. Since then, every transaction sent to the contract address where the bytecode is stored will trigger the code to run. It can be seen 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.
The calculation is quantified, and the corresponding cost is determined by the complexity of the code execution. Each operation in the instruction set of the blockchain virtual machine is marked with a price (called “Gas”), and the sender of the transaction will pay a fee based on the amount of calculation for each instruction executed.
Any complicated 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 gas limit. The upper gas limit refers to the total amount of gas that can be consumed by all transactions in a block. Unfortunately, due to the verifier’s dilemma, we cannot simply increase the upper gas limit; once miners receive a newly formed block, they need to verify whether the block is valid before starting to find the next block, but Such verification is free labor. Profit-driven miners are in a dilemma: to verify this block or skip it. When the upper gas limit of a block increases, the impact of this dilemma also increases.
So computing is expensive and limited.
Turebit aims to solve this problem.
It solves this problem by moving the calculation to the chain, and verifies the correctness of the calculation through an interactive crypto economic protocol.
Solution: verifiable calculations off-chain
When a dApp (decentralized application) wants to run calculations that are expensive or exceed the gas limit, instead of running the 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 is just a function called createTask on the Truebit smart contract.
The process of calling the createTask function of the dApp needs to send the following:
· Program: Program code. Turebit 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: the input value for the program. The dApp can send these input values directly, or send the hash value of these input values on a content-based addressing system.
· Reward: the amount of reward, provided to anyone who runs this program
A dApp creates a Truebit task
To further illustrate this process, let’s look at two examples below.
Livepeer is a decentralized computing platform, it needs to check whether the transcoder is working properly. So it calls the createTask function, and sends FFmpeg as a program and a video as an input value to the function.
Aragon is an anonymous organization platform that wants to count votes. It is very expensive to loop large batches of voting work on the chain, and if the number of votes is too large, the Gas upper limit will hinder this work. So Aragon calls Truebit’s createTask function, and sends the ticket counting function as a program and an array of votes as the input value to the function.
This function will generate a new task in the Truebit contract.
Truebit network
Truebit is a computing task market.
Anyone can install the Truebit client, join the barrier-free network, and then get paid by running computing tasks.
The client installed by the Truebit miner will listen to events emitted by the Truebit contract.
Truebit miners monitor computing tasks
Once a new task is generated, Truebit miners can download their code, then use the input provided by the task publisher to run the program in the local Truebit WebAssembly virtual machine, and then send their results to the smart contract.
Those who undertake calculation tasks must also pay a deposit to ensure that the task processor is responsible for their calculation results.
Task handler submits results
The timer starts. Within the challenge time limit, any Truebit verifier can challenge the submitted calculation results on the premise of paying a deposit.
The first situation: no challenger
This is in line with expectations. The task handler ran the program correctly. If within the entire challenge time limit, no one raises an objection to the existing calculation result, it is deemed to be the correct result. The Truebit contract will use the calculation result to call back the dApp that initiated the task.
The task initiator receives the answer to the question
The second case: there are challengers
A validator paid a deposit and challenged the current calculation results. Now there is a disagreement on the calculation results. For the contract, it not only keeps the original task rewards provided by the task initiator, but also the deposit of the task handler and the deposit of the challenger.
A validator initiates the challenge
As a result, an interactive verification game was launched between the task handler and the challenger.
Verify the game
It should be noted that the Truebit task is a WebAssembly program that executes a series of instructions in sequence.
A simple C program (picture left) and its compiled WebAssembly text form (picture right)
The challenger initiated the verification game.
The initial state of the task handler and the challenger is 0. They each start an empty virtual machine and 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.
At the end of the program, we assume that after running 14 instructions, they calculated different results. In other words, when the status is 14, the task handler and the challenger have a disagreement.
The task handler and the challenger agree on the calculation results when the state is 0 and diverge when the state is 14.
The challenger uses this information to query the status of the task handler when the program is halfway through, that is, when the seventh instruction is completed.
The challenger queries the status of the task handler
Task handlers can use Truebit’s WebAssembly virtual machine to calculate the hash value of their own state. It is a Merkel tree root derived from the stack, memory and complete state of the WebAssembly virtual machine of the task handler. The task handler will submit this root to the smart contract via a Respond message.
Task handlers and challengers play verification games
Now it is the challenger’s turn to calculate the Merkel tree root of his own state locally and compare the result with the result of the task handler.
If the two roots are equal, it can be judged that their divergence is in the second half of the calculation instruction set. If the two roots are not equal, then their divergence occurs in the first half of the set.
For the convenience of explanation, we now assume that the two roots are equal when the state is 7.
The challenger and the task handler are equal when the state is 7
The challenger then sends a Query message to ask the task handler to calculate the midpoint of the second half of the instruction set, that is, the state root after running the tenth instruction.
The challenger asks the state root of the second midpoint in the set
The task handler responds accordingly.
The challenger finds that the state roots of the two parties are the same when the state is 10, so they then query the next midpoint, that is, the state root when the state is 12.
The challenger queries the state root of the third midpoint
The interactive verification game continues.
The challenger uses the binary search method to force the task handler to find the position of the divergent state. The time complexity of the entire game is O(log(n)), where n is the total number of instructions in the program. According to the state roots before and after the instruction submitted by the task processor, the position of the divergence is finally locked at a certain instruction.
Argument: The instruction when changing from state 12 to state 13
The amount of calculation now is small enough for the Trubit smart contract to initialize a virtual machine based on the state before the instruction is executed, and then run the disputed instruction on the blockchain.
On-chain WebAssembly interpreter runs controversial instructions
If the Merkel root of this state is calculated to be different from the state root provided by the task handler, the latter’s deposit will be confiscated.
That’s the whole process!
We move all the calculations off-chain and use only Ethereum to calculate the single-step instruction to prevent disputes.
Through the above methods, we reached a consensus on the final result, but this consensus is more honest than Satoshi Nakamoto’s requirement for most people, and BFT’s requirement for two-thirds of people is stronger. We got a “uncontroversial consensus: as long as there is an honest validator, the security of the system can be guaranteed.
Cryptoeconomics
Truebit’s incentives include task rewards, deposits, challenge mechanisms between task handlers and challengers, and the economic design of the computing market.
We recently announced the upgrade plan for Truebit tokens. The following are two solutions currently being considered:
Incentive layer 1: Mandatory error & jackpot
If you study this protocol carefully, some keen readers may find a problem.
Task handlers understand that their calculation results will be checked, and if they make mistakes, their deposit will be confiscated, so they will not cheat. If things go on like this, it is extremely difficult for verifiers to find errors, unable to earn 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.
This system is not in a stable balance, but often flips 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 incorrect calculation results with a certain probability. Any validator who discovers such errors and challenges successfully will automatically receive a jackpot. The bonus of this windfall is drawn from the rewards of all tasks, so it is huge and provides considerable expected benefits for the verifier. Even if the task handler always provides the correct calculation results, the verification task is profitable.
Incentive layer two: multiple task handlers and pair verification challenges
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 result of the calculation. So instead of specifying a task handler and multiple challengers in accordance with the timing rules, why not change the protocol to allow everyone to submit their own calculation results at the same time?
The smart contract will check whether all the calculation results are consistent. If they agree, the result is considered correct. If they are inconsistent and produce several types of calculation results, the smart contract will organize different types of task handlers to perform pair verification.
This improved protocol can better guarantee timeliness, because the verification challenge is parallel. This improvement can also replace mandatory errors and jackpots. But the disadvantage is that it increases the complexity of how many rewards should be paid by the task initiator and how to distribute the rewards among multiple task handlers.
We are working hard on how to improve the agreement (you are welcome to send some constructive suggestions to Zack Lawrence and Ali Yahya’s Twitter!)
Modular architecture
Truebit is a modular system that can be divided into the following three levels:
Trubit’s modular architecture
Computing layer: the WebAssembly virtual machine (or a finite state machine, as we used in the design of the Doge-Ethereum conversion bridge using interactive scrypt), it requires both on-chain and off-chain construction.
Truebit’s WebAssembly interpreter is deterministic and measurable, and can generate a Merkel tree of internal states.
Dispute Resolution Layer: This is an interactive verification game between two parties, including multiple interactive questions and answers between task handlers and verifiers.
Incentive layer: This layer includes rewards, deposits, challenge mechanisms between task handlers and challengers, and token mechanisms. Each layer will communicate through a well-defined interface.
Concluding remarks
Our engineering direction is currently focused on the calculation and dispute resolution layer. Our research mainly focuses on the incentive layer and token mechanism.
Recently we announced the Truebit solution for Scrypt verification, which has been applied in the Doge-Ethereum conversion bridge.
You can click here to watch our demo video, or check our code on Github.
We will support WebAssembly VM in our next version.
Stay tuned!