Jump to content

Monero

  • entries
    229
  • comment
    1
  • views
    25103

Post-Mortem of Decoy Selection Bugs


Snider

255 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
      390.06 GH
    • Avg Hashrate
      157.47 MH
    • Total Miners
      2477
    • Miners Paid
      49625
    • Total Payments
      1442555
    • Total Hashes
      9.23 EX
    • Blocks Found
      2827300
  • Posts

    • Guest XRumerTest
      Hello. And Bye.
    • It is all set to rock the Drift Hunters with its impressive performance and ability to glue users for hours because it got thousands of active users within a few days.
    • it's hard to see them and you're so good diggy play with me
    • Guest RenkPluttovagaili
      Скачать День двести семнадцатый. Беседа с @Alexey Arestovych Алексеем Арестовичем #Фейгин #ФейгинLIVE День двести семнадцатый. Беседа с Алексеем Арестовичем (Киев). https://feygin-live.customprint.market/uk... Скачать ?исми пурраи Ахбори ВКД 28.09.2022 ?Подписаться на канал: https://www.youtube.com/c/ПайкиСугд? ?Подпишитесь в ФБ: https://www.facebook.com/%D0%9F%D0%B0...? ?Подпишитесь... Скачать Короткий ролик, недлинный https://bit.ly/3QTLd7x — ЗАБИРАЙ НАБОР КРУТОГО СНАРЯЖЕНИЯ В WARFACE ?????Стримы?????: https://www.twitch.tv/ghosthervalera ?? Поддержк... Скачать Кто виновен в провокациях на "Северных потоках"? Панорама ЕС теперь будет зависеть от поставок газа из США и Польши. Эксперты не исключают, что именно этим странам... Скачать РЕБЕНОК в Жёлтом ВСТРЕТИЛ МЕДВЕДЯ Who's Your Daddy ПОДПИШИСЬ СКОРЕЙ на FAMILY PLAY > https://www.youtube.com/channel/UCNJwQAU08P3muRZkZUOvx5A?sub_confirmation=1 Игра > https://store.steampowered.com/app/427730/Whos_Your_Da... Скачать Gas Station Simulator SS2[Thai] #4 ?????????????????????????? ??????????????? ?????????????????????? ?? ::Facebook page https://www.facebook.com/slapperch?re... ::My channel (??... Скачать Stranded Deep #10 ??????????????? ???? Ophtus ?? 100 ??? ??????? "Bay Riffer" ???????? - https://www.facebook.com/ophtus ?????????: bayriffer@ampverse.com ???... Скачать ???????????!! ??????????????????????????? Wither storm | Minecraft ??????? ?????????????????????????????????!! ????????????????????????... Скачать RoV : ????? Teeri ??????????????????????????????????????? ! #?????? #rov #teeri Скачать ?????????? RoV Pro League 2022 Winter | Regular Season | Week 8 Day 6 ?????????? RoV Pro League 2022 Winter??? ? ??? Regular Season | Week 8 Day 6 ? ?? ???????????????????????... Скачать PONNIYIN SELVAN Trailer Reaction! | #PS1 | Mani Ratnam | AR Rahman | Chiyaan Vikram | Karthi Reaction Gear: https://amzn.to/2QgTwk2 (affiliate link) ____________________ Intro music by DAVIS Youtube - http://bit.ly/30OK7RR Spotify - https://spoti.fi/2I3vRvE iTunes: https://apple.co/2KnvgY... Скачать Marvel Studios’ Secret Invasion | Official Trailer | Disney+ "I'm the last person standing between them and what they really want." Marvel Studios' Secret Invasion, an Original series, streaming 2023 on Disney+ . > Watch Marvel on Disney+: https://bit.ly... Скачать Bakasuran Teaser | Selvaraghavan | Natty Natraj | Sam CS | Mohan G | GM Film Corporation G M FILM CORPORATION presents The Official Teaser of Bakasuran( Tamil Movie ) Starring : Selvaragavan, Natty(Natraj Subramaniyan), Radharavi, Rajan K, Rams, Saravanan Subbiah, D Gunanithi,... Скачать Cobra - Official Trailer | Chiyaan Vikram | AR Rahman | Ajay Gnanamuthu | 7 Screen Studio 7 Screen Studio presents The Official Trailer of Cobra (Language : Tamil) Starring : Chiyaan Vikram, Srinidhi Shetty, Irfan Pathan, K.S. Ravikumar, Roshan Mathew, Anandraj, Robo Shankar, Mia... Скачать Doctor G Official Trailer | Ayushmann K, Rakul P, Shefali S | Anubhuti Kashyap | In Cinemas 14th Oct A medical campus comedy-drama, Doctor G is about the hilarious struggles of Dr. Uday Gupta, who wanted to specialise in Orthopaedic, but is stuck in an all-female class of Gynaecology. Will... Скачать Runtah (Biwir Beureum-Beureum Jawer Hayam Panon Coklat Kopi Susu) | Dara Ayu (Official Music Video) Official Music Video dari Dara Ayu "Runtah (Biwir Beureum- Beureum Jawer Hayam Panon Coklat Kopi Susu) Subscribe Bajol Ndanu Management di sini https://smarturl.it/subscribeBajolNdanu Artist... Скачать Farel Prayoga ft Lutfiana Dewi - Prau Layar (Official Music Video ANEKA SAFARI) Mau Lihat FAREL PRAYOGA JOGED loss tenann ,, KLIK LINK dan tonton video berikut ini SAMPAI SELESAI .. Coromu Ninggal Aku : https://www.youtube.com/watch?v=KyIq5xw5wZQ Jangan Lupa Subscribe... Скачать Yeni Inka - Teteg Ati (Official Music Yi Production) Teteg Ati - Yeni Inka (Official Music Yi Production). Mas perlu dingerteni, teteg ke atiku wis koyo ibumu. Ora tau nggersulo ngadepi polahmu, sing nggawe atiku atiku tatu. Title ... Скачать TETEG ATI - Arlida Putri Adella - OM ADELLA Live Music Performance by Arlida Putri Adella "Teteg Ati" Subscribe to Henny Adella: https://smarturl.it/HennyAdella Title : Teteg Ati Singer by Arlida Putri Adella Songwriter by Ilham Putratama... Скачать The Happiest Girl Provided to YouTube by YG PLUS (YGE) The Happiest Girl · BLACKPINK BORN PINK ? YG Entertainment Released on: 2022-09-16 Lyricist: Teddy Sinclair Lyricist: Willy Sinclair Lyricist: Paro... Скачать Psycho Party! feat. найтивыход - "Выпить" https://vk.cc/c5EU74 ************************************** Трек с альбома "Грустный рок" 02. "Выпить" https://vk.com/naitivihod ... Скачать Влад и Никита играют в кафе | Коллекция видео для детей Весёлые истории о том, как Влад и Никита играют в кафе. Подписывайся на канал! Интернет-магазин Влада и Никиты: ... Скачать БОЛЬШАЯ СРЕДНЯЯ или МАЛЕНЬКАЯ ТАРЕЛКА ЧЕЛЛЕНДЖ ! ***** Ссылка на НОВЫЙ МЕРЧ ВЛАДА А4 - https://a4shop.ru Канал ГЛЕНТА: https://bit.ly/2Gwxge4 Качай МОЁ новое ... Скачать Делон – Зеленскому: Я плачу вместе с вами и эту войну я не приемлю Президент Украины Владимир Зеленский пообщался с французским актером Аленом Делоном в эфире телеканала TV5 ... Скачать ?Что под песками Сахары. Допотопный Реактор. Засыпанные города. Канал Свидетель Виндовс - https://www.youtube.com/channel/UCVsDyCRge9DXmk1S6Ibr10Q Группа ВК: ... Скачать P S Позволь тебя любить????Марина Кистяева ???? аудиокниги Романы #аудиокнигиДетективTX #аудиокнигиРоманыTX #аудиокнигиМистикаTX аудиокниги Детектив TX аудиокниги РоманыTX ... Скачать Бумбокс Ой у лузі червона калина none Скачать НАШЛИ СЕКРЕТНУЮ ДВЕРЬ В ОББИ! А ТАМ... Roblox Cottons Difficulty Chart Obby HARD #KroshkaEva #Roblox. Скачать Как Балди стал таким из-за злой бабушки Гренни Все серии Страшилки Мультики Как Балди стал таким из-за злой бабушки Гренни Все серии Страшилки Мультики #horrorpig Композиция "Impending Boom" ... Скачать Не понимаю как могли исчезнуть сосиски Спасибо за просмотр Подпишись на мой YouTube Denis G : https://www.youtube.com/channel/UCpHqdyyN-zY0F_CNjyap6VQ ...
    • Rapid Assignment Help provide plagiarism free assignment online. Get Assignment Help from our team of professional writers at cheap rates.Browse our more sites like MBA Assignment Help and Management Assignment Help.
×
×
  • Create New...