Abstract out script execution out of VerifyWitnessProgram()

sipa commented at 9:06 pm on January 25, 2020: member

This is a refactoring cherry-picked out of #17977. As it touches consensus code, I don’t think this would ordinarily meet the bar for review cost vs benefit. However, it simplifies the changes for Taproot significantly, and if it’s going to be necessitated by inclusion of that code, I may as well give it some additional attention by PRing it independently.

sipa commented at 9:10 pm on January 25, 2020: member

A change like this was originally suggested by @JeremyRubin here: https://github.com/sipa/bitcoin/pull/116

DrahtBot added the label Consensus on Jan 25, 2020

fanquake added the label Refactoring on Jan 25, 2020

DrahtBot commented at 1:11 am on January 26, 2020: member

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#18267 (BIP-325: Signet [consensus] by kallewoof)
#17977 ([WIP] Implement BIP 340-342 validation (Schnorr/taproot/tapscript) by sipa)
#16653 (script: add simple signature support (checker/creator) by kallewoof)
#13062 (Make script interpreter independent from storage type CScript by sipa)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

fanquake requested review from ajtowns on Jan 26, 2020

fanquake requested review from JeremyRubin on Jan 26, 2020

JeremyRubin commented at 2:27 am on January 26, 2020: contributor

I’m generally a big fan of cleaning up this consensus logic such that the code is “tree-like” and terminates at leaf branches, rather than having interleaved “dag-like” branches that merge into a common exit point. One of the key advantages of code structured in this way is it’s much easier to see, at a glance, exactly how many “versions” (i.e., combinations of flags) we support. Otherwise, with N things that could either be on or off you get something like 2**N potential execution traces which makes it really hard to write tests for all flows (coverage is not enough).

