Skip to content

perf: optimize curve membership test#487

Merged
yelhousni merged 3 commits intomasterfrom
perf/IsOnCurve
Feb 13, 2024
Merged

perf: optimize curve membership test#487
yelhousni merged 3 commits intomasterfrom
perf/IsOnCurve

Conversation

@yelhousni
Copy link
Copy Markdown
Collaborator

@yelhousni yelhousni commented Feb 13, 2024

Description

This PR optimizes the curve membership test IsOnCurve() for all curves on both G1 and G2, by:

  • saving 1 Fp mul
  • specializing the multiplication by the curve coefficient b

Type of change

  • New feature (non-breaking change which adds functionality)

How has this been tested?

Old TestG1AffineIsOnCurve and TestG2AffineIsOnCurve

How has this been benchmarked?

e.g. BLS12-381 on AWS z1d.large:

G1 335 ns vs. 190.6 ns
G2 624 ns vs. 495.3 ns

Compared to geth/kilic (cc @asanso, @MariusVanDerWijden):
G1 320.7 ns vs. 190.6 ns
G2 917.9 ns vs. 495.3 ns

Checklist:

  • I have performed a self-review of my code
  • I have commented my code, particularly in hard-to-understand areas
  • I have made corresponding changes to the documentation
  • I have added tests that prove my fix is effective or that my feature works
  • I did not modify files generated from templates
  • golangci-lint does not output errors locally
  • New and existing unit tests pass locally with my changes
  • Any dependent changes have been merged and published in downstream modules

@yelhousni yelhousni added type: perf dep: geth Issues affecting geth downstream labels Feb 13, 2024
@yelhousni yelhousni added this to the v0.10.0 milestone Feb 13, 2024
@yelhousni yelhousni requested a review from gbotrel February 13, 2024 22:00
@yelhousni yelhousni self-assigned this Feb 13, 2024
@yelhousni yelhousni requested a review from gbotrel February 13, 2024 22:39
@yelhousni yelhousni merged commit 5a54be6 into master Feb 13, 2024
@yelhousni yelhousni deleted the perf/IsOnCurve branch February 13, 2024 22:51
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

dep: geth Issues affecting geth downstream type: perf

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants