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