Boojum 介绍

作者: 雪落无留痕 | 来源:发表于2023-08-29 17:35 被阅读0次

Boojum 是zkSync 新提出一种零知识证明方案，后续将zkSync 升级为一种基于STARK证明的方案，具有较高的性能。目前zkSync Era通到家100+TPS, Boojum能在些基础上再提升几个数量级。

Boojum能够降低硬件的要求，更好的实现证明的去中心化，可以在16GB的GPU上运行。

Boojum 采用Plonk样式的数值化方式，以及FRI 承诺方式。

Boojum 采用 $2^{64}-2^{32}+1$ Goldlicks 域，提供基于域的基元：Poseidon2函数，以及基于查找表的基元：SHA256, Keccak256, 和Blake2s。

证明过程是先成STARK 证明，再生成SNARK证明，方便在链上验证。

经过测试，Boojum算是最快的证明系统。

Ref: https://blog.celer.network/2023/07/14/the-pantheon-of-zero-knowledge-proof-development-frameworks/

源码分析

下面以 prove_simple 为例，分析源码执行过程：

约束系统配置

首先定义Goldilocs 域，如下所示

/// A field selected to have fast reduction.
///
/// Its order is 2^64 - 2^32 + 1.
/// ```ignore
/// P = 2**64 - EPSILON
///   = 2**64 - 2**32 + 1
///   = 2**32 * (2**32 - 1) + 1
/// ```
#[derive(Clone, Copy, serde::Serialize, serde::Deserialize)]
#[repr(transparent)]
pub struct GoldilocksField(pub u64);

定义CSGeometry, 其结构为：

pub struct CSGeometry { 
    pub num_columns_under_copy_permutation: usize, // 参与置换列的个数
    pub num_witness_columns: usize,   // witness 列的个数
    pub num_constant_columns: usize,   // 常量列的个数
    pub max_allowed_constraint_degree: usize,   //约束条件允许的最大度数
}

构建 CsReferenceImplementationBuilder ，主要用于构建约束系统；

pub struct CsReferenceImplementationBuilder<
    F: SmallField,
    P: PrimeFieldLikeVectorized<Base = F>,
    CFG: CSConfig,
> {
    phantom: std::marker::PhantomData<(P, CFG)>,

    parameters: CSGeometry,    // CS 几何参数
    lookup_parameters: LookupParameters,  // 查找表参数
    max_trace_len: usize,
    lookup_marker_gate_idx: Option<u32>,
    max_variables: usize,

    evaluation_data_over_general_purpose_columns: EvaluationDataOverGeneralPurposeColumns<F, P>,
    evaluation_data_over_specialized_columns: EvaluationDataOverSpecializedColumns<F, P>,
}

构建CsBuilder , 为：

pub struct CsBuilder<TImpl, F: SmallField, GC: GateConfigurationHolder<F>, TB: StaticToolboxHolder>
{
    pub(crate) phantom: std::marker::PhantomData<F>,

    pub(crate) implementation: TImpl,
    pub(crate) gates_config: GC,
    pub(crate) toolbox: TB,
}

配置电路，以要代码主要允许约束系统中可以添加ConstantsAllocatorGate, FmaGateInBaseFieldWithoutConstant, ZeroCheckGate, NopGate 四种电路。

       fn configure<
            T: CsBuilderImpl<F, T>,
            GC: GateConfigurationHolder<F>,
            TB: StaticToolboxHolder,
        >(
            builder: CsBuilder<T, F, GC, TB>,
        ) -> CsBuilder<T, F, impl GateConfigurationHolder<F>, impl StaticToolboxHolder> {
            let builder = ConstantsAllocatorGate::configure_builder(
                builder,
                GatePlacementStrategy::UseGeneralPurposeColumns,
            );
            let builder = FmaGateInBaseFieldWithoutConstant::configure_builder(
                builder,
                GatePlacementStrategy::UseGeneralPurposeColumns,
            );
            let builder = ZeroCheckGate::configure_builder(
                builder,
                GatePlacementStrategy::UseGeneralPurposeColumns,
                false,
            );
            let builder = NopGate::configure_builder(
                builder,
                GatePlacementStrategy::UseGeneralPurposeColumns,
            );

            builder
        }

配置完成的电路结构体为：

pub struct CSReferenceImplementation<
    F: SmallField, // over which we define a circuit
    P: field::traits::field_like::PrimeFieldLikeVectorized<Base = F>, // over whatever we evaluate gates. It can be vectorized type, or circuit variables
    CFG: CSConfig,
    GC: GateConfigurationHolder<F>,
    T: StaticToolboxHolder,
