File EIPS/eip-2537fast_subgroup_checks.md.md

Requires 1 more reviewers from @axic, @g11tech, @gcolvin, @lightclient, @SamWilsn, @xinbenlv

@shamatar, @ineffectualproperty, @ralexstokes I rephrased a bit the subgroup check section including the fast subgroup check.
Once we are on it, I would like to continue the discussion started in #8274 (comment).
Namery IMHO we need to decide if to employ subgroup checks only for pairing or for all operations.
Thoughts ?

The nature of suggestion is great, but now phrasing mentioning double and add and subgroup check is misleading. If you just say that

• one must check
• one should use fast subgroup checks
• default gas pricing assumes naive double-and-add multiplication

it'll be clear enough

Separately on mandatory checks: if no one found any use case when out of group elements are interesting for multiplication/addition then we can make subgroup checks mandatory iff fast subgroup checks are also mandatory. Of course, gas schedule will change, but most likely change will only be substantial for G1 add

@shamatar thanks for the comment.

The nature of suggestion is great, but now phrasing mentioning double and add and subgroup check is misleading.

any suggestion on the words to use ? the "double-and-add" part was already present in the original text

@shamatar I adjusted the text to include ALL the calls and added a new separate document (similar to the existing one for hash to curve) in https://github.com/asanso/EIPs/blob/patch-9/assets/eip-2537/fast_subgroup_checks.md .

Thoughts ? cc @ineffectualproperty @ralexstokes

The commit 1f129eb (as a parent of 9271b4d) contains errors.
Please inspect the Run Summary for details.

Actually I found an example where we may need to allow out-of-main-subgroup points https://github.com/ethyla/bls12-381-hash-to-curve/blob/main/src/readable_Hash_to_curve.sol

@shamatar what exactly in that file?

It's a full hash-to-curve implementation (starting from byte string and then using field element -> curve point precompile). I'm checking how is map-to-curve specified now. If it clears a cofactor internally then such case would not be applicable, but as far as I remember it's not.

Full author's comment https://ethereum-magicians.org/t/eip-2537-bls12-precompile-discussion-thread/4187/60

At least my implementation clears a cofactor for fp-to-g1. Now checking the spec

Spec is also defined to clear a cofactor

So one reason more to work in the subgroup for all the operations correct ?

Kind of. I think original IETF draft for mapping to curve suggests to get two points, add them and then clear cofactor, that makes sense because clearing cofactor is amortized this way. But if we want to keep a number of exposed precompile function manageable, we can build-in those cofactor cleanups.

My only concern is at some point we will see a use case where secondary subgroup point is needed. Yes, it's hard to produce it in EVM because precompiles will give only main subgroup, but I do not claim a knowledge of all possible cases

I've also mentioned concerned about subgroup checks here: https://ethereum-magicians.org/t/eip-2537-bls12-precompile-discussion-thread/4187/63

The issue is that without them, libraries cannot use endomorphism acceleration or the result will be wrong. They might also not be able to use projective coordinates with complete formula (from Renes 2015), though Jacobian coordinates would work OK.

As mentioned in https://ethereum-magicians.org/t/eip-2537-bls12-precompile-discussion-thread/4187/66, there are 3 paths ahead:

1. No change approach. no subgroup check, price like double-and-add and Pippenger today and add test vectors. For MSMs, in both Gnark and Constantine, endomorphism acceleration was not a problem or was even slower due to probably decomposition overhead + memory bandwidth / hardware cache limitations (at least on x86, Apple memory likely behaves differently).
2. Misuse resistance approach. See @asanso, enforce subgroup check except on addition.
3. Modular approach or performance approach, provide subgroup_check and clear_cofactor as separate primitives. People can cache subgroup_checks and ensure their cost is only paid once. Issue: they need to learn what a subgroup and cofactor is.

Some important point is that for large MSMs, endomorphism acceleration doesn't help, hence subgroup check cost is paid in vain. For single scalar mul, it represents about 1/3 (G1) and 1/5 (G2) more operations. (benchmarks in the link)

I do agree with @asanso that having them on all operations is reasonable due to the risk of some crypto libraries defaulting to endomorphism acceleration and outputting wrong result.

mratsim/constantine#368 (comment)

For @asanso on gas pricing

gas costs in ratio of G1 scalarmul

original: https://gist.github.com/mratsim/6785a29e72865cfa94e1174fae1e1168

Reproduction

git clone https://github.com/mratsim/constantine
cd constantine
git checkout eip2537
CC=clang nimble bench_eip2537_subgroup_checks_impact