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

\documentclass{beamer}

\usetheme{Warsaw}
\usecolortheme{crane}
\setbeamertemplate{footline}[page number]
\beamertemplatenavigationsymbolsempty

\title{Mimblewimble and Scriptless Scripts}
\author{Andrew Poelstra}
\institute{\texttt{grindelwald@wpsoftware.net}}
\date{January 10, 2018}

\usepackage{amsfonts,amsmath,latexsym,color,epsfig,graphicx,multirow,rotating}

\begin{document}
\frame{ \maketitle }

\frame
{
  \frametitle{What is a Blockchain?}
  \begin{itemize}
  \item For our purposes, a \emph{blockchain} is a Merkleized linked list of
        commitments, called \emph{blocks}, along with rules restricting the
        committed data.\\~\\
  \item (Also, critical but irrelevant magic, there is global
        consensus on what this list is.)\\~\\
  \item In Bitcoin the blocks are Merkle trees of transactions, each of which may
        not conflict with any other across the entire chain.
  \end{itemize}
}


\frame
{
  \frametitle{What is Mimblewimble?}
  \begin{itemize}
  \item Anyone can download the blockchain, validate all the committed data,
        and determine the current system state, the \emph{unspent transaction
        output set (utxoset)}.\\~\\
  \item Basically every cryptocurrency uses this model, up to structure and
        naming of the system state.\\~\\
  \item Mimblewimble, proposed in August 2016 by Tom Elvis Jedusor, is an alternate
        design where transaction data eventually becomes irrelevant and can be
        dropped, even for new validators.
  \end{itemize}
}

\frame
{
  \frametitle{Talk Outline}
  \begin{enumerate}
  \item How are Mimblewimble transactions structured to enable this redundancy?\\~\\
        Hint: they are restricted to be very simple.\\~\\~\\
  \item How, despite these restrictions, can we still execute trustless multiparty
        cryptosystems (``smart contracts'')?
  \end{enumerate}
}

\frame
{
  \frametitle{Confidential Transactions and Pedersen Commitments}
  \begin{itemize}
  \item Given a dollar value $v\in\mathbb{Z}/q\mathbb{Z}$, choose uniformly random
        $r\in\mathbb{Z}/q\mathbb{Z}$ and compute
        \[ C = vH + rG \]
        where $H$, $G\in\mathcal{G}\simeq\mathbb{Z}/q\mathbb{Z}$ are generators of
        a DL-hard group.\\~\\
  \item Attach a \emph{rangeproof} that $v<<q$, \emph{i.e.} our amounts are in the part of
        $\mathbb{Z}/q\mathbb{Z}$ that basically acts like $\mathbb{Z}^+$.\\~\\
  \item Replace all the amounts in a Bitcoin transaction with Pedersen commitments;
        verifiers check for each transaction that
        \[ \sum_{C\in\textnormal{inputs}} C \qquad=\qquad \sum_{C\in\textnormal{outputs}} C \]
  \end{itemize}
}

\frame {
  \frametitle{Mimblewimble: Transactions}
  \begin{itemize}
  \item Observe that the blinding factors $r$ in the input commitments must sum to the
        blinding factors in the output commitments.\\~\\
  \item Therefore it is impossible to construct a transaction without knowing the sum
        of its inputs' blinding factors, each of which should be secret.\\~\\
  \item Mimblewimble: drop all other forms of authentication and just do this.
  \end{itemize}
}

\frame {
  \frametitle{Mimblewimble: Kernels}
  \begin{itemize}
  \item This almost works, except that parties within the same transaction would learn
        about each others' secret blinding factors $r$. (Sum of one party's blinding
        factors equals the sum of the other's.)\\~\\
  \item By adding an unspendable 0-valued output to each transaction, called a
        \emph{kernel}, multiple parties can produce a transaction together without
        anyone learning each others' secret $r$ values.\\~\\
  \item Each participant $i$ chooses a blinding factor $\rho_i$ and sets the kernel
        commitment to $K = \sum_i \rho_i G$. They produce a multisignature with this
        key to authenticate the transaction and prove that $K$ is 0-valued.
  \end{itemize}
}

%% Illustration of two-transaction merge and cutthrough
\frame{ \frametitle{Mimblewimble in Pictures} \begin{center} \includegraphics[scale=0.09]{onetx/onetx-1.png} \end{center} }
\frame{ \frametitle{Mimblewimble in Pictures} \begin{center} \includegraphics[scale=0.09]{onetx/onetx-2.png} \end{center} }
\frame{ \frametitle{Mimblewimble in Pictures} \begin{center} \includegraphics[scale=0.09]{onetx/onetx-3.png} \end{center} }
\frame{ \frametitle{Mimblewimble in Pictures} \begin{center} \includegraphics[scale=0.09]{onetx/onetx-4.png} \end{center} }

%% Illustration of full blockchain merge and cuttthrough
\frame{ \frametitle{Mimblewimble in Pictures} \begin{center} \includegraphics[scale=0.06]{8txes/8txes-1.png} \end{center} }
\frame{ \frametitle{Mimblewimble in Pictures} \begin{center} \includegraphics[scale=0.06]{8txes/8txes-2.png} \end{center} }
\frame{ \frametitle{Mimblewimble in Pictures} \begin{center} \includegraphics[scale=0.06]{8txes/8txes-3.png} \end{center} }
\frame{ \frametitle{Mimblewimble in Pictures} \begin{center} \includegraphics[scale=0.06]{8txes/8txes-4.png} \end{center} }

