# FFlonk Comments and Optimizations

## (Optimized) PCS of ShPlonk

This PCS is composed by the following algorithms:
1. $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}$.
2. $com(f_i)$. Given a polynomial $f_i \in \mathbb{F}_{<d}[X]$, the committer algorithm outputs $[f_i(x)]_1$.
3. $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\}$**.
1. V sends a random challenge $\gamma \in \mathbb{F}$.
2. 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.
3. V sends a random evaluation point $z \in \mathbb{F}$.
4. 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$.
5. TOFINISH. verifier check

## PCS of Fflonk

This PCS differs from the previous one in that the commitment to a set of polynomials $f_i \in \mathbb{F}_{<d}[X]$, is carried on by computing the polynomial:
$$
g(X) = f_1(X^t) + f_2(X^t)X + \dots + f_t(X^t)X^{t-1},
$$
and outputting $[g(x)]_1$.

### One Vector of Polynomials and One Evaluation Point

Assume $z = h^t$.

Then, to open $f_1,\dots,f_t$ at $\{f_1(z), \dots, f_t(z)\}$, open $g$ at $\{h, h\omega, h\omega^2,\dots,h\omega^{t-1}\}$, where $\omega$ is a primitive $t$-th root of unity. To this end, compute the following two sets:
\begin{align}
\bar{Z}' = roots_t(z) = \{h, h\omega,\dots, h\omega^{t-1}\}, \\
\bar{S} = \{f_1(z), f_2(z), \dots, f_t(z)\},
\end{align}
and compute the set:
$$
\bar{S}' = \bar{S}(\bar{Z}') = \{f_1(z) + f_2(z)h + \dots + f_t(z)h^{t-1}, \dots, f_1(z) + f_2(z)h\omega + \dots + f_t(z)(h\omega)^{t-1}\}
$$
and notice that $\bar{S}' = \{g(h),g(h\omega),\dots,g(h\omega^{t-1})\}$.

Finally, engage in the $open(cm,\bar{Z}',\bar{S}'; g)$ protocol.

### One Vector of Polynomials and Multiple Evaluation Points

Assume $z_1 = h_1^t, \dots, z_k = h_k^t$. Then, basically run the previous protocol on each of the evaluations points.

Then, to open $f_1,\dots,f_t$ at $\{[f_1(z_1), f_2(z_1), \dots, f_t(z_1)], \dots, [f_1(z_k), f_2(z_k), \dots, f_t(z_k)]\}$, open $g$ at $\{[h_1, h_1\omega,\dots, h_1\omega^{t-1}], \dots, [h_k, h_k\omega,\dots, h_k\omega^{t-1}]\}$, where $\omega$ is a primitive $t$-th root of unity. To this end, compute the following two sets:
\begin{align}
\bar{Z}' = roots_t(z) = \{[h_1, h_1\omega,\dots, h_1\omega^{t-1}], \dots, [h_k, h_k\omega,\dots, h_k\omega^{t-1}]\}, \\
\bar{S} = \{[f_1(z_1), f_2(z_1), \dots, f_t(z_1)], \dots, [f_1(z_k), f_2(z_k), \dots, f_t(z_k)]\},
\end{align}
and compute the set $\bar{S}' = \{[g(h_1),g(h_1\omega),\dots,g(h_1\omega^{t-1})], \dots, [g(h_k),g(h_k\omega),\dots,g(h_k\omega^{t-1})]\}$.

Finally, engage in the $open(cm,\bar{Z}',\bar{S}'; g)$ protocol.

### Multiple Vectors of Polynomials and Multiple Evaluation Points

Generalize the previous protocol and engage in the $open(\{cm_i\},\bar{Z}',\bar{S}'; \{g_i\})$ protocol. I don't write it to avoid crazy notation, but this is the one applied in the following section.

## Adding Zero-Knowledge (with Dummy Gates)

