DoS Defense

[AdamISZ]

One way to deal with DOS attacks of the form 'start but don't complete the protocol': some variant of complete-with-subset.

In Coinshuffle they have a rather involved "blame" protocol to address this, meaning if one party doesn't follow protocol, they can kind of 'unwind' the steps and then re-complete. In Joinmarket we just use a much simpler approach of the Taker constructing a smaller CJ tx if say 1 out of 5 counterparties does not provide the necessary data.

But I don't believe there's a trick to stop the DOS attack of 'don't provide the signature at the end'; best one can do is handle it by rewinding and creating the tx template again.

But anyway, I don't really understand what you mean in Dos 1 and Dos 2 by "ban" (e.g. for one month as suggested). Are you banning a utxo (often we'd just be talking 1)? That doesn't appear to be worth much?

As for banning output reuse, sure that's necessary, we have that too.

(If you are banning a fixed pseudonymous identity it brings in a whole can of worms that we generally don't want to bring in, I guess you don't mean that.)

We have a kind of rate-limiting prevent-excessive-retrying feature in JM based "proof of discrete log equivalence" but don't want to stray off topic.

Generally I think this anti-DOS stuff is very hard. To whatever extent a complete-with-subset approach can work it's desirable, I think.

[nopara73]

complete-with-subset

I don't want to do such thing, because that'd lower the anonimity set, it's more straightforward to completely restart the round if someone doesn't play by the rules.
And the round is pretty fast so shouldn't be a problem restarting it.
On the other hand it could make DoS attacks more expensive. I will think about it.

But anyway, I don't really understand what you mean in Dos 1 and Dos 2 by "ban" (e.g. for one month as suggested). Are you banning a utxo (often we'd just be talking 1)?

Yes banning the utxos Alice provided at input registration phase. I will clarify it.

That doesn't appear to be worth much?

I am not sure how strong the ban should be. You could play with the time of banning and the transaction chain, like you can ban all the children of the utxo's parents and or all the children of the utxo.
I will clarify this, too. As I said I am not sure how strong the ban should be and the Tumbler can evolve its defense over time to be more resilient.

[AdamISZ]

Re: the round is pretty fast:

sure agreed but how long do the clients need to be online? If the clients are all there, synchronously, it can all be done at once, and can be restarted, but if it's based on gathering participants over time, or using epochs for different stages in various ways, it's harder right. I don't have a clear picture yet, just kind of thinking aloud.

[nopara73]

but how long do the clients need to be online?

Assuming malicious actors at Output Registration phase: 1 minute
Assuming malicous actors at signing phase: 1.1 minute (0.1 minute for signing and submitting the signature).
Otherwise maybe half a minute?

There are 4 phases:

1. Input Registration
2. Connection Confirmation
3. Output Registration
4. Signing

Output Registration and Signing has 1-1 minutes timeout.

The Input Registration phase can take quite long at the beginning while the wallet doesn't have sufficient liquidity, so if they disconnect during the process, so be it, they will not be present at connection confirmation. Which will result a fall back to Input Registration until everyone is present for Connection Confirmation.
So they can disconnect here without penalty, except during Output Registration and Signing phases.

(ToDo: clarify it in doc)

[nopara73]

I sufficiently addressed unclear parts and evolved the DoS protection model. 3557528
bb52ca7

I am still thinking about the "complete-with-subset" model you suggested. It'd surely help, but I am not sure its benefits justifies its complexity.

We have a kind of rate-limiting prevent-excessive-retrying feature in JM based "proof of discrete log equivalence" but don't want to stray off topic.

Where can I read more about it?

The good thing is whenever there's a problem, only the Tumbler must be updated and no need to update clients.

Some brainstorming here: I think one could utilize @gmaxwell's switching network scheme paired with the "complete-with-subset".

Isn't the anonymity set size limited by how many parties you can get in a single transaction?

Not quite. The anonymity set size of a single transaction is limited by the number of parties in it, obviously. And transaction size limits as well as failure (retry) risk mean that really huge joint transactions would not be wise. But because these transactions are cheap, there is no limit to the number of transactions you can cascade.

In particular, if you have can build transactions with m participants per transaction you can create a sequence of m*3 transactions which form a three-stage switching network that permits any of m^2 final outputs to have come from any of m^2 original inputs (e.g. using three stages of 32 transactions with 32 inputs each 1024 users can be joined with a total of 96 transactions). This allows the anonymity set to be any size, limited only by participation.

[nopara73]

