Dead Change - an anonymity issue

[Aswan]

Hello,

I think I have found a flaw with Darksend mixed coins anonymity which I am going to call "Dead change" in reference to Zombies which, if they stay dead, it's fine, but once they start moving they are gonna infest everyone whos in the same room/town with them.
If this issue is already known under another name - so be it

First of all, the issue with Darksend being marketed as a strong anonymity feature is that a lot of people will use darksend and therefore neglect other things to protect their identity. Once there is problem with Darksend, the anonymity might be broken completely because of that.
However, Darksend also wants to be an easy to use feature that people do not need to know much about in order to use it. Because of this, there has to be clear how many funds are anonymous and how many are not. With the current implementation, this is not the case.

Imagine mixing some coins (let's make it 20 Coins for this example, so thats 2 x 10.00000001 DRK). You now go ahead and spend 15 coins on something that you really cannot afford to be linked to you in any way. Fair enough, you can do that, but that will create a transaction using the 20.00000002 Coins, giving 15 of the to whoever you buy something from and giving 5.00000002 back to you as change. This change is "Dead Change".

It is highly important to keep in mind that the change (the 5.00000002 coins) is now tied to the purchase. Whatever you do with those coins can be traced back to your 15 coins purchase. Say you want to send them to an exchange, buy something else from another site etc. You have to be really careful what you do with them. Putting them on an exchange might lead to the exchange getting questioned about what you did with them. They might (have to) tell someone that you exchanged them to Bitcoins and that you sent your bitcoins to address X which belongs to.. lets say, coinbase, which has your real name etc. and suddenly your identity is tied to the purchase.
Another scenario would be that you just want to send all your DRK to your new wallet and you think it doesn't matter which funds you use because you will re-mix them before using anyway, so you combine mixed and non-mixed funds which ties the 15 coins purchase to your actual address that is probably associated with you. All because that 5.00000002 coins dead change was in there.
And there are a lot more things that can happen because of this.

As with Zombies, dead better stays dead. If you but it into a room (a transaction) with healthy (anonymized, unused) people (denominations), they are all gonna be infested (tied to a purchase / de-anonymized).
It's even worse. Unlike Zombies, Dead changes can infest each other if being used in a chain or if being combined resulting in even less anonymity / more ties to purchases.

The problem is that the dead change shouldn't be in the "anonymous coins pool" anymore. But they cannot be in the normal pool as well because then they might get used in a transaction with your non-mixed coins which is even worse. The question is, is it enough to have a 3rd pool for change?
The answer is no, because in crypto, Zombies infest each other. The change of several transactions would link them all together when being spent. Thats just as bad as leaving it in the "anonymous coins pool". Potentially even worse.
So the dead change that cannot be spent because otherwise the anonymity of the spending transaction might be compromised.

In the current implementation this can be prevented by not created change of mixed coins at all. This can be done by using up the whole input either by paying larger fees or by sending more DRK that one is supposed to. If money is sent to an exchange, send 100.00000001 anonymized coins instead of 100 or 95. Send 10.00000001 coins instead of 8.5 etc.

But thats not a good solution, it's just what we have to work with right now. In the example with the 5.00000002 Coins dead change, this change could re-enter Darksend mixing with other already mixed funds in order to make 4 x 1.00000001, which would leave 0.99999998 DRK of dead change behind while the rest is being re-anonymized.
However, the 0.99999998 DRK won't ever be spendable without possibly breaking anonymity. It can be donated though, if it's the only input of the donation Tx.

This is why I AGAIN suggest denomination convertibility. That means making the Darksend denominations be 1, 10, 100 etc instead of 1.00000001, 10.00000001 etc. Also, smaller denominations like 0.1 would be nice to have.
That way Dead change that accumulates over time can easily be re-anonymized without bloating the blockchain too much by combining 10 dead change re-anonymized denominations into the next bigger one. With the current implementation that is not possible as it would leave behind 0.00000009 DRK.
With denomination convertibility, there wouldn't be a leftover.

I hope there will be something implemented to prevent this from happening in the future. If not my solution suggestion, then hopefully something better.

Thanks for reading,
Aswan

 

[Ignition75]

An excellent piece of analysis, I did however, have to read it twice

 

[Aswan]

An excellent piece of analysis, I did however, have to read it twice

I'm sorry if there are some things unclear. What made you haveing to read it twice? Maybe I can edit some things.

 

[Ignition75]

I'm sorry if there are some things unclear. What made you haveing to read it twice? Maybe I can edit some things.

Nothing was unclear, I panic read it at the start quickly, then read it properly

 

[Aswan]

haha, alright

 

[UdjinM6]

That's an interesting read and I like "zombie-style" of it

But honestly I don't see what's the problem with change.
Suppose you have 100 anonymized DRKs. You pay 15 DRKs using Darksend transaction = you spend 20 anonymized DRKs and you get 5 DRKs of non-anonymized change. So now you have 80 anonymized DRKs and 5 non-anonymized DRKs. Now you have to mix 5 non-anonymized DRKs to be able to use them privately again.
Where is the problem?

 

[JGCMiner]

That's an interesting read and I like "zombie-style" of it

But honestly I don't see what's the problem with change.
Suppose you have 100 anonymized DRKs. You pay 15 DRKs using Darksend transaction = you spend 20 anonymized DRKs and you get 5 DRKs of non-anonymized change. So now you have 80 anonymized DRKs and 5 non-anonymized DRKs. Now you have to mix 5 non-anonymized DRKs to be able to use them privately again.
Where is the problem?

I think Aswan is referring to a situation where the change is less than 1 and thus cannot be remixed. Furthermore, due to the use of 10.00000001 as a denomination rather 10, if you try to combine change less than 1 to get to a denominable amount you will always end up with a few "duffs" left over.

Frankly, I have not thought about it enough to say that I agree that the current method will ALWAYS leave change that can't be anonymized, but that is my understanding of the post.

 

[eduffield]

Hello,

I think I have found a flaw with Darksend mixed coins anonymity which I am going to call "Dead change" in reference to Zombies which, if they stay dead, it's fine, but once they start moving they are gonna infest everyone whos in the same room/town with them.
If this issue is already known under another name - so be it

First of all, the issue with Darksend being marketed as a strong anonymity feature is that a lot of people will use darksend and therefore neglect other things to protect their identity. Once there is problem with Darksend, the anonymity might be broken completely because of that.
However, Darksend also wants to be an easy to use feature that people do not need to know much about in order to use it. Because of this, there has to be clear how many funds are anonymous and how many are not. With the current implementation, this is not the case.

Imagine mixing some coins (let's make it 20 Coins for this example, so thats 2 x 10.00000001 DRK). You now go ahead and spend 15 coins on something that you really cannot afford to be linked to you in any way. Fair enough, you can do that, but that will create a transaction using the 20.00000002 Coins, giving 15 of the to whoever you buy something from and giving 5.00000002 back to you as change. This change is "Dead Change".

It is highly important to keep in mind that the change (the 5.00000002 coins) is now tied to the purchase. Whatever you do with those coins can be traced back to your 15 coins purchase. Say you want to send them to an exchange, buy something else from another site etc. You have to be really careful what you do with them. Putting them on an exchange might lead to the exchange getting questioned about what you did with them. They might (have to) tell someone that you exchanged them to Bitcoins and that you sent your bitcoins to address X which belongs to.. lets say, coinbase, which has your real name etc. and suddenly your identity is tied to the purchase.
Another scenario would be that you just want to send all your DRK to your new wallet and you think it doesn't matter which funds you use because you will re-mix them before using anyway, so you combine mixed and non-mixed funds which ties the 15 coins purchase to your actual address that is probably associated with you. All because that 5.00000002 coins dead change was in there.
And there are a lot more things that can happen because of this.

As with Zombies, dead better stays dead. If you but it into a room (a transaction) with healthy (anonymized, unused) people (denominations), they are all gonna be infested (tied to a purchase / de-anonymized).
It's even worse. Unlike Zombies, Dead changes can infest each other if being used in a chain or if being combined resulting in even less anonymity / more ties to purchases.

The problem is that the dead change shouldn't be in the "anonymous coins pool" anymore. But they cannot be in the normal pool as well because then they might get used in a transaction with your non-mixed coins which is even worse. The question is, is it enough to have a 3rd pool for change?
The answer is no, because in crypto, Zombies infest each other. The change of several transactions would link them all together when being spent. Thats just as bad as leaving it in the "anonymous coins pool". Potentially even worse.
So the dead change that cannot be spent because otherwise the anonymity of the spending transaction might be compromised.

In the current implementation this can be prevented by not created change of mixed coins at all. This can be done by using up the whole input either by paying larger fees or by sending more DRK that one is supposed to. If money is sent to an exchange, send 100.00000001 anonymized coins instead of 100 or 95. Send 10.00000001 coins instead of 8.5 etc.

But thats not a good solution, it's just what we have to work with right now. In the example with the 5.00000002 Coins dead change, this change could re-enter Darksend mixing with other already mixed funds in order to make 4 x 1.00000001, which would leave 0.99999998 DRK of dead change behind while the rest is being re-anonymized.
However, the 0.99999998 DRK won't ever be spendable without possibly breaking anonymity. It can be donated though, if it's the only input of the donation Tx.

This is why I AGAIN suggest denomination convertibility. That means making the Darksend denominations be 1, 10, 100 etc instead of 1.00000001, 10.00000001 etc. Also, smaller denominations like 0.1 would be nice to have.
That way Dead change that accumulates over time can easily be re-anonymized without bloating the blockchain too much by combining 10 dead change re-anonymized denominations into the next bigger one. With the current implementation that is not possible as it would leave behind 0.00000009 DRK.
With denomination convertibility, there wouldn't be a leftover.

I hope there will be something implemented to prevent this from happening in the future. If not my solution suggestion, then hopefully something better.

Thanks for reading,
Aswan

Aswan,

Thanks for the analysis. I think change left over from anonymous transactions just needs to reenter the pool and get anonymized. For example you could have 5 Anon DRK and make 1 purchase for 2.5DRK (0.5 DRK change) and 1 purchase for 0.25 DRK (0.75 DRK change). Next the 0.5+0.75 can be combined and go into the pool and come out as a 1DRK anon.

By the way, the denominations are reserved amounts, that's why they have 1 extra duff. If you try to send that amount with the software, it will round down. That's how your wallet tells if a specific input is denominated or not. Amounts like 1, 5, 10, 100DRK are used on the network all of the time, so I didn't want to reserve them.

 

[UdjinM6]

I think Aswan is referring to a situation where the change is less than 1 and thus cannot be remixed. Furthermore, due to the use of 10.00000001 as a denomination rather 10, if you try to combine change less than 1 to get to a denominable amount you will always end up with a few "duffs" left over.

Frankly, I have not thought about it enough to say that I agree that the current method will ALWAYS leave change that can't be anonymized, but that is my understanding of the post.

Hmmm... Few quotes:

and giving 5.00000002 back to you as change. This change is "Dead Change".

No, 5 is definitely not "dead"

The problem is that the dead change shouldn't be in the "anonymous coins pool" anymore.

And they are not in "anonymous coins pool" now. I tested this exact scenario (10+10 -> 15) on testnet and got 5 non-anonymized coins as change.

But I agree that small amounts ("dust") could be combined and mixed together as one.

EDIT: testnet results added

 

[Aswan]

That's an interesting read and I like "zombie-style" of it

But honestly I don't see what's the problem with change.
Suppose you have 100 anonymized DRKs. You pay 15 DRKs using Darksend transaction = you spend 20 anonymized DRKs and you get 5 DRKs of non-anonymized change. So now you have 80 anonymized DRKs and 5 non-anonymized DRKs. Now you have to mix 5 non-anonymized DRKs to be able to use them privately again.
Where is the problem?

I can understand blockchain analysis being a little confusing in this case, since in cases like this, most transaction-chains are traced backwards in the blockchain, while in this case, it's traced forwards.
You are right that coins that are linked to a transaction can be re-anonymized by sending them into a Darksend Transaction, but it is imprtant to know that this cannot be a combined transaction of ones own funds, but instead can only have the dead change as an input.
This way it is possible to re-anonymize some coins, but not all of them.
I suggest implementing automatic re-mixing of dead change amounts which requires special rules. This is not currently done and has to be done manually. Since Darksend is supposed to be easy to use, I suggest offering an easy automatic solution.

I think Aswan is referring to a situation where the change is less than 1 and thus cannot be remixed. Furthermore, due to the use of 10.00000001 as a denomination rather 10, if you try to combine change less than 1 to get to a denominable amount you will always end up with a few "duffs" left over.

Frankly, I have not thought about it enough to say that I agree that the current method will ALWAYS leave change that can't be anonymized, but that is my understanding of the post.

The problem in UdjinM6s example would be that 5 non-anonymized coins won't fully go into a Darksend pool. Instead, 4x 1.00000001 DRK would go into the Darksend, leaving a dead change of 0.99999996 DRK behind, which can never be spent due to it being smaller than the smallest denomination. Such a leftover will always occur. There are only very few special cases in which the dead change will be consumed completely during the re-anonymization process.

Aswan,

Thanks for the analysis. I think change left over from anonymous transactions just needs to reenter the pool and get anonymized. For example you could have 5 Anon DRK and make 1 purchase for 2.5DRK (0.5 DRK change) and 1 purchase for 0.25 DRK (0.75 DRK change). Next the 0.5+0.75 can be combined and go into the pool and come out as a 1DRK anon.

By the way, the denominations are reserved amounts, that's why they have 1 extra duff. If you try to send that amount with the software, it will round down. That's how your wallet tells if a specific input is denominated or not. Amounts like 1, 5, 10, 100DRK are used on the network all of the time, so I didn't want to reserve them.

In your example, we'd have 5 x 1.00000001 = 5.00000005 anonymized DRK available.

buying something for 2.5 DRK would consume 3 outputs, leaving us with the following outputs:
1) 1.00000001
2) 1.00000001
3) 0.50000003

