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

perf: implement bounded scalar multiplication for GLV scalar mul #937

Open
ivokub opened this issue Nov 28, 2023 · 0 comments
Open

perf: implement bounded scalar multiplication for GLV scalar mul #937

ivokub opened this issue Nov 28, 2023 · 0 comments
Labels
consolidate strengthen an existing feature P2: Medium Issue priority: medium perf zk-evm

Comments

@ivokub
Copy link
Collaborator

ivokub commented Nov 28, 2023

This looks great! I looked into WideScalarMul for instance size 2 and I didn't neither come with a nice algorithm given the algorithms we use in ScalarMul and ScalarMulBase. For 2-chains GLV, indeed I don't think it would save constraints because the loop size there is bounded by lambda the (fixed) endomorphism eigenvalue size. Maybe for later we can try the approach of using GLV only if the scalar is uniformly random in Fr and using the bounded scalar approach if the scalar are of a particular form e.g. smaller than half lambda. But this not crucial for now and it needs benchmarking to confirm.

Originally posted by @yelhousni in #934 (review)

@ivokub ivokub added consolidate strengthen an existing feature perf zk-evm P2: Medium Issue priority: medium labels Nov 28, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
consolidate strengthen an existing feature P2: Medium Issue priority: medium perf zk-evm
Projects
None yet
Development

No branches or pull requests

1 participant