1use alloc::vec::Vec;
  2use core::ops::Mul;
  3
  4use plonky2::field::types::{Field, PrimeField};
  5
  6use crate::curve::curve_types::{Curve, CurveScalar, ProjectivePoint};
  7
  8const WINDOW_BITS: usize = 4;
  9const BASE: usize = 1 << WINDOW_BITS;
 10
 11fn digits_per_scalar<C: Curve>() -> usize {
 12    (C::ScalarField::BITS + WINDOW_BITS - 1) / WINDOW_BITS
 13}
 14
 15/// Precomputed state used for scalar x ProjectivePoint multiplications,
 16/// specific to a particular generator.
 17#[derive(Clone)]
 18pub struct MultiplicationPrecomputation<C: Curve> {
 19    /// [(2^w)^i] g for each i < digits_per_scalar.
 20    powers: Vec<ProjectivePoint<C>>,
 21}
 22
 23impl<C: Curve> ProjectivePoint<C> {
 24    pub fn mul_precompute(&self) -> MultiplicationPrecomputation<C> {
 25        let num_digits = digits_per_scalar::<C>();
 26        let mut powers = Vec::with_capacity(num_digits);
 27        powers.push(*self);
 28        for i in 1..num_digits {
 29            let mut power_i = powers[i - 1];
 30            for _j in 0..WINDOW_BITS {
 31                power_i = power_i.double();
 32            }
 33            powers.push(power_i);
 34        }
 35
 36        MultiplicationPrecomputation { powers }
 37    }
 38
 39    #[must_use]
 40    pub fn mul_with_precomputation(
 41        &self,
 42        scalar: C::ScalarField,
 43        precomputation: MultiplicationPrecomputation<C>,
 44    ) -> Self {
 45        // Yao's method; see https://koclab.cs.ucsb.edu/teaching/ecc/eccPapers/Doche-ch09.pdf
 46        let precomputed_powers = precomputation.powers;
 47
 48        let digits = to_digits::<C>(&scalar);
 49
 50        let mut y = ProjectivePoint::ZERO;
 51        let mut u = ProjectivePoint::ZERO;
 52        let mut all_summands = Vec::new();
 53        for j in (1..BASE).rev() {
 54            let mut u_summands = Vec::new();
 55            for (i, &digit) in digits.iter().enumerate() {
 56                if digit == j as u64 {
 57                    u_summands.push(precomputed_powers[i]);
 58                }
 59            }
 60            all_summands.push(u_summands);
 61        }
 62
 63        let all_sums: Vec<ProjectivePoint<C>> = all_summands
 64            .iter()
 65            .cloned()
 66            .map(|vec| vec.iter().fold(ProjectivePoint::ZERO, |a, &b| a + b))
 67            .collect();
 68        for i in 0..all_sums.len() {
 69            u = u + all_sums[i];
 70            y = y + u;
 71        }
 72        y
 73    }
 74}
 75
 76impl<C: Curve> Mul<ProjectivePoint<C>> for CurveScalar<C> {
 77    type Output = ProjectivePoint<C>;
 78
 79    fn mul(self, rhs: ProjectivePoint<C>) -> Self::Output {
 80        let precomputation = rhs.mul_precompute();
 81        rhs.mul_with_precomputation(self.0, precomputation)
 82    }
 83}
 84
 85#[allow(clippy::assertions_on_constants)]
 86fn to_digits<C: Curve>(x: &C::ScalarField) -> Vec<u64> {
 87    debug_assert!(
 88        64 % WINDOW_BITS == 0,
 89        "For simplicity, only power-of-two window sizes are handled for now"
 90    );
 91    let digits_per_u64 = 64 / WINDOW_BITS;
 92    let mut digits = Vec::with_capacity(digits_per_scalar::<C>());
 93    for limb in x.to_canonical_biguint().to_u64_digits() {
 94        for j in 0..digits_per_u64 {
 95            digits.push((limb >> (j * WINDOW_BITS) as u64) % BASE as u64);
 96        }
 97    }
 98
 99    digits
100}