ujtalksKZG+PLONK.tex

% !tex encoding = utf-8 unicode

% this is a simple template for a latex document using the "article" class.
% see "book", "report", "letter" for other types of document.

\documentclass[11pt]{article} % use larger type; default would be 10pt



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% packages
\usepackage[
    type={CC},
    modifier={by-nc-sa},
    version={3.0},
]{doclicense}

\usepackage[utf8]{inputenc} % set input encoding (not needed with xelatex)
\usepackage[strict]{changepage}
    
    %%% examples of article customizations
    % these packages are optional, depending whether you want the features they provide.
    % see the latex companion or other references for full information.
    
    
    %%% page dimensions
\usepackage{geometry} % to change the page dimensions
\geometry{a4paper} % or letterpaper (us) or a5paper or....
    % \geometry{margin=2in} % for example, change the margins to 2 inches all round
    % \geometry{landscape} % set up the page for landscape
    %   read geometry.pdf for detailed page layout information
 \usepackage{numdef}
   
\usepackage{graphicx} % support the \includegraphics command and options
    % some of the article customisations are relevant for this class
\usepackage{amsmath,amsthm}
\usepackage{amsfonts} % math fonts such as \mathbb{}
\usepackage{amssymb} % \therefore
% \usepackage{bickham}
\usepackage{hyperref}
\usepackage{cryptocode}
\usepackage{framed} 
    % \usepackage[parfill]{parskip} % activate to begin paragraphs with an empty line rather than an indent
    
    %%% packages
\usepackage{booktabs} % for much better looking tables
\usepackage{array} % for better arrays (eg matrices) in maths
\usepackage{paralist} % very flexible & customisable lists (eg. Enumerate/itemize, etc.)
\usepackage{verbatim} % adds environment for commenting out blocks of text & for better verbatim
\usepackage{subfig} % make it possible to include more than one captioned figure/table in a single float
    % % these packages are all incorporated in the memoir class to one degree or another...
\usepackage{mathrsfs}
\usepackage{booktabs}
\usepackage{makecell}
\usepackage{adjustbox}

\usepackage{pgfplots}

\renewcommand\theadalign{bc}
\renewcommand\theadfont{\bfseries}
\renewcommand\theadgape{\Gape[4pt]}
  
    %%% headers & footers
\usepackage{fancyhdr} % this should be set after setting up the page geometry
\pagestyle{fancy} % options: empty , plain , fancy
\renewcommand{\headrulewidth}{0pt} % customise the layout...
\lhead{}\chead{}\rhead{}
\lfoot{}\cfoot{\thepage}\rfoot{}
    
    
    %%% section title appearance
\usepackage{sectsty}
\allsectionsfont{\sffamily\mdseries\upshape} % (see the fntguide.pdf for font help)
    % (this matches context defaults)
    
    %%% toc (table of contents) appearance
\usepackage[nottoc,notlof,notlot]{tocbibind} % put the bibliography in the toc
\usepackage[titles,subfigure]{tocloft} % alter the style of the table of contents
\renewcommand{\cftsecfont}{\rmfamily\mdseries\upshape}
\renewcommand{\cftsecpagefont}{\rmfamily\mdseries\upshape} % no bold!

 %%% end article customizations
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 % macros
 \newcommand{\code}[1]{\texttt{#1}}
\newcommand\tstrut{\rule{0pt}{2.6ex}}         % = `top' strut
\newcommand\bstrut{\rule[-0.9ex]{0pt}{0pt}}   % = `bottom' strut
\newcommand{\bgamma}{\boldsymbol{\gamma}}
\newcommand{\bsigma}{\boldsymbol{\sigma}}
\newcommand{\plonk}{\ensuremath{\mathcal{P} \mathfrak{lon}\mathcal{K}}\xspace}
\newcommand{\caulkpp}{\ensuremath{\mathsf{\mathrel{Caulk}\mathrel{\scriptstyle{++}}}}\xspace}
\newcommand{\flookup}{\ensuremath{\mathsf{\mathpgoth{Flookup}}}\xspace}
\newcommand{\caulkp}{\ensuremath{\mathsf{\mathrel{Caulk}\mathrel{\scriptstyle{+}}}}\xspace}
\newcommand{\caulk}{\ensuremath{\mathsf{Caulk}}\xspace}
\newcommand{\plookup}{\ensuremath{\mathpgoth{plookup}}\xspace}
\newcommand{\tablegroup}{\ensuremath{\mathbb{H}}\xspace}
\newcommand{\V}{\ensuremath{\mathbf{V} }\xspace}



% \newcommand{\plonk}{\ensuremath{\mathtt{PLONK}}\xspace}
\newcommand{\papertitle}{UJ crypto course: the KZG PCS scheme and PlonK SNARK}
%\newcommand{\authorname}}
\newcommand{\company}{}
\title{ \bf \papertitle \\[0.72cm]}
\author{ Ariel Gabizon \\ \tt{Zeta Function Technologies}  } 
% 
% 	\large{\authorname} \\[0.5cm] \large{\company}
% 	\\ {DRAFT}
%}
%\date{} % activate to display a given date or no date (if empty),

% otherwise the current date is printed 
\DeclareMathAlphabet{\mathpgoth}{OT1}{pgoth}{m}{n}	
\ProvidesPackage{numdef}



%% Ariel Macros:
% \num\newcommand{\G1}{\ensuremath{{\mathbb G}_1}\xspace}
\newcommand{\Gi}{\ensuremath{{\mathbb G}_i}\xspace}
%\newcommand{\G}{\ensuremath{{\mathbb G}}\xspace}
\newcommand{\Gstar}{\ensuremath{{\mathbb G}^*}\xspace}
\newcommand{\x}{\ensuremath{\mathbf{x}}\xspace}
\newcommand{\z}{\ensuremath{\mathbf{z}}\xspace}
\newcommand{\X}{\ensuremath{\mathbf{X}}\xspace}

\newcommand{\G}{\ensuremath{{\mathbb G}}\xspace}
% \num\newcommand{\G2}{\ensuremath{{\mathbb G}_2}\xspace}
%\num\newcommand{\G11}{\ensuremath{\G1\setminus \set{0} }\xspace}
%\num\newcommand{\G21}{\ensuremath{\G2\setminus \set{0} }\xspace}
\newcommand{\grouppair}{\ensuremath{G^*}\xspace}
\newcommand{\prvperm}{\ensuremath{\mathrm{P_{\mathsf{\sigma}}}}\xspace}
\newcommand{\verperm}{\ensuremath{\mathrm{V_{\mathsf{\sigma}}}}\xspace}
\newcommand{\alg}{\ensuremath{\mathscr{A}}\xspace}

\newcommand{\Gt}{\ensuremath{{\mathbb G}_t}\xspace}
\newcommand{\F}{\ensuremath{\mathbb F}\xspace}
\newcommand{\Fstar}{\ensuremath{\mathbb F^*}\xspace}

