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.
38 lines
1.5 KiB
TeX
38 lines
1.5 KiB
TeX
\section{BLS Aggregation}
|
|
|
|
|
|
BLS12-381 aggregate signatures provide the only known $O(1)$ signature verification regardless of signer count.
|
|
|
|
\subsection{Benchmarks}
|
|
|
|
\begin{center}
|
|
\begin{tabular}{lrrr}
|
|
\toprule
|
|
\textbf{Operation} & \textbf{Time} & \textbf{Size} & \textbf{Scaling} \\
|
|
\midrule
|
|
Key generation & 10$\mu$s & 48 B (public) & --- \\
|
|
Sign & 15$\mu$s & 96 B & --- \\
|
|
Verify (single) & 1.2ms & --- & $O(1)$ \\
|
|
Aggregate $N$ sigs & $N \times 0.1\mu$s & 48 B (output) & $O(N)$ aggregate, $O(1)$ verify \\
|
|
Verify aggregate ($N=100$) & 1.2ms & 48 B & $O(1)$ \\
|
|
Verify aggregate ($N=1000$) & 1.2ms & 48 B & $O(1)$ \\
|
|
\bottomrule
|
|
\end{tabular}
|
|
\end{center}
|
|
|
|
\begin{observation}[BLS Efficiency]
|
|
BLS aggregation is the only mechanism that scales to thousands of validators without increasing verification cost. This is why it is used for per-block consensus despite lacking post-quantum security.
|
|
\end{observation}
|
|
|
|
\subsection{The Post-Quantum Gap}
|
|
|
|
BLS has no known post-quantum equivalent with the same aggregation property. Post-quantum schemes:
|
|
\begin{itemize}[leftmargin=2em]
|
|
\item ML-DSA: No aggregation. $N$ signatures = $N \times 3{,}309$ bytes.
|
|
\item SLH-DSA: No aggregation. $N$ signatures = $N \times 7{,}856$ bytes.
|
|
\item Lattice-based aggregation: Open research problem. No practical scheme exists.
|
|
\end{itemize}
|
|
|
|
STARK aggregation bridges this gap: compress $N$ ML-DSA signatures into a single $\sim$200 byte proof, with $O(\log N)$ verification. The cost is proof generation time.
|
|
|