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