本文主要对Matter Labs 聚合证明理论和源代码进行解析，参考：

Github: https://github.com/matter-labs/recursive_aggregation_circuit

commit：30bbf42c81c08ba8a15dcad3eaca9e771c4d8c89

日期：2021-07-11

聚合证明

聚合证明与Plonk共用CRS。

应用相关设置

1. 电路合成

   #[derive(Clone)]
   pub struct Assembly<E: Engine, P: PlonkConstraintSystemParams<E>, MG: MainGate<E>, S: SynthesisMode> {
       pub inputs_storage: PolynomialStorage<E>,
       pub aux_storage: PolynomialStorage<E>,
       pub num_input_gates: usize,
       pub num_aux_gates: usize,
       pub max_constraint_degree: usize,
       pub main_gate: MG,
       pub input_assingments: Vec<E::Fr>,
       pub aux_assingments: Vec<E::Fr>,
       pub num_inputs: usize,
       pub num_aux: usize,
       pub trace_step_for_batch: Option<usize>,
       pub is_finalized: bool,
   
       pub gates: std::collections::HashSet<Box<dyn GateInternal<E>>>,
       pub all_queried_polys_in_constraints: std::collections::HashSet<PolynomialInConstraint>,
       // pub sorted_setup_polynomial_ids: Vec<PolyIdentifier>,
       pub sorted_gates: Vec<Box<dyn GateInternal<E>>>,
       pub aux_gate_density: GateDensityStorage<E>,
       pub explicit_zero_variable: Option<Variable>,
       pub explicit_one_variable: Option<Variable>,
   
       pub tables: Vec<Arc<LookupTableApplication<E>>>,
       pub multitables: Vec<Arc<MultiTableApplication<E>>>,
       pub table_selectors: std::collections::HashMap<String, BitVec>,
       pub multitable_selectors: std::collections::HashMap<String, BitVec>,
       pub table_ids_poly: Vec<E::Fr>,
       pub total_length_of_all_tables: usize,
   
       pub individual_table_entries: std::collections::HashMap<String, Vec<Vec<E::Fr>>>,
       pub individual_multitable_entries: std::collections::HashMap<String, Vec<Vec<E::Fr>>>,
       pub known_table_ids: Vec<E::Fr>,
       pub num_table_lookups: usize,
       pub num_multitable_lookups: usize,
   
       _marker_p: std::marker::PhantomData<P>,
       _marker_s: std::marker::PhantomData<S>,
   }
   

2. setup生成

#[derive(Clone, PartialEq, Eq)]
pub struct Setup<E: Engine, C: Circuit<E>> {
    pub n: usize,
    pub num_inputs: usize,
    pub state_width: usize,
    pub num_witness_polys: usize,

    pub gate_setup_monomials: Vec<Polynomial<E::Fr, Coefficients>>,
    pub gate_selectors_monomials: Vec<Polynomial<E::Fr, Coefficients>>,
    pub permutation_monomials: Vec<Polynomial<E::Fr, Coefficients>>,

    pub total_lookup_entries_length: usize,
    pub lookup_selector_monomial: Option<Polynomial<E::Fr, Coefficients>>,
    pub lookup_tables_monomials: Vec<Polynomial<E::Fr, Coefficients>>,
    pub lookup_table_type_monomial: Option<Polynomial<E::Fr, Coefficients>>,

    pub non_residues: Vec<E::Fr>,

    _marker: std::marker::PhantomData<C>
}

3. 验证密钥生成

#[derive(Clone, PartialEq, Eq)]
pub struct VerificationKey<E: Engine, C: Circuit<E>> {
    pub n: usize,
    pub num_inputs: usize,
    pub state_width: usize,
    pub num_witness_polys: usize,

    pub gate_setup_commitments: Vec<E::G1Affine>,
    pub gate_selectors_commitments: Vec<E::G1Affine>,
    pub permutation_commitments: Vec<E::G1Affine>,

    pub total_lookup_entries_length: usize,
    pub lookup_selector_commitment: Option<E::G1Affine>,
    pub lookup_tables_commitments: Vec<E::G1Affine>,
    pub lookup_table_type_commitment: Option<E::G1Affine>,

    pub non_residues: Vec<E::Fr>,
    pub g2_elements: [E::G2Affine; 2],

    _marker: std::marker::PhantomData<C>
}

证明过程

生成的证明为：

#[derive(Clone, PartialEq, Eq)]
pub struct Proof<E: Engine, C: Circuit<E>> {
    pub n: usize,
    pub inputs: Vec<E::Fr>,
    pub state_polys_commitments: Vec<E::G1Affine>,
    pub witness_polys_commitments: Vec<E::G1Affine>,
    pub copy_permutation_grand_product_commitment: E::G1Affine,

    pub lookup_s_poly_commitment: Option<E::G1Affine>,
    pub lookup_grand_product_commitment: Option<E::G1Affine>,

    pub quotient_poly_parts_commitments: Vec<E::G1Affine>,

    pub state_polys_openings_at_z: Vec<E::Fr>,
    pub state_polys_openings_at_dilations: Vec<(usize, usize, E::Fr)>,
    pub witness_polys_openings_at_z: Vec<E::Fr>,
    pub witness_polys_openings_at_dilations: Vec<(usize, usize, E::Fr)>,

    pub gate_setup_openings_at_z: Vec<(usize, usize, E::Fr)>,
    pub gate_selectors_openings_at_z: Vec<(usize, E::Fr)>,

    pub copy_permutation_polys_openings_at_z: Vec<E::Fr>,
    pub copy_permutation_grand_product_opening_at_z_omega: E::Fr,

    pub lookup_s_poly_opening_at_z_omega: Option<E::Fr>,
    pub lookup_grand_product_opening_at_z_omega: Option<E::Fr>,

    pub lookup_t_poly_opening_at_z: Option<E::Fr>,
    pub lookup_t_poly_opening_at_z_omega: Option<E::Fr>,

    pub lookup_selector_poly_opening_at_z: Option<E::Fr>,
    pub lookup_table_type_poly_opening_at_z: Option<E::Fr>,

    pub quotient_poly_opening_at_z: E::Fr,

    pub linearization_poly_opening_at_z: E::Fr,

    pub opening_proof_at_z: E::G1Affine,
    pub opening_proof_at_z_omega: E::G1Affine,

    _marker: std::marker::PhantomData<C>
}

验证过程

采用双线性对进行校验。

参考

https://eprint.iacr.org/2019/953

https://vitalik.ca/general/2019/09/22/plonk.html

https://research.metastate.dev/plonk-by-hand-part-1/

https://github.com/matter-labs/proof_system_info_v1.0/blob/master/PlonkUnrolledForEthereum.pdf