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 Y_last: Vec<G::Scalar>, // output of the last instance that was folded
64 counter: usize, // the number of folds thus far
65}
66
67impl<G: Group> R1CSGens<G> {
68 /// Samples public parameters for the specified number of constraints and variables in an R1CS
69 pub fn new(num_cons: usize, num_vars: usize) -> R1CSGens<G> {
70 // generators to commit to witness vector `W`
71 let gens_W = CommitGens::new(b"gens_W", num_vars);
72
73 // generators to commit to the error/slack vector `E`
74 let gens_E = CommitGens::new(b"gens_E", num_cons);
75
76 R1CSGens { gens_E, gens_W }
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 let shape = 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 Ok(shape)
136 }
137
138 fn multiply_vec(
139 &self,
140 z: &[G::Scalar],
141 ) -> Result<(Vec<G::Scalar>, Vec<G::Scalar>, Vec<G::Scalar>), NovaError> {
142 if z.len() != self.num_io + self.num_vars + 1 {
143 return Err(NovaError::InvalidWitnessLength);
144 }
145
146 // computes a product between a sparse matrix `M` and a vector `z`
147 // This does not perform any validation of entries in M (e.g., if entries in `M` reference indexes outside the range of `z`)
148 // This is safe since we know that `M` is valid
149 let sparse_matrix_vec_product =
150 |M: &Vec<(usize, usize, G::Scalar)>, num_rows: usize, z: &[G::Scalar]| -> Vec<G::Scalar> {
151 (0..M.len())
152 .map(|i| {
153 let (row, col, val) = M[i];
154 (row, val * z[col])
155 })
156 .fold(vec![G::Scalar::zero(); num_rows], |mut Mz, (r, v)| {
157 Mz[r] += v;
158 Mz
159 })
160 };
161
162 let Az = sparse_matrix_vec_product(&self.A, self.num_cons, z);
163 let Bz = sparse_matrix_vec_product(&self.B, self.num_cons, z);
164 let Cz = sparse_matrix_vec_product(&self.C, self.num_cons, z);
165
166 Ok((Az, Bz, Cz))
167 }
168
169 /// Checks if the Relaxed R1CS instance is satisfiable given a witness and its shape
170 pub fn is_sat_relaxed(
171 &self,
172 gens: &R1CSGens<G>,
173 U: &RelaxedR1CSInstance<G>,
174 W: &RelaxedR1CSWitness<G>,
175 ) -> Result<(), NovaError> {
176 assert_eq!(W.W.len(), self.num_vars);
177 assert_eq!(W.E.len(), self.num_cons);
178 assert_eq!(U.X.len(), self.num_io);
179
180 // verify if Az * Bz = u*Cz + E
181 let res_eq: bool = {
182 let z = concat(vec![W.W.clone(), vec![U.u], U.X.clone()]);
183 let (Az, Bz, Cz) = self.multiply_vec(&z)?;
184 assert_eq!(Az.len(), self.num_cons);
185 assert_eq!(Bz.len(), self.num_cons);
186 assert_eq!(Cz.len(), self.num_cons);
187
188 let res: usize = (0..self.num_cons)
189 .map(|i| {
190 if Az[i] * Bz[i] == U.u * Cz[i] + W.E[i] {
191 0
192 } else {
193 1
194 }
195 })
196 .sum();
197
198 res == 0
199 };
200
201 // verify if comm_E and comm_W are commitments to E and W
202 let res_comm: bool = {
203 let comm_W = W.W.commit(&gens.gens_W);
204 let comm_E = W.E.commit(&gens.gens_E);
205
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| if Az[i] * Bz[i] == Cz[i] { 0 } else { 1 })
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_W);
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 .map(|i| AZ_1[i] * BZ_2[i])
273 .collect::<Vec<G::Scalar>>();
274 let AZ_2_circ_BZ_1 = (0..AZ_2.len())
275 .map(|i| AZ_2[i] * BZ_1[i])
276 .collect::<Vec<G::Scalar>>();
277 let u_1_cdot_CZ_2 = (0..CZ_2.len())
278 .map(|i| U1.u * CZ_2[i])
279 .collect::<Vec<G::Scalar>>();
280 let u_2_cdot_CZ_1 = (0..CZ_1.len()).map(|i| CZ_1[i]).collect::<Vec<G::Scalar>>();
281
282 let T = AZ_1_circ_BZ_2
283 .par_iter()
284 .zip(&AZ_2_circ_BZ_1)
285 .zip(&u_1_cdot_CZ_2)
286 .zip(&u_2_cdot_CZ_1)
287 .map(|(((a, b), c), d)| *a + *b - *c - *d)
288 .collect::<Vec<G::Scalar>>();
289
290 let comm_T = T.commit(&gens.gens_E);
291
292 Ok((T, comm_T))
293 }
294
295 /// returns the digest of R1CSShape
296 fn get_digest(&self) -> G::Scalar {
297 let shape_serialized = R1CSShapeSerialized {
298 num_cons: self.num_cons,
299 num_vars: self.num_vars,
300 num_io: self.num_io,
301 A: self
302 .A
303 .iter()
304 .map(|(i, j, v)| (*i, *j, v.to_repr().as_ref().to_vec()))
305 .collect(),
306 B: self
307 .B
308 .iter()
309 .map(|(i, j, v)| (*i, *j, v.to_repr().as_ref().to_vec()))
310 .collect(),
311 C: self
312 .C
313 .iter()
314 .map(|(i, j, v)| (*i, *j, v.to_repr().as_ref().to_vec()))
315 .collect(),
316 };
317
318 // obtain a vector of bytes representing the R1CS shape
319 let mut encoder = ZlibEncoder::new(Vec::new(), Compression::default());
320 bincode::serialize_into(&mut encoder, &shape_serialized).unwrap();
321 let shape_bytes = encoder.finish().unwrap();
322
323 // convert shape_bytes into a short digest
324 let mut hasher = Sha3_256::new();
325 hasher.input(&shape_bytes);
326 let shape_digest = hasher.result();
327
328 // truncate the digest to 250 bits
329 let bv = (0..NUM_HASH_BITS).map(|i| {
330 let (byte_pos, bit_pos) = (i / 8, i % 8);
331 let bit = (shape_digest[byte_pos] >> bit_pos) & 1;
332 bit == 1
333 });
334
335 // turn the bit vector into a scalar
336 let mut res = G::Scalar::zero();
337 let mut coeff = G::Scalar::one();
338 for bit in bv {
339 if bit {
340 res += coeff;
341 }
342 coeff += coeff;
343 }
344 res
345 }
346}
347
348#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
349struct R1CSShapeSerialized {
350 num_cons: usize,
351 num_vars: usize,
352 num_io: usize,
353 A: Vec<(usize, usize, Vec<u8>)>,
354 B: Vec<(usize, usize, Vec<u8>)>,
355 C: Vec<(usize, usize, Vec<u8>)>,
356}
357
358impl<G: Group> AppendToTranscriptTrait for R1CSShape<G> {
359 fn append_to_transcript(&self, _label: &'static [u8], transcript: &mut Transcript) {
360 self
361 .get_digest()
362 .append_to_transcript(b"R1CSShape", transcript);
363 }
364}
365
366impl<G: Group> AbsorbInROTrait<G> for R1CSShape<G> {
367 fn absorb_in_ro(&self, ro: &mut G::HashFunc) {
368 ro.absorb(scalar_as_base::<G>(self.get_digest()));
369 }
370}
371
372impl<G: Group> R1CSWitness<G> {
373 /// A method to create a witness object using a vector of scalars
374 pub fn new(S: &R1CSShape<G>, W: &[G::Scalar]) -> Result<R1CSWitness<G>, NovaError> {
375 if S.num_vars != W.len() {
376 Err(NovaError::InvalidWitnessLength)
377 } else {
378 Ok(R1CSWitness { W: W.to_owned() })
379 }
380 }
381
382 /// Commits to the witness using the supplied generators
383 pub fn commit(&self, gens: &R1CSGens<G>) -> Commitment<G> {
384 self.W.commit(&gens.gens_W)
385 }
386}
387
388impl<G: Group> R1CSInstance<G> {
389 /// A method to create an instance object using consitituent elements
390 pub fn new(
391 S: &R1CSShape<G>,
392 comm_W: &Commitment<G>,
393 X: &[G::Scalar],
394 ) -> Result<R1CSInstance<G>, NovaError> {
395 if S.num_io != X.len() {
396 Err(NovaError::InvalidInputLength)
397 } else {
398 Ok(R1CSInstance {
399 comm_W: *comm_W,
400 X: X.to_owned(),
401 })
402 }
403 }
404}
405
406impl<G: Group> AppendToTranscriptTrait for R1CSInstance<G> {
407 fn append_to_transcript(&self, _label: &'static [u8], transcript: &mut Transcript) {
408 self.comm_W.append_to_transcript(b"comm_W", transcript);
409 self.X.append_to_transcript(b"X", transcript);
410 }
411}
412
413impl<G: Group> AbsorbInROTrait<G> for R1CSInstance<G> {
414 fn absorb_in_ro(&self, ro: &mut G::HashFunc) {
415 self.comm_W.absorb_in_ro(ro);
416 for x in &self.X {
417 ro.absorb(scalar_as_base::<G>(*x));
418 }
419 }
420}
421
422impl<G: Group> RelaxedR1CSWitness<G> {
423 /// Produces a default RelaxedR1CSWitness given an R1CSShape
424 pub fn default(S: &R1CSShape<G>) -> RelaxedR1CSWitness<G> {
425 RelaxedR1CSWitness {
426 W: vec![G::Scalar::zero(); S.num_vars],
427 E: vec![G::Scalar::zero(); S.num_cons],
428 }
429 }
430
431 /// Commits to the witness using the supplied generators
432 pub fn commit(&self, gens: &R1CSGens<G>) -> (Commitment<G>, Commitment<G>) {
433 (self.W.commit(&gens.gens_W), self.E.commit(&gens.gens_E))
434 }
435
436 /// Folds an incoming R1CSWitness into the current one
437 pub fn fold(
438 &self,
439 W2: &R1CSWitness<G>,
440 T: &[G::Scalar],
441 r: &G::Scalar,
442 ) -> Result<RelaxedR1CSWitness<G>, NovaError> {
443 let (W1, E1) = (&self.W, &self.E);
444 let W2 = &W2.W;
445
446 if W1.len() != W2.len() {
447 return Err(NovaError::InvalidWitnessLength);
448 }
449
450 let W = W1
451 .par_iter()
452 .zip(W2)
453 .map(|(a, b)| *a + *r * *b)
454 .collect::<Vec<G::Scalar>>();
455 let E = E1
456 .par_iter()
457 .zip(T)
458 .map(|(a, b)| *a + *r * *b)
459 .collect::<Vec<G::Scalar>>();
460 Ok(RelaxedR1CSWitness { W, E })
461 }
462}
463
464impl<G: Group> RelaxedR1CSInstance<G> {
465 /// Produces a default RelaxedR1CSInstance given R1CSGens and R1CSShape
466 pub fn default(gens: &R1CSGens<G>, S: &R1CSShape<G>) -> RelaxedR1CSInstance<G> {
467 let (comm_W, comm_E) = RelaxedR1CSWitness::default(S).commit(gens);
468 RelaxedR1CSInstance {
469 comm_W,
470 comm_E,
471 u: G::Scalar::zero(),
472 X: vec![G::Scalar::zero(); S.num_io],
473 Y_last: vec![G::Scalar::zero(); S.num_io / 2],
474 counter: 0,
475 }
476 }
477
478 /// Folds an incoming RelaxedR1CSInstance into the current one
479 pub fn fold(
480 &self,
481 U2: &R1CSInstance<G>,
482 comm_T: &Commitment<G>,
483 r: &G::Scalar,
484 ) -> Result<RelaxedR1CSInstance<G>, NovaError> {
485 let (X1, u1, comm_W_1, comm_E_1) =
486 (&self.X, &self.u, &self.comm_W.clone(), &self.comm_E.clone());
487 let (X2, comm_W_2) = (&U2.X, &U2.comm_W);
488
489 // check if the input of the incoming instance matches the output
490 // of the incremental computation thus far if counter > 0
491 if self.counter > 0 {
492 if self.Y_last.len() != U2.X.len() / 2 {
493 return Err(NovaError::InvalidInputLength);
494 }
495 for i in 0..self.Y_last.len() {
496 if self.Y_last[i] != U2.X[i] {
497 return Err(NovaError::InputOutputMismatch);
498 }
499 }
500 }
501
502 // weighted sum of X, comm_W, comm_E, and u
503 let X = X1
504 .par_iter()
505 .zip(X2)
506 .map(|(a, b)| *a + *r * *b)
507 .collect::<Vec<G::Scalar>>();
508 let comm_W = comm_W_1 + comm_W_2 * r;
509 let comm_E = *comm_E_1 + *comm_T * *r;
510 let u = *u1 + *r;
511
512 Ok(RelaxedR1CSInstance {
513 comm_W,
514 comm_E,
515 X,
516 u,
517 Y_last: U2.X[U2.X.len() / 2..].to_owned(),
518 counter: self.counter + 1,
519 })
520 }
521}
522
523impl<G: Group> AppendToTranscriptTrait for RelaxedR1CSInstance<G> {
524 fn append_to_transcript(&self, _label: &'static [u8], transcript: &mut Transcript) {
525 self.comm_W.append_to_transcript(b"comm_W", transcript);
526 self.comm_E.append_to_transcript(b"comm_E", transcript);
527 self.u.append_to_transcript(b"u", transcript);
528 self.X.append_to_transcript(b"X", transcript);
529 }
530}
531
532impl<G: Group> AbsorbInROTrait<G> for RelaxedR1CSInstance<G> {
533 fn absorb_in_ro(&self, ro: &mut G::HashFunc) {
534 self.comm_W.absorb_in_ro(ro);
535 self.comm_E.absorb_in_ro(ro);
536 ro.absorb(scalar_as_base::<G>(self.u));
537
538 // absorb each element of self.X in bignum format
539 for x in &self.X {
540 let limbs: Vec<G::Scalar> = nat_to_limbs(&f_to_nat(x), BN_LIMB_WIDTH, BN_N_LIMBS).unwrap();
541 for limb in limbs {
542 ro.absorb(scalar_as_base::<G>(limb));
543 }
544 }
545 }
546}