# 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):

| b | own Pippenger | own Straus (wNAF-5) | k256 lincomb_vartime | k256 lincomb (ct) |
|---|---|---|---|---|
| 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) |
| 16 | 24.9 µs (0.99) | 12.9 µs (1.90) | 14.8 µs (1.65) | 22.5 µs (1.09) |
| 128 | 12.8 µs (1.92) | 12.2 µs (2.01) | 15.3 µs (1.60) | 21.9 µs (1.12) |
| 256 | 11.3 µs (2.16) | 12.4 µs (1.98) | 15.0 µs (1.63) | 21.8 µs (1.12) |
| 1024 | 8.6 µs (2.84) | 12.7 µs (1.93) | 15.8 µs (1.55) | — |
| 2048 | **7.9 µs (3.10 [3.05, 3.16])** | 13.4 µs (1.82) | 17.1 µs (1.43) | — |

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

| finding | classification | note |
|---|---|---|
| batch verification speed-up (F1) | `known_reproduced` | BIP340 text; Bernstein et al. 2012 (Ed25519) |
| speed-up cap from lift_x + hash floor (F2) | `empirical_observation` | measured constants, standard cost model |
| library / implementation spread, k256 signs faster, libsecp256k1 verifies faster (F3) | `empirical_observation` | implementation, not mathematics |
| ECDSA ≈ Schnorr verification cost (F4) | `known_reproduced` | |

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.