silentpayments: add scanning function that takes the labels as an array #1976

pull fametrano wants to merge 6 commits into bitcoin-core:master from fametrano:sp-scan-with-labels changing 7 files +967 −49

fametrano commented at 9:57 AM on October 22, 2026: contributor

With a label lookup, secp256k1_silentpayments_recipient_scan_outputs does two point additions and two lookups for every output of the transaction, even when the recipient scans only for the change label. A transaction with 2323 outputs that does not pay the recipient takes 0.86 ms to scan, against 25 µs for one with 2 outputs. One that pays the recipient in all 2323 outputs, the K_max limit, takes about a second, because the outputs are walked again for every k.

This PR adds secp256k1_silentpayments_recipient_scan_outputs_with_labels, which takes the labels as an array instead of a callback. For each k it adds every label to the candidate output and compares the result with the outputs, so its point additions grow with the number of labels, not with the number of outputs. It returns the same outputs, tweaks and labels as scan_outputs, also on malformed transactions, and the tests check that. scan_outputs does not change: the first commit only moves its setup into helpers that both functions use.

I measured both functions on the same transactions with an out-of-tree harness, using a hash table as the label lookup (Apple M5, best of 3 to 7 runs), and can share it. The in-tree nomatch benchmark at 2323 outputs agrees: about 880 µs and 30 µs.

transaction	labels	`scan_outputs`	`_with_labels`
2 outputs, no payment	1 / 10 / 100	25 / 25 / 26 µs	24 / 26 / 43 µs
2323 outputs, no payment	1 / 10	858 / 858 µs	28 / 37 µs
2323 outputs, all to the recipient (the K_max limit)	1 / 10 / 100 / 1000	1.0 s	0.027 / 0.040 / 0.18–0.44 / 1.52 s
23255 outputs, last 2323 to the recipient (non-standard, loaded machine)	1	18.7 s	76 ms

#1792 proposed this approach as the only scanning function. It was closed because K_max bounded the worst case it was meant to fix, and #1799 found that a cost growing with the number of labels outweighed its simpler API. jonasnick wrote there that "in the long run we should have both the BIP approach and the labelset approach". Now that #1765 has merged the BIP approach, this adds the other one as a second function, so recipients with many labels keep the callback and no label limit is needed. Each function takes the labels once, unlike the hybrid prototype, and the outputs keep their order, unlike in #1792, so the lowest index still wins as in #1765. The cost is one more public function and one struct.

This does not help a recipient with many labels. At 2323 outputs all paying the recipient, scan_outputs is faster from about 650 labels. This PR conflicts with #1912 and #1914, and I will rebase on whichever merges first.

silentpayments: factor out scan setup and output tweaking

Move the argument checks, the shared secret creation and the
calculation of t_k and unlabeled_output out of
`_recipient_scan_outputs` into helper functions, so that a second
scanning function can share them.

No behavior change: the checks run in the same order and the same
values are cleared on every return path.

7386752671

silentpayments: add API function for scanning with a list of labels

Add `secp256k1_silentpayments_recipient_scan_outputs_with_labels`. It
takes the labels as an array of label entries (label and label tweak)
instead of a label lookup callback, and finds the same outputs as
`_recipient_scan_outputs`.

For each k it adds every label to unlabeled_output and compares the x
coordinates of the results with the tx outputs. This costs one point
addition per label instead of two per tx output, and needs no label
lookups. It needs no sorting, no scratch space and no heap allocation,
and it does not modify its inputs.

The results match those of `_recipient_scan_outputs` also for malformed
transactions: the tx output with the lowest index wins, then a direct
match over a label match, then the label candidate with even Y over the
one with odd Y.

f4da69637e

silentpayments: test scanning with a list of labels against the callback

Check that `_recipient_scan_outputs_with_labels` returns the same found
outputs, tweaks and labels as `_recipient_scan_outputs` with a label
lookup over the same labels.

The cases are the BIP352 receiving test vectors with the tx outputs in
given, reversed and shuffled order; malformed transactions in every
output order, including a labeled match before a direct one; outputs
that match two labels; and random transactions with up to 40 labels.

67c2db72d8

silentpayments: add benchmarks for scanning with a list of labels

Run each scanning benchmark also with
`_recipient_scan_outputs_with_labels`, on the same transactions and
with the same label. The new benchmarks are
`silentpayments_scan_list_nomatch_N=...` and
`silentpayments_scan_list_worstcase_K=...`.

79b77a0825

silentpayments: add ctime-tests for scanning with a list of labels

Scan with the secret scan key and a label entry whose label is public
and whose label tweak is secret. This also covers the overflow check on
each label tweak.

70ab891d4c

silentpayments: extend example with scanning with a list of labels

Show that Bob can pass his label as a label entry to
`_recipient_scan_outputs_with_labels` instead of the label lookup
callback, and that he finds the same outputs.

d8e64d05ba

Contributors

fametrano

Linked (view graph)

#1765 Add "silentpayments" module implementing BIP352 (take 4, limited to full-node scanning)#1792 Add "silentpayments" module implementing BIP352 (take 5, using "LabelSet" scanning approach)#1799 Silent Payments module: discussion about different scanning approaches (BIP, LabelSet, hybrid)#1912 silentpayments: add light client API #1914 silentpayments: tweak spend pubkey using ecmult_gen_var (~25% scanning speedup for small N)