{%hackmd theme-dark %}
# HVZK Fix in Plonk Prover
**Disclaimer:** This documentation was written on July, 2022. 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.

###### tags: `vulnerabilities` `Aztec Connect` `cryptography`

In the previous version of the Plonk paper, it was found that when we split the quotient polynomial into three parts: $t_{\textsf{low}}(X), t_{\textsf{mid}}(X), t_{\textsf{hi}}(X)$, these polynomials weren't blinded explicitly. This meant that the protocol as a whole wasn't HVZK (honest-verifier zero-knowledge). Ariel has edited the Plonk [paper](https://eprint.iacr.org/2019/953.pdf) to fix this by adding blinding coefficients to each of the $t_{\textsf{low}}(X), t_{\textsf{mid}}(X), t_{\textsf{hi}}(X)$ polynomials.

To summarise the fix, after we split the quotient polynomial $t(X)$, we get:
$$
t(X) = t'_{\textsf{low}}(X) + X^nt'_{\textsf{mid}}(X) + X^{2n}t'_{\textsf{hi}}(X)
$$
where the degrees of $t'_{\textsf{low}}(X), t'_{\textsf{mid}}(X), t'_{\textsf{hi}}(X)$ are strictly less than $n$. To blind these polynomials, the prover samples random scalars $\color{red}{r_1}, \color{red}{r_2} \leftarrow \mathbb{F}$ and computes:
$$
\begin{aligned}
t_{\textsf{low}}(X) &:= t'_{\textsf{low}}(X) + \color{red}{r_1}X^n \\
t_{\textsf{mid}}(X) &:= t'_{\textsf{mid}}(X) + \color{red}{r_2}X^n - \color{red}{r_1} \\
t_{\textsf{hi}}(X) &:= t'_{\textsf{hi}}(X) - \color{red}{r_2} \\
\end{aligned}
$$

Note that the random scalars are added such that the original quotient polynomial does not change, i.e.
$$
\begin{aligned}
& \ \ t_{\textsf{low}}(X) + X^nt_{\textsf{mid}}(X) + X^{2n}t_{\textsf{hi}}(X) \\
=& \ (t'_{\textsf{low}}(X) + \color{red}{r_1}X^n) + X^n (t'_{\textsf{mid}}(X) + \color{red}{r_2}X^n - \color{red}{r_1}) + X^{2n}(t'_{\textsf{hi}}(X) - \color{red}{r_2}) \\
=& \ (t'_{\textsf{low}}(X) + X^nt'_{\textsf{mid}}(X) + X^{2n}t'_{\textsf{hi}}(X)) + \color{red}{r_1}X^n + \color{red}{r_2}X^{2n} - \color{red}{r_1}X^n - \color{red}{r_2}X^{2n} \\
=& \ \ t(X).
\end{aligned}
$$

More generally for TurboPlonk and UltraPlonk, we have:
$$
\begin{aligned}
t(X) &= t'_{1}(X) + X^nt'_{2}(X) + X^{2n}t'_{3}(X) + X^{3n}t'_{4}(X) \\
&= t_{1}(X) + X^nt_{2}(X) + X^{2n}t_{3}(X) + X^{3n}t_{4}(X)
\end{aligned}
$$
where
$$
\begin{aligned}
t_{1}(X) &:= t'_{1}(X) + \color{red}{r_1}X^n \\
t_{2}(X) &:= t'_{2}(X) + \color{red}{r_2}X^n - \color{red}{r_1} \\
t_{3}(X) &:= t'_{3}(X) + \color{red}{r_3}X^n - \color{red}{r_2} \\
t_{4}(X) &:= t'_{4}(X) - \color{red}{r_3}. \\
\end{aligned}
$$

To summarise the changes due to bliding of the quotient polynomial parts:
1. The degrees of the polynomials $t_1(X), t_2(X), t_3(X)$ is now $n$ (i.e. $(n+1)$ coefficients).
2. We need to open the blinded polynomials $t_1(X), t_2(X), t_3(X), t_4(X)$.
3. Hence, the linearisation polynomial $r(X)$ and the opening polynomial $W_{\mathfrak{z}}(X)$ would change appropriately.

Note that the verification algorithm would remain the same.

### Splitting the Quotient Polynomial

In the current implementation, we have a single quotient polynomial `quotient_large` with $4n$ coefficients. While committing and opening the parts $t'_{1}(X), t'_{2}(X), t'_{3}(X), t'_{4}(X)$ of the quotient polynomial $t(X)$, we use the size-$n$ slices from the polynomial `quotient_large` without explicitly slicing the array. For example, the coefficients at the indices $[0,n)$ represent the polynomial $t'_{1}(X)$.

#### Approach 1

To incorporate the blinding terms necessary to compute $t_{1}(X), t_{2}(X), t_{3}(X)$ and $t_{4}(X)$, we need one additional coefficient in $t'_{1}(X), t'_{2}(X)$ and $t'_{3}(X)$. Now, since the vector `quotient_large` is of size $4n$, its not possible to gel in the blinding scalars directly. One way around this would be to increase the size of `quotient_large` to $4n+3$ such that:
$$
\underbrace{0 \ 1 \ 2 \ \dots \ (\color{red}{n})}_{t_1(X)} \ \ \underbrace{(n+1) \ \dots \ (\color{red}{2n+1})}_{t_2(X)} \ \ \underbrace{(2n+2) \ \dots \ (\color{red}{3n+2})}_{t_3(X)} \ \ \underbrace{(3n+3) \ \dots \ (4n+2)}_{t_4(X)}.
$$

The problem with this approach is that the computation of the quotient polynomial needs a contiguous memory of size $4n$. If we wish to insert the random blinding factors at the indices shown in red, we will need to do redundant copy and paste (of sizes $n$) of coefficients of `quotient_large` to make room for the blinding factors.

A related solution to avoid insertion of blinding factors directly in the `quotient_large` polynomial could be to define four fresh polynomials in memory: `quotient_polynomial_part_i` for $i\in\{1,2,3,4\}$ each of size $(n+1)$. First, we need to copy the data from `quotient_large` into the individual polynomials `quotient_polynomial_part_i` and then add a blinding factor at the $(n+1)$th coefficient of first `quotient_polynomial_part_{1,2,3}`. This would be slightly cleaner in terms of readability, but we still haven't avoided the redundant copy of data.

#### Approach 2

Other solution is to completely get rid of `quotient_large` and instead only work with individual parts of the quotient polynomial: `quotient_polynomial_part_i` for $i\in\{1,2,3,4\}$. For doing this, the main challenge is performing the division by $Z_H(X)$ and iFFT on the quotient polynomial to compute its coefficients. We need to modify the division and iFFT functions to work with the parts of the quotient polynomial instead of a single `quotient_large` polynomial.

We decided to go with this approach since its the most efficient, does not require any redundant copy of data, and makes the code more modular from a readability point of view.

### Code Changes

1. Quotient Polynomial:
- As mentioned in the Approach 2, the quotient polynomial is split into 4 separate polynomials

        proving_key->quotient_polynomial_parts[0]
        proving_key->quotient_polynomial_parts[1]
        proving_key->quotient_polynomial_parts[2]
        proving_key->quotient_polynomial_parts[3]

- The first three of these contain $(n+1)$ coefficients while the last one contains $n$ coefficients
- For Turbo and UltraPlonk, the $(n+1)$th coefficient in the first **three** polynomials is the blinding factor of quotient polynomials.
- For StandardPlonk, the $(n+1)$th coefficient in the first **two** polynomials is the blinding factor of quotient polynomials.
- The functions which used to compute the quotient polynomial $t(X)$ are now modified to do the computation using the four separate polynomials, instead of a single polynomial of $4n$ coefficients.
- `compute_quotient_contribution` in the widgets that computes the numerator of the quotient polynomial $t(X)$
- `divide_by_pseudo_vanishing_polynomial` to divide $t(X)$ by $Z_H^{\ast}(X)$
- `coset_ifft` to compute the coefficient form of $t(X)$
- `compute_linearisation_coefficients` that computes the linearisation polynomial $r(X)$
- `batch_open` that computes the opening polynomials $W_{\mathfrak{z}}(X)$ and $W_{\mathfrak{z}\omega}(X)$
- An important note: the $(n+1)$th coefficient of all relevant polynomials must be initialised to $0$.

2. Removing `quotient_mid` and related stuff:
- The computation of the quotient polynomial $t(X)$ was split in two domains: `mid_domain` of size $2n$ and `large_domain` of size $4n$
- This was done for efficiency reasons: some terms in the quotient polynomial had degree $2n$ and those terms could be accumulated using loops of size $2n$ (as opposed to size $4n$).
- However, this optimisation wasn't being used in practice and therefore it was due to be removed since a long time.
- To complify the core proof system code, we got rid of this optimisation. Thus, there is no `quotient_mid`, `mid_domain` or `use_mod_for_selectorfft` anymore.
3. Pippenger MSM Size:
- Note that adding the blinding factors the parts of quotient polynomials make the degrees of $t_1(X), t_2(X)$ and $t_3(X)$ $n$, i.e. they have $(n+1)$ coefficients.
- As a result, the linearisation polynomial $r(X)$ is also a degree-$n$ polynomial by definition.
- Similarly, the opening polynomial $W_{\mathfrak{z}}(X)$ is also a degree-$n$ polynomial.
- To commit to the polynomials $t_1, t_2, t_3, W_{\mathfrak{z}}$, we now perform a size-$(n+1)$ multi-scalar multiplication.
- Note that the remaining witness polynomials are still degree-$n$.
- Thus, we needed to update `barretenberg.js/prover.ts` to correctly set the MSM-size while committing to witness polynomials.