Can Monero ever achieve private transactions?

If privacy is a game of cat and mouse, who's winning Monero's game?

• Monero's CryptoNote protocol is potentially vulnerable to various kinds of attacks. It is not completely anonymous.
• Several attacks used in tandem can de-anonymise a lot of Monero transactions.
• Monero is not the only cryptocurrency to have these kinds of issues.

As Monero lead maintainer Riccardo Spagni has said on occasion, privacy isn't just something you achieve. Rather, it's a constant game of cat and mouse.

In this case the cats and mice are locked in an arms race. The mice want to remain anonymous, the cats want to unveil the mice, and both are always looking for newer and better ways of getting what they want.

So, what are Monero's cats and mice up to these days?

Also watch

Background

Monero, and a range of other cryptocurrencies and blockchain projects that want to ensure privacy, use something called the CryptoNote protocol to facilitate private transactions. In this case, private means you can't identify individual users or transactions the way you can with Bitcoin.

For any of this to make sense, you'll need to know the basics of how CryptoNote works.

Tugging at threads

Breaking CryptoNote privacy is essentially done by finding a starting point, and then pulling on that thread to unravel the privacy of other transactions.

"If you know the payer and payee in a system you can trace the entire money flow... at least with the classic blockchain," explains Jiangshan Yu, cybersecurity researcher at Monash and one of the world's foremost unravellers of CryptoNote threads.

Monero's ongoing evolutions in the cat and mouse game of privacy have been largely informed by Yu's research, and he's been working with the team at Monero to improve the protocol when he discovers new vulnerabilities.

His starting point for unravelling CryptoNote privacy is based on the fact that mixins have to be real transactions. Using real transactions as decoys is a clever solution to the very tricky problem of privacy on a verifiable public ledger, but it also presents a potential entry point for anyone who wants to follow the money in Monero.

Mixin match

Because coins can only be spent once, when you can identify a single real transaction among the decoys with 100% certainty, you can say for sure it's a mixin when you see it crop up again. And while you can make it harder to track simply by adding more mixins, this also comes with downsides.

"The drawback of the system is that the more decoy input you add into the single transaction, the larger the transaction will be unless you pay more fees. And it's slowing down the system as well," Yu explains.

This meant that for a long time most Monero users would simply elect to not use any decoys at all. It made transactions cheaper, but it also meant that whenever someone actually did want to use Monero for privacy:

• a) Their transaction with all its decoys would stand out like a sore thumb.
• b) It was easy to identify the mixins, because most of them had previously been spent as the real output in a transaction with no mixins.

The real problem with that is that once you can start identifying the real transactions among the decoys, you can identify those transactions as decoys elsewhere and it all snowballs from there. This snowball effect is how you can go from de-anonymising a small handful of transactions to mapping out large chunks of the network.

In Monero security researcher lingo this is known as the "cascade effect".

And it's pretty dramatic. Zero mixin transactions were banned from Monero in 2016, but as of February 2017, around 65% of all Monero transactions to date still had zero mixins and therefore were not anonymous. The cascade effect could then be used to de-anonymise a further 22% of Monero transactions.

So at that time around 87% of Monero inputs could be de-anonymised with relatively little effort. That's probably bad news for someone.

The good news

The good news is that those numbers are getting much better as time passes, and according to Yu's findings Monero is still head and shoulders above many other CryptoNote coins thanks to its ongoing improvements.

One of them was to enforce a more sufficient number of mandatory mixins on all transactions.

"Several years ago they put enforcement on the number of mixins you should have in the system," Yu said. "From that point every transaction should have at least that number of mixins... so the average transaction now should have [a ring size of] 11."

This has been a gradual increase as people probe the anonymity offered by different ring sizes. Zero mixin transactions were banned in 2016, then in 2018 the mandatory ring size was incrementally upped from 5 to 7 to 11. Also in 2018, Monero developers eliminated the feature which let users choose their own ring size, to prevent people from unwittingly giving attackers a new entry point by consistently choosing the same unconventional ring size.

