main.tex

% Default course lecture note template by asp 
\documentclass[letterpaper]{article}
\usepackage[top=3cm, bottom=3cm, left=3.85cm, right=3.85cm]{geometry}
\usepackage[onehalfspacing]{setspace}
\usepackage{mathptmx}
\usepackage{amsmath,amssymb,wasysym,amsthm}
\usepackage{hyperref}
\usepackage{lineno,gitinfo}

\newtheorem{lmma}{Lemma}
\newtheorem{corl}{Corallary}
\newtheorem{thrm}{Theorem}
\newtheorem{defn}{Definition}
\newtheorem{expl}{Example}

\newcommand{\TR}[1]{\mathrm{TR}^{#1}}
\newcommand{\Setup}{\mathrm{Setup}}
\newcommand{\KeyGen}{\mathrm{KeyGen}}
\newcommand{\Sign}{\mathrm{Sign}}
\newcommand{\Verify}{\mathrm{Verify}}
\newcommand{\Commit}{\mathrm{Commit}}
\newcommand{\Open}{\mathrm{Open}}
\newcommand{\sk}{\mathrm{sk}}
\newcommand{\pk}{\mathrm{pk}}
\newcommand{\negl}{\mathrm{neg}}
\newcommand{\e}{\hat{e}}
\newcommand{\hash}{\mathcal{H}_2}
\newcommand{\truth}{\{\mathrm{true}, \mathrm{false}\}}
\newcommand{\randgets}{\xleftarrow{\$}}

\title{Taproot Security Proof}
\author{Andrew Poelstra\footnote{\texttt{taproot@wpsoftware.net}}}
\date{\gitAuthorDate{} (commit \texttt{\gitAbbrevHash)}}

\begin{document}

\maketitle

\modulolinenumbers[10]

\begin{defn} Throughout, we assume a security parameter $\lambda$, a
cyclic group $\mathcal{G} = \langle G\rangle$ for which no algorithm can solve the
discrete logarithm in order $p(\lambda)$ except with probability
$\negl(\lambda)$, and two hash functions $H^\pk$, $H^m$ modeled as
random oracles whose output is of length $q(\lambda)$.\end{defn}

\begin{defn} Let $\beta = (\KeyGen^\beta, \Sign^\beta, \Verify^\beta)$ be a
signature scheme. We define the \emph{Taproot} of
$\beta$, denoted $\TR{\beta}$, by the four algorithms

\begin{itemize}
\item $\KeyGen(b)$ takes a bit $b$ and outputs a keypair
$(\sk_0, \sk_1, \pk)$. It acts as follows.

It first selects $\sk^\alpha\randgets\mathbb{Z}/p(\lambda)\mathbb{Z}$,
and computes $\pk^\alpha\gets\sk^\alpha G(\lambda)$.

\begin{itemize}
\item If $b=0$, it simply outputs $(\sk^\alpha, \bot, \pk^\alpha)$.
\item If $b=1$, it obtains $(\sk^\beta, \pk^\beta) \gets \KeyGen^\beta$ and computes
a ``tweak'' $\epsilon\gets H^\pk(\pk^\beta\|\pk^\alpha)$.

It then outputs $\sk_0\gets\sk^\alpha+\epsilon$, $\sk_1=(\sk^\beta, \pk^\alpha, \pk^\beta)$ and
$\pk\gets\pk^\alpha+\epsilon G$.
\end{itemize}

% normal signing
\item $\Sign^1(\sk_0, m)$ takes a secret key $\sk_0$ and message $m$ and outputs
a signature $\sigma$. It acts as follows.
\begin{itemize}
\item It computes $k\randgets\mathbb{Z}/p(\lambda)\mathbb{Z}$, $R\gets kG$, $\pk\gets
\sk_0G$, and $e\gets H^m(\pk\|R\|m)$.
\item It outputs $\sigma = (R, k + e\sk_0)$.
\end{itemize}

% TapRoot signing
\item $\Sign^2(\sk_1 = (\sk^\beta, \pk^\alpha, \pk^\beta), m)$ takes a secret key $\sk_1$ and
message $m$ and outputs a signature $\sigma$. It acts as follows.
\begin{itemize}
\item It computes $\sigma^\beta = \Sign^\beta(\sk^\beta, m)$.
\item It outputs $\sigma = (\pk^\alpha, \pk^\beta, \sigma^\beta)$.
\end{itemize}


\item $\Verify(\pk, \sigma, m)$ takes a public key $\pk$, signature $\sigma$ and
message $m$. It outputs a bit $b$. It acts as follows.

\begin{itemize}
\item If $\sigma = (R, s)$, it computes $e\gets H^m(\pk\|R\|m)$ and accepts
iff $sG = R + e\pk$.

\item If $\sigma = (\pk^\alpha, \pk^\beta, \sigma^\beta)$, it checks first that
$\pk = \pk^\alpha + H^\pk(\pk^\beta\|\pk^\alpha)G$. If so, it accepts iff
$\Verify^\beta(\pk^\beta, \sigma^\beta, m)$ accepts.
\end{itemize}

\end{itemize}

\end{defn}

\begin{thrm} If the discrete logarithm problem is hard in $\mathcal{G}$, and
$\beta$ is (strongly) existentially unforgeable, then $\TR\beta$ is (strongly)
existentially unforgeable in the sense of the following game between adversary
$\mathcal{A}$ and challenger $\mathcal{C}$.

\begin{enumerate}
\item $\mathcal{A}$ chooses a bit $b$ and sends to $\mathcal{C}$.
$\mathcal{C}$ replies with a public key $\pk$ generated (in the adversary's
view) by $\KeyGen(b)$.
\item $\mathcal{A}$ then submits signing queries $(b_i, m_i)$ for $i\in\{1,2,\ldots,q\}$
where $q$ is bounded by some polynomial in $\lambda$. The challenger must respond
with a valid signature $\sigma_i$ of the form generated by $\Sign^b$. (Except that
if $b=0$ a then the challenger may respond $\bot$ whenever $b_i=1$.)
\item $\mathcal{A}$ finally resonds with a signature $(\sigma_*, m_*)$ of either
form, such that $\Verify(\pk, \sigma_*, m_*)$ accepts.

If $\beta$ is strongly existentially unforgeable, we require $(\sigma_*, m_*)\neq
(\sigma_i, m_i)$ for all $i$; otherwise we require further that $m_*\neq m_i$ for
all $i$.
\end{enumerate}
\end{thrm}

The proof consists of two lemmas which consider adversaries who produce the
two different forms of signatures. The intuition is essentially that forging
in the form of $\Sign^2$ is essentially just forging on $\beta$, while
forging in the form of $\Sign^1$ is essentially just forging a Schnorr signature.

\begin{lmma} If such an adversary $\mathcal{A}$ outputs a (strong) forgery in
the form of $\Sign^2$ with probability $\epsilon$, it can be used to produce a
(strong) forgery for $\beta$ with probability $\epsilon-\negl(\lambda,q)$.
\end{lmma}

\begin{proof} Suppose such an adversary $\mathcal{A}$ exists, and consider the
following challenger $\mathcal{C}$, with access to a $\beta$-challenger. First, $\mathcal{C}$ replies to all random
oracle queries uniformly at random.
\begin{enumerate}
\item $\mathcal{C}$ chooses a uniformly random keypair $(\sk^\alpha, \pk^\alpha)$.
\begin{itemize}
\item If $b=0$, he gives $\pk^\alpha$ to $\mathcal{A}$ and stores $\sk=\sk^\alpha$.
\item If $b=1$, he requests a public key $\pk^\beta$ from his $\beta$-challenger,
computes $\pk=\pk^\alpha+ H^\pk(\pk^\beta\|\pk^\alpha)G$, and gives this to $\mathcal{A}$.
He stores $\sk=\sk^\alpha+H^\pk(\pk^\beta\|\pk^\alpha)$.
\end{itemize}

\item Given a signing query $(b_i,m_i)$, $\mathcal{A}$ acts as follows. If $b_i=0$,
he executes $\Sign^1(\sk,m_i)$ and replies with the result $\sigma_i$. If $b_i=1$ and
$b=0$, he returns $\bot$.

If $b_i=1$ and $b=1$, he first obtains $\sigma^\beta_I$ by querying the
$\beta$-challenger on $m_i$. He replies with $\sigma_i=(\pk^\alpha,\pk^\beta,\sigma^\beta)$.

\item Finally, $\mathcal{A}$ responds with a signature $(\sigma_*, m_*)$ in the
form of $\Sign^2$; that is, $\sigma_* = (\pk^\alpha_*, \pk^\beta_*, \sigma^\beta_*)$.
Further, $\sigma^\beta_*$ is a valid signature on $m_*$
with key $\pk^\beta_*$, and $\pk = \pk^\alpha_* + H^\pk(\pk^\beta_*\|\pk^\alpha_*)$.

First, $(\pk^\alpha_*, \pk^\beta_*) = (\pk^\alpha, \pk^\beta)$ except with negligible
probability, since $H^\pk$ is modelled as a random oracle and $\mathcal{A}$ may make
only polynomially many queries to it.

We therefore observe that $\sigma_* = \sigma_i$ iff $\sigma^\beta_* = \sigma^\beta_i$, so that
$(\sigma^\beta_*, m_*)$ is a (strong) forgery for $\beta$ iff $(\sigma, m_*)$ is a
(strong) forgery for $\TR\beta$.
\end{enumerate}
\end{proof}

\begin{lmma} If such an adversary $\mathcal{A}$ outputs a (strong) forgery in
the form of $\Sign^1$ with probability $\epsilon$, it can be used to produce a
strong Schnorr signature forgery on $(\mathcal{G}, G, H^m)$ with probability
$\epsilon-\negl(\lambda,q)$.
\end{lmma}

\begin{proof}
Our challenger $\mathcal{C}$ now acts as follows. He has access to a Schnorr
challenger $\mathcal{S}$ who has a random oracle $H^S$ and expects signatures
of the form $(s, R)$ with $s = R + eP$ and $e = H^S(P\|R\|m)$.

First, if $b=0$, $\mathcal{C}$ forwards a public key from $\mathcal{S}$ to
$\mathcal{A}$, responds to all signatures with $b_i=1$ with $\bot$, and otherwise forwards all signatures to $\mathcal{S}$ and $H^m$ queries
to $H^S$, and presents the resulting forgery unmodified as a Schnorr forgery.
The result is immediate in this case, so we will assume $b=1$ for the
remainder of the proof.

\begin{enumerate}
\item $\mathcal{C}$ requests a public key $\pk^\alpha$ from $\mathcal{S}$,
chooses $(\sk^\beta, \pk^\beta)\gets\KeyGen^\beta$, and computes
$\pk=\pk^\alpha+H^\pk(\pk^\beta\|\pk^\alpha)G$. $\mathcal{C}$ sends $\pk$ to
$\mathcal{A}$.

\item $\mathcal{C}$ responds to $H^\pk$ queries uniformly randomly. $\mathcal{C}$
responds to $H^m$ queries by first replacing $\pk$ with $\pk^\alpha$
and vice-versa, then forwarding the query to $H^S$.

\item $\mathcal{C}$ responds to signature queries $(b_i, m_i)$ as follows. If $b_i=1$,
$\mathcal{C}$ obtains $\sigma_i\gets\Sign^2((\sk^\beta, \pk^\alpha,\pk^\beta), m_i)$
and returns this.

If $b_i=0$, $\mathcal{C}$ requests a signature $(s_i,R_i)$ from $\mathcal{S}$ on $m_i$.
Letting $e_i=H^S(\pk^\alpha\|R\|m_i)$, $\mathcal{C}$ adds $e_iH^\pk(\pk^\beta\|\pk^\alpha)$
to $s_i$ to obtain $s_i'$, and replies with $\sigma_i = (s_i', R_i)$.

We observe that this is actually a valid signature, since
\begin{align*}
s_i'G
    &= s_iG + e_iH^\pk(\pk^\beta\|\pk^\alpha)G	\\
    &= R_i + e_i(\pk^\alpha + H^\pk(\pk^\beta\|\pk^\alpha)G)	\\
    &= R_i + e_i\pk
\end{align*}
But $\mathcal{C}$'s replies to $H^m$ ensure that $e_i=H^S(\pk^\alpha\|R\|m_i)
=H^m(\pk\|R\|m_i)$, so this is exactly the verification equation for
$\TR\beta$.

\item Finally, $\mathcal{A}$ replies with a forgery $(\sigma_*, m_*)$ in the
form of $\Sign^1$ such that $(\sigma_*,m_*)\neq(\sigma_i,m_i)$ for any $i$
and $\Verify(\pk,\sigma_*, m_*)$ accepts.

That is, $\sigma_* = (s_*, R_*)$, $e_* = H^m(\pk\|R_*\|m_*) = H^S(\pk_\alpha\|R_*\|m_*)$, and
\begin{align*}
(s_* - e_*H^\pk(\pk^\beta\|\pk^\alpha))G
    &= R_* + e_*\pk - H^\pk(\pk^\beta\|\pk^\alpha)G
    &= R_* + e_*\pk^\alpha
\end{align*}
so that $(s_* - e_*H^\pk(\pk^\beta\|\pk^\alpha), R_*)$ is a valid Schnorr
signature which is not equal to output of any signature query to $\mathcal{S}$.
\end{enumerate}

\end{proof}

\paragraph{License.} This work is released into the public domain.

\end{document}