GGPR

Source: Proofs, Arguments, and Zero-Knowledge, Section 17.4

A linear PCP, for satisfiability of an R1CS instance (in this presentation), i.e., there is a witness $z\in {\mathbb{F}}^S$ such that

$$Az\circ Bz=Cz$$

where $A,B,C\in {\mathbb{F}}^{l\times S}$ are fixed matrices.

Let $H:=\{{\sigma }_1,...,{\sigma }_l\}$ be a set of elements in $\mathbb{F}$ (for example, a multiplicative subgroup). Then, we can interpolate univariate polynomials $A_j,B_j,C_j$ that map ${\sigma }_i$ to entry $(i,j)$ of the respective matrix. In other words, $M_j$ interpolates column $j$ of matrix $M$.

Then, the following polynomial is zero on all ${\sigma }_i\in H$ iff. $z$ is a valid witness:

$$g_z(t):=\left(\sum _{j\in \{1,...,S\}}{z}_j\cdot A_j(t)\right)\cdot \left(\sum _{j\in \{1,...,S\}}{z}_j\cdot B_j(t)\right)-\left(\sum _{j\in \{1,...,S\}}{z}_j\cdot C_j(t)\right)$$

This can be validated using the Univariate Zero-Check Protocol, which requires the prover to commit to a univariate polynomial $h^{\ast }$ such that $g_z={\mathbb{Z}}_H\cdot h^{\ast }$. The verifier than asks for an evaluation of both at a random point $r$.

The prover commits to linear functions ${\mathbb{F}}^S\to \mathbb{F}$:

• $f_{coeff(h^{\ast })}$: the vector of coefficients of $h^{\ast }$
• $f_z$: The vector $z$

Then, the verifier can:

• Evaluate $g_z(r)$ by querying $f_z$ at the vectors
  • $q^{(1)}=(A_1(r),...,A_S(r))$
  • $q^{(2)}=(B_1(r),...,B_S(r))$
  • $q^{(3)}=(C_1(r),...,C_S(r))$
• Evaluate $h^{\ast }(r)$ by querying $f_{coeff(h^{\ast })}$ at $q^{(4)}=(1,r,r^2,...,r^S)$

Linear Interactive Proof (LIP) vs. linear PCP:

• When querying the same polynomial using queries $q^{(1)},...,q^{(k)}$, a LIP ensures that all queries are answered using the same linear function
• We can add query $q^{(k+1)}={\sum }_{i=1}^k{\beta }_i{q}^{(i)}$ for randomly chosen ${\beta }_i$
• Given answers $a_1,...,a_{k+1}$, the verifier accepts iff. $a_{k+1}={\sum }_{i=1}^k{\beta }_i{a}_i$

⇒ We add $q^{(5)}={\sum }_{i=1}^3{\beta }_i{q}^{(i)}$

SRS: For a randomly chosen $\alpha$ and each $i=1,...,5$ and $j=1,...,S$, the SRS contains the pair $(g^{q_j^{(i)}},g^{\alpha q_j^{(i)}})$. (Only depends on the circuit!)

Verification key: $(g,g^{\alpha },g^{{\mathbb{Z}}_H(r)},g^{{\beta }_1},g^{{\beta }_2},g^{{\beta }_3})$

Proof: Using the SRS and additive homomorphism, the prover computes:

• $(g_1,g_1^{\prime }):=(g^{f_z(q^{(1)})},g^{\alpha \cdot f_z(q^{(1)})})$
• $(g_2,g_2^{\prime }):=(g^{f_z(q^{(2)})},g^{\alpha \cdot f_z(q^{(2)})})$
• $(g_3,g_3^{\prime }):=(g^{f_z(q^{(3)})},g^{\alpha \cdot f_z(q^{(3)})})$
• $(g_4,g_4^{\prime }):=(g^{f_{coeff(h^{\ast })}(q^{(4)})},g^{\alpha \cdot f_{coeff(h^{\ast })}(q^{(4)})})$
• $(g_5,g_5^{\prime }):=(g^{f_z(q^{(5)})},g^{\alpha \cdot f_z(q^{(5)})})$

Verification:

• $e(g_1,g_2)=e(g_3,g)\cdot e(g^{{\mathbb{Z}}_H(r)},g_4)$
  • Verifies that $g(t)$ vanishes on $H$!
• ${\prod }_{i=1}^{3}e(g^{{\beta }_i},g_i)=e(g_5,g)$
  • The verification from the LIP above
• For $i=1,...,5$: $e(g_i,g^{\alpha })=e(g,g_i^{\prime })$
  • Under the Knowledge of Exponent Assumption (KEA), this ensures that the prover actually knows the exponents of the sent values

Question: How is it possible that there is nothing circuit-specific in the verification algorithm & verification key?!

• $g^{{\mathbb{Z}}_H(r)}$ is used in the verification, so it’s specific to the setup
• The prover could not have used different values for $q^{(1)}$, $q^{(2)}$, $q^{(3)}$, and $q^{(5)}$ (corresponding to a different circuit), because that would require knowing $r$

Public inputs: This is a subset of $z$. The prover can simply commit to the other parts of $z$, while the verifier computes the contribution of the public input on its own. For this, $g^{q_j^i}$ needs to be part of the verification key (but not $g^{\alpha q_j^i}$; this was the bug Ariel Gabizon found in the BCTV14 paper and ZCash!)

Achieving Zero Knowledge (sketch): The prover can pick random values $r_A,r_B,r_C\in \mathbb{F}$ and apply the protocol to:

$$g_z^{\prime }(t):=(A(t)+r_A{\mathbb{Z}}_H(t))\cdot (B(t)+r_B{\mathbb{Z}}_H(t))-(C(t)+r_C{\mathbb{Z}}_H(t))$$

The rest of the protocol can be modified accordingly.

Groth16: Very influential variant of this SNARK which reduces the size of the proof from 10 to 3 group elements by:

• Introducing a LIP that makes 3 queries instead of 5
• Relying on the Algebraic Group Model instead of KEA, so all the $g_i^{\prime }$ elements aren’t needed anymore