snarkvm_algorithms/msm/
fixed_base.rs

1// Copyright 2024 Aleo Network Foundation
2// This file is part of the snarkVM library.
3
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at:
7
8// http://www.apache.org/licenses/LICENSE-2.0
9
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16use snarkvm_curves::traits::ProjectiveCurve;
17use snarkvm_fields::{FieldParameters, PrimeField};
18use snarkvm_utilities::{ToBits, cfg_into_iter, cfg_iter, cfg_iter_mut};
19
20#[cfg(not(feature = "serial"))]
21use rayon::prelude::*;
22
23pub struct FixedBase;
24
25impl FixedBase {
26    pub fn get_mul_window_size(num_scalars: usize) -> usize {
27        match num_scalars < 32 {
28            true => 3,
29            false => super::ln_without_floats(num_scalars),
30        }
31    }
32
33    pub fn get_window_table<T: ProjectiveCurve>(scalar_size: usize, window: usize, g: T) -> Vec<Vec<T>> {
34        let in_window = 1 << window;
35        let outerc = scalar_size.div_ceil(window);
36        let last_in_window = 1 << (scalar_size - (outerc - 1) * window);
37
38        let mut multiples_of_g = vec![vec![T::zero(); in_window]; outerc];
39
40        let mut g_outer = g;
41        let mut g_outers = Vec::with_capacity(outerc);
42        for _ in 0..outerc {
43            g_outers.push(g_outer);
44            for _ in 0..window {
45                g_outer.double_in_place();
46            }
47        }
48
49        cfg_iter_mut!(multiples_of_g).enumerate().take(outerc).zip(g_outers).for_each(
50            |((outer, multiples_of_g), g_outer)| {
51                let cur_in_window = if outer == outerc - 1 { last_in_window } else { in_window };
52
53                let mut g_inner = T::zero();
54                for inner in multiples_of_g.iter_mut().take(cur_in_window) {
55                    *inner = g_inner;
56                    g_inner += &g_outer;
57                }
58            },
59        );
60        multiples_of_g
61    }
62
63    pub fn windowed_mul<T: ProjectiveCurve>(
64        outerc: usize,
65        window: usize,
66        multiples_of_g: &[Vec<T>],
67        scalar: &T::ScalarField,
68    ) -> T {
69        let scalar_val = scalar.to_bigint().to_bits_le();
70
71        cfg_into_iter!(0..outerc)
72            .map(|outer| {
73                let mut inner = 0usize;
74                for i in 0..window {
75                    if outer * window + i < (<T::ScalarField as PrimeField>::Parameters::MODULUS_BITS as usize)
76                        && scalar_val[outer * window + i]
77                    {
78                        inner |= 1 << i;
79                    }
80                }
81                multiples_of_g[outer][inner]
82            })
83            .sum::<T>()
84            + multiples_of_g[0][0]
85    }
86
87    pub fn msm<T: ProjectiveCurve>(
88        scalar_size: usize,
89        window: usize,
90        table: &[Vec<T>],
91        v: &[T::ScalarField],
92    ) -> Vec<T> {
93        let outerc = scalar_size.div_ceil(window);
94        assert!(outerc <= table.len());
95
96        cfg_iter!(v).map(|e| Self::windowed_mul::<T>(outerc, window, table, e)).collect::<Vec<_>>()
97    }
98}
snarkvm_algorithms/msm/fixed_base.rs

snarkvm_algorithms/msm/
fixed_base.rs
