Jump to content

Monero

  • entries
    225
  • comment
    1
  • views
    24377

Post-Mortem of Decoy Selection Bugs


Snider

201 views

When constructing a new transaction, a Monero wallet references a past output a user received in a prior transaction, and uses it as an input to the new transaction. Today, the wallet mixes this output with a set of 10 decoy outputs selected from other people's transactions from across the blockchain (ring signature). Thus, an observer cannot tell which among the 11 total outputs is the real one a user spends in a transaction, obfuscating the link from the user's new transaction to their prior transaction. The decoy selection algorithm specifically handles the selection process for choosing which decoys to mix real outputs with when constructing a transaction.

Between Monero versions v0.14.1.0 and v0.17.2.2, the core wallet code had two bugs in the decoy selection algorithm that impacted Monero users' privacy:

  1. The algorithm sometimes ignored very recent spendable outputs for consideration as decoys, thus rendering it clearer when users spent outputs immediately after the outputs were able to be spent.

  2. If transaction volume were to increase substantially over a sustained period of time, then wallets would eventually construct transactions that reveal real outputs in the vast majority of cases.

Both have been patched in v0.17.2.3 and it is highly recommended to upgrade as soon as able.

Users should also be aware that the implications of the first bug are not as severe as previously reported. It was widely publicized that as a result of the first bug, some very newly spent outputs observed on chain were guaranteed identifiable as real outputs spent in a transaction, however, this is not actually the case. Since publication, we learned that at least one popular light wallet (MyMonero) has been using a separate implementation of the decoy selection algorithm that did not have the bug. Therefore, MyMonero users could have feasibly constructed transactions that selected newly spendable outputs as decoys, which means newly spent outputs observed on chain were not guaranteed identifiable as real outputs.

Note that having distinct implementations of the decoy selection algorithm is not ideal. Ideally, all wallets would conform to the same spec of the decoy selection algorithm to ensure transaction uniformity, so that transactions on-chain cannot be tied to a particular wallet implementation.

Technical Explanations

Applying the algorithm incorrectly (Bug 1)

The decoy selection algorithm is designed to select outputs from across the blockchain based on observed spending patterns, as recommended in Möser et al. The paper's analysis uses spending patterns from earlier versions of Monero — where in some cases, the real outputs used in transactions could be deduced with certainty — in order to arrive at a distribution of Monero user spending patterns. The paper highlights that users were more likely to spend outputs received relatively quickly than they were to spend outputs held for a long time. The paper then recommends factoring in the observed spending patterns when selecting outputs from across the blockchain to use as decoys, rather than apply an equal probability to the entire set of outputs from across the blockchain. This way, newer outputs would be more likely to be selected as decoys than older outputs, thus better obfuscating which output is real in users' transactions.

When the paper's recommendation was first implemented in Monero v0.13.0.0, the wallet correctly applied the observed spending pattern from the tip of the blockchain when selecting decoys. However, when the algorithm was upgraded in v0.14.1.0, the algorithm applied the observed spending pattern from 10 blocks prior to the chain tip. This was done because outputs younger than 10 blocks old are locked and cannot be spent, therefore it seemed logical to apply the distribution starting 10 blocks prior to the chain tip so as to only consider spendable outputs. However, the implementation ended up ignoring some very recent spendable outputs for consideration as decoys. Additionally, it caused the algorithm to select marginally fewer decoy outputs roughly 10 to 20 blocks old.

This bug was patched in PR #7821.

Divide by 0 (Bug 2)

The upgrade to the decoy selection algorithm in v0.14.1.0 factored in block size variance in order to better match spending patterns and reduce bias toward selecting coinbase outputs as decoys. When selecting a decoy, the algorithm first determines the age in seconds that the decoy output should be (by using the distribution of known spending patterns, as discussed above). Then, the algorithm divides the expected output age in seconds by the average seconds spaced between each output observed over the trailing year, in order to arrive at the output in the chain that should be used as a decoy. If the number of outputs in a year is equivalent to the number of seconds in a year, then the average seconds spaced between each output over the year is 1.

The calculation of average seconds per output had a bug where it would truncate the result. If the average seconds per output were to fall below 1, the result would have truncated to 0. When the algorithm divides the expected output age in seconds by 0, it ends up selecting decoys exclusively from the most recent spendable block on most systems. Thus, if output volume were to increase substantially over a sustained period, such that the seconds spaced between each output over the trailing year were to fall below 1 (i.e. the number of outputs over the trailing year exceeds the number of seconds in a year), then the algorithm would have selected decoys from the most recent spendable block in the vast majority of cases. At the time of this publication, the average seconds per output is around 1.7.

This divide by 0 bug was patched in PR #7845.

Conclusion