Now comes the next purchase for 0.25 DRK and we aleady have the first problem. We cannot use output 3) since it is already linked to a purchase possibly further linking to personal details or in case of an exchange, to another cryptocurrency address like a BTC address. So output 3) cannot be in the anonymous pool anymore.
But where else can it go? If it goes to the regular pool and gets spent together with other coins or even alone and this transaction can somehow get linked to the identity or something else, it automatically also de-anonymized the purchase that cost 2.5 DRK.
So I argue it can go to neither pool. It's a separate output that cannot be used anonymously, but will threaten the anonymity of the purchase that created it in case it gets put into the regular pool.
It has to be handled separately. It cannot re-enter the mixing stage in this example because it is smaller than the smallest Darksend denomination and it cannot be combined with other coins of the regular pool or with other changes since that threatens anonymity. It could get combined with other Darksend denominations if it was bigger without threatening anoymity, but because of it's size output 3 is dead change.

Next we are purchasing something for 0.25 DRK. We now know that we cannot use output 3 so output 1 or output 2 gets used, leaving behind a new change of 0.75000001 DRK. This change is Dead.

We now have:
1) 1.00000001
2) 0.75000001
3) 0.50000003

Output 1) can still be in the anonymous coins pool, but neither 2) nor 3) can be in the anonymous pool or in the regular pool.
One could argue they can be in a 3rd pool, a change pool,but there cannot exist a pool for dead changes since in crypto, Zombies infest each other.
What I mean by that is, if you want to combine 2) and 3) in oder to get another 1.00000001 denomination that can be used for Darksend, then first of all, in this case, this can be quite costly due to fees even or especially because they are now randomly taken (depends on your luck here).
However, the real reason you can't do it is because it would link your 2 purchases together. One of the purchases might be something you never want anyone to find out about, the other one is not that critical and could lead to your identity if investigated. Now that you have combined the 2, it is obvious that you did the 2 parent transactions which have been transactions for both purchases.
By combining dead changes with each other, you link together the purchases of their parent transactions.

