【zkMIPS系列】ZKM Prover——STARK to SNARK

ZKM
发布于 23小时前
阅读 126

STARK到SNARK的转换从构建递归电路开始，递归电路的作用是将原本庞大的STARK证明压缩成较小的SNARK证明，具体由以下几个组件构成，包括根电路，聚合电路和区块电路。

STARK到SNARK的转换从构建递归电路开始，递归电路的作用是将原本庞大的STARK证明压缩成较小的SNARK证明，具体由以下几个组件构成，包括根电路，聚合电路和区块电路，接下来首先介绍一下这些电路之间的作用：

# 1. 根电路（Root Circuit）

根电路是STARK证明压缩的最核心部分，它通过聚合多个表的递归证明最终生成一个SNARK证明。根电路将所有表的递归证明汇集在一起，并确保它们的公共输入符合要求。

代码实现：

```rust
/// The ZKVM root circuit, which aggregates the (shrunk) per-table recursive proofs.
#[derive(Eq, PartialEq, Debug)]
pub struct RootCircuitData<F, C, const D: usize>
where
    F: RichField + Extendable<D>,
    C: GenericConfig<D, F = F>,
{
    pub circuit: CircuitData<F, C, D>,  // 根电路数据
    proof_with_pis: [ProofWithPublicInputsTarget<D>; NUM_TABLES],  // 每个表的递归证明
    index_verifier_data: [Target; NUM_TABLES],  // 用于验证的索引数据
    public_values: PublicValuesTarget,  // 公共输入
    cyclic_vk: VerifierCircuitTarget,  // 用于循环验证的公钥
}

```

根电路的关键在于如何将每个表的递归证明压缩成一个最终的证明，并验证它们之间的一致性。在这个过程中，`proof_with_pis` 存储了每个表的递归证明，而 `index_verifier_data` 和 `public_values` 则是用于验证这些证明的公共输入。

# 2. 聚合电路（Aggregation Circuit）

聚合电路的目的是将两个证明压缩为一个。在STARK到SNARK的转换过程中，聚合电路通常用于将根电路和其他中间证明合并成最终的证明。聚合电路通过将多个递归证明聚合在一起，从而减少证明的大小。

代码实现：

```rust
/// Data for the aggregation circuit, which is used to compress two proofs into one.
#[derive(Eq, PartialEq, Debug)]
pub struct AggregationCircuitData<F, C, const D: usize>
where
    F: RichField + Extendable<D>,
    C: GenericConfig<D, F = F>,
{
    pub circuit: CircuitData<F, C, D>,  // 聚合电路数据
    lhs: AggregationChildTarget<D>,  // 左侧聚合子电路
    rhs: AggregationChildTarget<D>,  // 右侧聚合子电路
    public_values: PublicValuesTarget,  // 公共输入
    cyclic_vk: VerifierCircuitTarget,  // 用于循环验证的公钥
}

```

聚合电路通过 `lhs` 和 `rhs` 两个聚合子电路来压缩两个证明成一个最终证明。每个聚合子电路都可以是ZKVM根证明或另一个聚合证明。在实现中，`lhs` 和 `rhs` 是两个目标电路，它们分别表示聚合的左侧和右侧证明。

# 3. 区块电路（Block Circuit）

区块电路的作用类似于聚合电路，但它不仅仅是压缩证明，它还要验证两个证明（例如聚合证明和父块证明）的一致性。这个电路确保了区块链的有效性和一致性。

```rust
/// Data for the block circuit, which verifies an aggregation root proof and a previous block proof.
#[derive(Eq, PartialEq, Debug)]
pub struct BlockCircuitData<F, C, const D: usize>
where
    F: RichField + Extendable<D>,
    C: GenericConfig<D, F = F>,
{
    pub circuit: CircuitData<F, C, D>,  // 区块电路数据
    has_parent_block: BoolTarget,  // 是否有父块
    parent_block_proof: ProofWithPublicInputsTarget<D>,  // 父块证明
    agg_root_proof: ProofWithPublicInputsTarget<D>,  // 聚合根证明
    public_values: PublicValuesTarget,  // 公共输入
    cyclic_vk: VerifierCircuitTarget,  // 循环验证的公钥
}

```

