Bandersnatch, GLV and fakeGLV: Pectra optimal BLS12-381 arithmetic for ZK Dapps

(Electra, taming the ZK power of a wild Bandersnatch)

Introduction

Ethereum's update PECTRA comes in the next weeks as an important update bringing evolutivity and security improvements. Among those, the integration of BLS12-381 in clients opens up perspectives for elliptic curves primitives (such as multi/threshold signatures) and zero-knowledge applications. Examples are private payments (as designed by Railgun), ZKPassports, ZKTLS and ZKWebauthn over the deprecated altbn_128.

This blogpost describes how to optimize elliptic curve operations in the context of PECTRA update, with a focus on Bandersnatch. In particular, a technique mixing FakeGLV and GLV over Bandersnatch is provided, leading to the most efficient in-circuit verification algorithm over BLS12-381 to date. More general tricks for generic curves (ZKPassport, ZKTLS, ZKWebAuthn) are also discussed.

Those optimizations will lead to a reduction around 40% (asymptotically) of the ECC proving cost (being around 3.5 seconds on a phone, it would fell below 2). Find some benchmarks by Distributed Labs here.

Pectra

From BN254 to BLS12-381

BN254 is an elliptic curve that has been widely used in zero-knowledge (ZK) cryptography due to its efficiency and small parameter size, but it only provides around 100 bits of security, which is insufficient for modern cryptographic applications. For stronger security guarantees, another curve, BLS12-381, has been designed together with ZK properties. This curve fulfills approximately 128 bits of security, making it more resistant to potential future attacks. While it requires slightly larger parameters and computational overhead compared to BN254, the tradeoff is well worth it for applications that need stronger cryptographic assurances. Therefore, shifting from BN254 to BLS12-381 is a prudent choice for improving the security of zero-knowledge systems. Pectra integrates precompiles for the arithmetic of this curve (see EIP-2537). In a recent post Distributed Labs provides some insight on the prover complexity which, are not very far from its less secure version. Those complexity are however in a range where linear improvements are felt by the user (a few seconds).

Cryptographic primitive above BLS12-381

In the context of zero-knowledge proofs, it is sometimes required to compute elliptic curve arithmetic that will be, later on, verified in-circuit using BLS12-381. It is common to choose an elliptic curve designed to make ZK proofs efficient, called embedded curves. The curve is selected so that the verification algorithm involves native arithmetic for the ZK proof circuit. For BLS12-381, the ZK circuit is defined modulo a prime r (which is BLS12-381 scalar field order). In this context, an embedded curve is defined over 𝔽_r. While in-circuit verification is made efficient by this choice of base field, signature generation must also be fast in specific use-cases. Two curves have been designed for this purpose: Jubjub and Bandersnatch. The latter has been designed so that scalar multiplications are more efficient. Next section dig into the details of elliptic curve scalar multiplications in order to understand the benefits of Bandersnatch.

Elliptic curve arithmetic

Elliptic curves are used in cryptography to construct secure key exchange protocols and digital signatures, leveraging their algebraic structure to provide strong security with relatively small key sizes.

Scalar multiplication (SM)

The critical algorithm used in cryptography based on elliptic curves (ECC) is the scalar multiplication. Given a scalar k (usually of 256 bits), and a point P of the curve, the point [k]P is computed using the group law defined on the curve. This computation depends on the model used for the curve, but the cost is about 2log₂(k) point additions. Cost details are skipped in order to keep the description as simple as possible.

Multi-scalar multiplication (MSM)

In signature verification, it is common to compute multi-scalar multiplications (MSM) [k]P + [ℓ]Q for scalars k, ℓ < r. After precomputing P + Q, it is possible to compute [k]P + [ℓ]Q in only 2log₂(r) point additions, by reading simultaneously the bits of k and ℓ. More generally, a n-MSM $\sum_{i=1}^n [k_i]P_i$ can be computed in 2ⁿ − n − 1 precomputation additions, and 2log₂(r) additions for the simultaneous computation. From now, MSM(n, N) denotes the cost in elliptic curve additions of a multi-scalar multiplication of n points with scalar of N bits: MSM(n, N) ≈ 2ⁿ − n − 1 + 2N. Note that in practice, additional operations are required and not taken into account in this blog post.

Fixed point SM

When P is fixed, above technique can be used in order to speed-up a SM: precomputing P_i = [2^iN/n]P and $k = \sum_{i=1}^n k_i 2^{iN/n}$, we can decompose $[k]P = \sum_{i=1}^n [k_i]P_i$. This technique works in practice, but the precomputation part becomes expensive as long as n grows, as illustrated in the following table (where the costs are estimated in point additions, with the simplified formula above):

In the case of signature verification for an account, where the public key is the fixed point, this speed up can be used. It is implemented in efficient libraries, such as BOLOS, FCL and OpenZeppelin P256 libraries (leading to their reduced gas cost compared to Daimo), and SCL generic one. This algorithm is also the scope of RIP7696. Unfortunately, in the context of zero-knowledge circuits, this technique is not possible.

Fake-GLV: a hinted verification in ZK.

Zero-knowledge proofs are widespread cryptographic tools in blockchain, and one expensive computation is the scalar multiplication. In this context, the public key is kept as a secret input. Hence, it is not possible to use the fixed point MSM algorithm.

