monero_wallet/
decoys.rs

1#![expect(clippy::as_conversions, clippy::float_arithmetic)]
2
3use std_shims::{prelude::*, io, vec::Vec, collections::HashSet};
4
5use zeroize::{Zeroize, ZeroizeOnDrop};
6
7use rand_core::{RngCore, CryptoRng};
8use rand_distr::{Distribution as _, Gamma};
9#[cfg(not(feature = "std"))]
10use rand_distr::num_traits::Float;
11
12use crate::{
13  DEFAULT_LOCK_WINDOW, COINBASE_LOCK_WINDOW, BLOCK_TIME,
14  ed25519::{Scalar, Point, Commitment},
15  ringct::clsag::Decoys,
16  interface::{InterfaceError, TransactionsError, EvaluateUnlocked, ProvidesDecoys},
17  output::OutputData,
18  WalletOutput,
19};
20
21const RECENT_WINDOW: u64 = 15;
22const BLOCKS_PER_YEAR: usize = (365 * 24 * 60 * 60) / BLOCK_TIME;
23#[expect(clippy::cast_precision_loss)]
24const TIP_APPLICATION: f64 = (DEFAULT_LOCK_WINDOW * BLOCK_TIME) as f64;
25
26async fn select_n(
27  rng: &mut (impl RngCore + CryptoRng),
28  rpc: &impl ProvidesDecoys,
29  block_number: usize,
30  output_being_spent: &WalletOutput,
31  ring_len: u8,
32  fingerprintable_deterministic: bool,
33) -> Result<Vec<(u64, [Point; 2])>, TransactionsError> {
34  if block_number <= DEFAULT_LOCK_WINDOW {
35    Err(InterfaceError::InternalError("not enough blocks to select decoys".to_owned()))?;
36  }
37  if block_number > rpc.latest_block_number().await? {
38    Err(InterfaceError::InternalError(
39      "decoys being requested from blocks this node doesn't have".to_owned(),
40    ))?;
41  }
42
43  // Get the distribution
44  let distribution = rpc.ringct_output_distribution(..= block_number).await?;
45  if distribution.len() < DEFAULT_LOCK_WINDOW {
46    Err(InterfaceError::InternalError("not enough blocks to select decoys".to_owned()))?;
47  }
48  let highest_output_exclusive_bound = distribution[distribution.len() - DEFAULT_LOCK_WINDOW];
49  // This assumes that each miner TX had one output (as sane) and checks we have sufficient
50  // outputs even when excluding them (due to their own timelock requirements)
51  // Considering this a temporal error for very new chains, it's sufficiently sane to have
52  if highest_output_exclusive_bound.saturating_sub(
53    u64::try_from(COINBASE_LOCK_WINDOW).expect("coinbase lock window exceeds 2^{64}"),
54  ) < u64::from(ring_len)
55  {
56    Err(InterfaceError::InternalError("not enough decoy candidates".to_owned()))?;
57  }
58
59  // Determine the outputs per second
60  #[expect(clippy::cast_precision_loss)]
61  let per_second = {
62    let blocks = distribution.len().min(BLOCKS_PER_YEAR);
63    let initial = distribution[distribution.len().saturating_sub(blocks + 1)];
64    let outputs = distribution[distribution.len() - 1].saturating_sub(initial);
65    (outputs as f64) / ((blocks * BLOCK_TIME) as f64)
66  };
67
68  let output_being_spent_index = output_being_spent.relative_id.index_on_blockchain;
69
70  // Don't select the real output
71  let mut do_not_select = HashSet::new();
72  do_not_select.insert(output_being_spent_index);
73
74  let decoy_count = usize::from(ring_len - 1);
75  let mut res = Vec::with_capacity(decoy_count);
76
77  let mut first_iter = true;
78  let mut iters = 0;
79  // Iterates until we have enough decoys
80  // If an iteration only returns a partial set of decoys, the remainder will be obvious as decoys
81  // to the RPC
82  // The length of that remainder is expected to be minimal
83  while res.len() != decoy_count {
84    let remaining = decoy_count - res.len();
85    let mut candidates = Vec::with_capacity(remaining);
86    while candidates.len() != remaining {
87      {
88        iters += 1;
89
90        /*
91          Ensure this isn't infinitely looping.
92
93          We check both that we aren't at the maximum amount of iterations and that the not-yet
94          selected candidates exceed the amount of candidates necessary to trigger the next
95          iteration.
96        */
97        if (iters == {
98          #[cfg_attr(test, expect(unused))]
99          let max_iters = 10 * usize::from(ring_len);
100          // When testing on fresh chains, increased iterations can be useful and we don't
101          // necessitate reasonable performance
102          #[cfg(test)]
103          let max_iters = 1000 * usize::from(ring_len);
104          max_iters
105        }) || ((highest_output_exclusive_bound -
106          u64::try_from(do_not_select.len()).expect("amount of ignored decoys exceeds 2^{64}")) <
107          u64::try_from(remaining - candidates.len())
108            .expect("amount of remaining selections exceeds 2^{64}"))
109        {
110          Err(InterfaceError::InternalError("hit decoy selection round limit".to_owned()))?;
111        }
112      }
113
114      // Use a gamma distribution, as Monero does
115      // https://github.com/monero-project/monero/blob/cc73fe71162d564ffda8e549b79a350bca53c45
116      //   /src/wallet/wallet2.cpp#L142-L143
117      let mut age = Gamma::<f64>::new(19.28, 1.0 / 1.61)
118        .expect("constant Gamma distribution could no longer be created")
119        .sample(rng)
120        .exp();
121      #[expect(clippy::cast_precision_loss)]
122      if age > TIP_APPLICATION {
123        age -= TIP_APPLICATION;
124      } else {
125        // `f64` does not have `try_from` available, which is why these are written with `as`
126        age = (rng.next_u64() %
127          (RECENT_WINDOW * u64::try_from(BLOCK_TIME).expect("BLOCK_TIME exceeded u64::MAX")))
128          as f64;
129      }
130
131      #[expect(clippy::cast_sign_loss, clippy::cast_possible_truncation)]
132      let o = (age * per_second) as u64;
133      if o < highest_output_exclusive_bound {
134        // Find which block this points to
135        let i = distribution.partition_point(|s| *s < (highest_output_exclusive_bound - 1 - o));
136        let prev_block = i.checked_sub(1);
137        let prev_outputs = prev_block.map(|prev_block| distribution[prev_block]).unwrap_or(0);
138        let n = distribution[i].checked_sub(prev_outputs).ok_or_else(|| {
139          InterfaceError::InternalError("RPC returned non-monotonic distribution".to_owned())
140        })?;
141        if n != 0 {
142          // Select an output from within this block
143          let o = prev_outputs + (rng.next_u64() % n);
144          if !do_not_select.contains(&o) {
145            candidates.push(o);
146            // This output will either be used or is unusable
147            // In either case, we should not try it again
148            do_not_select.insert(o);
149          }
150        }
151      }
152    }
153
154    // If this is the first time we're requesting these outputs, include the real one as well
155    // Prevents the node we're connected to from having a list of known decoys and then seeing a
156    // TX which uses all of them, with one additional output (the true spend)
157    let real_index = first_iter.then(|| {
158      first_iter = false;
159
160      candidates.push(output_being_spent_index);
161      // Sort candidates so the real spends aren't the ones at the end
162      candidates.sort_unstable();
163      candidates
164        .binary_search(&output_being_spent_index)
165        .expect("selected a ring which didn't include the real spend")
166    });
167
168    for (i, output) in rpc
169      .unlocked_ringct_outputs(
170        &candidates,
171        if fingerprintable_deterministic {
172          EvaluateUnlocked::FingerprintableDeterministic { block_number }
173        } else {
174          EvaluateUnlocked::Normal
175        },
176      )
177      .await?
178      .iter_mut()
179      .enumerate()
180    {
181      // https://github.com/monero-oxide/monero-oxide/issues/56
182      if real_index == Some(i) {
183        if (Some(output_being_spent.key()) != output.map(|[key, _commitment]| key)) ||
184          (Some(output_being_spent.commitment().commit()) !=
185            output.map(|[_key, commitment]| commitment))
186        {
187          Err(InterfaceError::InvalidInterface(
188            "node presented different view of output we're trying to spend".to_owned(),
189          ))?;
190        }
191
192        continue;
193      }
194
195      // If this is an unlocked output, push it to the result
196      if let Some(output) = output.take() {
197        {
198          let [key, commitment] = output;
199          // Unless torsion is present
200          // https://github.com/monero-project/monero/blob/893916ad091a92e765ce3241b94e706ad012b62a
201          //   /src/wallet/wallet2.cpp#L9050-L9060
202          if !(key.into().is_torsion_free() && commitment.into().is_torsion_free()) {
203            continue;
204          }
205          /*
206            Or the key is the identity, and accordingly cannot be signed for as a real ring member.
207
208            If Monero omits this check, then transactions may technically be fingerprinted as from
209            `wallet2` (and not `monero-wallet`). We accept this (arguable) fingerprint.
210          */
211          use curve25519_dalek::traits::IsIdentity as _;
212          if key.into().is_identity() {
213            continue;
214          }
215        }
216        res.push((candidates[i], output));
217      }
218    }
219  }
220
221  Ok(res)
222}
223
224async fn select_decoys<R: RngCore + CryptoRng>(
225  rng: &mut R,
226  rpc: &impl ProvidesDecoys,
227  ring_len: u8,
228  block_number: usize,
229  input: &WalletOutput,
230  fingerprintable_deterministic: bool,
231) -> Result<Decoys, TransactionsError> {
232  if ring_len == 0 {
233    Err(InterfaceError::InternalError("requesting a ring of length 0".to_owned()))?;
234  }
235
236  // Select all decoys for this transaction, assuming we generate a sane transaction
237  // We should almost never naturally generate an insane transaction, hence why this doesn't
238  // bother with an overage
239  let decoys =
240    select_n(rng, rpc, block_number, input, ring_len, fingerprintable_deterministic).await?;
241
242  // Form the complete ring
243  let mut ring = decoys;
244  ring.push((input.relative_id.index_on_blockchain, [input.key(), input.commitment().commit()]));
245  ring.sort_by_key(|(index_on_blockcahin, _value)| *index_on_blockcahin);
246
247  /*
248    Monero does have sanity checks which it applies to the selected ring.
249
250    They're statistically unlikely to be hit and only occur when the transaction is published over
251    the RPC (so they are not a relay rule). The RPC allows disabling them, which our RPC
252    implementations do to ensure they don't pose a problem.
253
254    They aren't worth the complexity to implement here, especially since they're non-deterministic.
255  */
256
257  // We need to convert our positional indexes to offset indexes
258  let mut offsets = Vec::with_capacity(ring.len());
259  {
260    offsets.push(ring[0].0);
261    for m in 1 .. ring.len() {
262      offsets.push(ring[m].0 - ring[m - 1].0);
263    }
264  }
265
266  Ok(
267    Decoys::new(
268      offsets,
269      // Binary searches for the real spend since we don't know where it sorted to
270      u8::try_from(ring.partition_point(|x| x.0 < input.relative_id.index_on_blockchain))
271        .expect("ring of size <= u8::MAX had an index exceeding u8::MAX"),
272      ring.into_iter().map(|output| output.1).collect(),
273    )
274    .expect("selected a syntactically-invalid set of Decoys"),
275  )
276}
277
278/// An output with decoys selected.
279///
280/// The `Debug` implementation may reveal every value within its memory.
281#[derive(Clone, Debug, Zeroize, ZeroizeOnDrop)]
282pub struct OutputWithDecoys {
283  output: OutputData,
284  decoys: Decoys,
285}
286
287impl PartialEq for OutputWithDecoys {
288  fn eq(&self, other: &Self) -> bool {
289    bool::from(self.output.ct_eq(&other.output) & self.decoys.ct_eq(&other.decoys))
290  }
291}
292impl Eq for OutputWithDecoys {}
293
294impl OutputWithDecoys {
295  /// Select decoys for this output.
296  ///
297  /// The methodology used to sample decoys SHOULD prevent an RPC controlled by a passive adversary
298  /// from discovering the output actually being spent. An RPC controlled by an active adversary,
299  /// one who deliberately yields non-standard responses and provides a malicious view of the
300  /// Monero blockchain, may still be able to identify the output being spent. For privacy, please
301  /// only connect to trusted RPCs.
302  pub async fn new(
303    rng: &mut (impl Send + Sync + RngCore + CryptoRng),
304    rpc: &impl ProvidesDecoys,
305    ring_len: u8,
306    block_number: usize,
307    output: WalletOutput,
308  ) -> Result<OutputWithDecoys, TransactionsError> {
309    let decoys = select_decoys(rng, rpc, ring_len, block_number, &output, false).await?;
310    Ok(OutputWithDecoys { output: output.data.clone(), decoys })
311  }
312
313  /// Select a set of decoys for this output with a deterministic process.
314  ///
315  /// This function will always output the same set of decoys when called with the same arguments.
316  /// This makes it very useful in multisignature contexts, where instead of having one participant
317  /// select the decoys, everyone can locally select the decoys while coming to the same result.
318  ///
319  /// The set of decoys selected may be fingerprintable as having been produced by this
320  /// methodology.
321  ///
322  /// The methodology used to sample decoys SHOULD prevent an RPC controlled by a passive adversary
323  /// from discovering the output actually being spent. An RPC controlled by an active adversary,
324  /// one who deliberately yields non-standard responses and provides a malicious view of the
325  /// Monero blockchain, may still be able to identify the output being spent. For privacy, please
326  /// only connect to trusted RPCs.
327  pub async fn fingerprintable_deterministic_new(
328    rng: &mut (impl Send + Sync + RngCore + CryptoRng),
329    rpc: &impl ProvidesDecoys,
330    ring_len: u8,
331    block_number: usize,
332    output: WalletOutput,
333  ) -> Result<OutputWithDecoys, TransactionsError> {
334    let decoys = select_decoys(rng, rpc, ring_len, block_number, &output, true).await?;
335    Ok(OutputWithDecoys { output: output.data.clone(), decoys })
336  }
337
338  /// The key this output may be spent by.
339  pub fn key(&self) -> Point {
340    self.output.key()
341  }
342
343  /// The scalar to add to the private spend key for it to be the discrete logarithm of this
344  /// output's key.
345  pub fn key_offset(&self) -> Scalar {
346    self.output.key_offset
347  }
348
349  /// The commitment this output created.
350  pub fn commitment(&self) -> &Commitment {
351    &self.output.commitment
352  }
353
354  /// The decoys this output selected.
355  pub fn decoys(&self) -> &Decoys {
356    &self.decoys
357  }
358
359  /// Write the OutputWithDecoys.
360  ///
361  /// This is not a Monero protocol defined struct, and this is accordingly not a Monero protocol
362  /// defined serialization. This may run in time variable to its value.
363  pub fn write<W: io::Write>(&self, w: &mut W) -> io::Result<()> {
364    self.output.write(w)?;
365    self.decoys.write(w)
366  }
367
368  /// Serialize the OutputWithDecoys to a `Vec<u8>`.
369  ///
370  /// This is not a Monero protocol defined struct, and this is accordingly not a Monero protocol
371  /// defined serialization. This may run in time variable to its value.
372  pub fn serialize(&self) -> Vec<u8> {
373    let mut serialized = Vec::with_capacity(128);
374    self.write(&mut serialized).expect("write failed but <Vec as io::Write> doesn't fail");
375    serialized
376  }
377
378  /// Read an OutputWithDecoys.
379  ///
380  /// This is not a Monero protocol defined struct, and this is accordingly not a Monero protocol
381  /// defined serialization. This may run in time variable to its value.
382  pub fn read<R: io::Read>(r: &mut R) -> io::Result<Self> {
383    Ok(Self { output: OutputData::read(r)?, decoys: Decoys::read(r)? })
384  }
385}
monero_wallet/decoys.rs

monero_wallet/
decoys.rs
