papers/lux-wave-protocol/sections/07-byzantine-fault-tolerance.tex

\section{Byzantine Fault Tolerance}

\label{sec:byzantine}

\subsection{Adversarial Influence on Sampling}

A Byzantine adversary controlling fraction $\gamma < 1/3$ of validators can influence
the sampling process in two ways:
\begin{enumerate}[nosep]
\item \textbf{Equivocation}: Respond with different colors to different queries.
\item \textbf{Strategic silence}: Refuse to respond, forcing resampling.
\end{enumerate}

\begin{theorem}[Byzantine Safety]
\label{thm:byz-safety}
Under the Wave protocol with $f < n/3$ Byzantine validators, if two honest validators
$v_i$ and $v_j$ both finalize (i.e., some $d_c \geq \beta_1$), they finalize the same
color with probability at least $1 - 2 \cdot (q_0/q_1)^{\beta_1}$.
\end{theorem}

\begin{proof}
Suppose for contradiction that $v_i$ finalizes color 1 and $v_j$ finalizes color 0.
Then $d_1(v_i) \geq \beta_1$ and $d_0(v_j) \geq \beta_1$.

For $v_i$ to observe $\beta_1$ supermajority rounds for color 1, at least $\beta_1$ of
its samples must have $\geq \alpha k$ color-1 responses. Since samples include at least
$(1-\gamma)k$ honest validators in expectation, and honest validators respond consistently,
this requires the honest majority to prefer color 1 during those rounds.

Similarly, for $v_j$ to observe $\beta_1$ supermajority rounds for color 0, the honest
majority must prefer color 0 during those rounds.

But Theorem~\ref{thm:convergence} shows that the honest population converges to a single
color in $O(\log n)$ rounds. After convergence, the probability of sampling a supermajority
for the minority color is $q_0 < e^{-\Omega(k)}$. The probability that both events occur
(one validator sees $\beta_1$ supermajorities for each opposing color) is bounded by:
\[
\Pr[\text{safety violation}] \leq 2 \cdot q_0^{\beta_1} \leq 2 \cdot e^{-\Omega(k \beta_1)}
\]
For $k = 20$ and $\beta_1 = 11$, this is $2 \cdot e^{-\Omega(220)} \ll 2^{-128}$.
\end{proof}

\subsection{Liveness Under Byzantine Faults}

\begin{lemma}[Wave Liveness]
\label{lem:liveness}
Under partial synchrony, the Wave protocol achieves liveness after GST: every submitted
valid transaction is eventually finalized.
\end{lemma}

\begin{proof}
After GST, messages are delivered within $\Delta$. An honest validator initiating a query
receives $\geq k - f$ honest responses within $\Delta + \text{round time}$. Since
$k - f > \alpha k$ for appropriate $k$ and $\alpha$ (e.g., $k = 20$, $f \leq 6$, $\alpha k = 16$),
honest responses alone can form a supermajority. The honest majority ensures convergence
(Theorem~\ref{thm:convergence}), and once converged, the confidence counter reaches $\beta_1$
in $O(\beta_1)$ additional rounds (Lemma~\ref{lem:absorption}). Thus finalization occurs
in $O(\log n + \beta_1)$ rounds after GST.
\end{proof}

%% -----------------------------------------------------------------------
%%  8. EVALUATION
%% -----------------------------------------------------------------------