papers/lux-verkle-trees/sections/03-verkle-tree-background.tex

\section{Verkle Tree Background}


\subsection{Vector Commitments}

A vector commitment scheme allows committing to a vector $\vec{v} = (v_0, v_1, \ldots, v_{n-1})$ with a short commitment $C$, enabling selective opening of individual positions with constant-size proofs.

\begin{definition}[Vector Commitment]
A vector commitment scheme consists of algorithms:
\begin{itemize}
    \item $\mathsf{Setup}(1^\lambda, n) \rightarrow \mathsf{pp}$: Generate public parameters
    \item $\mathsf{Commit}(\mathsf{pp}, \vec{v}) \rightarrow C$: Commit to vector $\vec{v}$
    \item $\mathsf{Open}(\mathsf{pp}, \vec{v}, i) \rightarrow \pi$: Generate opening proof for position $i$
    \item $\mathsf{Verify}(\mathsf{pp}, C, i, v_i, \pi) \rightarrow \{0,1\}$: Verify opening proof
\end{itemize}
\end{definition}

\subsection{Polynomial Commitments}

Polynomial commitments enable committing to polynomials with efficient evaluation proofs. The KZG (Kate-Zaverucha-Goldberg) scheme provides optimal proof sizes using bilinear pairings.

For polynomial $f(X) = \sum_{i=0}^{n-1} a_i X^i$, the KZG commitment is:
\begin{equation}
    C = [f(\tau)]_1 = \sum_{i=0}^{n-1} a_i[\tau^i]_1
\end{equation}

where $\tau$ is a secret trapdoor from trusted setup and $[\cdot]_1$ denotes group elements in $\mathbb{G}_1$.

\subsection{Reed-Solomon Encoding}

Verkle trees encode data using Reed-Solomon codes for error correction and efficient batch opening. Given data $(d_0, \ldots, d_{k-1})$, we construct polynomial:
\begin{equation}
    f(X) = \sum_{i=0}^{k-1} d_i \cdot L_i(X)
\end{equation}

where $L_i(X)$ are Lagrange basis polynomials.

\subsection{Inner Product Arguments}

For bandwidth optimization, inner product arguments provide logarithmic-size proofs for polynomial evaluations. Given commitments $C$ and evaluation point $z$, the prover demonstrates:
\begin{equation}
    \langle \vec{a}, \vec{b} \rangle = v
\end{equation}

through recursive halving, achieving proof size $O(\log n)$ group elements.