Arijit Dutta

@arijitdutta67

Joined on Mar 31, 2021

  • In this document, we try to answer the following questions: How the Inner Product Argument (IPA) Polynoimial Commitment Scheme (PCS) works? How are we going to use IPA PCS in Aztec 3? How Does the IPA PCS Work? We consider the IPA PCS described in Section 3 of the Halo paper. We don't need it to be zero-knowledge. In high level, this is because the IPA PCS will be used at the last stage of Aztec 3 (similar to the smart contract/root verifier as in Aztec connect). Notation: We denote vectors by bold letters, group elements by capital letters, and scalars by small letters. Multiplication of a scalar $m$ with a group element $G$ i.e., $G$ added to itself $m$ times, is denoted by $[m]G$.
     Like 3 Bookmark
  • The latest version of the Plonk paper (a note on this can be found here) differs slightly from the actual implementation (based on an older version, implementation follows this version for public inputs). In this project, we have implemented the latest version (we call this the simplified Plonk here and in the code). Branch: https://github.com/AztecProtocol/aztec2-internal/tree/ad/simplified-plonk Acknoledgement: This project would not have been possible without the help and support I have received from Suyash, Zac, and Ariel. A good starting point might be this document written by Suyash which gives an overview of the codebase. Overview of the Changes: In the simplified Plonk, the definition of the linearization polynomial $r(X)$ is changed in such a way that it verifies the commitments $[t_{lo}]1$, $[t{mid}]1$, and $[t{hi}]_1$ and evaluates to zero at point $\mathfrak{z}$. As a result, we do not have to include $\bar{r}=r(\mathfrak{z}) = 0$ in the transcript. This reduces the proof size. In the verifier side, to reduce the number of scalar multiplications, $r(X)$ is split into constant and non-constant terms as follows.
     Like  Bookmark
  • This is a brief note about my understanding of the prover's and verifier's algorithms in the Plonk 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, $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. $(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$. $(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:
     Like 1 Bookmark