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