id: H13 title: BIP340 batch verification reduces per-signature cost by a factor that grows with batch size and saturates axis: B kind: algorithmic statement: Verifying b signatures with random 128-bit weights and a multi-scalar multiplication costs per signature a decreasing function of b, with speed-up ≈ 2× at b = 16 and ≈ 3× or more at b ≥ 256, without changing consensus semantics. motivation: Research question B2. assumptions: Random weights; lift_x cost included. expected_contribution: Measured curve with CI on two hardware platforms; operation counts of the MSM. related_work:
- bernstein2012high
- wuille2020bip340
- naccache1994can
- bellare1998fast
- pippenger1980evaluation possible_counterexamples: No speed-up (would indicate an MSM implementation issue). verification_strategy: experiments/signature_benchmarks/sigbench (k256 arithmetic), negative control with one invalid signature. computational_budget: ≈ 30 min status: evaluated classification: known_reproduced evidence:
- results/signature_benchmarks/summary.json
- results/signature_benchmarks/bench_MacBookPro-de-simon-pierre-2.json
- results/signature_benchmarks/bench_MacStudnpierre2.json verdict: Per-signature cost falls from 24.5 µs (single, k256) to 7.9 µs at b = 2048 with Pippenger (S = 3.10 [3.05, 3.16]; 1.67× vs libsecp256k1 single verify); Straus plateaus at ≈ 2×; ≈ 3 µs/sig of non-MSM work (lift_x, tagged hash) caps the gain; negative control rejected; same shape on M3 Ultra.
H13 — BIP340 batch verification reduces per-signature cost by a factor that grows with batch size and saturates
Verifying b signatures with random 128-bit weights and a multi-scalar multiplication costs per signature a decreasing function of b, with speed-up ≈ 2× at b = 16 and ≈ 3× or more at b ≥ 256, without changing consensus semantics.