1

What are all the benefits of introducing OP_CHECKSIGADD in Taproot instead of OP_CHECKMULTISIG?

I assume the first benefit is the following.

For example, in pre-taproot approach, if we have 3-of-10 multisig with the scriptPubKey:

3 <pub_key1> <pub_key2> <pub_key3> ... <pub_key9> <pub_key10> 10 OP_CHECKMULTISIG

and the scriptSig (or witness stack for segWit 1):

0 <signature 5> <signature 8> <signature 10>

the problem is that for every signature in witness data check must be done over all public keys in scriptPubKey (e.g. <signature 5> must be checked for all public keys up to 5th public key where they match; same for <signature 8> and <signature 10>). Therefore, there are a lot of unnecessary checks.

This does not exist with OP_CHECKSIGADD because there is a direct check between the signature and the public key and if they match, OP_CHECKSIGAD increments the counter on the stack by 1.

That is the first benefit.

Second benefit is that a bug with one additional element that must be passed to OP_CHECKMULTISIG in order to it work has been removed.

Third is that OP_CHECKSIG/OP_CHECKSIGVERITY and OP_CHECKSIGADD now work with Schnorr instead of ECDSA.

  1. Am I right for these three benefits?
  2. Are there any other benefits?
1
  • 1
    The signatures for a OP_CHECKMULTISIG must be provided in the same order as the public keys, and each key may only sign once. So in your example, the validation process would check <signature 5> against pub_key1 through pub_key5, then <signature 8> against pub_key6–pub_key8, and finally <signature 10> against pub_key9 and pub_key10, rather than needing to start over with pub_key1 for the latter two.
    – Murch
    Nov 27, 2023 at 18:55

1 Answer 1

1

You've correctly described three of the benefits:

  • OP_CHECKMULTISIG is inefficient, since it performs up to as many signature checks as there are public keys. OP_CHECKSIGADD always performs one check per signature, since unused public keys are required to be paired with an empty witness item and are skipped.
  • Fixing the dummy stack item bug. This was partially addressed in BIP147 by requiring it to be an empty vector, which removed malleability, but since OP_CHECKSIGADD is a new opcode it can just not reimplement the bug.
  • Schnorr signatures, whose benefits are too many to describe here.

There are other benefits:

  • One other weakness of OP_CHECKMULTISIG is that it only allows up to 20 public keys. OP_CHECKSIGADD is limited to 999 public keys, as that runs into the stack limit. See for example this transaction whose input has a 998-of-999 multisig script.
  • OP_CHECKMULTISIG is incompatible with batch verification, which was the primary motivation for introducing OP_CHECKSIGADD (and disabling OP_CHECKMULTISIG[VERIFY] in Tapscript).
  • Tapscript doesn't contribute to the global sigop limit, instead allocating a sigop budget per script based on its size. This makes blocks easier to construct for miners, as optimizing for both weight and sigops is a hard optimization problem (specifically the multidimensional knapsack problem).
8
  • 2
    All of these benefits are correct, but the direct motivation is something else: the "retrying" behavior of needing to figure out which signature corresponds to which key is incompatible with batch validation - a design goal of BIP341/342. That's why BIP342 didn't just add OP_CHECKSIGADD but also disable OP_CHECKMULTISIG[VERIFY]. Nov 24, 2023 at 18:25
  • @PieterWuille Thanks, I've updated the answer. Nov 24, 2023 at 18:32
  • Thanks, just have a question. You wrote that for OP_CHECKMULTISIG it is necessary to perform as many signature checks as there are public keys. So for my example it means that 30 signature check must be performed? Is there any optimization? Like, for example: if you don't find a corresponding public key for the first signature, fail (don't try with others), or (since signatures must be in order) to continue from the public key for which you last found a match and not to always start check from the beggining?
    – Cosmos
    Nov 24, 2023 at 18:32
  • 1
    @MudjaAdjum No, at most one check will be performed for every public key. If the check fails, the next public key is checked for the same signature, and the previous public key is never checked again. Nov 24, 2023 at 18:35
  • 1
    When a signature check succeeds, it continues with both the next key and the next signature. If a signature check fails, verification with the next key, but stays on the same signature. Nov 24, 2023 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.