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.
76 lines
2.8 KiB
TeX
76 lines
2.8 KiB
TeX
\section{Incremental State Sync}
|
|
\label{sec:incremental}
|
|
|
|
\subsection{Motivation}
|
|
|
|
Nodes that are temporarily offline (maintenance, network issues) need not re-download the entire state. Incremental sync transfers only the state delta between the node's last known state root $R_{\text{old}}$ and the current target $R_{\text{new}}$.
|
|
|
|
\subsection{State Diff Computation}
|
|
|
|
\begin{definition}[State Diff]
|
|
The state diff $\Delta(R_{\text{old}}, R_{\text{new}})$ consists of:
|
|
\begin{itemize}
|
|
\item Inserted keys: $\{k : k \in \text{Trie}(R_{\text{new}}) \setminus \text{Trie}(R_{\text{old}})\}$
|
|
\item Deleted keys: $\{k : k \in \text{Trie}(R_{\text{old}}) \setminus \text{Trie}(R_{\text{new}})\}$
|
|
\item Modified keys: $\{k : V_{R_{\text{old}}}(k) \neq V_{R_{\text{new}}}(k)\}$
|
|
\end{itemize}
|
|
\end{definition}
|
|
|
|
\begin{algorithm}[H]
|
|
\caption{Incremental Sync Protocol}
|
|
\label{alg:incremental}
|
|
\begin{algorithmic}[1]
|
|
\Require Local state root $R_{\text{old}}$, target root $R_{\text{new}}$
|
|
\State Request $\Delta(R_{\text{old}}, R_{\text{new}})$ from peer
|
|
\State Peer computes diff by traversing both tries simultaneously
|
|
\State Peer sends $\Delta$ with range proofs anchored at $R_{\text{new}}$
|
|
\State Apply insertions, deletions, and modifications to local trie
|
|
\State Recompute local root $R' \gets H(\text{updated trie})$
|
|
\If{$R' = R_{\text{new}}$}
|
|
\State Sync complete
|
|
\Else
|
|
\State Fall back to full state sync
|
|
\EndIf
|
|
\end{algorithmic}
|
|
\end{algorithm}
|
|
|
|
\subsection{Diff Size Analysis}
|
|
|
|
\begin{proposition}[Incremental Diff Size]
|
|
For a trie with $n$ leaves and $m$ modifications over $\tau$ blocks, the diff size is:
|
|
\begin{equation}
|
|
|\Delta| = O(m \cdot (L + d \cdot 32))
|
|
\end{equation}
|
|
where $L$ is the average leaf size and $d$ is the trie depth. The diff is independent of total state size $n$.
|
|
\end{proposition}
|
|
|
|
\begin{table}[H]
|
|
\centering
|
|
\caption{Incremental sync sizes for various staleness periods on Lux C-Chain.}
|
|
\label{tab:incremental}
|
|
\begin{tabular}{lrrr}
|
|
\toprule
|
|
\textbf{Staleness} & \textbf{Modified Accounts} & \textbf{Diff Size} & \textbf{Sync Time} \\
|
|
\midrule
|
|
1 hour & 50,000 & 8 MB & 3 s \\
|
|
1 day & 500,000 & 80 MB & 25 s \\
|
|
1 week & 2,000,000 & 320 MB & 90 s \\
|
|
1 month & 8,000,000 & 1.3 GB & 5 min \\
|
|
\bottomrule
|
|
\end{tabular}
|
|
\end{table}
|
|
|
|
\subsection{Diff Verification}
|
|
|
|
The incremental diff must be verified for correctness and completeness:
|
|
|
|
\begin{theorem}[Diff Verification]
|
|
An incremental diff $\Delta$ with proofs anchored at $R_{\text{new}}$ is verifiable if:
|
|
\begin{enumerate}
|
|
\item Each inserted/modified leaf is accompanied by a Merkle inclusion proof in $R_{\text{new}}$.
|
|
\item Each deleted leaf is accompanied by a Merkle exclusion proof in $R_{\text{new}}$.
|
|
\item Applying $\Delta$ to $\text{Trie}(R_{\text{old}})$ produces root $R_{\text{new}}$.
|
|
\end{enumerate}
|
|
\end{theorem}
|
|
|