L2 – 深入理解zkSync电路预处理

zkSync使用PLONK零知识证明算法生成证明。证明的生成逻辑是通过增强的bellman库实现。matter-labs开源了相关的代码，请查看plonk-release分支。zkSync虽然采用PLONK零知识证明算法，但是电路的搭建开发采用的R1CS形式。为了生成zkSync的电路证明，逻辑上需要两步：1/电路转换 2/ PLONK证明计算。电路转换就是zkSync电路预处理过程。本文重点分析zkSync电路预处理过程。 https://github.com/matter-labs/bellman.git 文章中涉及的代码的最后一个提交信息如下： “` commit f551a55d83d2ea604b2dbfe096fd9dcfdaedb189 (HEAD -> master) Merge: 06c10c0 87d8496 Author: Alexander 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 “` 一切从core/prover/src/plonk_step_by_step_prover.rs的next_round函数开始。在已知电路的情况下，通过如下的三步计算生成证明： “` 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) “` 第一步就是预处理，第二步是获取verification密钥，第三步开始生成证明。其中instance就是FranklinCircuit对象。核心逻辑是prepare_setup_for_step_by_step_prover函数。该函数实现在core/models/src/prover_utils/mod.rs中： “` pub fn prepare_setup_for_step_by_step_prover + Clone>( circuit: C, download_setup_file: bool, ) -> Result { 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, }) } “` 电路预处理的两个步骤：1/ Transpile 2/ Setup。Transpile是将电路从R1CS形式，转换成PLONK表示形式。从Transpile讲起。 ## Transpile transpile函数实现在src/plonk/mod.rs，实现电路的转换，从R1CS转换到PLONK形式。 “` pub fn transpile>(circuit: C) -> Result, SynthesisError> { let mut transpiler = Transpiler::::new(); circuit.synthesize(&mut transpiler).expect("sythesize into traspilation must succeed"); let hints = transpiler.into_hints(); Ok(hints) } “` 仔细看看Transpiler的定义： “` pub struct Transpiler> { current_constraint_index: usize, current_plonk_input_idx: usize, current_plonk_aux_idx: usize, scratch: HashSet, deduplication_scratch: HashMap, transpilation_scratch_space: Option>, hints: Vec, n: usize, } pub enum TranspilationVariant { IntoQuadraticGate, IntoAdditionGate(LcTransformationVariant), MergeLinearCombinations(MergeLcVariant, LcTransformationVariant), IntoMultiplicationGate((LcTransformationVariant, LcTransformationVariant, LcTransformationVariant)) } “` 特别注意Transpiler中的hints，是电路的每个门（模块）的类型。其实Transpile是电路转换的预处理，Transpile的结果就是获取hints。一个R1CS电路是如何转换成PLONK电路的核心逻辑在Transpile的enforce函数。熟悉R1CS形式的小伙伴知道，一个R1CS的约束形式是A*B=C。其中A/B/C都有可能是多个变量的线性组合。 “` let (a_has_constant, a_constant_term, a_lc_is_empty, a_lc) = deduplicate_and_split_linear_term::(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::(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::(c(crate::LinearCombination::zero()), &mut self.deduplication_scratch); “` 对输入的每一个R1CS约束，查看A/B/C的类型，是否是固定值，是否是多变量组合。针对A/B/C的不同组合，确定不同的转换逻辑。以C*LC=C为例： “` (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 + Blc) = C0为例，其中，A0，B0，C0都是固定值。整个约束可以变换为: “` A0*B0-C0 + A0*Blc = 0 “` 这个形式是个通用形式，也就是enforce_lc_as_gates需要解决的问题。A0*B0-C0就是free_constant_term，A0就是multiplier，Blc就是lc。 介绍具体的转换逻辑之前，介绍一下TranspilationScratchSpace。TranspilationScratchSpace存储一个门电路对应的相关信息，包括变量，系数等等。 “` struct TranspilationScratchSpace { scratch_space_for_vars: Vec, scratch_space_for_coeffs: Vec, scratch_space_for_booleans: Vec, } “` 注意的是，一个约束的系数比变量的个数要多。  如果一个lc不超过4个变量的组合，一个PLONK约束就可以表示。也就是不需要乘法，只需要5个加法（其中有个固定值）。 如果超过4个变量，需要多个门进行组合。额外需要的门数计算如下： “` let cycles = ((lc.0.len() – P::STATE_WIDTH) + (P::STATE_WIDTH – 2)) / (P::STATE_WIDTH – 1); “` 除了第一个门能支持4个变量外，其他额外的门只能处理3个变量（P::STATE_WIDTH – 1）。门与门之间通过中间变量进行“连接”：  ## Setup setup函数实现在src/plonk/mod.rs。setup主要是计算sigma函数和门系数函数。事实上，这两个函数“就是”PLONK算法对应的电路表示。 “` pub fn setup>( circuit: C, hints: &Vec ) -> Result, SynthesisError> { use crate::plonk::better_cs::cs::Circuit; let adapted_curcuit = AdaptorCircuit::::new(circuit, &hints); let mut assembly = self::better_cs::generator::GeneratorAssembly::::new(); adapted_curcuit.synthesize(&mut assembly)?; assembly.finalize(); let worker = Worker::new(); assembly.setup(&worker) } “` AdaptorCircuit是”R1CS“电路的Wrapper。AdaptorCircuit除了包括一个R1CS的Circuit外，还包括Transpile生成的hints信息。GeneratorAssembly实现了PLONK算法对应的门管理的逻辑。简单的说，一个R1CS的Circuit的Synthesize的过程如下图：  Adaptor实现了R1CS的ContraintSystem接口，并在enforce函数实现了R1CS电路转换。GeneratorAssembly中维护了PLONK电路对应的门的形式。GeneratorAssembly的finalize函数将电路的门的个数补齐到2的幂次。 特别注意的是，PLONK电路并不是完全和论文中一致。在bellman的实现中，一个门电路采用的是四个变量：a，b，c和d，而不是三个变量：a，b和c。 “` pub struct PlonkCsWidth4WithNextStepParams; impl PlonkConstraintSystemParams 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; } “` PlonkCsWidth4WithNextStepParams结构体中的STATE_WIDTH就是一个门对应的变量个数。 GeneratorAssembly的setup函数从门的表示，获取sigma函数和门对应的系数多项式。 “` pub fn setup(self, worker: &Worker) -> Result, 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:: { 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) } “` 逻辑比较清晰明了，计算permutation和selector多项式的点值表示，并换算到系数表示。make_selector_polynomials函数实现selector多项式的点值计算，相对简单。详细说说permutation的计算过程。 partitions数组的长度为所有变量的个数，记录的每个变量在每个门对应的位置。举个例子： “` partitions[3] = ((0, 1),(3, 2)) “` 第三个变量用在第一个门的第一个变量（0，1）和第三个门的第二个变量(3，2)。partitions帮助找出了使用同一个变量的所有的门的信息。通过partitions的信息可以构造sigma函数。 每个门由4个变量组成，每个门的每个变量的位置有独立连续的编号，如下图所示：  “` for (i, partition) in partitions.into_iter().enumerate().skip(1) { //枚举所有的变量 // 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() //构造同一变量对应的门的位置对 .zip(permutation.into_iter()) { let new_zero_enumerated = new.1 – 1; let mut new_value = domain_elements[new_zero_enumerated]; //新对应的门的变量的编号 new_value.mul_assign(&non_residues[new.0]); //乘以偏移，得到统一编号 // check to what witness polynomial the variable belongs let place_into = match original.0 { //获取同一个变量对应的原有位置信息 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; //进行置换 } } “` sigma_1/sigma_2/sigma_3/sigma_4就是需要求取的“置换”函数。整个逻辑如下图所示：  ## 总结： zkSync虽然采用PLONK零知识证明算法，但是电路的搭建开发采用的R1CS形式。zkSync电路处理包括：1/电路转换 2/PLONK证明计算。Transpile实现了电路的格式转换。电路转换的目的是获取：1/sigma函数 2/ 门系数多项式。 

