Skip to content

perf: ELM03+Joye07 for emulated scalarMul #760

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.

Sign up for GitHub

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

Jump to bottom
Merged
yelhousni merged 1 commit into from
Jul 17, 2023
Merged

perf: ELM03+Joye07 for emulated scalarMul #760

yelhousni merged 1 commit into from
Jul 17, 2023

Conversation

@yelhousni
Copy link
Contributor

@yelhousni yelhousni commented Jul 5, 2023

Actually with more select logic and since we are using affine formulas, we can turn double-and-add to add-only while skipping some computations. This PR trades off the y-coordinate computation of the second addition for a select. This would correspond to Alg.1' [Joye07] + [ELM03].

new bench

ecrecover (r1cs):  303521
ecrecover (scs):  1455938
ecmul (r1cs):  183756
ecmul (scs):  876507

old bench

ecrecover (r1sc):  365237
ecrecover (scs):  1767044
ecmul (r1sc):  244988
ecmul (scs):  1183191

@yelhousni yelhousni added type: perf dep: linea Issues affecting Linea downstream labels Jul 5, 2023
@yelhousni yelhousni added this to the v0.9.0 milestone Jul 5, 2023
@yelhousni yelhousni requested a review from ivokub July 5, 2023 10:28
ivokub
ivokub approved these changes Jul 13, 2023
View reviewed changes
Copy link
Collaborator

@ivokub ivokub left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks good. Great one!

@yelhousni yelhousni merged commit f2d37a5 into develop Jul 17, 2023
@yelhousni yelhousni deleted the perf/emulated-scalarMul branch July 17, 2023 10:24
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@ivokub ivokub ivokub approved these changes

Assignees

No one assigned

Labels

dep: linea Issues affecting Linea downstream type: perf

Projects

None yet

Milestone

v0.9.0

Development

Successfully merging this pull request may close these issues.

3 participants

@yelhousni @ivokub