1. ZKM Prover Proof Architecture

The ZKM Prover employs Plonky2 to construct a zero-knowledge proof system. Its primary steps involve generating, aggregating, and compressing proofs for each Plonkish table. The process is detailed below.

1.1 Generating Plonky2 Proofs for Each Plonkish Table

In this step, ZKM Prover uses the Plonky2 algorithm to generate a set of proofs for each Plonkish table. These proofs include sub-proofs such as Permutation Check and lookup arguments. These sub-proofs ensure that the data within the Plonkish table satisfies specific constraints while maintaining privacy and validity. The proof structure can be customized as needed. For example, the Permutation Check verifies the arrangement relationships between input values, while the lookup argument validates the correctness of table lookup operations. These proofs ensure that the data’s legality can be verified via zero-knowledge proof without leaking additional information, as illustrated in Figure 1.

1.2 Aggregating Plonky2 Proofs from Plonkish Tables

Once Plonky2 proofs are generated for each Plonkish table, the ZKM Prover aggregates them into a unified Root Proof. This involves representing each Plonkish proof as a circuit—a logical verification problem in circuit form. In this circuit, the inputs are the individual Plonkish proofs, and the output is the verified aggregate proof. Plonky2 is then called again to combine these individual proofs into a single Root Proof. This Root Proof synthesizes multiple proofs, ensuring their correctness while allowing verification of multiple Plonkish tables through one proof, as shown in Figure 2. The aggregation typically involves a random linear combination of sub-proofs, compressing multiple constraints into a single Root Proof.

1.3 Compressing the Root Proof into a SNARK Proof

The Root Proof, being a STARK Proof, can be lengthy and resource-intensive to verify. To address this, the ZKM Prover compresses the STARK Proof to reduce computational and storage costs. During this process, the Root Proof is represented as a circuit that validates its correctness. Subsequently, the ZKM Prover applies zkSNARK algorithms, such as Groth16 or Plonk, to further compress the STARK Proof into a shorter SNARK Proof. These zkSNARK techniques enhance verification efficiency while maintaining zero-knowledge properties. This transformation effectively reduces verification overhead and boosts system throughput.

2. zkVM Proof Workflow

This section introduces the proof generation process for each zkVM component (corresponding to each Plonkish table), covering the following modules:

pub struct AllStark<F: RichField + Extendable<D>, const D: usize> {
    pub arithmetic_stark: ArithmeticStark<F, D>,
    pub cpu_stark: CpuStark<F, D>,
    pub poseidon_stark: PoseidonStark<F, D>,
    pub poseidon_sponge_stark: PoseidonSpongeStark<F, D>,
    pub logic_stark: LogicStark<F, D>,
    pub memory_stark: MemoryStark<F, D>,
    pub cross_table_lookups: Vec<CrossTableLookup<F>>,
}
// prover/src/all_stark.rs

Next, we will introduce the basic functionality of each module:

arithmetic_stark: Verifies the correctness of arithmetic operations, including basic operations such as addition and multiplication. It ensures that computations adhere to expected arithmetic rules, such as polynomial calculations and numerical operations, by adding corresponding constraints in the circuit.

cpu_stark: Handles the verification of CPU instruction simulation and logical execution, ensuring the correctness of instruction sequence execution states. This module simulates a CPU execution environment and can verify state transitions, register updates, and instruction execution order.

poseidon_stark: Verifies the computation process of the Poseidon hash function, ensuring that the input data corresponds to the correct hash output. Poseidon is a zero-knowledge-friendly hash function commonly used in cryptographic operations like Merkle tree root generation and hash mapping.

poseidon_sponge_stark: Responsible for verifying the computations of the Poseidon Sponge construction, ensuring the correctness of hash chains or encryption operations. The Sponge construction is a general framework widely used in random number generation and hash data compression scenarios.

logic_stark: Verifies the correctness of logical operations, including Boolean and bitwise operations such as AND, OR, and XOR. This module constrains logical reasoning within circuits, ensuring that the results of logical computations match the inputs.

memory_stark: Verifies the correctness of memory read/write and state management, ensuring that data storage, loading, and index access meet expectations. This module is suitable for verifying memory consistency and state changes during program execution.

