Skip to article frontmatterSkip to article content

Basefold 优化

Yu Guo [email protected]

最后更新时间：2025-06-10

协议回顾

对于任意一个 nn 个变量（Indeterminate）的 Multilinear Polynomial f~(X0,X1,…,Xn−1)∈F≤1[X0,X1,…,Xn−1]\tilde{f}(X_0, X_1,\ldots, X_{n-1})\in F^{\leq 1}[X_0, X_1,\ldots, X_{n-1}]，如果要证明其在一个任意点 u⃗=(u0,u1,…,un−1)\vec{u}=(u_0, u_1, \ldots, u_{n-1}) 的运算值是正确的，Basefold 协议 [ZCF23] 提供了一个简洁优雅的方案。其核心思路是用 Sumcheck 协议来证明 f~(u0,u1,…,un−1)\tilde{f}(u_0, u_1, \ldots, u_{n-1}) ，然后在 Sumcheck 协议的最后一步，Verifier 需要验证 f~(r0,r1,…,rn−1)\tilde{f}(r_0, r_1, \ldots, r_{n-1}) 的运算值， Basefold 并没有借助于另一个 MLE PCS 来完成这最后一步的证明，而是借助一个 FRI 协议来辅助完成。本来 FRI 协议的证明目的是证明一个 Codeword 的 Proximity，即与正确的码字的距离不超过一个安全参数 δ，然而在 FRI 协议的最后一步，Prover 会发送一个折叠后的 Codeword 对应的 Message，如果折叠充分，那么最后的 Message 是一个常数（多项式），如果 Prover 诚实，那么这个值恰好等于 f~(r0,r1,…,rn−1)\tilde{f}(r_0, r_1, \ldots, r_{n-1}) 的值，恰好与 Sumcheck 形成互补的情况。

下面我们过一下协议细节，首先 f~(X⃗)\tilde{f}(\vec{X}) 可以重写成下面的等式：

f~(X⃗)=∑b⃗∈{0,1}nf~(b⃗)⋅eq(X⃗,b⃗)\tilde{f}(\vec{X}) = \sum_{\vec{b}\in\{0,1\}^n} \tilde{f}(\vec{b}) \cdot eq(\vec{X}, \vec{b})
(1)

可以看出等式右边是一个求和式，这满足 Sumcheck 协议的要求。Sumcheck 协议可以证明下面的内积等式：

v=∑b⃗∈{0,1}nf~(b⃗)⋅g~(b⃗)v = \sum_{\vec{b}\in\{0,1\}^n} \tilde{f}(\vec{b}) \cdot \tilde{g}(\vec{b})
(2)

基于 Sumcheck 协议的内积证明

我们回顾一下如何利用 Sumcheck 协议证明内积，我们假设两个长度为 2n2^n 的向量 f⃗\vec{f} 与 g⃗\vec{g} 分别对应两个 n 个变量的 Multilinear Polynomial，f~\tilde{f} 与 g~\tilde{g}，那么接下来我们解释 Prover 和 Verifier 如何证明下面的目标：

s=∑b⃗∈{0,1}nf~(b0,b1,…,bn−1)⋅g~(b0,b1,…,bn−1)s = \sum_{\vec{b}\in\{0,1\}^n} \tilde{f}(b_0, b_1, \ldots, b_{n-1}) \cdot \tilde{g}(b_0, b_1, \ldots, b_{n-1})
(3)

第一轮：Prover 构造一个 Degree 为 2 的一元多项式 h(0)(X)h^{(0)}(X)，发送它在 X=0,1,2X=0,1,2 这三个点上的求值，即 (h(0)(0),h(0)(1),h(0)(2))(h^{(0)}(0), h^{(0)}(1), h^{(0)}(2))。

h(0)(X)=∑b⃗∈{0,1}n−1f~(X,b1,b2,…,bn−1)⋅g~(X,b1,b2,…,bn−1)h^{(0)}(X) = \sum_{\vec{b}\in\{0,1\}^{n-1}} \tilde{f}(X, b_1, b_2, \ldots, b_{n-1}) \cdot \tilde{g}(X, b_1, b_2, \ldots, b_{n-1})
(4)

Verifier 检查 h(0)(0)+h(0)(1)=?vh^{(0)}(0)+h^{(0)}(1)\overset{?}{=}v，如果成立，则回应一个随机挑战数 r0∈Fqr_0\in\mathbb{F}_q，然后证明目标就被转换成了一个新的证明目标：

h(0)(r0)=∑b⃗∈{0,1}n−1f~(r0,b1,b2,…,bn−1)⋅g~(r0,b1,b2,…,bn−1)h^{(0)}(r_0) = \sum_{\vec{b}\in\{0,1\}^{n-1}} \tilde{f}(r_0, b_1, b_2, \ldots, b_{n-1}) \cdot \tilde{g}(r_0, b_1, b_2, \ldots, b_{n-1})
(5)

观察到 f~(r0,X1,…,Xn−1)\tilde{f}(r_0, X_1, \ldots, X_{n-1}) 和 g~(r0,X1,…,Xn−1)\tilde{g}(r_0, X_1, \ldots, X_{n-1}) 仍然是 Multilinear Polynomial，我们将其分别记为 f~(1)(X1,…,Xn−1)\tilde{f}^{(1)}(X_1, \ldots, X_{n-1}) 与 g~(1)(X1,…,Xn−1)\tilde{g}^{(1)}(X_1, \ldots, X_{n-1})，

f~(1)(X1,…,Xn−1)=f~(r0,X1,…,Xn−1)g~(1)(X1,…,Xn−1)=g~(r0,X1,…,Xn−1)\begin{aligned} \tilde{f}^{(1)}(X_1, \ldots, X_{n-1}) &= \tilde{f}(r_0, X_1, \ldots, X_{n-1}) \\ \tilde{g}^{(1)}(X_1, \ldots, X_{n-1}) &= \tilde{g}(r_0, X_1, \ldots, X_{n-1}) \end{aligned}
(6)

于是新的证明目标可以写为：

h(0)(r0)=v(1)=?∑b⃗∈{0,1}n−1f~(1)(b1,…,bn−1)⋅g~(1)(b1,…,bn−1)h^{(0)}(r_0) = v^{(1)} \overset{?}{=} \sum_{\vec{b}\in\{0,1\}^{n-1}} \tilde{f}^{(1)}(b_1, \ldots, b_{n-1}) \cdot \tilde{g}^{(1)}(b_1, \ldots, b_{n-1})
(7)

这样 Sumcheck 可以看成一个递归调用的协议，每次调用就会讲求和的长度减半。 接着 Prover 和 Verifier 重复上述过程，直到 Sumcheck 的证明长度变成 1 为止。

第 nn 轮，Prover 构造 h(n−1)(X)h^{(n-1)}(X)，发送 (h(n−1)(0),h(n−1)(1),h(n−1)(2))(h^{(n-1)}(0), h^{(n-1)}(1), h^{(n-1)}(2)) 三个点，

h(n−1)(X)=f~(n−1)(X)⋅g~(n−1)(X)h^{(n-1)}(X) = \tilde{f}^{(n-1)}(X) \cdot \tilde{g}^{(n-1)}(X)
(8)

Verifier 检查 h(n−1)(0)+h(n−1)(1)=?v(n−1)h^{(n-1)}(0)+h^{(n-1)}(1)\overset{?}{=}v^{(n-1)}，如果成立，则回应一个随机挑战数 rn−1∈Fqr_{n-1}\in\mathbb{F}_q，然后证明目标就被转换成了一个新的证明目标：

h(n−1)(rn−1)=?f~(n−1)(rn−1)⋅g~(n−1)(rn−1)h^{(n-1)}(r_{n-1}) \overset{?}{=} \tilde{f}^{(n-1)}(r_{n-1}) \cdot \tilde{g}^{(n-1)}(r_{n-1})
(9)