\frame
{ 
  \frametitle{Mimblewimble Scaling: Real Numbers}

  \begin{itemize}
  \item In Bitcoin there are 150 million transactions with about 400
        million outputs, 65 million of which are unspent.\\~\\
  \item This takes about 180Gb of space on disk today; with CT this
        would increase by another 270Gb.\\~\\
  \item MimbleWimble gives us CT and requires storing: ~18Gb of
        transaction kernels, headers etc.; 2Gb of unspent outputs,
        and 45Gb of UTXO rangeproofs.
  \end{itemize}
}

\frame
{
  \frametitle{``Scriptless Scripts''}
  \begin{itemize}
  \item Scriptless scripts: magicking digital signatures so that they can only
        be created by faithful execution of a smart contract.\\~\\
  \item Limited in power, but not nearly as much as you might expect.\\~\\
  \item Mimblewimble, having no permanent data except kernels and their signatures,
        supports only scriptless scripts, But anything that supports Schnorr
        signatures will support scriptless scripts.
  \end{itemize}
}

\frame
{
  \frametitle{Why use Scriptless Scripts?}
  \begin{itemize}
  \item Bitcoin (and Ethereum, etc.) uses a scripting language to describe smart
        contracts and enforce their execution.\\~\\
  \item These scripts must be downloaded, parsed, validated by all full nodes on
        the network. Can't be compressed or aggregated.\\~\\
  \item The details of the script are visible forever, compromising privacy and
        fungibility.\\~\\
  \item With scriptless scripts, the only visible things are public keys (i.e.
        uniformly random curvepoints) and digital signatures.\\~\\
  \end{itemize}
}

\frame
{
  \frametitle{Schnorr Signatures Support Scriptless Scripts}
  \begin{itemize}
  \item Basic Schnorr multisignature: signers have keypairs $(x_i, P_i)$
        with $P_i = x_iG$.\\~\\
  \item Agree on a message, compute uniformly random $R_i = k_iG$, and exchange
        $R_i$.\\~\\
  \item Each computes $R = \sum_i R_i$, $P = \sum_i P_i$, $e = H(P\|R\|m)$, and
        $s_i = k_i + ex_i$.\\~\\
  \item Signature is $(s, R)$ with $s=\sum_i s_i$. Validates as $sG = P + eR$.\\~\\
  \item (Here we ignore key cancellation attacks etc. Be careful!)
  \end{itemize}
}

\frame
{
  \frametitle{Schnorr multi-Signatures are Scriptless Scripts}
  \begin{itemize}
  \item Observe that this multisignature is already a scriptless script: the signing
        parties agree on a set $\{P_i\}$ of keys, but blockchain validators see only
        the sum $P$ and don't care about the details.\\~\\
  \item Can be generalized to $m$-of-$n$ by linear secret sharing.\\~\\
  \item In general, scriptless scripts will derive their power from these signatures
        being (verifiably) linear in all secret inputs.
  \end{itemize}
}

\frame
{
  \frametitle{Adaptor Signatures}
  \begin{itemize}
  \item Consider the Schnorr multisignature construction, modified such that the
        first party generates $T_1=t_1G$. In place of $R_1$ it passes $R_1+T_1$
        to the other parties. Alongside $s_1$ it passes $T_1$. Nothing else changes\\~\\
  \item We call the set $(T_1, T_1+R_1, s_1)$ an \emph{adaptor signature}.\\~\\
  \item The final signature $(s, R)$ isn't valid, but $(s + t_1, R)$ is.\\~\\
  \item Before signing, the other parti(es) verify $s_1G = R_1 + eP_1$, and therefore
        that knowledge of $t_1$ will be equivalent to knowledge of a valid signature.
  \end{itemize}
}

\frame
{
  \frametitle{Features of Adaptor Signatures}
  \begin{itemize}
  \item By attaching auxiliary proofs to $T_1$ to ensure $t_1$ is some necessary data
        for a separate protocol, arbitrary steps of arbitrary protocols can be made
        equivalent to signature production.\\~\\
  \item In a blockchain context, this means parties can be trustlessly paid for
        continued honest participation.\\~\\
  \item In particular, by using the same $T_1$ in multiple adaptor signatures it is
        possible to make arbitrary sets of signatures atomic, as we will see in the
        next example. Extremely cheap.\\~\\
  \item After a signature hits the chain, anyone can make up a $T_1$ and compute a
        corresponding ``adaptor signature'' for it, so such schemes are deniable/private.
  \end{itemize}
}


\frame
{
  \frametitle{Example: Atomic (Cross-chain) Swaps}

  \begin{itemize}
  \item Suppose Alice wants to trade 10 $A$-coins for 5 of Bob's $B$-coins.\\~\\
  \item On their respective chains, each moves the coins to outputs that can only be spent
        by a 2-of-2 multisignature with both Alice and Bob.\\~\\
  \item They do sign the multisignature protocols in parallel, except that in both cases
        Bob gives Alice adaptor signatures using \emph{the same} $T_1$.\\~\\
  \item Bob replaces one of the signatures $(s, R)$ with $(s+t_1, R)$ and publishes it, to
        take his coins. Alice sees this, learns $t_1$, then does the same thing on the
        other chain to take her coins.
  \end{itemize}
}

\frame
{
  \frametitle{Open Problems}
  \begin{itemize}
  \item Quantum-resistant analogues to all this\\~\\
  \item Scriptless scripts with more than 2 parties\\~\\
  \item Formalizing/understanding limits of scriptless scripts
  \end{itemize}
}

\frame
{
  \frametitle{~}

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

\end{document}