In the [PlonK](https://eprint.iacr.org/2019/953.pdf) paper, in the order for the protocol to be zero-knowledge, the authors add to some witness-related polynomial a blinding polynomial $b \in \mathbb{F}[X]$ as follows:
$$
a(X) := b(X)Z_H(X) + {\sum}_{i=1}^n w_iL_i(X).
$$
To guarantee zero-knowledge, the degree of this polynomial should be **at least** equal to the number of revealed evaluations of $a$ that the prover sends to the verifier in the opening phase of the KZG commitment scheme. This strategy ends up defining polynomials with degree $n + \deg(b)$, which is inefficient for practical scenarios in which $n$ is a power of two.

To avoid this issue, we proceed as follows. From now on, let $m$ be the circuit size (that is, the number of gates) and let $n$ be the closest power of two such that $n \geq m+4$.

### Wiring Polynomials

We add zero-knowledge to the wiring polynomials $a,b,c$ by sampling blinding factors $b_1,\dots,b_6 \in \mathbb{F}$ and defining:
\begin{align}
a(X) &:= {\sum}_{i=1}^m w_iL_i(X) + b_1L_{m+1}(X) + b_2L_{m+2}(X), \\
b(X) &:= {\sum}_{i=1}^m w_{m+i}L_i(X) + b_3L_{m+1}(X) + b_4L_{m+2}(X) , \\
c(X) &:= {\sum}_{i=1}^m w_{2m+i}L_i(X) + b_5L_{m+1}(X) + b_6L_{m+2}(X),
\end{align}
where note that $a(\omega^i)=b(\omega^i)=c(\omega^i)=0$ for all $i \in \{m+3,m+4,\dots,n\}$. In essence, we are adding **dummy gates** that will be satisfied by definition and not because of the circuit.

Now, let's look at the satisfiability of the following constraint, for each $x \in H$:
$$
q_L(x)a(x) + q_R(x)b(x) + q_O(x)c(x) + q_M(x)a(x)b(x) + q_C(x) + PI(x) = 0
$$
- For $i=1,\dots,m$ the constraint is satisfied if the associated values satisfy the given circuit. In fact, we can safely assume that the number of public inputs is lower than $m$, so the public input polynomial $PI$ evaluates to $0$ in the forthcoming cases.
- For $i=m+1$ the constraint becomes:
$$
q_L(\omega^{m+1})b_1 + q_R(\omega^{m+1})b_3 + q_O(\omega^{m+1})b_5 + q_M(\omega^{m+1})b_1\cdot b_3 + q_C(\omega^{m+1}) = 0,
$$
which is satisfied by setting all the selectors equal to $0$ at $\omega^{m+1}$. The same happens in the case $i=m+2$.
- For $i =m+3,\dots,n$ we simply set $q_C(\omega^i)=0$. Notice that while the rest of the selectors could evaluate to **any** value from $\mathbb{F}$ (without affecting the soundness of the protocol), so we set them to $0$ for simplicity of the exposition.

To summary, the only change we have to do with respect to the original protocol is to define the selector polynomials as follows:
$$
\begin{array}{c}
q_L(X) = {\sum}_{i=1}^{m} q_{L_i}L_i(X), \quad
q_R(X) = {\sum}_{i=1}^{m} q_{R_i}L_i(X), \quad
q_O(X) = {\sum}_{i=1}^{m} q_{O_i}L_i(X), \\[0.2cm]
q_M(X) = {\sum}_{i=1}^{m} q_{M_i}L_i(X), \quad
q_C(X) = {\sum}_{i=1}^{m} q_{C_i}L_i(X).
\end{array}
$$

### Grand-Product Polynomial

We add zero-knowledge to the grand-product polynomial $z$ by sampling blinding factors $b_7,b_8,b_9 \in \mathbb{F}$ and defining:
\begin{align}
z(X) := &~L_1(X)
+{\sum}_{i=1}^{m−1} \left(L_{i+1}(X) {\prod}_{j=1}^i \frac{(w_j + \beta \omega^j + \gamma)(w_{m+j} + \beta k_1 \omega^j + \gamma)(w_{2m+j} + \beta k_2 \omega^j + \gamma)}{(w_j + \beta \sigma^*(j) + \gamma)(w_{m+j} + \beta \sigma^*(m+j) + \gamma)(w_{2m+j} + \beta \sigma^*(2m+j) + \gamma)} \right) \\[0.1cm]
&~+ L_{m+1}(X) + b_7L_{m+2}(X) + b_8L_{m+3}(X) + b_9L_{m+4}(X) + \sum_{i=m+5}^n L_i(X).
\end{align}

Now, let's look at the satisfiability of the following constraint, for each $x \in H$:
\begin{align}
&(a(x) + \beta x + \gamma) (b(x) + \beta k_1 x + \gamma) (c(x) + \beta k_2 x + \gamma) z(x) \\
&-(a(x) + \beta S_{\sigma_1}(x) + \gamma) (b(x) + \beta S_{\sigma_2}(x) + \gamma) (c(x) + \beta S_{\sigma_3}(x) + \gamma) z(x\omega) = 0.
\end{align}
- For $i=1,\dots,m$ the constraints is satisfied if the $z$ polynomial is correctly constructed.
- For $i=m+1$ the constraint becomes:
\begin{align}
&(b_1 + \beta \omega^{m+1} + \gamma) (b_3 + \beta k_1 \omega^{m+1} + \gamma) (b_5 + \beta k_2 \omega^{m+1} + \gamma) \\
&-(b_1 + \beta S_{\sigma_1}(\omega^{m+1}) + \gamma) (b_3 + \beta S_{\sigma_2}(\omega^{m+1}) + \gamma) (b_5 + \beta S_{\sigma_3}(\omega^{m+1}) + \gamma) b_7 = 0,
\end{align}
which is not satisfied with overwhelming probability. Consequently, we should multiply both sides of the constraint by $(x-\omega^{m+1})$. The same goes for the cases $i=m+2,i=m+3$ and $i=m+4$, so we also multiply by $(x-\omega^{m+2}),(x-\omega^{m+3})$ and $(x-\omega^{m+4})$ as well.
- For $i =m+5,\dots,n$ the constraint turns out to be:
\begin{align}
(\beta \omega^{i} + \gamma) (\beta k_1 \omega^{i} + \gamma) (\beta k_2 \omega^{i} + \gamma) -(\beta S_{\sigma_1}(\omega^{i}) + \gamma) (\beta S_{\sigma_2}(\omega^{i}) + \gamma) (\beta S_{\sigma_3}(\omega^{i}) + \gamma) = 0,
\end{align}
which is satisfied by setting $S_{\sigma_1}(\omega^i) = \omega^i, S_{\sigma_2}(\omega^i) = k_1\omega^i$ and $S_{\sigma_3}(\omega^i) = k_2\omega^i$, i.e., the permutation $\sigma^*$ acts like the identity function for $i \in \{m+5,\dots,n\}$.

Moreover, we should add a constraint attesting that $z$ is equal to one at $\omega^{m+1}$ (since this is the point in which the "real" gates ends). Finally, notice that the $S_{\sigma_1},S_{\sigma_2},S_{\sigma_3}$ could evaluate to **any** value from $\mathbb{F}$ (without affecting the soundness of the protocol) for $i=m+1,\dots,m+4$, so we set them to $1$ for simplicity in their definition.

To summary, we must have to perform two changes. First, the new constraints of $Z$ become:
$$
\begin{align}
&L_1(X)(z(X)-1)) = 0, \\[0.1cm]
&[(a(X) + \beta X + \gamma) (b(X) + \beta k_1 X + \gamma) (c(X) + \beta k_2 X + \gamma) z(X) \\
&-(a(X) + \beta S_{\sigma_1}(X) + \gamma) (b(X) + \beta S_{\sigma_2}(X) + \gamma) (c(X) + \beta S_{\sigma_3}(X) + \gamma) z(X\omega)] \\
&\qquad (X-\omega^{m+1})(X-\omega^{m+2})(X-\omega^{m+3})(X-\omega^{m+4})= 0, \\[0.1cm]
&L_{m+1}(X)(z(X)-1)) = 0.
\end{align}
$$

