tl;dr: Groth16 is one of the most popular general-purpose zkSNARK schemes. Although Groth16 is slower to prove than more recent zkSNARKs, it has the smallest proof size and the fastest verification time. This probably explains why it has seen such wide adoption in the cryptocurrency space. (Recently, WHIR¹ could hope to challenge its verifier efficiency.) Groth16 requires a relation-specific trusted setup, making it more difficult to use in production systems.

Introduction

Groth16² remains one of the most popular ZKP systems today. But why? Groth16 offers a pretty-sweet trade-off: it boasts reasonably-fast proving times while offering extremely-short proofs (128 to 192 bytes) that are super-fast to verify (1.2 milliseconds).

Groth16 has many other nice properties too:

1. Its proofs are re-randomizable, which is useful for privacy use cases.
2. Its proofs can be verified against commitments to the public inputs.
3. Its proofs can be batch-verified and aggregated³.
4. It admits an efficient MPC protocol to distribute its trusted setup phase.
5. It allows for proof simulation, which makes development and testing easier.

Unfortunately, Groth16 requires a trusted setup to generate a relation-specific proving key (see Eq. \ref{eq:groth16-prk}). The setup is said to be “trusted” in the sense that it must discard some secret trapdoor information. Otherwise, anyone with knowledge of the trapdoor could forge a proof for any statment without necessarily having a witness for it.

Brief history

