CoinJoin: Bitcoin privacy for the real world

[Rassah]

Watching, and hopefully participating.

[1714940100]

1714940100

[1714940100]

1714940100

[1714940100]

1714940100

[1714940100]

1714940100

[markm]

lol just received this email about our coinjoin server. we are running nothing except tor and our own software (checked processes).

Tor gateway or merely the normal default Tor node mode (internal node that does not go out getting files of the lightnet for someone else somewhere out on the Tor/dark net?

-MarkM-

[cr1776]

One thing to be aware of is the potential lack of security even using Tor right now, so one should be using Tor 2.4 or later even though it is alpha. See below.  Once CoinJoin is live, one should be aware of Tor versions for best practices in privacy.

http://arstechnica.com/security/2013/09/majority-of-tor-crypto-keys-could-be-broken-by-nsa-researcher-says/

[jgarzik]

One thing to be aware of is the potential lack of security even using Tor right now, so one should be using Tor 2.4 or later even though it is alpha. See below.  Once CoinJoin is live, one should be aware of Tor versions for best practices in privacy.

http://arstechnica.com/security/2013/09/majority-of-tor-crypto-keys-could-be-broken-by-nsa-researcher-says/

And

https://twitter.com/jgarzik/status/376210228863172609
https://twitter.com/jgarzik/status/376210514562404352

[cr1776]

Very true.  Unfortunately Tor (et al) are not yet to the point that many would like.  :-)

One thing to be aware of is the potential lack of security even using Tor right now, so one should be using Tor 2.4 or later even though it is alpha. See below.  Once CoinJoin is live, one should be aware of Tor versions for best practices in privacy.

http://arstechnica.com/security/2013/09/majority-of-tor-crypto-keys-could-be-broken-by-nsa-researcher-says/

And

https://twitter.com/jgarzik/status/376210228863172609
https://twitter.com/jgarzik/status/376210514562404352

[Natanael]

There's actually an efficient MPC protocol now that appears to be as secure as my scheme requires! (Which I personally use to call SMPC = *secure* multiparty computation)

http://phys.org/news/2013-09-breakthrough-cryptography-result.html - also links to it's paper

Hopefully it will be released as open source as well.

[ghgr]

I propose a specification of the CoinJoin protocol. It is not yet implemented, but if you find the work-flow sound it would not be hard to make an IRC bot with the sx command line utilities as a proof-of-concept.

The idea is a P2P network where a thread is relaying all transactions. Another thread is in charge of the mixing.

A first, simple implementation would be an IRC bot which sends and listens to encoded transactions. Of course this approach would not be P2P, but a public channel in a hidden IRC server provides several advantages:

   -Easy implementation: IRC servers already exist. Bots enter to the channel #coinjoin (for example) and speak there.
   -Soft trust system:
      - If we trust the IRC server (for large values of 'trust') and only registered nicks are allowed to talk in the channel, a Sybil attack will be difficult.
      - We can chat (privately or publicly) with some users and thus allow them to prove their identity (by signing a given message, telling you a private joke, etc.)

The concept is composed by two parts (threads):

   1) Communications thread: In the case of the IRC server architecture, it has the method "sendTransaction" and "listenToTransaction". The first one "chats" in the channel and the latter listens to transactions and stores them in memory.

   2) The actual mixing part: Its work-flow is showed in the link [1]. It has been designed with yEd (http://www.yworks.com/en/products_yed_download.html) and the file (if you want to edit it) is [2] . The main points are:

      - It handles "change" addresses. If you want to mix 47 BTC, it will be a pain (really!) to make 47 inputs of 1 BTC and mix the separately. This approach allows you to send the 47 BTC as input, recover 1 BTC (for example) mixed and your 46 BTC back (of course, not mixed! In order to avoid confusion, this change address is the same as the input address). Fees are deduced from the change address, and thus you can serialize this method trivially as many times as you want.

      - Random decisions to avoid an attacker that listens how the transaction is constructed to map inputs with outputs. Each time transactions are composed in a different order.

      - If something goes wrong (bad signature, peer not responding, etc.) the output is discarded and the process restarted.


Q: What means checkTransaction?

A:
1) Are inputs confirmed (at least 1 confirmation)? OR, Are all unconfirmed previous transactions valid (for the Bitcoin network) and with enough fee?
AND
2) Signatures match?
AND
3) Is there enough transaction fee?
AND
4) Are all outputs equal AND sum(outputs) < sum(inputs)?


[1] http://i41.tinypic.com/5p3k02.jpg

[2] http://www18.zippyshare.com/v/26446175/file.html

