1use crate::sumcheck::unipoly::UniPoly;
  2use serde::{Deserialize, Serialize};
  3use tensor_pcs::{EqPoly, SparseMLPoly, 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 random_evals = (0..2usize.pow(num_vars as u32))
 54            .map(|_| F::random(&mut rng))
 55            .collect::<Vec<F>>();
 56        let blinder_poly_sum = random_evals.iter().fold(F::ZERO, |acc, x| acc + x);
 57        let blinder_poly = SparseMLPoly::from_dense(random_evals);
 58
 59        let blinder_poly_comm = pcs.commit(&blinder_poly);
 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
 74            .evals
 75            .iter()
 76            .map(|(_, x)| *x)
 77            .collect::<Vec<F>>();
 78        let mut eq_table = self.bound_eq_poly.evals();
 79
 80        let zero = F::ZERO;
 81        let one = F::ONE;
 82        let two = F::from(2);
 83        let three = F::from(3);
 84
 85        for j in 0..num_vars {
 86            let r_i = self.challenge[j];
 87
 88            let high_index = 2usize.pow((num_vars - j - 1) as u32);
 89
 90            let mut evals = [F::ZERO; 4];
 91
 92            // https://eprint.iacr.org/2019/317.pdf#subsection.3.2
 93            for b in 0..high_index {
 94                for (i, eval_at) in [zero, one, two, three].iter().enumerate() {
 95                    let a_eval = A_table[b] + (A_table[b + high_index] - A_table[b]) * eval_at;
 96                    let b_eval = B_table[b] + (B_table[b + high_index] - B_table[b]) * eval_at;
 97                    let c_eval = C_table[b] + (C_table[b + high_index] - C_table[b]) * eval_at;
 98                    let eq_eval = eq_table[b] + (eq_table[b + high_index] - eq_table[b]) * eval_at;
 99                    let blinder_eval = blinder_table[b]
100                        + (blinder_table[b + high_index] - blinder_table[b]) * eval_at;
101                    evals[i] += ((a_eval * b_eval - c_eval) * eq_eval) + rho * blinder_eval;
102                }
103
104                A_table[b] = A_table[b] + (A_table[b + high_index] - A_table[b]) * r_i;
105                B_table[b] = B_table[b] + (B_table[b + high_index] - B_table[b]) * r_i;
106                C_table[b] = C_table[b] + (C_table[b + high_index] - C_table[b]) * r_i;
107                eq_table[b] = eq_table[b] + (eq_table[b + high_index] - eq_table[b]) * r_i;
108                blinder_table[b] =
109                    blinder_table[b] + (blinder_table[b + high_index] - blinder_table[b]) * r_i;
110            }
111
112            // TODO: Maybe send the evaluations to the verifier?
113            let round_poly = UniPoly::interpolate(&evals);
114
115            round_polys.push(round_poly);
116        }
117
118        let v_A = A_table[0];
119        let v_B = B_table[0];
120        let v_C = C_table[0];
121
122        // Prove the evaluation of the blinder polynomial at rx.
123        let blinder_poly_eval_proof = pcs.open(
124            &blinder_poly_comm,
125            &blinder_poly,
126            &self.challenge,
127            transcript,
128        );
129
130        (
131            SCPhase1Proof {
132                blinder_poly_sum,
133                round_polys,
134                blinder_poly_eval_proof,
135            },
136            (v_A, v_B, v_C),
137        )
138    }
139
140    pub fn verify_round_polys(proof: &SCPhase1Proof<F>, challenge: &[F], rho: F) -> F {
141        debug_assert_eq!(proof.round_polys.len(), challenge.len());
142
143        let zero = F::ZERO;
144        let one = F::ONE;
145
146        // target = 0 + rho * blinder_poly_sum
147        let mut target = rho * proof.blinder_poly_sum;
148        for (i, round_poly) in proof.round_polys.iter().enumerate() {
149            assert_eq!(
150                round_poly.eval(zero) + round_poly.eval(one),
151                target,
152                "round poly {} failed",
153                i
154            );
155            target = round_poly.eval(challenge[i]);
156        }
157
158        target
159    }
160}
161
162#[cfg(test)]
163mod tests {
164    use super::*;
165    use halo2curves::secp256k1::Fp;
166    type F = Fp;
167    use halo2curves::ff::Field;
168
169    #[test]
170    fn test_unipoly_3() {
171        let coeffs = [F::from(1u64), F::from(2u64), F::from(3u64), F::from(4u64)];
172        let eval_at = Fp::from(33);
173
174        let mut expected_eval = F::ZERO;
175        for i in 0..coeffs.len() {
176            expected_eval += coeffs[i] * eval_at.pow(&[3 - i as u64, 0, 0, 0]);
177        }
178
179        let mut evals = [F::ZERO; 4];
180        for i in 0..4 {
181            let eval_at = F::from(i as u64);
182            let mut eval_i = F::ZERO;
183            for j in 0..coeffs.len() {
184                eval_i += coeffs[j] * eval_at.pow(&[3 - j as u64, 0, 0, 0]);
185            }
186            evals[i] = eval_i;
187        }
188
189        let uni_poly = UniPoly::interpolate(&evals);
190        let eval = uni_poly.eval(eval_at);
191        assert_eq!(eval, expected_eval);
192    }
193}