ark_relations/gr1cs/
instance_outliner.rs

1use ark_ff::Field;
2
3use crate::lc_diff;
4
5use super::{lc, ConstraintSystem, Label, SynthesisError, Variable};
6use ark_std::rc::Rc;
7use core::fmt::Debug;
8
9/// An instance outliner is a strategy for reducing the number of constraints
10/// that public input/instance variables are involved in.
11/// It does this as follows:
12/// 1. Create new public input variables that correspond to the original input variables
13/// 2. Replace the original input variables with corresponding new witness variables
14/// 3. Enforce equality between the new input variables and the new witness variables
15/// 4. In every constraint that involves the original input variables, replace them with the new witness variables.
16#[derive(Clone)]
17pub struct InstanceOutliner<F: Field> {
18    /// The label for the predicate that is used to enforce equality between
19    /// the new input/instance variables and the new witness variables.
20    pub pred_label: Label,
21    /// The strategy for outlining the instance variables
22    /// It takes as input the constraint system, and a map from the new
23    /// instance variables to the new witness variables.
24    pub func: OutliningFunc<F>,
25}
26
27type OutliningFunc<F> =
28    Rc<dyn Fn(&mut ConstraintSystem<F>, &[Variable]) -> Result<(), SynthesisError>>;
29
30impl<F: Field> Debug for InstanceOutliner<F> {
31    fn fmt(&self, f: &mut ark_std::fmt::Formatter<'_>) -> ark_std::fmt::Result {
32        write!(
33            f,
34            "InstanceOutliner {{ pred_label: {:?} }}",
35            self.pred_label
36        )
37    }
38}
39
40/// The outlining strategy for R1CS constraints.
41pub fn outline_r1cs<F: Field>(
42    cs: &mut ConstraintSystem<F>,
43    instance_witness_map: &[Variable],
44) -> crate::gr1cs::Result<()> {
45    // Now, enforce the equality between the instance and the corresponding witness
46    // variable This is done by iterating over the instance-witness map
47    // which contains the unique instance-witness pairs The equality
48    // constraints are enforced with r1cs constraints, it is assumed that a
49    // constraint system has a default r1cs predicate registered
50    let one = instance_witness_map[0];
51    cs.enforce_r1cs_constraint(|| lc![one], || lc![one], || lc![Variable::One])?;
52    for (instance, witness) in instance_witness_map.iter().enumerate().skip(1) {
53        cs.enforce_r1cs_constraint(
54            || lc![one],
55            || lc![*witness],
56            || lc![Variable::instance(instance)],
57        )?;
58    }
59
60    Ok(())
61}
62
63/// The outlining strategy for Square R1CS constraints.
64pub fn outline_sr1cs<F: Field>(
65    cs: &mut ConstraintSystem<F>,
66    instance_witness_map: &[Variable],
67) -> crate::gr1cs::Result<()> {
68    // Now, enforce the equality between the instance and the corresponding witness
69    // variable This is done by iterating over the instance-witness map
70    // which contains the unique instance-witness pairs The equality
71    // constraints are enforced with r1cs constraints, it is assumed that a
72    // constraint system has a default r1cs predicate registered
73    for (instance, witness) in instance_witness_map.iter().enumerate() {
74        cs.enforce_sr1cs_constraint(
75            || lc_diff![Variable::instance(instance), *witness],
76            || lc![],
77        )?;
78    }
79
80    Ok(())
81}
ark_relations/gr1cs/instance_outliner.rs

ark_relations/gr1cs/
instance_outliner.rs
