L2 — Deep Dive into zkSync circuit preprocessing

zkSync uses PLONK zero knowledge proof algorithm to generate proof. The logic of proof is implemented through enhanced bellman library. matter-labs has the open source code at plonk-release branch. Though zkSync uses PLONK zero knowledge proof algorithm, the construction of circuit still takes form of R1CS. In order to generate zkSync circuit proof, there are two steps in such logic: 1/circuit conversion 2/ PLONK proof generation. Circuit conversion is the preprocessing procedure of zkSync. This article focuses on the zkSync circuit preprocessing.

https://github.com/matter-labs/bellman.git

The last code submission mentioned in this article shows as follows:

commit f551a55d83d2ea604b2dbfe096fd9dcfdaedb189 (HEAD -> master)
Merge: 06c10c0 87d8496
Author: Alexander <alex.m.vlasov@gmail.com>
Date:   Tue Oct 13 17:06:24 2020 +0200
​
  Merge pull request #30 from matter-labs/plonk_release_cpu_flags_fix
   
  Fix CPU flags in blake2s

Everuthing starts from next_round function in core/prover/src/plonk_step_by_step_prover.rs. With known circuit, we generate the proof through the three steps below:

1. let setup = SetupForStepByStepProver::prepare_setup_for_step_by_step_prover(            
      instance.clone(),                                                                   
      self.config.download_setup_from_network,                                            
  )  
2. let vk = PlonkVerificationKey::read_verification_key_for_main_circuit(block_size)
3. let verified_proof = precomp
      .setup
      .gen_step_by_step_proof_using_prepared_setup(instance, &vk)

First step is preprocessing. Second step is getting verification key. Third step is generating the proof. As we can see, instance is the object of FranklinCircuit. Core logic is prepare_setup_for_step_by_step_prover function. This function is implemented in core/models/src/prover_utils/mod.rs:

pub fn prepare_setup_for_step_by_step_prover<C: Circuit<Engine> + Clone>(
        circuit: C,
        download_setup_file: bool,
    ) -> Result<Self, failure::Error> {
        let hints = transpile(circuit.clone())?;
        let setup_polynomials = setup(circuit, &hints)?;
        let size = setup_polynomials.n.next_power_of_two().trailing_zeros();
        let setup_power_of_two = std::cmp::max(size, SETUP_MIN_POW2); // for exit circuit
        let key_monomial_form = Some(get_universal_setup_monomial_form(
            setup_power_of_two,
            download_setup_file,
        )?);
        Ok(SetupForStepByStepProver {
            setup_power_of_two,
            setup_polynomials,
            hints,
            key_monomial_form,
        })
    }

The circuit preprocessing has two steps: 1/ Transpile 2/ Setup. Transpile takes the circuit from R1CS and converts into PLONK representative form. Let’s start with Transpile.

Transpile

transpile function is implemented in src/plonk/mod.rs. It implements the circuit conversion from R1CS to PLONK.

pub fn transpile<E: Engine, C: crate::Circuit<E>>(circuit: C) -> Result<Vec<(usize, TranspilationVariant)>, SynthesisError> {
    let mut transpiler = Transpiler::<E, PlonkCsWidth4WithNextStepParams>::new();
    circuit.synthesize(&mut transpiler).expect("sythesize into traspilation must succeed");
    let hints = transpiler.into_hints();
    Ok(hints)
}

Let us take a closer look at Transpiler definition:

pub struct Transpiler<E: Engine, P: PlonkConstraintSystemParams<E>> {
  current_constraint_index: usize,
  current_plonk_input_idx: usize,
  current_plonk_aux_idx: usize,
  scratch: HashSet<crate::cs::Variable>,
  deduplication_scratch: HashMap<crate::cs::Variable, usize>,
  transpilation_scratch_space: Option<TranspilationScratchSpace<E>>,
  hints: Vec<(usize, TranspilationVariant)>,
  n: usize,
}
​
pub enum TranspilationVariant {
  IntoQuadraticGate,
  IntoAdditionGate(LcTransformationVariant),
  MergeLinearCombinations(MergeLcVariant, LcTransformationVariant),
  IntoMultiplicationGate((LcTransformationVariant, LcTransformationVariant, LcTransformationVariant))
}

Note that hints in Transpiler is the type of each gate (module) of circuit. In fact, Transpile is the preprocess of circuit conversion. The result of Transpile is to get hints. The core logic of how an R1CS converts to PLONK circuit is implemented in enforce function of Transpile. For those of you familar with R1CS should know that the constraint form of an R1CS is A*B=C, with A/B/C possibly being linear combination of multiple variables.

