在零知识证明（Zero-Knowledge Proof, ZKP）中，GKR 协议（Goldwasser–Kalai–Rothblum protocol）是一种用于验证算术电路（Arithmetic Circuit）计算正确性的高效交互式证明系统。它通过多变量 Sumcheck 协议（Multivariate Sumcheck Protocol）递归地验证分层电路的输出与输入之间的关系，实现了在通信复杂度对数级、验证复杂度低于线性的前提下，对任意多层电路的正确性证明。

1. 算术电路与分层结构的形式化定义

设有一个算术电路：

$$ C: \mathbb{F}^{s_n} \to \mathbb{F} $$

该电路由 $n$ 层构成，从输入层 $n$ 到输出层 $0$，层与层之间通过有向边连接：

Layered Arithmetic Circuit:
  Layer 0   <- Output layer
  Layer 1
  ...
  Layer n-1
  Layer n   <- Input layer

定义如下符号：

• 第 $i$ 层的门（gates）索引集合：$G_i = {0,1}^{s_i}$；
• 每个门 $p \in Gi$ 的输出由第 $i+1$ 层的两个门 $u,v \in G{i+1}$ 计算得到；
• 每个门是加法门或乘法门；
• 电路的有向连接关系（wiring pattern）由布尔函数 $\text{add}^{(i)}(p,u,v)$ 与 $\text{mult}^{(i)}(p,u,v)$ 决定：

$$ \text{add}^{(i)}(p,u,v) = \begin{cases} 1, & \text{若 } p = u + v \text{ 且 } p \text{ 为加法门} \ 0, & \text{否则} \end{cases} $$

$$ \text{mult}^{(i)}(p,u,v) = \begin{cases} 1, & \text{若 } p = u \times v \text{ 且 } p \text{ 为乘法门} \ 0, & \text{否则} \end{cases} $$

为了在域 $\mathbb{F}$ 上进行代数化验证，我们将这些布尔函数进行多线性延拓（Multilinear Extension, MLE）：

$$ \widetilde{\text{add}}^{(i)}, \widetilde{\text{mult}}^{(i)}: \mathbb{F}^{si + 2s{i+1}} \to \mathbb{F} $$

它们在 ${0,1}$ 上保持布尔函数的一致性，同时在 $\mathbb{F}$ 上可作为多项式计算。

2. 目标：验证层间一致性（Layer Consistency）

GKR 协议的核心任务是验证每一层的输出是否与下层输入一致。 设 $\widetilde{w}_i: \mathbb{F}^{s_i} \to \mathbb{F}$ 表示第 $i$ 层门输出值的多线性延拓函数，则对于任意 $p \in G_i$，应满足：

$$ \widetilde{w}i(p) = \sum{u,v \in {0,1}^{s{i+1}}} \left[ \widetilde{\text{add}}^{(i)}(p,u,v) \big(\widetilde{w}{i+1}(u) + \widetilde{w}{i+1}(v)\big) + \widetilde{\text{mult}}^{(i)}(p,u,v) \big(\widetilde{w}{i+1}(u) \cdot \widetilde{w}_{i+1}(v)\big) \right] $$ 这表明每个门的输出值等于其输入门的加法或乘法计算结果的组合。

3. 代数化验证目标

Verifier 在协议开始时，从 $\mathbb{F}$ 中选择随机挑战点 $Z \in \mathbb{F}^{s_i}$，并要求 Prover 证明：

$$ \widetilde{w}i(Z) = \sum{u,v \in {0,1}^{s_{i+1}}} g^{(i)}(Z, u, v) $$

其中：

$$ g^{(i)}(Z,u,v) = \widetilde{\text{add}}^{(i)}(Z,u,v) \big(\widetilde{w}{i+1}(u) + \widetilde{w}{i+1}(v)\big) + \widetilde{\text{mult}}^{(i)}(Z,u,v) \big(\widetilde{w}{i+1}(u)\cdot \widetilde{w}{i+1}(v)\big) $$

