Remove template matching and pseudo opcodes #13194

sipa · 2018-05-09T03:27:44Z

The current code contains a rather complex script template matching engine, which is only used for 3 particular script types (P2PK, P2PKH, multisig). The first two of these are trivial to match for otherwise, and a specialized matcher for multisig is both more compact and more efficient than a generic one.

The goal is being more flexible, so that for example larger standard multisigs inside SegWit outputs are easier to implement.

As a side-effect, it also gets rid of the pseudo opcodes hack.

laanwj · 2018-05-09T11:18:42Z

src/script/script.h

-    OP_PUBKEYS = 0xfb,
-    OP_PUBKEYHASH = 0xfd,
-    OP_PUBKEY = 0xfe,
-


Nice to get rid of these fake opcodes here.

jtimon

utACK modulo nits and modulo this kind of unrelated thing I don't understand.
Perhaps a stupid question but, in https://github.com/bitcoin/bitcoin/blob/master/src/pubkey.h#L59 why are there 3 ways to indicate non-compressed and 2 ways to indicate compressed? shouldn't one for each be enough? also, should using an enum or macros or constants be more clear?

jtimon · 2018-05-09T14:22:46Z

src/script/standard.cpp

+    CScript::const_iterator it = script.begin();
+    if (script.size() < 1 || script.back() != OP_CHECKMULTISIG) return false;
+
+    if (!script.GetOp(it, opcode, data) || (opcode != OP_0 && (opcode < OP_1 || opcode > OP_16))) return false;


Souldn't this return false if it's op_0 too? or are 0 required sigs multisigs valid?

key count can be 0, I think. The only checks in the interpreter I see are for negative numbers.

I'm trying to stick to the original logic as close as possible; optimizations / other tweaks can happen later.

Agree with @sipa here. One step at a time is easier to review.

jtimon · 2018-05-09T14:26:06Z

src/script/standard.cpp

    }
+    if (opcode != OP_0 && (opcode < OP_1 || opcode > OP_16)) return false;


Same here, shouldn't OP_0 be invalid here too?
If 0 is allowed, why not just opcode < OP_0 || opcode > OP_16?

OP_0 is 0, OP_1 is 81. They aren't continuous.

An isOP_N(opcode) helper function would make this (and the expression above) slightly better readable.

I added an IsSmallInteger function for this (which would be distinct from IsOP_N by not accepting OP_1NEGATE).

instagibbs · 2018-05-09T15:18:36Z

src/script/standard.cpp

