1//! This module implements the permutation check protocol.
 2
 3use ark_ff::PrimeField;
 4use ark_poly::DenseMultilinearExtension;
 5
 6use crate::PolyIOPErrors;
 7
 8/// Compute `prod(0,x) := prod(0, x1, …, xn)` which is the MLE over the
 9/// evaluations of the following polynomial on the boolean hypercube {0,1}^n:
10///
11///  (w(x) + \beta s_id(x) + \gamma)/(w(x) + \beta s_perm(x) + \gamma)
12///
13/// where
14/// - beta and gamma are challenges
15/// - w(x), s_id(x), s_perm(x) are mle-s
16#[allow(dead_code)]
17// TODO: remove
18fn compute_prod_0<F: PrimeField>(
19    beta: &F,
20    gamma: &F,
21    w: &DenseMultilinearExtension<F>,
22    s_id: &DenseMultilinearExtension<F>,
23    s_perm: &DenseMultilinearExtension<F>,
24) -> Result<DenseMultilinearExtension<F>, PolyIOPErrors> {
25    let num_vars = w.num_vars;
26
27    if num_vars != s_id.num_vars || num_vars != s_perm.num_vars {
28        return Err(PolyIOPErrors::InvalidParameters(
29            "num of variables do not match".to_string(),
30        ));
31    }
32    let eval: Vec<F> = w
33        .iter()
34        .zip(s_id.iter().zip(s_perm.iter()))
35        .map(|(wi, (s_id_i, s_perm_i))| {
36            let tmp = *wi + *gamma;
37            (tmp + *beta * *s_id_i) / (tmp + *beta * *s_perm_i)
38        })
39        .collect();
40
41    let res = DenseMultilinearExtension::from_evaluations_vec(num_vars, eval);
42
43    Ok(res)
44}
45
46#[cfg(test)]
47mod test {
48    use super::*;
49    use crate::utils::bit_decompose;
50    use ark_bls12_381::Fr;
51    use ark_ff::UniformRand;
52    use ark_poly::MultilinearExtension;
53    use ark_std::test_rng;
54
55    #[test]
56    fn test_compute_prod_0() -> Result<(), PolyIOPErrors> {
57        let mut rng = test_rng();
58
59        for num_vars in 2..6 {
60            let w_vec: Vec<Fr> = (0..(1 << num_vars)).map(|_| Fr::rand(&mut rng)).collect();
61            let w = DenseMultilinearExtension::from_evaluations_vec(num_vars, w_vec);
62
63            let s_id_vec: Vec<Fr> = (0..(1 << num_vars)).map(|_| Fr::rand(&mut rng)).collect();
64            let s_id = DenseMultilinearExtension::from_evaluations_vec(num_vars, s_id_vec);
65
66            let s_perm_vec: Vec<Fr> = (0..(1 << num_vars)).map(|_| Fr::rand(&mut rng)).collect();
67            let s_perm = DenseMultilinearExtension::from_evaluations_vec(num_vars, s_perm_vec);
68
69            let beta = Fr::rand(&mut rng);
70            let gamma = Fr::rand(&mut rng);
71            for i in 0..1 << num_vars {
72                let r: Vec<Fr> = bit_decompose(i, num_vars)
73                    .iter()
74                    .map(|&x| Fr::from(x))
75                    .collect();
76
77                let prod_0 = compute_prod_0(&beta, &gamma, &w, &s_id, &s_perm)?;
78
79                let eval = prod_0.evaluate(&r).unwrap();
80
81                let w_eval = w.evaluate(&r).unwrap();
82                let s_id_eval = s_id.evaluate(&r).unwrap();
83                let s_perm_eval = s_perm.evaluate(&r).unwrap();
84                let eval_rec =
85                    (w_eval + beta * s_id_eval + gamma) / (w_eval + beta * s_perm_eval + gamma);
86
87                assert_eq!(eval, eval_rec);
88            }
89        }
90        Ok(())
91    }
92}