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