papers/lux-threshold-mpc/sections/03-frost-protocol.tex

%% ===================================================================
%% LP-134 canonical naming (2025-12-15):
%% Per LP-134 (Lux Chain Topology), T-Chain has been split into:
%%   M-Chain — MPC ceremonies for bridge custody of EXTERNAL wallets
%%             (CGGMP21, FROST, Pulsar-general)
%%   F-Chain — FHE compute + TFHE bootstrap-key generation (encrypted EVM)
%% The legacy name "T-Chain" is retained ONLY for `teleportvm` (LP-6332).
%% Where this paper says "T-Chain MPC" / "T-Chain threshold governance" /
%% "T-Chain TFHE" / "T-Chain custody", read as M-Chain (MPC) or F-Chain (FHE).
%% ===================================================================

\section{FROST Protocol}

\label{sec:frost}
% ============================================================

FROST (Flexible Round-Optimized Schnorr Threshold signatures)~\cite{komlo2020frost}
provides $(t,n)$-threshold Schnorr signatures in two rounds. We describe the protocol
over a generic group $\mathbb{G}$ and specialize to Ed25519 and BIP-340 in
Section~\ref{sec:taproot}.

\subsection{Distributed Key Generation}

FROST DKG uses Pedersen's verifiable secret sharing~\cite{pedersen1991} with
Feldman commitments~\cite{feldman1987}.

\begin{algorithm}[H]
\caption{FROST Distributed Key Generation}
\label{alg:frost-dkg}
\begin{algorithmic}[1]
\Require Threshold $t$, participants $n$, generator $G$
\Ensure Public key $Y$, shares $\{s_i\}_{i=1}^n$
\For{each party $i \in [n]$}
  \State $a_{i,0} \xleftarrow{\$} \mathbb{F}_q$ \Comment{secret coefficient}
  \State $a_{i,k} \xleftarrow{\$} \mathbb{F}_q$ for $k \in [t-1]$
  \State Define $f_i(x) = \sum_{k=0}^{t-1} a_{i,k} x^k$
  \State Broadcast $C_{i,k} = a_{i,k} \cdot G$ for $k = 0, \ldots, t-1$
  \State Send $f_i(j)$ to party $j$ over secure channel
\EndFor
\For{each party $j \in [n]$}
  \State Verify: $f_i(j) \cdot G \stackrel{?}{=} \sum_{k=0}^{t-1} j^k \cdot C_{i,k}$
  \State Compute share $s_j = \sum_{i=1}^n f_i(j) \bmod q$
  \State Compute public key $Y = \sum_{i=1}^n C_{i,0}$
\EndFor
\State \Return $(Y, \{s_i\}_{i=1}^n)$
\end{algorithmic}
\end{algorithm}

\begin{lemma}[DKG Correctness]
\label{lem:dkg-correct}
If all parties are honest, then $s_i$ is a valid Shamir share of
$s = \sum_{i=1}^n a_{i,0}$ under threshold $t$, and $Y = s \cdot G$.
\end{lemma}

\begin{proof}
Define $f(x) = \sum_{i=1}^n f_i(x)$. Then $f(0) = \sum_{i=1}^n a_{i,0} = s$ and
$s_j = f(j)$ for each $j$. Since each $f_i$ has degree $t-1$, $f$ has degree $t-1$,
so $\{(j, s_j)\}_{j=1}^n$ are Shamir shares with threshold $t$. The public key
satisfies $Y = \sum_{i=1}^n C_{i,0} = \sum_{i=1}^n a_{i,0} \cdot G = s \cdot G$.
\end{proof}

\subsection{Two-Round Signing}

