1 September 2024 | Simon Masson, Antonio Sanso, Zhenfei Zhang
Bandersnatch is a new elliptic curve constructed over the BLS12-381 scalar field, featuring an efficient endomorphism that enables a fast scalar multiplication algorithm. Benchmarks show that Bandersnatch is 42% faster, with 21% smaller R1CS circuits and 10% smaller Plonk circuits compared to Jubjub, a similar curve. Many zero-knowledge proof systems using Jubjub can benefit from this improvement.
BLS12-381 is a pairing-friendly curve used in blockchain projects for digital signatures and zero-knowledge proofs. Jubjub, an elliptic curve over BLS12-381, is not pairing-friendly but allows efficient arithmetic circuits. However, its scalar multiplication is slower than the "Bitcoin curve" (SECP256k1) due to the lack of an efficient endomorphism.
The authors' contribution is the development of Bandersnatch, an elliptic curve with a small discriminant, allowing the GLV method for efficient scalar multiplication. This was achieved through an exhaustive search of curves with small discriminant over the BLS12-381 scalar field. Bandersnatch is implemented in Rust using the Arkworks framework and is open-sourced.
Bandersnatch outperforms Jubjub in terms of circuit size for zero-knowledge proofs, requiring 2621 and 1669 constraints for group multiplication in R1CS and Plonk circuits, respectively, leading to 21% and 10% improvements.
The paper first describes how to obtain curves with the GLV method and cryptographic security. It then introduces Bandersnatch in different coordinate systems (Weierstrass, Montgomery, twisted Edwards). Finally, it compares the scalar multiplication algorithms of Bandersnatch and Jubjub from a practical perspective. The GLV method relies on an endomorphism, which is efficiently computable for curves with small discriminant. The endomorphism ring of such curves has a specific structure, enabling efficient scalar multiplication.Bandersnatch is a new elliptic curve constructed over the BLS12-381 scalar field, featuring an efficient endomorphism that enables a fast scalar multiplication algorithm. Benchmarks show that Bandersnatch is 42% faster, with 21% smaller R1CS circuits and 10% smaller Plonk circuits compared to Jubjub, a similar curve. Many zero-knowledge proof systems using Jubjub can benefit from this improvement.
BLS12-381 is a pairing-friendly curve used in blockchain projects for digital signatures and zero-knowledge proofs. Jubjub, an elliptic curve over BLS12-381, is not pairing-friendly but allows efficient arithmetic circuits. However, its scalar multiplication is slower than the "Bitcoin curve" (SECP256k1) due to the lack of an efficient endomorphism.
The authors' contribution is the development of Bandersnatch, an elliptic curve with a small discriminant, allowing the GLV method for efficient scalar multiplication. This was achieved through an exhaustive search of curves with small discriminant over the BLS12-381 scalar field. Bandersnatch is implemented in Rust using the Arkworks framework and is open-sourced.
Bandersnatch outperforms Jubjub in terms of circuit size for zero-knowledge proofs, requiring 2621 and 1669 constraints for group multiplication in R1CS and Plonk circuits, respectively, leading to 21% and 10% improvements.
The paper first describes how to obtain curves with the GLV method and cryptographic security. It then introduces Bandersnatch in different coordinate systems (Weierstrass, Montgomery, twisted Edwards). Finally, it compares the scalar multiplication algorithms of Bandersnatch and Jubjub from a practical perspective. The GLV method relies on an endomorphism, which is efficiently computable for curves with small discriminant. The endomorphism ring of such curves has a specific structure, enabling efficient scalar multiplication.