\def\hs{\hspace{0.4 cm}}
\documentclass{beamer}
\usetheme{Warsaw}
\usecolortheme{beaver}
\setbeamertemplate{footline}[page number]
\beamertemplatenavigationsymbolsempty
\title{Schnorr, MuSig, Scriptless Scripts, and More}
\author{Andrew Poelstra}
\institute{\texttt{scriptless@wpsoftware.net}}
\date{October 10, 2018}
\usepackage{amsfonts,amsmath,latexsym,color,epsfig,graphicx,multirow,rotating}
\usepackage{anyfontsize}
\begin{document}
\frame{ \frametitle{} \begin{center} \includegraphics[scale=0.17]{title.png} \end{center} }
\frame
{
\frametitle{Elliptic Curve Cryptography}
\begin{itemize}
\item EC crypto consists of geometric points with an {\color{blue}addition operator}.\\~\\
\item Such a set is a {\color{blue}group}.\\~\\
\item Any group element $G$ can be ``multiplied'' by an integer $n$ by adding $G$ to
itself repeatedly.
\[ \underbrace{G + G + \cdots + G}_{n\textnormal{ times }} \]
~\\
\item The multiples of $G$ form a {\color{blue}cyclic group} that we say is {\color{blue}generated} by $G$.
\end{itemize}
}
\frame
{
\frametitle{Elliptic Curve Cryptography}
\begin{itemize}
\item Suppose we have a group with $n\sim2^{256}$ elements generated by some point $G$.\\~\\
\item We can efficiently map integers into the group by $x\mapsto xG$.\\~\\
\item This is a {\color{blue}homomorphism}: $xG + yG = (x + y)G$.\\~\\
\item In theory we can map $xG\mapsto x$, but in practice it is an open problem
to do this efficiently with only a classical computer. This is the
{\color{blue}discrete logarithm problem}.\\~\\
\item We can think of $x$ as a {\color{blue}secret key} and $xG$ as a {\color{blue}public key}.
\end{itemize}
}
\frame
{
\frametitle{Elliptic Curve Cryptography}
\begin{center}
\includegraphics[scale=1.10]{sage-ec.png}
\end{center}
}
\frame
{
\frametitle{Elliptic Curve Commitments}
\begin{itemize}
\item Let $H$ be some cryptographic hash function, $c$ some message, and $(x', P')$
a keypair.\\~\\
\item Then $P = P' + H(P'\|c)G$ is a {\color{blue}commitment} to $c$.\\~\\
\item Further, if $x = x' + H(P'\|c)$, then $(x, P)$ is a keypair and somebody
who knows $x'$ definitely knows $x$.\\~\\
\item Further, somebody who knows $(P', c)$ can verify the commitment, while somebody
who knows neither cannot learn anything about them from $P$.
\end{itemize}
}
\frame
{
\frametitle{Taproot and Pay-to-Contract}
\begin{itemize}
\item Consider a hypothetical Bitcoin output labelled by a key $P$, such that
it may be spent by a signature with this key.\\~\\
\item Validators who see this output cannot determine how $P$ was generated, and
an ordinary transaction does not reveal anything about it.\\~\\
\item Suppose, however, that there exists some script $c$ and alternate point $P'$
such that $P = P' + H(P'\|c)G$.
\end{itemize}
}
\frame
{
\frametitle{Taproot and Pay-to-Contract}
\begin{itemize}
\item This construction is called \emph{pay-to-contract} and has been floating around
in some form or another since 2014 at least. (A 2012 paper by Gerhardt and Hanke
described a similar but broken scheme.)\\~\\
\item This is used in Liquid and Elements: the script $c$ is actually the scriptPubkey
of an output on the sidechain.\\~\\
\item But on Bitcoin itself, we could allow a second way to spend these coins: reveal
$(P, c)$ and satisfy the script $c$. Validators would check the commitment and check
the witness for $c$.\\~\\
\item This is {\color{blue}Taproot}.
\end{itemize}
}
\frame
{
\frametitle{ECDSA and EC-Schnorr}
\begin{itemize}
\item Suppose we have a keypair $(x, P)$ with $P = xG$.\\~\\
\item To sign a message $m$, first generate an ephemeral keypair or {\color{blue}nonce},
$(k, R)$.\\~\\
\item Compute $r = R_x$ and $e = H(m)$ (ECDSA) or $e = H(P\|R\|m)$ (Schnorr).\\~\\
\item Compute $s$ such that
\begin{align*}
sk &= e + rx&\text{(ECDSA)}\\
s &= k + ex&\text{(Schnorr)}
\end{align*}
\item The signature is $(s, R)$.
\end{itemize}
}
\frame
{
\frametitle{Sign-to-Contract}
\begin{itemize}
\item By the way, we can do the pay-to-contract/Taproot construction on $R$.\\~\\
\item The result is called {\color{blue}sign-to-contract} and allows committing things
to the blockchain in ordinary transactions with no additional space.
\end{itemize}
}
%% start verification triple
\frame
{
\frametitle{ECDSA and EC-Schnorr}
\begin{itemize}
\item Verification is basically the same as signing
\begin{align*}
sk{\color{white}G} &= e{\color{white}G} + rx{\color{white}G}&\text{(ECDSA)}\\
s{\color{white}G} &= k{\color{white}G} + ex{\color{white}G}&\text{(Schnorr)}
\end{align*}
\end{itemize}
}
\frame
{
\frametitle{ECDSA and EC-Schnorr}
\begin{itemize}
\item Verification is basically the same as signing
\begin{align*}
sk{\color{blue}G} &= e{\color{blue}G} + rx{\color{blue}G}&\text{(ECDSA)}\\
s{\color{blue}G} &= k{\color{blue}G} + ex{\color{blue}G}&\text{(Schnorr)}
\end{align*}
\end{itemize}
}
\frame
{
\frametitle{ECDSA and EC-Schnorr}
\begin{itemize}
\item Verification is basically the same as signing
\begin{align*}
{\color{white}k}sR &= e{\color{blue}G} + r{\color{white}x}P&\text{(ECDSA)}\\
s{\color{blue}G} &= {\color{white}k}R + e{\color{white}x}P&\text{(Schnorr)}
\end{align*}
\end{itemize}
}
%% end verification triple
\frame
{
\frametitle{ECDSA and EC-Schnorr}
\begin{itemize}
\item From this equation we can see that Schnorr signatures are \emph{linear
in the components of the signature} $(s, R)$ and can therefore be added:
\begin{align*}
s_1G &= R_1 + eP_1\\
s_2G &= R_2 + eP_2\\
(s_1 + s_2)G &= (R_1 + R_2) + e(P_1 + P_2)
\end{align*}
Notice same $e$ in both equations --- this requires interaction to achieve.
\item vs ECDSA
\begin{align*}
s_1R_1 &= eG + rP_1\\
s_2R_2 &= eG + rP_2
\end{align*}
\end{itemize}
}
\frame
{
\frametitle{Multisignatures}
\begin{itemize}
\item Suppose $n$ parties with keys $\{P_1,\ldots,P_n\}$ want to jointly sign a message $m$.\\~\\
\item They could create $n$ nonces $\{R_1,\ldots,R_n\}$ and compute
\begin{align*}
P &= P_1 + \cdots + P_n \\
R &= R_1 + \cdots + R_n \\
e &= H(P\|R\|m)
\end{align*}
then each compute $s_i = k_i + x_ie$. Writing $s_i = \sum s_i$, we then have
\[ sG = \left(\sum s_i\right)G = \left(\sum R_i\right) + e\sum P_i = R + eP \]
\end{itemize}
}
\frame
{
\frametitle{Multisignatures}
\begin{itemize}
\item This is a valid signature with $P$, but it does \textbf{not} prove that each
party $P_i$ participated in the production of the signature.\\~\\
\item Suppose that the $n$th party chose $P_n = P - \sum_{i}
\end{center}
}
\end{document}