Thanks

• 感谢SecbitLabs @郭宇 前两个月分享的Spartan Overview (尽管当时也没太理解)， 以及@even 在研究方向上的指引(据说Hyrax 不太好啃)，不至于走太多弯路。

我的动机

缘于folding，缘于NOVA，缘于Setty，了解到了Spartan，但并不认识它，所以才有了本篇及接下来的关于它的一切(预备知识)…… 

关于Spartan，在ZK领域可能时间上相对也有点儿远了，暂且不考虑它在某些方面的争议，它的一些思想其实已经影响到其它比较热门的方向了，比如当下的热点Lasso & Jolt，所以它的研究意义仍然很大。

Overview 

• 本篇文章主要参考Hyrax 论文前半部分1-4节，即优化前的GKR zk argument

• GKR 协议本身是Sumcheck协议的一种应用，不带zk argument的GKR 就可以简单认为是多个sumcheck协议的叠加，带zk argument的GKR就会带来很多的细节问题，这也是Hyrax 的起源，所以弄清楚GKR with zk argument 的各个细节后自然也就清楚了Hyrax的意义

数据并行化下的GKR 协议

节选自PAZK 中的图

何为数据并行化GKR？就是同一个电路描述应用在多组input 数据中的GKR 协议，这样prover 在最开始的claims 中就不再是针对单一电路的output，比如下面的 $$V_0=(0,2)$$：

而是多个子电路的output的汇总 $$V_0=(0,2,3,1)$$：​

在GKR协议中prover 要证明也不再是:

$${\tilde{V}}_{i-1}(q)=\sum _{h_L\in \{0,1{\}}^{b_G}}\sum _{h_R\in \{0,1{\}}^{b_G}}{\widetilde{add}}_i(q,h_L,h_R)({\tilde{V}}_i(h_L)+{\tilde{V}}_i(h_R))+{\widetilde{mul}}_i(q,h_L,h_R)({\tilde{V}}_i(h_L)\cdot {\tilde{V}}_i(h_R))$$

而是：​

$$\begin{array}{rl}{\tilde{V}}_{i-1}(q^{\prime },q)& =\sum _{h^{\prime }\in \{0,1{\}}^{b_N}}\sum _{h_L\in \{0,1{\}}^{b_G}}\sum _{h_R\in \{0,1{\}}^{b_G}}{P}_{q^{\prime },q,i}(h^{\prime },h_L,h_R)\\ & \\ P_{q^{\prime },q,i}(h^{\prime },h_L,h_R)& =\widetilde{eq}(q^{\prime },h^{\prime })\cdot [{\widetilde{add}}_i(q,h_L,h_R)({\tilde{V}}_i(h^{\prime },h_L)+{\tilde{V}}_i(h^{\prime },h_R))+{\widetilde{mul}}_i(q,h_L,h_R)({\tilde{V}}_i(h^{\prime },h_L)\ast {\tilde{V}}_i(h^{\prime },h_R))]\end{array}$$

另外需要备注一下各个notion的含义：

• N 代表子电路的个数

• G 代表单个子电路中每层Gate的个数

• $V_{i-1}(q^{\prime },q)$ 代表第$i-1$ 层电路编码$q^{\prime }\in {\mathbb{F}}^{b_N}$ Gate编码$q\in {\mathbb{F}}^{b_G}$ 上的evaluation 值，${\tilde{V}}_{i-1}(q^{\prime },q)$是$V_{i-1}(q^{\prime },q)$的MLE 

• $V_i(h^{\prime },h_L)$代表第$i$ 层电路编码$h^{\prime }\in {\mathbb{F}}^{b_N}$ Gate编码 $h_L\in {\mathbb{F}}^{b_G}$ 上的evaluation 值，${\tilde{V}}_i(h^{\prime },h_L)$是$V_i(h^{\prime },h_L)$的MLE；${\tilde{V}}_i(h^{\prime },h_R)$同理

• ${\widetilde{add}}_i(q,h_L,h_R)$和${\widetilde{mul}}_i(q,h_L,h_R)$分别代表$\{q,h_L,q_R\}\in {\mathbb{F}}^{b_G}$上的加法和乘法Gate的MLE，注意Gate的描述与电路的编码$q^{\prime }\in {\mathbb{F}}^{b_N}$ 无关，也跟input witness无关，所以它的计算可以在preprocessing 阶段就开始了，没有必要等到协议中才开始

