chap03-sec06.tex

% !TEX root = ../zeth-protocol-specification.tex

\section{$\zksnark$ instantiation}\label{instantiation:zksnark}

Groth's proof system $\groth$ \cite{groth2016size} is the most efficient known zk-SNARK (in terms of the proof size and proof and verification cost) for QAPs, and thus one of the most efficient $\nizk$ for proving statements on arithmetic circuits (consisting of addition and multiplication gates over a finite field $\FF$). Below we present $\groth$'s key generation, prover, verifier, and simulator algorithms, adjusted as described in \cite{bowe2017mpc} to further reduce the size of $\srs$ and proofs, and to make the $\kgen$ algorithm more amenable to implementation as a multi-party computation.

In what follows, let the number $\constno$ of constraints in the relation $\REL$ be fixed. Without loss of generality we consider $\constno$ to be an \emph{upper bound} on the number of constraints in the $\REL$ parameter, and assume that there exists some $\constno$-th root of unity $\omega \in \FFx{\rCURVE}$. Define $\ell_i(\xchi)$ to be the $i$-th Lagrange polynomial of degree $(\constno - 1)$ over the set $\smallset{\omega^i}_{i \in [\constno]}$, and let $\ell(\xchi)$ be the unique non-zero polynomial of degree $\constno$ that satisfies $\ell(\omega^i) = 0$ for all $i \in [\constno]$.

We note that the requirement that there exists a $\constno$-th root of unity $\omega$ imposes a restriction on the maximum number of constraints in $\REL$ that the scheme can support. In the particular case of $\omega \in \FFx{\rBN}$, the restriction becomes $\constno \leq 2^{28}$. For $\FFx{\rBLS}$ this becomes $\constno \leq 2^{47}$.

