generic_ec/
multiscalar.rs

1//! Multiscalar multiplication
2//!
3//! Let $s_{1, \dots, n}$ and $P_{1, \dots, n}$ be lists of scalars and points
4//! respectively. Multiscalar multiplication is computing point $Q$ such that:
5//!
6//! $$Q = s_1 P_1 + \dots + s_n P_n$$
7//!
8//! This module provides various algorithms for computing multiscalar multiplication
9//! efficiently.
10//!
11//! ## Performance
12//! Computing the sum naively, i.e. calculating each $s_i P_i$ separately and
13//! $\sum$-ing them, is inefficient even for small $n$. You can see that in the
14//! comparison below.
15//!
16#![doc = include_str!("../perf/multiscalar/secp256k1.svg")]
17//!
18//! ## How to use it
19//! In most cases, all you need is [`Scalar::multiscalar_mul`] which defaults
20//! to the most efficient available algorithm, similarly to [`struct@Default`].
21//!
22//! Alternatively, if you need to use a specific algorithm, this module provides
23//! [`Straus`] and [`Dalek`].
24//!
25//! On [`Ed25519`](crate::curves::Ed25519) curve, consider using [`Dalek`] multiscalar
26//! implementation.
27
28use crate::{Curve, Point, Scalar};
29
30#[cfg(feature = "alloc")]
31mod straus;
32
33#[cfg(feature = "alloc")]
34pub use self::straus::Straus;
35
36/// Multiscalar multiplication algorithm
37///
38/// See [module-level docs](self) for motivation and list of provided algorithms.
39pub trait MultiscalarMul<E: Curve> {
40    /// Performs multiscalar multiplication
41    ///
42    /// Takes iterator of pairs `(scalar, point)`. Returns sum of `scalar * point`. Iterator must have
43    /// exact size (i.e. it's [`ExactSizeIterator`]). Iterator size is used to determine the best
44    /// algorithm for multiscalar multiplication, preallocate memory, etc. If iterator size is not
45    /// correct, it may worsen performance or lead to runtime panic.
46    ///
47    /// Note that the multiscalar algorithm is not necessarily constant-time, thus is should not be
48    /// used with [`SecretScalar<E>`](crate::SecretScalar).
49    fn multiscalar_mul<S, P>(scalar_points: impl ExactSizeIterator<Item = (S, P)>) -> Point<E>
50    where
51        S: AsRef<Scalar<E>>,
52        P: AsRef<Point<E>>;
53}
54
55/// Defaults to the most efficient multiscalar multiplication algorithm
56///
57/// When `alloc` feature is off, it always falls back to [`Naive`] implementation.
58///
59/// When `alloc` feature is on, it uses [`Straus`] algorithm.
60///
61/// It may be more convenient to use [`Scalar::multiscalar_mul`] which is an alias
62/// to `Default`.
63pub struct Default;
64
65#[cfg(not(feature = "alloc"))]
66impl<E: Curve> MultiscalarMul<E> for Default {
67    fn multiscalar_mul<S, P>(scalar_points: impl ExactSizeIterator<Item = (S, P)>) -> Point<E>
68    where
69        S: AsRef<Scalar<E>>,
70        P: AsRef<Point<E>>,
71    {
72        Naive::multiscalar_mul(scalar_points)
73    }
74}
75
76#[cfg(feature = "alloc")]
77impl<E: Curve> MultiscalarMul<E> for Default {
78    fn multiscalar_mul<S, P>(scalar_points: impl ExactSizeIterator<Item = (S, P)>) -> Point<E>
79    where
80        S: AsRef<Scalar<E>>,
81        P: AsRef<Point<E>>,
82    {
83        Straus::multiscalar_mul(scalar_points)
84    }
85}
86
87/// Naive algorithm
88///
89/// Computes multiscalar multiplication naively, by calculating each $s_i P_i$ separately,
90/// and $\sum$-ing them.
91///
92/// Complexity:
93///
94/// $$\text{cost} = \log_2 s \cdot D + \frac{1}{2} \log_2 s \cdot A$$
95pub struct Naive;
96
97impl<E: Curve> MultiscalarMul<E> for Naive {
98    fn multiscalar_mul<S, P>(scalar_points: impl IntoIterator<Item = (S, P)>) -> Point<E>
99    where
100        S: AsRef<Scalar<E>>,
101        P: AsRef<Point<E>>,
102    {
103        scalar_points
104            .into_iter()
105            .map(|(scalar, point)| scalar.as_ref() * point.as_ref())
106            .sum()
107    }
108}
109
110/// Multiscalar implementation for [`Ed25519`] curve
111///
112/// [`curve25519_dalek`](curve25519) library provides multiscalar multiplication algorithm which only
113/// works with [`Ed25519`] curve. Due to the fact that it's specifically instantiated for
114/// the only one curve, this implementation is more efficient than generic [`struct@Default`]
115/// or [`Straus`].
116///
117#[doc = include_str!("../perf/multiscalar/ed25519.svg")]
118///
119/// [`Ed25519`]: crate::curves::Ed25519
120#[cfg(all(feature = "curve-ed25519", feature = "alloc"))]
121pub struct Dalek;
122
123#[cfg(all(feature = "curve-ed25519", feature = "alloc"))]
124impl MultiscalarMul<crate::curves::Ed25519> for Dalek {
125    fn multiscalar_mul<S, P>(
126        scalar_points: impl IntoIterator<Item = (S, P)>,
127    ) -> Point<crate::curves::Ed25519>
128    where
129        S: AsRef<Scalar<crate::curves::Ed25519>>,
130        P: AsRef<Point<crate::curves::Ed25519>>,
131    {
132        use alloc::vec::Vec;
133
134        use curve25519::traits::VartimeMultiscalarMul;
135        use generic_ec_core::{OnCurve, SmallFactor};
136
137        use crate::as_raw::AsRaw;
138
139        let scalar_points = scalar_points.into_iter().collect::<Vec<_>>();
140        let scalars = scalar_points.iter().map(|(s, _)| &s.as_ref().as_raw().0);
141        let points = scalar_points.iter().map(|(_, p)| &p.as_ref().as_raw().0);
142
143        let result = curve25519::EdwardsPoint::vartime_multiscalar_mul(scalars, points);
144        let result = generic_ec_curves::ed25519::Point(result);
145
146        // Resulting point must be valid
147        debug_assert!(result.is_on_curve().into() && result.is_torsion_free().into());
148        Point::from_raw_unchecked(result)
149    }
150}
generic_ec/multiscalar.rs

generic_ec/
multiscalar.rs
