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 要证明也不再是:

$$widetilde{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)+$$i(hR​))+muli(q,hL​,hR​)(Vi(hL​)⋅V_i(hR​))

而是：​

\begin{aligned}

\widetilde{V}{i - 1}(q’, q) &= \sum{h’ \in {0, 1}^{b_N} } \sum_{h_L \in {0, 1}^{b_G}} \sum_{h_R \in {0, 1}^{b_G}} P_{q’, q, i}(h’, h_L, h_R) \

\

P_{q’, q, i}(h’, h_L, h_R) &= \widetilde{eq}(q’, h’) \sdot [\widetilde{add}_i(q, h_L, h_R)(\widetilde{V}_i(h’, h_L) + \widetilde{V}_i(h’, h_R)) + \widetilde{mul}_i(q, h_L, h_R)(\widetilde{V}_i(h’, h_L) * \widetilde{V}_i(h’, h_R))] \

\end{aligned}

另外需要备注一下各个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,hL​,hR​)分别代表$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 ：

$$textcommit(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 值：

\def\arraystretch{1.5}

\begin{array}{c:c:c}

b_N & b_G & V_0(b_N, b_G) \ \hline

0 & 0 & 0 \ \hdashline

0 & 1 & 2 \ \hdashline

1 & 0 & 3 \ \hdashline

1 & 1 & 1 \ \hdashline

\end{array}

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

\begin{aligned}

s_0(x_1, x_2) &= 0 \sdot (1 - x_1)(1 - x_2) + 2 \sdot (1 - x_1) x_2 + 3 \sdot x_1(1 - x_2) + 1 \sdot x_1 x_2 \

\end{aligned}

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

\begin{aligned}

\widetilde{V}0(q’, q) &= \sum{h’ \in {0, 1}^{b_N} } \sum_{h_L \in {0, 1}^{b_G}} \sum_{h_R \in {0, 1}^{b_G}} P_{q’, q, 1}(h’, h_L, h_R) \

&= \sum_{h’ \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’, h’) \sdot [\widetilde{mul}_1(q, h_L, h_R)(\widetilde{V}_1(h’, h_L) * \widetilde{V}_1(h’, h_R)) + \widetilde{add}_1(q, h_L, h_R)(\widetilde{V}_1(h’, h_L) + \widetilde{V}_1(h’, h_R))] \

&\overset{?}= s_0(2, 4) = \textcolor{red}{2} \

\end{aligned}

Step TWO

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

\begin{aligned}

\widetilde{eq}_1(q’, h’) &= \widetilde{eq}_1(2, y_1) \ &= 2y_1 + (-1)(1 - y_1) \ &= 3 y_1 - 1 \

\

\widetilde{mul}_1(q, h_L, h_R) &= \widetilde{mul}_1(4, (y_2, y_3), (y_4, y_5)) \ &= 4 \sdot y_2(1 - y_3) \sdot 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) \sdot (1 - y_2)(1 - y_3) \sdot (1 - y_4) y_5 \

\

\widetilde{V}_1(h’, h_L) &= (1 - y_1) \sdot [(1 - y_2)(1 - y_3) + 4(1 - y_2)y_3 + 2 y_2(1 - y_3) + y_2 y_3] \ &+ y_1 \sdot [4(1 - y_2)(1 - y_3) + 4(1 - y_2)y_3 + y_2(1 - y_3) + y_2 y_3] \

\

\widetilde{V}_1(h’, h_R) &= (1 - y_1) \sdot [(1 - y_4)(1 - y_5) + 4(1 - y_4)y_5 + 2 y_4(1 - y_5) + y_4 y_5] \ &+ y_1 \sdot [4(1 - y_4)(1 - y_5) + 4(1 - y_4)y_5 + y_4(1 - y_5) + y_4 y_5] \

\end{aligned}

合并item ：​

\begin{aligned}

