Nova/src/bellperson/solver.rs
src/bellperson/solver.rsRaw
1//! Support for generating R1CS witness using bellperson.
2
3use crate::traits::Group;
4use ff::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 Self {
95 a_aux_density: DensityTracker::new(),
96 b_input_density: DensityTracker::new(),
97 b_aux_density: DensityTracker::new(),
98 a: vec![],
99 b: vec![],
100 c: vec![],
101 input_assignment: vec![],
102 aux_assignment: vec![],
103 }
104 }
105
106 fn alloc<F, A, AR>(&mut self, _: A, f: F) -> Result<Variable, SynthesisError>
107 where
108 F: FnOnce() -> Result<G::Scalar, SynthesisError>,
109 A: FnOnce() -> AR,
110 AR: Into<String>,
111 {
112 self.aux_assignment.push(f()?);
113 self.a_aux_density.add_element();
114 self.b_aux_density.add_element();
115
116 Ok(Variable(Index::Aux(self.aux_assignment.len() - 1)))
117 }
118
119 fn alloc_input<F, A, AR>(&mut self, _: A, f: F) -> Result<Variable, SynthesisError>
120 where
121 F: FnOnce() -> Result<G::Scalar, SynthesisError>,
122 A: FnOnce() -> AR,
123 AR: Into<String>,
124 {
125 self.input_assignment.push(f()?);
126 self.b_input_density.add_element();
127
128 Ok(Variable(Index::Input(self.input_assignment.len() - 1)))
129 }
130
131 fn enforce<A, AR, LA, LB, LC>(&mut self, _: A, a: LA, b: LB, c: LC)
132 where
133 A: FnOnce() -> AR,
134 AR: Into<String>,
135 LA: FnOnce(LinearCombination<G::Scalar>) -> LinearCombination<G::Scalar>,
136 LB: FnOnce(LinearCombination<G::Scalar>) -> LinearCombination<G::Scalar>,
137 LC: FnOnce(LinearCombination<G::Scalar>) -> LinearCombination<G::Scalar>,
138 {
139 let a = a(LinearCombination::zero());
140 let b = b(LinearCombination::zero());
141 let c = c(LinearCombination::zero());
142
143 let input_assignment = &self.input_assignment;
144 let aux_assignment = &self.aux_assignment;
145 let a_aux_density = &mut self.a_aux_density;
146 let b_input_density = &mut self.b_input_density;
147 let b_aux_density = &mut self.b_aux_density;
148
149 let a_res = a.eval(
150 // Inputs have full density in the A query
151 // because there are constraints of the
152 // form x * 0 = 0 for each input.
153 None,
154 Some(a_aux_density),
155 input_assignment,
156 aux_assignment,
157 );
158
159 let b_res = b.eval(
160 Some(b_input_density),
161 Some(b_aux_density),
162 input_assignment,
163 aux_assignment,
164 );
165
166 let c_res = c.eval(
167 // There is no C polynomial query,
168 // though there is an (beta)A + (alpha)B + C
169 // query for all aux variables.
170 // However, that query has full density.
171 None,
172 None,
173 input_assignment,
174 aux_assignment,
175 );
176
177 self.a.push(a_res);
178 self.b.push(b_res);
179 self.c.push(c_res);
180 }
181
182 fn push_namespace<NR, N>(&mut self, _: N)
183 where
184 NR: Into<String>,
185 N: FnOnce() -> NR,
186 {
187 // Do nothing; we don't care about namespaces in this context.
188 }
189
190 fn pop_namespace(&mut self) {
191 // Do nothing; we don't care about namespaces in this context.
192 }
193
194 fn get_root(&mut self) -> &mut Self::Root {
195 self
196 }
197
198 fn is_extensible() -> bool {
199 true
200 }
201
202 fn extend(&mut self, other: Self) {
203 self.a_aux_density.extend(other.a_aux_density, false);
204 self.b_input_density.extend(other.b_input_density, true);
205 self.b_aux_density.extend(other.b_aux_density, false);
206
207 self.a.extend(other.a);
208 self.b.extend(other.b);
209 self.c.extend(other.c);
210
211 self.input_assignment
212 // Skip first input, which must have been a temporarily allocated one variable.
213 .extend(&other.input_assignment[1..]);
214 self.aux_assignment.extend(other.aux_assignment);
215 }
216}