Topic: CoinJoin: Bitcoin privacy for the real world - page 38. (Read 294672 times)

Paying for anonymity isn't a good idea! It let look the coin like some commercial instrument (what we all dont want!). Maybe it is a good idea to pay with some stake or similar concept?

If it was locked to 2 participants, then you could use something like

flip a coin

If heads, send a broadcast with "I'll pay for ".
If tails, wait for a broadcast and then broadcast to 50% of peers "I'll pay into mix( )"

(Tails needs a timeout)

wait until you receive tx with all outputs broadcast from 1/3 of peers [ * ]

Wait 5 to 15 seconds at random from that point to broadcast tx with signed inputs that pay to the full set of outputs [ ** ]

One or other of the 2 participants can broadcast the full transaction to the network.

The fee would have to be agreed in advance.  Each participant would pay half the fee.

I still think standard coin sizes would help with the mixing.  However, the trick where you create a coin to mix with a person's change address is a good idea.

You could actually mix with both pieces.

I send 0.1BTC and 0.01BTC change.  The other person might buy something for 0.9 BTC with change of 0.1, 0.01 and .  They get their change mostly mixed and would still be paying a tx fee.

[ * ]
If you send the broadcast, then this is 1/3 of the nodes you didn't send it to.  This could be restricted to outbound nodes.
This syncs both participants to have the same start time.

We need a concept for a practical implementation of this in the main client. Then bounties and popcorn.

I edited that post down from a longer (4000 word?) version which included some specific examples that I had some personal involvement in: The (third?) ozcoin thief, who was identified by sending funds to a wallet service that reused addresses (and ultimately had those funds clawed back), and a person who had an insecure brain wallet found by a whitehat, ultimately tracked down and contacted due to a mining pool which reused addresses.

There are many other examples of privacy in Bitcoin being weak— one only needs to spend a few minutes browsing through bc.i's public block explorer interface to see real names attached to transactions (found by spidering webforums) and frequently accurate IP addresses (associated by connecting to many nodes), and from there you can find additional related addresses with the taint analysis button. Or look at the academic research "Bitcoin is not inherently anonymous. It may be possible to conduct transactions is such a way so as to obscure your identity, but, in many cases, users and their transactions can be identified." (papers on Bitcoin are of, ahem, highly variable quality— but the point remains, Bitcoin's privacy as it is today is not very good).

The privacy gap between Bitcoin and cash for most users is enormous, enough so that we have an explicit warning on Bitcoin.org:
Ignorance of these limitations makes the situation worse because without being acutely aware of the risk you will transact in ways that leaks more information about you and the parties you trade with.

My proposal can be 100% automated - the user doesn't even need to know it's happening behind the scenes.

It's also not really any different in spirit from what gmaxwell suggested in the first place - I've only fleshed out details with a particular way to do it.

This seems overly complicated. Is there any reason why Bitcoin isn't private enough as it is?

You presented a hypothetical situation which has not occurred yet.  It's not perfectly private but compared to credit cards and banks its very private. It's almost as private as cash.

I'll accept that, but the counter-proposals/additions to your initial proposal do nothing to keep the complexity for the user down. As an end user who is looking for ease of use and decent privacy, some of the other schemes here, unless done transparently, are just too much to keep up with.

I'm not sure what you're referring to, but in general I think a lot of people have not thought the fungibility implications through, and are also confusing privacy and anonymity because they are intimately related, especially where pseudoynmity is used to achieve privacy. Anonymity is fundamentally hard, and consider anonymity improvements a side effect of good privacy. If you want to go around telling someone which transactions are yours, you still can. And, an interesting point of that is that it's not at all incompatible with what is proposed here. Even if you're happy telling a particular set of people all about your transactions, that doesn't imply you also want the whole world to know.

I can probably contribute commits to this, debugging, testing, cross-platform building, etc.

If the goal is a simple way to regain anonymity, why are there counter-proposals to make regaining it more complex? Just curious.

Finally... atomic coin laundry. Nice. 

True.  People might be willing to throw it away.


True, and as you say, it isn't about perfection, it just increases the effort.

People appear to have been sending very large numbers of addresses dust as a way to break anonymity. Granted, they also may have been doing it as a way to get signatures from scriptPubKeys due to the 'R' re-use issue, but the script would use bitcoind to spend the dust which is known to not be vulnerable.

Also there's lots of pretty much unspendable dust out there from Satoshidice and others, and again such a script can help.