Hmmm... Few quotes:

No, 5 is definitely not "dead"

And they are not in "anonymous coins pool" now. I tested this exact scenario (10+10 -> 15) on testnet and got 5 non-anonymized coins as change.

But I agree that small amounts ("dust") could be combined and mixed together as one.

EDIT: testnet results added

5 can be re-anonymized, but its dead until that is actually done. It cannot be used together with another output without threatening privacy. If it is used by itself, thats fine. Dead changes can always be donated etc., they just cannot be combined with another output that is not anonymized and if that other output is anonymized, it has to re-enter the anonymization stage together with the output it is being combined with.
While in crypto Zombies infest each other, they don't infest themselves. Leave one alone and it's fine. You can even donate it ... Just don't put another or or regular people with it.

Edit: Dead change cannot enter the regular coins pool nor the anonymous coins pool without threatening privacy. I think them entering the regular pool is even worse than them entering the anonymous pool.

 

[UdjinM6]

Oh, ok. I see now. Thanks for detailed explanation!

EDIT: so in short: using non-anonimized change deanonymize your previously anonymous spend - the one you got this change from. Right?

 

[moli]

Aswan, if you could put up some pictures to show us, that would be great. Also, I'm not sure what you mean by saying:

As with Zombies, dead better stays dead. If you but it into a room (a transaction) with healthy (anonymized, unused) people (denominations), they are all gonna be infested (tied to a purchase / de-anonymized).
It's even worse. Unlike Zombies, Dead changes can infest each other if being used in a chain or if being combined resulting in even less anonymity / more ties to purchases.

 

