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.htmAnd 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.htmThis 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.htmIn 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.htmHere 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
