mirror of
https://github.com/lux-apps/papers.git
synced 2026-10-30 18:15:21 +00:00
zeekay
abf99d05fc
Restructured from flat .tex/.pdf files into per-paper subdirectories. Added Antje Worring as co-author on all papers. Synced PDFs to pdfs/ for download site.
81 lines
2.8 KiB
TeX
81 lines
2.8 KiB
TeX
\section{BLS12-381 Precompiles}
|
|
\label{sec:bls12381}
|
|
|
|
\subsection{Curve Parameters}
|
|
|
|
BLS12-381 \cite{bowe2017bls12381} is a pairing-friendly elliptic curve with:
|
|
\begin{align}
|
|
\mathbb{G}_1 &: y^2 = x^3 + 4 \quad \text{over } \mathbb{F}_p, \quad p \approx 2^{381} \\
|
|
\mathbb{G}_2 &: y^2 = x^3 + 4(u + 1) \quad \text{over } \mathbb{F}_{p^2} \\
|
|
|\mathbb{G}_1| &= |\mathbb{G}_2| = r \approx 2^{255}
|
|
\end{align}
|
|
|
|
Security level: approximately 128 bits. Embedding degree: 12.
|
|
|
|
\subsection{Operations and Gas Costs}
|
|
|
|
\begin{table}[H]
|
|
\centering
|
|
\caption{BLS12-381 precompile gas costs vs.\ EIP-2537 proposal.}
|
|
\label{tab:bls_gas}
|
|
\begin{tabular}{lrrr}
|
|
\toprule
|
|
\textbf{Operation} & \textbf{Lux Gas} & \textbf{EIP-2537 Gas} & \textbf{Benchmark (ms)} \\
|
|
\midrule
|
|
G1 Add & 500 & 500 & 0.01 \\
|
|
G1 Scalar Mul & 12,000 & 12,000 & 0.37 \\
|
|
G1 MSM ($n$ points) & $12{,}000 \cdot n \cdot d(n)$ & same & $0.37n \cdot d(n)$ \\
|
|
G2 Add & 800 & 800 & 0.02 \\
|
|
G2 Scalar Mul & 45,000 & 45,000 & 1.40 \\
|
|
Pairing ($k$ pairs) & $43{,}000k + 65{,}000$ & $43{,}000k + 65{,}000$ & $0.5k + 1.2$ \\
|
|
Map to G1 & 5,500 & 5,500 & 0.16 \\
|
|
Map to G2 & 110,000 & 110,000 & 3.30 \\
|
|
\bottomrule
|
|
\end{tabular}
|
|
\end{table}
|
|
|
|
The discount function $d(n)$ for multi-scalar multiplication (MSM) is:
|
|
\begin{equation}
|
|
d(n) = \max\left(0.4, \frac{1}{\lfloor \log_2 n \rfloor + 1}\right)
|
|
\end{equation}
|
|
reflecting Pippenger's algorithm sublinear scaling.
|
|
|
|
\subsection{Input Validation}
|
|
|
|
\begin{algorithm}[H]
|
|
\caption{BLS12-381 Pairing Input Validation}
|
|
\label{alg:bls_validate}
|
|
\begin{algorithmic}[1]
|
|
\Require Input bytes $I$
|
|
\If{$|I| = 0$ or $|I| \mod 288 \neq 0$}
|
|
\State \Return error (invalid length; each pair = 128 + 160 bytes)
|
|
\EndIf
|
|
\State $k \gets |I| / 288$
|
|
\For{$j = 0$ to $k-1$}
|
|
\State Parse $P_j \in \mathbb{G}_1$ from $I[288j : 288j + 128]$
|
|
\State Parse $Q_j \in \mathbb{G}_2$ from $I[288j + 128 : 288(j+1)]$
|
|
\State Verify $P_j$ is on curve $E(\mathbb{F}_p)$ and in subgroup $\mathbb{G}_1$
|
|
\State Verify $Q_j$ is on curve $E'(\mathbb{F}_{p^2})$ and in subgroup $\mathbb{G}_2$
|
|
\If{any check fails}
|
|
\State \Return error (point not on curve or not in subgroup)
|
|
\EndIf
|
|
\EndFor
|
|
\State \Return valid
|
|
\end{algorithmic}
|
|
\end{algorithm}
|
|
|
|
Subgroup checks are essential for security: accepting points outside the prime-order subgroup enables small-subgroup attacks that break pairing-based protocols \cite{barreto2006subgroup}.
|
|
|
|
\subsection{Application: Groth16 Verification}
|
|
|
|
BLS12-381 pairings enable on-chain Groth16 zk-SNARK verification:
|
|
|
|
\begin{proposition}[Groth16 Verification Cost]
|
|
Verifying a Groth16 proof with $\ell$ public inputs costs:
|
|
\begin{equation}
|
|
G_{\text{groth16}} = (\ell + 1) \cdot 12{,}000 + 3 \cdot 43{,}000 + 65{,}000 = 12{,}000\ell + 206{,}000
|
|
\end{equation}
|
|
For $\ell = 10$ public inputs: $326{,}000$ gas, approximately \$0.02 at typical gas prices.
|
|
\end{proposition}
|
|
|