papers/zoo-consensus/sections/05-gpu-batch-verification.tex

\section{GPU Batch Verification}


\subsection{Architecture}

Zoo validators already maintain GPUs for AI inference workloads. \Quasar{} co-locates consensus verification on these GPUs, amortizing hardware costs. The verification pipeline processes both BLS and \Corona{} signatures on GPU:

\begin{algorithm}
\caption{GPU Dual-Path Batch Verification}
\begin{algorithmic}[1]
\REQUIRE Blocks $\{B_1, \ldots, B_m\}$, BLS signatures $\{\sigma^{\text{BLS}}_j\}$, Corona shares $\{\sigma^{\text{RT}}_{i,j}\}$
\STATE \textbf{GPU Stream 0 (BLS):}
\STATE \quad Copy $\{pk_i\}$, $\{H(B_j)\}$, $\{\sigma^{\text{BLS}}_j\}$ to GPU
\STATE \quad Launch pairing kernel: batch verify all $m$ aggregate signatures
\STATE \quad Return $\texttt{bls\_valid}[1..m]$
\STATE \textbf{GPU Stream 1 (Corona):}
\STATE \quad Copy $\{pk^{\text{RT}}_i\}$, $\{H_{\text{lat}}(B_j)\}$, $\{\sigma^{\text{RT}}_j\}$ to GPU
\STATE \quad Launch NTT kernel: batch polynomial multiplication
\STATE \quad Launch verification kernel: check norm bounds
\STATE \quad Return $\texttt{rt\_valid}[1..m]$
\STATE \textbf{Synchronize streams}
\STATE $\texttt{final\_valid}[j] \leftarrow \texttt{bls\_valid}[j] \wedge \texttt{rt\_valid}[j]$ for all $j$
\end{algorithmic}
\end{algorithm}

\subsection{GPU Kernel Design}

The BLS kernel parallelizes: (1)~hash-to-curve via SWU map \cite{wahby2019fast}, one thread per block; (2)~multi-scalar multiplication via Pippenger's algorithm, 32 points per warp; (3)~pairing via 65 Miller loop iterations with $\mathbb{F}_{p^{12}}$ multiplications across 12 threads.

The \Corona{} kernel targets polynomial operations in $\mathbb{Z}_q[X]/(X^d + 1)$: (1)~NTT with $\log_2(1024) = 10$ fully parallelizable butterfly stages; (2)~parallel norm reduction for $\|\sigma\|_\infty < \beta$; (3)~NTT-multiply-INTT pipeline for polynomial evaluation.

\subsection{Performance Results}

\begin{table}[h]
\centering
\begin{tabular}{lccc}
\toprule
\textbf{Operation} & \textbf{CPU (ms)} & \textbf{GPU (ms)} & \textbf{Speedup} \\
\midrule
BLS verify (single) & 1.8 & 0.9 & 2.0x \\
BLS verify (batch 1000) & 1,800 & 180 & 10.0x \\
BLS verify (batch 10000) & 18,000 & 1,650 & 10.9x \\
Corona verify (single) & 4.2 & 1.1 & 3.8x \\
Corona NTT (batch 1000) & 4,200 & 520 & 8.1x \\
Dual-path (batch 1000) & 6,000 & 540 & 11.1x \\
\bottomrule
\end{tabular}
\caption{Verification latency: Intel Xeon 8380 vs NVIDIA A100 (40\,GB)}
\label{tab:gpu-perf}
\end{table}

The dual-path batch result (540\,ms for 1,000 blocks) demonstrates that parallel execution of both paths on separate GPU streams adds negligible overhead compared to BLS-only verification. The 10x batch speedup for BLS arises from amortizing the pairing's final exponentiation and exploiting GPU parallelism in multi-scalar multiplication.

\subsection{GPU Memory Budget}

\begin{table}[h]
\centering
\begin{tabular}{lcc}
\toprule
\textbf{Component} & \textbf{Per Validator} & \textbf{1000 Validators} \\
\midrule
BLS public key ($\mathbb{G}_1$) & 48\,B & 48\,KB \\
Corona public key & 1,952\,B & 1,952\,KB \\
Signature buffers & 256\,B & 256\,KB \\
NTT twiddle factors & --- & 32\,KB \\
Working memory & --- & 64\,KB \\
\midrule
\textbf{Total} & \textbf{$\sim$1.3\,KB} & \textbf{$\sim$1.3\,MB} \\
\bottomrule
\end{tabular}
\caption{GPU memory allocation for validator set}
\label{tab:gpu-mem}
\end{table}

At 1.3\,MB for 1,000 validators, the consensus state occupies $< 0.01\%$ of a 16\,GB GPU, leaving the remainder available for AI inference workloads.