kimchi/circuits/
berkeley_columns.rs

1//! This module defines the particular form of the expressions used in the Mina
2//! Berkeley hardfork. You can find more information in [this blog
3//! article](https://www.o1labs.org/blog/reintroducing-kimchi).
4//! This module is also a good starting point if you want to implement your own
5//! variant of Kimchi using the expression framework.
6//!
7//! The module uses the generic expression framework defined in the
8//! [crate::circuits::expr] module.
9//! The expressions define the polynomials that can be used to describe the
10//! constraints.
11//! It starts by defining the different challenges used by the PLONK IOP in
12//! [BerkeleyChallengeTerm] and [BerkeleyChallenges].
13//! It then defines the [Column] type which represents the different variables
14//! the polynomials are defined over.
15//!
16//! Two "environments" are after that defined: one for the lookup argument
17//! [LookupEnvironment], and one for the main argument [Environment], which
18//! contains the former.
19//! The trait [ColumnEnvironment] is then defined to provide the necessary
20//! primitives used to evaluate the quotient polynomial.
21use alloc::{
22    format,
23    string::{String, ToString},
24    vec::Vec,
25};
26
27use crate::{
28    circuits::{
29        domains::{Domain, EvaluationDomains},
30        expr::{
31            CacheId, ColumnEnvironment, ColumnEvaluations, ConstantExpr, ConstantTerm, Constants,
32            Expr, ExprError, FormattedOutput,
33        },
34        gate::{CurrOrNext, GateType},
35        lookup::{index::LookupSelectors, lookups::LookupPattern},
36        wires::COLUMNS,
37    },
38    collections::HashMap,
39    proof::{PointEvaluations, ProofEvaluations},
40};
41use ark_ff::FftField;
42use ark_poly::{Evaluations, Radix2EvaluationDomain as D};
43use serde::{Deserialize, Serialize};
44
45/// The challenge terms used in Berkeley.
46#[derive(Copy, Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
47pub enum BerkeleyChallengeTerm {
48    /// Used to combine constraints
49    Alpha,
50    /// The first challenge used in the permutation argument
51    Beta,
52    /// The second challenge used in the permutation argument
53    Gamma,
54    /// A challenge used to columns of a lookup table
55    JointCombiner,
56}
57
58impl core::fmt::Display for BerkeleyChallengeTerm {
59    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
60        use BerkeleyChallengeTerm::*;
61        let str = match self {
62            Alpha => "alpha".to_string(),
63            Beta => "beta".to_string(),
64            Gamma => "gamma".to_string(),
65            JointCombiner => "joint_combiner".to_string(),
66        };
67        write!(f, "{}", str)
68    }
69}
70
71impl<'a> super::expr::AlphaChallengeTerm<'a> for BerkeleyChallengeTerm {
72    const ALPHA: Self = Self::Alpha;
73}
74
75pub struct BerkeleyChallenges<F> {
76    /// The challenge α from the PLONK IOP.
77    pub alpha: F,
78    /// The challenge β from the PLONK IOP.
79    pub beta: F,
80    /// The challenge γ from the PLONK IOP.
81    pub gamma: F,
82    /// The challenge joint_combiner which is used to combine joint lookup
83    /// tables.
84    pub joint_combiner: F,
85}
86
87impl<F: ark_ff::Field> core::ops::Index<BerkeleyChallengeTerm> for BerkeleyChallenges<F> {
88    type Output = F;
89
90    fn index(&self, challenge_term: BerkeleyChallengeTerm) -> &Self::Output {
91        match challenge_term {
92            BerkeleyChallengeTerm::Alpha => &self.alpha,
93            BerkeleyChallengeTerm::Beta => &self.beta,
94            BerkeleyChallengeTerm::Gamma => &self.gamma,
95            BerkeleyChallengeTerm::JointCombiner => &self.joint_combiner,
96        }
97    }
98}
99
100/// A type representing the variables involved in the constraints of the
101/// Berkeley hardfork.
102///
103/// In Berkeley, the constraints are defined over the following variables:
104/// - The [COLUMNS] witness columns.
105/// - The permutation polynomial, Z.
106/// - The public coefficients, `Coefficients`, which can be used for public
107///   values. For instance, it is used for the Poseidon round constants.
108/// - ...
109#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord, Serialize, Deserialize)]
110pub enum Column {
111    Witness(usize),
112    Z,
113    LookupSorted(usize),
114    LookupAggreg,
115    LookupTable,
116    LookupKindIndex(LookupPattern),
117    LookupRuntimeSelector,
118    LookupRuntimeTable,
119    Index(GateType),
120    Coefficient(usize),
121    Permutation(usize),
122}
123
124impl FormattedOutput for Column {
125    fn is_alpha(&self) -> bool {
126        // FIXME. Unused at the moment
127        unimplemented!()
128    }
129
130    fn ocaml(&self, _cache: &mut HashMap<CacheId, Self>) -> String {
131        // FIXME. Unused at the moment
132        unimplemented!()
133    }
134
135    fn latex(&self, _cache: &mut HashMap<CacheId, Self>) -> String {
136        match self {
137            Column::Witness(i) => format!("w_{{{i}}}"),
138            Column::Z => "Z".to_string(),
139            Column::LookupSorted(i) => format!("s_{{{i}}}"),
140            Column::LookupAggreg => "a".to_string(),
141            Column::LookupTable => "t".to_string(),
142            Column::LookupKindIndex(i) => format!("k_{{{i:?}}}"),
143            Column::LookupRuntimeSelector => "rts".to_string(),
144            Column::LookupRuntimeTable => "rt".to_string(),
145            Column::Index(gate) => {
146                format!("{gate:?}")
147            }
148            Column::Coefficient(i) => format!("c_{{{i}}}"),
149            Column::Permutation(i) => format!("sigma_{{{i}}}"),
150        }
151    }
152
153    fn text(&self, _cache: &mut HashMap<CacheId, Self>) -> String {
154        match self {
155            Column::Witness(i) => format!("w[{i}]"),
156            Column::Z => "Z".to_string(),
157            Column::LookupSorted(i) => format!("s[{i}]"),
158            Column::LookupAggreg => "a".to_string(),
159            Column::LookupTable => "t".to_string(),
160            Column::LookupKindIndex(i) => format!("k[{i:?}]"),
161            Column::LookupRuntimeSelector => "rts".to_string(),
162            Column::LookupRuntimeTable => "rt".to_string(),
163            Column::Index(gate) => {
164                format!("{gate:?}")
165            }
166            Column::Coefficient(i) => format!("c[{i}]"),
167            Column::Permutation(i) => format!("sigma_[{i}]"),
168        }
169    }
170}
171
172impl<F: Copy> ColumnEvaluations<F> for ProofEvaluations<PointEvaluations<F>> {
173    type Column = Column;
174    fn evaluate(&self, col: Self::Column) -> Result<PointEvaluations<F>, ExprError<Self::Column>> {
175        use Column::*;
176        match col {
177            Witness(i) => Ok(self.w[i]),
178            Z => Ok(self.z),
179            LookupSorted(i) => self.lookup_sorted[i].ok_or(ExprError::MissingIndexEvaluation(col)),
180            LookupAggreg => self
181                .lookup_aggregation
182                .ok_or(ExprError::MissingIndexEvaluation(col)),
183            LookupTable => self
184                .lookup_table
185                .ok_or(ExprError::MissingIndexEvaluation(col)),
186            LookupRuntimeTable => self
187                .runtime_lookup_table
188                .ok_or(ExprError::MissingIndexEvaluation(col)),
189            Index(GateType::Poseidon) => Ok(self.poseidon_selector),
190            Index(GateType::Generic) => Ok(self.generic_selector),
191            Index(GateType::CompleteAdd) => Ok(self.complete_add_selector),
192            Index(GateType::VarBaseMul) => Ok(self.mul_selector),
193            Index(GateType::EndoMul) => Ok(self.emul_selector),
194            Index(GateType::EndoMulScalar) => Ok(self.endomul_scalar_selector),
195            Index(GateType::RangeCheck0) => self
196                .range_check0_selector
197                .ok_or(ExprError::MissingIndexEvaluation(col)),
198            Index(GateType::RangeCheck1) => self
199                .range_check1_selector
200                .ok_or(ExprError::MissingIndexEvaluation(col)),
201            Index(GateType::ForeignFieldAdd) => self
202                .foreign_field_add_selector
203                .ok_or(ExprError::MissingIndexEvaluation(col)),
204            Index(GateType::ForeignFieldMul) => self
205                .foreign_field_mul_selector
206                .ok_or(ExprError::MissingIndexEvaluation(col)),
207            Index(GateType::Xor16) => self
208                .xor_selector
209                .ok_or(ExprError::MissingIndexEvaluation(col)),
210            Index(GateType::Rot64) => self
211                .rot_selector
212                .ok_or(ExprError::MissingIndexEvaluation(col)),
213            Permutation(i) => Ok(self.s[i]),
214            Coefficient(i) => Ok(self.coefficients[i]),
215            LookupKindIndex(LookupPattern::Xor) => self
216                .xor_lookup_selector
217                .ok_or(ExprError::MissingIndexEvaluation(col)),
218            LookupKindIndex(LookupPattern::Lookup) => self
219                .lookup_gate_lookup_selector
220                .ok_or(ExprError::MissingIndexEvaluation(col)),
221            LookupKindIndex(LookupPattern::RangeCheck) => self
222                .range_check_lookup_selector
223                .ok_or(ExprError::MissingIndexEvaluation(col)),
224            LookupKindIndex(LookupPattern::ForeignFieldMul) => self
225                .foreign_field_mul_lookup_selector
226                .ok_or(ExprError::MissingIndexEvaluation(col)),
227            LookupRuntimeSelector => self
228                .runtime_lookup_table_selector
229                .ok_or(ExprError::MissingIndexEvaluation(col)),
230            Index(_) => Err(ExprError::MissingIndexEvaluation(col)),
231        }
232    }
233}
234
235impl<'a, F: FftField> ColumnEnvironment<'a, F, BerkeleyChallengeTerm, BerkeleyChallenges<F>>
236    for Environment<'a, F>
237{
238    type Column = Column;
239
240    fn get_column(&self, col: &Self::Column) -> Option<&'a Evaluations<F, D<F>>> {
241        use Column::*;
242        let lookup = self.lookup.as_ref();
243        match col {
244            Witness(i) => Some(&self.witness[*i]),
245            Coefficient(i) => Some(&self.coefficient[*i]),
246            Z => Some(self.z),
247            LookupKindIndex(i) => lookup.and_then(|l| l.selectors[*i].as_ref()),
248            LookupSorted(i) => lookup.map(|l| &l.sorted[*i]),
249            LookupAggreg => lookup.map(|l| l.aggreg),
250            LookupTable => lookup.map(|l| l.table),
251            LookupRuntimeSelector => lookup.and_then(|l| l.runtime_selector),
252            LookupRuntimeTable => lookup.and_then(|l| l.runtime_table),
253            Index(t) => match self.index.get(t) {
254                None => None,
255                Some(e) => Some(e),
256            },
257            Permutation(_) => None,
258        }
259    }
260
261    fn get_domain(&self, d: Domain) -> D<F> {
262        match d {
263            Domain::D1 => self.domain.d1,
264            Domain::D2 => self.domain.d2,
265            Domain::D4 => self.domain.d4,
266            Domain::D8 => self.domain.d8,
267        }
268    }
269
270    fn column_domain(&self, col: &Self::Column) -> Domain {
271        match *col {
272            Self::Column::Index(GateType::Generic) => Domain::D4,
273            Self::Column::Index(GateType::CompleteAdd) => Domain::D4,
274            _ => Domain::D8,
275        }
276    }
277
278    fn get_constants(&self) -> &Constants<F> {
279        &self.constants
280    }
281
282    fn get_challenges(&self) -> &BerkeleyChallenges<F> {
283        &self.challenges
284    }
285
286    fn vanishes_on_zero_knowledge_and_previous_rows(&self) -> &'a Evaluations<F, D<F>> {
287        self.vanishes_on_zero_knowledge_and_previous_rows
288    }
289
290    fn l0_1(&self) -> F {
291        self.l0_1
292    }
293}
294
295/// The polynomials specific to the lookup argument.
296///
297/// All are evaluations over the D8 domain
298pub struct LookupEnvironment<'a, F: FftField> {
299    /// The sorted lookup table polynomials.
300    pub sorted: &'a Vec<Evaluations<F, D<F>>>,
301    /// The lookup aggregation polynomials.
302    pub aggreg: &'a Evaluations<F, D<F>>,
303    /// The lookup-type selector polynomials.
304    pub selectors: &'a LookupSelectors<Evaluations<F, D<F>>>,
305    /// The evaluations of the combined lookup table polynomial.
306    pub table: &'a Evaluations<F, D<F>>,
307    /// The evaluations of the optional runtime selector polynomial.
308    pub runtime_selector: Option<&'a Evaluations<F, D<F>>>,
309    /// The evaluations of the optional runtime table.
310    pub runtime_table: Option<&'a Evaluations<F, D<F>>>,
311}
312
313/// The collection of polynomials (all in evaluation form) and constants
314/// required to evaluate an expression as a polynomial.
315///
316/// All are evaluations.
317pub struct Environment<'a, F: FftField> {
318    /// The witness column polynomials
319    pub witness: &'a [Evaluations<F, D<F>>; COLUMNS],
320    /// The coefficient column polynomials
321    pub coefficient: &'a [Evaluations<F, D<F>>; COLUMNS],
322    /// The polynomial that vanishes on the zero-knowledge rows and the row before.
323    pub vanishes_on_zero_knowledge_and_previous_rows: &'a Evaluations<F, D<F>>,
324    /// The permutation aggregation polynomial.
325    pub z: &'a Evaluations<F, D<F>>,
326    /// The index selector polynomials.
327    pub index: HashMap<GateType, &'a Evaluations<F, D<F>>>,
328    /// The value `prod_{j != 1} (1 - omega^j)`, used for efficiently
329    /// computing the evaluations of the unnormalized Lagrange basis polynomials.
330    pub l0_1: F,
331    /// Constant values required
332    pub constants: Constants<F>,
333    /// Challenges from the IOP.
334    pub challenges: BerkeleyChallenges<F>,
335    /// The domains used in the PLONK argument.
336    pub domain: EvaluationDomains<F>,
337    /// Lookup specific polynomials
338    pub lookup: Option<LookupEnvironment<'a, F>>,
339}
340
341//
342// Helpers
343//
344
345/// An alias for the intended usage of the expression type in constructing constraints.
346pub type E<F> = Expr<ConstantExpr<F, BerkeleyChallengeTerm>, Column>;
347
348/// Convenience function to create a constant as [Expr].
349pub fn constant<F>(x: F) -> E<F> {
350    ConstantTerm::Literal(x).into()
351}
352
353/// Helper function to quickly create an expression for a witness.
354pub fn witness<F>(i: usize, row: CurrOrNext) -> E<F> {
355    E::<F>::cell(Column::Witness(i), row)
356}
357
358/// Same as [witness] but for the current row.
359pub fn witness_curr<F>(i: usize) -> E<F> {
360    witness(i, CurrOrNext::Curr)
361}
362
363/// Same as [witness] but for the next row.
364pub fn witness_next<F>(i: usize) -> E<F> {
365    witness(i, CurrOrNext::Next)
366}
367
368/// Handy function to quickly create an expression for a gate.
369pub fn index<F>(g: GateType) -> E<F> {
370    E::<F>::cell(Column::Index(g), CurrOrNext::Curr)
371}
372
373pub fn coeff<F>(i: usize) -> E<F> {
374    E::<F>::cell(Column::Coefficient(i), CurrOrNext::Curr)
375}
kimchi/circuits/berkeley_columns.rs

kimchi/circuits/
berkeley_columns.rs