No, it's fees paid by previous transactions.

Now that does raise the question of where do those fees come from if you haven't made a transaction in awhile? One decent option is in fact to spend coin-age by signing to a txout that you don't actually intend to spend, however that's open to DoS attack by entities that simply have a lot of Bitcoins. Fidelity bonds are another option.

As an aside, the actual process of spending credit should include a field for the current balance of credit prior to that spend, and the hash of the previous time this credit was used to make double-spending credit not possible. This is particularly important with the coin-age or fidelity bond version, because there it's quite possible for nodes to securely give their peers the current status of the credit balance based on smallest balance left.


I'm actually thinking that mixes should have a small number of participants, usually two or three. Remember that we want the process of creating a tx to be as fast as possible, and multiple rounds of mixes wind up with just as much anonymity as fewer rounds with more participants in each round.

The economics of the DoS attack are such that the attacker wastes only a small integer multiple less fees than the target(s), and the targets are already spending the fees anyway. IE the defenders already have the resource, fee paying transactions, that the attacker has to buy specifically to launch the attack.


Standard sizes do not have to be a requirement actually. Suppose Alice has 2BTC and wants to send 1.5BTC to Bob: she can announce that she wants a 1.5BTC txout with Bob's scriptPubKey, and a 0.5BTC txout to a change address and broadcast that. Now suppose Charlie has 0.75BTC and simply wants to mix some of it, but doesn't really care how much. He can note that Alice has a 0.5BTC txout, and broadcast a request to make a transaction with her txouts, as well as a 0.5BTC txout to one of his addresses, and a 0.25BTC txout to a change address of his.

When the final transaction gets mined there are two 0.5BTC txouts - but who's are they?

Even in the general case where you have an Alice and a Bob who both want to send money it's often hard to figure out whose inputs and outputs are whose. Do the txouts belong to the same person, and they were just paying multiple people? Which of the multiple txins was actually owned by who?

It's easy to make the task of following the transaction graph very difficult without trying provided a lot of people are combining their transactions.

That basically sends the dust to anyone who wants it?  How does that help?


Since everyone has to pay for the service, if it fails, everyone loses.  However, the DOS attacker loses faster?

The "currency" for paying for message relay is effectively coin-age?

The transaction would be flooded in stages, everyone gets version 1 then version 2 then version 3 and so on.

Eventually someone signs and that ends the mixing. 

Signing the transaction early also acts as a DOS attack.

There would also be a requirement that "cleaned" coins have standard sizes.  You pay for something and you get 2 change payments, a cleaned standard value coin and the remainder.

This creates an incentive for merchants to set prices as one of the standard coin sizes.  One coin moving through the system doesn't link multiple transactions together at least.

FWIW I'll try implementing a "coin dust" collector this weekend that just does makes SIGHASH_NONE|ANYONECANPAY signatures for the dust in your wallet and sends them to a central collection point.

Regarding mixing in general if you can split up the mix protocol into separate stages of "I want these txouts", "I'll sign for those txouts", make broadcasting those requests use up a limited resource, and finally have a P2P flood fill network where finding the originator of a message is hard you can easily make a system that is both anonymous and DoS resistant. If we add a messaging layer to Bitcoin where messages are paid for somehow, perhaps by fees paid, this can be easily developed into a automatic 'coinjoin' system for every transaction made. In addition if you can add expiry times to 'txout requests' when peers connect you can give them the outstanding requests, which means allows nodes that just connected to their peers to quickly make a transaction even if they weren't online while the request was made.

What's really nice about this implementation is that while on the one hand it's a mixer, on the other hand it's also just a DoS-resistant way of making transactions smaller by getting multiple parties together to make them. It doesn't require any dedicated "rendezvous" points that may find their actions legally frowned upon, nor does it require a separate system (like Tor) be installed to talk to those points. The general purpose messaging layer could be useful for other things too - it'd be easy to use it for alerts for instance.

Rough technical sketch:

1) Create the messaging layer

1.1) Define NODE_MSG to signal that a node will relay messages. Define "message" inventory type and add to ppszTypeName. Optional: define "realms" of messages split up by a UUID or something.

1.2) Write code to maintain an inventory of such messages. Basically this will look kinda like the mempool, and there will be some time period for which old messages are expired, as well as a limit on total messages stored.

1.3) Relay those messages to peers/respond to getdata requests. If "realms" are supported, a bloom filter to select which realms a peer is interested in is useful.

