Join Log in
Score:1
Max avatar Crypto

ZK-SNARK basics: knowing t(x), what prevents the prover from creating random h(x) to forge L, R, and O

fr flag
Max

After reading a number of ZK-SNARK explainers from here, here, and here, I still don't understand a few things.

The setup of the algorithm uses QAP to calculate polynomial P(x) = L(x) * R(x) - O(x), as well as target divisor polynomial t(x), to represent the generic form of the target computation. Then, to create a proof, the prover

  • Calculates P(x) = L(x) * R(x) - O(x) for the specific parameters of the target computation.
  • Calculates h(x) = P(x) / t(x).
  • Calculates h(s), L(s), R(s), and O(s) to send to the verifier. The verifier then uses these values to check if h(s) * t(s) = L(s) * R(s) - O(s), or that t divides P without remainder.

If the prover knows t(x), what prevents it from choosing a random h(x), calculate h(x) * t(x), and forge L(x), R(x), and O(x) with the right order? It will pass the "no-remainder" verifier check. It will still be a polynomial (linear combination of E(s^d)), so should satisfy the shift checks as well.

What am I missing?

54
1 + 0
Score:0
Vadym Fedyukovych avatar Crypto
in flag
Vadym Fedyukovych

Please let me acknowledge proper problem statements, in terms of QAP. Maybe omitting R1CS, which is not the point for this question.

Please remember (1) "efficient" (succinct) verification is the target of snarks, and (2) there are secrets (witness) "mixed-in" polynomials $L(), R(), O(), h()$. Two points are missing: (1) polynomials are evaluated at a random point $\tau$ hidden from prover (the "toxic waste"), and (2) elliptic curves and bilinear operation (pairing).

Polynomials evaluated at $\tau$ are sent for verification, as group elements. Verification equation is equivalent to one stated in the question, up to a negligible soundness error (probability) evaluated with Schwartz-Zippel lemma.

0 + 3
Max avatar
fr flag
Max
Sorry, it still doesn't answer my question. Let's assume the proper setup happened, the polynomials and hidden target points were shared, toxic waste was removed, etc. In the normal verification process, the prover will first calculate L, O, R from the target program with specific input/output parameters that it wants to prove, then calculate h = (L*R-O)/t, evaluate it, and send results to the verifier. However, what prevents a prover from first picking a random polynomial h'(), then calculating L', R', and O' so that L'*R'-O'=h'*t, and then sending 'forged' evaluation result at random point?
0
Reply
Vadym Fedyukovych avatar
in flag
Vadym Fedyukovych
We need to start from R1CS to see how all the variables/wires are mixed into $L(), R(), O()$ polynomials. It would only make sense to consider problems and their R1CS arithmetization such that public variables completely define the instance. Verifier would feed his copy of public variables/wires into the verification equation. Regarding your comment: prover can only pick (L, R, O) that would agree with public variables. Next, prover does not send h() polynomial, but group elements like $h(\tau) G_1$. Can I refer to Theorem 2, page 18, IACR 2016/260 preprint for such a general "what prevents"?
0
Reply
Max avatar
fr flag
Max
Thank you, this is helpful!
0
Reply
ธงชาติไทย
Elon Musk
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.