\def\hs{\hspace{0.4 cm}}

\documentclass[aspectratio=169,usenames,dvipsnames]{beamer}

\usetheme{lined}
\usecolortheme{whale}
\setbeamertemplate{footline}[page number]
\beamertemplatenavigationsymbolsempty

\title{
    Monerokon Madness: Schnorr Schnadness
}
\author{
    Andrew Poelstra\\
    \small
    Director of Research, Blockstream
}
\date{June 20, 2019}

\usepackage{colortbl}
\usepackage{multirow}
\usepackage{tikz}

\tikzset{
    every node/.style = {
        shape=rectangle,
        rounded corners,
        draw,
        top color = white,
        label distance=-0.5ex,
    },
    comb/.style = { bottom color = blue!20 },
    term/.style = { bottom color = red!50 },
    E/.style = { label = {below:\tiny E} },
    F/.style = { label = {below:\tiny F} },
    Q/.style = { label = {below:\tiny Q} },
    T/.style = { label = {below:\tiny T} },
    V/.style = { label = {below:\tiny V} },
    W/.style = { label = {below:\tiny W} },
}

\newcommand{\outpoint}[3]{
    \framebox{
        \texttt{\hash{#1}#2\color{black!60}:#3}
    }
}
\newcommand{\txout}[3]{
    \framebox{\parbox{10em}{
        #1 BTC\\
        \texttt{\hash{#2}#3}
    }}
}
\newcommand{\hash}[9]{\texttt{\color{black!60}#1\color{black!55}#2\color{black!50}#3\color{black!45}#4\color{black!35}#5\color{black!25}#6\color{black!15}#7\color{black!10}#8\color{black!5}#9}}
\newcommand{\witstack}[4]{
    \framebox{\parbox{10em}{
        \texttt{\hash{#1}#2}
    }}
    \framebox{\parbox[t][8em]{10em}{\texttt{
        ~\\
        \alert{#3}\\
        #4
    }}}
}

\setlength{\fboxsep}{1ex}
\begin{document}
\frame{ \maketitle }

\frame
{
    \frametitle{Schnorr Signatures}

    \begin{itemize}
        \item \alert{Schnorr signatures} are an alternate signature scheme to ECDSA
        \item Proposed for Bitcoin as part of \alert{Taproot}
        \item Used in Monero since the Cryptonote days, courtesy of \alert{ed25519}
    \end{itemize}
}

\frame
{
    \frametitle{Schnorr Signatures}

    Schnorr signatures have an especially simple formulation
    for single signers:
    \begin{center}
        \begin{align*}
        k &\gets \$\\
        e &\gets H(\ldots)\\
        s &\gets k - xe
        \end{align*}
    \end{center}
}
\frame
{
    \frametitle{Schnorr Signatures}

    Schnorr signatures have an especially simple formulation
    for multi-signers:
    \begin{center}
        \begin{align*}
        k_i &\gets \$\\
        e &\gets H(\ldots)\\
        s_i &\gets k_i - x_ie
        \end{align*}
    \end{center}
}

\frame
{
    \frametitle{Nonce Bias}

    \begin{itemize}
    \item Like ECDSA, Schnorr signatures require an \alert{uniformly random
        nonce}
    \item Any bias is deadly
    \item Publicly verifying unbiasedness is hard
    \end{itemize}
}
\frame
{
    \frametitle{Nonce Bias}

    \begin{itemize}
    \item Idea: use \alert{RFC6979} to deterministically generate nonces.
    \item Great idea. But totally unverifiable.
    \end{itemize}
}
\frame
{
    \frametitle{Nonce Bias}

    \begin{itemize}
    \item Idea: use \alert{sign to contract} to mix randomness into an untrusted
        device's nonce
    \item $R \to R + H(R\|\$)$
    \end{itemize}
}
\frame
{
    \frametitle{Nonce Bias}
    \begin{itemize}
    \item But naively combining RFC6979 with s2c will lead to \alert{trivial secret
        key extraction}
    \item (We all know ``never reuse nonces''. But also, never use
        \alert{related nonces}.)
    \item (Even on the same message.)
    \end{itemize}
}

\frame
{
    \frametitle{Multisignatures}
    \begin{itemize}
    \item Schnorr multisignatures are easy!
    \item $s_i = k_i + x_ie$
    \item 1. Add the nonces. 2. Add the signatures.
    \end{itemize}
}

\frame
{
    \frametitle{Multisignatures}

    \begin{itemize}
    \item \alert{Rogue-key attacks} require you randomize the keys and signatures
    \item \alert{Wagner's algorithm} requires you mix randomness from every key
        into every key
    \item It also requires \alert{precommitting to nonces} before adding them (MuSig)
    \end{itemize}
}
\frame
{
    \frametitle{Multisignatures}

    \begin{itemize}
    \item Again, \alert{mixing RFC6979 and multisignatures} will lead to key extraction
    \item Naive or not. No way to do it
    \item Heh, well, maybe with sufficiently powerful ZKPs
    \end{itemize}
}
\frame
{
    \frametitle{Multisignatures}

    \begin{itemize}
    \item Need \alert{fresh randomness} for every signature. No RFC6979.
    \item Can we at least share nonces before choosing the message?
    \item \alert{No.} Wagner again. (Jonas Nick, 2 days ago)
    \end{itemize}
}

\frame
{
    \frametitle{Threshold Signatures}

    \begin{itemize}
    \item Schnorr threshold signatures are easy!
    \item Secret-share the keys. Replace keys with sums of shares.
    \item 1. Add the nonces. 2. Add the signatures.
    \end{itemize}
}

\frame
{
    \frametitle{Threshold Signatures}
    \begin{itemize}
    \item First, all of the above problems apply.
    \item Then, make sure you have a \alert{new nonce} for every signature,
       even for the same sig with same (combined) key
    \end{itemize}
}

\frame
{
    \frametitle{Threshold Signatures}
    \begin{itemize}
    \item If you need $k$ honest participants, have $k$ honest participants,
       but \alert{also have some dishonest ones}, can you recover? (Looks like it. But no.)
    \item Can you at least determine \alert{who} was dishonest? (Not easy.)
    \item What if ``dishonest'' just means \alert{timing out}? (Still not easy. Harder actually.)
    \end{itemize}
}

\frame
{
    \frametitle{Threshold Signatures}
    \begin{itemize}
    \item Unrelatedly, \alert{provable security} is much harder (public key biasing)
    \end{itemize}
}

%% end
\frame
{
    \frametitle{Thank You}
    \begin{center}
    Andrew Poelstra\\
    \texttt{monerokon@wpsoftware.net}\\~\\~\\
    \end{center}
}

\end{document}