CoinJoin: Bitcoin privacy for the real world

[Dabs]

I have a question:
When I am doing a transaction and I send my signed tx to the network. Could someone else take that transaction and add a additional signed input to the tx. So this would mean that my tx gets coinjoined without my approval, would that be accepted by the network?

Greets

From what I understand, that is not possible; or not practical. You'll have to coinjoin your transactions first before sending it to the network.

It may be possible with the replace-with-fee thingie, but if the first transaction gets confirmed, then the second one won't work anymore as it will be a double-spend.

For CoinJoin to work, people need to join their signed tx first. The only way I see this working is some sort of third-party that does the joining, or some app that does it for everyone involved, at the same time, or waiting within a set time.

I think what's happening is people meet up and then agree to do a CoinJoin, either in chat or through some app or website, the third-party not being able to steal any coins in the process.

[Cryddit]

Effective coinjoin that doesn't create metadata patterns of its own is hard. 

If you want the capital-S Solution, the Zerocoin protocol is down the hall - but it wasn't, and won't be, implemented in Bitcoin because the cryptographic accumulator comes with ridiculous compute-time overhead for verifying spends. 

If you want a lowercase-s Solution, Dash has its mixing masternodes; some node operator posts a big bond to the block chain to get to be trusted for pooling, and then people run their transactions through a dozen different masternodes that cant see what each other are doing to get them thoroughly mixed before they go on to the block chain.  This doesn't suck, but it's also not ideal; those masternodes are "trusted" in the sense that if they cooperate they can de-anonymize transactions. 

But coinjoin, in the absence of mixing services (aka masternodes) to join transactions between arbitrary people who've never heard of each other, creates exactly the kind of metadata it seeks to avoid.  People analyze the block chain and coinjoined transactions attract attention because they are anomalous in terms of how their inputs and outputs are connected to other tx.  When the chain is analyzed further, the snoops can identify which actors know each other and cooperated together to create the coinjoin. 

[Dabs]

But coinjoin, in the absence of mixing services (aka masternodes) to join transactions between arbitrary people who've never heard of each other, ...

That's the thing. The only missing element is a decentralized version of this. Mixing services that do CoinJoin can exist, I'm just wondering if that qualifies for the bounty here.

The few CoinJoin transactions that exist now can be analyzed, but when the volume and frequency of such transactions get big enough and often enough, it's practically impossible to analyze, especially if all actors are anonymous ...

All that people really need to give up is a little inconvenience, because they have to run their coins through such "masternodes", it's not automatic.

Normal people can send their CoinJoin transactions and their coins to some "masternode" while they sleep. A few hundred people to a few thousand people do this and in 8 hours to a day later you don't know who owns what coins. If this is done daily or with other mixers, every day, every month, the whole year ... do we achieve our goal then?

[Cryddit]

Well, consider the RSA/ extended Diffie-Hellman construction:

When you have X^AB mod G, (where X and G are public) you can find B if you know A, or you can find A if you know B, but you can't find AB, or A, or even B, unless you know the factors of G. 

So you can multiply the exponent by a couple of factors and produce a new accumulator - and nobody can tell what the factors were.  But later you can undo it, because you know what the factors were.  And you can do this even if a dozen other people have since added or removed values to the accumulator, in any order. 

In a lot of ways, what the people forming a coinjoin are doing is passing around an accumulator.  None of them knows what the others are putting in, but each is able to check the final accumulator and make sure their own input is part of it (ie, their values are still factors of the exponent).  And then if they break it down in a different order, at no time does it acquire the same value as it had at any previous state or one easily related to such - but it returns to the same initial state when everybody's value has been taken out of it.

That's sort of a truncated version of what Zerocoin does - but if you work out the details, you might be able to do it without that horrible zero-knowledge signature of knowledge proof.  People would only have to verify steps and final result of a single join per block.

I'm just sort of brainstorming here... 

[twinkletoes007]

Somebody please "CoinJoin for Dummies".

[Cryddit]

Heh.  Okay.

The way things are now, snoops looking at the block chain can mostly tell which transactions were made by the same people as other transactions.  If they identify a single thing as belonging to a particular person (which is usually easy, because among other things they listen on the network to get the IP addresses where tx originate) then they can generally walk it back and identify every other transaction that person has ever made from that wallet. 

