Small Hamming Weight Denominations for CoinJoins

Standardizing on a small set of denominations has advantages, among other use cases, for privacy in CoinJoin transactions. Instead of creating a single output for an arbitrary amount, a wallet can approximate the amount from below by a sum of standard denominations, and create one output for each denomination in the sum. Each of these outputs is less linkable to the input cluster that funded it.

The fewer denominations there are to choose from, the more likely it is that more than one user chooses any given denomination, which improves privacy. The cost is that more outputs are needed to represent a given balance.

With too few denominations, the approximations also get worse. This notebook quantifies that trade-off. It takes denominations with Hamming weight 1, meaning values with a single nonzero digit in some base, such as powers of 2. It then measures the gaps between consecutive sums of up to $k$ such denominations. There are only $O(\log n)$ such values up to $n$ sats.

Sub-transaction model and implications for privacy

In the sub-transaction model (1, 2), for every repeated value with multiplicity $m$ in the inputs or the outputs of a sub-transaction mapping as a whole, $m!$ equivalent mappings can be obtained by permutation. Permuting coins of equal value does not change the sum of any sub-transaction, so it preserves the defining property of a sub-transaction: that its inputs minus its outputs sum to (approximately) zero. Permutations within a single sub-transaction do not change which sub-transaction any coin is assigned to, so they yield no new mappings.

In base 2, a value with multiplicity 2 within a single sub-transaction is exchangeable with the next denomination up from some other sub-transaction. Base 3 and 10 have somewhat more complex arithmetic relationships which imply yet more permutations of subsets of coins.

If an arbitrary output value (i.e. with large Hamming weight) can be constructed – or more generally than in Maurer et al, approximated – by summing together $k$ distinct denominations, and each of which has multiplicity $m$ in the outputs of the sub-transaction mapping as a whole, then the number of equivalent mappings is $k\times m!$. This counts permutations over sets of subsets of outputs, specifically when a subset of size $k$ is exchanged with a subset of size $1$.

Although this preserves the nominal sum of the sub-transaction, its weight, and therefore its implied fee rate, will differ. A high variance in the implied fee rates of sub-transactions is less likely, so unlike 1:1 exchanges, k:1 exchanges are not perfectly symmetric. Here a sub-transaction’s implied fee rate is the nominal sum of its inputs minus that of its outputs, divided by the weight of the sub-transaction. Users who attempt to recover every last sat are more susceptible to such analysis.

A partition of the inputs and outputs is only a valid sub-transaction mapping if each part’s outputs balance its inputs. When the coins form a dense subset sum instance, almost any group of inputs can be balanced by many groups of outputs, and vice versa. With multiplicities high enough that no single sub-transaction uses every copy of a denomination, the remaining coins stay dense after any one sub-transaction is set aside, so the same holds for the rest of the transaction. Every input and output therefore appears in many distinct sub-transactions across all non-derived mappings.

Radix CoinJoin

It follows that a logarithmic (in the range of values) number of small Hamming weight values with non-trivial multiplicity, taken from a geometric progression, can provide cover for any number of arbitrary valued inputs and outputs. Larger Hamming weight values with multiplicity 1 can of course contribute to subset sum density, but a geometric progression with high multiplicity is much more robust and trivial to analyze.

Ignoring any hypothetical UTXO sharing, the anonymity set size of a CoinJoin transaction is constrained by the number of inputs or the number of outputs (the smaller of the two). Even if the estimated number of distinct sub-transactions in which a coin appears is very large, this only means that the sub-transaction mappings will not be the limiting constraint on anonymity set size for this coin. Therefore even loose lower bounds on this value are sufficient in practice.

Mixed bases and preferred values

If using only a single base, when a small fee cost is subtracted from a single denomination this will result in a remaining balance with a large Hamming weight in that base. To get around this to some extent, values from multiple bases can be used. Additionally, not all Hamming weight 1 values are required, a preferred value series can approximate values well with a smaller number of denominations.

