TrueBit forced errors approach – batch validation application

[folex]

This issue first gives some context on how does the forced error mechanism work in TrueBit (as described in A scalable verification solution for blockchains paper and wiki), then speculates about how forced errors could work in Fluence and finally poses the currently unsolved problem of hiding the correct result hash from verifiers.

Forced errors behavior in TrueBit

Initial assumption

It is assumed that Solvers and Verifiers are rational, so they make an action only if it is profitable for them. It should be noted that certain actions might be unprofitable within the system, but profitable in a greater arrangement. For example, if transactions transferring millions of dollars are forged, TrueBit might notice and punish malicious Solvers, but it's still profitable for them to supply a bogus solution.

Solver registration

In order to receive tasks each Solver should register itself in the TrueBit contract. On registration Solver supplies a deposit and a hash of private random bits r. Private random bits r are generated by the Solver before the registration and are used for deciding if the forced error state should be enabled.

Algorithm

In short, the algorithm can be described as following:

1. The Task Giver is the one who wants its task to be solved for a reward. It posts a task to the TrueBit contract specifying the minimum deposit, reward and the timeout for solving/verifying the task.

2. After that any Solver could bid itself on the task. Single suitable Solver is then chosen by a lottery and assigned to the task with the assignment recorded in the TrueBit contract.

   Note that the lottery is performed naturally when miners select one of the concurrent transactions sent to the TrueBit contract. A sender of the chosen transaction is selected as a Solver. It is still an open question however – see How is the Solver selected exactly? in the TrueBit's Open Problems list.

3. If the Solver has solved the task within the specified timeout, it submits an array of two hashes (which is called soln_hashes) to the contract: hash(correct solution) and hash(incorrect solution) where correct and incorrect result might go in any order.

4. Once the transaction with the submission is mined and included in some block, Solver knows if the forced error is in effect and calls designate method in the TrueBit contract passing hash(index || r) as an input. The index variable can take 0 or 1 value and is the position in soln_hashes array. This way the Solver is committing itself on which hash in the soln_hashes array should be treated as correct one. The Solver, however, is not revealing which hash was designated at this moment.

   Note that the designated hash might not always be the correct one. If the forced error is in effect, the Solver will designate the hash of the incorrect solution to be treated as a correct one. If there is no forced error in effect, the Solver should designate the correct solution.

5. Then any Verifier who has found one or two incorrect solutions in soln_hashes should publish a hash of a certain number v to the TrueBit contract within the specified timeout. v designates which hash in soln_hashes is deemed incorrect by the Verifier. If v mod 3 == 0 it means the first hash is deemed incorrect and v mod 3 == 1 – the second one. If v mod 3 == 2 it means that both hashes are marked incorrect by the Verifier.

6. If the forced error is in effect, challenged Solver reveals private random bits r to prove that it specifically designated an incorrect solution because of the forced error. In this case the Verifier can easily verify that another solution in the soln_hashes array is actually correct.

Forced error detection

The forced error is in effect if random bits hash(r || block hash) is less than forced error rate constant defined in the TrueBit contract. They should not be confused with private random bits r which is the Solver's private bits generated when it has registered in the contract.

It's important to note that neither Solver nor Verifiers know if the forced error is in effect in the beginning:

1. The Solver knows if the forced error is in effect only after the transaction with the submitted solutions is mined and placed into some block. At that point, the Solver knows the block hash so it is able to calculate random bits hash(r || block_hash) learning if the forced error is in effect.
2. Verifiers learn if the forced error is in effect only after the challenged Solver reveals its r in order to prove that an incorrect solution was selected because of the forced error. This is done by the Solver to avoid being penalized.

TrueBit paper states this in 4.4 Generating forced errors:

In order to motivate verification of all tasks and to guard the jackpot repository against swindle, forced errors must appear unpredictably. < ... > The system derives its unpredictability via the following properties.

