Rust Subgroup Checks

[kirk-baird]

Thought I'd open the issue to get the current status of subgroup checks for signatures and public keys in the rust bindings and hopefully reach a conclusion.

A quick summary of previous discussions (sorry if I've forgotten any):

1. Check subgroups on deserialisation Note: I believe this is currently what the go bindings do? Pros - simple, secure, if points are cached in BLST format the subgroup check is done once per point. Cons - if the same signature / public key is deserialised/not cached in BLST format, there are unnecessary subgroup checks

2. Always check signatures, skip public keys only on PoPVerified public keys (e.g. when calling fast_aggregate_verify() public keys are always PoPVerified). Pros - Faster deserialisation times, public keys will only be checked once Cons - Wasteful if we verify signatures then aggregate them, slower if we use public keys multiple times for non-PoPVerified methods.

3. Always check signatures and publickeys Pros - this matches the BLS Spec Cons - wasteful as points will have the subgroup checked during every use and public keys are likely used numerous times.

Personally I'm leaning towards option 1 to match the go bindings and for it's simplicity. Option 2 has a few edge cases to be weary of such as if we do fast_aggregate_verify_multiple() which multiplies a signature by random integer so we'd have to do subgroup checks before multiplication and aggregating signatures into an which individually aren't in the correct subgroup but aggregated are.

[CarlBeek]

One edge case in the bls specs itself is CoreAggregateVerify does not check the subgroup for unaggregated signatures, only the sum (see https://github.com/cfrg/draft-irtf-cfrg-bls-signature/issues/33).

I also lean towards 1 for simplicity and speed reasons. If there are speed concerns, a hybrid approach could be taken whereby in addition to the checks performed by (1), additional checks can be done right before any pairing is performed. For individual signatures this will slow things down a bit, but for aggregates, it becomes amortized over the number of signatures in the aggregate.

[alxiong]

1. Check subgroups on deserialisation Note: I believe this is currently what the go bindings do? Pros - simple, secure, if points are cached in BLST format the subgroup check is done once per point. Cons - if the same signature / public key is deserialised/not cached in BLST format, there are unnecessary subgroup checks

wait, is this true for the current status of blst? I skim through rust's binding on deserialize(pk_in: &[u8]) -> Result<Self, BLST_ERROR> which invokes blst_p2_deserialize (or p1_deserialize depending on variant), but internally, it's only checking if the group point is on the curve, but I didn't see the subgroup check.

In short, subgroup check is not included during deserialization, correct?

[dot-asm]

In short, subgroup check is not included during deserialization, correct?

Correct. Rationale is that the application is in a better position to determine when it would be more appropriate to perform the check. Thing is that it's quite an expensive operation, and it's more than appropriate to perform it in parallel and cache the result.