Spam attack to gain control of many outputs and undermine privacy

Question

Would it be possible for an attacker to send many transactions to himself with the goal of gaining control of many outputs for the purposes of deanonymizing transactions of others (using low mixins with most outputs sometimes controlled by the attacker) later?

What would be the cost of spamming the network to gain control of 20% of the network outputs today? What about 40% or 60%?

If Monero usage to date already makes this attack prohibitively expensive would it be a concern for another CryptoNote coin (that may be brand new or still has low numbers of existing outputs)? When the network has low levels of available outputs can an attacker gain control of a large percentage of network outputs relatively cheaply?

Is it true that RingCT will allow ring outputs to be comprised of any denomination? Would this mean that it would make it harder for an attacker to gain control of a significant percentage of network outputs compared to pre-RingCT where outputs were grouped by ^10 denominations (and the attacker could focus on gaining control of outputs of specific denomination)?

Answer 1

We can get a rough idea of a cost lower bound by doing the following:

This command looks at the tx_outputs database, which lists all the outputs on the blockchain:

mdb_stat -s tx_outputs ~/.bitmonerod/lmdb

We see that this database holds 17896556 entries. In order to get 20% of the entries, an attacker would have to create about 4.5 million new outputs (100 * 4.5 / (17.9+4.5) == 20). An output requires at least a 32 byte public key on the blockchain, so that'd mean a total of 144 MB to be added. At a cost of 0.01 monero/kB, that gives you a lower bound of 1406 monero in tx fees.

Now, this is a lower bound. You'd need more data. Each transaction needs at least one input (at least one 64 byte signature). The 32 byte public key is not the only thing that is needed per vout (at least 2 extra bytes).

In order to get 40%, you'd need 12 million extra outputs (3750 monero lower bound), and in order to get 60%, you'd need 27 million extra outputs (8437 monero lower bound).

If you want to concentrate on a given denomination, the same reasoning applies, with a twist: there are currently 812877 outputs of size 10 monero. But in that case, you will need to include change (or waste a lot of monero, or have a lot of monero in the first place). In the original case, I took the best case: you take an input of yours, and you divide it into as many outputs as the transaction will allow, quantize, and throw away the rest. I assumed you could perfectly quantize (the varint encoding takes just a byte) and you threw away nothing (otherwise it adds up to the tx fees). Now, if you want all your outputs to be a useful size (for instance, 10 monero), then you need to recover the remainders after splitting, in order to use them as inputs to a subsequent tx, as that remainder is now a significant amount of monero. As example: a 60 kB transaction can hold at most 1875 outputs (using 32 byte per output again, so an overestimate). If you have a single 20000 monero input, you can make 1875 new outputs of size 10, and you have 1250 monero left. You don't want to lose them, so you pay them as change, and then need to consolidate them with other change as inputs for a later tx. All that adds overhead to the amount of data you have to pay for.

Now, the chain is not going to wait, so an adversary will need to get more than that, especially if they want to keep that threshold. If the outputs are created as a one off, the adversary will own less and less of the total outputs are the chain grows.

If such a sustained attack were to happen, transaction fees would most likely be temporarily increased, which would make the cost go up by as much.

RingCT will indeed avoid the need to split amounts by denominations, and any RingCT input will be able to mix with any other. RingCT transaction size will also get larger per output (but also need less inputs). So creating a lot of outputs will cost more, too.

Answer 2

This is a legitimate concern for centrally controlled CryptoNote coins such as Bytecoin (BCN). Approximately 80% of BCN had already been mined as of the time it became known to most of the cryptocurrency community in 2014.

Assuming one person or a small group controlled all of the outputs generated up to that point the attack you describe is a very real risk. With very small trade volume and a lack of merchant adoption the blockchain transactions of BCN are extremely likely to be an automated attempt to fake activity. In effect the practice continues to ensure centralized control of available outputs.

The fair launch, emission curve and large community of Monero helps ensure that centralized control such as described above will not be a problem for XMR.