Prover Components

The ComponentProvers struct is similar to the Components struct but implements additional functions required by the prover, such as computing the composition polynomial. It is a collection of prover components as follows:

pub struct ComponentProvers<'a, B: Backend> {
    pub components: Vec<&'a dyn ComponentProver<B>>,
    pub n_preprocessed_columns: usize,
}

Here, components is a collection of objects that implement the ComponentProver trait. The ComponentProver trait is a wrapper around the Component trait with an additional function shown as follows:

pub trait ComponentProver<B: Backend>: Component {
    /// Evaluates the constraint quotients of the component on the evaluation domain.
    /// Accumulates quotients in `evaluation_accumulator`.
    fn evaluate_constraint_quotients_on_domain(
        &self,
        trace: &Trace<'_, B>,
        evaluation_accumulator: &mut DomainEvaluationAccumulator<B>,
    );
}

We can convert the ComponentProvers into a Components struct as follows:

    pub fn components(&self) -> Components<'_> {
        Components {
            components: self
                .components
                .iter()
                .map(|c| *c as &dyn Component)
                .collect_vec(),
            n_preprocessed_columns: self.n_preprocessed_columns,
        }
    }

The main function defined on the ComponentProvers struct to compute the composition polynomial is implemented as follows:

    pub fn compute_composition_polynomial(
        &self,
        random_coeff: SecureField,
        trace: &Trace<'_, B>,
    ) -> SecureCirclePoly<B> {
        let total_constraints: usize = self.components.iter().map(|c| c.n_constraints()).sum();
        let mut accumulator = DomainEvaluationAccumulator::new(
            random_coeff,
            self.components().composition_log_degree_bound(),
            total_constraints,
        );
        for component in &self.components {
            component.evaluate_constraint_quotients_on_domain(trace, &mut accumulator)
        }
        accumulator.finalize()
    }

Let us examine the above function for our example AIR containing two components. It takes the following three inputs:

&self: This is the ComponentProvers on which the function is called.
random_coeff: This is an element from the SecureField (i.e. $\mathsf{QM31}$ ). In our example, this is represented as $\gamma$ .
trace: The Trace struct which contains all the polynomials that make up the entire trace including all the components. For efficiency, it stores each polynomial in both coefficients and evaluations form.

pub struct Trace<'a, B: Backend> {
    /// Polynomials for each column.
    pub polys: TreeVec<ColumnVec<&'a CirclePoly<B>>>,
    /// Evaluations for each column (evaluated on their commitment domains).
    pub evals: TreeVec<ColumnVec<&'a CircleEvaluation<B, BaseField, BitReversedOrder>>>,
}

Now let us examine the body of the function. First, we compute total_constraints and initialize an accumulator. The total_constraints determine the number of powers of

\gamma

(random_coeff) required for the random linear combination. For each component, we call evaluate_constraint_quotients_on_domain, which computes and accumulates the evaluations of that component’s quotients on their respective evaluation domains within the accumulator. For the

0

th component, we add the evaluations of the quotient

q_0

over its evaluation domain

D_{n_0 + \beta}

to the accumulator. Similarly, for the

1

st component, we add the evaluations of the quotient

q_1

over its evaluation domain

D_{n_1 + \beta}

to the accumulator. After adding all component quotient evaluations to the accumulator, we call the finalize() function, which:

Combines the accumulated evaluations at different domain sizes to compute the evaluations of the quotient composition polynomial $q$ over the domain $D_{n + \beta}$ where $n = \max{(n_1, n_2)}$ .
Interpolates $q$ over $D_{n + \beta}$ using circle FFT to convert it into coefficient representation.

Note that the output is a SecureCirclePoly since the evaluations of

q

are in the secure field

\mathsf{QM31}

(as

\gamma

is randomly sampled from

\mathsf{QM31}

Protocol

S-two book

Cheatsheets

Starknet Privacy