mirror of
https://github.com/lux-apps/papers.git
synced 2026-10-30 18:15:21 +00:00
zeekay
abf99d05fc
Restructured from flat .tex/.pdf files into per-paper subdirectories. Added Antje Worring as co-author on all papers. Synced PDFs to pdfs/ for download site.
65 lines
2.4 KiB
TeX
65 lines
2.4 KiB
TeX
\section{Fraud Proof Basics}
|
|
|
|
|
|
The fraud proof protocol enables efficient verification of disputed state transitions through a carefully designed challenge-response mechanism.
|
|
|
|
\subsection{Assertion Protocol}
|
|
|
|
When a sequencer makes an assertion about a state transition, they essentially claim:
|
|
|
|
\begin{proposition}[State Transition Assertion]
|
|
Given initial state $S_0$ and transaction sequence $\mathcal{T} = \{t_1, t_2, ..., t_n\}$, applying the state transition function yields final state $S_n$:
|
|
\begin{equation}
|
|
S_n = \text{STF}^n(S_0, \mathcal{T})
|
|
\end{equation}
|
|
where $\text{STF}^n$ denotes $n$ sequential applications of the state transition function.
|
|
\end{proposition}
|
|
|
|
\subsection{Challenge Mechanism}
|
|
|
|
Any party observing an invalid assertion can initiate a challenge by:
|
|
|
|
\begin{enumerate}
|
|
\item Computing the correct final state $S'_n$
|
|
\item Demonstrating $S'_n \neq S_n$
|
|
\item Staking collateral to back the challenge
|
|
\item Initiating the interactive dispute resolution protocol
|
|
\end{enumerate}
|
|
|
|
\subsection{Interactive Proof Protocol}
|
|
|
|
The proof protocol follows an interactive game where challenger and defender exchange messages to narrow the dispute:
|
|
|
|
\begin{algorithm}
|
|
\caption{Interactive Fraud Proof Protocol}
|
|
\begin{algorithmic}[1]
|
|
\State \textbf{Input:} Assertion $A = (S_0, S_n, \mathcal{T})$, Challenger $C$, Defender $D$
|
|
\State \textbf{Output:} Winner $\in \{C, D\}$
|
|
\State $\text{left} \gets 0$, $\text{right} \gets n$
|
|
\While{$\text{right} - \text{left} > 1$}
|
|
\State $\text{mid} \gets \lfloor(\text{left} + \text{right})/2\rfloor$
|
|
\State $D$ provides $S_{\text{mid}}$
|
|
\State $C$ computes expected $S'_{\text{mid}}$
|
|
\If{$S_{\text{mid}} = S'_{\text{mid}}$}
|
|
\State $\text{left} \gets \text{mid}$ \Comment{Disagreement in right half}
|
|
\Else
|
|
\State $\text{right} \gets \text{mid}$ \Comment{Disagreement in left half}
|
|
\EndIf
|
|
\EndWhile
|
|
\State Execute single step $\text{left} \rightarrow \text{right}$ on-chain
|
|
\State \textbf{return} Winner based on execution result
|
|
\end{algorithmic}
|
|
\end{algorithm}
|
|
|
|
\subsection{On-chain Resolution}
|
|
|
|
Once the dispute is narrowed to a single step, the Layer 1 contract executes that step to determine the winner:
|
|
|
|
\begin{equation}
|
|
\text{Winner} = \begin{cases}
|
|
\text{Defender} & \text{if } S_{\text{right}} = \text{STF}(S_{\text{left}}, t_{\text{left}}) \\
|
|
\text{Challenger} & \text{otherwise}
|
|
\end{cases}
|
|
\end{equation}
|
|
|