Polynomials — seen by OpenAI

Under the hood of zkSNARKs — PLONK protocol: Part 2

In the previous article of the PLONK series, we covered the core of the protocol, the KZG commitment scheme, and how polynomial linear independence can aid in evaluating multiple polynomials within a single equation.

Under the hood of zkSNARKs — PLONK protocol: Part 1

Here, I want to discuss another important optimization used in PLONK, which is related to the vanishing polynomial.

Vanishing Polynomial

Note: The explanations in this chapter are based on my understanding of the role of vanishing polynomials. If you notice any inaccuracies, I am more than happy to address and correct them.

In the previous article, I mentioned that polynomials are an efficient way to encode the states of a particular process into one function. Consider the naive example illustrated below: at state #1, the process has a value of -6; at state #2, the value changes to 2; at state #3, it changes to 162, and so on.

This concept can be applied to an example involving program execution. At a particular execution point, the program had a state value of -6, and at another point, a value of 852, and so on. In the context of zero-knowledge proofs, we aim to prove the correctness of a program’s execution or the validation of a fact. To achieve this, we need to capture all the states. Delving deeper into the context of zero-knowledge proofs, and PLONK in particular, we construct polynomials in such a way that their evaluation at all states equals zero (the next article will provide a very specific example). If a program takes 5 steps to execute something, this means that we would have a polynomial where the evaluation result is zero for each of these steps.

Here comes into play the vanishing polynomial — it is the simplest type of polynomial that equals zero when evaluated at all points from 1 to 5.

Vanishing polynomial for all x (1, … 5)

As you can see, if you pick any x from 1 to 5, the evaluation result will be zero. Why do we need it? Let’s say we have a polynomial P(x) that we need to prove:

Polynomial P(x) is also equal to zero at all given points from 1 to 5. Therefore, if we divide P(x) by Zh(x) using polynomial division, there should be no remainder in the result; the polynomial Zh(x) should ‘vanish.’ This indicates that the prover indeed has a polynomial that is zero for all the x from 1 to 5. In PLONK, the vanishing polynomial is used in several places, so if you are constructing a proof and, after applying the division where it is required, your polynomial has a remainder, it means that there are error(s) in your calculations.

Another reason why there should be no remainder after division is that the prover would not be able to construct the proof using the Common Reference String (CRS) from the Trusted Setup.

Division with reminder

If we have a remainder x² after the division, we cannot evaluate this on Elliptic Curves because they do not support a division operation. Alternatively, we can represent division as multiplication by the inverse, effectively raising to the power of (-1). The problem here is that the given CRS is calculated for positive power values:

Vanishing polynomial optimisation

Earlier, we stated that if a program requires 5 steps to compute or verify something, then we need to construct a vanishing polynomial that equals zero for all the corresponding states. On average, zk-SNARK programs may require 1 million steps (gates) to generate a proof. Consequently, for a prover to construct and use such a lengthy polynomial, there would be a significant impact on the prover’s performance, exemplified by a polynomial like (x−1)(x−2)…(x−1000000). The Groth16 protocol does exactly this. PLONK, on the other hand, utilizes multiplicative subgroups, which are also built on roots of unity. Does this sound complicated? I will explain it very simply by addressing the following points:

1. All calculations are performed using modular arithmetic in a finite field of some prime number p, for example, 23. This means there are only numbers from 0 to 22, and any computation that exceeds this range will be adjusted by the modulo 23 operation. The best visual explanation can be found at the link below. In real-world applications, we would use a much larger prime number for p.

The Animated Elliptic Curve

2. The program requires 5 steps to compute the proof. To use roots of unity for evaluation, we need to extend our program to 8 steps because 8 is the next power of two closest to 5 (since 2³=8), and there is no power of two that equals 5. Now our program will have 8 steps, but the last three will not affect the program’s state.

3. Unfortunately, we cannot remain consistent with the previous example of the finite field p=23, because this set has too few elements to cover all 8 steps of the program’s execution. Therefore, we must use a finite field of a higher order, such as p=73. Within this finite field, there should be a number (let’s name it omega — ω) such that ω⁸ equals 1. In the case of p=73, this number is 10.

4. Next, we need to generate other values using 10, which serves as a generator. These generated values are called roots of unity.

import galois
Fp = galois.GF(73)

omega = Fp.primitive_root_of_unity(8)
roots = [omega**i for i in range(8)]
print(roots)
# ---- roots ---
# [1, 10, 27, 51, 72, 63, 46, 22]

So now, instead of using indices from 1 to 8 for each program step, we use these values, and the resulting vanishing polynomial should appear as follows:

You may wonder why this polynomial is longer than the original one considered more efficient than the original one, where we used indices from 1 to 8. But there is a catch: it can be represented in a much shorter form:

line #1 — vanishing polynomial for 8 steps/gates; line #2 — generic formula for vanishing polynomial.

This is the vanishing polynomial that saves time for the prover during proof generation.

Additionally, using roots of unity as evaluation points has a performance benefit. In the protocol, there are number of polynomial multiplications, which are one of the performance bottlenecks for proof generation. The most efficient way to perform these multiplications is by using Fast Fourier Transforms (FFTs), and FFTs are feasible only when roots of unity are used as evaluation points. The video below provides some good insights into why this is the case:

This is all for now. In the next article, we will start to delve into the PLONK protocol.

Under the hood of zkSNARKs — PLONK protocol: part3