papers/lux-data-availability/sections/04-security-analysis.tex

\section{Security Analysis}

\label{sec:security}
%% ============================================================================

\subsection{Threat Model Formalization}

We formalize the security of Lux-DAS in the Universal Composability (UC) framework,
defining an ideal functionality $\mathcal{F}_{\text{DA}}$ that guarantees: if an honest
block producer publishes data $B$, then every honest party can retrieve $B$; and if a
corrupt block producer's header is accepted by any honest light client, then $B$ is
reconstructable from the data held by honest full nodes.

\begin{definition}[DA Security Game]
\label{def:da-game}
The data availability game $\text{Game}_{\text{DA}}(\mathcal{A}, \lambda)$ proceeds as follows:
\begin{enumerate}
    \item The adversary $\mathcal{A}$ selects a $k \times k$ data matrix $M$ and an extended
          matrix $\hat{M}^*$ that may differ from the honest encoding $\hat{M}$.
    \item $\mathcal{A}$ computes commitments $\mathbf{C}^*$ and publishes the block header.
    \item The challenger simulates $L$ honest light clients, each sampling $s$ cells.
    \item $\mathcal{A}$ responds to each sample request with a cell value and opening proofs.
    \item $\mathcal{A}$ wins if: (a) at least one honest light client accepts, and
          (b) the honest reconstruction protocol applied to all received cells fails to
          reconstruct $M$.
\end{enumerate}
\end{definition}

\begin{theorem}[Main Security Theorem]
\label{thm:main-security}
Under the $d$-SDH assumption on the bilinear group, for any PPT adversary $\mathcal{A}$,
\[
    \Pr[\mathcal{A} \text{ wins } \text{Game}_{\text{DA}}] \leq L \cdot \left(\frac{3}{4}\right)^s + \text{negl}(\lambda).
\]
\end{theorem}

\begin{proof}
We proceed via a sequence of hybrid games.

\textbf{Game 0}: The real game as defined above.

\textbf{Game 1}: Replace KZG commitments with ideal commitments that perfectly bind the
polynomial. By the binding property of KZG under $d$-SDH, Games 0 and 1 are
computationally indistinguishable.

\textbf{Game 2}: Condition on the event $E$ that $\hat{M}^*$ is a valid 2D RS codeword.
If $E$ holds, then $M$ is uniquely determined by the commitments, and reconstruction always
succeeds---the adversary cannot win. If $\neg E$ holds, then there exist at least $k$ cells
in $\hat{M}^*$ that are inconsistent with the row or column commitments. Each light client's
probability of detecting at least one inconsistency in $s$ samples is at least
$1 - (3/4)^s$, by the combinatorial argument of~\cite{albassam2018fraud}. Union-bounding
over $L$ clients yields the claimed bound.
\end{proof}

\subsection{Reconstruction Guarantee}

\begin{theorem}[Reconstruction Threshold]
\label{thm:reconstruction}
If at least $k$ of the $2k$ rows and at least $k$ of the $2k$ columns of $\hat{M}$ are
available (each row/column having all $2k$ cells), then the original data matrix $M$ is
uniquely reconstructable in $O(k^2 \log^2 k)$ field operations.
\end{theorem}

\begin{proof}
Each available column provides $k$ evaluations of a polynomial of degree $< k$, which
suffices for unique interpolation via an FFT-based algorithm in $O(k \log^2 k)$ operations.
Repeating for all $2k$ columns and then decoding each row similarly gives the claimed
complexity.
\end{proof}

\subsection{Network-Level Security}

The per-client security of Theorem~\ref{thm:main-security} assumes each client independently
samples random cells. In practice, an adversary may serve different data to different clients,
partitioning the network. We address this with a \emph{data availability oracle} integrated
into the Lux gossip layer.

\begin{definition}[DA Oracle]
Full nodes that successfully reconstruct a blob broadcast a signed attestation
$\sigma_i = \text{Sign}(sk_i, \text{``DA''} \| \text{DataRoot})$ on the appchain's gossip
channel. A light client considers data available if it collects attestations from at least
$2f+1$ distinct validators.
\end{definition}

\begin{lemma}[Network Partition Resistance]
\label{lemma:partition}
Under the assumption that at most $f < N/3$ validators are adversarial, a light client
that collects $2f+1$ DA attestations is guaranteed that at least $f+1$ honest validators
possess the full data, which suffices for reconstruction.
\end{lemma}

\subsection{Interaction with Beacon Consensus}

Lux blocks achieve finality via the Beacon consensus protocol. A block is finalized
when a supermajority of validators has accepted it. Lux-DAS integrates with Beacon by
adding a \emph{DA vote} to the consensus message: a validator votes to accept a block only
if it has verified data availability (either by downloading the full data or by completing
$s$ successful DAS samples and receiving $2f+1$ attestations).

This coupling ensures that finalized blocks are data-available with the same probability
as the sampling security guarantee, without adding an additional consensus round.

\subsection{Adversarial Blob Producer Strategies}

We analyze two specific adversarial strategies:

\paragraph{Strategy 1: Selective Withholding.}
The adversary publishes all cells except those in a targeted row $i^*$, hoping that light
clients do not sample row $i^*$. The probability of evading detection by a single client is
$(1 - 1/(2k))^s \leq e^{-s/(2k)}$. For $k = 64$ and $s = 75$, this is $e^{-75/128} \approx 0.557$.
With $L = 50$ light clients sampling independently, the probability drops to $0.557^{50} < 2^{-42}$.

\paragraph{Strategy 2: Incorrect Encoding.}
The adversary publishes all $4k^2$ cells but encodes them with a polynomial of degree $\geq k$,
so that the data does not correspond to a valid RS codeword. KZG evaluation binding prevents
this: the commitment fixes the polynomial, and any cell inconsistent with the committed
polynomial will fail the opening verification. This strategy reduces to breaking KZG binding.


%% ============================================================================