papers/lux-wave-protocol/sections/04-confidence-monotonicity.tex

\section{Confidence Monotonicity}

\label{sec:analysis}

The central property of Wave is that confidence counters exhibit monotone behavior:
once a color establishes a lead, the lead tends to grow, making reversal exponentially
unlikely.

\subsection{Single-Round Dynamics}

Consider a single sampling round. Let $p$ be the fraction of honest validators
preferring color 1. The probability that a random sample of size $k$ yields a
supermajority of $\alpha k$ or more for color 1 is:

\begin{equation}
\Phi(p, k, \alpha) = \sum_{j = \lceil \alpha k \rceil}^{k} \binom{k}{j} p^j (1-p)^{k-j}
\label{eq:supermajority}
\end{equation}

\begin{lemma}[Supermajority Amplification]
\label{lem:amplification}
For $p > 1/2 + \epsilon$ with $\epsilon > 0$ and $\alpha \leq p$, the probability of
observing a supermajority for color 1 satisfies $\Phi(p, k, \alpha) > 1 - e^{-2k\epsilon^2}$
by the Chernoff bound. Conversely, the probability of observing a supermajority for
color 0 satisfies $\Phi(1-p, k, \alpha) < e^{-2k(p - (1-\alpha))^2}$.
\end{lemma}

\begin{proof}
Apply the multiplicative Chernoff bound. Let $X = \sum_{i=1}^{k} X_i$ where $X_i \sim \text{Bernoulli}(p)$.
Then $\mathbb{E}[X] = kp$. For $\alpha \leq p$:
\[
\Pr[X < \alpha k] = \Pr[X < (1 - \delta)\mathbb{E}[X]]
\]
where $\delta = 1 - \alpha/p$. By the Chernoff bound:
\[
\Pr[X < \alpha k] \leq \exp\left(-\frac{\delta^2 \mathbb{E}[X]}{2}\right) = \exp\left(-\frac{k(p - \alpha)^2}{2p}\right)
\]
For the supermajority for color 0, replace $p$ with $1-p$ and note that $1-p < 1/2 - \epsilon < 1-\alpha$
for typical parameterizations, yielding exponential decay.
\end{proof}

\subsection{Confidence Counter Drift}

\begin{theorem}[Confidence Monotonicity]
\label{thm:monotonicity}
Let $\Delta d(r) = d_1(r) - d_0(r)$ be the confidence lead of color 1 after round $r$.
If more than $2/3$ of validators are honest and the initial majority prefers color 1
(i.e., the fraction $p_0 > 1/2 + \gamma$ for some $\gamma > 0$), then:
\begin{enumerate}[nosep]
\item The expected drift is positive: $\mathbb{E}[\Delta d(r+1) - \Delta d(r)] > 0$.
\item The probability that color 0 ever catches up after a lead of $\delta$ satisfies:
\[
\Pr[\exists r' > r : d_0(r') \geq d_1(r')] \leq \left(\frac{q_0}{q_1}\right)^\delta
\]
where $q_c = \Phi(p_c, k, \alpha)$ is the probability of a supermajority for color $c$
with $p_1 > p_0$ being the honest population fractions.
\end{enumerate}
\end{theorem}

\begin{proof}
\textbf{Part 1.} In each round, the confidence counter for color 1 increments if
$\geq \alpha k$ sampled validators respond with color 1. This occurs with probability
$q_1 = \Phi(p_1, k, \alpha)$. Similarly, color 0 increments with probability
$q_0 = \Phi(1 - p_1, k, \alpha)$. Since $p_1 > 1/2 + \gamma$, by Lemma~\ref{lem:amplification},
$q_1 > q_0$ (the gap is exponential in $k\gamma^2$). Therefore:
\[
\mathbb{E}[\Delta d(r+1) - \Delta d(r)] = q_1 - q_0 > 0.
\]

\textbf{Part 2.} The process $\Delta d(r)$ is a random walk with positive drift $q_1 - q_0 > 0$.
By the classical gambler's ruin analysis, the probability of ever reaching $\Delta d = 0$
from $\Delta d = \delta$ is $\left(\frac{q_0}{q_1}\right)^\delta$ when $q_0 < q_1$.
This follows from the optional stopping theorem applied to the martingale
$M(r) = \left(\frac{q_0}{q_1}\right)^{\Delta d(r)}$.
\end{proof}

\begin{corollary}[Exponential Safety]
\label{cor:safety}
For $k = 20$, $\alpha = 0.8$, $n = 500$, and $f/n = 0.2$, the probability that a
finalized transaction (with $d_c \geq \beta_1 = 11$) is reversed is at most
$\left(\frac{q_0}{q_1}\right)^{11} < 2^{-128}$.
\end{corollary}

\begin{proof}
With $p_1 = 0.8$ (honest nodes converged), $q_1 = \Phi(0.8, 20, 0.8) \approx 0.6296$ and
$q_0 = \Phi(0.2, 20, 0.8) < 10^{-8}$. Thus $q_0/q_1 < 10^{-8}/0.63 < 2^{-23}$, and
$(q_0/q_1)^{11} < 2^{-253} \ll 2^{-128}$.
\end{proof}

\subsection{Convergence of Population Fractions}

The per-round dynamics of the population fraction $p$ (fraction preferring color 1)
follow the map:

\begin{equation}
p_{r+1} = p_r \cdot \Phi(p_r, k, \alpha) + (1 - p_r) \cdot (1 - \Phi(1 - p_r, k, \alpha))
\label{eq:population}
\end{equation}

\begin{theorem}[Exponential Convergence]
\label{thm:convergence}
If $p_0 > 1/2 + \epsilon$ for any $\epsilon > 0$, then after $r = O(\log n)$ rounds:
\[
p_r > 1 - e^{-\Omega(k \cdot 2^r \epsilon^2)}
\]
In particular, for $k = 20$ and $\epsilon = 0.01$, we have $p_r > 1 - 10^{-6}$ after
$r = 12$ rounds.
\end{theorem}

\begin{proof}
Define $\epsilon_r = p_r - 1/2$. The map in Equation~\ref{eq:population} satisfies, for
$p_r$ near 1/2 with $\epsilon_r > 0$:
\[
\epsilon_{r+1} \geq \epsilon_r \cdot \left(1 + c \cdot k \epsilon_r\right)
\]
for some constant $c > 0$ depending on $\alpha$. This follows from expanding $\Phi(p, k, \alpha)$
around $p = 1/2$ and using the central limit approximation to the binomial.
The recurrence $\epsilon_{r+1} \geq \epsilon_r(1 + ck\epsilon_r)$ exhibits superlinear growth,
reaching $\epsilon_r = \Omega(1)$ in $O(1/(k\epsilon_0))$ rounds. Once $\epsilon_r = \Omega(1)$,
Chernoff bounds give exponential convergence $1 - p_r < e^{-\Omega(k)}$ per additional round.
Since the initial perturbation need only exceed $1/\sqrt{n}$ (the natural fluctuation scale),
$O(\log n)$ rounds suffice from an arbitrary initial configuration.
\end{proof}

%% -----------------------------------------------------------------------
%%  5. MARKOV CHAIN MODEL
%% -----------------------------------------------------------------------