[Aswan]

It potentially does so.

Oh, ok. I see now. Thanks for detailed explanation!

EDIT: so in short: using non-anonimized change deanonymize your previously anonymous spend - the one you got this change from. Right?

It potentially does so, not necessarily. If you send some anonymized coins to an exchange and then send some more coins to the exchange using the dead change from the transaction that first sent coins to that exact exchange, then it doesn't matter since there only one other party involved.
But in most cases, it's not the same entity you are sending coins to, and if one of them has some info on you (be it just a payout BTC address on an exchange), then that info can be used to further investigate. Once linked together, those Txs will stay linked.
I suggest Using up the full amount of the inputs not leaving a change, or if there is a change re-anonymize it SEPARATELY (not combined with other coins, especially not with others from the regular pool). If it's too small to be re-anonymized, do not use it. Never use it. Donate it if you want. if not, send it away to another wallet so it cannot be used by your client.

Aswan, if you could put up some pictures to show us, that would be great.

I might have to create some pictures to show it since I know if can be quite confusing. But I still have a lot to do today so pictures, if needed, will have to wait until tomorrow.

Regarding your question:
What I mean is that if a dead change never gets used, it's fine, but when it gets used in a transaction that transacts more than the amount of the dead change and therefore needs another output as input, not only that transaction, but also it's change gets linked to the parent transaction of the initial dead change.
If you combine 2 or more dead changes, all the purchases of all of their parent transactions get linked together.

 

