silentpayments: optimize sender output creation with generator table #1970

Yudis-bit commented at 8:27 AM on October 20, 2026: contributor

In secp256k1_silentpayments_sender_create_outputs, output keys are generated by calling secp256k1_eckey_pubkey_tweak_add. That helper delegates to secp256k1_ecmult, executing full Straus W-NAF scalar multiplication with GLV decomposition and up to 129 point doublings per output, even though ctx->ecmult_gen_ctx is already validated on entry.

Switching to secp256k1_ecmult_gen_gej evaluates t_k * G from the precomputed generator table and adds B_spend with a single mixed addition (secp256k1_gej_add_ge). Jacobian coordinates are converted back to affine in constant time via secp256k1_ge_set_gej, eliminating point doublings across all sending scenarios.

The first commit introduces sender benchmarks to bench.c for N = 1, 2, 5, 10, 100 outputs with distinct and shared scan keys. The second commit applies the generator table optimization.

Against the first commit baseline, the generator table yields roughly 7 to 10% speedup for single outputs, 8 to 13% for multiple outputs with distinct scan keys, and 11 to 21% when outputs share a scan key.

Yudis-bit requested review from Copilot on Oct 20, 2026

Copilot commented at 8:27 AM on October 20, 2026: none

Copilot was unable to review this pull request because the user who requested the review has reached their quota limit.

An organization owner can choose the repository organization as the billing source for reviews requested by members with a paid Copilot license. Learn about Copilot code review billing.

fametrano commented at 11:07 PM on October 20, 2026: contributor

Concept ACK, tested 85ee5f5: it gives the same outputs as master, and sender_create_outputs takes 7% less time for one output, 14-15% less for 10-100 outputs with distinct scan keys and 29-35% less when they share one. I compared master, this PR and an independent Python implementation on the BIP352 sending vectors and 500 random sends, and timed both builds; script available. Question: the secp256k1_ecmult_gen_gej result now goes through secp256k1_ge_set_all_gej_var; is that intended? Its coordinates carry the context's blinding, the library converts them in constant time elsewhere, and secp256k1_ge_set_all_gej would fit here.

Yudis-bit commented at 8:59 AM on October 21, 2026: contributor

Updated to secp256k1_ge_set_all_gej in 192db92.

Because ecmult_gen_gej blinds the Jacobian coordinates, running the batch inversion through fe_inv_var leaks the context's blinding factor via variable-time divsteps. Non-infinity is already guaranteed by the check in create_output_pubkey_gej, so ge_set_all_gej drops in cleanly.

fametrano commented at 5:48 AM on October 22, 2026: contributor

ACK 192db92e. The constant-time conversion answers my question, and it costs under 1% against 85ee5f5 at every size I timed, in medians of seven interleaved rounds, so the speedups hold.

The stock ctime_tests cannot see this change: it runs the sender before the context is randomized, and t_k is declassified, so nothing secret reaches the conversion. A local probe runs the sender after secp256k1_context_randomize with a secret seed. Under Valgrind, 85ee5f5 gives 313 errors from 12 places, eight of them in the variable-time conversion as you describe, and 192db92 none there. Three branches remain, in the infinity check, fe_normalize_var and extrakeys_ge_even_y. They depend only on whether the output is infinity and on its y, not on the blinding, so they are false positives; a test like the probe would need to declassify the output before them. The outputs still match master and btclib-ecc on 600 random sends (15300 outputs), and the BIP352 vectors pass. Probe and scripts available.

theStack commented at 10:08 AM on October 23, 2026: contributor

