Descending Powers of 2 Coinjoins

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:

Image for post

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?

Image for post

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.

Image for post

Coinjoins are what the name suggest: you’re gonna join your coins together with someone else.

Image for post

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.

Image for post

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.

Image for post

Image for post

In this transaction every user gets back 1 BTC.

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.

Image for post

Image for post

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

Image for post

Image for post

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?

Image for post

Assume you know 35 and 7 are already registered and you have coins to choose from: 310 and 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.

Image for post

Hamming weight of an integer is the number of 1s in its binary representation.

Image for post

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:

Image for post

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.

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.

  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

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.

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.