Miracl backend: Accelerate "KeyValidate"

[mratsim]

Currently verification incurs a significant scalar multiplication overhead due to the repeated need of validating public key.

https://tools.ietf.org/html/draft-irtf-cfrg-bls-signature-04#section-2.5

2.5.  KeyValidate

   The KeyValidate algorithm ensures that a public key is valid.  In
   particular, it ensures that a public key represents a valid, non-
   identity point that is in the correct subgroup.  See Section 5.1 for
   further discussion.

   As an optimization, implementations MAY cache the result of
   KeyValidate in order to avoid unnecessarily repeating validation for
   known keys.

   result = KeyValidate(PK)

   Inputs:
   - PK, a public key in the format output by SkToPk.

   Outputs:
   - result, either VALID or INVALID

   Procedure:
   1. xP = pubkey_to_point(PK)
   2. If xP is INVALID, return INVALID
   3. If xP is the identity element, return INVALID
   4. If pubkey_subgroup_check(xP) is INVALID, return INVALID
   5. return VALID

The pubkey_subgroup_check is costly

nim-blscurve/blscurve/miracl/bls_signature_scheme.nim

Lines 98 to 104 in 70cbdd1

	func subgroupCheck(P: GroupG1 or GroupG2): bool =
	## Checks that a point `P`
	## is actually in the subgroup G1/G2 of the BLS Curve
	var rP = P
	{.noSideEffect.}:
	rP.mul(CURVE_Order)
	result = rP.isInf()

We have 2 solutions:

1. Instead of using scalar multiplication, use Bowe19 for Miracl backend, like what BLST does, see subgroup checks via Bowe19 pairingwg/bls_standard#21

subgroup_test_g2(P)

Input: a point P
Output: True if P is in the order-q subgroup of E2, else False

Constants:
- z = -0xd201000000010000
- point_at_infinity_E2 is the point at infinity on E2

Steps:
1. pP = psi(P)
2. pP = psi(pP)
3. Q = P - pP
4. pP = psi(pP)
5. pP = z * pP
6. Q = Q + pP
7. return Q == point_at_infinity_E2

psi is already defined for clearCofactor

2. We can cache the result of "KeyValidate" as suggested in the spec, probably by introducing a CheckedPublicKey type. Note that BLST doesn't offer verification primitives that skip the subgroup check.

[tersec]

Would miracl skipping the subgroup check be faster at verifying than BLST without skipping the subgroup check?

[mratsim]

No it won't.

[mratsim]

Note: subgroup check caching was implemented for BLST in #99.
As soon we won't need Miracl for ARM32, x86_32, MIPS, PPC, Riscv5 ... this is considered low-priority.

[mratsim]

Implemented in #100