CoinJoin: Bitcoin privacy for the real world

[laurentmt]

Peter Todd has made an interesting statement in the comments of this coindesk's article.

What Dark Wallet actually implements is to have two classes of users, those who need a transaction done immediately, and those who are mixing coins. The latter group simply copies the output amounts of the former group, providing a set of two outputs in every CoinJoin transaction whose ownership is unknown. SharedCoin does the same thing, but with blockchain.info acting as that coin mixing group.

I may be wrong but it seems likely that bc.i uses a same pool of coins over and over for the sharedcoin txs. It's not impossible that, with some efforts, someone could identify which txos in the transaction graph are concerned (i.e. belong to bc.i), decreasing a bit more the level of privacy offered. To be effective and avoid this kind of privacy leak, coinjoin should use a large pool of mixing coins (the 2nd group of users in Peter's comment) and avoid reusing the same mixing coins over and over (with a frequency which allows to identify them).

Btw, it's likely that decentralized solutions like darkwallet are the easiest way to achieve this goal if they have enough traction and can maintain a large mixing pool.

[1715287460]

1715287460

[1715287460]

1715287460

[1715287460]

1715287460

[sile16]

There should be an open protocol that can help coordinate people who want to coinjoin.  Is there already something else out there that can automate that?

[Nite69]

I'm implementing distributed coinjoin to a couple of alt coins. I guess it can be applied to bitcoin also.

Shortly the algo:
Coinjoin offers are broadcasted as normal transactions, but on other channel, using message "ctx".
These offers are collected to a complete coinjoin transaction by first sorting the offers, then all participants sign it in turns based on sorting order and transmits them on the ctx channel. When the last finds it is complete, it transmits the complete transaction using normal tx message.

https://bitcointalk.org/index.php?topic=607919.7860

[maaku]

So it's trivially identifiable whose outputs are whose based on the observed offers?

[Nite69]

So it's trivially identifiable whose outputs are whose based on the observed offers?

I have been wondering that too.
Coinjoin itself protects transactions on blockchain only. However it requires someone to log all transactions 24 hours / day.

It is one improvement which should be done some day. The offers should be encrypted, so only the participants can decrypt all inputs. Then it would reveal only one address, and that might be generated to be used only once, maybe with 0 output. Other possibility would be to share the offers throught encrypted channel.

Any other ideas to improve it?

[maaku]

Read the first page of this thread. There's a solution involving blinded outputs.

[ShakyhandsBTCer]

Peter Todd has made an interesting statement in the comments of this coindesk's article.

What Dark Wallet actually implements is to have two classes of users, those who need a transaction done immediately, and those who are mixing coins. The latter group simply copies the output amounts of the former group, providing a set of two outputs in every CoinJoin transaction whose ownership is unknown. SharedCoin does the same thing, but with blockchain.info acting as that coin mixing group.

I may be wrong but it seems likely that bc.i uses a same pool of coins over and over for the sharedcoin txs. It's not impossible that, with some efforts, someone could identify which txos in the transaction graph are concerned (i.e. belong to bc.i), decreasing a bit more the level of privacy offered. To be effective and avoid this kind of privacy leak, coinjoin should use a large pool of mixing coins (the 2nd group of users in Peter's comment) and avoid reusing the same mixing coins over and over (with a frequency which allows to identify them).

Btw, it's likely that decentralized solutions like darkwallet are the easiest way to achieve this goal if they have enough traction and can maintain a large mixing pool.

The more times your output is the same address the easier it would become to trace your coins.

[mitchellmint]

I havent read the whole thread so this might not be a new idea but... it was something I accidentally discovered sending coins to a different coin with the same digit.

This concept is not promised to be implemented by VVV but was kicked around.

https://docs.google.com/a/mitchellmint.com/presentation/d/1X0QHjzkVtGJf5sf1vtiIjGQ_AvPg2GdPSYrc5vb9NIo/edit#slide=id.g35a51815e_040

[AdNarim]

I have an idea about a way to perform a decentralized Coinjoin so that individual participants are unable to map inputs to outputs - without the need for an anonymity network or blinded signatures.

As a disclaimer, although I have experience programming I am not well-practiced in cryptography, so forgive me if I make any egregious mistakes and waste everyone’s time.

Given the IP addresses and public keys for all N Coinjoin participant nodes, I envision the following onion routing protocol (inspired by what is used in Tor):

1.   Decide upon a random path which visits every node once and ends up back at our node.

2.   Using Onion Routing, send a multi-level encrypted message along this path. Each node by using its private key to decrypt the message will be able to see where the message was supposed to originate from, the bitcoin addresses to be used as inputs, and where to send the message to next. The rest of the message will only be able to be further decrypted by the next destination. When the message gets back to us, it should have visited every node in the path.
See: http://en.wikipedia.org/wiki/Onion_routing

3.   Same protocol, but with output addresses (can be done in parallel with the input addresses).

4.   Same protocol, but with our signature of the completed transaction.

5.   Broadcast transaction.


In theory, each node will be unable to tell from what node the input and output addresses originated. However, I see several serious issues with this proposal, and would welcome even more critique:

• Timing Attacks: If a node receives the message early in the process, it is more likely that that the sender owns the associated addresses. This may be mitigated through random delays or other, more clever schemes.
  
• Message Size: A node may be able to analyze the size of the message to determine how far along it is. To counter this, a randomly-sized allotment of junk data should be included in the inner-most message.
  
• Slow: this protocol takes N time, as the message must be forwarded to each node.
  
• DDOS: What is to stop some other node from screwing everyone over? It is possible to see if our message was tampered with (using random numbers, accumulating counters, etc.), but it would still be difficult to make the protocol resistant to malicious nodes mucking everything up and wasting everyone’s time.
  
• Sybil Attacks: You’re pretty much screwed. Tor has similar issues, this is one thing you really can’t do anything about (other than favoring IP addresses that are likely to be in physically separate locations)
  
• Other stuff: It’s probably out there, I just can't think of it at the moment.
  

Well, what about the positives? Assuming all the negative obstacles are surmountable:

• Inputs are not linked to IP addresses.
  
• Outputs are not linked to IP addresses.
  
• Inputs are not linked to outputs any more than can be determined from looking at the finalized transaction.
  
• No anonymity network required. This is important as P2P over, say, Tor is a pain.
  
• No reconnecting required. You are not required to meet up with the same nodes again.
  
• If you are behind a NAT router or firewall blocking inbound connections, you can hire an open node as a proxy. As only you have access to your private key, you can have this node forward/receive your messages without worrying about it snooping (granted, it can still cause as much trouble as the other nodes, and you probably have to compensate the proxy owner by including a small transfer in your transaction).
  

[dillpicklechips]

Would using ring signatures work as a method of mixing without having to trust a server even though they are using one? Provably fair mixing?

Have the clients connect and have all the inputs define the initial state of the cryptonote type ring signatures. Each person then shuffles the ring and they are only able to follow their own coins. They then specify the outputs in the ring whatever they are. Once everyone is happy they are getting paid they all sign. No one, not even server would be able to follow who is getting what. And even if the person had one input they could have multiple outputs depending on what they specify in the ring.

Kind of like my idea here: https://bitcointalk.org/index.php?topic=706000.0

[gmaxwell]

Would using ring signatures work as a method of mixing without having to trust a server even though they are using one? Provably fair mixing?

Please see the fifth post in the thread.

[AdNarim]

I am currently working on a Java library which facilitates decentralized CoinJoin-ing using a BitcoinJ backend.

