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.

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

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.

External sites

Code coverage & benchmarks: https://corecheck.dev/bitcoin/bitcoin/pulls/36327
Ralph review <img src=https://review.fish.foo/assets/bitcoin/bitcoin/36327.png alt="Ralph review status"> https://git.fish.foo/bitcoin/bitcoin/pulls/36327#author-ralph

Reviews

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

Type	Reviewers
ACK	fametrano, theStack, ViniciusCestarii
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).

brunoerg commented at 10:30 AM on September 28, 2026:

Sounds good!

brunoerg commented at 10:39 AM on September 28, 2026:

Done

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.

brunoerg commented at 10:40 AM on September 28, 2026:

Done

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.

test: speed up secp256k1 fixed-base multiplication

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

Cache multiplications by G, since tests often multiply G repeatedly by
the same private key.

b6fc3cf004

brunoerg force-pushed on Sep 28, 2026

brunoerg commented at 10:42 AM on September 28, 2026: contributor

Force-pushed addressing #36327 (review) and #36327 (review)

brunoerg commented at 10:42 AM on September 28, 2026: contributor

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

From my bench, I guess 70% from the FastGEMul and 30% from the caching.

theStack commented at 11:15 AM on September 28, 2026: contributor

Concept ACK

fametrano commented at 11:45 AM on October 2, 2026: contributor

tACK b6fc3cf0046d3106e0dfb30f320d48514eff6fb2

I checked k * G on this branch against a second implementation for about 10,000 random scalars plus edge cases (0, n-1, n, n+1, 2n, negative values, runs of ones, each 4-bit window position). All matched. sign_schnorr passes the BIP340 vectors and gave the same signatures as that implementation for 2,000 random messages and aux_rand.

On where the gain comes from: both changes matter, the window somewhat more. In my steadiest run of feature_taproot.py (shared machine, so rough), the window alone took about 35% off master, the cache alone about 30%, and both together 54% (62s to 29s).

Nit, not new here: no unit test multiplies G by a negative scalar. I suggested one inline.

in test/functional/test_framework/crypto/secp256k1.py:364 in b6fc3cf004

 371 |  
 372 | +@functools.lru_cache(maxsize=1024)
 373 | +def mul_G(a):
 374 | +    return FAST_G.mul(a)
 375 | +
 376 |  class TestFrameworkSecp256k1(unittest.TestCase):

fametrano commented at 11:45 AM on October 2, 2026:

This catches the % GE.ORDER being dropped from both GE.__rmul__ and FastGEMul.mul, which the current tests miss:

class TestFrameworkSecp256k1(unittest.TestCase):
    def test_neg_mul(self):
        self.assertEqual(((-1) * G).to_bytes_compressed(), (-G).to_bytes_compressed())

DrahtBot requested review from theStack on Oct 2, 2026

DrahtBot requested review from real-or-random on Oct 2, 2026

in test/functional/test_framework/crypto/secp256k1.py:363 in b6fc3cf004

 370 |  FAST_G = FastGEMul(G)
 371 |  
 372 | +@functools.lru_cache(maxsize=1024)
 373 | +def mul_G(a):
 374 | +    return FAST_G.mul(a)
 375 | +

theStack commented at 3:24 PM on October 2, 2026:

nit: alternatively, applying the cache decorator directly on the GE.__rmul__ method (as suggested in #36327 (review)) seems to work fine and would include caching for other points (probably only the generator is relevant though), ~same speedup on my machine. no strong opinion on what to prefer

brunoerg commented at 6:19 PM on October 2, 2026:

I considered that, but I preferred to keep the cache scoped to G. I will leave as-is for now, but happy to change if others prefer.

real-or-random commented at 11:43 AM on October 3, 2026:

nit: alternatively, applying the cache decorator directly on the GE.__rmul__ method (as suggested in #36327 (comment)) seems to work fine and would include caching for other points (probably only the generator is relevant though), ~same speedup on my machine. no strong opinion on what to prefer

This is indeed what I had in mind when I suggested it. I have a slight preference for that variant. It's more general and future tests may profit from it.

(But no objections against merging as-is. :) It's certainly an improvement.)

theStack approved

theStack commented at 3:36 PM on October 2, 2026: contributor

ACK b6fc3cf0046d3106e0dfb30f320d48514eff6fb2

Results on my arm64 machine: 1m16.030s master vs. 0m52.547s PR branch

nit: could update the PR description before merging, as it still mentions the caching on compute_xonly_pubkey

brunoerg commented at 5:07 PM on October 2, 2026: contributor

nit: could update the PR description before merging, as it still mentions the caching on compute_xonly_pubkey

Done.

ViniciusCestarii commented at 6:41 PM on October 2, 2026: contributor

tACK b6fc3cf0046d3106e0dfb30f320d48514eff6fb2

Tested on an x86-64 machine with build/test/functional/feature_taproot.py --randomseed=1, mean of 5 runs:

Before: 51.570s After: 27.586s

sedited merged this on Oct 5, 2026

sedited closed this on Oct 5, 2026