cross_table_lookups: Handles constraints for cross-table lookups, connecting the computation results of different modules to verify their data dependencies. It ensures that the outputs and inputs across tables are consistent, achieving data integrity and correctness across modules.

Proof Aggregation Methods

Next, we will focus on introducing the aggregation method from a code perspective:

1. Segment File Reading and Kernel Generation: Load segment files sequentially to generate the corresponding kernel data.
2. Root Proof Generation: Generate independent root proofs for each segment.
3. Recursive Aggregation: Use prove_aggregation to merge proofs from multiple segments into a comprehensive proof.
4. Block Proof Generation: After processing all segments, generate the final block proof.
5. Verification: Each stage includes a verification step to ensure correctness.

The relative code path is: prover/examples/zkmips.rs.

2.1 Initialization of Basic Configuration

This process determines the proof environment, parameters, and dependencies to lay the foundation for subsequent operations, including:.

1. Parameter Definition:

• Use GoldilocksField as the field to ensure that mathematical computations occur in a specific finite field.
• Configure PoseidonGoldilocksConfig to support Poseidon hashing.
• Use recursive parameters InnerParameters and OuterParameters, possibly related to Groth16 zkSNARK configurations.‍

‍2. Input Check:

• Ensure the number of segment files is at least 2, with one file corresponding to one circuit; otherwise, terminate the program.

type InnerParameters = DefaultParameters;
type OuterParameters = Groth16WrapperParameters;
type F = GoldilocksField;
const D: usize = 2;
type C = PoseidonGoldilocksConfig;

if seg_file_number < 2 {
    panic!("seg file number must >= 2\n");
}

2.2 Initialization of Circuits and Timer

This process initializes recursive proof circuits and a time tracker, including:

1. Timer Initialization: TimingTree is used to track the time consumed by the entire process for performance optimization.
2. Creation of AllStark Object: The core proof structure encapsulates the logic for multi-segment proofs.
3. Loading Recursive Circuits: AllRecursiveCircuits provides support for recursive circuits, ensuring subsequent proofs can be recursively merged.

let total_timing = TimingTree::new("prove total time", log::Level::Info);
let all_stark = AllStark::<F, D>::default();
let config = StarkConfig::standard_fast_config();
let all_circuits = AllRecursiveCircuits::<F, C, D>::new(&all_stark, &DEGREE_BITS_RANGE, &config);

2.3 Loading the First Segment File

Read the first segment file and generate the root proof, including:

1. File Loading: Read the first segment file via its path.
2. Kernel Data Generation: Call segment_kernel to parse segment data and generate initial inputs.
3. Root Proof Generation: Use prove_root to generate the proof for the first segment, returning the initial aggregated proof (agg_proof) and public values.

let seg_file = format!("{}/{}", seg_dir, seg_start_id);
log::info!("Process segment {}", seg_file);
let seg_reader = BufReader::new(File::open(seg_file)?);
let input_first = segment_kernel(basedir, block, file, seg_reader, seg_size);
let mut timing = TimingTree::new("prove root first", log::Level::Info);
let (mut agg_proof, mut updated_agg_public_values) =
    all_circuits.prove_root(&all_stark, &input_first, &config, &mut timing)?;

2.4 Verify the Root Proof

Verify whether the generated root proof is correct, including:

1. Print Timing: Output the time consumed during the root proof generation process.
2. Verify the Proof: Call verify_root to ensure the validity of the root proof. If verification fails, the program will throw an error.

timing.filter(Duration::from_millis(100)).print();
all_circuits.verify_root(agg_proof.clone())?;

2.5 Load the Second Segment File and Generate Root Proof

If the number of segment files is even, process the second segment and generate its proof, including:

1. Read the Second Segment File: Load the file via its path.
2. Generate Kernel Data: Call segment_kernel to process the file data.
3. Generate Root Proof: Call prove_root to generate the proof for the second segment.
4. Verify Root Proof: Verify the generated root proof using verify_root.

let seg_file = format!("{}/{}", seg_dir, seg_start_id + 1);
log::info!("Process segment {}", seg_file);
let seg_reader = BufReader::new(File::open(seg_file)?);
let input = segment_kernel(basedir, block, file, seg_reader, seg_size);
timing = TimingTree::new("prove root second", log::Level::Info);
let (root_proof, public_values) = all_circuits.prove_root(&all_stark, &input, &config, &mut timing)?;
timing.filter(Duration::from_millis(100)).print();
all_circuits.verify_root(root_proof.clone())?;

