Skip to article frontmatterSkip to article content

MLE-PCS 比较 (最终报告)

Last update: 2025-06-12

背景

多项式承诺方案 (Polynomial Commitment Scheme) 是许多 zkSNARK (zero-knowledge Succinct Non-interactive ARguments of Knowledge) 系统中的一个重要组件。对于 Prover 承诺的一个多项式,Prover 可以向 Verifier 证明该多项式在一个公开的打开点的值是正确的。

zkSNARK 最初,例如 [KZG10] 多项式承诺方案支持的仅是单变量多项式,假设该单变量多项式有 NN 个系数,那么 Prover 的计算复杂度为 O(NlogN)O(N \log N) 。最近,许多 SNARK 证明系统开始使用多元线性多项式承诺方案 (Multilinear Polynomial Commitment Schemes, MLE-PCS),例如 Hyperplonk[CBBZ22],假设多元线性多项式有 NN 个系数,那么 Prover 的计算复杂度可以达到线性,即 O(N)O(N) 。MLE-PCS 不仅可以用来构建更加高效的证明系统,同时多元线性多项式的表示方式还能带来其他的好处,例如在 Hypercube 上能进行高效的递归拆分折叠(Split-and-fold),对支持高次的约束更加友好,分解更加灵活。

本项目 MLE-PCS 关注于研究并比较不同的多元线性多项式承诺方案,包括方案的设计、安全假设以及效率等方面。

MLE-PCS 概览

对于一个 nn 元线性多项式 f~(X0,X1,,Xn1)\tilde{f}(X_0, X_1, \ldots, X_{n - 1}) ,有以下两种表示形式:

  1. Coefficients form

多元线性多项式用系数可以表示为如下的形式

f~(X0,X1,,Xn1)=c0+c1X0+c2X1++c2n1X0X1Xn1\tilde{f}(X_0, X_1, \ldots, X_{n - 1}) = c_0 + c_1 X_0 + c_2 X_1 + \ldots + c_{2^n - 1} X_0 X_1 \cdots X_{n - 1}

其中 {ci}0i2n1\{c_i\}_{0 \le i \le 2^{n} - 1} 为该多元线性多项式的系数。

  1. Evaluations form

多元线性多项式还可以用在 Boolean Hypercube Bn={0,1}nB_n = \{0,1\}^n 上的值的形式表示,即

f~(X0,X1,,Xn1)=i=02n1f~(bits(i))eq~(bits(i),(X0,X1,,Xn1))\tilde{f}(X_0, X_1, \ldots, X_{n - 1}) = \sum_{i = 0}^{2^n - 1} \tilde{f}(\mathsf{bits}(i)) \cdot \tilde{eq}(\mathsf{bits}(i), (X_0, X_1, \ldots, X_{n - 1}))

其中,bits(i)=(i0,i1,,in1)\mathsf{bits}(i) = (i_0, i_1, \ldots, i_{n-1}) 表示 ii 的二进制表示构成的向量,向量中的第一个分量 i0i_0 为二进制表示中的最低位,即 Little-endian。例如当 n=3n = 3 时,3 的二进制表示为 011 ,则向量 bits(3)=(1,1,0)\mathsf{bits}(3) = (1,1,0)eq~(bits(i),(X0,X1,,Xn1))\tilde{eq}(\mathsf{bits}(i), (X_0, X_1, \ldots, X_{n - 1})) 为 Boolean Hypercube Bn={0,1}nB_n = \{0,1\}^n 上的 Lagrange 多项式,即

eq~(bits(i),(X0,X1,,Xn1))=j=0n1((1ij)(1Xj)+ijXj)\tilde{eq}(\mathsf{bits}(i), (X_0, X_1, \ldots, X_{n - 1})) = \prod_{j = 0}^{n - 1} ((1 - i_j)(1 - X_j) + i_j X_j)

在 MLE-PCS 的承诺协议中,Prover 先向 Verifier 承诺多元线性多项式 f~\tilde{f} ,随后在 Evaluation 证明协议中,Prover 要向 Verifier 证明 f~\tilde{f} 在一个公开点 u=(u0,,un1)\vec{u} = (u_0, \ldots, u_{n - 1}) 处的运算值为 vv,即证明 f~(u0,,un1)=v\tilde{f}(u_0, \ldots, u_{n - 1}) = v

有的 MLE-PCS 协议是按照 Evaluations Form 描述的,而有的协议是按照 Coefficients Form 描述的。这中间自然就会产生一个形式转换的问题,例如一个多元线性多项式是按照系数形式给定的,那么就需要用类似 FFT 的算法将其转换为 Evaluation 形式以适配用 Evaluation 描述的协议。不过,许多作者已经注意到不需要经过这个 FFT 转换,也能适配该协议。以 Basefold [ZCF23] 协议举例,在原论文 [ZCF23] 中,协议是按照系数进行描述的,但是 Ulrich Haböck 在论文 [H24] 中以 Evaluation 的形式重新描述了 Basefold 协议,在原 Basefold 协议的基础上,只需要更改 FRI 协议中的折叠形式即可,关于这部分的转换可见笔记 An Alternative Folding Method

本项目的工作描述了许多 MLE-PCS 的基本原理,同时对于有的协议,我们还补充了多元线性多项式在另一种表示形式下的协议描述。在下表中给出本项目所涉及的 MLE-PCS。

SchemePaperNotes
PST13[XZZPS19]Notes on Libra-PCS
zeromorph[KT23]Notes on Zeromorph, Zeromorph-PCS (Part II)
zeromorph-friZeromorph-PCS: Integration with FRI
gemini[BCH+22]Gemini-PCS (Part I),Gemini-PCS (Part II),Gemini-PCS (Part III), Gemini-PCS (Part IV)
gemini-friGemini: Interfacing with FRI
hyperKZGN/ANotes on HyperKZG
PH23-KZG[PH23]The Missing Protocol PH23-PCS (Part 1), Missing Protocol PH23-PCS (Part 2)
PH23-fri缺失的协议 PH23-PCS(四),缺失的协议 PH23-PCS(四)
Mercury[EG25]Mercury 笔记:实现常数证明尺寸, Mercury 笔记:对接 KZG
Samaritan[GPS25]
Virgo[ZXZS19]Notes on Virgo-PCS
Hyrax[WTSTW18]Notes on Hyrax-PCS
Basefold[ZCF23]Notes on Basefold (Part I): Foldable Linear Codes, Notes on Basefold (Part II): IOPP, Notes on Basefold (Part III): MLE Evaluation Argument
BasefoldAn Alternative Folding Method
Deepfold[GLHQTZ24]Note on DeepFold: Protocol Overview
Ligerito[GLHQTZ24]Notes on Ligerito-PCS
WHIR[ACFY24b]Note on WHIR: Reed-Solomon Proximity Testing with Super-Fast Verification
FRI-Binius[DP24]Notes on FRI-Binius (Part I): Binary Towers, Notes on Binius (Part II): Subspace Polynomial
Greyhound[NS24]Greyhound Commitment
Σ-Check[GQZGX24]https://eprint.iacr.org/2024/1654.pdf
Hyperwolf[ZGX25]https://eprint.iacr.org/2025/922

NOTE: 上表中在 Remark 一栏中添加“⭐️”的表示是在本项目中新增的协议描述。

按承诺协议的分类

CommitmentsAlgebraSchemes
KZG10Paring Friendly ECC basedPST13(mKZG or Liba-PCS), Zeromorph, Gemini, HyperKZG, PH23-KZG, Mercury, Samaritan
Merkle TreeLinear code basedLigero, Virgo, Basefold, Deepfold, WHIR, PH23-fri, Zeromorph-fri, Gemini-fri, Ligerito, FRI-Binius
Pedersen CommitmentECC basedHyrax, Σ-Check
Ajtai CommitmentLattice basedGreyhound, Hyperwolf

所有的 MLE-PCS 协议都是从 Univariate PCS 扩展而来,或者直接在其基础上构建的协议。

对于一个单变量多项式 f(X)f(X)

f(X)=a0+a1X+a2X2++aN1XN1f(X) = a_0 + a_1 X + a_2 X^2 + \ldots + a_{N-1}X^{N-1}

用不同的方式来对 f(X)f(X) 进行承诺,对应着不同的 Univariate PCS。

KZG10

KZG10 多项式承诺需要 Trusted Setup 来产生一组具有内部代数结构的向量,

(G0,G1,,GN1,H0,H1)=(G,γG,γ2G,,γN1G,H,γH)(G_0, G_1, \ldots, G_{N-1}, H_0, H_1) = (G, \gamma G, \gamma^2 G, \ldots, \gamma^{N- 1} G, H, \gamma H)

这里 γ\gamma 是一个通过 Trusted Setup 产生的随机数,产生后不能泄漏。G,HG, H 分别为椭圆曲线 G1,G2\mathbb{G}_1, \mathbb{G}_2 上的生成元,并且它们之间存在一个双线性映射:e:G1×G2GTe : \mathbb{G}_ 1\times \mathbb{G}_2 \rightarrow \mathbb{G}_T

对多项式 f(X)f(X) 的承诺为:

Cf(X)=a0G0+a1G1++aN1GN1=a0G+a1γG++aN1γN1G=f(γ)G\begin{align} C_{f(X)} & = a_0 G_0 + a_1 G_1 + \ldots + a_{N - 1}G_{N - 1} \\ & = a_0 G + a_1 \gamma G + \ldots + a_{N-1} \gamma^{N - 1} G \\ & = f(\gamma) G \end{align}

承诺 Cf(X)C_{f(X)} 恰好为 f(γ)Gf(\gamma)G 。若要用 KZG10 来构造 PCS,例如构造一个 f(ζ)=yf(\zeta) = y 的打开证明,即要证明存在商多项式 q(X)q(X) 满足

f(X)=q(X)(Xζ)+yf(X) = q(X) \cdot (X - \zeta) + y

那么 Prover 可以提供关于 q(X)q(X) 的承诺 Cq(X)C_{q(X)} 来作为 f(ζ)=yf(\zeta) = y 的打开证明。根据承诺的加法同态映射关系以及双线性映射,Verifier 可以在 GT\mathbb{G}_T 上来验证整除关系:

e(Cf(X)yG,H)=?e(Cq(X),γHζH)e(C_{f(X)} - y \cdot G, H) \overset{?}{=} e(C_{q(X)} , \gamma H - \zeta H)

从上述描述可以看出,KZG10 承诺方案具有以下特点:

Merkle Tree

基于 Merkle Tree 的承诺不需要 Trusted Setup,其底层是基于 Linear Code 的性质。以 FRI 协议为例,若要对 f(X)f(X) 进行承诺,则 Prover 将 f(X)f(X) 的 Reed-Solomon Code 通过 Merkle Tree 的形式发送给 Verifier。详细来说,设 HFqH \subset \mathbb{F}_q 为一个阶为 2k(kN)2^k (k \in \mathbb{N}) 的乘法群,Reed-Solomon Code 的码率为 ρ\rho ,则 f(X)f(X) 的 Reed-Solomon Code 即为 f(X)f(X)HH 上的取值,组成一个向量

[f(x)xH][f(x)|_{x \in H}]

将该向量中的元素或其哈希值作为 Merkle Tree 的叶子节点,该 Merkle Tree 的根节点即为 f(X)f(X) 的承诺。

若要证明 f(ζ)=y(ζH)f(\zeta) =y (\zeta \notin H) ,以 FRI 协议来构造 PCS 为例[H22],即证明

f(0)(X)=f(X)yXζ+λXf(X)yXζf^{(0)}(X) =\frac{f(X) - y}{X - \zeta} + \lambda \cdot X \cdot \frac{f(X) - y}{X - \zeta}

次数小于 NN ,其中 λFq\lambda \leftarrow \mathbb{F}_q 为 Verifier 发送的随机数。Prover 先对 f(0)(X)f^{(0)}(X)HH 上进行 Reed-Solomon 编码,对编码后的向量用 Merkle Tree 的方式进行承诺,随后 Prover 和 Verifier 进行 FRI 的协议过程。在协议的 Query 阶段,若要打开 Merkle Tree 上的一些叶子节点,则 Prover 要发送相应的 Merkle Path 作为证明。

采用 Merkle Tree 作为承诺方案的协议具有以下特点:

Pedersen Commitment

Ajtai Commitment

Ajtai commitment 是一种基于格 lattice 的承诺方法,具有抗量子攻击的特性。假设需要承诺的向量为 f\vec{f} (在多项式承诺中,可以将多项式 f(X)f(X) 的系数视为向量 f\vec{f},这与 Pedersen commitment 类似), Ajtai commitment 首先选择一个 n×mn \times m-size 矩阵 GG (类似于 Pedersen commitment 中的 group element),通过计算 Gf=tG \vec{f} = \vec{t} 得到承诺结果 t\vec{t}。与 Pedersen Commitment 类似,Ajtai commitment 同样不需要 trusted setup。其最重要的区别在于:

为了提升效率,许多实现中采用多项式环来实现 Ajtai commitment(注意,这里的多项式环与多项式承诺中的多项式无关),即向量/矩阵的元素为多项式环中的元素。这种更通用的情形可以使 Ajtai commitment 承诺的安全性归约到 M-SIS/M-LWE 问题。

按 Evaluation 证明原理分类

根据协议实现方法的不同,可以将 MLE-PCS 分为以下几类:

