2
$\begingroup$

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?

$\endgroup$

2 Answers 2

2
+50
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

New contributor
Bolton Bailey is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
3
  • $\begingroup$ it's expected that all the parties involved should have an idea of what this program is for. - the QAP is generated also using the witness which is supposed to be a secret. So I am not sure if it's OK to leak knowledge about the witness which leaking knowledge about the QAP will lead to $\endgroup$
    – user93353
    Commented Jul 10 at 2:56
  • $\begingroup$ @user93353 the witness is $(a_{\ell+1},\dots , a_m)$, which is not an input to the Setup procedure. So where do you get the idea that the setup depends on it? $\endgroup$
    – Maeher
    Commented Jul 11 at 7:14
  • $\begingroup$ @Maeher I think you are right - $u_i, v_i, w_i$ are formed by multiplying the QAP with the witness & QAP itself doesn't contain info about the witness! Let me ponder over it for a while $\endgroup$
    – user93353
    Commented Jul 11 at 10:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.