# Bandersnatch

*by Simon Masson (Anoma - https://anoma.network/) and Antonio Sanso (Ethereum Foundation - https://ethereum.foundation/)*

This document describes the details of **Bandersnatch** a new elliptic curve built over the BLS12-381 scalar field. The curve is similar to Jubjub but is equipped with the GLV endomorphism hence it has faster scalar multiplication.

## BlS12-381 and Jubjub

BLS12-381 is a pairing friendly curve created by Sean Bowe in 2017. Currently BLS12-381 is universally recognized as **THE PAIRING CURVE** to be used *given our present knowledge* (cit.).

The ZCash team also introduced a new curve built over the BLS12-381 scalar field: Jubjub.

JubJub is a twisted Edwards curve that can be made efficient inside of the zk-SNARK circuit.

## Introducing Bandersnatch

In order for some cryptographic application to scale it is needed to have a curve like Jubjub but with faster scalar multiplication. One efficient way to speed scalar multiplication up is to employ the celebrated GLV endomorphism (also used by the *“Bitcoin curve”* - secp256k1). This technique was until few months ago protected by a US Patent that is now expired and freely usable.

We performed an exhaustive search of curves where the GLV endomorphism could be used over the BLS12-381 scalar field using the Complex Multiplication (CM) method of generating an elliptic curve. To be more specific we computed the order of such curves for the discriminants from -1 to -388.

We found one suitable curve for discriminant -8 with order 2^2\cdot 13108968793781547619861935127046491459309155893440570251786403306729687672801 Bandersnatch is also twist secure: the order of the twist is 2^7 \cdot 3^3 \cdot 15172417585395309745210573063711216967055694857434315578142854216712503379

The curve has j-invariant equal 8000 and exhibits 125.75 bit security . Given the shape of the order it can be expressed also in Montgomery and Edward form.

Bandersnatch in twisted Edwards form looks like

-5x²+y² = 1+dx²y² with d=\frac{138827208126141220649022263972958607803}{171449701953573178309673572579671231137}.

### Bandersnatch’s endomorphism

The endomorphism of degree 2 is defined by

\psi(x,y,z) = (xa_1(y+a_2z)(y+a_3z), b_1(y+b_2z)(y+b_3z)yz^2, (y+c_1z)(y+c_2z)yz^2)

and can be computed in 17 multiplications and 6 additions modulo p (a_i, b_i, c_i are integers modulo p).

### Scalar multiplication improvement

From the efficient endomorphism \psi, it is easy to apply the GLV method and improve the scalar multiplication cost:

- Roughly, a scalar multiplication [n]P cost (\log n) \text{Dbl} + (\log n/2) \text{Add}.
- Using the GLV endomorphism, we can compute [n]P using (\log n/2 )\text{Dbl} + (3\log n/8) \text{Add}, plus few precomputations.

We performed `python`

benchmarks between the double-and-add algorithm and the GLV method applied in the case of our curve, and the GLV version is **30% faster**.

**Acknowledgments:** we would like to thank Luca De Feo, Justin Drake, Dankrad Feist, Daira Hopwood and Zhenfei Zhang for fruitful discussions.