Implement BIP 340-342 validation (Schnorr/taproot/tapscript)

sipa commented at 11:14 pm on January 21, 2020: member

This is an implementation of the Schnorr/taproot consensus rules proposed by BIPs 340, 341, and 342.

It consists of:

Addition of Schnorr signatures and 32-byte pubkey support to libsecp256k1 subtree (https://github.com/bitcoin-core/secp256k1/pull/558 PR 558), following BIP 340.
The taproot validation specified in BIP 341.
Script validation under taproot (aka tapscript), specified in BIP 342.
Addition of signing logic for Schnorr/Taproot to the Python test framework, and tests for the above.

This does not include any wallet support.

Related PRs and PRs that were extracted from this and submitted separately: #18002 #16902 #18388 #18401 #18422 #18675 #19228

Dependencies:

Merge BIP340 support in libsecp256k1
Update libsecp256k1 subtree in master (#19944)

TODO:

Tests for pre-activation (verify that consensus behavior doesn’t change until flag is enabled)
Extract small & fast BIP341/BIP342 test vectors with good coverage out of the programmatic & slow feature_taproot.py test

fanquake added the label Consensus on Jan 21, 2020

sipa force-pushed on Jan 21, 2020

DrahtBot commented at 11:47 pm on January 21, 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:

#19792 (rpc: Add dumpcoinstats by fjahr)
#19695 ([do not merge] Test impact of secp256k1 endianness detection change by sipa)
#19521 (Coinstats Index (without UTXO set hash) by fjahr)
#19438 (Introduce deploymentstatus by ajtowns)
#18788 (tests: Update more tests to work with descriptor wallets by achow101)
#16546 (External signer support - Wallet Box edition by Sjors)
#13533 ([tests] Reduced number of validations in tx_validationcache_tests by lucash-dev)
#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.

sipa force-pushed on Jan 22, 2020

in src/script/interpreter.cpp:1369 in 1f499c5b67 outdated

1365+uint256 HashAgain(const uint256& hash)
1366+{
1367+    uint256 result;
1368+    CSHA256().Write(hash.begin(), 32).Finalize(result.begin());
1369+    return result;
1370 }

junderw commented at 6:35 am on January 22, 2020:

Slightly confusing name… HashAgainSHA256?

I understand why it exists, and I can’t think of a much better name… but having something in the name to denote we’re hashing with SHA256 might make it a tiny bit more readable.

sipa commented at 8:12 pm on January 22, 2020:

Changed into SHA256Uint256, and moved to hash.{h,cpp}.

in src/chainparams.cpp:88 in 1f499c5b67 outdated

82@@ -83,6 +83,11 @@ class CMainParams : public CChainParams {
83         consensus.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].nStartTime = 1199145601; // January 1, 2008
84         consensus.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].nTimeout = 1230767999; // December 31, 2008
85 
86+        // Deployment of Taproot
87+        consensus.vDeployments[Consensus::DEPLOYMENT_TAPROOT].bit = 2;
88+        consensus.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].nStartTime = 1199145601; // January 1, 2008

kallewoof commented at 11:45 am on January 22, 2020:

s/TESTDUMMY/TAPROOT/ here and in testnet (regtest is fine). Also think you want to set timeout to something less expired.

sipa commented at 8:13 pm on January 22, 2020:

Nice catch, fixed. I don’t know what “less expired” means; all dates in the past are equally expired.

kallewoof commented at 1:47 am on January 23, 2020:

Sorry, I meant it should expire in the future or the taproot deployment will fail to activate.

sipa commented at 1:49 am on January 23, 2020:

This PR intentionally doesn’t include mainnet activation; the values here are just a dummy. Apart from the fact that no activation time (or mechanism) has been established yet, that activation logic will likely be included in a different release than the validation logic (thus needing a separate PR anyway).

in src/consensus/params.h:17 in 1f499c5b67 outdated

