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: Vec<C::ScalarField>,
 45        // incomming instances
 46        vec_instances: Vec<CommittedInstance<C>>,
 47        vec_w: Vec<C::ScalarField>,
 48    ) {
 49        let t = instance.betas.len();
 50        let n = w.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);
 57
 58        // F(X)
 59        let mut F_X: SparsePolynomial<C::ScalarField> = SparsePolynomial::zero();
 60        for i in 0..n {
 61            let lhs = pow_i_over_x::<C::ScalarField>(i, &instance.betas, &deltas);
 62            F_X = F_X.add(&lhs * f_w[i]);
 63        }
 64        // TODO return F(X)
 65
 66        let alpha = tr.get_challenge();
 67        // WIP
 68    }
 69}
 70
 71// naive impl of pow_i for betas, assuming that betas=(b, b^2, b^4, ..., b^{2^{t-1}})
 72fn pow_i<F: PrimeField>(i: usize, betas: &Vec<F>) -> F {
 73    // WIP check if makes more sense to do it with ifs instead of arithmetic
 74
 75    let n = 2_u64.pow(betas.len() as u32);
 76    let b = bit_decompose(i as u64, n as usize);
 77
 78    let mut r: F = F::one();
 79    for (j, beta_i) in betas.iter().enumerate() {
 80        let mut b_j = F::zero();
 81        if b[j] {
 82            b_j = F::one();
 83        }
 84        r *= (F::one() - b_j) + b_j * betas[j];
 85    }
 86    r
 87}
 88
 89fn pow_i_over_x<F: PrimeField>(i: usize, betas: &Vec<F>, deltas: &Vec<F>) -> SparsePolynomial<F> {
 90    assert_eq!(betas.len(), deltas.len());
 91
 92    let n = 2_u64.pow(betas.len() as u32);
 93    let b = bit_decompose(i as u64, n as usize);
 94
 95    let mut r: SparsePolynomial<F> =
 96        SparsePolynomial::<F>::from_coefficients_vec(vec![(0, F::one())]); // start with r(x) = 1
 97    for (j, beta_i) in betas.iter().enumerate() {
 98        if b[j] {
 99            let curr: SparsePolynomial<F> =
100                SparsePolynomial::<F>::from_coefficients_vec(vec![(0, betas[j]), (1, deltas[j])]);
101            r = r.mul(&curr);
102        }
103    }
104    r
105}
106
107#[derive(Clone, Debug)]
108pub struct R1CS<F: PrimeField> {
109    pub A: Vec<Vec<F>>,
110    pub B: Vec<Vec<F>>,
111    pub C: Vec<Vec<F>>,
112}
113
114// f(w) in R1CS context
115fn eval_f<F: PrimeField>(r1cs: &R1CS<F>, w: &Vec<F>) -> Vec<F> {
116    let AzBz = hadamard(&mat_vec_mul(&r1cs.A, &w), &mat_vec_mul(&r1cs.B, &w));
117    let Cz = mat_vec_mul(&r1cs.C, &w);
118    let f_w = vec_sub(&AzBz, &Cz);
119    f_w
120}
121
122fn check_instance<C: CurveGroup>(
123    r1cs: R1CS<C::ScalarField>,
124    instance: CommittedInstance<C>,
125    w: Witness<C>,
126) -> bool {
127    let n = 2_u64.pow(instance.betas.len() as u32) as usize;
128
129    let f_w = eval_f(&r1cs, &w.w); // f(w)
130
131    let mut r = C::ScalarField::zero();
132    for i in 0..n {
133        r += pow_i(i, &instance.betas) * f_w[i];
134    }
135    false
136}
137
138#[cfg(test)]
139mod tests {
140    use super::*;
141    use crate::pedersen::Pedersen;
142    use crate::transcript::poseidon_test_config;
143    use ark_bls12_381::{Fr, G1Projective};
144    use ark_std::One;
145    use ark_std::UniformRand;
146
147    pub fn to_F_matrix<F: PrimeField>(M: Vec<Vec<usize>>) -> Vec<Vec<F>> {
148        let mut R: Vec<Vec<F>> = vec![Vec::new(); M.len()];
149        for i in 0..M.len() {
150            R[i] = vec![F::zero(); M[i].len()];
151            for j in 0..M[i].len() {
152                R[i][j] = F::from(M[i][j] as u64);
153            }
154        }
155        R
156    }
157    pub fn to_F_vec<F: PrimeField>(z: Vec<usize>) -> Vec<F> {
158        let mut r: Vec<F> = vec![F::zero(); z.len()];
159        for i in 0..z.len() {
160            r[i] = F::from(z[i] as u64);
161        }
162        r
163    }
164
165    pub fn get_test_r1cs<F: PrimeField>() -> R1CS<F> {
166        // R1CS for: x^3 + x + 5 = y (example from article
167        // https://www.vitalik.ca/general/2016/12/10/qap.html )
168        let A = to_F_matrix::<F>(vec![
169            vec![0, 1, 0, 0, 0, 0],
170            vec![0, 0, 0, 1, 0, 0],
171            vec![0, 1, 0, 0, 1, 0],
172            vec![5, 0, 0, 0, 0, 1],
173        ]);
174        let B = to_F_matrix::<F>(vec![
175            vec![0, 1, 0, 0, 0, 0],
176            vec![0, 1, 0, 0, 0, 0],
177            vec![1, 0, 0, 0, 0, 0],
178            vec![1, 0, 0, 0, 0, 0],
179        ]);
180        let C = to_F_matrix::<F>(vec![
181            vec![0, 0, 0, 1, 0, 0],
182            vec![0, 0, 0, 0, 1, 0],
183            vec![0, 0, 0, 0, 0, 1],
184            vec![0, 0, 1, 0, 0, 0],
185        ]);
186
187        let r1cs = R1CS::<F> { A, B, C };
188        r1cs
189    }
190
191    pub fn get_test_z<F: PrimeField>(input: usize) -> Vec<F> {
192        // z = (1, io, w)
193        to_F_vec(vec![
194            1,
195            input,
196            input * input * input + input + 5, // x^3 + x + 5
197            input * input,                     // x^2
198            input * input * input,             // x^2 * x
199            input * input * input + input,     // x^3 + x
200        ])
201    }
202
203    #[test]
204    fn test_pow_i() {
205        let mut rng = ark_std::test_rng();
206        let t = 4;
207        let n = 16;
208        let beta = Fr::rand(&mut rng);
209        let betas = powers_of_beta(beta, t);
210        let not_betas = all_powers(beta, n);
211
212        for i in 0..n {
213            assert_eq!(pow_i(i, &betas), not_betas[i]);
214        }
215    }
216
217    #[test]
218    fn test_pow_i_over_x() {
219        let mut rng = ark_std::test_rng();
220        let t = 3;
221        let n = 8;
222        // let beta = Fr::rand(&mut rng);
223        // let delta = Fr::rand(&mut rng);
224        let beta = Fr::from(3);
225        let delta = Fr::from(5);
226        let betas = powers_of_beta(beta, t);
227        let deltas = powers_of_beta(delta, t);
228
229        // for i in 0..n {
230        //     dbg!(pow_i_over_x(i, &betas, &deltas));
231        // }
232    }
233
234    #[test]
235    fn test_eval_f() {
236        let r1cs = get_test_r1cs::<Fr>();
237        let mut z = get_test_z::<Fr>(3);
238
239        let f_w = eval_f(&r1cs, &z);
240        assert!(is_zero_vec(&f_w));
241
242        z[1] = Fr::from(111);
243        let f_w = eval_f(&r1cs, &z);
244        assert!(!is_zero_vec(&f_w));
245    }
246}