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

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

\usetheme{lined}
\usecolortheme{whale}
\setbeamertemplate{footline}[default]
\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{Bitcoin}
    \begin{block}{}<1->
        Bitcoin's state consists of a set of \emph{unspent transaction outputs}
        (\alert{UTXOs}).
    \end{block}

    \begin{block}{}<2->
        \begin{center}
            \begin{tabular}{rcl}
                \outpoint{2302}{b48b7936}{0}&
                $\Leftrightarrow$ &
                \txout{0.02000000}{611ee562}{824e976f}\\
                &&\\ % row spacer
                \outpoint{2302}{b48b7936}{1}&
                $\Leftrightarrow$ &
                \txout{0.45526959}{35c57b0f}{589e6291}\\
            \end{tabular}
        \end{center}
    \end{block}

    \begin{block}{}<1->
        These UTXOs are labelled by an \alert{amount} and \alert{witness program}.
    \end{block}
}

\frame
{
    \frametitle{Bitcoin}
    \begin{block}{}<1->
        Transactions destroy existing UTXOs and create new ones.
    \end{block}

    \begin{block}{}
        \begin{center}
            \outpoint{2302}{b48b7936}{0}
            $\rightarrow$
            \txout{0.01991250}{0356df34}{9c4e33f5}
            ~\\~\\
            \texttt{\tiny txid 39549b99b0f16dff9d3788b602f00df38a4b88ae647e269ecf82c51b15f1de32}
        \end{center}
    \end{block}

    \begin{block}{}
        To spend a UTXO, a transaction must include a \alert{witness}
        for its witness program.
    \end{block}
}