> {
    pub(crate) parameters: CSGeometry,
    pub(crate) lookup_parameters: LookupParameters,

    pub(crate) next_available_row: usize,
    pub(crate) next_available_place_idx: u64,
    pub(crate) next_lookup_table_index: u32,

    pub(crate) max_trace_len: usize,

    pub(crate) gates_application_sets: Vec<usize>, // index into gates_ordered_set for general-purpose columns

    pub(crate) copy_permutation_data: Vec<Vec<Variable>>, // store column-major order
    pub(crate) witness_placement_data: Vec<Vec<Witness>>, // store column-major order
    pub(crate) constants_requested_per_row: Vec<SmallVec<[F; 8]>>, // for general purpose gates
    pub(crate) constants_for_gates_in_specialized_mode: Vec<Vec<F>>, // for specialized gates we use another mode of placement
    pub(crate) lookup_table_marker_into_id: HashMap<TypeId, u32>,
    pub(crate) lookup_tables: Vec<std::sync::Arc<LookupTableWrapper<F>>>,
    pub(crate) lookup_multiplicities: Vec<std::sync::Arc<Vec<AtomicU32>>>, // per each subarbument (index 0) we have vector of multiplicities for every table

    // NOTE: it's a storage, it knows nothing about GateTool trait to avoid code to go from Box<dyn GateTool> into Box<dyn Any>
    pub(crate) dynamic_tools:
        HashMap<TypeId, (TypeId, Box<dyn std::any::Any + Send + Sync + 'static>)>,
    pub(crate) variables_storage: RwLock<CircuitResolver<F, CFG::ResolverConfig>>,

    /// Gate layout hints - we create our CS with only "general purpose" columns,
    /// and then if the gate is added in the specialized columns we should extend our
    /// holders for copy permutation and witness data, as well as know what the offsets are
    /// for the first copy of the evaluator
    pub(crate) evaluation_data_over_general_purpose_columns:
        EvaluationDataOverGeneralPurposeColumns<F, P>,
    pub(crate) evaluation_data_over_specialized_columns: EvaluationDataOverSpecializedColumns<F, P>,

    pub(crate) lookup_marker_gate_idx: Option<u32>,
    pub(crate) table_ids_as_variables: Vec<Variable>,
    pub(crate) public_inputs: Vec<(usize, usize)>,

    pub(crate) specialized_gates_rough_stats: HashMap<TypeId, usize>,

    pub(crate) static_toolbox: T,
    pub(crate) gates_configuration: GC,

    pub(crate) row_cleanups: Vec<GateRowCleanupFunction<Self>>,
    pub(crate) columns_cleanups: Vec<GateColumnsCleanupFunction<Self>>,
}

向约束系统中添加电路：

for _ in 0..100 {
            let a = if let Some(previous) = previous.take() {
                previous
            } else {
                cs.alloc_single_variable_from_witness(GoldilocksField::from_u64_unchecked(1))
            };
            let b = cs.alloc_single_variable_from_witness(GoldilocksField::from_u64_unchecked(2));
            let c = cs.alloc_single_variable_from_witness(GoldilocksField::from_u64_unchecked(3));
            
            // 添加Fma电路
            let d = FmaGateInBaseFieldWithoutConstant::compute_fma(
                &mut cs,
                GoldilocksField::TWO,
                (a, b),
                GoldilocksField::MINUS_ONE,
                c,
            );
            // previous = Some(d);

            let e = ZeroCheckGate::check_if_zero(&mut cs, d);  // 添加 ZeroCheckGate 电路
            previous = Some(e);
            // let e = FmaGateInBaseFieldWithoutConstant::compute_fma(
            //     &mut cs,
            //     GoldilocksField::TWO,
            //     (d, d),
            //     GoldilocksField::MINUS_ONE,
            //     a,
            // );
        }

进一步转化的约束系统：

pub struct CSReferenceAssembly<
    F: SmallField, // over which we define a circuit
    P: field::traits::field_like::PrimeFieldLikeVectorized<Base = F>, // over whatever we evaluate gates. It can be vectorized type, or circuit variables
    CFG: CSConfig,
> {
    pub parameters: CSGeometry,
    pub lookup_parameters: LookupParameters,

    pub(crate) next_available_place_idx: u64,

    pub max_trace_len: usize,

    pub gates_application_sets: Vec<usize>, // index into gates_ordered_set for general-purpose columns

    pub copy_permutation_data: Vec<Vec<Variable>>, // store column-major order
    pub witness_placement_data: Vec<Vec<Witness>>, // store column-major order
    pub constants_requested_per_row: Vec<SmallVec<[F; 8]>>, // for general purpose gates
    pub constants_for_gates_in_specialized_mode: Vec<Vec<F>>, // for specialized gates we use another mode of placement
    pub lookup_tables: Vec<std::sync::Arc<LookupTableWrapper<F>>>,
    pub lookup_multiplicities: Vec<std::sync::Arc<Vec<AtomicU32>>>, // per each subarbument (index 0) we have vector of multiplicities for every table

    pub variables_storage: RwLock<CircuitResolver<F, CFG::ResolverConfig>>,

    pub evaluation_data_over_general_purpose_columns: EvaluationDataOverGeneralPurposeColumns<F, P>,
    pub evaluation_data_over_specialized_columns: EvaluationDataOverSpecializedColumns<F, P>,

    pub specialized_gates_rough_stats: HashMap<TypeId, usize>,

    pub public_inputs: Vec<(usize, usize)>,

    pub placement_strategies: HashMap<TypeId, GatePlacementStrategy>,
}

证明生成

证明的配置的配置参数为：

pub struct ProofConfig {
    pub fri_lde_factor: usize,
    pub merkle_tree_cap_size: usize,
    pub fri_folding_schedule: Option<Vec<usize>>,
    pub security_level: usize,
    pub pow_bits: u32,
}

生成证明和验证密钥：

 let (proof, vk) = cs.prove_one_shot::<
            GoldilocksExt2,
            GoldilocksPoisedonTranscript,
            GoldilocksPoseidonSponge<AbsorptionModeOverwrite>,
            NoPow,
        >(&worker, proof_config, ());

证明验证

证明的验证过程为：

        let builder_impl = CsVerifierBuilder::<F, GoldilocksExt2>::new_from_parameters(geometry);
        let builder = new_builder::<_, F>(builder_impl);

        let builder = configure(builder);
        let verifier = builder.build(());

        let is_valid = verifier.verify::<
            GoldilocksPoseidonSponge<AbsorptionModeOverwrite>,
            GoldilocksPoisedonTranscript,
            NoPow
        >(
            (),
            &vk,
            &proof,
        );

        assert!(is_valid);