ark_linear_sumcheck/ml_sumcheck/
mod.rs

1//! Sumcheck Protocol for multilinear extension
2
3use crate::ml_sumcheck::data_structures::{ListOfProductsOfPolynomials, PolynomialInfo};
4use crate::ml_sumcheck::protocol::prover::{ProverMsg, ProverState};
5use crate::ml_sumcheck::protocol::verifier::SubClaim;
6use crate::ml_sumcheck::protocol::IPForMLSumcheck;
7use crate::rng::{Blake2s512Rng, FeedableRNG};
8use ark_ff::Field;
9use ark_std::marker::PhantomData;
10use ark_std::vec::Vec;
11
12pub mod protocol;
13
14pub mod data_structures;
15#[cfg(test)]
16mod test;
17
18/// Sumcheck for products of multilinear polynomial
19pub struct MLSumcheck<F: Field>(#[doc(hidden)] PhantomData<F>);
20
21/// proof generated by prover
22pub type Proof<F> = Vec<ProverMsg<F>>;
23
24impl<F: Field> MLSumcheck<F> {
25    /// extract sum from the proof
26    pub fn extract_sum(proof: &Proof<F>) -> F {
27        proof[0].evaluations[0] + proof[0].evaluations[1]
28    }
29
30    /// generate proof of the sum of polynomial over {0,1}^`num_vars`
31    ///
32    /// The polynomial is represented by a list of products of polynomials along with its coefficient that is meant to be added together.
33    ///
34    /// This data structure of the polynomial is a list of list of `(coefficient, DenseMultilinearExtension)`.
35    /// * Number of products n = `polynomial.products.len()`,
36    /// * Number of multiplicands of ith product m_i = `polynomial.products[i].1.len()`,
37    /// * Coefficient of ith product c_i = `polynomial.products[i].0`
38    ///
39    /// The resulting polynomial is
40    ///
41    /// $$\sum_{i=0}^{n}C_i\cdot\prod_{j=0}^{m_i}P_{ij}$$
42    pub fn prove(polynomial: &ListOfProductsOfPolynomials<F>) -> Result<Proof<F>, crate::Error> {
43        let mut fs_rng = Blake2s512Rng::setup();
44        Self::prove_as_subprotocol(&mut fs_rng, polynomial).map(|r| r.0)
45    }
46
47    /// This function does the same thing as `prove`, but it uses a `FeedableRNG` as the transcript/to generate the
48    /// verifier challenges. Additionally, it returns the prover's state in addition to the proof.
49    /// Both of these allow this sumcheck to be better used as a part of a larger protocol.
50    pub fn prove_as_subprotocol(
51        fs_rng: &mut impl FeedableRNG<Error = crate::Error>,
52        polynomial: &ListOfProductsOfPolynomials<F>,
53    ) -> Result<(Proof<F>, ProverState<F>), crate::Error> {
54        fs_rng.feed(&polynomial.info())?;
55
56        let mut prover_state = IPForMLSumcheck::prover_init(polynomial);
57        let mut verifier_msg = None;
58        let mut prover_msgs = Vec::with_capacity(polynomial.num_variables);
59        for _ in 0..polynomial.num_variables {
60            let prover_msg = IPForMLSumcheck::prove_round(&mut prover_state, &verifier_msg);
61            fs_rng.feed(&prover_msg)?;
62            prover_msgs.push(prover_msg);
63            verifier_msg = Some(IPForMLSumcheck::sample_round(fs_rng));
64        }
65
66        Ok((prover_msgs, prover_state))
67    }
68
69    /// verify the claimed sum using the proof
70    pub fn verify(
71        polynomial_info: &PolynomialInfo,
72        claimed_sum: F,
73        proof: &Proof<F>,
74    ) -> Result<SubClaim<F>, crate::Error> {
75        let mut fs_rng = Blake2s512Rng::setup();
76        Self::verify_as_subprotocol(&mut fs_rng, polynomial_info, claimed_sum, proof)
77    }
78
79    /// This function does the same thing as `prove`, but it uses a `FeedableRNG` as the transcript/to generate the
80    /// verifier challenges. This allows this sumcheck to be used as a part of a larger protocol.
81    pub fn verify_as_subprotocol(
82        fs_rng: &mut impl FeedableRNG<Error = crate::Error>,
83        polynomial_info: &PolynomialInfo,
84        claimed_sum: F,
85        proof: &Proof<F>,
86    ) -> Result<SubClaim<F>, crate::Error> {
87        fs_rng.feed(polynomial_info)?;
88        let mut verifier_state = IPForMLSumcheck::verifier_init(polynomial_info);
89        for i in 0..polynomial_info.num_variables {
90            let prover_msg = proof.get(i).expect("proof is incomplete");
91            fs_rng.feed(prover_msg)?;
92            let _verifier_msg =
93                IPForMLSumcheck::verify_round((*prover_msg).clone(), &mut verifier_state, fs_rng);
94        }
95
96        IPForMLSumcheck::check_and_generate_subclaim(verifier_state, claimed_sum)
97    }
98}
ark_linear_sumcheck/ml_sumcheck/mod.rs

ark_linear_sumcheck/ml_sumcheck/
mod.rs
