Bandersnatch/banderwagon endomorphism acceleration #380

mratsim · 2024-05-08T21:30:09Z

This implements:

endomorphism acceleration support for Twisted Edwards curves
endomorphism acceleration for Bandersnatch and Banderwagon
benchmarks for scalar multiplication and MSM

Departures from the generic derivation

λ

The endomorphism is equivalent to a scalar multiplication by a solution of λ² = -2.
There are 2 such solutions and for a generic implementation we should try
to ensure which of λ₀ = √-2 and λ₁ = -√-2 corresponds to the computation at

constantine/constantine/math/constants/zoo_endomorphisms.nim

Lines 49 to 73 in 69b8f41

 func computeEndoBander[F](r {.noalias.}: var ECP_TwEdwards_Prj[F], P: ECP_TwEdwards_Prj[F]) = 

 static: doAssert F.C in {Bandersnatch, Banderwagon} 

 var xy {.noInit.}, yy {.noInit.}, zz {.noInit.}: F 

 xy.prod(P.x, P.y) 

 yy.square(P.y) 

 zz.square(P.z) 

 const b = F.fromHex("0x52c9f28b828426a561f00d3a63511a882ea712770d9af4d6ee0f014d172510b4") 

 const c = F.fromHex("0x6cc624cf865457c3a97c6efd6c17d1078456abcfff36f4e9515c806cdf650b3d") 

 r.x.diff(zz, yy) 

 r.x *= c 

 zz *= b 

 r.y.sum(yy, zz) 

 r.y *= b 

 r.z.diff(yy, zz) 

 r.x *= r.z 

 r.y *= xy 

 r.z *= xy

This is what is done for cubic root endomorphisms:

constantine/sage/derive_endomorphisms.sage

Lines 151 to 162 in f3e08ed

 try: 

 check_cubic_root_endo(G1, Fp, r, cofactor, int(lambda1), phi1) 

 except: 

 print('Failure with:') 

 print(' 𝜑 (mod p): 0x' + Integer(phi1).hex()) 

 print(' λᵩ (mod r): 0x' + Integer(lambda1).hex()) 

 phi1, phi2 = phi2, phi1 

 check_cubic_root_endo(G1, Fp, r, cofactor, int(lambda1), phi1) 

 finally: 

 print('Success with:') 

 print(' 𝜑 (mod p): 0x' + Integer(phi1).hex()) 

 print(' λᵩ (mod r): 0x' + Integer(lambda1).hex())

constantine/sage/derive_endomorphisms.sage

Lines 84 to 112 in f3e08ed

 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 

 assert phiP^3 == Fp(1) 

 assert lambdaR^3 % r == 1 

 Prand = G1.random_point() 

 P = Prand * cofactor 

 assert P != G1([0, 1, 0]) 

 (Px, Py, Pz) = P 

 Qendo = G1([Px*phiP, Py, Pz]) 

 Qlambda = lambdaR * P 

 assert P != Qendo 

 assert P != Qlambda 

 assert Qendo == Qlambda 

 print('Endomorphism OK')

However, SageMath has no builtin support for Edwards curves so we would would need to reimplement scalar multiplication to do these checks. Hence we hardcode the λ from the paper.

Lattice decomposition

The lattice decomposition also follows the reference implementation, i.e. instead of

constantine/sage/derive_endomorphisms.sage

Lines 61 to 67 in f3e08ed

 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()

we do https://github.com/asanso/Bandersnatch/blob/e280929/python-ref-impl/bandersnatch.py#L20-L21

        M = Matrix([[-L,1], [r,0]])
        self.N = M.LLL()

This only moves signs around.

…[skip ci]

…ander curves

mratsim added 4 commits May 8, 2024 02:11

Banderwagon: lattice and Babai vectors for endomorphism acceleration …

8ece02a

…[skip ci]

refactor endomorphism acceleration to allow for twisted edwards and B…

57f1e03

…ander curves

scalar-mul: prepare for bandersnatch endomorphisms and tests

6347360

bandersnatch/wagon: fix scalar decomposition

69b8f41

mratsim added the performance 🏁 label May 8, 2024

mratsim mentioned this pull request May 8, 2024

Bandersnatch / Banderwagon endomorphism acceleration #298

Open

mratsim linked an issue May 8, 2024 that may be closed by this pull request

Bandersnatch / Banderwagon endomorphism acceleration #298

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Bandersnatch/banderwagon endomorphism acceleration #380

Bandersnatch/banderwagon endomorphism acceleration #380

mratsim commented May 8, 2024

	func computeEndoBander[F](r {.noalias.}: var ECP_TwEdwards_Prj[F], P: ECP_TwEdwards_Prj[F]) =
	static: doAssert F.C in {Bandersnatch, Banderwagon}

	var xy {.noInit.}, yy {.noInit.}, zz {.noInit.}: F

	xy.prod(P.x, P.y)
	yy.square(P.y)
	zz.square(P.z)

	const b = F.fromHex("0x52c9f28b828426a561f00d3a63511a882ea712770d9af4d6ee0f014d172510b4")
	const c = F.fromHex("0x6cc624cf865457c3a97c6efd6c17d1078456abcfff36f4e9515c806cdf650b3d")

	r.x.diff(zz, yy)
	r.x *= c

	zz *= b

	r.y.sum(yy, zz)
	r.y *= b

	r.z.diff(yy, zz)

	r.x *= r.z
	r.y *= xy
	r.z *= xy

	try:
	check_cubic_root_endo(G1, Fp, r, cofactor, int(lambda1), phi1)
	except:
	print('Failure with:')
	print(' 𝜑 (mod p): 0x' + Integer(phi1).hex())
	print(' λᵩ (mod r): 0x' + Integer(lambda1).hex())
	phi1, phi2 = phi2, phi1
	check_cubic_root_endo(G1, Fp, r, cofactor, int(lambda1), phi1)
	finally:
	print('Success with:')
	print(' 𝜑 (mod p): 0x' + Integer(phi1).hex())
	print(' λᵩ (mod r): 0x' + Integer(lambda1).hex())

	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

	assert phiP^3 == Fp(1)
	assert lambdaR^3 % r == 1

	Prand = G1.random_point()
	P = Prand * cofactor
	assert P != G1([0, 1, 0])

	(Px, Py, Pz) = P

	Qendo = G1([Px*phiP, Py, Pz])
	Qlambda = lambdaR * P

	assert P != Qendo
	assert P != Qlambda

	assert Qendo == Qlambda
	print('Endomorphism OK')

	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()

Bandersnatch/banderwagon endomorphism acceleration #380

Are you sure you want to change the base?

Bandersnatch/banderwagon endomorphism acceleration #380

Conversation

mratsim commented May 8, 2024

Departures from the generic derivation

λ

Lattice decomposition