noah_bulletproofs/r1cs/
constraint_system.rs

1//! Definition of the constraint system trait.
2
3use super::{LinearCombination, R1CSError, Variable};
4use curve25519_dalek::scalar::Scalar;
5use merlin::Transcript;
6
7/// The interface for a constraint system, abstracting over the prover
8/// and verifier's roles.
9///
10/// Statements to be proved by an [`R1CSProof`](::r1cs::R1CSProof) are specified by
11/// programmatically constructing constraints.  These constraints need
12/// to be identical between the prover and verifier, since the prover
13/// and verifier need to construct the same statement.
14///
15/// To prevent code duplication or mismatches between the prover and
16/// verifier, gadgets for the constraint system should be written
17/// using the `ConstraintSystem` trait, so that the prover and
18/// verifier share the logic for specifying constraints.
19pub trait ConstraintSystem {
20    /// Leases the proof transcript to the user, so they can
21    /// add extra data to which the proof must be bound, but which
22    /// is not available before creation of the constraint system.
23    fn transcript(&mut self) -> &mut Transcript;
24
25    /// Allocate and constrain multiplication variables.
26    ///
27    /// Allocate variables `left`, `right`, and `out`
28    /// with the implicit constraint that
29    /// ```text
30    /// left * right = out
31    /// ```
32    /// and add the explicit constraints that
33    /// ```text
34    /// left = left_constraint
35    /// right = right_constraint
36    /// ```
37    ///
38    /// Returns `(left, right, out)` for use in further constraints.
39    fn multiply(
40        &mut self,
41        left: LinearCombination,
42        right: LinearCombination,
43    ) -> (Variable, Variable, Variable);
44
45    /// Allocate a single variable.
46    ///
47    /// This either allocates a new multiplier and returns its `left` variable,
48    /// or returns a `right` variable of a multiplier previously allocated by this method.
49    /// The output of a multiplier is assigned on a even call, when `right` is assigned.
50    ///
51    /// When CS is committed at the end of the first or second phase, the half-assigned multiplier
52    /// has the `right` assigned to zero and all its variables committed.
53    ///
54    /// Returns unconstrained `Variable` for use in further constraints.
55    fn allocate(&mut self, assignment: Option<Scalar>) -> Result<Variable, R1CSError>;
56
57    /// Allocate variables `left`, `right`, and `out`
58    /// with the implicit constraint that
59    /// ```text
60    /// left * right = out
61    /// ```
62    ///
63    /// Returns `(left, right, out)` for use in further constraints.
64    fn allocate_multiplier(
65        &mut self,
66        input_assignments: Option<(Scalar, Scalar)>,
67    ) -> Result<(Variable, Variable, Variable), R1CSError>;
68
69    /// Counts the amount of allocated multipliers.
70    fn multipliers_len(&self) -> usize;
71
72    /// Enforce the explicit constraint that
73    /// ```text
74    /// lc = 0
75    /// ```
76    fn constrain(&mut self, lc: LinearCombination);
77}
78
79/// An extension to the constraint system trait that permits randomized constraints.
80/// Gadgets that do not use randomization should use trait bound `CS: ConstraintSystem`,
81/// while gadgets that need randomization should use trait bound `CS: RandomizedConstraintSystem`.
82/// Gadgets generally _should not_ use this trait as a bound on the CS argument: it should be used
83/// by the higher-order protocol that composes gadgets together.
84pub trait RandomizableConstraintSystem: ConstraintSystem {
85    /// Represents a concrete type for the CS in a randomization phase.
86    type RandomizedCS: RandomizedConstraintSystem;
87
88    /// Specify additional variables and constraints randomized using a challenge scalar
89    /// bound to the assignments of the non-randomized variables.
90    ///
91    /// If the constraint system’s low-level variables have not been committed yet,
92    /// the call returns `Ok()` and saves a callback until later.
93    ///
94    /// If the constraint system’s low-level variables are committed already,
95    /// the callback is invoked immediately and its result is return from this method.
96    ///
97    /// ### Usage
98    ///
99    /// Inside the closure you can generate one or more challenges using `challenge_scalar` method.
100    ///
101    /// ```text
102    /// cs.specify_randomized_constraints(move |cs| {
103    ///     let z = cs.challenge_scalar(b"some challenge");
104    ///     // ...
105    /// })
106    /// ```
107    fn specify_randomized_constraints<F>(&mut self, callback: F) -> Result<(), R1CSError>
108    where
109        F: 'static + Fn(&mut Self::RandomizedCS) -> Result<(), R1CSError>;
110}
111
112/// Represents a constraint system in the second phase:
113/// when the challenges can be sampled to create randomized constraints.
114///
115/// Note: this trait also includes `ConstraintSystem` trait
116/// in order to allow composition of gadgets: e.g. a shuffle gadget can be used in both phases.
117pub trait RandomizedConstraintSystem: ConstraintSystem {
118    /// Generates a challenge scalar.
119    ///
120    /// ### Usage
121    ///
122    /// This method is available only within the scope of a closure provided
123    /// to `specify_randomized_constraints`, which implements
124    /// the "randomization" phase of the protocol.
125    ///
126    /// Arbitrary number of challenges can be generated with additional calls.
127    ///
128    /// ```text
129    /// cs.specify_randomized_constraints(move |cs| {
130    ///     let z = cs.challenge_scalar(b"some challenge");
131    ///     // ...
132    /// })
133    /// ```
134    fn challenge_scalar(&mut self, label: &'static [u8]) -> Scalar;
135}
noah_bulletproofs/r1cs/constraint_system.rs

noah_bulletproofs/r1cs/
constraint_system.rs
