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