TrueBitFoundation
Too large or otherwise inaccessible IPFS files
How about the following?
-
In addition to posting the address of a wasm file, a task giver also posts the root of a Merkle tree corresponding to that file.
-
By bidding on a task, a solver implicitly agrees that the task's wasm file does indeed have the Merkle root provided by the task giver.
-
If there is a dispute between parties A and B and A's computation is a proper prefix of B's, then B must supply the instruction that extends A's computation and "prove" (using the Merkle tree) that the instruction lies at the appropriate offset within the wasm file.
-
If there is a dispute between parties A and B and neither's computation is a prefix of the other's, then the burden falls upon whichever party is the solver to provide the instruction that extends the longest common prefix and to "prove" that the instruction lies at the appropriate offset within the wasm file.
In regard to the final bullet, I can see arguments for both defaulting to the solver and defaulting to the verifier.
I lean (slightly) toward defaulting to the solver in order to help thwart the following attack.
-
A task giver posts the address of a wasm file along with the Merkle root of a distinct wasm file, but one that the task giver secretly knows.
-
A naive, over eager solver wins the election without first verifying that the Merkle root corresponds to the wasm file at the given address.
-
The solver posts a solution.
-
The task giver poses as a verifier and challenges the solver's solution, which happens to be incorrect for the wasm file with the given Merkle root.
-
The task giver collects the solver's deposit.
Defaulting to the solver does not thwart this attack outright. But, putting more responsibility upon the solver makes it a little more obvious that the solver should verify the wasm file before bidding on it.
How would a Verifier know whether or not to challenge if he can't see the raw data?
In the case where only the Task Giver has access to the raw data, then the Task Giver might also be the Solver. Consider such an instance. If the Verifier knows that the expected reward for a correct challenge is x and the penalty for a false challenge is y, then the Task Giver/Solver can choose to offer a correct solution with a probability p(x,y) and a bogus solution with probability 1 - p(x,y) so that rational Verifiers will not participate.
How would a Verifier know whether or not to challenge if he can't see the raw data?
I was imagining that a Verifier who is unable to check the Merkle root of the file would would simply not participate.
... the Task Giver/Solver can choose to offer a correct solution with a probability p(x,y) and a bogus solution with probability 1 - p(x,y) so that rational Verifiers will not participate.
In your attack, the Task Giver/Solver is trying to get a bogus computation onto the blockchain?
If so, then TrueBit could adjust the tax rate/jackpot payouts to ensure that such an attacker loses money in the long run.
Who would be harmed by such an attack? (Clearly, not the Task Giver.) The obvious victims would be those that mine the blockchain looking for solutions to tasks that have have already been proposed. Once TrueBit is in production, do you foresee this population being large? Are there other potential victims that I am not seeing?
Wouldn't this allow for bogus answers on the ETH Blockchain -- As a result -- no application could actually trust the results from Truebit, resulting in an ineffective protocol for certain applications. For 3rd party applications like Livepeer where they are submitting the tasks, there is no incentive to cheat. Also - couldn't a Task Giver sybil by submitting tasks continuously, solving themselves at no cost and then eventually drain the jackpot via winning forced error -
p(x,y) is just some carefully chosen probability that depends on x and y. Carefully chosen indeed... I was too lazy to compute it lol
One cannot necessarily trust tasks that originate from smart contracts. To use the Livepeer example, let's assume that a smart contract binds a Viewer to pay for whatever transcoding task that a Broadcaster submits to it and that the smart contract issues the transcoding task to TrueBit. If the Broadcaster is the only one who can see the task, then he may lazily and incorrectly perform the transcoding task and then, per my argument above, obtain a reward for such work because rational Verifiers don't show up to check it. The situation actually worse than I initially described above because a challenging Verifier has negligible chance of winning the verification game when she can't properly perform the binary search.
Got it -- was thinking of Livepeer as a 3rd party submitting to Truebit - but you're completely correct. Livepeer is made up of decentralized anonymous parties also
Metering could be used to prevent any negative side effects of this. When a Task Giver submits a task they also submit the reward they are willing to pay, this could be thought of as Truebit gas. Solver's and Verifier's should only read the file up to a certain point. This is assuming the input stream's count as computation steps (which they should because they are changing memory).
This also means a Solver could still prove a verifiable answer (in this case at the end of the computation). Except, that it might not be the answer the Task Giver was hoping for.
This is basically another form of a DOS attack. The best way to prevent this is to charge for each computation just like Ethereum does.
@truebitrobbie wrote:
Wouldn't this allow for bogus answers on the ETH Blockchain -- As a result -- no application could actually trust the results from Truebit...
I agree with the antecedent, but not with the conclusion, which I think should be: an application could not trust the results from TrueBit if that application were not the task giver.
These bogus-computation-on-the-blockchain attacks can be divided into two categories:
-
those in which the task giver is a willing participant, and
-
those in which the task giver is an innocent victim.
While both are undesirable, the latter are clearly far worse. And the attacks described above fall squarely into that first category.
Perhaps TrueBit could tolerate some attacks of the first kind, especially if they were associated with an approach for which no better alternative existed.
@truebitrobbie also wrote:
Also - couldn't a Task Giver sybil by submitting tasks continuously, solving themselves at no cost and then eventually drain the jackpot via winning forced error -
If my math is right then capping the jackpot for a task t at (the tax for t divided by the forced error rate) should cause such a task giver to lose money in the long run.
@teutsch wrote:
To use the Livepeer example, let's assume that a smart contract binds a Viewer to pay for whatever transcoding task that a Broadcaster submits to it and that the smart contract issues the transcoding task to TrueBit. If the Broadcaster is the only one who can see the task, then he may lazily and incorrectly perform the transcoding task...
Let me make sure that I understand:
-
A Viewer enters into a trust relationship with a Broadcaster.
-
The Broadcaster issues a transcoding task to TrueBit.
-
The Broadcaster poses as a solver and wins the election.
-
The Broadcaster does a poor job transcoding.
-
Verifiers are unable to access the task code and therefore unable to determine that the Broadcaster did a poor job.
-
The Viewer gets less than he paid for.
Is that about right? Because what is to stop the Broadcaster from literally disconnecting the content from the wall between steps 3 and 4? It strikes me as though TrueBit could at best help Livepeer solve this problem, but that TrueBit cannot solve the problem outright.
@hswick proposed metering as an alternative approach to dealing with large files. But I suspect that his approach would be subject to the same criticisms as my own, as it is not clear that his approach would deal with the following issue any differently:
- (AGREE) When a dispute arises and data has to be moved from off-chain to on-chain to resolve the dispute, how do you make it impossible, unprofitable, or otherwise undesirable for the parties to disagree as to the value of the on-chain data?
What alternatives approaches are there that deal with (AGREE) differently?
Livepeer transcoding is done in real time, but verification of the transcoding is not.