1
$\begingroup$

I have been going back and forth between part 2 and part 4 of the Explaining SNARKs series.

  • In part 2, it is claimed that Bob has an idea about the polynomial and want to test whether Alice knows it by sending her $(g, s.g, ..., s^d.g)$ and checking the answer $P(s).g$.

  • In part 4, it is claimed that now Alice return 2 polynomials $a' = P(s).g$ and $b'=\alpha P(s).g$ computed from $(g, s.g, ..., s^d.g)$ and $(\alpha.g,\alpha s.g, ..., \alpha s^d.g)$. But now Bob only check that $b'=\alpha.a'$ and that if it is the case then Alice knows with high probability $(c_0,...,c_d)$.

My question: What is the use of the d-KCA knowing that:

  • If Bob knows $P$ and the probability that Alice answers correctly without using P is very low, then the verifiability is ensured already.

  • If in the d-KCA, Alice sends back $a'=\beta .g$ and $b'=\beta \alpha .g$, we have $b'=\alpha . a'$. So if Bob only check that equality he can be fooled.

I am really wondering what I am missing...

$\endgroup$
2
$\begingroup$

Two points:

  • Bob does not know $P$ which is partly the point of the protocol.
  • Alice could respond with the $\alpha$-pair $(a',b') = (\beta g, \alpha\beta g)$, there is nothing wrong with that. This implies that her coefficients are $c_0=\beta, c_i=0$ for $i>1$.

However, this will only do her any good if her coefficients $(c_0, \cdots, c_d)$ actually present a solution to the QAP.

$\endgroup$
  • $\begingroup$ Thanks for your feedback. I read the QAP section but not yet the Pinocchio one. I might "get it" there. However, it is clearly mention in the last paragraph of part 2 that Bob has a knowledge of $P$: The rough intuition is that the verifier has a “correct” polynomial in mind, and wishes to check the prover knows it $\endgroup$ – Yohan Obadia Mar 25 '18 at 10:10
  • 1
    $\begingroup$ Bob does not know $P$ and in fact must not learn it -- this would defeat the purpose of the protocol. The passage you quote refers to something else and it isn't really relevant. The goal is for Alice to prove (1) that she knows coefficients $(c_0,\cdots, c_d)$ and (2) that these coefficients form a solution to a given problem (more on this in the QAP section). @YohanObadia $\endgroup$ – CRYPTONEWBIE Mar 26 '18 at 3:15
  • 1
    $\begingroup$ I need to dive more into the QAP section. It is this sentence that sent me on the wrong track. Great clear explanations ! $\endgroup$ – Yohan Obadia Mar 26 '18 at 12:29
1
$\begingroup$

All it proves is that Alice used ( g , s . g , . . . , s d . g ) and ( α . g , α s . g , . . . , α s d . g ) in the same linear combination.

Additional tests (explained later in their tutorial or this tutorial here) are required to ensure that the linear combination she resulting from a valid solution for our QAP

$\endgroup$
  • $\begingroup$ This additional tutorial is really good. Get's into other complementary details. Thanks for sharing ! $\endgroup$ – Yohan Obadia Mar 27 '18 at 7:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.