monero_bulletproofs/
lib.rs

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

monero_bulletproofs/
lib.rs
