-
-
Notifications
You must be signed in to change notification settings - Fork 43
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
Bandersnatch / Banderwagon endomorphism acceleration #298
Comments
Hey Mamy, I spent some time trying to tackle this issue and I have some knowledge gaps. I was not familiar with endomorphism so I read about it and came across GLV endomorphism through this paper. I was able to understand that - One part of the scalar is multiplied by the original point, and the other part is multiplied by a specially chosen point on the curve that is related to the original point through the endomorphism. The results of the two scalar multiplications are then combined to obtain the final result of the scalar multiplication. Am I approaching this issue the correct way? Is there any implementation of endomorphism acceleration that I can refer? |
Yes you are correct, if you want to collaborate with me on this issue, hmu on discord. |
As mentioned on Discord, I have an old Sage code here to actually see it working in practice: https://github.com/mratsim/constantine/blob/eee0f4f0fc5283ecb807f6756203df2819d0210f/sage/lattice_decomposition_bls12_381_g1.sage The description of what is happening is there: constantine/sage/derive_endomorphisms.sage Lines 84 to 94 in d77bb79
|
Implemented in #380 |
Scalar multiplication and Multi-scalar-multiplication for Bandersnatch and Banderwagon can be improved by 30% by adding endomorphism acceleration.
See:
Impl direction
We need to derive the lattice used for splitting a scalar as a linear combination of the endomorphism base.
This is done here:
constantine/sage/derive_endomorphisms.sage
Lines 61 to 67 in 5f7ba18
It seems like it should match the input of the LLL here:
https://github.com/asanso/Bandersnatch/blob/e280929/python-ref-impl/bandersnatch.py#L20-L21
The text was updated successfully, but these errors were encountered: