Closed mratsim closed 3 years ago
Would miracl skipping the subgroup check be faster at verifying than BLST without skipping the subgroup check?
No it won't.
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.
Implemented in #100
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
The
pubkey_subgroup_check
is costly https://github.com/status-im/nim-blscurve/blob/70cbdd16e00d15a6556e84552012b9a368cacb56/blscurve/miracl/bls_signature_scheme.nim#L98-L104We have 2 solutions:
Input: a point P Output: True if P is in the order-q subgroup of E2, else False
Constants:
Steps:
pP = psi(P)
pP = psi(pP)
Q = P - pP
pP = psi(pP)
pP = z * pP
Q = Q + pP
return Q == point_at_infinity_E2
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.