Automatic Coin Mixing Idea

[casascius]

I wanted to solicit some thoughts about the following way to mix coins.  This idea of mixing coins would be built right into the client, is very simple, and would result in everyone's coins being mixed periodically with zero risk of loss and without anybody actually have to feel like they were submitting their coins to a mixer.

Here is how it would work:

• On a random interval, each client will be Alice, and will ask one of its peers Bob if he would like to mix M number of coins with her.
• Upon receiving a "mix offer" message from Alice, Bob could either a) ignore it, b) accept it, or c) forward it to another randomly-chosen connected peer and serve as a relay.
• To accept the request, Bob would identify an unspent txid that belongs to him (or he could lie and offer one that doesn't belong to him, more about that later), and offer a fresh receiving address.
• When Alice gets Bob's acceptance, Alice will create a transaction with typically two inputs: some coins from Alice, and Bob's txid.  And there will be two (and possibly three or four) outputs in random order: M coins for Alice, and M coins for Bob.  If any change is left over, those would be the third (for Alice) and fourth (for Bob) outputs.  Alice signs the transaction, but it needs Bob's signature to be valid.
• Alice sends the transaction to Bob for approval.  If it looks fair to Bob, he signs it and broadcasts it.
• From the block chain, the M coins to Alice and Bob have been mixed.  One knows the coins belong to either Alice or Bob, but not which of the two.
• If everybody is periodically mixing coins like this, eventually it will be common to see six or ten or more "mixes" between real transactions.  Those "mixes" would make it so it's not just one of two, but one of 2^n different possible payers.
• I can think of other ideas that would dramatically improve the effectiveness further.  For example, if M were limited to specific numbers (e.g. 5^n where n is an integer, so M typically can be one of only 0.0016BTC, 0.04BTC, 0.2 BTC, 1BTC, 5BTC, 25BTC, 125BTC, 625BTC) then fewer mixing operations would involve change outputs that would detract from mixing effectiveness, as it would be far more likely that nodes are looking to mix txid's in identical amounts.  And Alice could talk to multiple Bobs at the same time and construct a transaction that mixes M coins for several parties, not just two.
• The possibility of forwarding requests, ignoring requests, and returning false txids, are all ways to prevent Alice from connecting to Bob and being able to ask him, "hey Bob, got coins? and if so, which ones?"  The forwarding allows for plausible deniability on the response (Bob can say "those weren't my coins, they belong to one of my peers, or were a lie").  (In the event Bob lies and returns a txid not his own, he won't be able to sign and complete the transaction, which would be indistinguishable from Bob simply deciding not to complete the transaction on his own.  For example, Bob may not have any coins, or might not have any peers who respond to the forwarded request.  Bob's ability to lie enhances his ability to claim the coins he offered to mix weren't his.)

Bottom line is, if coin mixing were built into the client, there would never be a need for anyone to use a coin mixing service, and thereby deliberately and identifiably participate in so-called "money laundering".  Rather, they would be exchanging coins in the normal course of business, the same way I can go to the grocery store with a twenty and ask for two tens without being guilty of "laundering" the twenty.

This process would also help greatly toward network scalability.  If coupled with a scheme where small penny txids (such as those generated by p2pool) were consolidated into amounts large enough to be valid for mixing, this also would defragment them without forcing whoever owns those outputs to deanonymize themselves... this would dramatically reduce the storage burden on near-future clients who will only be tracking unspent transactions instead of the whole block chain.

[unclemantis]

+1

Good luck!

[austonst]

I like the idea. I could imagine a client with an "Automatically mix coins" advanced option in a menu, along with a quick dialog box about the anonymity benefits, but constant transaction fees. The developer would probably want some sort of limit to prevent ignored wallets from running themselves dry from transaction fees over a long period of time (Maybe something like "I'd like to spend 10 bitcents of transaction fees on mixing, then stop", although this could definitely be worked out later).

The ability to combine a bunch of tiny bits of coins together without completely opening them up to tracking ownership sometime in the future is the best part of this. It'll help scalability and people who prefer to keep their coins consolidated at a few addresses without sacrificing anonymity.

[evoorhees]

I like the idea. I could imagine a client with an "Automatically mix coins" advanced option in a menu, along with a quick dialog box about the anonymity benefits

+1  I love the idea OP, but it should probably not be a mandatory function of the Satoshi client. Better as an option built into many clients.

The reason it shouldn't be a mandatory part of the Satoshi client is that that client should strive to avoid feature-creep. There is value in simplicity, especially for the core client. But if this option became standard in the Advanced tab of all clients, I'd be a happy man

[unclemantis]

It would be nice to have FRESH COINS to send to my cold storage savings!

[casascius]

I like the idea. I could imagine a client with an "Automatically mix coins" advanced option in a menu, along with a quick dialog box about the anonymity benefits, but constant transaction fees.

Transaction fees will be completely avoidable if the client strictly selects txids that can be spent without incurring any fees.  In fact, the logic for selecting txids to mix should completely exclude unconfirmed transactions as well as transactions that aren't old enough to be spent without a fee.

[casascius]

+1  I love the idea OP, but it should probably not be a mandatory function of the Satoshi client. Better as an option built into many clients.

The reason it shouldn't be a mandatory part of the Satoshi client is that that client should strive to avoid feature-creep. There is value in simplicity, especially for the core client. But if this option became standard in the Advanced tab of all clients, I'd be a happy man

My take is that it should be part of the Satoshi client, but turned off by default.  I think that's what you are suggesting, right?

I would agree it should be off by default for several other reasons including: it leaks information to the public that some might consider private (such as the fact that their node and wallet is online and alive), and it also results in confirmed funds suddenly becoming unconfirmed and then reconfirmed at random intervals (though not at a risk of loss to the wallet holder).

None of these things should occur to users who don't understand them or explicitly opt in to them.  They could be briefly explained as benign side effects to a user who checks a checkbox to enhance his anonymity.

[Nyhm]

This type of protocol discussion is why I'm enthralled with Bitcoin in general. I was actually contemplating something similar, but you're solution is much more integrated and concrete. I'm into distributed protocols, but I admit I haven't delved into the core messages of Bitcoin yet.

Am I correct that the tx created by Alice (including Bob's input tx) is a direct application of the multi-signature transaction BIP?

[casascius]

Am I correct that the tx created by Alice (including Bob's input tx) is a direct application of the multi-signature transaction BIP?

No, it is just a normal transaction that combines two inputs, and looks much the same as a transaction that combines two of your smaller coins in your wallet to make a bigger coin when one is needed.  It is not a multisig transaction at all.

The only difference between this and any other transaction is that the two inputs happen to belong to two different people, rather than the same person, so the signatures have to happen in separate steps.  In contrast, all coin-combining transactions already require multiple signatures, we just don't usually think of it that way because the same person's Bitcoin client (the sender's) can provide all of the needed signatures itself, and automatically does so whenever you "send coins" out of your wallet in an amount that makes coin-combining necessary.

[rjk]

Wasn't there some altcoin that already had a built in laundry?

[aq]

One of the biggest issues is that once you make a transfer you combine coins from multiple addresses and as a result those can be identified as one wallet. I think casascius proposal addresses this only to some extent. If after mixing coins I again have to combine I have gained nothing.
How about we do it different:
Whenever I want to make a transaction, my client sends this out as a "transaction-indent", other clients that are also about to do a transaction combine their "indent" with mine (adding inputs and outputs) and after a few seconds, we all sign this combined indent to form a transaction.
This would make it impossible to identify a single wallet, because inputs from multiple wallets would end up in a single transaction. And secondary, on one would know which input was the initiator for which output.
Your comments?

[austonst]

One of the biggest issues is that once you make a transfer you combine coins from multiple addresses and as a result those can be identified as one wallet. I think casascius proposal addresses this only to some extent. If after mixing coins I again have to combine I have gained nothing.
How about we do it different:
Whenever I want to make a transaction, my client sends this out as a "transaction-indent", other clients that are also about to do a transaction combine their "indent" with mine (adding inputs and outputs) and after a few seconds, we all sign this combined indent to form a transaction.
This would make it impossible to identify a single wallet, because inputs from multiple wallets would end up in a single transaction. And secondary, on one would know which input was the initiator for which output.
Your comments?

The reason this coin mixing strategy reveals that addresses belong to the same wallet is because of addition. Let's say you see a tx with inputs of value 2, 3, 9. The outputs are of value 5, 5, and 4. It's pretty easy to tell, knowing that this is a mixing tx, that the 2 and 3 came from the same source. We also know that the output of 4 belongs to the owner of the input of 9. What we've gained is not knowing who owns each 5 output.

With your proposed solution of just having two transactions per transaction, we still have the same problem. Let's say Alice is paying 5 BTC using inputs of size 2 and 3. Bob has another transaction where he pays 13 BTC with two inputs of 7.

Inputs: 2 3 7 7
Outputs: 5 1 13

It's still pretty easy to distinguish between the transactions. Clearly, one person owns the 2 and 3 input addresses, and someone else owns the 7 addresses. We can still tell that addresses are related. With both ideas, the only way to avoid this is to have multiple ways to combine input values to reach the output values (which is difficult when bitcoins are divisible down to 8 decimal places).

Inputs: 1 4 4 2
Outputs: 5 6

Now there's two possible solutions. 1 4 4 2 or 1 4 4 2. Casascius' idea of limiting mixing sizes to 5^n would help ensure that after the first mixing, each output should be of a fixed size. That should help reduce these concerns.

Getting back to the original issue: yes, using this mixing to combine coins would still often show that some of the source addresses are held by the same person. The strength is that that knowledge cannot be used to track future transactions. You become detached from your past, breaking any string of transactions people might be using to track you. Now, if you have 0.3 and 0.7 unspent tx's, and you happen to come across someone else with exactly 0.3 and 0.7, you can make it uncertain that you own both addresses.

[aq]

One of the biggest issues is that once you make a transfer you combine coins from multiple addresses and as a result those can be identified as one wallet. I think casascius proposal addresses this only to some extent. If after mixing coins I again have to combine I have gained nothing.
How about we do it different:
Whenever I want to make a transaction, my client sends this out as a "transaction-indent", other clients that are also about to do a transaction combine their "indent" with mine (adding inputs and outputs) and after a few seconds, we all sign this combined indent to form a transaction.
This would make it impossible to identify a single wallet, because inputs from multiple wallets would end up in a single transaction. And secondary, on one would know which input was the initiator for which output.
Your comments?

The reason this coin mixing strategy reveals that addresses belong to the same wallet is because of addition. Let's say you see a tx with inputs of value 2, 3, 1, and 5. The outputs are of value 5, 5, and 1. It's pretty easy to tell, knowing that this is a mixing tx, that the 2 and 3 came from the same source and that the 1 and 5 came from the same source. We also know that the output of 1 belongs to the owner of the previous 1 and 5 tx's. What we've gained is not knowing who owns each 5 output.

With your proposed solution of just having two transactions per transaction, we still have the same problem. Let's say Alice is paying 3 BTC using inputs of size 2 and 2. Bob has another transaction where he pays 10 BTC with a 3 and a 7.

Inputs: 2 2 3 7
Outputs: 3 1 10

It's still pretty easy to distinguish between the transactions. Clearly, one person owns the 2 and 2 input addresses, and someone else owns the 3 and 7 addresses. We can still tell that addresses are related. With both ideas, the only way to avoid this is to have equally sized inputs (which is difficult when bitcoins are divisible down to 8 decimal places).

Inputs: 1 4 4 2
Outputs: 5 6

Now there's two possible solutions. 1 4 4 2 or 1 4 4 2. Casascius' idea of limiting mixing sizes to 5^n would help ensure that after the first mixing, each output should be of a fixed size. That should help reduce these concerns.

Getting back to the original issue: yes, using this mixing to combine coins would still often show that some of the source addresses are held by the same person. The strength is that that knowledge cannot be used to track future transactions. You become detached from your past, breaking any string of transactions people might be using to track you. Now, if you have 0.3 and 0.7 unspent tx's, and you happen to come across someone else with exactly 0.3 and 0.7, you can make it uncertain that you own both addresses.

Well, my proposal wasn't to mix 2 transactions, but maybe 10, or even 50. And then once you add the change addresses (at least 1 per wallet), it is no longer so easy to figure out what was used for what, and what belongs to what.

[austonst]

Well, my proposal wasn't to mix 2 transactions, but maybe 10, or even 50. And then once you add the change addresses (at least 1 per wallet), it is no longer so easy to figure out what was used for what, and what belongs to what.

Couldn't you say the same thing about this mixing? It could be expanded pretty easily to have Alice's mix offer be "Hey, I'm running a 5 BTC mixing party. Let's get everyone in on this same transaction." If a lot of people are throwing in their 2's and 3's, it'll get difficult to find the original pairs.

[Nyhm]

Am I correct that the tx created by Alice (including Bob's input tx) is a direct application of the multi-signature transaction BIP?

No, it is just a normal transaction that combines two inputs, and looks much the same as a transaction that combines two of your smaller coins in your wallet to make a bigger coin when one is needed.  It is not a multisig transaction at all.

The only difference between this and any other transaction is that the two inputs happen to belong to two different people, rather than the same person, so the signatures have to happen in separate steps.  In contrast, all coin-combining transactions already require multiple signatures, we just don't usually think of it that way because the same person's Bitcoin client (the sender's) can provide all of the needed signatures itself, and automatically does so whenever you "send coins" out of your wallet in an amount that makes coin-combining necessary.

I see. Thanks for that clarification. Is it true, then, that a tx message is entirely invalid if all the input sigs are not included/valid? That is, when Alice creates & signs the tx (including Bob's input), but Bob never signs it, then it would never survive on the network (supposing Bob decided to transmit).

Forgive me if this is obvious to the experts here. I have the technical background to understand and appreciate this stuff, but I'm still new to this protocol.

[aq]

Well, my proposal wasn't to mix 2 transactions, but maybe 10, or even 50. And then once you add the change addresses (at least 1 per wallet), it is no longer so easy to figure out what was used for what, and what belongs to what.

Couldn't you say the same thing about this mixing? It could be expanded pretty easily to have Alice's mix offer be "Hey, I'm running a 5 BTC mixing party. Let's get everyone in on this same transaction." If a lot of people are throwing in their 2's and 3's, it'll get difficult to find the original pairs.

Not really, because once I do my 100btc transaction, I have to combine all those in my own wallet. So mine are again identifiable as mine. The "bad" operation is to actual combine. So my idea was, make the combine operation more anonymously.

[casascius]

One of the biggest issues is that once you make a transfer you combine coins from multiple addresses and as a result those can be identified as one wallet.

Reducing the swaps to specific granular amounts helps prevent this by making the units as indistinct as possible.

If five people go to a party, and one person has a 3-dollar bill, another person has a 17-dollar bill, and the others have equally unusual amounts, then it is clear how this idea is going to be ineffective.  And these weird denominations of bills are exactly like how Bitcoin works internally.  But that is why sticking to some standard swap denominations is important (as I suggested with 1, 5, 25, etc.).

if before everyone gets to the party, they exchange their unusual denominations for one-dollar bills, and then exchange 1:1 all evening, someone who hands you 5 of them isn't going to reveal any information on the basis of which 5 one-dollar bills you got, other than that one person came to the party with at least five dollars.  For all intents and purposes they are equally anonymous.

If I am an anonymizing Bitcoin client and somebody sends me 73.26 BTC, the first thing I will do is split that into 25+25+5+5+5+5+1+1+1+.20+.04 and I will probably discard the remaining 0.02 as a transaction fee somewhere so long as it's not worth mixing.  Then, all of those chunks will be traded with others, one-for-one.  By the time each chunk has been traded six or seven times, what's a recipient going to learn to know that for example three chunks of five were combined to make fifteen?  Not much of use.

One could perform an analysis on those three chunks to see if they might happen to all share a common possible point of origin on the block chain (an intersection attack), which could identify the original origin.  But that could be easily mitigated just by the client occasionally "mixing" same-sized chunks with itself, which is indistinguishable from mixing with others, and which would make the ancestry of each chunk look very "inbred" so to speak, and therefore poorly useful for confidently identifying distinct faraway ancestors.

[aq]

One more point, while casascius method would extremely bloat the block chain, mine could actually reduce the size.

[casascius]

Well, my proposal wasn't to mix 2 transactions, but maybe 10, or even 50. And then once you add the change addresses (at least 1 per wallet), it is no longer so easy to figure out what was used for what, and what belongs to what.

The only problem is that the more participants in the group, the easier it is for one party to disrupt the operation OR spoil the anonymity by recording/publishing the input-to-output connections.  Everyone has to participate, and no matter how you slice it, either everyone in the group will know the mapping of addresses for everyone in the group, OR anyone in the group can easily disrupt the process for everyone by failing to play by the rules (e.g. refusing to sign, or spending their original funds while the signatures are being coordinated, thus voiding the whole transaction).

The right group size is small and casual.  The average Bitcoin node tries to connect to 8 other nodes, and if "some" of those nodes cooperate, you'll have a group size of 2 to 4 most of the time.

[casascius]

One more point, while casascius method would extremely bloat the block chain, mine could actually reduce the size.

My proposal would indeed bloat the block chain, and therefore a prerequisite would be appropriate transaction pruning - something already being discussed by the devs.  It would also require deterministic wallets in the main client, otherwise a wallet backup would expire very quickly as all of the addresses are used up for this purpose.  So for now, my proposal is totally premature for implementation - it just won't be for much longer.

Your "transaction-intent" proposal would work really well, other than that it would be very easy to disrupt.  The Achilles heel is that until ALL of the signatures are provided, the entire transaction is invalid.

If every Bitcoin transaction were made by soliciting an offer to combine it with somebody else's transaction and a protocol were devised to coordinate this, transaction processing on the entire Bitcoin network could be brought to a halt just by somebody writing a bot that pretends to cooperate for as long as possible, but refuses to actually sign any transactions... and then running a few dozen instances of that bot.

A few dozen instances of such a bot would make detection and exclusion of the bot impossible, because they would cooperate and sign transactions most of the time, but each one would take turns disrupting a whole distributed transaction, letting a different bot instance do the job of disrupting each separate attempt.  Sort of like colluding in online poker.