jf_pcs/multilinear_kzg/
srs.rs

1// Copyright (c) 2022 Espresso Systems (espressosys.com)
2// This file is part of the Jellyfish library.
3
4// You should have received a copy of the MIT License
5// along with the Jellyfish library. If not, see <https://mit-license.org/>.
6
7//! Implementing Structured Reference Strings for multilinear polynomial KZG
8use crate::{
9    prelude::PCSError,
10    univariate_kzg::srs::{
11        UnivariateProverParam, UnivariateUniversalParams, UnivariateVerifierParam,
12    },
13    StructuredReferenceString,
14};
15use ark_ec::{pairing::Pairing, AffineRepr};
16use ark_serialize::{CanonicalDeserialize, CanonicalSerialize};
17use ark_std::{format, vec::Vec};
18
19/// Evaluations over {0,1}^n for G1 or G2
20#[derive(CanonicalSerialize, CanonicalDeserialize, Clone, Debug)]
21pub struct Evaluations<C: AffineRepr> {
22    /// The evaluations.
23    pub evals: Vec<C>,
24}
25
26/// Universal Parameter
27#[derive(CanonicalSerialize, CanonicalDeserialize, Clone, Debug)]
28pub struct MultilinearUniversalParams<E: Pairing> {
29    /// prover parameters
30    pub prover_param: MultilinearProverParam<E>,
31    /// h^randomness: h^t1, h^t2, ..., **h^{t_nv}**
32    pub h_mask: Vec<E::G2Affine>,
33}
34
35/// Prover Config
36#[derive(CanonicalSerialize, CanonicalDeserialize, Clone, Debug)]
37pub struct MultilinearProverParam<E: Pairing> {
38    /// number of variables
39    pub num_vars: usize,
40    /// `pp_{0}`, `pp_{1}`, ...,pp_{nu_vars} defined
41    /// by XZZPD19 where pp_{nv-0}=g and
42    /// pp_{nv-i}=g^{eq((t_1,..t_i),(X_1,..X_i))}
43    pub powers_of_g: Vec<Evaluations<E::G1Affine>>,
44    /// generator for G1
45    pub g: E::G1Affine,
46    /// generator for G2
47    pub h: E::G2Affine,
48}
49
50/// Verifier Config
51#[derive(CanonicalSerialize, CanonicalDeserialize, Clone, Debug)]
52pub struct MultilinearVerifierParam<E: Pairing> {
53    /// number of variables
54    pub num_vars: usize,
55    /// generator of G1
56    pub g: E::G1Affine,
57    /// generator of G2
58    pub h: E::G2Affine,
59    /// h^randomness: h^t1, h^t2, ..., **h^{t_nv}**
60    pub h_mask: Vec<E::G2Affine>,
61}
62
63impl<E: Pairing> StructuredReferenceString for MultilinearUniversalParams<E> {
64    type ProverParam = MultilinearProverParam<E>;
65    type VerifierParam = MultilinearVerifierParam<E>;
66
67    /// Extract the prover parameters from the public parameters.
68    fn extract_prover_param(&self, supported_num_vars: usize) -> Self::ProverParam {
69        let to_reduce = self.prover_param.num_vars - supported_num_vars;
70
71        Self::ProverParam {
72            powers_of_g: self.prover_param.powers_of_g[to_reduce..].to_vec(),
73            g: self.prover_param.g,
74            h: self.prover_param.h,
75            num_vars: supported_num_vars,
76        }
77    }
78
79    /// Extract the verifier parameters from the public parameters.
80    fn extract_verifier_param(&self, supported_num_vars: usize) -> Self::VerifierParam {
81        let to_reduce = self.prover_param.num_vars - supported_num_vars;
82        Self::VerifierParam {
83            num_vars: supported_num_vars,
84            g: self.prover_param.g,
85            h: self.prover_param.h,
86            h_mask: self.h_mask[to_reduce..].to_vec(),
87        }
88    }
89
90    /// Trim the universal parameters to specialize the public parameters
91    /// for multilinear polynomials to the given `supported_num_vars`, and
92    /// returns committer key and verifier key. `supported_num_vars` should
93    /// be in range `1..=params.num_vars`
94    fn trim(
95        &self,
96        supported_num_vars: usize,
97    ) -> Result<(Self::ProverParam, Self::VerifierParam), PCSError> {
98        if supported_num_vars > self.prover_param.num_vars {
99            return Err(PCSError::InvalidParameters(format!(
100                "SRS does not support target number of vars {supported_num_vars}"
101            )));
102        }
103
104        let to_reduce = self.prover_param.num_vars - supported_num_vars;
105        let ck = Self::ProverParam {
106            powers_of_g: self.prover_param.powers_of_g[to_reduce..].to_vec(),
107            g: self.prover_param.g,
108            h: self.prover_param.h,
109            num_vars: supported_num_vars,
110        };
111        let vk = Self::VerifierParam {
112            num_vars: supported_num_vars,
113            g: self.prover_param.g,
114            h: self.prover_param.h,
115            h_mask: self.h_mask[to_reduce..].to_vec(),
116        };
117        Ok((ck, vk))
118    }
119
120    /// Naive implementation
121    fn trim_with_verifier_degree(
122        &self,
123        prover_supported_num_vars: usize,
124        _verifier_supported_num_vars: usize,
125    ) -> Result<(Self::ProverParam, Self::VerifierParam), PCSError> {
126        self.trim(prover_supported_num_vars)
127    }
128
129    #[cfg(any(test, feature = "test-srs"))]
130    fn gen_srs_for_testing<R>(rng: &mut R, num_vars: usize) -> Result<Self, PCSError>
131    where
132        R: ark_std::rand::RngCore + ark_std::rand::CryptoRng,
133    {
134        tests::gen_srs_for_testing(rng, num_vars)
135    }
136
137    /// Naive implementation
138    #[cfg(any(test, feature = "test-srs"))]
139    fn gen_srs_for_testing_with_verifier_degree<R>(
140        rng: &mut R,
141        prover_num_vars: usize,
142        _verifier_num_vars: usize,
143    ) -> Result<Self, PCSError>
144    where
145        R: ark_std::rand::RngCore + ark_std::rand::CryptoRng,
146    {
147        tests::gen_srs_for_testing(rng, prover_num_vars)
148    }
149}
150
151// Implement `trait StructuredReferenceString` for (ML_pp, Uni_pp) to be used in
152// MLE PCS.
153impl<E: Pairing> StructuredReferenceString
154    for (MultilinearUniversalParams<E>, UnivariateUniversalParams<E>)
155{
156    type ProverParam = (MultilinearProverParam<E>, UnivariateProverParam<E>);
157    type VerifierParam = (MultilinearVerifierParam<E>, UnivariateVerifierParam<E>);
158
159    fn trim(
160        &self,
161        supported_degree: usize,
162    ) -> Result<(Self::ProverParam, Self::VerifierParam), PCSError> {
163        let ml_pp = <MultilinearUniversalParams<E> as StructuredReferenceString>::trim(
164            &self.0,
165            supported_degree,
166        )?;
167        let uni_pp = <UnivariateUniversalParams<E> as StructuredReferenceString>::trim(
168            &self.1,
169            supported_degree,
170        )?;
171
172        Ok(((ml_pp.0, uni_pp.0), (ml_pp.1, uni_pp.1)))
173    }
174
175    /// Naive implementation
176    fn trim_with_verifier_degree(
177        &self,
178        prover_supported_num_vars: usize,
179        _verifier_supported_num_vars: usize,
180    ) -> Result<(Self::ProverParam, Self::VerifierParam), PCSError> {
181        self.trim(prover_supported_num_vars)
182    }
183
184    fn extract_prover_param(&self, supported_degree: usize) -> Self::ProverParam {
185        let ml_prover_param =
186            <MultilinearUniversalParams<E> as StructuredReferenceString>::extract_prover_param(
187                &self.0,
188                supported_degree,
189            );
190        let uni_prover_param =
191            <UnivariateUniversalParams<E> as StructuredReferenceString>::extract_prover_param(
192                &self.1,
193                supported_degree,
194            );
195
196        (ml_prover_param, uni_prover_param)
197    }
198
199    fn extract_verifier_param(&self, supported_degree: usize) -> Self::VerifierParam {
200        let ml_verifier_param =
201            <MultilinearUniversalParams<E> as StructuredReferenceString>::extract_verifier_param(
202                &self.0,
203                supported_degree,
204            );
205        let uni_verifier_param =
206            <UnivariateUniversalParams<E> as StructuredReferenceString>::extract_verifier_param(
207                &self.1,
208                supported_degree,
209            );
210
211        (ml_verifier_param, uni_verifier_param)
212    }
213
214    #[cfg(any(test, feature = "test-srs"))]
215    fn gen_srs_for_testing<R>(rng: &mut R, supported_degree: usize) -> Result<Self, PCSError>
216    where
217        R: ark_std::rand::RngCore + ark_std::rand::CryptoRng,
218    {
219        let ml_pp =
220            <MultilinearUniversalParams<E> as StructuredReferenceString>::gen_srs_for_testing(
221                rng,
222                supported_degree,
223            )?;
224        let uni_pp =
225            <UnivariateUniversalParams<E> as StructuredReferenceString>::gen_srs_for_testing(
226                rng,
227                supported_degree,
228            )?;
229        Ok((ml_pp, uni_pp))
230    }
231
232    /// Naive implementation
233    #[cfg(any(test, feature = "test-srs"))]
234    fn gen_srs_for_testing_with_verifier_degree<R>(
235        rng: &mut R,
236        prover_num_vars: usize,
237        _verifier_num_vars: usize,
238    ) -> Result<Self, PCSError>
239    where
240        R: ark_std::rand::RngCore + ark_std::rand::CryptoRng,
241    {
242        Self::gen_srs_for_testing(rng, prover_num_vars)
243    }
244}
245
246#[cfg(any(test, feature = "test-srs"))]
247mod tests {
248    use super::*;
249    use crate::multilinear_kzg::util::eq_eval;
250    use ark_ec::{scalar_mul::fixed_base::FixedBase, CurveGroup};
251    use ark_ff::{Field, PrimeField, Zero};
252    use ark_poly::DenseMultilinearExtension;
253    use ark_std::{
254        collections::LinkedList,
255        end_timer,
256        rand::{CryptoRng, RngCore},
257        start_timer,
258        string::ToString,
259        vec, UniformRand,
260    };
261
262    // fix first `pad` variables of `poly` represented in evaluation form to zero
263    fn remove_dummy_variable<F: Field>(poly: &[F], pad: usize) -> Result<Vec<F>, PCSError> {
264        if pad == 0 {
265            return Ok(poly.to_vec());
266        }
267        if !poly.len().is_power_of_two() {
268            return Err(PCSError::InvalidParameters(
269                "Size of polynomial should be power of two.".to_string(),
270            ));
271        }
272        let nv = ark_std::log2(poly.len()) as usize - pad;
273
274        Ok((0..(1 << nv)).map(|x| poly[x << pad]).collect())
275    }
276
277    // Generate eq(t,x), a product of multilinear polynomials with fixed t.
278    // eq(a,b) is takes extensions of a,b in {0,1}^num_vars such that if a and
279    // b in {0,1}^num_vars are equal then this polynomial evaluates to 1.
280    fn eq_extension<F: PrimeField>(t: &[F]) -> Vec<DenseMultilinearExtension<F>> {
281        let start = start_timer!(|| "eq extension");
282
283        let dim = t.len();
284        let mut result = Vec::new();
285        for (i, &ti) in t.iter().enumerate().take(dim) {
286            let mut poly = Vec::with_capacity(1 << dim);
287            for x in 0..(1 << dim) {
288                let xi = if x >> i & 1 == 1 { F::one() } else { F::zero() };
289                let ti_xi = ti * xi;
290                poly.push(ti_xi + ti_xi - xi - ti + F::one());
291            }
292            result.push(DenseMultilinearExtension::from_evaluations_vec(dim, poly));
293        }
294
295        end_timer!(start);
296        result
297    }
298
299    pub(crate) fn gen_srs_for_testing<E: Pairing, R: RngCore + CryptoRng>(
300        rng: &mut R,
301        num_vars: usize,
302    ) -> Result<MultilinearUniversalParams<E>, PCSError> {
303        if num_vars == 0 {
304            return Err(PCSError::InvalidParameters(
305                "constant polynomial not supported".to_string(),
306            ));
307        }
308
309        let total_timer = start_timer!(|| "SRS generation");
310
311        let pp_generation_timer = start_timer!(|| "Prover Param generation");
312
313        let g = E::G1::rand(rng);
314        let h = E::G2::rand(rng);
315
316        let mut powers_of_g = Vec::new();
317
318        let t: Vec<_> = (0..num_vars).map(|_| E::ScalarField::rand(rng)).collect();
319        let scalar_bits = E::ScalarField::MODULUS_BIT_SIZE as usize;
320
321        let mut eq: LinkedList<DenseMultilinearExtension<E::ScalarField>> =
322            LinkedList::from_iter(eq_extension(&t));
323        let mut eq_arr = LinkedList::new();
324        let mut base = eq.pop_back().unwrap().evaluations;
325
326        for i in (0..num_vars).rev() {
327            eq_arr.push_front(remove_dummy_variable(&base, i)?);
328            if i != 0 {
329                let mul = eq.pop_back().unwrap().evaluations;
330                base = base
331                    .into_iter()
332                    .zip(mul.into_iter())
333                    .map(|(a, b)| a * b)
334                    .collect();
335            }
336        }
337
338        let mut pp_powers = Vec::new();
339        let mut total_scalars = 0;
340        for i in 0..num_vars {
341            let eq = eq_arr.pop_front().unwrap();
342            let pp_k_powers = (0..(1 << (num_vars - i))).map(|x| eq[x]);
343            pp_powers.extend(pp_k_powers);
344            total_scalars += 1 << (num_vars - i);
345        }
346        let window_size = FixedBase::get_mul_window_size(total_scalars);
347        let g_table = FixedBase::get_window_table(scalar_bits, window_size, g);
348
349        let pp_g = E::G1::normalize_batch(&FixedBase::msm(
350            scalar_bits,
351            window_size,
352            &g_table,
353            &pp_powers,
354        ));
355
356        let mut start = 0;
357        for i in 0..num_vars {
358            let size = 1 << (num_vars - i);
359            let pp_k_g = Evaluations {
360                evals: pp_g[start..(start + size)].to_vec(),
361            };
362            // check correctness of pp_k_g
363            let t_eval_0 = eq_eval(&vec![E::ScalarField::zero(); num_vars - i], &t[i..num_vars])?;
364            assert_eq!((g * t_eval_0).into_affine(), pp_k_g.evals[0]);
365
366            powers_of_g.push(pp_k_g);
367            start += size;
368        }
369        let gg = Evaluations {
370            evals: [g.into_affine()].to_vec(),
371        };
372        powers_of_g.push(gg);
373
374        let pp = MultilinearProverParam {
375            num_vars,
376            g: g.into_affine(),
377            h: h.into_affine(),
378            powers_of_g,
379        };
380
381        end_timer!(pp_generation_timer);
382
383        let vp_generation_timer = start_timer!(|| "VP generation");
384        let h_mask = {
385            let window_size = FixedBase::get_mul_window_size(num_vars);
386            let h_table = FixedBase::get_window_table(scalar_bits, window_size, h);
387            E::G2::normalize_batch(&FixedBase::msm(scalar_bits, window_size, &h_table, &t))
388        };
389        end_timer!(vp_generation_timer);
390        end_timer!(total_timer);
391        Ok(MultilinearUniversalParams {
392            prover_param: pp,
393            h_mask,
394        })
395    }
396
397    #[test]
398    fn test_srs_gen() -> Result<(), PCSError> {
399        use ark_bls12_381::Bls12_381;
400        use jf_utils::test_rng;
401        type E = Bls12_381;
402
403        let mut rng = test_rng();
404        for nv in 4..10 {
405            let _ = MultilinearUniversalParams::<E>::gen_srs_for_testing(&mut rng, nv)?;
406        }
407
408        Ok(())
409    }
410}
jf_pcs/multilinear_kzg/srs.rs

jf_pcs/multilinear_kzg/
srs.rs
