folding/
error_term.rs

1//! This module contains the functions used to compute the error terms, as
2//! described in the [top-level documentation of the expressions
3//! module](crate::expressions).
4
5use crate::{
6    columns::ExtendedFoldingColumn,
7    decomposable_folding::check_selector,
8    eval_leaf::EvalLeaf,
9    expressions::{Degree, FoldingExp, IntegratedFoldingExpr, Sign},
10    quadraticization::ExtendedWitnessGenerator,
11    FoldingConfig, FoldingEnv, Instance, RelaxedInstance, RelaxedWitness, ScalarField,
12};
13use ark_ff::{Field, One, Zero};
14use ark_poly::{Evaluations, Radix2EvaluationDomain};
15use kimchi::circuits::expr::Variable;
16use poly_commitment::{PolyComm, SRS};
17
18// FIXME: for optimisation, as values are not necessarily Fp elements and are
19// relatively small, we could get rid of the scalar field objects, and only use
20// bigint where we only apply the modulus when needed.
21
22/// This type refers to the two instances to be folded
23#[derive(Clone, Copy)]
24pub enum Side {
25    Left = 0,
26    Right = 1,
27}
28
29impl Side {
30    pub fn other(self) -> Self {
31        match self {
32            Side::Left => Side::Right,
33            Side::Right => Side::Left,
34        }
35    }
36}
37
38/// Evaluates the expression in the provided side
39pub(crate) fn eval_sided<'a, C: FoldingConfig>(
40    exp: &FoldingExp<C>,
41    env: &'a ExtendedEnv<C>,
42    side: Side,
43) -> EvalLeaf<'a, ScalarField<C>> {
44    use FoldingExp::*;
45
46    match exp {
47        Atom(col) => env.col(col, side),
48        Double(e) => {
49            let col = eval_sided(e, env, side);
50            col.map(Field::double, |f| {
51                Field::double_in_place(f);
52            })
53        }
54        Square(e) => {
55            let col = eval_sided(e, env, side);
56            col.map(Field::square, |f| {
57                Field::square_in_place(f);
58            })
59        }
60        Add(e1, e2) => eval_sided(e1, env, side) + eval_sided(e2, env, side),
61        Sub(e1, e2) => eval_sided(e1, env, side) - eval_sided(e2, env, side),
62        Mul(e1, e2) => {
63            //this assumes to some degree that selectors don't multiply each other
64            let selector = check_selector(e1)
65                .or(check_selector(e2))
66                .zip(env.enabled_selector())
67                .map(|(s1, s2)| s1 == s2);
68            match selector {
69                Some(false) => {
70                    let zero_vec = vec![ScalarField::<C>::zero(); env.domain.size as usize];
71                    EvalLeaf::Result(zero_vec)
72                }
73                Some(true) | None => {
74                    let d1 = e1.folding_degree();
75                    let d2 = e2.folding_degree();
76                    let e1 = match d1 {
77                        Degree::Two => eval_sided(e1, env, side),
78                        _ => eval_exp_error(e1, env, side),
79                    };
80                    let e2 = match d2 {
81                        Degree::Two => eval_sided(e2, env, side),
82                        _ => eval_exp_error(e2, env, side),
83                    };
84                    e1 * e2
85                }
86            }
87        }
88        Pow(e, i) => match i {
89            0 => EvalLeaf::Const(ScalarField::<C>::one()),
90            1 => eval_sided(e, env, side),
91            i => {
92                let err = eval_sided(e, env, side);
93                let mut acc = err.clone();
94                for _ in 1..*i {
95                    acc = acc * err.clone()
96                }
97                acc
98            }
99        },
100    }
101}
102
103pub(crate) fn eval_exp_error<'a, C: FoldingConfig>(
104    exp: &FoldingExp<C>,
105    env: &'a ExtendedEnv<C>,
106    side: Side,
107) -> EvalLeaf<'a, ScalarField<C>> {
108    use FoldingExp::*;
109
110    match exp {
111        Atom(col) => env.col(col, side),
112        Double(e) => {
113            let col = eval_exp_error(e, env, side);
114            col.map(Field::double, |f| {
115                Field::double_in_place(f);
116            })
117        }
118        Square(e) => match exp.folding_degree() {
119            Degree::Two => {
120                let cross = eval_exp_error(e, env, side) * eval_exp_error(e, env, side.other());
121                cross.map(Field::double, |f| {
122                    Field::double_in_place(f);
123                })
124            }
125            _ => {
126                let e = eval_exp_error(e, env, side);
127                e.map(Field::square, |f| {
128                    Field::square_in_place(f);
129                })
130            }
131        },
132        Add(e1, e2) => eval_exp_error(e1, env, side) + eval_exp_error(e2, env, side),
133        Sub(e1, e2) => eval_exp_error(e1, env, side) - eval_exp_error(e2, env, side),
134        Mul(e1, e2) => {
135            //this assumes to some degree that selectors don't multiply each other
136            let selector = check_selector(e1)
137                .or(check_selector(e2))
138                .zip(env.enabled_selector())
139                .map(|(s1, s2)| s1 == s2);
140            match selector {
141                Some(false) => {
142                    let zero_vec = vec![ScalarField::<C>::zero(); env.domain.size as usize];
143                    EvalLeaf::Result(zero_vec)
144                }
145                Some(true) | None => match (exp.folding_degree(), e1.folding_degree()) {
146                    (Degree::Two, Degree::One) => {
147                        let first =
148                            eval_exp_error(e1, env, side) * eval_exp_error(e2, env, side.other());
149                        let second =
150                            eval_exp_error(e1, env, side.other()) * eval_exp_error(e2, env, side);
151                        first + second
152                    }
153                    _ => eval_exp_error(e1, env, side) * eval_exp_error(e2, env, side),
154                },
155            }
156        }
157        Pow(_, 0) => EvalLeaf::Const(ScalarField::<C>::one()),
158        Pow(e, 1) => eval_exp_error(e, env, side),
159        Pow(e, 2) => match (exp.folding_degree(), e.folding_degree()) {
160            (Degree::Two, Degree::One) => {
161                let first = eval_exp_error(e, env, side) * eval_exp_error(e, env, side.other());
162                let second = eval_exp_error(e, env, side.other()) * eval_exp_error(e, env, side);
163                first + second
164            }
165            _ => {
166                let err = eval_exp_error(e, env, side);
167                err.clone() * err
168            }
169        },
170        Pow(e, i) => match exp.folding_degree() {
171            Degree::Zero => {
172                let e = eval_exp_error(e, env, side);
173                // TODO: Implement `pow` here for efficiency
174                let mut acc = e.clone();
175                for _ in 1..*i {
176                    acc = acc * e.clone();
177                }
178                acc
179            }
180            _ => panic!("degree over 2"),
181        },
182    }
183}
184
185/// Computes the error terms of a folding/homogeneous expression.
186/// The extended environment contains all the evaluations of the columns,
187/// including the ones added by the quadraticization process.
188/// `u` is the variables used to homogenize the expression.
189/// The output is a pair of error terms. To see how it is computed, see the
190/// [top-level documentation of the expressions module](crate::expressions).
191pub(crate) fn compute_error<C: FoldingConfig>(
192    exp: &IntegratedFoldingExpr<C>,
193    env: &ExtendedEnv<C>,
194    u: (ScalarField<C>, ScalarField<C>),
195) -> [Vec<ScalarField<C>>; 2] {
196    // FIXME: for speed, use inplace operations, and avoid cloning and
197    // allocating a new element.
198    // An allocation can cost a third of the time required for an addition and a
199    // 9th for a multiplication on the scalar field
200    // Indirections are also costly, so we should avoid them as much as
201    // possible, and inline code.
202    let (ul, ur) = (u.0, u.1);
203    let u_cross = ul * ur;
204    let zero_vec = vec![ScalarField::<C>::zero(); env.domain.size as usize];
205    let zero = || EvalLeaf::Result(zero_vec.clone());
206
207    let alphas_l = env
208        .get_relaxed_instance(Side::Left)
209        .extended_instance
210        .instance
211        .get_alphas();
212    let alphas_r = env
213        .get_relaxed_instance(Side::Right)
214        .extended_instance
215        .instance
216        .get_alphas();
217
218    let t_0 = {
219        let t_0 = (zero(), zero());
220        let (l, r) = exp.degree_0.iter().fold(t_0, |(l, r), (exp, sign, alpha)| {
221            //could be left or right, doesn't matter for constant terms
222            let exp = eval_exp_error(exp, env, Side::Left);
223            let alpha_l = alphas_l.get(*alpha).expect("alpha not present");
224            let alpha_r = alphas_r.get(*alpha).expect("alpha not present");
225            let left = exp.clone() * alpha_l;
226            let right = exp * alpha_r;
227            match sign {
228                Sign::Pos => (l + left, r + right),
229                Sign::Neg => (l - left, r - right),
230            }
231        });
232        let cross2 = u_cross.double();
233        let e0 = l.clone() * cross2 + r.clone() * ul.square();
234        let e1 = r * cross2 + l * ur.square();
235        (e0, e1)
236    };
237
238    let t_1 = {
239        let t_1 = (zero(), zero(), zero());
240        let (l, cross, r) = exp
241            .degree_1
242            .iter()
243            .fold(t_1, |(l, cross, r), (exp, sign, alpha)| {
244                let expl = eval_exp_error(exp, env, Side::Left);
245                let expr = eval_exp_error(exp, env, Side::Right);
246                let alpha_l = alphas_l.get(*alpha).expect("alpha not present");
247                let alpha_r = alphas_r.get(*alpha).expect("alpha not present");
248                let expr_cross = expl.clone() * alpha_r + expr.clone() * alpha_l;
249                let left = expl * alpha_l;
250                let right = expr * alpha_r;
251                match sign {
252                    Sign::Pos => (l + left, cross + expr_cross, r + right),
253                    Sign::Neg => (l - left, cross - expr_cross, r - right),
254                }
255            });
256        let e0 = cross.clone() * ul + l * ur;
257        let e1 = cross.clone() * ur + r * ul;
258        (e0, e1)
259    };
260    let t_2 = (zero(), zero());
261    let t_2 = exp.degree_2.iter().fold(t_2, |(l, r), (exp, sign, alpha)| {
262        let expl = eval_sided(exp, env, Side::Left);
263        let expr = eval_sided(exp, env, Side::Right);
264        //left or right matter in some way, but not at the top level call
265        let cross = eval_exp_error(exp, env, Side::Left);
266        let alpha_l = alphas_l.get(*alpha).expect("alpha not present");
267        let alpha_r = alphas_r.get(*alpha).expect("alpha not present");
268        let left = expl * alpha_r + cross.clone() * alpha_l;
269        let right = expr * alpha_l + cross * alpha_r;
270        match sign {
271            Sign::Pos => (l + left, r + right),
272            Sign::Neg => (l - left, r - right),
273        }
274    });
275    let t = [t_1, t_2]
276        .into_iter()
277        .fold(t_0, |(tl, tr), (txl, txr)| (tl + txl, tr + txr));
278
279    match t {
280        (EvalLeaf::Result(l), EvalLeaf::Result(r)) => [l, r],
281        _ => unreachable!(),
282    }
283}
284
285/// An extended environment contains the evaluations of all the columns, including
286/// the ones added by the quadraticization process. It also contains the
287/// the two instances and witnesses that are being folded.
288/// The domain is required to define the polynomial size of the evaluations of
289/// the error terms.
290pub(crate) struct ExtendedEnv<CF: FoldingConfig> {
291    inner: CF::Env,
292    instances: [RelaxedInstance<CF::Curve, CF::Instance>; 2],
293    witnesses: [RelaxedWitness<CF::Curve, CF::Witness>; 2],
294    domain: Radix2EvaluationDomain<ScalarField<CF>>,
295    selector: Option<CF::Selector>,
296}
297
298impl<CF: FoldingConfig> ExtendedEnv<CF> {
299    pub fn new(
300        structure: &CF::Structure,
301        // maybe better to have some structure extended or something like that
302        instances: [RelaxedInstance<CF::Curve, CF::Instance>; 2],
303        witnesses: [RelaxedWitness<CF::Curve, CF::Witness>; 2],
304        domain: Radix2EvaluationDomain<ScalarField<CF>>,
305        selector: Option<CF::Selector>,
306    ) -> Self {
307        let inner_instances = [
308            &instances[0].extended_instance.instance,
309            &instances[1].extended_instance.instance,
310        ];
311        let inner_witnesses = [
312            &witnesses[0].extended_witness.witness,
313            &witnesses[1].extended_witness.witness,
314        ];
315        let inner = <CF::Env>::new(structure, inner_instances, inner_witnesses);
316        Self {
317            inner,
318            instances,
319            witnesses,
320            domain,
321            selector,
322        }
323    }
324
325    pub fn enabled_selector(&self) -> Option<&CF::Selector> {
326        self.selector.as_ref()
327    }
328
329    #[allow(clippy::type_complexity)]
330    pub fn unwrap(
331        self,
332    ) -> (
333        [RelaxedInstance<CF::Curve, CF::Instance>; 2],
334        [RelaxedWitness<CF::Curve, CF::Witness>; 2],
335    ) {
336        let Self {
337            instances,
338            witnesses,
339            ..
340        } = self;
341        (instances, witnesses)
342    }
343
344    pub fn get_relaxed_instance(&self, side: Side) -> &RelaxedInstance<CF::Curve, CF::Instance> {
345        &self.instances[side as usize]
346    }
347
348    pub fn get_relaxed_witness(&self, side: Side) -> &RelaxedWitness<CF::Curve, CF::Witness> {
349        &self.witnesses[side as usize]
350    }
351
352    pub fn col(&self, col: &ExtendedFoldingColumn<CF>, side: Side) -> EvalLeaf<ScalarField<CF>> {
353        use EvalLeaf::Col;
354        use ExtendedFoldingColumn::*;
355        let relaxed_instance = self.get_relaxed_instance(side);
356        let relaxed_witness = self.get_relaxed_witness(side);
357        let alphas = relaxed_instance.extended_instance.instance.get_alphas();
358        match col {
359            Inner(Variable { col, row }) => Col(self.inner.col(*col, *row, side)),
360            WitnessExtended(i) => Col(&relaxed_witness
361                .extended_witness
362                .extended
363                .get(i)
364                .expect("extended column not present")
365                .evals),
366            Error => panic!("shouldn't happen"),
367            Constant(c) => EvalLeaf::Const(*c),
368            Challenge(chall) => EvalLeaf::Const(self.inner.challenge(*chall, side)),
369            Alpha(i) => {
370                let alpha = alphas.get(*i).expect("alpha not present");
371                EvalLeaf::Const(alpha)
372            }
373            Selector(s) => Col(self.inner.selector(s, side)),
374        }
375    }
376
377    pub fn col_try(&self, col: &ExtendedFoldingColumn<CF>, side: Side) -> bool {
378        use ExtendedFoldingColumn::*;
379        let relaxed_witness = self.get_relaxed_witness(side);
380        match col {
381            WitnessExtended(i) => relaxed_witness.extended_witness.extended.contains_key(i),
382            Error => panic!("shouldn't happen"),
383            Inner(_) | Constant(_) | Challenge(_) | Alpha(_) | Selector(_) => true,
384        }
385    }
386
387    pub fn add_witness_evals(&mut self, i: usize, evals: Vec<ScalarField<CF>>, side: Side) {
388        let (_instance, relaxed_witness) = match side {
389            Side::Left => (&self.instances[0], &mut self.witnesses[0]),
390            Side::Right => (&self.instances[1], &mut self.witnesses[1]),
391        };
392        let evals = Evaluations::from_vec_and_domain(evals, self.domain);
393        relaxed_witness.extended_witness.add_witness_evals(i, evals);
394    }
395
396    pub fn needs_extension(&self, side: Side) -> bool {
397        !match side {
398            Side::Left => self.witnesses[0].extended_witness.is_extended(),
399            Side::Right => self.witnesses[1].extended_witness.is_extended(),
400        }
401    }
402
403    /// Computes the extended witness column and the corresponding commitments,
404    /// updating the innner instance/witness pairs
405    pub fn compute_extension(
406        self,
407        witness_generator: &ExtendedWitnessGenerator<CF>,
408        srs: &CF::Srs,
409    ) -> Self {
410        let env = self;
411        let env = witness_generator.compute_extended_witness(env, Side::Left);
412        let env = witness_generator.compute_extended_witness(env, Side::Right);
413        let env = env.compute_extended_commitments(srs, Side::Left);
414        env.compute_extended_commitments(srs, Side::Right)
415    }
416
417    // FIXME: use reference to avoid indirect copying/cloning.
418    /// Computes the commitments of the columns added by quadriaticization, for
419    /// the given side.
420    /// The commitments are added to the instance, in the same order for both
421    /// side.
422    /// Note that this function is only going to be called on the left instance
423    /// once. When we fold the second time, the left instance will already be
424    /// relaxed and will have the extended columns.
425    /// Therefore, the blinder is always the one provided by the user, and it is
426    /// saved in the field `blinder` in the case of a relaxed instance that has
427    /// been built from a non-relaxed one.
428    fn compute_extended_commitments(mut self, srs: &CF::Srs, side: Side) -> Self {
429        let (relaxed_instance, relaxed_witness) = match side {
430            Side::Left => (&mut self.instances[0], &self.witnesses[0]),
431            Side::Right => (&mut self.instances[1], &self.witnesses[1]),
432        };
433
434        // FIXME: use parallelisation
435        let blinder = PolyComm::new(vec![relaxed_instance.blinder]);
436        for (expected_i, (i, wit)) in relaxed_witness.extended_witness.extended.iter().enumerate() {
437            // in case any where to be missing for some reason
438            assert_eq!(*i, expected_i);
439            // Blinding the commitments to support the case the witness is zero.
440            // The IVC circuit expects to have non-zero commitments.
441            let commit = srs
442                .commit_evaluations_custom(self.domain, wit, &blinder)
443                .unwrap()
444                .commitment;
445            relaxed_instance.extended_instance.extended.push(commit)
446        }
447        // FIXME: maybe returning a value is not necessary as it does inplace operations.
448        // It implies copying on the stack and possibly copy multiple times.
449        self
450    }
451
452    /// Return the list of scalars and commitments to be absorbed, by
453    /// concatenating the ones of the left with the ones of the right instance
454    pub(crate) fn to_absorb(
455        &self,
456        t0: &CF::Curve,
457        t1: &CF::Curve,
458    ) -> (Vec<ScalarField<CF>>, Vec<CF::Curve>) {
459        let mut left = self.instances[0].to_absorb();
460        let right = self.instances[1].to_absorb();
461
462        left.0.extend(right.0);
463        left.1.extend(right.1);
464        left.1.extend([t0, t1]);
465        left
466    }
467}
folding/error_term.rs

folding/
error_term.rs
