papers/lux-ray-protocol/sections/03-the-ray-protocol.tex

\section{The Ray Protocol}

\label{sec:protocol}

\subsection{Adaptive Threshold Function}

The core innovation of Ray is replacing the static threshold $\beta$ with an adaptive
threshold $\beta^*(r)$ that depends on the observed confidence velocity:

\begin{equation}
\beta^*(r) = \max\left(\beta_{\min}, \left\lceil \frac{\lambda}{\nu_c(r)} \right\rceil\right)
\label{eq:adaptive-threshold}
\end{equation}

where $\lambda$ is a security parameter ensuring $2^{-128}$ safety and $\beta_{\min} \geq 3$
is the minimum threshold providing base-level security.

The intuition is: when $\nu_c$ is high (close to 1, meaning supermajority in almost every
round), fewer total rounds suffice. When $\nu_c$ is low (adversary is slowing convergence),
more rounds are needed.

\begin{algorithm}[H]
\caption{Ray Protocol --- Adaptive Finality}
\label{alg:ray-core}
\begin{algorithmic}[1]
\Require Parameters: $k$, $\alpha$, $\beta_{\min}$, $\lambda$ (security parameter)
\State $d_c \gets 0$ for all colors $c$; $r \gets 0$
\While{$\lnot \text{finalized}$}
    \State $r \gets r + 1$
    \State $S \gets \text{RandomSample}(V \setminus \{v\}, k)$
    \State Query each $u \in S$ for $\text{col}(u, t)$
    \For{each color $c$}
        \State $n_c \gets |\{u \in S : \text{col}(u, t) = c\}|$
        \If{$n_c \geq \alpha k$}
            \State $d_c \gets d_c + 1$
        \EndIf
    \EndFor
    \State $\text{col}(v, t) \gets \arg\max_c d_c$
    \State $c^* \gets \text{col}(v, t)$
    \State $\nu_{c^*} \gets d_{c^*} / r$ \Comment{confidence velocity}
    \State $\beta^* \gets \max(\beta_{\min}, \lceil \lambda / \nu_{c^*} \rceil)$ \Comment{adaptive threshold}
    \If{$d_{c^*} \geq \beta^*$}
        \State \textbf{finalize} $t$ with color $c^*$
    \EndIf
\EndWhile
\end{algorithmic}
\end{algorithm}

\subsection{Security Parameter Derivation}

\begin{theorem}[Adaptive Safety]
\label{thm:adaptive-safety}
If the security parameter $\lambda$ satisfies:
\[
\lambda \geq \frac{128 \cdot \ln 2}{\ln(q_1 / q_0)}
\]
where $q_1, q_0$ are the supermajority probabilities for the winning and losing colors
respectively, then the adaptive threshold $\beta^*$ ensures safety probability
$\leq 2^{-128}$.
\end{theorem}

\begin{proof}
From Theorem~4.2 (confidence monotonicity in the Wave analysis), the probability of
a safety violation with threshold $\beta$ is at most $(q_0/q_1)^\beta$. We require:
\[
\left(\frac{q_0}{q_1}\right)^\beta \leq 2^{-128}
\]
Taking logarithms: $\beta \cdot \ln(q_0/q_1) \leq -128 \ln 2$, giving:
\[
\beta \geq \frac{128 \ln 2}{\ln(q_1/q_0)}
\]
The adaptive threshold $\beta^* = \lceil \lambda / \nu_{c^*} \rceil$ must satisfy this.
The confidence velocity $\nu_{c^*}$ is an estimator of $q_1$ (the probability of
observing supermajority for the winning color). When $\nu_{c^*} \approx q_1$:
\[
\beta^* = \frac{\lambda}{\nu_{c^*}} \approx \frac{\lambda}{q_1} \geq \frac{128 \ln 2}{q_1 \cdot \ln(q_1/q_0)}
\]
Setting $\lambda = 128 \ln 2 / \ln(q_1/q_0)$ satisfies the requirement. Since
$\nu_{c^*} \leq q_1$ (the velocity cannot exceed the supermajority probability), the
adaptive threshold $\beta^* = \lambda/\nu_{c^*} \geq \lambda/q_1$, ensuring safety.
\end{proof}

\subsection{Bayesian Adversary Estimator}

\begin{algorithm}[H]
\caption{Online Bayesian Adversary Estimator}
\label{alg:bayes-estimator}
\begin{algorithmic}[1]
\Function{UpdateEstimate}{$n_c$, $k$, $\hat{\gamma}_{r-1}$}
    \State \Comment{$n_c$ = count of majority-color responses in sample}
    \State $p_{\text{obs}} \gets n_c / k$ \Comment{observed agreement fraction}
    \State \Comment{Under honest majority: $p_{\text{obs}} \approx 1 - \gamma$ after convergence}
    \State $\hat{\gamma}_r \gets \eta \cdot (1 - p_{\text{obs}}) + (1 - \eta) \cdot \hat{\gamma}_{r-1}$
    \Comment{exponential moving average}
    \State \Return $\hat{\gamma}_r$
\EndFunction
\end{algorithmic}
\end{algorithm}

%% -----------------------------------------------------------------------
%%  4. CONVERGENCE OF THE ESTIMATOR
%% -----------------------------------------------------------------------