CoinJoin: Bitcoin privacy for the real world

[caedes]

Darkwallet does indeed implement coinjoin, albeit using a centralized matchmaking service to setup the mixes.

Just to clarify, we (darkwallet) don't exactly use a centralized matchmaking service, nor did we do at any point (as I would define it anyways). We did use a centralized matchmaking server in our first proof of concept on this thread.

The current scheme works on top of any chat service, where we initially integrated a simple chat in our lobby and now it's the same lobby but the channels exist in a p2p network of all gateways so clients can connect to any gateway or gateways seed from any other gateway.

You are right otherwise we don't yet use ring or blind signatures at the moment, so restricted to 2 party coinjoins, but the general design is done so we can (more or less) easily implement more complex coinjoin protocols.

cheers!

[maaku]

Here's how we did it in the initial CoinJoin implementation we made.

* There's an anonymous chatroom (pre-negotiated shared secret in public room) accessible over Tor.
* Some dudes submit various outputs.
* Some dudes submit various inputs.
* Server replies back with a tx.
* Some dudes submit valid signatures.

If you are not linking outputs to inputs in the submission (say, by signing the request containing the outputs with the keys of the inputs), then you are leaving the protocol vulnerable to very easy to execute denial of service attacks. If you do close that DoS hole by signing the outputs with the inputs, then the sever operator at the very least knows the linkages and could log this information.

The solution, as explained in the OP, is blinding: link the inputs to the blinded outputs, and later anonymously reveal the outputs and the unblinded signature from the server. Then the participants know that the output was one of the original blinded outputs (because the server signed it), but they don't know which one. Even in a two-party mix with a facilitating server, the server doesn't know which output belongs to whom. If there is a DoS withholding of a signature at the end, the honest participants can elect to back out and reveal their blinding factors, thereby demonstrating their own linkages and preventing themselves from being DoS banned.

BTW, blinding is super easy to do. Using RSA it like a half-dozen lines of code.

We also did it for fixed units.

There is absolutely no reason to use fixed units. It adds no anonymity, and increases blockchain traffic.

[genjix]

ok thanks for the clarification, makes sense now.
caedes also gave me a similar explanation.

[christianlundkvist]

There is absolutely no reason to use fixed units. It adds no anonymity, and increases blockchain traffic.

This surprised me. Surely a transaction with inputs 5,5,5,5 and outputs 5,5,5,5 will have better privacy characteristics than one with inputs 15, 5 and outputs 1,2,3,14?  Or am I misunderstanding what "fixed units" mean?

[jeffersonairplane]

Pretty interesting OP. I find the complexity hinders from anonymity.

[anti-scam]

