[Fundraise $12.5k] Implementing CoinJoin - anonymous, p2p mixing and more

[maaku]

Gregory Maxwell has outlined a protocol for constructing shared transactions which obscure linking of inputs to outputs and thereby increase privacy (by 'mixing' coins to disassociate taint), or enable join transactions such as a matched donation (“I'll contribute 10btc to cause XYZ if someone else does too”) or colored coin exchange. All of this is possible without a single change to bitcoin. Even though the transaction is constructed in public, ownership of the outputs is masked using chaum blind signatures.

As a weekend project I have started an implementation of CoinJoin using the JSON-RPC API, Bitmessage for distributed, p2p communication, and a SQL storage layer. I have posted the initial framework to Github, here:

https://github.com/maaku/coinjoin

Now that the scope of the project has been explored, it is unfortunately too large an undertaking to accomplish as a side project. I am therefore asking for donations so I can spend a significant portion of my working time devoted to it over the next couple of months.

For $12.5k I intend to write a command line program which can be daemonized (run in the background), and which collects incoming transactions and change outputs from a running instance of Bitcoin-Qt, organizes mixing transactions with other users anonymously over Bitmessage to achieve the desired level of privacy, and finally returns the anonymized coins to your wallet. It will be usable, though not user-friendly (no graphical tools, yet). Most importantly, it will implement a cryptographic protocol for privacy enhancing distributed mixing of coins which could eventually become a standard part of wallet applications.

If you would like to contribute to this project, please consider sending some coins to the following signed address. I will “bill” my time hourly up to the donation amount received, and post all source code to github (MIT license).

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Donation address for implementing
"CoinJoin" mixing daemon.

1CJRGzzZzjYbubXzmJERCoWqxNxgbjf5XG
-----BEGIN PGP SIGNATURE-----

iQIcBAEBAgAGBQJSLlNHAAoJECsa1YSJj/UDxI8P/3EBzwuCxjLzm/vxfQGnQDRR
rdcn6vHZGNDbxjuuLxDXUgPlAWSQ4/Cl+mYfzlDy3TtPX7tOTnEIZK3G5VPPuGuW
pEIl7r2FGQlKFxzyVFx0aYQ3f1VlHgvDhZM60DbhhHfm+uzgBYvIGVTXPWKHZTZ6
4KsV5Y8Y9jOA1C7KqAsI7rLuI59R3A/ovq7ItDpi5DsJb8KqZnKlVjcRWrrBd5Om
74h4WnI9dkaCFqY+alqb7uuGeEPld6eMPwCt7CneAdNu7AG21nW3Q4BR9Un/j861
Yxr9udod2uFzI7ULhj4MmbD20XSKVTUkFXo1BBzxa01yK9v/3JzRj97mT30kfY4h
QHn+pKmGTbVMJy+aiyLW+wX6UswKfF6krHeVa1BhEeQXSjhdNIp1y+2n1cbCqo5y
53MsxPD3pVMTf88uf4O7Eh7Srw1St1x4dXz5nBIdFQHm0IZ7dwrA3fojrLdrGjKP
DOnuH1Fr2NFDWnemwiJlab4AVS5F5/5Cm1jaYBWdl9LcKLr5O15M8OtZDNrcdRjJ
GupnNmn85E4Y6TLMUIqppwfqClLeVlaeam0DvChuRFy4QUAa521HBIpYQhUr8cq0
0O2tw0jnTZf/nMo+9Tk3vNPADQn26utUNCJdGQZTGfschxHWYijoEmTSG77KZRok
E/tYjHxnbnmL8l+5UMem
=ioqh
-----END PGP SIGNATURE-----

[1714155127]

1714155127

[1714155127]

1714155127

[1714155127]

1714155127

[bytemaster]

I am interested in funding such an effort... but would like to discuss how the effort could be done in a way that is usable by Project Quixote as well because the underlying tech could be used by everyone.

If you are willing to chat with me on skype, send me a PM and we may be able to arrange full funding for your effort.

[ghgr]

Thanks for sharing an implementation of the Coinjoin protocol! I would've loved to find a README file in your project explaining how the mix is carried out. It is really hard to deduce it just by looking at the source. The specification in gmaxwell's post, while very insightful, is too high level to apply formal methods of validation. I am glad you have an implementation, but I think we all will benefit with a low level specification of what coinjoin.py does.

I mean, something like what I've done in this post.

[Peter Todd]

As a weekend project I have started an implementation of CoinJoin using the JSON-RPC API, Bitmessage for distributed, p2p communication, and a SQL storage layer. I have posted the initial framework to Github, here:

(snip)

For 85btc I intend to write a command line program which can be daemonized (run in the background), and which collects incoming transactions and change outputs from a running instance of Bitcoin-Qt, organizes mixing transactions with other users anonymously over Bitmessage to achieve the desired level of privacy, and finally returns the anonymized coins to your wallet. (snip)

FWIW I strongly think this is the wrong approach for a few reasons.

First of all we really want CoinJoin transactions to be the standard way to make a transaction, and integrated into many different wallets by default. To meet that goal you need an standard based on very simple cryptography that anyone can write - mucking about with RSA primitives, while easy for a cryptographer, still doesn't meet that standard and it won't be re-implemented widely. In addition requiring Bitmessage also makes implementations much more difficult due to the extra dependency.

The second issue is more subtle: fancy multi-party chaum blinding protocols don't have any advantages over 2-party mixes unless you can achieve sybil resistance effectively, and if they decrease adoption of CoinJoin resisting sybil attacks is much harder. Now if you're doing a mix among, say, people with active bitcointalk accounts or people with good OTR ratings chaum blinding is valuable: it's hard to acquire those identities and the participants would rather the other participants not know where their funds went.

But if you'll do the transaction with whomever is currently available, like over Bitmessage as you propose, the only thing preventing a sybil is the cost in transactions fees - trivial if there aren't that many participants. The (three-letter-agency) can just as easily pretend to be the other 4 partners in the transaction; it's just as dangerous to use a chaum blinded mix as a series of 2-party mixes. But if coinjoin is implemented in a way that everyone can use it in their wallets, which requires transactions to be fast and implementations to be easy to make, that same three-letter-agency has to spend a significant fraction of all transaction fees to have a good chance of sybil attacking coinjoin.

In contrast my two-party-mix protocol requires only off-the-shelf cryptographic primitives, uses only one primitive - encryption to a ECC pubkey - not already used by standard Bitcoin wallets, includes a inherently DoS-resistant way to arrange the mixes over the existing P2P network, makes the PoW mechanism denominated in Bitcoins so attackers with custom hardware have no advantage over the defenders, has very low bandwidth costs, and can be easily done as a "by default" thing that wallets do for every transaction made.

I really think you should either make the bounty be for implementing that protocol, or make the bounty be for implementing a toolkit for groups - like the bitcointalk example - to arrange chaum-blinded mixes for their members. It's the latter application where the complexity of chaum blinding is really valuable, but for the former using chaum blinding is a good example of cryptographers getting enamored by fancy math and forgetting about the human factors of the systems they build.

FWIW I'm planning on writing a two-party-mix implementation myself, but I've got a day-job and I know I won't be able to finish it as fast as you could if you received funding; seeing it actually get implemented and integrated into widely-used wallets is much more important to me that getting credit for making it happen.

[maaku]

First of all we really want CoinJoin transactions to be the standard way to make a transaction, and integrated into many different wallets by default. To meet that goal you need an standard based on very simple cryptography that anyone can write - mucking about with RSA primitives, while easy for a cryptographer, still doesn't meet that standard and it won't be re-implemented widely.

Peter, RSA blind signatures are dead simple. All cryptographic libraries support the required primitive operations, albeit sometimes under different names. And the math itself is simple: you could even implement it in a few lines of Python (not recommended, however, as it'd be super slow):

Code:

token = (message * r^e) % N
blindsig = token^d % N
signature = (blindsig * r^-1) % N # <-- requires mult inverse mod N, simple algorithms exist

The difficulty in implementing CoinJoin is the standard software engineering problems of any distributed protocol, and not the cryptography itself. The crypto is remarkably simple. OpenSSL supports blind-signing directly, but even so I specifically chose RSA over other blind signature schemes because it is so straightforward to implement - multiplying large integers - even though it's quite a bit slower than more esoteric schemes. So yes, I take implementation complexity very seriously.

In addition requiring Bitmessage also makes implementations much more difficult due to the extra dependency.

I think you've misinterpreted my proposal. The work I've done so far specifies what those messages will look like, not the networks on which they are transmitted. It is a network protocol that can be run over any broadcast + point-to-point medium for which anonymous connections can be made. There is absolutely nothing tying this proposal to bitmessage, it is simply one of many possible implementation routes.

However the initial implementation will run over bitmessage because that is the simplist and fastest way to get started. I imagine that if/when this eventually gets adopted into Bitcoin-Qt and other wallets, it'll probably run over a modified version of the bitcoin p2p protocol, using Tor or I2P for the anonymous connections.

The second issue is more subtle: fancy multi-party chaum blinding protocols don't have any advantages over 2-party mixes ...

You are very focused on mixing, but that is only one application. There is also every category of group transactions from matched donations to group buys to auction bids, where 2 parties is only an edge case. There is also the possibility for an online facilitator (who gets paid) when the parties are not online often enough to arrange joins directly. And there is every other transaction with multiple inputs and multiple outputs, which desires a crowd to hide in. A multi-party Chaum blinding solution achieves that, whereas a 2-party mixer merely solves a single problem.

I really think you should either make the bounty be for implementing that protocol, or make the bounty be for implementing a toolkit for groups - like the bitcointalk example - to arrange chaum-blinded mixes for their members. It's the latter application where the complexity of chaum blinding is really valuable, but for the former using chaum blinding is a good example of cryptographers getting enamored by fancy math and forgetting about the human factors of the systems they build.

A toolkit for constructing group transactions is what I'm making.

And as a meta-point, I don't believe that bounties are the right tool for this job. If you donate to this campaign, you know what you're getting: X hours of my time to implement the spirit of this proposal, while understanding that I retain the right to make technical changes when it becomes necessary for reasons now unforeseen. Bounties, on the other hand, have too much variance, arbitrariness, and general risk for someone such as myself who makes his living off of it.

[Peter Todd]

Peter, RSA blind signatures are dead simple. All cryptographic libraries support the required primitive operations, albeit sometimes under different names. And the math itself is simple: you could even implement it in a few lines of Python (not recommended, however, as it'd be super slow):

Code:

token = (message * r^e) % N
blindsig = token^d % N
signature = (blindsig * r^-1) % N # <-- requires mult inverse mod N, simple algorithms exist

As Barbie said: Math is hard

Like it or not a lot of wallet and related software out there is being developed by people who would be able to handle some hashing and encryption primitives, but not that.

However the initial implementation will run over bitmessage because that is the simplist and fastest way to get started. I imagine that if/when this eventually gets adopted into Bitcoin-Qt and other wallets, it'll probably run over a modified version of the bitcoin p2p protocol, using Tor or I2P for the anonymous connections.

Ask yourself: why do you need Tor or I2P for this protocol? Remember that even requiring Tor is a big barrier to use.

Anyway as I've said before given that we want the majority of all transactions to be done with CoinJoin, and because the overhead of arranging CoinJoin tx's can be a small multiple of existing tx traffic, there's every reason to broadcast CoinJoin traffic on the Bitcoin p2p protocol itself. This also demands low bandwidth solutions, which multi-party RSA isn't.

The second issue is more subtle: fancy multi-party chaum blinding protocols don't have any advantages over 2-party mixes ...

You are very focused on mixing, but that is only one application. There is also every category of group transactions from matched donations to group buys to auction bids, where 2 parties is only an edge case. There is also the possibility for an online facilitator (who gets paid) when the parties are not online often enough to arrange joins directly. And there is every other transaction with multiple inputs and multiple outputs, which desires a crowd to hide in. A multi-party Chaum blinding solution achieves that, whereas a 2-party mixer merely solves a single problem.

I'm focused on mixing because it's the most pressing need right now - indeed the reason why I suggested the idea of a bounty and the name "CoinJoin" to gmaxwell in the first place. Auction bids and groups buys are much more niche things, and farther off in the future. In any case the privacy problems of them that make blinding useful are greatly lessened if obtaining anonymous coins is easy in the first place.

Your example of a facilitator is also much less important if CoinJoin is well used: if 10% of the transaction volume used CoinJoin you'd only have to wait a matter of seconds or maybe minutes anyway to mix coins.

I really think you should either make the bounty be for implementing that protocol, or make the bounty be for implementing a toolkit for groups - like the bitcointalk example - to arrange chaum-blinded mixes for their members. It's the latter application where the complexity of chaum blinding is really valuable, but for the former using chaum blinding is a good example of cryptographers getting enamored by fancy math and forgetting about the human factors of the systems they build.

A toolkit for constructing group transactions is what I'm making.

That's fine, but I do want people to understand that if that's what you are doing, their money will take a lot longer to be turned into the goal of "fairly anonymous coinjoin tx's everywhere" than it could otherwise. To be frank if you were focused on something targeted and pragmatic I myself would be willing to donate to the effort, but as it stands I'm not.

And as a meta-point, I don't believe that bounties are the right tool for this job. If you donate to this campaign, you know what you're getting: X hours of my time to implement the spirit of this proposal, while understanding that I retain the right to make technical changes when it becomes necessary for reasons now unforeseen. Bounties, on the other hand, have too much variance, arbitrariness, and general risk for someone such as myself who makes his living off of it.

Well, myself I envisioned the CoinJoin fund as, well, a fund to be best used towards a goal. Put another way I always saw it more like donating to the Bitcoin Foundation, who in turn would vet proposals by others and allocate funds; this doesn't have to be a bounty in any way, and I think it was a mistake on gmaxwell's part to use that term.

[maaku]

What I'm offering to implement is a strict superset of what you propose. I think the added functionality is important, today. We have a difference of opinion on priorities, and we'll have to leave it at that.

[klee]

Why don't you co-operate? 

[Peter Todd]

Why don't you co-operate? 

If I have time to work on CoinJoin stuff I'm sure we'll end up doing just that - maaku and my approaches aren't as different as the above discussion may lead you to believe, just different priorities.

[maaku]

Some people have been asking about the status of this on IRC. As of yet, I haven't received a single donation, so it's a very low priority. The code is on Github, so anyone can work with it, although I'm already partway through an entire restructuring of the protocol. It might take a long while to finish however, as without funding this is basically a side project with very low priority.

[maaku]

Given the recent rise in price, 85btc is a bit excessive. I have lowered the crowd-fund goal to 55btc. If anyone is interested in donating but has questions/reservations, please don't hesitate to contact me in this thread or via PM.

[devthedev]

Pretty interesting, good luck with your funding and I hope to see any further progress on this project 

[btc_enigma]

maaku,

We are interested to partially fund and work on this project, I am sending you a pm

[maaku]

Updated post to reflect current funding targets in USD, not bitcoin since the price has drifted drastically since initial posting.

I'm working on an update to the message structures which should be posted soon, based on feedback from gmaxwell and other developers.