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