ark_poly_commit/multilinear_pc/
mod.rs

1use crate::multilinear_pc::data_structures::{
2    Commitment, CommitterKey, Proof, UniversalParams, VerifierKey,
3};
4use ark_ec::{
5    pairing::Pairing,
6    scalar_mul::{BatchMulPreprocessing, ScalarMul},
7    AffineRepr, CurveGroup, VariableBaseMSM,
8};
9use ark_ff::{Field, One, PrimeField, Zero};
10use ark_poly::{DenseMultilinearExtension, MultilinearExtension};
11#[cfg(not(feature = "std"))]
12use ark_std::vec::Vec;
13use ark_std::{
14    collections::LinkedList, iter::FromIterator, marker::PhantomData, ops::Mul, rand::RngCore,
15    UniformRand,
16};
17
18/// data structures used by multilinear extension commitment scheme
19pub mod data_structures;
20
21/// Polynomial Commitment Scheme on multilinear extensions.
22pub struct MultilinearPC<E: Pairing> {
23    _engine: PhantomData<E>,
24}
25
26impl<E: Pairing> MultilinearPC<E> {
27    /// setup
28    pub fn setup<R: RngCore>(num_vars: usize, rng: &mut R) -> UniversalParams<E> {
29        assert!(num_vars > 0, "constant polynomial not supported");
30        let g = E::G1::rand(rng);
31        let h = E::G2::rand(rng);
32        let mut powers_of_g = Vec::new();
33        let mut powers_of_h = Vec::new();
34        let t: Vec<_> = (0..num_vars).map(|_| E::ScalarField::rand(rng)).collect();
35
36        let mut eq: LinkedList<DenseMultilinearExtension<E::ScalarField>> =
37            LinkedList::from_iter(eq_extension(&t).into_iter());
38        let mut eq_arr = LinkedList::new();
39        let mut base = eq.pop_back().unwrap().evaluations;
40
41        for i in (0..num_vars).rev() {
42            eq_arr.push_front(remove_dummy_variable(&base, i));
43            if i != 0 {
44                let mul = eq.pop_back().unwrap().evaluations;
45                base = base
46                    .into_iter()
47                    .zip(mul.into_iter())
48                    .map(|(a, b)| a * &b)
49                    .collect();
50            }
51        }
52
53        let mut pp_powers = Vec::new();
54        for i in 0..num_vars {
55            let eq = eq_arr.pop_front().unwrap();
56            let pp_k_powers = (0..(1 << (num_vars - i))).map(|x| eq[x]);
57            pp_powers.extend(pp_k_powers);
58        }
59
60        let g_table = BatchMulPreprocessing::new(g, num_vars);
61        let pp_g = g_table.batch_mul(&pp_powers);
62        let pp_h = h.batch_mul(&pp_powers);
63        let mut start = 0;
64        for i in 0..num_vars {
65            let size = 1 << (num_vars - i);
66            let pp_k_g = (&pp_g[start..(start + size)]).to_vec();
67            let pp_k_h = (&pp_h[start..(start + size)]).to_vec();
68            powers_of_g.push(pp_k_g);
69            powers_of_h.push(pp_k_h);
70            start += size;
71        }
72
73        // uncomment to measure the time for calculating vp
74        // let vp_generation_timer = start_timer!(|| "VP generation");
75        let g_mask = g_table.batch_mul(&t);
76        // end_timer!(vp_generation_timer);
77
78        UniversalParams {
79            num_vars,
80            g: g.into_affine(),
81            g_mask,
82            h: h.into_affine(),
83            powers_of_g,
84            powers_of_h,
85        }
86    }
87
88    /// Trim the universal parameters to specialize the public parameters
89    /// for multilinear polynomials to the given `supported_num_vars`, and returns committer key and verifier key.
90    /// `supported_num_vars` should be in range `1..=params.num_vars`
91    pub fn trim(
92        params: &UniversalParams<E>,
93        supported_num_vars: usize,
94    ) -> (CommitterKey<E>, VerifierKey<E>) {
95        assert!(supported_num_vars <= params.num_vars);
96        let to_reduce = params.num_vars - supported_num_vars;
97        let ck = CommitterKey {
98            powers_of_h: (&params.powers_of_h[to_reduce..]).to_vec(),
99            powers_of_g: (&params.powers_of_g[to_reduce..]).to_vec(),
100            g: params.g,
101            h: params.h,
102            nv: supported_num_vars,
103        };
104        let vk = VerifierKey {
105            nv: supported_num_vars,
106            g: params.g,
107            h: params.h,
108            g_mask_random: (&params.g_mask[to_reduce..]).to_vec(),
109        };
110        (ck, vk)
111    }
112
113    /// commit
114    pub fn commit(
115        ck: &CommitterKey<E>,
116        polynomial: &impl MultilinearExtension<E::ScalarField>,
117    ) -> Commitment<E> {
118        let nv = polynomial.num_vars();
119        let scalars: Vec<_> = polynomial
120            .to_evaluations()
121            .into_iter()
122            .map(|x| x.into_bigint())
123            .collect();
124        let g_product =
125            <E::G1 as VariableBaseMSM>::msm_bigint(&ck.powers_of_g[0], scalars.as_slice())
126                .into_affine();
127        Commitment { nv, g_product }
128    }
129
130    /// On input a polynomial `p` and a point `point`, outputs a proof for the same.
131    pub fn open(
132        ck: &CommitterKey<E>,
133        polynomial: &impl MultilinearExtension<E::ScalarField>,
134        point: &[E::ScalarField],
135    ) -> Proof<E> {
136        assert_eq!(polynomial.num_vars(), ck.nv, "Invalid size of polynomial");
137        let nv = polynomial.num_vars();
138        let mut r: Vec<Vec<E::ScalarField>> = (0..nv + 1).map(|_| Vec::new()).collect();
139        let mut q: Vec<Vec<E::ScalarField>> = (0..nv + 1).map(|_| Vec::new()).collect();
140
141        r[nv] = polynomial.to_evaluations();
142
143        let mut proofs = Vec::new();
144        for i in 0..nv {
145            let k = nv - i;
146            let point_at_k = point[i];
147            q[k] = (0..(1 << (k - 1)))
148                .map(|_| E::ScalarField::zero())
149                .collect();
150            r[k - 1] = (0..(1 << (k - 1)))
151                .map(|_| E::ScalarField::zero())
152                .collect();
153            for b in 0..(1 << (k - 1)) {
154                q[k][b] = r[k][(b << 1) + 1] - &r[k][b << 1];
155                r[k - 1][b] = r[k][b << 1] * &(E::ScalarField::one() - &point_at_k)
156                    + &(r[k][(b << 1) + 1] * &point_at_k);
157            }
158            let scalars: Vec<_> = (0..(1 << k))
159                .map(|x| q[k][x >> 1].into_bigint()) // fine
160                .collect();
161
162            let pi_h =
163                <E::G2 as VariableBaseMSM>::msm_bigint(&ck.powers_of_h[i], &scalars).into_affine(); // no need to move outside and partition
164            proofs.push(pi_h);
165        }
166
167        Proof { proofs }
168    }
169
170    /// Verifies that `value` is the evaluation at `x` of the polynomial
171    /// committed inside `comm`.
172    pub fn check<'a>(
173        vk: &VerifierKey<E>,
174        commitment: &Commitment<E>,
175        point: &[E::ScalarField],
176        value: E::ScalarField,
177        proof: &Proof<E>,
178    ) -> bool {
179        let left = E::pairing(commitment.g_product.into_group() - &vk.g.mul(value), vk.h);
180
181        let g_mul = vk.g.into_group().batch_mul(point);
182
183        let pairing_lefts: Vec<_> = (0..vk.nv)
184            .map(|i| vk.g_mask_random[i].into_group() - &g_mul[i])
185            .collect();
186        let pairing_lefts: Vec<E::G1Affine> = E::G1::normalize_batch(&pairing_lefts);
187        let pairing_lefts: Vec<E::G1Prepared> = pairing_lefts
188            .into_iter()
189            .map(|x| E::G1Prepared::from(x))
190            .collect();
191
192        let pairing_rights: Vec<E::G2Prepared> = proof
193            .proofs
194            .iter()
195            .map(|x| E::G2Prepared::from(*x))
196            .collect();
197
198        let right = E::multi_pairing(pairing_lefts, pairing_rights);
199        left == right
200    }
201}
202
203/// fix first `pad` variables of `poly` represented in evaluation form to zero
204fn remove_dummy_variable<F: Field>(poly: &[F], pad: usize) -> Vec<F> {
205    if pad == 0 {
206        return poly.to_vec();
207    }
208    if !poly.len().is_power_of_two() {
209        panic!("Size of polynomial should be power of two. ")
210    }
211    let nv = ark_std::log2(poly.len()) as usize - pad;
212    let table: Vec<_> = (0..(1 << nv)).map(|x| poly[x << pad]).collect();
213    table
214}
215
216/// generate eq(t,x), a product of multilinear polynomials with fixed t.
217/// eq(a,b) is takes extensions of a,b in {0,1}^num_vars such that if a and b in {0,1}^num_vars are equal
218/// then this polynomial evaluates to 1.
219fn eq_extension<F: Field>(t: &[F]) -> Vec<DenseMultilinearExtension<F>> {
220    let dim = t.len();
221    let mut result = Vec::new();
222    for i in 0..dim {
223        let mut poly = Vec::with_capacity(1 << dim);
224        for x in 0..(1 << dim) {
225            let xi = if x >> i & 1 == 1 { F::one() } else { F::zero() };
226            let ti = t[i];
227            let ti_xi = ti * xi;
228            poly.push(ti_xi + ti_xi - xi - ti + F::one());
229        }
230        result.push(DenseMultilinearExtension::from_evaluations_vec(dim, poly));
231    }
232
233    result
234}
235
236#[cfg(test)]
237mod tests {
238    use crate::multilinear_pc::{data_structures::UniversalParams, MultilinearPC};
239    use ark_bls12_381::Bls12_381;
240    use ark_ec::pairing::Pairing;
241    use ark_poly::{
242        DenseMultilinearExtension, MultilinearExtension, Polynomial, SparseMultilinearExtension,
243    };
244    #[cfg(not(feature = "std"))]
245    use ark_std::vec::Vec;
246    use ark_std::{rand::RngCore, test_rng, UniformRand};
247    type E = Bls12_381;
248    type Fr = <E as Pairing>::ScalarField;
249
250    fn test_polynomial<R: RngCore>(
251        uni_params: &UniversalParams<E>,
252        poly: &impl MultilinearExtension<Fr>,
253        rng: &mut R,
254    ) {
255        let nv = poly.num_vars();
256        assert_ne!(nv, 0);
257        let (ck, vk) = MultilinearPC::<E>::trim(&uni_params, nv);
258        let point: Vec<_> = (0..nv).map(|_| Fr::rand(rng)).collect();
259        let com = MultilinearPC::commit(&ck, poly);
260        let proof = MultilinearPC::open(&ck, poly, &point);
261
262        let value = poly.evaluate(&point);
263        let result = MultilinearPC::check(&vk, &com, &point, value, &proof);
264        assert!(result);
265    }
266
267    #[test]
268    fn setup_commit_verify_correct_polynomials() {
269        let mut rng = test_rng();
270
271        // normal polynomials
272        let uni_params = MultilinearPC::setup(10, &mut rng);
273
274        let poly1 = DenseMultilinearExtension::rand(8, &mut rng);
275        test_polynomial(&uni_params, &poly1, &mut rng);
276
277        let poly2 = SparseMultilinearExtension::rand_with_config(9, 1 << 5, &mut rng);
278        test_polynomial(&uni_params, &poly2, &mut rng);
279
280        // single-variate polynomials
281
282        let poly3 = DenseMultilinearExtension::rand(1, &mut rng);
283        test_polynomial(&uni_params, &poly3, &mut rng);
284
285        let poly4 = SparseMultilinearExtension::rand_with_config(1, 1 << 1, &mut rng);
286        test_polynomial(&uni_params, &poly4, &mut rng);
287    }
288
289    #[test]
290    #[should_panic]
291    fn setup_commit_verify_constant_polynomial() {
292        let mut rng = test_rng();
293
294        // normal polynomials
295        MultilinearPC::<E>::setup(0, &mut rng);
296    }
297
298    #[test]
299    fn setup_commit_verify_incorrect_polynomial_should_return_false() {
300        let mut rng = test_rng();
301        let nv = 8;
302        let uni_params = MultilinearPC::setup(nv, &mut rng);
303        let poly = DenseMultilinearExtension::rand(nv, &mut rng);
304        let nv = uni_params.num_vars;
305        let (ck, vk) = MultilinearPC::<E>::trim(&uni_params, nv);
306        let point: Vec<_> = (0..nv).map(|_| Fr::rand(&mut rng)).collect();
307        let com = MultilinearPC::commit(&ck, &poly);
308        let proof = MultilinearPC::open(&ck, &poly, &point);
309
310        let value = poly.evaluate(&point);
311        let result = MultilinearPC::check(&vk, &com, &point, value + &(1u16.into()), &proof);
312        assert!(!result);
313    }
314}
ark_poly_commit/multilinear_pc/mod.rs

ark_poly_commit/multilinear_pc/
mod.rs
