This document compares the theoretical scanning cost differences for silent payments depending on whether the "BIP style" or "LabelSet" algorithm is used. It is assumed that we primarily care about the upper bound of the scanning cost. In almost all cases this is a block filled with silent payment eligible transactions. The one exception is the case where a single user is being targeted under the BIP style algorithm, in which case the worst-case shifts to a block with a maximum number of outputs.
Summary
- BIP style scanning speed is fairly consistent throughout
- While LabelSet is slightly faster at low label usage, it gets significantly slower as label use increases
- The BIP style targeted worst-case can be effectively mitigated by limiting the number of outputs to the same recipient
Theoretical numbers for block scanning
General observations
- With a minimum number of labels, the cost of the ECC mults generally overshadows the cost of either algorithm
- With a minimum number of labels, LabelSet is 6% faster for a block with a maximum number of transactions (the general worst-case)
- At 12 labels, BIP style starts overtaking LabelSet
- For more normal block compositions this is 10% and 19 labels, respectively
- At 395 labels, LabelSet is 3.3x slower, and at 58k labels almost 360x slower
- Unless you are targeted, a block that maximizes the number of outputs over the number of transactions is always faster to scan (no ECC multiplications)
Theoretical numbers for targeted attack
Observations about targeted attack
- When targeted under BIP style, the theoretical worst case is almost 360x slower than the general worst-case
- If we limit the number of outputs per recipient (K) to 100, it's only 3.3x slower, and 31x at K = 1000 (close to linear)
- Performance wise, targeted BIP style K = 100 is equal to general LabelSet L = 395, and K = 1000 is equal to L = 58k
Numbers explained
- All percentages are comparative to the baseline, which is the BIP style approach with a general worst-case block
- 4700 is the rough maximum number of Silent Payments eligible transactions (single input and output)
- A standard block was assumed to have 3500 transactions and 5500 outputs
- 23250 is the rough maximum number of taproot outputs that can fit in a transaction (filling an entire block)
- Label counts were chosen to get LabelSet percentages that equal certain BIP style percentages for comparison
Formulas explained
- T*150 represents the ECC multiplications required for Silent Payments - one mult by G is estimated at 50 ops (=ECC additions or subtractions), and one mult by an arbitrary point at 100, so 150 total
- N*12 first has a cost of 10 ops per output to calculate the Y coordinate, and another 2 ops to account for the fact that it's not known whether Y is even or odd (so 12 total)
- N*N/2 involves randomization and the removal of checked outputs, otherwise it would be N*N (the N*10 Y calculations are left out due to being negligible)
- (K+10)*N involves randomization only - removal is ineffective for cases where N is significantly larger than K (includes N*10 Y calculations)
Thanks to theStack and Eunovo for all the discussions that helped establish the numbers and formulas, and w0xlt for the benchmarks that motivated it
My more opiniated view on how these numbers should inform our decisions can be found here.