1#![allow(non_snake_case)]
  2
  3pub mod merkletree;
  4use merkletree::{MerkleTreePoseidon as MT, Params as MTParams};
  5
  6use ark_ff::PrimeField;
  7use ark_poly::{univariate::DensePolynomial, UVPolynomial};
  8use ark_std::log2;
  9use ark_std::marker::PhantomData;
 10use ark_std::ops::Mul;
 11use ark_std::{rand::Rng, UniformRand};
 12
 13pub struct FRI<F: PrimeField, P: UVPolynomial<F>> {
 14    _f: PhantomData<F>,
 15    _poly: PhantomData<P>,
 16}
 17
 18impl<F: PrimeField, P: UVPolynomial<F>> FRI<F, P> {
 19    pub fn new() -> Self {
 20        Self {
 21            _f: PhantomData,
 22            _poly: PhantomData,
 23        }
 24    }
 25
 26    pub fn split(p: &P) -> (P, P) {
 27        // let d = p.degree() + 1;
 28        let d = p.coeffs().len();
 29        if (d != 0) && (d & (d - 1) != 0) {
 30            println!("d={:?}", d);
 31            panic!("d should be a power of 2");
 32        }
 33
 34        let coeffs = p.coeffs();
 35        let odd: Vec<F> = coeffs.iter().step_by(2).cloned().collect();
 36        let even: Vec<F> = coeffs.iter().skip(1).step_by(2).cloned().collect();
 37
 38        return (
 39            P::from_coefficients_vec(odd),
 40            P::from_coefficients_vec(even),
 41        );
 42    }
 43
 44    pub fn prove<R: Rng>(rng: &mut R, p: &P) -> (Vec<F>, [F; 2]) {
 45        // f_0(x) = fL_0(x^2) + x fR_0(x^2)
 46        let mut f_i1 = p.clone();
 47
 48        // TODO challenge a_0
 49        let mut f_is: Vec<P> = Vec::new();
 50        f_is.push(p.clone());
 51        let mut commitments: Vec<F> = Vec::new();
 52        let mut mts: Vec<MT<F>> = Vec::new();
 53        while f_i1.degree() > 1 {
 54            let alpha_i = F::from(3_u64); // TODO: WIP, defined by Verifier (well, hash transcript)
 55
 56            let (fL_i, fR_i) = Self::split(&f_i1);
 57
 58            // compute f_{i+1}(x) = fL_i(x) + alpha_i * fR_i(x)
 59            let aux = DensePolynomial::from_coefficients_slice(fR_i.coeffs());
 60            f_i1 = fL_i.clone() + P::from_coefficients_slice(aux.mul(alpha_i).coeffs());
 61            f_is.push(f_i1.clone());
 62        }
 63        let (fL_i, fR_i) = Self::split(&f_i1);
 64        let constant_fL_l: F = fL_i.coeffs()[0].clone();
 65        let constant_fR_l: F = fR_i.coeffs()[0].clone();
 66
 67        // TODO evaluate f_i(z^{2^i})
 68        let evals: Vec<F> = Vec::new();
 69
 70        (evals, [constant_fL_l, constant_fR_l])
 71    }
 72}
 73
 74#[cfg(test)]
 75mod tests {
 76    use super::*;
 77    use ark_ff::Field;
 78    use ark_std::UniformRand;
 79    pub type Fr = ark_bn254::Fr; // scalar field
 80    use ark_poly::univariate::DensePolynomial;
 81    use ark_poly::Polynomial;
 82
 83    #[test]
 84    fn test_split() {
 85        let mut rng = ark_std::test_rng();
 86        let deg = 7;
 87        let p = DensePolynomial::<Fr>::rand(deg, &mut rng);
 88        assert_eq!(p.degree(), deg);
 89
 90        type FRIC = FRI<Fr, DensePolynomial<Fr>>;
 91        let (pL, pR) = FRIC::split(&p);
 92
 93        // check that f(z) == fL(x^2) + x * fR(x^2), for a rand z
 94        let z = Fr::rand(&mut rng);
 95        assert_eq!(
 96            p.evaluate(&z),
 97            pL.evaluate(&z.square()) + z * pR.evaluate(&z.square())
 98        );
 99    }
100}