papers/lux-verkle-trees/sections/05-polynomial-commitments-kzg.tex

\section{Polynomial Commitments (KZG)}


\subsection{Trusted Setup}

The KZG scheme requires a structured reference string (SRS) generated through a trusted setup ceremony:

\begin{equation}
    \mathsf{SRS} = \{[\tau^i]_1\}_{i=0}^{n-1} \cup \{[\tau^i]_2\}_{i=0}^{1}
\end{equation}

where $\tau$ is destroyed after setup. Lux utilizes the Powers of Tau ceremony with 100,000+ participants, ensuring security under the assumption that at least one participant was honest.

\subsection{Commitment Generation}

Given polynomial $f(X) = \sum_{i=0}^{d} a_i X^i$:

\begin{equation}
    C = [f(\tau)]_1 = \sum_{i=0}^{d} a_i \cdot [\tau^i]_1
\end{equation}

This requires $d$ scalar multiplications in $\mathbb{G}_1$:
\begin{itemize}
    \item Scalar multiplication: 0.25 ms per operation
    \item Total commitment time: $0.25d$ ms
    \item Parallelizable across coefficients
\end{itemize}

\subsection{Opening Proofs}

To prove $f(z) = y$, compute quotient polynomial:
\begin{equation}
    q(X) = \frac{f(X) - y}{X - z}
\end{equation}

The proof is $\pi = [q(\tau)]_1$, computed as:
\begin{equation}
    \pi = \sum_{i=0}^{d-1} q_i \cdot [\tau^i]_1
\end{equation}

\subsection{Pairing Verification}

Verification uses bilinear pairing $e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$:

\begin{equation}
    e(C - [y]_1, [1]_2) \stackrel{?}{=} e(\pi, [\tau]_2 - [z]_2)
\end{equation}

Expanding the pairing equation:
\begin{equation}
    e([f(\tau) - y]_1, [1]_2) = e([q(\tau)]_1, [\tau - z]_2)
\end{equation}

This holds if and only if $f(z) = y$.