GKR协议：逐步示例

介绍

交互式证明是一种在两个参与方之间进行的协议，证明者 $P$ 尝试说服验证者 $V$ 证明某个声明的有效性。通过利用随机性和交互，验证者可以比起自己独立完成所有工作来更高效地检查该声明。我们可以用一种简单的方法来验证计算：重新执行。这正是区块链实现可验证性的方式：每个节点重新执行交易，然后达成共识。然而，这种方法效率低下，因为每个节点都必须重复相同的计算，导致瓶颈。简洁证明允许我们更快速地检查计算，避免重新执行并解决区块链的可扩展性问题。有关交互式证明系统的介绍，请参见 Thaler。其中一个这样的协议是由 Lund、Fortnow、Karloff 和 Nisan 于 1992 年提出的sum-check协议，这是多个证明系统使用的基础构件之一。

GKR 协议（Goldwasser–Kalai–Rothblum）扩展了 sum-check协议 的概念，以实现对算术电路的高效验证。该协议允许验证者检查一个计算即被表示为使用低度门的对数深度电路已被正确执行。这是通过仅需 O(log(n)) 的交互轮数和总共 O(polylog(n)) 的操作完成的。

GKR 协议的关键思想是，不是评估整个电路，而是通过递归利用 sum-check 协议高效验证表示计算值的部分总和。这种方法使资源有限的验证者能够检查远大于他们自己能够执行的计算，利用问题的基本代数结构。GKR 协议的优势在于避免了对电路中间结果的承诺，这通常是许多证明系统中最昂贵的部分。

这篇文章将通过一个示例解释该协议是如何工作的。有关协议的更多解释，我们建议观看双高效交互式证明的 第 1 部分 和 第 2 部分 ，或阅读 Thaler 的书 或这篇 简短说明。GKR 协议用于改进 LogUp 查询论证。你可以查看在 Stwo 中的实现。

协议

这篇文章的目标是详细解释该协议。为此，我们将使用一个简单的示例，并逐步跟随证明者（$P$）和验证者（$V$）所做的一切。

注意：我们将考虑协议的交互式版本。 你可以通过 Fiat-Shamir 转换将其转换为非交互式协议。

让我们首先描述我们希望证明的计算。我们必须将计算表达为在有限域 Fp 上的 log-space 合成算术电路 CC，具有 2 的输入复杂度。这意味着：

• 电路只有两种类型的门：加法和乘法。
• 电路是分层的，每个门仅连接到前一层的两个门（可能是同一个门）。
• 在每一层 ii，门的数量是 Si=2ki，其中 ki ∈ N。
• 所有值都是 Fp 的元素。

让我们构建一个满足这些条件的电路：

图 1：用于 GKR 协议示例的算术电路图。

该电路建模了一个具有 2 个输入和 2 个输出的程序，并且我们在有限域 F23 上进行操作。

协议的最终目标是证明者向验证者提供程序的输出，并说服验证者这些输出是从公共输入正确计算得出的。

请记住，电路和输入都是公开的。

第一部分：共享结果

我们可以将此分为几个步骤：

1. 输出声明：

证明者 $P$ 将声称为电路输出的值发送给验证者 $V$。这些值以函数的形式发送，$D:0,1^{k_0}→F_p$。

对于我们的示例：$k_0=1$，因此 $P$ 发送满足的线性多项式 D：

D(0)=18，D(1)=7

2. 随机挑战：

我们将在协议中频繁使用的一个关键资源是让验证者选择一个随机点并将其发送给证明者。证明者必须将此点纳入其计算中。这防止了证明者预先计算结果并试图欺骗验证者。

$V$ 选择随机 $r_0∈Fk0$，并将其发送给 $P$。

让我们选择 r_0=2。

3. 计算多线性扩展：

$V$ 和 $P$ 计算 $ \tilde D(r_0)$，其中 $ \tilde D(x)$ 为 D 的多线性扩展。这是 $Fp$ 上唯一的多线性多项式，满足：

$ \tilde D(x)=f(x)，对所有 x∈0,1^v$

这是一个 v−变数多项式， $ \tilde D(x) $ 在所有布尔值（或给定长度的比特串）输入上与 D(x) 一致。它作为 D(x) 的距离扩展编码，因为如果另一个函数 D′(x) 在一个输入上有不同，那么扩展 ~D(x) 将在原域之外几乎每一点与 D′(x) 不同。这是 Schwartz-Zi$P$el 引理 的结果，该引理指出随机选择多项式零点的概率为 v/|Fp|（对于足够大的域可忽略不计）。