• $eq(q^{\prime },h^{\prime })$代表电路编码$q^{\prime }\in {\mathbb{F}}^{b_N}$ 与 电路编码$h^{\prime }\in {\mathbb{F}}^{b_N}$ 是否一致，$\widetilde{eq}(q^{\prime },h^{\prime })$是$eq(q^{\prime },h^{\prime })$的MLE

GKR Protocol with ZK Argument

仍然以为个图为例来扮演整个协议的过程。其中电路的个数$N=2$，所以$b_N=1$；有限域的moduler $p=5$。​

Step ZERO

假设前半部分为public input，后半部分为witness，对witness 的每个元素进行commit，并发送给verifier ：

$$\text{commit}(2)、\text{commit}(3)、\text{commit}(2)、\text{commit}(4)$$

Step ONE

prover 发送电路的output 作为Sumcheck的初始claims$V_0=(0,2,3,1)$，verifier 根据给定的电路第0层的evaluation 值：

$$\begin{array}{ccc}{b}_N& b_G& V_0(b_N,b_G)\\ 0& 0& 0\\ 0& 1& 2\\ 1& 0& 3\\ 1& 1& 1\end{array}$$

可以插值出相应的多项式：

$$\begin{array}{rl}{s}_0(x_1,x_2)& =0\cdot (1-x_1)(1-x_2)+2\cdot (1-x_1)x_2+3\cdot x_1(1-x_2)+1\cdot x_1{x}_2\end{array}$$

verifier 生成challenge factor$(q^{\prime },q)=(2,4)=(x_1,x_2)$，并发送给prover，接下来进入第1层电路的 sumcheck 协议，prover 需要证明：

$$\begin{array}{rl}{\tilde{V}}_0(q^{\prime },q)& =\sum _{h^{\prime }\in \{0,1{\}}^{b_N}}\sum _{h_L\in \{0,1{\}}^{b_G}}\sum _{h_R\in \{0,1{\}}^{b_G}}{P}_{q^{\prime },q,1}(h^{\prime },h_L,h_R)\\ & =\sum _{h^{\prime }\in \{0,1{\}}^{b_N}}\sum _{h_L\in \{0,1{\}}^{b_G}}\sum _{h_R\in \{0,1{\}}^{b_G}}{\widetilde{eq}}_1(q^{\prime },h^{\prime })\cdot [{\widetilde{mul}}_1(q,h_L,h_R)({\tilde{V}}_1(h^{\prime },h_L)\ast {\tilde{V}}_1(h^{\prime },h_R))+{\widetilde{add}}_1(q,h_L,h_R)({\tilde{V}}_1(h^{\prime },h_L)+{\tilde{V}}_1(h^{\prime },h_R))]\\ & \stackrel{?}{=}{s}_0(2,4)=2\end{array}$$

Step TWO

将第1层的sumcheck 多项式拆解成多个item ：

$$\begin{array}{rl}{\widetilde{eq}}_1(q^{\prime },h^{\prime })& ={\widetilde{eq}}_1(2,y_1)\\ & =2y_1+(-1)(1-y_1)\\ & =3y_1-1\\ & \\ {\widetilde{mul}}_1(q,h_L,h_R)& ={\widetilde{mul}}_1(4,(y_2,y_3),(y_4,y_5))\\ & =4\cdot y_2(1-y_3)\cdot y_4{y}_5\\ & \\ {\widetilde{add}}_1(q,h_L,h_R)& ={\widetilde{add}}_1(4,(y_2,y_3),(y_4,y_5))\\ & =(-3)\cdot (1-y_2)(1-y_3)\cdot (1-y_4)y_5\\ & \\ {\tilde{V}}_1(h^{\prime },h_L)& =(1-y_1)\cdot [(1-y_2)(1-y_3)+4(1-y_2)y_3+2y_2(1-y_3)+y_2{y}_3]\\ & +y_1\cdot [4(1-y_2)(1-y_3)+4(1-y_2)y_3+y_2(1-y_3)+y_2{y}_3]\\ & \\ {\tilde{V}}_1(h^{\prime },h_R)& =(1-y_1)\cdot [(1-y_4)(1-y_5)+4(1-y_4)y_5+2y_4(1-y_5)+y_4{y}_5]\\ & +y_1\cdot [4(1-y_4)(1-y_5)+4(1-y_4)y_5+y_4(1-y_5)+y_4{y}_5]\end{array}$$

