Plonky2 介绍

2023-08-07 本文已影响0人雪落无留痕

Plonky2由Polygon Zero Team开发，主要可以实现快速递归，只需要300ms即可生成一个递归证明。

Plonky2 数值化基于TurboPLONK, 但承诺方案采用FRI, 采用64位的Goldilocks域。

Plonky2可以将任意多的证明收缩为43KB。

域的选择

Plonky2 采用素域 $p = 2^{64}-2^{32}+1$ ，采用64位的字，可以加速些底层运算。

扩域采用 $\mathbb{F}_p[X]/(X^2-7)$ .

PLONK 算术化

基于TurboPLONK, Plonky2 广泛使用定制门。

Filtering constraints

对于 $k$ 个多项式，采用 $k$ 个过虑多项式将大幅增加协议的代价，可以其它批量处理。

其中 $f_j(x)$ 的次数为 $n-1$ , 为了降低次数，可以将电路分成多个子集。

定义 $f(x)$ 为：
$f(g^i) = j$
若第 j 个门电路用在第 i 行；

则第 j 个定制电路的过滤多项式为：
$f_j(x) = \prod_{k=0,k\neq j}^{n-1}(f(x)-k)$
它在第j 个定制电路的值为非零。

Advice wires

若是某个列不需要参与Plonk 置换证明，例如对于除法，它逆单独作为一列，这种称为advice wires.

它不参与置换，可以减少置换多项式的次数，减少证明大小和验证者的代价。

Cumulative products

Plonk的置换多项式为度数为 $r+1$ 的约束：
$Z(x)\prod_{i=1}^rf_i'(x)=Z(gx)\prod_{i=1}^rg_i'(x)$

为了获取低度约束条件，可以将上述乘积为大小为8的块，引入多项式 $\pi_i(x)$ ，定义 $s = \lfloor r/8\rfloor$ , 可以得到：
$\pi_1(x)=Z(x)\prod_{i=1}^8f_i'(x)/g_i'(x) \\ \pi_2(x)=\pi_1(x)\prod_{i=9}^{16}f_i'(x)/g_i'(x) \\ ...\\ Z(gx)=\pi_s(x)\prod_{i=8s+1}^rf_i'(x)/g_i'(x)$

Boosting soundness

由于域的大小与安全性成反比，为了提升安全性，需要将置换和约束组合证明重复 $r$ 次。

公开输入

公开输入采用PublicInputGate, 主要有以下约束：
$w_1(x) = h_1, \\ w_2(x) = h_2, \\ w_3(x) = h_3, \\ w_4(x) = h_4, \\$

零知识性

通过添加随机的列盲化trace多项式和 $Z_H(x)$

对于FRI，其定义域放在 $H$ 的陪集中，并采用基于hash的向量承诺。

Hashing

Plonky2采用 $Poseidon^\pi$ , 宽度为12个域元素，S盒为 $x^7$ ，采用 8 满轮和22个部分轮变换，实现128位的安全性。

Plonky2 采用PoseidonGate 定制电路，这可能导致宽的列，Plonky2 使用135列，这是达到证明大小和FRI验证复杂的平衡。

最终协议

定义 $r$ 为重复的参数， $Com(\ \overrightarrow{p}\ )$ 表示多项式向量的承诺，即对于多项式的每个叶子节点，对于 $x\in H$ , 包含值 $p_1(x), \cdots, p_k(x)$ 。

预处理

P 和 V 构造电路并计算 $\overrightarrow{C}$ ，表示电路上的常量多项式，和 $\overrightarrow{\sigma}$ ，用以编码置换；
P, V构建包含 $\overrightarrow{C}$ 和 $\overrightarrow{\sigma}$ 的的Merkle树；
P存储Merkle 树，作为Proving key；
V存储 $Com(\overrightarrow{C}, \overrightarrow{\sigma})$ 作为Verification key；

主协议

P 生成 witness $\overrightarrow{w}$ ，并给V 发送 $Com(\overrightarrow{w})$ ;
V 抽样获取 $\beta_1, \cdots, \beta_r, \gamma_1,\cdots, \gamma_r$ 作为置换证明的随机数；
P 发送 $Com(\overrightarrow{Z},\overrightarrow{\pi})$ , 作为置换多项式 $Z(x)$ 和部分乘积多项式 $\pi(x)$ ;
V 抽样获取 $\alpha_1, \cdots, \alpha_r \in \mathbb{F}_p$ ，作为组合约束条件的随机数；
P 发送 $Com(\overrightarrow{q})$ , 作为商多项式 $q(x)$ 的承诺；

