sonobe/folding-schemes/src/arith/r1cs.rs
folding-schemes/src/arith/r1cs.rsRaw
1use crate::commitment::CommitmentScheme;
2use crate::RngCore;
3use ark_ec::CurveGroup;
4use ark_ff::PrimeField;
5use ark_relations::r1cs::ConstraintSystem;
6use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
7use ark_std::rand::Rng;
8
9use super::Arith;
10use crate::utils::vec::{hadamard, mat_vec_mul, vec_scalar_mul, vec_sub, SparseMatrix};
11use crate::Error;
12
13#[derive(Debug, Clone, Eq, PartialEq, CanonicalSerialize, CanonicalDeserialize)]
14pub struct R1CS<F: PrimeField> {
15 pub l: usize, // io len
16 pub A: SparseMatrix<F>,
17 pub B: SparseMatrix<F>,
18 pub C: SparseMatrix<F>,
19}
20
21impl<F: PrimeField> Arith<F> for R1CS<F> {
22 fn eval_relation(&self, z: &[F]) -> Result<Vec<F>, Error> {
23 if z.len() != self.A.n_cols {
24 return Err(Error::NotSameLength(
25 "z.len()".to_string(),
26 z.len(),
27 "number of variables in R1CS".to_string(),
28 self.A.n_cols,
29 ));
30 }
31
32 let Az = mat_vec_mul(&self.A, z)?;
33 let Bz = mat_vec_mul(&self.B, z)?;
34 let Cz = mat_vec_mul(&self.C, z)?;
35 // Multiply Cz by z[0] (u) here, allowing this method to be reused for
36 // both relaxed and unrelaxed R1CS.
37 let uCz = vec_scalar_mul(&Cz, &z[0]);
38 let AzBz = hadamard(&Az, &Bz)?;
39 vec_sub(&AzBz, &uCz)
40 }
41
42 fn params_to_le_bytes(&self) -> Vec<u8> {
43 [
44 self.l.to_le_bytes(),
45 self.A.n_rows.to_le_bytes(),
46 self.A.n_cols.to_le_bytes(),
47 ]
48 .concat()
49 }
50}
51
52impl<F: PrimeField> R1CS<F> {
53 pub fn empty() -> Self {
54 R1CS {
55 l: 0,
56 A: SparseMatrix::empty(),
57 B: SparseMatrix::empty(),
58 C: SparseMatrix::empty(),
59 }
60 }
61 pub fn rand<R: Rng>(rng: &mut R, n_rows: usize, n_cols: usize) -> Self {
62 Self {
63 l: 1,
64 A: SparseMatrix::rand(rng, n_rows, n_cols),
65 B: SparseMatrix::rand(rng, n_rows, n_cols),
66 C: SparseMatrix::rand(rng, n_rows, n_cols),
67 }
68 }
69
70 /// returns a tuple containing (w, x) (witness and public inputs respectively)
71 pub fn split_z(&self, z: &[F]) -> (Vec<F>, Vec<F>) {
72 (z[self.l + 1..].to_vec(), z[1..self.l + 1].to_vec())
73 }
74}
75
76pub trait RelaxedR1CS<C: CurveGroup, W, U>: Arith<C::ScalarField> {
77 /// returns a dummy running instance (Witness and CommittedInstance) for the current R1CS structure
78 fn dummy_running_instance(&self) -> (W, U);
79
80 /// returns a dummy incoming instance (Witness and CommittedInstance) for the current R1CS structure
81 fn dummy_incoming_instance(&self) -> (W, U);
82
83 /// checks if the given instance is relaxed
84 fn is_relaxed(w: &W, u: &U) -> bool;
85
86 /// extracts `z`, the vector of variables, from the given Witness and CommittedInstance
87 fn extract_z(w: &W, u: &U) -> Vec<C::ScalarField>;
88
89 /// checks if the computed error terms correspond to the actual one in `w`
90 /// or `u`
91 fn check_error_terms(w: &W, u: &U, e: Vec<C::ScalarField>) -> Result<(), Error>;
92
93 /// checks the tight (unrelaxed) R1CS relation
94 fn check_tight_relation(&self, w: &W, u: &U) -> Result<(), Error> {
95 if Self::is_relaxed(w, u) {
96 return Err(Error::R1CSUnrelaxedFail);
97 }
98
99 let z = Self::extract_z(w, u);
100 self.check_relation(&z)
101 }
102
103 /// checks the relaxed R1CS relation
104 fn check_relaxed_relation(&self, w: &W, u: &U) -> Result<(), Error> {
105 let z = Self::extract_z(w, u);
106 let e = self.eval_relation(&z)?;
107 Self::check_error_terms(w, u, e)
108 }
109
110 // Computes the E term, given A, B, C, z, u
111 fn compute_E(
112 A: &SparseMatrix<C::ScalarField>,
113 B: &SparseMatrix<C::ScalarField>,
114 C: &SparseMatrix<C::ScalarField>,
115 z: &[C::ScalarField],
116 u: &C::ScalarField,
117 ) -> Result<Vec<C::ScalarField>, Error> {
118 let Az = mat_vec_mul(A, z)?;
119 let Bz = mat_vec_mul(B, z)?;
120 let AzBz = hadamard(&Az, &Bz)?;
121
122 let Cz = mat_vec_mul(C, z)?;
123 let uCz = vec_scalar_mul(&Cz, u);
124 vec_sub(&AzBz, &uCz)
125 }
126
127 fn sample<CS>(&self, params: &CS::ProverParams, rng: impl RngCore) -> Result<(W, U), Error>
128 where
129 CS: CommitmentScheme<C, true>;
130}
131
132/// extracts arkworks ConstraintSystem matrices into crate::utils::vec::SparseMatrix format as R1CS
133/// struct.
134pub fn extract_r1cs<F: PrimeField>(cs: &ConstraintSystem<F>) -> R1CS<F> {
135 let m = cs.to_matrices().unwrap();
136
137 let n_rows = cs.num_constraints;
138 let n_cols = cs.num_instance_variables + cs.num_witness_variables; // cs.num_instance_variables already counts the 1
139
140 let A = SparseMatrix::<F> {
141 n_rows,
142 n_cols,
143 coeffs: m.a,
144 };
145 let B = SparseMatrix::<F> {
146 n_rows,
147 n_cols,
148 coeffs: m.b,
149 };
150 let C = SparseMatrix::<F> {
151 n_rows,
152 n_cols,
153 coeffs: m.c,
154 };
155
156 R1CS::<F> {
157 l: cs.num_instance_variables - 1, // -1 to subtract the first '1'
158 A,
159 B,
160 C,
161 }
162}
163
164/// extracts the witness and the public inputs from arkworks ConstraintSystem.
165pub fn extract_w_x<F: PrimeField>(cs: &ConstraintSystem<F>) -> (Vec<F>, Vec<F>) {
166 (
167 cs.witness_assignment.clone(),
168 // skip the first element which is '1'
169 cs.instance_assignment[1..].to_vec(),
170 )
171}
172
173#[cfg(test)]
174pub mod tests {
175 use super::*;
176 use crate::folding::nova::{CommittedInstance, Witness};
177 use crate::{
178 commitment::pedersen::Pedersen,
179 utils::vec::{
180 is_zero_vec,
181 tests::{to_F_matrix, to_F_vec},
182 },
183 };
184
185 use ark_pallas::{Fr, Projective};
186
187 #[test]
188 pub fn sample_relaxed_r1cs() {
189 let rng = rand::rngs::OsRng;
190 let r1cs = get_test_r1cs::<Fr>();
191 let (prover_params, _) = Pedersen::<Projective>::setup(rng, r1cs.A.n_rows).unwrap();
192
193 let sampled: Result<(Witness<Projective>, CommittedInstance<Projective>), _> =
194 r1cs.sample::<Pedersen<Projective, true>>(&prover_params, rng);
195 assert!(sampled.is_ok());
196 }
197
198 pub fn get_test_r1cs<F: PrimeField>() -> R1CS<F> {
199 // R1CS for: x^3 + x + 5 = y (example from article
200 // https://www.vitalik.ca/general/2016/12/10/qap.html )
201 let A = to_F_matrix::<F>(vec![
202 vec![0, 1, 0, 0, 0, 0],
203 vec![0, 0, 0, 1, 0, 0],
204 vec![0, 1, 0, 0, 1, 0],
205 vec![5, 0, 0, 0, 0, 1],
206 ]);
207 let B = to_F_matrix::<F>(vec![
208 vec![0, 1, 0, 0, 0, 0],
209 vec![0, 1, 0, 0, 0, 0],
210 vec![1, 0, 0, 0, 0, 0],
211 vec![1, 0, 0, 0, 0, 0],
212 ]);
213 let C = to_F_matrix::<F>(vec![
214 vec![0, 0, 0, 1, 0, 0],
215 vec![0, 0, 0, 0, 1, 0],
216 vec![0, 0, 0, 0, 0, 1],
217 vec![0, 0, 1, 0, 0, 0],
218 ]);
219
220 R1CS::<F> { l: 1, A, B, C }
221 }
222
223 pub fn get_test_z<F: PrimeField>(input: usize) -> Vec<F> {
224 // z = (1, io, w)
225 to_F_vec(vec![
226 1,
227 input, // io
228 input * input * input + input + 5, // x^3 + x + 5
229 input * input, // x^2
230 input * input * input, // x^2 * x
231 input * input * input + input, // x^3 + x
232 ])
233 }
234
235 pub fn get_test_z_split<F: PrimeField>(input: usize) -> (F, Vec<F>, Vec<F>) {
236 // z = (1, io, w)
237 (
238 F::one(),
239 to_F_vec(vec![
240 input, // io
241 ]),
242 to_F_vec(vec![
243 input * input * input + input + 5, // x^3 + x + 5
244 input * input, // x^2
245 input * input * input, // x^2 * x
246 input * input * input + input, // x^3 + x
247 ]),
248 )
249 }
250
251 #[test]
252 fn test_eval_r1cs_relation() {
253 let mut rng = ark_std::test_rng();
254 let r1cs = get_test_r1cs::<Fr>();
255 let mut z = get_test_z::<Fr>(rng.gen::<u16>() as usize);
256
257 let f_w = r1cs.eval_relation(&z).unwrap();
258 assert!(is_zero_vec(&f_w));
259
260 z[1] = Fr::from(111);
261 let f_w = r1cs.eval_relation(&z).unwrap();
262 assert!(!is_zero_vec(&f_w));
263 }
264
265 #[test]
266 fn test_check_r1cs_relation() {
267 let r1cs = get_test_r1cs::<Fr>();
268 let z = get_test_z(5);
269 r1cs.check_relation(&z).unwrap();
270 }
271}