papers/lux-flare-protocol/sections/04-certificate-skip-exclusivity.tex

\section{Certificate Skip Exclusivity}

\label{sec:cse}

The central theorem of this paper establishes that conflicting certificates cannot
form simultaneously.

\subsection{Honest Support Invariant}

\begin{definition}[Honest Support]
Color $c$ has \emph{honest support at round $r$} if more than $1/2$ of honest validators
prefer $c$ at round $r$: $|\{v \in H : \text{col}(v, t, r) = c\}| > |H|/2$.
\end{definition}

\begin{lemma}[Honest Support Necessity]
\label{lem:honest-support}
If honest validator $v$ observes $\geq \alpha k$ responses for color $c$ in round $r$,
then color $c$ had honest support at round $r$ (with probability $1 - e^{-\Omega(k)}$).
\end{lemma}

\begin{proof}
The sample of size $k$ contains at least $(1 - \gamma)k$ honest validators in expectation,
where $\gamma < 1/3$ is the Byzantine fraction. For $\alpha k$ responses to match color $c$,
at least $\alpha k - \gamma k = (\alpha - \gamma)k$ honest validators in the sample must
prefer $c$.

With $\alpha = 0.8$ and $\gamma < 1/3$, we need $(\alpha - \gamma)k > (0.8 - 0.33) \cdot 20 = 9.4$
honest validators in the sample preferring $c$. Since the sample contains about
$(1-\gamma)k \approx 13.4$ honest validators, this means $> 70\%$ of sampled honest
validators prefer $c$.

By a Chernoff bound, this implies that $> 50\%$ of the honest population prefers $c$
with probability $1 - e^{-\Omega(k)}$, since a random sample of 13 from the honest
population would not show 70\% for $c$ unless the true fraction exceeds 50\%.
\end{proof}

\begin{theorem}[Certificate Skip Exclusivity]
\label{thm:cse}
In any execution with $|B| < n/3$, the probability that two certificates
$\text{cert}(v_i, t, c_1)$ and $\text{cert}(v_j, t, c_0)$ exist for conflicting
colors $c_1 \neq c_0$ is at most $e^{-\Omega(k\beta_2)}$.
\end{theorem}

\begin{proof}
Assume for contradiction that honest validator $v_i$ certifies color 1 and honest
validator $v_j$ certifies color 0. By the conviction counter mechanism:
\begin{itemize}[nosep]
\item $v_i$ observed $\beta_2$ consecutive supermajority rounds for color 1, say in
rounds $r_1, r_1+1, \ldots, r_1+\beta_2-1$.
\item $v_j$ observed $\beta_2$ consecutive supermajority rounds for color 0, say in
rounds $r_2, r_2+1, \ldots, r_2+\beta_2-1$.
\end{itemize}

By Lemma~\ref{lem:honest-support}, each of $v_i$'s rounds implies honest support for
color 1, and each of $v_j$'s rounds implies honest support for color 0. But honest
support for both colors simultaneously is impossible: if $> |H|/2$ honest validators
prefer color 1 and $> |H|/2$ prefer color 0 in the same round, we need $> |H|$ honest
validators, a contradiction.

Therefore, the round intervals $[r_1, r_1+\beta_2-1]$ and $[r_2, r_2+\beta_2-1]$ must
be disjoint. Without loss of generality, assume $v_i$ certifies first (round intervals
don't overlap, and $r_1 + \beta_2 - 1 < r_2$).

During $v_i$'s conviction streak, the honest majority supports color 1. After $v_i$
certifies, the population fraction for color 1 is $p_1 > 1/2 + \gamma$ for some
$\gamma > 0$. For $v_j$ to then build $\beta_2$ consecutive rounds of supermajority
for color 0, the honest population must first switch majority support to color 0, and
then maintain that support for $\beta_2$ consecutive rounds.

The probability of the honest population switching from majority-1 to majority-0 is
at most $e^{-\Omega(k)}$ per round (by Theorem~\ref{thm:convergence} of the Wave
analysis, the dynamics amplify the majority). Even if a switch occurs, the probability
of maintaining $\beta_2$ consecutive supermajority rounds for color 0 (while the
population dynamics push back toward color 1) is at most $e^{-\Omega(k\beta_2)}$.

Formally: the event requires at least $\beta_2$ consecutive rounds where the adversary
controls enough of the sample to produce an $\alpha k$-supermajority for the minority
color. The probability per round is at most $p_{\text{false}} = e^{-\Omega(k)}$, and
consecutive occurrence for $\beta_2$ rounds gives $p_{\text{false}}^{\beta_2} = e^{-\Omega(k\beta_2)}$.
\end{proof}

\begin{corollary}[Safety Bound]
\label{cor:safety-bound}
For $k = 20$ and $\beta_2 = 14$, the probability of conflicting certificates is
bounded by $e^{-\Omega(280)} < 2^{-128}$.
\end{corollary}

\subsection{Formal Exclusivity Argument}

\begin{proposition}[Round Pigeonhole]
\label{prop:pigeonhole}
If two honest validators both certify within $T$ total rounds, their conviction
streaks must share at least $\max(0, 2\beta_2 - T)$ overlapping rounds. In any
overlapping round, both colors cannot have honest support simultaneously.
\end{proposition}

\begin{proof}
The two streaks occupy $\beta_2$ rounds each. If both fit within $T$ total rounds,
by the pigeonhole principle, they overlap in at least $2\beta_2 - T$ rounds (when
$2\beta_2 > T$). In each overlapping round, Lemma~\ref{lem:honest-support} requires
honest support for both colors, which is impossible. Therefore, overlapping streaks
are contradictory, and the streaks must be separated by at least 1 round of non-overlapping
honest support shift.
\end{proof}

%% -----------------------------------------------------------------------
%%  5. LURING ATTACKS
%% -----------------------------------------------------------------------