Work to improve the decoy selection algorithm is ongoing. It has room for improvement to provide stronger protection to users under a wider set of circumstances. A call to arms: anyone with a background in statistics and probability theory is encouraged to join in discussions geared toward improving the algorithm. Discussions are frequent in the #monero-research-lab and #monero-dev IRC/Matrix channels. While innovative research to improve Monero's cryptography continues in parallel in order to substantially increase the number of decoys mixed with real outputs in a transaction (i.e. increase the ring size), research to improve the decoy selection algorithm's statistical obfuscation techniques is also receiving more attention. If you feel you have the requisite skills, keep in mind there is growing interest from the Monero community to actively recruit you to the Monero project. If you are interested, consider contacting a Monero workgroup.

View the full article

1 Comment


Recommended Comments

dsds

Block size variance was taken into account when the decoy selection algorithm was upgraded in version 0.14.1.0 in order to better match spending patterns and lessen bias against choosing coinbase outputs as decoys. The method initially calculates the age in seconds that the decoy output should be before choosing a decoy (by using the distribution of known spending patterns, as discussed above). The output in the chain that should be utilized as a decoy is then determined by dividing the expected output age in seconds by the average number of seconds between each output seen over the preceding year. The average number of seconds between each output throughout the course of the year equals one if the number of outputs in a year is equal to the number of seconds in a year. octordle

Edited by beautifulgrease
Link to comment
Guest
Add a comment...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

  • HashVault Latest Blocks

  • HashVault Stats

    • Global Hashrate
      414.77 GH
    • Avg Hashrate
      174.27 MH
    • Total Miners
      2380
    • Miners Paid
      48447
    • Total Payments
      1416089
    • Total Hashes
      9.23 EX
    • Blocks Found
      2719411
  • Posts

    • Buenos dias, no se me abre pool monero,des de hace dias. Me comenta al abrir k puede haver cambiado de pagina.alguien sabe algo
    • How can I tell HiveOS how many cores or threads I want to use for mining? My Ryzen 3600 has been lowered to 55w. In order to avoid clogging GPUs, I only want to use 11 threads for mining, with 1 thread for system-specific purposes. fnf
    • ./xmrig --url pool.hashvault.pro:80 --user *** --pass x -a cn-heavy/xhv * ABOUT XMRig/6.17.0 gcc/9.3.0 * LIBS libuv/1.43.0 OpenSSL/1.1.1m hwloc/2.7.0 * HUGE PAGES supported * 1GB PAGES disabled * CPU AMD EPYC-Rome Processor (1) 64-bit AES VM L2:0.5 MB L3:16.0 MB 1C/1T NUMA:1 * MEMORY 0.6/1.9 GB (31%) DIMM 0: 2 GB RAM @ 0 MHz DIMM 0 * MOTHERBOARD Vultr - VHP * DONATE 1% * ASSEMBLY auto:ryzen * POOL #1 pool.hashvault.pro:80 algo cn-heavy/xhv * COMMANDS hashrate, pause, resume, results, connection [2022-05-22 12:49:13.205] net use pool pool.hashvault.pro:80 131.153.76.130 [2022-05-22 12:49:13.205] net new job from pool.hashvault.pro:80 diff 36000 algo rx/0 height 2628998 (7 tx) [2022-05-22 12:49:13.205] cpu use argon2 implementation AVX2 [2022-05-22 12:49:13.207] msr cannot read MSR 0xc0011020 [2022-05-22 12:49:13.207] msr FAILED TO APPLY MSR MOD, HASHRATE WILL BE LOW [2022-05-22 12:49:13.207] randomx init dataset algo rx/0 (1 threads) seed 6ac097ea635e9d1d... [2022-05-22 12:49:13.207] randomx not enough memory for RandomX dataset [2022-05-22 12:49:13.235] randomx failed to allocate RandomX dataset, switching to slow mode (27 ms) [2022-05-22 12:49:13.517] randomx dataset ready (282 ms) [2022-05-22 12:49:13.517] cpu use profile rx (1 thread) scratchpad 2048 KB [2022-05-22 12:49:13.519] cpu READY threads 1/1 (1) huge pages 100% 1/1 memory 2048 KB (1 ms) [2022-05-22 12:49:17.487] net new job from pool.hashvault.pro:80 diff 36000 algo rx/0 height 2628998 (52 tx) [2022-05-22 12:49:20.337] signal Ctrl+C received, exiting [2022-05-22 12:49:20.345] cpu stopped (8 ms I run xmrig and set the algorithm `cn-heavy/xhv`, but it still response `rx/0`.How to solve this problem?
    • Yes, I like the content of this article.  LOL Beans
    • Yeah, it does, but apparently it's not so transparent. So if we > mention that we'd better indicate in the same paragraph that you > probably don't actually want to use it. How about the attached?  UNO Online
×
×
  • Create New...