\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}

\title{Marlin Diagram}
\date{July 2020}

\usepackage[x11names]{xcolor}
\usepackage[b4paper,margin=1.2in]{geometry}
\usepackage{tikz}
\usepackage{afterpage}

\newenvironment{rcases}
  {\left.\begin{aligned}}
  {\end{aligned}\right\rbrace}

\DeclareMathOperator*{\argmax}{arg\,max}
\begin{document}

\newcommand{\cm}[1]{\ensuremath{\mathsf{cm}_{#1}}}
\newcommand{\vcm}[1]{\ensuremath{\mathsf{vcm}_{#1}}}
\newcommand{\s}{\ensuremath{m}}
\newcommand{\w}{\ensuremath{\hat{w}}}
\newcommand{\x}{\ensuremath{\hat{x}}}
\newcommand{\z}{\ensuremath{\hat{z}}}
\newcommand{\za}{\ensuremath{\hat{z}_A}}
\newcommand{\zb}{\ensuremath{\hat{z}_B}}
\newcommand{\zc}{\ensuremath{\hat{z}_C
}}
\newcommand{\zm}{\ensuremath{\hat{z}_M}}

\newcommand{\val}{\ensuremath{\mathsf{val}}}
\newcommand{\row}{\ensuremath{\mathsf{row}}}
\newcommand{\col}{\ensuremath{\mathsf{col}}}
\newcommand{\rowcol}{\ensuremath{\mathsf{rowcol}}}

\newcommand{\hval}{\ensuremath{{\val}}}
\newcommand{\hrow}{\ensuremath{{\row}}}
\newcommand{\hcol}{\ensuremath{{\col}}}
\newcommand{\hrowcol}{\ensuremath{{\rowcol}}}

\newcommand{\bb}{\ensuremath{\mathsf{b}}}
\newcommand{\denom}{\ensuremath{\mathsf{denom}}}

\newcommand{\sumcheckinner}{\mathsf{inner}}
\newcommand{\sumcheckouter}{\mathsf{outer}}

\newcommand{\Prover}{\mathcal{P}}
\newcommand{\Verifier}{\mathcal{V}}

\newcommand{\F}{\mathbb{F}}

\newcommand{\DomainA}{H}
\newcommand{\NonZeroDomain}{K}

\newcommand{\vPoly}[1]{\ensuremath{v_{#1}}}
\newcommand{\sPoly}[1]{\ensuremath{s_{#1}}}


This diagram (on the following page) shows the interaction of the Marlin prover and verifier. It is similar to the diagrams in the paper (Figure 5 in Section 5 and Figure 7 in Appendix E, in the latest ePrint version), but with two changes: it shows not just the AHP but also the use of the polynomial commitments (the cryptography layer); and it aims to be fully up-to-date with the recent optimizations to the codebase. This diagram, together with the diagrams in the paper, can act as a ``bridge" between the codebase and the theory that the paper describes.

\section{Glossary of notation}
\begin{table*}[htbp]
  \centering
  \renewcommand{\arraystretch}{1.5}
  \begin{tabular}{c|c}
    $\F$ & the finite field over which the R1CS instance is defined \\
     \hline
    $x$ & public input \\
     \hline
    $w$ & secret witness \\
     \hline
    $\DomainA$ & variable domain \\
     \hline
    $\NonZeroDomain_M$ & matrix domain for matrix $M$\\
     \hline
    $\NonZeroDomain$ & $\argmax_{\NonZeroDomain_M}{|\NonZeroDomain_M|}$\\
     \hline
    $X$ & domain sized for input (not including witness) \\
     \hline
    $\vPoly{D}(X)$ & vanishing polynomial over domain $D$ \\
    \hline
    $\sPoly{D_1, D_2}(X)$ & ``selector'' polynomial over domains $D_1 \supseteq D_2$, defined as $\frac{|D_2| \vPoly{D_1}}{|D_1| \vPoly{D_2}}$ \\
    \hline
    $u_D(X, Y)$ & bivariate derivative of vanishing polynomials over domain $D$\\
     \hline
    $A, B, C$ & R1CS instance matrices \\
    \hline
    $A^*, B^*, C^*$ &
    \begin{tabular}{@{}c@{}}shifted transpose of $A,B,C$ matries given by $M^*_{a,b} := M_{b,a} \cdot u_\DomainA(b,b) \; \forall a,b \in \DomainA$ \\ (optimization from Fractal, explained in Claim 6.7 of that paper) \end{tabular} \\
     \hline
    $\hrow_M, \hcol_M, \hval_M$ &
    LDEs of (respectively) row positions, column positions, and values of non-zero elements of matrix $M^*$\\
    \hline
    ${\hrowcol_M}$ &
    \begin{tabular}{@{}c@{}} LDE of the element-wise product of $\row$ and $\col$, given separately for efficiency  \\ (namely to allow this product to be part of a \textit{linear} combination) \end{tabular} \\
    \hline
    $\Prover$ & prover \\
     \hline
    $\Verifier$ & verifier \\
     \hline
    $\Verifier^{p}$ &
    	\begin{tabular}{@{}c@{}} $\Verifier$ with ``oracle" access to polynomial $p$ (via commitments provided \\ by the indexer, later opened as necessary by $\Prover$) \end{tabular}\\
    \hline
    $\bb$ & bound on the number of queries \\
    \hline
    $r_M(X, Y)$ & an intermediate polynomial defined by $r_M(X, Y) = M^*(Y,X)$\\
  \end{tabular}
\end{table*}

\afterpage{%
\newgeometry{margin=0.2in}

\section{Diagram}

\centering
\begin{tikzpicture}[scale=0.95, every node/.style={scale=0.95}]

\tikzstyle{lalign} = [minimum width=3cm,align=left,anchor=west]
\tikzstyle{ralign} = [minimum width=3cm,align=right,anchor=east]

\node[lalign] (prover) at (-3,27.3) {%
$\Prover(\F, \DomainA, \NonZeroDomain, A, B, C, x, w)$
};

\node[ralign] (verifier) at (16.2,27.3) {%
$\Verifier^{\hrow, \hcol, \hrowcol, \hval_{A^*}, \hval_{B^*}, \hval_{C^*}}(\F, \DomainA, \NonZeroDomain, x)$
};

\draw [line width=1.0pt] (-3,27.0) -- (16,27.0);

\node[lalign] (prover1) at (-3,26.1) {%
$z := (x, w), z_A := Az, z_B := Bz$ \\
sample $\w(X) \in \F^{<|w|+\bb}[X]$ and $\za(X), \zb(X) \in \F^{<|\DomainA|+\bb}[X]$ \\
sample mask poly $\s(X) \in \F^{<3|\DomainA|+2\bb-2}[X]$ such that $\sum_{\kappa \in \DomainA}\s(\kappa) = 0$
};

\draw [->] (-2,24.8) -- node[midway,fill=white] {commitments $\cm{\w}, \cm{\za}, \cm{\zb}, \cm{\s}$} (15,24.8);

\node[ralign] (verifier1) at (16,24.0) {%
$\eta_A, \eta_B, \eta_C \gets \F$ \\
$\alpha \gets \F \setminus \DomainA$
};

\draw [->] (15,23.3) -- node[midway,fill=white] {$\eta_A, \eta_B, \eta_C, \alpha \in \F$} (-2,23.3);

\node[lalign] (prover2) at (-3,22.5) {%
compute $t(X) := \sum_M \eta_M r_M(\alpha, X)$
};

\draw (-2.9,22.0) rectangle (15.9,3.8);

\node (sc1label) at (6.5,21.7) {%

\textbf{sumcheck for} $\s(X) + u_H(\alpha, X) \left(\sum_M \eta_M \zm(X)\right) - t(X)\z(X)$ \textbf{ over } $\DomainA$
};

\node[lalign] (prover3) at (-2,20.7) {%
let $\zc(X) := \za(X) \cdot \zb(X)$ \\
find $g_1(X) \in \F^{|\DomainA|-1}[X]$ and $h_1(X)$ such that \\
$\s(X)+u_H(\alpha, X)(\sum_M \eta_M \zm(X)) - t(X)\z(X) = h_1(X)\vPoly{\DomainA}(X) + Xg_1(X)$ \hspace{0.3cm} $(*)$
};

\draw [->] (-1,19.5) -- node[midway,fill=white] {commitments $\cm{g_1}, \cm{h_1}$} (14,19.5);

\node[ralign] (verifier2) at (15.4,19.1) {%
$\beta \gets \F \setminus \DomainA$
};

\draw [->] (14,18.7) -- node[midway,fill=white] {$\beta \in \F$} (-1,18.7);

\draw (-0.85,18.2) rectangle (13.85,7.6);

\node (sc2label) at (6.5,17.6) {%
\textbf{for each} $M \in \{A, B, C\}$, \textbf{ sumcheck for } $\frac{\vPoly{\DomainA}(\beta) \vPoly{\DomainA}(\alpha)\hval_{M^*}(X)}{\color{purple}(\beta-\hrow(X))(\alpha-\hcol(X))} $ \textbf{ over } $\NonZeroDomain_M$
};

\node[align=center] (mid1) at (6.5, 16) {%
$\begin{aligned} 
    \text{ let } {\color{orange} a_M(X)} &{}:= {\color{gray} \vPoly{\DomainA}(\beta) \vPoly{\DomainA}(\alpha)} \hval_{M^*}(X)
    \\
    \text{let } {\color{Green4} b_M(X)} &{}:= (\beta - \hrow_M(X)) (\alpha - \hcol_M(X)) \\
                                       &{}= {\color{gray}\alpha\beta} - {\color{gray}\alpha}\hrow_{M^*}(X) - {\color{gray}\beta}\hcol_{M^*}(X) + \hrowcol_{M^*}(X) \text{ (over $\NonZeroDomain_M$)}\\
\end{aligned}$
};

\node[lalign] (prover4) at (-0.75,14.4) {%
find $g_M(X), h_M(X) \in \F^{|\NonZeroDomain_M|-1}[X]$ and $\sigma_M \in \F$ s.t. \\
$h_M(X)\vPoly{\NonZeroDomain_M}(X) = {\color{orange} a_M(X)} - {\color{Green4} b_M(X)} (Xg_M(X)+ \sigma_M/|\NonZeroDomain_M|)$
};

\draw [->] (0,13.6) -- node[midway,fill=white] {commitments $\cm{g_A}, \cm{g_B}, \cm{g_C}$, and claimed sums $\sigma_A, \sigma_B, \sigma_C$} (13,13.6);
\node[ralign] (verifier3) at (13.9, 13) {%
$\delta_A, \delta_B, \delta_C \gets \F$
};
\draw [->] (11,13) -- (0,13);
\node[lalign] (prover5) at (-0.75,12.3) {%
let $h(X) := \sum_{M \in \{A, B, C\}} (\delta_M  h_M(X) |\NonZeroDomain_M|/|\NonZeroDomain|) \pmod{\vPoly{\NonZeroDomain}}$
};
\draw [->] (0,11.7) -- node[midway,fill=white] {commitment $\cm{h}$} (13,11.7);

\node[ralign] (verifier3) at (14.5, 10.9) {%
$\gamma \gets \F$
};
\draw [->] (12,10.9) -- (0,10.9);

\draw[dashed] (0.1,10.3) rectangle (12.9,7.8);

\node[align=center] (mid4) at (6.5, 8.9) {%
$\Verifier$ will need to check the following: \\[10pt]
$ \underbrace{{\color{gray}\vPoly{\NonZeroDomain}(\gamma)} h(\gamma)\ \   - \sum_{M \in \{A, B, C\}} {\color{gray}\delta_M \sPoly{\NonZeroDomain, \NonZeroDomain_M}(\gamma)}({\color{orange} a_M({\color{black} \gamma})} - {\color{Green4} b_M({\color{black} \gamma})} {\color{gray} (\gamma g_M(\gamma) + \sigma_M / |\NonZeroDomain_M|)})}_{\sumcheckinner(\gamma)} \stackrel{?}{=} {\color{gray} 0} $
};

\node[ralign] (verifier3) at (15.4, 6.9) {%
Compute $\x(X) \in \F^{<|x|}[X]$ from input $x$
};

\draw[dashed] (-2.7,7.4) rectangle (15.7,4.2);

\node[align=center] (mid5) at (6.5, 5.3) {%
To verify $(*)$, $\Verifier$ will compute $t := \sum_{M \in \{A, B, C\}} \eta_M \sigma_M/|\NonZeroDomain_M|$, and will need to check the following: \\[10pt]
$ \underbrace{s(\beta) + {\color{gray} v_H(\alpha, \beta)} ({\color{gray} \eta_A} \za(\beta) + {\color{gray} \eta_C\zb(\beta)} \za(\beta) + {\color{gray} \eta_B\zb(\beta)}) - {\color{gray} t\vPoly{X}(\beta)} \w(\beta) - {\color{gray} t\x(\beta)} - {\color{gray} \vPoly{\DomainA}(\beta)} h_1(\beta) - {\color{gray} \beta g_1(\beta)}}_{\sumcheckouter(\beta)} \stackrel{?}{=} 0 $
};

\node[lalign] (prover5) at (-3,2.9) {%
$v_{g_A} := g_A(\gamma), v_{g_B} := g_B(\gamma), v_{g_C} := g_C(\gamma)$ \\[3pt]
$v_{g_1} := g_1(\beta), v_{\zb} := \zb(\beta)$
};

\draw [->] (-2,1.9) -- node[midway,fill=white] {$v_{g_A}, v_{g_B}, v_{g_C} v_{g_1}, v_{\zb}$} (15,1.9);

\node[align=center] (mid7) at (6.5,0.8) {%
use $\cm{h}$, and for each $M \in \{A, B, C\}$, index commitments to $\hrow_M, \hcol_M, \hrowcol_M, \hval_M$, {\color{gray} evaluation $g_M(\gamma)$}, and {\color{gray}sum $\sigma_M$} \\
to construct virtual commitment $\vcm{\sumcheckinner}$
};

\node[align=center] (mid8) at (6.5,-0.5) {%
use commitments $\cm{\s}, \cm{\za}, \cm{\w}, \cm{h_1}$ {\color{gray} and evaluations $\zb(\beta), g_1(\beta)$ and sums $\sigma_A, \sigma_B, \sigma_C$} \\
to construct virtual commitment $\vcm{\sumcheckouter}$
};

\node[ralign] (verifier4) at (16,-1.4) {%
$\xi_1, \dots, \xi_5 \gets F$
};

\draw [->] (15,-2.1) -- node[midway,fill=white] {$\xi_1, \dots, \xi_5$} (-2,-2.1);

\node[lalign] (prover6) at (-3,-3.6) {%
use $\mathsf{PC}.\mathsf{Prove}$ with randomness $\xi_1, \dots, \xi_5$ to \\
construct a batch opening proof $\pi$ of the following: \\
$(\cm{g_A}, \cm{g_B}, \cm{g_C}, {\color{red} \vcm{\sumcheckinner}})$ at $\gamma$ evaluate to $(v_{g_A}, v_{g_B}, v_{g_C},{\color{red} 0})$ \hspace{0.3cm} ${\color{red} (**)}$ \\
$(\cm{g_1}, \cm{\zb}, \cm{t}, {\color{red} \vcm{\sumcheckouter}})$ at $\beta$ evaluate to $(v_{g_1}, v_{\zb}, {\color{red} 0})$ \hspace{0.3cm} ${\color{red} (*)}$ \\
};

\draw [->] (-2,-4.7) -- node[midway,fill=white] {$\pi$} (15,-4.7);

\node[ralign] (verifier5) at (16,-6.0) {%
verify $\pi$ with $\mathsf{PC}.\mathsf{Verify}$, using randomness $\xi_1, \dots, \xi_5$, \\
evaluations $v_{g_A}, v_{g_B}, v_{g_C}, v_{g_1}, v_{\zb}$, and \\
commitments $\cm{g_A},\cm{g_B}, \cm{g_C},\vcm{\sumcheckinner}, \cm{g_1}, \cm{\zb}, \vcm{\sumcheckinner}$
};

\end{tikzpicture}

\clearpage
\restoregeometry
}


\end{document}
