papers/lux-threshold-mpc/sections/05-bitcoin-taproot-integration.tex

\section{Bitcoin Taproot Integration}

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

Bitcoin Taproot (BIP-341~\cite{bip341}) uses Schnorr signatures per BIP-340~\cite{bip340}
over secp256k1 with x-only public keys. This requires specific adaptations to the
FROST protocol.

\subsection{BIP-340 Schnorr Signatures}

BIP-340 defines Schnorr verification as follows. Given message $m$, signature
$(R_x, s)$ where $R_x$ is the 32-byte x-coordinate of $R$, and x-only public key
$P_x$:

\begin{enumerate}[nosep]
  \item Lift $P_x$ to point $P$ with even y-coordinate.
  \item Lift $R_x$ to point $R$ with even y-coordinate.
  \item Compute $e = H_{\text{BIP0340/challenge}}(R_x \| P_x \| m)$.
  \item Accept iff $s \cdot G = R + e \cdot P$.
\end{enumerate}

\subsection{FROST KeygenTaproot}

Standard FROST keygen produces a full public key $Y = (Y_x, Y_y)$. BIP-340 requires
x-only keys (implicitly even y-coordinate). We define \textsc{KeygenTaproot}:

\begin{algorithm}[H]
\caption{FROST KeygenTaproot}
\label{alg:frost-taproot-keygen}
\begin{algorithmic}[1]
\Require Standard FROST DKG output $(Y, \{s_i\}_{i=1}^n)$
\Ensure x-only public key $P_x$, adjusted shares $\{s'_i\}$
\If{$Y$ has odd y-coordinate}
  \State $s'_i \gets q - s_i$ for all $i \in [n]$ \Comment{negate all shares}
  \State $P \gets -Y$ \Comment{now has even y-coordinate}
\Else
  \State $s'_i \gets s_i$ for all $i$
  \State $P \gets Y$
\EndIf
\State $P_x \gets$ x-coordinate of $P$ \Comment{32 bytes}
\State \Return $(P_x, \{s'_i\}_{i=1}^n)$
\end{algorithmic}
\end{algorithm}

\subsection{FROST SignTaproot}

Signing must also ensure $R$ has even y-coordinate per BIP-340:

\begin{algorithm}[H]
\caption{FROST SignTaproot}
\label{alg:frost-taproot-sign}
\begin{algorithmic}[1]
\Require Message $m$, signer set $S$, adjusted shares $\{s'_i\}$, x-only key $P_x$
\Ensure BIP-340 signature $(R_x, z)$
\State Execute FROST Rounds 1--2 (Algorithm~\ref{alg:frost-sign}) to obtain $(R, z)$
\If{$R$ has odd y-coordinate}
  \State $R \gets -R$
  \State $z \gets q - z$ \Comment{negate response}
\EndIf
\State $R_x \gets$ x-coordinate of $R$
\State $e \gets H_{\text{BIP0340/challenge}}(R_x \| P_x \| m)$
\State \textbf{Verify:} $z \cdot G \stackrel{?}{=} R + e \cdot P$
\State \Return $(R_x, z)$ \Comment{standard 64-byte BIP-340 signature}
\end{algorithmic}
\end{algorithm}

\begin{proposition}[Taproot Compatibility]
\label{prop:taproot}
Signatures produced by Algorithm~\ref{alg:frost-taproot-sign} pass BIP-340 verification
by any standard Bitcoin Taproot verifier.
\end{proposition}

\begin{proof}
The negation steps ensure both $R$ and $P$ have even y-coordinates, matching the
BIP-340 convention. The challenge hash uses $R_x$ and $P_x$ per the BIP-340 tagged
hash specification. The verification equation $z \cdot G = R + e \cdot P$ is the
standard Schnorr equation. Since the output is a pair $(R_x, z)$ of two 32-byte
values, it conforms to the 64-byte BIP-340 signature format.
\end{proof}

\subsection{Tapscript Integration}

For Taproot outputs using Tapscript (BIP-342~\cite{bip342}), the threshold public key
$P_x$ can be placed in the key-path spend, enabling direct Schnorr spending without
revealing the threshold structure. This provides:

\begin{itemize}[nosep]
  \item \textbf{Privacy}: On-chain, the UTXO is indistinguishable from a single-signer
    Taproot output. The threshold structure is never revealed.
  \item \textbf{Efficiency}: Key-path spends are the cheapest Bitcoin transaction type
    (1 input witness: 64-byte signature).
  \item \textbf{Fallback}: Script-path spends can encode alternative spending conditions
    (e.g., timelocked recovery) in the Tapscript tree.
\end{itemize}

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