[gmaxwell]

In order to avoid confusion, this change address is the same as the input address).

This is a terrible idea. You have to specify the input you want to spend, just specify the address you want change to be assigned to too.

[ghgr]

In order to avoid confusion, this change address is the same as the input address).

This is a terrible idea.

No it is not. Take a look at the flowchart. The way the transaction is constructed does not leak information about which input goes with which output.

For example (fees excluded for clarity)

Inputs:
1) 50 BTC from 1addr1
2) 100 BTC from 1addr2

Outputs:
1) 1 BTC to 1addrX
2) 1 BTC to 1addrY
3) 49 BTC to 1addr1
4) 99 BTC to 1addr2


The change is sent to the same address in order to avoid confuse the user (it was 1addr1 the mixed, or was it 1addrY?).

Anyway, if you *really* want to specify a different one, it is trivial to do that.

[maaku]

Don't reuse the input address. Don't ever reuse addresses, particularly in protocol.

[ghgr]

Don't reuse the input address. Don't ever reuse addresses, particularly in protocol.

I agree that it might not be ideal, but it does not compromise the anonymization. It is not intended to be pretty, but useful, and to decrease the chance of the user making mistakes.

[gmaxwell]

I agree that it might not be ideal, but it does not compromise the anonymization. It is not intended to be pretty, but useful, and to decrease the chance of the user making mistakes.

If you obtain an explicit change address from the user there won't be any confusion or mistakes. And it does reduce privacy— otherwise a third party is still unsure about the ownership of the change, if less unsure than they are about the other outputs.

Are you planning on writing software that does this? if not, the debate is kind of moot.

[ghgr]

I will answer the two questions:

1) Why is there a change address?
Because more often than not the user has more coins than the standard amount to mix (for example, 1 BTC).

2) Why is the same as the input address?
Because it makes clear that these funds are NOT mixed. Not only slightly mixed (in my previous example, the output with 49 BTC is obvious where it came from). There is no such thing as "little unsure". Funds are completely anonymous*, or they are identifiable. And I chose to make it clear in the protocol.

I would like feedback in the protocol itself. For example, how can a transaction be re-identified, or under which circumstances the program may be stuck. If you still believe that reusing the change address would compromise anonymity, please give a concrete example of how.

If it is OK, developing the program is quite straightforward. All the tools exist already (it can be even a bash script with the sx tools).


*Under certain assumptions, like for example excluding the other party (this is why the process is repeated several times)

[maaku]

The client knows from the history which outputs were added as part of the mix, and which were the result of explicit change addresses. This information needs to be tracked anyway because joined coins are not completely anonymous. At best each join adds only a few bits of entropy, and any competent implementation would have to track how much entropy is added with each mix, and therefore would be perfectly capable of setting entropy=0 for change outputs.

EDIT: BTW, in case anyone hasn't seen it, I'm running a crowdfund to finish the chaum blinded signature version of the protocol that I've started working on.

[Cryddit]

Here is something that would help.

Standardize some coin denominations, call 'minted coin'.  Random other denominations call 'bullion', for 'bulk metal.' 

Let a standard minted coin be anything that starts with 1, 25, or 5, and the rest of whose digits are zero. 

phase 1.  Merchants start splitting input into minted coin into own wallets, giving back minted coin as change.   Trigger phase 2 when 90% transactions last 100 blocks done exclusively with minted coin input & output. 

phase 2.  Now make 'normal' transaction be transaction exclusively in minted coin.  Other transactions still legal, just not 'normal' anymore (or maybe not 'normal' unless accompanied by bigger tx fee for miner). 

phase 3.  Clients concerned with privacy may start participate exclusively in tx have exactly same number, denomination, for input & output, and at least 2 inputs largest size coin used.  Other clients, not care, may allow tx where take maybe some number coin at same address , but if so let make another standard size coin. 

Easy for someone to figure out what's going on when there's an input that's 3.88 BTC, an output that's 3 BTC, and an output that's .88 BTC. 

Much less easy when there are 3 inputs of 1 BTC, 3 inputs of .25 BTC, 2 inputs of .05 BTC, and 3 inputs of 0.1 BTC, and output is exactly the same number and size of coins.  No way to know which is change going back to buyer.  No way to know which inputs & outputs represent buyer, which seller.  Maybe seller has inputs too, and is making change  Not even a way to know if the thing somebody bought cost 0.5 BTC or 3 BTC or 3.5 BTC, etc. Every address used have one coin, every address paid to have one coin. 

