kimchi/circuits/
argument.rs

1//! An argument is simply a number of constraints,
2//! which we want to enforce on all points of the domain.
3//! Both the permutation and the plookup arguments fit this type.
4//! Gates can be seen as filtered arguments,
5//! which apply only in some points (rows) of the domain.
6//! For more info, read book/src/kimchi/arguments.md
7
8use core::marker::PhantomData;
9
10use crate::{alphas::Alphas, circuits::expr::prologue::*};
11use ark_ff::{Field, PrimeField};
12use serde::{Deserialize, Serialize};
13
14//TODO use generic challenge
15use super::{
16    berkeley_columns::{BerkeleyChallengeTerm, BerkeleyChallenges},
17    expr::{constraints::ExprOps, Cache, ConstantExpr, ConstantTerm, Constants},
18    gate::{CurrOrNext, GateType},
19    polynomial::COLUMNS,
20};
21use CurrOrNext::{Curr, Next};
22
23/// A constraint type represents a polynomial that will be part of the final equation f (the circuit equation)
24#[derive(PartialEq, Eq, Clone, Copy, Hash, Debug, Serialize, Deserialize)]
25pub enum ArgumentType {
26    /// Gates in the PLONK constraint system.
27    /// As gates are mutually exclusive (a single gate is set per row),
28    /// we can reuse the same powers of alpha across gates.
29    Gate(GateType),
30    /// The permutation argument
31    Permutation,
32    /// The lookup argument
33    Lookup,
34}
35
36/// The argument environment is used to specify how the argument's constraints are
37/// represented when they are built.  If the environment is created without ArgumentData
38/// and with `F = Expr<F>`, then the constraints are built as Expr expressions (e.g. for
39/// use with the prover/verifier).  On the other hand, if the environment is
40/// created with ArgumentData and F = Field or F = PrimeField, then the constraints
41/// are built as expressions of real field elements and can be evaluated directly on
42/// the witness without using the prover.
43pub struct ArgumentEnv<F: 'static, T> {
44    data: Option<ArgumentData<F>>,
45    phantom_data: PhantomData<T>,
46}
47
48impl<F, T> Default for ArgumentEnv<F, T> {
49    /// Initialize the environment for creating Expr constraints for use with prover/verifier
50    fn default() -> Self {
51        ArgumentEnv {
52            data: None,
53            phantom_data: PhantomData,
54        }
55    }
56}
57
58impl<F: Field, T: ExprOps<F, BerkeleyChallengeTerm>> ArgumentEnv<F, T> {
59    /// Initialize the environment for creating constraints of real field elements that can be
60    /// evaluated directly over the witness without the prover/verifier
61    pub fn create(
62        witness: ArgumentWitness<F>,
63        coeffs: Vec<F>,
64        constants: Constants<F>,
65        challenges: BerkeleyChallenges<F>,
66    ) -> Self {
67        ArgumentEnv {
68            data: Some(ArgumentData {
69                witness,
70                coeffs,
71                constants,
72                challenges,
73            }),
74            phantom_data: PhantomData,
75        }
76    }
77
78    /// Witness cell (row, col)
79    pub fn witness(&self, row: CurrOrNext, col: usize) -> T {
80        T::witness(row, col, self.data.as_ref())
81    }
82
83    /// Witness cell on current row
84    pub fn witness_curr(&self, col: usize) -> T {
85        T::witness(Curr, col, self.data.as_ref())
86    }
87
88    /// Witness cell on next row
89    pub fn witness_next(&self, col: usize) -> T {
90        T::witness(Next, col, self.data.as_ref())
91    }
92
93    /// Witness cells in current row in an interval [from, to)
94    pub fn witness_curr_chunk(&self, from: usize, to: usize) -> Vec<T> {
95        let mut chunk = Vec::with_capacity(to - from);
96        for i in from..to {
97            chunk.push(self.witness_curr(i));
98        }
99        chunk
100    }
101
102    /// Witness cells in next row in an interval [from, to)
103    pub fn witness_next_chunk(&self, from: usize, to: usize) -> Vec<T> {
104        let mut chunk = Vec::with_capacity(to - from);
105        for i in from..to {
106            chunk.push(self.witness_next(i));
107        }
108        chunk
109    }
110
111    /// Coefficient value at index idx
112    pub fn coeff(&self, idx: usize) -> T {
113        T::coeff(idx, self.data.as_ref())
114    }
115
116    /// Chunk of consecutive coefficients in an interval [from, to)
117    pub fn coeff_chunk(&self, from: usize, to: usize) -> Vec<T> {
118        let mut chunk = Vec::with_capacity(to - from);
119        for i in from..to {
120            chunk.push(self.coeff(i));
121        }
122        chunk
123    }
124
125    /// Constant value (see [ConstantExpr] for supported constants)
126    pub fn constant(&self, expr: ConstantExpr<F, BerkeleyChallengeTerm>) -> T {
127        T::constant(expr, self.data.as_ref())
128    }
129
130    /// Helper to access endomorphism coefficient constant
131    pub fn endo_coefficient(&self) -> T {
132        T::constant(
133            ConstantExpr::from(ConstantTerm::EndoCoefficient),
134            self.data.as_ref(),
135        )
136    }
137
138    /// Helper to access maximum distance separable matrix constant at row, col
139    pub fn mds(&self, row: usize, col: usize) -> T {
140        T::constant(
141            ConstantExpr::from(ConstantTerm::Mds { row, col }),
142            self.data.as_ref(),
143        )
144    }
145}
146
147/// Argument environment data for constraints of field elements
148pub struct ArgumentData<F: 'static> {
149    /// Witness rows
150    pub witness: ArgumentWitness<F>,
151    /// Gate coefficients
152    pub coeffs: Vec<F>,
153    /// Constants
154    pub constants: Constants<F>,
155    pub challenges: BerkeleyChallenges<F>,
156}
157
158/// Witness data for an argument
159pub struct ArgumentWitness<T> {
160    /// Witness for current row
161    pub curr: [T; COLUMNS],
162    /// Witness for next row
163    pub next: [T; COLUMNS],
164}
165
166impl<T> core::ops::Index<(CurrOrNext, usize)> for ArgumentWitness<T> {
167    type Output = T;
168
169    fn index(&self, idx: (CurrOrNext, usize)) -> &T {
170        match idx.0 {
171            Curr => &self.curr[idx.1],
172            Next => &self.next[idx.1],
173        }
174    }
175}
176
177/// The interface for a minimal argument implementation.
178pub trait Argument<F: PrimeField> {
179    /// The type of constraints that this will produce.
180    /// This is important to enforce that we don't combine the constraints
181    /// with powers of alpha that collide with other mutually inclusive arguments.
182    const ARGUMENT_TYPE: ArgumentType;
183
184    /// The number of constraints created by the argument.
185    const CONSTRAINTS: u32;
186
187    /// Constraints for this argument
188    fn constraint_checks<T: ExprOps<F, BerkeleyChallengeTerm>>(
189        env: &ArgumentEnv<F, T>,
190        cache: &mut Cache,
191    ) -> Vec<T>;
192
193    /// Returns the set of constraints required to prove this argument.
194    fn constraints(cache: &mut Cache) -> Vec<E<F>> {
195        // Generate constraints
196        Self::constraint_checks(&ArgumentEnv::default(), cache)
197    }
198
199    /// Returns constraints safely combined via the passed combinator.
200    fn combined_constraints(alphas: &Alphas<F>, cache: &mut Cache) -> E<F> {
201        let constraints = Self::constraints(cache);
202        assert_eq!(constraints.len(), Self::CONSTRAINTS as usize);
203        let alphas = alphas.get_exponents(Self::ARGUMENT_TYPE, Self::CONSTRAINTS);
204        let combined_constraints = E::combine_constraints(alphas, constraints);
205
206        // An optional gate type, if used to define a gate.
207        // This is used to filter the gate, to avoid applying it on the entire domain.
208        if let ArgumentType::Gate(gate_type) = Self::ARGUMENT_TYPE {
209            index(gate_type) * combined_constraints
210        } else {
211            combined_constraints
212        }
213    }
214}
215
216pub trait DynArgument<F: PrimeField> {
217    fn constraints(&self, cache: &mut Cache) -> Vec<E<F>>;
218    fn combined_constraints(&self, alphas: &Alphas<F>, cache: &mut Cache) -> E<F>;
219    fn argument_type(&self) -> ArgumentType;
220}
221
222impl<F: PrimeField, T: Argument<F>> DynArgument<F> for T {
223    fn constraints(&self, cache: &mut Cache) -> Vec<E<F>> {
224        <Self as Argument<F>>::constraints(cache)
225    }
226    fn combined_constraints(&self, alphas: &Alphas<F>, cache: &mut Cache) -> E<F> {
227        <Self as Argument<F>>::combined_constraints(alphas, cache)
228    }
229    fn argument_type(&self) -> ArgumentType {
230        <Self as Argument<F>>::ARGUMENT_TYPE
231    }
232}
kimchi/circuits/argument.rs

kimchi/circuits/
argument.rs
