Spartan 预备知识：GKR with ZK Argument

  • 白菜
  • 发布于 2023-09-17 12:18
  • 阅读 4424

Thanks感谢SecbitLabs@郭宇前两个月分享的SpartanOverview(尽管当时也没太理解)，以及@even在研究方向上的指引(据说Hyrax不太好啃)，不至于走太多弯路。我的动机缘于folding，缘于NOVA，缘于Setty，了解到了Spartan，

Thanks


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

我的动机


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

image.png

关于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 中的图

image.png


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

image.png


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

image.png


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

V~i−1(q)=∑hL∈{0,1}bG∑hR∈{0,1}bGadd~i(q,hL,hR)(V~i(hL)+V~i(hR))+mul~i(q,hL,hR)(V~i(hL)⋅V~i(hR))\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)(\widetilde{V}_i(h_L) + \widetilde{V}_i(h_R)) + \widetilde{mul}_i(q, h_L, h_R)(\widetilde{V}_i(h_L) \sdot \widetilde{V}_i(h_R))

而是：​

V~i−1(q′,q)=∑h′∈{0,1}bN∑hL∈{0,1}bG∑hR∈{0,1}bGPq′,q,i(h′,hL,hR)Pq′,q,i(h′,hL,hR)=eq~(q′,h′)⋅[add~i(q,hL,hR)(V~i(h′,hL)+V~i(h′,hR))+mul~i(q,hL,hR)(V~i(h′,hL)∗V~i(h′,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的个数

  • Vi−1(q′,q)V_{i - 1}(q', q) 代表第i−1i−1 层电路编码q′∈FbNq' \in \mathbb{F}^{b_N} Gate编码q∈FbGq \in \mathbb{F}^{b_G} 上的evaluation 值，V~i−1(q′,q)\widetilde{V}_{i - 1}(q', q)是Vi−1(q′,q)V_{i - 1}(q', q)的MLE 

  • Vi(h′,hL)V_{i}(h', h_L)代表第ii 层电路编码h′∈FbNh' \in \mathbb{F}^{b_N} Gate编码 hL∈FbGh_L \in \mathbb{F}^{b_G} 上的evaluation 值，V~i(h′,hL)\widetilde{V}_i(h', h_L)是Vi(h′,hL)V_i(h', h_L)的MLE；V~i(h′,hR)\widetilde{V}_{i}(h', h_R)同理

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

  • eq(q′,h′)eq(q', h')代表电路编码q′∈FbNq' \in \mathbb{F}^{b_N} 与 电路编码h′∈FbNh' \in \mathbb{F}^{b_N} 是否一致，eq~(q′,h′)\widetilde{eq}(q', h')是eq(q′,h′)eq(q', h')的MLE

GKR Protocol with ZK Argument


image.png

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


Step ZERO


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

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

Step ONE


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

bNbGV0(bN,bG)000012103111\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}

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

s0(x1,x2)=0⋅(1−x1)(1−x2)+2⋅(1−x1)x2+3⋅x1(1−x2)+1⋅x1x2\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′,q)=(2,4)=(x1,x2)(q', q) = (2, 4) = (x_1, x_2)，并发送给prover，接下来进入第1层电路的 sumcheck 协议，prover 需要证明：

V~0(q′,q)=∑h′∈{0,1}bN∑hL∈{0,1}bG∑hR∈{0,1}bGPq′,q,1(h′,hL,hR)=∑h′∈{0,1}bN∑hL∈{0,1}bG∑hR∈{0,1}bGeq~1(q′,h′)⋅[mul~1(q,hL,hR)(V~1(h′,hL)∗V~1(h′,hR))+add~1(q,hL,hR)(V~1(h′,hL)+V~1(h′,hR))]=?s0(2,4)=2\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 ：

eq~1(q′,h′)=eq~1(2,y1)=2y1+(−1)(1−y1)=3y1−1mul~1(q,hL,hR)=mul~1(4,(y2,y3),(y4,y5))=4⋅y2(1−y3)⋅y4y5add~1(q,hL,hR)=add~1(4,(y2,y3),(y4,y5))=(−3)⋅(1−y2)(1−y3)⋅(1−y4)y5V~1(h′,hL)=(1−y1)⋅[(1−y2)(1−y3)+4(1−y2)y3+2y2(1−y3)+y2y3]+y1⋅[4(1−y2)(1−y3)+4(1−y2)y3+y2(1−y3)+y2y3]V~1(h′,hR)=(1−y1)⋅[(1−y4)(1−y5)+4(1−y4)y5+2y4(1−y5)+y4y5]+y1⋅[4(1−y4)(1−y5)+4(1−y4)y5+y4(1−y5)+y4y5]\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 ：​

V~0(q′,q)=V~0(2,4)=∑h′∈{0,1}bN∑hL∈{0,1}bG∑hR∈{0,1}bGeq~1(2,h′)⋅[mul~1(4,hL,hR)⋅(V~1(h′,hL)∗V~1(h′,hR))+add~1(4,hL,hR)⋅(V~1(h′,hL)+V~1(h′,hR))]=∑y1∈{0,1}∑y2∈{0,1}∑y3∈{0,1}∑y4∈{0,1}∑y5∈{0,1}(3y1−1)∗[(4y2(1−y3)y4y5)⋅[((1−y1)⋅((1−y2)(1−y3)+4(1−y2)y3+2y2(1−y3)+y2y3)+y1⋅(4(1−y2)(1−y3)+4(1−y2)y3+y2(1−y3)+y2y3))∗((1−y1)⋅((1−y4)(1−y5)+4(1−y4)y5+2y4(1−y5)+y4y5)+y1⋅(4(1−y4)(1−y5)+4(1−y4)y5+y4(1−y5)+y4y5))]+((−3)(1−y2)(1−y3)(1−y4)y5)⋅[((1−y1)⋅((1−y2)(1−y3)+4(1−y2)y3+2y2(1−y3)+y2y3)+y1⋅(4(1−y2)(1−y3)+4(1−y2)y3+y2(1−y3)+y2y3))+((1−y1)⋅((1−y4)(1−y5)+4(1−y4)y5+2y4(1−y5)+y4y5)+y1⋅(4(1−y4)(1−y5)+4(1−y4)y5+y4(1−y5)+y4y5))]]\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，也就是单变量多项式s1(y1)s_1(y_1)：

y2y3y4y5f(y1)0001(3y1−1)⋅(−3)⋅((1+3y1)+4)1011(3y1−1)⋅4⋅(2−y1)\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}

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

则：

s1(y1)=(3y1−1)⋅(−3)⋅((1+3y1)+4)+(3y1−1)⋅4⋅(2−y1)=2+2y1+y12=c0,1+c1,1y1+c2,1y12\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 需要把多项式s1(y1)s_1(y_1)的commitment发送给verifier，也就是把该多项式的4个系数的commitment 之后发过去：​

δc0,1=commit(c0,1)=commit(2)δc1,1=commit(c1,1)=commit(2)δc2,1=commit(c2,1)=commit(1)δc3,1=commit(c3,1)=commit(0)\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)\\

verifier 需要验证：​

s1(0)+s1(1)=?s0(2,4)=2s_1(0) + s_1(1) \overset{?}= s_0(2, 4) = 2

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

2δc0,1+δc1,1+δc2,1+δc3,1=?commit(s0(2,4))=commit(2)✓2 \delta_{c_{0, 1}} + \delta_{c_{1, 1}} + \delta_{c_{2, 1}} + \delta_{c_{3, 1}} \overset{?}= \text{commit}(s_0(2, 4)) = \text{commit}(2) \textcolor{green} {\checkmark}

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

s1(3)=2+6+9=17mod  5=2s_1(3) = 2 + 6 + 9 = 17\mod 5 = \textcolor{red} {2}

Round two


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

y3y4y5f(y2)0018⋅−3(1−y2)⋅((10−11y2)+4)0118⋅4y2⋅((10−11y2)∗1)\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}

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


则：​

s2(y2)=8⋅−3(1−y2)⋅((10−11y2)+4)+8⋅4y2⋅((10−11y2)∗1)=4+4y22=c0,2+c2,2y22\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 需要把多项式s2(y2)s_2(y_2)的commitment发送给verifier，也就是把该多项式的4个系数的commitment 之后发过去：​

δc0,2=commit(c0,2)=commit(4)δc1,2=commit(c1,2)=commit(0)δc2,2=commit(c2,2)=commit(4)δc3,2=commit(c3,2)=commit(0)\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)\\

verifier 需要验证：

s2(0)+s2(1)=?s1(3)=2s_2(0) + s_2(1) \overset{?}= s_1(3) = 2

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

2δc0,2+δc1,2+δc2,2+δc3,2=?commit(s1(3))=commit(2)✓2 \delta_{c_{0, 2}} + \delta_{c_{1, 2}} + \delta_{c_{2, 2}} + \delta_{c_{3, 2}} \overset{?}= \text{commit}(s_1(3)) = \text{commit}(2) \textcolor{green} {\checkmark}

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

s2(4)=4+64=68mod  5=3s_2(4) = 4 + 64 = 68\mod 5 = \textcolor{red} {3}

Round three


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

y4y5f(y3)018⋅9(1−y3)⋅((26y3−34)+4)118⋅16(1−y3)⋅((26y3−34)∗1)\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}

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


