What problem does Truebit solve

Original source: Medium

原文作者： Sina Habibian  

原文标题：《 Truebit: the marketplace for verifiable computation 》 

Ethereum enthusiasts

翻译作者： 安仔 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.

Problem: Decentralized computing

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.

Solution: Verifiable computing off the chain

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.

Truebit contracts

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 network

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.

Case 1: There is no challenger

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.  

Case 2: There is a challenger

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.

Verify the game

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.

  Cryptoeconomics

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:

  Excitation layer 1: forced error & Cumulative prize pool & NBSP;  

   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.

  Motivation Layer 2: Multitasking and Pair Validation Challenges & NBSP;  

  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!)

  Modular Architecture & NBSP;  

  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.

  conclusion

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.

Stay tuned!

Welcome to join the official BlockBeats community:

Telegram Subscription Group: https://t.me/theblockbeats

Telegram Discussion Group: https://t.me/BlockBeats_App

Official Twitter Account: https://twitter.com/BlockBeatsAsia