然后 Prover 无需再发送任何消息，Verifier 直接计算 h(n−1)(rn−1)h^{(n-1)}(r_{n-1}) 的值，然后调用 f~(X0,X1,…,Xn−1)\tilde{f}(X_0, X_1, \ldots, X_{n-1}) 与 g~(X0,X1,…,Xn−1)\tilde{g}(X_0, X_1, \ldots, X_{n-1}) 的 Oracle，得到 f~(n−1)(rn−1)\tilde{f}^{(n-1)}(r_{n-1}) 与 g~(n−1)(rn−1)\tilde{g}^{(n-1)}(r_{n-1}) 的值，然后验证等式是否成立：

f(n−1)(rn−1)=f~(r0,r1,…,rn−1)g(n−1)(rn−1)=g~(r0,r1,…,rn−1)\begin{aligned} f^{(n-1)}(r_{n-1}) &= \tilde{f}(r_0, r_1, \ldots, r_{n-1}) \\ g^{(n-1)}(r_{n-1}) &= \tilde{g}(r_0, r_1, \ldots, r_{n-1}) \\ \end{aligned}
(10)

通常来说，在 Sumcheck 最后一步，Verifier 所依赖的 f~\tilde{f} 与 g~\tilde{g} 的 Oracle 采用 Polynomial Commitment 来实现。即在 Sumcheck 开始之前，Prover 先发送它们的 Commitment，然后在 Sumcheck 的最后一步，由 Prover 来发送 f~(r0,r1,…,rn−1)\tilde{f}(r_0, r_1, \ldots, r_{n-1}) 与 g~(r0,r1,…,rn−1)\tilde{g}(r_0, r_1, \ldots, r_{n-1}) 的值，并附上相应的 Multilinear Polynomial Evaluation 的证明。

基于 FRI 协议的 Proximity 证明

TODO

基于 Multilinear Basis 的 Basefold 证明过程

我们采用实现的视角过一遍 Prover 的证明过程。为了方便读者理解，我们假设 f~\tilde{f} 是一个三变量的 Multilinear Polynomial，协议总共有 n=3n=3 轮，那么 Prover 先做一轮的 Sumcheck，然后复用 Sumcheck 的随机数，再做一轮 FRI 协议，这等于完成了一轮的 Basefold 协议；然后依次做下去，直到 Sumcheck 的证明长度变成 1 为止。

v=∑(b0,b1,b2)∈{0,1}3f~(b0,b1,b2)⋅eq((u0,u1,u2),(b0,b1,b2))=∑i=07ai⋅wi\begin{aligned} v &= \sum_{(b_0,b_1,b_2)\in\{0,1\}^3} \tilde{f}(b_0, b_1, b_2) \cdot eq((u_0, u_1, u_2), (b_0, b_1, b_2)) \\ &= \sum_{i=0}^{7} a_i\cdot w_i \end{aligned}
(11)

这里 v=f~(u0,u1,u2)v= \tilde{f}(u_0, u_1, u_2)，向量 a⃗=(a0,a1,⋯ ,a7)\vec{a}=(a_0, a_1, \cdots, a_{7}) 是 f~(X⃗)\tilde{f}(\vec{X}) 在 Boolean Hypercube 上的运算值，而 w⃗=(w0,w1,⋯ ,w7)\vec{w}=(w_0, w_1, \cdots, w_{7}) 是 eq(u⃗,X⃗)eq(\vec{u}, \vec{X}) 在 Boolean Hypercube 上取值：

w0=(1−u0)(1−u1)(1−u2)w1=u0(1−u1)(1−u2)w2=(1−u0)u1(1−u2)w3=u0u1(1−u2)w4=(1−u0)(1−u1)u2w5=u0(1−u1)u2w6=(1−u0)u1u2w7=u0u1u2\begin{aligned} w_0 &= (1-u_0)(1-u_1)(1-u_2) \\ w_1 &= u_0(1-u_1)(1-u_2) \\ w_2 &= (1-u_0)u_1(1-u_2) \\ w_3 &= u_0u_1(1-u_2) \\ w_4 &= (1-u_0)(1-u_1)u_2 \\ w_5 &= u_0(1-u_1)u_2 \\ w_6 &= (1-u_0)u_1u_2 \\ w_7 &= u_0u_1u_2 \\ \end{aligned}
(12)

Prover 需要证明这个内积计算的正确性。即

v=a0w0+a1w1+a2w2+a3w3+a4w4+a5w5+a6w6+a7w7v = a_0w_0 + a_1w_1 + a_2w_2 + a_3w_3 + a_4w_4 + a_5w_5 + a_6w_6 + a_7w_7
(13)

Prover 维护长度为 2n2^n 的两个数组，分别保存 a⃗\vec{a} 和 w⃗\vec{w}，分别对应 f~\tilde{f} 和 eqeq 的 Evaluations 表示。

ai=f~(i0,i1,i2)wi=eq((u0,u1,u2),(i0,i1,i2))\begin{aligned} a_i &= \tilde{f}(i_0, i_1, i_2) \\ w_i &= eq((u_0, u_1, u_2), (i_0, i_1, i_2)) \end{aligned}
(14)

第一轮的 Sumcheck 协议，Prover 计算 h(0)(X)h^{(0)}(X)。这是一个 Degree 为 2 的一元多项式，我们只要得到它在至少三个不同点上的求值，就可以唯一表示这个多项式，为了优化计算，我们特意选择 X=0,1,2X=0,1,2 这三个点。

h(0)(X)=∑b1,b2∈{0,1}2f~(X,b1,b2)⋅g~(X,b1,b2)h^{(0)}(X) = \sum_{b_1,b_2\in\{0,1\}^{2}} \tilde{f}(X, b_1, b_2) \cdot \tilde{g}(X, b_1, b_2)
(15)

而 h(0)(0)h^{(0)}(0) 恰好等于内积求和项中的位于偶数位置的项的和，而 h(0)(1)h^{(0)}(1) 恰好等于内积求和项中的位于奇数位置的项的和，表示如下：

h(0)(0)=a0w0+a2w2+a4w4+a6w6h(0)(1)=a1w1+a3w3+a5w5+a7w7\begin{aligned} h^{(0)}(0) &= a_0w_0 + a_2w_2 + a_4w_4 + a_6w_6 \\ h^{(0)}(1) &= a_1w_1 + a_3w_3 + a_5w_5 + a_7w_7 \\ \end{aligned}
(16)

因此 Prover 只需两遍 2n−12^{n-1} 次乘法与 2n−12^{n-1} 次加法（总计 2n2^n 次乘法与 2n2^{n} 次加法）就能计算出 h(0)(0)h^{(0)}(0) 和 h(0)(1)h^{(0)}(1)。但如何计算 h(0)(2)h^{(0)}(2) 呢？我们先证明下面的等式，这个等式我们反复要用到：

f~(X0+1,X1,X2)=f~(X0,X1,X2)+f~(1,X1,X2)−f~(0,X1,X2)\tilde{f}(X_0+1, X_1, X_2) = \tilde{f}(X_0, X_1, X_2) + \tilde{f}(1, X_1, X_2) - \tilde{f}(0, X_1, X_2)
(17)

推而广之，我们可以得到下面的式子

f~(Y⃗,Xk+1,Z⃗)=f~(Y⃗,Xk,Z⃗)+f~(Y⃗,1,Z⃗)−f~(Y⃗,0,Z⃗)\tilde{f}(\vec{Y}, X_k+1, \vec{Z}) = \tilde{f}(\vec{Y}, X_k, \vec{Z}) + \tilde{f}(\vec{Y}, 1, \vec{Z}) - \tilde{f}(\vec{Y}, 0, \vec{Z})
(18)

