Mixing Unequal Inputs [CCJ Extensions]

[nopara73]

Related Issues: #73, #74, #75
Related Question: https://bitcoin.stackexchange.com/questions/73431/mixing-unequal-inputs
Non-entropist Approach Measuring Anonymity: https://www.freehaven.net/anonbib/cache/entropist.pdf
Knapsack Algorithm: https://www.comsys.rwth-aachen.de/fileadmin/papers/2017/2017-maurer-trustcom-coinjoin.pdf

If optimal algorithm is found CCJ can be extended to handle unequal CJ outputs the following way:

The difference is: Alice doesn't provide change and active CJ outputs right away, rather, the coordinator builds the mix when all the inputs are provided and gives the output amounts to Alice.
Unlike in my sloppy illustration, there are more things are happening here: These output amounts will be paired up with outputs (scriptPubKeys), and these pairs will be blinded one by one.
These pairs then will be sent to the coordinator, the coordinator signs them blindly and send back to Alice along with a flag. The flag tells Alice if she has to unblind and expose the output-value pair to the server or not. If Alice lied and blinded the incorrect amount she'll be banned. The point is: when Alice blinds, she doesn't know if the server will ask for the information back or not. (Mental note: this will result in many unused receive addresses to be generated.)
Finally Alice changes to many Bob identities, unblinds the signatures and proceeds with the CCJ protocol normally.

[nopara73]

The coordinator can also just simply have like a bunch of keys to sign with and for each session one key is assigned for output denomination. (Not randomly, otherwise the tumbler could cheat.)
In this case the client, when it knows all the outputs can check if the blinded output was signed with the right key or not.
So no need for all this zero knowledge protocol.

[nopara73]

Ethan's idea on slack:

1. Users submit inputs, blinded values
2. Tumbler signs blinded values without knowing what is in them, sends users blinded signatures
3. Users unblind signatures
4. Users then from a different IP address send signatures to tumbler with requested output and output amount
5. if sum of inputs != sum of outputs + fee, tumbler aborts, demands that users show what input they control to determine who was lieing
   Since users can always abort before signing coinjoin, this does not introduce any new aborts

[nopara73]

Other things those may be relevant:
ValueShuffle: https://eprint.iacr.org/2017/238.pdf
Fragmanted Transaction Protocol: https://www.student.cs.uwaterloo.ca/~eatounno/mw/tom_oct17.txt