MLE-PCS 比较 （最终报告）

Last update: 2025-06-12

背景¶

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

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

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

MLE-PCS 概览¶

对于一个 $n$ 元线性多项式 $\tilde{f}(X_0, X_1, \ldots, X_{n - 1})$ ，有以下两种表示形式：

1. Coefficients form

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

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

2. Evaluations form

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

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

在 MLE-PCS 的承诺协议中，Prover 先向 Verifier 承诺多元线性多项式 $\tilde{f}$ ，随后在 Evaluation 证明协议中，Prover 要向 Verifier 证明 $\tilde{f}$ 在一个公开点 $\vec{u} = (u_0, \ldots, u_{n - 1})$ 处的运算值为 $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。

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

按承诺协议的分类¶

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

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

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

KZG10¶

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

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

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

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

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

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

• 需要可信设置(Trusted Setup)来生成具有特定代数结构的公共参数
• 利用椭圆曲线上的双线性映射(bilinear pairing)来验证打开证明
• 打开证明的验证只需要一个群元素，这使得证明大小往往是常数

Merkle Tree¶

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

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

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

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

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

• 不需要可信设置（Trusted Setup）
• 承诺计算主要依赖哈希运算，相比 KZG10 需要在椭圆曲线上进行运算，计算开销更小
• 由于证明过程中需要发送 Merkle Path 等，证明大小往往比 KZG10 更大

Pedersen Commitment¶

Ajtai Commitment¶

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

• Ajtai commitment 承诺要求被承诺的内容 $\vec{f}$ 必须“足够小”，即存在一个上界 $B$，使得对所有 $f_i$ 都有 $|f_i| < B$。这是由于 SIS/LWE 困难问题的要求，只有满足该条件，Ajtai commitment 的 binding/hiding 性质才能归约到 SIS/LWE 问题。为了承诺任意系数的多项式，常用的方法是将每个系数拆分为更小但更长的数组（如二进制表示），然后对拆分后的结果进行承诺。这样即可满足 $< B$ 的要求。同理，在 opening 时，还需额外一步，将二进制向量与 $(1, 2, 2^2, \cdots)$ 做内积，恢复原始系数。
• 由于 Ajtai commitment 的结果本身也是一个向量，这使得实现“ “commitment-of-commitment”，变得非常容易。即在拆分后，可以对多个承诺再次进行 Ajtai commitment。这一技术在 lattice 设计中被广泛应用，以进一步减小证明体积。

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

按 Evaluation 证明原理分类¶

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

• Quotienting
• Split-and-fold
• Inner-product
• Sumcheck

Quotienting¶

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

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

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

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

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

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

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

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

$\Phi_n(X)$ 与 $\Phi_{n-k}(X^{2^k})$ 也是一元多项式，一般地，$\Phi_k(X^h)$ 表示如下的多项式

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

Inner-product¶

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Sumcheck 方式¶

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

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

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

因此，Prover 在后续的协议交互中，同样采用一个新的 Sumcheck 协议来证明 $\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 多项式的系数式

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

以 $n = 3$ 为例，系数向量

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

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

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

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

这里 split-and-fold 的含义是，先将 8 项求和 split 成两部分，即偶项 $f_0 + f_2 u_1 + f_4 u_2 + f_6 u_1u_2$ 和奇项 $f_1 + f_3 u_1 + f_5 u_2 + f_7 u_1u_2$ ，再用 $u_0$ 将这两部分 fold 成一部分，fold 完的这一部分还可以继续接着进行 split-and-fold 的过程。这里 split-and-fold 的思想和 FRI 以及 sumcheck 是一样的。

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

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

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

• KZG10
• FRI
• Bulletproofs-Inner Product Argument

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

对于基于 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(N\log{N})$ 的计算时间复杂度。这有可能导致 Prover 做不到线性时间的工作量。

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

• ✅：表示支持
• ✔️：表示支持，但需要进一步分析
• ❓：可能不支持，但没有进一步证明

MLE-PCS 的安全性分析¶

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

基于 KZG10 的安全性¶

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

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

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

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

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