区块电路在处理证明时，会将父块证明和聚合根证明结合起来验证。如果没有父块证明，则需要用虚拟的父块证明来填补。

接下来，将重点介绍一下从每个STARK Proof，压缩为一个SNARK Proof的过程，包括确定递归电路链（即按照什么顺序进行递归证明），挑战集合和公开值之间的处理及最终的STARK Proof向SNARK Proof的转换，过程如下：

## 3.1 递归电路链的逐步压缩

递归电路链的关键在于逐步将每个表的递归证明压缩。每个表的递归电路都包含多个电路，每个电路的度数逐步减小，直到达到设定的阈值 `THRESHOLD_DEGREE_BITS`。

```rust
#[derive(Eq, PartialEq, Debug)]
pub struct RecursiveCircuitsForTable<F, C, const D: usize>
where
    F: RichField + Extendable<D>,
    C: GenericConfig<D, F = F>,
    C::Hasher: AlgebraicHasher<F>,
{
    by_stark_size: BTreeMap<usize, RecursiveCircuitsForTableSize<F, C, D>>,  // 每个表的递归电路链
}

impl<F, C, const D: usize> RecursiveCircuitsForTable<F, C, D>
where
    F: RichField + Extendable<D>,
    C: GenericConfig<D, F = F>,
    C::Hasher: AlgebraicHasher<F>,
{
    pub fn new<S: Stark<F, D>>(
        table: Table,
        stark: &S,
        degree_bits_range: Range<usize>,
        all_ctls: &[CrossTableLookup<F>],
        stark_config: &StarkConfig,
    ) -> Self {
        let by_stark_size = degree_bits_range
            .map(|degree_bits| {
                (
                    degree_bits,
                    RecursiveCircuitsForTableSize::new::<S>(
                        table,
                        stark,
                        degree_bits,
                        all_ctls,
                        stark_config,
                    ),
                )
            })
            .collect();
        Self { by_stark_size }
    }
}

```

`RecursiveCircuitsForTable` 为每个表构建一个递归电路链，链中的每个电路都有不同的大小。当递归电路的大小减少到预设阈值 `THRESHOLD_DEGREE_BITS` 时，递归过程结束。这个递归链通过 `RecursiveCircuitsForTableSize` 来实现。

## 3.2 挑战集与公共输入的处理

在每个递归步骤中，挑战集和公共输入被用来确保证明的有效性。公共输入提供了每个证明的验证信息，而挑战集用于验证每个证明的挑战值。通过 `RecursiveChallenger`，我们可以观察和验证这些挑战值。

```rust
let mut challenger = RecursiveChallenger::<F, C::Hasher, D>::new(&mut builder);
for pi in &pis {
    for h in &pi.trace_cap {
        challenger.observe_elements(h);  // 观察公共输入
    }
}

let ctl_challenges = get_grand_product_challenge_set_target(
    &mut builder,
    &mut challenger,
    stark_config.num_challenges,
);

```

在每个递归步骤中，`RecursiveChallenger` 用来观察公共输入中的挑战值，并验证它们的一致性。这确保了每个证明是有效的，并且可以进一步压缩。

## 3.3 STARK到SNARK的最终转换

在递归步骤完成后，最终的STARK到SNARK的转换过程通过多个递归电路链将STARK证明逐步压缩成一个更小的SNARK证明。每个表的证明会逐步减少，并最终合并成一个根证明。

