tl;dr: Inspired by a tweet¹, we explore whether, given (1) an R1CS and (2) some “powers-of-$\tau$”, we could construct a cryptographic proof that a Groth16 VK was derived from them. This should make it more efficient for folks to ensure that an on-chain VK corresponds to some published ZK circuit code (e.g., circom). Nonetheless, this is not sufficient: one should also verify that the VK was generated from several independent contributions in an MPC ceremony and that there exists a corresponding proving key that is consistent (e.g., has the same $\delta$ component, same QAP, etc.).

Background and notation

Mostly, assuming familiarity with Groth16 and its QAP/R1CS-based computational model.

We’ll be using additive group notation.

Powers-of-$\tau$

We use powers-of-$\tau$ to denote a bunch of group elements structured as follows: \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$.

QAPs

Mostly recall that ZK relation can be compiled into a quadratic arithmetic program (QAP); a set of $m+1$ polynomials of degree $\le n-1$ each. \begin{align} \label{eq:qap} \left(\gu_j(X),\rv_j(X),\bw_j(X)\right)_{j\in[0,m]} \end{align}

Recall that:

• $n$ is called either (1) the degree of the QAP or (2) the number of R1CS constraints.
• $m$ is called either (1) the size of the QAP or (2) the number of R1CS variables

[BGM17]

In practice, most folks use the [BGM17]² formulation of Groth16, which has a slightly different verification key (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 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: \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, except it lacks a $\gamma$ component and thus 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}

Protocol sketch

Let’s start by observing that given some ZK circuit code written in some zkDSL (e.g., circom or NoirLang, it is easy to compile it and obtain the QAP polynomials from Eq. $\ref{eq:qap}$.

A cry is heard: “But you said R1CS, not QAP!”. Yes, I did. But recall that they are one and the same.

Also, let’s for now assume that the $\ptau(\tau,\alpha,\beta)$ powers-of-$\tau$ from Eq. $\ref{eq:ptau}$ are available to the verifier. (We can think of compressing them later.)

Next, looking at the VK in Eq. $\ref{eq:bgm17-vk}$ observe that the $(\alphaOne,\betaTwo)$ components are trivial to prove correctness of, since they are part of $\ptau(\tau,\alpha,\beta)$.

For the $\deltaTwo$ component, for now, there is nothing we want to prove.

Again, not saying this protocol is sufficient to ensure security of a deployed VK. For example, as pointed out by levochka.eth, a trapdoored $\delta$ in the VK would allow an attacker to forge proofs.

Thus, the difficult component we must prove correctness of is the last one: \begin{align} \left( \uvwOne \right)_{j\in[0,\ell]} \end{align}

First, observe that the verifier, who has the QAP polynomials and the powers-of-$\tau$ can simply reconstruct this component³: \begin{align} \uvwOne &\equals \sum_{i=0}^{n-1} \left( \gu_{j,i}\cdot \one{\beta\tau^i} + \rv_{j,i}\cdot \one{\alpha\tau^i} + \bw_{j,i}\cdot \one{\tau^i} \right) \end{align} Here, $\gu_{j,i}$ denotes the $i$th coefficient of the $\gu_j(X)$ polynomial (same for $\rv_j(X)$ and $\bw_j(X)$).

In practice, the QAP polynomials are interpolated in Lagrange basis, so the equation above will look slightly different. But, for now, glancing over that.

Problem: The verification work above involves a size-$3n$ (or so) multi-scalar multiplication (MSM). Although it should work quite fast in practice, can we help the verifier do it asymptotically faster?

Idea (to be explored): If we can assume⁴ we have succinct, structured commitments to the vectors of $\one{\beta\tau^i}$’s, $\one{\alpha\tau^i}$’s, and $\one{\tau^i}$’s (e.g., AFGHO-style commitments⁵), then it may be possible to convince the verifier asymptotically faster (in terms of scalar multiplications in the group $\Gr_1$, rather than scalar operations in $\mathbb{F}$) by using an IPA-based MSM argument similar to $\mathsf{MIPP}_k$ in [BMM+19]⁶.

The difficulty will be that $\mathsf{MIPP}_k$ assumes that the scalars are structured as $(b^0, b^1, \ldots, b^{n-1})$, which is not the case here for our scalars (e.g., the $\gu_{j,i}$’s). This may be fixable though.

References