该恒等式是一个多变量多项式恒等式，其变量集合为 $(u, v) \in \mathbb{F}^{2s_{i+1}}$。\ Prover 与 Verifier 可通过 Multivariate Sumcheck Protocol 来验证此求和是否成立。

4. Sumcheck 协议嵌套结构

4.1 构造 Sumcheck 实例

定义总变量 $X = (u, v) \in \mathbb{F}^{2s_{i+1}}$，我们要验证：

$$ \sum{X \in {0,1}^{2s{i+1}}} g^{(i)}(Z, X) = \widetilde{w}_i(Z) $$

Sumcheck 协议允许 Prover 按变量顺序依次提交多项式 $G_1, G2, \ldots, G{2s_{i+1}}$，每个多项式表示在剩余变量固定时的部分求和。

Verifier 每轮发送随机挑战 $r_j$，更新目标函数的部分求值，直到最后一轮仅剩下对单点 $g^{(i)}(Z, r)$ 的验证。

4.2 递归到下一层验证

在 Sumcheck 结束后，Verifier 得到需要验证的点值：

$$ \widetilde{w}{i+1}(u), \quad \widetilde{w}{i+1}(v) $$

这两个点成为下一层递归验证的输入。 Verifier 再次随机选择挑战点 $Z' \in \mathbb{F}^{s_{i+1}}$，并构造新的等式：

$$ \widetilde{w}{i+1}(Z') =\ \sum{x,y \in {0,1}^{s_{i+2}}} g^{(i+1)}(Z', x, y) $$

重复 Sumcheck 验证过程。

4.3递归终止

当递归到最底层（输入层 $n$）时，$\widetilde{w}_n(x)$ 对应于电路的输入值，这些值是公开的或可直接验证的：

$$ \widetilde{w}_n(x) = \text{Input}(x) $$

Verifier 可直接检查该恒等式是否成立，从而结束整个验证过程。

5. 协议完整形式化描述

输入：

• 电路 $C$ 的布线多项式 $\widetilde{\text{add}}^{(i)}$, $\widetilde{\text{mult}}^{(i)}$；
• 各层输出延拓函数 $\widetilde{w}_i$；
• 公共输入值 $x \in \mathbb{F}^{s_n}$；
• Prover 提供的输出值 $y = \widetilde{w}_0(0)$。

输出：

• Verifier 接受或拒绝 Prover 的声明。

交互流程：

1. Verifier 随机选择 $Z \in \mathbb{F}^{s_0}$；
2. Prover 与 Verifier 运行 Sumcheck 协议验证： $$ \sum_{u,v \in {0,1}^{s_1}} g^{(0)}(Z, u, v) = \widetilde{w}_0(Z) $$
3. 若验证通过，递归到第 1 层；
4. 重复直到输入层；
5. 在输入层，Verifier 直接计算输入一致性。

6. 复杂度与安全性分析

7. 总结与扩展

GKR 协议通过多变量 Sumcheck 递归验证层间一致性，实现了对算术电路的高效代数化验证。其核心特征为：

1. 分层代数化（Layered Algebraization） 将电路的布尔连接关系转化为多线性多项式。
2. Sumcheck 验证（Sumcheck Verification） 以交互方式逐层验证多项式恒等式的正确性。
3. 递归压缩（Recursive Reduction） 每层验证仅依赖于下一层的两个点值，显著降低通信与计算复杂度。
4. 终止条件可验证（Verifiable Base Case） 当递归到输入层时，Verifier 可直接检查输入与声明输出间的一致性。

这种设计使得 GKR 协议成为现代零知识证明体系（如 Spartan、Halo、Nova、Lasso、Sumcheck-based zkVM）中的核心代数基础，被广泛应用于 高效电路验证、可扩展证明系统、以及递归证明构造 等场景。