\begin{algorithm}[H]
\caption{FROST Threshold Signing}
\label{alg:frost-sign}
\begin{algorithmic}[1]
\Require Message $m$, signer set $S$ with $|S| \geq t$, shares $\{s_i\}_{i \in S}$, public key $Y$
\Ensure Signature $\sigma = (R, z)$
\Statex \textbf{Round 1: Commitment}
\For{each signer $i \in S$}
  \State $d_i, e_i \xleftarrow{\$} \mathbb{F}_q$
  \State $(D_i, E_i) \gets (d_i \cdot G, \; e_i \cdot G)$
  \State Broadcast $(i, D_i, E_i)$
\EndFor
\Statex \textbf{Round 2: Response}
\State $B = \{(i, D_i, E_i)\}_{i \in S}$ \Comment{commitment list}
\For{each signer $i \in S$}
  \State $\rho_i \gets H_1(i, m, B)$ \Comment{binding factor}
\EndFor
\State $R \gets \sum_{i \in S} (D_i + \rho_i \cdot E_i)$
\State $c \gets H_2(R, Y, m)$ \Comment{Schnorr challenge}
\For{each signer $i \in S$}
  \State $z_i \gets d_i + \rho_i \cdot e_i + \lambda_{i,S} \cdot s_i \cdot c$
  \State Broadcast $z_i$
\EndFor
\State $z \gets \sum_{i \in S} z_i$
\State \textbf{Verify:} $z \cdot G \stackrel{?}{=} R + c \cdot Y$
\State \Return $\sigma = (R, z)$
\end{algorithmic}
\end{algorithm}

\begin{theorem}[FROST Correctness]
\label{thm:frost-correct}
If all signers in $S$ follow the protocol, the resulting signature $(R, z)$ satisfies
the Schnorr verification equation $z \cdot G = R + c \cdot Y$.
\end{theorem}

\begin{proof}
\begin{align*}
z \cdot G &= \left(\sum_{i \in S} z_i\right) \cdot G \\
  &= \sum_{i \in S} \left(d_i + \rho_i e_i + \lambda_{i,S} s_i c\right) \cdot G \\
  &= \sum_{i \in S} (D_i + \rho_i E_i) + c \sum_{i \in S} \lambda_{i,S} s_i \cdot G \\
  &= R + c \cdot s \cdot G = R + c \cdot Y
\end{align*}
where the last equality uses the Lagrange interpolation property
$\sum_{i \in S} \lambda_{i,S} s_i = s$.
\end{proof}

\subsection{Chain Coverage}

FROST produces signatures compatible with the following chain families:

\begin{table}[H]
\centering
\small
\begin{tabular}{@{}llll@{}}
\toprule
\textbf{Chain Family} & \textbf{Curve} & \textbf{Sig. Format} & \textbf{Size} \\
\midrule
Solana & Ed25519 & $(R, s)$ & 64 B \\
TON & Ed25519 & $(R, s)$ & 64 B \\
Sui (Ed25519 mode) & Ed25519 & $(R, s)$ & 64 B \\
Aptos & Ed25519 & $(R, s)$ & 64 B \\
Cosmos/IBC & Ed25519 & $(R, s)$ & 64 B \\
Polkadot/Substrate & Sr25519${}^*$ & $(R, s)$ & 64 B \\
NEAR & Ed25519 & $(R, s)$ & 64 B \\
Stellar & Ed25519 & $(R, s)$ & 64 B \\
Cardano & Ed25519 & $(R, s)$ & 64 B \\
Algorand & Ed25519 & $(R, s)$ & 64 B \\
Tezos & Ed25519 & $(R, s)$ & 64 B \\
Bitcoin Taproot & secp256k1${}^\dagger$ & $(R_x, s)$ & 64 B \\
\bottomrule
\end{tabular}
\caption{FROST chain coverage. ${}^*$Polkadot Sr25519 uses Ristretto Schnorr; FROST
adapts via the Ristretto encoding. ${}^\dagger$BIP-340 uses secp256k1 with Schnorr
verification; see Section~\ref{sec:taproot}.}
\label{tab:frost-chains}
\end{table}

% ============================================================