@AdamISZ I think I solved the DoS issue. How about this?

I'll refer to "sibling outputs", "child outputs" and "parent outputs" for the shake of simplicity according to the illustration:

So I will refer to not only the direct childs as child outputs, but also the sibling output's direct childs as child outputs of the output. Similarly at the parents output, I will call the siblings of the parents as also parents, sorry I'm a little short on english words and terminology here.

A basic strategy when malice detected is to ban with a one month timeout: all first child outputs, sibling outputs, first parents outputs and all the first childs of first parent outputs.

This should be sufficient to scare away most attacker. However a sophisticated attacker could simply make another transaction, that falls out of being first child output. For reason if attack is attempted again based on this pattern Tumbler must ban all child outputs for a month (future outputs of course). The Tumbler must ban all the childs of the output the attack is attempted in the first time and not the second time.

After this the only thing the attacker can do is to pre-divide its coins to the denomination before even getting banned (or after the one month ban expired). And keep attacking.
As I detailed in the document, it turnes out if the attacker is very sophisticated it can push out the rounds to take maximum for 3 minutes, therefore to keep up an attack for one day they would need (24*(60/3)/2 = 240 bitcoins, supposing 1 bitcoin denomination. The division with 2 is because it can reattack with the same coins after it makes another transaction to become second child from first child.
Of course this would also require to make him do around a thousand transaction so the attacker not only have to have 240 coins for a day attack, but also spend approx. $1000, supposing $1 transaction fees.

I don't see how this could be played.

[AdamISZ]

Where can I read more about it?

https://joinmarket.me/blog/blog/poodle/ is a summary of the technical idea.

I'll read your above idea again later. Generally I'd not previously seriously considered bans of children or generally related-to utxos ... ironically coinjoin itself is a serious potential flaw in that approach, right :)

As for switching networks, I'd note again that @chris-belcher 's tumbler algo design is of course an approach based on that general idea, too. So it's something people are somewhat familiar with, in that context. It is easier to analyse in an all-equal-output version though.

And I agree that that is the general approach to ameliorate small anonymity sets, whether due to having used a complete-with-subset approach or otherwise.

[nopara73]

coinjoin itself is a serious potential flaw in that approach

I'm not sure what you mean by that. There might be two concernes comes to mind, I detailed the first one in the protocol:

If the output being used to attack is coming out of tumbling the Tumbler SHOULD proceed with the banning normally. It is not a problem to ban tumbled outputs, becase they SHOULD NOT be tumbled again. Tumbling them again would mean those outputs are being joined together with other outputs, what SHOULD NOT be allowed with a post-mix wallet.

The second one is brings up the question: is there is any way to lose the track of the coins on blockchain? Yes, every day the attacker must send 240 bitcoins into a mixer/exchange and then withdraw different ones. That's just silly.

[nopara73]

@AdamISZ I documented this solution in the main document, probably more clearly than in this issue. If you cannot poke holes in it I will close this issue.

[AdamISZ]

@nopara73 Sorry only paying intermittent attention. About:

If the output being used to attack is coming out of tumbling the Tumbler SHOULD proceed with the banning normally. It is not a problem to ban tumbled outputs, becase they SHOULD NOT be tumbled again. Tumbling them again would mean those outputs are being joined together with other outputs, what SHOULD NOT be allowed with a post-mix wallet

Forgive me if I'm being dense, but isn't that the whole idea of switching networks? To use tumbled outs as inputs to new tumbles? I must have misunderstood something.

Generally when I was saying "coinjoin is a flaw" I was thinking, if you ban related utxos it must be because you're deducing common ownership of either (groups of inputs) or (outputs from a set of inputs), but come to think of it, any bitcoin tx, not just coinjoin, makes the latter unsafe, right?

I've been reading the section in the main document, but I'm struggling to understand the details precisely. For example:

When malicious Alice is detected Tumbler SHOULD ban all the outputs Alice registered with and all their (-1)., 0. and 1. generation related outputs. Of course only the ban of unspent utxos are needed, spent ones cannot be registered anyway. Tumbler SHOULD also extend the bans to future, not yet created outputs.

For example, what exactly does it mean to "ban all the ... -1 generation related outputs" here? IIUC the -1 generation here means the transaction that funded the coinjoin we're dealing with now, which I think is the "0" generation here. But they're spent? Or ...?

As another example, I cannot parse this sentence; perhaps it's missing a comma? Not sure:

In this case the 0. generation outputs are not the malicious outputs' generation those are used to disrupt a round the second time, but the first time.

