snarkvm_circuit_environment/helpers/
assignment.rs

1// Copyright 2024 Aleo Network Foundation
2// This file is part of the snarkVM library.
3
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at:
7
8// http://www.apache.org/licenses/LICENSE-2.0
9
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16use crate::Index;
17use snarkvm_fields::PrimeField;
18
19use indexmap::IndexMap;
20use std::sync::Arc;
21
22#[derive(Clone, Debug, PartialEq, Eq, Hash)]
23pub enum AssignmentVariable<F: PrimeField> {
24    Constant(F),
25    Public(Index),
26    Private(Index),
27}
28
29impl<F: PrimeField> From<&crate::Variable<F>> for AssignmentVariable<F> {
30    /// Converts a variable to an assignment variable.
31    fn from(variable: &crate::Variable<F>) -> Self {
32        match variable {
33            crate::Variable::Constant(value) => Self::Constant(**value),
34            crate::Variable::Public(index_value) => {
35                let (index, _value) = index_value.as_ref();
36                Self::Public(*index)
37            }
38            crate::Variable::Private(index_value) => {
39                let (index, _value) = index_value.as_ref();
40                Self::Private(*index)
41            }
42        }
43    }
44}
45
46#[derive(Clone, Debug)]
47pub struct AssignmentLC<F: PrimeField> {
48    constant: F,
49    terms: Vec<(AssignmentVariable<F>, F)>,
50}
51
52impl<F: PrimeField> From<&crate::LinearCombination<F>> for AssignmentLC<F> {
53    /// Converts a linear combination to an assignment linear combination.
54    fn from(lc: &crate::LinearCombination<F>) -> Self {
55        Self {
56            constant: lc.to_constant(),
57            terms: FromIterator::from_iter(
58                lc.to_terms().iter().map(|(variable, coefficient)| (variable.into(), *coefficient)),
59            ),
60        }
61    }
62}
63
64impl<F: PrimeField> AssignmentLC<F> {
65    /// Returns the constant term of the linear combination.
66    pub const fn constant(&self) -> F {
67        self.constant
68    }
69
70    /// Returns the terms of the linear combination.
71    pub const fn terms(&self) -> &Vec<(AssignmentVariable<F>, F)> {
72        &self.terms
73    }
74
75    /// Returns the number of nonzeros in the linear combination.
76    pub(super) fn num_nonzeros(&self) -> u64 {
77        // Increment by one if the constant is nonzero.
78        match self.constant.is_zero() {
79            true => self.terms.len() as u64,
80            false => (self.terms.len() as u64).saturating_add(1),
81        }
82    }
83}
84
85/// A struct that contains public variable assignments, private variable assignments,
86/// and constraint assignments.
87#[derive(Clone, Debug)]
88pub struct Assignment<F: PrimeField> {
89    /// The public variables.
90    public: Arc<[(Index, F)]>,
91    /// The private variables.
92    private: Arc<[(Index, F)]>,
93    /// The constraints.
94    constraints: Arc<[(AssignmentLC<F>, AssignmentLC<F>, AssignmentLC<F>)]>,
95    /// The number of constants, public, and private variables in the assignment.
96    num_variables: u64,
97}
98
99impl<F: PrimeField> From<crate::R1CS<F>> for Assignment<F> {
100    /// Converts an R1CS to an assignment.
101    fn from(r1cs: crate::R1CS<F>) -> Self {
102        Self {
103            public: FromIterator::from_iter(
104                r1cs.to_public_variables().iter().map(|variable| (variable.index(), variable.value())),
105            ),
106            private: FromIterator::from_iter(
107                r1cs.to_private_variables().iter().map(|variable| (variable.index(), variable.value())),
108            ),
109            constraints: FromIterator::from_iter(r1cs.to_constraints().iter().map(|constraint| {
110                let (a, b, c) = constraint.to_terms();
111                (a.into(), b.into(), c.into())
112            })),
113            num_variables: r1cs.num_variables(),
114        }
115    }
116}
117
118impl<F: PrimeField> Assignment<F> {
119    /// Returns the public inputs of the assignment.
120    pub const fn public_inputs(&self) -> &Arc<[(Index, F)]> {
121        &self.public
122    }
123
124    /// Returns the private inputs of the assignment.
125    pub const fn private_inputs(&self) -> &Arc<[(Index, F)]> {
126        &self.private
127    }
128
129    /// Returns the constraints of the assignment.
130    pub const fn constraints(&self) -> &Arc<[(AssignmentLC<F>, AssignmentLC<F>, AssignmentLC<F>)]> {
131        &self.constraints
132    }
133
134    /// Returns the number of public variables in the assignment.
135    pub fn num_public(&self) -> u64 {
136        self.public.len() as u64
137    }
138
139    /// Returns the number of private variables in the assignment.
140    pub fn num_private(&self) -> u64 {
141        self.private.len() as u64
142    }
143
144    /// Returns the number of constants, public, and private variables in the assignment.
145    pub fn num_variables(&self) -> u64 {
146        self.num_variables
147    }
148
149    /// Returns the number of constraints in the assignment.
150    pub fn num_constraints(&self) -> u64 {
151        self.constraints.len() as u64
152    }
153
154    /// Returns the number of nonzeros in the assignment.
155    pub fn num_nonzeros(&self) -> (u64, u64, u64) {
156        self.constraints
157            .iter()
158            .map(|(a, b, c)| (a.num_nonzeros(), b.num_nonzeros(), c.num_nonzeros()))
159            .fold((0, 0, 0), |(a, b, c), (x, y, z)| (a.saturating_add(x), b.saturating_add(y), c.saturating_add(z)))
160    }
161}
162
163impl<F: PrimeField> snarkvm_algorithms::r1cs::ConstraintSynthesizer<F> for Assignment<F> {
164    /// Synthesizes the constraints from the environment into a `snarkvm_algorithms::r1cs`-compliant constraint system.
165    fn generate_constraints<CS: snarkvm_algorithms::r1cs::ConstraintSystem<F>>(
166        &self,
167        cs: &mut CS,
168    ) -> Result<(), snarkvm_algorithms::r1cs::SynthesisError> {
169        /// A struct for tracking the mapping of variables from the virtual machine (first) to the gadget constraint system (second).
170        struct Converter {
171            public: IndexMap<u64, snarkvm_algorithms::r1cs::Variable>,
172            private: IndexMap<u64, snarkvm_algorithms::r1cs::Variable>,
173        }
174
175        let mut converter = Converter { public: Default::default(), private: Default::default() };
176
177        // Ensure the given `cs` is starting off clean.
178        assert_eq!(1, cs.num_public_variables());
179        assert_eq!(0, cs.num_private_variables());
180        assert_eq!(0, cs.num_constraints());
181
182        let result = converter.public.insert(0, CS::one());
183        assert!(result.is_none(), "Overwrote an existing public variable in the converter");
184
185        // Allocate the public variables.
186        // NOTE: we skip the first public `One` variable because we already allocated it in the `ConstraintSystem` constructor.
187        for (i, (index, value)) in self.public.iter().skip(1).enumerate() {
188            assert_eq!((i + 1) as u64, *index, "Public vars in first system must be processed in lexicographic order");
189
190            let gadget = cs.alloc_input(|| format!("Public {i}"), || Ok(*value))?;
191
192            assert_eq!(
193                snarkvm_algorithms::r1cs::Index::Public(*index as usize),
194                gadget.get_unchecked(),
195                "Public variables in the second system must match the first system (with an off-by-1 for the public case)"
196            );
197
198            let result = converter.public.insert(*index, gadget);
199
200            assert!(result.is_none(), "Overwrote an existing public variable in the converter");
201        }
202
203        // Allocate the private variables.
204        for (i, (index, value)) in self.private.iter().enumerate() {
205            assert_eq!(i as u64, *index, "Private variables in first system must be processed in lexicographic order");
206
207            let gadget = cs.alloc(|| format!("Private {i}"), || Ok(*value))?;
208
209            assert_eq!(
210                snarkvm_algorithms::r1cs::Index::Private(i),
211                gadget.get_unchecked(),
212                "Private variables in the second system must match the first system"
213            );
214
215            let result = converter.private.insert(*index, gadget);
216
217            assert!(result.is_none(), "Overwrote an existing private variable in the converter");
218        }
219
220        // Enforce all of the constraints.
221        for (i, (a, b, c)) in self.constraints.iter().enumerate() {
222            // Converts terms from one linear combination in the first system to the second system.
223            let convert_linear_combination = |lc: &AssignmentLC<F>| -> snarkvm_algorithms::r1cs::LinearCombination<F> {
224                // Initialize a linear combination for the second system.
225                let mut linear_combination = snarkvm_algorithms::r1cs::LinearCombination::<F>::zero();
226
227                // Process every term in the linear combination.
228                for (variable, coefficient) in lc.terms.iter() {
229                    match variable {
230                        AssignmentVariable::Constant(_) => {
231                            unreachable!(
232                                "Failed during constraint translation. The first system by definition cannot have constant variables in the terms"
233                            )
234                        }
235                        AssignmentVariable::Public(index) => {
236                            let gadget = converter.public.get(index).unwrap();
237                            assert_eq!(
238                                snarkvm_algorithms::r1cs::Index::Public(*index as usize),
239                                gadget.get_unchecked(),
240                                "Failed during constraint translation. The public variable in the second system must match the first system (with an off-by-1 for the public case)"
241                            );
242                            linear_combination += (*coefficient, *gadget);
243                        }
244                        AssignmentVariable::Private(index) => {
245                            let gadget = converter.private.get(index).unwrap();
246                            assert_eq!(
247                                snarkvm_algorithms::r1cs::Index::Private(*index as usize),
248                                gadget.get_unchecked(),
249                                "Failed during constraint translation. The private variable in the second system must match the first system"
250                            );
251                            linear_combination += (*coefficient, *gadget);
252                        }
253                    }
254                }
255
256                // Finally, add the accumulated constant value to the linear combination.
257                if !lc.constant.is_zero() {
258                    linear_combination += (
259                        lc.constant,
260                        snarkvm_algorithms::r1cs::Variable::new_unchecked(snarkvm_algorithms::r1cs::Index::Public(0)),
261                    );
262                }
263
264                // Return the linear combination of the second system.
265                linear_combination
266            };
267
268            cs.enforce(
269                || format!("Constraint {i}"),
270                |lc| lc + convert_linear_combination(a),
271                |lc| lc + convert_linear_combination(b),
272                |lc| lc + convert_linear_combination(c),
273            );
274        }
275
276        // Ensure the given `cs` matches in size with the first system.
277        assert_eq!(self.num_public(), cs.num_public_variables() as u64);
278        assert_eq!(self.num_private(), cs.num_private_variables() as u64);
279        assert_eq!(self.num_constraints(), cs.num_constraints() as u64);
280
281        Ok(())
282    }
283}
284
285#[cfg(test)]
286mod tests {
287    use snarkvm_algorithms::{AlgebraicSponge, SNARK, r1cs::ConstraintSynthesizer};
288    use snarkvm_circuit::prelude::*;
289    use snarkvm_curves::bls12_377::Fr;
290
291    /// Compute 2^EXPONENT - 1, in a purposefully constraint-inefficient manner for testing.
292    fn create_example_circuit<E: Environment>() -> Field<E> {
293        let one = snarkvm_console_types::Field::<E::Network>::one();
294        let two = one + one;
295
296        const EXPONENT: u64 = 64;
297
298        // Compute 2^EXPONENT - 1, in a purposefully constraint-inefficient manner for testing.
299        let mut candidate = Field::<E>::new(Mode::Public, one);
300        let mut accumulator = Field::new(Mode::Private, two);
301        for _ in 0..EXPONENT {
302            candidate += &accumulator;
303            accumulator *= Field::new(Mode::Private, two);
304        }
305
306        assert_eq!((accumulator - Field::one()).eject_value(), candidate.eject_value());
307        assert_eq!(2, E::num_public());
308        assert_eq!(2 * EXPONENT + 1, E::num_private());
309        assert_eq!(EXPONENT, E::num_constraints());
310        assert!(E::is_satisfied());
311
312        candidate
313    }
314
315    #[test]
316    fn test_constraint_converter() {
317        let _candidate_output = create_example_circuit::<Circuit>();
318        let assignment = Circuit::eject_assignment_and_reset();
319        assert_eq!(0, Circuit::num_constants());
320        assert_eq!(1, Circuit::num_public());
321        assert_eq!(0, Circuit::num_private());
322        assert_eq!(0, Circuit::num_constraints());
323
324        let mut cs = snarkvm_algorithms::r1cs::TestConstraintSystem::new();
325        assignment.generate_constraints(&mut cs).unwrap();
326        {
327            use snarkvm_algorithms::r1cs::ConstraintSystem;
328            assert_eq!(assignment.num_public(), cs.num_public_variables() as u64);
329            assert_eq!(assignment.num_private(), cs.num_private_variables() as u64);
330            assert_eq!(assignment.num_constraints(), cs.num_constraints() as u64);
331            assert!(cs.is_satisfied());
332        }
333    }
334
335    #[test]
336    fn test_varuna() {
337        let _candidate_output = create_example_circuit::<Circuit>();
338        let assignment = Circuit::eject_assignment_and_reset();
339        assert_eq!(0, Circuit::num_constants());
340        assert_eq!(1, Circuit::num_public());
341        assert_eq!(0, Circuit::num_private());
342        assert_eq!(0, Circuit::num_constraints());
343
344        // Varuna setup, prove, and verify.
345
346        use snarkvm_algorithms::{
347            crypto_hash::PoseidonSponge,
348            snark::varuna::{VarunaHidingMode, VarunaSNARK, ahp::AHPForR1CS},
349        };
350        use snarkvm_curves::bls12_377::{Bls12_377, Fq};
351        use snarkvm_utilities::rand::TestRng;
352
353        type FS = PoseidonSponge<Fq, 2, 1>;
354        type VarunaInst = VarunaSNARK<Bls12_377, FS, VarunaHidingMode>;
355
356        let rng = &mut TestRng::default();
357
358        let max_degree = AHPForR1CS::<Fr, VarunaHidingMode>::max_degree(200, 200, 300).unwrap();
359        let universal_srs = VarunaInst::universal_setup(max_degree).unwrap();
360        let universal_prover = &universal_srs.to_universal_prover().unwrap();
361        let universal_verifier = &universal_srs.to_universal_verifier().unwrap();
362        let fs_pp = FS::sample_parameters();
363
364        let (index_pk, index_vk) = VarunaInst::circuit_setup(&universal_srs, &assignment).unwrap();
365        println!("Called circuit setup");
366
367        let proof = VarunaInst::prove(universal_prover, &fs_pp, &index_pk, &assignment, rng).unwrap();
368        println!("Called prover");
369
370        let one = <Circuit as Environment>::BaseField::one();
371        assert!(VarunaInst::verify(universal_verifier, &fs_pp, &index_vk, [one, one], &proof).unwrap());
372        println!("Called verifier");
373        println!("\nShould not verify (i.e. verifier messages should print below):");
374        assert!(!VarunaInst::verify(universal_verifier, &fs_pp, &index_vk, [one, one + one], &proof).unwrap());
375    }
376}
snarkvm_circuit_environment/helpers/assignment.rs

snarkvm_circuit_environment/helpers/
assignment.rs
