Add support for BLS12

[JanBobolz]

Besides BN254, we should also implement support for BLS12_381.

Ressources:

• https://github.com/herumi/mcl/blob/master/ffi/java/com/herumi/mcl/MclConstants.java - this constant is input to InitSystem.
• Issue saying that BLS seems to be faster than BN: https://github.com/zcash/zcash/issues/2502
  • discussion may also contain useful knowledge for our case.

[rheitjoh]

I was hoping to be able to use both pairings at once, but it seems like that won't be possible since the pairing is initialized statically and so calling SystemInit with the second pairing type will essentially undo initialization of the first pairing type.

You can "hack" your way around this as done here by including bn.hpp in two different namespaces, but that is not possible for the Java FFI I think.

[rheitjoh]

My plan so far was to implement two BilinearGroupProvider and BilinearGroupImpl classes, one for each curve type. The rest of the classes should be reusable.

The problem is of course deciding how to deal with the "cannot use both at once" problem.

One way would be to call Mcl.SystemInit each time you use a method of a class that uses the other curve type so that you basically switch the Mcl library between the curve types whenever necessary. A quick benchmark indicates that a call of SystemInit takes around 350 microseconds. To compare: Group operations in the Mcl groups take between 1 and 5 micro seconds. So we would need to make sure that the switching does not happen too often.

A second option would be to basically check for the curve type in each group method, and throw an exception if it does not match. The user would then have to explicitly switch the current curve type used by Mcl if they want to switch between the curve types. This way we would not have any hidden performance costs as branch prediction should take care of the if condition. The user would need to be aware of this though.

Alternatively, if BLS12 381 is really faster than BN254, so just better in general, we could just completely replace BN254 with BLS12 381 and avoid any extra complexity. The security level is higher too, so I think I like this option. I haven't yet done a performance comparison of the two approaches though.

[rheitjoh]

I have compared the average time of the group operations for BN254 and BLS12_381 with the following results:

Benchmark	(curve)	Mode	Cnt	Score	Error	Units
BN254VsBLS12381.measureGroup1Op	bn254	avgt	24	1.218	± 0.308	us/op
BN254VsBLS12381.measureGroup1Op	bls12_381	avgt	24	1.785	± 0.445	us/op
BN254VsBLS12381.measureGroup2Op	bn254	avgt	24	2.536	± 0.770	us/op
BN254VsBLS12381.measureGroup2Op	bls12_381	avgt	24	4.582	± 0.511	us/op
BN254VsBLS12381.measureGroup3Op	bn254	avgt	24	3.127	± 0.518	us/op
BN254VsBLS12381.measureGroup3Op	bls12_381	avgt	24	4.669	± 0.144	us/op
BN254VsBLS12381.measurePairing	bn254	avgt	24	462.066	± 3.301	us/op
BN254VsBLS12381.measurePairing	bls12_381	avgt	24	1357.187	± 12.612	us/op

BLS12 381 being slower in the mcl library seems to match the benchmarks here(I assume the clk unit stands for clock cycles). I guess this excludes the idea of completely replacing our BN254 wrapper with a BLS12 381 one. There is still reason to use BLS12 381 if you want a higher security level, of course.

[JanBobolz]

After initializing bn, doing some operations resulting in a group element g, then initializing bls, then initializing bn again - does g still "work" (i.e. can we do operations on it)?

[rheitjoh]

You can, yes. I think the initialization just changes some parameters in Mcl. You can even initialize the group element in BN254, then change the group to BLS12, and the string representation of the element will change with the change of curve (So Mcl is just interpreting the element differently).

[JanBobolz]

Alright. I'd argue for the "auto switch" solution:

• In normal applications, heavy group switching will never happen (if we fear that it might, we could output a warning to syserr every 100 group switches to make people aware). Usually, you set up a group and stay with it.
• For performance tests (e.g., I want to check how my scheme fares with group x or y), I guess this could become an issue for some setups. For those, the warning will probably suffice.
• If we threw an exception for group switches, this will break, for example, all our tests (which will usually test both) and make it impossible to ever compare performance between both groups within a single JVM run (for the sake of, if the test is properly written, a single 350ms error term during setup).

[rheitjoh]

If we threw an exception for group switches, this will break, for example, all our tests (which will usually test both) and make it impossible to ever compare performance between both groups within a single JVM run (for the sake of, if the test is properly written, a single 350ms error term during setup).

You would of course reinitialize Mcl for the different tests so that would not be an issue. Exception would only be thrown on a mismatch (the group stores which curve type is meant to be initialized right now) which you can just avoid by calling init beforehand. So that should not affect anything in that regard, I think.

[rheitjoh]

I do agree that group switching should not usually be a problem, 350 us is still pretty cheap, even if you can fit a hundred group operations in it.

The only way I see group switching becoming an issue is if you have some kind of larger system where multiple schemes are operating and some are using BLS12 (for the security level) and some are using BN254 (for the better performance in Mcl). Plus they would have to switch quite frequently. I guess this could happen with interleaved execution?

[JanBobolz]

I guess this could happen with interleaved execution?

Oh. This is a good point. If we want to guarantee safety (in the sense that no computation is ever done on the wrong group), we'd strictly speaking have to do some multithread-locking/synchronization to guarantee that initialization doesn't change while some other operation is being computed / between auto-switching. That looks like a performance hit to me.

I may be flipping my vote to "throw an exception if someone is trying to reinitialize mcl". That's very much suboptimal, but I'm not willing to sacrifice what I believe (without evidence) to be a decent chunk of performance.

Alternatively, it would of course be cool if we could just load two copies of mcl and initialize one with bn and one with bls. But as you've said: that doesn't seem to be easy to do.

[wdcs-amitkumar]

Hi !!

I am new to BLS12 381 and need your guidance ::

• Currently EVM does not have precompiled contract to support bls12-381 operations.
• But is it possible that we can verifify BLS12 381 signature in solidity by hard coding values ??

[wdcs-amitkumar]

Can we implement all those operation in Solidity and verify signature ??

[JanBobolz]

Sorry amitcz, we’re using BLS strictly outside of smart contracts and are not familiar with those details. My blind guess is you can implement signature verification without explicit native support for the BLS curve, but it will likely be relatively inefficient. No guarantees that any of this is true, though.

This issue has been fixed by #38.