Sin7Y Tech Review (28): Specification for Marlin

Arkworks for Marlin
Marlin
Fractal

R1CS

Zero-knowledge proof algorithm Marlin is a R1CS based proof system, that, given a coefficient matrix parameter

$I=(F,n,m,A,B,C)$ and a set of valid assignments

$z=(x,w)\in F^n$，among which x is public information, namely Instance and is private information, namely, witness if

$Az\circ Bz=Cz$is established, R1CS is established.

If we let

$z_A=Az,z_B=Bz,z_C=Cz$ the above formula can be transformed into

$z_A\circ z_B=z_C$。

Therefore, if we can prove that there are four vectors

$z_A,z_B,z_C,z$ that satisfy

$$\begin{gathered} z_A\circ z_B=z_C \\ {z}_A=Az \\ {z}_B=Bz \\ {z}_C=Cz \end{gathered}$$

R1CS is established.

Transition into Polynomial (efficiency)

Prepare

1. Vanish polynomial
   
   $$v_H(X)=X^{|H|}-1$$
2. Derivative of Vanish polynomal
   
   $${\mu }_H(X,Y)=\frac{v_H(X)-v_H(Y)}{X-Y}$$

It’s a non-zero value if and only if

$$X=Y$$

Define polynomial

1. Define polynomials（LDE）
   ${\hat{z}}_A(X),{\hat{z}}_B(X),{\hat{z}}_C(X)\in F^{<|H|+b}[X]$ for vectors
   $z_A,z_B,z_C$ satisfying that the value on the group H is consistent with the vector, where the order of the group
   $H$ are equal to the length of the vector (assuming they are both ), that is:
   
   $$\begin{gathered} {\hat{z}}_A(g^0)=z_A[0],{\hat{z}}_B(X)(g^0)=z_B[0],{\hat{z}}_C(X)(g^0)=z_C[0] \\ {\hat{z}}_A(g^1)=z_A[1],{\hat{z}}_B(X)(g^1)=z_B[1],{\hat{z}}_C(X)(g^1)=z_C[1] \\ ... \\ {\hat{z}}_A(g^{n-1})=z_A[n-1],{\hat{z}}_B(X)(g^{n-1})=z_B[n-1],{\hat{z}}_C(X)(g^{n-1})=z_C[n-1] \end{gathered}$$
   Add
   $b$ redundant point without exposing any information of
   $w$
2. Define polynomial（LDE）for vector
   $z=(x,w)$
3. Define a polynomial
   $\hat{x}(X)\in F^{<|H_{[\le |x|]}|}[X]$ for
   $x$,satisfying
   
   $$\begin{gathered} \hat{x}(g^0)=x[0] \\ \hat{x}(g^1)=x[1] \\ ... \\ \hat{x}(g^{|x|-1})=x[|x|-1] \end{gathered}$$
4. Define a polynomial for
   $w$
   
   $$\mathrm{\forall }\gamma \in H[\ge |x|]，\overline{w}:=\frac{w(\gamma )-\hat{x}(\gamma )}{v_{H[\le |x|]}(\gamma )}$$
   Define a polynomial
   $\hat{w}(X)$（LDE）for a vector
   $\overline{w}$，satisfying
   
   $$\begin{gathered} \hat{w}(g^{|}x|)=\overline{w}[|x|] \\ \hat{w}(g^{|x|+1})=\overline{w}[|x|+1] \\ ... \\ \hat{w}(g^{|H|-1})=\overline{w}[|H|-1] \end{gathered}$$

Then the polynomial

$\hat{z}(X)$is

$$\hat{z}(X)=\hat{w}(X)V_{H[\le |x|]}(X)+\hat{x}(X)$$

3. Define Polynomials for Matrices
   $A,B,C$（Holographic）
   In order to reduce the computational complexity for the verifier (see paper 5.2.1 ), we use a special form to represent the matrix. Below is an example using matrix A.
   

Define:

$$\begin{gathered} \widehat{row}(k):={\varphi }^{-1}(t_k) \\ \widehat{col}(k):={\varphi }^{-1}(t_k) \\ \widehat{val}(k):k_{-th}non-zerovalue \end{gathered}$$

