Nova/src/r1cs.rs
src/r1cs.rsRaw
1//! This module defines R1CS related types and a folding scheme for Relaxed R1CS
2#![allow(clippy::type_complexity)]
3use crate::{
4 constants::{BN_LIMB_WIDTH, BN_N_LIMBS},
5 errors::NovaError,
6 gadgets::{
7 nonnative::{bignat::nat_to_limbs, util::f_to_nat},
8 utils::scalar_as_base,
9 },
10 traits::{
11 commitment::CommitmentEngineTrait, AbsorbInROTrait, Group, ROTrait, TranscriptReprTrait,
12 },
13 Commitment, CommitmentKey, CE,
14};
15use core::{cmp::max, marker::PhantomData};
16use ff::Field;
17use itertools::concat;
18use rayon::prelude::*;
19use serde::{Deserialize, Serialize};
20
21/// Public parameters for a given R1CS
22#[derive(Clone, Serialize, Deserialize)]
23#[serde(bound = "")]
24pub struct R1CS<G: Group> {
25 _p: PhantomData<G>,
26}
27
28/// A type that holds the shape of the R1CS matrices
29#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
30pub struct R1CSShape<G: Group> {
31 pub(crate) num_cons: usize,
32 pub(crate) num_vars: usize,
33 pub(crate) num_io: usize,
34 pub(crate) A: Vec<(usize, usize, G::Scalar)>,
35 pub(crate) B: Vec<(usize, usize, G::Scalar)>,
36 pub(crate) C: Vec<(usize, usize, G::Scalar)>,
37}
38
39/// A type that holds a witness for a given R1CS instance
40#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
41pub struct R1CSWitness<G: Group> {
42 W: Vec<G::Scalar>,
43}
44
45/// A type that holds an R1CS instance
46#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
47#[serde(bound = "")]
48pub struct R1CSInstance<G: Group> {
49 pub(crate) comm_W: Commitment<G>,
50 pub(crate) X: Vec<G::Scalar>,
51}
52
53/// A type that holds a witness for a given Relaxed R1CS instance
54#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
55pub struct RelaxedR1CSWitness<G: Group> {
56 pub(crate) W: Vec<G::Scalar>,
57 pub(crate) E: Vec<G::Scalar>,
58}
59
60/// A type that holds a Relaxed R1CS instance
61#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
62#[serde(bound = "")]
63pub struct RelaxedR1CSInstance<G: Group> {
64 pub(crate) comm_W: Commitment<G>,
65 pub(crate) comm_E: Commitment<G>,
66 pub(crate) X: Vec<G::Scalar>,
67 pub(crate) u: G::Scalar,
68}
69
70impl<G: Group> R1CS<G> {
71 /// Samples public parameters for the specified number of constraints and variables in an R1CS
72 pub fn commitment_key(S: &R1CSShape<G>) -> CommitmentKey<G> {
73 let num_cons = S.num_cons;
74 let num_vars = S.num_vars;
75 let total_nz = S.A.len() + S.B.len() + S.C.len();
76 G::CE::setup(b"ck", max(max(num_cons, num_vars), total_nz))
77 }
78}
79
80impl<G: Group> R1CSShape<G> {
81 /// Create an object of type `R1CSShape` from the explicitly specified R1CS matrices
82 pub fn new(
83 num_cons: usize,
84 num_vars: usize,
85 num_io: usize,
86 A: &[(usize, usize, G::Scalar)],
87 B: &[(usize, usize, G::Scalar)],
88 C: &[(usize, usize, G::Scalar)],
89 ) -> Result<R1CSShape<G>, NovaError> {
90 let is_valid = |num_cons: usize,
91 num_vars: usize,
92 num_io: usize,
93 M: &[(usize, usize, G::Scalar)]|
94 -> Result<(), NovaError> {
95 let res = (0..M.len())
96 .map(|i| {
97 let (row, col, _val) = M[i];
98 if row >= num_cons || col > num_io + num_vars {
99 Err(NovaError::InvalidIndex)
100 } else {
101 Ok(())
102 }
103 })
104 .collect::<Result<Vec<()>, NovaError>>();
105
106 if res.is_err() {
107 Err(NovaError::InvalidIndex)
108 } else {
109 Ok(())
110 }
111 };
112
113 let res_A = is_valid(num_cons, num_vars, num_io, A);
114 let res_B = is_valid(num_cons, num_vars, num_io, B);
115 let res_C = is_valid(num_cons, num_vars, num_io, C);
116
117 if res_A.is_err() || res_B.is_err() || res_C.is_err() {
118 return Err(NovaError::InvalidIndex);
119 }
120
121 // We require the number of public inputs/outputs to be even
122 if num_io % 2 != 0 {
123 return Err(NovaError::OddInputLength);
124 }
125
126 Ok(R1CSShape {
127 num_cons,
128 num_vars,
129 num_io,
130 A: A.to_owned(),
131 B: B.to_owned(),
132 C: C.to_owned(),
133 })
134 }
135
136 // Checks regularity conditions on the R1CSShape, required in Spartan-class SNARKs
137 // Panics if num_cons, num_vars, or num_io are not powers of two, or if num_io > num_vars
138 #[inline]
139 pub(crate) fn check_regular_shape(&self) {
140 assert_eq!(self.num_cons.next_power_of_two(), self.num_cons);
141 assert_eq!(self.num_vars.next_power_of_two(), self.num_vars);
142 assert_eq!(self.num_io.next_power_of_two(), self.num_io);
143 assert!(self.num_io < self.num_vars);
144 }
145
146 pub fn multiply_vec(
147 &self,
148 z: &[G::Scalar],
149 ) -> Result<(Vec<G::Scalar>, Vec<G::Scalar>, Vec<G::Scalar>), NovaError> {
150 if z.len() != self.num_io + self.num_vars + 1 {
151 return Err(NovaError::InvalidWitnessLength);
152 }
153
154 // computes a product between a sparse matrix `M` and a vector `z`
155 // This does not perform any validation of entries in M (e.g., if entries in `M` reference indexes outside the range of `z`)
156 // This is safe since we know that `M` is valid
157 let sparse_matrix_vec_product =
158 |M: &Vec<(usize, usize, G::Scalar)>, num_rows: usize, z: &[G::Scalar]| -> Vec<G::Scalar> {
159 (0..M.len())
160 .map(|i| {
161 let (row, col, val) = M[i];
162 (row, val * z[col])
163 })
164 .fold(vec![G::Scalar::ZERO; num_rows], |mut Mz, (r, v)| {
165 Mz[r] += v;
166 Mz
167 })
168 };
169
170 let (Az, (Bz, Cz)) = rayon::join(
171 || sparse_matrix_vec_product(&self.A, self.num_cons, z),
172 || {
173 rayon::join(
174 || sparse_matrix_vec_product(&self.B, self.num_cons, z),
175 || sparse_matrix_vec_product(&self.C, self.num_cons, z),
176 )
177 },
178 );
179
180 Ok((Az, Bz, Cz))
181 }
182
183 /// Checks if the Relaxed R1CS instance is satisfiable given a witness and its shape
184 pub fn is_sat_relaxed(
185 &self,
186 ck: &CommitmentKey<G>,
187 U: &RelaxedR1CSInstance<G>,
188 W: &RelaxedR1CSWitness<G>,
189 ) -> Result<(), NovaError> {
190 assert_eq!(W.W.len(), self.num_vars);
191 assert_eq!(W.E.len(), self.num_cons);
192 assert_eq!(U.X.len(), self.num_io);
193
194 // verify if Az * Bz = u*Cz + E
195 let res_eq: bool = {
196 let z = concat(vec![W.W.clone(), vec![U.u], U.X.clone()]);
197 let (Az, Bz, Cz) = self.multiply_vec(&z)?;
198 assert_eq!(Az.len(), self.num_cons);
199 assert_eq!(Bz.len(), self.num_cons);
200 assert_eq!(Cz.len(), self.num_cons);
201
202 let res: usize = (0..self.num_cons)
203 .map(|i| usize::from(Az[i] * Bz[i] != U.u * Cz[i] + W.E[i]))
204 .sum();
205
206 res == 0
207 };
208
209 // verify if comm_E and comm_W are commitments to E and W
210 let res_comm: bool = {
211 let (comm_W, comm_E) =
212 rayon::join(|| CE::<G>::commit(ck, &W.W), || CE::<G>::commit(ck, &W.E));
213 U.comm_W == comm_W && U.comm_E == comm_E
214 };
215
216 if res_eq && res_comm {
217 Ok(())
218 } else {
219 Err(NovaError::UnSat)
220 }
221 }
222
223 /// Checks if the R1CS instance is satisfiable given a witness and its shape
224 pub fn is_sat(
225 &self,
226 ck: &CommitmentKey<G>,
227 U: &R1CSInstance<G>,
228 W: &R1CSWitness<G>,
229 ) -> Result<(), NovaError> {
230 assert_eq!(W.W.len(), self.num_vars);
231 assert_eq!(U.X.len(), self.num_io);
232
233 // verify if Az * Bz = u*Cz
234 let res_eq: bool = {
235 let z = concat(vec![W.W.clone(), vec![G::Scalar::ONE], U.X.clone()]);
236 let (Az, Bz, Cz) = self.multiply_vec(&z)?;
237 assert_eq!(Az.len(), self.num_cons);
238 assert_eq!(Bz.len(), self.num_cons);
239 assert_eq!(Cz.len(), self.num_cons);
240
241 let res: usize = (0..self.num_cons)
242 .map(|i| usize::from(Az[i] * Bz[i] != Cz[i]))
243 .sum();
244
245 res == 0
246 };
247
248 // verify if comm_W is a commitment to W
249 let res_comm: bool = U.comm_W == CE::<G>::commit(ck, &W.W);
250
251 if res_eq && res_comm {
252 Ok(())
253 } else {
254 Err(NovaError::UnSat)
255 }
256 }
257
258 /// A method to compute a commitment to the cross-term `T` given a
259 /// Relaxed R1CS instance-witness pair and an R1CS instance-witness pair
260 pub fn commit_T(
261 &self,
262 ck: &CommitmentKey<G>,
263 U1: &RelaxedR1CSInstance<G>,
264 W1: &RelaxedR1CSWitness<G>,
265 U2: &R1CSInstance<G>,
266 W2: &R1CSWitness<G>,
267 ) -> Result<(Vec<G::Scalar>, Commitment<G>), NovaError> {
268 let (AZ_1, BZ_1, CZ_1) = {
269 let Z1 = concat(vec![W1.W.clone(), vec![U1.u], U1.X.clone()]);
270 self.multiply_vec(&Z1)?
271 };
272
273 let (AZ_2, BZ_2, CZ_2) = {
274 let Z2 = concat(vec![W2.W.clone(), vec![G::Scalar::ONE], U2.X.clone()]);
275 self.multiply_vec(&Z2)?
276 };
277
278 let AZ_1_circ_BZ_2 = (0..AZ_1.len())
279 .into_par_iter()
280 .map(|i| AZ_1[i] * BZ_2[i])
281 .collect::<Vec<G::Scalar>>();
282 let AZ_2_circ_BZ_1 = (0..AZ_2.len())
283 .into_par_iter()
284 .map(|i| AZ_2[i] * BZ_1[i])
285 .collect::<Vec<G::Scalar>>();
286 let u_1_cdot_CZ_2 = (0..CZ_2.len())
287 .into_par_iter()
288 .map(|i| U1.u * CZ_2[i])
289 .collect::<Vec<G::Scalar>>();
290 let u_2_cdot_CZ_1 = (0..CZ_1.len())
291 .into_par_iter()
292 .map(|i| CZ_1[i])
293 .collect::<Vec<G::Scalar>>();
294
295 let T = AZ_1_circ_BZ_2
296 .par_iter()
297 .zip(&AZ_2_circ_BZ_1)
298 .zip(&u_1_cdot_CZ_2)
299 .zip(&u_2_cdot_CZ_1)
300 .map(|(((a, b), c), d)| *a + *b - *c - *d)
301 .collect::<Vec<G::Scalar>>();
302
303 let comm_T = CE::<G>::commit(ck, &T);
304
305 Ok((T, comm_T))
306 }
307
308 /// Pads the R1CSShape so that the number of variables is a power of two
309 /// Renumbers variables to accomodate padded variables
310 pub fn pad(&self) -> Self {
311 // equalize the number of variables and constraints
312 let m = max(self.num_vars, self.num_cons).next_power_of_two();
313
314 // check if the provided R1CSShape is already as required
315 if self.num_vars == m && self.num_cons == m {
316 return self.clone();
317 }
318
319 // check if the number of variables are as expected, then
320 // we simply set the number of constraints to the next power of two
321 if self.num_vars == m {
322 return R1CSShape {
323 num_cons: m,
324 num_vars: m,
325 num_io: self.num_io,
326 A: self.A.clone(),
327 B: self.B.clone(),
328 C: self.C.clone(),
329 };
330 }
331
332 // otherwise, we need to pad the number of variables and renumber variable accesses
333 let num_vars_padded = m;
334 let num_cons_padded = m;
335 let apply_pad = |M: &[(usize, usize, G::Scalar)]| -> Vec<(usize, usize, G::Scalar)> {
336 M.par_iter()
337 .map(|(r, c, v)| {
338 (
339 *r,
340 if c >= &self.num_vars {
341 c + num_vars_padded - self.num_vars
342 } else {
343 *c
344 },
345 *v,
346 )
347 })
348 .collect::<Vec<_>>()
349 };
350
351 let A_padded = apply_pad(&self.A);
352 let B_padded = apply_pad(&self.B);
353 let C_padded = apply_pad(&self.C);
354
355 R1CSShape {
356 num_cons: num_cons_padded,
357 num_vars: num_vars_padded,
358 num_io: self.num_io,
359 A: A_padded,
360 B: B_padded,
361 C: C_padded,
362 }
363 }
364}
365
366impl<G: Group> R1CSWitness<G> {
367 /// A method to create a witness object using a vector of scalars
368 pub fn new(S: &R1CSShape<G>, W: &[G::Scalar]) -> Result<R1CSWitness<G>, NovaError> {
369 if S.num_vars != W.len() {
370 Err(NovaError::InvalidWitnessLength)
371 } else {
372 Ok(R1CSWitness { W: W.to_owned() })
373 }
374 }
375
376 /// Commits to the witness using the supplied generators
377 pub fn commit(&self, ck: &CommitmentKey<G>) -> Commitment<G> {
378 CE::<G>::commit(ck, &self.W)
379 }
380}
381
382impl<G: Group> R1CSInstance<G> {
383 /// A method to create an instance object using consitituent elements
384 pub fn new(
385 S: &R1CSShape<G>,
386 comm_W: &Commitment<G>,
387 X: &[G::Scalar],
388 ) -> Result<R1CSInstance<G>, NovaError> {
389 if S.num_io != X.len() {
390 Err(NovaError::InvalidInputLength)
391 } else {
392 Ok(R1CSInstance {
393 comm_W: *comm_W,
394 X: X.to_owned(),
395 })
396 }
397 }
398}
399
400impl<G: Group> AbsorbInROTrait<G> for R1CSInstance<G> {
401 fn absorb_in_ro(&self, ro: &mut G::RO) {
402 self.comm_W.absorb_in_ro(ro);
403 for x in &self.X {
404 ro.absorb(scalar_as_base::<G>(*x));
405 }
406 }
407}
408
409impl<G: Group> RelaxedR1CSWitness<G> {
410 /// Produces a default RelaxedR1CSWitness given an R1CSShape
411 pub fn default(S: &R1CSShape<G>) -> RelaxedR1CSWitness<G> {
412 RelaxedR1CSWitness {
413 W: vec![G::Scalar::ZERO; S.num_vars],
414 E: vec![G::Scalar::ZERO; S.num_cons],
415 }
416 }
417
418 /// Initializes a new RelaxedR1CSWitness from an R1CSWitness
419 pub fn from_r1cs_witness(S: &R1CSShape<G>, witness: &R1CSWitness<G>) -> RelaxedR1CSWitness<G> {
420 RelaxedR1CSWitness {
421 W: witness.W.clone(),
422 E: vec![G::Scalar::ZERO; S.num_cons],
423 }
424 }
425
426 /// Commits to the witness using the supplied generators
427 pub fn commit(&self, ck: &CommitmentKey<G>) -> (Commitment<G>, Commitment<G>) {
428 (CE::<G>::commit(ck, &self.W), CE::<G>::commit(ck, &self.E))
429 }
430
431 /// Folds an incoming R1CSWitness into the current one
432 pub fn fold(
433 &self,
434 W2: &R1CSWitness<G>,
435 T: &[G::Scalar],
436 r: &G::Scalar,
437 ) -> Result<RelaxedR1CSWitness<G>, NovaError> {
438 let (W1, E1) = (&self.W, &self.E);
439 let W2 = &W2.W;
440
441 if W1.len() != W2.len() {
442 return Err(NovaError::InvalidWitnessLength);
443 }
444
445 let W = W1
446 .par_iter()
447 .zip(W2)
448 .map(|(a, b)| *a + *r * *b)
449 .collect::<Vec<G::Scalar>>();
450 let E = E1
451 .par_iter()
452 .zip(T)
453 .map(|(a, b)| *a + *r * *b)
454 .collect::<Vec<G::Scalar>>();
455 Ok(RelaxedR1CSWitness { W, E })
456 }
457
458 /// Pads the provided witness to the correct length
459 pub fn pad(&self, S: &R1CSShape<G>) -> RelaxedR1CSWitness<G> {
460 let W = {
461 let mut W = self.W.clone();
462 W.extend(vec![G::Scalar::ZERO; S.num_vars - W.len()]);
463 W
464 };
465
466 let E = {
467 let mut E = self.E.clone();
468 E.extend(vec![G::Scalar::ZERO; S.num_cons - E.len()]);
469 E
470 };
471
472 Self { W, E }
473 }
474}
475
476impl<G: Group> RelaxedR1CSInstance<G> {
477 /// Produces a default RelaxedR1CSInstance given R1CSGens and R1CSShape
478 pub fn default(_ck: &CommitmentKey<G>, S: &R1CSShape<G>) -> RelaxedR1CSInstance<G> {
479 let (comm_W, comm_E) = (Commitment::<G>::default(), Commitment::<G>::default());
480 RelaxedR1CSInstance {
481 comm_W,
482 comm_E,
483 u: G::Scalar::ZERO,
484 X: vec![G::Scalar::ZERO; S.num_io],
485 }
486 }
487
488 /// Initializes a new RelaxedR1CSInstance from an R1CSInstance
489 pub fn from_r1cs_instance(
490 ck: &CommitmentKey<G>,
491 S: &R1CSShape<G>,
492 instance: &R1CSInstance<G>,
493 ) -> RelaxedR1CSInstance<G> {
494 let mut r_instance = RelaxedR1CSInstance::default(ck, S);
495 r_instance.comm_W = instance.comm_W;
496 r_instance.u = G::Scalar::ONE;
497 r_instance.X = instance.X.clone();
498 r_instance
499 }
500
501 /// Initializes a new RelaxedR1CSInstance from an R1CSInstance
502 pub fn from_r1cs_instance_unchecked(
503 comm_W: &Commitment<G>,
504 X: &[G::Scalar],
505 ) -> RelaxedR1CSInstance<G> {
506 RelaxedR1CSInstance {
507 comm_W: *comm_W,
508 comm_E: Commitment::<G>::default(),
509 u: G::Scalar::ONE,
510 X: X.to_vec(),
511 }
512 }
513
514 /// Folds an incoming RelaxedR1CSInstance into the current one
515 pub fn fold(
516 &self,
517 U2: &R1CSInstance<G>,
518 comm_T: &Commitment<G>,
519 r: &G::Scalar,
520 ) -> Result<RelaxedR1CSInstance<G>, NovaError> {
521 let (X1, u1, comm_W_1, comm_E_1) =
522 (&self.X, &self.u, &self.comm_W.clone(), &self.comm_E.clone());
523 let (X2, comm_W_2) = (&U2.X, &U2.comm_W);
524
525 // weighted sum of X, comm_W, comm_E, and u
526 let X = X1
527 .par_iter()
528 .zip(X2)
529 .map(|(a, b)| *a + *r * *b)
530 .collect::<Vec<G::Scalar>>();
531 let comm_W = *comm_W_1 + *comm_W_2 * *r;
532 let comm_E = *comm_E_1 + *comm_T * *r;
533 let u = *u1 + *r;
534
535 Ok(RelaxedR1CSInstance {
536 comm_W,
537 comm_E,
538 X,
539 u,
540 })
541 }
542}
543
544impl<G: Group> TranscriptReprTrait<G> for RelaxedR1CSInstance<G> {
545 fn to_transcript_bytes(&self) -> Vec<u8> {
546 [
547 self.comm_W.to_transcript_bytes(),
548 self.comm_E.to_transcript_bytes(),
549 self.u.to_transcript_bytes(),
550 self.X.as_slice().to_transcript_bytes(),
551 ]
552 .concat()
553 }
554}
555
556impl<G: Group> AbsorbInROTrait<G> for RelaxedR1CSInstance<G> {
557 fn absorb_in_ro(&self, ro: &mut G::RO) {
558 self.comm_W.absorb_in_ro(ro);
559 self.comm_E.absorb_in_ro(ro);
560 ro.absorb(scalar_as_base::<G>(self.u));
561
562 // absorb each element of self.X in bignum format
563 for x in &self.X {
564 let limbs: Vec<G::Scalar> = nat_to_limbs(&f_to_nat(x), BN_LIMB_WIDTH, BN_N_LIMBS).unwrap();
565 for limb in limbs {
566 ro.absorb(scalar_as_base::<G>(limb));
567 }
568 }
569 }
570}