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, NUM_HASH_BITS},
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 flate2::{write::ZlibEncoder, Compression};
18use itertools::concat;
19use rayon::prelude::*;
20use serde::{Deserialize, Serialize};
21use sha3::{Digest, Sha3_256};
22
23/// Public parameters for a given R1CS
24#[derive(Clone, Serialize, Deserialize)]
25#[serde(bound = "")]
26pub struct R1CS<G: Group> {
27 _p: PhantomData<G>,
28}
29
30/// A type that holds the shape of the R1CS matrices
31#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
32pub struct R1CSShape<G: Group> {
33 pub(crate) num_cons: usize,
34 pub(crate) num_vars: usize,
35 pub(crate) num_io: usize,
36 pub(crate) A: Vec<(usize, usize, G::Scalar)>,
37 pub(crate) B: Vec<(usize, usize, G::Scalar)>,
38 pub(crate) C: Vec<(usize, usize, G::Scalar)>,
39 digest: G::Scalar, // digest of the rest of R1CSShape
40}
41
42/// A type that holds a witness for a given R1CS instance
43#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
44pub struct R1CSWitness<G: Group> {
45 W: Vec<G::Scalar>,
46}
47
48/// A type that holds an R1CS instance
49#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
50#[serde(bound = "")]
51pub struct R1CSInstance<G: Group> {
52 pub(crate) comm_W: Commitment<G>,
53 pub(crate) X: Vec<G::Scalar>,
54}
55
56/// A type that holds a witness for a given Relaxed R1CS instance
57#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
58pub struct RelaxedR1CSWitness<G: Group> {
59 pub(crate) W: Vec<G::Scalar>,
60 pub(crate) E: Vec<G::Scalar>,
61}
62
63/// A type that holds a Relaxed R1CS instance
64#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
65#[serde(bound = "")]
66pub struct RelaxedR1CSInstance<G: Group> {
67 pub(crate) comm_W: Commitment<G>,
68 pub(crate) comm_E: Commitment<G>,
69 pub(crate) X: Vec<G::Scalar>,
70 pub(crate) u: G::Scalar,
71}
72
73impl<G: Group> R1CS<G> {
74 /// Samples public parameters for the specified number of constraints and variables in an R1CS
75 pub fn commitment_key(num_cons: usize, num_vars: usize) -> CommitmentKey<G> {
76 G::CE::setup(b"ck", max(num_vars, num_cons))
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 let digest = Self::compute_digest(num_cons, num_vars, num_io, A, B, C);
127
128 let shape = R1CSShape {
129 num_cons,
130 num_vars,
131 num_io,
132 A: A.to_owned(),
133 B: B.to_owned(),
134 C: C.to_owned(),
135 digest,
136 };
137
138 Ok(shape)
139 }
140
141 pub fn multiply_vec(
142 &self,
143 z: &[G::Scalar],
144 ) -> Result<(Vec<G::Scalar>, Vec<G::Scalar>, Vec<G::Scalar>), NovaError> {
145 if z.len() != self.num_io + self.num_vars + 1 {
146 return Err(NovaError::InvalidWitnessLength);
147 }
148
149 // computes a product between a sparse matrix `M` and a vector `z`
150 // This does not perform any validation of entries in M (e.g., if entries in `M` reference indexes outside the range of `z`)
151 // This is safe since we know that `M` is valid
152 let sparse_matrix_vec_product =
153 |M: &Vec<(usize, usize, G::Scalar)>, num_rows: usize, z: &[G::Scalar]| -> Vec<G::Scalar> {
154 (0..M.len())
155 .map(|i| {
156 let (row, col, val) = M[i];
157 (row, val * z[col])
158 })
159 .fold(vec![G::Scalar::zero(); num_rows], |mut Mz, (r, v)| {
160 Mz[r] += v;
161 Mz
162 })
163 };
164
165 let (Az, (Bz, Cz)) = rayon::join(
166 || sparse_matrix_vec_product(&self.A, self.num_cons, z),
167 || {
168 rayon::join(
169 || sparse_matrix_vec_product(&self.B, self.num_cons, z),
170 || sparse_matrix_vec_product(&self.C, self.num_cons, z),
171 )
172 },
173 );
174
175 Ok((Az, Bz, Cz))
176 }
177
178 /// Checks if the Relaxed R1CS instance is satisfiable given a witness and its shape
179 pub fn is_sat_relaxed(
180 &self,
181 ck: &CommitmentKey<G>,
182 U: &RelaxedR1CSInstance<G>,
183 W: &RelaxedR1CSWitness<G>,
184 ) -> Result<(), NovaError> {
185 assert_eq!(W.W.len(), self.num_vars);
186 assert_eq!(W.E.len(), self.num_cons);
187 assert_eq!(U.X.len(), self.num_io);
188
189 // verify if Az * Bz = u*Cz + E
190 let res_eq: bool = {
191 let z = concat(vec![W.W.clone(), vec![U.u], U.X.clone()]);
192 let (Az, Bz, Cz) = self.multiply_vec(&z)?;
193 assert_eq!(Az.len(), self.num_cons);
194 assert_eq!(Bz.len(), self.num_cons);
195 assert_eq!(Cz.len(), self.num_cons);
196
197 let res: usize = (0..self.num_cons)
198 .map(|i| usize::from(Az[i] * Bz[i] != U.u * Cz[i] + W.E[i]))
199 .sum();
200
201 res == 0
202 };
203
204 // verify if comm_E and comm_W are commitments to E and W
205 let res_comm: bool = {
206 let (comm_W, comm_E) =
207 rayon::join(|| CE::<G>::commit(ck, &W.W), || CE::<G>::commit(ck, &W.E));
208 U.comm_W == comm_W && U.comm_E == comm_E
209 };
210
211 if res_eq && res_comm {
212 Ok(())
213 } else {
214 Err(NovaError::UnSat)
215 }
216 }
217
218 /// Checks if the R1CS instance is satisfiable given a witness and its shape
219 pub fn is_sat(
220 &self,
221 ck: &CommitmentKey<G>,
222 U: &R1CSInstance<G>,
223 W: &R1CSWitness<G>,
224 ) -> Result<(), NovaError> {
225 assert_eq!(W.W.len(), self.num_vars);
226 assert_eq!(U.X.len(), self.num_io);
227
228 // verify if Az * Bz = u*Cz
229 let res_eq: bool = {
230 let z = concat(vec![W.W.clone(), vec![G::Scalar::one()], U.X.clone()]);
231 let (Az, Bz, Cz) = self.multiply_vec(&z)?;
232 assert_eq!(Az.len(), self.num_cons);
233 assert_eq!(Bz.len(), self.num_cons);
234 assert_eq!(Cz.len(), self.num_cons);
235
236 let res: usize = (0..self.num_cons)
237 .map(|i| usize::from(Az[i] * Bz[i] != Cz[i]))
238 .sum();
239
240 res == 0
241 };
242
243 // verify if comm_W is a commitment to W
244 let res_comm: bool = U.comm_W == CE::<G>::commit(ck, &W.W);
245
246 if res_eq && res_comm {
247 Ok(())
248 } else {
249 Err(NovaError::UnSat)
250 }
251 }
252
253 /// A method to compute a commitment to the cross-term `T` given a
254 /// Relaxed R1CS instance-witness pair and an R1CS instance-witness pair
255 pub fn commit_T(
256 &self,
257 ck: &CommitmentKey<G>,
258 U1: &RelaxedR1CSInstance<G>,
259 W1: &RelaxedR1CSWitness<G>,
260 U2: &R1CSInstance<G>,
261 W2: &R1CSWitness<G>,
262 ) -> Result<(Vec<G::Scalar>, Commitment<G>), NovaError> {
263 let (AZ_1, BZ_1, CZ_1) = {
264 let Z1 = concat(vec![W1.W.clone(), vec![U1.u], U1.X.clone()]);
265 self.multiply_vec(&Z1)?
266 };
267
268 let (AZ_2, BZ_2, CZ_2) = {
269 let Z2 = concat(vec![W2.W.clone(), vec![G::Scalar::one()], U2.X.clone()]);
270 self.multiply_vec(&Z2)?
271 };
272
273 let AZ_1_circ_BZ_2 = (0..AZ_1.len())
274 .into_par_iter()
275 .map(|i| AZ_1[i] * BZ_2[i])
276 .collect::<Vec<G::Scalar>>();
277 let AZ_2_circ_BZ_1 = (0..AZ_2.len())
278 .into_par_iter()
279 .map(|i| AZ_2[i] * BZ_1[i])
280 .collect::<Vec<G::Scalar>>();
281 let u_1_cdot_CZ_2 = (0..CZ_2.len())
282 .into_par_iter()
283 .map(|i| U1.u * CZ_2[i])
284 .collect::<Vec<G::Scalar>>();
285 let u_2_cdot_CZ_1 = (0..CZ_1.len())
286 .into_par_iter()
287 .map(|i| CZ_1[i])
288 .collect::<Vec<G::Scalar>>();
289
290 let T = AZ_1_circ_BZ_2
291 .par_iter()
292 .zip(&AZ_2_circ_BZ_1)
293 .zip(&u_1_cdot_CZ_2)
294 .zip(&u_2_cdot_CZ_1)
295 .map(|(((a, b), c), d)| *a + *b - *c - *d)
296 .collect::<Vec<G::Scalar>>();
297
298 let comm_T = CE::<G>::commit(ck, &T);
299
300 Ok((T, comm_T))
301 }
302
303 /// returns the digest of R1CSShape
304 pub fn get_digest(&self) -> G::Scalar {
305 self.digest
306 }
307
308 fn compute_digest(
309 num_cons: usize,
310 num_vars: usize,
311 num_io: usize,
312 A: &[(usize, usize, G::Scalar)],
313 B: &[(usize, usize, G::Scalar)],
314 C: &[(usize, usize, G::Scalar)],
315 ) -> G::Scalar {
316 #[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
317 struct R1CSShapeWithoutDigest<G: Group> {
318 num_cons: usize,
319 num_vars: usize,
320 num_io: usize,
321 A: Vec<(usize, usize, G::Scalar)>,
322 B: Vec<(usize, usize, G::Scalar)>,
323 C: Vec<(usize, usize, G::Scalar)>,
324 }
325
326 let shape = R1CSShapeWithoutDigest::<G> {
327 num_cons,
328 num_vars,
329 num_io,
330 A: A.to_vec(),
331 B: B.to_vec(),
332 C: C.to_vec(),
333 };
334
335 // obtain a vector of bytes representing the R1CS shape
336 let mut encoder = ZlibEncoder::new(Vec::new(), Compression::default());
337 bincode::serialize_into(&mut encoder, &shape).unwrap();
338 let shape_bytes = encoder.finish().unwrap();
339
340 // convert shape_bytes into a short digest
341 let mut hasher = Sha3_256::new();
342 hasher.input(&shape_bytes);
343 let digest = hasher.result();
344
345 // truncate the digest to 250 bits
346 let bv = (0..NUM_HASH_BITS).map(|i| {
347 let (byte_pos, bit_pos) = (i / 8, i % 8);
348 let bit = (digest[byte_pos] >> bit_pos) & 1;
349 bit == 1
350 });
351
352 // turn the bit vector into a scalar
353 let mut res = G::Scalar::zero();
354 let mut coeff = G::Scalar::one();
355 for bit in bv {
356 if bit {
357 res += coeff;
358 }
359 coeff += coeff;
360 }
361 res
362 }
363
364 /// Pads the R1CSShape so that the number of variables is a power of two
365 /// Renumbers variables to accomodate padded variables
366 pub fn pad(&self) -> Self {
367 // check if the provided R1CSShape is already as required
368 if self.num_vars.next_power_of_two() == self.num_vars
369 && self.num_cons.next_power_of_two() == self.num_cons
370 {
371 return self.clone();
372 }
373
374 // check if the number of variables are as expected, then
375 // we simply set the number of constraints to the next power of two
376 if self.num_vars.next_power_of_two() == self.num_vars {
377 let digest = Self::compute_digest(
378 self.num_cons.next_power_of_two(),
379 self.num_vars,
380 self.num_io,
381 &self.A,
382 &self.B,
383 &self.C,
384 );
385
386 return R1CSShape {
387 num_cons: self.num_cons.next_power_of_two(),
388 num_vars: self.num_vars,
389 num_io: self.num_io,
390 A: self.A.clone(),
391 B: self.B.clone(),
392 C: self.C.clone(),
393 digest,
394 };
395 }
396
397 // otherwise, we need to pad the number of variables and renumber variable accesses
398 let num_vars_padded = self.num_vars.next_power_of_two();
399 let num_cons_padded = self.num_cons.next_power_of_two();
400 let apply_pad = |M: &[(usize, usize, G::Scalar)]| -> Vec<(usize, usize, G::Scalar)> {
401 M.par_iter()
402 .map(|(r, c, v)| {
403 if c >= &self.num_vars {
404 (*r, c + num_vars_padded - self.num_vars, *v)
405 } else {
406 (*r, *c, *v)
407 }
408 })
409 .collect::<Vec<_>>()
410 };
411
412 let A_padded = apply_pad(&self.A);
413 let B_padded = apply_pad(&self.B);
414 let C_padded = apply_pad(&self.C);
415
416 let digest = Self::compute_digest(
417 num_cons_padded,
418 num_vars_padded,
419 self.num_io,
420 &A_padded,
421 &B_padded,
422 &C_padded,
423 );
424
425 R1CSShape {
426 num_cons: num_cons_padded,
427 num_vars: num_vars_padded,
428 num_io: self.num_io,
429 A: A_padded,
430 B: B_padded,
431 C: C_padded,
432 digest,
433 }
434 }
435}
436
437impl<G: Group> TranscriptReprTrait<G> for R1CSShape<G> {
438 fn to_transcript_bytes(&self) -> Vec<u8> {
439 self.get_digest().to_transcript_bytes()
440 }
441}
442
443impl<G: Group> AbsorbInROTrait<G> for R1CSShape<G> {
444 fn absorb_in_ro(&self, ro: &mut G::RO) {
445 ro.absorb(scalar_as_base::<G>(self.get_digest()));
446 }
447}
448
449impl<G: Group> R1CSWitness<G> {
450 /// A method to create a witness object using a vector of scalars
451 pub fn new(S: &R1CSShape<G>, W: &[G::Scalar]) -> Result<R1CSWitness<G>, NovaError> {
452 if S.num_vars != W.len() {
453 Err(NovaError::InvalidWitnessLength)
454 } else {
455 Ok(R1CSWitness { W: W.to_owned() })
456 }
457 }
458
459 /// Commits to the witness using the supplied generators
460 pub fn commit(&self, ck: &CommitmentKey<G>) -> Commitment<G> {
461 CE::<G>::commit(ck, &self.W)
462 }
463}
464
465impl<G: Group> R1CSInstance<G> {
466 /// A method to create an instance object using consitituent elements
467 pub fn new(
468 S: &R1CSShape<G>,
469 comm_W: &Commitment<G>,
470 X: &[G::Scalar],
471 ) -> Result<R1CSInstance<G>, NovaError> {
472 if S.num_io != X.len() {
473 Err(NovaError::InvalidInputLength)
474 } else {
475 Ok(R1CSInstance {
476 comm_W: *comm_W,
477 X: X.to_owned(),
478 })
479 }
480 }
481}
482
483impl<G: Group> AbsorbInROTrait<G> for R1CSInstance<G> {
484 fn absorb_in_ro(&self, ro: &mut G::RO) {
485 self.comm_W.absorb_in_ro(ro);
486 for x in &self.X {
487 ro.absorb(scalar_as_base::<G>(*x));
488 }
489 }
490}
491
492impl<G: Group> RelaxedR1CSWitness<G> {
493 /// Produces a default RelaxedR1CSWitness given an R1CSShape
494 pub fn default(S: &R1CSShape<G>) -> RelaxedR1CSWitness<G> {
495 RelaxedR1CSWitness {
496 W: vec![G::Scalar::zero(); S.num_vars],
497 E: vec![G::Scalar::zero(); S.num_cons],
498 }
499 }
500
501 /// Initializes a new RelaxedR1CSWitness from an R1CSWitness
502 pub fn from_r1cs_witness(S: &R1CSShape<G>, witness: &R1CSWitness<G>) -> RelaxedR1CSWitness<G> {
503 RelaxedR1CSWitness {
504 W: witness.W.clone(),
505 E: vec![G::Scalar::zero(); S.num_cons],
506 }
507 }
508
509 /// Commits to the witness using the supplied generators
510 pub fn commit(&self, ck: &CommitmentKey<G>) -> (Commitment<G>, Commitment<G>) {
511 (CE::<G>::commit(ck, &self.W), CE::<G>::commit(ck, &self.E))
512 }
513
514 /// Folds an incoming R1CSWitness into the current one
515 pub fn fold(
516 &self,
517 W2: &R1CSWitness<G>,
518 T: &[G::Scalar],
519 r: &G::Scalar,
520 ) -> Result<RelaxedR1CSWitness<G>, NovaError> {
521 let (W1, E1) = (&self.W, &self.E);
522 let W2 = &W2.W;
523
524 if W1.len() != W2.len() {
525 return Err(NovaError::InvalidWitnessLength);
526 }
527
528 let W = W1
529 .par_iter()
530 .zip(W2)
531 .map(|(a, b)| *a + *r * *b)
532 .collect::<Vec<G::Scalar>>();
533 let E = E1
534 .par_iter()
535 .zip(T)
536 .map(|(a, b)| *a + *r * *b)
537 .collect::<Vec<G::Scalar>>();
538 Ok(RelaxedR1CSWitness { W, E })
539 }
540
541 /// Pads the provided witness to the correct length
542 pub fn pad(&self, S: &R1CSShape<G>) -> RelaxedR1CSWitness<G> {
543 let W = {
544 let mut W = self.W.clone();
545 W.extend(vec![G::Scalar::zero(); S.num_vars - W.len()]);
546 W
547 };
548
549 let E = {
550 let mut E = self.E.clone();
551 E.extend(vec![G::Scalar::zero(); S.num_cons - E.len()]);
552 E
553 };
554
555 Self { W, E }
556 }
557}
558
559impl<G: Group> RelaxedR1CSInstance<G> {
560 /// Produces a default RelaxedR1CSInstance given R1CSGens and R1CSShape
561 pub fn default(_ck: &CommitmentKey<G>, S: &R1CSShape<G>) -> RelaxedR1CSInstance<G> {
562 let (comm_W, comm_E) = (Commitment::<G>::default(), Commitment::<G>::default());
563 RelaxedR1CSInstance {
564 comm_W,
565 comm_E,
566 u: G::Scalar::zero(),
567 X: vec![G::Scalar::zero(); S.num_io],
568 }
569 }
570
571 /// Initializes a new RelaxedR1CSInstance from an R1CSInstance
572 pub fn from_r1cs_instance(
573 ck: &CommitmentKey<G>,
574 S: &R1CSShape<G>,
575 instance: &R1CSInstance<G>,
576 ) -> RelaxedR1CSInstance<G> {
577 let mut r_instance = RelaxedR1CSInstance::default(ck, S);
578 r_instance.comm_W = instance.comm_W;
579 r_instance.u = G::Scalar::one();
580 r_instance.X = instance.X.clone();
581 r_instance
582 }
583
584 /// Folds an incoming RelaxedR1CSInstance into the current one
585 pub fn fold(
586 &self,
587 U2: &R1CSInstance<G>,
588 comm_T: &Commitment<G>,
589 r: &G::Scalar,
590 ) -> Result<RelaxedR1CSInstance<G>, NovaError> {
591 let (X1, u1, comm_W_1, comm_E_1) =
592 (&self.X, &self.u, &self.comm_W.clone(), &self.comm_E.clone());
593 let (X2, comm_W_2) = (&U2.X, &U2.comm_W);
594
595 // weighted sum of X, comm_W, comm_E, and u
596 let X = X1
597 .par_iter()
598 .zip(X2)
599 .map(|(a, b)| *a + *r * *b)
600 .collect::<Vec<G::Scalar>>();
601 let comm_W = *comm_W_1 + *comm_W_2 * *r;
602 let comm_E = *comm_E_1 + *comm_T * *r;
603 let u = *u1 + *r;
604
605 Ok(RelaxedR1CSInstance {
606 comm_W,
607 comm_E,
608 X,
609 u,
610 })
611 }
612}
613
614impl<G: Group> TranscriptReprTrait<G> for RelaxedR1CSInstance<G> {
615 fn to_transcript_bytes(&self) -> Vec<u8> {
616 [
617 self.comm_W.to_transcript_bytes(),
618 self.comm_E.to_transcript_bytes(),
619 self.u.to_transcript_bytes(),
620 self.X.as_slice().to_transcript_bytes(),
621 ]
622 .concat()
623 }
624}
625
626impl<G: Group> AbsorbInROTrait<G> for RelaxedR1CSInstance<G> {
627 fn absorb_in_ro(&self, ro: &mut G::RO) {
628 self.comm_W.absorb_in_ro(ro);
629 self.comm_E.absorb_in_ro(ro);
630 ro.absorb(scalar_as_base::<G>(self.u));
631
632 // absorb each element of self.X in bignum format
633 for x in &self.X {
634 let limbs: Vec<G::Scalar> = nat_to_limbs(&f_to_nat(x), BN_LIMB_WIDTH, BN_N_LIMBS).unwrap();
635 for limb in limbs {
636 ro.absorb(scalar_as_base::<G>(limb));
637 }
638 }
639 }
640}