Trait ark_ec::scalar_mul::variable_base::VariableBaseMSM

source · 
pub trait VariableBaseMSM: ScalarMul {
    fn msm_unchecked(
        bases: &[Self::MulBase],
        scalars: &[Self::ScalarField]
    ) -> Self { ... }
    fn msm(
        bases: &[Self::MulBase],
        scalars: &[Self::ScalarField]
    ) -> Result<Self, usize> { ... }
    fn msm_bigint(
        bases: &[Self::MulBase],
        bigints: &[<Self::ScalarField as PrimeField>::BigInt]
    ) -> Self { ... }
    fn msm_chunks<I, J>(bases_stream: &J, scalars_stream: &I) -> Self
    where
        I: Iterable + ?Sized,
        I::Item: Borrow<Self::ScalarField>,
        J: Iterable,
        J::Item: Borrow<Self::MulBase>,
    { ... }
}

Provided Methods§

Computes an inner product between the PrimeField elements in scalars and the corresponding group elements in bases.

If the elements have different length, it will chop the slices to the shortest length between scalars.len() and bases.len().

Reference: VariableBaseMSM::msm

Examples found in repository?
src/scalar_mul/variable_base/mod.rs (line 36)
34
35
36
37
38

    fn msm(bases: &[Self::MulBase], scalars: &[Self::ScalarField]) -> Result<Self, usize> {
        (bases.len() == scalars.len())
            .then(|| Self::msm_unchecked(bases, scalars))
            .ok_or(usize::min(bases.len(), scalars.len()))
    }
More examples
Hide additional examples
src/models/short_weierstrass/mod.rs (line 114)
109
110
111
112
113
114
115
116

    fn msm(
        bases: &[Affine<Self>],
        scalars: &[Self::ScalarField],
    ) -> Result<Projective<Self>, usize> {
        (bases.len() == scalars.len())
            .then(|| VariableBaseMSM::msm_unchecked(bases, scalars))
            .ok_or(usize::min(bases.len(), scalars.len()))
    }

Performs multi-scalar multiplication, without checking that bases.len() == scalars.len().

Warning

This method checks that bases and scalars have the same length. If they are unequal, it returns an error containing the shortest length over which the MSM can be performed.

Optimized implementation of multi-scalar multiplication.

Examples found in repository?
src/scalar_mul/variable_base/mod.rs (line 24)
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
80
81
82
83
84
85

    fn msm_unchecked(bases: &[Self::MulBase], scalars: &[Self::ScalarField]) -> Self {
        let bigints = cfg_into_iter!(scalars)
            .map(|s| s.into_bigint())
            .collect::<Vec<_>>();
        Self::msm_bigint(bases, &bigints)
    }

    /// Performs multi-scalar multiplication, without checking that `bases.len() == scalars.len()`.
    ///
    /// # Warning
    ///
    /// This method checks that `bases` and `scalars` have the same length.
    /// If they are unequal, it returns an error containing
    /// the shortest length over which the MSM can be performed.
    fn msm(bases: &[Self::MulBase], scalars: &[Self::ScalarField]) -> Result<Self, usize> {
        (bases.len() == scalars.len())
            .then(|| Self::msm_unchecked(bases, scalars))
            .ok_or(usize::min(bases.len(), scalars.len()))
    }

    /// Optimized implementation of multi-scalar multiplication.
    fn msm_bigint(
        bases: &[Self::MulBase],
        bigints: &[<Self::ScalarField as PrimeField>::BigInt],
    ) -> Self {
        if Self::NEGATION_IS_CHEAP {
            msm_bigint_wnaf(bases, bigints)
        } else {
            msm_bigint(bases, bigints)
        }
    }

    /// Streaming multi-scalar multiplication algorithm with hard-coded chunk
    /// size.
    fn msm_chunks<I: ?Sized, J>(bases_stream: &J, scalars_stream: &I) -> Self
    where
        I: Iterable,
        I::Item: Borrow<Self::ScalarField>,
        J: Iterable,
        J::Item: Borrow<Self::MulBase>,
    {
        assert!(scalars_stream.len() <= bases_stream.len());

        // remove offset
        let bases_init = bases_stream.iter();
        let mut scalars = scalars_stream.iter();

        // align the streams
        // TODO: change `skip` to `advance_by` once rust-lang/rust#7774 is fixed.
        // See <https://github.com/rust-lang/rust/issues/77404>
        let mut bases = bases_init.skip(bases_stream.len() - scalars_stream.len());
        let step: usize = 1 << 20;
        let mut result = Self::zero();
        for _ in 0..(scalars_stream.len() + step - 1) / step {
            let bases_step = (&mut bases)
                .take(step)
                .map(|b| *b.borrow())
                .collect::<Vec<_>>();
            let scalars_step = (&mut scalars)
                .take(step)
                .map(|s| s.borrow().into_bigint())
                .collect::<Vec<_>>();
            result += Self::msm_bigint(bases_step.as_slice(), scalars_step.as_slice());
        }
        result
    }
