Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Improve performance of point equality checks #450

Merged
merged 7 commits into from
Sep 29, 2023

Conversation

jsign
Copy link
Contributor

@jsign jsign commented Sep 22, 2023

Description

This PR optimizes how point equality checks are done for G1 and twedwards. The previous code transformed points to affine points and then did equality checks requiring two inverses. The new code avoids doing inverses. (I wonder if there was a reason for the current implementation, or if I might need to include something, LMK!).

I also added benchmark codes so we can compare the old and new code.

Type of change

Please delete options that are not relevant.

  • Performance improvement

How has this been tested?

It runs all existing tests. If this equality check code change breaks the correct logic, it will probably make many tests fail.

How has this been benchmarked?

I created new benchmarks for equality checks. To test it against master, I backported them to the current master.

This was run on AMD Ryzen 7 3800XT 8-Core Processor.

For succinctness, I'll show the performance difference between BLS12-381 and Bandersnatch curves (but the implementation should fix all the other curves too).

Bandersnatch:

name                    old time/op  new time/op  delta
ProjEqual/equal-16      2.45µs ± 2%  0.07µs ± 1%  -97.26%  (p=0.000 n=10+9)
ProjEqual/not_equal-16  2.39µs ± 2%  0.04µs ± 1%  -98.51%  (p=0.000 n=10+9)

BLS12-381:

name                     old time/op  new time/op  delta
G1JacEqual/equal-16      4.95µs ± 3%  0.23µs ± 1%  -95.44%  (p=0.000 n=10+8)
G1JacEqual/not_equal-16  4.79µs ± 5%  0.11µs ± 1%  -97.61%  (p=0.000 n=9+9)

In both cases, we can see that not_equal bench is faster than equal which makes sense since we compare X first and Y afterwards. In the old code, most of the time is dominated by inverses so equal and not_equal have similar-ish perf.

Signed-off-by: Ignacio Hagopian <jsign.uy@gmail.com>
Signed-off-by: Ignacio Hagopian <jsign.uy@gmail.com>
Signed-off-by: Ignacio Hagopian <jsign.uy@gmail.com>
Signed-off-by: Ignacio Hagopian <jsign.uy@gmail.com>
Signed-off-by: Ignacio Hagopian <jsign.uy@gmail.com>
Signed-off-by: Ignacio Hagopian <jsign.uy@gmail.com>
Signed-off-by: Ignacio Hagopian <jsign.uy@gmail.com>
@ThomasPiellard ThomasPiellard merged commit ace5318 into Consensys:master Sep 29, 2023
2 of 3 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

2 participants