1  // Copyright (c) 2025-2026 ACDC Network
  2  // This file is part of the alphavm library.
  3  //
  4  // Alpha Chain | Delta Chain Protocol
  5  // International Monetary Graphite.
  6  //
  7  // Derived from Aleo (https://aleo.org) and ProvableHQ (https://provable.com).
  8  // They built world-class ZK infrastructure. We installed the EASY button.
  9  // Their cryptography: elegant. Our modifications: bureaucracy-compatible.
 10  // Original brilliance: theirs. Robert's Rules: ours. Bugs: definitely ours.
 11  //
 12  // Original Aleo/ProvableHQ code subject to Apache 2.0 https://www.apache.org/licenses/LICENSE-2.0
 13  // All modifications and new work: CC0 1.0 Universal Public Domain Dedication.
 14  // No rights reserved. No permission required. No warranty. No refunds.
 15  //
 16  // https://creativecommons.org/publicdomain/zero/1.0/
 17  // SPDX-License-Identifier: CC0-1.0
 18  
 19  pub mod batched;
 20  pub mod standard;
 21  
 22  #[cfg(target_arch = "x86_64")]
 23  pub mod prefetch;
 24  
 25  use alphavm_curves::{bls12_377::G1Affine, traits::AffineCurve};
 26  use alphavm_fields::PrimeField;
 27  
 28  use core::any::TypeId;
 29  
 30  pub struct VariableBase;
 31  
 32  impl VariableBase {
 33      pub fn msm<G: AffineCurve>(bases: &[G], scalars: &[<G::ScalarField as PrimeField>::BigInteger]) -> G::Projective {
 34          // For BLS12-377, we perform variable base MSM using a batched addition
 35          // technique.
 36          if TypeId::of::<G>() == TypeId::of::<G1Affine>() {
 37              #[cfg(all(feature = "cuda", target_arch = "x86_64"))]
 38              // TODO SNP: where to set the threshold
 39              if scalars.len() > 1024 {
 40                  let result = alphavm_algorithms_cuda::msm::<G, G::Projective, <G::ScalarField as PrimeField>::BigInteger>(
 41                      bases, scalars,
 42                  );
 43                  if let Ok(result) = result {
 44                      return result;
 45                  }
 46              }
 47              batched::msm(bases, scalars)
 48          }
 49          // For all other curves, we perform variable base MSM using Pippenger's algorithm.
 50          else {
 51              standard::msm(bases, scalars)
 52          }
 53      }
 54  
 55      #[cfg(test)]
 56      fn msm_naive<G: AffineCurve>(bases: &[G], scalars: &[<G::ScalarField as PrimeField>::BigInteger]) -> G::Projective {
 57          use alphavm_utilities::BitIteratorBE;
 58          use itertools::Itertools;
 59  
 60          bases.iter().zip_eq(scalars).map(|(base, scalar)| base.mul_bits(BitIteratorBE::new(*scalar))).sum()
 61      }
 62  
 63      #[cfg(test)]
 64      fn msm_naive_parallel<G: AffineCurve>(
 65          bases: &[G],
 66          scalars: &[<G::ScalarField as PrimeField>::BigInteger],
 67      ) -> G::Projective {
 68          use alphavm_utilities::BitIteratorBE;
 69          use rayon::prelude::*;
 70  
 71          bases.par_iter().zip_eq(scalars).map(|(base, scalar)| base.mul_bits(BitIteratorBE::new(*scalar))).sum()
 72      }
 73  }
 74  
 75  #[cfg(test)]
 76  mod tests {
 77      use super::*;
 78      use alphavm_curves::bls12_377::{Fr, G1Affine};
 79      use alphavm_fields::PrimeField;
 80      use alphavm_utilities::rand::TestRng;
 81  
 82      #[cfg(all(feature = "cuda", target_arch = "x86_64"))]
 83      use alphavm_curves::ProjectiveCurve;
 84  
 85      fn create_scalar_bases<G: AffineCurve<ScalarField = F>, F: PrimeField>(
 86          rng: &mut TestRng,
 87          size: usize,
 88      ) -> (Vec<G>, Vec<F::BigInteger>) {
 89          let bases = (0..size).map(|_| G::rand(rng)).collect::<Vec<_>>();
 90          let scalars = (0..size).map(|_| F::rand(rng).to_bigint()).collect::<Vec<_>>();
 91          (bases, scalars)
 92      }
 93  
 94      #[test]
 95      fn test_msm() {
 96          use alphavm_curves::ProjectiveCurve;
 97  
 98          let mut rng = TestRng::default();
 99          for msm_size in [1, 5, 10, 50, 100, 500, 1000] {
100              let (bases, scalars) = create_scalar_bases::<G1Affine, Fr>(&mut rng, msm_size);
101  
102              let naive_a = VariableBase::msm_naive(bases.as_slice(), scalars.as_slice()).to_affine();
103              let naive_b = VariableBase::msm_naive_parallel(bases.as_slice(), scalars.as_slice()).to_affine();
104              assert_eq!(naive_a, naive_b, "MSM size: {msm_size}");
105  
106              let candidate = standard::msm(bases.as_slice(), scalars.as_slice()).to_affine();
107              assert_eq!(naive_a, candidate, "MSM size: {msm_size}");
108  
109              let candidate = batched::msm(bases.as_slice(), scalars.as_slice()).to_affine();
110              assert_eq!(naive_a, candidate, "MSM size: {msm_size}");
111          }
112      }
113  
114      #[cfg(all(feature = "cuda", target_arch = "x86_64"))]
115      #[test]
116      fn test_msm_cuda() {
117          let mut rng = TestRng::default();
118          for i in 2..17 {
119              let (bases, scalars) = create_scalar_bases::<G1Affine, Fr>(&mut rng, 1 << i);
120              let rust = standard::msm(bases.as_slice(), scalars.as_slice());
121              let cuda = VariableBase::msm::<G1Affine>(bases.as_slice(), scalars.as_slice());
122              assert_eq!(rust.to_affine(), cuda.to_affine());
123          }
124      }
125  }