# 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'(X)$ where

$$z'(X) = z(X) + (r_1 + r_2X + r_3X^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(X)$:

$$Z'_H(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(X)$ to be

$$
W'_i(X) = W_i(X) + \sum_{m=1}^{3} r_{i, m}L_{n - m}(X)
\tag{1}
$$

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

Similarly, we can transform the permutation polynomial $z(X)$ into $z'(X)$, where

$$
z'(X) = z(X) + \sum_{m=1}^3 r_{u + 1, m}L_{n - m}(X)
\tag{2}
$$

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 $$
W'_i(X) = W_i(X) + (r_{1}X + r_2) Z^{\prime}_H(X) \\
z'(X) = z(X) + (r_3X^2 + r_4X + r_5) Z^{\prime}_H(X)
$$
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(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(X)$ can be considered to be 'almost' the vanishing polynomial of subgroup $H$, or the actual vanishing polynomial of set $H'$. We check a circuit's constraints are satisfied relative to set $H'$ and therefore $Z'_H(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(X)$ but $A(X)B(X) - C(X) \ne 0 \text{ mod } Z_H(X)$
* Use `divide_by_vanishing_polynomial` to compute polynomial $T'(X) = \frac{A(X)B(X) - C(X)}{Z'_H(X)}$ and validate that $T(z)Z'_H(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`