```rust
pub fn prove_root(
    &self,
    all_stark: &AllStark<F, D>,
    kernel: &Kernel,
    config: &StarkConfig,
    timing: &mut TimingTree,
) -> anyhow::Result<(ProofWithPublicInputs<F, C, D>, PublicValues)> {
    let all_proof = prove::<F, C, D>(all_stark, kernel, config, timing)?;
    verify_proof(all_stark, all_proof.clone(), config).unwrap();
    let mut root_inputs = PartialWitness::new();

// 处理每个表的证明
    for table in 0..NUM_TABLES {
        let stark_proof = &all_proof.stark_proofs[table];
        let shrunk_proof = self.by_table[table]
            .by_stark_size
            .get(&stark_proof.proof.recover_degree_bits(config))
            .unwrap()
            .shrink(stark_proof, &all_proof.ctl_challenges)?;
        root_inputs.set_proof_with_pis_target(&self.root.proof_with_pis[table], &shrunk_proof);
    }

// 设置公共输入并生成根证明
    set_public_value_targets(
        &mut root_inputs,
        &self.root.public_values,
        &all_proof.public_values,
    )?;

let root_proof = self.root.circuit.prove(root_inputs)?;
    Ok((root_proof, all_proof.public_values))
}

```

在最终的转换中，`prove_root` 会逐个处理每个表的证明，通过 `shrink` 方法压缩这些证明，并通过设置公共输入生成最终的SNARK证明。

其中`shrink` 函数的核心作用是将一个大的 STARK 证明压缩成一个更小的证明，以适配递归证明的计算需求，同时保持原始证明的完整性和真实性。这个过程不仅减少了证明的复杂度，也提升了后续递归电路处理的效率，其具体过程如下：

1. 首先，`shrink` 会调用 `initial_wrapper` 中的证明函数，对 STARK 证明进行初步压缩。这一步是关键，负责将原始的较大证明映射到一个较小的电路中。
2. 接着，它会循环调用 `shrinking_wrappers` 中的每个递归电路，将初步压缩后的证明继续逐步压缩，直到其大小符合目标电路的约束（例如 `THRESHOLD_DEGREE_BITS` 的递归门大小）。
3. 返回一个最终压缩的 `ProofWithPublicInputs` 结构体，这个结构体包含了公共输入和压缩后的证明，能够被更小的递归电路直接使用。

```rust
fn shrink(
    &self,
    stark_proof_with_metadata: &StarkProofWithMetadata<F, C, D>,
    ctl_challenges: &GrandProductChallengeSet<F>,
) -> anyhow::Result<ProofWithPublicInputs<F, C, D>> {
    let mut proof = self
        .initial_wrapper
        .prove(stark_proof_with_metadata, ctl_challenges)?;
    for wrapper_circuit in &self.shrinking_wrappers {
        proof = wrapper_circuit.prove(&proof)?;
    }
    Ok(proof)
}

```

1. 根电路（Root Circuit）

代码实现：

/// The ZKVM root circuit, which aggregates the (shrunk) per-table recursive proofs.
#[derive(Eq, PartialEq, Debug)]
pub struct RootCircuitData&lt;F, C, const D: usize>
where
    F: RichField + Extendable&lt;D>,
    C: GenericConfig&lt;D, F = F>,
{
    pub circuit: CircuitData&lt;F, C, D>,  // 根电路数据
    proof_with_pis: [ProofWithPublicInputsTarget&lt;D>; NUM_TABLES],  // 每个表的递归证明
    index_verifier_data: [Target; NUM_TABLES],  // 用于验证的索引数据
    public_values: PublicValuesTarget,  // 公共输入
    cyclic_vk: VerifierCircuitTarget,  // 用于循环验证的公钥
}

根电路的关键在于如何将每个表的递归证明压缩成一个最终的证明，并验证它们之间的一致性。在这个过程中，proof_with_pis 存储了每个表的递归证明，而 index_verifier_data 和 public_values 则是用于验证这些证明的公共输入。

2. 聚合电路（Aggregation Circuit）

