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::{
4 commitments::{CommitGens, CommitTrait, Commitment},
5 constants::{BN_LIMB_WIDTH, BN_N_LIMBS, NUM_HASH_BITS},
6 errors::NovaError,
7 gadgets::utils::scalar_as_base,
8 traits::{AbsorbInROTrait, AppendToTranscriptTrait, Group, HashFuncTrait},
9};
10use bellperson_nonnative::{mp::bignat::nat_to_limbs, util::convert::f_to_nat};
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| {
195 if Az[i] * Bz[i] == U.u * Cz[i] + W.E[i] {
196 0
197 } else {
198 1
199 }
200 })
201 .sum();
202
203 res == 0
204 };
205
206 // verify if comm_E and comm_W are commitments to E and W
207 let res_comm: bool = {
208 let (comm_W, comm_E) = rayon::join(|| W.W.commit(&gens.gens), || W.E.commit(&gens.gens));
209 U.comm_W == comm_W && U.comm_E == comm_E
210 };
211
212 if res_eq && res_comm {
213 Ok(())
214 } else {
215 Err(NovaError::UnSat)
216 }
217 }
218
219 /// Checks if the R1CS instance is satisfiable given a witness and its shape
220 pub fn is_sat(
221 &self,
222 gens: &R1CSGens<G>,
223 U: &R1CSInstance<G>,
224 W: &R1CSWitness<G>,
225 ) -> Result<(), NovaError> {
226 assert_eq!(W.W.len(), self.num_vars);
227 assert_eq!(U.X.len(), self.num_io);
228
229 // verify if Az * Bz = u*Cz
230 let res_eq: bool = {
231 let z = concat(vec![W.W.clone(), vec![G::Scalar::one()], U.X.clone()]);
232 let (Az, Bz, Cz) = self.multiply_vec(&z)?;
233 assert_eq!(Az.len(), self.num_cons);
234 assert_eq!(Bz.len(), self.num_cons);
235 assert_eq!(Cz.len(), self.num_cons);
236
237 let res: usize = (0..self.num_cons)
238 .map(|i| if Az[i] * Bz[i] == Cz[i] { 0 } else { 1 })
239 .sum();
240
241 res == 0
242 };
243
244 // verify if comm_W is a commitment to W
245 let res_comm: bool = U.comm_W == W.W.commit(&gens.gens);
246
247 if res_eq && res_comm {
248 Ok(())
249 } else {
250 Err(NovaError::UnSat)
251 }
252 }
253
254 /// A method to compute a commitment to the cross-term `T` given a
255 /// Relaxed R1CS instance-witness pair and an R1CS instance-witness pair
256 pub fn commit_T(
257 &self,
258 gens: &R1CSGens<G>,
259 U1: &RelaxedR1CSInstance<G>,
260 W1: &RelaxedR1CSWitness<G>,
261 U2: &R1CSInstance<G>,
262 W2: &R1CSWitness<G>,
263 ) -> Result<(Vec<G::Scalar>, Commitment<G>), NovaError> {
264 let (AZ_1, BZ_1, CZ_1) = {
265 let Z1 = concat(vec![W1.W.clone(), vec![U1.u], U1.X.clone()]);
266 self.multiply_vec(&Z1)?
267 };
268
269 let (AZ_2, BZ_2, CZ_2) = {
270 let Z2 = concat(vec![W2.W.clone(), vec![G::Scalar::one()], U2.X.clone()]);
271 self.multiply_vec(&Z2)?
272 };
273
274 let AZ_1_circ_BZ_2 = (0..AZ_1.len())
275 .into_par_iter()
276 .map(|i| AZ_1[i] * BZ_2[i])
277 .collect::<Vec<G::Scalar>>();
278 let AZ_2_circ_BZ_1 = (0..AZ_2.len())
279 .into_par_iter()
280 .map(|i| AZ_2[i] * BZ_1[i])
281 .collect::<Vec<G::Scalar>>();
282 let u_1_cdot_CZ_2 = (0..CZ_2.len())
283 .into_par_iter()
284 .map(|i| U1.u * CZ_2[i])
285 .collect::<Vec<G::Scalar>>();
286 let u_2_cdot_CZ_1 = (0..CZ_1.len())
287 .into_par_iter()
288 .map(|i| CZ_1[i])
289 .collect::<Vec<G::Scalar>>();
290
291 let T = AZ_1_circ_BZ_2
292 .par_iter()
293 .zip(&AZ_2_circ_BZ_1)
294 .zip(&u_1_cdot_CZ_2)
295 .zip(&u_2_cdot_CZ_1)
296 .map(|(((a, b), c), d)| *a + *b - *c - *d)
297 .collect::<Vec<G::Scalar>>();
298
299 let comm_T = T.commit(&gens.gens);
300
301 Ok((T, comm_T))
302 }
303
304 /// returns the digest of R1CSShape
305 pub fn get_digest(&self) -> G::Scalar {
306 self.digest
307 }
308
309 fn compute_digest(
310 num_cons: usize,
311 num_vars: usize,
312 num_io: usize,
313 A: &[(usize, usize, G::Scalar)],
314 B: &[(usize, usize, G::Scalar)],
315 C: &[(usize, usize, G::Scalar)],
316 ) -> G::Scalar {
317 let shape_serialized = R1CSShapeSerialized {
318 num_cons,
319 num_vars,
320 num_io,
321 A: A
322 .par_iter()
323 .map(|(i, j, v)| (*i, *j, v.to_repr().as_ref().to_vec()))
324 .collect(),
325 B: B
326 .par_iter()
327 .map(|(i, j, v)| (*i, *j, v.to_repr().as_ref().to_vec()))
328 .collect(),
329 C: C
330 .par_iter()
331 .map(|(i, j, v)| (*i, *j, v.to_repr().as_ref().to_vec()))
332 .collect(),
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_serialized).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
437#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
438struct R1CSShapeSerialized {
439 num_cons: usize,
440 num_vars: usize,
441 num_io: usize,
442 A: Vec<(usize, usize, Vec<u8>)>,
443 B: Vec<(usize, usize, Vec<u8>)>,
444 C: Vec<(usize, usize, Vec<u8>)>,
445}
446
447impl<G: Group> AppendToTranscriptTrait for R1CSShape<G> {
448 fn append_to_transcript(&self, _label: &'static [u8], transcript: &mut Transcript) {
449 self
450 .get_digest()
451 .append_to_transcript(b"R1CSShape", transcript);
452 }
453}
454
455impl<G: Group> AbsorbInROTrait<G> for R1CSShape<G> {
456 fn absorb_in_ro(&self, ro: &mut G::HashFunc) {
457 ro.absorb(scalar_as_base::<G>(self.get_digest()));
458 }
459}
460
461impl<G: Group> R1CSWitness<G> {
462 /// A method to create a witness object using a vector of scalars
463 pub fn new(S: &R1CSShape<G>, W: &[G::Scalar]) -> Result<R1CSWitness<G>, NovaError> {
464 if S.num_vars != W.len() {
465 Err(NovaError::InvalidWitnessLength)
466 } else {
467 Ok(R1CSWitness { W: W.to_owned() })
468 }
469 }
470
471 /// Commits to the witness using the supplied generators
472 pub fn commit(&self, gens: &R1CSGens<G>) -> Commitment<G> {
473 self.W.commit(&gens.gens)
474 }
475}
476
477impl<G: Group> R1CSInstance<G> {
478 /// A method to create an instance object using consitituent elements
479 pub fn new(
480 S: &R1CSShape<G>,
481 comm_W: &Commitment<G>,
482 X: &[G::Scalar],
483 ) -> Result<R1CSInstance<G>, NovaError> {
484 if S.num_io != X.len() {
485 Err(NovaError::InvalidInputLength)
486 } else {
487 Ok(R1CSInstance {
488 comm_W: *comm_W,
489 X: X.to_owned(),
490 })
491 }
492 }
493}
494
495impl<G: Group> AppendToTranscriptTrait for R1CSInstance<G> {
496 fn append_to_transcript(&self, _label: &'static [u8], transcript: &mut Transcript) {
497 self.comm_W.append_to_transcript(b"comm_W", transcript);
498 self.X.append_to_transcript(b"X", transcript);
499 }
500}
501
502impl<G: Group> AbsorbInROTrait<G> for R1CSInstance<G> {
503 fn absorb_in_ro(&self, ro: &mut G::HashFunc) {
504 self.comm_W.absorb_in_ro(ro);
505 for x in &self.X {
506 ro.absorb(scalar_as_base::<G>(*x));
507 }
508 }
509}
510
511impl<G: Group> RelaxedR1CSWitness<G> {
512 /// Produces a default RelaxedR1CSWitness given an R1CSShape
513 pub fn default(S: &R1CSShape<G>) -> RelaxedR1CSWitness<G> {
514 RelaxedR1CSWitness {
515 W: vec![G::Scalar::zero(); S.num_vars],
516 E: vec![G::Scalar::zero(); S.num_cons],
517 }
518 }
519
520 /// Initializes a new RelaxedR1CSWitness from an R1CSWitness
521 pub fn from_r1cs_witness(S: &R1CSShape<G>, witness: &R1CSWitness<G>) -> RelaxedR1CSWitness<G> {
522 RelaxedR1CSWitness {
523 W: witness.W.clone(),
524 E: vec![G::Scalar::zero(); S.num_cons],
525 }
526 }
527
528 /// Commits to the witness using the supplied generators
529 pub fn commit(&self, gens: &R1CSGens<G>) -> (Commitment<G>, Commitment<G>) {
530 (self.W.commit(&gens.gens), self.E.commit(&gens.gens))
531 }
532
533 /// Folds an incoming R1CSWitness into the current one
534 pub fn fold(
535 &self,
536 W2: &R1CSWitness<G>,
537 T: &[G::Scalar],
538 r: &G::Scalar,
539 ) -> Result<RelaxedR1CSWitness<G>, NovaError> {
540 let (W1, E1) = (&self.W, &self.E);
541 let W2 = &W2.W;
542
543 if W1.len() != W2.len() {
544 return Err(NovaError::InvalidWitnessLength);
545 }
546
547 let W = W1
548 .par_iter()
549 .zip(W2)
550 .map(|(a, b)| *a + *r * *b)
551 .collect::<Vec<G::Scalar>>();
552 let E = E1
553 .par_iter()
554 .zip(T)
555 .map(|(a, b)| *a + *r * *b)
556 .collect::<Vec<G::Scalar>>();
557 Ok(RelaxedR1CSWitness { W, E })
558 }
559
560 /// Pads the provided witness to the correct length
561 pub fn pad(&self, S: &R1CSShape<G>) -> RelaxedR1CSWitness<G> {
562 let W = {
563 let mut W = self.W.clone();
564 W.extend(vec![G::Scalar::zero(); S.num_vars - W.len()]);
565 W
566 };
567
568 let E = {
569 let mut E = self.E.clone();
570 E.extend(vec![G::Scalar::zero(); S.num_cons - E.len()]);
571 E
572 };
573
574 Self { W, E }
575 }
576}
577
578impl<G: Group> RelaxedR1CSInstance<G> {
579 /// Produces a default RelaxedR1CSInstance given R1CSGens and R1CSShape
580 pub fn default(gens: &R1CSGens<G>, S: &R1CSShape<G>) -> RelaxedR1CSInstance<G> {
581 let (comm_W, comm_E) = RelaxedR1CSWitness::default(S).commit(gens);
582 RelaxedR1CSInstance {
583 comm_W,
584 comm_E,
585 u: G::Scalar::zero(),
586 X: vec![G::Scalar::zero(); S.num_io],
587 }
588 }
589
590 /// Initializes a new RelaxedR1CSInstance from an R1CSInstance
591 pub fn from_r1cs_instance(
592 gens: &R1CSGens<G>,
593 S: &R1CSShape<G>,
594 instance: &R1CSInstance<G>,
595 ) -> RelaxedR1CSInstance<G> {
596 let mut r_instance = RelaxedR1CSInstance::default(gens, S);
597 r_instance.comm_W = instance.comm_W;
598 r_instance.u = G::Scalar::one();
599 r_instance.X = instance.X.clone();
600 r_instance
601 }
602
603 /// Folds an incoming RelaxedR1CSInstance into the current one
604 pub fn fold(
605 &self,
606 U2: &R1CSInstance<G>,
607 comm_T: &Commitment<G>,
608 r: &G::Scalar,
609 ) -> Result<RelaxedR1CSInstance<G>, NovaError> {
610 let (X1, u1, comm_W_1, comm_E_1) =
611 (&self.X, &self.u, &self.comm_W.clone(), &self.comm_E.clone());
612 let (X2, comm_W_2) = (&U2.X, &U2.comm_W);
613
614 // weighted sum of X, comm_W, comm_E, and u
615 let X = X1
616 .par_iter()
617 .zip(X2)
618 .map(|(a, b)| *a + *r * *b)
619 .collect::<Vec<G::Scalar>>();
620 let comm_W = comm_W_1 + comm_W_2 * r;
621 let comm_E = *comm_E_1 + *comm_T * *r;
622 let u = *u1 + *r;
623
624 Ok(RelaxedR1CSInstance {
625 comm_W,
626 comm_E,
627 X,
628 u,
629 })
630 }
631}
632
633impl<G: Group> AppendToTranscriptTrait for RelaxedR1CSInstance<G> {
634 fn append_to_transcript(&self, _label: &'static [u8], transcript: &mut Transcript) {
635 self.comm_W.append_to_transcript(b"comm_W", transcript);
636 self.comm_E.append_to_transcript(b"comm_E", transcript);
637 self.u.append_to_transcript(b"u", transcript);
638 self.X.append_to_transcript(b"X", transcript);
639 }
640}
641
642impl<G: Group> AbsorbInROTrait<G> for RelaxedR1CSInstance<G> {
643 fn absorb_in_ro(&self, ro: &mut G::HashFunc) {
644 self.comm_W.absorb_in_ro(ro);
645 self.comm_E.absorb_in_ro(ro);
646 ro.absorb(scalar_as_base::<G>(self.u));
647
648 // absorb each element of self.X in bignum format
649 for x in &self.X {
650 let limbs: Vec<G::Scalar> = nat_to_limbs(&f_to_nat(x), BN_LIMB_WIDTH, BN_N_LIMBS).unwrap();
651 for limb in limbs {
652 ro.absorb(scalar_as_base::<G>(limb));
653 }
654 }
655 }
656}