Welcome to the Dash Forum!

Please sign up to discuss the most innovative cryptocurrency!

Dead Change - an anonymity issue

Discussion in 'Development Tech Discussion' started by Aswan, Nov 20, 2014.

Tags:
  1. Aswan

    Aswan Member

    Joined:
    Jun 26, 2014
    Messages:
    68
    Likes Received:
    216
    Trophy Points:
    73
    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
     
    #1 Aswan, Nov 20, 2014
    Last edited by a moderator: Nov 20, 2014
    • Like Like x 12
  2. Ignition75

    Ignition75 Active Member

    Joined:
    May 25, 2014
    Messages:
    332
    Likes Received:
    211
    Trophy Points:
    113
    An excellent piece of analysis, I did however, have to read it twice :)
     
  3. Aswan

    Aswan Member

    Joined:
    Jun 26, 2014
    Messages:
    68
    Likes Received:
    216
    Trophy Points:
    73
    I'm sorry if there are some things unclear. What made you haveing to read it twice? Maybe I can edit some things.
     
    #3 Aswan, Nov 20, 2014
    Last edited by a moderator: Nov 20, 2014
  4. Ignition75

    Ignition75 Active Member

    Joined:
    May 25, 2014
    Messages:
    332
    Likes Received:
    211
    Trophy Points:
    113

    Nothing was unclear, I panic read it at the start quickly, then read it properly :)
     
    • Like Like x 1
  5. Aswan

    Aswan Member

    Joined:
    Jun 26, 2014
    Messages:
    68
    Likes Received:
    216
    Trophy Points:
    73
    haha, alright :)
     
  6. UdjinM6

    UdjinM6 Official Dash Dev
    Dash Core Team Moderator

    Joined:
    May 20, 2014
    Messages:
    3,633
    Likes Received:
    3,533
    Trophy Points:
    1,183
    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?
     
  7. JGCMiner

    JGCMiner Moderator
    Moderator

    Joined:
    Jun 8, 2014
    Messages:
    351
    Likes Received:
    207
    Trophy Points:
    113
    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.
     
  8. eduffield

    eduffield Core Developer

    Joined:
    Mar 9, 2014
    Messages:
    1,084
    Likes Received:
    5,319
    Trophy Points:
    183
    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.
     
    • Like Like x 1
  9. UdjinM6

    UdjinM6 Official Dash Dev
    Dash Core Team Moderator

    Joined:
    May 20, 2014
    Messages:
    3,633
    Likes Received:
    3,533
    Trophy Points:
    1,183
    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
     
    • Like Like x 2
  10. Aswan

    Aswan Member

    Joined:
    Jun 26, 2014
    Messages:
    68
    Likes Received:
    216
    Trophy Points:
    73
    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.


    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.


    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.


    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 :p... 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.
     
    #10 Aswan, Nov 20, 2014
    Last edited by a moderator: Nov 20, 2014
    • Like Like x 4
  11. UdjinM6

    UdjinM6 Official Dash Dev
    Dash Core Team Moderator

    Joined:
    May 20, 2014
    Messages:
    3,633
    Likes Received:
    3,533
    Trophy Points:
    1,183
    Oh, ok. I see now. :oops: 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?
     
  12. moli

    moli Grizzled Member

    Joined:
    Aug 5, 2014
    Messages:
    3,262
    Likes Received:
    1,837
    Trophy Points:
    1,183
    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:

     
    • Like Like x 1
  13. Aswan

    Aswan Member

    Joined:
    Jun 26, 2014
    Messages:
    68
    Likes Received:
    216
    Trophy Points:
    73
    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.
     
    • Like Like x 2
  14. oblox

    oblox Well-known Member

    Joined:
    Aug 6, 2014
    Messages:
    1,032
    Likes Received:
    537
    Trophy Points:
    183
    Would implementing stealth addresses fix linkages?
     
    • Funny Funny x 1
  15. moli

    moli Grizzled Member

    Joined:
    Aug 5, 2014
    Messages:
    3,262
    Likes Received:
    1,837
    Trophy Points:
    1,183
    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.
     
  16. Aswan

    Aswan Member

    Joined:
    Jun 26, 2014
    Messages:
    68
    Likes Received:
    216
    Trophy Points:
    73
    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.

    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.
     
  17. crowning

    crowning Well-known Member

    Joined:
    May 29, 2014
    Messages:
    1,428
    Likes Received:
    2,005
    Trophy Points:
    183
    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.
     
  18. eduffield

    eduffield Core Developer

    Joined:
    Mar 9, 2014
    Messages:
    1,084
    Likes Received:
    5,319
    Trophy Points:
    183
    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.
     
  19. oblox

    oblox Well-known Member

    Joined:
    Aug 6, 2014
    Messages:
    1,032
    Likes Received:
    537
    Trophy Points:
    183
    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?
     
  20. Aswan

    Aswan Member

    Joined:
    Jun 26, 2014
    Messages:
    68
    Likes Received:
    216
    Trophy Points:
    73

    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.

    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.
     
    #20 Aswan, Nov 20, 2014
    Last edited by a moderator: Nov 20, 2014
  21. eduffield

    eduffield Core Developer

    Joined:
    Mar 9, 2014
    Messages:
    1,084
    Likes Received:
    5,319
    Trophy Points:
    183
    Stealth addresses are not nearly as useful as they're made out to be in crypto, they provide no extra anonymity to the payer (the one with the change address issue). They're only useful when posting a payment address in a public forum, because it stops people from being able to tie that public payment address to your actual payments.

    In our case, the wallet by default makes a brand new change address to receive the change on. That's pretty much the same thing the stealth address is offering. The problem is, you know the change address is tied to the person who paid.
     
    • Like Like x 1
  22. oblox

    oblox Well-known Member

    Joined:
    Aug 6, 2014
    Messages:
    1,032
    Likes Received:
    537
    Trophy Points:
    183
    catlasshrugged I know you are reading this thread Kristov, would love to hear your input on possible solutions.
     
  23. illodin

    illodin Member

    Joined:
    Apr 26, 2014
    Messages:
    122
    Likes Received:
    71
    Trophy Points:
    78
    So this must be the reason it's hard to make the denomination work smoothly. Stupid question, why can't the wallet keep track of which inputs are denominations and how many rounds they haven gone through, and how many times they've been tried to find a suitable mixing partners etc? I'd imagine that would simplify the code a whole lot and allow stuff like mixing some of the denominations "out of turn" if they find partners without having to wait larger denoms to get their mixing depth to the same level and so on.
     
  24. oblox

    oblox Well-known Member

    Joined:
    Aug 6, 2014
    Messages:
    1,032
    Likes Received:
    537
    Trophy Points:
    183
    It already can mix out of turn. You'll notice at times with the 500 denom that it will lag behind the more common 1s and 10s in terms of what round it is in. No longer do you need a denomination for each comprising the initial input. Now you can mix your 100s, 10s, and 1s with others with those more common amounts while waiting for people to join in with the 500s.
     
  25. eduffield

    eduffield Core Developer

    Joined:
    Mar 9, 2014
    Messages:
    1,084
    Likes Received:
    5,319
    Trophy Points:
    183
    So I think I have a solution to the "dead change" issue.

    The most simple solution is not allowing change with anonymous transactions, but that means we need to keep the closest set of denominations for the value a user is going to transfer anonymously. I think the best way to do this is eliminate the two largest denominations. For example, if a user wants to transfer 37.61DRK to another user, they would transfer 10x3DRK, 1x8DRK, that leaves .29DRK that would be donated.

    - The mixing process would be about 16x faster, which is a nice plus
    - The mixing would be much harder to follow (everyone is using the 2 denomination sets, so the mixing includes many more people at once)
    - The max change you could have would be .99DRK, on average it would be 0.5DRK or about $1.
    - We could have a list of donation addresses, Development Fund, Masternode Network, P2Pool Development, etc.

    If DRK's price goes up, we can just keep denominations about $2 and $20. That way, it's always really quick to mix on the network and the excess change of small purchases is low. Later on when the network is bigger, we could add back in the larger denominations, and when the wallet has larger ones but no smaller ones, it could use Darksend to convert them from 100 to 10x9 + 1x10.
     
    #25 eduffield, Nov 21, 2014
    Last edited by a moderator: Nov 21, 2014
    • Like Like x 6
  26. oblox

    oblox Well-known Member

    Joined:
    Aug 6, 2014
    Messages:
    1,032
    Likes Received:
    537
    Trophy Points:
    183
    Wait a minute, I thought bloat was the reason we couldn't break 500s into 100s but now we are breaking 100s and 500s into 10s?
     
  27. eduffield

    eduffield Core Developer

    Joined:
    Mar 9, 2014
    Messages:
    1,084
    Likes Received:
    5,319
    Trophy Points:
    183
    The Darksend pool currently is set to max 1000DRK, at that size we would have serious bloat problems. But the plan is to limit the Darksend pool to 100DRK. So the bloat problem isn't an issue at all.

    We'll also have to limit the "max anonymize" amount in the configuration to something like 500DRK. We don't want people anonymizing 10K DRK.
     
    • Like Like x 2
  28. moli

    moli Grizzled Member

    Joined:
    Aug 5, 2014
    Messages:
    3,262
    Likes Received:
    1,837
    Trophy Points:
    1,183
    YAY!! Thanks, Evan! :)
     
  29. smak

    smak New Member

    Joined:
    Sep 21, 2014
    Messages:
    12
    Likes Received:
    3
    Trophy Points:
    3
    Sounds like a winning concept eduffield.

    Possibly also a "re-anonomize" option for those who wish to keep a bank of anonymized funds and they can just "re-up" their anon with a single click, say if they recently spent 50 of their 100 mixed DRK
     
  30. oblox

    oblox Well-known Member

    Joined:
    Aug 6, 2014
    Messages:
    1,032
    Likes Received:
    537
    Trophy Points:
    183
    Sounds like a winner to me. Is there a way as is to look at the completion variable (or whatever the qt client is referencing to display 100%) and issue a walletlock command when it reads 100% being that darksend is done? That way the wallet is not just sitting there unlocked for anyone to tamper with.
     

Share This Page