papers/lux-evm-precompiles/sections/05-secp256k1-batch-verification.tex

\section{Secp256k1 Batch Verification}
\label{sec:batch}

\subsection{Design}

The standard \texttt{ecrecover} precompile verifies one ECDSA signature per call at 3,000 gas. For applications verifying many signatures (e.g., multisig wallets, state channels, rollup batches), we provide batch verification:

\begin{algorithm}[H]
\caption{Secp256k1 Batch Signature Verification}
\label{alg:batch_ecdsa}
\begin{algorithmic}[1]
\Require $n$ tuples $(h_j, r_j, s_j, \mathsf{pk}_j)$
\State Sample random weights $\alpha_1, \ldots, \alpha_n \xleftarrow{\$} \{1, \ldots, 2^{128}\}$
\State Compute $R_{\text{batch}} \gets \sum_{j=1}^n \alpha_j \cdot R_j$ \Comment{$R_j$ from $(r_j, s_j)$}
\State Compute $S_{\text{batch}} \gets \sum_{j=1}^n \alpha_j \cdot s_j^{-1} \cdot h_j \cdot G + \sum_{j=1}^n \alpha_j \cdot s_j^{-1} \cdot r_j \cdot \mathsf{pk}_j$
\If{$R_{\text{batch}} = S_{\text{batch}}$}
    \State \Return \textsc{Accept all}
\Else
    \State Fall back to individual verification to identify invalid signatures
    \State \Return bitmap of valid signatures
\EndIf
\end{algorithmic}
\end{algorithm}

\subsection{Gas Cost Model}

\begin{equation}
    G_{\text{batch}}(n) = 3{,}000 + 1{,}800 \cdot n
\end{equation}

This is cheaper than $n$ individual \texttt{ecrecover} calls ($3{,}000n$) for $n \geq 2$:
\begin{equation}
    \text{Savings} = 1 - \frac{3{,}000 + 1{,}800n}{3{,}000n} = 1 - \frac{1}{n} - 0.6 = 0.4 - \frac{1}{n}
\end{equation}

For $n = 100$: savings of 39\% ($180{,}000$ vs.\ $300{,}000$ gas).

\begin{table}[H]
\centering
\caption{Batch vs.\ sequential secp256k1 verification costs.}
\label{tab:batch_secp}
\begin{tabular}{rrrr}
\toprule
\textbf{Signatures} & \textbf{Sequential Gas} & \textbf{Batch Gas} & \textbf{Savings} \\
\midrule
10 & 30,000 & 21,000 & 30\% \\
50 & 150,000 & 93,000 & 38\% \\
100 & 300,000 & 183,000 & 39\% \\
500 & 1,500,000 & 903,000 & 40\% \\
\bottomrule
\end{tabular}
\end{table}