PrincipleSchemes
QuotientingPST13(Libra-PCS), Zeromorph, Zeromorph-FRI
SumcheckBasefold, Deepfold, WHIR, Ligerito, FRI-Binius
Split-and-foldGemini, HyperKZG, Gemini-fri, Hyperwolf
Inner-productLigero, Hyrax, Σ-Check, PH23-kzg, Virgo-PCS, Mercury, Samaritan, GreyHound

Quotienting

MLE-PCS 要证明的是一个多元线性多项式 f~(X0,,Xn1)\tilde{f}(X_0, \ldots, X_{n - 1}) 在一个公开点 (u0,,un1)(u_0, \ldots, u_{n - 1}) 的值为 vv ,即证明 f~(u0,,un1)=v\tilde{f}(u_0, \ldots, u_{n - 1}) = v

根据论文 [PST13] 给出的关于 MLE 多项式的除法分解定理,可以得到

f~(X0,X1,,Xn1)f~(u0,u1,,un1)=q~n1(X0,X1,,Xn2)(Xn1un1)+q~n2(X0,X1,,Xn3)(Xn2un2)++q~1(X0)(X1u1)+q~0(X0u0)\begin{split} \tilde{f}(X_0, X_1, \ldots, X_{n-1}) - {\color{red}\tilde{f}(u_0, u_1, \ldots, u_{n-1})} & = \tilde{q}_{n-1}(X_0, X_1, \ldots, X_{n-2}) \cdot (X_{n-1} - u_{n-1}) \\ & + \tilde{q}_{n-2}(X_0, X_1, \ldots, X_{n-3}) \cdot (X_{n-2} - u_{n-2}) \\ & + \cdots \\ & + \tilde{q}_{1}(X_0) \cdot (X_{1} - u_{1}) \\ & + \tilde{q}_{0} \cdot (X_{0} - u_{0}) \\ \end{split}

若有 f~(u0,,un1)=v\tilde{f}(u_0, \ldots, u_{n - 1}) = v ,那么就有

f~(X0,X1,,Xn1)v=q~n1(X0,X1,,Xn2)(Xn1un1)+q~n2(X0,X1,,Xn3)(Xn2un2)++q~1(X0)(X1u1)+q~0(X0u0)\begin{split} \tilde{f}(X_0, X_1, \ldots, X_{n-1}) - {\color{red}v} & = \tilde{q}_{n-1}(X_0, X_1, \ldots, X_{n-2}) \cdot (X_{n-1} - u_{n-1}) \\ & + \tilde{q}_{n-2}(X_0, X_1, \ldots, X_{n-3}) \cdot (X_{n-2} - u_{n-2}) \\ & + \cdots \\ & + \tilde{q}_{1}(X_0) \cdot (X_{1} - u_{1}) \\ & + \tilde{q}_{0} \cdot (X_{0} - u_{0}) \\ \end{split}

此时证明 f~(u0,,un1)=v\tilde{f}(u_0, \ldots, u_{n - 1}) = v 就可以转换为证明 {q~i}0i<n\{\tilde{q}_i\}_{0\leq i<n} 的存在性,并满足上面的除法等式。

PST13[PST13, XZZPS19] 通过引入结构化的 SRS 来承诺商多项式 q~0,q~1,,q~n1\tilde{q}_0, \tilde{q}_1, \ldots, \tilde{q}_{n-1} ,Verifier 通过 ECC-Pairing 运算来验证上述除法分解的正确性。

Zeromorph [KT23] 协议的核心是给出了一个从多元线性多项式到一元多项式的映射, MLE 多项式在 Boolean Hypercube 上的 Evaluations 直接作为一元多项式的系数。将上述除法分解式中的多元线性多项式通过这种映射方式变为一元多项式,可以得到 Zeromorph 协议想证明的一个关键等式:

[[f~(X0,X1,,Xn1)]]nvΦn(X)=k=0n1(X2kΦnk1(X2k+1)ukΦnk(X2k))[[q~k(X0,X1,,Xk1)]]k\begin{split} [[\tilde{f}(X_0, X_1, \ldots, X_{n-1})]]_n - v\cdot\Phi_n(X) &=\sum_{k=0}^{n-1}\Big(X^{2^k}\cdot \Phi_{n-k-1}(X^{2^{k+1}}) - u_k\cdot\Phi_{n-k}(X^{2^k})\Big)\cdot [[\tilde{q}_k(X_0, X_1, \ldots, X_{k-1})]]_k \end{split}

其中 [[f~(X0,X1,,Xn1)]]n[[\tilde{f}(X_0, X_1, \ldots, X_{n-1})]]_n 表示 f~(X0,,Xn1)\tilde{f}(X_0, \ldots, X_{n - 1}) 在 boolean hypercube Bn={0,1}nB_n = \{0,1\}^n 上的值直接对应一个单变量多项式的系数,即

[[f~(X0,X1,,Xn1)]]n=i=02n1f~(bits(i))Xi[[\tilde{f}(X_0, X_1, \ldots, X_{n-1})]]_n = \sum_{i = 0}^{2^n - 1} \tilde{f}(\mathsf{bits}(i)) \cdot X^{i}

[[q~k(X0,X1,,Xk1)]]k[[\tilde{q}_k(X_0, X_1, \ldots, X_{k-1})]]_k 也按照上述同样的映射方法,将一个多元线性多项式映射成一个单变量多项式,即

[[q~k(X0,X1,,Xk1)]]k=i=02k1q~k(bits(i))Xi[[\tilde{q}_k(X_0, X_1, \ldots, X_{k-1})]]_k = \sum_{i = 0}^{2^k - 1} \tilde{q}_{k}(\mathsf{bits}(i)) \cdot X^i

Φn(X)\Phi_n(X)Φnk(X2k)\Phi_{n-k}(X^{2^k}) 也是一元多项式,一般地,Φk(Xh)\Phi_k(X^h) 表示如下的多项式

Φk(Xh)=1+Xh+X2h++X(2k1)h\Phi_k(X^h) = 1 + X^h + X^{2h} + \ldots + X^{(2^{k}-1)h}

因此 zeromorph 协议的关键等式两边都是一元多项式,此时 Verifier 可以随机选择一个点,Prover 只要证明这些一元多项式在该随机点处满足上面的等式即可,也就是可以用 univariate-PCS 来证明上式成立。因此 zeromorph 协议可以选择对接不同的 univariate-PCS ,如 KZG10 或者 FRI-PCS。

Inner-product

Multilinear Polynomial 的证明 f~(u0,,un1)=v\tilde{f}(u_0, \ldots, u_{n - 1}) = v ,可以转化为下面的 Inner-product 形式:

f,j=0n1(1,ui)=v\langle \vec{f}, \otimes_{j=0}^{n - 1}(1, u_i)\rangle = v

即证明向量 f\vec{f} 和 向量 j=0n1(1,ui)\otimes_{j=0}^{n - 1}(1, u_i) 的内积为 vv 。通过这种内积证明的方式来构造 MLE-PCS 的协议有很多,有 Virgo[ZXZS19], Hyrax[WTSTW16],PH23-PCS[PH23], Mercury[EG25] 以及 Samaritan[GPS25]。

Virgo-PCS[ZXZS19] 是以 MLE 多项式的 Coefficients Form 描述的,证明 f~(u0,,un1)=v\tilde{f}(u_0, \ldots, u_{n - 1}) = v 即证明内积

f,j=0n1(1,ui)=v\langle \vec{f}, \otimes_{j=0}^{n - 1}(1, u_i)\rangle = v

Virgo-PCS 借助 Univariate Sumcheck 来证明这个内积。Univariate Sumcheck 中,除了证明一元多项式的约束成立,还需要证明一个一元多项式的次数小于某个值,这一部分证明借助 FRI 协议来完成。

在 Univariate Sumcheck 中,Verifier 要验证一个关于一元多项式的约束成立,需要计算由 j=0n1(1,ui)\otimes_{j=0}^{n - 1}(1, u_i) 组成的向量构造的多项式 u(X)u(X) 在一点的值,但这需要 O(N)O(N) 的计算量。Virgo 利用 GKR 协议,将这部分计算代理给 Prover,Verifier 整体只需要 O(log2(N))O(\log^2(N)) 的计算量就可以完成验证。

PH23-PCS[PH23] 协议描述的是多元线性多项式的 Evaluations Form,证明 f~(u0,,un1)=v\tilde{f}(u_0, \ldots, u_{n - 1}) = v 即证明

i=02n1f~(bits(i))eq~(bits(i),(u0,,un1))=v\sum_{i = 0}^{2^n - 1} \tilde{f}(\mathsf{bits}(i)) \cdot \tilde{eq}(\mathsf{bits}(i), (u_0,\ldots,u_{n-1})) = v

令向量 a=(f~(bits(0)),,f~(bits(2n1)))\vec{a} = (\tilde{f}(\mathsf{bits}(0)), \ldots, \tilde{f}(\mathsf{bits}(2^n - 1))) ,向量 c\vec{c} 的第 ii 个分量为 eq~(bits(i),(u0,,un1))\tilde{eq}(\mathsf{bits}(i), (u_0,\ldots,u_{n-1})) ,则上面的求和式子可以用内积的视角来看待,

a,c=v\langle \vec{a}, \vec{c} \rangle = v

PH23-PCS 证明协议就分为两部分:

(1) 证明向量 c\vec{c} 的分量确实是 eq~(bits(i),(u0,,un1))\tilde{eq}(\mathsf{bits}(i), (u_0,\ldots,u_{n-1}))

(2) 证明内积 a,c=v\langle \vec{a}, \vec{c} \rangle = v

对于第 (1) 部分的证明,利用 eq~(bits(i),(u0,,un1))\tilde{eq}(\mathsf{bits}(i), (u_0,\ldots,u_{n-1})) 的结构,构造一元多项式 c(X)c(X) ,用 n+1n + 1 个一元多项式的约束进行证明。

对于第 (2) 部分的证明,这是一个内积证明,可以用 Grand Sum 或者 Univariate Sumcheck 的方法来进行证明。文章 The Missing Protocol PH23-PCS (Part 1) 中给出了 PH23-PCS 用 Grand Sum 做内积证明的完整协议。用 Grand Sum 的方法证明内积可以转换为证明 3 个一元多项式的约束成立。

这样 PH23-PCS 两部分的证明就能转换为证明 n+4n + 4 个一元多项式的约束成立,进而可以用一元多项式的 PCS 来证明,因此 PH23-PCS 可以对接 KZG10 和 FRI-PCS。

Hyrax [WTSTW16] 协议直接将 MLE 多项式 f~(u0,u1,u2,u3)\tilde{f}(u_0, u_1, u_2, u_3) 看作是一个向量矩阵乘法等式,即

f~(u0,u1,u2,u3)=[1u2u3u2u3][c0c1c2c3c4c5c6c7c8c9c10c11c12c13c14c15][1u0u1u0u1]\tilde{f}(u_0, u_1, u_2, u_3) = \begin{bmatrix} 1 & u_2 & u_3 & u_2u_3 \\ \end{bmatrix} \begin{bmatrix} c_0 & c_1 & c_2 & c_3 \\ c_4 & c_5 & c_6 & c_7 \\ c_8 & c_9 & c_{10} & c_{11} \\ c_{12} & c_{13} & c_{14} & c_{15} \end{bmatrix} \begin{bmatrix} 1 \\ u_0 \\ u_1 \\ u_0u_1 \\ \end{bmatrix}

然后将矩阵按行进行承诺的计算,Hyrax 采用的是 Pedersen Commitment,具有加法的同态性,因此可以将承诺向量与 (1,u2,u3,u2u3)(1, u_2, u_3, u_2u_3) 先进行内积运算,得到一个单个的承诺,然后再证明这个承诺对应的向量与 (1,u0,u1,u0u1)(1, u_0, u_1, u_0u_1) 的内积等于 vv 。最后这个内积证明采用的是 Bulletproofs-IPA 协议,总体上 Verifier 的计算量为 ONO\sqrt{N},而 Proof size 为 O(log(N))O(\log(N))

Mercury [EG25] 协议和 Samaritan [GPS25] 协议的思路非常类似,它们都在 Hyrax 上述的矩阵乘法等式上进行改进。与 Hyrax 不同的是,Mercury 和 Samaritan 只需要对向量整体进行承诺计算,而不是按行产生 N\sqrt{N} 个承诺。然后将整体的 Evaluation 证明转换为两个内积证明。并且,Mercury 将两个内积证明 Batch 到一个内积证明,从而进一步优化了协议。

Sumcheck 方式

f~(u0,,un1)=v\tilde{f}(u_0, \ldots, u_{n - 1}) = v 代入多元线性多项式的点值式,可以转换为证明在 Bn={0,1}nB_n = \{0,1\}^n 上的求和式

b={0,1}nf~(b)eq~(b,u)=v\sum_{\vec{b} = \{0,1\}^n}\tilde{f}(\vec{b}) \cdot \tilde{eq}(\vec{b}, \vec{u}) = v

那么我们可以证明上面的求和式成立,从而证明 Multilinear Polynomial 的 Evaluation 正确性。采用 Sumcheck 的问题在于:在 Sumcheck 协议的最后一步 Verifier 需要得到 f~\tilde{f} 在一个随机点处的值来进行最后的验证,从而完成整个 Sumcheck 协议。Basefold [ZCF23] 协议的重要贡献是发现如果同步对 f~\tilde{f} 对应的一元多项式使用 FRI 协议,并且在每一轮折叠时采用和 Sumcheck 协议一样的随机数,那么当折叠到最后一步,得到的常数正是 Sumcheck 协议最后一步想要 f~\tilde{f} 在随机点处的值。

