Sum-Check & GKR

• Formal Verification of the Sumcheck Protocol
• Algebraic Methods for Interactive Proof Systems
• Proofs, Arguments, and Zero-Knowledge
• A GKR Tutorial
• Sum-Check: The Backbone of ZK Proofs

Intro

Sumcheck 是一种交互式的ZKP scheme.

Multivariate and multilinear polynomials

多变量多项式，形如：

$$g(x_1,x_2,\dots ,x_n)=\sum _{i_1,i_2,\dots ,i_n}{a}_{i_1,i_2,\dots ,i_n}{x}_1^{i_1}{x}_2^{i_2}\dots x_n^{i_n}$$

的被称为多变量多项式，注意这些运算都是在有限域 $\mathbb{F}$ 上进行的，每个元素在 $0,1$ 上取值。

multilinear polynomials 是一种特殊形式，其中所有的元素 $x_n$ 都只有0或1次幂：

布尔 hypercube

一个n维的hypercube包含所有的二进制点集，例如在三维中， $02^n-1$ 遍历8个点，其hypercube就可以表示为一个 list：

$${[}^{\prime }{000}^{\prime }{,}^{\prime }{001}^{\prime }{,}^{\prime }{010}^{\prime }{,}^{\prime }{011}^{\prime }{,}^{\prime }{100}^{\prime }{,}^{\prime }{101}^{\prime }{,}^{\prime }{110}^{\prime }{,}^{\prime }{111}^{\prime }]$$

而对于多项式在hypercube上的估值，假设我们有一个三变量多项式 $f(x,y,z)=x\ast y+z+2$，其在三维hypercube上的估值可以表示为：

f(0, 0, 0) + f(0, 0, 1)
+ f(0, 1, 0) + f(0, 1, 1)
+ f(1, 0, 0) + f(1, 0, 1)
+ f(1, 1, 0) + f(1, 1, 1)

这样求值后，就会得到 $F$ 上的一个值。

Equality function

eq是一个元素需要在 $\{0,1\}$ 上取值的函数，这里简化起见，只取 $x$ 和 $y$ 两个变量：

• $eq(x,y)=1$, if $x=y$
• $eq(x,y)=0$, if $x\ne y$

Its multilinear extension over a field $\mathbb{F}$ is given by:

$$eq(x,y)=\prod _{i=0}^{n-1}(x_i{y}_i+(1-x_i)(1-y_i))$$

The formula says if each bit of $x$ match the corresponding bit of $y$ then return 1, else return 0. Take $\{0,1{\}}^2$ as example, for each term inside the multiplication sign:

• $ter{m}_i=x_i{y}_i+(1-x_i)(1-y_i)$
• If $x_i=1$ and $y_i=1$: $1(1)+(0)(0)=1+0=\mathbf{1}$ (Match)
• If $x_i=0$ and $y_i=0$: $0(0)+(1)(1)=0+1=\mathbf{1}$ (Match)
• If $x_i=1$ and $y_i=0$: $1(0)+(0)(1)=0+0=\mathbf{0}$ (Mismatch)
• If $x_i=0$ and $y_i=1$: $0(1)+(1)(0)=0+0=\mathbf{0}$ (Mismatch)

After we multiply all the terms, if the final result is 1 then it means all the terms are in "Match" state.

Sum-Check Protocol

假设我们有一个v变量多项式 $g$ 在有限域 $\mathbb{F}$ 上，我们的目标是让Prover向Verifier证明：

$$H:=\sum _{x_i}^{i}g(x_1,x_2,\dots ,x_v)$$

在这里，$x_i$ 取值于 $\{0,1\}$，因此总共有 $2^v$ 种组合，既同样的，有 $2^v$ 个项需要求和。

简单地说，就是 P 要证明这个求和是正确的，Sum-Check 可以使得 V 只需要检查 $O(v)$ 次多项式的评估从而验证等式正确性。 吐槽，感觉evaluate的翻译真不如改成赋值

Start-up

P发送一个值 $C_1$，并声称这个值等于 $H$

Round 1

P 发送一个一元多项式，其形式为：

$$g_1(X_1)=g(X_1,x_2,x_3,\dots ,x_v)$$

这里，小写部分表示此元素按 $\{0,1\}$ 取值并需要遍历 $2^{v-1}$ 种情况

下面以一个二元多项式为例：

$$g_1(X_1)=g(X_1,0)+g(X_1,1)$$

在这里，显然 $g_1$ 是一个关于 $X_1$ 的一元多项式

并且声称 $g_1=s_1$，既 $s_1$ 才是真正正确的多项式

并且我们把正确的情况可以简化表示为 $H=s_1(0)+s_1(1)$

然后，V 检查 $C_1=g_1(0)+g_1(1)$ 是否成立，如果不成立则拒绝。

一旦通过，V 还要再选择一个在 $\mathbb{F}$ 上的随机值 $r_1$ (注意这里不用是布尔值)，选取这个值是因为防止 P 作恶， 如果 $g_1$ 是诚实的，则 $g_1(r_1)=s_1(r_1)$ 不成立的概率至少为 $1-\frac{deg(g_1)}{|\mathbb{F}|}$

Round j

记住我们在上一轮选取的随机值 $r_1$，第二轮 P 再发送一个一元多项式：

$$g_2(X_2)=g(r_1,X_2,x_3,\dots ,x_v)$$

然后V 进行检查并生成一个新的随机值 $r_2$：