Concept ACK, but I think the two optimization ideas of "tweak pubkey using ecmult_gen" (which can be seen as the sending equivalent of #1914) and "use batch inversion" could be separated and hence split into individual commits, or even go into different PRs. The first one is relatively simple and beneficial for all sending scenarios (even with a single SP recipient), while the batch inversion one I wouldn't see exactly as high priority right now.

It would certainly also be helpful to introduce sending benchmarks (here or in an own PR), so we don't have to rely on claims or request benchmark scripts from you.

theStack added the label performance on Oct 23, 2026

bench: add benchmark for silentpayments sender output creation

Introduce benchmark for secp256k1_silentpayments_sender_create_outputs,
covering both distinct scan keys (independent recipients) and shared scan
keys (multiple outputs to the same recipient) across realistic output counts
N = 1, 2, 5, 10, 100.

d56bf69723

Yudis-bit force-pushed on Oct 24, 2026

Yudis-bit commented at 3:10 AM on October 24, 2026: contributor

Pushed a rebase splitting the changes into three commits, with the first adding sender benchmarks to bench.c, the second isolating ecmult_gen_gej, and the third batching Jacobian inversions with ge_set_all_gej. The generator table alone gives roughly 7 to 16% speedup for distinct scan keys and about 30% for shared scan keys. If preferred, I can drop the batch inversion commit here and open it in a separate PR instead.

theStack commented at 2:25 AM on October 27, 2026: contributor

If preferred, I can drop the batch inversion commit here and open it in a separate PR instead.

Yeah, I'd prefer to drop the batch inversion commit here indeed. Given that sending to multiple outputs with a shared scan public key is probably still an extremely rare scenario (many SP wallets didn't even support more than one recipient in total, the last time I checked), I don't think the added code complexity is worth it for now.

Yudis-bit force-pushed on Oct 27, 2026

Yudis-bit renamed this:
~~silentpayments: optimize sender output creation with generator table and batch inversion~~
silentpayments: optimize sender output creation with generator table
on Oct 27, 2026

Yudis-bit commented at 4:13 AM on October 27, 2026: contributor

Dropped the batch inversion commit in 11ef56b. The branch now only adds the sender benchmarks in bench.c and the generator table optimization in ecmult_gen_gej, and I updated the PR title and description to match. Passes ./tests, silentpayments test vectors, and ctime_tests under Valgrind with clean range-diff.

fametrano commented at 12:42 AM on October 28, 2026: contributor

ACK 11ef56be99194b3fe67f3cc77a1b7da6fbf88954

I checked the range-diff from 192db92, the head I reviewed last: the batching is gone, and each output now goes through secp256k1_ge_set_gej, which is constant time. make check passes on macOS and Linux and ctime_tests gives 0 errors under Valgrind. The outputs match master and btclib-ecc on 600 random sends (7812 outputs), with and without a randomized context. My probe runs the sender after secp256k1_context_randomize with a secret seed, with the recipients' public keys marked as public. Here it finds nothing in the conversion, only the three branches that do not depend on the blinding. Probe, harness and logs: https://gist.github.com/fametrano/d7441ff9fd8fa6290b19fe682397efef/7cd1760777f5ff6c867f5c855d062adb8185989e.

Not blocking: for two or more outputs I measure smaller speedups than the description gives. With the new benchmark, against this PR's first commit, sending takes 7% less time for one output, 8-9% less for 2 to 100 outputs with distinct scan keys and 11-21% less when they share one (Apple M5, minimum of five alternated rounds, ecdsa_sign unchanged as control). The description's figures match what I measured on 85ee5f5, which also had batch inversion. Since the description goes into the merge commit, its figures could be updated or dropped.

Yudis-bit commented at 3:54 AM on October 28, 2026: contributor

Updated the benchmark figures in the PR description to match the generator table speedups measured against the first commit baseline.

in src/modules/silentpayments/main_impl.h:170 in 11ef56be99 outdated

 169 | -     * will happen only with negligible probability for honestly created spend_pubkey, but we handle this error anyway
 170 | -     * to protect against this function being called with malicious inputs, i.e.,
 171 | +    /* Calculate tweak_G = t_k * G using the precomputed generator table in ecmult_gen_ctx. */
 172 | +    secp256k1_ecmult_gen_gej(&ctx->ecmult_gen_ctx, &tweak_G_gej, &t_k_scalar);
 173 | +    /* Leaking this value would break indistinguishability of the transaction, so clear it. */
 174 | +    secp256k1_scalar_clear(&t_k_scalar);

theStack commented at 4:04 AM on October 28, 2026:

could you also clear tweak_G_gej ~here~ after the addition below? (see the comment in ecmult_gen_ge on the rationale behind); doesn't have to be in this PR, but maybe we should already introduce a separate helper function like _pubkey_tweak_add_with_gen_ctx

