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

\documentclass{beamer}

\usetheme{Berlin}
\usecolortheme{wolverine}
\setbeamertemplate{footline}[page number]
\usefonttheme{structureitalicserif}
\beamertemplatenavigationsymbolsempty
\setbeamertemplate{footline}{ }

\title{Scriptless Scripts}
\author{Andrew Poelstra}
\institute{\texttt{grindelwald@wpsoftware.net}}
\date{March 4, 2017}

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

\begin{document}
\frame{ \maketitle }

\section{Scriptless Scripts}  %% unclear what effect this has, but is needed for the subsections to show up 

\subsection{Introduction}
\frame
{
  \frametitle{``Scriptless Scripts''?}
  \begin{itemize}
  \item <1-> Scriptless scripts: magicking digital signatures so that they can only
             be created by faithful execution of a smart contract.
  \item <2-> Limited in power, but not nearly as much as you might expect
  \item <3-> 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 <1-> Bitcoin (and Ethereum, etc.) uses a scripting language to describe smart
             contracts and enforce their execution
  \item <2-> These scripts must be downloaded, parsed, validated by all full nodes on
             the network.
  \item <3-> Have little intrinsic structure to be compressed or aggregated
  \item <4-> The details of the script are visible forever and compromise privacy and
             fungibility.
  \item <5-> 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 <1-> Schnorr signatures: signer has a secret key $x$, ephemeral secret key $k$.
             Publishes a public key $xG$.
  \item <2-> A signature is the ephemeral public key $kG$ as well as
\[ s = k - ex \]
where $e = H(kG\|xG\|\textrm{message})$.
  \item <3-> Verified by checking
\[ sG = kG - exG \]
  \item <4-> ECDSA signatures (used in Bitcoin) have the same shape, but $s$ lacks
some structure and $e$ commits to only the message.
  \end{itemize}
}

\subsection{Scriptless scripts in the wild}
\frame
{
  \frametitle{Simplest (Sorta) Scriptless Script}
  \begin{itemize}
  \item <1-> \texttt{OP\_RETURN} outputs are used in Bitcoin to encode data for purpose
             of timestamping
  \item <2-> Instead, replace the public key (or emphemeral key) $P$ with $P + \texttt{Hash}(P\|m)G$.
  \item <3-> Replacing the public key is called ``pay to contract'' and is used by
             Elements and Liquid to move coins onto a sidechain.
  \item <4-> Replacing the emphemeral key is called ``sign to contract'' and can be
             used to append a message commitment in any ordinary transaction with
             zero network overhead.
  \item <5-> Works with Schnorr or ECDSA
  \end{itemize}
}

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

\frame
{
  \frametitle{moSt exSpressive Scriptless Script}
  \begin{itemize}
  \item <1-> Zero-Knowledge Contingent payments: sending coins conditioned on the
             recipient providing the solution to some hard problem.
  \item <2-> 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 <3-> 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 <4-> Must be done as a multisig between sender and receiver so that the sender
             can enforce what $e$ is.
  \end{itemize}
}

\frame
{
  \frametitle{Simultaneous Scriptless Scripts}
  \begin{itemize}
  \item <1-> 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 <2-> Atomic Swaps and Lightning channels use this construction.
  \item <3-> The previous hash-preimage construction doesn't work because a signature
             hash can't be controlled like this, plus it would require nonce-reuse
             (breaking the signature security), plus it would link the two transactions,
             which violates the spirit of scriptless scipts.
  \end{itemize}
}

\frame
{
  \frametitle{Simultaneous Scriptless Scripts}
  \begin{itemize}
  \item <1-> Instead what we do is consider the difference of two Schnorr signatures:
  \[ d = s - s' = k - k' + ex - e'x' \]
  \item <2-> Given $kG$, $k'G$, $e$, $e'$ this construction can be verified as
  \[ dG = kG - k'G + exG - e'x'G \]
  \item <3-> Given $d$ and either $s$ or $s'$, the other can be computed. So possession
  of $d$ makes these two signatures atomic!
  \item <4-> But since $d$ is computable by anybody after $s$, $s'$ are available,
  this scheme does nothing to link the two signatures or harm their security.
  \end{itemize}
}

%% Illustration of two-transaction merge and cutthrough
\frame
{ 
  \frametitle{Sorceror's Scriptless Script}

  \begin{itemize}
  \item <1-> MimbleWimble is the ultimate scriptless script.
  \item <2-> Every input and output has a key (actually a Pedersen commitment, but
             the transaction balances exactly when these commitment behave like keys;
             this trick is Confidential Transactions).
  \item <3-> A transaction signature uses the multisignature key of all input and
             output keys (called a ``kernel'' in MimbleWimble parlance). It is
             irrelevant what gets signed, just that something is.
  \item <4-> 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.
  \end{itemize}
}

\subsection{Conclusion}
\frame
{
  \frametitle{Open Problems}
  \begin{itemize}
  \item <1-> Generic scriptless scripts
  \item <2-> Locktimes or other extrospection
  \end{itemize}
}

\frame
{
  \frametitle{~}

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

\end{document}