G1 MSM syscall for advanced ZK verifiers

[nzengi]

PSE-Halo2 (BN254 / KZG / SHPLONK) verifier on Solana BPF, deployed on devnet. I haven't found prior art on Solana that does this natively (without wrapping down to Groth16 first); happy to be corrected. groth16-solana, sp1-solana, and risc0-solana all use the wrap-to-Groth16 pattern.

Wanted to write this up as a discussion before turning it into a formal SIMD because there are a few design questions I'd rather hash out first. Repo: https://github.com/nzengi/Solana-Plonk

What's already on devnet

The shuffle-circuit verify-tx 5DSF3xKZ…dpZ lands at 1,372,980 CU. The tx sets set_compute_unit_limit(1_400_000) (Solana's default per-tx ceiling) and doesn't request a raise; the verifier just fits. Mollusk vs on-chain delta is 0.15 %.

Tampered-proof rejects are also on-chain. Bit-flipping a Fr eval byte gives 26Tt9UqC…WCs9 → Custom 0x200: the verifier ran the full pipeline (read_proof, lagrange, evaluate_gates, build_queries, shplonk, pairing) and the pairing equation evaluated to non-identity at the end. Only 661 CU more than the valid run, so the cryptographic check actually fired rather than bailing out early. Bit-flipping a G1 commit byte gives Custom 0x201 the alt_bn128 syscall caught the off-curve point.

The concrete problem

The shuffle path fits, but range-check (Plookup) and the larger circuits still abort at the 1.4 M cap. Per-stage profile under Mollusk:

Stage	Range-check	StandardPlonk
read_proof	149,334	258,636
lagrange::evaluate_lagrange	542,854	533,710
compute_expected_h_eval	95,975	157,993
shplonk::verify_opening	764,412	1,666,984
pairing	49,546	49,546
total	1,692,408	2,728,844

shplonk::verify_opening is 38–61 % of the cost depending on circuit shape. Its inner loop is Σᵢ scalarsᵢ · pointsᵢ over BN254 G1, done today as a sequence of alt_bn128_g1_multiplication_be calls plus the G1 additions, plus O(n²) Lagrange interpolations for the rotation-set reductions. That's exactly what a batched MSM syscall would replace.

Why pure-BPF Pippenger doesn't work

Numbers from a Mollusk bench grid (programs/g1-msm-bench/) on a fresh build, all three modes through the same harness:

n	sequential alt_bn128_g1_mul (today)	Pippenger BPF	naive BPF
2	8,558	18,188,362	12,743,035
4	17,356	33,884,582	24,988,700
8	34,964	58,145,235	49,953,590
16	70,180	heap OOM	100,083,112
32	140,616	heap OOM	199,589,804
64	281,494	heap OOM	403,144,846

Naive scalar-mul-and-add in pure BPF is past the per-tx CU cap from n = 4 (which is why alt_bn128_g1_multiplication_be exists in the first place). The reference Pippenger (crates/g1-msm-ref/) exhausts the 256 KB heap budget at n ≥ 16 the bucket-array allocations + intermediate G1Projective storage push past request_heap_frame(256_000). So if you want batched G1 MSM on Solana, it has to be a syscall.

The proposal

A new syscall next to the existing alt_bn128_g1_* family from SIMD-0284 and the proposed G2 family from SIMD-0302 (in review):

// numbering follows whichever lands first; if SIMD-0302's G2 ops take 4–6,
// this would be 7. Otherwise the next available.
pub const ALT_BN128_G1_MSM_BE: u64 = 7;

// input:  [n: u32 LE | scalars: 32B BE × n | points: 64B BE × n]  = 4 + 96n bytes
// output: 64B BE G1Affine, identity = all zeros

Grouped layout (scalars then points) maps directly to arkworks VariableBaseMSM::msm, no internal reorder. Per-point validation does the same field check + curve equation as alt_bn128_g1_multiplication_be; subgroup check is skipped, consistent with the existing G1 syscalls (BN254 G1 has cofactor 1).

Cost model (rough, agave-side bench will refine): 4_000 + n × 2_400 CU.

Component	Source
Per-point 2,400 CU	The existing alt_bn128_g1_multiplication_be is 3,840 CU/call. Native Pippenger window-NAF benchmarks (arkworks, halo2curves) typically save 30–40 % over sequential scalar-mul at n ≥ 8. 2,400 ≈ 3,840 × 0.62, the optimistic end of that range.
Base 4,000 CU	Argument deserialization, scalar reduction, window setup. Rough analog to the constant component in pairing's ~50 k base; G1 MSM is much smaller in setup cost than pairing but still larger than g1_add's 334 CU.

This beats sequential n × 3,840 + (n − 1) × 334 for n ≥ 4. At n = 2 it's a slight wrong-direction crossover (~0.97×), so callers with n ≤ 3 should keep the per-point syscall. Real numbers want an agave PR with the actual implementation benched against the existing alt_bn128 fuzz/test harness in programs/bpf_loader/; the cost model above should be treated as a starting point.

For the verifier this projects to roughly −20 % total CU and −32 % on the SHPLONK slice. Doesn't get the larger circuits (StandardPlonk, range-check) under 1.4 M alone those would still need a 2-tx split or a follow-up SIMD on the Fr-arithmetic side. But this is the highest-impact single piece, and anything doing verifier-side commitment combination on BN254 benefits: PLONK variants, folding schemes (Nova-style), batched Groth16 aggregation.

What's in the repo

• crates/g1-msm-ref/ no_std Pippenger window-NAF reference, 11/11 tests cross-checked against arkworks naive scalar-mul-and-add at n ∈ {0, 1, 2, 4, 8, 16, 32, 64}.
• programs/g1-msm-bench/ Mollusk harness that produced the table above; three modes (sequential syscall, Pippenger BPF, naive BPF).
• docs/cu_profile.md the verifier with per-stage CU profile, prior-art comparison, and the on-chain evidence list.
• docs/simd-proposals/simd-XXXX-alt-bn128-g1-msm.md full SIMD draft following SIMD-0302's structure.

A few things I'm not sure about

Input layout. I went grouped (scalars then points) because it matches arkworks and solana-bn254 ergonomics and avoids an internal reorder copy. EIP-2537 went interleaved for BLS12-381. Don't see a reason to flip but happy to.

Max n. Proposing n ≤ 1024 to bound input-deserialization DoS surface (the syscall would reject larger inputs with InvalidInputData). Could go tighter, or drop the cap and rely on tx size + CU limits.

Canonical scalar handling. Current alt_bn128_g1_multiplication_be reduces non-canonical scalars mod p. I matched that for consistency, but verifiers (this Halo2 thing, groth16-solana) often want strict-canonical rejection for input hygiene. Worth a _strict_be variant, or pick one mode?

Cost model methodology. The 4_000 + n × 2_400 numbers above are rough derived from native Pippenger amortization analysis, not measured. agave folks will want to bench the actual implementation before locking the model in. If anyone has existing Pippenger numbers in the codebase or wants to suggest a derivation methodology, that would help.

G2 MSM follow-up. Does an alt_bn128_g2_msm make sense in parallel, or is the G2 use-case rare enough that pairing-based aggregation already covers it?

If anyone from Anza or Firedancer has a strong opinion on layout or cost model, early feedback would save a review round. Otherwise happy to keep iterating here before filing a fresh SIMD PR.

[samkim-crypto]

Thanks for the write-up. Instead of adding a new altbn128 MSM syscall, I think it makes more sense to augment the existing sol_curve_multiscalar_mul syscall (here) that currently just supports curve25519. We would simply need to add support for the altbn128 curve id.

This will create some inconsistency in the list of syscalls, meaning the basic altbn128 curve ops are handled by designated syscalls while MSM is handled by a generic syscall like sol_curve_multiscalar_mul. However, adding and maintaining individual syscalls for different curves is more work and more error-prone than augmenting an existing syscall that is already designed to support multiple curves. This inconsistency can also be easily hidden from developers by the SDK library.

Given this, I think it makes sense to follow the conventions already in place for curve25519 in sol_curve_multiscalar_mul (though let me know if you think any of these require change):

• Input layout: The current curve25519 implementation takes separate pointers for the scalar and point arrays.
• Max n: The current implementation caps this at 512 (here).
• Canonical scalar handling: The current curve25519 implementation enforces strict canonical rejection. I don't think the behavioral inconsistency with the existing altbn128 syscall is a big issue, given that the SDK library can abstract it away.
• Cost model: A linear cost model is used for curve25519 as well. Generally, the exact CUs don't have to be included in the SIMD, so simply mentioning a linear cost model analogous to the curve25519 MSM should suffice.

Regarding G2, there are definitely use cases like Groth16 proof aggregation. But since G2 operations are significantly more expensive, I think it makes sense to restrict this proposal to just G1. If there is sufficient demand later, G2 can be added via a separate designated SIMD.

[nzengi]

To address your actual feedback on this SIMD proposal:

Your suggestion to augment sol_curve_multiscalar_mul instead of creating a standalone ALT_BN128_G1_MSM_BE syscall is excellent. It perfectly preserves the runtime's consistency and avoids syscall bloat.

I agree with all your points for the alt_bn128 implementation:

• Input Layout: I'll switch to separate pointers for scalar and point arrays to match the Curve25519 standard.
• Max $n$: Capping $n \le 512$ is completely fine and plenty for the current SHPLONK/Halo2 bottlenecks we are hitting.
• Canonical Checking: Enforcing strict canonical rejection is much cleaner for verifier hygiene, and as you noted, SDK libraries can easily handle the abstraction.
• Cost Model: A linear cost model aligned with the existing framework makes sense, with exact CUs left for Agave-side benchmarking.

I will refactor the draft spec in the repository to reflect this design change and open a formal SIMD PR soon. Thanks again for steering this in the right direction!

[samkim-crypto]

Any thoughts @0x0ece, @deanmlittle?

[deanmlittle]

I honestly think we should do msm, multi-miller loop and exponentiation syscalls. All of these could help accelerate a bunch of cryptographic primitives that benefit from batching and cost less than our existing single invocation syscalls.

[0x0ece]

Makes sense to me. If the need is just G1 atm let's focus on that and get it "right" (good, simple integration with arkworks). Then we can add more later.