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

zinc_piop/
random_field_sumcheck.rs
