Fraud Proofs

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

$f\left(S\right)=S^{\prime }$

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 $S^{\prime }$ correctly.

Fortunately, this flaw can be mitigated with .

What are Optimistic Assumptions?

Instead of computing $S\to S^{\prime }$ on-chain, a smart contract can delegate the computation to an off-chain entity. The off-chain entity computes $S^{\prime }$ 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 $S^{\prime }$ is incorrect, the system will reject $S^{\prime }$.

• Otherwise, after the challenge period closes, the system lazily assumes that$S^{\prime }$ is correct, and accepts the computed value.

What are Fraud Proofs?

Fraud proofs is an on-chain proof that verifies $S\to S^{\prime }$ is incorrect. The most naive way to implement a fraud proof scheme is to implement the entire logic of $f$ on-chain.

Like before, $S^{\prime }$ is first computed off-chain and proposed to the system. Then, to challenge $S^{\prime }$, a challenger can trigger the system to compute $f\left(S\right)$ on-chain.

• If $f\left(S\right)\ne S^{\prime }$, the challenge succeeds and the system will reject $S^{\prime }$.

• Otherwise, the challenge fails.

This way, the expensive computation of $f$ is only executed when needed, and gas is only paid when a challenger is certain that the proposed $S^{\prime }$ is incorrect.

Interactive Fraud Proofs

The naive fraud proof we outlined works, but it is inefficient since it requires the complete on-chain execution of $f$ 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 $f$ into $n$ steps.

$S\to S_1\to S_2\to ...\to S_{n-1}\to S^{\prime }$

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.

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

2. The defender then responds one of two ways. If the defender agrees with the proposed $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.

$S_x\to S_{x+1}$

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

This makes a significant difference the higher $n$ is. If $f$ 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.