1. The Task Giver does not know the random bits at the time that it announces a task.
2. The Solver does not know the random bits until after he has committed his solution.
3. Verifiers do not know the random bits until after they decide whether to challenge.

Jackpot repository

Once Verifier succesfully challenges a task with the forced error in effect it receives a big payout which is called a jackpot payout. This payout is coming from a jackpot repository – i.e. a separate TrueBit contract that holds big enough amount of money and pays some of them to Verifiers in the case of the forced error.

That contract is supplied with the money collected through taxes from Task Givers who pay these taxes along with the reward for a submitted Task and also from forfeiting deposits of misbehaving actors. For example, a Solver producing incorrect results will lose its deposit. In this case the half of this deposit will go to the jackpot repository while up to the whole other half will be paid to the Verifier who won a challenge against that Solver.

Possible attacks

The Solver might share with Verifiers whether the forced error is in effect

Attack

This might be done in different ways, for example:

• if the Solver and the Verifier are controlled by the same entity (e.g. we have a Sybil attack)
• if the Solver could tell the Verifier if the forced error is in effect through a side channel
• if the Solver always submits hash(0) of the incorrect result – in this case if hash(0) is designated as a solution it's obvious that the forced error is in effect
• if the Solver always places the correct solution first and the incorrect one – second in the soln_hashes array

My understanding of TrueBit defence

To deal with this attack it seems that TrueBit proposes this is where Solvers rationality should come into play. Since the Solver knows if there is a forced error before any of Verifiers, it could (and would) challenge itself in the case of forced error and receive a jackpot payout. Moreover, TrueBit assumes that Solver will always challenge itself and receive a jackpot payout in the case of forced error, so there is no usual reward in that case.

Now, to understand the Solver's reasoning let's look at how the jackpot payout is calculated in TrueBit. For each task there is a possible jackpot payout J wich is bounded by 1/3 of the total jackpot repository and scaled for the task difficulty to equally incentivize solving complex and simple tasks. While J is the upper bound on the payout the actual payout is dependent on the total number of challenges submitted for the task. With each new challenge the payout gets exponentially decreased and is defined as J / 2 ^ (k - 1) where k is the number of submitted challenges.

Since the jackpot payout decreases exponentially with each new challenger the Solver doesn't have any economic reason to reveal the forced error state to anyone and is heavily incentivized to keep it in secret.

[NOT SOLVED] The Task Giver might set an unrealistically low timeout

Attack

It might happen that the Task Giver specifies a timeout which is too short. It might even make the timeout so short that the Solver won't ever be able to complete the computation correctly within that time. In this case the Solver's deposit will be slashed – so the Task Giver could slash innocent Solvers losing nothing but transaction fees. Ideally the Solver could make an assessment of the task difficulty, but that's not really possible for non-trivial tasks without the actual execution.

[UNCLEAR] The Solver might try to push bogus solutions through by publishing forced error state

Attack

This attack is similar to Scaring off Verifiers attack described in 5.2 The trifecta in the TrueBit paper.

The Solver might publish whether the forced error is in effect. In this case it will forfeit the jackpot but still receive rewards. Validators might learn about the forced error state and challenge only tasks with the forced error in effect ignoring all other tasks solved by this Solver. This way the Solver might submit an incorrect solution when there is no forced error and no Verifier will check it.

Potential defence

As of my understanding, it sounds unrealistic, because it's not necessary that Verifiers would listen to some public information and obey it. It also seems that TrueBit also states it's profitable for Verifiers to catch non-forced errors too, slashing malicious Solver's deposit and receiving at most the half of it. So, even if some of Verifiers would follow the "challenge only when found the forced error", it would be enough for one Verifier to challenge that Solver.

Reflection

Intuitively, it's unclear why we need forced errors mechanic if Verifiers will perform a verification even when forced errors and jackpot payouts are effectively shut down for the malicious Solvers solutions. Arbitrum: Scalable, private smart contracts seems to have a more formal analysis on this matter.

Applying forced errors in Fluence network

