We briefly describe the trusted-setup zkSNARK scheme defined in [Gro16]

Groth16 Scheme#

Algorithm 1 (\((\sigma, \tau) \leftarrow \operatorname{Setup}(R)\))

\[\begin{split} \begin{gathered} \alpha, \beta, \gamma, \delta, x \leftarrow \mathbb{Z}_{p}^{*}\\ \tau=(\alpha, \beta, \gamma, \delta, x)\\ \boldsymbol{\sigma}_{1}=\left(\begin{array}{l} \alpha, \beta, \delta,\left\{x^{i}\right\}_{i=0}^{n-1},\left\{\frac{\beta u_{i}(x)+\alpha v_{i}(x)+w_{i}(x)}{\gamma}\right\}_{i=0}^{\ell} \\ \left\{\frac{\beta u_{i}(x)+\alpha v_{i}(x)+w_{i}(x)}{\delta}\right\}_{i=\ell+1}^{m},\left\{\frac{x^{i} t(x)}{\delta}\right\}_{i=0}^{n-2} \end{array}\right) \\ \boldsymbol{\sigma}_{2}=\left(\beta, \gamma, \delta,\left\{x^{i}\right\}_{i=0}^{n-1}\right) \\ \boldsymbol{\sigma}=\left(\left[\boldsymbol{\sigma}_{1}\right]_{1},\left[\boldsymbol{\sigma}_{2}\right]_{2}\right) \end{gathered} \end{split}\]

Algorithm 2 (\(\pi \leftarrow \operatorname{Prove}\left(R, \sigma, a_{1}, \ldots, a_{m}\right)\))

\[\begin{split} \begin{gathered} A=\alpha+\sum_{i=0}^{m} a_{i} u_{i}(x)+r \delta \\ B=\beta+\sum_{i=0}^{m} a_{i} v_{i}(x)+s \delta \\ C=\frac{\sum_{i=\ell+1}^{m} a_{i}\left(\beta u_{i}(x)+\alpha v_{i}(x)+w_{i}(x)\right)+h(x) t(x)}{\delta}+A s+B r-r s \delta \\ \pi=\left([A]_{1},[C]_{1},[B]_{2}\right) \end{gathered} \end{split}\]

Algorithm 3 (\(0 / 1 \leftarrow \operatorname{Vfy}\left(R, \sigma, a_{1}, \ldots, a_{\ell}, \pi\right)\))

\[ [A]_{1} \cdot[B]_{2}=[\alpha]_{1} \cdot[\beta]_{2}+\sum_{i=0}^{\ell} a_{i}\left[\frac{\beta u_{i}(x)+\alpha v_{i}(x)+w_{i}(x)}{\gamma}\right]_{1} \cdot[\gamma]_{2}+[C]_{1} \cdot[\delta]_{2} \]

Algorithm 2

By Theorem 3 in [BKSV21] , the output of Rerand is statistically indistinguishable from a fresh proof of the same underlying statement.

Proofs for Groth16#

We now have four different proofs for Groth16.

(According to Mary Maller’s talk at zkSummit )

Previous Work#

  • [Kil92] gave the first sublinear communication zero-knowledge argument that sends fewer bits than the size of the statement to be proved.

  • [Mic00] proposed sublinear size arguments by letting the prover in a communication efficient argument compute the verifier’s challenges using a cryptographic function,

    • (as re-marked in [Kil95]) this leads to sublinear size NIZK proofs when the interactive argument is public coin and zero-knowledge.


Karim Baghery, Markulf Kohlweiss, Janno Siim, and Mikhail Volkhov. Another look at extraction and randomization of groth's zk-snark. In Financial Cryptography. 2021.


Jens Groth. On the size of pairing-based non-interactive arguments. In Marc Fischlin and Jean-Sébastien Coron, editors, Advances in Cryptology – EUROCRYPT 2016, 305–326. Berlin, Heidelberg, 2016. Springer Berlin Heidelberg.


Joe Kilian. A note on efficient zero-knowledge proofs and arguments (extended abstract). In STOC '92. 1992.


Joe Kilian. Improved efficient arguments (preliminary version). In CRYPTO. 1995.


Silvio Micali. Computationally sound proofs. SIAM J. Comput., 30:1253–1298, 2000.

Algorithm 4 (PROVE-EQUAL-NAIVE \(\left(x_{i}, x_{j}\right)\) )

Prove that \(x_{i}=x_{j}\)

  1. \(P\) sends \(V\) the value \(v = x_{i}^{0} \oplus x_{j}^{0}\).

  2. \(V\) uniformly chooses \(b \in\{0,1\}\), and sends \(b\) to \(P\).

  3. \(P\) reveals \(x_{i}^{b}\) and \(x_{j}^{b}\), who accepts iff \(x_{i}^{b} \oplus x_{j}^{b}=v\).

when you refers to Groth16 scheme.

Non-interactive Linear Proofs (NILP)#

Algorithm 5 (\((\boldsymbol{\sigma}, \boldsymbol{\tau}) \leftarrow \operatorname{Setup}(R)\))

\(\boldsymbol{\sigma} \in \mathbb{F}^{m}\) and \(\boldsymbol{\tau} \in \mathbb{F}^{n}\)

Algorithm 6 (\(\boldsymbol{\pi} \leftarrow \operatorname{Prove}(R, \boldsymbol{\sigma}, \phi, w)\))

  1. \(\Pi \leftarrow \operatorname{ProofMatrix}(R, \phi, w)\), \(\Pi \in \mathbb{F}^{k \times m}\).

  2. \(\boldsymbol{\pi}=\Pi \boldsymbol{\sigma}\)

Algorithm 7 (\(0 / 1 \leftarrow \operatorname{Vfy}(R, \boldsymbol{\sigma}, \phi, \pi)\))

  1. \(t \leftarrow \operatorname{Test}(R, \phi)\) , where \(\boldsymbol{t}: \mathbb{F}^{m+k} \rightarrow \mathbb{F}^{\eta}\)

  2. accepts the proof iff \(\boldsymbol{t}(\boldsymbol{\sigma}, \boldsymbol{\pi})=\mathbf{0}\).