I spent a decent amount of time thinking about how to denominate the receiving address as well.  One solution I thought of, is not nearly as fancy as what you describe but sort of works.  You could just have the recipient provide a concatenated list of addresses from his wallet than can be used to do denominate the transaction.  This could be called a "Dark" address or something else equally silly  . and would look something like this:

ABCDEFGHIJK

where each letter represents a different address in the receiving wallet. The "Dark" address would be long as fuck, but it would get the job done - on the blockchain there would be no record of a special "Dark" address ever existing, only the individual addresses, A, B, C etc.

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

I'm not sure I understand.

John darksends 2 coins from A to C, gets 8 back as change on address X.
He then contributes 2 additional coins from another address in his wallet, address X1?

If that's how it works I'm not sure I get how this helps.  It just exposes the holder of address X1 as the person who darksent 2 coins to C.

I am probably misunderstanding where X1 S1 and W1 are coming from.

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 John 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 don't think randomizing the amount would help because the numbers will still add up to one of the change addresses.  

Ie
1+1+1+1 = 4
1.2+1.5+.3+1 = 4

So in either scenario if the dirty change addresses are spent at the same time with one of the other addresses linked to the darksend transaction it would be possible to do the same analysis.

I do think randomizing the amount of time that the coins spend in repeated washing cycles will help solve the issue, see A) , but alone A) will only help - it needs to be combined with some of the other ideas to really fix the problem.  Really C) is super important.  There need to be other 8's and 2's in the pool to mathematically hide John's address.

Yep, that is the exact scenario, I must have missed your post earlier. I am kinda late to the party here and have missed a lot of the early discussion.  Hopefully we will get a response from Evan on this issue.

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.

This analysis appears to have confirmed my suspicions.  There is a flaw in darksend as currently implemented that removes virtually all anonymity from the mixing.  Luckily there are many steps that can be taken to remedy this, as I describe at the end of the post.

Let me start by describing how darksend is currently implemented, I did all of my testing on RC1, so any changes made in RC2 will not be reflected in this analysis:

Let’s pretend A,B,C etc. are addresses.
John wants to darksend 2 coins from address A to D
Fred wants to darksend 3 coins from address B to E
Bob wants to darksend 4 coins from address C to F

The masternode inputs are:
10 coins from A
10 coins from B
10 coins from C

The masternode outputs are:

2 coins to D + 8 coins to X
3 coins to E + 7 coins to Y
4 coins to F + 6 coins to Z

X,Y, and Z are “change” addresses, these are the addresses that are used to send back coins to A,B,C – instead of sending them back to the same address they are sent to a different “proxy” address in the same wallet.

As you can see, it is obvious which change address pairs to which darksend recipient address.
2+8 = 10, 3+7 = 10, etc.

But it appears (at this point at least) to be impossible to determine if someone is sending 2 coins to D and receiving 8 back in change or vice versa (sending 8 and recieving 2 back).  Later I will show you how this can be determined by analyzing the blockchain.

If we are given only this much info the transactions remain anonymous, as there are still 3 possibilities for each darksend:

A sent D&X, or E&Y, or F&Z
B sent D&X, or E&Y, or F&Z
C sent D&X, or E&Y, or F&Z

Now here is where the problem arises:

Let's pretend John has 500 coins at address A, he darksends 2 coins to address D, his wallet is deducted 10 coins.  The masternode sends John his “change”, 8 coins, which he receives at new address X. At the end of the darksend transaction everything is fine and dandy.  Johns has 490 coins at address A, and 8 coins at address X there is no way to link address A and X so he is safe, he might even have other addresses in his wallet that contain coins.

So far, so good.  BUT, John decides to buy something shiny, it costs a lot of coins (550 coins to be exact). So he sends 550 coins to address G, when he does so his wallet looks at the available addresses in his wallet and sends out 650 coins to address G.  On the blockchain it looks like this:

Input
490 coins from address A
52 coins from address F
8 coins from address X

Output
550 coins to address G

So this is the problem with the logic behind darksend as it is currently implemented.  The transaction itself is fine, the problem lies in the fact that a "change" address is created “address X” which acts like a ticking time bomb, capable of exposing darksend transactions well after they were conducted.  The transaction above exposes address A (with 100% certainty) as the sender of 2 coins to address D above.

Now I’m going to walk through an example on the blockchain to show you how one can analyze the chain to unravel the darksend mixing. Here is what the mixing step looks like on the blockchain:

http://chainz.cryptoid.info/drk/tx.dws?249282.htm

And if we map out John’s transactions (just by looking at the blockchain with no other info)



A: http://chainz.cryptoid.info/drk/tx.dws?249273.htm
This is the initial step when darksend is initiated.  All of the coins (22) from the address XbaY4 are subdivided into three pieces and assigned a new address. Only the piece of size 11.889 will be carried through towards the mixing transaction, the other two pieces will sit dormant in the user’s wallet.

B: http://chainz.cryptoid.info/drk/tx.dws?249281.htm
In this step 11.889 coins are divided into three pieces, the piece of size 10 will enter the mixing reaction, the two smaller pieces (1.778 and 0.11) are returned to the users’ wallet with a new address.

