• Forum has been upgraded, all links, images, etc are as they were. Please see Official Announcements for more information

Security Advisory for CoinShuffle and Darkwallet

Very interesting post.
Just a point about the vulnerability through change linking. This scenario is a possible interpretation but not the only one. Imagine that instead of Alice sending 0.7 and receiving 0.3 for change, we have Bob sending 0.3 to Alice and Alice merging this 0.3 with her previous 0.2 change...
You may consider that the probability of this scenario is low compared to the scenario described in your post, but this probability is not zero which leads to the general conclusion that results obtained from blockchain analysis are often probabilistic and rarely give 100% certainty.
 
Very interesting post.
Just a point about the vulnerability through change linking. This scenario is a possible interpretation but not the only one. Imagine that instead of Alice sending 0.7 and receiving 0.3 for change, we have Bob sending 0.3 to Alice and Alice merging this 0.3 with her previous 0.2 change...
You may consider that the probability of this scenario is low compared to the scenario described in your post, but this probability is not zero which leads to the general conclusion that results obtained from blockchain analysis are often probabilistic and rarely give 100% certainty.

I have to agree that with this kind of analysis, while some things might be highly unlikely, they are not impossible.
I also think these kinds of scenarios are really important to find and possibly use the unlikelyness of them happening for further development. In fact I see a lot of chances with such things.

For example: the same way you described this scenario of being of "low probability" it it also highly unlikely that during the process, there are less than 3, even less than 2 actual participants.
Bob, Alice and Charlie are just pseudonyms which can be created by any one entity in an unlimited amount.
Therefore, it is totally possible that Bob an Alice are the same person. It is even possible that all 3 of them are the same person, even if it is highly unlikely. However, this information can be used to construct a transaction with only one person participating but for the public it would seem like it was a normal mixing transaction with 3 people participating (if funds are not directly linked beforehand / have been anonymized beforehand).
Such a transaction could be forged offline, without the need of peers and without the need of other entities willing to mix at the same time.

By changing how likely it is for such an event to happen, the chance of successfully de-anonymizing the transaction can be changed.
If my example would become standard behavior of most clients and happened with a certain probability for each mixing round, then, by looking at a transaction, one could not say that it is highly likely that there have actually been 3 entities participating in the mixing.
So while before it was highly unlikely to not make the right assumptions about the amount of participants, it now has become a lot more likely to do so, which adds to anonymity/plausible denyability.

Going back to your example:
- the 3 pseudonyms may or may not belong to 3 different entities
- therefore, "payments" between them might not be actual payments, but them rearranging/mixing their funds
- regardless of the amount of entities participating and regardless of bob and alice being one person or 2 different persons, there will be either a change of 0.3 or a change of 0.7 which can be used for further tracing and which has to be accounted for.
- in case of them being 3 different entities (however likely that is in the environment this mixing transaction occurred), a payment of 0.3 from bob to alice would be leaving 0.7 change for bob, which can, when spent, be used to trace him, while the 0.3 could be traced to the 0.5 Tx alice is doing in combination with her 0.2.

I conclude: While we cannot know with a 100% probability which output is the change and which output is the payment, once any of them is combined with another output in order to facilitate a payment in a single Tx, we can trace that other input of said Tx.
In the case of bob sending alice 0.3, he cannot use his remaining 0.7 in conjunction with any other funds he owns without potentially leaking information that can be used to trade him.
In the case of alice sending the 0.7, she cannot use his remaining 0.3 in conjunction with any other funds she owns without potentially leaking information that can be used to trade her.
In the case of alice sending the 0.3...

The solution to this is to not output the change at all, therefore making it miners fees. In case of the change being a non-trivial amount, I see 2 options to not lose it:

1.) Mixing smaller denomination amounts so there will be less change lost. This is how it is currently done with Darksend and comes with the following disadvantages:
- if there are no small amounts left, you have the same problem again
- because of this, there have to be many small denominations readily available which unnecessarily bloats the blockchain.

2.)
- Payment mixing transactions. This is part of why I pushed for denomination convertibility so hard:
A payment mixing transaction does 2 things at once: It mixes coins and it simultaneously allows the participants to spend coins. In order for this to work, denomination convertibility is required.
It works just like a normal mixing transaction but instead participants who want to pay someone in this Tx will put the receivers address as an output address and assigns it the required amount of coins. This can be any amount including non-denomination amounts. denominations will be converted in order to have the least non-denominated change, which is then used as a miners fee to prevent Dead Change from occurring.
An Example:

Alice has 3 denominations of 10 DRK and wants to pay 5 DRK anonymously. Because this would leave Dead Change of 5 DRK, which she does not want to forfeit, she decides to do it via a payment mixing tx (Or "Payment Darksend Transaction"):
She cooperates with 2 other participants which both want some 10 DRK and some 1 DRK outputs.
She enters the mixing with 3x 10DRK and assigns 5 DRK to the payees address. She assigns to herself 2x 10 DRK and 5x 1 DRK.