%% For future reference (if it becomes necessary to explain MPC details):
%%
%% ... where $\constno$ is a power of 2 such that there exists some $\constno$-th root of unity $\omega \in \FFx{\rBN}$.
%%
%% The use of the $\constno$-th root of unity supports FFT transforms for fast polynomial manipulation. The requirement that $\constno$ is a power-of-2 dividing $\rBN$ allows FFT transforms to be used for fast evaluation of Langrange polynomials at $\tau$, in terms of a series of encoded powers $\smallset{ \groupenci{\tau}{1} }_{i = 0}^{\constno - 1}$ (as described in Section 3 of "A multi-party protocol for constructing the public parameters of the Pinocchio zk-SNARK" - https://eprint.iacr.org/2017/602.pdf)

Furthermore, we denote by $\inputs \in \FF^{\inpno+1}$ the tuple of variables (i.e.~``circuit wires'') in the algebraic representation of the relation $\REL$, such that:
\begin{itemize}
    \item $\inputs_0 = 1_{\FF}$ (the multiplicative identity in $\FF$),
    \item $(\inputs_1, \ldots, \inputs_{\inpnoprim})$ represent variables in the statement,
    \item $(\inputs_{\inpnoprim+1}, \ldots, \inputs_{\inpno})$ represent variables in the witness (so-called ``auxiliary input'').
\end{itemize}
\begin{description}

%% KeyGen
\item[$\kgen(\REL, \secparam)$:]\hfill
  \begin{compactenum}[i.]
  \item Pick trapdoor $\td = (\tau, \alpha, \beta, \delta) \sample (\ZZ^*_p \setminus \smallset{\omega^{i - 1}}_{i = 1}^\constno) \times (\ZZ^*_p)^3$;
  \item For $j \in \range{0}{\inpno}$, let
    \begin{align*}
      u_j (\tau) & = \sum_{i = 1}^\constno U_{i j} \ell_i (\tau), \\
      v_j (\tau) & = \sum_{i = 1}^\constno V_{i j} \ell_i (\tau), \\
      w_j (\tau) & = \sum_{i = 1}^\constno W_{i j} \ell_i (\tau);
    \end{align*}
  \item Set
    \begin{align*}
      \srs_\prover \gets &
      \left(
      \begin{aligned}
        & \groupenci{\alpha}{1}
        , \groupenc{\beta}
        , \groupenc{\delta}
        , \smallset{ \groupenci{ u_j(\tau) }{1} }_{j = 0}^{\inpno}
        , \smallset{ \groupenc{ v_j(\tau) } }_{j = 0}^{\inpno}
        , \\
        & \smallset{
          \groupenci{(u_j (\tau) \beta + v_j (\tau) \alpha + w_j (\tau)) /\delta}{1}
        }_{j = \inpnoprim + 1}^\inpno
        , \\
        & \smallset{
          \groupenci{\tau^i \ell (\tau) / \delta}{1}
        }_{i = 0}^{\constno - 2}
      \end{aligned}
      \right) \\
      \srs_\verifier \gets &
      \left(
      \begin{aligned}
        & \groupenci{\alpha}{1}
        , \groupenci{\beta}{2}
        , \groupenci{\delta}{2}
        , \smallset{
          \groupenci{ \beta u_j(\tau) + \alpha v_j(\tau) +w_j }{1}
        }_{j = 0}^{\inpnoprim}
      \end{aligned}
      \right) \\
      \srs \gets & (\srs_\algostyle{P}, \srs_\algostyle{V})
    \end{align*}
  \end{compactenum}
  \pcreturn $\srs, \td$

%% Prover
\item[$\prover(\REL, \srs_\prover, \priminputs  = (\inputs_j)_{j = 1}^{\inpnoprim}, \auxinputs = (\inputs_j)_{j = \inpnoprim + 1}^{\inpno})$:]\hfill
  \begin{compactenum}[i.]
  \item
    Define
    \begin{align*}
      a^\dagger (\xchi) = \sum_{j = 0}^\inpno \inputs_j u_j (\xchi),\ \
      b^\dagger (\xchi) = \sum_{j = 0}^\inpno \inputs_j v_j (\xchi),\ \
      c^\dagger (\xchi) = \sum_{j = 0}^\inpno \inputs_j w_j (\xchi);
    \end{align*}
  \item
    Define the polynomial $\HHH (\xchi) = (a^\dagger (\xchi) b^\dagger (\xchi) - c^\dagger (\xchi)) / \ell (\xchi)$ and compute the coefficients $\smallset{ \HHH_i }_{i = 0}^{\constno - 2}$ of $\HHH$, such that $\HHH(X) = \sum_{i = 0}^{\constno - 2} \HHH_i \xchi^i$.
  \item
    $r_a \sample \ZZ_p$;
  \item
    $r_b \sample \ZZ_p$;
  \item Compute proof elements:
    \begin{align*}
      \AAA \gets & \sum_{j = 0}^\inpno \inputs_j \groupenci{u_j (\tau)}{1} + \groupenci{\alpha}{1} + r_a \groupenci{\delta}{1} \\
      \BBB \gets & \sum_{j = 0}^\inpno \inputs_j \groupenci{v_j (\tau)}{2} + \groupenci{\beta}{2} + r_b \groupenci{\delta}{2} \\
      \CCC \gets & \sum_{j = \inpnoprim + 1}^\inpno \inputs_j \groupenci{\frac{u_j (\tau) \beta + v_j (\tau) \alpha + w_j (\tau)}{\delta}}{1} + \sum_{i=0}^{\constno - 2} \HHH_i \groupenci{\tau^i \ell (\tau) / \delta}{1} + \\
        &  r_b \AAA + r_a \brak{\sum_{j = 0}^\inpno \inputs_j \groupenci{v_j (\tau)}{1} + \groupenci{\beta}{1} + r_b \groupenci{\delta}{1}} - r_a r_b \groupenci{\delta}{1}
    \end{align*}
  \end{compactenum}
  \pcreturn $\pi \gets (\AAA, \BBB, \CCC)$;

%% Verifier
\item[$\verifier (\REL, \srs_\verifier, \priminputs = (\inputs_j)_{j = 1}^{\inpnoprim}, \pi)$:]\hfill
  \begin{compactenum}[i.]
  \item Check that:
    \begin{align*}
      \AAA \pair \BBB = & \CCC \pair \groupenci{\delta}{2} \\
      & + \brak{\sum_{j = 0}^{\inpnoprim} \inputs_j  \groupenci{u_j (\tau) \beta + v_j (\tau) \alpha + w_j (\tau)}{1}} \pair \groupenci{1}{2} \\
      & + \groupenci{\alpha}{1} \pair \groupenci{\beta}{2}
    \end{align*}
  \end{compactenum}
  Note that $\groupenci{\alpha}{1}$ and $\groupenci{\beta}{2}$ are stored individually and used by the prover to recompute $\groupenci{\alpha \beta}{T}$ seemingly redundantly. This is required in order to leverage the pairing check functionality built in to \ethereum, which accepts a sequence of tuples in $\gset_1 \times \gset_2$ and returns $\true$ if and only if the product of the resulting pairings equals $\groupenci{1}{T}$.

%% Simulator
\item[$\simulator(\REL, \srs, \td, \priminputs)$:]\hfill
  \begin{compactenum}[i.]
  \item Sample $a \sample \ZZ_p$; $b \sample \ZZ_p$;
  \item Compute proof elements:
    \begin{align*}
      & \AAA \gets \groupenci{a}{1}\\
      & \BBB \gets \groupenci{b}{2}\\
      & \CCC \gets \frac{1}{\delta} \cdot
    %    \left( a b \groupenci{1}{1} - \beta \groupenci{\alpha}{1} 
    %     - \sum_{j = 0}^{\inpnoprim} \inputs_j \groupenci{ u_j (\tau) \beta + v_j (\tau) \alpha + w_j (\tau)}{1} \right)
        \left( a b - \alpha \beta  
        - \sum_{j = 0}^{\inpnoprim} \inputs_j  (u_j (\tau) \beta + v_j (\tau) \alpha + w_j (\tau)) \right) \groupenci{1}{1}
    \end{align*}
  \end{compactenum}
  \pcreturn $\pi \gets (\AAA, \BBB, \CCC)$;
\end{description}