anza-xyz / anza-xyz/solana-sdk
[BLS] Batch G2 subgroup check: benchmark results and shelved optimization
- Lenguaje dominante
- Rust
- Estrellas
- 256
- Forks
- 250
- Merge medio
- 2 d 3 h
- PR fusionados (30 d)
- 39
Descripción
## Background
cross ref: https://github.com/anza-xyz/solana-sdk/pull/652
When processing BLS signatures from the network, each G2 point (signature) must be verified to lie in the prime-order subgroup. The naive approach checks each point individually using `blst_p2_in_g2`, which costs ~28 µs per point and is trivially parallelizable.
A recent paper ([eprint.iacr.org/2025/1311.pdf](https://eprint.iacr.org/2025/1311.pdf)) describes a probabilistic batch subgroup check that replaces k individual checks with 35 multi-scalar-multiplication (MSM) rounds. For a batch of k points `g_1, ..., g_k`:
1. Sample k independent random coefficients `c_i` from `{0, ..., 12}`.
2. Compute `h = Σ c_i · g_i` via MSM.
3. Check whether `h` is in the G2 subgroup via `blst_p2_in_g2`.
4. Repeat 35 times (since `13^35 > 2^128`, soundness error < 2^-128).
## What Was Tried
**Method 1 — Direct MSM each round:** Run 35 rounds, calling `blstrs::G2Projective::multi_exp` directly on projective points with small scalars (values 0–12 wrapped in `Scalar`).
**Method 2 — Pre-computed scalar lookup table:** Pre-build a table of the 13 possible `Scalar` values so each round only does a lookup instead of a field conversion per coefficient.
## Benchmark Results (single-threaded)
| Method | k=1000 | k=2000 | k=4000 |
|---|---|---|---|
| Naive (k individual checks) | 27.9 ms | 55.8 ms | 110.8 ms |
| Method 1 (35× MSM, direct) | 32.5 ms | 54.3 ms | 97.4 ms |
| Method 2 (35× MSM, precomputed scalars) | 26.3 ms | 51.7 ms | 103.2 ms |
Profile breakdown for Method 2 at k=4000:
precompute=33ms, sample=9.7ms, select=5.5ms, affine=56.7ms, accumulate=0.75ms, subgroup=0.98ms, total=107ms
## Why It Didn't Work
The improvement is marginal (<10% at k=4000, sometimes slower at k=1000). Two root causes:
1. **MSM with small scalars is inefficient.** Coefficients in `{0,...,12}` are 4-bit scalars. MSM implementations are optimized for full 256-bit scalars; with 4-bit scalars the algorithm degenerates toward a naive linear combination and loses its asymptotic advantage.
2. **Parallelism reverses the gain.** The naive approach is embarrassingly parallel — k independent `blst_p2_in_g2` calls can be dispatched across all cores. The MSM approach has 35 sequential rounds that are harder to parallelize the same way. In a multi-threaded validator context the naive method is likely competitive or better.
## Conclusion
Shelving for now. The single-threaded speedup is too small to justify the complexity, and multi-threaded gain is expected to be negative.
Related PR with bench details: https://github.com/anza-xyz/solana-sdk/pull/652
Reference: https://eprint.iacr.org/2025/1311.pdf
Guía de contribución
No hay ninguna guía de contribución indexada para este repositorio
Evaluación
Este issue todavía no se ha evaluado.