This is a great idea.

This is something that Andreas Antonopoulos is always talking in his conferences. I think we must focus in real "third world" problems instead of western world merchants.

We must beat Western Union first, then other FIAT currencies

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

Agree


I have no doubt!

Search for the discussion between Evan and AnonyMint earlier this month to not waste your time trying to reinvent the wheel.

So if the masternodes are required to keep 1k DRK on them, why do any of sender A's coins even need to be used for the change? It would make more sense if it went something like this:

10 People send transactions which use the default 10 DRK. The master node parks the 100 coins and uses 100 of the 1000 DRK that are just sitting there with absolutely no tie to anyone's wallet addresses in the current block transactions. This way there will be a several block disconnect between you sending the coins and the coins actually getting to a recipient. If you try to analyze the block chain you'll see the coins go to a wallet, sit there for X number of blocks then it gets sent to another address. Neither the sender nor the receiver will receive the coins that they actually sent, but the same value of coins that other users have sent.

I hope that makes sense.

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.

Wouldn't the best solution be that the change payment to be randomized in amount and time, leading to multiple change sends and in different amounts. This would look like a bucket where you can increase the users and randomly select (with some priority protocol parameters). Like 10 people in a bucket? If the bucket even has internal addresses to do the same thing stated above for even more shading?

There was a bunch of questions on the development around here +/- about 5 pages

https://bt.irlbtc.com/view/421615.msg6025211#msg6025211

Darkcoin has been added to Bter.com 's BTC market

Deposit at

https://bter.com/myaccount/deposit/DRK

and Trade at

https://bter.com/trade/drk_btc

About time. BTC38, are you watching?