TL;DR: The two elliptic curves implementation can be found here. We aim to construct an elliptic curve satisfying the following criteria: Prime order. Efficient group operations. Deterministc and efficient hash-to-curve encoding. Security level of 128 bits. Extension Field Selection

Link to the paper: https://eprint.iacr.org/2021/1167.pdf Link to the slides: https://hecmas.github.io/talk/fflonk-for-the-polygon-zkevm/ Link to some comments and optimizations: https://hackmd.io/-2oVDtk4TJGVWFAYvUoY1g?view Comparison to Other Protocols Protocol CRS/SRS Size Prover Comp. Proof Length Verifier Comp.

The post BN254 For The Rest Of Us constitutes the base point for this article, so I highly recommend reading it to get a solid background of the BN254 curve. This post will reuse some parts with an emphasy on the computational aspect of the optimal Ate pairing over the BN254 curve. For those with a poor background on Pairing-Based Cryptography (PBC) but with a decent background on Elliptic-Curve Cryptoraphy (ECC) I recommend reading the following resources in order: Pairings For Beginners. Pairing-Friendly Elliptic Curves of Prime Order. High-Speed Software Implementation of the Optimal Ate Pairing over Barreto–Naehrig Curves. Only after (and not before) you feel sufficiently comfortable with both PBC and ECC come back to this post and start to make sense out of it.

The post BLS12-381 For The Rest Of Us constitutes the base point for this article, so I highly recommend reading it to get a solid background of the BLS1-381 curve. This post will reuse some parts with an emphasy on the computational aspect of the optimal Ate pairing over such curve. For those with a poor background on Pairing-Based Cryptography (PBC) but with a decent background on Elliptic-Curve Cryptoraphy (ECC) I recommend reading the following resources in order: Pairings For Beginners. Constructing Elliptic Curves with Prescribed Embedding Degrees. BLS12-381: New zk-SNARK Elliptic Curve Construction. Only after (and not before) you feel sufficiently comfortable with both PBC and ECC come back to this post and start to make sense out of it. The full list of consulted resources can be found at the end of this post.

By Héctor and Tomer. This note comes out of a discussion with Markus, Tomer, Al, and Jordi. What others do Poseidon is a hash function instantiating a sponge construction using the Poseidon$^\pi$ permutation. The standard way to use the sponge construction is to carry over the output of one permutation call as input to the next. A widely used optimization, sometimes known as overwrite mode, is to truncate the top part of the permutation and only carry over the lower part to the next call. What we do In Polygon zkEVM, we are using a slightly modified version of this construction. The modification is in how we use the output of one permutation call as input to the next one. Rather than preserving the order of inputs between permutations, we carry over the four topmost elements of the last permutation output to be the bottom four elements of the next permutation’s input.

(Optimized) PCS of ShPlonk This PCS is composed by the following algorithms: $gen(d)$. The generator algorithm outputs $srs = ([1]_1, [x]_1, [x^2]_1,\dots,[x^{d-1}]_1,[1]_2,[x]_2)$ for a random (and secret) $x \in \mathbb{F}$. $com(f_i)$. Given a polynomial $f_i \in \mathbb{F}_{<d}[X]$, the committer algorithm outputs $[f_i(x)]_1$. $open({cm_i}_k,{S_i}_k,{r_i}_k; {f_i}_k)$. The opening algorithm works as follows, where $k$ is the number of committed polynomials, ${cm_i}_k$ are the alleged commitments to ${f_i}_k$, $T = {z_1,\dots,z_t}$ is the set of opening points, ${S_i}_k$ is the opening set for the $i$-th polynomial, and ${r_i}_k$ are the polynomials interpolating the alleged the openings. Assume for simplicity that $k=2$ and that $S_1 = {z_1}$ and $S_2 = {z_2}$.V sends a random challenge $\gamma \in \mathbb{F}$. P sends $W = [(f/Z_T)(x)]_1$, where: $$ f(X) = (X-z_2)(f_1(X) - r_1(X)) + \gamma (X-z_1)(f_2(X) - r_2(X)).$$ In the normal batched KZG, V would stop here and simply use pairings to check the correctness. In ShPlonk, however, there is one extra round to reduce verifier complexity. V sends a random evaluation point $z \in \mathbb{F}$. P sends $W' = \left[\frac{L(x)}{(z-z_2)(x-z)}\right]_1$, where: $$ L(X) = (z-z_2)(f_1(X) - r_1(z)) + \gamma (z-z_1)(f_2(X) - r_2(z)) - Z_T(z) \frac{f(X)}{Z_T(X)}.$$ This protocol improves the original shPlonk, by one verifier scalar multiplication, by normalizing the definition of $L$ dividing it by $(z-z_2)$. Notice that $L(z) = f(z) - f(z) = 0$. TOFINISH. verifier check

Terminology & Notation We consider $\mathbb{F}$ a finite field of prime order $p$, i.e., $\mathbb{F} = \mathbb{Z}_p$. For a given integer $n$, we denote by $[n]$ the set of integers ${1,...,n}$. We explicitly define the multiplicative subgroup $H\subset\mathbb{F}$ as the subgroup containing the $n$-th roots of unity in $\mathbb{F}$, where $\omega$ is a primitive $n$-th root of unity and a generator of $H$. That is, $$ H = {\omega, \dots, \omega^{n-1}, \omega^n = 1}. $$ We denote by $\mathbb{F}_{<n}[X]$ the set of univariate polynomials over $\mathbb{F}$ of degree strictly smaller than $n$.

TODO: Explain why these books are in this list in detail. :::info I will use the following colors to show my progress with the books: :large_blue_circle: Blue means that I have read the book. :red_circle: Red means that I am in progress. :black_circle: Black means that I have not started yet but I am willing to. :::

Multiplicative Subgrup: $$ H = {\omega, ... , \omega^{n-1}, \omega^n = 1} $$ Involved Vectors: $$ \boldsymbol{f} = (f_1, f_2, \dots, f_{n}) \in \mathbb{F}^n $$ $$ \boldsymbol{t} = (t_1, t_2, \dots, t_n) \in \mathbb{F}^n $$