Simulation of TrueBit Protocol: Part 1

by | May 12, 2019

https://truebit.io

TrueBit is a protocol set forth to expand computational performance. On the ETH blockchain, computation complexity and storage usage require a fee (gas). Because there is a per-block limit of gas, there is a clear limit to computational capacity.

For now, there is no way to perform complicated computation on the ETH network. For instance, it is impossible to run machine learning functions like facial recognition on a smart contract. Not only would it cost a lot of gas but it would not run properly due to block limitation. In order for the blockchain to function as a universal network structure, these limits need to be overcome.

The solution is TrueBit.

In this Decon series, we have run simulations on TrueBit’s incentive mechanism which is marked by ‘enforced error’ and ‘jackpot’. Will TrueBit accomplish a virtuous cycle as the designers intended?

TrueBit Protocol

The following is a summary of the TrueBit protocol.

  • People or other smart contracts that commission work on a program are called Task Givers. Task Givers register the program code on a TrueBit contract as a task.
  • The Solver works on the task on an OFF-chain WebAssembly virtual machine which is separate from the ON-chain network and submits the result onto the TrueBit contract. The Solver also submits a deposit as accountability for their solution.
  • For a certain period of time, after the Solver submits a solution, the submission is challenged. If there are no Challengers, the Solver’s solution is considered the correct answer and is returned to the Task Giver.
  • If a Verifier challenges the submission, then a verification game begins. The Verifier submits a solution and a deposit. The winner between the Verifier and the Solver receives one’s deposit while the loser loses the deposit.

Please refer to the TrueBit whitepaper for details..[1]

TrueBit structure

The verification game is testing the program ON-chain. But let’s remind ourselves of the true purpose of TrueBit. Computational complexity is so high that programs cannot be run ON-chain and therefore we use TrueBit. Therefore, a verification game cannot run the entire program code.

In fact, only one line of instruction is used in a verification game. There will be a part of the program code where there is a discrepancy between the Solver and the Verifier. The instruction of that discrepancy point is used to verify who is right. For this, the TrueBit contract implements a WebAssembly interpreter.

Forced Error and Jackpot

For the TrueBit protocol to operate properly, Solvers and Verifiers need to actively participate in the network and drive correct results to be returned to the Task Givers. At a glimpse, however, it seems that these two may not be able to co-exist.

If the Solver provides a correct solution, there is no incentive to reward verifiers. If expected gains are low and Verifiers leave the network, Solvers would be able to receive rewards even after submitting a wrong solution. When more and more Solvers set forth wrong solutions, expected gains go up and attract Verifiers back into the network. Consequently, Solvers return to submitting correct solutions in order to retain their deposit. This cycle repeats itself.

Introduction of the Jackpot system

In this cycle, there is a period when the wrong solutions are submitted, rendering the TrueBit network untrustworthy. To remedy this, TrueBit introduced forced error and jackpot systems.

Forced error forces a random Solver to submit an erroneous solution to drive Verifier participation. The Verifier who identifies the wrong solution is given a handsome reward (jackpot). This incentives Verifiers to constantly verify solutions which also checks Solvers to produce correct solutions. As a result, a positive cycle is created in the ecosystem.

If there is more than one Verifier (k) who found the forced error, they share the jackpot (J) distributed through the formula below. The exponential distribution is used to prevent Sybil attack in which one user poses as multiple Verifiers.

Simulation Environment Setting

Next, we will look into the setting and some assumptions for the jackpot mechanism (TrueBit’s fundamental incentive mechanism) simulation.

  • Number of agents: The number of Verifiers in the TrueBit network. Default number is 25.
  • Capacity: Capacity is the computing power that each agent has. The higher the capacity, the more problems an agent can solve in a given time or has lesser burden on solving one problem. We referred to the actual top 25 miners of the ETH network during the most recent 7 days for the capacity distribution.

  • Difficulty indicates the computation complexity of a task. We took used the distribution of gas consumed in each smart contract from a recent block of the ETH blockchain. Agents with low computation power have partial limitations (high costs, total number of computations that can be run in one episode). Difficulty is set in integer value ranging from a minimum 1 to a maximum 10.

  • Enforced error ratio : Refers to the ratio of which enforced errors occur. TrueBit sets the constant as 0.001, but for the purpose of flexibly performing simulations, we made it variable and the default as 0.01.
  • Default jackpot repository: Refers to the jackpot amount stored at the starting point of the simulation. This is appropriated by fees or deposits as the simulation goes through episodes or steps.
  • Solver error ratio: Refers to the probability of Solvers submitting wrong solutions. The focus of our simulation is the ratio and action of Verifiers.
  • Deposit amount: Refers to the deposit amount that Verifiers or Solvers have to bear.
  • Task fee: Refers to the fee paid by the Task Giver for using the protocol.
  • Computation cost: Refers to the fee incurred while performing computation. The harder the problem, the higher the computation cost.

