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