aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorfanquake <fanquake@gmail.com>2023-08-17 11:30:16 +0100
committerfanquake <fanquake@gmail.com>2023-08-17 12:54:16 +0100
commit7ef2d4ee4d09196d6fdf9a55dc9ebfd05d62d160 (patch)
tree43e059ca463ebca13c19646cd7e6e67301988b3b
parentd78ff380a2cde80c264e36e046b1cfc054bd9253 (diff)
parent91d924ede1b421df31c895f4f43359e453a09ca5 (diff)
Merge bitcoin/bitcoin#28244: Break up script/standard.{h/cpp}
91d924ede1b421df31c895f4f43359e453a09ca5 Rename script/standard.{cpp/h} to script/solver.{cpp/h} (Andrew Chow) bacdb2e208531124e85ed2d4ea2a4b508fbb5088 Clean up script/standard.{h/cpp} includes (Andrew Chow) f3c9078b4cddec5581e52de5c216ae53984ec130 Clean up things that include script/standard.h (Andrew Chow) 8bbe257bac751859a272ddf52dc0328c1b5a1ede MOVEONLY: Move datacarrier defaults to policy.h (Andrew Chow) 7a172c76d2361fc3cdf6345590e26c79a7821672 Move CTxDestination to its own file (Andrew Chow) 145f36ec81e79d2e391847520364c2420ef0e0e8 Move Taproot{SpendData/Builder} to signingprovider.{h/cpp} (Andrew Chow) 86ea8bed5473f400f7a93fcc455393a574a2f319 Move CScriptID to script.{h/cpp} (Andrew Chow) b81ebff0d99c45c071b999796b8ae3f0f2517b22 Remove ScriptHash from CScriptID constructor (Andrew Chow) cba69dda3da0e4fa39cff5ce4dc81d1242fe651b Move MANDATORY_SCRIPT_VERIFY_FLAGS from script/standard.h to policy/policy.h (Anthony Towns) Pull request description: Some future work needs to touch things in script/standard.{h/cpp}, however it is unclear if it is safe to do so as they are included in several different places that could effect standardness and consensus. It contains a mix of policy parameters, consensus parameters, and utilities only used by the wallet. This PR breaks up the various components and renames the files to clearly separate everything. * `CTxDestination` is moved to a new file `src/addresstype.{cpp/h}` * `TaprootSpendData` and `TaprootBuilder` (and their utility functions and structs) are moved to `SigningProvider` as these are used only during signing. * `CScriptID` is moved to `script/script.h` to be next to `CScript`. * `MANDATORY_SCRIPT_VERIFY_FLAGS` is moved to `interpreter.h` * The parameters `DEFAULT_ACCEPT_DATACARRIER` and `MAX_OP_RETURN_RELAY` are moved to `policy.h` * `standard.{cpp/h}` is renamed to `solver.{cpp/h}` since that's all that's left in the file after the above moves ACKs for top commit: Sjors: ACK 91d924ede1b421df31c895f4f43359e453a09ca5 ajtowns: ACK 91d924ede1b421df31c895f4f43359e453a09ca5 MarcoFalke: ACK 91d924ede1b421df31c895f4f43359e453a09ca5 😇 murchandamus: ACK 91d924ede1b421df31c895f4f43359e453a09ca5 darosior: Code review ACK 91d924ede1b421df31c895f4f43359e453a09ca5. theStack: Code-review ACK 91d924ede1b421df31c895f4f43359e453a09ca5 Tree-SHA512: d347439890c652081f6a303d99b2bde6c371c96e7f4127c5db469764a17d39981f19884679ba883e28b733fde6142351dd8288c7bc61c379b7eefe7fa7acca1a
-rw-r--r--src/Makefile.am8
-rw-r--r--src/addresstype.cpp150
-rw-r--r--src/addresstype.h121
-rw-r--r--src/bench/descriptors.cpp1
-rw-r--r--src/bench/verify_script.cpp2
-rw-r--r--src/common/bloom.cpp2
-rw-r--r--src/compressor.cpp2
-rw-r--r--src/core_write.cpp2
-rw-r--r--src/init.cpp1
-rw-r--r--src/interfaces/wallet.h9
-rw-r--r--src/kernel/mempool_options.h1
-rw-r--r--src/key_io.cpp2
-rw-r--r--src/key_io.h2
-rw-r--r--src/node/mempool_args.cpp1
-rw-r--r--src/outputtype.cpp1
-rw-r--r--src/outputtype.h2
-rw-r--r--src/policy/policy.cpp2
-rw-r--r--src/policy/policy.h25
-rw-r--r--src/psbt.cpp1
-rw-r--r--src/qt/guiutil.cpp2
-rw-r--r--src/qt/test/wallettests.cpp1
-rw-r--r--src/qt/walletmodel.h1
-rw-r--r--src/rpc/mempool.cpp1
-rw-r--r--src/rpc/output_script.cpp1
-rw-r--r--src/rpc/rawtransaction.cpp2
-rw-r--r--src/rpc/util.cpp1
-rw-r--r--src/rpc/util.h2
-rw-r--r--src/script/descriptor.cpp3
-rw-r--r--src/script/miniscript.cpp1
-rw-r--r--src/script/script.cpp3
-rw-r--r--src/script/script.h11
-rw-r--r--src/script/sign.cpp3
-rw-r--r--src/script/sign.h2
-rw-r--r--src/script/signingprovider.cpp298
-rw-r--r--src/script/signingprovider.h134
-rw-r--r--src/script/solver.cpp223
-rw-r--r--src/script/solver.h66
-rw-r--r--src/script/standard.cpp653
-rw-r--r--src/script/standard.h330
-rw-r--r--src/signet.cpp1
-rw-r--r--src/test/blockfilter_index_tests.cpp2
-rw-r--r--src/test/blockmanager_tests.cpp1
-rw-r--r--src/test/coins_tests.cpp2
-rw-r--r--src/test/compress_tests.cpp2
-rw-r--r--src/test/denialofservice_tests.cpp1
-rw-r--r--src/test/descriptor_tests.cpp1
-rw-r--r--src/test/fuzz/integer.cpp2
-rw-r--r--src/test/fuzz/key.cpp2
-rw-r--r--src/test/fuzz/script.cpp2
-rw-r--r--src/test/fuzz/util.h2
-rw-r--r--src/test/interfaces_tests.cpp2
-rw-r--r--src/test/miner_tests.cpp2
-rw-r--r--src/test/miniscript_tests.cpp2
-rw-r--r--src/test/orphanage_tests.cpp1
-rw-r--r--src/test/script_standard_tests.cpp2
-rw-r--r--src/test/script_tests.cpp1
-rw-r--r--src/test/sigopcount_tests.cpp4
-rw-r--r--src/test/transaction_tests.cpp2
-rw-r--r--src/test/txindex_tests.cpp2
-rw-r--r--src/test/txpackage_tests.cpp1
-rw-r--r--src/test/txvalidation_tests.cpp1
-rw-r--r--src/test/txvalidationcache_tests.cpp1
-rw-r--r--src/test/util/mining.cpp1
-rw-r--r--src/test/validation_block_tests.cpp1
-rw-r--r--src/util/message.cpp1
-rw-r--r--src/wallet/coincontrol.h1
-rw-r--r--src/wallet/interfaces.cpp1
-rw-r--r--src/wallet/rpc/addresses.cpp5
-rw-r--r--src/wallet/rpc/backup.cpp2
-rw-r--r--src/wallet/rpc/coins.cpp3
-rw-r--r--src/wallet/rpc/spend.cpp1
-rw-r--r--src/wallet/scriptpubkeyman.cpp2
-rw-r--r--src/wallet/scriptpubkeyman.h3
-rw-r--r--src/wallet/spend.cpp2
-rw-r--r--src/wallet/test/ismine_tests.cpp3
-rw-r--r--src/wallet/test/scriptpubkeyman_tests.cpp2
-rw-r--r--src/wallet/test/spend_tests.cpp1
-rw-r--r--src/wallet/test/util.h2
-rw-r--r--src/wallet/test/wallet_tests.cpp2
-rw-r--r--src/wallet/wallet.cpp1
-rw-r--r--src/wallet/wallet.h1
-rw-r--r--src/wallet/walletdb.cpp1
-rw-r--r--src/wallet/walletdb.h1
83 files changed, 1096 insertions, 1053 deletions
diff --git a/src/Makefile.am b/src/Makefile.am
index 06c156a8c0..1f953ab624 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -117,6 +117,7 @@ endif
.PHONY: FORCE check-symbols check-security
# bitcoin core #
BITCOIN_CORE_H = \
+ addresstype.h \
addrdb.h \
addrman.h \
addrman_impl.h \
@@ -265,7 +266,7 @@ BITCOIN_CORE_H = \
script/sigcache.h \
script/sign.h \
script/signingprovider.h \
- script/standard.h \
+ script/solver.h \
shutdown.h \
signet.h \
streams.h \
@@ -659,6 +660,7 @@ libbitcoin_consensus_a_SOURCES = \
libbitcoin_common_a_CPPFLAGS = $(AM_CPPFLAGS) $(BITCOIN_INCLUDES) $(BOOST_CPPFLAGS)
libbitcoin_common_a_CXXFLAGS = $(AM_CXXFLAGS) $(PIE_FLAGS)
libbitcoin_common_a_SOURCES = \
+ addresstype.cpp \
base58.cpp \
bech32.cpp \
chainparams.cpp \
@@ -699,7 +701,7 @@ libbitcoin_common_a_SOURCES = \
script/miniscript.cpp \
script/sign.cpp \
script/signingprovider.cpp \
- script/standard.cpp \
+ script/solver.cpp \
warnings.cpp \
$(BITCOIN_CORE_H)
@@ -960,7 +962,7 @@ libbitcoinkernel_la_SOURCES = \
script/script.cpp \
script/script_error.cpp \
script/sigcache.cpp \
- script/standard.cpp \
+ script/solver.cpp \
signet.cpp \
streams.cpp \
support/cleanse.cpp \
diff --git a/src/addresstype.cpp b/src/addresstype.cpp
new file mode 100644
index 0000000000..d96b820bc7
--- /dev/null
+++ b/src/addresstype.cpp
@@ -0,0 +1,150 @@
+// Copyright (c) 2023 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or https://www.opensource.org/licenses/mit-license.php.
+
+#include <addresstype.h>
+#include <script/script.h>
+#include <script/solver.h>
+#include <hash.h>
+#include <pubkey.h>
+#include <uint256.h>
+#include <util/hash_type.h>
+
+#include <vector>
+
+typedef std::vector<unsigned char> valtype;
+
+ScriptHash::ScriptHash(const CScript& in) : BaseHash(Hash160(in)) {}
+ScriptHash::ScriptHash(const CScriptID& in) : BaseHash(static_cast<uint160>(in)) {}
+
+PKHash::PKHash(const CPubKey& pubkey) : BaseHash(pubkey.GetID()) {}
+PKHash::PKHash(const CKeyID& pubkey_id) : BaseHash(pubkey_id) {}
+
+WitnessV0KeyHash::WitnessV0KeyHash(const CPubKey& pubkey) : BaseHash(pubkey.GetID()) {}
+WitnessV0KeyHash::WitnessV0KeyHash(const PKHash& pubkey_hash) : BaseHash(static_cast<uint160>(pubkey_hash)) {}
+
+CKeyID ToKeyID(const PKHash& key_hash)
+{
+ return CKeyID{static_cast<uint160>(key_hash)};
+}
+
+CKeyID ToKeyID(const WitnessV0KeyHash& key_hash)
+{
+ return CKeyID{static_cast<uint160>(key_hash)};
+}
+
+CScriptID ToScriptID(const ScriptHash& script_hash)
+{
+ return CScriptID{static_cast<uint160>(script_hash)};
+}
+
+WitnessV0ScriptHash::WitnessV0ScriptHash(const CScript& in)
+{
+ CSHA256().Write(in.data(), in.size()).Finalize(begin());
+}
+
+bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet)
+{
+ std::vector<valtype> vSolutions;
+ TxoutType whichType = Solver(scriptPubKey, vSolutions);
+
+ switch (whichType) {
+ case TxoutType::PUBKEY: {
+ CPubKey pubKey(vSolutions[0]);
+ if (!pubKey.IsValid())
+ return false;
+
+ addressRet = PKHash(pubKey);
+ return true;
+ }
+ case TxoutType::PUBKEYHASH: {
+ addressRet = PKHash(uint160(vSolutions[0]));
+ return true;
+ }
+ case TxoutType::SCRIPTHASH: {
+ addressRet = ScriptHash(uint160(vSolutions[0]));
+ return true;
+ }
+ case TxoutType::WITNESS_V0_KEYHASH: {
+ WitnessV0KeyHash hash;
+ std::copy(vSolutions[0].begin(), vSolutions[0].end(), hash.begin());
+ addressRet = hash;
+ return true;
+ }
+ case TxoutType::WITNESS_V0_SCRIPTHASH: {
+ WitnessV0ScriptHash hash;
+ std::copy(vSolutions[0].begin(), vSolutions[0].end(), hash.begin());
+ addressRet = hash;
+ return true;
+ }
+ case TxoutType::WITNESS_V1_TAPROOT: {
+ WitnessV1Taproot tap;
+ std::copy(vSolutions[0].begin(), vSolutions[0].end(), tap.begin());
+ addressRet = tap;
+ return true;
+ }
+ case TxoutType::WITNESS_UNKNOWN: {
+ WitnessUnknown unk;
+ unk.version = vSolutions[0][0];
+ std::copy(vSolutions[1].begin(), vSolutions[1].end(), unk.program);
+ unk.length = vSolutions[1].size();
+ addressRet = unk;
+ return true;
+ }
+ case TxoutType::MULTISIG:
+ case TxoutType::NULL_DATA:
+ case TxoutType::NONSTANDARD:
+ return false;
+ } // no default case, so the compiler can warn about missing cases
+ assert(false);
+}
+
+namespace {
+class CScriptVisitor
+{
+public:
+ CScript operator()(const CNoDestination& dest) const
+ {
+ return CScript();
+ }
+
+ CScript operator()(const PKHash& keyID) const
+ {
+ return CScript() << OP_DUP << OP_HASH160 << ToByteVector(keyID) << OP_EQUALVERIFY << OP_CHECKSIG;
+ }
+
+ CScript operator()(const ScriptHash& scriptID) const
+ {
+ return CScript() << OP_HASH160 << ToByteVector(scriptID) << OP_EQUAL;
+ }
+
+ CScript operator()(const WitnessV0KeyHash& id) const
+ {
+ return CScript() << OP_0 << ToByteVector(id);
+ }
+
+ CScript operator()(const WitnessV0ScriptHash& id) const
+ {
+ return CScript() << OP_0 << ToByteVector(id);
+ }
+
+ CScript operator()(const WitnessV1Taproot& tap) const
+ {
+ return CScript() << OP_1 << ToByteVector(tap);
+ }
+
+ CScript operator()(const WitnessUnknown& id) const
+ {
+ return CScript() << CScript::EncodeOP_N(id.version) << std::vector<unsigned char>(id.program, id.program + id.length);
+ }
+};
+} // namespace
+
+CScript GetScriptForDestination(const CTxDestination& dest)
+{
+ return std::visit(CScriptVisitor(), dest);
+}
+
+bool IsValidDestination(const CTxDestination& dest) {
+ return dest.index() != 0;
+}
diff --git a/src/addresstype.h b/src/addresstype.h
new file mode 100644
index 0000000000..6b651e9014
--- /dev/null
+++ b/src/addresstype.h
@@ -0,0 +1,121 @@
+// Copyright (c) 2023 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or https://www.opensource.org/licenses/mit-license.php.
+
+#ifndef BITCOIN_ADDRESSTYPE_H
+#define BITCOIN_ADDRESSTYPE_H
+
+#include <pubkey.h>
+#include <script/script.h>
+#include <uint256.h>
+#include <util/hash_type.h>
+
+#include <variant>
+#include <algorithm>
+
+class CNoDestination {
+public:
+ friend bool operator==(const CNoDestination &a, const CNoDestination &b) { return true; }
+ friend bool operator<(const CNoDestination &a, const CNoDestination &b) { return true; }
+};
+
+struct PKHash : public BaseHash<uint160>
+{
+ PKHash() : BaseHash() {}
+ explicit PKHash(const uint160& hash) : BaseHash(hash) {}
+ explicit PKHash(const CPubKey& pubkey);
+ explicit PKHash(const CKeyID& pubkey_id);
+};
+CKeyID ToKeyID(const PKHash& key_hash);
+
+struct WitnessV0KeyHash;
+
+struct ScriptHash : public BaseHash<uint160>
+{
+ ScriptHash() : BaseHash() {}
+ // These don't do what you'd expect.
+ // Use ScriptHash(GetScriptForDestination(...)) instead.
+ explicit ScriptHash(const WitnessV0KeyHash& hash) = delete;
+ explicit ScriptHash(const PKHash& hash) = delete;
+
+ explicit ScriptHash(const uint160& hash) : BaseHash(hash) {}
+ explicit ScriptHash(const CScript& script);
+ explicit ScriptHash(const CScriptID& script);
+};
+CScriptID ToScriptID(const ScriptHash& script_hash);
+
+struct WitnessV0ScriptHash : public BaseHash<uint256>
+{
+ WitnessV0ScriptHash() : BaseHash() {}
+ explicit WitnessV0ScriptHash(const uint256& hash) : BaseHash(hash) {}
+ explicit WitnessV0ScriptHash(const CScript& script);
+};
+
+struct WitnessV0KeyHash : public BaseHash<uint160>
+{
+ WitnessV0KeyHash() : BaseHash() {}
+ explicit WitnessV0KeyHash(const uint160& hash) : BaseHash(hash) {}
+ explicit WitnessV0KeyHash(const CPubKey& pubkey);
+ explicit WitnessV0KeyHash(const PKHash& pubkey_hash);
+};
+CKeyID ToKeyID(const WitnessV0KeyHash& key_hash);
+
+struct WitnessV1Taproot : public XOnlyPubKey
+{
+ WitnessV1Taproot() : XOnlyPubKey() {}
+ explicit WitnessV1Taproot(const XOnlyPubKey& xpk) : XOnlyPubKey(xpk) {}
+};
+
+//! CTxDestination subtype to encode any future Witness version
+struct WitnessUnknown
+{
+ unsigned int version;
+ unsigned int length;
+ unsigned char program[40];
+
+ friend bool operator==(const WitnessUnknown& w1, const WitnessUnknown& w2) {
+ if (w1.version != w2.version) return false;
+ if (w1.length != w2.length) return false;
+ return std::equal(w1.program, w1.program + w1.length, w2.program);
+ }
+
+ friend bool operator<(const WitnessUnknown& w1, const WitnessUnknown& w2) {
+ if (w1.version < w2.version) return true;
+ if (w1.version > w2.version) return false;
+ if (w1.length < w2.length) return true;
+ if (w1.length > w2.length) return false;
+ return std::lexicographical_compare(w1.program, w1.program + w1.length, w2.program, w2.program + w2.length);
+ }
+};
+
+/**
+ * A txout script template with a specific destination. It is either:
+ * * CNoDestination: no destination set
+ * * PKHash: TxoutType::PUBKEYHASH destination (P2PKH)
+ * * ScriptHash: TxoutType::SCRIPTHASH destination (P2SH)
+ * * WitnessV0ScriptHash: TxoutType::WITNESS_V0_SCRIPTHASH destination (P2WSH)
+ * * WitnessV0KeyHash: TxoutType::WITNESS_V0_KEYHASH destination (P2WPKH)
+ * * WitnessV1Taproot: TxoutType::WITNESS_V1_TAPROOT destination (P2TR)
+ * * WitnessUnknown: TxoutType::WITNESS_UNKNOWN destination (P2W???)
+ * A CTxDestination is the internal data type encoded in a bitcoin address
+ */
+using CTxDestination = std::variant<CNoDestination, PKHash, ScriptHash, WitnessV0ScriptHash, WitnessV0KeyHash, WitnessV1Taproot, WitnessUnknown>;
+
+/** Check whether a CTxDestination is a CNoDestination. */
+bool IsValidDestination(const CTxDestination& dest);
+
+/**
+ * Parse a standard scriptPubKey for the destination address. Assigns result to
+ * the addressRet parameter and returns true if successful. Currently only works for P2PK,
+ * P2PKH, P2SH, P2WPKH, and P2WSH scripts.
+ */
+bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet);
+
+/**
+ * Generate a Bitcoin scriptPubKey for the given CTxDestination. Returns a P2PKH
+ * script for a CKeyID destination, a P2SH script for a CScriptID, and an empty
+ * script for CNoDestination.
+ */
+CScript GetScriptForDestination(const CTxDestination& dest);
+
+#endif // BITCOIN_ADDRESSTYPE_H
diff --git a/src/bench/descriptors.cpp b/src/bench/descriptors.cpp
index 5d28d26909..fbef1395fb 100644
--- a/src/bench/descriptors.cpp
+++ b/src/bench/descriptors.cpp
@@ -6,7 +6,6 @@
#include <key.h>
#include <pubkey.h>
#include <script/descriptor.h>
-#include <script/standard.h>
#include <string>
#include <utility>
diff --git a/src/bench/verify_script.cpp b/src/bench/verify_script.cpp
index 757094167a..11f96b1005 100644
--- a/src/bench/verify_script.cpp
+++ b/src/bench/verify_script.cpp
@@ -8,7 +8,7 @@
#include <script/bitcoinconsensus.h>
#endif
#include <script/script.h>
-#include <script/standard.h>
+#include <script/interpreter.h>
#include <streams.h>
#include <test/util/transaction_utils.h>
diff --git a/src/common/bloom.cpp b/src/common/bloom.cpp
index fd3276b5a7..5c3ad882a1 100644
--- a/src/common/bloom.cpp
+++ b/src/common/bloom.cpp
@@ -8,7 +8,7 @@
#include <primitives/transaction.h>
#include <random.h>
#include <script/script.h>
-#include <script/standard.h>
+#include <script/solver.h>
#include <span.h>
#include <streams.h>
#include <util/fastrange.h>
diff --git a/src/compressor.cpp b/src/compressor.cpp
index 32af8eab49..668e25581c 100644
--- a/src/compressor.cpp
+++ b/src/compressor.cpp
@@ -6,7 +6,7 @@
#include <compressor.h>
#include <pubkey.h>
-#include <script/standard.h>
+#include <script/script.h>
/*
* These check for scripts for which a special case with a shorter encoding is defined.
diff --git a/src/core_write.cpp b/src/core_write.cpp
index 54ca306f60..7cf019a42e 100644
--- a/src/core_write.cpp
+++ b/src/core_write.cpp
@@ -11,7 +11,7 @@
#include <key_io.h>
#include <script/descriptor.h>
#include <script/script.h>
-#include <script/standard.h>
+#include <script/solver.h>
#include <serialize.h>
#include <streams.h>
#include <undo.h>
diff --git a/src/init.cpp b/src/init.cpp
index c2c4dbe459..864c2e278b 100644
--- a/src/init.cpp
+++ b/src/init.cpp
@@ -65,7 +65,6 @@
#include <rpc/util.h>
#include <scheduler.h>
#include <script/sigcache.h>
-#include <script/standard.h>
#include <shutdown.h>
#include <sync.h>
#include <timedata.h>
diff --git a/src/interfaces/wallet.h b/src/interfaces/wallet.h
index 8c31112fc9..9987681367 100644
--- a/src/interfaces/wallet.h
+++ b/src/interfaces/wallet.h
@@ -5,11 +5,12 @@
#ifndef BITCOIN_INTERFACES_WALLET_H
#define BITCOIN_INTERFACES_WALLET_H
+#include <addresstype.h>
#include <consensus/amount.h>
-#include <interfaces/chain.h> // For ChainClient
-#include <pubkey.h> // For CKeyID and CScriptID (definitions needed in CTxDestination instantiation)
-#include <script/standard.h> // For CTxDestination
-#include <support/allocators/secure.h> // For SecureString
+#include <interfaces/chain.h>
+#include <pubkey.h>
+#include <script/script.h>
+#include <support/allocators/secure.h>
#include <util/fs.h>
#include <util/message.h>
#include <util/result.h>
diff --git a/src/kernel/mempool_options.h b/src/kernel/mempool_options.h
index beb5fca5e9..58bb3debbf 100644
--- a/src/kernel/mempool_options.h
+++ b/src/kernel/mempool_options.h
@@ -8,7 +8,6 @@
#include <policy/feerate.h>
#include <policy/policy.h>
-#include <script/standard.h>
#include <chrono>
#include <cstdint>
diff --git a/src/key_io.cpp b/src/key_io.cpp
index 454a96df5e..a061165613 100644
--- a/src/key_io.cpp
+++ b/src/key_io.cpp
@@ -6,6 +6,8 @@
#include <base58.h>
#include <bech32.h>
+#include <script/interpreter.h>
+#include <script/solver.h>
#include <util/strencodings.h>
#include <algorithm>
diff --git a/src/key_io.h b/src/key_io.h
index 07b80c4b85..e387273e54 100644
--- a/src/key_io.h
+++ b/src/key_io.h
@@ -6,10 +6,10 @@
#ifndef BITCOIN_KEY_IO_H
#define BITCOIN_KEY_IO_H
+#include <addresstype.h>
#include <chainparams.h>
#include <key.h>
#include <pubkey.h>
-#include <script/standard.h>
#include <string>
diff --git a/src/node/mempool_args.cpp b/src/node/mempool_args.cpp
index 5381902263..7d8244980d 100644
--- a/src/node/mempool_args.cpp
+++ b/src/node/mempool_args.cpp
@@ -13,7 +13,6 @@
#include <logging.h>
#include <policy/feerate.h>
#include <policy/policy.h>
-#include <script/standard.h>
#include <tinyformat.h>
#include <util/error.h>
#include <util/moneystr.h>
diff --git a/src/outputtype.cpp b/src/outputtype.cpp
index 9a3870d8dc..566e5ec55a 100644
--- a/src/outputtype.cpp
+++ b/src/outputtype.cpp
@@ -9,7 +9,6 @@
#include <script/script.h>
#include <script/sign.h>
#include <script/signingprovider.h>
-#include <script/standard.h>
#include <util/vector.h>
#include <assert.h>
diff --git a/src/outputtype.h b/src/outputtype.h
index 7c50f445fc..a2d5942320 100644
--- a/src/outputtype.h
+++ b/src/outputtype.h
@@ -6,8 +6,8 @@
#ifndef BITCOIN_OUTPUTTYPE_H
#define BITCOIN_OUTPUTTYPE_H
+#include <addresstype.h>
#include <script/signingprovider.h>
-#include <script/standard.h>
#include <array>
#include <optional>
diff --git a/src/policy/policy.cpp b/src/policy/policy.cpp
index 41b5b2d0f1..d08ec4fb7f 100644
--- a/src/policy/policy.cpp
+++ b/src/policy/policy.cpp
@@ -15,7 +15,7 @@
#include <primitives/transaction.h>
#include <script/interpreter.h>
#include <script/script.h>
-#include <script/standard.h>
+#include <script/solver.h>
#include <serialize.h>
#include <span.h>
diff --git a/src/policy/policy.h b/src/policy/policy.h
index 9135cae91c..687d1881cb 100644
--- a/src/policy/policy.h
+++ b/src/policy/policy.h
@@ -10,7 +10,7 @@
#include <consensus/consensus.h>
#include <primitives/transaction.h>
#include <script/interpreter.h>
-#include <script/standard.h>
+#include <script/solver.h>
#include <cstdint>
#include <string>
@@ -63,16 +63,35 @@ static constexpr unsigned int DEFAULT_ANCESTOR_SIZE_LIMIT_KVB{101};
static constexpr unsigned int DEFAULT_DESCENDANT_LIMIT{25};
/** Default for -limitdescendantsize, maximum kilobytes of in-mempool descendants */
static constexpr unsigned int DEFAULT_DESCENDANT_SIZE_LIMIT_KVB{101};
+/** Default for -datacarrier */
+static const bool DEFAULT_ACCEPT_DATACARRIER = true;
+/**
+ * Default setting for -datacarriersize. 80 bytes of data, +1 for OP_RETURN,
+ * +2 for the pushdata opcodes.
+ */
+static const unsigned int MAX_OP_RETURN_RELAY = 83;
/**
* An extra transaction can be added to a package, as long as it only has one
* ancestor and is no larger than this. Not really any reason to make this
* configurable as it doesn't materially change DoS parameters.
*/
static constexpr unsigned int EXTRA_DESCENDANT_TX_SIZE_LIMIT{10000};
+
+
+/**
+ * Mandatory script verification flags that all new transactions must comply with for
+ * them to be valid. Failing one of these tests may trigger a DoS ban;
+ * see CheckInputScripts() for details.
+ *
+ * Note that this does not affect consensus validity; see GetBlockScriptFlags()
+ * for that.
+ */
+static const unsigned int MANDATORY_SCRIPT_VERIFY_FLAGS = SCRIPT_VERIFY_P2SH;
+
/**
* Standard script verification flags that standard transactions will comply
- * with. However scripts violating these flags may still be present in valid
- * blocks and we must accept those blocks.
+ * with. However we do not ban/disconnect nodes that forward txs violating
+ * these rules, for better forwards and backwards compatability.
*/
static constexpr unsigned int STANDARD_SCRIPT_VERIFY_FLAGS{MANDATORY_SCRIPT_VERIFY_FLAGS |
SCRIPT_VERIFY_DERSIG |
diff --git a/src/psbt.cpp b/src/psbt.cpp
index 009ed966ed..7ec9b9c136 100644
--- a/src/psbt.cpp
+++ b/src/psbt.cpp
@@ -5,6 +5,7 @@
#include <psbt.h>
#include <policy/policy.h>
+#include <script/signingprovider.h>
#include <util/check.h>
#include <util/strencodings.h>
diff --git a/src/qt/guiutil.cpp b/src/qt/guiutil.cpp
index 8d8328aad8..eb9c65caf2 100644
--- a/src/qt/guiutil.cpp
+++ b/src/qt/guiutil.cpp
@@ -10,6 +10,7 @@
#include <qt/qvalidatedlineedit.h>
#include <qt/sendcoinsrecipient.h>
+#include <addresstype.h>
#include <base58.h>
#include <chainparams.h>
#include <common/args.h>
@@ -20,7 +21,6 @@
#include <primitives/transaction.h>
#include <protocol.h>
#include <script/script.h>
-#include <script/standard.h>
#include <util/chaintype.h>
#include <util/exception.h>
#include <util/fs.h>
diff --git a/src/qt/test/wallettests.cpp b/src/qt/test/wallettests.cpp
index 5f789e400e..f5b86f44a6 100644
--- a/src/qt/test/wallettests.cpp
+++ b/src/qt/test/wallettests.cpp
@@ -24,6 +24,7 @@
#include <qt/transactiontablemodel.h>
#include <qt/transactionview.h>
#include <qt/walletmodel.h>
+#include <script/solver.h>
#include <test/util/setup_common.h>
#include <validation.h>
#include <wallet/test/util.h>
diff --git a/src/qt/walletmodel.h b/src/qt/walletmodel.h
index 4f75d41404..68218b0c1b 100644
--- a/src/qt/walletmodel.h
+++ b/src/qt/walletmodel.h
@@ -10,7 +10,6 @@
#endif
#include <key.h>
-#include <script/standard.h>
#include <qt/walletmodeltransaction.h>
diff --git a/src/rpc/mempool.cpp b/src/rpc/mempool.cpp
index 90ee2a48af..b1d2414416 100644
--- a/src/rpc/mempool.cpp
+++ b/src/rpc/mempool.cpp
@@ -17,7 +17,6 @@
#include <rpc/server.h>
#include <rpc/server_util.h>
#include <rpc/util.h>
-#include <script/standard.h>
#include <txmempool.h>
#include <univalue.h>
#include <util/fs.h>
diff --git a/src/rpc/output_script.cpp b/src/rpc/output_script.cpp
index 990ec3ab0c..4dd424fa14 100644
--- a/src/rpc/output_script.cpp
+++ b/src/rpc/output_script.cpp
@@ -13,7 +13,6 @@
#include <script/descriptor.h>
#include <script/script.h>
#include <script/signingprovider.h>
-#include <script/standard.h>
#include <tinyformat.h>
#include <univalue.h>
#include <util/check.h>
diff --git a/src/rpc/rawtransaction.cpp b/src/rpc/rawtransaction.cpp
index eb0200ccf5..9198529378 100644
--- a/src/rpc/rawtransaction.cpp
+++ b/src/rpc/rawtransaction.cpp
@@ -30,7 +30,7 @@
#include <script/script.h>
#include <script/sign.h>
#include <script/signingprovider.h>
-#include <script/standard.h>
+#include <script/solver.h>
#include <uint256.h>
#include <undo.h>
#include <util/bip32.h>
diff --git a/src/rpc/util.cpp b/src/rpc/util.cpp
index faae840d40..2732f1297a 100644
--- a/src/rpc/util.cpp
+++ b/src/rpc/util.cpp
@@ -12,6 +12,7 @@
#include <rpc/util.h>
#include <script/descriptor.h>
#include <script/signingprovider.h>
+#include <script/solver.h>
#include <tinyformat.h>
#include <util/check.h>
#include <util/result.h>
diff --git a/src/rpc/util.h b/src/rpc/util.h
index 02d26f1ab7..ac0b2c088e 100644
--- a/src/rpc/util.h
+++ b/src/rpc/util.h
@@ -5,6 +5,7 @@
#ifndef BITCOIN_RPC_UTIL_H
#define BITCOIN_RPC_UTIL_H
+#include <addresstype.h>
#include <node/transaction.h>
#include <outputtype.h>
#include <protocol.h>
@@ -13,7 +14,6 @@
#include <rpc/request.h>
#include <script/script.h>
#include <script/sign.h>
-#include <script/standard.h>
#include <univalue.h>
#include <util/check.h>
diff --git a/src/script/descriptor.cpp b/src/script/descriptor.cpp
index 09ded5fc61..436ea9c093 100644
--- a/src/script/descriptor.cpp
+++ b/src/script/descriptor.cpp
@@ -9,7 +9,8 @@
#include <pubkey.h>
#include <script/miniscript.h>
#include <script/script.h>
-#include <script/standard.h>
+#include <script/signingprovider.h>
+#include <script/solver.h>
#include <uint256.h>
#include <common/args.h>
diff --git a/src/script/miniscript.cpp b/src/script/miniscript.cpp
index 3937638cf8..19556a9775 100644
--- a/src/script/miniscript.cpp
+++ b/src/script/miniscript.cpp
@@ -5,7 +5,6 @@
#include <string>
#include <vector>
#include <script/script.h>
-#include <script/standard.h>
#include <script/miniscript.h>
#include <assert.h>
diff --git a/src/script/script.cpp b/src/script/script.cpp
index 79d19b9085..1594d3cc79 100644
--- a/src/script/script.cpp
+++ b/src/script/script.cpp
@@ -5,10 +5,13 @@
#include <script/script.h>
+#include <hash.h>
#include <util/strencodings.h>
#include <string>
+CScriptID::CScriptID(const CScript& in) : BaseHash(Hash160(in)) {}
+
std::string GetOpName(opcodetype opcode)
{
switch (opcode)
diff --git a/src/script/script.h b/src/script/script.h
index 374ae1642e..902f756afc 100644
--- a/src/script/script.h
+++ b/src/script/script.h
@@ -10,6 +10,8 @@
#include <crypto/common.h>
#include <prevector.h>
#include <serialize.h>
+#include <uint256.h>
+#include <util/hash_type.h>
#include <assert.h>
#include <climits>
@@ -575,6 +577,15 @@ struct CScriptWitness
std::string ToString() const;
};
+/** A reference to a CScript: the Hash160 of its serialization */
+class CScriptID : public BaseHash<uint160>
+{
+public:
+ CScriptID() : BaseHash() {}
+ explicit CScriptID(const CScript& in);
+ explicit CScriptID(const uint160& in) : BaseHash(in) {}
+};
+
/** Test for OP_SUCCESSx opcodes as defined by BIP342. */
bool IsOpSuccess(const opcodetype& opcode);
diff --git a/src/script/sign.cpp b/src/script/sign.cpp
index 85589fe86b..92b7ad50b5 100644
--- a/src/script/sign.cpp
+++ b/src/script/sign.cpp
@@ -11,8 +11,9 @@
#include <primitives/transaction.h>
#include <script/keyorigin.h>
#include <script/miniscript.h>
+#include <script/script.h>
#include <script/signingprovider.h>
-#include <script/standard.h>
+#include <script/solver.h>
#include <uint256.h>
#include <util/translation.h>
#include <util/vector.h>
diff --git a/src/script/sign.h b/src/script/sign.h
index f46bc55992..4d7dade44e 100644
--- a/src/script/sign.h
+++ b/src/script/sign.h
@@ -12,7 +12,7 @@
#include <pubkey.h>
#include <script/interpreter.h>
#include <script/keyorigin.h>
-#include <script/standard.h>
+#include <script/signingprovider.h>
#include <uint256.h>
class CKey;
diff --git a/src/script/signingprovider.cpp b/src/script/signingprovider.cpp
index ef055573b9..f3a69e5d21 100644
--- a/src/script/signingprovider.cpp
+++ b/src/script/signingprovider.cpp
@@ -4,8 +4,8 @@
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
#include <script/keyorigin.h>
+#include <script/interpreter.h>
#include <script/signingprovider.h>
-#include <script/standard.h>
#include <logging.h>
@@ -205,7 +205,7 @@ CKeyID GetKeyForDestination(const SigningProvider& store, const CTxDestination&
}
if (auto script_hash = std::get_if<ScriptHash>(&dest)) {
CScript script;
- CScriptID script_id(*script_hash);
+ CScriptID script_id = ToScriptID(*script_hash);
CTxDestination inner_dest;
if (store.GetCScript(script_id, script) && ExtractDestination(script, inner_dest)) {
if (auto inner_witness_id = std::get_if<WitnessV0KeyHash>(&inner_dest)) {
@@ -225,3 +225,297 @@ CKeyID GetKeyForDestination(const SigningProvider& store, const CTxDestination&
}
return CKeyID();
}
+/*static*/ TaprootBuilder::NodeInfo TaprootBuilder::Combine(NodeInfo&& a, NodeInfo&& b)
+{
+ NodeInfo ret;
+ /* Iterate over all tracked leaves in a, add b's hash to their Merkle branch, and move them to ret. */
+ for (auto& leaf : a.leaves) {
+ leaf.merkle_branch.push_back(b.hash);
+ ret.leaves.emplace_back(std::move(leaf));
+ }
+ /* Iterate over all tracked leaves in b, add a's hash to their Merkle branch, and move them to ret. */
+ for (auto& leaf : b.leaves) {
+ leaf.merkle_branch.push_back(a.hash);
+ ret.leaves.emplace_back(std::move(leaf));
+ }
+ ret.hash = ComputeTapbranchHash(a.hash, b.hash);
+ return ret;
+}
+
+void TaprootSpendData::Merge(TaprootSpendData other)
+{
+ // TODO: figure out how to better deal with conflicting information
+ // being merged.
+ if (internal_key.IsNull() && !other.internal_key.IsNull()) {
+ internal_key = other.internal_key;
+ }
+ if (merkle_root.IsNull() && !other.merkle_root.IsNull()) {
+ merkle_root = other.merkle_root;
+ }
+ for (auto& [key, control_blocks] : other.scripts) {
+ scripts[key].merge(std::move(control_blocks));
+ }
+}
+
+void TaprootBuilder::Insert(TaprootBuilder::NodeInfo&& node, int depth)
+{
+ assert(depth >= 0 && (size_t)depth <= TAPROOT_CONTROL_MAX_NODE_COUNT);
+ /* We cannot insert a leaf at a lower depth while a deeper branch is unfinished. Doing
+ * so would mean the Add() invocations do not correspond to a DFS traversal of a
+ * binary tree. */
+ if ((size_t)depth + 1 < m_branch.size()) {
+ m_valid = false;
+ return;
+ }
+ /* As long as an entry in the branch exists at the specified depth, combine it and propagate up.
+ * The 'node' variable is overwritten here with the newly combined node. */
+ while (m_valid && m_branch.size() > (size_t)depth && m_branch[depth].has_value()) {
+ node = Combine(std::move(node), std::move(*m_branch[depth]));
+ m_branch.pop_back();
+ if (depth == 0) m_valid = false; /* Can't propagate further up than the root */
+ --depth;
+ }
+ if (m_valid) {
+ /* Make sure the branch is big enough to place the new node. */
+ if (m_branch.size() <= (size_t)depth) m_branch.resize((size_t)depth + 1);
+ assert(!m_branch[depth].has_value());
+ m_branch[depth] = std::move(node);
+ }
+}
+
+/*static*/ bool TaprootBuilder::ValidDepths(const std::vector<int>& depths)
+{
+ std::vector<bool> branch;
+ for (int depth : depths) {
+ // This inner loop corresponds to effectively the same logic on branch
+ // as what Insert() performs on the m_branch variable. Instead of
+ // storing a NodeInfo object, just remember whether or not there is one
+ // at that depth.
+ if (depth < 0 || (size_t)depth > TAPROOT_CONTROL_MAX_NODE_COUNT) return false;
+ if ((size_t)depth + 1 < branch.size()) return false;
+ while (branch.size() > (size_t)depth && branch[depth]) {
+ branch.pop_back();
+ if (depth == 0) return false;
+ --depth;
+ }
+ if (branch.size() <= (size_t)depth) branch.resize((size_t)depth + 1);
+ assert(!branch[depth]);
+ branch[depth] = true;
+ }
+ // And this check corresponds to the IsComplete() check on m_branch.
+ return branch.size() == 0 || (branch.size() == 1 && branch[0]);
+}
+
+TaprootBuilder& TaprootBuilder::Add(int depth, Span<const unsigned char> script, int leaf_version, bool track)
+{
+ assert((leaf_version & ~TAPROOT_LEAF_MASK) == 0);
+ if (!IsValid()) return *this;
+ /* Construct NodeInfo object with leaf hash and (if track is true) also leaf information. */
+ NodeInfo node;
+ node.hash = ComputeTapleafHash(leaf_version, script);
+ if (track) node.leaves.emplace_back(LeafInfo{std::vector<unsigned char>(script.begin(), script.end()), leaf_version, {}});
+ /* Insert into the branch. */
+ Insert(std::move(node), depth);
+ return *this;
+}
+
+TaprootBuilder& TaprootBuilder::AddOmitted(int depth, const uint256& hash)
+{
+ if (!IsValid()) return *this;
+ /* Construct NodeInfo object with the hash directly, and insert it into the branch. */
+ NodeInfo node;
+ node.hash = hash;
+ Insert(std::move(node), depth);
+ return *this;
+}
+
+TaprootBuilder& TaprootBuilder::Finalize(const XOnlyPubKey& internal_key)
+{
+ /* Can only call this function when IsComplete() is true. */
+ assert(IsComplete());
+ m_internal_key = internal_key;
+ auto ret = m_internal_key.CreateTapTweak(m_branch.size() == 0 ? nullptr : &m_branch[0]->hash);
+ assert(ret.has_value());
+ std::tie(m_output_key, m_parity) = *ret;
+ return *this;
+}
+
+WitnessV1Taproot TaprootBuilder::GetOutput() { return WitnessV1Taproot{m_output_key}; }
+
+TaprootSpendData TaprootBuilder::GetSpendData() const
+{
+ assert(IsComplete());
+ assert(m_output_key.IsFullyValid());
+ TaprootSpendData spd;
+ spd.merkle_root = m_branch.size() == 0 ? uint256() : m_branch[0]->hash;
+ spd.internal_key = m_internal_key;
+ if (m_branch.size()) {
+ // If any script paths exist, they have been combined into the root m_branch[0]
+ // by now. Compute the control block for each of its tracked leaves, and put them in
+ // spd.scripts.
+ for (const auto& leaf : m_branch[0]->leaves) {
+ std::vector<unsigned char> control_block;
+ control_block.resize(TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * leaf.merkle_branch.size());
+ control_block[0] = leaf.leaf_version | (m_parity ? 1 : 0);
+ std::copy(m_internal_key.begin(), m_internal_key.end(), control_block.begin() + 1);
+ if (leaf.merkle_branch.size()) {
+ std::copy(leaf.merkle_branch[0].begin(),
+ leaf.merkle_branch[0].begin() + TAPROOT_CONTROL_NODE_SIZE * leaf.merkle_branch.size(),
+ control_block.begin() + TAPROOT_CONTROL_BASE_SIZE);
+ }
+ spd.scripts[{leaf.script, leaf.leaf_version}].insert(std::move(control_block));
+ }
+ }
+ return spd;
+}
+
+std::optional<std::vector<std::tuple<int, std::vector<unsigned char>, int>>> InferTaprootTree(const TaprootSpendData& spenddata, const XOnlyPubKey& output)
+{
+ // Verify that the output matches the assumed Merkle root and internal key.
+ auto tweak = spenddata.internal_key.CreateTapTweak(spenddata.merkle_root.IsNull() ? nullptr : &spenddata.merkle_root);
+ if (!tweak || tweak->first != output) return std::nullopt;
+ // If the Merkle root is 0, the tree is empty, and we're done.
+ std::vector<std::tuple<int, std::vector<unsigned char>, int>> ret;
+ if (spenddata.merkle_root.IsNull()) return ret;
+
+ /** Data structure to represent the nodes of the tree we're going to build. */
+ struct TreeNode {
+ /** Hash of this node, if known; 0 otherwise. */
+ uint256 hash;
+ /** The left and right subtrees (note that their order is irrelevant). */
+ std::unique_ptr<TreeNode> sub[2];
+ /** If this is known to be a leaf node, a pointer to the (script, leaf_ver) pair.
+ * nullptr otherwise. */
+ const std::pair<std::vector<unsigned char>, int>* leaf = nullptr;
+ /** Whether or not this node has been explored (is known to be a leaf, or known to have children). */
+ bool explored = false;
+ /** Whether or not this node is an inner node (unknown until explored = true). */
+ bool inner;
+ /** Whether or not we have produced output for this subtree. */
+ bool done = false;
+ };
+
+ // Build tree from the provided branches.
+ TreeNode root;
+ root.hash = spenddata.merkle_root;
+ for (const auto& [key, control_blocks] : spenddata.scripts) {
+ const auto& [script, leaf_ver] = key;
+ for (const auto& control : control_blocks) {
+ // Skip script records with nonsensical leaf version.
+ if (leaf_ver < 0 || leaf_ver >= 0x100 || leaf_ver & 1) continue;
+ // Skip script records with invalid control block sizes.
+ if (control.size() < TAPROOT_CONTROL_BASE_SIZE || control.size() > TAPROOT_CONTROL_MAX_SIZE ||
+ ((control.size() - TAPROOT_CONTROL_BASE_SIZE) % TAPROOT_CONTROL_NODE_SIZE) != 0) continue;
+ // Skip script records that don't match the control block.
+ if ((control[0] & TAPROOT_LEAF_MASK) != leaf_ver) continue;
+ // Skip script records that don't match the provided Merkle root.
+ const uint256 leaf_hash = ComputeTapleafHash(leaf_ver, script);
+ const uint256 merkle_root = ComputeTaprootMerkleRoot(control, leaf_hash);
+ if (merkle_root != spenddata.merkle_root) continue;
+
+ TreeNode* node = &root;
+ size_t levels = (control.size() - TAPROOT_CONTROL_BASE_SIZE) / TAPROOT_CONTROL_NODE_SIZE;
+ for (size_t depth = 0; depth < levels; ++depth) {
+ // Can't descend into a node which we already know is a leaf.
+ if (node->explored && !node->inner) return std::nullopt;
+
+ // Extract partner hash from Merkle branch in control block.
+ uint256 hash;
+ std::copy(control.begin() + TAPROOT_CONTROL_BASE_SIZE + (levels - 1 - depth) * TAPROOT_CONTROL_NODE_SIZE,
+ control.begin() + TAPROOT_CONTROL_BASE_SIZE + (levels - depth) * TAPROOT_CONTROL_NODE_SIZE,
+ hash.begin());
+
+ if (node->sub[0]) {
+ // Descend into the existing left or right branch.
+ bool desc = false;
+ for (int i = 0; i < 2; ++i) {
+ if (node->sub[i]->hash == hash || (node->sub[i]->hash.IsNull() && node->sub[1-i]->hash != hash)) {
+ node->sub[i]->hash = hash;
+ node = &*node->sub[1-i];
+ desc = true;
+ break;
+ }
+ }
+ if (!desc) return std::nullopt; // This probably requires a hash collision to hit.
+ } else {
+ // We're in an unexplored node. Create subtrees and descend.
+ node->explored = true;
+ node->inner = true;
+ node->sub[0] = std::make_unique<TreeNode>();
+ node->sub[1] = std::make_unique<TreeNode>();
+ node->sub[1]->hash = hash;
+ node = &*node->sub[0];
+ }
+ }
+ // Cannot turn a known inner node into a leaf.
+ if (node->sub[0]) return std::nullopt;
+ node->explored = true;
+ node->inner = false;
+ node->leaf = &key;
+ node->hash = leaf_hash;
+ }
+ }
+
+ // Recursive processing to turn the tree into flattened output. Use an explicit stack here to avoid
+ // overflowing the call stack (the tree may be 128 levels deep).
+ std::vector<TreeNode*> stack{&root};
+ while (!stack.empty()) {
+ TreeNode& node = *stack.back();
+ if (!node.explored) {
+ // Unexplored node, which means the tree is incomplete.
+ return std::nullopt;
+ } else if (!node.inner) {
+ // Leaf node; produce output.
+ ret.emplace_back(stack.size() - 1, node.leaf->first, node.leaf->second);
+ node.done = true;
+ stack.pop_back();
+ } else if (node.sub[0]->done && !node.sub[1]->done && !node.sub[1]->explored && !node.sub[1]->hash.IsNull() &&
+ ComputeTapbranchHash(node.sub[1]->hash, node.sub[1]->hash) == node.hash) {
+ // Whenever there are nodes with two identical subtrees under it, we run into a problem:
+ // the control blocks for the leaves underneath those will be identical as well, and thus
+ // they will all be matched to the same path in the tree. The result is that at the location
+ // where the duplicate occurred, the left child will contain a normal tree that can be explored
+ // and processed, but the right one will remain unexplored.
+ //
+ // This situation can be detected, by encountering an inner node with unexplored right subtree
+ // with known hash, and H_TapBranch(hash, hash) is equal to the parent node (this node)'s hash.
+ //
+ // To deal with this, simply process the left tree a second time (set its done flag to false;
+ // noting that the done flag of its children have already been set to false after processing
+ // those). To avoid ending up in an infinite loop, set the done flag of the right (unexplored)
+ // subtree to true.
+ node.sub[0]->done = false;
+ node.sub[1]->done = true;
+ } else if (node.sub[0]->done && node.sub[1]->done) {
+ // An internal node which we're finished with.
+ node.sub[0]->done = false;
+ node.sub[1]->done = false;
+ node.done = true;
+ stack.pop_back();
+ } else if (!node.sub[0]->done) {
+ // An internal node whose left branch hasn't been processed yet. Do so first.
+ stack.push_back(&*node.sub[0]);
+ } else if (!node.sub[1]->done) {
+ // An internal node whose right branch hasn't been processed yet. Do so first.
+ stack.push_back(&*node.sub[1]);
+ }
+ }
+
+ return ret;
+}
+
+std::vector<std::tuple<uint8_t, uint8_t, std::vector<unsigned char>>> TaprootBuilder::GetTreeTuples() const
+{
+ assert(IsComplete());
+ std::vector<std::tuple<uint8_t, uint8_t, std::vector<unsigned char>>> tuples;
+ if (m_branch.size()) {
+ const auto& leaves = m_branch[0]->leaves;
+ for (const auto& leaf : leaves) {
+ assert(leaf.merkle_branch.size() <= TAPROOT_CONTROL_MAX_NODE_COUNT);
+ uint8_t depth = (uint8_t)leaf.merkle_branch.size();
+ uint8_t leaf_ver = (uint8_t)leaf.leaf_version;
+ tuples.push_back(std::make_tuple(depth, leaf_ver, leaf.script));
+ }
+ }
+ return tuples;
+}
diff --git a/src/script/signingprovider.h b/src/script/signingprovider.h
index a5bbcff6a0..712e2e73d1 100644
--- a/src/script/signingprovider.h
+++ b/src/script/signingprovider.h
@@ -6,14 +6,146 @@
#ifndef BITCOIN_SCRIPT_SIGNINGPROVIDER_H
#define BITCOIN_SCRIPT_SIGNINGPROVIDER_H
+#include <addresstype.h>
#include <attributes.h>
#include <key.h>
#include <pubkey.h>
#include <script/keyorigin.h>
#include <script/script.h>
-#include <script/standard.h>
#include <sync.h>
+struct ShortestVectorFirstComparator
+{
+ bool operator()(const std::vector<unsigned char>& a, const std::vector<unsigned char>& b) const
+ {
+ if (a.size() < b.size()) return true;
+ if (a.size() > b.size()) return false;
+ return a < b;
+ }
+};
+
+struct TaprootSpendData
+{
+ /** The BIP341 internal key. */
+ XOnlyPubKey internal_key;
+ /** The Merkle root of the script tree (0 if no scripts). */
+ uint256 merkle_root;
+ /** Map from (script, leaf_version) to (sets of) control blocks.
+ * More than one control block for a given script is only possible if it
+ * appears in multiple branches of the tree. We keep them all so that
+ * inference can reconstruct the full tree. Within each set, the control
+ * blocks are sorted by size, so that the signing logic can easily
+ * prefer the cheapest one. */
+ std::map<std::pair<std::vector<unsigned char>, int>, std::set<std::vector<unsigned char>, ShortestVectorFirstComparator>> scripts;
+ /** Merge other TaprootSpendData (for the same scriptPubKey) into this. */
+ void Merge(TaprootSpendData other);
+};
+
+/** Utility class to construct Taproot outputs from internal key and script tree. */
+class TaprootBuilder
+{
+private:
+ /** Information about a tracked leaf in the Merkle tree. */
+ struct LeafInfo
+ {
+ std::vector<unsigned char> script; //!< The script.
+ int leaf_version; //!< The leaf version for that script.
+ std::vector<uint256> merkle_branch; //!< The hashing partners above this leaf.
+ };
+
+ /** Information associated with a node in the Merkle tree. */
+ struct NodeInfo
+ {
+ /** Merkle hash of this node. */
+ uint256 hash;
+ /** Tracked leaves underneath this node (either from the node itself, or its children).
+ * The merkle_branch field of each is the partners to get to *this* node. */
+ std::vector<LeafInfo> leaves;
+ };
+ /** Whether the builder is in a valid state so far. */
+ bool m_valid = true;
+
+ /** The current state of the builder.
+ *
+ * For each level in the tree, one NodeInfo object may be present. m_branch[0]
+ * is information about the root; further values are for deeper subtrees being
+ * explored.
+ *
+ * For every right branch taken to reach the position we're currently
+ * working in, there will be a (non-nullopt) entry in m_branch corresponding
+ * to the left branch at that level.
+ *
+ * For example, imagine this tree: - N0 -
+ * / \
+ * N1 N2
+ * / \ / \
+ * A B C N3
+ * / \
+ * D E
+ *
+ * Initially, m_branch is empty. After processing leaf A, it would become
+ * {nullopt, nullopt, A}. When processing leaf B, an entry at level 2 already
+ * exists, and it would thus be combined with it to produce a level 1 one,
+ * resulting in {nullopt, N1}. Adding C and D takes us to {nullopt, N1, C}
+ * and {nullopt, N1, C, D} respectively. When E is processed, it is combined
+ * with D, and then C, and then N1, to produce the root, resulting in {N0}.
+ *
+ * This structure allows processing with just O(log n) overhead if the leaves
+ * are computed on the fly.
+ *
+ * As an invariant, there can never be nullopt entries at the end. There can
+ * also not be more than 128 entries (as that would mean more than 128 levels
+ * in the tree). The depth of newly added entries will always be at least
+ * equal to the current size of m_branch (otherwise it does not correspond
+ * to a depth-first traversal of a tree). m_branch is only empty if no entries
+ * have ever be processed. m_branch having length 1 corresponds to being done.
+ */
+ std::vector<std::optional<NodeInfo>> m_branch;
+
+ XOnlyPubKey m_internal_key; //!< The internal key, set when finalizing.
+ XOnlyPubKey m_output_key; //!< The output key, computed when finalizing.
+ bool m_parity; //!< The tweak parity, computed when finalizing.
+
+ /** Combine information about a parent Merkle tree node from its child nodes. */
+ static NodeInfo Combine(NodeInfo&& a, NodeInfo&& b);
+ /** Insert information about a node at a certain depth, and propagate information up. */
+ void Insert(NodeInfo&& node, int depth);
+
+public:
+ /** Add a new script at a certain depth in the tree. Add() operations must be called
+ * in depth-first traversal order of binary tree. If track is true, it will be included in
+ * the GetSpendData() output. */
+ TaprootBuilder& Add(int depth, Span<const unsigned char> script, int leaf_version, bool track = true);
+ /** Like Add(), but for a Merkle node with a given hash to the tree. */
+ TaprootBuilder& AddOmitted(int depth, const uint256& hash);
+ /** Finalize the construction. Can only be called when IsComplete() is true.
+ internal_key.IsFullyValid() must be true. */
+ TaprootBuilder& Finalize(const XOnlyPubKey& internal_key);
+
+ /** Return true if so far all input was valid. */
+ bool IsValid() const { return m_valid; }
+ /** Return whether there were either no leaves, or the leaves form a Huffman tree. */
+ bool IsComplete() const { return m_valid && (m_branch.size() == 0 || (m_branch.size() == 1 && m_branch[0].has_value())); }
+ /** Compute scriptPubKey (after Finalize()). */
+ WitnessV1Taproot GetOutput();
+ /** Check if a list of depths is legal (will lead to IsComplete()). */
+ static bool ValidDepths(const std::vector<int>& depths);
+ /** Compute spending data (after Finalize()). */
+ TaprootSpendData GetSpendData() const;
+ /** Returns a vector of tuples representing the depth, leaf version, and script */
+ std::vector<std::tuple<uint8_t, uint8_t, std::vector<unsigned char>>> GetTreeTuples() const;
+ /** Returns true if there are any tapscripts */
+ bool HasScripts() const { return !m_branch.empty(); }
+};
+
+/** Given a TaprootSpendData and the output key, reconstruct its script tree.
+ *
+ * If the output doesn't match the spenddata, or if the data in spenddata is incomplete,
+ * std::nullopt is returned. Otherwise, a vector of (depth, script, leaf_ver) tuples is
+ * returned, corresponding to a depth-first traversal of the script tree.
+ */
+std::optional<std::vector<std::tuple<int, std::vector<unsigned char>, int>>> InferTaprootTree(const TaprootSpendData& spenddata, const XOnlyPubKey& output);
+
/** An interface to be implemented by keystores that support signing. */
class SigningProvider
{
diff --git a/src/script/solver.cpp b/src/script/solver.cpp
new file mode 100644
index 0000000000..1cd388b061
--- /dev/null
+++ b/src/script/solver.cpp
@@ -0,0 +1,223 @@
+// Copyright (c) 2009-2010 Satoshi Nakamoto
+// Copyright (c) 2009-2022 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 <script/solver.h>
+#include <pubkey.h>
+#include <script/interpreter.h>
+#include <script/script.h>
+#include <span.h>
+
+#include <string>
+#include <algorithm>
+
+typedef std::vector<unsigned char> valtype;
+
+std::string GetTxnOutputType(TxoutType t)
+{
+ switch (t) {
+ case TxoutType::NONSTANDARD: return "nonstandard";
+ case TxoutType::PUBKEY: return "pubkey";
+ case TxoutType::PUBKEYHASH: return "pubkeyhash";
+ case TxoutType::SCRIPTHASH: return "scripthash";
+ case TxoutType::MULTISIG: return "multisig";
+ 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);
+}
+
+static bool MatchPayToPubkey(const CScript& script, valtype& pubkey)
+{
+ if (script.size() == CPubKey::SIZE + 2 && script[0] == CPubKey::SIZE && script.back() == OP_CHECKSIG) {
+ pubkey = valtype(script.begin() + 1, script.begin() + CPubKey::SIZE + 1);
+ return CPubKey::ValidSize(pubkey);
+ }
+ if (script.size() == CPubKey::COMPRESSED_SIZE + 2 && script[0] == CPubKey::COMPRESSED_SIZE && script.back() == OP_CHECKSIG) {
+ pubkey = valtype(script.begin() + 1, script.begin() + CPubKey::COMPRESSED_SIZE + 1);
+ return CPubKey::ValidSize(pubkey);
+ }
+ return false;
+}
+
+static bool MatchPayToPubkeyHash(const CScript& script, valtype& pubkeyhash)
+{
+ if (script.size() == 25 && script[0] == OP_DUP && script[1] == OP_HASH160 && script[2] == 20 && script[23] == OP_EQUALVERIFY && script[24] == OP_CHECKSIG) {
+ pubkeyhash = valtype(script.begin () + 3, script.begin() + 23);
+ return true;
+ }
+ return false;
+}
+
+/** Test for "small positive integer" script opcodes - OP_1 through OP_16. */
+static constexpr bool IsSmallInteger(opcodetype opcode)
+{
+ return opcode >= OP_1 && opcode <= OP_16;
+}
+
+/** Retrieve a minimally-encoded number in range [min,max] from an (opcode, data) pair,
+ * whether it's OP_n or through a push. */
+static std::optional<int> GetScriptNumber(opcodetype opcode, valtype data, int min, int max)
+{
+ int count;
+ if (IsSmallInteger(opcode)) {
+ count = CScript::DecodeOP_N(opcode);
+ } else if (IsPushdataOp(opcode)) {
+ if (!CheckMinimalPush(data, opcode)) return {};
+ try {
+ count = CScriptNum(data, /* fRequireMinimal = */ true).getint();
+ } catch (const scriptnum_error&) {
+ return {};
+ }
+ } else {
+ return {};
+ }
+ if (count < min || count > max) return {};
+ return count;
+}
+
+static bool MatchMultisig(const CScript& script, int& required_sigs, std::vector<valtype>& pubkeys)
+{
+ opcodetype opcode;
+ valtype data;
+
+ CScript::const_iterator it = script.begin();
+ if (script.size() < 1 || script.back() != OP_CHECKMULTISIG) return false;
+
+ if (!script.GetOp(it, opcode, data)) return false;
+ auto req_sigs = GetScriptNumber(opcode, data, 1, MAX_PUBKEYS_PER_MULTISIG);
+ if (!req_sigs) return false;
+ required_sigs = *req_sigs;
+ while (script.GetOp(it, opcode, data) && CPubKey::ValidSize(data)) {
+ pubkeys.emplace_back(std::move(data));
+ }
+ auto num_keys = GetScriptNumber(opcode, data, required_sigs, MAX_PUBKEYS_PER_MULTISIG);
+ if (!num_keys) return false;
+ if (pubkeys.size() != static_cast<unsigned long>(*num_keys)) return false;
+
+ return (it + 1 == script.end());
+}
+
+std::optional<std::pair<int, std::vector<Span<const unsigned char>>>> MatchMultiA(const CScript& script)
+{
+ std::vector<Span<const unsigned char>> keyspans;
+
+ // Redundant, but very fast and selective test.
+ if (script.size() == 0 || script[0] != 32 || script.back() != OP_NUMEQUAL) return {};
+
+ // Parse keys
+ auto it = script.begin();
+ while (script.end() - it >= 34) {
+ if (*it != 32) return {};
+ ++it;
+ keyspans.emplace_back(&*it, 32);
+ it += 32;
+ if (*it != (keyspans.size() == 1 ? OP_CHECKSIG : OP_CHECKSIGADD)) return {};
+ ++it;
+ }
+ if (keyspans.size() == 0 || keyspans.size() > MAX_PUBKEYS_PER_MULTI_A) return {};
+
+ // Parse threshold.
+ opcodetype opcode;
+ std::vector<unsigned char> data;
+ if (!script.GetOp(it, opcode, data)) return {};
+ if (it == script.end()) return {};
+ if (*it != OP_NUMEQUAL) return {};
+ ++it;
+ if (it != script.end()) return {};
+ auto threshold = GetScriptNumber(opcode, data, 1, (int)keyspans.size());
+ if (!threshold) return {};
+
+ // Construct result.
+ return std::pair{*threshold, std::move(keyspans)};
+}
+
+TxoutType Solver(const CScript& scriptPubKey, std::vector<std::vector<unsigned char>>& vSolutionsRet)
+{
+ vSolutionsRet.clear();
+
+ // Shortcut for pay-to-script-hash, which are more constrained than the other types:
+ // it is always OP_HASH160 20 [20 byte hash] OP_EQUAL
+ if (scriptPubKey.IsPayToScriptHash())
+ {
+ std::vector<unsigned char> hashBytes(scriptPubKey.begin()+2, scriptPubKey.begin()+22);
+ vSolutionsRet.push_back(hashBytes);
+ return TxoutType::SCRIPTHASH;
+ }
+
+ int witnessversion;
+ std::vector<unsigned char> witnessprogram;
+ if (scriptPubKey.IsWitnessProgram(witnessversion, witnessprogram)) {
+ if (witnessversion == 0 && witnessprogram.size() == WITNESS_V0_KEYHASH_SIZE) {
+ vSolutionsRet.push_back(std::move(witnessprogram));
+ return TxoutType::WITNESS_V0_KEYHASH;
+ }
+ if (witnessversion == 0 && witnessprogram.size() == WITNESS_V0_SCRIPTHASH_SIZE) {
+ vSolutionsRet.push_back(std::move(witnessprogram));
+ return TxoutType::WITNESS_V0_SCRIPTHASH;
+ }
+ if (witnessversion == 1 && witnessprogram.size() == WITNESS_V1_TAPROOT_SIZE) {
+ 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));
+ return TxoutType::WITNESS_UNKNOWN;
+ }
+ return TxoutType::NONSTANDARD;
+ }
+
+ // Provably prunable, data-carrying output
+ //
+ // So long as script passes the IsUnspendable() test and all but the first
+ // byte passes the IsPushOnly() test we don't care what exactly is in the
+ // script.
+ if (scriptPubKey.size() >= 1 && scriptPubKey[0] == OP_RETURN && scriptPubKey.IsPushOnly(scriptPubKey.begin()+1)) {
+ return TxoutType::NULL_DATA;
+ }
+
+ std::vector<unsigned char> data;
+ if (MatchPayToPubkey(scriptPubKey, data)) {
+ vSolutionsRet.push_back(std::move(data));
+ return TxoutType::PUBKEY;
+ }
+
+ if (MatchPayToPubkeyHash(scriptPubKey, data)) {
+ vSolutionsRet.push_back(std::move(data));
+ return TxoutType::PUBKEYHASH;
+ }
+
+ int required;
+ std::vector<std::vector<unsigned char>> keys;
+ if (MatchMultisig(scriptPubKey, required, keys)) {
+ vSolutionsRet.push_back({static_cast<unsigned char>(required)}); // safe as required is in range 1..20
+ vSolutionsRet.insert(vSolutionsRet.end(), keys.begin(), keys.end());
+ vSolutionsRet.push_back({static_cast<unsigned char>(keys.size())}); // safe as size is in range 1..20
+ return TxoutType::MULTISIG;
+ }
+
+ vSolutionsRet.clear();
+ return TxoutType::NONSTANDARD;
+}
+
+CScript GetScriptForRawPubKey(const CPubKey& pubKey)
+{
+ return CScript() << std::vector<unsigned char>(pubKey.begin(), pubKey.end()) << OP_CHECKSIG;
+}
+
+CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys)
+{
+ CScript script;
+
+ script << nRequired;
+ for (const CPubKey& key : keys)
+ script << ToByteVector(key);
+ script << keys.size() << OP_CHECKMULTISIG;
+
+ return script;
+}
diff --git a/src/script/solver.h b/src/script/solver.h
new file mode 100644
index 0000000000..dc8f4c357d
--- /dev/null
+++ b/src/script/solver.h
@@ -0,0 +1,66 @@
+// Copyright (c) 2009-2010 Satoshi Nakamoto
+// Copyright (c) 2009-2022 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+// The Solver functions are used by policy and the wallet, but not consensus.
+
+#ifndef BITCOIN_SCRIPT_SOLVER_H
+#define BITCOIN_SCRIPT_SOLVER_H
+
+#include <attributes.h>
+#include <script/script.h>
+
+#include <string>
+#include <optional>
+#include <utility>
+#include <vector>
+
+class CPubKey;
+template <typename C> class Span;
+
+enum class TxoutType {
+ NONSTANDARD,
+ // 'standard' transaction types:
+ PUBKEY,
+ PUBKEYHASH,
+ SCRIPTHASH,
+ MULTISIG,
+ 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
+};
+
+/** Get the name of a TxoutType as a string */
+std::string GetTxnOutputType(TxoutType t);
+
+constexpr bool IsPushdataOp(opcodetype opcode)
+{
+ return opcode > OP_FALSE && opcode <= OP_PUSHDATA4;
+}
+
+/**
+ * Parse a scriptPubKey and identify script type for standard scripts. If
+ * successful, returns script type and parsed pubkeys or hashes, depending on
+ * the type. For example, for a P2SH script, vSolutionsRet will contain the
+ * script hash, for P2PKH it will contain the key hash, etc.
+ *
+ * @param[in] scriptPubKey Script to parse
+ * @param[out] vSolutionsRet Vector of parsed pubkeys and hashes
+ * @return The script type. TxoutType::NONSTANDARD represents a failed solve.
+ */
+TxoutType Solver(const CScript& scriptPubKey, std::vector<std::vector<unsigned char>>& vSolutionsRet);
+
+/** Generate a P2PK script for the given pubkey. */
+CScript GetScriptForRawPubKey(const CPubKey& pubkey);
+
+/** Determine if script is a "multi_a" script. Returns (threshold, keyspans) if so, and nullopt otherwise.
+ * The keyspans refer to bytes in the passed script. */
+std::optional<std::pair<int, std::vector<Span<const unsigned char>>>> MatchMultiA(const CScript& script LIFETIMEBOUND);
+
+/** Generate a multisig script. */
+CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys);
+
+#endif // BITCOIN_SCRIPT_SOLVER_H
diff --git a/src/script/standard.cpp b/src/script/standard.cpp
deleted file mode 100644
index 7c4a05b6e6..0000000000
--- a/src/script/standard.cpp
+++ /dev/null
@@ -1,653 +0,0 @@
-// Copyright (c) 2009-2010 Satoshi Nakamoto
-// Copyright (c) 2009-2022 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 <script/standard.h>
-
-#include <crypto/sha256.h>
-#include <hash.h>
-#include <pubkey.h>
-#include <script/interpreter.h>
-#include <script/script.h>
-#include <util/strencodings.h>
-
-#include <string>
-
-typedef std::vector<unsigned char> valtype;
-
-CScriptID::CScriptID(const CScript& in) : BaseHash(Hash160(in)) {}
-CScriptID::CScriptID(const ScriptHash& in) : BaseHash(static_cast<uint160>(in)) {}
-
-ScriptHash::ScriptHash(const CScript& in) : BaseHash(Hash160(in)) {}
-ScriptHash::ScriptHash(const CScriptID& in) : BaseHash(static_cast<uint160>(in)) {}
-
-PKHash::PKHash(const CPubKey& pubkey) : BaseHash(pubkey.GetID()) {}
-PKHash::PKHash(const CKeyID& pubkey_id) : BaseHash(pubkey_id) {}
-
-WitnessV0KeyHash::WitnessV0KeyHash(const CPubKey& pubkey) : BaseHash(pubkey.GetID()) {}
-WitnessV0KeyHash::WitnessV0KeyHash(const PKHash& pubkey_hash) : BaseHash(static_cast<uint160>(pubkey_hash)) {}
-
-CKeyID ToKeyID(const PKHash& key_hash)
-{
- return CKeyID{static_cast<uint160>(key_hash)};
-}
-
-CKeyID ToKeyID(const WitnessV0KeyHash& key_hash)
-{
- return CKeyID{static_cast<uint160>(key_hash)};
-}
-
-WitnessV0ScriptHash::WitnessV0ScriptHash(const CScript& in)
-{
- CSHA256().Write(in.data(), in.size()).Finalize(begin());
-}
-
-std::string GetTxnOutputType(TxoutType t)
-{
- switch (t) {
- case TxoutType::NONSTANDARD: return "nonstandard";
- case TxoutType::PUBKEY: return "pubkey";
- case TxoutType::PUBKEYHASH: return "pubkeyhash";
- case TxoutType::SCRIPTHASH: return "scripthash";
- case TxoutType::MULTISIG: return "multisig";
- 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);
-}
-
-static bool MatchPayToPubkey(const CScript& script, valtype& pubkey)
-{
- if (script.size() == CPubKey::SIZE + 2 && script[0] == CPubKey::SIZE && script.back() == OP_CHECKSIG) {
- pubkey = valtype(script.begin() + 1, script.begin() + CPubKey::SIZE + 1);
- return CPubKey::ValidSize(pubkey);
- }
- if (script.size() == CPubKey::COMPRESSED_SIZE + 2 && script[0] == CPubKey::COMPRESSED_SIZE && script.back() == OP_CHECKSIG) {
- pubkey = valtype(script.begin() + 1, script.begin() + CPubKey::COMPRESSED_SIZE + 1);
- return CPubKey::ValidSize(pubkey);
- }
- return false;
-}
-
-static bool MatchPayToPubkeyHash(const CScript& script, valtype& pubkeyhash)
-{
- if (script.size() == 25 && script[0] == OP_DUP && script[1] == OP_HASH160 && script[2] == 20 && script[23] == OP_EQUALVERIFY && script[24] == OP_CHECKSIG) {
- pubkeyhash = valtype(script.begin () + 3, script.begin() + 23);
- return true;
- }
- return false;
-}
-
-/** Test for "small positive integer" script opcodes - OP_1 through OP_16. */
-static constexpr bool IsSmallInteger(opcodetype opcode)
-{
- return opcode >= OP_1 && opcode <= OP_16;
-}
-
-/** Retrieve a minimally-encoded number in range [min,max] from an (opcode, data) pair,
- * whether it's OP_n or through a push. */
-static std::optional<int> GetScriptNumber(opcodetype opcode, valtype data, int min, int max)
-{
- int count;
- if (IsSmallInteger(opcode)) {
- count = CScript::DecodeOP_N(opcode);
- } else if (IsPushdataOp(opcode)) {
- if (!CheckMinimalPush(data, opcode)) return {};
- try {
- count = CScriptNum(data, /* fRequireMinimal = */ true).getint();
- } catch (const scriptnum_error&) {
- return {};
- }
- } else {
- return {};
- }
- if (count < min || count > max) return {};
- return count;
-}
-
-static bool MatchMultisig(const CScript& script, int& required_sigs, std::vector<valtype>& pubkeys)
-{
- opcodetype opcode;
- valtype data;
-
- CScript::const_iterator it = script.begin();
- if (script.size() < 1 || script.back() != OP_CHECKMULTISIG) return false;
-
- if (!script.GetOp(it, opcode, data)) return false;
- auto req_sigs = GetScriptNumber(opcode, data, 1, MAX_PUBKEYS_PER_MULTISIG);
- if (!req_sigs) return false;
- required_sigs = *req_sigs;
- while (script.GetOp(it, opcode, data) && CPubKey::ValidSize(data)) {
- pubkeys.emplace_back(std::move(data));
- }
- auto num_keys = GetScriptNumber(opcode, data, required_sigs, MAX_PUBKEYS_PER_MULTISIG);
- if (!num_keys) return false;
- if (pubkeys.size() != static_cast<unsigned long>(*num_keys)) return false;
-
- return (it + 1 == script.end());
-}
-
-std::optional<std::pair<int, std::vector<Span<const unsigned char>>>> MatchMultiA(const CScript& script)
-{
- std::vector<Span<const unsigned char>> keyspans;
-
- // Redundant, but very fast and selective test.
- if (script.size() == 0 || script[0] != 32 || script.back() != OP_NUMEQUAL) return {};
-
- // Parse keys
- auto it = script.begin();
- while (script.end() - it >= 34) {
- if (*it != 32) return {};
- ++it;
- keyspans.emplace_back(&*it, 32);
- it += 32;
- if (*it != (keyspans.size() == 1 ? OP_CHECKSIG : OP_CHECKSIGADD)) return {};
- ++it;
- }
- if (keyspans.size() == 0 || keyspans.size() > MAX_PUBKEYS_PER_MULTI_A) return {};
-
- // Parse threshold.
- opcodetype opcode;
- std::vector<unsigned char> data;
- if (!script.GetOp(it, opcode, data)) return {};
- if (it == script.end()) return {};
- if (*it != OP_NUMEQUAL) return {};
- ++it;
- if (it != script.end()) return {};
- auto threshold = GetScriptNumber(opcode, data, 1, (int)keyspans.size());
- if (!threshold) return {};
-
- // Construct result.
- return std::pair{*threshold, std::move(keyspans)};
-}
-
-TxoutType Solver(const CScript& scriptPubKey, std::vector<std::vector<unsigned char>>& vSolutionsRet)
-{
- vSolutionsRet.clear();
-
- // Shortcut for pay-to-script-hash, which are more constrained than the other types:
- // it is always OP_HASH160 20 [20 byte hash] OP_EQUAL
- if (scriptPubKey.IsPayToScriptHash())
- {
- std::vector<unsigned char> hashBytes(scriptPubKey.begin()+2, scriptPubKey.begin()+22);
- vSolutionsRet.push_back(hashBytes);
- return TxoutType::SCRIPTHASH;
- }
-
- int witnessversion;
- std::vector<unsigned char> witnessprogram;
- if (scriptPubKey.IsWitnessProgram(witnessversion, witnessprogram)) {
- if (witnessversion == 0 && witnessprogram.size() == WITNESS_V0_KEYHASH_SIZE) {
- vSolutionsRet.push_back(std::move(witnessprogram));
- return TxoutType::WITNESS_V0_KEYHASH;
- }
- if (witnessversion == 0 && witnessprogram.size() == WITNESS_V0_SCRIPTHASH_SIZE) {
- vSolutionsRet.push_back(std::move(witnessprogram));
- return TxoutType::WITNESS_V0_SCRIPTHASH;
- }
- if (witnessversion == 1 && witnessprogram.size() == WITNESS_V1_TAPROOT_SIZE) {
- 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));
- return TxoutType::WITNESS_UNKNOWN;
- }
- return TxoutType::NONSTANDARD;
- }
-
- // Provably prunable, data-carrying output
- //
- // So long as script passes the IsUnspendable() test and all but the first
- // byte passes the IsPushOnly() test we don't care what exactly is in the
- // script.
- if (scriptPubKey.size() >= 1 && scriptPubKey[0] == OP_RETURN && scriptPubKey.IsPushOnly(scriptPubKey.begin()+1)) {
- return TxoutType::NULL_DATA;
- }
-
- std::vector<unsigned char> data;
- if (MatchPayToPubkey(scriptPubKey, data)) {
- vSolutionsRet.push_back(std::move(data));
- return TxoutType::PUBKEY;
- }
-
- if (MatchPayToPubkeyHash(scriptPubKey, data)) {
- vSolutionsRet.push_back(std::move(data));
- return TxoutType::PUBKEYHASH;
- }
-
- int required;
- std::vector<std::vector<unsigned char>> keys;
- if (MatchMultisig(scriptPubKey, required, keys)) {
- vSolutionsRet.push_back({static_cast<unsigned char>(required)}); // safe as required is in range 1..20
- vSolutionsRet.insert(vSolutionsRet.end(), keys.begin(), keys.end());
- vSolutionsRet.push_back({static_cast<unsigned char>(keys.size())}); // safe as size is in range 1..20
- return TxoutType::MULTISIG;
- }
-
- vSolutionsRet.clear();
- return TxoutType::NONSTANDARD;
-}
-
-bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet)
-{
- std::vector<valtype> vSolutions;
- TxoutType whichType = Solver(scriptPubKey, vSolutions);
-
- switch (whichType) {
- case TxoutType::PUBKEY: {
- CPubKey pubKey(vSolutions[0]);
- if (!pubKey.IsValid())
- return false;
-
- addressRet = PKHash(pubKey);
- return true;
- }
- case TxoutType::PUBKEYHASH: {
- addressRet = PKHash(uint160(vSolutions[0]));
- return true;
- }
- case TxoutType::SCRIPTHASH: {
- addressRet = ScriptHash(uint160(vSolutions[0]));
- return true;
- }
- case TxoutType::WITNESS_V0_KEYHASH: {
- WitnessV0KeyHash hash;
- std::copy(vSolutions[0].begin(), vSolutions[0].end(), hash.begin());
- addressRet = hash;
- return true;
- }
- case TxoutType::WITNESS_V0_SCRIPTHASH: {
- WitnessV0ScriptHash hash;
- std::copy(vSolutions[0].begin(), vSolutions[0].end(), hash.begin());
- addressRet = hash;
- return true;
- }
- case TxoutType::WITNESS_V1_TAPROOT: {
- WitnessV1Taproot tap;
- std::copy(vSolutions[0].begin(), vSolutions[0].end(), tap.begin());
- addressRet = tap;
- return true;
- }
- case TxoutType::WITNESS_UNKNOWN: {
- WitnessUnknown unk;
- unk.version = vSolutions[0][0];
- std::copy(vSolutions[1].begin(), vSolutions[1].end(), unk.program);
- unk.length = vSolutions[1].size();
- addressRet = unk;
- return true;
- }
- case TxoutType::MULTISIG:
- case TxoutType::NULL_DATA:
- case TxoutType::NONSTANDARD:
- return false;
- } // no default case, so the compiler can warn about missing cases
- assert(false);
-}
-
-namespace {
-class CScriptVisitor
-{
-public:
- CScript operator()(const CNoDestination& dest) const
- {
- return CScript();
- }
-
- CScript operator()(const PKHash& keyID) const
- {
- return CScript() << OP_DUP << OP_HASH160 << ToByteVector(keyID) << OP_EQUALVERIFY << OP_CHECKSIG;
- }
-
- CScript operator()(const ScriptHash& scriptID) const
- {
- return CScript() << OP_HASH160 << ToByteVector(scriptID) << OP_EQUAL;
- }
-
- CScript operator()(const WitnessV0KeyHash& id) const
- {
- return CScript() << OP_0 << ToByteVector(id);
- }
-
- CScript operator()(const WitnessV0ScriptHash& id) const
- {
- return CScript() << OP_0 << ToByteVector(id);
- }
-
- CScript operator()(const WitnessV1Taproot& tap) const
- {
- return CScript() << OP_1 << ToByteVector(tap);
- }
-
- CScript operator()(const WitnessUnknown& id) const
- {
- return CScript() << CScript::EncodeOP_N(id.version) << std::vector<unsigned char>(id.program, id.program + id.length);
- }
-};
-} // namespace
-
-CScript GetScriptForDestination(const CTxDestination& dest)
-{
- return std::visit(CScriptVisitor(), dest);
-}
-
-CScript GetScriptForRawPubKey(const CPubKey& pubKey)
-{
- return CScript() << std::vector<unsigned char>(pubKey.begin(), pubKey.end()) << OP_CHECKSIG;
-}
-
-CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys)
-{
- CScript script;
-
- script << nRequired;
- for (const CPubKey& key : keys)
- script << ToByteVector(key);
- script << keys.size() << OP_CHECKMULTISIG;
-
- return script;
-}
-
-bool IsValidDestination(const CTxDestination& dest) {
- return dest.index() != 0;
-}
-
-/*static*/ TaprootBuilder::NodeInfo TaprootBuilder::Combine(NodeInfo&& a, NodeInfo&& b)
-{
- NodeInfo ret;
- /* Iterate over all tracked leaves in a, add b's hash to their Merkle branch, and move them to ret. */
- for (auto& leaf : a.leaves) {
- leaf.merkle_branch.push_back(b.hash);
- ret.leaves.emplace_back(std::move(leaf));
- }
- /* Iterate over all tracked leaves in b, add a's hash to their Merkle branch, and move them to ret. */
- for (auto& leaf : b.leaves) {
- leaf.merkle_branch.push_back(a.hash);
- ret.leaves.emplace_back(std::move(leaf));
- }
- ret.hash = ComputeTapbranchHash(a.hash, b.hash);
- return ret;
-}
-
-void TaprootSpendData::Merge(TaprootSpendData other)
-{
- // TODO: figure out how to better deal with conflicting information
- // being merged.
- if (internal_key.IsNull() && !other.internal_key.IsNull()) {
- internal_key = other.internal_key;
- }
- if (merkle_root.IsNull() && !other.merkle_root.IsNull()) {
- merkle_root = other.merkle_root;
- }
- for (auto& [key, control_blocks] : other.scripts) {
- scripts[key].merge(std::move(control_blocks));
- }
-}
-
-void TaprootBuilder::Insert(TaprootBuilder::NodeInfo&& node, int depth)
-{
- assert(depth >= 0 && (size_t)depth <= TAPROOT_CONTROL_MAX_NODE_COUNT);
- /* We cannot insert a leaf at a lower depth while a deeper branch is unfinished. Doing
- * so would mean the Add() invocations do not correspond to a DFS traversal of a
- * binary tree. */
- if ((size_t)depth + 1 < m_branch.size()) {
- m_valid = false;
- return;
- }
- /* As long as an entry in the branch exists at the specified depth, combine it and propagate up.
- * The 'node' variable is overwritten here with the newly combined node. */
- while (m_valid && m_branch.size() > (size_t)depth && m_branch[depth].has_value()) {
- node = Combine(std::move(node), std::move(*m_branch[depth]));
- m_branch.pop_back();
- if (depth == 0) m_valid = false; /* Can't propagate further up than the root */
- --depth;
- }
- if (m_valid) {
- /* Make sure the branch is big enough to place the new node. */
- if (m_branch.size() <= (size_t)depth) m_branch.resize((size_t)depth + 1);
- assert(!m_branch[depth].has_value());
- m_branch[depth] = std::move(node);
- }
-}
-
-/*static*/ bool TaprootBuilder::ValidDepths(const std::vector<int>& depths)
-{
- std::vector<bool> branch;
- for (int depth : depths) {
- // This inner loop corresponds to effectively the same logic on branch
- // as what Insert() performs on the m_branch variable. Instead of
- // storing a NodeInfo object, just remember whether or not there is one
- // at that depth.
- if (depth < 0 || (size_t)depth > TAPROOT_CONTROL_MAX_NODE_COUNT) return false;
- if ((size_t)depth + 1 < branch.size()) return false;
- while (branch.size() > (size_t)depth && branch[depth]) {
- branch.pop_back();
- if (depth == 0) return false;
- --depth;
- }
- if (branch.size() <= (size_t)depth) branch.resize((size_t)depth + 1);
- assert(!branch[depth]);
- branch[depth] = true;
- }
- // And this check corresponds to the IsComplete() check on m_branch.
- return branch.size() == 0 || (branch.size() == 1 && branch[0]);
-}
-
-TaprootBuilder& TaprootBuilder::Add(int depth, Span<const unsigned char> script, int leaf_version, bool track)
-{
- assert((leaf_version & ~TAPROOT_LEAF_MASK) == 0);
- if (!IsValid()) return *this;
- /* Construct NodeInfo object with leaf hash and (if track is true) also leaf information. */
- NodeInfo node;
- node.hash = ComputeTapleafHash(leaf_version, script);
- if (track) node.leaves.emplace_back(LeafInfo{std::vector<unsigned char>(script.begin(), script.end()), leaf_version, {}});
- /* Insert into the branch. */
- Insert(std::move(node), depth);
- return *this;
-}
-
-TaprootBuilder& TaprootBuilder::AddOmitted(int depth, const uint256& hash)
-{
- if (!IsValid()) return *this;
- /* Construct NodeInfo object with the hash directly, and insert it into the branch. */
- NodeInfo node;
- node.hash = hash;
- Insert(std::move(node), depth);
- return *this;
-}
-
-TaprootBuilder& TaprootBuilder::Finalize(const XOnlyPubKey& internal_key)
-{
- /* Can only call this function when IsComplete() is true. */
- assert(IsComplete());
- m_internal_key = internal_key;
- auto ret = m_internal_key.CreateTapTweak(m_branch.size() == 0 ? nullptr : &m_branch[0]->hash);
- assert(ret.has_value());
- std::tie(m_output_key, m_parity) = *ret;
- return *this;
-}
-
-WitnessV1Taproot TaprootBuilder::GetOutput() { return WitnessV1Taproot{m_output_key}; }
-
-TaprootSpendData TaprootBuilder::GetSpendData() const
-{
- assert(IsComplete());
- assert(m_output_key.IsFullyValid());
- TaprootSpendData spd;
- spd.merkle_root = m_branch.size() == 0 ? uint256() : m_branch[0]->hash;
- spd.internal_key = m_internal_key;
- if (m_branch.size()) {
- // If any script paths exist, they have been combined into the root m_branch[0]
- // by now. Compute the control block for each of its tracked leaves, and put them in
- // spd.scripts.
- for (const auto& leaf : m_branch[0]->leaves) {
- std::vector<unsigned char> control_block;
- control_block.resize(TAPROOT_CONTROL_BASE_SIZE + TAPROOT_CONTROL_NODE_SIZE * leaf.merkle_branch.size());
- control_block[0] = leaf.leaf_version | (m_parity ? 1 : 0);
- std::copy(m_internal_key.begin(), m_internal_key.end(), control_block.begin() + 1);
- if (leaf.merkle_branch.size()) {
- std::copy(leaf.merkle_branch[0].begin(),
- leaf.merkle_branch[0].begin() + TAPROOT_CONTROL_NODE_SIZE * leaf.merkle_branch.size(),
- control_block.begin() + TAPROOT_CONTROL_BASE_SIZE);
- }
- spd.scripts[{leaf.script, leaf.leaf_version}].insert(std::move(control_block));
- }
- }
- return spd;
-}
-
-std::optional<std::vector<std::tuple<int, std::vector<unsigned char>, int>>> InferTaprootTree(const TaprootSpendData& spenddata, const XOnlyPubKey& output)
-{
- // Verify that the output matches the assumed Merkle root and internal key.
- auto tweak = spenddata.internal_key.CreateTapTweak(spenddata.merkle_root.IsNull() ? nullptr : &spenddata.merkle_root);
- if (!tweak || tweak->first != output) return std::nullopt;
- // If the Merkle root is 0, the tree is empty, and we're done.
- std::vector<std::tuple<int, std::vector<unsigned char>, int>> ret;
- if (spenddata.merkle_root.IsNull()) return ret;
-
- /** Data structure to represent the nodes of the tree we're going to build. */
- struct TreeNode {
- /** Hash of this node, if known; 0 otherwise. */
- uint256 hash;
- /** The left and right subtrees (note that their order is irrelevant). */
- std::unique_ptr<TreeNode> sub[2];
- /** If this is known to be a leaf node, a pointer to the (script, leaf_ver) pair.
- * nullptr otherwise. */
- const std::pair<std::vector<unsigned char>, int>* leaf = nullptr;
- /** Whether or not this node has been explored (is known to be a leaf, or known to have children). */
- bool explored = false;
- /** Whether or not this node is an inner node (unknown until explored = true). */
- bool inner;
- /** Whether or not we have produced output for this subtree. */
- bool done = false;
- };
-
- // Build tree from the provided branches.
- TreeNode root;
- root.hash = spenddata.merkle_root;
- for (const auto& [key, control_blocks] : spenddata.scripts) {
- const auto& [script, leaf_ver] = key;
- for (const auto& control : control_blocks) {
- // Skip script records with nonsensical leaf version.
- if (leaf_ver < 0 || leaf_ver >= 0x100 || leaf_ver & 1) continue;
- // Skip script records with invalid control block sizes.
- if (control.size() < TAPROOT_CONTROL_BASE_SIZE || control.size() > TAPROOT_CONTROL_MAX_SIZE ||
- ((control.size() - TAPROOT_CONTROL_BASE_SIZE) % TAPROOT_CONTROL_NODE_SIZE) != 0) continue;
- // Skip script records that don't match the control block.
- if ((control[0] & TAPROOT_LEAF_MASK) != leaf_ver) continue;
- // Skip script records that don't match the provided Merkle root.
- const uint256 leaf_hash = ComputeTapleafHash(leaf_ver, script);
- const uint256 merkle_root = ComputeTaprootMerkleRoot(control, leaf_hash);
- if (merkle_root != spenddata.merkle_root) continue;
-
- TreeNode* node = &root;
- size_t levels = (control.size() - TAPROOT_CONTROL_BASE_SIZE) / TAPROOT_CONTROL_NODE_SIZE;
- for (size_t depth = 0; depth < levels; ++depth) {
- // Can't descend into a node which we already know is a leaf.
- if (node->explored && !node->inner) return std::nullopt;
-
- // Extract partner hash from Merkle branch in control block.
- uint256 hash;
- std::copy(control.begin() + TAPROOT_CONTROL_BASE_SIZE + (levels - 1 - depth) * TAPROOT_CONTROL_NODE_SIZE,
- control.begin() + TAPROOT_CONTROL_BASE_SIZE + (levels - depth) * TAPROOT_CONTROL_NODE_SIZE,
- hash.begin());
-
- if (node->sub[0]) {
- // Descend into the existing left or right branch.
- bool desc = false;
- for (int i = 0; i < 2; ++i) {
- if (node->sub[i]->hash == hash || (node->sub[i]->hash.IsNull() && node->sub[1-i]->hash != hash)) {
- node->sub[i]->hash = hash;
- node = &*node->sub[1-i];
- desc = true;
- break;
- }
- }
- if (!desc) return std::nullopt; // This probably requires a hash collision to hit.
- } else {
- // We're in an unexplored node. Create subtrees and descend.
- node->explored = true;
- node->inner = true;
- node->sub[0] = std::make_unique<TreeNode>();
- node->sub[1] = std::make_unique<TreeNode>();
- node->sub[1]->hash = hash;
- node = &*node->sub[0];
- }
- }
- // Cannot turn a known inner node into a leaf.
- if (node->sub[0]) return std::nullopt;
- node->explored = true;
- node->inner = false;
- node->leaf = &key;
- node->hash = leaf_hash;
- }
- }
-
- // Recursive processing to turn the tree into flattened output. Use an explicit stack here to avoid
- // overflowing the call stack (the tree may be 128 levels deep).
- std::vector<TreeNode*> stack{&root};
- while (!stack.empty()) {
- TreeNode& node = *stack.back();
- if (!node.explored) {
- // Unexplored node, which means the tree is incomplete.
- return std::nullopt;
- } else if (!node.inner) {
- // Leaf node; produce output.
- ret.emplace_back(stack.size() - 1, node.leaf->first, node.leaf->second);
- node.done = true;
- stack.pop_back();
- } else if (node.sub[0]->done && !node.sub[1]->done && !node.sub[1]->explored && !node.sub[1]->hash.IsNull() &&
- ComputeTapbranchHash(node.sub[1]->hash, node.sub[1]->hash) == node.hash) {
- // Whenever there are nodes with two identical subtrees under it, we run into a problem:
- // the control blocks for the leaves underneath those will be identical as well, and thus
- // they will all be matched to the same path in the tree. The result is that at the location
- // where the duplicate occurred, the left child will contain a normal tree that can be explored
- // and processed, but the right one will remain unexplored.
- //
- // This situation can be detected, by encountering an inner node with unexplored right subtree
- // with known hash, and H_TapBranch(hash, hash) is equal to the parent node (this node)'s hash.
- //
- // To deal with this, simply process the left tree a second time (set its done flag to false;
- // noting that the done flag of its children have already been set to false after processing
- // those). To avoid ending up in an infinite loop, set the done flag of the right (unexplored)
- // subtree to true.
- node.sub[0]->done = false;
- node.sub[1]->done = true;
- } else if (node.sub[0]->done && node.sub[1]->done) {
- // An internal node which we're finished with.
- node.sub[0]->done = false;
- node.sub[1]->done = false;
- node.done = true;
- stack.pop_back();
- } else if (!node.sub[0]->done) {
- // An internal node whose left branch hasn't been processed yet. Do so first.
- stack.push_back(&*node.sub[0]);
- } else if (!node.sub[1]->done) {
- // An internal node whose right branch hasn't been processed yet. Do so first.
- stack.push_back(&*node.sub[1]);
- }
- }
-
- return ret;
-}
-
-std::vector<std::tuple<uint8_t, uint8_t, std::vector<unsigned char>>> TaprootBuilder::GetTreeTuples() const
-{
- assert(IsComplete());
- std::vector<std::tuple<uint8_t, uint8_t, std::vector<unsigned char>>> tuples;
- if (m_branch.size()) {
- const auto& leaves = m_branch[0]->leaves;
- for (const auto& leaf : leaves) {
- assert(leaf.merkle_branch.size() <= TAPROOT_CONTROL_MAX_NODE_COUNT);
- uint8_t depth = (uint8_t)leaf.merkle_branch.size();
- uint8_t leaf_ver = (uint8_t)leaf.leaf_version;
- tuples.push_back(std::make_tuple(depth, leaf_ver, leaf.script));
- }
- }
- return tuples;
-}
diff --git a/src/script/standard.h b/src/script/standard.h
deleted file mode 100644
index 18cf5c8c88..0000000000
--- a/src/script/standard.h
+++ /dev/null
@@ -1,330 +0,0 @@
-// Copyright (c) 2009-2010 Satoshi Nakamoto
-// Copyright (c) 2009-2022 The Bitcoin Core developers
-// Distributed under the MIT software license, see the accompanying
-// file COPYING or http://www.opensource.org/licenses/mit-license.php.
-
-#ifndef BITCOIN_SCRIPT_STANDARD_H
-#define BITCOIN_SCRIPT_STANDARD_H
-
-#include <attributes.h>
-#include <pubkey.h>
-#include <script/interpreter.h>
-#include <uint256.h>
-#include <util/hash_type.h>
-
-#include <map>
-#include <string>
-#include <variant>
-
-static const bool DEFAULT_ACCEPT_DATACARRIER = true;
-
-class CKeyID;
-class CScript;
-struct ScriptHash;
-
-/** A reference to a CScript: the Hash160 of its serialization (see script.h) */
-class CScriptID : public BaseHash<uint160>
-{
-public:
- CScriptID() : BaseHash() {}
- explicit CScriptID(const CScript& in);
- explicit CScriptID(const uint160& in) : BaseHash(in) {}
- explicit CScriptID(const ScriptHash& in);
-};
-
-/**
- * Default setting for -datacarriersize. 80 bytes of data, +1 for OP_RETURN,
- * +2 for the pushdata opcodes.
- */
-static const unsigned int MAX_OP_RETURN_RELAY = 83;
-
-/**
- * Mandatory script verification flags that all new blocks must comply with for
- * them to be valid. (but old blocks may not comply with) Currently just P2SH,
- * but in the future other flags may be added.
- *
- * Failing one of these tests may trigger a DoS ban - see CheckInputScripts() for
- * details.
- */
-static const unsigned int MANDATORY_SCRIPT_VERIFY_FLAGS = SCRIPT_VERIFY_P2SH;
-
-enum class TxoutType {
- NONSTANDARD,
- // 'standard' transaction types:
- PUBKEY,
- PUBKEYHASH,
- SCRIPTHASH,
- MULTISIG,
- 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
-};
-
-class CNoDestination {
-public:
- friend bool operator==(const CNoDestination &a, const CNoDestination &b) { return true; }
- friend bool operator<(const CNoDestination &a, const CNoDestination &b) { return true; }
-};
-
-struct PKHash : public BaseHash<uint160>
-{
- PKHash() : BaseHash() {}
- explicit PKHash(const uint160& hash) : BaseHash(hash) {}
- explicit PKHash(const CPubKey& pubkey);
- explicit PKHash(const CKeyID& pubkey_id);
-};
-CKeyID ToKeyID(const PKHash& key_hash);
-
-struct WitnessV0KeyHash;
-struct ScriptHash : public BaseHash<uint160>
-{
- ScriptHash() : BaseHash() {}
- // These don't do what you'd expect.
- // Use ScriptHash(GetScriptForDestination(...)) instead.
- explicit ScriptHash(const WitnessV0KeyHash& hash) = delete;
- explicit ScriptHash(const PKHash& hash) = delete;
-
- explicit ScriptHash(const uint160& hash) : BaseHash(hash) {}
- explicit ScriptHash(const CScript& script);
- explicit ScriptHash(const CScriptID& script);
-};
-
-struct WitnessV0ScriptHash : public BaseHash<uint256>
-{
- WitnessV0ScriptHash() : BaseHash() {}
- explicit WitnessV0ScriptHash(const uint256& hash) : BaseHash(hash) {}
- explicit WitnessV0ScriptHash(const CScript& script);
-};
-
-struct WitnessV0KeyHash : public BaseHash<uint160>
-{
- WitnessV0KeyHash() : BaseHash() {}
- explicit WitnessV0KeyHash(const uint160& hash) : BaseHash(hash) {}
- explicit WitnessV0KeyHash(const CPubKey& pubkey);
- explicit WitnessV0KeyHash(const PKHash& pubkey_hash);
-};
-CKeyID ToKeyID(const WitnessV0KeyHash& key_hash);
-
-struct WitnessV1Taproot : public XOnlyPubKey
-{
- WitnessV1Taproot() : XOnlyPubKey() {}
- explicit WitnessV1Taproot(const XOnlyPubKey& xpk) : XOnlyPubKey(xpk) {}
-};
-
-//! CTxDestination subtype to encode any future Witness version
-struct WitnessUnknown
-{
- unsigned int version;
- unsigned int length;
- unsigned char program[40];
-
- friend bool operator==(const WitnessUnknown& w1, const WitnessUnknown& w2) {
- if (w1.version != w2.version) return false;
- if (w1.length != w2.length) return false;
- return std::equal(w1.program, w1.program + w1.length, w2.program);
- }
-
- friend bool operator<(const WitnessUnknown& w1, const WitnessUnknown& w2) {
- if (w1.version < w2.version) return true;
- if (w1.version > w2.version) return false;
- if (w1.length < w2.length) return true;
- if (w1.length > w2.length) return false;
- return std::lexicographical_compare(w1.program, w1.program + w1.length, w2.program, w2.program + w2.length);
- }
-};
-
-/**
- * A txout script template with a specific destination. It is either:
- * * CNoDestination: no destination set
- * * PKHash: TxoutType::PUBKEYHASH destination (P2PKH)
- * * ScriptHash: TxoutType::SCRIPTHASH destination (P2SH)
- * * WitnessV0ScriptHash: TxoutType::WITNESS_V0_SCRIPTHASH destination (P2WSH)
- * * WitnessV0KeyHash: TxoutType::WITNESS_V0_KEYHASH destination (P2WPKH)
- * * WitnessV1Taproot: TxoutType::WITNESS_V1_TAPROOT destination (P2TR)
- * * WitnessUnknown: TxoutType::WITNESS_UNKNOWN destination (P2W???)
- * A CTxDestination is the internal data type encoded in a bitcoin address
- */
-using CTxDestination = std::variant<CNoDestination, PKHash, ScriptHash, WitnessV0ScriptHash, WitnessV0KeyHash, WitnessV1Taproot, WitnessUnknown>;
-
-/** Check whether a CTxDestination is a CNoDestination. */
-bool IsValidDestination(const CTxDestination& dest);
-
-/** Get the name of a TxoutType as a string */
-std::string GetTxnOutputType(TxoutType t);
-
-constexpr bool IsPushdataOp(opcodetype opcode)
-{
- return opcode > OP_FALSE && opcode <= OP_PUSHDATA4;
-}
-
-/**
- * Parse a scriptPubKey and identify script type for standard scripts. If
- * successful, returns script type and parsed pubkeys or hashes, depending on
- * the type. For example, for a P2SH script, vSolutionsRet will contain the
- * script hash, for P2PKH it will contain the key hash, etc.
- *
- * @param[in] scriptPubKey Script to parse
- * @param[out] vSolutionsRet Vector of parsed pubkeys and hashes
- * @return The script type. TxoutType::NONSTANDARD represents a failed solve.
- */
-TxoutType Solver(const CScript& scriptPubKey, std::vector<std::vector<unsigned char>>& vSolutionsRet);
-
-/**
- * Parse a standard scriptPubKey for the destination address. Assigns result to
- * the addressRet parameter and returns true if successful. Currently only works for P2PK,
- * P2PKH, P2SH, P2WPKH, and P2WSH scripts.
- */
-bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet);
-
-/**
- * Generate a Bitcoin scriptPubKey for the given CTxDestination. Returns a P2PKH
- * script for a CKeyID destination, a P2SH script for a CScriptID, and an empty
- * script for CNoDestination.
- */
-CScript GetScriptForDestination(const CTxDestination& dest);
-
-/** Generate a P2PK script for the given pubkey. */
-CScript GetScriptForRawPubKey(const CPubKey& pubkey);
-
-/** Determine if script is a "multi_a" script. Returns (threshold, keyspans) if so, and nullopt otherwise.
- * The keyspans refer to bytes in the passed script. */
-std::optional<std::pair<int, std::vector<Span<const unsigned char>>>> MatchMultiA(const CScript& script LIFETIMEBOUND);
-
-/** Generate a multisig script. */
-CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys);
-
-struct ShortestVectorFirstComparator
-{
- bool operator()(const std::vector<unsigned char>& a, const std::vector<unsigned char>& b) const
- {
- if (a.size() < b.size()) return true;
- if (a.size() > b.size()) return false;
- return a < b;
- }
-};
-
-struct TaprootSpendData
-{
- /** The BIP341 internal key. */
- XOnlyPubKey internal_key;
- /** The Merkle root of the script tree (0 if no scripts). */
- uint256 merkle_root;
- /** Map from (script, leaf_version) to (sets of) control blocks.
- * More than one control block for a given script is only possible if it
- * appears in multiple branches of the tree. We keep them all so that
- * inference can reconstruct the full tree. Within each set, the control
- * blocks are sorted by size, so that the signing logic can easily
- * prefer the cheapest one. */
- std::map<std::pair<std::vector<unsigned char>, int>, std::set<std::vector<unsigned char>, ShortestVectorFirstComparator>> scripts;
- /** Merge other TaprootSpendData (for the same scriptPubKey) into this. */
- void Merge(TaprootSpendData other);
-};
-
-/** Utility class to construct Taproot outputs from internal key and script tree. */
-class TaprootBuilder
-{
-private:
- /** Information about a tracked leaf in the Merkle tree. */
- struct LeafInfo
- {
- std::vector<unsigned char> script; //!< The script.
- int leaf_version; //!< The leaf version for that script.
- std::vector<uint256> merkle_branch; //!< The hashing partners above this leaf.
- };
-
- /** Information associated with a node in the Merkle tree. */
- struct NodeInfo
- {
- /** Merkle hash of this node. */
- uint256 hash;
- /** Tracked leaves underneath this node (either from the node itself, or its children).
- * The merkle_branch field of each is the partners to get to *this* node. */
- std::vector<LeafInfo> leaves;
- };
- /** Whether the builder is in a valid state so far. */
- bool m_valid = true;
-
- /** The current state of the builder.
- *
- * For each level in the tree, one NodeInfo object may be present. m_branch[0]
- * is information about the root; further values are for deeper subtrees being
- * explored.
- *
- * For every right branch taken to reach the position we're currently
- * working in, there will be a (non-nullopt) entry in m_branch corresponding
- * to the left branch at that level.
- *
- * For example, imagine this tree: - N0 -
- * / \
- * N1 N2
- * / \ / \
- * A B C N3
- * / \
- * D E
- *
- * Initially, m_branch is empty. After processing leaf A, it would become
- * {nullopt, nullopt, A}. When processing leaf B, an entry at level 2 already
- * exists, and it would thus be combined with it to produce a level 1 one,
- * resulting in {nullopt, N1}. Adding C and D takes us to {nullopt, N1, C}
- * and {nullopt, N1, C, D} respectively. When E is processed, it is combined
- * with D, and then C, and then N1, to produce the root, resulting in {N0}.
- *
- * This structure allows processing with just O(log n) overhead if the leaves
- * are computed on the fly.
- *
- * As an invariant, there can never be nullopt entries at the end. There can
- * also not be more than 128 entries (as that would mean more than 128 levels
- * in the tree). The depth of newly added entries will always be at least
- * equal to the current size of m_branch (otherwise it does not correspond
- * to a depth-first traversal of a tree). m_branch is only empty if no entries
- * have ever be processed. m_branch having length 1 corresponds to being done.
- */
- std::vector<std::optional<NodeInfo>> m_branch;
-
- XOnlyPubKey m_internal_key; //!< The internal key, set when finalizing.
- XOnlyPubKey m_output_key; //!< The output key, computed when finalizing.
- bool m_parity; //!< The tweak parity, computed when finalizing.
-
- /** Combine information about a parent Merkle tree node from its child nodes. */
- static NodeInfo Combine(NodeInfo&& a, NodeInfo&& b);
- /** Insert information about a node at a certain depth, and propagate information up. */
- void Insert(NodeInfo&& node, int depth);
-
-public:
- /** Add a new script at a certain depth in the tree. Add() operations must be called
- * in depth-first traversal order of binary tree. If track is true, it will be included in
- * the GetSpendData() output. */
- TaprootBuilder& Add(int depth, Span<const unsigned char> script, int leaf_version, bool track = true);
- /** Like Add(), but for a Merkle node with a given hash to the tree. */
- TaprootBuilder& AddOmitted(int depth, const uint256& hash);
- /** Finalize the construction. Can only be called when IsComplete() is true.
- internal_key.IsFullyValid() must be true. */
- TaprootBuilder& Finalize(const XOnlyPubKey& internal_key);
-
- /** Return true if so far all input was valid. */
- bool IsValid() const { return m_valid; }
- /** Return whether there were either no leaves, or the leaves form a Huffman tree. */
- bool IsComplete() const { return m_valid && (m_branch.size() == 0 || (m_branch.size() == 1 && m_branch[0].has_value())); }
- /** Compute scriptPubKey (after Finalize()). */
- WitnessV1Taproot GetOutput();
- /** Check if a list of depths is legal (will lead to IsComplete()). */
- static bool ValidDepths(const std::vector<int>& depths);
- /** Compute spending data (after Finalize()). */
- TaprootSpendData GetSpendData() const;
- /** Returns a vector of tuples representing the depth, leaf version, and script */
- std::vector<std::tuple<uint8_t, uint8_t, std::vector<unsigned char>>> GetTreeTuples() const;
- /** Returns true if there are any tapscripts */
- bool HasScripts() const { return !m_branch.empty(); }
-};
-
-/** Given a TaprootSpendData and the output key, reconstruct its script tree.
- *
- * If the output doesn't match the spenddata, or if the data in spenddata is incomplete,
- * std::nullopt is returned. Otherwise, a vector of (depth, script, leaf_ver) tuples is
- * returned, corresponding to a depth-first traversal of the script tree.
- */
-std::optional<std::vector<std::tuple<int, std::vector<unsigned char>, int>>> InferTaprootTree(const TaprootSpendData& spenddata, const XOnlyPubKey& output);
-
-#endif // BITCOIN_SCRIPT_STANDARD_H
diff --git a/src/signet.cpp b/src/signet.cpp
index b73d82bb2e..21b289b637 100644
--- a/src/signet.cpp
+++ b/src/signet.cpp
@@ -18,7 +18,6 @@
#include <primitives/block.h>
#include <primitives/transaction.h>
#include <script/interpreter.h>
-#include <script/standard.h>
#include <span.h>
#include <streams.h>
#include <uint256.h>
diff --git a/src/test/blockfilter_index_tests.cpp b/src/test/blockfilter_index_tests.cpp
index 9bd5c7c2b6..97ea5cfbf3 100644
--- a/src/test/blockfilter_index_tests.cpp
+++ b/src/test/blockfilter_index_tests.cpp
@@ -2,6 +2,7 @@
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+#include <addresstype.h>
#include <blockfilter.h>
#include <chainparams.h>
#include <consensus/merkle.h>
@@ -10,7 +11,6 @@
#include <interfaces/chain.h>
#include <node/miner.h>
#include <pow.h>
-#include <script/standard.h>
#include <test/util/blockfilter.h>
#include <test/util/index.h>
#include <test/util/setup_common.h>
diff --git a/src/test/blockmanager_tests.cpp b/src/test/blockmanager_tests.cpp
index f52c692649..553bb31ba1 100644
--- a/src/test/blockmanager_tests.cpp
+++ b/src/test/blockmanager_tests.cpp
@@ -6,6 +6,7 @@
#include <node/blockstorage.h>
#include <node/context.h>
#include <node/kernel_notifications.h>
+#include <script/solver.h>
#include <util/chaintype.h>
#include <validation.h>
diff --git a/src/test/coins_tests.cpp b/src/test/coins_tests.cpp
index 853dc6dc1e..12dc4d1ccc 100644
--- a/src/test/coins_tests.cpp
+++ b/src/test/coins_tests.cpp
@@ -2,9 +2,9 @@
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+#include <addresstype.h>
#include <clientversion.h>
#include <coins.h>
-#include <script/standard.h>
#include <streams.h>
#include <test/util/poolresourcetester.h>
#include <test/util/random.h>
diff --git a/src/test/compress_tests.cpp b/src/test/compress_tests.cpp
index de99b91c7f..b56629ae40 100644
--- a/src/test/compress_tests.cpp
+++ b/src/test/compress_tests.cpp
@@ -3,7 +3,7 @@
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
#include <compressor.h>
-#include <script/standard.h>
+#include <script/script.h>
#include <test/util/setup_common.h>
#include <stdint.h>
diff --git a/src/test/denialofservice_tests.cpp b/src/test/denialofservice_tests.cpp
index b740a51574..90e5bb34ed 100644
--- a/src/test/denialofservice_tests.cpp
+++ b/src/test/denialofservice_tests.cpp
@@ -12,7 +12,6 @@
#include <pubkey.h>
#include <script/sign.h>
#include <script/signingprovider.h>
-#include <script/standard.h>
#include <serialize.h>
#include <test/util/net.h>
#include <test/util/random.h>
diff --git a/src/test/descriptor_tests.cpp b/src/test/descriptor_tests.cpp
index 5cec0b07c9..829afab8da 100644
--- a/src/test/descriptor_tests.cpp
+++ b/src/test/descriptor_tests.cpp
@@ -5,7 +5,6 @@
#include <pubkey.h>
#include <script/descriptor.h>
#include <script/sign.h>
-#include <script/standard.h>
#include <test/util/setup_common.h>
#include <util/strencodings.h>
diff --git a/src/test/fuzz/integer.cpp b/src/test/fuzz/integer.cpp
index 91521bc7f4..849618d748 100644
--- a/src/test/fuzz/integer.cpp
+++ b/src/test/fuzz/integer.cpp
@@ -19,7 +19,7 @@
#include <pow.h>
#include <protocol.h>
#include <pubkey.h>
-#include <script/standard.h>
+#include <script/script.h>
#include <serialize.h>
#include <streams.h>
#include <test/fuzz/FuzzedDataProvider.h>
diff --git a/src/test/fuzz/key.cpp b/src/test/fuzz/key.cpp
index 8faeb9e04f..a5a579d982 100644
--- a/src/test/fuzz/key.cpp
+++ b/src/test/fuzz/key.cpp
@@ -13,7 +13,7 @@
#include <script/script.h>
#include <script/sign.h>
#include <script/signingprovider.h>
-#include <script/standard.h>
+#include <script/solver.h>
#include <streams.h>
#include <test/fuzz/FuzzedDataProvider.h>
#include <test/fuzz/fuzz.h>
diff --git a/src/test/fuzz/script.cpp b/src/test/fuzz/script.cpp
index 1cb7d01906..acc82f55f6 100644
--- a/src/test/fuzz/script.cpp
+++ b/src/test/fuzz/script.cpp
@@ -16,7 +16,7 @@
#include <script/script_error.h>
#include <script/sign.h>
#include <script/signingprovider.h>
-#include <script/standard.h>
+#include <script/solver.h>
#include <streams.h>
#include <test/fuzz/FuzzedDataProvider.h>
#include <test/fuzz/fuzz.h>
diff --git a/src/test/fuzz/util.h b/src/test/fuzz/util.h
index 5f2aff08da..736311ed55 100644
--- a/src/test/fuzz/util.h
+++ b/src/test/fuzz/util.h
@@ -5,6 +5,7 @@
#ifndef BITCOIN_TEST_FUZZ_UTIL_H
#define BITCOIN_TEST_FUZZ_UTIL_H
+#include <addresstype.h>
#include <arith_uint256.h>
#include <coins.h>
#include <compat/compat.h>
@@ -13,7 +14,6 @@
#include <merkleblock.h>
#include <primitives/transaction.h>
#include <script/script.h>
-#include <script/standard.h>
#include <serialize.h>
#include <streams.h>
#include <test/fuzz/FuzzedDataProvider.h>
diff --git a/src/test/interfaces_tests.cpp b/src/test/interfaces_tests.cpp
index 68377e197f..29f0aea3b1 100644
--- a/src/test/interfaces_tests.cpp
+++ b/src/test/interfaces_tests.cpp
@@ -5,8 +5,8 @@
#include <chainparams.h>
#include <consensus/validation.h>
#include <interfaces/chain.h>
-#include <script/standard.h>
#include <test/util/setup_common.h>
+#include <script/solver.h>
#include <validation.h>
#include <boost/test/unit_test.hpp>
diff --git a/src/test/miner_tests.cpp b/src/test/miner_tests.cpp
index 94e3f27930..b4c7cac223 100644
--- a/src/test/miner_tests.cpp
+++ b/src/test/miner_tests.cpp
@@ -2,6 +2,7 @@
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+#include <addresstype.h>
#include <coins.h>
#include <common/system.h>
#include <consensus/consensus.h>
@@ -9,7 +10,6 @@
#include <consensus/tx_verify.h>
#include <node/miner.h>
#include <policy/policy.h>
-#include <script/standard.h>
#include <test/util/random.h>
#include <test/util/txmempool.h>
#include <timedata.h>
diff --git a/src/test/miniscript_tests.cpp b/src/test/miniscript_tests.cpp
index 9c811db3e9..0cb58450e8 100644
--- a/src/test/miniscript_tests.cpp
+++ b/src/test/miniscript_tests.cpp
@@ -10,6 +10,7 @@
#include <test/util/setup_common.h>
#include <boost/test/unit_test.hpp>
+#include <addresstype.h>
#include <core_io.h>
#include <hash.h>
#include <pubkey.h>
@@ -18,7 +19,6 @@
#include <crypto/sha256.h>
#include <script/interpreter.h>
#include <script/miniscript.h>
-#include <script/standard.h>
#include <script/script_error.h>
namespace {
diff --git a/src/test/orphanage_tests.cpp b/src/test/orphanage_tests.cpp
index a2c4774338..af53737fec 100644
--- a/src/test/orphanage_tests.cpp
+++ b/src/test/orphanage_tests.cpp
@@ -6,7 +6,6 @@
#include <pubkey.h>
#include <script/sign.h>
#include <script/signingprovider.h>
-#include <script/standard.h>
#include <test/util/random.h>
#include <test/util/setup_common.h>
#include <txorphanage.h>
diff --git a/src/test/script_standard_tests.cpp b/src/test/script_standard_tests.cpp
index 884e3d0634..1a205728d6 100644
--- a/src/test/script_standard_tests.cpp
+++ b/src/test/script_standard_tests.cpp
@@ -8,7 +8,7 @@
#include <key_io.h>
#include <script/script.h>
#include <script/signingprovider.h>
-#include <script/standard.h>
+#include <script/solver.h>
#include <test/util/setup_common.h>
#include <util/strencodings.h>
diff --git a/src/test/script_tests.cpp b/src/test/script_tests.cpp
index 411924496c..d63bfb9603 100644
--- a/src/test/script_tests.cpp
+++ b/src/test/script_tests.cpp
@@ -14,6 +14,7 @@
#include <script/sigcache.h>
#include <script/sign.h>
#include <script/signingprovider.h>
+#include <script/solver.h>
#include <streams.h>
#include <test/util/json.h>
#include <test/util/random.h>
diff --git a/src/test/sigopcount_tests.cpp b/src/test/sigopcount_tests.cpp
index a17be54419..ec9490d745 100644
--- a/src/test/sigopcount_tests.cpp
+++ b/src/test/sigopcount_tests.cpp
@@ -2,13 +2,15 @@
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+#include <addresstype.h>
#include <coins.h>
#include <consensus/consensus.h>
#include <consensus/tx_verify.h>
#include <key.h>
#include <pubkey.h>
+#include <script/interpreter.h>
#include <script/script.h>
-#include <script/standard.h>
+#include <script/solver.h>
#include <test/util/setup_common.h>
#include <uint256.h>
diff --git a/src/test/transaction_tests.cpp b/src/test/transaction_tests.cpp
index 34dd2c3e9f..a4c0db8aea 100644
--- a/src/test/transaction_tests.cpp
+++ b/src/test/transaction_tests.cpp
@@ -19,7 +19,7 @@
#include <script/script_error.h>
#include <script/sign.h>
#include <script/signingprovider.h>
-#include <script/standard.h>
+#include <script/solver.h>
#include <streams.h>
#include <test/util/json.h>
#include <test/util/random.h>
diff --git a/src/test/txindex_tests.cpp b/src/test/txindex_tests.cpp
index cb80dbed69..9fa59bab57 100644
--- a/src/test/txindex_tests.cpp
+++ b/src/test/txindex_tests.cpp
@@ -2,10 +2,10 @@
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+#include <addresstype.h>
#include <chainparams.h>
#include <index/txindex.h>
#include <interfaces/chain.h>
-#include <script/standard.h>
#include <test/util/index.h>
#include <test/util/setup_common.h>
#include <validation.h>
diff --git a/src/test/txpackage_tests.cpp b/src/test/txpackage_tests.cpp
index c08d2748a6..df5f8b4cce 100644
--- a/src/test/txpackage_tests.cpp
+++ b/src/test/txpackage_tests.cpp
@@ -8,7 +8,6 @@
#include <policy/policy.h>
#include <primitives/transaction.h>
#include <script/script.h>
-#include <script/standard.h>
#include <test/util/random.h>
#include <test/util/setup_common.h>
#include <validation.h>
diff --git a/src/test/txvalidation_tests.cpp b/src/test/txvalidation_tests.cpp
index f06bef3589..ecf0889711 100644
--- a/src/test/txvalidation_tests.cpp
+++ b/src/test/txvalidation_tests.cpp
@@ -8,7 +8,6 @@
#include <policy/policy.h>
#include <primitives/transaction.h>
#include <script/script.h>
-#include <script/standard.h>
#include <test/util/setup_common.h>
#include <validation.h>
diff --git a/src/test/txvalidationcache_tests.cpp b/src/test/txvalidationcache_tests.cpp
index 8f8628169f..c1f6226982 100644
--- a/src/test/txvalidationcache_tests.cpp
+++ b/src/test/txvalidationcache_tests.cpp
@@ -6,7 +6,6 @@
#include <key.h>
#include <script/sign.h>
#include <script/signingprovider.h>
-#include <script/standard.h>
#include <test/util/setup_common.h>
#include <txmempool.h>
#include <util/chaintype.h>
diff --git a/src/test/util/mining.cpp b/src/test/util/mining.cpp
index 51f4b89512..08d1b4c902 100644
--- a/src/test/util/mining.cpp
+++ b/src/test/util/mining.cpp
@@ -11,7 +11,6 @@
#include <node/context.h>
#include <pow.h>
#include <primitives/transaction.h>
-#include <script/standard.h>
#include <test/util/script.h>
#include <util/check.h>
#include <validation.h>
diff --git a/src/test/validation_block_tests.cpp b/src/test/validation_block_tests.cpp
index e08f2c98c2..d1463634cc 100644
--- a/src/test/validation_block_tests.cpp
+++ b/src/test/validation_block_tests.cpp
@@ -10,7 +10,6 @@
#include <node/miner.h>
#include <pow.h>
#include <random.h>
-#include <script/standard.h>
#include <test/util/random.h>
#include <test/util/script.h>
#include <test/util/setup_common.h>
diff --git a/src/util/message.cpp b/src/util/message.cpp
index f8ea8247d5..ec845aeffb 100644
--- a/src/util/message.cpp
+++ b/src/util/message.cpp
@@ -7,7 +7,6 @@
#include <key.h>
#include <key_io.h>
#include <pubkey.h>
-#include <script/standard.h>
#include <uint256.h>
#include <util/message.h>
#include <util/strencodings.h>
diff --git a/src/wallet/coincontrol.h b/src/wallet/coincontrol.h
index 7ff8fee5bc..71593e236f 100644
--- a/src/wallet/coincontrol.h
+++ b/src/wallet/coincontrol.h
@@ -11,7 +11,6 @@
#include <primitives/transaction.h>
#include <script/keyorigin.h>
#include <script/signingprovider.h>
-#include <script/standard.h>
#include <algorithm>
#include <map>
diff --git a/src/wallet/interfaces.cpp b/src/wallet/interfaces.cpp
index cd438cfe2f..5f2aee6923 100644
--- a/src/wallet/interfaces.cpp
+++ b/src/wallet/interfaces.cpp
@@ -11,7 +11,6 @@
#include <policy/fees.h>
#include <primitives/transaction.h>
#include <rpc/server.h>
-#include <script/standard.h>
#include <support/allocators/secure.h>
#include <sync.h>
#include <uint256.h>
diff --git a/src/wallet/rpc/addresses.cpp b/src/wallet/rpc/addresses.cpp
index a8ef0a5731..c1b99a4f97 100644
--- a/src/wallet/rpc/addresses.cpp
+++ b/src/wallet/rpc/addresses.cpp
@@ -5,6 +5,8 @@
#include <core_io.h>
#include <key_io.h>
#include <rpc/util.h>
+#include <script/script.h>
+#include <script/solver.h>
#include <util/bip32.h>
#include <util/translation.h>
#include <wallet/receive.h>
@@ -440,10 +442,9 @@ public:
UniValue operator()(const ScriptHash& scripthash) const
{
- CScriptID scriptID(scripthash);
UniValue obj(UniValue::VOBJ);
CScript subscript;
- if (provider && provider->GetCScript(scriptID, subscript)) {
+ if (provider && provider->GetCScript(ToScriptID(scripthash), subscript)) {
ProcessSubScript(subscript, obj);
}
return obj;
diff --git a/src/wallet/rpc/backup.cpp b/src/wallet/rpc/backup.cpp
index af8043f158..22c31436f1 100644
--- a/src/wallet/rpc/backup.cpp
+++ b/src/wallet/rpc/backup.cpp
@@ -12,7 +12,7 @@
#include <rpc/util.h>
#include <script/descriptor.h>
#include <script/script.h>
-#include <script/standard.h>
+#include <script/solver.h>
#include <sync.h>
#include <uint256.h>
#include <util/bip32.h>
diff --git a/src/wallet/rpc/coins.cpp b/src/wallet/rpc/coins.cpp
index 22f0f0b83c..6f0623cdf5 100644
--- a/src/wallet/rpc/coins.cpp
+++ b/src/wallet/rpc/coins.cpp
@@ -6,6 +6,7 @@
#include <hash.h>
#include <key_io.h>
#include <rpc/util.h>
+#include <script/script.h>
#include <util/moneystr.h>
#include <wallet/coincontrol.h>
#include <wallet/receive.h>
@@ -672,7 +673,7 @@ RPCHelpMan listunspent()
std::unique_ptr<SigningProvider> provider = pwallet->GetSolvingProvider(scriptPubKey);
if (provider) {
if (scriptPubKey.IsPayToScriptHash()) {
- const CScriptID& hash = CScriptID(std::get<ScriptHash>(address));
+ const CScriptID hash = ToScriptID(std::get<ScriptHash>(address));
CScript redeemScript;
if (provider->GetCScript(hash, redeemScript)) {
entry.pushKV("redeemScript", HexStr(redeemScript));
diff --git a/src/wallet/rpc/spend.cpp b/src/wallet/rpc/spend.cpp
index b695d4bed3..0e3f10dc76 100644
--- a/src/wallet/rpc/spend.cpp
+++ b/src/wallet/rpc/spend.cpp
@@ -8,6 +8,7 @@
#include <policy/policy.h>
#include <rpc/rawtransaction_util.h>
#include <rpc/util.h>
+#include <script/script.h>
#include <util/fees.h>
#include <util/rbf.h>
#include <util/translation.h>
diff --git a/src/wallet/scriptpubkeyman.cpp b/src/wallet/scriptpubkeyman.cpp
index 5b110b4d14..1f510d1c58 100644
--- a/src/wallet/scriptpubkeyman.cpp
+++ b/src/wallet/scriptpubkeyman.cpp
@@ -7,7 +7,9 @@
#include <logging.h>
#include <outputtype.h>
#include <script/descriptor.h>
+#include <script/script.h>
#include <script/sign.h>
+#include <script/solver.h>
#include <util/bip32.h>
#include <util/strencodings.h>
#include <util/string.h>
diff --git a/src/wallet/scriptpubkeyman.h b/src/wallet/scriptpubkeyman.h
index bf35c776ae..f03673e9d3 100644
--- a/src/wallet/scriptpubkeyman.h
+++ b/src/wallet/scriptpubkeyman.h
@@ -5,11 +5,12 @@
#ifndef BITCOIN_WALLET_SCRIPTPUBKEYMAN_H
#define BITCOIN_WALLET_SCRIPTPUBKEYMAN_H
+#include <addresstype.h>
#include <logging.h>
#include <psbt.h>
#include <script/descriptor.h>
+#include <script/script.h>
#include <script/signingprovider.h>
-#include <script/standard.h>
#include <util/error.h>
#include <util/message.h>
#include <util/result.h>
diff --git a/src/wallet/spend.cpp b/src/wallet/spend.cpp
index a3728223fb..c0ee00e097 100644
--- a/src/wallet/spend.cpp
+++ b/src/wallet/spend.cpp
@@ -11,7 +11,9 @@
#include <numeric>
#include <policy/policy.h>
#include <primitives/transaction.h>
+#include <script/script.h>
#include <script/signingprovider.h>
+#include <script/solver.h>
#include <util/check.h>
#include <util/fees.h>
#include <util/moneystr.h>
diff --git a/src/wallet/test/ismine_tests.cpp b/src/wallet/test/ismine_tests.cpp
index fd0718fbb9..95d5c1b9ce 100644
--- a/src/wallet/test/ismine_tests.cpp
+++ b/src/wallet/test/ismine_tests.cpp
@@ -6,7 +6,8 @@
#include <key_io.h>
#include <node/context.h>
#include <script/script.h>
-#include <script/standard.h>
+#include <script/solver.h>
+#include <script/signingprovider.h>
#include <test/util/setup_common.h>
#include <wallet/types.h>
#include <wallet/wallet.h>
diff --git a/src/wallet/test/scriptpubkeyman_tests.cpp b/src/wallet/test/scriptpubkeyman_tests.cpp
index d4997c418a..15bff04221 100644
--- a/src/wallet/test/scriptpubkeyman_tests.cpp
+++ b/src/wallet/test/scriptpubkeyman_tests.cpp
@@ -3,8 +3,8 @@
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
#include <key.h>
-#include <script/standard.h>
#include <test/util/setup_common.h>
+#include <script/solver.h>
#include <wallet/scriptpubkeyman.h>
#include <wallet/wallet.h>
#include <wallet/test/util.h>
diff --git a/src/wallet/test/spend_tests.cpp b/src/wallet/test/spend_tests.cpp
index 6e87d1cb49..b5ea275bcb 100644
--- a/src/wallet/test/spend_tests.cpp
+++ b/src/wallet/test/spend_tests.cpp
@@ -4,6 +4,7 @@
#include <consensus/amount.h>
#include <policy/fees.h>
+#include <script/solver.h>
#include <validation.h>
#include <wallet/coincontrol.h>
#include <wallet/spend.h>
diff --git a/src/wallet/test/util.h b/src/wallet/test/util.h
index 2a1fe639de..8bd238648f 100644
--- a/src/wallet/test/util.h
+++ b/src/wallet/test/util.h
@@ -5,7 +5,7 @@
#ifndef BITCOIN_WALLET_TEST_UTIL_H
#define BITCOIN_WALLET_TEST_UTIL_H
-#include <script/standard.h>
+#include <addresstype.h>
#include <wallet/db.h>
#include <memory>
diff --git a/src/wallet/test/wallet_tests.cpp b/src/wallet/test/wallet_tests.cpp
index dd914f159c..4abf6441d2 100644
--- a/src/wallet/test/wallet_tests.cpp
+++ b/src/wallet/test/wallet_tests.cpp
@@ -9,11 +9,13 @@
#include <stdint.h>
#include <vector>
+#include <addresstype.h>
#include <interfaces/chain.h>
#include <key_io.h>
#include <node/blockstorage.h>
#include <policy/policy.h>
#include <rpc/server.h>
+#include <script/solver.h>
#include <test/util/logging.h>
#include <test/util/random.h>
#include <test/util/setup_common.h>
diff --git a/src/wallet/wallet.cpp b/src/wallet/wallet.cpp
index 6b2755ea53..fd9a3e5a30 100644
--- a/src/wallet/wallet.cpp
+++ b/src/wallet/wallet.cpp
@@ -26,6 +26,7 @@
#include <script/descriptor.h>
#include <script/script.h>
#include <script/signingprovider.h>
+#include <script/solver.h>
#include <support/cleanse.h>
#include <txmempool.h>
#include <util/bip32.h>
diff --git a/src/wallet/wallet.h b/src/wallet/wallet.h
index cbd5008366..91c8e89d2d 100644
--- a/src/wallet/wallet.h
+++ b/src/wallet/wallet.h
@@ -6,6 +6,7 @@
#ifndef BITCOIN_WALLET_WALLET_H
#define BITCOIN_WALLET_WALLET_H
+#include <addresstype.h>
#include <consensus/amount.h>
#include <interfaces/chain.h>
#include <interfaces/handler.h>
diff --git a/src/wallet/walletdb.cpp b/src/wallet/walletdb.cpp
index 8212c04464..92eca46f05 100644
--- a/src/wallet/walletdb.cpp
+++ b/src/wallet/walletdb.cpp
@@ -8,6 +8,7 @@
#include <common/system.h>
#include <key_io.h>
#include <protocol.h>
+#include <script/script.h>
#include <serialize.h>
#include <sync.h>
#include <util/bip32.h>
diff --git a/src/wallet/walletdb.h b/src/wallet/walletdb.h
index 8f7c2f030c..dad0b18a78 100644
--- a/src/wallet/walletdb.h
+++ b/src/wallet/walletdb.h
@@ -7,7 +7,6 @@
#define BITCOIN_WALLET_WALLETDB_H
#include <script/sign.h>
-#include <script/standard.h>
#include <wallet/db.h>
#include <wallet/walletutil.h>
#include <key.h>