Second, we define the sigma polynomials as follows:
$$
\begin{array}{c}
S_{\sigma_1}(X) = {\sum}_{i=1}^{m} \sigma^*(i)L_i(X) + \sum_{i=m+1}^n \omega^iL_i(X), \quad
S_{\sigma_2}(X) = {\sum}_{i=1}^{m} \sigma^*(m+i)L_i(X) + \sum_{i=m+1}^n k_1\omega^iL_i(X), \\[0.1cm]
S_{\sigma_3}(X) = {\sum}_{i=1}^{m} \sigma^*(2m+i)L_i(X) + \sum_{i=m+1}^n k_2\omega^iL_i(X).
\end{array}
$$

## Lagrange Polynomials

Keep in mind that Lagrange polynomials are different if points in which they are evaluated are distinct. For example, the Lagrange polynomial for $H$ satisfies, for $i \in [n]$:
$$
L_i(x) =
\begin{cases}
1 & \text{if } x = \omega^{i-1} \\
0 & \text{if } x = \omega^j, j \neq i-1
\end{cases}
$$
and moreover $L_i$ is a polynomial of degree $n-1$.

In contrast, the Lagrange polynomial $L_i^{(S_0)}$ satisfies, for $i\in[8]$:
$$
L_i^{(S_0)}(x) =
\begin{cases}
1 & \text{if } x = h_0\omega_8^{i-1} \\
0 & \text{if } x = h_0\omega_8^j, j \neq i-1
\end{cases}
$$
the Lagrange polynomial $L_i^{(S_1)}$ satisfies, for $i\in[4]$:
$$
L_i^{(S_1)}(x) =
\begin{cases}
1 & \text{if } x = h_1\omega_4^{i-1} \\
0 & \text{if } x = h_1\omega_4^j, j \neq i-1
\end{cases}
$$
and the Lagrange polynomial $L_i^{(S_2)}$ satisfies, for $i \in \{1,2,3\}$ and $j \in \{4,5,6\}$:
\begin{array}{cc}
L_i^{(S_2)}(x) =
\begin{cases}
1 & \text{if } x = h_2\omega_3^{i-1} \\
0 & \text{otherwise}
\end{cases}
&
L_j^{(S_2)}(x) =
\begin{cases}
1 & \text{if } x = h_3\omega_3^{j-1} \\
0 & \text{otherwise}
\end{cases}
\end{array}
or more explicitly:
\begin{array}{c}
L_i(X) := \frac{\omega^{i-1}}{n}\frac{X^n-1}{X-\omega^{i-1}}, \\[0.1cm]
L_i^{(S_0)}(X) := \frac{\omega_8^{i-1}}{8h_0^7} \cdot \frac{X^8 - h_0^8}{(X-h_0\omega_8^{i-1})}, \\[0.1cm]
L_i^{(S_1)}(X) := \frac{\omega_4^{i-1}}{4h_1^3} \cdot \frac{X^4 - h_1^4}{(X-h_1\omega_4^{i-1})}, \\[0.1cm]
L_i^{(S_2)}(X) := \frac{\omega_3^{i-1}}{3h_2^5-3h_3^3h_2^2} \cdot \frac{X^6 - (h_2^3+h_3^3)X^3 + h_2^3h_3^3}{(X-h_2\omega_3^{i-1})}, \\[0.1cm]
L_j^{(S_2)}(X) := \frac{\omega_3^{j-1}}{3h_3^5-3h_2^3h_3^2} \cdot \frac{X^6 - (h_2^3+h_3^3)X^3 + h_2^3h_3^3}{(X-h_3\omega_3^{j-1})}.
\end{array}

