Coinjoin improvement..?

[Realpra]

If you do a couple of coinjoin transactions and you require that you will be the mixer in one of them, won't your anonymity be perfect?

Normally the mixer would know who was who and you would only have anonymity towards the public - but if you do the mixing only you will know where the money went.

Is this already how it works or would this be an improvement?

[gmaxwell]

Normally the mixer would know who was who and you would only have anonymity towards the public - but if you do the mixing only you will know where the money went.

Nothing about CoinJoin requires the party assembling the transaction to know the input/output mapping.

In the big splashy CoinJoin post I simplified it down a model where there was someone acting like a 'server' that did the join, but I'd described it a year before in a more complex form that had perfect privacy and DOS resistance (though of course privacy is limited to the anonymity set size; though by building a CLOS network it can be arbitrarily large).

I simplified it because no one was picking up and running with the more complex and complete description-- doing so seems to have been a huge success, recent research suggests that coinjoins are now a pretty substantial chunk of the activity on the network.

Indeed you could use a non-private version with multiple stages such that at least one of them is completely trusted by each of the members, but I think the more complete protocols are a better way to get there.

No system for improved privacy is perfect, the important thing is just to make progress.

[TierNolan]

I simplified it because no one was picking up and running with the more complex and complete description-- doing so seems to have been a huge success, recent research suggests that coinjoins are now a pretty substantial chunk of the activity on the network.

How large is a "substantial chunk"?  Is there a specific project that accomplishes it?

[Realpra]

In the big splashy CoinJoin post I simplified it down a model where there was someone acting like a 'server' that did the join, but I'd described it a year before in a more complex form that had perfect privacy and DOS resistance (though of course privacy is limited to the anonymity set size; though by building a CLOS network it can be arbitrarily large).

Well as has been recently shown someone could make a bunch of clients acting as servers for coinjoin transactions and gather a lot of data so the current simple version is a bit too simple I think.

I think you should describe your complex version a bit more in detail. Its also not entirely without consequence if an algorithm is very complex, it leaves room for error if no one understands it.

HTTPS is great example of this, yes people just click a button, but the security doesn't work because the certificate system is flawed.

[nambich]

I think that nothing about CoinJoin requires the party assembling the transaction to know the input/output mapping.

[andytoshi]

In the big splashy CoinJoin post I simplified it down a model where there was someone acting like a 'server' that did the join, but I'd described it a year before in a more complex form that had perfect privacy and DOS resistance (though of course privacy is limited to the anonymity set size; though by building a CLOS network it can be arbitrarily large).

Well as has been recently shown someone could make a bunch of clients acting as servers for coinjoin transactions and gather a lot of data so the current simple version is a bit too simple I think.

I think you should describe your complex version a bit more in detail. Its also not entirely without consequence if an algorithm is very complex, it leaves room for error if no one understands it.

HTTPS is great example of this, yes people just click a button, but the security doesn't work because the certificate system is flawed.

If gmaxwell is referring to what I think he is, the way it works is roughly:
1. Parties connect to the server over an anonymous connection (e.g. over Tor) and request a blind signature on their outputs; they also submit their inputs.
2. From a fresh anonymous (e.g. over a new Tor circuit) connection, they send their real output. The server sees its signature and knows that this is one of the blinded ones from step (1).
3. They repeat step (2) for each of their outputs.

Once the server has as many unblinded outputs as it signed blinded ones, it can construct the merged transaction and submit it to the original parties from step (1) for signing.

[Cryddit]

We used to play a game in college called "Beer hunter."  Although, if you were a nerd like me, root beer worked just as well.   

The way it worked, you shake the hell out of one bottle so it'll pretty much explode and go all over when it's opened.  Then you put that bottle into a six-pack with five unshaken.  One guy turned his back and the other guy swapped the bottles around, then the other guy turned his back and the one guy swapped the bottles around.  End result: neither of them knows where the shaken bottle is.  Then both of them take a bottle and open it. 

Why was this entertaining?  I dunno.  I think it was mostly entertaining to people who were already drunk.

But it could be adapted to a real mixer protocol.

If you have a few people who each take a couple of turns permuting the outputs, where nobody else can see what permutations they're making, then none of them - and nobody else - will know which output went where unless they all collude.

[andytoshi]

Cryddit, if the beers were all labeled with unique addresses this game would not have worked

[Realpra]

If gmaxwell is referring to what I think he is, the way it works is roughly:
1. Parties connect to the server over an anonymous connection (e.g. over Tor) and request a blind signature on their outputs; they also submit their inputs.
2. From a fresh anonymous (e.g. over a new Tor circuit) connection, they send their real output. The server sees its signature and knows that this is one of the blinded ones from step (1).
3. They repeat step (2) for each of their outputs.

Once the server has as many unblinded outputs as it signed blinded ones, it can construct the merged transaction and submit it to the original parties from step (1) for signing.

