hyperplonk/pcs/src/multilinear_kzg/srs.rs
pcs/src/multilinear_kzg/srs.rsRaw
1// Copyright (c) 2022 Espresso Systems (espressosys.com)
2// This file is part of the Jellyfish library.
3
4// You should have received a copy of the MIT License
5// along with the Jellyfish library. If not, see <https://mit-license.org/>.
6
7//! Implementing Structured Reference Strings for multilinear polynomial KZG
8use crate::{prelude::PCSError, StructuredReferenceString};
9use ark_ec::{msm::FixedBaseMSM, AffineCurve, PairingEngine, ProjectiveCurve};
10use ark_ff::{Field, PrimeField};
11use ark_poly::DenseMultilinearExtension;
12use ark_serialize::{CanonicalDeserialize, CanonicalSerialize, Read, SerializationError, Write};
13use ark_std::{
14 collections::LinkedList,
15 end_timer, format,
16 rand::{CryptoRng, RngCore},
17 start_timer,
18 string::ToString,
19 vec::Vec,
20 UniformRand,
21};
22use core::iter::FromIterator;
23
24/// Evaluations over {0,1}^n for G1 or G2
25#[derive(CanonicalSerialize, CanonicalDeserialize, Clone, Debug)]
26pub struct Evaluations<C: AffineCurve> {
27 /// The evaluations.
28 pub evals: Vec<C>,
29}
30
31/// Universal Parameter
32#[derive(CanonicalSerialize, CanonicalDeserialize, Clone, Debug)]
33pub struct MultilinearUniversalParams<E: PairingEngine> {
34 /// prover parameters
35 pub prover_param: MultilinearProverParam<E>,
36 /// h^randomness: h^t1, h^t2, ..., **h^{t_nv}**
37 pub h_mask: Vec<E::G2Affine>,
38}
39
40/// Prover Parameters
41#[derive(CanonicalSerialize, CanonicalDeserialize, Clone, Debug)]
42pub struct MultilinearProverParam<E: PairingEngine> {
43 /// number of variables
44 pub num_vars: usize,
45 /// `pp_{num_vars}`, `pp_{num_vars - 1}`, `pp_{num_vars - 2}`, ..., defined
46 /// by XZZPD19
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: PairingEngine> {
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: PairingEngine> 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: RngCore + CryptoRng>(
129 rng: &mut R,
130 num_vars: usize,
131 ) -> Result<Self, PCSError> {
132 if num_vars == 0 {
133 return Err(PCSError::InvalidParameters(
134 "constant polynomial not supported".to_string(),
135 ));
136 }
137
138 let total_timer = start_timer!(|| "SRS generation");
139
140 let pp_generation_timer = start_timer!(|| "Prover Param generation");
141
142 let g = E::G1Projective::rand(rng);
143 let h = E::G2Projective::rand(rng);
144
145 let mut powers_of_g = Vec::new();
146
147 let t: Vec<_> = (0..num_vars).map(|_| E::Fr::rand(rng)).collect();
148 let scalar_bits = E::Fr::size_in_bits();
149
150 let mut eq: LinkedList<DenseMultilinearExtension<E::Fr>> =
151 LinkedList::from_iter(eq_extension(&t).into_iter());
152 let mut eq_arr = LinkedList::new();
153 let mut base = eq.pop_back().unwrap().evaluations;
154
155 for i in (0..num_vars).rev() {
156 eq_arr.push_front(remove_dummy_variable(&base, i)?);
157 if i != 0 {
158 let mul = eq.pop_back().unwrap().evaluations;
159 base = base
160 .into_iter()
161 .zip(mul.into_iter())
162 .map(|(a, b)| a * b)
163 .collect();
164 }
165 }
166
167 let mut pp_powers = Vec::new();
168 let mut total_scalars = 0;
169 for i in 0..num_vars {
170 let eq = eq_arr.pop_front().unwrap();
171 let pp_k_powers = (0..(1 << (num_vars - i))).map(|x| eq[x]);
172 pp_powers.extend(pp_k_powers);
173 total_scalars += 1 << (num_vars - i);
174 }
175 let window_size = FixedBaseMSM::get_mul_window_size(total_scalars);
176 let g_table = FixedBaseMSM::get_window_table(scalar_bits, window_size, g);
177
178 let pp_g = E::G1Projective::batch_normalization_into_affine(
179 &FixedBaseMSM::multi_scalar_mul(scalar_bits, window_size, &g_table, &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 powers_of_g.push(pp_k_g);
189 start += size;
190 }
191
192 let pp = Self::ProverParam {
193 num_vars,
194 g: g.into_affine(),
195 h: h.into_affine(),
196 powers_of_g,
197 };
198
199 end_timer!(pp_generation_timer);
200
201 let vp_generation_timer = start_timer!(|| "VP generation");
202 let h_mask = {
203 let window_size = FixedBaseMSM::get_mul_window_size(num_vars);
204 let h_table = FixedBaseMSM::get_window_table(scalar_bits, window_size, h);
205 E::G2Projective::batch_normalization_into_affine(&FixedBaseMSM::multi_scalar_mul(
206 scalar_bits,
207 window_size,
208 &h_table,
209 &t,
210 ))
211 };
212 end_timer!(vp_generation_timer);
213 end_timer!(total_timer);
214 Ok(Self {
215 prover_param: pp,
216 h_mask,
217 })
218 }
219}
220
221/// fix first `pad` variables of `poly` represented in evaluation form to zero
222fn remove_dummy_variable<F: Field>(poly: &[F], pad: usize) -> Result<Vec<F>, PCSError> {
223 if pad == 0 {
224 return Ok(poly.to_vec());
225 }
226 if !poly.len().is_power_of_two() {
227 return Err(PCSError::InvalidParameters(
228 "Size of polynomial should be power of two.".to_string(),
229 ));
230 }
231 let nv = ark_std::log2(poly.len()) as usize - pad;
232 Ok((0..(1 << nv)).map(|x| poly[x << pad]).collect())
233}
234
235/// Generate eq(t,x), a product of multilinear polynomials with fixed t.
236/// eq(a,b) is takes extensions of a,b in {0,1}^num_vars such that if a and b in
237/// {0,1}^num_vars are equal then this polynomial evaluates to 1.
238fn eq_extension<F: PrimeField>(t: &[F]) -> Vec<DenseMultilinearExtension<F>> {
239 let start = start_timer!(|| "eq extension");
240
241 let dim = t.len();
242 let mut result = Vec::new();
243 for (i, &ti) in t.iter().enumerate().take(dim) {
244 let mut poly = Vec::with_capacity(1 << dim);
245 for x in 0..(1 << dim) {
246 let xi = if x >> i & 1 == 1 { F::one() } else { F::zero() };
247 let ti_xi = ti * xi;
248 poly.push(ti_xi + ti_xi - xi - ti + F::one());
249 }
250 result.push(DenseMultilinearExtension::from_evaluations_vec(dim, poly));
251 }
252
253 end_timer!(start);
254 result
255}
256
257#[cfg(test)]
258mod tests {
259 use super::*;
260 use ark_bls12_381::Bls12_381;
261 use ark_std::test_rng;
262 type E = Bls12_381;
263
264 #[test]
265 fn test_srs_gen() -> Result<(), PCSError> {
266 let mut rng = test_rng();
267 for nv in 4..10 {
268 let _ = MultilinearUniversalParams::<E>::gen_srs_for_testing(&mut rng, nv)?;
269 }
270
271 Ok(())
272 }
273}