1---2id: H133title: BIP340 batch verification reduces per-signature cost by a factor that grows with batch size and saturates4axis: B5kind: algorithmic6statement: Verifying b signatures with random 128-bit weights and a multi-scalar multiplication costs per signature a decreasing7 function of b, with speed-up ≈ 2× at b = 16 and ≈ 3× or more at b ≥ 256, without changing consensus semantics.8motivation: Research question B2.9assumptions: Random weights; lift_x cost included.10expected_contribution: Measured curve with CI on two hardware platforms; operation counts of the MSM.11related_work:12- bernstein2012high13- wuille2020bip34014- naccache1994can15- bellare1998fast16- pippenger1980evaluation17possible_counterexamples: No speed-up (would indicate an MSM implementation issue).18verification_strategy: experiments/signature_benchmarks/sigbench (k256 arithmetic), negative control with one invalid signature.19computational_budget: ≈ 30 min20status: evaluated21classification: known_reproduced22evidence:23- results/signature_benchmarks/summary.json24- results/signature_benchmarks/bench_MacBookPro-de-simon-pierre-2.json25- results/signature_benchmarks/bench_MacStudnpierre2.json26verdict: 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];27 1.67× vs libsecp256k1 single verify); Straus plateaus at ≈ 2×; ≈ 3 µs/sig of non-MSM work (lift_x, tagged hash) caps the28 gain; negative control rejected; same shape on M3 Ultra.29---3031# H13 — BIP340 batch verification reduces per-signature cost by a factor that grows with batch size and saturates3233Verifying 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.34