h(rn1)=?f~(r0,r1,,rn1)eq~((r0,r1,,rn1),u)h(r_{n-1}) \overset{?}{=} \tilde{f}(r_0, r_1, \ldots, r_{n-1})\cdot \tilde{eq}((r_0, r_1, \ldots, r_{n-1}), \vec{u})

Deepfold 协议,WHIR 协议也是延续了采用 Sumcheck 的思想,不同的地方在于 Deepfold 采用了 DEEP-FRI 中的想法,Prover 提前确定多项式在某个 Out-of-domain 随机点的求值,作为某种形式的 Commitment,确保 Prover 在 List-decoding Regime 中也能确保始终承诺的是同一个多项式。而这个随机 Evaluation 也可以同样采用 Sumcheck 协议来证明。具体地说,在每一轮的 Basefold 协议交互中,Verifier 再额外随机选择一个 ziFz_i\leftarrow \mathbb{F},然后 Prover 发送 yiy_i 并证明其是 f^(i)(zi)\hat{f}^{(i)}(z_i) 的值。因为 f^(i)\hat{f}^{(i)}f~(i)\tilde{f}^{(i)} 存在同构映射,因此 yiy_i 也是下面 MLE 多项式的运算值:

yi=f~(i)(zi,zi2,,zi2ni1)y_i = \tilde{f}^{(i)}(z_i, z_i^2, \cdots, z_i^{2^{n-i-1}})

因此,Prover 在后续的协议交互中,同样采用一个新的 Sumcheck 协议来证明 f~(i)(zi,zi2,,zi2ni1)\tilde{f}^{(i)}(z_i, z_i^2, \cdots, z_i^{2^{n-i-1}}) 的正确性。

WHIR 在 Deepfold 协议的基础上,将 Out-of-domain 和 In-domain 的随机查询都合并入 Sumcheck,使得协议达到了一个更优的状态。同样,基于 Basefold 的Ligerito 也利用了 Sumcheck 协议,在每一个 Round,Verifier 都会抽样一些 Oracle 中的点,然后这些点的编码正确性本应该由 Verifier 计算,由于这些计算是一个内积,于是 Verifier 可以利用 Sumcheck 协议将其代理给 Prover ,并且这个 Sumcheck 可以和当前轮 Basefold 协议部分的 Sumcheck 协议合并,从而大大优化协议的后续流程。

Split-and-fold (Recursive)

这种证明思路非常类似 FRI 协议,即将一个较大的多项式,反复进行拆分折叠(Split-and-fold),最后 Gemini [BCH+22] 协议和 HyperKZG 都是采用 split-and-fold 的思想来证明,它们的不同点在于 Gemini 中的多元线性多项式是 Coefficients Form,而 hyperKZG 中采用 Evaluations Form,在协议中只需要更换折叠的方式即可,不需要将点值式用 FFT 转换为系数式。

以 Gemini 协议为例,将 MLE 多项式的系数式

f~(X0,X1,,Xn1)=i=02n1fiX0i0X1i1Xn1in1\tilde{f}(X_0, X_1, \ldots, X_{n-1}) = \sum_{i=0}^{2^n-1} f_i \cdot X_0^{i_0}X_1^{i_1} \cdots X_{n - 1}^{i_{n - 1}}

中的求和形式看作是一个向量和一个 tensor product 结构的内积,即

f~(X0,X1,,Xn1)=f,i=0n1(1,Xi)\tilde{f}(X_0, X_1, \ldots, X_{n-1}) = \langle \vec{f}, \otimes_{i=0}^{n - 1}(1, X_i)\rangle

n=3n = 3 为例,系数向量

f=(f0,f1,f2,,f7)\vec{f} = (f_0,f_1, f_2, \ldots, f_7)

tensor product 结构也可以看作是一个向量,为

i=02(1,Xi)=(1,X0,X1,X0X1,X2,X0X2,X1X2,X0X1X2)\otimes_{i=0}^{2}(1, X_i) = (1, X_0, X_1, X_0X_1, X_2, X_0X_2, X_1X_2, X_0X_1X_2)

因此要证明 f~(u0,,un1)=v\tilde{f}(u_0, \ldots, u_{n - 1}) = v ,即证明

f,j=0n1(1,ui)=v\langle \vec{f}, \otimes_{j=0}^{n - 1}(1, u_i)\rangle = v

而上面的内积形式可以进行 spilt-and-fold ,即

f,j=0n1(1,ui)=feven,j=1n1(1,ui)+u0fodd,j=1n1(1,ui)\langle \vec{f}, \otimes_{j=0}^{n - 1}(1, u_i)\rangle = \langle \vec{f}_{even}, \otimes_{j=1}^{n - 1}(1, u_i)\rangle + u_0 \langle \vec{f}_{odd}, \otimes_{j=1}^{n - 1}(1, u_i)\rangle

feven\vec{f}_{even} 表示系数向量 f\vec{f} 中的偶数项组成的向量,fodd\vec{f}_{odd} 表示 f\vec{f} 中的奇数项组成的向量。依然以 n=3n = 3 为例,可以得到

f,j=0n1(1,ui)=f0+f1u0+f2u1+f3u0u1+f4u2+f5u0u2+f6u1u2+f7u0u1u2=(f0+f2u1+f4u2+f6u1u2)+u0(f1+f3u1+f5u2+f7u1u2)=feven,j=1n1(1,ui)+u0fodd,j=1n1(1,ui)\begin{align} \langle \vec{f}, \otimes_{j=0}^{n - 1}(1, u_i)\rangle & = f_0 + f_1 u_0 + f_2 u_1 + f_3 u_0 u_1 + f_4 u_2 + f_5 u_0 u_2 + f_6 u_1 u_2 + f_7 u_0u_1u_2 \\ & = (f_0 + f_2 u_1 + f_4 u_2 + f_6 u_1u_2) + u_0 \cdot (f_1 + f_3 u_1 + f_5 u_2 + f_7 u_1u_2) \\ & = \langle \vec{f}_{even}, \otimes_{j=1}^{n - 1}(1, u_i)\rangle + u_0 \langle \vec{f}_{odd}, \otimes_{j=1}^{n - 1}(1, u_i)\rangle \end{align}

这里 split-and-fold 的含义是,先将 8 项求和 split 成两部分,即偶项 f0+f2u1+f4u2+f6u1u2f_0 + f_2 u_1 + f_4 u_2 + f_6 u_1u_2 和奇项 f1+f3u1+f5u2+f7u1u2f_1 + f_3 u_1 + f_5 u_2 + f_7 u_1u_2 ,再用 u0u_0 将这两部分 fold 成一部分,fold 完的这一部分还可以继续接着进行 split-and-fold 的过程。这里 split-and-fold 的思想和 FRI 以及 sumcheck 是一样的。

我们将 MLE 多项式的系数式直接转换为一元多项式的系数,例如 f~(X0,,Xn1)\tilde{f}(X_0, \ldots, X_{n - 1}) 对应的一元多项式为

f(X)=i=02n1fiXif(X) = \sum_{i=0}^{2^n-1} f_i \cdot X^i

因此上面的 spilt-and-fold 技巧可以直接在 f(X)f(X) 上应用,其过程和 FRI 协议一致,不过每次 fold 的系数不是随机数,而是 uiu_i ,这样最后就会变成一个常数多项式,结果应该等于 f~\tilde{f} 在点 (u0,,un1)(u_0, \ldots, u_{n - 1}) 处的取值,即等于 vv 。在这个过程中 verifier 需要验证每次 fold 的正确性,verifier 可以随机挑战一些点来进行验证,这就可以通过 univariate-PCS 来实现,可以接 KZG10 或者 FRI。

这些协议通过上述方法将 MLE-PCS 转换为 univariate-PCS ,根据所采取的 univariate-PCS 的不同,又可以分为三类:

综合上述两种分类方法,该项目涉及的协议如下:

对于基于 KZG10 的协议,通过详细计算协议中的有限域乘法操作,求逆操作,椭圆曲线上的 msm 操作,proof 大小等,对比了 PH23-PCS, zeromorph, gemini 协议的具体运行效率,这一部分将在下文详细说明。

对于基于 FRI 的协议,详细统计了 basefold 协议与 zeromorph-fri 协议中的哈希计算、Merkle 树相关运算,有限域运算等,得出了在 Prover 复杂度,Verifier 复杂度以及 Proof Size 这三个维度上,basefold 协议都要优于 zeromorph-fri 协议。另外,从 Verifier query 复杂度的角度出发,对比了 Basefold,Deepfold 与 WHIR 这三个协议。这一部分将在下文详细阐述。

按 MLE 表示形式分类

MLE-PCS 协议的上层是 Multilinear PIOP 协议。而这类常见的 PIOP 通常是 Sumcheck 或者 GKR 协议。在通常的实现中,Multilinear Polynomial 会以 Evaluations Form 的形式表示。那么在 MLE-PCS 协议中,并不是所有的协议都直接对 Evaluations Form 进行证明。如果一个 MLE-PCS 协议只能对 Multilinear Polynomial 协议的 Coefficients Form 进行证明,或者进行承诺,那么 Prover 需要额外进行 Algebraic FFT(NTT)算法计算出 Multilinear Polynomial 的 Coefficients Form,这需要 O(NlogN)O(N\log{N}) 的计算时间复杂度。这有可能导致 Prover 做不到线性时间的工作量。

尽管一些 MLE-PCS 论文中仅描述了一种形式,比如 Coefficients Form。但是协议本身也可以支持 Evaluations Form,这在工程实践中,可以根据更进一步的性能分析,而选择适合的协议变种。下面我们列出本项目所覆盖到的 MLE-PCS 对 Multilinear Polynomial 的两种表示形式的支持情况:

SchemeCoefficientsEvaluations
PST13[PST13] ✅✅ [XZZPS19]
Zeromorph✅ [KT23]
Gemini[BCH+22]
hyperKZG✅ HyperKZG
PH23-KZG✅ [PH23]
Mercury✔️✅ [EG25]
Samaritan✔️✅ [GPS25]
Virgo✅ [ZXZS19]
Hyrax✅ [WTSTW16]
Basefold✅ [ZCF23]✅ [H24]
Deepfold✅ [GLHQTZ24]
Ligerito✅ [NA25]
WHIR✅ [ACFY24b]
FRI-Binius✔️✅ [DP24]
Σ-Check✅ [GQZGX24]
Greyhound✅ [NS24]
Hyperwolf✅ [ZGX25]

MLE-PCS 的安全性分析

对于一个 MLE-PCS 协议,我们不仅关注于协议是如何构造的,也关心协议的安全性证明,包括 Completeness、Soundness、Knowledge soundness 以及 Zero-knowledge 等性质。对于基于 KZG10 和基于 FRI 的 MLE-PCS,它们的安全假设有很大的不同。

AssumptionAlgebraSchemes
KZG10(BSDH, AGM, )ECC basedPST13, Zeromorph, Gemini, HyperKZG, PH23-KZG, Mercury, Samaritan
Random Oracle (Hash)Linear code basedVirgo, PH23-fri, zeromorph-fri, Gemini-fri, Basefold, Deepfold, WHIR, FRI-Binius
EC Discrete LogECC basedHyrax,∑-check
M-SISLattice basedGreyhound, Hyperwolf

基于 KZG10 的安全性

对于基于 [KZG10] 的 MLE-PCS,我们重点关注其 Knowledge Soundness 证明(也称作 Extractability)。

在 [KZG10] 论文中,作者要求协议满足 Evaluation Binding 性质,该性质只保证了证明者没法伪造证明:使得多项式 f(X)f(X) 在同一个点 aa 上打开为两个不同的值 v1v2v_1 \neq v_2

然而,当 [KZG10] 被用作 SNARK 设计中,仅满足 Evaluation Binding 性质无法满足证明系统 Knowledge Soundness 的安全要求。

因此,研究者们对 [KZG10] 提出了更强的安全性要求,即 “可提取性“ (Extractability): 对于任何代数敌手 Aalg\mathcal{A}_{alg},如果它能够输出一个合法的多项式求值证明,那么一定存在另一个高效的算法 Balg\mathcal{B}_{alg},能够提取出多项式承诺 CC 的秘密值 f(X)f(X),满足 f(z)=vf(z) = v

对于 [KZG10] 的可提取性证明,我们通常关心两点:

包括 [MBKM19],[GWC19],[CHM+20] 在内的多个基于 [KZG10] 的工作,都先后对可提取性的证明问题进行了讨论。我们总结如下:

papersecurity modelassumption separationassumption
[MBKM19], [GWC19]AGM+ROMFalsifiableq-DLOG
[CHM+20]ROMNon-FalsifiablePKE
[HPS23]AGMOS+ROMFalsifiableFPR+TOFR
[LPS24]ROMFalsifiableARSDH

本项目以博客文章的形式深入研究了KZG协议的安全性证明,包括

除此之外,[HPS23] 提出了一种改进的安全模型称作 AGMOS(Algebraic Group Model with Oblivious Sampling)。作为 AGM 的一种更加现实的变体,AGMOS 赋予对手在不知道离散对数的情况下模糊采样群元素的额外能力。

此外,[HPS23] 中还指出在实际协议设计中存在着两种不同的 KZG 可提取性定义:

其中,后者虽然能在 AGM 模型下被证明安全,但会归约到一种在标准模型下不安全的 spurious knowledge assumption。

