diff options
| author | fanquake <fanquake@gmail.com> | 2023-08-17 11:30:16 +0100 |
|---|---|---|
| committer | fanquake <fanquake@gmail.com> | 2023-08-17 12:54:16 +0100 |
| commit | 7ef2d4ee4d09196d6fdf9a55dc9ebfd05d62d160 (patch) | |
| tree | 43e059ca463ebca13c19646cd7e6e67301988b3b | |
| parent | d78ff380a2cde80c264e36e046b1cfc054bd9253 (diff) | |
| parent | 91d924ede1b421df31c895f4f43359e453a09ca5 (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
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> |