ark_ec/scalar_mul/
wnaf.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
80
81
82
83
use crate::PrimeGroup;
use ark_ff::{BigInteger, PrimeField};
use ark_std::vec::*;

/// A helper type that contains all the context required for computing
/// a window NAF multiplication of a group element by a scalar.
pub struct WnafContext {
    pub window_size: usize,
}

impl WnafContext {
    /// Constructs a new context for a window of size `window_size`.
    ///
    /// # Panics
    ///
    /// This function will panic if not `2 <= window_size < 64`
    pub fn new(window_size: usize) -> Self {
        assert!(window_size >= 2);
        assert!(window_size < 64);
        Self { window_size }
    }

    pub fn table<G: PrimeGroup>(&self, mut base: G) -> Vec<G> {
        let mut table = Vec::with_capacity(1 << (self.window_size - 1));
        let dbl = base.double();

        for _ in 0..(1 << (self.window_size - 1)) {
            table.push(base);
            base += &dbl;
        }
        table
    }

    /// Computes scalar multiplication of a group element `g` by `scalar`.
    ///
    /// This method uses the wNAF algorithm to perform the scalar
    /// multiplication; first, it uses `Self::table` to calculate an
    /// appropriate table of multiples of `g`, and then uses the wNAF
    /// algorithm to compute the scalar multiple.
    pub fn mul<G: PrimeGroup>(&self, g: G, scalar: &G::ScalarField) -> G {
        let table = self.table(g);
        self.mul_with_table(&table, scalar).unwrap()
    }

    /// Computes scalar multiplication of a group element by `scalar`.
    /// `base_table` holds precomputed multiples of the group element; it can be
    /// generated using `Self::table`. `scalar` is an element of
    /// `G::ScalarField`.
    ///
    /// Returns `None` if the table is too small.
    pub fn mul_with_table<G: PrimeGroup>(
        &self,
        base_table: &[G],
        scalar: &G::ScalarField,
    ) -> Option<G> {
        if 1 << (self.window_size - 1) > base_table.len() {
            return None;
        }
        let scalar_wnaf = scalar.into_bigint().find_wnaf(self.window_size).unwrap();

        let mut result = G::zero();

        let mut found_non_zero = false;

        for n in scalar_wnaf.iter().rev() {
            if found_non_zero {
                result.double_in_place();
            }

            if *n != 0 {
                found_non_zero = true;

                if *n > 0 {
                    result += &base_table[(n / 2) as usize];
                } else {
                    result -= &base_table[((-n) / 2) as usize];
                }
            }
        }

        Some(result)
    }
}