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 ff::{Field, PrimeField};
12use flate2::{write::ZlibEncoder, Compression};
13use itertools::concat;
14use merlin::Transcript;
15use rayon::prelude::*;
16use serde::{Deserialize, Serialize};
17use sha3::{Digest, Sha3_256};
18
19/// Public parameters for a given R1CS
20pub struct R1CSGens<G: Group> {
21 pub(crate) gens_W: CommitGens<G>, // TODO: avoid pub(crate)
22 pub(crate) gens_E: CommitGens<G>,
23}
24
25/// A type that holds the shape of the R1CS matrices
26#[derive(Clone, Debug, PartialEq, Eq)]
27pub struct R1CSShape<G: Group> {
28 num_cons: usize,
29 num_vars: usize,
30 num_io: usize,
31 A: Vec<(usize, usize, G::Scalar)>,
32 B: Vec<(usize, usize, G::Scalar)>,
33 C: Vec<(usize, usize, G::Scalar)>,
34 digest: G::Scalar, // digest of the rest of R1CSShape
35}
36
37/// A type that holds a witness for a given R1CS instance
38#[derive(Clone, Debug, PartialEq, Eq)]
39pub struct R1CSWitness<G: Group> {
40 W: Vec<G::Scalar>,
41}
42
43/// A type that holds an R1CS instance
44#[derive(Clone, Debug, PartialEq, Eq)]
45pub struct R1CSInstance<G: Group> {
46 pub(crate) comm_W: Commitment<G>,
47 pub(crate) X: Vec<G::Scalar>,
48}
49
50/// A type that holds a witness for a given Relaxed R1CS instance
51#[derive(Clone, Debug, PartialEq, Eq)]
52pub struct RelaxedR1CSWitness<G: Group> {
53 W: Vec<G::Scalar>,
54 E: Vec<G::Scalar>,
55}
56
57/// A type that holds a Relaxed R1CS instance
58#[derive(Clone, Debug, PartialEq, Eq)]
59pub struct RelaxedR1CSInstance<G: Group> {
60 pub(crate) comm_W: Commitment<G>,
61 pub(crate) comm_E: Commitment<G>,
62 pub(crate) X: Vec<G::Scalar>,
63 pub(crate) u: G::Scalar,
64}
65
66impl<G: Group> R1CSGens<G> {
67 /// Samples public parameters for the specified number of constraints and variables in an R1CS
68 pub fn new(num_cons: usize, num_vars: usize) -> R1CSGens<G> {
69 // generators to commit to witness vector `W`
70 let gens_W = CommitGens::new(b"gens_W", num_vars);
71
72 // generators to commit to the error/slack vector `E`
73 let gens_E = CommitGens::new(b"gens_E", num_cons);
74
75 R1CSGens { gens_E, gens_W }
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 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 = sparse_matrix_vec_product(&self.A, self.num_cons, z);
165 let Bz = sparse_matrix_vec_product(&self.B, self.num_cons, z);
166 let Cz = sparse_matrix_vec_product(&self.C, self.num_cons, z);
167
168 Ok((Az, Bz, Cz))
169 }
170
171 /// Checks if the Relaxed R1CS instance is satisfiable given a witness and its shape
172 pub fn is_sat_relaxed(
173 &self,
174 gens: &R1CSGens<G>,
175 U: &RelaxedR1CSInstance<G>,
176 W: &RelaxedR1CSWitness<G>,
177 ) -> Result<(), NovaError> {
178 assert_eq!(W.W.len(), self.num_vars);
179 assert_eq!(W.E.len(), self.num_cons);
180 assert_eq!(U.X.len(), self.num_io);
181
182 // verify if Az * Bz = u*Cz + E
183 let res_eq: bool = {
184 let z = concat(vec![W.W.clone(), vec![U.u], U.X.clone()]);
185 let (Az, Bz, Cz) = self.multiply_vec(&z)?;
186 assert_eq!(Az.len(), self.num_cons);
187 assert_eq!(Bz.len(), self.num_cons);
188 assert_eq!(Cz.len(), self.num_cons);
189
190 let res: usize = (0..self.num_cons)
191 .map(|i| {
192 if Az[i] * Bz[i] == U.u * Cz[i] + W.E[i] {
193 0
194 } else {
195 1
196 }
197 })
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 = W.W.commit(&gens.gens_W);
206 let comm_E = W.E.commit(&gens.gens_E);
207
208 U.comm_W == comm_W && U.comm_E == comm_E
209 };
210
211 if res_eq && res_comm {
212 Ok(())
213 } else {
214 Err(NovaError::UnSat)
215 }
216 }
217
218 /// Checks if the R1CS instance is satisfiable given a witness and its shape
219 pub fn is_sat(
220 &self,
221 gens: &R1CSGens<G>,
222 U: &R1CSInstance<G>,
223 W: &R1CSWitness<G>,
224 ) -> Result<(), NovaError> {
225 assert_eq!(W.W.len(), self.num_vars);
226 assert_eq!(U.X.len(), self.num_io);
227
228 // verify if Az * Bz = u*Cz
229 let res_eq: bool = {
230 let z = concat(vec![W.W.clone(), vec![G::Scalar::one()], U.X.clone()]);
231 let (Az, Bz, Cz) = self.multiply_vec(&z)?;
232 assert_eq!(Az.len(), self.num_cons);
233 assert_eq!(Bz.len(), self.num_cons);
234 assert_eq!(Cz.len(), self.num_cons);
235
236 let res: usize = (0..self.num_cons)
237 .map(|i| if Az[i] * Bz[i] == Cz[i] { 0 } else { 1 })
238 .sum();
239
240 res == 0
241 };
242
243 // verify if comm_W is a commitment to W
244 let res_comm: bool = U.comm_W == W.W.commit(&gens.gens_W);
245
246 if res_eq && res_comm {
247 Ok(())
248 } else {
249 Err(NovaError::UnSat)
250 }
251 }
252
253 /// A method to compute a commitment to the cross-term `T` given a
254 /// Relaxed R1CS instance-witness pair and an R1CS instance-witness pair
255 pub fn commit_T(
256 &self,
257 gens: &R1CSGens<G>,
258 U1: &RelaxedR1CSInstance<G>,
259 W1: &RelaxedR1CSWitness<G>,
260 U2: &R1CSInstance<G>,
261 W2: &R1CSWitness<G>,
262 ) -> Result<(Vec<G::Scalar>, Commitment<G>), NovaError> {
263 let (AZ_1, BZ_1, CZ_1) = {
264 let Z1 = concat(vec![W1.W.clone(), vec![U1.u], U1.X.clone()]);
265 self.multiply_vec(&Z1)?
266 };
267
268 let (AZ_2, BZ_2, CZ_2) = {
269 let Z2 = concat(vec![W2.W.clone(), vec![G::Scalar::one()], U2.X.clone()]);
270 self.multiply_vec(&Z2)?
271 };
272
273 let AZ_1_circ_BZ_2 = (0..AZ_1.len())
274 .map(|i| AZ_1[i] * BZ_2[i])
275 .collect::<Vec<G::Scalar>>();
276 let AZ_2_circ_BZ_1 = (0..AZ_2.len())
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 .map(|i| U1.u * CZ_2[i])
281 .collect::<Vec<G::Scalar>>();
282 let u_2_cdot_CZ_1 = (0..CZ_1.len()).map(|i| CZ_1[i]).collect::<Vec<G::Scalar>>();
283
284 let T = AZ_1_circ_BZ_2
285 .par_iter()
286 .zip(&AZ_2_circ_BZ_1)
287 .zip(&u_1_cdot_CZ_2)
288 .zip(&u_2_cdot_CZ_1)
289 .map(|(((a, b), c), d)| *a + *b - *c - *d)
290 .collect::<Vec<G::Scalar>>();
291
292 let comm_T = T.commit(&gens.gens_E);
293
294 Ok((T, comm_T))
295 }
296
297 /// returns the digest of R1CSShape
298 pub fn get_digest(&self) -> G::Scalar {
299 self.digest
300 }
301
302 fn compute_digest(
303 num_cons: usize,
304 num_vars: usize,
305 num_io: usize,
306 A: &[(usize, usize, G::Scalar)],
307 B: &[(usize, usize, G::Scalar)],
308 C: &[(usize, usize, G::Scalar)],
309 ) -> G::Scalar {
310 let shape_serialized = R1CSShapeSerialized {
311 num_cons,
312 num_vars,
313 num_io,
314 A: A
315 .iter()
316 .map(|(i, j, v)| (*i, *j, v.to_repr().as_ref().to_vec()))
317 .collect(),
318 B: B
319 .iter()
320 .map(|(i, j, v)| (*i, *j, v.to_repr().as_ref().to_vec()))
321 .collect(),
322 C: C
323 .iter()
324 .map(|(i, j, v)| (*i, *j, v.to_repr().as_ref().to_vec()))
325 .collect(),
326 };
327
328 // obtain a vector of bytes representing the R1CS shape
329 let mut encoder = ZlibEncoder::new(Vec::new(), Compression::default());
330 bincode::serialize_into(&mut encoder, &shape_serialized).unwrap();
331 let shape_bytes = encoder.finish().unwrap();
332
333 // convert shape_bytes into a short digest
334 let mut hasher = Sha3_256::new();
335 hasher.input(&shape_bytes);
336 let digest = hasher.result();
337
338 // truncate the digest to 250 bits
339 let bv = (0..NUM_HASH_BITS).map(|i| {
340 let (byte_pos, bit_pos) = (i / 8, i % 8);
341 let bit = (digest[byte_pos] >> bit_pos) & 1;
342 bit == 1
343 });
344
345 // turn the bit vector into a scalar
346 let mut res = G::Scalar::zero();
347 let mut coeff = G::Scalar::one();
348 for bit in bv {
349 if bit {
350 res += coeff;
351 }
352 coeff += coeff;
353 }
354 res
355 }
356}
357
358#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
359struct R1CSShapeSerialized {
360 num_cons: usize,
361 num_vars: usize,
362 num_io: usize,
363 A: Vec<(usize, usize, Vec<u8>)>,
364 B: Vec<(usize, usize, Vec<u8>)>,
365 C: Vec<(usize, usize, Vec<u8>)>,
366}
367
368impl<G: Group> AppendToTranscriptTrait for R1CSShape<G> {
369 fn append_to_transcript(&self, _label: &'static [u8], transcript: &mut Transcript) {
370 self
371 .get_digest()
372 .append_to_transcript(b"R1CSShape", transcript);
373 }
374}
375
376impl<G: Group> AbsorbInROTrait<G> for R1CSShape<G> {
377 fn absorb_in_ro(&self, ro: &mut G::HashFunc) {
378 ro.absorb(scalar_as_base::<G>(self.get_digest()));
379 }
380}
381
382impl<G: Group> R1CSWitness<G> {
383 /// A method to create a witness object using a vector of scalars
384 pub fn new(S: &R1CSShape<G>, W: &[G::Scalar]) -> Result<R1CSWitness<G>, NovaError> {
385 if S.num_vars != W.len() {
386 Err(NovaError::InvalidWitnessLength)
387 } else {
388 Ok(R1CSWitness { W: W.to_owned() })
389 }
390 }
391
392 /// Commits to the witness using the supplied generators
393 pub fn commit(&self, gens: &R1CSGens<G>) -> Commitment<G> {
394 self.W.commit(&gens.gens_W)
395 }
396}
397
398impl<G: Group> R1CSInstance<G> {
399 /// A method to create an instance object using consitituent elements
400 pub fn new(
401 S: &R1CSShape<G>,
402 comm_W: &Commitment<G>,
403 X: &[G::Scalar],
404 ) -> Result<R1CSInstance<G>, NovaError> {
405 if S.num_io != X.len() {
406 Err(NovaError::InvalidInputLength)
407 } else {
408 Ok(R1CSInstance {
409 comm_W: *comm_W,
410 X: X.to_owned(),
411 })
412 }
413 }
414}
415
416impl<G: Group> AppendToTranscriptTrait for R1CSInstance<G> {
417 fn append_to_transcript(&self, _label: &'static [u8], transcript: &mut Transcript) {
418 self.comm_W.append_to_transcript(b"comm_W", transcript);
419 self.X.append_to_transcript(b"X", transcript);
420 }
421}
422
423impl<G: Group> AbsorbInROTrait<G> for R1CSInstance<G> {
424 fn absorb_in_ro(&self, ro: &mut G::HashFunc) {
425 self.comm_W.absorb_in_ro(ro);
426 for x in &self.X {
427 ro.absorb(scalar_as_base::<G>(*x));
428 }
429 }
430}
431
432impl<G: Group> RelaxedR1CSWitness<G> {
433 /// Produces a default RelaxedR1CSWitness given an R1CSShape
434 pub fn default(S: &R1CSShape<G>) -> RelaxedR1CSWitness<G> {
435 RelaxedR1CSWitness {
436 W: vec![G::Scalar::zero(); S.num_vars],
437 E: vec![G::Scalar::zero(); S.num_cons],
438 }
439 }
440
441 /// Initializes a new RelaxedR1CSWitness from an R1CSWitness
442 pub fn from_r1cs_witness(S: &R1CSShape<G>, witness: &R1CSWitness<G>) -> RelaxedR1CSWitness<G> {
443 RelaxedR1CSWitness {
444 W: witness.W.clone(),
445 E: vec![G::Scalar::zero(); S.num_cons],
446 }
447 }
448
449 /// Commits to the witness using the supplied generators
450 pub fn commit(&self, gens: &R1CSGens<G>) -> (Commitment<G>, Commitment<G>) {
451 (self.W.commit(&gens.gens_W), self.E.commit(&gens.gens_E))
452 }
453
454 /// Folds an incoming R1CSWitness into the current one
455 pub fn fold(
456 &self,
457 W2: &R1CSWitness<G>,
458 T: &[G::Scalar],
459 r: &G::Scalar,
460 ) -> Result<RelaxedR1CSWitness<G>, NovaError> {
461 let (W1, E1) = (&self.W, &self.E);
462 let W2 = &W2.W;
463
464 if W1.len() != W2.len() {
465 return Err(NovaError::InvalidWitnessLength);
466 }
467
468 let W = W1
469 .par_iter()
470 .zip(W2)
471 .map(|(a, b)| *a + *r * *b)
472 .collect::<Vec<G::Scalar>>();
473 let E = E1
474 .par_iter()
475 .zip(T)
476 .map(|(a, b)| *a + *r * *b)
477 .collect::<Vec<G::Scalar>>();
478 Ok(RelaxedR1CSWitness { W, E })
479 }
480}
481
482impl<G: Group> RelaxedR1CSInstance<G> {
483 /// Produces a default RelaxedR1CSInstance given R1CSGens and R1CSShape
484 pub fn default(gens: &R1CSGens<G>, S: &R1CSShape<G>) -> RelaxedR1CSInstance<G> {
485 let (comm_W, comm_E) = RelaxedR1CSWitness::default(S).commit(gens);
486 RelaxedR1CSInstance {
487 comm_W,
488 comm_E,
489 u: G::Scalar::zero(),
490 X: vec![G::Scalar::zero(); S.num_io],
491 }
492 }
493
494 /// Initializes a new RelaxedR1CSInstance from an R1CSInstance
495 pub fn from_r1cs_instance(
496 gens: &R1CSGens<G>,
497 S: &R1CSShape<G>,
498 instance: &R1CSInstance<G>,
499 ) -> RelaxedR1CSInstance<G> {
500 let mut r_instance = RelaxedR1CSInstance::default(gens, S);
501 r_instance.comm_W = instance.comm_W;
502 r_instance.u = G::Scalar::one();
503 r_instance.X = instance.X.clone();
504 r_instance
505 }
506
507 /// Folds an incoming RelaxedR1CSInstance into the current one
508 pub fn fold(
509 &self,
510 U2: &R1CSInstance<G>,
511 comm_T: &Commitment<G>,
512 r: &G::Scalar,
513 ) -> Result<RelaxedR1CSInstance<G>, NovaError> {
514 let (X1, u1, comm_W_1, comm_E_1) =
515 (&self.X, &self.u, &self.comm_W.clone(), &self.comm_E.clone());
516 let (X2, comm_W_2) = (&U2.X, &U2.comm_W);
517
518 // weighted sum of X, comm_W, comm_E, and u
519 let X = X1
520 .par_iter()
521 .zip(X2)
522 .map(|(a, b)| *a + *r * *b)
523 .collect::<Vec<G::Scalar>>();
524 let comm_W = comm_W_1 + comm_W_2 * r;
525 let comm_E = *comm_E_1 + *comm_T * *r;
526 let u = *u1 + *r;
527
528 Ok(RelaxedR1CSInstance {
529 comm_W,
530 comm_E,
531 X,
532 u,
533 })
534 }
535}
536
537impl<G: Group> AppendToTranscriptTrait for RelaxedR1CSInstance<G> {
538 fn append_to_transcript(&self, _label: &'static [u8], transcript: &mut Transcript) {
539 self.comm_W.append_to_transcript(b"comm_W", transcript);
540 self.comm_E.append_to_transcript(b"comm_E", transcript);
541 self.u.append_to_transcript(b"u", transcript);
542 self.X.append_to_transcript(b"X", transcript);
543 }
544}
545
546impl<G: Group> AbsorbInROTrait<G> for RelaxedR1CSInstance<G> {
547 fn absorb_in_ro(&self, ro: &mut G::HashFunc) {
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}