[oblox]

Would implementing stealth addresses fix linkages?

 

[moli]

It potentially does so.


It potentially does so, not necessarily. If you send some anonymized coins to an exchange and then send some more coins to the exchange using the dead change from the transaction that first sent coins to that exact exchange, then it doesn't matter since there only one other party involved.
But in most cases, it's not the same entity you are sending coins to, and if one of them has some info on you (be it just a payout BTC address on an exchange), then that info can be used to further investigate. Once linked together, those Txs will stay linked.
I suggest Using up the full amount of the inputs not leaving a change, or if there is a change re-anonymize it SEPARATELY (not combined with other coins, especially not with others from the regular pool). If it's too small to be re-anonymized, do not use it. Never use it. Donate it if you want. if not, send it away to another wallet so it cannot be used by your client.



I might have to create some pictures to show it since I know if can be quite confusing. But I still have a lot to do today so pictures, if needed, will have to wait until tomorrow.

Regarding your question:
What I mean is that if a dead change never gets used, it's fine, but when it gets used in a transaction that transacts more than the amount of the dead change and therefore needs another output as input, not only that transaction, but also it's change gets linked to the parent transaction of the initial dead change.
If you combine 2 or more dead changes, all the purchases of all of their parent transactions get linked together.

To me, it seems easier to be traced if someone spends the whole anonymized amount in one purchase than if they don't. But I need to look into this more also.

 

