wnaf/
base.rs

1use crate::{WindowSize, WnafScalar, WnafSize, wnaf_multi_exp, wnaf_table};
2use array::Array;
3use core::iter;
4use core::ops::Mul;
5use group::Group;
6
7/// Fixed window table for a group element, precomputed to improve scalar multiplication speed.
8///
9/// By fixing the window size at compile time, we are able to support fully `no_alloc`
10/// stack-allocated operation, and also use the type system to ensure [`WnafBase`] and
11/// [`WnafScalar`] are using the same window size.
12///
13/// Precomputations are guaranteed to only occur once per base and once per scalar. Users should
14/// select their window size based on how long the bases are expected to live; a larger window size
15/// will consume more memory and take longer to precompute, but result in faster scalar
16/// multiplications.
17///
18/// # Examples
19///
20/// ```ignore
21/// type MyWnafBase = WnafBase<ProjectivePoint, U5, U8>;
22/// type MyWnafScalar = WnafScalar<Scalar, U5, U129>;
23///
24/// let base = MyWnafBase::new(ProjectivePoint::GENERATOR);
25/// let scalar = MyWnafScalar::new(&s);
26/// let result = base * scalar;
27/// ```
28///
29/// Note that this pattern requires specifying a fixed window size `W`. This is necessary to ensure
30/// in the type system that the base and scalar `Wnaf`s were computed with the same window
31/// size, allowing the result to be computed infallibly.
32#[derive(Clone, Debug)]
33pub struct WnafBase<G: Group, W: WindowSize> {
34    table: Array<G, W::TableSize>,
35}
36
37impl<G: Group, W: WindowSize> WnafBase<G, W> {
38    /// Computes a window table for the given base with the specified window size `W`.
39    #[inline]
40    pub fn new(base: &G) -> Self {
41        let mut ret = Self::default();
42        ret.init_from_base(base);
43        ret
44    }
45
46    /// Initialize an already allocated window table from the given base.
47    #[inline]
48    pub fn init_from_base(&mut self, base: &G) {
49        wnaf_table(&mut self.table, base, W::USIZE);
50    }
51
52    /// Perform a multiscalar multiplication.
53    ///
54    /// Computes a sum-of-products `aA + bB + ...` in variable time with wNAF multi-exponentiation
55    /// using the interleaved window method, also known as Straus's method.
56    #[must_use]
57    pub fn multiscalar_mul<'a, I>(pairs: I) -> G
58    where
59        G::Scalar: WnafSize,
60        I: Clone + Iterator<Item = (&'a Self, &'a WnafScalar<G::Scalar, W>)>,
61    {
62        wnaf_multi_exp(pairs.map(|(b, s)| (b.table.as_slice(), s.wnaf.as_slice(), s.digits)))
63    }
64}
65
66impl<G: Group, W: WindowSize> Default for WnafBase<G, W> {
67    fn default() -> Self {
68        Self {
69            table: Array::from_fn(|_| G::generator()),
70        }
71    }
72}
73
74impl<G, W> Mul<&WnafScalar<G::Scalar, W>> for &WnafBase<G, W>
75where
76    G: Group<Scalar: WnafSize>,
77    W: WindowSize,
78{
79    type Output = G;
80
81    fn mul(self, rhs: &WnafScalar<G::Scalar, W>) -> Self::Output {
82        WnafBase::multiscalar_mul(iter::once((self, rhs)))
83    }
84}
85
86impl<G, W> Mul<&WnafScalar<G::Scalar, W>> for WnafBase<G, W>
87where
88    G: Group<Scalar: WnafSize>,
89    W: WindowSize,
90{
91    type Output = G;
92
93    #[inline]
94    fn mul(self, rhs: &WnafScalar<G::Scalar, W>) -> Self::Output {
95        &self * rhs
96    }
97}
98
99impl<G, W> Mul<WnafScalar<G::Scalar, W>> for WnafBase<G, W>
100where
101    G: Group<Scalar: WnafSize>,
102    W: WindowSize,
103{
104    type Output = G;
105
106    #[inline]
107    fn mul(self, rhs: WnafScalar<G::Scalar, W>) -> Self::Output {
108        &self * &rhs
109    }
110}
wnaf/base.rs

wnaf/
base.rs