C: http://chainz.cryptoid.info/drk/tx.dws?249282.htm
This is the mixing step that is performed by the masternode John’s 10 coins from address XvGuC are sent into the pool with two other 10 coin inputs. 2 coins are sent to the darksend receiving address (Xpahw), and 7.999 coins are sent back to john’s “change” address XvitP.  Up to this point everything is anonymous and working well, the problem though is that address XvitP will at as a “ticking time bomb”, potentially acting as the key to unlock John’s contribution to the mixing step at some point in the future if this address is ever used in another transaction.

D: http://chainz.cryptoid.info/drk/tx.dws?249706.htm
Here the ticking time bomb goes off.  John sends 19.997 coins to address XjE6N.  The wallet uses 5 different inputs from three different addresses.  XfsVr, XvGuC are both linked to the darksend address Xbay4, these are packaged together with the dirty “change” address XvitP, and sent to XjE6N.  Looking back at the green box C, we can see that this outs John's address  XbaY4 as the initial darksender of 2 coins to to destination address Xpahw.  This is the essence of the problem.

Ok, so how can we solve this problem?

Here are my suggestions, not a comprehensive list for sure, listed by order of importance (IMO).

A) Randomized Serial Mixing
Darksent coins (both change and non-change) must be mixed more than once.  Importantly, the number of mixing cycles CAN NOT be fixed, as this would allow someone to know when a given input is expected to be finished mixing.  This is not good, it would defeat the whole purpose of mixing multiple times.  I propose that the number of mixing cycles be a random number, generated by the client, roughly between about 5 and 20 cycles.   Alternatively, this number could be set as a user-defined variable in an advanced settings menu.

B) More uniform pools
Each decimal place get’s its own pool.  Period.  Long decimal transactions can be divided into multiple pools.

C) Boost pool size and increase the number of duplicate inputs
The masternodes (or potentially even normal nodes that volunteer) could monitor the darksend pools, and automatically darksend transactions into the pool that match darksend amounts currently being washed. 2 coins, or 8 coins, for example to help keep John anonymous.   Also, if the pool size is 10, the wallet should attempt to send from an address that is as close to 10 as possible. If an address of exactly 10 is used, this removes the risk of exposing oneself in a later transaction.

D) Divide up change addresses
Instead of just address X (or in John’s case XvitP), break it into 8 addresses, each holding 1 coin.  Combine this with randomized serial mixing – wash each address a random number of times to maximize anonymity.

E) Smart wallet distribution of coins
If the change is 8 coins, the wallet should try NOT to send all 8 coins at once in a transaction – it should break up these coins when sending later transactions as much as possible.

F) Random transaction fees
Pay the masternode a small fee, and also increase anonymity in the pool at the same time.  Only the masternode knows how much fee you’ve paid.  This would help anonymize the smaller pool sizes (.01 pools and below)

E) Let's Brainstorm
There are other solutions I’m sure..  If everything above is implemented the anonymity of darkcoin will be extremely high, but there might be other great solutions I didn't think of, this is where you and our talented devs come in. Throw out your best ideas to increase anonymity

It's also worth mentioning that I haven't sold any of my coins since discovering the flaw, the future of Darkcoin is still extremely bright.  Evan is an amazing dev that should be able to fix this issue in no time. Sorry for the long post (:  

Best,
Sim

I like it.  Nice, minimalistic, clean.  Huge improvement IMO.

Yea, I usually use that one cuz it's so much prettier - but a couple hours ago the chains stopped updating on that site.

Any idea why the the addresses are all f'ed up on the official block explorer?

http://explorer.darkcoin.io/chain/DarkCoin

Yep, 45 BTC buy wall gets filled on mintpal, then another 112 BTC wall pops up to take its place.  Fun to watch  

http://chainz.cryptoid.info/drk/tx.dws?170330.htm

Well, after staring at several different transactions, I'm not even sure I know how darksend is working lol.

It's definitely not as simple as I am imagining... for one - the change addresses appear to be re-used, a new address is not generated each time from what I can tell.

Huge buy walls on cryptsy and mintpal 

Yep, but I think eventually there will be pools of 100, 10, 1, .1 -  anything below .1 could just be paid to the masternode as a fee for the mixing.

Plus we don't really want to go too low with the pool sizes because this would increase the amount of "dust" in the network.

Yep, I think remixing the change is the best option.  Even better would be to remix the change a user defined number of times     This would increase anonymity tremendously because anyone analyzing the blockchain would have no idea when the actual outputs were made, AND there would be less likelyhood of hitting a string of malevolent masternodes.


The masternode wouldn't necessarily have to forward the coins to the next masternode, they could just send it back to the client and have the client darksend the coins out again automatically.

Maybe one transaction doesn't prove anything 100%, but if you add up hundreds of darksends from the same address you could potentially mathmatically prove with 99.9999% certainty etc. Plus as dime explains, if sending a large transaction later the wallet will combine your clean coins with your dirty change wallets which will give away even more info.

Yes, stated very well  

Yep that would work.  The problem with multiple change addresses though is later if the person sends all of the coins on their change addresses to a new address you could analyze the blockchain and see that all of the change addresses merged into 1 address then work backward and link all of those addresses together in the original darksend.

>1. C did not receive 8 coins from E
>2. C did not send E 2 coins.

By looking at the blockchain you can easily determine that either 1) or 2) is true.

>3. Nothing links back to A anyway

It doesn't matter if nothing links to A, C and E are linked - so the coins are dirty.

>as the muxing is off-chain and no record is kept of it.

The mixing is off-chain but the inputs and outputs are all on the blockchain for everyone to see.

Thank god lol.