Groth16#

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.

BKSV21

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

Gro16

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.

Kil92

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

Kil95

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

Mic00

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}\).