Are there permanent solutions to address OP_CHECKMULTISIG bugs?

[Felicity_Tide]

I recently started looking into multi signatures when I learnt that the OPcode some how contains a bug that isn't considered much as a bug because of the application of a dummy for temporary solution.

So far, I've tried to understand what multi-sig comprises of, which a 2 of 3 was practically what I studied with.

For an ideal 2 of 3, we have the following as the locking script

Code:

2<pubkey1><pubkey2><pubkey3>3 OP_CHECKMULTISIG

While it's corresponding unlocking script

Code:

0<signature1><signature3>

Where the two signatures above must correspond to any of the Pubkey assuming I didn't use any specific number.

I learnt that the error produced by the OP_MULTICHECKSIG can be resolved permanently, but the dummy variable(with a value of 0 above) was rather used as a temporarily solution. I am curious to know

1. Why is that?
2. Is there any brief explanation on how the bug could have been resolved if actually it was possible?.


The two scripts shown below are literally thesame, and they are combination of scriptsig, scriptpubsig and opcode. But I am curious, as I want to be sure of the order of execution, and how values are been pushed into the stack.

Code:

0
<signature1>
<signature2>
2
<pubkey1>
<pubkey2>
<pubkey3>
3
OP_CHECKMULTISIG

Code:

3
<pubkey3>
<pubkey2>
<pubkey1>
2
<signature2>
<signature1>
0

Question:
3. Just to be sure, which of the execution order is correct between both?.


Please Note that I broke the post down into two sections for readability. Each section contains questions Incase you missed any.

I am 100% open to correction as I still see myself as a learner. Pardon any of my error, and do well to also DYOR Incase the things here are new to you. I can't really say that everything written is 100% accurate.

[Mia Chloe]

You're kinda right. Ever since Blackhatcoiner's last quiz I noticed similar things concerning OP codes.
For the "OP_CHECKMULTISIG" Bug the issue usually comes up  when verifying signatures. And I think this is mainly because the opcode expects a specific stack layout but doesn't properly handle the errors that comes along with it. However a temporary solution like you said which I usually use is to make use of a dummy variable (0) to ensure correct stack alignment.

A more kinda advanced approach  would involve modifying "OP_CHECKMULTISIG" to properly handle errors and stack layout like improving the way the stacks are managed, However, introducing changes to OP_CHECKMULTISIG risks disrupting contracts and transactions that already exists.

Also, for you code I think;

Code:

0 <signature1> <signature2> 2 <pubkey1> <pubkey2> <pubkey3> 3 OP_CHECKMULTISIG

Should solve the problems.
Like I said before, 0 here is a dummy variable and is pushed into the stack. Next, the OP code pushes the Signatures (`<signature1>` and `<signature2>`), alongside the Public keys (`<pubkey1>`, `<pubkey2>`, and `<pubkey3>`) then (`2` and `3`) specify the required signature count and public key count after which OP_CHECKMULTISIG` verifies the signatures.

Code:

3 <pubkey3> <pubkey2> <pubkey1> 2 <signature2> <signature1> 0

I believe this is wrong because the public keys were pushed before (2) which is supposed to be the signature count.

Locking script:

Code:

3 <pubkey1> <pubkey2> <pubkey3> 2 OP_CHECKMULTISIG

Unlocking script

Code:

0 <signature1> <signature2>

And this should be the combined script

Code:

0 <signature1> <signature2>  3 <pubkey1> <pubkey2> <pubkey3> 2 OP_CHECKMULTISIG

The biggest issues I've faced in OP codes is always stack error. Op codes depend so much on their data stack.

[nc50lc]

1. Why is that?
2. Is there any brief explanation on how the bug could have been resolved if actually it was possible?.

There are already great answers on the internet so I'll just point you to them:

• 1. Here's a nicely written reply by 'Nick ODell' that briefly explains (compared to the length of the OP) how and why.
  Link: https://bitcoin.stackexchange.com/a/40673
  
  
• 2. Here's a not-so-old Bitcointalk thread that asked the same question with replies explaining how troublesome to implement a fix since it requires a hard fork.
  Link: https://bitcointalk.org/index.php?topic=5271566.0
  
  Additionally, for number 2, TapRoot essentially "solved" it (if used for multi signature scripts) since it use OP_CHECKSIGADD which doesn't have that bug.
  Ref: https://github.com/bitcoin/bips/blob/master/bip-0342.mediawiki#design

[Felicity_Tide]

Also, for you code I think;

Code:

0 <signature1> <signature2> 2 <pubkey1> <pubkey2> <pubkey3> 3 OP_CHECKMULTISIG

Should solve the problems.
Like I said before, 0 here is a dummy variable and is pushed into the stack. Next, the OP code pushes the Signatures (`<signature1>` and `<signature2>`), alongside the Public keys (`<pubkey1>`, `<pubkey2>`, and `<pubkey3>`) then (`2` and `3`) specify the required signature count and public key count after which OP_CHECKMULTISIG` verifies the signatures.

