Standalone

Interactive Fraud Proofs

close button

Part I

Fraud Proofs

Download quests in Questplay

View the contracts and any other additional content from your IDE.

Let us consider a system that needs to run some extremely expensive computation on-chain.

f(S)=Sf(S) = S'

Gas is costly and moving the computation off-chain could be economical. However, this would mean that the system would need to trust an off-chain entity to compute SS' correctly.

Fortunately, this flaw can be mitigated with .

What are Optimistic Assumptions?

Instead of computing SSS \rightarrow S' on-chain, a smart contract can delegate the computation to an off-chain entity. The off-chain entity computes SS' and submits the computed value to the contract. Then the contract opens a challenge period (e.g., 7 days).

  • In this challenge period, if anyone can prove on-chain that SS′ is incorrect, the system will reject SS'.

  • Otherwise, after the challenge period closes, the system lazily assumes thatSS' is correct, and accepts the computed value.

What are Fraud Proofs?

Fraud proofs is an on-chain proof that verifies SSS \rightarrow S′ is incorrect. The most naive way to implement a fraud proof scheme is to implement the entire logic of ff on-chain.

Like before, SS' is first computed off-chain and proposed to the system. Then, to challenge SS', a challenger can trigger the system to compute f(S)f(S) on-chain.

  • If f(S)Sf(S) \neq S', the challenge succeeds and the system will reject SS'.

  • Otherwise, the challenge fails.

This way, the expensive computation of ff is only executed when needed, and gas is only paid when a challenger is certain that the proposed SS' is incorrect.

Interactive Fraud Proofs

If you are unfamiliar with how a "binary search" works, we encourage you to give it a quick study first!

The naive fraud proof we outlined works, but it is inefficient since it requires the complete on-chain execution of ff during a challenge. Interactive fraud proving is a clever way to cheapen the gas costs of fraud proofs.

We first break down the computation of ff into nn steps.

SS1S2...Sn1SS \rightarrow S_1 \rightarrow S_2 \rightarrow ... \rightarrow S_{n-1} \rightarrow S'

When a challenge is initiated, the challenger and the defender will enter a two-party binary search (called a “bisection protocol”) to agree on the first execution step that they disagree on. This is the earliest step where the two parties agree on the previous state, but disagree on the next state.

We know this step exists because the two entities agree on SS, but disagree on S'S′.

  1. Consider the middle step. The challenger will first propose what they think SmidS_{mid} should be.

  2. The defender then responds one of two ways. If the defender agrees with the proposed Smid,S_{mid}, the search is narrowed to the left half of the search space. Otherwise, the defender disagrees, and the search is narrowed to the right half of the search space.

We recurse, repeating steps 1-2 until the search space is narrowed to a single step.

SxSx+1S_x \rightarrow S_{x+1}​

At this point, the challenger and defender have agreed on SxS_x, but disagreed on Sx+1S_{x+1}. This one step is then run on-chain to determine who is correct. Compared to the naive fraud proof which has nn steps, this interactive fraud proof only requires the execution of a single step on-chain.

This makes a significant difference the higher nn is. If ff is a million steps long (we did say it was expensive), interactive fraud proving only requires a couple of transactions, followed by the execution of a single step. This is a fraction of the gas cost of a naive fraud proof.

Your Task

Read the above description and understand how interactive fraud proofs work.

In the play, the Bandit King was a treacherous man. Not even his family was spared from the cruelty.