consensus/paper/sections/background.tex

\section{Background and Related Work}

\subsection{System Model and BFT Assumptions}

We assume a distributed system of $N$ validator nodes, out of which at most $f$ may be Byzantine faulty (arbitrarily malicious) where $f < N$ is some fraction bounded by the protocol's requirements. Lux operates under Byzantine fault tolerance (BFT) assumptions in a partially synchronous network model. This means that there is an unknown global stabilization time after which network message delays are bounded (so eventual reliability), and before which the network may behave asynchronously.

Under partial synchrony and $f$-fault tolerance assumptions, consensus protocols can circumvent the FLP impossibility (which precludes deterministic consensus in pure asynchrony with one faulty node) and ensure both safety (consistency) and liveness (termination) properties. Lux does not assume a globally known set of validators or identities beyond cryptographic public keys—nodes may join or leave, though for analysis we often take $N$ as roughly fixed during a decision interval.

\textbf{Safety}: Informally, we require that no two correct (honest) nodes decide conflicting outcomes. In blockchain terms, this means the ledger does not fork irreversibly—honest nodes eventually agree on exactly the same set of transactions or blocks as finalized. Lux provides safety with a probability $1-\epsilon$ for arbitrarily small $\epsilon>0$, meaning it is $\epsilon$-safely BFT.

Formally, we can define safety as follows. A decision refers to a node finalizing a value (e.g., accepting a transaction as valid or a block as final). Let $dec_i$ be the decision value at node $i$ for a given instance. Lux aims to ensure:

\textbf{Consistency (Safety):} $\Pr[\exists i,j: dec_i \neq dec_j] \le \epsilon$ for any two correct nodes $i,j$ and any sufficiently long execution prefix.

\textbf{Liveness}: The protocol should ensure that if the network conditions eventually stabilize and the adversary is bounded by $f$, then all correct nodes will eventually make a decision. Lux guarantees probabilistic termination with exponential convergence.

\textbf{Liveness:} There exists a constant $c>0$ such that for any time $T$, $\Pr[\text{all correct nodes decide within } T] \ge 1 - e^{-c T}$ (assuming $f < f_{max}$ and after GST).

\subsection{Consensus Mechanisms: From Classical to Metastable}

\subsubsection{Classical BFT Consensus}

Traditional protocols like PBFT~\cite{pbft} and its derivatives (Tendermint, HotStuff~\cite{hotstuff}, etc.) achieve deterministic agreement with strong safety (no risk of fork under $f < 1/3$). They typically operate in rounds with a designated leader proposing a block or value, and a series of all-to-all voting phases. These protocols have the advantage of absolute finality once a value is committed, but suffer from high communication overhead ($O(N^2)$ total messages) and reliance on rotating leadership.

\subsubsection{Nakamoto (Longest-Chain) Consensus}

Bitcoin's approach~\cite{bitcoin} uses proof-of-work to elect a leader in expectation and builds a chain of blocks. Agreement is ensured by nodes following the longest (heaviest) chain. This eliminates explicit voting rounds and works in a dynamic, permissionless setting. However, it only offers probabilistic finality and has significant latency (minutes for confirmation) with energy inefficiency.

\subsubsection{Metastable Randomized Consensus}

Pioneered by Avalanche's family of protocols~\cite{avalanche}, these algorithms strike a middle ground: like classical BFT they use direct voting (no PoW) and can quiesce when idle, and like Nakamoto they provide probabilistic finality and can scale to many nodes. The key innovation is random subsampling for voting: instead of all nodes broadcasting votes to all others, each node picks a small random set of peers to query in each round.

If the network is large, even a sample of size $k=20$ can yield reliable information about the majority opinion with high confidence (by the law of large numbers). Avalanche's core protocols (Slush, Snowflake, Snowball) demonstrate that by repeated sampling, the network will rapidly amplify any initial slight majority preference into a strong consensus.

Lux falls in this category of metastable consensus. It adopts the subsampling voting mechanism and metastable decision process similar to Avalanche's Snow protocols. However, Lux extends and organizes this mechanism into a more modular architecture with explicit physics metaphors to guide design and explanation.