除了可提取性,我们通常还要求 [KZG10] 满足 hiding 性质,作为构造具有 Zero-knowledge 性质的 zkSNARK 或者其它安全协议的重要组件。 本项目对该方面研究也有所讨论,包括

Understanding Hiding KZG10:这篇文章中详细介绍了两种为 KZG10 实现 Hiding 性质的方法,一种方案出自 [KT23],其主要的技术是多元多项式承诺一个简化版本的 [PST13]。第二种方案出自 [CHM+20],其主要的技术是对原始 KZG 协议论文 [KZG10] 的改进。

基于 Linear Code 的安全性

对于基于 Linear Code 的 MLE-PCS,我们重点关注其 Soundness 证明。FRI 协议[BBHR18]本身是一个针对 Reed-Solomon (RS) 编码的 IOPP (Interactive Oracle Proof of Proximity, IOPP) 协议,其安全性与 RS 编码的性质以及一些编码理论紧密相关。我们深入研究了 FRI 系列协议的 soundness 证明。

对于在有限域 F\mathbb{F} 中的求值 (evaluation) 集合 SS ,假设 SS 中的元素个数为 NN ,给定一个码率参数 ρ(0,1]\rho \in (0,1] ,编码 RS[F,S,ρ]\text{RS}[\mathbb{F},S,\rho] 表示的是所有函数 f:SFf: S \rightarrow \mathbb{F} 的集合,其中 ff 是次数 d<ρNd < \rho N 的多项式的求值 (evaluations),即存在次数 d<ρNd < \rho N 的多项式 f^\hat{f} 使得 fff^\hat{f}SS 上的值是一致的。

FRI 协议解决的是 RS proximity problem:假设我们能获得关于函数 f:SFf: S \rightarrow \mathbb{F} 的 oracle ,需要 Verifier 用较少的查询复杂度,同时有很高的把握能辨别出 ff 属于下面哪一种情况:

  1. fRS[F,S,ρ]f \in \text{RS}[\mathbb{F},S,\rho]
  2. Δ(f,RS[F,S,ρ])>δ\Delta(f, \text{RS}[\mathbb{F},S,\rho]) > \delta

也就是要么 ff 是 RS 编码 RS[F,S,ρ]\text{RS}[\mathbb{F},S,\rho] 中的一个码字,要么距离所有 RS[F,S,ρ]\text{RS}[\mathbb{F},S,\rho] 中的码字的相对 Hamming 距离都大于接近参数 δ\delta

[BBHR18] 论文中给出了 FRI 协议的 soundness 证明,对于 δ<δ0\delta < \delta_0 ,其中 δ013ρ4\delta_0 \approx \frac{1 - 3 \rho}{4} ,对于任意作恶的 Prover PP^* ,Verifier 拒绝 PP^* 的概率大约为 δO(1)F\delta - \frac{O(1)}{|\mathbb{F}|}

通过分析知道,在相同的安全性参数下,δ0\delta_0 能取到的值越大,Verifier 在 Query 阶段需要查询的次数就越少,这样 FRI 协议的证明大小以及 Verifier 的计算复杂度都会降低。在 [BBHR18] 论文之后,出现了很多理论研究工作来提高 FRI 协议中的 δ0\delta_0

paperδ0\delta_0
[BBHR18]FRIδ013ρ4\delta_0 \approx \frac{1 - 3\rho}{4}
[BKS18]Worst-case ...δ01ρ14\delta_0 \approx 1 - \rho^{\frac{1}{4}}
[BGKS20]DEEP-FRIδ01ρ13\delta_0 \approx 1 - \rho^{\frac{1}{3}} , tight(!)
[BCIKS20]Proximity Gapsδ01ρ12\delta_0 \approx 1 - \rho^{\frac{1}{2}}

本项目以博客文章的形式深入研究了 FRI 协议的安全性证明,包括:

在论文 [ACFY24a] STIR 中提出了对 FRI 协议的一个改进,其思想是降低在 FRI 协议中每一次 kk-折的码率,达到更小的查询复杂度。在博客文章 STIR: Improving Rate to Reduce Query Complexity 中,我们详细介绍了 FRI 协议与 STIR 协议的区别,介绍了一次迭代的协议流程,并对一次迭代的 soundness 进行了分析。

尽管 Basefold 协议[ZCF23]适用的是论文中提到的 Random Foldable Code,但其依然适用于 Reed Solomon 编码,因此可以理解为 Basefold 协议结合了 sumcheck 和 FRI 协议。在 Basefold 原论文 [ZCF23] 中,其 soundness 只证明到 δ0\delta_0 最大能取到 (1ρ)/2(1 - \rho)/2 ,随后 Ulrich Haböck 在 [H24] 中证明了 Basefold 协议对于 Reed Solomon 能达到 Johnson bound 1ρ1 - \sqrt{\rho} ,Hadas Zeilberger 在 Khatam [Z24] 论文中证明了 Basefold 协议对于一般的 linear code 能达到 1ρ131 - \rho^{\frac{1}{3}}

关于 Basefold 协议相关的笔记文章有:

Deepfold 协议和 WHIR 协议采用了 Basefold 协议同样的思想,结合 sumcheck 协议来构造 MLE-PCS,Deepfold 协议结合了 sumcheck 协议与 DEEP-FRI,关于该协议的详细介绍可见博客文章 Note on DeepFold: Protocol Overview 。WHIR 协议则结合了 sumcheck 协议和 STIR 协议,在博客文章 Note on WHIR: Reed-Solomon Proximity Testing with Super-Fast Verification 中详细介绍了 WHIR 协议。

Basefold 协议、Deepfold 协议和 WHIR 协议有着类似的思路,我们在博客文章 BaseFold vs DeepFold vs WHIR 中对比了这三个协议的构造,并通过分析其 soundness 证明,对比了这三个协议 Verifier 的查询次数。

基于 M-SIS 的安全性

对于基于 lattice 的多项式承诺方案,我们重点关注其knowledge soundness的证明。

与基于离散对数的方案不同,lattice-based cryptography 中的 relation 通常包含额外的norm constraint,以满足 lattice 假设的安全需求。因此,在knowledge soundness的证明中,我们不仅需要证明提取出的 witness 满足如 IPA 等常规约束条件,还必须进一步证明该 witness 范数足够小,从而确保其能够与 Ajtai 承诺绑定。

Greyhound 协议的安全性建立在 infinite norm 变种的 M-SIS 问题之上。在 knowledge soundness 的证明中,Greyhound证明提取出的 witness pair (cˉ,wˉ)(\bar{c}, \bar{w}) 满足一个 relaxed relation。这个 relaxed relation 在其他常规约束上与 original relation 相同,仅在 norm constraint 和 binding constraint 上有所不同。

对于 binding 约束,relaxed relation 要求 cˉAwˉ=cˉcm\bar{c} A \bar{w} = \bar{c} \mathsf{cm},其中 cm\mathsf{cm} 是 witness 的 commitment,也是公共参数。对于 norm constraint,relaxed relation 要求 cˉwˉ2βˉ| \bar{c} \bar{w} | \le 2\bar{\beta},而 original relation 中要求的是 wβ| w | \le \beta

通过限制 M-SIS 问题在范数为 min{2βˉ, 8Tβˉ}\min\{2\bar{\beta},\ 8T\bar{\beta}\}时仍然成立,该证明可以保证提取出的 witness 既能与原始 commitment cm\mathsf{cm}绑定,又能满足所有其他常规约束。其中 TT 表示 cˉ\bar{c} 的 operation norm。

Hyperwolf 的安全性建立在 2\ell_2-norm 版本的 M-SIS 问题之上。在证明 norm constraint 时,协议采用了与 Labrador 类似的技术路线:通过证明 witness 在某个随机投影下的范数较小,从而以高概率推断出原始向量的范数也在可接受范围内。

为了证明向量 aZn\vec{a} \in \mathbb{Z}^n2\ell_2 范数较小,同时避免泄露其完整信息,我们可以利用 Johnson–Lindenstrauss (JL) 引理。该引理的核心思想是,高维向量在经过随机线性投影后,其 2\ell_2 范数能够在较高概率下被近似保留。

具体做法如下:Verifier 随机生成一个投影矩阵 ΠZ256×n\Pi \in \mathbb{Z}^{256 \times n},其中每个元素独立采样自集合 1,0,1{-1, 0, 1},取值概率分别为 Pr[1]=Pr[1]=1/4\Pr[-1] = \Pr[1] = 1/4Pr[0]=1/2\Pr[0] = 1/2。Prover 计算并发送投影向量 p=Πa\vec{p} = \Pi \vec{a}。Verifier 随后检查 p\vec{p} 的范数,从而估计原始向量 a\vec{a} 的范数是否满足约束。JL Lemma的具体内容如下:

Modular Johnson–Lindenstrauss Variant:qNq \in \mathbb{N},令 D\mathcal{D} 为定义在 0,±1{0, \pm 1} 上的分布,满足 D(1)=D(1)=1/4\mathcal{D}(1) = \mathcal{D}(-1) = 1/4D(0)=1/2\mathcal{D}(0) = 1/2。对于任意 aZqn\vec{a} \in \mathbb{Z}_q^n,若其满足 ab|\vec{a}| \le bbq/125b \le q/125,则有:

PrΠD256×n[Πamodq2<30b2]2128.\begin{split} \Pr_{\Pi \leftarrow \mathcal{D}^{256\times n}}[\|\Pi\vec{a}\mod q\|^2< 30b^2] \lessapprox 2^{-128}. \nonumber \end{split}

根据该定理,证明 short norm 问题可以被归约为证明某个投影向量 p\vec{p} 是 well-formed(即满足 IPA 关系)的任务。这种方式既能以高概率保证所提取的 witness 满足 norm constraint,同时只引入了一个常数级别的 slack,在效率与安全性之间取得了良好平衡。

发现

在深入研究这些 MLE-PCS 的底层原理的过程中,我们发现了一些协议还有优化的空间,并提出了一些新的实现方式。下面列举我们的主要创新点。

∑-Check 协议

The compressed Σ-protocol theory AC20, ACF21 offers a general approach for efficiently proving polynomial relations. In the context of PCS, it can be either (1) used directly to prove PCS evaluations by expressing them as a relation {(f;F,z,v):Com(f)=F,f(z)=v}\{(\vec{f}; F, \vec{z}, v): \mathsf{Com}(\vec{f}) = F, f(\vec{z}) = v\}, where f\vec{f} represents the coefficients of the polynomial ff; or (2) applied as a drop-in replacement for IPA in Bulletproofs-based PCS systems like Hyrax. AC20 and ACF21 demonstrate that this can be achieved through linearization based on arithmetic circuits, followed by the application of Bulletproofs compression, resulting in a Bulletproofs-based PCS with a transparent setup.

Our recent contribution, Σ-Check, advances this research field by introducing an efficient sumcheck-based method for proving kk distinct polynomial evaluations, each with nn variables, at a cost of O(n+logk)O(n+\log k)-size proofs. This approach eliminates the need for circuit-based linearization and proves to be more efficient when handling kk polynomials, which previously required O(n+k)O(n+k) cost in AC20 and ACF21. A prototype implementation is available at GitHub.

Hyperwolf 协议

Greyhound 协议中,多项式求值过程可以被表达为长度为 NN的系数向量 f\vec{f} 与两个长度为 n=Nn = \sqrt{N}的向量 a\vec{a}b\vec{b} 的tensor product的内积形式,即 v=f,abv = \langle \vec{f}, \vec{a} \otimes \vec{b} \rangle。换一种方式理解,该过程相当于将 f\vec{f} 重构为一个大小为 n×nn \times n 的矩阵 FF,然后依次与 a\vec{a}b\vec{b} 进行矩阵乘法。具体地, f\vec{f} 可以看作是由 FF 的各行按行主顺序拼接得到的。

通过将多项式求值过程重写为上述结构,Greyhound 协议实现了将proof size和verification time下降到sublinear级别,同时保持prover的计算成本为linear。这种结构上的优化,使得协议在保证安全性的同时,兼顾了效率和实用性。