\widetilde{V}0(q’, q) &= \widetilde{V}0(2, 4) \ &= \sum{h’ \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’) \sdot [\boxed{\widetilde{mul}_1(4, h_L, h_R) \sdot (\widetilde{V}_1(h’, h_L) * \widetilde{V}_1(h’, h_R))} + \boxed{\widetilde{add}_1(4, h_L, h_R) \sdot (\widetilde{V}_1(h’, h_L) + \widetilde{V}_1(h’, 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}} (3 y_1 - 1) \

&* [ \

&\boxed{ (4 y_2(1 - y_3) y_4 y_5) }\

&\sdot [((1 - y_1) \sdot \boxed{((1 - y_2)(1 - y_3) + 4(1 - y_2)y_3 + 2 y_2(1 - y_3) + y_2 y_3)} + y_1 \sdot \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) \sdot \boxed{((1 - y_4)(1 - y_5) + 4(1 - y_4)y_5 + 2 y_4(1 - y_5) + y_4 y_5)} + y_1 \sdot \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)} \

&\sdot [((1 - y_1) \sdot \boxed{((1 - y_2)(1 - y_3) + 4(1 - y_2)y_3 + 2 y_2(1 - y_3) + y_2 y_3)} + y_1 \sdot \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) \sdot \boxed{((1 - y_4)(1 - y_5) + 4(1 - y_4)y_5 + 2 y_4(1 - y_5) + y_4 y_5)} + y_1 \sdot \boxed{(4(1 - y_4)(1 - y_5) + 4(1 - y_4)y_5 + y_4(1 - y_5) + y_4 y_5)})] \

] \

\end{aligned}

Round one

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

\def\arraystretch{1.5}

\begin{array}{c:c}

y_2 y_3 y_4 y_5 & f(y_1) \ \hline

0001 & (3 y_1 - 1) \sdot (-3) \sdot ((1 + 3y_1) + 4) \ \hdashline

1011 & (3y_1 - 1) \sdot 4 \sdot (2 - y_1) \ \hdashline

\end{array}

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

则：

\begin{aligned}

s_1(y_1) &= (3 y_1 - 1) \sdot (-3) \sdot ((1 + 3y_1) + 4) + (3y_1 - 1) \sdot 4 \sdot (2 - y_1) \

&= 2 + 2 y_1 + y_1^2 \

&= c_{0, 1} + c_{1, 1} y_1 + c_{2, 1} y_1^2 \

\end{aligned}

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

$$deltac0,1$$commit(c0,1)=commit(2)deltac1,1=commit(c1,1)=commit(2)deltac2,1=commit(c2,1)=commit(1)deltac3,1=commit(c3,1)=commit(0)

verifier 需要验证：​

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

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

$$2\delta c0,1$$δc1,1+δc2,1+δc3,1=?commit(s0​(2,4))=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)$：

\def\arraystretch{1.5}

\begin{array}{c:c}

y_3 y_4 y_5 & f(y_2) \ \hline

001 & 8 \sdot -3(1 - y_2) \sdot ((10 - 11y_2) + 4) \ \hdashline

011 & 8 \sdot 4y_2 \sdot ((10 - 11y_2) * 1) \ \hdashline

\end{array}

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

则：​

\begin{aligned}

s_2(y_2) &= 8 \sdot -3(1 - y_2) \sdot ((10 - 11y_2) + 4) + 8 \sdot 4y_2 \sdot ((10 - 11y_2) * 1) \

&= 4 + 4y_2^2 \

&= c_{0, 2} + c_{2, 2} y_2^2 \

\end{aligned}

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

$$deltac0,2$$commit(c0,2)=commit(4)deltac1,2=commit(c1,2)=commit(0)deltac2,2=commit(c2,2)=commit(4)deltac3,2=commit(c3,2)=commit(0)

verifier 需要验证：

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

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

$$2\delta c0,2$$δc1,2+δc2,2+δc3,2=?commit(s1​(3))=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)$：

\def\arraystretch{1.5}

\begin{array}{c:c}

y_4 y_5 & f(y_3) \ \hline

01 & 8 \sdot 9(1 - y_3) \sdot ((26y_3 - 34) + 4) \ \hdashline

11 & 8 \sdot 16(1 - y_3) \sdot ((26y_3 - 34) * 1) \ \hdashline

\end{array}

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

则：

\begin{aligned}

s_3(y_3) &= 8 \sdot 9(1 - y_3) \sdot ((26y_3 - 34) + 4) + 8 \sdot 16(1 - y_3) \sdot ((26y_3 - 34) * 1) \

