openvm_stark_backend/prover/cpu/quotient/
mod.rs

Help
1use std::sync::Arc;
2
3use itertools::{izip, multiunzip, Itertools};
4use p3_commit::{Pcs, PolynomialSpace};
5use p3_field::FieldAlgebra;
6use p3_matrix::{dense::RowMajorMatrix, Matrix};
7use p3_util::log2_strict_usize;
8use tracing::instrument;
9
10use self::single::compute_single_rap_quotient_values;
11use super::PcsData;
12use crate::{
13    air_builders::symbolic::SymbolicExpressionDag,
14    config::{Com, Domain, PackedChallenge, StarkGenericConfig, Val},
15    prover::types::RapView,
16};
17
18mod evaluator;
19pub(crate) mod single;
20
21pub struct QuotientCommitter<'pcs, SC: StarkGenericConfig> {
22    pcs: &'pcs SC::Pcs,
23    alpha: SC::Challenge,
24}
25
26impl<'pcs, SC: StarkGenericConfig> QuotientCommitter<'pcs, SC> {
27    pub fn new(pcs: &'pcs SC::Pcs, alpha: SC::Challenge) -> Self {
28        Self { pcs, alpha }
29    }
30
31    /// Constructs quotient domains and computes the evaluation of the quotient polynomials
32    /// on the quotient domains of each RAP.
33    ///
34    /// ## Assumptions
35    /// - `constraints`, `extended_views`, `quotient_degrees` have equal lengths and the length equals number of RAPs.
36    /// - `quotient_degrees` is the factor to **multiply** the trace degree by to get the degree of the quotient polynomial. This should be determined from the constraint degree of the RAP.
37    /// - `extended_views` is a view of the trace polynomials evaluated on the quotient domain, with rows bit reversed to account for the fact that the quotient domain is different for each RAP.
38    #[instrument(name = "compute quotient values", level = "info", skip_all)]
39    pub fn quotient_values(
40        &self,
41        constraints: &[&SymbolicExpressionDag<Val<SC>>],
42        extended_views: Vec<RapView<impl Matrix<Val<SC>>, Val<SC>, SC::Challenge>>,
43        quotient_degrees: &[u8],
44    ) -> QuotientData<SC> {
45        assert_eq!(constraints.len(), extended_views.len());
46        assert_eq!(constraints.len(), quotient_degrees.len());
47        let inner = izip!(constraints, extended_views, quotient_degrees)
48            .map(|(constraints, extended_view, &quotient_degree)| {
49                self.single_rap_quotient_values(constraints, extended_view, quotient_degree)
50            })
51            .collect();
52        QuotientData { inner }
53    }
54
55    pub(super) fn single_rap_quotient_values(
56        &self,
57        constraints: &SymbolicExpressionDag<Val<SC>>,
58        view: RapView<impl Matrix<Val<SC>>, Val<SC>, SC::Challenge>,
59        quotient_degree: u8,
60    ) -> SingleQuotientData<SC> {
61        let log_trace_height = view.pair.log_trace_height;
62        let trace_domain = self
63            .pcs
64            .natural_domain_for_degree(1usize << log_trace_height);
65        let quotient_domain =
66            trace_domain.create_disjoint_domain(trace_domain.size() * quotient_degree as usize);
67
68        let (after_challenge_lde_on_quotient_domain, challenges, exposed_values_after_challenge): (
69            Vec<_>,
70            Vec<_>,
71            Vec<_>,
72        ) = multiunzip(view.per_phase.into_iter().map(|view| {
73            (
74                view.inner
75                    .expect("gap in challenge phase not supported yet"),
76                view.challenges
77                    .into_iter()
78                    .map(PackedChallenge::<SC>::from_f)
79                    .collect_vec(),
80                view.exposed_values
81                    .into_iter()
82                    .map(PackedChallenge::<SC>::from_f)
83                    .collect_vec(),
84            )
85        }));
86
87        let quotient_values = compute_single_rap_quotient_values::<SC, _>(
88            constraints,
89            trace_domain,
90            quotient_domain,
91            view.pair.preprocessed,
92            view.pair.partitioned_main,
93            after_challenge_lde_on_quotient_domain,
94            &challenges,
95            self.alpha,
96            &view.pair.public_values,
97            &exposed_values_after_challenge,
98        );
99        SingleQuotientData {
100            quotient_degree: quotient_degree as usize,
101            quotient_domain,
102            quotient_values,
103        }
104    }
105
106    #[instrument(name = "commit to quotient poly chunks", skip_all)]
107    pub fn commit(&self, data: QuotientData<SC>) -> (Com<SC>, PcsData<SC>) {
108        let (log_trace_heights, quotient_domains_and_chunks): (Vec<_>, Vec<_>) = data
109            .split()
110            .into_iter()
111            .map(|q| {
112                (
113                    log2_strict_usize(q.domain.size()) as u8,
114                    (q.domain, q.chunk),
115                )
116            })
117            .unzip();
118        let (commit, data) = self.pcs.commit(quotient_domains_and_chunks);
119        (
120            commit,
121            PcsData {
122                data: Arc::new(data),
123                log_trace_heights,
124            },
125        )
126    }
127}
128
129/// The quotient polynomials from multiple RAP matrices.
130pub(super) struct QuotientData<SC: StarkGenericConfig> {
131    inner: Vec<SingleQuotientData<SC>>,
132}
133
134impl<SC: StarkGenericConfig> QuotientData<SC> {
135    /// Splits the quotient polynomials from multiple AIRs into chunks of size equal to the trace domain size.
136    pub fn split(self) -> impl IntoIterator<Item = QuotientChunk<SC>> {
137        self.inner.into_iter().flat_map(|data| data.split())
138    }
139}
140
141/// The quotient polynomial from a single matrix RAP, evaluated on the quotient domain.
142pub(super) struct SingleQuotientData<SC: StarkGenericConfig> {
143    quotient_degree: usize,
144    /// Quotient domain
145    quotient_domain: Domain<SC>,
146    /// Evaluations of the quotient polynomial on the quotient domain
147    quotient_values: Vec<SC::Challenge>,
148}
149
150impl<SC: StarkGenericConfig> SingleQuotientData<SC> {
151    /// The vector of evaluations of the quotient polynomial on the quotient domain,
152    /// first flattened from vector of extension field elements to matrix of base field elements,
153    /// and then split into chunks of size equal to the trace domain size (quotient domain size
154    /// divided by `quotient_degree`).
155    pub fn split(self) -> impl IntoIterator<Item = QuotientChunk<SC>> {
156        let quotient_degree = self.quotient_degree;
157        let quotient_domain = self.quotient_domain;
158        // Flatten from extension field elements to base field elements
159        let quotient_flat = RowMajorMatrix::new_col(self.quotient_values).flatten_to_base();
160        let quotient_chunks = quotient_domain.split_evals(quotient_degree, quotient_flat);
161        let qc_domains = quotient_domain.split_domains(quotient_degree);
162        qc_domains
163            .into_iter()
164            .zip_eq(quotient_chunks)
165            .map(|(domain, chunk)| QuotientChunk { domain, chunk })
166    }
167}
168
169/// The vector of evaluations of the quotient polynomial on the quotient domain,
170/// split into chunks of size equal to the trace domain size (quotient domain size
171/// divided by `quotient_degree`).
172///
173/// This represents a single chunk, where the vector of extension field elements is
174/// further flattened to a matrix of base field elements.
175pub struct QuotientChunk<SC: StarkGenericConfig> {
176    /// Chunk of quotient domain, which is a coset of the trace domain
177    pub domain: Domain<SC>,
178    /// Matrix with number of rows equal to trace domain size,
179    /// and number of columns equal to extension field degree.
180    pub chunk: RowMajorMatrix<Val<SC>>,
181}
openvm_stark_backend/prover/cpu/quotient/mod.rs

openvm_stark_backend/prover/cpu/quotient/
mod.rs