Hyperwolf协议是对Greyhoud协议的优化,其核心思想是将原本的二维结构推广到 kk 维(k2k \ge 2

具体地,它将一维的系数向量 f\vec{f} 解析为一个 kk 维的hypercube [F](k)[F]^{(k)},其维度为 b×b××bb \times b \times \cdots \times b(共 kk 个维度),满足 bk=Nb^k = N。多项式的求值过程可视为该 hypercube 依次与 kk 个辅助向量进行张量方向上的矩阵乘法的过程。基于这一结构,我们设计了一个包含 kk 轮交互的证明系统,每一轮的 proof size 和验证时间均为 O(b)O(b),因此整体的 proof size 和 verification time 为 O(kb)=O(kN1/k)O(kb) = O(kN^{1/k})。当取 k=logNk = \log N 时,系统的总复杂度可优化至 O(logN)O(\log N),显著提升了性能。

优化 Zeromorph 协议

在 zeromorph 协议中,需要证明 nn 个商多项式 qi(X)=[[q~i]]i(0i<n)q_i(X) = [[\tilde{q}_i]]_i (0 \le i < n) 的次数小于 2i2^i,zeromorph 论文 [KT23] Section 6 中将多个 Degree Bound 证明聚合在一起进行证明,关于这部分协议的详细描述可见 Optimized Protocol,不过在这个协议中 Verifier 需要在椭圆曲线 G2\mathbb{G}_2 上进行两次运算,这对于 verifier 来说是很昂贵的操作。

我们使用了另一种证明 Degree Bound 的方法,避免了 Verifier 在椭圆曲线 G2\mathbb{G}_2 上的操作,带来的代价是增加了一点 Verifier 在椭圆曲线 G1\mathbb{G}_1 上的计算量以及在证明中增加了一个椭圆曲线 G1\mathbb{G}_1 上的点和一个有限域上的值,在对 Verifier Cost 要求高的场景下,这是可以接受的。该协议的详细描述见 Zeromorph-PCS (Part II)

优化 Gemini 协议

在 gemini 协议中,需要 Prover 计算 nn 个多项式 h0(X),,hn1(X)h_0(X), \ldots, h_{n - 1}(X) 在随机点 β,β,β2\beta, -\beta, \beta^2 处的值,并发送给 Verifier ,让 Verifier 验证 hi+1(X2)h_{i + 1}(X^2)hi(X)h_{i}(X)hi(X)h_i(-X) 之间存在折叠的关系,关于这部分协议描述可见 Gemini-PCS (Part I)

我们发现了两种对 gemini 协议进行优化的方式。

优化方法一:Prover 只需要发送 h0(β2)h_0(\beta^2) 以及 h0(X),,hn1(X)h_0(X), \ldots, h_{n - 1}(X) 在随机点 β,β\beta, -\beta 处的值,用随机数将 h0(X)h_0(X) 以及 h1(X),,hn1(X)h_1(X), \ldots, h_{n - 1}(X) 聚合成一个多项式,一次证明这些多项式在 β,β,β2\beta, -\beta, \beta^2 处的值正确,这样可以降低证明大小,减少了 n1n - 1 个有限域上的值,具体协议描述见 Gemini-PCS (Part III)

优化方法二:另外一种优化方法是采用 FRI 协议在 Query 阶段选取点的思路,对 h0(X)h_0(X) 挑战 X=βX = \beta 求值,进而对折叠后的多项式 h1(X)h_1(X) 挑战 X=β2X= \beta^2 ,依次类推,直到 hn1(β2n1)h_{n - 1}(\beta^{2^{n-1}}) 。这样做的好处是,每一次 hi(X)h_{i}(X) 的打开点可以在验证 hi+1(X)h_{i+1}(X) 的折叠时复用,从而在优化方法一的基础上又可以多节省 nn 个打开点。相比优化方法一,这样做的代价是增加了一些 Prover 和 Verifier 的计算量,但减少了证明大小。具体协议描述见 Gemini-PCS (Part IV)

优化 PH23 协议

在原始论文 [PH23],作者给出了一个基于内积的 MLE-PCS 协议。我们通过按照原始论文提供的思路,设计的协议其证明尺寸为 O(logN)O(\log{N})。PH23 协议的核心思想是证明下面的内积:

f~(X0,X1,,Xn1)=b{0,1}na(b)eq~(b,u)\tilde{f}(X_0,X_1,\ldots,X_{n-1}) = \sum_{\vec{b}\in\{0,1\}^n} a(\vec{b}) \cdot \tilde{eq}(\vec{b}, \vec{u})

如果我们把 eq~(b,u)\tilde{eq}(\vec{b}, \vec{u}) 记作 c\vec{c},那么 Evaluation 证明可以转化为一个内积证明,即证明

a,c=?f~(X0,X1,,Xn1)\langle \vec{a}, \vec{c} \rangle \overset{?}{=} \tilde{f}(X_0,X_1,\ldots,X_{n-1})

仅仅证明内积还不够,Prover 还需要承诺 c\vec{c},并且向 Verifier 证明 c\vec{c} 的正确性。论文 [PH23] 总给出了一种方案,是将 c\vec{c} 的正确性用 logN\log{N} 个多项式约束来证明。这可以将 Proof size 优化到 O(logN)O(\log{N}) 个 Field 加上 O(1)O(1) 个 Group Element。不过这并不是 Proof size 最优化的方案。

我们可以定义三列向量,分别是 c\vec{c}c\vec{c}'u\vec{u}',其中 c\vec{c}'c\vec{c} 中的 Lookup 向量,即对任意的 cicc_i\in\vec{c'},都有 cicc_i\in\vec{c},请注意这里并不是一个 Unindexed Lookup 关系,而是一个 Indexed Lookup 关系。然后定义 u\vec{u}' 中的每个元素也同样来自于 u\vec{u}。这样我们可以用一个多项式约束关系来证明 c\vec{c} 的正确性。

(1ui)ciuici=0,i[N](1-u'_i) \cdot c_i - u'_i \cdot c'_i = 0, \quad \forall i \in [N]

其中 Indexed Lookup 关系我们可以用 Copy Constraint Argument 来证明,或者我们也可以用 Indexed Logup Argument 协议来证明,这样一来,我们就可以得到 O(1)O(1) 的 Proof size。

增加 PH23, Gemini 对接 FRI 的协议描述

对于 PH23-PCS, zeromorph 以及 gemini 协议,它们都将 MLE-PCS 转换为了 univariate-PCS,在原来的协议中,对接 univariate-PCS 是 KZG10,我们尝试将这些协议对接 FRI-PCS 协议,并给出了完整的协议描述。

  1. PH23-FRI

    我们给出了两个不同的 PH23 协议对接 FRI 的协议。

    通过对上面两种不同的实现方式进行比较,我们发现协议 2 中要处理的多项式更多,整体证明大小和 Verifier 计算复杂度比协议 1 高。

  2. Gemini-FRI

    协议描述见 Gemini: Interfacing with FRI。FRI-PCS 有一个好处是对于不同次数的多项式在多个点的打开,可以用随机数合并成一个多项式,只需要再调用一次 FRI 的 low degree test 就能一次完成这些证明。因此结合 Gemini 协议和 FRI-PCS 时,只需调用一次 FRI 协议就能证明 Gemini 协议中多个多项式在不同点的打开正确。

优化 Basefold 协议

Basefold 中的 Sumcheck 子协议中,Prover 每一步发送的 h(i)(X)h^{(i)}(X) 是一个一元二次多项式,但实际上经过 Sumcheck 优化 [Gru24],Prover 可以仅发送一个一次多项式,这样可以减少 Sumcheck 子协议的通信量。这一点在论文 [H24] 中被提及。但进一步深入研究 Deepfold 协议,发现该协议中是一种与 [H24] 不同的 Sumcheck 协议,这部分详细描述见 Deepfold 与 sumcheck 的联系

简述下,根据 eq~(X,Y)\tilde{eq}(\vec{X}, \vec{Y}) 的定义,它可以被分解为:

eq~(X0X1,Y0Y1)=eq(X0,Y0)eq(X1,Y1)\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)

先观察下 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))

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

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}

这样 Prover 仅发送 g(X)=(b1,b2){0,1}2(f~(X,b1,b2)eq((u1,u2),(b1,b2)))g(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) 给 Verifier 即可,由 Verifier 补上计算 eq(u0,X)eq(u_0, X),而这个计算仅是一次 Linear Combination,仅包含一次乘法。

另一篇文章 Basefold Optimization 中将 Deepfold 的优化技巧应用到了 Basefold 中,可以有效减少 Prover 和 Verifier 的计算量,同时也减少了证明长度。经过大致的估算,Sumcheck Prover 的运算量减少一半,而 Sumcheck Verifier 的运算量减少到 [H24] 的六分之一。对于 Basefold 而言,Verifier 的总体运算量中占主要成分的还是 FRI-Query 的运算量,因此这个优化并没有那么显著,但是从协议设计方面,优化后的协议更加简洁,这种技术是否可以应用到别的协议中,值得进一步研究。感兴趣的读者可以参考优化后的代码原型实现 basefold_rs_opt_pcs.py

代码实现(Python)

本项目用 Python 代码实现了许多 MLE-PCS 协议,同时有的协议还提供了 Jupyter Notebook 版本,这些代码可以帮助使用者通过代码交互的形式深入理解协议。

SchemePython CodeJupyter Notebook
Geminibcho_pcs.pybcho_pcs.ipynb
HyperKZGhyperkzg_pcs.py
Zeromorphzeromorph.py, zeromorph_zk.py, zerofri.pyzeromorph.ipynb, zeromorph_mapping_tutorial.ipynb
PH23ph23_pcs.py
Mercurymercury_pcs.py
Samaritansamaritan_pcs.py
BasefoldBasefold.py,basefold_rs_opt_pcs.py, basefold_rs_pcs.pyBasefold.ipynb
Deepfolddeepfold_pcs.pydeepfold.ipynb
WHIRwhir_pcs.py
Hyraxhyrax_pcs.py
PST13(Libra-PCS)libra_pcs.py

除了实现这些协议以外,还实现了一些 MLE-PCS 协议会用到的子协议。

SubprotocolPython CodeJupyter Notebook
FRIfri.py
STIRstir.ipynb
KZG10kzg10.py,kzg10_hiding_m.py, kzg10_hiding_z.py, kzg10_non_hiding.py,kzg_hiding.pykzg10.ipynb
IPAipa.py
univariate polynomialunipolynomial.py, unipoly.py, unipoly2.py
multilinear polynomialmle2.py

代数运算优化

在实现 MLE-PCS 时,多项式的运算无处不在,不同的实现方式对多项式的运算复杂度有不同的影响。在本项目中,我们研究了一些多项式运算的优化方法,包括多项式除法的优化。

假设一个有限域 F\mathbb{F} ,对于 F[X]\mathbb{F}[X] 上的多项式 f(X)f(X)g(X)g(X) ,它们之间满足带余除法等式

f(X)=g(X)q(X)+r(X)f(X) = g(X) \cdot q(X) + r(X)

并且 deg(r)<deg(g)\deg(r) < \deg(g) ,记 n=deg(f),m=deg(g)n = \deg(f), m = \deg(g) 。传统的除法需要 O(n2)O(n^2) 的计算复杂度计算出 f(X)f(X)g(X)g(X) 相除后的商多项式 q(X)q(X) 和余数多项式 r(X)r(X) 。本项目介绍了一种利用 Newton Iteration 的快速除法算法,算法复杂度与多项式乘法一致,为 O(M(n))O(M(n)) ,其中 M(n)M(n) 表示多项式乘法的复杂度。关于该算法的详细描述见博客文章 基于 Newton Iteration 的多项式快速除法 ,对应的 python 代码实现为 unipolynomial.py

基于 KZG10 的 MLE-PCS 对比

基于 KZG 的 MLE-PCS 有 Libra-PCS、PH23-PCS、zeromorph、gemini、mercury 以及 samaritan。

本项目从理论上详细统计并分析了 PH23-PCS、zeromorph 以及 gemini 协议的复杂度,包括有限域乘法、有限域除法、椭圆曲线上的加法乘法等。这三个协议都将对 MLE 多项式的承诺转换为一元多项式的承诺,一元多项式的承诺方案可以对接 KZG10 或者 FRI ,但它们转换的方案各不相同,也导致它们在效率上有所差异。

先简要总结下这三个协议的思路,ph23 和 zeromorph 考虑的都是 MLE 多项式在 Hypercube 上的点值形式,而 gemini 考虑的是 MLE 多项式的系数形式。

MLE方案
ph23hypercube 上的 evaluation转换为证明内积,需证明 c\vec{c} 的构造正确与内积证明(sum product 方案),转换为证明 n+4n + 4 个一元多项式在 H\mathbb{H} 上为 0
zeromorphhypercube 上的 evaluation利用余数定理将多元多项式进行分解,再将分解后的多项式在 hypercube 上的值直接对应到一元多项式,证明关于一元多项式的等式成立以及商多项式的 degree bound。
gemini系数式直接对应一元多项式的系数式,利用 split-and-fold 对一元多项式进行折叠,直到最后折叠为一个常数多项式。

对于 zeromorph 协议和 gemini 协议,我们给出了一些优化思路,因此这两个协议有多个版本。关于这些协议的描述文档和复杂度分析文档链接如下表所示。

协议版本协议描述文档协议分析文档
ph23PH23+KZG10 Protocol (Optimized Version)ph23-analysis
gemini优化版 1gemini-pcs-02gemini-analysis
gemini优化版 2: 类似 FRI query 优化gemini-pcs-03gemini-analysis
zeromorphv1: batched degree boundOptimized Protocolzeromorph-anlysis
zeromorphv2: 优化 degree bound 证明Zeromorph-PCS (Part II)zeromorph-anlysis

下面给出这三个协议对接 KZG10 的复杂度分析结果,其中的记号说明如下:

PH23

在 PH23 协议的 Round 3 的第 10 步,Prover 需要构造 Quotient 多项式 qωζ(X)q_{\omega\zeta}(X)

qωζ(X)=z(X)z(ω1ζ)Xω1ζq_{\omega\zeta}(X) = \frac{z(X) - z(\omega^{-1}\cdot\zeta)}{X - \omega^{-1}\cdot\zeta}

在这一步计算时,我们考虑了两种实现方法。

方法一:分子分母的多项式用系数式进行表示,在计算商多项式时,由于分母是一次多项式,可以使用线性多项式的除法,复杂度为 (N1) Fmul(N - 1) ~ \mathbb{F}_{\mathsf{mul}} ,该方法得到的商多项式也是系数形式。在协议的后续步骤中需要对该商多项式进行承诺,并发送给 Verifier 。由于 qωζ(X)q_{\omega\zeta}(X) 的次数为 N2N - 2 ,假设计算得到的是 qωζ(X)q_{\omega\zeta}(X) 的系数式 qωζ(0),qωζ(1),,qωζ(N2)q_{\omega\zeta}^{(0)}, q_{\omega\zeta}^{(1)}, \ldots, q_{\omega\zeta}^{(N - 2)} ,那么商多项式的承诺为