则：

s3(y3)=8⋅9(1−y3)⋅((26y3−34)+4)+8⋅16(1−y3)⋅((26y3−34)∗1)=3+2y3=c0,3+c1,3y3\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 需要把多项式s3(y3)s_3(y_3)的commitment发送给verifier，也就是把该多项式的4个系数的commitment 之后发过去：​

δc0,3=commit(c0,3)=commit(3)δc1,3=commit(c1,3)=commit(2)δc2,3=commit(c2,3)=commit(0)δc3,3=commit(c3,3)=commit(0)\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)\\

verifier 需要验证：​

s3(0)+s3(1)=?s2(4)=3s_3(0) + s_3(1) \overset{?}= s_2(4) = 3

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

2δc0,3+δc1,3+δc2,3+δc3,3=?commit(s2(4))=commit(3)✓2 \delta_{c_{0, 3}} + \delta_{c_{1, 3}} + \delta_{c_{2, 3}} + \delta_{c_{3, 3}} \overset{?}= \text{commit}(s_2(4)) = \text{commit}(3) \textcolor{green} {\checkmark}

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

s3(2)=3+4=7mod  5=2s_3(2) = 3 + 4 = 7\mod 5 = \textcolor{red} {2}

Round four


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

y5f(y4)18⋅−16y4⋅(18∗(4−3y4))+8⋅−9(1−y4)⋅(18+(4−3y4))\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}

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


