zinc_piop/
random_field_sumcheck.rs

1//! Sumcheck protocol that operates over a random field.
2
3#[cfg(feature = "parallel")]
4use rayon::prelude::*;
5use std::marker::PhantomData;
6
7use crypto_primitives::{
8    BaseFieldConfig, ProjectPrimitiveIntegersWithConfig, SetConfig, SetElement,
9};
10use thiserror::Error;
11use zinc_poly::mle::{DenseMultilinearExtension, dense::project_coeffs};
12use zinc_transcript::traits::{ConstTranscribable, Transcript};
13use zinc_utils::{cfg_into_iter, projectable_to_field::ProjectableToField};
14
15use crate::sumcheck::{
16    MLSumcheck, SumCheckError, SumcheckProof, prover::ProverState, verifier::Subclaim,
17};
18
19pub struct RFSumcheck<C, R>(PhantomData<(C, R)>);
20
21#[derive(Clone, Debug, PartialEq)]
22pub struct RFSumcheckProof<F, R>(pub SumcheckProof<F>, PhantomData<R>);
23
24impl<F, R> RFSumcheckProof<F, R> {
25    pub fn new(inner: SumcheckProof<F>) -> Self {
26        Self(inner, Default::default())
27    }
28}
29
30pub struct RFProverState<C: SetConfig, R>(pub ProverState<C>, PhantomData<R>);
31
32impl<C: SetConfig, R> RFProverState<C, R> {
33    pub fn new(sumcheck_prover_state: ProverState<C>) -> Self {
34        Self(sumcheck_prover_state, Default::default())
35    }
36}
37
38impl<C, R> RFSumcheck<C, R>
39where
40    C: BaseFieldConfig + ProjectPrimitiveIntegersWithConfig,
41    C::Integer: ConstTranscribable,
42    R: SetElement + ProjectableToField<C>,
43{
44    /// Random field sumcheck prover.
45    /// Samples a random field element, projects the input MLEs
46    /// and performs the sumcheck proving algorithm.
47    ///
48    /// # Arguments
49    ///
50    /// * `transcript`: A mutable reference to a Fiat-Shamir `Transcript`.
51    /// * `mles`: A `Vec` of dense multilinear extension over the input semiring
52    ///   `R`. These will be projected by the prover.
53    /// * `mles_f`: A `Vec` of dense multilinear extension over the random
54    ///   field. E.g. `eq_r` can go into this argument. These will not be
55    ///   projected by the prover.
56    /// * `nvars`: The number of variables over which the `mles` are defined.
57    ///   This must be consistent across all `mles`.
58    /// * `degree`: The maximum combined degree of the `mles` under the
59    ///   `comb_fn`.
60    /// * `comb_fn`: A closure that defines the combination function $G(\alpha,
61    ///   \text{mles}(x))$. It takes the projecting element $\alpha$ the prover
62    ///   has sampled and a slice of field elements (the evaluations of the
63    ///   `mles` at a point $x$) and returns a single field element. The element
64    ///   $\alpha$ might be used to project some parts of the sumcheck
65    ///   polynomial, e.g. if a constraint systems requires projecting too.
66    /// * `config`: The configuration for the underlying field used in the
67    ///   protocol. The protocol does not sample the random prime and assumes it
68    ///   comes in this argument.
69    pub fn prove_as_subprotocol(
70        transcript: &mut impl Transcript,
71        mles: Vec<DenseMultilinearExtension<R>>,
72        mles_f: Vec<DenseMultilinearExtension<C::Element>>,
73        nvars: usize,
74        degree: usize,
75        comb_fn: impl Fn(&C::Element, &[C::Element]) -> C::Element + Send + Sync,
76        field_cfg: &C,
77    ) -> (RFSumcheckProof<C::Element, R>, RFProverState<C, R>) {
78        let projecting_element: C::Element = transcript.get_field_challenge(field_cfg);
79
80        let field_mles = cfg_into_iter!(mles)
81            .map(|mle| project_coeffs(field_cfg, mle, &projecting_element))
82            .chain(mles_f)
83            .collect();
84
85        let (proof, state) = MLSumcheck::prove_as_subprotocol(
86            transcript,
87            field_mles,
88            nvars,
89            degree,
90            |x| comb_fn(&projecting_element, x),
91            field_cfg,
92        );
93
94        (RFSumcheckProof::new(proof), RFProverState::new(state))
95    }
96
97    /// The verifier part of the random field sumcheck protocol.
98    /// # Arguments
99    ///
100    /// * `transcript`: A mutable reference to a Fiat-Shamir `Transcript`.
101    /// * `num_vars`: The number of variables over which the sum was originally
102    ///   computed.
103    /// * `degree`: The maximum combined degree of the underlying polynomial
104    ///   $G(x)$. This must match the degree used by the Prover.
105    /// * `claimed_sum`: The initial claimed value of the sum.
106    /// * `proof`: A reference to the `SumcheckProof<F>` generated by the
107    ///   Prover.
108    /// * `config`: The configuration for the underlying field used in the
109    ///   protocol.
110    pub fn verify_as_subprotocol(
111        transcript: &mut impl Transcript,
112        num_vars: usize,
113        degree: usize,
114        proof: &RFSumcheckProof<C::Element, R>,
115        field_cfg: C,
116    ) -> Result<Subclaim<C::Element>, RFSumcheckError<C::Element>> {
117        // Simulate getting the projecting element
118        // Verifier does not use that element as it verifies only over RC,
119        // but we keep it here for stability of FS sampling.
120        let _: C::Element = transcript.get_field_challenge(&field_cfg);
121
122        let subclaim =
123            MLSumcheck::verify_as_subprotocol(transcript, num_vars, degree, &proof.0, &field_cfg)?;
124
125        Ok(subclaim)
126    }
127}
128
129#[derive(Error, Debug)]
130pub enum RFSumcheckError<F> {
131    #[error("underlying sumcheck error: {0}")]
132    SumCheckError(SumCheckError<F>),
133}
134
135impl<F> From<SumCheckError<F>> for RFSumcheckError<F> {
136    fn from(value: SumCheckError<F>) -> Self {
137        Self::SumCheckError(value)
138    }
139}
140
141#[cfg(test)]
142mod tests {
143    use crypto_primitives::{
144        ProjectElementWithConfig, SemiringConfig, WithAssociatedInteger,
145        crypto_bigint_monty::MontyField,
146    };
147    use num_traits::Zero;
148    use rand::prelude::*;
149    use zinc_poly::{
150        mle::DenseMultilinearExtension, univariate::binary::BinaryPoly, utils::build_eq_x_r,
151    };
152    use zinc_primality::MillerRabin;
153    use zinc_transcript::{Blake3Transcript, traits::Transcript};
154
155    use crate::random_field_sumcheck::RFSumcheck;
156
157    const LIMBS: usize = 4;
158
159    type F = MontyField<LIMBS>;
160
161    #[test]
162    fn test_simple_product_random_field_sumcheck() {
163        let witness_size = 1 << 3;
164        let mut rng = rand::rng();
165        let a: Vec<u32> = (0..witness_size).map(|_| rng.random()).collect();
166        let b: Vec<u32> = (0..witness_size).map(|_| rng.random()).collect();
167        let c: Vec<u32> = (0..witness_size).map(|_| rng.random()).collect();
168
169        let nvars = zinc_utils::log2(witness_size) as usize;
170
171        let a: DenseMultilinearExtension<BinaryPoly<32>> =
172            DenseMultilinearExtension::from_evaluations_vec(
173                nvars,
174                a.into_iter().map(BinaryPoly::from).collect(),
175                BinaryPoly::zero(),
176            );
177
178        let b: DenseMultilinearExtension<BinaryPoly<32>> =
179            DenseMultilinearExtension::from_evaluations_vec(
180                nvars,
181                b.into_iter().map(BinaryPoly::from).collect(),
182                BinaryPoly::zero(),
183            );
184
185        let c: DenseMultilinearExtension<BinaryPoly<32>> =
186            DenseMultilinearExtension::from_evaluations_vec(
187                nvars,
188                c.into_iter().map(BinaryPoly::from).collect(),
189                BinaryPoly::zero(),
190            );
191
192        let mut transcript = Blake3Transcript::new();
193
194        let field_cfg: F = transcript
195            .get_random_field_cfg::<F, <F as WithAssociatedInteger>::Integer, MillerRabin>();
196
197        let eq_r = build_eq_x_r(&field_cfg, &vec![field_cfg.project(&2u32); nvars])
198            .expect("Failed to build eq_r");
199
200        let proof = (RFSumcheck::<F, _>::prove_as_subprotocol(
201            &mut transcript.clone(),
202            vec![a, b, c],
203            vec![eq_r],
204            nvars,
205            3,
206            |_x, vals| {
207                field_cfg.mul(
208                    &field_cfg.sub(&field_cfg.mul(&vals[0], &vals[1]), &vals[2]),
209                    &vals[3],
210                )
211            },
212            &field_cfg,
213        ))
214        .0;
215
216        assert!(
217            RFSumcheck::<F, _>::verify_as_subprotocol(
218                &mut transcript,
219                nvars,
220                3,
221                &proof,
222                field_cfg,
223            )
224            .is_ok()
225        )
226    }
227}
zinc_piop/random_field_sumcheck.rs

zinc_piop/
random_field_sumcheck.rs