Can you explain the blind signatures in detail? I mean I can name a bunch of cryptographic algorithms too, but it makes no sense unless I explain what I'm doing with it and when.

Some mathematical functions can be executed on encrypted data and when decrypting the result you will get the actual result. HOWEVER is ECDSA one such function?
If it is, how does this help you?

You say the participants submit to the server their outputs... right there; a bitcoin output is your address - so if that is what you submitted, the server will know exactly where each participant wants their money to go.
It won't matter WHERE it comes from to the FBI.

It won't matter if the other participants don't know where they sent their money (due to blind sigs) if the server knows. An attacker could set up and run a bunch of mixing servers and voila all coinjoins are unmasked.

This is why I suggest switching WHO is the mixing server from round to round.

[gmaxwell]

He gave you a nice link that explains blind signatures; and he explains how they're used for this.  Any blind signature scheme works for that usage, and a regular schnorr signature (which works fine with the secp256k1 group) can be easily blinded. Please don't waste peoples time by having them explain well known cryptographic tools, especially when they already handed you an adequate link. It is disrespectful to others here to ask them to burn their time rather than trying for a few more moments with your own to actually understand what is being presented before just turning around and arguing with it.

You say the participants submit to the server their outputs... right there; a bitcoin output is your address - so if that is what you submitted, the server will know exactly where each participant wants their money to go

Please see step 2 in the post, it addresses this specifically. They reconnect anonymously (or send their messages over mixmaster or bitmessage or whatever you like).  The server has no idea how the new participants are at all related to the old ones; the server learn nothing more than someone observing the transaction on the network would (except greater confidence that it was a CoinJoin at all).

if the server knows

The server doesn't know, that is the purpose of the blind signatures-- all the participants know that the outputs came from a valid participant, but not which participant they came from. Making the operation private from the server is what accomplished by the protocol described at a high level above.  No blind signatures are required to make things private from the other participants, that just happens automatically.

[belcher]

doing so seems to have been a huge success, recent research suggests that coinjoins are now a pretty substantial chunk of the activity on the network.

Is this research published anywhere?

[laurentmt]

doing so seems to have been a huge success, recent research suggests that coinjoins are now a pretty substantial chunk of the activity on the network.

Is this research published anywhere?

+1
I'm curious to know which criteria are used to define a coinjoin tx (fingerprint, entropy, ...)

[gmaxwell]

doing so seems to have been a huge success, recent research suggests that coinjoins are now a pretty substantial chunk of the activity on the network.

Is this research published anywhere?

http://fc15.ifca.ai/preproceedings/bitcoin/paper_5.pdf

But.. Hm. Her slides for this had usage figures that don't appear to be in the paper, I'll see if I can find them.

[laurentmt]

doing so seems to have been a huge success, recent research suggests that coinjoins are now a pretty substantial chunk of the activity on the network.

Is this research published anywhere?

http://fc15.ifca.ai/preproceedings/bitcoin/paper_5.pdf

But.. Hm. Her slides for this had usage figures that don't appear to be in the paper, I'll see if I can find them.

Thanks for the link !

EDIT:
Found the method used to detect coinjoin txs:

We defined this pattern as any transaction having more than five inputs and more than five outputs, and looked at how many transactions matched this pattern (which is admittedly only roughly correlated with coinjoins, but as coinjoins are indistinguishable from other transactions we cannot do better than an approximation).

TBH, that sounds like a terrible heuristic to detect coinjoin txs 

[belcher]

Possible coinjoins are transactions with more than two outputs of the same value, and at least that number of inputs. Even then they might be made by a single person.

EDIT: So this is not a coinjoin according to that paper?
https://blockchain.info/tx/92a78def188053081187b847b267f0bfabf28368e9a7a642780ce46a78f551ba

[laurentmt]

Possible coinjoins are transactions with more than two outputs of the same value, and at least that number of inputs. Even then they might be made by a single person.

EDIT: So this is not a coinjoin according to that paper?
https://blockchain.info/tx/92a78def188053081187b847b267f0bfabf28368e9a7a642780ce46a78f551ba

Nope. But according to their heuristic this tx (built by an exchange to process a batch of widthdrawals) is a coinjoin...

[Peter Todd]

EDIT:
Found the method used to detect coinjoin txs:

We defined this pattern as any transaction having more than five inputs and more than five outputs, and looked at how many transactions matched this pattern (which is admittedly only roughly correlated with coinjoins, but as coinjoins are indistinguishable from other transactions we cannot do better than an approximation).

TBH, that sounds like a terrible heuristic to detect coinjoin txs 

Agreed - very few Darkwallet Coinjoin's will be detected by that huristic. I just checked my wallet and only about %10 of the Coinjoins had more than four outputs. The usual transaction pattern in Darkwallet is for there to be four outputs - sender destination, sender change, mixer duplicated amount, mixer change - and two to four inputs.