ark_algebra_test_templates/
msm.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
use ark_ec::{
    scalar_mul::variable_base::{ChunkedPippenger, HashMapPippenger, VariableBaseMSM},
    ScalarMul,
};
use ark_ff::{PrimeField, UniformRand};
use ark_std::vec::*;

fn naive_var_base_msm<G: ScalarMul>(bases: &[G::MulBase], scalars: &[G::ScalarField]) -> G {
    let mut acc = G::zero();

    for (base, scalar) in bases.iter().zip(scalars.iter()) {
        acc += *base * scalar;
    }
    acc
}

pub fn test_var_base_msm<G: VariableBaseMSM>() {
    const SAMPLES: usize = 1 << 10;

    let mut rng = ark_std::test_rng();

    let v = (0..SAMPLES)
        .map(|_| G::ScalarField::rand(&mut rng))
        .collect::<Vec<_>>();
    let g = (0..SAMPLES).map(|_| G::rand(&mut rng)).collect::<Vec<_>>();
    let g = G::batch_convert_to_mul_base(&g);

    let naive = naive_var_base_msm::<G>(g.as_slice(), v.as_slice());
    let fast = G::msm(g.as_slice(), v.as_slice()).unwrap();

    assert_eq!(naive, fast);
}

pub fn test_chunked_pippenger<G: VariableBaseMSM>() {
    const SAMPLES: usize = 1 << 10;

    let mut rng = ark_std::test_rng();

    let v = (0..SAMPLES)
        .map(|_| G::ScalarField::rand(&mut rng).into_bigint())
        .collect::<Vec<_>>();
    let g = (0..SAMPLES).map(|_| G::rand(&mut rng)).collect::<Vec<_>>();
    let g = G::batch_convert_to_mul_base(&g);

    let arkworks = G::msm_bigint(g.as_slice(), v.as_slice());

    let mut p = ChunkedPippenger::<G>::new(1 << 20);
    for (s, g) in v.iter().zip(g) {
        p.add(g, s);
    }
    let mine = p.finalize();
    assert_eq!(arkworks, mine);
}

pub fn test_hashmap_pippenger<G: VariableBaseMSM>() {
    const SAMPLES: usize = 1 << 10;

    let mut rng = ark_std::test_rng();

    let mut v_scal = Vec::new();
    let v = (0..SAMPLES)
        .map(|_| {
            let x = G::ScalarField::rand(&mut rng);
            v_scal.push(x);
            x.into_bigint()
        })
        .collect::<Vec<_>>();
    let g = (0..SAMPLES).map(|_| G::rand(&mut rng)).collect::<Vec<_>>();
    let g = G::batch_convert_to_mul_base(&g);

    let arkworks = G::msm_bigint(g.as_slice(), v.as_slice());

    let mut p = HashMapPippenger::<G>::new(1 << 20);
    for (s, g) in v_scal.iter().zip(g) {
        p.add(g, s);
    }
    let mine = p.finalize();
    assert_eq!(arkworks, mine);
}