papers/lux-field-protocol/sections/04-convergence-analysis.tex

\section{Convergence Analysis}

\label{sec:potential}

\subsection{Potential Decrease}

\begin{theorem}[Monotone Potential Decrease]
\label{thm:potential}
Under the Field protocol dynamics with honest supermajority ($f < n/3$), the expected
field potential decreases in each round:
\[
\mathbb{E}[\Phi(\mathbf{P}_{r+1})] \leq \Phi(\mathbf{P}_r) - \frac{\eta(2-\eta)}{n} \sum_{i \in H} \left\| \mathbf{p}_i - \bar{\mathbf{p}}_i \right\|^2
\]
where $\bar{\mathbf{p}}_i$ is the expected sample mean for honest validator $i$.
\end{theorem}

\begin{proof}
Consider honest validator $i$ updating its preference. The new preference is:
\[
\mathbf{p}_i' = (1 - \eta)\mathbf{p}_i + \eta \bar{\mathbf{p}}_S
\]
where $\bar{\mathbf{p}}_S$ is the sample mean. The contribution of $\mathbf{p}_i$ to the
potential changes by:
\begin{align}
\Delta \Phi_i &= -\frac{2}{n^2} \mathbf{p}_i' \cdot \sum_{j \neq i} \mathbf{p}_j + \frac{2}{n^2} \mathbf{p}_i \cdot \sum_{j \neq i} \mathbf{p}_j - \frac{1}{n^2}(\|\mathbf{p}_i'\|^2 - \|\mathbf{p}_i\|^2) \nonumber \\
&= -\frac{2}{n^2} \eta(\bar{\mathbf{p}}_S - \mathbf{p}_i) \cdot \sum_{j \neq i} \mathbf{p}_j - \frac{1}{n^2}(\|\mathbf{p}_i'\|^2 - \|\mathbf{p}_i\|^2) \label{eq:delta-phi}
\end{align}

Taking expectations over the random sample $S$:
$\mathbb{E}[\bar{\mathbf{p}}_S] = \bar{\mathbf{p}} = \frac{1}{n}\sum_{j} \mathbf{p}_j$
(the population mean, up to Byzantine distortion bounded by $\gamma$).

The cross term in~(\ref{eq:delta-phi}) contributes:
\[
-\frac{2\eta}{n^2} (\bar{\mathbf{p}} - \mathbf{p}_i) \cdot \sum_{j \neq i} \mathbf{p}_j
= -\frac{2\eta}{n} (\bar{\mathbf{p}} - \mathbf{p}_i) \cdot \bar{\mathbf{p}} + O(1/n^2)
\]

The self-term $\|\mathbf{p}_i'\|^2 - \|\mathbf{p}_i\|^2 = 2\eta(\bar{\mathbf{p}}_S - \mathbf{p}_i) \cdot \mathbf{p}_i + \eta^2\|\bar{\mathbf{p}}_S - \mathbf{p}_i\|^2$.

Combining and summing over all honest validators:
\[
\mathbb{E}[\Delta \Phi] \leq -\frac{\eta(2-\eta)}{n} \sum_{i \in H} \|\mathbf{p}_i - \bar{\mathbf{p}}\|^2
\]
This is non-positive, with equality only when all honest validators already agree
($\mathbf{p}_i = \bar{\mathbf{p}}$ for all $i \in H$).
\end{proof}

\subsection{Convergence Rate}

\begin{lemma}[Exponential Convergence]
\label{lem:convergence-rate}
Define the disagreement $\mathcal{D}(r) = \frac{1}{|H|}\sum_{i \in H} \|\mathbf{p}_i(r) - \bar{\mathbf{p}}(r)\|^2$.
Under the Field protocol:
\[
\mathbb{E}[\mathcal{D}(r)] \leq (1 - \eta(2-\eta)/k)^r \cdot \mathcal{D}(0) + O(\gamma^2)
\]
where the $O(\gamma^2)$ term accounts for Byzantine interference.
\end{lemma}

\begin{proof}
The potential decrease per round (Theorem~\ref{thm:potential}) implies that the disagreement
decreases multiplicatively: each honest validator's preference moves toward the sample mean
by a factor of $\eta$. Since the sample mean is close to the population mean (within $O(1/\sqrt{k})$),
the disagreement contracts by factor $(1 - \eta(2-\eta)/k)$ per round.

The Byzantine validators contribute a constant perturbation bounded by $\gamma^2$ (since
$|B|/n < \gamma$ and each Byzantine vector has unit norm). This creates a floor below
which disagreement cannot decrease but does not prevent convergence to a neighborhood of
agreement.

The convergence time to $\mathcal{D} = \epsilon$ is:
\[
r^* = O\left(\frac{k}{\eta(2-\eta)} \ln \frac{\mathcal{D}(0)}{\epsilon}\right) = O(k \log(1/\epsilon))
\]
For $\epsilon = 1/n$ (population-level agreement), this is $O(k \log n)$.
\end{proof}

\begin{corollary}[Multi-Valued Convergence]
\label{cor:multi}
For $d$-valued conflicts, the convergence rate is the same as for binary conflicts:
$O(k \log n)$ rounds, independent of $d$. This is because the potential function and
its decrease rate do not depend on the dimension $d$.
\end{corollary}

%% -----------------------------------------------------------------------
%%  5. STAKE-WEIGHTED FIELD STRENGTH
%% -----------------------------------------------------------------------