papers/lux-consensus/sections/07-implementation.tex

\section{Implementation}

\label{sec:implementation}

\subsection{Architecture Overview}

The Lux consensus engine is implemented in Go as part of the Lux node software. The
implementation consists of four primary components:

\begin{enumerate}
\item \textbf{Sampler}: Selects $k$ validators from the active validator set using
weighted uniform sampling proportional to stake weight.
\item \textbf{Querier}: Manages concurrent query sessions with connection pooling and
timeout handling.
\item \textbf{Preference Engine}: Maintains per-conflict-set Wave state (confidence
counters, preference, finalization status).
\item \textbf{DAG Manager}: Tracks transaction ancestry relationships and manages
acceptance propagation.
\end{enumerate}

\subsection{Networking}

Query messages are sent over persistent ZAP-native connections (LP-200) with TLS 1.3.
The protocol uses a push-pull gossip model: new transactions are pushed to neighbors,
while preference queries are explicit request-response interactions.

Connection management uses a gossip overlay with $O(\log n)$ degree: each validator
maintains $\lceil \log_2 n \rceil$ outbound connections. The sampler draws from the full
validator set by routing through this overlay when direct connections are unavailable.

\subsection{Transaction Pipeline}

\begin{lstlisting}[language=Go, caption=Core Lux preference query handler]
type LuxEngine struct {
    validators ValidatorSet
    sampler    Sampler
    dag        TransactionDAG
    wave   map[ConflictID]*WaveState
}

type WaveState struct {
    preference  TransactionID
    lastChoice  TransactionID
    confidence  map[TransactionID]int
    consecutive int
    decided     bool
}

func (e *LuxEngine) QueryRound(tx TransactionID) error {
    conflict := e.dag.ConflictSet(tx)
    state := e.wave[conflict.ID]
    if state == nil || state.decided {
        return nil
    }
    sample := e.sampler.Sample(k, e.validators)
    votes := make(map[TransactionID]int)
    var wg sync.WaitGroup
    var mu sync.Mutex
    for _, v := range sample {
        wg.Add(1)
        go func(validator Validator) {
            defer wg.Done()
            resp, err := e.querier.Query(validator, conflict)
            if err == nil {
                mu.Lock()
                votes[resp]++
                mu.Unlock()
            }
        }(v)
    }
    wg.Wait()
    winner, count := maxVote(votes)
    if count >= int(alpha * float64(k)) {
        state.confidence[winner]++
        if state.confidence[winner] > state.confidence[state.preference] {
            state.preference = winner
        }
        if winner == state.lastChoice {
            state.consecutive++
        } else {
            state.lastChoice = winner
            state.consecutive = 1
        }
        if state.consecutive >= beta {
            e.finalize(conflict, state.preference)
        }
    }
    return nil
}
\end{lstlisting}

\subsection{Stake-Weighted Sampling}

Lux uses stake-weighted sampling. The probability that validator $v$ is selected is:
\begin{equation}
\Pr[v \in S] = \frac{w_v}{\sum_{u \in V} w_u}
\label{eq:stake_sampling}
\end{equation}

The implementation uses a cumulative distribution function (CDF) array sorted by stake weight,
enabling $O(\log n)$ binary search per sample draw. For $k$ samples, total sampling cost
is $O(k \log n)$.

\subsection{Validator Set Management}

The active validator set is managed by the platform chain (P-Chain). Validators stake LUX
tokens and register with the P-Chain. Validator set changes are handled gracefully: if a
validator goes offline, queries to that validator timeout and the sample is considered of
reduced size $k' < k$, with the supermajority threshold scaled: $\alpha' = \lceil \alpha k \rceil / k'$.

\subsection{Optimizations}

Several engineering optimizations improve practical performance:
\begin{itemize}[nosep]
\item \textbf{Batch queries}: Multiple conflict sets are queried in a single network round-trip.
\item \textbf{Early termination}: If $\alpha k$ responses arrive before all $k$, the round
can terminate early with the current supermajority.
\item \textbf{Pipelined rounds}: Round $r+1$ begins before all responses from round $r$
arrive, with late responses applied retroactively.
\item \textbf{Virtuous frontier}: Non-conflicting transactions bypass the Wave mechanism
entirely and are accepted as soon as their ancestors are accepted.
\end{itemize}

%% -----------------------------------------------------------------------
%%  8. EVALUATION
%% -----------------------------------------------------------------------