L2 — Deep into PLONK Aggregation circuit

PLONK algorithm requires trusted setup once, however, the complexity of the proof complexity is higher than Groth16 algorithm. PLONK algorithm has its advantage on trusted setup, since any of the circuit can share the initial configuration. Since any circuit can share SRS, PLONK algorithm itself has the proof validation logic, which can use SRS too. That is to say, based on PLONK algorithm we can construct the validation circuit, so that cased on PLONK algorithm we can prove PLONK validation.

Matter-Labs has open sourced the PLONK algorithm validation circuit. It can prove multiple PLONK proofs, corresponding code as follows:

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

The lines of code is relatively small, everything starts from synthesize in RecursiveAggregationCircuit.

synthesize function

synthesize logic is rather clear. The whole circuit implements following features:

1/ circuit proves validity of all proofs.

2/ verify if vks are the appointed ones saved in Smart Contract are the vks corresponded to “validation” proof

3/ packing all public input information with sha256 algorithm

the entire logic shows in below graph. The 1/2/3 are related features.

Step 2/3 are rather easy to understand. Core is in step 1. aggregrate_proof function implements circuit to validate if a proof is correct.

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);
}

There are two outputs after validation: pair_with_generator and pair_with_x.

Check PlonK algorithm validation logic and we can find that, the last step of verification is to validate the two pairing functions:

The left side pairing function is x, while pairing function on the right side has g2 value 1(generator). If we check the function aggregate_proof, we can see that this validation circuit does not validate if the pairing function results are equal. Therefore, the validation circuit does not have complete proof process.

aggregate_proof proves that pair_with_generator and pair_with_x calculation are right. Folks interested can check out these functions. The pair_with_generator and pair_with_x “aggregated” together after acquiring all proofs.

In order to avoid take, “aggregation” takes a random factor:

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)?;

Binding the proof information we generate random information. aggregation_challenge is the random factor. We mark it as 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;
}

Each pair_with_generator/x has coefficient c^n. After obtaining coefficients for all points, we “aggregate” all points by using 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,
)?;

The whole flow shows below:

Through this method, we turned the validation calculation which is required for each proof’s pairing function into one validation calculation for the pairing function. Pay attention that the validation of pairing function did not happen inside the circuit, but conducted inside “smart contract”. Let’s check out the verify_recursive in contract/PlonkCore.sol:

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;
}

This function checks if the submitted aggregation proof is correct by using aggregate_for_verification function. After ensuring its validity, use PairingsBn254.pairingProd2 to check the validity of aggregated pair_with_x/generator.

So far, we can see that this is an aggregation proof validation circuit, and it is capable of validate multiple proofs based on PlonK. After we understand synthesize function, then the interface functions are rather easy to undrstand: create_recursive_circuit_vk_and_setup and proof_recursive_aggregate_for_zksync. You can go ahead read the the definitions in interested.

The core of circuits is the proof of circuit. PlonK algorithm proofs are based on “points”. The essense of this calculation is how the circuit proves one point on the ellipsis curve.

Point calculation proof

Point calculation circuit is implemented in the franklin-crypto library located at src/plonk/circuit/curve/sw_affine.rs file.

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

Circuit proof multiexp takes the NAF table look-uscheme. After scalar calculated from each bit in the order from high to low, we use double-add. MultiexpTable is NAF established table.

Interestingly, we can see the implementation of points on 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,
}

In order to simulate Fq points on Fr, Fq points are divided into multiple Limbs. Each Limb has its own independent variable. If you are interested, please check out the specific point calculation and Multiexp circuit proof on your own.

Conclusion:

Matter-Labs has open sourced PLONK algorithm validation circuit, which implements multiple aggregation proofs for PLONK proof. Aggregation circuit proves a certain proof validation, and ensures that the VK used is correct. Note that, last step of PLONK algorithm validation (pairing function) is not proved in the circuit, but relies on the smart contract to prove.