2.6 Merge Proofs of the First Two Segments

Merge the proofs of the first two segments and update public values, including:

1. Update Public Values: Merge the public values (roots_before, roots_after, and user data) of the two segments.
2. Merge Proofs: Call prove_aggregation to merge the first two root proofs.
3. Verify Aggregated Proof: Ensure the correctness of the merged proof using verify_aggregation.

let agg_public_values = PublicValues {
    roots_before: updated_agg_public_values.roots_before,
    roots_after: public_values.roots_after,
    userdata: public_values.userdata,
};
(agg_proof, updated_agg_public_values) = all_circuits.prove_aggregation(
    false,
    &agg_proof,
    false,
    &root_proof,
    agg_public_values.clone(),
)?;
all_circuits.verify_aggregation(&agg_proof)?;

2.7 Process Remaining Segment Files

Generate root proofs and recursively merge them for each pair of segment files, including:

1. Load Each Pair of Segment Files: Read files for even and odd segments.
2. Generate Root Proofs: Call prove_root to generate proofs for the two segments.
3. Recursive Merging: Merge the two root proofs using prove_aggregation.

for i in 0..seg_num / 2 {
    let seg_file = format!("{}/{}", seg_dir, base_seg + (i << 1));
    let seg_reader = BufReader::new(File::open(&seg_file)?);
    let input_first = segment_kernel(basedir, block, file, seg_reader, seg_size);
    let (root_proof_first, first_public_values) =
        all_circuits.prove_root(&all_stark, &input_first, &config, &mut timing)?;

    let seg_file = format!("{}/{}", seg_dir, base_seg + (i << 1) + 1);
    let seg_reader = BufReader::new(File::open(&seg_file)?);
    let input = segment_kernel(basedir, block, file, seg_reader, seg_size);
    let (root_proof, public_values) =
        all_circuits.prove_root(&all_stark, &input, &config, &mut timing)?;

    let new_agg_public_values = PublicValues {
        roots_before: first_public_values.roots_before,
        roots_after: public_values.roots_after,
        userdata: public_values.userdata,
    };
    let (new_agg_proof, new_updated_agg_public_values) = all_circuits.prove_aggregation(
        false,
        &root_proof_first,
        false,
        &root_proof,
        new_agg_public_values,
    )?;
}

2.8 Generate the Final Block Proof

After completing the recursive aggregation of all segments, generate the final block proof, including:

1. Call prove_block: Generate the final block proof.
2. Verify the Block Proof: Ensure the validity of the final proof using verify_block.

let (block_proof, _block_public_values) =
    all_circuits.prove_block(None, &agg_proof, updated_agg_public_values)?;
all_circuits.verify_block(&block_proof)?;

3. Function Analysis

The two most critical methods are prove_aggregation and prove_root, which are used for proof aggregation and root proof generation, respectively:

Function prove_aggregation

The core function of this method is to perform recursive proof aggregation. It merges two proofs to generate a new aggregated proof while maintaining the correctness of public values. It aggregates two proofs (lhs_proof and rhs_proof) into a new proof and updates public values (public_values) in the process. The main steps include:

1. Circuit Binding: Map the proofs, public values, and verifier data to circuit targets.
2. Proof Generation: Call the prove method to generate the aggregated proof based on the inputs.
3. Error Handling: Use anyhow to handle potential errors in public value settings, enhancing robustness.

File Path: prover/src/fixed_recursive_verifier.rs

Function Definition

pub fn prove_aggregation(
    &self,
    lhs_is_agg: bool, // Whether the left-hand-side proof is an aggregated proof
    lhs_proof: &ProofWithPublicInputs<F, C, D>, // Left-hand-side proof (with public inputs)
    rhs_is_agg: bool, // Whether the right-hand-side proof is an aggregated proof
    rhs_proof: &ProofWithPublicInputs<F, C, D>, // Right-hand-side proof (with public inputs)
    public_values: PublicValues, // Public values
) -> anyhow::Result<(ProofWithPublicInputs<F, C, D>, PublicValues)>

‍
Inputs:

