papers/lux-wave-protocol/sections/06-dag-strong-preference-monotonicity.tex

\section{DAG Strong Preference Monotonicity}

\label{sec:dag}

\subsection{Monotone Predicate}

\begin{theorem}[Strong Preference Monotonicity]
\label{thm: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: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: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: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: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: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
%% -----------------------------------------------------------------------