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 #[allow(dead_code)]
121 pub fn pretty_print_list(&self) -> Vec<String> {
122 let mut result = Vec::new();
123
124 for input in &self.inputs {
125 result.push(format!("INPUT {}", input));
126 }
127 for aux in &self.aux {
128 result.push(format!("AUX {}", aux));
129 }
130
131 for &(ref _a, ref _b, ref _c, ref name) in &self.constraints {
132 result.push(name.to_string());
133 }
134
135 result
136 }
137
138 /// Print all iputs and a detailed representation of each constraint.
139 #[allow(dead_code)]
140 pub fn pretty_print(&self) -> String {
141 let mut s = String::new();
142
143 for input in &self.inputs {
144 s.push_str(&format!("INPUT {}\n", &input))
145 }
146
147 let negone = -<G::Scalar>::one();
148
149 let powers_of_two = (0..G::Scalar::NUM_BITS)
150 .map(|i| G::Scalar::from(2u64).pow_vartime(&[u64::from(i)]))
151 .collect::<Vec<_>>();
152
153 let pp = |s: &mut String, lc: &LinearCombination<G::Scalar>| {
154 s.push('(');
155 let mut is_first = true;
156 for (var, coeff) in proc_lc::<G::Scalar>(lc) {
157 if coeff == negone {
158 s.push_str(" - ")
159 } else if !is_first {
160 s.push_str(" + ")
161 }
162 is_first = false;
163
164 if coeff != <G::Scalar>::one() && coeff != negone {
165 for (i, x) in powers_of_two.iter().enumerate() {
166 if x == &coeff {
167 s.push_str(&format!("2^{} . ", i));
168 break;
169 }
170 }
171
172 s.push_str(&format!("{:?} . ", coeff))
173 }
174
175 match var.0.get_unchecked() {
176 Index::Input(i) => {
177 s.push_str(&format!("`I{}`", &self.inputs[i]));
178 }
179 Index::Aux(i) => {
180 s.push_str(&format!("`A{}`", &self.aux[i]));
181 }
182 }
183 }
184 if is_first {
185 // Nothing was visited, print 0.
186 s.push('0');
187 }
188 s.push(')');
189 };
190
191 for &(ref a, ref b, ref c, ref name) in &self.constraints {
192 s.push('\n');
193
194 s.push_str(&format!("{}: ", name));
195 pp(&mut s, a);
196 s.push_str(" * ");
197 pp(&mut s, b);
198 s.push_str(" = ");
199 pp(&mut s, c);
200 }
201
202 s.push('\n');
203
204 s
205 }
206
207 /// Associate `NamedObject` with `path`.
208 /// `path` must not already have an associated object.
209 fn set_named_obj(&mut self, path: String, to: NamedObject) {
210 assert!(
211 !self.named_objects.contains_key(&path),
212 "tried to create object at existing path: {}",
213 path
214 );
215
216 self.named_objects.insert(path, to);
217 }
218}
219
220impl<G: Group> Default for ShapeCS<G>
221where
222 G::Scalar: PrimeField,
223{
224 fn default() -> Self {
225 let mut map = HashMap::new();
226 map.insert("ONE".into(), NamedObject::Var(ShapeCS::<G>::one()));
227 ShapeCS {
228 named_objects: map,
229 current_namespace: vec![],
230 constraints: vec![],
231 inputs: vec![String::from("ONE")],
232 aux: vec![],
233 }
234 }
235}
236
237impl<G: Group> ConstraintSystem<G::Scalar> for ShapeCS<G>
238where
239 G::Scalar: PrimeField,
240{
241 type Root = Self;
242
243 fn alloc<F, A, AR>(&mut self, annotation: A, _f: F) -> Result<Variable, SynthesisError>
244 where
245 F: FnOnce() -> Result<G::Scalar, SynthesisError>,
246 A: FnOnce() -> AR,
247 AR: Into<String>,
248 {
249 let path = compute_path(&self.current_namespace, &annotation().into());
250 self.aux.push(path);
251
252 Ok(Variable::new_unchecked(Index::Aux(self.aux.len() - 1)))
253 }
254
255 fn alloc_input<F, A, AR>(&mut self, annotation: A, _f: F) -> Result<Variable, SynthesisError>
256 where
257 F: FnOnce() -> Result<G::Scalar, SynthesisError>,
258 A: FnOnce() -> AR,
259 AR: Into<String>,
260 {
261 let path = compute_path(&self.current_namespace, &annotation().into());
262 self.inputs.push(path);
263
264 Ok(Variable::new_unchecked(Index::Input(self.inputs.len() - 1)))
265 }
266
267 fn enforce<A, AR, LA, LB, LC>(&mut self, annotation: A, a: LA, b: LB, c: LC)
268 where
269 A: FnOnce() -> AR,
270 AR: Into<String>,
271 LA: FnOnce(LinearCombination<G::Scalar>) -> LinearCombination<G::Scalar>,
272 LB: FnOnce(LinearCombination<G::Scalar>) -> LinearCombination<G::Scalar>,
273 LC: FnOnce(LinearCombination<G::Scalar>) -> LinearCombination<G::Scalar>,
274 {
275 let path = compute_path(&self.current_namespace, &annotation().into());
276 let index = self.constraints.len();
277 self.set_named_obj(path.clone(), NamedObject::Constraint(index));
278
279 let a = a(LinearCombination::zero());
280 let b = b(LinearCombination::zero());
281 let c = c(LinearCombination::zero());
282
283 self.constraints.push((a, b, c, path));
284 }
285
286 fn push_namespace<NR, N>(&mut self, name_fn: N)
287 where
288 NR: Into<String>,
289 N: FnOnce() -> NR,
290 {
291 let name = name_fn().into();
292 let path = compute_path(&self.current_namespace, &name);
293 self.set_named_obj(path, NamedObject::Namespace);
294 self.current_namespace.push(name);
295 }
296
297 fn pop_namespace(&mut self) {
298 assert!(self.current_namespace.pop().is_some());
299 }
300
301 fn get_root(&mut self) -> &mut Self::Root {
302 self
303 }
304}
305
306fn compute_path(ns: &[String], this: &str) -> String {
307 assert!(
308 !this.chars().any(|a| a == '/'),
309 "'/' is not allowed in names"
310 );
311
312 let mut name = String::new();
313
314 let mut needs_separation = false;
315 for ns in ns.iter().chain(Some(this.to_string()).iter()) {
316 if needs_separation {
317 name += "/";
318 }
319
320 name += ns;
321 needs_separation = true;
322 }
323
324 name
325}