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/ 门系数多项式。