Qωζ=qωζ(0)G+qωζ(1)(τG)++qωζ(N2)(τN2G)Q_{\omega\zeta} = q_{\omega\zeta}^{(0)} \cdot G + q_{\omega\zeta}^{(1)} \cdot (\tau \cdot G) + \cdots + q_{\omega\zeta}^{(N - 2)} \cdot (\tau^{N - 2} \cdot G)

其中 GG 是椭圆曲线 G1\mathbb{G}_1 上的生成元,(G,τG,,τN2G)(G, \tau G, \ldots, \tau^{N - 2}G) 是 KZG10 的 SRS。这就要求内存中存储这些 SRS。

方法二:用点值式进行计算。计算得到 [qωζ(x)xH][q_{\omega\zeta}(x)|_{x \in H}]

这种方法计算商多项式的总复杂度为

Finv+(4N3) Fmul\mathbb{F}_{\mathsf{inv}} + (4N - 3) ~ \mathbb{F}_{\mathsf{mul}}

可以看到,由于分母只是一次多项式,用方法一会更高效一些,带来的代价是内存中需要多存储 SRS (G,τG,,τN2G)(G, \tau G, \ldots, \tau^{N - 2}G)

考虑这两种不同的实现方法,得到 PH23 协议的复杂度为:

Prover’s cost:

  1. 在协议的 Round 3-10 用系数形式,复杂度为
(17nN+36N+9n2) Fmul+(n+1)log2(n+1) Fmul+2 Finv+5 msm(N,G1)+2 msm(N1,G1)\begin{align} (17nN + 36N + 9n - 2) ~ \mathbb{F}_{\mathsf{mul}} + {(n + 1) \log^2(n + 1) ~ \mathbb{F}_{\mathsf{mul}} } + 2~ \mathbb{F}_{\mathsf{inv}} + 5 ~ \mathsf{msm}(N, \mathbb{G}_1) + 2 ~ \mathsf{msm}(N - 1, \mathbb{G}_1) \end{align}

这种方法要求内存中要存储 SRS (G,τG,,τN2G)(G, \tau G, \ldots, \tau^{N - 2}G) ,便于用系数形式进行多项式的承诺。

  1. 在 Round 3-10 用方法二,点值形式,复杂度为
(17nN+39N+9n4) Fmul+(n+1)log2(n+1) Fmul+3 Finv+6 msm(N,G1)+msm(N1,G1)\begin{align} (17nN + 39N + 9n - 4) ~ \mathbb{F}_{\mathsf{mul}} + { (n + 1) \log^2(n + 1) ~ \mathbb{F}_{\mathsf{mul}} } + 3~ \mathbb{F}_{\mathsf{inv}} + 6 ~ \mathsf{msm}(N, \mathbb{G}_1) + \mathsf{msm}(N - 1, \mathbb{G}_1) \end{align}

Verifier’s cost:

(11n+11) Fmul+(n+4) Finv+19 EccMulG1+16 EccAddG1+2 P(11n + 11) ~ \mathbb{F}_{\mathsf{mul}} + (n + 4) ~ \mathbb{F}_{\mathsf{inv}} + 19 ~ \mathsf{EccMul}^{\mathbb{G}_1} + 16 ~ \mathsf{EccAdd}^{\mathbb{G}_1} + 2 ~ P

Proof size:

(n+1)Fp+7 G1(n + 1) \cdot \mathbb{F}_p + 7 ~ \mathbb{G}_1

gemini

gemini 优化版 1

Prover’s cost:

(10N+n+5) Fmul+N Finv+i=1n1msm(2i,G1)+msm(N3,G1)+msm(N1,G1)(10 N + n + 5) ~ \mathbb{F}_{\mathsf{mul}} + N ~ \mathbb{F}_{\mathsf{inv}} + \sum_{i = 1}^{n - 1} \mathsf{msm}(2^{i}, \mathbb{G}_1) + \mathsf{msm}(N - 3, \mathbb{G}_1) + \mathsf{msm}(N - 1, \mathbb{G}_1)

Verifier’s cost:

(4n+8) Fmul+(2n+2) Finv+(n+1) EccMulG1+(n+2) EccAddG1+2 P\begin{aligned} & (4n + 8) ~ \mathbb{F}_{\mathsf{mul}} + (2n + 2) ~ \mathbb{F}_{\mathsf{inv}} + (n + 1) ~ \mathsf{EccMul}^{\mathbb{G}_1} + (n + 2) ~ \mathsf{EccAdd}^{\mathbb{G}_1} + 2~P \end{aligned}

Proof size:

(2n+1)Fp+(n+1)G1(2n + 1) \mathbb{F}_p + (n + 1) \cdot \mathbb{G}_1

gemini 优化版 2

Prover’s cost:

(14N+6n11) Fmul+(n+1) Finv+i=1n1msm(2i,G1)+2 msm(N1,G1)\begin{aligned} & (14 N + 6n - 11) ~ \mathbb{F}_{\mathsf{mul}} + (n + 1) ~ \mathbb{F}_{\mathsf{inv}} + \sum_{i = 1}^{n - 1} \mathsf{msm}(2^{i}, \mathbb{G}_1) + 2 ~ \mathsf{msm}(N - 1, \mathbb{G}_1) \\ \end{aligned}

Verifier’s cost:

8n Fmul+(3n+1) Finv+(2n+4) EccMulG1+(2n+3) EccAddG1+2 P8n ~ \mathbb{F}_{\mathsf{mul}} + (3n + 1) ~ \mathbb{F}_{\mathsf{inv}} + (2n + 4) ~ \mathsf{EccMul}^{\mathbb{G}_1} + (2n + 3) ~ \mathsf{EccAdd}^{\mathbb{G}_1} + 2~P

Proof size:

(n+1)Fp+(n+1)G1(n + 1) \cdot \mathbb{F}_p + (n + 1) \cdot \mathbb{G}_1

通过上面两个协议的对比知,gemini 优化版 2 协议通过增加 Prover 和 Verifier 的工作量的代价,降低了 n Fpn ~ \mathbb{F}_p 的 proof size。

Zeromorph

我们对三个版本的 zeromorph 协议进行了详细的复杂度分析。

zeromorph-v1

我们对两个优化版本的 zeromorph 协议进行了详细的复杂度分析。

Prover’s cost:

(7N+5n9) Fmul+k=0nmsm(2k,G1)+msm(Dmax+1,G1)\begin{align} & (7N + 5n - 9) ~ \mathbb{F}_{\mathsf{mul}} + \sum_{k=0}^{n} \mathsf{msm}(2^k,\mathbb{G}_1) + \mathsf{msm}(D_{max} + 1, {\mathbb{G}_1}) \\ \end{align}

Verifier’s cost:

(5n1) Fmul+(2n+2) EccMulG1+(2n+2) EccAddG1+EccMulG2+EccAddG2+2 P(5n - 1) ~ \mathbb{F}_{\mathsf{mul}} + (2n + 2) ~ \mathsf{EccMul}^{\mathbb{G}_1} + (2n + 2) ~ \mathsf{EccAdd}^{\mathbb{G}_1} + \mathsf{EccMul}^{\mathbb{G}_2} + \mathsf{EccAdd}^{\mathbb{G}_2} + 2~P

Proof size:

(n+2) G1(n + 2) ~ \mathbb{G}_1

zeromorph-v2

Prover’s cost:

(7N+5n10) Fmul+Finv+k=0nmsm(2k,G1)+msm(2n1,G1)+msm(2n11,G1)+msm(2n1,G1)\begin{aligned} & (7N + 5n - 10) ~ \mathbb{F}_{\mathsf{mul}} + \mathbb{F}_{\mathsf{inv}} \\ & + \sum_{k=0}^{n} \mathsf{msm}(2^k,\mathbb{G}_1) + \mathsf{msm}(2^{n - 1} , \mathbb{G}_1) + \mathsf{msm}(2^{n - 1} - 1, \mathbb{G}_1) + \mathsf{msm}(2^n - 1, \mathbb{G}_1) \end{aligned}

Verifier’s cost:

(5n1) Fmul+Finv+(2n+6) EccMulG1+(2n+7) EccAddG1+2 P\begin{aligned} (5n - 1) ~ \mathbb{F}_{\mathsf{mul}} + \mathbb{F}_{\mathsf{inv}} + (2n + 6) ~ \mathsf{EccMul}^{\mathbb{G}_1} + (2n + 7) ~ \mathsf{EccAdd}^{\mathbb{G}_1} + 2~P \end{aligned}

Proof size:

(n+3)G1+Fq\begin{aligned} (n + 3) \cdot \mathbb{G}_1 + \mathbb{F}_q \end{aligned}

总结

通过这两个协议的复杂度分析结果对比可知,没有进行任何优化的 zeromorph 协议的 msm 操作的长度是最大的,为 n msm(Dmax+1,G1)n ~ \mathsf{msm}(D_{max} + 1,\mathbb{G}_1) ,同时 proof size 也最大,为 (2n+1)G1(2n + 1) \mathbb{G}_1 ,这部分协议复杂度详细分析可见 zeromorph-anlysis。zeromorph-v1 和 zeromorph-v2 这两个协议采取了不同的方法来优化 degree bound 的证明,减少了 Prover 的 msm 的操作并降低了大约 n G1n ~ \mathbb{G}_1 的证明大小。zeromorph-v1 和 zeromorph-v2 在计算复杂度上的最大差别是,zeromorph-v2 协议避免了 Verifier 在椭圆曲线 G2\mathbb{G}_2 上进行运算,带来的代价是增加了 Verifier 在椭圆曲线 G1\mathbb{G}_1 常数级别的计算量和 G1+Fq\mathbb{G}_1 + \mathbb{F}_q 的证明大小。

对比

参考 mercury 论文[EG25]中的理论分析,并结合上述分析结果,对比基于 KZG10 的协议的复杂度。

ProtocolProver’s costVerifier’s costProof size
Libra-PCS
PH23-KZGO(NlogN) F,O(N)GO(N\log N) ~ \mathbb{F}, O(N) \mathbb{G}O(logN) F,O(1) GO(\log N) ~ \mathbb{F}, O(1) ~ \mathbb{G}O(logN) F,O(1) GO(\log N)~ \mathbb{F}, O(1) ~ \mathbb{G}
geminiO(N) F,O(N)GO(N) ~ \mathbb{F}, O(N) \mathbb{G}O(logN) F,O(n) GO(\log N) ~ \mathbb{F}, O(n) ~ \mathbb{G}O(logN) F,O(logN) GO(\log N)~ \mathbb{F}, O(\log N) ~ \mathbb{G}
hyperKZG
zeromorph-v0O(N) F,O(N)GO(N) ~ \mathbb{F}, O(N) \mathbb{G}O(logN) F,O(logN) GO(\log N) ~ \mathbb{F}, O(\log N) ~ \mathbb{G}(2logN+1) G(2\log N + 1) ~ \mathbb{G}
zeromorph-v1O(N) F,O(N)GO(N) ~ \mathbb{F}, O(N) \mathbb{G}O(logN) F,O(logN) GO(\log N) ~ \mathbb{F}, O(\log N) ~ \mathbb{G}(logN+2) G(\log N + 2) ~ \mathbb{G}
zeromorph-v2O(N) F,O(N)GO(N) ~ \mathbb{F}, O(N) \mathbb{G}O(logN) F,O(logN) GO(\log N) ~ \mathbb{F}, O(\log N) ~ \mathbb{G}F,(logN+3) G\mathbb{F}, (\log N + 3) ~ \mathbb{G}
mercury [EG25]O(N) F,2N+O(N)GO(N) ~ \mathbb{F}, 2N + O(\sqrt{N}) \mathbb{G}O(logN) F,O(1) GO(\log N) ~ \mathbb{F}, O(1) ~ \mathbb{G}O(1) F,O(1) GO(1)~ \mathbb{F}, O(1) ~ \mathbb{G}
samaritan [GPS25]O(N) F,O(N)GO(N) ~ \mathbb{F}, O(N) \mathbb{G}O(logN) F,O(1) GO(\log N) ~ \mathbb{F}, O(1) ~ \mathbb{G}O(1) F,O(1) GO(1)~ \mathbb{F}, O(1) ~ \mathbb{G}

通过对比发现:

  1. 在 Prover 计算复杂度方面,PH23 复杂度最高,需要 O(NlogN)O(N\log N) 数量级的有限域上的计算量,而其他协议只需要 O(N) FO(N) ~ \mathbb{F} 的计算量。
  2. 在 Verifier 计算复杂度方面,所有协议都需要 O(logN)O(\log N) 的有限域操作, PH23, mercury 和 samaritan 协议只需要常数级别椭圆曲线上的计算,而其他协议需要 O(logN)O(\log N) 级别的椭圆曲线上的计算。
  3. 在 Proof size 方面,mercury 和 samaritan 协议能够达到常数级别的证明大小。我们发现,PH23 协议在使用类似 Plonk 的方案时也能达到常数的证明大小,计划在将来的工作中详细描述这部分协议。 目前看来,mercury 和 SamaritanPCS 这两个协议效率最优,能在不牺牲 Prover 线性 O(N)O(N) 的有限域运算的情况下,达到常数的证明尺寸,而非对数级别的 O(logN)O(\log N)

基于 FRI 的 MLE-PCS 对比