let (a_has_constant, a_constant_term, a_lc_is_empty, a_lc) = deduplicate_and_split_linear_term::<E, Self>(a(crate::LinearCombination::zero()), &mut self.deduplication_scratch);
let (b_has_constant, b_constant_term, b_lc_is_empty, b_lc) = deduplicate_and_split_linear_term::<E, Self>(b(crate::LinearCombination::zero()), &mut self.deduplication_scratch);
let (c_has_constant, c_constant_term, c_lc_is_empty, c_lc) = deduplicate_and_split_linear_term::<E, Self>(c(crate::LinearCombination::zero()), &mut self.deduplication_scratch);

For each input R1CS constraint, let’s look at the type of A/B/C. Whether it is a fixed value, whether it is a combination of multiple variables. Take different conversion logic to deal with different combination of A/B/C. Take C*LC=C as an example:

(true, false, true) | (false, true, true) => {
...
​
  let (_, _, hint) = enforce_lc_as_gates(
      self,
      lc,
      multiplier,
      free_constant_term,
      false,
      &mut space
  ).expect("must allocate LCs as gates for constraint like c0 * LC = c1");
  ...
}

Take (A0) * (B0 + Blc) = C0 as another example. Here, A0, B0, C0 are fixed. The entire constraint can be converted to:

A0*B0-C0 + A0*Blc = 0

This is a common form, also the problem to be solved with enforce_lc_as_gates. A0*B0-C0 is the free_constant_term, A0 is multiplier，Blc is lc.

Before getting into the specific conversion logic, I want to talk about TranspilationScratchSpace. TranspilationScratchSpace saves information of a gate circuit, including variables, coefficients, and so on.

struct TranspilationScratchSpace<E: Engine> {
  scratch_space_for_vars: Vec<PlonkVariable>,
  scratch_space_for_coeffs: Vec<E::Fr>,
  scratch_space_for_booleans: Vec<bool>,
}

Note that, the number of coefficients of a constraint is greater than the number of a variables.

If an lc contains no more than combination of 4 variables, then one PLONK constraint can express it. That is to say no multiplication is needed; 5 additions can achieve it (with one fixed value).

If there are more than 4 variables involved, we need to combine multiple gates. The calculation of amount of extra gates listed below:

let cycles = ((lc.0.len() - P::STATE_WIDTH) + (P::STATE_WIDTH - 2)) / (P::STATE_WIDTH - 1);

Besides the first gate can support 4 variables, the other gates can process only 3 variables (P::STATE_WIDTH — 1). Gate connects with gate through the intermediate variables.

Setup

setup function is implemented in src/plonk/mod.rs. setup mainly calculates sigma function and gate coefficient function. As a matter of fact, these two functions are, indeed, the corresponding circuit expression of the PLONK algorithm.

pub fn setup<E: Engine, C: crate::Circuit<E>>(
  circuit: C,
  hints: &Vec<(usize, TranspilationVariant)>
) -> Result<SetupPolynomials<E, PlonkCsWidth4WithNextStepParams>, SynthesisError> {
  use crate::plonk::better_cs::cs::Circuit;
​
  let adapted_curcuit = AdaptorCircuit::<E, PlonkCsWidth4WithNextStepParams, _>::new(circuit, &hints);
​
  let mut assembly = self::better_cs::generator::GeneratorAssembly::<E, PlonkCsWidth4WithNextStepParams>::new();
​
  adapted_curcuit.synthesize(&mut assembly)?;
  assembly.finalize();
​
  let worker = Worker::new();
​
  assembly.setup(&worker)
}

AdaptorCircuit is the wrapper of ”R1CS“ circuit. Besides an R1CS Circuit, AdaptorCircuit also include hints information generated through Transpile. GeneratorAssembly implements the gate management logic in PLONK algirthm. In summary, the Synthesize process of an R1CS Circuit is shown in the figure below:

Adaptor implements the interface for ContraintSystem of R1CS, as well as the R1CS circuit conversion in enforce function. GeneratorAssembly maintains a collection of corresponding gates of PLONK circuits. The finalize function of GeneratorAssembly makes up the difference so it becomes power of 2.

One thing to highlight is, PLONK circuit does not match exactly the description in the paper. With bellman’s implementation, one gate circuit takes 4 arguments: a, b, c and d in stead of 3 arguments only: a, b and c.

