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}
35
36/// A type that holds a witness for a given R1CS instance
37#[derive(Clone, Debug, PartialEq, Eq)]
38pub struct R1CSWitness<G: Group> {
39 W: Vec<G::Scalar>,
40}
41
42/// A type that holds an R1CS instance
43#[derive(Clone, Debug, PartialEq, Eq)]
44pub struct R1CSInstance<G: Group> {
45 pub(crate) comm_W: Commitment<G>,
46 pub(crate) X: Vec<G::Scalar>,
47}
48
49/// A type that holds a witness for a given Relaxed R1CS instance
50#[derive(Clone, Debug, PartialEq, Eq)]
51pub struct RelaxedR1CSWitness<G: Group> {
52 W: Vec<G::Scalar>,
53 E: Vec<G::Scalar>,
54}
55
56/// A type that holds a Relaxed R1CS instance
57#[derive(Clone, Debug, PartialEq, Eq)]
58pub struct RelaxedR1CSInstance<G: Group> {
59 pub(crate) comm_W: Commitment<G>,
60 pub(crate) comm_E: Commitment<G>,
61 pub(crate) X: Vec<G::Scalar>,
62 pub(crate) u: G::Scalar,
63}
64
65impl<G: Group> R1CSGens<G> {
66 /// Samples public parameters for the specified number of constraints and variables in an R1CS
67 pub fn new(num_cons: usize, num_vars: usize) -> R1CSGens<G> {
68 // generators to commit to witness vector `W`
69 let gens_W = CommitGens::new(b"gens_W", num_vars);
70
71 // generators to commit to the error/slack vector `E`
72 let gens_E = CommitGens::new(b"gens_E", num_cons);
73
74 R1CSGens { gens_E, gens_W }
75 }
76}
77
78impl<G: Group> R1CSShape<G> {
79 /// Create an object of type `R1CSShape` from the explicitly specified R1CS matrices
80 pub fn new(
81 num_cons: usize,
82 num_vars: usize,
83 num_io: usize,
84 A: &[(usize, usize, G::Scalar)],
85 B: &[(usize, usize, G::Scalar)],
86 C: &[(usize, usize, G::Scalar)],
87 ) -> Result<R1CSShape<G>, NovaError> {
88 let is_valid = |num_cons: usize,
89 num_vars: usize,
90 num_io: usize,
91 M: &[(usize, usize, G::Scalar)]|
92 -> Result<(), NovaError> {
93 let res = (0..M.len())
94 .map(|i| {
95 let (row, col, _val) = M[i];
96 if row >= num_cons || col > num_io + num_vars {
97 Err(NovaError::InvalidIndex)
98 } else {
99 Ok(())
100 }
101 })
102 .collect::<Result<Vec<()>, NovaError>>();
103
104 if res.is_err() {
105 Err(NovaError::InvalidIndex)
106 } else {
107 Ok(())
108 }
109 };
110
111 let res_A = is_valid(num_cons, num_vars, num_io, A);
112 let res_B = is_valid(num_cons, num_vars, num_io, B);
113 let res_C = is_valid(num_cons, num_vars, num_io, C);
114
115 if res_A.is_err() || res_B.is_err() || res_C.is_err() {
116 return Err(NovaError::InvalidIndex);
117 }
118
119 // We require the number of public inputs/outputs to be even
120 if num_io % 2 != 0 {
121 return Err(NovaError::OddInputLength);
122 }
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 };
132
133 Ok(shape)
134 }
135
136 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 = sparse_matrix_vec_product(&self.A, self.num_cons, z);
161 let Bz = sparse_matrix_vec_product(&self.B, self.num_cons, z);
162 let Cz = sparse_matrix_vec_product(&self.C, self.num_cons, z);
163
164 Ok((Az, Bz, Cz))
165 }
166
167 /// Checks if the Relaxed R1CS instance is satisfiable given a witness and its shape
168 pub fn is_sat_relaxed(
169 &self,
170 gens: &R1CSGens<G>,
171 U: &RelaxedR1CSInstance<G>,
172 W: &RelaxedR1CSWitness<G>,
173 ) -> Result<(), NovaError> {
174 assert_eq!(W.W.len(), self.num_vars);
175 assert_eq!(W.E.len(), self.num_cons);
176 assert_eq!(U.X.len(), self.num_io);
177
178 // verify if Az * Bz = u*Cz + E
179 let res_eq: bool = {
180 let z = concat(vec![W.W.clone(), vec![U.u], U.X.clone()]);
181 let (Az, Bz, Cz) = self.multiply_vec(&z)?;
182 assert_eq!(Az.len(), self.num_cons);
183 assert_eq!(Bz.len(), self.num_cons);
184 assert_eq!(Cz.len(), self.num_cons);
185
186 let res: usize = (0..self.num_cons)
187 .map(|i| {
188 if Az[i] * Bz[i] == U.u * Cz[i] + W.E[i] {
189 0
190 } else {
191 1
192 }
193 })
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 = W.W.commit(&gens.gens_W);
202 let comm_E = W.E.commit(&gens.gens_E);
203
204 U.comm_W == comm_W && U.comm_E == comm_E
205 };
206
207 if res_eq && res_comm {
208 Ok(())
209 } else {
210 Err(NovaError::UnSat)
211 }
212 }
213
214 /// Checks if the R1CS instance is satisfiable given a witness and its shape
215 pub fn is_sat(
216 &self,
217 gens: &R1CSGens<G>,
218 U: &R1CSInstance<G>,
219 W: &R1CSWitness<G>,
220 ) -> Result<(), NovaError> {
221 assert_eq!(W.W.len(), self.num_vars);
222 assert_eq!(U.X.len(), self.num_io);
223
224 // verify if Az * Bz = u*Cz
225 let res_eq: bool = {
226 let z = concat(vec![W.W.clone(), vec![G::Scalar::one()], U.X.clone()]);
227 let (Az, Bz, Cz) = self.multiply_vec(&z)?;
228 assert_eq!(Az.len(), self.num_cons);
229 assert_eq!(Bz.len(), self.num_cons);
230 assert_eq!(Cz.len(), self.num_cons);
231
232 let res: usize = (0..self.num_cons)
233 .map(|i| if Az[i] * Bz[i] == Cz[i] { 0 } else { 1 })
234 .sum();
235
236 res == 0
237 };
238
239 // verify if comm_W is a commitment to W
240 let res_comm: bool = U.comm_W == W.W.commit(&gens.gens_W);
241
242 if res_eq && res_comm {
243 Ok(())
244 } else {
245 Err(NovaError::UnSat)
246 }
247 }
248
249 /// A method to compute a commitment to the cross-term `T` given a
250 /// Relaxed R1CS instance-witness pair and an R1CS instance-witness pair
251 pub fn commit_T(
252 &self,
253 gens: &R1CSGens<G>,
254 U1: &RelaxedR1CSInstance<G>,
255 W1: &RelaxedR1CSWitness<G>,
256 U2: &R1CSInstance<G>,
257 W2: &R1CSWitness<G>,
258 ) -> Result<(Vec<G::Scalar>, Commitment<G>), NovaError> {
259 let (AZ_1, BZ_1, CZ_1) = {
260 let Z1 = concat(vec![W1.W.clone(), vec![U1.u], U1.X.clone()]);
261 self.multiply_vec(&Z1)?
262 };
263
264 let (AZ_2, BZ_2, CZ_2) = {
265 let Z2 = concat(vec![W2.W.clone(), vec![G::Scalar::one()], U2.X.clone()]);
266 self.multiply_vec(&Z2)?
267 };
268
269 let AZ_1_circ_BZ_2 = (0..AZ_1.len())
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 .map(|i| AZ_2[i] * BZ_1[i])
274 .collect::<Vec<G::Scalar>>();
275 let u_1_cdot_CZ_2 = (0..CZ_2.len())
276 .map(|i| U1.u * CZ_2[i])
277 .collect::<Vec<G::Scalar>>();
278 let u_2_cdot_CZ_1 = (0..CZ_1.len()).map(|i| CZ_1[i]).collect::<Vec<G::Scalar>>();
279
280 let T = AZ_1_circ_BZ_2
281 .par_iter()
282 .zip(&AZ_2_circ_BZ_1)
283 .zip(&u_1_cdot_CZ_2)
284 .zip(&u_2_cdot_CZ_1)
285 .map(|(((a, b), c), d)| *a + *b - *c - *d)
286 .collect::<Vec<G::Scalar>>();
287
288 let comm_T = T.commit(&gens.gens_E);
289
290 Ok((T, comm_T))
291 }
292
293 /// returns the digest of R1CSShape
294 fn get_digest(&self) -> G::Scalar {
295 let shape_serialized = R1CSShapeSerialized {
296 num_cons: self.num_cons,
297 num_vars: self.num_vars,
298 num_io: self.num_io,
299 A: self
300 .A
301 .iter()
302 .map(|(i, j, v)| (*i, *j, v.to_repr().as_ref().to_vec()))
303 .collect(),
304 B: self
305 .B
306 .iter()
307 .map(|(i, j, v)| (*i, *j, v.to_repr().as_ref().to_vec()))
308 .collect(),
309 C: self
310 .C
311 .iter()
312 .map(|(i, j, v)| (*i, *j, v.to_repr().as_ref().to_vec()))
313 .collect(),
314 };
315
316 // obtain a vector of bytes representing the R1CS shape
317 let mut encoder = ZlibEncoder::new(Vec::new(), Compression::default());
318 bincode::serialize_into(&mut encoder, &shape_serialized).unwrap();
319 let shape_bytes = encoder.finish().unwrap();
320
321 // convert shape_bytes into a short digest
322 let mut hasher = Sha3_256::new();
323 hasher.input(&shape_bytes);
324 let shape_digest = hasher.result();
325
326 // truncate the digest to 250 bits
327 let bv = (0..NUM_HASH_BITS).map(|i| {
328 let (byte_pos, bit_pos) = (i / 8, i % 8);
329 let bit = (shape_digest[byte_pos] >> bit_pos) & 1;
330 bit == 1
331 });
332
333 // turn the bit vector into a scalar
334 let mut res = G::Scalar::zero();
335 let mut coeff = G::Scalar::one();
336 for bit in bv {
337 if bit {
338 res += coeff;
339 }
340 coeff += coeff;
341 }
342 res
343 }
344}
345
346#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
347struct R1CSShapeSerialized {
348 num_cons: usize,
349 num_vars: usize,
350 num_io: usize,
351 A: Vec<(usize, usize, Vec<u8>)>,
352 B: Vec<(usize, usize, Vec<u8>)>,
353 C: Vec<(usize, usize, Vec<u8>)>,
354}
355
356impl<G: Group> AppendToTranscriptTrait for R1CSShape<G> {
357 fn append_to_transcript(&self, _label: &'static [u8], transcript: &mut Transcript) {
358 self
359 .get_digest()
360 .append_to_transcript(b"R1CSShape", transcript);
361 }
362}
363
364impl<G: Group> AbsorbInROTrait<G> for R1CSShape<G> {
365 fn absorb_in_ro(&self, ro: &mut G::HashFunc) {
366 ro.absorb(scalar_as_base::<G>(self.get_digest()));
367 }
368}
369
370impl<G: Group> R1CSWitness<G> {
371 /// A method to create a witness object using a vector of scalars
372 pub fn new(S: &R1CSShape<G>, W: &[G::Scalar]) -> Result<R1CSWitness<G>, NovaError> {
373 if S.num_vars != W.len() {
374 Err(NovaError::InvalidWitnessLength)
375 } else {
376 Ok(R1CSWitness { W: W.to_owned() })
377 }
378 }
379
380 /// Commits to the witness using the supplied generators
381 pub fn commit(&self, gens: &R1CSGens<G>) -> Commitment<G> {
382 self.W.commit(&gens.gens_W)
383 }
384}
385
386impl<G: Group> R1CSInstance<G> {
387 /// A method to create an instance object using consitituent elements
388 pub fn new(
389 S: &R1CSShape<G>,
390 comm_W: &Commitment<G>,
391 X: &[G::Scalar],
392 ) -> Result<R1CSInstance<G>, NovaError> {
393 if S.num_io != X.len() {
394 Err(NovaError::InvalidInputLength)
395 } else {
396 Ok(R1CSInstance {
397 comm_W: *comm_W,
398 X: X.to_owned(),
399 })
400 }
401 }
402}
403
404impl<G: Group> AppendToTranscriptTrait for R1CSInstance<G> {
405 fn append_to_transcript(&self, _label: &'static [u8], transcript: &mut Transcript) {
406 self.comm_W.append_to_transcript(b"comm_W", transcript);
407 self.X.append_to_transcript(b"X", transcript);
408 }
409}
410
411impl<G: Group> AbsorbInROTrait<G> for R1CSInstance<G> {
412 fn absorb_in_ro(&self, ro: &mut G::HashFunc) {
413 self.comm_W.absorb_in_ro(ro);
414 for x in &self.X {
415 ro.absorb(scalar_as_base::<G>(*x));
416 }
417 }
418}
419
420impl<G: Group> RelaxedR1CSWitness<G> {
421 /// Produces a default RelaxedR1CSWitness given an R1CSShape
422 pub fn default(S: &R1CSShape<G>) -> RelaxedR1CSWitness<G> {
423 RelaxedR1CSWitness {
424 W: vec![G::Scalar::zero(); S.num_vars],
425 E: vec![G::Scalar::zero(); S.num_cons],
426 }
427 }
428
429 /// Commits to the witness using the supplied generators
430 pub fn commit(&self, gens: &R1CSGens<G>) -> (Commitment<G>, Commitment<G>) {
431 (self.W.commit(&gens.gens_W), self.E.commit(&gens.gens_E))
432 }
433
434 /// Folds an incoming R1CSWitness into the current one
435 pub fn fold(
436 &self,
437 W2: &R1CSWitness<G>,
438 T: &[G::Scalar],
439 r: &G::Scalar,
440 ) -> Result<RelaxedR1CSWitness<G>, NovaError> {
441 let (W1, E1) = (&self.W, &self.E);
442 let W2 = &W2.W;
443
444 if W1.len() != W2.len() {
445 return Err(NovaError::InvalidWitnessLength);
446 }
447
448 let W = W1
449 .par_iter()
450 .zip(W2)
451 .map(|(a, b)| *a + *r * *b)
452 .collect::<Vec<G::Scalar>>();
453 let E = E1
454 .par_iter()
455 .zip(T)
456 .map(|(a, b)| *a + *r * *b)
457 .collect::<Vec<G::Scalar>>();
458 Ok(RelaxedR1CSWitness { W, E })
459 }
460}
461
462impl<G: Group> RelaxedR1CSInstance<G> {
463 /// Produces a default RelaxedR1CSInstance given R1CSGens and R1CSShape
464 pub fn default(gens: &R1CSGens<G>, S: &R1CSShape<G>) -> RelaxedR1CSInstance<G> {
465 let (comm_W, comm_E) = RelaxedR1CSWitness::default(S).commit(gens);
466 RelaxedR1CSInstance {
467 comm_W,
468 comm_E,
469 u: G::Scalar::zero(),
470 X: vec![G::Scalar::zero(); S.num_io],
471 }
472 }
473
474 /// Folds an incoming RelaxedR1CSInstance into the current one
475 pub fn fold(
476 &self,
477 U2: &R1CSInstance<G>,
478 comm_T: &Commitment<G>,
479 r: &G::Scalar,
480 ) -> Result<RelaxedR1CSInstance<G>, NovaError> {
481 let (X1, u1, comm_W_1, comm_E_1) =
482 (&self.X, &self.u, &self.comm_W.clone(), &self.comm_E.clone());
483 let (X2, comm_W_2) = (&U2.X, &U2.comm_W);
484
485 // weighted sum of X, comm_W, comm_E, and u
486 let X = X1
487 .par_iter()
488 .zip(X2)
489 .map(|(a, b)| *a + *r * *b)
490 .collect::<Vec<G::Scalar>>();
491 let comm_W = comm_W_1 + comm_W_2 * r;
492 let comm_E = *comm_E_1 + *comm_T * *r;
493 let u = *u1 + *r;
494
495 Ok(RelaxedR1CSInstance {
496 comm_W,
497 comm_E,
498 X,
499 u,
500 })
501 }
502}
503
504impl<G: Group> AppendToTranscriptTrait for RelaxedR1CSInstance<G> {
505 fn append_to_transcript(&self, _label: &'static [u8], transcript: &mut Transcript) {
506 self.comm_W.append_to_transcript(b"comm_W", transcript);
507 self.comm_E.append_to_transcript(b"comm_E", transcript);
508 self.u.append_to_transcript(b"u", transcript);
509 self.X.append_to_transcript(b"X", transcript);
510 }
511}
512
513impl<G: Group> AbsorbInROTrait<G> for RelaxedR1CSInstance<G> {
514 fn absorb_in_ro(&self, ro: &mut G::HashFunc) {
515 self.comm_W.absorb_in_ro(ro);
516 self.comm_E.absorb_in_ro(ro);
517 ro.absorb(scalar_as_base::<G>(self.u));
518
519 // absorb each element of self.X in bignum format
520 for x in &self.X {
521 let limbs: Vec<G::Scalar> = nat_to_limbs(&f_to_nat(x), BN_LIMB_WIDTH, BN_N_LIMBS).unwrap();
522 for limb in limbs {
523 ro.absorb(scalar_as_base::<G>(limb));
524 }
525 }
526 }
527}