% begin script execution
\frame
{
    \frametitle{Bitcoin}

    \begin{minipage}[c]{0.35\textwidth}
        \witstack
            {e3b0c442}{98fc1c14}
            {witness script}
            {public key\\signature}
    \end{minipage}
    \begin{minipage}[c]{0.6\textwidth}
        \texttt{\alert{DUP HASH160 <hash> EQUALVERIFY CHECKSIG}}
    \end{minipage}
}
\frame
{
    \frametitle{Bitcoin}

    \begin{minipage}[c]{0.35\textwidth}
        \witstack
            {e3b0c442}{98fc1c14}
            {public key}
            {signature}
    \end{minipage}
    \begin{minipage}[c]{0.6\textwidth}
        \texttt{\color{olive}\alert{DUP} HASH160 <hash> EQUALVERIFY CHECKSIG}
    \end{minipage}
}
\frame
{
    \frametitle{Bitcoin}

    \begin{minipage}[c]{0.35\textwidth}
        \witstack
            {e3b0c442}{98fc1c14}
            {public key}
            {public key\\signature}
    \end{minipage}
    \begin{minipage}[c]{0.6\textwidth}
        \texttt{\color{olive}DUP \alert{HASH160} <hash> EQUALVERIFY CHECKSIG}
    \end{minipage}
}
\frame
{
    \frametitle{Bitcoin}

    \begin{minipage}[c]{0.35\textwidth}
        \witstack
            {e3b0c442}{98fc1c14}
            {hash(public key)}
            {public key\\signature}
    \end{minipage}
    \begin{minipage}[c]{0.6\textwidth}
        \texttt{\color{olive}DUP HASH160 \alert{<hash>} EQUALVERIFY CHECKSIG}
    \end{minipage}
}
\frame
{
    \frametitle{Bitcoin}

    \begin{minipage}[c]{0.35\textwidth}
        \witstack
            {e3b0c442}{98fc1c14}
            {<hash>}
            {\alert{hash(public key)}\\public key\\signature}
    \end{minipage}
    \begin{minipage}[c]{0.6\textwidth}
        \texttt{\color{olive}DUP HASH160 <hash> \alert{EQUALVERIFY} CHECKSIG}
    \end{minipage}
}
\frame
{
    \frametitle{Bitcoin}

    \begin{minipage}[c]{0.35\textwidth}
        \witstack
            {e3b0c442}{98fc1c14}
            {public key}
            {\alert{signature}}
    \end{minipage}
    \begin{minipage}[c]{0.6\textwidth}
        \texttt{\color{olive}DUP HASH160 <hash> EQUALVERIFY \alert{CHECKSIG}}
    \end{minipage}
}
\frame
{
    \frametitle{Bitcoin}

    \begin{minipage}[c]{0.35\textwidth}
        \witstack
            {e3b0c442}{98fc1c14}
            {1}
            {}
    \end{minipage}
    \begin{minipage}[c]{0.6\textwidth}
        \texttt{\color{olive}DUP HASH160 <hash> EQUALVERIFY CHECKSIG}
    \end{minipage}
}
% end script execution
% start another script IFDUP NOT 1ADD <pk1> <pk2> 2SWAP ROLL CHECKSIG NIP
\frame
{
    \frametitle{Bitcoin}

    \begin{minipage}[c]{0.3\textwidth}
        \witstack
            {b6194fbc}{410c06ef}
            {witness script}
            {sig2}
    \end{minipage}
    \begin{minipage}[c]{0.3\textwidth}
        \witstack
            {b6194fbc}{410c06ef}
            {witness script}
            {0\\sig1}
    \end{minipage}
    \begin{minipage}[c]{0.38\textwidth}
        \begin{flushright}
            \texttt{\color{olive}\alert{IFDUP NOT 1ADD <pk1> <pk2> 2SWAP ROLL CHECKSIG NIP}}
        \end{flushright}
    \end{minipage}
}
\frame
{
    \frametitle{Bitcoin}

    \begin{minipage}[c]{0.3\textwidth}
        \witstack
            {b6194fbc}{410c06ef}
            {sig2}
            {}
    \end{minipage}
    \begin{minipage}[c]{0.3\textwidth}
        \witstack
            {b6194fbc}{410c06ef}
            {0}
            {sig1}
    \end{minipage}
    \begin{minipage}[c]{0.38\textwidth}
        \begin{flushright}
            \texttt{\color{olive}\alert{IFDUP} NOT 1ADD <pk1> <pk2> 2SWAP ROLL CHECKSIG NIP}
        \end{flushright}
    \end{minipage}
}
\frame
{
    \frametitle{Bitcoin}

    \begin{minipage}[c]{0.3\textwidth}
        \witstack
            {b6194fbc}{410c06ef}
            {sig2}
            {sig2}
    \end{minipage}
    \begin{minipage}[c]{0.3\textwidth}
        \witstack
            {b6194fbc}{410c06ef}
            {0}
            {sig1}
    \end{minipage}
    \begin{minipage}[c]{0.38\textwidth}
        \begin{flushright}
            \texttt{\color{olive}IFDUP \alert{NOT} 1ADD <pk1> <pk2> 2SWAP ROLL CHECKSIG NIP}
        \end{flushright}
    \end{minipage}
}
\frame
{
    \frametitle{Bitcoin}

    \begin{minipage}[c]{0.3\textwidth}
        \witstack
            {b6194fbc}{410c06ef}
            {0}
            {sig2}
    \end{minipage}
    \begin{minipage}[c]{0.3\textwidth}
        \witstack
            {b6194fbc}{410c06ef}
            {1}
            {sig1}
    \end{minipage}
    \begin{minipage}[c]{0.38\textwidth}
        \begin{flushright}
            \texttt{\color{olive}IFDUP NOT \alert{1ADD} <pk1> <pk2> 2SWAP ROLL CHECKSIG NIP}
        \end{flushright}
    \end{minipage}
}
\frame
{
    \frametitle{Bitcoin}

    \begin{minipage}[c]{0.3\textwidth}
        \witstack
            {b6194fbc}{410c06ef}
            {1}
            {sig2}
    \end{minipage}
    \begin{minipage}[c]{0.3\textwidth}
        \witstack
            {b6194fbc}{410c06ef}
            {2}
            {sig1}
    \end{minipage}
    \begin{minipage}[c]{0.38\textwidth}
        \begin{flushright}
            \texttt{\color{olive}IFDUP NOT 1ADD \alert{<pk1>} <pk2> 2SWAP ROLL CHECKSIG NIP}
        \end{flushright}
    \end{minipage}
}
\frame
{
    \frametitle{Bitcoin}

    \begin{minipage}[c]{0.3\textwidth}
        \witstack
            {b6194fbc}{410c06ef}
            {<pk1>}
            {1\\sig2}
    \end{minipage}
    \begin{minipage}[c]{0.3\textwidth}
        \witstack
            {b6194fbc}{410c06ef}
            {<pk1>}
            {2\\sig1}
    \end{minipage}
    \begin{minipage}[c]{0.38\textwidth}
        \begin{flushright}
            \texttt{\color{olive}IFDUP NOT 1ADD <pk1> \alert{<pk2>} 2SWAP ROLL CHECKSIG NIP}
        \end{flushright}
    \end{minipage}
}
\frame
{
    \frametitle{Bitcoin}

    \begin{minipage}[c]{0.3\textwidth}
        \witstack
            {b6194fbc}{410c06ef}
            {<pk2>}
            {\alert{<pk1>}\\1\\sig2}
    \end{minipage}
    \begin{minipage}[c]{0.3\textwidth}
        \witstack
            {b6194fbc}{410c06ef}
            {<pk2>}
            {\alert{<pk1>}\\2\\sig1}
    \end{minipage}
    \begin{minipage}[c]{0.38\textwidth}
        \begin{flushright}
            \texttt{\color{olive}IFDUP NOT 1ADD <pk1> <pk2> \alert{2SWAP} ROLL CHECKSIG NIP}
        \end{flushright}
    \end{minipage}
}
\frame
{
    \frametitle{Bitcoin}

    \begin{minipage}[c]{0.3\textwidth}
        \witstack
            {b6194fbc}{410c06ef}
            {1}
            {sig2\\\alert{<pk2>}\\ <pk1>}
    \end{minipage}
    \begin{minipage}[c]{0.3\textwidth}
        \witstack
            {b6194fbc}{410c06ef}
            {2}
            {sig1\\ <pk2>\\\alert{<pk1>}}
    \end{minipage}
    \begin{minipage}[c]{0.38\textwidth}
        \begin{flushright}
            \texttt{\color{olive}IFDUP NOT 1ADD <pk1> <pk2> 2SWAP \alert{ROLL} CHECKSIG NIP}
        \end{flushright}
    \end{minipage}
}
\frame
{
    \frametitle{Bitcoin}

    \begin{minipage}[c]{0.3\textwidth}
        \witstack
            {b6194fbc}{410c06ef}
            {<pk2>}
            {\alert{sig2}\\ <pk1>}
    \end{minipage}
    \begin{minipage}[c]{0.3\textwidth}
        \witstack
            {b6194fbc}{410c06ef}
            {<pk1>}
            {\alert{sig1}\\ <pk2>}
    \end{minipage}
    \begin{minipage}[c]{0.38\textwidth}
        \begin{flushright}
            \texttt{\color{olive}IFDUP NOT 1ADD <pk1> <pk2> 2SWAP ROLL \alert{CHECKSIG} NIP}
        \end{flushright}
    \end{minipage}
}
\frame
{
    \frametitle{Bitcoin}

    \begin{minipage}[c]{0.3\textwidth}
        \witstack
            {b6194fbc}{410c06ef}
            {1}
            { <pk1>}
    \end{minipage}
    \begin{minipage}[c]{0.3\textwidth}
        \witstack
            {b6194fbc}{410c06ef}
            {1}
            { <pk2>}
    \end{minipage}
    \begin{minipage}[c]{0.38\textwidth}
        \begin{flushright}
            \texttt{\color{olive}IFDUP NOT 1ADD <pk1> <pk2> 2SWAP ROLL CHECKSIG \alert{NIP}}
        \end{flushright}
    \end{minipage}
}
\frame
{
    \frametitle{Bitcoin}

    \begin{minipage}[c]{0.3\textwidth}
        \witstack
            {b6194fbc}{410c06ef}
            {1}
            {}
    \end{minipage}
    \begin{minipage}[c]{0.3\textwidth}
        \witstack
            {b6194fbc}{410c06ef}
            {1}
            {}
    \end{minipage}
    \begin{minipage}[c]{0.38\textwidth}
        \begin{flushright}
            \texttt{\color{olive}IFDUP NOT 1ADD <pk1> <pk2> 2SWAP ROLL CHECKSIG NIP}
        \end{flushright}
    \end{minipage}
}
% end script execution
\frame
{
    \frametitle{Issues with Bitcoin Script}

    \begin{itemize}
    \item Difficult to argue correctness (or other properties)
    \item Difficult to argue security (or malleability freeness)
    \item Difficult to estimate satisfaction cost
    \item Difficult to determine which signatures are needed
    \item Difficult to assemble a witness, even given signatures
    \end{itemize}
}

