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

\documentclass{beamer}

\usetheme{Warsaw}
\usecolortheme{beaver}
\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}
\usepackage{anyfontsize}

\begin{document}
\frame{ \frametitle{} \begin{center} \includegraphics[scale=0.12]{data/title-slide.png} \end{center} }

\frame
{
  \frametitle{Confidential Transactions}
  \begin{itemize}
  \item Confidential Transactions: replacing output amounts with \emph{Pedersen commitments}~\\~\\
  \item Publicly verifiable that transactions balance.~\\~\\
  \item Specific amounts are zero-knowledge.~\\~\\
  \item Amounts must be encoded as integers mod $q$, which can overflow. To prevent this we use
        a \emph{rangeproof}.
  \end{itemize}
}

\frame
{
  \frametitle{Rangeproofs from Ring Signatures}
  \begin{itemize}
  \item Idea: split numbers into 64 bits. Hide the bits with more Pedersen commitments.~\\~\\
  \item Prove these commitments are actually bits.~\\~\\
  \item Do this with a \emph{ring signature} on each bit commitment.~\\~\\
  \item Size: 80 bytes per bit. 5Kb for 64 bits.~\\~\\
  \item Verify time: 91$\mu$s per bit. 5.8ms for 64 bits.
  \end{itemize}
}

\frame
{
  \frametitle{Rangeproofs from Inner Products}
  \begin{itemize}
  \item Idea: hide all the bits in a single \emph{vector} Pedersen commitment.~\\~\\
  \item Prove each bit satisfies $x(x - 1) = 0$. And that they sum to $v$.~\\~\\
  \item Express these conditions as an inner product.~\\~\\
  \item Take an efficient inner product argument (Bootle 2016), simplify it, shrink
        its size, make it work with Pedersen commitments.
  \end{itemize}
}

\frame
{
  \frametitle{Bulletproofs: size}
  Size: logarithmic in the number of bits; can be aggregated.
  \begin{center} \includegraphics[scale=0.15]{data/bp-size.png} \end{center}
}

\frame
{
  \frametitle{Bulletproofs: size}
  Verify time: sublinear in the number of bits; can be batch verified
  \begin{center} \includegraphics[scale=0.15]{data/bp-validation-perf.png} \end{center}
}

\frame
{
  \frametitle{Arithmetic Circuits}
  \begin{itemize}
  \item Inner products can prove much more than just ranges.~\\~\\
  \item Any algorithm with known running time.~\\~\\
  \item As expressive as SNARKs, STARKs, ZKBoo, etc.~\\~\\
  \item Small proofs (couple kb), fast-ish verification, fast-ish proving
  \end{itemize}
}

\frame
{
  \frametitle{Hash Preimages}
  \begin{itemize}
  \item SHA-256 (512 bits): 21s to prove, 441ms to verify, 39ms to batch-verify~\\~\\
  \item Pedersen Hash (a la ZCash) (768 bits): 1.35s to prove, 72ms to verify, 5ms to batch-verify~\\~\\
  \item $\sim$ 2Kb for both these proofs
  \end{itemize}
}

\frame
{
  \frametitle{Applications}
  \begin{itemize}
  \item Rangeproofs, of course~\\~\\
  \item Merkle proofs~\\~\\
  \item Proof of solvency~\\~\\
  \item Multisig with deterministic nonces~\\~\\
  \item Scriptless Scripts (with ECDSA in some cases)~\\~\\
  \item Assets / smart contracts / crypto-derivatives
  \end{itemize}
}

\frame
{
  \frametitle{~}

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

\end{document}