BIP342 defines OP_CHECKSIGADD as a replacement for OP_CHECKMULTISIG. In the footnote it's mentioned that OP_CHECKMULTISIG is not compatible with batch verification, but I can't understand why and I can't find any answers online. Are there any good resources that I can read?
(Asked on Twitter by Alekos Filini)
Batch verification is effectively the following. Whenever a signature check is encountered during script execution, simply remember the (pubkey, message, signature) tuple, but continue immediately without actually invoking any cryptographic verification for it. At the end of the batch (which may be for a single transaction, multiple transactions, a whole block, or even multiple blocks), all those tuples are fed simultaneously to the cryptographic verification routine, which determines whether or not all of them are valid. If one isn't valid, it gives no indication about which one(s) was invalid; only that not everything was valid.
This requires being able to predict whether the signature is intended to be successful. If the further execution of the script (or signature checks) depends in any way on the outcome of the signature checking, batch validation runs into a problem. Whenever there are multiple possible sets of permitted valid (pubkey, message, signature) tuple combinations, we would need to check all those combinations when verifying the batch. If there are multiple transactions or scripts that each permit multiple combinations, the combinations multiply. Pretty much any uncertainty would kill any advantage batch validation might have.
OP_CHECKMULTISIG is inherently incompatible with this, as such an opcode permits multiple combinations of pubkey/signature combinations. The signatures must be in the same order as the public keys, but whenever n>k, the opcode isn't fed any information about which keys are supposed to be skipped. The opcode just tries them all, in order.
To combat this problem, all signature checking opcodes in BIP342 tapscript must succeed, unless an empty signature is provided. Whenever a signature is not empty but invalid, the entire script is invalid. This allows the interpreter to know in advance which signature checks are supposed to succeed: all of the non-empty ones. As OP_CHECKMULTISIG would be useless in this context (it'd fail if anything but the first k keys match the first k signatures in order), it is removed and replaced with a slightly lower-level opcode which works for a single pubkey/signature only: OP_CHECKSIGADD.
