diff options
44 files changed, 2985 insertions, 121 deletions
diff --git a/build_msvc/libsecp256k1/libsecp256k1.vcxproj b/build_msvc/libsecp256k1/libsecp256k1.vcxproj index 99fb63fb02..c42918d6e1 100644 --- a/build_msvc/libsecp256k1/libsecp256k1.vcxproj +++ b/build_msvc/libsecp256k1/libsecp256k1.vcxproj @@ -12,7 +12,7 @@ </ItemGroup> <ItemDefinitionGroup> <ClCompile> - <PreprocessorDefinitions>ENABLE_MODULE_ECDH;ENABLE_MODULE_RECOVERY;%(PreprocessorDefinitions)</PreprocessorDefinitions> + <PreprocessorDefinitions>ENABLE_MODULE_ECDH;ENABLE_MODULE_RECOVERY;ENABLE_MODULE_EXTRAKEYS;ENABLE_MODULE_SCHNORRSIG;%(PreprocessorDefinitions)</PreprocessorDefinitions> <AdditionalIncludeDirectories>..\..\src\secp256k1;%(AdditionalIncludeDirectories)</AdditionalIncludeDirectories> </ClCompile> </ItemDefinitionGroup> diff --git a/ci/test/04_install.sh b/ci/test/04_install.sh index d3566914ac..632bccf574 100755 --- a/ci/test/04_install.sh +++ b/ci/test/04_install.sh @@ -81,11 +81,10 @@ else fi if [ ! -d ${DIR_QA_ASSETS} ]; then - if [ "$RUN_FUZZ_TESTS" = "true" ]; then - DOCKER_EXEC git clone https://github.com/bitcoin-core/qa-assets ${DIR_QA_ASSETS} - fi + DOCKER_EXEC git clone --depth=1 https://github.com/bitcoin-core/qa-assets ${DIR_QA_ASSETS} fi export DIR_FUZZ_IN=${DIR_QA_ASSETS}/fuzz_seed_corpus/ +export DIR_UNIT_TEST_DATA=${DIR_QA_ASSETS}/unit_test_data/ DOCKER_EXEC mkdir -p "${BASE_SCRATCH_DIR}/sanitizer-output/" diff --git a/ci/test/06_script_b.sh b/ci/test/06_script_b.sh index 6c14a3dfbe..607a2820dd 100755 --- a/ci/test/06_script_b.sh +++ b/ci/test/06_script_b.sh @@ -23,13 +23,13 @@ fi if [ "$RUN_UNIT_TESTS" = "true" ]; then BEGIN_FOLD unit-tests - DOCKER_EXEC LD_LIBRARY_PATH=$DEPENDS_DIR/$HOST/lib make $MAKEJOBS check VERBOSE=1 + DOCKER_EXEC DIR_UNIT_TEST_DATA=${DIR_UNIT_TEST_DATA} LD_LIBRARY_PATH=$DEPENDS_DIR/$HOST/lib make $MAKEJOBS check VERBOSE=1 END_FOLD fi if [ "$RUN_UNIT_TESTS_SEQUENTIAL" = "true" ]; then BEGIN_FOLD unit-tests-seq - DOCKER_EXEC LD_LIBRARY_PATH=$DEPENDS_DIR/$HOST/lib "${BASE_BUILD_DIR}/bitcoin-*/src/test/test_bitcoin*" --catch_system_errors=no -l test_suite + DOCKER_EXEC DIR_UNIT_TEST_DATA=${DIR_UNIT_TEST_DATA} LD_LIBRARY_PATH=$DEPENDS_DIR/$HOST/lib "${BASE_BUILD_DIR}/bitcoin-*/src/test/test_bitcoin*" --catch_system_errors=no -l test_suite END_FOLD fi diff --git a/configure.ac b/configure.ac index 6db9dab404..ab40991ce4 100644 --- a/configure.ac +++ b/configure.ac @@ -1700,7 +1700,7 @@ if test x$need_bundled_univalue = xyes; then AC_CONFIG_SUBDIRS([src/univalue]) fi -ac_configure_args="${ac_configure_args} --disable-shared --with-pic --enable-benchmark=no --with-bignum=no --enable-module-recovery" +ac_configure_args="${ac_configure_args} --disable-shared --with-pic --enable-benchmark=no --with-bignum=no --enable-module-recovery --enable-module-schnorrsig --enable-experimental" AC_CONFIG_SUBDIRS([src/secp256k1]) AC_OUTPUT diff --git a/src/Makefile.test.include b/src/Makefile.test.include index 835b12ce3e..7fac78f973 100644 --- a/src/Makefile.test.include +++ b/src/Makefile.test.include @@ -129,6 +129,7 @@ FUZZ_TARGETS = \ test/fuzz/script_deserialize \ test/fuzz/script_flags \ test/fuzz/script_interpreter \ + test/fuzz/script_assets_test_minimizer \ test/fuzz/script_ops \ test/fuzz/script_sigcache \ test/fuzz/script_sign \ @@ -1083,6 +1084,12 @@ test_fuzz_script_interpreter_LDADD = $(FUZZ_SUITE_LD_COMMON) test_fuzz_script_interpreter_LDFLAGS = $(FUZZ_SUITE_LDFLAGS_COMMON) test_fuzz_script_interpreter_SOURCES = test/fuzz/script_interpreter.cpp +test_fuzz_script_assets_test_minimizer_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) +test_fuzz_script_assets_test_minimizer_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) +test_fuzz_script_assets_test_minimizer_LDADD = $(FUZZ_SUITE_LD_COMMON) +test_fuzz_script_assets_test_minimizer_LDFLAGS = $(RELDFLAGS) $(AM_LDFLAGS) $(LIBTOOL_APP_LDFLAGS) +test_fuzz_script_assets_test_minimizer_SOURCES = test/fuzz/script_assets_test_minimizer.cpp + test_fuzz_script_ops_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) test_fuzz_script_ops_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS) test_fuzz_script_ops_LDADD = $(FUZZ_SUITE_LD_COMMON) diff --git a/src/chainparams.cpp b/src/chainparams.cpp index ef501e9de2..a34bf350fc 100644 --- a/src/chainparams.cpp +++ b/src/chainparams.cpp @@ -86,6 +86,11 @@ public: consensus.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].nStartTime = 1199145601; // January 1, 2008 consensus.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].nTimeout = 1230767999; // December 31, 2008 + // Deployment of Taproot (BIPs 340-342) + consensus.vDeployments[Consensus::DEPLOYMENT_TAPROOT].bit = 2; + consensus.vDeployments[Consensus::DEPLOYMENT_TAPROOT].nStartTime = 1199145601; // January 1, 2008 + consensus.vDeployments[Consensus::DEPLOYMENT_TAPROOT].nTimeout = 1230767999; // December 31, 2008 + // The best chain should have at least this much work. consensus.nMinimumChainWork = uint256S("0x00000000000000000000000000000000000000000e1ab5ec9348e9f4b8eb8154"); @@ -197,6 +202,11 @@ public: consensus.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].nStartTime = 1199145601; // January 1, 2008 consensus.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].nTimeout = 1230767999; // December 31, 2008 + // Deployment of Taproot (BIPs 340-342) + consensus.vDeployments[Consensus::DEPLOYMENT_TAPROOT].bit = 2; + consensus.vDeployments[Consensus::DEPLOYMENT_TAPROOT].nStartTime = 1199145601; // January 1, 2008 + consensus.vDeployments[Consensus::DEPLOYMENT_TAPROOT].nTimeout = 1230767999; // December 31, 2008 + // The best chain should have at least this much work. consensus.nMinimumChainWork = uint256S("0x0000000000000000000000000000000000000000000001495c1d5a01e2af8a23"); @@ -380,6 +390,9 @@ public: consensus.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].bit = 28; consensus.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].nStartTime = 0; consensus.vDeployments[Consensus::DEPLOYMENT_TESTDUMMY].nTimeout = Consensus::BIP9Deployment::NO_TIMEOUT; + consensus.vDeployments[Consensus::DEPLOYMENT_TAPROOT].bit = 2; + consensus.vDeployments[Consensus::DEPLOYMENT_TAPROOT].nStartTime = Consensus::BIP9Deployment::ALWAYS_ACTIVE; + consensus.vDeployments[Consensus::DEPLOYMENT_TAPROOT].nTimeout = Consensus::BIP9Deployment::NO_TIMEOUT; // The best chain should have at least this much work. consensus.nMinimumChainWork = uint256S("0x00"); diff --git a/src/consensus/params.h b/src/consensus/params.h index 85ab3f61ef..932f0d2c60 100644 --- a/src/consensus/params.h +++ b/src/consensus/params.h @@ -14,6 +14,7 @@ namespace Consensus { enum DeploymentPos { DEPLOYMENT_TESTDUMMY, + DEPLOYMENT_TAPROOT, // Deployment of Schnorr/Taproot (BIPs 340-342) // NOTE: Also add new deployments to VersionBitsDeploymentInfo in versionbits.cpp MAX_VERSION_BITS_DEPLOYMENTS }; diff --git a/src/hash.cpp b/src/hash.cpp index 83b90ae063..3657b38639 100644 --- a/src/hash.cpp +++ b/src/hash.cpp @@ -6,6 +6,7 @@ #include <crypto/common.h> #include <crypto/hmac_sha512.h> +#include <string> inline uint32_t ROTL32(uint32_t x, int8_t r) { @@ -84,3 +85,12 @@ uint256 SHA256Uint256(const uint256& input) CSHA256().Write(input.begin(), 32).Finalize(result.begin()); return result; } + +CHashWriter TaggedHash(const std::string& tag) +{ + CHashWriter writer(SER_GETHASH, 0); + uint256 taghash; + CSHA256().Write((const unsigned char*)tag.data(), tag.size()).Finalize(taghash.begin()); + writer << taghash << taghash; + return writer; +} diff --git a/src/hash.h b/src/hash.h index c16bbb48ce..6d876076ee 100644 --- a/src/hash.h +++ b/src/hash.h @@ -15,6 +15,7 @@ #include <uint256.h> #include <version.h> +#include <string> #include <vector> typedef uint256 ChainCode; @@ -202,4 +203,12 @@ unsigned int MurmurHash3(unsigned int nHashSeed, Span<const unsigned char> vData void BIP32Hash(const ChainCode &chainCode, unsigned int nChild, unsigned char header, const unsigned char data[32], unsigned char output[64]); +/** Return a CHashWriter primed for tagged hashes (as specified in BIP 340). + * + * The returned object will have SHA256(tag) written to it twice (= 64 bytes). + * A tagged hash can be computed by feeding the message into this object, and + * then calling CHashWriter::GetSHA256(). + */ +CHashWriter TaggedHash(const std::string& tag); + #endif // BITCOIN_HASH_H diff --git a/src/policy/policy.cpp b/src/policy/policy.cpp index 0e9820da1e..69f2b456f1 100644 --- a/src/policy/policy.cpp +++ b/src/policy/policy.cpp @@ -9,7 +9,7 @@ #include <consensus/validation.h> #include <coins.h> - +#include <span.h> CAmount GetDustThreshold(const CTxOut& txout, const CFeeRate& dustRelayFeeIn) { @@ -206,6 +206,7 @@ bool IsWitnessStandard(const CTransaction& tx, const CCoinsViewCache& mapInputs) // get the scriptPubKey corresponding to this input: CScript prevScript = prev.scriptPubKey; + bool p2sh = false; if (prevScript.IsPayToScriptHash()) { std::vector <std::vector<unsigned char> > stack; // If the scriptPubKey is P2SH, we try to extract the redeemScript casually by converting the scriptSig @@ -216,6 +217,7 @@ bool IsWitnessStandard(const CTransaction& tx, const CCoinsViewCache& mapInputs) if (stack.empty()) return false; prevScript = CScript(stack.back().begin(), stack.back().end()); + p2sh = true; } int witnessversion = 0; @@ -237,6 +239,36 @@ bool IsWitnessStandard(const CTransaction& tx, const CCoinsViewCache& mapInputs) return false; } } + + // Check policy limits for Taproot spends: + // - MAX_STANDARD_TAPSCRIPT_STACK_ITEM_SIZE limit for stack item size + // - No annexes + if (witnessversion == 1 && witnessprogram.size() == WITNESS_V1_TAPROOT_SIZE && !p2sh) { + // Taproot spend (non-P2SH-wrapped, version 1, witness program size 32; see BIP 341) + auto stack = MakeSpan(tx.vin[i].scriptWitness.stack); + if (stack.size() >= 2 && !stack.back().empty() && stack.back()[0] == ANNEX_TAG) { + // Annexes are nonstandard as long as no semantics are defined for them. + return false; + } + if (stack.size() >= 2) { + // Script path spend (2 or more stack elements after removing optional annex) + const auto& control_block = SpanPopBack(stack); + SpanPopBack(stack); // Ignore script + if (control_block.empty()) return false; // Empty control block is invalid + if ((control_block[0] & TAPROOT_LEAF_MASK) == TAPROOT_LEAF_TAPSCRIPT) { + // Leaf version 0xc0 (aka Tapscript, see BIP 342) + for (const auto& item : stack) { + if (item.size() > MAX_STANDARD_TAPSCRIPT_STACK_ITEM_SIZE) return false; + } + } + } else if (stack.size() == 1) { + // Key path spend (1 stack element after removing optional annex) + // (no policy rules apply) + } else { + // 0 stack elements; this is already invalid by consensus rules + return false; + } + } } return true; } diff --git a/src/policy/policy.h b/src/policy/policy.h index 7f168ee20f..51d67b9390 100644 --- a/src/policy/policy.h +++ b/src/policy/policy.h @@ -40,6 +40,8 @@ static const bool DEFAULT_PERMIT_BAREMULTISIG = true; static const unsigned int MAX_STANDARD_P2WSH_STACK_ITEMS = 100; /** The maximum size of each witness stack item in a standard P2WSH script */ static const unsigned int MAX_STANDARD_P2WSH_STACK_ITEM_SIZE = 80; +/** The maximum size of each witness stack item in a standard BIP 342 script (Taproot, leaf version 0xc0) */ +static const unsigned int MAX_STANDARD_TAPSCRIPT_STACK_ITEM_SIZE = 80; /** The maximum size of a standard witnessScript */ static const unsigned int MAX_STANDARD_P2WSH_SCRIPT_SIZE = 3600; /** Min feerate for defining dust. Historically this has been based on the @@ -68,7 +70,11 @@ static constexpr unsigned int STANDARD_SCRIPT_VERIFY_FLAGS = MANDATORY_SCRIPT_VE SCRIPT_VERIFY_WITNESS | SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM | SCRIPT_VERIFY_WITNESS_PUBKEYTYPE | - SCRIPT_VERIFY_CONST_SCRIPTCODE; + SCRIPT_VERIFY_CONST_SCRIPTCODE | + SCRIPT_VERIFY_TAPROOT | + SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_TAPROOT_VERSION | + SCRIPT_VERIFY_DISCOURAGE_OP_SUCCESS | + SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_PUBKEYTYPE; /** For convenience, standard but not mandatory verify flags. */ static constexpr unsigned int STANDARD_NOT_MANDATORY_VERIFY_FLAGS = STANDARD_SCRIPT_VERIFY_FLAGS & ~MANDATORY_SCRIPT_VERIFY_FLAGS; diff --git a/src/pubkey.cpp b/src/pubkey.cpp index fc14f41a0c..4d734fc891 100644 --- a/src/pubkey.cpp +++ b/src/pubkey.cpp @@ -7,6 +7,7 @@ #include <secp256k1.h> #include <secp256k1_recovery.h> +#include <secp256k1_schnorrsig.h> namespace { @@ -166,6 +167,27 @@ int ecdsa_signature_parse_der_lax(const secp256k1_context* ctx, secp256k1_ecdsa_ return 1; } +XOnlyPubKey::XOnlyPubKey(Span<const unsigned char> bytes) +{ + assert(bytes.size() == 32); + std::copy(bytes.begin(), bytes.end(), m_keydata.begin()); +} + +bool XOnlyPubKey::VerifySchnorr(const uint256& msg, Span<const unsigned char> sigbytes) const +{ + assert(sigbytes.size() == 64); + secp256k1_xonly_pubkey pubkey; + if (!secp256k1_xonly_pubkey_parse(secp256k1_context_verify, &pubkey, m_keydata.data())) return false; + return secp256k1_schnorrsig_verify(secp256k1_context_verify, sigbytes.data(), msg.begin(), &pubkey); +} + +bool XOnlyPubKey::CheckPayToContract(const XOnlyPubKey& base, const uint256& hash, bool parity) const +{ + secp256k1_xonly_pubkey base_point; + if (!secp256k1_xonly_pubkey_parse(secp256k1_context_verify, &base_point, base.data())) return false; + return secp256k1_xonly_pubkey_tweak_add_check(secp256k1_context_verify, m_keydata.begin(), parity, &base_point, hash.begin()); +} + bool CPubKey::Verify(const uint256 &hash, const std::vector<unsigned char>& vchSig) const { if (!IsValid()) return false; diff --git a/src/pubkey.h b/src/pubkey.h index fcbc7e8416..0f784b86e4 100644 --- a/src/pubkey.h +++ b/src/pubkey.h @@ -9,6 +9,7 @@ #include <hash.h> #include <serialize.h> +#include <span.h> #include <uint256.h> #include <stdexcept> @@ -169,7 +170,7 @@ public: /* * Check syntactic correctness. * - * Note that this is consensus critical as CheckSig() calls it! + * Note that this is consensus critical as CheckECDSASignature() calls it! */ bool IsValid() const { @@ -206,6 +207,27 @@ public: bool Derive(CPubKey& pubkeyChild, ChainCode &ccChild, unsigned int nChild, const ChainCode& cc) const; }; +class XOnlyPubKey +{ +private: + uint256 m_keydata; + +public: + /** Construct an x-only pubkey from exactly 32 bytes. */ + XOnlyPubKey(Span<const unsigned char> bytes); + + /** Verify a Schnorr signature against this public key. + * + * sigbytes must be exactly 64 bytes. + */ + bool VerifySchnorr(const uint256& msg, Span<const unsigned char> sigbytes) const; + bool CheckPayToContract(const XOnlyPubKey& base, const uint256& hash, bool parity) const; + + const unsigned char& operator[](int pos) const { return *(m_keydata.begin() + pos); } + const unsigned char* data() const { return m_keydata.begin(); } + size_t size() const { return m_keydata.size(); } +}; + struct CExtPubKey { unsigned char nDepth; unsigned char vchFingerprint[4]; diff --git a/src/rpc/blockchain.cpp b/src/rpc/blockchain.cpp index 1fbddc1ceb..a162c1ee70 100644 --- a/src/rpc/blockchain.cpp +++ b/src/rpc/blockchain.cpp @@ -1354,6 +1354,7 @@ RPCHelpMan getblockchaininfo() BuriedForkDescPushBack(softforks, "csv", consensusParams.CSVHeight); BuriedForkDescPushBack(softforks, "segwit", consensusParams.SegwitHeight); BIP9SoftForkDescPushBack(softforks, "testdummy", consensusParams, Consensus::DEPLOYMENT_TESTDUMMY); + BIP9SoftForkDescPushBack(softforks, "taproot", consensusParams, Consensus::DEPLOYMENT_TAPROOT); obj.pushKV("softforks", softforks); obj.pushKV("warnings", GetWarnings(false).original); diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp index 50a6192476..5735e7df66 100644 --- a/src/script/interpreter.cpp +++ b/src/script/interpreter.cpp @@ -342,13 +342,10 @@ public: }; } -/** Helper for OP_CHECKSIG and OP_CHECKSIGVERIFY - * - * A return value of false means the script fails entirely. When true is returned, the - * fSuccess variable indicates whether the signature check itself succeeded. - */ -static bool EvalChecksig(const valtype& vchSig, const valtype& vchPubKey, CScript::const_iterator pbegincodehash, CScript::const_iterator pend, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* serror, bool& fSuccess) +static bool EvalChecksigPreTapscript(const valtype& vchSig, const valtype& vchPubKey, CScript::const_iterator pbegincodehash, CScript::const_iterator pend, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* serror, bool& fSuccess) { + assert(sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0); + // Subset of script starting at the most recent codeseparator CScript scriptCode(pbegincodehash, pend); @@ -363,7 +360,7 @@ static bool EvalChecksig(const valtype& vchSig, const valtype& vchPubKey, CScrip //serror is set return false; } - fSuccess = checker.CheckSig(vchSig, vchPubKey, scriptCode, sigversion); + fSuccess = checker.CheckECDSASignature(vchSig, vchPubKey, scriptCode, sigversion); if (!fSuccess && (flags & SCRIPT_VERIFY_NULLFAIL) && vchSig.size()) return set_error(serror, SCRIPT_ERR_SIG_NULLFAIL); @@ -371,7 +368,67 @@ static bool EvalChecksig(const valtype& vchSig, const valtype& vchPubKey, CScrip return true; } -bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* serror) +static bool EvalChecksigTapscript(const valtype& sig, const valtype& pubkey, ScriptExecutionData& execdata, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* serror, bool& success) +{ + assert(sigversion == SigVersion::TAPSCRIPT); + + /* + * The following validation sequence is consensus critical. Please note how -- + * upgradable public key versions precede other rules; + * the script execution fails when using empty signature with invalid public key; + * the script execution fails when using non-empty invalid signature. + */ + success = !sig.empty(); + if (success) { + // Implement the sigops/witnesssize ratio test. + // Passing with an upgradable public key version is also counted. + assert(execdata.m_validation_weight_left_init); + execdata.m_validation_weight_left -= VALIDATION_WEIGHT_PER_SIGOP_PASSED; + if (execdata.m_validation_weight_left < 0) { + return set_error(serror, SCRIPT_ERR_TAPSCRIPT_VALIDATION_WEIGHT); + } + } + if (pubkey.size() == 0) { + return set_error(serror, SCRIPT_ERR_PUBKEYTYPE); + } else if (pubkey.size() == 32) { + if (success && !checker.CheckSchnorrSignature(sig, pubkey, sigversion, execdata, serror)) { + return false; // serror is set + } + } else { + /* + * New public key version softforks should be defined before this `else` block. + * Generally, the new code should not do anything but failing the script execution. To avoid + * consensus bugs, it should not modify any existing values (including `success`). + */ + if ((flags & SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_PUBKEYTYPE) != 0) { + return set_error(serror, SCRIPT_ERR_DISCOURAGE_UPGRADABLE_PUBKEYTYPE); + } + } + + return true; +} + +/** Helper for OP_CHECKSIG, OP_CHECKSIGVERIFY, and (in Tapscript) OP_CHECKSIGADD. + * + * A return value of false means the script fails entirely. When true is returned, the + * success variable indicates whether the signature check itself succeeded. + */ +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) +{ + switch (sigversion) { + case SigVersion::BASE: + case SigVersion::WITNESS_V0: + return EvalChecksigPreTapscript(sig, pubkey, pbegincodehash, pend, flags, checker, sigversion, serror, success); + case SigVersion::TAPSCRIPT: + return EvalChecksigTapscript(sig, pubkey, execdata, flags, checker, sigversion, serror, success); + case SigVersion::TAPROOT: + // Key path spending in Taproot has no script, so this is unreachable. + break; + } + assert(false); +} + +bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptExecutionData& execdata, ScriptError* serror) { static const CScriptNum bnZero(0); static const CScriptNum bnOne(1); @@ -381,6 +438,9 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& // static const valtype vchZero(0); static const valtype vchTrue(1, 1); + // sigversion cannot be TAPROOT here, as it admits no script execution. + assert(sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0 || sigversion == SigVersion::TAPSCRIPT); + CScript::const_iterator pc = script.begin(); CScript::const_iterator pend = script.end(); CScript::const_iterator pbegincodehash = script.begin(); @@ -389,15 +449,18 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& ConditionStack vfExec; std::vector<valtype> altstack; set_error(serror, SCRIPT_ERR_UNKNOWN_ERROR); - if (script.size() > MAX_SCRIPT_SIZE) + if ((sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0) && script.size() > MAX_SCRIPT_SIZE) { return set_error(serror, SCRIPT_ERR_SCRIPT_SIZE); + } int nOpCount = 0; bool fRequireMinimal = (flags & SCRIPT_VERIFY_MINIMALDATA) != 0; + uint32_t opcode_pos = 0; + execdata.m_codeseparator_pos = 0xFFFFFFFFUL; + execdata.m_codeseparator_pos_init = true; try { - while (pc < pend) - { + for (; pc < pend; ++opcode_pos) { bool fExec = vfExec.all_true(); // @@ -408,9 +471,12 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& if (vchPushValue.size() > MAX_SCRIPT_ELEMENT_SIZE) return set_error(serror, SCRIPT_ERR_PUSH_SIZE); - // Note how OP_RESERVED does not count towards the opcode limit. - if (opcode > OP_16 && ++nOpCount > MAX_OPS_PER_SCRIPT) - return set_error(serror, SCRIPT_ERR_OP_COUNT); + if (sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0) { + // Note how OP_RESERVED does not count towards the opcode limit. + if (opcode > OP_16 && ++nOpCount > MAX_OPS_PER_SCRIPT) { + return set_error(serror, SCRIPT_ERR_OP_COUNT); + } + } if (opcode == OP_CAT || opcode == OP_SUBSTR || @@ -568,6 +634,15 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& if (stack.size() < 1) return set_error(serror, SCRIPT_ERR_UNBALANCED_CONDITIONAL); valtype& vch = stacktop(-1); + // Tapscript requires minimal IF/NOTIF inputs as a consensus rule. + if (sigversion == SigVersion::TAPSCRIPT) { + // The input argument to the OP_IF and OP_NOTIF opcodes must be either + // exactly 0 (the empty vector) or exactly 1 (the one-byte vector with value 1). + if (vch.size() > 1 || (vch.size() == 1 && vch[0] != 1)) { + return set_error(serror, SCRIPT_ERR_TAPSCRIPT_MINIMALIF); + } + } + // Under witness v0 rules it is only a policy rule, enabled through SCRIPT_VERIFY_MINIMALIF. if (sigversion == SigVersion::WITNESS_V0 && (flags & SCRIPT_VERIFY_MINIMALIF)) { if (vch.size() > 1) return set_error(serror, SCRIPT_ERR_MINIMALIF); @@ -1001,6 +1076,7 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& // Hash starts after the code separator pbegincodehash = pc; + execdata.m_codeseparator_pos = opcode_pos; } break; @@ -1015,7 +1091,7 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& valtype& vchPubKey = stacktop(-1); bool fSuccess = true; - if (!EvalChecksig(vchSig, vchPubKey, pbegincodehash, pend, flags, checker, sigversion, serror, fSuccess)) return false; + if (!EvalChecksig(vchSig, vchPubKey, pbegincodehash, pend, execdata, flags, checker, sigversion, serror, fSuccess)) return false; popstack(stack); popstack(stack); stack.push_back(fSuccess ? vchTrue : vchFalse); @@ -1029,9 +1105,32 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& } break; + case OP_CHECKSIGADD: + { + // OP_CHECKSIGADD is only available in Tapscript + if (sigversion == SigVersion::BASE || sigversion == SigVersion::WITNESS_V0) return set_error(serror, SCRIPT_ERR_BAD_OPCODE); + + // (sig num pubkey -- num) + if (stack.size() < 3) return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION); + + const valtype& sig = stacktop(-3); + const CScriptNum num(stacktop(-2), fRequireMinimal); + const valtype& pubkey = stacktop(-1); + + bool success = true; + if (!EvalChecksig(sig, pubkey, pbegincodehash, pend, execdata, flags, checker, sigversion, serror, success)) return false; + popstack(stack); + popstack(stack); + popstack(stack); + stack.push_back((num + (success ? 1 : 0)).getvch()); + } + break; + case OP_CHECKMULTISIG: case OP_CHECKMULTISIGVERIFY: { + if (sigversion == SigVersion::TAPSCRIPT) return set_error(serror, SCRIPT_ERR_TAPSCRIPT_CHECKMULTISIG); + // ([sig ...] num_of_signatures [pubkey ...] num_of_pubkeys -- bool) int i = 1; @@ -1089,7 +1188,7 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& } // Check signature - bool fOk = checker.CheckSig(vchSig, vchPubKey, scriptCode, sigversion); + bool fOk = checker.CheckECDSASignature(vchSig, vchPubKey, scriptCode, sigversion); if (fOk) { isig++; @@ -1159,6 +1258,12 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& return set_success(serror); } +bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* serror) +{ + ScriptExecutionData execdata; + return EvalScript(stack, script, flags, checker, sigversion, execdata, serror); +} + namespace { /** @@ -1291,35 +1396,183 @@ uint256 GetOutputsSHA256(const T& txTo) return ss.GetSHA256(); } +/** Compute the (single) SHA256 of the concatenation of all amounts spent by a tx. */ +uint256 GetSpentAmountsSHA256(const std::vector<CTxOut>& outputs_spent) +{ + CHashWriter ss(SER_GETHASH, 0); + for (const auto& txout : outputs_spent) { + ss << txout.nValue; + } + return ss.GetSHA256(); +} + +/** Compute the (single) SHA256 of the concatenation of all scriptPubKeys spent by a tx. */ +uint256 GetSpentScriptsSHA256(const std::vector<CTxOut>& outputs_spent) +{ + CHashWriter ss(SER_GETHASH, 0); + for (const auto& txout : outputs_spent) { + ss << txout.scriptPubKey; + } + return ss.GetSHA256(); +} + + } // namespace template <class T> -void PrecomputedTransactionData::Init(const T& txTo) +void PrecomputedTransactionData::Init(const T& txTo, std::vector<CTxOut>&& spent_outputs) { - assert(!m_ready); + assert(!m_spent_outputs_ready); - // Cache is calculated only for transactions with witness - if (txTo.HasWitness()) { - hashPrevouts = SHA256Uint256(GetPrevoutsSHA256(txTo)); - hashSequence = SHA256Uint256(GetSequencesSHA256(txTo)); - hashOutputs = SHA256Uint256(GetOutputsSHA256(txTo)); + m_spent_outputs = std::move(spent_outputs); + if (!m_spent_outputs.empty()) { + assert(m_spent_outputs.size() == txTo.vin.size()); + m_spent_outputs_ready = true; } - m_ready = true; + // Determine which precomputation-impacting features this transaction uses. + bool uses_bip143_segwit = false; + bool uses_bip341_taproot = false; + for (size_t inpos = 0; inpos < txTo.vin.size(); ++inpos) { + if (!txTo.vin[inpos].scriptWitness.IsNull()) { + if (m_spent_outputs_ready && m_spent_outputs[inpos].scriptPubKey.size() == 2 + WITNESS_V1_TAPROOT_SIZE && + m_spent_outputs[inpos].scriptPubKey[0] == OP_1) { + // Treat every witness-bearing spend with 34-byte scriptPubKey that starts with OP_1 as a Taproot + // spend. This only works if spent_outputs was provided as well, but if it wasn't, actual validation + // will fail anyway. Note that this branch may trigger for scriptPubKeys that aren't actually segwit + // but in that case validation will fail as SCRIPT_ERR_WITNESS_UNEXPECTED anyway. + uses_bip341_taproot = true; + } else { + // Treat every spend that's not known to native witness v1 as a Witness v0 spend. This branch may + // also be taken for unknown witness versions, but it is harmless, and being precise would require + // P2SH evaluation to find the redeemScript. + uses_bip143_segwit = true; + } + } + if (uses_bip341_taproot && uses_bip143_segwit) break; // No need to scan further if we already need all. + } + + if (uses_bip143_segwit || uses_bip341_taproot) { + // Computations shared between both sighash schemes. + m_prevouts_single_hash = GetPrevoutsSHA256(txTo); + m_sequences_single_hash = GetSequencesSHA256(txTo); + m_outputs_single_hash = GetOutputsSHA256(txTo); + } + if (uses_bip143_segwit) { + hashPrevouts = SHA256Uint256(m_prevouts_single_hash); + hashSequence = SHA256Uint256(m_sequences_single_hash); + hashOutputs = SHA256Uint256(m_outputs_single_hash); + m_bip143_segwit_ready = true; + } + if (uses_bip341_taproot) { + m_spent_amounts_single_hash = GetSpentAmountsSHA256(m_spent_outputs); + m_spent_scripts_single_hash = GetSpentScriptsSHA256(m_spent_outputs); + m_bip341_taproot_ready = true; + } } template <class T> PrecomputedTransactionData::PrecomputedTransactionData(const T& txTo) { - Init(txTo); + Init(txTo, {}); } // explicit instantiation -template void PrecomputedTransactionData::Init(const CTransaction& txTo); -template void PrecomputedTransactionData::Init(const CMutableTransaction& txTo); +template void PrecomputedTransactionData::Init(const CTransaction& txTo, std::vector<CTxOut>&& spent_outputs); +template void PrecomputedTransactionData::Init(const CMutableTransaction& txTo, std::vector<CTxOut>&& spent_outputs); template PrecomputedTransactionData::PrecomputedTransactionData(const CTransaction& txTo); template PrecomputedTransactionData::PrecomputedTransactionData(const CMutableTransaction& txTo); +static const CHashWriter HASHER_TAPSIGHASH = TaggedHash("TapSighash"); +static const CHashWriter HASHER_TAPLEAF = TaggedHash("TapLeaf"); +static const CHashWriter HASHER_TAPBRANCH = TaggedHash("TapBranch"); +static const CHashWriter HASHER_TAPTWEAK = TaggedHash("TapTweak"); + +template<typename T> +bool SignatureHashSchnorr(uint256& hash_out, const ScriptExecutionData& execdata, const T& tx_to, uint32_t in_pos, uint8_t hash_type, SigVersion sigversion, const PrecomputedTransactionData& cache) +{ + uint8_t ext_flag, key_version; + switch (sigversion) { + case SigVersion::TAPROOT: + ext_flag = 0; + // key_version is not used and left uninitialized. + break; + case SigVersion::TAPSCRIPT: + ext_flag = 1; + // key_version must be 0 for now, representing the current version of + // 32-byte public keys in the tapscript signature opcode execution. + // An upgradable public key version (with a size not 32-byte) may + // request a different key_version with a new sigversion. + key_version = 0; + break; + default: + assert(false); + } + assert(in_pos < tx_to.vin.size()); + assert(cache.m_bip341_taproot_ready && cache.m_spent_outputs_ready); + + CHashWriter ss = HASHER_TAPSIGHASH; + + // Epoch + static constexpr uint8_t EPOCH = 0; + ss << EPOCH; + + // Hash type + 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 + const uint8_t input_type = hash_type & SIGHASH_INPUT_MASK; + if (!(hash_type <= 0x03 || (hash_type >= 0x81 && hash_type <= 0x83))) return false; + ss << hash_type; + + // Transaction level data + ss << tx_to.nVersion; + ss << tx_to.nLockTime; + if (input_type != SIGHASH_ANYONECANPAY) { + ss << cache.m_prevouts_single_hash; + ss << cache.m_spent_amounts_single_hash; + ss << cache.m_spent_scripts_single_hash; + ss << cache.m_sequences_single_hash; + } + if (output_type == SIGHASH_ALL) { + ss << cache.m_outputs_single_hash; + } + + // Data about the input/prevout being spent + assert(execdata.m_annex_init); + const bool have_annex = execdata.m_annex_present; + const uint8_t spend_type = (ext_flag << 1) + (have_annex ? 1 : 0); // The low bit indicates whether an annex is present. + ss << spend_type; + if (input_type == SIGHASH_ANYONECANPAY) { + ss << tx_to.vin[in_pos].prevout; + ss << cache.m_spent_outputs[in_pos]; + ss << tx_to.vin[in_pos].nSequence; + } else { + ss << in_pos; + } + if (have_annex) { + ss << execdata.m_annex_hash; + } + + // Data about the output (if only one). + if (output_type == SIGHASH_SINGLE) { + if (in_pos >= tx_to.vout.size()) return false; + CHashWriter sha_single_output(SER_GETHASH, 0); + sha_single_output << tx_to.vout[in_pos]; + ss << sha_single_output.GetSHA256(); + } + + // Additional data for BIP 342 signatures + if (sigversion == SigVersion::TAPSCRIPT) { + assert(execdata.m_tapleaf_hash_init); + ss << execdata.m_tapleaf_hash; + ss << key_version; + assert(execdata.m_codeseparator_pos_init); + ss << execdata.m_codeseparator_pos; + } + + hash_out = ss.GetSHA256(); + return true; +} + template <class T> uint256 SignatureHash(const CScript& scriptCode, const T& txTo, unsigned int nIn, int nHashType, const CAmount& amount, SigVersion sigversion, const PrecomputedTransactionData* cache) { @@ -1329,7 +1582,7 @@ uint256 SignatureHash(const CScript& scriptCode, const T& txTo, unsigned int nIn uint256 hashPrevouts; uint256 hashSequence; uint256 hashOutputs; - const bool cacheready = cache && cache->m_ready; + const bool cacheready = cache && cache->m_bip143_segwit_ready; if (!(nHashType & SIGHASH_ANYONECANPAY)) { hashPrevouts = cacheready ? cache->hashPrevouts : SHA256Uint256(GetPrevoutsSHA256(txTo)); @@ -1389,13 +1642,19 @@ uint256 SignatureHash(const CScript& scriptCode, const T& txTo, unsigned int nIn } template <class T> -bool GenericTransactionSignatureChecker<T>::VerifySignature(const std::vector<unsigned char>& vchSig, const CPubKey& pubkey, const uint256& sighash) const +bool GenericTransactionSignatureChecker<T>::VerifyECDSASignature(const std::vector<unsigned char>& vchSig, const CPubKey& pubkey, const uint256& sighash) const { return pubkey.Verify(sighash, vchSig); } template <class T> -bool GenericTransactionSignatureChecker<T>::CheckSig(const std::vector<unsigned char>& vchSigIn, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const +bool GenericTransactionSignatureChecker<T>::VerifySchnorrSignature(Span<const unsigned char> sig, const XOnlyPubKey& pubkey, const uint256& sighash) const +{ + return pubkey.VerifySchnorr(sighash, sig); +} + +template <class T> +bool GenericTransactionSignatureChecker<T>::CheckECDSASignature(const std::vector<unsigned char>& vchSigIn, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const { CPubKey pubkey(vchPubKey); if (!pubkey.IsValid()) @@ -1410,13 +1669,41 @@ bool GenericTransactionSignatureChecker<T>::CheckSig(const std::vector<unsigned uint256 sighash = SignatureHash(scriptCode, *txTo, nIn, nHashType, amount, sigversion, this->txdata); - if (!VerifySignature(vchSig, pubkey, sighash)) + if (!VerifyECDSASignature(vchSig, pubkey, sighash)) return false; return true; } template <class T> +bool GenericTransactionSignatureChecker<T>::CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey_in, SigVersion sigversion, const ScriptExecutionData& execdata, ScriptError* serror) const +{ + assert(sigversion == SigVersion::TAPROOT || sigversion == SigVersion::TAPSCRIPT); + // Schnorr signatures have 32-byte public keys. The caller is responsible for enforcing this. + assert(pubkey_in.size() == 32); + // Note that in Tapscript evaluation, empty signatures are treated specially (invalid signature that does not + // abort script execution). This is implemented in EvalChecksigTapscript, which won't invoke + // CheckSchnorrSignature in that case. In other contexts, they are invalid like every other signature with + // size different from 64 or 65. + if (sig.size() != 64 && sig.size() != 65) return set_error(serror, SCRIPT_ERR_SCHNORR_SIG_SIZE); + + XOnlyPubKey pubkey{pubkey_in}; + + uint8_t hashtype = SIGHASH_DEFAULT; + if (sig.size() == 65) { + hashtype = SpanPopBack(sig); + if (hashtype == SIGHASH_DEFAULT) return set_error(serror, SCRIPT_ERR_SCHNORR_SIG_HASHTYPE); + } + uint256 sighash; + assert(this->txdata); + if (!SignatureHashSchnorr(sighash, execdata, *txTo, nIn, hashtype, sigversion, *this->txdata)) { + return set_error(serror, SCRIPT_ERR_SCHNORR_SIG_HASHTYPE); + } + if (!VerifySchnorrSignature(sig, pubkey, sighash)) return set_error(serror, SCRIPT_ERR_SCHNORR_SIG); + return true; +} + +template <class T> bool GenericTransactionSignatureChecker<T>::CheckLockTime(const CScriptNum& nLockTime) const { // There are two kinds of nLockTime: lock-by-blockheight @@ -1504,17 +1791,39 @@ bool GenericTransactionSignatureChecker<T>::CheckSequence(const CScriptNum& nSeq template class GenericTransactionSignatureChecker<CTransaction>; template class GenericTransactionSignatureChecker<CMutableTransaction>; -static bool ExecuteWitnessScript(const Span<const valtype>& stack_span, const CScript& scriptPubKey, unsigned int flags, SigVersion sigversion, const BaseSignatureChecker& checker, ScriptError* serror) +static bool ExecuteWitnessScript(const Span<const valtype>& stack_span, const CScript& scriptPubKey, unsigned int flags, SigVersion sigversion, const BaseSignatureChecker& checker, ScriptExecutionData& execdata, ScriptError* serror) { std::vector<valtype> stack{stack_span.begin(), stack_span.end()}; + if (sigversion == SigVersion::TAPSCRIPT) { + // OP_SUCCESSx processing overrides everything, including stack element size limits + CScript::const_iterator pc = scriptPubKey.begin(); + while (pc < scriptPubKey.end()) { + opcodetype opcode; + if (!scriptPubKey.GetOp(pc, opcode)) { + // Note how this condition would not be reached if an unknown OP_SUCCESSx was found + return set_error(serror, SCRIPT_ERR_BAD_OPCODE); + } + // New opcodes will be listed here. May use a different sigversion to modify existing opcodes. + if (IsOpSuccess(opcode)) { + if (flags & SCRIPT_VERIFY_DISCOURAGE_OP_SUCCESS) { + return set_error(serror, SCRIPT_ERR_DISCOURAGE_OP_SUCCESS); + } + return set_success(serror); + } + } + + // Tapscript enforces initial stack size limits (altstack is empty here) + if (stack.size() > MAX_STACK_SIZE) return set_error(serror, SCRIPT_ERR_STACK_SIZE); + } + // Disallow stack item size > MAX_SCRIPT_ELEMENT_SIZE in witness stack for (const valtype& elem : stack) { if (elem.size() > MAX_SCRIPT_ELEMENT_SIZE) return set_error(serror, SCRIPT_ERR_PUSH_SIZE); } // Run the script interpreter. - if (!EvalScript(stack, scriptPubKey, flags, checker, sigversion, serror)) return false; + if (!EvalScript(stack, scriptPubKey, flags, checker, sigversion, execdata, serror)) return false; // Scripts inside witness implicitly require cleanstack behaviour if (stack.size() != 1) return set_error(serror, SCRIPT_ERR_CLEANSTACK); @@ -1522,40 +1831,104 @@ static bool ExecuteWitnessScript(const Span<const valtype>& stack_span, const CS return true; } -static bool VerifyWitnessProgram(const CScriptWitness& witness, int witversion, const std::vector<unsigned char>& program, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* serror) +static bool VerifyTaprootCommitment(const std::vector<unsigned char>& control, const std::vector<unsigned char>& program, const CScript& script, uint256& tapleaf_hash) { - CScript scriptPubKey; + const int path_len = (control.size() - TAPROOT_CONTROL_BASE_SIZE) / TAPROOT_CONTROL_NODE_SIZE; + const XOnlyPubKey p{uint256(std::vector<unsigned char>(control.begin() + 1, control.begin() + TAPROOT_CONTROL_BASE_SIZE))}; + const XOnlyPubKey q{uint256(program)}; + tapleaf_hash = (CHashWriter(HASHER_TAPLEAF) << uint8_t(control[0] & TAPROOT_LEAF_MASK) << script).GetSHA256(); + uint256 k = tapleaf_hash; + for (int i = 0; i < path_len; ++i) { + CHashWriter ss_branch{HASHER_TAPBRANCH}; + Span<const unsigned char> node(control.data() + TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * i, TAPROOT_CONTROL_NODE_SIZE); + if (std::lexicographical_compare(k.begin(), k.end(), node.begin(), node.end())) { + ss_branch << k << node; + } else { + ss_branch << node << k; + } + k = ss_branch.GetSHA256(); + } + k = (CHashWriter(HASHER_TAPTWEAK) << MakeSpan(p) << k).GetSHA256(); + return q.CheckPayToContract(p, k, control[0] & 1); +} + +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) +{ + CScript exec_script; //!< Actually executed script (last stack item in P2WSH; implied P2PKH script in P2WPKH; leaf script in P2TR) Span<const valtype> stack{witness.stack}; + ScriptExecutionData execdata; if (witversion == 0) { if (program.size() == WITNESS_V0_SCRIPTHASH_SIZE) { - // Version 0 segregated witness program: SHA256(CScript) inside the program, CScript + inputs in witness + // BIP141 P2WSH: 32-byte witness v0 program (which encodes SHA256(script)) if (stack.size() == 0) { return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_WITNESS_EMPTY); } const valtype& script_bytes = SpanPopBack(stack); - scriptPubKey = CScript(script_bytes.begin(), script_bytes.end()); - uint256 hashScriptPubKey; - CSHA256().Write(&scriptPubKey[0], scriptPubKey.size()).Finalize(hashScriptPubKey.begin()); - if (memcmp(hashScriptPubKey.begin(), program.data(), 32)) { + exec_script = CScript(script_bytes.begin(), script_bytes.end()); + uint256 hash_exec_script; + CSHA256().Write(&exec_script[0], exec_script.size()).Finalize(hash_exec_script.begin()); + if (memcmp(hash_exec_script.begin(), program.data(), 32)) { return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH); } - return ExecuteWitnessScript(stack, scriptPubKey, flags, SigVersion::WITNESS_V0, checker, serror); + return ExecuteWitnessScript(stack, exec_script, flags, SigVersion::WITNESS_V0, checker, execdata, serror); } else if (program.size() == WITNESS_V0_KEYHASH_SIZE) { - // Special case for pay-to-pubkeyhash; signature + pubkey in witness + // BIP141 P2WPKH: 20-byte witness v0 program (which encodes Hash160(pubkey)) if (stack.size() != 2) { return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH); // 2 items in witness } - scriptPubKey << OP_DUP << OP_HASH160 << program << OP_EQUALVERIFY << OP_CHECKSIG; - return ExecuteWitnessScript(stack, scriptPubKey, flags, SigVersion::WITNESS_V0, checker, serror); + exec_script << OP_DUP << OP_HASH160 << program << OP_EQUALVERIFY << OP_CHECKSIG; + return ExecuteWitnessScript(stack, exec_script, flags, SigVersion::WITNESS_V0, checker, execdata, serror); } else { return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_WRONG_LENGTH); } + } else if (witversion == 1 && program.size() == WITNESS_V1_TAPROOT_SIZE && !is_p2sh) { + // BIP341 Taproot: 32-byte non-P2SH witness v1 program (which encodes a P2C-tweaked pubkey) + if (!(flags & SCRIPT_VERIFY_TAPROOT)) return set_success(serror); + if (stack.size() == 0) return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_WITNESS_EMPTY); + if (stack.size() >= 2 && !stack.back().empty() && stack.back()[0] == ANNEX_TAG) { + // Drop annex (this is non-standard; see IsWitnessStandard) + const valtype& annex = SpanPopBack(stack); + execdata.m_annex_hash = (CHashWriter(SER_GETHASH, 0) << annex).GetSHA256(); + execdata.m_annex_present = true; + } else { + execdata.m_annex_present = false; + } + execdata.m_annex_init = true; + if (stack.size() == 1) { + // Key path spending (stack size is 1 after removing optional annex) + if (!checker.CheckSchnorrSignature(stack.front(), program, SigVersion::TAPROOT, execdata, serror)) { + return false; // serror is set + } + return set_success(serror); + } else { + // Script path spending (stack size is >1 after removing optional annex) + const valtype& control = SpanPopBack(stack); + const valtype& script_bytes = SpanPopBack(stack); + exec_script = CScript(script_bytes.begin(), script_bytes.end()); + if (control.size() < TAPROOT_CONTROL_BASE_SIZE || control.size() > TAPROOT_CONTROL_MAX_SIZE || ((control.size() - TAPROOT_CONTROL_BASE_SIZE) % TAPROOT_CONTROL_NODE_SIZE) != 0) { + return set_error(serror, SCRIPT_ERR_TAPROOT_WRONG_CONTROL_SIZE); + } + if (!VerifyTaprootCommitment(control, program, exec_script, execdata.m_tapleaf_hash)) { + return set_error(serror, SCRIPT_ERR_WITNESS_PROGRAM_MISMATCH); + } + execdata.m_tapleaf_hash_init = true; + if ((control[0] & TAPROOT_LEAF_MASK) == TAPROOT_LEAF_TAPSCRIPT) { + // Tapscript (leaf version 0xc0) + execdata.m_validation_weight_left = ::GetSerializeSize(witness.stack, PROTOCOL_VERSION) + VALIDATION_WEIGHT_OFFSET; + execdata.m_validation_weight_left_init = true; + return ExecuteWitnessScript(stack, exec_script, flags, SigVersion::TAPSCRIPT, checker, execdata, serror); + } + if (flags & SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_TAPROOT_VERSION) { + return set_error(serror, SCRIPT_ERR_DISCOURAGE_UPGRADABLE_TAPROOT_VERSION); + } + return set_success(serror); + } } else { if (flags & SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM) { return set_error(serror, SCRIPT_ERR_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM); } - // Higher version witness scripts return true for future softfork compatibility + // Other version/size/p2sh combinations return true for future softfork compatibility return true; } // There is intentionally no return statement here, to be able to use "control reaches end of non-void function" warnings to detect gaps in the logic above. @@ -1601,7 +1974,7 @@ bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const C // The scriptSig must be _exactly_ CScript(), otherwise we reintroduce malleability. return set_error(serror, SCRIPT_ERR_WITNESS_MALLEATED); } - if (!VerifyWitnessProgram(*witness, witnessversion, witnessprogram, flags, checker, serror)) { + if (!VerifyWitnessProgram(*witness, witnessversion, witnessprogram, flags, checker, serror, /* is_p2sh */ false)) { return false; } // Bypass the cleanstack check at the end. The actual stack is obviously not clean @@ -1646,7 +2019,7 @@ bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const C // reintroduce malleability. return set_error(serror, SCRIPT_ERR_WITNESS_MALLEATED_P2SH); } - if (!VerifyWitnessProgram(*witness, witnessversion, witnessprogram, flags, checker, serror)) { + if (!VerifyWitnessProgram(*witness, witnessversion, witnessprogram, flags, checker, serror, /* is_p2sh */ true)) { return false; } // Bypass the cleanstack check at the end. The actual stack is obviously not clean diff --git a/src/script/interpreter.h b/src/script/interpreter.h index 71f2436369..c0c2b012c6 100644 --- a/src/script/interpreter.h +++ b/src/script/interpreter.h @@ -7,14 +7,17 @@ #define BITCOIN_SCRIPT_INTERPRETER_H #include <script/script_error.h> +#include <span.h> #include <primitives/transaction.h> #include <vector> #include <stdint.h> class CPubKey; +class XOnlyPubKey; class CScript; class CTransaction; +class CTxOut; class uint256; /** Signature hash types/flags */ @@ -24,6 +27,10 @@ enum SIGHASH_NONE = 2, SIGHASH_SINGLE = 3, SIGHASH_ANYONECANPAY = 0x80, + + SIGHASH_DEFAULT = 0, //!< Taproot only; implied when sighash byte is missing, and equivalent to SIGHASH_ALL + SIGHASH_OUTPUT_MASK = 3, + SIGHASH_INPUT_MASK = 0x80, }; /** Script verification flags. @@ -79,6 +86,8 @@ enum // "Exactly one stack element must remain, and when interpreted as a boolean, it must be true". // (BIP62 rule 6) // Note: CLEANSTACK should never be used without P2SH or WITNESS. + // Note: WITNESS_V0 and TAPSCRIPT script execution have behavior similar to CLEANSTACK as part of their + // consensus rules. It is automatic there and does not need this flag. SCRIPT_VERIFY_CLEANSTACK = (1U << 8), // Verify CHECKLOCKTIMEVERIFY @@ -101,6 +110,8 @@ enum // Segwit script only: Require the argument of OP_IF/NOTIF to be exactly 0x01 or empty vector // + // Note: TAPSCRIPT script execution has behavior similar to MINIMALIF as part of its consensus + // rules. It is automatic there and does not depend on this flag. SCRIPT_VERIFY_MINIMALIF = (1U << 13), // Signature(s) must be empty vector if a CHECK(MULTI)SIG operation failed @@ -114,19 +125,49 @@ enum // Making OP_CODESEPARATOR and FindAndDelete fail any non-segwit scripts // SCRIPT_VERIFY_CONST_SCRIPTCODE = (1U << 16), + + // Taproot/Tapscript validation (BIPs 341 & 342) + // + SCRIPT_VERIFY_TAPROOT = (1U << 17), + + // Making unknown Taproot leaf versions non-standard + // + SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_TAPROOT_VERSION = (1U << 18), + + // Making unknown OP_SUCCESS non-standard + SCRIPT_VERIFY_DISCOURAGE_OP_SUCCESS = (1U << 19), + + // Making unknown public key versions (in BIP 342 scripts) non-standard + SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_PUBKEYTYPE = (1U << 20), }; bool CheckSignatureEncoding(const std::vector<unsigned char> &vchSig, unsigned int flags, ScriptError* serror); struct PrecomputedTransactionData { + // BIP341 precomputed data. + // These are single-SHA256, see https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#cite_note-15. + uint256 m_prevouts_single_hash; + uint256 m_sequences_single_hash; + uint256 m_outputs_single_hash; + uint256 m_spent_amounts_single_hash; + uint256 m_spent_scripts_single_hash; + //! Whether the 5 fields above are initialized. + bool m_bip341_taproot_ready = false; + + // BIP143 precomputed data (double-SHA256). uint256 hashPrevouts, hashSequence, hashOutputs; - bool m_ready = false; + //! Whether the 3 fields above are initialized. + bool m_bip143_segwit_ready = false; + + std::vector<CTxOut> m_spent_outputs; + //! Whether m_spent_outputs is initialized. + bool m_spent_outputs_ready = false; PrecomputedTransactionData() = default; template <class T> - void Init(const T& tx); + void Init(const T& tx, std::vector<CTxOut>&& spent_outputs); template <class T> explicit PrecomputedTransactionData(const T& tx); @@ -134,13 +175,48 @@ struct PrecomputedTransactionData enum class SigVersion { - BASE = 0, - WITNESS_V0 = 1, + BASE = 0, //!< Bare scripts and BIP16 P2SH-wrapped redeemscripts + WITNESS_V0 = 1, //!< Witness v0 (P2WPKH and P2WSH); see BIP 141 + TAPROOT = 2, //!< Witness v1 with 32-byte program, not BIP16 P2SH-wrapped, key path spending; see BIP 341 + TAPSCRIPT = 3, //!< Witness v1 with 32-byte program, not BIP16 P2SH-wrapped, script path spending, leaf version 0xc0; see BIP 342 +}; + +struct ScriptExecutionData +{ + //! Whether m_tapleaf_hash is initialized. + bool m_tapleaf_hash_init = false; + //! The tapleaf hash. + uint256 m_tapleaf_hash; + + //! Whether m_codeseparator_pos is initialized. + bool m_codeseparator_pos_init = false; + //! Opcode position of the last executed OP_CODESEPARATOR (or 0xFFFFFFFF if none executed). + uint32_t m_codeseparator_pos; + + //! Whether m_annex_present and (when needed) m_annex_hash are initialized. + bool m_annex_init = false; + //! Whether an annex is present. + bool m_annex_present; + //! Hash of the annex data. + uint256 m_annex_hash; + + //! Whether m_validation_weight_left is initialized. + bool m_validation_weight_left_init = false; + //! How much validation weight is left (decremented for every successful non-empty signature check). + int64_t m_validation_weight_left; }; /** Signature hash sizes */ static constexpr size_t WITNESS_V0_SCRIPTHASH_SIZE = 32; static constexpr size_t WITNESS_V0_KEYHASH_SIZE = 20; +static constexpr size_t WITNESS_V1_TAPROOT_SIZE = 32; + +static constexpr uint8_t TAPROOT_LEAF_MASK = 0xfe; +static constexpr uint8_t TAPROOT_LEAF_TAPSCRIPT = 0xc0; +static constexpr size_t TAPROOT_CONTROL_BASE_SIZE = 33; +static constexpr size_t TAPROOT_CONTROL_NODE_SIZE = 32; +static constexpr size_t TAPROOT_CONTROL_MAX_NODE_COUNT = 128; +static constexpr size_t TAPROOT_CONTROL_MAX_SIZE = TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * TAPROOT_CONTROL_MAX_NODE_COUNT; template <class T> uint256 SignatureHash(const CScript& scriptCode, const T& txTo, unsigned int nIn, int nHashType, const CAmount& amount, SigVersion sigversion, const PrecomputedTransactionData* cache = nullptr); @@ -148,7 +224,12 @@ uint256 SignatureHash(const CScript& scriptCode, const T& txTo, unsigned int nIn class BaseSignatureChecker { public: - virtual bool CheckSig(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const + virtual bool CheckECDSASignature(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const + { + return false; + } + + virtual bool CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey, SigVersion sigversion, const ScriptExecutionData& execdata, ScriptError* serror = nullptr) const { return false; } @@ -176,12 +257,14 @@ private: const PrecomputedTransactionData* txdata; protected: - virtual bool VerifySignature(const std::vector<unsigned char>& vchSig, const CPubKey& vchPubKey, const uint256& sighash) const; + virtual bool VerifyECDSASignature(const std::vector<unsigned char>& vchSig, const CPubKey& vchPubKey, const uint256& sighash) const; + virtual bool VerifySchnorrSignature(Span<const unsigned char> sig, const XOnlyPubKey& pubkey, const uint256& sighash) const; public: GenericTransactionSignatureChecker(const T* txToIn, unsigned int nInIn, const CAmount& amountIn) : txTo(txToIn), nIn(nInIn), amount(amountIn), txdata(nullptr) {} GenericTransactionSignatureChecker(const T* txToIn, unsigned int nInIn, const CAmount& amountIn, const PrecomputedTransactionData& txdataIn) : txTo(txToIn), nIn(nInIn), amount(amountIn), txdata(&txdataIn) {} - bool CheckSig(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const override; + bool CheckECDSASignature(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const override; + bool CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey, SigVersion sigversion, const ScriptExecutionData& execdata, ScriptError* serror = nullptr) const override; bool CheckLockTime(const CScriptNum& nLockTime) const override; bool CheckSequence(const CScriptNum& nSequence) const override; }; @@ -189,6 +272,7 @@ public: using TransactionSignatureChecker = GenericTransactionSignatureChecker<CTransaction>; using MutableTransactionSignatureChecker = GenericTransactionSignatureChecker<CMutableTransaction>; +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); bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& script, unsigned int flags, const BaseSignatureChecker& checker, SigVersion sigversion, ScriptError* error = nullptr); bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const CScriptWitness* witness, unsigned int flags, const BaseSignatureChecker& checker, ScriptError* serror = nullptr); diff --git a/src/script/script.cpp b/src/script/script.cpp index 92c6fe7785..f31472e42d 100644 --- a/src/script/script.cpp +++ b/src/script/script.cpp @@ -140,6 +140,9 @@ std::string GetOpName(opcodetype opcode) case OP_NOP9 : return "OP_NOP9"; case OP_NOP10 : return "OP_NOP10"; + // Opcode added by BIP 342 (Tapscript) + case OP_CHECKSIGADD : return "OP_CHECKSIGADD"; + case OP_INVALIDOPCODE : return "OP_INVALIDOPCODE"; default: @@ -328,3 +331,11 @@ bool GetScriptOp(CScriptBase::const_iterator& pc, CScriptBase::const_iterator en opcodeRet = static_cast<opcodetype>(opcode); return true; } + +bool IsOpSuccess(const opcodetype& opcode) +{ + return opcode == 80 || opcode == 98 || (opcode >= 126 && opcode <= 129) || + (opcode >= 131 && opcode <= 134) || (opcode >= 137 && opcode <= 138) || + (opcode >= 141 && opcode <= 142) || (opcode >= 149 && opcode <= 153) || + (opcode >= 187 && opcode <= 254); +} diff --git a/src/script/script.h b/src/script/script.h index c1f2b66921..974cde4984 100644 --- a/src/script/script.h +++ b/src/script/script.h @@ -44,6 +44,17 @@ static const unsigned int LOCKTIME_THRESHOLD = 500000000; // Tue Nov 5 00:53:20 // SEQUENCE_FINAL). static const uint32_t LOCKTIME_MAX = 0xFFFFFFFFU; +// Tag for input annex. If there are at least two witness elements for a transaction input, +// and the first byte of the last element is 0x50, this last element is called annex, and +// has meanings independent of the script +static constexpr unsigned int ANNEX_TAG = 0x50; + +// Validation weight per passing signature (Tapscript only, see BIP 342). +static constexpr uint64_t VALIDATION_WEIGHT_PER_SIGOP_PASSED = 50; + +// How much weight budget is added to the witness size (Tapscript only, see BIP 342). +static constexpr uint64_t VALIDATION_WEIGHT_OFFSET = 50; + template <typename T> std::vector<unsigned char> ToByteVector(const T& in) { @@ -187,6 +198,9 @@ enum opcodetype OP_NOP9 = 0xb8, OP_NOP10 = 0xb9, + // Opcode added by BIP 342 (Tapscript) + OP_CHECKSIGADD = 0xba, + OP_INVALIDOPCODE = 0xff, }; @@ -555,4 +569,7 @@ struct CScriptWitness std::string ToString() const; }; +/** Test for OP_SUCCESSx opcodes as defined by BIP342. */ +bool IsOpSuccess(const opcodetype& opcode); + #endif // BITCOIN_SCRIPT_SCRIPT_H diff --git a/src/script/script_error.cpp b/src/script/script_error.cpp index 3b383393f9..fadc04262c 100644 --- a/src/script/script_error.cpp +++ b/src/script/script_error.cpp @@ -73,6 +73,12 @@ std::string ScriptErrorString(const ScriptError serror) return "NOPx reserved for soft-fork upgrades"; case SCRIPT_ERR_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM: return "Witness version reserved for soft-fork upgrades"; + case SCRIPT_ERR_DISCOURAGE_UPGRADABLE_TAPROOT_VERSION: + return "Taproot version reserved for soft-fork upgrades"; + case SCRIPT_ERR_DISCOURAGE_OP_SUCCESS: + return "OP_SUCCESSx reserved for soft-fork upgrades"; + case SCRIPT_ERR_DISCOURAGE_UPGRADABLE_PUBKEYTYPE: + return "Public key version reserved for soft-fork upgrades"; case SCRIPT_ERR_PUBKEYTYPE: return "Public key is neither compressed or uncompressed"; case SCRIPT_ERR_CLEANSTACK: @@ -91,6 +97,20 @@ std::string ScriptErrorString(const ScriptError serror) return "Witness provided for non-witness script"; case SCRIPT_ERR_WITNESS_PUBKEYTYPE: return "Using non-compressed keys in segwit"; + case SCRIPT_ERR_SCHNORR_SIG_SIZE: + return "Invalid Schnorr signature size"; + case SCRIPT_ERR_SCHNORR_SIG_HASHTYPE: + return "Invalid Schnorr signature hash type"; + case SCRIPT_ERR_SCHNORR_SIG: + return "Invalid Schnorr signature"; + case SCRIPT_ERR_TAPROOT_WRONG_CONTROL_SIZE: + return "Invalid Taproot control block size"; + case SCRIPT_ERR_TAPSCRIPT_VALIDATION_WEIGHT: + return "Too much signature validation relative to witness weight"; + case SCRIPT_ERR_TAPSCRIPT_CHECKMULTISIG: + return "OP_CHECKMULTISIG(VERIFY) is not available in tapscript"; + case SCRIPT_ERR_TAPSCRIPT_MINIMALIF: + return "OP_IF/NOTIF argument must be minimal in tapscript"; case SCRIPT_ERR_OP_CODESEPARATOR: return "Using OP_CODESEPARATOR in non-witness script"; case SCRIPT_ERR_SIG_FINDANDDELETE: diff --git a/src/script/script_error.h b/src/script/script_error.h index 2978c147e1..b071681613 100644 --- a/src/script/script_error.h +++ b/src/script/script_error.h @@ -56,6 +56,9 @@ typedef enum ScriptError_t /* softfork safeness */ SCRIPT_ERR_DISCOURAGE_UPGRADABLE_NOPS, SCRIPT_ERR_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM, + SCRIPT_ERR_DISCOURAGE_UPGRADABLE_TAPROOT_VERSION, + SCRIPT_ERR_DISCOURAGE_OP_SUCCESS, + SCRIPT_ERR_DISCOURAGE_UPGRADABLE_PUBKEYTYPE, /* segregated witness */ SCRIPT_ERR_WITNESS_PROGRAM_WRONG_LENGTH, @@ -66,6 +69,15 @@ typedef enum ScriptError_t SCRIPT_ERR_WITNESS_UNEXPECTED, SCRIPT_ERR_WITNESS_PUBKEYTYPE, + /* Taproot */ + SCRIPT_ERR_SCHNORR_SIG_SIZE, + SCRIPT_ERR_SCHNORR_SIG_HASHTYPE, + SCRIPT_ERR_SCHNORR_SIG, + SCRIPT_ERR_TAPROOT_WRONG_CONTROL_SIZE, + SCRIPT_ERR_TAPSCRIPT_VALIDATION_WEIGHT, + SCRIPT_ERR_TAPSCRIPT_CHECKMULTISIG, + SCRIPT_ERR_TAPSCRIPT_MINIMALIF, + /* Constant scriptCode */ SCRIPT_ERR_OP_CODESEPARATOR, SCRIPT_ERR_SIG_FINDANDDELETE, diff --git a/src/script/sigcache.cpp b/src/script/sigcache.cpp index aaecab1ef2..4a6e04f2eb 100644 --- a/src/script/sigcache.cpp +++ b/src/script/sigcache.cpp @@ -22,8 +22,9 @@ namespace { class CSignatureCache { private: - //! Entries are SHA256(nonce || signature hash || public key || signature): - CSHA256 m_salted_hasher; + //! Entries are SHA256(nonce || 'E' or 'S' || 31 zero bytes || signature hash || public key || signature): + CSHA256 m_salted_hasher_ecdsa; + CSHA256 m_salted_hasher_schnorr; typedef CuckooCache::cache<uint256, SignatureCacheHasher> map_type; map_type setValid; boost::shared_mutex cs_sigcache; @@ -34,18 +35,30 @@ public: uint256 nonce = GetRandHash(); // We want the nonce to be 64 bytes long to force the hasher to process // this chunk, which makes later hash computations more efficient. We - // just write our 32-byte entropy twice to fill the 64 bytes. - m_salted_hasher.Write(nonce.begin(), 32); - m_salted_hasher.Write(nonce.begin(), 32); + // just write our 32-byte entropy, and then pad with 'E' for ECDSA and + // 'S' for Schnorr (followed by 0 bytes). + static constexpr unsigned char PADDING_ECDSA[32] = {'E'}; + static constexpr unsigned char PADDING_SCHNORR[32] = {'S'}; + m_salted_hasher_ecdsa.Write(nonce.begin(), 32); + m_salted_hasher_ecdsa.Write(PADDING_ECDSA, 32); + m_salted_hasher_schnorr.Write(nonce.begin(), 32); + m_salted_hasher_schnorr.Write(PADDING_SCHNORR, 32); } void - ComputeEntry(uint256& entry, const uint256 &hash, const std::vector<unsigned char>& vchSig, const CPubKey& pubkey) + ComputeEntryECDSA(uint256& entry, const uint256 &hash, const std::vector<unsigned char>& vchSig, const CPubKey& pubkey) { - CSHA256 hasher = m_salted_hasher; + CSHA256 hasher = m_salted_hasher_ecdsa; hasher.Write(hash.begin(), 32).Write(&pubkey[0], pubkey.size()).Write(&vchSig[0], vchSig.size()).Finalize(entry.begin()); } + void + ComputeEntrySchnorr(uint256& entry, const uint256 &hash, Span<const unsigned char> sig, const XOnlyPubKey& pubkey) + { + CSHA256 hasher = m_salted_hasher_schnorr; + hasher.Write(hash.begin(), 32).Write(&pubkey[0], pubkey.size()).Write(sig.data(), sig.size()).Finalize(entry.begin()); + } + bool Get(const uint256& entry, const bool erase) { @@ -85,15 +98,25 @@ void InitSignatureCache() (nElems*sizeof(uint256)) >>20, (nMaxCacheSize*2)>>20, nElems); } -bool CachingTransactionSignatureChecker::VerifySignature(const std::vector<unsigned char>& vchSig, const CPubKey& pubkey, const uint256& sighash) const +bool CachingTransactionSignatureChecker::VerifyECDSASignature(const std::vector<unsigned char>& vchSig, const CPubKey& pubkey, const uint256& sighash) const { uint256 entry; - signatureCache.ComputeEntry(entry, sighash, vchSig, pubkey); + signatureCache.ComputeEntryECDSA(entry, sighash, vchSig, pubkey); if (signatureCache.Get(entry, !store)) return true; - if (!TransactionSignatureChecker::VerifySignature(vchSig, pubkey, sighash)) + if (!TransactionSignatureChecker::VerifyECDSASignature(vchSig, pubkey, sighash)) return false; if (store) signatureCache.Set(entry); return true; } + +bool CachingTransactionSignatureChecker::VerifySchnorrSignature(Span<const unsigned char> sig, const XOnlyPubKey& pubkey, const uint256& sighash) const +{ + uint256 entry; + signatureCache.ComputeEntrySchnorr(entry, sighash, sig, pubkey); + if (signatureCache.Get(entry, !store)) return true; + if (!TransactionSignatureChecker::VerifySchnorrSignature(sig, pubkey, sighash)) return false; + if (store) signatureCache.Set(entry); + return true; +} diff --git a/src/script/sigcache.h b/src/script/sigcache.h index 807b61b542..00534f9758 100644 --- a/src/script/sigcache.h +++ b/src/script/sigcache.h @@ -7,6 +7,7 @@ #define BITCOIN_SCRIPT_SIGCACHE_H #include <script/interpreter.h> +#include <span.h> #include <vector> @@ -48,7 +49,8 @@ private: public: CachingTransactionSignatureChecker(const CTransaction* txToIn, unsigned int nInIn, const CAmount& amountIn, bool storeIn, PrecomputedTransactionData& txdataIn) : TransactionSignatureChecker(txToIn, nInIn, amountIn, txdataIn), store(storeIn) {} - bool VerifySignature(const std::vector<unsigned char>& vchSig, const CPubKey& vchPubKey, const uint256& sighash) const override; + bool VerifyECDSASignature(const std::vector<unsigned char>& vchSig, const CPubKey& vchPubKey, const uint256& sighash) const override; + bool VerifySchnorrSignature(Span<const unsigned char> sig, const XOnlyPubKey& pubkey, const uint256& sighash) const override; }; void InitSignatureCache(); diff --git a/src/script/sign.cpp b/src/script/sign.cpp index 9b3f94f14d..0e6864d547 100644 --- a/src/script/sign.cpp +++ b/src/script/sign.cpp @@ -111,6 +111,7 @@ static bool SignStep(const SigningProvider& provider, const BaseSignatureCreator case TxoutType::NONSTANDARD: case TxoutType::NULL_DATA: case TxoutType::WITNESS_UNKNOWN: + case TxoutType::WITNESS_V1_TAPROOT: return false; case TxoutType::PUBKEY: if (!CreateSig(creator, sigdata, provider, sig, CPubKey(vSolutions[0]), scriptPubKey, sigversion)) return false; @@ -260,9 +261,9 @@ private: public: SignatureExtractorChecker(SignatureData& sigdata, BaseSignatureChecker& checker) : sigdata(sigdata), checker(checker) {} - bool CheckSig(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const override + bool CheckECDSASignature(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const override { - if (checker.CheckSig(scriptSig, vchPubKey, scriptCode, sigversion)) { + if (checker.CheckECDSASignature(scriptSig, vchPubKey, scriptCode, sigversion)) { CPubKey pubkey(vchPubKey); sigdata.signatures.emplace(pubkey.GetID(), SigPair(pubkey, scriptSig)); return true; @@ -339,7 +340,7 @@ SignatureData DataFromTransaction(const CMutableTransaction& tx, unsigned int nI for (unsigned int i = last_success_key; i < num_pubkeys; ++i) { const valtype& pubkey = solutions[i+1]; // We either have a signature for this pubkey, or we have found a signature and it is valid - if (data.signatures.count(CPubKey(pubkey).GetID()) || extractor_checker.CheckSig(sig, pubkey, next_script, sigversion)) { + if (data.signatures.count(CPubKey(pubkey).GetID()) || extractor_checker.CheckECDSASignature(sig, pubkey, next_script, sigversion)) { last_success_key = i + 1; break; } @@ -400,7 +401,7 @@ class DummySignatureChecker final : public BaseSignatureChecker { public: DummySignatureChecker() {} - bool CheckSig(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const override { return true; } + bool CheckECDSASignature(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const override { return true; } }; const DummySignatureChecker DUMMY_CHECKER; diff --git a/src/script/sign.h b/src/script/sign.h index b77d26c0d7..a1cfe1574d 100644 --- a/src/script/sign.h +++ b/src/script/sign.h @@ -11,6 +11,7 @@ #include <pubkey.h> #include <script/interpreter.h> #include <script/keyorigin.h> +#include <span.h> #include <streams.h> class CKey; diff --git a/src/script/standard.cpp b/src/script/standard.cpp index 96a3d311a6..f2f81664f6 100644 --- a/src/script/standard.cpp +++ b/src/script/standard.cpp @@ -55,6 +55,7 @@ std::string GetTxnOutputType(TxoutType t) case TxoutType::NULL_DATA: return "nulldata"; case TxoutType::WITNESS_V0_KEYHASH: return "witness_v0_keyhash"; case TxoutType::WITNESS_V0_SCRIPTHASH: return "witness_v0_scripthash"; + case TxoutType::WITNESS_V1_TAPROOT: return "witness_v1_taproot"; case TxoutType::WITNESS_UNKNOWN: return "witness_unknown"; } // no default case, so the compiler can warn about missing cases assert(false); @@ -130,6 +131,11 @@ TxoutType Solver(const CScript& scriptPubKey, std::vector<std::vector<unsigned c vSolutionsRet.push_back(witnessprogram); return TxoutType::WITNESS_V0_SCRIPTHASH; } + if (witnessversion == 1 && witnessprogram.size() == WITNESS_V1_TAPROOT_SIZE) { + vSolutionsRet.push_back(std::vector<unsigned char>{(unsigned char)witnessversion}); + vSolutionsRet.push_back(std::move(witnessprogram)); + return TxoutType::WITNESS_V1_TAPROOT; + } if (witnessversion != 0) { vSolutionsRet.push_back(std::vector<unsigned char>{(unsigned char)witnessversion}); vSolutionsRet.push_back(std::move(witnessprogram)); @@ -203,7 +209,7 @@ bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet) std::copy(vSolutions[0].begin(), vSolutions[0].end(), hash.begin()); addressRet = hash; return true; - } else if (whichType == TxoutType::WITNESS_UNKNOWN) { + } else if (whichType == TxoutType::WITNESS_UNKNOWN || whichType == TxoutType::WITNESS_V1_TAPROOT) { WitnessUnknown unk; unk.version = vSolutions[0][0]; std::copy(vSolutions[1].begin(), vSolutions[1].end(), unk.program); diff --git a/src/script/standard.h b/src/script/standard.h index 6dbcd04968..721203385e 100644 --- a/src/script/standard.h +++ b/src/script/standard.h @@ -129,6 +129,7 @@ enum class TxoutType { NULL_DATA, //!< unspendable OP_RETURN script that carries data WITNESS_V0_SCRIPTHASH, WITNESS_V0_KEYHASH, + WITNESS_V1_TAPROOT, WITNESS_UNKNOWN, //!< Only for Witness versions not already defined above }; @@ -206,7 +207,8 @@ struct WitnessUnknown * * ScriptHash: TxoutType::SCRIPTHASH destination (P2SH) * * WitnessV0ScriptHash: TxoutType::WITNESS_V0_SCRIPTHASH destination (P2WSH) * * WitnessV0KeyHash: TxoutType::WITNESS_V0_KEYHASH destination (P2WPKH) - * * WitnessUnknown: TxoutType::WITNESS_UNKNOWN destination (P2W???) + * * WitnessUnknown: TxoutType::WITNESS_UNKNOWN/WITNESS_V1_TAPROOT destination (P2W???) + * (taproot outputs do not require their own type as long as no wallet support exists) * A CTxDestination is the internal data type encoded in a bitcoin address */ typedef boost::variant<CNoDestination, PKHash, ScriptHash, WitnessV0ScriptHash, WitnessV0KeyHash, WitnessUnknown> CTxDestination; diff --git a/src/test/fuzz/script_assets_test_minimizer.cpp b/src/test/fuzz/script_assets_test_minimizer.cpp new file mode 100644 index 0000000000..d20fa43d68 --- /dev/null +++ b/src/test/fuzz/script_assets_test_minimizer.cpp @@ -0,0 +1,200 @@ +// Copyright (c) 2020 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#include <test/fuzz/fuzz.h> + +#include <primitives/transaction.h> +#include <pubkey.h> +#include <script/interpreter.h> +#include <serialize.h> +#include <streams.h> +#include <univalue.h> +#include <util/strencodings.h> + +#include <boost/algorithm/string.hpp> +#include <cstdint> +#include <string> +#include <vector> + +// This fuzz "test" can be used to minimize test cases for script_assets_test in +// src/test/script_tests.cpp. While it written as a fuzz test, and can be used as such, +// fuzzing the inputs is unlikely to construct useful test cases. +// +// Instead, it is primarily intended to be run on a test set that was generated +// externally, for example using test/functional/feature_taproot.py's --dumptests mode. +// The minimized set can then be concatenated together, surrounded by '[' and ']', +// and used as the script_assets_test.json input to the script_assets_test unit test: +// +// (normal build) +// $ mkdir dump +// $ for N in $(seq 1 10); do TEST_DUMP_DIR=dump test/functional/feature_taproot --dumptests; done +// $ ... +// +// (fuzz test build) +// $ mkdir dump-min +// $ ./src/test/fuzz/script_assets_test_minimizer -merge=1 dump-min/ dump/ +// $ (echo -en '[\n'; cat dump-min/* | head -c -2; echo -en '\n]') >script_assets_test.json + +namespace { + +std::vector<unsigned char> CheckedParseHex(const std::string& str) +{ + if (str.size() && !IsHex(str)) throw std::runtime_error("Non-hex input '" + str + "'"); + return ParseHex(str); +} + +CScript ScriptFromHex(const std::string& str) +{ + std::vector<unsigned char> data = CheckedParseHex(str); + return CScript(data.begin(), data.end()); +} + +CMutableTransaction TxFromHex(const std::string& str) +{ + CMutableTransaction tx; + try { + VectorReader(SER_DISK, SERIALIZE_TRANSACTION_NO_WITNESS, CheckedParseHex(str), 0) >> tx; + } catch (const std::ios_base::failure&) { + throw std::runtime_error("Tx deserialization failure"); + } + return tx; +} + +std::vector<CTxOut> TxOutsFromJSON(const UniValue& univalue) +{ + if (!univalue.isArray()) throw std::runtime_error("Prevouts must be array"); + std::vector<CTxOut> prevouts; + for (size_t i = 0; i < univalue.size(); ++i) { + CTxOut txout; + try { + VectorReader(SER_DISK, 0, CheckedParseHex(univalue[i].get_str()), 0) >> txout; + } catch (const std::ios_base::failure&) { + throw std::runtime_error("Prevout invalid format"); + } + prevouts.push_back(std::move(txout)); + } + return prevouts; +} + +CScriptWitness ScriptWitnessFromJSON(const UniValue& univalue) +{ + if (!univalue.isArray()) throw std::runtime_error("Script witness is not array"); + CScriptWitness scriptwitness; + for (size_t i = 0; i < univalue.size(); ++i) { + auto bytes = CheckedParseHex(univalue[i].get_str()); + scriptwitness.stack.push_back(std::move(bytes)); + } + return scriptwitness; +} + +const std::map<std::string, unsigned int> FLAG_NAMES = { + {std::string("P2SH"), (unsigned int)SCRIPT_VERIFY_P2SH}, + {std::string("DERSIG"), (unsigned int)SCRIPT_VERIFY_DERSIG}, + {std::string("NULLDUMMY"), (unsigned int)SCRIPT_VERIFY_NULLDUMMY}, + {std::string("CHECKLOCKTIMEVERIFY"), (unsigned int)SCRIPT_VERIFY_CHECKLOCKTIMEVERIFY}, + {std::string("CHECKSEQUENCEVERIFY"), (unsigned int)SCRIPT_VERIFY_CHECKSEQUENCEVERIFY}, + {std::string("WITNESS"), (unsigned int)SCRIPT_VERIFY_WITNESS}, + {std::string("TAPROOT"), (unsigned int)SCRIPT_VERIFY_TAPROOT}, +}; + +std::vector<unsigned int> AllFlags() +{ + std::vector<unsigned int> ret; + + for (unsigned int i = 0; i < 128; ++i) { + unsigned int flag = 0; + if (i & 1) flag |= SCRIPT_VERIFY_P2SH; + if (i & 2) flag |= SCRIPT_VERIFY_DERSIG; + if (i & 4) flag |= SCRIPT_VERIFY_NULLDUMMY; + if (i & 8) flag |= SCRIPT_VERIFY_CHECKLOCKTIMEVERIFY; + if (i & 16) flag |= SCRIPT_VERIFY_CHECKSEQUENCEVERIFY; + if (i & 32) flag |= SCRIPT_VERIFY_WITNESS; + if (i & 64) flag |= SCRIPT_VERIFY_TAPROOT; + + // SCRIPT_VERIFY_WITNESS requires SCRIPT_VERIFY_P2SH + if (flag & SCRIPT_VERIFY_WITNESS && !(flag & SCRIPT_VERIFY_P2SH)) continue; + // SCRIPT_VERIFY_TAPROOT requires SCRIPT_VERIFY_WITNESS + if (flag & SCRIPT_VERIFY_TAPROOT && !(flag & SCRIPT_VERIFY_WITNESS)) continue; + + ret.push_back(flag); + } + + return ret; +} + +const std::vector<unsigned int> ALL_FLAGS = AllFlags(); + +unsigned int ParseScriptFlags(const std::string& str) +{ + if (str.empty()) return 0; + + unsigned int flags = 0; + std::vector<std::string> words; + boost::algorithm::split(words, str, boost::algorithm::is_any_of(",")); + + for (const std::string& word : words) + { + auto it = FLAG_NAMES.find(word); + if (it == FLAG_NAMES.end()) throw std::runtime_error("Unknown verification flag " + word); + flags |= it->second; + } + + return flags; +} + +void Test(const std::string& str) +{ + UniValue test; + if (!test.read(str) || !test.isObject()) throw std::runtime_error("Non-object test input"); + + CMutableTransaction tx = TxFromHex(test["tx"].get_str()); + const std::vector<CTxOut> prevouts = TxOutsFromJSON(test["prevouts"]); + if (prevouts.size() != tx.vin.size()) throw std::runtime_error("Incorrect number of prevouts"); + size_t idx = test["index"].get_int64(); + if (idx >= tx.vin.size()) throw std::runtime_error("Invalid index"); + unsigned int test_flags = ParseScriptFlags(test["flags"].get_str()); + bool final = test.exists("final") && test["final"].get_bool(); + + if (test.exists("success")) { + tx.vin[idx].scriptSig = ScriptFromHex(test["success"]["scriptSig"].get_str()); + tx.vin[idx].scriptWitness = ScriptWitnessFromJSON(test["success"]["witness"]); + PrecomputedTransactionData txdata; + txdata.Init(tx, std::vector<CTxOut>(prevouts)); + MutableTransactionSignatureChecker txcheck(&tx, idx, prevouts[idx].nValue, txdata); + for (const auto flags : ALL_FLAGS) { + // "final": true tests are valid for all flags. Others are only valid with flags that are + // a subset of test_flags. + if (final || ((flags & test_flags) == flags)) { + (void)VerifyScript(tx.vin[idx].scriptSig, prevouts[idx].scriptPubKey, &tx.vin[idx].scriptWitness, flags, txcheck, nullptr); + } + } + } + + if (test.exists("failure")) { + tx.vin[idx].scriptSig = ScriptFromHex(test["failure"]["scriptSig"].get_str()); + tx.vin[idx].scriptWitness = ScriptWitnessFromJSON(test["failure"]["witness"]); + PrecomputedTransactionData txdata; + txdata.Init(tx, std::vector<CTxOut>(prevouts)); + MutableTransactionSignatureChecker txcheck(&tx, idx, prevouts[idx].nValue, txdata); + for (const auto flags : ALL_FLAGS) { + // If a test is supposed to fail with test_flags, it should also fail with any superset thereof. + if ((flags & test_flags) == test_flags) { + (void)VerifyScript(tx.vin[idx].scriptSig, prevouts[idx].scriptPubKey, &tx.vin[idx].scriptWitness, flags, txcheck, nullptr); + } + } + } +} + +ECCVerifyHandle handle; + +} + +void test_one_input(const std::vector<uint8_t>& buffer) +{ + if (buffer.size() < 2 || buffer.back() != '\n' || buffer[buffer.size() - 2] != ',') return; + const std::string str((const char*)buffer.data(), buffer.size() - 2); + try { + Test(str); + } catch (const std::runtime_error&) {} +} diff --git a/src/test/fuzz/script_sigcache.cpp b/src/test/fuzz/script_sigcache.cpp index 434a47b702..87af71897b 100644 --- a/src/test/fuzz/script_sigcache.cpp +++ b/src/test/fuzz/script_sigcache.cpp @@ -35,11 +35,19 @@ void test_one_input(const std::vector<uint8_t>& buffer) const bool store = fuzzed_data_provider.ConsumeBool(); PrecomputedTransactionData tx_data; CachingTransactionSignatureChecker caching_transaction_signature_checker{mutable_transaction ? &tx : nullptr, n_in, amount, store, tx_data}; - const std::optional<CPubKey> pub_key = ConsumeDeserializable<CPubKey>(fuzzed_data_provider); - if (pub_key) { - const std::vector<uint8_t> random_bytes = ConsumeRandomLengthByteVector(fuzzed_data_provider); - if (!random_bytes.empty()) { - (void)caching_transaction_signature_checker.VerifySignature(random_bytes, *pub_key, ConsumeUInt256(fuzzed_data_provider)); + if (fuzzed_data_provider.ConsumeBool()) { + const auto random_bytes = fuzzed_data_provider.ConsumeBytes<unsigned char>(64); + const XOnlyPubKey pub_key(ConsumeUInt256(fuzzed_data_provider)); + if (random_bytes.size() == 64) { + (void)caching_transaction_signature_checker.VerifySchnorrSignature(random_bytes, pub_key, ConsumeUInt256(fuzzed_data_provider)); + } + } else { + const auto random_bytes = ConsumeRandomLengthByteVector(fuzzed_data_provider); + const auto pub_key = ConsumeDeserializable<CPubKey>(fuzzed_data_provider); + if (pub_key) { + if (!random_bytes.empty()) { + (void)caching_transaction_signature_checker.VerifyECDSASignature(random_bytes, *pub_key, ConsumeUInt256(fuzzed_data_provider)); + } } } } diff --git a/src/test/fuzz/signature_checker.cpp b/src/test/fuzz/signature_checker.cpp index 3aaeb66649..e121c89665 100644 --- a/src/test/fuzz/signature_checker.cpp +++ b/src/test/fuzz/signature_checker.cpp @@ -28,7 +28,12 @@ public: { } - bool CheckSig(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const override + bool CheckECDSASignature(const std::vector<unsigned char>& scriptSig, const std::vector<unsigned char>& vchPubKey, const CScript& scriptCode, SigVersion sigversion) const override + { + return m_fuzzed_data_provider.ConsumeBool(); + } + + bool CheckSchnorrSignature(Span<const unsigned char> sig, Span<const unsigned char> pubkey, SigVersion sigversion, const ScriptExecutionData& execdata, ScriptError* serror = nullptr) const override { return m_fuzzed_data_provider.ConsumeBool(); } diff --git a/src/test/key_tests.cpp b/src/test/key_tests.cpp index 4e4c44266a..3362b8d17c 100644 --- a/src/test/key_tests.cpp +++ b/src/test/key_tests.cpp @@ -264,4 +264,32 @@ BOOST_AUTO_TEST_CASE(pubkey_unserialize) } } +BOOST_AUTO_TEST_CASE(bip340_test_vectors) +{ + static const std::vector<std::pair<std::array<std::string, 3>, bool>> VECTORS = { + {{"F9308A019258C31049344F85F89D5229B531C845836F99B08601F113BCE036F9", "0000000000000000000000000000000000000000000000000000000000000000", "E907831F80848D1069A5371B402410364BDF1C5F8307B0084C55F1CE2DCA821525F66A4A85EA8B71E482A74F382D2CE5EBEEE8FDB2172F477DF4900D310536C0"}, true}, + {{"DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659", "243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89", "6896BD60EEAE296DB48A229FF71DFE071BDE413E6D43F917DC8DCF8C78DE33418906D11AC976ABCCB20B091292BFF4EA897EFCB639EA871CFA95F6DE339E4B0A"}, true}, + {{"DD308AFEC5777E13121FA72B9CC1B7CC0139715309B086C960E18FD969774EB8", "7E2D58D8B3BCDF1ABADEC7829054F90DDA9805AAB56C77333024B9D0A508B75C", "5831AAEED7B44BB74E5EAB94BA9D4294C49BCF2A60728D8B4C200F50DD313C1BAB745879A5AD954A72C45A91C3A51D3C7ADEA98D82F8481E0E1E03674A6F3FB7"}, true}, + {{"25D1DFF95105F5253C4022F628A996AD3A0D95FBF21D468A1B33F8C160D8F517", "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", "7EB0509757E246F19449885651611CB965ECC1A187DD51B64FDA1EDC9637D5EC97582B9CB13DB3933705B32BA982AF5AF25FD78881EBB32771FC5922EFC66EA3"}, true}, + {{"D69C3509BB99E412E68B0FE8544E72837DFA30746D8BE2AA65975F29D22DC7B9", "4DF3C3F68FCC83B27E9D42C90431A72499F17875C81A599B566C9889B9696703", "00000000000000000000003B78CE563F89A0ED9414F5AA28AD0D96D6795F9C6376AFB1548AF603B3EB45C9F8207DEE1060CB71C04E80F593060B07D28308D7F4"}, true}, + {{"EEFDEA4CDB677750A420FEE807EACF21EB9898AE79B9768766E4FAA04A2D4A34", "243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89", "6CFF5C3BA86C69EA4B7376F31A9BCB4F74C1976089B2D9963DA2E5543E17776969E89B4C5564D00349106B8497785DD7D1D713A8AE82B32FA79D5F7FC407D39B"}, false}, + {{"DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659", "243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89", "FFF97BD5755EEEA420453A14355235D382F6472F8568A18B2F057A14602975563CC27944640AC607CD107AE10923D9EF7A73C643E166BE5EBEAFA34B1AC553E2"}, false}, + {{"DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659", "243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89", "1FA62E331EDBC21C394792D2AB1100A7B432B013DF3F6FF4F99FCB33E0E1515F28890B3EDB6E7189B630448B515CE4F8622A954CFE545735AAEA5134FCCDB2BD"}, false}, + {{"DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659", "243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89", "6CFF5C3BA86C69EA4B7376F31A9BCB4F74C1976089B2D9963DA2E5543E177769961764B3AA9B2FFCB6EF947B6887A226E8D7C93E00C5ED0C1834FF0D0C2E6DA6"}, false}, + {{"DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659", "243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89", "0000000000000000000000000000000000000000000000000000000000000000123DDA8328AF9C23A94C1FEECFD123BA4FB73476F0D594DCB65C6425BD186051"}, false}, + {{"DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659", "243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89", "00000000000000000000000000000000000000000000000000000000000000017615FBAF5AE28864013C099742DEADB4DBA87F11AC6754F93780D5A1837CF197"}, false}, + {{"DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659", "243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89", "4A298DACAE57395A15D0795DDBFD1DCB564DA82B0F269BC70A74F8220429BA1D69E89B4C5564D00349106B8497785DD7D1D713A8AE82B32FA79D5F7FC407D39B"}, false}, + {{"DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659", "243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89", "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F69E89B4C5564D00349106B8497785DD7D1D713A8AE82B32FA79D5F7FC407D39B"}, false}, + {{"DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659", "243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89", "6CFF5C3BA86C69EA4B7376F31A9BCB4F74C1976089B2D9963DA2E5543E177769FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141"}, false}, + {{"FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC30", "243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89", "6CFF5C3BA86C69EA4B7376F31A9BCB4F74C1976089B2D9963DA2E5543E17776969E89B4C5564D00349106B8497785DD7D1D713A8AE82B32FA79D5F7FC407D39B"}, false} + }; + + for (const auto& test : VECTORS) { + auto pubkey = ParseHex(test.first[0]); + auto msg = ParseHex(test.first[1]); + auto sig = ParseHex(test.first[2]); + BOOST_CHECK_EQUAL(XOnlyPubKey(pubkey).VerifySchnorr(uint256(msg), sig), test.second); + } +} + BOOST_AUTO_TEST_SUITE_END() diff --git a/src/test/script_tests.cpp b/src/test/script_tests.cpp index 0830743d61..a2efd8ac07 100644 --- a/src/test/script_tests.cpp +++ b/src/test/script_tests.cpp @@ -5,10 +5,12 @@ #include <test/data/script_tests.json.h> #include <core_io.h> +#include <fs.h> #include <key.h> #include <rpc/util.h> #include <script/script.h> #include <script/script_error.h> +#include <script/sigcache.h> #include <script/sign.h> #include <script/signingprovider.h> #include <streams.h> @@ -1339,13 +1341,41 @@ BOOST_AUTO_TEST_CASE(script_GetScriptAsm) BOOST_CHECK_EQUAL(derSig + "83 " + pubKey, ScriptToAsmStr(CScript() << ToByteVector(ParseHex(derSig + "83")) << vchPubKey)); } -static CScript -ScriptFromHex(const char* hex) +static CScript ScriptFromHex(const std::string& str) { - std::vector<unsigned char> data = ParseHex(hex); + std::vector<unsigned char> data = ParseHex(str); return CScript(data.begin(), data.end()); } +static CMutableTransaction TxFromHex(const std::string& str) +{ + CMutableTransaction tx; + VectorReader(SER_DISK, SERIALIZE_TRANSACTION_NO_WITNESS, ParseHex(str), 0) >> tx; + return tx; +} + +static std::vector<CTxOut> TxOutsFromJSON(const UniValue& univalue) +{ + assert(univalue.isArray()); + std::vector<CTxOut> prevouts; + for (size_t i = 0; i < univalue.size(); ++i) { + CTxOut txout; + VectorReader(SER_DISK, 0, ParseHex(univalue[i].get_str()), 0) >> txout; + prevouts.push_back(std::move(txout)); + } + return prevouts; +} + +static CScriptWitness ScriptWitnessFromJSON(const UniValue& univalue) +{ + assert(univalue.isArray()); + CScriptWitness scriptwitness; + for (size_t i = 0; i < univalue.size(); ++i) { + auto bytes = ParseHex(univalue[i].get_str()); + scriptwitness.stack.push_back(std::move(bytes)); + } + return scriptwitness; +} BOOST_AUTO_TEST_CASE(script_FindAndDelete) { @@ -1610,5 +1640,107 @@ BOOST_AUTO_TEST_CASE(bitcoinconsensus_verify_script_invalid_flags) BOOST_CHECK_EQUAL(err, bitcoinconsensus_ERR_INVALID_FLAGS); } +static std::vector<unsigned int> AllConsensusFlags() +{ + std::vector<unsigned int> ret; + + for (unsigned int i = 0; i < 128; ++i) { + unsigned int flag = 0; + if (i & 1) flag |= SCRIPT_VERIFY_P2SH; + if (i & 2) flag |= SCRIPT_VERIFY_DERSIG; + if (i & 4) flag |= SCRIPT_VERIFY_NULLDUMMY; + if (i & 8) flag |= SCRIPT_VERIFY_CHECKLOCKTIMEVERIFY; + if (i & 16) flag |= SCRIPT_VERIFY_CHECKSEQUENCEVERIFY; + if (i & 32) flag |= SCRIPT_VERIFY_WITNESS; + if (i & 64) flag |= SCRIPT_VERIFY_TAPROOT; + + // SCRIPT_VERIFY_WITNESS requires SCRIPT_VERIFY_P2SH + if (flag & SCRIPT_VERIFY_WITNESS && !(flag & SCRIPT_VERIFY_P2SH)) continue; + // SCRIPT_VERIFY_TAPROOT requires SCRIPT_VERIFY_WITNESS + if (flag & SCRIPT_VERIFY_TAPROOT && !(flag & SCRIPT_VERIFY_WITNESS)) continue; + + ret.push_back(flag); + } + + return ret; +} + +/** Precomputed list of all valid combinations of consensus-relevant script validation flags. */ +static const std::vector<unsigned int> ALL_CONSENSUS_FLAGS = AllConsensusFlags(); + +static void AssetTest(const UniValue& test) +{ + BOOST_CHECK(test.isObject()); + + CMutableTransaction mtx = TxFromHex(test["tx"].get_str()); + const std::vector<CTxOut> prevouts = TxOutsFromJSON(test["prevouts"]); + BOOST_CHECK(prevouts.size() == mtx.vin.size()); + size_t idx = test["index"].get_int64(); + unsigned int test_flags = ParseScriptFlags(test["flags"].get_str()); + bool fin = test.exists("final") && test["final"].get_bool(); + + if (test.exists("success")) { + mtx.vin[idx].scriptSig = ScriptFromHex(test["success"]["scriptSig"].get_str()); + mtx.vin[idx].scriptWitness = ScriptWitnessFromJSON(test["success"]["witness"]); + CTransaction tx(mtx); + PrecomputedTransactionData txdata; + txdata.Init(tx, std::vector<CTxOut>(prevouts)); + CachingTransactionSignatureChecker txcheck(&tx, idx, prevouts[idx].nValue, true, txdata); + for (const auto flags : ALL_CONSENSUS_FLAGS) { + // "final": true tests are valid for all flags. Others are only valid with flags that are + // a subset of test_flags. + if (fin || ((flags & test_flags) == flags)) { + bool ret = VerifyScript(tx.vin[idx].scriptSig, prevouts[idx].scriptPubKey, &tx.vin[idx].scriptWitness, flags, txcheck, nullptr); + BOOST_CHECK(ret); + } + } + } + + if (test.exists("failure")) { + mtx.vin[idx].scriptSig = ScriptFromHex(test["failure"]["scriptSig"].get_str()); + mtx.vin[idx].scriptWitness = ScriptWitnessFromJSON(test["failure"]["witness"]); + CTransaction tx(mtx); + PrecomputedTransactionData txdata; + txdata.Init(tx, std::vector<CTxOut>(prevouts)); + CachingTransactionSignatureChecker txcheck(&tx, idx, prevouts[idx].nValue, true, txdata); + for (const auto flags : ALL_CONSENSUS_FLAGS) { + // If a test is supposed to fail with test_flags, it should also fail with any superset thereof. + if ((flags & test_flags) == test_flags) { + bool ret = VerifyScript(tx.vin[idx].scriptSig, prevouts[idx].scriptPubKey, &tx.vin[idx].scriptWitness, flags, txcheck, nullptr); + BOOST_CHECK(!ret); + } + } + } +} + +BOOST_AUTO_TEST_CASE(script_assets_test) +{ + // See src/test/fuzz/script_assets_test_minimizer.cpp for information on how to generate + // the script_assets_test.json file used by this test. + + const char* dir = std::getenv("DIR_UNIT_TEST_DATA"); + BOOST_WARN_MESSAGE(dir != nullptr, "Variable DIR_UNIT_TEST_DATA unset, skipping script_assets_test"); + if (dir == nullptr) return; + auto path = fs::path(dir) / "script_assets_test.json"; + bool exists = fs::exists(path); + BOOST_WARN_MESSAGE(exists, "File $DIR_UNIT_TEST_DATA/script_assets_test.json not found, skipping script_assets_test"); + if (!exists) return; + fs::ifstream file(path); + BOOST_CHECK(file.is_open()); + file.seekg(0, std::ios::end); + size_t length = file.tellg(); + file.seekg(0, std::ios::beg); + std::string data(length, '\0'); + file.read(&data[0], data.size()); + UniValue tests = read_json(data); + BOOST_CHECK(tests.isArray()); + BOOST_CHECK(tests.size() > 0); + + for (size_t i = 0; i < tests.size(); i++) { + AssetTest(tests[i]); + } + file.close(); +} + #endif BOOST_AUTO_TEST_SUITE_END() diff --git a/src/test/transaction_tests.cpp b/src/test/transaction_tests.cpp index 94b5dba913..b7ee280336 100644 --- a/src/test/transaction_tests.cpp +++ b/src/test/transaction_tests.cpp @@ -57,6 +57,7 @@ static std::map<std::string, unsigned int> mapFlagNames = { {std::string("DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM"), (unsigned int)SCRIPT_VERIFY_DISCOURAGE_UPGRADABLE_WITNESS_PROGRAM}, {std::string("WITNESS_PUBKEYTYPE"), (unsigned int)SCRIPT_VERIFY_WITNESS_PUBKEYTYPE}, {std::string("CONST_SCRIPTCODE"), (unsigned int)SCRIPT_VERIFY_CONST_SCRIPTCODE}, + {std::string("TAPROOT"), (unsigned int)SCRIPT_VERIFY_TAPROOT}, }; unsigned int ParseScriptFlags(std::string strFlags) diff --git a/src/validation.cpp b/src/validation.cpp index 06b9b36fca..423b93479a 100644 --- a/src/validation.cpp +++ b/src/validation.cpp @@ -1532,14 +1532,21 @@ bool CheckInputScripts(const CTransaction& tx, TxValidationState &state, const C return true; } - if (!txdata.m_ready) { - txdata.Init(tx); + if (!txdata.m_spent_outputs_ready) { + std::vector<CTxOut> spent_outputs; + spent_outputs.reserve(tx.vin.size()); + + for (const auto& txin : tx.vin) { + const COutPoint& prevout = txin.prevout; + const Coin& coin = inputs.AccessCoin(prevout); + assert(!coin.IsSpent()); + spent_outputs.emplace_back(coin.out); + } + txdata.Init(tx, std::move(spent_outputs)); } + assert(txdata.m_spent_outputs.size() == tx.vin.size()); for (unsigned int i = 0; i < tx.vin.size(); i++) { - const COutPoint &prevout = tx.vin[i].prevout; - const Coin& coin = inputs.AccessCoin(prevout); - assert(!coin.IsSpent()); // We very carefully only pass in things to CScriptCheck which // are clearly committed to by tx' witness hash. This provides @@ -1548,7 +1555,7 @@ bool CheckInputScripts(const CTransaction& tx, TxValidationState &state, const C // spent being checked as a part of CScriptCheck. // Verify signature - CScriptCheck check(coin.out, tx, i, flags, cacheSigStore, &txdata); + CScriptCheck check(txdata.m_spent_outputs[i], tx, i, flags, cacheSigStore, &txdata); if (pvChecks) { pvChecks->push_back(CScriptCheck()); check.swap(pvChecks->back()); @@ -1562,7 +1569,7 @@ bool CheckInputScripts(const CTransaction& tx, TxValidationState &state, const C // splitting the network between upgraded and // non-upgraded nodes by banning CONSENSUS-failing // data providers. - CScriptCheck check2(coin.out, tx, i, + CScriptCheck check2(txdata.m_spent_outputs[i], tx, i, flags & ~STANDARD_NOT_MANDATORY_VERIFY_FLAGS, cacheSigStore, &txdata); if (check2()) return state.Invalid(TxValidationResult::TX_NOT_STANDARD, strprintf("non-mandatory-script-verify-flag (%s)", ScriptErrorString(check.GetScriptError()))); @@ -1907,6 +1914,11 @@ static unsigned int GetBlockScriptFlags(const CBlockIndex* pindex, const Consens flags |= SCRIPT_VERIFY_CHECKSEQUENCEVERIFY; } + // Start enforcing Taproot using versionbits logic. + if (VersionBitsState(pindex->pprev, consensusparams, Consensus::DEPLOYMENT_TAPROOT, versionbitscache) == ThresholdState::ACTIVE) { + flags |= SCRIPT_VERIFY_TAPROOT; + } + // Start enforcing BIP147 NULLDUMMY (activated simultaneously with segwit) if (IsWitnessEnabled(pindex->pprev, consensusparams)) { flags |= SCRIPT_VERIFY_NULLDUMMY; diff --git a/src/versionbitsinfo.cpp b/src/versionbitsinfo.cpp index 20297b9f9d..20dfc044ca 100644 --- a/src/versionbitsinfo.cpp +++ b/src/versionbitsinfo.cpp @@ -11,4 +11,8 @@ const struct VBDeploymentInfo VersionBitsDeploymentInfo[Consensus::MAX_VERSION_B /*.name =*/ "testdummy", /*.gbt_force =*/ true, }, + { + /*.name =*/ "taproot", + /*.gbt_force =*/ true, + }, }; diff --git a/src/wallet/rpcdump.cpp b/src/wallet/rpcdump.cpp index 9e36a09780..7dcab46ad3 100644 --- a/src/wallet/rpcdump.cpp +++ b/src/wallet/rpcdump.cpp @@ -932,6 +932,7 @@ static std::string RecurseImportData(const CScript& script, ImportData& import_d return "unspendable script"; case TxoutType::NONSTANDARD: case TxoutType::WITNESS_UNKNOWN: + case TxoutType::WITNESS_V1_TAPROOT: default: return "unrecognized script"; } diff --git a/src/wallet/scriptpubkeyman.cpp b/src/wallet/scriptpubkeyman.cpp index 435716e56a..b7c70dac3a 100644 --- a/src/wallet/scriptpubkeyman.cpp +++ b/src/wallet/scriptpubkeyman.cpp @@ -96,6 +96,7 @@ IsMineResult IsMineInner(const LegacyScriptPubKeyMan& keystore, const CScript& s case TxoutType::NONSTANDARD: case TxoutType::NULL_DATA: case TxoutType::WITNESS_UNKNOWN: + case TxoutType::WITNESS_V1_TAPROOT: break; case TxoutType::PUBKEY: keyID = CPubKey(vSolutions[0]).GetID(); diff --git a/test/functional/feature_taproot.py b/test/functional/feature_taproot.py new file mode 100755 index 0000000000..7b534c1c2f --- /dev/null +++ b/test/functional/feature_taproot.py @@ -0,0 +1,1458 @@ +#!/usr/bin/env python3 +# Copyright (c) 2019-2020 The Bitcoin Core developers +# Distributed under the MIT software license, see the accompanying +# file COPYING or http://www.opensource.org/licenses/mit-license.php. +# Test Taproot softfork (BIPs 340-342) + +from test_framework.blocktools import ( + create_coinbase, + create_block, + add_witness_commitment, + MAX_BLOCK_SIGOPS_WEIGHT, + WITNESS_SCALE_FACTOR, +) +from test_framework.messages import ( + COutPoint, + CTransaction, + CTxIn, + CTxInWitness, + CTxOut, + ToHex, +) +from test_framework.script import ( + ANNEX_TAG, + CScript, + CScriptNum, + CScriptOp, + LEAF_VERSION_TAPSCRIPT, + LegacySignatureHash, + LOCKTIME_THRESHOLD, + MAX_SCRIPT_ELEMENT_SIZE, + OP_0, + OP_1, + OP_2, + OP_3, + OP_4, + OP_5, + OP_6, + OP_7, + OP_8, + OP_9, + OP_10, + OP_11, + OP_12, + OP_16, + OP_2DROP, + OP_2DUP, + OP_CHECKMULTISIG, + OP_CHECKMULTISIGVERIFY, + OP_CHECKSIG, + OP_CHECKSIGADD, + OP_CHECKSIGVERIFY, + OP_CODESEPARATOR, + OP_DROP, + OP_DUP, + OP_ELSE, + OP_ENDIF, + OP_EQUAL, + OP_EQUALVERIFY, + OP_HASH160, + OP_IF, + OP_NOP, + OP_NOT, + OP_NOTIF, + OP_PUSHDATA1, + OP_RETURN, + OP_SWAP, + OP_VERIFY, + SIGHASH_DEFAULT, + SIGHASH_ALL, + SIGHASH_NONE, + SIGHASH_SINGLE, + SIGHASH_ANYONECANPAY, + SegwitV0SignatureHash, + TaprootSignatureHash, + is_op_success, + taproot_construct, +) +from test_framework.test_framework import BitcoinTestFramework +from test_framework.util import assert_raises_rpc_error, assert_equal +from test_framework.key import generate_privkey, compute_xonly_pubkey, sign_schnorr, tweak_add_privkey, ECKey +from test_framework.address import ( + hash160, + sha256, +) +from collections import OrderedDict, namedtuple +from io import BytesIO +import json +import hashlib +import os +import random + +# === Framework for building spending transactions. === +# +# The computation is represented as a "context" dict, whose entries store potentially-unevaluated expressions that +# refer to lower-level ones. By overwriting these expression, many aspects - both high and low level - of the signing +# process can be overridden. +# +# Specifically, a context object is a dict that maps names to compositions of: +# - values +# - lists of values +# - callables which, when fed the context object as argument, produce any of these +# +# The DEFAULT_CONTEXT object specifies a standard signing process, with many overridable knobs. +# +# The get(ctx, name) function can evaluate a name, and cache its result in the context. +# getter(name) can be used to construct a callable that evaluates name. For example: +# +# ctx1 = {**DEFAULT_CONTEXT, inputs=[getter("sign"), b'\x01']} +# +# creates a context where the script inputs are a signature plus the bytes 0x01. +# +# override(expr, name1=expr1, name2=expr2, ...) can be used to cause an expression to be evaluated in a selectively +# modified context. For example: +# +# ctx2 = {**DEFAULT_CONTEXT, sighash=override(default_sighash, hashtype=SIGHASH_DEFAULT)} +# +# creates a context ctx2 where the sighash is modified to use hashtype=SIGHASH_DEFAULT. This differs from +# +# ctx3 = {**DEFAULT_CONTEXT, hashtype=SIGHASH_DEFAULT} +# +# in that ctx3 will globally use hashtype=SIGHASH_DEFAULT (including in the hashtype byte appended to the signature) +# while ctx2 only uses the modified hashtype inside the sighash calculation. + +def deep_eval(ctx, expr): + """Recursively replace any callables c in expr (including inside lists) with c(ctx).""" + while callable(expr): + expr = expr(ctx) + if isinstance(expr, list): + expr = [deep_eval(ctx, x) for x in expr] + return expr + +# Data type to represent fully-evaluated expressions in a context dict (so we can avoid reevaluating them). +Final = namedtuple("Final", "value") + +def get(ctx, name): + """Evaluate name in context ctx.""" + assert name in ctx, "Missing '%s' in context" % name + expr = ctx[name] + if not isinstance(expr, Final): + # Evaluate and cache the result. + expr = Final(deep_eval(ctx, expr)) + ctx[name] = expr + return expr.value + +def getter(name): + """Return a callable that evaluates name in its passed context.""" + return lambda ctx: get(ctx, name) + +def override(expr, **kwargs): + """Return a callable that evaluates expr in a modified context.""" + return lambda ctx: deep_eval({**ctx, **kwargs}, expr) + +# === Implementations for the various default expressions in DEFAULT_CONTEXT === + +def default_hashtype(ctx): + """Default expression for "hashtype": SIGHASH_DEFAULT for taproot, SIGHASH_ALL otherwise.""" + mode = get(ctx, "mode") + if mode == "taproot": + return SIGHASH_DEFAULT + else: + return SIGHASH_ALL + +def default_tapleaf(ctx): + """Default expression for "tapleaf": looking up leaf in tap[2].""" + return get(ctx, "tap").leaves[get(ctx, "leaf")] + +def default_script_taproot(ctx): + """Default expression for "script_taproot": tapleaf.script.""" + return get(ctx, "tapleaf").script + +def default_leafversion(ctx): + """Default expression for "leafversion": tapleaf.version""" + return get(ctx, "tapleaf").version + +def default_negflag(ctx): + """Default expression for "negflag": tap.negflag.""" + return get(ctx, "tap").negflag + +def default_pubkey_inner(ctx): + """Default expression for "pubkey_inner": tap.inner_pubkey.""" + return get(ctx, "tap").inner_pubkey + +def default_merklebranch(ctx): + """Default expression for "merklebranch": tapleaf.merklebranch.""" + return get(ctx, "tapleaf").merklebranch + +def default_controlblock(ctx): + """Default expression for "controlblock": combine leafversion, negflag, pubkey_inner, merklebranch.""" + return bytes([get(ctx, "leafversion") + get(ctx, "negflag")]) + get(ctx, "pubkey_inner") + get(ctx, "merklebranch") + +def default_sighash(ctx): + """Default expression for "sighash": depending on mode, compute BIP341, BIP143, or legacy sighash.""" + tx = get(ctx, "tx") + idx = get(ctx, "idx") + hashtype = get(ctx, "hashtype_actual") + mode = get(ctx, "mode") + if mode == "taproot": + # BIP341 signature hash + utxos = get(ctx, "utxos") + annex = get(ctx, "annex") + if get(ctx, "leaf") is not None: + codeseppos = get(ctx, "codeseppos") + leaf_ver = get(ctx, "leafversion") + script = get(ctx, "script_taproot") + return TaprootSignatureHash(tx, utxos, hashtype, idx, scriptpath=True, script=script, leaf_ver=leaf_ver, codeseparator_pos=codeseppos, annex=annex) + else: + return TaprootSignatureHash(tx, utxos, hashtype, idx, scriptpath=False, annex=annex) + elif mode == "witv0": + # BIP143 signature hash + scriptcode = get(ctx, "scriptcode") + utxos = get(ctx, "utxos") + return SegwitV0SignatureHash(scriptcode, tx, idx, hashtype, utxos[idx].nValue) + else: + # Pre-segwit signature hash + scriptcode = get(ctx, "scriptcode") + return LegacySignatureHash(scriptcode, tx, idx, hashtype)[0] + +def default_tweak(ctx): + """Default expression for "tweak": None if a leaf is specified, tap[0] otherwise.""" + if get(ctx, "leaf") is None: + return get(ctx, "tap").tweak + return None + +def default_key_tweaked(ctx): + """Default expression for "key_tweaked": key if tweak is None, tweaked with it otherwise.""" + key = get(ctx, "key") + tweak = get(ctx, "tweak") + if tweak is None: + return key + else: + return tweak_add_privkey(key, tweak) + +def default_signature(ctx): + """Default expression for "signature": BIP340 signature or ECDSA signature depending on mode.""" + sighash = get(ctx, "sighash") + if get(ctx, "mode") == "taproot": + key = get(ctx, "key_tweaked") + flip_r = get(ctx, "flag_flip_r") + flip_p = get(ctx, "flag_flip_p") + return sign_schnorr(key, sighash, flip_r=flip_r, flip_p=flip_p) + else: + key = get(ctx, "key") + return key.sign_ecdsa(sighash) + +def default_hashtype_actual(ctx): + """Default expression for "hashtype_actual": hashtype, unless mismatching SIGHASH_SINGLE in taproot.""" + hashtype = get(ctx, "hashtype") + mode = get(ctx, "mode") + if mode != "taproot": + return hashtype + idx = get(ctx, "idx") + tx = get(ctx, "tx") + if hashtype & 3 == SIGHASH_SINGLE and idx >= len(tx.vout): + return (hashtype & ~3) | SIGHASH_NONE + return hashtype + +def default_bytes_hashtype(ctx): + """Default expression for "bytes_hashtype": bytes([hashtype_actual]) if not 0, b"" otherwise.""" + return bytes([x for x in [get(ctx, "hashtype_actual")] if x != 0]) + +def default_sign(ctx): + """Default expression for "sign": concatenation of signature and bytes_hashtype.""" + return get(ctx, "signature") + get(ctx, "bytes_hashtype") + +def default_inputs_keypath(ctx): + """Default expression for "inputs_keypath": a signature.""" + return [get(ctx, "sign")] + +def default_witness_taproot(ctx): + """Default expression for "witness_taproot", consisting of inputs, script, control block, and annex as needed.""" + annex = get(ctx, "annex") + suffix_annex = [] + if annex is not None: + suffix_annex = [annex] + if get(ctx, "leaf") is None: + return get(ctx, "inputs_keypath") + suffix_annex + else: + return get(ctx, "inputs") + [bytes(get(ctx, "script_taproot")), get(ctx, "controlblock")] + suffix_annex + +def default_witness_witv0(ctx): + """Default expression for "witness_witv0", consisting of inputs and witness script, as needed.""" + script = get(ctx, "script_witv0") + inputs = get(ctx, "inputs") + if script is None: + return inputs + else: + return inputs + [script] + +def default_witness(ctx): + """Default expression for "witness", delegating to "witness_taproot" or "witness_witv0" as needed.""" + mode = get(ctx, "mode") + if mode == "taproot": + return get(ctx, "witness_taproot") + elif mode == "witv0": + return get(ctx, "witness_witv0") + else: + return [] + +def default_scriptsig(ctx): + """Default expression for "scriptsig", consisting of inputs and redeemscript, as needed.""" + scriptsig = [] + mode = get(ctx, "mode") + if mode == "legacy": + scriptsig = get(ctx, "inputs") + redeemscript = get(ctx, "script_p2sh") + if redeemscript is not None: + scriptsig += [bytes(redeemscript)] + return scriptsig + +# The default context object. +DEFAULT_CONTEXT = { + # == The main expressions to evaluate. Only override these for unusual or invalid spends. == + # The overall witness stack, as a list of bytes objects. + "witness": default_witness, + # The overall scriptsig, as a list of CScript objects (to be concatenated) and bytes objects (to be pushed) + "scriptsig": default_scriptsig, + + # == Expressions you'll generally only override for intentionally invalid spends. == + # The witness stack for spending a taproot output. + "witness_taproot": default_witness_taproot, + # The witness stack for spending a P2WPKH/P2WSH output. + "witness_witv0": default_witness_witv0, + # The script inputs for a taproot key path spend. + "inputs_keypath": default_inputs_keypath, + # The actual hashtype to use (usually equal to hashtype, but in taproot SIGHASH_SINGLE is not always allowed). + "hashtype_actual": default_hashtype_actual, + # The bytes object for a full signature (including hashtype byte, if needed). + "bytes_hashtype": default_bytes_hashtype, + # A full script signature (bytes including hashtype, if needed) + "sign": default_sign, + # An ECDSA or Schnorr signature (excluding hashtype byte). + "signature": default_signature, + # The 32-byte tweaked key (equal to key for script path spends, or key+tweak for key path spends). + "key_tweaked": default_key_tweaked, + # The tweak to use (None for script path spends, the actual tweak for key path spends). + "tweak": default_tweak, + # The sighash value (32 bytes) + "sighash": default_sighash, + # The information about the chosen script path spend (TaprootLeafInfo object). + "tapleaf": default_tapleaf, + # The script to push, and include in the sighash, for a taproot script path spend. + "script_taproot": default_script_taproot, + # The inner pubkey for a taproot script path spend (32 bytes). + "pubkey_inner": default_pubkey_inner, + # The negation flag of the inner pubkey for a taproot script path spend. + "negflag": default_negflag, + # The leaf version to include in the sighash (this does not affect the one in the control block). + "leafversion": default_leafversion, + # The Merkle path to include in the control block for a script path spend. + "merklebranch": default_merklebranch, + # The control block to push for a taproot script path spend. + "controlblock": default_controlblock, + # Whether to produce signatures with invalid P sign (Schnorr signatures only). + "flag_flip_p": False, + # Whether to produce signatures with invalid R sign (Schnorr signatures only). + "flag_flip_r": False, + + # == Parameters that can be changed without invalidating, but do have a default: == + # The hashtype (as an integer). + "hashtype": default_hashtype, + # The annex (only when mode=="taproot"). + "annex": None, + # The codeseparator position (only when mode=="taproot"). + "codeseppos": -1, + # The redeemscript to add to the scriptSig (if P2SH; None implies not P2SH). + "script_p2sh": None, + # The script to add to the witness in (if P2WSH; None implies P2WPKH) + "script_witv0": None, + # The leaf to use in taproot spends (if script path spend; None implies key path spend). + "leaf": None, + # The input arguments to provide to the executed script + "inputs": [], + + # == Parameters to be set before evaluation: == + # - mode: what spending style to use ("taproot", "witv0", or "legacy"). + # - key: the (untweaked) private key to sign with (ECKey object for ECDSA, 32 bytes for Schnorr). + # - tap: the TaprootInfo object (see taproot_construct; needed in mode=="taproot"). + # - tx: the transaction to sign. + # - utxos: the UTXOs being spent (needed in mode=="witv0" and mode=="taproot"). + # - idx: the input position being signed. + # - scriptcode: the scriptcode to include in legacy and witv0 sighashes. +} + +def flatten(lst): + ret = [] + for elem in lst: + if isinstance(elem, list): + ret += flatten(elem) + else: + ret.append(elem) + return ret + +def spend(tx, idx, utxos, **kwargs): + """Sign transaction input idx of tx, provided utxos is the list of outputs being spent. + + Additional arguments may be provided that override any aspect of the signing process. + See DEFAULT_CONTEXT above for what can be overridden, and what must be provided. + """ + + ctx = {**DEFAULT_CONTEXT, "tx":tx, "idx":idx, "utxos":utxos, **kwargs} + + def to_script(elem): + """If fed a CScript, return it; if fed bytes, return a CScript that pushes it.""" + if isinstance(elem, CScript): + return elem + else: + return CScript([elem]) + + scriptsig_list = flatten(get(ctx, "scriptsig")) + scriptsig = CScript(b"".join(bytes(to_script(elem)) for elem in scriptsig_list)) + witness_stack = flatten(get(ctx, "witness")) + return (scriptsig, witness_stack) + + +# === Spender objects === +# +# Each spender is a tuple of: +# - A scriptPubKey which is to be spent from (CScript) +# - A comment describing the test (string) +# - Whether the spending (on itself) is expected to be standard (bool) +# - A tx-signing lambda returning (scriptsig, witness_stack), taking as inputs: +# - A transaction to sign (CTransaction) +# - An input position (int) +# - The spent UTXOs by this transaction (list of CTxOut) +# - Whether to produce a valid spend (bool) +# - A string with an expected error message for failure case if known +# - The (pre-taproot) sigops weight consumed by a successful spend +# - Whether this spend cannot fail +# - Whether this test demands being placed in a txin with no corresponding txout (for testing SIGHASH_SINGLE behavior) + +Spender = namedtuple("Spender", "script,comment,is_standard,sat_function,err_msg,sigops_weight,no_fail,need_vin_vout_mismatch") + +def make_spender(comment, *, tap=None, witv0=False, script=None, pkh=None, p2sh=False, spk_mutate_pre_p2sh=None, failure=None, standard=True, err_msg=None, sigops_weight=0, need_vin_vout_mismatch=False, **kwargs): + """Helper for constructing Spender objects using the context signing framework. + + * tap: a TaprootInfo object (see taproot_construct), for Taproot spends (cannot be combined with pkh, witv0, or script) + * witv0: boolean indicating the use of witness v0 spending (needs one of script or pkh) + * script: the actual script executed (for bare/P2WSH/P2SH spending) + * pkh: the public key for P2PKH or P2WPKH spending + * p2sh: whether the output is P2SH wrapper (this is supported even for Taproot, where it makes the output unencumbered) + * spk_mutate_pre_psh: a callable to be applied to the script (before potentially P2SH-wrapping it) + * failure: a dict of entries to override in the context when intentionally failing to spend (if None, no_fail will be set) + * standard: whether the (valid version of) spending is expected to be standard + * err_msg: a string with an expected error message for failure (or None, if not cared about) + * sigops_weight: the pre-taproot sigops weight consumed by a successful spend + """ + + conf = dict() + + # Compute scriptPubKey and set useful defaults based on the inputs. + if witv0: + assert tap is None + conf["mode"] = "witv0" + if pkh is not None: + # P2WPKH + assert script is None + pubkeyhash = hash160(pkh) + spk = CScript([OP_0, pubkeyhash]) + conf["scriptcode"] = CScript([OP_DUP, OP_HASH160, pubkeyhash, OP_EQUALVERIFY, OP_CHECKSIG]) + conf["script_witv0"] = None + conf["inputs"] = [getter("sign"), pkh] + elif script is not None: + # P2WSH + spk = CScript([OP_0, sha256(script)]) + conf["scriptcode"] = script + conf["script_witv0"] = script + else: + assert False + elif tap is None: + conf["mode"] = "legacy" + if pkh is not None: + # P2PKH + assert script is None + pubkeyhash = hash160(pkh) + spk = CScript([OP_DUP, OP_HASH160, pubkeyhash, OP_EQUALVERIFY, OP_CHECKSIG]) + conf["scriptcode"] = spk + conf["inputs"] = [getter("sign"), pkh] + elif script is not None: + # bare + spk = script + conf["scriptcode"] = script + else: + assert False + else: + assert script is None + conf["mode"] = "taproot" + conf["tap"] = tap + spk = tap.scriptPubKey + + if spk_mutate_pre_p2sh is not None: + spk = spk_mutate_pre_p2sh(spk) + + if p2sh: + # P2SH wrapper can be combined with anything else + conf["script_p2sh"] = spk + spk = CScript([OP_HASH160, hash160(spk), OP_EQUAL]) + + conf = {**conf, **kwargs} + + def sat_fn(tx, idx, utxos, valid): + if valid: + return spend(tx, idx, utxos, **conf) + else: + assert failure is not None + return spend(tx, idx, utxos, **{**conf, **failure}) + + return Spender(script=spk, comment=comment, is_standard=standard, sat_function=sat_fn, err_msg=err_msg, sigops_weight=sigops_weight, no_fail=failure is None, need_vin_vout_mismatch=need_vin_vout_mismatch) + +def add_spender(spenders, *args, **kwargs): + """Make a spender using make_spender, and add it to spenders.""" + spenders.append(make_spender(*args, **kwargs)) + +# === Helpers for the test === + +def random_checksig_style(pubkey): + """Creates a random CHECKSIG* tapscript that would succeed with only the valid signature on witness stack.""" + return bytes(CScript([pubkey, OP_CHECKSIG])) + opcode = random.choice([OP_CHECKSIG, OP_CHECKSIGVERIFY, OP_CHECKSIGADD]) + if (opcode == OP_CHECKSIGVERIFY): + ret = CScript([pubkey, opcode, OP_1]) + elif (opcode == OP_CHECKSIGADD): + num = random.choice([0, 0x7fffffff, -0x7fffffff]) + ret = CScript([num, pubkey, opcode, num + 1, OP_EQUAL]) + else: + ret = CScript([pubkey, opcode]) + return bytes(ret) + +def random_bytes(n): + """Return a random bytes object of length n.""" + return bytes(random.getrandbits(8) for i in range(n)) + +def bitflipper(expr): + """Return a callable that evaluates expr and returns it with a random bitflip.""" + def fn(ctx): + sub = deep_eval(ctx, expr) + assert isinstance(sub, bytes) + return (int.from_bytes(sub, 'little') ^ (1 << random.randrange(len(sub) * 8))).to_bytes(len(sub), 'little') + return fn + +def zero_appender(expr): + """Return a callable that evaluates expr and returns it with a zero added.""" + return lambda ctx: deep_eval(ctx, expr) + b"\x00" + +def byte_popper(expr): + """Return a callable that evaluates expr and returns it with its last byte removed.""" + return lambda ctx: deep_eval(ctx, expr)[:-1] + +# Expected error strings + +ERR_SIG_SIZE = {"err_msg": "Invalid Schnorr signature size"} +ERR_SIG_HASHTYPE = {"err_msg": "Invalid Schnorr signature hash type"} +ERR_SIG_SCHNORR = {"err_msg": "Invalid Schnorr signature"} +ERR_OP_RETURN = {"err_msg": "OP_RETURN was encountered"} +ERR_CONTROLBLOCK_SIZE = {"err_msg": "Invalid Taproot control block size"} +ERR_WITNESS_PROGRAM_MISMATCH = {"err_msg": "Witness program hash mismatch"} +ERR_PUSH_LIMIT = {"err_msg": "Push value size limit exceeded"} +ERR_DISABLED_OPCODE = {"err_msg": "Attempted to use a disabled opcode"} +ERR_TAPSCRIPT_CHECKMULTISIG = {"err_msg": "OP_CHECKMULTISIG(VERIFY) is not available in tapscript"} +ERR_MINIMALIF = {"err_msg": "OP_IF/NOTIF argument must be minimal in tapscript"} +ERR_UNKNOWN_PUBKEY = {"err_msg": "Public key is neither compressed or uncompressed"} +ERR_STACK_SIZE = {"err_msg": "Stack size limit exceeded"} +ERR_CLEANSTACK = {"err_msg": "Stack size must be exactly one after execution"} +ERR_STACK_EMPTY = {"err_msg": "Operation not valid with the current stack size"} +ERR_SIGOPS_RATIO = {"err_msg": "Too much signature validation relative to witness weight"} +ERR_UNDECODABLE = {"err_msg": "Opcode missing or not understood"} +ERR_NO_SUCCESS = {"err_msg": "Script evaluated without error but finished with a false/empty top stack element"} +ERR_EMPTY_WITNESS = {"err_msg": "Witness program was passed an empty witness"} +ERR_CHECKSIGVERIFY = {"err_msg": "Script failed an OP_CHECKSIGVERIFY operation"} + +VALID_SIGHASHES_ECDSA = [ + SIGHASH_ALL, + SIGHASH_NONE, + SIGHASH_SINGLE, + SIGHASH_ANYONECANPAY + SIGHASH_ALL, + SIGHASH_ANYONECANPAY + SIGHASH_NONE, + SIGHASH_ANYONECANPAY + SIGHASH_SINGLE +] + +VALID_SIGHASHES_TAPROOT = [SIGHASH_DEFAULT] + VALID_SIGHASHES_ECDSA + +VALID_SIGHASHES_TAPROOT_SINGLE = [ + SIGHASH_SINGLE, + SIGHASH_ANYONECANPAY + SIGHASH_SINGLE +] + +VALID_SIGHASHES_TAPROOT_NO_SINGLE = [h for h in VALID_SIGHASHES_TAPROOT if h not in VALID_SIGHASHES_TAPROOT_SINGLE] + +SIGHASH_BITFLIP = {"failure": {"sighash": bitflipper(default_sighash)}} +SIG_POP_BYTE = {"failure": {"sign": byte_popper(default_sign)}} +SINGLE_SIG = {"inputs": [getter("sign")]} +SIG_ADD_ZERO = {"failure": {"sign": zero_appender(default_sign)}} + +DUST_LIMIT = 600 +MIN_FEE = 50000 + +# === Actual test cases === + + +def spenders_taproot_active(): + """Return a list of Spenders for testing post-Taproot activation behavior.""" + + secs = [generate_privkey() for _ in range(8)] + pubs = [compute_xonly_pubkey(sec)[0] for sec in secs] + + spenders = [] + + # == Tests for BIP340 signature validation. == + # These are primarily tested through the test vectors implemented in libsecp256k1, and in src/tests/key_tests.cpp. + # Some things are tested programmatically as well here. + + tap = taproot_construct(pubs[0]) + # Test with key with bit flipped. + add_spender(spenders, "sig/key", tap=tap, key=secs[0], failure={"key_tweaked": bitflipper(default_key_tweaked)}, **ERR_SIG_SCHNORR) + # Test with sighash with bit flipped. + add_spender(spenders, "sig/sighash", tap=tap, key=secs[0], failure={"sighash": bitflipper(default_sighash)}, **ERR_SIG_SCHNORR) + # Test with invalid R sign. + add_spender(spenders, "sig/flip_r", tap=tap, key=secs[0], failure={"flag_flip_r": True}, **ERR_SIG_SCHNORR) + # Test with invalid P sign. + add_spender(spenders, "sig/flip_p", tap=tap, key=secs[0], failure={"flag_flip_p": True}, **ERR_SIG_SCHNORR) + # Test with signature with bit flipped. + add_spender(spenders, "sig/bitflip", tap=tap, key=secs[0], failure={"signature": bitflipper(default_signature)}, **ERR_SIG_SCHNORR) + + # == Tests for signature hashing == + + # Run all tests once with no annex, and once with a valid random annex. + for annex in [None, lambda _: bytes([ANNEX_TAG]) + random_bytes(random.randrange(0, 250))]: + # Non-empty annex is non-standard + no_annex = annex is None + + # Sighash mutation tests (test all sighash combinations) + for hashtype in VALID_SIGHASHES_TAPROOT: + common = {"annex": annex, "hashtype": hashtype, "standard": no_annex} + + # Pure pubkey + tap = taproot_construct(pubs[0]) + add_spender(spenders, "sighash/purepk", tap=tap, key=secs[0], **common, **SIGHASH_BITFLIP, **ERR_SIG_SCHNORR) + + # Pubkey/P2PK script combination + scripts = [("s0", CScript(random_checksig_style(pubs[1])))] + tap = taproot_construct(pubs[0], scripts) + add_spender(spenders, "sighash/keypath_hashtype_%x" % hashtype, tap=tap, key=secs[0], **common, **SIGHASH_BITFLIP, **ERR_SIG_SCHNORR) + add_spender(spenders, "sighash/scriptpath_hashtype_%x" % hashtype, tap=tap, leaf="s0", key=secs[1], **common, **SINGLE_SIG, **SIGHASH_BITFLIP, **ERR_SIG_SCHNORR) + + # Test SIGHASH_SINGLE behavior in combination with mismatching outputs + if hashtype in VALID_SIGHASHES_TAPROOT_SINGLE: + add_spender(spenders, "sighash/keypath_hashtype_mis_%x" % hashtype, tap=tap, key=secs[0], annex=annex, standard=no_annex, hashtype_actual=random.choice(VALID_SIGHASHES_TAPROOT_NO_SINGLE), failure={"hashtype_actual": hashtype}, **ERR_SIG_HASHTYPE, need_vin_vout_mismatch=True) + add_spender(spenders, "sighash/scriptpath_hashtype_mis_%x" % hashtype, tap=tap, leaf="s0", key=secs[1], annex=annex, standard=no_annex, hashtype_actual=random.choice(VALID_SIGHASHES_TAPROOT_NO_SINGLE), **SINGLE_SIG, failure={"hashtype_actual": hashtype}, **ERR_SIG_HASHTYPE, need_vin_vout_mismatch=True) + + # Test OP_CODESEPARATOR impact on sighashing. + hashtype = lambda _: random.choice(VALID_SIGHASHES_TAPROOT) + common = {"annex": annex, "hashtype": hashtype, "standard": no_annex} + scripts = [ + ("pk_codesep", CScript(random_checksig_style(pubs[1]) + bytes([OP_CODESEPARATOR]))), # codesep after checksig + ("codesep_pk", CScript(bytes([OP_CODESEPARATOR]) + random_checksig_style(pubs[1]))), # codesep before checksig + ("branched_codesep", CScript([random_bytes(random.randrange(511)), OP_DROP, OP_IF, OP_CODESEPARATOR, pubs[0], OP_ELSE, OP_CODESEPARATOR, pubs[1], OP_ENDIF, OP_CHECKSIG])), # branch dependent codesep + ] + random.shuffle(scripts) + tap = taproot_construct(pubs[0], scripts) + add_spender(spenders, "sighash/pk_codesep", tap=tap, leaf="pk_codesep", key=secs[1], **common, **SINGLE_SIG, **SIGHASH_BITFLIP, **ERR_SIG_SCHNORR) + add_spender(spenders, "sighash/codesep_pk", tap=tap, leaf="codesep_pk", key=secs[1], codeseppos=0, **common, **SINGLE_SIG, **SIGHASH_BITFLIP, **ERR_SIG_SCHNORR) + add_spender(spenders, "sighash/branched_codesep/left", tap=tap, leaf="branched_codesep", key=secs[0], codeseppos=3, **common, inputs=[getter("sign"), b'\x01'], **SIGHASH_BITFLIP, **ERR_SIG_SCHNORR) + add_spender(spenders, "sighash/branched_codesep/right", tap=tap, leaf="branched_codesep", key=secs[1], codeseppos=6, **common, inputs=[getter("sign"), b''], **SIGHASH_BITFLIP, **ERR_SIG_SCHNORR) + + # Reusing the scripts above, test that various features affect the sighash. + add_spender(spenders, "sighash/annex", tap=tap, leaf="pk_codesep", key=secs[1], hashtype=hashtype, standard=False, **SINGLE_SIG, annex=bytes([ANNEX_TAG]), failure={"sighash": override(default_sighash, annex=None)}, **ERR_SIG_SCHNORR) + add_spender(spenders, "sighash/script", tap=tap, leaf="pk_codesep", key=secs[1], **common, **SINGLE_SIG, failure={"sighash": override(default_sighash, script_taproot=tap.leaves["codesep_pk"].script)}, **ERR_SIG_SCHNORR) + add_spender(spenders, "sighash/leafver", tap=tap, leaf="pk_codesep", key=secs[1], **common, **SINGLE_SIG, failure={"sighash": override(default_sighash, leafversion=random.choice([x & 0xFE for x in range(0x100) if x & 0xFE != 0xC0]))}, **ERR_SIG_SCHNORR) + add_spender(spenders, "sighash/scriptpath", tap=tap, leaf="pk_codesep", key=secs[1], **common, **SINGLE_SIG, failure={"sighash": override(default_sighash, leaf=None)}, **ERR_SIG_SCHNORR) + add_spender(spenders, "sighash/keypath", tap=tap, key=secs[0], **common, failure={"sighash": override(default_sighash, leaf="pk_codesep")}, **ERR_SIG_SCHNORR) + + # Test that invalid hashtypes don't work, both in key path and script path spends + hashtype = lambda _: random.choice(VALID_SIGHASHES_TAPROOT) + for invalid_hashtype in [x for x in range(0x100) if x not in VALID_SIGHASHES_TAPROOT]: + add_spender(spenders, "sighash/keypath_unk_hashtype_%x" % invalid_hashtype, tap=tap, key=secs[0], hashtype=hashtype, failure={"hashtype": invalid_hashtype}, **ERR_SIG_HASHTYPE) + add_spender(spenders, "sighash/scriptpath_unk_hashtype_%x" % invalid_hashtype, tap=tap, leaf="pk_codesep", key=secs[1], **SINGLE_SIG, hashtype=hashtype, failure={"hashtype": invalid_hashtype}, **ERR_SIG_HASHTYPE) + + # Test that hashtype 0 cannot have a hashtype byte, and 1 must have one. + add_spender(spenders, "sighash/hashtype0_byte_keypath", tap=tap, key=secs[0], hashtype=SIGHASH_DEFAULT, failure={"bytes_hashtype": bytes([SIGHASH_DEFAULT])}, **ERR_SIG_HASHTYPE) + add_spender(spenders, "sighash/hashtype0_byte_scriptpath", tap=tap, leaf="pk_codesep", key=secs[1], **SINGLE_SIG, hashtype=SIGHASH_DEFAULT, failure={"bytes_hashtype": bytes([SIGHASH_DEFAULT])}, **ERR_SIG_HASHTYPE) + add_spender(spenders, "sighash/hashtype1_byte_keypath", tap=tap, key=secs[0], hashtype=SIGHASH_ALL, failure={"bytes_hashtype": b''}, **ERR_SIG_SCHNORR) + add_spender(spenders, "sighash/hashtype1_byte_scriptpath", tap=tap, leaf="pk_codesep", key=secs[1], **SINGLE_SIG, hashtype=SIGHASH_ALL, failure={"bytes_hashtype": b''}, **ERR_SIG_SCHNORR) + # Test that hashtype 0 and hashtype 1 cannot be transmuted into each other. + add_spender(spenders, "sighash/hashtype0to1_keypath", tap=tap, key=secs[0], hashtype=SIGHASH_DEFAULT, failure={"bytes_hashtype": bytes([SIGHASH_ALL])}, **ERR_SIG_SCHNORR) + add_spender(spenders, "sighash/hashtype0to1_scriptpath", tap=tap, leaf="pk_codesep", key=secs[1], **SINGLE_SIG, hashtype=SIGHASH_DEFAULT, failure={"bytes_hashtype": bytes([SIGHASH_ALL])}, **ERR_SIG_SCHNORR) + add_spender(spenders, "sighash/hashtype1to0_keypath", tap=tap, key=secs[0], hashtype=SIGHASH_ALL, failure={"bytes_hashtype": b''}, **ERR_SIG_SCHNORR) + add_spender(spenders, "sighash/hashtype1to0_scriptpath", tap=tap, leaf="pk_codesep", key=secs[1], **SINGLE_SIG, hashtype=SIGHASH_ALL, failure={"bytes_hashtype": b''}, **ERR_SIG_SCHNORR) + + # Test aspects of signatures with unusual lengths + for hashtype in [SIGHASH_DEFAULT, random.choice(VALID_SIGHASHES_TAPROOT)]: + scripts = [ + ("csv", CScript([pubs[2], OP_CHECKSIGVERIFY, OP_1])), + ("cs_pos", CScript([pubs[2], OP_CHECKSIG])), + ("csa_pos", CScript([OP_0, pubs[2], OP_CHECKSIGADD, OP_1, OP_EQUAL])), + ("cs_neg", CScript([pubs[2], OP_CHECKSIG, OP_NOT])), + ("csa_neg", CScript([OP_2, pubs[2], OP_CHECKSIGADD, OP_2, OP_EQUAL])) + ] + random.shuffle(scripts) + tap = taproot_construct(pubs[3], scripts) + # Empty signatures + add_spender(spenders, "siglen/empty_keypath", tap=tap, key=secs[3], hashtype=hashtype, failure={"sign": b""}, **ERR_SIG_SIZE) + add_spender(spenders, "siglen/empty_csv", tap=tap, key=secs[2], leaf="csv", hashtype=hashtype, **SINGLE_SIG, failure={"sign": b""}, **ERR_CHECKSIGVERIFY) + add_spender(spenders, "siglen/empty_cs", tap=tap, key=secs[2], leaf="cs_pos", hashtype=hashtype, **SINGLE_SIG, failure={"sign": b""}, **ERR_NO_SUCCESS) + add_spender(spenders, "siglen/empty_csa", tap=tap, key=secs[2], leaf="csa_pos", hashtype=hashtype, **SINGLE_SIG, failure={"sign": b""}, **ERR_NO_SUCCESS) + add_spender(spenders, "siglen/empty_cs_neg", tap=tap, key=secs[2], leaf="cs_neg", hashtype=hashtype, **SINGLE_SIG, sign=b"", failure={"sign": lambda _: random_bytes(random.randrange(1, 63))}, **ERR_SIG_SIZE) + add_spender(spenders, "siglen/empty_csa_neg", tap=tap, key=secs[2], leaf="csa_neg", hashtype=hashtype, **SINGLE_SIG, sign=b"", failure={"sign": lambda _: random_bytes(random.randrange(66, 100))}, **ERR_SIG_SIZE) + # Appending a zero byte to signatures invalidates them + add_spender(spenders, "siglen/padzero_keypath", tap=tap, key=secs[3], hashtype=hashtype, **SIG_ADD_ZERO, **(ERR_SIG_HASHTYPE if hashtype == SIGHASH_DEFAULT else ERR_SIG_SIZE)) + add_spender(spenders, "siglen/padzero_csv", tap=tap, key=secs[2], leaf="csv", hashtype=hashtype, **SINGLE_SIG, **SIG_ADD_ZERO, **(ERR_SIG_HASHTYPE if hashtype == SIGHASH_DEFAULT else ERR_SIG_SIZE)) + add_spender(spenders, "siglen/padzero_cs", tap=tap, key=secs[2], leaf="cs_pos", hashtype=hashtype, **SINGLE_SIG, **SIG_ADD_ZERO, **(ERR_SIG_HASHTYPE if hashtype == SIGHASH_DEFAULT else ERR_SIG_SIZE)) + add_spender(spenders, "siglen/padzero_csa", tap=tap, key=secs[2], leaf="csa_pos", hashtype=hashtype, **SINGLE_SIG, **SIG_ADD_ZERO, **(ERR_SIG_HASHTYPE if hashtype == SIGHASH_DEFAULT else ERR_SIG_SIZE)) + add_spender(spenders, "siglen/padzero_cs_neg", tap=tap, key=secs[2], leaf="cs_neg", hashtype=hashtype, **SINGLE_SIG, sign=b"", **SIG_ADD_ZERO, **(ERR_SIG_HASHTYPE if hashtype == SIGHASH_DEFAULT else ERR_SIG_SIZE)) + add_spender(spenders, "siglen/padzero_csa_neg", tap=tap, key=secs[2], leaf="csa_neg", hashtype=hashtype, **SINGLE_SIG, sign=b"", **SIG_ADD_ZERO, **(ERR_SIG_HASHTYPE if hashtype == SIGHASH_DEFAULT else ERR_SIG_SIZE)) + # Removing the last byte from signatures invalidates them + add_spender(spenders, "siglen/popbyte_keypath", tap=tap, key=secs[3], hashtype=hashtype, **SIG_POP_BYTE, **(ERR_SIG_SIZE if hashtype == SIGHASH_DEFAULT else ERR_SIG_SCHNORR)) + add_spender(spenders, "siglen/popbyte_csv", tap=tap, key=secs[2], leaf="csv", hashtype=hashtype, **SINGLE_SIG, **SIG_POP_BYTE, **(ERR_SIG_SIZE if hashtype == SIGHASH_DEFAULT else ERR_SIG_SCHNORR)) + add_spender(spenders, "siglen/popbyte_cs", tap=tap, key=secs[2], leaf="cs_pos", hashtype=hashtype, **SINGLE_SIG, **SIG_POP_BYTE, **(ERR_SIG_SIZE if hashtype == SIGHASH_DEFAULT else ERR_SIG_SCHNORR)) + add_spender(spenders, "siglen/popbyte_csa", tap=tap, key=secs[2], leaf="csa_pos", hashtype=hashtype, **SINGLE_SIG, **SIG_POP_BYTE, **(ERR_SIG_SIZE if hashtype == SIGHASH_DEFAULT else ERR_SIG_SCHNORR)) + add_spender(spenders, "siglen/popbyte_cs_neg", tap=tap, key=secs[2], leaf="cs_neg", hashtype=hashtype, **SINGLE_SIG, sign=b"", **SIG_POP_BYTE, **(ERR_SIG_SIZE if hashtype == SIGHASH_DEFAULT else ERR_SIG_SCHNORR)) + add_spender(spenders, "siglen/popbyte_csa_neg", tap=tap, key=secs[2], leaf="csa_neg", hashtype=hashtype, **SINGLE_SIG, sign=b"", **SIG_POP_BYTE, **(ERR_SIG_SIZE if hashtype == SIGHASH_DEFAULT else ERR_SIG_SCHNORR)) + # Verify that an invalid signature is not allowed, not even when the CHECKSIG* is expected to fail. + add_spender(spenders, "siglen/invalid_cs_neg", tap=tap, key=secs[2], leaf="cs_neg", hashtype=hashtype, **SINGLE_SIG, sign=b"", failure={"sign": default_sign, "sighash": bitflipper(default_sighash)}, **ERR_SIG_SCHNORR) + add_spender(spenders, "siglen/invalid_csa_neg", tap=tap, key=secs[2], leaf="csa_neg", hashtype=hashtype, **SINGLE_SIG, sign=b"", failure={"sign": default_sign, "sighash": bitflipper(default_sighash)}, **ERR_SIG_SCHNORR) + + # == Test that BIP341 spending only applies to witness version 1, program length 32, no P2SH == + + for p2sh in [False, True]: + for witver in range(1, 17): + for witlen in [20, 31, 32, 33]: + def mutate(spk): + prog = spk[2:] + assert len(prog) == 32 + if witlen < 32: + prog = prog[0:witlen] + elif witlen > 32: + prog += bytes([0 for _ in range(witlen - 32)]) + return CScript([CScriptOp.encode_op_n(witver), prog]) + scripts = [("s0", CScript([pubs[0], OP_CHECKSIG])), ("dummy", CScript([OP_RETURN]))] + tap = taproot_construct(pubs[1], scripts) + if not p2sh and witver == 1 and witlen == 32: + add_spender(spenders, "applic/keypath", p2sh=p2sh, spk_mutate_pre_p2sh=mutate, tap=tap, key=secs[1], **SIGHASH_BITFLIP, **ERR_SIG_SCHNORR) + add_spender(spenders, "applic/scriptpath", p2sh=p2sh, leaf="s0", spk_mutate_pre_p2sh=mutate, tap=tap, key=secs[0], **SINGLE_SIG, failure={"leaf": "dummy"}, **ERR_OP_RETURN) + else: + add_spender(spenders, "applic/keypath", p2sh=p2sh, spk_mutate_pre_p2sh=mutate, tap=tap, key=secs[1], standard=False) + add_spender(spenders, "applic/scriptpath", p2sh=p2sh, leaf="s0", spk_mutate_pre_p2sh=mutate, tap=tap, key=secs[0], **SINGLE_SIG, standard=False) + + # == Test various aspects of BIP341 spending paths == + + # A set of functions that compute the hashing partner in a Merkle tree, designed to exercise + # edge cases. This relies on the taproot_construct feature that a lambda can be passed in + # instead of a subtree, to compute the partner to be hashed with. + PARTNER_MERKLE_FN = [ + # Combine with itself + lambda h: h, + # Combine with hash 0 + lambda h: bytes([0 for _ in range(32)]), + # Combine with hash 2^256-1 + lambda h: bytes([0xff for _ in range(32)]), + # Combine with itself-1 (BE) + lambda h: (int.from_bytes(h, 'big') - 1).to_bytes(32, 'big'), + # Combine with itself+1 (BE) + lambda h: (int.from_bytes(h, 'big') + 1).to_bytes(32, 'big'), + # Combine with itself-1 (LE) + lambda h: (int.from_bytes(h, 'little') - 1).to_bytes(32, 'big'), + # Combine with itself+1 (LE) + lambda h: (int.from_bytes(h, 'little') + 1).to_bytes(32, 'little'), + # Combine with random bitflipped version of self. + lambda h: (int.from_bytes(h, 'little') ^ (1 << random.randrange(256))).to_bytes(32, 'little') + ] + # Start with a tree of that has depth 1 for "128deep" and depth 2 for "129deep". + scripts = [("128deep", CScript([pubs[0], OP_CHECKSIG])), [("129deep", CScript([pubs[0], OP_CHECKSIG])), random.choice(PARTNER_MERKLE_FN)]] + # Add 127 nodes on top of that tree, so that "128deep" and "129deep" end up at their designated depths. + for _ in range(127): + scripts = [scripts, random.choice(PARTNER_MERKLE_FN)] + tap = taproot_construct(pubs[0], scripts) + # Test that spends with a depth of 128 work, but 129 doesn't (even with a tree with weird Merkle branches in it). + add_spender(spenders, "spendpath/merklelimit", tap=tap, leaf="128deep", **SINGLE_SIG, key=secs[0], failure={"leaf": "129deep"}, **ERR_CONTROLBLOCK_SIZE) + # Test that flipping the negation bit invalidates spends. + add_spender(spenders, "spendpath/negflag", tap=tap, leaf="128deep", **SINGLE_SIG, key=secs[0], failure={"negflag": lambda ctx: 1 - default_negflag(ctx)}, **ERR_WITNESS_PROGRAM_MISMATCH) + # Test that bitflips in the Merkle branch invalidate it. + add_spender(spenders, "spendpath/bitflipmerkle", tap=tap, leaf="128deep", **SINGLE_SIG, key=secs[0], failure={"merklebranch": bitflipper(default_merklebranch)}, **ERR_WITNESS_PROGRAM_MISMATCH) + # Test that bitflips in the inner pubkey invalidate it. + add_spender(spenders, "spendpath/bitflippubkey", tap=tap, leaf="128deep", **SINGLE_SIG, key=secs[0], failure={"pubkey_inner": bitflipper(default_pubkey_inner)}, **ERR_WITNESS_PROGRAM_MISMATCH) + # Test that empty witnesses are invalid. + add_spender(spenders, "spendpath/emptywit", tap=tap, leaf="128deep", **SINGLE_SIG, key=secs[0], failure={"witness": []}, **ERR_EMPTY_WITNESS) + # Test that adding garbage to the control block invalidates it. + add_spender(spenders, "spendpath/padlongcontrol", tap=tap, leaf="128deep", **SINGLE_SIG, key=secs[0], failure={"controlblock": lambda ctx: default_controlblock(ctx) + random_bytes(random.randrange(1, 32))}, **ERR_CONTROLBLOCK_SIZE) + # Test that truncating the control block invalidates it. + add_spender(spenders, "spendpath/trunclongcontrol", tap=tap, leaf="128deep", **SINGLE_SIG, key=secs[0], failure={"controlblock": lambda ctx: default_merklebranch(ctx)[0:random.randrange(1, 32)]}, **ERR_CONTROLBLOCK_SIZE) + + scripts = [("s", CScript([pubs[0], OP_CHECKSIG]))] + tap = taproot_construct(pubs[1], scripts) + # Test that adding garbage to the control block invalidates it. + add_spender(spenders, "spendpath/padshortcontrol", tap=tap, leaf="s", **SINGLE_SIG, key=secs[0], failure={"controlblock": lambda ctx: default_controlblock(ctx) + random_bytes(random.randrange(1, 32))}, **ERR_CONTROLBLOCK_SIZE) + # Test that truncating the control block invalidates it. + add_spender(spenders, "spendpath/truncshortcontrol", tap=tap, leaf="s", **SINGLE_SIG, key=secs[0], failure={"controlblock": lambda ctx: default_merklebranch(ctx)[0:random.randrange(1, 32)]}, **ERR_CONTROLBLOCK_SIZE) + # Test that truncating the control block to 1 byte ("-1 Merkle length") invalidates it + add_spender(spenders, "spendpath/trunc1shortcontrol", tap=tap, leaf="s", **SINGLE_SIG, key=secs[0], failure={"controlblock": lambda ctx: default_merklebranch(ctx)[0:1]}, **ERR_CONTROLBLOCK_SIZE) + + # == Test BIP342 edge cases == + + csa_low_val = random.randrange(0, 17) # Within range for OP_n + csa_low_result = csa_low_val + 1 + + csa_high_val = random.randrange(17, 100) if random.getrandbits(1) else random.randrange(-100, -1) # Outside OP_n range + csa_high_result = csa_high_val + 1 + + OVERSIZE_NUMBER = 2**31 + assert_equal(len(CScriptNum.encode(CScriptNum(OVERSIZE_NUMBER))), 6) + assert_equal(len(CScriptNum.encode(CScriptNum(OVERSIZE_NUMBER-1))), 5) + + big_choices = [] + big_scriptops = [] + for i in range(1000): + r = random.randrange(len(pubs)) + big_choices.append(r) + big_scriptops += [pubs[r], OP_CHECKSIGVERIFY] + + + def big_spend_inputs(ctx): + """Helper function to construct the script input for t33/t34 below.""" + # Instead of signing 999 times, precompute signatures for every (key, hashtype) combination + sigs = {} + for ht in VALID_SIGHASHES_TAPROOT: + for k in range(len(pubs)): + sigs[(k, ht)] = override(default_sign, hashtype=ht, key=secs[k])(ctx) + num = get(ctx, "num") + return [sigs[(big_choices[i], random.choice(VALID_SIGHASHES_TAPROOT))] for i in range(num - 1, -1, -1)] + + # Various BIP342 features + scripts = [ + # 0) drop stack element and OP_CHECKSIG + ("t0", CScript([OP_DROP, pubs[1], OP_CHECKSIG])), + # 1) normal OP_CHECKSIG + ("t1", CScript([pubs[1], OP_CHECKSIG])), + # 2) normal OP_CHECKSIGVERIFY + ("t2", CScript([pubs[1], OP_CHECKSIGVERIFY, OP_1])), + # 3) Hypothetical OP_CHECKMULTISIG script that takes a single sig as input + ("t3", CScript([OP_0, OP_SWAP, OP_1, pubs[1], OP_1, OP_CHECKMULTISIG])), + # 4) Hypothetical OP_CHECKMULTISIGVERIFY script that takes a single sig as input + ("t4", CScript([OP_0, OP_SWAP, OP_1, pubs[1], OP_1, OP_CHECKMULTISIGVERIFY, OP_1])), + # 5) OP_IF script that needs a true input + ("t5", CScript([OP_IF, pubs[1], OP_CHECKSIG, OP_ELSE, OP_RETURN, OP_ENDIF])), + # 6) OP_NOTIF script that needs a true input + ("t6", CScript([OP_NOTIF, OP_RETURN, OP_ELSE, pubs[1], OP_CHECKSIG, OP_ENDIF])), + # 7) OP_CHECKSIG with an empty key + ("t7", CScript([OP_0, OP_CHECKSIG])), + # 8) OP_CHECKSIGVERIFY with an empty key + ("t8", CScript([OP_0, OP_CHECKSIGVERIFY, OP_1])), + # 9) normal OP_CHECKSIGADD that also ensures return value is correct + ("t9", CScript([csa_low_val, pubs[1], OP_CHECKSIGADD, csa_low_result, OP_EQUAL])), + # 10) OP_CHECKSIGADD with empty key + ("t10", CScript([csa_low_val, OP_0, OP_CHECKSIGADD, csa_low_result, OP_EQUAL])), + # 11) OP_CHECKSIGADD with missing counter stack element + ("t11", CScript([pubs[1], OP_CHECKSIGADD, OP_1, OP_EQUAL])), + # 12) OP_CHECKSIG that needs invalid signature + ("t12", CScript([pubs[1], OP_CHECKSIGVERIFY, pubs[0], OP_CHECKSIG, OP_NOT])), + # 13) OP_CHECKSIG with empty key that needs invalid signature + ("t13", CScript([pubs[1], OP_CHECKSIGVERIFY, OP_0, OP_CHECKSIG, OP_NOT])), + # 14) OP_CHECKSIGADD that needs invalid signature + ("t14", CScript([pubs[1], OP_CHECKSIGVERIFY, OP_0, pubs[0], OP_CHECKSIGADD, OP_NOT])), + # 15) OP_CHECKSIGADD with empty key that needs invalid signature + ("t15", CScript([pubs[1], OP_CHECKSIGVERIFY, OP_0, OP_0, OP_CHECKSIGADD, OP_NOT])), + # 16) OP_CHECKSIG with unknown pubkey type + ("t16", CScript([OP_1, OP_CHECKSIG])), + # 17) OP_CHECKSIGADD with unknown pubkey type + ("t17", CScript([OP_0, OP_1, OP_CHECKSIGADD])), + # 18) OP_CHECKSIGVERIFY with unknown pubkey type + ("t18", CScript([OP_1, OP_CHECKSIGVERIFY, OP_1])), + # 19) script longer than 10000 bytes and over 201 non-push opcodes + ("t19", CScript([OP_0, OP_0, OP_2DROP] * 10001 + [pubs[1], OP_CHECKSIG])), + # 20) OP_CHECKSIGVERIFY with empty key + ("t20", CScript([pubs[1], OP_CHECKSIGVERIFY, OP_0, OP_0, OP_CHECKSIGVERIFY, OP_1])), + # 21) Script that grows the stack to 1000 elements + ("t21", CScript([pubs[1], OP_CHECKSIGVERIFY, OP_1] + [OP_DUP] * 999 + [OP_DROP] * 999)), + # 22) Script that grows the stack to 1001 elements + ("t22", CScript([pubs[1], OP_CHECKSIGVERIFY, OP_1] + [OP_DUP] * 1000 + [OP_DROP] * 1000)), + # 23) Script that expects an input stack of 1000 elements + ("t23", CScript([OP_DROP] * 999 + [pubs[1], OP_CHECKSIG])), + # 24) Script that expects an input stack of 1001 elements + ("t24", CScript([OP_DROP] * 1000 + [pubs[1], OP_CHECKSIG])), + # 25) Script that pushes a MAX_SCRIPT_ELEMENT_SIZE-bytes element + ("t25", CScript([random_bytes(MAX_SCRIPT_ELEMENT_SIZE), OP_DROP, pubs[1], OP_CHECKSIG])), + # 26) Script that pushes a (MAX_SCRIPT_ELEMENT_SIZE+1)-bytes element + ("t26", CScript([random_bytes(MAX_SCRIPT_ELEMENT_SIZE+1), OP_DROP, pubs[1], OP_CHECKSIG])), + # 27) CHECKSIGADD that must fail because numeric argument number is >4 bytes + ("t27", CScript([CScriptNum(OVERSIZE_NUMBER), pubs[1], OP_CHECKSIGADD])), + # 28) Pushes random CScriptNum value, checks OP_CHECKSIGADD result + ("t28", CScript([csa_high_val, pubs[1], OP_CHECKSIGADD, csa_high_result, OP_EQUAL])), + # 29) CHECKSIGADD that succeeds with proper sig because numeric argument number is <=4 bytes + ("t29", CScript([CScriptNum(OVERSIZE_NUMBER-1), pubs[1], OP_CHECKSIGADD])), + # 30) Variant of t1 with "normal" 33-byte pubkey + ("t30", CScript([b'\x03' + pubs[1], OP_CHECKSIG])), + # 31) Variant of t2 with "normal" 33-byte pubkey + ("t31", CScript([b'\x02' + pubs[1], OP_CHECKSIGVERIFY, OP_1])), + # 32) Variant of t28 with "normal" 33-byte pubkey + ("t32", CScript([csa_high_val, b'\x03' + pubs[1], OP_CHECKSIGADD, csa_high_result, OP_EQUAL])), + # 33) 999-of-999 multisig + ("t33", CScript(big_scriptops[:1998] + [OP_1])), + # 34) 1000-of-1000 multisig + ("t34", CScript(big_scriptops[:2000] + [OP_1])), + # 35) Variant of t9 that uses a non-minimally encoded input arg + ("t35", CScript([bytes([csa_low_val]), pubs[1], OP_CHECKSIGADD, csa_low_result, OP_EQUAL])), + # 36) Empty script + ("t36", CScript([])), + ] + # Add many dummies to test huge trees + for j in range(100000): + scripts.append((None, CScript([OP_RETURN, random.randrange(100000)]))) + random.shuffle(scripts) + tap = taproot_construct(pubs[0], scripts) + common = { + "hashtype": hashtype, + "key": secs[1], + "tap": tap, + } + # Test that MAX_SCRIPT_ELEMENT_SIZE byte stack element inputs are valid, but not one more (and 80 bytes is standard but 81 is not). + add_spender(spenders, "tapscript/inputmaxlimit", leaf="t0", **common, standard=False, inputs=[getter("sign"), random_bytes(MAX_SCRIPT_ELEMENT_SIZE)], failure={"inputs": [getter("sign"), random_bytes(MAX_SCRIPT_ELEMENT_SIZE+1)]}, **ERR_PUSH_LIMIT) + add_spender(spenders, "tapscript/input80limit", leaf="t0", **common, inputs=[getter("sign"), random_bytes(80)]) + add_spender(spenders, "tapscript/input81limit", leaf="t0", **common, standard=False, inputs=[getter("sign"), random_bytes(81)]) + # Test that OP_CHECKMULTISIG and OP_CHECKMULTISIGVERIFY cause failure, but OP_CHECKSIG and OP_CHECKSIGVERIFY work. + add_spender(spenders, "tapscript/disabled_checkmultisig", leaf="t1", **common, **SINGLE_SIG, failure={"leaf": "t3"}, **ERR_TAPSCRIPT_CHECKMULTISIG) + add_spender(spenders, "tapscript/disabled_checkmultisigverify", leaf="t2", **common, **SINGLE_SIG, failure={"leaf": "t4"}, **ERR_TAPSCRIPT_CHECKMULTISIG) + # Test that OP_IF and OP_NOTIF do not accept non-0x01 as truth value (the MINIMALIF rule is consensus in Tapscript) + add_spender(spenders, "tapscript/minimalif", leaf="t5", **common, inputs=[getter("sign"), b'\x01'], failure={"inputs": [getter("sign"), b'\x02']}, **ERR_MINIMALIF) + add_spender(spenders, "tapscript/minimalnotif", leaf="t6", **common, inputs=[getter("sign"), b'\x01'], failure={"inputs": [getter("sign"), b'\x03']}, **ERR_MINIMALIF) + add_spender(spenders, "tapscript/minimalif", leaf="t5", **common, inputs=[getter("sign"), b'\x01'], failure={"inputs": [getter("sign"), b'\x0001']}, **ERR_MINIMALIF) + add_spender(spenders, "tapscript/minimalnotif", leaf="t6", **common, inputs=[getter("sign"), b'\x01'], failure={"inputs": [getter("sign"), b'\x0100']}, **ERR_MINIMALIF) + # Test that 1-byte public keys (which are unknown) are acceptable but nonstandard with unrelated signatures, but 0-byte public keys are not valid. + add_spender(spenders, "tapscript/unkpk/checksig", leaf="t16", standard=False, **common, **SINGLE_SIG, failure={"leaf": "t7"}, **ERR_UNKNOWN_PUBKEY) + add_spender(spenders, "tapscript/unkpk/checksigadd", leaf="t17", standard=False, **common, **SINGLE_SIG, failure={"leaf": "t10"}, **ERR_UNKNOWN_PUBKEY) + add_spender(spenders, "tapscript/unkpk/checksigverify", leaf="t18", standard=False, **common, **SINGLE_SIG, failure={"leaf": "t8"}, **ERR_UNKNOWN_PUBKEY) + # Test that 33-byte public keys (which are unknown) are acceptable but nonstandard with valid signatures, but normal pubkeys are not valid in that case. + add_spender(spenders, "tapscript/oldpk/checksig", leaf="t30", standard=False, **common, **SINGLE_SIG, sighash=bitflipper(default_sighash), failure={"leaf": "t1"}, **ERR_SIG_SCHNORR) + add_spender(spenders, "tapscript/oldpk/checksigadd", leaf="t31", standard=False, **common, **SINGLE_SIG, sighash=bitflipper(default_sighash), failure={"leaf": "t2"}, **ERR_SIG_SCHNORR) + add_spender(spenders, "tapscript/oldpk/checksigverify", leaf="t32", standard=False, **common, **SINGLE_SIG, sighash=bitflipper(default_sighash), failure={"leaf": "t28"}, **ERR_SIG_SCHNORR) + # Test that 0-byte public keys are not acceptable. + add_spender(spenders, "tapscript/emptypk/checksig", leaf="t1", **SINGLE_SIG, **common, failure={"leaf": "t7"}, **ERR_UNKNOWN_PUBKEY) + add_spender(spenders, "tapscript/emptypk/checksigverify", leaf="t2", **SINGLE_SIG, **common, failure={"leaf": "t8"}, **ERR_UNKNOWN_PUBKEY) + add_spender(spenders, "tapscript/emptypk/checksigadd", leaf="t9", **SINGLE_SIG, **common, failure={"leaf": "t10"}, **ERR_UNKNOWN_PUBKEY) + add_spender(spenders, "tapscript/emptypk/checksigadd", leaf="t35", standard=False, **SINGLE_SIG, **common, failure={"leaf": "t10"}, **ERR_UNKNOWN_PUBKEY) + # Test that OP_CHECKSIGADD results are as expected + add_spender(spenders, "tapscript/checksigaddresults", leaf="t28", **SINGLE_SIG, **common, failure={"leaf": "t27"}, err_msg="unknown error") + add_spender(spenders, "tapscript/checksigaddoversize", leaf="t29", **SINGLE_SIG, **common, failure={"leaf": "t27"}, err_msg="unknown error") + # Test that OP_CHECKSIGADD requires 3 stack elements. + add_spender(spenders, "tapscript/checksigadd3args", leaf="t9", **SINGLE_SIG, **common, failure={"leaf": "t11"}, **ERR_STACK_EMPTY) + # Test that empty signatures do not cause script failure in OP_CHECKSIG and OP_CHECKSIGADD (but do fail with empty pubkey, and do fail OP_CHECKSIGVERIFY) + add_spender(spenders, "tapscript/emptysigs/checksig", leaf="t12", **common, inputs=[b'', getter("sign")], failure={"leaf": "t13"}, **ERR_UNKNOWN_PUBKEY) + add_spender(spenders, "tapscript/emptysigs/nochecksigverify", leaf="t12", **common, inputs=[b'', getter("sign")], failure={"leaf": "t20"}, **ERR_UNKNOWN_PUBKEY) + add_spender(spenders, "tapscript/emptysigs/checksigadd", leaf="t14", **common, inputs=[b'', getter("sign")], failure={"leaf": "t15"}, **ERR_UNKNOWN_PUBKEY) + # Test that scripts over 10000 bytes (and over 201 non-push ops) are acceptable. + add_spender(spenders, "tapscript/no10000limit", leaf="t19", **SINGLE_SIG, **common) + # Test that a stack size of 1000 elements is permitted, but 1001 isn't. + add_spender(spenders, "tapscript/1000stack", leaf="t21", **SINGLE_SIG, **common, failure={"leaf": "t22"}, **ERR_STACK_SIZE) + # Test that an input stack size of 1000 elements is permitted, but 1001 isn't. + add_spender(spenders, "tapscript/1000inputs", leaf="t23", **common, inputs=[getter("sign")] + [b'' for _ in range(999)], failure={"leaf": "t24", "inputs": [getter("sign")] + [b'' for _ in range(1000)]}, **ERR_STACK_SIZE) + # Test that pushing a MAX_SCRIPT_ELEMENT_SIZE byte stack element is valid, but one longer is not. + add_spender(spenders, "tapscript/pushmaxlimit", leaf="t25", **common, **SINGLE_SIG, failure={"leaf": "t26"}, **ERR_PUSH_LIMIT) + # Test that 999-of-999 multisig works (but 1000-of-1000 triggers stack size limits) + add_spender(spenders, "tapscript/bigmulti", leaf="t33", **common, inputs=big_spend_inputs, num=999, failure={"leaf": "t34", "num": 1000}, **ERR_STACK_SIZE) + # Test that the CLEANSTACK rule is consensus critical in tapscript + add_spender(spenders, "tapscript/cleanstack", leaf="t36", tap=tap, inputs=[b'\x01'], failure={"inputs": [b'\x01', b'\x01']}, **ERR_CLEANSTACK) + + # == Test for sigops ratio limit == + + # Given a number n, and a public key pk, functions that produce a (CScript, sigops). Each script takes as + # input a valid signature with the passed pk followed by a dummy push of bytes that are to be dropped, and + # will execute sigops signature checks. + SIGOPS_RATIO_SCRIPTS = [ + # n OP_CHECKSIGVERFIYs and 1 OP_CHECKSIG. + lambda n, pk: (CScript([OP_DROP, pk] + [OP_2DUP, OP_CHECKSIGVERIFY] * n + [OP_CHECKSIG]), n + 1), + # n OP_CHECKSIGVERIFYs and 1 OP_CHECKSIGADD, but also one unexecuted OP_CHECKSIGVERIFY. + lambda n, pk: (CScript([OP_DROP, pk, OP_0, OP_IF, OP_2DUP, OP_CHECKSIGVERIFY, OP_ENDIF] + [OP_2DUP, OP_CHECKSIGVERIFY] * n + [OP_2, OP_SWAP, OP_CHECKSIGADD, OP_3, OP_EQUAL]), n + 1), + # n OP_CHECKSIGVERIFYs and 1 OP_CHECKSIGADD, but also one unexecuted OP_CHECKSIG. + lambda n, pk: (CScript([random_bytes(220), OP_2DROP, pk, OP_1, OP_NOTIF, OP_2DUP, OP_CHECKSIG, OP_VERIFY, OP_ENDIF] + [OP_2DUP, OP_CHECKSIGVERIFY] * n + [OP_4, OP_SWAP, OP_CHECKSIGADD, OP_5, OP_EQUAL]), n + 1), + # n OP_CHECKSIGVERFIYs and 1 OP_CHECKSIGADD, but also one unexecuted OP_CHECKSIGADD. + lambda n, pk: (CScript([OP_DROP, pk, OP_1, OP_IF, OP_ELSE, OP_2DUP, OP_6, OP_SWAP, OP_CHECKSIGADD, OP_7, OP_EQUALVERIFY, OP_ENDIF] + [OP_2DUP, OP_CHECKSIGVERIFY] * n + [OP_8, OP_SWAP, OP_CHECKSIGADD, OP_9, OP_EQUAL]), n + 1), + # n+1 OP_CHECKSIGs, but also one OP_CHECKSIG with an empty signature. + lambda n, pk: (CScript([OP_DROP, OP_0, pk, OP_CHECKSIG, OP_NOT, OP_VERIFY, pk] + [OP_2DUP, OP_CHECKSIG, OP_VERIFY] * n + [OP_CHECKSIG]), n + 1), + # n OP_CHECKSIGADDs and 1 OP_CHECKSIG, but also an OP_CHECKSIGADD with an empty signature. + lambda n, pk: (CScript([OP_DROP, OP_0, OP_10, pk, OP_CHECKSIGADD, OP_10, OP_EQUALVERIFY, pk] + [OP_2DUP, OP_16, OP_SWAP, OP_CHECKSIGADD, b'\x11', OP_EQUALVERIFY] * n + [OP_CHECKSIG]), n + 1), + ] + for annex in [None, bytes([ANNEX_TAG]) + random_bytes(random.randrange(1000))]: + for hashtype in [SIGHASH_DEFAULT, SIGHASH_ALL]: + for pubkey in [pubs[1], random_bytes(random.choice([x for x in range(2, 81) if x != 32]))]: + for fn_num, fn in enumerate(SIGOPS_RATIO_SCRIPTS): + merkledepth = random.randrange(129) + + + def predict_sigops_ratio(n, dummy_size): + """Predict whether spending fn(n, pubkey) with dummy_size will pass the ratio test.""" + script, sigops = fn(n, pubkey) + # Predict the size of the witness for a given choice of n + stacklen_size = 1 + sig_size = 64 + (hashtype != SIGHASH_DEFAULT) + siglen_size = 1 + dummylen_size = 1 + 2 * (dummy_size >= 253) + script_size = len(script) + scriptlen_size = 1 + 2 * (script_size >= 253) + control_size = 33 + 32 * merkledepth + controllen_size = 1 + 2 * (control_size >= 253) + annex_size = 0 if annex is None else len(annex) + annexlen_size = 0 if annex is None else 1 + 2 * (annex_size >= 253) + witsize = stacklen_size + sig_size + siglen_size + dummy_size + dummylen_size + script_size + scriptlen_size + control_size + controllen_size + annex_size + annexlen_size + # sigops ratio test + return witsize + 50 >= 50 * sigops + # Make sure n is high enough that with empty dummy, the script is not valid + n = 0 + while predict_sigops_ratio(n, 0): + n += 1 + # But allow picking a bit higher still + n += random.randrange(5) + # Now pick dummy size *just* large enough that the overall construction passes + dummylen = 0 + while not predict_sigops_ratio(n, dummylen): + dummylen += 1 + scripts = [("s", fn(n, pubkey)[0])] + for _ in range(merkledepth): + scripts = [scripts, random.choice(PARTNER_MERKLE_FN)] + tap = taproot_construct(pubs[0], scripts) + standard = annex is None and dummylen <= 80 and len(pubkey) == 32 + add_spender(spenders, "tapscript/sigopsratio_%i" % fn_num, tap=tap, leaf="s", annex=annex, hashtype=hashtype, key=secs[1], inputs=[getter("sign"), random_bytes(dummylen)], standard=standard, failure={"inputs": [getter("sign"), random_bytes(dummylen - 1)]}, **ERR_SIGOPS_RATIO) + + # Future leaf versions + for leafver in range(0, 0x100, 2): + if leafver == LEAF_VERSION_TAPSCRIPT or leafver == ANNEX_TAG: + # Skip the defined LEAF_VERSION_TAPSCRIPT, and the ANNEX_TAG which is not usable as leaf version + continue + scripts = [ + ("bare_c0", CScript([OP_NOP])), + ("bare_unkver", CScript([OP_NOP]), leafver), + ("return_c0", CScript([OP_RETURN])), + ("return_unkver", CScript([OP_RETURN]), leafver), + ("undecodable_c0", CScript([OP_PUSHDATA1])), + ("undecodable_unkver", CScript([OP_PUSHDATA1]), leafver), + ("bigpush_c0", CScript([random_bytes(MAX_SCRIPT_ELEMENT_SIZE+1), OP_DROP])), + ("bigpush_unkver", CScript([random_bytes(MAX_SCRIPT_ELEMENT_SIZE+1), OP_DROP]), leafver), + ("1001push_c0", CScript([OP_0] * 1001)), + ("1001push_unkver", CScript([OP_0] * 1001), leafver), + ] + random.shuffle(scripts) + tap = taproot_construct(pubs[0], scripts) + add_spender(spenders, "unkver/bare", standard=False, tap=tap, leaf="bare_unkver", failure={"leaf": "bare_c0"}, **ERR_CLEANSTACK) + add_spender(spenders, "unkver/return", standard=False, tap=tap, leaf="return_unkver", failure={"leaf": "return_c0"}, **ERR_OP_RETURN) + add_spender(spenders, "unkver/undecodable", standard=False, tap=tap, leaf="undecodable_unkver", failure={"leaf": "undecodable_c0"}, **ERR_UNDECODABLE) + add_spender(spenders, "unkver/bigpush", standard=False, tap=tap, leaf="bigpush_unkver", failure={"leaf": "bigpush_c0"}, **ERR_PUSH_LIMIT) + add_spender(spenders, "unkver/1001push", standard=False, tap=tap, leaf="1001push_unkver", failure={"leaf": "1001push_c0"}, **ERR_STACK_SIZE) + add_spender(spenders, "unkver/1001inputs", standard=False, tap=tap, leaf="bare_unkver", inputs=[b'']*1001, failure={"leaf": "bare_c0"}, **ERR_STACK_SIZE) + + # OP_SUCCESSx tests. + hashtype = lambda _: random.choice(VALID_SIGHASHES_TAPROOT) + for opval in range(76, 0x100): + opcode = CScriptOp(opval) + if not is_op_success(opcode): + continue + scripts = [ + ("bare_success", CScript([opcode])), + ("bare_nop", CScript([OP_NOP])), + ("unexecif_success", CScript([OP_0, OP_IF, opcode, OP_ENDIF])), + ("unexecif_nop", CScript([OP_0, OP_IF, OP_NOP, OP_ENDIF])), + ("return_success", CScript([OP_RETURN, opcode])), + ("return_nop", CScript([OP_RETURN, OP_NOP])), + ("undecodable_success", CScript([opcode, OP_PUSHDATA1])), + ("undecodable_nop", CScript([OP_NOP, OP_PUSHDATA1])), + ("undecodable_bypassed_success", CScript([OP_PUSHDATA1, OP_2, opcode])), + ("bigpush_success", CScript([random_bytes(MAX_SCRIPT_ELEMENT_SIZE+1), OP_DROP, opcode])), + ("bigpush_nop", CScript([random_bytes(MAX_SCRIPT_ELEMENT_SIZE+1), OP_DROP, OP_NOP])), + ("1001push_success", CScript([OP_0] * 1001 + [opcode])), + ("1001push_nop", CScript([OP_0] * 1001 + [OP_NOP])), + ] + random.shuffle(scripts) + tap = taproot_construct(pubs[0], scripts) + add_spender(spenders, "opsuccess/bare", standard=False, tap=tap, leaf="bare_success", failure={"leaf": "bare_nop"}, **ERR_CLEANSTACK) + add_spender(spenders, "opsuccess/unexecif", standard=False, tap=tap, leaf="unexecif_success", failure={"leaf": "unexecif_nop"}, **ERR_CLEANSTACK) + add_spender(spenders, "opsuccess/return", standard=False, tap=tap, leaf="return_success", failure={"leaf": "return_nop"}, **ERR_OP_RETURN) + add_spender(spenders, "opsuccess/undecodable", standard=False, tap=tap, leaf="undecodable_success", failure={"leaf": "undecodable_nop"}, **ERR_UNDECODABLE) + add_spender(spenders, "opsuccess/undecodable_bypass", standard=False, tap=tap, leaf="undecodable_success", failure={"leaf": "undecodable_bypassed_success"}, **ERR_UNDECODABLE) + add_spender(spenders, "opsuccess/bigpush", standard=False, tap=tap, leaf="bigpush_success", failure={"leaf": "bigpush_nop"}, **ERR_PUSH_LIMIT) + add_spender(spenders, "opsuccess/1001push", standard=False, tap=tap, leaf="1001push_success", failure={"leaf": "1001push_nop"}, **ERR_STACK_SIZE) + add_spender(spenders, "opsuccess/1001inputs", standard=False, tap=tap, leaf="bare_success", inputs=[b'']*1001, failure={"leaf": "bare_nop"}, **ERR_STACK_SIZE) + + # Non-OP_SUCCESSx (verify that those aren't accidentally treated as OP_SUCCESSx) + for opval in range(0, 0x100): + opcode = CScriptOp(opval) + if is_op_success(opcode): + continue + scripts = [ + ("normal", CScript([OP_RETURN, opcode] + [OP_NOP] * 75)), + ("op_success", CScript([OP_RETURN, CScriptOp(0x50)])) + ] + tap = taproot_construct(pubs[0], scripts) + add_spender(spenders, "alwaysvalid/notsuccessx", tap=tap, leaf="op_success", inputs=[], standard=False, failure={"leaf": "normal"}) # err_msg differs based on opcode + + # == Legacy tests == + + # Also add a few legacy spends into the mix, so that transactions which combine taproot and pre-taproot spends get tested too. + for compressed in [False, True]: + eckey1 = ECKey() + eckey1.set(generate_privkey(), compressed) + pubkey1 = eckey1.get_pubkey().get_bytes() + eckey2 = ECKey() + eckey2.set(generate_privkey(), compressed) + for p2sh in [False, True]: + for witv0 in [False, True]: + for hashtype in VALID_SIGHASHES_ECDSA + [random.randrange(0x04, 0x80), random.randrange(0x84, 0x100)]: + standard = (hashtype in VALID_SIGHASHES_ECDSA) and (compressed or not witv0) + add_spender(spenders, "legacy/pk-wrongkey", hashtype=hashtype, p2sh=p2sh, witv0=witv0, standard=standard, script=CScript([pubkey1, OP_CHECKSIG]), **SINGLE_SIG, key=eckey1, failure={"key": eckey2}, sigops_weight=4-3*witv0, **ERR_NO_SUCCESS) + add_spender(spenders, "legacy/pkh-sighashflip", hashtype=hashtype, p2sh=p2sh, witv0=witv0, standard=standard, pkh=pubkey1, key=eckey1, **SIGHASH_BITFLIP, sigops_weight=4-3*witv0, **ERR_NO_SUCCESS) + + # Verify that OP_CHECKSIGADD wasn't accidentally added to pre-taproot validation logic. + for p2sh in [False, True]: + for witv0 in [False, True]: + for hashtype in VALID_SIGHASHES_ECDSA + [random.randrange(0x04, 0x80), random.randrange(0x84, 0x100)]: + standard = hashtype in VALID_SIGHASHES_ECDSA and (p2sh or witv0) + add_spender(spenders, "compat/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) + + return spenders + +def spenders_taproot_inactive(): + """Spenders for testing that pre-activation Taproot rules don't apply.""" + + spenders = [] + + sec = generate_privkey() + pub, _ = compute_xonly_pubkey(sec) + scripts = [ + ("pk", CScript([pub, OP_CHECKSIG])), + ("future_leaf", CScript([pub, OP_CHECKSIG]), 0xc2), + ("op_success", CScript([pub, OP_CHECKSIG, OP_0, OP_IF, CScriptOp(0x50), OP_ENDIF])), + ] + tap = taproot_construct(pub, scripts) + + # Test that keypath spending is valid & standard if compliant, but valid and nonstandard otherwise. + add_spender(spenders, "inactive/keypath_valid", key=sec, tap=tap) + add_spender(spenders, "inactive/keypath_invalidsig", key=sec, tap=tap, standard=False, sighash=bitflipper(default_sighash)) + add_spender(spenders, "inactive/keypath_empty", key=sec, tap=tap, standard=False, witness=[]) + + # Same for scriptpath spending (but using future features like annex, leaf versions, or OP_SUCCESS is nonstandard). + add_spender(spenders, "inactive/scriptpath_valid", key=sec, tap=tap, leaf="pk", inputs=[getter("sign")]) + add_spender(spenders, "inactive/scriptpath_invalidsig", key=sec, tap=tap, leaf="pk", standard=False, inputs=[getter("sign")], sighash=bitflipper(default_sighash)) + add_spender(spenders, "inactive/scriptpath_invalidcb", key=sec, tap=tap, leaf="pk", standard=False, inputs=[getter("sign")], controlblock=bitflipper(default_controlblock)) + add_spender(spenders, "inactive/scriptpath_valid_unkleaf", key=sec, tap=tap, leaf="future_leaf", standard=False, inputs=[getter("sign")]) + add_spender(spenders, "inactive/scriptpath_invalid_unkleaf", key=sec, tap=tap, leaf="future_leaf", standard=False, inputs=[getter("sign")], sighash=bitflipper(default_sighash)) + add_spender(spenders, "inactive/scriptpath_valid_opsuccess", key=sec, tap=tap, leaf="op_success", standard=False, inputs=[getter("sign")]) + add_spender(spenders, "inactive/scriptpath_valid_opsuccess", key=sec, tap=tap, leaf="op_success", standard=False, inputs=[getter("sign")], sighash=bitflipper(default_sighash)) + + return spenders + +# Consensus validation flags to use in dumps for tests with "legacy/" or "inactive/" prefix. +LEGACY_FLAGS = "P2SH,DERSIG,CHECKLOCKTIMEVERIFY,CHECKSEQUENCEVERIFY,WITNESS,NULLDUMMY" +# Consensus validation flags to use in dumps for all other tests. +TAPROOT_FLAGS = "P2SH,DERSIG,CHECKLOCKTIMEVERIFY,CHECKSEQUENCEVERIFY,WITNESS,NULLDUMMY,TAPROOT" + +def dump_json_test(tx, input_utxos, idx, success, failure): + spender = input_utxos[idx].spender + # Determine flags to dump + flags = LEGACY_FLAGS if spender.comment.startswith("legacy/") or spender.comment.startswith("inactive/") else TAPROOT_FLAGS + + fields = [ + ("tx", tx.serialize().hex()), + ("prevouts", [x.output.serialize().hex() for x in input_utxos]), + ("index", idx), + ("flags", flags), + ("comment", spender.comment) + ] + + # The "final" field indicates that a spend should be always valid, even with more validation flags enabled + # than the listed ones. Use standardness as a proxy for this (which gives a conservative underestimate). + if spender.is_standard: + fields.append(("final", True)) + + def dump_witness(wit): + return OrderedDict([("scriptSig", wit[0].hex()), ("witness", [x.hex() for x in wit[1]])]) + if success is not None: + fields.append(("success", dump_witness(success))) + if failure is not None: + fields.append(("failure", dump_witness(failure))) + + # Write the dump to $TEST_DUMP_DIR/x/xyz... where x,y,z,... are the SHA1 sum of the dump (which makes the + # file naming scheme compatible with fuzzing infrastructure). + dump = json.dumps(OrderedDict(fields)) + ",\n" + sha1 = hashlib.sha1(dump.encode("utf-8")).hexdigest() + dirname = os.environ.get("TEST_DUMP_DIR", ".") + ("/%s" % sha1[0]) + os.makedirs(dirname, exist_ok=True) + with open(dirname + ("/%s" % sha1), 'w', encoding="utf8") as f: + f.write(dump) + +# Data type to keep track of UTXOs, where they were created, and how to spend them. +UTXOData = namedtuple('UTXOData', 'outpoint,output,spender') + +class TaprootTest(BitcoinTestFramework): + def add_options(self, parser): + parser.add_argument("--dumptests", dest="dump_tests", default=False, action="store_true", + help="Dump generated test cases to directory set by TEST_DUMP_DIR environment variable") + + def skip_test_if_missing_module(self): + self.skip_if_no_wallet() + + def set_test_params(self): + self.num_nodes = 2 + self.setup_clean_chain = True + # Node 0 has Taproot inactive, Node 1 active. + self.extra_args = [["-whitelist=127.0.0.1", "-par=1", "-vbparams=taproot:1:1"], ["-whitelist=127.0.0.1", "-par=1"]] + + def block_submit(self, node, txs, msg, err_msg, cb_pubkey=None, fees=0, sigops_weight=0, witness=False, accept=False): + + # Deplete block of any non-tapscript sigops using a single additional 0-value coinbase output. + # It is not impossible to fit enough tapscript sigops to hit the old 80k limit without + # busting txin-level limits. We simply have to account for the p2pk outputs in all + # transactions. + extra_output_script = CScript([OP_CHECKSIG]*((MAX_BLOCK_SIGOPS_WEIGHT - sigops_weight) // WITNESS_SCALE_FACTOR)) + + block = create_block(self.tip, create_coinbase(self.lastblockheight + 1, pubkey=cb_pubkey, extra_output_script=extra_output_script, fees=fees), self.lastblocktime + 1) + block.nVersion = 4 + for tx in txs: + tx.rehash() + block.vtx.append(tx) + block.hashMerkleRoot = block.calc_merkle_root() + witness and add_witness_commitment(block) + block.rehash() + block.solve() + block_response = node.submitblock(block.serialize(True).hex()) + if err_msg is not None: + assert block_response is not None and err_msg in block_response, "Missing error message '%s' from block response '%s': %s" % (err_msg, "(None)" if block_response is None else block_response, msg) + if (accept): + assert node.getbestblockhash() == block.hash, "Failed to accept: %s (response: %s)" % (msg, block_response) + self.tip = block.sha256 + self.lastblockhash = block.hash + self.lastblocktime += 1 + self.lastblockheight += 1 + else: + assert node.getbestblockhash() == self.lastblockhash, "Failed to reject: " + msg + + def test_spenders(self, node, spenders, input_counts): + """Run randomized tests with a number of "spenders". + + Steps: + 1) Generate an appropriate UTXO for each spender to test spend conditions + 2) Generate 100 random addresses of all wallet types: pkh/sh_wpkh/wpkh + 3) Select random number of inputs from (1) + 4) Select random number of addresses from (2) as outputs + + Each spender embodies a test; in a large randomized test, it is verified + that toggling the valid argument to each lambda toggles the validity of + the transaction. This is accomplished by constructing transactions consisting + of all valid inputs, except one invalid one. + """ + + # Construct a bunch of sPKs that send coins back to the host wallet + self.log.info("- Constructing addresses for returning coins") + host_spks = [] + host_pubkeys = [] + for i in range(16): + addr = node.getnewaddress(address_type=random.choice(["legacy", "p2sh-segwit", "bech32"])) + info = node.getaddressinfo(addr) + spk = bytes.fromhex(info['scriptPubKey']) + host_spks.append(spk) + host_pubkeys.append(bytes.fromhex(info['pubkey'])) + + # Initialize variables used by block_submit(). + self.lastblockhash = node.getbestblockhash() + self.tip = int(self.lastblockhash, 16) + block = node.getblock(self.lastblockhash) + self.lastblockheight = block['height'] + self.lastblocktime = block['time'] + + # Create transactions spending up to 50 of the wallet's inputs, with one output for each spender, and + # one change output at the end. The transaction is constructed on the Python side to enable + # having multiple outputs to the same address and outputs with no assigned address. The wallet + # is then asked to sign it through signrawtransactionwithwallet, and then added to a block on the + # Python side (to bypass standardness rules). + self.log.info("- Creating test UTXOs...") + random.shuffle(spenders) + normal_utxos = [] + mismatching_utxos = [] # UTXOs with input that requires mismatching output position + done = 0 + while done < len(spenders): + # Compute how many UTXOs to create with this transaction + count_this_tx = min(len(spenders) - done, (len(spenders) + 4) // 5, 10000) + + fund_tx = CTransaction() + # Add the 50 highest-value inputs + unspents = node.listunspent() + random.shuffle(unspents) + unspents.sort(key=lambda x: int(x["amount"] * 100000000), reverse=True) + if len(unspents) > 50: + unspents = unspents[:50] + random.shuffle(unspents) + balance = 0 + for unspent in unspents: + balance += int(unspent["amount"] * 100000000) + txid = int(unspent["txid"], 16) + fund_tx.vin.append(CTxIn(COutPoint(txid, int(unspent["vout"])), CScript())) + # Add outputs + cur_progress = done / len(spenders) + next_progress = (done + count_this_tx) / len(spenders) + change_goal = (1.0 - 0.6 * next_progress) / (1.0 - 0.6 * cur_progress) * balance + self.log.debug("Create %i UTXOs in a transaction spending %i inputs worth %.8f (sending ~%.8f to change)" % (count_this_tx, len(unspents), balance * 0.00000001, change_goal * 0.00000001)) + for i in range(count_this_tx): + avg = (balance - change_goal) / (count_this_tx - i) + amount = int(random.randrange(int(avg*0.85 + 0.5), int(avg*1.15 + 0.5)) + 0.5) + balance -= amount + fund_tx.vout.append(CTxOut(amount, spenders[done + i].script)) + # Add change + fund_tx.vout.append(CTxOut(balance - 10000, random.choice(host_spks))) + # Ask the wallet to sign + ss = BytesIO(bytes.fromhex(node.signrawtransactionwithwallet(ToHex(fund_tx))["hex"])) + fund_tx.deserialize(ss) + # Construct UTXOData entries + fund_tx.rehash() + for i in range(count_this_tx): + utxodata = UTXOData(outpoint=COutPoint(fund_tx.sha256, i), output=fund_tx.vout[i], spender=spenders[done]) + if utxodata.spender.need_vin_vout_mismatch: + mismatching_utxos.append(utxodata) + else: + normal_utxos.append(utxodata) + done += 1 + # Mine into a block + self.block_submit(node, [fund_tx], "Funding tx", None, random.choice(host_pubkeys), 10000, MAX_BLOCK_SIGOPS_WEIGHT, True, True) + + # Consume groups of choice(input_coins) from utxos in a tx, testing the spenders. + self.log.info("- Running %i spending tests" % done) + random.shuffle(normal_utxos) + random.shuffle(mismatching_utxos) + assert done == len(normal_utxos) + len(mismatching_utxos) + + left = done + while left: + # Construct CTransaction with random nVersion, nLocktime + tx = CTransaction() + tx.nVersion = random.choice([1, 2, random.randint(-0x80000000, 0x7fffffff)]) + min_sequence = (tx.nVersion != 1 and tx.nVersion != 0) * 0x80000000 # The minimum sequence number to disable relative locktime + if random.choice([True, False]): + tx.nLockTime = random.randrange(LOCKTIME_THRESHOLD, self.lastblocktime - 7200) # all absolute locktimes in the past + else: + tx.nLockTime = random.randrange(self.lastblockheight + 1) # all block heights in the past + + # Decide how many UTXOs to test with. + acceptable = [n for n in input_counts if n <= left and (left - n > max(input_counts) or (left - n) in [0] + input_counts)] + num_inputs = random.choice(acceptable) + + # If we have UTXOs that require mismatching inputs/outputs left, include exactly one of those + # unless there is only one normal UTXO left (as tests with mismatching UTXOs require at least one + # normal UTXO to go in the first position), and we don't want to run out of normal UTXOs. + input_utxos = [] + while len(mismatching_utxos) and (len(input_utxos) == 0 or len(normal_utxos) == 1): + input_utxos.append(mismatching_utxos.pop()) + left -= 1 + + # Top up until we hit num_inputs (but include at least one normal UTXO always). + for _ in range(max(1, num_inputs - len(input_utxos))): + input_utxos.append(normal_utxos.pop()) + left -= 1 + + # The first input cannot require a mismatching output (as there is at least one output). + while True: + random.shuffle(input_utxos) + if not input_utxos[0].spender.need_vin_vout_mismatch: + break + first_mismatch_input = None + for i in range(len(input_utxos)): + if input_utxos[i].spender.need_vin_vout_mismatch: + first_mismatch_input = i + assert first_mismatch_input is None or first_mismatch_input > 0 + + # Decide fee, and add CTxIns to tx. + amount = sum(utxo.output.nValue for utxo in input_utxos) + fee = min(random.randrange(MIN_FEE * 2, MIN_FEE * 4), amount - DUST_LIMIT) # 10000-20000 sat fee + in_value = amount - fee + tx.vin = [CTxIn(outpoint=utxo.outpoint, nSequence=random.randint(min_sequence, 0xffffffff)) for utxo in input_utxos] + tx.wit.vtxinwit = [CTxInWitness() for _ in range(len(input_utxos))] + sigops_weight = sum(utxo.spender.sigops_weight for utxo in input_utxos) + self.log.debug("Test: %s" % (", ".join(utxo.spender.comment for utxo in input_utxos))) + + # Add 1 to 4 random outputs (but constrained by inputs that require mismatching outputs) + num_outputs = random.choice(range(1, 1 + min(4, 4 if first_mismatch_input is None else first_mismatch_input))) + assert in_value >= 0 and fee - num_outputs * DUST_LIMIT >= MIN_FEE + for i in range(num_outputs): + tx.vout.append(CTxOut()) + if in_value <= DUST_LIMIT: + tx.vout[-1].nValue = DUST_LIMIT + elif i < num_outputs - 1: + tx.vout[-1].nValue = in_value + else: + tx.vout[-1].nValue = random.randint(DUST_LIMIT, in_value) + in_value -= tx.vout[-1].nValue + tx.vout[-1].scriptPubKey = random.choice(host_spks) + sigops_weight += CScript(tx.vout[-1].scriptPubKey).GetSigOpCount(False) * WITNESS_SCALE_FACTOR + fee += in_value + assert fee >= 0 + + # Select coinbase pubkey + cb_pubkey = random.choice(host_pubkeys) + sigops_weight += 1 * WITNESS_SCALE_FACTOR + + # Precompute one satisfying and one failing scriptSig/witness for each input. + input_data = [] + for i in range(len(input_utxos)): + fn = input_utxos[i].spender.sat_function + fail = None + success = fn(tx, i, [utxo.output for utxo in input_utxos], True) + if not input_utxos[i].spender.no_fail: + fail = fn(tx, i, [utxo.output for utxo in input_utxos], False) + input_data.append((fail, success)) + if self.options.dump_tests: + dump_json_test(tx, input_utxos, i, success, fail) + + # Sign each input incorrectly once on each complete signing pass, except the very last. + for fail_input in list(range(len(input_utxos))) + [None]: + # Skip trying to fail at spending something that can't be made to fail. + if fail_input is not None and input_utxos[fail_input].spender.no_fail: + continue + # Expected message with each input failure, may be None(which is ignored) + expected_fail_msg = None if fail_input is None else input_utxos[fail_input].spender.err_msg + # Fill inputs/witnesses + for i in range(len(input_utxos)): + tx.vin[i].scriptSig = input_data[i][i != fail_input][0] + tx.wit.vtxinwit[i].scriptWitness.stack = input_data[i][i != fail_input][1] + # Submit to mempool to check standardness + is_standard_tx = fail_input is None and all(utxo.spender.is_standard for utxo in input_utxos) and tx.nVersion >= 1 and tx.nVersion <= 2 + tx.rehash() + msg = ','.join(utxo.spender.comment + ("*" if n == fail_input else "") for n, utxo in enumerate(input_utxos)) + if is_standard_tx: + node.sendrawtransaction(tx.serialize().hex(), 0) + assert node.getmempoolentry(tx.hash) is not None, "Failed to accept into mempool: " + msg + else: + assert_raises_rpc_error(-26, None, node.sendrawtransaction, tx.serialize().hex(), 0) + # Submit in a block + self.block_submit(node, [tx], msg, witness=True, accept=fail_input is None, cb_pubkey=cb_pubkey, fees=fee, sigops_weight=sigops_weight, err_msg=expected_fail_msg) + + if (len(spenders) - left) // 200 > (len(spenders) - left - len(input_utxos)) // 200: + self.log.info(" - %i tests done" % (len(spenders) - left)) + + assert left == 0 + assert len(normal_utxos) == 0 + assert len(mismatching_utxos) == 0 + self.log.info(" - Done") + + def run_test(self): + self.connect_nodes(0, 1) + + # Post-taproot activation tests go first (pre-taproot tests' blocks are invalid post-taproot). + self.log.info("Post-activation tests...") + self.nodes[1].generate(101) + self.test_spenders(self.nodes[1], spenders_taproot_active(), input_counts=[1, 2, 2, 2, 2, 3]) + + # Transfer % of funds to pre-taproot node. + addr = self.nodes[0].getnewaddress() + self.nodes[1].sendtoaddress(address=addr, amount=int(self.nodes[1].getbalance() * 70000000) / 100000000) + self.nodes[1].generate(1) + self.sync_blocks() + + # Pre-taproot activation tests. + self.log.info("Pre-activation tests...") + self.test_spenders(self.nodes[0], spenders_taproot_inactive(), input_counts=[1, 2, 2, 2, 2, 3]) + + +if __name__ == '__main__': + TaprootTest().main() diff --git a/test/functional/p2p_segwit.py b/test/functional/p2p_segwit.py index d79ed449e5..29735b0fb3 100755 --- a/test/functional/p2p_segwit.py +++ b/test/functional/p2p_segwit.py @@ -55,6 +55,7 @@ from test_framework.script import ( MAX_SCRIPT_ELEMENT_SIZE, OP_0, OP_1, + OP_2, OP_16, OP_2DROP, OP_CHECKMULTISIG, @@ -1400,7 +1401,11 @@ class SegWitTest(BitcoinTestFramework): assert_equal(len(self.nodes[1].getrawmempool()), 0) for version in list(range(OP_1, OP_16 + 1)) + [OP_0]: # First try to spend to a future version segwit script_pubkey. - script_pubkey = CScript([CScriptOp(version), witness_hash]) + if version == OP_1: + # Don't use 32-byte v1 witness (used by Taproot; see BIP 341) + script_pubkey = CScript([CScriptOp(version), witness_hash + b'\x00']) + else: + script_pubkey = CScript([CScriptOp(version), witness_hash]) tx.vin = [CTxIn(COutPoint(self.utxo[0].sha256, self.utxo[0].n), b"")] tx.vout = [CTxOut(self.utxo[0].nValue - 1000, script_pubkey)] tx.rehash() @@ -1413,9 +1418,9 @@ class SegWitTest(BitcoinTestFramework): self.sync_blocks() assert len(self.nodes[0].getrawmempool()) == 0 - # Finally, verify that version 0 -> version 1 transactions + # Finally, verify that version 0 -> version 2 transactions # are standard - script_pubkey = CScript([CScriptOp(OP_1), witness_hash]) + script_pubkey = CScript([CScriptOp(OP_2), witness_hash]) tx2 = CTransaction() tx2.vin = [CTxIn(COutPoint(tx.sha256, 0), b"")] tx2.vout = [CTxOut(tx.vout[0].nValue - 1000, script_pubkey)] diff --git a/test/functional/rpc_blockchain.py b/test/functional/rpc_blockchain.py index 35cea85c07..f965677408 100755 --- a/test/functional/rpc_blockchain.py +++ b/test/functional/rpc_blockchain.py @@ -146,7 +146,19 @@ class BlockchainTest(BitcoinTestFramework): 'possible': True, }, }, - 'active': False} + 'active': False + }, + 'taproot': { + 'type': 'bip9', + 'bip9': { + 'status': 'active', + 'start_time': -1, + 'timeout': 9223372036854775807, + 'since': 0 + }, + 'height': 0, + 'active': True + } }) def _test_getchaintxstats(self): diff --git a/test/functional/test_framework/bip340_test_vectors.csv b/test/functional/test_framework/bip340_test_vectors.csv new file mode 100644 index 0000000000..e068322deb --- /dev/null +++ b/test/functional/test_framework/bip340_test_vectors.csv @@ -0,0 +1,16 @@ +index,secret key,public key,aux_rand,message,signature,verification result,comment +0,0000000000000000000000000000000000000000000000000000000000000003,F9308A019258C31049344F85F89D5229B531C845836F99B08601F113BCE036F9,0000000000000000000000000000000000000000000000000000000000000000,0000000000000000000000000000000000000000000000000000000000000000,E907831F80848D1069A5371B402410364BDF1C5F8307B0084C55F1CE2DCA821525F66A4A85EA8B71E482A74F382D2CE5EBEEE8FDB2172F477DF4900D310536C0,TRUE, +1,B7E151628AED2A6ABF7158809CF4F3C762E7160F38B4DA56A784D9045190CFEF,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,0000000000000000000000000000000000000000000000000000000000000001,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,6896BD60EEAE296DB48A229FF71DFE071BDE413E6D43F917DC8DCF8C78DE33418906D11AC976ABCCB20B091292BFF4EA897EFCB639EA871CFA95F6DE339E4B0A,TRUE, +2,C90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B14E5C9,DD308AFEC5777E13121FA72B9CC1B7CC0139715309B086C960E18FD969774EB8,C87AA53824B4D7AE2EB035A2B5BBBCCC080E76CDC6D1692C4B0B62D798E6D906,7E2D58D8B3BCDF1ABADEC7829054F90DDA9805AAB56C77333024B9D0A508B75C,5831AAEED7B44BB74E5EAB94BA9D4294C49BCF2A60728D8B4C200F50DD313C1BAB745879A5AD954A72C45A91C3A51D3C7ADEA98D82F8481E0E1E03674A6F3FB7,TRUE, +3,0B432B2677937381AEF05BB02A66ECD012773062CF3FA2549E44F58ED2401710,25D1DFF95105F5253C4022F628A996AD3A0D95FBF21D468A1B33F8C160D8F517,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF,7EB0509757E246F19449885651611CB965ECC1A187DD51B64FDA1EDC9637D5EC97582B9CB13DB3933705B32BA982AF5AF25FD78881EBB32771FC5922EFC66EA3,TRUE,test fails if msg is reduced modulo p or n +4,,D69C3509BB99E412E68B0FE8544E72837DFA30746D8BE2AA65975F29D22DC7B9,,4DF3C3F68FCC83B27E9D42C90431A72499F17875C81A599B566C9889B9696703,00000000000000000000003B78CE563F89A0ED9414F5AA28AD0D96D6795F9C6376AFB1548AF603B3EB45C9F8207DEE1060CB71C04E80F593060B07D28308D7F4,TRUE, +5,,EEFDEA4CDB677750A420FEE807EACF21EB9898AE79B9768766E4FAA04A2D4A34,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,6CFF5C3BA86C69EA4B7376F31A9BCB4F74C1976089B2D9963DA2E5543E17776969E89B4C5564D00349106B8497785DD7D1D713A8AE82B32FA79D5F7FC407D39B,FALSE,public key not on the curve +6,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,FFF97BD5755EEEA420453A14355235D382F6472F8568A18B2F057A14602975563CC27944640AC607CD107AE10923D9EF7A73C643E166BE5EBEAFA34B1AC553E2,FALSE,has_even_y(R) is false +7,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,1FA62E331EDBC21C394792D2AB1100A7B432B013DF3F6FF4F99FCB33E0E1515F28890B3EDB6E7189B630448B515CE4F8622A954CFE545735AAEA5134FCCDB2BD,FALSE,negated message +8,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,6CFF5C3BA86C69EA4B7376F31A9BCB4F74C1976089B2D9963DA2E5543E177769961764B3AA9B2FFCB6EF947B6887A226E8D7C93E00C5ED0C1834FF0D0C2E6DA6,FALSE,negated s value +9,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,0000000000000000000000000000000000000000000000000000000000000000123DDA8328AF9C23A94C1FEECFD123BA4FB73476F0D594DCB65C6425BD186051,FALSE,sG - eP is infinite. Test fails in single verification if has_even_y(inf) is defined as true and x(inf) as 0 +10,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,00000000000000000000000000000000000000000000000000000000000000017615FBAF5AE28864013C099742DEADB4DBA87F11AC6754F93780D5A1837CF197,FALSE,sG - eP is infinite. Test fails in single verification if has_even_y(inf) is defined as true and x(inf) as 1 +11,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,4A298DACAE57395A15D0795DDBFD1DCB564DA82B0F269BC70A74F8220429BA1D69E89B4C5564D00349106B8497785DD7D1D713A8AE82B32FA79D5F7FC407D39B,FALSE,sig[0:32] is not an X coordinate on the curve +12,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F69E89B4C5564D00349106B8497785DD7D1D713A8AE82B32FA79D5F7FC407D39B,FALSE,sig[0:32] is equal to field size +13,,DFF1D77F2A671C5F36183726DB2341BE58FEAE1DA2DECED843240F7B502BA659,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,6CFF5C3BA86C69EA4B7376F31A9BCB4F74C1976089B2D9963DA2E5543E177769FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141,FALSE,sig[32:64] is equal to curve order +14,,FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC30,,243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C89,6CFF5C3BA86C69EA4B7376F31A9BCB4F74C1976089B2D9963DA2E5543E17776969E89B4C5564D00349106B8497785DD7D1D713A8AE82B32FA79D5F7FC407D39B,FALSE,public key is not a valid X coordinate because it exceeds the field size diff --git a/test/functional/test_framework/blocktools.py b/test/functional/test_framework/blocktools.py index afc1995009..4be8b7d80b 100644 --- a/test/functional/test_framework/blocktools.py +++ b/test/functional/test_framework/blocktools.py @@ -43,7 +43,9 @@ from .script import ( from .util import assert_equal from io import BytesIO +WITNESS_SCALE_FACTOR = 4 MAX_BLOCK_SIGOPS = 20000 +MAX_BLOCK_SIGOPS_WEIGHT = MAX_BLOCK_SIGOPS * WITNESS_SCALE_FACTOR # Genesis block time (regtest) TIME_GENESIS_BLOCK = 1296688602 @@ -101,22 +103,31 @@ def script_BIP34_coinbase_height(height): return CScript([CScriptNum(height)]) -def create_coinbase(height, pubkey=None): - """Create a coinbase transaction, assuming no miner fees. +def create_coinbase(height, pubkey=None, extra_output_script=None, fees=0): + """Create a coinbase transaction. If pubkey is passed in, the coinbase output will be a P2PK output; - otherwise an anyone-can-spend output.""" + otherwise an anyone-can-spend output. + + If extra_output_script is given, make a 0-value output to that + script. This is useful to pad block weight/sigops as needed. """ coinbase = CTransaction() coinbase.vin.append(CTxIn(COutPoint(0, 0xffffffff), script_BIP34_coinbase_height(height), 0xffffffff)) coinbaseoutput = CTxOut() coinbaseoutput.nValue = 50 * COIN halvings = int(height / 150) # regtest coinbaseoutput.nValue >>= halvings - if (pubkey is not None): + coinbaseoutput.nValue += fees + if pubkey is not None: coinbaseoutput.scriptPubKey = CScript([pubkey, OP_CHECKSIG]) else: coinbaseoutput.scriptPubKey = CScript([OP_TRUE]) coinbase.vout = [coinbaseoutput] + if extra_output_script is not None: + coinbaseoutput2 = CTxOut() + coinbaseoutput2.nValue = 0 + coinbaseoutput2.scriptPubKey = extra_output_script + coinbase.vout.append(coinbaseoutput2) coinbase.calc_sha256() return coinbase diff --git a/test/functional/test_framework/key.py b/test/functional/test_framework/key.py index adbffb7dc7..17b869e542 100644 --- a/test/functional/test_framework/key.py +++ b/test/functional/test_framework/key.py @@ -1,4 +1,4 @@ -# Copyright (c) 2019 Pieter Wuille +# Copyright (c) 2019-2020 Pieter Wuille # Distributed under the MIT software license, see the accompanying # file COPYING or http://www.opensource.org/licenses/mit-license.php. """Test-only secp256k1 elliptic curve implementation @@ -6,10 +6,24 @@ WARNING: This code is slow, uses bad randomness, does not properly protect keys, and is trivially vulnerable to side channel attacks. Do not use for anything but tests.""" +import csv +import hashlib +import os import random +import sys +import unittest from .util import modinv +def TaggedHash(tag, data): + ss = hashlib.sha256(tag.encode('utf-8')).digest() + ss += ss + ss += data + return hashlib.sha256(ss).digest() + +def xor_bytes(b0, b1): + return bytes(x ^ y for (x, y) in zip(b0, b1)) + def jacobi_symbol(n, k): """Compute the Jacobi symbol of n modulo k @@ -68,6 +82,10 @@ class EllipticCurve: inv_3 = (inv_2 * inv) % self.p return ((inv_2 * x1) % self.p, (inv_3 * y1) % self.p, 1) + def has_even_y(self, p1): + """Whether the point p1 has an even Y coordinate when expressed in affine coordinates.""" + return not (p1[2] == 0 or self.affine(p1)[1] & 1) + def negate(self, p1): """Negate a Jacobian point tuple p1.""" x1, y1, z1 = p1 @@ -86,13 +104,13 @@ class EllipticCurve: return jacobi_symbol(x_3 + self.a * x + self.b, self.p) != -1 def lift_x(self, x): - """Given an X coordinate on the curve, return a corresponding affine point.""" + """Given an X coordinate on the curve, return a corresponding affine point for which the Y coordinate is even.""" x_3 = pow(x, 3, self.p) v = x_3 + self.a * x + self.b y = modsqrt(v, self.p) if y is None: return None - return (x, y, 1) + return (x, self.p - y if y & 1 else y, 1) def double(self, p1): """Double a Jacobian tuple p1 @@ -197,7 +215,8 @@ class EllipticCurve: r = self.add(r, p) return r -SECP256K1 = EllipticCurve(2**256 - 2**32 - 977, 0, 7) +SECP256K1_FIELD_SIZE = 2**256 - 2**32 - 977 +SECP256K1 = EllipticCurve(SECP256K1_FIELD_SIZE, 0, 7) SECP256K1_G = (0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798, 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8, 1) SECP256K1_ORDER = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141 SECP256K1_ORDER_HALF = SECP256K1_ORDER // 2 @@ -223,7 +242,7 @@ class ECPubKey(): p = SECP256K1.lift_x(x) # if the oddness of the y co-ord isn't correct, find the other # valid y - if (p[1] & 1) != (data[0] & 1): + if data[0] & 1: p = SECP256K1.negate(p) self.p = p self.valid = True @@ -307,6 +326,10 @@ class ECPubKey(): return False return True +def generate_privkey(): + """Generate a valid random 32-byte private key.""" + return random.randrange(1, SECP256K1_ORDER).to_bytes(32, 'big') + class ECKey(): """A secp256k1 private key""" @@ -324,7 +347,7 @@ class ECKey(): def generate(self, compressed=True): """Generate a random private key (compressed or uncompressed).""" - self.set(random.randrange(1, SECP256K1_ORDER).to_bytes(32, 'big'), compressed) + self.set(generate_privkey(), compressed) def get_bytes(self): """Retrieve the 32-byte representation of this key.""" @@ -369,3 +392,161 @@ class ECKey(): rb = r.to_bytes((r.bit_length() + 8) // 8, 'big') sb = s.to_bytes((s.bit_length() + 8) // 8, 'big') return b'\x30' + bytes([4 + len(rb) + len(sb), 2, len(rb)]) + rb + bytes([2, len(sb)]) + sb + +def compute_xonly_pubkey(key): + """Compute an x-only (32 byte) public key from a (32 byte) private key. + + This also returns whether the resulting public key was negated. + """ + + assert len(key) == 32 + x = int.from_bytes(key, 'big') + if x == 0 or x >= SECP256K1_ORDER: + return (None, None) + P = SECP256K1.affine(SECP256K1.mul([(SECP256K1_G, x)])) + return (P[0].to_bytes(32, 'big'), not SECP256K1.has_even_y(P)) + +def tweak_add_privkey(key, tweak): + """Tweak a private key (after negating it if needed).""" + + assert len(key) == 32 + assert len(tweak) == 32 + + x = int.from_bytes(key, 'big') + if x == 0 or x >= SECP256K1_ORDER: + return None + if not SECP256K1.has_even_y(SECP256K1.mul([(SECP256K1_G, x)])): + x = SECP256K1_ORDER - x + t = int.from_bytes(tweak, 'big') + if t >= SECP256K1_ORDER: + return None + x = (x + t) % SECP256K1_ORDER + if x == 0: + return None + return x.to_bytes(32, 'big') + +def tweak_add_pubkey(key, tweak): + """Tweak a public key and return whether the result had to be negated.""" + + assert len(key) == 32 + assert len(tweak) == 32 + + x_coord = int.from_bytes(key, 'big') + if x_coord >= SECP256K1_FIELD_SIZE: + return None + P = SECP256K1.lift_x(x_coord) + if P is None: + return None + t = int.from_bytes(tweak, 'big') + if t >= SECP256K1_ORDER: + return None + Q = SECP256K1.affine(SECP256K1.mul([(SECP256K1_G, t), (P, 1)])) + if Q is None: + return None + return (Q[0].to_bytes(32, 'big'), not SECP256K1.has_even_y(Q)) + +def verify_schnorr(key, sig, msg): + """Verify a Schnorr signature (see BIP 340). + + - key is a 32-byte xonly pubkey (computed using compute_xonly_pubkey). + - sig is a 64-byte Schnorr signature + - msg is a 32-byte message + """ + assert len(key) == 32 + assert len(msg) == 32 + assert len(sig) == 64 + + x_coord = int.from_bytes(key, 'big') + if x_coord == 0 or x_coord >= SECP256K1_FIELD_SIZE: + return False + P = SECP256K1.lift_x(x_coord) + if P is None: + return False + r = int.from_bytes(sig[0:32], 'big') + if r >= SECP256K1_FIELD_SIZE: + return False + s = int.from_bytes(sig[32:64], 'big') + if s >= SECP256K1_ORDER: + return False + e = int.from_bytes(TaggedHash("BIP0340/challenge", sig[0:32] + key + msg), 'big') % SECP256K1_ORDER + R = SECP256K1.mul([(SECP256K1_G, s), (P, SECP256K1_ORDER - e)]) + if not SECP256K1.has_even_y(R): + return False + if ((r * R[2] * R[2]) % SECP256K1_FIELD_SIZE) != R[0]: + return False + return True + +def sign_schnorr(key, msg, aux=None, flip_p=False, flip_r=False): + """Create a Schnorr signature (see BIP 340).""" + + if aux is None: + aux = bytes(32) + + assert len(key) == 32 + assert len(msg) == 32 + assert len(aux) == 32 + + sec = int.from_bytes(key, 'big') + if sec == 0 or sec >= SECP256K1_ORDER: + return None + P = SECP256K1.affine(SECP256K1.mul([(SECP256K1_G, sec)])) + if SECP256K1.has_even_y(P) == flip_p: + sec = SECP256K1_ORDER - sec + t = (sec ^ int.from_bytes(TaggedHash("BIP0340/aux", aux), 'big')).to_bytes(32, 'big') + kp = int.from_bytes(TaggedHash("BIP0340/nonce", t + P[0].to_bytes(32, 'big') + msg), 'big') % SECP256K1_ORDER + assert kp != 0 + R = SECP256K1.affine(SECP256K1.mul([(SECP256K1_G, kp)])) + k = kp if SECP256K1.has_even_y(R) != flip_r else SECP256K1_ORDER - kp + e = int.from_bytes(TaggedHash("BIP0340/challenge", R[0].to_bytes(32, 'big') + P[0].to_bytes(32, 'big') + msg), 'big') % SECP256K1_ORDER + return R[0].to_bytes(32, 'big') + ((k + e * sec) % SECP256K1_ORDER).to_bytes(32, 'big') + +class TestFrameworkKey(unittest.TestCase): + def test_schnorr(self): + """Test the Python Schnorr implementation.""" + byte_arrays = [generate_privkey() for _ in range(3)] + [v.to_bytes(32, 'big') for v in [0, SECP256K1_ORDER - 1, SECP256K1_ORDER, 2**256 - 1]] + keys = {} + for privkey in byte_arrays: # build array of key/pubkey pairs + pubkey, _ = compute_xonly_pubkey(privkey) + if pubkey is not None: + keys[privkey] = pubkey + for msg in byte_arrays: # test every combination of message, signing key, verification key + for sign_privkey, sign_pubkey in keys.items(): + sig = sign_schnorr(sign_privkey, msg) + for verify_privkey, verify_pubkey in keys.items(): + if verify_privkey == sign_privkey: + self.assertTrue(verify_schnorr(verify_pubkey, sig, msg)) + sig = list(sig) + sig[random.randrange(64)] ^= (1 << (random.randrange(8))) # damaging signature should break things + sig = bytes(sig) + self.assertFalse(verify_schnorr(verify_pubkey, sig, msg)) + + def test_schnorr_testvectors(self): + """Implement the BIP340 test vectors (read from bip340_test_vectors.csv).""" + num_tests = 0 + with open(os.path.join(sys.path[0], 'test_framework', 'bip340_test_vectors.csv'), newline='', encoding='utf8') as csvfile: + reader = csv.reader(csvfile) + next(reader) + for row in reader: + (i_str, seckey_hex, pubkey_hex, aux_rand_hex, msg_hex, sig_hex, result_str, comment) = row + i = int(i_str) + pubkey = bytes.fromhex(pubkey_hex) + msg = bytes.fromhex(msg_hex) + sig = bytes.fromhex(sig_hex) + result = result_str == 'TRUE' + if seckey_hex != '': + seckey = bytes.fromhex(seckey_hex) + pubkey_actual = compute_xonly_pubkey(seckey)[0] + self.assertEqual(pubkey.hex(), pubkey_actual.hex(), "BIP340 test vector %i (%s): pubkey mismatch" % (i, comment)) + aux_rand = bytes.fromhex(aux_rand_hex) + try: + sig_actual = sign_schnorr(seckey, msg, aux_rand) + self.assertEqual(sig.hex(), sig_actual.hex(), "BIP340 test vector %i (%s): sig mismatch" % (i, comment)) + except RuntimeError as e: + self.assertFalse("BIP340 test vector %i (%s): signing raised exception %s" % (i, comment, e)) + result_actual = verify_schnorr(pubkey, sig, msg) + if result: + self.assertEqual(result, result_actual, "BIP340 test vector %i (%s): verification failed" % (i, comment)) + else: + self.assertEqual(result, result_actual, "BIP340 test vector %i (%s): verification succeeded unexpectedly" % (i, comment)) + num_tests += 1 + self.assertTrue(num_tests >= 15) # expect at least 15 test vectors diff --git a/test/functional/test_framework/script.py b/test/functional/test_framework/script.py index 5e35ba0fce..8e5848d493 100644 --- a/test/functional/test_framework/script.py +++ b/test/functional/test_framework/script.py @@ -6,11 +6,15 @@ This file is modified from python-bitcoinlib. """ + +from collections import namedtuple import hashlib import struct import unittest from typing import List, Dict +from .key import TaggedHash, tweak_add_pubkey + from .messages import ( CTransaction, CTxOut, @@ -22,8 +26,13 @@ from .messages import ( ) MAX_SCRIPT_ELEMENT_SIZE = 520 +LOCKTIME_THRESHOLD = 500000000 +ANNEX_TAG = 0x50 + OPCODE_NAMES = {} # type: Dict[CScriptOp, str] +LEAF_VERSION_TAPSCRIPT = 0xc0 + def hash160(s): return hashlib.new('ripemd160', sha256(s)).digest() @@ -239,11 +248,8 @@ OP_NOP8 = CScriptOp(0xb7) OP_NOP9 = CScriptOp(0xb8) OP_NOP10 = CScriptOp(0xb9) -# template matching params -OP_SMALLINTEGER = CScriptOp(0xfa) -OP_PUBKEYS = CScriptOp(0xfb) -OP_PUBKEYHASH = CScriptOp(0xfd) -OP_PUBKEY = CScriptOp(0xfe) +# BIP 342 opcodes (Tapscript) +OP_CHECKSIGADD = CScriptOp(0xba) OP_INVALIDOPCODE = CScriptOp(0xff) @@ -359,10 +365,7 @@ OPCODE_NAMES.update({ OP_NOP8: 'OP_NOP8', OP_NOP9: 'OP_NOP9', OP_NOP10: 'OP_NOP10', - OP_SMALLINTEGER: 'OP_SMALLINTEGER', - OP_PUBKEYS: 'OP_PUBKEYS', - OP_PUBKEYHASH: 'OP_PUBKEYHASH', - OP_PUBKEY: 'OP_PUBKEY', + OP_CHECKSIGADD: 'OP_CHECKSIGADD', OP_INVALIDOPCODE: 'OP_INVALIDOPCODE', }) @@ -593,6 +596,7 @@ class CScript(bytes): return n +SIGHASH_DEFAULT = 0 # Taproot-only default, semantics same as SIGHASH_ALL SIGHASH_ALL = 1 SIGHASH_NONE = 2 SIGHASH_SINGLE = 3 @@ -615,7 +619,6 @@ def FindAndDelete(script, sig): r += script[last_sop_idx:] return CScript(r) - def LegacySignatureHash(script, txTo, inIdx, hashtype): """Consensus-correct SignatureHash @@ -738,3 +741,113 @@ class TestFrameworkScript(unittest.TestCase): values = [0, 1, -1, -2, 127, 128, -255, 256, (1 << 15) - 1, -(1 << 16), (1 << 24) - 1, (1 << 31), 1 - (1 << 32), 1 << 40, 1500, -1500] for value in values: self.assertEqual(CScriptNum.decode(CScriptNum.encode(CScriptNum(value))), value) + +def TaprootSignatureHash(txTo, spent_utxos, hash_type, input_index = 0, scriptpath = False, script = CScript(), codeseparator_pos = -1, annex = None, leaf_ver = LEAF_VERSION_TAPSCRIPT): + assert (len(txTo.vin) == len(spent_utxos)) + assert (input_index < len(txTo.vin)) + out_type = SIGHASH_ALL if hash_type == 0 else hash_type & 3 + in_type = hash_type & SIGHASH_ANYONECANPAY + spk = spent_utxos[input_index].scriptPubKey + ss = bytes([0, hash_type]) # epoch, hash_type + ss += struct.pack("<i", txTo.nVersion) + ss += struct.pack("<I", txTo.nLockTime) + if in_type != SIGHASH_ANYONECANPAY: + ss += sha256(b"".join(i.prevout.serialize() for i in txTo.vin)) + ss += sha256(b"".join(struct.pack("<q", u.nValue) for u in spent_utxos)) + ss += sha256(b"".join(ser_string(u.scriptPubKey) for u in spent_utxos)) + ss += sha256(b"".join(struct.pack("<I", i.nSequence) for i in txTo.vin)) + if out_type == SIGHASH_ALL: + ss += sha256(b"".join(o.serialize() for o in txTo.vout)) + spend_type = 0 + if annex is not None: + spend_type |= 1 + if (scriptpath): + spend_type |= 2 + ss += bytes([spend_type]) + if in_type == SIGHASH_ANYONECANPAY: + ss += txTo.vin[input_index].prevout.serialize() + ss += struct.pack("<q", spent_utxos[input_index].nValue) + ss += ser_string(spk) + ss += struct.pack("<I", txTo.vin[input_index].nSequence) + else: + ss += struct.pack("<I", input_index) + if (spend_type & 1): + ss += sha256(ser_string(annex)) + if out_type == SIGHASH_SINGLE: + if input_index < len(txTo.vout): + ss += sha256(txTo.vout[input_index].serialize()) + else: + ss += bytes(0 for _ in range(32)) + if (scriptpath): + ss += TaggedHash("TapLeaf", bytes([leaf_ver]) + ser_string(script)) + ss += bytes([0]) + ss += struct.pack("<i", codeseparator_pos) + assert len(ss) == 175 - (in_type == SIGHASH_ANYONECANPAY) * 49 - (out_type != SIGHASH_ALL and out_type != SIGHASH_SINGLE) * 32 + (annex is not None) * 32 + scriptpath * 37 + return TaggedHash("TapSighash", ss) + +def taproot_tree_helper(scripts): + if len(scripts) == 0: + return ([], bytes(0 for _ in range(32))) + if len(scripts) == 1: + # One entry: treat as a leaf + script = scripts[0] + assert(not callable(script)) + if isinstance(script, list): + return taproot_tree_helper(script) + assert(isinstance(script, tuple)) + version = LEAF_VERSION_TAPSCRIPT + name = script[0] + code = script[1] + if len(script) == 3: + version = script[2] + assert version & 1 == 0 + assert isinstance(code, bytes) + h = TaggedHash("TapLeaf", bytes([version]) + ser_string(code)) + if name is None: + return ([], h) + return ([(name, version, code, bytes())], h) + elif len(scripts) == 2 and callable(scripts[1]): + # Two entries, and the right one is a function + left, left_h = taproot_tree_helper(scripts[0:1]) + right_h = scripts[1](left_h) + left = [(name, version, script, control + right_h) for name, version, script, control in left] + right = [] + else: + # Two or more entries: descend into each side + split_pos = len(scripts) // 2 + left, left_h = taproot_tree_helper(scripts[0:split_pos]) + right, right_h = taproot_tree_helper(scripts[split_pos:]) + left = [(name, version, script, control + right_h) for name, version, script, control in left] + right = [(name, version, script, control + left_h) for name, version, script, control in right] + if right_h < left_h: + right_h, left_h = left_h, right_h + h = TaggedHash("TapBranch", left_h + right_h) + return (left + right, h) + +TaprootInfo = namedtuple("TaprootInfo", "scriptPubKey,inner_pubkey,negflag,tweak,leaves") +TaprootLeafInfo = namedtuple("TaprootLeafInfo", "script,version,merklebranch") + +def taproot_construct(pubkey, scripts=None): + """Construct a tree of Taproot spending conditions + + pubkey: an ECPubKey object for the internal pubkey + scripts: a list of items; each item is either: + - a (name, CScript) tuple + - a (name, CScript, leaf version) tuple + - another list of items (with the same structure) + - a function, which specifies how to compute the hashing partner + in function of the hash of whatever it is combined with + + Returns: script (sPK or redeemScript), tweak, {name:(script, leaf version, negation flag, innerkey, merklepath), ...} + """ + if scripts is None: + scripts = [] + + ret, h = taproot_tree_helper(scripts) + tweak = TaggedHash("TapTweak", pubkey + h) + tweaked, negated = tweak_add_pubkey(pubkey, tweak) + leaves = dict((name, TaprootLeafInfo(script, version, merklebranch)) for name, version, script, merklebranch in ret) + return TaprootInfo(CScript([OP_1, tweaked]), pubkey, negated + 0, tweak, leaves) + +def is_op_success(o): + return o == 0x50 or o == 0x62 or o == 0x89 or o == 0x8a or o == 0x8d or o == 0x8e or (o >= 0x7e and o <= 0x81) or (o >= 0x83 and o <= 0x86) or (o >= 0x95 and o <= 0x99) or (o >= 0xbb and o <= 0xfe) diff --git a/test/functional/test_runner.py b/test/functional/test_runner.py index 6b746b1fee..8cd82649b6 100755 --- a/test/functional/test_runner.py +++ b/test/functional/test_runner.py @@ -70,6 +70,7 @@ TEST_FRAMEWORK_MODULES = [ "address", "blocktools", "muhash", + "key", "script", "segwit_addr", "util", @@ -107,6 +108,7 @@ BASE_SCRIPTS = [ 'mempool_updatefromblock.py', 'wallet_dump.py', 'wallet_listtransactions.py', + 'feature_taproot.py', # vv Tests less than 60s vv 'p2p_sendheaders.py', 'wallet_importmulti.py', |