那么根据 Multilinear Polynomial 的性质，我们可以计算出 h(0)(2)h^{(0)}(2) 的值：

h(0)(2)=∑b1,b2∈{0,1}2f~(2,b1,b2)⋅w~(2,b1,b2)=∑b1,b2∈{0,1}2(2⋅f~(1,b1,b2)−f~(0,b1,b2))⋅(2⋅w~(1,b1,b2)−w~(0,b1,b2))\begin{aligned} h^{(0)}(2) &= \sum_{b_1,b_2\in\{0,1\}^{2}} \tilde{f}(2, b_1, b_2) \cdot \tilde{w}(2, b_1, b_2) \\ &= \sum_{b_1,b_2\in\{0,1\}^{2}} \Big( 2\cdot\tilde{f}(1, b_1, b_2) - \tilde{f}(0, b_1, b_2) \Big)\cdot \Big( 2\cdot\tilde{w}(1, b_1, b_2) - \tilde{w}(0, b_1, b_2) \Big) \end{aligned}
(19)

这需要 Prover 计算 2n−12^{n-1} 次乘法 与 5⋅2n−15\cdot 2^{n-1} 次加法。然后 Prover 发送 h(0)(0),h(0)(1),h(0)(2)h^{(0)}(0), h^{(0)}(1), h^{(0)}(2) 给 Verifier，Verifier 检查下面的等式是否成立：

h(0)(0)+h(0)(1)=?vh^{(0)}(0)+h^{(0)}(1) \overset{?}{=} v
(20)

如果成立，则回复一个随机数 r0∈Fqr_0\in\mathbb{F}_q，然后证明目标就 Reduce 成了一个新的证明目标：

h(0)(r0)=∑b1,b2∈{0,1}2f~(r0,b1,b2)⋅w~(r0,b1,b2)=∑b1,b2∈{0,1}2f~(1)(b1,b2)⋅w~(1)(b1,b2)\begin{aligned} h^{(0)}(r_0) &= \sum_{b_1,b_2\in\{0,1\}^{2}} \tilde{f}(r_0, b_1, b_2) \cdot \tilde{w}(r_0, b_1, b_2) \\ & = \sum_{b_1,b_2\in\{0,1\}^{2}} \tilde{f}^{(1)}(b_1,b_2) \cdot \tilde{w}^{(1)}(b_1,b_2) \end{aligned}
(21)

这里 f(1)(X1,X2)f^{(1)}(X_1, X_2) 和 w(1)(X1,X2)w^{(1)}(X_1, X_2) 在二维 Boolean Hypercube 上的 Evaluations 实际上直接可以通过 f~\tilde{f} 和 w~\tilde{w} 的 Evaluations 计算得到：

a0(1)=f~(1)(0,0)=(1−r0)⋅f~(0,0,0)+r0⋅f~(1,0,0)a1(1)=f~(1)(0,1)=(1−r0)⋅f~(0,0,1)+r0⋅f~(1,0,1)a2(1)=f~(1)(1,0)=(1−r0)⋅f~(0,1,0)+r0⋅f~(1,1,0)a3(1)=f~(1)(1,1)=(1−r0)⋅f~(0,1,1)+r0⋅f~(1,1,1)\begin{aligned} a^{(1)}_0 &= \tilde{f}^{(1)}(0, 0) = (1-r_0)\cdot\tilde{f}(0, 0, 0) + r_0\cdot\tilde{f}(1, 0, 0) \\ a^{(1)}_1 &= \tilde{f}^{(1)}(0, 1) = (1-r_0)\cdot\tilde{f}(0, 0, 1) + r_0\cdot\tilde{f}(1, 0, 1) \\ a^{(1)}_2 &= \tilde{f}^{(1)}(1, 0) = (1-r_0)\cdot\tilde{f}(0, 1, 0) + r_0\cdot\tilde{f}(1, 1, 0) \\ a^{(1)}_3 &= \tilde{f}^{(1)}(1, 1) = (1-r_0)\cdot\tilde{f}(0, 1, 1) + r_0\cdot\tilde{f}(1, 1, 1) \\ \end{aligned}
(22)

所以这需要 Prover 计算 2n−12^{n-1} 次乘法与 2n2^n 次加法从而得到 f(1)(X1,X2)f^{(1)}(X_1, X_2) 的 Evaluations 表示，记在 (a0(1),a1(1),a2(1),a3(1))(a^{(1)}_0, a^{(1)}_1, a^{(1)}_2, a^{(1)}_3) 中

a0(1)=(1−r0)⋅a0+r0⋅a1a1(1)=(1−r0)⋅a2+r0⋅a3a2(1)=(1−r0)⋅a4+r0⋅a5a3(1)=(1−r0)⋅a6+r0⋅a7\begin{aligned} a^{(1)}_0 &= (1-r_0)\cdot a_0 + r_0\cdot a_1 \\ a^{(1)}_1 &= (1-r_0)\cdot a_2 + r_0\cdot a_3 \\ a^{(1)}_2 &= (1-r_0)\cdot a_4 + r_0\cdot a_5 \\ a^{(1)}_3 &= (1-r_0)\cdot a_6 + r_0\cdot a_7 \\ \end{aligned}
(23)

除此之外，Prover 还需要以同样的方式（2n−12^{n-1} 次乘法与 2n2^n 次加法）计算 w~(1)(X1,X2)\tilde{w}^{(1)}(X_1,X_2) 的 Evaluations 表示：

w0(1)=w~(1)(0,0)=(1−r0)⋅w~(0,0,0)+r0⋅w~(1,0,0)w1(1)=w~(1)(0,1)=(1−r0)⋅w~(0,0,1)+r0⋅w~(1,0,1)w2(1)=w~(1)(1,0)=(1−r0)⋅w~(0,1,0)+r0⋅w~(1,1,0)w3(1)=w~(1)(1,1)=(1−r0)⋅w~(0,1,1)+r0⋅w~(1,1,1)\begin{aligned} w^{(1)}_0 &= \tilde{w}^{(1)}(0, 0) = (1-r_0)\cdot\tilde{w}(0, 0, 0) + r_0\cdot\tilde{w}(1, 0, 0) \\ w^{(1)}_1 &= \tilde{w}^{(1)}(0, 1) = (1-r_0)\cdot\tilde{w}(0, 0, 1) + r_0\cdot\tilde{w}(1, 0, 1) \\ w^{(1)}_2 &= \tilde{w}^{(1)}(1, 0) = (1-r_0)\cdot\tilde{w}(0, 1, 0) + r_0\cdot\tilde{w}(1, 1, 0) \\ w^{(1)}_3 &= \tilde{w}^{(1)}(1, 1) = (1-r_0)\cdot\tilde{w}(0, 1, 1) + r_0\cdot\tilde{w}(1, 1, 1) \\ \end{aligned}
(24)

这两部分对 Multilinear Polynomial 的折叠计算加起来总共需要 2n2^n 次乘法与 2⋅2n2\cdot 2^n 次加法。计算结果保存在两个长度为 2n−12^{n-1} 的数组 a⃗(1)\vec{a}^{(1)} 和 w⃗(1)\vec{w}^{(1)} 中。

接下来 Prover 和 Verifier 要完成 FRI 协议的第一轮（Commit-phase），即计算折叠后的一元多项式的 RS Code。下面是 f~(X0,X1,X2)\tilde{f}(X_0, X_1, X_2) 所对应的一元多项式，f^(X)\hat{f}(X)。请务必注意，它的系数式对应于 f~(X)\tilde{f}(X) 的 Evaluations表示，这不同于 Basefold 论文 [ZCF23] 中的形式：

f^(X)=a0+a1X+a2X2+a3X3+a4X4+a5X5+a6X6+a7X7\hat{f}(X) = a_0 + a_1X + a_2X^2 + a_3X^3 + a_4X^4 + a_5X^5 + a_6X^6 + a_7X^7
(25)

