# Plonky2协议简析

## 简介
Plonky2 是一个基于多项式承诺和基于 Plonk 的 PIOP 交互式证明的 zkSNARK 协议，致力于通过 FRI 技术实现高效的 zkSNARK。Plonky2 的主要目标是提高传统 zkSNARK 在递归零知识证明场景中的效率，同时增强后量子安全性。其核心理念是利用 FRI（Fast Reed-Solomon Interactive Oracle Proof of Proximity）实现高效的多项式验证，并使用随机抽样来增强协议的完整性和安全性。

在这篇文章中，将分析Plonky2协议的主要步骤和构造逻辑，并探讨如何用抗碰撞的哈希函数代替验证者的随机挑战，从而将协议转变为非交互式证明系统。

## 预处理
### 构造电路和相应的多项式
在预处理阶段，证明者（P）和验证者（V）共同构建电路并计算一组多项式向量$\vec{C}$和$\vec{\sigma}$这些多项式对每个电路门的常数和扩展排列进行编码，这些多项式表示电路内的关系和操作。

具体来说，$\vec{C}$包含对门常数和中间变量的约束（门约束），而$\vec{\sigma}$表示扩展置换的信息，又称复制约束。这些在后面的多项式置换和零知识证明过程中起到关键作用。
### 构建Merkle树
P 和 V 哈希的评估$\vec{C}$和$\vec{\sigma}$构建Merkle树，这棵树不仅压缩了证明的大小，而且在后续的多项式一致性验证中提供了高效的数据认证结构。
### P存储验证密钥
V存储$Com(\vec{C}, \vec{\sigma})$，作为验证密钥，以确保在后续步骤验证多项式与电路的关系时保持一致。

优化：通常，在实现中，我们使用 Merkle 帽（部分子树节点）代替 Merkle 根，以减少最终 Merkle 证明的大小。

## 主要协议
### 生成见证和多项式承诺
证明者生成见证向量$\vec{w}$（电路的私有输入）并计算其多项式形式$w(x)$. 然后，证明者使用 FRI 协议生成对多项式 (Merkle 根)的承诺$Com(\vec{C}, \vec{\sigma})$并将其发送给验证者。
### 验证者样本随机挑战
验证者随机选择$\beta_{1}, \ldots, \beta_{r}, \gamma_{1}, \ldots, \gamma_{r}$在有限域中$\mathbb F_p$这些随机参数将用于后续置换多项式的验证，以保证协议的完备性。
### 发送排列多项式和中间多项式承诺
P 发送置换多项式的承诺$Z(x)$和乘积多项式$\pi(x)$作为$Com(\vec{Z}, \vec{\pi})$，保证副本约束的一致性。

置换多项式是为了验证变量之间的一致性（即复制约束是否成立），乘积多项式是为了验证中间变量计算的正确性（减少多项式次数，允许并行计算以提高效率）。
### 验证者抽样新的随机参数
验证者对另一组随机参数进行采样$\alpha_{1}, \ldots, \alpha_{r}$将多个约束通过随机的线性组合进行组合，通过引入不同的随机系数，简化了验证过程。
### 生成并发送商多项式承诺
证明者使用 FRI 协议构建 Merkle 树并生成商多项式$q_i(x)$并做出相应的承诺Com(\vec{q})。商多项式采用以下形式：
$$
q_i(x) = \frac{C_i(x)}{z_H(x)},
$$
在哪里$C_i(x)$是使用随机线性组合对约束进行组合后的约束多项式。它表示合并后的约束，并且$Z_{H}(x)=x^{n}-1$
是集合上的消失多项式$H$，多项式在特定域上消失$H$（即，它可以被消失多项式分解）。
### 验证者样本验证点
验证者选择一个新的随机点$\zeta \in F_p$验证此时商多项式与约束多项式的一致性。
### P 在验证点发送多项式的求值结果
证明者计算并发送点处所有多项式的求值$\zeta$，表示$\vec{P}(\zeta)$， 在哪里$\vec{P}$表示以下链接多项式：
$$
\vec{P}=(\vec{c},\vec{\sigma},\vec{w},\vec{Z},\vec{\pi},\vec{q}).
$$
此步骤旨在将所有多项式值的验证压缩到单点，避免逐一验证的开销。
### 使用FRI进行验证
Prover 和 Verifier 共同使用 FRI 协议进行批量验证（Batch FRI Protocol），目标是验证如下多项式是否满足一致性条件：
$$
\vec{B}=(\frac{p_{t}(x)-p_{t}(\zeta)}{x-\zeta}|p_{t}\in\vec{P}).
$$
在此步骤中，FRI采用多层折叠和随机系数调整来确保多项式值在验证点处的一致性。
### 验证约束一致性
验证者接收以下值$\vec{P}(\zeta)$并验证合并的约束多项式$c_i(\zeta)$确保$c_i(\zeta) = q_i(x)Z_H(x)$持有。

## 协议摘要和分析
与传统Plonk不同，Plonky2引入置换多项式和商多项式承诺，降低多项式次数，并行化多项式计算，实现电路内多项式关系的高效验证。结合FRI的批量验证，可以大幅降低验证者端的计算开销。协议的优势主要体现在以下几个方面：
1. **高效多项式验证**
FRI技术的引入使得多项式验证更加高效，特别是在递归零知识证明和后量子安全场景中。
2. **灵活随机参数选择**
Plonky2 通过引入多个随机参数来增强安全性（$\beta, \gamma, \alpha$等）贯穿整个协议，确保零知识属性和安全性。
2. **支持递归验证**
Plonky2 的设计旨在在递归场景中表现出色，使其适用于复杂的电路证明和多层验证结构。