BLS vs Secpk for ticket Sigs

[sternhenri]

Wanted to put out final thoughts on this (many from #390) ahead of making a PR (meta-note: I should have opened this issue back when these conversations were fresh. Apologies):

Why BLS?

From conversations with @nikkolasg, @whyrusleeping, @dignifiedquire :

• sizing considerations come out about even with some tradeoffs made
• timing considerations, BLS is worse; but not meaningfully so, quick back of the envelope math with BLS about 100x slower than secp to verify (which is highly conservative) means verifying a year's worth of blocks would take on the order of ~10 hours rather than dozens of minutes (nbd either way). Happy to redo the math if there is demand.
• the bulk of the reasoning was to try and use as few sigs as possible in our impl. We know we need BLS (for aggregation of trx), we may not need secp in the future.
• I had understood, if memory serves, that both had appropriately the same type of support in libraries, though indeed libsodium as used by algorand is nice.

[ZenGround0]

Thanks for opening this @henri.

@nikkolasg -- @henri tells me you are the right person to direct my concerns at regarding BLS VRF. My security concern is that the ECVRF spec is not necessarily secure when you swap out its underlying signature algorithm. I am specifically concerned with key validation which is critical for our setting and appears to be non-trivially coupled to the signature algorithm used.

I'm no expert on elliptic curve signatures and it could very well be that validating BLSVRF keys is a trivial transformation of ECVRF key validation if you know a bit more about these things. Perhaps there is a BLSVRF spec out there somewhere that I'm missing too. I just want to double check that we are not veering from the well vetted and adopted construction for non-security reasons without being totally confident in the modified construction's security.

@dignifiedquire -- I want to flag that developing a BLSVRF means writing some (might be simple or easy to copy) software beyond importing a BLS library and using the signature function. Again I'm specifically calling out key verification.

[sternhenri]

I'm going to hold off on making a PR for BLS here until I get a thumbs up to do so from @dignifiedquire @whyrusleeping or @nikkolasg assuming @ZenGround0 's concerns will have been ack'd :)

[nikkolasg]

@ZenGround0 The RFC (draft IIRC) ECVRF is not using any pairing based curves; only presenting a RSA-based VRF and a "regular" EC based VRF.
BLS is a signature scheme (brings "randomness") which is deterministic (i.e. it's the deterministic "outpout" from the regular (output, proof) VRF output). There's no BLS-VRF draft but there is BLS draft RFC https://tools.ietf.org/html/draft-irtf-cfrg-bls-signature-00 .

Regarding which BLS signature scheme to use, we want to use the latest one from Boneh which prevents against rogue key attacks when aggregation takes place: https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html - Although I'm not sure that's the one described in the RFC from a quick glance. I can look more into that but we anyway definitely want to use the latest boneh's one (https://crypto.stanford.edu/~dabo)[https://crypto.stanford.edu/~dabo]

[ZenGround0]

BLS is a signature scheme (brings "randomness") which is deterministic

I am on the same page here. I understand that BLS is deterministic and that this determinism makes constructing a VRF from BLS a reasonable idea.

we want to use the latest one from Boneh which prevents against rogue key attacks when aggregation takes place

Got it. Reiterating here, I have full confidence in the team's shared understanding around the goal to use/build and vet a secure BLS signature implementation. This issue is to call out the need to additionally construct, use/build and vet a secure VRF in the untrusted keys model using BLS as the signature primitive if we opt to use our own homegrown "BLSVRF" instead of the ECVRF.

To really reiterate the point: I am flagging the requirement that we do theoretical work to develop the process for BLSVRF key verification (separate from signature creation and signature verification) if we use BLSVRF. As stated above I'm a noob so maybe it turns out this is trivial, but because BLS is pairings based and the ECVRF key verification seems to be tightly coupled to the underlying basic EC signature construction, the process of key verification for BLSVRF is possibly quite different and maybe even requires some subtle cryptography.

If we do not adequately validate that our VRF keys are "good" then the system can be owned by a single low-resource miner who chooses a clever public/private key.

[ZenGround0]

@nikkolasg One last thing to make clear: perhaps a "rogue" key in the aggregation context is the same as a "rogue key" in the VRF context. If that's the case: awesome, the VRF work is pretty much complete when the signature work is done. Another way to think about my concern is that we need to make sure these two notions of "rogue" are the same before using the same key verification.

[nikkolasg]

Sorry I'm the one that answered too fast. I understand now that you made the reference to the "key validation" part in the RFC.
You can and must use the same validation procedure, namely the section 5.6.1 (for example with the group G2 from the BLS12-381 curves, if we choose G2 to be the group from which we derive public keys). Especially the point 3, because BLS12-381 does not have prime-order curves so we definitely need to do the cofactor check.

Even though I'm pretty confident on this, we can double check that with Ariel.

[sternhenri]

This would necessitate changes (replacing Secp with BLS) to:

• EC Spec, specifically ticket generation and running a leader election
• Mining Spec, specifically Ticket Validation and Election Validation

[sternhenri]

G1 vs G2 as sig: sizing considerations

[nikkolasg]

I did a bit of reading and the situation is more nuanced than what I originally thought.
Context: The BLS signature scheme, implemented naively, is susceptible to rogue-key attacks where an attacker can create a fake signature which can be validated by the aggregration of a victim's public key with the attacker, i.e. it can make the verifier believe that the attacker created an aggregated signature. There are different ways to protect against that:

• Enforcing distinct messages: either by doing the check manually or adding the public key in the message for example.
  • Simple to implement and fast
  • We lose the property of fast verification in case the messages to sign are similar -> every aggregation is treated as in the "different messages" case.
• Adding a proof of possession (PoP): That methods enforces that each public key is accompanied by a proof of possession, namely a signature of the public key itself with the private key. This method is described in the RFC. Usually employed when only the aggregated public key needs to be published onchain and the individuals are exchanged and verified between parties offline (multisig wallet).
  • Public keys with valid PoP can be aggregated using the normal rprocedure (fast).
  • Larger footprint on-chain (public key + pop = 2 points on the curve)
  • Dfinity is using this scheme in their implementation and Eth2.0 is probably relying on that since the specs are using the RFC (to confirm).
• Using BDN18 scheme: That method prevents the rogue key attack during the aggregation phase of the public keys. This is the one I suggested above.
  • Small footprint on chain (only public key).
  • Aggregation of public keys is slower because it uses multi-exponentiation.
  • Chia is using this scheme in their implementation.

Choice of algorithm: Now the question is which one do we want to use. My personal opinion on this is:

• If FIL already requires some kind of proof of possession, or a BLS signature that could potentially be used as a proof of possession (some kind of registration for participating?), then we should go with the PoP approach since we don't inccur any overhead and we keep the simplest and fastest aggregation procedure.
• Otherwise, the BDN18 approach is imo simply better because of the zero overhead it inccurs on chain.

Implementation: In both cases, the bls-signatures repo will have to undergo some changes since at the moment it does NOT provides any method to protect against rogue key attacks in the multi-signature aggregation context.

cc/ @sternhenri @whyrusleeping @dignifiedquire @ZenGround0

[sternhenri]

Sorry for the lag here. also adding @jzimmerman in case of interest.

I fully agree with your conclusions @nikkolasg. I don't see us needing to do aggregation on tickets (though we could imagine something down the line if we wanted to reseed randomness or something), so unless we are getting PoP for free, we should orient toward BDN18.

That said, I reckon we will need PoP in order to do aggregation elsewhere (for txs to be specific). If that's so, let's move in that direction... @dignifiedquire @whyrusleeping, can you confirm/deny?

[sternhenri]

also, super clear write-up! Thanks!

[nikkolasg]

One interesting note though: Surprisingly the BDN18 approach is NOT mentionned in the BLS RFC. I don't know why . I doubt it's because of a security issue but it could be interesting to know why it's not included.