test: speed up secp256k1 fixed-base multiplication and Schnorr signing #36327

brunoerg commented at 3:08 PM on September 24, 2026: contributor

This PR speeds up the test framework’s fixed-base multiplication and Schnorr signing by:

Changing FastGEMul to process scalars in 4-bit windows instead of individual bits. Precompute all 16 multiples for each window position, reducing multiplication from about 128 point additions on average to 64 table lookups and about 60 nonzero point additions. This trades a larger table and additional initialization work for cheaper repeated multiplications.
Cache compute_xonly_pubkey and reuse it in sign_schnorr. Repeated signing with the same key avoids recomputing the public key, leaving only the nonce’s generator multiplication, which also benefits from the updated FastGEMul.

On my local machine (Macbook M2 Pro) the feature_taproot.py's medium time decreased from 83.39s to 35.42s.

test: speed up secp256k1 fixed-base multiplication and Schnorr signing

Use a 4-bit precomputed table in FastGEMul to reduce the average number
of nonzero point additions from about 128 to 60.

Cache compute_xonly_pubkey and reuse it in sign_schnorr to avoid
recomputing public keys when signing repeatedly with the same key.

7b32b442f8

DrahtBot added the label Tests on Sep 24, 2026

DrahtBot commented at 3:08 PM on September 24, 2026: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/36327.

Reviews

See the guideline and AI policy for information on the review process.

Type	Reviewers
Concept ACK	StephenChi-hi, real-or-random

If your review is incorrectly listed, please copy-paste <code></code> into the comment that the bot should ignore.

fanquake commented at 4:27 PM on September 24, 2026: member

cc @theStack @real-or-random

StephenChi-hi commented at 6:21 PM on September 25, 2026: none

ACK

Nice, the multiplication logic looks correct

in test/functional/test_framework/key.py:193 in 7b32b442f8

 188 | @@ -188,10 +189,14 @@ def sign_ecdsa(self, msg, low_s=True, rfc6979=False):
 189 |          sb = s.to_bytes((s.bit_length() + 8) // 8, 'big')
 190 |          return b'\x30' + bytes([4 + len(rb) + len(sb), 2, len(rb)]) + rb + bytes([2, len(sb)]) + sb
 191 |  
 192 | +@functools.cache
 193 |  def compute_xonly_pubkey(key):

real-or-random commented at 7:46 PM on September 25, 2026:

What about caching GE.__rmul__ instead, which is the actual expensive operation here? Other callers may benefit, and you could leave sign_schnorr untouched (which keeps it closer to the reference implementation in BIP340 also).

in test/functional/test_framework/crypto/secp256k1.py:327 in 7b32b442f8

 321 | @@ -322,27 +322,35 @@ def __repr__(self):
 322 |  class FastGEMul:
 323 |      """Table for fast multiplication with a constant group element.
 324 |  
 325 | -    Speed up scalar multiplication with a fixed point P by using a precomputed lookup table with
 326 | -    its powers of 2:
 327 | +    Speed up scalar multiplication with a fixed point P by using a precomputed lookup table.
 328 | +    The scalar is split into WINDOW-bit chunks, and for every chunk position i the table holds
 329 | +    the points (0 * 2^(WINDOW*i)) * P, (1 * 2^(WINDOW*i)) * P, ..., ((2^WINDOW-1) * 2^(WINDOW*i)) * P:

real-or-random commented at 8:29 PM on September 25, 2026:

    The scalar is split into WINDOW-bit chunks, and for every chunk position i the table holds
    a row [(0 * 2^(WINDOW*i)) * P, (1 * 2^(WINDOW*i)) * P, ..., ((2^WINDOW-1) * 2^(WINDOW*i)) * P]:

Without this, the row variable name below may be confusing. It's not clear to the reader if the table indices are row-first or column-first.

real-or-random commented at 8:30 PM on September 25, 2026: contributor

Changing FastGEMul to process scalars in 4-bit windows instead of individual bits. [...] This trades a larger table and additional initialization work for cheaper repeated multiplications.

Since this is test-only code, I believe the actual trade-off here is between simplicity of the implementation vs. running time. The current implementation is probably close to the most obvious one can write whereas the windowed one is already "optimized", though it's still simple.

Concept ACK -- And yeah saving ~40s sounds like a reasonable trade-off.

Though I wonder how much comes from the caching and how much from the optimized FastGEMul.