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 /// h^randomness: h^t1, h^t2, ..., **h^{t_nv}**
22 pub h_mask: Vec<E::G2Affine>,
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 /// generator for G1
34 pub g: E::G1Affine,
35 /// generator for G2
36 pub h: E::G2Affine,
37}
38
39/// Verifier Parameters
40#[derive(CanonicalSerialize, CanonicalDeserialize, Clone, Debug)]
41pub struct VerifierParam<E: PairingEngine> {
42 /// number of variables
43 pub num_vars: usize,
44
45 /// generator of G1
46 pub g: E::G1Affine,
47
48 /// generator of G2
49 pub h: E::G2Affine,
50
51 /// h^randomness: h^t1, h^t2, ..., **h^{t_nv}**
52 pub h_mask: Vec<E::G2Affine>,
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 h_mask: self.h_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_g: self.prover_param.powers_of_g[to_reduce..].to_vec(),
89 g: self.prover_param.g,
90 h: self.prover_param.h,
91 num_vars: supported_num_vars,
92 };
93 let vk = VerifierParam {
94 num_vars: supported_num_vars,
95 g: self.prover_param.g,
96 h: self.prover_param.h,
97 h_mask: self.h_mask[to_reduce..].to_vec(),
98 };
99 Ok((ck, vk))
100 }
101
102 /// Build SRS for testing.
103 /// WARNING: THIS FUNCTION IS FOR TESTING PURPOSE ONLY.
104 /// THE OUTPUT SRS SHOULD NOT BE USED IN PRODUCTION.
105 pub fn gen_srs_for_testing<R: RngCore>(
106 rng: &mut R,
107 num_vars: usize,
108 ) -> Result<Self, PCSErrors> {
109 if num_vars == 0 {
110 return Err(PCSErrors::InvalidParameters(
111 "constant polynomial not supported".to_string(),
112 ));
113 }
114
115 let total_timer = start_timer!(|| "SRS generation");
116
117 let pp_generation_timer = start_timer!(|| "Prover Param generation");
118
119 let g = E::G1Projective::rand(rng);
120 let h = E::G2Projective::rand(rng);
121
122 let mut powers_of_g = Vec::new();
123
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
155 let pp_g = E::G1Projective::batch_normalization_into_affine(
156 &FixedBaseMSM::multi_scalar_mul(scalar_bits, window_size, &g_table, &pp_powers),
157 );
158
159 let mut start = 0;
160 for i in 0..num_vars {
161 let size = 1 << (num_vars - i);
162 let pp_k_g = Evaluations {
163 evals: pp_g[start..(start + size)].to_vec(),
164 };
165 powers_of_g.push(pp_k_g);
166 start += size;
167 }
168
169 let pp = ProverParam {
170 num_vars,
171 g: g.into_affine(),
172 h: h.into_affine(),
173 powers_of_g,
174 };
175
176 end_timer!(pp_generation_timer);
177
178 let vp_generation_timer = start_timer!(|| "VP generation");
179 let h_mask = {
180 let window_size = FixedBaseMSM::get_mul_window_size(num_vars);
181 let h_table = FixedBaseMSM::get_window_table(scalar_bits, window_size, h);
182 E::G2Projective::batch_normalization_into_affine(&FixedBaseMSM::multi_scalar_mul(
183 scalar_bits,
184 window_size,
185 &h_table,
186 &t,
187 ))
188 };
189 end_timer!(vp_generation_timer);
190 end_timer!(total_timer);
191 Ok(Self {
192 prover_param: pp,
193 h_mask,
194 })
195 }
196}
197
198/// fix first `pad` variables of `poly` represented in evaluation form to zero
199fn remove_dummy_variable<F: Field>(poly: &[F], pad: usize) -> Result<Vec<F>, PCSErrors> {
200 if pad == 0 {
201 return Ok(poly.to_vec());
202 }
203 if !poly.len().is_power_of_two() {
204 return Err(PCSErrors::InvalidParameters(
205 "Size of polynomial should be power of two.".to_string(),
206 ));
207 }
208 let nv = ark_std::log2(poly.len()) as usize - pad;
209
210 Ok((0..(1 << nv)).map(|x| poly[x << pad]).collect())
211}
212
213/// Generate eq(t,x), a product of multilinear polynomials with fixed t.
214/// eq(a,b) is takes extensions of a,b in {0,1}^num_vars such that if a and b in
215/// {0,1}^num_vars are equal then this polynomial evaluates to 1.
216fn eq_extension<F: PrimeField>(t: &[F]) -> Vec<DenseMultilinearExtension<F>> {
217 let start = start_timer!(|| "eq extension");
218
219 let dim = t.len();
220 let mut result = Vec::new();
221 for (i, &ti) in t.iter().enumerate().take(dim) {
222 let mut poly = Vec::with_capacity(1 << dim);
223 for x in 0..(1 << dim) {
224 let xi = if x >> i & 1 == 1 { F::one() } else { F::zero() };
225 let ti_xi = ti * xi;
226 poly.push(ti_xi + ti_xi - xi - ti + F::one());
227 }
228 result.push(DenseMultilinearExtension::from_evaluations_vec(dim, poly));
229 }
230
231 end_timer!(start);
232 result
233}
234
235#[cfg(test)]
236mod tests {
237 use super::*;
238 use ark_bls12_381::Bls12_381;
239 use ark_std::test_rng;
240 type E = Bls12_381;
241
242 #[test]
243 fn test_srs_gen() -> Result<(), PCSErrors> {
244 let mut rng = test_rng();
245 for nv in 4..10 {
246 let _ = UniversalParams::<E>::gen_srs_for_testing(&mut rng, nv)?;
247 }
248
249 Ok(())
250 }
251}