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