1. 引言

Plonky2 是一种基于多项式承诺和Plonk的PIOP交互式证明的零知识证明协议，专注于通过 FRI 技术实现高效的zkSNARK。Plonky2 的主要设计目的是提高传统 zk-SNARKs 在递归零知识证明场景下的效率，并增强其后量子安全性，其基本思想是利用基于哈希函数的 FRI（Fast Reed-Solomon Interactive Oracle Proof of Proximity）对多项式进行高效验证，并通过随机性采样来提高协议的完整性与安全性。

本文将详细解析 Plonky2 协议的主要步骤和构建逻辑，并结合协议的具体操作过程进行分析，其中验证方V的随机挑战可以使用一个抗碰撞的哈希函数进行替换，从而改造为非交互式证明系统。

2. 协议预处理

2.1 构造电路与对应的多项式

在协议的预处理阶段，证明方P和验证方V首先共同构造电路，并计算一组多项式向量 $\vec{C}$ 和 $\vec{\sigma}$。这组多项式主要用于编码每个电路门的常量和扩展排列信息，表示电路中每个门的关系和操作。

具体而言，$\vec{C}$ 包含了门的常量和中间变量的约束，即门约束（Gate Constraint），而 $\vec{\sigma}$ 表示拓展排列（extended permutation）的信息，即复制约束（Copy Constraint）。 在后续多项式置换和零知识证明中起到关键作用。

2.2 构建 Merkle 树

证明方和验证方随后对 $\vec{C}$ 和 $\vec{\sigma}$ 进行哈希运算，构建一个 Merkle 树。该 Merkle 树不仅能有效压缩证明大小，还能在后续的多项式一致性验证中提供高效的数据认证结构。

2.3 证明方存储证明密钥

证明方将上述整棵 Merkle 树存储为证明密钥（proving key），用于后续的多项式承诺和验证操作。

2.4 验证方存储验证密钥

验证方存储 $\text{Com}(\vec{C}, \vec{\sigma})$ 作为验证密钥（verification key），确保在后续步骤中能够一致验证多项式与电路关系的正确性。

优化方法：通常通过存储Merkle cap（即Merkle树的部分子树节点信息），以减小最后提交的Merkle proof的大小

3. 主协议

主协议流程如图所示：

3.1 生成证明与多项式承诺

证明方生成电路的证明（$witness$）对应的向量 $\vec{w}$，并计算其多项式形式 $w(x)$。随后，证明方使用FRI协议，生成承诺多项式的对应的承诺值（Merkle root) $\text{Com}(\vec{w})$，并发送给验证方。

3.2 验证方随机采样

验证方在有限域 $\mathbb{F}_p$ 中随机选择挑战 $\beta_1, \ldots, \beta_r, \gamma_1, \ldots, \gamma_r$，这些随机参数将用于后续的置换多项式（Permutation Polynomial）验证，以保证协议的完备性。

3.3 发送置换多项式与中间多项式承诺

证明方发送置换多项式 $Z(x)$ 与中间乘积多项式 $\pi(x)$ 的承诺 $\text{Com}(\vec{Z}, \vec{\pi})$，以确保排列关系的完整性。

置换多项式的主要作用是验证变量间的一致性（即Copy Constraint是否满足），而乘积多项式用于验证中间变量计算的正确性（降低多项式的次数，并行计算以提高效率）。

3.4 验证方再次随机采样

验证方再次采样一组新的随机参数 $\alpha_1, \ldots, \alpha_r$，用于将多个约束使用随机线性组合进行合并（constraint combination）。这一步操作旨在通过引入不同的随机系数来结合多个约束，从而简化验证流程并降低复杂度。

3.5 生成并发送商多项式承诺

证明方使用FRI协议构建Merkle树，以生成商多项式 $q_i(x)$ 对应的承诺 $\text{Com}(\vec{q})$。商多项式的具体形式如下：

$$ q_i(x) = \frac{C_i(x)}{Z_H(x)} $$

其中，$ C_i(x) $ 是合并后（进行随机线性组合后）的约束多项式，表示所有约束的组合结果；而 $ Z_H(x) = x^n - 1 $ 则是集合H上的消去多项式（vanishing polynomial），确保验证时的多项式在特定域 $ H $ 上消去（即可以被对应的消去多项式进行因式分解）。

3.6 验证方采样随机检测点

验证方选择一个新的随机点 $ \zeta \in \mathbb{F}_p(\phi) $，用于验证商多项式和约束多项式在此点上的一致性。

3.7 证明方发送多项式在检测点的值

证明方计算并发送每个多项式在 $ \zeta $ 点的值 $\vec{P}(\zeta)$，其中 $\vec{P}$ 是所有如下多项式的链接：

$$ \vec{P} = (\vec{C}, \vec{\sigma}, \vec{w}, \vec{Z}, \vec{\pi}, \vec{q}) $$

这样做的目的是将所有需要验证的多项式值统一在同一个点进行验证，从而避免逐项验证所带来额外开销。

3.8 使用 FRI 进行验证

证明方和验证方共同使用 FRI 协议进行一组批量验证（Batch FRI Protocol），其目标是验证以下形式的多项式是否满足对应关系：

$$ \vec{B} = \left( \frac{p_i(x) - p_i(\zeta)}{x - \zeta} \, \bigg| \, p_i \in \vec{P} \right) $$

在这个步骤中，FRI 通过多层次折叠（folding）与随机系数调整来确保多项式在验证点的值满足一致性条件。

3.9 验证约束一致性

验证方接收 $\vec{P}(\zeta)$ 的值，并对合并后的约束多项式 $c_i(\zeta)$ 进行验证，最终确保 $c_i(\zeta) = q_i(x) Z_H(x)$ 成立。

4. 总结与分析

有别于传统的Plonk，Plonky2 协议通过引入置换多项式和商多项式承诺，以降低多项式的次数，并并行化对多项式进行计算，实现了对电路内多项式关系的高效验证。同时，结合 FRI 批量验证进一步降低了验证方的计算负担。该协议的优势主要体现在以下几个方面：

1. 高效的多项式验证： FRI 技术的引入使得多项式验证变得更加高效，尤其在递归零知识证明和后量子安全场景中具有显著的计算优势。
2. 灵活的随机参数选择： Plonky2 中通过多次引入随机参数（$\beta, \gamma, \alpha$ 等），提高了多项式验证的随机性和安全性，确保了协议的零知识属性和安全性。
3. 支持递归验证： Plonky2 的设计允许其在递归场景中表现出色，适用于复杂的电路证明和多层次验证结构。