Why use BLS over Schnorr in PopProve and PopVerify?

[burdges]

Why is a BLS signature used in PopProve and PopVerify? Am I missing something?

I suppose BLS PoP save some space especially if you "aggregate" many PoPs, using their messages' distinctness. Yet, it's always much faster to verify a Schnorr PoP thought, no matter the aggregation used. I'd expect BLS deployments might download PoPs once but verify them numerous times, like upon node restarts, signer set changes, etc.

In my mind, the question was between witness (R) and challenge (c) variants for Schnorr PoP since R permits batch verification but increases Schnorr signature size for pairing friendly curves. I've leaned towards the c form because (1) cashing verification sounds vastly more important (2) pairing friendly curve crates rarely implement Pippenger right now, and (3) deserializing R can be extremely slow.

[burdges]

I'd think PoP verification should always integrate with another inner/role certificate scheme in practice, ala #27 (comment) This might go beyond the scope of this spec but maybe a comment on there being more to the message.

[mratsim]

From a practical point of view, all BLS signatures libraries have to implement BLS signatures, so it's significantly ease implementation to reuse that for PoPs.

Regarding Pippenger / multiexponentiations algorithms, implementations used for Zero-Knowledge proofs do have them:

• Aztec Barrentenberg, BN254-Snarks has multithreaded Pippenger (warning ⚠️ GPL License) + Endomorphism acceleration: https://github.com/AztecProtocol/barretenberg/blob/884c641e/barretenberg/src/aztec/ecc/curves/bn254/scalar_multiplication/scalar_multiplication.cpp
• Goff, BN254-Snarks, BLS12-377 and BLS12-381 has multithreaded Pippenger: https://github.com/ConsenSys/gurvy/blob/54ab4763/bls381/g1.go#L481-L650

However implementations used for blockchain consensus (MCL, BLST, MIRACL/Milagro) with the first 2 being reviewed or scheduled for in security audits are focused on multipairings (for now) with BLST having multithreaded multipairings support.

[burdges]

I'm aware their making progress on Pippenger, but the torsion free check in deserializing R still kills any benefit there, so c still makes sense unless someone integrates this check into PopVerify.

[kwantam]

Out of curiosity, does using a faster torsion free check like the ones described in Bowe19 revive some of the benefit of Pippenger?

As @mratsim points out, it's easier and arguably more natural to define PoP in terms of a BLS signature instead of a Schnorr proof. Obviously nothing wrong with doing it in terms of Schnorr! but it might be a hard sell to put two PoP methods in the document, especially when one needs different machinery.

[burdges]

I suggest this for performance reasons. I only mentioned the torsion free check because it swaps the optimal Schnorr form.

Also..

We might implement our BLS signatures themselves as a Schnorr DLEQ proof, meaning a single BLS signature consists of (sigma,c,s) where sigma = sk * H_2(msg) is the usual BLS signature and c = H( H(msg), pk, c * pk - s G_1, c * sigma - s H_2(msg), sigma ). We'd then verify individual BLS signatures with one G_2 point deserialization and two scalar multiplications on each of G_1 and G_2, but no pairings. We'd throw away the (c,s) once we start aggregating of course.

If we do not do this, then we'd wrap individual BLS signatures inside another Schnorr signature, which actually runs faster than the Schnorr DLEQ proof in theory. Yet, it'd require a slashing condition for when the signatures disagree, and worse assumes aggregation likes the gossip layer. Ugh! It's tricky however because one likely winds up doing Schnorr signatures on aggregate BLS signatures too, and doing a similar slashing condition for improper aggregation, so maybe the code complexity savings never materialize.

At the extreme, one finds an Edwards curve E with Cocks-Pinch whose odd prime divisor agrees with the pairing friendly curve, so then a public key consists of points on both E and G_1 with a PoP given by a Schnorr DLEQ proof from E to G_1 for them, and a BLS signature becomes a Schnorr DLEQ proof from E to G_2. This increases security somewhat too, provided you slash for improper aggregation.

[kwantam]

At the extreme, one finds an Edwards curve E with Cocks-Pinch whose odd prime divisor agrees with the pairing friendly curve, so then a public key consists of points on both E and G_1 with a PoP given by a Schnorr DLEQ proof from E to G_1 for them, and a BLS signature becomes a Schnorr DLEQ proof from E to G_2. This increases security somewhat too, provided you slash for improper aggregation.

FYI, you can do a lot better than Cocks-Pinch here---you can construct an Edwards curve with order precisely 4*p for arbitrary p.

http://arxiv.org/pdf/0904.2243v1.pdf

If this would be helpful, I have a working (but not so beautiful) implementation I could make public. (But who cares about beauty: you only need to run it once, and it's easy to verify a claimed result.)

[kwantam]

@burdges I've posted https://github.com/kwantam/eccons

Let me know if it gives you trouble. Sorry for the messy code...

---

As an example, the curve

-x^2 + y^2 = 1 + d * x^2 * y^2
d = 60912168144815564697207975035132947531112799593189986442673280194214951700554

over GF(p),

p = 209743500700504761917790962032743863350058407497631366060636747930242587818793

has a subgroup with the desired order.

[burdges]

Oh wow! cool! :)