More Submappings

[nopara73]

It's not a bug or issue, so I guess it can be insta closed, it's just I wanted to share a few notes and elaborate on the example used in the paper.

Avoiding Amount Linkages Through Combinatorics

Naive multiparty coinjoin schemes are vulnerable to chain analysis based on amount linkages. For example, if you see a joined transaction of (0.5, 0.5, 0.4, 0.7) -> (0.4, 0.6, 0.3, 0.8), this can be uniquely decomposed into (0.5, 0.5) -> (0.4, 0.6) and (0.4, 0.7) -> (0.3, 0.8). (references: https://www.coinjoinsudoku.com/, https://github.com/Samourai-Wallet/boltzmann).

For the record, the full list of submappings are:

0.5,0.5,0.4,0.7 -> 0.4,0.6,0.3,0.8
0.5,0.5,0.7 -> 0.6,0.3,0.8 | 0.4 -> 0.4
0.5,0.7 -> 0.4,0.8 | 0.5,0.4 -> 0.6,0.3
0.5,0.5,0.4 -> 0.6,0.8 | 0.7 -> 0.4,0.3
0.5,0.4 -> 0.6,0.3 | 0.5,0.7 -> 0.4,0.8
0.5,0.5 -> 0.4,0.6 | 0.4,0.7 -> 0.3,0.8

This actually shows how important it is to use numbers those are either random or sit on the distribution of real world data. Since the following lines in the paper...

As a result of the above analysis, modern coin shuffling schemes have focused on making equal-amount coins, which intrinsically are indistinguishable (CashShuffle, Wasabi, etc). In isolation, these shuffle schemes are essentially perfect, especially since the cryptographic protocol allows parties to hide information even from each other.

...would like to state that coinjoins can be easily decomposed to their submappings, this is the wrong example to make here, as it illustrates the opposite, that it cannot be easily decomposed and that there are numerous submappings.

More Interesting Info

Input match probabilities:
0.5 - inputs: 0.5(0.67) 0.4(0.5) 0.7(0.5) | outputs: 0.4(0.5) 0.6(0.83) 0.3(0.5) 0.8(0.67)
0.5 - inputs: 0.5(0.67) 0.4(0.5) 0.7(0.5) | outputs: 0.4(0.5) 0.6(0.83) 0.3(0.5) 0.8(0.67)
0.4 - inputs: 0.5(0.5) 0.5(0.5) 0.7(0.33) | outputs: 0.4(0.33) 0.6(0.67) 0.3(0.67) 0.8(0.5)
0.7 - inputs: 0.5(0.5) 0.5(0.5) 0.4(0.33) | outputs: 0.4(0.67) 0.6(0.33) 0.3(0.67) 0.8(0.83)

Output match probabilities:
0.4 - inputs: 0.6(0.33) 0.3(0.33) 0.8(0.5) | outputs: 0.5(0.5) 0.5(0.5) 0.4(0.33) 0.7(0.67)
0.6 - inputs: 0.4(0.33) 0.3(0.67) 0.8(0.5) | outputs: 0.5(0.83) 0.5(0.83) 0.4(0.67) 0.7(0.33)
0.3 - inputs: 0.4(0.33) 0.6(0.67) 0.8(0.5) | outputs: 0.5(0.5) 0.5(0.5) 0.4(0.67) 0.7(0.67)
0.8 - inputs: 0.4(0.5) 0.6(0.5) 0.3(0.5) | outputs: 0.5(0.67) 0.5(0.67) 0.4(0.5) 0.7(0.83)

CoinJoin Ambiguity Score: 72

Resources

• Explanation: https://medium.com/@nopara73/knapsack-mixing-6a5b1ac95c33
• Tool used to create the analysis: https://github.com/nopara73/CoinJoinAnalysis