openvm_stark_backend/verifier/
evaluator.rs

1use p3_field::{ExtensionField, Field, PrimeCharacteristicRing, TwoAdicField};
2
3use crate::air_builders::symbolic::{
4    symbolic_expression::SymbolicEvaluator,
5    symbolic_variable::{Entry, SymbolicVariable},
6};
7
8type ViewPair<'a, T> = &'a [(T, T)];
9
10/// Returns the sum `1 + m + ... + m^{2^l - 1}`.
11/// Could be done with `if m == 1 { ... } else { num / denom }`,
12/// but I don't like divisions of field extension elements.
13fn progression_exp_2<EF>(m: EF, l: usize) -> EF
14where
15    EF: PrimeCharacteristicRing + Copy,
16{
17    (0..l)
18        .fold((m, EF::ONE), |(pow, sum), _| {
19            (pow * pow, sum * (EF::ONE + pow))
20        })
21        .1
22}
23
24pub(super) struct VerifierConstraintEvaluator<'a, F, EF> {
25    pub preprocessed: Option<ViewPair<'a, EF>>,
26    pub partitioned_main: &'a [ViewPair<'a, EF>],
27    pub is_first_row: EF,
28    pub is_last_row: EF,
29    pub public_values: &'a [F],
30}
31
32impl<'a, F, EF> VerifierConstraintEvaluator<'a, F, EF>
33where
34    F: Field + TwoAdicField,
35    EF: ExtensionField<F>,
36{
37    pub(super) fn new(
38        preprocessed: Option<ViewPair<'a, EF>>,
39        partitioned_main: &'a [ViewPair<'a, EF>],
40        public_values: &'a [F],
41        rs: &'a [EF],
42        l_skip: usize,
43    ) -> Self {
44        let omega = F::two_adic_generator(l_skip);
45        let inv = EF::from(F::from_usize(1 << l_skip).inverse());
46        let is_first_row = inv
47            * progression_exp_2(rs[0], l_skip)
48            * rs[1..].iter().fold(EF::ONE, |acc, &x| acc * (EF::ONE - x));
49        let is_last_row = inv
50            * progression_exp_2(rs[0] * omega, l_skip)
51            * rs[1..].iter().fold(EF::ONE, |acc, &x| acc * x);
52        Self {
53            preprocessed,
54            partitioned_main,
55            is_first_row,
56            is_last_row,
57            public_values,
58        }
59    }
60}
61
62impl<F, EF> SymbolicEvaluator<F, EF> for VerifierConstraintEvaluator<'_, F, EF>
63where
64    F: Field,
65    EF: ExtensionField<F>,
66{
67    fn eval_const(&self, c: F) -> EF {
68        EF::from(c)
69    }
70
71    fn eval_var(&self, symbolic_var: SymbolicVariable<F>) -> EF {
72        let index = symbolic_var.index;
73        match symbolic_var.entry {
74            Entry::Preprocessed { offset } => match &self.preprocessed {
75                Some(vp) => {
76                    if offset == 0 {
77                        vp[index].0
78                    } else {
79                        vp[index].1
80                    }
81                }
82                None => panic!(),
83            },
84            Entry::Main { part_index, offset } => {
85                let vp = &self.partitioned_main[part_index];
86                if offset == 0 {
87                    vp[index].0
88                } else {
89                    vp[index].1
90                }
91            }
92            Entry::Public => EF::from(self.public_values[index]),
93            _ => unimplemented!(),
94        }
95    }
96
97    fn eval_is_first_row(&self) -> EF {
98        self.is_first_row
99    }
100
101    fn eval_is_last_row(&self) -> EF {
102        self.is_last_row
103    }
104
105    fn eval_is_transition(&self) -> EF {
106        EF::ONE - self.is_last_row
107    }
108}
openvm_stark_backend/verifier/evaluator.rs

openvm_stark_backend/verifier/
evaluator.rs
