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.
- 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
- 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/current block compositions this is 16% and 31 labels, respectively
- At 135 labels, LabelSet is 1.8x slower, and at 2463 labels 16x 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
- When targeted under BIP style, the theoretical worst case with an unbounded K (= 23255) is 187x slower than the general worst-case
- If we limit the number of outputs per recipient (K) to 100, it's only 1.7x slower, 16x at K = 1000, and 37x at K = 2325 (close to linear)
- Performance wise, targeted BIP style K = 100 is equal to general LabelSet L = 135, and K = 1000 is equal to L = 2463 (and while not shown in table, block size bounded K = 23255 is equal to L = 30k)
- All percentages are comparative to the baseline, which is the BIP style approach with a general worst-case block
- 8986 is the maximum number of Silent Payments eligible transactions (single input and output)
- A standard block is assumed to have 3143 transactions and 8172 outputs (the mean from the past six months, as calculated by Novo)
- 23255 is the 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
- 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)
- Conversion between affenine and Jacobian is currently not taken into account and may affect accuracy
Thanks to theStack and Eunovo for all the discussions that helped establish the numbers and formulas, and w0xlt for the benchmarks that motivated it
2026-02-25: The output and transaction counts for blocks were too low in some cases. The main difference is that the general worst-case was actually worse than previously calculated, which causes the targeted worst-case to look less bad in comparison by about 2x (significant, but not enough to change any conclusions). It also makes the LabelSet approach a bit faster for normal blocks, but the difference isn't huge. All other statistics remain unaffected. Some small clarifications were also added.
My more opiniated view on how these numbers should inform our decisions can be found here.