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