# Sumcheck

- $g(x_1, x_2, \dots, x_v),\ x_i \in \mathbb{F}$
- Prover 需要计算并证明 $g$ 在布尔输入上的值求和的结果是 $H$:
- $H := \sum_{x_1 \in \{0,1\}} \sum_{x_2 \in \{0,1\}}\cdots\sum_{x_v \in \{0, 1\}}g(x_1, x_2, \cdots, x_v)$
- 完全展开后会产生 $2^v$ 个常数项，并求和
- Sumcheck 可以计算任意 $B \subseteq \mathbb{F}$ 时 $\sum_{x_1 \in B} \sum_{x_2 \in B}\cdots\sum_{x_v \in B}g(x_1, x_2, \cdots, x_v)$ 的值，完全展开后会产生 $\left | B \right |^v$ 个常数项。
- 证明者的计算时间 $\mathcal{O}(2^v) + c$，$c$ 是证明过程需要用到的额外步骤，一个常数因子。
- 验证者的计算时间 $\mathcal{O}(v+d)$，$d$ 为 $g$ 在单个输入上的计算成本。

## 协议描述
假设验证者拥有对 $g$ 的 oracle 的访问权限，即获取 $g$ 在随机向量 $(r_1, r_2, \dots, r_v) \in \mathbb{F}^v$ 的取值 $g(r_1, r_2, \dots, r_v)$。

- 协议开始时，$\mathcal{P}$ 发送 $C_1$, 并声称 $C_1 = H$
- round $1$:
- $\mathcal{P}$ 发送一个一元多项式 $g_1(X_1)$, 声称：$$g_1(X_1) = \sum_{(x_2, \dots, x_v) \in \{0,1\}^{v-1}} g(X_1, x_2, \cdots, x_v)$$
- $\mathcal{V}$ 检查 $C_1 \stackrel{?}{=} \sum_{X_1 \in \{0, 1\}}g(X_1) = g_1(0) + g_1(1)$，如果不相等，则拒绝。如果 $g_1$ 的次数大于 $deg_1(g)$，则拒绝。
- $\mathcal{V}$ 选择一个随机数 $r_1 \in \mathbb{F}$，发送给 $\mathcal{P}$
- round $j$ for $1 < j < v$:
- $\mathcal{P}$ 发送一个一元多项式 $g_j(X_j)$，声称：$$g_j(X_j) = \sum_{(x_{j+1}, \dots, x_v) \in \{0, 1\}^{v-j}} g(r_1, \dots, r_{j-1}, X_j, x_{j+1}, \dots, x_v)$$
- $\mathcal{V}$ 检查 $g_{j-1}(r_{j-1}) \stackrel{?}{=}\sum_{X_j \in \{0, 1\}} g_j(X_j) = g_j(0) + g_j(1)$，如果不相等，则拒绝。如果 $g_j$ 的次数大于 $deg_j(g)$，则拒绝。
- $\mathcal{V}$ 选择一个随机数 $r_j \in \mathbb{F}$，发送给 $\mathcal{P}$
- round $v$：
- $\mathcal{P}$ 发送一个一元多项式 $g_v(X_v)$，声称：$$g_v(X_v) = g(r_1, \dots, r_{v-1}, X_v)$$
- $\mathcal{V}$ 检查 $g_{v-1}(r_{v-1}) \stackrel{?}{=}\sum_{X_v \in \{0, 1\}} g_v(X_v) = g_v(0) + g_v(1)$，如果不相等，则拒绝。如果 $g_v$ 的次数大于 $deg_v(g)$，则拒绝。
- $\mathcal{V}$ 选择一个随机数 $r_v \in \mathbb{F}$，并使用 oracle 查询来获取 $g(r_1, r_2, \dots, r_v) \stackrel{?}{=} g_v(r_v)$，如果不相等，则拒绝。
- 如果 $\mathcal{V}$ 在上述操作中仍未拒绝，则 $\mathcal{V}$ 停止并接受。