Yeah. I am aware that the application of the dummy is a temporary solution, but I was a little curious to know if there are other alternatives to this. I think I was able to find out something from the GitHub link that nc50lc shared, and here it is..

^ Alternatives to CHECKMULTISIG There are multiple ways of implementing a threshold k-of-n policy using Taproot and Tapscript:
Using a single OP_CHECKSIGADD-based script A CHECKMULTISIG script m <pubkey_1> ... <pubkey_n> n CHECKMULTISIG with witness 0 <signature_1> ... <signature_m> can be rewritten as script <pubkey_1> CHECKSIG <pubkey_2> CHECKSIGADD ... <pubkey_n> CHECKSIGADD m NUMEQUAL with witness <w_n> ... <w_1>. Every witness element w_i is either a signature corresponding to pubkey_i or an empty vector

Code:

3 <pubkey3> <pubkey2> <pubkey1> 2 <signature2> <signature1> 0

I believe this is wrong because the public keys were pushed before (2) which is supposed to be the signature count.

Locking script:

Code:

3 <pubkey1> <pubkey2> <pubkey3> 2 OP_CHECKMULTISIG

Thanks for pointing this out. Didn't notice at first.

There are already great answers on the internet so I'll just point you to them:

• 1. Here's a nicely written reply by 'Nick ODell' that briefly explains (compared to the length of the OP) how and why.
  Link: https://bitcoin.stackexchange.com/a/40673
  
  
• 2. Here's a not-so-old Bitcointalk thread that asked the same question with replies explaining how troublesome to implement a fix since it requires a hard fork.
  Link: https://bitcointalk.org/index.php?topic=5271566.0
  
  Additionally, for number 2, TapRoot essentially "solved" it (if used for multi signature scripts) since it use OP_CHECKSIGADD which doesn't have that bug.
  Ref: https://github.com/bitcoin/bips/blob/master/bip-0342.mediawiki#design

I really find these references very helpful. The order of execution was well explained from the first link, while the discussion from the second link was quite interesting to read through, though the last reply didn't agree much to the idea of calling it a bug, which he gave some reasonable explanations to that.

[pooya87]

And this should be the combined script

Code:

0 <signature1> <signature2>  3 <pubkey1> <pubkey2> <pubkey3> 2 OP_CHECKMULTISIG

Considering how multisig usually corresponds to a script-hash output script, this script is wrong because the entire redeem script (ie. 3 <pubkey1>...) has to be pushed to the stack as raw bytes not like this. Because the output script will have to first create a duplicate of it (the top stack element), then first hash it to see if it corresponds to the hash inside the script-hash (P2SH or P2WSH) and then evaluate it as a script.
So what you posted has to become:

Code:

0 <signature1> <signature2> <redeem_script>

And the redeem script itself is:

Code:

2 <pubkey1> <pubkey2> <pubkey3> 3 OP_CHECKMULTISIG

Also notice that m(=2) comes before n(=3) in an m-of-n (2of3) multi sig. The reason is because stack works from top to bottom meaning OP_CHECKMULTISIG first pops the top stack element (ie. 3) and knows it has to read n number of public keys. Then it reads n number of pubkeys to reach m (ie. 2) and after popping that and reading it the interpreter knows it has to read 2 signatures.
If it were the way you posted, after OP_CHECKMULTISIG pops the top stack element and sees 2 (signatures) it has no way of knowing how many public keys it has to read.

[Felicity_Tide]

Code:

0 <signature1> <signature2> <redeem_script>

And the redeem script itself is:

Code:

2 <pubkey1> <pubkey2> <pubkey3> 3 OP_CHECKMULTISIG

