potential measures against a black marble attack

[chaserene]

updated: 2024-04-16

motivation

starting with March 4, 2024, Monero has experienced a sudden surge in on-chain transaction volume (15k-25k tx/day -> 115k-140k tx/day). as of April 16, the volume has waned, but there have been new spikes to levels that have rarely been breached during the months before the surge.

it has been known since the birth of the network (see Noether, et al: A Note on Chain Reactions in Traceability in CryptoNote 2.0 from 2014) that ring signatures as a method of obfuscating the transaction graph are vulnerable to an adversary flooding the network with transactions and progressively eliminating the decoys of honest users, thereby reducing their privacy in the graph, potentially to the point of identifying the real spend. following the above paper's terminology, this is called here a black marble attack, although it has other names as well, e.g. flood(ing) attack (from Chervinski, et al: Analysis of transaction flooding attacks against monero).

for an analysis of this event, see @Rucknium's paper March 2024 Suspected Black Marble Flooding Against Monero.

some in the community don't believe that the current situation is a black marble attack (attributing it to organic activity or other sources); others do. I posit that this is irrelevant, because of the following:

1. we can't prove it's not a black marble attack, and since Monero is primarily a tool for preserving privacy, we should err on the side of defensiveness. we don't have the luxury of assuming the optimistic scenario, since the downside is that people who rely on Monero are exposed to excess danger.
2. this situation is simply a reminder that such an attack is currently very practical and cheap in Monero, and serves as the best available opportunity to try to tackle it (that is, before an ultimate solution is deployed; see the "omitted measures" section below). if the current flood were to abruptly stop, the probability of a black marble attack would remain at least the same. if anything, this demonstration is rather an invitation for future attackers.

measures

the below is an informal summary of potential measures we are discussing that can counter such an attack, applicable to the Monero protocol in its current state (fork version v16, code name "Fluorine Fermi"). I will try to keep the information here in sync with the state of the discussion in the Monero Research Lab and Monero Research Lounge chat rooms.

since none of these measures solve the root issue, some of them can be thought of as temporary changes that can be reverted if/when Monero is upgraded to full-chain membership proofs (FCMP). most of them can be combined with each other.

measure	pro	con
do nothing	* avoids rushed decisions/mistakes that could make things worse and take an(other) fork to remedy * many of these interventions can be rendered ineffective if attacker has a lot of resources	* attacker can keep lowering the effective ring size at the same costs as now * we don't know how much resources an attacker has without trying to exhaust them (defeatism)
increase ring size	* tx's have more non-attacker decoys on average (in absolute terms); attacker may choose not to increase their tx volume in accordance (due to higher tx fee costs) * depending on ring size, can prepare the network for tx sizes under Seraphis (+ potentially FCMP)	* requires fork * higher node/wallet resource requirements * higher tx fees?
modify existing dynamic block size parameters	* attacker may reduce/stop their tx's due to higher tx fee costs	* requires fork * higher tx fees in general
introduce ultra-long-term sanity median	* attacker may eventually reduce/stop their tx's due higher tx fee costs	* requires fork * eventually higher tx fees in general * will have effect only on a very long time scale
increase "effective minimum tx fee"	* attacker may reduce/stop their tx's due to higher tx fee costs	* requires fork * higher tx fees
increase minimum node relay tx fee	* attacker may reduce/stop their tx's due to higher tx fee costs * can be activated without a fork	* requires fork to work effectively (otherwise nodes can stay on older version) * higher tx fees * attacker can coordinate with mining pools to get their tx's mined * same best-case outcome as with increasing the "effective minimum tx fee", but with the above added risk
introduce per-peer tx PoW for relay	* attacker may reduce/stop their tx's due to introduced hardware + electricity costs * can be activated without a fork	* attacker can coordinate with mining pools to get their tx's mined * higher wallet resource requirements; can price out senders with low-end hardware, expensive electricity and/or in hot climates
introduce tx PoW for inclusion in block	* attacker may reduce/stop their tx's due to introduced hardware + electricity costs	* requires fork * higher wallet resource requirements; can price out senders with low-end hardware, expensive electricity and/or in hot climates
reduce tx lifespan in tx pool	* less of an attacker's transactions may get mined * can be activated without a fork	* attacker can fine-tune the rate of tx broadcast to reach same inclusion rate * requires fork to work effectively (otherwise nodes can stay on older version) * attacker can coordinate with mining pools to get their tx's mined

omitted measures

measures discussed but omitted from the table because they don't seem to be (immediately) applicable:

• introduce full-chain membership proofs (FCMP) with Seraphis: FCMPs are the ultimate solution to attacks related to ring signatures, but they are currently not in a deployable state. ideally, they would be introduced together with the Seraphis transaction protocol. these two, presuming the current rate of progress won't change, are estimated to be ready in 5+ years.
• introduce FCMP on top of ring confidential transactions (RingCT): @kayabaNerve thinks it's feasible and desirable to deploy FCMP on top of the current transaction protocol (RingCT/CryptoNote), that is, before Seraphis. there is general support for this new direction. kayabaNerve's optimistic timeline for deploying such a setup is about 12 months. this would radically fast-track the statistical proofing of Monero's privacy, but still wouldn't make it applicable on the short/mid term.
• shift decoy selection distribution toward older enotes: this would make it easier in certain cases to guess the real spend, and any advantage would be eroded over time if an attack is sustained. this would also require a fork.
• counterattack: this would rely on honest participants conducting a counter-flood, keeping the resulting deanonymizing transaction data safe, and then securely erasing it. all these involve unverifiable actions (trust), and, unless perfectly coordinated among all participants, they would be unable to tell if an attack was over or not.
• miners limit the size of their blocks: this would limit the ratio of an attacker's enotes to all enotes in a block, but relies on altruism and well-enough coordination from miners.

[monerobull]

i like artics suggestion of raising the minimum fee to the level a standard transaction will cost in the future under FCMPs.

[mmgen]

Raising the minimum fee, along with the possible addition of transaction POW, seems like the easiest-to-implement and least disruptive interim solution to me.

[johnr365]

After reading through the March 20 MRL meeting, my vote would be for increasing the minimum transaction fee as a first step.

That doesn't preclude raising the ring size later, if needed, whilst waiting on FCMPs.

I saw that rbrunner, sech1 and Alex of Local Monero were against raising the minimum fee. Which does give me pause for thought. I'd like to hear more about their rationale not to.

One argument against raising minimum fees is that if Monero fiat value goes 10x then the fees may look too expensive, and would require another fork to correct.

But simultaneously, if Monero goes 10x, it's a nice problem to have, and the community can probably manage the small tweak needed to make fees more affordable.

[donttracemebruh]

I support raising the minimum fee with plans to revert the fee raise during the FCMP fork. Cheap fees make sense in a FCMP protocol, but cheap fees are detrimental to privacy under a ring signature protocol as rings have this spam attack weakness.

I would also support a ring increase, although I think it would be better to aim for something like 50% (or less) of the tx size under FCMPs, in order not to increase the blockchain size any more than we have to.

[tarris034otheracc]

Increase ring signatures, leave fees at current level as the attacker surely won't be affected by 10x fees and we will have to do another hard fork if we see 10x FIAT evaluation.

If the attacker is chainanalysis company, we would need to increase fees 100x to make a dent in their accounts.

[donttracemebruh]

Its about increasing the cost to attack. There will always be entities with seemingly unlimited resources that no amount of fees will ever deter. The goal should be to price out small to medium sized attackers while making miners more profitable and increasing network hashrate. Currently mining is very much not profitable to the point that a certain Monero fork is more profitable to mine and has surpassed Monero in hashrate. We shouldn't increase fees too drastically, but targeting fees of 1 cent to 5 cents for example would still be a negigible amount for most Monero users while drastically increasing miner's profits and the cost to spam the network.

