This is an implementation of the Schnorr/taproot consensus rules proposed by BIPs 340, 341, and 342.
See the list of commits below. No signing or wallet support of any kind is included, as testing is done entirely through the Python test framework.
This is a successor to #17977 (see discussion following this comment), and will have further changes squashed/rebased. The history of this PR can be found in #19997.
Here is a categorized list of all the commits:
CheckSig, VerifySignature, and ComputeEntry, give them an ECDSA specific name.SignatureChecker classes. The (verification side of the) BIP340 test vectors is also added.SigVersion::TAPSCRIPT, makes the necessary interpreter changes to make it implement BIP342, and uses them for leaf version 0xc0 in Taproot script path spends.TxoutType::WITNESS_V1_TAPROOT for P2TR outputs, and permits spending them in standardness rules. No corresponding CTxDestination is added for it, as that isn’t needed until we want wallet integration. The taproot validation flags are also enabled for mempool transactions, and standardness rules are added (stack item size limit, no annexes).PREV="$(git rev-parse HEAD)"; git log --oneline upstream/master..HEAD | while read C L; do if [ "d${L:0:14}" == "d--- [TAPROOT] " ]; then if [ "d$PREV" != "" ]; then git diff --shortstat $C..$PREV | (read _ _ _ ADD _ DEL _; echo "### ${L:14:-4} (https://github.com/sipa/bitcoin/compare/$C...$PREV) [+$ADD -$DEL]:"); echo; fi; PREV=$C; PREVL=$L; else echo -n " * $C **${L}**: "; git show "$C" --format="%b" -s | awk '/^$/{exit} 1' | tr $'\n' ' '; echo; fi; done | tac
Concept ACK :)
Perhaps the pure refactor commits can be split into their own PR to reduce the size of this?
1644@@ -1645,7 +1645,7 @@ if test x$need_bundled_univalue = xyes; then
1645 AC_CONFIG_SUBDIRS([src/univalue])
1646 fi
1647
1648-ac_configure_args="${ac_configure_args} --disable-shared --with-pic --enable-benchmark=no --with-bignum=no --enable-module-recovery"
1649+ac_configure_args="${ac_configure_args} --disable-shared --with-pic --enable-benchmark=no --with-bignum=no --enable-module-recovery --enable-module-schnorrsig --enable-experimental"
-enable-experimental flag to build the schnorrsig module?
This was discussed in the previous PR.
luke-jr
Should this be non-experimental before merging?
gmaxwell
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
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.
244+ // - MAX_STANDARD_TAPSCRIPT_STACK_ITEM_SIZE limit for stack item size
245+ // - No annexes
246+ if (witnessversion == 1 && witnessprogram.size() == WITNESS_V1_TAPROOT_SIZE && !p2sh) {
247+ // Taproot spend (non-P2SH-wrapped, version 1, witness program size 32; see BIP 341)
248+ auto stack = MakeSpan(tx.vin[i].scriptWitness.stack);
249+ if (stack.size() >= 2 && !stack.back().empty() && stack.back()[0] == ANNEX_TAG) {
stack.size() >= 2 twice
I added a unit test too now, with test vectors that were extracted from 20000 runs of the feature_taproot.py test (with the largest tests removed, and larger groups of inputs per transaction), minimized using libfuzzer’s coverage tracking to 105.
The code for doing so is in https://github.com/sipa/bitcoin/commits/taproot-test-creation. I’ll clean that code up a bit and integrate some parts of it in the normal Python test, so it’s easier to recreate these vectors if improvements to the Python test are made.
I was surprised to learn that this was a 2500-line PR. By directory:
/test/functional - 1790 lines/src/test - 134 lines/src (exc test) - 817 linesSo the majority of code in this PR is tests (which is a good thing!)
I agree with sipa that it’s not necessary to split off the first two commits (especially now that they’re separated to the top of the branch). Equally no harm in doing so if that’d reduce the workload.
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.
Reviewers, this pull request conflicts with the following ones:
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.
215+ /** Construct an x-only pubkey from exactly 32 bytes. */
216+ XOnlyPubKey(Span<const unsigned char> input);
217+
218+ /** Verify a 64-byte Schnorr signature.
219+ *
220+ * If the signature is not exactly 64 bytes, false is returned.
VerifySchnorr has assert(sigbytes.size() == 64); so false won’t be returned. Should either change this comment or change the assertion to if (sigbytes.size() != 64) return false;
335+bool IsOpSuccess(const opcodetype& opcode)
336+{
337+ return (opcode == 0x50 || opcode == 0x62 || opcode == 0x89 ||
338+ opcode == 0x8a || opcode == 0x8d || opcode == 0x8e ||
339+ (opcode >= 0x7e && opcode <= 0x81) || (opcode >= 0x83 && opcode <= 0x86) ||
340+ (opcode >= 0x95 && opcode <= 0x99) || (opcode >= 0xbb && opcode <= 0xfe));
74@@ -75,6 +75,10 @@ std::string ScriptErrorString(const ScriptError serror)
75 return "Witness version reserved for soft-fork upgrades";
76 case SCRIPT_ERR_DISCOURAGE_UPGRADABLE_TAPROOT_VERSION:
77 return "Taproot version reserved for soft-fork upgrades";
78+ case SCRIPT_ERR_DISCOURAGE_OP_SUCCESS:
79+ return "SUCCESSx reserved for soft-fork upgrades";
OP_, to be consistent this could be changed to OP_SUCCESSx reserved for...
After initial research and deep dive, I ask the following:
Below are my concerns with questions regarding this PR, answers and clarifications will hopefully bring me around.
Original motivation to review this PR came from a tweet with a bounty. I am honored to help bitcoin, and am reviewing this PR independant of monetary expectations.
Following documents have been read and reviewed in detail specifically for this review, skipping some code and proofs.
Reason for not a simple “concept NACK” is because of the known information gap on my end. Specifically, I have not read most of bitcoin bips since early segwit.
some of these are leading some of these are clarifying
MultiSig I’m concerned that we are explicitly promoting MultiSig as a net positive for securing users private keys, and as far as i can tell, the consensus is that multisig comes down to a single leader in practice.
Key Reuse I’m concerned that we are implicitly assuming that key reuse is wrong, but as far as i can tell, the consensus is that code reuse is fine for most cases.
Highest concern is if the efficiency improvements, like removal of double sha256 hashing and others, are assuming no key reuse, creating a new vector for user error, since a majority of bitcoin users reuse their keys.
similar sentiments:
“While the key holders are expected not to reuse key pair, little could be done to stop payers to reuse an address. Unfortunately, key-pair reuse has been a social and technical norm since the creation of Bitcoin (the first tx made in block 170 reused the previous public key). I don’t see any hope to change this norm any time soon, if possible at all.” bitcoin-dev
Overall, we are left with concerns both about the merit of doing Taproot versus alternatives, as well as the process through which we got to be here.
- Is Taproot actually more private than bare MAST and Schnorr separately? What are the actual anonymity set benefits compared to doing the separately?
Yes, presuming single-pubkey-single-signature remains a common authorisation pattern. bitcoin-dev
and fud:
red flags:
Homomorphic Payment Addresses and the Pay-to-Contract Protocol
- Customer public key “a" in the tx cannot be used twice for same Public-Key of merchant
- signaling variation? address(a,c) vs address(P,c) -
- (a,c) becomes a private key
other: DISCOURAGE_FLAG - why the need for this flag? can’t we say - ON_POLICY_CHANGE(Transform the mempool)?
flagged for followup: BIP340
This complicates the implementation of secure signing protocols in scenarios in which a group of mutually distrusting signers work together to produce a single joint signature
Using the first option would be slightly more efficient for verification (around 10%), but we prioritize compactness, and therefore choose option 3. batch verification
breaking an X only key - at most a small constant faster
nonce - leaking secret
every public key - has two corresponding secret keys
not using the same private key - across different signing schemes - signatures can leak secret key through nonce reuse
open up new nonce attack vectors
However, if this optimization is used and additionally the signature verification at the end of the signing algorithm is dropped for increased efficiency, signers must ensure the public key is correctly calculated and not taken from untrusted sources.
While recent academic papers claim that they are also possible with ECDSA, consensus support for Schnorr signature verification would significantly simplify the constructions.”
Combining all these ideas in a single proposal would be an extensive change, be hard to review, and likely miss new discoveries that otherwise could have been made along the way.
Just like other existing output types, taproot outputs should never reuse keys, for privacy reasons. This does not only apply to the particular leaf that was used to spend an output but to all leaves committed to in the output. If leaves were reused, it could happen that spending a different output would reuse the same Merkle branches in the Merkle proof.
fixes the verification capabilities of offline signing devices by including amount and scriptPubKey in the signature message, avoids unnecessary hashing
Hashes that go into the signature message and the message itself are now computed with a single SHA256 invocation instead of double SHA256. There is no expected security improvement by doubling SHA256 because this only protects against length-extension attacks against SHA256 which are not a concern for signature messages because there is no secret data. Therefore doubling SHA256 is a waste of resources.
The public key is directly included in the output in contrast to typical earlier constructions which store a hash of the public key or script in the output. This has the same cost for senders and is more space efficient overall if the key-based spending path is taken. [2]
The inefficient OP_CHECKMULTISIG and OP_CHECKMULTISIGVERIFY opcodes are disabled. Instead, a new opcode OP_CHECKSIGADD is introduced to allow creating the same multisignature policies in a batch-verifiable way.
Disabled script opcodes The following script opcodes are disabled in tapscript: OP_CHECKMULTISIG and OP_CHECKMULTISIGVERIFY[2]. The disabled opcodes behave in the same way as OP_RETURN, by failing and terminating the script immediately when executed, and being ignored when found in unexecuted branch of the script.
This way, new SIGHASH modes can be added, as well as NOINPUT-tagged public keys and a public key constant which is replaced by the taproot internal key for signature validation.
Why is a limit on script size no longer needed? Since there is no scriptCode directly included in the signature hash (only indirectly through a precomputable tapleaf hash), the CPU time spent on a signature check is no longer proportional to the size of the script being executed.
as stated
privacy, efficiency, and flexibility of Bitcoin’s scripting capabilities
This proposal aims to improve privacy, efficiency, and flexibility of Bitcoin’s scripting capabilities without adding new security assumptions[1]. Specifically, it seeks to minimize how much information about the spendability conditions of a transaction output is revealed on chain at creation or spending time and to add a number of upgrade mechanisms, while fixing a few minor but long-standing issues
Taproot is an optional feature, and P2PKH key reusers, not concerned with privacy, do not need to us it. Yet, they still get the benefits of smaller multisig transactions.
Is this chart the only benefits of this PR for the majority of users? Is it worth consensus soft-fork? What are the risks?
Taproot’s advantages become apparent under the assumption that most applications involve outputs that could be spent by all parties agreeing
This use of practical reality built into the bitcoin protocol is exactly what we need more off! Maybe this abstraction can one day be made between alice and bob, because many times alice is really bob in a dress, and bob has no double spend risk on the tx from bob to bob.
defaut spending path from what i understand, since in practice over 85% of bitcoin transaction are single key, the default path will be basically p2pkh (or the Segwit + Schnorr equivalent)
user story If Taproot tree path spending is not for the 85% of bitcoin users, then who is it for? actual user stories will go a long way here.
@jaybny All of those questions are about the BIPs themselves, and not about the code changes to implement them, and thus out of scope here. I suggest you discuss them on the bitcoin-dev mailing list, https://bitcoin.stackexchange.com, or other media.
I’ll give my answers for your list of short questions, but if you have follow up discussion, please take it elsewhere. It would be distracting to code reviewers here.
104@@ -86,13 +105,13 @@ def is_x_coord(self, x):
105 return jacobi_symbol(x_3 + self.a * x + self.b, self.p) != -1
106
107 def lift_x(self, x):
108- """Given an X coordinate on the curve, return a corresponding affine point."""
109+ """Given an X coordinate on the curve, return a corresponding affine point for which the y-coordinate is even."""
406+ return (None, None)
407+ P = SECP256K1.affine(SECP256K1.mul([(SECP256K1_G, x)]))
408+ return (P[0].to_bytes(32, 'big'), not SECP256K1.has_even_y(P))
409+
410+def tweak_add_privkey(key, tweak, negated=False):
411+ """Tweak a private key (after optionally negating it)."""
479+
480+def sign_schnorr(key, msg, aux=None, flip_p=False, flip_r=False):
481+ """Create a Schnorr signature (see BIP 340)."""
482+
483+ if aux is None:
484+ aux = bytes(0 for _ in range(32))
bytes(32). python wouldn’t let you have uninitialized memory.
524+ def test_schnorr_testvectors(self):
525+ """Implement the BIP340 test vectors (read from bip340_test_vectors.csv)."""
526+ num_tests = 0
527+ with open(os.path.join(sys.path[0], 'test_framework', 'bip340_test_vectors.csv'), newline='', encoding='utf8') as csvfile:
528+ reader = csv.reader(csvfile)
529+ reader.__next__()
next(reader)? arguably more readable.
This was copied from the BIP340 reference code. You may want to update it there too.
Done.
481+ """Create a Schnorr signature (see BIP 340)."""
482+
483+ if aux is None:
484+ aux = bytes(0 for _ in range(32))
485+
486+ assert(len(key) == 32)
427+ return x.to_bytes(32, 'big')
428+
429+def tweak_add_pubkey(key, tweak):
430+ """Tweak a public key and return whether the result was negated."""
431+
432+ assert(len(key) == 32)
I addressed comments by @benthecarman and @ysangkok. See “Updates 2020-09-22” in the new PR #19997 for the changes that were applied.
I also moved the “keep spent outputs in PrecomputedTransactionData” to the refactors section, as it contains no semantics changes, and didn’t depend on any earlier commits.
reviewed updates to https://github.com/bitcoin/bitcoin/pull/19953/commits/fe5cf2ed6adbf2271553f97c61de4d59bee20c05
IsOpSuccess was compared against the BIP directly rather than previous iteration, which I had hand-calculated painstakingly. It matches the BIP.
1430+ }
1431+ if (have_annex) {
1432+ ss << (CHashWriter(SER_GETHASH, 0) << witstack->back()).GetSHA256();
1433+ }
1434+
1435+ // Data about the output(s)
438@@ -381,6 +439,9 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript&
439 // static const valtype vchZero(0);
440 static const valtype vchTrue(1, 1);
441
442+ // sigversion cannot be TAPROOT here, as it admits no script execution.
443+ assert(sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0 || sigversion == SigVersion::TAPSCRIPT);
assert(sigversion != SigVersion:: TAPROOT)?
1674@@ -1565,7 +1675,7 @@ bool GenericTransactionSignatureChecker<T>::CheckSchnorrSignature(Span<const uns
1675 if (hashtype == SIGHASH_DEFAULT) return false;
1676 }
1677 uint256 sighash;
1678- if (!SignatureHashSchnorr(sighash, execdata, *txTo, nIn, hashtype, sigversion, this->txdata)) return false;
1679+ if (!SignatureHashSchnorr(sighash, execdata, *txTo, nIn, hashtype, sigversion, 0x00, this->txdata)) return false;
0 if (!SignatureHashSchnorr(sighash, execdata, *txTo, nIn, hashtype, sigversion, 0x00 /* key_version */, this->txdata)) return false;
1648+ SCRIPT_VERIFY_P2SH |
1649+ SCRIPT_VERIFY_CHECKLOCKTIMEVERIFY |
1650+ SCRIPT_VERIFY_CHECKSEQUENCEVERIFY |
1651+ SCRIPT_VERIFY_WITNESS |
1652+ SCRIPT_VERIFY_NULLFAIL |
1653+ SCRIPT_VERIFY_TAPROOT;
MINIMALIF?
ACK https://github.com/bitcoin/bitcoin/pull/19953/commits/fe5cf2ed6adbf2271553f97c61de4d59bee20c05
Reviewed all commits one by one, side by side with my latest known-good review. Poked at new unit tests/mutated logic as a sanity check.
One request I’d have is some documentation on how to extract the unit test, if possible. Maybe it was hacked together, but still having a general description of using the fuzzing construct could be helpful for people to look for smaller/better sets. For example, someone could create coverage for MINIMALIF. (I did a mutation test for it and it passed)
1338+ if (!txTo.vin[inpos].scriptWitness.IsNull()) {
1339+ if (m_spent_outputs_ready && m_spent_outputs[inpos].scriptPubKey.size() == 2 + WITNESS_V1_TAPROOT_SIZE &&
1340+ m_spent_outputs[inpos].scriptPubKey[0] == OP_1) {
1341+ // Treat every native witness v1 spend as a Taproot spend. This only works if spent_outputs was
1342+ // provided as well, but if it wasn't, actual validation will fail anyway.
1343+ uses_bip341_taproot = true;
34da2198264cf90a7ae7f50a912a599f6fd66291
No need to be exhaustive?
0uses_bip341_taproot = true;
1if (uses_bip143_segwit) break;
uses_bip341_taproot and uses_bip143_segwit set correctly, vs with the current implementation it would continue and check the remaining 98 inputs.
1387+ break;
1388+ default:
1389+ assert(false);
1390+ }
1391+ assert(in_pos < tx_to.vin.size());
1392+ assert(cache != nullptr && cache->m_bip341_taproot_ready && cache->m_spent_outputs_ready);
34da2198264cf90a7ae7f50a912a599f6fd66291
Then change to const PrecomputedTransactionData& cache instead?
I addressed comments by @instagibbs, and made the unit test vectors test more and generic and made it qa-assets based (see corresponding PR https://github.com/bitcoin-core/qa-assets/pull/27). Changes are in two new sections in #19997.
I’m still working on polishing up the tooling used to create script_assets_test.json. At this point they don’t test anything that (many iterations of) feature_taproot.py doesn’t test, so I think review should be focused on that.
80efcba
1514+ ss << EPOCH;
1515+
1516+ // Hash type
1517+ 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
1518+ const uint8_t input_type = hash_type & SIGHASH_INPUT_MASK;
1519+ if (!(hash_type <= 0x03 || (hash_type >= 0x81 && hash_type <= 0x83))) return false;
This line is very compact.
Looks like those numeric literals are based on SIGHASH_INPUT_MASK. If they are, could they not be constructed from it? It is weird to have logic based partly on the enum, and partly on hard coded numeric literals.
I think this could be split up into two if’s, each returning false. Then, each of those branches could be explaining the situation and the reason for rejection.
Every time I see a negation of a boolean operator, I do de-morgan in my head. Either way, if you prefer this with or without the outer negation, I think splitting it up would really be preferable, it would be readable for all kinds of brains.
This is not complicated logic, and it is easy to avoid having it look complex. Just my two cents :)
That would be incorrect.
de-morganing it gives you !(hash_type <= 0x03) && !(hash_type >= 0x81 && hash_type <= 0x83), which is a conjunction at the top level. Splitting that up into two separate ifs would make it a disjunction.
50f0a10f7b2e45491775c1166c4593e7fa8cfd4b
0 if (hash_type >= 0x84 || (hash_type >= 0x04 && hash_type <= 0x80)) return false;
seems slightly more straightforward, IMO.
Interpreting it becomes “If the hash type is above 0x84 or within 0x04 and 0x80” vs “if it is NOT the case that the hash type is <= 0x03 or within 0x81 and 0x83”.
A few updates (see #19997 for detailed history):
85@@ -86,6 +86,11 @@ class CMainParams : public CChainParams {
86 consensus.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].nStartTime = 1199145601; // January 1, 2008
87 consensus.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].nTimeout = 1230767999; // December 31, 2008
88
89+ // Deployment of Taproot (BIPs 340-342)
90+ consensus.vDeployments[Consensus::DEPLOYMENT_TAPROOT].bit = 2;
91+ consensus.vDeployments[Consensus::DEPLOYMENT_TAPROOT].nStartTime = 1199145601; // January 1, 2008
DEPLOYMENT_TESTDUMMY I suspect
c849dae
1499@@ -1470,6 +1500,7 @@ BOOST_AUTO_TEST_CASE(script_HasValidOps)
1500 BOOST_CHECK(!script.HasValidOps());
1501 }
1502
1503+
0@@ -1,15 +1,30 @@
1-# Copyright (c) 2019 Pieter Wuille
2+# Copyright (c) 2019-2020 Pieter Wuille
3+
245
246 using TransactionSignatureChecker = GenericTransactionSignatureChecker<CTransaction>;
247 using MutableTransactionSignatureChecker = GenericTransactionSignatureChecker<CMutableTransaction>;
248
249-bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* error = nullptr);
250+bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* error = nullptr, ScriptExecutionData execdata = {});
6577f465f3dad2460b2bee02ca662c7ebbe72e4c
nit, avoids copying ScriptExecutionData and error is still the last one.
0bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, const ScriptExecutionData& execdata, ScriptError* error = nullptr);
1bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* error = nullptr)
2{
3 ScriptExecutionData execdata;
4 EvalScript(stack, script, flags, checker, sigversion, execdata, error);
5}
That won’t work, EvalScript needs a mutable ScriptExecutionData object.
It would be slightly cleaner to split the execdata into a fixed-at-VerifyScript-time part and a changed-during-execution part, but that’d be a even more annoying interface change.
Actually, it’s possible to avoid the copy still by just making it mutable, and using your idea of a wrapper to provide a default:
https://github.com/sipa/bitcoin/commit/09b24d503a7b9baace0be3f51e53f2a095cf160b
0diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
1index 9d25ec156a..f4cf24fee5 100644
2--- a/src/script/interpreter.cpp
3+++ b/src/script/interpreter.cpp
4@@ -428,8 +428,7 @@ static bool EvalChecksig(const valtype& sig, const valtype& pubkey, CScript::con
5 assert(false);
6 }
7
8-
9-bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* serror, ScriptExecutionData execdata)
10+bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptExecutionData& execdata, ScriptError* serror)
11 {
12 static const CScriptNum bnZero(0);
13 static const CScriptNum bnOne(1);
14@@ -1257,6 +1256,12 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript&
15 return set_success(serror);
16 }
17
18+bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* serror)
19+{
20+ ScriptExecutionData execdata;
21+ return EvalScript(stack, script, flags, checker, sigversion, execdata, serror);
22+}
23+
24 namespace {
25
26 /**
27@@ -1776,7 +1781,7 @@ bool GenericTransactionSignatureChecker<T>::CheckSequence(const CScriptNum& nSeq
28 template class GenericTransactionSignatureChecker<CTransaction>;
29 template class GenericTransactionSignatureChecker<CMutableTransaction>;
30
31-static bool ExecuteWitnessScript(const Span<const valtype>& stack_span, const CScript& scriptPubKey, unsigned int flags, SigVersion sigversion, const BaseSignatureChecker& checker, const ScriptExecutionData& execdata, ScriptError* serror)
32+static bool ExecuteWitnessScript(const Span<const valtype>& stack_span, const CScript& scriptPubKey, unsigned int flags, SigVersion sigversion, const BaseSignatureChecker& checker, ScriptExecutionData& execdata, ScriptError* serror)
33 {
34 std::vector<valtype> stack{stack_span.begin(), stack_span.end()};
35
36@@ -1810,7 +1815,7 @@ static bool ExecuteWitnessScript(const Span<const valtype>& stack_span, const CS
37 }
38
39 // Run the script interpreter.
40- if (!EvalScript(stack, scriptPubKey, flags, checker, sigversion, serror, execdata)) return false;
41+ if (!EvalScript(stack, scriptPubKey, flags, checker, sigversion, execdata, serror)) return false;
42
43 // Scripts inside witness implicitly require cleanstack behaviour
44 if (stack.size() != 1) return set_error(serror, SCRIPT_ERR_CLEANSTACK);
45diff --git a/src/script/interpreter.h b/src/script/interpreter.h
46index c71a125e73..1050ed1550 100644
47--- a/src/script/interpreter.h
48+++ b/src/script/interpreter.h
49@@ -272,7 +272,8 @@ public:
50 using TransactionSignatureChecker = GenericTransactionSignatureChecker<CTransaction>;
51 using MutableTransactionSignatureChecker = GenericTransactionSignatureChecker<CMutableTransaction>;
52
53-bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* error = nullptr, ScriptExecutionData execdata = {});
54+bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptExecutionData& execdata, ScriptError* error = nullptr);
55+bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* error = nullptr);
56 bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const CScriptWitness* witness, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* serror = nullptr);
57
58 size_t CountWitnessSigOps(const CScript& scriptSig, const CScript& scriptPubKey, const CScriptWitness* witness, unsigned int flags);
ScriptExecutionData’s contents has a linear history, so there is no need to pass it as const.
In preparation for adding Schnorr versions of `CheckSig`, `VerifySignature`, and
`ComputeEntry`, give them an ECDSA specific name.
-BEGIN VERIFY SCRIPT-
sed -i 's/CheckSig(/CheckECDSASignature(/g' $(git grep -l CheckSig ./src)
sed -i 's/VerifySignature(/VerifyECDSASignature(/g' $(git grep -l VerifySignature ./src)
sed -i 's/ComputeEntry(/ComputeEntryECDSA(/g' $(git grep -l ComputeEntry ./src)
-END VERIFY SCRIPT-
The old name is confusing, as it doesn't store a scriptPubKey, but the
actually executed script.
1543+ if (!txdata.m_spent_outputs_ready) {
1544+ std::vector<CTxOut> spent_outputs;
1545+ spent_outputs.reserve(tx.vin.size());
1546+
1547+ for (const auto& txin : tx.vin) {
1548+ const COutPoint &prevout = txin.prevout;
1ef50ed µ-nit
0 const COutPoint& prevout = txin.prevout;
1412+
1413 } // namespace
1414
1415 template <class T>
1416-void PrecomputedTransactionData::Init(const T& txTo)
1417+void PrecomputedTransactionData::Init(const T& txTo, std::vector<CTxOut> spent_outputs)
1ef50ed perhaps, per #19953 (review)
0void PrecomputedTransactionData::Init(const T& txTo, std::vector<CTxOut>&& spent_outputs)
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;
31c322a perhaps use constexpr
0static constexpr unsigned int ANNEX_TAG = 0x50;
1491+static const CHashWriter HASHER_TAPLEAF = TaggedHash("TapLeaf");
1492+static const CHashWriter HASHER_TAPBRANCH = TaggedHash("TapBranch");
1493+static const CHashWriter HASHER_TAPTWEAK = TaggedHash("TapTweak");
1494+
1495+template<typename T>
1496+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 uint8_t key_version, const PrecomputedTransactionData& cache)
In commits 31c322a (in_pos, hash_type, sigversion) and 332dc13bdc (key_version) perhaps remove constness for by-value arguments, e.g. per discussion at #19845 (review)
0bool SignatureHashSchnorr(uint256& hash_out, const ScriptExecutionData& execdata, const T& tx_to, uint32_t in_pos, uint8_t hash_type, SigVersion sigversion, uint8_t key_version, const PrecomputedTransactionData& cache)
1481
1482 // explicit instantiation
1483-template void PrecomputedTransactionData::Init(const CTransaction& txTo);
1484-template void PrecomputedTransactionData::Init(const CMutableTransaction& txTo);
1485+template void PrecomputedTransactionData::Init(const CTransaction& txTo, std::vector<CTxOut> spent_outputs);
1486+template void PrecomputedTransactionData::Init(const CMutableTransaction& txTo, std::vector<CTxOut> spent_outputs);
1ef50ed perhaps, per #19953 (review)
0-template void PrecomputedTransactionData::Init(const CTransaction& txTo, std::vector<CTxOut> spent_outputs);
1-template void PrecomputedTransactionData::Init(const CMutableTransaction& txTo, std::vector<CTxOut> spent_outputs);
2+template void PrecomputedTransactionData::Init(const CTransaction& txTo, std::vector<CTxOut>&& spent_outputs);
3+template void PrecomputedTransactionData::Init(const CMutableTransaction& txTo, std::vector<CTxOut>&& spent_outputs);
167
168 PrecomputedTransactionData() = default;
169
170 template <class T>
171- void Init(const T& tx);
172+ void Init(const T& tx, std::vector<CTxOut> spent_outputs);
1ef50ed perhaps, as the caller is txdata.Init(tx, std::move(spent_outputs));, if we want to force callers to move it
0 void Init(const T& tx, std::vector<CTxOut>&& spent_outputs);
211+private:
212+ uint256 m_keydata;
213+
214+public:
215+ /** Construct an x-only pubkey from exactly 32 bytes. */
216+ XOnlyPubKey(Span<const unsigned char> input);
XOnlyPubKey::XOnlyPubKey(Span<const unsigned char> in) as in the declaration
bytes.
39- m_salted_hasher.Write(nonce.begin(), 32);
40- m_salted_hasher.Write(nonce.begin(), 32);
41+ // just write our 32-byte entropy, and then pad with 'E' for ECDSA and
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'};
constexpr for these two declarations
178+ secp256k1_xonly_pubkey pubkey;
179+ if (!secp256k1_xonly_pubkey_parse(secp256k1_context_verify, &pubkey, m_keydata.data())) return false;
180+ return secp256k1_schnorrsig_verify(secp256k1_context_verify, sigbytes.data(), msg.begin(), &pubkey);
181+}
182+
183+bool XOnlyPubKey::CheckPayToContract(const XOnlyPubKey& base, const uint256& hash, const bool parity) const
3c2d549 constness not present in the declaration on by-value argument
0bool XOnlyPubKey::CheckPayToContract(const XOnlyPubKey& base, const uint256& hash, bool parity) const
First pass of code review and debug build of each commit up to 3c2d549ee. No blocking issues seen so far. A few minor comments follow; feel free to pick/choose/ignore. Continuing on the second half of the commits.
Reviewers: if helpful, there are several review club sessions on this BIP340-342 implementation at https://bitcoincore.reviews/meetings-components/#consensus
Edit: a new dedicated taproot review club section has been added:
205+ uint256 m_annex_hash;
206+
207+ /** Whether m_validation_weight_left is initialized. */
208+ bool m_validation_weight_left_init = false;
209+ /** How much validation weight is left (decremented for every successful non-empty signature check). */
210+ int64_t m_validation_weight_left;
332dc13b perhaps use same doc style as other members of this struct, and also per doc/developer-notes.md “To describe a member or variable”
0- /** Whether m_validation_weight_left is initialized. */
1+ //! Whether m_validation_weight_left is initialized.
2 bool m_validation_weight_left_init = false;
3- /** How much validation weight is left (decremented for every successful non-empty signature check). */
4+ //! How much validation weight is left (decremented for every successful non-empty signature check).
437@@ -381,6 +438,9 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript&
438 // static const valtype vchZero(0);
439 static const valtype vchTrue(1, 1);
440
441+ // sigversion cannot be TAPROOT here, as it admits no script execution.
442+ assert(sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0 || sigversion == SigVersion::TAPSCRIPT);
sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0 in EvalScript(), could (very optionally) factor out to a const bool localvar
1498+static const CHashWriter HASHER_TAPTWEAK = TaggedHash("TapTweak");
1499+
1500+template<typename T>
1501+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 uint8_t key_version, const PrecomputedTransactionData& cache)
1502+{
1503+ uint8_t ext_flag;
332dc13b currently low-risk here, but perhaps avoid future possibility of use before set
0 uint8_t ext_flag{0};
633@@ -568,6 +634,13 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript&
634 if (stack.size() < 1)
635 return set_error(serror, SCRIPT_ERR_UNBALANCED_CONDITIONAL);
636 valtype& vch = stacktop(-1);
637+ // Tapscript requires minimal IF/NOTIF inputs as a consensus rule.
638+ if (sigversion == SigVersion::TAPSCRIPT) {
639+ if (vch.size() > 1 || (vch.size() == 1 && vch[0] != 1)) {
332dc13bdc perhaps add this additional code documentation from BIP342 to clarify the intention of the code
0 // Tapscript requires minimal IF/NOTIF inputs as a consensus rule.
1 if (sigversion == SigVersion::TAPSCRIPT) {
2+ // The input argument to the OP_IF and OP_NOTIF opcodes must be either
3+ // exactly 0 (the empty vector) or exactly 1 (the one-byte vector with value 1).
4 if (vch.size() > 1 || (vch.size() == 1 && vch[0] != 1)) {
1565+
1566+ // Additional data for BIP 342 signatures
1567+ if (sigversion == SigVersion::TAPSCRIPT) {
1568+ assert(execdata.m_tapleaf_hash_init);
1569+ ss << execdata.m_tapleaf_hash;
1570+ assert(key_version == 0); // key_version must be 0 for now
332dc13bdc perhaps add this additional info from BIP 342
0- assert(key_version == 0); // key_version must be 0 for now
1+ // key_version must be 0 for now, representing the current version of
2+ // public keys in the tapscript signature opcode execution.
3+ assert(key_version == 0);
335+bool IsOpSuccess(const opcodetype& opcode)
336+{
337+ return opcode == 80 || opcode == 98 || (opcode >= 126 && opcode <= 129) ||
338+ (opcode >= 131 && opcode <= 134) || (opcode >= 137 && opcode <= 138) ||
339+ (opcode >= 141 && opcode <= 142) || (opcode >= 149 && opcode <= 153) ||
340+ (opcode >= 187 && opcode <= 254);
332dc13b maybe simplify
0 return opcode == 80 || opcode == 98 || (opcode >= 126 && opcode <= 129) ||
1- (opcode >= 131 && opcode <= 134) || (opcode >= 137 && opcode <= 138) ||
2- (opcode >= 141 && opcode <= 142) || (opcode >= 149 && opcode <= 153) ||
3+ (opcode >= 131 && opcode <= 134) || opcode == 137 || opcode == 138 ||
4+ opcode == 141 || opcode == 142 || (opcode >= 149 && opcode <= 153) ||
5 (opcode >= 187 && opcode <= 254);
IIRC the text as-is completely “matches” the BIP text, meaning if it gives a range here, it gives a range in the BIP text. I think as-is is easier to pattern match.
80, 98, 126-129, 131-134, 137-138, 141-142, 149-153, 187-254
I made a few more changes related to signature checking:
key_version (currently always 0) is no longer passed as an argument into SignatureHashSchnorr, because if a new one was introduced, it would need a new SigVersion as well. So instead use the latter to derive the key_version. @ariard This partially reverts an earlier comment you had, but I think the comments make it clearer still.ScriptError in a few more places.As always, details of the changes are in #19997.
1834 if (!CastToBool(stack.back())) return set_error(serror, SCRIPT_ERR_EVAL_FALSE);
1835 return true;
1836 }
1837
1838-static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion, const std::vector<unsigned char>& program, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* serror)
1839+static bool VerifyTaprootCommitment(const std::vector<unsigned char>& control, const std::vector<unsigned char>& program, const CScript& script, uint256* tapleaf_hash)
tapleaf_hash passed as a pointer with a non-null check? This function is always called with a non-null tapleaf_hash, so it’d make more sense to pass by reference.
1550+ spent_outputs.emplace_back(coin.out);
1551+ }
1552+ txdata.Init(tx, std::move(spent_outputs));
1553 }
1554
1555 for (unsigned int i = 0; i < tx.vin.size(); i++) {
in 6b0f2a4320aebe1b802763a559cbaf3c348c2ffc:
Not sure if it’s needed but could add an assert for extra caution:
0assert(txdata.m_spent_outputs.size() == tx.vin.size());
1754+ return set_error(serror, SCRIPT_ERR_TAPROOT_WRONG_CONTROL_SIZE);
1755+ }
1756+ if (!VerifyTaprootCommitment(control, program, exec_script)) {
1757+ return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH);
1758+ }
1759+ if (flags & SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_TAPROOT_VERSION) {
in 68f87cb0da326bcaa2570ed6299a7ee1c6d7b5f6:
nit: this could be at the beginning of the else block I think
409+}
410+
411+/** Helper for OP_CHECKSIG, OP_CHECKSIGVERIFY, and (in Tapscript) OP_CHECKSIGADD.
412+ *
413+ * A return value of false means the script fails entirely. When true is returned, the
414+ * fSuccess variable indicates whether the signature check itself succeeded.
in c3825c1bc41815d9b27d9a5dc36e46165b2f5861:
0 * success variable indicates whether the signature check itself succeeded.
95+# Specifically, a context object is a dict that maps names to compositions of:
96+# - values
97+# - lists of values
98+# - callables which, when fed the context object as argument, produce any of these
99+#
100+# # The DEFAULT_CONTEXT object specifies a standard signing process, with many overridable knobs.
in 58c90569f75221bc4652cbde5cad4dbae543a1ca:
nit
0# The DEFAULT_CONTEXT object specifies a standard signing process, with many overridable knobs.
1198+ the transaction. This is accomplished by constructing transactions consisting
1199+ of all valid inputs, except one invalid one.
1200+ """
1201+
1202+ # Generate some coins to fund the wallet.
1203+ node.generate(10)
in 58c90569f75221bc4652cbde5cad4dbae543a1ca:
There are already some 101 blocks mined on the taproot node to fund it earlier and then funds are transferred to the non-taproot node to fund it. I guess this generate can be removed and the blocks could be mined earlier?
1236+
1237+ fund_tx = CTransaction()
1238+ # Add the 50 highest-value inputs
1239+ unspents = node.listunspent()
1240+ random.shuffle(unspents)
1241+ unspents.sort(key=lambda x: -int(x["amount"] * 100000000))
in 58c90569f75221bc4652cbde5cad4dbae543a1ca:
0 unspents.sort(key=lambda x: int(x["amount"] * 100000000), reverse=True)
1064+ ("1001push_nop", CScript([OP_0] * 1001 + [OP_NOP])),
1065+ ]
1066+ random.shuffle(scripts)
1067+ tap = taproot_construct(pubs[0], scripts)
1068+ add_spender(spenders, "opsuccess/bare", standard=False, tap=tap, leaf="bare_success", failure={"leaf": "bare_nop"}, **ERR_CLEANSTACK)
1069+ add_spender(spenders, "opsuccess/exexecif", standard=False, tap=tap, leaf="unexecif_success", failure={"leaf": "unexecif_nop"}, **ERR_CLEANSTACK)
in 58c90569f75221bc4652cbde5cad4dbae543a1ca:
probably?
0 add_spender(spenders, "opsuccess/unexecif", standard=False, tap=tap, leaf="unexecif_success", failure={"leaf": "unexecif_nop"}, **ERR_CLEANSTACK)
1418+ if (output_type == SIGHASH_ALL) {
1419+ ss << cache.m_outputs_single_hash;
1420+ }
1421+
1422+ // Data about the input/prevout being spent
1423+ const auto* witstack = &tx_to.vin[in_pos].scriptWitness.stack;
const auto& witstack = tx_to.[...] which should effectively have the same result, except as a C++ ref rather than a pointer.
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.
This adds the TaggedHash function as defined by BIP340 to the hash module, which
is used in BIP340 and BIP341 to produce domain-separated hashes.
Re-ACK sans the fuccess typo.
0diff --git a/src/pubkey.cpp b/src/pubkey.cpp
1index 689328765..4d734fc89 100644
2--- a/src/pubkey.cpp
3+++ b/src/pubkey.cpp
4@@ -173,7 +173,8 @@ XOnlyPubKey::XOnlyPubKey(Span<const unsigned char> bytes)
5 std::copy(bytes.begin(), bytes.end(), m_keydata.begin());
6 }
7
8-bool XOnlyPubKey::VerifySchnorr(const uint256& msg, Span<const unsigned char> sigbytes) const {
9+bool XOnlyPubKey::VerifySchnorr(const uint256& msg, Span<const unsigned char> sigbytes) const
10+{
11 assert(sigbytes.size() == 64);
12 secp256k1_xonly_pubkey pubkey;
13 if (!secp256k1_xonly_pubkey_parse(secp256k1_context_verify, &pubkey, m_keydata.data())) return false;
14diff --git a/src/pubkey.h b/src/pubkey.h
15index 65f3fdf38..0f784b86e 100644
16--- a/src/pubkey.h
17+++ b/src/pubkey.h
18@@ -207,7 +207,8 @@ public:
19 bool Derive(CPubKey& pubkeyChild, ChainCode &ccChild, unsigned int nChild, const ChainCode& cc) const;
20 };
21
22-class XOnlyPubKey {
23+class XOnlyPubKey
24+{
25 private:
26 uint256 m_keydata;
27
28diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
29index 92994a56e..1067a5293 100644
30--- a/src/script/interpreter.cpp
31+++ b/src/script/interpreter.cpp
32@@ -392,13 +392,13 @@ static bool EvalChecksigTapscript(const valtype& sig, const valtype& pubkey, Scr
33 return set_error(serror, SCRIPT_ERR_PUBKEYTYPE);
34 } else if (pubkey.size() == 32) {
35 if (success && !checker.CheckSchnorrSignature(sig, pubkey, sigversion, execdata, serror)) {
36- return false;
37+ return false; // serror is set
38 }
39 } else {
40 /*
41 * New public key version softforks should be defined before this `else` block.
42 * Generally, the new code should not do anything but failing the script execution. To avoid
43- * consensus bugs, it should not modify any existing values (including success).
44+ * consensus bugs, it should not modify any existing values (including `success`).
45 */
46 if ((flags & SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_PUBKEYTYPE) != 0) {
47 return set_error(serror, SCRIPT_ERR_DISCOURAGE_UPGRADABLE_PUBKEYTYPE);
48@@ -411,7 +411,7 @@ static bool EvalChecksigTapscript(const valtype& sig, const valtype& pubkey, Scr
49 /** Helper for OP_CHECKSIG, OP_CHECKSIGVERIFY, and (in Tapscript) OP_CHECKSIGADD.
50 *
51 * A return value of false means the script fails entirely. When true is returned, the
52- * fSuccess variable indicates whether the signature check itself succeeded.
53+ * fuccess variable indicates whether the signature check itself succeeded.
54 */
55 static bool EvalChecksig(const valtype& sig, const valtype& pubkey, CScript::const_iterator pbegincodehash, CScript::const_iterator pend, ScriptExecutionData& execdata, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* serror, bool& success)
56 {
57@@ -1814,9 +1814,7 @@ static bool ExecuteWitnessScript(const Span<const valtype>& stack_span, const CS
58 }
59
60 // Tapscript enforces initial stack size limits (altstack is empty here)
61- if (stack.size() > MAX_STACK_SIZE) {
62- return set_error(serror, SCRIPT_ERR_STACK_SIZE);
63- }
64+ if (stack.size() > MAX_STACK_SIZE) return set_error(serror, SCRIPT_ERR_STACK_SIZE);
65 }
66
67 // Disallow stack item size > MAX_SCRIPT_ELEMENT_SIZE in witness stack
68@@ -1900,7 +1898,7 @@ static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion,
69 if (stack.size() == 1) {
70 // Key path spending (stack size is 1 after removing optional annex)
71 if (!checker.CheckSchnorrSignature(stack.front(), program, SigVersion::TAPROOT, execdata, serror)) {
72- return false;
73+ return false; // serror is set
74 }
75 return set_success(serror);
76 } else {
77diff --git a/src/validation.cpp b/src/validation.cpp
78index fdabff9bb..0b78ba677 100644
79--- a/src/validation.cpp
80+++ b/src/validation.cpp
81@@ -1550,6 +1550,7 @@ bool CheckInputScripts(const CTransaction& tx, TxValidationState &state, const C
82 }
83 txdata.Init(tx, std::move(spent_outputs));
84 }
85+ assert(txdata.m_spent_outputs.size() == tx.vin.size());
86
87 for (unsigned int i = 0; i < tx.vin.size(); i++) {
88
89diff --git a/test/functional/feature_taproot.py b/test/functional/feature_taproot.py
90index 82ccdae06..7b534c1c2 100755
91--- a/test/functional/feature_taproot.py
92+++ b/test/functional/feature_taproot.py
93@@ -100,7 +100,7 @@ import random
94 # - lists of values
95 # - callables which, when fed the context object as argument, produce any of these
96 #
97-# # The DEFAULT_CONTEXT object specifies a standard signing process, with many overridable knobs.
98+# The DEFAULT_CONTEXT object specifies a standard signing process, with many overridable knobs.
99 #
100 # The get(ctx, name) function can evaluate a name, and cache its result in the context.
101 # getter(name) can be used to construct a callable that evaluates name. For example:
102@@ -1070,7 +1070,7 @@ def spenders_taproot_active():
103 random.shuffle(scripts)
104 tap = taproot_construct(pubs[0], scripts)
105 add_spender(spenders, "opsuccess/bare", standard=False, tap=tap, leaf="bare_success", failure={"leaf": "bare_nop"}, **ERR_CLEANSTACK)
106- add_spender(spenders, "opsuccess/exexecif", standard=False, tap=tap, leaf="unexecif_success", failure={"leaf": "unexecif_nop"}, **ERR_CLEANSTACK)
107+ add_spender(spenders, "opsuccess/unexecif", standard=False, tap=tap, leaf="unexecif_success", failure={"leaf": "unexecif_nop"}, **ERR_CLEANSTACK)
108 add_spender(spenders, "opsuccess/return", standard=False, tap=tap, leaf="return_success", failure={"leaf": "return_nop"}, **ERR_OP_RETURN)
109 add_spender(spenders, "opsuccess/undecodable", standard=False, tap=tap, leaf="undecodable_success", failure={"leaf": "undecodable_nop"}, **ERR_UNDECODABLE)
110 add_spender(spenders, "opsuccess/undecodable_bypass", standard=False, tap=tap, leaf="undecodable_success", failure={"leaf": "undecodable_bypassed_success"}, **ERR_UNDECODABLE)
111@@ -1245,9 +1245,6 @@ class TaprootTest(BitcoinTestFramework):
112 of all valid inputs, except one invalid one.
113 """
114
115- # Generate some coins to fund the wallet.
116- node.generate(10)
117-
118 # Construct a bunch of sPKs that send coins back to the host wallet
119 self.log.info("- Constructing addresses for returning coins")
120 host_spks = []
121@@ -1284,7 +1281,7 @@ class TaprootTest(BitcoinTestFramework):
122 # Add the 50 highest-value inputs
123 unspents = node.listunspent()
124 random.shuffle(unspents)
125- unspents.sort(key=lambda x: -int(x["amount"] * 100000000))
126+ unspents.sort(key=lambda x: int(x["amount"] * 100000000), reverse=True)
127 if len(unspents) > 50:
128 unspents = unspents[:50]
129 random.shuffle(unspents)
411+}
412+
413+/** Helper for OP_CHECKSIG, OP_CHECKSIGVERIFY, and (in Tapscript) OP_CHECKSIGADD.
414+ *
415+ * A return value of false means the script fails entirely. When true is returned, the
416+ * fuccess variable indicates whether the signature check itself succeeded.
0 * success variable indicates whether the signature check itself succeeded.
1377@@ -1322,6 +1378,75 @@ template void PrecomputedTransactionData::Init(const CMutableTransaction& txTo,
1378 template PrecomputedTransactionData::PrecomputedTransactionData(const CTransaction& txTo);
1379 template PrecomputedTransactionData::PrecomputedTransactionData(const CMutableTransaction& txTo);
1380
1381+static const CHashWriter HASHER_TAPSIGHASH = TaggedHash("TapSighash");
1382+
1383+template<typename T>
1384+bool SignatureHashSchnorr(uint256& hash_out, const T& tx_to, uint32_t in_pos, uint8_t hash_type, SigVersion sigversion, uint8_t key_version, const PrecomputedTransactionData& cache)
In 614479450e911dba6938bb7feb85088229faf9b1 “Implement Taproot signature hashing (BIP 341)”
nit: remove key_version here. It is removed in the next commit anyways.
46@@ -47,7 +47,7 @@ static const uint32_t LOCKTIME_MAX = 0xFFFFFFFFU;
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+static constexpr unsigned int ANNEX_TAG = 0x50;
In 4e6196e53109ab4ebcfe64a88be6fcf2e3d7e2a6 “Implement Taproot validation (BIP 341)”
nit: move this change to the commit ANNEX_TAG was introduced.
light ACK cc036c251c16eda1cdc558db2049e8db0f3a50b7
Skimmed the tests, will review them in further detail soon.
This implements the new sighashing scheme from BIP341, with all relevant
whole-transaction values precomputed once and cached.
Includes changes to PrecomputedTransactionData by Pieter Wuille.
This enables the schnorrsig module in libsecp256k1, adds the relevant types
and functions to src/pubkey, as well as in higher-level `SignatureChecker`
classes. The (verification side of the) BIP340 test vectors is also added.
Code review ACK cc036c251c16eda1cdc558db2049e8db0f3a50b7
Hope I can get enough testing in soon to get to a full ACK.
This includes key path spending and script path spending, but not the
Tapscript execution implementation (leaf 0xc0 remains unemcumbered in
this commit).
Includes constants for various aspects of the consensus rules suggested
by Jeremy Rubin.
Instead of recomputing the annex hash every time a signature is verified, compute it
once and cache it in a new ScriptExecutionData structure.
This adds a new `SigVersion::TAPSCRIPT`, makes the necessary interpreter
changes to make it implement BIP342, and uses them for leaf version 0xc0
in Taproot script path spends.
This adds a `TxoutType::WITNESS_V1_TAPROOT` for P2TR outputs, and permits spending
them in standardness rules. No corresponding `CTxDestination` is added for it,
as that isn't needed until we want wallet integration. The taproot validation flags
are also enabled for mempool transactions, and standardness rules are added
(stack item size limit, no annexes).
Define a versionbits-based activation for the new consensus rules on regtest.
No activation or activation mechanism is defined for testnet or mainnet.
Add a pure Python implementation of BIP340 signing and verification, tested against
the BIP's test vectors.
A large functional test is added that automatically generates random transactions which
exercise various aspects of the new rules, and verifies they are accepted into the mempool
(when appropriate), and correctly accepted/rejected in (Python-constructed) blocks.
Includes sighashing code and many tests by Johnson Lau.
Includes a test by Matthew Zipkin.
Includes several tests and improvements by Greg Sanders.
This adds a unit test that does generic script verification tests,
with positive/negative witnesses/scriptsigs, under various flags.
The test data is large (several MB) so it's stored in the qa-assets
repo.
This adds a --dumptests flag to the feature_taproot.py test, to dump all its
generated test cases to files, in a format compatible with the
script_assets_test unit test. A fuzzer for said format is added as well, whose
primary purpose is coverage-based minimization of those dumps.
241@@ -223,7 +242,7 @@ def set(self, data):
242 p = SECP256K1.lift_x(x)
243 # if the oddness of the y co-ord isn't correct, find the other
244 # valid y
245- if (p[1] & 1) != (data[0] & 1):
246+ if data[0] & 1:
247 p = SECP256K1.negate(p)
In 3c226639eb134314a0640d34e4ccb6148dbde22f “tests: add BIP340 Schnorr signature support to test framework”
nit: The code here seems to be entirely unnecessary as lift_x ensures the evenness of y is correct. I commented out these 2 lines and no tests failed.
I think the only thing that’s wrong here is the comment: with this change, it’s not longer “correcting” the oddness; it’s just negating if an odd Y coordinate is desired.
The code is necessary though, but possibly untested. It’s what constructs a point from a compressed public key. It’s only used for ECDSA (as BIP340 public keys are x-only, not compressed), and unused in the current tests (which only use the signing side of ECDSA).
Going to leave this for a follow-up, as it’s not directly related to Taproot testing.
540+ aux_rand = bytes.fromhex(aux_rand_hex)
541+ try:
542+ sig_actual = sign_schnorr(seckey, msg, aux_rand)
543+ self.assertEqual(sig.hex(), sig_actual.hex(), "BIP340 test vector %i (%s): sig mismatch" % (i, comment))
544+ except RuntimeError as e:
545+ self.assertFalse("BIP340 test vector %i (%s): signing raised exception %s" % (i, comment, e))
In 3c226639eb134314a0640d34e4ccb6148dbde22f “tests: add BIP340 Schnorr signature support to test framework”
nit: This should be self.fail rather than assertFalse.
1544+ spent_outputs.reserve(tx.vin.size());
1545+
1546+ for (const auto& txin : tx.vin) {
1547+ const COutPoint& prevout = txin.prevout;
1548+ const Coin& coin = inputs.AccessCoin(prevout);
1549+ assert(!coin.IsSpent());
Note to other reviewers: even though this is a move from existing code, I was still curious about whether this assert is safe. There are three call-sites for CheckInputScripts(); here they are with the various ways they ensure the input coins aren’t already spent (and so this assert won’t blow up):
MemPoolAccept::PolicyScriptChecks(): only ever called from MemPoolAccept::AcceptSingleTransaction(), which makes a call to Consensus::CheckTxInputs() via MemPoolAccept::PreChecks() beforehand,CheckInputsFromMempoolAndCache(): only ever called from MemPoolAccept::ConsensusScriptChecks(), which is only ever called from AcceptSingleTransaction() (case above),CChainState::ConnectBlock(): call to Consensus::CheckTxInputs() beforehand1423+ const auto& witstack = tx_to.vin[in_pos].scriptWitness.stack;
1424+ bool have_annex = witstack.size() > 1 && witstack.back().size() > 0 && witstack.back()[0] == ANNEX_TAG;
1425+ const uint8_t spend_type = (ext_flag << 1) + (have_annex ? 1 : 0); // The low bit indicates whether an annex is present.
1426+ ss << spend_type;
1427+ if (input_type == SIGHASH_ANYONECANPAY) {
1428+ ss << tx_to.vin[in_pos].prevout;
1424+ bool have_annex = witstack.size() > 1 && witstack.back().size() > 0 && witstack.back()[0] == ANNEX_TAG;
1425+ const uint8_t spend_type = (ext_flag << 1) + (have_annex ? 1 : 0); // The low bit indicates whether an annex is present.
1426+ ss << spend_type;
1427+ if (input_type == SIGHASH_ANYONECANPAY) {
1428+ ss << tx_to.vin[in_pos].prevout;
1429+ ss << cache.m_spent_outputs[in_pos];
1430+ ss << tx_to.vin[in_pos].nSequence;
1431+ } else {
1432+ ss << in_pos;
1433+ }
1434+ if (have_annex) {
1435+ ss << (CHashWriter(SER_GETHASH, 0) << witstack.back()).GetSHA256();
That serialization code you link to:
Span<const unsigned char> as a fixed length object, without any length at all. It’s invoking the Stream function write(const unsigned char* data, size_t length), which writes the length bytes starting at data. It doesn’t write the length itself.std::vector<unsigned char>, not a Span<const unsigned char>), which has different serialization code a bit further down the file.
Hm yeah I guess I must be wrong because the tests encode in the right order (per ser_string’s definition). Maybe I’m looking at the wrong serializer.
Edit: yup, my mistake!
Partial review; more soon.
1681@@ -1679,14 +1682,35 @@ static bool ExecuteWitnessScript(const Span<const valtype>& stack_span, const CS
1682 return true;
1683 }
1684
1685-static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion, const std::vector<unsigned char>& program, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* serror)
1686+static bool VerifyTaprootCommitment(const std::vector<unsigned char>& control, const std::vector<unsigned char>& program, const CScript& script)
VerifyTaprootCommitment to take script as a const valtype& – future taproot versions might not look like current script at all.
1705+ return q.CheckPayToContract(p, k, control[0] & 1);
1706+}
1707+
1708+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)
1709+{
1710+ CScript exec_script; //!< Actually executed script (last stack item in P2WSH; implied P2PKH script in P2WPKH; leaf script in P2TR)
exec_script closer to its assignment, and make it const CScript exec_script(script_bytes.begin(), script_bytes.end()); for the p2wsh and p2tr cases.
836+ - a (name, CScript, leaf version) tuple
837+ - another list of items (with the same structure)
838+ - a function, which specifies how to compute the hashing partner
839+ in function of the hash of whatever it is combined with
840+
841+ Returns: script (sPK or redeemScript), tweak, {name:(script, leaf version, negation flag, innerkey, merklepath), ...}
tweak is returned in 4th position, after internal pubkey in 2nd and the negation flag in 3rd. Further it seems leaves are sorted on (script, version, merklebranch) and doesn’t rely on negation flag/ innerkey.
440+ * p2sh: whether the output is P2SH wrapper (this is supported even for Taproot, where it makes the output unencumbered)
441+ * spk_mutate_pre_psh: a callable to be applied to the script (before potentially P2SH-wrapping it)
442+ * failure: a dict of entries to override in the context when intentionally failing to spend (if None, no_fail will be set)
443+ * standard: whether the (valid version of) spending is expected to be standard
444+ * err_msg: a string with an expected error message for failure (or None, if not cared about)
445+ * sigops_weight: the pre-taproot sigops weight consumed by a successful spend
need_vin_vout_mismatch isn’t commented
1836-static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion, const std::vector<unsigned char>& program, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* serror)
1837+static bool VerifyTaprootCommitment(const std::vector<unsigned char>& control, const std::vector<unsigned char>& program, const CScript& script, uint256& tapleaf_hash)
1838 {
1839- CScript scriptPubKey;
1840+ const int path_len = (control.size() - TAPROOT_CONTROL_BASE_SIZE) / TAPROOT_CONTROL_NODE_SIZE;
1841+ const XOnlyPubKey p{uint256(std::vector<unsigned char>(control.begin() + 1, control.begin() + TAPROOT_CONTROL_BASE_SIZE))};
+1 would be great. Like “Exclude parity bit from internal pubkey”
169@@ -169,7 +170,7 @@ class CPubKey
170 /*
171 * Check syntactic correctness.
172 *
173- * Note that this is consensus critical as CheckSig() calls it!
174+ * Note that this is consensus critical as CheckECDSASignature() calls it!
*this intentional?
381+ * the script execution fails when using non-empty invalid signature.
382+ */
383+ success = !sig.empty();
384+ if (success) {
385+ // Implement the sigops/witnesssize ratio test.
386+ // Passing with an upgradable public key version is also counted.
if (success) branch ?
398+ }
399+ } else {
400+ /*
401+ * New public key version softforks should be defined before this `else` block.
402+ * Generally, the new code should not do anything but failing the script execution. To avoid
403+ * consensus bugs, it should not modify any existing values (including `success`).
Code Review ACK 0e2a5e4. Mainly reviewed change since my last review in #17977 at 84ec870.
One thing I’m still inquiring is scope of test coverage. I’ve started to look at it only now and it’s still trying to map if every spec object is correctly covered. I’ll try if I can come with any comment improvement suggestion.
205@@ -206,6 +206,7 @@ bool IsWitnessStandard(const CTransaction& tx, const CCoinsViewCache& mapInputs)
206 // get the scriptPubKey corresponding to this input:
207 CScript prevScript = prev.scriptPubKey;
208
209+ bool p2sh = false;
nit in commit e9a021d7e6:
Why not directly assign this with the correct value?
0const bool p2sh{prevScript.IsPayToScriptHash()};
238@@ -237,6 +239,36 @@ bool IsWitnessStandard(const CTransaction& tx, const CCoinsViewCache& mapInputs)
239 return false;
240 }
241 }
242+
243+ // Check policy limits for Taproot spends:
same commit:
You are modifying what this function is doing, so the comment in validation is no longer applicable and should probably be adjusted.
0 // Check for non-standard witness in P2WSH
521+ self.assertFalse(verify_schnorr(verify_pubkey, sig, msg))
522+
523+ def test_schnorr_testvectors(self):
524+ """Implement the BIP340 test vectors (read from bip340_test_vectors.csv)."""
525+ num_tests = 0
526+ with open(os.path.join(sys.path[0], 'test_framework', 'bip340_test_vectors.csv'), newline='', encoding='utf8') as csvfile:
I can’t run the tests here:
0test]$ python -m unittest functional/test_framework/key.py
1.E
2======================================================================
3ERROR: test_schnorr_testvectors (functional.test_framework.key.TestFrameworkKey)
4Implement the BIP340 test vectors (read from bip340_test_vectors.csv).
5----------------------------------------------------------------------
6Traceback (most recent call last):
7 File "test/functional/test_framework/key.py", line 526, in test_schnorr_testvectors
8 with open(os.path.join(sys.path[0], 'test_framework', 'bip340_test_vectors.csv'), newline='', encoding='utf8') as csvfile:
9FileNotFoundError: [Errno 2] No such file or directory: 'test/test_framework/bip340_test_vectors.csv'
10
11----------------------------------------------------------------------
12Ran 2 tests in 0.775s
13
14FAILED (errors=1)
What about this diff:
0diff --git a/test/functional/test_framework/key.py b/test/functional/test_framework/key.py
1index a6bc187985..ceaaa474ff 100644
2--- a/test/functional/test_framework/key.py
3+++ b/test/functional/test_framework/key.py
4@@ -523,7 +523,7 @@ class TestFrameworkKey(unittest.TestCase):
5 def test_schnorr_testvectors(self):
6 """Implement the BIP340 test vectors (read from bip340_test_vectors.csv)."""
7 num_tests = 0
8- with open(os.path.join(sys.path[0], 'test_framework', 'bip340_test_vectors.csv'), newline='', encoding='utf8') as csvfile:
9+ with open(os.path.join(os.path.dirname(os.path.realpath(__file__)), 'bip340_test_vectors.csv'), newline='', encoding='utf8') as csvfile:
10 reader = csv.reader(csvfile)
11 next(reader)
12 for row in reader:
21+ ss += ss
22+ ss += data
23+ return hashlib.sha256(ss).digest()
24+
25+def xor_bytes(b0, b1):
26+ return bytes(x ^ y for (x, y) in zip(b0, b1))
1152+
1153+ def set_test_params(self):
1154+ self.num_nodes = 2
1155+ self.setup_clean_chain = True
1156+ # Node 0 has Taproot inactive, Node 1 active.
1157+ self.extra_args = [["-whitelist=127.0.0.1", "-par=1", "-vbparams=taproot:1:1"], ["-whitelist=127.0.0.1", "-par=1"]]
1387+ assert len(normal_utxos) == 0
1388+ assert len(mismatching_utxos) == 0
1389+ self.log.info(" - Done")
1390+
1391+ def run_test(self):
1392+ self.connect_nodes(0, 1)
1082@@ -1082,6 +1083,12 @@ test_fuzz_script_interpreter_LDADD = $(FUZZ_SUITE_LD_COMMON)
1083 test_fuzz_script_interpreter_LDFLAGS = $(FUZZ_SUITE_LDFLAGS_COMMON)
1084 test_fuzz_script_interpreter_SOURCES = test/fuzz/script_interpreter.cpp
1085
1086+test_fuzz_script_assets_test_minimizer_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES)
1087+test_fuzz_script_assets_test_minimizer_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)
1088+test_fuzz_script_assets_test_minimizer_LDADD = $(FUZZ_SUITE_LD_COMMON)
1089+test_fuzz_script_assets_test_minimizer_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS)
Concept ACK 0e2a5e448f
left some questions in the test commits
1689+ for (const auto flags : ALL_CONSENSUS_FLAGS) {
1690+ // "final": true tests are valid for all flags. Others are only valid with flags that are
1691+ // a subset of test_flags.
1692+ if (fin || ((flags & test_flags) == flags)) {
1693+ bool ret = VerifyScript(tx.vin[idx].scriptSig, prevouts[idx].scriptPubKey, &tx.vin[idx].scriptWitness, flags, txcheck, nullptr);
1694+ BOOST_CHECK(ret);
Can you explain what the point of this unit test is? It seems that the python test is used to generate inputs for the fuzz test, which is used to minimize the corpus. The resulting corpus is fed into the unit test.
However, the unit test and fuzz test do the same thing. If they didn’t, the fuzz test couldn’t be used to capture the coverage.
I think the unit test (all changes in this commit) can be reverted if the fuzz asserts the ret return code directly.
If the fuzz tests would assert the return code directly, they wouldn’t be usable in fuzzing mode, and likely cause people to file bug reports if they’d try to run them. As is, the fuzz tests are just for assessing coverage, and can be used either as test directly (only covering things caught by sanitizers), or used to minimize a corpus generated externally (with known validity/invalidity). Only the latter can be used as a unit test.
So I think the differences are:
with known validity/invalidity
Oh, I missed that the validity flag is included in the seed itself. Makes sense now.
The unit test can be run without building in fuzz mode.
Heh, I am pretty sure the developers that have the seed dir cloned, run the unit tests, but not the fuzz tests is an empty set.
775+ ss += sha256(ser_string(annex))
776+ if out_type == SIGHASH_SINGLE:
777+ if input_index < len(txTo.vout):
778+ ss += sha256(txTo.vout[input_index].serialize())
779+ else:
780+ ss += bytes(0 for _ in range(32))
Post-merge comment/question after stumbling upon this while looking at the test framework code:
Is using 32 zero bytes instead of correct BIP341 behaviour (i.e. failing) intentional here ?
The code does not seem accidental, as it is not copied from legacy sighash function, and if I stick assert 0 here, the test/functional/feature_taproot.py test fails, but it is not clear from the backtrace where exactly, a lot of deep_eval() in that backtrace.
If this is intentional, I think that a comment with explanation was in order here, to avoid confusion for the readers of the code.
If this was not intentional, then even if does not cause problems now, it might result in incorrect test behaviour in the future
I think it’s testing that a SIGHASH_SINGLE signature without a corresponding output will fail, even if you generate an otherwise reasonable looking signature. If you change it to bytes(42 for _ in range(32)) rather than an assert 0, the tests will still pass, demonstrating the exact value used isn’t important. (If you change the length to something other than 32, you’ll get an assertion failure slightly later when the length of hashed data is tested)
See the need_vin_vout_mismatch argument to make_spender(), which is set to True in the “Test SIGHASH_SINGLE behavior in combination with mismatching outputs” section. If you disable those two spenders, then adding the assert 0 when there isn’t a corresponding output works fine.
It is very much looks like you are correct, these two tests depend on this behavior of TaprootSignatureHash.
Without any comment explaining this, It will confuse people who read only a part of the code. Some people might copy that code and have problems later. I only cross-referenced this code with C++ implementation in Core while writing my own implementation in python, but I think it is definitely a possibility that someone may just copy the whole TaprootSignatureHash, and maybe even without looking at the comments. Other possibility might be that TaprootSignatureHash is reused for some another purpose inside the test framework without taking this behavior into account.
Might it be better to just do add_spender( ... , failure={"hashtype_actual": hashtype, "sighash": lambda(ctx): b"\x00"*32}, ... ) for these two tests ? It is not that TaprootSignatureHash itself is tested here, AFAIU, and expected behavior is incorrect hash returned, so why not just return it right away ? Alternative might be a special flag in the context “invalid sighash expected instead of failure”. Or at least a comment with explanation inside TaprootSignatureHash, to spare readers from confusion.