## Division by a Polynomial of the form $X^m - \beta$

Given a polynomial $p(X) = a_dX^d + \dots + a_1X + a_0 \in \mathbb{F}[X]$ of degree $d$ at least $m$ and a field element $\beta$, the quotient of the division $p(X)/(X^m-\beta)$ is the polynomial:
\begin{align}
q(X) := &~a_{d}X^{d-m} + a_{d-1}X^{(d-1)-m} + \dots + a_{d-(m-1)}X^{(d-(m-1))-m} + \\[0.2cm]
&+ (a_{d-m}+a_{d} \cdot \beta)X^{(d-m)-m} + \dots + (a_{d-(2m-1)}+a_{d-(m-1)} \cdot \beta)X^{(d-(2m-1))-m} + \\[0.2cm]
&+ (a_{d-2m}+a_{d-m}\cdot \beta + a_{d} \cdot \beta^2)X^{(d-2m)-m} + \dots + (a_{d-(3m-1)}+a_{d-(2m-1)}\cdot\beta + a_{d-(m-1)} \cdot \beta^2)X^{(d-(3m-1))-m} \\
&\qquad\qquad\qquad\qquad\qquad\qquad\quad~\vdots \\
\end{align}

Basically, $q$ is a polynomial with the $m$ leading coefficients equal to the $m$ leading coefficients of $p$; the following $m$ coefficients are of the form $a_i+a_j \cdot \beta$, with $j-i=m$; the following $m$ coefficients are of the form $a_i+a_j\cdot\beta + a_k \cdot \beta^2$, with $j-i=k-j=m$; and so on. Intuitively speaking, each $m$ coefficients of $q$, one jumps from the actual coefficient of $p$ with jumps of length $m$ until "is possible" from bot to top. Consequently, the last $m$ coefficients of $p$ are never used for $q$.

