Nova/src/bellperson/shape_cs.rs
src/bellperson/shape_cs.rsRaw
1//! Support for generating R1CS shape using bellperson.
2
3use std::{
4 cmp::Ordering,
5 collections::{BTreeMap, HashMap},
6};
7
8use crate::traits::Group;
9use ff::{Field, PrimeField};
10
11use bellperson::{ConstraintSystem, Index, LinearCombination, SynthesisError, Variable};
12
13#[derive(Clone, Copy)]
14struct OrderedVariable(Variable);
15
16#[derive(Debug)]
17enum NamedObject {
18 Constraint(usize),
19 Var(Variable),
20 Namespace,
21}
22
23impl Eq for OrderedVariable {}
24impl PartialEq for OrderedVariable {
25 fn eq(&self, other: &OrderedVariable) -> bool {
26 match (self.0.get_unchecked(), other.0.get_unchecked()) {
27 (Index::Input(ref a), Index::Input(ref b)) => a == b,
28 (Index::Aux(ref a), Index::Aux(ref b)) => a == b,
29 _ => false,
30 }
31 }
32}
33impl PartialOrd for OrderedVariable {
34 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
35 Some(self.cmp(other))
36 }
37}
38impl Ord for OrderedVariable {
39 fn cmp(&self, other: &Self) -> Ordering {
40 match (self.0.get_unchecked(), other.0.get_unchecked()) {
41 (Index::Input(ref a), Index::Input(ref b)) => a.cmp(b),
42 (Index::Aux(ref a), Index::Aux(ref b)) => a.cmp(b),
43 (Index::Input(_), Index::Aux(_)) => Ordering::Less,
44 (Index::Aux(_), Index::Input(_)) => Ordering::Greater,
45 }
46 }
47}
48
49#[allow(clippy::upper_case_acronyms)]
50/// `ShapeCS` is a `ConstraintSystem` for creating `R1CSShape`s for a circuit.
51pub struct ShapeCS<G: Group>
52where
53 G::Scalar: PrimeField + Field,
54{
55 named_objects: HashMap<String, NamedObject>,
56 current_namespace: Vec<String>,
57 #[allow(clippy::type_complexity)]
58 /// All constraints added to the `ShapeCS`.
59 pub constraints: Vec<(
60 LinearCombination<G::Scalar>,
61 LinearCombination<G::Scalar>,
62 LinearCombination<G::Scalar>,
63 String,
64 )>,
65 inputs: Vec<String>,
66 aux: Vec<String>,
67}
68
69fn proc_lc<Scalar: PrimeField>(
70 terms: &LinearCombination<Scalar>,
71) -> BTreeMap<OrderedVariable, Scalar> {
72 let mut map = BTreeMap::new();
73 for (var, &coeff) in terms.iter() {
74 map
75 .entry(OrderedVariable(var))
76 .or_insert_with(Scalar::zero)
77 .add_assign(&coeff);
78 }
79
80 // Remove terms that have a zero coefficient to normalize
81 let mut to_remove = vec![];
82 for (var, coeff) in map.iter() {
83 if coeff.is_zero().into() {
84 to_remove.push(*var)
85 }
86 }
87
88 for var in to_remove {
89 map.remove(&var);
90 }
91
92 map
93}
94
95impl<G: Group> ShapeCS<G>
96where
97 G::Scalar: PrimeField,
98{
99 /// Create a new, default `ShapeCS`,
100 pub fn new() -> Self {
101 ShapeCS::default()
102 }
103
104 /// Returns the number of constraints defined for this `ShapeCS`.
105 pub fn num_constraints(&self) -> usize {
106 self.constraints.len()
107 }
108
109 /// Returns the number of inputs defined for this `ShapeCS`.
110 pub fn num_inputs(&self) -> usize {
111 self.inputs.len()
112 }
113
114 /// Returns the number of aux inputs defined for this `ShapeCS`.
115 pub fn num_aux(&self) -> usize {
116 self.aux.len()
117 }
118
119 /// Print all public inputs, aux inputs, and constraint names.
120 pub fn pretty_print_list(&self) -> Vec<String> {
121 let mut result = Vec::new();
122
123 for input in &self.inputs {
124 result.push(format!("INPUT {}", input));
125 }
126 for aux in &self.aux {
127 result.push(format!("AUX {}", aux));
128 }
129
130 for &(ref _a, ref _b, ref _c, ref name) in &self.constraints {
131 result.push(name.to_string());
132 }
133
134 result
135 }
136
137 /// Print all iputs and a detailed representation of each constraint.
138 pub fn pretty_print(&self) -> String {
139 let mut s = String::new();
140
141 for input in &self.inputs {
142 s.push_str(&format!("INPUT {}\n", &input))
143 }
144
145 let negone = -<G::Scalar>::one();
146
147 let powers_of_two = (0..G::Scalar::NUM_BITS)
148 .map(|i| G::Scalar::from(2u64).pow_vartime(&[u64::from(i)]))
149 .collect::<Vec<_>>();
150
151 let pp = |s: &mut String, lc: &LinearCombination<G::Scalar>| {
152 s.push('(');
153 let mut is_first = true;
154 for (var, coeff) in proc_lc::<G::Scalar>(lc) {
155 if coeff == negone {
156 s.push_str(" - ")
157 } else if !is_first {
158 s.push_str(" + ")
159 }
160 is_first = false;
161
162 if coeff != <G::Scalar>::one() && coeff != negone {
163 for (i, x) in powers_of_two.iter().enumerate() {
164 if x == &coeff {
165 s.push_str(&format!("2^{} . ", i));
166 break;
167 }
168 }
169
170 s.push_str(&format!("{:?} . ", coeff))
171 }
172
173 match var.0.get_unchecked() {
174 Index::Input(i) => {
175 s.push_str(&format!("`I{}`", &self.inputs[i]));
176 }
177 Index::Aux(i) => {
178 s.push_str(&format!("`A{}`", &self.aux[i]));
179 }
180 }
181 }
182 if is_first {
183 // Nothing was visited, print 0.
184 s.push('0');
185 }
186 s.push(')');
187 };
188
189 for &(ref a, ref b, ref c, ref name) in &self.constraints {
190 s.push('\n');
191
192 s.push_str(&format!("{}: ", name));
193 pp(&mut s, a);
194 s.push_str(" * ");
195 pp(&mut s, b);
196 s.push_str(" = ");
197 pp(&mut s, c);
198 }
199
200 s.push('\n');
201
202 s
203 }
204
205 /// Associate `NamedObject` with `path`.
206 /// `path` must not already have an associated object.
207 fn set_named_obj(&mut self, path: String, to: NamedObject) {
208 assert!(
209 !self.named_objects.contains_key(&path),
210 "tried to create object at existing path: {}",
211 path
212 );
213
214 self.named_objects.insert(path, to);
215 }
216}
217
218impl<G: Group> Default for ShapeCS<G>
219where
220 G::Scalar: PrimeField,
221{
222 fn default() -> Self {
223 let mut map = HashMap::new();
224 map.insert("ONE".into(), NamedObject::Var(ShapeCS::<G>::one()));
225 ShapeCS {
226 named_objects: map,
227 current_namespace: vec![],
228 constraints: vec![],
229 inputs: vec![String::from("ONE")],
230 aux: vec![],
231 }
232 }
233}
234
235impl<G: Group> ConstraintSystem<G::Scalar> for ShapeCS<G>
236where
237 G::Scalar: PrimeField,
238{
239 type Root = Self;
240
241 fn alloc<F, A, AR>(&mut self, annotation: A, _f: F) -> Result<Variable, SynthesisError>
242 where
243 F: FnOnce() -> Result<G::Scalar, SynthesisError>,
244 A: FnOnce() -> AR,
245 AR: Into<String>,
246 {
247 let path = compute_path(&self.current_namespace, &annotation().into());
248 self.aux.push(path);
249
250 Ok(Variable::new_unchecked(Index::Aux(self.aux.len() - 1)))
251 }
252
253 fn alloc_input<F, A, AR>(&mut self, annotation: A, _f: F) -> Result<Variable, SynthesisError>
254 where
255 F: FnOnce() -> Result<G::Scalar, SynthesisError>,
256 A: FnOnce() -> AR,
257 AR: Into<String>,
258 {
259 let path = compute_path(&self.current_namespace, &annotation().into());
260 self.inputs.push(path);
261
262 Ok(Variable::new_unchecked(Index::Input(self.inputs.len() - 1)))
263 }
264
265 fn enforce<A, AR, LA, LB, LC>(&mut self, annotation: A, a: LA, b: LB, c: LC)
266 where
267 A: FnOnce() -> AR,
268 AR: Into<String>,
269 LA: FnOnce(LinearCombination<G::Scalar>) -> LinearCombination<G::Scalar>,
270 LB: FnOnce(LinearCombination<G::Scalar>) -> LinearCombination<G::Scalar>,
271 LC: FnOnce(LinearCombination<G::Scalar>) -> LinearCombination<G::Scalar>,
272 {
273 let path = compute_path(&self.current_namespace, &annotation().into());
274 let index = self.constraints.len();
275 self.set_named_obj(path.clone(), NamedObject::Constraint(index));
276
277 let a = a(LinearCombination::zero());
278 let b = b(LinearCombination::zero());
279 let c = c(LinearCombination::zero());
280
281 self.constraints.push((a, b, c, path));
282 }
283
284 fn push_namespace<NR, N>(&mut self, name_fn: N)
285 where
286 NR: Into<String>,
287 N: FnOnce() -> NR,
288 {
289 let name = name_fn().into();
290 let path = compute_path(&self.current_namespace, &name);
291 self.set_named_obj(path, NamedObject::Namespace);
292 self.current_namespace.push(name);
293 }
294
295 fn pop_namespace(&mut self) {
296 assert!(self.current_namespace.pop().is_some());
297 }
298
299 fn get_root(&mut self) -> &mut Self::Root {
300 self
301 }
302}
303
304fn compute_path(ns: &[String], this: &str) -> String {
305 assert!(
306 !this.chars().any(|a| a == '/'),
307 "'/' is not allowed in names"
308 );
309
310 let mut name = String::new();
311
312 let mut needs_separation = false;
313 for ns in ns.iter().chain(Some(this.to_string()).iter()) {
314 if needs_separation {
315 name += "/";
316 }
317
318 name += ns;
319 needs_separation = true;
320 }
321
322 name
323}