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