Bandersnatch / Banderwagon endomorphism acceleration

[mratsim]

Scalar multiplication and Multi-scalar-multiplication for Bandersnatch and Banderwagon can be improved by 30% by adding endomorphism acceleration.

See:

• https://eprint.iacr.org/2021/1152.pdf
• https://ethresear.ch/t/introducing-bandersnatch-a-fast-elliptic-curve-built-over-the-bls12-381-scalar-field/9957
• https://github.com/asanso/Bandersnatch

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: https://github.com/mratsim/constantine/blob/5f7ba18f2ed351260015397c9eae079a6decaee1/sage/derive_endomorphisms.sage#L61-L67

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

[namn-grg]

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 - The GLV endomorphism decomposes a scalar into two smaller scalars. This decomposition is done in such a way that the scalar multiplication can be split into two smaller scalar multiplications.

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?

[agnxsh]

Yes you are correct, if you want to collaborate with me on this issue, hmu on discord.

[mratsim]

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: https://github.com/mratsim/constantine/blob/d77bb79a41b7920505f1915454c802f4d8c1977c/sage/derive_endomorphisms.sage#L84-L94

[mratsim]

Implemented in https://github.com/mratsim/constantine/pull/380