Together with my colleagues Ryan Cao and Kunming Jiang, we re-derived the knowledge soundness of Groth16 as an entertaining exercise. Groth16 is a pairing-based ZK-SNARK. See here for an excellent tutorial on Groth16, or check out the paper itself.

R1CS & QAPs

A witness is $$ \mathbf a = (a_0,\ldots,a_\ell,a_{\ell+1},\ldots,a_m) \in \mathbb{F}^{m+1}, $$ where $a_0,\ldots,a_\ell$ are public and $a_{\ell+1},\ldots,a_m$ are private; by convention, $a_0=1$.

Constraints are expressed via $(m+1)\times n$ matrices $U,V,W$. The constraints are satisfied by $\mathbf a$ if $$\begin{equation}\label{1}\tag{1} (\mathbf a U)\circ(\mathbf a V)=\mathbf a W, \end{equation}$$ where $\circ$ is the Hadamard product (so this is an equality of vectors).

Assume that $|\mathbb{F}|\ge n$. Choose $n$ distinct field elements $\omega_j\in\mathbb{F}$, $j=1,\ldots,n$, and interpolate over the constraints to obtain polynomials $$ u_i,v_i,w_i\in\mathbb{F}[x]^{<n}, \qquad i=0,\ldots,m, $$ such that $$ u_i(\omega_j)=U_{ij},\qquad v_i(\omega_j)=V_{ij},\qquad w_i(\omega_j)=W_{ij} $$ for every $i$ and $j$. Thus, if $$ f_{\mathbf a}(x) := \left(\sum_{i=0}^{m}a_i u_i(x)\right) \left(\sum_{i=0}^{m}a_i v_i(x)\right) -\sum_{i=0}^{m}a_i w_i(x), $$ then $f_{\mathbf a}(x)\in\mathbb{F}[x]^{< 2n-1}$ for any $\mathbf a$ and $f_{\mathbf a}(\omega_j)=0$ for every $j$ if and only if \eqref{1} holds. Equivalently, $\mathbf a$ satisfies the R1CS constraints if and only if the polynomial $$ t(x):=\prod_{j=1}^{n}(x-\omega_j) $$ divides $f_{\mathbf a}$. This is the equivalence of R1CS and QAP.

Bilinear groups

The groups $G_1,G_2,G_T$ are cyclic groups of prime order $p$, written additively. The elements $g_1,g_2$ are generators of $G_1,G_2$, respectively, and $$ e:G_1\times G_2\longrightarrow G_T $$ is a bilinear map such that $e(g_1,g_2)$ is a generator of $G_T$. In particular, $\mathbb{F}=\mathbb{F}_p$ is the scalar field of the groups. Write $$ [a]_1:=a\,g_1, \qquad [a]_2:=a\,g_2, \qquad a\in\mathbb{F}. $$

Trusted setup

Choose random “trapdoor values” $$ \alpha,\beta,\gamma,\delta,\tau \xleftarrow{\$}\mathbb{F}, $$ and publish the following CRS:

In brief, $\alpha,\beta$ force the prover to use the constraints; $\gamma,\delta$ prevent the prover from using the $[\Psi_i]_1$ with $0\le i\le\ell$ (corresponding to the public inputs) in a proof; and the $[\Phi_j]_1$ are used to construct $[\delta^{-1}f_{\mathbf a}(\tau)]_1$.

Proof format

A proof is $ ([A]_1,[B]_2,[C]_1)\in G_1\times G_2\times G_1.$

Verifier checks

Given a proof $ ([A]_1,[B]_2,[C]_1)\in G_1\times G_2\times G_1$ and public witness values $a_0, \dots, a_\ell$ the verifier checks $$ e([A]_1,[B]_2) =e([\alpha]_1,[\beta]_2) +e([C]_1,[\delta]_2) +e\left(\sum_{i=0}^{\ell}a_i[\Psi_i]_1,[\gamma]_2\right),$$ accepting the proof if equality holds.

Honest prover

Sample $r,s\xleftarrow{\$}\mathbb{F}$ for zero knowledge, and set

Proof malleability

If $([A]_1,[B]_2,[C]_1)$ satisfies the verifier check, then so does $$ (\lambda[A]_1,\lambda^{-1}[B]_2,[C]_1) $$ for every $\lambda\in\mathbb{F}^{\times}$.

Knowledge soundness assumptions

It is assumed that the prover/adversary uses only “generic” operations, i.e., the group operations, the pairing operation, and equality checks. This is the generic group model (“GGM”) extended to pairings. The GGM basically says that the particular way in which group elements are symbolically represented may not be used.

In particular, any $G_1$ or $G_2$ element used by the prover/adversary is an affine combination of $G_1$ or $G_2$ elements from the CRS, respectively. Elements of $G_T$ may be quadratic because of the pairing. Call this assumption $(\ast_1)$.

It is furthermore assumed that any equation involving elements of the CRS either always holds, irrespective of the particular CRS sampled (so the equation holds “by design”), or instead holds with only negligible probability. Thus the CRS is “disclosure free” in the language of the paper. Call this assumption $(\ast_2)$.

We will show statistical knowledge soundness in the generic bilinear group model: any prover strategy involving only generic operations contains sufficient information to recover the witness values.

By $(\ast_1)$, for any proof $([A]_1,[B]_2,[C]_1)$,

for some coefficients $$ A_\alpha,A_\beta,A_\delta, A_{\Psi_i},A_{\Phi_j},A_{\tau,j}\in\mathbb{F}. $$

Moreover, by $(\ast_2)$, these coefficients are unique with overwhelming probability. For the soundness proof, however, $(\ast_2)$ is not needed at this point, since the extractor is assumed to have access to the particular coefficients used by the prover.

Similarly, $$ [C]_1=C_\alpha[\alpha]_1+\cdots \qquad\text{(with the same CRS basis as for $[A]_1$),} $$ while $$ [B]_2 =B_\beta[\beta]_2+B_\gamma[\gamma]_2+B_\delta[\delta]_2 +\sum_{j=0}^{n-1}B_{\tau^j}[\tau^j]_2. $$

Recovering the witness

First steps

Suppose that the verifier check passes. Both sides of the verifier-check equation are $e(g_1,g_2)$ multiplied by a Laurent polynomial in $\alpha,\beta,\gamma,\delta,\tau$. We proceed by comparing coefficients, writing, for example, $\mathrm{LHS}_{\alpha\beta}\in\mathbb{F}$ for the coefficient of $\alpha\beta$ on the left-hand side. For $\alpha\beta$, $$ \mathrm{LHS}_{\alpha\beta}=A_\alpha B_\beta, \qquad \mathrm{RHS}_{\alpha\beta}=1. $$ Thus $A_\alpha=B_\beta^{-1}$. By proof malleability, we may assume without loss of generality that $$ A_\alpha=B_\beta=1. $$ For $\beta^2$, $$ \mathrm{LHS}_{\beta^2}=A_\beta B_\beta, \qquad \mathrm{RHS}_{\beta^2}=0, $$ so $$ A_\beta=0. $$ For $\alpha\delta$, $$ \mathrm{LHS}_{\alpha\delta} =A_\alpha B_\delta=B_\delta, \qquad \mathrm{RHS}_{\alpha\delta}=C_\alpha, $$ so $$ C_\alpha=B_\delta. $$ For $\beta\delta$, $$ \mathrm{LHS}_{\beta\delta} =A_\beta B_\delta+A_\delta B_\beta=A_\delta, \qquad \mathrm{RHS}_{\beta\delta}=C_\beta, $$ so $$ C_\beta=A_\delta. $$ At this point we do not expect (or need, for knowledge soundness) to determine $A_\delta$ and $B_\delta$, since these are freely chosen by an honest prover as $r$ and $s$, respectively. For $\alpha\gamma$, $$ \mathrm{LHS}_{\alpha\gamma}=A_\alpha B_\gamma, \qquad \mathrm{RHS}_{\alpha\gamma}=0, $$ so $$ B_\gamma=0. $$ For $\delta\tau^j$, $$ \mathrm{LHS}_{\delta\tau^j} =A_\delta B_{\tau^j}+B_\delta A_{\tau^j}, \qquad \mathrm{RHS}_{\delta\tau^j}=C_{\tau^j}, $$ so $$ C_{\tau^j}=A_\delta B_{\tau^j}+B_\delta A_{\tau^j}. $$ For $\delta^2$, $$ \mathrm{LHS}_{\delta^2}=A_\delta B_\delta=C_\alpha C_\beta, \qquad \mathrm{RHS}_{\delta^2}=C_\delta, $$ so $$ C_\delta=C_\alpha C_\beta. $$

Deducing knowledge soundness

The coefficient of $\delta^{-1}$

Write $$ A=A_{\delta^1}\delta^1 +A_{\delta^0}\delta^0 +A_{\delta^{-1}}\delta^{-1} $$ for Laurent polynomials $A_{\delta^1},A_{\delta^0},A_{\delta^{-1}}$. Notice that all of the $A_{\Phi_j}$ and all $A_{\Psi_i}$ with $\ell < i \le m$ occur in $A_{\delta^{-1}}$. Similarly, $$ B=B_{\delta^1}\delta^1+B_{\delta^0}\delta^0, $$ where $B_{\delta^0}=\beta+\cdots$. The remaining summands cannot eliminate $\beta$, so $B_{\delta^0}\ne0$. Comparing now the $\delta^{-1}$ coefficients of the two sides of the verifier check as Laurent polynomials in the remaining variables, we have $$ \mathrm{LHS}_{\delta^{-1}} =B_{\delta^0}A_{\delta^{-1}}, \qquad \mathrm{RHS}_{\delta^{-1}}=0, $$ and hence $A_{\delta^{-1}}=0$. Thus $$ \sum_{j=0}^{n-1}A_{\Phi_j}[\Phi_j]_1 +\sum_{\ell < i\le m}A_{\Psi_i}[\Psi_i]_1 =0. $$ This is the $\delta^{-1}A_{\delta^{-1}}$ part of $[A]_1$. We did not need to show that the individual coefficients $A_{\Phi_j}$ and $A_{\Psi_i}$ are zero, although this could now be concluded using disclosure freeness.

The coefficient of $\gamma^{-1}\delta^0$

Summarizing what we know thus far, \begin{align*} A &=\alpha+A_\delta\delta +\sum_{i=0}^{\ell}A_{\Psi_i}\gamma^{-1} k_i(\alpha,\beta,\tau) +\sum_{j=0}^{n-1}A_{\tau^j}\tau^j, \\ B &=\beta+B_\delta\delta +\sum_{j=0}^{n-1}B_{\tau^j}\tau^j, \end{align*} where $A_\delta,B_\delta,B_{\tau^j}\in\mathbb{F}$ and $$ k_i(\alpha,\beta,\tau) :=\alpha v_i(\tau)+\beta u_i(\tau)+w_i(\tau).$$ Consider the $\mathbb{F}[\alpha,\beta,\tau]$-valued coefficients of $\gamma^{-1}\delta^0$. We have $$ \mathrm{LHS}_{\gamma^{-1}\delta^0} =\left(\beta+\sum_{j=0}^{n-1}B_{\tau^j}\tau^j\right) \left(\sum_{i=0}^{\ell}A_{\Psi_i} k_i(\alpha,\beta,\tau)\right). $$ The left factor is nonzero, while inspection of the verifier check gives $$ \mathrm{RHS}_{\gamma^{-1}\delta^0}=0. $$ Therefore $$ \sum_{i=0}^{\ell}A_{\Psi_i}k_i(\alpha,\beta,\tau)=0, $$ and hence $$ \sum_{i=0}^{\ell}A_{\Psi_i}[\Psi_i]_1=0. $$