Where

$t_k$ is the row index of the kth non-zero value of the matrix，

$${\varphi }^{-1}(t_k)：[|H|]\to H$$maps the index to the computational domain，and

$\widehat{val}(k)$ is the kth non-zero value of the matrix，which can be divisible by

$${\mu }_H(\widehat{row}(k),\widehat{row}(k)){\mu }_H(\widehat{col}(k),\widehat{col}(k))$$

Therefore, a polynomial can be expressed as

$$\hat{M}(X,Y)=\sum _{k\in K}{\mu }_H(X,\widehat{row}(k)){\mu }_H(Y,\widehat{col}(k))\widehat{val(k)}$$

Linearity check

In order to prove

${\hat{z}}_A(X)=A\hat{z}(X)$，define the polynomial

$$q(X)=r(a,X){\hat{z}}_A(X)-\sum _{k\in H}r(a,k)A(k,X)\hat{z}(X)$$

Which should satisfy

$$\sum _{X\in H}q(X)=\sum _{X\in H}(r(a,X){\hat{z}}_A(X)-\sum _{k\in H}r(a,k)A(k,X)\hat{z}(X))=0$$

The relationship among

${\hat{z}}_A(X),A,\hat{z}(X)$in the group H is as shown in the following figure

Now, we multiply a factor

$r(\alpha ,X)$for each element of

${\hat{z}}_A(X)$on group

$H$，then in order to ensure balance, we should multiply a factor

$r(\alpha ,X)$for the

$A\hat{z}(X)$which is as shown in the following figure

It can be seen that when the polynomial

$t(X)$traverses the value of group

$H$, the following is satisfied

$$\sum _{X\in H}q(X)=\sum _{X\in H}(r(a,X){\hat{z}}_A(X)-\sum _{k\in H}r(a,k)A(k,X)\hat{z}(X))=0$$

Likewise, we can also derive it from the formula

$$\begin{gathered} \sum _{X\in H}q(X)=\sum _{X\in H}(r(a,X){\hat{z}}_A(X)-\sum _{k\in H}r(a,k)A(k,X)\hat{z}(X)) \\ =\sum _{X\in H}r(a,X){\hat{z}}_A(X)-\sum _{X\in H}\sum _{k\in H}r(a,k)A(k,X)\hat{z}(X) \\ =\sum _{X\in H}r(a,X){\hat{z}}_A(X)-\sum _{k\in H}r(a,k)\sum _{X\in H}A(k,X)\hat{z}(X) \\ =\sum _{k\in H}r(a,k)({\hat{z}}_A(k)-\sum _{X\in H}A(k,X)\hat{z}(X)) \\ =?0 \end{gathered}$$
That is, if it can be proved that the accumulation of polynomials

$q(X)$on group

$H$ is 0, the linear relationship among

${\hat{z}}_A(X),A,\hat{z}(X)$is established.

AHP for R1CS

Common

Given a polynomial

$$\begin{gathered} {\hat{z}}_A(X),{\hat{z}}_B(X),{\hat{z}}_C(X)\in F^{<|H|+b}[X] \\ \hat{w}(X)\in F^{<|H[>|x|]|+b}[X] \\ {\widehat{row}}_A(X),{\widehat{row}}_B(X),{\widehat{row}}_C(X) \\ {\widehat{col}}_A(X),{\widehat{col}}_B(X),{\widehat{col}}_C(X) \\ {\widehat{val}}_A(X),{\widehat{val}}_B(X),{\widehat{val}}_C(X) \end{gathered}$$
Compute polynomial

$h_0(X)$ satisfying

$${\hat{z}}_A(X)\cdot {\hat{z}}_B(X)-{\hat{z}}_C(X)=h_0(X)v_H(X)$$
Generate random polynomials

$$s(X)\in F^{2|H|+b-1}[X],\sum _{k\in H}s(k)={\delta }_1$$

Prover

=> Prover
a. Commit to

