Incentivizing challengers in optimistic settings

Challengers earn a reward (some portion of the prover's collateral) if they successfully challenge an optimistic proof. Let's look at the costs and rewards of the parties involved (ignoring network fees).

Prover (rollup)

Costs

• Computation costs (
  $P_{\mathsf{c}\mathsf{o}\mathsf{m}\mathsf{p}}$) - The cost of doing the required computation, which includes computing the actual "rolled up" state transition (new state
  $y=f(x)$, where
  $x$ are the input transactions).
  • In naysayer proofs, this also includes computing a SNARK
    $\pi$ that
    $y=f(x)$.
• Collateral (
  $P_{\mathsf{c}\mathsf{o}\mathsf{l}\mathsf{l}}$) - To disincentivize malicious/lazy provers. Will be returned if no successful challenge happens during the challenge period.

Rewards

• Rollup reward (orthogonal to this note, so I'm not going to talk about it) - This is similar to miner fees on the L1, and it's paid by rollup users to the prover(s) for their services

Challenger

Costs

• Observation costs (
  $C_{\mathsf{o}\mathsf{b}\mathsf{s}}$) - The cost to monitor whether the prover's reported results
  $y$ (or
  $\pi$) are correct.
  • In naysayer proofs, the observation cost is lower since it does not require re-computing
    $f$ (computationally expensive), but instead only running SNARK verification on
    $\pi$. This expands the potential challenger pool to other, resource-constrained parties, e.g., light clients.
• Collateral (
  $C_{\mathsf{c}\mathsf{o}\mathsf{l}\mathsf{l}}$) - A challenger must put down some collateral in order to challenge a result
  $y$, since resolving the dispute will require the involvement of the prover (bisection game).
  • In naysayer proofs, the dispute resolution process is non-interactive and does not require any action by the original prover. Therefore, the challenger does not need to cover any prover costs, only the on-chain costs of settling the dispute (the cost of the VerifyNay algorithm). This lowers the challenger collateral.
• Computation costs (
  $C_{\mathsf{c}\mathsf{o}\mathsf{m}\mathsf{p}}$) - The cost of the computation involved in creating a challenge.
  • In naysayer proofs, this is the cost of the Naysay algorithm.
• Submission costs (
  $C_{\mathsf{s}\mathsf{u}\mathsf{b}}$) - The cost of submitting the challenge on-chain.
  • In naysayer proofs, this is the cost of posting the naysayer proof
    ${\pi }_{\mathsf{n}\mathsf{a}\mathsf{y}}$ in calldata.

Rewards

• Prover collateral (
  $P_{\mathsf{c}\mathsf{o}\mathsf{l}\mathsf{l}}$) - If the challenge is deemed correct, the challenger receives the prover collateral (minus the amount spent to verify the challenge)

Why be a challenger?

Whether or not it's "worth it" to be a challenger (assuming rational, risk-neutral parties) depends on the above parameters. Roughly speaking, the rewards outweigh the costs if

$$P_{\mathsf{c}\mathsf{o}\mathsf{l}\mathsf{l}}-V>n_{\mathsf{o}\mathsf{b}\mathsf{s}}\cdot C_{\mathsf{o}\mathsf{b}\mathsf{s}}+n_{\mathsf{s}\mathsf{u}\mathsf{b}}\cdot (C_{\mathsf{c}\mathsf{o}\mathsf{m}\mathsf{p}}+C_{\mathsf{s}\mathsf{u}\mathsf{b}})$$

where

• $V$: the cost of verifying the challenge on-chain
• $n_{\mathsf{o}\mathsf{b}\mathsf{s}}=\mathbb{E}[\text{\# observations until success}]$: the expected number of observations before the challenger notices an incorrect result
• $n_{\mathsf{s}\mathsf{u}\mathsf{b}}=\mathbb{E}[\mathrm{\#}\text{submissions until success}]$: the expected number of submitted challenges until a challenge is submitted successfully. (This is because even if a party spots a faulty update, someone else may notice it too and also submit a challenge. So it may be that a challenger wastes work not only by observing, but by computing and submitting a challenge only to be beaten to the punch.)

A rational challenger should only submit correct challenges, so it should always expect to have its collateral returned.

Purely theoretically speaking, since

$n_{\mathsf{o}\mathsf{b}\mathsf{s}},n_{\mathsf{s}\mathsf{u}\mathsf{b}}$ increase as more challengers enter the system, the prover collateral will have to be high to incentivize challengers to expend resources on observation and challenging (

$C_{\mathsf{o}\mathsf{b}\mathsf{s}}$,

$C_{\mathsf{c}\mathsf{o}\mathsf{m}\mathsf{p}}$, and

$C_{\mathsf{s}\mathsf{u}\mathsf{b}}$).

In practice, challengers have some vested interest in the proper functioning of the system as a whole. That is, there is an additional positive term

$I$ on the left side of the inequality which allows

$P_{\mathsf{c}\mathsf{o}\mathsf{l}\mathsf{l}}$ to be lower.

Advantages of naysayer proofs

Naysayer proofs offer lower

$C_{\mathsf{o}\mathsf{b}\mathsf{s}}$ (and probably also

$V$,

$C_{\mathsf{c}\mathsf{o}\mathsf{m}\mathsf{p}}$ and

$C_{\mathsf{s}\mathsf{u}\mathsf{b}}$, but more precise analysis is needed), lowering the necessary magnitude of

$P_{\mathsf{c}\mathsf{o}\mathsf{l}\mathsf{l}}$ compared to "vanilla" optimistic proofs. This also has the effect of lowering the barrier of entry for challengers:

• Lower challenger collateral. Because dispute-resolution is non-interactive, challengers are not required to put up any collateral to challenge.
• Lower observation cost. The passive cost of monitoring the prover(s) for cheating is lower, since it requires only a SNARK verification (efficient) rather than recomputing the rollup's work
  $f$ (slow). This "democratizes" challenging by making it accessible to, e.g., end users with light clients.

There's no such thing as a free lunch, though, and these advantages come at the cost of increasing the burden on rollup services (provers), who must now additionally compute a SNARK (which is quite computationally expensive) and post it in blob data.

Other considerations

This note only discusses the collateral/rewards aspects of vanilla optimistic rollups vs. naysayer proofs. Another direction to explore is what effect the naysayer paradigm has on the length of the optimistic challenge period, which in vanilla rollups is generally set to 7 days and causes a significant usability burden (this is one of the main criticisms of optimistic rollups).