\newcommand{\help}[1]{$#1$-helper\xspace}
\newcommand{\randompair}[1]{\ensuremath{\mathsf{randomPair}(#1)}\xspace}
\newcommand{\pair}[1]{$#1$-pair\xspace}
\newcommand{\pairs}[1]{$#1$-pairs\xspace}
\newcommand{\chalpoint}{\ensuremath{\mathfrak{z}}\xspace}

\newcommand{\pairone}[1]{\G1-$#1$-pair\xspace}
\newcommand{\pairtwo}[1]{\G2-$#1$-pair\xspace}
\newcommand{\sameratio}[2]{\ensuremath{\mathsf{SameRatio}(#1,#2)}\xspace}
\newcommand{\vecc}[2]{\ensuremath{(#1)_{#2}}\xspace}
\newcommand{\players}{\ensuremath{[n]}\xspace}
\newcommand{\adv}{\ensuremath{\mathcal A}\xspace}
\newcommand{\advprime}{\ensuremath{{\mathcal A}'}\xspace}
\newcommand{\extprime}{\ensuremath{E'}\xspace}
\newcommand{\advrand}{\ensuremath{\mathsf{rand}_{\adv}}\xspace}
% \num\newcommand{\srs1}{\ensuremath{\mathsf{srs_1}}\xspace}
% \num\newcommand{\srs2}{\ensuremath{\mathsf{srs_2}}\xspace}
% \num\newcommand{\srs0}{\ensuremath{\mathsf{srs}}\xspace}
\newcommand{\srs}{\ensuremath{\mathsf{srs}}\xspace}
\newcommand{\kzgsrs}[1]{\ensuremath{\enc{1},\enc{x},\ldots,\enc{x^{#1}}}\xspace}
\newcommand{\srsi}{\ensuremath{\mathsf{srs_i}}\xspace}
\newcommand{\com}[1]{\ensuremath{\mathsf{com(#1)}}\xspace}
\newcommand{\setup}{\ensuremath{\mathsf{setup}}\xspace}
\newcommand{\comperm}{\ensuremath{\mathsf{com_{\sigma}}}\xspace}
\newcommand{\cm}{\ensuremath{\mathsf{cm}}\xspace}
\newcommand{\cmsig}{\ensuremath{\mathsf{cm_\sigma}}\xspace}
\newcommand{\open}{\ensuremath{\mathsf{open}}\xspace}
\newcommand{\openperm}{\ensuremath{\mathsf{open_{\sigma}}}\xspace}
\newcommand{\sigof}[1]{\ensuremath{\sigma(#1)}\xspace}
\newcommand{\proverexp}{\ensuremath{\mathsf{e}}\xspace}
\newcommand{\reducedelems}{\ensuremath{\mathsf{r}}\xspace}

\newcommand{\ci}{\ensuremath{\mathrm{CI}}\xspace}
\renewcommand{\deg}{\ensuremath{\mathrm{deg}}\xspace}
\newcommand{\pairvec}[1]{$#1$-vector\xspace}
\newcommand{\Fq}{\ensuremath{\mathbb{F}_q}\xspace}
\newcommand{\randpair}[1]{\ensuremath{\mathsf{rp}_{#1}}\xspace}
\newcommand{\randpairone}[1]{\ensuremath{\mathsf{rp}_{#1}^{1}}\xspace}
\newcommand{\abase}{\ensuremath{A_{\mathrm{\mathbf{0}}}}\xspace}
\newcommand{\bbase}{\ensuremath{B_{\mathrm{\mathbf{0}}}}\xspace}
\newcommand{\cbase}{\ensuremath{C_{\mathrm{\mathbf{0}}}}\xspace}
\newcommand{\bliop}[1]{\ensuremath{\mathsf{#1{\text{-}}{BLIOP}}}\xspace}
\newcommand{\blop}{\ensuremath{\mathsf{\mathscr{BL} {\text{-}}IOP}}\xspace}
\newcommand{\openprotinput}{\ensuremath{\mathcal{O}}\xspace}
\newcommand{\amid}{\ensuremath{A_{\mathrm{mid}}}\xspace}
\newcommand{\bmid}{\ensuremath{B_{\mathrm{mid}}}\xspace}
\newcommand{\cmid}{\ensuremath{C_{\mathrm{mid}}}\xspace}

\newcommand{\negl}{\ensuremath{\mathsf{negl}(\lambda)}\xspace}
\newcommand{\randpairtwo}[1]{\ensuremath{\mathsf{rp_{#1}^2}}\xspace}%the randpair in G2
\newcommand{\nilp}{\ensuremath{\mathscr N}\xspace}
\newcommand{\groupgen}{\ensuremath{\mathscr G}\xspace}
\newcommand{\qap}{\ensuremath{\mathscr Q}\xspace}
\newcommand{\polprot}[4]{$(#1,#2,#3,#4)$-polynomial protocol}
\newcommand{\rangedprot}[5]{$#5$-ranged $(#1,#2,#3,#4)$-polynomial protocol}

\newcommand{\rej}{\ensuremath{\mathsf{rej}}\xspace}
\newcommand{\acc}{\ensuremath{\mathsf{acc}}\xspace}
\newcommand{\res}{\ensuremath{\mathsf{res}}\xspace}
\newcommand{\sha}[1]{\ensuremath{\mathsf{COMMIT}(#1)}\xspace}
 \newcommand{\shaa}{\ensuremath{\mathsf{COMMIT}}\xspace}
 \newcommand{\comm}[1]{\ensuremath{\mathsf{comm}_{#1}}\xspace}
 \newcommand{\defeq}{:=}

\newcommand{\B}{\ensuremath{\vec{B}}\xspace}
\newcommand{\dom}{\ensuremath{H}\xspace}
\newcommand{\C}{\ensuremath{\vec{C}}\xspace}
\newcommand{\Btwo}{\ensuremath{\vec{B_2}}\xspace}
\newcommand{\treevecsimp}{\ensuremath{(\tau,\rho_A,\rho_A \rho_B,\rho_A\alpha_A,\rho_A\rho_B\alpha_B, \rho_A\rho_B\alpha_C,\beta,\beta\gamma)}\xspace}% The sets of elements used in simplifed relation tree in main text body
\newcommand{\rcptc}{random-coefficient subprotocol\xspace}
\newcommand{\rcptcparams}[2]{\ensuremath{\mathrm{RCPC}(#1,#2)}\xspace}
\newcommand{\verifyrcptcparams}[2]{\ensuremath{\mathrm{\mathsf{verify}RCPC}(#1,#2)}\xspace}
\newcommand{\randadv}{\ensuremath{\mathsf{rand}_{\adv}}\xspace}
 \num\newcommand{\ex1}[1]{\ensuremath{ #1\cdot g_1}\xspace}
 \num\newcommand{\ex2}[1]{\ensuremath{#1\cdot g_2}\xspace}
 \newcommand{\pr}{\mathrm{Pr}}
 \newcommand{\powervec}[2]{\ensuremath{(1,#1,#1^{2},\ldots,#1^{#2})}\xspace}
 \newcommand{\partition}{\ensuremath{{\mathcal T}}\xspace}
 \newcommand{\partof}[1]{\ensuremath{{\partition_{#1}}}\xspace}
\num\newcommand{\out1}[1]{\ensuremath{\ex1{\powervec{#1}{d}}}\xspace}
\num\newcommand{\out2}[1]{\ensuremath{\ex2{\powervec{#1}{d}}}\xspace}
 \newcommand{\nizk}[2]{\ensuremath{\mathrm{NIZK}(#1,#2)}\xspace}% #2 is the hash concatenation input
 \newcommand{\verifynizk}[3]{\ensuremath{\mathrm{VERIFY\mhyphen NIZK}(#1,#2,#3)}\xspace}
\newcommand{\protver}{protocol verifier\xspace} 
\newcommand{\hash}{\ensuremath{\mathcal{H}}\xspace} 
\newcommand{\mulgroup}{\ensuremath{\F^*}\xspace}
\newcommand{\lag}[1]{\ensuremath{L_{#1}}\xspace} 
\newcommand{\sett}[2]{\ensuremath{\set{#1}_{#2}}\xspace}
\newcommand{\omegaprod}{\ensuremath{\alpha_{\omega}}\xspace}
\newcommand{\lagvec}[1]{\ensuremath{\mathrm{LAG}_{#1}}\xspace}
\newcommand{\trapdoor}{\ensuremath{r}}
\newcommand{\trapdoorext}{\ensuremath{r_{\mathrm{ext}}}\xspace}
\newcommand{\trapdoorsim}{\ensuremath{r_{\mathrm{sim}}}\xspace}
\renewcommand{\mod}{\ensuremath{\;\mathrm{mod}\;}}
\newcommand{\hsub}{\ensuremath{H^*}\xspace}
% \num\newcommand{\enc1}[1]{\ensuremath{\left[#1\right]_1}\xspace}
\newcommand{\enci}[1]{\ensuremath{\left[#1\right]_i}\xspace}
% \num\newcommand{\enc2}[1]{\ensuremath{\left[#1\right]_2}\xspace}
\newcommand{\enc}[1]{\ensuremath{\left[#1\right]}\xspace}
\newcommand{\gen}{\ensuremath{\mathsf{gen}}\xspace}
\newcommand{\prv}{\ensuremath{\mathsf{\mathbf{P}}}\xspace}
\newcommand{\prvpoly}{\ensuremath{\mathrm{P_{\mathsf{poly}}}}\xspace}
\newcommand{\prvpc}{\ensuremath{\mathrm{P_{\mathsf{PC}}}}\xspace}
\newcommand{\verpoly}{\ensuremath{\mathrm{V_{\mathsf{poly}}}}\xspace}
\newcommand{\verpc}{\ensuremath{\mathrm{V_{\mathsf{PC}}}}\xspace}
\newcommand{\ideal}{\ensuremath{\mathcal{I}}\xspace}
\newcommand{\prf}{\ensuremath{\pi}\xspace}
\newcommand{\simprv}{\ensuremath{\mathrm{P^{sim}}}\xspace}

%\newcommand{\enc}[1]{\ensuremath{\left[#1\right]}\xspace}
%\num\newcommand{\G0}{\ensuremath{\mathbf{G}}\xspace}
\newcommand{\GG}{\ensuremath{\mathbf{G^*}}\xspace}  % would have liked to call this G01 but problem with name
% \newcommand{\G}{\ensuremath{\mathbf{G}}\xspace}  % would have liked to call this G01 but problem with name
% \num\newcommand{\g0}{\ensuremath{\mathbf{g}}\xspace}
\newcommand{\inst}{\ensuremath{\phi}\xspace}
\newcommand{\inp}{\ensuremath{\mathsf{x}}\xspace}
\newcommand{\wit}{\ensuremath{\omega}\xspace}
\newcommand{\ver}{\ensuremath{\mathsf{\mathbf{V}}}\xspace}
\newcommand{\per}{\ensuremath{\mathsf{\mathbf{P}}}\xspace}
\newcommand{\sonic}{\ensuremath{\mathsf{Sonic}}\xspace}
\newcommand{\aurora}{\ensuremath{\mathsf{Aurora}}\xspace}
\newcommand{\auroralight}{\ensuremath{\mathsf{Auroralight}}\xspace}
\newcommand{\groth}{\ensuremath{\mathsf{Groth'16}}\xspace}
\newcommand{\kate}{\ensuremath{\mathsf{KZG}}\xspace}
\newcommand{\rel}{\ensuremath{\mathcal{R}}\xspace}
\newcommand{\relcirc}{\ensuremath{\mathcal{R}_C}\xspace}
\newcommand{\lang}{\ensuremath{\mathcal{L}}\xspace}
\newcommand{\ext}{\ensuremath{E}\xspace}
\newcommand{\params}{\ensuremath{\mathsf{params}_{\inst}}\xspace}
\newcommand{\protparams}{\ensuremath{\mathsf{params}_{\inst}^\advv}\xspace}
\num\newcommand{\p1}{\ensuremath{P_1}\xspace}
\newcommand{\advv}{\ensuremath{ {\mathcal A}^{\mathbf{*}}}\xspace} % the adversary that uses protocol adversary as black box
\newcommand{\crs}{\ensuremath{\sigma}\xspace}
%\num\newcommand{\crs1}{\ensuremath{\mathrm{\sigma}_1}\xspace}
%\num\newcommand{\crs2}{\ensuremath{\mathrm{\sigma}_2}\xspace}
\newcommand{\set}[1]{\ensuremath{\left\{#1\right\}}\xspace}
\newcommand{\hgen}{\ensuremath{\mathbf{\omega}}\xspace}
\newcommand{\vgen}{\ensuremath{\mathbf{g}}\xspace}
\renewcommand{\sim}{\ensuremath{\mathsf{sim}}\xspace}%the distribution of messages when \advv simulates message of \p1
\newcommand{\real}{\ensuremath{\mathsf{real}}\xspace}%the distribution of messages when \p1 is honest and \adv controls rest of players
 \newcommand{\koevec}[2]{\ensuremath{(1,#1,\ldots,#1^{#2},\alpha,\alpha #1,\ldots,\alpha #1^{#2})}\xspace}
\newcommand{\mida}{\ensuremath{A_{\mathrm{mid}}}\xspace}
\newcommand{\midb}{\ensuremath{B_{\mathrm{mid}}}\xspace}
\newcommand{\midc}{\ensuremath{C_{\mathrm{mid}}}\xspace}
\newcommand{\chal}{\ensuremath{\mathsf{challenge}}\xspace}
\newcommand{\attackparams}{\ensuremath{\mathsf{params^{pin}}}\xspace}
\newcommand{\pk}{\ensuremath{\mathsf{pk}}\xspace}
\newcommand{\attackdist}[2]{\ensuremath{AD_{#1}}\xspace}
\renewcommand{\neg}{\ensuremath{\mathsf{negl}(\lambda)}\xspace}
\newcommand{\ro}{\ensuremath{{\mathcal R}}\xspace}
\newcommand{\elements}[1]{\ensuremath{\mathsf{elements}_{#1}}\xspace}
 \num\newcommand{\elmpowers1}[1]{\ensuremath{\mathrm{\mathsf{e}}^1_{#1}}\xspace}
 \num\newcommand{\elmpowers2}[1]{\ensuremath{\mathrm{\mathsf{e}}^2_{#1}}\xspace}
\newcommand{\elempowrs}[1]{\ensuremath{\mathsf{e}_{#1}}\xspace}
 \newcommand{\secrets}{\ensuremath{\mathsf{secrets}}\xspace}
 \newcommand{\polysofdeg}[1]{\ensuremath{\F_{< #1}[X]}\xspace}
 \newcommand{\polys}{\ensuremath{\F[X]}\xspace}
 \newcommand{\bivar}[1]{\ensuremath{\F_{< #1}[X,Y]}\xspace}
 \newcommand{\sig}{\ensuremath{\mathscr{S}}\xspace}
 \newcommand{\prot}{\ensuremath{\mathscr{P}}\xspace}
 \newcommand{\PCscheme}{\ensuremath{\mathscr{S}}\xspace}
 \newcommand{\protprime}{\ensuremath{\mathscr{P^*}}\xspace}
 \newcommand{\sigprv}{\ensuremath{\mathsf{P_{sc}}}\xspace}
 \newcommand{\sigver}{\ensuremath{\mathsf{V_{sc}}}\xspace}
 \newcommand{\sigpoly}{\ensuremath{\mathsf{S_{\sigma}}}\xspace}
 \newcommand{\idpoly}{\ensuremath{\mathsf{S_{ID}}}\xspace}
\newcommand{\idpolyevala}{\ensuremath{\mathsf{\bar{s}_{ID1}}}\xspace}
\newcommand{\sigpolyevala}{\ensuremath{\mathsf{\bar{s}_{\sigma1}}}\xspace}
\newcommand{\sigpolyevalb}{\ensuremath{\mathsf{\bar{s}_{\sigma2}}}\xspace}
\newcommand{\bctv}{\ensuremath{\mathsf{BCTV}}\xspace}
\newcommand{\PI}{\ensuremath{\mathsf{PI}}\xspace}
\newcommand{\PIb}{\ensuremath{\mathsf{PI_B}}\xspace}
\newcommand{\PIc}{\ensuremath{\mathsf{PI_C}}\xspace}
\newcommand{\dl}[1]{\ensuremath{\widehat{#1}}\xspace}
\newcommand{\obgen}{\ensuremath{\mathcal O}\xspace}
\newcommand{\PC}{\ensuremath{\mathscr{P}}\xspace}
\newcommand{\permscheme}{\ensuremath{\sigma_\mathscr{P}}\xspace}

	
\newcommand{\selleft}{\ensuremath{\mathbf{q_L}}\xspace}
\newcommand{\selright}{\ensuremath{\mathbf{q_R}}\xspace}
\newcommand{\selout}{\ensuremath{\mathbf{q_O}}\xspace}
\newcommand{\selmult}{\ensuremath{\mathbf{q_M}}\xspace}
\newcommand{\selconst}{\ensuremath{\mathbf{q_C}}\xspace}
\newcommand{\selectors}{\ensuremath{\mathcal{Q}}\xspace}
\newcommand{\lvar}{\ensuremath{\mathbf{a}}\xspace}
\newcommand{\vars}{\ensuremath{\mathcal{V}}\xspace}
\newcommand{\rvar}{\ensuremath{\mathbf{b}}\xspace}
\newcommand{\ovar}{\ensuremath{\mathbf{c}}\xspace}
\newcommand{\pubvars}{\ensuremath{\mathcal{I}}\xspace}
\newcommand{\assignment}{\ensuremath{\mathbf{x}}\xspace}
\newcommand{\constsystem}{\ensuremath{\mathscr{C}}\xspace}
\newcommand{\relof}[1]{\ensuremath{\rel_{#1}}\xspace}
\newcommand{\pubinppoly}{\ensuremath{\mathsf{PI}}\xspace}
\newcommand{\sumi}[1]{\sum_{i\in[#1]}}
\newcommand{\summ}[1]{\sum_{i\in[#1]}}
\newcommand{\sumj}[1]{\sum_{j\in[#1]}}
\newcommand{\ZeroH}{\ensuremath{Z_{H}} \xspace}
\newcommand{\lpoly}{\ensuremath{\mathsf{a}}\xspace}
\newcommand{\rpoly}{\ensuremath{\mathsf{b}}\xspace}
\newcommand{\opoly}{\ensuremath{\mathsf{c}}\xspace}
\newcommand{\idpermpoly}{\ensuremath{\mathsf{z}}\xspace}
\newcommand{\lagrangepoly}{\ensuremath{\mathsf{L}}\xspace}
\newcommand{\zeropoly}{\ensuremath{\mathsf{\ZeroH}}\xspace}
\newcommand{\selmultpoly}{\ensuremath{\mathsf{q_M}}\xspace}
\newcommand{\selleftpoly}{\ensuremath{\mathsf{q_L}}\xspace}
\newcommand{\selrightpoly}{\ensuremath{\mathsf{q_R}}\xspace}
\newcommand{\seloutpoly}{\ensuremath{\mathsf{q_O}}\xspace}
\newcommand{\selconstpoly}{\ensuremath{\mathsf{q_C}}\xspace}
\newcommand{\idcomm}{\ensuremath{[s_{\mathsf{ID1}}]_1}\xspace}
\newcommand{\sigcomma}{\ensuremath{[s_{\mathsf{\sigma1}}]_1}\xspace}
\newcommand{\sigcommb}{\ensuremath{[s_{\mathsf{\sigma2}}]_1}\xspace}
\newcommand{\sigcommc}{\ensuremath{[s_{\mathsf{\sigma3}}]_1}\xspace}
\newcommand{\selleftcomm}{\ensuremath{[q_\mathsf{L}]_1}\xspace}
\newcommand{\selrightcomm}{\ensuremath{[q_\mathsf{R}]_1}\xspace}
\newcommand{\seloutcomm}{\ensuremath{[q_\mathsf{O}]_1}\xspace}
\newcommand{\selconstcomm}{\ensuremath{[q_\mathsf{C}]_1}\xspace}
\newcommand{\selmultcomm}{\ensuremath{[q_\mathsf{M}]_1}\xspace}

\newcommand{\multlinecomment}[1]{\directlua{-- #1}}
    

\newtheorem{lemma}{Lemma}[section]
\newtheorem{thm}[lemma]{Theorem}
\newtheorem{dfn}[lemma]{Definition}
\newtheorem{remark}[lemma]{Remark}

\newtheorem{claim}[lemma]{Claim}
\newtheorem{corollary}[lemma]{Corollary}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathcal{R}}
\newcommand{\crct}{\ensuremath{\mathsf{C}}\xspace}
\newcommand{\A}{\mathcal{A}}
%\newcommand{\G}{\mathcal{G}}
\newcommand{\Gr}{\mathbb{G}}
%\newcommand{\com}{\textsf{com}}  Ariel defined equivalent that also works in math mode
\newcommand{\cgen}{\text{cgen}}
\newcommand{\poly}{\ensuremath{\mathsf{poly(\lambda)}}\xspace}
\newcommand{\snark}{\ensuremath{\mathsf{snark}}\xspace}
\newcommand{\grandprod}{\mathsf{prod}}
\newcommand{\perm}{\mathsf{perm}}
%\newcommand{\open}{\mathsf{open}}
\newcommand{\update}{\mathsf{update}}
\newcommand{\Prove}{\mathcal{P}}
\newcommand{\Verify}{\mathcal{V}}
\newcommand{\Extract}{\mathcal{E}}
\newcommand{\Simulate}{\mathcal{S}}
\newcommand{\Unique}{\mathcal{U}}
\newcommand{\Rpoly}{\R{\poly}}
\newcommand{\Ppoly}{\Prove{\poly}}
\newcommand{\Vpoly}{\Verify{\poly}}
\newcommand{\Psnark}{\prv}%{\Prove{\snark}}
\newcommand{\Vsnark}{\ver}%{\Verify{\snark}}
\newcommand{\Rprod}{\R{\grandprod}}
\newcommand{\Pprod}{\Prove{\grandprod}}
\newcommand{\Vprod}{\Verify{\grandprod}}
\newcommand{\Rperm}{\R{\perm}}
\newcommand{\Pperm}{\Prove{\perm}}
\newcommand{\Vperm}{\Verify{\perm}}
% \newcommand{\zw}[1]{{\textcolor{magenta}{Zac:#1}}}
% \newcommand{\ag}[1]{{\textcolor{blue}{\emph{Ariel:#1}}}}
\newcommand{\prob}{\ensuremath{\mathrm{Pr}}\xspace}
\newcommand{\add}{\ensuremath{\mathrm{A}}\xspace}
\newcommand{\mul}{\ensuremath{\mathrm{M}}\xspace}
\newcommand{\prog}{\ensuremath{\mathrm{BP}}\xspace}

\newcommand{\extprot}{\ensuremath{E_{\prot}}\xspace}
\newcommand{\transcript}{\ensuremath{\mathsf{transcript}}\xspace}
\newcommand{\extpc}{\ensuremath{E_{\PCscheme}}\xspace}
\newcommand{\advpc}{\ensuremath{\mathcal A_{\PCscheme}}\xspace}
\newcommand{\advprot}{\ensuremath{\mathcal A_{\prot}}\xspace}
\newcommand{\protmany}{\ensuremath{ {\prot}_k}\xspace}

\usepackage{pifont}% http://ctan.org/pkg/pifont
\newcommand{\cmark}{\ding{51}}%
\newcommand{\xmark}{\ding{55}}%
\newcommand{\marlin}{\ensuremath{\mathsf{Marlin}}\xspace}
\newcommand{\fractal}{\ensuremath{\mathsf{Fractal}}\xspace}
% \newcommand{\Rsnark}{\R{\snark}}
\newcommand{\Rsnark}{\R}
\newcommand{\subvec}[1]{\ensuremath{#1|_{\subspace}}\xspace}
\newcommand{\restricttoset}[2]{\ensuremath{#1|_{#2}}\xspace}
\newcommand{\isinvanishing}[1]{\ensuremath{\mathsf{IsInVanishing_{\subspace,#1}}}\xspace}
\newcommand{\batchedisinvanishing}[1]{\ensuremath{\mathsf{BatchedIsInVanishing_{\subspace,#1}}}\xspace}
\newcommand{\isconsistent}{\ensuremath{\mathsf{IsConsistent}}\xspace}
\newcommand{\isintable}[1]{\ensuremath{\mathsf{IsInTable_{\subspace,#1}}}\xspace}
\newcommand{\isinvanishingtable}[1]{\ensuremath{\mathsf{IsInVanishingTable_{\subspace,#1}}}\xspace}
\newcommand{\isvanishingsubtable}[1]{\ensuremath{\mathsf{IsVanishingSubtable_{#1}}}\xspace}
\newcommand{\haslowerdegree}{\ensuremath{\mathsf{HasLowerDegree}}\xspace}
\newcommand{\haslowdegree}[1]{\ensuremath{\mathsf{HasLowDegree_{#1}}}\xspace}
\newcommand{\issubtable}[1]{\ensuremath{\mathsf{IsSubtable_{#1}}}\xspace}
\newcommand{\isinsubtable}[2]{\ensuremath{\mathsf{IsInSubtable_{#1,#2}}}\xspace}
\newcommand{\secbasezero}[1]{\ensuremath{\hat{\tau}_{#1}}\xspace}
\newcommand{\secbase}[1]{\ensuremath{\hat{\tau}_{#1}}\xspace}
\newcommand{\secbasereg}[1]{\ensuremath{\tau_{#1}}\xspace}
\newcommand{\secset}{\ensuremath{I}\xspace}
\newcommand{\pubbase}[1]{\ensuremath{\mu_{#1}}\xspace}
\newcommand{\subspace}{\ensuremath{\mathbb{H}}\xspace}
\newcommand{\subtable}{\ensuremath{T_0}\xspace}
\newcommand{\tablelang}{\ensuremath{\lang_{T}}\xspace}
\newcommand{\vanishingtablelang}{\ensuremath{\lang_{\subspace}}\xspace}
\newcommand{\nonorm}[1]{\ensuremath{\Gamma^T_{#1}}\xspace}
\newcommand{\unnorm}[2]{\ensuremath{\Gamma^{#1}_{#2}}\xspace}
\newcommand{\bigsubspace}{\ensuremath{\mathbb{H}}\xspace}
\newcommand{\bigspacebase}{\ensuremath{\lambda}\xspace}
\newcommand{\bigspacegen}{\ensuremath{\mathsf{h}}\xspace}
\newcommand{\modvan}[1]{\ensuremath{\mathrm{mod\;}Z_{#1}}\xspace}
\newcommand{\extractevaltable}{\ensuremath{\mathsf{ExtractEvalTable}_{C,\tablegroup}}\xspace}


\begin{document}
\maketitle
\bibliographystyle{alpha}
\bibliography{references}
\section{The KZG polynomial commitment scheme - an informal intro}

The idea of polynomial commitment schemes is that a prover \prv can send a short commitment to a large polynomial $f\in \polysofdeg{d}$;
and later open it at a point $z\in \F$ chosen by the verifier.
\prv can also construct a proof \prf that the value he sends is really $f(z)$ for the $f$ he had in mind during commitment time.

\section{The KZG commitment scheme:}
\paragraph{Prequisites:}
Given integer security parameter $\lambda$. We assume access to
\begin{itemize}
 \item 
Groups \G,\Gt of prime order $r$ written additively with $\lambda^{\omega(1)}<r\leq 2^{\lambda}$
\item randomly chosen generator $g\in \G$ and generator $g_t\in \Gt$.

\item Denote by \F the field of size $r$. A bi-linear pairing function $e:\G\times \G \to \Gt$ such that $\forall a,b \in \F$, 
$e(a\cdot ,b\cdot g) = g_t^{a\cdot b}$


For $c\in \F$, we use the notation $\enc{c}\defeq c\cdot g$.

\end{itemize}

\begin{remark}
 How do we actually construct pairings??
 They were first constructed by Andr\'e Weil, where $\G$ is taken to be the degree zero divisor class group of an algebraic curve - which is the same as the so-called Jacobian of the curve. In crypto we always use elliptic curves which are a special case, and where this group is isomorphic to the curve itself!  These pairings were part of Weil's proof of what's called the Riemann hypothesis for curves over finite fields/Algebraic function fields. 
 Much later, Victor Miller showed a practical algorithm to compute them (the ``Miller loop'').
\end{remark}

\subsection{The scheme:}
\begin{itemize}
 \item 
 \textbf{setup:}: Generate $\srs= \enc{1},\enc{x},\ldots,\enc{x^d}$,\\
 for random $x\in \F$.
 \item\textbf{Commitment to $f\in\polysofdeg{d}$:}


 $\cm(f)\defeq   \enc{f(x)}$\\
 \item The $\open(\cm,z,s;f)$ protocol  - proving $f(z)=s$ 
\begin{enumerate}
 \item \prv computes 
 $h(X)\defeq \frac{f(X)-f(z)}{X-z}$\\
 \item \prv sends $\prf=[h(x)]$.
 \item \ver outputs \acc if and only if 
\[e(\cm-\enc{s},\enc{1}) = e(\prf, \enc{x-z})\]
\end{enumerate}
\end{itemize}

\section{The Algebraic Group Model}
We wish to capture the notion of an Algebraic Adversary that can generate new group elements by doing ``natural'' operations on the set
of group elements he already received.

The intuition is that when the discrete log is hard, the group elements look random to (an efficient) adversary, and thus there's no other way for him
to produce ``useful'' group elements.


More formally,
\begin{dfn}
 By an \emph{SRS-based protocol} we mean a protocol between a prover \prv and verifier \ver such that at
 before the protocol begins a randomized procedure \setup is run, returning a string $\srs \in \G^n$.

In our protocols, by an \emph{algebraic adversary} \adv in an SRS-based protocol we mean a \poly-time algorithm which satisfies the following.
\begin{itemize}
 \item Whenever \adv outputs an element $A\in \G$, it also outputs a vector $v$ over \F such that $A = \sum_{i\in [n]}v_i \srs _i$.
\end{itemize}
\end{dfn}
\section{Knowledge Soundness of the KZG scheme}
We say a PCS has \emph{Knowledge soundness in the Algebraic Group Model} if, there exists an efficient algorithm $E$
such that any algebraic adversary \adv has probability at most \negl to win the following game:
\begin{enumerate}
 \item \adv outputs a commitment \cm.
 \item \ext outputs a polynomial $f\in \polysofdeg{d}$
 \item \adv outputs $z,s\in \F,\prf\in \G$.
 \item \adv takes part of \prv in $\open(\cm,z,s)$.
 \item \adv wins iff
 \begin{enumerate}
  \item \ver outputs \acc in the end of \open.
  \item $f(z)\neq s$.
 \end{enumerate}

\end{enumerate}
We use the following extension of the discrete-log assumption:
\begin{dfn}
    The $Q$-DLOG assumption for \G says that:
    For any efficient algorithm $A$, the probability that given
    \kzgsrs{Q} for random $x\in \F$
    outputs $x$ is \negl
\end{dfn}
\begin{lemma}
 Assuming the $d$-DLOG for \G, KZG has knowledge soundness in the algebraic group model
\end{lemma}
\begin{proof}
 We must define the extractor \ext:
 When \adv outputs \cm, since it's algebraic, it also outputs  $f\in\polysofdeg{d}$ such that
 $\cm = \enc{f(x)}$.
 \ext will simply output $f$.
 Let \adv be some efficient algebraic adversary.
 
 We will describe an algorithm $B$ following the game between \ext and \adv such that
 whenever \adv wins the game, $B$ finds $x$!.
 
 
 During \open when \adv sends \prf, it also sends 
 $h\in \polysofdeg{d}$ such that $\prf=\enc{h(x)}$.
 Assume we're in the case that \adv won the game.
 This means that \adv sent $z,s$  and $\prf$ such that
 $\ver(\cm,z,s,\prf) =\acc$.
 This means that
 $e(\cm-[s],[1]) = e(\prf,[x-z])$
 In our case this is the same as
 $e(\enc{f(x)}-[s],[1]) = e(\enc{h(x)},[x-z])$
 This implies
 \[f(x)-s = h(x)(x-z)\]
 Define the polynomial 
 \[p(X)\defeq f(X)-s - h(X)(X-z)\]
 We claim that $p(X)$ \emph{can't} be the zero polynomial:
 If it was, in particular $p(z)=0$, and then
 $f(z)-s =  h(z)(z-z)=0$, which means $f(z)=s$ - but \adv won the game so $f(z)\neq s$!
 
 So $p(X)$ isn't the zero polynomial in the case that \adv won.
 We claim that in this case we can find $x$:
 
 Note that we can compute the coefficients of $p$, since \adv sent the coefficients of $f$ and $h$.
 
 Since \ver accepting means that $p(x)=0$.
Thus, we can factor $p$, and $x$ will be one of its roots.
We can check for each root $\gamma$ of $p$ if $\gamma=x$ by checking $\enc{\gamma}=\enc{x}$.


 
 
\end{proof}

\section{Lecture 2: Proving circuit satisfiability Plonk style}

We'll look at arithmetic circuits $C$ over \F
\begin{itemize}
 \item with addition and multiplication gates of fan-in 2 and unbounded fan-out.
\item We'll assume there's a unique output wire
\item we'll denote by $n$ the number of gates and $m$ the number of wires.
\item We'll assume input wires go only into one gate (as someone astutely observed during the lecture, otherwise we need extra copy constraints in the BP program described later).
\end{itemize}

Draw example of $(a+b)\cdot c$ circuit


Given such a circuit we can look at the relation
\relcirc
containing all pairs $(z\in \F,\wit\in \F^m)$ such that
$w$ is a valid assignment to the wires of $C$ with output value $\wit_m=z$.

Though in SNARK context, we almost always want to look at relations and separate the instance and witness, for simplicity we'll focus on simply proving
knowledge of *some* assignment to $C$.

\subsection{Baby-Plonk programs}
We wish to reduce checking an assignment to a circuit to checking an assignment to a Plonk program.
In the literature you will find references to Turbo-plonk and ultra-plonk programs.
Here for simplicity, we look at a much more restricted notion of ``baby plonk'' programs, that are still sufficient to capture our circuits.

\begin{dfn}
 A \emph{Baby-PlonK} program \prog is defined by 
 \begin{enumerate}
  \item vectors $\add,\mul\in \F^n$.
 \item A set of  ``copy constraints'' of the form ``$w_{i,j}=w_{i',j'}$''  for some $i,i' \in \set{1,2,3}$ and $j,j' \in [n]$
 \end{enumerate}
 A set of vectors $a,b,c\in \F^n$ \emph{satisfies} \prog if 
 \begin{enumerate}
  \item For each $i\in [n]$ 
  \[\add_i \cdot (a_i+b_i) + \mul_i(a_i\cdot b_i) = c_i\]
  \item Setting $w_1=a,w_2=b,w_3=c$ all copy constraints are satisfied.
 \end{enumerate}
\textit{Draw example as rectangle - emphasizing local vs global}
\end{dfn}



\subsection{Some algebra}
Let's assume $n$ is a power of two, and $n$ divides $|F|-1$.
That means there's an element $g\in \F$ of order $n$.
That is $H=\set{g,\ldots,g^n}$ is a multiplicative subgroup of order $n$.
We denote by $Z_H(X)= \prod_{i\in [n]}(X-g^i)$ the vanishing polynomial of $H$.
We have $Z_H(X)=X^n-1$.

We have for any polynomial $F(X)$ that 
$F(a)=0$ for all $a\in H$ iff $F$ is divisible by $Z_H$, i.e. iff there exists $T(X)\in \polys$ such that $F(X)=T(X)Z_H(X)$.

Given vector $v\in \F^n$ we'll say a polynomial $f$ \emph{interpolates $v$ over $H$} if it has degree $<n$
for all $i\in [n]$ $f(g^i)=v_i$.
There is always such unique $f(X)=\sum v_i L_i(X)$ where $L_i(X)=\frac{g^i}{n} \frac{X^n-1}{X-g^i}$ are the Lagrange base of $H$.

Given $\add,\mul,a,b,c \in \F^n$ we abuse notation and denote by the same names the polynomials interpolating them.

Define 
  \[F(X)\defeq \add(X) \cdot (a(X)+b(X)) + \mul(X)(a(X)\cdot b(X)) -c(X).\]
Assume that $a,b,c$ \emph{satisfy} the copy constraints of \prog.
(Verifying that is in fact the more interesting part of PlonK and we'll deal with that later!)
Then we have that $a,b,c$ satisfy \prog iff $F(X)$ is divisible by $Z_H$.


\subsection{A protocol for checking satisfiability (missing the copy constraint checks for now)}
Now we can use the KZG scheme to get a protocol checking an assignment for \prog.
The cool thing is that the proof size will be a \emph{constant} number of \F and \G elements - independent of $n$!
(For construction to work we need that $|\G|=|\F|>n$ so in fact in terms of bit-length the proof is $\Omega(\log n)$)

In the description below we write $\com(f)$ for the KZG commitment of $f\in \polys$.

Below we assume \prv has a satisfying assignment $(a,b,c)$ to \prog.

\textbf{Preprocessing:}
We precompute the KZG commitments \com{A},\com{M} of $A,M$ and send them to \ver.

\textbf{The protocol:}
\begin{enumerate}
 \item \prv computes and sends \com{a},\com{b},\com{c} to \ver.
 \item With $F(X)$ defined as above, \prv computes the quotient polynomial $T(X)\defeq F(X)/Z_H(X)$.
 \item \prv computes and sends \com{T} to \ver.
 \item \ver chooses random $\alpha\in \F$ and sends it to \prv.
 \item \prv sends $\bar{A}\defeq A(\alpha),\bar{M}\defeq M(\alpha),\bar{a}\defeq a(\alpha),\bar{b}\defeq b(\alpha),\bar{c}\defeq c(\alpha),\bar{T}\defeq T(\alpha)$ to \ver.
 \item \prv sends the KZG opening proofs for the above values.
 \item \ver verifies the KZG openings proofs for all values.
 \item \ver computes $\bar{F}\defeq     \bar{A}(\bar{a}+\bar{b})+\bar{M}\bar{a}\bar{b} - \bar{c}$.
 \item \ver accepts iff $\bar{F}=Z_H(\alpha)\bar{T}$.
\end{enumerate}



\section{Lecture 3: the PlonK permutation argument (based on Bayer-Groth)}
\subsection{Copy checks via permutations}
Let $v=(a,b,c)$, and redefine $n$ as $n=|v|$. In \prog we have a bunch of constraints $v_i=v_j$ for $i,j \in [3n]$.
We can reduce all checks to one \emph{permutation check}.
This mean checking for some fixed permutation $\sigma$ on $[n]$, that $\sigma(v)=v$.
Here we define $\sigma(v)\in \F^n$ by $\sigma(v)_{\sigma(i)} =v_i$ $\forall\; i\in [n]$.
\textbf{example:}
Say we have the constraints $v_1=v_2, v_2=v_7, v_5=v_6$.
Define $\sigma= (127)(56)$.
Then $v$ satisfies the copy constraints iff $v=\sigma(v)$.


\subsection{Mutliset checks via grand products}
Let's look at a related problem that we will use soon for the permutation check.
Now \prv has  \emph{two} vectors $f,g$ of size $n$ and wishes to show to \ver they are equal as multisets,
i.e. that there is \emph{some} permutation $\sigma$ such that $g=\sigma(f)$.

Here is a protocol for this.
\begin{enumerate}
 \item \ver sends random $\gamma\in \F$
 \item \prv shows to \ver  that 
 \[\prod_{i\in [n]} (f_i+\gamma) = \prod_{i\in [n]}(g_i+\gamma)\]\label{eq:prod}
\end{enumerate}
\begin{claim}
Let $r=|\F|$.
 The check in equation \ref{eq:prod} holds with probability one if $f,g$ are mutliset equal,
 and probability at most $n/r$ if they are not.
\end{claim}
\begin{proof}
Define the polynomials 
$F(X)\defeq \prod_{i\in [n]} (f_i+X),G(X)\defeq \prod_{i\in [n]} (g_i+X)$
We are checking $F(\gamma)=G(\gamma)$. If $f,g$ are mutliset equal $F\equiv G$ so this holds for all $\gamma$.
If they are not $F\not\equiv G$ so they can be equal for at most $n$ $\gamma\in \F$.
\end{proof}


One main question is how \prv efficiently shows to \ver that equation \ref{eq:prod} holds when \ver only 
has commitments to $f,g$? We will see a solution soon!
\subsection{Permuations via mulitset checks}
For our SNARK, we wish to check that $g=\sigma(f)$ for a \emph{fixed} permutation $\sigma$.
We show we can reduce this check to a multiset check.
\begin{claim}
 Given a permutation $\sigma$ on $[n]$ and vectors $f,g\in \F^n$, we have $g=\sigma(f)$ if and only if
 the sets of pairs $A\defeq \set{(f_i,i)}_{i\in [n]}$ and $B\defeq \set{(g_{i},\sigma(i)}_{i\in [n]}$
 are equal as (multi)sets.
\end{claim}

The mulitset protocol dealt with scalars, not tuples.
Here we can use a little randomness to reduce the scalars to tuples.
\begin{claim}
 Given sets of pairs $A,B$ as in the claim above and $\beta \in \F$.
 Define the mutlisets $A'=\defeq \set{f_i+\beta \cdot i}$, $B'\defeq \set{g_i + \beta \cdot \sigma(i)}$.
 Then if $A,B$ are different as sets, then $A',B'$ are different as multisets except with probability $n/r$ over $\beta$
\end{claim}
\begin{proof}
If $A\neq B$, there is some pair $(b_1,\beta b_2)\in B\setminus A$.
For any fixed $(a_1,a_2)\in A$ the probability that $a_1+\beta a_2= b_1+\beta b_2$ is at most $1/r$.
Now do a union bound over elements of $A$.
\end{proof}


\subsection{grand products via polynomial equations}
Now we deal with the following question. Suppose \ver has a KZG-commitment $\cm(f)$ to a polynomial of degree $<n$ (as before 
think of $f$ as interpolating the vector $f\in \F^n$ over $H$).
Suppose that $\prod_{i\in [n]} f_i =1$.  How can \prv prove this to \ver?

\textbf{Protocol:}
\begin{enumerate}
 \item \prv interpolates on $H$ the vector $Z$ with values 
 $Z_1=1$, $Z_i=\prod_{j<i} (f_j)$ for $i\in \set{2,\ldots,n}$.
 I.e $Z(g^i) = Z_i$ $\forall i\in [n]$.
 \item \prv computes and send $\com{Z}$ to \ver.
 \item \ver sends random $\alpha\in \F$ to \prv.
 \item \prv computes poly:
 \[T(X)=\frac{L_1(X)(Z(X)-1)) + \alpha(Z(g\cdot X)-Z(X)f(X))}{Z_H(X)}\]
 \item \ver sends random $\gamma \in \F$ to \prv. 
 \item \prv sends $\bar{T}\defeq T(\gamma),\bar{f}\defeq f(\gamma),\bar{Z}\defeq Z(\gamma),\bar{Z}_{g}\defeq Z(g\cdot \gamma)$
 \item \prv sends the KZG opening proofs for the above values.
 \item \ver verifies the KZG openings proofs for all values.
 \item \ver computes $\bar{F}\defeq    L_1(\gamma)(Z(\gamma)-1) + \alpha(Z(g\cdot\gamma)-Z(\gamma)f(\gamma)))$
 \item \ver accepts iff $\bar{F}=Z_H(\gamma)\bar{T}$.
\end{enumerate}

\begin{claim}
 If $\prod_{i\in [n]}f_i =  \prod_{i\in [n]}f(g^i)\neq 1$ then \ver rejects e.w.p $(3n)/r$.
\end{claim}
\begin{proof}
 Define the polynomial 
 \[F(X)=L_1(X)(Z(X)-1) + \alpha(Z(g\cdot X)-Z(X)f(X))\]
 similar to the protocol of the previous lecture, the protocol is checking if $F$ vanishes on $H$ via a divisibility check.
 Assume it does vanish on $H$.
 Then e.w.p $1/r$ over $\alpha$ this implies both terms  $F_1=L_1(X)(Z(X)-1))$ and $F_2\defeq Z(g\cdot X)-Z(X)f(X)$ vanish on $H$.
 
 \begin{itemize}
  \item $F_1$ vanishing on $H$ implies $Z(g)=1$.
  \item $F_2$ vanishing on $H$ implies that for each $i\in [n]$, $Z(g^{i+1})=f(g^i)Z(g^i)$. And so 
  \[1=Z(g)= Z(g^{n+1})=\prod_{i\in [n]} f(g^i)\] 
 as required.
 \end{itemize}

 
\end{proof}
\subsection{Putting it all together}
We sketch how the above components can be used to show $\sigma(v)=v$ assuming \ver has $\com{v}$:

\ver chooses random $\beta,\gamma\in \F$.

\prv uses the above grand product argument to show $\prod_{i\in [n]} f_i =1$.
For the vector $f$ defined as
\[f_i \defeq \frac{v_i + \beta \cdot i +\gamma}{v_i + \beta \cdot \sigma(i) +\gamma}\]

To enable this we compute in a preprocessing phase the polynomials $ID,S$ that interpolate on $H$ the identity and $\sigma$ permutation.
I.e. $ID(g^i)=i, S(g^i)=\sigma(i)$.
For full details see Section 5 of the PlonK paper.





\section{Lecture 4 - lookup arguments}
Say we want to prove in a plonk program
that $0\leq x \leq 2^{s-1}$.
We could do it as follows:
\prv sends the binary decomposition $x_0,\ldots,x_{s-1}$
and proves that
\begin{itemize}
 \item Send $x_0,\ldots,x_{s-1}$ are binary, via equation $x_i(x_i-1)=0$.
 \item $\sum_{i<s} x_i2^i =x$
\end{itemize}
This takes $s+1$ gates - in fact more like $2s$ since the addition has to be split up.
Lookup arguments offer an alternative approach.
For polynomials $f,t\in \polys$ let's write $f\subset t$ if as \emph{sets} $\sett{f(a)}{a\in H}\subset \sett{t(a)}{a\in H}$.
A \emph{lookup protocol} allows proving this to \ver having \com{f},\com{t}.
Say $s=\log n$, $|H|=n$. Say we want to check all of $f$'s vals are $0\leq f_i \leq 2^s-1$.
In the above example, we could precompute \com{t} for $t$ with values \set{0,\ldots,2^s-1} on $H$ 
and apply lookup protocol.

\subsection{plookup - Lookup protocols via multiset checks}
Fix $t,f\in \F^n$. Define the \emph{multi-set} 
$A=\set{(f_i,f_i)}_{i\in [n]}\cup \sett{(t_i,t_{i+1})}{i \in [n-1]}$

\begin{claim}
Assume (for simplicity mainly) $t$ contains distinct values and is sorted: $t_1<t_2\ldots<t_n$.
 $f\subset t$ if and only if there exists $s\in \F^{2n-1}$ such that 
defining $S'=\set{(s_i,s_{i+1}}_{i\in [2n-1]}$, 
we have $A=S$ as multisets.
\end{claim}
\begin{proof}
\textbf{only if:}
Define $s$ to be the \emph{sorted} version of the (mutli-set) union $f\cup t$.
Then $A=S'$.
\end{proof}


\subsection{Lookups based on log-derivative}

The main claim is :

\begin{claim}
Assume $r=|\F|$ is prime and larger than $n$.
 $f\subset t$ if and only if there exists $m\in \F^n$ such that as rational functions
 \[\sum_{i\in [n]}\frac{m_i}{X+t_i}=\sumi{n}\frac{1}{X+f_i}\]
\end{claim}
\begin{proof}
 \textbf{only if:} Define $m_i$ to be the number of times $t_i$ appears in $f$.
 \textbf{if(sketch):} The functions $1/(X+a)$ for different $a\in \F$ are linearly independent,
 therefore the functions in the equation being equal implies every coefficient is equal.
 So there can't be any $1/(X+a)$ on the RHS for $a\notin T$.
\end{proof}


\textbf{protocol idea:check identity on random $\beta$}
\begin{enumerate}
 \item \prv computes and send \com{m}
 \item \ver chooses random $\beta\in \F$.
 \item \prv sends \com{A} for polynomial $A$ with $A_i=\frac{m_i}{\beta+t_i}-\frac{1}{\beta+f_i}$
 \item \ver checks that $A$ is well-formed and sums to zero on $H$.
\end{enumerate}

Checking that $A$ is well-formed - has the correct values, can be done by a quotient polynomial similar to others we've seen.

\subsection{Proving a polynomial sums to zero:}
We rely on the following claim from the Aurora paper:
\begin{claim}
 Given $f\in \polysofdeg{n}$,
 $\sum_{a\in H} f(a) = n\cdot f(0)$.
\end{claim}
\begin{proof}
 \[f(0)=\sumi{n}f_i L_i(0)\]
 We have for all $i\in [n]$, $L_i(0)=1/n$.
\end{proof}





\end{document}