${\hat{z}}_A(X),{\hat{z}}_B(X),{\hat{z}}_C(X),\hat{w}(X),h_0(X),s(X)$
b. Transcript.write

${\delta }_1,c{m}_{\ast }$

=> Oracle

Generate random numbers

$\alpha ,{\eta }_A,{\eta }_B,{\eta }_C$

=> Prover - sumcheck-1

Sumcheck for

$$\sum _{X\in H}s(X)+r(a,X)(\sum _M{\eta }_M{\hat{z}}_M(X))-(\sum _M{\eta }_M{r}_M(a,X)\hat{z}(X))$$
c. Compute polynomials

$h_1(X)$and

$g_1(X)$such that

$$s(X)+r(a,X)(\sum _M{\eta }_M{\hat{z}}_M(X))-(\sum _M{\eta }_M{r}_M(a,X)\hat{z}(X))=h_1(X)v_H(X)+X{g}_1(X)+{\delta }_1/|H|$$
d. Commit to

$h_1(X),g_1(X)$
e. Transcript.write

$cm\mathrm{\_}{h}_1,cm\mathrm{\_}{g}_1$
=> Oracle

Generate random number

${\beta }_1$

=> Prover - sumcheck-1
a. Compute

$s({\beta }_1),h_1({\beta }_1),g_1({\beta }_1),{\hat{z}}_A({\beta }_1),{\hat{z}}_B({\beta }_1),{\hat{z}}_C({\beta }_1),\hat{w}({\beta }_1)$
b. If we send these numbers to the verifier, the verifier needs to compute
       i.

$v_H({\beta }_1),v_{H[\le |x|]}({\beta }_1),r(\alpha ,{\beta }_1)$
       ii.

$\hat{z}({\beta }_1)=\hat{w}({\beta }_1)v_{H[\le |x|]}({\beta }_1)+\hat{x}({\beta }_1)$
       iii.

$$\begin{gathered} ={\eta }_A{r}_A(\alpha ,{\beta }_1)+{\eta }_B{r}_B(\alpha ,{\beta }_1)+{\eta }_C{r}_C(\alpha ,{\beta }_1) \\ ={\eta }_A\sum _{k\in H}r(\alpha ,k)\hat{A}(k,{\beta }_1)+{\eta }_B\sum _{k\in H}r(\alpha ,k)\hat{B}(k,{\beta }_1)+{\eta }_C\sum _{k\in H}r(\alpha ,k)\hat{C}(k,{\beta }_1) \\ =\sum _{k\in H}r(\alpha ,k)({\eta }_A\hat{A}(k,{\beta }_1)+{\eta }_B\hat{B}(k,{\beta }_1)+{\eta }_C\hat{C}(k,{\beta }_1)) \end{gathered}$$

Its computational complexity is

$\mathrm{\Omega }(|H||K|)$，therefore，this part of the calculation needs to be executed by the Prover as a proxy.

=> Prover -sumcheck-2

Sumcheck for

$\sum _{X\in H}r(\alpha ,X)({\eta }_A\hat{A}(X,{\beta }_1)+{\eta }_B\hat{B}(X,{\beta }_1)+{\eta }_C\hat{C}(X,{\beta }_1))$
a. Compute polynomials

$h_2(X)$ and

$g_2(X)$such that

$$r(\alpha ,X)({\eta }_A\hat{A}(X,{\beta }_1)+{\eta }_B\hat{B}(X,{\beta }_1)+{\eta }_C\hat{C}(X,{\beta }_1))=h_2(X)v_H(X)+X{g}_2(X)+{\delta }_2/|H|$$
b. Commit to

$h_2(X),g_2(X)$
c. Transcript.write

${\delta }_2,cm\mathrm{\_}{h}_2,cm\mathrm{\_}{g}_2$

=> Oracle

Generate random number

${\beta }_2$

=> Prover - sumcheck-2
a. Compute

$h_2({\beta }_2),g_2({\beta }_2)$
b. If we send these numbers to the verifier, the verifier needs to compute
       i.

