nova_snark/frontend/
constraint_system.rs

1use std::marker::PhantomData;
2
3use ff::PrimeField;
4
5use super::lc::{Index, LinearCombination, Variable};
6
7/// Computations are expressed in terms of arithmetic circuits, in particular
8/// rank-1 quadratic constraint systems. The `Circuit` trait represents a
9/// circuit that can be synthesized. The `synthesize` method is called during
10/// CRS generation and during proving.
11pub trait Circuit<Scalar: PrimeField> {
12  /// Synthesize the circuit into a rank-1 quadratic constraint system.
13  fn synthesize<CS: ConstraintSystem<Scalar>>(self, cs: &mut CS) -> Result<(), SynthesisError>;
14}
15
16/// This is an error that could occur during circuit synthesis contexts,
17/// such as CRS generation, proving or verification.
18#[allow(clippy::upper_case_acronyms)]
19#[derive(thiserror::Error, Debug, Clone)]
20pub enum SynthesisError {
21  /// During synthesis, we lacked knowledge of a variable assignment.
22  #[error("an assignment for a variable could not be computed")]
23  AssignmentMissing,
24  /// During synthesis, we divided by zero.
25  #[error("division by zero")]
26  DivisionByZero,
27  /// During synthesis, we constructed an unsatisfiable constraint system.
28  #[error("unsatisfiable constraint system: {0}")]
29  Unsatisfiable(String),
30  /// During synthesis, our polynomials ended up being too high of degree
31  #[error("polynomial degree is too large")]
32  PolynomialDegreeTooLarge,
33  /// During proof generation, we encountered an identity in the CRS
34  #[error("encountered an identity element in the CRS")]
35  UnexpectedIdentity,
36  /// During verification, our verifying key was malformed.
37  #[error("malformed verifying key")]
38  MalformedVerifyingKey,
39  /// During CRS generation, we observed an unconstrained auxiliary variable
40  #[error("auxiliary variable was unconstrained")]
41  UnconstrainedVariable,
42  /// During GPU multiexp/fft, some GPU related error happened
43  #[error("attempted to aggregate malformed proofs: {0}")]
44  MalformedProofs(String),
45  /// Non power of two proofs given for aggregation
46  #[error("non power of two proofs given for aggregation")]
47  NonPowerOfTwo,
48  /// Incompatible vector length
49  #[error("incompatible vector length: {0}")]
50  IncompatibleLengthVector(String),
51}
52
53/// Represents a constraint system which can have new variables
54/// allocated and constrains between them formed.
55pub trait ConstraintSystem<Scalar: PrimeField>: Sized + Send {
56  /// Represents the type of the "root" of this constraint system
57  /// so that nested namespaces can minimize indirection.
58  type Root: ConstraintSystem<Scalar>;
59
60  /// Create a new empty constraint system
61  fn new() -> Self {
62    unimplemented!(
63            "ConstraintSystem::new must be implemented for extensible types implementing ConstraintSystem"
64        );
65  }
66
67  /// Return the "one" input variable
68  fn one() -> Variable {
69    Variable::new_unchecked(Index::Input(0))
70  }
71
72  /// Allocate a private variable in the constraint system. The provided function is used to
73  /// determine the assignment of the variable. The given `annotation` function is invoked
74  /// in testing contexts in order to derive a unique name for this variable in the current
75  /// namespace.
76  fn alloc<F, A, AR>(&mut self, annotation: A, f: F) -> Result<Variable, SynthesisError>
77  where
78    F: FnOnce() -> Result<Scalar, SynthesisError>,
79    A: FnOnce() -> AR,
80    AR: Into<String>;
81
82  /// Allocate a public variable in the constraint system. The provided function is used to
83  /// determine the assignment of the variable.
84  fn alloc_input<F, A, AR>(&mut self, annotation: A, f: F) -> Result<Variable, SynthesisError>
85  where
86    F: FnOnce() -> Result<Scalar, SynthesisError>,
87    A: FnOnce() -> AR,
88    AR: Into<String>;
89
90  /// Enforce that `A` * `B` = `C`. The `annotation` function is invoked in testing contexts
91  /// in order to derive a unique name for the constraint in the current namespace.
92  fn enforce<A, AR, LA, LB, LC>(&mut self, annotation: A, a: LA, b: LB, c: LC)
93  where
94    A: FnOnce() -> AR,
95    AR: Into<String>,
96    LA: FnOnce(LinearCombination<Scalar>) -> LinearCombination<Scalar>,
97    LB: FnOnce(LinearCombination<Scalar>) -> LinearCombination<Scalar>,
98    LC: FnOnce(LinearCombination<Scalar>) -> LinearCombination<Scalar>;
99
100  /// Create a new (sub)namespace and enter into it. Not intended
101  /// for downstream use; use `namespace` instead.
102  fn push_namespace<NR, N>(&mut self, name_fn: N)
103  where
104    NR: Into<String>,
105    N: FnOnce() -> NR;
106
107  /// Exit out of the existing namespace. Not intended for
108  /// downstream use; use `namespace` instead.
109  fn pop_namespace(&mut self);
110
111  /// Gets the "root" constraint system, bypassing the namespacing.
112  /// Not intended for downstream use; use `namespace` instead.
113  fn get_root(&mut self) -> &mut Self::Root;
114
115  /// Begin a namespace for this constraint system.
116  fn namespace<NR, N>(&mut self, name_fn: N) -> Namespace<'_, Scalar, Self::Root>
117  where
118    NR: Into<String>,
119    N: FnOnce() -> NR,
120  {
121    self.get_root().push_namespace(name_fn);
122
123    Namespace(self.get_root(), Default::default())
124  }
125
126  /// Most implementations of ConstraintSystem are not 'extensible': they won't implement a specialized
127  /// version of `extend` and should therefore also keep the default implementation of `is_extensible`
128  /// so callers which optionally make use of `extend` can know to avoid relying on it when unimplemented.
129  fn is_extensible() -> bool {
130    false
131  }
132
133  /// Extend concatenates thew  `other` constraint systems to the receiver, modifying the receiver, whose
134  /// inputs, allocated variables, and constraints will precede those of the `other` constraint system.
135  /// The primary use case for this is parallel synthesis of circuits which can be decomposed into
136  /// entirely independent sub-circuits. Each can be synthesized in its own thread, then the
137  /// original `ConstraintSystem` can be extended with each, in the same order they would have
138  /// been synthesized sequentially.
139  fn extend(&mut self, _other: &Self) {
140    unimplemented!(
141      "ConstraintSystem::extend must be implemented for types implementing ConstraintSystem"
142    );
143  }
144
145  /// Determines if the current `ConstraintSystem` instance is a witness generator.
146  /// ConstraintSystems that are witness generators need not assemble the actual constraints. Rather, they exist only
147  /// to efficiently create a witness.
148  ///
149  /// # Returns
150  ///
151  /// * `false` - By default, a `ConstraintSystem` is not a witness generator.
152  fn is_witness_generator(&self) -> bool {
153    false
154  }
155
156  /// Extend the inputs of the `ConstraintSystem`.
157  ///
158  /// # Panics
159  ///
160  /// Panics if called on a `ConstraintSystem` that is not a witness generator.
161  fn extend_inputs(&mut self, _new_inputs: &[Scalar]) {
162    assert!(self.is_witness_generator());
163    unimplemented!("ConstraintSystem::extend_inputs must be implemented for witness generators implementing ConstraintSystem")
164  }
165
166  /// Extend the auxiliary inputs of the `ConstraintSystem`.
167  ///
168  /// # Panics
169  ///
170  /// Panics if called on a `ConstraintSystem` that is not a witness generator.
171  fn extend_aux(&mut self, _new_aux: &[Scalar]) {
172    assert!(self.is_witness_generator());
173    unimplemented!("ConstraintSystem::extend_aux must be implemented for witness generators implementing ConstraintSystem")
174  }
175
176  /// Allocate empty space for the auxiliary inputs and the main inputs of the `ConstraintSystem`.
177  ///
178  /// # Panics
179  ///
180  /// Panics if called on a `ConstraintSystem` that is not a witness generator.
181  fn allocate_empty(&mut self, _aux_n: usize, _inputs_n: usize) -> (&mut [Scalar], &mut [Scalar]) {
182    // This method should only ever be called on witness generators.
183    assert!(self.is_witness_generator());
184    unimplemented!("ConstraintSystem::allocate_empty must be implemented for witness generators implementing ConstraintSystem")
185  }
186
187  /// Allocate empty space for the main inputs of the `ConstraintSystem`.
188  ///
189  /// # Panics
190  ///
191  /// Panics if called on a `ConstraintSystem` that is not a witness generator.
192  fn allocate_empty_inputs(&mut self, _n: usize) -> &mut [Scalar] {
193    // This method should only ever be called on witness generators.
194    assert!(self.is_witness_generator());
195    unimplemented!("ConstraintSystem::allocate_empty_inputs must be implemented for witness generators implementing ConstraintSystem")
196  }
197
198  /// Allocate empty space for the auxiliary inputs of the `ConstraintSystem`.
199  ///
200  /// # Panics
201  ///
202  /// Panics if called on a `ConstraintSystem` that is not a witness generator.
203  fn allocate_empty_aux(&mut self, _n: usize) -> &mut [Scalar] {
204    // This method should only ever be called on witness generators.
205    assert!(self.is_witness_generator());
206    unimplemented!("ConstraintSystem::allocate_empty_aux must be implemented for witness generators implementing ConstraintSystem")
207  }
208
209  /// Returns the constraint system's inputs as a slice of `Scalar`s.
210  ///
211  /// # Panics
212  ///
213  /// Panics if called on a `ConstraintSystem` that is not a witness generator.
214  fn inputs_slice(&self) -> &[Scalar] {
215    assert!(self.is_witness_generator());
216    unimplemented!("ConstraintSystem::inputs_slice must be implemented for witness generators implementing ConstraintSystem")
217  }
218
219  /// Returns the constraint system's aux witness as a slice of `Scalar`s.
220  ///
221  /// # Panics
222  ///
223  /// Panics if called on a `ConstraintSystem` that is not a witness generator.
224  fn aux_slice(&self) -> &[Scalar] {
225    assert!(self.is_witness_generator());
226    unimplemented!("ConstraintSystem::aux_slice must be implemented for witness generators implementing ConstraintSystem")
227  }
228}
229
230/// This is a "namespaced" constraint system which borrows a constraint system (pushing
231/// a namespace context) and, when dropped, pops out of the namespace context.
232#[derive(Debug)]
233pub struct Namespace<'a, Scalar: PrimeField, CS: ConstraintSystem<Scalar>>(
234  &'a mut CS,
235  PhantomData<Scalar>,
236);
237
238impl<Scalar: PrimeField, CS: ConstraintSystem<Scalar>> ConstraintSystem<Scalar>
239  for Namespace<'_, Scalar, CS>
240{
241  type Root = CS::Root;
242
243  fn one() -> Variable {
244    CS::one()
245  }
246
247  fn alloc<F, A, AR>(&mut self, annotation: A, f: F) -> Result<Variable, SynthesisError>
248  where
249    F: FnOnce() -> Result<Scalar, SynthesisError>,
250    A: FnOnce() -> AR,
251    AR: Into<String>,
252  {
253    self.0.alloc(annotation, f)
254  }
255
256  fn alloc_input<F, A, AR>(&mut self, annotation: A, f: F) -> Result<Variable, SynthesisError>
257  where
258    F: FnOnce() -> Result<Scalar, SynthesisError>,
259    A: FnOnce() -> AR,
260    AR: Into<String>,
261  {
262    self.0.alloc_input(annotation, f)
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<Scalar>) -> LinearCombination<Scalar>,
270    LB: FnOnce(LinearCombination<Scalar>) -> LinearCombination<Scalar>,
271    LC: FnOnce(LinearCombination<Scalar>) -> LinearCombination<Scalar>,
272  {
273    self.0.enforce(annotation, a, b, c)
274  }
275
276  // Downstream users who use `namespace` will never interact with these
277  // functions and they will never be invoked because the namespace is
278  // never a root constraint system.
279
280  fn push_namespace<NR, N>(&mut self, _: N)
281  where
282    NR: Into<String>,
283    N: FnOnce() -> NR,
284  {
285    panic!("only the root's push_namespace should be called");
286  }
287
288  fn pop_namespace(&mut self) {
289    panic!("only the root's pop_namespace should be called");
290  }
291
292  fn get_root(&mut self) -> &mut Self::Root {
293    self.0.get_root()
294  }
295
296  fn is_witness_generator(&self) -> bool {
297    self.0.is_witness_generator()
298  }
299
300  fn extend_inputs(&mut self, new_inputs: &[Scalar]) {
301    self.0.extend_inputs(new_inputs)
302  }
303
304  fn extend_aux(&mut self, new_aux: &[Scalar]) {
305    self.0.extend_aux(new_aux)
306  }
307
308  fn allocate_empty(&mut self, aux_n: usize, inputs_n: usize) -> (&mut [Scalar], &mut [Scalar]) {
309    self.0.allocate_empty(aux_n, inputs_n)
310  }
311
312  fn inputs_slice(&self) -> &[Scalar] {
313    self.0.inputs_slice()
314  }
315  fn aux_slice(&self) -> &[Scalar] {
316    self.0.aux_slice()
317  }
318}
319
320impl<Scalar: PrimeField, CS: ConstraintSystem<Scalar>> Drop for Namespace<'_, Scalar, CS> {
321  fn drop(&mut self) {
322    self.get_root().pop_namespace()
323  }
324}
325
326/// Convenience implementation of `ConstraintSystem<Scalar>` for mutable references to
327/// constraint systems.
328impl<Scalar: PrimeField, CS: ConstraintSystem<Scalar>> ConstraintSystem<Scalar> for &'_ mut CS {
329  type Root = CS::Root;
330
331  fn one() -> Variable {
332    CS::one()
333  }
334
335  fn alloc<F, A, AR>(&mut self, annotation: A, f: F) -> Result<Variable, SynthesisError>
336  where
337    F: FnOnce() -> Result<Scalar, SynthesisError>,
338    A: FnOnce() -> AR,
339    AR: Into<String>,
340  {
341    (**self).alloc(annotation, f)
342  }
343
344  fn alloc_input<F, A, AR>(&mut self, annotation: A, f: F) -> Result<Variable, SynthesisError>
345  where
346    F: FnOnce() -> Result<Scalar, SynthesisError>,
347    A: FnOnce() -> AR,
348    AR: Into<String>,
349  {
350    (**self).alloc_input(annotation, f)
351  }
352
353  fn enforce<A, AR, LA, LB, LC>(&mut self, annotation: A, a: LA, b: LB, c: LC)
354  where
355    A: FnOnce() -> AR,
356    AR: Into<String>,
357    LA: FnOnce(LinearCombination<Scalar>) -> LinearCombination<Scalar>,
358    LB: FnOnce(LinearCombination<Scalar>) -> LinearCombination<Scalar>,
359    LC: FnOnce(LinearCombination<Scalar>) -> LinearCombination<Scalar>,
360  {
361    (**self).enforce(annotation, a, b, c)
362  }
363
364  fn push_namespace<NR, N>(&mut self, name_fn: N)
365  where
366    NR: Into<String>,
367    N: FnOnce() -> NR,
368  {
369    (**self).push_namespace(name_fn)
370  }
371
372  fn pop_namespace(&mut self) {
373    (**self).pop_namespace()
374  }
375
376  fn get_root(&mut self) -> &mut Self::Root {
377    (**self).get_root()
378  }
379
380  fn namespace<NR, N>(&mut self, name_fn: N) -> Namespace<'_, Scalar, Self::Root>
381  where
382    NR: Into<String>,
383    N: FnOnce() -> NR,
384  {
385    (**self).namespace(name_fn)
386  }
387
388  fn is_extensible() -> bool {
389    CS::is_extensible()
390  }
391
392  fn extend(&mut self, other: &Self) {
393    (**self).extend(other)
394  }
395
396  fn is_witness_generator(&self) -> bool {
397    (**self).is_witness_generator()
398  }
399
400  fn extend_inputs(&mut self, new_inputs: &[Scalar]) {
401    (**self).extend_inputs(new_inputs)
402  }
403
404  fn extend_aux(&mut self, new_aux: &[Scalar]) {
405    (**self).extend_aux(new_aux)
406  }
407
408  fn allocate_empty(&mut self, aux_n: usize, inputs_n: usize) -> (&mut [Scalar], &mut [Scalar]) {
409    (**self).allocate_empty(aux_n, inputs_n)
410  }
411
412  fn allocate_empty_inputs(&mut self, n: usize) -> &mut [Scalar] {
413    (**self).allocate_empty_inputs(n)
414  }
415
416  fn allocate_empty_aux(&mut self, n: usize) -> &mut [Scalar] {
417    (**self).allocate_empty_aux(n)
418  }
419
420  fn inputs_slice(&self) -> &[Scalar] {
421    (**self).inputs_slice()
422  }
423
424  fn aux_slice(&self) -> &[Scalar] {
425    (**self).aux_slice()
426  }
427}
nova_snark/frontend/constraint_system.rs

nova_snark/frontend/
constraint_system.rs
