ark_algebra_test_templates/
msm.rs

1use ark_ec::{
2    scalar_mul::variable_base::{ChunkedPippenger, HashMapPippenger, VariableBaseMSM},
3    ScalarMul,
4};
5use ark_ff::{PrimeField, UniformRand};
6use ark_std::vec::*;
7
8fn naive_var_base_msm<G: ScalarMul>(bases: &[G::MulBase], scalars: &[G::ScalarField]) -> G {
9    let mut acc = G::zero();
10
11    for (base, scalar) in bases.iter().zip(scalars.iter()) {
12        acc += *base * scalar;
13    }
14    acc
15}
16
17pub fn test_var_base_msm<G: VariableBaseMSM>() {
18    const SAMPLES: usize = 1 << 10;
19
20    let mut rng = ark_std::test_rng();
21
22    let v = (0..SAMPLES)
23        .map(|_| G::ScalarField::rand(&mut rng))
24        .collect::<Vec<_>>();
25    let g = (0..SAMPLES).map(|_| G::rand(&mut rng)).collect::<Vec<_>>();
26    let g = G::batch_convert_to_mul_base(&g);
27
28    let naive = naive_var_base_msm::<G>(g.as_slice(), v.as_slice());
29    let fast = G::msm(g.as_slice(), v.as_slice()).unwrap();
30
31    assert_eq!(naive, fast);
32}
33
34pub fn test_chunked_pippenger<G: VariableBaseMSM>() {
35    const SAMPLES: usize = 1 << 10;
36
37    let mut rng = ark_std::test_rng();
38
39    let v = (0..SAMPLES)
40        .map(|_| G::ScalarField::rand(&mut rng).into_bigint())
41        .collect::<Vec<_>>();
42    let g = (0..SAMPLES).map(|_| G::rand(&mut rng)).collect::<Vec<_>>();
43    let g = G::batch_convert_to_mul_base(&g);
44
45    let arkworks = G::msm_bigint(g.as_slice(), v.as_slice());
46
47    let mut p = ChunkedPippenger::<G>::new(1 << 20);
48    for (s, g) in v.iter().zip(g) {
49        p.add(g, s);
50    }
51    let mine = p.finalize();
52    assert_eq!(arkworks, mine);
53}
54
55pub fn test_hashmap_pippenger<G: VariableBaseMSM>() {
56    const SAMPLES: usize = 1 << 10;
57
58    let mut rng = ark_std::test_rng();
59
60    let mut v_scal = Vec::new();
61    let v = (0..SAMPLES)
62        .map(|_| {
63            let x = G::ScalarField::rand(&mut rng);
64            v_scal.push(x);
65            x.into_bigint()
66        })
67        .collect::<Vec<_>>();
68    let g = (0..SAMPLES).map(|_| G::rand(&mut rng)).collect::<Vec<_>>();
69    let g = G::batch_convert_to_mul_base(&g);
70
71    let arkworks = G::msm_bigint(g.as_slice(), v.as_slice());
72
73    let mut p = HashMapPippenger::<G>::new(1 << 20);
74    for (s, g) in v_scal.iter().zip(g) {
75        p.add(g, s);
76    }
77    let mine = p.finalize();
78    assert_eq!(arkworks, mine);
79}
ark_algebra_test_templates/msm.rs

ark_algebra_test_templates/
msm.rs
