# 2026-11-01 — Research Axis B: ECDSA / BIP340 Schnorr benchmarks (questions B2, B5)

Research question. B2: can BIP340 verification be accelerated without changing consensus semantics (batch verification)? B5: which implementation choices produce measurable differences? Null hypothesis (B2). Batch verification gives no per-signature saving over single verification at any batch size. Alternative. The per-signature cost decreases with b and saturates.

Setup. experiments/signature_benchmarks/sigbench (Rust 1.95/1.96, rust-secp256k1 0.33.1 → libsecp256k1 via secp256k1-sys 0.14.1, k256 0.14.0, elliptic-curve 0.14.3, ecdsa 0.17.0, wnaf 0.14.1), seed 34, 7 repetitions × ≥ 2000 operations per measurement, single thread, bootstrap CI with 2000 resamples. Two hosts: laptop (Apple M5 Max, 18 cores, macOS 27.0) and cluster node M3U96a (Apple M3 Ultra, 28 cores, macOS 26.6). Results: results/signature_benchmarks/bench_MacBookPro-de-simon-pierre-2.json, bench_MacStudnpierre2.json, summary.json, logs run_laptop.log, run_m3u96a.log. Commands are stored in each JSON (command, params.rust_command). Synthetic keys only.

# Correctness gates (both hosts, identical because the RNG is seeded)

• BIP340 official vectors: 19/19 verification outcomes and 8/8 byte-identical signatures with both libsecp256k1 and k256 (vectors 5–14 with invalid keys / r ≥ p / s ≥ n / wrong parity all rejected as expected).
• Cross-library: 1000/1000 k256-signed ECDSA signatures verified by libsecp256k1 and vice versa; same for Schnorr; 1000/1000 byte-identical in both schemes (RFC 6979 nonces for ECDSA, the BIP340 aux-rand nonce derivation for Schnorr — deterministic by construction).
• Python reference (src/wp34, exact integer arithmetic): 200/200 Rust signatures verified for all four (scheme × library) combinations, 200/200 re-signed identically in pure Python, 200/200 tampered signatures rejected. tests/test_sig_crosscheck.py passes (2 tests, also checks the Python reference against the 19 vectors independently of Rust).
• Own MSM: Straus with one term agrees with k256 on 64 scalar multiplications; batch negative controls (s+1, flipped message bit, r+1 inside a batch of 64) rejected by all four MSM back-ends, while the unmodified batch is accepted.

# Findings

# F1 — Batch verification speed-up (classification: known_reproduced)

Per-signature cost of Σ a_i s_i G = Σ a_i R_i + Σ a_i e_i P_i with a_1 = 1 and random 128-bit a_i, as a function of b (laptop; M3U96a shows the same shape at ×1.3 cost):

S = speed-up versus a single k256 verify_raw (24.5 µs); versus libsecp256k1's single verify (13.2 µs) the best point is 1.67 [1.65, 1.68] (M3U96a: 3.03 [3.00, 3.04] and 1.58). The null hypothesis is rejected for every back-end at b ≥ 4 (CIs exclude 1); the gain saturates. This is the expected behaviour described in the BIP340 text ("batch verification ... up to a factor of 2") and measured for Ed25519 by Bernstein, Duif, Lange, Schwabe and Yang (2012); our numbers reproduce the known result in k256 arithmetic and do not constitute a new algorithm. Op counts (per signature, 2b + 1 terms): Straus plateaus at ≈ 79 projective additions + 2 doublings per signature exactly as predicted by wNAF-5 density (≈ 256/6 + 7 table additions for the 256-bit P_i term, ≈ 128/6 + 7 for the 128-bit R_i term); Pippenger at b = 2048 (c = 8) uses 47.8 mixed additions + 8.0 additions + 0.1 doublings per signature, i.e. about 0.7× the group operations of Straus, which is the whole source of its advantage.

# F2 — The attainable speed-up is capped by the per-signature non-MSM work (empirical_observation)

The MSM-only time falls to 4.9 µs/sig (laptop, b = 2048) but the total is 7.9 µs/sig: ≈ 3.0 µs per signature (3.6 µs on M3U96a) is spent outside the MSM — lift_x(r) (one square root = a 255-bit field exponentiation), the tagged SHA-256 challenge hash and the scalar parse. Single verification pays the same hash but no square root for R (it compares x-coordinates). Hence the asymptotic speed-up is bounded by (single verify) / (non-MSM floor + MSM/sig), roughly 4–5× in this arithmetic even with an ideal MSM — consistent with the saturation seen above. This is a well-understood cost model, reported here with measured constants.

