SarangNoether
commented
5 years ago Output selection
Introduction For every output spent in a transaction, the wallet chooses a ring of 10 additional decoy outputs from the chain to use in a ring signature. Originally, the wallet chose these decoys uniformly from the chain. In later versions, it chose them from a modified triangular distribution. Since it is suspected that users generally spend newer outputs more often than older outputs, the wallet should select decoys from a distribution that matches the expected spend pattern.
Current approach Empirical studies on both Bitcoin and certain older Monero transactions suggest that a particular statistical distribution (call it exp-gamma) closely matches provable spend patterns. Currently, the wallet selects a block at random using exp-gamma, and then forms a small window of blocks around it; the size of the window depends on how many neighboring blocks are empty. It then selects an output uniformly from the window. This ensures that in general, newer outputs are more likely to be selected than older outputs.
Drawbacks Depending on transaction volume, it is often the case that there is large variability in the number of outputs contained in blocks. At the extreme, up to 25% of blocks at any given time may be empty, containing only a coinbase output. This variability means that the selection algorithm will choose outputs from smaller (in terms of outputs) blocks with higher probability than is expected. This is apparent when a transaction occurs whose input rings might contain many coinbase outputs.
An adversary analyzing the chain may develop a heuristic stating that a coinbase output appearing in a ring is a decoy, under the (currently unproven) assumption that coinbase outputs have a different spend pattern than non-coinbase outputs. A more clever adversary might develop more advanced statistical heuristics that account for the size of the block where an output was generated.
Goals We want to modify the wallet's output selection algorithm to more correctly account for variability in block sizes, while still staying true to the expected spend distributions known from empirical data. This will help to mitigate the types of analysis that could be useful to an adversary.
Outputs generated in neighboring blocks, regardless of the size of the blocks, should be selected with approximately the same probability once we account for the exp-gamma distribution. Further, outputs generated in the same block should all be selected with precisely the same probability, since these outputs have the same age.
Selection algorithms Here are four options for output selection, including the current one. Each has a short name so we can refer to it easily.
-
Partial window. This is the current approach, where the size of the window around the chosen block depends on whether or not adjacent blocks are empty or non-empty.
-
Full window. This is a slight modification to partial window, where the size of the window around the chosen block is fixed according to a given parameter.
-
Output lineup. In this approach, an exp-gamma selection is made on the entire list of outputs, ignoring the structure of blocks altogether. Once an output is selected, another uniform selection is made among all outputs in the block.
-
Biased lineup. In this approach, an exp-gamma selection is made on a block. A uniform selection is then made among all outputs from the tip of the chain to twice the age of the selected block.
Chain density Each of the output selection outputs is tested against several different chain densities (the distribution of the number of outputs per block).
-
Real. This uses actual Monero chain data for all post-RingCT blocks generated before 15 February 2019.
-
Geometric. This uses a geometric distribution to determine the number of outputs in each block.
-
Famine. This assumes that blocks newer than the exp-gamma mean (approximately 1.8 days) are all empty, and that older blocks are packed using a geometric distribution.
-
Feast. This assumes that blocks newer than the exp-gamma mean are all packed using a geometric distribution, and that older blocks are empty.
The last two models are extreme cases, intended to simulate different types of worst-case behaviors. The first two models are intended to simulate more typical chain conditions and transaction behavior.
Simulation method Each combination of selection algorithm and chain density is simulated using a chain consisting of 500000 blocks. After generating the chain, 10000 selections are made from the same point in time at the tip of the chain; that is, we assume that the chain does not grow as we make the selections.
We initially examine only two simple metrics.
-
Mean fraction. What fraction of selection block ages are less than the exp-gamma expected mean (approximately 1.8 days)?
-
Coinbase ratio. What fraction of selections are coinbase outputs? For comparison, the fraction of coinbase outputs appearing in the entire chain (which is independent of the selection algorithm and depends only on the chain density) is also provided.
All simulation Python code is available.
Results The following table shows the results of the two metrics for each combination of selection algorithm and chain density.
density selection mean coinbase (chain fraction)
-----------------------------------------------------
real partial 0.5509 0.1463 (0.0595)
full 0.5461 0.0913
lineup 0.5100 0.0804
bias 0.5456 0.0746
geom partial 0.5460 0.3166 (0.2493)
full 0.5421 0.2767 (0.2500)
lineup 0.5276 0.2564 (0.2496)
bias 0.5521 0.2491 (0.2504)
famine partial 0.5379 0.6872 (0.2502)
full 0.5372 0.6601 (0.2500)
lineup 0.3405 0.5114 (0.2499)
bias 0.5289 0.6221 (0.2512)
feast partial 0.5424 0.6279 (0.9924)
full 0.5480 0.6052 (0.9920)
lineup 0.7378 0.4454 (0.9919)
bias 0.5420 0.4817 (0.9921)
b-g-goodell
SamsungGalaxyPlayer
RandomRun
binaryFate
Join in for the weekly Monero Research Lab meeting.
When: Monday, 25 February 2019 @ 17:00 UTC Where: #monero-research-lab (freenode/matrix)
Agenda
Greetings
Output selection a. Selection algorithm b. Requirements (if any) for coinbase
Other work a. Sarang b. Surae c. Others?
Questions
Action items