CoinJoin: Bitcoin privacy for the real world

[themgp]

If you and someone else both send money to Wikileaks, you both sign your transactions.  The transactions, even for identical amounts, are not identical.  For one thing they will name different unspent txouts to spend; for another they'll have different timestamps.  For a third thing they will specify different addresses for "change" to come back to.  All of these things will be combined in a hash function to give your transaction a transaction ID which is unique.

There is no way in a transaction to determine what is "my output" and "your output".  That is what makes coin join work, but also brings up the problem originally posed.

Your output is the one that you have the key to spend.  What's hard about that?  There may be no way for anyone *else* to tell whose output is whose, but you are the guy who created that key pair, you still have the private key, and you know damn well whether a given output has the corresponding public key.  In a coinjoin everyone can identify their own outputs.  But they can't distinguish anyone else's, and no third-party observer can distinguish them at all.

We might be talking about different outputs.  The original question was not about the TxOut that is an input to the CoinJoin transaction, but instead the outputs of the CoinJoin Transaction itself. AFAIK, there is no way for me to get Wikileak's private key.

[1713525532]

1713525532

[1713525532]

1713525532

[1713525532]

1713525532

[prezbo]

You would never sign it.

But how would you know? If only one Wikileaks donation makes it into the final txn,  wouldn't each participant just assume it was their donation? How could they tell otherwise?

My reasoning exactly.

[prezbo]

If you and someone else both send money to Wikileaks, you both sign your transactions.  The transactions, even for identical amounts, are not identical.  For one thing they will name different unspent txouts to spend; for another they'll have different timestamps.  For a third thing they will specify different addresses for "change" to come back to.  All of these things will be combined in a hash function to give your transaction a transaction ID which is unique.

I suggest you carefully read the first post of this thread. We aren't discussing the usual bitcoin transactions here but coinjoin specifics.

When Participant A and Participant B create the Transaction from the information from Controller C, they will only create and sign a transaction where Controller C indicates the correct output amount, address, and identifier.  Participant A will only sign a transaction that has an output with identifier X and Participant B will only sign a transaction with identifier Y.

I guess one could include an indentifier in the tx_out using OP_DROP, that might work.

[Crowex]

It's a bit more convoluted but if everybody signs a dummy transaction with identifiers for the outputs then you could just remove the identifiers and everybody signs again if the transaction is exactly the same in terms of tx_out and tx_in.

[prezbo]

It's a bit more convoluted but if everybody signs a dummy transaction with identifiers for the outputs then you could just remove the identifiers and everybody signs again if the transaction is exactly the same in terms of tx_out and tx_in.

I don't quite understand, what exactly do you mean?

[Crowex]

I hope I've understood the problem correctly.

I just meant that if you didn't want to include the identifiers in the actual multi signature coin join transaction then everybody would sign a dummy transaction.
This dummy transaction would contain everybody's outputs with identifier so that they know that the controller hasn't redirected any duplicate payments to himself. The dummy transaction would not be broadcastable or valid but everybody would use it to agree to the tx_outs and tx_ins by everybody signing it.
 Once they had agreed by all signing the controller could create a valid transaction with the same inputs and outputs but without identifiers and then they would all sign this.
 
..or maybe I've misunderstood something?
 

[prezbo]

I hope I've understood the problem correctly.

I just meant that if you didn't want to include the identifiers in the actual multi signature coin join transaction then everybody would sign a dummy transaction.
This dummy transaction would contain everybody's outputs with identifier so that they know that the controller hasn't redirected any duplicate payments to himself. The dummy transaction would not be broadcastable or valid but everybody would use it to agree to the tx_outs and tx_ins by everybody signing it.
 Once they had agreed by all signing the controller could create a valid transaction with the same inputs and outputs but without identifiers and then they would all sign this.
 
..or maybe I've misunderstood something?
 

I see. The problem is if the service chooses the identifiers they would just send the two users different dummy transactions to sign, with such identifiers both would be convinced the donation is actually their own, so I think it has to be users who choose identifiers beforehand. I think just adding (random) id's to the outputs that are dropped off the stack using OP_DROP wold work though - so for each output I choose random number, add it (as <rnd number> OP_DROP), send inputs and outputs to the service, when I get the transaction back I check if the outputs match with what I sent, if they do I sign the transaction.

[Crowex]

I meant the users do choose their own identifiers, the dummy transaction is created with these.
I just thought the identifiers might be able mark out the transaction as a coin join transaction if they were part of the transaction which might not be desirable.
I'm not really familiar with OP_DROP, maybe it achieves the same thing.

[maaku]

But how would you know? If only one Wikileaks donation makes it into the final txn,  wouldn't each participant just assume it was their donation? How could they tell otherwise?

Reference the original offers in the join request, so that anyone considering signing the transaction can make sure that not just the correct outputs, but also the correct number of outputs are present. My Python implementation does this.

[prezbo]

But how would you know? If only one Wikileaks donation makes it into the final txn,  wouldn't each participant just assume it was their donation? How could they tell otherwise?

Reference the original offers in the join request, so that anyone considering signing the transaction can make sure that not just the correct outputs, but also the correct number of outputs are present. My Python implementation does this.

Can you link to your implementation, please? I'd like to have a look because I don't fully understand.

[maaku]

https://github.com/maaku/coinjoin

[prezbo]

https://github.com/maaku/coinjoin

thanks!

edit: hoped there would be a protocol draft of some sorts, unfortunately don't have the time to work it out how it works from the code.

[Murphant]

The way I understand it, the problem can be phrased in the following way.

