zksync_pairing/
wnaf.rs

1use super::{CurveProjective, PrimeField, PrimeFieldRepr};
2
3/// Replaces the contents of `table` with a w-NAF window table for the given window size.
4pub(crate) fn wnaf_table<G: CurveProjective>(table: &mut Vec<G>, mut base: G, window: usize) {
5    table.truncate(0);
6    table.reserve(1 << (window - 1));
7
8    let mut dbl = base;
9    dbl.double();
10
11    for _ in 0..(1 << (window - 1)) {
12        table.push(base);
13        base.add_assign(&dbl);
14    }
15}
16
17/// Replaces the contents of `wnaf` with the w-NAF representation of a scalar.
18pub(crate) fn wnaf_form<S: PrimeFieldRepr>(wnaf: &mut Vec<i64>, mut c: S, window: usize) {
19    wnaf.truncate(0);
20
21    while !c.is_zero() {
22        let mut u;
23        if c.is_odd() {
24            u = (c.as_ref()[0] % (1 << (window + 1))) as i64;
25
26            if u > (1 << window) {
27                u -= 1 << (window + 1);
28            }
29
30            if u > 0 {
31                c.sub_noborrow(&S::from(u as u64));
32            } else {
33                c.add_nocarry(&S::from((-u) as u64));
34            }
35        } else {
36            u = 0;
37        }
38
39        wnaf.push(u);
40
41        c.div2();
42    }
43}
44
45/// Performs w-NAF exponentiation with the provided window table and w-NAF form scalar.
46///
47/// This function must be provided a `table` and `wnaf` that were constructed with
48/// the same window size; otherwise, it may panic or produce invalid results.
49pub(crate) fn wnaf_exp<G: CurveProjective>(table: &[G], wnaf: &[i64]) -> G {
50    let mut result = G::zero();
51
52    let mut found_one = false;
53
54    for n in wnaf.iter().rev() {
55        if found_one {
56            result.double();
57        }
58
59        if *n != 0 {
60            found_one = true;
61
62            if *n > 0 {
63                result.add_assign(&table[(n / 2) as usize]);
64            } else {
65                result.sub_assign(&table[((-n) / 2) as usize]);
66            }
67        }
68    }
69
70    result
71}
72
73/// A "w-ary non-adjacent form" exponentiation context.
74#[derive(Debug)]
75pub struct Wnaf<W, B, S> {
76    base: B,
77    scalar: S,
78    window_size: W,
79}
80
81impl<G: CurveProjective> Wnaf<(), Vec<G>, Vec<i64>> {
82    /// Construct a new wNAF context without allocating.
83    pub fn new() -> Self {
84        Wnaf {
85            base: vec![],
86            scalar: vec![],
87            window_size: (),
88        }
89    }
90
91    /// Given a base and a number of scalars, compute a window table and return a `Wnaf` object that
92    /// can perform exponentiations with `.scalar(..)`.
93    pub fn base(&mut self, base: G, num_scalars: usize) -> Wnaf<usize, &[G], &mut Vec<i64>> {
94        // Compute the appropriate window size based on the number of scalars.
95        let window_size = G::recommended_wnaf_for_num_scalars(num_scalars);
96
97        // Compute a wNAF table for the provided base and window size.
98        wnaf_table(&mut self.base, base, window_size);
99
100        // Return a Wnaf object that immutably borrows the computed base storage location,
101        // but mutably borrows the scalar storage location.
102        Wnaf {
103            base: &self.base[..],
104            scalar: &mut self.scalar,
105            window_size,
106        }
107    }
108
109    /// Given a scalar, compute its wNAF representation and return a `Wnaf` object that can perform
110    /// exponentiations with `.base(..)`.
111    pub fn scalar(&mut self, scalar: <<G as CurveProjective>::Scalar as PrimeField>::Repr) -> Wnaf<usize, &mut Vec<G>, &[i64]> {
112        // Compute the appropriate window size for the scalar.
113        let window_size = G::recommended_wnaf_for_scalar(scalar);
114
115        // Compute the wNAF form of the scalar.
116        wnaf_form(&mut self.scalar, scalar, window_size);
117
118        // Return a Wnaf object that mutably borrows the base storage location, but
119        // immutably borrows the computed wNAF form scalar location.
120        Wnaf {
121            base: &mut self.base,
122            scalar: &self.scalar[..],
123            window_size,
124        }
125    }
126}
127
128impl<'a, G: CurveProjective> Wnaf<usize, &'a [G], &'a mut Vec<i64>> {
129    /// Constructs new space for the scalar representation while borrowing
130    /// the computed window table, for sending the window table across threads.
131    pub fn shared(&self) -> Wnaf<usize, &'a [G], Vec<i64>> {
132        Wnaf {
133            base: self.base,
134            scalar: vec![],
135            window_size: self.window_size,
136        }
137    }
138}
139
140impl<'a, G: CurveProjective> Wnaf<usize, &'a mut Vec<G>, &'a [i64]> {
141    /// Constructs new space for the window table while borrowing
142    /// the computed scalar representation, for sending the scalar representation
143    /// across threads.
144    pub fn shared(&self) -> Wnaf<usize, Vec<G>, &'a [i64]> {
145        Wnaf {
146            base: vec![],
147            scalar: self.scalar,
148            window_size: self.window_size,
149        }
150    }
151}
152
153impl<B, S: AsRef<[i64]>> Wnaf<usize, B, S> {
154    /// Performs exponentiation given a base.
155    pub fn base<G: CurveProjective>(&mut self, base: G) -> G
156    where
157        B: AsMut<Vec<G>>,
158    {
159        wnaf_table(self.base.as_mut(), base, self.window_size);
160        wnaf_exp(self.base.as_mut(), self.scalar.as_ref())
161    }
162}
163
164impl<B, S: AsMut<Vec<i64>>> Wnaf<usize, B, S> {
165    /// Performs exponentiation given a scalar.
166    pub fn scalar<G: CurveProjective>(&mut self, scalar: <<G as CurveProjective>::Scalar as PrimeField>::Repr) -> G
167    where
168        B: AsRef<[G]>,
169    {
170        wnaf_form(self.scalar.as_mut(), scalar, self.window_size);
171        wnaf_exp(self.base.as_ref(), self.scalar.as_mut())
172    }
173}
zksync_pairing/wnaf.rs

zksync_pairing/
wnaf.rs
