# 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)
Last changed by  
 
Sin7Y
Exploring #Layer 2, #Crosschain, #ZK, and #Privacy Computing.

Read more

Sin7y Tech Review (35) Hybrid Rollup - The Next-Generation Infrastructure

A comparative study of Aztec, Miden, and Ola In this article, we delve into the concept of "Hybrid Rollup," examining how projects Aztec, Miden, and Ola approach this technology. We investigate their unique smart contract languages, explore state tree designs, and consider the trade-offs in privacy designs. Our objective is to provide a comprehensive overview of Hybrid Rollup technologies, helping you understand their key components and envision their future trajectory. What is Hybrid Rollup? We are delighted to see that our recent initiatives have been garnering an increasing amount of attention in the market. "Hybrid Rollup" is the most accurate summary of what we at Ola have been working on: Rollup: a. It operates at Layer 2, but it also has the flexibility to function at Layer 3, depending on the platform utilized for the verification contract deployment.b. It's a scalability solution.c. It has programmability - "Rollup" doesn't specifically indicate this feature; "Programmable Rollup" is more accurate. Hybrid: a. It supports public, private, and hybrid contract types.b. Developers can freely choose the contract type based on their needs.c. Users can freely choose the transaction type in hybrid contracts.

6/13/2023
Sin7y Tech Review (34): Is SuperNova's Folding Scheme the Endgame for ZK?![](https://hackmd.io/_uploads/rkLrzROBh.png)

This article is the 34th series of the Sin7y Tech Review and will mainly interpret SuperNova, which is a new recursive proof system for incrementally producing succinct proofs of correct execution of programs on a stateful machine with a particular instruction set. These seem to be fantastic features. This article will mainly interpret how these features are implemented. For easy understanding, all interpretations are based on the paper itself. What is folding? First, let's look at the definition in the paper:As shown by the green marker in the figure: input: two (instance, witness) pairs

5/23/2023
Sin7y Tech Review (33): Principles of private transactions and regulatory compliance issues

In August 2022, the Office of Foreign Assets Control (OFAC) announced sanctions against Tornado Cash, which directly cast a shadow on protocols aiming to achieve privacy on public blockchains. This led to discouragement in the market towards privacy and raised regulatory concerns. However, Ola, an Ethereum Layer 2 network that supports programmable privacy utilizing its ZK-ZKVM architecture, still recognizes the urgent need for robust privacy across the blockchain space. Ola is not the first project dedicated to bringing privacy to blockchains, nor will it be the last. As a member of the blockchain community, Ola is committed to interpreting the privacy technologies used in most projects and the regulatory compliance issues involved in privacy transactions, in order to help the market understand privacy on top of public blockchains more comprehensively. 1. Why was Tornado Cash banned? The reason for Tornado Cash's blacklisting by OFAC is obvious: its transactions can not be tracked. This has made Tornado Cash widely used for illegal activities. The principle of privacy in Tornado Cash differs from that of Zcash, which is entirely based on ZK technology. Tornado Cash combines coin mixing and ZK technology, with coin mixing making transactions untraceable. As the coin-mixing pool grows larger, the chances of tracking it approach zero. ZK is only used to realize its own asset proof once the coin mixing is complete. Therefore, Tornado Cash is called a haven for hackers and black money, as it is impossible to track the addresses to which non-performing assets are withdrawn after entering the mixing pool. This is also the underlying reason for Tornado Cash's blacklisting. Many articles interpret the principle of coin-mixing in Tornado Cash, which readers can find for themselves.

5/22/2023
Hello, OlaVM!

TL;DR We are working on building the first ZKVM based on a parallel execution architecture and achieving higher TPS through the improvement of ZK-friendly design and ZK algorithms. The technical features are as follows:Fast proof generationZK-friendly: smaller circuit scale and simplified bottom constraint units Fast ZK: further optimization on Plonky2 Fast execution: Utilizing parallel execution to significantly shorten the proof generation time Current progress: In July 2022, we released the OlaVM Whitepaper. November 2022, completed instruction set design and development, and realized the OlaVM execution module of the virtual machine, you can check the link: https://github.com/Sin7Y/olavm to view our code, continuously updated.

1/10/2023
Read more from Sin7Y
Published on HackMD