monero_bulletproofs/
lib.rs

1#![cfg_attr(docsrs, feature(doc_cfg))]
2#![doc = include_str!("../README.md")]
3#![cfg_attr(not(feature = "std"), no_std)]
4#![allow(non_snake_case)]
5
6use std_shims::{
7  prelude::*,
8  sync::LazyLock,
9  io::{self, Read, Write},
10};
11
12use rand_core::{RngCore, CryptoRng};
13use zeroize::Zeroizing;
14
15use curve25519_dalek::EdwardsPoint;
16
17use monero_io::*;
18use monero_ed25519::*;
19pub use monero_bulletproofs_generators::MAX_BULLETPROOF_COMMITMENTS as MAX_COMMITMENTS;
20use monero_bulletproofs_generators::COMMITMENT_BITS;
21
22pub(crate) mod scalar_vector;
23pub(crate) mod point_vector;
24
25pub(crate) mod core;
26
27pub(crate) mod batch_verifier;
28use batch_verifier::{BulletproofsBatchVerifier, BulletproofsPlusBatchVerifier};
29pub use batch_verifier::BatchVerifier;
30
31pub(crate) mod original;
32use crate::original::{
33  IpProof, AggregateRangeStatement as OriginalStatement, AggregateRangeWitness as OriginalWitness,
34  AggregateRangeProof as OriginalProof,
35};
36
37pub(crate) mod plus;
38use crate::plus::{
39  WipProof, AggregateRangeStatement as PlusStatement, AggregateRangeWitness as PlusWitness,
40  AggregateRangeProof as PlusProof,
41};
42
43#[cfg(test)]
44mod tests;
45
46// The logarithm (over 2) of the amount of bits a value within a commitment may use.
47#[allow(clippy::as_conversions)]
48const LOG_COMMITMENT_BITS: usize = COMMITMENT_BITS.ilog2() as usize;
49// The maximum length of L/R `Vec`s.
50#[allow(clippy::as_conversions)]
51const MAX_LR: usize = (MAX_COMMITMENTS.ilog2() as usize) + LOG_COMMITMENT_BITS;
52
53// A static for `H` as it's frequently used yet this decompression is expensive.
54static MONERO_H: LazyLock<EdwardsPoint> = LazyLock::new(|| {
55  CompressedPoint::H.decompress().expect("couldn't decompress `CompressedPoint::H`").into()
56});
57
58/// An error from proving/verifying Bulletproofs(+).
59#[derive(Clone, Copy, PartialEq, Eq, Debug, thiserror::Error)]
60pub enum BulletproofError {
61  /// Proving/verifying a Bulletproof(+) range proof with no commitments.
62  #[error("no commitments to prove the range for")]
63  NoCommitments,
64  /// Proving/verifying a Bulletproof(+) range proof with more commitments than supported.
65  #[error("too many commitments to prove the range for")]
66  TooManyCommitments,
67}
68
69/// A Bulletproof(+).
70///
71/// This encapsulates either a Bulletproof or a Bulletproof+.
72#[allow(clippy::large_enum_variant)]
73#[derive(Clone, PartialEq, Eq, Debug)]
74pub enum Bulletproof {
75  /// A Bulletproof.
76  Original(OriginalProof),
77  /// A Bulletproof+.
78  Plus(PlusProof),
79}
80
81impl Bulletproof {
82  fn bp_fields(plus: bool) -> usize {
83    if plus {
84      6
85    } else {
86      9
87    }
88  }
89
90  /// Calculate the weight penalty for the Bulletproof(+).
91  ///
92  /// Bulletproofs(+) are logarithmically sized yet linearly timed. Evaluating by their size alone
93  /// accordingly doesn't properly represent the burden of the proof. Monero 'claws back' some of
94  /// the weight lost by using a proof smaller than it is fast to compensate for this.
95  ///
96  /// If the amount of outputs specified exceeds the maximum amount of outputs, the result for the
97  /// maximum amount of outputs will be returned.
98  // https://github.com/monero-project/monero/blob/94e67bf96bbc010241f29ada6abc89f49a81759c/
99  //   src/cryptonote_basic/cryptonote_format_utils.cpp#L106-L124
100  pub fn calculate_clawback(plus: bool, n_outputs: usize) -> (usize, usize) {
101    #[allow(non_snake_case)]
102    let mut LR_len = 0;
103    let mut n_padded_outputs = 1;
104    while n_padded_outputs < n_outputs.min(MAX_COMMITMENTS) {
105      LR_len += 1;
106      n_padded_outputs = 1 << LR_len;
107    }
108    LR_len += LOG_COMMITMENT_BITS;
109
110    let mut clawback = 0;
111    if n_padded_outputs > 2 {
112      let fields = Bulletproof::bp_fields(plus);
113      let base = ((fields + (2 * (LOG_COMMITMENT_BITS + 1))) * 32) / 2;
114      let size = (fields + (2 * LR_len)) * 32;
115      clawback = ((base * n_padded_outputs) - size) * 4 / 5;
116    }
117
118    (clawback, LR_len)
119  }
120
121  /// Prove the list of commitments are within [0 .. 2^64) with an aggregate Bulletproof.
122  ///
123  /// This function runs in time variable to the validity of the arguments and the public data.
124  pub fn prove<R: RngCore + CryptoRng>(
125    rng: &mut R,
126    outputs: Vec<Commitment>,
127  ) -> Result<Bulletproof, BulletproofError> {
128    if outputs.is_empty() {
129      Err(BulletproofError::NoCommitments)?;
130    }
131    if outputs.len() > MAX_COMMITMENTS {
132      Err(BulletproofError::TooManyCommitments)?;
133    }
134    let commitments =
135      outputs.iter().map(|commitment| commitment.commit().into()).collect::<Vec<_>>();
136    Ok(Bulletproof::Original(
137      OriginalStatement::new(&commitments)
138        .expect("failed to create statement despite checking amount of commitments")
139        .prove(
140          rng,
141          OriginalWitness::new(outputs)
142            .expect("failed to create witness despite checking amount of commitments"),
143        )
144        .expect(
145          "failed to prove Bulletproof::Original despite ensuring statement/witness consistency",
146        ),
147    ))
148  }
149
150  /// Prove the list of commitments are within [0 .. 2^64) with an aggregate Bulletproof+.
151  ///
152  /// This function runs in time variable to the validity of the arguments and the public data.
153  pub fn prove_plus<R: RngCore + CryptoRng>(
154    rng: &mut R,
155    outputs: Vec<Commitment>,
156  ) -> Result<Bulletproof, BulletproofError> {
157    if outputs.is_empty() {
158      Err(BulletproofError::NoCommitments)?;
159    }
160    if outputs.len() > MAX_COMMITMENTS {
161      Err(BulletproofError::TooManyCommitments)?;
162    }
163    let commitments =
164      outputs.iter().map(|commitment| commitment.commit().into()).collect::<Vec<_>>();
165    Ok(Bulletproof::Plus(
166      PlusStatement::new(&commitments)
167        .expect("failed to create statement despite checking amount of commitments")
168        .prove(
169          rng,
170          &Zeroizing::new(
171            PlusWitness::new(outputs)
172              .expect("failed to create witness despite checking amount of commitments"),
173          ),
174        )
175        .expect("failed to prove Bulletproof::Plus despite ensuring statement/witness consistency"),
176    ))
177  }
178
179  /// Verify the given Bulletproof(+).
180  #[must_use]
181  pub fn verify<R: RngCore + CryptoRng>(
182    &self,
183    rng: &mut R,
184    commitments: &[CompressedPoint],
185  ) -> bool {
186    let Some(commitments) = commitments
187      .iter()
188      .map(|point| point.decompress().map(Point::into))
189      .collect::<Option<Vec<_>>>()
190    else {
191      return false;
192    };
193
194    match self {
195      Bulletproof::Original(bp) => {
196        let mut verifier = BulletproofsBatchVerifier::default();
197        let Some(statement) = OriginalStatement::new(&commitments) else {
198          return false;
199        };
200        if !statement.verify(rng, &mut verifier, bp.clone()) {
201          return false;
202        }
203        verifier.verify()
204      }
205      Bulletproof::Plus(bp) => {
206        let mut verifier = BulletproofsPlusBatchVerifier::default();
207        let Some(statement) = PlusStatement::new(&commitments) else {
208          return false;
209        };
210        if !statement.verify(rng, &mut verifier, bp.clone()) {
211          return false;
212        }
213        verifier.verify()
214      }
215    }
216  }
217
218  /// Accumulate the verification for the given Bulletproof(+) into the specified BatchVerifier.
219  ///
220  /// Returns false if the Bulletproof(+) isn't sane, leaving the BatchVerifier in an undefined
221  /// state.
222  ///
223  /// Returns true if the Bulletproof(+) is sane, regardless of its validity.
224  ///
225  /// The BatchVerifier must have its verification function executed to actually verify this proof.
226  #[must_use]
227  pub fn batch_verify<R: RngCore + CryptoRng>(
228    &self,
229    rng: &mut R,
230    verifier: &mut BatchVerifier,
231    commitments: &[CompressedPoint],
232  ) -> bool {
233    let Some(commitments) = commitments
234      .iter()
235      .map(|point| point.decompress().map(Point::into))
236      .collect::<Option<Vec<_>>>()
237    else {
238      return false;
239    };
240
241    match self {
242      Bulletproof::Original(bp) => {
243        let Some(statement) = OriginalStatement::new(&commitments) else {
244          return false;
245        };
246        statement.verify(rng, &mut verifier.original, bp.clone())
247      }
248      Bulletproof::Plus(bp) => {
249        let Some(statement) = PlusStatement::new(&commitments) else {
250          return false;
251        };
252        statement.verify(rng, &mut verifier.plus, bp.clone())
253      }
254    }
255  }
256
257  // This uses `write_all(scalar.to_bytes())` as these are `curve25519_dalek::Scalar`, not
258  // `monero_ed25519::Scalar`
259  fn write_core<W: Write, F: Fn(&[CompressedPoint], &mut W) -> io::Result<()>>(
260    &self,
261    w: &mut W,
262    specific_write_vec: F,
263  ) -> io::Result<()> {
264    match self {
265      Bulletproof::Original(bp) => {
266        bp.A.write(w)?;
267        bp.S.write(w)?;
268        bp.T1.write(w)?;
269        bp.T2.write(w)?;
270        w.write_all(&bp.tau_x.to_bytes())?;
271        w.write_all(&bp.mu.to_bytes())?;
272        specific_write_vec(&bp.ip.L, w)?;
273        specific_write_vec(&bp.ip.R, w)?;
274        w.write_all(&bp.ip.a.to_bytes())?;
275        w.write_all(&bp.ip.b.to_bytes())?;
276        w.write_all(&bp.t_hat.to_bytes())
277      }
278
279      Bulletproof::Plus(bp) => {
280        bp.A.write(w)?;
281        bp.wip.A.write(w)?;
282        bp.wip.B.write(w)?;
283        w.write_all(&bp.wip.r_answer.to_bytes())?;
284        w.write_all(&bp.wip.s_answer.to_bytes())?;
285        w.write_all(&bp.wip.delta_answer.to_bytes())?;
286        specific_write_vec(&bp.wip.L, w)?;
287        specific_write_vec(&bp.wip.R, w)
288      }
289    }
290  }
291
292  /// Write a Bulletproof(+) for the message signed by a transaction's signature.
293  ///
294  /// This has a distinct encoding from the standard encoding.
295  pub fn signature_write<W: Write>(&self, w: &mut W) -> io::Result<()> {
296    self.write_core(w, |points, w| write_raw_vec(CompressedPoint::write, points, w))
297  }
298
299  /// Write a Bulletproof(+).
300  pub fn write<W: Write>(&self, w: &mut W) -> io::Result<()> {
301    self.write_core(w, |points, w| write_vec(CompressedPoint::write, points, w))
302  }
303
304  /// Serialize a Bulletproof(+) to a `Vec<u8>`.
305  pub fn serialize(&self) -> Vec<u8> {
306    let mut serialized = Vec::with_capacity(512);
307    self.write(&mut serialized).expect("write failed but <Vec as io::Write> doesn't fail");
308    serialized
309  }
310
311  /// Read a Bulletproof.
312  pub fn read<R: Read>(r: &mut R) -> io::Result<Bulletproof> {
313    Ok(Bulletproof::Original(OriginalProof {
314      A: CompressedPoint::read(r)?,
315      S: CompressedPoint::read(r)?,
316      T1: CompressedPoint::read(r)?,
317      T2: CompressedPoint::read(r)?,
318      tau_x: Scalar::read(r)?.into(),
319      mu: Scalar::read(r)?.into(),
320      ip: IpProof {
321        L: read_vec(CompressedPoint::read, Some(MAX_LR), r)?,
322        R: read_vec(CompressedPoint::read, Some(MAX_LR), r)?,
323        a: Scalar::read(r)?.into(),
324        b: Scalar::read(r)?.into(),
325      },
326      t_hat: Scalar::read(r)?.into(),
327    }))
328  }
329
330  /// Read a Bulletproof+.
331  pub fn read_plus<R: Read>(r: &mut R) -> io::Result<Bulletproof> {
332    Ok(Bulletproof::Plus(PlusProof {
333      A: CompressedPoint::read(r)?,
334      wip: WipProof {
335        A: CompressedPoint::read(r)?,
336        B: CompressedPoint::read(r)?,
337        r_answer: Scalar::read(r)?.into(),
338        s_answer: Scalar::read(r)?.into(),
339        delta_answer: Scalar::read(r)?.into(),
340        L: read_vec(CompressedPoint::read, Some(MAX_LR), r)?,
341        R: read_vec(CompressedPoint::read, Some(MAX_LR), r)?,
342      },
343    }))
344  }
345}
monero_bulletproofs/lib.rs

monero_bulletproofs/
lib.rs
