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, CompressedCommitment},
5 errors::NovaError,
6 traits::{AppendToTranscriptTrait, Group},
7};
8use ff::{Field, PrimeField};
9use flate2::{write::ZlibEncoder, Compression};
10use itertools::concat;
11use merlin::Transcript;
12use rayon::prelude::*;
13use serde::{Deserialize, Serialize};
14
15/// Public parameters for a given R1CS
16pub struct R1CSGens<G: Group> {
17 pub(crate) gens_W: CommitGens<G>, // TODO: avoid pub(crate)
18 pub(crate) gens_E: CommitGens<G>,
19}
20
21/// A type that holds the shape of the R1CS matrices
22#[derive(Clone, Debug, PartialEq, Eq)]
23pub struct R1CSShape<G: Group> {
24 num_cons: usize,
25 num_vars: usize,
26 num_io: usize,
27 A: Vec<(usize, usize, G::Scalar)>,
28 B: Vec<(usize, usize, G::Scalar)>,
29 C: Vec<(usize, usize, G::Scalar)>,
30}
31
32/// A type that holds a witness for a given R1CS instance
33#[derive(Clone, Debug, PartialEq, Eq)]
34pub struct R1CSWitness<G: Group> {
35 W: Vec<G::Scalar>,
36}
37
38/// A type that holds an R1CS instance
39#[derive(Clone, Debug, PartialEq, Eq)]
40pub struct R1CSInstance<G: Group> {
41 pub(crate) comm_W: Commitment<G>,
42 pub(crate) X: Vec<G::Scalar>,
43}
44
45/// A type that holds a witness for a given Relaxed R1CS instance
46#[derive(Clone, Debug, PartialEq, Eq)]
47pub struct RelaxedR1CSWitness<G: Group> {
48 W: Vec<G::Scalar>,
49 E: Vec<G::Scalar>,
50}
51
52/// A type that holds a Relaxed R1CS instance
53#[derive(Clone, Debug, PartialEq, Eq)]
54pub struct RelaxedR1CSInstance<G: Group> {
55 pub(crate) comm_W: Commitment<G>,
56 pub(crate) comm_E: Commitment<G>,
57 pub(crate) X: Vec<G::Scalar>,
58 pub(crate) u: G::Scalar,
59 Y_last: Vec<G::Scalar>, // output of the last instance that was folded
60 counter: usize, // the number of folds thus far
61}
62
63impl<G: Group> R1CSGens<G> {
64 /// Samples public parameters for the specified number of constraints and variables in an R1CS
65 pub fn new(num_cons: usize, num_vars: usize) -> R1CSGens<G> {
66 // generators to commit to witness vector `W`
67 let gens_W = CommitGens::new(b"gens_W", num_vars);
68
69 // generators to commit to the error/slack vector `E`
70 let gens_E = CommitGens::new(b"gens_E", num_cons);
71
72 R1CSGens { gens_E, gens_W }
73 }
74}
75
76impl<G: Group> R1CSShape<G> {
77 /// Create an object of type `R1CSShape` from the explicitly specified R1CS matrices
78 pub fn new(
79 num_cons: usize,
80 num_vars: usize,
81 num_io: usize,
82 A: &[(usize, usize, G::Scalar)],
83 B: &[(usize, usize, G::Scalar)],
84 C: &[(usize, usize, G::Scalar)],
85 ) -> Result<R1CSShape<G>, NovaError> {
86 let is_valid = |num_cons: usize,
87 num_vars: usize,
88 num_io: usize,
89 M: &[(usize, usize, G::Scalar)]|
90 -> Result<(), NovaError> {
91 let res = (0..M.len())
92 .map(|i| {
93 let (row, col, _val) = M[i];
94 if row >= num_cons || col > num_io + num_vars {
95 Err(NovaError::InvalidIndex)
96 } else {
97 Ok(())
98 }
99 })
100 .collect::<Result<Vec<()>, NovaError>>();
101
102 if res.is_err() {
103 Err(NovaError::InvalidIndex)
104 } else {
105 Ok(())
106 }
107 };
108
109 let res_A = is_valid(num_cons, num_vars, num_io, A);
110 let res_B = is_valid(num_cons, num_vars, num_io, B);
111 let res_C = is_valid(num_cons, num_vars, num_io, C);
112
113 if res_A.is_err() || res_B.is_err() || res_C.is_err() {
114 return Err(NovaError::InvalidIndex);
115 }
116
117 // We require the number of public inputs/outputs to be even
118 if num_io % 2 != 0 {
119 return Err(NovaError::OddInputLength);
120 }
121
122 let shape = R1CSShape {
123 num_cons,
124 num_vars,
125 num_io,
126 A: A.to_owned(),
127 B: B.to_owned(),
128 C: C.to_owned(),
129 };
130
131 Ok(shape)
132 }
133
134 fn multiply_vec(
135 &self,
136 z: &[G::Scalar],
137 ) -> Result<(Vec<G::Scalar>, Vec<G::Scalar>, Vec<G::Scalar>), NovaError> {
138 if z.len() != self.num_io + self.num_vars + 1 {
139 return Err(NovaError::InvalidWitnessLength);
140 }
141
142 // computes a product between a sparse matrix `M` and a vector `z`
143 // This does not perform any validation of entries in M (e.g., if entries in `M` reference indexes outside the range of `z`)
144 // This is safe since we know that `M` is valid
145 let sparse_matrix_vec_product =
146 |M: &Vec<(usize, usize, G::Scalar)>, num_rows: usize, z: &[G::Scalar]| -> Vec<G::Scalar> {
147 (0..M.len())
148 .map(|i| {
149 let (row, col, val) = M[i];
150 (row, val * z[col])
151 })
152 .fold(vec![G::Scalar::zero(); num_rows], |mut Mz, (r, v)| {
153 Mz[r] += v;
154 Mz
155 })
156 };
157
158 let Az = sparse_matrix_vec_product(&self.A, self.num_cons, z);
159 let Bz = sparse_matrix_vec_product(&self.B, self.num_cons, z);
160 let Cz = sparse_matrix_vec_product(&self.C, self.num_cons, z);
161
162 Ok((Az, Bz, Cz))
163 }
164
165 /// Checks if the Relaxed R1CS instance is satisfiable given a witness and its shape
166 pub fn is_sat_relaxed(
167 &self,
168 gens: &R1CSGens<G>,
169 U: &RelaxedR1CSInstance<G>,
170 W: &RelaxedR1CSWitness<G>,
171 ) -> Result<(), NovaError> {
172 assert_eq!(W.W.len(), self.num_vars);
173 assert_eq!(W.E.len(), self.num_cons);
174 assert_eq!(U.X.len(), self.num_io);
175
176 // verify if Az * Bz = u*Cz + E
177 let res_eq: bool = {
178 let z = concat(vec![W.W.clone(), vec![U.u], U.X.clone()]);
179 let (Az, Bz, Cz) = self.multiply_vec(&z)?;
180 assert_eq!(Az.len(), self.num_cons);
181 assert_eq!(Bz.len(), self.num_cons);
182 assert_eq!(Cz.len(), self.num_cons);
183
184 let res: usize = (0..self.num_cons)
185 .map(|i| {
186 if Az[i] * Bz[i] == U.u * Cz[i] + W.E[i] {
187 0
188 } else {
189 1
190 }
191 })
192 .sum();
193
194 res == 0
195 };
196
197 // verify if comm_E and comm_W are commitments to E and W
198 let res_comm: bool = {
199 let comm_W = W.W.commit(&gens.gens_W);
200 let comm_E = W.E.commit(&gens.gens_E);
201
202 U.comm_W == comm_W && U.comm_E == comm_E
203 };
204
205 if res_eq && res_comm {
206 Ok(())
207 } else {
208 Err(NovaError::UnSat)
209 }
210 }
211
212 /// Checks if the R1CS instance is satisfiable given a witness and its shape
213 pub fn is_sat(
214 &self,
215 gens: &R1CSGens<G>,
216 U: &R1CSInstance<G>,
217 W: &R1CSWitness<G>,
218 ) -> Result<(), NovaError> {
219 assert_eq!(W.W.len(), self.num_vars);
220 assert_eq!(U.X.len(), self.num_io);
221
222 // verify if Az * Bz = u*Cz
223 let res_eq: bool = {
224 let z = concat(vec![W.W.clone(), vec![G::Scalar::one()], U.X.clone()]);
225 let (Az, Bz, Cz) = self.multiply_vec(&z)?;
226 assert_eq!(Az.len(), self.num_cons);
227 assert_eq!(Bz.len(), self.num_cons);
228 assert_eq!(Cz.len(), self.num_cons);
229
230 let res: usize = (0..self.num_cons)
231 .map(|i| if Az[i] * Bz[i] == Cz[i] { 0 } else { 1 })
232 .sum();
233
234 res == 0
235 };
236
237 // verify if comm_W is a commitment to W
238 let res_comm: bool = U.comm_W == W.W.commit(&gens.gens_W);
239
240 if res_eq && res_comm {
241 Ok(())
242 } else {
243 Err(NovaError::UnSat)
244 }
245 }
246
247 /// A method to compute a commitment to the cross-term `T` given a
248 /// Relaxed R1CS instance-witness pair and an R1CS instance-witness pair
249 pub fn commit_T(
250 &self,
251 gens: &R1CSGens<G>,
252 U1: &RelaxedR1CSInstance<G>,
253 W1: &RelaxedR1CSWitness<G>,
254 U2: &R1CSInstance<G>,
255 W2: &R1CSWitness<G>,
256 ) -> Result<
257 (
258 Vec<G::Scalar>,
259 CompressedCommitment<G::CompressedGroupElement>,
260 ),
261 NovaError,
262 > {
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).compress();
293
294 Ok((T, comm_T))
295 }
296}
297
298#[derive(Clone, Debug, PartialEq, Eq, Serialize, Deserialize)]
299struct R1CSShapeSerialized {
300 num_cons: usize,
301 num_vars: usize,
302 num_io: usize,
303 A: Vec<(usize, usize, Vec<u8>)>,
304 B: Vec<(usize, usize, Vec<u8>)>,
305 C: Vec<(usize, usize, Vec<u8>)>,
306}
307
308impl<G: Group> AppendToTranscriptTrait for R1CSShape<G> {
309 fn append_to_transcript(&self, _label: &'static [u8], transcript: &mut Transcript) {
310 let shape_serialized = R1CSShapeSerialized {
311 num_cons: self.num_cons,
312 num_vars: self.num_vars,
313 num_io: self.num_io,
314 A: self
315 .A
316 .iter()
317 .map(|(i, j, v)| (*i, *j, v.to_repr().as_ref().to_vec()))
318 .collect(),
319 B: self
320 .B
321 .iter()
322 .map(|(i, j, v)| (*i, *j, v.to_repr().as_ref().to_vec()))
323 .collect(),
324 C: self
325 .C
326 .iter()
327 .map(|(i, j, v)| (*i, *j, v.to_repr().as_ref().to_vec()))
328 .collect(),
329 };
330
331 let mut encoder = ZlibEncoder::new(Vec::new(), Compression::default());
332 bincode::serialize_into(&mut encoder, &shape_serialized).unwrap();
333 let shape_bytes = encoder.finish().unwrap();
334 transcript.append_message(b"R1CSShape", &shape_bytes);
335 }
336}
337
338impl<G: Group> R1CSWitness<G> {
339 /// A method to create a witness object using a vector of scalars
340 pub fn new(S: &R1CSShape<G>, W: &[G::Scalar]) -> Result<R1CSWitness<G>, NovaError> {
341 if S.num_vars != W.len() {
342 Err(NovaError::InvalidWitnessLength)
343 } else {
344 Ok(R1CSWitness { W: W.to_owned() })
345 }
346 }
347
348 /// Commits to the witness using the supplied generators
349 pub fn commit(&self, gens: &R1CSGens<G>) -> Commitment<G> {
350 self.W.commit(&gens.gens_W)
351 }
352}
353
354impl<G: Group> R1CSInstance<G> {
355 /// A method to create an instance object using consitituent elements
356 pub fn new(
357 S: &R1CSShape<G>,
358 comm_W: &Commitment<G>,
359 X: &[G::Scalar],
360 ) -> Result<R1CSInstance<G>, NovaError> {
361 if S.num_io != X.len() {
362 Err(NovaError::InvalidInputLength)
363 } else {
364 Ok(R1CSInstance {
365 comm_W: *comm_W,
366 X: X.to_owned(),
367 })
368 }
369 }
370}
371
372impl<G: Group> AppendToTranscriptTrait for R1CSInstance<G> {
373 fn append_to_transcript(&self, _label: &'static [u8], transcript: &mut Transcript) {
374 self.comm_W.append_to_transcript(b"comm_W", transcript);
375 self.X.append_to_transcript(b"X", transcript);
376 }
377}
378
379impl<G: Group> RelaxedR1CSWitness<G> {
380 /// Produces a default RelaxedR1CSWitness given an R1CSShape
381 pub fn default(S: &R1CSShape<G>) -> RelaxedR1CSWitness<G> {
382 RelaxedR1CSWitness {
383 W: vec![G::Scalar::zero(); S.num_vars],
384 E: vec![G::Scalar::zero(); S.num_cons],
385 }
386 }
387
388 /// Commits to the witness using the supplied generators
389 pub fn commit(&self, gens: &R1CSGens<G>) -> (Commitment<G>, Commitment<G>) {
390 (self.W.commit(&gens.gens_W), self.E.commit(&gens.gens_E))
391 }
392
393 /// Folds an incoming R1CSWitness into the current one
394 pub fn fold(
395 &self,
396 W2: &R1CSWitness<G>,
397 T: &[G::Scalar],
398 r: &G::Scalar,
399 ) -> Result<RelaxedR1CSWitness<G>, NovaError> {
400 let (W1, E1) = (&self.W, &self.E);
401 let W2 = &W2.W;
402
403 if W1.len() != W2.len() {
404 return Err(NovaError::InvalidWitnessLength);
405 }
406
407 let W = W1
408 .par_iter()
409 .zip(W2)
410 .map(|(a, b)| *a + *r * *b)
411 .collect::<Vec<G::Scalar>>();
412 let E = E1
413 .par_iter()
414 .zip(T)
415 .map(|(a, b)| *a + *r * *b)
416 .collect::<Vec<G::Scalar>>();
417 Ok(RelaxedR1CSWitness { W, E })
418 }
419}
420
421impl<G: Group> RelaxedR1CSInstance<G> {
422 /// Produces a default RelaxedR1CSInstance given R1CSGens and R1CSShape
423 pub fn default(gens: &R1CSGens<G>, S: &R1CSShape<G>) -> RelaxedR1CSInstance<G> {
424 let (comm_W, comm_E) = RelaxedR1CSWitness::default(S).commit(gens);
425 RelaxedR1CSInstance {
426 comm_W,
427 comm_E,
428 u: G::Scalar::zero(),
429 X: vec![G::Scalar::zero(); S.num_io],
430 Y_last: vec![G::Scalar::zero(); S.num_io / 2],
431 counter: 0,
432 }
433 }
434
435 /// Folds an incoming RelaxedR1CSInstance into the current one
436 pub fn fold(
437 &self,
438 U2: &R1CSInstance<G>,
439 comm_T: &CompressedCommitment<G::CompressedGroupElement>,
440 r: &G::Scalar,
441 ) -> Result<RelaxedR1CSInstance<G>, NovaError> {
442 let comm_T_unwrapped = comm_T.decompress()?;
443 let (X1, u1, comm_W_1, comm_E_1) =
444 (&self.X, &self.u, &self.comm_W.clone(), &self.comm_E.clone());
445 let (X2, comm_W_2) = (&U2.X, &U2.comm_W);
446
447 // check if the input of the incoming instance matches the output
448 // of the incremental computation thus far if counter > 0
449 if self.counter > 0 {
450 if self.Y_last.len() != U2.X.len() / 2 {
451 return Err(NovaError::InvalidInputLength);
452 }
453 for i in 0..self.Y_last.len() {
454 if self.Y_last[i] != U2.X[i] {
455 return Err(NovaError::InputOutputMismatch);
456 }
457 }
458 }
459
460 // weighted sum of X, comm_W, comm_E, and u
461 let X = X1
462 .par_iter()
463 .zip(X2)
464 .map(|(a, b)| *a + *r * *b)
465 .collect::<Vec<G::Scalar>>();
466 let comm_W = comm_W_1 + comm_W_2 * r;
467 let comm_E = *comm_E_1 + comm_T_unwrapped * *r;
468 let u = *u1 + *r;
469
470 Ok(RelaxedR1CSInstance {
471 comm_W,
472 comm_E,
473 X,
474 u,
475 Y_last: U2.X[U2.X.len() / 2..].to_owned(),
476 counter: self.counter + 1,
477 })
478 }
479}
480
481impl<G: Group> AppendToTranscriptTrait for RelaxedR1CSInstance<G> {
482 fn append_to_transcript(&self, _label: &'static [u8], transcript: &mut Transcript) {
483 self.comm_W.append_to_transcript(b"comm_W", transcript);
484 self.comm_E.append_to_transcript(b"comm_E", transcript);
485 self.X.append_to_transcript(b"X", transcript);
486 self.u.append_to_transcript(b"u", transcript);
487 }
488}