pub struct PlonkCsWidth4WithNextStepParams;
impl<E: Engine> PlonkConstraintSystemParams<E> for PlonkCsWidth4WithNextStepParams {
  const STATE_WIDTH: usize = 4;
  const HAS_CUSTOM_GATES: bool = false;
  const CAN_ACCESS_NEXT_TRACE_STEP: bool = true;
​
  type StateVariables = [Variable; 4];
  type ThisTraceStepCoefficients = [E::Fr; 6];
  type NextTraceStepCoefficients = [E::Fr; 1];
​
  type CustomGateType = NoCustomGate;
}

STATE_WIDTH in the PlonkCsWidth4WithNextStepParams structure is the amount of variables corresponds to one gate.

setup function in GeneratorAssembly gets the sigma function and related coefficient polynomial from the gate expression.

pub fn setup(self, worker: &Worker) -> Result<SetupPolynomials<E, PlonkCsWidth4WithNextStepParams>, SynthesisError> {
      assert!(self.is_finalized);
​
      let n = self.n;
      let num_inputs = self.num_inputs;
​
      let [sigma_1, sigma_2, sigma_3, sigma_4] = self.make_permutations(&worker);
​
      let ([q_a, q_b, q_c, q_d, q_m, q_const],
          [q_d_next]) = self.make_selector_polynomials(&worker)?;
​
      drop(self);
​
      let sigma_1 = sigma_1.ifft(&worker);
      let sigma_2 = sigma_2.ifft(&worker);
      let sigma_3 = sigma_3.ifft(&worker);
      let sigma_4 = sigma_4.ifft(&worker);
​
      let q_a = q_a.ifft(&worker);
      let q_b = q_b.ifft(&worker);
      let q_c = q_c.ifft(&worker);
      let q_d = q_d.ifft(&worker);
      let q_m = q_m.ifft(&worker);
      let q_const = q_const.ifft(&worker);
​
      let q_d_next = q_d_next.ifft(&worker);
​
      let setup = SetupPolynomials::<E, PlonkCsWidth4WithNextStepParams> {
          n,
          num_inputs,
          selector_polynomials: vec![q_a, q_b, q_c, q_d, q_m, q_const],
          next_step_selector_polynomials: vec![q_d_next],
          permutation_polynomials: vec![sigma_1, sigma_2, sigma_3, sigma_4],
       
          _marker: std::marker::PhantomData
      };
​
      Ok(setup)
  }

Here the logic is clear. Calculate the permutation and selector polynomial points expression, and convert into the coefficient expression. make_selector_polynomials function implements selector polynomial point value calculation. This is rather simple. I want to dive a bit deeper into permutation calculation process.

partitions dataset length is the number of all variables. It records the lacation of each variable at corresponding gate. As an example:

partitions[3] = ((0, 1),(3, 2))

The third variable take the first variable of first gate (0, 1), and the second variable of the third gate (3,2). partitions helps gathering all gate information with the same variable. Through partitions information we can construct the sigma function.

Each gate is made up with 4 variables. Each variable of a specific fate has unique, consecutive index, shown as below:

for (i, partition) in partitions.into_iter().enumerate().skip(1) { //enumerate all variables
          // copy-permutation should have a cycle around the partition
...
          let permutation = rotate(partition.clone());
          permutations[i] = permutation.clone();
​
          for (original, new) in partition.into_iter() //construct the key value pair for gate location corresponds to same variable
                                  .zip(permutation.into_iter()) 
          {
              let new_zero_enumerated = new.1 - 1;
              let mut new_value = domain_elements[new_zero_enumerated]; //new gate variable index
​
              new_value.mul_assign(&non_residues[new.0]); //multiply by offset and obtain uniform index
              // check to what witness polynomial the variable belongs
              let place_into = match original.0 { //obtain original location information for same variable
                  0 => {
                      sigma_1.as_mut()
                  },
                  1 => {
                      sigma_2.as_mut()
                  },
                  2 => {
                      sigma_3.as_mut()
                  },
                  3 => {
                      sigma_4.as_mut()
                  },
                  _ => {
                      unreachable!()
                  }
              };
​
              let original_zero_enumerated = original.1 - 1;
              place_into[original_zero_enumerated] = new_value; //swapping
          }
      }

sigma_1/sigma_2/sigma_3/sigma_4 is the permutation function that’s asked for. The entire logic shows in below figure:

Summary:

Even though zkSync takes PLONK Zero knowledge proof algorithm, its circuit construction is developed with R1CS. zkSync ciucuit process includes: 1/circuit conversion 2/PLONK proof calculation. Transpile implements the circuit format conversion. The goal of circuit conversion is to get: 1/sigma function 2/ gate coefficient polynomial.