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