papers/lux-fraud-proofs/sections/06-one-step-proof-verification.tex

\section{One-Step Proof Verification}


The one-step proof is the ultimate arbiter of disputes, executing a single computational step on-chain to determine validity.

\subsection{EVM State Transition}

For EVM-based rollups, the one-step proof verifies a single opcode execution:

\begin{definition}[EVM State]
An EVM state $\mathcal{S}$ consists of:
\begin{align}
\mathcal{S} = \langle &\text{PC}, \text{Stack}, \text{Memory}, \text{Storage}, \\
&\text{Gas}, \text{ReturnData}, \text{Logs} \rangle
\end{align}
\end{definition}

\subsection{Memory and Storage Access}

Memory and storage operations require Merkle proofs to verify claimed values:

\begin{theorem}[Memory Access Verification]
A memory read at address $a$ returning value $v$ is valid if:
\begin{equation}
\text{VerifyProof}(\text{MemoryRoot}, a, v, \pi) = \text{true}
\end{equation}
where $\pi$ is a Merkle proof of inclusion.
\end{theorem}

\subsection{Witness Data Validation}

The witness must provide all data necessary to execute the disputed step:

\begin{algorithm}
\caption{One-Step Verification}
\begin{algorithmic}[1]
\State \textbf{Input:} PreState $S$, Instruction $I$, Witness $W$, PostState $S'$
\State \textbf{Output:} Valid $\in \{\text{true}, \text{false}\}$
\State Verify all Merkle proofs in $W$
\State Load required values from witness
\State Execute instruction $I$ with state $S$
\State Compute expected PostState $S''$
\State \textbf{return} $(S'' = S')$
\end{algorithmic}
\end{algorithm}

\subsection{Gas Constraints}

One-step verification must fit within Layer 1 gas limits:

\begin{equation}
\text{Gas}_{\text{verification}} \leq \text{Gas}_{\text{block}} \times \text{MaxGasRatio}
\end{equation}

This constrains the complexity of verifiable operations and influences rollup design.