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
