1// code forked from:
  2// https://github.com/EspressoSystems/hyperplonk/tree/main/subroutines/src/poly_iop/sum_check
  3//
  4// Copyright (c) 2023 Espresso Systems (espressosys.com)
  5// This file is part of the HyperPlonk library.
  6
  7// You should have received a copy of the MIT License
  8// along with the HyperPlonk library. If not, see <https://mit-license.org/>.
  9
 10//! This module implements the sum check protocol.
 11
 12use crate::{
 13    transcript::Transcript,
 14    utils::virtual_polynomial::{VPAuxInfo, VirtualPolynomial},
 15};
 16use ark_crypto_primitives::sponge::Absorb;
 17use ark_ff::PrimeField;
 18use ark_poly::univariate::DensePolynomial;
 19use ark_poly::{DenseMultilinearExtension, DenseUVPolynomial, Polynomial};
 20use ark_std::{end_timer, start_timer};
 21use std::{fmt::Debug, marker::PhantomData, sync::Arc};
 22
 23use crate::utils::sum_check::structs::IOPProverMessage;
 24use crate::utils::sum_check::structs::IOPVerifierState;
 25use espresso_subroutines::poly_iop::prelude::PolyIOPErrors;
 26use structs::{IOPProof, IOPProverState};
 27
 28mod prover;
 29pub mod structs;
 30pub mod verifier;
 31
 32/// A generic sum-check trait over a curve group
 33pub trait SumCheck<F: PrimeField> {
 34    type VirtualPolynomial;
 35    type VPAuxInfo;
 36    type MultilinearExtension;
 37
 38    type SumCheckProof: Clone + Debug + Default + PartialEq;
 39    type SumCheckSubClaim: Clone + Debug + Default + PartialEq;
 40
 41    /// Extract sum from the proof
 42    fn extract_sum(proof: &Self::SumCheckProof) -> F;
 43
 44    /// Generate proof of the sum of polynomial over {0,1}^`num_vars`
 45    ///
 46    /// The polynomial is represented in the form of a VirtualPolynomial.
 47    fn prove(
 48        poly: &Self::VirtualPolynomial,
 49        transcript: &mut impl Transcript<F>,
 50    ) -> Result<Self::SumCheckProof, PolyIOPErrors>;
 51
 52    /// Verify the claimed sum using the proof
 53    fn verify(
 54        sum: F,
 55        proof: &Self::SumCheckProof,
 56        aux_info: &Self::VPAuxInfo,
 57        transcript: &mut impl Transcript<F>,
 58    ) -> Result<Self::SumCheckSubClaim, PolyIOPErrors>;
 59}
 60
 61/// Trait for sum check protocol prover side APIs.
 62pub trait SumCheckProver<F: PrimeField>
 63where
 64    Self: Sized,
 65{
 66    type VirtualPolynomial;
 67    type ProverMessage;
 68
 69    /// Initialize the prover state to argue for the sum of the input polynomial
 70    /// over {0,1}^`num_vars`.
 71    fn prover_init(polynomial: &Self::VirtualPolynomial) -> Result<Self, PolyIOPErrors>;
 72
 73    /// Receive message from verifier, generate prover message, and proceed to
 74    /// next round.
 75    ///
 76    /// Main algorithm used is from section 3.2 of [XZZPS19](https://eprint.iacr.org/2019/317.pdf#subsection.3.2).
 77    fn prove_round_and_update_state(
 78        &mut self,
 79        challenge: &Option<F>,
 80    ) -> Result<Self::ProverMessage, PolyIOPErrors>;
 81}
 82
 83/// Trait for sum check protocol verifier side APIs.
 84pub trait SumCheckVerifier<F: PrimeField> {
 85    type VPAuxInfo;
 86    type ProverMessage;
 87    type Challenge;
 88    type SumCheckSubClaim;
 89
 90    /// Initialize the verifier's state.
 91    fn verifier_init(index_info: &Self::VPAuxInfo) -> Self;
 92
 93    /// Run verifier for the current round, given a prover message.
 94    ///
 95    /// Note that `verify_round_and_update_state` only samples and stores
 96    /// challenges; and update the verifier's state accordingly. The actual
 97    /// verifications are deferred (in batch) to `check_and_generate_subclaim`
 98    /// at the last step.
 99    fn verify_round_and_update_state(
100        &mut self,
101        prover_msg: &Self::ProverMessage,
102        transcript: &mut impl Transcript<F>,
103    ) -> Result<Self::Challenge, PolyIOPErrors>;
104
105    /// This function verifies the deferred checks in the interactive version of
106    /// the protocol; and generate the subclaim. Returns an error if the
107    /// proof failed to verify.
108    ///
109    /// If the asserted sum is correct, then the multilinear polynomial
110    /// evaluated at `subclaim.point` will be `subclaim.expected_evaluation`.
111    /// Otherwise, it is highly unlikely that those two will be equal.
112    /// Larger field size guarantees smaller soundness error.
113    fn check_and_generate_subclaim(
114        &self,
115        asserted_sum: &F,
116    ) -> Result<Self::SumCheckSubClaim, PolyIOPErrors>;
117}
118
119/// A SumCheckSubClaim is a claim generated by the verifier at the end of
120/// verification when it is convinced.
121#[derive(Clone, Debug, Default, PartialEq, Eq)]
122pub struct SumCheckSubClaim<F: PrimeField> {
123    /// the multi-dimensional point that this multilinear extension is evaluated
124    /// to
125    pub point: Vec<F>,
126    /// the expected evaluation
127    pub expected_evaluation: F,
128}
129
130#[derive(Clone, Debug, Default, Copy, PartialEq, Eq)]
131pub struct IOPSumCheck<F: PrimeField, T: Transcript<F>> {
132    #[doc(hidden)]
133    phantom: PhantomData<F>,
134    #[doc(hidden)]
135    phantom2: PhantomData<T>,
136}
137
138impl<F: PrimeField + Absorb, T: Transcript<F>> SumCheck<F> for IOPSumCheck<F, T> {
139    type SumCheckProof = IOPProof<F>;
140    type VirtualPolynomial = VirtualPolynomial<F>;
141    type VPAuxInfo = VPAuxInfo<F>;
142    type MultilinearExtension = Arc<DenseMultilinearExtension<F>>;
143    type SumCheckSubClaim = SumCheckSubClaim<F>;
144
145    fn extract_sum(proof: &Self::SumCheckProof) -> F {
146        let start = start_timer!(|| "extract sum");
147        let poly = DensePolynomial::from_coefficients_vec(proof.proofs[0].coeffs.clone());
148        let res = poly.evaluate(&F::ONE) + poly.evaluate(&F::ZERO);
149        end_timer!(start);
150        res
151    }
152
153    fn prove(
154        poly: &VirtualPolynomial<F>,
155        transcript: &mut impl Transcript<F>,
156    ) -> Result<IOPProof<F>, PolyIOPErrors> {
157        transcript.absorb(&F::from(poly.aux_info.num_variables as u64));
158        transcript.absorb(&F::from(poly.aux_info.max_degree as u64));
159        let mut prover_state: IOPProverState<F> = IOPProverState::prover_init(poly)?;
160        let mut challenge: Option<F> = None;
161        let mut prover_msgs: Vec<IOPProverMessage<F>> =
162            Vec::with_capacity(poly.aux_info.num_variables);
163        for _ in 0..poly.aux_info.num_variables {
164            let prover_msg: IOPProverMessage<F> =
165                IOPProverState::prove_round_and_update_state(&mut prover_state, &challenge)?;
166            transcript.absorb(&prover_msg.coeffs);
167            prover_msgs.push(prover_msg);
168            challenge = Some(transcript.get_challenge());
169        }
170        if let Some(p) = challenge {
171            prover_state.challenges.push(p)
172        };
173        Ok(IOPProof {
174            point: prover_state.challenges,
175            proofs: prover_msgs,
176        })
177    }
178
179    fn verify(
180        claimed_sum: F,
181        proof: &IOPProof<F>,
182        aux_info: &VPAuxInfo<F>,
183        transcript: &mut impl Transcript<F>,
184    ) -> Result<SumCheckSubClaim<F>, PolyIOPErrors> {
185        transcript.absorb(&F::from(aux_info.num_variables as u64));
186        transcript.absorb(&F::from(aux_info.max_degree as u64));
187        let mut verifier_state = IOPVerifierState::verifier_init(aux_info);
188        for i in 0..aux_info.num_variables {
189            let prover_msg = proof.proofs.get(i).expect("proof is incomplete");
190            transcript.absorb(&prover_msg.coeffs);
191            IOPVerifierState::verify_round_and_update_state(
192                &mut verifier_state,
193                prover_msg,
194                transcript,
195            )?;
196        }
197
198        IOPVerifierState::check_and_generate_subclaim(&verifier_state, &claimed_sum)
199    }
200}
201
202#[cfg(test)]
203pub mod tests {
204    use std::sync::Arc;
205
206    use ark_crypto_primitives::sponge::poseidon::PoseidonSponge;
207    use ark_crypto_primitives::sponge::CryptographicSponge;
208    use ark_ff::Field;
209    use ark_pallas::Fr;
210    use ark_poly::DenseMultilinearExtension;
211    use ark_poly::MultilinearExtension;
212    use ark_std::test_rng;
213
214    use crate::transcript::poseidon::poseidon_canonical_config;
215    use crate::utils::sum_check::SumCheck;
216    use crate::utils::virtual_polynomial::VirtualPolynomial;
217
218    use super::IOPSumCheck;
219
220    #[test]
221    pub fn sumcheck_poseidon() {
222        let n_vars = 5;
223
224        let mut rng = test_rng();
225        let poly_mle = DenseMultilinearExtension::rand(n_vars, &mut rng);
226        let virtual_poly = VirtualPolynomial::new_from_mle(&Arc::new(poly_mle), Fr::ONE);
227
228        sumcheck_poseidon_opt(virtual_poly);
229
230        // test with zero poly
231        let poly_mle = DenseMultilinearExtension::from_evaluations_vec(
232            n_vars,
233            vec![Fr::ZERO; 2u32.pow(n_vars as u32) as usize],
234        );
235        let virtual_poly = VirtualPolynomial::new_from_mle(&Arc::new(poly_mle), Fr::ONE);
236        sumcheck_poseidon_opt(virtual_poly);
237    }
238
239    fn sumcheck_poseidon_opt(virtual_poly: VirtualPolynomial<Fr>) {
240        let poseidon_config = poseidon_canonical_config::<Fr>();
241
242        // sum-check prove
243        let mut transcript_p: PoseidonSponge<Fr> = PoseidonSponge::<Fr>::new(&poseidon_config);
244        let sum_check =
245            IOPSumCheck::<Fr, PoseidonSponge<Fr>>::prove(&virtual_poly, &mut transcript_p).unwrap();
246
247        // sum-check verify
248        let claimed_sum = IOPSumCheck::<Fr, PoseidonSponge<Fr>>::extract_sum(&sum_check);
249        let mut transcript_v: PoseidonSponge<Fr> = PoseidonSponge::<Fr>::new(&poseidon_config);
250        let res_verify = IOPSumCheck::<Fr, PoseidonSponge<Fr>>::verify(
251            claimed_sum,
252            &sum_check,
253            &virtual_poly.aux_info,
254            &mut transcript_v,
255        );
256
257        assert!(res_verify.is_ok());
258    }
259}