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::{One, Zero};
6use std::marker::PhantomData;
7use std::ops::Add;
8
9use ark_poly::{univariate::SparsePolynomial, Polynomial};
10
11use crate::pedersen::{Commitment, Params as PedersenParams, Pedersen, Proof as PedersenProof};
12use crate::transcript::Transcript;
13use crate::utils::*;
14
15#[derive(Clone, Debug)]
16pub struct CommittedInstance<C: CurveGroup> {
17 phi: Commitment<C>,
18 betas: Vec<C::ScalarField>,
19 e: C::ScalarField,
20}
21
22#[derive(Clone, Debug)]
23pub struct Witness<C: CurveGroup> {
24 w: Vec<C::ScalarField>,
25 r_w: C::ScalarField,
26}
27
28#[derive(Clone, Debug)]
29pub struct Folding<C: CurveGroup> {
30 _phantom: PhantomData<C>,
31}
32impl<C: CurveGroup> Folding<C>
33where
34 <C as Group>::ScalarField: Absorb,
35 <C as CurveGroup>::BaseField: Absorb,
36{
37 // WIP naming of functions
38 pub fn prover(
39 tr: &mut Transcript<C::ScalarField, C>,
40 pedersen_params: &PedersenParams<C>,
41 r1cs: R1CS<C::ScalarField>,
42 // running instance
43 instance: CommittedInstance<C>,
44 w: Witness<C>,
45 // incomming instances
46 vec_instances: Vec<CommittedInstance<C>>,
47 vec_w: Vec<Witness<C>>,
48 ) {
49 let t = instance.betas.len();
50 let n = r1cs.A[0].len();
51
52 let delta = tr.get_challenge();
53
54 let deltas = powers_of_beta(delta, t);
55
56 let f_w = eval_f(&r1cs, &w.w);
57 dbg!(w.w.len());
58 dbg!(f_w.len());
59 dbg!(n);
60
61 // F(X)
62 let mut F_X: SparsePolynomial<C::ScalarField> = SparsePolynomial::zero();
63 for i in 0..n {
64 let lhs = pow_i_over_x::<C::ScalarField>(i, &instance.betas, &deltas);
65 let curr = &lhs * f_w[i];
66 F_X = F_X.add(curr);
67 }
68 // TODO return F(X)
69
70 let alpha = tr.get_challenge();
71 // eval F(alpha)
72 let F_alpha = F_X.evaluate(&alpha);
73
74 // betas*
75 let betas_star: Vec<C::ScalarField> = instance
76 .betas
77 .iter()
78 .zip(
79 deltas
80 .iter()
81 .map(|delta_i| alpha * delta_i)
82 .collect::<Vec<C::ScalarField>>(),
83 )
84 .map(|(beta_i, delta_i_alpha)| *beta_i + delta_i_alpha)
85 .collect();
86
87 // sanity check: check that the new randomized instnace (the original instance but with
88 // 'refreshed' randomness) satisfies the relation.
89 assert!(check_instance(
90 r1cs,
91 CommittedInstance {
92 phi: instance.phi,
93 betas: betas_star,
94 e: F_alpha,
95 },
96 w.clone(),
97 ));
98 }
99}
100
101// naive impl of pow_i for betas, assuming that betas=(b, b^2, b^4, ..., b^{2^{t-1}})
102fn pow_i<F: PrimeField>(i: usize, betas: &Vec<F>) -> F {
103 // WIP check if makes more sense to do it with ifs instead of arithmetic
104
105 let n = 2_u64.pow(betas.len() as u32);
106 let b = bit_decompose(i as u64, n as usize);
107
108 let mut r: F = F::one();
109 for (j, beta_i) in betas.iter().enumerate() {
110 let mut b_j = F::zero();
111 if b[j] {
112 b_j = F::one();
113 }
114 r *= (F::one() - b_j) + b_j * betas[j];
115 }
116 r
117}
118
119fn pow_i_over_x<F: PrimeField>(i: usize, betas: &Vec<F>, deltas: &Vec<F>) -> SparsePolynomial<F> {
120 assert_eq!(betas.len(), deltas.len());
121
122 let n = 2_u64.pow(betas.len() as u32);
123 let b = bit_decompose(i as u64, n as usize);
124
125 let mut r: SparsePolynomial<F> =
126 SparsePolynomial::<F>::from_coefficients_vec(vec![(0, F::one())]); // start with r(x) = 1
127 for (j, beta_i) in betas.iter().enumerate() {
128 if b[j] {
129 let curr: SparsePolynomial<F> =
130 SparsePolynomial::<F>::from_coefficients_vec(vec![(0, betas[j]), (1, deltas[j])]);
131 r = r.mul(&curr);
132 }
133 }
134 r
135}
136
137#[derive(Clone, Debug)]
138pub struct R1CS<F: PrimeField> {
139 pub A: Vec<Vec<F>>,
140 pub B: Vec<Vec<F>>,
141 pub C: Vec<Vec<F>>,
142}
143
144// f(w) in R1CS context
145fn eval_f<F: PrimeField>(r1cs: &R1CS<F>, w: &Vec<F>) -> Vec<F> {
146 let AzBz = hadamard(&mat_vec_mul(&r1cs.A, &w), &mat_vec_mul(&r1cs.B, &w));
147 let Cz = mat_vec_mul(&r1cs.C, &w);
148 let f_w = vec_sub(&AzBz, &Cz);
149 f_w
150}
151
152fn check_instance<C: CurveGroup>(
153 r1cs: R1CS<C::ScalarField>,
154 instance: CommittedInstance<C>,
155 w: Witness<C>,
156) -> bool {
157 let n = 2_u64.pow(instance.betas.len() as u32) as usize;
158 dbg!(n);
159 dbg!(w.w.len());
160
161 let f_w = eval_f(&r1cs, &w.w); // f(w)
162 dbg!(f_w.len());
163
164 let mut r = C::ScalarField::zero();
165 for i in 0..n {
166 r += pow_i(i, &instance.betas) * f_w[i];
167 }
168 if instance.e == r {
169 return true;
170 }
171 false
172}
173
174#[cfg(test)]
175mod tests {
176 use super::*;
177 use crate::pedersen::Pedersen;
178 use crate::transcript::poseidon_test_config;
179 use ark_bls12_381::{Fr, G1Projective};
180 use ark_std::One;
181 use ark_std::UniformRand;
182
183 pub fn to_F_matrix<F: PrimeField>(M: Vec<Vec<usize>>) -> Vec<Vec<F>> {
184 let mut R: Vec<Vec<F>> = vec![Vec::new(); M.len()];
185 for i in 0..M.len() {
186 R[i] = vec![F::zero(); M[i].len()];
187 for j in 0..M[i].len() {
188 R[i][j] = F::from(M[i][j] as u64);
189 }
190 }
191 R
192 }
193 pub fn to_F_vec<F: PrimeField>(z: Vec<usize>) -> Vec<F> {
194 let mut r: Vec<F> = vec![F::zero(); z.len()];
195 for i in 0..z.len() {
196 r[i] = F::from(z[i] as u64);
197 }
198 r
199 }
200
201 pub fn get_test_r1cs<F: PrimeField>() -> R1CS<F> {
202 // R1CS for: x^3 + x + 5 = y (example from article
203 // https://www.vitalik.ca/general/2016/12/10/qap.html )
204 let A = to_F_matrix::<F>(vec![
205 vec![0, 1, 0, 0, 0, 0, /**/ 0, 0],
206 vec![0, 0, 0, 1, 0, 0, /**/ 0, 0],
207 vec![0, 1, 0, 0, 1, 0, /**/ 0, 0],
208 vec![5, 0, 0, 0, 0, 1, /**/ 0, 0],
209 //
210 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
211 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
212 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
213 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
214 ]);
215 let B = to_F_matrix::<F>(vec![
216 vec![0, 1, 0, 0, 0, 0, /**/ 0, 0],
217 vec![0, 1, 0, 0, 0, 0, /**/ 0, 0],
218 vec![1, 0, 0, 0, 0, 0, /**/ 0, 0],
219 vec![1, 0, 0, 0, 0, 0, /**/ 0, 0],
220 //
221 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
222 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
223 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
224 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
225 ]);
226 let C = to_F_matrix::<F>(vec![
227 vec![0, 0, 0, 1, 0, 0, /**/ 0, 0],
228 vec![0, 0, 0, 0, 1, 0, /**/ 0, 0],
229 vec![0, 0, 0, 0, 0, 1, /**/ 0, 0],
230 vec![0, 0, 1, 0, 0, 0, /**/ 0, 0],
231 //
232 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
233 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
234 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
235 vec![0, 0, 0, 0, 0, 0, /**/ 0, 0],
236 ]);
237
238 let r1cs = R1CS::<F> { A, B, C };
239 r1cs
240 }
241
242 pub fn get_test_z<F: PrimeField>(input: usize) -> Vec<F> {
243 // z = (1, io, w)
244 to_F_vec(vec![
245 1,
246 input,
247 input * input * input + input + 5, // x^3 + x + 5
248 input * input, // x^2
249 input * input * input, // x^2 * x
250 input * input * input + input, // x^3 + x
251 0, // pad to pow of 2
252 0,
253 ])
254 }
255
256 #[test]
257 fn test_pow_i() {
258 let mut rng = ark_std::test_rng();
259 let t = 4;
260 let n = 16;
261 let beta = Fr::rand(&mut rng);
262 let betas = powers_of_beta(beta, t);
263 let not_betas = all_powers(beta, n);
264
265 for i in 0..n {
266 assert_eq!(pow_i(i, &betas), not_betas[i]);
267 }
268 }
269
270 #[test]
271 fn test_pow_i_over_x() {
272 let mut rng = ark_std::test_rng();
273 let t = 3;
274 let n = 8;
275 // let beta = Fr::rand(&mut rng);
276 // let delta = Fr::rand(&mut rng);
277 let beta = Fr::from(3);
278 let delta = Fr::from(5);
279 let betas = powers_of_beta(beta, t);
280 let deltas = powers_of_beta(delta, t);
281
282 // for i in 0..n {
283 // dbg!(pow_i_over_x(i, &betas, &deltas));
284 // }
285 }
286
287 #[test]
288 fn test_eval_f() {
289 let r1cs = get_test_r1cs::<Fr>();
290 let mut z = get_test_z::<Fr>(3);
291
292 let f_w = eval_f(&r1cs, &z);
293 assert!(is_zero_vec(&f_w));
294
295 z[1] = Fr::from(111);
296 let f_w = eval_f(&r1cs, &z);
297 assert!(!is_zero_vec(&f_w));
298 }
299
300 #[test]
301 fn test_fold_prover() {
302 let mut rng = ark_std::test_rng();
303 let pedersen_params = Pedersen::<G1Projective>::new_params(&mut rng, 100); // 100 is wip, will get it from actual vec
304 let poseidon_config = poseidon_test_config::<Fr>();
305
306 let r1cs = get_test_r1cs::<Fr>();
307 let mut z = get_test_z::<Fr>(3);
308
309 // init Prover's transcript
310 let mut transcript_p = Transcript::<Fr, G1Projective>::new(&poseidon_config);
311
312 let n = z.len();
313 let t = log2(n) as usize;
314 dbg!(n);
315 dbg!(t);
316
317 let beta = Fr::rand(&mut rng);
318 let betas = powers_of_beta(beta, t);
319
320 let witness = Witness::<G1Projective> {
321 w: z, // WIP
322 r_w: Fr::rand(&mut rng),
323 };
324 let phi = Pedersen::<G1Projective>::commit(&pedersen_params, &witness.w, &witness.r_w);
325 let instance = CommittedInstance::<G1Projective> {
326 phi,
327 betas,
328 e: Fr::zero(),
329 };
330
331 Folding::<G1Projective>::prover(
332 &mut transcript_p,
333 &pedersen_params,
334 r1cs,
335 instance,
336 witness,
337 Vec::new(),
338 Vec::new(),
339 );
340 }
341}