链眼社区:专注于区块链安全,区块链数据分析, 区块链信息整合,区块链技术服务和区块链技术咨询。

L2 - 深入 PLONK 聚合电路
shijiang
2022-06-10 09:46:24

PLONK 算法需要一次可信设置,但证明复杂度高于 Groth16 算法。PLONK 算法在可信设置方面具有优势,因为任何电路都可以共享初始配置。由于任何电路都可以共享 SRS,因此 PLONK 算法本身具有证明验证逻辑,也可以使用 SRS。也就是说,基于PLONK算法我们可以构造验证电路,这样就可以在PLONK算法的基础上证明PLONK验证。

Matter-Labs 开源了 PLONK 算法验证电路。可以证明多个PLONK证明,对应代码如下:

https://github.com/matter-labs/recursive_aggregation_circuit

代码行数比较少,一切都是从 RecursiveAggregationCircuit 中的综合开始。

一. 综合功能

综合逻辑比较清楚。整个电路实现以下特点:

1/ 电路证明所有证明的有效性。

2/验证vks是否是智能合约中保存的指定vks是“validation proof”对应的vks

3/ 使用 sha256 算法打包所有公共输入信息

整个逻辑如下图所示。1/2/3 是相关的特征。

步骤 2/3 相当容易理解。核心在步骤 1。aggregrate_proof 函数实现电路以验证证明是否正确。

let mut pairs_for_generator = vec![];
let mut pairs_for_x = vec![];
​
for proof_idx in 0..self.num_proofs_to_check {
  let proof = &proof_witnesses[proof_idx];
  let vk = &vk_witnesses[proof_idx];
​
  let [pair_with_generator, pair_with_x] = aggregate_proof::<_, _, T, CS::Params, P, _, _>(
      cs,
      self.transcript_params,
      &proof.input_values,
      &vk,
      &proof,
      &self.aux_data,
      self.rns_params,
  )?;
​
  pairs_for_generator.push(pair_with_generator);
  pairs_for_x.push(pair_with_x);
}

验证后有两个输出:pair_with_generator 和 pair_with_x。

查看 PlonK 算法验证逻辑,我们可以发现,验证的最后一步是验证两个配对函数:

左边的配对函数是 x,而右边的配对函数的 g2 值为 1(生成器)。如果我们检查函数 aggregate_proof,我们可以看到这个验证电路不验证配对函数结果是否相等。因此,验证电路没有完整的证明过程。

aggregate_proof 证明 pair_with_generator 和 pair_with_x 计算是正确的。有兴趣的朋友可以看看这些功能。在获得所有证明后,pair_with_generator 和 pair_with_x “聚合”在一起。

为了避免采取,“聚合”采取随机因素:

let mut sponge = StatefulRescueGadget::<E>::new(self.rescue_params);
​
for w in fs_witnesses.into_iter() {
  sponge.absorb_single_value(cs, w, self.rescue_params)?;
}
​
sponge.pad_if_necessary(self.rescue_params)?;
​
let aggregation_challenge = sponge
  .squeeze_out_single(cs, self.rescue_params)?
  .into_allocated_num(cs)?;

绑定证明信息我们生成随机信息。aggregation_challenge 是随机因素。我们将其标记为 c。

let mut scalars = vec![];
scalars.push(aggregation_challenge.clone());
​
let mut current = aggregation_challenge.clone();
for _ in 1..self.num_proofs_to_check {
  let new = current.mul(cs, &aggregation_challenge)?;
  scalars.push(new.clone());
​
  current = new;
}

每个pair_with_generator/x都有系数c^n。在获得所有点的系数后,我们使用 multiexp 对所有点进行“聚合”。

let pair_with_generator = WP::multiexp(
  cs,
  &scalars,
  &pairs_for_generator,
  None,
  self.rns_params,
  &self.aux_data,
)?;
let pair_with_x = WP::multiexp(
  cs,
  &scalars,
  &pairs_for_x,
  None,
  self.rns_params,
  &self.aux_data,
)?;

整个流程如下图:

