---
# System prepended metadata

title: 'Sin7Y Tech Review (28): Specification for Marlin'

---

# Sin7Y Tech Review (28): Specification for Marlin

![](https://i.imgur.com/tsz3NKj.png)



[Arkworks for Marlin](https://github.com/arkworks-rs/marlin/blob/master/diagram/diagram.pdf)
[Marlin](https://eprint.iacr.org/2019/1047.pdf)
[Fractal](https://eprint.iacr.org/2019/1076.pdf)

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

![](https://i.imgur.com/AKRKN44.png)


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 

$$z_A \circ z_B= z_C \\
z_A = Az \\
z_B=Bz\\
z_C = Cz$$

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:
$$\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]$$
Add $b$ redundant point without exposing any information of $w$
2. Define polynomial（LDE）for vector $z=(x,w)$
  1. Define a polynomial $\hat{x}(X)\in F^{<|H_{[\le|x|]}|}[X]$ for $x$,satisfying
$$\hat{x}(g^0) =x[0] \\
\hat{x}(g^1) =x[1] \\
...\\
\hat{x}(g^{|x|-1}) =x[|x|-1] $$
  2. Define a polynomial for $w$
$$\forall \gamma \in H[\ge|x|]， \bar{w} := \frac{w(\gamma) - \hat x(\gamma)}{v_{H[\le |x|]}(\gamma)}$$
Define a polynomial $\hat{w}(X)$（LDE）for a vector $\bar{w}$，satisfying
$$\hat{w}(g^|x|) =\bar{w}[|x|] \\
\hat{w}(g^{|x|+1}) =\bar{w}[|x|+1] \\
...\\
\hat{w}(g^{|H|-1}) =\bar{w}[|H|-1] $$

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](https://eprint.iacr.org/2019/1047.pdf) ), we use a special form to represent the matrix. Below is an example using matrix A.
![](https://i.imgur.com/aRdtVNS.png)


Define:
$$\hat{row}(k) := \phi^{-1}(t_k)\\
\hat{col}(k) := \phi^{-1}(t_k)\\
\hat{val}(k) : k_{-th} \ non-zero\  value$$

Where $t_k$ is the row index of the kth non-zero value of the matrix，$$\phi ^{-1}(t_k)：[|H|] \rightarrow H$$maps the index to the computational domain，and $\hat{val}(k)$ is the kth non-zero value of the matrix，which can be divisible by$$\mu_H(\hat{row}(k), \hat{row}(k))\mu_H(\hat{col}(k), \hat{col}(k))$$

Therefore, a polynomial can be expressed as

$$\hat{M}(X,Y) = \sum_{k\in K}\mu_H(X,\hat{row}(k))\mu_H(Y,\hat{col}(k))\hat{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

![](https://i.imgur.com/avGvqjc.png)

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

![](https://i.imgur.com/D4hyrbJ.png)



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
$$\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$$
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
$$\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]\\
\hat{row}_A(X),\hat{row}_B(X),\hat{row}_C(X)\\
\hat{col}_A(X),\hat{col}_B(X),\hat{col}_C(X)\\
\hat{val}_A(X),\hat{val}_B(X),\hat{val}_C(X)$$
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

<span style="color:green">=> Prover</span>
  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, cm_*$

<span style="color:orange">=> Oracle</span>

Generate random numbers $\alpha, \eta_A, \eta_B, \eta_C$

 <span style="color:green">=> Prover - sumcheck-1</span>


Sumcheck for $$\sum_{X\in H}s(X) + r(a, X)(\sum_M \eta_M\hat{z}_M(X)) - (\sum_M\eta_Mr_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_Mr_M(a, X)\hat{z}(X)) = h_1(X)v_H(X) + Xg_1(X) + \delta_1/ |H|$$
  d. Commit to $h_1(X), g_1(X)$
  e. Transcript.write $cm\_h_1, cm\_g_1$
<span style="color:orange">=> Oracle</span>

Generate random number $\beta_1$

<span style="color:green">=>  Prover - sumcheck-1</span> 
  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
   &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; i. $v_H(\beta_1), v_{H[\le|x|]}(\beta_1), r(\alpha, \beta_1)$
   &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ii. $\hat{z}(\beta_1) = \hat{w}(\beta_1) v_{H[\le|x|]}(\beta_1) + \hat{x}(\beta_1)$
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  iii. 
$= \eta_Ar_A(\alpha, \beta_1) + \eta_Br_B(\alpha, \beta_1) +\eta_Cr_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))$

Its computational complexity is $\Omega(|H||K|)$，therefore，this part of the calculation needs to be executed by the Prover as a proxy.

<span style="color:green">=> Prover -sumcheck-2 </span>

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) + Xg_2(X) +\delta_2/ |H|$$
  b. Commit to $h_2(X), g_2(X)$
  c. Transcript.write $\delta_2, cm\_h_2, cm\_g_2$

<span style="color:orange">=> Oracle</span>


Generate random number $\beta_2$

 <span style="color:green">=>  Prover - sumcheck-2</span> 
  a. Compute $h_2(\beta_2), g_2(\beta_2)$
  b. If we send these numbers to the verifier, the verifier needs to compute
   &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; i.  $v_H(\beta_2),  r(\alpha, \beta_2)$
  &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  ii.  $\hat{A}(\beta_2,\beta_1),\hat{B}(\beta_2,\beta_1),\hat{C}(\beta_2,\beta_1)$
Its computational complexity is $\Omega(|K|)$，therefore，this part of the calculation needs to be executed by Prover as a proxy.

 <span style="color:green">=>  Prover - sumcheck-3</span> 


Sumcheck for 
$$ \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)\hat{val}(k)}{(\beta_2 - \hat{row}_M(k))(\beta_1 - \hat{col}_M(k))}$$
Define the polynomial
$$f_3(k)= \sum_{M \in {A,B,C}} \eta_M\frac{v_H(\beta_2)v_H(\beta_1)\hat{val}(k)}{(\beta_2 - \hat{row}_M(k))(\beta_1 - \hat{col}_M(k))}, k\in K$$
  a. Compute polynomials $h_3(x)$and $g_3(x)$such that
$$f_3(X) = Xg_3(X) + \delta_3/|K| \\
a(X)-b(X)f_3(X) = h_3(X)v_K(X)$$
which can be combined as：$a(X)-b(X)(Xg_3(X) + \delta_3/|K|) = h_3(X)v_K(X)$


where

$$a(X) =\sum_{M \in {A,B,C}}\eta_M{v_H(\beta_2)v_H(\beta_1)\hat{val}(X)}\prod_{N \in \{A,B,C \}exp\{M\}}(\beta_2 - \hat{row}_N(X))(\beta_1 - \hat{col}_N(X))\\
b(X) = \prod_{M \in \{A,B,C \}}(\beta_2 - \hat{row}_M(X))(\beta_1 - \hat{col}_M(X))$$

  b. Commit to $h_3(x),g_3(x)$
  c. Transcript.write $\delta_3,cm\_h_3, cm\_g_3$

<span style="color:orange">=> Oracle</span>


Generate random number $\beta_3$

=>  Prover - sumcheck-3
  a. Compute
$$h_3(\beta_3), g_3(\beta_3),\\
\hat{row}_A(\beta_3),\hat{row}_B(\beta_3),\hat{row}_C(\beta_3)\\
\hat{col}_A(\beta_3),\hat{col}_B(\beta_3),\hat{col}_C(\beta_3)\\
\hat{val}_A(\beta_3),\hat{val}_B(\beta_3),\hat{val}_C(\beta_3)$$
  b.  Send to the verifier

### Verifier

 <span style="color:red">=> Verifier-sumcheck-3</span>


  a. Compute
   &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; i. $v_K(\beta_3)$
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ii. $$a(\beta_3) =\sum_{M \in {A,B,C}}\eta_M{v_H(\beta_2)v_H(\beta_1)\hat{val}(\beta_3)}\prod_{N \in \{A,B,C \}exp\{M\}}(\beta_2 - \hat{row}_N(\beta_3))(\beta_1 - \hat{col}_N(\beta_3))\\
b(\beta_3) = \prod_{M \in \{A,B,C \}}(\beta_2 - \hat{row}_M(\beta_3))(\beta_1 - \hat{col}_M(\beta_3))$$
  b.  Verify
$$
a(\beta_3)-b(\beta_3)(\beta_3g_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 
$$ \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)\hat{val}(k)}{(\beta_2 - \hat{row}_M(k))(\beta_1 - \hat{col}_M(k))} \\
=\delta_3$$
is valid, then go to the previous level for verification.

<span style="color:red">=> Verifier-sumcheck-2</span>

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) + Xg_2(X) +\delta_2/ |H|$$

  a. Compute
   &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; i. $v_H(\beta_2)$
  b. Verify
