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