> ## Documentation Index
> Fetch the complete documentation index at: https://docs.starknet.io/llms.txt
> Use this file to discover all available pages before exploring further.

# 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:

```rust theme={null}
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](/learn/S-two-book/how-it-works/air/components) and [Prover Components](/learn/S-two-book/how-it-works/air/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](/learn/S-two-book/how-it-works/pcs/prover).

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

```rust theme={null}
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](/learn/S-two-book/how-it-works/air/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](/learn/S-two-book/how-it-works/pcs/overview#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](/learn/S-two-book/how-it-works/pcs/prover#prove) 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.