Score:4

Make sure of Quadratic Arithmetic Program validity

dz flag

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)$ ?

Score:1
br flag

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.

upavloff avatar
dz flag
In the vidéo https://www.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
rozbb avatar
br flag
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?
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.