No subgroup checks performed in point validation

[guidovranken]

The following G1 point:

X: 1850443652098619803069679949935703490545934817616361671487073351271435645926537537028144222559542259604367871156773
Y: 1776970151258755586951871078535415548807448204545244204542330019247278385570277860229537378843413568111354158837149

Is on the curve but not in the subgroup. G1Element::CheckValid only performs a curve check but not a subgroup check. Is this intentional?

@dfaranha

[dfaranha]

G1Element::CheckValid actually defers the subgroup check to RELIC, which performs checks for curve and order. It turns out that the optimized check I had implemented was satisfied by points in the prime-order subgroup r but also by points with order multiple of r.

I just fixed it with 3429421e84b3a2124d8744573084c1a0ba0b729a by making the check more strict and a bit slower. I know there are papers in progress with faster techniques, so part of the performance penalty will be reverted soon.

[guidovranken]

Thanks @dfaranha

This is what blst does: https://github.com/supranational/blst/blob/48f69febca82082298f18e31509670b20f64f2ed/src/map_to_g1.c#L499-L516

Did you also check G2 subgroup checks? blst: https://github.com/supranational/blst/blob/eb6151961c133a930420e844e1a84708fbb4f6a4/src/map_to_g2.c#L403-L418

[dfaranha]

Yes, my starting point was also Bowe's ePrint, but I replaced the multiplication by (z^2 - 1) with the endomorphism. Too good to be true, I guess.

I have the same subgroup check as in blst implemented for G2.

[guidovranken]

@hoffmang9 Can you update relic to 3429421e84b3a2124d8744573084c1a0ba0b729a or later?

[hoffmang9]

I actually need Amine to update his fork first as there is a compilation related upstream issue getting worked out.

-Gene

On Aug 29, 2021, at 5:40 AM, Guido Vranken @.***> wrote:

@hoffmang9 https://github.com/hoffmang9 Can you update relic to 3429421e84b3a2124d8744573084c1a0ba0b729a or later?

— You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub https://github.com/Chia-Network/bls-signatures/issues/271#issuecomment-907785181, or unsubscribe https://github.com/notifications/unsubscribe-auth/AHHYNTFROR5LRELQH6V7ID3T7ITFNANCNFSM5CKWUNSQ.

[AmineKhaldi]

Unfortunately 3429421e84b3a2124d8744573084c1a0ba0b729a introduced the following test failure: https://github.com/Chia-Network/bls-signatures/blob/main/src/test.cpp#L478

  REQUIRE_NOTHROW( G1Element::FromByteVector(buf) )
due to unexpected exception with message:
  G1 element is invalid

377091f0e728463bc2da7d546c53b9f6b81df4a1cc1ab5bf29c5908b7151a32d
86243290bbcbfd9ae75bdece7981965350208eb5e99b04d5cd24e955ada961f8c0a162dee740be7bdc6c3c0613ba2eb1
b00ab9a8af54804b43067531d96c176710c05980fccf8eee1ae12a4fd543df929cce860273af931fe4fdbc407d495f73114ab7d17ef08922e56625daada0497582340ecde841a9e997f2f557653c21c070119662dd2efa47e2d6c5e2de00eefa
===============================================================================
test cases:   13 |   12 passed | 1 failed
assertions: 1217 | 1216 passed | 1 failed

[dfaranha]

I don't fully understand what is going on there, but I assume that the group element being tested does not have the right order?

[mariano54]

I am looking into this issue now.

[hoffmang9]

Fixed in 1.0.6 and released in chia-blockchain 1.2.6