Sorry I know this is probably annoying, but it's a combination of (1) I don't understand exactly what you're saying and (2) I'm having a hard time believing a "related outputs" approach makes sense.

[nopara73]

As another example, I cannot parse this sentence; perhaps it's missing a comma? Not sure:
In this case the 0. generation outputs are not the malicious outputs' generation those are used to disrupt a round the second time, but the first time.

From another point of view there are 2 bans.

1. If an attack happens the first time 3 generations of outputs are banned: -1,0,1
2. If an attack happens the second time with an output that's a descendant of an already banned output, that means the attacker is persistent. In this case we identify the output that was malicious the first time and extend the ban to all the remaining generations down the road: 2, 3, 4, 5....

The reason why all generations are not outright banned down the road, because honest users can get coins from malicious attackers and if the attacker isn't willing to make 2 transactions to get out of banned generation (from 0 to 1, from 1 to 2) to disrupt one more round.

Why the parent generation (-1) comes from the same user? In order to disrupt as many rounds as you can, you must divide your coins into denomination first. Nobody has 240 bitcoins that happens to be evenly divided to the denomination.

Forgive me if I'm being dense, but isn't that the whole idea of switching networks? To use tumbled outs as inputs to new tumbles? I must have misunderstood something.

Switching networks are not used here.

Generally when I was saying "coinjoin is a flaw" I was thinking, if you ban related utxos it must be because you're deducing common ownership of either (groups of inputs) or (outputs from a set of inputs), but come to think of it, any bitcoin tx, not just coinjoin, makes the latter unsafe, right?

By unsafe you mean "pain in the ass"? If someone gets his coins from an attacker it cannot use them for one month.

For example, what exactly does it mean to "ban all the ... -1 generation related outputs" here? IIUC the -1 generation here means the transaction that funded the coinjoin we're dealing with now, which I think is the "0" generation here. But they're spent? Or ...?

I think the generation model made it easier to understand what I previously tried to illustrate with "parents, parents' childs, siblings, etc...".

IIUC the -1 generation here means the transaction that funded the coinjoin we're dealing with now

The transaction that funded the malicious output. Keep in mind malicious output is only detected when a CoinJoin did not happen. If the CoinJoin happen, the round is not disrupted, therefore the ouput is not malicious.
The 0. generation is always the generation where the malicious output is found.

I will do further work on clarification, I really thought I finally got it clear.

[nopara73]

@AdamISZ I will carefully refactor, clarify and explain the DoS protection. Maybe put this topic on hold until I finished the work. Hopefully you can understand easily after that.

[nopara73]

@AdamISZ I realized there is no need to go to such lenghts, a simpler utxo banning strategy is sufficiently expensive in a $1 Bitcoin fee environment. ($500usd per day) This might be the reason why you did not consider related utxo banning in JoinMarket. At the time you developed it there was a zero-fee environment, where my DoS protection would fail.

https://github.com/nopara73/ZeroLink#d-defending-against-dos-attacks

[AdamISZ]

What we did in JM was coming from a different direction: we were concerned that snooping was costless, snooping here being Taker requesting Maker utxos to build txs then not building the txs and just recording utxos owned by Makers, to try to unmix in future. In that context, we wanted to impose a rate-limiting cost on requesting a join, which I implemented using the PoDLE construction above. It limits use of any particular utxo as a "3 time usage token" (can be extended to any N), and usage is also restricted to be at least 20% of size of coinjoin.

Note that because it's p2p we had to have a "banning" mechanism that was broadcastable across peers (podle gives required privacy for that to work).

Btw this was not just theoretical; that attack was in active use in mid 2016, and after the above rules were added, the attacks stopped.

With a Chaumian server you don't have those concerns (certainly, not in the same way, in any case).

The DOS concern in a JM model though is from the Maker side, since the Taker is the customer so to speak, and against that we currently only have complete-with-subset. There are some related ideas but no one has gone further than some discussions on that. Don't want to bog down with irrelevant details here.

I say all that to get to the point: we never considered banning utxos used in coinjoins as such, just rate-limiting as per above. Any ban would have to be global across peers, and see above about podle/privacy.

[chris-belcher]

I was reading the google docs document and thought of another way to make DOS more costly, which is to use a fidelity bond. I used the same idea when thinking about anti-DOS for coinswap but didn't use that name.

