plookupzksummit2020.tex

\documentclass[shadesubsections,compress,14pt,mathserif]{beamer}
\usepackage[danish]{babel}	
\usepackage{tikz}
\usetikzlibrary{shapes, positioning}
\usenavigationsymbolstemplate{}
\usepackage{pgfplots}
\usepackage[absolute,overlay]{textpos}

%\usepackage[T1]{fontenc}
%\usepackage{fourier}
% Dokumentets sprog
%\usepackage{mathtools}
%\usepackage{pxfonts}
\usepackage{eulervm}
% Class options include: notes, notesonly, handout, trans,
%                        hidesubsections, shadesubsections,
%                        inrow, blue, red, grey, brown

% Theme for beamer presentation.
%\usepackage{beamertheme} 
% Other themes include: beamerthemebars, beamerthemelined, 
%                       beamerthemetree, beamerthemetreebars  
\newcommand{\adv}{\ensuremath{\mathcal A}}
\newcommand{\xor}{\ensuremath{\oplus}}
\newcommand{\plonk}{\ensuremath{\mathcal{P} \mathfrak{lon}\mathcal{K}}}
\newcommand{\F}{\ensuremath{\mathbb F}}
\newcommand{\set}[1]{\ensuremath{\left\{#1\right\}}}
\newcommand{\sett}[2]{\ensuremath{\left\{#1\right\}_{#2}}}
\newcommand{\enc}[1]{\ensuremath{\left[#1\right ]}}
\newcommand{\cm}{\ensuremath{\mathsf{cm}}}
\newcommand{\open}[1]{\ensuremath{\mathsf{open}(#1)}}
\newcommand{\verify}[1]{\ensuremath{\mathsf{verify}(#1)}}
\newcommand{\defeq}{\ensuremath{:=}}
\newcommand{\helper}{\ensuremath{\mathcal{H}}}
\newcommand{\ver}{\ensuremath{\mathcal{V}}}
\newcommand{\prv}{\ensuremath{\mathcal{P}}}
 \newcommand{\polysofdeg}[1]{\F_{< #1}[X]}
 \newcommand{\polys}{\F[X]}
\newcommand{\acc}{{\mathbf{acc}}}
\newcommand{\ideal}{\mathbf{I}}
\newcommand{\gen}{\alpha}

%\setbeamersize{text margin left=3mm,text margin right=3mm} 
\title{\large{plookup: speeding up SNARKs on non-friendly functions with lookup tables}}    % Enter your title between curly braces
\author{\small{Ariel Gabizon  \; Zachary J. Williamson}\\                 % Enter your name between curly braces
\tt{\footnotesize{\;\;\;\;\;\; \textbf{Aztec}   \;\;\;\;\;\;\;\;\;\;\;\; }                                       } }      % Enter your institute name between curly braces
\date{}                    % Enter the date or \today between curly braces
%\usefonttheme{professionalfonts}
%\usefonttheme[onlymath]{serif}
\begin{document}
\boldmath
% Creates title page of slide show using above information
\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
\frametitle{SNARKs are easy prey in a  world full of nasty binary functions}
$a,b,c\in \F$
  \vspace{0.2in}

Want to show $c = a\;\; \xor\;\; b $ as 8-bit strings\pause
  \vspace{0.2in}

Standard way requires 25-32 constraints: Give bit decomposition of $a,b,c$, check bitwise xor.
\end{frame}


\begin{frame}

Want to show $c = a\;\; \xor\;\; b $ as 8-bit strings.
  \vspace{0.2in}

Standard way requires 25-32 constraints: Give bit decomposition of $a,b,c$, check bitwise xor.\\
  \vspace{0.2in}
\emph{This is a \textbf{multiplicative} factor you pay on each small operation while computing SHA/BLAKE}

\end{frame}




\begin{frame}
 \frametitle{Approach 1: Keep SNARKs in friendly neighborhoods}
 
  
  
\begin{tikzpicture}[ball/.style={circle, minimum width=5cm, minimum height=5cm, draw}]
Blake




% \node[ball] (gate1) {+};
% \node[ball, above right=1.25cm of gate1] (gate2) {$\times$};
\node[ball] (text1){ MIMC \linebreak Poseidon \linebreak Rescue   
};
\node[right=2cm of text1] (text2) {Blake};

% \node[ below=3cm of input1] (input3) {no trusted setup};   
% \node[ right=0.1cm of input3] (text3) {\footnotesize{(STARKs, bulletproofs,DARKs,Redshift)}};   

% \draw[->] (input1) -- (input3);
% \node[above = 0.2cm of text1] (pic1){

%   \node[anchor=south west,inner sep=0cm] at ($(current page.south west)$) {
%      \includegraphics[width=80]{nicehouse.jpg}
%   };
\end{tikzpicture}
  
  
  SHA                            
  
  
\end{frame}

\begin{frame}
 \frametitle{Our Approach: lookup tables {\normalsize (see also: Arya{\footnotesize [Bootle, Cerulli, Groth, Jakobsen, Maller]})}}
 
 
 Precompute table $T$ of all triplets $(a,b,c)$
  
  s.t. $c=a\;\;\xor\;\;b$.\pause
  
    \vspace{0.2in}

Instead of representing
$\xor$ logic, check that $(a,b,c)\in T$\pause
    \vspace{0.2in}
  
After enough lookups, has amortized cost of $\sim 1$ constraint per $\xor$.

    
\end{frame}



\begin{frame}
 \center{The plookup protocol in a nutshell}    
 
 \center{\emph{\footnotesize (a simpler protocol we came up with while preparing the slides)}}
\end{frame}

 
\begin{frame}
\frametitle{Basic tool: The multiset check}
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
\textbf{example:} Given $a,b\in \F^3$, want to check $\{b_1,b_2,b_3\} \stackrel{?}{=} \{a_1,a_2,a_3\}$ \\ \pause
 \vspace{0.2in}

  
 Choose random $\gamma\in \F$. Check
  \[(a_1 + \gamma)(a_2+ \gamma)(a_3 + \gamma) \stackrel{?}{=} (b_1+\gamma)(b_2+\gamma)(b_3+\gamma)\]\pause
%   \[a'_1 = a_1 + \gamma, a'_2 = a_2 + \gamma, a'_3 = a_3 + \gamma\]
%  \[b'_1 = b_1 + \gamma, b'_2 = b_2 + \gamma, b'_3 = b_3 + \gamma\]\pause

 \vspace{0.2in}
 If $a,b$ different as sets then w.h.p products different.\pause
 
  \vspace{0.2in}

 \plonk's grand product implements this super efficiently
\end{frame}



\begin{frame}
Witness $f=\sett{f_i}{i\in [n]}$
Table $t=\sett{t_i}{i\in [d]}$

Want to prove $f\subset t$.
{\small (using randomness we can reduce tuples to single elements)}.
\end{frame}


\begin{frame}

Witness $f=\set{3,1,1}$
Table $t=\set{1,3,4}$

\begin{enumerate}
 \item Prover commits to $s\defeq$ \emph{sorted} version of $f\cup t$. $s\defeq (1,1,1,3,3,4)$  \pause
 \item Prover shows $s=f\cup t$. \pause
 \item Look at difference multiset of $s$ $s'\defeq \set{0,0,2,0,1}$, and difference multiset of $t$ $t'\defeq \set{2,1}$\pause
 \item Prover shows $s'=t'\cup \set{0,0,0}$.
\end{enumerate}

\end{frame}
% 
% \begin{frame}
%  Arya approach
%  
%  \[F=\prod_{i\in [n]}(X-f_i), T=\prod_{i\in [d] (X-t_i)\]
% \end{frame}
% 




% \begin{frame}
%  For security, SNARKs require a setup phase.\\ \linebreak
%   \vspace{0.2in}
%  \includegraphics[width=300, valign=m]{zcashsetup.png}
%  
% \end{frame}




                           % typeset with the notes or notesonly class options

%\section[Outline]{}

% Creates table of contents slide incorporating
% all \section and \subsection commands
%\begin{frame}
  %\tableofcontents
%\end{frame}
\end{document}