一、Sumcheck
需要计算的结果
H$H=\sum_{b_1\in\{0,1\}}\sum_{b_2\in\{0,1\}}…\sum_{b_v\in\{0,1\}}g(b_1,…,b_v)$
验证者V，证明者P
- V具有多项式时间的计算能力，但是不具备指数级的计算能力，上述H计算需要$2^v$次计算，V无法完成
- 假设P具有无限的计算能力，可以完成上述计算
- V委托P对H进行计算，但V并不信任P，需要P对其计算结果进行证明
Sumcheck协议
一个v轮的验证协议
首先，P向V发送$H$，并声称
$H=\sum_{b_1\in\{0,1\}}\sum_{b_2\in\{0,1\}}…\sum_{b_v\in\{0,1\}}g(b_1,…,b_v)$
在第1轮，P向V发送一个多项式$g_1(X_1)=\sum_{(x_2,…,x_v)\in\{0,1\}^{v-1}}g(X_1,x_2,…,x_v)$
记一个多项式的最高次数为$d$，包括常数项它一共会有$d+1$个系数
- 发送一个多项式的方式可以是
- 发送它的$d+1$个系数
- 发送$d+1$个不同的点值对，V可以通过拉格朗日插值法还原出多项式（一个次数为$d$的抛物线可以由$d+1$个点确定）
- 发送一个多项式的方式可以是
V验证$H=g_1(0)+g_1(1)$，如果不是则拒绝P的证明
- V检验$g_1$的最高次数是否是$g$中$x_1$的最高次数，如果不是则拒绝P的证明
在第$j>1$轮，V向P发送一个随机的值$r_{j-1}$
- P向V发送多项式$g_j(X_j)=\sum_{(x_{j+1},…,x_{v})}g(r_1,…,r_{j-1},X_j,x_{j+1},…,x_v)$
- V验证$g_{j-1}(r_{j-1})=g_j(0)+g_j(1)$,如果不是则拒绝P的证明
- V检验$g_j$的最高次数是否是$g$中$x_j$的最高次数，如果不是则拒绝P的证明
在第v轮之后，V选择一个随机值$r_v$并计算$g(r_1,…,r_v)$
- V验证$g(r_1,…,r_v)=g_v(v_r)$，如果不是则拒绝P的证明
如果V通过上述验证，则接受P的$H$
概率
在第v轮之后验证的$g(r_1,…,r_v)$是真实的可以确定的与V本地已知的$g$相关的结果，在$r_1,…,r_{v-1}$给出的前提下，P要给出一个错误的$g_v$使得$g_v(r_v)=g(r_1,r_2,…,r_v)$,相当于是找到一个多项式与真实的多项式$h_v$(原本的$g$对前$v-1$个变量赋值后)恰好相交于$r_v$，而$h_v$是一个最高次数不超过$d$的多项式，因此不同的$h_v$和$g_v$之间最多有$d$个交点，而$r_v$又是随机选择的，也就是P构造出一个假的多项式使得其在$r_v$上的值正好等于$h_v(r_v)$的概率不超过$\frac{d}{|F|}$，也就是从所有点里正好拿到了那$d$个交点的概率。
如果我们认为P给出的$g_v$是正确的，那么接下来就是要看P给出的$g_{v-1}$和真实的$h_{v-1}$是否一样，同样我们可以证明此时我们接受一个错误的多项式的概率不超过$\frac{d}{|F|}$
一直向上递归，直到确认我们第一轮接受的$g_1$是对的，那么最终计算的$H$就是对的，总的接受错误结果的概率不超过$\frac{d}{|F|}·v$,因为$|F|$是是无限大的，所以这个概率可以忽略
Identity Function
- 我们通常判断两个二值向量$a,b$相同的方式就是，遍历各个位置看是否相同即$a_i=b_i$
- 更通用的表示方法
- $\tilde{\beta}(x,y)=\prod_{i=1}^v((1-x_i)(1-y_i)+x_iy_i)$
- $x_i=y_i=1$，则前面一项为0，后面一项为1,$x_i=y_i=0$，则前面一项为1，后面一项为0，那么$x_i=y_i$时,$(1-x_i)(1-y_i)+x_iy_i=1$
- 当每一对$(x_i,y_i)$都相等时，函数结果为1,反之为0
多线性扩展
当我们有一个输入为二值的函数$V(x_1,x_2,…x_v)$,那么它的多线性扩展$\tilde{V}(x_1,x_2,…,x_v)$可以表示为
这个形式可以用Sumcheck
数组/向量的多线性扩展
- 可以把数组或者向量看成一个函数$a(i)=a_i$，然后把$i$转换为其二进制表示形式，可以用$logN$个0/1来表示那么我们进一步可以将其多线性扩展为
$m\times n$的矩阵可以拉平成一个$mn\times1$的向量，然后表示为上述形式，即
例.矩阵乘法$A=BC$
- 如果要直接验证$A=BC$，则需要先计算$BC$,这需要$O(n^3)$的复杂度
- 可以通过$Ax=B(Cx)$的方式减少复杂度，但是通信过程依旧需要$O(n^2)$的高复杂度
- 交互式证明方法：$f_A(i,j)=\sum_{k\in\{0,1\}^{logN}}f_B(i,k)f_C(k,j)$
- 可以证明