## 另外一个角度
- $\mathcal{V}$ 直接生成随机挑战 $(r_1, r_2, \dots, r_v)$，让 $\mathcal{P}$ 返回 $s_p = g_p(r_1, \dots, r_v)$，然后和通过 oracle 获取 $s_o = g(r_1, \dots, r_v)$，再验证 $s_p \stackrel{?}{=} s_o$
- 这样只能验证 $\mathcal{P}$ 知道多项式 $g$，不能获取在布尔输入下的结果。

## 再另外一个角度
- $\mathcal{P}$ 声称 $$g_v(X_v) = g(r_1, \dots, r_{v-1}, X_v)$$
- $\mathcal{V}$ 通过随机挑战，选取 $X_v = r_v$，通过 oracle 计算 $g(r_1, \dots, r_{v-1}, r_v)$，验证 $g_v(r_v) = g(r_1, \dots, r_{v-1}, r_v)$，没问题，就是单变量多项式那一套。现在可以信任 $g_v(X_v)$
- $\mathcal{P}$ 声称 $$g_{v-1}(X_{v-1}) = g(r_1, \dots, r_{v-2}, X_{v-1}, 0) + g(r_1, \dots, r_{v-2}, X_{v-1}, 1)$$
- $\mathcal{V}$ 通过随机挑战，选取 $X_{v-1} = r_{v-1}$，验证 $g_{v-1}(r_{v-1}) = g(r_1, \dots, r_{v-1}, 0) + g(r_1, \dots, r_{v-1}, 1) = g_v(0) + g_v(1)$，没问题，就是单变量多项式那一套。现在可以信任 $g_{v-1}(X_{v-1})$
- 然后一路回溯到可以相信 $H$

## 和 Fields of Small Characteristic 的结合

https://people.cs.georgetown.edu/jthaler/small-sumcheck.pdf

> The Sum-Check Protocol over Fields of Small Characteristic

https://zhuanlan.zhihu.com/p/688641141

基于 Sumcheck 的 SNARKs 拥有最快的 prover，其中 prover 的复杂度为 $\mathcal{O}(n)$，其中 $n$ 为被求和项个数，等于 $2^v$。

本文的优化：协议运行在一个很小的 base field 的扩域上。然后让尽量多的 prover 乘法操作在这个 base field 上。代价是更多的 total field 乘法

什么是 total field?

当 sumcheck 应用到多项式乘积时，并且它的 output 是在这个 base field。该算法可以能够将扩域上的操作减少几个数量级。

在一些 SNARK 中， sumcheck 和 多项式承诺相结合，但是多项式承诺发展更快（growing faster），尤其被承诺的值很小的时候。这些优化后的承诺方案让 sum-check prover 成为瓶颈，本文可以缓解该瓶颈。

### 扩域

$\mathbb{B}$ 为基域，$\mathbb{F}$ 为 $\mathbb{B}$ 上的 $k$ 次扩域。$\mathbb{F}$ 中的元素可用向量空间的一组基 $\beta_1, \dots, \beta_k$ 表示。其中 $\beta_i \in \mathbb{B}$。

$\forall x \in \mathbb{F}$
$$x = \sum_{i=1}^k \alpha_i \cdot \beta_i \quad \alpha_i \in \mathbb{B}$$

塔式基

令 $k = 2^z$，其中 $z > 0$ 且 $z \in \mathbb{Z}$。

如果 $\mathbb{F}$ 通过以下步骤从 $\mathbb{B}$ 构造出来，则 $\mathbb{F}$ 称为塔式扩域：
1. 首先构造一个 $\mathbb{B}$ 的 $2$ 次扩域 $\mathbb{B}^\prime$
2. 然后构造 $\mathbb{B}^\prime$ 的 $2$ 次扩域 $\mathbb{B}^{\prime\prime}$
3. 进行 $z$ 次迭代。

Binius[DP23b] 已经使用了 tower basis。并产生好处：
1. 压缩子域元素
2. 子域之间，基域与子域之间的快速乘法

成本：

- $bb$：指两个基域元素相乘的成本
- $be$: 指基域元素与扩域元素相乘的成本，大约为 $k \cdot bb$, $k$ 为扩张次数
- $ee$：指两个扩域元素相乘的成本，由前面讨论的 Karatsuba 算法可得，若 $k$ 是 $2$ 的幂，则 $ee \approx k^{1.58496} \cdot bb$