Welcome to the Dash Forum!

Please sign up to discuss the most innovative cryptocurrency!

Security Advisory for CoinShuffle and Darkwallet

Discussion in 'Official Announcements' started by eduffield, Jan 25, 2015.

  1. eduffield

    eduffield Core Developer
    Dash Core Team

    Joined:
    Mar 9, 2014
    Messages:
    1,084
    Likes Received:
    5,318
    Trophy Points:
    183
    It’s a well known fact that the anonymity of Bitcoin is trivial to break, and many projects have started with an intention to bring anonymity to digital currency to protect consumers and businesses.

    Darkcoin is the first privacy-centric digital currency. Founded in 2014, Darkcoin uses its anonymizing technology called Darksend to keep users funds safe and make the blockchain protected for everyday use without being tracked at some point in the future. Darksend uses a 2-tier network known as the masternode network to provide mixing services. Utilizing this technology, users are able to achieve a high level of anonymity. Darksend is trustless, decentralized and it’s nearly free to use.

    CoinShuffle and Darkwallet are new technologies targeted at providing anonymity on the Bitcoin network. CoinShuffle was created by researchers from Saarland University. Included were Tim Ruffing, Pedro Moreno-Sanchez, and Aniket Kate. Their paper can be found at http://crypsys.mmci.uni-saarland.de/projects/CoinShuffle/coinshuffle.pdf.

    DarkWallet was created in 2013 by Amir Taaki and Cody Wilson, but has since been adopted by a group of open source programmers.

    The problem with CoinShuffle arises from the need to return change to the participants. Change has to be handled with the greatest of care in situations where anonymity is important. Change is very important because it can expose anonymized transactions if dealt with incorrectly. This can happen by observing what is done with the change after doing the anonymous transaction.

    When making anonymity technology, one must remember the blockchain can be traced bi-directionally. These vulnerabilities come from the fact that, if you anonymize 1BTC at a point, then you spend some of it, later on that change must be kept separate from any identifiable transactions. Otherwise you can simply walk backward through the transactions from the identifiable transaction, to the transaction meant to be anonymous.

    From the paper:

    “The use of change addresses is supported in CoinShuffle: Participants can announce additional change addresses in phase 1, if they do not have an address holding exactly the mixing amount B ν. In phase 5, every participant adds all the change addresses as outputs of the mixing transaction tx before it is signed. CoinShuffle still preserves the unlinkability between the input addresses and the (regular) output addresses of the honest participants.”

    There are 2 connected issues with the mismanagement of change. Mario Müller (DarkcoinTalk user Aswan) originally found this issue in Darksend. Presently, this has been resolved in Darksend and it is not vulnerable these kind of attacks.

    1. CoinShuffle Vulnerability
    Forward Change Linking:


    [​IMG]


    In this example, Alice anonymizes 1.2BTC, which goes to 2 outputs, 1BTC and 0.2BTC. She then spends .7BTC from the 1BTC output, receiving change of 0.3BTC. That 0.3BTC then goes to an identifiable source, confirming Alice also spent the .7BTC in the prior transaction.

    To identify the sender of the anonymous transaction, start at the “coinbase” transaction and go backwards in the blockchain till you get to the “Alice sends 0.7BTC anonymously”. As coinbase, you know it was your user who just recently bought something anonymously, thus breaking the anonymity completely.

    Through Change Linking:

    [​IMG]

    In the second example, Alice buys 1.2 BTC from coinbase, then anonymizes this amount into a 1BTC output. She then spends the 1BTC, receives change in the amount of 0.3BTC and then combines that with her 0.2BTC earlier change.

    By combining the change from the anonymous transaction (0.3BTC) and the change she received from the CoinShuffle transaction, you can link the entire history before and after, completely breaking the anonymity.

    Solution:

    All issues presented here can be solved, but require denominated inputs and outputs. Just like the United States Dollar, which has denominations of $1, $5, $10 and $20, Darksend uses 0.1DRK, 1DRK, 10DRK and 100DRK. When mixing on the network, users can only send and receive these denominations. Afterward, transactions are protected by combining the denominations to pay slightly over the required amount.

    For example, if a user needs to pay 1.17DRK anonymously, they will use 1DRK + 0.1DRK + 0.1DRK. This results in a transaction that pays exactly 1.17DRK to the payee, and pays a mining fee of 0.03DRK to eliminate change related tracking.

    3. DarkWallet Vulnerability : Uniquely identifiable amounts

    This mixer is constructed in such a way, where multiple users (or idle mixing bots) are paired up with users desiring to send funds in real time. It’s trivial to de-anonymize any transaction used in DarkWallet due to the unique values of the amounts in the transactions.


    [​IMG]

    For Example:

    In this transaction, 0.05BTC was sent through the mixer. To identify the source of the money, one simply has to add up the values on the right until they match one of the values on the left.

    0.05+0.0499+0.0001(fee) = 0.10BTC.
    0.0499+0.05940182+0.0001(fee) = 0.10940182BTC.

    This gets exponentially more difficult as more users are added to the mixer. However, these sessions can be retroactively de-anonymized at any point in the future.

    Transactions involved:
    https://blockchain.info/tx/4eb3b2f9fe597d0aef6e43b58bbaa7b8fb727e645fa89f922952f3e57ee6d603
    https://blockchain.info/tx/1694122b34c8543d01ad422ce600d59f8d8fde495ac9ddd894edc7139aed7617

    Solution:

    There is no known solution to this issue.

    4. CoinShuffle and DarkWallet Vulnerability : DOS attack

    Both Coinshuffle and Darkwallet are susceptible to DOS attacks, where a malicious user simply refuses to sign the final transaction or logs off during one of the final phases. Since a signature is required to successfully make the final transaction, this process can be stopped simply by refusing to participate.

    Darkwallet and CoinShuffle have suggested a few different approaches to solve this, but all of these allow initial attacks to take place on the network before some action can be taken to protect the network further.

    Solution:

    Darksend uses a novel approach to protect the network from attack known as a collateral transaction. When opening a new mixing session, the user must make out a complete and signed transaction to the masternode he wishes to mix on. Once the process begins, the user is then obligated to complete the process by responding to requests and completing the mixing session or else the collateral transaction will be cashed. This can be thought of as putting a deposit down on a lease, afterward you retain your money if you acted according to the contract.
     
    #1 eduffield, Jan 25, 2015
    Last edited by a moderator: Jan 26, 2015
    • Like Like x 22
  2. eduffield

    eduffield Core Developer
    Dash Core Team

    Joined:
    Mar 9, 2014
    Messages:
    1,084
    Likes Received:
    5,318
    Trophy Points:
    183

    Example Darksend Transaction:


    As an example of the type of anonymity Darkcoin provides, I’ve listed a fully anonymous transaction here. This transaction went more than 10 layers deep (mixed funds went through the process on more than 10 separate masternodes, each with 3 total participants). You’ll notice, there is no change to track transactions with and each participant in each phases uses the same denominations.


    http://explorer.darkcoin.io/tx/14be41bfbcda630615be6a7e7df5d2391f60c570bc2280763e22349f689f6474 (sent 3.2DRK anonymously)
    http://explorer.darkcoin.io/tx/1d7072ab9448d8b59b453fcb53f49f3601f4418e21adc00b03a9bf46cbad7955
    http://explorer.darkcoin.io/tx/d71ba5edd833e0a13cc3f4f828e7ae8bdebb7b8eeabc3a780099695d0bde9525
    http://explorer.darkcoin.io/tx/327c39874c5e6bb981001b5ac4e14a59549007d202bc42bf404b9232944c1255
    http://explorer.darkcoin.io/tx/05be05e35917043ec128fffac6d1c18832f62ed93616cfc805cca1de18b152f7
    http://explorer.darkcoin.io/tx/fd946e98a4e4168ba426e69d0a7d2c8a871973c013698900aa4a3c9e23722d5d
    http://explorer.darkcoin.io/tx/de8be67ed9a45ded8c179d5cb9e4ca5dc958a57804645cc83ad30a57229bfe05
    http://explorer.darkcoin.io/tx/5ce1b10d8d39ee12fada352f646a0bc7fd10e5c68be3657b7e1f25daa96445ec
    http://explorer.darkcoin.io/tx/d438fbdc1cd08a9335d0d85705cca1b4b16ae02ccf4c912202288750fa3d3a06
    http://explorer.darkcoin.io/tx/12d0d2f81eabc990556126e8e86abd7f6587ce9a252e697d49babe02e1e0784d
    http://explorer.darkcoin.io/tx/faa07d6d48cbaabc6cf7f6167cd851b722d8b5d56ed5b45be4c221cd54a4dc7f
    http://explorer.darkcoin.io/tx/278ac690ed283b2f8c6d27173fb45d777198b612b3a67484724fea5c340b1b35
    http://explorer.darkcoin.io/tx/0c1c8796010c466d340c209bf3804d14f8ded70e523fa92baa25d938491625d7
    http://explorer.darkcoin.io/tx/990e5d83a66fa189241af04492496f7d1d2ea7ebb958cc7e3a75185525b94116
    http://explorer.darkcoin.io/tx/01edb919d043e7f34a54e58714cd0e4796a7752132d7d7498938b6b9c2ec4595
    http://explorer.darkcoin.io/tx/6b32a47efebf9c2d8ed4fd97f6f3787cb01b47100a51fc38cd63457ffe254a05
    http://explorer.darkcoin.io/tx/0c16df3800da43b22cfb1caeeedb6ac77e919a8609d0a863337a992f7c9757a6
    http://explorer.darkcoin.io/tx/e5a084b5ca7d0f98b80f142fc4a216b5f210e29d5a1c143ac376416240d09074
    http://explorer.darkcoin.io/tx/bd2f5435ef5a3ba2ff9c873606745d2ced11854977119a017dbe6ad150cfafde
    http://explorer.darkcoin.io/tx/a8452f95817a42531f42440dc5ff489eda0fcf76c3219847cb6bb4e99c0e5d88
    http://explorer.darkcoin.io/tx/54e885792b0d7e07604ed3d2915f6b86499b932ebc2c888125ab68b48720abd4
    http://explorer.darkcoin.io/tx/26906bef4c41e02565561a54dcdaf9e242d3830921b0ba4d5e5bfa085579a0de
    http://explorer.darkcoin.io/tx/1777adc8c015d8282c562d9401902330e9db1ffb18c830222d51c4f7e7c4388b
    http://explorer.darkcoin.io/tx/2edccdb8e9544d6d096b0369c02db7b4c8d3350465ca5b7b772609746a27b15c
    http://explorer.darkcoin.io/tx/15383602cf81ed5e3ddfac17211b5078cbbd1dcec882c4ec8d0a8ce7e6902496
    http://explorer.darkcoin.io/tx/37ec592c7b609e837a6265d7ba28e944e43319a072528e3e6c9e6d39a67a569d
    http://explorer.darkcoin.io/tx/995c8ad4347d7157683a3ac40625d366e1f5f8773e5dc8ac2c3a8148aa4cd423
    http://explorer.darkcoin.io/tx/b8d1475ca6d43934f4d6ce3d4b2cc7e2a01782c506a4e73e036ed4f83c3cdcf7
    http://explorer.darkcoin.io/tx/32ee32b2c2458100a64ee04679c3961f7b714ba3a58e5c425c9ec9d5c4c5b670
    http://explorer.darkcoin.io/tx/4162c8bf1704a2eb3d1e8a4e81dfcae144d231c52e33f992814c0a1d381c3eb7
    http://explorer.darkcoin.io/tx/59f9bfb8d822b8044e143a8a2c32e753aaa50cc34e179579314a0ca85f200faa
    http://explorer.darkcoin.io/tx/57a403abac5e3c244b2206101d4419bf21ede3aee79a69a49eb9bf91dfc4d2ea
    http://explorer.darkcoin.io/tx/e00181d3a04aca647501cea5970b84e932838a71e4bbd4e1ed4a0c850d81d26c
    http://explorer.darkcoin.io/tx/92c4774c1459b71a111ed9dc04eac80a287040797a179c2618590455a3475114
    http://explorer.darkcoin.io/tx/bbba3c932ce873be4d7fcc99832f289e24e94e85dd4fe267d5f9a9daed055228
    http://explorer.darkcoin.io/tx/c802ef9a3c7bf82fa95a6bd9afd05eb8ce656e6a292246c2600ae47298d9aefc
    http://explorer.darkcoin.io/tx/741b07d77cc42c586228a4704bb9c25e2552277399f443c79e08c1af41004e04
    http://explorer.darkcoin.io/tx/fd2f659f41239383bd3ff48062adfee3735c5c35155d2bee045cb044f4f4218e (source)

    It’s worth noting that Darksend anonymizes large portions of Darkcoin at a time, so a mixing session like the one above can be used to send many different anonymous transactions afterward.

    Conclusion:

    We would suggest CoinShuffle and DarkWallet not be used for any type of sensitive transactions due to these flaws in the design. The issues raised here will apply to a high percentage of all transactions that go through the anonymization process and result in the complete loss of anonymity for users involved.
     
    #2 eduffield, Jan 25, 2015
    Last edited by a moderator: Jan 25, 2015
    • Like Like x 30
  3. strix

    strix Well-known Member
    Foundation Member

    Joined:
    Sep 14, 2014
    Messages:
    140
    Likes Received:
    121
    Trophy Points:
    193
    Thank you so much Evan for providing this explanation. As someone who lacks programing skills it is sometimes frustrating to find that explanations of these matters to often fall into only two camps; either highly technical explanations filled with programming code, or simplistic explanations that amount to "trust me, I know what I'm doing." Your concise explanation respects our intelligence without demanding highly specialized knowledge. I now feel that I have a good understanding of the problems associated with other anonymization systems and of why DRK has a better implementation.

    In short I can trust your programing skills which I don't understand, because you have taken time to explain the logic, which I do understand.

    Again, thank you, and keep up the good work!
     
    • Like Like x 9
  4. aaxx1503

    aaxx1503 Active Member

    Joined:
    Feb 28, 2014
    Messages:
    113
    Likes Received:
    106
    Trophy Points:
    93
    • Like Like x 4
  5. miningpros

    miningpros New Member

    Joined:
    Jun 6, 2014
    Messages:
    27
    Likes Received:
    19
    Trophy Points:
    8
    great article, could non crypto people get confused that darkwallet has nothing to do with darksend
     
    • Like Like x 1
  6. buster

    buster Guest

    I find it funny that any time a flaw is discovered or pointed out by someone not in the Bitcoin camp they seem to take offense by the comments and posts. Sometimes I love reddit, but for the most part it's full of inbread fucktards who cant tell the difference between left and right. "Which way is up again?"

    Nice work on this advisory Evan, you deserve a lot more credit than you get.
     
    • Like Like x 6
  7. TaoOfSatoshi

    TaoOfSatoshi Grizzled Member
    Linguistic Dash Nation Founder Moderator

    Joined:
    Jul 15, 2014
    Messages:
    2,604
    Likes Received:
    2,572
    Trophy Points:
    1,183
    This, exactly. Well said! Who cares what they think at this point, we'll show them all eventually...
     
    • Like Like x 5
  8. Sub-Ether

    Sub-Ether Well-known Member

    Joined:
    Mar 31, 2014
    Messages:
    1,525
    Likes Received:
    1,259
    Trophy Points:
    183
    So by choosing a small number of low denominations for mixing makes tracing harder because all the denominations are going to look so similar, as opposed to many more unique values which would surely make tracking easier, plus the fact that the (randomizing) small change element is chopped off the end to pay the miners, making the transaction more tricky to track (if not impossible) because the formula does not add up(LHS ≠ RHS) as there is a unknown element (small change).
    Is this a kind of a complex variation of a none invertable hash function then?
     
  9. Raico

    Raico Well-known Member
    Foundation Member Dash Support Group

    Joined:
    May 28, 2014
    Messages:
    139
    Likes Received:
    143
    Trophy Points:
    193
    The light of technology and the innovation behind the Darkcoin illuminate the fog of lies and foolish.
     
    • Like Like x 1
  10. camosoul

    camosoul Well-known Member

    Joined:
    Sep 19, 2014
    Messages:
    1,992
    Likes Received:
    1,091
    Trophy Points:
    183
    Lols. People calling it an advertisement for DarkCoin... Well, by definition, Evan designed DarkCoin to solve these problems. It's the one that solves all this... BTC wouldn't do it. So, here's the project that does... It's not an advertisement it's just true... Fact: a thing that is true. Evan made it that way. How dare he mention the reasons why he did so...

    Even among cryptotards... Mass adoption? It'll never happen for any crypto when the majority of crypto users are till too dumb/petty to figure it out... And the totally clueless masses who can barely operate an iPhone? The percentage of the popualtion who can even comprehend the issues at hand, then subtract those who insist on denial and egotism... There might be 8 people on the planet qualified to even read what Evan says, much less talk to him about it or criticize him...

    "I R BAGHOLDER, HOW DARE YOU SAY STUFFS! CULT OF EVAN! TRUST MIXER WITH OBVIOUS CHANGE IS JUST FINE! I HAVE NO IDEA, BUT I BELIEVE! THE TV SAID ANON INTERNET DEVIL DRUG MONEY! IT MUST BE TRUE! EVANCOIN IS PUMPER SCAM"

    Whatever... I should charge a fee to let people get heard by me.
     
    • Like Like x 2
  11. AnarchicCluster

    AnarchicCluster Active Member

    Joined:
    Dec 22, 2014
    Messages:
    400
    Likes Received:
    409
    Trophy Points:
    133
    Dash Address:
    XgJkzjmW1onXH8EsaaZakN1GswjjnAYhUE
    How does it work? I am not well versed in this technology, but when I look at it, it doesn't really add up. 1DRK+0.1DRK+0.01DRK = 1.11DRk. Even if 0.03DRK goes to the miner for processing the transaction we are still 0.03DRK short. Does 0.03DRK go to the masternodes as well? If yes, does it mean that if I send 1.17DRK the receiver will get only 1.11DRK?
     
  12. splawik21

    splawik21 Grizzled Member
    Dash Core Team Foundation Member Dash Support Group

    Joined:
    Apr 8, 2014
    Messages:
    2,105
    Likes Received:
    1,418
    Trophy Points:
    1,283
    Count good :) you added one 0 too much ;)
    There is 1+0.1+0.1 not 1+0.1.0.01
     
    • Like Like x 1
  13. moli

    moli Grizzled Member

    Joined:
    Aug 5, 2014
    Messages:
    3,262
    Likes Received:
    1,837
    Trophy Points:
    1,183
    "1DRK + 0.1DRK + 0.1DRK."
    1.00 + 0.10 + 0.10 = 1.20
    1.20 - 1.17 = 0.03

    What Evan meant is to avoid a change back, you just pay the whole amount of 1.20 for something that costs 1.17, and the 0.03 will be a fee to miners. However the split between miners and masternodes is another issue according to their payment scale.
     
    #13 moli, Jan 29, 2015
    Last edited by a moderator: Jan 29, 2015
  14. AnarchicCluster

    AnarchicCluster Active Member

    Joined:
    Dec 22, 2014
    Messages:
    400
    Likes Received:
    409
    Trophy Points:
    133
    Dash Address:
    XgJkzjmW1onXH8EsaaZakN1GswjjnAYhUE
    Alright ,thanks guys for the clarification. it is 1+0.1+0.1 not 1+0.1+0.01 as I previously thought
     
    • Like Like x 3
  15. camosoul

    camosoul Well-known Member

    Joined:
    Sep 19, 2014
    Messages:
    1,992
    Likes Received:
    1,091
    Trophy Points:
    183
    Awesome sig, man.
     
    • Like Like x 4
  16. AnarchicCluster

    AnarchicCluster Active Member

    Joined:
    Dec 22, 2014
    Messages:
    400
    Likes Received:
    409
    Trophy Points:
    133
    Dash Address:
    XgJkzjmW1onXH8EsaaZakN1GswjjnAYhUE
    Thanks! It is a quote from Robert A. Heinlein's book ”The Moon is a Harsh Mistress ”
    I highly recommend the book.
     
    • Like Like x 2
  17. stan.distortion

    stan.distortion Active Member

    Joined:
    Oct 30, 2014
    Messages:
    822
    Likes Received:
    490
    Trophy Points:
    133

    Unfortunately this is very true, the cult of fiat has ingrained its self so deep in peoples heads that most are simply incapable of seeing value without reference to dollars, pounds, euros and are blinded to the risks and potential consequences of their own actions by layers and layers of regulatory cotton wool, such easy pray to those pulling the strings, slaves that fight to wear their chains. And it goes down so deep, endless layers with a sense of finally achieving freedom as each is pulled away that only serves to better hide the next layer of indoctrination, will we ever learn to see things clearly again, to listen to our instinctive sense of value and risk? Its become a religion, all hail our priests of value! What about or other religions, what have they hidden from us never to be seen again?

    Sorry for the off-topic rant, kind of sickened by how blind we are to the risk of fractional reserves on the exchanges at the mo and I'm sure there's plenty more I'm blind to, the truth seems so close but maybe its just convention all the way down to the basic animal.
     
    • Like Like x 1
  18. camosoul

    camosoul Well-known Member

    Joined:
    Sep 19, 2014
    Messages:
    1,992
    Likes Received:
    1,091
    Trophy Points:
    183
    Its not realy off topic, this strikes at the very reason why DRK exists.

    You can't force people to embrace freedom over slavery. But, for those who choose it, Evan has created DRK. Choice. We finally have one. Not all will choose to be free. Free will. For what is love but the choice to give it? Some wish to be robbed of it, some give it up for comforts and convenience, some would rather die on their feet than live on their knees...

    And by this truth, we know evil by it's desire to eliminate choice.
     
    #18 camosoul, Feb 1, 2015
    Last edited by a moderator: Feb 1, 2015
    • Like Like x 1
  19. stan.distortion

    stan.distortion Active Member

    Joined:
    Oct 30, 2014
    Messages:
    822
    Likes Received:
    490
    Trophy Points:
    133
    Thanks :) And to give those bastards trying to kill or control Bitcoin something serious to think about ofc. For everything else there's Darkcoin. Maybe for everything if they get their way, if semi-anonymous gave their minions a surprise just wait 'till they get a load of the real thing!
     
  20. camosoul

    camosoul Well-known Member

    Joined:
    Sep 19, 2014
    Messages:
    1,992
    Likes Received:
    1,091
    Trophy Points:
    183
    Be the consequence.
     
    • Like Like x 1
  21. LaurentMT

    LaurentMT New Member

    Joined:
    Feb 1, 2015
    Messages:
    4
    Likes Received:
    3
    Trophy Points:
    3
    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.
     
    • Like Like x 2
  22. Aswan

    Aswan Member

    Joined:
    Jun 26, 2014
    Messages:
    68
    Likes Received:
    216
    Trophy Points:
    73
    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
     
    #22 Aswan, Feb 3, 2015
    Last edited by a moderator: Feb 3, 2015
    • Like Like x 4
  23. LaurentMT

    LaurentMT New Member

    Joined:
    Feb 1, 2015
    Messages:
    4
    Likes Received:
    3
    Trophy Points:
    3
    +1 for payment as output of coinjoin transaction. Imho, this is how coinjoin should be used.
     
  24. LaurentMT

    LaurentMT New Member

    Joined:
    Feb 1, 2015
    Messages:
    4
    Likes Received:
    3
    Trophy Points:
    3
    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).
     
    • Like Like x 1
  25. Aswan

    Aswan Member

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

    LaurentMT New Member

    Joined:
    Feb 1, 2015
    Messages:
    4
    Likes Received:
    3
    Trophy Points:
    3
    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 ! ;)
     
  27. Aswan

    Aswan Member

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

Share This Page