\frame
{
    \frametitle{Miniscript}

    \begin{itemize}
    \item Idea: create script templates for signature checks, hash-locks and time-locks
    \item Idea: create \alert{composable} script templates for AND, OR and thresholds
    \end{itemize}
}

\frame
{
    \frametitle{Miniscript}
    % todo figure out this \indent black magic
    \begin{minipage}[c]{0.5\textwidth}
        \texttt{2 pk$_1$ pk$_2$ pk$_3$ 3 CHECKMULTISIG\\
        \alert{IFDUP NOTIF}\\
        \indent ~~~~pk\textsubscript{emergency} CHECKSIGVERIFY\\
        \indent ~~~~1000 CSV\\
        \alert{ENDIF}}
    \end{minipage}
    \begin{minipage}[c]{0.45\textwidth}

    \begin{tikzpicture}[
        level 1/.style = {sibling distance=8em},
        level 2/.style = {sibling distance=8em},
    ]
        \node[comb,T] {OR\textsubscript{casc}}
            child { node[term,E] {multi(2,pk$_1$,pk$_2$,pk$_3$)} }
            child { node[comb,T] {AND\textsubscript{cat}}
                child { node[term,V] {pk\textsubscript{emergency}} }
                child { node[term,T] {after(1000)} }
            };
    \end{tikzpicture}
    \end{minipage}
}