$v_H({\beta }_2),r(\alpha ,{\beta }_2)$
       ii.

$\hat{A}({\beta }_2,{\beta }_1),\hat{B}({\beta }_2,{\beta }_1),\hat{C}({\beta }_2,{\beta }_1)$
Its computational complexity is

$\mathrm{\Omega }(|K|)$，therefore，this part of the calculation needs to be executed by Prover as a proxy.

=> Prover - sumcheck-3

Sumcheck for

$$\begin{gathered} {\eta }_A\hat{A}({\beta }_2,{\beta }_1)+{\eta }_B\hat{B}({\beta }_2,{\beta }_1)+{\eta }_C\hat{C}({\beta }_2,{\beta }_1) \\ =\sum _{k\in K}\sum _{M\in A,B,C}{\eta }_M\frac{v_H({\beta }_2)v_H({\beta }_1)\widehat{val}(k)}{({\beta }_2-{\widehat{row}}_M(k))({\beta }_1-{\widehat{col}}_M(k))} \end{gathered}$$
Define the polynomial

$$f_3(k)=\sum _{M\in A,B,C}{\eta }_M\frac{v_H({\beta }_2)v_H({\beta }_1)\widehat{val}(k)}{({\beta }_2-{\widehat{row}}_M(k))({\beta }_1-{\widehat{col}}_M(k))},k\in K$$
a. Compute polynomials

$h_3(x)$and

$g_3(x)$such that

$$\begin{gathered} f_3(X)=X{g}_3(X)+{\delta }_3/|K| \\ a(X)-b(X)f_3(X)=h_3(X)v_K(X) \end{gathered}$$
which can be combined as：

$a(X)-b(X)(X{g}_3(X)+{\delta }_3/|K|)=h_3(X)v_K(X)$

where

$$\begin{gathered} a(X)=\sum _{M\in A,B,C}{\eta }_M{v}_H({\beta }_2)v_H({\beta }_1)\widehat{val}(X)\prod _{N\in \{A,B,C\}exp\{M\}}({\beta }_2-{\widehat{row}}_N(X))({\beta }_1-{\widehat{col}}_N(X)) \\ b(X)=\prod _{M\in \{A,B,C\}}({\beta }_2-{\widehat{row}}_M(X))({\beta }_1-{\widehat{col}}_M(X)) \end{gathered}$$

b. Commit to

$h_3(x),g_3(x)$
c. Transcript.write

${\delta }_3,cm\mathrm{\_}{h}_3,cm\mathrm{\_}{g}_3$

=> Oracle

Generate random number

${\beta }_3$

=> Prover - sumcheck-3
a. Compute

$$\begin{gathered} h_3({\beta }_3),g_3({\beta }_3), \\ {\widehat{row}}_A({\beta }_3),{\widehat{row}}_B({\beta }_3),{\widehat{row}}_C({\beta }_3) \\ {\widehat{col}}_A({\beta }_3),{\widehat{col}}_B({\beta }_3),{\widehat{col}}_C({\beta }_3) \\ {\widehat{val}}_A({\beta }_3),{\widehat{val}}_B({\beta }_3),{\widehat{val}}_C({\beta }_3) \end{gathered}$$
b. Send to the verifier

Verifier

=> Verifier-sumcheck-3

a. Compute
       i.

$v_K({\beta }_3)$
       ii.

$$\begin{gathered} a({\beta }_3)=\sum _{M\in A,B,C}{\eta }_M{v}_H({\beta }_2)v_H({\beta }_1)\widehat{val}({\beta }_3)\prod _{N\in \{A,B,C\}exp\{M\}}({\beta }_2-{\widehat{row}}_N({\beta }_3))({\beta }_1-{\widehat{col}}_N({\beta }_3)) \\ b({\beta }_3)=\prod _{M\in \{A,B,C\}}({\beta }_2-{\widehat{row}}_M({\beta }_3))({\beta }_1-{\widehat{col}}_M({\beta }_3)) \end{gathered}$$
b. Verify

