1//! Support for generating R1CS witness using bellperson.
  2
  3use crate::traits::Group;
  4use ff::{Field, PrimeField};
  5
  6use bellperson::{
  7  multiexp::DensityTracker, ConstraintSystem, Index, LinearCombination, SynthesisError, Variable,
  8};
  9
 10/// A `ConstraintSystem` which calculates witness values for a concrete instance of an R1CS circuit.
 11#[derive(PartialEq)]
 12pub struct SatisfyingAssignment<G: Group>
 13where
 14  G::Scalar: PrimeField,
 15{
 16  // Density of queries
 17  a_aux_density: DensityTracker,
 18  b_input_density: DensityTracker,
 19  b_aux_density: DensityTracker,
 20
 21  // Evaluations of A, B, C polynomials
 22  a: Vec<G::Scalar>,
 23  b: Vec<G::Scalar>,
 24  c: Vec<G::Scalar>,
 25
 26  // Assignments of variables
 27  pub(crate) input_assignment: Vec<G::Scalar>,
 28  pub(crate) aux_assignment: Vec<G::Scalar>,
 29}
 30use std::fmt;
 31
 32impl<G: Group> fmt::Debug for SatisfyingAssignment<G>
 33where
 34  G::Scalar: PrimeField,
 35{
 36  fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
 37    fmt
 38      .debug_struct("SatisfyingAssignment")
 39      .field("a_aux_density", &self.a_aux_density)
 40      .field("b_input_density", &self.b_input_density)
 41      .field("b_aux_density", &self.b_aux_density)
 42      .field(
 43        "a",
 44        &self
 45          .a
 46          .iter()
 47          .map(|v| format!("Fr({v:?})"))
 48          .collect::<Vec<_>>(),
 49      )
 50      .field(
 51        "b",
 52        &self
 53          .b
 54          .iter()
 55          .map(|v| format!("Fr({v:?})"))
 56          .collect::<Vec<_>>(),
 57      )
 58      .field(
 59        "c",
 60        &self
 61          .c
 62          .iter()
 63          .map(|v| format!("Fr({v:?})"))
 64          .collect::<Vec<_>>(),
 65      )
 66      .field("input_assignment", &self.input_assignment)
 67      .field("aux_assignment", &self.aux_assignment)
 68      .finish()
 69  }
 70}
 71
 72impl<G: Group> ConstraintSystem<G::Scalar> for SatisfyingAssignment<G>
 73where
 74  G::Scalar: PrimeField,
 75{
 76  type Root = Self;
 77
 78  fn new() -> Self {
 79    let input_assignment = vec![G::Scalar::ONE];
 80    let mut d = DensityTracker::new();
 81    d.add_element();
 82
 83    Self {
 84      a_aux_density: DensityTracker::new(),
 85      b_input_density: d,
 86      b_aux_density: DensityTracker::new(),
 87      a: vec![],
 88      b: vec![],
 89      c: vec![],
 90      input_assignment,
 91      aux_assignment: vec![],
 92    }
 93  }
 94
 95  fn alloc<F, A, AR>(&mut self, _: A, f: F) -> Result<Variable, SynthesisError>
 96  where
 97    F: FnOnce() -> Result<G::Scalar, SynthesisError>,
 98    A: FnOnce() -> AR,
 99    AR: Into<String>,
100  {
101    self.aux_assignment.push(f()?);
102    self.a_aux_density.add_element();
103    self.b_aux_density.add_element();
104
105    Ok(Variable(Index::Aux(self.aux_assignment.len() - 1)))
106  }
107
108  fn alloc_input<F, A, AR>(&mut self, _: A, f: F) -> Result<Variable, SynthesisError>
109  where
110    F: FnOnce() -> Result<G::Scalar, SynthesisError>,
111    A: FnOnce() -> AR,
112    AR: Into<String>,
113  {
114    self.input_assignment.push(f()?);
115    self.b_input_density.add_element();
116
117    Ok(Variable(Index::Input(self.input_assignment.len() - 1)))
118  }
119
120  fn enforce<A, AR, LA, LB, LC>(&mut self, _: A, _a: LA, _b: LB, _c: LC)
121  where
122    A: FnOnce() -> AR,
123    AR: Into<String>,
124    LA: FnOnce(LinearCombination<G::Scalar>) -> LinearCombination<G::Scalar>,
125    LB: FnOnce(LinearCombination<G::Scalar>) -> LinearCombination<G::Scalar>,
126    LC: FnOnce(LinearCombination<G::Scalar>) -> LinearCombination<G::Scalar>,
127  {
128    // Do nothing: we don't care about linear-combination evaluations in this context.
129  }
130
131  fn push_namespace<NR, N>(&mut self, _: N)
132  where
133    NR: Into<String>,
134    N: FnOnce() -> NR,
135  {
136    // Do nothing; we don't care about namespaces in this context.
137  }
138
139  fn pop_namespace(&mut self) {
140    // Do nothing; we don't care about namespaces in this context.
141  }
142
143  fn get_root(&mut self) -> &mut Self::Root {
144    self
145  }
146
147  fn is_extensible() -> bool {
148    true
149  }
150
151  fn extend(&mut self, other: Self) {
152    self.a_aux_density.extend(other.a_aux_density, false);
153    self.b_input_density.extend(other.b_input_density, true);
154    self.b_aux_density.extend(other.b_aux_density, false);
155
156    self.a.extend(other.a);
157    self.b.extend(other.b);
158    self.c.extend(other.c);
159
160    self.input_assignment
161            // Skip first input, which must have been a temporarily allocated one variable.
162            .extend(&other.input_assignment[1..]);
163    self.aux_assignment.extend(other.aux_assignment);
164  }
165}