Avoid selecting coinbase outputs as decoys

Summary

This issue is for discussing a potentially privacy-improving decoy selection rule for ring signatures that would entirely avoid using any coinbase outputs as decoys.

p2pool Coinbase Transactions

Most, if not all, coinbase transactions produced by centralized mining pools or solo miners have a single output. Therefore, these outputs occur once per block. The probability that they would be included in any given transaction's ring is low.

p2pool coinbase transactions split the block reward among dozens and sometimes hundred of miners, producing dozens or hundreds of outputs in each p2pool block that are small in value. I wrote an R script that calculates the number of p2pool outputs for any interval of time.

The numbers for Sept. 28 2022 to December 27, 2022 (block heights 2721396 to 2786779) are:

Total number of blocks: 65384
Number of blocks found by p2pool: 4540 (6.94% of total)
Summary statistics on number of payout outputs per block found by p2pool:
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
   66.0   104.0   113.0   128.4   122.0   615.0 
Total number of transaction outputs: 4,123,336
Number of p2pool payout transaction outputs: 582,919 (14.14% of total)

Privacy Risk of Status Quo

Given that 14 percent of all outputs are p2pool payouts, we can approximate the probability of any given ring selecting a certain number of p2pool outputs as decoys by computing the probability density function of a Binomial(15, 0.14) distribution (under some mild simplifying assumptions).

A simple R script to calculate:

for (i in 0:15) {
cat("Probability that a ring has ",
  formatC(i, width = 2),
  " p2pool coinbase outputs as decoys: ",
  formatC(round(dbinom(i, size = 15, prob = 0.14) * 100, 3), digits = 3, width = 6, format = "f"),
  " % \n", sep = "")
}

which produces:

Probability that a ring has  0 p2pool coinbase outputs as decoys: 10.411 % 
Probability that a ring has  1 p2pool coinbase outputs as decoys: 25.421 % 
Probability that a ring has  2 p2pool coinbase outputs as decoys: 28.968 % 
Probability that a ring has  3 p2pool coinbase outputs as decoys: 20.435 % 
Probability that a ring has  4 p2pool coinbase outputs as decoys:  9.980 % 
Probability that a ring has  5 p2pool coinbase outputs as decoys:  3.574 % 
Probability that a ring has  6 p2pool coinbase outputs as decoys:  0.970 % 
Probability that a ring has  7 p2pool coinbase outputs as decoys:  0.203 % 
Probability that a ring has  8 p2pool coinbase outputs as decoys:  0.033 % 
Probability that a ring has  9 p2pool coinbase outputs as decoys:  0.004 % 
Probability that a ring has 10 p2pool coinbase outputs as decoys:  0.000 % 
Probability that a ring has 11 p2pool coinbase outputs as decoys:  0.000 % 
Probability that a ring has 12 p2pool coinbase outputs as decoys:  0.000 % 
Probability that a ring has 13 p2pool coinbase outputs as decoys:  0.000 % 
Probability that a ring has 14 p2pool coinbase outputs as decoys:  0.000 % 
Probability that a ring has 15 p2pool coinbase outputs as decoys:  0.000 %

Between one and three decoys are usually wasted on p2pool coinbase outputs. This means that effective ring size is usually 15 - 13 rather than the intended 16.

In most transactions, p2pool outputs can be ruled out as the real spend because p2pool miners need to consolidate their payouts in transactions with a large number of inputs. Furthermore, the miners' addresses are in plaintext on the p2pool side chain, observable by Monero privacy adversaries. @SChernykh can discuss the issue in greater detail.

Implementation

This change would not require a network upgrade (hard fork) because decoy selection is not enforced by any blockchain consensus rules. This would be a change at the wallet software level.

It would make the most sense to implement this in production code at the same time that the decoy selection changes of OSPEAD are implemented, assuming that OSPEAD passes review. Simultaneous implementation would avoid creating yet another "anonymity puddle" where users who are slow to update their software are transacting with diverse versions of the decoy selection algorithm.

With this wallet-level change, when a miner spends a coinbase output, the coinbase output would still be included in the ring. It would be obvious to observers that the miner's coinbase output is the real spend in that ring. The behavior could be changed by #108

monero-project / research-lab