&= 3 + 2 y_3 \

&= c_{0, 3} + c_{1, 3} y_3 \

\end{aligned}

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

$$deltac0,3$$commit(c0,3)=commit(3)deltac1,3=commit(c1,3)=commit(2)deltac2,3=commit(c2,3)=commit(0)deltac3,3=commit(c3,3)=commit(0)

verifier 需要验证：​

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

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

$$2\delta c0,3$$δc1,3+δc2,3+δc3,3=?commit(s2​(4))=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)$：

\def\arraystretch{1.5}

\begin{array}{c:c}

y_5 & f(y_4) \ \hline

1 & 8 \sdot -16 y_4 \sdot (18 * (4 - 3y_4)) + 8 \sdot -9 (1 - y_4) \sdot (18 + (4 - 3y_4)) \ \hdashline

\end{array}

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

则：

\begin{aligned}

s_4(y_4) &= 8 \sdot -16 y_4 \sdot (18 * (4 - 3y_4)) + 8 \sdot -9 (1 - y_4) \sdot (18 + (4 - 3y_4)) \

&= 1 + 4 y_4 + y_4^2 \

&= c_{0, 4} + c_{1, 4} y_4+ c_{2, 4} y_4^2 \

\end{aligned}

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

$$deltac0,4$$commit(c0,4)=commit(1)deltac1,4=commit(c1,4)=commit(4)deltac2,4=commit(c2,4)=commit(1)deltac3,4=commit(c3,4)=commit(0)

verifier 需要验证：​

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

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

$$2\delta c0,4$$δc1,4+δc2,4+δc3,4=?commit(s3​(2))=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)$：

\def\arraystretch{1.5}

\begin{array}{c:c}

• & f(y_5) \ \hline

• & 8 \sdot -64 y_5 \sdot (18 * (26 y_5 - 34)) + 8 \sdot 27 y_5 \sdot (18 + (26 y_5 - 34)) \ \hdashline

\end{array}

则：

\begin{aligned}

s_5(y_5) &= 8 \sdot -64 y_5 \sdot (18 * (26 y_5 - 34)) + 8 \sdot 27 y_5 \sdot (18 + (26 y_5 - 34)) \

&= 3y_5 \

&= c_{1, 5} y_5 \

\end{aligned}

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

$$deltac0,5$$commit(c0,5)=commit(0)deltac1,5=commit(c1,5)=commit(3)deltac2,5=commit(c2,5)=commit(0)deltac3,5=commit(c3,5)=commit(0)

verifier 需要验证：​

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

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

$$2\delta c0,5$$δc1,5+δc2,5+δc3,5=?commit(s4​(4))=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{aligned}

\widetilde{V}_1(x_1, x_2, x_3) &= (1 - x_1) \sdot [(1 - x_2)(1 - x_3) + 4(1 - x_2)x_3 + 2 x_2 (1 - x_3) + x_2 x_3] \

&+ x_1 \sdot [4(1 - x_2)(1 - x_3) + 4(1 - x_2)x_3 + x_2 (1 - x_3) + x_2 x_3]

\end{aligned}

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

\begin{aligned}

X &= \text{commit}(\widetilde{V}_1(r’, r_L)) = \text{commit}(\widetilde{V}_1(3, (4, 2))) = \text{commit}(3) \

Y &= \text{commit}(\widetilde{V}_1(r’, r_R)) = \text{commit}(\widetilde{V}_1(3, (4, 1))) = \text{commit}(2) \

Z &= \text{commit}(\widetilde{V}_1(r’, r_L) \sdot \widetilde{V}_1(r’, r_R)) = \text{commit}(3 * 2) = \text{commit}(1) \

\end{aligned}

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

\begin{aligned}

&\widetilde{eq}_1(2, r’) \sdot [\widetilde{mul}_1(4, h_L, h_R) \sdot \text{commit}(\widetilde{V}_1(r’, h_L) \sdot \widetilde{V}_1(r’, h_R)) \

&+ \widetilde{add}_1(4, h_L, h_R) \sdot (\text{commit}(\widetilde{V}_1(r’, h_L)) + \text{commit}(\widetilde{V}_1(r’, h_R)))] \