[Aswan]

To me, it seems easier to be traced if someone spends the whole anonymized amount in one purchase than if they don't. But I need to look into this more also.

What I mean is the whole amount of the input, so when you have an input of 10.00000001 DRK and only have to pay 9.8 DRK, then there would be a dead change of 0.20000001 DRK which possibly threatens anonymity when reused. However, if you give that 0.20000001 DRK as a tip, there will not be dead change since there is no change at all.

Would implementing stealth addresses fix linkages?

The last time I dealt with stealth addresses was a few months ago so I cannot currently answer that question. I am sure eduffield can though.

 

[crowning]

Regarding your question:
What I mean is that if a dead change never gets used, it's fine, but when it gets used in a transaction that transacts more than the amount of the dead change and therefore needs another output as input, not only that transaction, but also it's change gets linked to the parent transaction of the initial dead change.
If you combine 2 or more dead changes, all the purchases of all of their parent transactions get linked together.

What I would do:

• automatically move ALL changes to one input and mix them in the background once it's more than 1 DRK. Some users might be a bit surprised to suddenly have some mixed coins, but better save than sorry.
  
• the leftovers (< 1DRK) which we can't be mixed would be labelled with the lowest priority (maybe add an extra 'Zombie' priority), thus spend last and only after a pop-up informs the user that those are used.

 

[eduffield]

Edit: Dead change cannot enter the regular coins pool nor the anonymous coins pool without threatening privacy. I think them entering the regular pool is even worse than them entering the anonymous pool.

You're right, thanks for the very detailed explanation. Any usage of change can be used to de-anonymized other spending done in the wallet. The only way to fix this is to over-pay in the closest denomination, I could add a 0.1DRK denomination, that should fix it.

 

[oblox]

Any reason why we aren't discussing stealth addresses. On paper, it seems like a match made in heaven. DS to cause reasonable doubt on who the sender is, stealth addresses to mask the receiver. What's not to like?

 

[Aswan]

What I would do:

• automatically move ALL changes to one input and mix them in the background once it's more than 1 DRK. Some users might be a bit surprised to suddenly have some mixed coins, but better save than sorry.
  
• the leftovers (< 1DRK) which we can't be mixed would be labelled with the lowest priority (maybe add an extra 'Zombie' priority), thus spend last and only after a pop-up informs the user that those are used.

Putting all the changes into a "change-pool" is not a good solution as I have already explained in my other posts as is links together the purchases. Every change has to be mixed separately.
For leftovers there could be an option in the client where the user can save some donation addresses of others that can be selected in order to send them the change to get rid of it.
As you say, there should be at least a warning popping up when trying to spend it with a message how much coins can safely be spent.

You're right, thanks for the very detailed explanation. Any usage of change can be used to de-anonymized other spending done in the wallet. The only way to fix this is to over-pay in the closest denomination, I could add a 0.1DRK denomination, that should fix it.

Adding a 0.1 DRk denomination could keep the waste low. However, there should be some features in the client that help that help the user to not get their anonymity compromised because they just didn't about this issue. Something that automatically takes the change out of the spendable balance until re-mixed, possibly with a donation option and an address book of donation addresses (the development teams address could be in there by default

I am not sure yet if there might be bloating issues with the 0.1 DRK denomination. I have thought a lot about blockchain bloating recently and I might start another discussion about it in the future.
For now, the 0.1 DRK denomination seems like a good temporary solution. Temporary because depending on the value of DRK is might eventually cause too much value to be wasted, but there can always be a lower denomination added.