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

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?

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