search

lambdaclass / zksync_era_precompiles

Yul precompile library to speedup elliptic curves operations.
Apache License 2.0
51 stars 19 forks source link

Optimization of G2 subgroup check using NAF representation #266

Open IAvecilla opened 6 months ago

IAvecilla commented 6 months ago

This closes #237.

IAvecilla commented 6 months ago

The table below presents the gas usage reports for the ecpairing precompile, comparing its performance between the main branch and a proposed optimization branch.

Test/Branch main g2_subgroup_naf
ecpairing_empty_data 65473 65001
ecpairing_empty_data_insufficient_gas 65473 65001
ecpairing_one_point_insufficient_gas 3144003 3160241
ecpairing_one_point_fail 3144003 3160241
ecpairing_fuzz_negative_1 3143457 3159695
ecpairing_one_point_with_g1_zero 1631296 1646358
ecpairing_one_point_with_g2_zero 1410436 1409952
ecpairing_fuzz_negative_2 3364750 3396534
ecpairing_fuzz_negative_3 4879761 4912721
ecpairing_fuzz_negative_4 3143457 3160116
ecpairing_three_point_fail_1 6616353 6666035
ecpairing_three_point_match_1 4880704 4913664
ecpairing_two_point_fail_1 4879539 4912499
ecpairing_two_point_fail_2 4879413 4912373
ecpairing_two_point_match_1 4879611 4912571
ecpairing_fuzz_negative_5 11824649 11924497
ecpairing_two_point_oog 4879611 4912571
ecpairing_two_point_match_2 4879611 4912571
ecpairing_two_point_match_3 4879959 4912919
ecpairing_two_point_match_4 4880115 4913075
ecpairing_two_point_match_5 1631885 1646947
ecpairing_two_points_with_one_g2_zero 3144592 3160830
ecpairing_fuzz_positive_1 4879000 4913000
ecpairing_fuzz_positive_2 1411000 1411000
ecpairing_fuzz_positive_3 2074194 2120348
ecpairing_fuzz_positive_4 8351577 8417981
ecpairing_fuzz_positive_5 10087461 10170587

As observed, there appears to be a slight regression in performance with these changes compared to the implementation of the g2IsInsubgroup function in the main branch.