Basically all the parties have to send bitcoins to a time-locked address, and they show that UTXO and redeemScript to everyone else before beginning the protocol. That UTXO can then be banned if the owner ends up DOSing. This doesn't rely on high miner fees like simply banning UTXOs, but it does mean the users need to own more bitcoins than they intend to mix (e.g. to mix 1btc they need to own 1.5btc if the fidelity bond is for 0.5btc). Although the time-locked UTXO could be used for many successive coinjoins as long as it doesn't get banned.

I've written a little about the idea here https://en.bitcoin.it/wiki/Fidelity_bonds#Temporary_Fidelity_Bond

Edit: in case it's interesting, here is one of my (more complicated because of the 'punishment fee') anti-DOS schemes for coinswap JoinMarket-Org/joinmarket#335 (comment)

Edit2: There is also @AdamISZ 's scheme of "pay to contract hash" which we came up as an antiDOS idea in JoinMarket at one point: https://gist.github.com/AdamISZ/9cbba5e9408d23813ca8#defence-3-pay-to-contract-hash

[nopara73]

@chris-belcher Unfortunately fidelity bonds would require the user to have more money in its wallet, than it can mix, which ruins user experience, but also it would result longer rounds if we assume non-zero confirmations. I added the idea to the document, however as long as I am confident about my DoS solution I flagged it with a "SHOULD NOT" keyword.

[wintercooled]

Regarding: "Tumbler must ban all child outputs for a month (future outputs of course)"

If you ban a certain txout from being an input and also it's siblings would the following not allow for an attack on potential users?:

An attacker joins a round but fails to sign repeatedly and gets banned. This is their intention.
They then spam dust to the known addresses of their target user.
Should the target user submit an output referencing the banned output at some point in its history they will not be able to use the service.
So by doing this a malicious users can force other txouts to be banned? Unless I have misunderstood the ban.

Also - if Bob sends me BTC and I get banned will his txouts also not get banned by prior association?

I may have misunderstood so apologies if I have.

[wintercooled]

Regarding my last comment I see this has been addressed: "The issue is increasing severity might result in banning honest actors out of the mix: if honest actors get their coins from malicious ones, therefore severity should be kept at level two and only to be increased if needed."

[nopara73]

Right, additionally the Tumbler can evolve its DoS protection if ever needed. For example: there can be a dust limit for bans.

[nopara73]

@wintercooled I just realized it's not an issue at all. Bitcoin addresses are not banned, only utxos. So the attacker can send one satoshi to all the bitcoin addresses in the world, the wallets will never register those outputs into a CoinJoin.

[wintercooled]

If you ban child utxos though... If you only have 1btc in utxo1 and I send you 0.0001btc and you at a later date send 1.0001 BTC which forms a new utxo that utxo might be banned because of the previous association with my banned utxo no? If you don't limit parent/child depth it might result in me being banned. So we could limit it by depth to look back I guess.

…

On 21 Oct 2017 14:57, "nopara73" ***@***.***> wrote: @wintercooled <https://github.com/wintercooled> I just realized it's not an issue at all. Bitcoin addresses are not banned, only utxos. So the attacker can send to one satoshi to all the bitcoin addresses in the world, the wallets will never register those outputs into a CoinJoin. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#6 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AYgLfRAA9pK_pKlnEOz8uZqTxjcShtIUks5sufhNgaJpZM4OopvG> .

[wintercooled]

REF: https://bitcointalk.org/index.php?topic=279249.0 "As I write this people with unknown motivations are raining down tiny little payments on old addresses, presumably in an effort to get wallets to consume them and create evidence of common address ownership." On 21 October 2017 at 15:32, Matthew Haywood < [email protected]> wrote:

…

If you ban child utxos though... If you only have 1btc in utxo1 and I send you 0.0001btc and you at a later date send 1.0001 BTC which forms a new utxo that utxo might be banned because of the previous association with my banned utxo no? If you don't limit parent/child depth it might result in me being banned. So we could limit it by depth to look back I guess. On 21 Oct 2017 14:57, "nopara73" ***@***.***> wrote: > @wintercooled <https://github.com/wintercooled> I just realized it's not > an issue at all. Bitcoin addresses are not banned, only utxos. So the > attacker can send to one satoshi to all the bitcoin addresses in the world, > the wallets will never register those outputs into a CoinJoin. > > — > You are receiving this because you were mentioned. > Reply to this email directly, view it on GitHub > <#6 (comment)>, > or mute the thread > <https://github.com/notifications/unsubscribe-auth/AYgLfRAA9pK_pKlnEOz8uZqTxjcShtIUks5sufhNgaJpZM4OopvG> > . >

