zkSNARKS - unable to understand the usage of polynomial to verify some condition

Question

From Vitalik Buterin's Blogpost - An approximate introduction to how zk-SNARKs are possible

From the sub-topic "Comparing a polynomial to itself", I understood till here

In other words, any polynomial that equals zero across some set is a (polynomial) multiple of the simplest (lowest-degree) polynomial that equals zero across that same set.

However, I am unable to figure out how he uses that to verify some condition.

This is the part I am having trouble understanding

if we have a polynomial that encodes Fibonacci numbers (so across $F(x+2) = F(x) + F(x+1)$ across $x = $ { $0, 1, ..., 98$}), then I can convince you that $F$ actually satisfies this condition by proving that the polynomial $P(x) = F(x+2) - F(x+1) - F(x)$ is zero over that range, by giving you the quotient $H(x) = \frac {F(x+2) - F(x+1) - F(x)}{Z(x)}$ where $Z(x) = (x - 0) * (x - 1) ... (x - 98)$

First of all, I don't understand what he means by "giving you the quotient" - what exactly is he going to give the verifier & how will the verifier verify it?

Answer 1

It means he will give $H(x)$, so that the verifier can compute $H(x)*Z(x)$ and verify that it is equal to $F(x+2) = F(x) + F(x+1)$. As polynomials this is obvious, because all we've done is divide and then multiply by the same thing ($Z(x)$), arriving back at the original polynomial. However, if we evaluate all these polynomials at a random point $x=s$, then all the above equations still hold, but now we're just multiplying and checking equality of numbers. That's where the succinctness of SNARKs comes from.

So the prover can provide $H(s)$ as well as $F(s), F(s+2), F(s+1)$, and the verifier can (pre-)compute $Z(s)$, and then use the equality $F(s+2) - F(s) - F(s+1) = H(s)*Z(s)$ to verify everything matches up. This is based on the fact that two polynomials of degree less than or equal to $n$ can agree on at most $n$ points (by the Schwartz-Zippel lemma). So this is a probabilistic proof of equality.

We need to go further though, because obviously if we know $s$, we can forge values that will verify. So we instead evaluate all the polynomials on an encrypted value $E(s)$ using homomorphic encryption.

Answer 2

If a polynomial $P(x)$ (think of it as a function that accepts input $x$ and returns an evaluation result) evaluates to zero for certain input values for $x$ (a very simple example could be $x=x_1, x_2, x_3$), then as stated in the first quoted passage in the question, $P(x)$ will be a multiple of a lowest-degree polynomial $Z(x)$ that is zero across those input values for $x$ (here it would be $Z(x)=(x-x_1)(x-x_2)(x-x_3)$). This means that if $P(x)$ is divided by $Z(x)$, the quotient (call it $H(x)$) will still be a polynomial. The prover computes $H(x)$ by actually performing the division, namely $P(x)/Z(x)$, and this $H(x)$ is sent from the Prover to the Verifier as the “Proof”. The Verifier then confirms that the product of $H(x)$ and $Z(x)$ is indeed equal to $P(x)$, and if so the Verifier accepts the proof. The Verifier needs to also confirm that $H(x)$ is actually a polynomial, and not some other type of function (for example, it should not be a rational function, which is a non-trivial fraction with polynomial numerator and denominator). In practice, this is pretty much confirmed by default due to the way that the Prover communicates or calculates $H(x)$. For example, if the protocol requires that the Prover sends over the coefficients of $H(x)$, then it is obvious that it is a polynomial. Or, if the protocol requires that the Prover computes $H(r)$ for a secret value $r$ (meaning that $H(x)$ is evaluated at $x=r$), then there will be a “Common Reference String” provided to the Prover that includes encodings (e.g., in the exponent of a group generator in a pairing friendly group) of powers of $r$ up to a highest power (e.g., ${g^{r}, g^{r^2}, g^{r^3}, g^{r^4}, g^{r^5}}$), so the Prover is forced to only propose a polynomial $H(x)$ (evaluated at $x=r$) with degree up to that highest power (in this simple example, 5).