$$a({\beta }_3)-b({\beta }_3)({\beta }_3{g}_3({\beta }_3)+{\delta }_3/|K|)=?h_3({\beta }_3)v_K({\beta }_3)$$
If it passes the verification, it means that the value computed by the Prover

$$\begin{gathered} {\eta }_A\hat{A}({\beta }_2,{\beta }_1)+{\eta }_B\hat{B}({\beta }_2,{\beta }_1)+{\eta }_C\hat{C}({\beta }_2,{\beta }_1) \\ =\sum _{k\in K}\sum _{M\in A,B,C}{\eta }_M\frac{v_H({\beta }_2)v_H({\beta }_1)\widehat{val}(k)}{({\beta }_2-{\widehat{row}}_M(k))({\beta }_1-{\widehat{col}}_M(k))} \\ ={\delta }_3 \end{gathered}$$
is valid, then go to the previous level for verification.

=> Verifier-sumcheck-2

Recall the equality

$$r(\alpha ,X)({\eta }_A\hat{A}(X,{\beta }_1)+{\eta }_B\hat{B}(X,{\beta }_1)+{\eta }_C\hat{C}(X,{\beta }_1))=h_2(X)v_H(X)+X{g}_2(X)+{\delta }_2/|H|$$

a. Compute
       i.

$v_H({\beta }_2)$
b. Verify

$$r(\alpha ,{\beta }_2){\delta }_3=?h_2({\beta }_2)v_H({\beta }_2)+{\beta }_2{g}_2({\beta }_2)+{\delta }_2/|H|$$
If it passes the verification, it means that the value computed by the Prover

$$\begin{gathered} \sum _{X\in H}r(\alpha ,X)({\eta }_A\hat{A}(X,{\beta }_1)+{\eta }_B\hat{B}(X,{\beta }_1)+{\eta }_C\hat{C}(X,{\beta }_1)) \\ ={\delta }_2 \end{gathered}$$
is valid, then go to the previous level for verification.

=> Verifier-sumcheck-1

Recall the equality

$$s(X)+r(a,X)(\sum _M{\eta }_M{\hat{z}}_M(X))-(\sum _M{\eta }_M{r}_M(a,X)\hat{z}(X))=h_1(X)v_H(X)+X{g}_1(X)+{\delta }_1/|H|$$
a. Compute
      i.

$v_H({\beta }_1)$
      ii.

$r(\alpha ,{\beta }_1)$
      iii.

$v_{H[\le |x|]}({\beta }_1)$
      iv.

$\hat{z}({\beta }_1)=\hat{w}({\beta }_1)v_{H[\le |x|]}({\beta }_1)+\hat{x}({\beta }_1)$
b. Verify

$$s({\beta }_1)+r(a,{\beta }_1)(\sum _M{\eta }_M{\hat{z}}_M({\beta }_1))-{\beta }_2\hat{z}({\beta }_1))=?h_1({\beta }_1)v_H({\beta }_1)+{\beta }_1{g}_1({\beta }_1)+{\delta }_1/|H|$$
If it passes the verification，it means that the polynomials

${\hat{z}}_A(X),{\hat{z}}_B(X),{\hat{z}}_C(X)$ and

$\hat{z}(X)$ satisfy a linear relationship.

=> Verifier

Verify

${\hat{z}}_A({\beta }_1)\cdot {\hat{z}}_B({\beta }_1)-{\hat{z}}_C({\beta }_1)=h_0({\beta }_1)v_H({\beta }_1)$

Polynomial commitment

The protocol has carried out three rounds of interaction in total. The polynomials of each round of interaction commitment and the query points are as follows:

Sumcheck - 1

$${\beta }_1\to \{s({\beta }_1),h_1({\beta }_1),g_1({\beta }_1),\hat{w}({\beta }_1),{\hat{z}}_A({\beta }_1),{\hat{z}}_B({\beta }_1),{\hat{z}}_C({\beta }_1)\}$$

Sumcheck - 2

$${\beta }_2\to \{h_2({\beta }_2),g_2({\beta }_2)\}$$

Sumcheck - 3