People generally don't think this is okay.  Even if they're not crooks they don't necessarily want everybody else to know when and where they bought a dirty magazine and some hand lotion - or, you know, bondage gear or any number of other things that are just plain private. 

So they look for a way to mix up transactions; store txOuts in the block chain somehow where snoops can't tell which belongs to whom.  When a hundred people do a coinjoin, you take a bunch of different transactions, and make them into one giant transaction, with maybe hundreds of different txIns and txOuts - and now the snoops can't tell any more which of the txOuts belongs to whom.  If you then open a new wallet and put the txOuts from the coinjoin into it and no txOuts from your old wallet, they'll never be able to link the purchases you made (or payments you received)  before the coinjoin with the ones after it.  At most they'll be able to tell such-and-such a purchase group of purchases after the coinjoin was made by one of the hundred people who participated in this coinjoin transaction. 

But it's dastardly hard to do this in such a way that when you're exchanging messages to set up the coinjoin, you don't give the eavesdropping snoops enough information to suss out which txOuts from the coinjoin belong to whom.  Especially since everybody has to be able to verify that the transactions are correct. 

So what you try to do is things like Diffie-Hellman key exchange, where you can have two people (or in this case way more than two) find a secret value together (in diffie-hellman a key; in coinjoin a whole transaction) without giving snoops any clues. 

This is made harder by the difference between the two use cases.  In Diffie-Hellman the parties don't care much what the value winds up being; only that they agree on what it is and nobody who's been listening to them can suss it out.  But with coinjoin you care a whole lot about exactly what the value is, because the value you're trying to agree on has to be a valid transaction that does what you want it to do. 

So we need things more complicated than just hashes and bit commitments and signatures; we need things like cryptographic accumulators and commutative encryption, which are sort of esoteric and usually really compute expensive.

Somebody figured out a way to do it with a compound-exponential accumulator under a modulus (called the ZeroCoin protocol) but it's ridiculously compute-intensive; it would mean everybody has to spend five minutes or so just checking correctness after each block, and people with 'weak' machines couldn't check those tx at all.  I've been wondering about a way to do it using single-exponential accumulators and bit commitments. 

Note:  An 'accumulator' is a keyed transformation such that

A ==> Encrypt with key1, key2, key3, etc, in any order ==> Decrypt with key1, key2, key3, etc in any order ==> A.

You could use something like that to show that you have one of the keys that went into creating it, without revealing which.  That is, assuming you  manage to not reveal the key that went into creating it when you encrypt it the first time.  Which, if you don't, makes the transaction hard to check....

[Dabs]

Cryddit,

Is there a difference between a CoinJoin transaction and a regular bitcoin transaction that has many inputs and many outputs? What I mean is, for example, I have a large wallet with 10 different and unconnected unspent bitcoins, in 10 separate addresses. Then since I am the owner of that wallet, I can do a transaction and use those 10 as inputs to a transaction that pays out or sends out bitcoins to 20 different addresses.

What I'm wondering is if there is a fundamental difference between that, and a CoinJoin transaction with 9 other people.

Yes, I've read and re-read the original post and this entire thread, I'm just seeking clarification if I am understanding this correctly.

[dooglus]

Cryddit,

Is there a difference between a CoinJoin transaction and a regular bitcoin transaction that has many inputs and many outputs? What I mean is, for example, I have a large wallet with 10 different and unconnected unspent bitcoins, in 10 separate addresses. Then since I am the owner of that wallet, I can do a transaction and use those 10 as inputs to a transaction that pays out or sends out bitcoins to 20 different addresses.

What I'm wondering is if there is a fundamental difference between that, and a CoinJoin transaction with 9 other people.

Yes, I've read and re-read the original post and this entire thread, I'm just seeking clarification if I am understanding this correctly.

There's no difference other than that with a coinjoin the inputs are owned by different people whereas with the transaction you made all the inputs were owned by you.

Before coinjoin, you could look at a transaction and be pretty certain that all its inputs were owned by the same wallet. People would use this information to cluster addresses into groups.

After coinjoin that assumption is no longer valid. Multiple parties can cooperate to sign a single transaction where they each own some of the inputs. This makes clustering by ownership harder to do.

