papers/lux-data-availability/sections/02-background.tex

\section{Background}

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

\subsection{Reed-Solomon Erasure Coding}

A Reed-Solomon (RS) code over a finite field $\mathbb{F}_p$ encodes a message of $k$ symbols
into a codeword of $n$ symbols such that any $k$ of the $n$ symbols suffice to reconstruct the
original message~\cite{reed1960polynomial}. The encoding interprets the $k$ message symbols
as coefficients of a polynomial $f(x)$ of degree $< k$ and evaluates $f$ at $n$ distinct
points $\omega_0, \omega_1, \ldots, \omega_{n-1} \in \mathbb{F}_p$.

\begin{definition}[Reed-Solomon Code]
Let $\mathbb{F}_p$ be a finite field with $|\mathbb{F}_p| \geq n$, and let
$\Omega = \{\omega_0, \ldots, \omega_{n-1}\} \subset \mathbb{F}_p$ be a set of $n$ distinct
evaluation points. The Reed-Solomon code $\text{RS}[n, k, \Omega]$ is the set
\[
    \text{RS}[n,k,\Omega] = \{(f(\omega_0), \ldots, f(\omega_{n-1})) \mid f \in \mathbb{F}_p[x],\; \deg(f) < k\}.
\]
The code has minimum distance $d = n - k + 1$, correcting up to $\lfloor(d-1)/2\rfloor$ errors
and tolerating up to $n - k$ erasures.
\end{definition}

For DAS, we set $n = 2k$ (rate $1/2$), so that any $k$ of $2k$ symbols reconstruct the
original data. This means an adversary must withhold at least $k + 1$ of $2k$ symbols---more
than half---to prevent reconstruction.

\subsection{Two-Dimensional Extension}

A one-dimensional RS code applied to a blob of $k^2$ symbols produces a codeword of $2k^2$
symbols. While functional, this forces light clients to sample from a single long vector,
offering no structural locality. The \emph{two-dimensional} extension arranges the $k^2$ data
symbols in a $k \times k$ matrix $M$ and encodes each row and each column independently with
an RS code of rate $1/2$, producing a $2k \times 2k$ extended matrix $\hat{M}$.

\begin{definition}[2D RS Extension]
Given a $k \times k$ data matrix $M$ over $\mathbb{F}_p$:
\begin{enumerate}
    \item Encode each row of $M$ using $\text{RS}[2k, k]$, producing a $k \times 2k$ matrix $M'$.
    \item Encode each column of $M'$ using $\text{RS}[2k, k]$, producing the $2k \times 2k$
          extended matrix $\hat{M}$.
\end{enumerate}
\end{definition}

The key property is that \emph{any} $k$ rows (out of $2k$) together with any $k$ columns
suffice to reconstruct $M$. Equivalently, the adversary must corrupt at least one full row
or one full column to prevent reconstruction, which is detectable by checking row/column
polynomial constraints.

\subsection{KZG Polynomial Commitments}
\label{sec:background:kzg}

The Kate-Zaverucha-Goldberg (KZG) commitment scheme~\cite{kate2010commitment} enables
a prover to commit to a polynomial $f(x)$ of degree $< d$ with a single group element
and later open the commitment at any point $z$ with a single group-element proof.

\begin{definition}[KZG Commitment]
Let $(\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T, e, g_1, g_2, p)$ be a bilinear group of
prime order $p$ with pairing $e : \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$.
A trusted setup produces $\text{SRS} = (g_1, \tau g_1, \tau^2 g_1, \ldots, \tau^{d-1} g_1,
g_2, \tau g_2)$ for a secret $\tau$. The commitment to $f(x) = \sum_{i=0}^{d-1} a_i x^i$ is
\[
    C = f(\tau) \cdot g_1 = \sum_{i=0}^{d-1} a_i \cdot \tau^i g_1.
\]
An opening proof for $f(z) = y$ is the group element
$\pi = q(\tau) \cdot g_1$ where $q(x) = \frac{f(x) - y}{x - z}$.
Verification checks $e(C - y \cdot g_1, g_2) = e(\pi, \tau g_2 - z \cdot g_2)$.
\end{definition}

KZG commitments have three properties essential for DAS:
\begin{itemize}[leftmargin=*]
    \item \textbf{Binding}: Under the $d$-Strong Diffie-Hellman assumption, no efficient adversary
          can produce two different polynomials with the same commitment.
    \item \textbf{Evaluation binding}: A commitment uniquely determines evaluations at all points.
    \item \textbf{Homomorphism}: Commitments are additively homomorphic, enabling efficient
          aggregation.
\end{itemize}

\subsection{Existing DAS Constructions}

\subsubsection{EIP-4844 and Proto-Danksharding}

Ethereum's EIP-4844~\cite{eip4844} introduces \emph{blob transactions} that carry up to
128\,KiB of data committed via KZG. Each blob is a degree-4095 polynomial over the BLS12-381
scalar field, with the commitment serving as the blob's identifier. EIP-4844 does not implement
full DAS; blob data is distributed via the gossip network and pruned after approximately
18 days. Full Danksharding~\cite{dankrad2022danksharding} extends this to 2D DAS with
$16 \times 16$ to $256 \times 256$ blob matrices, but remains undeployed as of late 2025.

\subsubsection{Celestia}

Celestia~\cite{albassam2019lazyledger} implements 2D RS erasure coding with Namespaced Merkle
Trees (NMTs) for commitments. Each row and column of the extended data matrix is committed
via an NMT, and light nodes sample cells by requesting Merkle proofs. Celestia's design
differs from KZG-based approaches in that Merkle proofs are $O(\log n)$ in size versus
$O(1)$ for KZG openings, but require no trusted setup.

\subsubsection{Limitations of Prior Approaches}

Both EIP-4844 and Celestia assume a single monolithic DA namespace. In a multi-chain
environment like Lux, this forces all appchain validators to participate in a single DA
protocol, negating the isolation benefits of appchains. Lux-DAS addresses this by partitioning
the commitment namespace while preserving cross-appchain verifiability.


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