commit f551a55d83d2ea604b2dbfe096fd9dcfdaedb189 (HEAD -> master) Merge: 06c10c0 87d8496 Author: Alexander  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 + Clone>(  circuit: C,  download_setup_file: bool,  ) -> Result {  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,  })  }

 pub fn transpile>(circuit: C) -> Result, SynthesisError> {  let mut transpiler = Transpiler::::new();   circuit.synthesize(&mut transpiler).expect("sythesize into traspilation must succeed");   let hints = transpiler.into_hints();   Ok(hints)  }

pub struct Transpiler> {  current_constraint_index: usize,  current_plonk_input_idx: usize,  current_plonk_aux_idx: usize,  scratch: HashSet,  deduplication_scratch: HashMap,  transpilation_scratch_space: Option>,  hints: Vec,  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::(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::(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::(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 {  scratch_space_for_vars: Vec,  scratch_space_for_coeffs: Vec,  scratch_space_for_booleans: Vec, }

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

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

pub struct PlonkCsWidth4WithNextStepParams; impl PlonkConstraintSystemParams 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, 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:: {  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) { //枚举所有的变量  // 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() //构造同一变量对应的门的位置对  .zip(permutation.into_iter())   {  let new_zero_enumerated = new.1 - 1;  let mut new_value = domain_elements[new_zero_enumerated]; //新对应的门的变量的编号   new_value.mul_assign(&non_residues[new.0]); //乘以偏移，得到统一编号   // check to what witness polynomial the variable belongs  let place_into = match original.0 { //获取同一个变量对应的原有位置信息  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; //进行置换  }  }

部分转自网络，侵权联系删除www.interchains.cchttps://www.interchains.cc/20822.html