folding/
decomposable_folding.rs

1//! This variant of folding is designed to efficiently handle cases where
2//! certain assumptions about the witness can be made.
3//! Specifically, an alternative is provided such that the scheme is created
4//! from a set of list of constraints, each set associated with a particular
5//! selector, as opposed to a single list of constraints.
6
7use crate::{
8    columns::ExtendedFoldingColumn,
9    error_term::{compute_error, ExtendedEnv},
10    expressions::{ExpExtension, FoldingCompatibleExpr, FoldingCompatibleExprInner, FoldingExp},
11    instance_witness::{RelaxableInstance, RelaxablePair, RelaxedInstance, RelaxedWitness},
12    BaseField, FoldingConfig, FoldingOutput, FoldingScheme, ScalarField,
13};
14use ark_poly::{Evaluations, Radix2EvaluationDomain};
15use mina_poseidon::FqSponge;
16use poly_commitment::{PolyComm, SRS};
17use std::collections::BTreeMap;
18
19pub struct DecomposableFoldingScheme<'a, CF: FoldingConfig> {
20    inner: FoldingScheme<'a, CF>,
21}
22
23impl<'a, CF: FoldingConfig> DecomposableFoldingScheme<'a, CF> {
24    /// Creates a new folding scheme for decomposable circuits.
25    /// It takes as input:
26    /// - a set of constraints, each associated with a particular selector;
27    /// - a list of common constraints, that are applied to every instance
28    ///   regardless of the selector (can be empty);
29    /// - a structured reference string;
30    /// - a domain;
31    /// - a structure of the associated folding configuration.
32    ///
33    /// The function uses the normal `FoldingScheme::new()` function to create
34    /// the decomposable scheme, using for that the concatenation of the
35    /// constraints associated with each selector multiplied by the selector,
36    /// and the common constraints.
37    /// This product is performed with
38    /// `FoldingCompatibleExprInner::Extensions(ExpExtension::Selector(s))`.
39    pub fn new(
40        // constraints with a dynamic selector
41        constraints: BTreeMap<CF::Selector, Vec<FoldingCompatibleExpr<CF>>>,
42        // constraints to be applied to every single instance regardless of selectors
43        common_constraints: Vec<FoldingCompatibleExpr<CF>>,
44        srs: &'a CF::Srs,
45        domain: Radix2EvaluationDomain<ScalarField<CF>>,
46        structure: &CF::Structure,
47    ) -> (Self, FoldingCompatibleExpr<CF>) {
48        let constraints = constraints
49            .into_iter()
50            .flat_map(|(s, exps)| {
51                exps.into_iter().map(move |exp| {
52                    let s = FoldingCompatibleExprInner::Extensions(ExpExtension::Selector(s));
53                    let s = Box::new(FoldingCompatibleExpr::Atom(s));
54                    FoldingCompatibleExpr::Mul(s, Box::new(exp))
55                })
56            })
57            .chain(common_constraints)
58            .collect();
59        let (inner, exp) = FoldingScheme::new(constraints, srs, domain, structure);
60        (DecomposableFoldingScheme { inner }, exp)
61    }
62
63    /// Return the number of additional columns added by quadraticization
64    pub fn get_number_of_additional_columns(&self) -> usize {
65        self.inner.get_number_of_additional_columns()
66    }
67
68    #[allow(clippy::type_complexity)]
69    /// folding with a selector will assume that only the selector in question
70    /// is enabled (i.e. set to 1) in all rows, and any other selector is 0 over
71    /// all rows.
72    /// If that is not the case, providing `None` will fold without assumptions
73    pub fn fold_instance_witness_pair<A, B, Sponge>(
74        &self,
75        a: A,
76        b: B,
77        selector: Option<CF::Selector>,
78        fq_sponge: &mut Sponge,
79    ) -> FoldingOutput<CF>
80    where
81        A: RelaxablePair<CF::Curve, CF::Instance, CF::Witness>,
82        B: RelaxablePair<CF::Curve, CF::Instance, CF::Witness>,
83        Sponge: FqSponge<BaseField<CF>, CF::Curve, ScalarField<CF>>,
84    {
85        let scheme = &self.inner;
86        let a = a.relax(&scheme.zero_vec);
87        let b = b.relax(&scheme.zero_vec);
88
89        let u = (a.0.u, b.0.u);
90
91        let (left_instance, left_witness) = a;
92        let (right_instance, right_witness) = b;
93        let env = ExtendedEnv::new(
94            &scheme.structure,
95            [left_instance, right_instance],
96            [left_witness, right_witness],
97            scheme.domain,
98            selector,
99        );
100
101        let env = env.compute_extension(&scheme.extended_witness_generator, scheme.srs);
102        let error = compute_error(&scheme.expression, &env, u);
103        let error_evals = error.map(|e| Evaluations::from_vec_and_domain(e, scheme.domain));
104
105        let error_commitments = error_evals
106            .iter()
107            .map(|e| scheme.srs.commit_evaluations_non_hiding(scheme.domain, e))
108            .collect::<Vec<_>>();
109        let error_commitments: [PolyComm<CF::Curve>; 2] = error_commitments.try_into().unwrap();
110
111        let error = error_evals.into_iter().map(|e| e.evals).collect::<Vec<_>>();
112        let error: [Vec<_>; 2] = error.try_into().unwrap();
113
114        // sanity check to verify that we only have one commitment in polycomm
115        // (i.e. domain = poly size)
116        assert_eq!(error_commitments[0].len(), 1);
117        assert_eq!(error_commitments[1].len(), 1);
118
119        let t0 = &error_commitments[0].get_first_chunk();
120        let t1 = &error_commitments[1].get_first_chunk();
121
122        let to_absorb = env.to_absorb(t0, t1);
123        fq_sponge.absorb_fr(&to_absorb.0);
124        fq_sponge.absorb_g(&to_absorb.1);
125
126        let challenge = fq_sponge.challenge();
127
128        let (
129            [relaxed_extended_left_instance, relaxed_extended_right_instance],
130            [relaxed_extended_left_witness, relaxed_extended_right_witness],
131        ) = env.unwrap();
132
133        let folded_instance = RelaxedInstance::combine_and_sub_cross_terms(
134            // FIXME: remove clone
135            relaxed_extended_left_instance.clone(),
136            relaxed_extended_right_instance.clone(),
137            challenge,
138            &error_commitments,
139        );
140
141        let folded_witness = RelaxedWitness::combine_and_sub_cross_terms(
142            relaxed_extended_left_witness,
143            relaxed_extended_right_witness,
144            challenge,
145            error,
146        );
147        FoldingOutput {
148            folded_instance,
149            folded_witness,
150            t_0: error_commitments[0].clone(),
151            t_1: error_commitments[1].clone(),
152            relaxed_extended_left_instance,
153            relaxed_extended_right_instance,
154            to_absorb,
155        }
156    }
157
158    /// Fold two relaxable instances into a relaxed instance.
159    /// It is parametrized by two different types `A` and `B` that represent
160    /// "relaxable" instances to be able to fold a normal and "already relaxed"
161    /// instance.
162    pub fn fold_instance_pair<A, B, Sponge>(
163        &self,
164        a: A,
165        b: B,
166        error_commitments: [PolyComm<CF::Curve>; 2],
167        fq_sponge: &mut Sponge,
168    ) -> RelaxedInstance<CF::Curve, CF::Instance>
169    where
170        A: RelaxableInstance<CF::Curve, CF::Instance>,
171        B: RelaxableInstance<CF::Curve, CF::Instance>,
172        Sponge: FqSponge<BaseField<CF>, CF::Curve, ScalarField<CF>>,
173    {
174        let a: RelaxedInstance<CF::Curve, CF::Instance> = a.relax();
175        let b: RelaxedInstance<CF::Curve, CF::Instance> = b.relax();
176
177        // sanity check to verify that we only have one commitment in polycomm
178        // (i.e. domain = poly size)
179        assert_eq!(error_commitments[0].len(), 1);
180        assert_eq!(error_commitments[1].len(), 1);
181
182        let to_absorb = {
183            let mut left = a.to_absorb();
184            let right = b.to_absorb();
185            left.0.extend(right.0);
186            left.1.extend(right.1);
187            left.1.extend([
188                error_commitments[0].get_first_chunk(),
189                error_commitments[1].get_first_chunk(),
190            ]);
191            left
192        };
193
194        fq_sponge.absorb_fr(&to_absorb.0);
195        fq_sponge.absorb_g(&to_absorb.1);
196
197        let challenge = fq_sponge.challenge();
198
199        RelaxedInstance::combine_and_sub_cross_terms(a, b, challenge, &error_commitments)
200    }
201}
202
203pub(crate) fn check_selector<C: FoldingConfig>(exp: &FoldingExp<C>) -> Option<&C::Selector> {
204    match exp {
205        FoldingExp::Atom(ExtendedFoldingColumn::Selector(s)) => Some(s),
206        _ => None,
207    }
208}
folding/decomposable_folding.rs

folding/
decomposable_folding.rs
