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::utils::virtual_polynomial::{VPAuxInfo, VirtualPolynomial};
 13use ark_ff::PrimeField;
 14use ark_poly::DenseMultilinearExtension;
 15use ark_std::{end_timer, start_timer};
 16use std::{fmt::Debug, sync::Arc};
 17
 18use espresso_subroutines::poly_iop::{prelude::PolyIOPErrors, PolyIOP};
 19use espresso_transcript::IOPTranscript;
 20use structs::{IOPProof, IOPProverState, IOPVerifierState};
 21
 22mod prover;
 23pub mod structs;
 24pub mod verifier;
 25
 26/// Trait for doing sum check protocols.
 27pub trait SumCheck<F: PrimeField> {
 28    type VirtualPolynomial;
 29    type VPAuxInfo;
 30    type MultilinearExtension;
 31
 32    type SumCheckProof: Clone + Debug + Default + PartialEq;
 33    type Transcript;
 34    type SumCheckSubClaim: Clone + Debug + Default + PartialEq;
 35
 36    /// Extract sum from the proof
 37    fn extract_sum(proof: &Self::SumCheckProof) -> F;
 38
 39    /// Initialize the system with a transcript
 40    ///
 41    /// This function is optional -- in the case where a SumCheck is
 42    /// an building block for a more complex protocol, the transcript
 43    /// may be initialized by this complex protocol, and passed to the
 44    /// SumCheck prover/verifier.
 45    fn init_transcript() -> Self::Transcript;
 46
 47    /// Generate proof of the sum of polynomial over {0,1}^`num_vars`
 48    ///
 49    /// The polynomial is represented in the form of a VirtualPolynomial.
 50    fn prove(
 51        poly: &Self::VirtualPolynomial,
 52        transcript: &mut Self::Transcript,
 53    ) -> Result<Self::SumCheckProof, PolyIOPErrors>;
 54
 55    /// Verify the claimed sum using the proof
 56    fn verify(
 57        sum: F,
 58        proof: &Self::SumCheckProof,
 59        aux_info: &Self::VPAuxInfo,
 60        transcript: &mut Self::Transcript,
 61    ) -> Result<Self::SumCheckSubClaim, PolyIOPErrors>;
 62}
 63
 64/// Trait for sum check protocol prover side APIs.
 65pub trait SumCheckProver<F: PrimeField>
 66where
 67    Self: Sized,
 68{
 69    type VirtualPolynomial;
 70    type ProverMessage;
 71
 72    /// Initialize the prover state to argue for the sum of the input polynomial
 73    /// over {0,1}^`num_vars`.
 74    fn prover_init(polynomial: &Self::VirtualPolynomial) -> Result<Self, PolyIOPErrors>;
 75
 76    /// Receive message from verifier, generate prover message, and proceed to
 77    /// next round.
 78    ///
 79    /// Main algorithm used is from section 3.2 of [XZZPS19](https://eprint.iacr.org/2019/317.pdf#subsection.3.2).
 80    fn prove_round_and_update_state(
 81        &mut self,
 82        challenge: &Option<F>,
 83    ) -> Result<Self::ProverMessage, PolyIOPErrors>;
 84}
 85
 86/// Trait for sum check protocol verifier side APIs.
 87pub trait SumCheckVerifier<F: PrimeField> {
 88    type VPAuxInfo;
 89    type ProverMessage;
 90    type Challenge;
 91    type Transcript;
 92    type SumCheckSubClaim;
 93
 94    /// Initialize the verifier's state.
 95    fn verifier_init(index_info: &Self::VPAuxInfo) -> Self;
 96
 97    /// Run verifier for the current round, given a prover message.
 98    ///
 99    /// Note that `verify_round_and_update_state` only samples and stores
100    /// challenges; and update the verifier's state accordingly. The actual
101    /// verifications are deferred (in batch) to `check_and_generate_subclaim`
102    /// at the last step.
103    fn verify_round_and_update_state(
104        &mut self,
105        prover_msg: &Self::ProverMessage,
106        transcript: &mut Self::Transcript,
107    ) -> Result<Self::Challenge, PolyIOPErrors>;
108
109    /// This function verifies the deferred checks in the interactive version of
110    /// the protocol; and generate the subclaim. Returns an error if the
111    /// proof failed to verify.
112    ///
113    /// If the asserted sum is correct, then the multilinear polynomial
114    /// evaluated at `subclaim.point` will be `subclaim.expected_evaluation`.
115    /// Otherwise, it is highly unlikely that those two will be equal.
116    /// Larger field size guarantees smaller soundness error.
117    fn check_and_generate_subclaim(
118        &self,
119        asserted_sum: &F,
120    ) -> Result<Self::SumCheckSubClaim, PolyIOPErrors>;
121}
122
123/// A SumCheckSubClaim is a claim generated by the verifier at the end of
124/// verification when it is convinced.
125#[derive(Clone, Debug, Default, PartialEq, Eq)]
126pub struct SumCheckSubClaim<F: PrimeField> {
127    /// the multi-dimensional point that this multilinear extension is evaluated
128    /// to
129    pub point: Vec<F>,
130    /// the expected evaluation
131    pub expected_evaluation: F,
132}
133
134impl<F: PrimeField> SumCheck<F> for PolyIOP<F> {
135    type SumCheckProof = IOPProof<F>;
136    type VirtualPolynomial = VirtualPolynomial<F>;
137    type VPAuxInfo = VPAuxInfo<F>;
138    type MultilinearExtension = Arc<DenseMultilinearExtension<F>>;
139    type SumCheckSubClaim = SumCheckSubClaim<F>;
140    type Transcript = IOPTranscript<F>;
141
142    fn extract_sum(proof: &Self::SumCheckProof) -> F {
143        let start = start_timer!(|| "extract sum");
144        let res = proof.proofs[0].evaluations[0] + proof.proofs[0].evaluations[1];
145        end_timer!(start);
146        res
147    }
148
149    fn init_transcript() -> Self::Transcript {
150        let start = start_timer!(|| "init transcript");
151        let res = IOPTranscript::<F>::new(b"Initializing SumCheck transcript");
152        end_timer!(start);
153        res
154    }
155
156    fn prove(
157        poly: &Self::VirtualPolynomial,
158        transcript: &mut Self::Transcript,
159    ) -> Result<Self::SumCheckProof, PolyIOPErrors> {
160        let start = start_timer!(|| "sum check prove");
161
162        transcript.append_serializable_element(b"aux info", &poly.aux_info)?;
163
164        let mut prover_state = IOPProverState::prover_init(poly)?;
165        let mut challenge = None;
166        let mut prover_msgs = Vec::with_capacity(poly.aux_info.num_variables);
167        for _ in 0..poly.aux_info.num_variables {
168            let prover_msg =
169                IOPProverState::prove_round_and_update_state(&mut prover_state, &challenge)?;
170            transcript.append_serializable_element(b"prover msg", &prover_msg)?;
171            prover_msgs.push(prover_msg);
172            challenge = Some(transcript.get_and_append_challenge(b"Internal round")?);
173        }
174        // pushing the last challenge point to the state
175        if let Some(p) = challenge {
176            prover_state.challenges.push(p)
177        };
178
179        end_timer!(start);
180        Ok(IOPProof {
181            point: prover_state.challenges,
182            proofs: prover_msgs,
183        })
184    }
185
186    fn verify(
187        claimed_sum: F,
188        proof: &Self::SumCheckProof,
189        aux_info: &Self::VPAuxInfo,
190        transcript: &mut Self::Transcript,
191    ) -> Result<Self::SumCheckSubClaim, PolyIOPErrors> {
192        let start = start_timer!(|| "sum check verify");
193
194        transcript.append_serializable_element(b"aux info", aux_info)?;
195        let mut verifier_state = IOPVerifierState::verifier_init(aux_info);
196        for i in 0..aux_info.num_variables {
197            let prover_msg = proof.proofs.get(i).expect("proof is incomplete");
198            transcript.append_serializable_element(b"prover msg", prover_msg)?;
199            IOPVerifierState::verify_round_and_update_state(
200                &mut verifier_state,
201                prover_msg,
202                transcript,
203            )?;
204        }
205
206        let res = IOPVerifierState::check_and_generate_subclaim(&verifier_state, &claimed_sum);
207
208        end_timer!(start);
209        res
210    }
211}