papers/lux-state-sync/sections/08-checkpoint-verification.tex

\section{Checkpoint Verification}
\label{sec:checkpoint}

\subsection{Consensus-Based Checkpoints}

The syncing node must verify that the target state root $R$ is part of a legitimately finalized block. This is done by verifying a BLS aggregate signature from the validator set:

\begin{algorithm}[H]
\caption{Checkpoint Verification}
\label{alg:checkpoint}
\begin{algorithmic}[1]
\Require Block header $B = (h, R, \ldots)$, signature $\sigma_B$, validator set $\mathcal{V}$
\State $\mathsf{apk} \gets \sum_{i \in \mathcal{Q}} \mathsf{pk}_i$ where $\mathcal{Q}$ is the signer set
\State Verify $\sum_{i \in \mathcal{Q}} w_i \geq 2W/3$
\State Verify $e(\sigma_B, g_2) = e(H(B), \mathsf{apk})$
\If{all checks pass}
    \State Accept $R = B.\mathsf{stateRoot}$ as sync target
\Else
    \State Reject; try different checkpoint
\EndIf
\end{algorithmic}
\end{algorithm}

\subsection{Checkpoint Chain}

For initial sync, the node needs a trusted genesis validator set. From genesis, it verifies a chain of epoch transitions:

\begin{equation}
    \mathcal{V}_0 \xrightarrow{\sigma_0} \mathcal{V}_1 \xrightarrow{\sigma_1} \cdots \xrightarrow{\sigma_{e-1}} \mathcal{V}_e
\end{equation}

Each transition is authenticated by $\geq 2/3$ of the current epoch's validators.

\begin{proposition}[Checkpoint Chain Verification Cost]
Verifying a chain of $e$ epoch transitions requires $e$ BLS aggregate signature verifications, taking $O(e)$ time with constant factors $\leq 2$ ms per verification.
\end{proposition}

For a chain spanning 1,000 epochs ($\approx 3$ years at daily epochs): verification takes $< 2$ seconds.