PlonkSimonsCorrected.tex

\documentclass[shadesubsections,trans,14pt,mathserif]{beamer}
\usepackage[danish]{babel}	
%\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{\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{PLONK: Permutations over Lagrange-Bases for Oecumenical Noninteractive arguments of Knowledge}}    % Enter your title between curly braces
\author{\small{Ariel Gabizon}\\                 % Enter your name between curly braces
\tt{\footnotesize{Zeta Function Technologies}                                       } }      % 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}
\note{Talk for 30 minutes} % Add notes to yourself that will be displayed when
                           % 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}
\begin{frame}
\frametitle{Prelude: Trusted setups for pairing-based SNARKs}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 
  \begin{itemize}
  \item Want to prove statements about circuit satisfiability
\item Generate CRS of elements $g^{P(s)}$ for secret $s\in \F$ nobody knows, for some polynomials $P$ (potentially depending on circuit).
  \end{itemize}


\end{frame}

\begin{frame}
\frametitle{Prelude: Trusted setups for pairing-based SNARKs}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 
  \begin{itemize}
  \item Want to prove statements about circuit satisfiability
\item Generate CRS of elements $g^{P(s)}$ for secret $s\in \F$ nobody knows, for some polynomials $P$ (potentially depending on circuit).
\item If CRS only contains elements $g^{s^i}$ setup is \textbf{universal and updatable}.

\end{itemize}


\end{frame}





\begin{frame}
\frametitle{Plonk in two sips}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 
  \begin{enumerate}
%\item The protocol definition includes a set of \emph{preprocessed polynomials} $g_1,\ldots,g_\ell \in \polysofdeg{d}$.

\item All you need is a permutation check.\pause 
 \item Permutations are easier to check on mutliplicative subgroups
\end{enumerate}


\end{frame}


\begin{frame}
\large{Part 1: All you need is a permutation check}\\
 \vspace{0.2in}
\normalsize{\textbf{Our setting:} want short proofs about fan-in 2 unlimited fan-out circuits, trusted setup is updatable depends only on circuit size.}
\end{frame}




\begin{frame}
\textbf{example:} Prove knowledge of $a,b,c$ with
 
 
 
 
 
\[(a+b)\cdot c =7\]




\end{frame}


\begin{frame}
Left values: 
$l_1,l_2$\\
Right values: $r_1,r_2$\\
Output values:
$o_1,o_2$


 \vspace{0.2in}

\end{frame}

\begin{frame}
Left values: 
$l_1,l_2$\\
Right values: $r_1,r_2$\\
Output values:
$o_1,o_2$


 \vspace{0.2in}

Gate checks:
 $l_1 + r_1 = o_1 , l_2\cdot r_2 = o_2$


Wire/copy checks:
$o_1 = l_2$

Public input checks: $o_2=7$.
\end{frame}
\begin{frame}
   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\


Left values: 
$l_1,l_2$\\
Right values: $r_1,r_2$\\
Output values:
$o_1,o_2$


 \vspace{0.2in}

Gate checks:
 $l_1 + r_1 = o_1 , l_2\cdot r_2 = o_2$\;\;\textbf{\small{(easy)}}


Wire/copy checks:
$o_1 = l_2$\;\;\textbf{\small{(hard)}}

Public input checks: $o_2=7$ \textbf{\small{(easy)}}
\end{frame}


\begin{frame}
\frametitle{Copy checks with permutations\\ \normalsize{similar to [Groth09,BCGGHJ17]}}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 
 
 \[V= (l_1,l_2,r_1,r_2,o_1,o_2)\]
 
 

\end{frame}


\begin{frame}
\frametitle{Copy checks with permutations\\ \normalsize{similar to [Groth09,BCGGHJ17]}}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 
 
 \[V= (l_1,l_2,r_1,r_2,o_1,o_2)\]
 
 $o_1=l_2$ iff $V=\sigma(V)$ \\
 For permutation $\sigma = (25)$
 
 