• 安全模型：使用标准模型还是理想化模型，例如 Random Oracle 模型，或者 Algebraic Group 模型
• 困难假设：主要考虑使用假设的类型是 Falsifiable 还是 Non-falsifiable

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

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

• KZG-soundness-1：介绍了KZG 可提取性的概念，并分析了 [MBKM19] 论文中基于 AGM+ROM 模型下的 KZG 安全性证明方法

• KZG-soundness-2：详细介绍并分析了 [LPS24] 论文中基于 ROM 模型下的KZG 安全性证明方法

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

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

• 提取器算法在 Commit 和 Open 阶段之后提取多项式，如 [MBKM19]，[CHM+20]
• 提取器算法仅在 Commit 阶段之后提取多项式，如 [GWC19]

其中，后者虽然能在 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 证明。

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

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

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

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

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

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

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

• Dive into BBHR18-FRI Soundness ：详细分析了 FRI 论文 [BBHR18] 中的安全性证明
• Dive into BCIKS20-FRI Soundness ：介绍了如何通过 Proximity Gaps 定理来提高 FRI 协议中的安全性参数
• Proximity Gaps and Correlated Agreement: The Core of FRI Security Proof ：深入探讨了 FRI 安全性证明中的核心概念

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

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

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

• Basefold 协议介绍：
  • Notes on Basefold (Part I): Foldable Linear Codes
  • Notes on Basefold (Part II): IOPP
  • Notes on Basefold (Part III): MLE Evaluation Argument
• Basefold 原论文 [ZCF23] 中的 soundness 证明：
  • Notes on BaseFold (Part IV): Random Foldable Codes
  • Notes on Basefold (Part V): IOPP Soundness
• [H24] 中给出的 Basefold 协议的 soundness 证明：
  • Note on Basefold’s Soundness Proof under List Decoding
  • Note on Soundness Proof of Basefold under List Decoding

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 $(\bar{c}, \bar{w})$ 满足一个 relaxed relation。这个 relaxed relation 在其他常规约束上与 original relation 相同，仅在 norm constraint 和 binding constraint 上有所不同。

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

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

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

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

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

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

根据该定理，证明 short norm 问题可以被归约为证明某个投影向量 $\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 $\{(\vec{f}; F, \vec{z}, v): \mathsf{Com}(\vec{f}) = F, f(\vec{z}) = v\}$, where $\vec{f}$ represents the coefficients of the polynomial $f$; 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 $k$ distinct polynomial evaluations, each with $n$ variables, at a cost of $O(n+\log k)$-size proofs. This approach eliminates the need for circuit-based linearization and proves to be more efficient when handling $k$ polynomials, which previously required $O(n+k)$ cost in AC20 and ACF21. A prototype implementation is available at GitHub.

Hyperwolf 协议¶

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

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

Hyperwolf协议是对Greyhoud协议的优化，其核心思想是将原本的二维结构推广到 $k$ 维（$k \ge 2$）

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

优化 Zeromorph 协议¶

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

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

优化 Gemini 协议¶

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

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

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

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

优化 PH23 协议¶

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

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

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

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

其中 Indexed Lookup 关系我们可以用 Copy Constraint Argument 来证明，或者我们也可以用 Indexed Logup Argument 协议来证明，这样一来，我们就可以得到 $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 的协议。

   • 协议 1 描述见 缺失的协议 PH23-PCS（四），其中内积证明通过 Grand Sum 实现。
   • 协议 2 描述见 缺失的协议 PH23-PCS（五） ，其中内积证明通过 Univariate Sumcheck 方法实现。

   通过对上面两种不同的实现方式进行比较，我们发现协议 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)$ 是一个一元二次多项式，但实际上经过 Sumcheck 优化 [Gru24]，Prover 可以仅发送一个一次多项式，这样可以减少 Sumcheck 子协议的通信量。这一点在论文 [H24] 中被提及。但进一步深入研究 Deepfold 协议，发现该协议中是一种与 [H24] 不同的 Sumcheck 协议，这部分详细描述见 Deepfold 与 sumcheck 的联系。

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

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

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