Cost

Fundamentally, the cost is proportional to the difficulty of the performed computation. However, if the Verifier conducted an ill-willed action and such action is apprehended, the Verifier’s deposit is confiscated, incurring an additional cost.

Benefit

Benefit is basically given by the Task Giver. However, in case one wins the verification game, one can win a maximum of half of the deposit made by the Solver. Additionally, if one wins a jackpot, one can expect an immense amount of benefit.

Reward

The reward is the difference between benefit and cost.

Actions

In this simulation, the agent — the Verifier — may or may not perform the computation for verification. By verifying, the Verifier can perform a valid action. In other words, if the Solver sets forth a correct solution, Verifiers will not challenge the solution and only challenge wrong solutions. Meanwhile, Verifiers seeking jackpot wins might challenge solutions without verifying or even not verify nor challenge.

Therefore, we can categorize the action of the Verifier largely into the following three:

  • Verify and perform valid action
  • Do not verify but challenge the Solver
  • Do not participate in the network by not verifying and not challenging the Solver

As episodes progress, the agents will learn and choose the action that is most profitable.

For the proper functioning of the TrueBit network, higher participation ratio of the agents choosing the first action is desirable. Yet, if more agents choose the second action, the network will become unreliable, and if more agents choose the third action, the network will not be organized in a healthy manner.

Simulation Result Analysis

In this simulation, we bundled up 100 tasks into one episode. Because the enforced error ratio was set as 0.01, we expected that one enforced error will occur per episode. Moreover, because the Solver error ratio was set as 0.1, we expected about 10 Solver errors per episode.

Next is the simulation result.

Verification Rate

Ratios of Verifiers performing verification

The graph on the left depicts the ratio of agents that performed verification as episodes progressed. Although there are ups and downs, the overall trend is a downward trend. This is because costs are incurred when a computation is performed for verification while benefit (jackpot) occurs intermittently. In other words, agents do not feel the need to risk verifying due to unexpected rewards.

The graph on the right shows a scenario where the jackpot repository is expanded x100. Yet, because the problem is unpredictability, increasing the jackpot repository will not improve the problem significantly. In fact, the decrease in performing Verifiers is not a good sign for the network. The presence of just one Verifier can detect errors, meaning that even though Verifier ratio drops, the TrueBit network will not crumble instantaneously. We can see this is true through the error detection rate.

Error Detection Rate

Valid challenge rate (error detection rate)

The graph above shows the rate of invalid solution detection rate. If every wrong solution proposed by Solvers are catched, then it’s marked 1.0. If it is not 1.0, that means some wrong solutions have slipped the radar.

The reason such a phenomenon occurs is that the network failed to drive agent participation with unexpected rewards, every agent did not participate in the verification (even with the participation of one agent would enable detecting an error). This means that there is a point where the error detection rate is not 1.0.

When the jackpot repository is increased a hundredfold.

Simply increasing the jackpot repository will not be an improvement measure.

Network Attention Rate

Network attention rate

You can see the ratio of agents participating in the network gradually decreases. The network is slowly dying.

Fairness

The jackpot mechanism, like its name, has a lottery feature. Because enforced errors pop up randomly, not all Verifiers get the opportunity to win a jackpot but can have the fortune of earning a lot of money by winning one.

However, the opportunity is not given fairly. As an agent for computation, having the bigger computation capacity means a higher probability of winning a jackpot. This is similar to the miner with the larger hash power mining most of the rewards in BTC. In this simulation, we were able to observe agents with high computation capacity detecting more errors.

Capacity level and error detection count

Inequality of reward distribution aggravates due to differences in capacity might cause network users to leave and another issue of centralization. Therefore, the system designer must accomplish a certain level of fairness.[2] Because this deviates from the objective and scope of the simulation, we will not go into the details.

Conclusion

The intermittent occurrence of points where the error detection rate is not 1.0 and the increase of non-participation of agents in the network is because of unpredictable rewards. This will not be solved by simply increasing the jackpot size.

We can expect that the agent verification rate and network participation can grow when rewards are somewhat predictable. In fact, Christian Reitwießner, the co-author of the TrueBit whitepaper, saw this problem and even proposed a predictable reward mechanism named the ‘multiple solver mechanism’. [3]

In our next article, we will look into the multiple solver mechanism, introduce to you Decon’s ‘pension mechanism, and analyze the simulation results of these mechanisms.

Reference

[1] Jason Teutsch and Christian Reitwießner, “A scalable verification solution for blockchains”, Nov. 16, 2017

[2] Adem Efe Gencer, Soumya Basu, et al., “Decentralization in Bitcoin and Ethereum Networks”, Mar. 29, 2018

[3] Julia Koch and Christian Reitwießner, “A Predictable Incentive Mechanism for TrueBit”, Jul. 2, 2018