Differences and similarities between Fluence and TrueBit

In Fluence network the Client acts as a Task Giver. The difference is that in TrueBit the Task Giver submits batch tasks through Ethereum contract, but in Fluence the Client sends a number of requests directly to the real-time cluster demanding low (less than few seconds) response time.

The Solver role is almost the same but is played not by a single machine, but by a Cluster of Solvers using Tendermint to reach the BFT consensus. Every request that is modifying the state causes a Tendermint transaction, which is eventually included into the Tendermint block.

Every time the block is processed by the Cluster, it changes the Cluster state. The new state can actually be considered the result of the computation similar to the batch computation result obtained in TrueBit.

Because the Cluster of Solvers is driven by a consensus mechanism and every Solver in it chooses the same decision, we will refer to it simply as the Cluster like it was a single entity. Additionally, the Cluster also stores the computation results in a decentralized deep storage like Swarm or IPFS. This allows batch validators to check computations later on without the need to interact with the real-time Cluster.

Validators in Fluence network behave pretty much the same as Verifiers in TrueBit.

Algorithm

1. Once VM has processed all requests coming from the Client it will have a state S which is considered a result of the computation. Without loss of generality we can state that each request is responded by the Cluster to the Client with the result R.

2. For each block the cluster generates private random bits r. The Cluster stores a pair of hashes H_c = hash(S) and H_w = hash(some random number) which are correct and incorrect hashes respectively in the deep storage. Those hashes might be stored in any order similar to how this is done in TrueBit. The Cluster storeshash(r) along with H_c and H_w.

   Caveat: here we also assume there is no way to derive H_c or H_w from R – see below for the Correct state hash disclosure problem.

3. The Cluster commits hashes H_c, H_w and hash(r) to the Contract by sending a checkpoint transaction.

4. Contract stores the hashes alongside with the current Ethereum block hash at the moment the checkpoint transaction has arrived.

5. Once the checkpoint transaction is mined, the Cluster checks the block hash and calculates if the forced error should be in effect in the same way as it's done in TrueBit: hash(r || Ethereum block hash) < forced error rate.

6. The Cluster writes the new state to the deep storage in which it designates either H_c or H_w as a solution.

7. Validators are notified by the Contract that there is the new work to check.

8. Chosen Validator downloads a block and waits for the designation.

9. If the Validator wishes to challenge, it publishes hash(v) where v mod 3 == 0 means the first hash is incorrect, v mod 3 == 1 – second, v mod 3 == 2 – both similar to how it's done in TrueBit.

10. The Cluster reveals r to prove that forced error was or was not in effect for the block. This is also similar to TrueBit.

11. The Validator should now have:

• the block hash, verifiable by Contract since it has stored it at the step 3

• the proof that Cluster committed to specific r which would be S_r from the step 9

• the proof that Validator has committed validation results

  That should be enough for Contract to decide if Validator really checked for a forced error and should be paid amplified reward. So Validator submits these values to Contract in order to claim forced error payout.

12. Contract checks values correctness and send money to the Validator

Open problems

Correct state hash disclosure

Since the Client receives the correct response R almost immediately, it can share it with Validators, so the latter gather enough information from the shared response to know if there is the forced error in effect so they could stop validating all the other computations. This would render forced errors useless.

For example, let's assume that the Cluster returns the entire state S to the client in response: R == S. In this case the Client/Validator pair could compute the hash(R), compare it to H_c == hash(S) and H_w == hash(some random number) and instantly know which result is the correct one.

So, the question is how to obfuscate H_c and H_w that the validator knowing R would not be able to to guess the correct hash.

Potentially this could be done by computing H_c as not just hash(S) but as hash(S || computation execution fingerprint), where the computation execution fingerprint is not revealed to the Client. For example, we could randomly sample instructions from the execution similar to how it's done in Proof of Independent Execution. In this case the Validator would have to actually repeat the computation to be able to find the incorrect hash from H_c/H_w pair.