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