$$\begin{gathered} {\beta }_3\to \{h_3({\beta }_3),g_3({\beta }_3),{\widehat{row}}_A({\beta }_3),{\widehat{row}}_B({\beta }_3),{\widehat{row}}_C({\beta }_3){\widehat{col}}_A({\beta }_3),{\widehat{col}}_B({\beta }_3),{\widehat{col}}_C({\beta }_3) \\ {\widehat{val}}_A({\beta }_3),{\widehat{val}}_B({\beta }_3),{\widehat{val}}_C({\beta }_3)\} \end{gathered}$$

Extended KZG10 (cross multi-poly)

Optimization

Sum(s(X)) = 0

Generate random polynomials

$$s(X)\in F^{3|H|+2b-2}[X],\sum _{k\in H}s(k)=0$$
Then, forsumcheck - 1

Reduce sumcheck

According to the optimization mentioned in the paper COS20. Claim6.7（Fractal）we make

$$\begin{gathered} r(X,Y)={\mu }_H(X,Y) \\ {r}_M(X,Y)=M^{\ast }(Y,X) \\ {M}^{\ast }(X,Y)=\sum _{\alpha \in H}\sum _{b\in H}{L}_{\alpha ,H}(X)L_{b,H}(Y)M_{b,a}\cdot {\mu }_H(b,b) \end{gathered}$$
For matrices

$A,B,C$，the transformed matrices are

$$\begin{gathered} A_{a,b}^{\ast }=A_{b,a}\cdot \mu (b,b) \\ {B}_{a,b}^{\ast }=B_{b,a}\cdot \mu (b,b) \\ {C}_{a,b}^{\ast }=C_{b,a}\cdot \mu (b,b) \end{gathered}$$

Define polynomial

$t(X)$

$$t(X):=\sum _M{\eta }_M{r}_M(a,X)$$
Then, for sumcheck - 1，the formula becomes

$$\begin{gathered} \sum _{X\in H}s(X)+r(\alpha ,X)(\sum _M{\eta }_M{\hat{z}}_M(X))-(\sum _M{\eta }_M{r}_M(\alpha ,X)\hat{z}(X)) \\ =\sum _{X\in H}s(X)+\mu (\alpha ,X)(\sum _M{\eta }_M{\hat{z}}_M(X))-t(X)\hat{z}(X) \end{gathered}$$

Common

Given the polynomial

$$\begin{gathered} {\hat{z}}_A(X),{\hat{z}}_B(X),{\hat{z}}_C(X)\in F^{<|H|+b}[X] \\ \hat{w}(X)\in F^{<|H[>|x|]|+b}[X] \\ {\widehat{row}}_A(X),{\widehat{row}}_B(X),{\widehat{row}}_C(X) \\ {\widehat{col}}_A(X),{\widehat{col}}_B(X),{\widehat{col}}_C(X) \\ {\widehat{val}}_A(X),{\widehat{val}}_B(X),{\widehat{val}}_C(X) \end{gathered}$$
Compute polynomial

$h_0(X)$ satisfying

$${\hat{z}}_A(X)\cdot {\hat{z}}_B(X)-{\hat{z}}_C(X)=h_0(X)v_H(X)$$
Generate random polynomials

$$s(X)\in F^{2|H|+b-1}[X],\sum _{k\in H}s(k)={\delta }_1$$

Prover

=> Prover

a. Commit to

${\hat{z}}_A(X),{\hat{z}}_B(X),{\hat{z}}_C(X),\hat{w}(X),h_0(X),s(X)$
b. Transcript.write

${\delta }_1,c{m}_{\ast }$

=> Oracle

Generate random number

$\alpha ,{\eta }_A,{\eta }_B,{\eta }_C$

=> Prover-sumcheck - 1

Sumcheck for

$$\sum _{X\in H}s(X)+\mu (\alpha ,X)(\sum _M{\eta }_M{\hat{z}}_M(X))-t(X)\hat{z}(X)$$

a. Compute polynomials

$h_1(X)$ and

$g_1(X)$ such that:

$$s(X)+\mu (a,X)(\sum _M{\eta }_M{\hat{z}}_M(X))-t(X)\hat{z}(X))=h_1(X)v_H(X)+X{g}_1(X)+\text{sout}{\delta }_1/|H|$$
b. Commit to

$h_1(X),g_1(X)$
c. Transcript.write

$cm\mathrm{\_}{h}_1,cm\mathrm{\_}{g}_1$

=> Oracle

Generate random number

${\beta }_1$

=> Prover-sumcheck - 1

a. Compute

$s({\beta }_1),h_1({\beta }_1),g_1({\beta }_1),{\hat{z}}_A({\beta }_1),{\hat{z}}_B({\beta }_1),{\hat{z}}_C({\beta }_1),\hat{w}({\beta }_1)$
b. i. If we send these numbers to the verifier, the verifier needs to compute
      i.

$v_H({\beta }_1),v_{H[\le |x|]}({\beta }_1),r(\alpha ,{\beta }_1)$
      ii.

$\hat{z}({\beta }_1)=\hat{w}({\beta }_1)v_{H[\le |x|]}({\beta }_1)+\hat{x}({\beta }_1)$
      iii.

$t({\beta }_1)={\eta }_A{A}^{\ast }({\beta }_1,\alpha )+{\eta }_B{B}^{\ast }({\beta }_1,\alpha )+{\eta }_C{C}^{\ast }({\beta }_1,\alpha )$

Its computational complexity is

$\mathrm{\Omega }(|K|)$，Therefore, this part of the calculation needs to be executed by Prover as a proxy.

=> Prover - sumcheck-2

Sumcheck for

$$\begin{gathered} {\eta }_A{A}^{\ast }({\beta }_1,\alpha )+{\eta }_B{B}^{\ast }({\beta }_1,\alpha )+{\eta }_C{C}^{\ast }({\beta }_1,\alpha ) \\ =\sum _{k\in K}\sum _{M\in A^{\ast },B^{\ast },C^{\ast }}{\eta }_M\frac{v_H({\beta }_1)v_H(\alpha ){\widehat{val}}_{M^{\ast }}(k)}{({\beta }_1-{\widehat{row}}_{M^{\ast }}(k))(\alpha -{\widehat{col}}_{M^{\ast }}(k))} \end{gathered}$$
Define the polynomial

$$f_2(k)=\sum _{M\in A^{\ast },B^{\ast },C^{\ast }}{\eta }_M\frac{v_H({\beta }_1)v_H(\alpha ){\widehat{val}}_{M^{\ast }}(k)}{({\beta }_1-{\widehat{row}}_{M^{\ast }}(k))(\alpha -{\widehat{col}}_{M^{\ast }}(k))},k\in K$$
a. Compute polynomials

$h_2(x)$ and

$g_2(x)$ such that

$$\begin{gathered} f_2(X)=X{g}_2(X)+{\delta }_2/|K| \\ a(X)-b(X)f_2(X)=h_2(X)v_K(X) \end{gathered}$$

which can be combined as

$a(X)-b(X)(X{g}_2(X)+t({\beta }_1)/|K|)=h_2(X)v_K(X)$

where

$$\begin{gathered} a(X)=\sum _{M\in A^{\ast },B^{\ast },C^{\ast }}{\eta }_M{v}_H({\beta }_1)v_H(\alpha ){\widehat{val}}_{M^{\ast }}(X)\prod _{N^{\ast }\in \{A^{\ast },B^{\ast },C^{\ast }\}exp\{M^{\ast }\}}({\beta }_1-{\widehat{row}}_{N^{\ast }}(X))(\alpha -{\widehat{col}}_{N^{\ast }}(X)) \\ b(X)=\prod _{M^{\ast }\in \{A^{\ast },B^{\ast },C^{\ast }\}}({\beta }_1-{\widehat{row}}_{M^{\ast }}(X))(\alpha -{\widehat{col}}_{M^{\ast }}(X)) \end{gathered}$$
b. Commit to

$h_2(x),g_2(x)$
c. Transcript.write

