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
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189

#![cfg_attr(docsrs, feature(doc_auto_cfg))]

use zeroize::Zeroize;

use ff::PrimeFieldBits;
use group::Group;

mod straus;
use straus::*;

mod pippenger;
use pippenger::*;

#[cfg(feature = "batch")]
mod batch;
#[cfg(feature = "batch")]
pub use batch::BatchVerifier;

#[cfg(test)]
mod tests;

pub(crate) fn prep_bits<G: Group>(pairs: &[(G::Scalar, G)], window: u8) -> Vec<Vec<u8>>
where
  G::Scalar: PrimeFieldBits,
{
  let w_usize = usize::from(window);

  let mut groupings = vec![];
  for pair in pairs {
    let p = groupings.len();
    let mut bits = pair.0.to_le_bits();
    groupings.push(vec![0; (bits.len() + (w_usize - 1)) / w_usize]);

    #[allow(unused_assignments)]
    for (i, mut raw_bit) in bits.iter_mut().enumerate() {
      let mut bit = u8::from(*raw_bit);
      *raw_bit = false;

      groupings[p][i / w_usize] |= bit << (i % w_usize);
      bit.zeroize();
    }
  }

  groupings
}

pub(crate) fn prep_tables<G: Group>(pairs: &[(G::Scalar, G)], window: u8) -> Vec<Vec<G>> {
  let mut tables = Vec::with_capacity(pairs.len());
  for pair in pairs {
    let p = tables.len();
    tables.push(vec![G::identity(); 2_usize.pow(window.into())]);
    let mut accum = G::identity();
    for i in 1 .. tables[p].len() {
      accum += pair.1;
      tables[p][i] = accum;
    }
  }
  tables
}

#[derive(Clone, Copy, PartialEq, Eq, Debug)]
enum Algorithm {
  Null,
  Single,
  Straus(u8),
  Pippenger(u8),
}

/*
Release (with runs 20, so all of these are off by 20x):

k256
Straus 3 is more efficient at 5 with 678µs per
Straus 4 is more efficient at 10 with 530µs per
Straus 5 is more efficient at 35 with 467µs per

Pippenger 5 is more efficient at 125 with 431µs per
Pippenger 6 is more efficient at 275 with 349µs per
Pippenger 7 is more efficient at 375 with 360µs per

dalek
Straus 3 is more efficient at 5 with 519µs per
Straus 4 is more efficient at 10 with 376µs per
Straus 5 is more efficient at 170 with 330µs per

Pippenger 5 is more efficient at 125 with 305µs per
Pippenger 6 is more efficient at 275 with 250µs per
Pippenger 7 is more efficient at 450 with 205µs per
Pippenger 8 is more efficient at 800 with 213µs per

Debug (with runs 5, so...):

k256
Straus 3 is more efficient at 5 with 2532µs per
Straus 4 is more efficient at 10 with 1930µs per
Straus 5 is more efficient at 80 with 1632µs per

Pippenger 5 is more efficient at 150 with 1441µs per
Pippenger 6 is more efficient at 300 with 1235µs per
Pippenger 7 is more efficient at 475 with 1182µs per
Pippenger 8 is more efficient at 625 with 1170µs per

dalek:
Straus 3 is more efficient at 5 with 971µs per
Straus 4 is more efficient at 10 with 782µs per
Straus 5 is more efficient at 75 with 778µs per
Straus 6 is more efficient at 165 with 867µs per

Pippenger 5 is more efficient at 125 with 677µs per
Pippenger 6 is more efficient at 250 with 655µs per
Pippenger 7 is more efficient at 475 with 500µs per
Pippenger 8 is more efficient at 875 with 499µs per
*/
fn algorithm(len: usize) -> Algorithm {
  #[cfg(not(debug_assertions))]
  if len == 0 {
    Algorithm::Null
  } else if len == 1 {
    Algorithm::Single
  } else if len < 10 {
    // Straus 2 never showed a performance benefit, even with just 2 elements
    Algorithm::Straus(3)
  } else if len < 20 {
    Algorithm::Straus(4)
  } else if len < 50 {
    Algorithm::Straus(5)
  } else if len < 100 {
    Algorithm::Pippenger(4)
  } else if len < 125 {
    Algorithm::Pippenger(5)
  } else if len < 275 {
    Algorithm::Pippenger(6)
  } else if len < 400 {
    Algorithm::Pippenger(7)
  } else {
    Algorithm::Pippenger(8)
  }

  #[cfg(debug_assertions)]
  if len == 0 {
    Algorithm::Null
  } else if len == 1 {
    Algorithm::Single
  } else if len < 10 {
    Algorithm::Straus(3)
  } else if len < 80 {
    Algorithm::Straus(4)
  } else if len < 100 {
    Algorithm::Straus(5)
  } else if len < 125 {
    Algorithm::Pippenger(4)
  } else if len < 275 {
    Algorithm::Pippenger(5)
  } else if len < 475 {
    Algorithm::Pippenger(6)
  } else if len < 750 {
    Algorithm::Pippenger(7)
  } else {
    Algorithm::Pippenger(8)
  }
}

/// Performs a multiexponentation, automatically selecting the optimal algorithm based on the
/// amount of pairs.
pub fn multiexp<G: Group>(pairs: &[(G::Scalar, G)]) -> G
where
  G::Scalar: PrimeFieldBits + Zeroize,
{
  match algorithm(pairs.len()) {
    Algorithm::Null => Group::identity(),
    Algorithm::Single => pairs[0].1 * pairs[0].0,
    Algorithm::Straus(window) => straus(pairs, window),
    Algorithm::Pippenger(window) => pippenger(pairs, window),
  }
}

/// Performs a multiexponentation in variable time, automatically selecting the optimal algorithm
/// based on the amount of pairs.
pub fn multiexp_vartime<G: Group>(pairs: &[(G::Scalar, G)]) -> G
where
  G::Scalar: PrimeFieldBits,
{
  match algorithm(pairs.len()) {
    Algorithm::Null => Group::identity(),
    Algorithm::Single => pairs[0].1 * pairs[0].0,
    Algorithm::Straus(window) => straus_vartime(pairs, window),
    Algorithm::Pippenger(window) => pippenger_vartime(pairs, window),
  }
}