Descending Powers of 2 Coinjoins

This article is a light exploration and discussion of ideas by Yuval Kogman.

Bitcoin 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

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

In this transaction every user gets back 1 BTC.

Powers of 2 Coinjoins

Ascending

This way the mixes are more blockspace efficient, but we can do even more. Let’s turn it upside down!

Descending

Coin Selection

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

Hamming Weight

Notice the hamming weight is also the number of outputs those would be created in descending powers of 2 coinjoins.

Counting 1s

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

  1. 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.
  2. To minimize costs (by minimizing the number of outputs) a wallet could select from the remaining coins with the lowest hamming weight.

Coin Merge

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