我们详细描述了 PH23、gemini 以及 zeromorph 协议对接 FRI 的协议。对于采用 mmcs 结构以及用 rolling batch [ZLGSCLD24] 技巧进行优化的 zeromorph-fri 协议,我们详细分析了该协议的复杂度。通过与 Basefold 协议对比发现,Basefold 协议要优于 zeromorph-fri 协议。另外,我们从 Verifier 的查询复杂度的角度对比了 Basefold、Deepfold 以及 WHIR 协议。

协议版本协议描述文档协议分析文档
basefoldbasefold 论文 [ZCF23]basefold-analysis
ph23-fri内积采用 grand sum缺失的协议 PH23-PCS(四)
ph23-fri内积采用 univariate sumcheck缺失的协议 PH23-PCS(五)
gemini-friGemini: Interfacing with FRI
zeromorph-fri直接对接 fri 协议Zeromorph-PCS: Integration with FRI
zeromorph-fri优化版:采用 mmcs 结构承诺商多项式和 rolling batch [ZLGSCLD24] 技巧Zeromorph-PCS: Integration with FRIzeromorph-fri-analysis

Basefold v.s. Zeromorph-fri

下面给出 basefold 协议和 zeromorph-fri(优化版) 的复杂度分析结果,其中的记号说明如下:

Basefold

经过分析,得到 basefold 协议的复杂度为:

Prover’s cost:

((52R+9)N+3n52R13) Fmul+(RNR) Finv+i=1n1MT.commit(2iR)\begin{aligned} \left((\frac{5}{2} \mathcal{R} + 9) \cdot N + 3n - \frac{5}{2} \mathcal{R} - 13 \right) ~ \mathbb{F}_{\mathsf{mul}} + (\mathcal{R} \cdot N - \mathcal{R}) ~ \mathbb{F}_{\mathsf{inv}} + \sum_{i = 1}^{n - 1} \mathsf{MT.commit}(2^{i} \cdot \mathcal{R}) \end{aligned}

若加上 Prover 计算编码 πn\pi_n 的算法复杂度,则总复杂度为

(R2nN+(52R+9)N+3n52R13) Fmul+(RNR) Finv+i=1n1MT.commit(2iR)\left(\frac{\mathcal{R}}{2} \cdot nN + (\frac{5}{2} \mathcal{R} + 9) \cdot N + 3n - \frac{5}{2} \mathcal{R} - 13 \right) ~ \mathbb{F}_{\mathsf{mul}} + (\mathcal{R} \cdot N - \mathcal{R}) ~ \mathbb{F}_{\mathsf{inv}} + \sum_{i = 1}^{n - 1} \mathsf{MT.commit}(2^{i} \cdot \mathcal{R})

Proof size:

((2l+3)n+R) F+(l2n2+(logRl+12l+1)n) H\begin{align} ((2l + 3)n + \mathcal{R}) ~ \mathbb{F} + \left( \frac{l}{2} \cdot n^2 + \left(\log \mathcal{R} \cdot l +\frac{1}{2} \cdot l + 1\right) \cdot n \right) ~ H \end{align}

Verifier’s cost:

(l2n2+(llogR+l2)n) H+(5l+12)n Fmul+((2l+5)n+1) Finv\begin{align} \left( \frac{l}{2} \cdot n^2 + (l\log \mathcal{R} + \frac{l}{2})n \right) ~ H + (5l + 12)n ~ \mathbb{F}_{\mathsf{mul}} + ((2l + 5)n + 1) ~ \mathbb{F}_{\mathsf{inv}} \end{align}

Zeromorph-fri

Zeromorph-fri 协议的复杂度为:

Prover’s Cost: $$

(2RnN+(2RlogR+7R+3)N+nRlogR4R3) Fmul+(3RN2R+1) Finv+MMCS.commit(2n1R,,R)+i=1n1MT.commit(2iR)\begin{align} & (2\mathcal{R}\cdot nN + (2\mathcal{R} \log \mathcal{R} + 7 \mathcal{R} + 3) \cdot N + n - \mathcal{R}\log \mathcal{R} - 4 \mathcal{R} - 3) ~\mathbb{F}_{\mathsf{mul}} + (3 \mathcal{R} \cdot N - 2 \mathcal{R} + 1) ~\mathbb{F}_{\mathsf{inv}} \\ & + \mathsf{MMCS.commit}(2^{n-1} \cdot \mathcal{R}, \ldots, \mathcal{R}) + \sum_{i = 1}^{n - 1}\mathsf{MT.commit}(2^{i} \cdot \mathcal{R}) \end{align}

$$

Proof size: $$

((2l+1)n+3l) F+(32ln2+(3logRl12l+1)nl+1) H\begin{align} ((2l + 1) \cdot n + 3l) ~ \mathbb{F} + (\frac{3}{2} l \cdot n^2 + (3\log \mathcal{R}l - \frac{1}{2}l + 1) n - l + 1) ~ H \end{align}

$$

Verifier’s Cost:

(ln2+(2logRll)n+l2logRl) C+(l2n2+(3l2+logRl)nl) H+((7l+5)n+5l+1) Fmul+((3l+1)n+2l) Finv\begin{aligned} & (ln^2 + (2 \log \mathcal{R}l - l) n + l - 2 \log \mathcal{R}l) ~C + (\frac{l}{2} n^2 + (\frac{3l}{2} + \log \mathcal{R}l)n - l) ~H \\ & + ((7l + 5)n + 5l + 1) ~ \mathbb{F}_{\mathsf{mul}} + ((3l + 1)n + 2l) ~ \mathbb{F}_{\mathsf{inv}} \end{aligned}

对比结果

下面对比 Basefold 协议与 zeromorph-fri 协议的复杂度。

Prover’s cost

将 zeromorph-fri 的 Prover cost 减去 basefold 加上编码复杂度的 Prover cost,结果为

(2RnN+(2RlogR+7R+3)N+nRlogR4R3) Fmul+(3RN2R+1) Finv+MMCS.commit(2n1R,,R)+i=1n1MT.commit(2iR)((R2nN+(52R+9)N+3n52R13) Fmul+(RNR) Finv+i=1n1MT.commit(2iR))=(32RnN+(2RlogR+92R6)N2nRlogR32R+10) Fmul+(2RNR+1) Finv+MMCS.commit(2n1R,,R)\begin{align} & (2\mathcal{R}\cdot nN + (2\mathcal{R} \log \mathcal{R} + 7 \mathcal{R} + 3) \cdot N + n - \mathcal{R}\log \mathcal{R} - 4 \mathcal{R} - 3) ~\mathbb{F}_{\mathsf{mul}} + (3 \mathcal{R} \cdot N - 2 \mathcal{R} + 1) ~\mathbb{F}_{\mathsf{inv}} \\ & + \mathsf{MMCS.commit}(2^{n-1} \cdot \mathcal{R}, \ldots, \mathcal{R}) + \sum_{i = 1}^{n - 1}\mathsf{MT.commit}(2^{i} \cdot \mathcal{R}) \\ & - \left(\left(\frac{\mathcal{R}}{2} \cdot nN + (\frac{5}{2} \mathcal{R} + 9) \cdot N + 3n - \frac{5}{2} \mathcal{R} - 13 \right) ~ \mathbb{F}_{\mathsf{mul}} + (\mathcal{R} \cdot N - \mathcal{R}) ~ \mathbb{F}_{\mathsf{inv}} + \sum_{i = 1}^{n - 1} \mathsf{MT.commit}(2^{i} \cdot \mathcal{R}) \right) \\ = & ( \frac{3}{2}\mathcal{R}\cdot nN + (2\mathcal{R} \log \mathcal{R} + \frac{9}{2} \mathcal{R} - 6) \cdot N - 2 \cdot n - \mathcal{R}\log \mathcal{R} - \frac{3}{2}\mathcal{R} + 10) ~\mathbb{F}_{\mathsf{mul}} + (2 \mathcal{R} \cdot N - \mathcal{R} + 1) ~\mathbb{F}_{\mathsf{inv}} \\ & + \mathsf{MMCS.commit}(2^{n-1} \cdot \mathcal{R}, \ldots, \mathcal{R}) \\ \end{align}

可以看出 basefold 远比 zeromorph-fri 计算量小,体现在有限域的乘法计算,求逆操作还有进行 Merkle Tree 承诺的哈希计算上。

Proof size

将 zeromorph-fri 的 proof size 减去 basefold 的 proof size,结果为

((2l+1)n+3l) F+(32ln2+(3logRl12l+1)nl+1) H(((2l+3)n+R) F+(l2n2+(logRl+12l+1)n) H)=(2n+3lR) F+(ln2+(2logRll)nl+1) H\begin{align} & ((2l + 1) \cdot n + 3l) ~ \mathbb{F} + (\frac{3}{2} l \cdot n^2 + (3\log \mathcal{R}l - \frac{1}{2}l + 1) n - l + 1) ~ H \\ & - \left(((2l + 3)n + \mathcal{R}) ~ \mathbb{F} + \left( \frac{l}{2} \cdot n^2 + \left(\log \mathcal{R} \cdot l +\frac{1}{2} \cdot l + 1\right) \cdot n \right) ~ H \right) \\ = & (-2n + 3l - \mathcal{R}) ~ \mathbb{F} + \left(l \cdot n^2 + (2\log \mathcal{R} \cdot l - l) n - l + 1\right) ~H \end{align}

可以看出 basefold 在 proof size 上比 zeromorph-fri 小,少发送大约 ln2ln^2 个哈希值。

Verifier’s Cost

将 zeromorph-fri verifier cost 减去 basefold 的 verifier cost,结果为

(ln2+(2logRll)n+l2logRl) C+(l2n2+(3l2+logRl)nl) H+((7l+5)n+5l+1) Fmul+((3l+1)n+2l) Finv((l2n2+(llogR+l2)n) H+(5l+12)n Fmul+((2l+5)n+1) Finv)=(ln2+(2logRll)n+l2logRl) C+(lnl) H+((2l7)n+5l+1) Fmul+((l4)n+2l1) Finv\begin{align} \\ & (ln^2 + (2 \log \mathcal{R}l - l) n + l - 2 \log \mathcal{R}l) ~C + (\frac{l}{2} n^2 + (\frac{3l}{2} + \log \mathcal{R}l)n - l) ~H \\ & + ((7l + 5)n + 5l + 1) ~ \mathbb{F}_{\mathsf{mul}} + ((3l + 1)n + 2l) ~ \mathbb{F}_{\mathsf{inv}} \\ & - \left(\left( \frac{l}{2} \cdot n^2 + (l\log \mathcal{R} + \frac{l}{2})n \right) ~ H + (5l + 12)n ~ \mathbb{F}_{\mathsf{mul}} + ((2l + 5)n + 1) ~ \mathbb{F}_{\mathsf{inv}}\right) \\ = & (ln^2 + (2 \log \mathcal{R}l - l) n + l - 2 \log \mathcal{R}l) ~C + \left(ln - l \right) ~ H\\ & + ((2l - 7)n + 5l + 1) ~ \mathbb{F}_{\mathsf{mul}} + ((l - 4)n + 2l - 1) ~ \mathbb{F}_{\mathsf{inv}} \\ \end{align}

可以看出,basefold 在 verifier cost 上比 zeromorph-fri 小。

综合上述三个方面的计算量,可以得出 Basefold 协议要优于 Zeromorph-fri 协议。

对比 Basefold, Deepfold 与 WHIR

关于 Basefold、Deepfold 与 WHIR 协议之间的对比在博客文章 [BaseFold vs DeepFold vs WHIR](mle-pcs/basefold-deepfold-whir/basefold-deepfold-whir.md at main · sec-bit/mle-pcs · GitHub) 中有详细的描述,这里主要叙述这三个协议的效率对比结果。

Basefold、Deepfold 与 WHIR 协议在协议框架上非常相似,这三个协议的框架都是 BaseFold 协议的框架,用相同的随机数同步进行 sumcheck 协议和 FRI/DEEP-FRI/STIR 协议,它们之间的不同主要也是来自 FRI 协议、DEEP-FRI 协议和 STIR 协议之间的不同。

对比这三个协议的效率,Prover 的计算量差异不是特别明显,主要取决于 Verifier 的查询次数,查询次数越大,会造成 Verifier 的计算量与证明大小越大。由于 STIR 协议在理论上的查询复杂度比 FRI 协议和 DEEP-FRI 协议更优,因此 WHIR 协议相比 BaseFold 协议与 DeepFold 协议有更少的查询次数。

另一方面,Verifier 的查询次数是和协议的 soundness 证明中能取到的 bound 相关的,根据目前的研究进展有:

  1. 基于 DEEP-FRI 协议的 DeepFold 协议,在基于一个简单的猜想下,能达到最优的界 1ρ1 - \rho 。若 FRI 协议想达到 1ρ1 - \rho 的界,其基于的猜想会更强(见 [BCIKS20] Conjecture 8.4)。
  2. BaseFold 协议在针对 Reed Solomon 编码下能达到 Johnson bound 1ρ1 - \sqrt{\rho}
  3. WHIR 协议在原论文中仅证明了其能达到 (1ρ)/2(1 - \rho)/2 ,但根据 [H24] 中的方法,有望证明达到 Johnson bound 1ρ1 - \sqrt{\rho}

基于 Bulletproofs 的 MLE-PCS

基于 Bulletproofs 的 MLE-PCS 有 Hyrax. 与 Σ-Check

Hyrax

Multilinear polynomial evaluations can be viewed as inner-product relations and thus can be proven directly using inner-product arguments (IPAs), such as Bulletproofs. However, a major drawback of Bulletproofs is their linear verification time: for an nn-variate multilinear polynomial, verification requires O(2n)O(2^n) time.