Currency conversions often result in excessively precise bitcoin amounts. In some base $b$, a value $v$ will have expected weight $\frac{(b-1){\log }_{b}v}{b}$. Values which have a small weight in one base usually have a large weight in another, in particular bases 2 and 3. The result of subtracting a value with weight 1 in base 3 from a value with a large weight in base 2 can often have a weight that is smaller by more than 1 (but it may also be higher).

Concretely, the 1-2-5 series in base 10 is useful for representing values with a decimal bias. Base 2 and 3 are suitable for decomposing arbitrary values with a high decimal Hamming weight. They are also complementary to each other: the 1-2 series in base 3 has a high Hamming weight in base 2 and powers of 2 have a high Hamming weight in base 3. These additional values also improve the overall density, reducing the sizes of combinations required for good approximations. Beyond this, additional denominations provide diminishing returns.

As we will see in detail, allowing more outputs improves the density of representable values. Coverage is denser in the interior of the range and becomes sparser towards the upper end, where combinations are limited by the largest available denomination. Raising this denomination limit can improve coverage in the upper region, but does not fill existing gaps between smaller values. With the parameters used here, some gaps still exceed the dust threshold even with six outputs.

This python implementation is optimized for simplicity, not performance or memory use, and the nature of this problem lends itself to precomputation. In an optimized implementation it’s possible to exhaustively enumerate all possibilities even as part of an online computation. This is worth noting because for privacy choosing uniformly at random between an unbiased selection of acceptable choices is better than always picking the best choice according to the cost function. A black box optimization approach may introduce such a bias depending on the cost function.

Parameters

The minimal feerate can be controlled in order to vary the dust threshold.

# bitcoin network parameters
max_sats = 2099999997690000
dust_feerate = 3.0
expected_feerate = 10.0
min_vbytes = 98 # 294 sats @ 3 sat/vb for p2wpkh per https://bitcoin.stackexchange.com/a/41082
dust = int(min_vbytes * dust_feerate)

We will generate denominations from the dust threshold to some maximum value. Setting a large max_denom smooths the gap distribution and emphasizes the gaps between the larger magnitude values, which tend to have smaller relative differences. max_combination_value cuts the sums off at a multiple of max_denom, because larger sums are less informative. A sum above $c$ times max_denom needs more than $c$ terms, since no term exceeds max_denom, so it effectively has fewer than $k$ free terms and the sumset is sparse there.

# denomination parameters
min_denom = dust
max_denom = int(1e8) # reducing this reveals some interesting structure in the plots below
max_combination_size = 6 # 7 is slow but doable, and consumes lots of ram for larger values of max_denom with this naive implementation. results are not very interesting, median gap size is 1 sat.
max_combination_value = max_denom * 2

The final parameters set a cutoff for the smallest gaps. The smallest possible gap is of size 1. Setting a higher cutoff omits negligible gaps (e.g. below dust) improving readability of the individual histograms with regard to larger gaps. Low values aid in comparing between sumset degrees.

# analysis parameters
min_diff = 2 # setting to dust hides small gaps, focusing on more significant ones
min_diff_ratio = 0 # 1e-4 is a basis point

Generate denominations

Denominations are based on preferred value series in base 2, 3, and 10.

# helper functions
def powers(b: int) -> set[int]:
  """
  Generates the powers of the given base up to the maximum denomination.
  Smaller powers are kept, since a multiple of one may still be large enough.
  """
  return { b**i for i in range(int(log(max_denom)/log(b))+1) }

def multiples(vs: set[int], cs: set[int]) -> set[int]:
  """
  Computes the products of pairs of values from two sets.
  """
  return { c*v for (c,v) in product(cs,vs) if c*v in range(min_denom, max_denom+1) }

# denominations of different bases
binary  = multiples(powers(2),  {1})
ternary = multiples(powers(3),  {1,2})
decimal = multiples(powers(10), {1,2,5})

# these additional Hamming weight 2 values plug the proportionally largest gaps
# between the denominations. this has some impact on the decomposition of smaller
# values (max_denom <= 1e6 or so) and so seem appropriate for a future with a
# lower dust feerate, but marginal benefit today

#binary = binary | multiples({3}, { 2**i for i in [ 10, 13, 15, 18 ]})

