papers/lux-wave-protocol/sections/03-the-wave-protocol.tex

\section{The Wave Protocol}

\label{sec:protocol}

\subsection{Protocol State}

Each validator $v$ maintains the following state for each known transaction $t$:
\begin{itemize}[nosep]
\item $\text{col}(v, t) \in \{0, 1, \bot\}$: current color preference ($\bot$ if undecided)
\item $d_c(v, t) \in \mathbb{N}_0$ for each color $c$: confidence counter for color $c$
\item $\text{accepted}(v, t) \in \{\text{true}, \text{false}\}$: finality flag
\end{itemize}

The key distinction from Flare is that Wave maintains \emph{separate} counters $d_0$ and
$d_1$ for each color, and the node's preference is always the color with the highest
confidence: $\text{col}(v, t) = \arg\max_c d_c(v, t)$.

\subsection{Core Protocol}

\begin{algorithm}[H]
\caption{Wave Protocol --- Core Sampling Loop}
\label{alg:wave-core}
\begin{algorithmic}[1]
\Require Validator $v$, transaction $t$ with conflict set $\mathcal{C}(t) \neq \emptyset$
\Require Parameters: $k$ (sample size), $\alpha$ (quorum fraction), $\beta_1$ (acceptance threshold)
\State Initialize $d_c \gets 0$ for all colors $c$
\State Initialize $\text{col}(v, t) \gets$ color of first-seen transaction in $\mathcal{C}(t) \cup \{t\}$
\While{$\lnot \text{accepted}(v, t)$}
    \State $S \gets \text{RandomSample}(V \setminus \{v\}, k)$ \Comment{sample $k$ validators uniformly}
    \State Query each $u \in S$ for $\text{col}(u, t)$
    \For{each color $c$}
        \State $n_c \gets |\{u \in S : \text{col}(u, t) = c\}|$
        \If{$n_c \geq \alpha k$} \Comment{supermajority for color $c$}
            \State $d_c \gets d_c + 1$
        \EndIf
    \EndFor
    \State $\text{col}(v, t) \gets \arg\max_c d_c$ \Comment{prefer highest confidence}
    \If{$\exists c : d_c \geq \beta_1$}
        \State $\text{accepted}(v, t) \gets \text{true}$
        \State Finalize transaction with color $c$
    \EndIf
\EndWhile
\end{algorithmic}
\end{algorithm}

\subsection{DAG Strong Preference}

Transaction finalization requires not just local preference but \emph{strong preference}
through the DAG ancestry.

\begin{definition}[Strong Preference]
\label{def:strong-pref}
Transaction $t$ is \emph{strongly preferred} by validator $v$ if:
\begin{enumerate}[nosep]
\item $\text{col}(v, t) = 1$ (the transaction itself is preferred), and
\item For every ancestor $t' \in \mathcal{A}(t)$, the transaction $t'$ is preferred:
$\text{col}(v, t') = 1$ or $\mathcal{C}(t') = \emptyset$ (no conflict).
\end{enumerate}
\end{definition}

\begin{algorithm}[H]
\caption{Wave DAG Strong Preference Check}
\label{alg:wave-dag}
\begin{algorithmic}[1]
\Function{IsStronglyPreferred}{$v$, $t$}
    \If{$\text{col}(v, t) \neq 1$}
        \Return \textbf{false}
    \EndIf
    \For{each $t' \in \text{TopologicalSort}(\mathcal{A}(t))$} \Comment{ancestors in order}
        \If{$\mathcal{C}(t') \neq \emptyset$ \textbf{and} $\text{col}(v, t') \neq 1$}
            \Return \textbf{false} \Comment{some ancestor not preferred}
        \EndIf
    \EndFor
    \Return \textbf{true}
\EndFunction
\end{algorithmic}
\end{algorithm}

\subsection{Protocol Parameters}

\begin{table}[h]
\centering
\begin{tabular}{@{}lll@{}}
\toprule
\textbf{Parameter} & \textbf{Symbol} & \textbf{Typical Value} \\
\midrule
Sample size & $k$ & 20 \\
Quorum fraction & $\alpha$ & 0.8 \\
Acceptance threshold & $\beta_1$ & 11 \\
Validator count & $n$ & 100--1000 \\
Byzantine fraction & $f/n$ & $< 1/3$ \\
\bottomrule
\end{tabular}
\caption{Wave protocol parameters}
\label{tab:params}
\end{table}

%% -----------------------------------------------------------------------
%%  4. CONFIDENCE MONOTONICITY ANALYSIS
%% -----------------------------------------------------------------------