monero_bulletproofs/original/

mod.rs

#![allow(clippy::many_single_char_names)]

use std_shims::{sync::LazyLock, vec::Vec};

use rand_core::{RngCore, CryptoRng};

use zeroize::Zeroize;

use curve25519_dalek::{constants::ED25519_BASEPOINT_POINT, Scalar, EdwardsPoint};

use monero_ed25519::{CompressedPoint, Commitment};
use monero_bulletproofs_generators::{Generators, COMMITMENT_BITS};

use crate::{
  core::{MAX_COMMITMENTS, multiexp},
  scalar_vector::ScalarVector,
  MONERO_H, BulletproofsBatchVerifier,
};

pub(crate) mod inner_product;
use inner_product::*;
pub(crate) use inner_product::IpProof;

include!(concat!(env!("OUT_DIR"), "/generators.rs"));

const INV_EIGHT: monero_ed25519::Scalar = monero_ed25519::Scalar::INV_EIGHT;

#[derive(Clone, Debug)]
pub(crate) struct AggregateRangeStatement<'a> {
  commitments: &'a [EdwardsPoint],
}

#[derive(Clone)]
pub(crate) struct AggregateRangeWitness {
  commitments: Vec<Commitment>,
}

/// Internal structure representing a Bulletproof, as defined by Monero.
#[doc(hidden)]
#[derive(Clone, PartialEq, Eq, Debug, Zeroize)]
pub struct AggregateRangeProof {
  pub(crate) A: CompressedPoint,
  pub(crate) S: CompressedPoint,
  pub(crate) T1: CompressedPoint,
  pub(crate) T2: CompressedPoint,
  pub(crate) tau_x: Scalar,
  pub(crate) mu: Scalar,
  pub(crate) t_hat: Scalar,
  pub(crate) ip: IpProof,
}

impl<'a> AggregateRangeStatement<'a> {
  pub(crate) fn new(commitments: &'a [EdwardsPoint]) -> Option<Self> {
    if commitments.is_empty() || (commitments.len() > MAX_COMMITMENTS) {
      None?;
    }
    Some(Self { commitments })
  }
}

impl AggregateRangeWitness {
  pub(crate) fn new(commitments: Vec<Commitment>) -> Option<Self> {
    if commitments.is_empty() || (commitments.len() > MAX_COMMITMENTS) {
      None?;
    }
    Some(Self { commitments })
  }
}