The bad news

The bad news is that this doesn't mean CryptoNote's problems are solved. In true cat and mouse fashion, Monero's ongoing improvements mean security researchers are finding newer and more sophisticated holes.

For example, last year a team managed to de-anonymise an estimated 80% or so of Monero transactions by identifying the fact that the newest Monero transaction was also disproportionately likely to be the real one, and then combining that with the cascade effect.

And Yu's team managed to get over 70% as of March 2018 with a new flavour of brute force-style attack. The same method picked up about 75% of ByteCoin transactions, and over 90% of DigitalNote transactions, in a similar timeframe.

"Our [new] attack is about another thing," Yu says, "which is that even though there are no zero mixin transactions in the system at all – even if this is not happening – we can still identify the real spend of a transaction. This is more complicated than the previous one."

Closed set attacks

In CryptoNote, every mixin has to be a real spend somewhere else. So as you can imagine, someone with an infinite amount of time and computing power could theoretically identify the real spend in a number of transactions through the power of sheer number crunching.

It would be prohibitively expensive though. Closed set attacks are a way around this cost barrier, to a certain extent.

It's essentially a more efficient formula for achieving the same result, which allowed Yu to carry out a practical brute force attack of sorts on Monero. It lets attackers identify the real transaction to kickstart the cascade effect even when people are using multiple mixins in their transactions.

A closed set is built on analysis of transactions, which here refers to both the bundle of mixins and the real spend which make up a Monero transaction. This bundle of transactions is called a closed set when the number of transactions in the set is equal to the number of different public keys included in the same set.

It's probably easier to visualise with an example.

The table below shows what a very simple closed set might look like.

This is a closed set because the number of transactions (four in this case) is equal to the number of different public keys found in the same group (also four: a, b, c and d).

"Since we know that each coin can only be spent once and each transaction can only be a unique coin, a, b, c must be the real input of each transaction [from Transaction 1 to Transaction 3]" Yu explains. "We don't know which one is the real one but we do know that one must be real."

"So we can tick a, b and c off from the fourth transaction, and d is naturally the real spend of that transaction."

So the closed set attack is literally just an algorithm for discovering all available closed sets – up to a certain size – in CryptoNote blockchains at any given time. You can then use that information to pick out certain obvious decoys and real transactions, and see if you can kick start a cascade effect even without any zero mixin transactions.

"Later on if another coin used, say, a, b, c, d, e, then e will be identified as the real spend of that transaction," Yu says. "And this is the cascade effect, since the one you've chosen is already identified, basically the mixin does not help in this case."

In real life, when this algorithm was applied to Monero, it found over 3,000 closed sets, containing 7,478 distinct public keys. This essentially renders all those public keys useless as mixins.

Larger ring sizes help, "but it doesn't really address the problem," Yu says. "[The risk] is lower now, but still possible to have such a thing. The minimum number of mixins is 11. I think we were chatting with the Monero team – they are going to release a new enforcement on the number of mixins."

But you can't really keep upping the default ring size forever.

"The more mixins, the more expensive the transaction fee would be," Yu notes. "So you also need to consider this."

Instead, you need to rethink how exactly CryptoNote picks its mixins. One starting point would be to avoid using any of those 7,500 odd public keys as mixins. Another would be for users to generate a bunch of zero value transactions simply to create more public keys to use as mixins elsewhere.

It's still not ideal though.

Active inference attacks

Yu also detailed a considerably simpler but more active attack vector. Because the decoys use the public keys from real transactions, you can obviously identify your own transaction public keys as decoys when they appear in someone else's transaction.

"This is the active attack we found which is presented in the Sun Zu paper," Yu said.

It's fairly straightforward. You simply create a bunch of transactions, and then wait for someone else to use the keys from those transactions as mixins. With a concerted enough effort, there will be people whose mixins were 100% created by you, so you can instantly tell which transaction is the real one. Do that a bit, and you have a new entry point for the cascade effect.