使用拉格朗日插值，我们有：

$$ \tilde{f}(x_1, \ldots, xv) = \sum{w \in {0, 1^v }} f(w) \cdot \chi_w(x_1, \ldots, x_v) $$

其中 $χ_w$ 是（多线性）拉格朗日基多项式：

$$ \chi_{w}(x_1, \ldots, xv) = \prod{i=1}^v \left( x_i \cdot w_i + (1 - x_i)(1 - w_i) \right) $$

在我们的例子中（k0=1）：

~D(x)=D(0):(x⋅0+(1−x)(1−0))+D(1):(x⋅1(1−x)(1−1))=D(0)⋅(1−x)+D(1)⋅x=18(1−x)+7x。

因此：

~D(r_0)=~D(2)=−4≡19 mod (23)，我们将该值记为：

~D(r_0)=19=m0。

现在，我们可以看到验证程序的输出归结为检查：

m0=~W0(r_0)。

在继续之前，让我们引入一个额外的符号。对于电路的每一层 ii，我们将表示：

Wi:{0,1}ki→Fp。

以映射节点位置到其实际值的函数，~Wi(x) 为其多线性扩展。

通过这个符号，验证者的任务可以视为检查：

D(x)=W0(x)。

因为 D(x) 代表声称输出而 W0(x) 表示正确值。由于多线性扩展是唯一的，这等同于验证：

~D(x)=~W0(x)。

最后，根据 Schwartz-Zi$P$el 引理，仅需检查：

~D(r_0)=~W0(r_0)。

但等一下！验证者不能直接访问 W(x)。这就是协议的目的！

第二部分：建模电路

在此阶段，目标是验证多个项（对应于节点计算值）的总和是否等于 m0。

为此，我们高效使用sum-check协议。

引入布线函数

我们定义两个函数来捕获电路的布线：

• 加法函数。

该函数标记第 ii 层中的所有加法节点。它的输入为：

x∈{0,1}ki+2ki+1。

这编码了当前层中加法节点的位置信息 a，以及连接到此节点的下一层两个节点 b 和 c 的位置信息。

加法函数 Addi 定义为当 x=(a,b,c) 对应一个有效的加法节点并且输入正确时为 1，否则为 0。

与 ~D(x) 类似，我们将需要创建多线性扩展：˜Addi(x)。

在我们的电路中：

输出加法节点位于位置：a=(1)。

并且连接到节点：b:(1,0)(1,0)，c:(1,1)(1,1)。

由于这是唯一的加法节点，我们定义函数为：

