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::G1Affine>,
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, gi)) in point
104 .iter()
105 .zip(prover_param.powers_of_g.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 G1 and is likely to be the bottleneck
131 proofs.push(VariableBaseMSM::multi_scalar_mul(&gi.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 h_table = FixedBaseMSM::get_window_table(
159 scalar_size,
160 window_size,
161 verifier_param.h.into_projective(),
162 );
163 let h_mul: Vec<E::G2Projective> =
164 FixedBaseMSM::multi_scalar_mul(scalar_size, window_size, &h_table, point);
165
166 let h_vec: Vec<_> = (0..verifier_param.num_vars)
167 .map(|i| verifier_param.h_mask[i].into_projective() - h_mul[i])
168 .collect();
169 let h_vec: Vec<E::G2Affine> = E::G2Projective::batch_normalization_into_affine(&h_vec);
170 end_timer!(prepare_inputs_timer);
171
172 let pairing_product_timer = start_timer!(|| "pairing product");
173
174 let mut pairings: Vec<_> = proof
175 .proofs
176 .iter()
177 .map(|&x| E::G1Prepared::from(x))
178 .zip(
179 h_vec
180 .into_iter()
181 .take(verifier_param.num_vars)
182 .map(E::G2Prepared::from),
183 )
184 .collect();
185
186 pairings.push((
187 E::G1Prepared::from(
188 (verifier_param.g.mul(value) - commitment.g_product.into_projective())
189 .into_affine(),
190 ),
191 E::G2Prepared::from(verifier_param.h),
192 ));
193
194 let res = E::product_of_pairings(pairings.iter()) == E::Fqk::one();
195
196 end_timer!(pairing_product_timer);
197 end_timer!(verify_timer);
198 Ok(res)
199 }
200}
201
202#[cfg(test)]
203mod tests {
204 use super::*;
205 use ark_bls12_381::Bls12_381;
206 use ark_ec::PairingEngine;
207 use ark_poly::{DenseMultilinearExtension, MultilinearExtension, SparseMultilinearExtension};
208 use ark_std::{rand::RngCore, test_rng, vec::Vec, UniformRand};
209 type E = Bls12_381;
210 type Fr = <E as PairingEngine>::Fr;
211
212 fn test_kzg_mlpc_helper<R: RngCore>(
213 uni_params: &UniversalParams<E>,
214 poly: &impl MultilinearExtension<Fr>,
215 rng: &mut R,
216 ) -> Result<(), PCSErrors> {
217 let nv = poly.num_vars();
218 assert_ne!(nv, 0);
219 let (ck, vk) = uni_params.trim(nv)?;
220 let point: Vec<_> = (0..nv).map(|_| Fr::rand(rng)).collect();
221 let com = KZGMultilinearPC::commit(&ck, poly)?;
222 let proof = KZGMultilinearPC::open(&ck, poly, &point)?;
223
224 let value = poly.evaluate(&point).unwrap();
225 assert!(KZGMultilinearPC::verify(&vk, &com, &point, value, &proof)?);
226
227 let value = Fr::rand(rng);
228 assert!(!KZGMultilinearPC::verify(&vk, &com, &point, value, &proof)?);
229
230 Ok(())
231 }
232
233 #[test]
234 fn setup_commit_verify_correct_polynomials() -> Result<(), PCSErrors> {
235 let mut rng = test_rng();
236
237 let uni_params = KZGMultilinearPC::<E>::setup(&mut rng, 10)?;
238
239 // normal polynomials
240 let poly1 = DenseMultilinearExtension::rand(8, &mut rng);
241 test_kzg_mlpc_helper(&uni_params, &poly1, &mut rng)?;
242
243 let poly2 = SparseMultilinearExtension::rand_with_config(9, 1 << 5, &mut rng);
244 test_kzg_mlpc_helper(&uni_params, &poly2, &mut rng)?;
245
246 // single-variate polynomials
247 let poly3 = DenseMultilinearExtension::rand(1, &mut rng);
248 test_kzg_mlpc_helper(&uni_params, &poly3, &mut rng)?;
249
250 let poly4 = SparseMultilinearExtension::rand_with_config(1, 1 << 1, &mut rng);
251 test_kzg_mlpc_helper(&uni_params, &poly4, &mut rng)?;
252 Ok(())
253 }
254
255 #[test]
256 fn setup_commit_verify_constant_polynomial() {
257 let mut rng = test_rng();
258
259 // normal polynomials
260 assert!(KZGMultilinearPC::<E>::setup(&mut rng, 0).is_err());
261 }
262}