To address this inefficiency, the Hyrax PCS observes that polynomial evaluation can be reformulated as a matrix product. For example, consider f(z0,z1,z2,z3)=vf(z_0, z_1, z_2, z_3) = v. We can write:

f~(z0,z1,z2,z3)=[1z2z3z2z3][f0f1f2f3f4f5f6f7f8f9f10f11f12f13f14f15][1z0z1z0z1]\tilde{f}(z_0, z_1, z_2, z_3) = \begin{bmatrix} 1 & z_2 & z_3 & z_2z_3 \end{bmatrix} \begin{bmatrix} f_0 & f_1 & f_2 & f_3 \\ f_4 & f_5 & f_6 & f_7 \\ f_8 & f_9 & f_{10} & f_{11} \\ f_{12} & f_{13} & f_{14} & f_{15} \end{bmatrix} \begin{bmatrix} 1 \\ z_0 \\ z_1 \\ z_0z_1 \end{bmatrix}

Let FF denote the inner matrix, z1:=(1,z2,z3,z2z3)\vec{z}_1 := (1, z_2, z_3, z_2z_3), and z0:=(1,z0,z1,z0z1)\vec{z}_0 := (1, z_0, z_1, z_0z_1). In the Hyrax protocol, the prover first sends w=z1F\vec{w} = \vec{z}_1 \cdot F, enabling the verifier to check that wz0=v\vec{w} \cdot \vec{z}_0^\top = v. To ensure that w\vec{w} is computed correctly, the verifier issues a random challenge vector r\vec{r}, and the prover responds with t:=Fr\vec{t}^\top := F \cdot \vec{r}^\top. This leads to the relation z1t=z1Fr=wr\vec{z}_1 \cdot \vec{t}^\top = \vec{z}_1 \cdot F \cdot \vec{r}^\top = \vec{w} \cdot \vec{r}^\top, which holds if and only if w\vec{w} is correctly computed.

As a result, the verifier only needs to compute two inner products of length N\sqrt{N} (N=2nN = 2^n), achieving sublinear verification cost. Furthermore, the prover can use an IPA to prove these inner-product relations, reducing the proof size to O(logn)O(\log n).

Σ-Check

To prove a single evaluation relation f(z)=vf(\vec{z}) = v, Σ-Check employs an improved sumcheck protocol. In each round, the prover sends a linear polynomial fi(X):=f(r1,,ri1,X,zi+1,,zn)f_i(X) := f(r_1, \cdots, r_{i-1}, X, z_{i+1}, \cdots, z_n), while the verifier checks the following condition:

fi(0)eq(0,zi)+fi(1)eq(1,zi)=?fi1(ri1).f_i(0) \cdot \mathsf{eq}(0, z_i) + f_i(1) \cdot \mathsf{eq}(1, z_i) \overset{?}{=} f_{i-1}(r_{i-1}).

This approach reduces the proof size by nn compared to directly applying sumcheck, as in BaseFold.

When proving kk evaluation relations (fi(zi)=vi)i=1k(f_i(\vec{z}_i) = v_i)_{i = 1}^k, Σ-Check interpolates all fi(X)f_i(\vec{X}) as a single function f(y,X)f(\vec{y}, \vec{X}) over a hypercube y{0,1}logk\vec{y} \in \{0, 1\}^{\log k}. Similarly, z(y)\vec{z}(\vec{y}) and v(y)v(\vec{y}) are defined. Given a challenge αFlogk\vec{\alpha} \in \mathbb{F}^{\log k}, the prover can then use the improved sumcheck protocol to prove the following relation:

y{0,1}logkeq(α,y)(f(y,z(y))v(y)).\sum_{\vec{y} \in \{0, 1\}^{\log k}} \mathsf{eq}(\vec{\alpha}, \vec{y}) \cdot \big( f(\vec{y}, \vec{z}(\vec{y})) - v(\vec{y}) \big).

After the sumcheck, this reduces to the relation f(r,z(r))v(r)=sf(\vec{r}, \vec{z}(\vec{r})) - v(\vec{r}) = s.

Since z(Y)\vec{z}(\vec{Y}) and v(Y)v(\vec{Y}) are public, the verifier can compute them directly. Let fr(X):=f(r,X)f_r(\vec{X}) := f(\vec{r}, \vec{X}), zr:=z(r)\vec{z}_r := \vec{z}(\vec{r}), and vr:=v(r)v_r := v(\vec{r}). The output relation then becomes fr(zr)=s+vrf_r(\vec{z}_r) = s + v_r, which is itself an evaluation proof and can be handled by another sumcheck protocol.

It is worth noting that Σ-Check can also serve as an inner product argument (IPA), as described in Section 4.1 of GZQ+24). This enables sublinear verification when combined with the Hyrax IOP. We summarize the performance as follows.

SchemeProver TimeVerifier TimeProof Size
Σ\Sigma-Check (as PCS)O(k+N)O(k+N) F\mathbb{F}, O(N)O(N) G\mathbb{G}O(k+N)O(k+N) F\mathbb{F}, O(k+N)O(k+N) G\mathbb{G}2(logk+logN)2(\log k + \log N) G\mathbb{G}
Σ\Sigma-Check (as IPA)O(k+N)O(k+\sqrt{N}) F\mathbb{F}, O(N)O(\sqrt{N}) G\mathbb{G}O(k+N)O(k+\sqrt{N}) F\mathbb{F}, O(k+N)O(k+\sqrt{N}) G\mathbb{G}2(logk+logN)2(\log k + \log N) G\mathbb{G}

基于 Lattice 的 PCS

Greyhound

Greyhound是一种基于lattice的PCS,其底层协议依赖于 Labrador——一个用于证明 inner product relation 的lattice-based interactive proof。

整体结构上,Greyhound与 Brakedown 类似,首先将多项式的evaluation过程抽象为两个长向量内积的计算,即:

v=f,uv = \langle \vec{f}, \vec{u} \rangle

其中,f\vec{f} 是多项式 f(X)=i=0N1fiXif(X) = \sum_{i=0}^{N-1} f_i X^i 的系数向量,u=(1,u,u2,,uN1)\vec{u} = (1, u, u^2, \dots, u^{N-1}) 是一个幂向量。接着,将 f\vec{f} 的系数向量解析为一个 n×nn \times n 的矩阵 FF,其中 n=Nn = \sqrt{N},并将 u\vec{u} 写成两个向量的 tensor product:

a=(1,u,u2,,un1),b=(1,un,u2n,,u(n1)n),ba=u.\vec{a} = (1, u, u^2, \dots, u^{n-1}), \quad \vec{b} = (1, u^n, u^{2n}, \dots, u^{(n-1)n}), \quad \vec{b} \otimes \vec{a} = \vec{u}.

在证明过程中,Prover 首先计算 FaF\cdot \vec{a},得到中间结果向量 w\vec{w},并将其发送给 Verifier。Verifier 检查 w\vec{w}b\vec{b} 的内积是否等于 v,即验证:

v?=w,b.v ?= \langle \vec{w}, \vec{b} \rangle.

接着,Verifier 生成一个长度为 n 的随机 challenge 向量 c\vec{c},Prover 计算 z=cTF\vec{z} = \vec{c}^TF 并将其发送给 Verifier。Verifier 通过以下关系验证 \vec{w} 的正确性:

a,z?=w,c.\langle \vec{a}, \vec{z} \rangle ?= \langle \vec{w}, \vec{c} \rangle.

显而易见,通过将一维的系数向量扩展为二维矩阵,协议的 proof size 和 verification time 都得到了显著优化,降低到了 sublinear 的级别。

Greyhound 的安全性基于格上的困难问题 MSIS (Modular Short Integer Solution)。通过对系数矩阵的每一列以 δ\delta 为基进行decompose,可以得到 nn 个长度为 nlnl 的短向量,其中 l=logδql = \log_\delta q。随后,对每个短向量进行 Ajtai Commit,即可生成相应的 commitment 值。

Hyperwolf

受 Greyhound 的启发,我们最新的研究成果 Hyperwolf 进一步优化了结构,将其推广到 kk 维,整体效率达到了 O(kN1/k)O(kN^{1/k})。通过令 k=logNk = \log N,该方案成功实现了 log 级别的 proof size 和 verification time,显著提升了性能。

具体来说,我们将长度为 NN 的一维系数向量解析为一个 b×b××bb \times b \times \cdots \times bkk 维 hypercube [F](k)[F]^{(k)},其中 bk=Nb^k = N,并构造了 kk 个辅助向量 (ai)i[k](\vec{a}_i)_{i \in [k]},其中:

ai=(1,ubi,u2bi,,u(b1)bi)\vec{a}_i = (1, u^{b^{i}}, u^{2b^{i}}, \cdots, u^{(b-1)b^{i}})

并且满足:

ak1ak2a0=u.\vec{a}_{k-1} \otimes \vec{a}_{k-2} \otimes \cdots \otimes \vec{a}_0 = \vec{u}.

基于此,PCS 的 evaluation 过程可以描述为:

v=(F((F(F([F](k))a0)a1)a2))ak1.v = \left( \mathcal{F}\left( \cdots \left( \mathcal{F}\left( \mathcal{F}([F]^{(k)}) \cdot \vec{a}_0 \right) \cdot \vec{a}_1 \right) \cdot \vec{a}_2 \right) \cdots \right) \cdot \vec{a}_{k-1}.

其中,函数 F\mathcal{F} 将一个大小为 bk1×bk2××bib_{k-1} \times b_{k-2} \times \cdots \times b_i(ki)(k-i) 维 hypercube 映射为一个大小为 (bk1bi+1)×bi(b_{k-1} \cdots b_{i+1}) \times b_i(ki1)(k-i-1) 维 hypercube 矩阵,其中 i[k]i \in [k]

k=2k=2 时,该 evaluation 过程与 Greyhound 相同。

下图展示了 k=3k=3 时 evaluation 过程的示意图:

lattice.png

我们的证明协议由 kk 轮交互组成,每一轮可以看作是将一个高维关系降低一维的 reduction of knowledge。

在第 0 轮中,Prover 首先向 Verifier 发送中间结果:

fold(k)=F((F(F([F](k))a0)a1)ak2),\mathsf{fold}^{(k)} = \mathcal{F}(\cdots(\mathcal{F}(\mathcal{F}([F]^{(k)}) \cdot \vec{a}_0) \cdot \vec{a}_1) \cdots \vec{a}_{k-2}),

Verifier 随后验证其是否满足内积关系 fold(k),ak1=v\langle \mathsf{fold}^{(k)}, \vec{a}_{k-1} \rangle = v。为了进一步验证 fold(k)\mathsf{fold}^{(k)} 的正确性,Verifier 随机生成一个长度为 bb 的挑战向量 c(k)\vec{c}^{(k)}。Prover 使用 c(k)\vec{c}^{(k)}kk 维 hypercube [F](k)[F]^{(k)} 进行 fold,将其降维为一个 k1k-1 维的 hypercube [F](k1)[F]^{(k-1)},即:

[F](k1)=(c(k))T([F](k)).[F]^{(k-1)} =(\vec{c}^{(k)})^T\cdot([F]^{(k)}) .

即相当于一个 1×b1 \times b的向量乘一个 b×(b×b××b)b \times (b\times b\times … \times b)的矩阵。

与此同时,Verifier 更新验证值:

y=fold(k),c(k)y = \langle \mathsf{fold}^{(k)}, \vec{c}^{(k)} \rangle。

在后续每一轮中,Prover 和 Verifier 重复类似的交互:

对于任意第 ii 轮,Prover 向 Verifier 发送中间结果 fold(ki)\mathsf{fold}^{(k-i)},Verifier 检查 fold(ki),aki1=y\langle \mathsf{fold}^{(k-i)}, \vec{a}_{k-i-1} \rangle = y 是否成立,并生成新的挑战向量 c(ki)\vec{c}^{(k-i)}。Prover 使用该挑战对 witness 进行折叠降维,而 Verifier 同时更新验证值 y。每一轮结束后,witness 的维度从 kik-i 降低为 ki1k-i-1

经过 k2k-2 轮后,witness 被压缩为一个一维向量 f(1)\vec{f}^{(1)}。此时,Prover 将该一维向量 f(1)\vec{f}^{(1)} 直接发送给 Verifier,Verifier 最终验证是否满足以下关系:

f(1),a0=fold(2),c(2)\langle \vec{f}^{(1)}, \vec{a}_0 \rangle = \langle \mathsf{fold}^{(2)}, \vec{c}^{(2)} \rangle。

上述交互过程中,每一轮发送的proof size为 O(b)=O(N1/k)O(b) = O(N^{1/k}),verifier执行检查和更新参数所消耗的cost也为 O(N1/k)O(N^{1/k})。因此,kk轮的总proof size和verification cost分别为 O(kN1/k)O(kN^{1/k})。当 k=logNk = \log N时,改值可以优化到 O(logN)O(\log N)级别。

Future work

本项目目标还没有深入对比采用 Small Fields 的 PCS,这一类 PCS 会显著提升 Prover 的性能。这部分将是我们下一步的工作。另外除了 RS Code 之外,具有更好编码性能的线性编码 Spelman Code 也常常被用来构造 PCS,比如 brakedown, orion。此外,还有一些新的基于 Binary Field 的 PCS 协议,包括上面分析的一些协议,也可以用于 Binary Fields,比如 FRI,Ligerito 等。

References