preferred value series mixing.md

Unequal Amount Mixing for ZeroLink using Preferred Value Series Fixed Denominations

This is a quick sketch of several modifications to zerolink. This document tries to articulate an as of yet unproven intuition is that combined together they can allow unequal input amounts as well as relaxation of the post-mix no linking restriction, while retaining the same conservative assumptions about mixed output indistinguishability.

Disallowing post-mix linking is arguably bad for fungibility, since users are likely to bypass this restriction by transferring to other wallets. Therefore, if I am able to justify this change this seems like a much more substantial contribution to usability and fungibility. That said even if it can't be shown to be reasonable to do so, some of these ideas still have merit on their own, so not all would be lost.

Proposed Protocol Changes

"Soft Fork" changes

1. Enable additional fixed denomination mixing rounds based on preferred value series: i.e. instead of just rounds of 0.1 as is the case today with wasabi, there would be multiple independent rounds for e.g. using the 1-2-5 series, the round denominations could be { 1, 2, 5 } * 10^n for all non-dust values of n (unpopular denominations would simply take longer to mix). Even with increased adoption this would likely reduce the size of anonymity set in given wallclock time interval, but not in discrete time measured mixing rounds.

3 phase chaumian coinjoin "hard fork"

Instead of input registration submitting multiple inputs, a change output and a blinded mix output, input registration mints chaumian tokens corresponding to the input amount minus the per-input fees, at a rate corresponding to the mixing fees.

These tokens can then be unblinded and "spent", deducting the per output fee, to register outputs that are not linked to the inputs before the final coinjoin signing phase. The server could still enforce the restriction of only 1 mixed output per participant if inputs must be registered together, with a single "mix" token being issued for the round denomination, and the remaining amount issued as "change" tokens (thus limiting the number of mixed outputs that can be made from one or more inputs to at most one). This restriction could also be relaxed, to allow tumbling that preserves the fixed denomination (allowing mixing fees to be paid by seemingly unrelated inputs).

Token denominations and colours would be specified by a set of per-round keys, and are thus only valid for the duration of the round. To allow O(1) verification of tokens, the amount should also be specified when spending: (amount, serial, signature) (see also brands credentials, anonymous credentials light for how to encode amount information with blind signatures).

This revised protocol would allow the following changes:

2. Implement group send proposal as a new round type (non mixing round). If post-mix linking is allowed, then values over 0.1 would be spendable by using multiple mixed txos. Assuming preferred value series denominations are used, payments should generally be possible without requiring a change output given enough values (e.g. 0.321 = 0.2 + 0.1 + 0.02 + 0.001).

3. Implement dual of group send, i.e. non mixing rounds for breaking arbitrary sized inputs into fixed size, mixable denominations.

4. When rounds of any kind coincide, be they splitting to fixed denominations, mixing rounds, or group sends, they can be merged by the server into a single coinjoin transaction (merged rounds end by signing the same transaction). The server should still enforce rules for different round types, i.e. unequal amounts only get broken up, normal mixing rounds take fixed denomination inputs and outputs, and group sends of unequal output values are are only constructed from mixed inputs.

5. Inputs with good anonymity set sizes can be given a negative fees, covering the output creation amount (limited to the first registered output from a previous mixing transaction). This would incentivize "switching network" mixing topologies, allowing already mixed coins to contribute more to the anonymity sets of newly mixed coins.

Anonymity Set for Output Linking Transactions

TBD. Work is ongoing to provide an improved set of anonymity set estimation metrics, to analyze the feasibiltity of removing the post-mix linking restriction, and to address some of the computational complexity of Boltzmann.

See previous revisions of this document for early notes (mostly incorrect and incoherent)

Links & References

• https://github.com/Samourai-Wallet/boltzmann
• Bitcoin Transactions & Privacy (part 1) : https://gist.github.com/LaurentMT/e758767ca4038ac40aaf
• Bitcoin Transactions & Privacy (part 2) : https://gist.github.com/LaurentMT/d361bca6dc52868573a2
• Bitcoin Transactions & Privacy (part 3) : https://gist.github.com/LaurentMT/e8644d5bc903f02613c6
• https://www.comsys.rwth-aachen.de/fileadmin/papers/2017/2017-maurer-trustcom-coinjoin.pdf
• https://github.com/AdamISZ/JMPrivacyAnalysis/blob/master/tumbler_privacy.md
• nopara73/ZeroLink#74 - unqeual input mixing
• https://github.com/zkSNACKs/WalletWasabi/issues/728 - improved anonymity set calculation
• https://github.com/zkSNACKs/WalletWasabi/issues/760 - group send proposal
• zkSNACKs/WalletWasabi#414 - schnorr blinding

JFC when will i learn to spell anonymity o_O

@Shabnam-Mir shared the knapsack mixing paper with me:

Our algorithm tries to split outputs so that different output sets can be constructed for the same input set. It achieves this by splitting a single output when two transactions are merged. The difference between the sum of the two sets is calculated and one coin of the larger set is split to produce this difference. The new coin with the value of the difference can then be added to the smaller set to produce a new set with the same sum as the originally larger set.
...
However, we notice, that it only decreases the linkability of input-output pairs and not the linkability of input-input pairs. The reason for this is, that our algorithm only produces new output sets with the same sum than existing output sets. Hence, only input sets with the same sum than without mixing will be found. It can be easily fixed by randomizing the input sets before applying the output splitting algorithm

When splitting or consolidating fixed denominations from a preferred value series, this property of a mixing transaction arises naturally so long as the sum amounts are of roughly the same magnitude.

Furthermore, with at least one round of mixing per fixed denomination as an intermediate stage, the search space extends to the space of all partitions of all inputs of the mixing mixing transactions. In other words, their computational hardness argument is extended to a potentially significantly larger set of inputs, when analyzing these multi-round transactions as a switching network topology.

for anyone reading the comments, note that as of revision 6 the section about the anonymity set size and entropy calculation has been removed due to improved understanding of the problem, they are planned to be reinstated later when progress has been made to formalize improved metrics.

this paper is about anonymity metrics. It may be helpful.