Use multiple change addresses and coinjoin them

[chris-belcher]

One issue with JoinMarket CoinJoins is it's still usually possible to link together inputs from a single entity with the change address.

In the spirit of Mike Hearn's suggestion in the Merge Avoidance blog post of using multiple addresses, a partial solution to this might be that more than one change address is used, the taker tries to construct a coinjoin out of them too.

See this coinjoin example https://blockchain.info/tx/da1a2259be752dd6b5162221989181b7334bd0acbbc1bca31596e5bc32375770 The makers should send two or three change address to the taker, the change is distributed between them such that one set of change address has output value 1.88769 BTC, the smallest change output here.

Then it will be much less trivial to link inputs to change addresses, and link inputs together.

In a future transaction, the UTXOs on the different change addresses might be combined in one transaction. This may not always happen, and it's also very difficult to distinguish this between different makers being used again to create another coinjoin.

[chris-belcher]

Thinking carefully about this. It would still be possible to link together inputs, it would be harder to link together change outputs with inputs.

[AdamISZ]

Just noting this before I forget it, I wondered whether there might be a way to have a default behaviour where change is a fixed size (e.g. in set 0.01,0.1,1,10..) and then it would be possible to do 'change rounds' of joins which kill the change problem permanently. It would just be a default option, of course, rather than required, if people want to delink fixed amounts then you wouldn't do this.

[chris-belcher]

I know some altcoins have fixed sizes like that. Does that have implications for the divisibility of a currency?

[raedah]

Copying over my comments from dup #337.

We are currently creating a single change output per participant per transaction. Using coin join for anonymity means you are trying to obscure connecting the inputs to the outputs. Often times the change address is connectable to the input by seeing that the users total input size minus the coinjoin size (outputs of the same size) is equal to the users output change address. This can be further obscured by taking into account the size of the change addresses (non coinjoin sized outputs) in the transaction, and using the correct logic to decide the sizes and number of change outputs to use.

Examples:

Take the sizes of the largest change outputs that are not ours and which are smaller then the size of our output size needed. Then create outputs equal to the other parties outputs, effectively creating additional joins of the change. Note, this also obscures the intention of the transaction because the coinjoin size can now be indistinguishable from the joined change for some cases.

Included in the protocol and negotiation for the transaction setup could be steps for agreeing upon a mutual change output size. Or, a shared algorithm could be used which determines the shared change output size.

After the initial transaction setup, each participant, starting from the one with the second smallest change output, would have the option to split their change output to join with the smaller sized change outputs. This process continues through each party successively from the small sized output to larger sized output. Note that this process would allow parties with larger sized outputs to join with both of the previous parties change outputs, obscuring both or all of the earlier parties outputs completely.

It could also be done that any party who wishes to join outputs can initiate a transaction reorg with the rest of the group. Instead of starting at the smallest, it may actually be more effective for participants with larger size change to initiate the process, as they can create a join output against the change outputs that match one or many of the change outputs of the other participants. This will reduce the overall number of outputs, hence a smaller transaction, and a smaller transaction fee.

The general rule here is that the outputs should not be mathematically deduced as connected to that participant's total input size. (We must assume the inputs ownership is not yet obscured, even in cases of many inputs from a single participant.) A participant does not even need to create outputs of the same size as other parties. It may be possible they created an output that is the cumulative size of other outputs, and which could have plausibly been created by another participant. Non joined output change remainders would need to be taken into account. The math for this would need to be figured out.

Change outputs that are joined (obscured) do not need to remain in the existing mix depth, and can get moved down to the next mix depth.

A variation of this functionality could be implemented with no protocol changes and no negotiation with the other participants (as long as we can know the other participants change output sizes before telling them ours.) Allow a participant to automatically add additional outputs equal to the size of the initial coinjoin. This can be done for both the taker or the maker. Though this would provide some additional privacy in all cases, it could still be determined with a higher probability that a majority of the joined coins came from a particular participant but still not with certainty which particular outputs. So to maintain strong joining, it would be wise to do this only for amounts that are less then the total size of an other participants change. Also needed is one change output that is equal to the remainder needed in order to be equivalent to the other parties outputs, and hence equivalently joined, obscured, and plausibly deniable.

Even the remainder amount left over from the participant with the largest change could be joined against other smaller outputs in the transaction, creating the smallest remainder possible. Mathematical checks should be done to make sure that these additional remainder joins still have the same level of obscurity and link-ability probability. This would depend on the distribution of sizes of outputs from other participants.

There may be a way to support advertising this additional join functionality and charging a cjfee for it as well.

If sendpayment.py (patientsendpayments.py) supported batching/queuing of outgoing transactions, many joins per transaction could occur this way, and a flag could be enabled to require the joining of the change address as well so that it is treated as a regular outgoing address.

As mentioned in issue #105 , the makers could send additional change addresses to the taker, and the taker could organize the transaction appropriately. Note, unused change addresses should not be reusable since they would already be exposed.

Caveats:

In cases where some of the change gets joined, there would likely still be additional left over coins that would not get joined and would not be obscured. It is unlikely that all change would be obscured. It may be possible to obscure all participants change except the participant with the largest sized change.

This is protocol enhancement. Linking to #171

[Giszmo]

The taker could generally demand all makers to bring at least as many coins to the table as him, to blind the change, too, paying for the full UTXO and not only for the first output.

Especially with #218 being common and the change being non-powers of ten, the result could look like a cut-through transaction. Still the powers of ten are intriguing as they are by far the most common UTXO amounts anyway.

Counting UTXO amounts:

amount [mBTC]	count
10	365547
1	238014
100	116729
1000	95985
20	78374
50	68496
5	55263
2	46007