Replacing OP_CHECKMULTISIG(VERIFY) with OP_CHECKSIGADD

[Zedpastin]

I have a question on how TapRoot improves batch validation by replacing OP_CHECKMULTISIG(VERIFY) with OP_CHECKSIGADD, to support batch validation. I have been reading through the posts and documents supplied here: https://bitcointalk.org/index.php?topic=5140134.0

But I have been struggling to find the documentation explaining how and why this is an improvement. Is there anyone here that can explain the technical differences between OP_CHECKMULTISIG(VERIFY) and OP_CHECKSIGADD and what that means for the future of Bitcoin?

[1715012737]

1715012737

[1715012737]

1715012737

[1715012737]

1715012737

[NotATether]

OP_CHECKSIGADD's opcode looks like this: OP_CHECKSIGADD <combined public key> <n> <signature>

While OP_CHECKMULTISIG and OP_CHECKMULTISIGVERIFY opcodes take this format: <nsig> <sig1> <sig2> ... <npubkey> <pubkey1> <pubkey2> ... <dummy OP_0 value>

In segwit transactions, it appears that the public keys aren't even included in the redeem script for CHECKMULTISIG* (They're in the witness data, so disregard that). The size of the witness data, hash preimage and as a result the signed transaction is bloated as a result as the number of cosigners increases.

In contrast, OP_CHECKSIGADD only expects a 64 or 65 byte signature and 32 byte public key, so there is a massive space saving here over multisig transactions when several public keys are involved.

[gmaxwell]

CHECKMULTISIG has a stupid design where it has to use trial and error.

Say your stack looks like 0 [sig3] [sig2] 2 [pub3] [pub2] [pub1] 3  with sig3 and sig2 being signatures with pubkeys 3 and 2 respectively.

The validation will first attempt to verify with pub1 and sig2, which will fail. Then it will try pub2 and sig2 which will be successful.

This is pointlessly inefficient and in a batch validation *no* signature can fail or otherwise the whole batch fails. In something like a 1 of 20 signature every node could be forced to process 20 failing signatures just to find the one passing one.

Perhaps Satoshi had intended to use the dummy value to indicate which signatures were in use, but that was never implemented.

The checksigadd construction avoids the inefficiency and makes batch validation possible-- because no checksig(add) input is allowed to fail except for an empty signature regardless of what the surrounding script does.  It also works equally well for weighed thresholds without losing any efficiency.

[Zedpastin]

Thank you both for your great answers.

Perhaps Satoshi had intended to use the dummy value to indicate which signatures were in use, but that was never implemented.

The checksigadd construction avoids the inefficiency and makes batch validation possible-- because no checksig(add) input is allowed to fail except for an empty signature regardless of what the surrounding script does.  It also works equally well for weighed thresholds without losing any efficiency.

If Satoshi did add the dummy value you still think that this solution is better than that?

[vjudeu]

If Satoshi did add the dummy value you still think that this solution is better than that?

Yes, OP_CHECKSIGADD is still better, because you can use combined public key and as long as there is no disagreement, then one signature is enough to cover everything.

[gmaxwell]

If Satoshi did add the dummy value you still think that this solution is better than that?

I think it's better than checkmultisig with an extra field that specifies which pubkeys are in use-- because it's also easily adaptable to weighed thresholds.

[Zedpastin]

Thank you everyone for answering my questions! I am sure I will have more