# Sumcheck（求和检验）协议：基础

> 适用对象：已学习有限域、基础多项式、概率论与复杂性基础（可选：交互式证明/PCP/IOP 基础）
>
> 本讲目标：掌握标准 Sumcheck 协议、完备性与健全性证明框架，并理解其在现代证明系统（如 GKR、SNARK/IOP）中的接口方式。

---

## 目录

1. [学习目标与背景](#学习目标与背景)
2. [问题定义：要验证什么？](#问题定义：要验证什么？)
3. [直觉：逐维“折叠”指数求和](#直觉：逐维“折叠”指数求和)
4. [标准 Sumcheck 协议（形式化流程）](#标准Sumcheck协议形式化流程)
5. [正确性：完备性与健全性（核心证明）](#正确性完备性与健全性核心证明)
6. [例子：2 变量多线性多项式跑一遍协议](#例子2-变量多线性多项式跑一遍协议)
7. [为何多线性扩展（MLE）几乎总出现？](#为何多线性扩展mle几乎总出现)
8. [与多项式承诺/IOP 的接口](#与多项式承诺iop-的接口)
9. [常见变体与工程技巧](#常见变体与工程技巧)
10. [复杂度与参数选择](#复杂度与参数选择)
11. [课后练习与思考题](#课后练习与思考题)
12. [一页速记（Cheat Sheet）](#一页速记cheat-sheet)

---

## 学习目标与背景

### 为什么要学 Sumcheck？

Sumcheck（求和检验）是交互式证明（IP）与 IOP/SNARK 体系中的**核心子协议**，用于验证如下类型的声明：

$$S \stackrel{?}{=} \sum_{x\in\{0,1\}^n} g(x).$$

它的重要性体现在：

- 将对 $2^n$ 个点的求和验证，压缩成 **$n$ 轮交互**；
- 通信量与多项式次数线性相关，常见情形（多线性）每轮只需常数个域元素；
- 可作为“胶水协议”把复杂全局约束归约为少量随机点的多项式求值一致性。

### 本讲你应当掌握

- 能写出标准 Sumcheck 协议并解释每一步含义；
- 能用“逐轮归纳 + 一元多项式根数界”给出健全性证明；
- 了解多线性扩展（MLE）为何使协议更干净（$d=1$）；
- 了解它与多项式承诺/低度测试组合后的用法。

---

## 问题定义：要验证什么？

### 输入

- 有限域 $\mathbb{F}$（通常取大素域或扩域）；
- 多项式 $g(X_1,\dots,X_n)\in\mathbb{F}[X_1,\dots,X_n]$；
- 声称的求和值 $S\in\mathbb{F}$。

### 目标声明

验证者希望验证：

$$S = \sum_{x\in\{0,1\}^n} g(x).$$

### 关键假设：度数上界

Sumcheck 的健全性依赖一个低度假设。常见的度界形式：

- **按变量度界**：对每个 $i$，$\deg_{X_i}(g)\le d$。

在现代证明系统中，$g$ 常常是**多线性**（每变量度 $\le 1$），此时 $d=1$。

---

## 直觉：逐维“折叠”指数求和

将声明写成嵌套求和：

$$S = \sum_{x_1\in\{0,1\}} \sum_{x_2\in\{0,1\}} \cdots \sum_{x_n\in\{0,1\}} g(x_1,\dots,x_n).$$

先把最外层提出：

$$S = \sum_{x_1\in\{0,1\}} G_1(x_1),\quad \text{其中 }G_1(X_1)=\sum_{x_2,\dots,x_n\in\{0,1\}} g(X_1,x_2,\dots,x_n).$$

注意：$G_1$ 是一元多项式，次数 $\le d$。如果证明者给出 $G_1$，验证者可检查：

1. **边界一致性**：$G_1(0)+G_1(1)=S$；
2. 随机抽取 $r_1\in\mathbb{F}$，把问题降维为验证

$$G_1(r_1) \stackrel{?}{=} \sum_{x_2,\dots,x_n\in\{0,1\}} g(r_1,x_2,\dots,x_n).$$

这将 $n$ 维求和归约为 $n-1$ 维求和。重复 $n$ 次即可。

---

## 标准 Sumcheck 协议（形式化流程）

### 记号

- 初始声明值：$S_0 := S$
- 验证者随机挑战：$r_1,\dots,r_n \in \mathbb{F}$
- 第 $i$ 轮证明者发送的一元多项式：$p_i(X)$
- 更新：$S_i := p_i(r_i)$

### 协议

令 $S_0=S$。对 $i=1,2,\dots,n$：

1. **Prover → Verifier：** 发送一元多项式 $p_i(X)$，并声称：

$$p_i(X) \stackrel{claim}{=} \sum_{x_{i+1},\dots,x_n\in\{0,1\}} g(r_1,\dots,r_{i-1},X,x_{i+1},\dots,x_n).$$

2. **Verifier 检查：**

$$p_i(0)+p_i(1) \stackrel{?}{=} S_{i-1}.$$

若不等则拒绝。

3. **Verifier → Prover：** 采样随机 $r_i\xleftarrow{\$}\mathbb{F}$ 并发送。

4. **更新：** $S_i := p_i(r_i)$。

最后，验证者检查：

$$S_n \stackrel{?}{=} g(r_1,\dots,r_n).$$

> **备注**：在很多应用中，验证者无法直接计算 $g(r)$。这时需要多项式承诺/IOP 来提供 $g(r)$ 的可信求值（见后文）。

---

## 正确性：完备性与健全性（核心证明）

### 完备性（Completeness）

若证明者诚实发送真实的部分求和多项式，则第 $i$ 轮：

$$S_{i-1} = \sum_{x_i\in\{0,1\}} \sum_{x_{i+1..n}\in\{0,1\}} g(r_{<i},x_i,x_{>i})
= p_i(0)+p_i(1).$$

且更新 $S_i=p_i(r_i)$ 保持与真实降维目标一致，最终 $S_n=g(r_1,\dots,r_n)$ 成立。因此诚实证明者总能被接受。

### 可靠性（Soundness）——核心直觉

若声明为假：

$$S \ne \sum_{x\in\{0,1\}^n} g(x),$$

任何作弊证明者想通过，必须在某一轮伪造 $p_i$。验证者每轮随机选择 $r_i$，迫使 $p_i$ 在随机点上与真实多项式一致。由于都是低度一元多项式，伪造在随机点“碰巧”一致的概率很小。

#### 一元多项式根数界

若 $q(X)$ 是非零一元多项式且 $\deg(q)\le d$，则它在 $\mathbb{F}$ 上最多有 $d$ 个根。

#### 逐轮归纳的健全性界（常用版本）

设 $\deg_{X_i}(g)\le d$ 对所有 $i$。则对任意证明者，在声明错误时通过协议的概率：

$$\Pr[\text{Verifier accepts}] \le \frac{n\cdot d}{|\mathbb{F}|}.$$

**证明框架：**

- 定义真实的第 $i$ 轮多项式：

$$G_i(X) := \sum_{x_{i+1..n}\in\{0,1\}} g(r_1,\dots,r_{i-1},X,x_{i+1},\dots,x_n).$$

- 若作弊发送 $p_i\neq G_i$，令差多项式 $\Delta_i(X)=p_i(X)-G_i(X)$，则 $\Delta_i$ 是次数 $\le d$ 的非零一元多项式。
- 想继续欺骗，必须满足 $p_i(r_i)=G_i(r_i)$，即 $\Delta_i(r_i)=0$。随机 $r_i$ 落在根上的概率 $\le d/|\mathbb{F}|$。
- 用并集界/逐轮归纳汇总得到 $\le nd/|\mathbb{F}|$。

我们可以展开证明过程：
- 每一步成功猜中多项式随机点的概率 $\le d/|\mathbb{F}|$，如果没有猜中，攻击者仍然可以构造多项式，满足中间的检查。
- 考虑攻击轮次， 攻击者在第 $i$ 轮攻击成功（猜中多项式随机交叉点）的概率是 $\le (1-d/|\mathbb{F}|)^{i-1}d/|\mathbb{F}|$。
- 因此攻击者总的攻击成功的概率可以用并集界/逐轮归纳汇总得到 $\le nd/|\mathbb{F}|$。

> **参数含义**：域越大、次数越低，作弊成功概率越小。多线性情形 $d=1$ 通常非常理想。

---

## 例子：2 变量多线性多项式跑一遍协议

取 $n=2$，$g(x_1,x_2)=3x_1x_2+2x_1+5$。验证：

$$S \stackrel{?}{=} \sum_{(x_1,x_2)\in\{0,1\}^2} g(x_1,x_2).$$

### 真实求和值（可课堂练习）

- $g(0,0)=5$
- $g(0,1)=5$
- $g(1,0)=7$
- $g(1,1)=10$

总和 $S=27$。

#### 尝试攻击（可以作为反例来演示为什么攻击会失败）

恶意证明者伪造 $S' = 25$。

### 第 1 轮

$$p_1(X_1)=\sum_{x_2\in\{0,1\}} g(X_1,x_2).$$

计算：

- $g(X_1,0)=2X_1+5$
- $g(X_1,1)=3X_1+2X_1+5=5X_1+5$

相加：$p_1(X_1)=7X_1+10$。

Verifier 检查：$p_1(0)+p_1(1)=10+(17)=27$ 通过。
抽样 $r_1$，更新：$S_1=p_1(r_1)=7r_1+10$。
$r_1 = 3$, $S_1=p_1(r_1)=7r_1+10 = 7*3+10 = 31$。

#### 尝试攻击
恶意证明者伪造 $p_1(X_1) = 7X_1 + 9$，通过第1轮中的 Verifier 检查：$p_1(0)+p_1(1)=9+(16)=25$。

此时 Verifier 计算的 $S_1 = 7r_1+9=30$。

### 第 2 轮

$$p_2(X_2)=g(r_1,X_2)=3r_1X_2+2r_1+5.$$

$$p_2(X_2)=g(r_1,X_2)=3r_1X_2+2r_1+5 = 9X_2 + 11.$$

Verifier 检查：

$$p_2(0)+p_2(1)=(2r_1+5)+(3r_1+2r_1+5)=7r_1+10=S_1.$$

$$p_2(0)+p_2(1)=(2r_1+5)+(3r_1+2r_1+5)=7r_1+10=31.$$

抽样 $r_2$，更新：$S_2=p_2(r_2)=g(r_1,r_2)$。

最终检查自然通过：

$$r_2 = 7, g(r_1,r_2)= 3*3*7 + 2*3 +5 = 74$$

$$p_2(r_2) = p_2(7) = 9*7 + 11 = 74$$

#### 尝试攻击
为了使得 $p_2(0)+p_2(1)= 30 $, 恶意证明者伪造 $$p_2(X_2) = 10X_2 + 10$$

此时，Verifier 计算 $$p_2(r_2) = 10*7+10=80 $$

但是，Verifier 计算出的原始多项式在 $(r_1, r_2)$ 处的取值是
$$g(r_1,r_2)= 3*3*7 + 2*3 +5 = 74$$

明显与恶意证明者提供的多项式的计算结果不符合，所以 Verifier 拒绝证明者的伪造，攻击失败。

---

## 为何多线性扩展（MLE）几乎总出现？

很多时候我们从布尔超立方体上的函数出发：

$$f:\{0,1\}^n\to\mathbb{F}.$$

为了用 Sumcheck，我们希望有一个多项式 $\tilde f$ 满足：

- $\tilde f(x)=f(x)$ 对所有 $x\in\{0,1\}^n$；
- $\deg_{X_i}(\tilde f)\le 1$（多线性），使得 $d=1$。

**多线性扩展**保证上述两点并且是唯一的：任意布尔函数都存在唯一的多线性多项式与其在布尔点上一致。

> 直觉：布尔点上做拉格朗日插值，但限制每变量次数 $\le 1$，得到唯一扩展。

---

## 与多项式承诺/IOP 的接口

标准 Sumcheck 的最后一步需要验证者得到 $g(r_1,\dots,r_n)$ 的可信值。但在许多应用中：

- $g$ 是由证明者持有的大表（例如电路每层的值），验证者无法直接计算；
- 或 $g$ 很大，计算代价过高。

典型解决办法：

1. **多项式承诺（PC）**：证明者先对 $g$（或相关多项式）做承诺；最后提供对点 $r$ 的开证明，验证 $g(r)$ 与承诺一致。
2. **IOP/PCP**：将 $g$ 作为 oracle，并用低度测试保证其确为低度多项式；Sumcheck 的终检点查询结合 oracle 访问完成。

因此 Sumcheck 常被视为一个**中间层**：把“指数规模求和”归约为“少量随机点求值一致性”。

---

## 常见变体与工程技巧

### 1) 批量（Batched）Sumcheck

要同时验证多个求和：$S^{(j)}=\sum_x g_j(x)$。可用随机线性组合压缩：

$$\sum_j \alpha_j S^{(j)} \stackrel{?}{=} \sum_x \left(\sum_j \alpha_j g_j(x)\right),$$

只跑一次 sumcheck，通信与轮数不变。

### 2) 低通信实现：只发系数

每轮发送一元多项式 $p_i$ 的系数即可：次数 $\le d$ 需 $d+1$ 个域元素。多线性（$d=1$）时每轮只需 2 个域元素。

### 3) 非交互化：Fiat–Shamir（ROM）

将每轮随机挑战 $r_i$ 用哈希生成：

$$r_i := H(\text{transcript up to round }i).$$

这在 SNARK/IOP 中非常常见，但要注意：

- hash-to-field 方式；
- transcript 绑定与域分离（domain separation）；
- 与多项式承诺的组合顺序。

---

## 复杂度与参数选择

### 轮数

- 轮数固定为 $n$（变量数）。

### 通信量

- 每轮发送一个次数 $\le d$ 的一元多项式：$d+1$ 个域元素；
- 总通信 $\approx n(d+1)$ 个域元素（不含最终开证明/承诺等）。

### 验证开销

- 每轮做常数次多项式求值（对 0、1 与随机点），加一次随机采样；
- 终检需要得到 $g(r)$（直接算或由承诺/IOP 提供）。

### 健全性误差

- $\le nd/|\mathbb{F}|$。

> 使用中上选取 64-bit 或 128-bit 大域，使误差可忽略。

---

## 练习与思考题

1. **手算 3 变量**：给一个 3 变量多线性 $g$，写出每轮 $p_i$ 并验证一致性条件。
2. **误差估算**：若 $|\mathbb{F}|=2^{64}$、$n=30$、$d=2$，给出最大作弊成功概率上界。
3. **度界讨论**：比较“按变量度界”和“总度界”的差异，为何分析更常用前者？
4. **接口题**：若验证者无法计算 $g(r)$，描述用多项式承诺完成终检的一般流程。
5. **FS 直觉**：在随机预言机模型下，用哈希生成挑战为何合理？它替代了什么假设？

---

## 一页速记（Cheat Sheet）

- **目标**：验证 $S=\sum_{x\in\{0,1\}^n} g(x)$
- **第 i 轮**：Prover 发 $p_i(X)\approx\sum_{x_{i+1..n}} g(r_{<i},X,x_{>i})$
- **检查**：$p_i(0)+p_i(1)=S_{i-1}$
- **挑战**：随机 $r_i\in\mathbb{F}$，更新 $S_i=p_i(r_i)$
- **终检**：$S_n=g(r_1,\dots,r_n)$
- **健全性误差**：$\le nd/|\mathbb{F}|$；多线性时 $d=1$

---