\def\hs{\hspace{0.4 cm}} \documentclass{beamer} \usetheme{Berlin} \usecolortheme{wolverine} \setbeamertemplate{footline}[page number] \usefonttheme{structureitalicserif} \beamertemplatenavigationsymbolsempty \setbeamertemplate{footline}{ } \title{MimbleWimble, 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 } \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 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} } \subsection{Simple Scriptless Scripts} \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{moSt exSpressive 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} } \subsection{Simultaneous Scriptless Scripts} \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} } \subsection{Conclusion} \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 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{} \end{center} } \end{document}