\frame
{
    \frametitle{Miniscript}

    \begin{center}
        \renewcommand{\arraystretch}{1.5}
        \begin{tabular}{ccc}
              & \textbf{Satisfaction} & \textbf{Dissatisfaction} \\
            \rowcolor{violet!4}
            T & non-0 & - \\
            V & (nothing) & - \\
            \rowcolor{violet!4}
            F & 1 & - \\
            Q & pubkey & - \\
            \rowcolor{violet!4}
            E & 1 & 0 \\
            W & \texttt{[X 1]} or \texttt{[1 X]}
              & \texttt{[X 0]} or \texttt{[0 X]} \\[-2em]
            % spacing
            \parbox{2em}{~} & \parbox{10em}{~} & \parbox{10em}{~}
        \end{tabular}
    \end{center}
    Under adversarial inputs, all conventions will simply abort the script,
    except T, which may instead put 0 on the stack.
}

\frame
{
    \frametitle{Miniscript}

    \begin{center}
    \begin{tikzpicture}[
        level 1/.style = {sibling distance=20em},
        level 2/.style = {sibling distance=10em},
        level 3/.style = {sibling distance=5em},
    ]
        \node[comb,T] {AND\textsubscript{cat}}
            child { node[comb,V] {OR\textsubscript{cont}}
                child { node[term,E] {pk$_1$} }
                child { node[term,V] {hash(\texttt{e3729fc20045e}...)} }
            }
            child { node[comb,T] {AND\textsubscript{cat}}
                child { node[comb,V] {OR\textsubscript{cont}}
                    child { node[term,E] {pk$_2$} }
                    child { node[term,V] {pk$_3$} }
                }
                child { node[comb,T] {OR\textsubscript{if}}
                    child { node[term,T] {pk$_4$} }
                    child { node[term,T] {after(1000)} }
                }
            };
    \end{tikzpicture}
    \texttt{\tiny
        pk$_1$ CHECKSIG NOTIF SIZE 32 EQUALVERIFY SHA256 \hash{e3729fc2}0045e8b5 EQUALVERIFY ENDIF\\pk$_2$ CHECKSIG NOTIF pk$_3$ CHECKSIGVERIFY ENDIF IF pk$_4$ CHECKSIG ELSE 1000 CSV ENDIF
    }
    \end{center}
}
\frame
{
    \frametitle{Miniscript}

    \begin{center}
    \begin{tikzpicture}[
        level 1/.style = {sibling distance=20em},
        level 2/.style = {sibling distance=10em},
        level 3/.style = {sibling distance=5em},
    ]
        \node[comb] {AND}
            child { node[comb] {OR}
                child { node[term] {pk$_1$} }
                child { node[term] {hash(\texttt{e3729fc20045e}...)} }
            }
            child { node[comb] {AND}
                child { node[comb] {OR}
                    child { node[term] {pk$_2$} }
                    child { node[term] {pk$_3$} }
                }
                child { node[comb] {OR}
                    child { node[term] {pk$_4$} }
                    child { node[term] {after(1000)} }
                }
            };
    \end{tikzpicture}
    \\~\\
    \texttt{\tiny
        pk$_1$ CHECKSIG NOTIF SIZE 32 EQUALVERIFY SHA256 \hash{e3729fc2}0045e8b5 EQUALVERIFY ENDIF\\pk$_2$ CHECKSIG NOTIF pk$_3$ CHECKSIGVERIFY ENDIF IF pk$_4$ CHECKSIG ELSE 1000 CSV ENDIF
    }
    \end{center}
}

\frame
{
    \frametitle{Script and Miniscript}

    \begin{itemize}
    \item In a technical sense, Miniscript is a subset of Script.
    \item In a non-technical sense, Miniscript works in a \alert{different paradigm} than Script
    \item Miniscript describes \alert{conditions to satisfy}, not \alert{instructions to execute}
    \end{itemize}
}

\frame
{
    \frametitle{Future Work}

    \begin{itemize}
    \item Better documentation and more robust tooling
    \item Extensions to support absolute timelocks, different hashes
    \item Extensions to support new Script constructions (pubkey hashes)
    \item Integration with PSBT
    \end{itemize}
}

%% end
\frame
{
    \frametitle{Thank You}
    \begin{center}
    Andrew Poelstra\\
    \texttt{miniscript@wpsoftware.net}\\~\\~\\
    \texttt{\huge https://bitcoin.sipa.be/miniscript}
    \end{center}
}

\end{document}