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