papers/lux-verkle-trees/sections/06-proof-generation.tex

\section{Proof Generation}


\subsection{Single-Point Opening}

For proving value at position $i$ in Verkle tree:

\begin{algorithmic}[1]
\STATE \textbf{function} $\mathsf{GenerateProof}(tree, key)$
\STATE $path \gets \mathsf{GetPath}(tree, key)$
\STATE $commitments \gets []$
\STATE $openings \gets []$
\FOR{$node$ in $path$}
    \STATE $chunk \gets key[node.depth]$
    \STATE $\pi \gets \mathsf{KZG.Open}(node, chunk)$
    \STATE $commitments.\mathsf{append}(node.C)$
    \STATE $openings.\mathsf{append}(\pi)$
\ENDFOR
\RETURN $(commitments, openings)$
\end{algorithmic}

\subsection{Multi-Point Opening}

For $k$ openings at points $(z_1, \ldots, z_k)$ with values $(y_1, \ldots, y_k)$:

\begin{equation}
    g(X) = \sum_{i=1}^{k} y_i \cdot \frac{\omega^i(X)}{X - z_i}
\end{equation}

where $\omega^i(X) = \prod_{j \neq i}(X - z_j)$.

The aggregated proof satisfies:
\begin{equation}
    e(C - [g(\tau)]_1, [1]_2) = e(\pi_{agg}, [\tau]_2)
\end{equation}

\subsection{Proof Aggregation}

Multiple proofs along a path aggregate into a single proof:

\begin{equation}
    \pi_{final} = \sum_{i=0}^{d-1} \alpha^i \cdot \pi_i
\end{equation}

where $\alpha$ is derived via Fiat-Shamir from the transcript.

\subsection{Final Proof Structure}

\begin{lstlisting}[caption=Verkle Proof Format]
struct VerkleProof {
    uint8_t depth;              // Tree depth
    Commitment[] commitments;   // 48 bytes each
    Point opening_proof;        // 48 bytes
    Scalar[] values;           // 32 bytes each
    uint256 key;               // Target key
}
\end{lstlisting}

Total proof size: $48 + 48 + 32d$ bytes $\approx$ 150 bytes for $d = 2$.