<p>Batch verification is effectively the following. Whenever a signature check is encountered during script execution, simply remember the <em>(pubkey, message, signature)</em> 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 <em>all</em> 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.</p>
<p>This requires being able to predict whether the signature is <em>intended</em> 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 <em>(pubkey, message, signature)</em> 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.</p>
<p><code>OP_CHECKMULTISIG</code> 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&gt;k, the opcode isn't fed any information about which keys are supposed to be skipped. The opcode just tries them all, in order.</p>
<p>To combat this problem, all signature checking opcodes in BIP342 tapscript <em>must</em> 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 <code>OP_CHECKMULTISIG</code> 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: <code>OP_CHECKSIGADD</code>.</p>

CC BY-SA 4.0
2022-05-20T19:19:35.237Z
2022-05-20T20:03:35.223Z
2022-05-20T20:03:35.223Z
Pieter Wuille
<p>BIP342 defines <code>OP_CHECKSIGADD</code> as a replacement for <code>OP_CHECKMULTISIG</code>.  In the <a href="https://github.com/bitcoin/bips/blob/master/bip-0342.mediawiki#cite_note-4" rel="nofollow noreferrer">footnote</a> it's mentioned that <code>OP_CHECKMULTISIG</code> 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?</p>
<p>(<a href="https://twitter.com/afilini/status/1527704335416705028" rel="nofollow noreferrer">Asked</a> on Twitter by Alekos Filini)</p>

<multi-signature><schnorr-signatures><opcodes>
Why isn't `OP_CHECKMULTISIG` compatible with batch verification of schnorr signatures?
David A. Harding
# Why isn't `OP_CHECKMULTISIG` compatible with batch verification of schnorr signatures?

(Asked by: username_0 on 2022-05-20)

BIP342 defines `OP_CHECKSIGADD` as a replacement for `OP_CHECKMULTISIG`. In the [footnote](https://github.com/bitcoin/bips/blob/master/bip-0342.mediawiki#cite_note-4) 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](https://twitter.com/afilini/status/1527704335416705028) on Twitter by Alekos Filini)

**Tags:** multi-signature, schnorr-signatures, opcodes


---

## 1 answers

### Answer by username_1 on 2022-05-20. Score: 9

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`.


---