Prover 在 Sumcheck 第一轮中已经计算得到了折叠后的 f~(1)(X1,X2)\tilde{f}^{(1)}(X_1, X_2) 的 Evaluations 表示，即 a⃗(1)\vec{a}^{(1)}。它也对应到一个一元多项式 f^(1)(X)\hat{f}^{(1)}(X)，其系数式表示为：

f^(1)(X)=a0(1)+a1(1)X+a2(1)X2+a3(1)X3\begin{aligned} \hat{f}^{(1)}(X) &= a^{(1)}_0 + a^{(1)}_1X + a^{(1)}_2X^2 + a^{(1)}_3X^3 \end{aligned}
(26)

接下来，Prover 需要计算 f~(1)(X)\tilde{f}^{(1)}(X) 的 RS Code，如果直接计算，这需要 Prover 计算 (n2n−1)(n2^{n-1}) 次乘法。幸运地是，由于 RS Code 是一种「线性编码」，因此 Prover 可以直接在 f^(X)\hat{f}(X) 的 RS Code 上直接用 (1−r0,r0)(1-r_0, r_0) 进行折叠运算，即可得到 f^(1)(X)\hat{f}^{(1)}(X) 的 RS Code。

先回顾下熟悉的 f^(X)\hat{f}(X) 的多项式分解：

f^(X)=fe(X2)+X⋅fo(X2)f^(−X)=fe(X2)−X⋅fo(X2)\begin{aligned} \hat{f}(X) &= f_e(X^2) + X\cdot f_o(X^2) \\ \hat{f}(-X) &= f_e(X^2) - X\cdot f_o(X^2) \end{aligned}
(27)

其中 fe(X)f_e(X) 是偶数项组成的多项式，fo(X)f_o(X) 是奇数项组成的多项式：

fe(X)=a0+a2X+a4X2+a6X3fo(X)=a1+a3X+a5X2+a7X3\begin{aligned} f_e(X) &= a_0 + a_2X + a_4X^2 + a_6X^3 \\ f_o(X) &= a_1 + a_3X + a_5X^2 + a_7X^3 \end{aligned}
(28)

又因为

f^(1)(X2)=(1−r0)⋅fe(X2)+r0⋅fo(X2)=(1−r0)⋅f^(X)+f^(−X)2+r0⋅f^(X)−f^(−X)2\begin{aligned} \hat{f}^{(1)}(X^2) &= (1-r_0)\cdot f_e(X^2) + r_0\cdot f_o(X^2) \\ & = (1-r_0)\cdot\frac{\hat{f}(X)+\hat{f}(-X)}{2} + r_0\cdot\frac{\hat{f}(X)-\hat{f}(-X)}{2} \end{aligned}
(29)

所以，Prover 只需要对 f^(X)\hat{f}(X) 的 RS Code 进行同样的折叠运算，就可以得到 f^(1)(X)\hat{f}^{(1)}(X) 的 RS Code：

encode(f^(1))i=(1−r0)⋅encode(f^)i+r0⋅encode(f^)(i+N/2),i∈[0,N)\mathsf{encode}(\hat{f}^{(1)})_i = (1-r_0)\cdot\mathsf{encode}(\hat{f})_i + r_0\cdot\mathsf{encode}(\hat{f})_{(i+N/2)}, \quad i\in[0, N)
(30)

这里 NN 为长度为 2n2^n 的消息经过编码后的长度，其中 ρ=2n/N\rho=2^n/N 为码率。

这时候 Prover 发送 encode(f^(1))\mathsf{encode}(\hat{f}^{(1)}) 的 Merkle Root 作为承诺，然后 Prover 和 Verifier 进行 Sumcheck 的第二轮，重复上面的过程，直到 Sumcheck 协议的求和项长度为 1 ，这时伴随执行的 FRI 协议也将多项式折叠到了一个常数多项式 f^(3)(X)\hat{f}^{(3)}(X)。如果 Prover 诚实，那么 f^(3)(X)\hat{f}^{(3)}(X) 的常数项恰好就是 f~(r0,r1,r2)\tilde{f}(r_0, r_1, r_2)：

f^(3)(X)=f~(r0,r1,r2)\hat{f}^{(3)}(X) = \tilde{f}(r_0, r_1, r_2)
(31)

这个值正好可以被 Verifier 利用用来验证：

v(3)=?f^(3)(0)⋅eq~((u0,u1,u2),(r0,r1,r2))v^{(3)} \overset{?}{=} \hat{f}^{(3)}(0)\cdot \tilde{eq}((u_0, u_1, u_2), (r_0, r_1, r_2))
(32)

这时候，Verifier 需要计算 eq~((u0,u1,u2),(r0,r1,r2))\tilde{eq}((u_0, u_1, u_2), (r_0, r_1, r_2)) 来完成最后的验证步，这需要 2n2n 次乘法：

eq~((u0,u1,u2),(r0,r1,r2))=∏i=02((1−ri)⋅(1−ui)+ri⋅ui)=∏i=02(1+2ri⋅ui−ri−ui)\begin{aligned} \tilde{eq}((u_0, u_1, u_2), (r_0, r_1, r_2)) &= \prod_{i=0}^{2} \Big( (1-r_i)\cdot(1-u_i) + r_i\cdot u_i \Big) \\ &= \prod_{i=0}^{2} \Big( 1 + 2r_i\cdot u_i - r_i -u_i \Big) \end{aligned}
(33)

对于 FRI 的 Query-phase 部分，这里我们略去。

Sumcheck 性能分析

在 Sumcheck 协议部分，Prover 总共的计算量为

Verifier 计算量：

Sumcheck 优化

在上面的协议中，Prover 需要发送 Degree 为 2 的 h(0)(X),h(1)(X),h(2)(X)h^{(0)}(X), h^{(1)}(X), h^{(2)}(X) 三个多项式。最朴素的实现是 Prover 发送这些多项式在 X=0,1,2X=0,1,2 处的三个运算值，Verifier 检查前两个值，然后利用第三个值来计算 Lagrange Interpolation，计算得到 h(0)(r0)h^{(0)}(r_0)。

我们可以对上面的协议稍做变化，即可让 Prover 只发送 Degree 为 1 的线性多项式，那么 Prover 仅需要发两个点的运算值即可，而且 Verifier 也只需要做线性插值即可计算出下一个求和值。

Habock 在 [Hab24] 中给出了一个 Basefold 协议的优化版本，可以把 h(X)h(X) 变成 Degree 为 1 的线性多项式。这个优化技术最早出现在 [Gru24] 中。下面我们简述下这个优化技术。

根据 eq~(X⃗,Y⃗)\tilde{eq}(\vec{X}, \vec{Y}) 的定义，它可以被分解为：

eq~(X⃗0∥X⃗1,Y⃗0∥Y⃗1)=eq(X⃗0,Y⃗0)⋅eq(X⃗1,Y⃗1)\tilde{eq}(\vec{X}_0\parallel\vec{X}_1, \vec{Y}_0\parallel\vec{Y}_1) = eq(\vec{X}_0, \vec{Y}_0) \cdot eq(\vec{X}_1, \vec{Y}_1)
(34)

我们先观察下 h(0)(X)h^{(0)}(X) 的定义：

h(0)(X)=∑b1,b2∈{0,1}2f~(X,b1,b2)⋅eq~((u0,u1,u2),(X,b1,b2))h^{(0)}(X) = \sum_{b_1,b_2\in\{0,1\}^{2}} \tilde{f}(X, b_1, b_2) \cdot \tilde{eq}((u_0, u_1, u_2), (X, b_1, b_2))
(35)

它的等式右边可以改写为：