Recovering the witness values

Consider $$ \mathrm{LHS}_{\alpha^1\delta^0\beta^0}, \mathrm{RHS}_{\alpha^1\delta^0\beta^0} \in\mathbb{F}[\gamma^{\pm1},\tau]. $$ We have \begin{align*} \mathrm{LHS}_{\alpha^1\delta^0\beta^0} &=\sum_{j=0}^{n-1}B_{\tau^j}\tau^j, \\ \mathrm{RHS}_{\alpha^1\delta^0\beta^0} &=\sum_{\ell < i\le m}C_{\Psi_i}v_i(\tau) +\sum_{i=0}^{\ell}a_i v_i(\tau). \end{align*} Relabel the coefficients $C_{\Psi_i}$ as $a_i$ for $\ell < i \le m$, (these correspond to the private inputs). We have shown $$ \sum_{j=0}^{n-1}B_{\tau^j}\tau^j =\sum_{i=0}^{m}a_i v_i(\tau), $$ and therefore $$ \sum_{j=0}^{n-1}B_{\tau^j}[\tau^j]_2 =\sum_{i=0}^{m}a_i[v_i(\tau)]_2. $$ Considering instead $$ \mathrm{LHS}_{\alpha^0\delta^0\beta^1}, \mathrm{RHS}_{\alpha^0\delta^0\beta^1} \in\mathbb{F}[\gamma^{\pm1},\tau], $$ it follows in the same way that $$ \sum_{j=0}^{n-1}A_{\tau^j}[\tau^j]_1 =\sum_{i=0}^{m}a_i[u_i(\tau)]_1. $$

The remaining coefficients & QAP satisfaction

Consider now $$ \mathrm{LHS}_{\alpha^0\beta^0\gamma^0\delta^0}, \mathrm{RHS}_{\alpha^0\beta^0\gamma^0\delta^0} \in\mathbb{F}[\tau]. $$ By the above, \begin{align*} A&=\alpha+A_\delta\delta+\sum_{i=0}^{m}a_i u_i(\tau), \\ B&=\beta+B_\delta\delta+\sum_{i=0}^{m}a_i v_i(\tau). \end{align*} Hence $$ \mathrm{LHS}_{\alpha^0\beta^0\gamma^0\delta^0} =\left(\sum_{i=0}^{m}a_i u_i(\tau)\right) \left(\sum_{i=0}^{m}a_i v_i(\tau)\right), $$ while \begin{align*} \mathrm{RHS}_{\alpha^0\beta^0\gamma^0\delta^0} ={}&\sum_{j=0}^{n-1}C_{\Phi_j}\tau^j t(\tau) +\sum_{\ell < i \le m}C_{\Psi_i}w_i(\tau) +\sum_{i=0}^{\ell}a_i w_i(\tau). \end{align*} Thus, after the relabeling $C_{\Psi_i}=a_i$ for $\ell< i\le m$, $$ \left(\sum_{i=0}^{m}a_i u_i(\tau)\right) \left(\sum_{i=0}^{m}a_i v_i(\tau)\right) -\sum_{i=0}^{m}a_i w_i(\tau) =\left(\sum_{j=0}^{n-1}C_{\Phi_j}\tau^j\right)t(\tau). $$ By disclosure freeness, $f_{\mathbf a} (X)$ thus divides $t(X)$ and the QAP is therefore satisfied. In particular, the prover knows the witness $$ \mathbf a =\bigl(a_0,\ldots,a_\ell, C_{\Psi_{\ell+1}},\ldots,C_{\Psi_m}\bigr), $$ whose first $\ell+1$ entries are public. This establishes knowledge soundness.