Switch from BN254 to BLS12-381

[ebfull]

Our zk-SNARKs currently rely on BN254, a pairing-friendly Barreto-Naehrig curve construction over a 254-bit base field. After some recent optimizations to the NFS algorithm, our team did an analysis to understand the concrete security level of BN254.

@zooko's conclusion:

Okay, done! We've understood the concrete security level BN_128. Answer: everyone agrees that it is at least 110 bits, and either everyone or almost-everyone agrees that if you counted all of the costs it would be at least 128 bits.

Pairing-friendly curves are inherently more susceptible to advances in crypto research due to their small embedding degrees, so although the BN curve is currently good enough there is wisdom in adopting current academic recommendations wherever possible.

Sapling is a great opportunity to switch to a more secure pairing curve, since our protocol currently doesn't depend on the underlying curve, and we're considering many changes to the protocol which will. Switching later will be irritating, as it will require re-implementing everything again: new embedded curves, new hash functions, etc. We can buy more time by switching now when it's not as painful.

I've designed a new curve construction called BLS12-381 which targets 128-bit security given current recommendations.

Performance of BLS12-381

Currently, Zcash uses the BN254 implementation inside of libsnark, with USE_ASM disabled. I have recently implemented BLS12-381 in Rust.

Here are some preliminary benchmarks run on my i7-3770S:

As you can see, my implementation of BLS12-381 (which doesn't use any unsafe{} code or any hand-optimized assembly) is faster than the implementation of BN254 that we currently use in Zcash.

In fact, due to the small Hamming weight of its parameterization and its more efficient extension field tower, its G2 and pairing performance are on par with libsnark's assembly-optimized code that we don't use. This makes adopting BLS12-381 a strict performance improvement in all areas, without the auditing cost of assembly optimization.

Here are my current benchmarks:

BLS12-381 (Rust):
    G1 addition: 1,249 ns/iter
    G2 addition: 4,141 ns/iter
    Full pairing: 2,557,330 ns/iter
        G1 precomputation: 12,894 ns/iter
        G2 precomputation: 223,809 ns/iter
        Miller loop: 606,379 ns/iter
        Final exponentiation: 1,696,878 ns/iter

libsnark USE_ASM off:
    G1 addition: 1,366 ns/iter.
    G2 addition: 6,509 ns/iter.
    Full pairing: 4,199,397 ns/iter.
        G1 precomputation: 3,102 ns/iter.
        G2 precomputation: 540,984 ns/iter.
        Miller loop: 1,339,208 ns/iter.
        Final exponentiation: 2,332,928 ns/iter.

libsnark USE_ASM on:
    G1 addition: 900 ns/iter.
    G2 addition: 3,990 ns/iter.
    Full pairing: 2,627,332 ns/iter.
        G1 precomputation: 3,002 ns/iter.
        G2 precomputation: 338,027 ns/iter.
        Miller loop: 838,821 ns/iter.
        Final exponentiation: 1,437,695 ns/iter.

ate-pairing:
    G1 addition: 735 ns/iter.
    G2 addition: 1,897 ns/iter.
    Full pairing: 659,231 ns/iter.
        G1 precomputation: 2,615 ns/iter.
        G2 precomputation: 91,191 ns/iter.
        Miller loop: 216,609 ns/iter.
        Final exponentiation: 346,264 ns/iter.

Obviously, ate-pairing is way faster, but it relies on dynamic code compilation and tons of tricky optimizations. Hence, we don't use it in Zcash.

Security of BLS12-381

BLS12-381 follows the recommendations of several papers that pairing-friendly curves with embedding degree 12 should be instantiated over approximately 384-bit fields. (BN curves are thus unacceptable for us, because they will have exceedingly large scalar fields.)

BLS12-381 is also a far more rigid construction; it is part of a subfamily of BLS curves that have optimal extension field towers, simple twisting isomorphisms, and immediately determined curve parameters. It is the largest curve that meets our requirements for zk-SNARK efficiency, and so it's likely that others would arrive to the same curve as well.

The same cannot be said of BN254, which was chosen without respect to pairing and G2 performance.

Matthew Green and Ian Miers had Paulo Barreto and Diego Aranha, both experts in these curves, take a look at the BLS12-381 construction. Diego even implemented it in his RELIC library. It is also slated to appear in an upcoming academic paper.

Implementation of BLS12-381

As I previously mentioned, I have an implementation of BLS12-381 in Rust. This implementation follows over a year of refinement, testing, and auditing in which I uncovered several bugs in libsnark, one of which was a subgroup attack vulnerability (now fixed) and others that could have manifested as remote DoS. I carefully avoid some of the mistakes made in libsnark's BN254 implementation.

I'm also automatically testing my implementation on 64-bit and 32-bit Linux/Windows.

I'm not entirely finished with this implementation, but when I'm finished it should have strong guarantees against memory safety problems and API misuse, without the portability problems of libsnark's curve implementations. It already has and will continue to accrue extensive test coverage.

[daira]

Concept ACK.

I assume that the recent improvements to libsnark's multiexp algorithm (using the simplification of Pippenger's algorithm) are orthogonal to the choice of curve, and haven't yet but could be applied to the Rust implementation?

[daira]

Let's not forget that BLS12-381 comes also along with an inner curve (that I called Ed255-Jubjub here) which we intend to use for Pedersen hashes and commitments, and possibly note encryption. The security of that curve also needs to be analysed, although it does not need to be pairing-friendly so is subject to fewer design constraints.

[ebfull]

I assume that the recent improvements to libsnark's multiexp algorithm (using the simplification of Pippenger's algorithm) are orthogonal to the choice of curve, and haven't yet but could be applied to the Rust implementation?

Indeed, the choice of curve does not affect that algorithm.

[nathan-at-least]

I've removed this from DevInfra project. It seems to fit Sapling much better. The Dev Infra tasks that might be associated, though, are adding proper CI support to test the switch. I assume those tickets will come later in the process.

[nathan-at-least]

It sounds like this construct has review from a couple of domain experts, two implementations, and the performance and security benefits described above. We're proceeding with this curve for the Sapling upgrade, barring surprises.

[arielgabizon]

References for recent security recommendations from bls-12 curves to obtain 128 bit security

According to the extremely conservative estimates of https://eprint.iacr.org/2017/334.pdf,
see 2.2 together with 7.2 there.
We would need an ever larger field - 462 bits (to be precise they recommend this field size for the 128 bit security level but say you get 131.8 security bits with it)

https://eprint.iacr.org/2016/1102.pdf , page 18, which are also very conservative in my opinion.
Say 384 bits are enough - slightly more than the 381 bits here.

[daira]

The difference between 381 and 384 bits is neither here nor there. (Note that our current construction targets 126-bit security, not 128.)

https://eprint.iacr.org/2017/334.pdf claims (table 8) that the G_T field size needs to be 5530 bits for BLS12, which is really very conservative indeed.

[ebfull]

Note that we can't go much larger than BLS12-381 without blowing past our performance budget. It was hard enough to get the curve implementation faster than libsnark despite the fact the curve is bigger.

[ebfull]

I wanted to point out a neat coincidence: 381/3 = 127, and 127*2 = 254. 254 bits is the capacity of the scalar field. This means that Fq multiplications/squarings inside the circuit (for things like #2425) can be achieved through elegant 127-bit limb arithmetic.

[ebfull]

I've just published a work-in-progress implementation of BLS12-381:

https://github.com/ebfull/pairing

At this point, it merely needs more testing and implementations of serialization. Once those are done, I will make it 1.0 and solicit reviews. Everything else can be built on top, including the new multiexp, wNAF, FFTs, etc.