• lhs_is_agg and rhs_is_agg: Indicate whether the left and right proofs are aggregated proofs.
• lhs_proof and rhs_proof: The left and right proofs, both containing public input data.
• public_values: The current public values to be updated.

Return Values:

• Aggregated proof (ProofWithPublicInputs).
• Updated public values.

3.1 Initialization of PartialWitness

let mut agg_inputs = PartialWitness::new();

‍
PartialWitness is a core structure in the proof system, used to set variable values (witnesses) within the circuit.

Here, an empty PartialWitness object is initialized to store the input data for the aggregation proof circuit.

3.2 Setting Inputs for the Left-Hand-Side Proof

agg_inputs.set_bool_target(self.aggregation.lhs.is_agg, lhs_is_agg);
agg_inputs.set_proof_with_pis_target(&self.aggregation.lhs.agg_proof, lhs_proof);
agg_inputs.set_proof_with_pis_target(&self.aggregation.lhs.evm_proof, lhs_proof);

‍

set_bool_target:

• Maps whether the left-hand-side proof is an aggregated proof (lhs_is_agg) to the circuit target variable self.aggregation.lhs.is_agg.
• This is a Boolean value indicating the type of the left-hand-side proof.

set_proof_with_pis_target:

• Maps the left-hand-side proof to the aggregation proof target self.aggregation.lhs.agg_proof.
• Simultaneously binds the proof to the Ethereum verification target self.aggregation.lhs.evm_proof.

3.3 Setting Inputs for the Right-Hand-Side Proof

agg_inputs.set_bool_target(self.aggregation.rhs.is_agg, rhs_is_agg);
agg_inputs.set_proof_with_pis_target(&self.aggregation.rhs.agg_proof, rhs_proof);
agg_inputs.set_proof_with_pis_target(&self.aggregation.rhs.evm_proof, rhs_proof);

‍

Similar to the left-hand-side setup, the inputs for the right-hand-side proof are configured:

• The Boolean value rhs_is_agg indicates whether the right-hand-side proof is an aggregated proof.
• rhs_proof is mapped to both the aggregation proof and Ethereum verification targets.

3.4 Setting Verifier Data

agg_inputs.set_verifier_data_target(
    &self.aggregation.cyclic_vk,
    &self.aggregation.circuit.verifier_only,
);

‍
set_verifier_data_target:

• Sets the verifier data targets.
• self.aggregation.cyclic_vk represents the cyclic verification key for validating recursive aggregated proofs.
• self.aggregation.circuit.verifier_only provides circuit-specific verifier data.

3.5 Setting Public Value Targets

set_public_value_targets(
    &mut agg_inputs,
    &self.aggregation.public_values,
    &public_values,
)
.map_err(|_| {
    anyhow::Error::msg("Invalid conversion when setting public values targets.")
})?;

‍
set_public_value_targets:

• Maps the provided public values (public_values) to the circuit’s public value targets (self.aggregation.public_values).
• If mapping fails, an error message is returned.

3.6 Generating the Aggregated Proof

let aggregation_proof = self.aggregation.circuit.prove(agg_inputs)?;

‍
Proof Generation:

• Calls self.aggregation.circuit to generate the proof based on the configured agg_inputs.
• Returns the aggregated proof object, aggregation_proof.

3.7 Returning the Aggregated Result

Ok((aggregation_proof, public_values))

The returned results include:

• The generated aggregated proof, aggregation_proof.
• The updated public values, public_values.

4. Function prove_root

This function is primarily designed to process proof data for a specific table and generate the root proof for recursive verification. It integrates STARK proofs with zkSNARK circuit proofs, compressing and embedding the STARK proofs into a recursive proof circuit. The overall process includes:

1. Generate STARK Proof:

• Use the prove function to create the STARK proof.
• Verify the generated STARK proof to ensure correctness.

2. Compress Proofs for Each Table:

• Iterate through each table and extract the corresponding STARK proof.
• Compress the proof to fit the recursive circuit.

3. Set Recursive Circuit Targets:

• Configure the verification data indices, compressed proofs, and public values in the recursive circuit targets.

4. Generate Root Proof:

• Call the recursive circuit’s prove function to create the root proof.

5. Return Results:

• Return the generated root proof and the updated public values.

Function Definition

