\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{June 15, 2017}

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

\begin{document}
\frame{ \maketitle }

\frame
{
  \frametitle{Overview / What is Mimblewimble?}
  \begin{itemize}
  \item Mimblewimble is an anonymously-originated design for a blockchain-based
        ledger that is very different from Bitcoin.
  \item Unlike Bitcoin transactions, transaction verification can be done with
        only ``kernels'', which are multisignature keys of the transactors. The
        inputs and outputs are auxiliary and can be deleted.
  \item To allow this deletion, Mimblewimble outputs (and inputs) are inherently
        scriptless.
  \item However, smart contracting in Mimblewimble is still possible using ``scriptless
        scripts''. These are more efficient and private than ordinary Bitcoin or
        Ethereum scripts, and can potentially be used with those blockchains.
  \end{itemize}
}


\frame
{
  \frametitle{An Anonymous History of Blockchain Tech}
  \begin{itemize}
  \item November 2008: Satoshi Nakamoto announces Bitcoin; first client released January 2009\\~\\
  \item December 2012: Nicolas van Saberhagen announces Bytecoin, using ring signatures
        to enhance transaction privacy\\~\\
  \item September 2013: Horaus Yuan Mouton announces ``OWAS'', a pre-Mimblewimble technology
        whitepaper that uses pairing-based cryptography\\~\\
  \item August 2014: sundance describes ``Byzantine Cycle Mode'', a method to improve
        Greg Maxwell's CoinJoin by better hiding transaction amounts.
  \end{itemize}
}

\frame
{
  \frametitle{An Anonymous History of Blockchain Tech}
  \begin{itemize}
  \item August 2016: Tom Elvis Jedusor posts a .onion link to a text file on IRC and
        disappears. It describes ``Mimblewimble'', an enhanced variant of Maxwell's
        Confidential Transactions,  on IRC and disappears\\~\\
  \item October 2016: ``Ignotus Peverell'' appears on IRC and announces a project on Github
        to implement MimbleWimble.\\~\\
  \item November 2016-Present: yet more Harry Potter characters have appeared and continue
        to develop the project
  \end{itemize}
}

\frame
{
  \frametitle{More History of Mimblewimble}
  \begin{itemize}
  \item After Ignotus Peverell appeared, we discussed practicalities and found that
        aggregate signatures would give space savings on top of the Voldemort scheme
  \item January 2017: Ethan Heilman (of TumbleBit fame), Ruben Somsen and myself discover
        that we could add a weak form of scripting to MimbleWimble to get Lightning, atomic
        swaps, Tumblebit, etc.
  \item However, adding scripting to Mimblewimble would hurt its otherwise perfect fungibility
  \item These ideas evolve into ``scriptless scripts'', a way to move the script verification
        into the signatures themselves, simplifying and hiding them
  \end{itemize}
}

\frame {
  \frametitle{More History of Mimblewimble}
  \begin{itemize}
  \item January 2017: Tim Ruffing and Pedro Moreno-Sanchez announce ValueShuffle, a
        method to securely combine Confidential Transactions\\~\\
  \item April 2017: Blockstream announces Confidential Assets, I publish a design I'd been
        sitting on for a multi-asset Mimblewimble\\~\\
  \item May 2017: Luna Lovegood appears on the Mimblewimble list to discuss ValueShuffle
        on Mimblewimble. In fact, Tim had already been planning to work on this.
  \end{itemize}
}

\frame
{
  \frametitle{Mimblewimble Transactions}
  A Mimblewimble transaction is the following data:
  \begin{itemize}
  \item Inputs (references to old outputs).\\~\\
  \item Outputs: confidential transaction outputs (group elements, which blind
        and commit to amounts), plus rangeproofs.\\~\\
  \item Kernel: algebraically, difference between outputs and inputs (group element);
        morally a multisignature key for all transacting parties.\\~\\
  \item Kernel signature: proves the kernel is really a multisignature key, and is not
        hiding any coins
  \end{itemize}
}

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

