kimchi_msm/
column_env.rs

1use ark_ff::FftField;
2use ark_poly::{Evaluations, Radix2EvaluationDomain};
3
4use crate::{logup, logup::LookupTableID, witness::Witness};
5use kimchi::circuits::{
6    berkeley_columns::{BerkeleyChallengeTerm, BerkeleyChallenges},
7    domains::{Domain, EvaluationDomains},
8    expr::{ColumnEnvironment as TColumnEnvironment, Constants},
9};
10
11/// The collection of polynomials (all in evaluation form) and constants
12/// required to evaluate an expression as a polynomial.
13///
14/// All are evaluations.
15pub struct ColumnEnvironment<
16    'a,
17    const N: usize,
18    const N_REL: usize,
19    const N_DSEL: usize,
20    const N_FSEL: usize,
21    F: FftField,
22    ID: LookupTableID,
23> {
24    /// The witness column polynomials. Includes relation columns,
25    /// fixed selector columns, and dynamic selector columns.
26    pub witness: &'a Witness<N, Evaluations<F, Radix2EvaluationDomain<F>>>,
27    /// Fixed selectors. These are "predefined" with the circuit, and,
28    /// unlike public input or dynamic selectors, are not part of the
29    /// witness that users are supposed to change after the circuit is
30    /// fixed.
31    pub fixed_selectors: &'a [Evaluations<F, Radix2EvaluationDomain<F>>; N_FSEL],
32    /// The value `prod_{j != 1} (1 - omega^j)`, used for efficiently
33    /// computing the evaluations of the unnormalized Lagrange basis polynomials.
34    pub l0_1: F,
35    /// Constant values required
36    pub constants: Constants<F>,
37    /// Challenges from the IOP.
38    pub challenges: BerkeleyChallenges<F>,
39    /// The domains used in the PLONK argument.
40    pub domain: EvaluationDomains<F>,
41
42    /// Lookup specific polynomials
43    pub lookup: Option<logup::prover::QuotientPolynomialEnvironment<'a, F, ID>>,
44}
45
46impl<
47        'a,
48        const N_WIT: usize,
49        const N_REL: usize,
50        const N_DSEL: usize,
51        const N_FSEL: usize,
52        F: FftField,
53        ID: LookupTableID,
54    > TColumnEnvironment<'a, F, BerkeleyChallengeTerm, BerkeleyChallenges<F>>
55    for ColumnEnvironment<'a, N_WIT, N_REL, N_DSEL, N_FSEL, F, ID>
56{
57    type Column = crate::columns::Column<usize>;
58
59    fn get_column(
60        &self,
61        col: &Self::Column,
62    ) -> Option<&'a Evaluations<F, Radix2EvaluationDomain<F>>> {
63        // TODO: when non-literal constant generics are available, substitute N with N_REG + N_DSEL + N_FSEL
64        assert!(N_WIT == N_REL + N_DSEL);
65        assert!(N_WIT == self.witness.len());
66        match *col {
67            // Handling the "relation columns" at the beginning of the witness columns
68            Self::Column::Relation(i) => {
69                // TODO: add a test for this
70                assert!(i < N_REL,"Requested column with index {:?} but the given witness is meant for {:?} relation columns", i, N_REL);
71                let res = &self.witness[i];
72                Some(res)
73            }
74            // Handling the "dynamic selector columns" at the end of the witness columns
75            Self::Column::DynamicSelector(i) => {
76                assert!(i < N_DSEL, "Requested dynamic selector with index {:?} but the given witness is meant for {:?} dynamic selector columns", i, N_DSEL);
77                let res = &self.witness[N_REL + i];
78                Some(res)
79            }
80            Self::Column::FixedSelector(i) => {
81                assert!(i < N_FSEL, "Requested fixed selector with index {:?} but the given witness is meant for {:?} fixed selector columns", i, N_FSEL);
82                let res = &self.fixed_selectors[i];
83                Some(res)
84            }
85            Self::Column::LookupPartialSum((table_id, i)) => {
86                if let Some(ref lookup) = self.lookup {
87                    let table_id = ID::from_u32(table_id);
88                    Some(&lookup.lookup_terms_evals_d8[&table_id][i])
89                } else {
90                    panic!("No lookup provided")
91                }
92            }
93            Self::Column::LookupAggregation => {
94                if let Some(ref lookup) = self.lookup {
95                    Some(lookup.lookup_aggregation_evals_d8)
96                } else {
97                    panic!("No lookup provided")
98                }
99            }
100            Self::Column::LookupMultiplicity((table_id, i)) => {
101                if let Some(ref lookup) = self.lookup {
102                    Some(&lookup.lookup_counters_evals_d8[&ID::from_u32(table_id)][i])
103                } else {
104                    panic!("No lookup provided")
105                }
106            }
107            Self::Column::LookupFixedTable(table_id) => {
108                if let Some(ref lookup) = self.lookup {
109                    Some(&lookup.fixed_tables_evals_d8[&ID::from_u32(table_id)])
110                } else {
111                    panic!("No lookup provided")
112                }
113            }
114        }
115    }
116
117    fn get_domain(&self, d: Domain) -> Radix2EvaluationDomain<F> {
118        match d {
119            Domain::D1 => self.domain.d1,
120            Domain::D2 => self.domain.d2,
121            Domain::D4 => self.domain.d4,
122            Domain::D8 => self.domain.d8,
123        }
124    }
125
126    fn column_domain(&self, col: &Self::Column) -> Domain {
127        match *col {
128            Self::Column::Relation(_)
129            | Self::Column::DynamicSelector(_)
130            | Self::Column::FixedSelector(_) => {
131                let domain_size = match *col {
132                    Self::Column::Relation(i) => self.witness[i].domain().size,
133                    Self::Column::DynamicSelector(i) => self.witness[N_REL + i].domain().size,
134                    Self::Column::FixedSelector(i) => self.fixed_selectors[i].domain().size,
135                    _ => panic!("Impossible"),
136                };
137                if self.domain.d1.size == domain_size {
138                    Domain::D1
139                } else if self.domain.d2.size == domain_size {
140                    Domain::D2
141                } else if self.domain.d4.size == domain_size {
142                    Domain::D4
143                } else if self.domain.d8.size == domain_size {
144                    Domain::D8
145                } else {
146                    panic!("Domain not supported. We do support the following multiple of the domain registered in the environment: 1, 2, 4, 8")
147                }
148            }
149            Self::Column::LookupAggregation
150            | Self::Column::LookupFixedTable(_)
151            | Self::Column::LookupMultiplicity(_)
152            | Self::Column::LookupPartialSum(_) => {
153                // When there is a lookup, we do suppose the domain is always D8
154                // and we have at leat 6 lookups per row.
155                Domain::D8
156            }
157        }
158    }
159
160    fn get_constants(&self) -> &Constants<F> {
161        &self.constants
162    }
163
164    fn get_challenges(&self) -> &BerkeleyChallenges<F> {
165        &self.challenges
166    }
167
168    fn vanishes_on_zero_knowledge_and_previous_rows(
169        &self,
170    ) -> &'a Evaluations<F, Radix2EvaluationDomain<F>> {
171        panic!("Not supposed to be used in MSM")
172    }
173
174    fn l0_1(&self) -> F {
175        self.l0_1
176    }
177}
kimchi_msm/column_env.rs

kimchi_msm/
column_env.rs
