Last active
December 9, 2025 07:26
-
-
Save theStack/25c77747838610931e8bbeb9d76faf78 to your computer and use it in GitHub Desktop.
Different approaches for scanning in Silent Payments (BIP-352)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| Different approaches for scanning in Silent Payments (BIP-352) | |
| ============================================================================================= | |
| ===== "calculate label candidates for each tx output, look them up in the labels cache" ===== | |
| ============================================================================================= | |
| The current approach for scanning in secp #1765 is as follows, following BIP-352: | |
| For each k value, derive the unlabeled output candidate P_k, then loop over the | |
| transaction x-only outputs linearly to check whether there is either a unlabeled or a | |
| labeled match. For the latter, two label candidates are calculated for each transaction | |
| output (necessary as we don't know the correct Y coordinate for x-only outputs), that are | |
| checked against the labels cache each to see if there is a match: | |
| ------------------------------------------------------------ | |
| for k = 0..: | |
| derive P_k | |
| for tx_output in tx_outputs: | |
| if pk_xonly(P_k) == tx_output: | |
| UNLABELED_MATCH | |
| label_candidate1 = pk_even(tx_output) - P_k | |
| label_candidate2 = pk_odd(tx_output) - P_k | |
| if any of label_candidate{1,2} in labels_cache: | |
| LABELED_MATCH | |
| abort scanning if there was no match | |
| ------------------------------------------------------------ | |
| For scanning a transaction that doesn't have any matches (the common case), there are | |
| 2 * N_OUTPUTS point additions needed for labels scanning, independent on the number of | |
| different labels to scan for. | |
| ======================================================================================== | |
| ===== "calculate output candidates for each label, look them up in the tx outputs" ===== | |
| ======================================================================================== | |
| Alternative approach (as proposed by w0xlt): | |
| For each k value, derive the unlabeled output candidate P_k (that part is still the same). | |
| Instead of looping linearly over all the transaction outputs and calculating label | |
| candidates for each of them, let the user supply all the label public keys to scan for, | |
| and calculate the output candidate from that, then look for each label if there is a match: | |
| ------------------------------------------------------------ | |
| for k = 0..: | |
| derive P_k | |
| if pk_xonly(P_k) in tx_outputs: | |
| UNLABELED_MATCH | |
| for label_pubkey in user_supplied_labels: | |
| output_candidate = P_k + label_pubkey | |
| if pk_xonly(output_candidate) in tx_outputs: | |
| LABELED_MATCH | |
| abort scanning if there was no match | |
| ------------------------------------------------------------ | |
| The lookup in tx_outputs can be sped up by using binary search (relevant for worst-case | |
| scanning attack). For scanning a transaction that doesn't have any matches (the common | |
| case), there are N_LABELS point additions needed for labels scanning. | |
| Especially for users with a small number of used labels (i.e. only the label for change | |
| outputs is used, i.e. N_LABELS = 1), the second approach seems significanly faster than | |
| the original one, considering that most Silent Payments eligible transactions will likely have | |
| at least two outputs to scan for. As the number of labels to scan for increases, the first | |
| approach is likely faster. | |
| Any thoughts on this? Did I miss anything? |
Author
@theStack Thanks for improving the benchmarking method — it’s much more accurate now.
I ran it on my machine and got the following numbers (with batch inversion):
Click to expand
Benchmark , Min(us) , Avg(us) , Max(us)
sp_full_scan_BIP-algo_L=0_N=2 , 33.3 , 33.3 , 33.4
sp_full_scan_BIP-algo_L=0_N=5 , 33.4 , 33.4 , 33.5
sp_full_scan_BIP-algo_L=0_N=10 , 33.5 , 33.6 , 33.6
sp_full_scan_BIP-algo_L=0_N=20 , 33.6 , 33.7 , 33.8
sp_full_scan_BIP-algo_L=0_N=50 , 33.8 , 33.9 , 34.0
sp_full_scan_BIP-algo_L=0_N=100 , 34.3 , 34.3 , 34.3
sp_full_scan_BIP-algo_L=0_N=200 , 35.1 , 35.2 , 35.3
-----
sp_full_scan_BIP-algo_L=1_N=2 , 37.0 , 37.1 , 37.1
sp_full_scan_BIP-algo_L=1_N=5 , 42.6 , 42.8 , 42.8
sp_full_scan_BIP-algo_L=1_N=10 , 52.4 , 52.4 , 52.5
sp_full_scan_BIP-algo_L=1_N=20 , 72.1 , 72.2 , 72.4
sp_full_scan_BIP-algo_L=1_N=50 , 130.0 , 131.0 , 131.0
sp_full_scan_BIP-algo_L=1_N=100 , 228.0 , 228.0 , 229.0
sp_full_scan_BIP-algo_L=1_N=200 , 423.0 , 424.0 , 424.0
-----
sp_full_scan_BIP-algo_L=2_N=2 , 37.0 , 37.1 , 37.1
sp_full_scan_BIP-algo_L=2_N=5 , 42.7 , 42.8 , 43.1
sp_full_scan_BIP-algo_L=2_N=10 , 52.4 , 52.5 , 52.6
sp_full_scan_BIP-algo_L=2_N=20 , 72.2 , 72.3 , 72.3
sp_full_scan_BIP-algo_L=2_N=50 , 131.0 , 131.0 , 131.0
sp_full_scan_BIP-algo_L=2_N=100 , 228.0 , 228.0 , 228.0
sp_full_scan_BIP-algo_L=2_N=200 , 424.0 , 428.0 , 435.0
-----
sp_full_scan_BIP-algo_L=3_N=2 , 37.4 , 37.9 , 38.8
sp_full_scan_BIP-algo_L=3_N=5 , 43.2 , 44.1 , 45.9
sp_full_scan_BIP-algo_L=3_N=10 , 52.5 , 54.5 , 55.8
sp_full_scan_BIP-algo_L=3_N=20 , 74.7 , 75.4 , 76.3
sp_full_scan_BIP-algo_L=3_N=50 , 136.0 , 137.0 , 139.0
sp_full_scan_BIP-algo_L=3_N=100 , 229.0 , 231.0 , 235.0
sp_full_scan_BIP-algo_L=3_N=200 , 439.0 , 442.0 , 449.0
-----
sp_full_scan_BIP-algo_L=5_N=2 , 40.1 , 40.5 , 40.9
sp_full_scan_BIP-algo_L=5_N=5 , 45.9 , 46.5 , 46.9
sp_full_scan_BIP-algo_L=5_N=10 , 56.1 , 56.5 , 57.0
sp_full_scan_BIP-algo_L=5_N=20 , 77.2 , 77.8 , 78.5
sp_full_scan_BIP-algo_L=5_N=50 , 137.0 , 138.0 , 138.0
sp_full_scan_BIP-algo_L=5_N=100 , 229.0 , 232.0 , 235.0
sp_full_scan_BIP-algo_L=5_N=200 , 425.0 , 437.0 , 444.0
-----
sp_full_scan_BIP-algo_L=10_N=2 , 39.7 , 39.9 , 40.0
sp_full_scan_BIP-algo_L=10_N=5 , 45.9 , 46.0 , 46.1
sp_full_scan_BIP-algo_L=10_N=10 , 56.1 , 56.3 , 56.4
sp_full_scan_BIP-algo_L=10_N=20 , 76.1 , 77.0 , 78.5
sp_full_scan_BIP-algo_L=10_N=50 , 136.0 , 138.0 , 139.0
sp_full_scan_BIP-algo_L=10_N=100 , 236.0 , 244.0 , 248.0
sp_full_scan_BIP-algo_L=10_N=200 , 442.0 , 453.0 , 461.0
-----
sp_full_scan_BIP-algo_L=20_N=2 , 39.7 , 40.0 , 40.5
sp_full_scan_BIP-algo_L=20_N=5 , 45.7 , 45.7 , 45.8
sp_full_scan_BIP-algo_L=20_N=10 , 55.8 , 56.0 , 56.2
sp_full_scan_BIP-algo_L=20_N=20 , 75.0 , 75.7 , 77.2
sp_full_scan_BIP-algo_L=20_N=50 , 133.0 , 135.0 , 135.0
sp_full_scan_BIP-algo_L=20_N=100 , 229.0 , 232.0 , 235.0
sp_full_scan_BIP-algo_L=20_N=200 , 431.0 , 438.0 , 445.0
-----
sp_full_scan_BIP-algo_L=50_N=2 , 40.4 , 40.8 , 41.6
sp_full_scan_BIP-algo_L=50_N=5 , 46.1 , 46.2 , 46.3
sp_full_scan_BIP-algo_L=50_N=10 , 56.3 , 56.4 , 56.4
sp_full_scan_BIP-algo_L=50_N=20 , 77.4 , 77.5 , 77.7
sp_full_scan_BIP-algo_L=50_N=50 , 138.0 , 139.0 , 139.0
sp_full_scan_BIP-algo_L=50_N=100 , 242.0 , 246.0 , 261.0
sp_full_scan_BIP-algo_L=50_N=200 , 441.0 , 443.0 , 444.0
-----
sp_full_scan_LabelSet-algo_L=0_N=2 , 35.8 , 35.9 , 36.1
sp_full_scan_LabelSet-algo_L=0_N=5 , 35.9 , 36.1 , 36.5
sp_full_scan_LabelSet-algo_L=0_N=10 , 36.2 , 36.4 , 36.7
sp_full_scan_LabelSet-algo_L=0_N=20 , 37.2 , 37.3 , 37.5
sp_full_scan_LabelSet-algo_L=0_N=50 , 40.5 , 40.6 , 40.8
sp_full_scan_LabelSet-algo_L=0_N=100 , 47.8 , 48.0 , 48.4
sp_full_scan_LabelSet-algo_L=0_N=200 , 64.6 , 65.2 , 65.8
-----
sp_full_scan_LabelSet-algo_L=1_N=2 , 37.0 , 37.0 , 37.2
sp_full_scan_LabelSet-algo_L=1_N=5 , 37.1 , 37.3 , 37.5
sp_full_scan_LabelSet-algo_L=1_N=10 , 37.3 , 37.4 , 37.6
sp_full_scan_LabelSet-algo_L=1_N=20 , 38.1 , 38.4 , 38.9
sp_full_scan_LabelSet-algo_L=1_N=50 , 41.8 , 41.9 , 42.1
sp_full_scan_LabelSet-algo_L=1_N=100 , 48.9 , 49.1 , 49.3
sp_full_scan_LabelSet-algo_L=1_N=200 , 65.5 , 65.8 , 66.5
-----
sp_full_scan_LabelSet-algo_L=2_N=2 , 37.2 , 37.3 , 37.4
sp_full_scan_LabelSet-algo_L=2_N=5 , 37.3 , 37.4 , 37.5
sp_full_scan_LabelSet-algo_L=2_N=10 , 37.6 , 37.7 , 37.7
sp_full_scan_LabelSet-algo_L=2_N=20 , 38.4 , 38.5 , 38.6
sp_full_scan_LabelSet-algo_L=2_N=50 , 41.9 , 42.3 , 42.7
sp_full_scan_LabelSet-algo_L=2_N=100 , 49.1 , 49.2 , 49.3
sp_full_scan_LabelSet-algo_L=2_N=200 , 66.0 , 66.8 , 67.5
-----
sp_full_scan_LabelSet-algo_L=3_N=2 , 37.3 , 37.4 , 37.6
sp_full_scan_LabelSet-algo_L=3_N=5 , 37.4 , 37.6 , 38.0
sp_full_scan_LabelSet-algo_L=3_N=10 , 37.7 , 37.9 , 38.0
sp_full_scan_LabelSet-algo_L=3_N=20 , 38.7 , 38.8 , 39.1
sp_full_scan_LabelSet-algo_L=3_N=50 , 42.3 , 42.6 , 42.9
sp_full_scan_LabelSet-algo_L=3_N=100 , 49.4 , 49.6 , 49.9
sp_full_scan_LabelSet-algo_L=3_N=200 , 65.8 , 66.1 , 66.6
-----
sp_full_scan_LabelSet-algo_L=5_N=2 , 37.6 , 37.7 , 37.8
sp_full_scan_LabelSet-algo_L=5_N=5 , 37.8 , 37.9 , 37.9
sp_full_scan_LabelSet-algo_L=5_N=10 , 38.2 , 38.2 , 38.2
sp_full_scan_LabelSet-algo_L=5_N=20 , 39.0 , 39.1 , 39.2
sp_full_scan_LabelSet-algo_L=5_N=50 , 42.5 , 42.7 , 43.0
sp_full_scan_LabelSet-algo_L=5_N=100 , 49.6 , 49.7 , 49.7
sp_full_scan_LabelSet-algo_L=5_N=200 , 66.1 , 66.2 , 66.4
-----
sp_full_scan_LabelSet-algo_L=10_N=2 , 38.5 , 38.6 , 38.8
sp_full_scan_LabelSet-algo_L=10_N=5 , 39.1 , 39.3 , 39.6
sp_full_scan_LabelSet-algo_L=10_N=10 , 39.4 , 39.6 , 39.9
sp_full_scan_LabelSet-algo_L=10_N=20 , 40.1 , 40.3 , 40.5
sp_full_scan_LabelSet-algo_L=10_N=50 , 43.8 , 44.1 , 44.2
sp_full_scan_LabelSet-algo_L=10_N=100 , 50.9 , 50.9 , 51.0
sp_full_scan_LabelSet-algo_L=10_N=200 , 67.6 , 67.9 , 68.3
-----
sp_full_scan_LabelSet-algo_L=20_N=2 , 40.7 , 40.8 , 41.1
sp_full_scan_LabelSet-algo_L=20_N=5 , 40.8 , 41.0 , 41.2
sp_full_scan_LabelSet-algo_L=20_N=10 , 41.4 , 41.5 , 41.6
sp_full_scan_LabelSet-algo_L=20_N=20 , 42.5 , 42.6 , 42.6
sp_full_scan_LabelSet-algo_L=20_N=50 , 46.1 , 46.2 , 46.3
sp_full_scan_LabelSet-algo_L=20_N=100 , 53.3 , 53.4 , 53.6
sp_full_scan_LabelSet-algo_L=20_N=200 , 70.4 , 70.5 , 70.7
-----
sp_full_scan_LabelSet-algo_L=50_N=2 , 47.3 , 47.4 , 47.6
sp_full_scan_LabelSet-algo_L=50_N=5 , 47.9 , 48.2 , 48.9
sp_full_scan_LabelSet-algo_L=50_N=10 , 48.6 , 48.8 , 49.1
sp_full_scan_LabelSet-algo_L=50_N=20 , 50.1 , 50.2 , 50.2
sp_full_scan_LabelSet-algo_L=50_N=50 , 54.2 , 54.3 , 54.6
sp_full_scan_LabelSet-algo_L=50_N=100 , 61.5 , 61.7 , 62.1
sp_full_scan_LabelSet-algo_L=50_N=200 , 78.5 , 78.6 , 78.8
Given the results, it looks like in practical wallet scenarios—if a wallet uses labels at all—and it is scanning typical transactions (say N ≥ 2–4) or whole blocks with many outputs, the label-set approach might be the better default. This seems especially true for rescans, where lots of “no matches” cases are expected.
But if we don’t want to maintain a label set structure, then the BIP352-style callback remains the only option anyway.
Just for analysis purposes, I implemented a version that unifies both algorithms. The parameter struct looks like this:
typedef struct {
/* Optional precomputed label set (used by the label-set scanning approach). */
const secp256k1_silentpayments_label_set *label_set;
/* Optional callback-based label lookup (BIP352 approach). */
secp256k1_silentpayments_label_lookup label_lookup;
const void *label_context;
} secp256k1_silentpayments_labels;The unified version is:
The benchmark is shown below. It appears to achieve fast scan performance in most practical and adversarial cases.
Click to expand
Benchmark , Min(us) , Avg(us) , Max(us)
sp_full_scan_L=0_N=2 , 33.3 , 33.5 , 33.7
sp_full_scan_L=0_N=5 , 33.4 , 33.5 , 33.5
sp_full_scan_L=0_N=10 , 33.4 , 33.5 , 33.5
sp_full_scan_L=0_N=20 , 33.5 , 33.6 , 33.7
sp_full_scan_L=0_N=50 , 33.8 , 33.8 , 33.9
sp_full_scan_L=0_N=100 , 34.3 , 34.3 , 34.5
sp_full_scan_L=0_N=200 , 35.2 , 35.3 , 35.4
-----
sp_full_scan_L=1_N=2 , 34.3 , 34.4 , 34.5
sp_full_scan_L=1_N=5 , 34.5 , 34.5 , 34.5
sp_full_scan_L=1_N=10 , 34.8 , 34.8 , 34.9
sp_full_scan_L=1_N=20 , 35.6 , 35.7 , 35.8
sp_full_scan_L=1_N=50 , 38.7 , 38.9 , 39.0
sp_full_scan_L=1_N=100 , 45.3 , 45.4 , 45.5
sp_full_scan_L=1_N=200 , 60.6 , 60.8 , 60.9
-----
sp_full_scan_L=2_N=2 , 34.6 , 34.7 , 34.7
sp_full_scan_L=2_N=5 , 34.7 , 34.8 , 34.9
sp_full_scan_L=2_N=10 , 35.1 , 35.1 , 35.2
sp_full_scan_L=2_N=20 , 35.9 , 36.0 , 36.0
sp_full_scan_L=2_N=50 , 39.1 , 39.1 , 39.2
sp_full_scan_L=2_N=100 , 45.6 , 45.7 , 45.9
sp_full_scan_L=2_N=200 , 61.1 , 61.2 , 61.3
-----
sp_full_scan_L=3_N=2 , 34.8 , 34.9 , 35.0
sp_full_scan_L=3_N=5 , 35.0 , 35.0 , 35.1
sp_full_scan_L=3_N=10 , 35.2 , 35.3 , 35.3
sp_full_scan_L=3_N=20 , 36.1 , 36.1 , 36.1
sp_full_scan_L=3_N=50 , 39.3 , 39.4 , 39.5
sp_full_scan_L=3_N=100 , 45.8 , 45.9 , 46.0
sp_full_scan_L=3_N=200 , 61.3 , 61.3 , 61.5
-----
sp_full_scan_L=5_N=2 , 35.2 , 35.4 , 35.7
sp_full_scan_L=5_N=5 , 35.3 , 35.5 , 35.8
sp_full_scan_L=5_N=10 , 35.6 , 35.7 , 35.7
sp_full_scan_L=5_N=20 , 36.4 , 36.5 , 36.6
sp_full_scan_L=5_N=50 , 39.7 , 39.8 , 39.9
sp_full_scan_L=5_N=100 , 46.2 , 46.3 , 46.3
sp_full_scan_L=5_N=200 , 62.2 , 62.4 , 62.8
-----
sp_full_scan_L=10_N=2 , 36.2 , 36.7 , 37.9
sp_full_scan_L=10_N=5 , 36.5 , 36.8 , 37.1
sp_full_scan_L=10_N=10 , 36.7 , 36.8 , 36.9
sp_full_scan_L=10_N=20 , 37.6 , 37.7 , 37.9
sp_full_scan_L=10_N=50 , 41.0 , 41.1 , 41.2
sp_full_scan_L=10_N=100 , 47.6 , 47.9 , 48.1
sp_full_scan_L=10_N=200 , 63.3 , 63.7 , 64.0
-----
sp_full_scan_L=20_N=2 , 37.1 , 37.3 , 37.5
sp_full_scan_L=20_N=5 , 38.5 , 38.7 , 38.7
sp_full_scan_L=20_N=10 , 39.0 , 39.3 , 39.7
sp_full_scan_L=20_N=20 , 39.8 , 40.1 , 40.5
sp_full_scan_L=20_N=50 , 43.4 , 43.5 , 43.6
sp_full_scan_L=20_N=100 , 50.1 , 50.5 , 51.0
sp_full_scan_L=20_N=200 , 66.5 , 66.7 , 66.9
-----
sp_full_scan_L=50_N=2 , 37.1 , 37.4 , 37.5
sp_full_scan_L=50_N=5 , 42.8 , 42.9 , 42.9
sp_full_scan_L=50_N=10 , 45.5 , 45.7 , 46.0
sp_full_scan_L=50_N=20 , 46.9 , 47.0 , 47.2
sp_full_scan_L=50_N=50 , 50.9 , 51.1 , 51.5
sp_full_scan_L=50_N=100 , 58.2 , 58.5 , 58.8
sp_full_scan_L=50_N=200 , 75.4 , 75.7 , 76.1
-----
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Benchmark results from the WIP "silentpayments" secp256k1 module (theStack/secp256k1@8eced64) over a L/N matrix (note that L=1 should represent any higher L values as well for the BIP approach, assuming that the label cache lookup cost can be neglected):