snarkvm_algorithms/msm/variable_base/
standard.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::{AffineCurve, ProjectiveCurve};
17use snarkvm_fields::{One, PrimeField, Zero};
18use snarkvm_utilities::{BigInteger, cfg_into_iter};
19
20#[cfg(not(feature = "serial"))]
21use rayon::prelude::*;
22
23fn update_buckets<G: AffineCurve>(
24    base: &G,
25    mut scalar: <G::ScalarField as PrimeField>::BigInteger,
26    w_start: usize,
27    c: usize,
28    buckets: &mut [G::Projective],
29) {
30    // We right-shift by w_start, thus getting rid of the lower bits.
31    scalar.divn(w_start as u32);
32
33    // We mod the remaining bits by the window size.
34    let scalar = scalar.as_ref()[0] % (1 << c);
35
36    // If the scalar is non-zero, we update the corresponding bucket.
37    // (Recall that `buckets` doesn't have a zero bucket.)
38    if scalar != 0 {
39        buckets[(scalar - 1) as usize].add_assign_mixed(base);
40    }
41}
42
43fn standard_window<G: AffineCurve>(
44    bases: &[G],
45    scalars: &[<G::ScalarField as PrimeField>::BigInteger],
46    w_start: usize,
47    c: usize,
48) -> (G::Projective, usize) {
49    let mut res = G::Projective::zero();
50    let fr_one = G::ScalarField::one().to_bigint();
51
52    // We only process unit scalars once in the first window.
53    if w_start == 0 {
54        scalars.iter().zip(bases).filter(|(&s, _)| s == fr_one).for_each(|(_, base)| {
55            res.add_assign_mixed(base);
56        });
57    }
58
59    // We don't need the "zero" bucket, so we only have 2^c - 1 buckets
60    let window_size = if (w_start % c) != 0 { w_start % c } else { c };
61    let mut buckets = vec![G::Projective::zero(); (1 << window_size) - 1];
62    scalars
63        .iter()
64        .zip(bases)
65        .filter(|(&s, _)| s > fr_one)
66        .for_each(|(&scalar, base)| update_buckets(base, scalar, w_start, c, &mut buckets));
67    // G::Projective::batch_normalization(&mut buckets);
68
69    for running_sum in buckets.into_iter().rev().scan(G::Projective::zero(), |sum, b| {
70        *sum += b;
71        Some(*sum)
72    }) {
73        res += running_sum;
74    }
75
76    (res, window_size)
77}
78
79pub fn msm<G: AffineCurve>(bases: &[G], scalars: &[<G::ScalarField as PrimeField>::BigInteger]) -> G::Projective {
80    // Determine the bucket size `c` (chosen empirically).
81    let c = match scalars.len() < 32 {
82        true => 1,
83        false => crate::msm::ln_without_floats(scalars.len()) + 2,
84    };
85
86    let num_bits = <G::ScalarField as PrimeField>::size_in_bits();
87
88    // Each window is of size `c`.
89    // We divide up the bits 0..num_bits into windows of size `c`, and
90    // in parallel process each such window.
91    let window_sums: Vec<_> =
92        cfg_into_iter!(0..num_bits).step_by(c).map(|w_start| standard_window(bases, scalars, w_start, c)).collect();
93
94    // We store the sum for the lowest window.
95    let (lowest, window_sums) = window_sums.split_first().unwrap();
96
97    // We're traversing windows from high to low.
98    window_sums.iter().rev().fold(G::Projective::zero(), |mut total, (sum_i, window_size)| {
99        total += sum_i;
100        for _ in 0..*window_size {
101            total.double_in_place();
102        }
103        total
104    }) + lowest.0
105}
snarkvm_algorithms/msm/variable_base/standard.rs

snarkvm_algorithms/msm/variable_base/
standard.rs
