Branch data Line data Source code
# 1 : : // Copyright (c) 2009-2010 Satoshi Nakamoto
# 2 : : // Copyright (c) 2009-2021 The Bitcoin Core developers
# 3 : : // Distributed under the MIT software license, see the accompanying
# 4 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
# 5 : :
# 6 : : #ifndef BITCOIN_SCRIPT_STANDARD_H
# 7 : : #define BITCOIN_SCRIPT_STANDARD_H
# 8 : :
# 9 : : #include <pubkey.h>
# 10 : : #include <script/interpreter.h>
# 11 : : #include <uint256.h>
# 12 : : #include <util/hash_type.h>
# 13 : :
# 14 : : #include <map>
# 15 : : #include <string>
# 16 : : #include <variant>
# 17 : :
# 18 : : static const bool DEFAULT_ACCEPT_DATACARRIER = true;
# 19 : :
# 20 : : class CKeyID;
# 21 : : class CScript;
# 22 : : struct ScriptHash;
# 23 : :
# 24 : : /** A reference to a CScript: the Hash160 of its serialization (see script.h) */
# 25 : : class CScriptID : public BaseHash<uint160>
# 26 : : {
# 27 : : public:
# 28 : 466031 : CScriptID() : BaseHash() {}
# 29 : : explicit CScriptID(const CScript& in);
# 30 : 141869 : explicit CScriptID(const uint160& in) : BaseHash(in) {}
# 31 : : explicit CScriptID(const ScriptHash& in);
# 32 : : };
# 33 : :
# 34 : : /**
# 35 : : * Default setting for nMaxDatacarrierBytes. 80 bytes of data, +1 for OP_RETURN,
# 36 : : * +2 for the pushdata opcodes.
# 37 : : */
# 38 : : static const unsigned int MAX_OP_RETURN_RELAY = 83;
# 39 : :
# 40 : : /**
# 41 : : * A data carrying output is an unspendable output containing data. The script
# 42 : : * type is designated as TxoutType::NULL_DATA.
# 43 : : */
# 44 : : extern bool fAcceptDatacarrier;
# 45 : :
# 46 : : /** Maximum size of TxoutType::NULL_DATA scripts that this node considers standard. */
# 47 : : extern unsigned nMaxDatacarrierBytes;
# 48 : :
# 49 : : /**
# 50 : : * Mandatory script verification flags that all new blocks must comply with for
# 51 : : * them to be valid. (but old blocks may not comply with) Currently just P2SH,
# 52 : : * but in the future other flags may be added.
# 53 : : *
# 54 : : * Failing one of these tests may trigger a DoS ban - see CheckInputScripts() for
# 55 : : * details.
# 56 : : */
# 57 : : static const unsigned int MANDATORY_SCRIPT_VERIFY_FLAGS = SCRIPT_VERIFY_P2SH;
# 58 : :
# 59 : : enum class TxoutType {
# 60 : : NONSTANDARD,
# 61 : : // 'standard' transaction types:
# 62 : : PUBKEY,
# 63 : : PUBKEYHASH,
# 64 : : SCRIPTHASH,
# 65 : : MULTISIG,
# 66 : : NULL_DATA, //!< unspendable OP_RETURN script that carries data
# 67 : : WITNESS_V0_SCRIPTHASH,
# 68 : : WITNESS_V0_KEYHASH,
# 69 : : WITNESS_V1_TAPROOT,
# 70 : : WITNESS_UNKNOWN, //!< Only for Witness versions not already defined above
# 71 : : };
# 72 : :
# 73 : : class CNoDestination {
# 74 : : public:
# 75 : 0 : friend bool operator==(const CNoDestination &a, const CNoDestination &b) { return true; }
# 76 : 0 : friend bool operator<(const CNoDestination &a, const CNoDestination &b) { return true; }
# 77 : : };
# 78 : :
# 79 : : struct PKHash : public BaseHash<uint160>
# 80 : : {
# 81 : 3 : PKHash() : BaseHash() {}
# 82 : 648674 : explicit PKHash(const uint160& hash) : BaseHash(hash) {}
# 83 : : explicit PKHash(const CPubKey& pubkey);
# 84 : : explicit PKHash(const CKeyID& pubkey_id);
# 85 : : };
# 86 : : CKeyID ToKeyID(const PKHash& key_hash);
# 87 : :
# 88 : : struct WitnessV0KeyHash;
# 89 : : struct ScriptHash : public BaseHash<uint160>
# 90 : : {
# 91 : 0 : ScriptHash() : BaseHash() {}
# 92 : : // These don't do what you'd expect.
# 93 : : // Use ScriptHash(GetScriptForDestination(...)) instead.
# 94 : : explicit ScriptHash(const WitnessV0KeyHash& hash) = delete;
# 95 : : explicit ScriptHash(const PKHash& hash) = delete;
# 96 : :
# 97 : 17480 : explicit ScriptHash(const uint160& hash) : BaseHash(hash) {}
# 98 : : explicit ScriptHash(const CScript& script);
# 99 : : explicit ScriptHash(const CScriptID& script);
# 100 : : };
# 101 : :
# 102 : : struct WitnessV0ScriptHash : public BaseHash<uint256>
# 103 : : {
# 104 : 2141 : WitnessV0ScriptHash() : BaseHash() {}
# 105 : 0 : explicit WitnessV0ScriptHash(const uint256& hash) : BaseHash(hash) {}
# 106 : : explicit WitnessV0ScriptHash(const CScript& script);
# 107 : : };
# 108 : :
# 109 : : struct WitnessV0KeyHash : public BaseHash<uint160>
# 110 : : {
# 111 : 353216 : WitnessV0KeyHash() : BaseHash() {}
# 112 : 478367 : explicit WitnessV0KeyHash(const uint160& hash) : BaseHash(hash) {}
# 113 : : explicit WitnessV0KeyHash(const CPubKey& pubkey);
# 114 : : explicit WitnessV0KeyHash(const PKHash& pubkey_hash);
# 115 : : };
# 116 : : CKeyID ToKeyID(const WitnessV0KeyHash& key_hash);
# 117 : :
# 118 : : struct WitnessV1Taproot : public XOnlyPubKey
# 119 : : {
# 120 : 9018 : WitnessV1Taproot() : XOnlyPubKey() {}
# 121 : 69570 : explicit WitnessV1Taproot(const XOnlyPubKey& xpk) : XOnlyPubKey(xpk) {}
# 122 : : };
# 123 : :
# 124 : : //! CTxDestination subtype to encode any future Witness version
# 125 : : struct WitnessUnknown
# 126 : : {
# 127 : : unsigned int version;
# 128 : : unsigned int length;
# 129 : : unsigned char program[40];
# 130 : :
# 131 : 2 : friend bool operator==(const WitnessUnknown& w1, const WitnessUnknown& w2) {
# 132 [ - + ]: 2 : if (w1.version != w2.version) return false;
# 133 [ - + ]: 2 : if (w1.length != w2.length) return false;
# 134 : 2 : return std::equal(w1.program, w1.program + w1.length, w2.program);
# 135 : 2 : }
# 136 : :
# 137 : 17 : friend bool operator<(const WitnessUnknown& w1, const WitnessUnknown& w2) {
# 138 [ + + ]: 17 : if (w1.version < w2.version) return true;
# 139 [ + + ]: 12 : if (w1.version > w2.version) return false;
# 140 [ + + ]: 9 : if (w1.length < w2.length) return true;
# 141 [ + + ]: 7 : if (w1.length > w2.length) return false;
# 142 : 6 : return std::lexicographical_compare(w1.program, w1.program + w1.length, w2.program, w2.program + w2.length);
# 143 : 7 : }
# 144 : : };
# 145 : :
# 146 : : /**
# 147 : : * A txout script template with a specific destination. It is either:
# 148 : : * * CNoDestination: no destination set
# 149 : : * * PKHash: TxoutType::PUBKEYHASH destination (P2PKH)
# 150 : : * * ScriptHash: TxoutType::SCRIPTHASH destination (P2SH)
# 151 : : * * WitnessV0ScriptHash: TxoutType::WITNESS_V0_SCRIPTHASH destination (P2WSH)
# 152 : : * * WitnessV0KeyHash: TxoutType::WITNESS_V0_KEYHASH destination (P2WPKH)
# 153 : : * * WitnessV1Taproot: TxoutType::WITNESS_V1_TAPROOT destination (P2TR)
# 154 : : * * WitnessUnknown: TxoutType::WITNESS_UNKNOWN destination (P2W???)
# 155 : : * A CTxDestination is the internal data type encoded in a bitcoin address
# 156 : : */
# 157 : : using CTxDestination = std::variant<CNoDestination, PKHash, ScriptHash, WitnessV0ScriptHash, WitnessV0KeyHash, WitnessV1Taproot, WitnessUnknown>;
# 158 : :
# 159 : : /** Check whether a CTxDestination is a CNoDestination. */
# 160 : : bool IsValidDestination(const CTxDestination& dest);
# 161 : :
# 162 : : /** Get the name of a TxoutType as a string */
# 163 : : std::string GetTxnOutputType(TxoutType t);
# 164 : :
# 165 : : constexpr bool IsPushdataOp(opcodetype opcode)
# 166 : 1950 : {
# 167 [ + + ][ + + ]: 1950 : return opcode > OP_FALSE && opcode <= OP_PUSHDATA4;
# 168 : 1950 : }
# 169 : :
# 170 : : /**
# 171 : : * Parse a scriptPubKey and identify script type for standard scripts. If
# 172 : : * successful, returns script type and parsed pubkeys or hashes, depending on
# 173 : : * the type. For example, for a P2SH script, vSolutionsRet will contain the
# 174 : : * script hash, for P2PKH it will contain the key hash, etc.
# 175 : : *
# 176 : : * @param[in] scriptPubKey Script to parse
# 177 : : * @param[out] vSolutionsRet Vector of parsed pubkeys and hashes
# 178 : : * @return The script type. TxoutType::NONSTANDARD represents a failed solve.
# 179 : : */
# 180 : : TxoutType Solver(const CScript& scriptPubKey, std::vector<std::vector<unsigned char>>& vSolutionsRet);
# 181 : :
# 182 : : /**
# 183 : : * Parse a standard scriptPubKey for the destination address. Assigns result to
# 184 : : * the addressRet parameter and returns true if successful. Currently only works for P2PK,
# 185 : : * P2PKH, P2SH, P2WPKH, and P2WSH scripts.
# 186 : : */
# 187 : : bool ExtractDestination(const CScript& scriptPubKey, CTxDestination& addressRet);
# 188 : :
# 189 : : /**
# 190 : : * Generate a Bitcoin scriptPubKey for the given CTxDestination. Returns a P2PKH
# 191 : : * script for a CKeyID destination, a P2SH script for a CScriptID, and an empty
# 192 : : * script for CNoDestination.
# 193 : : */
# 194 : : CScript GetScriptForDestination(const CTxDestination& dest);
# 195 : :
# 196 : : /** Generate a P2PK script for the given pubkey. */
# 197 : : CScript GetScriptForRawPubKey(const CPubKey& pubkey);
# 198 : :
# 199 : : /** Determine if script is a "multi_a" script. Returns (threshold, keyspans) if so, and nullopt otherwise.
# 200 : : * The keyspans refer to bytes in the passed script. */
# 201 : : std::optional<std::pair<int, std::vector<Span<const unsigned char>>>> MatchMultiA(const CScript& script LIFETIMEBOUND);
# 202 : :
# 203 : : /** Generate a multisig script. */
# 204 : : CScript GetScriptForMultisig(int nRequired, const std::vector<CPubKey>& keys);
# 205 : :
# 206 : : struct ShortestVectorFirstComparator
# 207 : : {
# 208 : : bool operator()(const std::vector<unsigned char>& a, const std::vector<unsigned char>& b) const
# 209 : 58348 : {
# 210 [ + + ]: 58348 : if (a.size() < b.size()) return true;
# 211 [ + + ]: 35802 : if (a.size() > b.size()) return false;
# 212 : 23697 : return a < b;
# 213 : 35802 : }
# 214 : : };
# 215 : :
# 216 : : struct TaprootSpendData
# 217 : : {
# 218 : : /** The BIP341 internal key. */
# 219 : : XOnlyPubKey internal_key;
# 220 : : /** The Merkle root of the script tree (0 if no scripts). */
# 221 : : uint256 merkle_root;
# 222 : : /** Map from (script, leaf_version) to (sets of) control blocks.
# 223 : : * More than one control block for a given script is only possible if it
# 224 : : * appears in multiple branches of the tree. We keep them all so that
# 225 : : * inference can reconstruct the full tree. Within each set, the control
# 226 : : * blocks are sorted by size, so that the signing logic can easily
# 227 : : * prefer the cheapest one. */
# 228 : : std::map<std::pair<CScript, int>, std::set<std::vector<unsigned char>, ShortestVectorFirstComparator>> scripts;
# 229 : : /** Merge other TaprootSpendData (for the same scriptPubKey) into this. */
# 230 : : void Merge(TaprootSpendData other);
# 231 : : };
# 232 : :
# 233 : : /** Utility class to construct Taproot outputs from internal key and script tree. */
# 234 : : class TaprootBuilder
# 235 : : {
# 236 : : private:
# 237 : : /** Information about a tracked leaf in the Merkle tree. */
# 238 : : struct LeafInfo
# 239 : : {
# 240 : : CScript script; //!< The script.
# 241 : : int leaf_version; //!< The leaf version for that script.
# 242 : : std::vector<uint256> merkle_branch; //!< The hashing partners above this leaf.
# 243 : : };
# 244 : :
# 245 : : /** Information associated with a node in the Merkle tree. */
# 246 : : struct NodeInfo
# 247 : : {
# 248 : : /** Merkle hash of this node. */
# 249 : : uint256 hash;
# 250 : : /** Tracked leaves underneath this node (either from the node itself, or its children).
# 251 : : * The merkle_branch field of each is the partners to get to *this* node. */
# 252 : : std::vector<LeafInfo> leaves;
# 253 : : };
# 254 : : /** Whether the builder is in a valid state so far. */
# 255 : : bool m_valid = true;
# 256 : :
# 257 : : /** The current state of the builder.
# 258 : : *
# 259 : : * For each level in the tree, one NodeInfo object may be present. m_branch[0]
# 260 : : * is information about the root; further values are for deeper subtrees being
# 261 : : * explored.
# 262 : : *
# 263 : : * For every right branch taken to reach the position we're currently
# 264 : : * working in, there will be a (non-nullopt) entry in m_branch corresponding
# 265 : : * to the left branch at that level.
# 266 : : *
# 267 : : * For example, imagine this tree: - N0 -
# 268 : : * / \
# 269 : : * N1 N2
# 270 : : * / \ / \
# 271 : : * A B C N3
# 272 : : * / \
# 273 : : * D E
# 274 : : *
# 275 : : * Initially, m_branch is empty. After processing leaf A, it would become
# 276 : : * {nullopt, nullopt, A}. When processing leaf B, an entry at level 2 already
# 277 : : * exists, and it would thus be combined with it to produce a level 1 one,
# 278 : : * resulting in {nullopt, N1}. Adding C and D takes us to {nullopt, N1, C}
# 279 : : * and {nullopt, N1, C, D} respectively. When E is processed, it is combined
# 280 : : * with D, and then C, and then N1, to produce the root, resulting in {N0}.
# 281 : : *
# 282 : : * This structure allows processing with just O(log n) overhead if the leaves
# 283 : : * are computed on the fly.
# 284 : : *
# 285 : : * As an invariant, there can never be nullopt entries at the end. There can
# 286 : : * also not be more than 128 entries (as that would mean more than 128 levels
# 287 : : * in the tree). The depth of newly added entries will always be at least
# 288 : : * equal to the current size of m_branch (otherwise it does not correspond
# 289 : : * to a depth-first traversal of a tree). m_branch is only empty if no entries
# 290 : : * have ever be processed. m_branch having length 1 corresponds to being done.
# 291 : : */
# 292 : : std::vector<std::optional<NodeInfo>> m_branch;
# 293 : :
# 294 : : XOnlyPubKey m_internal_key; //!< The internal key, set when finalizing.
# 295 : : XOnlyPubKey m_output_key; //!< The output key, computed when finalizing.
# 296 : : bool m_parity; //!< The tweak parity, computed when finalizing.
# 297 : :
# 298 : : /** Combine information about a parent Merkle tree node from its child nodes. */
# 299 : : static NodeInfo Combine(NodeInfo&& a, NodeInfo&& b);
# 300 : : /** Insert information about a node at a certain depth, and propagate information up. */
# 301 : : void Insert(NodeInfo&& node, int depth);
# 302 : :
# 303 : : public:
# 304 : : /** Add a new script at a certain depth in the tree. Add() operations must be called
# 305 : : * in depth-first traversal order of binary tree. If track is true, it will be included in
# 306 : : * the GetSpendData() output. */
# 307 : : TaprootBuilder& Add(int depth, const CScript& script, int leaf_version, bool track = true);
# 308 : : /** Like Add(), but for a Merkle node with a given hash to the tree. */
# 309 : : TaprootBuilder& AddOmitted(int depth, const uint256& hash);
# 310 : : /** Finalize the construction. Can only be called when IsComplete() is true.
# 311 : : internal_key.IsFullyValid() must be true. */
# 312 : : TaprootBuilder& Finalize(const XOnlyPubKey& internal_key);
# 313 : :
# 314 : : /** Return true if so far all input was valid. */
# 315 : 38063 : bool IsValid() const { return m_valid; }
# 316 : : /** Return whether there were either no leaves, or the leaves form a Huffman tree. */
# 317 [ + - ][ + + ]: 183844 : bool IsComplete() const { return m_valid && (m_branch.size() == 0 || (m_branch.size() == 1 && m_branch[0].has_value())); }
# [ + + ][ + - ]
# 318 : : /** Compute scriptPubKey (after Finalize()). */
# 319 : : WitnessV1Taproot GetOutput();
# 320 : : /** Check if a list of depths is legal (will lead to IsComplete()). */
# 321 : : static bool ValidDepths(const std::vector<int>& depths);
# 322 : : /** Compute spending data (after Finalize()). */
# 323 : : TaprootSpendData GetSpendData() const;
# 324 : : };
# 325 : :
# 326 : : /** Given a TaprootSpendData and the output key, reconstruct its script tree.
# 327 : : *
# 328 : : * If the output doesn't match the spenddata, or if the data in spenddata is incomplete,
# 329 : : * std::nullopt is returned. Otherwise, a vector of (depth, script, leaf_ver) tuples is
# 330 : : * returned, corresponding to a depth-first traversal of the script tree.
# 331 : : */
# 332 : : std::optional<std::vector<std::tuple<int, CScript, int>>> InferTaprootTree(const TaprootSpendData& spenddata, const XOnlyPubKey& output);
# 333 : :
# 334 : : #endif // BITCOIN_SCRIPT_STANDARD_H
|