%\frame {
%  \frametitle{Mimblewimble Blocks}
%  Blocks consist of:
%  \begin{itemize}
%  \item <1-> A merkle tree of transaction inputs.
%  \item <2-> A merkle tree of transaction outputs and rangeproofs.
%  \item <3-> A list of kernel(s) and their signature(s)
%  \end{itemize}
%}

%% Illustration of full blockchain merge and cuttthrough
\frame{ \frametitle{Mimblewimble Transactions} \begin{center} \includegraphics[scale=0.06]{8txes/8txes-1.png} \end{center} }
\frame{ \frametitle{Mimblewimble Transactions} \begin{center} \includegraphics[scale=0.06]{8txes/8txes-2.png} \end{center} }
\frame{ \frametitle{Mimblewimble Transactions} \begin{center} \includegraphics[scale=0.06]{8txes/8txes-3.png} \end{center} }
\frame{ \frametitle{Mimblewimble Transactions} \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 350
        million outputs, 45 million of which are unspent.
  \item This takes about 100Gb of space on disk today; with CT this
        would be over 1Tb!
  \item MimbleWimble gives us CT and requires storing: ~15Gb of
        transaction kernels, headers etc.; 2Gb of unspent outputs,
        and 100Gb of UTXO rangeproofs.
  \item In pre-segwit Bitcoin, none of this is separable ``witness
        data'' which can be dropped in exchange for trust. In MW
        the rangeproofs are, leaving less than 20Gb of normative
        blockchain space.
  \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 is a blockchain design that supports only scriptless scripts,
        and derives its privacy and scaling properties from this.
  \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 Schnorr signatures: signer has a keypair $(x, P)$.\\~\\
  \item A signature is the public half of an ``ephemeral keypair'' $(k, R)$
        along with a linear equation in $x$ and $k$. Equation depends on the
        hash of a message.\\~\\
  \item Signature can be verified because the key-derivation map $x\mapsto P$
        is also linear.\\~\\
  \item ECDSA signatures (used in Bitcoin) have the same basic shape but aren't
linear in $x$ and $k$, so they are less useful.
  \end{itemize}
}

\frame
{
  \frametitle{Simplest (Sorta) Scriptless Script}
  \begin{itemize}
  \item \texttt{OP\_RETURN} outputs are used in Bitcoin to encode data for purpose
        of timestamping.\\~\\
  \item Alternate: replace a public key $P$ with $P + \texttt{Hash}(P\|m)G$.\\~\\
  \item Replacing the signer's public key is called ``pay to contract'' and is used
        by Elements and Liquid to move coins onto a sidechain.\\~\\
  \item Replacing the ephemeral key is called ``sign to contract''. Used to
        attach a timestamp to an unrelated transaction with zero network
        overhead.
  \end{itemize}
}

\frame
{
  \frametitle{Schnorr multi-Signatures are Scriptless Scripts}
  \begin{itemize}
  \item By adding Schnorr signature keys, a new key is obtained which can only
        be signed with with the cooperation of all parties.\\~\\
  \item Can be generalized to $m$-of-$n$ by all parties giving $m$-of-$n$
        linear secret shares to all others so they can cooperatively replace
        missing parties.\\~\\
  \item (Don't try this at home: some extra precautions are needed to prevent
        adversarial choice of keys.) 
  \end{itemize}
}

\frame
{
  \frametitle{ZKCPs in Scriptless Script}
  \begin{itemize}
  \item Zero-Knowledge Contingent payments (Greg Maxwell): sending coins conditioned
        on the recipient providing the solution to some hard problem.
  \item Recipient provides a hash $H$ and a zk-proof that the preimage
        is the encryption key to a valid solution. Sender puts coins in a script
        that allows claimage by revealing the preimage.
  \item Use the signature hash $e$ in place of $H$ and now you have a scriptless
        script ZKCP: a single digital signature which cannot be created without
        the signer solving some arbitrary (but predetermined) problem for you.
  \item Alternate: Banasik, Dziembowski and Malinowski (2016/451)
  \end{itemize}
}

