slop_sumcheck/
mle.rs

1use rayon::prelude::*;
2
3use slop_algebra::{
4    interpolate_univariate_polynomial, AbstractField, ExtensionField, Field, UnivariatePolynomial,
5};
6use slop_alloc::CpuBackend;
7use slop_multilinear::Mle;
8
9use crate::{
10    backend::{ComponentPolyEvalBackend, SumcheckPolyBackend},
11    SumCheckPolyFirstRoundBackend, SumcheckPolyBase,
12};
13
14impl<F: AbstractField> SumcheckPolyBase for Mle<F, CpuBackend> {
15    #[inline]
16    fn num_variables(&self) -> u32 {
17        self.num_variables()
18    }
19}
20
21impl<F, EF> ComponentPolyEvalBackend<Mle<F, CpuBackend>, EF> for CpuBackend
22where
23    F: Field,
24    EF: ExtensionField<F>,
25{
26    fn get_component_poly_evals(poly: &Mle<F, CpuBackend>) -> Vec<EF> {
27        let eval: F = *poly.guts()[[0, 0]];
28        vec![EF::from_base(eval)]
29    }
30}
31
32impl<F> SumcheckPolyBackend<Mle<F, CpuBackend>, F> for CpuBackend
33where
34    F: Field,
35{
36    fn fix_last_variable(poly: Mle<F, CpuBackend>, alpha: F) -> Mle<F, CpuBackend> {
37        poly.fix_last_variable(alpha)
38    }
39
40    fn sum_as_poly_in_last_variable(
41        poly: &Mle<F, CpuBackend>,
42        claim: Option<F>,
43    ) -> UnivariatePolynomial<F> {
44        // If the polynomial is 0-variate, the length of its guts is not divisible by 2, so we need
45        // to handle this case separately.
46        if poly.num_variables() == 0 {
47            return UnivariatePolynomial::new(vec![*poly.guts()[[0, 0]], F::zero()]);
48        }
49
50        let claim = claim.expect("expected a claim for a non-zero-variate polynomial");
51
52        assert_eq!(poly.num_polynomials(), 1);
53
54        let eval_zero = poly.guts().as_slice().par_iter().step_by(2).copied().sum::<F>();
55        let eval_one = claim - eval_zero;
56
57        interpolate_univariate_polynomial(&[F::zero(), F::one()], &[eval_zero, eval_one])
58    }
59}
60
61impl<F, EF> SumCheckPolyFirstRoundBackend<Mle<F, CpuBackend>, EF> for CpuBackend
62where
63    F: Field,
64    EF: ExtensionField<F>,
65{
66    type NextRoundPoly = Mle<EF, CpuBackend>;
67
68    fn fix_t_variables(poly: Mle<F, CpuBackend>, alpha: EF, t: usize) -> Self::NextRoundPoly {
69        assert_eq!(t, 1);
70        poly.fix_last_variable(alpha)
71    }
72
73    fn sum_as_poly_in_last_t_variables(
74        poly: &Mle<F, CpuBackend>,
75        claim: Option<EF>,
76        t: usize,
77    ) -> UnivariatePolynomial<EF> {
78        assert_eq!(t, 1);
79        assert!(poly.num_variables() > 0);
80        let claim = claim.expect("expected a claim for a non-zero-variate polynomial");
81
82        assert_eq!(poly.num_polynomials(), 1);
83
84        let eval_zero =
85            EF::from_base(poly.guts().as_slice().par_iter().step_by(2).copied().sum::<F>());
86        let eval_one = claim - eval_zero;
87
88        interpolate_univariate_polynomial(&[EF::zero(), EF::one()], &[eval_zero, eval_one])
89    }
90}
91#[cfg(test)]
92mod tests {
93    use rand::thread_rng;
94    use slop_algebra::{extension::BinomialExtensionField, AbstractExtensionField};
95    use slop_baby_bear::{
96        baby_bear_poseidon2::{my_bb_16_perm, Perm},
97        BabyBear,
98    };
99    use slop_challenger::DuplexChallenger;
100
101    use crate::{partially_verify_sumcheck_proof, reduce_sumcheck_to_evaluation};
102
103    use super::*;
104
105    #[test]
106    fn test_single_mle_sumcheck() {
107        let mut rng = thread_rng();
108
109        let mle = Mle::<BabyBear, CpuBackend>::rand(&mut rng, 1, 10);
110        type EF = BinomialExtensionField<BabyBear, 4>;
111
112        let default_perm = my_bb_16_perm();
113        let mut challenger = DuplexChallenger::<BabyBear, Perm, 16, 8>::new(default_perm.clone());
114
115        let claim = EF::from_base(mle.guts().as_slice().par_iter().copied().sum::<BabyBear>());
116
117        let (sumcheck_proof, _) = reduce_sumcheck_to_evaluation::<BabyBear, EF, _>(
118            vec![mle.clone()],
119            &mut challenger,
120            vec![claim],
121            1,
122            EF::one(),
123        );
124
125        // Verify the evaluation claim.
126        let (point, eval_claim) = sumcheck_proof.point_and_eval.clone();
127        let evaluation = mle.eval_at(&point)[0];
128        assert_eq!(evaluation, eval_claim);
129
130        // Verify the proof.
131        let mut challenger = DuplexChallenger::<BabyBear, Perm, 16, 8>::new(default_perm);
132        partially_verify_sumcheck_proof(&sumcheck_proof, &mut challenger, 10, 1).unwrap()
133    }
134}
slop_sumcheck/mle.rs

slop_sumcheck/
mle.rs
