Groth16 - Since the Circuit Specific Trusted Setup requires knowledge of the QAP, how does it not leak knowledge?

Question

In the Groth16 paper, Page 14, the terms below have to computed as part of the circuit specific trusted setup $$ \left ( \frac{\beta u_i(x)+ \alpha v_i(x)+ w_i(x)}{\gamma} ^{\ell}_{ i=0}, \frac{\beta u_i(x)+ \alpha v_i(x)+w_i(x)}{\delta} ^{m}_{i=\ell+ 1} \right)$$

All the $u_i, v_i$ & $w_i$ terms in this come from the QAP which is generated by the prover. So the QAP has to be known for generating these parts of the trusted setup.

So how is the QAP knowledge not leaked to the Circuit Specific Trusted Setup participants?

Answer 1

This seems to be a basic misunderstanding. Although the paper is actually quite clear on this. Let's recall some basics:

A language $\mathcal{L} \subseteq \{0,1\}^*$ is a set of "words" or, in the context of proof systems more commonly, "statements" $x$. An NP language $\mathcal{L}$ is generally defined by an efficient relation $\mathcal{R}$, such that $$\mathcal{L} = \{x\in\{0,1\}^*\mid \exists\; w\ldotp\; (x,w)\in\mathcal{R} \}$$ where $w$ is referred to as a "witness" of $x$.

What Groth16 would like to be, is a proof system for the language of satisfiable arithmetic circuits, which happens to be equivalent to a proof system for the language of satisfiable quadratic arithmetic programs.

In this setting, a statement $x$ would be a quadratic arithmetic program and a witness $w$ would be a satisfying assignment for that program.

Unfortunately it doesn't actually manage to do that, because it doesn't have a universal setup. So what does Groth16 actually do?

In Groth16 the Setup is for a specific quadratic arithmetic program, that defines the relation $\mathcal{R}$, statements $x$ are the publicly known inputs to this program and witnesses $w$ are the secret inputs to that program.

That is, purported statements are of the form $x = (a_1,\dots,a_\ell) \in \mathbb{F}^\ell$ and witnesses are of the form $w = (a_{\ell+1},\dots,a_m) \in \mathbb{F}^{m-\ell}$ and the specific NP relation for which Groth 16 proves something is defined by a bunch of polynomials $t(X)$ and $u_i(X), v_i(X), w_i(X)$ for $0\leq i \leq m$ as

$$\mathcal{R} := \{((a_1,\dots,a_\ell),(a_{\ell+1},\dots,a_m)) \in \mathbb{F}^\ell \times \mathbb{F}^{m-\ell} \mid \sum_{i=0}^m a_iu_i(X)\cdot\sum_{i=0}^m a_iv_i(X) = \sum_{i=0}^m a_iw_i(X)\} +h(X)t(X)\}$$

where for convenience of notation $a_0 =1$ and $h(X)$ is an arbitrary degree $n − 2$ quotient polynomial.

What all of this means, is that what the Setup algorithms receives as input, is not the witness and not even the statement, but a description of the NP-relation we're trying to generate proofs for. The NP relation is of course public anyway and therefore, nothing is being "leaked" here.

Answer 2

The QAP instance is known to the circuit-specific trusted setup creators. It is not the intention of the design of Groth '16 to prevent this trusted third party from learning this information (this is why we call this party trusted).

To elaborate, the zero-knowledge property of a zk-SNARK like Groth '16 is only meant to refer to the verifier, and refers specifically to the fact that they should not learn the prover's secret inputs to the program. The QAP itself represents some fact or program being proven, so it's expected that all the parties involved should have an idea of what this program is for.