The publication of a new investigation related to an abnormal transaction flood -viewed by some as an attempted trace attack – on the Monero network has some users worried that larger entities with a large budget can trace and de-anonymize some transactions en masse in the future. But did you know that these worries were dismissed by Monero developers two years earlier when a similar scheme was detailed by a then-recently published academic research paper?
2019 – FloodXMR research paper published
On May 2019, researchers published a scholarly article titled FloodXMR: Low-cost transaction flooding attack with Monero’s bulletproof protocol. The article claims that “an attacker can trace up to 47.63% of the transaction inputs at a cost of just 1,746.53 USD”. This was done by abusing Monero’s bulletproof protocol – which mainly reduces transaction fees – to insert a sufficiently large number of the attacker’s transactions into the Monero network, such that mixins are removed from the transaction input.
Preliminary definitions you must know
The mixin count is described in Monero Stack Exchange as “the number of other signatures (aside from yours) in the ring signature that authorizes the transaction”.
“The mixin count refers to the number of other signatures (aside from yours) in the ring signature that authorizes the transaction. A default mixin of 4 means that there are 5 total signatures. Someone looking at a transaction with a mixin of 4 has no way of knowing which of the five signers is the true sender”Monero Stack Exchange, originallly from Bitcointalk
A transaction ring, also known as “RingCT” or “Ring Confidential Transactions”, refers to the process of inserting dummy outputs inside a Monero transaction. One feature of this is that assuming a transaction has one input, public keys of these outputs are multiples of the generator point
G, that add up together with the one for the “real” output to get the value for the transaction input.
In other words, Monero inserts decoy outputs inside its transactions in an attempt to obfuscate the transaction recipient. Also note that Monero uses two pairs of keys, one of which is used for spending – in the transaction signing algorithm, the other is used to make a unique address.
It turns out that decoy keys are sampled from the “Key Images” of transaction inputs in recent, past transactions. (Source).
Finally, a “bulletproof” here refers to the proof that is written inside the raw transaction that is later included in a block. Before bulletproofs were implemented, Monero transactions included the size of the UTXO set – which is all the outputs in a transaction – in its weight, and this was reflected in the transaction fees.
After bulletproofs were deployed on October 18, 2018, Monero transactions only counted the size of unspent output – hence a logarithm of the UTXO set – as the transaction weight and hence fee. Critically, this means that decoy ring outputs are not included in the transaction weight and fee. Hence, bulletproofs save massively on transaction fees – but this does not apply to Monero “flood” transactions with lots of outputs. This has lead people to say that transaction fees increase logarithmically for regular transactions.
The minimum transaction fee will increase as the size of Monero blocks exceeds the minimum block size limit. Miners (and mining pools) are incentivized to include fewer transactions in their blocks to avoid bringing about large network fees, meaning fewer Monero flood transactions at a time can be included in a block. This makes it even harder – but not impossible – to perform a Monero trace attack.
At the time the paper was written, Monero used a fixed amount of 10 decoy keys, which allowed the authors to trace nearly half of the payment keys – and hence transaction inputs. A previous version of Monero used up to 6 decoy keys, a slight majority proportion of which consisted of 6-decoy-key transactions.
The Monero trace attack works something like this: If an attacker creates a large enough number of Monero transactions with many transaction inputs, then eventually the Key Images belonging to the attacker’s transaction inputs will eventually start to appear in legitimate transactions. Obviously, some transactions will contain more than one “real” input, and the aim is to analyze the past blockchain history to look for Key Images of transaction inputs that appear in earlier transactions prior to the one being traced. This enables one to determine which transaction inputs are decoys.
In simpler terms: The attacker makes a large number of transactions with a fixed number of outputs (for example, 99) and saves their key images into a list. Make enough transactions, and you have enough key images to reliably identify and mark decoy keys.
Also, the percentage of deanonymized transactions increases the longer – as in more months – the Monero trace attack is carried out.
To maximize the efficiency of the attack, new output keys must be created
every day. Based on our experimental observations, one simple, yet effective,
strategy for the attacker is to analyze the number of output keys generated
during the last 24 hours and then create the appropriate number of keys based
on the percentage of the keys that s/he wishes to control. For example, if 5,000
keys were created during the past 24 hours and the attacker wishes to control
75% of the outputs, then 15,000 new outputs must be created. This strategy
should be followed until the end of the attack.
Chervinski, Kreutz, and Yu – FloodXMR: Low-cost transaction flooding attack with Monero’s bulletproof protocol
Note that it was mentioned in the paper that the Monero trace attack was simulated (by using historic Monero data from block 1,499,601 to block 1,761,435 – Feb 1, 2018 to Feb 1, 2019), to avoid disruption in Monero transactions, but that doesn’t invalidate the results of the research, since many impossible-to-perform scientific situations are also simulated.
Monero Community Reacts To FloodXMR Paper
This paper was posted to the r/Monero subreddit on Reddit (Archived) where it was met by criticism from several readers, and a few Monero developers. Some of the replies at the top of the page have been published below.
The paper is incorrect insofar as it assumes transactions with 100 outputs are feasible, whereas Monero limits the amount of outputs to 16. The paper also does not factor in that fees increase if the (dynamic) block size limit is reached. That being said, the general conclusions of this paper may be relevant for Monero. The Monero Research Lab is currently discussing them and I think it would be best to wait until they reach a conclusion.u/dEBRUYNE_1 – Reddit
The paper also appears to assume that fees scale purely with transaction size, which is not the case. Therefore, the claims of logarithmic fee progression are also incorrect. That being said, the general idea of mass output control affecting privacy is valid and has been known for years. I hope the authors update the paper to correct the assumptions so the data are accurate.u/SarangNoether – Reddit
As has been already pointed out above this paper fails to account for significant anti-spam measures that are present in Monero.
1) Limitation of number of outputs to 16 per transaction.
2) The use of transaction weight as opposed to size to determine the penalty formula and hence fees. The weight formula “claws back” ~80% of the fee savings from the logarithmic scaling of transaction size with number of outputs that would have occurred for transactions between 3 and 16 outputs.
The effect of 1) and 2) is that the paper needs to use 16 output translations and calculate the cost based upon the transaction weight that is used for penalty and fee determination.
3) The cost analysis fails to take into account even the cost of doubling the block weight from the ham level,. This is required to achieve ~50% output control. For 90% control one needs 10x the blocksize. To place things into perspective. To move the effective median blockweight from 300000 bytes to 600000 bytes for just one block by maxing out the penalty with rational miners one needs 4x the block reward over 50 blocks. This works out to -560 XMR and we have not even started. They also fail to take into account the recent changes to fight a very similar spam bloating attack, described as Big Bang.
Edit 1: To put this mildly they are no even close to getting started, let alone maintaining the attack for a year as claimed.
Edit 2: Given the relatively slight advantage of using 16 output transaction the attacker might just as well use 2 output transactions. A flood of 16 output transactions is a dead giveaway that something is going on.u/ArticMine – XMR Core Team – Reddit
The number of chain reactions seems abnormally high by a very large margin. The explanation for this is that the authors ran simulations on a data sample sufficiently in the past, so that many rings were smaller than 11 (the mandatory standard now), when it was down to 4. (See the top of page 10).
What is dubious is that they then phrase all their results as something that could be applied nowadays. Personally I believe, do to the consistency with which they do so, that the authors deliberately try to inflate the relevance and importance of their results.
Here are some examples from the conclusion:
“Simulation results shown that by executing the proposed attack, a malicious actor […] in a one year time frame is able to trace 47.63% of all transaction inputs created in the sametime period.”
This is false. This is not “in a one year time frame”, it is only “in that particular time frame” that the authors chose. Which by the way is in the past and the protocol changes (ring size increase) make it irrelevant today unless you can travel in time.
“The results show the existence of vulnerabilites on Monero’s privacy mechanisms, with emphasis on the recently launched Bulletproof protocol which was essential to making the proposed attack cost effective.“
This is hilarious because bulletproof did not exist in the time frame they chose for their data sample, oops. Yet they even put it in the title.
A proper conclusion of the paper: “IF you had a time machine, and IF you could use bulletproof transactions before they existed, and IF you would perform this attack in the past when rings were smaller, then you could have done X”.u/binaryFate – XMR Core Team – Reddit
The general theme around these replies is that while the existence of such an attack is acknowledged, the researchers have made errors in their cost analysis for this attack – mainly the limitation of 16 outputs per transaction instead of 99, and that the fees scale if the block size limit is reached – therefore the results of the paper are largely dismissed. This theme will be revisited in the next section.
2021 – A Monero Transaction Flood Happens
Around mid-July this year, users noticed a significant uptick in the number of transactions. This activity was investigated by the Monero Research Lab and the results were published on Medium. The summary of this research is that there were a large number of Monero flood transactions with 1 to 2 inputs. The transactions were created from the Monero core wallet, using a large set of unspent transaction outputs (UTXOs).
Also, while before, the RingCT protocol would only occasionally use decoys from blocks less than 50 blocks old, several transaction rings included a transaction from within the last 15 blocks, while the flood was happening.
Many of the generated outputs were spent again, enabling them to be included in transaction rings as decoys (emphasis ours):
So far, we have mostly focused on aggregate statistics and counts, without even touching on ancestry analysis. Due to the volume and speed of the anomaly, it is likely that many of the rings can be deanonymized (i.e. we can identify which was the true spend versus decoys). We already have traction by knowing the anomaly fingerprint, which allows us to rule out ring members that don’t match the signature. Contextually, ring members from freshly converted coinbases can also be ruled out. The fact that transaction generation was so rapid (see section 2b) is also detrimental to the anomaly’s privacy. Since a vast number of transactions were generated with an extremely fast spend time (outputs typically being consumed 10–15 blocks after creation), it is likely that the guess-newest heuristic will be very effective.Mitchell P. Krawiec-Thayer, Monero Research Lab – Medium
These research findings have also speculated the transaction costs to be around 5 XMR (about $1000 at the time the research findings were written), about 0.000015 XMR per transaction – however, the author warns that this cost analysis was also speculative and made “assumptions that could introduce significant error”.
These findings were posted yesterday to Reddit (Archived). While no Monero Developers have commented on this matter as of this writing, it was promptly noted by another user that the percentage increase in the number of transactions (100%) was not enough to carry out a Monero trace attack (1000%) – which we should note is the kind of trace mentioned in the previous section.
However, despite both cost analyses being speculative, this flood serves as a warning to the Monero community that – with a sufficiently large, nefarious mining pool and an entity with a large enough budget and UTXO set (think Chainalysis or the NSA using 8 figures in USD, or loads of seized cryptocurrency), this kind of trace attack on the Monero network could be possible.
Editors note: this is a sponsored post and does not necessarily reflect the views of NotATether.com.