合并item ：​

$$\begin{array}{rl}{\tilde{V}}_0(q^{\prime },q)& ={\tilde{V}}_0(2,4)\\ & =\sum _{h^{\prime }\in \{0,1{\}}^{b_N}}\sum _{h_L\in \{0,1{\}}^{b_G}}\sum _{h_R\in \{0,1{\}}^{b_G}}{\widetilde{eq}}_1(2,h^{\prime })\cdot [\boxed{{\widetilde{mul}}_1(4,h_L,h_R)\cdot ({\tilde{V}}_1(h^{\prime },h_L)\ast {\tilde{V}}_1(h^{\prime },h_R))}+\boxed{{\widetilde{add}}_1(4,h_L,h_R)\cdot ({\tilde{V}}_1(h^{\prime },h_L)+{\tilde{V}}_1(h^{\prime },h_R))}]\\ & =\sum _{y_1\in \{0,1\}}\sum _{y_2\in \{0,1\}}\sum _{y_3\in \{0,1\}}\sum _{y_4\in \{0,1\}}\sum _{y_5\in \{0,1\}}(3y_1-1)\\ & \ast [\\ & \boxed{(4y_2(1-y_3)y_4{y}_5)}\\ & \cdot [((1-y_1)\cdot \boxed{((1-y_2)(1-y_3)+4(1-y_2)y_3+2y_2(1-y_3)+y_2{y}_3)}+y_1\cdot \boxed{(4(1-y_2)(1-y_3)+4(1-y_2)y_3+y_2(1-y_3)+y_2{y}_3)})\\ & \ast ((1-y_1)\cdot \boxed{((1-y_4)(1-y_5)+4(1-y_4)y_5+2y_4(1-y_5)+y_4{y}_5)}+y_1\cdot \boxed{(4(1-y_4)(1-y_5)+4(1-y_4)y_5+y_4(1-y_5)+y_4{y}_5)})]\\ & +\\ & \boxed{((-3)(1-y_2)(1-y_3)(1-y_4)y_5)}\\ & \cdot [((1-y_1)\cdot \boxed{((1-y_2)(1-y_3)+4(1-y_2)y_3+2y_2(1-y_3)+y_2{y}_3)}+y_1\cdot \boxed{(4(1-y_2)(1-y_3)+4(1-y_2)y_3+y_2(1-y_3)+y_2{y}_3)})\\ & +((1-y_1)\cdot \boxed{((1-y_4)(1-y_5)+4(1-y_4)y_5+2y_4(1-y_5)+y_4{y}_5)}+y_1\cdot \boxed{(4(1-y_4)(1-y_5)+4(1-y_4)y_5+y_4(1-y_5)+y_4{y}_5)})]\\ ]& \end{array}$$

Round one

prover 计算本次round 验证需要用到的proof，也就是单变量多项式$s_1(y_1)$：

$$\begin{array}{cc}{y}_2{y}_3{y}_4{y}_5& f(y_1)\\ 0001& (3y_1-1)\cdot (-3)\cdot ((1+3y_1)+4)\\ 1011& (3y_1-1)\cdot 4\cdot (2-y_1)\end{array}$$

备注：$y_2{y}_3{y}_4{y}_5$​ 其它编码取值对应的多项式为0，就没有一一枚举出来

则：

$$\begin{array}{rl}{s}_1(y_1)& =(3y_1-1)\cdot (-3)\cdot ((1+3y_1)+4)+(3y_1-1)\cdot 4\cdot (2-y_1)\\ & =2+2y_1+y_1^2\\ & =c_{0,1}+c_{1,1}{y}_1+c_{2,1}{y}_1^2\end{array}$$

prover 需要把多项式$s_1(y_1)$的commitment发送给verifier，也就是把该多项式的4个系数的commitment 之后发过去：​

