# Sin7Y Tech Review (28): Specification for Marlin
[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.
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.
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
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
$$\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
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.
$= \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
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 $\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
i. $v_K(\beta_3)$
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
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
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_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
### 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
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_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
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_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)
Sign in with Wallet
Connect another wallet