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::pcs::{
  9    multilinear_kzg::util::eq_extension, prelude::PCSError, StructuredReferenceString,
 10};
 11use ark_ec::{msm::FixedBaseMSM, AffineCurve, PairingEngine, ProjectiveCurve};
 12use ark_ff::{Field, PrimeField};
 13use ark_poly::DenseMultilinearExtension;
 14use ark_serialize::{CanonicalDeserialize, CanonicalSerialize, Read, SerializationError, Write};
 15use ark_std::{
 16    collections::LinkedList,
 17    end_timer, format,
 18    rand::{CryptoRng, RngCore},
 19    start_timer,
 20    string::ToString,
 21    vec::Vec,
 22    UniformRand,
 23};
 24use core::iter::FromIterator;
 25
 26/// Evaluations over {0,1}^n for G1 or G2
 27#[derive(CanonicalSerialize, CanonicalDeserialize, Clone, Debug)]
 28pub struct Evaluations<C: AffineCurve> {
 29    /// The evaluations.
 30    pub evals: Vec<C>,
 31}
 32
 33/// Universal Parameter
 34#[derive(CanonicalSerialize, CanonicalDeserialize, Clone, Debug)]
 35pub struct MultilinearUniversalParams<E: PairingEngine> {
 36    /// prover parameters
 37    pub prover_param: MultilinearProverParam<E>,
 38    /// h^randomness: h^t1, h^t2, ..., **h^{t_nv}**
 39    pub h_mask: Vec<E::G2Affine>,
 40}
 41
 42/// Prover Parameters
 43#[derive(CanonicalSerialize, CanonicalDeserialize, Clone, Debug)]
 44pub struct MultilinearProverParam<E: PairingEngine> {
 45    /// number of variables
 46    pub num_vars: usize,
 47    /// `pp_{0}`, `pp_{1}`, ...,pp_{nu_vars} defined
 48    /// by XZZPD19 where pp_{nv-0}=g and
 49    /// pp_{nv-i}=g^{eq((t_1,..t_i),(X_1,..X_i))}
 50    pub powers_of_g: Vec<Evaluations<E::G1Affine>>,
 51    /// generator for G1
 52    pub g: E::G1Affine,
 53    /// generator for G2
 54    pub h: E::G2Affine,
 55}
 56
 57/// Verifier Parameters
 58#[derive(CanonicalSerialize, CanonicalDeserialize, Clone, Debug)]
 59pub struct MultilinearVerifierParam<E: PairingEngine> {
 60    /// number of variables
 61    pub num_vars: usize,
 62    /// generator of G1
 63    pub g: E::G1Affine,
 64    /// generator of G2
 65    pub h: E::G2Affine,
 66    /// h^randomness: h^t1, h^t2, ..., **h^{t_nv}**
 67    pub h_mask: Vec<E::G2Affine>,
 68}
 69
 70impl<E: PairingEngine> StructuredReferenceString<E> for MultilinearUniversalParams<E> {
 71    type ProverParam = MultilinearProverParam<E>;
 72    type VerifierParam = MultilinearVerifierParam<E>;
 73
 74    /// Extract the prover parameters from the public parameters.
 75    fn extract_prover_param(&self, supported_num_vars: usize) -> Self::ProverParam {
 76        let to_reduce = self.prover_param.num_vars - supported_num_vars;
 77
 78        Self::ProverParam {
 79            powers_of_g: self.prover_param.powers_of_g[to_reduce..].to_vec(),
 80            g: self.prover_param.g,
 81            h: self.prover_param.h,
 82            num_vars: supported_num_vars,
 83        }
 84    }
 85
 86    /// Extract the verifier parameters from the public parameters.
 87    fn extract_verifier_param(&self, supported_num_vars: usize) -> Self::VerifierParam {
 88        let to_reduce = self.prover_param.num_vars - supported_num_vars;
 89        Self::VerifierParam {
 90            num_vars: supported_num_vars,
 91            g: self.prover_param.g,
 92            h: self.prover_param.h,
 93            h_mask: self.h_mask[to_reduce..].to_vec(),
 94        }
 95    }
 96
 97    /// Trim the universal parameters to specialize the public parameters
 98    /// for multilinear polynomials to the given `supported_num_vars`, and
 99    /// returns committer key and verifier key. `supported_num_vars` should
100    /// be in range `1..=params.num_vars`
101    fn trim(
102        &self,
103        supported_num_vars: usize,
104    ) -> Result<(Self::ProverParam, Self::VerifierParam), PCSError> {
105        if supported_num_vars > self.prover_param.num_vars {
106            return Err(PCSError::InvalidParameters(format!(
107                "SRS does not support target number of vars {}",
108                supported_num_vars
109            )));
110        }
111
112        let to_reduce = self.prover_param.num_vars - supported_num_vars;
113        let ck = Self::ProverParam {
114            powers_of_g: self.prover_param.powers_of_g[to_reduce..].to_vec(),
115            g: self.prover_param.g,
116            h: self.prover_param.h,
117            num_vars: supported_num_vars,
118        };
119        let vk = Self::VerifierParam {
120            num_vars: supported_num_vars,
121            g: self.prover_param.g,
122            h: self.prover_param.h,
123            h_mask: self.h_mask[to_reduce..].to_vec(),
124        };
125        Ok((ck, vk))
126    }
127
128    /// Build SRS for testing.
129    /// WARNING: THIS FUNCTION IS FOR TESTING PURPOSE ONLY.
130    /// THE OUTPUT SRS SHOULD NOT BE USED IN PRODUCTION.
131    fn gen_srs_for_testing<R: RngCore + CryptoRng>(
132        rng: &mut R,
133        num_vars: usize,
134    ) -> Result<Self, PCSError> {
135        if num_vars == 0 {
136            return Err(PCSError::InvalidParameters(
137                "constant polynomial not supported".to_string(),
138            ));
139        }
140
141        let total_timer = start_timer!(|| "SRS generation");
142
143        let pp_generation_timer = start_timer!(|| "Prover Param generation");
144
145        let g = E::G1Projective::rand(rng);
146        let h = E::G2Projective::rand(rng);
147
148        let mut powers_of_g = Vec::new();
149
150        let t: Vec<_> = (0..num_vars).map(|_| E::Fr::rand(rng)).collect();
151        let scalar_bits = E::Fr::size_in_bits();
152
153        let mut eq: LinkedList<DenseMultilinearExtension<E::Fr>> =
154            LinkedList::from_iter(eq_extension(&t).into_iter());
155        let mut eq_arr = LinkedList::new();
156        let mut base = eq.pop_back().unwrap().evaluations;
157
158        for i in (0..num_vars).rev() {
159            eq_arr.push_front(remove_dummy_variable(&base, i)?);
160            if i != 0 {
161                let mul = eq.pop_back().unwrap().evaluations;
162                base = base
163                    .into_iter()
164                    .zip(mul.into_iter())
165                    .map(|(a, b)| a * b)
166                    .collect();
167            }
168        }
169
170        let mut pp_powers = Vec::new();
171        let mut total_scalars = 0;
172        for i in 0..num_vars {
173            let eq = eq_arr.pop_front().unwrap();
174            let pp_k_powers = (0..(1 << (num_vars - i))).map(|x| eq[x]);
175            pp_powers.extend(pp_k_powers);
176            total_scalars += 1 << (num_vars - i);
177        }
178        let window_size = FixedBaseMSM::get_mul_window_size(total_scalars);
179        let g_table = FixedBaseMSM::get_window_table(scalar_bits, window_size, g);
180
181        let pp_g = E::G1Projective::batch_normalization_into_affine(
182            &FixedBaseMSM::multi_scalar_mul(scalar_bits, window_size, &g_table, &pp_powers),
183        );
184
185        let mut start = 0;
186        for i in 0..num_vars {
187            let size = 1 << (num_vars - i);
188            let pp_k_g = Evaluations {
189                evals: pp_g[start..(start + size)].to_vec(),
190            };
191            powers_of_g.push(pp_k_g);
192            start += size;
193        }
194        let gg = Evaluations {
195            evals: [g.into_affine()].to_vec(),
196        };
197        powers_of_g.push(gg);
198
199        let pp = Self::ProverParam {
200            num_vars,
201            g: g.into_affine(),
202            h: h.into_affine(),
203            powers_of_g,
204        };
205
206        end_timer!(pp_generation_timer);
207
208        let vp_generation_timer = start_timer!(|| "VP generation");
209        let h_mask = {
210            let window_size = FixedBaseMSM::get_mul_window_size(num_vars);
211            let h_table = FixedBaseMSM::get_window_table(scalar_bits, window_size, h);
212            E::G2Projective::batch_normalization_into_affine(&FixedBaseMSM::multi_scalar_mul(
213                scalar_bits,
214                window_size,
215                &h_table,
216                &t,
217            ))
218        };
219        end_timer!(vp_generation_timer);
220        end_timer!(total_timer);
221        Ok(Self {
222            prover_param: pp,
223            h_mask,
224        })
225    }
226}
227
228/// fix first `pad` variables of `poly` represented in evaluation form to zero
229fn remove_dummy_variable<F: Field>(poly: &[F], pad: usize) -> Result<Vec<F>, PCSError> {
230    if pad == 0 {
231        return Ok(poly.to_vec());
232    }
233    if !poly.len().is_power_of_two() {
234        return Err(PCSError::InvalidParameters(
235            "Size of polynomial should be power of two.".to_string(),
236        ));
237    }
238    let nv = ark_std::log2(poly.len()) as usize - pad;
239    Ok((0..(1 << nv)).map(|x| poly[x << pad]).collect())
240}
241
242#[cfg(test)]
243mod tests {
244    use super::*;
245    use ark_bls12_381::Bls12_381;
246    use ark_std::test_rng;
247    type E = Bls12_381;
248
249    #[test]
250    fn test_srs_gen() -> Result<(), PCSError> {
251        let mut rng = test_rng();
252        for nv in 4..10 {
253            let params = MultilinearUniversalParams::<E>::gen_srs_for_testing(&mut rng, nv)?;
254            assert_eq!(
255                params.prover_param.g,
256                params.prover_param.powers_of_g[0].evals[0]
257            );
258        }
259
260        Ok(())
261    }
262}