The Attack of the Black Marble – BitcoinBlog.de – the blog for Bitcoin and other virtual currencies

In March, Monero (XMR) fell victim to a wave of spam. Behind this was a specific attack that attempted to break the anonymity of ring signatures. We explain what happened.

During March there was a spam attack on the privacycoin Monero that apparently tried to make transactions a little less anonymous.

In some ways, the spam wave represented the most sophisticated attempt yet to break the cryptocurrency’s most sophisticated anonymity. So we have reached the highest peak in the technological war for privacy, where the adversaries, attackers and defenders, also treat each other with respect.

It won’t be easy for us as laypeople to understand what happened – but it’s still a celebration. On the surface, this is what happened: in early March, the number of standard transactions jumped from about 15,000 a day to more than 100,000, and remained at this level for most of the month. The size of the blocks, which are found every two minutes, reached a threshold of 300 kilobytes, after which a dynamic adjustment mechanism took effect, which gently increased the size of the blocks.

The Monero community suspects that it was a “black marble” attack, as described by developer Rucknium. To understand it in principle, you have to know that Monero uses so-called ring signatures.

The difference between transactions in Bitcoin and Monero

We have to elaborate a little bit here: A Bitcoin transaction takes an input – a so-called UTXO (unspent transaction output) – and sends it as an output to a receiver. With a signature, the sender proves that it is the owner of the input; The chain of signed inputs connects the addresses, making it easy to follow the money trail.

With Monero this chain is broken. A transmitter does not use a single input, but rather a “ring” of valid inputs. Among these is his own, but also others that he randomly selects on the blockchain. With his signature, the sender only proves that he has the key for one of these inputs, but not for which one. The ring size indicates how many inputs it uses. She is currently 16 by default.

The ring signatures make it more or less impossible to identify the sender and receiver in a transaction. However, they are only part of Monero’s privacy set: stealth addresses ensure that the recipient’s address remains unknown, zero knowledge proofs hide the amount sent.

In this set, ring signatures are the weakest link. This is also due to the Black Marble attack that was observed in March.

Black marble

If you understand how ring signatures work, the Black Marble attack is easy to understand: you spam the blockchain with transactions in order to have as many outputs as possible. These can then be excluded from the rings of other transactions, which reduces their effective ring size.

One advantage of the attack is that the algorithm used to form a wallet into the ring favors newer outputs.

The name of the attack comes from the fact that the process of elimination is reminiscent of drawing a black marble through hypergeometric distributions. The specific formula is too much math for this point, but it indicates how high an attacker’s chance is of shrinking other rings to the point where the transaction flow can be reasonably understood.

This way you can calculate what the effective ring size was during the spam attack. As Monero researcher Rucknium shows, it dropped relatively quickly from 16 to five or six, while the attacker owned 75 percent of all fresh outputs.

Effectively, the attacker could guess what the true input of a transaction was with a probability of about one in five. Monero, in other words, has largely held up.

Future scenarios

You could now lean back and breathe out. Rucknium still simulates the long-term scenarios. What happens if the attacker not only fills 300 kilobytes, but also 500, 1000 or 2000? Do the ring signatures still hold?

This shows that with the current standard ring size of 16, the effective ring size drops to 4 from 500 kilobytes and to two from around 1000. From now on, an attacker could safely guess who sent many transactions and even more with reasonable probability.

If, on the other hand, the ring size were increased to 40 or 60, it would still be largely safe even with 2000 kilobytes of spam per block. However, this would have the disadvantage that the transactions would become significantly larger.

One of the problems with the Black Marble attack is that it is relatively cheap. According to Rucknium, the entire wave of spam only cost between 61.5 and 81.3 Monero (XMR), depending on which fee models the attacker used (which cannot be determined exactly because Monero is anonymous). That’s around 6500-9000 euros, which isn’t really much for a 23-day attack.

However, the costs of a more extensive attack are likely to be significantly more expensive. Because as soon as the 300 kilobyte threshold per block is cracked, the fees increase significantly.

Problems for users

The ring signatures survived the attack relatively well. Theoretically you can break them, but only temporarily, and then you have to invest a lot of money.

Nevertheless, the Monero community is already considering increasing the ring size to 64. In addition, with “Full Chain Membership Proofs”, it already has a concept at hand that can replace the ring signatures and which, after the attack, will now be used earlier than expected, possibly in six to twelve months.

A more unpleasant consequence of the attack could affect the usability of Monero. Many users saw their transactions stuck in the mempool; Significantly delayed confirmations occurred throughout most of the month, sometimes escalating to up to two hours.

What was probably even more unpleasant was that most of the remote nodes were hopelessly overloaded. Users who do not have a full node dock their wallets to these. For them, Monero was now almost unusable.

Both the problem with remote nodes and delayed transactions can be solved with better software, for example by improving fee calculation or querying the mempool more effectively.

But another problem is more difficult to solve: the attacker created more than three gigabytes of outputs for a few thousand euros – which are never deleted again because there is no consensus as to when an output was actually used. The Monero blockchain can be inflated with relatively moderate amounts to such an extent that almost every operation on it is massively impaired.

Privacy is hard and competitive. It is not a state that one has achieved once, but that one must continually maintain.