Summary
This PR implements BIP352 with scanning limited to full-nodes. Compared to #1765, an alternative scanning method called the “LabelSet approach” (initially [proposed by @w0xlt](/bitcoin-core-secp256k1/1765/#issuecomment-3592403663)) is used, with the primary goal of fixing the worst-case scanning attack, discovered and discussed at length in previous takes 3 and 4. In constrast to the previously used “BIP approach”, the scanning cost depends primarily on the number of labels (something the user can control and the module can set a limit on), rather than the number of transaction outputs (limited only by Bitcoin’s consensus rules, i.e. the block weight limit). See https://gist.github.com/theStack/25c77747838610931e8bbeb9d76faf78 for a high-level comparison between the two approaches with benchmarks, and a Python implementation based on secp256k1lab.
Pros and cons
Other than mitigating adversarial scanning scenarios, the LabelSet approach offers additional advantages:
- simpler API: passing an explicit list of labels to scan for is much simpler than having to maintain a label cache data structure and provide a callback function; passing the transaction outputs as raw 32-byte x-only pubkeys is also simpler for the user, as no prior
secp256k1_xonly_pubkey_parsecalls are needed anymore (see #1765 (comment) for more details about API and implementation between the two approaches) - faster also for the common case (i.e. no match), if the number of labels used is reasonably small, as recent benchmarks indicate (in theory, the LabelSet approach should be faster whenever the number of labels L is smaller than twice the number of the scanned tx’s taproot outputs N, i.e. if L < 2 * N).
- simpler implementation: scanning resembles the flow on the sender side (i.e. start with unlabeled public key, end with the taproot output), and there is no need to handle the missing y-parity information in x-only public keys (by trying both)
The main drawback of the LabelSet approach is that every additional label increases the scanning cost by at least one EC point addition. As a result, it is definitely not suitable for use cases that require a large number of labels.
Limiting the number of labels
To be on the safe side and still avoid the worst-case scanning attack, it was suggested to limit the number of supported labels in the module. Currently, this limit is not enforced in code; it only appears as a WARNING in the API header documentation, with the recommendation to not use more than 20 (that’s the number where the worst-case takes about a second on my machine, see benchmarks below). It is unclear whether this is sufficient. We may want to enforce a hard limit instead, or introduce a configurable limit (for example at compile time or via an API call). This would better communicate that using values outside the recommended range is done at the user’s own risk.
For a minimalist solution, one could in theory support only a single label for now. That’s of course very restrictive, but would still comply with the minimum BIP requirements (see https://github.com/bitcoin/bips/blob/fc00f51c229088c447b3694cca9bf14ace0e1a96/bip-0352.mediawiki?plain=1#L131). The advantage would be that it would result in the simplest possible API and implementation, and expectations would be very clearly expressed to the user, if the parameter might be even called e.g. change_label.
Benchmarks
Benchmarks have been updated to show average scenarios over a N/L matrix (N…number of tx outputs, L… number of labels) as well as the worst case scenario:
0$ ./build/bin/bench silentpayments
1Benchmark , Min(us) , Avg(us) , Max(us)
2
3silentpayments_scan_nomatch_N=10_L=0 , 41.1 , 41.1 , 41.2
4silentpayments_scan_nomatch_N=10_L=1 , 42.1 , 42.1 , 42.2
5silentpayments_scan_nomatch_N=10_L=2 , 43.1 , 43.2 , 43.2
6silentpayments_scan_nomatch_N=10_L=5 , 46.1 , 46.2 , 46.2
7silentpayments_scan_nomatch_N=10_L=10 , 51.6 , 51.6 , 51.7
8silentpayments_scan_nomatch_N=10_L=20 , 62.6 , 62.7 , 62.7
9silentpayments_scan_nomatch_N=10_L=50 , 96.4 , 96.5 , 96.6
10silentpayments_scan_nomatch_N=10_L=100 , 153.0 , 153.0 , 153.0
11
12silentpayments_scan_nomatch_N=100_L=0 , 43.5 , 43.5 , 43.5
13silentpayments_scan_nomatch_N=100_L=1 , 44.4 , 44.5 , 44.5
14silentpayments_scan_nomatch_N=100_L=2 , 45.5 , 45.5 , 45.5
15silentpayments_scan_nomatch_N=100_L=5 , 48.5 , 48.5 , 48.6
16silentpayments_scan_nomatch_N=100_L=10 , 53.9 , 54.0 , 54.0
17silentpayments_scan_nomatch_N=100_L=20 , 65.0 , 65.0 , 65.1
18silentpayments_scan_nomatch_N=100_L=50 , 99.0 , 99.0 , 99.1
19silentpayments_scan_nomatch_N=100_L=100 , 156.0 , 156.0 , 156.0
20
21silentpayments_scan_nomatch_N=2325_L=0 , 220.0 , 221.0 , 222.0
22silentpayments_scan_nomatch_N=2325_L=1 , 221.0 , 222.0 , 223.0
23silentpayments_scan_nomatch_N=2325_L=2 , 222.0 , 223.0 , 223.0
24silentpayments_scan_nomatch_N=2325_L=5 , 226.0 , 227.0 , 228.0
25silentpayments_scan_nomatch_N=2325_L=10 , 232.0 , 233.0 , 234.0
26silentpayments_scan_nomatch_N=2325_L=20 , 243.0 , 244.0 , 245.0
27silentpayments_scan_nomatch_N=2325_L=50 , 279.0 , 280.0 , 280.0
28silentpayments_scan_nomatch_N=2325_L=100, 339.0 , 339.0 , 340.0
29
30silentpayments_scan_worstcase_L=1 , 416567.0 , 416567.0 , 416567.0
31silentpayments_scan_worstcase_L=2 , 444503.0 , 444503.0 , 444503.0
32silentpayments_scan_worstcase_L=5 , 531165.0 , 531165.0 , 531165.0
33silentpayments_scan_worstcase_L=10 , 674923.0 , 674923.0 , 674923.0
34silentpayments_scan_worstcase_L=20 , 961857.0 , 961857.0 , 961857.0
35silentpayments_scan_worstcase_L=50 , 1820950.0 , 1820950.0 , 1820950.0
36silentpayments_scan_worstcase_L=100 , 3249931.0 , 3249931.0 , 3249931.0
History and details about the “BIP approach”
Prior takes of the “silentpayments” module (PRs #1471, #1519, #1698, #1765) implemented scanning for labels as suggested in BIP352 (the “BIP approach”): for each taproot output, subtract the unlabeled output candidate and check if the result is in a pre-calculated label cache. This method has the useful property of being performance-independent of the number of labels to scan for, as the lookups in the label cache are constant and fast, if implemented in a proper efficient data structure like a hash map (even hundreds of thousands of labels can be checked without a noticeable loss in performance, see the showcase in https://groups.google.com/g/bitcoindev/c/bP6ktUyCOJI/m/HGCF9YxNAQAJ).
One drawback of the BIP approach is that it scales poorly for pathological transactions containing a large number of outputs, all corresponding to Silent Payments recipients sharing the same scan key. In the worst-case scenario of a single, very large transaction filling an entire block (note that such a transaction would be non-standard, but still consensus-valid), scanning could take several minutes for the targeted recipient (see #1698#pullrequestreview-3341766084). Proposed mitigations in takes 3 and 4 that were based on the BIP approach turned out to be insufficient to fix the problem, and it is currently believed that this is an inherent problem that could only be solved by a protocol change (by e.g. limiting the Silent Payments eligible transactions to a smaller number of outputs).
Therefore, a different way of scanning has been proposed that works in the opposite direction: iterate over a list of explicitly passed labels, add the unlabeled output candidate and check if the result is in the list of taproot outputs (via binary search to be efficient), i.e. the “LabelSet approach”.
