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

Question

I am reading this explanation of zkSnark written by Maksym Petkus - https://arxiv.org/pdf/1906.07221.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?

Answer 1

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).