Post-fork Monero Decoy Selection Bias Could Have Detrimental Impact On Privacy

370 engineer and concerned Monero user ‘Lacksfish’ has outlined a troubling bias towards the use of coinbase (block reward) transactions as decoys (also known as mixins) occuring on the post-fork Monero chain, with potentially troublesome privacy implications. The Github issue outlined here points towards a concerning number of recent transactions in which there is a disproportionate number of block reward transactions utilised as decoys in the ring signature. A fix has now merged and a new version of the Monero CLI has now been released, but a number of other wallets are yet to upgrade.

The changes to the decoy selection algorithm have been present in the Monero codebase for several months, but its impact appears to have been exacerbated by the recent transaction size improvements related to this month’s hard-fork which introduced the use of highly efficient bulletproofs. These more compact zero-knowledge proofs created a notable reduction in average transaction fees overnight which many users are pleased with, but the transaction size decrease has also resulted in a greater transaction capacity per block, and as a consequence there appears to have been an increase in the number of empty blocks being mined.

Smaller transactions on the blockchain results in significant gains to transaction throughput, as more unconfirmed transactions can be included with each block mined. As Monero targets a reasonably rapid two minute block time, it isn’t uncommon for the mempool to be completely cleared within a couple of blocks, at which point the next block will be empty if no new transactions are broadcast over the following minutes. It is the growing number of these recent empty blocks that appear to be associated with a potential reduction in the privacy of affected transactions and a growing risk of a chain reaction reducing the privacy of others; if more and more chains of transactions include large numbers of coinbase decoys there is an increase in the potential for tracking some transactions with sophisticated analysis.

The decoy selection algorithm uses block height to gather a selection of transactions from random blocks, but whenever an empty block is chosen the coinbase transaction is the only option to be used as a decoy. Whilst including coinbase transactions as decoys is not a bad thing in moderation, the reality of recent changes has resulted in disproportionate numbers of these being used together which greatly decreases the real number of likely decoys. This potentially makes the likelihood of an observer deciphering the real transaction that is being spent in a transaction somewhat higher, particularly if sophisticated analysis heuristics are applied. The research outlined in ‘An Empirical Analysis of Traceability in the Monero Blockchain’ found a few shortcomings related to ring signature decoy selections, and some of the improvements discussed in an early version of the paper were already implemented by the time it was released. Monero developers responded to the most recent version of the paper to suggest the current updated selection algorithm was a vast improvement upon the algorithm employed in the period referred to in the research, whilst acknowledging that decoy selection is an area for future research and improvement.

The problem with any bias towards block reward transactions being utilised as ring signature decoys inputs is down to the fact that block reward transactions tend to be some of the least private Monero transactions possible, primarily due to the nature of public pool mining payouts. If attempting to track Monero transactions it would be plausible to ignore all of the coinbase transactions and in some cases this has reduced the number of candidates for the potential spending transaction from 10 down to 3.

The lack of wider community discussion over this issue is somewhat surprising, as this appears to be a relatively easily avoidable privacy loss that made its way into the codebase, with minimal consultation. This is perhaps due in part to the difference between theory and reality as the real-world of empty blocks could have been overseen when thinking about increases in transaction throughput. Monero Research Lab and other contributors have been doing fantastic work on continuous improvements to privacy over the last few years, but there does appear to be a gap between more esoteric research and real-world risk analysis of Monero, which represents over $1billion in real value out in the wild.

Whilst it is important to acknowledge the experimental nature of Monero and indeed the wider cryptocurrency ecosystem, greater discussion about the impacts of changes on the expected privacy of the chain can only be a positive. There is a risk that due to not being consensus critical, decoy selection improvements may not have been included by some large exchanges responsible for significant transaction volume. Perhaps greater community interest, understanding and engagement with such changes, could encourage important economic entities to improve their own decoy selection process.

Many Monero wallets, such as MyMonero and Cake Wallet are yet to update to correct the issue, but a fix has been merged into the main Monero repository so hopefully these alternative wallets will see the importance of the issue and move to implement the improved decoy selection algorithm as a matter of priority.

Great credit must go to ‘Lacksfish’ for bringing this issue into the spotlight.