ark_ec/scalar_mul/
mod.rs

1pub mod glv;
2pub mod wnaf;
3
4pub mod variable_base;
5
6use crate::{
7    short_weierstrass::{Affine, Projective, SWCurveConfig},
8    PrimeGroup,
9};
10use ark_ff::{AdditiveGroup, BigInteger, PrimeField, Zero};
11use ark_std::{
12    cfg_iter, cfg_iter_mut,
13    ops::{Add, AddAssign, Mul, Neg, Sub, SubAssign},
14    vec::*,
15};
16
17#[cfg(feature = "parallel")]
18use rayon::prelude::*;
19
20/// The result of this function is only approximately `ln(a)`
21/// [`Explanation of usage`]
22///
23/// [`Explanation of usage`]: https://github.com/scipr-lab/zexe/issues/79#issue-556220473
24fn ln_without_floats(a: usize) -> usize {
25    // log2(a) * ln(2)
26    (ark_std::log2(a) * 69 / 100) as usize
27}
28
29/// Standard double-and-add method for multiplication by a scalar.
30#[inline(always)]
31pub fn sw_double_and_add_affine<P: SWCurveConfig>(
32    base: &Affine<P>,
33    scalar: impl AsRef<[u64]>,
34) -> Projective<P> {
35    let mut res = Projective::<P>::zero();
36    for b in ark_ff::BitIteratorBE::without_leading_zeros(scalar) {
37        res.double_in_place();
38        if b {
39            res += base
40        }
41    }
42
43    res
44}
45
46/// Standard double-and-add method for multiplication by a scalar.
47#[inline(always)]
48pub fn sw_double_and_add_projective<P: SWCurveConfig>(
49    base: &Projective<P>,
50    scalar: impl AsRef<[u64]>,
51) -> Projective<P> {
52    let mut res = Projective::<P>::zero();
53    for b in ark_ff::BitIteratorBE::without_leading_zeros(scalar) {
54        res.double_in_place();
55        if b {
56            res += base
57        }
58    }
59
60    res
61}
62
63pub trait ScalarMul:
64    PrimeGroup
65    + Add<Self::MulBase, Output = Self>
66    + AddAssign<Self::MulBase>
67    + for<'a> Add<&'a Self::MulBase, Output = Self>
68    + for<'a> AddAssign<&'a Self::MulBase>
69    + Sub<Self::MulBase, Output = Self>
70    + SubAssign<Self::MulBase>
71    + for<'a> Sub<&'a Self::MulBase, Output = Self>
72    + for<'a> SubAssign<&'a Self::MulBase>
73    + From<Self::MulBase>
74{
75    type MulBase: Send
76        + Sync
77        + Copy
78        + Eq
79        + core::hash::Hash
80        + Mul<Self::ScalarField, Output = Self>
81        + for<'a> Mul<&'a Self::ScalarField, Output = Self>
82        + Neg<Output = Self::MulBase>
83        + From<Self>;
84
85    const NEGATION_IS_CHEAP: bool;
86
87    fn batch_convert_to_mul_base(bases: &[Self]) -> Vec<Self::MulBase>;
88
89    /// Compute the vector v[0].G, v[1].G, ..., v[n-1].G, given:
90    /// - an element `g`
91    /// - a list `v` of n scalars
92    ///
93    /// # Example
94    /// ```
95    /// use ark_std::{One, UniformRand};
96    /// use ark_ec::pairing::Pairing;
97    /// use ark_test_curves::bls12_381::G1Projective as G;
98    /// use ark_test_curves::bls12_381::Fr;
99    /// use ark_ec::scalar_mul::ScalarMul;
100    ///
101    /// // Compute G, s.G, s^2.G, ..., s^9.G
102    /// let mut rng = ark_std::test_rng();
103    /// let max_degree = 10;
104    /// let s = Fr::rand(&mut rng);
105    /// let g = G::rand(&mut rng);
106    /// let mut powers_of_s = vec![Fr::one()];
107    /// let mut cur = s;
108    /// for _ in 0..max_degree {
109    ///     powers_of_s.push(cur);
110    ///     cur *= &s;
111    /// }
112    /// let powers_of_g = g.batch_mul(&powers_of_s);
113    /// let naive_powers_of_g: Vec<G> = powers_of_s.iter().map(|e| g * e).collect();
114    /// assert_eq!(powers_of_g, naive_powers_of_g);
115    /// ```
116    fn batch_mul(self, v: &[Self::ScalarField]) -> Vec<Self::MulBase> {
117        let table = BatchMulPreprocessing::new(self, v.len());
118        Self::batch_mul_with_preprocessing(&table, v)
119    }
120
121    /// Compute the vector v[0].G, v[1].G, ..., v[n-1].G, given:
122    /// - an element `g`
123    /// - a list `v` of n scalars
124    ///
125    /// This method allows the user to provide a precomputed table of multiples of `g`.
126    /// A more ergonomic way to call this would be to use [`BatchMulPreprocessing::batch_mul`].
127    ///
128    /// # Example
129    /// ```
130    /// use ark_std::{One, UniformRand};
131    /// use ark_ec::pairing::Pairing;
132    /// use ark_test_curves::bls12_381::G1Projective as G;
133    /// use ark_test_curves::bls12_381::Fr;
134    /// use ark_ec::scalar_mul::*;
135    ///
136    /// // Compute G, s.G, s^2.G, ..., s^9.G
137    /// let mut rng = ark_std::test_rng();
138    /// let max_degree = 10;
139    /// let s = Fr::rand(&mut rng);
140    /// let g = G::rand(&mut rng);
141    /// let mut powers_of_s = vec![Fr::one()];
142    /// let mut cur = s;
143    /// for _ in 0..max_degree {
144    ///     powers_of_s.push(cur);
145    ///     cur *= &s;
146    /// }
147    /// let table = BatchMulPreprocessing::new(g, powers_of_s.len());
148    /// let powers_of_g = G::batch_mul_with_preprocessing(&table, &powers_of_s);
149    /// let powers_of_g_2 = table.batch_mul(&powers_of_s);
150    /// let naive_powers_of_g: Vec<G> = powers_of_s.iter().map(|e| g * e).collect();
151    /// assert_eq!(powers_of_g, naive_powers_of_g);
152    /// assert_eq!(powers_of_g_2, naive_powers_of_g);
153    /// ```
154    fn batch_mul_with_preprocessing(
155        table: &BatchMulPreprocessing<Self>,
156        v: &[Self::ScalarField],
157    ) -> Vec<Self::MulBase> {
158        table.batch_mul(v)
159    }
160}
161
162/// Preprocessing used internally for batch scalar multiplication via [`ScalarMul::batch_mul`].
163/// - `window` is the window size used for the precomputation
164/// - `max_scalar_size` is the maximum size of the scalars that will be multiplied
165/// - `table` is the precomputed table of multiples of `base`
166pub struct BatchMulPreprocessing<T: ScalarMul> {
167    pub window: usize,
168    pub max_scalar_size: usize,
169    pub table: Vec<Vec<T::MulBase>>,
170}
171
172impl<T: ScalarMul> BatchMulPreprocessing<T> {
173    pub fn new(base: T, num_scalars: usize) -> Self {
174        let scalar_size = T::ScalarField::MODULUS_BIT_SIZE as usize;
175        Self::with_num_scalars_and_scalar_size(base, num_scalars, scalar_size)
176    }
177
178    pub fn with_num_scalars_and_scalar_size(
179        base: T,
180        num_scalars: usize,
181        max_scalar_size: usize,
182    ) -> Self {
183        let window = Self::compute_window_size(num_scalars);
184        let in_window = 1 << window;
185        let outerc = (max_scalar_size + window - 1) / window;
186        let last_in_window = 1 << (max_scalar_size - (outerc - 1) * window);
187
188        let mut multiples_of_g = vec![vec![T::zero(); in_window]; outerc];
189
190        let mut g_outer = base;
191        let mut g_outers = Vec::with_capacity(outerc);
192        for _ in 0..outerc {
193            g_outers.push(g_outer);
194            for _ in 0..window {
195                g_outer.double_in_place();
196            }
197        }
198        cfg_iter_mut!(multiples_of_g)
199            .enumerate()
200            .take(outerc)
201            .zip(g_outers)
202            .for_each(|((outer, multiples_of_g), g_outer)| {
203                let cur_in_window = if outer == outerc - 1 {
204                    last_in_window
205                } else {
206                    in_window
207                };
208
209                let mut g_inner = T::zero();
210                for inner in multiples_of_g.iter_mut().take(cur_in_window) {
211                    *inner = g_inner;
212                    g_inner += &g_outer;
213                }
214            });
215        let table = cfg_iter!(multiples_of_g)
216            .map(|s| T::batch_convert_to_mul_base(s))
217            .collect();
218        Self {
219            window,
220            max_scalar_size,
221            table,
222        }
223    }
224
225    pub fn compute_window_size(num_scalars: usize) -> usize {
226        if num_scalars < 32 {
227            3
228        } else {
229            ln_without_floats(num_scalars)
230        }
231    }
232
233    pub fn batch_mul(&self, v: &[T::ScalarField]) -> Vec<T::MulBase> {
234        let result: Vec<_> = cfg_iter!(v).map(|e| self.windowed_mul(e)).collect();
235        T::batch_convert_to_mul_base(&result)
236    }
237
238    fn windowed_mul(&self, scalar: &T::ScalarField) -> T {
239        let outerc = (self.max_scalar_size + self.window - 1) / self.window;
240        let modulus_size = T::ScalarField::MODULUS_BIT_SIZE as usize;
241        let scalar_val = scalar.into_bigint().to_bits_le();
242
243        let mut res = T::from(self.table[0][0]);
244        for outer in 0..outerc {
245            let mut inner = 0usize;
246            for i in 0..self.window {
247                if outer * self.window + i < modulus_size && scalar_val[outer * self.window + i] {
248                    inner |= 1 << i;
249                }
250            }
251            res += &self.table[outer][inner];
252        }
253        res
254    }
255}
ark_ec/scalar_mul/mod.rs

ark_ec/scalar_mul/
mod.rs
