anza-xyz / anza-xyz/solana-sdk

[BLS] Batch G2 subgroup check: benchmark results and shelved optimization

Abierto
#658 0 comentarios 0 reacciones 1 asignado Reclamado por @zz-sol Ver en GitHub
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.

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.