Simulation of TrueBit Protocol: Part 2
Because the TrueBit jackpot mechanism’ unpredictable reward, certain tasks involve Verifiers not doing any computation and therefore not detecting wrong answers submitted by Solvers. To solve this problem, a predictable reward mechanism is needed.
This article introduces two mechanisms that provide predictable rewards and provides a comparative analysis of the two mechanisms through simulation. Also, we will look into the pros and cons compared to the existing jackpot mechanism. First is the ‘multiple solver mechanism’ mentioned in our previous post. Second is the ‘pension mechanism’ designed by Decon.
Pension Mechanism
Consistent rewards
How can we design a reward mechanism that enables expectation of when and how much reward a user can gain? We could distribute the task fee paid by the Task Giver at every task. Yet, would it be possible to distribute task feed based on a clear knowledge of what computation the Verifiers actually performed? With the jackpot mechanism, knowing about the actual computation performed by Verifiers was not an issue because rewards were not given out instantly even for diligent Verifiers. Verifiers were paid after a challenge was performed and the Verifiers’ solution was verified through ON-chain computation. With a Verifier’s challenge, the ON-chain conducts computation to see if the solution is correct. However, because challenges do not happen frequently, it was not a burden to learn whether or not the Verifier actually performed computation. In a predictable mechanism, such a method cannot be applied. While it is not burdensome for the ON-chain to perform solution checks upon challenges with the jackpot mechanism (refer to Simulation of TrueBit Protocol: Part 1), it would be burdensome with a predictable mechanism because the ON-chain has to perform all solution checks. This would tarnish TrueBit’s objective of preserving ON-chain computation capacity. Then how can we minimize the load on the ON-chain while discerning nodes that performed and did not perform computation?
We focused on the fact that most Solvers submit correct answers. As long as there are valid Verifiers, most Solvers will submit correct solutions to protect their deposit. Therefore, we will first deem the solution of Solvers as correct.
Verifiers qualify to receive a pension only when their submission matches that of Solvers. Verifiers must submit five or more matching solutions in their recent six submissions. Verifiers who qualify will continually receive his quota from the task fee. If the Verifier does not go through verification by computation, the solution will not match with the Solver’s solution and will be stripped of being a pension recipient. This incentivizes Verifiers actually compute for the verification.
If the solutions of the Solver and Verifier do not match, the right solution is found via verification game and the deposit of the wrong side is confiscated.
Simulation Result Analysis
Result of the Pension Mechanism
In the pension mechanism, Solvers and Verifiers are rewarded only with the task fee. Therefore, because task fee is more significant than it is in the jackpot mechanism, verification rate, and error detection rate drop if the task fee is small. The current setting has task fee as 100 when the actual computation cost is 1.
Adversely, we can expect that the verification rate and error detection rate will rise when the task fee is bigger. Raising the task fee in the jackpot mechanism has little influence toward improvement. The following graph shows a case when the task fee is 500 times that of the computation cost.
You can see that the verification rate increases significantly and the error detection rate maintains 1.0. However, the burden on Task Givers would be immense.
By running simulations by adjusting the task fee size, we found that changes in the verification rate and error detection rate are minimal after a certain task fee level. The following verification rate graphs illustrate changes when the task fee is increased x500, x1000, x2000, and x4000.
Because rewards are distributed based on 2^(n-1), further increasing the reward after a certain size does not translate into a meaningful reward to each agent and is insufficient in incentivizing dormant agents to participate.
By comparing the jackpot mechanism and pension mechanism, we could see that the network functions in a more predictable manner with the pension mechanism. With the jackpot mechanism, it was difficult to predict the error detection rate just by adjusting the jackpot repository and task fee. The reason was from time to time nobody participated in the verification because rewards were given intermittently. However, the pension mechanism displayed perfect error detection when the task fee was raised above a certain amount.
Still, jackpot mechanism was able to detect significantly more errors when task fee was equally 5.
Multiple-Solver Mechanism
Another predictable reward mechanism is the Multiple-Solver mechanism designed by TrueBit contributors Julia Koch and Christian Reitwießner (Koch, J., & Reitwiessner, C. (2018). A Predictable Incentive Mechanism for TrueBit. arXiv preprint arXiv:1806.11476.). The contributors sought out to solve the problem of not being able to judge whether performing computation is beneficial or not since network users cannot predict the reward.
Multiple-Solver
What stands out in this mechanism is that there are no separate Verifiers. All users can express their willingness to solve problems as the Solver. Once a user decides to participate, the user must submit a solution within the deadline or else the user’s deposit is taken away.
If Solvers come up with different answers, the Solvers are grouped up into tournaments. The group with the correct solution receives the deposits of the other group.
Of course, there is no jackpot repository. Rewards are funded by task fees and through the tournament game.
The advantage of the Multiple-Solver mechanism is that the obligation to verify has been enforced. In the jackpot mechanism, Verifiers are not obligated to verify certain problems. Thus, some solutions submitted by Solvers, although the probability is low, are passed by without verification. Even so, the Verifiers do not lose anything.
However, because the Multiple-Solver mechanism takes away the deposit of users who decided to take part, Solvers are forced to submit valid solutions. All tasks have two or more Solvers participating, and the tournament mechanism kicks in to detect erroneous solutions.
The Multiple-Solver mechanism solves the jackpot mechanism’s problem of not having a consistent reward. Unlike the pension mechanism, it removes Verifiers who have nothing to lose by not submitting solutions and minimizes the possibility of wrong solutions only with Solvers who risk losing their deposit if they do not participate.
Simulation Result Analysis
Result of the Multiple-Solver Mechanism
Like the case of the pension mechanism, it is expected that Multiple solver mechanism requires much more task fee than Jackpot mechanism. Below is a set of verification ratios and error ratios when task fee is differed by x1, x10, x100, x500. In multiple solver simulation, there is no verifier by definition, so verification ratio represents how many solvers participated rather than verifier. Also, the error ratio represents how many solvers made errors rather than how many errors verifier detected.
The more fee is paid, agent participate rate rises, and the number of the wrong solution decreases.
Regardless of the number of wrong answers, the tournament is implemented when all Solvers do not have the same answer, which leads to the ON-chain finding the right solution. However, if cases without the precise solution frequently occur, it is meaningless to seek the computation services of TrueBit. It would be best to set a sufficient task fee from the beginning.
Comparative Analysis
The table above summarizes the pros and cons of the jackpot, pension, and Multiple-Solver mechanisms. The first row shows the task fee level at which increasing the fee no longer leads to significant improvement. The second row and the third row represents verification ratio and error ratio when task fee is given by the first row. Simply, the fee given on the first row means the minimum required to maintain the network. According to the table, the jackpot mechanism allows network operations at relatively low fee, but has relatively fewer participating agents and higher error occurrence rate. Meanwhile, the pension and Multiple-Solver mechanisms have high fees but low error occurrence.
Taking a closer look, the pension mechanism is free from wrong solutions when the fee is 500 times that of the computation cost while it is 100 times for the Multiple-Solver mechanism. This is because generally there are more agents to be rewarded per tasks in the pension mechanism than the Multiple-Solver mechanism. The pension mechanism distributes rewards even when users get one out of six solutions wrong. Such flexibility increases the number of agents eligible for rewards. The reward amount quickly reduces proportional to the number of agents. If you want to use the pension mechanism while matching the solution record of the Multiple-Solver mechanism, the Task Giver has to pay more in task fees.
Conclusion
While the jackpot mechanism renders moderate error levels with less money, predictable mechanisms eliminate all errors with much cost.
The jackpot mechanism has low fees per task. Simply raising the task fee was not effective to detect all wrong solution. Because the rewards are handed out intermittently, there are times (very rarely) when not even one Verifier participates in verifying the wrong solution of a Solver.
As alternatives, the pension mechanism and Multiple-Solver mechanism were proposed. These mechanisms have perfect detection scores if the task fees are raised in the simulation.
To sum up, the jackpot mechanism has its strength of having an affordable task fee while the predictable mechanisms have their strength in ensuring perfect results when the task fee is big enough. Network designers should consider these differences when designing a network.
Furthermore
Through this simulation, we have learned that although there are proposed mechanisms with predictable rewards to overcome the limits of the jackpot mechanism, the jackpot mechanism is still a useful mechanism.
The pension and Multiple-Solver mechanisms have higher task fees than the jackpot mechanism because the distribution method is proportional using 2^(n-1) (the jackpot mechanism also uses this reward method, but dividing a smaller task fee with 2^(n-1) have a bigger influence on the participation decision-making than dividing a big jackpot.) Although these mechanisms were proposed to deter the possibility of sybil attacks in which one user uses various accounts, the increase of good-will users also diminish the reward amount. If this distribution method is not improved, the predictable mechanisms will forever be a mechanism with predictably little reward.
Additionally, we felt the need to add Task Givers in our next simulation. Because we did not have Task Givers, the rise of task fees was absolutely advantageous for the Verifiers and Solvers. However, in reality, high task fees would reduce the number of Task Givers, and the decreased task requests would lead to a drop in Verifier/Solver participation. Therefore, it would be helpful to see whether the network functions when the task fee is raised with the presence of Task Givers and compare the jackpot mechanism and predictable mechanisms.