则：

s4(y4)=8⋅−16y4⋅(18∗(4−3y4))+8⋅−9(1−y4)⋅(18+(4−3y4))=1+4y4+y42=c0,4+c1,4y4+c2,4y42\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 需要把多项式s4(y4)s_4(y_4)的commitment发送给verifier，也就是把该多项式的4个系数的commitment 之后发过去：​

δc0,4=commit(c0,4)=commit(1)δc1,4=commit(c1,4)=commit(4)δc2,4=commit(c2,4)=commit(1)δc3,4=commit(c3,4)=commit(0)\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)\\

verifier 需要验证：​

s4(0)+s4(1)=?s3(2)=2s_4(0) + s_4(1) \overset{?}= s_3(2) = 2

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

2δc0,4+δc1,4+δc2,4+δc3,4=?commit(s3(2))=commit(2)✓2 \delta_{c_{0, 4}} + \delta_{c_{1, 4}} + \delta_{c_{2, 4}} + \delta_{c_{3, 4}} \overset{?}= \text{commit}(s_3(2)) = \text{commit}(2) \textcolor{green} {\checkmark}

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

s4(4)=1+16+16=33mod  5=3s_4(4) = 1 + 16 + 16= 33\mod 5 = \textcolor{red} {3}

Round five


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

−f(y5)−8⋅−64y5⋅(18∗(26y5−34))+8⋅27y5⋅(18+(26y5−34))\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}

则：

s5(y5)=8⋅−64y5⋅(18∗(26y5−34))+8⋅27y5⋅(18+(26y5−34))=3y5=c1,5y5\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 需要把多项式s5(y5)s_5(y_5) 的commitment发送给verifier，也就是把该多项式的4个系数的commitment 之后发过去：​