13@@ -14,6 +14,7 @@ namespace Consensus {
14 enum DeploymentPos
15 {
16     DEPLOYMENT_TESTDUMMY,
17+    DEPLOYMENT_TAPROOT, // Deployment of bip-taproot/bip-tapscript/bip-schnorr

MaxHillebrand commented at 2:31 pm on January 22, 2020:

0    DEPLOYMENT_TAPROOT, // Deployment of BIP-340/BIP-341/BIP-342

sipa commented at 8:13 pm on January 22, 2020:

Fixed.

in src/hash.h:221 in 1f499c5b67 outdated

217@@ -204,4 +218,12 @@ unsigned int MurmurHash3(unsigned int nHashSeed, const std::vector<unsigned char
218 
219 void BIP32Hash(const ChainCode &chainCode, unsigned int nChild, unsigned char header, const unsigned char data[32], unsigned char output[64]);
220 
221+/** Return a CHashWriter primed for computing bip-schnorr compatible tagged hashes.

MaxHillebrand commented at 2:32 pm on January 22, 2020:

0/** Return a CHashWriter primed for computing BIP-340 compatible tagged hashes.

sipa commented at 8:13 pm on January 22, 2020:

Fixed.

in src/secp256k1/include/secp256k1_schnorrsig.h:11 in 1f499c5b67 outdated

 6+#ifdef __cplusplus
 7+extern "C" {
 8+#endif
 9+
10+/** This module implements a variant of Schnorr signatures compliant with
11+ * BIP-schnorr

MaxHillebrand commented at 2:38 pm on January 22, 2020:

0 * BIP-340

sipa commented at 8:14 pm on January 22, 2020:

This belongs in https://github.com/bitcoin-core/secp256k1/pull/558.

in test/functional/test_framework/key.py:458 in 1f499c5b67 outdated

452@@ -384,3 +453,33 @@ def sign_ecdsa(self, msg, low_s=True):
453         rb = r.to_bytes((r.bit_length() + 8) // 8, 'big')
454         sb = s.to_bytes((s.bit_length() + 8) // 8, 'big')
455         return b'\x30' + bytes([4 + len(rb) + len(sb), 2, len(rb)]) + rb + bytes([2, len(sb)]) + sb
456+
457+    def sign_schnorr(self, msg):
458+        """Construct a bip-schnorr compatible signature with this key."""

MaxHillebrand commented at 2:45 pm on January 22, 2020:

0        """Construct a BIP-340 compatible Schnorr signature with this key."""

sipa commented at 8:14 pm on January 22, 2020:

Fixed.

MaxHillebrand commented at 2:48 pm on January 22, 2020: none

As the BIPs have now been assigned numbers, this changes…:

BIP-Schnorr to BIP-340
BIP-Taproot to BIP-341
BIP-Tapscript to BIP-342

in src/secp256k1/include/secp256k1_schnorrsig.h:12 in 1f499c5b67 outdated

 7+extern "C" {
 8+#endif
 9+
10+/** This module implements a variant of Schnorr signatures compliant with
11+ * BIP-schnorr
12+ * (https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki).

MaxHillebrand commented at 2:58 pm on January 22, 2020:

0 * (https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki).

This link is broken until the BIP PR is merged.

sipa commented at 8:14 pm on January 22, 2020:

This belongs in https://github.com/bitcoin-core/secp256k1/pull/558.

in src/secp256k1/include/secp256k1_schnorrsig.h:72 in 1f499c5b67 outdated

67+ * Returns 1 on success, 0 on failure.
68+ *  Args:    ctx: pointer to a context object, initialized for signing (cannot be NULL)
69+ *  Out:     sig: pointer to the returned signature (cannot be NULL)
70+ *  In:    msg32: the 32-byte message being signed (cannot be NULL)
71+ *        seckey: pointer to a 32-byte secret key (cannot be NULL)
72+ *       noncefp: pointer to a nonce generation function. If NULL, secp256k1_nonce_function_bipschnorr is used

MaxHillebrand commented at 2:59 pm on January 22, 2020:

0 *       noncefp: pointer to a nonce generation function. If NULL, secp256k1_nonce_function_bip340 is used

Not sure if this breaks anything? :confused:

sipa commented at 8:15 pm on January 22, 2020:

This belongs in https://github.com/bitcoin-core/secp256k1/pull/558.

MaxHillebrand commented at 8:40 pm on January 22, 2020:

I have suggested the changes there

in src/secp256k1/src/modules/schnorrsig/main_impl.h:67 in 1f499c5b67 outdated

62+    ARG_CHECK(sig != NULL);
63+    ARG_CHECK(msg32 != NULL);
64+    ARG_CHECK(seckey != NULL);
65+
66+    if (noncefp == NULL) {
67+        noncefp = secp256k1_nonce_function_bipschnorr;

MaxHillebrand commented at 3:00 pm on January 22, 2020:

0        noncefp = secp256k1_nonce_function_bip-340;

Not sure if this breaks anything :confused:

sipa commented at 8:15 pm on January 22, 2020:

This belongs in https://github.com/bitcoin-core/secp256k1/pull/558. Also, that would be invalid C code.

in src/secp256k1/src/modules/schnorrsig/main_impl.h:87 in 1f499c5b67 outdated

82+    if (!secp256k1_fe_is_quad_var(&pk.y)) {
83+        secp256k1_scalar_negate(&x, &x);
84+    }
85+
86+    secp256k1_scalar_get_b32(seckey_tmp, &x);
87+    if (!noncefp(buf, msg32, seckey_tmp, (unsigned char *) "BIPSchnorrDerive", (void*)ndata, 0)) {

MaxHillebrand commented at 3:00 pm on January 22, 2020:

0    if (!noncefp(buf, msg32, seckey_tmp, (unsigned char *) "BIP340Derive", (void*)ndata, 0)) {

Not sure if this breaks anything :confused:

sipa commented at 8:15 pm on January 22, 2020:

Changing that would violate the spec.

in src/policy/policy.cpp:240 in 1f499c5b67 outdated

235+        // Check P2TR standard limits
236+        if (witnessversion == 1 && witnessprogram.size() == WITNESS_V1_TAPROOT_SIZE && !prevScript.IsPayToScriptHash()) {
237+            // Taproot spend
238+            const auto& stack = tx.vin[i].scriptWitness.stack;
239+            size_t stack_size = stack.size();
240+            if (stack_size >= 2 && !stack[stack_size - 1].empty() && stack[stack_size - 1][0] == ANNEX_TAG) {

skwp commented at 3:32 pm on January 22, 2020:

Is there a name for this condition that can be explained with a function name or at least a comment?

kallewoof commented at 4:13 pm on January 22, 2020:

I don’t see the problem, personally.

skwp commented at 5:47 pm on January 22, 2020:

hey kalle, please see my comment below to pieter. I’m seeing if people are open to using a more consistent single level of abstraction to make the source easier to read.

e.g. this can be evaluated by a newb (ignore if I got the concepts wrong, I’m trying to illustrate a more literate / single level of abstraction style as per http://principles-wiki.net/principles:single_level_of_abstraction)

0if (payToTapRoot)
1  if annexOnStack
2    stack_size--; // ignore annex
3  else 
4    if (OpWhateverOnStack)
5      checkWhateverConditionWithLoop
6    end

Again I could have totally gotten the details wrong but if the program looked like that at a single level of abstraction, with magic numbers given names and conditionals given names, many more people could actually participate in the PR process and grok what’s going on.

sipa commented at 8:16 pm on January 22, 2020:

I’ve added some comments. Better now?

skwp commented at 9:12 pm on January 22, 2020:

Thanks definitely helps, though I would still love to see some vars extracted to named for readability and deduplication. I’m not gonna nitpick your code for style, I’m just a humble bitcoin pleb. But I do know what it’s like to scale codebases to be friendly to onboarding new devs. I do think readability should be a concern if we want more devs in bitcoin. e.g. stack[stack_size - 1] is repeated all over the place. call it top_of_stack and so much more readable! 🤷‍♂ 😄

sipa commented at 9:22 pm on January 22, 2020:

Well the reason is that the stack_size variable changes, so a “top_of_stack” one would need to be updated, kinda defeating its meaning.

sipa commented at 1:42 am on January 23, 2020:

I’ve changed this code quite a bit. What do you think?

in src/policy/policy.cpp:245 in 1f499c5b67 outdated

240+            if (stack_size >= 2 && !stack[stack_size - 1].empty() && stack[stack_size - 1][0] == ANNEX_TAG) {
241+                stack_size--; // Ignore annex
242+            }
243+            if (stack_size >= 2) {
244+                // Script path spend
245+                if ((stack[stack_size - 1][0] & 0xfe) == 0xc0) {

skwp commented at 3:35 pm on January 22, 2020:

why nested conditional here, but not nested above (line 240)? both branches have “stack_size >= 2” as well. without understanding what any of this means, would it be clearer to write like this, removing the duplication and nesting?

0// precondition for taproot (?)
1if (stack_size < 2) { return }
2
3if (!stack[stack_size - 1].empty() && stack[stack_size - 1][0] == ANNEX_TAG) {
4// whatever this is
5
6} else if ((stack[stack_size - 1][0] & 0xfe) == 0xc0)) {
7// script path spend
8
9}

sipa commented at 5:26 pm on January 22, 2020:

@skwp I’ll add some comments to clarify, but what you’re suggesting would be incorrect.

skwp commented at 5:39 pm on January 22, 2020:

Thanks @sipa. I’m not trying to nitpick, rather looking at ways to lower the barrier for reviewers and thus help get more eyes on things. I find that complex conditionals with lots of low level details can make bugs hard to spot and make it daunting for people new to the source to contribute. There might be good reason for the style employed throughout the code and we probably can’t change everything overnight, but even things like magic numbers (0xfe?? 0xc0??) everywhere makes it really hard to reason about, imho. Seems like we can make the source easier to read as we go with named conditionals, constants, etc.

skwp commented at 5:52 pm on January 22, 2020:

In fact I see that these magic numbers are already given names elsewhere. Can we use them here? This is way more readable and expresses intent

0(stack[stack_size - 1][0] & TAPROOT_LEAF_MASK) == TAPROOT_LEAF_TAPSCRIPT

sipa commented at 8:18 pm on January 22, 2020:

Changed it to use the constants, that’s obviously the better way.

The reason why the annex does not use a nested conditional is because it’s a single if statement that tests the presence of the annex (as in: both conditions are needed to have an annex). The tapscript conditional is split up into the logical “this is a script path spending” condition and the “this is a leaf version 0xc0 script”.

sipa commented at 5:25 pm on January 22, 2020: member

@MaxHillebrand A few overall comments:

I don’t think all references to (bip-)taproot/tapscript/schnorr should be changed to the BIP numbers; in some cases maybe we should just drop the “bip-” prefix (e.g. I think talking about a “taproot spend” is more clear than “bip341 spend”).
All changes in the src/secp256k1 directory should go to https://github.com/bitcoin-core/secp256k1/pull/558 instead (the src/secp256k1 is a git subtree imported from there).
The “BIPSchnorr” and “BIPSchnorrDerive” tagged hash tags are part of the spec, which I don’t think should be changed.

MaxHillebrand commented at 5:34 pm on January 22, 2020: none

Thanks @sipa, I agree with your comments. I have deleted my suggestions to change the tagged hashes, the others are still open. Please ACK/NACK and commit what you think is correct.

in src/hash.cpp:94 in 1f499c5b67 outdated

82+CHashWriter TaggedHash(const std::string& tag)
83+{
84+    CHashWriter writer(SER_GETHASH, 0);
85+    uint256 taghash;
86+    CSHA256().Write((unsigned char*)tag.data(), tag.size()).Finalize(taghash.begin());
87+    writer << taghash << taghash;

constcast-glitch commented at 7:42 pm on January 22, 2020:

taghash is written twice. Is this intentional?

sipa commented at 7:45 pm on January 22, 2020:

Yes, please read the spec.

in src/hash.cpp:86 in 1f499c5b67 outdated

77@@ -77,3 +78,12 @@ void BIP32Hash(const ChainCode &chainCode, unsigned int nChild, unsigned char he
78     num[3] = (nChild >>  0) & 0xFF;
79     CHMAC_SHA512(chainCode.begin(), chainCode.size()).Write(&header, 1).Write(data, 32).Write(num, 4).Finalize(output);
80 }
81+
82+CHashWriter TaggedHash(const std::string& tag)
83+{
84+    CHashWriter writer(SER_GETHASH, 0);
85+    uint256 taghash;
86+    CSHA256().Write((unsigned char*)tag.data(), tag.size()).Finalize(taghash.begin());

Empact commented at 7:49 pm on January 22, 2020:

nit: reinterpret_cast<unsigned char*>(const_cast<char*>(?

The const_cast could be removed with C++17 and a switch to rvalue references.

sipa commented at 8:11 pm on January 22, 2020:

This should just be (const char*)tag.data. We don’t usually use C++ style casts for primitive types (they’re all equivalent anyway, and the C++ style ones are very verbose).

sipa force-pushed on Jan 22, 2020

in src/consensus/params.h:17 in 9f578bfcc7 outdated

13@@ -14,6 +14,7 @@ namespace Consensus {
14 enum DeploymentPos
15 {
16     DEPLOYMENT_TESTDUMMY,
17+    DEPLOYMENT_TAPROOT, // Deployment of taproot (BIPs 340-342)

nopara73 commented at 8:15 pm on January 22, 2020:

Unify Taproot capitalization in comments.

0    DEPLOYMENT_TAPROOT, // Deployment of Taproot (BIPs 340-342)

sipa commented at 1:43 am on January 23, 2020:

Updated.

nopara73 commented at 3:13 am on January 23, 2020:

Btw, I wasn’t planning to waste your time on this by suggesting to manually fix it up. You can just click apply suggestion on GitHub and it’ll create a shared commit.

in src/script/interpreter.h:128 in 9f578bfcc7 outdated

119@@ -114,32 +120,98 @@ enum
120     // Making OP_CODESEPARATOR and FindAndDelete fail any non-segwit scripts
121     //
122     SCRIPT_VERIFY_CONST_SCRIPTCODE = (1U << 16),
123+
124+    // Taproot validation
125+    //
126+    SCRIPT_VERIFY_TAPROOT = (1U << 17),
127+
128+    // Making unknown taproot leaf versions non-standard

nopara73 commented at 8:16 pm on January 22, 2020:

Unify Taproot capitalization in comments.

0    // Making unknown Taproot leaf versions non-standard

sipa commented at 1:43 am on January 23, 2020:

Updated.

in src/script/script.cpp:141 in 9f578bfcc7 outdated

137@@ -138,6 +138,9 @@ const char* GetOpName(opcodetype opcode)
138     case OP_NOP9                   : return "OP_NOP9";
139     case OP_NOP10                  : return "OP_NOP10";
140 
141+    // taproot

nopara73 commented at 8:17 pm on January 22, 2020:

Unify Taproot capitalization in comments.

0    // Taproot

sipa commented at 1:43 am on January 23, 2020:

Updated.

in src/script/script.h:201 in 9f578bfcc7 outdated

197@@ -187,6 +198,9 @@ enum opcodetype
198     OP_NOP9 = 0xb8,
199     OP_NOP10 = 0xb9,
200 
201+    // taproot

nopara73 commented at 8:17 pm on January 22, 2020:

Unify Taproot capitalization in comments.

0    // Taproot

sipa commented at 1:44 am on January 23, 2020:

Updated.

in test/functional/p2p_segwit.py:1369 in 9f578bfcc7 outdated

1364@@ -1364,7 +1365,11 @@ def test_segwit_versions(self):
1365         assert_equal(len(self.nodes[1].getrawmempool()), 0)
1366         for version in list(range(OP_1, OP_16 + 1)) + [OP_0]:
1367             # First try to spend to a future version segwit script_pubkey.
1368-            script_pubkey = CScript([CScriptOp(version), witness_hash])
1369+            if version == OP_1:
1370+                # Don't use 32-byte v1 witness (used by taproot)

nopara73 commented at 8:18 pm on January 22, 2020:

Unify Taproot capitalization in comments.

0                # Don't use 32-byte v1 witness (used by Taproot)

sipa commented at 1:44 am on January 23, 2020:

Updated.

in test/functional/feature_taproot.py:5 in 9f578bfcc7 outdated

0@@ -0,0 +1,600 @@
1+#!/usr/bin/env python3
2+# Copyright (c) 2019 The Bitcoin Core developers
3+# Distributed under the MIT software license, see the accompanying
4+# file COPYING or http://www.opensource.org/licenses/mit-license.php.
5+# Test taproot softfork.

nopara73 commented at 8:24 pm on January 22, 2020:

Unify Taproot capitalization in comments.

0# Test Taproot softfork.

sipa commented at 1:44 am on January 23, 2020:

Updated.

in src/script/interpreter.cpp:1449 in 9f578bfcc7 outdated

1449+    // Epoch
1450+    uint8_t epoch = 0;
1451+    ss << epoch;
1452+
1453+    // Hash type
1454+    if ((hash_type > 3) && (hash_type < 0x81 || hash_type > 0x83)) return false;

Empact commented at 8:29 pm on January 22, 2020:

nit: Perhaps more readable if we avoid magic numbers with something like:

0static_assert(SIGHASH_TAPOUTPUTMASK < SIGHASH_TAPINPUTMASK);
1if ((hash_type > SIGHASH_TAPOUTPUTMASK) && (hash_type <= SIGHASH_TAPINPUTMASK || hash_type > (SIGHASH_TAPINPUTMASK | SIGHASH_TAPOUTPUTMASK))) return false;

Alternatively, a comment could be helpful.

gmaxwell commented at 4:36 pm on January 23, 2020:

I find that much less readable, particularly since the symbolic values you define wouldn’t be used anywhere else. More comments, however, would be fine.

sipa commented at 2:32 am on January 25, 2020:

I’ve rewritten this code in an overall more readable way, I think.

in src/script/interpreter.cpp:1472 in 9f578bfcc7 outdated

1472+    // Data about the input/prevout being spent
1473+    const CScript& scriptPubKey = cache.m_spent_outputs[in_pos].scriptPubKey;
1474+    uint8_t spend_type = 0;
1475+    assert(execdata.m_annex_init);
1476+    if (execdata.m_annex_present) {
1477+        spend_type |= 1;

Empact commented at 8:30 pm on January 22, 2020:

nit: is it clearer to use or comment e.g. WITNESS_V0, and TAPROOT below?

sipa commented at 2:33 am on January 25, 2020:

I’ve rewritten this code to match the BIP specification more closely.

in src/policy/policy.cpp:246 in 9f578bfcc7 outdated

241+                stack_size--; // Ignore annex if present
242+            }
243+            if (stack_size >= 2) {
244+                // Script path spend (2 or more stack elements are removing optional annex)
245+                if ((stack[stack_size - 1][0] & TAPROOT_LEAF_MASK) == TAPROOT_LEAF_TAPSCRIPT) {
246+                    // Leaf version 0xc0 (aka tapscript, see BIP 342)

MaxHillebrand commented at 8:41 pm on January 22, 2020:

0                    // Leaf version 0xc0 (aka Tapscript, see BIP 342)

sipa commented at 2:48 am on January 23, 2020:

Updated.

in src/policy/policy.h:43 in 9f578bfcc7 outdated

39@@ -40,6 +40,8 @@ static const bool DEFAULT_PERMIT_BAREMULTISIG = true;
40 static const unsigned int MAX_STANDARD_P2WSH_STACK_ITEMS = 100;
41 /** The maximum size of each witness stack item in a standard P2WSH script */
42 static const unsigned int MAX_STANDARD_P2WSH_STACK_ITEM_SIZE = 80;
43+/** The maximum size of each witness stack item in a standard tapscript */

MaxHillebrand commented at 8:42 pm on January 22, 2020:

0/** The maximum size of each witness stack item in a standard Tapscript */

sipa commented at 2:47 am on January 23, 2020:

Updated.

in src/script/interpreter.h:139 in 9f578bfcc7 outdated

134+    SCRIPT_VERIFY_DISCOURAGE_UNKNOWN_ANNEX = (1U << 19),
135+
136+    // Making unknown OP_SUCCESS non-standard
137+    SCRIPT_VERIFY_DISCOURAGE_OP_SUCCESS = (1U << 20),
138+
139+    // Making unknown public key versions in tapscript non-standard

MaxHillebrand commented at 8:42 pm on January 22, 2020:

0    // Making unknown public key versions in Tapscript non-standard

sipa commented at 2:47 am on January 23, 2020:

Updated.

in src/script/script.h:52 in 9f578bfcc7 outdated

43@@ -44,6 +44,17 @@ static const unsigned int LOCKTIME_THRESHOLD = 500000000; // Tue Nov  5 00:53:20
44 // SEQUENCE_FINAL).
45 static const uint32_t LOCKTIME_MAX = 0xFFFFFFFFU;
46 
47+// Tag for input annex. If there are at least two witness elements for a transaction input,
48+// and the first byte of the last element is 0x50, this last element is called annex, and
49+// has meanings independent of the script
50+static const unsigned int ANNEX_TAG = 0x50;
51+
52+// Validation weight per passing signature (tapscript only).

MaxHillebrand commented at 8:42 pm on January 22, 2020:

0// Validation weight per passing signature (Tapscript only).

sipa commented at 2:48 am on January 23, 2020:

Updated.

in src/script/script.h:55 in 9f578bfcc7 outdated

50+static const unsigned int ANNEX_TAG = 0x50;
51+
52+// Validation weight per passing signature (tapscript only).
53+static constexpr uint64_t VALIDATION_WEIGHT_PER_SIGOP_PASSED = 50;
54+
55+// How much weight budget is added to the witness size (tapscript only).

MaxHillebrand commented at 8:42 pm on January 22, 2020:

0// How much weight budget is added to the witness size (Tapscript only).

sipa commented at 2:48 am on January 23, 2020:

Updated.

in test/functional/test_framework/script.py:232 in 9f578bfcc7 outdated

228@@ -223,11 +229,8 @@ def __new__(cls, n):
229 OP_NOP9 = CScriptOp(0xb8)
230 OP_NOP10 = CScriptOp(0xb9)
231 
232-# template matching params
233-OP_SMALLINTEGER = CScriptOp(0xfa)
234-OP_PUBKEYS = CScriptOp(0xfb)
235-OP_PUBKEYHASH = CScriptOp(0xfd)
236-OP_PUBKEY = CScriptOp(0xfe)
237+# tapscript

MaxHillebrand commented at 8:43 pm on January 22, 2020:

0# Tapscript

sipa commented at 2:48 am on January 23, 2020:

Updated.

MaxHillebrand commented at 8:46 pm on January 22, 2020: none

Similar to Taproot, this unifies the upper case Tapscript consistently in the comments.

in src/policy/policy.cpp:240 in 9f578bfcc7 outdated

235+        // Check P2TR standard limits
236+        if (witnessversion == 1 && witnessprogram.size() == WITNESS_V1_TAPROOT_SIZE && !prevScript.IsPayToScriptHash()) {
237+            // Taproot spend (non-P2SH-wrapped, version 1, witness program size 32; see BIP 341)
238+            const auto& stack = tx.vin[i].scriptWitness.stack;
239+            size_t stack_size = stack.size();
240+            if (stack_size >= 2 && !stack[stack_size - 1].empty() && stack[stack_size - 1][0] == ANNEX_TAG) {

Empact commented at 8:56 pm on January 22, 2020:

~~nit: stack.back()~~

Neglected to examine the full context.

sipa commented at 8:56 pm on January 22, 2020:

No, that would be incorrect.

sipa force-pushed on Jan 22, 2020

in src/pubkey.cpp:177 in 2c55acda1c outdated

166@@ -166,6 +167,23 @@ static int ecdsa_signature_parse_der_lax(const secp256k1_context* ctx, secp256k1
167     return 1;
168 }
169 
170+bool XOnlyPubKey::VerifySchnorr(const uint256 &hash, const std::vector<unsigned char>& sigbytes) const {
171+    if (sigbytes.size() != 64) return false;

Empact commented at 9:08 pm on January 22, 2020:

nit: how about != sizeof(((secp256k1_schnorrsig){0}).data), a static_assert, or similar?

real-or-random commented at 10:50 pm on January 22, 2020:

In the end, all of this is probably personal taste but I think there is a reason why a lot of those magic numbers are just literals. This number will never need to change. sizeof(((secp256k1_schnorrsig){0}).data) just makes the code harder to read and review (because you need to look up the definition of secp256k1_schnorrsig, and it would be a little bit like having a constant BITS_IN_UINT256 = 256.

Empact commented at 11:44 pm on January 22, 2020:

The notion is that by tying one constant to a formal description, we can make explicit and enforced a connection that would otherwise be implicit and unenforced. IMO, that such a thing can’t be violated is always better than that it won’t be violated.

There are ways to do that without making the code markedly more complex, such as offloading it to a constant + static_assert.

gmaxwell commented at 4:30 pm on January 23, 2020:

I agree with real-or-random.

secp256k1_schnorrsig should be “functionally opaque”– like the other secp256k1_ types it isn’t actually an opaque struct only so it can be allocated on the stack. Library users should not be messing around with the internals of these types, and the library API makes no promise that the internal representation won’t change (and for some of them it’s even currently different on different platforms– although not this one).

If the representation of secp256k1_schnorrsig were to change, signatures with sizes other than 64 bytes wouldn’t suddenly become valid in Bitcoin.

If you were talking about a ‘64’ who’s purposes was to allocate memory to store a secp256k1_schnorrsig then your reflex to interrogate it with sizeof would be well placed– but that isn’t the case here. The data field in a secp256k1_schnorrsig could change length pretty arbitrarily (for example, storing R decompressed) and this line wouldn’t change).

sipa commented at 1:48 am on January 25, 2020:

I agree as well. The size of serialized signatures is not inherently related to the in-memory representation of secp256k1_schnorrsig.

The BIP says something about sizes 64 and 65. The code does the exact same thing. You could introduce a constant, but I think that’s just distracting. You’d need to go look up the constant to verify the code is correct, while now you can just directly compare it with the BIP.

in src/script/interpreter.cpp:459 in 2c55acda1c outdated

456+        return set_error(serror, SCRIPT_ERR_STACK_SIZE);
457+    }
458     int nOpCount = 0;
459     bool fRequireMinimal = (flags & SCRIPT_VERIFY_MINIMALDATA) != 0;
460+    uint32_t opcode_pos = 0;
461+    execdata.m_codeseparator_pos = 0xFFFFFFFFUL;

Empact commented at 10:15 pm on January 22, 2020:

nit: a NONE_EXECUTED constant would be expressive

gmaxwell commented at 4:16 pm on January 23, 2020:

It’s never reused. Renaming it just makes you look up a definition. Adding a comment like “// Fall-through value if none are executed.” would be both more informative and not create a reason to bounce around the code.

Empact commented at 4:52 pm on January 23, 2020:

Fair enough, it’s a matter of opinion as to which is more legible - though I see a few uses, e.g.: https://github.com/bitcoin/bitcoin/pull/17977/files#diff-b81dfdd8a5bd80fe9f82b5a40c4c991eR180

sipa commented at 2:33 am on January 25, 2020:

That initialization wasn’t needed actually, I’ve removed it. The constant in just in one place now.

in test/functional/test_framework/key.py:368 in 2c55acda1c outdated

363+            return False
364+        s = int.from_bytes(sig[32:64], 'big')
365+        if s >= SECP256K1_ORDER:
366+            return False
367+        e = int.from_bytes(TaggedHash("BIPSchnorr", sig[0:32] + self.get_bytes()[1:33] + msg), 'big') % SECP256K1_ORDER
368+        if self.is_positive:

jnewbery commented at 10:59 pm on January 22, 2020:

This seems weird to me. How can we verify a signature for a point which does not have a square Y? Such public keys are not defined in bip-schnorr.

I think it’d be clearer to assert that the pubkey has a square Y before verifying. I’d also suggest adding a get_xonly_pubkey() method to ECKey so we can directly get the valid bip-schnorr pubkey.

real-or-random commented at 11:39 pm on January 22, 2020:

This seems weird to me. How can we verify a signature for a point which does not have a square Y? Such public keys are not defined in bip-schnorr.

Hm in fact it’s different in yet another way.

The very pedantic version: bip-schnorr defines public keys to be byte arrays of length 32. “square y” does not make sense for byte arrays.
The less pedantic version: Even if you interpret the byte array as an integer, it’s supposed to encode an x-coordinate only. “square y” does not make sense for an x-coordinate.

If we want to be compatible with the existing code here, I’m not sure what the best approach is. Maybe it makes more sense to accept a byte string, then parse it into a point and then use the existing code? edit: Well okay, I think in the end that’s already happening in the code, but I think it will still be cleaner if the verify_schnorr function would not take points directly.

jnewbery commented at 2:18 pm on January 23, 2020:

verify_schnorr has been updated to be a function that takes a pubkey (32-byte array) instead of being a method on ECPubKey.

sipa commented at 2:34 am on January 25, 2020:

I’ve completely rewritten the Python Schnorr code now, not using ECKey/ECPubKey at all.

sipa force-pushed on Jan 23, 2020

in src/script/interpreter.h:30 in 41acd620b5 outdated

25@@ -24,6 +26,10 @@ enum
26     SIGHASH_NONE = 2,
27     SIGHASH_SINGLE = 3,
28     SIGHASH_ANYONECANPAY = 0x80,
29+
30+    SIGHASH_TAPDEFAULT = 0,

v1048576 commented at 9:51 am on January 23, 2020:

Use taproot instead of tap? SIGHASH_TAPROOT_DEFAULT TAPROOT like other instances, e.g. TAPROOT_PROGRAM_SIZE.

Also, SignatureHashTap() renamed to SignatureHashTaproot()? Similar to VerifyTaprootCommitment.

sipa commented at 2:37 am on January 25, 2020:

Agree, those enum values were weird. Changed to SIGHASH_INPUT_MASK, SIGHASH_OUTPUT_MASK, and SIGHASH_DEFAULT; even though they’re Taproot specific for now, that’s not inherently the case.

SignatureHashTap wasn’t actually necessary, it was a leftover from older code. I’ve removed it.

in src/script/script.cpp:337 in 41acd620b5 outdated

328@@ -326,3 +329,11 @@ bool GetScriptOp(CScriptBase::const_iterator& pc, CScriptBase::const_iterator en
329     opcodeRet = static_cast<opcodetype>(opcode);
330     return true;
331 }
332+
333+bool IsOpSuccess(const opcodetype& opcode)
334+{
335+    return (opcode == 0x50 || opcode == 0x62 || opcode == 0x89 ||

v1048576 commented at 9:59 am on January 23, 2020:

Why not check against opcode defines?

gmaxwell commented at 4:32 pm on January 23, 2020:

Because they’re all “OP_SUCCESS”? They aren’t other opcodes right now. Some of them share values with non-tapscript opcodes, but the usage is different.

v1048576 commented at 5:28 pm on January 23, 2020:

I was expecting something along the lines of OP_SUCCESS80, …, OP_SUCCESS254. OP_SUCCESSx mapping explicitly shows the shared opcodes?

sipa commented at 2:08 am on January 25, 2020:

I considered that, but I don’t think the amount of code needed is worth it, or would be more readable (if there isn’t a normative IsOpSuccess function, you’d be adding 87 constants to the enum, and instead writing “opcode == OP_SUCCESS80 || opcode == OP_SUCCESS98 || opcode == OP_SUCCESS126 || …” in ExecuteWitnessProgram directly).

v1048576 commented at 3:42 pm on January 25, 2020:

Ah yes, good point about 87 constants, thanks for the clarification.

in test/functional/feature_taproot.py:403 in 41acd620b5 outdated

398+        for annex in [None, bytes([ANNEX_TAG]) + random_bytes(random.randrange(0, 250))]:
399+            standard = annex is None
400+            sec1, sec2 = ECKey(), ECKey()
401+            sec1.generate()
402+            sec2.generate()
403+            pub1, pub2 = sec1.get_pubkey(), sec2.get_pubkey()

jnewbery commented at 2:27 pm on January 23, 2020:

Should these be updated to be BIP schnorr pubkeys (32-byte arrays)?

sipa commented at 2:38 am on January 25, 2020:

Done by completely rewriting the Schnorr Python code.

in src/script/sigcache.cpp:101 in 41acd620b5 outdated

86@@ -79,15 +87,25 @@ void InitSignatureCache()
87             (nElems*sizeof(uint256)) >>20, (nMaxCacheSize*2)>>20, nElems);
88 }
89 
90-bool CachingTransactionSignatureChecker::VerifySignature(const std::vector<unsigned char>& vchSig, const CPubKey& pubkey, const uint256& sighash) const
91+bool CachingTransactionSignatureChecker::VerifyECDSASignature(const std::vector<unsigned char>& vchSig, const CPubKey& pubkey, const uint256& sighash) const

constcast-glitch commented at 4:49 pm on January 23, 2020:

nit: This function (VerifyECDSASignature) is formatted different than VerifySchnorrSignature which have the single line if-statements on one line. Maybe use same formatting for consistency since the functions are very similar in layout. I guess it’s because this function already existed and don’t want to make unrelated formatting changes. New here so not sure if this is a valid remark. Please excuse me if so.

sipa commented at 2:11 am on January 25, 2020:

This is intentional, see https://github.com/bitcoin/bitcoin/blob/master/doc/developer-notes.md#coding-style-general:

When writing patches, favor the new style over attempting to mimic the surrounding style, except for move-only commits.

Do not submit patches solely to modify the style of existing code.

So the new Schnorr code follows the preferred style, even though the ECDSA one retains the style it had before.

sipa force-pushed on Jan 23, 2020

sipa force-pushed on Jan 25, 2020

in test/functional/feature_taproot.py:9 in b8048b8148 outdated

0@@ -0,0 +1,594 @@
1+#!/usr/bin/env python3
2+# Copyright (c) 2019 The Bitcoin Core developers
3+# Distributed under the MIT software license, see the accompanying
4+# file COPYING or http://www.opensource.org/licenses/mit-license.php.
5+# Test Taproot softfork (BIPs 340-342)
6+
7+from test_framework.blocktools import create_coinbase, create_block, add_witness_commitment
8+from test_framework.messages import CTransaction, CTxIn, CTxOut, COutPoint, CTxInWitness
9+from test_framework.script import CScript, TaprootSignatureHash, taproot_construct, OP_0, OP_1, OP_CHECKSIG, OP_CHECKSIGVERIFY, OP_CHECKSIGADD, OP_IF, OP_CODESEPARATOR, OP_ELSE, OP_ENDIF, OP_DROP, LEAF_VERSION_TAPSCRIPT, SIGHASH_SINGLE, is_op_success, CScriptOp, OP_RETURN, OP_VERIF, OP_1NEGATE, OP_EQUAL, OP_SWAP, OP_CHECKMULTISIG, OP_CHECKMULTISIGVERIFY, OP_NOTIF, OP_2DROP, OP_NOT, OP_2DUP, OP_1SUB, OP_DUP, MAX_SCRIPT_ELEMENT_SIZE, LOCKTIME_THRESHOLD, ANNEX_TAG

kallewoof commented at 2:35 am on January 25, 2020:

 0from test_framework.script import (
 1    ANNEX_TAG,
 2    CScript,
 3    CScriptOp,
 4    LEAF_VERSION_TAPSCRIPT,
 5    LOCKTIME_THRESHOLD,
 6    MAX_SCRIPT_ELEMENT_SIZE,
 7    OP_0,
 8    OP_1,
 9    OP_1SUB,
10    OP_1NEGATE,
11    OP_2DROP,
12    OP_2DUP,
13    OP_CHECKMULTISIG,
14    OP_CHECKMULTISIGVERIFY,
15    OP_CHECKSIG,
16    OP_CHECKSIGADD,
17    OP_CHECKSIGVERIFY,
18    OP_CODESEPARATOR,
19    OP_DROP,
20    OP_DUP,
21    OP_ELSE,
22    OP_ENDIF,
23    OP_EQUAL,
24    OP_IF,
25    OP_NOT,
26    OP_NOTIF,
27    OP_RETURN,
28    OP_SWAP,
29    OP_VERIF,
30    SIGHASH_SINGLE,
31    TaprootSignatureHash,
32    is_op_success,
33    taproot_construct,
34)

sipa commented at 2:39 am on January 25, 2020:

What a waste of lines. Is this more readable?

kallewoof commented at 2:52 am on January 25, 2020:

Lines don’t really cost anything. This is definitely readable, compared to the big blob it replaces.

sipa commented at 2:55 am on January 25, 2020:

They cost screen space, and this isn’t something that really requires reading.

kallewoof commented at 3:00 am on January 25, 2020:

It feels like people can just scroll down if they aren’t interested, or not if they are. I prefer to let the reader decide whether they desire to read or not. Anyway, it’s not big enough to waste time over. Do ignore.

sipa commented at 6:56 pm on March 21, 2020:

Done.

in src/script/interpreter.cpp:1777 in b8048b8148 outdated

1775+    if (tapleaf_hash) *tapleaf_hash = k;
1776+    for (int i = 0; i < path_len; ++i) {
1777+        CHashWriter ss_branch = HasherTapBranch;
1778+        auto node_begin = control.data() + TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * i;
1779+        if (std::lexicographical_compare(k.begin(), k.end(), node_begin, node_begin + TAPROOT_CONTROL_NODE_SIZE)) {
1780+           ss_branch << k << Span<const unsigned char>(node_begin, TAPROOT_CONTROL_NODE_SIZE);

kallewoof commented at 6:10 am on January 25, 2020:

Nit: indentation (here and L1781).

sipa commented at 6:58 pm on March 21, 2020:

Done.

fanquake deleted a comment on Jan 25, 2020

in src/script/interpreter.h:182 in b8048b8148 outdated

179+    //! The tapleaf hash.
180+    uint256 m_tapleaf_hash;
181+
182+    //! Whether m_codeseparator_pos is initialized.
183+    bool m_codeseparator_pos_init = false;
184+    //! Opcode position of the last executed OP_CODESEPARATOR (or -1 if none executed).

JeremyRubin commented at 6:30 pm on January 25, 2020:

documentation nit: preference to not use -1 to indicate a sentinel for a unsigned type.

sipa commented at 6:58 pm on March 21, 2020:

Done.

in src/script/interpreter.h:195 in b8048b8148 outdated

185+    uint32_t m_codeseparator_pos;
186+
187+    //! Whether m_annex_present and m_annex_hash are initialized.
188+    bool m_annex_init = false;
189+    //! Whether an annex is present.
190+    bool m_annex_present;

JeremyRubin commented at 6:32 pm on January 25, 2020:

UB nit: while this is safe, I believe, as it is used, it would be better to initialize this to either true or false should there be a bug, it would at least not invoke UB.

sipa commented at 6:35 pm on January 25, 2020:

Not initializing it means giving valgrind a chance to detect incorrect use. I prefer to keep values uninitialized if they’re actually intended to not be used.

JeremyRubin commented at 6:49 pm on January 25, 2020:

That’s an interesting point I hadn’t considered! Could be an interesting separate project idea to have a macro of something like

DEFINED_CONSENSUS(param) ---> if not VALGRIND_BUILD param endig

to make sure that we define these things when we build for consensus, but to leave them undefined for valigrind.

This could be expanded to, for class members which you want to have this check, to union/wrap and define an accessor function via macro to avoid class initialization and be able to check initialization for arbitrary things not just primitives.

sipa commented at 6:59 pm on January 25, 2020:

Does that really add anything? Yes, it technically removes UB in this case, but replaces it with incorrect consensus code. Furthermore, there already is a runtime check to avoid it (the _init) flag, and the ability to detect it during tests through Valgrind/ubsan/… (in the even less likely case the _init flag is set incorrectly).

I feel this is all overkill, and we should just stick to the common practice of not initializing variables that deliberately hold no value.

JeremyRubin commented at 7:12 pm on January 25, 2020:

My point was more that we don’t get the valgrind checkability for non primitive types, which seems like a good property if we want it for primitive types. A 0’d hash should be treated as undefined so that valgrind could pick it up.

But I’m resolving this convo here as it’s a sidetrack, as noted above, “Could be an interesting separate project idea”.

in src/script/interpreter.h:180 in b8048b8148 outdated

170+    WITNESS_V0 = 1,  //!< Witness v0 (P2WPKH and P2WSH); see BIP 141
171+    TAPROOT = 2,     //!< Witness v1 with non-P2SH 32 byte program (Taproot), key path spending; see BIP 341
172+    TAPSCRIPT = 3,   //!< Witness v1 with non-P2SH 32 byte program (Taproot), script path spending, leaf version 0xc0 (Tapscript); see BIP 342
173+};
174+
175+struct ScriptExecutionData

JeremyRubin commented at 6:43 pm on January 25, 2020:

I’m generally not a fan of these Data interfaces which have all the bool x_init fields.

As an alternative, we could use an optional type wrapper.

However, optional types depend on boost until c++17, which we shouldn’t introduce consensus dependencies on.

My proposal would be to copy the definition of c++17 optional into https://github.com/bitcoin/bitcoin/blob/99813a9745fe10a58bedd7a4cb721faf14f907a4/src/optional.h and drop the boost dependency, and then use this here. This can be done as a PR separate from Taproot so as not to further burden this PR.

Here, optionals express both the nothing set and not initialized state (hence dual-wrapped options) but perhaps we’d be OK in collapsing the wrapped ones to represent (not initialized or not set) OR value.

0 struct ScriptExecutionData
1 {
2     //! The tapleaf hash.
3     Option<uint256> m_tapleaf_hash;
4     Option<Option<uint32_t>> m_codeseparator_pos;
5     //! Hash of the annex data, if any
6     Option<Option<uint256>> m_annex_hash;
7     /** How much validation weight is left (decremented for every successful signature check). */
8     Option<int64_t> m_validation_weight_left;
9 };

This would seem, to me, to make the interface quite a bit safer and eliminates a bunch of initialization logic & prevents UB from cropping up.

It would also be, in my opinion, a larger project (perhaps worthwhile) to generally rethink this state object to be accessed through an interface that guarantees the fields are accessed correctly – e.g., once a m_validation_weight_left is set it can only be read or decreased, and the function to decrease can set error if the condition isn’t met on underflow. Maybe not worth that large of a refactor though, I think optionals would already be an improvement.

sipa commented at 7:13 pm on January 25, 2020:

I agree to an extent that all the _init variables are ugly, but I don’t think that they’re that bad if you see them as just runtime checks for invalid code. The same can be accomplished without them using ubsan/valgrind, in many cases.

About using Option… It’s arguably the right tool for the job, but there is no singular “definition of c++17 optional”; there is the libstdc++ implementation, and the libc++ one, both of which may be relying on platform specific extensions (I haven’t checked). Even ignoring that, the libstdc++ one is 1500 lines of code, which I think is really overkill for what we’d get. Since the Boost one can’t be used in libconsensus, I think the current code is not too bad.

StEvUgnIn commented at 7:07 am on January 27, 2020:

I examined libstdc++ implementation for RISC-V architechture and it seems portable and independent from any physical architecture https://github.com/riscv/riscv-gcc/commits/riscv-gcc-8.3.0/libstdc%2B%2B-v3

sipa commented at 6:37 pm on January 27, 2020:

@StEvUgnIn We can’t just copy GPL code, unfortunately. Using libc++’s version may be an option, but it still seems overkill to me (it also contains lots of libc++ specific macros, that may require additional files to be included).

elichai commented at 5:01 pm on January 30, 2020:

@JeremyRubin Don’t forget that the std namespace get special treatment from the compiler. so copying code from libstd without checking it might actually contain implementation defined behavior that won’t necessarily work correctly with a different compiler(or even just by being outside of the std namespace).

sipa commented at 5:39 pm on March 21, 2020:

This seems to be more of a potential improvement for later.

in src/secp256k1/src/secp256k1.c:440 in b8048b8148 outdated

435+
436+    if (counter != 0) {
437+        return 0;
438+    }
439+    /* Tag the hash with algo16 which is important to avoid nonce reuse across
440+     * algorithms. If the this nonce function is used in BIP-schnorr signing as

constcast-glitch commented at 9:14 pm on January 26, 2020:

I believe “If the this nonce function …” should be “If this nonce function …”.

gmaxwell commented at 9:30 pm on January 26, 2020:

Can you repeat this comment here: https://github.com/bitcoin-core/secp256k1/pull/558 ?

constcast-glitch commented at 9:37 pm on January 26, 2020:

Done

in src/pubkey.h:220 in b8048b8148 outdated

212+
213+    /** Verify a 64-byte Schnorr signature.
214+     *
215+     * If the signature is not 64 bytes, or the public key is not fully valid, false is returned.
216+     */
217+    bool VerifySchnorr(const uint256& hash, const std::vector<unsigned char>& vchSig) const;

kallewoof commented at 6:07 am on January 27, 2020:

It would be nice if there was an IsValid() function to check if the pubkey is actually valid, as opposed to the signature being invalid.

sipa commented at 6:27 am on January 27, 2020:

There should be no need.

Public keys as specified by BIP340 are 32-byte arrays, not points or X coordinates or whatever. The signature validation algorithm takes as input a 32-byte public key, and 64-byte signature, and a 32-byte message.

This is intentionally different from how ECDSA works, where differences between encoding errors and invalid signatures are significant, and arguably the cause of all the trouble we went through with ECDSA encodings, and BIP66…

So, to be clear: there should never be a behavior difference between an invalid signature and invalidity due to invalid public keys. Both are just inputs for which the verification returns false. Having a way to distinguish the two would be a risk.

StEvUgnIn commented at 6:44 am on January 27, 2020:

It would be nice if there was an IsValid() function to check if the pubkey is actually valid, as opposed to the signature being invalid.

 0class XOnlyPubKey {
 1private:
 2    uint256 m_keydata;
 3
 4public:
 5    XOnlyPubKey(const uint256& in) : m_keydata(in) {}
 6
 7    /** Verify a 64-byte Schnorr signature.
 8     *
 9     * If the signature is not 64 bytes, or the public key is not fully valid, false is returned.
10     */
11    bool VerifySchnorr(const uint256& hash, const std::vector<unsigned char>& vchSig) const;
12    bool CheckPayToContract(const XOnlyPubKey& base, const uint256& hash, bool sign) const;
13
14    const unsigned char& operator[](int pos) const { return *(m_keydata.begin() + pos); }
15    const unsigned char* data() const { return m_keydata.begin(); }
16    size_t size() const { return 32; }
17};

This on-line instruction is already doing the job XOnlyPubKey(const uint256& in) : m_keydata(in) {}

kallewoof commented at 7:25 am on January 27, 2020:

@sipa It is not useful to be able to distinguish between an invalid pubkey and an invalid signature? I don’t understand the reasoning there. Indeed it should be helpful to be able to tell a user which part they fat fingered, if any.

kallewoof commented at 7:27 am on January 27, 2020:

@StEvUgnIn No, I am talking about the call to secp256k1_xonly_pubkey_parse failing.

sipa commented at 7:29 am on January 27, 2020:

Sure, for users it may be useful to have a sanity check. But consensus code should never distinguish between invalid public key and invalid signature.

StEvUgnIn commented at 7:51 am on January 31, 2020:

@kallewoof OK

sipa commented at 5:43 pm on March 21, 2020:

@kallewoof So, I suggest that maybe we add a way to test if a pubkey is valid later when wallet support is added. But as the current PR is solely consensus/validation code, I think it’s simpler and safer to not expose that distinction for now.

in src/script/interpreter.cpp:1451 in b8048b8148 outdated

1451+        break;
1452+    default:
1453+        assert(false);
1454+    }
1455+    assert(in_pos < tx_to.vin.size());
1456+    assert(cache.ready && cache.m_amounts_spent_ready);

kallewoof commented at 7:40 am on January 28, 2020:

This assertion will be hit, because cache is null when using the below constructor:

https://github.com/bitcoin/bitcoin/blob/b8048b814821913b1f4c1c2070ec68b0c9001ec8/src/script/interpreter.h#L258

Maybe checking if txdata is non-null and complain if it isn’t, at

https://github.com/bitcoin/bitcoin/blob/b8048b814821913b1f4c1c2070ec68b0c9001ec8/src/script/interpreter.cpp#L1638

sipa commented at 8:12 am on January 28, 2020:

Well yes it would assert because that would be invalid. It seems it’s just doing its job?

kallewoof commented at 8:21 am on January 28, 2020:

I’m not arguing against the assert, I’m saying that we should catch ‘cache is null’ before this point.

kallewoof commented at 8:33 am on January 28, 2020:

Because it’s misleading and confusing. The assert is not triggering for the right reasons (I don’t even think it’s triggering at all, though tbh I’m not sure how C++ deals with being passed a null value for a referenced non-reference like this).

It’s checking whether the cache is ready, but in reality the cache is null. This method does not even take a ref to begin with. The one place it’s called is L1638, which could just do an assert(txdata) before calling SignatureHashSchnorr.

sipa commented at 8:33 am on January 28, 2020:

I don’t think that helps. If you reach this point without the cache initialized, you’re using the code incorrectly.

What is perhaps not clear is that this is not just a cache - we can’t recompute data in it if it missing based on other sources. We rely on it to pass in essential information about the spending that cannot be retrieved otherwise.

sipa commented at 8:36 am on January 28, 2020:

Oh, you’re talking about null vs uninitialized. I’ll investigate tomorrow. Dereferencing or invoking a member function of a null pointer is UB; if that can happen we should indeed catch it earlier. I can’t check the code right now.

kallewoof commented at 8:44 am on January 28, 2020:

Hm.. for v0 this is actually accomodated for

0        const bool cacheready = cache && cache->ready;

whereas for v1 this is mandatory. I still think it’s unnecessarily unhelpful, and a bit scary to have non-ref null values in code paths (even if as you say this is a hint of a bigger problem).

sipa commented at 8:47 am on January 28, 2020:

What do “non-ref null values” mean?

A reference to nullptr is illegal, always. Only pointers can be nullptr.

kallewoof commented at 8:58 am on January 28, 2020:

In SignatureHashSchnorr, the last parameter, defined as const PrecomputedTransactionData& cache, is 0x0000000000000000 for the case where *this->txdata == nullptr above. This may be using the code incorrectly, but it seems worth catching before that call above.

sipa commented at 6:57 pm on March 21, 2020:

Nice catch, I finally looked into this, and I agree this is too fragile. I’ve changed SignatureHashSchnorr to take a pointer to a PrecomputedTramsactionData instead, and assert fail when it’s null.

in src/script/interpreter.cpp:1401 in b8048b8148 outdated

1398-PrecomputedTransactionData::PrecomputedTransactionData(const T& txTo)
1399+void PrecomputedTransactionData::Init(const T& txTo, std::vector<CTxOut> spent_outputs)
1400 {
1401+    m_spent_outputs = std::move(spent_outputs);
1402+
1403+    if (ready) return;

kallewoof commented at 8:07 am on January 28, 2020:

If someone does txdata = PrecomputedTransactionData(tx); and then later tries to do txdata.Init(tx, spent_outputs); this line will terminate, despite m_amounts_spent_ready not being updated based on the new spent_outputs. Perhaps

0if (ready && spent_outputs.empty()) return;

Edit: maybe even split into if !ready, make hashes and if !m_amounts_spend_ready, do spent stuff. (also fixed description; m_spent_outputs is updated, but the bool is not)

sipa commented at 6:58 pm on March 21, 2020:

Done. I’ve rewritten this to effectively treat ready as referring to the pre-taproot stuff and m_amounts_spend_ready for the rest.

in src/script/interpreter.h:216 in b8048b8148 outdated

213 
214 template <class T>
215 uint256 SignatureHash(const CScript& scriptCode, const T& txTo, unsigned int nIn, int nHashType, const CAmount& amount, SigVersion sigversion, const PrecomputedTransactionData* cache = nullptr);
216 
217+template <class T>
218+bool SignatureHashTap(uint256& hash_out, const ScriptExecutionData& execdata, const T& tx_to, unsigned int in_pos, uint8_t hash_type, SigVersion sigversion, const PrecomputedTransactionData& cache);

kallewoof commented at 5:57 am on January 30, 2020:

I believe this should be called SignatureHashSchnorr and be <typename T> to match interpreter.cpp v.

sipa commented at 6:57 pm on March 21, 2020:

It’s not called anywhere externally, so I’ve just dropped it from the header file.

in src/policy/policy.cpp:236 in b8048b8148 outdated

230@@ -231,6 +231,30 @@ bool IsWitnessStandard(const CTransaction& tx, const CCoinsViewCache& mapInputs)
231                     return false;
232             }
233         }
234+
235+        // Check P2TR standard limits
236+        if (witnessversion == 1 && witnessprogram.size() == WITNESS_V1_TAPROOT_SIZE && !prevScript.IsPayToScriptHash()) {

pinheadmz commented at 1:19 pm on February 26, 2020:

Is the P2SH check necessary here? There is a test for prevScript.IsWitnessProgram() a few lines up, is there anyway the script could still be P2SH at this point? Or should this actually test prev.scriptPubKey.IsPayToScriptHash() which is the actual previous TX output script, defined before prevScript is updated to the redeem script.

sipa commented at 7:00 pm on March 21, 2020:

@pinheadmz Good point, this is wrong; it’s supposed to test prev.scriptPubKey instead of prevScript. I’ve changed it to keep track of p2sh-ness above, and then test that instead.

in src/script/interpreter.cpp:1820 in b8048b8148 outdated

1826 
1827-    // Disallow stack item size > MAX_SCRIPT_ELEMENT_SIZE in witness stack
1828-    for (unsigned int i = 0; i < stack.size(); i++) {
1829-        if (stack.at(i).size() > MAX_SCRIPT_ELEMENT_SIZE)
1830-            return set_error(serror, SCRIPT_ERR_PUSH_SIZE);
1831+    if (witversion == 1 && program.size() == TAPROOT_PROGRAM_SIZE && !is_p2sh) {

jnewbery commented at 9:44 pm on March 9, 2020:

Adding the !is_p2sh here means that any transaction input spending a P2SH-wrapped segwit v1 output will be valid, but will fail standardness withSCRIPT_ERR_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM (“Witness version reserved for soft-fork upgrades”) which seems like the wrong error message. We’re not expecting P2SH-wrapped segwit v1 outputs to reinterpreted by a future soft-fork, we’re simply leaving them unencumbered for safety reasons. I think for correctness we should return a new error type in that case.

sipa commented at 7:01 pm on March 21, 2020:

Maybe we can just change the error message to also encompass things that we don’t expect will ever be used? (for example, we don’t expect witness programs with size below 32 - and certainly not ones with size below 20 - to be used, but they’re still available for future extensions)

laanwj referenced this in commit e5cb0dffd5 on Mar 13, 2020

DrahtBot added the label Needs rebase on Mar 13, 2020

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

jnewbery commented at 9:18 pm on March 17, 2020: member

I’ve rebased this on master, and taken the most recent version of https://github.com/bitcoin-core/secp256k1/pull/558 (which I’ve saved at https://github.com/jnewbery/secp256k1/tree/819c3a6c1 since the PR will have commits squashed and further small changes made). The rebased branch is at https://github.com/jnewbery/bitcoin/tree/pr17977.1. Changes:

O(1) OP_IF/NOTIF/ELSE/ENDIF script implementation and Abstract out script execution out of VerifyWitnessProgram() have both been merged into master (#16902 and #18002) so are no longer part of this PR.
The interface to secp256k1_xonly_pubkey_tweak_test has been changed to take the 32 bytes serialized output pubkey.
32 bytes pubkeys are now implicit even y, not implicit square y
tagged hashes have changed

I haven’t implemented the synthetic nonce/auxiliary randomness from https://github.com/bitcoin/bips/pull/893 in the test code. That could be done separately (but there’s nothing to be done in bitcoind for this - it’d be more as demonstration code in the test framework).

The [MOVEONLY] Move single-sig checking EvalScript code to EvalChecksig and [REFACTOR] Initialize PrecomputedTransactionData in CheckInputs commits could be sliced off into their own PRs. There’s not any benefit from those changes outside Taproot, but if people think it’d be useful to reduce the size of this PR, I’m happy to open and maintain those PRs.

sipa force-pushed on Mar 18, 2020

sipa commented at 5:43 am on March 18, 2020: member

Rebased, and included @jnewbery’s changes from above.

Here is what I did:

I created a rebase myself (with the old libsecp256k1, and old square pubkey rule).
Compared the final tree with John’s version, allowing me to review the even-pubkey changes; everything looked correct, but I saw a few minor improvements.
I switched to John’s version, apart from this patch:

 0diff --git a/src/pubkey.cpp b/src/pubkey.cpp
 1index 246c19a8f8..2231a4ee71 100644
 2--- a/src/pubkey.cpp
 3+++ b/src/pubkey.cpp
 4@@ -178,9 +178,8 @@ bool XOnlyPubKey::VerifySchnorr(const uint256 &hash, const std::vector<unsigned
 5 
 6 bool XOnlyPubKey::CheckPayToContract(const XOnlyPubKey& base, const uint256& hash, bool negated) const
 7 {
 8-    secp256k1_xonly_pubkey base_point, output_point;
 9+    secp256k1_xonly_pubkey base_point;
10     if (!secp256k1_xonly_pubkey_parse(secp256k1_context_verify, &base_point, base.data())) return false;
11-    if (!secp256k1_xonly_pubkey_parse(secp256k1_context_verify, &output_point, m_keydata.begin())) return false;
12     return secp256k1_xonly_pubkey_tweak_test(secp256k1_context_verify, m_keydata.begin(), negated, &base_point, hash.begin());
13 }
14 
15diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
16index 12ad6e7236..c3dd00de43 100644
17--- a/src/script/interpreter.cpp
18+++ b/src/script/interpreter.cpp
19@@ -1812,7 +1812,6 @@ static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion,
20         } else {
21             return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_WRONG_LENGTH);
22         }
23-        assert(false); // Unreachable code
24     } else if (witversion == 1 && program.size() == TAPROOT_PROGRAM_SIZE && !is_p2sh) {
25         if (!(flags & SCRIPT_VERIFY_TAPROOT)) return set_success(serror);
26         auto stack = witness.stack;
27@@ -1857,7 +1856,6 @@ static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion,
28             }
29             return set_success(serror);
30         }
31-        assert(false); // Unreachable code
32     } else {
33         if (flags & SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM) {
34             return set_error(serror, SCRIPT_ERR_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM);

Also added a commit 61bdc448dffdc41ef03cb775bfb67e0dac1dca09, after noticing that an unnecessary stack copy was being made in VerifyWitnessProgram.
Pushed to the PR branch, and noticed that a new rebase was necessary.
Did another rebase.
Noticed the tests were failing, due to a bug introduced in #17319; fixed in 1d293165551dbc6403dba59c2e5a896c5ae5366e (submitted separately as #18374).

DrahtBot removed the label Needs rebase on Mar 18, 2020

sipa force-pushed on Mar 18, 2020

sipa force-pushed on Mar 19, 2020

sipa force-pushed on Mar 20, 2020

sipa force-pushed on Mar 21, 2020

in src/hash.cpp:9 in 7641c52162 outdated

5@@ -6,6 +6,7 @@
6 #include <crypto/common.h>
7 #include <crypto/hmac_sha512.h>
8 
9+#include <string>

Empact commented at 9:55 pm on March 21, 2020:

nit: I’m not 100% clear on ourinclude guidelines - string is included via hash.h, so if that’s sufficient this line is unnecessary, if that’s not sufficient, then we should also include uint256.h, etc here.

kallewoof commented at 11:36 pm on March 21, 2020:

Guidelines say to include what you use, so including seems correct to me.

sipa force-pushed on Mar 21, 2020

sipa force-pushed on Mar 22, 2020

in src/script/interpreter.cpp:1833 in 98ad33ac24 outdated

1837+            execdata.m_annex_present = false;
1838+        }
1839+        execdata.m_annex_init = true;
1840+        if (stack.size() == 1) {
1841+            // Key path spending (stack size is 1 after removing optional annex)
1842+            if (!checker.CheckSigSchnorr(stack[0], program, SigVersion::TAPROOT, execdata)) {

jnewbery commented at 7:12 pm on March 24, 2020:

should stack.front() be preferred over stack[0]?

sipa commented at 8:30 pm on March 26, 2020:

Done.

sipa force-pushed on Mar 26, 2020

sipa commented at 8:31 pm on March 26, 2020: member

Rebased on top of #18388, #18422, and #18401, and addressed a number of comments.

sipa force-pushed on Mar 26, 2020

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

DrahtBot added the label Needs rebase on Mar 27, 2020

sipa force-pushed on Mar 27, 2020

sipa commented at 8:48 pm on March 27, 2020: member

Rebased now that #18388 (Span stack) is merged.

DrahtBot removed the label Needs rebase on Mar 27, 2020

in src/script/interpreter.h:193 in b1e76bda23 outdated

183+    bool m_codeseparator_pos_init = false;
184+    //! Opcode position of the last executed OP_CODESEPARATOR (or 0xFFFFFFFF if none executed).
185+    uint32_t m_codeseparator_pos;
186+
187+    //! Whether m_annex_present and m_annex_hash are initialized.
188+    bool m_annex_init = false;

jnewbery commented at 4:24 pm on March 28, 2020:

nit: could these two bools be replaced with an Optional<bool>? Optional is std from c++17 but currently implemented using boost::optional. Do we prefer to keep that out of consensus code?

sipa commented at 6:37 pm on March 28, 2020:

We can’t use boost in libconsensus (well we could if we add a dependency mess to it, but I suspect we rather not). There was an earlier discussion in this PR about this, including the option of including a simple native Optional type definition. I think this is overkill, and this approach is fine for now - we can switch to std::optional once it’s available.

instagibbs commented at 8:48 pm on July 14, 2020:

Would be nice when time comes.

in src/script/interpreter.h:206 in b1e76bda23 outdated

203+static constexpr size_t WITNESS_V1_TAPROOT_SIZE = 32;
204+
205+
206+static constexpr uint8_t TAPROOT_LEAF_MASK = 0xfe;
207+static constexpr uint8_t TAPROOT_LEAF_TAPSCRIPT = 0xc0;
208+static constexpr size_t TAPROOT_PROGRAM_SIZE = 32;

jnewbery commented at 4:46 pm on March 28, 2020:

Is this just a duplicate of WITNESS_V1_TAPROOT_SIZE? It’s only used once in VerifyWitnessProgram(). Can we replace that usage with WITNESS_V1_TAPROOT_SIZE?

sipa commented at 6:38 pm on March 28, 2020:

The constants happen to be identical, but there is no a-priori reason why they would be (if you wouldn’t know the BIP, say). They’re separate concepts, so merging the constants would IMO defeat the purpose of having a named constant in the first place.

jnewbery commented at 8:54 pm on March 28, 2020:

I’m confused by what the difference is.

In policy.cpp:

0        if (witnessversion == 1 && witnessprogram.size() == WITNESS_V1_TAPROOT_SIZE && !p2sh) {

In interpreter.cpp:

0    } else if (witversion == 1 && program.size() == TAPROOT_PROGRAM_SIZE && !is_p2sh) {

Are those not comparing the same data to the same constant, just with different constant names?

(those functions use the same constant names for segwit V0 scripthash program sizes:

0        if (program.size() == WITNESS_V0_SCRIPTHASH_SIZE) {

and

0        if (witnessversion == 0 && witnessprogram.size() == WITNESS_V0_SCRIPTHASH_SIZE) {

)

sipa commented at 9:12 pm on March 28, 2020:

Oh, of course! Sorry, I misread; thinking that one was the constant for (v0) P2WSH. Will merge them into one.

sipa commented at 10:26 pm on March 28, 2020:

Done.

sipa force-pushed on Mar 28, 2020

sipa commented at 10:27 pm on March 28, 2020: member

Made another change: the policy-checking code now also uses Span stacks.

MarcoFalke referenced this in commit a9213bbe75 on Apr 10, 2020

DrahtBot added the label Needs rebase on Apr 10, 2020

jnewbery commented at 8:30 pm on April 10, 2020: member

Don’t rebase yet. I hope to get #18401 merged soon.

in src/script/interpreter.h:147 in e83b1772d0 outdated

142 
143 bool CheckSignatureEncoding(const std::vector<unsigned char> &vchSig, unsigned int flags, ScriptError* serror);
144 
145 struct PrecomputedTransactionData
146 {
147+    //! Single-SHA256 versions

michaelfolkson commented at 11:23 am on April 11, 2020:

Optional nit (feel free to ignore): Refer to the BIP (341) explaining why single hashes are added. https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#cite_note-15

sidhujag referenced this in commit 042234f7f3 on Apr 13, 2020

MarcoFalke referenced this in commit e16718a8b3 on Apr 16, 2020

sidhujag referenced this in commit 8e77630a77 on Apr 16, 2020

jnewbery commented at 7:19 pm on April 16, 2020: member

I’ve rebased this branch on master here: https://github.com/jnewbery/bitcoin/tree/pr17977.2 (using the same libsecp commit).

This did require one additional commit https://github.com/jnewbery/bitcoin/commit/df38ebef99229a29c16cda571ded4a3613ead743 due to the new assert added in PrecomputedTransactionData::Init(). I’ll PR that separately.

MarcoFalke referenced this in commit a998c5185b on Apr 19, 2020

jnewbery commented at 3:21 pm on April 19, 2020: member

I’ve rebased on master again now that https://github.com/jnewbery/bitcoin/commit/df38ebef99229a29c16cda571ded4a3613ead743 is merged. Here: https://github.com/jnewbery/bitcoin/tree/pr17977.3

sipa force-pushed on Apr 19, 2020

sipa commented at 9:34 pm on April 19, 2020: member

@jnewbery Did the rebase myself, and ended up with an almost identical tree as yours. Yours was slightly cleaner, so I used that one, rebased it on a new secp256k1 subtree merge, and pushed it.

DrahtBot removed the label Needs rebase on Apr 19, 2020

sidhujag referenced this in commit 729d3bbcee on Apr 20, 2020

JeremyRubin commented at 7:14 pm on April 21, 2020: contributor

BTW if willing #18071 plucks out some of the changes from taproot & should be a relatively easy rebase. A couple symbol names are changed for clarity as the crypto return value has changed from the double hash to the single.

DrahtBot added the label Needs rebase on Apr 27, 2020

sipa force-pushed on May 2, 2020

sipa commented at 9:19 pm on May 2, 2020: member

Rebased, updated libsecp256k1 branch, and converted the Schnorr framework test to a Python unittest (see #18576).

DrahtBot removed the label Needs rebase on May 2, 2020

in test/functional/test_framework/address.py:10 in c547a9683b outdated

 5@@ -6,6 +6,7 @@
 6 
 7 import enum
 8 
 9+from .base58 import byte_to_base58
10 from .script import hash256, hash160, sha256, CScript, OP_0

MarcoFalke commented at 10:58 pm on May 2, 2020:

0test/functional/test_framework/address.py:10:1: F401 '.script.hash256' imported but unused

sipa commented at 7:34 am on May 6, 2020:

Fixed.

sipa force-pushed on May 6, 2020

fanquake commented at 8:40 am on May 22, 2020: member

@sipa IIUC, the secp256k1 changes here are currently updating our subtree to upstream @ https://github.com/bitcoin-core/secp256k1/commit/e9fccd4de1f2b382545dfbadeae54868447e2cdf; with https://github.com/bitcoin-core/secp256k1/pull/558 on top.

Given there’s been another push to https://github.com/bitcoin-core/secp256k1/pull/558, as well as additional merges to secp256k1 master, and, it’s now been more than a year since we last updated our subtree, could you pull the secp256k1 subtree update out of here, and PR it separately? Then we’d have less change here, and what’s left would just be Schnorr related (#558). It’s also a good time as we are early in the 0.21 cycle.

sipa force-pushed on May 22, 2020

sipa commented at 8:17 pm on May 22, 2020: member

Rebased to include the new bitcoin-core/secp256k1#558. @fanquake Will do, as soon as a few recent improvements are merged in the secp256k1 repository.

sipa force-pushed on May 22, 2020

sipa force-pushed on May 23, 2020

sipa commented at 0:14 am on May 23, 2020: member

Updated now to include the changes in https://github.com/bitcoin/bips/pull/920.

Viral approved

DrahtBot added the label Needs rebase on May 30, 2020

sipa commented at 0:49 am on June 10, 2020: member

Rebased on top of #19228

sipa force-pushed on Jun 10, 2020

fanquake removed the label Needs rebase on Jun 10, 2020

ComputerCraftr referenced this in commit a600f3b1f9 on Jun 10, 2020

MarcoFalke referenced this in commit 6762a627ec on Jun 10, 2020

DrahtBot added the label Needs rebase on Jun 10, 2020

sidhujag referenced this in commit 13869fcaee on Jun 10, 2020

MarcoFalke referenced this in commit 85f7db2284 on Jun 11, 2020

sidhujag referenced this in commit b195ad9d5c on Jun 11, 2020

sipa force-pushed on Jun 18, 2020

sipa commented at 4:27 pm on June 18, 2020: member

Rebased after merge of #19228 and #18468.

Viral approved

DrahtBot removed the label Needs rebase on Jun 18, 2020

sipa force-pushed on Jun 20, 2020

in src/script/interpreter.cpp:1900 in a9f418aeb0 outdated

1721+                return set_error(serror, SCRIPT_ERR_TAPROOT_WRONG_CONTROL_SIZE);
1722+            }
1723+            if (!VerifyTaprootCommitment(control, program, scriptPubKey)) {
1724+                return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH);
1725+            }
1726+            if (flags & SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_TAPROOT_VERSION) {

theuni commented at 4:45 pm on July 1, 2020:

Any reason not to put the cheap policy check before VerifyTaprootCommitment() ?

JeremyRubin commented at 7:19 pm on July 16, 2020:

Also perhaps this is checked elsewhere by the logic that sets this SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_TAPROOT_VERSION flag, but don’t we need to check the flag version is not currently defined here?

JeremyRubin commented at 7:22 pm on July 16, 2020:

Ah I think @theuni commented from an earlier commit, so it wasn’t showing that a version is defined.

sipa commented at 8:16 pm on July 19, 2020:

@theuni I think it’s preferable to do checks for consensus-invalidity first, so that the error code you get is more consistent. As it isn’t inherently more expensive for an attacker to create a policy-invalid spend instead of one that just has an invalid signature say, I don’t think it matters for DoS resistance either. @JeremyRubin I have no idea what you’re trying to say.

JeremyRubin commented at 8:41 pm on July 19, 2020:

@theuni comment shows up on this line, which is later amended to

So I was simply confused from the tagged snippet as to why it did not check the taproot leaf version.

But the reason is because @theuni dropped his comment on an earlier commit, and github didn’t tag it as outdated.

sipa commented at 8:53 pm on July 19, 2020:

Ah, I see. That also explains why it may look like these two could easily be swapped @theuni - it’s only in a later commit that something is added in between them (and the order matters).

JeremyRubin commented at 9:09 pm on July 19, 2020:

I think in theory @theuni’s point stands, we could add a cheap check ahead of verifytaprootcommitment that checks and aborts if it’s an unknown leaf version, but yes the final state makes more sense as is.

in src/hash.cpp:94 in 146952354b outdated

86@@ -87,3 +87,10 @@ CHashWriter TaggedHash(const std::string& tag)
87     writer << taghash << taghash;
88     return writer;
89 }
90+
91+uint256 SHA256Uint256(const uint256& hash)
92+{
93+    uint256 result;
94+    CSHA256().Write(hash.begin(), 32).Finalize(result.begin());

instagibbs commented at 7:57 pm on July 14, 2020:

s/32/hash.size()/ if you don’t mind

sipa commented at 9:15 pm on July 19, 2020:

Done.

in src/script/interpreter.cpp:1417 in 146952354b outdated

1324+        hashPrevouts = SHA256Uint256(m_prevouts_hash);
1325+        m_sequences_hash = GetSequenceHash(txTo);
1326+        hashSequence = SHA256Uint256(m_sequences_hash);
1327+        m_outputs_hash = GetOutputsHash(txTo);
1328+        hashOutputs = SHA256Uint256(m_outputs_hash);
1329+        if (!m_spent_outputs.empty()) {

instagibbs commented at 8:02 pm on July 14, 2020:

Is this ever expected to not hit?

Sjors commented at 4:06 pm on July 16, 2020:

Afaik no, because CheckInputScripts returns early for coinbase transactions. An assert here would make more sense

sipa commented at 8:23 pm on July 19, 2020:

I believe this is fine right now, but if this code ends up being reused in signing logic, it will actually be empty in cases where not all spent outputs are known (e.g. legacy signing through some RPCs).

in src/script/interpreter.cpp:1420 in 146952354b outdated

1327+        m_outputs_hash = GetOutputsHash(txTo);
1328+        hashOutputs = SHA256Uint256(m_outputs_hash);
1329+        if (!m_spent_outputs.empty()) {
1330+            m_spent_amounts_hash = GetSpentAmountsHash(m_spent_outputs);
1331+            m_spent_scripts_hash = GetSpentScriptsHash(m_spent_outputs);
1332+            m_spent_outputs_ready = true;

instagibbs commented at 8:03 pm on July 14, 2020:

Is this for simply catching assertion condition?

sipa commented at 8:24 pm on July 19, 2020:

Yes. It’s an alternative to using optional here (which would otherwise pull in boost stuff into libconsensus, unless we wait for c++17).

in src/pubkey.h:220 in 05b00d5eab outdated

215+     * If the signature is not 64 bytes, or the public key is not fully valid, false is returned.
216+     */
217+    bool VerifySchnorr(const uint256& hash, const std::vector<unsigned char>& vchSig) const;
218+
219+    const unsigned char& operator[](int pos) const { return *(m_keydata.begin() + pos); }
220+    size_t size() const { return 32; }

instagibbs commented at 8:08 pm on July 14, 2020:

s/32/m_keydata.size()/

sipa commented at 9:15 pm on July 19, 2020:

Done.

in src/script/interpreter.cpp:1781 in a9f418aeb0 outdated

1777@@ -1724,7 +1778,7 @@ bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const C
1778                 // The scriptSig must be _exactly_ CScript(), otherwise we reintroduce malleability.
1779                 return set_error(serror, SCRIPT_ERR_WITNESS_MALLEATED);
1780             }
1781-            if (!VerifyWitnessProgram(*witness, witnessversion, witnessprogram, flags, checker, serror)) {
1782+            if (!VerifyWitnessProgram(*witness, witnessversion, witnessprogram, flags, checker, serror, false)) {

instagibbs commented at 8:28 pm on July 14, 2020:

please annotate /* is_p2sh */

sipa commented at 9:15 pm on July 19, 2020:

Done.

in src/script/interpreter.cpp:1826 in a9f418aeb0 outdated

1822@@ -1769,7 +1823,7 @@ bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const C
1823                     // reintroduce malleability.
1824                     return set_error(serror, SCRIPT_ERR_WITNESS_MALLEATED_P2SH);
1825                 }
1826-                if (!VerifyWitnessProgram(*witness, witnessversion, witnessprogram, flags, checker, serror)) {
1827+                if (!VerifyWitnessProgram(*witness, witnessversion, witnessprogram, flags, checker, serror, true)) {

instagibbs commented at 8:28 pm on July 14, 2020:

please annotate /* is_p2sh */

sipa commented at 9:15 pm on July 19, 2020:

Done.

in src/script/script_error.cpp:101 in a9f418aeb0 outdated

94@@ -91,6 +95,10 @@ std::string ScriptErrorString(const ScriptError serror)
95             return "Witness provided for non-witness script";
96         case SCRIPT_ERR_WITNESS_PUBKEYTYPE:
97             return "Using non-compressed keys in segwit";
98+        case SCRIPT_ERR_TAPROOT_INVALID_SIG:
99+            return "Invalid signature for Taproot key path spending";

instagibbs commented at 8:33 pm on July 14, 2020:

Could mention the key could be busted too.

sipa commented at 8:30 pm on July 19, 2020:

Do you have a suggested string?

in src/script/interpreter.cpp:1396 in da73c5e3eb outdated

1390@@ -1391,9 +1391,9 @@ bool SignatureHashSchnorr(uint256& hash_out, const T& tx_to, const uint32_t in_p
1391     }
1392 
1393     // Data about the input/prevout being spent
1394-    const auto* witstack = &tx_to.vin[in_pos].scriptWitness.stack;
1395-    bool have_annex = witstack->size() > 1 && witstack->back().size() > 0 && witstack->back()[0] == 0xff;
1396-    const uint8_t spend_type = (ext_flag << 1) + (have_annex ? 1 : 0); // The low bit indicates whether an annex is present.
1397+    assert(execdata.m_annex_init);
1398+    bool have_annex = execdata.m_annex_present;
1399+    uint8_t spend_type = (ext_flag << 1) + (have_annex ? 1 : 0); // The low bit indicates whether an annex is present.

instagibbs commented at 8:45 pm on July 14, 2020:

did I miss why the const is dropped here?

sipa commented at 9:15 pm on July 19, 2020:

Nope, fixed.

in src/script/interpreter.cpp:376 in 7cdc010c70 outdated

367@@ -371,6 +368,67 @@ static bool EvalChecksig(const valtype& vchSig, const valtype& vchPubKey, CScrip
368     return true;
369 }
370 
371+static bool EvalChecksigTapscript(const valtype& sig, const valtype& pubkey, ScriptExecutionData& execdata, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* serror, bool& success)
372+{
373+    assert(sigversion == SigVersion::TAPSCRIPT);
374+
375+    /*
376+     *  The following validation sequence is consensus critical. Please note how --

instagibbs commented at 8:52 pm on July 14, 2020:

The following validation sequence is consensus critical.

You don’t say

sipa commented at 9:16 pm on July 19, 2020:

I know, right?

Sjors commented at 5:22 pm on July 24, 2020:

Perhaps the comment can be expanded to clarify how success is used by the caller:

0If script execution doesn't trigger an error, success is added to the stack.
1OP_CHECKSIGVERIFY immediately fails if success is false, whereas with
2OP_CHECKSIG(_ADD) it's up to the rest of the script to
3decide what to do with the signature result, typically based on the number
4of non-empty signatures.

Renaming success to did_sign makes its purpose more clear (but we’re kinda stuck with this variable name).

in src/script/interpreter.cpp:1111 in 7cdc010c70 outdated

1105+
1106+                    // (sig num pubkey -- num)
1107+                    if (stack.size() < 3) return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
1108+
1109+                    const valtype& sig = stacktop(-3);
1110+                    const CScriptNum num(stacktop(-2), fRequireMinimal);

instagibbs commented at 9:16 pm on July 14, 2020:

N.B.: Let’s make sure there’s a test that catches the >4 bytes rule for addition

sipa commented at 9:16 pm on July 19, 2020:

Good idea.

instagibbs commented at 1:24 am on July 20, 2020:

I ended up writing that test, in the branch I posted.

sipa commented at 6:13 pm on August 7, 2020:

Marking as resolved.

in src/script/interpreter.cpp:475 in 7cdc010c70 outdated

472@@ -408,9 +473,12 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript&
473             if (vchPushValue.size() > MAX_SCRIPT_ELEMENT_SIZE)
474                 return set_error(serror, SCRIPT_ERR_PUSH_SIZE);
475 
476-            // Note how OP_RESERVED does not count towards the opcode limit.
477-            if (opcode > OP_16 && ++nOpCount > MAX_OPS_PER_SCRIPT)
478-                return set_error(serror, SCRIPT_ERR_OP_COUNT);
479+            if (sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0) {

instagibbs commented at 9:28 pm on July 14, 2020:

The various peppering of sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0 and sigversion != SigVersion::TAPSCRIPT makes me a little uneasy. Synchronize these checks?

sipa commented at 9:16 pm on July 19, 2020:

There was only one sigversion != SigVersion::TAPSCRIPT so I’ve changed that to the other one.

in src/script/interpreter.cpp:1743 in 7cdc010c70 outdated

1739@@ -1634,6 +1740,25 @@ static bool ExecuteWitnessScript(const Span<const valtype>& stack_span, const CS
1740 {
1741     std::vector<valtype> stack{stack_span.begin(), stack_span.end()};
1742 
1743+    // OP_SUCCESSx processing overrides everything, including stack element size limits

instagibbs commented at 1:16 pm on July 15, 2020:

this would be easy/nice to split out for unit tests

sipa commented at 8:48 pm on July 19, 2020:

This is a bit annoying, as this loop has multiple distinct return branches, and it returning success can mean either continue execution or not.

Happy to take some code if you have a suggestion, though.

instagibbs commented at 1:08 am on July 20, 2020:

Yeah found out the hard way after trying a few times.

in src/script/interpreter.cpp:1659 in a9f418aeb0 outdated

1655+    XOnlyPubKey p{uint256(std::vector<unsigned char>(control.begin() + 1, control.begin() + TAPROOT_CONTROL_BASE_SIZE))};
1656+    XOnlyPubKey q{uint256(program)};
1657+    uint256 k = (CHashWriter(HasherTapLeaf) << uint8_t(control[0] & TAPROOT_LEAF_MASK) << script).GetSHA256();
1658+    for (int i = 0; i < path_len; ++i) {
1659+        CHashWriter ss_branch = HasherTapBranch;
1660+        auto node_begin = control.data() + TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * i;

instagibbs commented at 1:25 pm on July 15, 2020:

I think it’d be cleaner to just make the Span here, then use it for next 4 lines?

sipa commented at 9:17 pm on July 19, 2020:

Good idea, done.

in src/policy/policy.cpp:237 in 43cbfab02a outdated

232@@ -231,6 +233,34 @@ bool IsWitnessStandard(const CTransaction& tx, const CCoinsViewCache& mapInputs)
233                     return false;
234             }
235         }
236+
237+        // Check Taproot standardness limits

instagibbs commented at 1:37 pm on July 15, 2020:

Currently this only enforces MAX_STANDARD_TAPSCRIPT_STACK_ITEM_SIZE on top of consensus checks, yes?

sipa commented at 9:16 pm on July 19, 2020:

Indeed, updated comment.

in test/functional/test_framework/key.py:437 in 98ea8e9b9b outdated

432+    if x == 0 or x >= SECP256K1_ORDER:
433+        return (None, None)
434+    P = SECP256K1.affine(SECP256K1.mul([(SECP256K1_G, x)]))
435+    return (P[0].to_bytes(32, 'big'), not SECP256K1.has_even_y(P))
436+
437+def tweak_privkey(key, tweak, negated=False):

instagibbs commented at 1:40 pm on July 15, 2020:

Should mention/rename it to show it’s “add” not “mult”

sipa commented at 9:17 pm on July 19, 2020:

Done.

in test/functional/test_framework/key.py:459 in 98ea8e9b9b outdated

451+    x = (x + t) % SECP256K1_ORDER
452+    if x == 0:
453+        return None
454+    return x.to_bytes(32, 'big')
455+
456+def tweak_pubkey(key, tweak):

instagibbs commented at 1:40 pm on July 15, 2020:

Should mention/rename it to show it’s “add” not “mult”

sipa commented at 9:17 pm on July 19, 2020:

Done.

jnewbery commented at 9:55 am on July 24, 2020:

should this be tweak_add_pubkey?

instagibbs commented at 1:01 pm on July 24, 2020:

yeah looks like this didn’t change

sipa commented at 11:41 pm on July 28, 2020:

Oops, done now.

instagibbs commented at 1:43 pm on July 15, 2020: member

Did a higher level pass. Pretty easy to follow and review. 👍

Sjors commented at 4:14 pm on July 16, 2020: member

Code reviewed:

284ca85e3fc4d30f60e7fbb903303b4dc935d82c: see #19055 (review)
906819fb3a356c2c49fc6ae66bcd0d6157a7f216
7469f0a078dbaae52848277c92b0592d2628df4f needs description, e.g.: A BIP-341 signature message may commit to the scriptPubKeys of all spent outputs, so store them all instead of processing sequentially..

Regarding the “revert” commits in the secp256k1 branch. Are those to minimise the diff to just Schnorr related changes? Is the plan to do another subtree update like #19228 after https://github.com/bitcoin-core/secp256k1/pull/558 is merged?

You can link to the BIP pages themselves now in the description.

instagibbs commented at 2:13 pm on July 17, 2020: member

I reviewed the tests(way more comprehensive than I thought), and made some commits which I believe increase readability quite a bit and test case(s): https://github.com/instagibbs/bitcoin/commits/taproot_tests

Tests cases I’d like covered:

Invalid CScriptNum( too large) as input to CHECKSIGADD
Tests prior to activation of taproot (ideally you could run all the tests again, make sure they always pass block validity, even “damaged” cases? Future Work since no activation method is specified anyways yet.)
Too large for script push prior to OP_SUCCESSX causes failure(but not after)
If OP_SUCCESSX is hit, stack element sizes don’t exist
OP_CHECKSIGADD does the correct thing with valid inputs
Test that taproot/tapscript sigs don’t count towards legacy/segwitv0 block sig limits.
Adapt tests to explicitly check for reject message reasons for txns/blocks where possible
“Signature opcodes with unknown public key type and non-empty signature are also counted.”
Test empty signatures executed don’t count towards txin sigop limit … will update list as I go

in test/functional/feature_taproot.py:311 in 23985b72be outdated

306+        self.skip_if_no_wallet()
307+
308+    def set_test_params(self):
309+        self.num_nodes = 1
310+        self.setup_clean_chain = True
311+        self.extra_args = [["-whitelist=127.0.0.1", "-acceptnonstdtxn=0", "-par=1"]]

instagibbs commented at 6:29 pm on July 17, 2020:

FYI nonstandard txns are rejected by default in regtest now ( I don’t mind explicit args in tests so meh)

sipa commented at 9:17 pm on July 19, 2020:

Done.

sipa force-pushed on Jul 19, 2020

sipa commented at 9:22 pm on July 19, 2020: member

Rebased, updated to latest version of https://github.com/bitcoin-core/secp256k1/pull/558, and addressed a number of comments above. @Sjors The revert commits are a side-effect of using git subtree to switch to https://github.com/bitcoin-core/secp256k1/pull/558 (which itself is not based on secp256k1 master, so things in master but not there get reverted). Yes, the plan is to merge the Schnorr code in libsecp256k1, and then update subtree in this repo, before actually merging this PR. @instagibbs All of those test improvements look great! I’d prefer not picking up dozens of tiny commits for them though; do you want me to just squash them into the relevant commit here, or do you want to wait until you’ve done more? One nit: when adding overall comments about what a Python function does, use """bla""" docstrings instead of # comments.

instagibbs commented at 1:09 am on July 20, 2020: member

@sipa take the tests in any form you’d like, I just thought it would be easier for you to review the changes.

I’m done for now, so feel free to check off any un-ticked boxes yourself.

sipa force-pushed on Jul 20, 2020

sipa commented at 1:57 am on July 20, 2020: member

@instagibbs All your test improvements squashed into the relevant commits here.

in test/functional/feature_taproot.py:701 in 42bda3592c outdated

650+                CScript([CScriptNum(oversize_number-1), pub2, OP_CHECKSIGADD]),
651+                # 29) CHECKSIGADD that must fail because numeric argument number is >4 bytes
652+                CScript([CScriptNum(oversize_number), pub2, OP_CHECKSIGADD]),
653+            ]
654+            # For the next test we must predict the exact witness size
655+            witness_size = 141 + (hashtype != 0) + (0 if annex is None else len(annex) + 1)

instagibbs commented at 2:11 am on July 20, 2020:

Wondering if you could un-magic this constant a bit. I was going to attempt to write another case for unknown pubkey using this template, but ran out of motivation to reverse engineer it.

sipa commented at 4:49 am on July 28, 2020:

I still have to do this.

sipa commented at 11:40 pm on July 28, 2020:

Better now? I’ve extended the test further too, and moved it to its own section.

sipa force-pushed on Jul 20, 2020

sipa force-pushed on Jul 21, 2020

sipa commented at 8:55 pm on July 21, 2020: member

Squashed in some more functional test improvements by @instagibbs. The failed spenders no check for expected error messages in block validation.

in src/script/interpreter.cpp:1362 in 41d08f5d77 outdated

1264@@ -1265,7 +1265,7 @@ uint256 GetPrevoutHash(const T& txTo)
1265     for (const auto& txin : txTo.vin) {
1266         ss << txin.prevout;
1267     }
1268-    return ss.GetHash();
1269+    return ss.GetSHA256();

Sjors commented at 2:43 pm on July 23, 2020:

41d08f5d77f52bec0e31bb081d85fff2d67d0467: let’s document that uint256 GetPrevoutHash and GetSequenceHash (now) return a single SHA256 hash.

Perhaps we should rename them to GetPrevoutsHash and GetSequencesHash, consistent with GetSpentAmountsHash and GetSpentScriptsHash.

In BIP-341 the phrasing is slightly ambiguous: “sha_prevouts (32): the SHA256 of the serialization of all input outpoints.” It could be more clear that this means concatenate all previous and then hash them, rather than to concatenate the hashes. Changing the variable name helps with that clarity too.

JeremyRubin commented at 9:38 pm on July 23, 2020:

@Sjors please review https://github.com/bitcoin/bitcoin/pull/18071/files which proposes something similar.

sipa commented at 4:50 am on July 28, 2020:

Added some extra comments.

in src/script/interpreter.cpp:1321 in 41d08f5d77 outdated

1316@@ -1299,9 +1317,17 @@ void PrecomputedTransactionData::Init(const T& txTo, std::vector<CTxOut> spent_o
1317 
1318     // Cache is calculated only for transactions with witness
1319     if (txTo.HasWitness()) {
1320-        hashPrevouts = GetPrevoutHash(txTo);
1321-        hashSequence = GetSequenceHash(txTo);
1322-        hashOutputs = GetOutputsHash(txTo);
1323+        m_prevouts_hash = GetPrevoutHash(txTo);
1324+        hashPrevouts = SHA256Uint256(m_prevouts_hash);

Sjors commented at 3:16 pm on July 23, 2020:

41d08f5d77f52bec0e31bb081d85fff2d67d0467: maybe rename to m_prevouts_hash_v0 or m_prevouts_double_hash?

In addition, shouldn’t we skip calculating hashes we don’t need depending on the witness version? Or is that negligible for validation performance (sorry, too lazy to bench this myself)?

JeremyRubin commented at 9:42 pm on July 23, 2020:

these are computed at the txn level, so you’d need to add some code which detects if there is no input of that type. Maybe worthwhile?

But keep in mind that taproot isn’t calculating anything new, just caching the intermediate results…

Sjors commented at 9:25 am on July 24, 2020:

Don’t m_spent_amounts_hash and m_spent_scripts_hash (below) add two extra hash operations when verifying SegWit transactions?

JeremyRubin commented at 7:32 pm on July 24, 2020:

ah yes those are extra, but only when haswitness. I suppose we could add a function hasv1witness?

sipa commented at 4:50 am on July 28, 2020:

I’ve made some significant changes here; the code will now detect if a transaction needs BIP341 and/or BIP143 sighashing, and then only precompute what is needed for the existing ones.

JeremyRubin commented at 3:09 am on August 28, 2020:

I think it’s after this comment that the hash names began containing bip341?

I don’t think it’s worth changing at this point, but I don’t love that naming convention because it’s more clear to name them based on what they are (e.g., m_prevouts_sha256 or m_prevouts_d_sha256) than to name based on a BIP, especially since 143 and 341 are digit wise reversed it tripped me up a bit when re-reviewing.

This is also confusing because CTV & anyprevout will also use these same single hashes, so then it’s not even really accurate to call them bip341 hashes – that’s actually why I noticed, because rebasing CTV on taproot needed to be adjusted for the new names.

Again, not worth changing at this point, but if you decide to rename them again later might be worth going to non bip name.

in src/script/interpreter.cpp:1348 in 41d08f5d77 outdated

1344@@ -1319,6 +1345,76 @@ template void PrecomputedTransactionData::Init(const CMutableTransaction& txTo,
1345 template PrecomputedTransactionData::PrecomputedTransactionData(const CTransaction& txTo);
1346 template PrecomputedTransactionData::PrecomputedTransactionData(const CMutableTransaction& txTo);
1347 
1348+static const CHashWriter HasherTapSighash = TaggedHash("TapSighash");

Sjors commented at 3:21 pm on July 23, 2020:

41d08f5d77f52bec0e31bb081d85fff2d67d0467 : TapSighash is written in camel case (TapSigHash) most of the time in BIP 341 (which would be my preference too).

fjahr commented at 4:54 pm on July 24, 2020:

I think these runtime constants tend to be formatted like normal variables in the rest of the code base, i.e. snake case. But there does not seem to be a particular rule on these in the style guide.

Sjors commented at 7:30 am on July 25, 2020:

Assuming this is in reply to #17977 (review) The string “TapSighash” itself, not the variable name, is consensus critical, because it gets hashed into transactions. So the code style guidelines aren’t relevant.

sipa commented at 4:51 am on July 28, 2020:

The constant itself is consensus-critical.

The name of the variable was a style violation; it’s a constant, it should be ALL_CAPS. Did that.

sipa commented at 4:58 am on July 28, 2020:

Changed the variable name.

sipa commented at 8:54 pm on July 28, 2020:

See https://github.com/bitcoin/bips/pull/954 for fixing the consensus-critical inconsistency.

in src/script/interpreter.cpp:1496 in 41d08f5d77 outdated

1362+    assert(cache != nullptr && cache->m_ready && cache->m_spent_outputs_ready);
1363+
1364+    CHashWriter ss = HasherTapSighash;
1365+
1366+    // Epoch
1367+    static constexpr uint8_t EPOCH = 0;

Sjors commented at 6:42 pm on July 23, 2020:

41d08f5d77f52bec0e31bb081d85fff2d67d0467: EPOCH is explained in BIP-341, but missing from “the message is the concatenation of the following data, in order”

sipa commented at 4:52 am on July 28, 2020:

The epoch is explained in footnote 19 of BIP341. Not sure what is missing.

in src/script/interpreter.cpp:1514 in 41d08f5d77 outdated

1381+        ss << cache->m_prevouts_hash;
1382+        ss << cache->m_spent_amounts_hash;
1383+        ss << cache->m_spent_scripts_hash;
1384+        ss << cache->m_sequences_hash;
1385+    }
1386+    if (output_type == SIGHASH_ALL) {

Sjors commented at 7:00 pm on July 23, 2020:

41d08f5: this could lead to confusion if a later upgrade adds and permits a new SIGHASH type, given that the BIP specifies this as a negative: “If hash_type & 3 does not equal SIGHASH_NONE or SIGHASH_SINGLE”.

sipa commented at 4:53 am on July 28, 2020:

If this code is reused for a new sighash algorithm, this will be the least of our problems.

in src/script/interpreter.cpp:1392 in 41d08f5d77 outdated

1387+        ss << cache->m_outputs_hash;
1388+    }
1389+
1390+    // Data about the input/prevout being spent
1391+    const auto* witstack = &tx_to.vin[in_pos].scriptWitness.stack;
1392+    bool have_annex = witstack->size() > 1 && witstack->back().size() > 0 && witstack->back()[0] == 0xff;

Sjors commented at 7:02 pm on July 23, 2020:

41d08f5: The BIP (still?) says 0x50 (I see this completely changes in a later commit, so will revisit then)

sipa commented at 4:53 am on July 28, 2020:

Good catch, fixed.

in src/script/interpreter.cpp:1403 in 41d08f5d77 outdated

1398+        ss << tx_to.vin[in_pos].nSequence;
1399+    } else {
1400+        ss << in_pos;
1401+    }
1402+    if (have_annex) {
1403+        ss << (CHashWriter(SER_GETHASH, 0) << witstack->back()).GetSHA256();

Sjors commented at 7:12 pm on July 23, 2020:

41d08f5d77f52bec0e31bb081d85fff2d67d0467 : isn’t this missing a compact_size(size of annex) prefix?

instagibbs commented at 7:26 pm on July 23, 2020:

I thought that was implicit with vector serializations like this.

Sjors commented at 7:44 pm on July 23, 2020:

Having bumped my head against (missing) size bytes in serialisations, e.g with libwally, let’s at least add a comment to that effect.

sipa commented at 7:50 pm on July 23, 2020:

Vectors are serialized everywhere this way. Do we need to add comments also to block, transaction inputs, transaction outputs, ADDR messages, all lists in the protocol, …?

Sjors commented at 9:26 am on July 24, 2020:

No, you’re right, it’s actually the BIP that explicitly mentions it only here.

Sjors commented at 7:18 pm on July 23, 2020: member

Reviewed 41d08f5d77f52bec0e31bb081d85fff2d67d0467 Implement Taproot signature hashing (BIP 341)

in src/secp256k1/src/modules/schnorrsig/main_impl.h:162 in ad51604f57 outdated

156+        secp256k1_scalar_negate(&k, &k);
157+    }
158+    secp256k1_fe_normalize_var(&r.x);
159+    secp256k1_fe_get_b32(&sig64[0], &r.x);
160+
161+    /* tagged hash(r.x, pk.x, msg32) */

brmdbr commented at 10:47 pm on July 23, 2020:

Hate to do this: capitalisation. Tagged hash

sipa commented at 4:54 am on July 28, 2020:

Comments for the libsecp256k1 changes should go to the PR there: https://github.com/bitcoin-core/secp256k1/pull/558

in src/hash.cpp:91 in ad51604f57 outdated

86+    CSHA256().Write((const unsigned char*)tag.data(), tag.size()).Finalize(taghash.begin());
87+    writer << taghash << taghash;
88+    return writer;
89+}
90+
91+uint256 SHA256Uint256(const uint256& hash)

jnewbery commented at 9:25 am on July 24, 2020:

hash is the wrong name for this param. It should be input to match the header declaration (although I think preimage would be better still).

sipa commented at 4:54 am on July 28, 2020:

I’ve changed it to data. I think preimage is more useful when you’re talking about a hash input that generates a specified output.

in src/script/interpreter.h:155 in ad51604f57 outdated

147+    //! Single-SHA256 versions
148+    uint256 m_prevouts_hash, m_sequences_hash, m_outputs_hash, m_spent_amounts_hash, m_spent_scripts_hash;
149+    bool m_spent_outputs_ready = false;
150+
151+    //! Double-SHA256 versions
152     uint256 hashPrevouts, hashSequence, hashOutputs;

jnewbery commented at 9:44 am on July 24, 2020:

I agree with @Sjors (https://github.com/bitcoin/bitcoin/pull/17977#discussion_r459527853) that these should be renamed. m_prevouts_hash and hashPrevouts doesn’t communicate that one of these members is the SHA256 digest and the other is the dSHA256 digest. I’d propose m_prevouts_sha256 and m_prevouts_double_sha256, but anything that communicates what these are would be an improvement.

sipa commented at 4:55 am on July 28, 2020:

Renamed the BIP341 ones with just a _bip341_ in the name, which is as specific as it can be, I think. I’m trying not to touch too much other stuff, so the others keep their name.

in test/functional/test_framework/key.py:11 in ad51604f57 outdated

 6@@ -7,6 +7,17 @@
 7 keys, and is trivially vulnerable to side channel attacks. Do not use for
 8 anything but tests."""
 9 import random
10+import hashlib

jnewbery commented at 9:52 am on July 24, 2020:

nit: sort :)

sipa commented at 6:13 pm on August 7, 2020:

Done.

in src/script/interpreter.cpp:432 in cbcaab9a66 outdated

370@@ -371,7 +371,7 @@ static bool EvalChecksig(const valtype& vchSig, const valtype& vchPubKey, CScrip
371     return true;
372 }
373 
374-bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* serror)
375+bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* serror, ScriptExecutionData execdata)

fjahr commented at 2:15 pm on July 24, 2020:

nit: I would prefer the execdata before serror. Would also be more consistent with ExecuteWitnessScript.

sipa commented at 4:58 am on July 28, 2020:

Meh.

sipa commented at 6:16 pm on August 7, 2020:

Not going to do this, as it would mean changing more call sites (which currently pass serror, but wouldn’t have an execdata to pass).

in src/script/interpreter.h:177 in b7a7f6ab2c outdated

157@@ -146,14 +158,21 @@ struct PrecomputedTransactionData
158 
159 enum class SigVersion
160 {
161-    BASE = 0,
162-    WITNESS_V0 = 1,
163-    TAPROOT = 2,
164+    BASE = 0,        //!< Bare scripts and P2SH redeemscripts; see BIP 16

Sjors commented at 2:33 pm on July 24, 2020:

b7a7f6ab2ccc30e323a5396c27cb82ffd613550b nit: these comments could be introduced in 41d08f5d77f52bec0e31bb081d85fff2d67d0467 (which adds TAPROOT = 2)

sipa commented at 4:55 am on July 28, 2020:

Indeed, done.

in src/script/interpreter.h:168 in cbcaab9a66 outdated

162@@ -163,6 +163,16 @@ enum class SigVersion
163     TAPROOT = 2,     //!< Witness v1 with non-P2SH 32 byte program (Taproot), key path spending; see BIP 341
164 };
165 
166+struct ScriptExecutionData
167+{
168+    //! Whether m_annex_present and m_annex_hash are initialized.

Sjors commented at 4:35 pm on July 24, 2020:

cbcaab9a66f82fa5bcc2711a5fee2adc47004cc8 nit: m_annex_hash is only initialized if m_annex_present is true, though I doubt it will confuse anyone. Alternate wordings:

0//! Whether m_annex_present is initialized

Or:

0 //! Whether m_annex_present and (when needed) m_annex_hash are initialized.

JeremyRubin commented at 9:02 pm on July 24, 2020:

#17977#pullrequestreview-348338789

sipa commented at 4:57 am on July 28, 2020:

Done.

in src/validation.cpp:1546 in 14d2178048 outdated

1539@@ -1540,13 +1540,19 @@ bool CheckInputScripts(const CTransaction& tx, TxValidationState &state, const C
1540     }
1541 
1542     if (!txdata.m_ready) {
1543-        txdata.Init(tx);
1544+        std::vector<CTxOut> spent_outputs;
1545+        spent_outputs.reserve(tx.vin.size());
1546+
1547+        for (unsigned int i = 0; i < tx.vin.size(); i++) {

fjahr commented at 4:56 pm on July 24, 2020:

styleguide nit:

0        for (unsigned int i = 0; i < tx.vin.size(); ++i) {

sipa commented at 4:58 am on July 28, 2020:

Done.

in src/script/interpreter.cpp:381 in 988d7a795c outdated

376+     *  The following validation sequence is consensus critical. Please note how --
377+     *    upgradable public key versions precede other rules;
378+     *    the script execution fails when using empty signature with invalid public key;
379+     *    the script execution fails when using non-empty invalid signature.
380+     */
381+    success = !sig.empty();

Sjors commented at 6:14 pm on July 24, 2020:

I would find it marginally more readable to use !sig.empty() in the if statements below and move success = !sig.empty(); all the way to the bottom.

sipa commented at 4:57 am on July 28, 2020:

I’m not sure. The result is always exactly equal to !sig.empty() if no failure occurs, so I think this makes sense.

in src/script/interpreter.cpp:411 in 988d7a795c outdated

406+    }
407+
408+    return true;
409+}
410+
411+/** Helper for OP_CHECKSIG and OP_CHECKSIGVERIFY

Sjors commented at 6:22 pm on July 24, 2020:

0/** Helper for OP_CHECKSIG, OP_CHECKSIGVERIFY and OP_CHECKSIGADD

sipa commented at 4:58 am on July 28, 2020:

Done.

in src/script/interpreter.cpp:1780 in 988d7a795c outdated

1741+        // OP_SUCCESSx processing overrides everything, including stack element size limits
1742+        CScript::const_iterator pc = scriptPubKey.begin();
1743+        while (pc < scriptPubKey.end()) {
1744+            opcodetype opcode;
1745+            if (!scriptPubKey.GetOp(pc, opcode)) {
1746+                // Note how this condition would not be reached if an unknown OP_SUCCESSx was found

Sjors commented at 7:03 pm on July 24, 2020:

But only if OP_SUCCESSx occurred earlier? Is it worth the effort to check the whole script for OP_SUCCESSx before and then do second pass for other conditions?

JeremyRubin commented at 7:40 pm on July 24, 2020:

Nope, the spec is defined as first parsing the script into opcodes to check for OP_SUCCESSx, and then executing.

JeremyRubin commented at 7:40 pm on July 24, 2020:

so you should check for e.g. unexecuted branches as well.

Sjors commented at 7:23 am on July 25, 2020:

Afaik this code fails if it finds an unknown OPCODE before OP_SUCCESSx, so then it doesn’t match the spec?

sipa commented at 7:30 am on July 25, 2020:

If by unknown opcode you mean undecodable, no - because if an opcode can’t be decoded, there are also no other opcodes decodable after it.

Sjors commented at 10:59 am on July 25, 2020:

It wasn’t entirely clear to me what GetScriptOp does, in particular what happens if an opcode does not occur in the opcodetype enum, but apparently this is fine.

Sjors commented at 7:17 pm on July 24, 2020: member

Also reviewed 8594b77415c290089d2e88fd2c09dbfecef995ba (BIP 340) until 988d7a795cfc29b37c3ea3359fb69412ab04de53 (BIP 342)

There’s two future anticipated features the BIPs: batch-verification and annexes. Is there any proof of concept code that can be used to sanity check this PR (and the BIPs themselves)?

real-or-random commented at 8:25 pm on July 24, 2020: member

Also reviewed 8594b77 (BIP 340) until 988d7a7 (BIP 342)

There’s two future anticipated features the BIPs: batch-verification and annexes. Is there any proof of concept code that can be used to sanity check this PR (and the BIPs themselves)?

Not sure if this is helpful but there’s https://github.com/bitcoin-core/secp256k1/pull/760.

fjahr commented at 10:28 pm on July 24, 2020: member

Initial review of 6c98ca63df45bebe2b87c69244f36d75f1ab4c82 to c05ec93cf9affc44c9c548f69685500c7648691e, everything but schnorr and tests, mainly focussed on comparing code and the BIPs. Only leaving a few nits, feel free to ignore. Will still review the tests more thoroughly.

sipa force-pushed on Jul 28, 2020

sipa commented at 5:02 am on July 28, 2020: member

Rebased, updated to latest libsecp256k1 Schnorr PR, addressed a number of comments (though there are a few left). The biggest change is that the sighash precomputation now takes into account whether a transaction contains/needs taproot precomputation or not.

I also improved the functional tests. It now includes P2PKH/P2WPKH/P2SH-P2WPKH spends as well, just to make sure transactions with mixes have their sighashes computed correctly still. The framework now also tracks (pre-taproot) sigops, to accurately fill the block with them.

The BIP340 implementation in the test framework is also updated to the latest spec (including support for the auxiliary randomness), and implements/contains the BIP’s test vectors now (which are verified against the secp256k1 implementation as well).

sipa force-pushed on Jul 28, 2020

sipa renamed this:
~~[WIP] Implement BIP 340-342 validation (Schnorr/taproot/tapscript)~~
Implement BIP 340-342 validation (Schnorr/taproot/tapscript)
on Jul 28, 2020

in test/functional/feature_taproot.py:1156 in 92d3928ed1 outdated

405+
406+    def block_submit(self, node, txs, msg, err_msg, cb_pubkey=None, fees=0, sigops_weight=0, witness=False, accept=False):
407+
408+        # Deplete block of any non-tapscript sigops using a single additional 0-value coinbase output.
409+        # It is not impossible to fit enough tapscript sigops to hit the old 80k limit without
410+        # busting txin-level limits. We simply have to account for the p2pk outputs in all

instagibbs commented at 2:01 pm on July 28, 2020:

Last sentence here is outdated.

sipa commented at 9:17 pm on August 6, 2020:

How so?

instagibbs commented at 0:53 am on August 7, 2020:

I was taking p2pk literally but I guess it could be read more generally.

sipa commented at 6:18 pm on August 7, 2020:

You can take it literally. P2PK (and other bare-public-key-in-output types, but there aren’t any of those in this test) are the only ones that cost sigops.

instagibbs commented at 6:22 pm on August 7, 2020:

ok I misunderstood your comment, will just review instead.

in test/functional/feature_taproot.py:1158 in 92d3928ed1 outdated

407+
408+        # Deplete block of any non-tapscript sigops using a single additional 0-value coinbase output.
409+        # It is not impossible to fit enough tapscript sigops to hit the old 80k limit without
410+        # busting txin-level limits. We simply have to account for the p2pk outputs in all
411+        # transactions.
412+        extra_output_script = CScript([OP_CHECKSIG]*((MAX_BLOCK_SIGOPS_WEIGHT - sigops_weight) // WITNESS_SCALE_FACTOR))

instagibbs commented at 2:04 pm on July 28, 2020:

nice, you may get 1 to 3 sigops weight left over by chance, but tests will blow that out regularly.

sipa commented at 8:21 pm on July 28, 2020:

Yeah, I know, but it’s a lot harder to test that accurately (it needs creating outputs and spending them using witness spends, …).

Ideally, we’d also test that if you have one sigop too many, things also fail. Otherwise it could be the case that some of the sigops estimates in the test are overestimates.

instagibbs commented at 2:06 pm on July 28, 2020: member

Looks great, love the mixed input types. test delta ACK

sipa force-pushed on Jul 28, 2020

gmaxwell commented at 2:25 am on July 29, 2020: contributor

im in ur codebase 0pt1miz1ng ur lines.

u can tell diz code waz unoptimal cuz feature_taproot.py still passes with this optimization

 0diff --git a/src/secp256k1/src/modules/schnorrsig/main_impl.h b/src/secp256k1/src/modules/schnorrsig/main_impl.h
 1index 2ec1cea5b..5efdee4b4 100644
 2--- a/src/secp256k1/src/modules/schnorrsig/main_impl.h
 3+++ b/src/secp256k1/src/modules/schnorrsig/main_impl.h
 4@@ -223,8 +223,7 @@ int secp256k1_schnorrsig_verify(const secp256k1_context* ctx, const unsigned cha
 5     secp256k1_gej_set_ge(&pkj, &pk);
 6     secp256k1_ecmult(&ctx->ecmult_ctx, &rj, &pkj, &e, &s);
 7 
 8-    return secp256k1_gej_has_quad_y_var(&rj) /* fails if rj is infinity */
 9-            && secp256k1_gej_eq_x_var(&rx, &rj);
10+    return secp256k1_gej_eq_x_var(&rx, &rj);
11 }
12 
13 #endif

(yes, libsecp256k1’s tests catches this, but this an an important and easily botched consensus rule too)

moar optimization “fixes” coming soon

gmaxwell commented at 2:45 am on July 29, 2020: contributor

all numb3erz r equally blessed in eyes of ur tests

 0diff --git a/src/secp256k1/src/modules/extrakeys/main_impl.h b/src/secp256k1/src/modules/extrakeys/main_impl.h
 1index a2abc6afa..04c84bde5 100644
 2--- a/src/secp256k1/src/modules/extrakeys/main_impl.h
 3+++ b/src/secp256k1/src/modules/extrakeys/main_impl.h
 4@@ -30,9 +30,8 @@ int secp256k1_xonly_pubkey_parse(const secp256k1_context* ctx, secp256k1_xonly_p
 5     if (!secp256k1_fe_set_b32(&x, input32)) {
 6         return 0;
 7     }
 8-    if (!secp256k1_ge_set_xo_var(&pk, &x, 0)) {
 9-        return 0;
10-    }
11+    secp256k1_ge_set_xo_var(&pk, &x, 0);
12+
13     secp256k1_xonly_pubkey_save(pubkey, &pk);
14     secp256k1_ge_clear(&pk);
15     return 1;

gmaxwell commented at 3:20 am on July 29, 2020: contributor

shrinking ur transactshuns.

y send sign if ne1 no care?

 0diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
 1index e095f0a42..1f6d4ca14 100644
 2--- a/src/script/interpreter.cpp
 3+++ b/src/script/interpreter.cpp
 4@@ -1823,7 +1823,7 @@ static bool VerifyTaprootCommitment(const std::vector<unsigned char>& control, c
 5         k = ss_branch.GetSHA256();
 6     }
 7     k = (CHashWriter(HASHER_TAPTWEAK) << MakeSpan(p) << k).GetSHA256();
 8-    return q.CheckPayToContract(p, k, control[0] & 1);
 9+    return q.CheckPayToContract(p, k, 0) || q.CheckPayToContract(p, k, 1);
10 }
11 
12 static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion, const std::vector<unsigned char>& program, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* serror, bool is_p2sh)

sipa force-pushed on Jul 29, 2020

gmaxwell commented at 3:56 am on July 29, 2020: contributor

2 many byte 4 so little bark

 0diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
 1index e095f0a42..88093caa0 100644
 2--- a/src/script/interpreter.cpp
 3+++ b/src/script/interpreter.cpp
 4@@ -1815,7 +1815,7 @@ static bool VerifyTaprootCommitment(const std::vector<unsigned char>& control, c
 5     for (int i = 0; i < path_len; ++i) {
 6         CHashWriter ss_branch = HASHER_TAPBRANCH;
 7         Span<const unsigned char> node(control.data() + TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * i, TAPROOT_CONTROL_NODE_SIZE);
 8-        if (std::lexicographical_compare(k.begin(), k.end(), node.begin(), node.end())) {
 9+        if (std::lexicographical_compare(k.begin(), k.begin()+2, node.begin(), node.begin()+2)) {
10             ss_branch << k << node;
11         } else {
12             ss_branch << node << k;

gmaxwell commented at 4:03 am on July 29, 2020: contributor

big iz bootyfull

 0diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
 1index e095f0a42..b12cd25ad 100644
 2--- a/src/script/interpreter.cpp
 3+++ b/src/script/interpreter.cpp
 4@@ -1856,7 +1856,7 @@ static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion,
 5         } else {
 6             return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_WRONG_LENGTH);
 7         }
 8-    } else if (witversion == 1 && program.size() == WITNESS_V1_TAPROOT_SIZE && !is_p2sh) {
 9+    } else if (witversion == 1 && program.size() >= WITNESS_V1_TAPROOT_SIZE && !is_p2sh) {
10         // BIP341 Taproot: 32-byte non-P2SH witness v1 program (which encodes a P2C-tweaked pubkey)
11         if (!(flags & SCRIPT_VERIFY_TAPROOT)) return set_success(serror);
12         if (stack.size() == 0) return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_WITNESS_EMPTY);

gmaxwell commented at 4:25 am on July 29, 2020: contributor

deez statemints r doin nuthing

 0diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
 1index e095f0a42..e115a6a99 100644
 2--- a/src/script/interpreter.cpp
 3+++ b/src/script/interpreter.cpp
 4@@ -1858,8 +1858,6 @@ static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion,
 5         }
 6     } else if (witversion == 1 && program.size() == WITNESS_V1_TAPROOT_SIZE && !is_p2sh) {
 7         // BIP341 Taproot: 32-byte non-P2SH witness v1 program (which encodes a P2C-tweaked pubkey)
 8-        if (!(flags & SCRIPT_VERIFY_TAPROOT)) return set_success(serror);
 9-        if (stack.size() == 0) return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_WITNESS_EMPTY);
10         if (stack.size() >= 2 && !stack.back().empty() && stack.back()[0] == ANNEX_TAG) {
11             // Drop annex
12             if (flags & SCRIPT_VERIFY_DISCOURAGE_UNKNOWN_ANNEX) return set_error(serror, SCRIPT_ERR_DISCOURAGE_UNKNOWN_ANNEX);
13@@ -1881,7 +1879,7 @@ static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion,
14             const valtype& control = SpanPopBack(stack);
15             const valtype& script_bytes = SpanPopBack(stack);
16             scriptPubKey = CScript(script_bytes.begin(), script_bytes.end());
17-            if (control.size() < TAPROOT_CONTROL_BASE_SIZE || control.size() > TAPROOT_CONTROL_MAX_SIZE || ((control.size() - TAPROOT_CONTROL_BASE_SIZE) % TAPROOT_CONTROL_NODE_SIZE) != 0) {
18+            if (control.size() > TAPROOT_CONTROL_MAX_SIZE) {
19                 return set_error(serror, SCRIPT_ERR_TAPROOT_WRONG_CONTROL_SIZE);
20             }
21             if (!VerifyTaprootCommitment(control, program, scriptPubKey, &execdata.m_tapleaf_hash)) {

gmaxwell commented at 4:38 am on July 29, 2020: contributor

ur gold star no offset being phat

 0diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
 1index e095f0a42..c2823a565 100644
 2--- a/src/script/interpreter.cpp
 3+++ b/src/script/interpreter.cpp
 4@@ -1770,6 +1770,10 @@ static bool ExecuteWitnessScript(const Span<const valtype>& stack_span, const CS
 5     if (sigversion == SigVersion::TAPSCRIPT) {
 6         // OP_SUCCESSx processing overrides everything, including stack element size limits
 7         CScript::const_iterator pc = scriptPubKey.begin();
 8+        // Tapscript enforces initial stack size limits (altstack is empty here)
 9+        if (stack.size() > MAX_STACK_SIZE) {
10+            return set_error(serror, SCRIPT_ERR_STACK_SIZE);
11+        }
12         while (pc < scriptPubKey.end()) {
13             opcodetype opcode;
14             if (!scriptPubKey.GetOp(pc, opcode)) {
15@@ -1785,10 +1789,6 @@ static bool ExecuteWitnessScript(const Span<const valtype>& stack_span, const CS
16             }
17         }
18 
19-        // Tapscript enforces initial stack size limits (altstack is empty here)
20-        if (stack.size() > MAX_STACK_SIZE) {
21-            return set_error(serror, SCRIPT_ERR_STACK_SIZE);
22-        }
23     }
24 
25     // Disallow stack item size > MAX_SCRIPT_ELEMENT_SIZE in witness stack

gmaxwell commented at 5:18 am on July 29, 2020: contributor

just cuz im empty inside doesnt mean i cant count

 0diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
 1index e095f0a42..a4113be95 100644
 2--- a/src/script/interpreter.cpp
 3+++ b/src/script/interpreter.cpp
 4@@ -379,7 +379,7 @@ static bool EvalChecksigTapscript(const valtype& sig, const valtype& pubkey, Scr
 5      *    the script execution fails when using non-empty invalid signature.
 6      */
 7     success = !sig.empty();
 8-    if (success) {
 9+    {
10         // Implement the sigops/witnesssize ratio test.
11         // Passing with an upgradable public key version is also counted.
12         assert(execdata.m_validation_weight_left_init);

gmaxwell commented at 5:25 am on July 29, 2020: contributor

dont ignore big boyz

 0diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
 1index e095f0a42..a1f46d960 100644
 2--- a/src/script/interpreter.cpp
 3+++ b/src/script/interpreter.cpp
 4@@ -390,7 +390,7 @@ static bool EvalChecksigTapscript(const valtype& sig, const valtype& pubkey, Scr
 5     }
 6     if (pubkey.size() == 0) {
 7         return set_error(serror, SCRIPT_ERR_PUBKEYTYPE);
 8-    } else if (pubkey.size() == 32) {
 9+    } else if (pubkey.size() >= 32) {
10         if (success && !checker.CheckSigSchnorr(sig, pubkey, sigversion, execdata)) {
11             return set_error(serror, SCRIPT_ERR_SIG_NULLFAIL);
12         }

gmaxwell commented at 6:09 am on July 29, 2020: contributor

tapscript iz not 4 minimalists

 0diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
 1index e095f0a42..26dd6c036 100644
 2--- a/src/script/interpreter.cpp
 3+++ b/src/script/interpreter.cpp
 4@@ -634,8 +634,6 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript&
 5                             return set_error(serror, SCRIPT_ERR_UNBALANCED_CONDITIONAL);
 6                         valtype& vch = stacktop(-1);
 7                         if (sigversion == SigVersion::TAPSCRIPT || (sigversion == SigVersion::WITNESS_V0 && (flags & SCRIPT_VERIFY_MINIMALIF))) {
 8-                            if (vch.size() > 1)
 9-                                return set_error(serror, SCRIPT_ERR_MINIMALIF);
10                             if (vch.size() == 1 && vch[0] != 1)
11                                 return set_error(serror, SCRIPT_ERR_MINIMALIF);
12                         }

gmaxwell commented at 6:28 am on July 29, 2020: contributor

why u no share with witness v0??

 0diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
 1index e095f0a42..2697bc482 100644
 2--- a/src/script/interpreter.cpp
 3+++ b/src/script/interpreter.cpp
 4@@ -1097,8 +1097,7 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript&
 5 
 6                 case OP_CHECKSIGADD:
 7                 {
 8-                    // OP_CHECKSIGADD is only available in Tapscript
 9-                    if (sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0) return set_error(serror, SCRIPT_ERR_BAD_OPCODE);
10+                    // OP_CHECKSIGADD is AVAILABLE TO EVERYONE!!!
11 
12                     // (sig num pubkey -- num)
13                     if (stack.size() < 3) return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);

gmaxwell commented at 9:02 am on July 29, 2020: contributor

DONT TRUST VER

 0diff --git a/src/script/script.cpp b/src/script/script.cpp
 1index 8bd10f8ba..2604d5dae 100644
 2--- a/src/script/script.cpp
 3+++ b/src/script/script.cpp
 4@@ -334,7 +334,7 @@ bool GetScriptOp(CScriptBase::const_iterator& pc, CScriptBase::const_iterator en
 5 
 6 bool IsOpSuccess(const opcodetype& opcode)
 7 {
 8-    return (opcode == 0x50 || opcode == 0x62 || opcode == 0x89 ||
 9+    return (opcode == 0x50 || opcode == 0x89 ||
10             opcode == 0x8a || opcode == 0x8d || opcode == 0x8e ||
11             (opcode >= 0x7e && opcode <= 0x81) || (opcode >= 0x83 && opcode <= 0x86) ||
12             (opcode >= 0x95 && opcode <= 0x99) || (opcode >= 0xbb && opcode <= 0xfe));

gmaxwell commented at 9:59 am on July 29, 2020: contributor

u haz boundary but i shifted it

0-static constexpr uint64_t VALIDATION_WEIGHT_OFFSET = 50;
1+static constexpr uint64_t VALIDATION_WEIGHT_OFFSET = 53;

0-static constexpr uint64_t VALIDATION_WEIGHT_OFFSET = 50;
1+static constexpr uint64_t VALIDATION_WEIGHT_OFFSET = 47;

in src/script/sigcache.cpp:25 in 066f086e96 outdated

22@@ -23,7 +23,8 @@ class CSignatureCache
23 {
24 private:
25      //! Entries are SHA256(nonce || signature hash || public key || signature):

gmaxwell commented at 10:38 am on July 29, 2020:

  //! Entries are SHA256(nonce || 'E' or 'S' || 0x00 * 32 || signature hash || public key || signature)

sipa commented at 11:27 pm on August 6, 2020:

Done.

gmaxwell commented at 3:20 pm on July 29, 2020: contributor

Okay, those are all the locations I found where breaking the code still results in the taproot tests passing (and weren’t obviously due to an unreachable condition on account of a redundant consensus rule). In some cases I could have given more examples (e.g. more success opcodes that are untested), though I hope if the tests are improved they’re written more generally than is required to reject my example bugs.

Just as a general comment, I found the way that things like op_success overlays on evalscript to be pretty opaque– e.g. which opcodes still exist and which ones are turned into success? Also interactions like the maximum script size condition in evalscript going from always applying to just applying in base and witness v0. Took a minute to convince myself that there wasn’t an inadvertent consensus change due to the caller already bypassing evalscript for other witness versions. I think it would have been easier to review if evalscript were just split for v1, but because they’re so similar I could argue it either way so I understand why it wasn’t. Though if this is done several more times I think the complexity will compound and a different approach will be needed (which might just be as simple as duplicating the function).

There also are a moderate number of unreachable redundant checks (e.g. signature size) but I figured I would leave that up to someone driven by branch coverage analysis to report those– since they’re harmless but for the fact that they’re false positives on coverage screening. Several of the things I reported should have been obvious on coverage analysis, so I guess no one has done that yet?

All in all it’s a simpler change than I remembered, even having read it completely not that long ago. I found relatively few places that even seemed like they’d be likely mutation targets, though I did have a pretty high hitrate on the things I tried turning up limitations in the tests.

instagibbs commented at 2:15 pm on July 30, 2020: member

test changes through https://github.com/bitcoin/bitcoin/pull/17977/commits/d4260e830a0a3614f05b1bfa855f08edc1a7b39c look good. @gmaxwell : cool stuff. I suspect some of those cases are covered sometimes due to the random nature of some of the tests, for example the OP_VER one. IIRC the test randomly picks an op_success code per run. Maybe it’s worth running all those cases N times when N is reasonably small to get complete coverage per run?

think it would have been easier to review if evalscript were just split for v1, but because they’re so similar I could argue it either way so I understand why it wasn’t. Though if this is done several more times I think the complexity will compound and a different approach will be needed (which might just be as simple as duplicating the function).

+1, Peter Todd argued this back for segwit v0 even, and I found it pretty compelling if we’re going to be making lots of changes in the future.

sipa commented at 5:19 pm on July 30, 2020: member

@instagibbs Indeed; the “y send sign if ne1 no care?” I believe is also covered by random mutations of the control block already - but it’s rare to hit that exact bit.

I’m reworking the tests to make sure more edge cases are always hit (or at least, making it easier to add them).

Unfortunately, it will mean making the randomized Python test take significantly longer. One idea is that we could work to make it as complete as possible, then extract a set of UTXOs/spending transactions from it, use coverage analysis to minimize it, and then turn the result of that into a test vector set - which can be included as a fast unit test (in C++) and added to the BIP.

sipa commented at 5:34 pm on July 30, 2020: member

As far as the idea of having a separate EvalScript goes - indeed, I think that’s a useful idea in general, and I think @theuni has also argued in favour of it.

I chose not to here, because the majority of the changes isn’t actually inside script execution as such. The best argument in favour would be if separation would let us get rid of the OP_SUCCESSx preprocessing step, and have a single pass execution instead. However, because of the “presence of any OP_SUCCESSx in a script triggers success, even if not executed and even if it appears after a failing opcode” behaviour, that isn’t really doable. Other than OP_SUCCESSx handling, there are only a few fairly isolated changes.

That said, I’m not opposed to splitting if off if it aids review.

EDIT: I guess it’s possible to keep track of a bool “failed” during execution, which is set to false whenever a “return false” occurs in the original script execution code, and this flag causes skipping of execution of all opcodes except OP_SUCCESSx ones.

JeremyRubin commented at 6:09 pm on July 30, 2020: contributor

I think it’s a good investment to completely split the interpreters, especially given the myriad of different upgrade mechanisms the current approach can lead to confusing code paths of what is actually getting called (imagine a future with 5 different leaf versions all passing different interpreter flags in – better to normalize that v1 witness leaf versions have their own interpreter separate from v0 and legacy).

see discussion following here: #15969 (comment)

The downside is that this that we end up over time having several different interpreters (e.g., imagine each leaf version having their own interpreter) which can lead to a bloated code base – however I think it’s worth it because it’s much easier to audit change-to-change that remain fully consensus compatible with old implementations. The bloat becomes a problem when we, e.g., switch a representation (like Spans) and then have to mirror the change across much more code.

edit: making sure all testing is consistent and applies on all interpreters might be tough right now, but maybe there’s a way to make sure all tests are hitting all code paths for legacy and new interpreters.

edit2: @sipa, is there also logic that we could remove from a v1 interpreter that is only required for legacy interpretation?

gmaxwell commented at 2:39 am on August 1, 2020: contributor

That said, I’m not opposed to splitting if off if it aids review.

Well I, and presumably other reviewers, already undertook the additional cost. So I don’t think doing it would aid me now.

It’s a change that could be made at any time in the future too.

EDIT: I guess it’s possible to keep track of a bool “failed” during execution, which is set to false whenever a “return false” occurs in the original script execution code, and this flag causes skipping of execution of all opcodes except OP_SUCCESSx ones.

Yes, though the interaction with size limits needs to be minded. I don’t think having two passes was that big of a deal however, but the fact that there is a bunch of code that is there but won’t execute due to the first pass did take a little extra review effort.

Right now there is no trivial way to prove that the changes don’t change existing basic/v0 scripts. If it were split, you could just look and see that evalscript literally doesn’t change except for the v1 case.

In any case, I don’t particularly think it’s worth changing now. I think it will probably get split in the future however, if not for v1 then for some other version or leaf version.

but maybe there’s a way to make sure all tests are hitting all code paths for legacy and new interpreters.

It’s called branch coverage analysis. :)

edit2: @sipa, is there also logic that we could remove from a v1 interpreter that is only required for legacy interpretation?

All the guts of the opcodes turned into success, as well as the guts from the checkmultisig stuff that was disabled.

JeremyRubin commented at 5:43 am on August 1, 2020: contributor

I don’t think branch coverage fully helps because it’s conceivable we have multiple tests that cover things and coverage might not help that much…

I think there might be a kinda silly way to split the interpreters for the taproot implementation without causing anyone to have to re-review much taproot related.

take current tip of taproot
Move the interpreter guts into a new file/dir called v1 script, update both paths to use this new location interpreter.
check out the pre-taproot interpreter files. (reviewers can verify this step by checking out from the named commit hash)
switch non v1 to use the old interpreter again
(some time later) move the legacy interpreter to it’s own directory
(optional) clear out code paths in v1 interpreter that are clearly unused (can do with aid of coverage tools)

This causes a pretty small amount of new review work for what may be a substantial benefit. In terms of consensus consistency:

Doing this after release would be very hard, because the risk that we accidentally had some additional rule change on legacy interpreter semantics that would get hard-fork undone on change. I think the developer community would think it’s a waste of time and effort to do this after release, so it’s worth at least considering now. After merge but before release is still doable as there’s no consistency issue, but the git history is better bisectable if they are contiguous in git history.
This minimizes the potential for any taproot changes that break legacy interpretation
If there are behavior changes against taproot as is (which should come up in tests), this is before release, so it’s OK as long as the behavior is pinned before any release
No re-review is required as this is purely forward changes.

sipa commented at 6:10 am on August 1, 2020: member

@JeremyRubin There are plenty of ways to minimize the difference with both the existing branch here, and between the new legacy interpreter and the current interpreter in master.

The question whether we want it. It at least means additional review, and code duplication. Given there has already been a decent amount of review here, I’d rather not do it unless there’s wide agreement about the change.

The amount of code that can be removed from the hypothetical new interpreter is pretty minimal I think - OP_CHECKMULTISIG(VERIFY) and some accounting (201 opcode limit). All the OP_SUCCESSx codes are “immediate failure” in the current interpreter, so not really anything to gain from that.

DrahtBot added the label Needs rebase on Aug 3, 2020

in src/script/interpreter.cpp:1441 in d4260e830a outdated

1450+        // Computations shared between both sighash schemes.
1451+        m_bip341_prevouts_hash = GetPrevoutHash(txTo);
1452+        m_bip341_sequences_hash = GetSequenceHash(txTo);
1453+        m_bip341_outputs_hash = GetOutputsHash(txTo);
1454+    }
1455+    if (uses_bip143) {

JeremyRubin commented at 1:03 am on August 4, 2020:

don’t we use these caches for any non taproot signature? Not just segwit?

sipa commented at 1:05 am on August 4, 2020:

No, there is nothing to be cached for pre-segwit sighashes (they’re just hashing a serialized modified transaction).

theuni commented at 1:20 am on August 4, 2020: member

As far as the idea of having a separate EvalScript goes - indeed, I think that’s a useful idea in general, and I think @theuni has also argued in favour of it.

I chose not to here, because the majority of the changes isn’t actually inside script execution as such. The best argument in favour would be if separation would let us get rid of the OP_SUCCESSx preprocessing step, and have a single pass execution instead. However, because of the “presence of any OP_SUCCESSx in a script triggers success, even if not executed and even if it appears after a failing opcode” behaviour, that isn’t really doable. Other than OP_SUCCESSx handling, there are only a few fairly isolated changes.

That said, I’m not opposed to splitting if off if it aids review.

I really like this idea. So much so that I have a branch with a similar split. I was hoping to get a taproot implementation done on top of it so that I could propose it before review of this PR really cranked up, but sadly I didn’t make it in time and decided to just drop it.

For anyone interested, this is my attempt at split interpreters: https://github.com/theuni/bitcoin/tree/policy-split2

It splits consensus and policy, but the split could be anything. I didn’t go as far as splitting out the interpreters into separate files, but I think it’s easy to see where it was going.

in src/script/interpreter.cpp:1426 in d4260e830a outdated

1429+    // Determine which precomputation-impacting features this transaction uses.
1430+    bool uses_bip143 = false;
1431+    bool uses_bip341 = false;
1432+    for (size_t inpos = 0; inpos < txTo.vin.size(); ++inpos) {
1433+        if (!txTo.vin[inpos].scriptWitness.IsNull()) {
1434+            if (m_spent_outputs_ready && m_spent_outputs[inpos].scriptPubKey.size() == 2 + WITNESS_V1_TAPROOT_SIZE &&

instagibbs commented at 3:00 pm on August 4, 2020:

I’d kind of prefer to just use IsWitnessProgram to grab the values for here since I know that works already.

What about erring on the side of bip341 precomputing instead? Could just say:

0if (m_spent_outputs_ready && m_spent_outputs[inpos].scriptPubKey.IsWitnessProgram(version, witness_program) && version > 0) {

then we can delete the “unknown witness verison” comment below.

sipa commented at 11:24 pm on August 6, 2020:

We also need to make sure that BIP143 caching is enabled for P2SH-wrapped segwit spends (where we can’t just look at the scriptPubKey, and going as far as doing P2SH decoding seems excessive here).

I was trying to avoid IsWitnessProgram since it’d create an unnecessary copy of witness_program.

ShawkiS approved

sipa force-pushed on Aug 6, 2020

DrahtBot removed the label Needs rebase on Aug 6, 2020

sipa commented at 11:48 pm on August 6, 2020: member

Rebased, and big update to the functional tests.

During test improving I discovered a discrepancy between the implemented consensus rules and the BIP: undefined hashtypes were not rejected as they should be. This is now fixed (and tested).

I’ve addressed most of the discoveries by @gmaxwell’s lolcat above:

u haz boundary but i shifted it: I’ve reworked the sigops ratio test to have much better accuracy; any divergence in the computation should now be detected.
DONT TRUST VER: the OP_SUCCESSx tests are now run for all changed opcodes, rather than randomly. Tests are also added to verify that all other opcodes do not have their behavior modified. (TODO: verify that OP_SUCCESSx isn’t applied to non-Taproot spends)
why u no share with witness v0??: added an explicit test that OP_CHECKSIGADD doesn’t work for legacy or witv0 spends
tapscript iz not 4 minimalists: added a test that feeds larger-than-1-byte truthy values to OP_IF and OP_NOTIF
dont ignore big boyz: added tests with larger-than-32byte pubkeys (and specifically one that uses traditional 33-byte pubkeys with 0x02/0x03 prefix)
just cuz im empty inside doesnt mean i cant count: tests for OP_CHECKSIG and OP_CHECKSIGADD were added to verify that 0-byte (failing) signatures do not count towards the sigops ratio test.
ur gold star no offset being phat: added a test that the input stacksize limit does not apply with OP_SUCCESSx (all of them)
2 many byte 4 so little bark: several tests now include Merkle branch elements that equal the partner hashed with, or that value +1 or -1 (both in little endian and big endian).
im in ur codebase 0pt1miz1ng ur lines.: the BIP340 test vectors are now also tested in a unit test, and a functional test was added that signs with incorrect R sign (and one with incorrect P sign as well)
deez statemints r doin nuthing:
- TODO: the return if taproot validation is off isn’t tested yet, as there are no tests to verify pre-taproot-activation behavior is unaffected. Added a TODO in the PR description for that.
- A test for witness stack size 0 was added.
- A test that appends to, or truncates, the control block was added (and specifically, one that reduces it to size 1)
big iz bootyfull: added tests that taproot validation doesn’t apply to (version != 1, p2sh, or programsize != 32) segwit outputs.
all numb3erz r equally blessed in eyes of ur tests: this is very hard to test, as it would require constructing a signature that validates except for not having R on the curve.
y send sign if ne1 no care?: this was tested before (random control block bit flips), but was only hit with very low probability. Added a test that explicitly tests negation of the sign bit. @gsanders @jnewbery In the process I’ve also significantly rewritten the functional tests. There is now just a single “spend” function and a single function constructing the “Spender” object; all actually injected failures happen by overwriting entries in a dict with default functions that implement aspects of the spending behavior. It’s rather unconventional, but it’s very easy now to add tests that modify basically any aspect of the process.

sipa force-pushed on Aug 6, 2020

sipa force-pushed on Aug 7, 2020

in src/validation.cpp:1536 in ff9b7e6e26 outdated

1533+    if (!txdata.m_spent_outputs_ready) {
1534+        std::vector<CTxOut> spent_outputs;
1535+        spent_outputs.reserve(tx.vin.size());
1536+
1537+        for (unsigned int i = 0; i < tx.vin.size(); ++i) {
1538+            const COutPoint &prevout = tx.vin[i].prevout;

jnewbery commented at 12:08 pm on August 7, 2020:

Any reason not to do a range-based for loop here?

0        for (const CTxIn& txin : tx.vin) {
1            const COutPoint &prevout = txin.prevout;

sipa commented at 11:25 pm on August 7, 2020:

Done.

in src/script/interpreter.h:230 in ff9b7e6e26 outdated

226@@ -153,6 +227,11 @@ class BaseSignatureChecker
227         return false;
228     }
229 
230+    virtual bool CheckSigSchnorr(const std::vector<unsigned char>& sig, const std::vector<unsigned char>& pubkey, SigVersion sigversion, const ScriptExecutionData& execdata) const

jnewbery commented at 2:41 pm on August 7, 2020:

There’s a naming inconsistency here. VerifySignature changed to VerifyECDSASignature/VerifySchnorrSignature, but CheckSig has changed to CheckSigSchnorr/CheckSig. Would it be better to name them CheckSchnorrSig/CheckECDSASig?

sipa commented at 11:25 pm on August 7, 2020:

Done.

in src/script/interpreter.cpp:1673 in ff9b7e6e26 outdated

1669+        sig.pop_back();
1670+    }
1671+    if (sig.size() != 64) return false;
1672+    uint256 sighash;
1673+    bool ret = SignatureHashSchnorr(sighash, execdata, *txTo, nIn, hashtype, sigversion, this->txdata);
1674+    if (!ret) return false;

jnewbery commented at 3:45 pm on August 7, 2020:

Is there any disadvantage to combining these two lines and eliminating the temporary return value:

0    if !(SignatureHashSchnorr(sighash, execdata, *txTo, nIn, hashtype, sigversion, this->txdata) return false;

sipa commented at 11:25 pm on August 7, 2020:

None. Done.

in test/functional/feature_taproot.py:185 in ff9b7e6e26 outdated

180+def default_merklebranch(ctx):
181+    """Default expression for "merklebranch": tapleaf.merklebranch."""
182+    return get(ctx, "tapleaf").merklebranch
183+
184+def default_controlblock(ctx):
185+    """Default expreesion for "controlblock": combine leafversion, negflag, pubkey_inner, merklebranch."""

instagibbs commented at 8:23 pm on August 7, 2020:

expression

sipa commented at 4:36 am on August 14, 2020:

Done.

sipa force-pushed on Aug 7, 2020

sipa commented at 11:28 pm on August 7, 2020: member

Rebased on top of #19620 (taproot outputs are now no longer WITNESS_UNKNOWN, as taproot spends would otherwise end up in the reject filter).

Also added some tests to verify pre-taproot activation behavior (rules enforced for standardness, but not for consensus).

in test/functional/feature_taproot.py:638 in 8692041ef5 outdated

633+        add_spender(spenders, "sighash/branched_codesep/right", tap=tap, leaf="branched_codesep", key=sec2, codeseppos=6, **common, inputs=[getter("sign"), b''], **SIGHASH_BITFLIP, **ERR_SCRIPTPATH_INVALID_SIG)
634+
635+    # Reusing the scripts above, test that various features affect the sighash.
636+    add_spender(spenders, "sighash/annex", tap=tap, leaf="pk_codesep", key=sec2, hashtype=hashtype, standard=False, **SINGLE_SIG, annex=bytes([ANNEX_TAG]), failure={"sighash": override(default_sighash, annex=None)}, **ERR_SCRIPTPATH_INVALID_SIG)
637+    add_spender(spenders, "sighash/script", tap=tap, leaf="pk_codesep", key=sec2, **common, **SINGLE_SIG, failure={"sighash": override(default_sighash, script_taproot=tap.leaves["codesep_pk"].script)}, **ERR_SCRIPTPATH_INVALID_SIG)
638+    add_spender(spenders, "sighash/leafver", tap=tap, leaf="pk_codesep", key=sec2, **common, **SINGLE_SIG, failure={"sighash": override(default_sighash, leafversion=0xc2)}, **ERR_SCRIPTPATH_INVALID_SIG)

instagibbs commented at 2:47 pm on August 10, 2020:

for leafversion anything other than 0xc0 should fail it, maybe just flip a bit of this too

sipa commented at 4:37 am on August 14, 2020:

Randomenized it.

in test/functional/feature_taproot.py:644 in 8692041ef5 outdated

639+    add_spender(spenders, "sighash/scriptpath", tap=tap, leaf="pk_codesep", key=sec2, **common, **SINGLE_SIG, failure={"sighash": override(default_sighash, leaf=None)}, **ERR_SCRIPTPATH_INVALID_SIG)
640+    add_spender(spenders, "sighash/keypath", tap=tap, key=sec1, **common, failure={"sighash": override(default_sighash, leaf="pk_codesep")}, **ERR_KEYPATH_INVALID_SIG)
641+
642+    # Test that invalid hashtypes don't work, both in key path and script path spends
643+    hashtype = lambda _: random.choice(VALID_SIGHASHES_TAPROOT)
644+    for invalid_hashtype in range(256):

instagibbs commented at 2:48 pm on August 10, 2020:

I’m getting some strange mutation results:

0--- a/src/script/interpreter.cpp
1+++ b/src/script/interpreter.cpp
2@@ -1497,7 +1497,7 @@ bool SignatureHashSchnorr(uint256& hash_out, const ScriptExecutionData& execdata
3     // Hash type
4     const uint8_t output_type = (hash_type == SIGHASH_DEFAULT) ? SIGHASH_ALL : (hash_type & SIGHASH_OUTPUT_MASK); // Default (no sighash byte) is equivalent to SIGHASH_ALL
5     const uint8_t input_type = hash_type & SIGHASH_INPUT_MASK;
6-    if (!(hash_type <= 0x03 || (hash_type >= 0x80 && hash_type <= 0x83))) return false;
7+    if (!(hash_type <= 0x04 || (hash_type >= 0x80 && hash_type <= 0x84))) return false;
8     ss << hash_type;

passes even though it’s definitely running the 0x04/0x84 cases. Anything beyond that seems to fail.

sipa commented at 4:40 am on August 14, 2020:

Very nice catch.

It took me a while: what happened is that the sighash code on the Python code (intentionally) supported invalid hashtypes, but implemented them slightly differently than what the C++ code did (after applying your mutation). Thus the signature for 0x04 and 0x84 (which map to output_type == 0, an invalid value) was constructed, but still rejected.

I’ve changed the Python side to be closer to the C++ one. I’m not entirely happy with that; I think it was useful to have an implementation that worked with a somewhat different principle, but on the other hand, it served its purpose.

in test/functional/feature_taproot.py:865 in 8692041ef5 outdated

860+    add_spender(spenders, "tapscript/pushmaxlimit", leaf="t25", **common, **SINGLE_SIG, failure={"leaf": "t26"}, **ERR_PUSH_LIMIT)
861+
862+    # == Test for sigops ratio limit ==
863+
864+    # Given a number n, and a public key pk, functions that produces a (CScript, sigops). Each script takes as
865+    # input a valid signature with the passed pk followed by a dummy, and will execute sigops signature checks.

instagibbs commented at 2:50 pm on August 10, 2020:

s/followed by a dummy/followed by a dummy push of bytes that are to be dropped/

sipa commented at 4:40 am on August 14, 2020:

Done.

in test/functional/feature_taproot.py:617 in 8692041ef5 outdated

612+            add_spender(spenders, "sighash/purepk", tap=tap, key=sec1, **common, **SIGHASH_BITFLIP, **ERR_KEYPATH_INVALID_SIG)
613+
614+            # Pubkey/P2PK script combination
615+            scripts = [("s0", CScript(random_checksig_style(pub2)))]
616+            tap = taproot_construct(pub1, scripts)
617+            add_spender(spenders, "sighash/keypath", tap=tap, key=sec1, **common, **SIGHASH_BITFLIP, **ERR_KEYPATH_INVALID_SIG)

instagibbs commented at 2:52 pm on August 10, 2020:

suggestion:

"sighash/keypath_{}".format(hashtype)

sipa commented at 4:41 am on August 14, 2020:

Done (with %x).

in test/functional/feature_taproot.py:618 in 8692041ef5 outdated

613+
614+            # Pubkey/P2PK script combination
615+            scripts = [("s0", CScript(random_checksig_style(pub2)))]
616+            tap = taproot_construct(pub1, scripts)
617+            add_spender(spenders, "sighash/keypath", tap=tap, key=sec1, **common, **SIGHASH_BITFLIP, **ERR_KEYPATH_INVALID_SIG)
618+            add_spender(spenders, "sighash/scriptpath", tap=tap, leaf="s0", key=sec2, **common, **SINGLE_SIG, **SIGHASH_BITFLIP, **ERR_SCRIPTPATH_INVALID_SIG)

instagibbs commented at 2:52 pm on August 10, 2020:

suggestion:

"sighash/scriptpath_{}".format(hashtype)

sipa commented at 4:41 am on August 14, 2020:

Done (with %x).

in test/functional/feature_taproot.py:646 in 8692041ef5 outdated

641+
642+    # Test that invalid hashtypes don't work, both in key path and script path spends
643+    hashtype = lambda _: random.choice(VALID_SIGHASHES_TAPROOT)
644+    for invalid_hashtype in range(256):
645+        if invalid_hashtype not in VALID_SIGHASHES_TAPROOT:
646+            add_spender(spenders, "sighash/keypath_unk_hashtype", tap=tap, key=sec1, hashtype=hashtype, failure={"hashtype": invalid_hashtype}, **ERR_KEYPATH_INVALID_SIG)

instagibbs commented at 2:53 pm on August 10, 2020:

suggestion:

"sighash/keypath_unk_hashtype_{}".format(invalid_hashtype)

sipa commented at 4:41 am on August 14, 2020:

Done (with %x).

in test/functional/feature_taproot.py:647 in 8692041ef5 outdated

642+    # Test that invalid hashtypes don't work, both in key path and script path spends
643+    hashtype = lambda _: random.choice(VALID_SIGHASHES_TAPROOT)
644+    for invalid_hashtype in range(256):
645+        if invalid_hashtype not in VALID_SIGHASHES_TAPROOT:
646+            add_spender(spenders, "sighash/keypath_unk_hashtype", tap=tap, key=sec1, hashtype=hashtype, failure={"hashtype": invalid_hashtype}, **ERR_KEYPATH_INVALID_SIG)
647+            add_spender(spenders, "sighash/scriptpath_unk_hashtype", tap=tap, leaf="pk_codesep", key=sec2, **SINGLE_SIG, hashtype=hashtype, failure={"hashtype": invalid_hashtype}, **ERR_SCRIPTPATH_INVALID_SIG)

instagibbs commented at 2:53 pm on August 10, 2020:

suggestion:

"sighash/scriptpath_unk_hashtype_{}".format(invalid_hashtype)

sipa commented at 4:41 am on August 14, 2020:

Done, with %x.

in test/functional/feature_taproot.py:941 in 8692041ef5 outdated

936+        add_spender(spenders, "unkver/bare", standard=False, tap=tap, leaf="bare_unkver", failure={"leaf": "bare_c0"}, **ERR_CLEANSTACK)
937+        add_spender(spenders, "unkver/return", standard=False, tap=tap, leaf="return_unkver", failure={"leaf": "return_c0"}, **ERR_OP_RETURN)
938+        add_spender(spenders, "unkver/undecodable", standard=False, tap=tap, leaf="undecodable_unkver", failure={"leaf": "undecodable_c0"}, **ERR_UNDECODABLE)
939+        add_spender(spenders, "unkver/bigpush", standard=False, tap=tap, leaf="bigpush_unkver", failure={"leaf": "bigpush_c0"}, **ERR_PUSH_LIMIT)
940+        add_spender(spenders, "unkver/1001push", standard=False, tap=tap, leaf="1001push_unkver", failure={"leaf": "1001push_c0"}, **ERR_STACK_SIZE)
941+        add_spender(spenders, "unkver/1001inputs", standard=False, tap=tap, leaf="bare_unkver", inputs=[b'' for _ in range(1001)], failure={"leaf": "bare_c0"}, **ERR_STACK_SIZE)

instagibbs commented at 3:04 pm on August 10, 2020:

take-or-leave-nit: just do [b''] * 1001

sipa commented at 4:41 am on August 14, 2020:

Ah yes, I forgot you could do that.

in test/functional/feature_taproot.py:973 in 8692041ef5 outdated

968+        add_spender(spenders, "opsuccess/return", standard=False, tap=tap, leaf="return_success", failure={"leaf": "return_nop"}, **ERR_OP_RETURN)
969+        add_spender(spenders, "opsuccess/undecodable", standard=False, tap=tap, leaf="undecodable_success", failure={"leaf": "undecodable_nop"}, **ERR_UNDECODABLE)
970+        add_spender(spenders, "opsuccess/undecodable_bypass", standard=False, tap=tap, leaf="undecodable_success", failure={"leaf": "undecodable_bypassed_success"}, **ERR_UNDECODABLE)
971+        add_spender(spenders, "opsuccess/bigpush", standard=False, tap=tap, leaf="bigpush_success", failure={"leaf": "bigpush_nop"}, **ERR_PUSH_LIMIT)
972+        add_spender(spenders, "opsuccess/1001push", standard=False, tap=tap, leaf="1001push_success", failure={"leaf": "1001push_nop"}, **ERR_STACK_SIZE)
973+        add_spender(spenders, "opsuccess/1001inputs", standard=False, tap=tap, leaf="bare_success", inputs=[b'' for _ in range(1001)], failure={"leaf": "bare_nop"}, **ERR_STACK_SIZE)

instagibbs commented at 3:06 pm on August 10, 2020:

take-or-leave-nit: just do [b''] * 1001

sipa commented at 4:41 am on August 14, 2020:

Done.

in test/functional/feature_taproot.py:1104 in 8692041ef5 outdated

1002+    # Verify that OP_CHECKSIGADD wasn't accidentally added to pre-taproot validation logic.
1003+    for p2sh in [False, True]:
1004+        for witv0 in [False, True]:
1005+            for hashtype in VALID_SIGHASHES_ECDSA + [random.randrange(0x04, 0x80), random.randrange(0x84, 0x100)]:
1006+                standard = hashtype in VALID_SIGHASHES_ECDSA and (p2sh or witv0)
1007+                add_spender(spenders, "legacy/nocsa", hashtype=hashtype, p2sh=p2sh, witv0=witv0, standard=standard, script=CScript([OP_IF, OP_11, pubkey1, OP_CHECKSIGADD, OP_12, OP_EQUAL, OP_ELSE, pubkey1, OP_CHECKSIG, OP_ENDIF]), key=eckey1, sigops_weight=4-3*witv0, inputs=[getter("sign"), b''], failure={"inputs": [getter("sign"), b'\x01']}, **ERR_UNDECODABLE)

instagibbs commented at 3:09 pm on August 10, 2020:

nice script for this check

sipa commented at 4:42 am on August 14, 2020:

thanks I wrote it myself

sipa force-pushed on Aug 14, 2020

instagibbs commented at 1:37 pm on August 14, 2020: member

utACK https://github.com/bitcoin/bitcoin/pull/17977/commits/b0d2a3a788222fa6770ffe9eee132f829199275f the non-sighash changes, I think there still might be issues on that front since tests are failing

0AssertionError: Missing error message 'Signature must be zero for failed CHECK(MULTI)SIG operation' from block response '(None)': applic/scriptpath,sighash/keypath_unk_hashtype_90,sighash/scriptpath_unk_hashtype_80*

sipa force-pushed on Aug 14, 2020

sipa commented at 5:32 pm on August 14, 2020: member

@instagibbs … and that was an actual bug in the sighash code. It wasn’t rejecting 0x80 as hashtype.

Fixed:

0--- a/src/script/interpreter.cpp
1+++ b/src/script/interpreter.cpp
2@@ -1497,7 +1497,7 @@ bool SignatureHashSchnorr(uint256& hash_out, const ScriptExecutionData& execdata
3     // Hash type
4     const uint8_t output_type = (hash_type == SIGHASH_DEFAULT) ? SIGHASH_ALL : (hash_type & SIGHASH_OUTPUT_MASK); // Default (no sighash byte) is equivalent to SIGHASH_ALL
5     const uint8_t input_type = hash_type & SIGHASH_INPUT_MASK;
6-    if (!(hash_type <= 0x03 || (hash_type >= 0x80 && hash_type <= 0x83))) return false;
7+    if (!(hash_type <= 0x03 || (hash_type >= 0x81 && hash_type <= 0x83))) return false;

in src/script/interpreter.cpp:1486 in c18ba5afa6 outdated

1498+        break;
1499+    default:
1500+        assert(false);
1501+    }
1502+    assert(in_pos < tx_to.vin.size());
1503+    assert(cache != nullptr && cache->m_bip341_ready && cache->m_spent_outputs_ready);

kallewoof commented at 2:39 am on August 20, 2020:

If I want to taproot-sign a transaction, it will not have any ScriptWitness data when I try to obtain the signature hash, which means m_bip341_ready will not be set after the PrecomputedTransactionData::Init() call has been made.

This means I have to put in junk data in the vin’s scriptwitness in order to obtain the sighash, which seems off.

instagibbs commented at 7:11 pm on August 20, 2020:

Will you be using a cache when signing a tx? I figured no.

kallewoof commented at 3:17 am on August 21, 2020:

I need the sighash to sign the transaction, and I need the cache to get the sighash.

sipa commented at 3:39 am on August 21, 2020:

There is no signing code yet, so this may go in a number of different ways, but I was imagining that the cache would indeed be used for signing as well, as it becomes increasingly inconvenient to pass all arguments (including all spent UTXOs now!) along down into the signing function.

In fact, I think after the change to use the cache to pass that information along, we can stop passing scriptPubKey/amount/txFrom to SignSignature… but that’s for much later. @kallewoof It’s indeed ugly in the signing case that the scriptWitness is used to determine if a transaction is a witness input. I’ll change that for now to just default to BIP143 caching unless it’s clearly a BIP341 spend, instead of relying on there being a non-empty witness.

kallewoof commented at 3:46 am on August 21, 2020:

@sipa I worked around it on my end, so feel free to leave it as is until a decision is made on how signing should work!

instagibbs commented at 5:31 pm on August 22, 2020:

oh I was having a special brain moment thinking it was a conditional check on if the cache existed.

in src/script/interpreter.cpp:1462 in c18ba5afa6 outdated

1467 
1468 template <class T>
1469 PrecomputedTransactionData::PrecomputedTransactionData(const T& txTo)
1470 {
1471-    Init(txTo);
1472+    Init(txTo, {});

luke-jr commented at 8:06 pm on August 24, 2020:

I think we should probably require spent_outputs in the constructor. That gets us a compile-time error rather than a runtime surprise, if any code is missing an update.

Aside from tests (which have a mere 4 uses), it’s only used in libbitcoinconsensus, where the omission is arguably a bug (impossible to use existing APIs for Taproot verification).

sipa commented at 1:30 am on August 28, 2020:

I would very much like that, but I think we inevitably need a few states in it at least.

The PrecomputedTransactionData objects used for block validation are constructed once up front, and then initialized simultaneously with other checks in CheckInputScripts. This means they need some sort of “uninitialized” state which can detect incorrect use before initialization. A cleaner solution would be to move the construction of these objects out of CheckInputScripts and do it up front, so they can be constructed with all available information once and for all. I think that makes sense, but it’s a bigger change to validation logic that I’d like to avoid in this PR.

The other reason is indeed libconsensus, which has no API for taproot validation. There is also no problem, as it doesn’t expose a taproot validation flag (yet). A future extension to it would add a new call that lets you pass in the spent UTXOs, and let you enable taproot validation. But as of right now, changing things to require the UTXOs whenever initializing the PrecomputedTransactionData would mean that libconsensus would need to construct mock UTXOs and pass those in… which I think is worse than having an explicit uninitialized state that’d trigger an error on misuse.

in src/script/interpreter.cpp:1354 in c18ba5afa6 outdated

1348@@ -1258,65 +1349,207 @@ class CTransactionSignatureSerializer
1349     }
1350 };
1351 
1352+/** Compute the (single) SHA256 of the concatenation of all prevouts of a tx. */

luke-jr commented at 11:13 pm on August 24, 2020:

Please rename things that change meaning. eg, GetPrevoutSHA256

JeremyRubin commented at 8:18 am on August 25, 2020:

#19601

sipa commented at 1:48 am on August 28, 2020:

Done, by virtue of rebasing on master which includes #19601 now.

in src/script/interpreter.cpp:1429 in c18ba5afa6 outdated

1432+    for (size_t inpos = 0; inpos < txTo.vin.size(); ++inpos) {
1433+        if (!txTo.vin[inpos].scriptWitness.IsNull()) {
1434+            if (m_spent_outputs_ready && m_spent_outputs[inpos].scriptPubKey.size() == 2 + WITNESS_V1_TAPROOT_SIZE &&
1435+                m_spent_outputs[inpos].scriptPubKey[0] == OP_1) {
1436+                // Treat every native witness v1 spend as a Taproot spend. This only works if spent_outputs was
1437+                // provided as well, but if it wasn't, actual validation will fail anyway.

luke-jr commented at 11:19 pm on August 24, 2020:

(Review TODO: Check that this is actually true, even when no signature checking occurs.)

sipa commented at 1:31 am on August 28, 2020:

If no signature checking occurs none of the code in interpreter.cpp matters.

in src/script/interpreter.h:180 in c18ba5afa6 outdated

179-    BASE = 0,
180-    WITNESS_V0 = 1,
181+    BASE = 0,        //!< Bare scripts and P2SH redeemscripts; see BIP 16
182+    WITNESS_V0 = 1,  //!< Witness v0 (P2WPKH and P2WSH); see BIP 141
183+    TAPROOT = 2,     //!< Witness v1 with non-P2SH 32 byte program (Taproot), key path spending; see BIP 341
184+    TAPSCRIPT = 3,   //!< Witness v1 with non-P2SH 32 byte program (Taproot), script path spending, leaf version 0xc0 (Tapscript); see BIP 342

luke-jr commented at 11:56 pm on August 24, 2020:

Technically, Tapscript itself is a form of P2SH, just not BIP16 P2SH.

The comment here confused me. Perhaps “non-BIP16-wrapped”?

sipa commented at 0:31 am on August 28, 2020:

I tend to think of P2SH as referring to BIP16 based script hashing specifically, not the abstract concept.

And arguably, it’s not exactly true that taproot script path spending is paying to a script hash - it’s paying to a tweaked public key (where the tweak happens to be indirectly a hash of a script).

sipa commented at 1:48 am on August 28, 2020:

Addressed by changing the comments to “Witness v1 with 32-byte program, not BIP16 P2SH-wrapped, …”

in configure.ac:1648 in c18ba5afa6 outdated

1609@@ -1610,7 +1610,7 @@ if test x$need_bundled_univalue = xyes; then
1610   AC_CONFIG_SUBDIRS([src/univalue])
1611 fi
1612 
1613-ac_configure_args="${ac_configure_args} --disable-shared --with-pic --enable-benchmark=no --with-bignum=no --enable-module-recovery"
1614+ac_configure_args="${ac_configure_args} --disable-shared --with-pic --enable-benchmark=no --with-bignum=no --enable-module-recovery --enable-module-schnorrsig --enable-experimental"

luke-jr commented at 0:15 am on August 25, 2020:

Should this be non-experimental before merging?

gmaxwell commented at 0:14 am on August 28, 2020:

I don’t think so: It probably shouldn’t be marked non-experimental until after it deployed for activation in Bitcoin because it wouldn’t be good to encourage third party users of it while it is still easy to make incompatible changes in Bitcoin (e.g. as was just done. :) )

sipa commented at 0:19 am on August 28, 2020:

Or, maybe more likely: the API in libsecp256k1 may change still significantly in the near future (e.g. support for variable-length messages, batch validation, …) even after we treat the scheme itself final.

in src/script/interpreter.h:262 in c18ba5afa6 outdated

262 
263 public:
264     GenericTransactionSignatureChecker(const T* txToIn, unsigned int nInIn, const CAmount& amountIn) : txTo(txToIn), nIn(nInIn), amount(amountIn), txdata(nullptr) {}
265     GenericTransactionSignatureChecker(const T* txToIn, unsigned int nInIn, const CAmount& amountIn, const PrecomputedTransactionData& txdataIn) : txTo(txToIn), nIn(nInIn), amount(amountIn), txdata(&txdataIn) {}
266-    bool CheckSig(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const override;
267+    bool CheckECDSASignature(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const override;

luke-jr commented at 0:18 am on August 25, 2020:

Suggest moving CheckSig -> CheckECDSASignature rename to a dedicated commit

sipa commented at 1:48 am on August 28, 2020:

Good idea, done.

in src/pubkey.h:218 in c18ba5afa6 outdated

213+public:
214+    XOnlyPubKey(const uint256& in) : m_keydata(in) {}
215+
216+    /** Verify a 64-byte Schnorr signature.
217+     *
218+     * If the signature is not 64 bytes, or the public key is not fully valid, false is returned.

luke-jr commented at 0:19 am on August 25, 2020:

nit: “is not exactly 64 bytes”

sipa commented at 1:49 am on August 28, 2020:

Done.

in src/script/interpreter.cpp:1662 in c18ba5afa6 outdated

1658+{
1659+    std::vector<unsigned char> sig(sig_in);
1660+    if (sig.empty()) return false;
1661+
1662+    if (pubkey_in.size() != 32) return false;
1663+    XOnlyPubKey pubkey{uint256(pubkey_in)};

luke-jr commented at 0:26 am on August 25, 2020:

Suggest moving the size check and uint256 cast into XOnlyPubKey construction & IsValid, like CheckECDSASignature does

sipa commented at 10:58 pm on August 27, 2020:

I’m not sure about this. BIP340 public keys are just 32-byte arrays, not abstract objects that require serialization. So there shouldn’t be a concept of an “invalid public key” that’s distinct from signature validation failure, and I’d prefer not to introduce such a concept to XOnlyPubKey.

Arguably, this could be an assert(pubkey_in.size() == 32); even. If a different length is used, it’s a code error.

sipa commented at 1:50 am on August 28, 2020:

Made a few changes here, including passing pubkey/signature as a Span (which means one less useless vector copy during signature validation). The size is now asserted to be 32 bytes (both in XOnlyPubKey (where it’s required), and in CheckSchnorrSignature (which makes decisions based on the length).

in src/script/sigcache.cpp:25 in c18ba5afa6 outdated

21@@ -22,8 +22,9 @@ namespace {
22 class CSignatureCache
23 {
24 private:
25-     //! Entries are SHA256(nonce || signature hash || public key || signature):
26-    CSHA256 m_salted_hasher;
27+     //! Entries are SHA256(nonce || 'E' or 'S' || signature hash || public key || signature):

luke-jr commented at 0:34 am on August 25, 2020:

Inaccuracy in previous comment aside, seems like it would be best to correct the new one (with 31 null bytes after E/S)

JeremyRubin commented at 8:26 am on August 25, 2020:

the previous one is not incorrect AFIACT, because the nonce is just required to be 64 bytes long with at least 256 bits of entropy, which it has (nonce, signature hash, and public key are not variable names).

sipa commented at 1:50 am on August 28, 2020:

Fixed by adding “31 zero bytes” explicitly in the comment.

in src/script/sigcache.cpp:44 in c18ba5afa6 outdated

42+        // 'S' for Schnorr (followed by 0 bytes).
43+        static const unsigned char PADDING_ECDSA[32] = {'E'};
44+        static const unsigned char PADDING_SCHNORR[32] = {'S'};
45+        m_salted_hasher_ecdsa.Write(nonce.begin(), 32);
46+        m_salted_hasher_ecdsa.Write(PADDING_ECDSA, 32);
47+        m_salted_hasher_schnorr.Write(nonce.begin(), 32);

luke-jr commented at 0:35 am on August 25, 2020:

Probable premature optimisation: Copy m_salted_hasher_ecdsa before adding the padding?

JeremyRubin commented at 8:23 am on August 25, 2020:

it only happens on startup right now, so :man_shrugging:

sipa commented at 9:39 pm on August 27, 2020:

@luke-jr SHA256’s blocksize is 64 bytes; if you’ve written less than that, there isn’t anything to gain from duplicating the state (also, as @JeremyRubin says, it only runs once on startup).

in src/script/interpreter.cpp:426 in c18ba5afa6 outdated

423+        return EvalChecksigPreTapscript(sig, pubkey, pbegincodehash, pend, flags, checker, sigversion, serror, success);
424+    case SigVersion::TAPSCRIPT:
425+        return EvalChecksigTapscript(sig, pubkey, execdata, flags, checker, sigversion, serror, success);
426+    case SigVersion::TAPROOT:
427+        // Key path spending in Taproot has no script, so this is unreachable.
428+        break;

luke-jr commented at 4:08 am on August 25, 2020:

Prefer assert(false); for unreachable conditions

sipa commented at 9:38 pm on August 27, 2020:

This case will cause the assert(false) below to be triggered. Is that sufficient?

in src/script/interpreter.cpp:1239 in c18ba5afa6 outdated

1234@@ -1146,6 +1235,8 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript&
1235             // Size limits
1236             if (stack.size() + altstack.size() > MAX_STACK_SIZE)
1237                 return set_error(serror, SCRIPT_ERR_STACK_SIZE);
1238+
1239+            ++opcode_pos;

luke-jr commented at 4:25 am on August 25, 2020:

If we ever had a continue, this would get skipped. Seems like a code footgun.

We could replace while (pc < pend) with for ( ; pc < pend; ++opcode_pos) perhaps?

sipa commented at 1:51 am on August 28, 2020:

I think there are bigger footguns already if there ever was a continue (like the stack size check just above), but regardless: good idea, done.

in src/script/interpreter.cpp:1122 in c18ba5afa6 outdated

1117+                break;
1118+
1119                 case OP_CHECKMULTISIG:
1120                 case OP_CHECKMULTISIGVERIFY:
1121                 {
1122+                    if (sigversion == SigVersion::TAPSCRIPT) return set_error(serror, SCRIPT_ERR_DISABLED_OPCODE);

luke-jr commented at 4:30 am on August 25, 2020:

All existing disabled opcodes trigger SCRIPT_ERR_DISABLED_OPCODE unconditionally, even if their branch isn’t taken. Do we want to preserve that for CHECKMULTISIG? If not, do we still want to use the same error code?

sipa commented at 1:54 am on August 28, 2020:

Nice catch, I didn’t realize there was a discrepancy here. As BIP342 explicitly states that CMS/CMSV behave as OP_RETURN, namely failing the script if executed, I’m not going to change semantics, but I’ve changed it to have a separate dedicated error code.

in src/policy/policy.cpp:248 in c18ba5afa6 outdated

243+        // Check MAX_STANDARD_TAPSCRIPT_STACK_ITEM_SIZE policy limit for Taproot spends.
244+        if (witnessversion == 1 && witnessprogram.size() == WITNESS_V1_TAPROOT_SIZE && !p2sh) {
245+            // Taproot spend (non-P2SH-wrapped, version 1, witness program size 32; see BIP 341)
246+            auto stack = MakeSpan(tx.vin[i].scriptWitness.stack);
247+            if (stack.size() >= 2 && !stack.back().empty() && stack.back()[0] == ANNEX_TAG) {
248+                // Drop annex

luke-jr commented at 4:42 am on August 25, 2020:

We should probably policy-reject annex here for now?

sipa commented at 9:13 pm on August 27, 2020:

They are policy-invalid, though it’s implemented as a script verification flag (SCRIPT_VERIFY_DISCOURAGE_UNKNOWN_ANNEX). Any particular reason why you prefer it here?

luke-jr commented at 10:57 pm on August 27, 2020:

Less expensive/faster to reject?

sipa commented at 1:57 am on August 28, 2020:

My thinking was initially that there wouldn’t be a performance benefit, as taproot execution to the point where the annex is reached is very cheap - but then again, there may be a valid, expensive input, and another one with an annex.

I’ve moved the annex policy rule to policy/policy.cpp (which also removes a validation flag).

This makes me wonder if we’d want the same with unknown leaf versions, but a reason not to may be that that would mean putting knowledge about defined/valid leaf versions in two places. So I’m going to stick with the rule “implement it where it’s simplest”, which means annex here, and leaf versions there.

luke-jr commented at 4:49 am on August 25, 2020: member

Without having fully read the latest BIPs, some code review.

Did not look at tests (final 2 commits).

fanquake referenced this in commit f8462a6d27 on Aug 25, 2020

DrahtBot added the label Needs rebase on Aug 25, 2020

sidhujag referenced this in commit 16d841beaa on Aug 25, 2020

sipa force-pushed on Aug 28, 2020

sipa commented at 2:15 am on August 28, 2020: member

Rebased, updated to latest https://github.com/bitcoin-core/secp256k1/pull/558 (including the even-R BIP change), and addressed a number of @luke-jr’s comments above.

I made one additional somewhat significant change on top, the signature/pubkey is now passed into validation routines using a Span (which means one less vector copy per script). A change like this would also make sense for ECDSA, but isn’t done here yet.

So far I’ve been eagerly rewriting commits to address comments without good overview of the code history, but as the code stabilizes, I think it makes sense to stop doing so. My idea is that at some point (perhaps as soon as the libsecp256k1 changes are merged), I’ll close this PR, and open 2 different new ones - one with just fixups, and one with the final squashed state (like #7910 and #8149 for segwit). Thoughts?

DrahtBot removed the label Needs rebase on Aug 28, 2020

jnewbery commented at 7:20 am on August 28, 2020: member

My idea is that at some point (perhaps as soon as the libsecp256k1 changes are merged), I’ll close this PR, and open 2 different new ones - one with just fixups, and one with the final squashed state (like #7910 and #8149 for segwit). Thoughts?

Sounds good to me!

[aside: I often get unicorns when loading this PR on mobile, so starting afresh would be useful if only to make interacting with the PR more manageable]

sipa force-pushed on Aug 29, 2020

in test/functional/feature_taproot.py:745 in 619ceebd4d outdated

740+    assert_equal(len(CScriptNum.encode(CScriptNum(OVERSIZE_NUMBER-1))), 5)
741+
742+    big_choices = []
743+    big_scriptops = []
744+    for i in range(1000):
745+        r = random.randrange(4)

instagibbs commented at 1:39 am on August 29, 2020:

r = random.randrange(len(pubs)) ?

sipa commented at 2:16 am on August 29, 2020:

Done.

in test/functional/feature_taproot.py:755 in 619ceebd4d outdated

750+    def big_spend_inputs(ctx):
751+        """Helper function to construct the script input for t33/t34 below."""
752+        # Instead of signing 999 times, precompute signatures for every (key, hashtype) combination
753+        sigs = {}
754+        for ht in VALID_SIGHASHES_TAPROOT:
755+            for k in range(4):

instagibbs commented at 1:40 am on August 29, 2020:

for k in range(len(pubs)): ?

sipa commented at 2:17 am on August 29, 2020:

Done.

instagibbs commented at 2:00 am on August 29, 2020: member

Agreed on proposed PR strategy.

Did light review of the rebase.

sipa force-pushed on Aug 29, 2020

DrahtBot added the label Needs rebase on Sep 1, 2020

in src/script/interpreter.cpp:1418 in 84ec870859 outdated

1421     }
1422 
1423-    m_ready = true;
1424+    // Determine which precomputation-impacting features this transaction uses.
1425+    bool uses_bip143 = false;
1426+    bool uses_bip341 = false;

Kixunil commented at 2:59 pm on September 2, 2020:

Since these names look so similar (made me confused), maybe use names without numbers to distinguish them better? Or something like uses_bip341_taproot?

sipa commented at 3:52 am on September 4, 2020:

Good idea, done.

in src/script/interpreter.cpp:1684 in a6ca5080c4 outdated

1680+    int path_len = (control.size() - TAPROOT_CONTROL_BASE_SIZE) / TAPROOT_CONTROL_NODE_SIZE;
1681+    XOnlyPubKey p{uint256(std::vector<unsigned char>(control.begin() + 1, control.begin() + TAPROOT_CONTROL_BASE_SIZE))};
1682+    XOnlyPubKey q{uint256(program)};
1683+    uint256 k = (CHashWriter(HASHER_TAPLEAF) << uint8_t(control[0] & TAPROOT_LEAF_MASK) << script).GetSHA256();
1684+    for (int i = 0; i < path_len; ++i) {
1685+        CHashWriter ss_branch = HASHER_TAPBRANCH;

fjahr commented at 3:36 pm on September 2, 2020:

nit if you retouch

0    const int path_len = (control.size() - TAPROOT_CONTROL_BASE_SIZE) / TAPROOT_CONTROL_NODE_SIZE;
1    const XOnlyPubKey p{uint256(std::vector<unsigned char>(control.begin() + 1, control.begin() + TAPROOT_CONTROL_BASE_SIZE))};
2    const XOnlyPubKey q{uint256(program)};
3    uint256 k = (CHashWriter(HASHER_TAPLEAF) << uint8_t(control[0] & TAPROOT_LEAF_MASK) << script).GetSHA256();
4    for (int i = 0; i < path_len; ++i) {
5        CHashWriter ss_branch{HASHER_TAPBRANCH};

sipa commented at 3:52 am on September 4, 2020:

Done.

in src/pubkey.cpp:184 in a6ca5080c4 outdated

180@@ -181,6 +181,13 @@ bool XOnlyPubKey::VerifySchnorr(const uint256& msg, Span<const unsigned char> si
181     return secp256k1_schnorrsig_verify(secp256k1_context_verify, sigbytes.data(), msg.begin(), &pubkey);
182 }
183 
184+bool XOnlyPubKey::CheckPayToContract(const XOnlyPubKey& base, const uint256& hash, bool negated) const

fjahr commented at 3:38 pm on September 2, 2020:

0bool XOnlyPubKey::CheckPayToContract(const XOnlyPubKey& base, const uint256& hash, const bool negated) const

in src/pubkey.h:223 in a6ca5080c4 outdated

219@@ -220,8 +220,10 @@ class XOnlyPubKey {
220      * If the signature is not exactly 64 bytes, false is returned.
221      */
222     bool VerifySchnorr(const uint256& msg, Span<const unsigned char> sigbytes) const;
223+    bool CheckPayToContract(const XOnlyPubKey& base, const uint256& hash, bool sign) const;

fjahr commented at 3:39 pm on September 2, 2020:

(renaming suggested to be consistent with the name in the implementation)

0    bool CheckPayToContract(const XOnlyPubKey& base, const uint256& hash, const bool negated) const;

sipa commented at 3:53 am on September 4, 2020:

Changed to parity in both .h and .cpp, as that’s the name of the libsecp256k1 function.

fjahr commented at 4:13 pm on September 2, 2020: member

Minor suggestions from reviewing a6ca5080c4ac550dc74330e89c44d3eb268d4eb5.

I don’t see an issue with the proposed strategy if it doesn’t create too much more work for you maintaining both. As the code stabilizes reviewing changes with range diffs might be bearable as well and I am not sure what I would use the history for. But I also wasn’t reviewing Segwit so I can’t speak from experience.

in src/script/interpreter.cpp:1803 in 84ec870859 outdated

1801 }
1802 
1803-static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion, const std::vector<unsigned char>& program, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* serror)
1804+static bool VerifyTaprootCommitment(const std::vector<unsigned char>& control, const std::vector<unsigned char>& program, const CScript& script, uint256* tapleaf_hash)
1805+{
1806+    int path_len = (control.size() - TAPROOT_CONTROL_BASE_SIZE) / TAPROOT_CONTROL_NODE_SIZE;

Kixunil commented at 4:27 pm on September 2, 2020:

Would moving the control.size() check here be less of a footgun?

sipa commented at 0:31 am on September 4, 2020:

I kept it out so that invalid control size can be its own error code. It’s sanity checked before this function is invoked.

Kixunil commented at 4:46 pm on September 7, 2020:

Good point.

in src/script/interpreter.h:215 in 84ec870859 outdated

214+static constexpr uint8_t TAPROOT_LEAF_MASK = 0xfe;
215+static constexpr uint8_t TAPROOT_LEAF_TAPSCRIPT = 0xc0;
216+static constexpr size_t TAPROOT_CONTROL_BASE_SIZE = 33;
217+static constexpr size_t TAPROOT_CONTROL_NODE_SIZE = 32;
218+static constexpr size_t TAPROOT_CONTROL_MAX_NODE_COUNT = 128;
219+static constexpr size_t TAPROOT_CONTROL_MAX_SIZE = TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * TAPROOT_CONTROL_MAX_NODE_COUNT;

Kixunil commented at 5:56 pm on September 2, 2020:

This is different from BIP114 which says the max size of path must be below 1024, however 32 * 128 == 4096

Is this correct?

I suppose BIP114 limit is superseded by BIP341 (which I find reasonable) but asking to be sure. (Perhaps BIP114 should be updated?)

sipa commented at 0:34 am on September 4, 2020:

This is an implementation of BIP340/341/342, not BIP114. BIP341 specifies a max depth of 128 nodes, and gives a rationale why.

BIP114 is a completely independent proposal, which BIP341 took some inspiration from, but it isn’t compatible with in any way. You could suggest to BIP114’s author that it may be retracted, but in theory, they’re free to pursue activation of that as an alternative to, or in addition to, BIP341.

in test/functional/rpc_blockchain.py:152 in 84ec870859 outdated

145@@ -146,7 +146,19 @@ def _test_getblockchaininfo(self):
146                         'possible': True,
147                     },
148                 },
149-                'active': False}
150+                'active': False
151+            },
152+            'taproot': {
153+                'type': 'bip9',

Kixunil commented at 7:58 pm on September 2, 2020:

Why not BIP8?

sipa commented at 0:37 am on September 4, 2020:

I think there is a bit of a misconception here: this doesn’t, and doesn’t intended to, implement mainchain activation. That’s still up for discussion, and BIP341 states that activation is TBD.

BIP9 is chosen here for regtest activation as it’s easiest in the current codebase, so that the consensus changes can be tested. Mainchain activation will probably follow in a separate PR, possibly in a different version (the consensus changes usually go in a major release, with activation in a later minor release once there is community consensus on that).

Kixunil commented at 8:30 pm on September 2, 2020: none

Concept ACK

I’ve reviewed most of the code and it’s very good. The biggest mistake IMO is using BIP9 instead of BIP8. I wouldn’t be surprised at all if there’s opposition to Taproot due to its privacy nature.

I’ve written down a detailed review for the curious.

in src/script/standard.h:132 in 8859e78b6a outdated

128@@ -129,6 +129,7 @@ enum class TxoutType {
129     NULL_DATA, //!< unspendable OP_RETURN script that carries data
130     WITNESS_V0_SCRIPTHASH,
131     WITNESS_V0_KEYHASH,
132+    WITNESS_V1_TAPROOT,

ariard commented at 11:25 pm on September 2, 2020:

Should be referenced in CTxDestination typedef.

sipa commented at 3:52 am on September 4, 2020:

Done.

in src/script/interpreter.cpp:1655 in 84ec870859 outdated

1651 }
1652 
1653+template <class T>
1654+bool GenericTransactionSignatureChecker<T>::CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey_in, SigVersion sigversion, const ScriptExecutionData& execdata) const
1655+{
1656+    if (sig.empty()) return false;

ariard commented at 11:28 pm on September 2, 2020:

I don’t get a feature_taproot.py failure for this ?

 0diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
 1index 053df47a2..02de07bc5 100644
 2--- a/src/script/interpreter.cpp
 3+++ b/src/script/interpreter.cpp
 4@@ -1652,7 +1652,7 @@ bool GenericTransactionSignatureChecker<T>::CheckECDSASignature(const std::vecto
 5 template <class T>
 6 bool GenericTransactionSignatureChecker<T>::CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey_in, SigVersion sigversion, const ScriptExecutionData& execdata) const
 7 {
 8-    if (sig.empty()) return false;
 9+    if (sig.empty()) return true;
10     if (pubkey_in.size() != 32) return false;
11 
12     XOnlyPubKey pubkey{pubkey_in};

instagibbs commented at 1:49 am on September 3, 2020:

Seems like tapscript/emptysigs/checksig aka script t12 should cover this case? Confirmed it somehow doesn’t.

sipa commented at 5:26 am on September 4, 2020:

Great catch. There were no tests at all with signatures with unusual lengths, so I’ve added a number of them. tapscript/emptysigs/checksig didn’t exercise this, as empty signatures are dealt with specially in script path spending. I’ve added comments to explain this.

in src/script/interpreter.cpp:1656 in 84ec870859 outdated

1652 
1653+template <class T>
1654+bool GenericTransactionSignatureChecker<T>::CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey_in, SigVersion sigversion, const ScriptExecutionData& execdata) const
1655+{
1656+    if (sig.empty()) return false;
1657+    if (pubkey_in.size() != 32) return false;

ariard commented at 11:32 pm on September 2, 2020:

Idem, is this part of the code tested non-deterministically ?

 0diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
 1index 053df47a2..fcaacc152 100644
 2--- a/src/script/interpreter.cpp
 3+++ b/src/script/interpreter.cpp
 4@@ -1653,7 +1653,7 @@ template <class T>
 5 bool GenericTransactionSignatureChecker<T>::CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey_in, SigVersion sigversion, const ScriptExecutionData& execdata) const
 6 {
 7     if (sig.empty()) return false;
 8-    if (pubkey_in.size() != 32) return false;
 9+    if (pubkey_in.size() != 32) return true;
10 
11     XOnlyPubKey pubkey{pubkey_in};

sipa commented at 5:28 am on September 4, 2020:

I’ve changed this to an assert. You can’t do BIP340 signature verification with keys of length different than 32, and as both call sites already enforce this, it seems better to leave the responsibility for key length checking there.

in src/script/interpreter.cpp:1665 in 84ec870859 outdated

1661+    uint8_t hashtype = SIGHASH_DEFAULT;
1662+    if (sig.size() == 65) {
1663+        hashtype = SpanPopBack(sig);
1664+        if (hashtype == SIGHASH_DEFAULT) return false;
1665+    }
1666+    if (sig.size() != 64) return false;

ariard commented at 11:41 pm on September 2, 2020:

Again don’t get failure in feature_taproot.py ? What should be the prefix something like sighash/keypath_* ?

 0diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
 1index 053df47a2..24ba2ac41 100644
 2--- a/src/script/interpreter.cpp
 3+++ b/src/script/interpreter.cpp
 4@@ -1662,7 +1662,7 @@ bool GenericTransactionSignatureChecker<T>::CheckSchnorrSignature(Span<const uns
 5         hashtype = SpanPopBack(sig);
 6         if (hashtype == SIGHASH_DEFAULT) return false;
 7     }
 8-    if (sig.size() != 64) return false;
 9+    if (sig.size() != 64) return true;
10     uint256 sighash;
11     if (!SignatureHashSchnorr(sighash, execdata, *txTo, nIn, hashtype, sigversion, this->txdata)) return false;
12     return VerifySchnorrSignature(sig, pubkey, sighash);

sipa commented at 5:29 am on September 4, 2020:

I’ve restructed this a bit. It should be covered by new tests.

in src/script/interpreter.cpp:1875 in 84ec870859 outdated

1873+            return set_success(serror);
1874+        } else {
1875+            // Script path spending (stack size is >1 after removing optional annex)
1876+            const valtype& control = SpanPopBack(stack);
1877+            const valtype& script_bytes = SpanPopBack(stack);
1878+            scriptPubKey = CScript(script_bytes.begin(), script_bytes.end());

ariard commented at 11:46 pm on September 2, 2020:

Technically this should be called witnessScript (BIP141) or just script (BIP341) ? scriptPubKey is a bit confusing as this is fed from the witness?

sipa commented at 5:29 am on September 4, 2020:

I’ve added an extra commit that renames the variable. It was just wrong to call it scriptPubKey.

in src/script/interpreter.cpp:1817 in 84ec870859 outdated

1804+static bool VerifyTaprootCommitment(const std::vector<unsigned char>& control, const std::vector<unsigned char>& program, const CScript& script, uint256* tapleaf_hash)
1805+{
1806+    int path_len = (control.size() - TAPROOT_CONTROL_BASE_SIZE) / TAPROOT_CONTROL_NODE_SIZE;
1807+    XOnlyPubKey p{uint256(std::vector<unsigned char>(control.begin() + 1, control.begin() + TAPROOT_CONTROL_BASE_SIZE))};
1808+    XOnlyPubKey q{uint256(program)};
1809+    uint256 k = (CHashWriter(HASHER_TAPLEAF) << uint8_t(control[0] & TAPROOT_LEAF_MASK) << script).GetSHA256();

ariard commented at 0:03 am on September 3, 2020:

I tried to tweak serializers to test that compact_size(size of s) is well-committed in tapleaf hash. Of course I got failure far earlier, so I was wondering if there is a way to test this in isolation ? I guess that’s useless as our script ser is already used at anytime, so any error would be more than obvious.

sipa commented at 1:03 am on September 4, 2020:

Given that this is covered by a hash, this is sort of implicitly tested. The functional tests reimplement the (hopefully correctly, but please review) serialization/leaf hashing scheme, and there are tests that if the wrong leaf is used, spending fails.

The fact that there is a hash around this whole computation means that it’s either right or wrong, and there is little avenue for testing small tweaks to the code - any change will break the whole thing immediately.

I’m happy to try adding a test that explicitly tests spending with an incorrectly hashed leaf, but I don’t think it adds much.

ariard commented at 7:16 pm on September 4, 2020:

Okay, bookmarked to look on functional tests serializer correctness during next round of review.

I’m happy to try adding a test that explicitly tests spending with an incorrectly hashed leaf, but I don’t think it adds much.

I think we agree here. I expect serialization correctness to be already covered on its own but not that we test any new invocation of them in consensus code.

in src/script/interpreter.cpp:1830 in 84ec870859 outdated

1817+            ss_branch << node << k;
1818+        }
1819+        k = ss_branch.GetSHA256();
1820+    }
1821+    k = (CHashWriter(HASHER_TAPTWEAK) << MakeSpan(p) << k).GetSHA256();
1822+    return q.CheckPayToContract(p, k, control[0] & 1);

ariard commented at 0:28 am on September 3, 2020:

Computation of tweaked_pubkey Q is guarantee to be non-malleable by a third-party such that any intentional flip of the parity bit of the control block would fail here ? Is this test somewhere, when I try to test it I got some opsuccess/return error ?

sipa commented at 1:04 am on September 4, 2020:

spendpath/negflag should explicitly test this already.

in src/script/interpreter.cpp:1867 in 84ec870859 outdated

1854         }
1855+    } else if (witversion == 1 && program.size() == WITNESS_V1_TAPROOT_SIZE && !is_p2sh) {
1856+        // BIP341 Taproot: 32-byte non-P2SH witness v1 program (which encodes a P2C-tweaked pubkey)
1857+        if (!(flags & SCRIPT_VERIFY_TAPROOT)) return set_success(serror);
1858+        if (stack.size() == 0) return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_WITNESS_EMPTY);
1859+        if (stack.size() >= 2 && !stack.back().empty() && stack.back()[0] == ANNEX_TAG) {

ariard commented at 0:46 am on September 3, 2020:

Why can’t we outlaw witness-with-annex from our policy ?

EDIT: This is part of it as 7548827. Maybe add a reference that’s is outlawed in IsWitnessStandard. A side-question, why OP_SUCESSx and unknown public key types aren’t rejected there too to gather all witness sanitization check in one place ?

sipa commented at 1:26 am on September 4, 2020:

There was some earlier discussion about this (github’s webinterface is starting to suffer from the obesity of the discussion here, so I can’t find the link).

I’m not sure what the best strategy is here:

Keeping things solely in the interpreter avoids duplicate work/complexity of detecting what type of spending is used, but means extra script validation flags.
Putting things in IsWitnessStandard may be more efficient, as it runs before any script validation is executed (and can be bypassed on testnet, which may or may not be desirable).

I’m currrently following a “things that don’t need significant duplication of work go in IsWitnessStandard, the rest is done using script validation flags” rule, but I admit it’s fairly arbitrary.

Going to add a comment here to note that annexes are nonstandard through other code.

ariard commented at 8:05 pm on September 4, 2020:

I personally lean towards a clean separation between policy and consensus. You need to duplicate detection anyway both at relay and validation, what we may avoid I hope is having twice the same parsing logic. Parsing can be unique and interpretation according to consensus or policy ?

Anyway, it sounds costly in refactoring, I think that’s a wider discussion to have so opened #19875 (pinning previous PR discussion on this matter)

sipa commented at 8:20 pm on September 4, 2020:

@ariard Yes, I agree conceptually with better separation between consensus and policy implementation of script (I myself suggested splitting CScript in a minimal consensus implementation, and a more featureful separate one for everything else - policy and more), but I don’t think that’s relevant to the discussion here.

Even if we have a separate script interpreter for consensus and one for policy, we’ll still want a separate IsStandard* function, which can do policy checks before any script interpreter (which may be expensive) is run.

in src/script/interpreter.cpp:1793 in 84ec870859 outdated

1778+                return set_success(serror);
1779+            }
1780+        }
1781+
1782+        // Tapscript enforces initial stack size limits (altstack is empty here)
1783+        if (stack.size() > MAX_STACK_SIZE) {

ariard commented at 0:59 am on September 3, 2020:

Assert altstack empty ?

sipa commented at 1:33 am on September 4, 2020:

The variable to hold the altstack doesn’t even exist at this point (it’s local to EvalScript, which is invoked a bit further in this function).

ariard commented at 1:00 am on September 3, 2020: member

Still have to review new hash algorithm/opcodes evaluation. So far issues sound to be test holes, see #17977 (review)

in src/script/interpreter.cpp:424 in 84ec870859 outdated

421+    case SigVersion::BASE:
422+    case SigVersion::WITNESS_V0:
423+        return EvalChecksigPreTapscript(sig, pubkey, pbegincodehash, pend, flags, checker, sigversion, serror, success);
424+    case SigVersion::TAPSCRIPT:
425+        return EvalChecksigTapscript(sig, pubkey, execdata, flags, checker, sigversion, serror, success);
426+    case SigVersion::TAPROOT:

ariard commented at 1:47 pm on September 3, 2020:

Should we assert exclusion of scriptless (?) script versions at a higher-level like EvalScript or ExecuteWitnessScript to catch witness parsing bug where such a script wouldn’t call a sig operation ?

sipa commented at 5:30 am on September 4, 2020:

I’ve added a few more asserts (I’m using the terminology “key path spending”, fwiw).

in src/script/interpreter.h:201 in 84ec870859 outdated

200+    //! Hash of the annex data.
201+    uint256 m_annex_hash;
202+
203+    /** Whether m_validation_weight_left is initialized. */
204+    bool m_validation_weight_left_init = false;
205+    /** How much validation weight is left (decremented for every successful signature check). */

ariard commented at 2:35 pm on September 3, 2020:

I think this comment is ambiguous with regards to EvalChecksigTapscript and BIP342 requirement. Successful could be interpreted as :

if signature verification is successful
if signature is non-empty

AFAICT, the second alternative is actually what is referred by signature check. Maybe add successful non-empty signature check

sipa commented at 5:31 am on September 4, 2020:

Good point, done. That also matches the BIP.

in src/script/interpreter.cpp:640 in 84ec870859 outdated

631@@ -568,7 +632,7 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript&
632                         if (stack.size() < 1)
633                             return set_error(serror, SCRIPT_ERR_UNBALANCED_CONDITIONAL);
634                         valtype& vch = stacktop(-1);
635-                        if (sigversion == SigVersion::WITNESS_V0 && (flags & SCRIPT_VERIFY_MINIMALIF)) {
636+                        if (sigversion == SigVersion::TAPSCRIPT || (sigversion == SigVersion::WITNESS_V0 && (flags & SCRIPT_VERIFY_MINIMALIF))) {

ariard commented at 3:01 pm on September 3, 2020:

I think melting a consensus check with a policy one in the same conditional is likely source to confusion for future reviewers. I’m quite sure that’s already something done elsewhere but maybe we could do better by adding a GetScriptVersionFlags(SigVersion) called at the top of EvalScript.

This new function should set each consensus-compliant interpreter flags per-type of script evaluated thus avoiding setting flags for old scripts types if we would do this in GetBlockScriptFlags while easily overloading flag setting for future types.

sipa commented at 5:32 am on September 4, 2020:

I don’t like the idea of changing script validation flags based on context. It might be ok here, but in general that gets complex very quickly - things could even start interacting.

I’ve just added a comment to explain this. What do you think?

ariard commented at 7:39 pm on September 4, 2020:

It depends on how you define context, does it include sigversion parameter ? BIP342 introduction presents well the script rules hierarchy and that would be better if we could encode it in clean code paths, a “flat” flag matrix is obviously harder to reason on.

I think added comment is good enough for now, I guess this conversation belong to the previous, wider one on refactoring/duplicating interpreter before post-taproot script softforks.

nit: SCRIPT_VERIFY_MINIMALIF you forgot the IF in new comment.

sipa commented at 4:26 am on September 14, 2020:

nit: SCRIPT_VERIFY_MINIMALIF you forgot the IF in new comment.

Fixed.

in src/script/interpreter.cpp:1111 in 84ec870859 outdated

1101+
1102+                    // (sig num pubkey -- num)
1103+                    if (stack.size() < 3) return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
1104+
1105+                    const valtype& sig = stacktop(-3);
1106+                    const CScriptNum num(stacktop(-2), fRequireMinimal);

ariard commented at 3:17 pm on September 3, 2020:

Is MINIMALDATA consensus-mandatory for OP_CHECKSIGADD or only part of our relay-policy like for other CScriptNum operators ? The spec only mentions All CScriptNum-related behaviours of OP_ADDare also applicable toOP_CHECKSIGADD", it’s a bit unclear.

In either case flipping it to true/false doesn’t give me back any test failure.

sipa commented at 5:34 am on September 4, 2020:

MINIMALDATA is purely a policy rule, and those are out of scope for BIP341/BIP342. It’s not consensus, but apart from that, this behavior isn’t specified by the BIPs.

I’ve added a test that should exercise non-minimal inputs to OP_CHECKSIGADD.

in src/script/interpreter.cpp:1482 in 84ec870859 outdated

1483+bool SignatureHashSchnorr(uint256& hash_out, const ScriptExecutionData& execdata, const T& tx_to, const uint32_t in_pos, const uint8_t hash_type, const SigVersion sigversion, const PrecomputedTransactionData* cache)
1484+{
1485+    uint8_t ext_flag;
1486+    switch (sigversion) {
1487+    case SigVersion::TAPROOT:
1488+        ext_flag = 0;

ariard commented at 4:05 pm on September 3, 2020:

I think BIP341 footnote mentions that TAPSCRIPT’s ext_flag=1 but I don’t find where it mandates that TAPROOT’s one is actually ext_flag=0

sipa commented at 2:23 am on September 4, 2020:

BIP341 says to use 0x00 || SigMsg(0x00, 0) as message. The 0 there is the ext_flag argument.

in src/script/interpreter.cpp:1536 in 84ec870859 outdated

1537+        ss << execdata.m_annex_hash;
1538+    }
1539+
1540+    // Data about the output(s)
1541+    if (output_type == SIGHASH_SINGLE) {
1542+        if (in_pos >= tx_to.vout.size()) return false;

ariard commented at 4:20 pm on September 3, 2020:

I don’t get feature_taproot.py failure for this :

 0diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
 1index 053df47a2..eb3847250 100644
 2--- a/src/script/interpreter.cpp
 3+++ b/src/script/interpreter.cpp
 4@@ -1528,7 +1528,7 @@ bool SignatureHashSchnorr(uint256& hash_out, const ScriptExecutionData& execdata
 5
 6     // Data about the output(s)
 7     if (output_type == SIGHASH_SINGLE) {
 8-        if (in_pos >= tx_to.vout.size()) return false;
 9+        if (in_pos >= tx_to.vout.size()) return true;
10         CHashWriter sha_single_output(SER_GETHASH, 0);
11         sha_single_output << tx_to.vout[in_pos];
12         ss << sha_single_output.GetSHA256();

Also I think this is check can be moved above at hash_type validation as every predicate is already known and we would save on hashing by failing faster ?

sipa commented at 5:35 am on September 4, 2020:

Nice catch, this one was harder to address. I’ve added support in the test framework for specifying that a particular spending test requires a mismatching output (so the number of outputs <= input position), shuffling inputs around to accomplish that.

in src/script/interpreter.cpp:1541 in 84ec870859 outdated

1547+
1548+    // Additional data for BIP 342 signatures
1549+    if (sigversion == SigVersion::TAPSCRIPT) {
1550+        assert(execdata.m_tapleaf_hash_init);
1551+        ss << execdata.m_tapleaf_hash;
1552+        ss << uint8_t(0); // key_version

ariard commented at 4:28 pm on September 3, 2020:

Does this key version is actually the one of defined 32-byte public key or it is an independent versioning ?

If it is the first option I think we should add a m_key_version to ScriptExecutionData and ensure we set it at key type detection in ExecuteWitnessScript to avoid hashing and public key validation going out of sync ?

sipa commented at 5:39 am on September 4, 2020:

It’s intended to be used for future key versions. That means it can’t be in ScriptExecutionData which is shared for an entire script execution (and one script could contain multiple key versions).

I’ve tried to clarify this by making key_version an explicit argument to SignatureHashSchnorr (but with an assert that it’s zero). This allows passing it down from CheckSchnorrSignature, which is where that decision logic might go (there, or even higher in EvalChecksigTapscript).

in src/pubkey.cpp:177 in 84ec870859 outdated

172+    assert(in.size() == 32);
173+    std::copy(in.begin(), in.end(), m_keydata.begin());
174+}
175+
176+bool XOnlyPubKey::VerifySchnorr(const uint256& msg, Span<const unsigned char> sigbytes) const {
177+    if (sigbytes.size() != 64) return false;

ariard commented at 4:53 pm on September 3, 2020:

I don’t get feature_taproot.py failure for :

 0diff --git a/src/pubkey.cpp b/src/pubkey.cpp
 1index 111f9c10e..0163f61a2 100644
 2--- a/src/pubkey.cpp
 3+++ b/src/pubkey.cpp
 4@@ -174,7 +174,7 @@ XOnlyPubKey::XOnlyPubKey(Span<const unsigned char> in)
 5 }
 6 
 7 bool XOnlyPubKey::VerifySchnorr(const uint256& msg, Span<const unsigned char> sigbytes) const {
 8-    if (sigbytes.size() != 64) return false;
 9+    if (sigbytes.size() != 64) return true;
10     if (msg.size() != 32) return false;
11     secp256k1_xonly_pubkey pubkey;
12     if (!secp256k1_xonly_pubkey_parse(secp256k1_context_verify, &

And same for next check on message size.

sipa commented at 5:40 am on September 4, 2020:

I’ve changed the sigbytes length check to an assert. The msg length check was just stupid; it’s a uint256, its length is always 32.

in src/policy/policy.cpp:268 in 84ec870859 outdated

263+                }
264+            } else if (stack.size() == 1) {
265+                // Key path spend (1 stack element after removing optional annex)
266+                // (no policy rules apply)
267+            } else {
268+                // 0 stack elements remain after removing optional annex; this is invalid

ariard commented at 4:57 pm on September 3, 2020:

Maybe precise that’s invalid with regards to consensus. Or at least we enforce this as a policy rule without any tightening with regards to consensus rule.

sipa commented at 5:40 am on September 4, 2020:

Done.

ariard commented at 4:59 pm on September 3, 2020: member

See #17977 (review) and #17977 (review) which are overall worthy of attention.

(done for now and ACK on merging strategy)

sipa force-pushed on Sep 4, 2020

DrahtBot removed the label Needs rebase on Sep 4, 2020

gmaxwell commented at 4:48 am on September 4, 2020: contributor

The biggest mistake IMO is using BIP9 instead of BIP8.

This PR doesn’t even have activation at all: it is set to always active in regtest and not at all otherwise. The only connection to bip9 is that the code that handles BIP9 is the codebases’ generic code for handling consensus rules which are active in some places and not others.

The way this works (and the way it has generally worked for prior consensus changes)– is that the functionality is first merged disabled (except for in testing modes) and then later the activation gets done. It’s difficult to test things completely without establishing them in the codebase, and people can’t really decide to activate a consensus change that isn’t done.

So please don’t bring activation discussion to this PR, it’s offtopic unless there is some specific technical property of the implementation or specification that would have some particular ramification for activation: e.g. if it was implemented in a way that prevented the new rules from being activated at a particular block but not active before then that would be worth pointing out.

sipa force-pushed on Sep 4, 2020

sipa commented at 5:51 am on September 4, 2020: member

Rebased, updated libsecp256k1 to latest https://github.com/bitcoin-core/secp256k1/pull/558, and addressed a number of comments by @fjahr, @Kixunil, and @ariard. Thanks!

sipa force-pushed on Sep 4, 2020

sipa force-pushed on Sep 5, 2020

sipa force-pushed on Sep 6, 2020

Kixunil commented at 4:50 pm on September 7, 2020: none

@gmaxwell thanks for clarifying, will check activation discussion at whatever is the appropriate place.

sipa force-pushed on Sep 11, 2020

sipa commented at 9:36 pm on September 11, 2020: member

Rebased on top of #19944.

fanquake referenced this in commit ba4b3fbcf2 on Sep 14, 2020

Add TaggedHash function (BIP 340) 3430eaec88

Keep spent outputs in PrecomputedTransactionData during validation

A BIP-341 signature message may commit to the scriptPubKeys and amounts
of all spent outputs (including other ones than the input being signed
for spends), so keep them available to signature hashing code.

ba285d8d2b

Implement Taproot signature hashing (BIP 341)

Includes changes to PrecomputedTransactionData by Pieter Wuille.

b63f19a4bd

refactor: put ECDSA in name of signature function 466b0229ca

Support for Schnorr signatures and integration in SignatureCheckers (BIP 340) 76f2e3e14d

refactor: rename scriptPubKey in VerifyWitnessProgram to exec_script

The old name is confusing, as it doesn't store a scriptPubKey, but the
actually executed script.

ddfc3657d0

Implement Taproot validation (BIP 341)

This includes key path spending and script path spending, but not the
Tapscript execution implementation.

Includes constants for various aspects of the consensus rules suggested
by Jeremy Rubin.

804ff644f4

Use ScriptExecutionData to pass through annex hash d384d67873

sipa force-pushed on Sep 14, 2020

Implement Tapscript script validation rules (BIP 342) a73d5e1d8b

Make Taproot spends standard + policy limits a7ab59707c

Activate Taproot/Tapscript on regtest (BIP 341, BIP 342) 24fd22f2ef

[TESTS] Add BIP340 Schnorr signature support to test framework 89a14b5b7d

[TESTS] Functional tests for Schnorr/Taproot/Tapscript

Includes sighashing code and many tests by Johnson Lau.
Includes a test by Matthew Zipkin.
Includes several tests and improvements by Greg Sanders.

6c1edf0d73

sipa force-pushed on Sep 14, 2020

sipa closed this on Sep 14, 2020

sipa commented at 4:34 am on September 14, 2020: member

Closing in favor of new PR(s), as discussed here.

sidhujag referenced this in commit 711b81967a on Sep 15, 2020

laanwj referenced this in commit 3caee16946 on Oct 15, 2020

sidhujag referenced this in commit ca9eeb33df on Oct 16, 2020

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

UdjinM6 referenced this in commit c2ab8285d8 on Aug 10, 2021

5tefan referenced this in commit abf9ac837f on Aug 12, 2021

PhotoshiNakamoto referenced this in commit 6a91740085 on Dec 11, 2021

DrahtBot locked this on Feb 15, 2022

Implement BIP 340-342 validation (Schnorr/taproot/tapscript) #17977

Conflicts