\frame
{
  \frametitle{Simultaneous Scriptless Scripts}
  \begin{itemize}
  \item Executing separate transactions in an atomic fashion is traditionally
        done with preimages: if two transactions require the preimage to the
        same hash, once one is executed, the preimage is exposed so that the
        other one can be too.\\~\\
  \item Atomic Swaps (Tier Nolan) and Lightning channels (Poon/Dryja) use this construction.\\~\\
  \item ``Use the message-hash as the hash'' doesn't work here to scriptless-scriptify
        this because message hashes can't be fixed before a signature is created. Worse,
        this would link the two transactions,
        violating the spirit of scriptless scripts.
  \end{itemize}
}

\frame
{
  \frametitle{Adaptor Signatures}
  \begin{itemize}
  \item Instead use another ephemeral keypair $(t, T)$ and treat $T$ as the
        ``hash'' of $t$.\\~\\
  \item When doing a multi-signature replace the old ephemeral key $R$ with $R + T$,
        and now the signature $s$ must be replaced by $s + t$ to be valid.\\~\\
  \item Now the original $s$ is an ``adaptor signature''. Anyone with this can
        compute a valid signature from $t$ or vice-versa. They can verify
        that it is an adaptor signature for $T$, no trust needed.\\~\\
  \item One can compute an adaptor signature without knowing $t$, but they
        will then be unable to produce a real signature.
  \end{itemize}
}

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

  \begin{itemize}
  \item Parties Alice and Bob send coins on their respective
        chains to 2-of-2 outputs. Bob thinks of a keypair $(t, T)$ and gives $T$ to
        Alice.\\~\\
  \item Before Alice signs to give Bob his coins, she demands adaptor signatures with $T$
        from him for \emph{both} his signatures: the one taking his coins and the one giving
        her coins.\\~\\
  \item Now when Bob signs to take his coins, Alice learns $t$ from one adaptor signature,
        which she can combine with the other adaptor signature to take \emph{her} coins.
  \end{itemize}
}

\frame
{
  \frametitle{Basic Lightning}

  \begin{itemize}
  \item Suppose Alice is paying David through Bob and Carol. She produces an onion-routed
        path
        \[ \textnormal{Alice} \to \textnormal{Bob} \to \textnormal{Carol} \to \textnormal{David} \]
        and asks for public keys $B$, $C$ and $D$ from each participant.\\~\\
  \item She sends coins to a 2-of-2 between her and Bob. She asks Bob for an adaptor signature
        with $B + C + D$ before signing to send him the coins.\\~\\
  \item Similarly Bob sends coins to Carol, first demanding an adaptor signature with $C + D$
        from her. Carol sends to David, demanding an adaptor signature with $D$.
  \end{itemize}
}

\frame
{
  \frametitle{Features of Adaptor Signatures}
  \begin{itemize}
  \item Adaptor signatures work across blockchains, even if they use different EC groups,
        though this requires a bit more work.\\~\\
  \item After a signature hits the chain, anyone can make up a $(t, T)$ and
        compute a corresponding ``adaptor signature'' for it, so the scheme is deniable.
        It also does not link the signatures in any way.\\~\\
  \item Adaptor signatures are re-blindable, as we saw in the Lightning example. This
        is also deniable and unlinkable.
  \end{itemize}
}

\frame
{ 
  \frametitle{Sorceror's Scriptless Script}

  \begin{itemize}
  \item Mimblewimble is the ultimate scriptless script.\\~\\
  \item Every input and output has a key, and a transaction signature uses a multisignature
        of all these keys.\\~\\
  \item Transaction validity is now contained in a scriptless script; further,
        the signature has be used with other scriptless script constructions
        (atomic swaps, ZKCP, etc.) to add additional validity requirements with
        zero overhead or even visibility to the network.
  \end{itemize}
}

\frame
{
  \frametitle{Open Problems}
  \begin{itemize}
  \item Quantum-resistant Mimblewimble\\~\\
  \item Efficient / Aggregatable rangeproofs\\~\\
  \item Preserving scriptless scripts in multisig\\~\\
  \item ECDSA support\\~\\
  \item Locktimes and other extrospection\\~\\
  \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}