STARK Prover

This section provides an overview of the prove function, the key function in the STARK proof generation process. It is implemented as follows:

pub fn prove<B: BackendForChannel<MC>, MC: MerkleChannel>(
    components: &[&dyn ComponentProver<B>],
    channel: &mut MC::C,
    mut commitment_scheme: CommitmentSchemeProver<'_, B, MC>,
) -> Result<StarkProof<MC::H>, ProvingError> {
    let n_preprocessed_columns = commitment_scheme.trees[PREPROCESSED_TRACE_IDX]
        .polynomials
        .len();
    let component_provers = ComponentProvers {
        components: components.to_vec(),
        n_preprocessed_columns,
    };
    let trace = commitment_scheme.trace();

    // Evaluate and commit on composition polynomial.
    let random_coeff = channel.draw_secure_felt();

    let span = span!(Level::INFO, "Composition", class = "Composition").entered();
    let span1 = span!(
        Level::INFO,
        "Generation",
        class = "CompositionPolynomialGeneration"
    )
    .entered();
    let composition_poly = component_provers.compute_composition_polynomial(random_coeff, &trace);
    span1.exit();

    let mut tree_builder = commitment_scheme.tree_builder();
    tree_builder.extend_polys(composition_poly.into_coordinate_polys());
    tree_builder.commit(channel);
    span.exit();

    // Draw OODS point.
    let oods_point = CirclePoint::<SecureField>::get_random_point(channel);

    // Get mask sample points relative to oods point.
    let mut sample_points = component_provers.components().mask_points(oods_point);

    // Add the composition polynomial mask points.
    sample_points.push(vec![vec![oods_point]; SECURE_EXTENSION_DEGREE]);

    // Prove the trace and composition OODS values, and retrieve them.
    let commitment_scheme_proof = commitment_scheme.prove_values(sample_points, channel);
    let proof = StarkProof(commitment_scheme_proof);
    info!(proof_size_estimate = proof.size_estimate());

    // Evaluate composition polynomial at OODS point and check that it matches the trace OODS
    // values. This is a sanity check.
    if proof.extract_composition_oods_eval().unwrap()
        != component_provers
            .components()
            .eval_composition_polynomial_at_point(oods_point, &proof.sampled_values, random_coeff)
    {
        return Err(ProvingError::ConstraintsNotSatisfied);
    }

    Ok(proof)
}

Let us go through the function in detail.

Input and Output

It takes the following as input:

• components: A list of AIR components. For more details, refer to the Components and Prover Components sections.
• channel: A Fiat-Shamir channel for non-interactive randomness.
• commitment_scheme: A CommitmentSchemeProver for committing to trace and composition polynomials. For more details, refer to the PCS Prover section.

It outputs a StarkProof object if successful, or a ProvingError if any constraint is not satisfied. The StarkProof object is a wrapper around CommitmentSchemeProof.

pub struct StarkProof<H: MerkleHasher>(pub CommitmentSchemeProof<H>);

Step-by-Step Breakdown

1. Determine Preprocessed Columns

   • The function determines the number of preprocessed columns, n_preprocessed_columns, from the commitment_scheme, which is used to initialize the ComponentProvers structure.

2. Collect Trace Data

   • The trace, containing all columns (execution, interaction, preprocessed), is retrieved from the commitment_scheme. This includes both coefficient and evaluation forms for each column.

3. Composition Polynomial Construction

   • A random_coeff is drawn from the channel.
   • The composition_poly is computed as a random linear combination of all constraint quotient polynomials, using powers of the random coefficient. For more details, refer to the Prover Components section.

4. Commit to the Composition Polynomial

   • The composition_poly is split into coordinate polynomials and committed to using a Merkle tree.

5. Out-of-Domain Sampling (OODS)

   • An oods_point is drawn randomly from the channel. This point is used to bind the prover to a unique low-degree polynomial, preventing ambiguity in the list decoding regime. For more details, refer to the Out-of-Domain Sampling section.

6. Determine Sample Points

   • The function computes all sample_points required to verify constraints at the OODS point, using the mask_points function. This includes all necessary offsets for each constraint and the OODS points for the composition polynomial.

7. Openings and Proof Generation

   • The commitment_scheme is asked to open all committed polynomials at the sampled points, producing the required evaluations and Merkle authentication paths. This is handled by the prove_values function, which also integrates the FRI protocol for low-degree testing. For more details, refer to the PCS Prover section.

8. Sanity Check

   • The function checks that the composition polynomial evaluated at the OODS point matches the value reconstructed from the sampled trace values. If not, it returns a ConstraintsNotSatisfied error.

9. Return Proof

   • If all checks pass, the function returns a StarkProof object containing the full proof transcript, including all commitments, openings, and FRI proof.