-        mTemplates.insert(std::make_pair(TX_PUBKEY, CScript() << OP_PUBKEY << OP_CHECKSIG));
+    if (script.size() == 35 && script[0] == 33 && script[34] == OP_CHECKSIG) {
+        pubkey = valtype(script.begin() + 1, script.begin() + 34);
+        return CPubKey::ValidSize(pubkey);


Redundant check here? We know the size.

CpubKey::ValidSize checks the data-dependent size (depending on what the first byte is).

instagibbs · 2018-05-09T15:18:41Z

src/script/standard.cpp

+    }
+    if (script.size() == 67 && script[0] == 65 && script[66] == OP_CHECKSIG) {
+        pubkey = valtype(script.begin() + 1, script.begin() + 66);
+        return CPubKey::ValidSize(pubkey);


Redundant check here? We know the size.

We could just use proper constants in the lines above for more belt and suspenders.

sipa · 2018-05-09T15:33:20Z

@jtimon Hybrid public keys (the 0x06 and 0x07 ones) are stupid, but were supported by OpenSSL, and because of that they're supported in Bitcoin. Nothing we can do about that.

instagibbs · 2018-05-09T15:46:23Z

light tACK

laanwj · 2018-05-10T12:42:42Z

src/script/standard.cpp

+
+    if (!script.GetOp(it, opcode, data) || (opcode != OP_0 && (opcode < OP_1 || opcode > OP_16))) return false;
+    required = CScript::DecodeOP_N(opcode);
+    while (script.GetOp(it, opcode, data) && CPubKey::ValidSize(data)) {


Shouldn't it check the opcodes here?
Oh I guess not, all the push opcodes valid here will return non-empty data, and CPubKey::ValidSize rejects empty data.

Indeed (that's also what the old code does).

Empact · 2018-05-16T02:06:18Z

src/script/standard.cpp

+        pubkey = valtype(script.begin() + 1, script.begin() + 34);
+        return CPubKey::ValidSize(pubkey);
+    }
+    if (script.size() == 67 && script[0] == 65 && script[66] == OP_CHECKSIG) {


CPubKey::PUBLIC_KEY_SIZE == 65, would add clarity

Empact · 2018-05-16T02:06:45Z

src/script/standard.cpp

-    {
-        // Standard tx, sender provides pubkey, receiver adds signature
-        mTemplates.insert(std::make_pair(TX_PUBKEY, CScript() << OP_PUBKEY << OP_CHECKSIG));
+    if (script.size() == 35 && script[0] == 33 && script[34] == OP_CHECKSIG) {


CPubKey::COMPRESSED_PUBLIC_KEY_SIZE == 33, would add clarity

Incidentally, I have #12461 to make these references more succinct.

Empact · 2018-05-16T02:36:58Z

src/script/standard.cpp

+    return false;
+}
+
+static bool MatchPayToPubkeyHash(const CScript& script, valtype& pubkeyhash)


See also IsToKeyID in compressor.cpp, which looks equivalent.

Could split this up as CScript::IsPayToPubkeyHash, and do the unpacking in Solver, ala IsPayToScriptHash. Would make the case handling more consistent in Solver.

I'd rather not merging with the versions in compressor - they may end up living separate lives as the standard templates change.

Empact · 2018-05-16T02:37:31Z

src/script/standard.cpp

@@ -35,22 +35,55 @@ const char* GetTxnOutputType(txnouttype t)
    return nullptr;
 }

-bool Solver(const CScript& scriptPubKey, txnouttype& typeRet, std::vector<std::vector<unsigned char> >& vSolutionsRet)
+static bool MatchPayToPubkey(const CScript& script, valtype& pubkey)


See also IsToPubKey in compressor, which looks equivalent.

Empact · 2018-05-16T02:42:21Z

Concept ACK! Much simpler way to handle these 3 cases.

jonasschnelli · 2018-05-16T06:20:18Z

Nice!
utACK 2fc4fdd0945a3800af8213676182ebb2c63689d8

gmaxwell · 2018-05-25T21:35:37Z

ACK.

Empact · 2018-05-26T00:29:29Z

src/script/standard.cpp

    }
+    if (!IsSmallInteger(opcode)) return false;
+    unsigned int keys = CScript::DecodeOP_N(opcode);
+    if (pubkeys.size() != keys || required == 0 || keys < required) return false;


nit: this required == 0 check could be an earlier return

Empact · 2018-05-26T00:30:43Z

src/script/standard.cpp

+        typeRet = TX_MULTISIG;
+        vSolutionsRet.push_back({static_cast<unsigned char>(required)});
+        vSolutionsRet.insert(vSolutionsRet.end(), keys.begin(), keys.end());
+        vSolutionsRet.push_back({static_cast<unsigned char>(keys.size())});


Maybe worth noting these casts are safe due to small integer limits?

Empact · 2018-05-26T00:31:33Z

utACK fa1f642

Empact · 2018-05-26T00:43:17Z

re-utACK 89736a9 just addresses comments above

promag · 2018-05-26T08:46:36Z

src/script/standard.cpp

+    if (!IsSmallInteger(opcode)) return false;
+    unsigned int keys = CScript::DecodeOP_N(opcode);
+    if (pubkeys.size() != keys || keys < required) return false;
+    if (it + 1 != script.end()) return false;


nit

return it + 1 == script.end();

promag · 2018-05-26T08:47:55Z

utACK 89736a9.

jl2012 · 2018-05-29T16:53:35Z

src/script/standard.cpp

-    {
-        // Standard tx, sender provides pubkey, receiver adds signature
-        mTemplates.insert(std::make_pair(TX_PUBKEY, CScript() << OP_PUBKEY << OP_CHECKSIG));
+    if (script.size() == CPubKey::PUBLIC_KEY_SIZE + 2 && script[0] == CPubKey::PUBLIC_KEY_SIZE && script[CPubKey::PUBLIC_KEY_SIZE + 1] == OP_CHECKSIG) {


what about script.back() == OP_CHECKSIG?

jl2012 · 2018-05-29T17:02:47Z

src/script/standard.cpp

+/** Test for "small integer" script opcodes - OP_0 through OP_16. */
+static constexpr bool IsSmallInteger(opcodetype opcode)
+{
+    return opcode == OP_0 || (opcode >= OP_1 && opcode <= OP_16);


if you remove opcode == OP_0 here, you can remove if (required == 0) return false; below

The current code contains a rather complex script template matching engine, which is only used for 3 particular script types (P2PK, P2PKH, multisig). The first two of these are trivial to match for otherwise, and a specialized matcher for multisig is both more compact and more efficient than a generic one. The goal is being more flexible, so that for example larger standard multisigs inside SegWit outputs are more easy to implement. As a side-effect, it also gets rid of the pseudo opcodes hack.

jonasschnelli · 2018-08-30T09:09:17Z

This change has the side effect that invalid pubkeys (with correct size of 33 or 65) in bare multisig are now non-standard (see #14104)

The current code contains a rather complex script template matching engine, which is only used for 3 particular script types (P2PK, P2PKH, multisig). The first two of these are trivial to match for otherwise, and a specialized matcher for multisig is both more compact and more efficient than a generic one. The goal is being more flexible, so that for example larger standard multisigs inside SegWit outputs are more easy to implement. As a side-effect, it also gets rid of the pseudo opcodes hack. Committer's note: This is a port of bitcoin/bitcoin/pull/13194 tha has been adapted to work with BU. The main differencies are related to the fact that we expose to the user two other kind of transaction use cases: TX_LABELPUBLIC, TX_CLTV.

Bitcoin script PRs 1 Cherry-picked from the following upstream PRs: - bitcoin/bitcoin#6335 - bitcoin/bitcoin#6424 - bitcoin/bitcoin#11058 - bitcoin/bitcoin#12460 - bitcoin/bitcoin#13194 Part of #2074.

The current code contains a rather complex script template matching engine, which is only used for 3 particular script types (P2PK, P2PKH, multisig). The first two of these are trivial to match for otherwise, and a specialized matcher for multisig is both more compact and more efficient than a generic one. The goal is being more flexible, so that for example larger standard multisigs inside SegWit outputs are more easy to implement. As a side-effect, it also gets rid of the pseudo opcodes hack. Committer's note: This is a port of bitcoin/bitcoin/pull/13194 tha has been adapted to work with BU. The main differencies are related to the fact that we expose to the user two other kind of transaction use cases: TX_LABELPUBLIC, TX_CLTV.

bitcoin/bitcoin#13194 zcash/zcash@2cb14d7 KomodoPlatform/komodo#298

5d96c91 add missing policy.cpp file to cmake (furszy) 2d0783d Standard Solver(): Include cold staking template matching. (furszy) b7fe4c0 Remove template matching and pseudo opcodes (furszy) fe31b31 Assert CPubKey::ValidLength to the pubkey's header-relevent size (Ben Woosley) 2f6b249 Make TX_SCRIPTHASH clear vSolutionsRet first (Peter Todd) 45e5102 Policy: MOVEONLY: 3 functions to policy (furszy) 2c7da7f Policy: MOVEONLY: Create policy/policy.h with some constants (furszy) Pull request description: Coming from the following PRs (with small customizations for our features): * bitcoin#6335 * bitcoin#6424 * bitcoin#12460 * bitcoin#13194 ACKs for top commit: random-zebra: Looking good. ACK 5d96c91 Fuzzbawls: ACK 5d96c91 Tree-SHA512: b3e7479864e16942682b9bc19f432b2a657561647eeadf0ef1285651feb05875d295ff530582ebbc8edacaf3c7d3888249513b4a93d871c2d6c2e1b157ace8c8

c814e2e Remove template matching and pseudo opcodes (Pieter Wuille) Pull request description: The current code contains a rather complex script template matching engine, which is only used for 3 particular script types (P2PK, P2PKH, multisig). The first two of these are trivial to match for otherwise, and a specialized matcher for multisig is both more compact and more efficient than a generic one. The goal is being more flexible, so that for example larger standard multisigs inside SegWit outputs are easier to implement. As a side-effect, it also gets rid of the pseudo opcodes hack. Tree-SHA512: 643b409c5c36821519f613a43efd399af0ec99b6131f35cd4024decfb2d483d719e0e921cd088bc9832a7ac797cb4a6b1158b8574c82f7fbebb75f1b31b359df

sipa mentioned this pull request May 9, 2018

[wallet] Support CMV signing of 17~20 key template #11545

Closed

laanwj added the Wallet label May 9, 2018

laanwj reviewed May 9, 2018

View reviewed changes

jtimon approved these changes May 9, 2018

View reviewed changes

instagibbs reviewed May 9, 2018

View reviewed changes

laanwj reviewed May 10, 2018

View reviewed changes

sipa force-pushed the 201805_noscriptpattern branch from 688d796 to 2fc4fdd Compare May 12, 2018 20:31

Empact reviewed May 16, 2018

View reviewed changes

sipa force-pushed the 201805_noscriptpattern branch from 2fc4fdd to fa1f642 Compare May 17, 2018 00:14

Empact reviewed May 26, 2018

View reviewed changes

sipa force-pushed the 201805_noscriptpattern branch from fa1f642 to 89736a9 Compare May 26, 2018 00:39

promag reviewed May 26, 2018

View reviewed changes

sipa force-pushed the 201805_noscriptpattern branch from 89736a9 to c639f5a Compare May 26, 2018 18:24

jl2012 reviewed May 29, 2018

View reviewed changes

sipa force-pushed the 201805_noscriptpattern branch from c639f5a to c814e2e Compare May 29, 2018 21:42

Bushstar mentioned this pull request Jun 1, 2018

commits from bitcoin/master FeatherCoin/Feathercoin#340

Merged

This was referenced Jun 1, 2018

scripted-diff: Avoid temporary copies when looping over std::map #13241

Merged

Avoid unused locals for CScript::IsWitnessProgram #12938

Closed

scripted-diff: Rename key size consts to be relative to their class #12461

Merged

jonasschnelli mentioned this pull request Aug 30, 2018

0.17.2rc issue (standardness change for bare multisig) #14104

Closed

jonasschnelli added the Needs release note label Aug 30, 2018

laanwj mentioned this pull request Aug 30, 2018

TODO for release notes 0.17.0 #12391

Closed

fanquake removed the Needs release note label Mar 20, 2019

nkostoulas mentioned this pull request Apr 11, 2019

Guardnode: CLTV multisig transaction Solver/Signing and Request changes commerceblock/ocean#109

Merged

sickpig mentioned this pull request Oct 10, 2019

[port] Remove template matching and pseudo opcodes BitcoinUnlimited/BitcoinUnlimited#1976

Merged

str4d mentioned this pull request Nov 14, 2019

Bitcoin script PRs 1 zcash/zcash#4227

Merged

DeckerSU added a commit to DeckerSU/KomodoOcean that referenced this pull request Mar 17, 2020

Remove template matching and pseudo opcodes

337442e

bitcoin/bitcoin#13194 zcash/zcash@2cb14d7 KomodoPlatform/komodo#298

furszy mentioned this pull request Jun 18, 2020

Upstream scripts back ports [Step 1] PIVX-Project/PIVX#1693

Merged

bitcoin locked as resolved and limited conversation to collaborators Dec 16, 2021

		}
		if (opcode != OP_0 && (opcode < OP_1 \|\| opcode > OP_16)) return false;

Remove template matching and pseudo opcodes #13194

Remove template matching and pseudo opcodes #13194

Uh oh!

Conversation

sipa commented May 9, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jtimon left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

sipa commented May 9, 2018

Uh oh!

instagibbs commented May 9, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Empact commented May 16, 2018

Uh oh!

jonasschnelli commented May 16, 2018

Uh oh!

gmaxwell commented May 25, 2018

Uh oh!

Empact May 26, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Empact commented May 26, 2018

Uh oh!

Empact commented May 26, 2018

Uh oh!

sipa commented May 9, 2018 •

edited

Loading

Empact May 26, 2018 •

edited

Loading

promag May 26, 2018 •

edited

Loading