musig: allocate scratch space for multi-exponentiation in pubkey_agg #1971

pull Yudis-bit wants to merge 1 commits into bitcoin-core:master from Yudis-bit:musig_keyagg_scratch_opt changing 1 files +16 −7

Yudis-bit commented at 10:36 AM on October 20, 2026: contributor

In secp256k1_musig_pubkey_agg, secp256k1_ecmult_multi_var is called with a NULL scratch space. Without a scratch space, secp256k1_ecmult_multi_var falls back to secp256k1_ecmult_multi_simple_var, which evaluates each public key scalar multiplication individually in a serial loop with up to 129 point doublings per signer.

This patch addresses the TODO in secp256k1_musig_pubkey_agg by allocating a temporary scratch space sized for Strauss (or Pippenger when n_pubkeys exceeds ECMULT_PIPPENGER_THRESHOLD). By providing the scratch buffer, secp256k1_ecmult_multi_var executes multi-scalar multiplication sharing the point doubling loop across the entire signer set.

In local benchmarks on x86_64, this cuts pubkey aggregation cycles by roughly 34% for 4 signers (274k vs 416k cycles), 57% for 16 signers (998k vs 2.37M cycles), and 58% for 128 signers (7.27M vs 17.39M cycles, saving over 10M cycles per call). All existing MuSig2 test vectors and module tests pass.

musig: allocate scratch space for multi-exponentiation in pubkey_agg

In secp256k1_musig_pubkey_agg, secp256k1_ecmult_multi_var was called with a
NULL scratch space, falling back to secp256k1_ecmult_multi_simple_var where
each public key scalar multiplication is evaluated individually with up to
129 point doublings per signer.

Resolve the TODO in secp256k1_musig_pubkey_agg by allocating a temporary
scratch space sized for Strauss (or Pippenger when n_pubkeys >
ECMULT_PIPPENGER_THRESHOLD). This enables multi-scalar multiplication to
share the doubling loop across all signers.

In local benchmarks on x86_64, this reduces pubkey aggregation cycles by
34% for 4 signers, 57% for 16 signers, and 58% (saving over 10M cycles) for
128 signers, while passing all MuSig2 test vectors and module tests.

365a3aa206

Yudis-bit requested review from Copilot on Oct 20, 2026
Copilot commented at 10:36 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:00 PM on October 20, 2026: contributor

I don't think this can go in as is: it adds a malloc to secp256k1_musig_pubkey_agg, while the README says "No runtime heap allocation" and the headers point users who must avoid malloc entirely to secp256k1_preallocated.h. #1789 kept pubkey_agg allocation-free for this reason (comment), and the plan there for MuSig on hardware wallets is still open, likely via an overridable malloc (#1917). The speedup is real: on arm64, 365a3aa against master e74a018 over 5 runs, it halves the time at 16 keys and saves 70% at 1024, with matching results. Happy to share the numbers and the cross-check.
Yudis-bit commented at 5:49 AM on October 23, 2026: contributor

Fair point on the heap invariant for embedded targets under secp256k1_preallocated.h. Resolving the TODO in keyagg_impl.h cleanly depends on compile-time allocator overrides (#1917) or exposing a caller-provided scratch buffer in the API. Closing for now until the allocator plumbing in #1917 lands.
Yudis-bit closed this on Oct 23, 2026

Contributors

Yudis-bit

Copilot

fametrano