[wallart1]

Just a random thought from a neophyte: How about building in a laundering system that would, in effect, increase the anonymity set by multiples for even non-linearly. Do the laundering in the nodes, making it distributed. And figure out some way to make the distribution random. God help you if coins get lost, and you need to figure out what happened.

I apologize if this has been considered already.

[molangning]

I’m not good with crypto stuff, but isn’t that technically a counter attack?

[wallart1]

I don't think it is. It's just a way to increase privacy.

Edit: Bitcoiners do it all the time, and the government hates it.

[Rucknium]

I have preliminary analysis of the possible black marble flood:

https://github.com/Rucknium/misc-research/blob/main/Monero-Black-Marble-Flood/pdf/monero-black-marble-flood.pdf

March 2024 Suspected Black Marble Flooding Against Monero: Privacy, User Experience, and Countermeasures

Abstract

On March 4, 2024, aggregate Monero transaction volume suddenly almost tripled. This note analyzes the effect of the large number of transactions, assuming that the transaction volume is an attempted black marble flooding attack by an adversary. According to my estimates, mean effective ring size has decreased from 16 to 5.5 if the black marble flooding hypothesis is correct. At current transaction volumes, the suspected spam transactions probably cannot be used for large-scale “chain reaction” analysis to eliminate all ring members except for the real spend. Effects of increasing Monero's ring size above 16 are analyzed.

[tarris034otheracc]

...The goal should be to price out small to medium sized attackers

In this case, more attackers that don't collude is better when it comes to black marble attack. (just saying)

Currently mining is very much not profitable....

Auto adjusting difficulty will take care of this, some miners will drop and some new will come.
I wouldn't worry about some premined fork taking over miners that could mine for Monero network, ALL premined projects rug pull eventually.

[ohaponiuk]

Can someone explain how introducing tx PoW would have a different effect than increasing the minimum tx fee? Fundamentally, a piece of Monero already represents that some PoW was done. So if someone is willing to make "tx PoW", they could just mine some monero (in case of increased minimum tx fee) and it would have the same exact effect. Except that if you can't mine it, you could just buy some, while in the case of tx PoW you're not able to. It worsens the user experience by removing this alternative, while the effect for an attacker would be ultimately the same as if the minimum tx fee was raised (if they have money to flood the network, they have money to rent powerful enough hardware to do the tx PoW required). In the end, I see no scenario where tx PoW would be preferable to raising the minimum tx fee.

[Gingeropolous]

you should indicate that 2 versions of the tx-pow exist. The one where PoW is block inclusion consensus (which requires a fork), and one that requires a PoW for relaying transactions (which does not require a fork).

they have money to rent powerful enough hardware to do the tx PoW required).

do they? It depends on how its done. The way I imagine tx-PoW is to require the PoW for relaying a transaction, and the diff requirements are dynamic per node connection.

Here I tried to put together a simulation and the flow of how it would work (the sim doesn't work because I can't code that well and I need a time multiplier so I can do more things in a day):
https://github.com/Gingeropolous/txsim/blob/main/prompt_flow_description.txt

But basically, your node tracks the transaction rate of every node you are connected to. In normal conditions, the PoW diff is so low as to not even be noticeable, even by phone users. Perhaps it takes 5-10 seconds to craft a PoW to package your tx for relay.

If your node starts receiving transactions way over some rolling average (or something), your node increases the PoW requirements in an exponential fashion. It can be designed that in a matter of seconds (10 seconds?), if so many transactions come in from a peer (who is clearly an attacker), the difficulty requirements skyrocket to the point where it would take many minutes for the attacker to craft a PoW for each tx.

So, this decreases the rate at which an attacker can actually submit txs to the network. Yes, it is still possible for the attacker to submit transactions, but the effort wall has been raised ... exponentially.