because others also requested outputs of 10 DRK and 1DRK, the "change" cannot be traced directly to Alice.

This has the following advantages over 1.):
- Alice does not lose the change
- It requires only one transaction for mixing some coins and paying someone. This reduces blockchain bloat
Disadvantages:
- Alice has to wait for mixing partners and cannot instantly pay. However with the method described above (the 3 participants not always being 3 different entities), Alice could set a time cap after which, if no mixing partners have been found, she will mix with other anonymized coins of herself without the use of a masternode. An observer would not be able to tell the difference. between this and a regular mixing round.
Extra!:
With InstantX this could be pushed to the limit. She could wait until the payment almost expired and then send a fully confirmed Tx this way using IX


Edit: Wow this somehow turned into a proposal for DS development :D
 
Last edited by a moderator:
Very interesting thoughts.

Wrt using coinjoin for payments, I mean that by doing this, you automatically avoid the case of a user merging change from coinjoin tx with change from tx done after the coinjoin tx (alice in first example of OP).

This point seems important to me because the main source of weakness for anonymity is often human (aka the user). Of course, it raises the problem of "coincidence of needs" (it's highly unlikely that 2 users want to pay the same amount at the same time). In spite of its limitations, dark wallet has a nice approach for this, by mixing coins from a payer and a provider, the mixed amount being decided by the needs of the payer (it's just sad that they don't insert more obfuscation of changes by using some standardized denominations as it's done in DS but I'm almost sure it will be done in a future release).

Another approach for payment might be to use the model of cash instead of the model of electronic payments:
- With electronic payment systems, payment of amount M is associated to a single line in the "book" with this non-standardized amount. You have: M = 1 * M
- With cash, your payment is done in one transaction but is split among several standardized denominations (coins & bank-notes): You have: M = a_1 * M1 + a_2 * M2 + ... + a_n * Mn
With this model, a crypto-payment could be done in one (coinjoin) transaction but would be split in several utxos, all with standardized denominations & sent to different addresses (controlled by the payee). It might require a specific payment protocol allowing the payer to notify the payee about tx and utxos concerned by her payment but it doesn't seem as the most difficult part. I don't know Darkcoin vey well but it seems to me that this model fits its philosophy of standardized denominations to improve priacy. Anyway, I'm just speaking loud ;)

Wrt to complexity of coinjoin, I could not agree more. I've been working on the subject for a while and the study of its "mechanics" reveals an incredible complexity if you want to analyze it (subset sum + matching problems).
 
Sorry for deleting my previous post. When I read over it, I felt like it doesn't add anything new to the discussion because it basically only rephrased what I wrote in the post before it. I didn't know you were in the process of answering to it, else I would have let it there.

Using multiple receiving addresses for different denominations is an interesting idea. However, I think this could be susceptible to timing analysis. Then again this wouldn't make it any less anonymous than the current implementation.
Thats something to think about. Thanks for the input.
 
Using multiple receiving addresses for different denominations is an interesting idea. However, I think this could be susceptible to timing analysis. Then again this wouldn't make it any less anonymous than the current implementation.
Thats something to think about. Thanks for the input.
Just gave some more thought to this idea.

I'm not sure if it's what you call timing analysis but a potential flaw is that split outputs may increase the probability of merge inputs when the payee use the received utxos. Even if we imagine that all txs (payment or pure mixing) are coinjoin txs, a heuristic might be to check if some inputs come from a same previous coinjoin tx and thus to consider that they're controlled by a same entity.

If I'm correct, the quality of this heuristic should increase with the number of users (the probability that 2 users "collide" in chained coinjoin txs should decrease with #users).

Another "proof" that coinjoin is a complex beast ! ;)
 
Just gave some more thought to this idea.

I'm not sure if it's what you call timing analysis but a potential flaw is that split outputs may increase the probability of merge inputs when the payee use the received utxos. Even if we imagine that all txs (payment or pure mixing) are coinjoin txs, a heuristic might be to check if some inputs come from a same previous coinjoin tx and thus to consider that they're controlled by a same entity.

If I'm correct, the quality of this heuristic should increase with the number of users (the probability that 2 users "collide" in chained coinjoin txs should decrease with #users).

Another "proof" that coinjoin is a complex beast ! ;)

Nice find!
Every output would have to be flagged and outputs that are flagged as being used as a combined payment cannot be used in a single Tx.
However, regarding blockchain analysis, they could still be used for a single payment if the payment is of the same nature as the one before, because that that would not make them appear in a single Tx but in multiple Txs that all are part of that one payment.
The problem with this is that the receiver of that 2nd Tx would know about that, which would be another problem.

But thats now what I meant. By Timing attack I mean that, using such a Payment Tx, one could look at Transactions that are sent at the same time. Because they come from the same source, a node should receive all the single Transactions at the same time or at nearly the same.
This could be used as part of an analysis because if makes it a lot more likely that these belong together. It cannot be used by itself to unmask the origin of the funds, but as part of an analysis it has a huge impact.
 
Back
Top