通过这种方法,我们将每个证明的配对函数所需的验证计算变成了配对函数的一次验证计算。请注意,配对功能的验证不是在电路内部进行的,而是在“智能合约”内部进行的。让我们看看 contract/PlonkCore.sol 中的 verify_recursive:

function verify_recursive(
  Proof memory proof,
  VerificationKey memory vk,
  uint256 recursive_vks_root,
  uint8 max_valid_index,
  uint8[] memory recursive_vks_indexes,
  uint256[] memory individual_vks_inputs,
  uint256[16] memory subproofs_limbs
) internal view returns (bool) {
  (uint256 recursive_input, PairingsBn254.G1Point[2] memory aggregated_g1s) = reconstruct_recursive_public_input(
      recursive_vks_root, max_valid_index, recursive_vks_indexes,
      individual_vks_inputs, subproofs_limbs
  );
​
  assert(recursive_input == proof.input_values[0]);
​
  (bool valid, PairingsBn254.G1Point[2] memory recursive_proof_part) = aggregate_for_verification(proof, vk);
  if (valid == false) {
      return false;
  }
​
  // aggregated_g1s = inner
  // recursive_proof_part = outer
  PairingsBn254.G1Point[2] memory combined = combine_inner_and_outer(aggregated_g1s, recursive_proof_part);
​
  valid = PairingsBn254.pairingProd2(combined[0], PairingsBn254.P2(), combined[1], vk.g2_x);
​
  return valid;
}

该函数使用 aggregate_for_verification 函数检查提交的聚合证明是否正确。确保其有效性后,使用 PairingsBn254.pairingProd2 来检查聚合的 pair_with_x/generator 的有效性。

到目前为止,我们可以看到这是一个聚合证明验证电路,它能够验证基于 PlonK 的多个证明。了解了综合函数之后,接口函数就比较容易理解了:create_recursive_circuit_vk_and_setup 和 proof_recursive_aggregate_for_zksync。您可以继续阅读感兴趣的定义。

电路的核心是电路的证明。PlonK 算法证明基于“点”。这个计算的本质是电路如何证明椭圆曲线上的一个点。

二. 积分计算证明

点计算电路在位于 src/plonk/circuit/curve/sw_affine.rs 文件的 franklin-crypto 库中实现。

pub fn multiexp<CS: ConstraintSystem<E>>(
  cs: &mut CS,
  scalars: &[Num::<E>],
  points: &[Self],
  bit_limit: Option<usize>
) -> Result<Self, SynthesisError> {

电路证明 multiexp 采用 NAF 表外观方案。在从高到低的顺序从每个位计算出标量后,我们使用双加。MultiexpTable 是 NAF 建立的表。

有趣的是,我们可以看到点在 Fq(AffinePoint) 上的实现:

pub struct AffinePoint<'a, E: Engine, G: CurveAffine> where <G as CurveAffine>::Base: PrimeField {
  pub x: FieldElement<'a, E, G::Base>,
  pub y: FieldElement<'a, E, G::Base>,
  pub value: Option<G>,
}
​
pub struct FieldElement<'a, E: Engine, F: PrimeField>{
  // this is kind-of normal UintX limbs
  pub binary_limbs: Vec<Limb<E>>,
  // we can not multiply by power of modulus of our base field E,
  // so we keep only one single limb
  pub base_field_limb: Term<E>,
​
  pub representation_params: &'a RnsParameters<E, F>,
  pub value: Option<F>,
}
​
pub struct Limb<E: Engine> {
  pub term: Term<E>,
  pub max_value: BigUint,
}

为了模拟Fr上的Fq点,将Fq点分为多个Limbs。每个肢体都有自己的自变量。有兴趣的请自行查看具体的点计算和Multiexp电路证明。

三.结论

Matter-Labs 开源了 PLONK 算法验证电路,实现了 PLONK 证明的多重聚合证明。聚合电路证明一定的证明验证,并确保使用的 VK 是正确的。注意,PLONK算法验证的最后一步(配对功能)在电路中没有得到证明,而是依靠智能合约来证明。

文章翻译自: https://starli.medium.com/l2-deep-into-plonk-aggregation-circuit-d9928ccd0749