1# 2026-11-01 — Research Axis B: ECDSA / BIP340 Schnorr benchmarks (questions B2, B5)23**Research question.** B2: can BIP340 verification be accelerated without changing consensus4semantics (batch verification)? B5: which implementation choices produce measurable differences?5**Null hypothesis (B2).** Batch verification gives no per-signature saving over single verification6at any batch size. **Alternative.** The per-signature cost decreases with b and saturates.78**Setup.** `experiments/signature_benchmarks/sigbench` (Rust 1.95/1.96, rust-secp256k1 0.33.1 →9libsecp256k1 via secp256k1-sys 0.14.1, k256 0.14.0, elliptic-curve 0.14.3, ecdsa 0.17.0, wnaf 0.14.1),10seed 34, 7 repetitions × ≥ 2000 operations per measurement, single thread, bootstrap CI with 200011resamples. Two hosts: laptop (Apple M5 Max, 18 cores, macOS 27.0) and cluster node M3U96a12(Apple M3 Ultra, 28 cores, macOS 26.6). Results: `results/signature_benchmarks/bench_MacBookPro-de-simon-pierre-2.json`,13`bench_MacStudnpierre2.json`, `summary.json`, logs `run_laptop.log`, `run_m3u96a.log`.14Commands are stored in each JSON (`command`, `params.rust_command`). Synthetic keys only.1516## Correctness gates (both hosts, identical because the RNG is seeded)1718- BIP340 official vectors: 19/19 verification outcomes and 8/8 byte-identical signatures with19 **both** libsecp256k1 and k256 (vectors 5–14 with invalid keys / r ≥ p / s ≥ n / wrong parity all20 rejected as expected).21- Cross-library: 1000/1000 k256-signed ECDSA signatures verified by libsecp256k1 and vice versa;22 same for Schnorr; **1000/1000 byte-identical** in both schemes (RFC 6979 nonces for ECDSA, the23 BIP340 aux-rand nonce derivation for Schnorr — deterministic by construction).24- Python reference (`src/wp34`, exact integer arithmetic): 200/200 Rust signatures verified for all25 four (scheme × library) combinations, 200/200 re-signed identically in pure Python, 200/200 tampered26 signatures rejected. `tests/test_sig_crosscheck.py` passes (2 tests, also checks the Python27 reference against the 19 vectors independently of Rust).28- Own MSM: Straus with one term agrees with k256 on 64 scalar multiplications; batch negative29 controls (s+1, flipped message bit, r+1 inside a batch of 64) rejected by all four MSM back-ends,30 while the unmodified batch is accepted.3132## Findings3334### F1 — Batch verification speed-up (classification: `known_reproduced`)3536Per-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 a37function of b (laptop; M3U96a shows the same shape at ×1.3 cost):3839| b | own Pippenger | own Straus (wNAF-5) | k256 lincomb_vartime | k256 lincomb (ct) |40|---|---|---|---|---|41| 1 | 91.9 µs (S 0.27) | 30.4 µs (S 0.81) | 25.1 µs (S 0.97) | 38.5 µs (S 0.64) |42| 16 | 24.9 µs (0.99) | 12.9 µs (1.90) | 14.8 µs (1.65) | 22.5 µs (1.09) |43| 128 | 12.8 µs (1.92) | 12.2 µs (2.01) | 15.3 µs (1.60) | 21.9 µs (1.12) |44| 256 | 11.3 µs (2.16) | 12.4 µs (1.98) | 15.0 µs (1.63) | 21.8 µs (1.12) |45| 1024 | 8.6 µs (2.84) | 12.7 µs (1.93) | 15.8 µs (1.55) | — |46| 2048 | **7.9 µs (3.10 [3.05, 3.16])** | 13.4 µs (1.82) | 17.1 µs (1.43) | — |4748S = speed-up versus a single k256 `verify_raw` (24.5 µs); versus libsecp256k1's single verify49(13.2 µs) the best point is **1.67 [1.65, 1.68]** (M3U96a: 3.03 [3.00, 3.04] and 1.58). The null50hypothesis is rejected for every back-end at b ≥ 4 (CIs exclude 1); the gain saturates. This is the51expected behaviour described in the BIP340 text ("batch verification ... up to a factor of 2") and52measured for Ed25519 by Bernstein, Duif, Lange, Schwabe and Yang (2012); our numbers reproduce the53known result in k256 arithmetic and do not constitute a new algorithm. Op counts (per signature,542b + 1 terms): Straus plateaus at ≈ 79 projective additions + 2 doublings per signature exactly as55predicted by wNAF-5 density (≈ 256/6 + 7 table additions for the 256-bit P_i term, ≈ 128/6 + 7 for56the 128-bit R_i term); Pippenger at b = 2048 (c = 8) uses 47.8 mixed additions + 8.0 additions +570.1 doublings per signature, i.e. about 0.7× the group operations of Straus, which is the whole58source of its advantage.5960### F2 — The attainable speed-up is capped by the per-signature non-MSM work (`empirical_observation`)6162The MSM-only time falls to 4.9 µs/sig (laptop, b = 2048) but the total is 7.9 µs/sig: ≈ 3.0 µs per63signature (3.6 µs on M3U96a) is spent outside the MSM — `lift_x(r)` (one square root = a 255-bit64field exponentiation), the tagged SHA-256 challenge hash and the scalar parse. Single verification65pays the same hash but no square root for R (it compares x-coordinates). Hence the asymptotic66speed-up is bounded by (single verify) / (non-MSM floor + MSM/sig), roughly 4–5× in this arithmetic67even with an ideal MSM — consistent with the saturation seen above. This is a well-understood cost68model, reported here with measured constants.6970### F3 — Library choice matters more than batching (`empirical_observation`)7172- libsecp256k1 verifies ≈ 2× faster than k256 (ECDSA 12.6 vs 25.0 µs; Schnorr 13.2 vs 24.5 µs on the73 laptop), consistent with its 5×52-bit field representation, GLV + wNAF strategy with effective-affine74 precomputation and years of tuning. Conversely **k256 signs faster** than libsecp256k1 (ECDSA 15.3 vs75 23.6 µs; Schnorr 11.6 vs 20.5 µs): rust-secp256k1's signing path goes through the blinded,76 constant-time `ecmult_gen` (19.8 µs for a generator multiplication through `PublicKey::from_secret_key`)77 whereas k256's `mul_by_generator` uses a 30 kB fixed table (8.3 µs; 6.6 µs in variable time). This78 was not anticipated and is worth stating in the paper as an implementation-choice effect, not a79 mathematical one.80- Scalar multiplication (laptop): own wNAF-5 double-and-add without GLV 21.1 µs (257 doublings +81 52 additions); k256 constant-time with GLV 16.4–17.2 µs; k256 variable-time GLV + wNAF 14.0 µs;82 libsecp256k1 `ecmult_const` 11.5 µs. The GLV endomorphism therefore buys ≈ 1.3–1.5× here, in line83 with Gallant–Lambert–Vanstone (2001). GLV is not switchable from either public API; this is stated84 in the JSON (`scalar_mult.glv_note`).85- k256's own `lincomb_vartime` is slower than our naive Straus for b ≥ 8 and degrades for large b86 (17.1 µs/sig at b = 2048 vs 15.0 at b = 256); its per-term wNAF table precomputation (doubled by the87 GLV split) dominates when the terms are used once. Surprising at first sight, but it is a table-cost88 effect, not an arithmetic one.89- Implementation spread for the same mathematics (Schnorr verify, laptop): pure Python `src/wp34`90 7.4 ms → python-ecdsa (ECDSA) 419 µs → coincurve (CFFI) 12.5 µs → k256 24.5 µs → libsecp256k1 13.2 µs:91 a factor ≈ 560 between the pure-Python reference and C. coincurve adds ≈ 0–8 µs of FFI/object overhead92 (its `sign_schnorr` creates a keypair per call: 28.3 µs vs 20.5 µs in Rust).93- Host effect: the M5 Max is 1.25–1.35× faster than the M3 Ultra on every single-threaded operation;94 the speed-up curves S(b) are the same within CI on both hosts, as expected for a ratio.9596### F4 — ECDSA vs Schnorr cost (`known_reproduced`)9798In libsecp256k1 the two verifications cost the same within 5 % (12.6 vs 13.2 µs): both are one99double-scalar multiplication plus hashing; Schnorr's extra cost is the tagged hash and the x-only key100lift, ECDSA's the modular inversion of s. Schnorr signing is cheaper than ECDSA signing in both101libraries (no inversion). Nothing here contradicts the standard comparison (BIP340 motivation section).102103## Classification summary104105| finding | classification | note |106|---|---|---|107| batch verification speed-up (F1) | `known_reproduced` | BIP340 text; Bernstein et al. 2012 (Ed25519) |108| speed-up cap from lift_x + hash floor (F2) | `empirical_observation` | measured constants, standard cost model |109| library / implementation spread, k256 signs faster, libsecp256k1 verifies faster (F3) | `empirical_observation` | implementation, not mathematics |110| ECDSA ≈ Schnorr verification cost (F4) | `known_reproduced` | |111112No algebraic shortcut was sought or found in this family; every measured gain is a constant factor113from a known algorithm (Straus, Pippenger, GLV) and is **not** a cryptographic weakness.114115## Negative control and reproducibility116117- Negative controls: three corrupted batches (s+1, message bit flip, r+1) rejected by all back-ends;118 pure-Python `batch_verify` likewise rejects a flipped bit (`pure_python_batch_negative_control_rejected`).119- Reproduce: `PYTHONPATH=src .venv/bin/python experiments/signature_benchmarks/run_bench.py --seed 34`120 (≈ 20 s Rust + 11 s Python cross-check + 35 s Python baselines on the laptop), then `summarize.py`,121 `figures/make_sig_figures.py`. The crosscheck triple files produced on both hosts are byte-identical.122123## Files produced today124125`experiments/signature_benchmarks/{sigbench/, run_bench.py, python_crosscheck.py, python_baselines.py, summarize.py, README.md}`,126`results/signature_benchmarks/{bench_MacBookPro-de-simon-pierre-2.json, bench_MacStudnpierre2.json, summary.json, crosscheck_triples_*.json, run_*.log}`,127`figures/{make_sig_figures.py, sig_batch_verification.pdf, sig_implementations.pdf}`, `tests/test_sig_crosscheck.py`.128129Open items for the paper: cite `bernstein2012highspeed`, `bip340`, `gallant2001glv`, `pippenger1976`,130`straus1964` (verify keys exist in `paper/references.bib` before use); a hypothesis file for B2131(`hypotheses/`) was not created here because this run was restricted to the directories above.132