δc0,5=commit(c0,5)=commit(0)δc1,5=commit(c1,5)=commit(3)δc2,5=commit(c2,5)=commit(0)δc3,5=commit(c3,5)=commit(0)\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)\\

verifier 需要验证：​

s5(0)+s5(1)=?s4(4)=3s_5(0) + s_5(1) \overset{?}= s_4(4) = 3

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

2δc0,5+δc1,5+δc2,5+δc3,5=?commit(s4(4))=commit(3)✓2 \delta_{c_{0, 5}} + \delta_{c_{1, 5}} + \delta_{c_{2, 5}} + \delta_{c_{3, 5}} \overset{?}= \text{commit}(s_4(4)) = \text{commit}(3) \textcolor{green} {\checkmark}

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

s5(1)=3s_5(1) = \textcolor{red} {3}

Last Round


目前challenge factor 的组合为：

(3,(4,2),(4,1))=(y1,(y2,y3),(y4,y5))=(r′,rL,rR)(3, (4, 2), (4, 1)) = (y_1, (y_2, y_3), (y_4, y_5)) = (r', r_L, r_R)

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

V~1(x1,x2,x3)=(1−x1)⋅[(1−x2)(1−x3)+4(1−x2)x3+2x2(1−x3)+x2x3]+x1⋅[4(1−x2)(1−x3)+4(1−x2)x3+x2(1−x3)+x2x3]\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：​

X=commit(V~1(r′,rL))=commit(V~1(3,(4,2)))=commit(3)Y=commit(V~1(r′,rR))=commit(V~1(3,(4,1)))=commit(2)Z=commit(V~1(r′,rL)⋅V~1(r′,rR))=commit(3∗2)=commit(1)\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 协议的最后验证：​

eq~1(2,r′)⋅[mul~1(4,hL,hR)⋅commit(V~1(r′,hL)⋅V~1(r′,hR))+add~1(4,hL,hR)⋅(commit(V~1(r′,hL))+commit(V~1(r′,hR)))]=8⋅[−64∗commit(1)+27∗(commit(3)+commit(2))]=?commit(s5(1))=commit(3)✓\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 ：​

V~1(x1,x2,x3)=(1−x1)⋅[(1−x2)(1−x3)+4⋅(1−x2)x3+2⋅x2(1−x3)+x2x3]+x1⋅[4⋅(1−x2)(1−x3)+4⋅(1−x2)x3+x2(1−x3)+x2x3]\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，也就是：​

V~1(r′,rL)=V~1(3,(4,2))=3V~1(r′,rR)=V~1(3,(4,1))=2\widetilde{V}_1(r', r_L) = \widetilde{V}_1(3, (4, 2)) = 3 \\ \widetilde{V}_1(r', r_R) = \widetilde{V}_1(3, (4, 1)) = 2 \\

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

fH(t)=V~1(r′,(1−t)⋅rL+t⋅rR)=V~1(3,(4,2−t))=18−26t=3+4t\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}

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

fH(0)=3=V~1(r′,rL)fH(1)=2=V~1(r′,rR)f_H(0) = 3 = \widetilde{V}_1(r', r_L) \\ f_H(1) = 2 = \widetilde{V}_1(r', r_R) \\

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

δf0=commit(3)δf1=commit(4)δf2=commit(0)\delta_{f_0} = \text{commit}(3) \\ \delta_{f_1} = \text{commit}(4) \\ \delta_{f_2} = \text{commit}(0) \\

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

commit(fH(0))=δf0commit(fH(1))=δf0+δf1\begin{aligned} \text{commit}(f_H(0)) &= \delta_{f_0} \\ \text{commit}(f_H(1)) &= \delta_{f_0} + \delta_{f_1} \\ \end{aligned}

这样就可以验证prover 之前发送的V~1(r′,rL)、V~1(r′,rR)\widetilde{V}_1(r', r_L)、\widetilde{V}_1(r', r_R)的commitment 是否与当前多项式的commitment 是否一致：