$t({\beta }_1),cm\mathrm{\_}{h}_2,cm\mathrm{\_}{g}_2$

=> Oracle

Generate random number

${\beta }_2$

=> Prover - sumcheck-2

1. Compute
   
   $$\begin{gathered} h_2({\beta }_2),g_2({\beta }_2), \\ {\widehat{row}}_{A^{\ast }}({\beta }_2),{\widehat{row}}_{B^{\ast }}({\beta }_2),{\widehat{row}}_{C^{\ast }}({\beta }_2) \\ {\widehat{col}}_{A^{\ast }}({\beta }_2),{\widehat{col}}_{B^{\ast }}({\beta }_2),{\widehat{col}}_{C^{\ast }}({\beta }_2) \\ {\widehat{val}}_{A^{\ast }}({\beta }_2),{\widehat{val}}_{B^{\ast }}({\beta }_2),{\widehat{val}}_{C^{\ast }}({\beta }_2) \end{gathered}$$
2. b. Send them to the verifier

Verifier

=> Verifier sumcheck - 2

1. Compute
   a.
   $v_K({\beta }_2)$
   b.
   $$\begin{gathered} a({\beta }_2)=\sum _{M\in A^{\ast },B^{\ast },C^{\ast }}{\eta }_M{v}_H({\beta }_1)v_H(\alpha ){\widehat{val}}_{M^{\ast }}({\beta }_2)\prod _{N^{\ast }\in \{A^{\ast },B^{\ast },C^{\ast }\}exp\{M^{\ast }\}}({\beta }_1-{\widehat{row}}_{N^{\ast }}({\beta }_2))(\alpha -{\widehat{col}}_{N^{\ast }}({\beta }_2)) \\ b({\beta }_2)=\prod _{M^{\ast }\in \{A^{\ast },B^{\ast },C^{\ast }\}}({\beta }_1-{\widehat{row}}_{M^{\ast }}({\beta }_2))(\alpha -{\widehat{col}}_{M^{\ast }}({\beta }_2)) \end{gathered}$$
2. Verify
   $$a({\beta }_2)-b({\beta }_2)({\beta }_2{g}_2({\beta }_2)+t({\beta }_1)/|K|)=?h_2({\beta }_2)v_K({\beta }_2)$$

If it passes the verification, it means that the calculation

$t({\beta }_1)$calculated by the Prover is valid, then it goes up to the previous verification.

=> Verifier sumcheck - 1

Recall the equality

a. Compute
      i.

$v_H({\beta }_1)$
      ii.

$\mu (\alpha ,{\beta }_1)$
      iii.

$v_{H[\le |x|]}({\beta }_1)$
      iv.

$\hat{z}({\beta }_1)=\hat{w}({\beta }_1)v_{H[\le |x|]}({\beta }_1)+\hat{x}({\beta }_1)$

3. Verify
   
   $$s({\beta }_1)+\mu (a,{\beta }_1)(\sum _M{\eta }_M{\hat{z}}_M({\beta }_1))-t({\beta }_1)\hat{z}({\beta }_1)=?h_1({\beta }_1)v_H({\beta }_1)+{\beta }_1{g}_1({\beta }_1)$$
   If it passes the verification, it means that the polynomials
   ${\hat{z}}_A(X),{\hat{z}}_B(X),{\hat{z}}_C(X)$ and
   $\hat{z}(X)$
   satisfy a linear relationship.

=> Verifier

Verify

${\hat{z}}_A({\beta }_1)\cdot {\hat{z}}_B({\beta }_1)-{\hat{z}}_C({\beta }_1)=h_0({\beta }_1)v_H({\beta }_1)$

Reduce polynomial numbers for Sumcheck - 2

Compress the current verification of the three matrices into the verification of one matrix, namely

$$M={\eta }_A{A}^{\ast }+{\eta }_B{B}^{\ast }+{\eta }_C{C}^{\ast }$$

Represent this polynomial as a sparse matrix.

Matrix polynomials are reduced from 9 to 3.

Set b = 1

Set b = 1

Final Procotol

Marlin in Arkworks