$$ r(\alpha,\beta_2)\delta_3 =?\  h_2(\beta_2)v_H(\beta_2) + \beta_2g_2(\beta_2) +\delta_2/ |H|$$
If it passes the verification, it means that the value computed by the Prover
$$ \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$$
is valid, then go to the previous level for verification.

 <span style="color:red">=> Verifier-sumcheck-1</span>

Recall the equality
$$s(X) + r(a, X)(\sum_M \eta_M\hat{z}_M(X)) - (\sum_M\eta_Mr_M(a, X)\hat{z}(X)) = h_1(X)v_H(X) + Xg_1(X) + \delta_1/ |H|$$
  a. Compute
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i. $v_H(\beta_1)$
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ii. $r(\alpha, \beta_1)$
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;iii. $v_{H[\le|x|]}(\beta_1)$
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;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_1g_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.

<span style="color:red">=> Verifier</span>

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 \rightarrow \{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 \rightarrow \{ h_2(\beta_2), g_2(\beta_2)\}$$

#### Sumcheck - 3

$$\beta_3 \rightarrow \{h_3(\beta_3), g_3(\beta_3),
\hat{row}_A(\beta_3),\hat{row}_B(\beta_3),\hat{row}_C(\beta_3)
\hat{col}_A(\beta_3),\hat{col}_B(\beta_3),\hat{col}_C(\beta_3)\\
\hat{val}_A(\beta_3),\hat{val}_B(\beta_3),\hat{val}_C(\beta_3)\}$$

#### 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
![](https://i.imgur.com/u73srRp.png)

### Reduce sumcheck 

According to the optimization mentioned in the paper [COS20.  Claim6.7](https://eprint.iacr.org/2019/1076.pdf)（Fractal）we make
$$r(X, Y) = \mu_H(X,Y)\\
r_M(X,Y) = M^*(Y,X)\\
M^*(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)$$
For matrices $A,B,C$，the transformed matrices are

$$ A^*_{a,b} = A_{b,a}\cdot \mu(b,b)\\
B^*_{a,b} = B_{b,a}\cdot \mu(b,b)\\
C^*_{a,b} = C_{b,a}\cdot \mu(b,b)\\ $$

Define polynomial  $t(X)$
$$t(X) := \sum_{M}\eta_Mr_M(a, X) $$
Then, for sumcheck - 1，the formula becomes
$$\sum_{X\in H}s(X) + r(\alpha, X)(\sum_M \eta_M\hat{z}_M(X)) - (\sum_M\eta_Mr_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)$$

#### Common

Given the polynomial
$$\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]\\
\hat{row}_A(X),\hat{row}_B(X),\hat{row}_C(X)\\
\hat{col}_A(X),\hat{col}_B(X),\hat{col}_C(X)\\
\hat{val}_A(X),\hat{val}_B(X),\hat{val}_C(X)$$
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

<span style="color:green">=> Prover</span>

  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, cm_*$

<span style="color:orange">=> Oracle</span>

Generate random number $\alpha, \eta_A, \eta_B, \eta_C$

<span style="color:green">=> Prover-sumcheck - 1 </span> 

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) + Xg_1(X) + \sout {\delta_1/ |H|}$$
  b. Commit to  $h_1(X), g_1(X)$
  c. Transcript.write $cm\_h_1, cm\_g_1$
  
<span style="color:orange">=> Oracle</span>


Generate random number $\beta_1$

 <span style="color:green">=> Prover-sumcheck - 1</span>

  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
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i. $v_H(\beta_1), v_{H[\le|x|]}(\beta_1), r(\alpha, \beta_1)$
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ii. $\hat{z}(\beta_1) = \hat{w}(\beta_1) v_{H[\le|x|]}(\beta_1) + \hat{x}(\beta_1)$
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;iii. $t(\beta_1) = \eta_AA^*(\beta_1, \alpha) + \eta_BB^*(\beta_1, \alpha) +\eta_CC^*(\beta_1, \alpha)$

Its computational complexity is $\Omega(|K|)$，Therefore, this part of the calculation needs to be executed by Prover as a proxy.

 <span style="color:green">=>  Prover - sumcheck-2</span> 


Sumcheck for 
$$ \eta_AA^*(\beta_1,\alpha)+\eta_BB^*(\beta_1,\alpha)+\eta_CC^*(\beta_1,\alpha)\\
= \sum_{k \in K}\sum_{M \in {A^*,B^*,C^*}} \eta_M\frac{v_H(\beta_1)v_H(\alpha)\hat{val}_{M^*}(k)}{(\beta_1 - \hat{row}_{M^*}(k))(\alpha - \hat{col}_{M^*}(k))}$$
Define the polynomial
$$f_2(k)= \sum_{M \in {A^*,B^*,C^*}} \eta_M\frac{v_H(\beta_1)v_H(\alpha)\hat{val}_{M^*}(k)}{(\beta_1 - \hat{row}_{M^*}(k))(\alpha - \hat{col}_{M^*}(k))}, k\in K$$
  a. Compute polynomials $h_2(x)$ and $g_2(x)$ such that
$$f_2(X) = Xg_2(X) + \delta_2/|K| \\
a(X)-b(X)f_2(X) = h_2(X)v_K(X)$$

which can be combined as $a(X)-b(X)(Xg_2(X) + t(\beta_1)/|K|) = h_2(X)v_K(X)$

where
$$a(X) =\sum_{M \in {A^*,B^*,C^*}}\eta_M{v_H(\beta_1)v_H(\alpha)\hat{val}_{M^*}(X)}\prod_{N^* \in \{A^*,B^*,C^* \}exp\{M^*\}}(\beta_1 - \hat{row}_{N^*}(X))(\alpha - \hat{col}_{N^*}(X))\\
b(X) = \prod_{M^* \in \{A^*,B^*,C^* \}}(\beta_1 - \hat{row}_{M^*}(X))(\alpha - \hat{col}_{M^*}(X))$$
  b. Commit to $h_2(x),g_2(x)$
  c. Transcript.write $t(\beta_1),cm\_h_2, cm\_g_2$

=> Oracle

Generate random number $\beta_2$

=>  Prover - sumcheck-2
  1. Compute
$$h_2(\beta_2), g_2(\beta_2),\\
\hat{row}_{A^*}(\beta_2),\hat{row}_{B^*}(\beta_2),\hat{row}_{C^*}(\beta_2)\\
\hat{col}_{A^*}(\beta_2),\hat{col}_{B^*}(\beta_2),\hat{col}_{C^*}(\beta_2)\\
\hat{val}_{A^*}(\beta_2),\hat{val}_{B^*}(\beta_2),\hat{val}_{C^*}(\beta_2)$$
  2. b. Send them to the verifier 

#### Verifier

 <span style="color:red">=> Verifier sumcheck - 2</span>
1. Compute
  a.  $v_K(\beta_2)$
  b. $$a(\beta_2) =\sum_{M \in {A^*,B^*,C^*}}\eta_M{v_H(\beta_1)v_H(\alpha)\hat{val}_{M^*}(\beta_2)}\prod_{N^* \in \{A^*,B^*,C^* \}exp\{M^*\}}(\beta_1 - \hat{row}_{N^*}(\beta_2))(\alpha - \hat{col}_{N^*}(\beta_2))\\
b(\beta_2) = \prod_{M^* \in \{A^*,B^*,C^* \}}(\beta_1 - \hat{row}_{M^*}(\beta_2))(\alpha - \hat{col}_{M^*}(\beta_2))$$
2. Verify$$
a(\beta_2)-b(\beta_2)(\beta_2g_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.

 <span style="color:red">=> Verifier sumcheck - 1</span>

Recall the equality
![](https://i.imgur.com/HToFQE1.png)

  a. Compute
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;i. $v_H(\beta_1)$
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ii. $\mu(\alpha, \beta_1)$
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;iii. $v_{H[\le|x|]}(\beta_1)$
    &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;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_1g_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.

<span style="color:red">=> Verifier</span>

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_AA^* + \eta_BB^*+\eta_CC^*$$

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](https://github.com/arkworks-rs/marlin/blob/master/diagram/diagram.pdf)
