Do CoinJoin Mixes Really Require Equal Transaction Amounts for Privacy? Part Two: Knapsack

Although Satoshi Nakamoto’s white paper suggests that privacy was a design goal of the Bitcoin protocol, blockchain analysis can often break users’ privacy. This is a problem. Bitcoin users might not necessarily want the world to know where they spend their money, what they earn or how much they own, while businesses may not want to leak transaction details to competitors — to name some examples.

But there are solutions to regain privacy, like CoinJoin. Some of the most popular mixing solutions available today use this trick, including Wasabi Wallet (which leverages ZeroLink) and Samourai Wallet (which leverages Whirlpool). In both cases, users chop their coins into equal amounts to mix them with each other. Using equal amounts is considered a crucial step for the mix to be effective.

Part one of this miniseries covered a new mixing protocol in development for Bitcoin Cash called CashFusion, which challenges the assumption that equal amounts are necessary for a successful mix.

But even in 2017, in a paper analyzing the privacy of non-equal amount CoinJoins in depth, researchers from RWTH Aachen University and Karlsruhe Institute of Technology proposed a solution to gain privacy through CoinJoin without the need to use equal amounts: knapsack mixing.

Author’s note: If you do not know what a CoinJoin transaction is or why equal amounts are assumed necessary for mixing, you should first read part one of this miniseries — or at least read the first two sections of that article.

Mixing Versus Paying

As explained in part one of this miniseries, equal-amount Bitcoin mixing probably offers the best achievable privacy on the Bitcoin blockchain today. But it does leave users with unequal-change outputs. These don’t offer the same level of privacy and could even be a privacy risk. CashFusion could help deal with these unequal outputs.

But there’s another problem. The requirement to use equal amounts prevents users from making actual payments through CoinJoin transactions: It’s unlikely that a merchant would charge the exact amount required in the CoinJoin. So, instead, equal-amount CoinJoins are really only used for mixing*: Participants put funds in and get the same amount of funds back. Unfortunately, this means that mixing requires extra blockchain transactions, which cost transaction fees and time.

Researchers Felix Konstantin Maurer (of RWTH Aachen University), Till Neudecker and Martin Florian (both of Karlsruhe Institute of Technology) set out to solve this problem in their 2017 paper titled “Anonymous CoinJoin Transactions with Arbitrary Values.” They proposed a CoinJoin solution that could be useful for actual payments — that is, it uses unequal amounts — while still offering privacy.

Named after the knapsack problem, their solution is referred to as knapsack mixing.

Knapsack Mixing

Like CashFusion, the core idea behind knapsack mixing is to generate a CoinJoin transaction that can be puzzled together into several different configurations of potential original transactions. Different configurations would link different inputs to different outputs, thereby breaking the trail of coins on the blockchain.

Knapsack mixing achieves this by cutting the original outputs from the original transactions into smaller outputs for the CoinJoin transaction. Furthermore, it uses relatively simple tricks to ensure that the smaller outputs result in several potential configurations being possible.

Maurer, Neudecker and Florian’s paper includes three variants of knapsack mixing. The first variant is the most fleshed out in the white paper itself. The second and third versions are fairly similar, where the third version is really a superior version of the second version. (The authors of the paper only came up with the third version in a late stage of writing the paper; it would have probably been given a more prominent place in the study otherwise.)

Let’s look at the different variants.

Variant One

To explain the first variant of knapsack mixing, let’s take a CoinJoin example from the first article in this miniseries. Alice wants to pay Carol 3.2 coins and has two inputs worth 2.3 and 1.4 coins, respectively. Meanwhile, Bob wants to pay Dave 4 coins and has two inputs worth 3 and 2 coins, respectively.

Simplified, these transactions look like so:

2.3 + 1.4 = 3.2 + 0.5

and

3 + 2 = 4 + 1

(The 0.5 BTC and 1 BTC outputs are change.)

Merged together, the CoinJoin transaction would then look like so:

3 + 2.3 + 2 + 1.4 = 4 + 3.2 + 1 + 0.5

As pointed out in the previous article, the transactions were merged, but assuming you know that there are two payers, the amounts can be puzzled together in only one configuration: the original transactions. As such, it’s trivial to rediscover which inputs paid which outputs, defeating the point of making a CoinJoin.

Knapsack mixing changes this. In short, it uses the value difference between the two original transactions to split an original output from the biggest transaction into…

Article Source…