In ZK circuits,the assumption to prove is that [k]P = Q, where Q is a hinted point (provided as additional helper input). FakeGLV was recently introduced by [YEH] using a fractional decomposition of k = u/v mod r, found by reducing the lattice defined by the rows of
$$\begin{pmatrix} r & 0\\k & 1 \end{pmatrix}$$
Indeed, a vector (x, y) of this lattice satisfies x = ky mod r. Using lattice reduction, it is expected to find a small vector of norm around $1.16\sqrt{r}$. In consequence, it is possible to find u, v of 128 bits (for our targeted curve Bandersnatch) and to compute [k]P = Q ⇔ [u]P − [v]Q = 0. In this context, the scalar multiplication can be verified in-circuit in MSM(2, 128).

Bandersnatch combines this decomposition together with the GLV optimization.

Bandersnatch

Bandersnatch is an embedded curve for BLS12-381, such as Jubjub, which was designed so that it has an efficiently computable endomorphism. This structure enables faster scalar multiplications.

GLV optimization

Small discriminant curves have a specfic structure that speeds up the scalar multiplication: there exists an (efficiently computable but non trivial) endomorphism ϕ that has an eigenvalue λ on the points of order r defined over 𝔽_p. It results that k can decomposed as k = k₁ + λk₂ mod r with log₂(k_i) = 128, and the cost of a scalar multiplication is thus obtained using MSM(2, 128): [k]P = k₁P + k₂ϕ(P). This techniques was originally developed in 2001 and is for example implemented in Bitcoin's signatures.

GLV hinted verification

The technique presented in [YEH] can be combined with the GLV optimization, as mentioned byn Liam Eagen here. The scalar k can thus be decomposed as
$$k = \frac{u_1+λu_2}{v_1+λv_2}\bmod r$$
using a reduction of the lattice defined by the rows of
$$ \begin{pmatrix} r & 0 & 0 & 0\\ -λ & 1 & 0 & 0 \\ 0 & 0 & -λ & 1\\ k & 0 & 1 & 0 \end{pmatrix} $$
In this case, using lattice reduction, it is expected to find a vector with coefficients bounded by $1.22\sqrt[4]{r}$. Finally, a scalar multiplication is verified using
[k]P = Q ⇔ [u₁]P + [u₂]ϕ(P) − [v₁]Q − [v₂]ϕ(Q) = 0
with a cost of MSM(4, 64) in the case of Bandersnatch. This bound is slightly bigger for other r (for instance, 65 bits for seckp256k1).

higher dimension in-circuit MSM

If circuits are used for validity and not privacy, then it is possible to use MSM. When applying the previous technique for multi-scalar multiplications, it is possible to reduce the cost of a 2-MSM (and more generally a n-MSM). However, the gain is not significant in R1CS due to lookups cost for native curves. It has a potential outcome for non native, such as P256 as used by ZKMAIL, ZKWebAuthn.

Proof of concept implementation

ZKNOX repository provides a proof of concept of these algorithms in the context of Bandersnatch. In particular, this file implements the decomposition using the four-dimensional lattice and then the verification of [k]P = Q using a 4-MSM with scalars of 64 bits. Although this technique is useful in-circuit, we provide here an proof of concept to illustrate the efficiency gain. In particular, we provide an example of lattice decomposition:

k = 8809196524735054409598625807987834789941239467291111440141961710399690321154 (253 bits)
u1 = -4721629758273561887 (64 bits)
u2 = 4445070398100683295 (62 bits)
v1 = -968749169646434063 (61 bits)
v2 = 2866665739561707568 (62 bits)

A benchmark is also provided for demonstration (although the implementation is not optimized), achieving around 40% improvement for Bandersnatch. We are now looking for an in-circuit implementation, together with Youssef El Housni. Note that Fake GLV is already implemented in gnark here and the combined GLV+Fake GLV is done here, but the decomposition is done differently (using a partial extended gcd algorithm), leading to higher scalars and thus a slightly larger proving time.

Use cases

Private wallets, Privacy pools

All cryptographic primitives that can be converted into zero-knowledge schemes should be implemented using Bandersnatch. Railgun enables privacy in Ethereum using a ZK construction with BabyJubjub and the pairing-based curve BN254. This will be updated to work with Bandernsatch and BLS12-381 in order to reach a state of the art security level as well, without loss of efficiency.

ZKWebAuthn, ZKTLS and ZKPassports

ZKPassports and ZKWebAuthn are systems that allow users to prove ownership of an authenticated ID (resp. Passkey credential) without revealing the actual ID content, metadata, or even the ID itself (resp. credentials). During authentication, the server sends a challenge, signed by the user, but instead of the signature, a ZK proof of the signature is sent and then verified onchain.

Conclusion

This note described several optimizations to improve both security and UX (reducing the prover computations, i.e the latency of the phone/laptop) for the most popular ZK applications. While GLV remains restricted to small discriminant curves (such as Bandersatch), the FakeGLV + 2MSM technique can be applied (with a lower gain) to generic curves. The provided python code is a first step before developing the circuits for an integration into proving backends. When moving to BLS12-381, Bandersnatch outperforms Jubjub and is a better choice in terms of efficiency.

Acknowledgments

The FakeGLV technique is an original idea from Youssef El Housni. Combining it with GLV has been discussed in ethresearch by Liam Eagen. The developments into ZK backend are currently in progress with Consensys and the techniques are being formalized into a research paper.

🚀 Let's future-proof Ethereum together!

Reach us

🔐 Practical security on the whole chain.

Github | Website | Twitter | Blog | Contact Info

Found typo, or want to improve the note ? Our blog is open to PRs.