mirror of
https://github.com/lux-apps/papers.git
synced 2026-11-03 05:07:46 +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.
62 lines
2.3 KiB
TeX
62 lines
2.3 KiB
TeX
\section{FROST: Threshold Schnorr and BLS Signatures}
|
|
|
|
\label{sec:frost}
|
|
|
|
\subsection{Protocol Overview}
|
|
|
|
FROST (Flexible Round-Optimized Schnorr Threshold)~\cite{komlo2020frost} is a
|
|
two-round threshold Schnorr signature protocol. Unlike CGGMP21, FROST operates
|
|
over groups where Schnorr signatures are native, making it suitable for:
|
|
|
|
\begin{itemize}[leftmargin=2em]
|
|
\item Ed25519 (Solana, Cosmos, Polkadot)
|
|
\item BLS12-381 (Ethereum consensus, Lux consensus)
|
|
\item BIP-340 Taproot (Bitcoin)
|
|
\end{itemize}
|
|
|
|
\subsection{Two-Round Protocol}
|
|
|
|
\begin{algorithm}[ht]
|
|
\caption{FROST Signing.}
|
|
\label{alg:frost}
|
|
\begin{algorithmic}[1]
|
|
\Require Message $m$; key shares $sk_i$ for $i \in S$; $|S| = t$
|
|
\Ensure Schnorr signature $(\tilde{R}, z)$
|
|
\State \textbf{Round 1 (commitment):}
|
|
\ForAll{$P_i \in S$}
|
|
\State Sample $(d_i, e_i) \leftarrow \mathbb{Z}_q^2$
|
|
\State Broadcast $(D_i, E_i) = (d_i \cdot G, e_i \cdot G)$
|
|
\EndFor
|
|
\State \textbf{Round 2 (response):}
|
|
\State $B \leftarrow \{(i, D_i, E_i)\}_{i \in S}$
|
|
\State $\rho_i \leftarrow H(\text{``binding''}, i, m, B)$ for each $i$
|
|
\State $\tilde{R} \leftarrow \sum_{i \in S} (D_i + \rho_i \cdot E_i)$
|
|
\State $c \leftarrow H(\tilde{R}, pk, m)$ \Comment{Fiat-Shamir challenge}
|
|
\ForAll{$P_i \in S$}
|
|
\State $z_i \leftarrow d_i + \rho_i \cdot e_i + \lambda_i \cdot sk_i \cdot c$
|
|
\State Broadcast $z_i$
|
|
\EndFor
|
|
\State $z \leftarrow \sum_{i \in S} z_i$
|
|
\State \Return $(\tilde{R}, z)$
|
|
\end{algorithmic}
|
|
\end{algorithm}
|
|
|
|
\subsection{FROST for BLS}
|
|
|
|
FROST extends naturally to BLS signatures because BLS signing is a scalar
|
|
multiplication $\sigma = sk \cdot H(m)$ in $\mathbb{G}_1$. Threshold BLS:
|
|
|
|
\begin{enumerate}[leftmargin=2em]
|
|
\item Each party computes partial signature $\sigma_i = sk_i \cdot H(m)$.
|
|
\item The coordinator reconstructs $\sigma = \sum_{i \in S} \lambda_i \cdot \sigma_i$.
|
|
\item Verification: $e(\sigma, G_2) = e(H(m), pk)$ where $pk \in \mathbb{G}_2$.
|
|
\end{enumerate}
|
|
|
|
BLS threshold signing requires only \emph{one} round (each party independently
|
|
computes their partial signature). No precomputation or commitment phase is needed.
|
|
This makes BLS threshold signing significantly faster than ECDSA threshold signing.
|
|
|
|
%% ========================================================================
|
|
%% 6. KEY RESHARING
|
|
%% ========================================================================
|