CoinJoin: Bitcoin privacy for the real world

[laurentmt]

I like this idea.

Providing a financial incentive seems a good way to increase adoption of privacy tools and transform dormant bitcoins in active money.

Moreover, some coinjoin txs (like the example in your post) provide a low entropy and it's really easy to link outputs.
By transferring a fee from taker to maker, the tx becomes more similar to a regular tx in term of entropy and you can't link outputs with 100% certainty.
The "downside" is that these txs still have a specific signature (#outputs >=4) different from the most usual txs (#outputs = 2).

Just a detail: Don't think your proposal will "solve" the third point from your post. Having more makers is nice but it won't remove attackers. And some could argue that your proposal will just help to fund them

[belcher]

I do wonder though, could this potentially compromise the privacy of coinjoin makers based on the unique fee amounts that they charge? If I'm charging 0.5773% per transaction, that might make it easy to identify which transactions I'm involved in. Or does this not matter?

An individual maker's fees won't be too different from anyone else because of market forces. There will surely be many many people offering to make coinjoin at almost exactly the same fee.

But you're right that coinjoin doesnt hide the fact that coinjoin is taking place. In the posted example (tx hash: c38aac9...) we know its a coinjoin but have no idea which 0.01btc output belongs to whom.

Moreover, some coinjoin txs (like the example in your post) provide a low entropy and it's really easy to link outputs.
By transferring a fee from taker to maker, the tx becomes more similar to a regular tx in term of entropy and you can't link outputs with 100% certainty.
The "downside" is that these txs still have a specific signature (#outputs >=4) different from the most usual txs (#outputs = 2).

Yep, it's inherent in coinjoin that you cant hide easily the fact that a coinjoin took place.
Individual outputs are still mixed though.

Just a detail: Don't think your proposal will "solve" the third point from your post. Having more makers is nice but it won't remove attackers. And some could argue that your proposal will just help to fund them

I never said it would
(Maybe implied it)

It's similar to the situation with tor nodes. More honest nodes make it harder for the NSA.

[HostFat]

I's a very good idea, I like it

Maybe this idea can be even used to give more funds to the DarkWallet team.

[little tiger]

it's a cool idea, but is there any simpler way to maintain the btc privacy?

[molecular]

here's an idea by belcher@irc regarding coinjoin implementation in darkwallet:

A proposal for an improvement to darkwallet's coinjoin system.
 
Darkwallet's coinjoin works with two parties. One party will wait around with bitcoins they wish to mix. Another party will connect with them whenever they want to do a transactions and the two parties will do a coinjoin. By analogy with exchange matching engines, I will call the first party the coinjoin maker and the second the coinjoin taker.
 
The idea is that there will be people acting as makers who will slowly mix their coins for the benefit of the takers who want to immediately mix.
 
Here is an example of a darkwallet coinjoin transaction
https://blockchain.info/tx/c38aac9910f327700e0f199972eed8ea7c6b1920e965f9cb48a92973e7325046
 
As you can see, the change addresses can be linked with the inputs but the address with outputs of 0.01btc cannot be linked. Mixing is achieved.
The maker/taker model solves the problem of having to wait around for someone who wants to coinjoin exactly the same amount as you.
 
There are a few small problems with this. I will propose an improvement.
 
First, the only people motivated enough to mix will be people who already have desire privacy. So, for the example of someone wanting to privately buy contraception and hide the fact from their parents, mixing may result in their coins being mixed with drug money. It is easy to imagine this ecosystem being split between 'clean' coins mostly owned by investors and 'dirty' coins owned by 'undesirables' of society. It's easy to imagine a blacklist system being made which these two groups are seperated and cannot cross the barrier of blacklists, which would be highly damaging to bitcoin fungiblility.
 
Secondly, there is little incentive to act as a coinjoin maker when you could just be a coinjoin taker and get your mixing done without any waiting.
 
Thirdly, a small number of coinjoin makers leaves open the possiblity of three-letter agencies offering coinjoin making, and using that role to deanonymize darkwallet coinjoins.
 
Proposal: Pay the coinjoin makers. They will put up offers to do coinjoin along with a fee they ask. The coinjoin transaction would be built up in a similar way to the above example, with the coinjoin maker fee being added to the associated change address and taken away from the coinjoin taker's change address.
 
An implication of this is that darkwallet coinjoin mixing will become like an almost-riskless savings account. We already see that holders of bitcoin are willing to earn just 0.006% per day by lending btc on the bitfinex exchange, and that contains a substantial risk that bitfinex will go disappear or be hacked taking all the bitcoins with it.
Darkwallet coinjoin with a maker's fees would be far less risky, the bitcoin private keys would never leave the owner's computer. This would likely result in investors pouring in. The huge relative supply of bitcoins along with the drought of other worthy bitcoin investments is likely to drive down the fees of mixing as the investors bid each other down.
 
The coinjoin takers will have access to tens of thousands of clean, untainted bitcoins to mix with at a very low price. The makers will have access to a very low risk investment for their bitcoins. Bitcoin fungiblility as a whole will benefit because the entire economy and flow of money will be more interrelated, making blacklists completely unfeasable. The market for coinjoin makers may end up so deep and liquid that three-party or even four-party coinjoins may become managable to organise.
 
 
~Belcher
PGP fingerprint: 0A8B 038F 5E10 CC27 89BF  CFFF EF73 4EA6 77F3 1129
 
 
some notes on the darkwallet example transactions
 
INPUTS
1FDCg = 0.0067
1FAkh = 0.0056
total = 0.0123
 
OUTPUTS
1MUZn = 0.001   total = 0.0062 => fee = 0.0005
1231P = 0.0052
1Fufj = 0.001   total = 0.0055 => fee = 0.0001
1iYSY = 0.0045
total = 0.0117
 
fee = 0.0006
 
so we can see the 1FDCg input address has the same owner as 1231P
 and that 1FAkh is owned by the same person as 1iYSY
 but cant tell from this tx which of those owns 1MUZn or 1Fufj
 
so we can see the owner of 1FDCg address paid 0.0005 for the miner fee
 while 1FAkh only paid 0.0001

it's mainly about incentivizing people to offer to be a coinjoin mixing partner by creating a market for this with a fee takers would pay.

[2586]

You're late to the party, molecular. 

Another idea: Instead of or in addition to specifying a max fee they're willing to pay, takers could specify an amount of time that they're willing to wait, and their wallet would pick a max fee based on that (similar to the new dynamic transaction fees in bitcoin-qt).

If a taker specifies a max fee of zero, in addition to looking for a zero-fee maker to pair with, their wallet should also look for other takers with similar transaction sizes to pair them with. Senders could even specify that they want to receive a fee rather than paying one, effectively turning them into makers as well, except that they want to send bitcoins in the process, rather than just idly mixing their funds.

These options do increase the complexity of the pairing algorithm, but would allow for a wider variety of preferences to be expressed on the mixing market. Incentivizing idle-mixing is a great idea, but we don't want to discourage send-mixing just because all the idle-mixers start expecting payment for it.

[HostFat]

As it seems that just-mined-bitcoins have a higher value on privacy, it would be cool to have something that show this to the end user.
Something that show that some "offers" are better than others.

[laurentmt]

@belcher:
The idea surely requires some more thoughts (potential incentives for sybil attacks, ...) but I like the analogy with mining.
Miners are incentivized to ensure network security by blocks rewards and txs fees.
With this model, users are incentivized to ensure better network privacy thanks to "coinjoin fees".
Note that people at unsystem may have considered a similar idea (see bottom of this page).

Another idea: Instead of or in addition to specifying a max fee they're willing to pay, takers could specify an amount of time that they're willing to wait, and their wallet would pick a max fee based on that (similar to the new dynamic transaction fees in bitcoin-qt).

If a taker specifies a max fee of zero, in addition to looking for a zero-fee maker to pair with, their wallet should also look for other takers with similar transaction sizes to pair them with. Senders could even specify that they want to receive a fee rather than paying one, effectively turning them into makers as well, except that they want to send bitcoins in the process, rather than just idly mixing their funds.

These options do increase the complexity of the pairing algorithm, but would allow for a wider variety of preferences to be expressed on the mixing market.

Interesting idea.
IMHO,we should make a distinction between what is defined at protocol level (e.g pairing of maker & taker if fees match) and more complex behaviours implemented by wallets (e.g. taker defines the max fee he wants to pay and how long he can wait and the wallet applies a strategy to get a coinjoin which optimizes user's goals).
But I fully agree that UX will be key for adoption and that we should avoid too complex schemes.

Incentivizing idle-mixing is a great idea, but we don't want to discourage send-mixing just because all the idle-mixers start expecting payment for it.

That's another very good point but I'm not sure I reach the same conclusion.

Being a "constant" maker implies a few things :
- your computer remains online and consumes energy => being a maker implies a cost (not comparable to mining costs but there's a cost)
- you keep mixable coins in an hot wallet instead of a cold wallet => being a maker implies some risks

I'm sure that privacy enthusiasts may accept the cost and risk and become "constant" makers without a reward but this free model doesn't incentivize others people to become "constant" makers. The risk is that send-mixing is discouraged because there isn't enough makers and mixing takes too much time.

With fees, we may expect a range of offers (from 0 fee proposed by privacy enthusiasts to some X,Y, ... fees proposed by others makers).
It seems reasonable to think that a fair "market price" should appear even if some makers may still propose 0 fee mixing in order to maintain the system.

[belcher]

@belcher:
The idea surely requires some more thoughts (potential incentives for sybil attacks, ...) but I like the analogy with mining.
Miners are incentivized to ensure network security by blocks rewards and txs fees.
With this model, users are incentivized to ensure better network privacy thanks to "coinjoin fees".
Note that people at unsystem may have considered a similar idea (see bottom of this page).

Yes. There's some good points raised by waxwing and others on the reddit thread that appeared.
https://pay.reddit.com/r/Bitcoin/comments/2ku4tc/darkwallet_forward_from_irc_coinjoin_proposal/

Also painlord2k had suggested an idea like this too on the dev mailing list in Nov 2013. The idea is quite obvious so I'm not surprised its been thought of a few times.


So Sybil attacks.
On the one hand it seems more honest coinjoin makers, motivated by their income, is a good thing because they crowd out the sybils.
On the other hand, now the sybils get paid too so their cost of maintaining a maker (running a computer online, owning large amounts of bitcoins) is slightly reduced.
Then there's also the coinjoin makers who were there in the status quo, people who just want to mix coins, don't mind waiting and would be willing to mix for free.
I'm not sure which way it would swing. I intuitively think Sybils will find it harder in the fee-paying model but I'm not sure how to prove or disprove that.

Now for a Sybil attack new identities need to be cheap and easy to create. But Sybil coinjoin makers are actually expensive to create and maintain because they must have bitcoins which cant be used anywhere else while the attack goes on. If bitcoiners are happy with mining power being proportional to processor power, I imagine they will be happy with coinjoin making power proportional to bitcoin ownership.

Maybe an analogy helps to clarify somehow? If tor nodes were paid would sybils find it harder or easier? If bitcoin nodes were paid would sybil nodes find it harder or easier to operate?

Would appreciate thoughts.

As it seems that just-mined-bitcoins have a higher value on privacy, it would be cool to have something that show this to the end user.
Something that show that some "offers" are better than others.

IMHO I would be against reducing the fungibility of bitcoins. Part of the purpose of all this coinjoin stuff is to keep bitcoins fungible so that it can be a good form of money.
But your idea could be implemented by the makers publishing the UTXO they will use, and the takers can scan the entire blockchain to see how close it is to a coinbase transaction.



To people who like this idea. Be honest, how much did you like the part about generating an income from your own hoarded bitcoins.
I'm guessing the psychological effect of earning interest on your coins, even if its only a few thousand satoshis a day, will be very strong.
You all love getting money for doing nothing. Of course you do, that's part of the reason you chose to save and invest (In bonds, shares, and yes, bitcoins) rather than consume your entire income.

So we have to be careful our greed and entrepreneurial rapture don't blind us to some problem (sybil attack, etc)

[2586]

So Sybil attacks.
On the one hand it seems more honest coinjoin makers, motivated by their income, is a good thing because they crowd out the sybils.
On the other hand, now the sybils get paid too so their cost of maintaining a maker (running a computer online, owning large amounts of bitcoins) is slightly reduced.
Then there's also the coinjoin makers who were there in the status quo, people who just want to mix coins, don't mind waiting and would be willing to mix for free.
I'm not sure which way it would swing. I intuitively think Sybils will find it harder in the fee-paying model but I'm not sure how to prove or disprove that.

Now for a Sybil attack new identities need to be cheap and easy to create. But Sybil coinjoin makers are actually expensive to create and maintain because they must have bitcoins which cant be used anywhere else while the attack goes on. If bitcoiners are happy with mining power being proportional to processor power, I imagine they will be happy with coinjoin making power proportional to bitcoin ownership.

Performing a coinjoin makes the maker's funds unavailable for a little while, right? Or can it be done safely with unconfirmed outputs? Either way, it might make sense to require inputs to have a certain number of confirmations in order to drive up the cost of a sybil attack. If the attacker can't make their funds available again immediately after performing a mix, they'll be severely limited in the number of mixes they're able to participate in. Perhaps takers could specify a minimum number of confirmations that they want the maker's inputs to have.

Takers will need to be wary of automatically accepting the lowest-priced mix offers, since that will give attackers a way to get their offers taken more often than those of comparatively higher-fee honest makers. Some sort of fuzzing is probably in order, i.e. "pick a random offer from available offers with fee from 0% to 0.5%" rather than "pick the lowest offer available, not to exceed 0.5%". Depending on how paranoid the taker is, they may want to do one or more coinjoin sends back to themselves, then a final coinjoin send to their intended recipient, increasing their odds of getting at least one good mix.

To people who like this idea. Be honest, how much did you like the part about generating an income from your own hoarded bitcoins.
I'm guessing the psychological effect of earning interest on your coins, even if its only a few thousand satoshis a day, will be very strong.
You all love getting money for doing nothing. Of course you do, that's part of the reason you chose to save and invest (In bonds, shares, and yes, bitcoins) rather than consume your entire income.

So we have to be careful our greed and entrepreneurial rapture don't blind us to some problem (sybil attack, etc)

Got me. I'm currently lending a significant chunk of my bitcoin savings on Bitfinex, though I'm not entirely certain that my income from it outweighs the counterparty risk. I'd love to be able to eliminate the counterparty risk entirely.

Without fees, I'd still operate as a coinjoin maker, since I want financial privacy for myself, I want to "stick it to the man", and I want to help others gain financial privacy as well. However, being paid would make the difference between acting as a maker part time with small amounts and doing so full time with large amounts. Which is the whole point of this proposal, after all. 

[laurentmt]

So Sybil attacks.
...
Would appreciate thoughts.

A quick thought : I think the answer will depend on the type of attacker you consider.
My previous comment about 3 letters agency was almost a joke but I think that for this kind of "attacker", reward/no reward doesn't make any difference because of their financial resources. Having a financial incentive may increase the number of makers and you can expect that some people won't be catched by the attacker but I'm not really sure it will make a big difference.

To people who like this idea. Be honest, how much did you like the part about generating an income from your own hoarded bitcoins.
I'm guessing the psychological effect of earning interest on your coins, even if its only a few thousand satoshis a day, will be very strong.
You all love getting money for doing nothing. Of course you do, that's part of the reason you chose to save and invest (In bonds, shares, and yes, bitcoins) rather than consume your entire income.

So we have to be careful our greed and entrepreneurial rapture don't blind us to some problem (sybil attack, etc)

Human "greed" is precisely the interesting factor for this model.
Privacy usually comes with a cost (in term of UX or financial cost, ...) and no "obvious" reward (except for people having a "shadow" activity).
The outcome is that digital privacy is at a very low level for many people.
IMHO, introducing a reward may be an important factor to increase adoption.

Let's make a parallel with bitcoin security. This security is enforced by mining and full nodes.
Mining comes with a reward and hashpower is skyrocketing. Full nodes have no reward and their number is almost constant or decreasing...

[Duky]

Hi everybody, i have a question regarding the cascads and transaction fees.

So, in the first post it says that you can get better anonymity when you cascade your outputs.

If i have 5 BTC and find e.g. 3 People who also want to anonymize 5 BTC i can make a CoinJoin transcation tx_1 with them. The first (minor) problem is, that we have to pay transaction fees. So every praticipant have inputs with at least 5.1 BTC (0.1 BTC for fees). If we have that, we can make the transaction tx_1 where the outputs have a value of 5 BTC.
The problem that i see is, that if i want to cascade, say 3 times, i have to pay transaction fees every time.
I see two ways one could do that.

1. The transaction fees for the second transaction, which uses the output from transaction tx_1 is paid only from that output/input. So i have to find participants who want to make a CoinJoin Transaction with an Output of 4.9 BTC (5BTC - 0.1 Fee) which could be hard, or i find participants who want to make a transaction with less than 4.9 BTC. If i allow participants with lower values the rest is send to an change address of mine. But in this case i can't , in the beginning, know how much Bitcoins i have left in the output after say three cascades.
So if i want a cascade of three and at the end i want to have 5 anonymous BTCs the first Input must be 5.3 BTC -> output ist 5.2. The second Input is 5.2 BTC -> output 5.1 BTC. The third Input is 5.1 BTC -> 5.0 output.
I think it could be hard to find participants with exactly the amount of Inputs that i need. Furthermore i have to know in advance how long my cascade has to be and how much bitcoins i want in the end.

2. The transaction fees is paid by another Input.
So Alice makes transaction tx_1 with an  Input of 5.1 BTC -> output is 5.0 BTC.
The second transaction tx_2 consists of the Input with 5.0 BTC from the last transaction, and a new Input with 0.1 BTC for my fees.
Assume an attacker who can match all Bitcoin addresses to the person behind these addresses excluding the output addresses used for outputs in CoinJoin transactions.
If Alice uses an address  for the transaction fees input , which the attacker can match to Alice, the attacker knows which output of tx_1 belongs to Alice.
Why?
The attacker knows who participates in tx_1 because he knows the persons behind the inputs. The only thing he doesn't knows is, which ouput belongs to which participan. But if one output is used in a second transaction in which Alice pays the fees for, and no other input in that transaction could come from Alice, the only plausible way is, that Alice is the owner of the ouput from tx_1 which is used in tx_2. In that case the anonymity of the CoinJoin Transaction tx_1 is broken.
This even works if the fee Input comes from another CoinJoin transaction. You just have to look at the inputs of the CoinJoin transaction uses for the fee input, if one input matches an address of Alice you can be pretty sure, that the output from tx_1 also belongs to Alice.

So my question is, am i missing something, or is this really a problem when using cascades in CoinJoin. Cause i see no other option than the first case, if you want to use cascades and don't want the anonymity broken by the fees.

I hope you can unterstand what i mean.

Greetings
Duky

[Gyrsur]

is this live already?

[belcher]

I'm coding an implementation of my idea. Stay tuned.

By the way, does anyone have any ideas for the name of the project?

[HostFat]

I'm coding an implementation of my idea. Stay tuned.

By the way, does anyone have any ideas for the name of the project?

Yup, I hope to see it implemented on Darkwallet

[Sir Lagsalot]

I'm coding an implementation of my idea. Stay tuned.

By the way, does anyone have any ideas for the name of the project?

Good idea, belcher.

Mixtape!

edit: MixTip is probably better.

[teukon]

Hi everybody, i have a question regarding the cascads and transaction fees.

So, in the first post it says that you can get better anonymity when you cascade your outputs.

If i have 5 BTC and find e.g. 3 People who also want to anonymize 5 BTC i can make a CoinJoin transcation tx_1 with them. The first (minor) problem is, that we have to pay transaction fees. So every praticipant have inputs with at least 5.1 BTC (0.1 BTC for fees). If we have that, we can make the transaction tx_1 where the outputs have a value of 5 BTC.
The problem that i see is, that if i want to cascade, say 3 times, i have to pay transaction fees every time.
I see two ways one could do that.

1. The transaction fees for the second transaction, which uses the output from transaction tx_1 is paid only from that output/input. So i have to find participants who want to make a CoinJoin Transaction with an Output of 4.9 BTC (5BTC - 0.1 Fee) which could be hard, or i find participants who want to make a transaction with less than 4.9 BTC. If i allow participants with lower values the rest is send to an change address of mine. But in this case i can't , in the beginning, know how much Bitcoins i have left in the output after say three cascades.
So if i want a cascade of three and at the end i want to have 5 anonymous BTCs the first Input must be 5.3 BTC -> output ist 5.2. The second Input is 5.2 BTC -> output 5.1 BTC. The third Input is 5.1 BTC -> 5.0 output.
I think it could be hard to find participants with exactly the amount of Inputs that i need. Furthermore i have to know in advance how long my cascade has to be and how much bitcoins i want in the end.

2. The transaction fees is paid by another Input.
So Alice makes transaction tx_1 with an  Input of 5.1 BTC -> output is 5.0 BTC.
The second transaction tx_2 consists of the Input with 5.0 BTC from the last transaction, and a new Input with 0.1 BTC for my fees.
Assume an attacker who can match all Bitcoin addresses to the person behind these addresses excluding the output addresses used for outputs in CoinJoin transactions.
If Alice uses an address  for the transaction fees input , which the attacker can match to Alice, the attacker knows which output of tx_1 belongs to Alice.
Why?
The attacker knows who participates in tx_1 because he knows the persons behind the inputs. The only thing he doesn't knows is, which ouput belongs to which participan. But if one output is used in a second transaction in which Alice pays the fees for, and no other input in that transaction could come from Alice, the only plausible way is, that Alice is the owner of the ouput from tx_1 which is used in tx_2. In that case the anonymity of the CoinJoin Transaction tx_1 is broken.
This even works if the fee Input comes from another CoinJoin transaction. You just have to look at the inputs of the CoinJoin transaction uses for the fee input, if one input matches an address of Alice you can be pretty sure, that the output from tx_1 also belongs to Alice.

So my question is, am i missing something, or is this really a problem when using cascades in CoinJoin. Cause i see no other option than the first case, if you want to use cascades and don't want the anonymity broken by the fees.

I hope you can unterstand what i mean.

Greetings
Duky

I think I have a rough understanding of what you're pondering.  I believe that OP has dropped transaction fees from the introduction for simplicity and from the tone it should be clear that he's primarily interested in a little extra privacy as opposed to hardened secrecy.

If we assume the hostile environment of your scenario 2 and desire regular, thorough mixing then I would first think about dropping the "all inputs/outputs should be of the same size" assumption.  Of course, we'd have to take care here not to allow varying input/output sizes to reveal too much information.  If we want regular mixing we really also ought to tackle the issue of combining outputs (always a pain).  Here's a first thought:

Inputs	(5)		Outputs	(110)
Party_A:	1.5671 BTC		1 x	1 BTC
	0.3894 BTC		29 x	0.1 BTC
	0.0015 BTC		25 x	0.01 BTC
Party_B:	1.5000 BTC		33 x	0.001 BTC
Party_C:	0.7082 BTC		22 x	0.0001 BTC
	0.0203 BTC

(Fee: 0.0013 BTC)

I'm afraid I lack the time to explain everything I'm thinking here but I hope this example transaction gives you an idea or two.  I'll happily try to tackle a follow-up question if you have one.

[belcher]

I'm coding an implementation of my idea. Stay tuned.

By the way, does anyone have any ideas for the name of the project?

Yup, I hope to see it implemented on Darkwallet

Yep I agree.
Hopefully something like this will be in many kinds of wallets. An Electrum plugin also seems like a low-hanging fruit.

[belcher]

Last few months I've been working on an implementation of my idea.

I'm calling it Joinmarket.

https://bitcointalk.org/index.php?topic=919116.msg10096718

The coinjoiner bots meet in an IRC channel. The bots announce their orders in an open-outcry trading pit style. Transaction data is sent between users as IRC private messages. Encryption is a planned feature to stop the IRC server eavesdropping. I have plans one day to move away from IRC entirely and have the users meet in some kind of peer to peer network.

Github: https://github.com/chris-belcher/joinmarket
IRC: irc.freenode.net #joinmarket

[molecular]

Last few months I've been working on an implementation of my idea.

I'm calling it Joinmarket.

https://bitcointalk.org/index.php?topic=919116.msg10096718

The coinjoiner bots meet in an IRC channel. The bots announce their orders in an open-outcry trading pit style. Transaction data is sent between users as IRC private messages. Encryption is a planned feature to stop the IRC server eavesdropping. I have plans one day to move away from IRC entirely and have the users meet in some kind of peer to peer network.

Github: https://github.com/chris-belcher/joinmarket
IRC: irc.freenode.net #joinmarket

I checked it out, it's a great idea that already works! Thank you!

Looking at the TODO and some of the code it seems there's still quite a bit of work to be done, though.

Seems to me electrum integration would be a rather low-hanging fruit, no?