Re: [ANN][DRK] DarkCoin | First Anonymous Coin | First X11 | First DGW

I spent a fair amount of time thinking about the discussion with dime, humanitee, luigi1111, camosoul and others yesterday about the anonymity of Darksend. I suspected that the logic behind darksend as currently implemented was not sound, and I thought it would be best to determine how exactly darksend was working, and do an in-depth analysis of a mixing cycle and the transactions that follow mixing.

...

Best,
Sim

Wow! This is great. About 400+ pages ago I talked about having a different kind of pool for change outputs only. Put in all of your change outputs and you'll get new fresh clean inputs of 10DRK. The client could automatically do this after each darksend, which would also get you new inputs for the next round.

I'm currently embedded in patching stratum and p2pool to support the masternode payments, which is why I haven't been around. It takes a lot of work to make something so different from anything else out there, dare I say, revolutionary?

On second thought, I'm not sure this solves the problem. My understanding is that you want to accumulate the dirty change in the wallet until it breaches a certain amount (say 10 for example), then it is washed in a "change only" wash with a bunch of "10" transactions. The problem I see is that even the clean coins could be linked to the original transaction. Just to explain:

John darksends 2 coins from A to C, gets 8 back as change on address X
a few days later..
John darksends 8 coins from B to D, gets 2 back as change on address Y

Y+X are submitted to the change mixing pool (10 coins), and come out "clean" at address Z.

The problem is that the coins at address Z are not clean really, they are "suspect", they could have possibly participated in any darksends that generated the dirty coins that composed the "change washing" pool.

Now when Johns wants to spend coins from A, B, and Z in the same transaction.

So if John wants to send coins from A+B+Z in one transaction, the fact that Z participated in a pool that contained X and Y is enough to expose A and B as the original participants in the darksend transaction.

Really it leaves us at the same position that we were at previously after the original darksends.

I hope that made sense.

I came up with a way better solution to this issue than my previous idea. Plus it's already supported by DarkSend, I'll just enforce it in RC3

John darksends 2.5 coins from A to C, gets 7.5 back as change on address X, Y, V, Z (X = 5DRK, Y = 1DRK, V = 1DRK, Z=0.5DRK )
Joe darksends 3 coins from E to G, gets 7 back as change on address W, K, J (W = 5DRK, K = 1DRK, J = 1DRK)
Suzie darksends 3.5 coins from K to Q, gets 6.5 back as change on address F, G, H (F = 5DRK, G = 1DRK, H = 0.5DRK)

Change is denominated into units of 5, 1, 0.5, 0.25, 0.1, 0.05, and 0.01 DRK. I'll introduce the precision limitation back again of 0.01DRK. So if you get 7.5 DRK of change back, you'll end up with 5DRK+1DRK+1DRK+0.5DRK.

You could still possible do taint analysis on denominations only used once, but this would be solved with multiple rounds in DarkSend.

Ok, well I think this is a great solution, definitely the best idea proposed so far. I have spent several hours thinking about ways to break it but I can't seem to come up with an Achilles heel.

A couple suggestions off the top of my head. I think it would help if there was some randomness added to the way things are denominated. Ie sometimes 1.5 is denomated 1+0.5 - sometimes it is denominated 1+0.25+0.1+0.1+.05 sometimes it is denominated 0.5+0.5+0.5. This would make it substantially harder to figure out what is going on in the blockchain

My other concern is that whoever gets the biggest amount of change is put in a precarious position. In the above example this would be John. If John sends X+Y+V+Z+A he is outing A as the sender to C. Even if John Darksends these coins he is still outing address A. Then once he outs himself, Joe (as the second largest change recipient (7DRK) is at risk of outing himself if he sends (or darksends) W+K+J+E. I suppose this whole scenario is a non-issue if we consider that more than one transaction can be sent into the pool from the same wallet, so it would be impossible to tell for certain who got the most change, as someone could have submitted multiple transactions and received 20,30,40 change coins to the same wallet.

Seriously though, this is a fantastic solution, I'm relatively certain the logic is sound, and the level of anonymity will be very high. I'll sleep well tonight for sure Cheesy

I was in the middle of going through this very logic myself, when I refreshed and saw your post.

I agree with the basic analysis: this proposed method seems to me to be flawless unless and until the largest change holder sends from all his change addresses associated with a particular DarkSend simultaneously with balance from his "main" address.

I'm still going to have to think about it more, because what if we DON'T consider the last sentence in your 3rd paragraph? Aren't we still *potentially* impacting anonymity?

I'm falling asleep right now, but I can't think of how you could actually secure this if the largest change holder did what you describe above. Even additional mixing wouldn't help as you could just track inputs and outputs all the way back once John did the bad deed.

I guess my point is: there's probably a large chance of additional "noise" being created that would make our potential analysis of John's coins impossible, but what if in a particular case this noise doesn't exist?

Or I'm just tired.

Yes if it we knew for sure that each 10 coins came from a separate wallet, there would be a big problem with the logic. But because multiple inputs can come from the same wallet and hopefully the denominization will be semi-random, so the logic is sound. If X+Y+V+Z+A shows up in a darksend, A is not necessarily outed because even though X+Y+V+Z adds up to 7.5 and there was a 2.5 output, it is possible that the Joe&Suzie transactions came from the same wallet and we are actually looking at W+K+G+H+A not X+Y+V+Z+A. It would be impossible to differentiate between X+Y+V+Z+A and A+W+K+G+H because both of these possible "change" combinations add up to 7.5 Grin

It is quite an eloquent solution actually.

There is still the problem evan mentions: if only one instance of a denomination is present it will be easy to out that person, but this seems like it would be an unlikely event once there are more than 4-5 people participating in the pool. Evan could even completely ablate this problem by coding it so that the darksend mixing won't start until there are at least 2 of every denomination represented.