batch verification
https://www.btcstudy.org/2021/12/06/schnorr-applications-batch-verification/
Schnorr signature variant Elliptic Curve Schnorr signatures for message m and public key P generally involve a point R, integers e and s picked by the signer, and the base point G which satisfy e = hash(R || m) and s⋅G = R + e⋅P. Two formulations exist, depending on whether the signer reveals e or R:
- Signatures are pairs (e, s) that satisfy e = hash(s⋅G - e⋅P || m). This variant avoids minor complexity introduced by the encoding of the point R in the signature (see paragraphs "Encoding R and public key point P" and "Implicit Y coordinates" further below in this subsection). Moreover, revealing e instead of R allows for potentially shorter signatures: Whereas an encoding of R inherently needs about 32 bytes, the hash e can be tuned to be shorter than 32 bytes, and a short hash of only 16 bytes suffices to provide SUF-CMA security at the target security level of 128 bits. However, a major drawback of this optimization is that finding collisions in a short hash function is easy. This complicates the implementation of secure signing protocols in scenarios in which a group of mutually distrusting signers work together to produce a single joint signature (see Applications below). In these scenarios, which are not captured by the SUF-CMA model due its assumption of a single honest signer, a promising attack strategy for malicious co-signers is to find a collision in the hash function in order to obtain a valid signature on a message that an honest co-signer did not intend to sign.
- Signatures are pairs (R, s) that satisfy s⋅G = R + hash(R || m)⋅P. This supports batch verification, as there are no elliptic curve operations inside the hashes. Batch verification enables significant speedups