Here's an early example:

  

It looks like gmaxwell owns both input addresses, but he doesn't. He only owns the smaller one.

[Cryddit]

Cryddit,

Is there a difference between a CoinJoin transaction and a regular bitcoin transaction that has many inputs and many outputs? What I mean is, for example, I have a large wallet with 10 different and unconnected unspent bitcoins, in 10 separate addresses. Then since I am the owner of that wallet, I can do a transaction and use those 10 as inputs to a transaction that pays out or sends out bitcoins to 20 different addresses.

What I'm wondering is if there is a fundamental difference between that, and a CoinJoin transaction with 9 other people.

In terms of the bytes that appear in the transaction itself, there is no difference. 

The difference is all in what the snoops can infer from the bytes.  When you make that transaction you described, the snoops would look at the block chain and say,

Oh, these twenty new addresses were all funded by the same transaction.  Therefore all the funding came from the same source (because almost always it's a single source sending money).  And since this doesn't look like a purchase (purchases typically have one large output and one much smaller "change" output) it must have been a logistical or bookkeeping movement of coins.  So we're going to assume that now all twenty of these new addresses are owned by the same person. 

Later on, they'll confirm it if, say, one of those 20 outputs gets spent, and you get a millibitcoin of change, and then later that millibitcoin of change gets spent in the same transaction as another of those 20 outputs, or as change from another of those 20 outputs - they go, Aha, look!  This new evidence means that what we thought about the addresses being owned by the same person, is now confirmed!  These two txOuts were owned by the same person, and now we can link all the purchases that were made with both of them! 

Now consider what happens with a coinjoin.  Alice is buying an Anvil, Bob is buying a Book. Carol is buying a Coat, Dave is buying a duck, and so on....  Maybe Zebulon is buying a Zebra, who knows.  They do a coinjoin transaction, and there's an output to the blacksmith shop and an output to the bookstore, and an output to the clothier, and also outputs to Alice, Bob, Dave, Carol, and everybody else - and the outputs are all kinds of different sizes instead of just being clearly "payment" and "change." 

Superficially, it looks like the same transaction.  Some number of inputs, some number of outputs.  But the snoops looking at it say, "Oh, all these inputs must have come from the same person, and it doesn't look like a regular purchase, so we'll assume all the outputs are going to the same person too...."  except this time they're wrong.  They'll pretty quickly figure out (because the way merchants combine the money that they get paid is very obvious) which outputs went to merchants and how much each merchant got.  They may be able to backtrace a lot of the unconnected txIns to figure out who owned them before the transaction.  But they will never figure out who it was that bought the duck, who it was that bought the book, and who it was that bought the zebra.  The best they'll be able to say is, "one of these people whose coins went into the transaction." 

And by the same token, even after they figure out which outputs were paid to merchants, they won't know which of those people now have the other outputs, until or unless those other people spend them along with txOuts they can link to that person.  Again, best they'll be able to say is "one of these people whose coins went into the transaction." 

But this requires that Alice, and Bob, and Carol, and Dave, etc have a way to set up the coinjoin that Eve can't figure out.  Even if Eve is one of the people putting coins into the coinjoin and getting coins out, she shouldn't be getting information about what other people are putting in and getting out.

[waxwing]

But it's dastardly hard to do this in such a way that when you're exchanging messages to set up the coinjoin, you don't give the eavesdropping snoops enough information to suss out which txOuts from the coinjoin belong to whom.  Especially since everybody has to be able to verify that the transactions are correct. 

So what you try to do is things like Diffie-Hellman key exchange, where you can have two people (or in this case way more than two) find a secret value together (in diffie-hellman a key; in coinjoin a whole transaction) without giving snoops any clues. 

I realise this doesn't fully speak to what you're musing on in that post, but thought it might add to the discussion:

In Joinmarket we use E2E encryption authenticated to the bitcoin pubkeys that the different parties use as inputs to prevent MITM. This prevents a non-participant from learning the linkages.

As to preventing counterparties knowing the linkages, that's discussed in the first post(s) here. There are several ways to do it. The simplest is to have a server that's trusted, obviously suboptimal. You can add blind signing with network-level anonymisation to cut the connection between the proposal and the signing. To achieve the same effect you can use Coinshuffle. But, these two approaches don't address the Sybil problem - if all your counterparties are the same person, they learn the linkages by elimination.

Joinmarket allows one of the participants to act as the central coordinator - called the taker - and so only the taker gets the full defence against others knowing linkages - and so pays for that privilege (albeit in practice the payment is ultra-small). the other participants still get the defence against outside parties knowing the linkage due to the E2E encryption. And the Sybil problem remains; while we have some ideas about making it harder (see e.g. here: https://gist.github.com/AdamISZ/9cbba5e9408d23813ca8 , although there are other ideas/things to be said), we haven't implemented it.

The network level snooping: as where tx broadcasts originate - can be addressed with Tor to some extent. We also have things like randomising which participant broadcasts the transaction (a feature that belcher recently added). But as you mention there's also the issue of where you source the data to verify inputs (e.g. if you use a centralised blockchain API it's decidedly suboptimal).

[waxwing]

On the topic of whether a coinjoin is discoverable/watermarkable let's say, I'd say a couple of things: if coinjoins follow an identifiable pattern, it certainly doesn't mean that they're useless; the main effect that a coinjoin output (i.e. equal sized output) is fundamentally indistinguishable from its neighbour coinjoin outputs is still true. That's the main effect we're looking for. The only conceivable negative is that the inputs to such a transaction are marked "This wallet closure is suspicious"; although I think any good "Bitcoin citizen" should prefer to use coinjoins where it's practical, since this is a currency and it's intended to be fungible. I've tried to make most of my recent retail payments with coinjoins.

Wallet closure analysis *is* damaged (severely) by use of coinjoins and that's the intention. Trying to make them invisible (i.e. not have properties distinct from non-coinjoins) seems like a high bar to set, and a moving target. I know Kristov Atlas has been looking into how transaction structures could be standardized to facilitate this; it seems like a hard goal to reach, but worth looking into.

Second, Joinmarket coinjoins are fairly easily found (with some false positives of course), see e.g.: https://github.com/AdamISZ/JMPrivacyAnalysis/blob/master/tumbler_privacy.md#identifying-joinmarket-transaction-types and Adlai's even made a tool to automate finding them on the blockchain: https://github.com/adlai/cjhunt.

TLDR I don't think coinjoins being identifiable is such a bad thing; even the most brain-dead construction is better for privacy than a non-coinjoin in any case, and by a long way.

[waxwing]

I have a question:
When I am doing a transaction and I send my signed tx to the network. Could someone else take that transaction and add a additional signed input to the tx. So this would mean that my tx gets coinjoined without my approval, would that be accepted by the network?

Greets

Not possible unless you explicitly chose to use non-standard sighash flags (and even then! possibly it could happen with SIGHASH_SINGLE|SIGHASH_ANYONECANPAY).

[dooglus]

I have a question:
When I am doing a transaction and I send my signed tx to the network. Could someone else take that transaction and add a additional signed input to the tx. So this would mean that my tx gets coinjoined without my approval, would that be accepted by the network?

Greets

Not possible unless you explicitly chose to use non-standard sighash flags (and even then! possibly it could happen with SIGHASH_SINGLE|SIGHASH_ANYONECANPAY).

Or in layman's terms, by default every signature is signing the complete set of inputs and outputs. If you change any input or output the signatures become invalid.

[Dabs]

Oh. Ok. I get it. This is good then.

But for people to do the CoinJoin, they all have to sign the same transaction, thus the possibility of a denial of service attack (by pretending to be part of the process but not signing the transaction.)

From what I understand, this "network level snooping" can only be done live, or someone or something is watching a good number of nodes, because the blockchain data itself does not store ip addresses. The transaction doesn't have any ip address information either. And where the transaction is first relayed is no indication that that is the one that actually sent it. And in any case, with a CoinJoin with a good number of real people, it doesn't matter who sent it as everyone else signed it, the one who actually broadcasts the transaction can be anyone, or even a completely different entity, or went through Tor or a VPN or from some random internet cafe. (Spammers do it all the time and are rarely or never caught.)

So, the problem is: too big a CoinJoin, (like with a few thousand) is hard to pull off, and some people might not go through with it. Too small, (such as 2 or 3 or 4 inputs and outputs) and its too easy to analyze.

So, if someone comes up with a "trusted" server, or shall I say "trustless" server, even if it is suboptimal, then that's still a good thing as long as that server is not compromised, or it doesn't keep logs after every transaction or something like that.

I mean, I can see at least 2 really big "traditional" mixers on these forums. The biggest one supposedly has a reserve of 3000 BTC. These guys can certainly pull it off, many people already trust them to mix "traditionally", I don't suppose they'd have a problem getting the same users to trust them to "CoinJoin" the whole thing and include their reserve in the process.

I have an idea, and guys, let me know if this is decent or crazy or whatever: or if this is already what is being done by JoinMarket, Shuffle, Whatever.

1. I make a website or a server for this purpose.
2. It asks users to create their transactions, and a given time limit, say 30 minutes or 1 hour.
3. Every 30 minutes, or every hour, it gets back to all the users with the giant CoinJoin transaction formed thus far and asks all the people to sign.
4. The site itself takes a fee, and that's some how inserted into the process.
5. Assuming the site is "trustable", then only outsiders are "attackers" and they're not going to learn much except "I see 100 inputs and 200 outputs, and I own 20 of them. I dunno who the other 80 are."
6. Repeat every hour or every whenever. Or every 100 people. Or once a day.
7. Java script or open source client side signing thingy that can sign for you if you're away from your computer so the site doesn't have to wait an hour when it reaches the minimum number of people.

The other idea I had, which I mentioned a long time ago, is like a traditional mixer, in that the mixer site itself has to be trusted, but it does everything internally, and you just send your coins. Instead of the traditional mixing of unrelated inputs and outputs, it's basically a CoinJoin mixer that gets all deposits and spits out the transactions just like a traditional mixer. The only downside is having to trust the site.

[Rampion]

BTW (and sorry for being slightly off-topic): did blockchain.info remove "shared coin", their coinjoin implementation? Cannot find it anymore!

[waxwing]

I have an idea, and guys, let me know if this is decent or crazy or whatever: or if this is already what is being done by JoinMarket, Shuffle, Whatever.

1. I make a website or a server for this purpose.
2. It asks users to create their transactions, and a given time limit, say 30 minutes or 1 hour.
3. Every 30 minutes, or every hour, it gets back to all the users with the giant CoinJoin transaction formed thus far and asks all the people to sign.
4. The site itself takes a fee, and that's some how inserted into the process.
5. Assuming the site is "trustable", then only outsiders are "attackers" and they're not going to learn much except "I see 100 inputs and 200 outputs, and I own 20 of them. I dunno who the other 80 are."
6. Repeat every hour or every whenever. Or every 100 people. Or once a day.
7. Java script or open source client side signing thingy that can sign for you if you're away from your computer so the site doesn't have to wait an hour when it reaches the minimum number of people.

I don't know if you're aware, but joinmarket exists (has done for a year on mainnet now), it's doing maybe 50-100 transactions per day (hard to get numbers without running the blockchain analysis mentioned above; and false positives there will confuse it). You can see the orderbook at https://joinmarket.me/ob

As for the description above, it's fine (it's the first, simplest design mentioned by gmaxwell in the OP) but having the server know all the linkages is a bit much. Joinmarket has one participant act as the coordinator for each transaction, and pay for the privilege of knowing the linkages for that transaction (I'm repeating myself now, I said this a few posts back). Instead of one server with a global history. To go further, you add Coinshuffle or blind signing so that no-one needs to know the linkages (assuming no Sybil case, i.e. other participants are really distinct).

The economic incentive, while small, helps create more participants. Most joinmarket coinjoins involve 3-6 participants although 10+ is not unheard of  (I myself had a couple of 9,10 party joins recently, e.g. e701bc57fa663eaef4d57a9ea20b3212a90a8be71a32bd3bcb84062e864bdab0).

[CohibAA]

I have an idea, and guys, let me know if this is decent or crazy or whatever: or if this is already what is being done by JoinMarket, Shuffle, Whatever.

1. I make a website or a server for this purpose.
2. It asks users to create their transactions, and a given time limit, say 30 minutes or 1 hour.
3. Every 30 minutes, or every hour, it gets back to all the users with the giant CoinJoin transaction formed thus far and asks all the people to sign.
4. The site itself takes a fee, and that's some how inserted into the process.
5. Assuming the site is "trustable", then only outsiders are "attackers" and they're not going to learn much except "I see 100 inputs and 200 outputs, and I own 20 of them. I dunno who the other 80 are."
6. Repeat every hour or every whenever. Or every 100 people. Or once a day.
7. Java script or open source client side signing thingy that can sign for you if you're away from your computer so the site doesn't have to wait an hour when it reaches the minimum number of people.

The other idea I had, which I mentioned a long time ago, is like a traditional mixer, in that the mixer site itself has to be trusted, but it does everything internally, and you just send your coins. Instead of the traditional mixing of unrelated inputs and outputs, it's basically a CoinJoin mixer that gets all deposits and spits out the transactions just like a traditional mixer. The only downside is having to trust the site.

I think it's at least a decent idea, although implementation might be tricky.  One limitation with JoinMarket is the ability to easily facilitate a transaction with a very large number of parties.  As of right now, there are only about 50 "makers" on the orderbook, and likely many of those are actually the same people, running multiple yield generator bots.  The largest coinjoin done using JoinMarket that I am aware of had 17 parties. (that might not even be the most interesting thing about that transaction...)

 

I think something like this would be possible to build within JoinMarket, such that "takers" are given an option to delay and group their transaction with other takers (and makers, maybe), but again, I'm sure the coding would be substantial.  A better solution for JoinMarket will likely be simple growth.  The GUI is probably helping to bring in more users.  An Electrum plugin could also be potentially huge for JoinMarket, bringing fungibility (is that a word?) to many more users.  I think some privacy conscious websites may also benefit from implementing JoinMarket transactions into their wallet structure (online casinos, darknet markets, etc.) which will also help the current limitations.

Interesting times.

[belcher]

New paper on address closures / clustering.

http://arxiv.org/abs/1605.06369

Sorry for bumping this thread ... I'm just curious.

...

3M8XGFBKwkf7miBzpkU3x2DoWwAVrD1mhk

...

The bounty fund will pay out as funds are available according to the signers best judgment for completed work proposed in this thread that furthers the goal of making improved transaction privacy a practical reality for Bitcoin users.

If JoinMarket did not qualify, and CoinShuffle (or ShuffleCoin?) did not also qualify, what would do it? Does it have to be completely decentralized? Can it be something that relies on a "super-node" or even a third party website, bot or api? (Someone collects possible transactions and makes everyone sign it once a day or once an hour or something.)

How do you define "practical reality for Bitcoin users"?

Did I miss any other attempts at implementing this aside from CoinShuffle and JoinMarket?

Would be interested to know as well.
Six months ago I sent a PM to theymos, Pieter Wuille, gmaxwell asking for (some of) the bounty.

I think something like this would be possible to build within JoinMarket, such that "takers" are given an option to delay and group their transaction with other takers (and makers, maybe), but again, I'm sure the coding would be substantial.  A better solution for JoinMarket will likely be simple growth.  The GUI is probably helping to bring in more users.  An Electrum plugin could also be potentially huge for JoinMarket, bringing fungibility (is that a word?) to many more users.  I think some privacy conscious websites may also benefit from implementing JoinMarket transactions into their wallet structure (online casinos, darknet markets, etc.) which will also help the current limitations.

This could be done with a script called patientsendpayment.py, https://github.com/JoinMarket-Org/joinmarket/wiki/Sending-payments-with-CoinJoin#patient-send-payment
Although because the current protocol is flawed and needs updating, you can only send to addresses for which you know the private key.

Using JoinMarket for bitcoin websites could be done today, I've written a brief explanation on how here https://github.com/JoinMarket-Org/joinmarket/issues/293

[Dabs]

(that might not even be the most interesting thing about that transaction...)

I looked at that, and this one looked interesting to me:

https://btc.blockr.io/address/info/1PavedWithGodAndSomeTeensionXudq5X

It would seem someone intentionally destroyed 1.6 BTC.

[waxwing]

It would seem someone intentionally destroyed 1.6 BTC.

Phi to be (more) precise