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:

constantine/sage/derive_endomorphisms.sage

Lines 61 to 67 in 5f7ba18

	def derive_lattice(r, lambdaR, m):
	lat = Matrix(matrix.identity(m))
	lat[0, 0] = r
	for i in range(1, m):
	lat[i, 0] = -lambdaR^i
	return lat.LLL()

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:

constantine/sage/derive_endomorphisms.sage

Lines 84 to 94 in d77bb79

	def check_cubic_root_endo(G1, Fp, r, cofactor, lambdaR, phiP):
	## Check the Endomorphism for p mod 3 == 1
	## Endomorphism can be field multiplication by one of the non-trivial cube root of unity 𝜑
	## Rationale:
	## curve equation is y² = x³ + b, and y² = (x𝜑)³ + b <=> y² = x³ + b (with 𝜑³ == 1) so we are still on the curve
	## this means that multiplying by 𝜑 the x-coordinate is equivalent to a scalar multiplication by some λᵩ
	## with λᵩ² + λᵩ + 1 ≡ 0 (mod r) and 𝜑² + 𝜑 + 1 ≡ 0 (mod p), see below.
	## Hence we have a 2 dimensional decomposition of the scalar multiplication
	## i.e. For any [s]P, we can find a corresponding [k1]P + [k2][λᵩ]P with [λᵩ]P being a simple field multiplication by 𝜑
	## Finding cube roots:
	## x³−1=0 <=> (x−1)(x²+x+1) = 0, if x != 1, x solves (x²+x+1) = 0 <=> x = (-1±√3)/2

[mratsim]

Implemented in #380