1use crate::polynomial::ml_poly::MlPoly;
  2use crate::sumcheck::unipoly::UniPoly;
  3use serde::{Deserialize, Serialize};
  4use tensor_pcs::{EqPoly, Transcript};
  5
  6use crate::FieldExt;
  7
  8#[derive(Serialize, Deserialize)]
  9pub struct SCPhase1Proof<F: FieldExt> {
 10    pub blinder_poly_sum: F,
 11    pub blinder_poly_eval_claim: F,
 12    pub round_polys: Vec<UniPoly<F>>,
 13}
 14
 15pub struct SumCheckPhase1<F: FieldExt> {
 16    Az_evals: Vec<F>,
 17    Bz_evals: Vec<F>,
 18    Cz_evals: Vec<F>,
 19    bound_eq_poly: EqPoly<F>,
 20    challenge: Vec<F>,
 21}
 22
 23impl<F: FieldExt> SumCheckPhase1<F> {
 24    pub fn new(
 25        Az_evals: Vec<F>,
 26        Bz_evals: Vec<F>,
 27        Cz_evals: Vec<F>,
 28        tau: Vec<F>,
 29        challenge: Vec<F>,
 30    ) -> Self {
 31        let bound_eq_poly = EqPoly::new(tau);
 32        Self {
 33            Az_evals,
 34            Bz_evals,
 35            Cz_evals,
 36            bound_eq_poly,
 37            challenge,
 38        }
 39    }
 40
 41    pub fn prove(&self, transcript: &mut Transcript<F>) -> (SCPhase1Proof<F>, (F, F, F)) {
 42        let num_vars = (self.Az_evals.len() as f64).log2() as usize;
 43        let mut round_polys = Vec::<UniPoly<F>>::with_capacity(num_vars - 1);
 44
 45        let mut rng = rand::thread_rng();
 46        // Sample a blinding polynomial g(x_1, ..., x_m) of degree 3
 47        let random_evals = (0..2usize.pow(num_vars as u32))
 48            .map(|_| F::random(&mut rng))
 49            .collect::<Vec<F>>();
 50        let blinder_poly_sum = random_evals.iter().fold(F::ZERO, |acc, x| acc + x);
 51        let blinder_poly = MlPoly::new(random_evals);
 52
 53        transcript.append_fe(&blinder_poly_sum);
 54        let rho = transcript.challenge_fe();
 55
 56        // Compute the sum of g(x_1, ... x_m) over the boolean hypercube
 57
 58        // Do the sum check for f + \rho g
 59
 60        let mut A_table = self.Az_evals.clone();
 61        let mut B_table = self.Bz_evals.clone();
 62        let mut C_table = self.Cz_evals.clone();
 63        let mut blinder_table = blinder_poly.evals.clone();
 64        let mut eq_table = self.bound_eq_poly.evals();
 65
 66        let zero = F::ZERO;
 67        let one = F::ONE;
 68        let two = F::from(2);
 69        let three = F::from(3);
 70
 71        for j in 0..num_vars {
 72            let r_i = self.challenge[j];
 73
 74            let high_index = 2usize.pow((num_vars - j - 1) as u32);
 75
 76            let mut evals = [F::ZERO; 4];
 77
 78            // https://eprint.iacr.org/2019/317.pdf#subsection.3.2
 79            for b in 0..high_index {
 80                for (i, eval_at) in [zero, one, two, three].iter().enumerate() {
 81                    let a_eval = A_table[b] + (A_table[b + high_index] - A_table[b]) * eval_at;
 82                    let b_eval = B_table[b] + (B_table[b + high_index] - B_table[b]) * eval_at;
 83                    let c_eval = C_table[b] + (C_table[b + high_index] - C_table[b]) * eval_at;
 84                    let eq_eval = eq_table[b] + (eq_table[b + high_index] - eq_table[b]) * eval_at;
 85                    let blinder_eval = blinder_table[b]
 86                        + (blinder_table[b + high_index] - blinder_table[b]) * eval_at;
 87                    evals[i] += ((a_eval * b_eval - c_eval) * eq_eval) + rho * blinder_eval;
 88                }
 89
 90                A_table[b] = A_table[b] + (A_table[b + high_index] - A_table[b]) * r_i;
 91                B_table[b] = B_table[b] + (B_table[b + high_index] - B_table[b]) * r_i;
 92                C_table[b] = C_table[b] + (C_table[b + high_index] - C_table[b]) * r_i;
 93                eq_table[b] = eq_table[b] + (eq_table[b + high_index] - eq_table[b]) * r_i;
 94                blinder_table[b] =
 95                    blinder_table[b] + (blinder_table[b + high_index] - blinder_table[b]) * r_i;
 96            }
 97
 98            let round_poly = UniPoly::interpolate(&evals);
 99
100            round_polys.push(round_poly);
101        }
102
103        let v_A = A_table[0];
104        let v_B = B_table[0];
105        let v_C = C_table[0];
106
107        let rx = self.challenge.clone();
108        let blinder_poly_eval_claim = blinder_poly.eval(&rx);
109
110        // Prove the evaluation of the blinder polynomial at rx.
111
112        (
113            SCPhase1Proof {
114                blinder_poly_sum,
115                round_polys,
116                blinder_poly_eval_claim,
117            },
118            (v_A, v_B, v_C),
119        )
120    }
121
122    pub fn verify_round_polys(proof: &SCPhase1Proof<F>, challenge: &[F], rho: F) -> F {
123        debug_assert_eq!(proof.round_polys.len(), challenge.len());
124
125        let zero = F::ZERO;
126        let one = F::ONE;
127
128        // target = 0 + rho * blinder_poly_sum
129        let mut target = rho * proof.blinder_poly_sum;
130        for (i, round_poly) in proof.round_polys.iter().enumerate() {
131            assert_eq!(
132                round_poly.eval(zero) + round_poly.eval(one),
133                target,
134                "round poly {} failed",
135                i
136            );
137            target = round_poly.eval(challenge[i]);
138        }
139
140        target
141    }
142}
143
144#[cfg(test)]
145mod tests {
146    use super::*;
147    use halo2curves::secp256k1::Fp;
148    type F = Fp;
149    use halo2curves::ff::Field;
150
151    #[test]
152    fn test_unipoly_3() {
153        let coeffs = [F::from(1u64), F::from(2u64), F::from(3u64), F::from(4u64)];
154        let eval_at = Fp::from(33);
155
156        let mut expected_eval = F::ZERO;
157        for i in 0..coeffs.len() {
158            expected_eval += coeffs[i] * eval_at.pow(&[3 - i as u64, 0, 0, 0]);
159        }
160
161        let mut evals = [F::ZERO; 4];
162        for i in 0..4 {
163            let eval_at = F::from(i as u64);
164            let mut eval_i = F::ZERO;
165            for j in 0..coeffs.len() {
166                eval_i += coeffs[j] * eval_at.pow(&[3 - j as u64, 0, 0, 0]);
167            }
168            evals[i] = eval_i;
169        }
170
171        let uni_poly = UniPoly::interpolate(&evals);
172        let eval = uni_poly.eval(eval_at);
173        assert_eq!(eval, expected_eval);
174    }
175}