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