1
$\begingroup$

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?

$\endgroup$

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.