BIP-0341+BIP-0342: correct mediawiki code formatting, update OP

Roasbeef commented at 1:39 am on February 22, 2022: contributor

This PR fixes a few areas that use the markdown style backtick instead of the mediawiki <code> for variable names.

This PR also attempts to correct a potential ambguity in the description of OP_CHECKSIGVERIFY in the tapscript execution context.

Upon my initial reading of this section of the BIP, I thought that this mean that OP_CEHCKSIGVERIFY didn’t modify the stack by popping up the element pushed on by OP_CEHCKSIG. Instead it’s exactly the same, as pre tapscript behavior.

In this commit, we attempt to make this clearer by removing the “without any further changes to the stack” text in the BIP. This is what led me to believe that the op code no longer modified the stack.

jonasnick commented at 1:33 pm on February 22, 2022: contributor

Thanks @roasbeef. According to this BIP, CHECKSIGVERIFY neither pushes nor pops a result from the stack. Per my superficial reading, Core’s behavior in case of success (pushing, then popping) seems like a no-op. Anyway, “as normal” is very ambiguous.

Roasbeef commented at 7:40 pm on February 22, 2022: contributor

Anyway, “as normal” is very ambiguous.

Agree, just trying to capture that the pop still happens, will think of some better phrasing that better captures the semantics. When working on my implementation, and testing against the generated test vectors, I encountered a test case where an checksig follows a checksigverify, but if you don’t pop the element, then the stack is invalid for the checksig op, as you end up with 0x01 and trying to parse that as a sig fails.

Here’s what the stack looks like in this case during execution:

 0stepping 01:0000: OP_1
 1Stack:
 200000000  01                                                |.|
 3
 4stepping 01:0001: OP_DATA_32 0x85bbaf732586004b91d5e29af7be3965e4cbd4294c3dd4aad30280f6dcbe0145
 5Stack:
 600000000  <empty>
 700000000  36 22 8b be 24 62 eb f9  b4 4d 57 43 a1 61 bb 8b  |6"..$b...MWC.a..|
 800000010  43 de c7 d3 53 20 10 64  a0 46 96 e3 c5 07 4c 9f  |C...S .d.F....L.|
 900000020  7e 1a 0c b7 2e e0 2e 5e  ea a1 de 3f 2b 76 57 cb  |~......^...?+vW.|
