作者：ZKSwap
上篇⽂章中，我們研讀了ZKSync中better_cs如何⽣成single proof、aggregation proof的電路邏輯等實現。在這篇⽂章中，我們繼續研讀ZKSync的聚合證明，我們重點關注better_better_cs如何⽣成聚合證明。
還是⽤上⼀篇的這張代碼調⽤圖，我們這篇著重講create_proof。
我們分析的bellman_ce代碼版本是beta分⽀，commit id 為48441155ec7006bf7bfac553b5fb7d466d7fcd00。
Aggregation_proof 的⽣成
create_proof 這個函數在bellman_ce/src/plonk/better_better_cs/proof/mod.rs 中，將近2000 ⾏代碼。
⼤體上，分為以下⼏個步驟：
- 基本的⼀些檢查和預計算
for idx in 0 ..num_state_polys { let key = PolyIdentifier::PermutationPolynomial(idx); let vals = setup.permutation_monomials[idx].clone().fft_using_bitreversed_ntt( &worker, &omegas_bitreversed, &E::Fr::one() )?.into_coeffs(); let poly = Polynomial::from_values_unpadded(vals)?; let poly = PolynomialProxy::from_owned(poly); values_storage.setup_map.insert(key, poly); } - ⽣成state 多項式狀態和witness 多項式狀態，且為lookup table 參數⽣成排序好的多項式
// ... proof .state_polys_commitments .push ( commitment ); proof .witness_polys_commitments .push ( commitment ); // ... - 構造lookupdataholder，⽤於後續計算
let data = data_structures::LookupDataHolder::<E> { eta, f_poly_unpadded_values: Some (f_poly_values_aggregated), t_poly_unpadded_values: Some (t_poly_values), t_shifted_unpadded_values: Some (t_poly_values_shifted), s_poly_unpadded_values: Some (s_poly_unpadded_values), s_shifted_unpadded_values: Some (s_shifted_unpadded_values), t_poly_monomial: Some (t_poly_monomial), s_poly_monomial: Some (s_poly_monomial), selector_poly_monomial: Some (selector_poly), table_type_poly_monomial: Some (table_type_mononial), }; - 對置換多項式進⾏乘積（grand product）計算
// ... let mut z_2 = grand_products_proto_it.next().unwrap(); z_2.add_assign_scaled( &worker , permutation_polys_it.next().unwrap(), &beta_for_copy_permutation ); for (mut p, perm) in grand_products_proto_it.zip(permutation_polys_it) { p.add_assign_scaled( &worker , &perm , &beta_for_copy_permutation ); z_2.mul_a ssign( &worker , &p ); } z_2.batch_inversi on( &worker )?; - 對商多項式進⾏計算
// ... let mut t = gate.contribute_into_quotient_for_public_inputs( required_domain_size, &input_values , &mut ldes_storage, &monomials_storage , for_gate, &omegas_bitreversed , &omegas_inv_bitreversed , &worker )?; // ... transcript.commit_field_element( "ient_at_z ); proof.quotient_poly_opening_at_z = quotient_at_z; - 根據lookup table 進⾏線性化
let queries_with_linearization = sort_queries_for_linearization(&self.sorted_gates, MAX_DILATION); // ... for (dilation_value, ids) in queries_with_linearization . state_polys . iter () . enumerate () {...} for (dilation_value, ids) in queries_with_linearization . witness_polys . iter () . enumerate () {...} for (gate_idx, queries) in queries_with_linearization . gate_setup_polys . iter () . enumerate () {...} - 對多項式的selectors 進⾏ open 取值
let mut selector_values = vec! []; for s in queries_with_linearization.gate_selectors.iter() { let gate_index = self .sorted_gates.iter().position(|r| r == s).unwrap(); let key = PolyIdentifier::GateSelector(s.name()); let poly_ref = monomials_storage.gate_selectors.get(&key).unwrap().as_ref(); let value = poly_ref.evaluate_at(&worker, z); transcript.commit_field_element(&value); proof.gate_selectors_openings_at_z.push((gate_index, value)); selector_values.push(value); } - 增加拷⻉置換多項式、lookup置換的優化結果
// ... r_poly.add_assign_scaled( &worker , ©_permutation_z_in_monomial_form , &factor ); r_poly.sub_assign_scaled( &worker , last_permutation_poly_ref, &factor ); r_poly.add_assign_scaled( &worker , ©_permutation_z_in_monomial_form , &factor ); - 使⽤ lookup 進⾏ query
s_at_z_omega, grand_product_at_z_omega, t_at_z, t_at_z_omega, selector_at_z, table_type_at_z, }; - 對多項式的selectors 在z 進⾏ open 取值
for s in queries_with_linearization.gate_selectors.iter() { multiopening_challenge.mul_a ssign( &v ); let key = PolyIdentifier::GateSelector(s.name()); let poly_ref = monomials_storage.get_poly( key ); poly_to_divide_at_z.add_assign_scaled( &worker , poly_ref, &multiopening_challenge ); } - 將最終的lookup 值放⼊proof中
if let Some(data) = lookup_data.as_ref() { // we need to add t( x ), selector( x ) and table type( x ) multiopening_challenge.mul_a ssign( &v ); let poly_ref = data.t_poly_monomial.as_ref().unwrap().as_ref(); poly_to_divide_at_z.add_assign_scaled( &worker , poly_ref, &multiopening_challenge ); multiopening_challenge.mul_a ssign( &v ); let poly_ref = data.selector_poly_monomial.as_ref().unwrap().as_ref(); poly_to_divide_at_z.add_assign_scaled( &worker , poly_ref, &multiopening_challenge ); multiopening_challenge.mul_a ssign( &v ); let poly_ref = data.table_type_poly_monomial.as_ref().unwrap().as_ref(); poly_to_divide_at_z.add_assign_scaled( &worker , poly_ref, &multiopening_challenge ); } - 計算z、z_omega 處的open 值，最後組裝proof
let open_at_z_omega = polys.pop().unwrap().0; let open_at_z = polys.pop().unwrap().0; let opening_at_z = commit_using_monomials( &open_at_z , &mon_crs , &worker )?; let opening_at_z_omega = commit_using_monomials( &open_at_z_omega , &mon_crs , &worker )?; proof.opening_proof_at_z = opening_at_z; proof.opening_proof_at_z_omega = opening_at_z_omega;
在這個函數中，我們看到了熟悉的MainGate 函數，從上⼀版如何實現聚合中，我們知道這個⽤於⻔的設計，可以實現custom gate，達到優化電路的⽬的。 ⽽除開custom gate，ZKSync 中還使⽤了plonkup（即plonk + lookup table） 來提升效率。
我們在之前的⽂章中，已經講解過plonkup的原理了，簡單來說，就是預計算有效的input/output組成lookup table，prover需要證明witness在這個table⾥，詳細內容請參⻅ ZKSwap團隊解讀Plookup原理。 ZKSync 對plonkup 的實現，並不是將custom gate 和plonkup 分開的，⽽是結合在⼀起來優化電路設計的。我們下⾯看看，MainGate trait 中的接⼝，是如何和plonkup 結合的。
Lookup 的使⽤
在上⼀節的create_proof 函數中，線性化⽤到了gate 的 contribute_into_linearization_for_public_inputs 函數，我們以它為例，來看看lookup 的使⽤。這個代碼在bellman_ce/src/plonk/better_better_cs/cs.rs 中。
fn contribute_into_linearization_for_public_inputs( &self, _domain_size: usize, _public_inputs: &[ E: :Fr], _at: E: :Fr, queried_values: & std: : collections: :HashMap<PolynomialInConstraint, E: :Fr>, monomials_storage: & AssembledPolynomialStorageForMonomialForms<E>, challenges: &[ E: :Fr], worker: &Worker ) -> Result<Polynomial< E: :Fr, Coefficients>, SynthesisError> {}⽤到的傳⼊參數有hashmap 格式的queried_values、單項式緩存值、隨機數數組queried_values 這個參數是在create_proof 時，根據排序的query 列表⽣成的，key 是多項式，value是Fr 值。 query 列表的排序規則是先witness、gate 的selector 次之、gate 的setup 再次之，這個SortedGateQueries 的結構是：
pub struct SortedGateQueries <E: Engine>{ pub state_polys: Vec < Vec <PolyIdentifier>>, // state 多项式pub witness_polys: Vec < Vec <PolyIdentifier>>, // witness 多项式pub gate_selectors: Vec < Box < dyn GateInternal<E>>>, // gate 的selectors pub gate_setup_polys: Vec < Vec < Vec <PolyIdentifier>>>, // gate setup 多项式}代碼中，調⽤ sort_queries_for_linearization函數來⽣成SortedGateQueries ，這個函數也在當前mod.rs ⽂件中。這個函數輸⼊參數是gate數組，輸出即為SortedGateQueries 。
fn sort_queries_for_linearization <E: Engine>(gates: & Vec < Box < dyn GateInternal<E>>>, max_dilation: usize ) -> SortedGateQueries<E> { }函數會對傳⼊的gate數組遍歷，根據gate返回的多項式數組，將其按照VariablesPolynomial ， WitnessPolynomial， GateSetupPolynomial的不同類型，將多項式存⼊ SortedGateQueries中。
回到contribute_into_linearization_for_public_inputs函數，可以看到，它會從queried_values 中，獲取a/b/c/d的值。 ⽽ Q_a/Q_b/Q_c/Q_d/Q_m的值，都是從create_proof剛開始⽣成的單項式緩存數據中取到的，也是⼀個lookup table的概念。
這個單項式緩存的值是從電路的setup獲得的，即電路確定了，那麼電路的⻔就確定了，則在⽣成proof時，這些數據都已經有了，可以直接將setup預計算的結果，放⼊lookup table中，查詢使⽤數據。
let mut monomials_storage = Self::create_monomial_storage( &worker, &omegas_inv_bitreversed, &values_storage, true )?; monomials_storage.extend_from_setup(setup)?;最後，結合a/b/c/d和Q_a/Q_b/Q_c/Q_d，可以⾮常⽅便的構造出多項式。
// 可以看到，⾮常⾼效的get取到了数据let a_value = *queried_values.get(&PolynomialInConstraint::from_id(PolyIdentifier::VariablesPolynomia l( 0 ))) .ok_or(SynthesisError::AssignmentMissing)?; let b_value = *queried_values.get(&PolynomialInConstraint::from_id(PolyIdentifier::VariablesPolynomia l( 1 ))) .ok_or(SynthesisError::AssignmentMissing)?; let c_value = *queried_values.get(&PolynomialInConstraint::from_id(PolyIdentifier::VariablesPolynomia l( 2 ))) .ok_or(SynthesisError::AssignmentMissing)?; let d_value = *queried_values.get(&PolynomialInConstraint::from_id(PolyIdentifier::VariablesPolynomia l( 3 ))) .ok_or(SynthesisError::AssignmentMissing)?; let d_next_value = *queried_values.get(&PolynomialInConstraint::from_id_and_dilation(PolyIdentifier::Varia blesPolynomial( 3 ), 1 )) .ok_or(SynthesisError::AssignmentMissing)?; let name = < Self as GateInternal<E>>::name(& self ); // get_ploy 也是查找table的⽅式获取多项式// Q_a * A let mut result = monomials_storage.get_poly(PolyIdentifier::GateSetupPolynomial(name, 0 )).clone(); result.scale(&worker, a_value); // Q_b * B let poly_ref = monomials_storage.get_poly(PolyIdentifier::GateSetupPolynomial(name, 1 )); result.add_assign_scaled(&worker, poly_ref, &b_value); // Q_c * C let poly_ref = monomials_storage.get_poly(PolyIdentifier::GateSetupPolynomial(name, 2 )); result.add_assign_scaled(&worker, poly_ref, &c_value); // Q_d * D let poly_ref = monomials_storage.get_poly(PolyIdentifier::GateSetupPolynomial(name, 3 )); result.add_assign_scaled(&worker, poly_ref, &d_value); // Q_m * A*B let mut tmp = a_value; tmp.mul_assign(&b_value); let poly_ref = monomials_storage.get_poly(PolyIdentifier::GateSetupPolynomial(name, 4 )); result.add_assign_scaled(&worker, poly_ref, &tmp); // Q_const let poly_ref = monomials_storage.get_poly(PolyIdentifier::GateSetupPolynomial(name, 5 )); result.add_assign(&worker, poly_ref); // Q_dNext * D_next let poly_ref = monomials_storage.get_poly(PolyIdentifier::GateSetupPolynomial(name, 6 )); result.add_assign_scaled(&worker, poly_ref, &d_next_value); result.scale(&worker, challenges[ 0 ]); // 结果都存⼊result中Ok (result)另外⼏個MainGate⾥的接⼝函數，都是⼀樣的，結合lookup table，⾮常容易的計算出多項式。
綜上，ZKSync將witness、gate的selector、setup放⼊lookup table中，在⽣成proof時，使⽤lookuptable，直接查詢⽽不是再次計算，加快⽣成速度，提升prover效率。
