protogalaxy-poc/src/protogalaxy.rs
src/protogalaxy.rsRaw
1use ark_crypto_primitives::sponge::Absorb;
2use ark_ec::{CurveGroup, Group};
3use ark_ff::fields::PrimeField;
4use ark_std::log2;
5use ark_std::{cfg_into_iter, One, Zero};
6use std::marker::PhantomData;
7use std::ops::{Add, Mul};
8
9use ark_ff::{batch_inversion, FftField};
10use ark_poly::{
11 univariate::{DensePolynomial, SparsePolynomial},
12 DenseUVPolynomial, EvaluationDomain, Evaluations, GeneralEvaluationDomain, Polynomial,
13};
14
15use crate::pedersen::{Commitment, Params as PedersenParams, Pedersen, Proof as PedersenProof};
16use crate::transcript::Transcript;
17use crate::utils::*;
18
19#[derive(Clone, Debug)]
20pub struct CommittedInstance<C: CurveGroup> {
21 phi: Commitment<C>,
22 betas: Vec<C::ScalarField>,
23 e: C::ScalarField,
24}
25
26#[derive(Clone, Debug)]
27pub struct Witness<C: CurveGroup> {
28 w: Vec<C::ScalarField>,
29 r_w: C::ScalarField,
30}
31
32#[derive(Clone, Debug)]
33pub struct Folding<C: CurveGroup> {
34 _phantom: PhantomData<C>,
35}
36impl<C: CurveGroup> Folding<C>
37where
38 <C as Group>::ScalarField: Absorb,
39 <C as CurveGroup>::BaseField: Absorb,
40{
41 // WIP naming of functions
42 pub fn prover(
43 tr: &mut Transcript<C::ScalarField, C>,
44 pedersen_params: &PedersenParams<C>,
45 r1cs: &R1CS<C::ScalarField>,
46 // running instance
47 instance: CommittedInstance<C>,
48 w: Witness<C>,
49 // incomming instances
50 vec_instances: Vec<CommittedInstance<C>>,
51 vec_w: Vec<Witness<C>>,
52 ) -> (
53 Vec<C::ScalarField>,
54 Vec<C::ScalarField>,
55 CommittedInstance<C>,
56 Witness<C>,
57 ) {
58 let t = instance.betas.len();
59 let n = r1cs.A[0].len();
60
61 // TODO initialize transcript
62 let delta = tr.get_challenge();
63 let deltas = powers_of_beta(delta, t);
64
65 let f_w = eval_f(&r1cs, &w.w);
66 // println!("is f(w) {:?}", f_w);
67
68 // F(X)
69 let mut F_X: SparsePolynomial<C::ScalarField> = SparsePolynomial::zero();
70 for i in 0..n {
71 let lhs = pow_i_over_x::<C::ScalarField>(i, &instance.betas, &deltas);
72 let curr = &lhs * f_w[i];
73 F_X = F_X.add(curr);
74 }
75
76 let F_X_dense = DensePolynomial::from(F_X.clone());
77 tr.add_vec(&F_X_dense.coeffs);
78
79 let alpha = tr.get_challenge();
80
81 // eval F(alpha)
82 let F_alpha = F_X.evaluate(&alpha);
83
84 // betas*
85 let betas_star: Vec<C::ScalarField> = instance
86 .betas
87 .iter()
88 .zip(
89 deltas
90 .iter()
91 .map(|delta_i| alpha * delta_i)
92 .collect::<Vec<C::ScalarField>>(),
93 )
94 .map(|(beta_i, delta_i_alpha)| *beta_i + delta_i_alpha)
95 .collect();
96
97 // sanity check: check that the new randomized instnace (the original instance but with
98 // 'refreshed' randomness) satisfies the relation.
99 assert!(check_instance(
100 r1cs,
101 CommittedInstance {
102 phi: instance.phi.clone(),
103 betas: betas_star.clone(),
104 e: F_alpha,
105 },
106 w.clone(),
107 ));
108
109 let gamma = tr.get_challenge();
110
111 // TODO WIP compute G(X) & K(X)
112 let G_evals: Vec<C::ScalarField> = vec![C::ScalarField::zero(); n];
113 let G_X: DensePolynomial<C::ScalarField> =
114 Evaluations::<C::ScalarField>::from_vec_and_domain(G_evals.clone(), H).interpolate();
115 // dbg!(&G_X);
116 let (K_X, remainder) = G_X.divide_by_vanishing_poly(H).unwrap();
117 // dbg!(&K_X);
118 assert!(remainder.is_zero());
119
120 let Z_X: DensePolynomial<C::ScalarField> = H.vanishing_polynomial().into();
121
122 let e_star =
123 F_alpha * L_X[0].evaluate(&gamma) + Z_X.evaluate(&gamma) * K_X.evaluate(&gamma);
124
125 let mut phi_star: C = instance.phi.0 * L_X[0].evaluate(&gamma);
126 for i in 0..k {
127 phi_star += vec_instances[i].phi.0 * L_X[i].evaluate(&gamma);
128 }
129 let mut w_star: Vec<C::ScalarField> = vec_scalar_mul(&w.w, &L_X[0].evaluate(&gamma));
130 for i in 0..k {
131 w_star = vec_add(
132 &w_star,
133 &vec_scalar_mul(&vec_w[i].w, &L_X[i].evaluate(&gamma)),
134 );
135 }
136
137 (
138 F_X_dense.coeffs,
139 K_X.coeffs,
140 CommittedInstance {
141 betas: betas_star,
142 phi: Commitment(phi_star),
143 e: e_star,
144 },
145 Witness {
146 w: w_star,
147 r_w: w.r_w,
148 },
149 )
150 }
151
152 pub fn verifier(
153 tr: &mut Transcript<C::ScalarField, C>,
154 pedersen_params: &PedersenParams<C>,
155 r1cs: R1CS<C::ScalarField>,
156 // running instance
157 instance: CommittedInstance<C>,
158 // incomming instances
159 vec_instances: Vec<CommittedInstance<C>>,
160 // polys from P
161 F_coeffs: Vec<C::ScalarField>,
162 K_coeffs: Vec<C::ScalarField>,
163 ) -> CommittedInstance<C> {
164 let t = instance.betas.len();
165 let n = r1cs.A[0].len();
166
167 let delta = tr.get_challenge();
168 let deltas = powers_of_beta(delta, t);
169
170 tr.add_vec(&F_coeffs);
171
172 let alpha = tr.get_challenge();
173 let alphas = all_powers(alpha, n);
174
175 // dbg!(instance.e);
176 // dbg!(F_coeffs[0]);
177
178 // F(alpha) = e + \sum_t F_i * alpha^i
179 let mut F_alpha = instance.e;
180 for (i, F_i) in F_coeffs.iter().enumerate() {
181 F_alpha += *F_i * alphas[i];
182 }
183
184 let betas_star: Vec<C::ScalarField> = instance
185 .betas
186 .iter()
187 .zip(
188 deltas
189 .iter()
190 .map(|delta_i| alpha * delta_i)
191 .collect::<Vec<C::ScalarField>>(),
192 )
193 .map(|(beta_i, delta_i_alpha)| *beta_i + delta_i_alpha)
194 .collect();
195
196 let gamma = tr.get_challenge();
197
198 let k = vec_instances.len();
199 let domain_k = GeneralEvaluationDomain::<C::ScalarField>::new(k).unwrap();
200 let L_X: Vec<DensePolynomial<C::ScalarField>> = lagrange_polys(domain_k);
201 let Z_X: DensePolynomial<C::ScalarField> = domain_k.vanishing_polynomial().into();
202 let K_X: DensePolynomial<C::ScalarField> =
203 DensePolynomial::<C::ScalarField>::from_coefficients_vec(K_coeffs);
204 let e_star =
205 F_alpha * L_X[0].evaluate(&gamma) + Z_X.evaluate(&gamma) * K_X.evaluate(&gamma);
206
207 let mut phi_star: C = instance.phi.0 * L_X[0].evaluate(&gamma);
208 for i in 0..k {
209 phi_star += vec_instances[i].phi.0 * L_X[i].evaluate(&gamma);
210 }
211
212 // return the folded instance
213 CommittedInstance {
214 betas: betas_star,
215 phi: Commitment(phi_star),
216 e: e_star,
217 }
218 }
219}
220
221// naive impl of pow_i for betas, assuming that betas=(b, b^2, b^4, ..., b^{2^{t-1}})
222fn pow_i<F: PrimeField>(i: usize, betas: &Vec<F>) -> F {
223 // WIP check if makes more sense to do it with ifs instead of arithmetic
224
225 let n = 2_u64.pow(betas.len() as u32);
226 let b = bit_decompose(i as u64, n as usize);
227
228 let mut r: F = F::one();
229 for (j, beta_i) in betas.iter().enumerate() {
230 let mut b_j = F::zero();
231 if b[j] {
232 b_j = F::one();
233 }
234 r *= (F::one() - b_j) + b_j * betas[j];
235 }
236 r
237}
238
239fn pow_i_over_x<F: PrimeField>(i: usize, betas: &Vec<F>, deltas: &Vec<F>) -> SparsePolynomial<F> {
240 assert_eq!(betas.len(), deltas.len());
241
242 let n = 2_u64.pow(betas.len() as u32);
243 let b = bit_decompose(i as u64, n as usize);
244
245 let mut r: SparsePolynomial<F> =
246 SparsePolynomial::<F>::from_coefficients_vec(vec![(0, F::one())]); // start with r(x) = 1
247 for (j, beta_i) in betas.iter().enumerate() {
248 if b[j] {
249 let curr: SparsePolynomial<F> =
250 SparsePolynomial::<F>::from_coefficients_vec(vec![(0, betas[j]), (1, deltas[j])]);
251 r = r.mul(&curr);
252 }
253 }
254 r
255}
256
257// method from caulk: https://github.com/caulk-crypto/caulk/tree/8210b51fb8a9eef4335505d1695c44ddc7bf8170/src/multi/setup.rs#L300
258fn lagrange_polys<F: PrimeField>(domain_n: GeneralEvaluationDomain<F>) -> Vec<DensePolynomial<F>> {
259 let mut lagrange_polynomials: Vec<DensePolynomial<F>> = Vec::new();
260
261 for i in 0..domain_n.size() {
262 let evals: Vec<F> = cfg_into_iter!(0..domain_n.size())
263 .map(|k| if k == i { F::one() } else { F::zero() })
264 .collect();
265 lagrange_polynomials.push(Evaluations::from_vec_and_domain(evals, domain_n).interpolate());
266 }
267 lagrange_polynomials
268}
269
270#[derive(Clone, Debug)]
271pub struct R1CS<F: PrimeField> {
272 pub A: Vec<Vec<F>>,
273 pub B: Vec<Vec<F>>,
274 pub C: Vec<Vec<F>>,
275}
276
277// f(w) in R1CS context
278fn eval_f<F: PrimeField>(r1cs: &R1CS<F>, w: &Vec<F>) -> Vec<F> {
279 let AzBz = hadamard(&mat_vec_mul(&r1cs.A, &w), &mat_vec_mul(&r1cs.B, &w));
280 let Cz = mat_vec_mul(&r1cs.C, &w);
281 let f_w = vec_sub(&AzBz, &Cz);
282 f_w
283}
284
285fn check_instance<C: CurveGroup>(
286 r1cs: &R1CS<C::ScalarField>,
287 instance: CommittedInstance<C>,
288 w: Witness<C>,
289) -> bool {
290 let n = 2_u64.pow(instance.betas.len() as u32) as usize;
291 dbg!(n);
292 dbg!(w.w.len());
293
294 let f_w = eval_f(&r1cs, &w.w); // f(w)
295 dbg!(f_w.len());
296
297 let mut r = C::ScalarField::zero();
298 for i in 0..n {
299 r += pow_i(i, &instance.betas) * f_w[i];
300 }
301 if instance.e == r {
302 return true;
303 }
304 false
305}
306
307#[cfg(test)]
308mod tests {
309 use super::*;
310 use crate::pedersen::Pedersen;
311 use crate::transcript::poseidon_test_config;
312 use ark_bls12_381::{Fr, G1Projective};
313 use ark_std::One;
314 use ark_std::UniformRand;
315
316 pub fn to_F_matrix<F: PrimeField>(M: Vec<Vec<usize>>) -> Vec<Vec<F>> {
317 let mut R: Vec<Vec<F>> = vec![Vec::new(); M.len()];
318 for i in 0..M.len() {
319 R[i] = vec![F::zero(); M[i].len()];
320 for j in 0..M[i].len() {
321 R[i][j] = F::from(M[i][j] as u64);
322 }
323 }
324 R
325 }
326 pub fn to_F_vec<F: PrimeField>(z: Vec<usize>) -> Vec<F> {
327 let mut r: Vec<F> = vec![F::zero(); z.len()];
328 for i in 0..z.len() {
329 r[i] = F::from(z[i] as u64);
330 }
331 r
332 }
333
334 pub fn get_test_r1cs<F: PrimeField>() -> R1CS<F> {
335 // R1CS for: x^3 + x + 5 = y (example from article
336 // https://www.vitalik.ca/general/2016/12/10/qap.html )
337 let A = to_F_matrix::<F>(vec![
338 vec![0, 1, 0, 0, 0, 0, /**/ 0, 0],
339 vec![0, 0, 0, 1, 0, 0, /**/ 0, 0],
340 vec![0, 1, 0, 0, 1, 0, /**/ 0, 0],
341 vec![5, 0, 0, 0, 0, 1, /**/ 0, 0],
342 //
343 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
344 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
345 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
346 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
347 ]);
348 let B = to_F_matrix::<F>(vec![
349 vec![0, 1, 0, 0, 0, 0, /**/ 0, 0],
350 vec![0, 1, 0, 0, 0, 0, /**/ 0, 0],
351 vec![1, 0, 0, 0, 0, 0, /**/ 0, 0],
352 vec![1, 0, 0, 0, 0, 0, /**/ 0, 0],
353 //
354 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
355 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
356 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
357 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
358 ]);
359 let C = to_F_matrix::<F>(vec![
360 vec![0, 0, 0, 1, 0, 0, /**/ 0, 0],
361 vec![0, 0, 0, 0, 1, 0, /**/ 0, 0],
362 vec![0, 0, 0, 0, 0, 1, /**/ 0, 0],
363 vec![0, 0, 1, 0, 0, 0, /**/ 0, 0],
364 //
365 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
366 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
367 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
368 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
369 ]);
370
371 let r1cs = R1CS::<F> { A, B, C };
372 r1cs
373 }
374
375 pub fn get_test_z<F: PrimeField>(input: usize) -> Vec<F> {
376 // z = (1, io, w)
377 to_F_vec(vec![
378 1,
379 input,
380 input * input * input + input + 5, // x^3 + x + 5
381 input * input, // x^2
382 input * input * input, // x^2 * x
383 input * input * input + input, // x^3 + x
384 0, // pad to pow of 2
385 0,
386 ])
387 }
388
389 #[test]
390 fn test_pow_i() {
391 let mut rng = ark_std::test_rng();
392 let t = 4;
393 let n = 16;
394 let beta = Fr::rand(&mut rng);
395 let betas = powers_of_beta(beta, t);
396 let not_betas = all_powers(beta, n);
397
398 for i in 0..n {
399 assert_eq!(pow_i(i, &betas), not_betas[i]);
400 }
401 }
402
403 #[test]
404 fn test_pow_i_over_x() {
405 let mut rng = ark_std::test_rng();
406 let t = 3;
407 let n = 8;
408 // let beta = Fr::rand(&mut rng);
409 // let delta = Fr::rand(&mut rng);
410 let beta = Fr::from(3);
411 let delta = Fr::from(5);
412 let betas = powers_of_beta(beta, t);
413 let deltas = powers_of_beta(delta, t);
414
415 // for i in 0..n {
416 // dbg!(pow_i_over_x(i, &betas, &deltas));
417 // }
418 }
419
420 #[test]
421 fn test_eval_f() {
422 let r1cs = get_test_r1cs::<Fr>();
423 let mut z = get_test_z::<Fr>(3);
424
425 let f_w = eval_f(&r1cs, &z);
426 assert!(is_zero_vec(&f_w));
427
428 z[1] = Fr::from(111);
429 let f_w = eval_f(&r1cs, &z);
430 assert!(!is_zero_vec(&f_w));
431 }
432
433 #[test]
434 fn test_fold() {
435 let mut rng = ark_std::test_rng();
436 let pedersen_params = Pedersen::<G1Projective>::new_params(&mut rng, 100); // 100 is wip, will get it from actual vec
437 let poseidon_config = poseidon_test_config::<Fr>();
438
439 let k = 5;
440
441 let r1cs = get_test_r1cs::<Fr>();
442 let mut z = get_test_z::<Fr>(3);
443 let mut zs: Vec<Vec<Fr>> = Vec::new();
444 for i in 0..k {
445 let z_i = get_test_z::<Fr>(i + 4);
446 zs.push(z_i);
447 }
448
449 // init Prover & Verifier's transcript
450 let mut transcript_p = Transcript::<Fr, G1Projective>::new(&poseidon_config);
451 let mut transcript_v = Transcript::<Fr, G1Projective>::new(&poseidon_config);
452
453 let n = z.len();
454 let t = log2(n) as usize;
455 dbg!(n);
456 dbg!(t);
457
458 let beta = Fr::rand(&mut rng);
459 let betas = powers_of_beta(beta, t);
460
461 let witness = Witness::<G1Projective> {
462 w: z.clone(), // WIP
463 r_w: Fr::rand(&mut rng),
464 };
465 let phi = Pedersen::<G1Projective>::commit(&pedersen_params, &witness.w, &witness.r_w);
466 let instance = CommittedInstance::<G1Projective> {
467 phi,
468 betas: betas.clone(),
469 e: Fr::zero(),
470 };
471 // same for the other instances
472 let mut witnesses: Vec<Witness<G1Projective>> = Vec::new();
473 let mut instances: Vec<CommittedInstance<G1Projective>> = Vec::new();
474 for i in 0..k {
475 let witness_i = Witness::<G1Projective> {
476 w: zs[i].clone(), // WIP
477 r_w: Fr::rand(&mut rng),
478 };
479 let phi_i =
480 Pedersen::<G1Projective>::commit(&pedersen_params, &witness_i.w, &witness_i.r_w);
481 let instance_i = CommittedInstance::<G1Projective> {
482 phi: phi_i,
483 betas: betas.clone(),
484 e: Fr::zero(),
485 };
486 witnesses.push(witness_i);
487 instances.push(instance_i);
488 }
489
490 let (F_coeffs, K_coeffs, folded_instance, folded_witness) = Folding::<G1Projective>::prover(
491 &mut transcript_p,
492 &pedersen_params,
493 &r1cs,
494 instance.clone(),
495 witness,
496 instances.clone(),
497 witnesses,
498 );
499 dbg!(&F_coeffs);
500
501 // veriier
502 let folded_instance_v = Folding::<G1Projective>::verifier(
503 &mut transcript_v,
504 &pedersen_params,
505 r1cs.clone(), // TODO rm clone do borrow
506 instance,
507 instances,
508 F_coeffs,
509 K_coeffs,
510 );
511
512 assert_eq!(folded_instance.phi.0, folded_instance_v.phi.0);
513 assert_eq!(folded_instance.betas, folded_instance_v.betas);
514 assert_eq!(folded_instance.e, folded_instance_v.e);
515
516 // assert!(check_instance(&r1cs, folded_instance, folded_witness));
517 }
518}