monero_bulletproofs/
core.rs

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

monero_bulletproofs/
core.rs
