L2 — Deep Dive into zkSync circuit preprocessing

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

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)
}
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))
}
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);
(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");
...
}
A0*B0-C0 + A0*Blc = 0
struct TranspilationScratchSpace<E: Engine> {
scratch_space_for_vars: Vec<PlonkVariable>,
scratch_space_for_coeffs: Vec<E::Fr>,
scratch_space_for_booleans: Vec<bool>,
}
let cycles = ((lc.0.len() - P::STATE_WIDTH) + (P::STATE_WIDTH - 2)) / (P::STATE_WIDTH - 1);

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)
}
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;
}
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)
}
partitions[3] = ((0, 1),(3, 2))
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
}
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Trapdoor-Tech

Trapdoor-Tech

Trapdoor-Tech tries to connect the world with zero-knowledge proof technologies. zk-SNARK/STARK solution and proving acceleration are our first small steps :)