hyperplonk/pcs/src/commit.rs
pcs/src/commit.rsRaw
1use ark_ec::{
2 msm::{FixedBaseMSM, VariableBaseMSM},
3 AffineCurve, PairingEngine, ProjectiveCurve,
4};
5use ark_ff::PrimeField;
6use ark_poly::MultilinearExtension;
7use ark_serialize::{CanonicalDeserialize, CanonicalSerialize, Read, SerializationError, Write};
8use ark_std::{end_timer, rand::RngCore, start_timer, vec::Vec, One, Zero};
9
10use crate::{
11 KZGMultilinearPC, MultilinearCommitmentScheme, PCSErrors, ProverParam, UniversalParams,
12 VerifierParam,
13};
14
15#[derive(CanonicalSerialize, CanonicalDeserialize, Clone, Debug)]
16/// commitment
17pub struct Commitment<E: PairingEngine> {
18 /// number of variables
19 pub nv: usize,
20 /// product of g as described by the vRAM paper
21 #[cfg(not(feature = "group-switched"))]
22 pub g_product: E::G1Affine,
23 #[cfg(feature = "group-switched")]
24 pub g_product: E::G2Affine,
25}
26
27#[derive(CanonicalSerialize, CanonicalDeserialize, Clone, Debug)]
28/// proof of opening
29pub struct Proof<E: PairingEngine> {
30 /// Evaluation of quotients
31 #[cfg(not(feature = "group-switched"))]
32 pub proofs: Vec<E::G2Affine>,
33 #[cfg(feature = "group-switched")]
34 pub proofs: Vec<E::G1Affine>,
35}
36
37impl<E: PairingEngine> MultilinearCommitmentScheme<E> for KZGMultilinearPC<E> {
38 type ProverParam = ProverParam<E>;
39 type VerifierParam = VerifierParam<E>;
40 type SRS = UniversalParams<E>;
41 type Commitment = Commitment<E>;
42 type Proof = Proof<E>;
43
44 /// Generate SRS from RNG.
45 /// WARNING: THIS FUNCTION IS FOR TESTING PURPOSE ONLY.
46 /// THE OUTPUT SRS SHOULD NOT BE USED IN PRODUCTION.
47 fn setup<R: RngCore>(rng: &mut R, num_vars: usize) -> Result<Self::SRS, PCSErrors> {
48 let setup_timer = start_timer!(|| format!("SRS setup for dim {}", num_vars));
49 let res = Self::SRS::gen_srs_for_testing(rng, num_vars);
50 end_timer!(setup_timer);
51 res
52 }
53
54 /// Generate a commitment for a polynomial.
55 ///
56 /// This function takes `2^num_vars` number of scalar multiplications over
57 /// G1.
58 fn commit(
59 prover_param: &Self::ProverParam,
60 poly: &impl MultilinearExtension<E::Fr>,
61 ) -> Result<Self::Commitment, PCSErrors> {
62 let commit_timer = start_timer!(|| "commit");
63
64 let nv = poly.num_vars();
65 let scalars: Vec<_> = poly
66 .to_evaluations()
67 .into_iter()
68 .map(|x| x.into_repr())
69 .collect();
70 let g_product = VariableBaseMSM::multi_scalar_mul(
71 &prover_param.powers_of_g[0].evals,
72 scalars.as_slice(),
73 )
74 .into_affine();
75
76 end_timer!(commit_timer);
77 Ok(Commitment { nv, g_product })
78 }
79
80 /// On input a polynomial `p` and a point `point`, outputs a proof for the
81 /// same. This function does not need to take the evaluation value as an
82 /// input.
83 ///
84 /// This function takes 2^{num_var +1} number of scalar multiplications over
85 /// G2:
86 /// - it proceeds with `num_var` number of rounds,
87 /// - at round i, we compute an MSM for `2^{num_var - i + 1}` number of G2
88 /// elements.
89 fn open(
90 prover_param: &Self::ProverParam,
91 polynomial: &impl MultilinearExtension<E::Fr>,
92 point: &[E::Fr],
93 ) -> Result<Self::Proof, PCSErrors> {
94 let open_timer = start_timer!(|| "open");
95
96 assert_eq!(
97 polynomial.num_vars(),
98 prover_param.num_vars,
99 "Invalid size of polynomial"
100 );
101 let nv = polynomial.num_vars();
102 let mut r: Vec<Vec<E::Fr>> = (0..nv + 1).map(|_| Vec::new()).collect();
103 let mut q: Vec<Vec<E::Fr>> = (0..nv + 1).map(|_| Vec::new()).collect();
104
105 r[nv] = polynomial.to_evaluations();
106
107 let mut proofs = Vec::new();
108
109 for (i, (&point_at_k, hi)) in point
110 .iter()
111 .zip(prover_param.powers_of_h.iter())
112 .take(nv)
113 .enumerate()
114 {
115 let ith_round = start_timer!(|| format!("{}-th round", i));
116
117 let k = nv - i;
118 let cur_dim = 1 << (k - 1);
119 let mut cur_q = vec![E::Fr::zero(); cur_dim];
120 let mut cur_r = vec![E::Fr::zero(); cur_dim];
121
122 for b in 0..(1 << (k - 1)) {
123 // q_b = pre_r [2^b + 1] - pre_r [2^b]
124 cur_q[b] = r[k][(b << 1) + 1] - r[k][b << 1];
125
126 // r_b = pre_r [2^b]*(1-p) + pre_r [2^b + 1] * p
127 cur_r[b] =
128 r[k][b << 1] * (E::Fr::one() - point_at_k) + (r[k][(b << 1) + 1] * point_at_k);
129 }
130
131 let scalars: Vec<_> = (0..(1 << k)).map(|x| cur_q[x >> 1].into_repr()).collect();
132
133 q[k] = cur_q;
134 r[k - 1] = cur_r;
135
136 // this is a MSM over G2 and is likely to be the bottleneck
137 proofs.push(VariableBaseMSM::multi_scalar_mul(&hi.evals, &scalars).into_affine());
138 end_timer!(ith_round);
139 }
140
141 end_timer!(open_timer);
142 Ok(Proof { proofs })
143 }
144
145 /// Verifies that `value` is the evaluation at `x` of the polynomial
146 /// committed inside `comm`.
147 ///
148 /// This function takes
149 /// - num_var number of pairing product.
150 /// - num_var number of MSM
151 fn verify(
152 verifier_param: &Self::VerifierParam,
153 commitment: &Self::Commitment,
154 point: &[E::Fr],
155 value: E::Fr,
156 proof: &Self::Proof,
157 ) -> Result<bool, PCSErrors> {
158 let verify_timer = start_timer!(|| "verify");
159 let prepare_inputs_timer = start_timer!(|| "prepare pairing inputs");
160
161 let scalar_size = E::Fr::size_in_bits();
162 let window_size = FixedBaseMSM::get_mul_window_size(verifier_param.num_vars);
163
164 let g_table = FixedBaseMSM::get_window_table(
165 scalar_size,
166 window_size,
167 verifier_param.g.into_projective(),
168 );
169 #[cfg(not(feature = "group-switched"))]
170 let g_mul: Vec<E::G1Projective> =
171 FixedBaseMSM::multi_scalar_mul(scalar_size, window_size, &g_table, point);
172 #[cfg(feature = "group-switched")]
173 let g_mul: Vec<E::G2Projective> =
174 FixedBaseMSM::multi_scalar_mul(scalar_size, window_size, &g_table, point);
175
176 let mut g1_vec: Vec<_> = (0..verifier_param.num_vars)
177 .map(|i| verifier_param.g_mask[i].into_projective() - g_mul[i])
178 .collect();
179 g1_vec.push(verifier_param.g.mul(value) - commitment.g_product.into_projective());
180
181 #[cfg(not(feature = "group-switched"))]
182 let g1_vec: Vec<E::G1Affine> = E::G1Projective::batch_normalization_into_affine(&g1_vec);
183 #[cfg(feature = "group-switched")]
184 let g1_vec: Vec<E::G2Affine> = E::G2Projective::batch_normalization_into_affine(&g1_vec);
185 let tmp = g1_vec[verifier_param.num_vars];
186 end_timer!(prepare_inputs_timer);
187
188 let pairing_product_timer = start_timer!(|| "pairing product");
189
190 #[cfg(not(feature = "group-switched"))]
191 let mut pairings: Vec<_> = g1_vec
192 .into_iter()
193 .take(verifier_param.num_vars)
194 .map(E::G1Prepared::from)
195 .zip(proof.proofs.iter().map(|&x| E::G2Prepared::from(x)))
196 .collect();
197
198 #[cfg(feature = "group-switched")]
199 let mut pairings: Vec<_> = proof
200 .proofs
201 .iter()
202 .take(verifier_param.num_vars)
203 .map(|&x| E::G1Prepared::from(x))
204 .zip(
205 g1_vec
206 .into_iter()
207 .take(verifier_param.num_vars)
208 .map(E::G2Prepared::from),
209 )
210 .collect();
211
212 #[cfg(not(feature = "group-switched"))]
213 pairings.push((
214 E::G1Prepared::from(tmp),
215 E::G2Prepared::from(verifier_param.h),
216 ));
217
218 #[cfg(feature = "group-switched")]
219 pairings.push((
220 E::G1Prepared::from(verifier_param.h),
221 E::G2Prepared::from(tmp),
222 ));
223
224 let res = E::product_of_pairings(pairings.iter()) == E::Fqk::one();
225
226 end_timer!(pairing_product_timer);
227 end_timer!(verify_timer);
228 Ok(res)
229 }
230}
231
232#[cfg(test)]
233mod tests {
234 use super::*;
235 use ark_bls12_381::Bls12_381;
236 use ark_ec::PairingEngine;
237 use ark_poly::{DenseMultilinearExtension, MultilinearExtension, SparseMultilinearExtension};
238 use ark_std::{rand::RngCore, test_rng, vec::Vec, UniformRand};
239 type E = Bls12_381;
240 type Fr = <E as PairingEngine>::Fr;
241
242 fn test_kzg_mlpc_helper<R: RngCore>(
243 uni_params: &UniversalParams<E>,
244 poly: &impl MultilinearExtension<Fr>,
245 rng: &mut R,
246 ) -> Result<(), PCSErrors> {
247 let nv = poly.num_vars();
248 assert_ne!(nv, 0);
249 let (ck, vk) = uni_params.trim(nv)?;
250 let point: Vec<_> = (0..nv).map(|_| Fr::rand(rng)).collect();
251 let com = KZGMultilinearPC::commit(&ck, poly)?;
252 let proof = KZGMultilinearPC::open(&ck, poly, &point)?;
253
254 let value = poly.evaluate(&point).unwrap();
255 assert!(KZGMultilinearPC::verify(&vk, &com, &point, value, &proof)?);
256
257 let value = Fr::rand(rng);
258 assert!(!KZGMultilinearPC::verify(&vk, &com, &point, value, &proof)?);
259
260 Ok(())
261 }
262
263 #[test]
264 fn setup_commit_verify_correct_polynomials() -> Result<(), PCSErrors> {
265 let mut rng = test_rng();
266
267 let uni_params = KZGMultilinearPC::<E>::setup(&mut rng, 10)?;
268
269 // normal polynomials
270 let poly1 = DenseMultilinearExtension::rand(8, &mut rng);
271 test_kzg_mlpc_helper(&uni_params, &poly1, &mut rng)?;
272
273 let poly2 = SparseMultilinearExtension::rand_with_config(9, 1 << 5, &mut rng);
274 test_kzg_mlpc_helper(&uni_params, &poly2, &mut rng)?;
275
276 // single-variate polynomials
277 let poly3 = DenseMultilinearExtension::rand(1, &mut rng);
278 test_kzg_mlpc_helper(&uni_params, &poly3, &mut rng)?;
279
280 let poly4 = SparseMultilinearExtension::rand_with_config(1, 1 << 1, &mut rng);
281 test_kzg_mlpc_helper(&uni_params, &poly4, &mut rng)?;
282 Ok(())
283 }
284
285 #[test]
286 fn setup_commit_verify_constant_polynomial() {
287 let mut rng = test_rng();
288
289 // normal polynomials
290 assert!(KZGMultilinearPC::<E>::setup(&mut rng, 0).is_err());
291 }
292}