But creating enough transactions to do that would be super expensive, right? Nah, it's actually very reasonably priced, Yu says.

"So we actually calculated the cost of dominating all the coins," Yu says. "You only pay a few hundred dollars for the selections in the last few weeks [and] most of the possible mixins to be selected will be from us."

"It's affordable because you simply transfer money to yourself. A few hundred dollars for the last few weeks."

A few hundred bucks to effectively de-anonymise a few weeks of Monero transactions isn't especially high security.

To make matters worse

It doesn't help that there are quite a lot of Monero forks.

"One interesting thing is that when there is a hard fork you double your money, so your coin is riding on either branch," Yu explains. "If you claim your coin on both branches you need to use your key twice... so you can apply the same attacks on multiple Monero forks... we can already identify some transactions in the new forks."

So every fork brings new opportunities to unmask transactions and extrapolate that information to the main fork.

And remember, all of these kinds of attacks can be applied in tandem. You can start with pulling the thread of those old zero mixin transactions, then apply the closed set algorithm to unveil a whole lot more, and can then follow it up by spending a few hundred bucks to seed the network with your own public addresses. If you want to go even further you can apply these techniques to Monero as well as all its active forks, for a more complete picture.

And all the while, the cascade effect is working in your favour.

And CryptoNote is bigger than Monero alone, Yu emphasises. If Monero is the most capable CryptoNote coin, how well will any of the others fare against these kinds of attacks?

"It's not only Monero. It's the whole type of the protocol which is called CryptoNote," he said. "There are several different implementations of the protocol and Monero is one of them – and probably is the most available one so far. There are probably another at least 7 or 8 other systems. Not all of them are cryptocurrencies, but there are other blockchain applications in different fields."

It's not too crazy to believe someone, somewhere has been mapping Monero transactions in detail for a long time now.

"When I was in the Caribbean, there was a colleague in the States saying the US government, and similarly the Australian DOD – can't remember exactly which department – is asking for proposals to provide tools for blockchain forensics for Zcash and Monero," Yu recalls. "So they could give you funding to do the research, to build up a tool for them to trace the money."

Can Monero's cryptocurrency's mice ever beat the cats?

CryptoNote as a protocol is from the early days of cryptocurrency. It was devised in 2013 by the (presumably) pseudonymous Nicolas van Saberhagen, and it was the first concerted effort to implement workable privacy measures on the blockchain.

But can its framework ever be stretched far enough to bring true privacy, or does the entire system of using ring signatures for privacy fall apart under real world conditions? Will there ever come a time to retire Monero and its ring signatures, or will its mice continually stay just enough steps ahead of the cats?

And to what extent are other well-known cryptocurrencies burdened with similar issues?

As a security researcher, Yu has probably seen a little too much to be anything but ambivalent about most cryptocurrencies out there. It's also worth noting that security researchers are the ones who know about vulnerabilities before they become public knowledge, and Yu alluded to a lot of cybersecurity icebergs beneath the surface of the blockchain industry as a whole.

"There are many pitfalls in the system design and if you are not the expert, and if you are not careful enough, there are too many attacks and too many mistakes you can make," he said. "So I'm pretty worried about the current state of the blockchain. I do believe blockchain has a future, but not in its current form."

"There should be better and stronger regulation on the design part. Even Microsoft can't make Windows secure, so we definitely need to have some control there as well."

And there's no shortage of evidence to say people should probably be a bit warier with their faith in the current state of blockchain.

Even looking at money printing bugs alone finds a fairly extensive list of past issues.

For example, Zcash was vulnerable to a money printing bug from birth to earlier this year, while Stellar fell victim to a money printing exploit in 2017. Even Bitcoin had a money printing vulnerability for a while in late 2018.

So, how many of the top 20 cryptocurrencies right now have major security issues?

"You'd be surprised," Yu says.

Blockchain is still in early days, which means that for all its high tech chops it's still very primitive in many ways.

Disclosure: The author holds BTC at the time of writing.