monero_bulletproofs/
core.rs

1use std_shims::{vec, vec::Vec};
2
3use curve25519_dalek::{
4  traits::{MultiscalarMul, VartimeMultiscalarMul},
5  scalar::Scalar,
6  edwards::EdwardsPoint,
7};
8
9pub(crate) use monero_generators::{MAX_COMMITMENTS, COMMITMENT_BITS, LOG_COMMITMENT_BITS};
10
11pub(crate) fn multiexp(pairs: &[(Scalar, EdwardsPoint)]) -> EdwardsPoint {
12  let mut buf_scalars = Vec::with_capacity(pairs.len());
13  let mut buf_points = Vec::with_capacity(pairs.len());
14  for (scalar, point) in pairs {
15    buf_scalars.push(scalar);
16    buf_points.push(point);
17  }
18  EdwardsPoint::multiscalar_mul(buf_scalars, buf_points)
19}
20
21pub(crate) fn multiexp_vartime(pairs: &[(Scalar, EdwardsPoint)]) -> EdwardsPoint {
22  let mut buf_scalars = Vec::with_capacity(pairs.len());
23  let mut buf_points = Vec::with_capacity(pairs.len());
24  for (scalar, point) in pairs {
25    buf_scalars.push(scalar);
26    buf_points.push(point);
27  }
28  EdwardsPoint::vartime_multiscalar_mul(buf_scalars, buf_points)
29}
30
31/*
32This has room for optimization worth investigating further. It currently takes
33an iterative approach. It can be optimized further via divide and conquer.
34
35Assume there are 4 challenges.
36
37Iterative approach (current):
38  1. Do the optimal multiplications across challenge column 0 and 1.
39  2. Do the optimal multiplications across that result and column 2.
40  3. Do the optimal multiplications across that result and column 3.
41
42Divide and conquer (worth investigating further):
43  1. Do the optimal multiplications across challenge column 0 and 1.
44  2. Do the optimal multiplications across challenge column 2 and 3.
45  3. Multiply both results together.
46
47When there are 4 challenges (n=16), the iterative approach does 28 multiplications
48versus divide and conquer's 24.
49*/
50pub(crate) fn challenge_products(challenges: &[(Scalar, Scalar)]) -> Vec<Scalar> {
51  let mut products = vec![Scalar::ONE; 1 << challenges.len()];
52
53  if !challenges.is_empty() {
54    products[0] = challenges[0].1;
55    products[1] = challenges[0].0;
56
57    for (j, challenge) in challenges.iter().enumerate().skip(1) {
58      let mut slots = (1 << (j + 1)) - 1;
59      while slots > 0 {
60        products[slots] = products[slots / 2] * challenge.0;
61        products[slots - 1] = products[slots / 2] * challenge.1;
62
63        slots = slots.saturating_sub(2);
64      }
65    }
66
67    // Sanity check since if the above failed to populate, it'd be critical
68    for product in &products {
69      debug_assert!(*product != Scalar::ZERO);
70    }
71  }
72
73  products
74}