$$\begin{gathered} {\delta }_{c_{0,1}}=\text{commit}(c_{0,1})=\text{commit}(2) \\ {\delta }_{c_{1,1}}=\text{commit}(c_{1,1})=\text{commit}(2) \\ {\delta }_{c_{2,1}}=\text{commit}(c_{2,1})=\text{commit}(1) \\ {\delta }_{c_{3,1}}=\text{commit}(c_{3,1})=\text{commit}(0) \end{gathered}$$

verifier 需要验证：​

$$s_1(0)+s_1(1)\stackrel{?}{=}{s}_0(2,4)=2$$

根据commitment 加法同态的性质，需要验证：​

$$2{\delta }_{c_{0,1}}+{\delta }_{c_{1,1}}+{\delta }_{c_{2,1}}+{\delta }_{c_{3,1}}\stackrel{?}{=}\text{commit}(s_0(2,4))=\text{commit}(2)✓$$

验证通过，verfier 发送challenge factor  $r_1=y_1=3$，下一个round 需要验证的目标值为：​

$$s_1(3)=2+6+9=17\mathrm{mod}5=2$$

Round two

基于$y_1=3$ ，prover 计算本次round 验证需要用到的proof，也就是单变量多项式$s_2(y_2)$：

$$\begin{array}{cc}{y}_3{y}_4{y}_5& f(y_2)\\ 001& 8\cdot -3(1-y_2)\cdot ((10-11y_2)+4)\\ 011& 8\cdot 4y_2\cdot ((10-11y_2)\ast 1)\end{array}$$

备注：$y_3{y}_4{y}_5$​ 其它编码取值对应的多项式为0，就没有一一枚举出来

则：​

$$\begin{array}{rl}{s}_2(y_2)& =8\cdot -3(1-y_2)\cdot ((10-11y_2)+4)+8\cdot 4y_2\cdot ((10-11y_2)\ast 1)\\ & =4+4y_2^2\\ & =c_{0,2}+c_{2,2}{y}_2^2\end{array}$$

prover 需要把多项式$s_2(y_2)$的commitment发送给verifier，也就是把该多项式的4个系数的commitment 之后发过去：​

$$\begin{gathered} {\delta }_{c_{0,2}}=\text{commit}(c_{0,2})=\text{commit}(4) \\ {\delta }_{c_{1,2}}=\text{commit}(c_{1,2})=\text{commit}(0) \\ {\delta }_{c_{2,2}}=\text{commit}(c_{2,2})=\text{commit}(4) \\ {\delta }_{c_{3,2}}=\text{commit}(c_{3,2})=\text{commit}(0) \end{gathered}$$

verifier 需要验证：

$$s_2(0)+s_2(1)\stackrel{?}{=}{s}_1(3)=2$$

根据commitment 加法同态的性质，需要验证：​

$$2{\delta }_{c_{0,2}}+{\delta }_{c_{1,2}}+{\delta }_{c_{2,2}}+{\delta }_{c_{3,2}}\stackrel{?}{=}\text{commit}(s_1(3))=\text{commit}(2)✓$$

验证通过，verfier 发送challenge factor$r_2=y_2=4$给prover，下一个round 需要验证的目标值为:

$$s_2(4)=4+64=68\mathrm{mod}5=3$$

Round three

基于$y_1=3,y_2=4$，prover 计算本次round 验证需要用到的proof，也就是单变量多项式$s_3(y_3)$：

$$\begin{array}{cc}{y}_4{y}_5& f(y_3)\\ 01& 8\cdot 9(1-y_3)\cdot ((26y_3-34)+4)\\ 11& 8\cdot 16(1-y_3)\cdot ((26y_3-34)\ast 1)\end{array}$$

备注：$y_4{y}_5$​ 其它编码取值对应的多项式为0，就没有一一枚举出来

则：

$$\begin{array}{rl}{s}_3(y_3)& =8\cdot 9(1-y_3)\cdot ((26y_3-34)+4)+8\cdot 16(1-y_3)\cdot ((26y_3-34)\ast 1)\\ & =3+2y_3\\ & =c_{0,3}+c_{1,3}{y}_3\end{array}$$

prover 需要把多项式$s_3(y_3)$的commitment发送给verifier，也就是把该多项式的4个系数的commitment 之后发过去：​