For instance, if $p(X) = \sum_{i=0}^{10} a_iX^i$ and $m=2$, then:
\begin{align}
q(X) := &~a_{10}X^8 + a_9X^7 + (a_8+a_{10}\beta)X^6 + (a_7+a_9\beta)X^5 + \\
&+(a_6+a_8\beta+a_{10}\beta^2)X^4 + (a_5+a_7\beta+a_9\beta^2)X^3 + \\
&+(a_4+a_6\beta+a_8\beta^2+a_{10}\beta^3)X^2 + (a_3+a_5\beta+a_7\beta^2+a_9\beta^3)X + \\
&+(a_2+a_4\beta+a_6\beta^2+a_8\beta^3+a_{10}\beta^4)
\end{align}

Note that if $d \leq 2m-1$, then $q$ is only composed of the $m$ leading coefficients of $p$.

### Alternative

function divideByVanishingCoset(p, n, b, p) {
  let q = Array(p.length).fill(0n);
  let r = [...p];
  for (let i = p.length - 1; i >= n; i--) {
    let leadingCoeff = r[i];
    if (leadingCoeff === 0n) continue;
    r[i] = 0n;
    r[i - n] = mod(r[i - n] + b * leadingCoeff, p);
    q[i - n] = mod(q[i - n] + leadingCoeff, p);
  }
  return [q, r];
}

We want to find polynomials $q$ and $r$ such that $p(X) = q(X)(X^n-\beta) + r(X)$ with $0 \leq \deg(r)<n$. The following observation is crucial:
\begin{align}p(X) &= 0 \cdot (X^n-\beta) + p(X) = 0 \cdot (X^n-\beta) + (p(X) - p_dX^d) + p_dX^d = \\ &= 0 \cdot (X^n-\beta) + (p(X) - p_dX^d) + p_dX^{d-n}X^d - \beta \cdot p_dX^{d-n} + \beta \cdot p_dX^{d-n} = \\ &= 0 \cdot (X^n-\beta) + (p(X) - p_dX^d) + p_dX^{d-n}(X^d - \beta) + \beta \cdot p_dX^{d-n} = \\ &=p_dX^{d-n} \cdot (X^n-\beta) + (p(X) - p_dX^d + \beta \cdot p_dX^{d-n}) \end{align}
The idea is to lower the degree of $r$ by correctly varying $q$ and $r$ while preserving the previous identity.

### Generalization to Multiple Polynomials

Given a polynomial $p(X) = a_dX^d + \dots + a_1X + a_0$ of degree $d$ at least $|T| = 18$ that is divisible by $Z_T$, the following algorithm gives the quotient of the division $p/Z_T$.

We start by noticing that:
$$
Z_T(X) = Z_{S_0}(X) \cdot Z_{S_1}(X) \cdot Z_{S_2}(X) = (X^8 - \mathfrak{z}) \cdot (X^4-\mathfrak{z}) \cdot (X^6 - \mathfrak{z}(1 + \omega)X^3 + \mathfrak{z}^2\omega)
$$

Then, we proceed as follows:
1. Divide $p$ by $Z_{S_0}$ to obtain the polynomial $q_0$ such that $q_0(X) \cdot Z_{S_0}(X) = p(X)$.
1. Divide $q_0$ by $Z_{S_1}$ to obtain the polynomial $q_1$ such that $q_1(X) \cdot Z_{S_1}(X) = q_0(X)$.

1. Split $Z_{S_2}(X) = (X^6 - \mathfrak{z}(1 + \omega)X^3 + \mathfrak{z}^2\omega)$ as the multiplication of $(X^3-\mathfrak{z})$ and $(X^3-\mathfrak{z}\omega)$. Then:
- Divide $q_1$ by $(X^3-\mathfrak{z})$ to obtain the polynomial $q_2$ s.t. $q_2(X) \cdot (X^3-\mathfrak{z}) = q_1(X)$.
- Divide $q_2$ by $(X^3-\mathfrak{z}\omega)$ to obtain the polynomial $q_3$ s.t. $q_3(X) \cdot (X^3-\mathfrak{z}\omega) = q_2(X)$.

The polynomial $q_3(X)$ satisfies $Z_T(X) \cdot q_3(X) = p(X)$.

###### tags: `PlonK`