\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<n} P_i$ for some key $P$ that
  xe knows the secret key to.\\~\\
  \item Then $P = \sum P_i$ is actually entirely controlled by the $n$th party, who
  can produce signatures without anyone else's involvement.
  \end{itemize}
}

\frame
{
  \frametitle{Multisignatures}
  \begin{itemize}
  \item We could prevent this by using {\color{blue}knowledge-of-secret-key (KOSK)},
  i.e. having the participants refuse to participate unless every other participant
  had proven control over their individual key.\\~\\
  \item This is a bad fit for Bitcoin where the signers don't necessarily choose the
  public key (the sender does).\\~\\
  \item But also, it doesn't work with Taproot! Suppose our attacker chooses $P_n$
  by first choosing some $P_n'$ and a script $c$ which gives xir all the coins. Xe
  computes $P = \sum_{i<n} P_i + P_n'$ and publishes $P_n = P_n' + H(P\|c)G$.
  \end{itemize}
}

\frame
{
  \frametitle{Multisignatures}
  \begin{itemize}
  \item Instead, we use a key-combining technique called {\color{blue}MuSig}\footnote{Well,
  technically MuSig refers to the full signing scheme. But I spent a lot of time mixing
  keys and basically no time signing anything, so I've started using ``MuSig'' to refer to just
  the key-combination part.}.\\~\\
  \item In MuSig, rather than taking $P = P_1 + \cdots + P_n$, we first compute
\begin{align*}
C &= H(P_1\|\cdots\|P_n)\\
\mu_i &= H(C\|i) &\text{for each $i$}\\
P &= \sum_i \mu_i P_i
\end{align*}
  \item Now every party must choose their public key $P_i$ before learning any $\mu_i$ or $P$, so
  it is impossible to cancel others' contributions or add Taproot commitments.
  \end{itemize}
}

\frame
{
  \frametitle{Multisignatures --- 2-of-2 MuSig Example}
  \begin{enumerate}
  \item \textbf{Key Setup.} Suppose Alice and Bob choose public keys $P_A$ and $P_B$, and send these to
  each other. They can both compute $C = H(P_A\|P_B)$, $\mu_A = H(C\|1)$, $\mu_B = H(C\|2)$ and
  $P = \mu_AP_A + \mu_BP_B$.\\~\\
  \item \textbf{Signing (1).} They agree on a message $m$. The parties compute nonces $(k_A, R_A)$
  and $(k_B, R_B)$ and exchange the public halves. They both compute $R = R_A + R_B$ and $e =
  H(P\|R\|m)$\footnote{\color{red}Edit 2018-10-07 you \textbf{must} add a ``exchange precommits to $R_A$, $R_B$
  round, cf \texttt{https://eprint.iacr.org/2018/417}}\\~\\
  \item \textbf{Signing (2).} They each compute
\begin{align*}
s_A &= k_A + \mu_A x_A e\\
s_B &= k_B + \mu_B x_B e
\end{align*}
and add these together.
  \end{enumerate}
}

\frame
{
  \frametitle{Sign-to-Contract Redox}
  \begin{itemize}
  \item Each partial signature should have the form $s_i = k_i + e\mu_ix_i$, where $e$ is a
  commitment to, among other things, the total nonce $R$.\\~\\
  \item If one party wants the signature to sign some auxillary data --- for example, a detailed
   invoice or audit log in a Lightning payment --- they can require that $R$ has the form $R=
   R' + H(R'\|c)G$, where $c$ is the auxillary data.\\~\\
  \item It can be shown that if the underlying signature scheme is secure, then the extended
   scheme where $(R', c)$ are revealed is also a secure signature on $c$.
  \end{itemize}
}

\frame
{
  \frametitle{Adaptor Signatures}
  \begin{itemize}
  \item Suppose that in the MuSig protocol some party gave an invalid $s_i$
  so that the final signature did not validate. Could the guilty party be identified?\\~\\
  \item Yes -- just as for complete signatures, the ``partial signatures'' $s_i$ have a
  verification equation
\begin{align*}
s_i &= k_i + e\mu_i x_i\\
s_iG &= k_iG + e\mu_i x_iG\\
s_iG &= R_i + e\mu_i P_i
\end{align*}
  \end{itemize}
}

\frame
{
  \frametitle{Adaptor Signatures}
  \begin{itemize}
  \item We can extend this verification equation to make these partial signatures more powerful.\\~\\
  \item Suppose that party $i$ chooses yet another ephemeral keypair $(t_i, T_i)$, called an
  {\color{blue}adaptor}, and offsets the signature as
\[ s_i' = k_i + e\mu_i x_i + t_i \]
  \item This is verifiable; it's equivalent to
\[ s_i'G = R_i + e\mu_i P_i + T_i \]
  \item and anyone who knows $s_i'$ will learn a valid signature $s_i$ on the same hash $e$
 \textbf{if and only if} they learn $t_i$.
  \end{itemize}
}

\frame
{
  \frametitle{Adaptor Signatures}
  Suppose Bob sends coins to an output controlled by the key $P = \mu_AP_A +
\mu_BP_B$\footnote{And suppose that he adds a Taproot commitment to a timelocked refund.},
with the intention of sending these coins to Alice.
  \begin{enumerate}
  \item Like a standard multisignature, they start by exchanging nonces $R_A$ and $R_B$ and
computing the messagehash $e$. However Alice \emph{also} provides a second public key $T_A$.
  \item Alice provides an adaptor signature $s_A' = k_A + \mu_A x_A + t_A$.
  \item Bob provides an ordinary partial signature $s_B = k_B + \mu_B x_B$.
  \item Alice computes $s_A = k_A + \mu_Ax_A$, adds this to $s_B$ to get a complete signature,
and uses this to take her coins. {\color{red}In doing so, she reveals $t_A$ to Bob.}
  \end{enumerate}
}

\frame
{
  \frametitle{Adaptor Signatures and ZKCP}
  \begin{itemize}
  \item In the previous protocol, Bob ``bought'' the discrete log $t_A$ of $T_A$ from Alice,
in a trustless way.\\~\\
  \item The obvious application of this is a {\color{blue}zero-knowledge contingent payment}.\\~\\
  \item Here $t_i$ is the (encryption key to) a witness to some NP problem, and Alice
  proves beforehand that this is the case.\\~\\
  \item Some useful examples exist that are naturally expressed as discrete logs. e.g.
  Pedersen commitment openings, blind sigs.\\~\\
  \item (Jonas Nick has adaptor-signature-based protocols for both.)
  \end{itemize}
}

\frame
{
  \frametitle{Adaptor Signatures and Atomic Swaps}
  \begin{itemize}
  \item Finally we get to the point of this workshop: atomic swaps using adaptor signatures.\\~\\
  \item On a high level, this works by doing the ``sell $t_i$'' protocol twice in parallel.\\~\\
  \item More specifically, both Alice and Bob put coins into jointly controlled outputs. They
  start to sign transactions that send Alice's coins to Bob and Bob's coins to Alice, but once
  again Alice first provides adaptor signatures in place of real partial signatures.\\~\\
  \item Specifically, she provides adaptor signatures with \emph{the same adaptor $T_A$}. Then
  when she completes the transaction that gives her coins, Bob learns $t_A$, which he uses to
  take his coins.
  \end{itemize}
}

\frame
{
  \frametitle{~}

  \begin{center}
  Thank You
  ~\\~\\
  Andrew Poelstra \texttt{<scriptless@wpsoftware.net>}
  \end{center}
}

\end{document}