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

kimchi/circuits/
argument.rs