$$g_1(r_1)=g_2(0)+g_2(1)$$

就这样不断递归运行

$$g_j(X_j)=g(r_1,r_2,\dots ,r_{j-1},X_j,x_{j+1},\dots ,x_v)$$

check:

$$g_{j-1}(r_{j-1})=g_j(0)+g_j(1)$$

Round v

直到运行到 $v$ 轮，得到最终的形式：

$$g_v(X_v)=g(r_1,r_2,\dots ,r_{v-1},X_v)$$

此时，直接检查：

$$g_v(r_v)=g(r_1,r_2,\dots ,r_{v-1},r_v)$$

一个三变量的示例

Start-up

$$g(X_1,X_2,X_3)=2X_1^3+X_1{X}_2+X_2{X}_3$$

在Hypercube上，这个多项式的求和为： $H=12$

Round 1

P计算 $s_1(X_1）\leftarrow g_1(X_1)$:

$$g(X_1,0,0)+g(X_1,0,1)+g(X_1,1,0)+g(X_1,1,1)=(2X_1^3)+(2X_1^3+X_1)+(2X_1^3)+(2X_1^3+X_1+1)$$$$=8X_1^3+2X_1+1$$

V检查 $H=s_1(0)+s_1(1)=12$， 检查通过，选择随机值 $r_1=2$

Round 2

P计算 $s_2(X_2）\leftarrow g_2(X_2)$:

$$s_2(X_2)=g(2,X_2,0)+g(2,X_2,1)=34+X_2$$

V 检查 $s_2(0)+s_2(1)==s_1(r_1)==69$

通过，选择随机值 $r_2=3$

Round 3

P 计算多项式 $s_3(X_3)=g(r_1,r_2,X_3)=16+5X_3$

V 检查 $s_3(0)+s_3(1)==s_2(r_2)==37$

V 选择随机值 $r_3=6$, 检查 $s_3(r_3)==g(r_1,r_2,r_3)$

如果检查都通过，则 V 接受证明

Sage Code

Start-up

# Start-up

# 定义伽罗瓦域 GF(17)
F = GF(17)

# 这里设置 x1 , x2, x3
T.<x1,x2,x3> = F[]
Rx.<x> = F[]

# 定义多项式 g
g = 2*x1^3+x1*x2 + x2*x3
print("多项式 g:", g)

# 生成 维度为 3 的 hypercube
import itertools
dimention = 3
cube = list(itertools.product([0,1], repeat=dimention))
print("hypercube:", cube)

# 计算在Hypercube上的和H
H = sum([g(i) for i in cube])
print("H =", H )

""" 
多项式 g: 2*x1^3 + x1*x2 + x2*x3
hypercube: [(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)]
H = 12
"""

Round 1

# Round 1

# 计算多项式 g1(X_1)

g1 = sum([g(x1, x2, x3) for x2,x3 in itertools.product([0,1], repeat=2)])
print("多项式 g1(X_1)=", g1)

#  转换g1到单变量多项式
g1 = Rx(g1(x,0,0))

# 检查 g1(0) + g1(1)
sum_check = g1(0) + g1(1)
print("g1(0) + g1(1) =", sum_check)
assert(sum_check == H)

# 检查通过，选择随机值r1 = 2
# 一般来说可以使用 F.random_element() 来选择随机值
r1 = 2

""" 
多项式 g1(X_1)= 8*x1^3 + 2*x1 + 1
g1(0) + g1(1) = 12
"""

Round 2

# Round 2

# 计算多项式 g2(X_2)
g2 = g(r1, x2, 0) + g(r1, x2, 1)
print("多项式 g2(X_2):", g2)  # 注意这里是在  GF(17) 上的形式，所以输出和文章表述不一致

# 转换g2到单变量多项式
g2 = Rx(g2(0,x,0)) 

# 检查g2(0)+g2(1) == g1(r1) == 69 == 1 mod 17
left = g2(0) + g2(1)
right = g1(r1)
print("g2(0) + g2(1) =", left)
print("g1(r1) =", right)

# 选择 随机值 r2 = 3 
r2 = 3

""" 
多项式 g2(X_2): 5*x2 - 2
g2(0) + g2(1) = 1
g1(r1) = 1
"""

Round 3

# Round 3

# 计算多项式 g3(X_3)
g3 = g(r1, r2, x3)
print("多项式 g3(X_3):", g3)

# 转换g3到单变量多项式
g3 = Rx(g3(r1,r2,x))

# 检查 g3(0) + g3(1) == g2(r2)
left = g3(0) + g3(1)
right = g2(r2)
print("g3(0) + g3(1) =", left)
print("g2(r2) =", right)

# 最后选取 r3 = 6
r3 = 6

# 检查g3(r3) == g(r1, r2, r3)
left = g3(r3)
right = g(r1, r2, r3)
print("g3(r3) =", left)
print("g(r1, r2, r3) =", right)

""" 
多项式 g3(X_3): 3*x3 + 5
g3(0) + g3(1) = 13
g2(r2) = 13
g3(r3) = 6
g(r1, r2, r3) = 6
"""

GKR Protocol

假设 P 要向 V 证明 对于一个 在 ${\mathbb{F}}_2$ 上的布尔电路 $C$，其输出 $y$ 是正确的，这就是 GKR 的目标，对于验证者 V 来说，其时间复杂度为 $O(d\cdot logS)$，其中， $S$ 指电路的门数量，$d$ 指电路的深度。