Gennaro et al.⁴ introduced the notion of quadratic arithmetic programs (QAPs) and built the first highly-succinct ZKP without PCPs, with a linear common-reference string (CRS) and a quasilinear prover time. In the process, they also defined the notion of a strong QAP which guaranteed that, if satisfiable, it must be via the same witness $\vec{a}$ across the three polynomials $\gu_j,\rv_j,\bw_j$ (see Eq. \ref{eq:rel-qap}). They showed that any QAP can be converted into a strong QAP (although at the cost of more than tripling the # of polynomials $m$). Then, they built a ZKP for strong QAP satisfiability.

Parno et al.⁵ quickly observed that regular QAPs are sufficient for building an efficient ZKP and gave a new, simpler construction called Pinocchio. Trinocchio⁶ provided a way to outsource proving to three or more workers without leaking the secret witness to them. Geppetto⁷ introduced multi QAPs as a way to reduce prover cost by “sharing state” between computations, especially MapReduce-style ones.

Groth² improved upon Pinocchio’s efficiency by (1) more efficiently-instantiating a linear interactive proof (LIP) that uses 3 (instead of 4) field elements, (2) “compiling” it into a zkSNARK more aggresively in the generic group model (GGM)⁸ instead of relying on knowledge-of-exponent (KoE) assumptions which tend to double the commitment cost and (3) relying on asymetric pairing-friendly groups instead of symmetric ones.

Since its introduction in 2016, Groth’s scheme has been colloquially referred to as Groth16 and deployed widely due to its verifier efficiency and reasonable proving times.

Bowe, Gabizon and Miers [BGM17]⁹ gave an efficient, player-exchangeable, multi-party computation (MPC) protocol for performing the trusted setup of Groth16 such that, as long as one player is honest, nobody learns the trapdoor. In 2018, Zcash successfully used this MPC protocol amongst ~200 participants to securely set up their new Groth16-based ZKP¹⁰.

Kohlweiss et al.¹¹ improved upon [BGM17] by proving that there is no need for a last public contribution from a randomness beacon.

Preliminaries

Notation and background

Notation:

• $n$ typically denotes the QAP degree (i.e., the # of multiplication gates)
• $m$ typically denotes the QAP size
• $\omega$ typically denotes a primitive $n$th root of unity in a finite field $\F$
• $\lagr_i(X) = \prod_{j\in [0,n), j\ne i} \frac{X - \omega^j}{\omega^i - \omega^j}$ denotes the $i$th Lagrange polynomial
• $a \concat b$ denotes concatenation, whether of vectors or of strings

We assume sufficient mathematical background:

• Basic linear algebra:
  • Vector dot products, matrix-vector multiplication, and Hadamard products
• Polynomials:
  • See basics here
  • See how to interpolate a polynomial here
  • Fast Fourier Transforms (FFTs) in finite fields with a primitive $n$th root of unity

We also assume sufficient cryptography background:

• Abelian groups that admit bilinear maps.
• Pedersen commitments
• KZG polynomial commitments
• Definitions of zero-knowledge proofs
• Quadratic arithmetic programs (QAPs): representations of arithmetic circuits (see here)
  • An alternative formulation of QAPs is R1CS, but this blog post uses QAPs.

Pairing-friendly groups

Assume $G_1, G_2$ are generators for bilinear groups $\Gr_1,\Gr_2$ of prime order $p$ that admit a pairing $e :\Gr_1 \times\Gr_2\rightarrow\Gr_T$.

Here, $\Gr_T$ is the target group, also of order $p$ with generator $G_T=\pair{G_1}{G_2}$

We use additive group notation: \begin{align} a \cdot G_1 \bydef a G_1 \bydef \underbrace{G_1 + G_1 + \ldots + G_1}_{a\ \text{times}},\ \text{where}\ a\in \F=\Zp \end{align} (Of course, $b G_2$ is similarly-defined.)

For ease of notation, for any $a,b,c\in \F$, we use the following: \begin{align} \one{a} \bydef a \cdot G_1\in\Gr_1\\
\two{b} \bydef b \cdot G_2\in\Gr_2\\
\three{c} \bydef c \cdot G_T\in\Gr_T \end{align}

Note that the identity elements in the groups will be $\one{0},\two{0}$ and $\three{0}$.

No matter what group $i\in\{1,2,\top\}$ we are using, we have $\forall a,b,c\in \F$: \begin{align} \left[a\right]_i + \left[b\right]_i &= \left[a+b\right]_i\\
c\left[a\right]_i &= \left[ca\right]_i \end{align}

We use Type 3 pairings, which means we can efficiently check useful properties like: \begin{align} \pair{\one{a}}{\two{b}} &= \three{ab}\\
\pair{\one{a}}{G_2} &= \pair{G_1}{\two{a}} \end{align}

We use $\bp \bydef (\Gr_1,\Gr_2,\Gr_T, p, G_1,G_2, e)$ to denote the bilinear group. For clarity, when an algorithm $\mathsf{Alg}$ needs to be aware of the group generators $G_1, G_2$ we write it as $\mathsf{Alg}_\bp$. As an example, the $\grothVerify$ proof verification algorithm does not actually need to be aware of the generators $G_1$ and $G_2$ while the $\grothSetup_\bp$ algorithm does. So we subscript the latter with $\bp$.

QAPs

We fully-cover QAPs in a separate blog post but, for completeness, we give minimum background on them here.

Let’s recall two basic facts:

1. Groth16 is a ZKP for the satisfiability of any NP relation $R$: i.e., it proves knowledge of a secret witness $\witn$ such that $R(\stmt; \witn) = 1$ for a public statement $\stmt$
2. Any NP relation $R$ can be re-written as a quadratic arithmetic program (QAP): a set of polynomials $(\gu_j(X),\rv_j(X),\bw_j(X))_{i\in[0,m]}$ of degree $n-1$ each.

Like the original paper², this blog post describes Groth16 as a ZKP for the QAP satisfiability relation:

\begin{align} \label{eq:rel-qap} \relqap=\left\{ \begin{array}{c|c} (\stmt,\witn) & \begin{array}{l} \vec{a} \bydef (1,\underbrace{a_1,a_2,\ldots,a_\ell}_\stmt,\underbrace{a_{\ell+1},a_{\ell+2},\ldots,a_m}_\witn)^\top \in \F^{m+1}\\
\sum_{j=0}^m \gu_j(X) a_j \cdot \sum_{j=0}^m \rv_j(X) a_j \equiv \sum_{j=0}^m \bw_j(X) a_j \bmod X^n - 1 \end{array} \end{array}\right\} \end{align}

All $\gu_j, \rv_j, \bw_j$ polynomials are of degree-bound $n$ (i.e., their degree $\le n-1$). The degree of the QAP is said to be $n$. The size of the QAP is said to be $m$.

Also, recall that the main tool in proving QAP satisfiability is arguing existence of a quotient polynomial $h(X)$ of degree $n-2$ such that: \begin{align} \label{eq:qap-quotient} \sum_{j=0}^m \gu_j(X) a_j \cdot \sum_{j=0}^m \rv_j(X) a_j &= \sum_{j=0}^m \bw_j(X) a_j + h(X) (X^n - 1) \end{align}

To prove your application-specific relation $R$, you must first convert it to a QAP. Although this is beyond the scope of this blog post, typically, developers use domain-specific languages (DSLs) like circom or Noir to specify their relation $R$. Then, these DSLs can “compile” $R$ to R1CS and thus to a QAP.

The Groth16 protocol

The Groth16 protocol follows below. At first, it may seem overwhelming. But, later on, we at least explain why correctness holds.

It is useful to recall our notation for group elements and for Lagrange polynomials $\lagr_i(X)$.

$\mathsf{Groth16.Setup}_\mathcal{G}(1^\lambda, R) \Rightarrow (\mathsf{prk},\vk,\td)$

Setting up a Groth16 ZKP system for proving the satisfiability of an NP relation $R$ involves three steps.

First, pick the random trapdoor: \begin{align} \label{eq:groth16-trapdoor} \td\gets \left(\begin{array} % \tau, \alpha,\beta, \delta, \gamma \end{array}\right)\randget\F^5 \end{align}

Second, given the degree-$n$ QAP for $R$ as polynomials $(\gu_j(X),\rv_j(X),\bw_j(X))_{i\in[0,m]}$ and this trapdoor, compute the proving key: \begin{align} \label{eq:groth16-prk} \prk \gets \left( \begin{array} % % \alphaOne,\betaOne,\betaTwo,\deltaOne,\deltaTwo \\
% \left( \ujc, \vjc \right)_{j\in[0,m]}, % \left( \vvjc \right)_{j\in[0,m]}\\
% \left( \uvwDeltaOne \right)_{j\in[\ell+1,m]}\\
% \left( \htaus \right)_{i\in[0,n-2]} \end{array}\right) \end{align}

Third, derive the verification key (VK), which overlaps a little with the proving key (i.e., they share some $\alpha,\beta$ and $\delta$ commitments such as $\deltaTwo$): \begin{align} \label{eq:groth16-vk} \vk \gets \left( \begin{array} % \alphaOne,\betaTwo,\gammaTwo,\deltaTwo\\
% \left( \uvwGammaOne \right)_{j\in[0,\ell]} \end{array}\right) \end{align}

Our proving key differs from the original paper² slightly. First, it contains commitments to QAP polynomials $\gu_j, \rv_j$ instead of the $\one{\tau^i}$ and $\two{\tau^i}$ commitments. Second, it contains $\htaus$ instead of $\crs{\one{\frac{\tau^i(\tau^n - 1)}{\delta}}}$. We do this (1) for clarity of exposition and (2) to showcase what an efficient implementation would actually employ as its proving key.

$\mathsf{Groth16.Prove}(\mathsf{prk}, \mathbf{x}; \mathbf{w}) \Rightarrow \pi$

To create a proof for a vector $\vec{a} \bydef 1\concat\stmt\concat\witn$ satisfying the QAP in Eq. \ref{eq:rel-qap}, the prover samples random $r,s\in \F$ and uses the proving key from Eq. \ref{eq:groth16-prk} to compute: \begin{align} \label{eq:groth16-a} \one{A} &\gets \alphaOne + r\deltaOne + \sum_{j=0}^m a_j \ujc\\
\label{eq:groth16-b} \two{B} &\gets \betaTwo + s\deltaTwo + \sum_{j=0}^m a_j \vvjc \end{align}

Suppose we have computed the quotient polynomial $h(X)=\sum_{i=0}^{n-2} h(\omega^i) \lagr_i(\tau)$ from Eq. \ref{eq:qap-quotient}. (We describe how later on.) Then, the last component of the proof is:

\begin{align} \label{eq:groth16-c} \one{C} &\gets \sum_{j=\ell+1}^m a_j \uvwDeltaOne + \sum_{i=0}^{n-2} h(\omega^i) \htaus + s\one{A} + r\one{B} - rs\deltaOne \end{align} The final proof is $\pi\gets(\one{A},\two{B},\one{C})\in\Gr_1\times\Gr_2\times\Gr_1$.

Prover time

The prover’s time complexity is dominated by:

1. A size-$(m + 1)$ multi-($\green{\textsf{small}}$-)scalar multiplication for $\one{A}$.
2. A size-$(m+1)$ multi-($\green{\textsf{small}}$-)scalar multiplication for $\two{B}$.
3. Another size-$(m+1)$ multi-($\green{\textsf{small}}$-)scalar multiplication for $\one{B}$.
4. A size-$(m-\ell)$ multi-($\green{\textsf{small}}$-)scalar multiplication for the witness-component of $\one{C}$.
5. A size-$(n-1)$ multi-($\red{\textsf{large}}$-)scalar multiplication for the $h(X)$ component of $\one{C}$.
6. 6 size-$n$ FFTs over $\F$ for computing $h(X)$. (Currently, this is the best-known algorithm.)

Multi-scalar multiplications (MSMs) with “small” scalars (e.g., the $a_j$’s) are computed separately from MSMs with “large” scalars. Otherwise, mixing the two in a single MSM would actually be slower, at least for MSM algorithms like Pippenger whose performance depends on a window size which in turn depends on the max scalar size.

Computing $h(X)$

Typically, the most efficient approach of computing $h(X)$ is known as Jordi’s trick (by Jordi Baylina), which only uses 6 size-$n$ FFTs. Kobi Gurkan described this nicely in a blog post¹².

In this blog post, I’ll describe (what I think is) a simpler method based on polynomial differentiation, which is used quite often in the literature¹³$^,$¹⁴$^,$¹⁵. As shown recently, this method is slightly faster and requires a smaller set of roots of unity¹⁶.

First, to simplify notation, denote: \begin{align} \label{eq:uvw-polys} \gu(X) &\bydef \sum_{j=0}^m \gu_j(X) a_j\\
\rv(X) &\bydef \sum_{j=0}^m \rv_j(X) a_j\\
\bw(X) &\bydef \sum_{j=0}^m \bw_j(X) a_j \end{align} Then, rewrite Eq. $\ref{eq:qap-quotient}$ as: \begin{align} \gu(X) \rv(X) &= \bw(X) + h(X)(X^n - 1)\Leftrightarrow\\
\label{eq:uv-w} \gu(X) \rv(X) - \bw(X) &= h(X)(X^n - 1)\Leftrightarrow\\
\label{eq:hx-fraction} h(X) &= \frac{\gu(X) \rv(X) - \bw(X)}{X^n - 1} \end{align}

Our goal will be to compute all $h(\omega^i)$ so that we can substitute them in Eq. $\ref{eq:groth16-c}$ when computing $\one{C}$. Unfortunately, the $h(X)$ formula from Eq. $\ref{eq:hx-fraction}$ above does not help us do this: even though we can compute the numerator $\gu(\omega^i)\rv(\omega^i) - \bw(\omega^i)$ efficiently, the denominator $X^{n-1}$ is 0 when $X = \omega^i$. Fortunately, we can apply some differentiation tricks:

$\forall f,g,h\in\F[X]$ such that $f(x) = g(X)h(X)$ and $g(\omega^i) = 0$, we have $f’(\omega^i) = g’(\omega^i) h(\omega^i)$.

(We give a proof here.)

Applying this theorem, denote the numerator and denominator of $h(X)$ in Eq. \ref{eq:hx-fraction} by $f(X)$ and $g(X)$, respectively, and differentiate them: \begin{align} f’(X) &\bydef \left(\gu(X) \rv(X) - \bw(X))\right)’ = \left(\gu’(X)\rv(X)+\gu(X)\rv’(X)−\bw’(X)\right)\\
g’(X) &\bydef \left(X^n - 1\right)’ = nX^{n-1} \end{align} As a result, we have a closed-form formula for all $h(\omega^i)$’s: \begin{align} \label{eq:hx-diff-formula} h(\omega^i) &= \frac{f’(\omega^i)}{g’(\omega^i)} = \frac{u’(\omega^i)\rv(\omega^i)+\gu(\omega^i)v’(\omega^i)−w’(\omega^i)}{n\omega^{i(n-1)}},\forall i\in[0,n-2] \end{align}

Now, let’s see how fast we can compute all $h(\omega^i)$’s. The main computational challenge will be efficiently evaluating the derivatives $u’(X), v’(X)$ and $w’(X)$ at all the roots of unity $\omega^i$.

Let’s consider computing all $u’(\omega^i), \forall i\in[0,n)$:

1. We can do one inverse size-$n$ FFT to compute $u(X) = \prod_{i\in[0,n)} c_i \cdot X^i$ in “monomial basis”
2. Then, we can easily differentiate and obtain $u’(X) = \prod_{i\in[1,n)} i \cdot c_i\cdot X^{i-1}$, also in “monomial basis”
3. Lastly, we can do a size-$n$ FFT to compute $u’(\omega^i),\forall i\in[0,n-2]$

So, using 6 FFTs of size $n$ each, we can evaluate the $u’(X), v’(X)$ and $w’(X)$ derivatives!

Thus, the total amount of work to obtain all $h(\omega^i),\forall i\in[0,n-2]$ evaluations as per Eq. $\ref{eq:hx-diff-formula}$ will be:

1. Denominator: The $n\omega^{i(n-1)} = n\omega^{in - i}=n\omega^{-i}$ denominators from Eq. $\ref{eq:hx-diff-formula}$ can all be pre-computed in $O(n)$ field multiplications.
2. Numerator:
   • The $\gu’(\omega^i), \rv’(\omega^i)$ and $\bw’(\omega^i)$ derivative evaluations require 6 size-$n$ FFTs, as discussed above.
   • The $\gu(\omega^i), \rv(\omega^i)$ and $\bw(\omega^i)$ evaluations can all be computed in $O(n)$ field operations as per Eq. \ref{eq:uvw-polys}.
     • Why? The QAP polynomials $\gu_j,\rv_j,\bw_j$ are “sparse”: all together, they only interpolate $O(n)$ non-zero entries

$\mathsf{Groth16.Verify}(\vk, \mathbf{x}; \pi) \Rightarrow \{0,1\}$

Let $\alphabeta\bydef \pair{\alphaOne}{\betaTwo}$ be precomputed as part of post-processing the VK from Eq. $\ref{eq:groth16-vk}$.

To verify a proof for the public statement $\stmt=(a_1,\ldots,a_\ell)$, with $a_0 = 1$, check that: \begin{align} \pair{\one{A}}{\two{B}} \equals \alphabeta + \pair{\sum_{j=0}^\ell a_j \uvwGammaOne}{\gammaTwo} + \pair{\one{C}}{\deltaTwo} \end{align}

In a real-world implementation, the equation above is slightly-reorganized so as to compute the 3 pairings above faster via a multi-pairing: \begin{align} \label{eq:groth16-verify} \alphabeta + \pair{\one{A}}{-\two{B}} + \pair{\sum_{j=0}^\ell a_j \uvwGammaOne}{\gammaTwo} + \pair{\one{C}}{\deltaTwo} \equals \three{0} \end{align}

The verifier’s time complexity is dominated by:

• a size-$\ell$, $\Gr_1$ multi-($\red{\textsf{large}}$-)scalar multiplication (because $a_0 = 1$)
• a size-3 multipairing

Correctness

Recall from our ZKP definitions that a ZKP scheme like Groth16 is “correct” if honestly-generated proofs generated via $\grothProve$ verify via $\grothVerify$.

We will show Groth16 is correct by expanding the right-hand side of Eq. \ref{eq:groth16-verify} and showing that it yields the left-hand side.

The right-hand side is: \begin{align} \alphabeta + \pair{\sum_{j=0}^\ell a_j \uvwGammaOne}{\gammaTwo} + \pair{\one{C}} {\deltaTwo} =\\
\label{eq:groth16-correctness-1} = \three{\alpha\beta + \bluedashedbox{\sum_{j=0}^\ell a_j \left(\beta u_j(\tau)+\alpha v_j(\tau) + w_j(\tau)\right)}} + \redbox{\pair{\one{C}}{\deltaTwo}} \end{align} Let’s simplify the last $\redbox{\pair{\one{C}}{\deltaTwo}}$ term in the RHS above which is equal to: \begin{align} \pair{\sum_{j=\ell+1}^m a_j \uvwDeltaOne + \sum_{i=0}^{n-2} h_i \htaus + s\one{A} + r\one{B} - rs\deltaOne}{\deltaTwo}=\\
= \three{\sum_{j=\ell+1}^m a_j \left(\beta u_j(\tau)+\alpha v_j(\tau) + w_j(\tau)\right) + \sum_{i=0}^{n-2} h_i \tau^i (\tau^n - 1) + s\delta A + r\delta B - rs\delta^2}=\\
\label{eq:groth16-correctness-2} = \three{\bluedashedbox{\sum_{j=\ell+1}^m a_j \left(\beta u_j(\tau)+\alpha v_j(\tau) + w_j(\tau)\right)} + h(\tau) (\tau^n - 1) + s\delta A + r\delta B - rs\delta^2}=\\
\end{align} Next, substitute the expansion of $\redbox{\pair{\one{C}}{\deltaTwo}}$ from Eq. \ref{eq:groth16-correctness-2} back into Eq. \ref{eq:groth16-correctness-1} while combining the two sums in the dashed $\textcolor{blue}{\text{blue}}$ boxes into one solid $\textcolor{blue}{\text{blue}}$ box: \begin{align} \three{\alpha\beta + \bluebox{\sum_{j=0}^m a_j \left(\beta u_j(\tau)+\alpha v_j(\tau) + w_j(\tau)\right)} + h(\tau) (\tau^n - 1) + s\delta A + r\delta B - rs\delta^2} = \\
= \three{\alpha\beta + \sum_{j=0}^m a_j \left(\beta u_j(\tau)+\alpha v_j(\tau)\right) + \greenbox{\sum_{j=0}^m a_j w_j(\tau) + h(\tau) (\tau^n - 1)} + s\delta A + r\delta B - rs\delta^2} = \\
\end{align} Note that, by the QAP definition from Eq. \ref{eq:qap-quotient}, the $\textcolor{green}{\text{green}}$ box can be replaced by: \begin{align} \three{\alpha\beta + \sum_{j=0}^m a_j \left(\beta u_j(\tau)+\alpha v_j(\tau)\right) + \greenbox{\sum_{j=0}^m a_j u_j(\tau)\cdot \sum_{j=0}^m a_j v_j(\tau)} + s\delta A + r\delta B - rs\delta^2} = \\
= \label{eq:groth16-correctness-3} \three{\alpha\beta + \beta\reddashedbox{\sum_{j=0}^m a_j u_j(\tau)}+ \alpha \reddashedbox{\sum_{j=0}^m a_jv_j(\tau)} + \reddashedbox{\sum_{j=0}^m a_j u_j(\tau)}\cdot \reddashedbox{\sum_{j=0}^m a_j v_j(\tau)} + s\delta A + r\delta B - rs\delta^2} \end{align} Denote the $\reddashedbox{\sum_j a_j u_j(\tau)}$ sum in $A$ and the $\reddashedbox{\sum_j a_j v_j(\tau)}$ in $B$ by: \begin{align} U\bydef \sum_{j=0}^m a_j u_j(\tau)\Rightarrow A = \alpha + U + r\delta\\
V\bydef \sum_{j=0}^m a_j v_j(\tau)\Rightarrow B = \beta + V + s\delta \end{align} Next, substitute these definitions back in Eq. \ref{eq:groth16-correctness-3}: \begin{align} \three{\alpha\beta + \beta U + \alpha V + U V + s\delta A + r\delta B - rs\delta^2} =\\
\end{align} Next, expand $A$ and $B$: \begin{align} \three{\alpha\beta + \beta U + \alpha V + U V + s\delta(\alpha+U+r\delta) + r\delta (\beta+V+s\delta) - rs\delta^2} =\\
= \three{\alpha\beta + \beta U + \alpha V + U V + s\delta\alpha+s\delta U+rs\delta^2 + r\delta\beta+r\delta V} =\\
\end{align} Next, factor $V$: \begin{align} \three{\alpha\beta + \beta U + (\alpha + U + r\delta) V + s\delta\alpha+s\delta U+rs\delta^2 + r\delta\beta} =\\
= \three{\alpha\beta + \beta U + A V + s\delta\alpha+s\delta U+rs\delta^2 + r\delta\beta} =\\
\end{align} Next, factor $\beta$: \begin{align} \three{(\alpha + U + r\delta)\beta + A V + s\delta\alpha+s\delta U+rs\delta^2} =\\
= \three{A \beta + A V + s\delta\alpha+s\delta U+rs\delta^2} =\\
\end{align} Next, factor $s\delta$: \begin{align} \three{A \beta + A V + (\alpha+ U+r\delta)s\delta} = \three{A \beta + A V + A s\delta} =\\
= \three{A (\beta + V + s\delta)} = \three{A B} = \pair{\one{A}}{\two{B}} \end{align} This is exactly the left-hand side of Eq. \ref{eq:groth16-verify}, as expected.

$\mathsf{Groth16}.\mathsf{Simulate}_\mathcal{G}(R, \mathsf{td}, \mathbf{x}) \rightarrow \pi$

If one has the secret trapdoor $\td\bydef(\tau,\alpha,\beta,\delta,\gamma)$ (Eq. \ref{eq:groth16-trapdoor}) behind the $\vk$ (Eq. $\ref{eq:groth16-vk}$) for a relation $R$, then one can create, or simulate, a Groth16 proof for any statement $\stmt$ without actually knowing a valid witness $\witn$ such that $R(\stmt; \witn) = 1$.

In fact, the simulated proofs will be indistinguishable from proofs computed by an honest prover who knows a witness for the statement.

Of course, this would make Groth16 useless in practice, which is why either a trusted setup or an MPC-based ceremony is used to generate the $\vk$ and proving key without revealing the underlying trapdoor to anyone.

Proof simulation is helpful when testing ZKP-based software, since it gives a much faster way to compute a proof, say when writing test cases.

But how does it work?

Denote the $\gamma$-based components of the VK by: \begin{align} \label{eq:Uj} \Uj &\bydef \uvwgamma \end{align}

Each $\Uj$ can be easily pre-computed given the trapdoor $\td$ and the QAP associated with $R$. Having these pre-computed will make simulating proofs faster.

The task is to compute $A,B,C\in \F$ such that (1) they are uniformly-distributed and (2) $\pi\bydef(\one{A},\two{B},\one{C})$ satisfies the verification in Eq. $\ref{eq:groth16-verify}$ for the statement $\stmt \bydef (a_0, a_1, \ldots, a_\ell)$: \begin{align} \alphabeta + \pair{\one{A}}{-\two{B}} + \pair{\sum_{j=0}^\ell a_j \Uj}{\gammaTwo} + \pair{\one{C}}{\deltaTwo} &\equals \three{0}\Leftrightarrow\\
\label{eq:groth16-field-verify} \crs{\alpha}\crs{\beta} - AB + \left(\sum_{j=0}^\ell a_j \Uj\right)\crs{\gamma} + C\crs{\delta} &\equals 0 \end{align} A simple, albeit not uniformly-distributed, solution would be to set: \begin{align} A&\gets 0\\
B&\gets 0 \end{align} …and then solve for: \begin{align} C&\gets -\frac{\left(\sum_{j=0}^\ell a_j \Uj\right)\crs{\gamma} + \alpha\beta}{\crs{\delta}} \end{align} To make it uniformly-distributed, we can “randomize” it a little: \begin{align} (r_\alpha,r_\beta) &\randget\F^2\\
A&\gets r_\alpha\\
B&\gets r_\beta\\
C&\gets -\frac{\left(\sum_{j=0}^\ell a_j \Uj\right)\crs{\gamma} + \alpha\beta - r_\alpha r_\beta}{\crs{\delta}} \end{align} The simulated proof will be $\pi\bydef(\one{A},\two{B},\one{C})$.

I think any bases $G_1$ and $G_2$ can be used to encode the field elements $A,B,C$ as $\one{A},\two{B},\one{C}$, as long as they are used consistently. Not just the ones in $\bp$.

[BGM17] formulation

Bowe, Gabizon and Miers¹⁷ slightly-reformulated Groth16’s construction to allow for a more eficient MPC protocol for the $\grothSetup$ algorithm.

Specifically, instead of requiring a random $\gamma$ in the $\vk$ from Eq. $\ref{eq:groth16-vk}$, they set $\gamma = 1$.

The advantages are two-fold:

1. The VK is smaller by one-group element (no more $\gamma$)
   • e.g., when using BLS12-381 elliptic curves, this lowers the VK size from 384 to 288 bytes!
2. The MPC protocol for $\grothSetup$ is faster (because no more $\gamma$)

Importantly, this reformulation only slightly-alters the $\grothSetup$ and $\grothVerify$ algorithms, while keeping all other algorithms and the performance the same!

In practice, Groth16 tools like snarkjs actually implicitly use BGM17 by assuming $\gamma=1$ throughout the protocol. Confusingly, some of these tools unnecessarily leave the $\two{\gamma} = \two{1} = G_2$ element in their VK.

$\mathsf{BGM17.Setup}_\mathcal{G}(1^\lambda, R)\rightarrow (\mathsf{prk},\mathsf{vk},\mathsf{td})$

The trapdoor is almost the same as in Groth16’s Eq. \ref{eq:groth16-trapdoor} except there is no more $\gamma$: \begin{align} \label{eq:bgm17-trapdoor} \td\gets \left(\begin{array} % \tau, \alpha,\beta, \delta \end{array}\right)\randget\F^4 \end{align}

The proving key remains the same as in Groth16’s Eq. \ref{eq:groth16-prk}: \begin{align} \label{eq:bgm17-prk} \prk \gets \left( \begin{array} % % \alphaOne,\betaOne,\betaTwo,\deltaOne,\deltaTwo \\
% \left( \ujc, \vjc \right)_{j\in[0,m]}, % \left( \vvjc \right)_{j\in[0,m]}\\
% \left( \uvwDeltaOne \right)_{j\in[\ell+1,m]}\\
% \left( \htaus \right)_{i\in[0,n-2]} \end{array}\right) \end{align}

The verification key is also almost the same as in Groth16’s Eq. \ref{eq:groth16-vk}, except it lacks a $\gamma$ component and no longer divides by $\gamma$: \begin{align} \label{eq:bgm17-vk} \vk \gets \left( \begin{array} % \alphaOne,\betaTwo,\deltaTwo\\
% \left( \uvwOne \right)_{j\in[0,\ell]} \end{array}\right) \end{align}

$\mathsf{BGM17.Prove}(\mathsf{prk}, \mathbf{x}; \mathbf{w}) \Rightarrow \pi$

The proof $\pi=(\one{A},\two{B},\one{C})$ is computed exactly like in Groth16 above with the same Groth16 proving key.

$\mathsf{BGM17.Verify}(\vk, \mathbf{x}; \pi) \Rightarrow \{0,1\}$

The proof now verifies against the slightly-smaller VK from Eq. \ref{eq:bgm17-vk}.

The verification is almost the same as Groth16’s, except there is no $\gamma$ component, since it has been removed from the trapdoor: \begin{align} \label{eq:bgm17-verify} \alphabeta + \pair{\one{A}}{\two{B}} + \pair{\sum_{j=0}^\ell a_j \uvwOne}{\two{1}}+ \pair{\one{C}}{\deltaTwo} \equals \three{0} \end{align}

Extensions

We describe some useful extensions to Groth16 and its [BGM17] variant.

$\mathsf{Groth16.BatchVerify}(\vk, (\mathbf{x}_k; \pi_k)_{k\in[b]}) \Rightarrow \{0,1\}$

Verifying a batch of $b$ proofs (w.r.t. the same $\vk$) can be done more efficiently by taking random linear combinations of the verification in Eq. $\ref{eq:groth16-verify}$.

Recall from Eq. \ref{eq:Uj} that $\Uj\bydef\uvwgamma$ and denote: \begin{align} \stmt_k &\bydef (a_{k, 1}, a_{k,2},\ldots,a_{k,\ell})\\
\pi_k &\bydef \left(\one{A_k},\two{B_k},\one{C_k}\right)\\
P_k &\bydef\sum_{j=0}^\ell a_{k,j} \Uj \end{align}

Then, the Groth16 verification from Eq. $\ref{eq:groth16-verify}$ applied to the $k$th proof now looks like: \begin{align} \alphabeta + \pair{\one{A_k}}{-\two{B_k}} + \pair{P_k}{\gammaTwo} + \pair{\one{C_k}}{\deltaTwo} \equals \three{0} \end{align}

The verifier randomly picks $\rk\randget\F$ (128-bit scalars suffice) and uses them to randomly-combine each proof’s verification equation into one.

Too see this, first consider a randomized variant of the verification equation above applied to the $k$th proof: \begin{align} \rk\alphabeta + \pair{\rk\one{A_k}}{-\two{B_k}} + \pair{\rk P_k}{\gammaTwo} + \pair{\rk\one{C_k}}{\deltaTwo} \equals \three{0} \end{align} Scond, leveraging the bilinear property of the pairing (i.e., $\pair{\one{a_1}}{\two{b}} + \pair{\one{a_2}}{\two{b}} = \pair{\one{a_1+a_2}}{\two{b}}$), we can combine all such equations into one: \begin{align} \label{eq:groth16-batch-verify} \left(\sum_{k\in[b]}\rk\right)\alphabeta + \sum_{k\in[b]} \pair{\rk\one{A_k}}{-\two{B_k}} + \pair{\sum_{k\in[b]}\rk P_k}{\gammaTwo} + \pair{\sum_{k\in[b]}\rk\one{C_k}}{\deltaTwo} \equals \three{0} \end{align}

The batch verifier’s time complexity for $b$ proofs is:

• one $\Gr_T$ scalar multiplication for $\left(\sum_{k\in[b]}\rk\right)\alphabeta$
• $b$ $\Gr_1$ scalar multiplications, one for each $r_k\one{A_k}$
• a size-$(\ell+1)$, $\Gr_1$ multi-($\red{\textsf{large}}$-)scalar multiplication for $\sum_{k\in[b]}\rk P_k$, since it can be rewritten as:
  • $\sum_{k\in[b]} r_k \left(\sum_{j=0}^\ell a_{k,j} \Uj\right)$
  • $\sum_{j=0}^\ell \left[ \left( \sum_{k\in[b]} r_k a_{k,j} \right) \Uj\right]$
• $\ell b$ field multiplications in $\F$ to compute all $r_k a_{k,j}$’s above
• a size-$b$, $\Gr_1$ multi-($\red{\textsf{large}}$-)scalar multiplication for $\sum_{k\in[b]}\rk \one{C_k}$
• a size-$(b+2)$ multi-pairing

Done naively, verification would have been much slower: (1) $b$ size-$\ell$, $\Gr_1$ multi-($\red{\textsf{large}}$-)scalar multiplications and (2) $b$ size-3 multipairings

Batching verification for [BGM17] is virtually the same, except we replace (1) the $\Uj$’s defined in Eq. $\ref{eq:Uj}$ with $\Vj \bydef \uvw$ and (2) the $\gammaTwo$ in the batch-verification Eq. $\ref{eq:groth16-batch-verify}$ with $\two{1}$.

$\mathsf{Groth16}.\mathsf{Rerandomize}(\mathsf{vk}, \pi; \Delta{r},\Delta{s}) \rightarrow \pi’$

Suppose we have a proof $\pi\bydef(\one{A},\two{B},\one{C})$ that verifies. Baghery et al.¹⁸ shows how to re-randomize this proof into a new one $\pi’ = (\one{A},\two{B},\one{C})$ as follows: \begin{align} \one{A’} &\gets \frac{1}{\Delta{r}} \one{A}\\\ \two{B’} &\gets \Delta{r}\two{B} + \Delta{r}\Delta{s}\deltaTwo\\\ \one{C’} &\gets \one{C} + \Delta{s}\one{A} \end{align}

$\Delta{r}$ and $\Delta{s}$ should be picked uniformly at random in $\F$. This way, the distribution of re-randomized proofs is the same as the distribution of honestly-generated ones. This can be very useful in privacy applications, especially when verifying proofs over committed statements.

To see why correctness holds, recall that a proof $\pi$ is valid iff. the proof verification from Eq. \ref{eq:groth16-field-verify} holds: \begin{align} \crs{\alpha}\crs{\beta} - AB + \left(\sum_{j=0}^\ell a_j \Uj\right)\crs{\gamma} + C\crs{\delta} &\equals 0 \end{align} Next, observe that, if the verification above holds for $\pi$, then it also holds for the re-randomized $\pi’$: \begin{align} \crs{\alpha}\crs{\beta} - \reddashedbox{A’B’} + \left(\sum_{j=0}^\ell a_j \Uj\right)\crs{\gamma} + \bluedashedbox{C’}\crs{\delta} &\equals 0 \Leftrightarrow\\
% \crs{\alpha}\crs{\beta} - \reddashedbox{\frac{A}{\Delta{r}}(\Delta{r}B + \Delta{r}\Delta{s}\crs{\delta})} + \left(\sum_{j=0}^\ell a_j \Uj\right)\crs{\gamma} + \bluedashedbox{\left(C + \Delta{s} A\right)} \crs{\delta} &\equals 0 \Leftrightarrow\\
% \crs{\alpha}\crs{\beta} - \reddashedbox{\left(\frac{A\Delta{r}B}{\Delta{r}} + \frac{A\Delta{r}\Delta{s}\crs{\delta}}{\Delta{r}}\right)} + \left(\sum_{j=0}^\ell a_j \Uj\right)\crs{\gamma} + C\crs{\delta} + \Delta{s} A\crs{\delta} &\equals 0 \Leftrightarrow\\
% \crs{\alpha}\crs{\beta} - \reddashedbox{\left(AB + A\Delta{s}\crs{\delta}\right)} + \left(\sum_{j=0}^\ell a_j \Uj\right)\crs{\gamma} + C\crs{\delta} + \Delta{s} A\crs{\delta} &\equals 0 \Leftrightarrow\\
% \crs{\alpha}\crs{\beta} - AB + \left(\sum_{j=0}^\ell a_j \Uj\right)\crs{\gamma} + C \crs{\delta} &= 0 \end{align}

This algorithm also works to re-randomize proofs for [BGM17].

[BGM17] commit-and-prove extension

A [BGM17]-style proof for a statement $\stmt$ can be converted into a “commit-and-prove”-style proof $\pi’$ that verifies against a Pedersen commitment $c$ to $\stmt$. This is very useful in privacy-preserving settings, where the verifier may only have a commitment to $\stmt$ instead of the statement itself (e.g., see zk-creds¹⁹ or the keyless relation in Eq. \ref{eq:keyless-rel}).

We describe such a commit-and-prove extension to [BGM17] below. The scheme is extracted from a more general-purpose Groth16 linkage scheme by Rosenberg et al.¹⁹.

Technically, this may not pass mustard as a proper commit-and-prove (CaP) SNARK because, as we’ll see below, the commitment key is a function of the relation $R$ being proved. I am not sure if CaP SNARKs demand a relation-independent commitment key. Nonetheless, this can be surmounted easily via a discrete-log equality proof, as already explored in zk-creds¹⁹.

$\mathsf{BGM17}.\mathsf{Blind}(\mathsf{vk}, \mathbf{x}; \pi, z) \rightarrow (c, \pi’)$

Given a [BGM17]-style proof $\pi\bydef(\one{A},\two{B},\one{C})$ for $\stmt$, this algorithm returns a Pedersen commitment $c$ to $\stmt$ and a new re-randomized proof $\pi’$ that verifies against $c$.

First, picks random blinding factors $(\Delta{r}, \Delta{s})\randget \F^2$ and re-randomizes the proof $\pi$ via $\grothRerand$ (in place): \begin{align} \pi\gets \grothRerand(\vk, \pi; \Delta{r},\Delta{s}) \end{align}

Let $\Vj$ denote part of the $\vk$ in Eq. \ref{eq:bgm17-vk}: \begin{align} \label{eq:Vj} \Vj\bydef\uvw \end{align}

Second, using $\left(\deltaOne,\crs{\one{V_1}},\ldots\crs{\one{V_\ell}}\right)$ as the Pedersen commitment key and the supplied $z$ as the blinding factor, commits to the statement $\stmt\bydef(1,a_1,a_2,\ldots,a_\ell)$: \begin{align} \label{eq:bgm17-commit} c&\gets z\deltaOne + \sum_{j=1}^\ell a_j \VjOne \end{align}

The commitment excludes the $a_0 = 1$ component, which will be added in during verification.

Third, computes a ZKPoK $\pi_c$ of the opening to the Pedersen commitment $c$. (This can be done via a $\Sigma$-protocol; e.g., see the $\mathsf{EqWire}$ protocol in zk-creds¹⁹.)

Fourth, slightly-adjusts the proof to account for the blinded commitment and to include the ZKPoK: \begin{align} \pi’ \gets (\pi_c, \one{A},\two{B},\one{C} - \one{z}) \end{align}

$\mathsf{BGM17}.\mathsf{BlindVerify}(\mathsf{vk}, c; \pi’) \rightarrow \{0,1\}$

Parses $(\pi_c, \one{A’},\two{B’},\one{C’})\gets \pi’$.

First, checks the ZKPoK $\pi_c$ against the commitment $c$ and the Pedersen commitment key.

Second, performs a [BGM17]-like check of the proof: \begin{align} \label{eq:bgm17-blind-verify} \alphabeta + \pair{\one{A’}}{-\two{B’}} + \pair{\crs{\one{V_0}} + c}{\two{1}} + \pair{\one{C’}}{\deltaTwo} \equals \three{0} \end{align}

This verification over $(c,\pi’)$ is equivalent to the [BGM17]-style verification from Eq. \ref{eq:bgm17-verify} over $\left(x,\pi\bydef(\one{A},\two{B},\one{C})\right)$, where $\pi$ is the original proof and $x$ is the statement committed in $c$: \begin{align} \alphabeta + \pair{\one{A’}}{-\two{B’}} + \pair{\crs{\one{V_0}} + c}{\two{1}} + \pair{\one{C’}}{\deltaTwo} &\equals \three{0} \Leftrightarrow\\
\alphabeta + \pair{\one{A}}{-\two{B}} + \pair{\crs{\one{V_0}} + z\deltaOne + \sum_{j=1}^\ell a_j \VjOne}{\two{1}} + \pair{\one{C’}}{\deltaTwo} &\equals \three{0} \Leftrightarrow\\
\alphabeta + \pair{\one{A}}{-\two{B}} + \pair{z\deltaOne + \sum_{j=0}^\ell a_j \VjOne}{\two{1}} + \pair{\one{C}-\one{z}}{\deltaTwo} &\equals \three{0} \Leftrightarrow\\
\alphabeta + \pair{\one{A}}{-\two{B}} + \pair{\sum_{j=0}^\ell a_j \VjOne}{\two{1}} + \pair{\one{C}}{\deltaTwo} &\equals \three{0} \end{align}

In some settings, it may be useful to leave part of the statement $\stmt$ uncommitted. The scheme above can be easily-adjusted to do this.

Prize-winning stuff: Could this be modified to work for Groth16? We could: (1) replace the $\Vj$’s from Eq. \ref{eq:Vj} with the $\Uj$’s from Eq. \ref{eq:Uj}, (2) replace the $\deltaOne$ used as the base for committing to $z$ with $\crs{\one{\delta/\gamma}}$, which would now have to be computed as part of the $\vk$, and (3) replace $\gammaTwo$ with $\two{1}$ in the blind verification from Eq. \ref{eq:bgm17-blind-verify}. The rest should remain the same, I think? Unfortunately, because of the extra $\crs{\one{\delta/\gamma}}$ $\vk$ component, it would not work with an out-of-the-box Groth16.

MPC protocol for $\mathsf{BGM17}.\mathsf{Setup}$

Bowe, Gabizon and Miers¹⁷ proposed a multi-party computation (MPC) protocol amongst $N$ players that generates the Groth16 proving and verification keys for a QAP without revealing the trapdoor, as long as at least one player is honest.

Moreover, their protocol has a versatile player-exchangeability property, which allows players to join and leave the protocol as they please (including rejoining). This precludes problems such as:

1. Having to pre-agree on the set of participating players.
2. Worrying about players aborting during the protocol.
3. A player having to maintain long-term secrets across a long-running MPC protocol.

The MPC protocol consists of two phases, which are themselves MPC protocols:

1. A phase-1 “powers-of-$\tau$” MPC: it does not depend on the QAP polynomials from Eq. $\ref{eq:qap-quotient}$ and is thus universal and reusable
2. A phase-2 relation-specific MPC: it depends on the QAPs that Groth16 is being set up to prove

At a high level, each phase-$i$ MPC operates very simply, in rounds:

• Previously, round $N-1$ produced an output $\mathsf{out}_{N-1}$ with proofs-of-knowledge $(\pi_i)_{i\in[N-1]}$ from each contributing player
• A player joins, triggering the beginning of round $N$
• The player generates his secret contribution as $s\gets\mathsf{Phase}_i.\mathsf{Gen}(1^\lambda)$
• The player verifies the previous players’ contributions, if any, via $\mathsf{Phase}_i.\mathsf{Verify}(\mathsf{out}_{N-1}, (\pi_i)_{i\in[N-1]})\equals 1$
• The player contributes via $(\mathsf{out}_N,\pi_N) \gets \mathsf{Phase}_i.\mathsf{Contribute}(\mathsf{out}_{N-1}, (\pi_i)_{i\in[N-1]}; s)$
  • Importantly, the new output $\mathsf{out}_N$ and proof-of-knowledge $\pi_N$ leak nothing about the player’s secrets contribution $s$
  • $\pi_N$ is a proof of knowledge for $s$
• The player leaves, ending round $N$, feeding $\left(\mathsf{out}_N,(\pi_i)_{i\in[N]}\right)$ into the next round
• This repeats until enough secret contributions are incorported.

“Enough” to guarantee that at least one of the players discards their secret contribution, thereby hiding the Groth16 trapdoor from Eq. $\ref{eq:groth16-trapdoor}$. Obviously, different applications demand different levels of paranoia. In the past, MPC ceremonies have used anywhere from six players to hundreds of players.

After all players contribute to a phase $i\in\{1,2\}$, Bowe, Gabizon and Miers apply a public round at the end of the phase, where this round’s secret contribution is actually publicly-generated from a random beacon (e.g., drand) rather than secretly-generated by a player. However, Kohlweiss et al. showed that this is not necessary for security¹¹. In this blog post, we describe the variant without a random beacon.

Public-verifiability: At the end of a phase, all players use the phase’s $\mathsf{Verify}$ algorithm to verify that the final $\mathsf{out}_N$ was correctly-derived given all the proofs-of-knowledge $\pi_1, \pi_2, \ldots, \pi_N$. Nonetheless, even if this verification succeeds, it remains each player’s responsibility to check that one of the $\pi_i$’s is a proof-of-knowledge for their own secret contribution $s$: i.e., that $s$ was incorporated in the derivation of $\mathsf{out}_N$.

Let $\hashPokNoArg : \Gr_1 \times \{0,1\}^* \rightarrow \Gr_2$ be a hash function modeled as a random oracle.

Next, we describe the two phase-1 and phase-2 (sub)protocols.

Phase 1: Powers of $\tau$

The phase-1 MPC outputs powers-of-$\tau$, denoted by: \begin{align} \label{eq:ptau} \ptau(\tau,\alpha,\beta) &\bydef \left( \two{\beta}, \left(\two{\tau^i},\one{\alpha\tau^i},\one{\beta\tau^i}\right)_{i\in[0, n-1]}, \left(\one{\tau^i}\right)_{i\in[0, 2n-2]} \right) \\
&\bydef \left[\begin{array}% \two{\beta}\\
\left(\two{\tau^0}, \two{\tau^1}, \two{\tau^2}, \ldots, \two{\tau^{n-1}}\right)\\
\left(\one{\alpha\tau^0}, \one{\alpha\tau^1}, \one{\alpha\tau^2},\ldots,\one{\alpha\tau^{n-1}}\right)\\
\left(\one{\beta\tau^0}, \one{\beta\tau^1}, \one{\beta\tau^2},\ldots,\one{\beta\tau^{n-1}}\right)\\
\left(\one{\tau^0}, \one{\tau^1}, \one{\tau^2},\ldots,\one{\tau^{2n-2}}\right)\\
\end{array}\right] \end{align} …where $(\tau,\alpha,\beta)\in \F^3$.

The key idea: Given a previous $\ptau(\tau,\alpha,\beta)$ powers-of-$\tau$, a new player can incorporate their secret contribution $(\otau,\oalpha,\obeta)$ by computing scalar multiplications. We denote this operation using the $\oplus$ operator: \begin{align} \ptau(\tau,\alpha,\beta) \oplus (\otau,\oalpha,\obeta) & \bydef \left[\begin{array}% \obeta\cdot\two{\beta}\\
\left(\otau^0\cdot\two{\tau^0}, \otau^1\cdot\two{\tau^1}, \otau^2\cdot\two{\tau^2}, \ldots, \otau^{n-1}\cdot\two{\tau^{n-1}}\right)\\
\left(\oalpha\otau^0\cdot\one{\alpha\tau^0}, \oalpha\otau^1\cdot\one{\alpha\tau^1}, \oalpha\otau^2\cdot\one{\alpha\tau^2},\ldots,\oalpha\otau^{n-1}\cdot\one{\alpha\tau^{n-1}}\right)\\
\left(\obeta\otau^0\cdot\one{\beta\tau^0}, \obeta\otau^1\cdot\one{\beta\tau^1}, \obeta\otau^2\cdot\one{\beta\tau^2},\ldots,\obeta\otau^{n-1}\cdot\one{\beta\tau^{n-1}}\right)\\
\left(\otau^0\cdot\one{\tau^0}, \otau^1\cdot\one{\tau^1}, \otau^2\cdot\one{\tau^2},\ldots,\otau^{2n-2}\cdot\one{\tau^{2n-2}}\right)\\
\end{array}\right]\\
& = \left[\begin{array}% \two{\obeta\beta}\\
\left(\two{(\otau\tau)^0}, \two{(\otau\tau)^1}, \two{(\otau\tau)^2}, \ldots, \two{(\otau\tau)^{n-1}}\right)\\
\left(\one{\oalpha\alpha(\otau\tau)^0}, \one{\oalpha\alpha(\otau\tau)^1}, \one{\oalpha\alpha(\otau\tau)^2},\ldots,\one{\oalpha\alpha(\otau\tau)^{n-1}}\right)\\
\left(\one{\obeta\beta(\otau\tau)^0}, \one{\obeta\beta(\otau\tau)^1}, \one{\obeta\beta(\otau\tau)^2},\ldots,\one{\obeta\beta(\otau\tau)^{n-1}}\right)\\
\left(\one{(\otau\tau)^0}, \one{(\otau\tau)^1}, \one{(\otau\tau)^2},\ldots,\one{(\otau\tau)^{2n-2}}\right)\\
\end{array}\right]\\
& \bydef \left[\begin{array}% \two{\bbeta}\\
\left(\two{\btau^0}, \two{\btau^1}, \two{\btau^2}, \ldots, \two{\btau^{n-1}}\right)\\
\left(\one{\balpha\btau^0}, \one{\balpha\btau^1}, \one{\balpha\btau^2},\ldots,\one{\balpha\btau^{n-1}}\right)\\
\left(\one{\bbeta\btau^0}, \one{\bbeta\btau^1}, \one{\bbeta\btau^2},\ldots,\one{\bbeta\btau^{n-1}}\right)\\
\left(\one{\btau^0}, \one{\btau^1}, \one{\btau^2},\ldots,\one{\btau^{2n-2}}\right)\\
\end{array}\right]\\
& = \ptau(\otau\cdot\tau,\oalpha\cdot\alpha,\obeta\cdot\beta) \bydef \ptau(\btau,\balpha,\bbeta) %,\ \text{where}\ (\btau,\balpha,\bbeta) = (\otau\cdot\tau,\oalpha\cdot\alpha,\obeta\cdot\beta) \end{align}

The $(\two{\tau^i})_{i\in[0,2n-2]}$ are needed to commit to $h(X) (X^n - 1)$, since $h(X)$ has max. degree $n-2$.

It is useful to run a phase 1 for a much higher-than-needed $n$. This way, the resulting powers-of-$\tau$ are larger and can be reused across many phase-2 MPCs for QAPs that have higher degree $n$. Nonetheless, Groth16 remains secure even though more “powers of $\tau$” are exposed than strictly needed.

Furthermore, in some academic papers, $\ptau(\tau,\alpha,\beta)$ is defined to include additional group elements that are not needed for Groth16 but may be useful for other SNARKs. For example, see Mary Maller’s description²⁰. In this blog post, we only included the minimal amount of elements needed for Groth16. Nonetheless, once the reader understands the phase 1 MPC protocol, it should be easy to extend it to include extra elements.

Next, we describe the three algorithms for phase 1.

$\mathsf{Phase}_1.\mathsf{Gen}(1^\lambda)\rightarrow (\orange{\tilde{\tau}},\orange{\tilde{\alpha}},\orange{\tilde{\beta}})$

Generates the player’s secret contribution: \begin{align} (\orange{\tilde{\tau}},\orange{\tilde{\alpha}},\orange{\tilde{\beta}}) \randget \F^3 \end{align}

$\mathsf{Phase}_1.\mathsf{Init}_\mathcal{G}(\orange{\tilde{\tau}},\orange{\tilde{\alpha}},\orange{\tilde{\beta}}) \rightarrow (\mathsf{ptau}_1,\pi_1)$

Outputs the first round’s powers-of-$\tau$ together with its proof-of-knowledge (PoK):

• $\ptau_1 \gets \ptau(\otau,\oalpha,\obeta)$
• $\trx_1\gets (\bp)$
• $\pi_1\gets \left(\begin{array}% \hashPok{\one{\otau}, \trx_1}^\otau, & \one{\otau}, & \one{\otau} \\
  \hashPok{\one{\oalpha}, \trx_1}^\oalpha, & \one{\oalpha}, & \one{\oalpha} \\
  \hashPok{\one{\obeta}, \trx_1}^\obeta, & \one{\obeta}, & \one{\obeta} \\
  \end{array}\right)$

Since this is the first contribution, the last two columns in $\pi_1$ are identical.

$\mathsf{Phase}_1.\mathsf{Contribute}_\mathcal{G}\left(\mathsf{ptau}_{N-1},(\pi_k)_{k\in[N-1]}; (\orange{\tilde{\tau}},\orange{\tilde{\alpha}},\orange{\tilde{\beta}})\right) \rightarrow (\mathsf{ptau}_N, \pi_N)$

Step 0: If $N = 1$, return $\phaseOneInit(\otau,\oalpha,\obeta)$. Otherwise, continue below.

Step 1: Parses the previous powers-of-$\tau$ (see Eq. \ref{eq:ptau}), \begin{align} \ptau(\tau,\alpha,\beta) &\parse \ptau_{N-1} \end{align} …and extracts its underlying commitments-of-$\tau$: \begin{align} \one{\tau} , \one{\alpha}, \one{\beta} \end{align} Step 2: Computes the new powers-of-$\tau$, by incorporating the secret contribution $(\otau,\oalpha,\obeta)$ via the $\oplus$ operator: \begin{align} \ptau_N &\gets \ptau(\tau,\alpha,\beta) \oplus (\otau, \oalpha, \obeta) \bydef \ptau(\btau,\balpha,\bbeta) ,\ \text{where}\ (\btau,\balpha,\bbeta) = (\otau\cdot\tau,\oalpha\cdot\alpha,\obeta\cdot\beta) \end{align}

This will be slow. For example, contributing to the $\ptau(\tau,\alpha,\beta)$ in Eq. $\ref{eq:ptau}$ requires: $n$ $\Gr_2$ scalar multiplications and $4n-1$ $\Gr_1$ scalar multiplications. On a state-of-the-art BLS12-381 implementation like blstrs, for $n=2^{21}$, this would take $7 + 14 = 21$ minutes in a single thread.

…extracts its underlying commitments-of-$\tau$: \begin{align} \label{eq:new-commitments-of-tau} \one{\btau},\one{\balpha},\one{\bbeta} \end{align} …and computes the public contribution: \begin{align} \label{eq:ptau-contrib} \one{\otau} \gets \otau\cdot G_1\\
\one{\oalpha} \gets \oalpha\cdot G_1\\
\one{\obeta} \gets \obeta\cdot G_1 \end{align}

Step 3: Derives the transcript: \begin{align} \label{eq:phase1-trx} \trx_N \gets (\bp, \pi_1, \pi_2, \ldots \pi_{N-1}) \end{align}

Step 4: Computes the proof-of-knowledge (PoK), consisting of: (1) BLS-style proofs-of-possesion²¹ of $\otau,\oalpha$ and $\obeta$, (2) the player’s public contribution from Eq. \ref{eq:ptau-contrib} and (3) the new commitments-of-$\tau$ from Eq. \ref{eq:new-commitments-of-tau}: \begin{align} \pi_N \gets \left(\begin{array}% \hashPok{\one{\otau}, \trx_N}^\otau, & \one{\otau}, & \one{\btau} \\
\hashPok{\one{\oalpha}, \trx_N}^\oalpha, & \one{\oalpha}, & \one{\balpha} \\
\hashPok{\one{\obeta}, \trx_N}^\obeta, & \one{\obeta}, & \one{\bbeta} \\
\end{array}\right) \end{align}

$\mathsf{Phase}_1.\mathsf{Verify}_\mathcal{G}\left(\mathsf{ptau}_N, (\pi_k)_{k\in[N]}\right) \rightarrow \{0,1\}$

Step 1: Set the initial commitments-of-$\tau$ to: \begin{align} (\one{\tau},\one{\alpha},\one{\beta}) &\gets (\one{1},\one{1},\one{1})\\
% \ptau_0 &\gets \ptau(\tau,\alpha,\beta) \end{align}

Step 2: For $k \in [1, N]$:

Substep 2.1: Parse the proof-of-knowledge: \begin{align} \left(\begin{array}% \pok_\otau, & \one{\otau}, & \one{\btau} \\
\pok_\oalpha, & \one{\oalpha}, & \one{\balpha} \\
\pok_\obeta, & \one{\obeta}, & \one{\bbeta} \\
\end{array}\right)&\parse \pi_k\\
\end{align}

Substep 2.2: Check that the public contribution is not zero, which would cancel out all previous and future contributions: \begin{align} \textbf{assert}\ \one{\otau} \ne \one{0} \wedge \textbf{assert}\ \one{\oalpha} \ne \one{0} \wedge \textbf{assert}\ \one{\obeta} \ne \one{0} \end{align} …and, while at it, also check it is not one, which would be useless: \begin{align} \textbf{assert}\ \one{\otau} \ne \one{1} \wedge \textbf{assert}\ \one{\oalpha} \ne \one{1} \wedge \textbf{assert}\ \one{\obeta} \ne \one{1} \end{align}

Substep 2.3: Verify the proof-of-knowledge: \begin{align} \trx_k &\gets (\bp, \pi_1, \pi_2, \ldots, \pi_{k-1})\\
% h_\otau \gets \hashPok{\one{\otau},\trx_k} &\wedge \textbf{assert}\ \pair{\one{\otau}}{h_\otau} \equals \pair{\one{1}}{\pok_\otau}\\
h_\oalpha \gets \hashPok{\one{\oalpha},\trx_k} &\wedge \textbf{assert}\ \pair{\one{\oalpha}}{h_\oalpha} \equals \pair{\one{1}}{\pok_\oalpha}\\
h_\obeta \gets \hashPok{\one{\obeta},\trx_k} &\wedge \textbf{assert}\ \pair{\one{\obeta}}{h_\obeta} \equals \pair{\one{1}}{\pok_\obeta}\\
\end{align}

These three checks above verify the proof-of-knowledge (PoK) on $\otau,\oalpha$ and $\obeta$. To see why correctness holds, let’s consider the check for $\tau$: \begin{align} \pair{\one{\otau}}{h_\otau} &\equals \pair{\one{1}}{\pok_\otau}\Leftrightarrow\\
\pair{\one{\otau}}{\hashPok{\one{\otau},\trx_k}} &\equals \pair{\one{1}}{\otau\cdot\hashPok{\one{\otau},\trx_k}}\Leftrightarrow\\
\pair{\one{1}}{\otau\cdot\hashPok{\one{\otau},\trx_k}} &\equals \pair{\one{1}}{\otau\cdot\hashPok{\one{\otau},\trx_k}}\Leftrightarrow\\
\otau\cdot\hashPok{\one{\otau},\trx_k} &= \otau\cdot\hashPok{\one{\otau},\trx_k} \end{align}

\begin{align} % \textbf{assert}\ \pair{\one{\tau}}{\pok_\otau} &\equals \pair{\one{\btau}}{h_\otau}\\
\textbf{assert}\ \pair{\one{\alpha}}{\pok_\oalpha} &\equals \pair{\one{\balpha}}{h_\oalpha}\\
\textbf{assert}\ \pair{\one{\beta}}{\pok_\obeta} &\equals \pair{\one{\bbeta}}{h_\obeta}\\
\end{align}

These three checks above ensure that $\btau =\tau\otau$, $\balpha=\alpha\oalpha$ and $\bbeta=\beta\obeta$. To see why correctness holds, let’s take the check for $\tau$: \begin{align} \pair{\one{\tau}}{\pok_\otau} &\equals \pair{\one{\btau}}{h_\otau}\Leftrightarrow\\\ \pair{\one{\tau}}{\otau\cdot\hashPok{\one{\otau},\trx_k}} &\equals \pair{\one{\btau}}{\hashPok{\one{\otau},\trx_k}}\Leftrightarrow\\
\pair{\one{1}}{(\tau\otau)\cdot\hashPok{\one{\otau},\trx_k}} &\equals \pair{\one{1}}{\btau\cdot\hashPok{\one{\otau},\trx_k}}\Leftrightarrow\\
\tau\otau &\equals \btau \end{align}

Substep 2.4: Re-set the commitments-of-$\tau$ for the next iteration. \begin{align} \label{eq:phase-1-tau-alpha-beta} (\one{\tau},\one{\alpha},\one{\beta}) &\gets (\one{\btau},\one{\balpha},\one{\bbeta})\\
\end{align}

Substep 2.5: Go back to Step 2.

The next steps will verify $\ptau_N$ is well-formed as per Eq. \ref{eq:ptau} and derived from the $(\one{\tau},\one{\alpha},\one{\beta})$ commitments-of-$\tau$ arrived at in Eq. \ref{eq:phase-1-tau-alpha-beta} from the verification above.

Step 3: Parse $\ptau_N$: \begin{align} \label{eq:parsed-ptau} % \two{\beta}, % \left(\two{\tau^i},\one{\alpha\tau^i},\one{\beta\tau^i}\right)_{i\in[0, n-1]}, % \left(\one{\tau^i}\right)_{i\in[0, 2n-2]} \left( \tilde{B}, \left(\tilde{T}_i,\mathsf{at}_i,\mathsf{bt}_i\right)_{i\in[0, n-1]}, \left(T_i\right)_{i\in[0, 2n-2]} \right) \parse \ptau_N \end{align}

Step 4: Verify that $\ptau_N$ contains the right $G_1\bydef\one{1},G_2\bydef\two{1}$ (as per $\bp$), and the expected $\one{\tau},\one{\alpha},\one{\beta}$ group elements from Eq. \ref{eq:phase-1-tau-alpha-beta} in the right positions: \begin{align} \textbf{assert}\ T_0 \equals \one{1} &\wedge \textbf{assert}\ \tilde{T}_0 \equals \two{1}\\
\textbf{assert}\ \mathsf{at}_0 \equals \one{\alpha} &\wedge \textbf{assert}\ \mathsf{bt}_0 \equals \one{\beta}\wedge \textbf{assert}\ T_1 \equals \one{\tau}\\
\end{align}

Step 5: Verify $\tilde{T}_1\equals\two{\tau}$ and $\tilde{B}=\two{\beta}$ using pairing checks against $\one{\tau}$ and $\one{\beta}$: \begin{align} \pair{\one{1}}{\tilde{T}_1} &\equals \pair{\one{\tau}}{\two{1}}\\
\pair{\one{1}}{\tilde{B}} &\equals \pair{\one{\beta}}{\two{1}} \end{align}

Step 6: Check that the $T_i$’s and $\tilde{T}_i$’s contain the powers $\tau^0, \tau^1, \tau^2, \ldots$ committed in $\Gr_1$ and $\Gr_2$, respectively: \begin{align} \forall i\in [0,n-1), \pair{T_i}{\two{\tau}} &\equals \pair{T_{i+1}}{\two{1}}\\
\forall i\in [0,2n-2), \pair{\one{\tau}}{\tilde{T}_i} &\equals \pair{\one{1}}{\tilde{T}_{i+1}}\\
\end{align}

Step 7: Check that the $\mathsf{at}_i$’s contain the powers $\alpha\tau^0, \alpha\tau^1, \alpha\tau^2, \ldots$ committed in $\Gr_1$: \begin{align} \forall i\in [0,n-1), \pair{\mathsf{at}_i}{\two{\tau}} &\equals \pair{\mathsf{at}_{i+1}}{\two{1}}\\
\end{align}

Step 8: Check that the $\mathsf{bt}_i$’s contain the powers $\beta\tau^0, \beta\tau^1, \beta\tau^2, \ldots$ committed in $\Gr_1$: \begin{align} \forall i\in [0,n-1), \pair{\mathsf{bt}_i}{\two{\tau}} &\equals \pair{\mathsf{bt}_{i+1}}{\two{1}}\\
\end{align}

Steps 6 through 8 can benefit greatly from being implemented as a multi-pairing check: e.g., $\pair{\sum_{i\in[0,n-1)} (\gamma_i T_i + \psi_i \mathsf{at}_i + \chi_i \mathsf{bt}_i)}{\two{\tau}} \equals \pair{\sum_{i\in[0,n-1)} (\gamma_i T_{i+1} + \psi_i \mathsf{at}_{i+1} + \chi_i \mathsf{bt}_{i+1})}{\two{\tau}}$, where the $(\gamma_i,\psi_i,\chi_i)$’s are 128-bit random scalars. In fact, many of the pairing-based checks in the previous steps can also benefit from such tricks. The most efficient multi-pairing strategy is not immediately obvious.

Phase 2: Relation-specific

The final output of the phase-2 MPC will be a bunch of QAP-specific parameters: \begin{align} \label{eq:mpc-phase2-output} \outTwo(\delta)\bydef\left[\begin{array}% \one{\delta},\two{\delta} \\
\left(\one{\frac{\beta\gu_j(\tau) + \alpha\rv_j(\tau) + \bw_j(\tau)}{\delta}}\right)_{j\in[\ell+1, m]} \\
\left(\one{\frac{\tau^i (\tau^n - 1)}{\delta}}\right)_{i\in[0, n-2]} \\
\end{array}\right] \end{align}

Note that the phase-2 round output depends on (1) the bilinear group $\bp$ used in phase 1, (2) the phase-1 $\ptau_N$ output and (2) the QAP encoding a relation $R$. As a result, its algorithms (described below) will have implicit access to $\bp$, $R$ and $\ptau$, and also to the final phase-1 transcript $\trx_N\bydef\trx$.

Note that, in a pre-processing phase, anybody can compute the following group elements: \begin{align} \left(\uvwOneCol\right)_{j\in[\ell+1, m]} \\
\left(\tauN\right)_{i\in[0, n-2]} \end{align} Therefore, we assume that the phase-2 algorithms also have implicit access to these.

Much like in phase 1, we can formalize a player incorporating their secret contribution $\odelta$ using the $\oplus$ operator: \begin{align} \outTwo(\delta) \oplus \odelta \bydef \outTwo(\odelta\cdot\delta)\bydef\outTwo(\bdelta) \end{align} where $\bdelta = \odelta\cdot\delta$.

We describe the algorithms next.

$\mathsf{Phase}_2.\mathsf{Gen}(1^\lambda)\rightarrow \orange{\tilde{\delta}}$

Generates the player’s secret contribution: \begin{align} \orange{\tilde{\delta}} \randget \F \end{align}

$\mathsf{Phase}_2.\mathsf{Init}(\orange{\tilde{\delta}}) \rightarrow (\outTwo_1,\pi_1)$

Outputs the second round’s QAP-specific parameters together with a proof-of-knowledge (PoK):

• $\outTwo_1 \gets \outTwo(\odelta)$
• $\trx_1\gets \trx$ (Recall that $\trx\bydef\trx_N$ is the final transcript of the phase 1 MPC from Eq. \ref{eq:phase1-trx}.)
• $\pi_1\gets \left(\begin{array}% \hashPok{\one{\odelta}, \trx_1}^\odelta, & \one{\odelta}, & \one{\odelta} \\
  \end{array}\right)$

$\mathsf{Phase}_2.\mathsf{Contribute}\left(\mathsf{qp}_{M-1},(\pi_k)_{k\in[M-1]}; \orange{\tilde{\delta}}\right) \rightarrow (\mathsf{qp}_M, \pi_M)$

Step 0: If $M = 1$, return $\phaseTwoInit(\odelta)$. Otherwise, continue below.

Step 1: Parses the previous QAP-specific parameters (see Eq. \ref{eq:mpc-phase2-output}), \begin{align} \outTwo(\delta) &\parse \outTwo_{M-1} \end{align} …and extracts its underlying commitment-of-$\delta$: \begin{align} \one{\delta} \end{align} Step 2: Computes the new QAP-specific parameters, by incorporating the secret contribution $\odelta$ via the $\oplus$ operator: \begin{align} \outTwo_N &\gets \outTwo(\delta) \oplus \odelta \bydef \outTwo(\bdelta) ,\ \text{where}\ \bdelta = \odelta\cdot\delta \end{align}

This will be a little slow too. For example, contributing to the $\outTwo(\delta)$ in Eq. $\ref{eq:mpc-phase2-output}$ requires: $(n-2) + (m-\ell)$ $\Gr_1$ scalar multiplications. Assuming $m=n=2^{21}$ and $\ell = 1$, on a state-of-the-art BLS12-381 implementation like blstrs, this would take $7$ minutes in a single thread. (3x faster than its phase-1 counterpart.)

…extracts its underlying commitment-of-$\delta$: \begin{align} \label{eq:new-commitment-of-delta} \one{\bdelta} \end{align} …and computes the public contribution: \begin{align} \label{eq:phase2-contrib} \one{\odelta} \gets \odelta\cdot G_1 \end{align}

Step 3: Derives the transcript: \begin{align} \label{eq:phase2-trx} \trx_N \gets (\trx, \pi_1, \pi_2, \ldots \pi_{M-1}) \end{align}

Step 4: Computes the proof-of-knowledge (PoK), consisting of: (1) BLS-style proofs-of-possesion²¹ of $\odelta$, (2) the player’s public contribution from Eq. \ref{eq:phase2-contrib} and (3) the new commitment-of-$\delta$ from Eq. \ref{eq:new-commitment-of-delta}: \begin{align} \pi_N \gets \left(\begin{array}% \hashPok{\one{\odelta}, \trx_N}^\odelta, & \one{\odelta}, & \one{\bdelta} \\
\end{array}\right) \end{align}

$\mathsf{Phase}_2.\mathsf{Verify}\left(\mathsf{qp}_M, (\pi_k)_{k\in[M]}\right) \rightarrow \{0,1\}$

Step 1: Set the initial commitment-of-$\delta$ to: \begin{align} \one{\delta}\gets\one{1} \end{align}

Step 2: For $k \in [1, M]$:

Substep 2.1: Parse the proof-of-knowledge: \begin{align} \left(\begin{array}% \pok_\odelta, & \one{\odelta}, & \one{\bdelta} \\
\end{array}\right)&\parse \pi_k\\
\end{align}

Substep 2.2: Check that the public contribution is neither zero, which would cancel out all previous and future contributions, nor one, which would be useless: \begin{align} \textbf{assert}\ \one{\odelta} \ne \one{0} \wedge \textbf{assert}\ \one{\odelta} \ne \one{1} \end{align}

Substep 2.3: Verify the proof-of-knowledge: \begin{align} \trx_k &\gets (\trx, \pi_1, \pi_2, \ldots, \pi_{k-1})\\
% h_\odelta \gets \hashPok{\one{\odelta},\trx_k} &\wedge \textbf{assert}\ \pair{\one{\odelta}}{h_\odelta} \equals \pair{\one{1}}{\pok_\odelta}\\
\end{align}

\begin{align} \textbf{assert}\ \pair{\one{\delta}}{\pok_\odelta} &\equals \pair{\one{\bdelta}}{h_\odelta}\\
\end{align}

Substep 2.4: Re-set the commitment-of-$\delta$ for the next iteration. \begin{align} \label{eq:phase2-delta} \one{\delta} &\gets \one{\bdelta} \end{align}

Substep 2.5: Go back to Step 2.

The next steps will verify $\outTwo_M$ is well-formed as per Eq. \ref{eq:mpc-phase2-output} and derived from the commitment-of-$\delta$ arrived at in Eq. \ref{eq:phase2-delta} from the verification above.

Step 3: Parse $\outTwo_M$: \begin{align} \label{eq:parsed-qp} \left( D, \tilde{D}, \left(Q_j\right)_{j\in[\ell+1, m]}, \left(T_i\right)_{i\in[0, n-2]} \right) \parse \outTwo_M \end{align}

Step 4: Verify that $\outTwo_M$ contains the expected $\one{\delta}$ from Eq. \ref{eq:phase2-delta}: \begin{align} \textbf{assert}\ D \equals \one{\delta} &\wedge \textbf{assert}\ \tilde{D} \equals \two{\delta}\\
\end{align}

Step 5: Verify $Q_j\equals\uvwDeltaOneCol$ and $T_i=\tauNdelta$ using pairing checks against and $\one{\delta},\two{\delta}$, $\uvwOneCol$ and $\tauN$: \begin{align} \forall j\in[\ell+1,m], \pair{\uvwOneCol}{\two{1}} &\equals \pair{Q_j}{\two{\delta}}\\
\forall i\in[0,n-2], \pair{\tauN}{\two{1}} &\equals \pair{T_i}{\two{\delta}} \end{align}

Post-processing phase-1 and phase-2 into a [BGM17] $\prk$ and $\vk$

The [BGM17] $\prk$ from Eq. $\ref{eq:groth16-prk}$ and $\vk$ from Eq. $\ref{eq:bgm17-vk}$ can be publicly-computed from the phase-1 $\ptau(\tau,\alpha,\beta)$ in Eq. \ref{eq:ptau} and phase-2 $\outTwo(\delta)$ in Eq. \ref{eq:mpc-phase2-output}:

1. $\left(\one{\gu_j(\tau)},\one{\rv_j(\tau)}\right)_{j\in[0,m]}$ in the $\prk$ can be computed from the $\one{\tau^i}$’s in $\ptau(\tau,\alpha,\beta)$
2. $\left(\two{\rv_j(\tau)}\right)_{j\in[0,m]}$ in the $\prk$ can be computed from the $\two{\tau^i}$’s in $\ptau(\tau,\alpha,\beta)$ from Eq. $\ref{eq:ptau}$
3. $\left(\one{\frac{\lagr_i(\tau)(\tau^n - 1)}{\delta}}\right)_{i\in[0,n-2]}$ in the $\prk$ can be computed via a size-$n$ FFT on the $\one{\frac{\tau^i(\tau^n - 1)}{\delta}}$’s from $\outTwo(\delta)$, but right-padded with a bunch of $\one{0}$’s
4. $\left(\one{\beta\gu_j(\tau) + \alpha\rv_j(\tau) + \bw_j(\tau)}\right)_{j\in[0, \ell]}$ in the $\vk$ can be computed from the $\left(\one{\tau^i},\one{\alpha\tau^i},\one{\beta\tau^i}\right)$’s in $\ptau(\tau,\alpha,\beta)$

The rest of the $\prk$ and $\vk$ elements are already available in $\ptau(\tau,\alpha,\beta)$ and $\outTwo(\delta)$.

Conclusion

There is so much interesting work around Groth16 that I did not cover in this blog post:

• Celo’s optimistic out-of-order powers-of-$\tau$ ceremony²²
• Computing the powers-of-$\tau$ in asynchrony²³
• Groth16 linkage¹⁹
• Commit-carrying variants of Groth16 and distributed proving²⁴
• Groth16 proof aggregation via Snarkpack³
• Collaborative Groth16 proving when the witness is split amongst several provers²⁵
• Non-malleability
  • [BG18]²⁶ gives a non-malleability fix that increases the verifier time by 1 pairing
  • [ABPR20]²⁷ and[ABPR24]²⁸ have a more efficient fix
• Groth16 is weakly-simulation-extractable²⁹$^,$³⁰
• The security definition of re-randomizability

There are many other references the reader should check out:

• LambdaClass’s Groth16 overview³¹
• Mary Maller’s proof of BGM17²⁰
• Anca Nitulescu’s zkSNARK write-up³²

Lastly, I would’ve liked to but did not get to:

• Break down the knowledge-soundness proof of Groth16
• Give examples of QAPs for interesting relations (e.g., a range proof)

Example: Keyless blockchain accounts

I’ll describe a Groth16 use case deployed on the Aptos network: keyless accounts secured via a traditional Web2 account instead of a secret key or mnemonic, without relying on a MPC service custodying keys (i.e.: your blockchain account = your Google account).

The ZK relation $\relkeyless$ that needs to be proved is described in detail in AIP-61³³.

At a high-level, the relation checks various properties of a $\green{\mathsf{public\ statement}}$ using some $\orange{\mathsf{secret\ witness}}$ data:

1. There exists a valid signature $\sig$ under $\gpk$ from an OpenID Connect (OIDC) provider (e.g., Google) on a JSON Web Token (JWT) $\jwt$
2. The signed $\jwt$’s nonce field is set to be a commitment to an ephemeral public key (EPK) $\epk$
3. The user’s address $\addr$ is a commitment to the sub and aud fields in the $\jwt$, using a random $\pepper$ as a blinding factor
   • A pepper service is used to store each user’s peppers. This service authenticates users via the same JWT that is used in the ZK relation, requiring no additional keys or extra authentication.

More formally, $\relkeyless$ enforces the following checks: \begin{align} \label{eq:keyless-rel} \relkeyless\left(\begin{array}% \stmt = (\addr,\epk,\gpk);\\
\witn = (\jwt, \sig, \epkblinder, \pepper) \end{array}\right) = 1 \Leftrightarrow \begin{cases} \text{1. signature}\ \sig\ \text{verifies under}\ \gpk\ \text{on}\ \jwt \wedge {} \\
\text{2.}\ \jwt\text{["}\texttt{nonce}\text{"] =}\ H_1(\epk, \epkblinder) \wedge {} \\
\text{3.}\ \addr = H_2( \jwt\text{["}\texttt{sub}\text{"]}, \jwt\text{["}\texttt{aud}\text{"]}; \pepper ) \end{cases} \end{align}

If the blockchain validators successfuly verify a ZKP for $\relkeyless$, they can safely “delegate” signing rights for the account identified by $\addr$ to the ephemeral secret key (ESK) associated with $\epk$.

This is great because blockchain users can easily create such proofs after signing in with Google (say) in their favorite dapp or wallet. As a result, they can now authorize TXNs for their account identified by $\addr$ using their ESK! Importantly, they need not remember this ESK, since they can always generate a new one, sign back in and delegate signing rights to it. (For more resources on how this works, see this keyless accounts post.)

Some notes on the implementation:

• The $\relkeyless$ keyles relation from Eq. $\ref{eq:keyless-rel}$ is implemented in circom

  • circom is a popular DSL that generates an R1CS representation of the relation, and thus a QAP, whose satisfiability can be proven via Groth16.

• The $\relkeyless$ circom code is in aptos-labs/keyless-zk-proofs

• The QAP degree (i.e., # of R1CS constraints) $n$ is around 1.5 million

• The QAP size (i.e., # of R1CS variables) $m$ is around the same

• The # of non-zero entries across the three QAP polynomials is ~6.3 million

• Computing a Groth16 proof for $\relkeyless$ takes tens of seconds in the browser

• A proving service allows users to compute their proofs faster

• The proving service code is also in aptos-labs/keyless-zk-proofs

References