mirror of
https://github.com/lux-apps/papers.git
synced 2026-10-30 18:15:21 +00:00
zeekay
1ecc25e9cf
The seven engine specifications (lux-{photon,wave,nova,nebula,prism,ray,field}-protocol)
were fragmented short notes documenting layers of the same Quasar consensus stack.
This commit merges them into a single canonical reference, lux-consensus-engines.tex,
that uses one preamble, one set of theorems, one bibliography, and one composition
chapter showing how the engines layer into the LP-020 finality pipeline.
The seven originals are reduced to single-page breadcrumb stubs pointing at the
consolidated paper; their sections/ content is preserved on disk for git history.
- new: lux-consensus-engines/ (50 pages, 646KB PDF, ~2900 lines tex)
- breadcrumbs: each original keeps cover + title + stub paragraph naming its chapter
- composition: chapter 9 records the layered contract Photon < Wave < Nova < ...
- bibliography: consolidated from the seven original thebibliography blocks
101 lines
3.6 KiB
TeX
101 lines
3.6 KiB
TeX
\section{The Wave Protocol}
|
|
|
|
\label{sec:wave-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-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:wave-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-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:wave-params}
|
|
\end{table}
|
|
|
|
%% -----------------------------------------------------------------------
|
|
%% 4. CONFIDENCE MONOTONICITY ANALYSIS
|
|
%% -----------------------------------------------------------------------
|