openvm_stark_backend/verifier/
folder.rs

1use std::{
2    marker::PhantomData,
3    ops::{AddAssign, MulAssign},
4};
5
6use p3_field::{ExtensionField, Field, PrimeCharacteristicRing};
7use p3_matrix::Matrix;
8
9use crate::{
10    air_builders::{
11        symbolic::{
12            symbolic_expression::SymbolicEvaluator,
13            symbolic_variable::{Entry, SymbolicVariable},
14            SymbolicExpressionDag,
15        },
16        ViewPair,
17    },
18    config::{StarkGenericConfig, Val},
19};
20
21pub type VerifierConstraintFolder<'a, SC> = GenericVerifierConstraintFolder<
22    'a,
23    Val<SC>,
24    <SC as StarkGenericConfig>::Challenge,
25    Val<SC>,
26    <SC as StarkGenericConfig>::Challenge,
27    <SC as StarkGenericConfig>::Challenge,
28>;
29// Struct definition copied from sp1 under MIT license.
30/// A folder for verifier constraints with generic types.
31///
32/// `Var` is still a challenge type because this is a verifier.
33pub struct GenericVerifierConstraintFolder<'a, F, EF, PubVar, Var, Expr> {
34    pub preprocessed: ViewPair<'a, Var>,
35    pub partitioned_main: Vec<ViewPair<'a, Var>>,
36    pub after_challenge: Vec<ViewPair<'a, Var>>,
37    pub challenges: &'a [Vec<Var>],
38    pub is_first_row: Var,
39    pub is_last_row: Var,
40    pub is_transition: Var,
41    pub alpha: Var,
42    pub accumulator: Expr,
43    pub public_values: &'a [PubVar],
44    pub exposed_values_after_challenge: &'a [Vec<Var>],
45    pub _marker: PhantomData<(F, EF)>,
46}
47
48impl<F, EF, PubVar, Var, Expr> GenericVerifierConstraintFolder<'_, F, EF, PubVar, Var, Expr>
49where
50    F: Field,
51    EF: ExtensionField<F>,
52    Expr: PrimeCharacteristicRing + From<F> + MulAssign<Var> + AddAssign<Var> + Send + Sync,
53    Var: Into<Expr> + Copy + Send + Sync,
54    PubVar: Into<Expr> + Copy + Send + Sync,
55{
56    pub fn eval_constraints(&mut self, constraints: &SymbolicExpressionDag<F>) {
57        let dag = constraints;
58        // node_idx -> evaluation
59        // We do a simple serial evaluation in topological order.
60        // This can be parallelized if necessary.
61        let exprs = self.eval_nodes(&dag.nodes);
62        for &idx in &dag.constraint_idx {
63            self.assert_zero(exprs[idx].clone());
64        }
65    }
66
67    pub fn assert_zero(&mut self, x: impl Into<Expr>) {
68        let x = x.into();
69        self.accumulator *= self.alpha;
70        self.accumulator += x;
71    }
72}
73
74impl<F, EF, PubVar, Var, Expr> SymbolicEvaluator<F, Expr>
75    for GenericVerifierConstraintFolder<'_, F, EF, PubVar, Var, Expr>
76where
77    F: Field,
78    EF: ExtensionField<F>,
79    Expr: PrimeCharacteristicRing + From<F> + Send + Sync,
80    Var: Into<Expr> + Copy + Send + Sync,
81    PubVar: Into<Expr> + Copy + Send + Sync,
82{
83    fn eval_const(&self, c: F) -> Expr {
84        c.into()
85    }
86    fn eval_is_first_row(&self) -> Expr {
87        self.is_first_row.into()
88    }
89    fn eval_is_last_row(&self) -> Expr {
90        self.is_last_row.into()
91    }
92    fn eval_is_transition(&self) -> Expr {
93        self.is_transition.into()
94    }
95    fn eval_var(&self, symbolic_var: SymbolicVariable<F>) -> Expr {
96        let index = symbolic_var.index;
97        match symbolic_var.entry {
98            Entry::Preprocessed { offset } => self
99                .preprocessed
100                .get(offset, index)
101                .expect("matrix index out of bounds")
102                .into(),
103            Entry::Main { part_index, offset } => self.partitioned_main[part_index]
104                .get(offset, index)
105                .expect("matrix index out of bounds")
106                .into(),
107            Entry::Public => self.public_values[index].into(),
108            Entry::Permutation { offset } => self
109                .after_challenge
110                .first()
111                .expect("Challenge phase not supported")
112                .get(offset, index)
113                .expect("matrix index out of bounds")
114                .into(),
115            Entry::Challenge => self
116                .challenges
117                .first()
118                .expect("Challenge phase not supported")[index]
119                .into(),
120            Entry::Exposed => self
121                .exposed_values_after_challenge
122                .first()
123                .expect("Challenge phase not supported")[index]
124                .into(),
125        }
126    }
127    // NOTE: do not use the eval_expr function as it can have exponential complexity!
128    // Instead use `eval_nodes`
129}
openvm_stark_backend/verifier/folder.rs

openvm_stark_backend/verifier/
folder.rs