Add_1(x){1 if x=(1,1,0,1,1) 0 if not.Add_1(x){1 if x=(1,1,0,1,1) 0 if not。

然后我们将该函数扩展为多线性多项式，记作 ˜Addi(x)：

˜Add1(x1,x2,x3,x4,x5)=x1⋅x2⋅(1−x3)⋅x4⋅x5。

• 乘法函数。

类似地，我们定义乘法节点的函数 Mult0(x) 及其多线性扩展。

对于我们第一层的乘法节点：

Mult_1(x){1 if x=(0,0,0,0,1) 0 if not.Mult_1(x){1 if x=(0,0,0,0,1) 0 if not。

它的多线性扩展为：

˜Mult_1(x1,x2,x3,x4,x5)=(1−x1)⋅(1−x2)⋅(1−x3)⋅(1−x4)⋅x5。

最后，我们需要连接这两个新函数。为此，我们可以定义一个函数，该函数“计算”第 ii 层中给定下一层值的节点值：

~f(i)(a,b,c):=˜Add_i(a,b,c)⋅(~Wi+1(b)+~Wi+1(c))+˜Mult_i⋅~Wi+1(b)⋅~Wi+1(c)。

该函数在对应于第 ii 层节点的值 (a,b,c) 上评估时，将返回该节点的值。

在我们的第一层：

~f(0)(0,0,0,0,1)=18， ~f(0)(1,1,0,1,1)=7。

这个函数很方便，但是我们可以更进一步，固定 a=ra=r 并对所有可能的二进制分配 b 和 c 进行求和，我们得到：

∑(b,c)∈{0,1}2ki~f(i)(r,b,c)=~W(r)。

这个新函数现在是一个单变量多项式！

让我们将固定 a=r 的函数表示为 ~fr(b,c)(i)。

让我们回顾一下我们要检查的内容：

~D(r_0)=~W(r_0)。

亦即，

~W(r_0)=m0。

因此，使用新函数 ~ff，我们可以将其视为：

∑(b,c)∈0,12ki~f(0)r_0(b,c)=m0。

为了验证这个等式，这意味着有很多加法（操作），我们将使用sum-check协议。

第三部分：sum-check

让我们逐步描述在这一阶段，证明者和验证者所做的所有操作，以更好地理解协议。

1. 证明者 $P$ 构建新的函数 g1(z):

g1(z):Fp→Fpg1(z):Fp→Fp。

g1(z):=∑(x2,x3,...,x2k1)∈{0,1}2k1−1~f(0)r_0(z,x2,...,x2k1−1)。

换句话说，我们将 ~f(0)r_0(x) 的第一个坐标留作自由变量 z，然后对剩余坐标的所有可能赋值进行求和。

观察该函数满足：

g1(0)+g1(1)=m0。

因为 g1(0) 计算的是第一个坐标为 0 的所有组合的和，而 g1(1) 则是第一个坐标等于 1 的情况。

在我们的例子中，k1=2（即第2层有 2^2=4 个节点），我们有：

g1(z)=∑(x2,x3,x4)∈{0,1}3~f(0)r_0(z,x2,x3,x4)。

计算 g1(0) 和 g1(1) 可以得到以下多项式...

...（后面的内容减少）...

现在我们必须保持 b1 固定，其中 b1,c1,c2 变化。

由于乘法因子的影响（例如，类似于

2b1(1−b2)c1c2

除非 (c1=c2=1) 在第一项中，该项消失，而在第二项亦然）， 大多数组合将贡献为零。在我们的例子中，我们假设在代入后，唯一的非零贡献来自：

• 案例 1： 当 (b2,c1,c2)=(0,1,1) 时。
• 案例 2： 当 (b2,c1,c2)=(0,0,1) 时。

我们将单独分析这些案例。

案例 1： (b2,c1,c2)=(0,1,1)。

2b1[3(1−b1)+4b1+3]→2x(x−6)→2x^2+12x。

案例 2： (b2,c1,c2)=(0,0,1)。

−(1−b1)[3(1−b1)+4b1]6→−6(1−x)(3−3x+4x)→(−6+6x)(x+3)−(1−b1)[3(1−b1)+4b1]6→−6(1−x)(3−3x+4x)→(−6+6x)(x+3)。

这些和的结果是：

g1(z)=8z^2+24z−18≡8z^2+z−18。

证明者将该多项式发送给验证者（由于其低度可以直接发送系数）。

验证者检查两件事：

• g1 是否确实是低度多项式。
• g1(0)+g1(1)=m0。

在我们的例子中： g1(0)=−18， g1(1)=14， g1(0)+g1(1)=−4≡19=m0。

2. 验证者 $V$ 选择一个随机值 s1∈Fp 并将其发送给证明者 $P$。验证者还计算：

g1(s1)=C1。

我们可以取样 s1=3: g1(s1)=g1(3)=8⋅32+24⋅3−18=126≡11。

3. 收到 s1 后，FP 计算 C1，然后重复类似过程。证明者定义新函数：

g2(z):Fp→Fpg2(z):Fp→Fp。

g2(z):=∑(x3,...,x2k1)∈{0,1}2k1−2~f(0)r_0(s1,z,x3...,x2k1−2)。

此处，证明者将第一个变量固定为 s1，并将第二个变量留空（由 z 表示），对其他每个二进制分配进行求和。

我们有：

g2(z)=∑(x3,x4)∈{0,1}2~f(0)r_0(s1,z,x3,x4)。

g2(z)=162x^2−288x+126≡x^2−12x+11。

4. 证明者 $P$ 将 g2(z) 的系数发送给 $V$。

5. 验证者检查：

g2(0)+g2(1)=C1。

g2(0)=0。

我们必须检查： g2(1)=11， g2(0)+g2(1)=11。

6. 此过程重复，直至验证者收到 C2k+1：

C2k+1:=~f(0)r_0(s1,s2,x3...,s2ki+1)。

这是sum-check协议的最后一步。 此时，验证者通常会查询一个 Oracle 直接计算这个值；然而，在我们的协议中，验证者无法直接评估该函数。

验证者可以构建 ˜Add 和 ˜Mult，但无法构建 ~Wi+1，这些值表示直接前一层的节点值。

我们实现了什么？

实际上，我们已经将验证电路的输出问题简化为验证一层低的值。这种简化一层对一层重复，直到达到最后一层，即验证者已经知道的输入。这实际上就是协议的整个思想。

让我们为我们的示例进行计算：

• $V$ 取样 s2=2 并将其发送给 $P$。

• $V$ 和 $P$ 计算 C2=g2(s2)： g2(s2)=g2(2)=22−12⋅2+11=−9≡14。

• $P$ 计算： g3(z)=∑x4∈{0,1}~f(0)r_0(s1,s2,z,x4)→~g3(z)=90x^2−180x+144≡21x^2−19x+6。

• $V$ 接收到 g3(z)，并检查： g3(0)=8， g3(1)=6， g3(0)+g3(1)=14。

• $V$ 选择 s3=4 并发送给 $P$。

• $V$ 和 $P$ 计算 C3=g3(s3)： g3(s3)=21⋅42−19⋅4+6=266≡13。

• $P$ 计算：

  g4(z)=~f(0)r_0(s1,s2,s3,z)。

  g4(z)=−288z^2+1152z≡11z^2+2z。

• $V$ 收到 g4(z)，并检查： g4(0)=0， g4(1)=13， g4(0)+g3(1)=13。

• $V$ 选择 s4=7 并发送给 $P$。

• $V$ 和 $P$ 计算 C4=g4(s4)： g4(s4)=553≡1。

• $P$ 计算:

  ~f(0)r_0(s1,s2,s3,s4)=C4。

  ~f(0)(r1,s1,s2,s3,s4):=˜Add1(r1,s1,s2,s3,s4)⋅(~W2(s1,s2)+~W2(s3,s4)) + ˜Mult1(r1,s1,s2,s3,s4)⋅~W2(s1,s2)⋅~W2(s3,s4)。

第四部分：递归

我们已经达到这样的阶段：验证者的目标是检查

~f(0)r_0(s1,s2,x3,...,s2ki+1)=C1。

然而，要做到这一点，验证者需要知道：

~W2(s1,s2,...,sk+1)， ~W2(sk+1,...,s2k+1)。

如果验证者要为这些值执行两次单独的sum-check，最后的工作量将是巨大的。相反，证明者在一点做出单一主张，如何做到这一点？

双方计算唯一函数：

ℓ:F→F2k。

满足：

ℓ(0)=(s1,s2,...,sk+1)， ℓ(1)=(sk+1,...,s2k+1)。

然后 $P$ 将函数发送给验证者：

q=~W2∘ℓ:F→F。

注意：

q(0)=~W2(s1,s2,...,sk+1) 和 q(1)=~W2(sk+1,...,s2k+1)。

因此，凭借 q(x)，验证者可以恢复完成sum-check协议所需的值 q(0) 和 q(1)。

因此，凭借 q(x)，$V$ 可以利用 q(0) 和 q(1) 进行sum-check协议中的最后一次评估。

但验证者如何知道 q(x) 是正确的？再次，$V$ 选取一个随机元素 r∗∈F 并计算：

r1=ℓ(r∗)。

然后，$P$ 和 $V$ 计算：

m1=q(r1)。

现在，证明者的任务是说服验证者：

~W2(r1)=m1。

这个主张类似于我们最初的验证步骤：

~D(r_0)=m0。

其中 ~D(x) 编码了输出值，现在 ~W2(x) 编码了直接前一层节点的值。

因此，剩下的任务是对这层应用相同的sum-check协议。> 对于我们的电路：

• $P$ 和 $V$ 计算：

  ℓ(0)=(s1,s2)=(3,2)ℓ(0)=(s1,s2)=(3,2)ℓ(1)=(s3,s4)=(4,7)ℓ(1)=(s3,s4)=(4,7)ℓ(x)=(s1(1−x)+s3x,s2(1−x)+s4x)=(3(1−x)+4x,2(1−x)+7x).ℓ(x)=(s1(1−x)+s3x,s2(1−x)+s4x)=(3(1−x)+4x,2(1−x)+7x).

• $P$ 发送 q=~W1∘ℓ:F→F.q=W~1∘ℓ:F→F.

  q(x)=−20x²−52x−12≡3x²+17x+11q(x)=−20x²−52x−12≡3x²+17x+11

• $V$ 检查 ~f(0)r_0(s1,s2,s3,s4)=c4f~r_0(0)(s1,s2,s3,s4)=c4，使用 q(x)q(x)

• $V$ 发送 $P$ 一随机数 r∗∈Fr∗∈F

  r∗=6r∗=6

• $V$ 和 $P$ 计算：

  r1=ℓ(6)=(9,32)≡(9,9)r1=ℓ(6)=(9,32)≡(9,9)m1=q(6)=14.m1=q(6)=14.

• 现在 $P$ 需要说服 $V$：

  ∑(b,c):∈0,12⋅1f(1)r1(b,c)=m1∑(b,c):∈0,12⋅1fr1(1)(b,c)=m1

• $P$ 计算 g1(z)g1(z) 并发送给 $V$：

  g1(z)=∑x₂∈0,1f(1)r1(z,x₂)g1(z)=∑x₂∈0,1fr1(1)(z,x₂)g1(z)=2z²+7z+14g1(z)=2z²+7z+14

• $V$ 检查 g1(0)+g1(1)=m1g1(0)+g1(1)=m1：

  g1(0)=14g1(0)=14g1(1)=0g1(1)=0g1(0)+g1(1)=14g1(0)+g1(1)=14

• $V$ 采样 s1=12s1=12 并发送给 $P$。

• $V$ 和 $P$ 计算 C1=g1(s1)C1=g1(s1)：

  g1(12)=2⋅12²+7⋅12+14=386≡18g1(12)=2⋅12²+7⋅12+14=386≡18

• $P$ 计算 g2(z)g2(z) 并发送给 $V$：

  g2(z)=~f(1)r1(s1,z)g2(z)=f~r1(1)(s1,z)g2(z)=9z²+z+4g2(z)=9z²+z+4

• $V$ 检查 g2(0)+g2(1)=C1g2(0)+g2(1)=C1：

  g2(0)=4g2(0)=4g2(1)=14g2(1)=14g2(0)+g2(1)=18g2(0)+g2(1)=18

• $V$ 采样 s2=5s2=5 并发送给 $P$。

• $V$ 和 $P$ 计算 C2=g2(s2)C2=g2(s2)：

  C2=g2(5)=4C2=g2(5)=4

• $P$ 和 $V$ 计算：

  ℓ(0)=s1=12ℓ(0)=s1=12ℓ(1)=s2=5ℓ(1)=s2=5ℓ(x)=−7x+12ℓ(x)=−7x+12

• $P$ 发送 q=~W1∘ℓ:F→F.q=W~1∘ℓ:F→F.

  q(x)=3(1−(−7x+12))+(−7x+12)q(x)=3(1−(−7x+12))+(−7x+12)

• $V$ 检查 f(1)r1(s1,s2)=c2fr1(1)(s1,s2)=c2，使用 q(x)q(x)

• $V$ 发送 $P$ 一随机数 r∗∈Fr∗∈F

  r∗=17r∗=17

• $V$ 和 $P$ 计算：

  r2=ℓ(17)=8r2=ℓ(17)=8m2=q(17)=10m2=q(17)=10

• 最后，$V$ 计算 ~W2(x)W~2(x) 并检查 ~W2(r2)=m2W~2(r2)=m2

  W2(0)=3W2(0)=3W2(1)=1W2(1)=1~W2(x)=3(1−x)+xW~2(x)=3(1−x)+x~W2(8)=10W~2(8)=10

最后部分：重复

好吧，一切几乎准备好了！我们只需针对每一层重复这个过程。最后，$Wd(x)$ 是将程序输入映射的函数，我们将用其验证层 $d−1$ 的sum-check。如果这个检查是正确的，这意味着之前的所有检查也是正确的，因此我们可以自信地说计算是正确执行的。

结论：

总之，GKR 协议优雅地将验证复杂算术电路输出的问题简化为一系列较简单的验证，这些验证递归地从输出层移动到输入层。每一步依赖于代数性质——尤其是多线性扩展的唯一性和 Schwartz–Zi$P$el 引理——确保一个资源有限的验证者可以高效地确认计算的正确性。这个协议展示了互动证明的力量，并为更高级的加密应用奠定了基础，例如零知识证明。

• 原文链接： blog.lambdaclass.com/gkr...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～