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},
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 itertools::concat;
18use rayon::prelude::*;
19use serde::{Deserialize, Serialize};
20
21/// Public parameters for a given R1CS
22#[derive(Clone, Serialize, Deserialize)]
23#[serde(bound = "")]
24pub struct R1CS<G: Group> {
25 _p: PhantomData<G>,
26}
27
28/// A type that holds the shape of the R1CS matrices
29#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
30pub struct R1CSShape<G: Group> {
31 pub(crate) num_cons: usize,
32 pub(crate) num_vars: usize,
33 pub(crate) num_io: usize,
34 pub(crate) A: Vec<(usize, usize, G::Scalar)>,
35 pub(crate) B: Vec<(usize, usize, G::Scalar)>,
36 pub(crate) C: Vec<(usize, usize, G::Scalar)>,
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> R1CS<G> {
71 /// Samples public parameters for the specified number of constraints and variables in an R1CS
72 pub fn commitment_key(S: &R1CSShape<G>) -> CommitmentKey<G> {
73 let num_cons = S.num_cons;
74 let num_vars = S.num_vars;
75 let total_nz = S.A.len() + S.B.len() + S.C.len();
76 G::CE::setup(b"ck", max(max(num_cons, num_vars), total_nz))
77 }
78}
79
80impl<G: Group> R1CSShape<G> {
81 /// Create an object of type `R1CSShape` from the explicitly specified R1CS matrices
82 pub fn new(
83 num_cons: usize,
84 num_vars: usize,
85 num_io: usize,
86 A: &[(usize, usize, G::Scalar)],
87 B: &[(usize, usize, G::Scalar)],
88 C: &[(usize, usize, G::Scalar)],
89 ) -> Result<R1CSShape<G>, NovaError> {
90 let is_valid = |num_cons: usize,
91 num_vars: usize,
92 num_io: usize,
93 M: &[(usize, usize, G::Scalar)]|
94 -> Result<(), NovaError> {
95 let res = (0..M.len())
96 .map(|i| {
97 let (row, col, _val) = M[i];
98 if row >= num_cons || col > num_io + num_vars {
99 Err(NovaError::InvalidIndex)
100 } else {
101 Ok(())
102 }
103 })
104 .collect::<Result<Vec<()>, NovaError>>();
105
106 if res.is_err() {
107 Err(NovaError::InvalidIndex)
108 } else {
109 Ok(())
110 }
111 };
112
113 let res_A = is_valid(num_cons, num_vars, num_io, A);
114 let res_B = is_valid(num_cons, num_vars, num_io, B);
115 let res_C = is_valid(num_cons, num_vars, num_io, C);
116
117 if res_A.is_err() || res_B.is_err() || res_C.is_err() {
118 return Err(NovaError::InvalidIndex);
119 }
120
121 // We require the number of public inputs/outputs to be even
122 if num_io % 2 != 0 {
123 return Err(NovaError::OddInputLength);
124 }
125
126 Ok(R1CSShape {
127 num_cons,
128 num_vars,
129 num_io,
130 A: A.to_owned(),
131 B: B.to_owned(),
132 C: C.to_owned(),
133 })
134 }
135
136 pub fn multiply_vec(
137 &self,
138 z: &[G::Scalar],
139 ) -> Result<(Vec<G::Scalar>, Vec<G::Scalar>, Vec<G::Scalar>), NovaError> {
140 if z.len() != self.num_io + self.num_vars + 1 {
141 return Err(NovaError::InvalidWitnessLength);
142 }
143
144 // computes a product between a sparse matrix `M` and a vector `z`
145 // This does not perform any validation of entries in M (e.g., if entries in `M` reference indexes outside the range of `z`)
146 // This is safe since we know that `M` is valid
147 let sparse_matrix_vec_product =
148 |M: &Vec<(usize, usize, G::Scalar)>, num_rows: usize, z: &[G::Scalar]| -> Vec<G::Scalar> {
149 (0..M.len())
150 .map(|i| {
151 let (row, col, val) = M[i];
152 (row, val * z[col])
153 })
154 .fold(vec![G::Scalar::ZERO; num_rows], |mut Mz, (r, v)| {
155 Mz[r] += v;
156 Mz
157 })
158 };
159
160 let (Az, (Bz, Cz)) = rayon::join(
161 || sparse_matrix_vec_product(&self.A, self.num_cons, z),
162 || {
163 rayon::join(
164 || sparse_matrix_vec_product(&self.B, self.num_cons, z),
165 || sparse_matrix_vec_product(&self.C, self.num_cons, z),
166 )
167 },
168 );
169
170 Ok((Az, Bz, Cz))
171 }
172
173 /// Checks if the Relaxed R1CS instance is satisfiable given a witness and its shape
174 pub fn is_sat_relaxed(
175 &self,
176 ck: &CommitmentKey<G>,
177 U: &RelaxedR1CSInstance<G>,
178 W: &RelaxedR1CSWitness<G>,
179 ) -> Result<(), NovaError> {
180 assert_eq!(W.W.len(), self.num_vars);
181 assert_eq!(W.E.len(), self.num_cons);
182 assert_eq!(U.X.len(), self.num_io);
183
184 // verify if Az * Bz = u*Cz + E
185 let res_eq: bool = {
186 let z = concat(vec![W.W.clone(), vec![U.u], U.X.clone()]);
187 let (Az, Bz, Cz) = self.multiply_vec(&z)?;
188 assert_eq!(Az.len(), self.num_cons);
189 assert_eq!(Bz.len(), self.num_cons);
190 assert_eq!(Cz.len(), self.num_cons);
191
192 let res: usize = (0..self.num_cons)
193 .map(|i| usize::from(Az[i] * Bz[i] != U.u * Cz[i] + W.E[i]))
194 .sum();
195
196 res == 0
197 };
198
199 // verify if comm_E and comm_W are commitments to E and W
200 let res_comm: bool = {
201 let (comm_W, comm_E) =
202 rayon::join(|| CE::<G>::commit(ck, &W.W), || CE::<G>::commit(ck, &W.E));
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 ck: &CommitmentKey<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 == CE::<G>::commit(ck, &W.W);
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 ck: &CommitmentKey<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 = CE::<G>::commit(ck, &T);
294
295 Ok((T, comm_T))
296 }
297
298 /// Pads the R1CSShape so that the number of variables is a power of two
299 /// Renumbers variables to accomodate padded variables
300 pub fn pad(&self) -> Self {
301 // equalize the number of variables and constraints
302 let m = max(self.num_vars, self.num_cons).next_power_of_two();
303
304 // check if the provided R1CSShape is already as required
305 if self.num_vars == m && self.num_cons == m {
306 return self.clone();
307 }
308
309 // check if the number of variables are as expected, then
310 // we simply set the number of constraints to the next power of two
311 if self.num_vars == m {
312 return R1CSShape {
313 num_cons: m,
314 num_vars: m,
315 num_io: self.num_io,
316 A: self.A.clone(),
317 B: self.B.clone(),
318 C: self.C.clone(),
319 };
320 }
321
322 // otherwise, we need to pad the number of variables and renumber variable accesses
323 let num_vars_padded = m;
324 let num_cons_padded = m;
325 let apply_pad = |M: &[(usize, usize, G::Scalar)]| -> Vec<(usize, usize, G::Scalar)> {
326 M.par_iter()
327 .map(|(r, c, v)| {
328 (
329 *r,
330 if c >= &self.num_vars {
331 c + num_vars_padded - self.num_vars
332 } else {
333 *c
334 },
335 *v,
336 )
337 })
338 .collect::<Vec<_>>()
339 };
340
341 let A_padded = apply_pad(&self.A);
342 let B_padded = apply_pad(&self.B);
343 let C_padded = apply_pad(&self.C);
344
345 R1CSShape {
346 num_cons: num_cons_padded,
347 num_vars: num_vars_padded,
348 num_io: self.num_io,
349 A: A_padded,
350 B: B_padded,
351 C: C_padded,
352 }
353 }
354}
355
356impl<G: Group> R1CSWitness<G> {
357 /// A method to create a witness object using a vector of scalars
358 pub fn new(S: &R1CSShape<G>, W: &[G::Scalar]) -> Result<R1CSWitness<G>, NovaError> {
359 if S.num_vars != W.len() {
360 Err(NovaError::InvalidWitnessLength)
361 } else {
362 Ok(R1CSWitness { W: W.to_owned() })
363 }
364 }
365
366 /// Commits to the witness using the supplied generators
367 pub fn commit(&self, ck: &CommitmentKey<G>) -> Commitment<G> {
368 CE::<G>::commit(ck, &self.W)
369 }
370}
371
372impl<G: Group> R1CSInstance<G> {
373 /// A method to create an instance object using consitituent elements
374 pub fn new(
375 S: &R1CSShape<G>,
376 comm_W: &Commitment<G>,
377 X: &[G::Scalar],
378 ) -> Result<R1CSInstance<G>, NovaError> {
379 if S.num_io != X.len() {
380 Err(NovaError::InvalidInputLength)
381 } else {
382 Ok(R1CSInstance {
383 comm_W: *comm_W,
384 X: X.to_owned(),
385 })
386 }
387 }
388}
389
390impl<G: Group> AbsorbInROTrait<G> for R1CSInstance<G> {
391 fn absorb_in_ro(&self, ro: &mut G::RO) {
392 self.comm_W.absorb_in_ro(ro);
393 for x in &self.X {
394 ro.absorb(scalar_as_base::<G>(*x));
395 }
396 }
397}
398
399impl<G: Group> RelaxedR1CSWitness<G> {
400 /// Produces a default RelaxedR1CSWitness given an R1CSShape
401 pub fn default(S: &R1CSShape<G>) -> RelaxedR1CSWitness<G> {
402 RelaxedR1CSWitness {
403 W: vec![G::Scalar::ZERO; S.num_vars],
404 E: vec![G::Scalar::ZERO; S.num_cons],
405 }
406 }
407
408 /// Initializes a new RelaxedR1CSWitness from an R1CSWitness
409 pub fn from_r1cs_witness(S: &R1CSShape<G>, witness: &R1CSWitness<G>) -> RelaxedR1CSWitness<G> {
410 RelaxedR1CSWitness {
411 W: witness.W.clone(),
412 E: vec![G::Scalar::ZERO; S.num_cons],
413 }
414 }
415
416 /// Commits to the witness using the supplied generators
417 pub fn commit(&self, ck: &CommitmentKey<G>) -> (Commitment<G>, Commitment<G>) {
418 (CE::<G>::commit(ck, &self.W), CE::<G>::commit(ck, &self.E))
419 }
420
421 /// Folds an incoming R1CSWitness into the current one
422 pub fn fold(
423 &self,
424 W2: &R1CSWitness<G>,
425 T: &[G::Scalar],
426 r: &G::Scalar,
427 ) -> Result<RelaxedR1CSWitness<G>, NovaError> {
428 let (W1, E1) = (&self.W, &self.E);
429 let W2 = &W2.W;
430
431 if W1.len() != W2.len() {
432 return Err(NovaError::InvalidWitnessLength);
433 }
434
435 let W = W1
436 .par_iter()
437 .zip(W2)
438 .map(|(a, b)| *a + *r * *b)
439 .collect::<Vec<G::Scalar>>();
440 let E = E1
441 .par_iter()
442 .zip(T)
443 .map(|(a, b)| *a + *r * *b)
444 .collect::<Vec<G::Scalar>>();
445 Ok(RelaxedR1CSWitness { W, E })
446 }
447
448 /// Pads the provided witness to the correct length
449 pub fn pad(&self, S: &R1CSShape<G>) -> RelaxedR1CSWitness<G> {
450 let W = {
451 let mut W = self.W.clone();
452 W.extend(vec![G::Scalar::ZERO; S.num_vars - W.len()]);
453 W
454 };
455
456 let E = {
457 let mut E = self.E.clone();
458 E.extend(vec![G::Scalar::ZERO; S.num_cons - E.len()]);
459 E
460 };
461
462 Self { W, E }
463 }
464}
465
466impl<G: Group> RelaxedR1CSInstance<G> {
467 /// Produces a default RelaxedR1CSInstance given R1CSGens and R1CSShape
468 pub fn default(_ck: &CommitmentKey<G>, S: &R1CSShape<G>) -> RelaxedR1CSInstance<G> {
469 let (comm_W, comm_E) = (Commitment::<G>::default(), Commitment::<G>::default());
470 RelaxedR1CSInstance {
471 comm_W,
472 comm_E,
473 u: G::Scalar::ZERO,
474 X: vec![G::Scalar::ZERO; S.num_io],
475 }
476 }
477
478 /// Initializes a new RelaxedR1CSInstance from an R1CSInstance
479 pub fn from_r1cs_instance(
480 ck: &CommitmentKey<G>,
481 S: &R1CSShape<G>,
482 instance: &R1CSInstance<G>,
483 ) -> RelaxedR1CSInstance<G> {
484 let mut r_instance = RelaxedR1CSInstance::default(ck, S);
485 r_instance.comm_W = instance.comm_W;
486 r_instance.u = G::Scalar::ONE;
487 r_instance.X = instance.X.clone();
488 r_instance
489 }
490
491 /// Initializes a new RelaxedR1CSInstance from an R1CSInstance
492 pub fn from_r1cs_instance_unchecked(
493 comm_W: &Commitment<G>,
494 X: &[G::Scalar],
495 ) -> RelaxedR1CSInstance<G> {
496 RelaxedR1CSInstance {
497 comm_W: *comm_W,
498 comm_E: Commitment::<G>::default(),
499 u: G::Scalar::ONE,
500 X: X.to_vec(),
501 }
502 }
503
504 /// Folds an incoming RelaxedR1CSInstance into the current one
505 pub fn fold(
506 &self,
507 U2: &R1CSInstance<G>,
508 comm_T: &Commitment<G>,
509 r: &G::Scalar,
510 ) -> Result<RelaxedR1CSInstance<G>, NovaError> {
511 let (X1, u1, comm_W_1, comm_E_1) =
512 (&self.X, &self.u, &self.comm_W.clone(), &self.comm_E.clone());
513 let (X2, comm_W_2) = (&U2.X, &U2.comm_W);
514
515 // weighted sum of X, comm_W, comm_E, and u
516 let X = X1
517 .par_iter()
518 .zip(X2)
519 .map(|(a, b)| *a + *r * *b)
520 .collect::<Vec<G::Scalar>>();
521 let comm_W = *comm_W_1 + *comm_W_2 * *r;
522 let comm_E = *comm_E_1 + *comm_T * *r;
523 let u = *u1 + *r;
524
525 Ok(RelaxedR1CSInstance {
526 comm_W,
527 comm_E,
528 X,
529 u,
530 })
531 }
532}
533
534impl<G: Group> TranscriptReprTrait<G> for RelaxedR1CSInstance<G> {
535 fn to_transcript_bytes(&self) -> Vec<u8> {
536 [
537 self.comm_W.to_transcript_bytes(),
538 self.comm_E.to_transcript_bytes(),
539 self.u.to_transcript_bytes(),
540 self.X.as_slice().to_transcript_bytes(),
541 ]
542 .concat()
543 }
544}
545
546impl<G: Group> AbsorbInROTrait<G> for RelaxedR1CSInstance<G> {
547 fn absorb_in_ro(&self, ro: &mut G::RO) {
548 self.comm_W.absorb_in_ro(ro);
549 self.comm_E.absorb_in_ro(ro);
550 ro.absorb(scalar_as_base::<G>(self.u));
551
552 // absorb each element of self.X in bignum format
553 for x in &self.X {
554 let limbs: Vec<G::Scalar> = nat_to_limbs(&f_to_nat(x), BN_LIMB_WIDTH, BN_N_LIMBS).unwrap();
555 for limb in limbs {
556 ro.absorb(scalar_as_base::<G>(limb));
557 }
558 }
559 }
560}