# 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 , \hat{z}_B(X)(g^0) =z_B,\hat{z}_C(X)(g^0) =z_C\\ \hat{z}_A(g^1) =z_A , \hat{z}_B(X)(g^1) =z_B,\hat{z}_C(X)(g^1) =z_C\\ ...\\ \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 \\ \hat{x}(g^1) =x \\ ...\\ \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)