More examples
Hide additional examples
src/scalar_mul/variable_base/stream_pippenger.rs (lines 48-51)
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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

    pub fn add<B, S>(&mut self, base: B, scalar: S)
    where
        B: Borrow<G::MulBase>,
        S: Borrow<<G::ScalarField as PrimeField>::BigInt>,
    {
        self.scalars_buffer.push(*scalar.borrow());
        self.bases_buffer.push(*base.borrow());
        if self.scalars_buffer.len() == self.buf_size {
            self.result.add_assign(G::msm_bigint(
                self.bases_buffer.as_slice(),
                self.scalars_buffer.as_slice(),
            ));
            self.scalars_buffer.clear();
            self.bases_buffer.clear();
        }
    }

    /// Output the final Pippenger algorithm result.
    #[inline(always)]
    pub fn finalize(mut self) -> G {
        if !self.scalars_buffer.is_empty() {
            self.result +=
                G::msm_bigint(self.bases_buffer.as_slice(), self.scalars_buffer.as_slice());
        }
        self.result
    }
}

/// Hash map struct for Pippenger algorithm.
pub struct HashMapPippenger<G: VariableBaseMSM> {
    buffer: HashMap<G::MulBase, G::ScalarField>,
    result: G,
    buf_size: usize,
}

impl<G: VariableBaseMSM> HashMapPippenger<G> {
    /// Produce a new hash map with the maximum msm buffer size.
    pub fn new(max_msm_buffer: usize) -> Self {
        Self {
            buffer: HashMap::with_capacity(max_msm_buffer),
            result: G::zero(),
            buf_size: max_msm_buffer,
        }
    }

    /// Add a new (base, scalar) pair into the hash map.
    #[inline(always)]
    pub fn add<B, S>(&mut self, base: B, scalar: S)
    where
        B: Borrow<G::MulBase>,
        S: Borrow<G::ScalarField>,
    {
        // update the entry, guarding the possibility that it has been already set.
        let entry = self
            .buffer
            .entry(*base.borrow())
            .or_insert(G::ScalarField::zero());
        *entry += *scalar.borrow();
        if self.buffer.len() == self.buf_size {
            let bases = self.buffer.keys().cloned().collect::<Vec<_>>();
            let scalars = self
                .buffer
                .values()
                .map(|s| s.into_bigint())
                .collect::<Vec<_>>();
            self.result += G::msm_bigint(&bases, &scalars);
            self.buffer.clear();
        }
    }

    /// Update the final result with (base, scalar) pairs in the hash map.
    #[inline(always)]
    pub fn finalize(mut self) -> G {
        if !self.buffer.is_empty() {
            let bases = self.buffer.keys().cloned().collect::<Vec<_>>();
            let scalars = self
                .buffer
                .values()
                .map(|s| s.into_bigint())
                .collect::<Vec<_>>();

            self.result += G::msm_bigint(&bases, &scalars);
        }
        self.result
    }

Streaming multi-scalar multiplication algorithm with hard-coded chunk size.

Implementors§