# the addition of 3 * 2^n arguably over-represents base 2 values
# https://en.wikipedia.org/wiki/Preferred_number#Computer_engineering

#binary  = multiples(powers(2), {1,3})

The combined set of denominations is just a union of these Hamming weight 1 values in these 3 useful bases.

# combined denomination set
combined = binary | ternary | decimal

Generate sumsets

{0} is unioned with the denominations in order to obtain the sumsets from combinations of size $\le k$ as opposed to $=k$.

# compute sumsets naively

sumsets = []
for k in range(1, max_combination_size+1):
  subsets = combinations_with_replacement({0} | combined, k)
  sumset = { s for s in map(sum, subsets) if s in range(1,max_combination_value+1) }
  sumsets.append(np.array(sorted(sumset)))

# compute gaps efficiently
gaps = []
for s in sumsets:
  diffs = np.diff(s)
  gaps.append(diffs[diffs >= min_diff])

For the relative gap size, omit gaps below the dust threshold. These gaps are negligible and unrecoverable (since an additional output has a cost), and are therefore noise. To improve clarity of the plots they are filtered out of the relative differences.

# compute normalized gaps efficiently

relative_gaps = []
for s in sumsets:
    diffs = np.diff(s)
    relative_diffs = diffs / s[1:]
    mask = (diffs >= dust) & (relative_diffs >= min_diff_ratio)
    relative_gaps.append(relative_diffs[mask])

Plots

Gaps

Count and sizes

Here we compare the gaps (ignoring gaps of size 1) of the sumsets of different degrees. As larger combinations are permitted the number of distinct sums grows and with them the number of gaps between these sums. Because these values are all in a fixed range, the sizes of the more numerous gaps of sumsets of higher degrees are of course smaller.

Note that for $k\in \{1,6\}$ the scatterplots are a little misleading. For $k=1$ there aren’t that many distinct values, so even though these values are smoothly distributed the quantile values aren’t. For $k=6$ several quantiles of the sumset are entirely gaps of size 1. The plot omits those gaps, so its lowest several quantiles are 2 and the next several are 3. The spacings of these in the scatter plot are a visual artifact arising from plotting integer values.

Gap sizes distribution

The next two plots show the gaps in more detail, both their sizes and their sizes in relation to the next larger value. When decomposing into low Hamming weight values, the total balance being decomposed may fall in one of these gaps. The distribution of their sizes bounds the loss from the decomposition. Here too small integer values create visual artifacts, the empty bins for $k>3$ are empty because the populated bins interspersing them correspond to successive integer values.

Relative gap size

The next plot displays gaps larger than the dust threshold as a fraction of the larger value. No quantization artifacts arise in this plot, but there is a cutoff imposed by dividing by values no larger than the maximum combination value.

Sums and combinations

Density of distinct sums

The next plot shows the density of distinct sums in the integers. The previous plots show the gap sizes over the entire range, but not all balances decompose as readily, and towards the end of the range the density tapers off (see max_combination_value parameter). The initial ramp up is determined by the size of the smallest denomination (see also dust_feerate parameter).

This plot gives a clearer indication of the expected loss as a function of the balance being decomposed into a sum of standard values. The distinct constructible sums are assigned into bins (ranges of natural numbers). To plot each bin, this number of distinct values is divided by the size of the bin (number of distinct values, or difference between smallest and largest values).

A density of 1 implies every possible integer value in the bin can be constructed exactly, and a density $\ge {\mathrm{dust}}^{-1}$ means every value can be approximated from below with error smaller than the dust threshold.

More intuitively, anything above the dashed line means values can be well approximated often enough that the loss is on average negligible (the cost of an additional output will be higher even at the minimum relay fee). The difference in costs will be linear in $k$, smaller combinations are more efficient representations of a given value but concrete efficiency depends on the feerate, and at higher feerates.

Distinct combinations vs. distinct sums

The following plot displays the possible combinations (as opposed to the distinct sums of the previous plot), which gives an indication for how many ways of constructing a possible sum there are as the combination size increases.