The promised update to the original Zerocoin/Zerocash paper (http://zerocash-project.org/media/pdf/zerocash-extended-20140518.pdf) has been released and it claims to reduce the size of a Zerocash transaction to under 1 kB and the time to verify a coin's spending transaction to under 6 ms. I have not fully read the paper yet, but am wondering if anyone has investigated these claims and whether or not these improvements would fully remove the barriers that previously prevented the protocol's integration into Bitcoin?

I am posting this here since I assume that there is a reasonable degree of overlap between those interested in Zerocash and those interested in CoinJoin. I apologize if this has already been addressed but I have been away for a while and am trying to catch up. I know that Peter Todd is advising the Zerocash team so I'm sure he has some valuable insight.

[maaku]

anti-scam: off-topic. please use the zerocash thread.

[Carlton Banks]

anti-scam: off-topic. please use the zerocash thread.

maaku, you do actually have to read the post before making OT admonishments

[genjix]

The promised update to the original Zerocoin/Zerocash paper (http://zerocash-project.org/media/pdf/zerocash-extended-20140518.pdf) has been released and it claims to reduce the size of a Zerocash transaction to under 1 kB and the time to verify a coin's spending transaction to under 6 ms. I have not fully read the paper yet, but am wondering if anyone has investigated these claims and whether or not these improvements would fully remove the barriers that previously prevented the protocol's integration into Bitcoin?

I am posting this here since I assume that there is a reasonable degree of overlap between those interested in Zerocash and those interested in CoinJoin. I apologize if this has already been addressed but I have been away for a while and am trying to catch up. I know that Peter Todd is advising the Zerocash team so I'm sure he has some valuable insight.

It sounds exciting from what I've heard, but it probably won't go into Bitcoin directly. We need to keep Bitcoin's consensus pure and untouched. We don't nearly know enough.

[anti-scam]

The promised update to the original Zerocoin/Zerocash paper (http://zerocash-project.org/media/pdf/zerocash-extended-20140518.pdf) has been released and it claims to reduce the size of a Zerocash transaction to under 1 kB and the time to verify a coin's spending transaction to under 6 ms. I have not fully read the paper yet, but am wondering if anyone has investigated these claims and whether or not these improvements would fully remove the barriers that previously prevented the protocol's integration into Bitcoin?

I am posting this here since I assume that there is a reasonable degree of overlap between those interested in Zerocash and those interested in CoinJoin. I apologize if this has already been addressed but I have been away for a while and am trying to catch up. I know that Peter Todd is advising the Zerocash team so I'm sure he has some valuable insight.

It sounds exciting from what I've heard, but it probably won't go into Bitcoin directly. We need to keep Bitcoin's consensus pure and untouched. We don't nearly know enough.

I find this response a bit confusing. In what way would Zerocash affect Bitcoin's consensus, assuming a one-to-one conversion rate? As for not knowing nearly enough, the whitepaper is pretty detailed and still seems to make provisions for including the protocol directly into Bitcoin. I don't mean to be argumentative, but I consider truly anonymous payments to be a "killer feature" that could very negatively affect Bitcoin's value if it lags behind. Of course there's no rush but it would seem prudent to me to start collecting a bounty.

[Michael_S]

Hope that this thread is appropriate:

I think the wide perception that CoinJoin (or DarkCoin) as such brings full anonymity is wrong.

I tried to write an educational memo to illustrate why only using CoinJoin (or DarkCoin) does not yet guarantee anonymity.

You can find it here: http://de.scribd.com/doc/227369807

[maaku]

maaku, you do actually have to read the post before making OT admonishments

He was asking about Zerocash. Zerocash has nothing to do with CoinJoin, and has it's own thread. I'd happy to discuss it there. In very short summary: Zerocash is not and never has been considered for inclusion on the bitcoin block chain. When the author references bitcoin he means the bitcoin protocol generally.

@Michael_S the point is that you multiple mixes, as well as opportunistic mixes each time you transact. Each mix increases the anonymity set. No one is claiming perfect anonymity a la Zerocash.

[genjix]

yep that's how ZeroCash and CoinJoin could work together. Both are pretty cool systems.

CoinJoin would be for your day to day payments.

ZeroCash would be for anonymising your savings.

(I'm just projecting here don't know full details) It seems like their plan is to build a layer on top of Bitcoin like how MasterCoin works. And that the ZC ledger tracks the Bitcoin one so you can convert to and from the ZC system. That's really exciting if so.

[dewdeded]

AFAIK ZeroCash needs a trusted accumulator. So it's just a science prototype and wont become a cryptocurrency, no one will use a cryptocurrency where:

- if an NSA agent contributed to the "trusted setup" there will be no privacy
or
- if an Mark Karpeles guy contributed to the "trusted setup" he can generate/create more coins than announced (as his crime would be invisible in the block chain)



Why use technologies based on trust, when we have trustless ones. Satoshi created Bitcoin specifically with the idea/key feature of not depending on trusting a third party.

[Carlton Banks]

maaku, you do actually have to read the post before making OT admonishments

He was asking about Zerocash. Zerocash has nothing to do with CoinJoin, and has it's own thread. I'd happy to discuss it there. In very short summary: Zerocash is not and never has been considered for inclusion on the bitcoin block chain. When the author references bitcoin he means the bitcoin protocol generally.

@Michael_S the point is that you multiple mixes, as well as opportunistic mixes each time you transact. Each mix increases the anonymity set. No one is claiming perfect anonymity a la Zerocash.

Surely a discussion about the way new developments in the Zerocash project relate to Coinjoin actually belong in their own exclusive thread, no? Technically, I mean.

[anti-scam]

In very short summary: Zerocash is not and never has been considered for inclusion on the bitcoin block chain

Considering the billions of dollars of other people's money that's at stake here, that seems like something that needs a public discussion and not a decree by fiat.

When the author references bitcoin he means the bitcoin protocol generally.

Here's a direct quote from page 10 of the paper: "Zerocash can be integrated into Bitcoin or forks of it (commonly referred to as "altcoins"); we later describe how this is done."

(I'm just projecting here don't know full details) It seems like their plan is to build a layer on top of Bitcoin like how MasterCoin works. And that the ZC ledger tracks the Bitcoin one so you can convert to and from the ZC system. That's really exciting if so.

I think that's being considered but I'm not sure if it's their final plan. It seems to me that, given some BTC developers' hostility toward their technology, they'd have an incentive to strike out on their own. As far as I know the infrastructure for Bitcoin sidechains is not yet in place so they can't go that route.

AFAIK ZeroCash needs a trusted accumulator. So it's just a science prototype and wont become a cryptocurrency, no one will use a cryptocurrency where:

- if an NSA agent contributed to the "trusted setup" there will be no privacy
or
- if an Mark Karpeles guy contributed to the "trusted setup" he can generate/create more coins than announced (as his crime would be invisible in the block chain)

Why use technologies based on trust, when we have trustless ones. Satoshi created Bitcoin specifically with the idea/key feature of not depending on trusting a third party.

Zerocash needs a "one time trusted setup of public parameters". It's not unique in that sense. Many cryptography systems can be broken if certain constants are chosen in a particular way. Bitcoin itself could potentially be broken if its curve parameters were backdoored in some way (see https://bitcointalk.org/index.php?topic=151120.0). I don't know exactly what the Zerocash team's plan to instill confidence in their public parameters is but it seems like a surmountable complaint.

[gmaxwell]

Bitcoin itself could potentially be broken if its curve parameters were backdoored in some way (see https://bitcointalk.org/index.php?topic=151120.0).

Incorrect.  People have speculated that potentially an attacker powered by non-public mathematical breakthroughs could select parameters in a way to make a system weaker against publicly-unknown attacks which require specific improbable curve characteristics. This is pure conjecture, however— though it's something prudent to be cautious about, it is not a known backdoor vector by itself. The process for selecting curve parameters already excludes known classes of bad curves, if we knew about any other classes we'd exclude those too.  In the case of Bitcoin our parameters were selected in a way where performance considerations removed their degrees of freedom (like the ed25519 parameters were selected), and are all explicable from first principles. In fact, they have an additional property that even if you drop some of the performance characteristics, and increment from the smallest possible parameter requirement the first curve of prime order you find is the one Bitcoin uses. Other cryptosystems also use nothing up my sleeve numbers, where an abundance of caution demands the designers pick them in a way that limit their degrees of freedom but at the same time no one knows of a way where control could be used secretly to do something bad— it's just a good practice, not a backdoor closed.

In the case of the GGPR'12 based SNARKs there is no comparable way to generate the parameters: The creation of the prover/verification keys requires computation using secret values, which— if known— completely compromise the soundness of the proofs. Here the backdoor is very concrete— not theoretical— when you know just a couple of the secrets you can do a few multiplies and have a false proof. Worse, there is no known way to use a nothing up my sleeve number to pick the parameters to convince people that no one could know the secrets. The best you can do is use process, like the CA system does (but potentially way better) to convince people of security.  This isn't insurmountable for _many_ applications, but it is not at all comparable to EC curve parameters, there is nothing in curve parameter selection that looks like a magic number where if the attacker knows it all is lost. As far as I know there nothing like this in widespread use, the nearest parallel I can think of is the backdoor in DUAL_EC DRBG, though in that case the backdoor was a "surprise" and no process to prove that the potential backdoor wasn't weaponized (because it was)— which certantly makes it more concerning. There are a fair number of proposed _theoretical_ cryptosystems which have similar assumptions (e.g. Any of the neat uses of obfuscation involve the obfuscation being established by a trusted party), but I'm not aware of these systems being put into production. One reason for this may be because theoreticians find trusted initialization to be more acceptable than practitioners do— the theoreticians just posit "A spherically honest cow in random-oracle derived motion faithfully creates the parameters", the practitioners are the ones that have to figure out how to approximate the spherical cow using three chickens, a reed-solomon code, and a priest.

It seems to me that, given some BTC developers' hostility toward their technology, they'd have an incentive to strike out on their own

Funny, I've seen similar disinformation published before— that person was unwilling (unable) to substantiate it— can you do better?   The comments I made on Zerocoin were, I think, reasonably positive— but at the same time the system as it was wasn't suitable for deployment, and was later replaced by a complete reboot with much better performance (also evidence by the fact that no altcoin has deployed it, though they made a nice implementation of the cryptosystem available). I don't think there was anything hostile there, I've spent time with the developers of it and I think they're great guys, ... and I don't know any other developers who have been hostile about it either, so I'd really like to know what you're talking about.

This has really gone off-topic, but I thought leaving the FUD sitting around would be harmful.

[Kiwigoeswest]

Interesting read. Perhaps someone can make test QT soon

[laurentmt]

Follow-up of discussion from this thread

A careless join is one in which the correct solution is obviously the most plausible. Note that evaluating different solutions to the matrix lends itself well to parallel processing, there is no time limit since everything is permanently recorded in the blockchain, and mass surveillance doesn't require 100% accuracy.

Probably the only way to make CoinJoin useful in real-world situations is to build into the clients the exact same type of analysis tools attackers will use to reverse the joins so that clients can evaluate any proposed join prior to agreeing to it. (That's a good subject for the other thread).

I like your remark about time limit and 100% accuracy. It remembers me an interview of a computer scientist working for an US intel agency. He was explaining how they were building a different paradigm for search: sometimes you ask a question and you don't get an answer because it's just too early. If you don't ask again later, you'll never know the answer. But if you let the question pending, till the "right" data is gathered and aggregated, then you start to get something very efficient.

You can apply the same principle to transaction graph analysis. Even if you're very carefull about the privacy of your transactions, one-time coinjoin is not enough if others participants are less carefull and can be deanonymized later.
For now, systematic coinjoin (as proposed by DarkWallet) seems the most serious option to enhance privacy since it would create a combinatorial explosion and would significantly raise the cost of deanonymisation. But I guess it also comes with a lot of others issues to solve (delay required, constraints on amounts, ...).

Moreover, till now, main heuristics used for analysis of the transaction graph are "quite simple" (tainting, "address reuse" and "change address" patterns) and I guess it's just the first generation (at least which is publicized). I'm quite sure that more elaborated tools (temporal patterns, behavorial patterns) combined with side-channels attacks (data gathered from peripheral systems like exchanges, merchants, ...) could provide stunning results.

[justusranvier]

Moreover, till now, main heuristics used for analysis of the transaction graph are "quite simple" (tainting, "address reuse" and "change address" patterns) and I guess it's just the first generation (at least which is publicized). I'm quite sure that more elaborated tools (temporal patterns, behavorial patterns) combined with side-channels attacks (data gathered from peripheral systems like exchanges, merchants, ...) could provide stunning results.

The problem is that those tools are all being developed behind closed doors, which gives the attackers an advantage. Too many people think a low taint score displayed on blockchain.info provides them with meaningful protection.

I'll predict though that for all this investment money flowing into Bitcoin startups, not one VC is going to fund investment into open source graph analysis tools that could help individuals measure their privacy and warn them before they do something that will compromise it.