[nopara73]

No. Consider this:

You see, it's the same address, but yet the utxos are unrelated from a banning point of view.

[wintercooled]

What if they consolidated into one utxo and then later that becomes the input to our ccj. So 1 and 0.0001 become the inputs to a new output. That output becomes the input to a CCJ tx. That new output is now tainted with a past history involving the banned utxo.

…

On 21 Oct 2017 16:01, "nopara73" ***@***.***> wrote: No. Consider this: <https://camo.githubusercontent.com/0e5f068cfd67a828a13e4ec4185fc55d13d27516/68747470733a2f2f692e696d6775722e636f6d2f6171353865624c2e706e67> You see, it's the same address, but yet they are unrelated from a banning point of view. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#6 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AYgLfTN8s2JxUDNBmNIL4XGnxWtfmLd0ks5sugdHgaJpZM4OopvG> .

[wintercooled]

[image: Inline images 1] On 21 October 2017 at 16:51, Matthew Haywood < [email protected]> wrote:

…

What if they consolidated into one utxo and then later that becomes the input to our ccj. So 1 and 0.0001 become the inputs to a new output. That output becomes the input to a CCJ tx. That new output is now tainted with a past history involving the banned utxo. On 21 Oct 2017 16:01, "nopara73" ***@***.***> wrote: > No. Consider this: > > > <https://camo.githubusercontent.com/0e5f068cfd67a828a13e4ec4185fc55d13d27516/68747470733a2f2f692e696d6775722e636f6d2f6171353865624c2e706e67> > > You see, it's the same address, but yet they are unrelated from a banning > point of view. > > — > You are receiving this because you were mentioned. > Reply to this email directly, view it on GitHub > <#6 (comment)>, > or mute the thread > <https://github.com/notifications/unsubscribe-auth/AYgLfTN8s2JxUDNBmNIL4XGnxWtfmLd0ks5sugdHgaJpZM4OopvG> > . >

[nopara73]

Note: If you added an image through email, it doesn't appear on GitHub.
All I can see is this:

[image: Inline images 1]

Administration aside. There are multiple things to consider here.

How often do wallets join inputs together?

Maybe 30%?

How wallets select inputs?

When they have not enough money on one input to fund the transaction, they'll add another input that's the smallest, but still can fund the transaction.
How often will dusts be selected as additional inputs TO CoinJoin transacions? Never?

Now we are there that the attacker must send people considerable amount of Bitcoins to have a 10-20% chance of making them getting banned.

Who to target?

But the attacker first have to figure out its targets. Mass targeting will never be possible, because the attacker has no way to know who will want to participate in CoinJoin transactions in the future.
But let's say the attacker has a specific target and knows all his bitcoin addresses and sends considerable amount to them.

Target is rich

If the target is rich there is no way he wouldn't be able to do a bunch of CoinJoin transactions, before it would consider to join malicious inputs into the transaction.
But let's say the target is poor, the attacker knows all the bitcoin addresses of the target and the attacker is willing to enrich with considerable amount of banned utxos to the target.

What does the attacker achieve?

10% chance of one month ban on one poor target, while also enriching the target.

[nopara73]

Problem

Bitcoin fees are low again. Chaumian CoinJoin's DoS protection assumes 1$ fees.

Idea

Introducing mixing fees as DoS protection.

How It Works

When user selects how much it wants to mix, it'll buy mixing tickets from the server. Zero-conf transaction is fine for this. It can be done with blind signatures. (User creates some ticket, for some bitcoin it makes the tickets signed blindly.)

These signed tickets can be stored locally, and used whenever the user wants to participate in a mix.

Conclusions

If the user doesn't sign, it loses its money to the server. The DoS protection can be hardened by one simple parameter.
It also exposes how many round that specific input is participating, which may result in much more privacy problems (eg. BC analysis can figure out all the ticket paying transactions may lead to unexpected information leak.)

Extension: Accidentally build Chaumian e-cash:

1. If the tickets can be used for other purposes (eg. buy different functionality in the wallet) then the information leak is probably insignificant, since BC analysis cannot assume a ticket was used to buy mixing participation.
2. Make the tickets transferable: send the ticket directly to another user, the user asks for reissuance of the ticket from the server, so the sender won't have access to it anymore.
3. Provide a ticket buy-back option, so users would be sure (as long as they trust the company) that the tickets will be bought back and get bitcoins for it.

This way the company would accidentally build Chaumian e-cash, which has a level of privacy as cash that no cryptocurrency can hope to achieve.