1000000030  fd c9 ee 34 ef a9 d9 85  9d 04 c4 0a 6b 4a c1 df  |...4........kJ..|
11
12stepping 02:0000: OP_DATA_32 0x871bf677dcc1eeea213f60505c1c9f1695f8b7d2ee8bbacb3ba246e9f1e57e20
13Stack:
1400000000  <empty>
1500000000  36 22 8b be 24 62 eb f9  b4 4d 57 43 a1 61 bb 8b  |6"..$b...MWC.a..|
1600000010  43 de c7 d3 53 20 10 64  a0 46 96 e3 c5 07 4c 9f  |C...S .d.F....L.|
1700000020  7e 1a 0c b7 2e e0 2e 5e  ea a1 de 3f 2b 76 57 cb  |~......^...?+vW.|
1800000030  fd c9 ee 34 ef a9 d9 85  9d 04 c4 0a 6b 4a c1 df  |...4........kJ..|
1900000000  87 1b f6 77 dc c1 ee ea  21 3f 60 50 5c 1c 9f 16  |...w....!?`P\...|
2000000010  95 f8 b7 d2 ee 8b ba cb  3b a2 46 e9 f1 e5 7e 20  |........;.F...~ |
21
22stepping 02:0001: OP_CHECKSIGVERIFY
23Stack:
2400000000  <empty>
2500000000  01                                                |.|
26
27stepping 02:0002: OP_DATA_32 0x7d732801de7e0c866f2462f29c14b63e555159b62ba93a5d5963d1c04795f936
28Stack:
2900000000  <empty>
3000000000  01                                                |.|
3100000000  7d 73 28 01 de 7e 0c 86  6f 24 62 f2 9c 14 b6 3e  |}s(..~..o$b....>|
3200000010  55 51 59 b6 2b a9 3a 5d  59 63 d1 c0 47 95 f9 36  |UQY.+.:]Yc..G..6|
33
34stepping 02:0003: OP_CHECKSIG

The witness uses an empty sig that should be consumed by the OP_CHECKSIG op, but since OP_CHECKSIGVERIFY didn’t pop from the stack, it parses that “true” pushed onto it. So in most cases the pop behavior is indeed a noop, but there’re case where the stack isn’t in the correct position for a valid script to succeed.

BIP-0341: replace backticks with <code> tag

This commit fixes a few areas that use the markdown style backtick
instead of the mediawiki `<code>` for variable names.

0e7ceaf226

BIP-0342: tighten up OP_CEHCKSIGVERIFY tapscript execution description

Upon my initial reading of this section of the BIP, I thought that this
mean that `OP_CEHCKSIGVERIFY` _didn't_ modify the stack by popping up
the element pushed on by `OP_CEHCKSIG`. Instead it's exactly the same,
as pre tapscript behavior.

In this commit, we attempt to make this clearer by removing the "without
any further changes to the stack" text in the BIP. This is what led me
to believe that the op code no longer modified the stack.

92a12d6cc7

Roasbeef force-pushed on Feb 23, 2022

Roasbeef commented at 1:56 am on February 23, 2022: contributor

Anyway, “as normal” is very ambiguous.

Updated to explicitly note that an element is popped from the stack. This matches the OP_CHECKSIG behavior that details what happens to the stack in the case of a success.

jonasnick commented at 10:35 am on February 23, 2022: contributor

I can see that it’s possible to be confused if one is primed by the legacy implementation of CHECKSIGVERIFY in Core (which is presumably similar to btcd’s). But the spec alone is pretty clear that CHECKSIGVERIFY does not modify the stack after consuming signature and public key. For “a an element is popped from the stack” to make sense, wouldn’t it first need to be stated that that element is pushed onto the stack?

We could consider adding a footnote that says something like “this does not mean that checksigverify leaves a 1 on the stack” but that also seems quite confusing if you don’t know the context.

Zamy159 commented at 10:39 am on February 23, 2022: none

You should come down please let me understand this shit more

On Wed, Feb 23, 2022 at 05:36 Jonas Nick @.***> wrote:

I can see that it’s possible to be confused if one is primed by the legacy implementation of CHECKSIGVERIFY in Core (which is presumably similar to btcd’s). But the spec alone is pretty clear that CHECKSIGVERIFY does not modify the stack after consuming signature and public key. For “a an element is popped from the stack” to make sense, wouldn’t it first need to be stated that that element is pushed onto the stack?

We could consider adding a footnote that says something like “this does not mean that checksigverify leaves a 1 on the stack” but that also seems quite confusing if you don’t know the context.

— Reply to this email directly, view it on GitHub https://github.com/bitcoin/bips/pull/1284#issuecomment-1048646223, or unsubscribe https://github.com/notifications/unsubscribe-auth/AXM3YBYUFK444LDR5J5W4RTU4S2EJANCNFSM5PAAADYQ . Triage notifications on the go with GitHub Mobile for iOS https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675 or Android https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub.

You are receiving this because you are subscribed to this thread.Message ID: @.***>

Roasbeef commented at 8:34 pm on February 23, 2022: contributor

I can see that it’s possible to be confused if one is primed by the legacy implementation of CHECKSIGVERIFY in Core (which is presumably similar to btcd’s).

Here’s my current reference: https://github.com/bitcoin/bitcoin/blob/master/src/script/interpreter.cpp#L1084

If I’m reading this correctly, then an item is always pushed onto the stack here (as normal with checksig): https://github.com/bitcoin/bitcoin/blob/master/src/script/interpreter.cpp#L1097

For the verify op code, an item is then always popped from the stack here (when succesful): https://github.com/bitcoin/bitcoin/blob/master/src/script/interpreter.cpp#L1100

But the spec alone is pretty clear that CHECKSIGVERIFY does not modify the stack after consuming signature and public key.

Therefore, this isn’t correct from the PoV of tapscript execution, as EvalChecksigTapscript always returns true if the sig is valid: https://github.com/bitcoin/bitcoin/blob/master/src/script/interpreter.cpp#L408. So if the sig is valid, then an item will always be popped off the stack.

For “a an element is popped from the stack” to make sense, wouldn’t it first need to be stated that that element is pushed onto the stack?

I agree, which then means we’d need to actually fully specify OP_CHECKSIGVERIFY, instead of describe modifications to the existing behavior. The BIP as is assumes that an implementation already has that op code working, if it’s gotten to this point in the history of sot-forks, which is likely a reasonable assumption.

Roasbeef commented at 8:49 pm on February 23, 2022: contributor

Discussed this on IRC w/ sipa, and I understand your PoV now @jonasnick: if you made an impl of OP_CHECKSIGVERIFY from scratch based on this spec, you’d implement things properly and the spec is correct. It just so happens that implementations in practice, based off the prior consensus rules and soft forks end up treating OP_CHECKSIGVERIFY as extra logic at the end of OP_CHECKSIG execution.

So maybe just a footnote is enough, that if an implementation pushed the return value onto the stack in a prior step (re-using OP_CHECKSIG logic), then it should ensure not to leave that element.

JeremyRubin commented at 11:32 pm on February 23, 2022: contributor

@Roasbeef I think it is a good point worth clarifying because if an alternative implementation enforced invariants on stack depth within the stack, it could lead to bugs if the push actually does hit the stack or not, so it’s best to be clear that no effect of a stack push/pop should be observable.

in bip-0342.mediawiki:103 in 92a12d6cc7

 99@@ -100,7 +100,7 @@ The following rules apply to <code>OP_CHECKSIG</code>, <code>OP_CHECKSIGVERIFY</
100 *** For <code>OP_CHECKSIG</code>, an empty vector is pushed onto the stack, and execution continues with the next opcode.
101 *** For <code>OP_CHECKSIGADD</code>, a <code>CScriptNum</code> with value <code>n</code> is pushed onto the stack, and execution continues with the next opcode.
102 ** If the signature is not the empty vector, the opcode is counted towards the sigops budget (see further).
103-*** For <code>OP_CHECKSIGVERIFY</code>, execution continues without any further changes to the stack.
104+*** For <code>OP_CHECKSIGVERIFY</code>, a an element is popped from the stack.

ajtowns commented at 1:48 am on March 22, 2022:

“a an element” and trailing whitespace.

Note that the first bullet point here already says “For OP_CHECKSIGVERIFY and OP_CHECKSIG, the public key (top element) and a signature (second to top element) are popped from the stack.”

Maybe it would be better to describe the difference between “OP_CHECKSIG OP_VERIFY” and “OP_CHECKSIGVERIFY” – in particular, the only case where they differ is if stack.size() + altstack.size() = MAX + 1 after OP_CHECKSIG completes, in which case the former will always fail, while the latter may succeed.

Roasbeef commented at 11:55 pm on May 8, 2024:

Note that the first bullet point here already says

Ah, you’re right I’d missed that! This section decribes what happens after the initial pops and verification. So in this case OP_CHECKSIGVERIFY does just indeed “continue as normal”.

pancamarga41 commented at 7:07 am on May 13, 2024:

dana..

luke-jr added the label Proposed BIP modification on May 5, 2022

murchandamus commented at 8:15 pm on April 26, 2024: contributor

I think in the title you mean 342 instead of 432? It seems that this PR has outstanding review comments. Is this still in progress?

jonatack commented at 9:17 pm on May 1, 2024: contributor

cc @Roasbeef

murchandamus renamed this:
~~BIP-0341+BIP-0432: correct mediawiki code formatting, update OP_CHECKSIGVERIFY description~~
BIP-0341+BIP-0342: correct mediawiki code formatting, update OP_CHECKSIGVERIFY description
on May 2, 2024

murchandamus added the label PR Author action required on May 8, 2024

Roasbeef commented at 11:56 pm on May 8, 2024: contributor

Closing based on this comment: https://github.com/bitcoin/bips/pull/1284/commits/92a12d6cc72b8257d68a3b82cd547bf38903bc58#r1594817709

Roasbeef closed this on May 8, 2024

BIP-0341+BIP-0342: correct mediawiki code formatting, update OP_CHECKSIGVERIFY description #1284