impl AggregateRangeStatement<'_> {
  fn initial_transcript(&self) -> (Scalar, Vec<EdwardsPoint>) {
    let V = self.commitments.iter().map(|c| c * INV_EIGHT.into()).collect::<Vec<_>>();
    (
      monero_ed25519::Scalar::hash(
        V.iter().flat_map(|V| V.compress().to_bytes()).collect::<Vec<_>>(),
      )
      .into(),
      V,
    )
  }

  fn transcript_A_S(
    transcript: Scalar,
    A: CompressedPoint,
    S: CompressedPoint,
  ) -> (Scalar, Scalar) {
    let mut buf = Vec::with_capacity(96);
    buf.extend(transcript.to_bytes());
    buf.extend(A.to_bytes());
    buf.extend(S.to_bytes());
    let y = monero_ed25519::Scalar::hash(buf).into();
    let z = monero_ed25519::Scalar::hash(y.to_bytes()).into();
    (y, z)
  }

  fn transcript_T12(transcript: Scalar, T1: CompressedPoint, T2: CompressedPoint) -> Scalar {
    let mut buf = Vec::with_capacity(128);
    buf.extend(transcript.to_bytes());
    buf.extend(transcript.to_bytes());
    buf.extend(T1.to_bytes());
    buf.extend(T2.to_bytes());
    monero_ed25519::Scalar::hash(buf).into()
  }

  fn transcript_tau_x_mu_t_hat(
    transcript: Scalar,
    tau_x: Scalar,
    mu: Scalar,
    t_hat: Scalar,
  ) -> Scalar {
    let mut buf = Vec::with_capacity(128);
    buf.extend(transcript.to_bytes());
    buf.extend(transcript.to_bytes());
    buf.extend(tau_x.to_bytes());
    buf.extend(mu.to_bytes());
    buf.extend(t_hat.to_bytes());
    monero_ed25519::Scalar::hash(buf).into()
  }

  #[allow(clippy::needless_pass_by_value)]
  pub(crate) fn prove(
    self,
    rng: &mut (impl RngCore + CryptoRng),
    witness: AggregateRangeWitness,
  ) -> Option<AggregateRangeProof> {
    if self.commitments !=
      witness.commitments.iter().map(|commitment| commitment.commit().into()).collect::<Vec<_>>()
    {
      None?;
    }

    let generators = &GENERATORS;

    let (mut transcript, _) = self.initial_transcript();

    // Find out the padded amount of commitments
    let mut padded_pow_of_2 = 1;
    while padded_pow_of_2 < witness.commitments.len() {
      padded_pow_of_2 <<= 1;
    }

    let mut aL = ScalarVector::new(padded_pow_of_2 * COMMITMENT_BITS);
    for (i, commitment) in witness.commitments.iter().enumerate() {
      let mut amount = commitment.amount;
      for j in 0 .. COMMITMENT_BITS {
        aL[(i * COMMITMENT_BITS) + j] = Scalar::from(amount & 1);
        amount >>= 1;
      }
    }
    let aR = aL.clone() - Scalar::ONE;

    let alpha = monero_ed25519::Scalar::random(&mut *rng).into();

    let A = CompressedPoint::from(
      {
        let mut terms = Vec::with_capacity(1 + (2 * aL.len()));
        terms.push((alpha, ED25519_BASEPOINT_POINT));
        for (aL, G) in aL.0.iter().zip(&generators.G) {
          terms.push((*aL, *G));
        }
        for (aR, H) in aR.0.iter().zip(&generators.H) {
          terms.push((*aR, *H));
        }
        let res = multiexp(&terms) * INV_EIGHT.into();
        terms.zeroize();
        res
      }
      .compress()
      .to_bytes(),
    );

    let mut sL = ScalarVector::new(padded_pow_of_2 * COMMITMENT_BITS);
    let mut sR = ScalarVector::new(padded_pow_of_2 * COMMITMENT_BITS);
    for i in 0 .. (padded_pow_of_2 * COMMITMENT_BITS) {
      sL[i] = monero_ed25519::Scalar::random(&mut *rng).into();
      sR[i] = monero_ed25519::Scalar::random(&mut *rng).into();
    }
    let rho = monero_ed25519::Scalar::random(&mut *rng).into();

    let S = CompressedPoint::from(
      {
        let mut terms = Vec::with_capacity(1 + (2 * sL.len()));
        terms.push((rho, ED25519_BASEPOINT_POINT));
        for (sL, G) in sL.0.iter().zip(&generators.G) {
          terms.push((*sL, *G));
        }
        for (sR, H) in sR.0.iter().zip(&generators.H) {
          terms.push((*sR, *H));
        }
        let res = multiexp(&terms) * INV_EIGHT.into();
        terms.zeroize();
        res
      }
      .compress()
      .to_bytes(),
    );

    let (y, z) = Self::transcript_A_S(transcript, A, S);
    transcript = z;
    let z = ScalarVector::powers(z, 3 + padded_pow_of_2);

    let twos = ScalarVector::powers(Scalar::from(2u8), COMMITMENT_BITS);

    let l = [aL - z[1], sL];
    let y_pow_n = ScalarVector::powers(y, aR.len());
    let mut r = [((aR + z[1]) * &y_pow_n), sR * &y_pow_n];
    {
      for j in 0 .. padded_pow_of_2 {
        for i in 0 .. COMMITMENT_BITS {
          r[0].0[(j * COMMITMENT_BITS) + i] += z[2 + j] * twos[i];
        }
      }
    }
    let t1 = (l[0].clone().inner_product(&r[1])) + (r[0].clone().inner_product(&l[1]));
    let t2 = l[1].clone().inner_product(&r[1]);

    let tau_1 = monero_ed25519::Scalar::random(&mut *rng).into();
    let T1 = CompressedPoint::from(
      {
        let mut T1_terms = [(t1, *MONERO_H), (tau_1, ED25519_BASEPOINT_POINT)];
        for term in &mut T1_terms {
          term.0 *= INV_EIGHT.into();
        }
        let T1 = multiexp(&T1_terms);
        T1_terms.zeroize();
        T1
      }
      .compress()
      .to_bytes(),
    );
    let tau_2 = monero_ed25519::Scalar::random(&mut *rng).into();
    let T2 = CompressedPoint::from(
      {
        let mut T2_terms = [(t2, *MONERO_H), (tau_2, ED25519_BASEPOINT_POINT)];
        for term in &mut T2_terms {
          term.0 *= INV_EIGHT.into();
        }
        let T2 = multiexp(&T2_terms);
        T2_terms.zeroize();
        T2
      }
      .compress()
      .to_bytes(),
    );

    transcript = Self::transcript_T12(transcript, T1, T2);
    let x = transcript;

    let [l0, l1] = l;
    let l = l0 + &(l1 * x);
    let [r0, r1] = r;
    let r = r0 + &(r1 * x);
    let t_hat = l.clone().inner_product(&r);
    let mut tau_x = ((tau_2 * x) + tau_1) * x;
    {
      for (i, commitment) in witness.commitments.iter().enumerate() {
        tau_x += z[2 + i] * commitment.mask.into();
      }
    }
    let mu = alpha + (rho * x);

    let y_inv_pow_n = ScalarVector::powers(y.invert(), l.len());

    transcript = Self::transcript_tau_x_mu_t_hat(transcript, tau_x, mu, t_hat);
    let x_ip = transcript;

    let ip = IpStatement::new_without_P_transcript(y_inv_pow_n, x_ip)
      .prove(
        transcript,
        IpWitness::new(l, r).expect("Bulletproofs::Original created an invalid IpWitness"),
      )
      .expect("Bulletproofs::Original failed to prove the inner-product");

    let res = AggregateRangeProof { A, S, T1, T2, tau_x, mu, t_hat, ip };
    #[cfg(debug_assertions)]
    {
      let mut verifier = BulletproofsBatchVerifier::default();
      debug_assert!(self.verify(rng, &mut verifier, res.clone()));
      debug_assert!(verifier.verify());
    }
    Some(res)
  }

  #[must_use]
  pub(crate) fn verify(
    self,
    rng: &mut (impl RngCore + CryptoRng),
    verifier: &mut BulletproofsBatchVerifier,
    AggregateRangeProof { A, S, T1, T2, tau_x, mu, t_hat, ip }: AggregateRangeProof,
  ) -> bool {
    let mut padded_pow_of_2 = 1;
    while padded_pow_of_2 < self.commitments.len() {
      padded_pow_of_2 <<= 1;
    }
    let ip_rows = padded_pow_of_2 * COMMITMENT_BITS;

    while verifier.0.g_bold.len() < ip_rows {
      verifier.0.g_bold.push(Scalar::ZERO);
      verifier.0.h_bold.push(Scalar::ZERO);
    }

    let (mut transcript, mut commitments) = self.initial_transcript();
    for commitment in &mut commitments {
      *commitment = commitment.mul_by_cofactor();
    }

    let (y, z) = Self::transcript_A_S(transcript, A, S);
    transcript = z;
    let z = ScalarVector::powers(z, 3 + padded_pow_of_2);
    transcript = Self::transcript_T12(transcript, T1, T2);
    let x = transcript;
    transcript = Self::transcript_tau_x_mu_t_hat(transcript, tau_x, mu, t_hat);
    let x_ip = transcript;

    let decomp_mul_cofactor =
      |p| CompressedPoint::decompress(&p).map(|p| EdwardsPoint::mul_by_cofactor(&p.into()));

    let (Some(A), Some(S), Some(T1), Some(T2)) = (
      decomp_mul_cofactor(A),
      decomp_mul_cofactor(S),
      decomp_mul_cofactor(T1),
      decomp_mul_cofactor(T2),
    ) else {
      return false;
    };

    let y_pow_n = ScalarVector::powers(y, ip_rows);
    let y_inv_pow_n = ScalarVector::powers(y.invert(), ip_rows);

    let twos = ScalarVector::powers(Scalar::from(2u8), COMMITMENT_BITS);

    // 65
    {
      let weight = monero_ed25519::Scalar::random(&mut *rng).into();
      verifier.0.h += weight * t_hat;
      verifier.0.g += weight * tau_x;

      // Now that we've accumulated the lhs, negate the weight and accumulate the rhs
      // These will now sum to 0 if equal
      let weight = -weight;

      verifier.0.h += weight * (z[1] - (z[2])) * y_pow_n.sum();

      for (i, commitment) in commitments.iter().enumerate() {
        verifier.0.other.push((weight * z[2 + i], *commitment));
      }

      for i in 0 .. padded_pow_of_2 {
        verifier.0.h -= weight * z[3 + i] * twos.clone().sum();
      }
      verifier.0.other.push((weight * x, T1));
      verifier.0.other.push((weight * (x * x), T2));
    }

    let ip_weight = monero_ed25519::Scalar::random(&mut *rng).into();

    // 66
    verifier.0.other.push((ip_weight, A));
    verifier.0.other.push((ip_weight * x, S));
    // We can replace these with a g_sum, h_sum scalar in the batch verifier
    // It'd trade `2 * ip_rows` scalar additions (per proof) for one scalar addition and an
    // additional term in the MSM
    let ip_z = ip_weight * z[1];
    for i in 0 .. ip_rows {
      verifier.0.h_bold[i] += ip_z;
    }
    let neg_ip_z = -ip_z;
    for i in 0 .. ip_rows {
      verifier.0.g_bold[i] += neg_ip_z;
    }
    {
      for j in 0 .. padded_pow_of_2 {
        for i in 0 .. COMMITMENT_BITS {
          let full_i = (j * COMMITMENT_BITS) + i;
          verifier.0.h_bold[full_i] += ip_weight * y_inv_pow_n[full_i] * z[2 + j] * twos[i];
        }
      }
    }
    verifier.0.h += ip_weight * x_ip * t_hat;

    // 67, 68
    verifier.0.g += ip_weight * -mu;
    let res = IpStatement::new_without_P_transcript(y_inv_pow_n, x_ip)
      .verify(verifier, ip_rows, transcript, ip_weight, ip);
    res.is_ok()
  }
}