Adding zero-knowledge into PLONK

Disclaimer: This documentation was written on sometime in 2020. It is intended to give readers a high-level understanding. The codebase is the canonical source of truth, and over time this document might fall behind the implementation details of the code.

In order for PLONK to be honest-verifier zero-knowledge, we require witness indistinguishability. A verifier, when provided with a randomly-generated proof transcript and a set of random blinding factors, should be able to derive a satisfying witness, where the proof transcript is indistinguishable from a transcript generated with a structured witness.

This requires the addition of 2 random blinding factors into each witness polynomial, and 3 for the permutation polynomial (the permutation polynomial is evaluated at two distinct points vs one for the witnesses).

For Turbo Plonk, each witness requires 3 random blinding scalars, like the permutation polynomial they are evaluated at two distinct points.

In the paper, we add zero-knowledge by generating random degree-2 and degree-3 polynomials, and compute the product of these with the vanishing polynomial

$Z_H(X)$ . E.g. for the permutation polynomial

$z(X)$, we compute the 'blinded' polynomial

$z^{\prime }(X)$ where

$$z^{\prime }(X)=z(X)+(r_1+r_{2}X+r_3{X}^2)Z_H(X)$$

The problem with this approach

The subgroup

$H$ is of order

$n$. Plonk proofs are computed using a pairing-friendly elliptic curve defined over some prime field

${\mathbb{F}}_q$, generating a prime-order subgroup of order

$r$.

For efficiency reasons, we define the subgroup

$H$ to be the n'th roots of unity of

${\mathbb{F}}_r$.

We use elliptic curves specifically constructed such that

${\mathbb{F}}_r$ has real roots of unity for a large range of powers of two.

E.g. the BN254 curve that we use, has valid roots of unity for al

$2^i$ roots of unity,where

$i$ comes from the range

$[0,...,2^{30}]$

This restriction forces the circuit size,

$n$, to be a power of two.

The addition of random degree-2 blinding polynomials will increase the degree of the permutation polynomial

$z(X)$ to be

$n+2$

To perform fast fourier transforms of

$z(X)$, we need a set of unique evaluation points that is at least 4x larger than the polynomial's degree (because

$z(X)$ is involved in a product of 4 polynomials). The number of evaluation points must also be a power of two for a radix-2 FFT

If

$z(X)$ is degree

$n+2$, this requires an evaluation domain that is 8n. If

$z(X)$ was degree

$n$, the evaluation domain would be 4n (which is currently what we use)

To summarise: adding zero knowledge in this manner would double the evaluation domain size of the FFT transformations required by the prover

The plan to add efficient zero-knowledge

Instead of increasing the degree of our witness polynomials, we instead modify the vanishing polynomial

$Z_H(X)$ to not include 3 roots of unity.

For example, consider a subgroup

$H$ with generator

$\omega$ and order

$n$. If we cut the last 3 roots out of the vanishing polynomial, we get a new 'vanshing' polynomial

$Z_H^{\prime }(X)$:

$$Z_H^{\prime }(X)=\frac{Z_H(X)}{(X-{\omega }^{n-1})(X-{\omega }^{n-2})(X-{\omega }^{n-3})}$$

We can now fill the final 3 gates of our circuit with random witnesses and still produce a satisfying proof.

Consider a Plonk circuit with

$x$ gates and a width of u (where width defines the number of distinct wires per Plonk gate. Standard Plonk has a width of 3, Turbo Plonk has a width of 4). We define the subgroup order of

$H$,

$n$, to be the smallest power of two that is

$\ge (x+3)$. The witness polynomials

$W_i(X)$ are defined as

$$W_i(X)=\sum _{j=1}^x{a}_{i,j}{L}_j(X)$$

Where

$a_{i,j}$ is value of the

$i$'th wire for gate

$j$.

$L_j(X)$ is the

$j$'th Lagrange polynomial, where

$$L_j({\omega }^k)={\delta }_{j,k}$$

We define our new zero-knowledge witness

$W_i^{\prime }(X)$ to be

$$\begin{array}{}\text{(1)}& W_i^{\prime }(X)=W_i(X)+\sum _{m=1}^3{r}_{i,m}{L}_{n-m}(X)\end{array}$$

Where

$r_{i,m}$ are randomly-generated blinding scalars.

Similarly, we can transform the permutation polynomial

$z(X)$ into

$z^{\prime }(X)$, where

$$\begin{array}{}\text{(2)}& z^{\prime }(X)=z(X)+\sum _{m=1}^3{r}_{u+1,m}{L}_{n-m}(X)\end{array}$$

Using the modified vanishing polynomial, all values of

$r$ can be chosen at random without affecting the ability to produce a satisfying proof

Note: To add randomness to witness polynomial

$W_i(X)$ and permutation polynomial

$z(X)$, we could also do