代码实现：

/// Data for the aggregation circuit, which is used to compress two proofs into one.
#[derive(Eq, PartialEq, Debug)]
pub struct AggregationCircuitData&lt;F, C, const D: usize>
where
    F: RichField + Extendable&lt;D>,
    C: GenericConfig&lt;D, F = F>,
{
    pub circuit: CircuitData&lt;F, C, D>,  // 聚合电路数据
    lhs: AggregationChildTarget&lt;D>,  // 左侧聚合子电路
    rhs: AggregationChildTarget&lt;D>,  // 右侧聚合子电路
    public_values: PublicValuesTarget,  // 公共输入
    cyclic_vk: VerifierCircuitTarget,  // 用于循环验证的公钥
}

聚合电路通过 lhs 和 rhs 两个聚合子电路来压缩两个证明成一个最终证明。每个聚合子电路都可以是ZKVM根证明或另一个聚合证明。在实现中，lhs 和 rhs 是两个目标电路，它们分别表示聚合的左侧和右侧证明。

3. 区块电路（Block Circuit）

/// Data for the block circuit, which verifies an aggregation root proof and a previous block proof.
#[derive(Eq, PartialEq, Debug)]
pub struct BlockCircuitData&lt;F, C, const D: usize>
where
    F: RichField + Extendable&lt;D>,
    C: GenericConfig&lt;D, F = F>,
{
    pub circuit: CircuitData&lt;F, C, D>,  // 区块电路数据
    has_parent_block: BoolTarget,  // 是否有父块
    parent_block_proof: ProofWithPublicInputsTarget&lt;D>,  // 父块证明
    agg_root_proof: ProofWithPublicInputsTarget&lt;D>,  // 聚合根证明
    public_values: PublicValuesTarget,  // 公共输入
    cyclic_vk: VerifierCircuitTarget,  // 循环验证的公钥
}

区块电路在处理证明时，会将父块证明和聚合根证明结合起来验证。如果没有父块证明，则需要用虚拟的父块证明来填补。

3.1 递归电路链的逐步压缩

递归电路链的关键在于逐步将每个表的递归证明压缩。每个表的递归电路都包含多个电路，每个电路的度数逐步减小，直到达到设定的阈值 THRESHOLD_DEGREE_BITS。

#[derive(Eq, PartialEq, Debug)]
pub struct RecursiveCircuitsForTable&lt;F, C, const D: usize>
where
    F: RichField + Extendable&lt;D>,
    C: GenericConfig&lt;D, F = F>,
    C::Hasher: AlgebraicHasher&lt;F>,
{
    by_stark_size: BTreeMap&lt;usize, RecursiveCircuitsForTableSize&lt;F, C, D>>,  // 每个表的递归电路链
}

impl&lt;F, C, const D: usize> RecursiveCircuitsForTable&lt;F, C, D>
where
    F: RichField + Extendable&lt;D>,
    C: GenericConfig&lt;D, F = F>,
    C::Hasher: AlgebraicHasher&lt;F>,
{
    pub fn new&lt;S: Stark&lt;F, D>>(
        table: Table,
        stark: &S,
        degree_bits_range: Range&lt;usize>,
        all_ctls: &[CrossTableLookup&lt;F>],
        stark_config: &StarkConfig,
    ) -> Self {
        let by_stark_size = degree_bits_range
            .map(|degree_bits| {
                (
                    degree_bits,
                    RecursiveCircuitsForTableSize::new::&lt;S>(
                        table,
                        stark,
                        degree_bits,
                        all_ctls,
                        stark_config,
                    ),
                )
            })
            .collect();
        Self { by_stark_size }
    }
}

RecursiveCircuitsForTable 为每个表构建一个递归电路链，链中的每个电路都有不同的大小。当递归电路的大小减少到预设阈值 THRESHOLD_DEGREE_BITS 时，递归过程结束。这个递归链通过 RecursiveCircuitsForTableSize 来实现。

