Join Log in
Score:1
avatar Crypto

zkSNARKS: What prevents the prover from chosing a different polynomial than the one he is expected to know

et flag
user93353

I am reading this explanation of zkSnark written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf

Here the Prover knows a polynomial of degree 3, 2 of the solutions of the polynomial are 3 & 4. He has to prove to the verifier he knows such a polynomial without revealing to the verifier the 3rd solution.

This is the polynomial they use as an example - $P(x) = x^3 - 7x^2 + 12x$ This can be factored as $x(x-3)(x-4)$, so the 3rd solution is $x = 0$

$T(x) = (x-3)(x-4)$

$H(x) = x$ (only prover knows this)

$P(x) = H(x) . T(x)$

$E(c) = g^c \pmod p$.

In short, this is the protocol used

  1. Verifier chooses a random $s$, calculates $E(s^0), E(s^1), E(s^2), E(s^3)$ Sends these 4 values to prover without revealing s.

  2. Prover calculates $E(p(s))$ using different $E(s^n)$s. He also calculates $E(H(s))$ similarly without knowing $s$. He hands both to verifier

  3. Verifier calculates $T(s)$ & then raises $E(H(s))^ {T(s)}$. If $E(P(s))$ sent by prover matches with $E(H(s))^ {T(s)}$, then the protocol verifies successfully.

I understood the protocol in general. There are issues with it which they address later, but one issue which comes to my mind (which they don't address) is the following.

If prover doesn't know the actual polynomial (i.e. $x^3 - 7x^2 + 12x$), but just picks some random 3rd solution - i.e. $x = 2$ & he goes ahead with the above protocol steps as described, it will still verify with the verifier.

In which case, I am unable to figure out what exactly is the protocol trying to achieve?

70
0 + 0
Score:1
meshcollider avatar Crypto
gb flag
meshcollider

I cannot find that specific example $x^3 − 7x^2 + 12x$ in the linked document. But I think you have somewhat answered your own question here:

Here the Prover knows a polynomial of degree 3, 2 of the solutions of the polynomial are 3 & 4. He has to prove to the verifier he knows such a polynomial without revealing to the verifier the 3rd solution.

This is exactly what he is trying to prove here - that he knows a degree 3 polynomial, which has solutions 3 and 4. Proving knowledge of such a polynomial is not specific to one single polynomial - there are multiple such degree-3 polynomials with roots 3 and 4. All the proof does is prove knowledge of one of them.

If prover doesn't know the actual polynomial (i.e. $x^3 − 7x^2 + 12x$) but just picks some random 3rd solution - i.e. $x = 2$ & he goes ahead with the above protocol steps as described, it will still verify with the verifier.

This is because knowledge of a polynomial is the same as knowledge of its roots - the only degree-3 polynomial with the roots 3, 4, and 2 is $(x-2)(x-3)(x-4)$. So the prover is still proving that they know a degree-3 polynomial with roots 3 and 4, even if it isn't $x^3 − 7x^2 + 12x$. In that case they "know" the polynomial $(x-2)(x-3)(x-4)$ instead.

What must be emphasised is that this document slowly builds up to more interesting applications. This protocol of proving knowledge of a polynomial is just a building block, and on its own may seem a little useless. But the document explains later on how this "Knowledge of Polynomial" can be built upon, for example in section 4.4 and beyond. Usually, this is because we only actually care that a polynomial has a certain set of roots (which corresponds to certain conditions holding on the thing being proven in zero knowledge).

0 + 0
et flag
user93353
Thank you. I will come back this after I finish section 4.
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.