pub fn prove_root(
    &self,
    all_stark: &AllStark<F, D>, // STARK proof configuration
    kernel: &Kernel,            // Kernel for core processing
    config: &StarkConfig,       // STARK configuration
    timing: &mut TimingTree,    // Timing tracker
) -> anyhow::Result<(ProofWithPublicInputs<F, C, D>, PublicValues)>

‍
Input Parameters:

• all_stark: Configuration for all STARK proofs, controlling proof generation.
• kernel: Core kernel containing table and computation logic.
• config: STARK configuration specifying proof-related parameters.
• timing: Timer to track operation durations.

Return Values:

• ProofWithPublicInputs: The root proof containing public inputs.
• PublicValues: Updated public values.

Below is a step-by-step analysis of the implementation:

4.1 Generate and Verify STARK Proof

let all_proof = prove::<F, C, D>(all_stark, kernel, config, timing)?;
verify_proof(all_stark, all_proof.clone(), config).unwrap();

‍
1. Generate STARK Proof:

• Use the prove function with all_stark and kernel inputs to generate the STARK proof all_proof.
• This proof contains all table-specific STARK proofs and public inputs.

2. Verify STARK Proof:

• Call verify_proof to validate the generated STARK proof.
• The program will panic on validation failure, ensuring correctness.

4.2 Initialize Root Proof Inputs

let mut root_inputs = PartialWitness::new();

Create a PartialWitness object to prepare inputs for the recursive circuit.

4.3 Iterate Through All Tables

for table in 0..NUM_TABLES {
    let stark_proof = &all_proof.stark_proofs[table];
    let original_degree_bits = stark_proof.proof.recover_degree_bits(config);

Iterate through all tables (NUM_TABLES), extracting each table’s corresponding STARK proof.

Recover the original polynomial degree bits using recover_degree_bits.

4.4 Shrink STARK Proofs

let table_circuits = &self.by_table[table];
let shrunk_proof = table_circuits
    .by_stark_size
    .get(&original_degree_bits)
    .ok_or_else(|| {
        anyhow::Error::msg(format!(
            "Missing preprocessed circuits for {:?} table with size {}.",
            Table::all()[table],
            original_degree_bits,
        ))
    })?
    .shrink(stark_proof, &all_proof.ctl_challenges)?;

Retrieve Circuit:

• Access preprocessed circuits (self.by_table[table].by_stark_size) for the table’s degree bits.

Shrink Proof:

• Call the shrink function to compress the STARK proof, making it compatible with the recursive circuit.
• The shrink function reduces the proof size while preserving its integrity and validity.

Core shrink Implementation

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)
}

4.5 Set Target Values

let index_verifier_data = table_circuits
    .by_stark_size
    .keys()
    .position(|&size| size == original_degree_bits)
    .unwrap();
root_inputs.set_target(
    self.root.index_verifier_data[table],
    F::from_canonical_usize(index_verifier_data),
);
root_inputs.set_proof_with_pis_target(&self.root.proof_with_pis[table], &shrunk_proof);

‍
Set Verification Data Index:

• Locate the degree bits in verification data indices and set it as a target for the recursive circuit.

Set Compressed Proof:

• Assign the shrunk proof to the recursive circuit target.

4.6 Configure Cyclic Verification Data

root_inputs.set_verifier_data_target(
    &self.root.cyclic_vk,
    &self.aggregation.circuit.verifier_only,
);

Bind the cyclic verification key (cyclic_vk) to the recursive circuit’s verifier data target.

4.7 Map Public Values

set_public_value_targets(
    &mut root_inputs,
    &self.root.public_values,
    &all_proof.public_values,
)
.map_err(|_| {
    anyhow::Error::msg("Invalid conversion when setting public values targets.")
})?;

Map public values from the STARK proof to the recursive circuit’s public value targets.

4.8 Generate Root Proof

let root_proof = self.root.circuit.prove(root_inputs)?;

Call the recursive circuit’s prove function to generate the root proof.

4.9 Return Results

Ok((root_proof, all_proof.public_values))

Return the generated root proof (root_proof) and the STARK proof’s public values.

‍

Subscribe to the ZKM Blog to stay updated with the latest research by ZKM. If you have any questions about the article, you can contact the ZKM team on discord: discord.com/zkm