# F3 — Library choice matters more than batching (empirical_observation)

• libsecp256k1 verifies ≈ 2× faster than k256 (ECDSA 12.6 vs 25.0 µs; Schnorr 13.2 vs 24.5 µs on the laptop), consistent with its 5×52-bit field representation, GLV + wNAF strategy with effective-affine precomputation and years of tuning. Conversely k256 signs faster than libsecp256k1 (ECDSA 15.3 vs 23.6 µs; Schnorr 11.6 vs 20.5 µs): rust-secp256k1's signing path goes through the blinded, constant-time ecmult_gen (19.8 µs for a generator multiplication through PublicKey::from_secret_key) whereas k256's mul_by_generator uses a 30 kB fixed table (8.3 µs; 6.6 µs in variable time). This was not anticipated and is worth stating in the paper as an implementation-choice effect, not a mathematical one.
• Scalar multiplication (laptop): own wNAF-5 double-and-add without GLV 21.1 µs (257 doublings + 52 additions); k256 constant-time with GLV 16.4–17.2 µs; k256 variable-time GLV + wNAF 14.0 µs; libsecp256k1 ecmult_const 11.5 µs. The GLV endomorphism therefore buys ≈ 1.3–1.5× here, in line with Gallant–Lambert–Vanstone (2001). GLV is not switchable from either public API; this is stated in the JSON (scalar_mult.glv_note).
• k256's own lincomb_vartime is slower than our naive Straus for b ≥ 8 and degrades for large b (17.1 µs/sig at b = 2048 vs 15.0 at b = 256); its per-term wNAF table precomputation (doubled by the GLV split) dominates when the terms are used once. Surprising at first sight, but it is a table-cost effect, not an arithmetic one.
• Implementation spread for the same mathematics (Schnorr verify, laptop): pure Python src/wp34 7.4 ms → python-ecdsa (ECDSA) 419 µs → coincurve (CFFI) 12.5 µs → k256 24.5 µs → libsecp256k1 13.2 µs: a factor ≈ 560 between the pure-Python reference and C. coincurve adds ≈ 0–8 µs of FFI/object overhead (its sign_schnorr creates a keypair per call: 28.3 µs vs 20.5 µs in Rust).
• Host effect: the M5 Max is 1.25–1.35× faster than the M3 Ultra on every single-threaded operation; the speed-up curves S(b) are the same within CI on both hosts, as expected for a ratio.

# F4 — ECDSA vs Schnorr cost (known_reproduced)

In libsecp256k1 the two verifications cost the same within 5 % (12.6 vs 13.2 µs): both are one double-scalar multiplication plus hashing; Schnorr's extra cost is the tagged hash and the x-only key lift, ECDSA's the modular inversion of s. Schnorr signing is cheaper than ECDSA signing in both libraries (no inversion). Nothing here contradicts the standard comparison (BIP340 motivation section).

# Classification summary

No algebraic shortcut was sought or found in this family; every measured gain is a constant factor from a known algorithm (Straus, Pippenger, GLV) and is not a cryptographic weakness.

# Negative control and reproducibility

• Negative controls: three corrupted batches (s+1, message bit flip, r+1) rejected by all back-ends; pure-Python batch_verify likewise rejects a flipped bit (pure_python_batch_negative_control_rejected).
• Reproduce: PYTHONPATH=src .venv/bin/python experiments/signature_benchmarks/run_bench.py --seed 34 (≈ 20 s Rust + 11 s Python cross-check + 35 s Python baselines on the laptop), then summarize.py, figures/make_sig_figures.py. The crosscheck triple files produced on both hosts are byte-identical.

# Files produced today

experiments/signature_benchmarks/{sigbench/, run_bench.py, python_crosscheck.py, python_baselines.py, summarize.py, README.md}, results/signature_benchmarks/{bench_MacBookPro-de-simon-pierre-2.json, bench_MacStudnpierre2.json, summary.json, crosscheck_triples_*.json, run_*.log}, figures/{make_sig_figures.py, sig_batch_verification.pdf, sig_implementations.pdf}, tests/test_sig_crosscheck.py.

Open items for the paper: cite bernstein2012highspeed, bip340, gallant2001glv, pippenger1976, straus1964 (verify keys exist in paper/references.bib before use); a hypothesis file for B2 (hypotheses/) was not created here because this run was restricted to the directories above.