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(\{c{m}_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,
   $\{c{m}_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^{\prime }={\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+\cdots +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{array}{r}{\overline{Z}}^{\prime }=root{s}_t(z)=\{h,h\omega ,\dots ,h{\omega }^{t-1}\},\\ \overline{S}=\{f_1(z),f_2(z),\dots ,f_t(z)\},\end{array}$$
and compute the set:

$${\overline{S}}^{\prime }=\overline{S}({\overline{Z}}^{\prime })=\{f_1(z)+f_2(z)h+\cdots +f_t(z)h^{t-1},\dots ,f_1(z)+f_2(z)h\omega +\cdots +f_t(z)(h\omega {)}^{t-1}\}$$
and notice that

${\overline{S}}^{\prime }=\{g(h),g(h\omega ),\dots ,g(h{\omega }^{t-1})\}$.

Finally, engage in the

$open(cm,{\overline{Z}}^{\prime },{\overline{S}}^{\prime };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{array}{r}{\overline{Z}}^{\prime }=root{s}_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}]\},\\ \overline{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{array}$$
and compute the set

${\overline{S}}^{\prime }=\{[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,{\overline{Z}}^{\prime },{\overline{S}}^{\prime };g)$ protocol.

Multiple Vectors of Polynomials and Multiple Evaluation Points

Generalize the previous protocol and engage in the

$open(\{c{m}_i\},{\overline{Z}}^{\prime },{\overline{S}}^{\prime };\{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 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}_i{L}_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+\mathrm{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\ge 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{array}{rl}a(X)& :={\sum }_{i=1}^m{w}_i{L}_i(X)+b_1{L}_{m+1}(X)+b_2{L}_{m+2}(X),\\ b(X)& :={\sum }_{i=1}^m{w}_{m+i}{L}_i(X)+b_3{L}_{m+1}(X)+b_4{L}_{m+2}(X),\\ c(X)& :={\sum }_{i=1}^m{w}_{2m+i}{L}_i(X)+b_5{L}_{m+1}(X)+b_6{L}_{m+2}(X),\end{array}$$
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),q_R(X)={\sum }_{i=1}^m{q}_{R_i}{L}_i(X),q_O(X)={\sum }_{i=1}^m{q}_{O_i}{L}_i(X),\\ q_M(X)={\sum }_{i=1}^m{q}_{M_i}{L}_i(X),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{array}{rl}z(X):=& L_1(X)+{\sum }_{i=1}^{m-1}(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 }^{\ast }(j)+\gamma )(w_{m+j}+\beta {\sigma }^{\ast }(m+j)+\gamma )(w_{2m+j}+\beta {\sigma }^{\ast }(2m+j)+\gamma )})\\ & +L_{m+1}(X)+b_7{L}_{m+2}(X)+b_8{L}_{m+3}(X)+b_9{L}_{m+4}(X)+\sum _{i=m+5}^n{L}_i(X).\end{array}$$

Now, let's look at the satisfiability of the following constraint, for each

$x\in H$:

$$\begin{array}{rl}& (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{array}$$

• For
  $i=1,\dots ,m$ the constraints is satisfied if the
  $z$ polynomial is correctly constructed.
• For
  $i=m+1$ the constraint becomes:
  
  $$\begin{array}{rl}& (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{array}$$
  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{array}{r}(\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{array}$$
  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 }^{\ast }$ 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{array}{rl}& L_1(X)(z(X)-1))=0,\\ & [(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 )]\\ & (X-{\omega }^{m+1})(X-{\omega }^{m+2})(X-{\omega }^{m+3})(X-{\omega }^{m+4})=0,\\ & L_{m+1}(X)(z(X)-1))=0.\end{array}$$

Second, we define the sigma polynomials as follows:

$$\begin{array}{c}{S}_{{\sigma }_1}(X)={\sum }_{i=1}^m{\sigma }^{\ast }(i)L_i(X)+\sum _{i=m+1}^n{\omega }^i{L}_i(X),S_{{\sigma }_2}(X)={\sum }_{i=1}^m{\sigma }^{\ast }(m+i)L_i(X)+\sum _{i=m+1}^n{k}_1{\omega }^i{L}_i(X),\\ S_{{\sigma }_3}(X)={\sum }_{i=1}^m{\sigma }^{\ast }(2m+i)L_i(X)+\sum _{i=m+1}^n{k}_2{\omega }^i{L}_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{array}{ll}1& \text{if }x={\omega }^{i-1}\\ 0& \text{if }x={\omega }^j,j\ne i-1\end{array}$$
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{array}{ll}1& \text{if }x=h_0{\omega }_8^{i-1}\\ 0& \text{if }x=h_0{\omega }_8^j,j\ne i-1\end{array}$$
the Lagrange polynomial

$L_i^{(S_1)}$ satisfies, for

$i\in [4]$:

$$L_i^{(S_1)}(x)=\{\begin{array}{ll}1& \text{if }x=h_1{\omega }_4^{i-1}\\ 0& \text{if }x=h_1{\omega }_4^j,j\ne i-1\end{array}$$
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{array}{ll}1& \text{if }x=h_2{\omega }_3^{i-1}\\ 0& \text{otherwise}\end{array}& L_j^{(S_2)}(x)=\{\begin{array}{ll}1& \text{if }x=h_3{\omega }_3^{j-1}\\ 0& \text{otherwise}\end{array}\end{array}$$
or more explicitly:

$$\begin{array}{c}{L}_i(X):=\frac{{\omega }^{i-1}}{n}\frac{X^n-1}{X-{\omega }^{i-1}},\\ 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})},\\ 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})},\\ L_i^{(S_2)}(X):=\frac{{\omega }_3^{i-1}}{3h_2^5-3h_3^3{h}_2^2}\cdot \frac{X^6-(h_2^3+h_3^3)X^3+h_2^3{h}_3^3}{(X-h_2{\omega }_3^{i-1})},\\ L_j^{(S_2)}(X):=\frac{{\omega }_3^{j-1}}{3h_3^5-3h_2^3{h}_3^2}\cdot \frac{X^6-(h_2^3+h_3^3)X^3+h_2^3{h}_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_d{X}^d+\cdots +a_{1}X+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{array}{rl}q(X):=& a_d{X}^{d-m}+a_{d-1}{X}^{(d-1)-m}+\cdots +a_{d-(m-1)}{X}^{(d-(m-1))-m}+\\ & +(a_{d-m}+a_d\cdot \beta )X^{(d-m)-m}+\cdots +(a_{d-(2m-1)}+a_{d-(m-1)}\cdot \beta )X^{(d-(2m-1))-m}+\\ & +(a_{d-2m}+a_{d-m}\cdot \beta +a_d\cdot {\beta }^2)X^{(d-2m)-m}+\cdots +(a_{d-(3m-1)}+a_{d-(2m-1)}\cdot \beta +a_{d-(m-1)}\cdot {\beta }^2)X^{(d-(3m-1))-m}\\ & ⋮\end{array}$$

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}_i{X}^i$ and

$m=2$, then:

$$\begin{array}{rl}q(X):=& a_{10}{X}^8+a_9{X}^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{array}$$

Note that if

$d\le 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\le \mathrm{deg}(r)<n$. The following observation is crucial:

$$\begin{array}{rl}p(X)& =0\cdot (X^n-\beta )+p(X)=0\cdot (X^n-\beta )+(p(X)-p_d{X}^d)+p_d{X}^d=\\ & =0\cdot (X^n-\beta )+(p(X)-p_d{X}^d)+p_d{X}^{d-n}{X}^d-\beta \cdot p_d{X}^{d-n}+\beta \cdot p_d{X}^{d-n}=\\ & =0\cdot (X^n-\beta )+(p(X)-p_d{X}^d)+p_d{X}^{d-n}(X^d-\beta )+\beta \cdot p_d{X}^{d-n}=\\ & =p_d{X}^{d-n}\cdot (X^n-\beta )+(p(X)-p_d{X}^d+\beta \cdot p_d{X}^{d-n})\end{array}$$
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_d{X}^d+\cdots +a_{1}X+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)$.

2. 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)$.

3. 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