Trades in 'bullion' (arbitrary N-digit denominations) still possible, maybe not 'standard', or may require small 'minting fee'.  But also possible exchange 'bullion' for 'minted coin'  of standard denominations, down to level of negligible dust award for miners.   Not even possible when watching to tell difference between someone changing own 'bullion' for goods with merchant take 'minted coin' and getting 'minted coin' change, from someone just changing own bullion for minted coin.

Makes 'coinjoin' privacy by default.  Money go through a few ordinary trades under new rules, specially trades with or by privacy enforcing clients, no longer possible tell who own which. Is soft fork only; all tx legal under new rules also legal under old.  Takes no 'mixing' as such or 'mixers.'  Requires trust no extra party.  Implementation simple and easy make secure.

Edward.

[Hawkix]

I would prefer mixing arbitrary values of BTC. Ideally, the adversary should not be able to distinguish on-purpose mixing transaction from normal multiple input/multiple output transactions.

That's why I would like to do the mixing kind of automatically, from the queue of transactions to be mined.

If there are signed transactions A1+A2->X1+X2 from one user, B1->Y1+Y2 from other, etc., there should be a mechanism how to "RESIGN" mixing large transaction A1+B1+A2 -> X2+Y1+X1+Y2. If both A and B sign this and add a slighly better fee, it will be mined. It may look like double spend, but this could be solved using special "propose transaction" message instead of "broadcast transaction".

Thus, the Bitcoin transfers of users, who do not know each other, will be, kinda automatically (think of "offer for mixing" checkbox in Bitcoin-QT) mixed together by the network prior to be mined. Could save some blockchain space, too.

[ghgr]

That's a neat idea (mixing large transactions) but unfortunately I cannot see how it could be implemented. When signing an input we sign a hash of the outputs, and thus adding new outputs will require to re-sign the transaction (as you already stated).

So, the transaction must go back and fort (in order to resign it each time an output is added) and the miner becomes essentially the rendez-vous server.

[gmaxwell]

That's a neat idea (mixing large transactions) but unfortunately I cannot see how it could be implemented. When signing an input we sign a hash of the outputs, and thus adding new outputs will require to re-sign the transaction (as you already stated).
So, the transaction must go back and fort (in order to resign it each time an output is added) and the miner becomes essentially the rendez-vous server.

That isn't the case, and if you see the "taint rich" link in the post, you can see I went and performed these transactions with people with no back and forth, there is a single round trip:  I offer inputs and outputs, you respond with inputs and outputs and your signature, I then add my signature. If you'd like we can do one together too.

My main motivation in creating that long writeup was correcting that misconception.  For SIGHASH_ALL these can be accomplished by simply agreeing on the outputs before any signing begins. (Obviously things are even simpler with SIGHASH_SINGLE, but that doesn't have the desirable privacy properties).

Standardize some coin denominations, call 'minted coin'.

I tried pretty hard a couple years ago to get pools to round up their payments to non-jagged numbers like 0.01, because the highly jagged outputs they produce are bad for privacy and produce more bloaty change... and had absolutely zero luck. I am not anticipating great success on any kind of denominationalizing bitcoin. Maybe if the block explorers that give the misleading "account" view go away and people use more clients that show a more accurate "coin" view people will start to care more about the denomination of the coins they receive.

[jgarzik]

I tried pretty hard a couple years ago to get pools to round up their payments to non-jagged numbers like 0.01, because the highly jagged outputs they produce are bad for privacy and produce more bloaty change... and had absolutely zero luck.

Interesting.  I had not thought about the privacy implications of the jagged numbers, just the bloaty change part.

[ghgr]

Thanks for your answer, gmaxwell.

So, if I understand correctly, what you propose in your "I taint rich" thread is:

- You say publicly that someone make a transaction with this schema (first transmission):

inputs:
 a) His address (spendable previous output with X BTC)
 b) Your address (spendable previous output with 1 BTC)

outputs:
 a) A different address of him (X BTC)
 b) You address (with 1 BTC)

- This transaction is signed and sent back to you (cited: "via PM, anonymous gpg encrypted email, or a post in this thread") (second transmission).

- You sign this transaction and announce it (third transmission)

Or, in other words, in order to agree on the outputs, we need to have a rdv server (either an IRC server, a Forum -as in your thread-, a P2P network, etc.). We cannot avoid playing ping-pong with the transactions (I have nothing against it. In fact I proposed a detailed specification some post above).

For SIGHASH_ALL these can be accomplished by simply agreeing on the outputs before any signing begins.

How can we agree on something without previous communication? What is the advantage over, for example, sending back and forth the transaction?