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
56 lines
2.5 KiB
TeX
56 lines
2.5 KiB
TeX
\section{DAG Strong Preference Monotonicity}
|
|
|
|
\label{sec:wave-dag}
|
|
|
|
\subsection{Monotone Predicate}
|
|
|
|
\begin{theorem}[Strong Preference Monotonicity]
|
|
\label{thm:wave-dag-monotone}
|
|
Let $\text{SP}(v, t, r)$ denote the event that transaction $t$ is strongly preferred
|
|
by validator $v$ at round $r$. Under the Wave dynamics with honest supermajority:
|
|
\[
|
|
\Pr[\text{SP}(v, t, r+1) \mid \text{SP}(v, t, r)] > 1 - e^{-\Omega(k)}
|
|
\]
|
|
That is, once a transaction becomes strongly preferred, it remains strongly preferred
|
|
with overwhelming probability.
|
|
\end{theorem}
|
|
|
|
\begin{proof}
|
|
Strong preference requires that $t$ and all ancestors $t' \in \mathcal{A}(t)$ are preferred.
|
|
By Definition~\ref{def:wave-strong-pref}, $\text{SP}(v, t, r)$ implies $d_1(v, t', r) > d_0(v, t', r)$
|
|
for all $t' \in \mathcal{A}(t) \cup \{t\}$. By Theorem~\ref{thm:wave-monotonicity}, each individual
|
|
confidence lead is maintained with probability $1 - (q_0/q_1)^{\delta}$ where $\delta \geq 1$.
|
|
|
|
For the strong preference to fail at round $r+1$, at least one ancestor must flip its
|
|
preference. The probability of any single ancestor flipping is at most $(q_0/q_1)$.
|
|
By a union bound over $|\mathcal{A}(t)|$ ancestors:
|
|
\[
|
|
\Pr[\lnot \text{SP}(v, t, r+1) \mid \text{SP}(v, t, r)] \leq |\mathcal{A}(t)| \cdot \frac{q_0}{q_1}
|
|
\]
|
|
Since $q_0/q_1 < e^{-\Omega(k)}$ once the population has converged (Theorem~\ref{thm:wave-convergence}),
|
|
and $|\mathcal{A}(t)| = O(\text{poly}(n))$, the bound $|\mathcal{A}(t)| \cdot e^{-\Omega(k)} = e^{-\Omega(k)}$
|
|
holds for any polynomially bounded DAG size.
|
|
\end{proof}
|
|
|
|
\subsection{Ancestor Propagation}
|
|
|
|
\begin{lemma}[Preference Propagation]
|
|
\label{lem:wave-propagation}
|
|
If transaction $t$ has depth $D$ in the DAG (longest path from $t$ to a root), then the
|
|
expected time for $t$ to become strongly preferred, given that all transactions at each
|
|
depth level converge independently, is at most $O(D + \log n)$ rounds.
|
|
\end{lemma}
|
|
|
|
\begin{proof}
|
|
Each conflict set at depth $d$ converges independently in $O(\log n)$ rounds
|
|
(Theorem~\ref{thm:wave-convergence}). The strong preference check for $t$ requires convergence
|
|
at all $D$ depth levels. Since conflicts at different depths are on disjoint UTXOs, their
|
|
Wave instances are independent. By a union bound, all $D$ levels converge within
|
|
$O(\log n + \log D)$ rounds with high probability. For typical DAG structures where
|
|
$D = O(\log n)$, this gives $O(\log n)$ total rounds.
|
|
\end{proof}
|
|
|
|
%% -----------------------------------------------------------------------
|
|
%% 7. BYZANTINE TOLERANCE
|
|
%% -----------------------------------------------------------------------
|