Also notice that m(=2) comes before n(=3) in an m-of-n (2of3) multi sig. The reason is because stack works from top to bottom meaning OP_CHECKMULTISIG first pops the top stack element (ie. 3) and knows it has to read n number of public keys. Then it reads n number of pubkeys to reach m (ie. 2) and after popping that and reading it the interpreter knows it has to read 2 signatures.
If it were the way you posted, after OP_CHECKMULTISIG pops the top stack element and sees 2 (signatures) it has no way of knowing how many public keys it has to read.

So,, it's obvious that 3 verifies the number of n which must be at the top of the stack, while 2 verifies the number of m that must come after the pubkeys assuming we are using the 2of3 Multi-sig?.

Now assuming we are reading from the top (pubkeys), we also have to confirm for their corresponding signature at that instance?, (Like read for pubkey3 and confirm with signature2. if it doesn't Correspond, we read again for pubkey3 and confirm with signature1)?.

And again, since no pubkey can share same signature, when a pubkey finally matches a signature, it's seems those two matches(assuming pubkey2 and signature2) will be omitted, and won't be used in the next verification attempt while verifying the last m and corresponding n?.

[Ambatman]

Now assuming we are reading from the top (pubkeys), we also have to confirm for their corresponding signature at that instance?, (Like read for pubkey3 and confirm with signature2. if it doesn't Correspond, we read again for pubkey3 and confirm with signature1)?.

Yeah, you mostly correct. But the Pubkeys doesn't have to be matched with the signature in a sequence.
Instead the script interpreter would match any of the signature with any of the Pubkeys
Once a signature corresponds with any of the Pubkeys it's considered valid and no longer available for further checking and moves to the next signature until this is satisfied 2-of-3 and if this isn't meant i.e if a signature couldn't correspond with a Pubkey, the entire script fails and the transaction becomes invalid.

[Felicity_Tide]

Now assuming we are reading from the top (pubkeys), we also have to confirm for their corresponding signature at that instance?, (Like read for pubkey3 and confirm with signature2. if it doesn't Correspond, we read again for pubkey3 and confirm with signature1)?.

Yeah, you mostly correct. But the Pubkeys doesn't have to be matched with the signature in a sequence.
Instead the script interpreter would match any of the signature with any of the Pubkeys

I actually asked that question initially just to confirm if the reverse process can occur. But I don't think we can just freely match any of the signature without using a sequential process. From what has been discussed so far, it's certain that the Pubkeys are loaded at the top of the stack, while the signatures proceeds it. From the first link shared by nc50lc, this was suppose to be the actual matching order from a sequential sense..

Loop through all of the public keys, starting with the keys at the top of the stack.

For each public key, check a single signature.
For the first public key checked, start with the signature closest to the top of the stack.
If it fails to verify, go to the next public key and check the same signature.
If it succeeds, go to the next public key with the next signature.

Note that the signatures need to be in the same order as the key's that they're signing for.

If all of the signatures succeeded with one of the keys, CHECKMULTISIG returns 1, otherwise 0.

You see what I was trying to say. But if were to use any signature and any pubkey, then we might have not followed this sequential process that the quoted text suggested above. The reason for my question earlier was actually to confirm if a reverse process of the quoted text can occur.

Once a signature corresponds with any of the Pubkeys it's considered valid and no longer available for further checking and moves to the next signature until this is satisfied 2-of-3 and if this isn't meant i.e if a signature couldn't correspond with a Pubkey, the entire script fails and the transaction becomes invalid

But there are about 3 available Pubkeys to match with, so I don't think it will fail automatically since there are two more pubkeys to go. So, if we follow the actual sequential process from the quoted text, I think the whole process might end up resulting to 1, which proves to be valid. Except we've successfully tested a signature with the 3 Pubkeys and there isn't any match. But Incase I am missing something here which I don't think so, please clearify me.

[Ambatman]

Hmm you right I guess I missed it on how I understood it.
The signature has to be matched with the Pubkeys in sequence
I guess it's like a 2*3 matrix.

About it failing, I was Talking a scenario where the Sig couldn't match any Pubkeys.
Yeah if one isn't matching it goes to the next until all are exhausted
And if non corresponds it fails.

I will check this out. Later maybe with different arrangements of the Pubkeys and Sig.