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