4
$\begingroup$

In the process of learning zk-SNARKs, I'm faced with this problem:

I understand why if the prover sends a polynomial $P$ that can be divided by $T$, the target polynomial, the prover knows a valid assignment. But I don't understand how the verifier makes sure that the prover actually sent a polynomial $P$ which matches the R1CS and not some polynomial multiplied by $T$ like: $P(x)=T(x)\times F(x)$ ?

$\endgroup$

1 Answer 1

1
$\begingroup$

Recall the QAP equivalence condition. If $r_1, \ldots, r_n$ are uniformly chosen elements in the field $\mathbb{F}$, and $\{u_i(X),v_i(X),w_i(X)\}_{i=1}^m$ are all degree $n-1$ polynomials in $\mathbb{F}[X]$ denoting the QAP representation of the circuit; then the arithmetic circuit is satisfied by the wire assignment $a_1, \ldots, a_m \in \mathbb{F}$ iff for all $j = 1,\ldots, n$, $$ \left(\sum_{i=1}^m a_i u_i(r_j)\right) \cdot \left(\sum_{i=1}^m a_i v_i(r_j)\right) = \left(\sum_{i=1}^m a_i w_i(r_j)\right) $$ Let $p(X)$ be the polynomial representing the above equality condition, i.e., the above holds iff $p(r_j) = 0$ for all $r_j$. This is equivalent to saying that the target polynomial $t(X) = \prod_j (X - r_j)$ divides $p(X)$, since $t(X) \mid p(X)$ iff the roots of $t(X)$ are a subset of the roots of $p(X)$.

Your question is: what if you set up your QAP-based SNARK using a malformed polynomial $p(X)$ that is not the QAP representation of the circuit, but still satisfies $t(X) \mid p(X)$. Can the verifier detect this?

The answer is: no, not generally. Let's take Groth16 as an example, which is a trusted-setup SNARK. The verifying key, assuming for the sake of argument that there are no public inputs, is 2 uniform group elements ($[\delta]_2$ and $e([\alpha]_1, [\beta]_2)$), which convey no information whatsoever about the circuit. So, if the verifier only has access to the verifying key, they have no introspection ability. Suppose that the verifier had access to the proving key too. There is a little more they can do. For example, they can check that the size of the proving key is the expected size (there are components of size $n-2$ and size $m$). But there's still no ability to tell whether the prover used this proving key for their proof.

There are ways to fix this, though. Groth16 can be setup using multiparty ceremonies, where you're guaranteed that the resulting keys are correct as long as 1 party is honest. Another solution is to use a non-trusted-setup SNARK such as Spartan, Aurora, or Brakedown. In these schemes, the setup can be done using public randomness. So if a verifier wants to check that the verification key they have corresponds to the circuit, they can simply run the setup procedure using the same randomness as the original setup, and check that the resulting verification key is identical.

$\endgroup$
2
  • $\begingroup$ In the vidéo youtube.com/watch?v=HInxj5qUIsk&t=556s the guy explains how you can have a trusted setup, but still be sure that it's about the right circuit $\endgroup$
    – upavloff
    Mar 21, 2023 at 8:52
  • $\begingroup$ Where in the video do they say that? The timestamp you linked describes Groth16 verification. As I mentioned above, you can simplify a bit by imagining the verification polynomial is 0, in the case the circuit has no public inputs. In this case, how is the verifier making sure that the verifying key comes from the alleged circuit? $\endgroup$
    – rozbb
    Mar 24, 2023 at 19: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.