\

&= 8 \sdot [-64 * \text{commit}(1) + 27 * (\text{commit}(3) + \text{commit}(2))] \

&\overset{?}= \text{commit}(s_5(1)) = \text{commit}(3) \textcolor{green} {\checkmark} \

\end{aligned}

mini-protocols ​

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

\begin{aligned}

\widetilde{V}_1(x_1, x_2, x_3) &= (1 - x_1) \sdot [(1 - x_2)(1 - x_3) + 4 \sdot (1 - x_2) x_3 + 2 \sdot x_2 (1 - x_3) + x_2 x_3] \

&+ x_1 \sdot [4 \sdot (1 - x_2)(1 - x_3) + 4 \sdot (1 - x_2) x_3 + x_2 (1 - x_3) + x_2 x_3] \

\end{aligned}

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

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

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

\begin{aligned}

f_H(t) &= \widetilde{V}_1(r’, (1 - t) \sdot r_L + t \sdot r_R) \

&= \widetilde{V}_1(3, (4, 2 - t)) \

&= 18 - 26t = 3 + 4t

\end{aligned}

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

$$\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 \end{gathered}$$commit(4)delta_f2​=commit(0)

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

\begin{aligned}

\text{commit}(f_H(0)) &= \delta_{f_0} \

\text{commit}(f_H(1)) &= \delta_{f_0} + \delta_{f_1} \

\end{aligned}

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

\begin{aligned}

\text{commit}(\widetilde{V}1(r’, r_L)) &= \text{commit}(3) \overset{?}= \text{commit}(f_H(0)) = \delta{f_0} \textcolor{green} {\checkmark} \

\text{commit}(\widetilde{V}1(r’, r_R)) &= \text{commit}(2) \overset{?}= \text{commit}(f_H(1)) = \delta{f_0} + \delta_{f_1} \textcolor{green} {\checkmark} \

\end{aligned}

为了验证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{aligned}

\widetilde{V}1(q’, q) &= \sum{h’ \in {0, 1}^{b_N} } \sum_{h_L \in {0, 1}^{b_G}} \sum_{h_R \in {0, 1}^{b_G}} P_{q’, q, 2}(h’, h_L, h_R) \

&= \sum_{h’ \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’, h’) \sdot [\widetilde{mul}_1(q, h_L, h_R)(\widetilde{V}_2(h’, h_L) * \widetilde{V}_2(h’, h_R)) + \widetilde{add}_2(q, h_L, h_R)(\widetilde{V}_1(h’, h_L) + \widetilde{V}_2(h’, h_R))] \

& \overset{?} = f_H(v)= \textcolor{red}{3 + 4v} \

\end{aligned}

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

$$textcommit(f_H(v))=\delta f_0+\delta$$v+δ_f2​⋅v2

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

\begin{aligned}

&\text{commit}(\widetilde{V}1(3, (4, 2 - v))) \overset{?}= \delta{f_0} + \delta_{f_1} \sdot v + \delta_{f_2} \sdot v^2 \

&\textcolor{red}{ OR } \

