lambdaworks_math/msm/
naive.rs

1use core::fmt::Display;
2
3use crate::cyclic_group::IsGroup;
4use crate::unsigned_integer::traits::IsUnsignedInteger;
5
6#[derive(Debug)]
7pub enum MSMError {
8    LengthMismatch(usize, usize),
9}
10
11impl Display for MSMError {
12    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
13        match self {
14            MSMError::LengthMismatch(cs, points) => write!(f, "`cs` and `points` must be of the same length to compute `msm`. Got: {cs} and {points}"),
15        }
16    }
17}
18
19#[cfg(feature = "std")]
20impl std::error::Error for MSMError {}
21
22/// This function computes the multiscalar multiplication (MSM).
23///
24/// Assume a group G of order r is given.
25/// Let `points = [g_1, ..., g_n]` be a tuple of group points in G and
26/// let `cs = [k_1, ..., k_n]` be a tuple of scalars in the Galois field GF(r).
27///
28/// Then, with additive notation, `msm(cs, points)` computes k_1 * g_1 + .... + k_n * g_n.
29///
30/// If `points` and `cs` are empty, then `msm` returns the zero element of the group.
31///
32/// Panics if `cs` and `points` have different lengths.
33pub fn msm<C, T>(cs: &[C], points: &[T]) -> Result<T, MSMError>
34where
35    C: IsUnsignedInteger,
36    T: IsGroup,
37{
38    if cs.len() != points.len() {
39        return Err(MSMError::LengthMismatch(cs.len(), points.len()));
40    }
41    let res = cs
42        .iter()
43        .zip(points.iter())
44        .map(|(&c, h)| h.operate_with_self(c))
45        .reduce(|acc, x| acc.operate_with(&x))
46        .unwrap_or_else(T::neutral_element);
47
48    Ok(res)
49}
50
51#[cfg(test)]
52mod tests {
53    use super::*;
54    use crate::elliptic_curve::short_weierstrass::curves::test_curve_1::TestCurve1;
55    use crate::elliptic_curve::short_weierstrass::point::ShortWeierstrassProjectivePoint;
56    use crate::elliptic_curve::traits::IsEllipticCurve;
57    use crate::field::fields::u64_prime_field::U64FieldElement;
58
59    const ORDER_R: u64 = 5;
60    type FE = U64FieldElement<ORDER_R>;
61
62    #[test]
63    fn msm_11_is_1_over_elliptic_curves() {
64        let c: [u64; 1] = [1];
65        let hiding = [TestCurve1::generator()];
66        assert_eq!(msm(&c, &hiding).unwrap(), TestCurve1::generator());
67    }
68
69    #[test]
70    fn msm_23_is_6_over_field_elements() {
71        let c: [u64; 1] = [3];
72        let hiding = [FE::new(2)];
73        assert_eq!(msm(&c, &hiding).unwrap(), FE::new(6));
74    }
75
76    #[test]
77    fn msm_23_is_6_over_elliptic_curves() {
78        let c: [u64; 1] = [3];
79        let g = TestCurve1::generator();
80        let hiding = [g.operate_with_self(2_u16)];
81        assert_eq!(msm(&c, &hiding).unwrap(), g.operate_with_self(6_u16));
82    }
83
84    #[test]
85    fn msm_with_c_2_3_hiding_3_4_is_18_over_field_elements() {
86        let c: [u64; 2] = [2, 3];
87        let hiding = [FE::new(3), FE::new(4)];
88        assert_eq!(msm(&c, &hiding).unwrap(), FE::new(18));
89    }
90
91    #[test]
92    fn msm_with_c_2_3_hiding_3_4_is_18_over_elliptic_curves() {
93        let c: [u64; 2] = [2, 3];
94        let g = TestCurve1::generator();
95        let hiding = [g.operate_with_self(3_u16), g.operate_with_self(4_u16)];
96        assert_eq!(msm(&c, &hiding).unwrap(), g.operate_with_self(18_u16));
97    }
98
99    #[test]
100    fn msm_with_empty_input_over_field_elements() {
101        let c: [u64; 0] = [];
102        let hiding: [FE; 0] = [];
103        assert_eq!(msm(&c, &hiding).unwrap(), FE::new(0));
104    }
105
106    #[test]
107    fn msm_with_empty_c_is_none_over_elliptic_curves() {
108        let c: [u64; 0] = [];
109        let hiding: [ShortWeierstrassProjectivePoint<TestCurve1>; 0] = [];
110        assert_eq!(
111            msm(&c, &hiding).unwrap(),
112            ShortWeierstrassProjectivePoint::neutral_element()
113        );
114    }
115}
lambdaworks_math/msm/naive.rs

lambdaworks_math/msm/
naive.rs