It’s a code style that I think we should strive to use when possible, and it makes me a bit extreme in that I go as far as to think we should re-write some other consensus logic (see #15969) to be more in line with this style.

I say the above here not to advocate for more expansive changes at this time, but more so that other reviewers can appropriately discount my ACKs here if you disagree with this viewpoint.

That this makes Taproot simpler to review and implement is a plus, but I think these changes stand on their own.

Concept ACK + lite CR-ack, untested.

in src/script/interpreter.cpp:1467 in 1e1e28cdc2 outdated

1486-    // Scripts inside witness implicitly require cleanstack behaviour
1487-    if (stack.size() != 1)
1488-        return set_error(serror, SCRIPT_ERR_CLEANSTACK);
1489-    if (!CastToBool(stack.back()))
1490-        return set_error(serror, SCRIPT_ERR_EVAL_FALSE);
1491-    return true;

NicolasDorier commented at 7:51 am on January 26, 2020:

~~Before this PR SCRIPT_ERR_CLEANSTACK would be enforced even on non version 0 witnessed. This change only enforce it on version 0 witnesses, this is probably a hardfork case?~~ (not the case, I missed the else clause in the original code)

NicolasDorier commented at 7:58 am on January 26, 2020:

~~EDIT: Actually right now, all non witness 0 script would be rejected by consensus? Because the stack of a non version 0 witness is always empty and this would violate SCRIPT_ERR_CLEANSTACK?~~ (not the case, I missed the else clause in the original code)

NicolasDorier commented at 8:04 am on January 26, 2020: contributor

Code review ACK.

I like the approach of trying to get small refactors onto the codebase that can be independently reviewed to make the taproot PR more reviewable.

in src/script/interpreter.cpp:1419 in 1e1e28cdc2 outdated

1415@@ -1416,9 +1416,26 @@ bool GenericTransactionSignatureChecker<T>::CheckSequence(const CScriptNum& nSeq
1416 template class GenericTransactionSignatureChecker<CTransaction>;
1417 template class GenericTransactionSignatureChecker<CMutableTransaction>;
1418 
1419+static bool ExecuteWitnessProgram(std::vector<std::vector<unsigned char>> stack, const CScript& scriptPubKey, unsigned int flags, SigVersion sigversion, const BaseSignatureChecker& checker, ScriptError* serror)

Empact commented at 0:03 am on January 30, 2020:

nit: Maybe stack passing could be clarified by passing as const reference and instantiating the local within? Or a doc commenting that it’s an in var.

sipa commented at 0:05 am on January 30, 2020:

Passing it as const reference would require an unnecessary copy. I’ll add a comment.

Empact commented at 0:15 am on January 30, 2020:

Sounds good re comment. Doesn’t the copy occur in either case? AFAIK pass by value requires a copy to have a new instance available for modification.

sipa commented at 0:18 am on January 30, 2020:

Pass by value is a terrible name.

It’s just a variable on the callee side that is constructed in place by the caller. The call sites construct temporaries, so the move constructor will be invoked to construct the parameter.

ajtowns commented at 4:23 am on January 31, 2020:

Everything else is called Eval rather than Execute

sipa commented at 4:35 am on February 3, 2020:

I didn’t want to call it …Eval, as it’s not just evaluating a script (EvalScript just executes opcodes, and modifies a stack; this function is actually closer to VerifyScript which maps it to a true/false success overall).

theStack commented at 1:09 am on February 7, 2020:

Concerning the stack parameter: would it make sense to declare it as an rvalue parameter (&&) and pass constructed temporaries in both calls (would need to change witness.stack to {witness.stack.begin(), witness.stack.end()}, to ensure and clarify that the move-constructor is always involved? Just an idea following the “explicit is better than implicit” principle.

sipa commented at 3:25 am on February 7, 2020:

@theStack Ok, better like this?

theStack commented at 11:24 am on February 7, 2020:

That was more of a suggestion/question than a concrete wish (you probably have way more C++ experience), but personally I’d prefer it, yes. Interestingly enough, on the first call explicitely calling the constructor would not be needed (passing {witness.stack.begin(), witness.stack.end() - 1} is sufficient), while on the second call only {witness.stack} would lead to an error and an explicit constructor call (std::vector<std::vector<unsigned char>>(...)) is needed.

sipa commented at 6:49 pm on February 7, 2020:

Yes, I’m aware it wasn’t necessary to invoke the constructor explicitly, but it’s probably clearer this way (semantically it’s equivalent).

ajtowns commented at 8:31 pm on February 9, 2020:

You could do:

0-static bool ExecuteWitnessProgram(std::vector<std::vector<unsigned char>>&& stack, const CScript& scriptPubKey, unsigned int flags, SigVersion sigversion, const BaseSignatureChecker& checker, ScriptError* serror)
1+static bool ExecuteWitnessProgram(std::vector<valtype>::const_iterator begin, std::vector<valtype>::const_iterator end, const CScript& scriptPubKey, unsigned int flags, SigVersion sigversion, const BaseSignatureChecker& checker, ScriptError* serror)
2 {
3+    std::vector<valtype> stack{begin, end};

and just pass the iterators in directly.

sipa commented at 7:37 pm on February 12, 2020:

Done, as that makes it also more compatible with #13062.

Empact commented at 0:11 am on January 30, 2020: member

Code Review ACK https://github.com/bitcoin/bitcoin/pull/18002/commits/1e1e28cdc207b7f12a8dce953e61c7c508c63611

in src/script/interpreter.cpp:1464 in 1e1e28cdc2 outdated

1472-
1473-    // Disallow stack item size > MAX_SCRIPT_ELEMENT_SIZE in witness stack
1474-    for (unsigned int i = 0; i < stack.size(); i++) {
1475-        if (stack.at(i).size() > MAX_SCRIPT_ELEMENT_SIZE)
1476-            return set_error(serror, SCRIPT_ERR_PUSH_SIZE);
1477+        assert(false); // Unreachable code

ajtowns commented at 11:20 am on January 30, 2020:

Having if () { ...; } else { ... } instead of if () { ...; assert(false); } ... would let gcc and clang issue a compile-time warning (“control reaches end of non-void function”) if the logic got messed up in future, but I don’t think there’s any way to get both a compile time warning and a runtime safety check (assert(false) overrules the “control reaches end…” warning), so just having the runtime safety check is probably best.

sipa commented at 7:33 pm on February 12, 2020:

Done. I think the compiler can do an equally good job of detecting missing branches, and it avoids an assertion in consensus code.

in src/script/interpreter.cpp:1423 in 1e1e28cdc2 outdated

1415@@ -1416,9 +1416,26 @@ bool GenericTransactionSignatureChecker<T>::CheckSequence(const CScriptNum& nSeq
1416 template class GenericTransactionSignatureChecker<CTransaction>;
1417 template class GenericTransactionSignatureChecker<CMutableTransaction>;
1418 
1419+static bool ExecuteWitnessProgram(std::vector<std::vector<unsigned char>> stack, const CScript& scriptPubKey, unsigned int flags, SigVersion sigversion, const BaseSignatureChecker& checker, ScriptError* serror)
1420+{
1421+    // Disallow stack item size > MAX_SCRIPT_ELEMENT_SIZE in witness stack
1422+    for (unsigned int i = 0; i < stack.size(); i++) {
1423+        if (stack.at(i).size() > MAX_SCRIPT_ELEMENT_SIZE) {

ajtowns commented at 11:23 am on January 30, 2020:

for (const auto& el : stack) { if (el.size() > MAX_SCRIPT_ELEMENT_SIZE) { ... ? Probably too gratuitous a change to justify. Likewise ++i vs i++ :)

jonatack commented at 12:36 pm on February 12, 2020:

agree with @ajtowns, this seems nicer

0-    for (unsigned int i = 0; i < stack.size(); i++) {
1-        if (stack.at(i).size() > MAX_SCRIPT_ELEMENT_SIZE) {
2+    for (const auto& el : stack) {
3+        if (el.size() > MAX_SCRIPT_ELEMENT_SIZE) {

sipa commented at 7:34 pm on February 12, 2020:

Done, I’m making style improvements anyway.

ajtowns approved

ajtowns commented at 4:26 am on January 31, 2020: member

ACK 1e1e28cdc207b7f12a8dce953e61c7c508c63611 ; nits only, none of which seem worth fixing

sipa force-pushed on Feb 7, 2020

theStack approved

theStack commented at 11:23 am on February 7, 2020: member

ACK https://github.com/bitcoin/bitcoin/pull/18002/commits/139f7ffc71b706df748624e9c41d83a041b9f8b3

in src/script/interpreter.cpp:1427 in 139f7ffc71 outdated

1424+            return set_error(serror, SCRIPT_ERR_PUSH_SIZE);
1425+        }
1426+    }
1427+
1428+    // Run the script interpreter.
1429+    if (!EvalScript(stack, scriptPubKey, flags, checker, sigversion, serror)) return false;

egp commented at 4:31 pm on February 7, 2020:

Why not return EvalScript(stack, scriptPubKey, flags, checker, sigversion, serror));

sipa commented at 4:32 pm on February 7, 2020:

That would be incorrect. The lines below wouldn’t be executed anymore.

egp commented at 4:43 pm on February 7, 2020:

Ah, I see. Sorry. I missed that because I am used to FP.

in src/script/interpreter.cpp:1419 in 139f7ffc71 outdated

1415@@ -1416,9 +1416,26 @@ bool GenericTransactionSignatureChecker<T>::CheckSequence(const CScriptNum& nSeq
1416 template class GenericTransactionSignatureChecker<CTransaction>;
1417 template class GenericTransactionSignatureChecker<CMutableTransaction>;
1418 
1419+static bool ExecuteWitnessProgram(std::vector<std::vector<unsigned char>>&& stack, const CScript& scriptPubKey, unsigned int flags, SigVersion sigversion, const BaseSignatureChecker& checker, ScriptError* serror)

jnewbery commented at 4:12 pm on February 11, 2020:

Hi 🙋 I’d also like to bikeshed this function name please.

My understanding is that the witness program is the 20/32 byte commitment to the spending condition. The ‘witness script’ is what is actually executed. Does ExecuteWitnessScript() makes more sense as a function name? For both P2WPKH and P2WSH, the program is not actually passed in here.

sipa commented at 7:34 pm on February 12, 2020:

Bikeshed accepted.

in src/script/interpreter.cpp:1472 in 139f7ffc71 outdated

1488-        return set_error(serror, SCRIPT_ERR_CLEANSTACK);
1489-    if (!CastToBool(stack.back()))
1490-        return set_error(serror, SCRIPT_ERR_EVAL_FALSE);
1491-    return true;
1492+    // Higher version witness scripts return true for future softfork compatibility
1493+    return set_success(serror);

jnewbery commented at 4:17 pm on February 11, 2020:

calling set_success() isn’t required here. It only needs to be called once, by VerifyScript(). Anything further up the stack can just return true.

jonatack commented at 12:38 pm on February 12, 2020:

calling set_success() isn’t required here. It only needs to be called once, by VerifyScript()

agree with @jnewbery here AFAICT

sipa commented at 7:34 pm on February 12, 2020:

Done.

jnewbery commented at 4:17 pm on February 11, 2020: member

Code review ACK 139f7ffc71b706df748624e9c41d83a041b9f8b3

A couple of nits inline.

jonatack commented at 12:40 pm on February 12, 2020: member

ACK 139f7ff mod comments

fjahr commented at 6:15 pm on February 12, 2020: member

Code review ACK 139f7ffc71b706df748624e9c41d83a041b9f8b3

Verified the changes are a pure refactor. Also ran test locally. I agree with both of @jnewbery s comments but can also be merged as it is right now.

[REFACTOR] Abstract out script execution out of VerifyWitnessProgram()

This removes the unclear reliance on "falling through" to get to the
script execution part.

Also fix some code style issues.

c8e24ddce3

sipa force-pushed on Feb 12, 2020

sipa commented at 7:38 pm on February 12, 2020: member

I’ve made a few invasive changes here, which will need re-review.

fjahr commented at 8:31 pm on February 12, 2020: member

Re-ACK c8e24ddce31a8de6255b23c19d958c1cd44a8847

New changes addressed the review comments.

in src/script/interpreter.cpp:1422 in c8e24ddce3

1413@@ -1414,9 +1414,26 @@ bool GenericTransactionSignatureChecker<T>::CheckSequence(const CScriptNum& nSeq
1414 template class GenericTransactionSignatureChecker<CTransaction>;
1415 template class GenericTransactionSignatureChecker<CMutableTransaction>;
1416 
1417+static bool ExecuteWitnessScript(std::vector<valtype>::const_iterator begin, std::vector<valtype>::const_iterator end, const CScript& scriptPubKey, unsigned int flags, SigVersion sigversion, const BaseSignatureChecker& checker, ScriptError* serror)
1418+{
1419+    std::vector<valtype> stack{begin, end};
1420+
1421+    // Disallow stack item size > MAX_SCRIPT_ELEMENT_SIZE in witness stack
1422+    for (const valtype& elem : stack) {

jonatack commented at 11:42 pm on February 12, 2020:

For my understanding, is there a reason why auto would not be preferred here?

0-    for (const valtype& elem : stack) {
1+    for (const auto& elem : stack) {

sipa commented at 9:42 pm on February 18, 2020:

Personal preference.

jonatack commented at 11:44 pm on February 12, 2020: member

ACK c8e24dd

theStack commented at 6:47 pm on February 16, 2020: member

re-ACK https://github.com/bitcoin/bitcoin/commit/c8e24ddce31a8de6255b23c19d958c1cd44a8847 Checked that since my previous ACK https://github.com/bitcoin/bitcoin/commit/139f7ffc71b706df748624e9c41d83a041b9f8b3 the following changes have been made:

s/ExecuteWitnessProgram/ExecuteWitnessScript
pass script stack to ExecuteWitnessScript as const_iterator pair (and create local copy) instead of rvalue reference
use range-based for loop for stack item size check
in success case, just return true instead of the not needed set_success(...)
removed the assertion for unreachable code, put the bottom part in an else-branch instead and intentionally have no return statement at the end of the function (if it is ever reached, the compiler would spit out a warning, indicating a flawed logic above)

Empact commented at 8:58 pm on February 17, 2020: member

Code Review Re-ACK https://github.com/bitcoin/bitcoin/pull/18002/commits/c8e24ddce31a8de6255b23c19d958c1cd44a8847

nit: could use cbegin/cend

ajtowns commented at 2:34 am on February 19, 2020: member

ACK c8e24ddce31a8de6255b23c19d958c1cd44a8847

NicolasDorier commented at 12:53 pm on February 19, 2020: contributor

Code Review reACK

jnewbery commented at 9:22 pm on March 13, 2020: member

ACK c8e24ddce31a8de6255b23c19d958c1cd44a8847

laanwj merged this on Mar 13, 2020

laanwj closed this on Mar 13, 2020

sidhujag referenced this in commit 82fee8186d on Mar 14, 2020

fanquake referenced this in commit 54646167db on Mar 27, 2020

sidhujag referenced this in commit 111c6867e4 on Nov 10, 2020

DrahtBot locked this on Feb 15, 2022

Abstract out script execution out of VerifyWitnessProgram() #18002

Conflicts