---
tags: Onboarding
---
# Notes on Plonk Prover's and Verifier's Algorithm
**Disclaimer:** This documentation was written on July, 2021. 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.
##### Author: Arijit
This is a brief note about my understanding of the prover's and verifier's algorithms in the [Plonk](https://https://eprint.iacr.org/2019/953.pdf) paper. The note directly jumps to Section 8.4 of the paper and tries to answer some questions which I had while going through the various steps of the algorithms. I would like to acknowledge the help and clarifications I got from Zac, Ariel, and Suyash in writing this note.
The goal of the prover is described in the language $R_{\text{snark}}(\lambda)$ given in Section 8.3 of the paper. In the polynomial setting, this boils down to proving knowledge of the wire polynomials $a(X), b(X)$, $c(X)$, and the permutation polynomial $z(X)$ such that,
1. $a(X)b(X)q_M(X) + a(X)q_{L} (X) + b(X)q_R (X) + c(X)q_O (X) + PI(X) + q_C (X) = 0$ holds for all $X \in H$, where $H$ is the set containing the roots of unity.
2. $(a(X) + βX + γ)(b(X) + βk_1 X + γ)(c(X) + βk_2 X + γ)z(X) - \\ (a(X) + βS_{σ1}(X) + γ)(b(X) + βS_{σ2}(X) + γ)(c(X) + βS_{σ3}(X) + γ)z(Xω) = 0$ holds for all $X \in H$.
3. $(z(X) − 1) L_1 (X)=0$ holds for all $X \in H$.
As explained in the paper, the first condition will validate the gate contraints (the witnesses satisfy the plonk circuit) and the second and third conditions will validate the copy constraints (all the connections of the plonk circuit are verified by the grand product argument). However, the prover should prove that the above conditions hold in zero-knowledge i.e. without revealing the polynomials $a(X), b(X)$,$c(X)$, and $z(X)$. To do so the prover proceeds as follows.
### Round 1:
The prover constructs the polynomials $a(X),b(X)$, and $c(X)$ with some randomizations. Then it computes the commitments of $a(X),b(X)$, and $c(X)$ as per the Kate's polynomial commitment scheme. Here the commitment ${[k]}_1$ to a polynomial $k(X)=\sum_i{k_iX^i}$ is defined as the evaluation of the polynomial at the unknown SRS point $x$ in the exponent of the generator $G_1$ of the first group i.e.,
\begin{align}
{[k]}_1 = (\sum_i{k_ix^i})G_1.
\end{align}
Note: The random parts of $a(X),b(X)$, and $c(X)$ are,
$$
b_1X+b_2, b_3X+b_4, b_5X+b_6,
$$
respectively. Note that they have zero contributions when the polynomials are evaluated at the roots of unity. This is due to the multiplication with the vanishing polynomial $Z_H(X) = X^n - 1$ which has all $n$ roots of unity as its roots.
Q: Why do we need two random scalars to randomize $a(X),b(X)$ and $c(X)$.
A: The prover needs to send the commitments to $a(X),b(X)$, and $c(X)$ and also their evaluations at $\mathfrak{z}$ to the verifier. Roughly, the two revelations costs two random scalars for the protocol to satisfy the special honest-verifier zero-knowledge (SHVZK) property.
### Round 2:
Like the wire polynomials, the permutation polynomial $z(X)$ is computed by adding some randomization. In Section 5 (Polynomial protocols for identifying permutations), it is explained what should be the value of $z(X)$ for each roots of unity. Those values are set by using the Lagrange bases $L_i(X)$s.
Q: Why do we need three random scalars to randomize $z(X)$.
A: Unlike $a(X),b(X)$, and $c(X)$, the permutation polynomial $z(X)$ has been used to evaluate two opening proof polynomials $W_{\mathfrak{z}}(X)$ and $W_{\mathfrak{z}\omega}(X)$. This costs three random scalars to ensure the SHVZK property of the protocol.
### Round 3:
Q: What is the quotient polynomial $t(X)$ and why it is computed?
A: The quotient polynomial $t(X)$ has four elements. The numerators of the four elements are from the three conditions given above that the prover has to satisfy. Each of them are divided by $Z_H(X)$ and added after some random scaling by $\alpha$ and $\alpha^2$. The fact that the prover has successfully computed a "valid" commitment to $t(X)$ will ensure that $t(X)$ does not have any $a_iX^{-i}$ term. This is because the SRS used to compute the commitment does not have any $x^{-i}G_1$ term.
This in turn proves that $Z_H(X)$ divides all the numerator i.e. the numerators evaluate to zero at every roots of unity. Hence the three conditions given above are satisfied.
Instead of computing commitment to $t(X)$, the prover breaks $t(X)$ into three parts $t_{lo}(X)$, $t_{mid}(X)$, and $t_{hi}(X)$ and computes their commitments. This is done because of the folloing reasons.
1. We want the max degree of our polynomials to be n.
2. Kate opening proof $W_{\mathfrak{z}}(X)$ computation (in terms of $r(X)$) would require committing to size 3n polynomials which is very inefficient.
### Round 4:
To prove the definition of $t(X)$, $a(X)$, $b(X)$, $c(X)$, $S_{\sigma1}(X)$, $S_{\sigma2}(X)$ are evaluated at a random challenge point $\mathfrak{z}$ which is generated non-interactively by Fiat-Shamir heuristic.
Q: Why every polynomial in $t(X)$ is not evaluated?
A: This is because of the linearization trick (described in page 18) where a partial evaluation of polynomials is done to prove an identity involving them. This is to reduce the communication cost of the prover.
Q: Why $z(X)$ is evaluated at a different point $\mathfrak{z}\omega$?
A: In $t(X)$, both $Z(X)$ and $Z(X\omega)$ appear. We do not evaluate $Z(X)$ to make use of the linearization trick and only evaluate $Z(X)$ at $\mathfrak{z}\omega$. As $Z(X)$ is opened in $\mathfrak{z}\omega$ instead of $\mathfrak{z}$, we need a separate opening polynomial $W_{\mathfrak{z}\omega}(X)$ for $Z(X)$ defined in Round 5.
### Round 5
Q: What is the linearization polynomial $r(X)$?
A: To simplify, let
\begin{align}
& t(x) = t_{lo}(X) + X^nt_{mid}(X) + X^{2n}t_{hi}(X) = \frac{l(X)}{Z_H(X)}.
\end{align}
This implies, $r(X) = l(X)_{par} - Z_H(\mathfrak{z})(t_{lo}(X) + \mathfrak{z}^nt_{mid}(X) + \mathfrak{z}^{2n}t_{hi}(X))$ is zero if it is evaluated at $\mathfrak{z}$. Here $l(X)_{par}$ has a mixed form of polynomials and evaluations at $\mathfrak{z}$.
Note that the verifier can calculate the commitment of $r(X)$ using the elements of the proof $\pi_{SNARK}$ generated so far i.e. $({[a]}_1, {[b]}_1, {[c]}_1, {[z]}_1,{[t_{lo}]}_1,{[t_{mid}]}_1,{[t_{hi}]}_1,\bar{a},\bar{b},\bar{c},\bar{s}_{\sigma1},\bar{s}_{\sigma2},\bar{z}_{\omega})$. Thus the prover does not have to send the commitment to $r(x)$ to prove that it vanishes at $\mathfrak{z}$.
Now let us observe $W_{\mathfrak{z}}(X)$. Let,
\begin{align}
W_{\mathfrak{z}}(X) = \frac{M(X)}{X - \mathfrak{z}}
\end{align}
If the prover can compute the commitment to $W_{\mathfrak{z}}(X)$, then it is verified that $(X - \mathfrak{z})$ divides $M(X)$ (As the SRS does not have negetive exponents of $x$). Now consider each part of $M(X)$. As $v$ is random, $(X - \mathfrak{z})$ divides each term. $(X - \mathfrak{z})$ divides $r(X)$ implies $r(\mathfrak{z})=0$. Similarly $(X - \mathfrak{z})$ divides $(a(X)-\bar{a})$ implies $\bar{a}$ is the evaluation of $a(X)$ at $\mathfrak{z}$.
>To show that if $(X - \mathfrak{z})$ divides $(a(X)-\bar{a})$, then $\bar{a} = a(\mathfrak{z})$.
>We have $(a(X)-\bar{a})=q(X)(X - \mathfrak{z})$. Putting $x=\mathfrak{z}$, we get $\bar{a} = a(\mathfrak{z})$.
>
This applies for other polynomials and their evaluations as well. In this way the commitment to $W_{\mathfrak{z}}(X)$ verifies every evaluations of the polynomials and also $r(\mathfrak{z})=0$.
As discussed above, we need a separate opening polynomial $W_{\mathfrak{z}\omega}(X)$ to validate the evaluation $\bar{z}_{\omega}$ of the polynomial $z(X)$ at $\mathfrak{z}\omega$.
Finally, the prover outputs commitments ${[W_{\mathfrak{z}}]}_1$, ${[W_{\mathfrak{z}\omega}]}_1$ to these two opening polynomials and construct the proof $\pi_{\text{SNARK}}$.
## Verifier's algorithm:
In steps 1 to 3, the verifier checks the sanity of different elements of $\pi_{\text{SNARK}}$. Steps 4 to 11 are the various steps that prepare the verifier for the pairing check.
Let $W_{\mathfrak{z}}(X) = \frac{M(X)}{X - \mathfrak{z}}$ and $W_{\mathfrak{z}\omega}(X) = \frac{N(X)}{X - \mathfrak{z}\omega}$. After rearranging we get,
\begin{align}
XW_{\mathfrak{z}}(X) &= M(X) + \mathfrak{z} W_{\mathfrak{z}}(X) \\
XW_{\mathfrak{z}\omega}(X) &= N(X) + \mathfrak{z}\omega W_{\mathfrak{z}\omega}(X)
\end{align}
Combining these two identities with the multi-point evolution challenge $u$ gives,
\begin{align}
X(W_{\mathfrak{z}}(X)+uW_{\mathfrak{z}\omega}(X)) = \mathfrak{z}W_{\mathfrak{z}}(X) + u\mathfrak{z}\omega W_{\mathfrak{z}\omega}(X) + M(X)+uN(X)
\end{align}
Step 12 checks the above identity in the exponent using pairing and all the commitments and the evaluations of polynomials sent by the prover. Using the polynomial commitments, the unknown SRS value $x$ is used instead of the indeterminate $X$ and accumulated in $F$. The components involving constant terms and evaluations are accumulated in $E$. This is similar to the batch verification of the Kate commitment scheme described in Section 3 of the paper.
This validates the opening commitments ${[W_{\mathfrak{z}}]}_1$, ${[W_{\mathfrak{z}\omega}]}_1$ and all the three statements to be proved by the prover are verified.

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**