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