2) Make DoS-attacks expensive

2.1) For every mempool tx, record the scriptPubKeys spent, and take the fees of the tx and proportion them to those scriptPubKeys.

2.2) Add a way to for messages to be signed by scriptPubKeys, and reduce the "balance" of fees recorded for each message. (amount sacrificed per msg should be configurable) Note that it may be necessary to only allow for fees to be used from transactions that have been actually mined - not sure how much that opens up attacks.

2.3) Other methods, PoW, fidelity bonds etc. possible too.

3) Add mix protocol

2.1) Define "I want these txouts" and "I'll sign for these txouts" messages.

2.2) Add logic for the announce/sign sequence, along with options for the user to decide how fast they want the tx to be generated. Typically after a few seconds I'd expect the program to give up and just sign the txouts it already has, thus creating a non-mixed tx. Note how if you need more than one txout in a given transaction this can still be a privacy improvement, because you can arrange so that the txin/txout set is still indistinguishable from a two-party tx.

2.3) Add better logic to make sure the fee-paying tx's used don't break anonymity - you wouldn't want to use the same scriptPubKey for txout announce and signature announce. Also clever crypto can help here too - but that can be added later. Remember that timing is a potential anonymity breaker too, so randomize it, and also randomly sometimes wait for the other party to broadcast signatures, or sometimes broadcast signatures yourself.

2.4) Long-term: add more SIGHASH options to make it easier to specify what txin's and txouts a signature applies too on a set basis, rather than the current inflexible options available.

4) Add prioritization so that blocks always get priority over message data and are transferred around the network fastest. Note how having non-blockchain data actually helps the overall resistance to traffic analysis for the whole system by providing a constant stream of data for which latency is less important to hide the data for which latency is more important.

Another fun one: with realms you can port completely different applications, like IRC chat, to run over this basis concept. Only nodes that are interested in a particular application, or are willing to lend bandwidth to allow users of that application more anonymity, need to relay messages for a given realm, which keeps the whole system scalable. Needs some work to actually find peers for a given realm, but that's just a matter of extending the address gossip functionality.

Meni Rosenfeld has also proposed using commutative encryption to mask participants from each other in such a scheme: https://bitcointalksearch.org/topic/using-mixing-transactions-to-improve-anonymity-54266

I'm too dumb to contribute to the code...but not so dumb as to not contribute to the bounty.  Thank you for the detailed explanation of this important issue.

This is a really nice writeup, thanks Gregory. Such ideas have been kicked around informally for a while:

https://bitcointalksearch.org/topic/m.1829259

see the part about p2p mixing protocols ... but it's good to have a name and a formal writeup.

The examples of how ordinary, everyday privacy leaks can cause people problems are great. I think I've named the "people learning each others salaries" one before, but birth control is an interesting one.

I think adding a rendezvous mechanism to the P2P network makes sense. It's already a broadcast network after all. So perhaps the right design is not to try and do absolutely everything over the existing P2P network but rather allow people to announce rendezvous points (Tor hidden services?) over the broadcast channel and then allow nodes to set announcement filters like they set Bloom filters today. If you are an SPV/leaf node on the network you wouldn't hear announcements until you request them. Other nodes would relay them all.

The difficult part is that you need a lot of traffic to make this work. Current tx volumes don't even reach one per second. So to accumulate enough users for a mix, you'd need to wait a while. It's fine for some kinds of payments that aren't time sensitive, but it's not going to work today for restaurant bills.

If I were doing it, I'd want to do the bulk of the implementation in bitcoinj of course, just because that's what most users are going to end up using (given current trajectories). It also has the advantage that using a managed language like Java eliminates entire classes of security holes, always a concern when writing financial software.

The advanced crypto part isn't necessarily that advanced and doesn't require ZK proof systems. Such protocols were already designed:

http://blog.ezyang.com/2012/07/secure-multiparty-bitcoin-anonymization/

It just requires secure multi-party sorts, which is a more well studied subset of general MPC.

@gmaxwell

I'm saluting to the unquestionalble genius of you and (almost ?) everybody else in this community.

Do you have any plans to start working on this feature soon ?
EDIT:
OK i read your post completely and appears that you are not.

Take a look also here: https://bitcointalksearch.org/topic/ann-bitprivacy-decentralized-trustless-privacy-200952  I think this is a similar concept, which is currently being worked on already (and I think even a test-net some-what-working version already exists).