Darksend technical diskussion - anonymity, liquidity, improvements

A

Aswan

Active member
Hello,

I haven't been very active on this forum so far, but I think it's time to talk about these things:

Darksend, in the current implementation, has a few flaws I want to discuss and find possible improvements for.

Problem #1:

Denomination fee:
The denomination fee is always 0.0125 DRK per participant. There are always 3 participants per Darsend Tx making it a total of 0.0375 DRK.
While I agree that the Darksend Tx has to be of the same size for everyone due to anonymity implications, the fee itself is not mixed, meaning it will always link to the origin of the funds before they entered the Darksend process. Heres an example:
Address XmaH4tKi8jwdTkuyLVVvPrBLxwz2bc3rk7 has first been loaded with a little over 1000 DRK and then performed a Darksend Transaction for amout 98 DRK and then added another ~34 DRK to it's darksend pool, resulting in the funds being Dark sent to different addresses as 10.00000001 and 1.00000001 bits in this transaction.

Theres also some change of 0.71363402 which has not become part of the Darkcoin pool. Now, for further Darksend rounds, technically and for the sake of anonymity, none of those outputs should be re-linked to XmaH4tKi8jwdTkuyLVVvPrBLxwz2bc3rk7.
However, in the next round of Darksend they are linked back to XmaH4tKi8jwdTkuyLVVvPrBLxwz2bc3rk7 because the fee of 0.0125 DRK is paid from there. The same goes for the next round after this one again.
Again the fee is being paid from XmaH4tKi8jwdTkuyLVVvPrBLxwz2bc3rk7 linking it to all further rounds of Darksend.

This is a real issue, especially because theres only 3 participants per Darksend round (and each round connects the transaction to the 3 origin address due to this fee issue). This means there are only 2 Parties to check (of which we know the origin addresses) in order to de-anonymize the 3rd one as well.
People talk about malicious Masternodes, how about malicious liquidity providers removing all other layers of Darksend anonymity because of the fee issue?

Solution:
Send the fee through Darksend as well. That way each fee will be paid by an output of a Darksend transaction and not be linked to the origin address.
This means that an observer is able to know how many Darksend rounds are still to come for the outputs of a Darksend transaction, but it does not enable him to know how they are devided amongst the Darksend outputs and it does not allow him to know how many rounds each output has already gone through, so I do not see an issue with that.


Problem #2:

Liquidity and denomination size:
Currently, there are different denomination sizes of which the most common ones are 1.00000001, 10.00000001 and 100.00000001 with the latter one being used less frequently than the other 2. There are higher Darksend denomiation sizes but they are rarely used.

Also, we all know there is currently a liquidity problem resulting in long waiting times when trying to create a Darksend transaction. I see the way denomination is handled as one reason for the long waiting times and the low liquidity.

When someone creates a Darksend Transaction with denominations of 100.00000001, 10.00000001 and 1.00000001, then be has to wait for someone else who has at least one of each. If he finds someone who has the ~10 DRK and the ~1 DRK denominations, but not the ~100 denominations, he can't mix with him.
And thats quite reasonable since it woudl mean that, in the end, the ~100DRK denomination would be easily linked to an input address.
Thats means there are a lot less potential Darksend participants for each constellation with a combination of ~10DRK and ~1 DRK ones being the most used one.
This results in less liquidity for everyone since each combination "plays on it's own level", not allowing them to be mixed.


Solution:
In order to allow all sorts of denominations to be mixed, we'd simply have to change the denominations from 10.00000001 to exactly 10DRK. The same for all the others.
That way a 100 DRK denomination can enter a transaction with only 10s and 1s and just be split into 10x10DRK.
With the current implementation this is not possible since you cannot split 0.00000001 DRK, but by "flattening" denominations to 1s, 10s and 100s, this wouldn't be a problem at all.
Suddenly, they could all be mixed adding a massive amount of liquidity to the Darksend feature.



Problem #3:

Re-mixing total amounts and spending in one go:
The problem i describe here is the fact that once an amount of DRK enters the Darkcoin mixing pool, there will always be the full amount mixed (at least to the smallest denomination). That means if I have ~55 coins being mixed, resulting in 5x ~ 10DRK and 5x ~ 1DRK denominations, each Darksend round will use all of them.
Together with Problem #1, which allows us to see the 3 origin addresses of each Darksend transaction, this can cause some anonymity issues.

