{%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 ```c++ 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.