{%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.

Zora created a 100% on-chain Nft marketplace with simple contract interfaces that make it relatively easy to integrate with Aztec Connect bridges. Here are some things we could build: Asks Sell Nfts with the Zora Asks Module. docsthe simplest case is to post an Nft for sale at a specific price buy NFTs with the fillAsk function just specify tokenId, contract address and price

1/24/2023A mechanism for people to purchase and sell ETH, LUSD, DAI or other assets directly on the Aztec rollup is highly desirable. This avoids Ethereum L1 transaction fees for depositing and withdrawing assets between Aztec and Ethereum. It is important to note that there are 2 types of accounts in Aztec, basic accounts and registered accounts. Basic accounts are just a private/public keypair. Registered accounts include distinct spending keys, an "alias" to identify accounts and some additional features. Registering an account requires a transaction on the network. You can read more about the two types of accounts here. Requirements A funded Aztec account to send funds to individual's Aztec accounts when on-ramping Aztec account(s) to receive funds when users are off-ramping. This can be done in multiple ways.create a unique aztec account for each user or withdrawal request. When that account receives funds, you know exactly who it came from.optionally, users send aztec transaction proofs to the service provider off-chain. The service provider validates the tx info, accepting or rejecting the transaction based on pre-determined acceptance criteria, before submitting to the Aztec sequencer. have 1 common recipient for all users. Users will have to reveal their pub key when sending funds to the off ramp account.

1/11/2023Spec What does this bridge do? Why did you build it? This bridge will allow users to deposit assets into Aztec from other L2 bridges supported by Connext as well as send assets from Aztec directly to L2s. Here is a simple bridge contract from the connext docs for reference. The Hop protocol could also be used for an Aztec-->L2 transaction, reference, but not for an L2-->Aztec since it doesnt support arbitrary message passing. The rest of this specs assumes using Connext, but Hop would be similar. What protocol(s) does the bridge interact with?

1/3/2023Spec What does this bridge do? Why did you build it? This bridge allows users to deposit and withdraw NFTs to/from Aztec Connect as well as send their NFTs to other bridge contracts. A user may want to send their NFT to another bridge contract because it may have additional functionality (swapping, minting, etc). What protocol(s) does the bridge interact with? ERC-721 contracts on Etheruem. ERC-721 contracts are the most widely used NFT standard. A bridge that supports 721 contracts should be able to handle most NFTs.

12/22/2022
Published on ** HackMD**