Original source: Medium
原文作者： Sina Habibian
原文标题：《 Truebit: the marketplace for verifiable computation 》
翻译作者： 安仔 Clint & 闵敏
Decentralized applications offer a rosy picture of the future. They are transparent and tamper-proof, running non-stop, unleashing incentives and resolving coordination issues on a global scale.
But there are obstacles in the way.
Decentralized computing is expensive and is limited by the block Gas cap, making many decentralized applications expensive and impractical.
Code written using Solidity is compiled into bytecode in EVM (Ethereum Virtual Machine) and packaged into the blockchain. Since then, every transaction sent to the address of the contract where the bytecode is stored triggers the code to run. As you can see, the blockchain consensus mechanism is redundant in design: all miners perform the same calculation and then agree on the result.
The calculation is quantified, and the cost is correspondingly based on how complex the code is to execute. Each operation in the blockchain virtual machine instruction set is marked with a price (called "Gas"), and the sender of the transaction is paid for each order executed based on the amount of computation.
Any complex business logic always brings high cost.
Not only that, the total amount of computing done on the network is affected by the Gas cap. The Gas cap is the amount of Gas that can be consumed by all transactions in a block. Unfortunately, we can't simply increase the GAS cap due to the validator dilemma problem; Once a miner receives a newly formed block, he needs to verify that it is valid before he can start looking for the next block, but such verification is free labor. Profit - driven miners are faced with a dilemma: verify the block or skip it. This dilemma was exacerbated when the Gas ceiling for the blocks was increased.
So computing is expensive and limited.
Turebit Aimed at solving this problem.
It solves this problem by moving the calculation down the chain and verifying the correctness of the calculation through an interactive cryptoeconomy protocol.
When a dApp (decentralized application) wants to run computations that are expensive or above the Gas ceiling, instead of running the computations directly on Ethereum, it can be turned over to the Truebit protocol.
The API that interacts with the TrueBit protocol is simple: it is simply a function called createTask on TrueBit's smart contract.
The dApp calls the createTask function by sending the following:
, & have spent Program: Program code. TureBit uses WebAssembly virtual machine technology, so a DAP can send bytecode of a program's code directly to the WebAssembly virtual machine, or send a hash of the program's code on IPFS or other content-addressable systems.
, & have spent Input value: The input value to the program. A dApp can send these input values either directly or as a hash of the input values on a content-addressable system.
, & have spent Bonus: The amount of money awarded to anyone who runs the program.
A dApp creates a Truebit task
To further illustrate this process, let's look at two examples.
Livepeer Is a decentralized computing platform that needs to check that the transcoder is working properly. So it calls The createTask function, which sets FFmpeg As a program, a video is sent to the function as input.
Aragon Is a platform for an anonymous group that wants to do the counting. It is expensive to loop a large number of votes up and down the chain, and if too many votes are counted, the Gas cap prevents this from happening. So Aragon called Truebit's createTask Function, sending the vote count function as the program and the number of votes array as the input value.
This function generates a new task in the TrueBit contract.
Truebit is a computing task marketplace.
Anyone can install the TrueBit client, join a barrier free network, and get paid to run computing tasks.
Truebit Miners install clients that listen for events emitted by Truebit contracts.
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 input provided by the task publisher, and then send their results to a smart contract.
Those who undertake computations are also required to pay a deposit, which is used to ensure that the task handler is responsible for his or her calculations.
The task handler submits the result.
Timer starts. Any Truebit verifier within the challenge time limit can challenge submitted calculations with the payment of a deposit.
This is in line with expectations. The task handler ran the program correctly. If no one disputes the calculated result during the entire challenge period, the result is considered correct. The TrueBit contract uses this calculation to call back the dApp that initiated the task.
The task initiator receives the answer to the question.
One verifier put down a deposit and challenged the current calculation. There is now disagreement about the calculations. In the case of the contract, it holds not only the original quest reward provided by the quest originator, but also the quest handler's deposit, and the challenger's deposit.
A verifier issued a challenge
This leads to an interactive verification game between the task handlers and the challengers.
Note that the TrueBit task is a WebAssembly program that executes a sequence of instructions.
A simple C program (figure left) and its compiled WebAssembly text form (figure right)
The challenger launched a verification game.
Both the task handler and the challenger start with a state of 0, and they each start an empty virtual machine running the same input with the same program (as specified in the task description on the blockchain). At state zero, they're consistent.
At the end of the program's run, let's say after 14 instructions, they computed different results. That is, at state 14, the task handler and the challenger diverged.
The task handler and challenger's calculations agree at state 0 and diverge at state 14
The challenger uses this information to ask the task handler about the state of the program halfway through, when the seventh instruction has been run.
The challenger queries the status of the task handler
A task processor can use TrueBit's WebAssembly virtual machine to calculate the hash of its own state. It exports a Merkell root from the stack, memory, and full state of the task handler's WebAssembly virtual machine. The task handler submits the root to the smart contract with a Respond message.
The task handler and the challenger play a verification game
Now it is the challenger's turn to calculate the merkle root of his side's state locally and compare the results with those of the task handler.
If the two roots are equal, you can tell where they diverge in the second half of the computation instruction set. If the two roots are not equal, then their divergence occurs in the first half of the set.
And just for the sake of illustration, we're going to assume that at state 7 these two roots are equal.
The state roots of the challenger and the task handler are equal at state 7
The challenger then sends a The Query message asks the task handler to calculate the state root at the midpoint in the last half of the instruction set, after the 10th instruction has been run.
The challenger asks for the state root of the second midpoint in the set
The task handler then responds in kind.
The challenger finds that at state 10 both sides have the same state root, and then queries the next midpoint, which is the state root at state 12.
The challenger queries the state root of the third midpoint
The interactive verification game continues.
The challenger uses a binary search method to force the task handler to find the location of the conflicting states. 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 root before and after the occurrence of the instruction submitted by the task handler, the location of the divergence is finally locked at a certain instruction.
Controversy: the command that transitions from state 12 to state 13
The amount of computation is now small enough for Trubit smart contracts to initialize a virtual machine based on the pre-execution state of the instruction, and then run the disputed instruction on the blockchain.
The on-chain WebAssembly interpreter runs the disputed instruction
If the merkle root of the state is calculated differently from the status root provided by the task handler, the latter's deposit is forfeited.
That's the whole process!
We moved all the calculations down the chain and used Ethereum only to compute that single step instruction, in case there was a dispute.
In this way, we reached a consensus on the final result, but this consensus is stronger than Satoshi's requirement that a majority of people be honest, and BFT's requirement that two-thirds be honest. We came to an "undisputed consensus that as long as there is an honest verifier, the system is secure.
Truebit's incentives include task rewards, deposits, challenge mechanisms between task handlers and challengers, and the economic design of the computing marketplace.
We recently announced plans to upgrade TrueBit tokens. Here are two of the solutions we're considering:
Examine this protocol closely, and some astute readers may discover a problem.
Knowing that their calculations will be checked and that they will forfeit their deposit if they are wrong, the taskmaster does not cheat. Over time, verifiers are extremely difficult to detect errors, unable to generate revenue, and eventually disappear from 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 often flips up and down.
To solve this problem, Truebit's white paper introduces the concept of forced error and jackpot. The Truebit protocol forces the task handler to provide incorrect calculations under certain probabilities. Any verifier who finds such errors and succeeds in the challenge will automatically receive a cumulative bonus. This windfall is taken out of the rewards for all tasks and is therefore huge, providing the verifier with a substantial expected payoff. Validating tasks can be profitable even if the task handler always provides correct calculations.
Another alternative comes from the implementation process. The task handler and the verifier always do the same job: they download the same program, run it locally, and get the results. So instead of having a single task handler and multiple challengers based on a chronological rule, why not change the protocol to allow everyone to submit their calculations at the same time?
The smart contract checks that all the calculations are consistent. If so, the result is considered correct. If there are inconsistencies and several types of results are produced, the smart contract will organize a pair of different types of task handlers for verification.
This improved protocol ensures better timeliness because the validation challenges are parallel. This improvement can also replace forced errors and accumulated bonus pools. The downside is the increased complexity of how much the task sponsor should pay for the rewards and how the rewards should be distributed among the multitaskers.
We are working hard to see how we can improve the protocol. Zack Lawrence And & have spent Ali Yahya Twitter with some constructive suggestions!)
Truebit is a modular system that can be divided into three levels:
Trubit's modular architecture
Computing layer: i.e. The WebAssembly virtual machine (or a finite state machine, as we do with interactive Scrypt As used in the design of the DOGE-Ethereum transition bridge) it requires both on-chain and off-chain construction.
Truebit's WebAssembly interpreter is deterministic and quantifiable, generating a Merkle tree of internal state.
Dispute Resolution Layer: & NBSP; This is a two-party interactive verification game, involving multiple interactive questions and answers between the task handler and the verifier.
Incentive Layer: This layer includes rewards, deposits, challenge mechanisms between task handlers and challengers, and token mechanisms. The layers communicate with each other through defined interfaces.
Our engineering direction is currently focused on the computing and dispute resolution layer. Our research focuses on the incentive layer and token mechanism.
We recently announced our TrueBit solution for Scrypt validation, which is being used in the DoGE-Ethereum transition bridge.
You can watch our demo video here, or at Github Check out our code on.
Support for the WebAssembly VM is in our sights for the next release.
律动 BlockBeats 提醒，根据银保监会等五部门于 2018 年 8 月发布《关于防范以「虚拟货币」「区块链」名义进行非法集资的风险提示》的文件，请广大公众理性看待区块链，不要盲目相信天花乱坠的承诺，树立正确的货币观念和投资理念，切实提高风险意识；对发现的违法犯罪线索，可积极向有关部门举报反映。