This article is a light exploration and discussion of ideas by Yuval Kogman.
Bitcoin Transaction
You got 50 bitcoins from a friend and 23 from another. But now you want to spend 73 bitcoins on alpaca socks. So you create a transaction:
This Bitcoin transaction has 2 inputs and 1 output. However it’s unlikely you’ll have a coin composition that adds up exactly to your desired spend amount. What if you’d want to only spend 72 BTC?
In that case you’ll create an extra output to yourself. This is called the UTXO model. This is how Bitcoin works.
Coinjoin
Someone else in the world also wants to make a Bitcoin transaction.
Coinjoins are what the name suggest: you’re gonna join your coins together with someone else.
This is all nice and well, but there’s a privacy issue. From an outside observer’s perspective, this transaction can only mean 2 things: all the inputs belong to the same user, or it can be decomposed to two sub transactions by examining the amounts.
Equal Amount Coinjoins
To solve the privacy issues let’s create equal amount coinjoins where all the users are self spending in a coinjoin before an actual spending transactions would take place.
In this transaction every user gets back 1 BTC.
Powers of 2 Coinjoins
Ascending
Notice we could achieve more efficient mixes by introducing multiple denominations. We may chose powers of 2 as that results in the smallest number denominations those can be decomposed from each other.
This way the mixes are more blockspace efficient, but we can do even more. Let’s turn it upside down!
Descending
Coin Selection
You have many coins in your wallet. Which ones should you select for mixing? What if you know the currently registered input set and make your decision accordingly?
Assume you know 3, 5 and 7 are already registered and you have coins to choose from: 3, 10 and 13. Which one would you ideally register for this coinjoin? 3 seems intuitively correct, but let’s examine this deeper.
Binary Representation
Amounts can be represented in binary.
Hamming Weight
Hamming weight of an integer is the number of 1s in its binary representation.
Notice the hamming weight is also the number of outputs those would be created in descending powers of 2 coinjoins.
Counting 1s
For fun I’m going to count the 1s in our coinjoin:
What I can notice with this exercise is that there’re zero 8 BTC outputs, two 4 BTC outputs, two 2 BTC outputs and three 1 BTC outputs.
Putting It All Together
One could intuitively come up with many coin selection strategies with the discussed binary representation insights, but I think the most important ones would first and foremost try to avoid unmixed changes, then minimize the number of outputs.
- To ensure minimum anonymity (by avoiding unmixed changes) a wallet could select coins those have all their
1s covered by the mix’s already registered inputs. - To minimize costs (by minimizing the number of outputs) a wallet could select from the remaining coins with the lowest hamming weight.
Coin Merge
Coin merging is a dirty business, but wallets are getting bloated all the time and everyone will eventually have to do it. How? In coinjoins it’s more private than in normal transactions.
The disadvantage of it is that your coin merging makes your input decompositions unknown in advance, which can lead to accidental change coin generation by others.
However the benefit is that one can significantly improve mixing costs by merging coins those sum would result in low hamming weights .
In Conclusion
Some assumptions made here are based on intuition and experience and if we’d to do anything with them, we’d have to have sound reasoning to build on top of them, but for now I had to dump my mind here, because I would hate to forget all this.
