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