Suppose that both Alice (address A) and Mallory (address M) want to buy an item from seller Steve. Alice and Mallory create a CoinJoin transaction (A,M) -> (S,M') where M' is another address controlled by Mallory. Alice signs the transaction as she sees that the correct amount is sent to Steve and expects to receive her service. However, Mallory may also later claim that he sent the money to Steve and that he should receive the service. From Steve's point of view, both claims are equally valid.

I believe that maaku's solution would work as long as the join requests are signed and kept by each party. One downside of this is that it might reduce the anonymity of the system since each user can later prove the other user's intentions to a third party.

Reference the original offers in the join request, so that anyone considering signing the transaction can make sure that not just the correct outputs, but also the correct number of outputs are present. My Python implementation does this.

Another, simpler solution would be to make sure to never send funds to a public address in a CoinJoin transaction and for sellers to always use fresh receiving addresses.

[prezbo]

Suppose that both Alice (address A) and Mallory (address M) want to buy an item from seller Steve. Alice and Mallory create a CoinJoin transaction (A,M) -> (S,M') where M' is another address controlled by Mallory. Alice signs the transaction as she sees that the correct amount is sent to Steve and expects to receive her service. However, Mallory may also later claim that he sent the money to Steve and that he should receive the service. From Steve's point of view, both claims are equally valid.

This is not exactly what I meant.

Alice uses input A and sends 1 btc to address S. Bob uses input B and sends 1 btc to address S. Legit coinjoin transaction would look like [A, B] -> [(S,1), (S,1)], but here the service could change it to  [A, B] -> [(S,1), (X,1)], where X is service's address. Since Alice isn't aware of Bob's transaction and vice versa none would suspect that the (S,1) output is not theirs, thus signing the transaction. As I said I don't really understand how maaku solves this problem. As I see it the only way to solve it is for users to provide some kind of a nonce with the outputs that can later be checked.

[Murphant]

Suppose that both Alice (address A) and Mallory (address M) want to buy an item from seller Steve. Alice and Mallory create a CoinJoin transaction (A,M) -> (S,M') where M' is another address controlled by Mallory. Alice signs the transaction as she sees that the correct amount is sent to Steve and expects to receive her service. However, Mallory may also later claim that he sent the money to Steve and that he should receive the service. From Steve's point of view, both claims are equally valid.

This is not exactly what I meant.

Alice uses input A and sends 1 btc to address S. Bob uses input B and sends 1 btc to address S. Correct coinjoin transaction would look like [A, B] -> [(S,1), (S,1)], but here service could change it to  [A, B] -> [(S,1), (X,1)], where X is services' address. Since Alice isn't aware of Bob's transaction and vice versa none would suspect the (S,1) output is not theirs, thus signing the transaction. As I said I don't really understand how maaku solves this problem. As I see it the only way to solve it is for users to provide some kind of a nonce with the outputs that can later be checked.

I was imagining more of a decentralized CoinJoin where people got together to create the transaction instead of asking a service to do it, but both situations are similar. In the centralized case, maaku's solution does not seem to work as it requires communication between the participants. However, sellers not reusing addresses that receive payments does solve the problem even in the centralized case as Alice and Bob cannot simultaneously think that they are paying Steve.

[prezbo]

However, sellers not reusing addresses that receive payments does solve the problem even in the centralized case as Alice and Bob cannot simultaneously think that they are paying Steve.

That is true, but the protocol shouldn't limit users in such a way. But you are correct, in a world with perfect information this is not a problem.

[piotr_n]

Of course you cannot trust any service more than to provide you the entire transaction you get to sign - not only its hash.
Then you make sure that at least one of its outputs satisfies your input.
And then you get to know more about a possible connections between the txs inputs and output. Which inforamtion, who knows, maybe you'll be able to sell one day in a future so you may want to keep it

Its really not as cool as you think, unless you build a huge and anonymous infrastrtuctere for it.
Who's going to do it? Jesus is dead for all I know. We're talking about tor at least, otherwise it dont make no sense. And what: SR style, or p2p? Is there even a p2p in tor? Who's going to pay for it to profit from it? Or it won't happen...

Anyway, understand that the weakest link here is the ip that sends your money to the network. Sharing the tx with your pals or strangers picked by some system to increase privacy - give me a break

[Crowex]

However, sellers not reusing addresses that receive payments does solve the problem even in the centralized case as Alice and Bob cannot simultaneously think that they are paying Steve.

That is true, but the protocol shouldn't limit users in such a way. But you are correct, in a world with perfect information this is not a problem.

the example was a donation address, it would be difficult to imagine this changing for each donation

As I said I don't really understand how maaku solves this problem

nor me, his approach seems to be more de-centralised, but I can't quite grasp how he can guarantee that this problem can't occur

[maaku]

maaku's solution does not seem to work as it requires communication between the participants

No, the server can include this signed information in the message it sends to participants.

The solution is simple: each participants sign what outputs they want to see on the chain. No participant signs the transaction unless they receive invoices separately signed by every single input which cumulatively add up to the transaction. Cryptographic blinding is used to make sure that users can specify hidden outputs not subject to this check.

the example was a donation address, it would be difficult to imagine this changing for each donation

Google "bitcoin stealth address"

[kjj]

Rather than adding more steps and layers to the system, I propose ignoring the chance of the joiner operator skimming merges.

If it bothers anyone, they can send their donation to a new address in their own wallet, then send that to the donation address in the normal way.  This operation could even be scripted.  (Your wallet searches google for your payment address.  If there are no results, it is more or less impossible for another coin join user to be sending to that address.  If there are results for it outside of the explorer sites, it automatically switches into 2-stage mode.)