snarkvm_circuit_environment/helpers/
r1cs.rs

1// Copyright (c) 2019-2025 Provable Inc.
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::{
17    helpers::{Constraint, Counter},
18    prelude::*,
19};
20use snarkvm_fields::PrimeField;
21
22#[cfg(feature = "save_r1cs_hashes")]
23use sha2::{Digest, Sha256};
24use std::sync::Arc;
25#[cfg(feature = "save_r1cs_hashes")]
26use std::{
27    hash::{Hash, Hasher},
28    sync::Mutex,
29};
30
31#[cfg(feature = "save_r1cs_hashes")]
32struct Sha256Hasher(Sha256);
33
34#[cfg(feature = "save_r1cs_hashes")]
35impl Hasher for Sha256Hasher {
36    fn write(&mut self, bytes: &[u8]) {
37        self.0.update(bytes);
38    }
39
40    fn finish(&self) -> u64 {
41        unimplemented!("Use Digest::finalize instead to get the full SHA-256 digest");
42    }
43}
44
45#[cfg(feature = "save_r1cs_hashes")]
46fn hash_to_sha256<T: Hash>(t: &T) -> [u8; 32] {
47    let mut hasher = Sha256Hasher(Sha256::new());
48    t.hash(&mut hasher);
49    hasher.0.finalize().into()
50}
51
52pub type Scope = String;
53
54/// A list of hashes of all the R1CS objects that have reached the
55/// conversion to Assignment stage. It's a vector in case there are
56/// any duplicates (which could indicate no change or redundant
57/// work) and since they need to eventually be sorted in order to
58/// have deterministic order, as they may be created in parallel.
59#[cfg(feature = "save_r1cs_hashes")]
60pub static R1CS_HASHES: Mutex<Vec<[u8; 32]>> = Mutex::new(Vec::new());
61
62#[derive(Debug, Hash)]
63pub struct R1CS<F: PrimeField> {
64    constants: Vec<Variable<F>>,
65    pub(crate) public: Vec<Variable<F>>,
66    pub(crate) private: Vec<Variable<F>>,
67    pub(crate) constraints: Vec<Arc<Constraint<F>>>,
68    counter: Counter<F>,
69    pub(crate) num_variables: u64,
70    nonzeros: (u64, u64, u64),
71}
72
73impl<F: PrimeField> R1CS<F> {
74    /// Returns a new instance of a constraint system.
75    pub(crate) fn new() -> Self {
76        Self {
77            constants: Default::default(),
78            public: vec![Variable::Public(Arc::new((0u64, F::one())))],
79            private: Default::default(),
80            constraints: Default::default(),
81            counter: Default::default(),
82            num_variables: 1u64,
83            nonzeros: (0, 0, 0),
84        }
85    }
86
87    /// Appends the given scope to the current environment.
88    pub(crate) fn push_scope<S: Into<String>>(&mut self, name: S) -> Result<(), String> {
89        self.counter.push(name)
90    }
91
92    /// Removes the given scope from the current environment.
93    pub(crate) fn pop_scope<S: Into<String>>(&mut self, name: S) -> Result<(), String> {
94        self.counter.pop(name)
95    }
96
97    /// Returns a new constant with the given value and scope.
98    pub(crate) fn new_constant(&mut self, value: F) -> Variable<F> {
99        let variable = Variable::Constant(Arc::new(value));
100        self.constants.push(variable.clone());
101        self.counter.increment_constant();
102        self.num_variables += 1;
103        variable
104    }
105
106    /// Returns a new public variable with the given value and scope.
107    pub(crate) fn new_public(&mut self, value: F) -> Variable<F> {
108        let variable = Variable::Public(Arc::new((self.public.len() as u64, value)));
109        self.public.push(variable.clone());
110        self.counter.increment_public();
111        self.num_variables += 1;
112        variable
113    }
114
115    /// Returns a new private variable with the given value and scope.
116    pub(crate) fn new_private(&mut self, value: F) -> Variable<F> {
117        let variable = Variable::Private(Arc::new((self.private.len() as u64, value)));
118        self.private.push(variable.clone());
119        self.counter.increment_private();
120        self.num_variables += 1;
121        variable
122    }
123
124    /// Adds one constraint enforcing that `(A * B) == C`.
125    pub(crate) fn enforce(&mut self, constraint: Constraint<F>) {
126        let (a_nonzeros, b_nonzeros, c_nonzeros) = constraint.num_nonzeros();
127        self.nonzeros.0 += a_nonzeros;
128        self.nonzeros.1 += b_nonzeros;
129        self.nonzeros.2 += c_nonzeros;
130
131        let constraint = Arc::new(constraint);
132        self.constraints.push(Arc::clone(&constraint));
133        self.counter.add_constraint(constraint);
134    }
135
136    /// Returns `true` if all of the constraints are satisfied.
137    ///
138    /// In addition, when in debug mode, this function also checks that
139    /// all constraints use variables corresponding to the declared variables.
140    pub fn is_satisfied(&self) -> bool {
141        // Ensure all constraints are satisfied.
142        let constraints_satisfied = self.constraints.iter().all(|constraint| constraint.is_satisfied());
143        if !constraints_satisfied {
144            return false;
145        }
146
147        // In debug mode, ensure all constraints use variables corresponding to the declared variables.
148        #[cfg(not(debug_assertions))]
149        return true;
150        #[cfg(debug_assertions)]
151        self.constraints.iter().all(|constraint| {
152            let (a, b, c) = constraint.to_terms();
153            [a, b, c].into_iter().all(|lc| {
154                lc.to_terms().iter().all(|(variable, _)| match variable {
155                    Variable::Constant(_value) => false, // terms should not contain Constants
156                    Variable::Private(private) => {
157                        let (index, value) = private.as_ref();
158                        self.private.get(*index as usize).map_or_else(|| false, |v| v.value() == *value)
159                    }
160                    Variable::Public(public) => {
161                        let (index, value) = public.as_ref();
162                        self.public.get(*index as usize).map_or_else(|| false, |v| v.value() == *value)
163                    }
164                })
165            })
166        })
167    }
168
169    /// Returns `true` if all constraints in the current scope are satisfied.
170    pub(crate) fn is_satisfied_in_scope(&self) -> bool {
171        self.counter.is_satisfied_in_scope()
172    }
173
174    /// Returns the current scope.
175    pub(crate) fn scope(&self) -> Scope {
176        self.counter.scope()
177    }
178
179    /// Returns the number of constants in the constraint system.
180    pub fn num_constants(&self) -> u64 {
181        self.constants.len() as u64
182    }
183
184    /// Returns the number of public variables in the constraint system.
185    pub fn num_public(&self) -> u64 {
186        self.public.len() as u64
187    }
188
189    /// Returns the number of private variables in the constraint system.
190    pub fn num_private(&self) -> u64 {
191        self.private.len() as u64
192    }
193
194    /// Returns the number of constant, public, and private variables in the constraint system.
195    pub fn num_variables(&self) -> u64 {
196        self.num_variables
197    }
198
199    /// Returns the number of constraints in the constraint system.
200    pub fn num_constraints(&self) -> u64 {
201        self.constraints.len() as u64
202    }
203
204    /// Returns the number of nonzeros in the constraint system.
205    pub fn num_nonzeros(&self) -> (u64, u64, u64) {
206        self.nonzeros
207    }
208
209    /// Returns the number of constants for the current scope.
210    pub(crate) fn num_constants_in_scope(&self) -> u64 {
211        self.counter.num_constants_in_scope()
212    }
213
214    /// Returns the number of public variables for the current scope.
215    pub(crate) fn num_public_in_scope(&self) -> u64 {
216        self.counter.num_public_in_scope()
217    }
218
219    /// Returns the number of private variables for the current scope.
220    pub(crate) fn num_private_in_scope(&self) -> u64 {
221        self.counter.num_private_in_scope()
222    }
223
224    /// Returns the number of constraints for the current scope.
225    pub(crate) fn num_constraints_in_scope(&self) -> u64 {
226        self.counter.num_constraints_in_scope()
227    }
228
229    /// Returns the number of nonzeros for the current scope.
230    pub(crate) fn num_nonzeros_in_scope(&self) -> (u64, u64, u64) {
231        self.counter.num_nonzeros_in_scope()
232    }
233
234    /// Returns the public variables in the constraint system.
235    pub fn to_public_variables(&self) -> &Vec<Variable<F>> {
236        &self.public
237    }
238
239    /// Returns the private variables in the constraint system.
240    pub fn to_private_variables(&self) -> &Vec<Variable<F>> {
241        &self.private
242    }
243
244    /// Returns the constraints in the constraint system.
245    pub fn to_constraints(&self) -> &Vec<Arc<Constraint<F>>> {
246        &self.constraints
247    }
248
249    /// Register the current hash of the entire R1CS and add
250    /// it to the R1CS_HASHES collection.
251    #[cfg(feature = "save_r1cs_hashes")]
252    pub(crate) fn save_hash(&self) {
253        let r1cs_hash = hash_to_sha256(self);
254        R1CS_HASHES.lock().unwrap().push(r1cs_hash);
255    }
256}
257
258impl<F: PrimeField> Display for R1CS<F> {
259    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
260        let mut output = String::default();
261        for constraint in self.to_constraints() {
262            output += &constraint.to_string();
263        }
264        output += "\n";
265
266        write!(f, "{output}")
267    }
268}
snarkvm_circuit_environment/helpers/r1cs.rs

snarkvm_circuit_environment/helpers/
r1cs.rs
