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

Optimize variable-base scalar multiplication in the circuit #85

Open
daira opened this issue Aug 16, 2018 · 0 comments
Open

Optimize variable-base scalar multiplication in the circuit #85

daira opened this issue Aug 16, 2018 · 0 comments

Comments

@daira
Copy link
Contributor

daira commented Aug 16, 2018

Consider a 251-bit multiplication [x] P.

Edwards double-and-add requires 3252 constraints: 2 to select P or the zero point initially; 250 doublings at 5 constraints each; 250 conditional additions at 6 + 2 constraints each.

When P is large-order and x250 is set, Montgomery double-and-add requires only 2254 constraints: 2 to convert to Montgomery; 250 doublings at 4 constraints each; 250 conditional additions at 3 + 2 constraints each; 2 to convert back to Edwards.

This is a 30.7% improvement — although it is not a drop-in replacement, even if consensus compatibility were not an issue.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants