papers/lux-verkle-trees/sections/10-cryptographic-primitives.tex

\section{Cryptographic Primitives}


\subsection{BLS12-381 Curve}

Verkle trees utilize the BLS12-381 pairing-friendly elliptic curve:

\begin{align}
    E_1 &: y^2 = x^3 + 4 \text{ over } \mathbb{F}_p \\
    E_2 &: y^2 = x^3 + 4(1+i) \text{ over } \mathbb{F}_{p^2}
\end{align}

where $p = 2^{381} - 2^{255} + 2^0$.

Key properties:
\begin{itemize}
    \item 128-bit security level
    \item Efficient pairing: 2.5 ms on modern CPUs
    \item Small group element: 48 bytes compressed
    \item Subgroup order $r \approx 2^{255}$
\end{itemize}

\subsection{Kate Commitments}

The commitment to polynomial $f(X)$ is:
\begin{equation}
    C = g^{f(\tau)} = \prod_{i=0}^{d} g^{a_i \tau^i}
\end{equation}

Binding property relies on $d$-Strong Diffie-Hellman assumption:
\begin{theorem}[Computational Binding]
If the $d$-SDH assumption holds in $\mathbb{G}_1$, then KZG commitments are computationally binding.
\end{theorem}

\subsection{Fiat-Shamir Transform}

Interactive proofs become non-interactive via Fiat-Shamir:
\begin{equation}
    \alpha = \mathsf{Hash}(transcript || commitment || statement)
\end{equation}

Security requires modeling hash as random oracle.

\subsection{Pairing Operations}

The bilinear pairing $e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$ satisfies:
\begin{itemize}
    \item \textbf{Bilinearity}: $e(g^a, h^b) = e(g,h)^{ab}$
    \item \textbf{Non-degeneracy}: $e(g,h) \neq 1$ for generators $g,h$
    \item \textbf{Efficiency}: Computable in polynomial time
\end{itemize}

Miller loop implementation:
\begin{equation}
    e(P,Q) = f_{r,P}(Q)^{\frac{p^{12}-1}{r}}
\end{equation}