As of this moment the library only works with fixed CoinJoin participants, I have yet to implement participant discovery (that's next on the list).
It also is very insecure at the moment, as I hacked together some sections in order to test general principles. It will be some time before the code is solid enough to not be embarrassing :\

Current plan:
1. Implement peer discovery (perhaps using a DHT)
2. Fix error handling and enhance verification of transaction components
3. simplify, refactor, rename
4. post source code (under a permissive OSS license)
5. Make CoinJoin process more anonymous.
6. ALPHA release?

example:
http://tbtc.blockr.io/tx/info/c4d86d7a054e5979172b223a15d5d9594f703d6376ab294ee4b2da45ff77b0eb

This is a test CoinJoin transaction between only 2 users. In this example I set the change and output address to be the same. The general caveats of a CoinJoin transaction still apply: each change address is clearly linked with an output address, and therefore by using blockchain analysis it may still be possible to link addresses. True anonymity requires minimal address reuse and tools for managing taint.

For now, though, I just send an unconfirmed transaction to a new address of fixed size, then use that unconfirmed transaction as part of the CoinJoin. Needless to say, for this scheme 0 confirmation coinjoins should not be accepted! Regardless, I am trying to write the library to be adaptable as possible to different types of CoinJoins, including coinjoins where each user has multiple inputs, casual coinjoins, and coinjoins without any change address.

[AdNarim]

Currently peer discovery is implemented with a centralized server. The server waits for N users to connect, then sends a message containing the IP Address and port of all participants. This approach is vulnerable to denial of service and is a single point of failure, but on the up-side any compliant server can be used. I still believe distributed peer discovery is ideal, but that can always be added later.

The centralized method is also NAT-friendly if Tor is used. Here is an idea for anonymous peer discovery and communication:

1. Each participant starts a Tor Hidden Service.
2. Using Tor, each participant connects to a peer discovery server, which is itself a Hidden Service. It announces the ID of its Hidden Service and open port.
3. The server then sends each participant a list of the Hidden Services. The participants then connect to these Servers and proceed with the decentralized CoinJoin process.

+ No traffic ever leaves the Tor network
+ No port forwarding / NAT traversal is required (in this sense it is more user-friendly than a non-anonymous

It should be noted that in order to prevent inputs and outputs from being linked by participants more complicated measures such as the blind signatures discussed on the first page must be used.

P.S.
Here is an example of a 10-way CoinJoin I generated using my library:
http://tbtc.blockr.io/tx/info/894d10fea8e017789e80e2965d3421572e42e19ba8c6f51ce4a22b3c40b0f831

This is similar to what a CoinJoin transaction would look like in practice, except a more secure implementation would mix the outputs around better.

[BTCfan668]

How safe is doing this bitcoin transaction?

This is very safe, however it is not very private. It is essentially not possible to "lose" your coins doing this, however it has been proven that these types of transactions can be traced by inspecting the blockchain.

[gmaxwell]

This is very safe, however it is not very private. It is essentially not possible to "lose" your coins doing this, however it has been proven that these types of transactions can be traced by inspecting the blockchain.

Don't confuse blockchain.info's completely broken "Shared Send"— they provide no privacy at all for reasons unrelated with this thread. The privacy implications of well constructed CoinJoins are discussed in some depth in the initial post and some other posts in this thread.

[belcher]

I have coded a simple implementation of CoinJoin.
https://bitcointalk.org/index.php?topic=730321.msg8254585

It makes no assumptions about how peers communicate but instead provides ascii-armored raw transactions similar to the PGP format which can be shared on any text-based protocol such as a Tor hidden service forums, Bitmessage chans, I2P eepsites, Freenet pages or something like that.

[molecular]

I am currently working on a Java library which facilitates decentralized CoinJoin-ing using a BitcoinJ backend.

I applaud!

Current plan:
1. Implement peer discovery (perhaps using a DHT)
2. Fix error handling and enhance verification of transaction components
3. simplify, refactor, rename
4. post source code?
5. Make CoinJoin process more anonymous.
6. ALPHA release?

I think it would be good if you removed the "?" from number 4, no?

I don't have much time currently, but let me know if you need testers.

[themgp]

Currently peer discovery is implemented with a centralized server. The server waits for N users to connect, then sends a message containing the IP Address and port of all participants. This approach is vulnerable to denial of service and is a single point of failure, but on the up-side any compliant server can be used. I still believe distributed peer discovery is ideal, but that can always be added later.

The centralized method is also NAT-friendly if Tor is used. Here is an idea for anonymous peer discovery and communication:

1. Each participant starts a Tor Hidden Service.
2. Using Tor, each participant connects to a peer discovery server, which is itself a Hidden Service. It announces the ID of its Hidden Service and open port.
3. The server then sends each participant a list of the Hidden Services. The participants then connect to these Servers and proceed with the decentralized CoinJoin process.

+ No traffic ever leaves the Tor network
+ No port forwarding / NAT traversal is required (in this sense it is more user-friendly than a non-anonymous

It should be noted that in order to prevent inputs and outputs from being linked by participants more complicated measures such as the blind signatures discussed on the first page must be used.

P.S.
Here is an example of a 10-way CoinJoin I generated using my library:
http://tbtc.blockr.io/tx/info/894d10fea8e017789e80e2965d3421572e42e19ba8c6f51ce4a22b3c40b0f831

This is similar to what a CoinJoin transaction would look like in practice, except a more secure implementation would mix the outputs around better.

If you are writing a Java library and are planning on using a DHT, have a look at TomP2P.  Its what i used in http://coinmux.com.

[Wafel16]

This is amazing, i will definitly keep an eye on this.

[MarisaFea]

So let me try and figure this out this is a little out of my league but here it goes:

Effectively you are creating a mixing service within the Bitcoin network itself? Making privacy better because no one can track where you sent your Bitcoin because it is split up and combined with other peoples transactions. Surely this has already been done by several mixing services?

Wouldn't this create more legal problems for Bitcoin? If this is what you want to achieve surely it's illegal because this can be abused very easily.