openvm_stark_backend/verifier/
folder.rs

Help
1use std::{
2    marker::PhantomData,
3    ops::{AddAssign, MulAssign},
4};
5
6use p3_field::{ExtensionField, Field, FieldAlgebra};
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: FieldAlgebra + 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: FieldAlgebra + 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.preprocessed.get(offset, index).into(),
99            Entry::Main { part_index, offset } => {
100                self.partitioned_main[part_index].get(offset, index).into()
101            }
102            Entry::Public => self.public_values[index].into(),
103            Entry::Permutation { offset } => self
104                .after_challenge
105                .first()
106                .expect("Challenge phase not supported")
107                .get(offset, index)
108                .into(),
109            Entry::Challenge => self
110                .challenges
111                .first()
112                .expect("Challenge phase not supported")[index]
113                .into(),
114            Entry::Exposed => self
115                .exposed_values_after_challenge
116                .first()
117                .expect("Challenge phase not supported")[index]
118                .into(),
119        }
120    }
121    // NOTE: do not use the eval_expr function as it can have exponential complexity!
122    // Instead use `eval_nodes`
123}
openvm_stark_backend/verifier/folder.rs

openvm_stark_backend/verifier/
folder.rs
