req: Enhance privacy with multiple change addresses

[raedah]

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 Use multiple change addresses and coinjoin them #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

[chris-belcher]

Agreed.

This is the same as #105

[AdamISZ]

@raedah Would it be possible to close this and add your comments to #105 ? trying to reduce issue duplication if possible.