This post is inspired by “Why and How zk-SNARK Works: Definitive Explanation” by Maksym Petkus.

Proof that you know a polynomial

The last post explains a (over) simplified version of what ZK is. Also, we talked about how polynomials are secretly important. We will first develop a baby approach that alone is not useful. In the next post, we will build something interesting on top of this.

Problem statement

We have a Prover and a Verifier.

They both know a polynomial t(x).

And Prover wants to convince Verifier that they know a polynomial p(x) that is divisible by t(x). Since p(x) is special, Prover doesn’t want to tell what it is to Verifier.

Approach

  1. Verifier picks a random number s and sends it to Prover.
  2. Prover calculates p(s) and sends it back.
  3. Verifier checks if t(s) divides p(s).

Rationale

If t(x) really divides p(x), then t(s) must divide p(s). The converse is not true, but you can see the motivation for this approach.

Obviously, this approach has many issues. We will solve a few of them by applying homomorphic encryption.

Homomorphic encryption

We will use homomorphic encryption since we can multiply and add encrypted values without decrypting.

  1. Verifier picks the following:
    • $s$ a secret code
    • $(g, n)$ two random positive integers.
  2. Verifier calculates $g^{s^0} \pmod{n}, g^{s^1} \pmod{n}, \cdots$ and sends them to Prover.
  3. Prover calculates $g^{p(s)} \pmod{n}, g^{h(s)} \pmod{n}$ where $h(x) = p(x) / t(x)$ and sends it back.
  4. Verifier checks $g^{p(s)} = (g^{h(s)})^{t(s)} \pmod n$.

From here, I will omit $\pmod n$ whenever it is obvious.

It might seem unclear as to why we send $g^{s^i}$’s. This is because Prover can’t calculate $g^{p(s)}$ without it. For instance, assume $p(x) = x^2 + 3x + 4$.

Then, without ever knowing what $s$ is, Prover can calculate $g^{p(s)}$ by

\[\begin{align*} g^{p(s)} &= g^{s^2 + 3s + 4} \\ &= g^{s^2}g^{3s}g^{4} \\ &= g^{s^2}(g^{s^1})^3(g^{s^0})^{4}, \end{align*}\]

and Prover is given the values of $g^{s^2}, g^{s^1}, g^{s^0}$.

It might also seem strange that we calculated $h(x)$ that we didn’t calculate before. This is because there is no straightforward way of telling if $a$ divides $b$ when given $g^a$ and $g^b$.

It is obvious that one can easily do the same thing by using other practical encryption methods such as elliptic curves.