Welcome to the Dash Forum!

Please sign up to discuss the most innovative cryptocurrency!

Darksend technical diskussion - anonymity, liquidity, improvements

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

  1. Aswan

    Aswan Member

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

    I haven't been very active on this forum so far, but I think it's time to talk about these things:

    Darksend, in the current implementation, has a few flaws I want to discuss and find possible improvements for.

    Problem #1:

    Denomination fee:
    The denomination fee is always 0.0125 DRK per participant. There are always 3 participants per Darsend Tx making it a total of 0.0375 DRK.
    While I agree that the Darksend Tx has to be of the same size for everyone due to anonymity implications, the fee itself is not mixed, meaning it will always link to the origin of the funds before they entered the Darksend process. Heres an example:
    Address XmaH4tKi8jwdTkuyLVVvPrBLxwz2bc3rk7 has first been loaded with a little over 1000 DRK and then performed a Darksend Transaction for amout 98 DRK and then added another ~34 DRK to it's darksend pool, resulting in the funds being Dark sent to different addresses as 10.00000001 and 1.00000001 bits in this transaction.

    Theres also some change of 0.71363402 which has not become part of the Darkcoin pool. Now, for further Darksend rounds, technically and for the sake of anonymity, none of those outputs should be re-linked to XmaH4tKi8jwdTkuyLVVvPrBLxwz2bc3rk7.
    However, in the next round of Darksend they are linked back to XmaH4tKi8jwdTkuyLVVvPrBLxwz2bc3rk7 because the fee of 0.0125 DRK is paid from there. The same goes for the next round after this one again.
    Again the fee is being paid from XmaH4tKi8jwdTkuyLVVvPrBLxwz2bc3rk7 linking it to all further rounds of Darksend.

    This is a real issue, especially because theres only 3 participants per Darksend round (and each round connects the transaction to the 3 origin address due to this fee issue). This means there are only 2 Parties to check (of which we know the origin addresses) in order to de-anonymize the 3rd one as well.
    People talk about malicious Masternodes, how about malicious liquidity providers removing all other layers of Darksend anonymity because of the fee issue?

    Solution:
    Send the fee through Darksend as well. That way each fee will be paid by an output of a Darksend transaction and not be linked to the origin address.
    This means that an observer is able to know how many Darksend rounds are still to come for the outputs of a Darksend transaction, but it does not enable him to know how they are devided amongst the Darksend outputs and it does not allow him to know how many rounds each output has already gone through, so I do not see an issue with that.


    Problem #2:

    Liquidity and denomination size:
    Currently, there are different denomination sizes of which the most common ones are 1.00000001, 10.00000001 and 100.00000001 with the latter one being used less frequently than the other 2. There are higher Darksend denomiation sizes but they are rarely used.


    Also, we all know there is currently a liquidity problem resulting in long waiting times when trying to create a Darksend transaction. I see the way denomination is handled as one reason for the long waiting times and the low liquidity.

    When someone creates a Darksend Transaction with denominations of 100.00000001, 10.00000001 and 1.00000001, then be has to wait for someone else who has at least one of each. If he finds someone who has the ~10 DRK and the ~1 DRK denominations, but not the ~100 denominations, he can't mix with him.
    And thats quite reasonable since it woudl mean that, in the end, the ~100DRK denomination would be easily linked to an input address.
    Thats means there are a lot less potential Darksend participants for each constellation with a combination of ~10DRK and ~1 DRK ones being the most used one.
    This results in less liquidity for everyone since each combination "plays on it's own level", not allowing them to be mixed.


    Solution:
    In order to allow all sorts of denominations to be mixed, we'd simply have to change the denominations from 10.00000001 to exactly 10DRK. The same for all the others.
    That way a 100 DRK denomination can enter a transaction with only 10s and 1s and just be split into 10x10DRK.
    With the current implementation this is not possible since you cannot split 0.00000001 DRK, but by "flattening" denominations to 1s, 10s and 100s, this wouldn't be a problem at all.
    Suddenly, they could all be mixed adding a massive amount of liquidity to the Darksend feature.



    Problem #3:

    Re-mixing total amounts and spending in one go:
    The problem i describe here is the fact that once an amount of DRK enters the Darkcoin mixing pool, there will always be the full amount mixed (at least to the smallest denomination). That means if I have ~55 coins being mixed, resulting in 5x ~ 10DRK and 5x ~ 1DRK denominations, each Darksend round will use all of them.
    Together with Problem #1, which allows us to see the 3 origin addresses of each Darksend transaction, this can cause some anonymity issues.

    If we want to spend all mixed coins at once, we ill have the same amount spent as we put in to mix. Because an observer can see the origin addresses, he can quickly link the funds spent to the address which put exactly that amount into the Darksend pool.
    Now one could say don't spend them all at once then, but what if the 2 other participants do exactly that? There would only be your origin address left to tie the rest of the outputs to and it will always be correct.

    Solution:
    What I suggest is (in addition to the solution for problem #1), that Darksend does not take the whole Darksend pool to mix, but a random amount of denominated coins. This would result in more Darksend transactions, but also more liquidity (not in total amounts, but in number of participations). Unlike the other 2 solutions, this might be a lot of work and I a am not sure amount how to deal with the transaction fee in this case, so this solution is kind of a draft which I hope people will help develop. The solution to problem #1 should deal with a lot of issues problem #3 causes as well, so #1 and #2 should be fixed first I think.



    If you are still reading, thanks and I hope you have something useful to add to the discussion.
    If I forgot about something or if I just wrote plain bullshit because I didn't see something, then..meh... But I think these suggestions could help Darkcoin grow. I hope to get some useful input here, let the discussion begin :)
     
    • Like Like x 13
  2. JGCMiner

    JGCMiner Moderator
    Moderator

    Joined:
    Jun 8, 2014
    Messages:
    358
    Likes Received:
    210
    Trophy Points:
    113
    Well first things first...
    paging eduffield

    Secondly, I don't know about issue 2 and 3, but I have a memory of issue 1 being discussed and resolved. Via the issue outlined in 1 have you successfully traced coins through Darksend?
     
  3. Aswan

    Aswan Member

    Joined:
    Jun 26, 2014
    Messages:
    68
    Likes Received:
    216
    Trophy Points:
    73
    Via the issue in #1 I have been able to trace coins when other things applied as well (the "spending in one go"-issue described in problem #3).
    When No coins have been spent, I was not able to trace the coins to the exact destination, but because of the denomination fee the 3 origin addresses were known ofc.
    However, eventually the coins will be spent and there are multiple ways to link them to the origin address then (e.g. spending in one go), which de-anonymizes your coins if you do it or if the 2 other participants do it.
    Also, if the change is re-grouped with the the other Darksend outputs in another Tx, it will eventually add up to the original Darksend pool input.


    Edit: the tracing is actually pretty simple.

    1. You receive a transaction which has Darksend outputs as input.
    2. You verify they are all from the same transaction.
    3. If they are, look up all 3 origin addresses (those are the addresses that pay the fee)
    4. Look for the transaction that is creating the fee denominations
    5. follow the non-fee part to the first darksend transaction.
    6. Substract the leftover (the "odd" DRK amount in the Tx output) to know how many coins this address actually sent into the darksend pool
    7. If the amount you received is higher than 2 of those darksend inputs, the transaction you received is from the remaining origin address.
    8. If according to #7 there is more than 1 possible sender, check if the amount you got equals one of the inputs of the origin addresses. If yes, this is your origin address.
    9.1 If #8 doesn't work, you can further investigate by grouping spendings together. This works especially well if it was not the last Darksend round for 2 of the participants, because then they will always spend the full amount, making it easy to find the remaining origin address.
    9.2 Look for the origin addresses transactions. If they both did another Darksend round after the one you got your coins from, there is only 1 origin address left (the one that did not do another round). This if the address you got your coins from.
     
    #3 Aswan, Nov 10, 2014
    Last edited by a moderator: Nov 10, 2014
    • Like Like x 6
  4. oblox

    oblox Well-known Member

    Joined:
    Aug 6, 2014
    Messages:
    1,032
    Likes Received:
    537
    Trophy Points:
    183
  5. moli

    moli Grizzled Member

    Joined:
    Aug 5, 2014
    Messages:
    3,261
    Likes Received:
    1,837
    Trophy Points:
    1,183
    You are correct. Evan needs to fix this.
     
  6. eduffield

    eduffield Core Developer

    Joined:
    Mar 9, 2014
    Messages:
    1,084
    Likes Received:
    5,319
    Trophy Points:
    183
    Hello Aswan,

    This is some great feedback, you've shown you really know your way around the protocol. It's great to get feedback, even if it's showing flaws in the system. I'll address these in the next release. But in the meantime, here's some thoughts:

    Problem #1:

    Darksend makes the transaction fees in batches, which usually don't have enough fee inputs to get a user all the way through the process. So at some point during the process the chain usually be broken. However, the issue still remains and darksend needs a fee mixing phase. That should at least be very fast because all of the inputs are one size.

    Liquidity providers mix random amounts each round already, so they will make good partners for stopping this type of tracking until #3 is done. E.g. they don't spend the whole previous round as the default client does.

    Problem #2:

    I think the way it works is a pretty good mix of speed and lack of bloating. If we allowed inputs to be split up in the mixing phase like you say, you could split 100DRK into 10x10, or 10DRK into 10x1, that would cause a lot of bloating. I see this as being a problem with bootstrapping the currency. We just don't have enough active volume of Darksends to really speed up the process. There's really only a few mixes a day, it's went up recently, but it's still not very high. If we were doing hundreds a day, then it should just take an hour to complete.

    In the future we actually shouldn't need liquidity providers. At that point we could increase the mixes to 4 or 5, which even makes the anonymity much more robust.

    Problem #3:

    This is a great idea and I'll implement it in the next version. It should speed up mixing for everyone on the network. By using random amounts each time, we'll match with random denomination mixes, which will match with more users.
     
    #6 eduffield, Nov 10, 2014
    Last edited by a moderator: Nov 10, 2014
    • Like Like x 7
  7. moli

    moli Grizzled Member

    Joined:
    Aug 5, 2014
    Messages:
    3,261
    Likes Received:
    1,837
    Trophy Points:
    1,183
    Evan, I can find my original address by clicking on the tx, go to next page, click on the 3rd fee 0.0125 and it takes me to my original address.. This isn't hard to find like he said.

    Edit: And my DRK had gone through 8 rounds anonymized.
     
    #7 moli, Nov 10, 2014
    Last edited by a moderator: Nov 10, 2014
  8. moli

    moli Grizzled Member

    Joined:
    Aug 5, 2014
    Messages:
    3,261
    Likes Received:
    1,837
    Trophy Points:
    1,183
  9. eduffield

    eduffield Core Developer

    Joined:
    Mar 9, 2014
    Messages:
    1,084
    Likes Received:
    5,319
    Trophy Points:
    183
    Aswan, The community would like to thank you. Got a donation address?
     
    • Like Like x 8
  10. Ignition75

    Ignition75 Active Member

    Joined:
    May 25, 2014
    Messages:
    332
    Likes Received:
    216
    Trophy Points:
    113
    +1

    Thank you for that excellent analysis...
     
  11. lostmybrain

    lostmybrain New Member

    Joined:
    Sep 23, 2014
    Messages:
    17
    Likes Received:
    14
    Trophy Points:
    3
    Feedback, constructive discussion and quick fixes in crypto? Preposterous! :)
     
  12. Ignition75

    Ignition75 Active Member

    Joined:
    May 25, 2014
    Messages:
    332
    Likes Received:
    216
    Trophy Points:
    113
    It's Dark Magic!

    ;)
     
    • Like Like x 1
  13. eduffield

    eduffield Core Developer

    Joined:
    Mar 9, 2014
    Messages:
    1,084
    Likes Received:
    5,319
    Trophy Points:
    183
    Solution #1:

    I think I'm in favor of hard-forking the network to make Darksend transactions completely free. So there will be no fees to track at all. That means that we'll have to have the users pay another kind of fee to stop sybil attacks. Instead of the miners, they could pay either the masternode network (the one you connected to even), the development fund, foundation fund, etc. These payments would be passed to the masternode and could be cashed later to avoid timing analysis. Another upside to this is it's impossible to do in Bitcoin and the fees could be MUCH lower than 0.0125. Thoughts?
     
    #13 eduffield, Nov 10, 2014
    Last edited by a moderator: Nov 10, 2014
  14. JGCMiner

    JGCMiner Moderator
    Moderator

    Joined:
    Jun 8, 2014
    Messages:
    358
    Likes Received:
    210
    Trophy Points:
    113
    Three thoughts/questions:

    1. How exactly would this new fee --say, to the masternodes -- be enforced?

    2. I thought the DS transaction fee was there not just to prevent Sybil attacks but also to ensure DS blocks get processed immediately by miners. I remember the days of 0.001 fees when RC4 was released and DS rounds >1 not working because of this issue.

    3. This seems like a lot more work compared to adding a fees mixing phase. Is there some technical reason why the fee mixing phase can't be done or is a bad idea?
     
    #14 JGCMiner, Nov 10, 2014
    Last edited by a moderator: Nov 10, 2014
  15. moli

    moli Grizzled Member

    Joined:
    Aug 5, 2014
    Messages:
    3,261
    Likes Received:
    1,837
    Trophy Points:
    1,183
    Can you make DS free with NO fees from each round but when the anonymized DRK is spent, there's a fee attached to it and sent from the same pseudo address with the tx, which can not be traced back to the origin address?

    Edit: Although I can see the problem with this.. How can we punish abusers and trouble-makers to DS..
     
    #15 moli, Nov 10, 2014
    Last edited by a moderator: Nov 11, 2014
  16. eduffield

    eduffield Core Developer

    Joined:
    Mar 9, 2014
    Messages:
    1,084
    Likes Received:
    5,319
    Trophy Points:
    183
    I'm thinking the user will pay for Darksend access for a period of time. For example, you do one transaction for 0.1 to the Darksend access address, this is the very first thing you do when Darksend starts. Then you send that transaction ID, and a signature proving you own the input. That gives you access to darksend for 1 day or something.

    You're correct. That's what the hard fork is for.

    I think there's a problem with the fee mixing phase. That would be much easier, but every round of a darksend would still go back to 1 Darksend fee mixing transaction. So you could follow a transaction from round 8,7...1. If you control the last masternode, you could tell who owns the final Darkcoin.
     
  17. JGCMiner

    JGCMiner Moderator
    Moderator

    Joined:
    Jun 8, 2014
    Messages:
    358
    Likes Received:
    210
    Trophy Points:
    113
    Thanks.

    I think your plan is a good idea.
     
  18. Stealth923

    Stealth923 Well-known Member
    Foundation Member

    Joined:
    Mar 9, 2014
    Messages:
    343
    Likes Received:
    370
    Trophy Points:
    233
    I think it sounds good - although if users pay their 0.1DRK to gain access to the masternode network - what happens if their inputs dont get mixed after 1 day due to liquidity and or their inputs dont match with anyone.

    There needs to be some sort of guarantee that if the users pay their 0.1DRK to access it would complete X number of rounds within a day...otherwise users would be spending 0.1DRK for a chance to mix with others..
     
  19. eduffield

    eduffield Core Developer

    Joined:
    Mar 9, 2014
    Messages:
    1,084
    Likes Received:
    5,319
    Trophy Points:
    183
    There's no way to guarantee anything. I guess that's the only catch. As we get bigger, this shouldn't be a problem. There should be liquidity.
     
  20. tungfa

    tungfa Administrator
    Dash Core Team Foundation Member Masternode Owner/Operator Moderator

    Joined:
    Apr 9, 2014
    Messages:
    8,964
    Likes Received:
    6,737
    Trophy Points:
    1,283
    great to see the fast response from everybody towards the issues raised !
    Well done team ....>
    Tx Aswan for bringing this up !
     
  21. Stealth923

    Stealth923 Well-known Member
    Foundation Member

    Joined:
    Mar 9, 2014
    Messages:
    343
    Likes Received:
    370
    Trophy Points:
    233
    Yep agreed - chicken and egg thing....

    After thinking about it a little more I definitely agree this is the best way to go.

    Thanks Evan!
     
  22. darkwing

    darkwing Active Member

    Joined:
    Apr 8, 2014
    Messages:
    149
    Likes Received:
    110
    Trophy Points:
    103
    This is why a darksend session might be better than a subscription. You get what you pay for. How long it takes depends on how many rounds you've set/liquidity but as long as you don't close the session it runs until done?
     
  23. eduffield

    eduffield Core Developer

    Joined:
    Mar 9, 2014
    Messages:
    1,084
    Likes Received:
    5,319
    Trophy Points:
    183
    Fees per round isn't possible, unless it's in the transaction. How does the user prove he didn't get 8 rounds?
     
  24. darkwing

    darkwing Active Member

    Joined:
    Apr 8, 2014
    Messages:
    149
    Likes Received:
    110
    Trophy Points:
    103
    I meant 1 fee to denominate.. not fee per round. So pay a fee to denominate choose how many rounds (this doesn't affect the fee, just how long it takes) and press go.

    1 fee for the session.

    A separate idea: would routing the fee via a stealth address help?
     
    • Like Like x 1
  25. Dr.Crypto

    Dr.Crypto Member

    Joined:
    Jul 9, 2014
    Messages:
    46
    Likes Received:
    32
    Trophy Points:
    58
    How about porting stealth addresses (SX) from vertcoin's recently open-sourced code and combine them with Darksend? Two results:
    1/ impossibility to trace back the coins to the source, so no reason to run rogue liquidity providers to gain information by monitoring DS transactions
    2/ possibility to lower the DS fees or completely remove them if desired as sybil attacks are rendered impossible
     
  26. coingun

    coingun Active Member
    Masternode Owner/Operator

    Joined:
    Jul 8, 2014
    Messages:
    489
    Likes Received:
    402
    Trophy Points:
    133
    I personally love the idea of a pay for access type system.

    This would scale really well to other (potential) services that could be run by the masternodes. Want to mix some darkcoins? Pay for the time to mix them. Want to use DPN? Pay for the time you need your routes in place. Want to sync the blockchain faster? Pay to sync from the MN network.

    This scales really well and would definitely be useful in the future with other services that became "paid for".

    Aside: I really love all the constructive criticism in this thread. This community is really growing up fast!
     
  27. moli

    moli Grizzled Member

    Joined:
    Aug 5, 2014
    Messages:
    3,261
    Likes Received:
    1,837
    Trophy Points:
    1,183
    The user can see from the Coin Control how many rounds he's got, and that info should be enough, right?
     
  28. crowning

    crowning Well-known Member

    Joined:
    May 29, 2014
    Messages:
    1,428
    Likes Received:
    2,005
    Trophy Points:
    183
    So for ONE single fee I'll be able to SPAM the Masternodes with Darksend mixing requests for 24 hours?
     
  29. JGCMiner

    JGCMiner Moderator
    Moderator

    Joined:
    Jun 8, 2014
    Messages:
    358
    Likes Received:
    210
    Trophy Points:
    113
    This has changed. Here is the current idea (from Evan on BCT):

    "Solution 3:
    Pay per round of Darksend, in a separate transaction, paid directly to the miners as a fee. The masternodes would hold on to them and publish them later on. To double spend attack this, you would need to pay the miners more fees, so it's impossible to double spend against and it's timing attack resistant. "

    Link:
    https://bitcointalk.org/index.php?topic=421615.msg9503956#msg9503956
     
    • Like Like x 1
  30. crowning

    crowning Well-known Member

    Joined:
    May 29, 2014
    Messages:
    1,428
    Likes Received:
    2,005
    Trophy Points:
    183
    Ah, thanks, these days I rarely read bitcointalk.org because it causes brain-cancer.

    Solution 3 is similar to what I was thinking. Not 100% sure why the extra step to pay the miners is needed (IMO it would be sufficient to add the paid fee to the next Masternode payment as a bonus).