monero_mlsag/
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 zeroize::Zeroize;
13
14use curve25519_dalek::EdwardsPoint;
15
16use monero_io::*;
17use monero_ed25519::{Scalar, Point, CompressedPoint};
18
19// A static for `H` as it's frequently used yet this decompression is expensive.
20static H: LazyLock<EdwardsPoint> = LazyLock::new(|| {
21  CompressedPoint::H.decompress().expect("couldn't decompress `CompressedPoint::H`").into()
22});
23
24/// Errors when working with MLSAGs.
25#[derive(Clone, Copy, PartialEq, Eq, Debug, thiserror::Error)]
26pub enum MlsagError {
27  /// Invalid ring (such as too small or too large).
28  #[error("invalid ring")]
29  InvalidRing,
30  /// Invalid amount of key images.
31  #[error("invalid amount of key images")]
32  InvalidAmountOfKeyImages,
33  /// Invalid ss matrix.
34  #[error("invalid ss")]
35  InvalidSs,
36  /// Invalid key image.
37  #[error("invalid key image")]
38  InvalidKeyImage,
39  /// Invalid ci vector.
40  #[error("invalid ci")]
41  InvalidCi,
42}
43
44/// A vector of rings, forming a matrix, to verify the MLSAG with.
45#[derive(Clone, PartialEq, Eq, Debug, Zeroize)]
46pub struct RingMatrix {
47  matrix: Vec<Vec<EdwardsPoint>>,
48}
49
50impl RingMatrix {
51  /// Construct a ring matrix from an already formatted series of points.
52  fn new(matrix: Vec<Vec<EdwardsPoint>>) -> Result<Self, MlsagError> {
53    // Monero requires that there is more than one ring member for MLSAG signatures:
54    // https://github.com/monero-project/monero/blob/ac02af92867590ca80b2779a7bbeafa99ff94dcb/
55    // src/ringct/rctSigs.cpp#L462
56    if matrix.len() < 2 {
57      Err(MlsagError::InvalidRing)?;
58    }
59    for member in &matrix {
60      if member.is_empty() || (member.len() != matrix[0].len()) {
61        Err(MlsagError::InvalidRing)?;
62      }
63    }
64
65    Ok(RingMatrix { matrix })
66  }
67
68  /// Construct a ring matrix for an individual output.
69  pub fn individual(
70    ring: &[[CompressedPoint; 2]],
71    pseudo_out: CompressedPoint,
72  ) -> Result<Self, MlsagError> {
73    let mut matrix = Vec::with_capacity(ring.len());
74    for ring_member in ring {
75      let decomp = |p: CompressedPoint| Ok(p.decompress().ok_or(MlsagError::InvalidRing)?.into());
76
77      matrix.push(vec![decomp(ring_member[0])?, decomp(ring_member[1])? - decomp(pseudo_out)?]);
78    }
79    RingMatrix::new(matrix)
80  }
81
82  /// Iterate over the members of the matrix.
83  fn iter(&self) -> impl Iterator<Item = &[EdwardsPoint]> {
84    self.matrix.iter().map(AsRef::as_ref)
85  }
86
87  /// Get the amount of members in the ring.
88  pub fn members(&self) -> usize {
89    self.matrix.len()
90  }
91
92  /// Get the length of a ring member.
93  ///
94  /// A ring member is a vector of points for which the signer knows all of the discrete logarithms
95  /// of.
96  pub fn member_len(&self) -> usize {
97    // this is safe to do as the constructors don't allow empty rings
98    self.matrix[0].len()
99  }
100}
101
102/// The MLSAG linkable ring signature, as used in Monero.
103#[derive(Clone, PartialEq, Eq, Debug, Zeroize)]
104pub struct Mlsag {
105  ss: Vec<Vec<Scalar>>,
106  cc: Scalar,
107}
108
109impl Mlsag {
110  /// Write a MLSAG.
111  pub fn write<W: Write>(&self, w: &mut W) -> io::Result<()> {
112    for ss in &self.ss {
113      write_raw_vec(Scalar::write, ss, w)?;
114    }
115    self.cc.write(w)
116  }
117
118  /// Read a MLSAG.
119  pub fn read<R: Read>(decoys: usize, ss_2_elements: usize, r: &mut R) -> io::Result<Mlsag> {
120    Ok(Mlsag {
121      ss: (0 .. decoys)
122        .map(|_| read_raw_vec(Scalar::read, ss_2_elements, r))
123        .collect::<Result<_, _>>()?,
124      cc: Scalar::read(r)?,
125    })
126  }
127
128  /// Verify a MLSAG.
129  ///
130  /// WARNING: This follows the Fiat-Shamir transcript format used by the Monero protocol, which
131  /// makes assumptions on what has already been transcripted and bound to within `msg`. Do not use
132  /// this if you don't know what you're doing.
133  pub fn verify(
134    &self,
135    msg: &[u8; 32],
136    ring: &RingMatrix,
137    key_images: &[CompressedPoint],
138  ) -> Result<(), MlsagError> {
139    // Mlsag allows for layers to not need linkability, hence they don't need key images
140    // Monero requires that there is always only 1 non-linkable layer - the amount commitments.
141    if ring.member_len() != (key_images.len() + 1) {
142      Err(MlsagError::InvalidAmountOfKeyImages)?;
143    }
144
145    let mut buf = Vec::with_capacity(6 * 32);
146    buf.extend_from_slice(msg);
147
148    let mut ci = self.cc.into();
149
150    // This is an iterator over the key images as options with an added entry of `None` at the
151    // end for the non-linkable layer
152    let key_images_iter = key_images.iter().map(Some).chain(core::iter::once(None));
153
154    if ring.matrix.len() != self.ss.len() {
155      Err(MlsagError::InvalidSs)?;
156    }
157
158    for (ring_member, ss) in ring.iter().zip(&self.ss) {
159      if ring_member.len() != ss.len() {
160        Err(MlsagError::InvalidSs)?;
161      }
162
163      for ((ring_member_entry, s), ki) in ring_member.iter().zip(ss).zip(key_images_iter.clone()) {
164        let s = (*s).into();
165        #[allow(non_snake_case)]
166        let L = EdwardsPoint::vartime_double_scalar_mul_basepoint(&ci, ring_member_entry, &s);
167
168        let compressed_ring_member_entry = ring_member_entry.compress();
169        buf.extend_from_slice(compressed_ring_member_entry.as_bytes());
170        buf.extend_from_slice(L.compress().as_bytes());
171
172        // Not all dimensions need to be linkable, e.g. commitments, and only linkable layers need
173        // to have key images.
174        if let Some(ki) = ki {
175          let Some(ki) = ki.decompress() else {
176            return Err(MlsagError::InvalidKeyImage);
177          };
178          let ki = ki.key_image().ok_or(MlsagError::InvalidKeyImage)?;
179
180          // TODO: vartime_double_scalar_mul?
181          #[allow(non_snake_case)]
182          let R =
183            (s * Point::biased_hash(compressed_ring_member_entry.to_bytes()).into()) + (ci * ki);
184          buf.extend_from_slice(R.compress().as_bytes());
185        }
186      }
187
188      ci = Scalar::hash(&buf).into();
189      // keep the msg in the buffer.
190      buf.drain(msg.len() ..);
191    }
192
193    if ci != self.cc.into() {
194      Err(MlsagError::InvalidCi)?;
195    }
196    Ok(())
197  }
198}
199
200/// Builder for a RingMatrix when using an aggregate signature.
201///
202/// This handles the formatting as necessary.
203#[derive(Clone, PartialEq, Eq, Debug, Zeroize)]
204pub struct AggregateRingMatrixBuilder {
205  key_ring: Vec<Vec<EdwardsPoint>>,
206  amounts_ring: Vec<EdwardsPoint>,
207  sum_out: EdwardsPoint,
208}
209
210impl AggregateRingMatrixBuilder {
211  /// Create a new AggregateRingMatrixBuilder.
212  ///
213  /// This takes in the transaction's outputs' commitments and fee used.
214  pub fn new(commitments: &[CompressedPoint], fee: u64) -> Result<Self, MlsagError> {
215    // TODO: Use a short mul for the fee
216    Ok(AggregateRingMatrixBuilder {
217      key_ring: vec![],
218      amounts_ring: vec![],
219      sum_out: commitments
220        .iter()
221        .map(|compressed| compressed.decompress().map(Point::into))
222        .sum::<Option<EdwardsPoint>>()
223        .ok_or(MlsagError::InvalidRing)? +
224        (*H * curve25519_dalek::Scalar::from(fee)),
225    })
226  }
227
228  /// Push a ring of [output key, commitment] to the matrix.
229  pub fn push_ring(&mut self, ring: &[[CompressedPoint; 2]]) -> Result<(), MlsagError> {
230    if self.key_ring.is_empty() {
231      self.key_ring = vec![vec![]; ring.len()];
232      // Now that we know the length of the ring, fill the `amounts_ring`.
233      self.amounts_ring = vec![-self.sum_out; ring.len()];
234    }
235
236    if (self.amounts_ring.len() != ring.len()) || ring.is_empty() {
237      // All the rings in an aggregate matrix must be the same length.
238      return Err(MlsagError::InvalidRing);
239    }
240
241    for (i, ring_member) in ring.iter().enumerate() {
242      self.key_ring[i].push(ring_member[0].decompress().ok_or(MlsagError::InvalidRing)?.into());
243      self.amounts_ring[i] += ring_member[1].decompress().ok_or(MlsagError::InvalidRing)?.into();
244    }
245
246    Ok(())
247  }
248
249  /// Build and return the [`RingMatrix`].
250  pub fn build(mut self) -> Result<RingMatrix, MlsagError> {
251    for (i, amount_commitment) in self.amounts_ring.drain(..).enumerate() {
252      self.key_ring[i].push(amount_commitment);
253    }
254    RingMatrix::new(self.key_ring)
255  }
256}
monero_mlsag/lib.rs

monero_mlsag/
lib.rs