$$\begin{gathered} {\delta }_{c_{0,3}}=\text{commit}(c_{0,3})=\text{commit}(3) \\ {\delta }_{c_{1,3}}=\text{commit}(c_{1,3})=\text{commit}(2) \\ {\delta }_{c_{2,3}}=\text{commit}(c_{2,3})=\text{commit}(0) \\ {\delta }_{c_{3,3}}=\text{commit}(c_{3,3})=\text{commit}(0) \end{gathered}$$

verifier 需要验证：​

$$s_3(0)+s_3(1)\stackrel{?}{=}{s}_2(4)=3$$

根据commitment 加法同态的性质，需要验证：​

$$2{\delta }_{c_{0,3}}+{\delta }_{c_{1,3}}+{\delta }_{c_{2,3}}+{\delta }_{c_{3,3}}\stackrel{?}{=}\text{commit}(s_2(4))=\text{commit}(3)✓$$

验证通过，verfier 发送challenge factor$r_3=y_3=2$给prover，下一个round 需要验证的目标值为:

$$s_3(2)=3+4=7\mathrm{mod}5=2$$

Round four

基于$y_1=3,y_2=4,y_3=2$，prover 计算本次round 验证需要用到的proof，也就是单变量多项式$s_4(y_4)$：

$$\begin{array}{cc}{y}_5& f(y_4)\\ 1& 8\cdot -16y_4\cdot (18\ast (4-3y_4))+8\cdot -9(1-y_4)\cdot (18+(4-3y_4))\end{array}$$

备注：$y_5$​ 其它编码取值对应的多项式为0，就没有一一枚举出来

则：

$$\begin{array}{rl}{s}_4(y_4)& =8\cdot -16y_4\cdot (18\ast (4-3y_4))+8\cdot -9(1-y_4)\cdot (18+(4-3y_4))\\ & =1+4y_4+y_4^2\\ & =c_{0,4}+c_{1,4}{y}_4+c_{2,4}{y}_4^2\end{array}$$

prover 需要把多项式$s_4(y_4)$的commitment发送给verifier，也就是把该多项式的4个系数的commitment 之后发过去：​

$$\begin{gathered} {\delta }_{c_{0,4}}=\text{commit}(c_{0,4})=\text{commit}(1) \\ {\delta }_{c_{1,4}}=\text{commit}(c_{1,4})=\text{commit}(4) \\ {\delta }_{c_{2,4}}=\text{commit}(c_{2,4})=\text{commit}(1) \\ {\delta }_{c_{3,4}}=\text{commit}(c_{3,4})=\text{commit}(0) \end{gathered}$$

verifier 需要验证：​

$$s_4(0)+s_4(1)\stackrel{?}{=}{s}_3(2)=2$$

根据commitment 加法同态的性质，需要验证：​

$$2{\delta }_{c_{0,4}}+{\delta }_{c_{1,4}}+{\delta }_{c_{2,4}}+{\delta }_{c_{3,4}}\stackrel{?}{=}\text{commit}(s_3(2))=\text{commit}(2)✓$$

验证通过，verfier 发送challenge factor $r_4=y_4=4$给prover，下一个round 需要验证的目标值为:​

$$s_4(4)=1+16+16=33\mathrm{mod}5=3$$

Round five

基于$y_1=3,y_2=4,y_3=2,y_4=4$，prover 计算本次round 验证需要用到的proof，也就是单变量多项式$s_5(y_5)$：

$$\begin{array}{cc}-& f(y_5)\\ -& 8\cdot -64y_5\cdot (18\ast (26y_5-34))+8\cdot 27y_5\cdot (18+(26y_5-34))\end{array}$$

则：

$$\begin{array}{rl}{s}_5(y_5)& =8\cdot -64y_5\cdot (18\ast (26y_5-34))+8\cdot 27y_5\cdot (18+(26y_5-34))\\ & =3y_5\\ & =c_{1,5}{y}_5\end{array}$$

prover 需要把多项式$s_5(y_5)$ 的commitment发送给verifier，也就是把该多项式的4个系数的commitment 之后发过去：​

$$\begin{gathered} {\delta }_{c_{0,5}}=\text{commit}(c_{0,5})=\text{commit}(0) \\ {\delta }_{c_{1,5}}=\text{commit}(c_{1,5})=\text{commit}(3) \\ {\delta }_{c_{2,5}}=\text{commit}(c_{2,5})=\text{commit}(0) \\ {\delta }_{c_{3,5}}=\text{commit}(c_{3,5})=\text{commit}(0) \end{gathered}$$