$$\begin{gathered} W_i^{\prime }(X)=W_i(X)+(r_{1}X+r_2)Z_H^{\prime }(X) \\ {z}^{\prime }(X)=z(X)+(r_3{X}^2+r_{4}X+r_5)Z_H^{\prime }(X) \end{gathered}$$
where

$r_1,\dots ,r_5\in {\mathbb{Z}}_q$ are randomly generated. However, since we are cutting 3 zeros out of the vanishing polynomial

$Z_H(X)$, we can directly add random scalars in the last 3 gates of the circuit. This results in a simpler form of the witness and permutation polynomials in lagrange basis form as shown in

$(1),(2)$.

Required modifications to barretenberg

• polynomial_arithmetic::divide_by_pseudo_vanishing_polynomial must be modified to support the modified form of
  $Z_H^{\prime }(X)$
• Update prover::execute_preamble_round to add randomness into the witness polynomials
• Update permutation_widget::compute_round_commitments (in prover/proof_system/widgets/random_widgets/permutation_widget_impl.hpp) to add randomness into the permutation polynomial
• Update polynomial_arithmetic::get_lagrange_evaluations such that the vanishing polynomial returned is the new modified vanishing polynomial
• Rename divide_by_pseudo_vanishing_polyonmial to divide_by_vanishing_polynomial. Semantically,
  $Z_H^{\prime }(X)$ can be considered to be 'almost' the vanishing polynomial of subgroup
  $H$, or the actual vanishing polynomial of set
  $H^{\prime }$. We check a circuit's constraints are satisfied relative to set
  $H^{\prime }$ and therefore
  $Z_H^{\prime }(X)$ should be considered to be the complete vanishing polynomial.
• The Plonk permutation argument has a dependence on the last lagrange polynomial that corresponds to a real gate. For example, this is currently
  $L_{n-1}(X)$. Our permutation argument validates that
  $z({\omega }^{n-1})=1$ using this polynomial. This will change to
  $L_{n-3}(X)$. This requires modifications to permutation_widget::compute_quotient_contribution and permutation_widget::compute_quotient_evaluation_contribution. In addition polynomial_arithmetic::get_lagrange_evaluations returns a struct lagrange_evaluations (in polynomial_arithmetic.hpp) with a member variable l_n_minus_1. We should rename this to l_end, and change polynomial_arithmetic::get_lagrange_evaluations to compute this value correctly (i.e. for some value
  $\zeta$, compute
  $L_{n-3}(\zeta )$). For consistency, the member variable l_1 should be renamed to l_start.

Ideally the above modifications should be performed in a generic manner, where the number of roots cut out of

$H$ is variable, and defined by a template parameter fed into the above methods. This means that, should the need arise to cut out more roots of unity, we won't have to repeat the above process a second time!

Add tests into polynomial_arithmetic_test.cpp that validates the following:

• Generate mock polynomials
  $A(X),B(X),C(X)$, where
  $A(X)B(X)-C(X)=0\text{ mod }{Z}_H^{\prime }(X)$ but
  $A(X)B(X)-C(X)\ne 0\text{ mod }{Z}_H(X)$
• Use divide_by_vanishing_polynomial to compute polynomial
  $T^{\prime }(X)=\frac{A(X)B(X)-C(X)}{Z_H^{\prime }(X)}$ and validate that
  $T(z)Z_H^{\prime }(z)=A(z)B(z)-C(z)$ for pseudorandom
  $z$
• Repeat for
  $T(X)=\frac{A(X)B(X)-C(X)}{Z_H(X)}$ and validate that
  $T(z)Z_H(z)\ne A(z)B(z)-C(z)$ (due to a nonzero remainder term that has not been computed)

Updating StandardComposer's quotient polynomial computation

The scalar multiplications performed by the prover are implemented using a work queue. The reason is to improve the performance of our web-based provers. Most internet browsers do not support multithreaded WASM - to utilize multi-threading in this context, we instead push computationally-heavy tasks into a work queue. We then, using our javascript SDK, spawn multiple processes (using multiple threads) to perform the tasks in the work queue.

Because of this, we don't want to change the underlying data structures utilized by the work queue, as any modifications of the data structure will require changes made to our javascript sdk.

We need to enable the following. When performing a work item of type SCALAR_MULTIPLICATION, have the ability to conditionally alter the number of points being multiplied.

In work_queue.hpp, in process_queue, we can see that we by default call pippenger_unsafe to perform a multiexponentiation of size n (which is equal to small_domain.size). We need to be able to call pippenger_unsafe over a size n + 1, without altering the work_item struct (line 23)

We can do this by utilizing the variable work_item::constant. This variable is normally used when performing fourier transforms via the work queue, so we can repurpose it.

When the prover is pushing tasks onto the work queue to compute the quotient polynoimal - we need to, when the width is 3, set work_item::constant to equal 1 for the final tasks pushed onto the queue (there will be 3).

In work_queue::process_queue we can then check the value of constant. If it is 1, we call pippenger_unsafe with a size parameter of small_domain.size + 1 instead of small_domain.size