Update EIP-2537: Rephrased subgroup check part

[asanso]

trafficstars

ATTENTION: ERC-RELATED PULL REQUESTS NOW OCCUR IN ETHEREUM/ERCS

--

When opening a pull request to submit a new EIP, please use the suggested template: https://github.com/ethereum/EIPs/blob/master/eip-template.md

We have a GitHub bot that automatically merges some PRs. It will merge yours immediately if certain criteria are met:

• The PR edits only existing draft PRs.
• The build passes.
• Your GitHub username or email address is listed in the 'author' header of all affected PRs, inside .
• If matching on email address, the email address is the one publicly listed on your GitHub profile.

[eth-bot]

File EIPS/eip-2537fast_subgroup_checks.md.md

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

[asanso]

@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 https://github.com/ethereum/EIPs/pull/8274#issuecomment-1973386322. Namery IMHO we need to decide if to employ subgroup checks only for pairing or for all operations. Thoughts ?

[shamatar]

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

[shamatar]

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

[asanso]

@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]

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

@asanso I meant that we can just remove/simplify that paragraph and put compact information

• implementation MUST perform subgroup checks
• default gas schedule uses double-and-add multiplication cost as a cost of subgroup check
• nevertheless, implementers SHOULD (or at least encouraged) to use faster subgroup checks

[asanso]

default gas schedule uses double-and-add multiplication cost as a cost of subgroup check

@shamatar do we really want to go that route? For Fp2 double-and-add multiplication is super expensive and if we add subrgroup checking for any operations well gas schedule becomes prohibitive!

[shamatar]

I meant that in the current cost of pairing (and only pairing) there is an included cost of subgroup check assuming double-and-add for the check implementation. I do not refer to a global approach change to make subgroup checks mandatory, but only to rephrasing a current paragraph

[asanso]

ok my proposal is a bit wider than that. I meant to change the document mandate subgroup check to all operations as previously discussed and you seemed to agree :)

[asanso]

@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

[github-actions[bot]]

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

[shamatar]

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

[asanso]

@shamatar what exactly in that file?

[shamatar]

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

[shamatar]

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

[shamatar]

Spec is also defined to clear a cofactor

[asanso]

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

[shamatar]

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

[mratsim]

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]

https://github.com/mratsim/constantine/pull/368#issuecomment-2047473465

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