verifier 需要验证：​

$$s_5(0)+s_5(1)\stackrel{?}{=}{s}_4(4)=3$$

根据commitment 加法同态的性质，需要验证：​

$$2{\delta }_{c_{0,5}}+{\delta }_{c_{1,5}}+{\delta }_{c_{2,5}}+{\delta }_{c_{3,5}}\stackrel{?}{=}\text{commit}(s_4(4))=\text{commit}(3)✓$$

验证通过，verfier 发送challenge factor$r_5=y_5=1$给prover，下一个round 需要验证的目标值为:​

$$s_5(1)=3$$

Last Round

目前challenge factor 的组合为：

$$(3,(4,2),(4,1))=(y_1,(y_2,y_3),(y_4,y_5))=(r^{\prime },r_L,r_R)$$

prover 根据第1层电路的evaluation 值很容易就能插值出相应的MLE 多项式：​

$$\begin{array}{rl}{\tilde{V}}_1(x_1,x_2,x_3)& =(1-x_1)\cdot [(1-x_2)(1-x_3)+4(1-x_2)x_3+2x_2(1-x_3)+x_2{x}_3]\\ & +x_1\cdot [4(1-x_2)(1-x_3)+4(1-x_2)x_3+x_2(1-x_3)+x_2{x}_3]\end{array}$$

prover 分别计算出三个claims 值的commitment：​

$$\begin{array}{rl}X& =\text{commit}({\tilde{V}}_1(r^{\prime },r_L))=\text{commit}({\tilde{V}}_1(3,(4,2)))=\text{commit}(3)\\ Y& =\text{commit}({\tilde{V}}_1(r^{\prime },r_R))=\text{commit}({\tilde{V}}_1(3,(4,1)))=\text{commit}(2)\\ Z& =\text{commit}({\tilde{V}}_1(r^{\prime },r_L)\cdot {\tilde{V}}_1(r^{\prime },r_R))=\text{commit}(3\ast 2)=\text{commit}(1)\end{array}$$

verifier 拿着这三个commitment 完成第1层电路 sumcheck 协议的最后验证：​

$$\begin{array}{rl}& {\widetilde{eq}}_1(2,r^{\prime })\cdot [{\widetilde{mul}}_1(4,h_L,h_R)\cdot \text{commit}({\tilde{V}}_1(r^{\prime },h_L)\cdot {\tilde{V}}_1(r^{\prime },h_R))\\ & +{\widetilde{add}}_1(4,h_L,h_R)\cdot (\text{commit}({\tilde{V}}_1(r^{\prime },h_L))+\text{commit}({\tilde{V}}_1(r^{\prime },h_R)))]\\ & \\ & =8\cdot [-64\ast \text{commit}(1)+27\ast (\text{commit}(3)+\text{commit}(2))]\\ & \stackrel{?}{=}\text{commit}(s_5(1))=\text{commit}(3)✓\end{array}$$

mini-protocols ​

第一层电路evaluation 对应的MLE ：​

$$\begin{array}{rl}{\tilde{V}}_1(x_1,x_2,x_3)& =(1-x_1)\cdot [(1-x_2)(1-x_3)+4\cdot (1-x_2)x_3+2\cdot x_2(1-x_3)+x_2{x}_3]\\ & +x_1\cdot [4\cdot (1-x_2)(1-x_3)+4\cdot (1-x_2)x_3+x_2(1-x_3)+x_2{x}_3]\end{array}$$

上一个sumcheck 协议的Last Round中prover 新增加了两个claims，也就是：​

$$\begin{gathered} {\tilde{V}}_1(r^{\prime },r_L)={\tilde{V}}_1(3,(4,2))=3 \\ {\tilde{V}}_1(r^{\prime },r_R)={\tilde{V}}_1(3,(4,1))=2 \end{gathered}$$

引入一个fold factor $t$ 我们可以把两个claims fold到一起：​

$$\begin{array}{rl}{f}_H(t)& ={\tilde{V}}_1(r^{\prime },(1-t)\cdot r_L+t\cdot r_R)\\ & ={\tilde{V}}_1(3,(4,2-t))\\ & =18-26t=3+4t\end{array}$$

