papers/lux-consensus/sections/02-background-and-related-work.tex

%% ===================================================================
%% LP-134 canonical naming (2025-12-15):
%% Per LP-134 (Lux Chain Topology), T-Chain has been split into:
%%   M-Chain — MPC ceremonies for bridge custody of EXTERNAL wallets
%%             (CGGMP21, FROST, Pulsar-general)
%%   F-Chain — FHE compute + TFHE bootstrap-key generation (encrypted EVM)
%% T-Chain is REMOVED entirely; teleport is B-Chain (bridgevm, LP-6000). No teleportvm.
%% Where this paper says "T-Chain MPC" / "T-Chain threshold governance" /
%% "T-Chain TFHE" / "T-Chain custody", read as M-Chain (MPC) or F-Chain (FHE).
%% ===================================================================

\section{Background and Related Work}

\label{sec:background}

\subsection{The Physics of Metastability}

The term ``metastable'' comes from statistical physics: a system is metastable when it rests
in a local energy minimum that is not the global minimum. A ball perched on a hilltop is in
an unstable equilibrium; a ball resting in a shallow valley partway down a slope is
metastable. Small perturbations cannot dislodge it, but large enough fluctuations will push
it into the global minimum~\cite{landau1980statistical}.

In consensus, metastability refers to configurations where a preference is nearly but not
quite dominant. The Wave family exploits this: repeated sampling amplifies any small
preference imbalance exponentially, pushing the system from a metastable near-equal split
into a stable decided state. This is analogous to spinodal decomposition in thermodynamics,
where a binary mixture spontaneously separates into two phases when quenched past the
spinodal line~\cite{binder1987theory}.

More formally, consider a network of $n$ nodes each holding a binary preference $\{0, 1\}$.
If fraction $p > 1/2$ prefer value 1, then after one round of majority-polling with sample
size $k$, the expected fraction preferring 1 becomes:
\begin{equation}
p' = \sum_{j=\lceil k/2 \rceil}^{k} \binom{k}{j} p^j (1-p)^{k-j}
\label{eq:single_round}
\end{equation}
For $p > 1/2$, we have $p' > p$, and the dynamics are self-reinforcing. The fixed points of
this map are $p=0$, $p=1$ (stable), and $p=1/2$ (unstable), exactly the metastable
structure described above.

The Ising model~\cite{ising1925beitrag} provides a deeper analogy. Consider $n$ spins on a
graph, each taking values $\pm 1$. The Glauber dynamics~\cite{glauber1963time} update each
spin stochastically based on the majority of its neighbors. Below the critical temperature
$T_c$, the system spontaneously magnetizes: one spin orientation dominates. The Wave
sampling protocol implements a mean-field version of Glauber dynamics where the effective
temperature is controlled by the sample size $k$ and threshold $\alpha$.

\subsection{The Wave Family}

The Wave family represents a progressive refinement of the basic random sampling idea:

\subsubsection{Slush}
Slush~\cite{rocket2019wave} is the simplest protocol. Each node initializes with no
preference ($\bot$), or adopts the color of the first transaction it sees. In each round,
it queries $k$ random peers. If more than $\alpha k$ respond with the same color $c$, the
node switches to $c$. Slush has no memory: it can be driven back and forth by an adversary.
Despite this weakness, Slush demonstrates that random sampling can achieve emergent
consensus in $O(\log n)$ rounds.

\subsubsection{Flare}
Flare adds a \emph{conviction counter}~\cite{rocket2019wave}: an integer $cnt$
that tracks how many consecutive rounds the node has seen a supermajority for its current
preference. A node finalizes when $cnt \geq \beta$. If the node switches preference, it
resets $cnt = 0$. This prevents oscillation: an adversary must now create $\beta$
consecutive supermajority samples against the node's preference, an event that becomes
exponentially unlikely as $\beta$ increases.

\subsubsection{Wave}
Wave~\cite{rocket2019wave} adds a \emph{confidence counter}: a counter $d[c]$ for
each color $c$ tracking the total number of rounds with supermajority for $c$. The node's
preference is the color with the highest confidence counter. This makes Wave harder to
manipulate: an adversary must overcome the entire history of supermajority rounds, not just
the current streak.

\subsubsection{Lux DAG}
Lux~\cite{rocket2019wave} builds a DAG of transactions on top of Wave. Each
transaction carries a set of \emph{parents}---earlier transactions it references. A
transaction is \emph{strongly preferred} if all transactions in its ancestry are preferred.
Lux runs Wave independently on each \emph{conflict set}---the set of transactions
that spend the same input UTXO. This allows unrelated transactions to be processed
concurrently while maintaining consistency within each conflict.

\subsection{Classical BFT Protocols}

\subsubsection{PBFT}
Practical Byzantine Fault Tolerance~\cite{castro1999practical} achieves safety under
$f < n/3$ Byzantine faults and liveness under partial synchrony. PBFT requires
$O(n^2)$ message complexity per decision, limiting it to small validator sets (tens of
nodes). The three-phase commit (pre-prepare, prepare, commit) ensures safety even when the
leader is Byzantine.

\subsubsection{HotStuff}
HotStuff~\cite{yin2019hotstuff} achieves linear message complexity $O(n)$ per phase through
a threshold signature scheme, making it practical for hundreds of validators. HotStuff
requires a leader to drive consensus and achieves safety under $f < n/3$. Its chained
variant (LibraBFT~\cite{baudet2019state}) is used in Diem/Aptos.

\subsubsection{Tendermint}
Tendermint~\cite{buchman2016tendermint} achieves immediate finality with $O(n^2)$
communication through a locking mechanism: once a validator pre-commits to a block, it
cannot vote for a conflicting block in the same height. This prevents forks at the cost of
requiring $2f+1$ validators to be online and responsive.

\subsection{DAG-Based Consensus}

DAG-BFT protocols such as Narwhal-Tusk~\cite{danezis2022narwhal}, Bullshark~\cite{malkhi2022bullshark},
and Shoal~\cite{spiegelman2022shoal} separate data dissemination from ordering, achieving
high throughput by structuring the mempool as a DAG. Narwhal achieves 130,000 TPS on
commodity hardware by decoupling reliability from consensus ordering. However, these systems
still rely on an underlying BFT consensus layer (typically HotStuff or Tusk) with $O(n)$
leader-based overhead per ordering decision. Lux Consensus is leaderless by design, avoiding
view-change stalls entirely.

\subsection{Nakamoto Consensus}

Bitcoin's longest-chain rule~\cite{nakamoto2008bitcoin} achieves probabilistic safety that
strengthens over time as more blocks are appended. Safety is not instantaneous: a block
at depth $d$ is reversed with probability $\left(\frac{q}{p}\right)^d$ where $q$ is the
adversary's hash rate fraction and $p = 1-q$. The expected time to finality for practical
safety levels is 60 minutes (6 confirmations in Bitcoin). Proof-of-stake variants reduce
energy consumption but retain similar finality latencies~\cite{buterin2020ethereum2}.

\subsection{Prism and Physical-Limit Protocols}

Prism~\cite{bagaria2019prism} deconstructs the blockchain into parallel proposal, voter, and
transaction blocks, approaching the physical throughput limit of the network. While Prism
achieves impressive throughput, it inherits the probabilistic finality model of Nakamoto
consensus with finality on the order of tens of seconds. Lux's sampling-based approach
achieves comparable throughput with sub-second finality.

%% -----------------------------------------------------------------------
%%  3. SYSTEM MODEL
%% -----------------------------------------------------------------------