starky/
stark.rs

1//! Implementation of the [`Stark`] trait that defines the set of constraints
2//! related to a statement.
3
4#[cfg(not(feature = "std"))]
5use alloc::{vec, vec::Vec};
6
7use plonky2::field::extension::{Extendable, FieldExtension};
8use plonky2::field::packed::PackedField;
9use plonky2::field::types::Field;
10use plonky2::fri::structure::{
11    FriBatchInfo, FriBatchInfoTarget, FriInstanceInfo, FriInstanceInfoTarget, FriOracleInfo,
12    FriPolynomialInfo,
13};
14use plonky2::hash::hash_types::RichField;
15use plonky2::iop::ext_target::ExtensionTarget;
16use plonky2::iop::target::Target;
17use plonky2::plonk::circuit_builder::CircuitBuilder;
18
19use crate::config::StarkConfig;
20use crate::constraint_consumer::{ConstraintConsumer, RecursiveConstraintConsumer};
21use crate::evaluation_frame::StarkEvaluationFrame;
22use crate::lookup::Lookup;
23
24/// Represents a STARK system.
25pub trait Stark<F: RichField + Extendable<D>, const D: usize>: Sync {
26    /// The total number of columns in the trace.
27    const COLUMNS: usize = Self::EvaluationFrameTarget::COLUMNS;
28    /// The total number of public inputs.
29    const PUBLIC_INPUTS: usize = Self::EvaluationFrameTarget::PUBLIC_INPUTS;
30
31    /// This is used to evaluate constraints natively.
32    type EvaluationFrame<FE, P, const D2: usize>: StarkEvaluationFrame<P, FE>
33    where
34        FE: FieldExtension<D2, BaseField = F>,
35        P: PackedField<Scalar = FE>;
36
37    /// The `Target` version of `Self::EvaluationFrame`, used to evaluate constraints recursively.
38    type EvaluationFrameTarget: StarkEvaluationFrame<ExtensionTarget<D>, ExtensionTarget<D>>;
39
40    /// Evaluates constraints at a vector of points.
41    ///
42    /// The points are elements of a field `FE`, a degree `D2` extension of `F`. This lets us
43    /// evaluate constraints over a larger domain if desired. This can also be called with `FE = F`
44    /// and `D2 = 1`, in which case we are using the trivial extension, i.e. just evaluating
45    /// constraints over `F`.
46    fn eval_packed_generic<FE, P, const D2: usize>(
47        &self,
48        vars: &Self::EvaluationFrame<FE, P, D2>,
49        yield_constr: &mut ConstraintConsumer<P>,
50    ) where
51        FE: FieldExtension<D2, BaseField = F>,
52        P: PackedField<Scalar = FE>;
53
54    /// Evaluates constraints at a vector of points from the base field `F`.
55    fn eval_packed_base<P: PackedField<Scalar = F>>(
56        &self,
57        vars: &Self::EvaluationFrame<F, P, 1>,
58        yield_constr: &mut ConstraintConsumer<P>,
59    ) {
60        self.eval_packed_generic(vars, yield_constr)
61    }
62
63    /// Evaluates constraints at a single point from the degree `D` extension field.
64    fn eval_ext(
65        &self,
66        vars: &Self::EvaluationFrame<F::Extension, F::Extension, D>,
67        yield_constr: &mut ConstraintConsumer<F::Extension>,
68    ) {
69        self.eval_packed_generic(vars, yield_constr)
70    }
71
72    /// Evaluates constraints at a vector of points from the degree `D` extension field.
73    /// This is like `eval_ext`, except in the context of a recursive circuit.
74    /// Note: constraints must be added through`yield_constr.constraint(builder, constraint)`
75    /// in the same order as they are given in `eval_packed_generic`.
76    fn eval_ext_circuit(
77        &self,
78        builder: &mut CircuitBuilder<F, D>,
79        vars: &Self::EvaluationFrameTarget,
80        yield_constr: &mut RecursiveConstraintConsumer<F, D>,
81    );
82
83    /// Outputs the maximum constraint degree of this [`Stark`].
84    fn constraint_degree(&self) -> usize;
85
86    /// Outputs the maximum quotient polynomial's degree factor of this [`Stark`].
87    fn quotient_degree_factor(&self) -> usize {
88        match self.constraint_degree().checked_sub(1) {
89            Some(v) => 1.max(v),
90            None => 0,
91        }
92    }
93
94    /// Outputs the number of quotient polynomials this [`Stark`] would require with
95    /// the provided [`StarkConfig`]
96    fn num_quotient_polys(&self, config: &StarkConfig) -> usize {
97        self.quotient_degree_factor() * config.num_challenges
98    }
99
100    /// Computes the FRI instance used to prove this Stark.
101    fn fri_instance(
102        &self,
103        zeta: F::Extension,
104        g: F,
105        num_ctl_helpers: usize,
106        num_ctl_zs: Vec<usize>,
107        config: &StarkConfig,
108    ) -> FriInstanceInfo<F, D> {
109        let mut oracles = vec![];
110        let trace_info = FriPolynomialInfo::from_range(oracles.len(), 0..Self::COLUMNS);
111        oracles.push(FriOracleInfo {
112            num_polys: Self::COLUMNS,
113            blinding: false,
114        });
115
116        let num_lookup_columns = self.num_lookup_helper_columns(config);
117        let num_auxiliary_polys = num_lookup_columns + num_ctl_helpers + num_ctl_zs.len();
118        let auxiliary_polys_info = if self.uses_lookups() || self.requires_ctls() {
119            let aux_polys = FriPolynomialInfo::from_range(oracles.len(), 0..num_auxiliary_polys);
120            oracles.push(FriOracleInfo {
121                num_polys: num_auxiliary_polys,
122                blinding: false,
123            });
124            aux_polys
125        } else {
126            vec![]
127        };
128
129        let num_quotient_polys = self.num_quotient_polys(config);
130        let quotient_info = if num_quotient_polys > 0 {
131            let quotient_polys =
132                FriPolynomialInfo::from_range(oracles.len(), 0..num_quotient_polys);
133            oracles.push(FriOracleInfo {
134                num_polys: num_quotient_polys,
135                blinding: false,
136            });
137            quotient_polys
138        } else {
139            vec![]
140        };
141
142        let zeta_batch = FriBatchInfo {
143            point: zeta,
144            polynomials: [
145                trace_info.clone(),
146                auxiliary_polys_info.clone(),
147                quotient_info,
148            ]
149            .concat(),
150        };
151        let zeta_next_batch = FriBatchInfo {
152            point: zeta.scalar_mul(g),
153            polynomials: [trace_info, auxiliary_polys_info].concat(),
154        };
155
156        let mut batches = vec![zeta_batch, zeta_next_batch];
157
158        if self.requires_ctls() {
159            let ctl_zs_info = FriPolynomialInfo::from_range(
160                1, // auxiliary oracle index
161                num_lookup_columns + num_ctl_helpers..num_auxiliary_polys,
162            );
163            let ctl_first_batch = FriBatchInfo {
164                point: F::Extension::ONE,
165                polynomials: ctl_zs_info,
166            };
167
168            batches.push(ctl_first_batch);
169        }
170
171        FriInstanceInfo { oracles, batches }
172    }
173
174    /// Computes the FRI instance used to prove this Stark.
175    fn fri_instance_target(
176        &self,
177        builder: &mut CircuitBuilder<F, D>,
178        zeta: ExtensionTarget<D>,
179        g: Target,
180        num_ctl_helper_polys: usize,
181        num_ctl_zs: usize,
182        config: &StarkConfig,
183    ) -> FriInstanceInfoTarget<D> {
184        let mut oracles = vec![];
185        let trace_info = FriPolynomialInfo::from_range(oracles.len(), 0..Self::COLUMNS);
186        oracles.push(FriOracleInfo {
187            num_polys: Self::COLUMNS,
188            blinding: false,
189        });
190
191        let num_lookup_columns = self.num_lookup_helper_columns(config);
192        let num_auxiliary_polys = num_lookup_columns + num_ctl_helper_polys + num_ctl_zs;
193        let auxiliary_polys_info = if self.uses_lookups() || self.requires_ctls() {
194            let aux_polys = FriPolynomialInfo::from_range(oracles.len(), 0..num_auxiliary_polys);
195            oracles.push(FriOracleInfo {
196                num_polys: num_auxiliary_polys,
197                blinding: false,
198            });
199            aux_polys
200        } else {
201            vec![]
202        };
203
204        let num_quotient_polys = self.num_quotient_polys(config);
205        let quotient_info = if num_quotient_polys > 0 {
206            let quotient_polys =
207                FriPolynomialInfo::from_range(oracles.len(), 0..num_quotient_polys);
208            oracles.push(FriOracleInfo {
209                num_polys: num_quotient_polys,
210                blinding: false,
211            });
212            quotient_polys
213        } else {
214            vec![]
215        };
216
217        let zeta_batch = FriBatchInfoTarget {
218            point: zeta,
219            polynomials: [
220                trace_info.clone(),
221                auxiliary_polys_info.clone(),
222                quotient_info,
223            ]
224            .concat(),
225        };
226        let g_ext = builder.convert_to_ext(g);
227        let zeta_next = builder.mul_extension(g_ext, zeta);
228        let zeta_next_batch = FriBatchInfoTarget {
229            point: zeta_next,
230            polynomials: [trace_info, auxiliary_polys_info].concat(),
231        };
232
233        let mut batches = vec![zeta_batch, zeta_next_batch];
234
235        if self.requires_ctls() {
236            let ctl_zs_info = FriPolynomialInfo::from_range(
237                1, // auxiliary oracle index
238                num_lookup_columns + num_ctl_helper_polys..num_auxiliary_polys,
239            );
240            let ctl_first_batch = FriBatchInfoTarget {
241                point: builder.one_extension(),
242                polynomials: ctl_zs_info,
243            };
244
245            batches.push(ctl_first_batch);
246        }
247
248        FriInstanceInfoTarget { oracles, batches }
249    }
250
251    /// Outputs all the [`Lookup`] this STARK table needs to perform across its columns.
252    fn lookups(&self) -> Vec<Lookup<F>> {
253        vec![]
254    }
255
256    /// Outputs the number of total lookup helper columns, based on this STARK's vector
257    /// of [`Lookup`] and the number of challenges used by this [`StarkConfig`].
258    fn num_lookup_helper_columns(&self, config: &StarkConfig) -> usize {
259        self.lookups()
260            .iter()
261            .map(|lookup| lookup.num_helper_columns(self.constraint_degree()))
262            .sum::<usize>()
263            * config.num_challenges
264    }
265
266    /// Indicates whether this STARK uses lookups over some of its columns, and as such requires
267    /// additional steps during proof generation to handle auxiliary polynomials.
268    fn uses_lookups(&self) -> bool {
269        !self.lookups().is_empty()
270    }
271
272    /// Indicates whether this STARK belongs to a multi-STARK system, and as such may require
273    /// cross-table lookups to connect shared values across different traces.
274    ///
275    /// It defaults to `false`, i.e. for simple uni-STARK systems.
276    fn requires_ctls(&self) -> bool {
277        false
278    }
279}
starky/stark.rs

starky/
stark.rs