它的非常重要的特性就是：​

$$\begin{gathered} f_H(0)=3={\tilde{V}}_1(r^{\prime },r_L) \\ {f}_H(1)=2={\tilde{V}}_1(r^{\prime },r_R) \end{gathered}$$

prover 把多项式$f_H(t)$进行commit后发送给verifier，同样也是多个系数分别commit，该多项式degree 为2，也就是说最多有3个commitment：​

$$\begin{gathered} {\delta }_{f_0}=\text{commit}(3) \\ {\delta }_{f_1}=\text{commit}(4) \\ {\delta }_{f_2}=\text{commit}(0) \end{gathered}$$

verifier 拿到多项式$f_H(t)$的commitment 后就可以计算出：

$$\begin{array}{rl}\text{commit}(f_H(0))& ={\delta }_{f_0}\\ \text{commit}(f_H(1))& ={\delta }_{f_0}+{\delta }_{f_1}\end{array}$$

这样就可以验证prover 之前发送的${\tilde{V}}_1(r^{\prime },r_L)、{\tilde{V}}_1(r^{\prime },r_R)$的commitment 是否与当前多项式的commitment 是否一致：

$$\begin{array}{rl}\text{commit}({\tilde{V}}_1(r^{\prime },r_L))& =\text{commit}(3)\stackrel{?}{=}\text{commit}(f_H(0))={\delta }_{f_0}✓\\ \text{commit}({\tilde{V}}_1(r^{\prime },r_R))& =\text{commit}(2)\stackrel{?}{=}\text{commit}(f_H(1))={\delta }_{f_0}+{\delta }_{f_1}✓\end{array}$$

为了验证prover 之前发送的${\tilde{V}}_1(r^{\prime },r_L)、{\tilde{V}}_1(r^{\prime },r_R)$的commitment X、Y是否合法，基于多项式$f_H(t)$的commitment ${\delta }_{f_0}、{\delta }_{f_1}、{\delta }_{f_2}$， verifier 随机采样一个challenge factor $v$ 并发送给prover，prover 自然可以计算出下一轮sumcheck协议需要证明的evaluation值$f_H(v)$，即：

$$\begin{array}{rl}{\tilde{V}}_1(q^{\prime },q)& =\sum _{h^{\prime }\in \{0,1{\}}^{b_N}}\sum _{h_L\in \{0,1{\}}^{b_G}}\sum _{h_R\in \{0,1{\}}^{b_G}}{P}_{q^{\prime },q,2}(h^{\prime },h_L,h_R)\\ & =\sum _{h^{\prime }\in \{0,1{\}}^{b_N}}\sum _{h_L\in \{0,1{\}}^{b_G}}\sum _{h_R\in \{0,1{\}}^{b_G}}{\widetilde{eq}}_2(q^{\prime },h^{\prime })\cdot [{\widetilde{mul}}_1(q,h_L,h_R)({\tilde{V}}_2(h^{\prime },h_L)\ast {\tilde{V}}_2(h^{\prime },h_R))+{\widetilde{add}}_2(q,h_L,h_R)({\tilde{V}}_1(h^{\prime },h_L)+{\tilde{V}}_2(h^{\prime },h_R))]\\ & \stackrel{?}{=}{f}_H(v)=3+4v\end{array}$$

同时verifier 计算下一轮sumcheck协议需要证明的$f_H(v)$ 的commitment：

$$\text{commit}(f_H(v))={\delta }_{f_0}+{\delta }_{f_1}\cdot v+{\delta }_{f_2}\cdot v^2$$

最后我们再明确一点：mini-protocol 的根本目的是把两个claims fold成一个claims，减少prover 的成本，不然prover要分别证明两个claims：​

$$\begin{array}{rl}& \text{commit}({\tilde{V}}_1(3,(4,2-v)))\stackrel{?}{=}{\delta }_{f_0}+{\delta }_{f_1}\cdot v+{\delta }_{f_2}\cdot v^2\\ & OR\\ & \text{commit}({\tilde{V}}_1(3,(4,2))\stackrel{?}{=}\text{commit}(3)\\ & \text{commit}({\tilde{V}}_1(3,(4,1))\stackrel{?}{=}\text{commit}(2)\end{array}$$