commit(V~1(r′,rL))=commit(3)=?commit(fH(0))=δf0✓commit(V~1(r′,rR))=commit(2)=?commit(fH(1))=δf0+δf1✓\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 之前发送的V~1(r′,rL)、V~1(r′,rR)\widetilde{V}_1(r', r_L)、\widetilde{V}_1(r', r_R)的commitment X、Y是否合法，基于多项式fH(t)f_H(t)的commitment δf0、δf1、δf2\delta_{f_0} 、\delta_{f_1}、\delta_{f_2}， verifier 随机采样一个challenge factor vv 并发送给prover，prover 自然可以计算出下一轮sumcheck协议需要证明的evaluation值fH(v)f_H(v)，即：

V~1(q′,q)=∑h′∈{0,1}bN∑hL∈{0,1}bG∑hR∈{0,1}bGPq′,q,2(h′,hL,hR)=∑h′∈{0,1}bN∑hL∈{0,1}bG∑hR∈{0,1}bGeq~2(q′,h′)⋅[mul~1(q,hL,hR)(V~2(h′,hL)∗V~2(h′,hR))+add~2(q,hL,hR)(V~1(h′,hL)+V~2(h′,hR))]=?fH(v)=3+4v\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协议需要证明的fH(v)f_H(v) 的commitment：

commit(fH(v))=δf0+δf1⋅v+δf2⋅v2\text{commit}(f_H(v)) = \delta_{f_0} + \delta_{f_1} \sdot v + \delta_{f_2} \sdot v^2

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

commit(V~1(3,(4,2−v)))=?δf0+δf1⋅v+δf2⋅v2ORcommit(V~1(3,(4,2))=?commit(3)commit(V~1(3,(4,1))=?commit(2)\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


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

image.png

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

V~2(x1,x2,x3)=(1−x1)⋅[(1−x2)(1−x3)+2⋅(1−x2)x3+x2(1−x3)+4⋅x2x3]+x1⋅[2⋅(1−x2)(1−x3)+3⋅(1−x2)x3+2⋅x2(1−x3)+4⋅x2x3]\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′,rL,rR)=(2,(3,2),(3,3))(r', r_L, r_R) = (2, (3, 2), (3, 3))：

V~2(r′,rL)=?V~2(2,(3,2))=0V~2(r′,rR)=?V~2(2,(3,3))=1\widetilde{V}_2(r', r_L) \overset{?}= \widetilde{V}_2(2, (3, 2)) = 0 \\ \widetilde{V}_2(r', r_R) \overset{?}= \widetilde{V}_2(2, (3, 3)) = 1 \\

多项式fH(t)f_H(t)：

fH(t)=tf_H(t) = t

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

V~2(2,(3,4))=?fH(v)=2\widetilde{V}_2(2, (3, 4)) \overset{?}= f_H(v) = 2

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


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

commit(fH(2))=δf0+δf1⋅2+δf2⋅22=commit(1)⋅2\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：

(1,2,1,4⏟public input,2,3,2,4⏟witness)(\underbrace{1, 2, 1, 4}_{\text{public input}}, \underbrace{2, 3, 2, 4}_{\textcolor{red}{\text{witness}}})

因此，我们需要把V~2\widetilde{V}_2拆解成两部分

V~2(x1,x2,x3)=(1−x1)⋅p~(x2,x3)+x1⋅w~(x2,x3)\widetilde{V}_2(x_1, x_2, x_3) = (1 - x_1) \sdot \widetilde{p}(x_2, x_3) + x_1 \sdot \widetilde{w}(x_2, x_3)

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

w~(x2,x3)=2⋅(1−x2)(1−x3)+3⋅(1−x2)x3+2⋅x2(1−x3)+4⋅x2x3⇓commit(w~(x2,x3))=commit(2)⋅(1−x2)(1−x3)+commit(3)⋅(1−x2)x3+commit(2)⋅x2(1−x3)+commit(4)⋅x2x3\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 ：​

2⋅commit(1)=?(1−2)⋅commit(p~(3,4))+2⋅commit(w~(3,4))=4⋅commit(p~(3,4))+2⋅[commit(2)⋅1+commit(3)⋅2+commit(2)⋅1+commit(4)⋅2]\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

点赞 0
收藏 0
分享
本文参与登链社区写作激励计划 ，好文好收益，欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论
白菜
白菜
0x6b50...a615
crypto

白菜

如果觉得我的文章对您有用，请随意打赏。你的支持将鼓励我继续创作！