&\text{commit}(\widetilde{V}_1(3, (4, 2)) \overset{?}= \text{commit}(3) \

&\text{commit}(\widetilde{V}_1(3, (4, 1)) \overset{?}= \text{commit}(2) \

\end{aligned}

这样应该能make sense！

Step THREE

同Step TWO 一样，这里我们省略掉N 行文字+公式… 直接进入到Final Step！

Final Step

我们再回顾一下最开始的实例结构图：

根据最下面一层(public input + witness)的值，我们可以插值出MLE：

\begin{aligned}

\widetilde{V}_2(x_1, x_2, x_3) &= (1 - x_1) \sdot [(1 - x_2)(1 - x_3) + 2 \sdot (1 - x_2) x_3 + x_2 (1 - x_3) + 4 \sdot x_2 x_3] \

&+ x_1 \sdot [2 \sdot (1 - x_2)(1 - x_3) + 3 \sdot (1 - x_2) x_3 + 2 \sdot x_2 (1 - x_3) + 4 \sdot x_2 x_3] \

\end{aligned}

Step THREE 的mini-protocol 同样也会归结到证明两个claims，为了方便描述我们假设 $(r^{\prime },r_L,r_R)=(2,(3,2),(3,3))$：

$$\begin{gathered} widetildeV\_2(r^{\prime },r_L)\stackrel{?}{=}\tilde{V}\_2(2,(3,2))=0 \\ widetildeV\_2(r^{\prime },r_R)\stackrel{?}{=}\tilde{V}\_2(2,(3,3))=1 \end{gathered}$$

多项式$f_H(t)$：

$$f_H(t)=t$$

假设fold factor $v=2$，把上面的两个claims合并成一个claim:​

$$widetildeV\_2(2,(3,4))\stackrel{?}{=}{f}_H(v)=2$$

备注：简单一句话就是，证明最下面一层(public input+witness)电路、Gate编码为(2, (3, 4))， evaluation 值为2 ，组成的点在MLE 多项式上。

同样，verifier 基于prover 提供的$f_H(t)$的commitment，计算出$f_H(v)$ 的commitment:

\begin{aligned}

\text{commit}(f_H(2)) &= \delta_{f_0} + \delta_{f_1} \sdot 2 + \delta_{f_2} \sdot 2^2 \

&= \text{commit}(1) \sdot 2

\end{aligned}

verifier 如何验证prover 提供的这个commitment的合法性？对于verifier 来说最下面一层电路的evaluation 分 public input p和 witness w，其中后者未知，假设两者长度相等，按照上图中的实例，也就是说前半部分为public input，后半部分为witness：

$$(\underset{\text{public input}}{\underbrace{1,2,1,4}},\underset{\text{witness}}{\underbrace{2,3,2,4}})$$

因此，我们需要把$\tilde{V}\_2$拆解成两部分

$$widetildeV\_2(x_1,x_2,x_3)=(1-x_1)\cdot \tilde{p}(x_2,x_3)+x_1\cdot \tilde{w}(x_2,x_3)$$

最终是要计算出$\tilde{V}\_2(2,(3,4))$的commitment，其中public input 部分因为是公开的，所以verifier 可以自行计算出相应的MLE 多项式$\tilde{p}(x_2,x_3)$，并拿到$\tilde{p}(3,4)$的commitment；另外witness 部分因为在Step ZERO prover 已经把它们的commitment 全部都已经发给verifier 了，verifier 只需要基于此拿到$\tilde{w}(x_2,x_3)$ 的commitment就可以了：

\begin{aligned}

\widetilde{w}(x_2, x_3) &= 2 \sdot (1 - x_2)(1 - x_3) + 3 \sdot (1 - x_2)x_3 + 2 \sdot x_2 (1 - x_3) + 4 \sdot x_2 x_3 \

&\Downarrow \

\text{commit}(\widetilde{w}(x_2, x_3) ) &= \text{commit}(2) \sdot (1 - x_2)(1 - x_3) + \text{commit}(3) \sdot (1 - x_2)x_3 + \text{commit}(2) \sdot x_2 (1 - x_3) + \text{commit}(4) \sdot x_2 x_3 \

\end{aligned}

最后的最后，我们put it together ：​

\begin{aligned}

2 \sdot \text{commit}(1) &\overset{?}= (1 - 2) \sdot \text{commit}(\widetilde{p}(3, 4)) + 2 \sdot \text{commit}(\widetilde{w}(3, 4)) \

&= 4 \sdot \text{commit}(\widetilde{p}(3, 4)) + 2 \sdot [\text{commit}(2) \sdot 1+ \text{commit}(3) \sdot 2 + \text{commit}(2) \sdot 1 + \text{commit}(4) \sdot 2]

\end{aligned}

What’s Next

到此为止，满足ZK argument的Vallina 版本的GKR协议也就完整了，紧接着我们再detail一下Hyrax 在此基础之上都做了些什么？接着再看看Spark 在Hyrax基础之上做了些什么？最后再看看Spartan 的整个全貌？

参考资料

【1】Hyrax 论文：https://eprint.iacr.org/2017/1132.pdf

【2】PAZK by Thaler：https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf

【3】trivial GKR 协议：https://learnblockchain.cn/article/6199

【4】sumcheck 协议：https://learnblockchain.cn/article/6188