1
$\begingroup$

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?

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – Max
    Jul 10, 2021 at 20:26
  • $\begingroup$ 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"? $\endgroup$ Jul 10, 2021 at 21:16
  • $\begingroup$ Thank you, this is helpful! $\endgroup$
    – Max
    Jul 12, 2021 at 19:21

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.