$q_i(x) = C_i(x)/Z_H(x)$

V 抽象 $\zeta \in \mathbb{F}_p(\phi)$ , 用来测试多项式之间的恒等关系；
P 发送 $\overrightarrow{P}(\zeta)$ , 其中 $\overrightarrow{P}$ 包含多个多项式 $\overrightarrow{P} = (\overrightarrow{C},\overrightarrow{\sigma},\overrightarrow{w},\overrightarrow{Z},\overrightarrow{\pi},\overrightarrow{q})$ ;
P 计算 $\overrightarrow{P}$ , 和 V 参与到FRI 协议中:

$\overrightarrow{B}=(\frac{p_i(x)-p_i(\zeta)}{x-\zeta}|p_i\in \overrightarrow{P})$

V 利用 $\overrightarrow{P}(\zeta)$ 计算 $c_1(\zeta), \cdots, c_r(\zeta)$ ，并验证 $c_i(\zeta) = q_i(\zeta)Z_H(\zeta)$

FRI 协议

V 抽样获取 $\alpha \in \mathbb{F}(\phi)$ ，主要将 $\overrightarrow{B}$ 转换为指定的码字；
P 发送 $Com(h_0)$ , $h_0$ 为 DEEP组合多项式：

$h_0(x)=\sum_{i=0}^{|\overrightarrow{B}|-1}\alpha^i\overrightarrow{B_i}(x)$

P， V执行 FRI 承诺阶段，对于每个约减参数 $l_i$ ,

(a) V抽样 $\beta \in\mathbb{F}(\phi)$ ,

(b) P 重写 $h_i(x)$ 为：
$h_i(x) = \sum_{j=0}^{l_i-1}x^jh_{i,j}(x^{l_i})$
P 生成承诺 $Com(h_{i+1})$ , 其中
$h_{i+1}(x) = \sum_{j=0}^{l_i-1}\beta^jh_{i,j}(x)$
V抽样 $\tau \in \mathbb{F}_p^4$
P 执行 grinding, 并发送 PoW的见证参数 $u$ ;
V 断言 $H(\tau, \mu)$ 包含 proof of work bits前面的0；
V抽样获取 num_query_rounds的随机索引 $q_1,\cdots, q_k \in \{0, \cdots, n-1\}$ ;
对于每个索引 $q_i$ :

(a) P 发送 $\overrightarrow{P}$ 的估值和每个 $h_i(x)$

(b) V 验证在 $x$ 的一系列一致性检查，首先是在 $\overrightarrow{P}(x)$ 和 $h_0(x)$ ，然后是在每个 $(h_i(x), h_{i+1}(x))$ 对之间。

示例

使用plonky2写个关于x^2-4x+7的电路证明示例为：

use anyhow::Result;
use plonky2::field::types::Field;
use plonky2::iop::witness::{PartialWitness, Witness};
use plonky2::plonk::circuit_builder::CircuitBuilder;
use plonky2::plonk::circuit_data::CircuitConfig;
use plonky2::plonk::config::{GenericConfig, PoseidonGoldilocksConfig};

/// An example of using Plonky2 to prove a statement of the form
/// "I know x² - 4x + 7".
fn main() -> Result<()> {
    const D: usize = 2;
    type C = PoseidonGoldilocksConfig;
    type F = <C as GenericConfig<D>>::F;

    let config = CircuitConfig::standard_recursion_config();
    let mut builder = CircuitBuilder::<F, D>::new(config);

    // The arithmetic circuit.
    let x = builder.add_virtual_target();
    let a = builder.mul(x, x);
    let b = builder.mul_const(F::from_canonical_u32(4), x);
    let c = builder.mul_const(F::NEG_ONE, b);
    let d = builder.add(a, c);
    let e = builder.add_const(d, F::from_canonical_u32(7));

    // Public inputs are the initial value (provided below) and the result (which is generated).
    builder.register_public_input(x);
    builder.register_public_input(e);
    let mut pw = PartialWitness::new();
    pw.set_target(x, F::from_canonical_u32(1));
    let data = builder.build::<C>();
    let proof = data.prove(pw)?;
    println!(
        "x² - 4 *x + 7 where x = {} is {}",
        proof.public_inputs[0],
        proof.public_inputs[1]
    );
    data.verify(proof)
}