Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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)$ ?
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.