\end{frame}





\begin{frame}
\large{Part 2: Permutations are easier to check on mutliplicative subgroups
}

\end{frame}

\begin{frame}
\frametitle{{\normalsize{[Bayer-Groth12]}} - perm checks with products}   % Insert frame title between curly braces
%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) = (a_3,a_1,a_2)$ \\


\end{frame}


\begin{frame}
\frametitle{{\normalsize{[Bayer-Groth12]}} - perm checks with products}   % Insert frame title between curly braces
%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) = (a_3,a_1,a_2)$ \\
 \vspace{0.2in}

\textbf{step 1:} Choose random $\beta\in \F$. Let
 \[a'_1 = a_1 + \beta, a'_2 = a_2 + 2\beta, a'_3 = a_3 + 3\beta\]
 \[b'_1 = b_1 + 3\beta, b'_2 = b_2 + \beta, b'_3 = b_3 + 2\beta\]

 
 \vspace{0.2in}


\end{frame}
\begin{frame}
\frametitle{{\normalsize{[Bayer-Groth12]}} - perm checks with products}   % Insert frame title between curly braces
%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) = (a_3,a_1,a_2)$ \\
 \vspace{0.2in}

\textbf{step 1:} Choose random $\beta\in \F$. Let
 \[a'_1 = a_1 + \beta, a'_2 = a_2 + 2\beta, a'_3 = a_3 + 3\beta\]
 \[b'_1 = b_1 + 3\beta, b'_2 = b_2 + \beta, b'_3 = b_3 + 2\beta\]

 
 \vspace{0.2in}

If claim false - w.h.p as mutliset $\set{a'_1,a'_2,a'_3}\neq \set{b'_1,b'_2,b'_3}$:

\end{frame}


\begin{frame}
\frametitle{{\normalsize{[Bayer-Groth12]}} - reducing permutation checks to products}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\

\textbf{step 2:} Choose random $\gamma\in \F$. Let
 \[a''_i=a'_i +\gamma, b''_i = b_i + \gamma\]
 
 
 \vspace{0.2in}


\end{frame}
\begin{frame}
\frametitle{{\normalsize{[Bayer-Groth12]}} - reducing permutation checks to products}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\

\textbf{step 2:} Choose random $\gamma\in \F$. Let
 \[a''_i=a'_i +\gamma, b''_i = b'_i + \gamma\]
 
 
 \vspace{0.2in}

If $\set{a'_1,a'_2,a'_3}\neq \set{b'_1,b'_2,b'_3}$ as multiset - w.h.p  \[a''_1\cdot a''_2\cdot a''_3 \neq b''_1\cdot b''_2\cdot b''_3.\]  

\end{frame}

% \begin{frame}
% \textbf{Feel life is too short to constantly cite the Schwartz-Zippel Lemma?}
% \end{frame}
% 

\begin{frame}
\frametitle{Idealized Polynomials Protocols}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 
 \textbf{Preprocessing:} $\ver$ chooses polynomials $g_1,\ldots,g_t\in \polysofdeg{d}$.\\
 \vspace{0.4in}
\textbf{Protocol:}
  \begin{enumerate}
%\item The protocol definition includes a set of \emph{preprocessed polynomials} $g_1,\ldots,g_\ell \in \polysofdeg{d}$.

\item 
$\prv$'s  msgs are to ideal party $\ideal$. Must be $f_i\in \polysofdeg{d}$.
 \item At protocol end $\ver$ asks $\ideal$ if some identities hold between $\set{f_1,\ldots,f_\ell,g_1,\ldots,g_t}$.  Outputs $\acc$ iff they do.
\end{enumerate}
\end{frame}
\begin{frame}
\frametitle{Idealized Polynomials Protocols}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 
 \textbf{Preprocessing:} $\ver$ chooses polynomials $g_1,\ldots,g_t\in \polysofdeg{d}$.\\
 \vspace{0.2in}
\textbf{Protocol:}
 
 \begin{enumerate}
%\item The protocol definition includes a set of \emph{preprocessed polynomials} $g_1,\ldots,g_\ell \in \polysofdeg{d}$.

\item $\prv$'s  msgs are to ideal party $\ideal$. Must be $f_i\in \polysofdeg{d}$.
\item At end, $\ver$ asks $\ideal$ if some identities hold between $\set{f_1,\ldots,f_\ell,g_1,\ldots,g_t}$.  


\end{enumerate}
\emph{Using [KZG10], can compile to real protocol with each msg of $\prv$ being 32-64 bytes according to your NFSPL.} 

\end{frame}


% \begin{frame}
% \textbf{Feel life is too short to constantly cite the fundamental thm of Algebra?}
% \end{frame}

\begin{frame}
\frametitle{$H$-ranged Polynomials Protocols}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 
 \textbf{Preprocessing:} $\ver$ chooses polynomials $g_1,\ldots,g_t\in \polysofdeg{d}$, $H\subset\F$.\\
 \vspace{0.4in}
\textbf{Protocol:}
 
 \begin{enumerate}
%\item The protocol definition includes a set of \emph{preprocessed polynomials} $g_1,\ldots,g_\ell \in \polysofdeg{d}$.

\item $\prv$'s  msgs are to ideal party $\ideal$. Must be $f_i\in \polysofdeg{d}$.
\item At end, $\ver$ asks $\ideal$ if some identities hold between $\set{f_1,\ldots,f_\ell,g_1,\ldots,g_t}$   \textbf{\textit{on $H$}}. 

\end{enumerate}
\end{frame}


\begin{frame}
\frametitle{$H$-ranged protocol using polynomial protocol:}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 
 
 $\ver$ wants to check identities $P_1,P_2$ on $H$.\\
 \vspace{0.2in}
\begin{itemize}
\item  After $\prv$ finished sending \set{f_i}, $\ver$ sends random $a_1,a_2\in \F$.\\
\item $\prv$ sends  $T\in \polysofdeg{d}$.\\
\item $\ver$ checks identity
$a_1\cdot P_1 + a_2\cdot P_2 \equiv T\cdot Z_H$.
\end{itemize}


\end{frame}



\begin{frame}
\frametitle{Checking permutations with $H$-ranged protocols}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 Permutation $\sigma: [n]\to [n]$.
 $H=\set{\gen,\gen^2,\ldots,\gen^n}$.\\
 \vspace{0.2in}
 
 $\prv$ has sent $f\in \polysofdeg{d}$.\\
 \vspace{0.2in}
 Wants to prove $f=\sigma(f)$:
 \[\forall i\in [n], f(\gen^i) = f(\gen^{\sigma(i)})\]

 

\end{frame}
\begin{frame}
\frametitle{Using [BG12] reduces to:}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 $H=\set{\gen,\gen^2,\ldots,\gen^n}$.\\
 \vspace{0.2in}
 
 $\prv$ has sent $f,g\in \polysofdeg{d}$.\\
 \vspace{0.2in}
 Wants to prove:
 \[\prod_{i\in [n]}  f(\gen^i) = \prod_{i\in [n]} g(\gen^i)\]

 

\end{frame}




\begin{frame}
\frametitle{Checking products with $H$-ranged protocols}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 \begin{enumerate}
  \item $\prv$ computes $Z$ with 
  $ Z(\gen)=1, Z(\gen^i) = \prod_{j<i}  f(\gen^j)/g(\gen^j)$, {\small{$i=2..n+1$}}.
  \item Sends $Z$ to $\ideal$.

 \end{enumerate}


\end{frame}

\begin{frame}
\frametitle{Checking products with $H$-ranged protocols}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 \begin{enumerate}
  \item $\prv$ computes $Z$ with 
  $ Z(\gen)=1, Z(\gen^i) = \prod_{j<i}  f(\gen^j)/g(\gen^j)$.
  \item Sends $Z$ to $\ideal$.
  \item $\ver$ checks following identities on $H$.
  \begin{enumerate}
   \item $L_1(X) (Z(X)-1) =0$
   \item $Z(X) f(X) = Z(\gen\cdot X)g(X)$
 \item $L_n(X) (Z(\gen\cdot X) -1)=0$ 
 \end{enumerate}

 \end{enumerate}


\end{frame}




\begin{frame}
\frametitle{The bottom line {\normalsize{(on BLS-381 curve)}}}   % Insert frame title between curly braces
%Since the beginning of time (LFKN, 1989) humanity has been trying to verify prover polynomial evaluations.\\
 600 byte proofs with one trusted setup for all fan-in two circuits of $n$ gates.\\
  \vspace{0.2in}
Prover does $11n$ $G_1$ exp {\small{(or $9n$ $G_1$ exp with 700 byte proof)}}.\\
  \vspace{0.2in}
For batch of proofs on same circuit only $3n$ $G_1$ exp and $240$ bytes for each additional proof.
 

\end{frame}


\begin{frame}
\large{Bonus material: The KZG polynomial commitment scheme
}

\end{frame}

\begin{frame}
 SRS: \enc{1},\enc{x},\ldots,\enc{x^d}, for random $x\in \F$.\\
 \vspace{0.4in}
 $f(X) = \sum_{i=0}^d a_i X^i$\\
 \vspace{0.4in}
 $\cm(f)\defeq  \sum_{i=0}^d a_i \enc{x^i}=  \enc{f(x)}$\\
 \vspace{0.4in}
 
\end{frame}
\begin{frame}
 SRS: \enc{1},\enc{x},\ldots,\enc{x^d},\\
 for random $x\in \F$.
 \vspace{0.4in}
 
 $\cm(f)\defeq   \enc{f(x)}$\\
 \vspace{0.4in}
$\open{f,i}\defeq \enc{h(x)}$, where
$h(X)\defeq \frac{f(X)-f(i)}{X-i}$
 \vspace{0.4in}
 
\end{frame}

% 
% \begin{frame}
%  $\cm(f)\defeq   \enc{f(x)}$\\
%  \vspace{0.4in}
% $\open{f,i}\defeq \enc{h(x)}$, where
%  $h(X)\defeq \frac{f(X)-f(i)}{X-i}$\\
%  \vspace{0.4in}
% \textbf{exercise} - using pairing, define:\\
%  \vspace{0.2in}
%  $\verify{\cm,\pi,z,i}$,
%  where $z$ is allegedly $f(i)$
%  \end{frame}




\begin{frame}

 $\cm(f)\defeq   \enc{f(x)}$\\
 \vspace{0.4in}
$\open{f,i}\defeq \enc{h(x)}$, where
 $h(X)\defeq \frac{f(X)-f(i)}{X-i}$\\
 \vspace{0.4in}
 $\verify{\cm,\pi,z,i}:$
\[e(\cm-\enc{z},\enc{1}) \stackrel{?}{=} e(\pi, \enc{x-i})\]
\end{frame}


 


\begin{frame}

 $\cm(f)\defeq   \enc{f(x)}$\\
 \vspace{0.4in}
$\open{f,i}\defeq \enc{h(x)}$, where
 $h(X)\defeq \frac{f(X)-f(i)}{X-i}$\\
 \vspace{0.4in}
 $\verify{\cm,\pi,z,i}:$
\[e(\cm-\enc{z},\enc{1}) \stackrel{?}{=} e(\pi, \enc{x-i})\]
 \vspace{0.4in}
\textbf{Thm}{\footnotesize{[KZG,MBKM]}}: \emph{This works in the Algebraic Group Model.}
 \end{frame}


\end{document}