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$ 的次数大于
    $de{g}_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$ 的次数大于
    $de{g}_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$ 的次数大于
    $de{g}_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}$。

$\mathrm{\forall }x\in \mathbb{F}$

$$x=\sum _{i=1}^k{\alpha }_i\cdot {\beta }_i{\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$