bellpepper_core/
constraint_system.rs

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

bellpepper_core/
constraint_system.rs