theStack commented at 4:05 AM on October 28, 2026: contributor

ACK modulo one clearing request

silentpayments: optimize sender output creation with generator table

In secp256k1_silentpayments_create_output_pubkey, output keys are
generated by calling secp256k1_eckey_pubkey_tweak_add. That helper
delegates to secp256k1_ecmult, executing full Straus W-NAF scalar
multiplication with up to 129 point doublings even though ecmult_gen_ctx
is already validated on entry.

Switch to secp256k1_ecmult_gen_gej to evaluate t_k * G from the precomputed
generator table and add B_spend with a single mixed addition (secp256k1_gej_add_ge),
reducing per-output scalar multiplication cost across all sending scenarios.

e4a626655c

Yudis-bit force-pushed on Oct 28, 2026

Yudis-bit commented at 4:50 AM on October 28, 2026: contributor

Cleared tweak_G_gej with secp256k1_gej_clear right after the mixed addition in e4a6266. Introducing a shared _pubkey_tweak_add_with_gen_ctx helper makes sense as a follow-up alongside #1914. Passes ./tests, silentpayments test vectors, and ctime_tests under Valgrind with clean range-diff.

fametrano commented at 8:19 AM on October 28, 2026: contributor

ACK e4a626655c1b753c21b1aab821562fb395c3fc0a

The range-diff from 11ef56b only adds the secp256k1_gej_clear(&tweak_G_gej) theStack asked for. On e4a6266, make check passes on macOS and Linux, and ctime_tests gives 0 errors under Valgrind on Linux.

in src/bench.c:79 in d56bf69723

  72 | @@ -73,9 +73,12 @@ static void help(const char *executable_path, int default_iters) {
  73 |  #endif
  74 |  
  75 |  #ifdef ENABLE_MODULE_SILENTPAYMENTS
  76 | -    printf("    silentpayments                       : all Silent payments benchmarks (scan_nomatch, scan_worstcase)\n");
  77 | +    printf("    silentpayments                       : all Silent payments benchmarks (scan_nomatch, scan_worstcase, send)\n");
  78 |      printf("    silentpayments_scan_nomatch          : Silent payments scanning common case (no match)\n");
  79 |      printf("    silentpayments_scan_worstcase        : Silent payments scanning worst case (block-sized tx, all match)\n");
  80 | +    printf("    silentpayments_send                  : all Silent payments sending benchmarks\n");

theStack commented at 1:49 PM on October 28, 2026:

small follow-up idea: an option for running all scanning benchmarks (silentpayments_scan) could now make sense as well

in src/modules/silentpayments/bench_impl.h:338 in d56bf69723

 333 | +            send_data.shared_scan_key = 0;
 334 | +            sprintf(str, "silentpayments_send_distinct_N=%i", num_outputs);
 335 | +            if (iters <= 2 && num_outputs > 10) {
 336 | +                printf("Skipping benchmark \"%s\" due to SECP256K1_BENCH_ITERS <= 2\n", str);
 337 | +            } else {
 338 | +                run_benchmark(str, bench_silentpayments_send, bench_silentpayments_send_setup, bench_silentpayments_send_teardown, &send_data, 10, num_outputs <= 10 ? iters : iters / 10 + 1);

theStack commented at 1:56 PM on October 28, 2026:

nit-like: I've noticed that the sending benchmarks with the default setting (i.e. 20000 iterations) take quite a long time, over 6m30s on my machine vs. the scanning benchmarks (~2m50s, dominated by the worst-case scenario), it might make sense to adjust the formula for the iterations parameter a bit (maybe just a fixed number for num_outputs > 10 like in the scanning benchmark?). For CI that's not an issue as the slow N=100 case is skipped, so no blocker and can be discussed/tweaked in a follow-up

theStack approved

theStack commented at 2:04 PM on October 28, 2026: contributor

ACK e4a626655c1b753c21b1aab821562fb395c3fc0a

fametrano referenced this in commit 3e2c484760 on Nov 2, 2026

fametrano referenced this in commit 8575b19a8b on Nov 2, 2026

theStack added the label side-channel on Nov 5, 2026

theStack added this to the milestone 0.8.1 on Nov 5, 2026