papers/lux-data-availability/lux-data-availability.tex

\documentclass[11pt,a4paper]{article}
\usepackage{../shared/luxcover}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{mathtools}
\usepackage{graphicx}
\usepackage{algorithm}
\usepackage{algpseudocode}
\usepackage{tikz}
\usepackage{pgfplots}
\usepackage{booktabs}
\usepackage{hyperref}
\usepackage{cleveref}
\usepackage{listings}
\input{../shared/lstlang}
\usepackage{xcolor}
\usepackage{multicol}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{array}
\usepackage{tabularx}
\usepackage{float}
\usepackage{enumitem}


\usetikzlibrary{automata, positioning, arrows.meta, shapes.geometric, matrix, fit, backgrounds}
\pgfplotsset{compat=1.17}

\definecolor{codegreen}{rgb}{0,0.6,0}
\definecolor{codegray}{rgb}{0.5,0.5,0.5}
\definecolor{codepurple}{rgb}{0.58,0,0.82}
\definecolor{backcolour}{rgb}{0.95,0.95,0.92}
\definecolor{luxred}{rgb}{0.992,0.267,0.267}

\lstdefinestyle{mystyle}{
    backgroundcolor=\color{backcolour},
    commentstyle=\color{codegreen},
    keywordstyle=\color{magenta},
    numberstyle=\tiny\color{codegray},
    stringstyle=\color{codepurple},
    basicstyle=\ttfamily\footnotesize,
    breakatwhitespace=false,
    breaklines=true,
    captionpos=b,
    keepspaces=true,
    numbers=left,
    numbersep=5pt,
    showspaces=false,
    showstringspaces=false,
    showtabs=false,
    tabsize=2
}
\lstset{style=mystyle}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]

\theoremstyle{definition}
\newtheorem{definition}{Definition}[section]
\newtheorem{example}{Example}[section]

\theoremstyle{remark}
\newtheorem{remark}{Remark}[section]

\hypersetup{colorlinks=true,linkcolor=black,citecolor=blue,urlcolor=blue}

\title{\textbf{Data Availability Sampling in Lux Network}\\
\large A Reed-Solomon Erasure-Coded DA Layer with KZG Commitments\\
and 2D Sampling for Scalable Light Node Verification}

\author{
Zach Kelling\thanks{Corresponding author: [email protected]}\\
\textit{Lux Industries, Inc.}\\
\texttt{[email protected]}
}
\date{2020}

\begin{document}

\luxcoverpage

\begin{abstract}
We present \textbf{Lux-DAS}, a data availability sampling protocol that enables light nodes
on the Lux Network to verify that block data has been published without downloading entire
blocks. Lux-DAS employs two-dimensional Reed-Solomon erasure coding over blob data arranged
in a $k \times k$ matrix, extended to $2k \times 2k$ with redundancy factor four, coupled
with Kate-Zaverucha-Goldberg (KZG) polynomial commitments on each row and column. Light
clients sample $s$ random cells from the extended matrix and request openings from full nodes;
if all $s$ openings verify, the client accepts the block with confidence
$1 - (1/4)^s \geq 1 - 2^{-\lambda}$ for security parameter $\lambda = 2s$. We prove that
an adversary who withholds more than $50\%$ of any row or column is detected with
overwhelming probability when the number of sampling light nodes exceeds
$O(k^2 / s)$. Our construction introduces three innovations beyond existing DAS designs:
(i) a \emph{appchain-scoped DA layer} that partitions the commitment namespace across Lux
appchains, reducing validator bandwidth by a factor proportional to the number of active appchains;
(ii) an \emph{adaptive sampling strategy} that increases sample count $s$ in proportion to
observed network churn, maintaining target security under dynamic validator sets; and
(iii) \emph{KZG commitment aggregation via inner-product arguments} that amortizes proof
verification cost when a light client queries cells from multiple blobs in the same slot.
We compare Lux-DAS against Ethereum's EIP-4844 (Proto-Danksharding) and Celestia's DAS
protocol, demonstrating a $3.1\times$ reduction in amortized verification cost per blob
and a $5.8\times$ improvement in sampling throughput for networks with more than 64 appchains.
A prototype implementation on the Lux Fuji testnet processes 128 blobs per slot with a
blob size of 128\,KiB, achieving median light-client verification latency of 42\,ms.
\end{abstract}

\tableofcontents
\newpage

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

\input{sections/01-introduction}
\input{sections/02-background}
\input{sections/03-protocol-design}
\input{sections/04-security-analysis}
\input{sections/05-implementation}
\input{sections/06-evaluation}
\input{sections/07-related-work}
\input{sections/09-parameter-selection-guide}
\input{sections/10-kzg-ceremony-compatibility}
\input{sections/11-formal-specification-of-the-da-oracle-pr}
\input{sections/99-conclusion}

\end{document}