On-chain BLS signature verification

[mhluongo]

We need to be able to verify single and threshold signatures on-chain. Aggregated signature verification would also be great, though it appears to be too expensive for practical use without new precompiled contracts.

Getting this to done, I'd like to see

• Detailed documentation
• Go signing proof-of-concept
• Solidity verification proof-of-concept
• Naive gas cost analysis (mostly the pairings check)
• Test vectors

Once we're there, the BLS verification implementation can be pulled out into its own lib.

[mhluongo]

Ethereum has pre-compiled (re: cheaper) contracts for addition, scalar multiplication, and a pairing check on bn128, which appears to be a poorly named version of the bn256 curve. Note the bn256 curve provides something like 100-110 bits of security- bn128 appears to be named after the 128 bits of security bn256 would provide without accounting for certain classes of attack.

BLS can run on what we will henceforth call bn256 with some modifications- in particular, we need to use an asymmetric type-3 pairing rather than the type-1 pairing as used in the original description of BLS.

[mhluongo]

The Dfinity Barreto-Naerig and BLS library appear to support the necessary curve. We'll have to make sure we use bn256 going forward for anything that needs to be verified on chain (cc @Shadowfiend).

[mhluongo]

Now, here's where it get tricky. It appears that verifying BLS "multisig" (note: in traditional cryptography multisig means n-of-n) and threshold signatures (t-of-n) require two pairings checks, and aggregate signatures verification requires O(n).

We need to confirm that understanding. If the threshold verification only requires two, happy day- we can make this work on Ethereum. Even better if we can get it down to one- I've seen references to BLS implementations where G_1 = G_2 that only require a single pairing check to verify, though I have no idea whether there are tradeoffs or whether that scheme fits the above requirements.

Signature aggregation requiring O(n) checks means any schemes we come up with where clients sign off- eg to show a public key came from them- will become impossible on-chain for many situations. For example, for all group members to sign a new threshold key, we'd have 200 +/- pairing checks required to confirm a new group. I haven't checked, but I'll be very surprised if that fits in a single Ethereum block.

If that is the case, anywhere where we need significant signature aggregation will instead need to use a challenge-based mechanism, or some other trick like a verified circuit that has "cached" the aggregated signature verification off-chain, speeding up the on-chain verification step.

[mhluongo]

On the gas cost of the pairing check -> https://github.com/ethereum/go-ethereum/blob/5bbd7fb390a539a7183bccc5f2b75b4e564ed398/core/vm/contracts.go#L348

[Shadowfiend]

So after some spelunking, I don't think this necessarily means what we think it means… And indeed I don't think what the EIP implements matches what the Go BLS lib exposes for use with bn.

First off, if we look at where the bn256 namespaces is referenced in the bn code, it's actually used or not used based on a preprocessor directive = compile-time setting:

https://github.com/keep-network/bn/blob/181e0679edcd42c847bda59a5e2016174f942696/mcl/src/bn_c_impl.hpp#L11-L20

Also worth noting, if we use the 256-bit config, we only support this curve setting:

https://github.com/keep-network/bn/blob/master/mcl/include/mcl/bn.h#L80-L89

And, this is not the default build setting:

https://github.com/keep-network/bn/blob/181e0679edcd42c847bda59a5e2016174f942696/bls/Makefile#L8-L11

Additionally, the fact that there is a CurveSNARK1 CurveParam in bn (one that isn't exposed through the BLS Go library), and that the EIP explicitly mentions SNARK as the goal makes me think what the EIP implements and what we're looking at here are not the same thing, and that none of the exposed BLS curves match what the EIP is using. This is also my reading of the note on libsnark about Elliptic curve choices:

The underlying curve implementation is [ate-pairing], which has incorporated our patch that changes the BN curve to one suitable for SNARK applications.

The curve identifiers used in BN seem to be from this IETF document on BN curves. However, herumi's older library ate-pairing specifically distinguishes between CurveSnark and CurveFp254BNb, and mentions the former is from libsnark, which is also referenced from the EIP. A closer look at libsnark reveals the b coefficient and the z exponent are the same as the ones in bn's CurveSnark (which differ from the one in CurveFp254BNb).

Net-net… I think we're going to have to do some work if we want to use the same curve supported in the EIP, and we'll need to figure out if we're comfortable with it.

[mhluongo]

I got a little optimistic that bn's bn256 module was what we wanted, but I hadn't checked the curve params. I'll dig in as well.

The big question is whether libsnark's curve matches the EVM's. A conversation I had the other day with the author led me to believe not, but we can go deeper 🐰

[Shadowfiend]

Parameters seem the same, if differently named:

• b: var curveB = new(big.Int).SetInt64(3)
• xi_a: where ξ = i+9
• z: var u = bigFromBase10("4965661367192848881")

EDIT: The same as CurveSnark in bn, that is.

[mhluongo]

Right, I'm talking about the actual Ethereum curve though. Checking to see which that matches.

[Shadowfiend]

The above links are to the go-ethereum repo :)

[mhluongo]

Ohh the links in the code formatting are fancy! Also I need coffee.

[mhluongo]

CurveSNARK in bn appears to work fine with the BLS implementation (single sig, verify)- unsure whether the bn implementation is a type 3 construction though. Digging deeper.

[Shadowfiend]

Also worth checking if the threshold sig works (by plugging it into the guard tower stuff)? The other Bn curve didn't seem to.

[Shadowfiend]

unsure whether the bn implementation is a type 3 construction though

My confusion there is basically… The pairing construction should be the same irrespective of curve parameters, no? Or are those two entangled somehow? Or are we saying the bn pairings aren't type 3 constructions for any curve?

[mhluongo]

I'm not sure whether bn supports the proper BLS construction- separate from the curve choice. When I tried this curve with the threshold sig I did have issues, but I didn't spend much time on it. The bigger issue with bn is that I've had to write our own hash function to G1 to be able to implement it in Solidity with reasonable gas costs. If we're rewriting that function- which is core to the sig- I think it's faster to reimplement BLS on top of geth's crypto lib and dig into using bn later.

[pdyraga]

@mhluongo @ngrinkevich This is no longer research work - we have a part of it implemented and now we are integrating the rest of the code on-chain, correct?

[pdyraga]

Moving it to Feb '19 board. Please correct me if I am mistaken about the scope of this issue and the outstanding work.

[pdyraga]

We will need to adjust off-chain protocol to produce public key as G2. Also, we'll need to update key marshalling logic to output full compressed G2 point.

[pdyraga]

Moving to Sprint 1 (Feb 11th-Feb15th)