papers/lux-evm-precompiles/sections/04-bn254-extended-precompiles.tex

\section{BN254 Extended Precompiles}
\label{sec:bn254}

\subsection{Motivation}

While EIP-196/197 provide basic BN254 operations, they lack batch pairing verification and optimized MSM. Lux extends BN254 support with:

\begin{table}[H]
\centering
\caption{BN254 extended precompile operations.}
\label{tab:bn254}
\begin{tabular}{lrrl}
\toprule
\textbf{Operation} & \textbf{Lux Gas} & \textbf{EIP-196/197 Gas} & \textbf{Improvement} \\
\midrule
Pairing (2 pairs) & 80,000 & 180,000 & 2.25x \\
Pairing (4 pairs) & 120,000 & 340,000 & 2.83x \\
Batch pairing (random) & $40{,}000k + 40{,}000$ & N/A & New \\
G1 MSM ($n$ points) & $6{,}000n \cdot d(n)$ & $6{,}000n$ & $1/d(n)$x \\
\bottomrule
\end{tabular}
\end{table}

\subsection{Batch Pairing Verification}

For verifying multiple independent pairing equations (e.g., batch Groth16 proofs), we use random linear combination:

\begin{algorithm}[H]
\caption{Batch Pairing Verification}
\label{alg:batch_pairing}
\begin{algorithmic}[1]
\Require $k$ pairing equations $\{e(A_j, B_j) = e(C_j, D_j)\}_{j=1}^k$
\State Sample random $r_1, \ldots, r_k \xleftarrow{\$} \{1, \ldots, 2^{128}\}$
\State Compute $L = \prod_{j=1}^k e(r_j \cdot A_j, B_j)$
\State Compute $R = \prod_{j=1}^k e(r_j \cdot C_j, D_j)$
\If{$L = R$}
    \State \Return \textsc{Accept}
\Else
    \State \Return \textsc{Reject}
\EndIf
\end{algorithmic}
\end{algorithm}

\begin{theorem}[Batch Verification Soundness]
If any individual pairing equation is false, the batch check rejects with probability $\geq 1 - 2^{-128}$.
\end{theorem}

\begin{proof}
By the Schwartz-Zippel lemma, a non-zero polynomial of degree at most 1 in each $r_j$ has at most $k \cdot 2^{-128}$ roots over the field, giving soundness error $\leq k / 2^{128} \approx 2^{-128}$ for practical $k$.
\end{proof}