\def\hs{\hspace{0.4 cm}} \documentclass{beamer} \usetheme{Warsaw} \usecolortheme{crane} \setbeamertemplate{footline}[page number] \beamertemplatenavigationsymbolsempty \title{Mimblewimble: Private, Massively-Prunable Blockchains} \author{Andrew Poelstra} \institute{\texttt{grindelwald@wpsoftware.net}} \date{October 8, 2016} \usepackage{amsfonts,amsmath,latexsym,color,epsfig,graphicx,multirow,rotating} \begin{document} \frame{ \maketitle } \frame { \frametitle{History} \begin{itemize} \item <1-> 04:30 UTC, August 2nd, 2016: ``Tom Elvis Jedusor'' posts a .onion link to a text file on IRC, titled MIMBLEWIMBLE and dated July 19. \item <2-> Next morning: myself and Bryan Bishop verify it's actually just text and rehost it. \item <3-> (Previous week: I had independently found a small part of Mimblewimble which was almost supported by Elements Alpha; starting from this I got the gist of the paper.) \item <4-> Following week: discussion on Reddit with Greg Sanders and others leads to understanding Mimblewimble's trust model, and hints that the new crypto has merit. \item <5-> September: myself and Avi Kulkarni develop an extension, ``sinking signatures'', to greatly improve its scaling properties. \item <6-> I am not Lord Voldemort. \end{itemize} } \frame { \frametitle{What is Mimblewimble?} \begin{itemize} \item <1-> Mimblewimble is a design for a blockchain-based ledger that is very different from Bitcoin. \item <2-> It can be implemented as a sidechain, or softforked into Bitcoin (with limitations). \item <3-> In Bitcoin transactions, old outputs sign new outputs; outputs have ``script pubkeys'' that are independent of each other. In Mimblewimble transactions, outputs have only EC pubkeys, and the difference between new outputs' keys and old ones' is multisigned by all transacting parties. \item <4-> Mimblewimble transactions are inherently scriptless. \end{itemize} } \frame { \frametitle{Mimblewimble Transactions} A Mimblewimble transaction is the following data: \begin{itemize} \item <1-> Inputs (references to old outputs). \item <2-> Outputs: confidential transaction outputs (group elements, which blind and commit to amounts), plus rangeproofs. \item <3-> Excess: difference between outputs and inputs (group element), plus signature (for authentication and to prove non-infaltion) \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 Transactions} \begin{center} \includegraphics[scale=0.09]{onetx/onetx-1.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 excess value(s) and 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{Trust Model: Transactions} A transaction is valid if: \begin{itemize} \item <1-> It is non-inflationary (total input amount equals total output amount) \item <2-> The owner of the input(s) has signed off on it. \item <3-> \includegraphics[scale=0.06]{tx-wide.png} \end{itemize} } \frame { \frametitle{Trust Model: Blockchain} It should be verifiable that \begin{itemize} \item <1-> A transaction, once committed to a block, cannot be reversed without doing enough work to rewrite the block (and all its descendants). \item <2-> The current state of all coins reflects zero net theft and inflation. \item <3-> \emph{The exact historical sequence of transactions does not need to be publicly verifable.} \item <4-> \includegraphics[scale=0.06]{tx-wide.png} \end{itemize} } \frame { \frametitle{Trust Model: Block Verification} It is possible to verify the blockchain with only the following data: \begin{itemize} \item <1-> Block headers \item <2-> Unspent outputs from each block \item <3-> Excess values and signatures. \item <4-> Rangeproofs for the above (witness data) \item <5-> Full blocks near the tip should be kept to handle reorgs \item <6-> In Bitcoin there are 150 million transactions and 40 million unsigned transaction outputs: 21.6Gb of historic data, 2Gb of UTXOs and 100Gb of UTXO rangeproofs. \end{itemize} } \frame { \frametitle{Sinking Signatures} Open problem 2 from the Voldemort paper: can we aggregate excess signatures? \begin{itemize} \item <1-> Difficult to do without also making them negatable in later blocks. (If you can add you can subtract.) \item <2-> We can by using pairings and (a variant of) Boneh-Lynn-Shacham signatures which sign \emph{the current block height}. \item <3-> Now only one excess and (multi-)signature per block. \item <4-> In Bitcoin there are 450000 blocks: so 22Mb of historic data (but 450k pairings to verify), 2Gb of UTXO and 100Gb of rangeproofs. \end{itemize} } \frame { \frametitle{Sinking Signatures} What if we could combine blocks as well? \begin{itemize} \item <1-> It is possible to compress a chain of blockheaders to logarithmic size while still having a proof that takes the same expected work as the original [Back et. al. 2014; Kiayias, Lamprou, Stouka 2016]. \item <2-> Treat the blockchain as a ``skiplist'' where blocks have distant parents. \item <3-> If excess values signed the \emph{current height} and \emph{previous heights}, the excesses and signatures can be combined for skipped blocks. \item <4-> This is a \emph{sinking signature}, which can be made log-sized. [Poelstra, Kulkarni 2016] \item <5-> Simulations show a 500000-block chain can likely be compressed to 300 blocks. We now have \emph{1Mb} of historic data (20 seconds on one core to verify), 2Gb of UTXO and 100Gb of rangeproofs. \end{itemize} } \frame { \frametitle{Trust Model: Blockchain verifitation, redox} \begin{itemize} \item <1-> Compact chains have same \emph{expected work} to produce but much higher variance than the original chain. \item <2-> With nontrivial probability a compact chain can be produced in less work than one block; thus compact chains prove no work. \item <3-> We thus distinguish between \emph{expected work} which affects economic incentives for forgeries, and \emph{proven work} which assures a verifier an historic fact about how a chain was produced. \item <4-> Mimblewimble verifiers should demand a month or two of non-compact blocks on top of a compact chain. This proves a month or two of work, but a forger expects to do as much work as the entire chain. So no ``incentive cliff'' and verifiers can also be assured that their chain was no accident. \end{itemize} } \frame { \frametitle{Next Steps} \begin{itemize} \item <1-> Development, development, development! \item <2-> Nail down chain parameters, in particular choice of pairing-friendly curve. \item <3-> Sidechain? \end{itemize} } \frame { \frametitle{Open Problems} \begin{itemize} \item <1-> Smaller rangeproofs? Aggregation of rangeproofs? \item <2-> Peer-to-peer protocol that can handle transaction merging \item <3-> Quantum resistance \end{itemize} } \frame { \frametitle{~} \begin{center} Thank You ~\\~\\ Andrew Poelstra \texttt{} \end{center} } \end{document}