If we want to spend all mixed coins at once, we ill have the same amount spent as we put in to mix. Because an observer can see the origin addresses, he can quickly link the funds spent to the address which put exactly that amount into the Darksend pool.
Now one could say don't spend them all at once then, but what if the 2 other participants do exactly that? There would only be your origin address left to tie the rest of the outputs to and it will always be correct.

Solution:
What I suggest is (in addition to the solution for problem #1), that Darksend does not take the whole Darksend pool to mix, but a random amount of denominated coins. This would result in more Darksend transactions, but also more liquidity (not in total amounts, but in number of participations). Unlike the other 2 solutions, this might be a lot of work and I a am not sure amount how to deal with the transaction fee in this case, so this solution is kind of a draft which I hope people will help develop. The solution to problem #1 should deal with a lot of issues problem #3 causes as well, so #1 and #2 should be fixed first I think.



If you are still reading, thanks and I hope you have something useful to add to the discussion.
If I forgot about something or if I just wrote plain bullshit because I didn't see something, then..meh... But I think these suggestions could help Darkcoin grow. I hope to get some useful input here, let the discussion begin :)
 
Well first things first...
paging eduffield

Secondly, I don't know about issue 2 and 3, but I have a memory of issue 1 being discussed and resolved. Via the issue outlined in 1 have you successfully traced coins through Darksend?
 
JGCMiner said:
Well first things first...
paging eduffield

Secondly, I don't know about issue 2 and 3, but I have a memory of issue 1 being discussed and resolved. Via the issue outlined in 1 have you successfully traced coins through Darksend?
Click to expand...

Via the issue in #1 I have been able to trace coins when other things applied as well (the "spending in one go"-issue described in problem #3).
When No coins have been spent, I was not able to trace the coins to the exact destination, but because of the denomination fee the 3 origin addresses were known ofc.
However, eventually the coins will be spent and there are multiple ways to link them to the origin address then (e.g. spending in one go), which de-anonymizes your coins if you do it or if the 2 other participants do it.
Also, if the change is re-grouped with the the other Darksend outputs in another Tx, it will eventually add up to the original Darksend pool input.


Edit: the tracing is actually pretty simple.

1. You receive a transaction which has Darksend outputs as input.
2. You verify they are all from the same transaction.
3. If they are, look up all 3 origin addresses (those are the addresses that pay the fee)
4. Look for the transaction that is creating the fee denominations
5. follow the non-fee part to the first darksend transaction.
6. Substract the leftover (the "odd" DRK amount in the Tx output) to know how many coins this address actually sent into the darksend pool
7. If the amount you received is higher than 2 of those darksend inputs, the transaction you received is from the remaining origin address.
8. If according to #7 there is more than 1 possible sender, check if the amount you got equals one of the inputs of the origin addresses. If yes, this is your origin address.
9.1 If #8 doesn't work, you can further investigate by grouping spendings together. This works especially well if it was not the last Darksend round for 2 of the participants, because then they will always spend the full amount, making it easy to find the remaining origin address.
9.2 Look for the origin addresses transactions. If they both did another Darksend round after the one you got your coins from, there is only 1 origin address left (the one that did not do another round). This if the address you got your coins from.
 
Last edited by a moderator:
Aswan said:
Via the issue in #1 I have been able to trace coins when other things applied as well (the "spending in one go"-issue described in problem #3).
When No coins have been spent, I was not able to trace the coins to the exact destination, but because of the denomination fee the 3 origin addresses were known ofc.
However, eventually the coins will be spent and there are multiple ways to link them to the origin address then (e.g. spending in one go), which de-anonymizes your coins if you do it or if the 2 other participants do it.
Also, if the change is re-grouped with the the other Darksend outputs in another Tx, it will eventually add up to the original Darksend pool input.


Edit: the tracing is actually pretty simple.

1. You receive a transaction which has Darksend outputs as input.
2. You verify they are all from the same transaction.
3. If they are, look up all 3 origin addresses (those are the addresses that pay the fee)
4. Look for the transaction that is creating the fee denominations
5. follow the non-fee part to the first darksend transaction.
6. Substract the leftover (the "odd" DRK amount in the Tx output) to know how many coins this address actually sent into the darksend pool
7. If the amount you received is higher than 2 of those darksend inputs, the transaction you received is from the remaining origin address.
8. If according to #7 there is more than 1 possible sender, check if the amount you got equals one of the inputs of the origin addresses. If yes, this is your origin address.
9.1 If #8 doesn't work, you can further investigate by grouping spendings together. This works especially well if it was not the last Darksend round for 2 of the participants, because then they will always spend the full amount, making it easy to find the remaining origin address.
9.2 Look for the origin addresses transactions. If they both did another Darksend round after the one you got your coins from, there is only 1 origin address left (the one that did not do another round). This if the address you got your coins from.
Click to expand...
You are correct. Evan needs to fix this.
 
Hello Aswan,

This is some great feedback, you've shown you really know your way around the protocol. It's great to get feedback, even if it's showing flaws in the system. I'll address these in the next release. But in the meantime, here's some thoughts:

Problem #1:

Darksend makes the transaction fees in batches, which usually don't have enough fee inputs to get a user all the way through the process. So at some point during the process the chain usually be broken. However, the issue still remains and darksend needs a fee mixing phase. That should at least be very fast because all of the inputs are one size.

Liquidity providers mix random amounts each round already, so they will make good partners for stopping this type of tracking until #3 is done. E.g. they don't spend the whole previous round as the default client does.

Problem #2:

I think the way it works is a pretty good mix of speed and lack of bloating. If we allowed inputs to be split up in the mixing phase like you say, you could split 100DRK into 10x10, or 10DRK into 10x1, that would cause a lot of bloating. I see this as being a problem with bootstrapping the currency. We just don't have enough active volume of Darksends to really speed up the process. There's really only a few mixes a day, it's went up recently, but it's still not very high. If we were doing hundreds a day, then it should just take an hour to complete.

In the future we actually shouldn't need liquidity providers. At that point we could increase the mixes to 4 or 5, which even makes the anonymity much more robust.

Problem #3:

This is a great idea and I'll implement it in the next version. It should speed up mixing for everyone on the network. By using random amounts each time, we'll match with random denomination mixes, which will match with more users.
 
Last edited by a moderator:
eduffield said:
Hello Aswan,

This is some great feedback, you've shown you really know your way around the protocol. It's great to get feedback, even if it's showing flaws in the system. I'll address these in the next release. But in the meantime, here's some thoughts:

Problem #1:

Darksend makes the transaction fees in batches, which usually don't have enough fee inputs to get a user all the way through the process. So at some point during the process the chain usually be broken. However, the issue still remains and darksend needs a fee mixing phase. That should at least be very fast because all of the inputs are one size.

If you were able to follow a transaction all of the way till the very last round, you still will not be able to tell who spent the coins. The fees are consumed by the process, so they can't tell you anything at that point.

Problem #2:

I think the way it works is a pretty good mix of speed and lack of bloating. If we allowed inputs to be split up in the mixing phase like you say, you could split 100DRK into 10x10, or 10DRK into 10x1, that would cause a lot of bloating. I see this as being a problem with bootstrapping the currency. We just don't have enough active volume of Darksends to really speed up the process. There's really only a few mixes a day, it's went up recently, but it's still not very high. If we were doing hundreds a day, then it should just take an hour to complete.

In the future we actually shouldn't need liquidity providers. At that point we could increase the mixes to 4 or 5, which even makes the anonymity much more robust.

Problem #3:

This is a great idea and I'll implement it in the next version. It should speed up mixing for everyone on the network. By using random amounts each time, we'll match with random denomination mixes, which will match with more users.
Click to expand...
Evan, I can find my original address by clicking on the tx, go to next page, click on the 3rd fee 0.0125 and it takes me to my original address.. This isn't hard to find like he said.

Edit: And my DRK had gone through 8 rounds anonymized.
 
Last edited by a moderator:
Solution #1:

I think I'm in favor of hard-forking the network to make Darksend transactions completely free. So there will be no fees to track at all. That means that we'll have to have the users pay another kind of fee to stop sybil attacks. Instead of the miners, they could pay either the masternode network (the one you connected to even), the development fund, foundation fund, etc. These payments would be passed to the masternode and could be cashed later to avoid timing analysis. Another upside to this is it's impossible to do in Bitcoin and the fees could be MUCH lower than 0.0125. Thoughts?
 
Last edited by a moderator:
eduffield said:
Solution #1:

I think I'm in favor of hard-forking the network to make Darksend transactions completely free. So there will be no fees to track at all. That means that we'll have to have the users pay another kind of fee to stop sybil attacks. Instead of the miners, they could pay either the masternode network or the development fund. These payments would be passed to the masternode and could be cashed later to avoid timing analysis. Another upside to this is it's impossible to do in Bitcoin and the fee's could be MUCH lower than 0.0125. Thoughts?
Click to expand...

Three thoughts/questions:

1. How exactly would this new fee --say, to the masternodes -- be enforced?

2. I thought the DS transaction fee was there not just to prevent Sybil attacks but also to ensure DS blocks get processed immediately by miners. I remember the days of 0.001 fees when RC4 was released and DS rounds >1 not working because of this issue.

3. This seems like a lot more work compared to adding a fees mixing phase. Is there some technical reason why the fee mixing phase can't be done or is a bad idea?
 
Last edited by a moderator:
eduffield said:
Solution #1:

I think I'm in favor of hard-forking the network to make Darksend transactions completely free. So there will be no fees to track at all. That means that we'll have to have the users pay another kind of fee to stop sybil attacks. Instead of the miners, they could pay either the masternode network (the one you connected to even), the development fund, foundation fund, etc. These payments would be passed to the masternode and could be cashed later to avoid timing analysis. Another upside to this is it's impossible to do in Bitcoin and the fees could be MUCH lower than 0.0125. Thoughts?
Click to expand...
Can you make DS free with NO fees from each round but when the anonymized DRK is spent, there's a fee attached to it and sent from the same pseudo address with the tx, which can not be traced back to the origin address?

Edit: Although I can see the problem with this.. How can we punish abusers and trouble-makers to DS..
 
Last edited by a moderator:
JGCMiner said:
Three thoughts/questions:
How exactly would this new fee --say, to the masternodes -- be enforced?
Click to expand...

I'm thinking the user will pay for Darksend access for a period of time. For example, you do one transaction for 0.1 to the Darksend access address, this is the very first thing you do when Darksend starts. Then you send that transaction ID, and a signature proving you own the input. That gives you access to darksend for 1 day or something.

JGCMiner said:
I thought the DS transaction fee was there not just to prevent Sybil attacks but also to ensure DS blocks get processed immediately by miners. I remember the days of 0.001 fees when RC4 was released and DS rounds >1 not working because of this issue.
Click to expand...

You're correct. That's what the hard fork is for.

JGCMiner said:
This seems like a lot more work compared to adding a fees mixing phase. Is there some technical reason why the fee mixing phase can't be done or is a bad idea?
Click to expand...

I think there's a problem with the fee mixing phase. That would be much easier, but every round of a darksend would still go back to 1 Darksend fee mixing transaction. So you could follow a transaction from round 8,7...1. If you control the last masternode, you could tell who owns the final Darkcoin.
 
eduffield said:
I'm thinking the user will pay for Darksend access for a period of time. For example, you do one transaction for 0.1 to the Darksend access address, this is the very first thing you do when Darksend starts. Then you send that transaction ID, and a signature proving you own the input. That gives you access to darksend for 1 day or something.



You're correct. That's what the hard fork is for.



I think there's a problem with the fee mixing phase. That would be much easier, but every round of a darksend would still go back to 1 Darksend fee mixing transaction. So you could follow a transaction from round 8,7...1. If you control the last masternode, you could tell who owns the final Darkcoin.
Click to expand...

Thanks.

I think your plan is a good idea.
 
JGCMiner said:
Thanks.

I think your plan is a good idea.
Click to expand...

I think it sounds good - although if users pay their 0.1DRK to gain access to the masternode network - what happens if their inputs dont get mixed after 1 day due to liquidity and or their inputs dont match with anyone.

There needs to be some sort of guarantee that if the users pay their 0.1DRK to access it would complete X number of rounds within a day...otherwise users would be spending 0.1DRK for a chance to mix with others..
 
Stealth923 said:
I think it sounds good - although if users pay their 0.1DRK to gain access to the masternode network - what happens if their inputs dont get mixed after 1 day due to liquidity and or their inputs dont match with anyone.

There needs to be some sort of guarantee that if the users pay their 0.1DRK to access it would complete X number of rounds within a day...otherwise users would be spending 0.1DRK for a chance to mix with others..
Click to expand...

There's no way to guarantee anything. I guess that's the only catch. As we get bigger, this shouldn't be a problem. There should be liquidity.
 
great to see the fast response from everybody towards the issues raised !
Well done team ....>
Tx Aswan for bringing this up !
 
You must log in or register to reply here.
Back
Top