silentpayments: optimize sender output creation with generator table and batch inversion #1970

In secp256k1_silentpayments_sender_create_outputs, output keys are currently generated by calling secp256k1_eckey_pubkey_tweak_add. That helper delegates to secp256k1_ecmult, which does a full Straus W-NAF scalar multiplication with GLV decomposition and up to 129 point doublings per output, followed by an immediate modular inversion in secp256k1_ge_set_gej.

Because ctx->ecmult_gen_ctx is already validated on entry, we can compute t_k * G with secp256k1_ecmult_gen_gej from the generator table and add B_spend with a single mixed addition (secp256k1_gej_add_ge). This drops all point doublings from the tweak calculation.

To avoid the individual field inversions, we collect the Jacobian points in batches of up to 16 outputs and convert them simultaneously via Montgomery batch inversion (secp256k1_ge_set_all_gej_var), like we already do for label candidates in the scanning path. This cuts modular inversions down to one per 16 outputs.

Passes all BIP-352 test vectors and existing tests. In local benchmarks, this reduces runtime by roughly 12% to 23% depending on output batch size.

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.

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.

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.

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.