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.
72 lines
2.2 KiB
TeX
72 lines
2.2 KiB
TeX
\section{Bisection Protocol Implementation}
|
|
|
|
|
|
The practical implementation of the bisection protocol requires careful handling of state commitments, timeout mechanisms, and proof verification.
|
|
|
|
\subsection{Round Structure}
|
|
|
|
Each bisection round follows a structured format:
|
|
|
|
\begin{enumerate}
|
|
\item \textbf{Assertion Phase}: Defender provides midpoint state
|
|
\item \textbf{Verification Phase}: Challenger verifies midpoint
|
|
\item \textbf{Selection Phase}: Challenger selects disputed segment
|
|
\item \textbf{Timeout Phase}: Enforces progress
|
|
\end{enumerate}
|
|
|
|
\begin{figure}[h]
|
|
\centering
|
|
\begin{tikzpicture}[node distance=2cm, auto]
|
|
\node[draw, circle] (S0) {$S_0$};
|
|
\node[draw, circle, right=of S0] (Smid) {$S_{n/2}$};
|
|
\node[draw, circle, right=of Smid] (Sn) {$S_n$};
|
|
|
|
\draw[->, thick] (S0) -- node[above] {Round 1} (Smid);
|
|
\draw[->, thick] (Smid) -- node[above] {Dispute} (Sn);
|
|
|
|
\node[below=0.5cm of S0] {Start};
|
|
\node[below=0.5cm of Smid] {Midpoint};
|
|
\node[below=0.5cm of Sn] {End};
|
|
|
|
\draw[dashed, red, thick] (Smid) -- ++(0,-1.5) node[below] {Challenger selects};
|
|
\end{tikzpicture}
|
|
\caption{First round of bisection protocol}
|
|
\end{figure}
|
|
|
|
\subsection{State Commitment Scheme}
|
|
|
|
States are committed using a Merkle tree structure enabling efficient proofs:
|
|
|
|
\begin{equation}
|
|
\text{StateRoot} = \text{MerkleRoot}(\text{PC}, \text{Stack}, \text{Memory}, \text{Storage}, \text{GlobalState})
|
|
\end{equation}
|
|
|
|
This commitment allows proving specific parts of the state without revealing the entire state.
|
|
|
|
\subsection{Witness Data Structure}
|
|
|
|
For the final one-step proof, witness data includes:
|
|
|
|
\begin{lstlisting}[language=Solidity, caption=Witness Data Structure]
|
|
struct WitnessData {
|
|
bytes32 preStateRoot;
|
|
bytes32 postStateRoot;
|
|
bytes instruction;
|
|
bytes32[] memoryProof;
|
|
bytes32[] storageProof;
|
|
bytes32[] stackProof;
|
|
uint256 gasUsed;
|
|
}
|
|
\end{lstlisting}
|
|
|
|
\subsection{Timeout Mechanism}
|
|
|
|
To prevent griefing through non-participation:
|
|
|
|
\begin{equation}
|
|
\text{Timeout}_{\text{round}} = \text{BaseTimeout} \times 2^{\text{round}}
|
|
\end{equation}
|
|
|
|
This exponential backoff ensures the protocol completes even with delays while penalizing consistent non-participation.
|
|
|