Descending Powers of 2 Coinjoins
This article is a light exploration and discussion of ideas by Yuval Kogman.
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
In that case you’ll create an extra output to yourself. This is called the UTXO model. This is how Bitcoin works.
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
Powers of 2 Coinjoins
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!
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
7 are already registered and you have coins to choose from:
13. Which one would you ideally register for this coinjoin?
3 seems intuitively correct, but let’s examine this deeper.
Amounts can be represented in binary.
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.
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 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 .
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.
by the author.