3.2 挑战集与公共输入的处理

在每个递归步骤中，挑战集和公共输入被用来确保证明的有效性。公共输入提供了每个证明的验证信息，而挑战集用于验证每个证明的挑战值。通过 RecursiveChallenger，我们可以观察和验证这些挑战值。

let mut challenger = RecursiveChallenger::&lt;F, C::Hasher, D>::new(&mut builder);
for pi in &pis {
    for h in &pi.trace_cap {
        challenger.observe_elements(h);  // 观察公共输入
    }
}

let ctl_challenges = get_grand_product_challenge_set_target(
    &mut builder,
    &mut challenger,
    stark_config.num_challenges,
);

在每个递归步骤中，RecursiveChallenger 用来观察公共输入中的挑战值，并验证它们的一致性。这确保了每个证明是有效的，并且可以进一步压缩。

3.3 STARK到SNARK的最终转换

pub fn prove_root(
    &self,
    all_stark: &AllStark&lt;F, D>,
    kernel: &Kernel,
    config: &StarkConfig,
    timing: &mut TimingTree,
) -> anyhow::Result&lt;(ProofWithPublicInputs&lt;F, C, D>, PublicValues)> {
    let all_proof = prove::&lt;F, C, D>(all_stark, kernel, config, timing)?;
    verify_proof(all_stark, all_proof.clone(), config).unwrap();
    let mut root_inputs = PartialWitness::new();

    // 处理每个表的证明
    for table in 0..NUM_TABLES {
        let stark_proof = &all_proof.stark_proofs[table];
        let shrunk_proof = self.by_table[table]
            .by_stark_size
            .get(&stark_proof.proof.recover_degree_bits(config))
            .unwrap()
            .shrink(stark_proof, &all_proof.ctl_challenges)?;
        root_inputs.set_proof_with_pis_target(&self.root.proof_with_pis[table], &shrunk_proof);
    }

    // 设置公共输入并生成根证明
    set_public_value_targets(
        &mut root_inputs,
        &self.root.public_values,
        &all_proof.public_values,
    )?;

    let root_proof = self.root.circuit.prove(root_inputs)?;
    Ok((root_proof, all_proof.public_values))
}

在最终的转换中，prove_root 会逐个处理每个表的证明，通过 shrink 方法压缩这些证明，并通过设置公共输入生成最终的SNARK证明。

其中shrink 函数的核心作用是将一个大的 STARK 证明压缩成一个更小的证明，以适配递归证明的计算需求，同时保持原始证明的完整性和真实性。这个过程不仅减少了证明的复杂度，也提升了后续递归电路处理的效率，其具体过程如下：

首先，shrink 会调用 initial_wrapper 中的证明函数，对 STARK 证明进行初步压缩。这一步是关键，负责将原始的较大证明映射到一个较小的电路中。
接着，它会循环调用 shrinking_wrappers 中的每个递归电路，将初步压缩后的证明继续逐步压缩，直到其大小符合目标电路的约束（例如 THRESHOLD_DEGREE_BITS 的递归门大小）。
返回一个最终压缩的 ProofWithPublicInputs 结构体，这个结构体包含了公共输入和压缩后的证明，能够被更小的递归电路直接使用。

fn shrink(
    &self,
    stark_proof_with_metadata: &StarkProofWithMetadata&lt;F, C, D>,
    ctl_challenges: &GrandProductChallengeSet&lt;F>,
) -> anyhow::Result&lt;ProofWithPublicInputs&lt;F, C, D>> {
    let mut proof = self
        .initial_wrapper
        .prove(stark_proof_with_metadata, ctl_challenges)?;
    for wrapper_circuit in &self.shrinking_wrappers {
        proof = wrapper_circuit.prove(&proof)?;
    }
    Ok(proof)
}

原创
学分: 3
分类: Layer2
标签: