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

kimchi/circuits/
berkeley_columns.rs