h(0)(X)=∑b1,b2∈{0,1}2f~(X,b1,b2)⋅eq~((u0,u1,u2),(X,b1,b2))=∑b1,b2∈{0,1}2f~(X,b1,b2)⋅eq(u0,X)⋅eq((u1,u2),(b1,b2))=eq(u0,X)⋅∑(b1,b2)∈{0,1}2‘(f~(X,b1,b2)⋅eq((u1,u2),(b1,b2)))\begin{aligned} h^{(0)}(X) &= \sum_{b_1,b_2\in\{0,1\}^{2}} \tilde{f}(X, b_1, b_2) \cdot \tilde{eq}((u_0, u_1, u_2), (X, b_1, b_2)) \\ &= \sum_{b_1,b_2\in\{0,1\}^{2}} \tilde{f}(X, b_1, b_2) \cdot eq(u_0, X) \cdot eq((u_1, u_2), (b_1, b_2)) \\ &= eq(u_0, X) \cdot \sum_{(b_1,b_2)\in\{0,1\}^2`} \Big( \tilde{f}(X, b_1, b_2) \cdot eq((u_1,u_2), (b_1, b_2)) \Big) \\ \end{aligned}
(36)

我们引入记号 g(0)(X)g^{(0)}(X) 来表示等式右边的除 eq(u0,X)eq(u_0, X) 之外的线性多项式，那么 h(0)(X)h^{(0)}(X) 可以表示为两个线性多项式的乘积：

h(0)(X)=eq(u0,X)⋅g(0)(X)h^{(0)}(X) = eq(u_0, X) \cdot g^{(0)}(X)
(37)

我们按照下面的方式修改协议，让 Prover 不直接发送 h0(X)h_0(X)，而是发送线性多项式 g0(X)g_0(X)，即 g(0)(0),g(0)(1)g^{(0)}(0), g^{(0)}(1)，

g(0)(X)=∑(b1,b2)∈{0,1}2(f~(X,b1,b2)⋅eq((u1,u2),(b1,b2)))g^{(0)}(X) = \sum_{(b_1,b_2)\in\{0,1\}^2} \Big( \tilde{f}(X, b_1, b_2) \cdot eq((u_1,u_2), (b_1, b_2)) \Big)
(38)

而 Verifier 收到 g(0)(0),g(0)(1)g^{(0)}(0), g^{(0)}(1) 多项式之后，可以自行计算 h(0)(0),h(0)(1)h^{(0)}(0), h^{(0)}(1) 的值，因为

h(0)(0)=(1−u0)⋅g(0)(0)h(0)(1)=u0⋅g(0)(1)\begin{aligned} h^{(0)}(0) &= (1-u_0)\cdot g^{(0)}(0) \\ h^{(0)}(1) &= u_0 \cdot g^{(0)}(1) \\ \end{aligned}
(39)

然后 Verifier 可以验证 h(0)(0)+h(0)(1)=?vh^{(0)}(0)+h^{(0)}(1)\overset{?}{=}v，如果验证通过，那么 Verifier 可以计算 h(0)(r0)h^{(0)}(r_0)，

h(0)(r0)=((1−u0)(1−r0)+u0r0)⋅g(0)(r0)h^{(0)}(r_0) = \Big((1-u_0)(1-r_0)+u_0r_0\Big) \cdot g^{(0)}(r_0)
(40)

这里 g(0)(r0)g^{(0)}(r_0) 也可以通过 g(0)(0),g(0)(1)g^{(0)}(0), g^{(0)}(1) 计算得到：

g(0)(r0)=g(0)(0)+(g(0)(1)−g(0)(0))⋅r0g^{(0)}(r_0) = g^{(0)}(0) + \Big(g^{(0)}(1)-g^{(0)}(0)\Big)\cdot r_0
(41)

最后计算得到 h0(r0)h_0(r_0) 。总结下，这样Verifier 需要一个乘法来验证 vv，三个乘法来计算 h(0)(r0)h^{(0)}(r_0)。

性能分析

Prover 总共的计算量为

Verifier 计算量：

进一步优化 Verifier

我们再观察下 g(0)(X)g^{(0)}(X) 的定义：

g(0)(X)=∑(b1,b2)∈{0,1}2(f~(X,b1,b2)⋅eq((u1,u2),(b1,b2)))g^{(0)}(X) = \sum_{(b_1,b_2)\in\{0,1\}^2} \Big( \tilde{f}(X, b_1, b_2) \cdot eq((u_1,u_2), (b_1, b_2)) \Big)
(42)

这个求和式恰好等于 f~(X,u1,u2)\tilde{f}(X, u_1, u_2)，于是我们可以换一个视角回顾下上面的优化协议：

Prover 在第一步发送 g(0)(0),g(0)(1)g^{(0)}(0), g^{(0)}(1)，实际上是发送：

g(0)(0)=f~(0,u1,u2)g(0)(1)=f~(1,u1,u2)\begin{aligned} g^{(0)}(0) &= \tilde{f}(0, u_1, u_2) \\ g^{(0)}(1) &= \tilde{f}(1, u_1, u_2) \\ \end{aligned}
(43)

Verifier 检查验证 h(0)(X)h^{(0)}(X) 的正确性，等价于验证 g(0)(X)g^{(0)}(X) 的正确性：

h(0)(u0)=eq(u0,u0)⋅g(0)(u0)=g(0)(u0)=g(0)(0)+(g(0)(1)−g(0)(0))⋅u0=?vh^{(0)}(u_0) = eq(u_0, u_0) \cdot g^{(0)}(u_0) = g^{(0)}(u_0) = g^{(0)}(0) + \Big(g^{(0)}(1)-g^{(0)}(0)\Big)\cdot u_0 \overset{?}{=} v
(44)

然后 Verifier 计算 g(0)(r0)g^{(0)}(r_0) 作为下一轮 Sumcheck 的求和值。

g(0)(r0)=g(0)(0)+(g(0)(1)−g(0)(0))⋅r0g^{(0)}(r_0) = g^{(0)}(0) + \Big(g^{(0)}(1)-g^{(0)}(0)\Big)\cdot r_0
(45)

因此，我们好像可以不再需要引入 h(i)(X)h^{(i)}(X)，而直接使用 g(i)(X)g^{(i)}(X) 即可。这样每一轮 Sumcheck 协议，Prover 需要发送 g(i)(0),g(i)(1)g^{(i)}(0), g^{(i)}(1)，Verifier 只需要计算两次乘法，一次用来计算 g(i)(ui)g^{(i)}(u_i)，一次用来计算 g(i)(ri)g^{(i)}(r_i)。而且在 Sumcheck 的最后一步，Verifier 只需要验证：

g(n−1)(rn−1)=?f~(r0,r1,⋯ ,rn−1)g^{(n-1)}(r_{n-1}) \overset{?}{=} \tilde{f}(r_0, r_1, \cdots, r_{n-1})
(46)

不难发现，在第 ii 轮，如果 Prover 诚实，g(i)(X)g^{(i)}(X) 恰好应该等于 f~(i)(r0,r1,⋯ ,ri−1,X,ui+1,⋯ ,un−1)\tilde{f}^{(i)}(r_0, r_1, \cdots, r_{i-1}, X, u_{i+1}, \cdots, u_{n-1})。我们重新写一下 改头换面后的 Sumcheck 协议：

第一轮：Prover 发送 f~(0,u1,u2),f~(1,u1,u2)\tilde{f}(0, u_1, u_2), \tilde{f}(1, u_1, u_2)，Verifier 验证：

(1−u0)⋅f~(0,u1,u2)+u0⋅f~(1,u1,u2)=?f~(u0,u1,u2)=v(1-u_0)\cdot \tilde{f}(0, u_1, u_2) + u_0\cdot \tilde{f}(1, u_1, u_2) \overset{?}{=} \tilde{f}(u_0, u_1, u_2) = v
(47)

Verifier 回应 r0∈Fr_0\in F，并计算 g(0)(r0)=f~(r0,u1,u2)g^{(0)}(r_0) = \tilde{f}(r_0, u_1, u_2) 作为新的求和值 v(1)v^{(1)}：

f~(r0,u1,u2)=(1−r0)⋅f~(0,u1,u2)+r0⋅f~(1,u1,u2)\tilde{f}(r_0, u_1, u_2) = (1-r_0)\cdot \tilde{f}(0, u_1, u_2) + r_0\cdot \tilde{f}(1, u_1, u_2)
(48)

第二轮：Prover 发送 f~(r0,0,u2),f~(r0,1,u2)\tilde{f}(r_0, 0, u_2), \tilde{f}(r_0, 1, u_2)，Verifier 验证：

(1−u1)⋅f~(r0,0,u2)+u1⋅f~(r0,1,u2)=?f~(r0,u1,u2)=v(1)(1-u_1)\cdot \tilde{f}(r_0, 0, u_2) + u_1\cdot \tilde{f}(r_0, 1, u_2) \overset{?}{=} \tilde{f}(r_0, u_1, u_2) = v^{(1)}
(49)

Verifier 回应 r1∈Fr_1\in F，并计算 g(1)(r1)=f~(r0,r1,u2)g^{(1)}(r_1) = \tilde{f}(r_0, r_1, u_2) 作为新的求和值：

f~(r0,r1,u2)=(1−r1)⋅f~(r0,0,u2)+r1⋅f~(r0,1,u2)\tilde{f}(r_0, r_1, u_2) = (1-r_1)\cdot \tilde{f}(r_0, 0, u_2) + r_1\cdot \tilde{f}(r_0, 1, u_2)
(50)

第三轮：Prover 发送 f~(r0,r1,0),f~(r0,r1,1)\tilde{f}(r_0, r_1, 0), \tilde{f}(r_0, r_1, 1)，Verifier 验证：

(1−u2)⋅f~(r0,r1,0)+u2⋅f~(r0,r1,1)=?f~(r0,r1,u2)=v(2)(1-u_2)\cdot \tilde{f}(r_0, r_1, 0) + u_2\cdot \tilde{f}(r_0, r_1, 1) \overset{?}{=} \tilde{f}(r_0, r_1, u_2) = v^{(2)}
(51)

Verifier 回应 r2∈Fr_2\in F，并计算 g(2)(r2)=f~(r0,r1,r2)g^{(2)}(r_2) = \tilde{f}(r_0, r_1, r_2) 作为新的求和值：

f~(r0,r1,r2)=(1−r2)⋅f~(r0,r1,0)+r2⋅f~(r0,r1,1)\tilde{f}(r_0, r_1, r_2) = (1-r_2)\cdot \tilde{f}(r_0, r_1, 0) + r_2\cdot \tilde{f}(r_0, r_1, 1)
(52)

验证步：Verifier 通过 f~(X0,X1,X2)\tilde{f}(X_0, X_1, X_2) Oracle，验证下面的等式：

g(2)(r2)=?f~(r0,r1,r2)g^{(2)}(r_2) \overset{?}{=} \tilde{f}(r_0, r_1, r_2)
(53)

这样每轮 Verifier 只需要进行两次乘法运算即可，第一个乘法是验证求和值 v(i)v^{(i)} 的正确性，第二个乘法是计算 g(i)(ri)g^{(i)}(r_i)，总共 2n2n 个乘法。

Prover 的计算优化

Prover 在三轮中，需要依次发送：g(0)(0)g^{(0)}(0) 和 g(0)(1)g^{(0)}(1)，g(1)(0)g^{(1)}(0) 和 g(1)(1)g^{(1)}(1)，g(2)(0)g^{(2)}(0) 和 g(2)(1)g^{(2)}(1)。

g(0)(0)=f~(0,u1,u2)g(0)(1)=f~(1,u1,u2)g(1)(0)=f~(r0,0,u2)g(1)(1)=f~(r0,1,u2)g(2)(0)=f~(r0,r1,0)g(2)(1)=f~(r0,r1,1)\begin{aligned} g^{(0)}(0) &= \tilde{f}(0, u_1, u_2) \\ g^{(0)}(1) &= \tilde{f}(1, u_1, u_2) \\ g^{(1)}(0) &= \tilde{f}(r_0, 0, u_2) \\ g^{(1)}(1) &= \tilde{f}(r_0, 1, u_2) \\ g^{(2)}(0) &= \tilde{f}(r_0, r_1, 0) \\ g^{(2)}(1) &= \tilde{f}(r_0, r_1, 1) \\ \end{aligned}
(54)

这一节我们看下 Prover 如何能高效地计算 g(i)(0),g(i)(1)g^{(i)}(0), g^{(i)}(1)。

前文我们提到 Prover 维护了一个数组 a⃗\vec{a}，长度为 2n2^n，

a0=f~(0,0,0)a1=f~(1,0,0)a2=f~(0,1,0)a3=f~(1,1,0)a4=f~(0,0,1)a5=f~(1,0,1)a6=f~(0,1,1)a7=f~(1,1,1)\begin{aligned} a_0 &= \tilde{f}(0, 0, 0) \\ a_1 &= \tilde{f}(1, 0, 0) \\ a_2 &= \tilde{f}(0, 1, 0) \\ a_3 &= \tilde{f}(1, 1, 0) \\ a_4 &= \tilde{f}(0, 0, 1) \\ a_5 &= \tilde{f}(1, 0, 1) \\ a_6 &= \tilde{f}(0, 1, 1) \\ a_7 &= \tilde{f}(1, 1, 1) \\ \end{aligned}
(55)

在每次 Sumcheck 轮中进行折叠，例如在经过第一轮的折叠（ r0r_0 作为折叠因子）后，Prover 得到：

a0(1)=f~(1)(0,0)=(1−r0)⋅f~(0,0,0)+r0⋅f~(1,0,0)a1(1)=f~(1)(0,1)=(1−r0)⋅f~(0,0,1)+r0⋅f~(1,0,1)a2(1)=f~(1)(1,0)=(1−r0)⋅f~(0,1,0)+r0⋅f~(1,1,0)a3(1)=f~(1)(1,1)=(1−r0)⋅f~(0,1,1)+r0⋅f~(1,1,1)\begin{aligned} a^{(1)}_0 &= \tilde{f}^{(1)}(0, 0) = (1-r_0)\cdot\tilde{f}(0, 0, 0) + r_0\cdot\tilde{f}(1, 0, 0) \\ a^{(1)}_1 &= \tilde{f}^{(1)}(0, 1) = (1-r_0)\cdot\tilde{f}(0, 0, 1) + r_0\cdot\tilde{f}(1, 0, 1) \\ a^{(1)}_2 &= \tilde{f}^{(1)}(1, 0) = (1-r_0)\cdot\tilde{f}(0, 1, 0) + r_0\cdot\tilde{f}(1, 1, 0) \\ a^{(1)}_3 &= \tilde{f}^{(1)}(1, 1) = (1-r_0)\cdot\tilde{f}(0, 1, 1) + r_0\cdot\tilde{f}(1, 1, 1) \\ \end{aligned}
(56)

为了高效计算 g(i)(0),g(i)(1)g^{(i)}(0), g^{(i)}(1)，我们让 Prover 在 Sumcheck 协议开始前，进行一番预计算，得到一个长度为 2n−12^n-1 的向量 d⃗\vec{d}。

这个向量是将 a⃗\vec{a} 向量（u2,u1,u0u_2, u_1, u_0 作为折叠因子）折叠后计算得到的结果。我们先将 a⃗\vec{a} 向量采用 u2u_2 折叠，得到 d0,d1,d2,d3d_0, d_1, d_2, d_3：

d0=(1−u2)⋅a0+u2⋅a4=f~(0,0,u2)d1=(1−u2)⋅a1+u2⋅a5=f~(1,0,u2)d2=(1−u2)⋅a2+u2⋅a6=f~(0,1,u2)d3=(1−u2)⋅a3+u2⋅a7=f~(1,1,u2)\begin{aligned} d_0 &= (1-u_2)\cdot a_0 + u_2\cdot a_4 = \tilde{f}(0, 0, u_2)\\ d_1 &= (1-u_2)\cdot a_1 + u_2\cdot a_5 = \tilde{f}(1, 0, u_2)\\ d_2 &= (1-u_2)\cdot a_2 + u_2\cdot a_6 = \tilde{f}(0, 1, u_2)\\ d_3 &= (1-u_2)\cdot a_3 + u_2\cdot a_7 = \tilde{f}(1, 1, u_2)\\ \end{aligned}
(57)

然后 Prover 对 d0,d1,d2,d3d_0, d_1, d_2, d_3 再次进行折叠运算，使用折叠因子 u1u_1，得到 d4,d5d_4, d_5：

d4=(1−u1)⋅d0+u1⋅d2=f~(0,u1,u2)d5=(1−u1)⋅d1+u1⋅d3=f~(1,u1,u2)\begin{aligned} d_4 &= (1-u_1)\cdot d_0 + u_1\cdot d_2 = \tilde{f}(0, u_1, u_2)\\ d_5 &= (1-u_1)\cdot d_1 + u_1\cdot d_3 = \tilde{f}(1, u_1, u_2)\\ \end{aligned}
(58)

最后 Prover 对 d4,d5d_4, d_5 进行折叠运算，使用折叠因子 u0u_0，得到 d6d_6：

d6=(1−u0)⋅d4+u0⋅d5=f~(u0,u1,u2)d_6 = (1-u_0)\cdot d_4 + u_0\cdot d_5 = \tilde{f}(u_0, u_1, u_2)
(59)

观察下，向量 (d0,d1,d2,d3,d4,d5,d6)(d_0, d_1, d_2, d_3, d_4, d_5, d_6) 的末尾值 d6d_6 恰好是 f~(u0,u1,u2)\tilde{f}(u_0, u_1, u_2)，而倒数第二个和第三个元素，恰好是 g(0)(0),g(0)(1)g^{(0)}(0), g^{(0)}(1)：

g(0)(0)=d4g(0)(1)=d5g^{(0)}(0) = d_4 \\ g^{(0)}(1) = d_5 \\
(60)

如果 Prover 去除 d6d_6，将剩下的向量 (d0,d1,d2,d3,d4,d5)(d_0, d_1, d_2, d_3, d_4, d_5) 跟随 a⃗\vec{a} 一同折叠（采用 r0r_0 作为折叠因子），那么我们可以得到：

d0′=(1−r0)⋅d0+r0⋅d1=f~(r0,0,u2)d1′=(1−r0)⋅d2+r0⋅d3=f~(r0,1,u2)d2′=(1−r0)⋅d4+r0⋅d5=f~(r0,u1,u2)\begin{aligned} d'_0 &= (1-r_0)\cdot d_0 + r_0\cdot d_1 = \tilde{f}(r_0, 0, u_2) \\ d'_1 &= (1-r_0)\cdot d_2 + r_0\cdot d_3 = \tilde{f}(r_0, 1, u_2) \\ d'_2 &= (1-r_0)\cdot d_4 + r_0\cdot d_5 = \tilde{f}(r_0, u_1, u_2) \\ \end{aligned}
(61)

我们惊奇地发现，d2′d'_2 恰好是 g(0)(r0)g^{(0)}(r_0) 的值，而 d0′,d1′d'_0, d'_1 恰好是 g(1)(0),g(1)(1)g^{(1)}(0), g^{(1)}(1) 的值。

接下来在第二轮 Sumcheck 中，Prover 将 (d0′,d1′)(d'_0, d'_1) 跟随 a⃗′\vec{a}' 一起采用 r1r_1 进行折叠，可以得到 d0′′d''_0 的值：

d0′′=(1−r1)⋅d0′+r1⋅d1′=f~(r0,r1,u2)d''_0 = (1-r_1)\cdot d'_0 + r_1\cdot d'_1 = \tilde{f}(r_0, r_1, u_2)
(62)

这恰好是 g(1)(r1)g^{(1)}(r_1) 的值。

那么在第三轮 Sumcheck 中，Prover 需要发送 g(2)(0),g(2)(1)g^{(2)}(0), g^{(2)}(1) 的值，可是 d⃗\vec{d} 向量已经折叠消失，不过这时候，Prover 手里有折叠后的 a⃗\vec{a} 向量：

a0(2)=f~(2)(0)=f~(r0,r1,0)a1(2)=f~(2)(1)=f~(r0,r1,1)\begin{aligned} a^{(2)}_0 &= \tilde{f}^{(2)}(0) = \tilde{f}(r_0, r_1, 0) \\ a^{(2)}_1 &= \tilde{f}^{(2)}(1) = \tilde{f}(r_0, r_1, 1) \\ \end{aligned}
(63)

这两个值恰好等于 g(2)(0),g(2)(1)g^{(2)}(0), g^{(2)}(1) 的值。

性能分析

至此，我们总结下，只需要让 Prover 在 Sumcheck 开始前，预计算出向量 d⃗\vec{d}，它保存了 f~(X0,X1,X2)\tilde{f}(X_0, X_1, X_2) 依次带入 X2=u2,X1=u1,X0=u0X_2=u_2, X_1=u_1, X_0=u_0 进行 Partial Evaluation 的所有中间结果。而这个向量跟随 a⃗\vec{a} 向量采用相同的随机挑战数一同进行折叠，那么就可以高效计算出 g(i)(0),g(i)(1),g(i)(ri)g^{(i)}(0), g^{(i)}(1), g^{(i)}(r_i) 的值。其中预计算需要 2n−12^n-1 次乘法，折叠总共需要 2n−22^n-2 次乘法。

Prover 计算量：

Verifier 计算量：

再进一步优化 Verifier

在上面的协议中，Prover 需要发送 g(i)(0),g(i)(1)g^{(i)}(0), g^{(i)}(1) ，然后 Verifier 验证

g(i)(0)+(g(i)(1)−g(i)(0))⋅ui=?g(i−1)(ri−1)=g(i)(ui)g^{(i)}(0) + (g^{(i)}(1) - g^{(i)}(0))\cdot u_i \overset{?}{=} g^{(i-1)}(r_{i-1}) = g^{(i)}(u_i)
(64)

那么其实，Prover 在每轮 Sumcheck 中只需发送一个值 g(i)(0)g^{(i)}(0)，然后 Verifier 根据「验证等式」反向计算得到 g(i)(1)g^{(i)}(1) ：

g(i)(1)=g(i−1)(ri−1)−g(i)(0)ui+g(i)(0)g^{(i)}(1) = \frac{g^{(i-1)}(r_{i-1}) - g^{(i)}(0)}{u_i} + g^{(i)}(0)
(65)

这样一来 Verifier 用一次除法计算来换取通讯量的减少（一半）。但注意有限域除法（求逆）的计算开销要显著大于乘法，计算量至少是 o(log⁡q)o(\log{q}) 的复杂度。但是无论如何，我们通过这种方式，可以进一步减少通讯量，即 Proof size。

其实，我们不难发现这个开销相对不小的除法是可以优化掉的，这个思路来源于 Deepfold []。我们让 Prover 在每轮 Sumcheck 中只发送 g(i)(ui+1)g^{(i)}(u_i+1) 而不是 gi(0)g_i(0) 或 gi(1)g_i(1)：

g(i)(ui+1)=g(i)(ui)+g(i)(1)−g(i)(0)g^{(i)}(u_i+1) = g^{(i)}(u_i) + g^{(i)}(1) - g^{(i)}(0)
(66)

再次提醒，g(i)(ui)g^{(i)}(u_i) 是 d⃗\vec{d} 向量每次折叠之后的尾部元素，因此它的计算开销已经包含在 d⃗\vec{d} 的折叠计算中。因此 Prover 的代价仅仅为在每轮额外计算两次加法。

然后，又因为此时Verifier 手里已经有了 g(i)(ui)=g(i−1)(ri−1)g^{(i)}(u_{i})=g^{(i-1)}(r_{i-1})，这样 Verifier 可以不用除法就可得到 g(i)(ri)g^{(i)}(r_i)：

g(i)(ri)=g(i)(ui)+(g(i)(ui+1)−g(i)(ui))⋅(ri−ui)g^{(i)}(r_i) = g^{(i)}(u_i) + \Big(g^{(i)}(u_i+1)-g^{(i)}(u_i)\Big)\cdot (r_i - u_i)
(67)

计算开销仅为三次加法与一次乘法。

性能分析

Prover 计算量：

Verifier 计算量：

从另一个角度来理解 Sumcheck 优化

上面我们经过多步的优化，达到了一个比较理想的状态。我们看看能否更容易地去理解这个简洁的协议。

我们可以把上面的优化协议看成是一个 Recursive Split-and-fold 风格的求和证明。因为本身 f~(u0,u1,u2)\tilde{f}(u_0, u_1, u_2) 就是一个数量为 8 项的求和式：

f~(u0,u1,u2)=a0(1−u0)(1−u1)(1−u2)+a1u0(1−u1)(1−u2)+a2(1−u0)u1(1−u2)+a3u0u1(1−u2)+a4(1−u0)u1u2+a5u0(1−u1)u2+a6u0u1(1−u2)+a7u0u1u2=(1−u0)⋅(a0(1−u1)(1−u2)+a2u1(1−u2)+a4(1−u1)u2+a6u1u2)+u0⋅(a1(1−u1)(1−u2)+a3u1(1−u2)+a5(1−u1)u2+a7u1u2)\begin{aligned} \tilde{f}(u_0, u_1, u_2) &= a_0(1-u_0)(1-u_1)(1-u_2) + a_1u_0(1-u_1)(1-u_2) \\ &+ a_2(1-u_0)u_1(1-u_2) + a_3u_0u_1(1-u_2) \\ &+ a_4(1-u_0)u_1u_2 + a_5u_0(1-u_1)u_2 \\ &+ a_6u_0u_1(1-u_2) + a_7u_0u_1u_2 \\ & = (1-u_0)\cdot \Big(a_0(1-u_1)(1-u_2) + a_2u_1(1-u_2) + a_4(1-u_1)u_2 + a_6u_1u_2 \Big) \\ &+ u_0\cdot \Big(a_1(1-u_1)(1-u_2) + a_3u_1(1-u_2) + a_5(1-u_1)u_2 + a_7u_1u_2 \Big) \\ \end{aligned}
(68)

第一轮，Prover 分别发送左半边的括号中 4 项的和，右半边括号中 4 项的和，分别记为 g0(0)g_0(0) 和 g0(1)g_0(1)，并发送给 Verifier：

g0(0)=a0(1−u1)(1−u2)+a2u1(1−u2)+a4(1−u1)u2+a6u1u2g0(1)=a1(1−u1)(1−u2)+a3u1(1−u2)+a5(1−u1)u2+a7u1u2\begin{aligned} g_0(0) &= a_0(1-u_1)(1-u_2) + a_2u_1(1-u_2) + a_4(1-u_1)u_2 + a_6u_1u_2 \\ g_0(1) &= a_1(1-u_1)(1-u_2) + a_3u_1(1-u_2) + a_5(1-u_1)u_2 + a_7u_1u_2 \\ \end{aligned}
(69)

或者

g0(0)=f~(0,u1,u2)g0(1)=f~(1,u1,u2)\begin{aligned} g_0(0) &= \tilde{f}(0, u_1, u_2) \\ g_0(1) &= \tilde{f}(1, u_1, u_2) \\ \end{aligned}
(70)

然后 Verifier 首先验证 (g0(0),g0(1))(g_0(0), g_0(1)) 与 (1−u0,u0)(1-u_0, u_0) 进行内积的结果是否等于待证明的和 vv，

(1−u0)⋅g0(0)+u0⋅g0(1)=?f~(u0,u1,u2)(1-u_0)\cdot g_0(0) + u_0\cdot g_0(1) \overset{?}{=} \tilde{f}(u_0, u_1, u_2)
(71)

这样一来，Prover 和 Verifier 就将长度为 8 的求和证明 Reduce 到了两个长度为 4 的求和证明。又因为这两个新的求和式实际上具有相同的结构，即它们都是多项式的奇偶项系数分别和同一向量 (1−u1,u1)⊗(1−u2,u2)(1-u_1,u_1)\otimes(1-u_2,u_2) 进行内积的结果，

g(0)(0)=⟨(a0,a2,a4,a6),(1−u1,u1)⊗(1−u2,u2)⟩g(0)(1)=⟨(a1,a3,a5,a7),(1−u1,u1)⊗(1−u2,u2)⟩\begin{aligned} g^{(0)}(0) &= \langle(a_0, a_2, a_4, a_6), (1-u_1, u_1)\otimes(1-u_2, u_2)\rangle \\ g^{(0)}(1) &= \langle(a_1, a_3, a_5, a_7), (1-u_1, u_1)\otimes(1-u_2, u_2)\rangle \\ \end{aligned}
(72)

所以 Verifier 可以给出一个随机数 r0r_0，利用它把这两个新的求和证明合并（Batching）在一起。巧合的是，合并之后的长度为 4 的求和值恰好是 g(0)(r0)g^{(0)}(r_0) ，并且它等于 f~(r0,u1,u2)\tilde{f}(r_0, u_1, u_2)。当然这其实不是巧合，因为我们故意采用 (1−r0,r0)(1-r_0, r_0) 这种 Multilinear Basis 对 g(0)(0),g(0)(1)g^{(0)}(0), g^{(0)}(1) 进行折叠，目的正是使之与 g(0)(r0)g^{(0)}(r_0) 保持相等：

(1−r0)⋅g0(0)+r0⋅g0(1)=f~(r0,u1,u2)(1-r_0)\cdot g_0(0) + r_0\cdot g_0(1) = \tilde{f}(r_0, u_1, u_2)
(73)

这样，Prover 和 Verifier 接下来证明合并后的长度为 4 个向量的求和值等于 f~(r0,u1,u2)\tilde{f}(r_0, u_1, u_2)，即

(1−r0)⋅g(0)(0)+r0⋅g(0)(1)=?a0′w0′+a1′w1′+a2′w2′+a3′w3′(1-r_0)\cdot g^{(0)}(0) + r_0\cdot g^{(0)}(1) \overset{?}{=} a'_0w'_0 + a'_1w'_1 + a'_2w'_2 + a'_3w'_3
(74)

依次类推，这个协议和 Sumcheck 协议的思路是一致的，都是将一个求和等式，通过拆分成多段不同部分的求和，然后再用随机数将这些不同的求和段合并在一起证明。直到最后一轮，求和证明 Reduce 到了多项式的求值证明，Prover 和 Verifier 再借助其他工具来补上最后的证明部分。

而最原始的 Sumcheck in Basefold 协议，则没有利用求和式内部结构，而是采用了一个更通用的内积求和的证明。因此本文介绍的简洁协议正式充分利用了求和项的内部结构。

References

Basefold
笔记：Basefold 在 List Decoding 下的 Soundness 证明
FRI
[BBHR18] FRI 论文 soundness 解析