To me, the only downside is the critique proposed by articmine, where low-end users wouldn't be able to submit txs during an attack. I attempt to mitigate this by creating a re-packaging process, whereby nodes can re-package a tx with a new PoW to facilitate relay in instances where they receive txs with low diff from a "friendly" node connection (one that has a low rate of txs etc).

[chaserene]

@Gingeropolous

you should indicate that 2 versions of the tx-pow exist. The one where PoW is block inclusion consensus (which requires a fork), and one that requires a PoW for relaying transactions (which does not require a fork).

that's a very good point. I split it up into two entries in the table in the OP.

[hundehausen]

@Gingeropolous do all nodes increase their PoW requirements, or only the node receiving the spike in transaction? What stops the attacker from switching to the next node to relay the transactions, where the PoW requirement is still low? Or what about the attacker using a new tor circuit or other proxy server to relay their txs?

[Gingeropolous]

do all nodes increase their PoW requirements, or only the node receiving the spike in transaction?

Only the node receiving the spike in txs

What stops the attacker from switching to the next node to relay the transactions, where the PoW requirement is still low?

Nothing, but nodes have connection limits. I've witnessed plenty of incoming connection denials to my nodes due to my node being at its connection limit.

Or what about the attacker using a new tor circuit or other proxy server to relay their txs?

I think at some point, whatever the tor circuit or proxy, you're going to hit the connection limit of a node.

All of these moving parts is why I wanted to build a simulation for this.

[tevador]

The way I imagine tx-PoW is to require the PoW for relaying a transaction

It should be noted that Monero already has an indirect PoW requirement for relaying transactions. Because we use CPU-friendly PoW for mining, you can convert tx fees to equivalent CPU hashes. With the current network hashrate, a 1/2 transaction with the minimum relay fee needs about the equivalent of 12 000 000 RandomX hashes. To put that into perspective, a relatively powerful PC can do around 10 000 hashes per second, so we are talking about 20 minutes of PoW to submit one transaction.

With that in mind, we can clearly see that any "5-10 second PoW to submit a tx" makes little sense in comparison with the necessary transaction fee. Equivalent functionality would be achieved by simply adjusting the minimum relay fee.

[Gingeropolous]

I get what you're saying, but the fee as currently designed doesn't create a per-node rate limiter, which is what a PoW could do.

Much the same way in which PoW essentially rate-limits block production, we could use it to rate limit the amount of transactions your node will receive from a single peer.

Like, the spam attacks probably operated as such: Attacker Alice spins up some nodes (A1-An) and then relays transactions to whichever nodes they happened to connect to, nodes B1-Bn. So B1-Bn went from the standard trickle of transactions it would receive for relay to hundreds of transactions per second, perhaps thousands.

If Alice had to craft a Pow for each transactions, and the difficulty of the PoW increased as they tried to send thousands of transactions to the node they are connected to...

then yes they'll hop to another node, but they will also get rate limited there, expending more work.

In the current system, the attacker is only limited by IP address space. If there was dynamic PoW for relay, the attacker is limited by compute space.

at least thats how it makes sense in my head.

again, sure if we could make the tx fee dynamically related to a per node thing, then we could just do this with fees....

but we could also make the tx-pow where the sender actually mines on a block for the receiver.... well that could get complicated.

• edited to add - i was on some thought train about some flaws, but then i realized that node A can have a bundle of txs and negotiate relay with node B using the cumulative PoW. That could help in a scenario where the attacker tried to stall the network by driving up the difficulty.

[wallart1]

I don't understand why one wouldn't just set a tx rate limit as a node setting and ban any node that insists on exceeding it. Maybe one could be nice and put some back pressure in the protocol. Otherwise ban the bastard if he refuses to play by the rules.

[Gingeropolous]

Because the tx rate limit needs to change in response to the demand. Like the blocksize.

And also, a simple rate limit would allow the attacker to just get more IP addresses to make more connections.