miniscript.h
1 // Copyright (c) 2019-present The Bitcoin Core developers 2 // Distributed under the MIT software license, see the accompanying 3 // file COPYING or http://www.opensource.org/licenses/mit-license.php. 4 5 #ifndef BITCOIN_SCRIPT_MINISCRIPT_H 6 #define BITCOIN_SCRIPT_MINISCRIPT_H 7 8 #include <algorithm> 9 #include <compare> 10 #include <concepts> 11 #include <cstdint> 12 #include <cstdlib> 13 #include <functional> 14 #include <iterator> 15 #include <memory> 16 #include <optional> 17 #include <set> 18 #include <stdexcept> 19 #include <tuple> 20 #include <utility> 21 #include <vector> 22 23 #include <consensus/consensus.h> 24 #include <policy/policy.h> 25 #include <script/interpreter.h> 26 #include <script/parsing.h> 27 #include <script/script.h> 28 #include <serialize.h> 29 #include <span.h> 30 #include <util/check.h> 31 #include <util/strencodings.h> 32 #include <util/string.h> 33 #include <util/vector.h> 34 35 namespace miniscript { 36 37 /** This type encapsulates the miniscript type system properties. 38 * 39 * Every miniscript expression is one of 4 basic types, and additionally has 40 * a number of boolean type properties. 41 * 42 * The basic types are: 43 * - "B" Base: 44 * - Takes its inputs from the top of the stack. 45 * - When satisfied, pushes a nonzero value of up to 4 bytes onto the stack. 46 * - When dissatisfied, pushes a 0 onto the stack. 47 * - This is used for most expressions, and required for the top level one. 48 * - For example: older(n) = <n> OP_CHECKSEQUENCEVERIFY. 49 * - "V" Verify: 50 * - Takes its inputs from the top of the stack. 51 * - When satisfied, pushes nothing. 52 * - Cannot be dissatisfied. 53 * - This can be obtained by adding an OP_VERIFY to a B, modifying the last opcode 54 * of a B to its -VERIFY version (only for OP_CHECKSIG, OP_CHECKSIGVERIFY, 55 * OP_NUMEQUAL and OP_EQUAL), or by combining a V fragment under some conditions. 56 * - For example vc:pk_k(key) = <key> OP_CHECKSIGVERIFY 57 * - "K" Key: 58 * - Takes its inputs from the top of the stack. 59 * - Becomes a B when followed by OP_CHECKSIG. 60 * - Always pushes a public key onto the stack, for which a signature is to be 61 * provided to satisfy the expression. 62 * - For example pk_h(key) = OP_DUP OP_HASH160 <Hash160(key)> OP_EQUALVERIFY 63 * - "W" Wrapped: 64 * - Takes its input from one below the top of the stack. 65 * - When satisfied, pushes a nonzero value (like B) on top of the stack, or one below. 66 * - When dissatisfied, pushes 0 op top of the stack or one below. 67 * - Is always "OP_SWAP [B]" or "OP_TOALTSTACK [B] OP_FROMALTSTACK". 68 * - For example sc:pk_k(key) = OP_SWAP <key> OP_CHECKSIG 69 * 70 * There are type properties that help reasoning about correctness: 71 * - "z" Zero-arg: 72 * - Is known to always consume exactly 0 stack elements. 73 * - For example after(n) = <n> OP_CHECKLOCKTIMEVERIFY 74 * - "o" One-arg: 75 * - Is known to always consume exactly 1 stack element. 76 * - Conflicts with property 'z' 77 * - For example sha256(hash) = OP_SIZE 32 OP_EQUALVERIFY OP_SHA256 <hash> OP_EQUAL 78 * - "n" Nonzero: 79 * - For every way this expression can be satisfied, a satisfaction exists that never needs 80 * a zero top stack element. 81 * - Conflicts with property 'z' and with type 'W'. 82 * - "d" Dissatisfiable: 83 * - There is an easy way to construct a dissatisfaction for this expression. 84 * - Conflicts with type 'V'. 85 * - "u" Unit: 86 * - In case of satisfaction, an exact 1 is put on the stack (rather than just nonzero). 87 * - Conflicts with type 'V'. 88 * 89 * Additional type properties help reasoning about nonmalleability: 90 * - "e" Expression: 91 * - This implies property 'd', but the dissatisfaction is nonmalleable. 92 * - This generally requires 'e' for all subexpressions which are invoked for that 93 * dissatisfaction, and property 'f' for the unexecuted subexpressions in that case. 94 * - Conflicts with type 'V'. 95 * - "f" Forced: 96 * - Dissatisfactions (if any) for this expression always involve at least one signature. 97 * - Is always true for type 'V'. 98 * - "s" Safe: 99 * - Satisfactions for this expression always involve at least one signature. 100 * - "m" Nonmalleable: 101 * - For every way this expression can be satisfied (which may be none), 102 * a nonmalleable satisfaction exists. 103 * - This generally requires 'm' for all subexpressions, and 'e' for all subexpressions 104 * which are dissatisfied when satisfying the parent. 105 * 106 * One type property is an implementation detail: 107 * - "x" Expensive verify: 108 * - Expressions with this property have a script whose last opcode is not EQUAL, CHECKSIG, or CHECKMULTISIG. 109 * - Not having this property means that it can be converted to a V at no cost (by switching to the 110 * -VERIFY version of the last opcode). 111 * 112 * Five more type properties for representing timelock information. Spend paths 113 * in miniscripts containing conflicting timelocks and heightlocks cannot be spent together. 114 * This helps users detect if miniscript does not match the semantic behaviour the 115 * user expects. 116 * - "g" Whether the branch contains a relative time timelock 117 * - "h" Whether the branch contains a relative height timelock 118 * - "i" Whether the branch contains an absolute time timelock 119 * - "j" Whether the branch contains an absolute height timelock 120 * - "k" 121 * - Whether all satisfactions of this expression don't contain a mix of heightlock and timelock 122 * of the same type. 123 * - If the miniscript does not have the "k" property, the miniscript template will not match 124 * the user expectation of the corresponding spending policy. 125 * For each of these properties the subset rule holds: an expression with properties X, Y, and Z, is also 126 * valid in places where an X, a Y, a Z, an XY, ... is expected. 127 */ 128 class Type { 129 //! Internal bitmap of properties (see ""_mst operator for details). 130 uint32_t m_flags; 131 132 //! Internal constructor used by the ""_mst operator. 133 explicit constexpr Type(uint32_t flags) : m_flags(flags) {} 134 135 public: 136 //! The only way to publicly construct a Type is using this literal operator. 137 friend consteval Type operator""_mst(const char* c, size_t l); 138 139 //! Compute the type with the union of properties. 140 constexpr Type operator|(Type x) const { return Type(m_flags | x.m_flags); } 141 142 //! Compute the type with the intersection of properties. 143 constexpr Type operator&(Type x) const { return Type(m_flags & x.m_flags); } 144 145 //! Check whether the left hand's properties are superset of the right's (= left is a subtype of right). 146 constexpr bool operator<<(Type x) const { return (x.m_flags & ~m_flags) == 0; } 147 148 //! Comparison operator to enable use in sets/maps (total ordering incompatible with <<). 149 constexpr bool operator<(Type x) const { return m_flags < x.m_flags; } 150 151 //! Equality operator. 152 constexpr bool operator==(Type x) const { return m_flags == x.m_flags; } 153 154 //! The empty type if x is false, itself otherwise. 155 constexpr Type If(bool x) const { return Type(x ? m_flags : 0); } 156 }; 157 158 //! Literal operator to construct Type objects. 159 inline consteval Type operator""_mst(const char* c, size_t l) 160 { 161 Type typ{0}; 162 163 for (const char *p = c; p < c + l; p++) { 164 typ = typ | Type( 165 *p == 'B' ? 1 << 0 : // Base type 166 *p == 'V' ? 1 << 1 : // Verify type 167 *p == 'K' ? 1 << 2 : // Key type 168 *p == 'W' ? 1 << 3 : // Wrapped type 169 *p == 'z' ? 1 << 4 : // Zero-arg property 170 *p == 'o' ? 1 << 5 : // One-arg property 171 *p == 'n' ? 1 << 6 : // Nonzero arg property 172 *p == 'd' ? 1 << 7 : // Dissatisfiable property 173 *p == 'u' ? 1 << 8 : // Unit property 174 *p == 'e' ? 1 << 9 : // Expression property 175 *p == 'f' ? 1 << 10 : // Forced property 176 *p == 's' ? 1 << 11 : // Safe property 177 *p == 'm' ? 1 << 12 : // Nonmalleable property 178 *p == 'x' ? 1 << 13 : // Expensive verify 179 *p == 'g' ? 1 << 14 : // older: contains relative time timelock (csv_time) 180 *p == 'h' ? 1 << 15 : // older: contains relative height timelock (csv_height) 181 *p == 'i' ? 1 << 16 : // after: contains time timelock (cltv_time) 182 *p == 'j' ? 1 << 17 : // after: contains height timelock (cltv_height) 183 *p == 'k' ? 1 << 18 : // does not contain a combination of height and time locks 184 (throw std::logic_error("Unknown character in _mst literal"), 0) 185 ); 186 } 187 188 return typ; 189 } 190 191 using Opcode = std::pair<opcodetype, std::vector<unsigned char>>; 192 193 template<typename Key> class Node; 194 195 //! Unordered traversal of a miniscript node tree. 196 template <typename Key, std::invocable<const Node<Key>&> Fn> 197 void ForEachNode(const Node<Key>& root, Fn&& fn) 198 { 199 std::vector<std::reference_wrapper<const Node<Key>>> stack{root}; 200 while (!stack.empty()) { 201 const Node<Key>& node = stack.back(); 202 std::invoke(fn, node); 203 stack.pop_back(); 204 for (const auto& sub : node.Subs()) { 205 stack.emplace_back(sub); 206 } 207 } 208 } 209 210 //! The different node types in miniscript. 211 enum class Fragment { 212 JUST_0, //!< OP_0 213 JUST_1, //!< OP_1 214 PK_K, //!< [key] 215 PK_H, //!< OP_DUP OP_HASH160 [keyhash] OP_EQUALVERIFY 216 OLDER, //!< [n] OP_CHECKSEQUENCEVERIFY 217 AFTER, //!< [n] OP_CHECKLOCKTIMEVERIFY 218 SHA256, //!< OP_SIZE 32 OP_EQUALVERIFY OP_SHA256 [hash] OP_EQUAL 219 HASH256, //!< OP_SIZE 32 OP_EQUALVERIFY OP_HASH256 [hash] OP_EQUAL 220 RIPEMD160, //!< OP_SIZE 32 OP_EQUALVERIFY OP_RIPEMD160 [hash] OP_EQUAL 221 HASH160, //!< OP_SIZE 32 OP_EQUALVERIFY OP_HASH160 [hash] OP_EQUAL 222 WRAP_A, //!< OP_TOALTSTACK [X] OP_FROMALTSTACK 223 WRAP_S, //!< OP_SWAP [X] 224 WRAP_C, //!< [X] OP_CHECKSIG 225 WRAP_D, //!< OP_DUP OP_IF [X] OP_ENDIF 226 WRAP_V, //!< [X] OP_VERIFY (or -VERIFY version of last opcode in X) 227 WRAP_J, //!< OP_SIZE OP_0NOTEQUAL OP_IF [X] OP_ENDIF 228 WRAP_N, //!< [X] OP_0NOTEQUAL 229 AND_V, //!< [X] [Y] 230 AND_B, //!< [X] [Y] OP_BOOLAND 231 OR_B, //!< [X] [Y] OP_BOOLOR 232 OR_C, //!< [X] OP_NOTIF [Y] OP_ENDIF 233 OR_D, //!< [X] OP_IFDUP OP_NOTIF [Y] OP_ENDIF 234 OR_I, //!< OP_IF [X] OP_ELSE [Y] OP_ENDIF 235 ANDOR, //!< [X] OP_NOTIF [Z] OP_ELSE [Y] OP_ENDIF 236 THRESH, //!< [X1] ([Xn] OP_ADD)* [k] OP_EQUAL 237 MULTI, //!< [k] [key_n]* [n] OP_CHECKMULTISIG (only available within P2WSH context) 238 MULTI_A, //!< [key_0] OP_CHECKSIG ([key_n] OP_CHECKSIGADD)* [k] OP_NUMEQUAL (only within Tapscript ctx) 239 // AND_N(X,Y) is represented as ANDOR(X,Y,0) 240 // WRAP_T(X) is represented as AND_V(X,1) 241 // WRAP_L(X) is represented as OR_I(0,X) 242 // WRAP_U(X) is represented as OR_I(X,0) 243 }; 244 245 enum class Availability { 246 NO, 247 YES, 248 MAYBE, 249 }; 250 251 enum class MiniscriptContext { 252 P2WSH, 253 TAPSCRIPT, 254 }; 255 256 /** Whether the context Tapscript, ensuring the only other possibility is P2WSH. */ 257 constexpr bool IsTapscript(MiniscriptContext ms_ctx) 258 { 259 switch (ms_ctx) { 260 case MiniscriptContext::P2WSH: return false; 261 case MiniscriptContext::TAPSCRIPT: return true; 262 } 263 assert(false); 264 } 265 266 namespace internal { 267 268 //! The maximum size of a witness item for a Miniscript under Tapscript context. (A BIP340 signature with a sighash type byte.) 269 static constexpr uint32_t MAX_TAPMINISCRIPT_STACK_ELEM_SIZE{65}; 270 271 //! version + nLockTime 272 constexpr uint32_t TX_OVERHEAD{4 + 4}; 273 //! prevout + nSequence + scriptSig 274 constexpr uint32_t TXIN_BYTES_NO_WITNESS{36 + 4 + 1}; 275 //! nValue + script len + OP_0 + pushdata 32. 276 constexpr uint32_t P2WSH_TXOUT_BYTES{8 + 1 + 1 + 33}; 277 //! Data other than the witness in a transaction. Overhead + vin count + one vin + vout count + one vout + segwit marker 278 constexpr uint32_t TX_BODY_LEEWAY_WEIGHT{(TX_OVERHEAD + GetSizeOfCompactSize(1) + TXIN_BYTES_NO_WITNESS + GetSizeOfCompactSize(1) + P2WSH_TXOUT_BYTES) * WITNESS_SCALE_FACTOR + 2}; 279 //! Maximum possible stack size to spend a Taproot output (excluding the script itself). 280 constexpr uint32_t MAX_TAPSCRIPT_SAT_SIZE{GetSizeOfCompactSize(MAX_STACK_SIZE) + (GetSizeOfCompactSize(MAX_TAPMINISCRIPT_STACK_ELEM_SIZE) + MAX_TAPMINISCRIPT_STACK_ELEM_SIZE) * MAX_STACK_SIZE + GetSizeOfCompactSize(TAPROOT_CONTROL_MAX_SIZE) + TAPROOT_CONTROL_MAX_SIZE}; 281 /** The maximum size of a script depending on the context. */ 282 constexpr uint32_t MaxScriptSize(MiniscriptContext ms_ctx) 283 { 284 if (IsTapscript(ms_ctx)) { 285 // Leaf scripts under Tapscript are not explicitly limited in size. They are only implicitly 286 // bounded by the maximum standard size of a spending transaction. Let the maximum script 287 // size conservatively be small enough such that even a maximum sized witness and a reasonably 288 // sized spending transaction can spend an output paying to this script without running into 289 // the maximum standard tx size limit. 290 constexpr auto max_size{MAX_STANDARD_TX_WEIGHT - TX_BODY_LEEWAY_WEIGHT - MAX_TAPSCRIPT_SAT_SIZE}; 291 return max_size - GetSizeOfCompactSize(max_size); 292 } 293 return MAX_STANDARD_P2WSH_SCRIPT_SIZE; 294 } 295 296 //! Helper function for Node::CalcType. 297 Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Type>& sub_types, uint32_t k, size_t data_size, size_t n_subs, size_t n_keys, MiniscriptContext ms_ctx); 298 299 //! Helper function for Node::CalcScriptLen. 300 size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs, size_t n_keys, MiniscriptContext ms_ctx); 301 302 //! A helper sanitizer/checker for the output of CalcType. 303 Type SanitizeType(Type x); 304 305 //! An object representing a sequence of witness stack elements. 306 struct InputStack { 307 /** Whether this stack is valid for its intended purpose (satisfaction or dissatisfaction of a Node). 308 * The MAYBE value is used for size estimation, when keys/preimages may actually be unavailable, 309 * but may be available at signing time. This makes the InputStack structure and signing logic, 310 * filled with dummy signatures/preimages usable for witness size estimation. 311 */ 312 Availability available = Availability::YES; 313 //! Whether this stack contains a digital signature. 314 bool has_sig = false; 315 //! Whether this stack is malleable (can be turned into an equally valid other stack by a third party). 316 bool malleable = false; 317 //! Whether this stack is non-canonical (using a construction known to be unnecessary for satisfaction). 318 //! Note that this flag does not affect the satisfaction algorithm; it is only used for sanity checking. 319 bool non_canon = false; 320 //! Serialized witness size. 321 size_t size = 0; 322 //! Data elements. 323 std::vector<std::vector<unsigned char>> stack; 324 //! Construct an empty stack (valid). 325 InputStack() = default; 326 //! Construct a valid single-element stack (with an element up to 75 bytes). 327 InputStack(std::vector<unsigned char> in) : size(in.size() + 1), stack(Vector(std::move(in))) {} 328 //! Change availability 329 InputStack& SetAvailable(Availability avail); 330 //! Mark this input stack as having a signature. 331 InputStack& SetWithSig(); 332 //! Mark this input stack as non-canonical (known to not be necessary in non-malleable satisfactions). 333 InputStack& SetNonCanon(); 334 //! Mark this input stack as malleable. 335 InputStack& SetMalleable(bool x = true); 336 //! Concatenate two input stacks. 337 friend InputStack operator+(InputStack a, InputStack b); 338 //! Choose between two potential input stacks. 339 friend InputStack operator|(InputStack a, InputStack b); 340 }; 341 342 /** A stack consisting of a single zero-length element (interpreted as 0 by the script interpreter in numeric context). */ 343 static const auto ZERO = InputStack(std::vector<unsigned char>()); 344 /** A stack consisting of a single malleable 32-byte 0x0000...0000 element (for dissatisfying hash challenges). */ 345 static const auto ZERO32 = InputStack(std::vector<unsigned char>(32, 0)).SetMalleable(); 346 /** A stack consisting of a single 0x01 element (interpreted as 1 by the script interpreted in numeric context). */ 347 static const auto ONE = InputStack(Vector((unsigned char)1)); 348 /** The empty stack. */ 349 static const auto EMPTY = InputStack(); 350 /** A stack representing the lack of any (dis)satisfactions. */ 351 static const auto INVALID = InputStack().SetAvailable(Availability::NO); 352 353 //! A pair of a satisfaction and a dissatisfaction InputStack. 354 struct InputResult { 355 InputStack nsat, sat; 356 357 template<typename A, typename B> 358 InputResult(A&& in_nsat, B&& in_sat) : nsat(std::forward<A>(in_nsat)), sat(std::forward<B>(in_sat)) {} 359 }; 360 361 //! Class whose objects represent the maximum of a list of integers. 362 template <typename I> 363 class MaxInt 364 { 365 bool valid; 366 I value; 367 368 public: 369 MaxInt() : valid(false), value(0) {} 370 MaxInt(I val) : valid(true), value(val) {} 371 372 bool Valid() const { return valid; } 373 I Value() const { return value; } 374 375 friend MaxInt<I> operator+(const MaxInt<I>& a, const MaxInt<I>& b) { 376 if (!a.valid || !b.valid) return {}; 377 return a.value + b.value; 378 } 379 380 friend MaxInt<I> operator|(const MaxInt<I>& a, const MaxInt<I>& b) { 381 if (!a.valid) return b; 382 if (!b.valid) return a; 383 return std::max(a.value, b.value); 384 } 385 }; 386 387 struct Ops { 388 //! Non-push opcodes. 389 uint32_t count; 390 //! Number of keys in possibly executed OP_CHECKMULTISIG(VERIFY)s to satisfy. 391 MaxInt<uint32_t> sat; 392 //! Number of keys in possibly executed OP_CHECKMULTISIG(VERIFY)s to dissatisfy. 393 MaxInt<uint32_t> dsat; 394 395 Ops(uint32_t in_count, MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : count(in_count), sat(in_sat), dsat(in_dsat) {}; 396 }; 397 398 /** A data structure to help the calculation of stack size limits. 399 * 400 * Conceptually, every SatInfo object corresponds to a (possibly empty) set of script execution 401 * traces (sequences of opcodes). 402 * - SatInfo{} corresponds to the empty set. 403 * - SatInfo{n, e} corresponds to a single trace whose net effect is removing n elements from the 404 * stack (may be negative for a net increase), and reaches a maximum of e stack elements more 405 * than it ends with. 406 * - operator| is the union operation: (a | b) corresponds to the union of the traces in a and the 407 * traces in b. 408 * - operator+ is the concatenation operator: (a + b) corresponds to the set of traces formed by 409 * concatenating any trace in a with any trace in b. 410 * 411 * Its fields are: 412 * - valid is true if the set is non-empty. 413 * - netdiff (if valid) is the largest difference between stack size at the beginning and at the 414 * end of the script across all traces in the set. 415 * - exec (if valid) is the largest difference between stack size anywhere during execution and at 416 * the end of the script, across all traces in the set (note that this is not necessarily due 417 * to the same trace as the one that resulted in the value for netdiff). 418 * 419 * This allows us to build up stack size limits for any script efficiently, by starting from the 420 * individual opcodes miniscripts correspond to, using concatenation to construct scripts, and 421 * using the union operation to choose between execution branches. Since any top-level script 422 * satisfaction ends with a single stack element, we know that for a full script: 423 * - netdiff+1 is the maximal initial stack size (relevant for P2WSH stack limits). 424 * - exec+1 is the maximal stack size reached during execution (relevant for P2TR stack limits). 425 * 426 * Mathematically, SatInfo forms a semiring: 427 * - operator| is the semiring addition operator, with identity SatInfo{}, and which is commutative 428 * and associative. 429 * - operator+ is the semiring multiplication operator, with identity SatInfo{0}, and which is 430 * associative. 431 * - operator+ is distributive over operator|, so (a + (b | c)) = (a+b | a+c). This means we do not 432 * need to actually materialize all possible full execution traces over the whole script (which 433 * may be exponential in the length of the script); instead we can use the union operation at the 434 * individual subexpression level, and concatenate the result with subexpressions before and 435 * after it. 436 * - It is not a commutative semiring, because a+b can differ from b+a. For example, "OP_1 OP_DROP" 437 * has exec=1, while "OP_DROP OP_1" has exec=0. 438 */ 439 class SatInfo 440 { 441 //! Whether a canonical satisfaction/dissatisfaction is possible at all. 442 bool valid; 443 //! How much higher the stack size at start of execution can be compared to at the end. 444 int32_t netdiff; 445 //! How much higher the stack size can be during execution compared to at the end. 446 int32_t exec; 447 448 public: 449 /** Empty script set. */ 450 constexpr SatInfo() noexcept : valid(false), netdiff(0), exec(0) {} 451 452 /** Script set with a single script in it, with specified netdiff and exec. */ 453 constexpr SatInfo(int32_t in_netdiff, int32_t in_exec) noexcept : 454 valid{true}, netdiff{in_netdiff}, exec{in_exec} {} 455 456 bool Valid() const { return valid; } 457 int32_t NetDiff() const { return netdiff; } 458 int32_t Exec() const { return exec; } 459 460 /** Script set union. */ 461 constexpr friend SatInfo operator|(const SatInfo& a, const SatInfo& b) noexcept 462 { 463 // Union with an empty set is itself. 464 if (!a.valid) return b; 465 if (!b.valid) return a; 466 // Otherwise the netdiff and exec of the union is the maximum of the individual values. 467 return {std::max(a.netdiff, b.netdiff), std::max(a.exec, b.exec)}; 468 } 469 470 /** Script set concatenation. */ 471 constexpr friend SatInfo operator+(const SatInfo& a, const SatInfo& b) noexcept 472 { 473 // Concatenation with an empty set yields an empty set. 474 if (!a.valid || !b.valid) return {}; 475 // Otherwise, the maximum stack size difference for the combined scripts is the sum of the 476 // netdiffs, and the maximum stack size difference anywhere is either b.exec (if the 477 // maximum occurred in b) or b.netdiff+a.exec (if the maximum occurred in a). 478 return {a.netdiff + b.netdiff, std::max(b.exec, b.netdiff + a.exec)}; 479 } 480 481 /** The empty script. */ 482 static constexpr SatInfo Empty() noexcept { return {0, 0}; } 483 /** A script consisting of a single push opcode. */ 484 static constexpr SatInfo Push() noexcept { return {-1, 0}; } 485 /** A script consisting of a single hash opcode. */ 486 static constexpr SatInfo Hash() noexcept { return {0, 0}; } 487 /** A script consisting of just a repurposed nop (OP_CHECKLOCKTIMEVERIFY, OP_CHECKSEQUENCEVERIFY). */ 488 static constexpr SatInfo Nop() noexcept { return {0, 0}; } 489 /** A script consisting of just OP_IF or OP_NOTIF. Note that OP_ELSE and OP_ENDIF have no stack effect. */ 490 static constexpr SatInfo If() noexcept { return {1, 1}; } 491 /** A script consisting of just a binary operator (OP_BOOLAND, OP_BOOLOR, OP_ADD). */ 492 static constexpr SatInfo BinaryOp() noexcept { return {1, 1}; } 493 494 // Scripts for specific individual opcodes. 495 static constexpr SatInfo OP_DUP() noexcept { return {-1, 0}; } 496 static constexpr SatInfo OP_IFDUP(bool nonzero) noexcept { return {nonzero ? -1 : 0, 0}; } 497 static constexpr SatInfo OP_EQUALVERIFY() noexcept { return {2, 2}; } 498 static constexpr SatInfo OP_EQUAL() noexcept { return {1, 1}; } 499 static constexpr SatInfo OP_SIZE() noexcept { return {-1, 0}; } 500 static constexpr SatInfo OP_CHECKSIG() noexcept { return {1, 1}; } 501 static constexpr SatInfo OP_0NOTEQUAL() noexcept { return {0, 0}; } 502 static constexpr SatInfo OP_VERIFY() noexcept { return {1, 1}; } 503 }; 504 505 class StackSize 506 { 507 SatInfo sat, dsat; 508 509 public: 510 constexpr StackSize(SatInfo in_sat, SatInfo in_dsat) noexcept : sat(in_sat), dsat(in_dsat) {}; 511 constexpr StackSize(SatInfo in_both) noexcept : sat(in_both), dsat(in_both) {}; 512 513 const SatInfo& Sat() const { return sat; } 514 const SatInfo& Dsat() const { return dsat; } 515 }; 516 517 struct WitnessSize { 518 //! Maximum witness size to satisfy; 519 MaxInt<uint32_t> sat; 520 //! Maximum witness size to dissatisfy; 521 MaxInt<uint32_t> dsat; 522 523 WitnessSize(MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : sat(in_sat), dsat(in_dsat) {}; 524 }; 525 526 struct NoDupCheck {}; 527 528 } // namespace internal 529 530 //! A node in a miniscript expression. 531 template <typename Key> 532 class Node 533 { 534 //! What node type this node is. 535 enum Fragment fragment; 536 //! The k parameter (time for OLDER/AFTER, threshold for THRESH(_M)) 537 uint32_t k = 0; 538 //! The keys used by this expression (only for PK_K/PK_H/MULTI) 539 std::vector<Key> keys; 540 //! The data bytes in this expression (only for HASH160/HASH256/SHA256/RIPEMD160). 541 std::vector<unsigned char> data; 542 //! Subexpressions (for WRAP_*/AND_*/OR_*/ANDOR/THRESH) 543 std::vector<Node> subs; 544 //! The Script context for this node. Either P2WSH or Tapscript. 545 MiniscriptContext m_script_ctx; 546 547 public: 548 // Permit 1 level deep recursion since we own instances of our own type. 549 // NOLINTBEGIN(misc-no-recursion) 550 ~Node() 551 { 552 // Destroy the subexpressions iteratively after moving out their 553 // subexpressions to avoid a stack-overflow due to recursive calls to 554 // the subs' destructors. 555 // We move vectors in order to only update array-pointers inside them 556 // rather than moving individual Node instances which would involve 557 // moving/copying each Node field. 558 std::vector<std::vector<Node>> queue; 559 queue.push_back(std::move(subs)); 560 do { 561 auto flattening{std::move(queue.back())}; 562 queue.pop_back(); 563 for (Node& n : flattening) { 564 if (!n.subs.empty()) queue.push_back(std::move(n.subs)); 565 } 566 } while (!queue.empty()); 567 } 568 // NOLINTEND(misc-no-recursion) 569 570 Node<Key> Clone() const 571 { 572 // Use TreeEval() to avoid a stack-overflow due to recursion 573 auto upfn = [](const Node& node, std::span<Node> children) { 574 std::vector<Node> new_subs; 575 for (auto& child : children) { 576 // It's fine to move from children as they are new nodes having 577 // been produced by calling this function one level down. 578 new_subs.push_back(std::move(child)); 579 } 580 return Node{internal::NoDupCheck{}, node.m_script_ctx, node.fragment, std::move(new_subs), node.keys, node.data, node.k}; 581 }; 582 return TreeEval<Node>(upfn); 583 } 584 585 enum Fragment Fragment() const { return fragment; } 586 uint32_t K() const { return k; } 587 const std::vector<Key>& Keys() const { return keys; } 588 const std::vector<unsigned char>& Data() const { return data; } 589 const std::vector<Node>& Subs() const { return subs; } 590 591 private: 592 //! Cached ops counts. 593 internal::Ops ops; 594 //! Cached stack size bounds. 595 internal::StackSize ss; 596 //! Cached witness size bounds. 597 internal::WitnessSize ws; 598 //! Cached expression type (computed by CalcType and fed through SanitizeType). 599 Type typ; 600 //! Cached script length (computed by CalcScriptLen). 601 size_t scriptlen; 602 //! Whether a public key appears more than once in this node. This value is initialized 603 //! by all constructors except the NoDupCheck ones. The NoDupCheck ones skip the 604 //! computation, requiring it to be done manually by invoking DuplicateKeyCheck(). 605 //! DuplicateKeyCheck(), or a non-NoDupCheck constructor, will compute has_duplicate_keys 606 //! for all subnodes as well. 607 mutable std::optional<bool> has_duplicate_keys; 608 609 // Constructor which takes all of the data that a Node could possibly contain. 610 // This is kept private as no valid fragment has all of these arguments. 611 // Only used by Clone() 612 Node(internal::NoDupCheck, MiniscriptContext script_ctx, enum Fragment nt, std::vector<Node> sub, std::vector<Key> key, std::vector<unsigned char> arg, uint32_t val) 613 : fragment(nt), k(val), keys(std::move(key)), data(std::move(arg)), subs(std::move(sub)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {} 614 615 //! Compute the length of the script for this miniscript (including children). 616 size_t CalcScriptLen() const 617 { 618 size_t subsize = 0; 619 for (const auto& sub : subs) { 620 subsize += sub.ScriptSize(); 621 } 622 Type sub0type = subs.size() > 0 ? subs[0].GetType() : ""_mst; 623 return internal::ComputeScriptLen(fragment, sub0type, subsize, k, subs.size(), keys.size(), m_script_ctx); 624 } 625 626 /* Apply a recursive algorithm to a Miniscript tree, without actual recursive calls. 627 * 628 * The algorithm is defined by two functions: downfn and upfn. Conceptually, the 629 * result can be thought of as first using downfn to compute a "state" for each node, 630 * from the root down to the leaves. Then upfn is used to compute a "result" for each 631 * node, from the leaves back up to the root, which is then returned. In the actual 632 * implementation, both functions are invoked in an interleaved fashion, performing a 633 * depth-first traversal of the tree. 634 * 635 * In more detail, it is invoked as node.TreeEvalMaybe<Result>(root, downfn, upfn): 636 * - root is the state of the root node, of type State. 637 * - downfn is a callable (State&, const Node&, size_t) -> State, which given a 638 * node, its state, and an index of one of its children, computes the state of that 639 * child. It can modify the state. Children of a given node will have downfn() 640 * called in order. 641 * - upfn is a callable (State&&, const Node&, std::span<Result>) -> std::optional<Result>, 642 * which given a node, its state, and a span of the results of its children, 643 * computes the result of the node. If std::nullopt is returned by upfn, 644 * TreeEvalMaybe() immediately returns std::nullopt. 645 * The return value of TreeEvalMaybe is the result of the root node. 646 * 647 * Result type cannot be bool due to the std::vector<bool> specialization. 648 */ 649 template<typename Result, typename State, typename DownFn, typename UpFn> 650 std::optional<Result> TreeEvalMaybe(State root_state, DownFn downfn, UpFn upfn) const 651 { 652 /** Entries of the explicit stack tracked in this algorithm. */ 653 struct StackElem 654 { 655 const Node& node; //!< The node being evaluated. 656 size_t expanded; //!< How many children of this node have been expanded. 657 State state; //!< The state for that node. 658 659 StackElem(const Node& node_, size_t exp_, State&& state_) : 660 node(node_), expanded(exp_), state(std::move(state_)) {} 661 }; 662 /* Stack of tree nodes being explored. */ 663 std::vector<StackElem> stack; 664 /* Results of subtrees so far. Their order and mapping to tree nodes 665 * is implicitly defined by stack. */ 666 std::vector<Result> results; 667 stack.emplace_back(*this, 0, std::move(root_state)); 668 669 /* Here is a demonstration of the algorithm, for an example tree A(B,C(D,E),F). 670 * State variables are omitted for simplicity. 671 * 672 * First: stack=[(A,0)] results=[] 673 * stack=[(A,1),(B,0)] results=[] 674 * stack=[(A,1)] results=[B] 675 * stack=[(A,2),(C,0)] results=[B] 676 * stack=[(A,2),(C,1),(D,0)] results=[B] 677 * stack=[(A,2),(C,1)] results=[B,D] 678 * stack=[(A,2),(C,2),(E,0)] results=[B,D] 679 * stack=[(A,2),(C,2)] results=[B,D,E] 680 * stack=[(A,2)] results=[B,C] 681 * stack=[(A,3),(F,0)] results=[B,C] 682 * stack=[(A,3)] results=[B,C,F] 683 * Final: stack=[] results=[A] 684 */ 685 while (stack.size()) { 686 const Node& node = stack.back().node; 687 if (stack.back().expanded < node.subs.size()) { 688 /* We encounter a tree node with at least one unexpanded child. 689 * Expand it. By the time we hit this node again, the result of 690 * that child (and all earlier children) will be at the end of `results`. */ 691 size_t child_index = stack.back().expanded++; 692 State child_state = downfn(stack.back().state, node, child_index); 693 stack.emplace_back(node.subs[child_index], 0, std::move(child_state)); 694 continue; 695 } 696 // Invoke upfn with the last node.subs.size() elements of results as input. 697 assert(results.size() >= node.subs.size()); 698 std::optional<Result> result{upfn(std::move(stack.back().state), node, 699 std::span<Result>{results}.last(node.subs.size()))}; 700 // If evaluation returns std::nullopt, abort immediately. 701 if (!result) return {}; 702 // Replace the last node.subs.size() elements of results with the new result. 703 results.erase(results.end() - node.subs.size(), results.end()); 704 results.push_back(std::move(*result)); 705 stack.pop_back(); 706 } 707 // The final remaining results element is the root result, return it. 708 assert(results.size() >= 1); 709 CHECK_NONFATAL(results.size() == 1); 710 return std::move(results[0]); 711 } 712 713 /** Like TreeEvalMaybe, but without downfn or State type. 714 * upfn takes (const Node&, std::span<Result>) and returns std::optional<Result>. */ 715 template<typename Result, typename UpFn> 716 std::optional<Result> TreeEvalMaybe(UpFn upfn) const 717 { 718 struct DummyState {}; 719 return TreeEvalMaybe<Result>(DummyState{}, 720 [](DummyState, const Node&, size_t) { return DummyState{}; }, 721 [&upfn](DummyState, const Node& node, std::span<Result> subs) { 722 return upfn(node, subs); 723 } 724 ); 725 } 726 727 /** Like TreeEvalMaybe, but always produces a result. upfn must return Result. */ 728 template<typename Result, typename State, typename DownFn, typename UpFn> 729 Result TreeEval(State root_state, DownFn&& downfn, UpFn upfn) const 730 { 731 // Invoke TreeEvalMaybe with upfn wrapped to return std::optional<Result>, and then 732 // unconditionally dereference the result (it cannot be std::nullopt). 733 return std::move(*TreeEvalMaybe<Result>(std::move(root_state), 734 std::forward<DownFn>(downfn), 735 [&upfn](State&& state, const Node& node, std::span<Result> subs) { 736 Result res{upfn(std::move(state), node, subs)}; 737 return std::optional<Result>(std::move(res)); 738 } 739 )); 740 } 741 742 /** Like TreeEval, but without downfn or State type. 743 * upfn takes (const Node&, std::span<Result>) and returns Result. */ 744 template<typename Result, typename UpFn> 745 Result TreeEval(UpFn upfn) const 746 { 747 struct DummyState {}; 748 return std::move(*TreeEvalMaybe<Result>(DummyState{}, 749 [](DummyState, const Node&, size_t) { return DummyState{}; }, 750 [&upfn](DummyState, const Node& node, std::span<Result> subs) { 751 Result res{upfn(node, subs)}; 752 return std::optional<Result>(std::move(res)); 753 } 754 )); 755 } 756 757 /** Compare two miniscript subtrees, using a non-recursive algorithm. */ 758 friend int Compare(const Node<Key>& node1, const Node<Key>& node2) 759 { 760 std::vector<std::pair<const Node<Key>&, const Node<Key>&>> queue; 761 queue.emplace_back(node1, node2); 762 while (!queue.empty()) { 763 const auto& [a, b] = queue.back(); 764 queue.pop_back(); 765 if (std::tie(a.fragment, a.k, a.keys, a.data) < std::tie(b.fragment, b.k, b.keys, b.data)) return -1; 766 if (std::tie(b.fragment, b.k, b.keys, b.data) < std::tie(a.fragment, a.k, a.keys, a.data)) return 1; 767 if (a.subs.size() < b.subs.size()) return -1; 768 if (b.subs.size() < a.subs.size()) return 1; 769 size_t n = a.subs.size(); 770 for (size_t i = 0; i < n; ++i) { 771 queue.emplace_back(a.subs[n - 1 - i], b.subs[n - 1 - i]); 772 } 773 } 774 return 0; 775 } 776 777 //! Compute the type for this miniscript. 778 Type CalcType() const { 779 using namespace internal; 780 781 // THRESH has a variable number of subexpressions 782 std::vector<Type> sub_types; 783 if (fragment == Fragment::THRESH) { 784 for (const auto& sub : subs) sub_types.push_back(sub.GetType()); 785 } 786 // All other nodes than THRESH can be computed just from the types of the 0-3 subexpressions. 787 Type x = subs.size() > 0 ? subs[0].GetType() : ""_mst; 788 Type y = subs.size() > 1 ? subs[1].GetType() : ""_mst; 789 Type z = subs.size() > 2 ? subs[2].GetType() : ""_mst; 790 791 return SanitizeType(ComputeType(fragment, x, y, z, sub_types, k, data.size(), subs.size(), keys.size(), m_script_ctx)); 792 } 793 794 public: 795 template<typename Ctx> 796 CScript ToScript(const Ctx& ctx) const 797 { 798 // To construct the CScript for a Miniscript object, we use the TreeEval algorithm. 799 // The State is a boolean: whether or not the node's script expansion is followed 800 // by an OP_VERIFY (which may need to be combined with the last script opcode). 801 auto downfn = [](bool verify, const Node& node, size_t index) { 802 // For WRAP_V, the subexpression is certainly followed by OP_VERIFY. 803 if (node.fragment == Fragment::WRAP_V) return true; 804 // The subexpression of WRAP_S, and the last subexpression of AND_V 805 // inherit the followed-by-OP_VERIFY property from the parent. 806 if (node.fragment == Fragment::WRAP_S || 807 (node.fragment == Fragment::AND_V && index == 1)) return verify; 808 return false; 809 }; 810 // The upward function computes for a node, given its followed-by-OP_VERIFY status 811 // and the CScripts of its child nodes, the CScript of the node. 812 const bool is_tapscript{IsTapscript(m_script_ctx)}; 813 auto upfn = [&ctx, is_tapscript](bool verify, const Node& node, std::span<CScript> subs) -> CScript { 814 switch (node.fragment) { 815 case Fragment::PK_K: return BuildScript(ctx.ToPKBytes(node.keys[0])); 816 case Fragment::PK_H: return BuildScript(OP_DUP, OP_HASH160, ctx.ToPKHBytes(node.keys[0]), OP_EQUALVERIFY); 817 case Fragment::OLDER: return BuildScript(node.k, OP_CHECKSEQUENCEVERIFY); 818 case Fragment::AFTER: return BuildScript(node.k, OP_CHECKLOCKTIMEVERIFY); 819 case Fragment::SHA256: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_SHA256, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL); 820 case Fragment::RIPEMD160: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_RIPEMD160, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL); 821 case Fragment::HASH256: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_HASH256, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL); 822 case Fragment::HASH160: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_HASH160, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL); 823 case Fragment::WRAP_A: return BuildScript(OP_TOALTSTACK, subs[0], OP_FROMALTSTACK); 824 case Fragment::WRAP_S: return BuildScript(OP_SWAP, subs[0]); 825 case Fragment::WRAP_C: return BuildScript(std::move(subs[0]), verify ? OP_CHECKSIGVERIFY : OP_CHECKSIG); 826 case Fragment::WRAP_D: return BuildScript(OP_DUP, OP_IF, subs[0], OP_ENDIF); 827 case Fragment::WRAP_V: { 828 if (node.subs[0].GetType() << "x"_mst) { 829 return BuildScript(std::move(subs[0]), OP_VERIFY); 830 } else { 831 return std::move(subs[0]); 832 } 833 } 834 case Fragment::WRAP_J: return BuildScript(OP_SIZE, OP_0NOTEQUAL, OP_IF, subs[0], OP_ENDIF); 835 case Fragment::WRAP_N: return BuildScript(std::move(subs[0]), OP_0NOTEQUAL); 836 case Fragment::JUST_1: return BuildScript(OP_1); 837 case Fragment::JUST_0: return BuildScript(OP_0); 838 case Fragment::AND_V: return BuildScript(std::move(subs[0]), subs[1]); 839 case Fragment::AND_B: return BuildScript(std::move(subs[0]), subs[1], OP_BOOLAND); 840 case Fragment::OR_B: return BuildScript(std::move(subs[0]), subs[1], OP_BOOLOR); 841 case Fragment::OR_D: return BuildScript(std::move(subs[0]), OP_IFDUP, OP_NOTIF, subs[1], OP_ENDIF); 842 case Fragment::OR_C: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[1], OP_ENDIF); 843 case Fragment::OR_I: return BuildScript(OP_IF, subs[0], OP_ELSE, subs[1], OP_ENDIF); 844 case Fragment::ANDOR: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[2], OP_ELSE, subs[1], OP_ENDIF); 845 case Fragment::MULTI: { 846 CHECK_NONFATAL(!is_tapscript); 847 CScript script = BuildScript(node.k); 848 for (const auto& key : node.keys) { 849 script = BuildScript(std::move(script), ctx.ToPKBytes(key)); 850 } 851 return BuildScript(std::move(script), node.keys.size(), verify ? OP_CHECKMULTISIGVERIFY : OP_CHECKMULTISIG); 852 } 853 case Fragment::MULTI_A: { 854 CHECK_NONFATAL(is_tapscript); 855 CScript script = BuildScript(ctx.ToPKBytes(*node.keys.begin()), OP_CHECKSIG); 856 for (auto it = node.keys.begin() + 1; it != node.keys.end(); ++it) { 857 script = BuildScript(std::move(script), ctx.ToPKBytes(*it), OP_CHECKSIGADD); 858 } 859 return BuildScript(std::move(script), node.k, verify ? OP_NUMEQUALVERIFY : OP_NUMEQUAL); 860 } 861 case Fragment::THRESH: { 862 CScript script = std::move(subs[0]); 863 for (size_t i = 1; i < subs.size(); ++i) { 864 script = BuildScript(std::move(script), subs[i], OP_ADD); 865 } 866 return BuildScript(std::move(script), node.k, verify ? OP_EQUALVERIFY : OP_EQUAL); 867 } 868 } 869 assert(false); 870 }; 871 return TreeEval<CScript>(false, downfn, upfn); 872 } 873 874 template<typename CTx> 875 std::optional<std::string> ToString(const CTx& ctx) const { 876 bool dummy{false}; 877 return ToString(ctx, dummy); 878 } 879 880 template<typename CTx> 881 std::optional<std::string> ToString(const CTx& ctx, bool& has_priv_key) const { 882 // To construct the std::string representation for a Miniscript object, we use 883 // the TreeEvalMaybe algorithm. The State is a boolean: whether the parent node is a 884 // wrapper. If so, non-wrapper expressions must be prefixed with a ":". 885 auto downfn = [](bool, const Node& node, size_t) { 886 return (node.fragment == Fragment::WRAP_A || node.fragment == Fragment::WRAP_S || 887 node.fragment == Fragment::WRAP_D || node.fragment == Fragment::WRAP_V || 888 node.fragment == Fragment::WRAP_J || node.fragment == Fragment::WRAP_N || 889 node.fragment == Fragment::WRAP_C || 890 (node.fragment == Fragment::AND_V && node.subs[1].fragment == Fragment::JUST_1) || 891 (node.fragment == Fragment::OR_I && node.subs[0].fragment == Fragment::JUST_0) || 892 (node.fragment == Fragment::OR_I && node.subs[1].fragment == Fragment::JUST_0)); 893 }; 894 auto toString = [&ctx, &has_priv_key](Key key) -> std::optional<std::string> { 895 bool fragment_has_priv_key{false}; 896 auto key_str{ctx.ToString(key, fragment_has_priv_key)}; 897 if (key_str) has_priv_key = has_priv_key || fragment_has_priv_key; 898 return key_str; 899 }; 900 // The upward function computes for a node, given whether its parent is a wrapper, 901 // and the string representations of its child nodes, the string representation of the node. 902 const bool is_tapscript{IsTapscript(m_script_ctx)}; 903 auto upfn = [is_tapscript, &toString](bool wrapped, const Node& node, std::span<std::string> subs) -> std::optional<std::string> { 904 std::string ret = wrapped ? ":" : ""; 905 906 switch (node.fragment) { 907 case Fragment::WRAP_A: return "a" + std::move(subs[0]); 908 case Fragment::WRAP_S: return "s" + std::move(subs[0]); 909 case Fragment::WRAP_C: 910 if (node.subs[0].fragment == Fragment::PK_K) { 911 // pk(K) is syntactic sugar for c:pk_k(K) 912 auto key_str = toString(node.subs[0].keys[0]); 913 if (!key_str) return {}; 914 return std::move(ret) + "pk(" + std::move(*key_str) + ")"; 915 } 916 if (node.subs[0].fragment == Fragment::PK_H) { 917 // pkh(K) is syntactic sugar for c:pk_h(K) 918 auto key_str = toString(node.subs[0].keys[0]); 919 if (!key_str) return {}; 920 return std::move(ret) + "pkh(" + std::move(*key_str) + ")"; 921 } 922 return "c" + std::move(subs[0]); 923 case Fragment::WRAP_D: return "d" + std::move(subs[0]); 924 case Fragment::WRAP_V: return "v" + std::move(subs[0]); 925 case Fragment::WRAP_J: return "j" + std::move(subs[0]); 926 case Fragment::WRAP_N: return "n" + std::move(subs[0]); 927 case Fragment::AND_V: 928 // t:X is syntactic sugar for and_v(X,1). 929 if (node.subs[1].fragment == Fragment::JUST_1) return "t" + std::move(subs[0]); 930 break; 931 case Fragment::OR_I: 932 if (node.subs[0].fragment == Fragment::JUST_0) return "l" + std::move(subs[1]); 933 if (node.subs[1].fragment == Fragment::JUST_0) return "u" + std::move(subs[0]); 934 break; 935 default: break; 936 } 937 switch (node.fragment) { 938 case Fragment::PK_K: { 939 auto key_str = toString(node.keys[0]); 940 if (!key_str) return {}; 941 return std::move(ret) + "pk_k(" + std::move(*key_str) + ")"; 942 } 943 case Fragment::PK_H: { 944 auto key_str = toString(node.keys[0]); 945 if (!key_str) return {}; 946 return std::move(ret) + "pk_h(" + std::move(*key_str) + ")"; 947 } 948 case Fragment::AFTER: return std::move(ret) + "after(" + util::ToString(node.k) + ")"; 949 case Fragment::OLDER: return std::move(ret) + "older(" + util::ToString(node.k) + ")"; 950 case Fragment::HASH256: return std::move(ret) + "hash256(" + HexStr(node.data) + ")"; 951 case Fragment::HASH160: return std::move(ret) + "hash160(" + HexStr(node.data) + ")"; 952 case Fragment::SHA256: return std::move(ret) + "sha256(" + HexStr(node.data) + ")"; 953 case Fragment::RIPEMD160: return std::move(ret) + "ripemd160(" + HexStr(node.data) + ")"; 954 case Fragment::JUST_1: return std::move(ret) + "1"; 955 case Fragment::JUST_0: return std::move(ret) + "0"; 956 case Fragment::AND_V: return std::move(ret) + "and_v(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")"; 957 case Fragment::AND_B: return std::move(ret) + "and_b(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")"; 958 case Fragment::OR_B: return std::move(ret) + "or_b(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")"; 959 case Fragment::OR_D: return std::move(ret) + "or_d(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")"; 960 case Fragment::OR_C: return std::move(ret) + "or_c(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")"; 961 case Fragment::OR_I: return std::move(ret) + "or_i(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")"; 962 case Fragment::ANDOR: 963 // and_n(X,Y) is syntactic sugar for andor(X,Y,0). 964 if (node.subs[2].fragment == Fragment::JUST_0) return std::move(ret) + "and_n(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")"; 965 return std::move(ret) + "andor(" + std::move(subs[0]) + "," + std::move(subs[1]) + "," + std::move(subs[2]) + ")"; 966 case Fragment::MULTI: { 967 CHECK_NONFATAL(!is_tapscript); 968 auto str = std::move(ret) + "multi(" + util::ToString(node.k); 969 for (const auto& key : node.keys) { 970 auto key_str = toString(key); 971 if (!key_str) return {}; 972 str += "," + std::move(*key_str); 973 } 974 return std::move(str) + ")"; 975 } 976 case Fragment::MULTI_A: { 977 CHECK_NONFATAL(is_tapscript); 978 auto str = std::move(ret) + "multi_a(" + util::ToString(node.k); 979 for (const auto& key : node.keys) { 980 auto key_str = toString(key); 981 if (!key_str) return {}; 982 str += "," + std::move(*key_str); 983 } 984 return std::move(str) + ")"; 985 } 986 case Fragment::THRESH: { 987 auto str = std::move(ret) + "thresh(" + util::ToString(node.k); 988 for (auto& sub : subs) { 989 str += "," + std::move(sub); 990 } 991 return std::move(str) + ")"; 992 } 993 default: break; 994 } 995 assert(false); 996 }; 997 998 return TreeEvalMaybe<std::string>(false, downfn, upfn); 999 } 1000 1001 private: 1002 internal::Ops CalcOps() const { 1003 switch (fragment) { 1004 case Fragment::JUST_1: return {0, 0, {}}; 1005 case Fragment::JUST_0: return {0, {}, 0}; 1006 case Fragment::PK_K: return {0, 0, 0}; 1007 case Fragment::PK_H: return {3, 0, 0}; 1008 case Fragment::OLDER: 1009 case Fragment::AFTER: return {1, 0, {}}; 1010 case Fragment::SHA256: 1011 case Fragment::RIPEMD160: 1012 case Fragment::HASH256: 1013 case Fragment::HASH160: return {4, 0, {}}; 1014 case Fragment::AND_V: return {subs[0].ops.count + subs[1].ops.count, subs[0].ops.sat + subs[1].ops.sat, {}}; 1015 case Fragment::AND_B: { 1016 const auto count{1 + subs[0].ops.count + subs[1].ops.count}; 1017 const auto sat{subs[0].ops.sat + subs[1].ops.sat}; 1018 const auto dsat{subs[0].ops.dsat + subs[1].ops.dsat}; 1019 return {count, sat, dsat}; 1020 } 1021 case Fragment::OR_B: { 1022 const auto count{1 + subs[0].ops.count + subs[1].ops.count}; 1023 const auto sat{(subs[0].ops.sat + subs[1].ops.dsat) | (subs[1].ops.sat + subs[0].ops.dsat)}; 1024 const auto dsat{subs[0].ops.dsat + subs[1].ops.dsat}; 1025 return {count, sat, dsat}; 1026 } 1027 case Fragment::OR_D: { 1028 const auto count{3 + subs[0].ops.count + subs[1].ops.count}; 1029 const auto sat{subs[0].ops.sat | (subs[1].ops.sat + subs[0].ops.dsat)}; 1030 const auto dsat{subs[0].ops.dsat + subs[1].ops.dsat}; 1031 return {count, sat, dsat}; 1032 } 1033 case Fragment::OR_C: { 1034 const auto count{2 + subs[0].ops.count + subs[1].ops.count}; 1035 const auto sat{subs[0].ops.sat | (subs[1].ops.sat + subs[0].ops.dsat)}; 1036 return {count, sat, {}}; 1037 } 1038 case Fragment::OR_I: { 1039 const auto count{3 + subs[0].ops.count + subs[1].ops.count}; 1040 const auto sat{subs[0].ops.sat | subs[1].ops.sat}; 1041 const auto dsat{subs[0].ops.dsat | subs[1].ops.dsat}; 1042 return {count, sat, dsat}; 1043 } 1044 case Fragment::ANDOR: { 1045 const auto count{3 + subs[0].ops.count + subs[1].ops.count + subs[2].ops.count}; 1046 const auto sat{(subs[1].ops.sat + subs[0].ops.sat) | (subs[0].ops.dsat + subs[2].ops.sat)}; 1047 const auto dsat{subs[0].ops.dsat + subs[2].ops.dsat}; 1048 return {count, sat, dsat}; 1049 } 1050 case Fragment::MULTI: return {1, (uint32_t)keys.size(), (uint32_t)keys.size()}; 1051 case Fragment::MULTI_A: return {(uint32_t)keys.size() + 1, 0, 0}; 1052 case Fragment::WRAP_S: 1053 case Fragment::WRAP_C: 1054 case Fragment::WRAP_N: return {1 + subs[0].ops.count, subs[0].ops.sat, subs[0].ops.dsat}; 1055 case Fragment::WRAP_A: return {2 + subs[0].ops.count, subs[0].ops.sat, subs[0].ops.dsat}; 1056 case Fragment::WRAP_D: return {3 + subs[0].ops.count, subs[0].ops.sat, 0}; 1057 case Fragment::WRAP_J: return {4 + subs[0].ops.count, subs[0].ops.sat, 0}; 1058 case Fragment::WRAP_V: return {subs[0].ops.count + (subs[0].GetType() << "x"_mst), subs[0].ops.sat, {}}; 1059 case Fragment::THRESH: { 1060 uint32_t count = 0; 1061 auto sats = Vector(internal::MaxInt<uint32_t>(0)); 1062 for (const auto& sub : subs) { 1063 count += sub.ops.count + 1; 1064 auto next_sats = Vector(sats[0] + sub.ops.dsat); 1065 for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub.ops.dsat) | (sats[j - 1] + sub.ops.sat)); 1066 next_sats.push_back(sats[sats.size() - 1] + sub.ops.sat); 1067 sats = std::move(next_sats); 1068 } 1069 assert(k < sats.size()); 1070 return {count, sats[k], sats[0]}; 1071 } 1072 } 1073 assert(false); 1074 } 1075 1076 internal::StackSize CalcStackSize() const { 1077 using namespace internal; 1078 switch (fragment) { 1079 case Fragment::JUST_0: return {{}, SatInfo::Push()}; 1080 case Fragment::JUST_1: return {SatInfo::Push(), {}}; 1081 case Fragment::OLDER: 1082 case Fragment::AFTER: return {SatInfo::Push() + SatInfo::Nop(), {}}; 1083 case Fragment::PK_K: return {SatInfo::Push()}; 1084 case Fragment::PK_H: return {SatInfo::OP_DUP() + SatInfo::Hash() + SatInfo::Push() + SatInfo::OP_EQUALVERIFY()}; 1085 case Fragment::SHA256: 1086 case Fragment::RIPEMD160: 1087 case Fragment::HASH256: 1088 case Fragment::HASH160: return { 1089 SatInfo::OP_SIZE() + SatInfo::Push() + SatInfo::OP_EQUALVERIFY() + SatInfo::Hash() + SatInfo::Push() + SatInfo::OP_EQUAL(), 1090 {} 1091 }; 1092 case Fragment::ANDOR: { 1093 const auto& x{subs[0].ss}; 1094 const auto& y{subs[1].ss}; 1095 const auto& z{subs[2].ss}; 1096 return { 1097 (x.Sat() + SatInfo::If() + y.Sat()) | (x.Dsat() + SatInfo::If() + z.Sat()), 1098 x.Dsat() + SatInfo::If() + z.Dsat() 1099 }; 1100 } 1101 case Fragment::AND_V: { 1102 const auto& x{subs[0].ss}; 1103 const auto& y{subs[1].ss}; 1104 return {x.Sat() + y.Sat(), {}}; 1105 } 1106 case Fragment::AND_B: { 1107 const auto& x{subs[0].ss}; 1108 const auto& y{subs[1].ss}; 1109 return {x.Sat() + y.Sat() + SatInfo::BinaryOp(), x.Dsat() + y.Dsat() + SatInfo::BinaryOp()}; 1110 } 1111 case Fragment::OR_B: { 1112 const auto& x{subs[0].ss}; 1113 const auto& y{subs[1].ss}; 1114 return { 1115 ((x.Sat() + y.Dsat()) | (x.Dsat() + y.Sat())) + SatInfo::BinaryOp(), 1116 x.Dsat() + y.Dsat() + SatInfo::BinaryOp() 1117 }; 1118 } 1119 case Fragment::OR_C: { 1120 const auto& x{subs[0].ss}; 1121 const auto& y{subs[1].ss}; 1122 return {(x.Sat() + SatInfo::If()) | (x.Dsat() + SatInfo::If() + y.Sat()), {}}; 1123 } 1124 case Fragment::OR_D: { 1125 const auto& x{subs[0].ss}; 1126 const auto& y{subs[1].ss}; 1127 return { 1128 (x.Sat() + SatInfo::OP_IFDUP(true) + SatInfo::If()) | (x.Dsat() + SatInfo::OP_IFDUP(false) + SatInfo::If() + y.Sat()), 1129 x.Dsat() + SatInfo::OP_IFDUP(false) + SatInfo::If() + y.Dsat() 1130 }; 1131 } 1132 case Fragment::OR_I: { 1133 const auto& x{subs[0].ss}; 1134 const auto& y{subs[1].ss}; 1135 return {SatInfo::If() + (x.Sat() | y.Sat()), SatInfo::If() + (x.Dsat() | y.Dsat())}; 1136 } 1137 // multi(k, key1, key2, ..., key_n) starts off with k+1 stack elements (a 0, plus k 1138 // signatures), then reaches n+k+3 stack elements after pushing the n keys, plus k and 1139 // n itself, and ends with 1 stack element (success or failure). Thus, it net removes 1140 // k elements (from k+1 to 1), while reaching k+n+2 more than it ends with. 1141 case Fragment::MULTI: return {SatInfo(k, k + keys.size() + 2)}; 1142 // multi_a(k, key1, key2, ..., key_n) starts off with n stack elements (the 1143 // signatures), reaches 1 more (after the first key push), and ends with 1. Thus it net 1144 // removes n-1 elements (from n to 1) while reaching n more than it ends with. 1145 case Fragment::MULTI_A: return {SatInfo(keys.size() - 1, keys.size())}; 1146 case Fragment::WRAP_A: 1147 case Fragment::WRAP_N: 1148 case Fragment::WRAP_S: return subs[0].ss; 1149 case Fragment::WRAP_C: return { 1150 subs[0].ss.Sat() + SatInfo::OP_CHECKSIG(), 1151 subs[0].ss.Dsat() + SatInfo::OP_CHECKSIG() 1152 }; 1153 case Fragment::WRAP_D: return { 1154 SatInfo::OP_DUP() + SatInfo::If() + subs[0].ss.Sat(), 1155 SatInfo::OP_DUP() + SatInfo::If() 1156 }; 1157 case Fragment::WRAP_V: return {subs[0].ss.Sat() + SatInfo::OP_VERIFY(), {}}; 1158 case Fragment::WRAP_J: return { 1159 SatInfo::OP_SIZE() + SatInfo::OP_0NOTEQUAL() + SatInfo::If() + subs[0].ss.Sat(), 1160 SatInfo::OP_SIZE() + SatInfo::OP_0NOTEQUAL() + SatInfo::If() 1161 }; 1162 case Fragment::THRESH: { 1163 // sats[j] is the SatInfo corresponding to all traces reaching j satisfactions. 1164 auto sats = Vector(SatInfo::Empty()); 1165 for (size_t i = 0; i < subs.size(); ++i) { 1166 // Loop over the subexpressions, processing them one by one. After adding 1167 // element i we need to add OP_ADD (if i>0). 1168 auto add = i ? SatInfo::BinaryOp() : SatInfo::Empty(); 1169 // Construct a variable that will become the next sats, starting with index 0. 1170 auto next_sats = Vector(sats[0] + subs[i].ss.Dsat() + add); 1171 // Then loop to construct next_sats[1..i]. 1172 for (size_t j = 1; j < sats.size(); ++j) { 1173 next_sats.push_back(((sats[j] + subs[i].ss.Dsat()) | (sats[j - 1] + subs[i].ss.Sat())) + add); 1174 } 1175 // Finally construct next_sats[i+1]. 1176 next_sats.push_back(sats[sats.size() - 1] + subs[i].ss.Sat() + add); 1177 // Switch over. 1178 sats = std::move(next_sats); 1179 } 1180 // To satisfy thresh we need k satisfactions; to dissatisfy we need 0. In both 1181 // cases a push of k and an OP_EQUAL follow. 1182 return { 1183 sats[k] + SatInfo::Push() + SatInfo::OP_EQUAL(), 1184 sats[0] + SatInfo::Push() + SatInfo::OP_EQUAL() 1185 }; 1186 } 1187 } 1188 assert(false); 1189 } 1190 1191 internal::WitnessSize CalcWitnessSize() const { 1192 const uint32_t sig_size = IsTapscript(m_script_ctx) ? 1 + 65 : 1 + 72; 1193 const uint32_t pubkey_size = IsTapscript(m_script_ctx) ? 1 + 32 : 1 + 33; 1194 switch (fragment) { 1195 case Fragment::JUST_0: return {{}, 0}; 1196 case Fragment::JUST_1: 1197 case Fragment::OLDER: 1198 case Fragment::AFTER: return {0, {}}; 1199 case Fragment::PK_K: return {sig_size, 1}; 1200 case Fragment::PK_H: return {sig_size + pubkey_size, 1 + pubkey_size}; 1201 case Fragment::SHA256: 1202 case Fragment::RIPEMD160: 1203 case Fragment::HASH256: 1204 case Fragment::HASH160: return {1 + 32, {}}; 1205 case Fragment::ANDOR: { 1206 const auto sat{(subs[0].ws.sat + subs[1].ws.sat) | (subs[0].ws.dsat + subs[2].ws.sat)}; 1207 const auto dsat{subs[0].ws.dsat + subs[2].ws.dsat}; 1208 return {sat, dsat}; 1209 } 1210 case Fragment::AND_V: return {subs[0].ws.sat + subs[1].ws.sat, {}}; 1211 case Fragment::AND_B: return {subs[0].ws.sat + subs[1].ws.sat, subs[0].ws.dsat + subs[1].ws.dsat}; 1212 case Fragment::OR_B: { 1213 const auto sat{(subs[0].ws.dsat + subs[1].ws.sat) | (subs[0].ws.sat + subs[1].ws.dsat)}; 1214 const auto dsat{subs[0].ws.dsat + subs[1].ws.dsat}; 1215 return {sat, dsat}; 1216 } 1217 case Fragment::OR_C: return {subs[0].ws.sat | (subs[0].ws.dsat + subs[1].ws.sat), {}}; 1218 case Fragment::OR_D: return {subs[0].ws.sat | (subs[0].ws.dsat + subs[1].ws.sat), subs[0].ws.dsat + subs[1].ws.dsat}; 1219 case Fragment::OR_I: return {(subs[0].ws.sat + 1 + 1) | (subs[1].ws.sat + 1), (subs[0].ws.dsat + 1 + 1) | (subs[1].ws.dsat + 1)}; 1220 case Fragment::MULTI: return {k * sig_size + 1, k + 1}; 1221 case Fragment::MULTI_A: return {k * sig_size + static_cast<uint32_t>(keys.size()) - k, static_cast<uint32_t>(keys.size())}; 1222 case Fragment::WRAP_A: 1223 case Fragment::WRAP_N: 1224 case Fragment::WRAP_S: 1225 case Fragment::WRAP_C: return subs[0].ws; 1226 case Fragment::WRAP_D: return {1 + 1 + subs[0].ws.sat, 1}; 1227 case Fragment::WRAP_V: return {subs[0].ws.sat, {}}; 1228 case Fragment::WRAP_J: return {subs[0].ws.sat, 1}; 1229 case Fragment::THRESH: { 1230 auto sats = Vector(internal::MaxInt<uint32_t>(0)); 1231 for (const auto& sub : subs) { 1232 auto next_sats = Vector(sats[0] + sub.ws.dsat); 1233 for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub.ws.dsat) | (sats[j - 1] + sub.ws.sat)); 1234 next_sats.push_back(sats[sats.size() - 1] + sub.ws.sat); 1235 sats = std::move(next_sats); 1236 } 1237 assert(k < sats.size()); 1238 return {sats[k], sats[0]}; 1239 } 1240 } 1241 assert(false); 1242 } 1243 1244 template<typename Ctx> 1245 internal::InputResult ProduceInput(const Ctx& ctx) const { 1246 using namespace internal; 1247 1248 // Internal function which is invoked for every tree node, constructing satisfaction/dissatisfactions 1249 // given those of its subnodes. 1250 auto helper = [&ctx](const Node& node, std::span<InputResult> subres) -> InputResult { 1251 switch (node.fragment) { 1252 case Fragment::PK_K: { 1253 std::vector<unsigned char> sig; 1254 Availability avail = ctx.Sign(node.keys[0], sig); 1255 return {ZERO, InputStack(std::move(sig)).SetWithSig().SetAvailable(avail)}; 1256 } 1257 case Fragment::PK_H: { 1258 std::vector<unsigned char> key = ctx.ToPKBytes(node.keys[0]), sig; 1259 Availability avail = ctx.Sign(node.keys[0], sig); 1260 return {ZERO + InputStack(key), (InputStack(std::move(sig)).SetWithSig() + InputStack(key)).SetAvailable(avail)}; 1261 } 1262 case Fragment::MULTI_A: { 1263 // sats[j] represents the best stack containing j valid signatures (out of the first i keys). 1264 // In the loop below, these stacks are built up using a dynamic programming approach. 1265 std::vector<InputStack> sats = Vector(EMPTY); 1266 for (size_t i = 0; i < node.keys.size(); ++i) { 1267 // Get the signature for the i'th key in reverse order (the signature for the first key needs to 1268 // be at the top of the stack, contrary to CHECKMULTISIG's satisfaction). 1269 std::vector<unsigned char> sig; 1270 Availability avail = ctx.Sign(node.keys[node.keys.size() - 1 - i], sig); 1271 // Compute signature stack for just this key. 1272 auto sat = InputStack(std::move(sig)).SetWithSig().SetAvailable(avail); 1273 // Compute the next sats vector: next_sats[0] is a copy of sats[0] (no signatures). All further 1274 // next_sats[j] are equal to either the existing sats[j] + ZERO, or sats[j-1] plus a signature 1275 // for the current (i'th) key. The very last element needs all signatures filled. 1276 std::vector<InputStack> next_sats; 1277 next_sats.push_back(sats[0] + ZERO); 1278 for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + ZERO) | (std::move(sats[j - 1]) + sat)); 1279 next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(sat)); 1280 // Switch over. 1281 sats = std::move(next_sats); 1282 } 1283 // The dissatisfaction consists of as many empty vectors as there are keys, which is the same as 1284 // satisfying 0 keys. 1285 auto& nsat{sats[0]}; 1286 CHECK_NONFATAL(node.k != 0); 1287 assert(node.k < sats.size()); 1288 return {std::move(nsat), std::move(sats[node.k])}; 1289 } 1290 case Fragment::MULTI: { 1291 // sats[j] represents the best stack containing j valid signatures (out of the first i keys). 1292 // In the loop below, these stacks are built up using a dynamic programming approach. 1293 // sats[0] starts off being {0}, due to the CHECKMULTISIG bug that pops off one element too many. 1294 std::vector<InputStack> sats = Vector(ZERO); 1295 for (size_t i = 0; i < node.keys.size(); ++i) { 1296 std::vector<unsigned char> sig; 1297 Availability avail = ctx.Sign(node.keys[i], sig); 1298 // Compute signature stack for just the i'th key. 1299 auto sat = InputStack(std::move(sig)).SetWithSig().SetAvailable(avail); 1300 // Compute the next sats vector: next_sats[0] is a copy of sats[0] (no signatures). All further 1301 // next_sats[j] are equal to either the existing sats[j], or sats[j-1] plus a signature for the 1302 // current (i'th) key. The very last element needs all signatures filled. 1303 std::vector<InputStack> next_sats; 1304 next_sats.push_back(sats[0]); 1305 for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back(sats[j] | (std::move(sats[j - 1]) + sat)); 1306 next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(sat)); 1307 // Switch over. 1308 sats = std::move(next_sats); 1309 } 1310 // The dissatisfaction consists of k+1 stack elements all equal to 0. 1311 InputStack nsat = ZERO; 1312 for (size_t i = 0; i < node.k; ++i) nsat = std::move(nsat) + ZERO; 1313 assert(node.k < sats.size()); 1314 return {std::move(nsat), std::move(sats[node.k])}; 1315 } 1316 case Fragment::THRESH: { 1317 // sats[k] represents the best stack that satisfies k out of the *last* i subexpressions. 1318 // In the loop below, these stacks are built up using a dynamic programming approach. 1319 // sats[0] starts off empty. 1320 std::vector<InputStack> sats = Vector(EMPTY); 1321 for (size_t i = 0; i < subres.size(); ++i) { 1322 // Introduce an alias for the i'th last satisfaction/dissatisfaction. 1323 auto& res = subres[subres.size() - i - 1]; 1324 // Compute the next sats vector: next_sats[0] is sats[0] plus res.nsat (thus containing all dissatisfactions 1325 // so far. next_sats[j] is either sats[j] + res.nsat (reusing j earlier satisfactions) or sats[j-1] + res.sat 1326 // (reusing j-1 earlier satisfactions plus a new one). The very last next_sats[j] is all satisfactions. 1327 std::vector<InputStack> next_sats; 1328 next_sats.push_back(sats[0] + res.nsat); 1329 for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + res.nsat) | (std::move(sats[j - 1]) + res.sat)); 1330 next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(res.sat)); 1331 // Switch over. 1332 sats = std::move(next_sats); 1333 } 1334 // At this point, sats[k].sat is the best satisfaction for the overall thresh() node. The best dissatisfaction 1335 // is computed by gathering all sats[i].nsat for i != k. 1336 InputStack nsat = INVALID; 1337 for (size_t i = 0; i < sats.size(); ++i) { 1338 // i==k is the satisfaction; i==0 is the canonical dissatisfaction; 1339 // the rest are non-canonical (a no-signature dissatisfaction - the i=0 1340 // form - is always available) and malleable (due to overcompleteness). 1341 // Marking the solutions malleable here is not strictly necessary, as they 1342 // should already never be picked in non-malleable solutions due to the 1343 // availability of the i=0 form. 1344 if (i != 0 && i != node.k) sats[i].SetMalleable().SetNonCanon(); 1345 // Include all dissatisfactions (even these non-canonical ones) in nsat. 1346 if (i != node.k) nsat = std::move(nsat) | std::move(sats[i]); 1347 } 1348 assert(node.k < sats.size()); 1349 return {std::move(nsat), std::move(sats[node.k])}; 1350 } 1351 case Fragment::OLDER: { 1352 return {INVALID, ctx.CheckOlder(node.k) ? EMPTY : INVALID}; 1353 } 1354 case Fragment::AFTER: { 1355 return {INVALID, ctx.CheckAfter(node.k) ? EMPTY : INVALID}; 1356 } 1357 case Fragment::SHA256: { 1358 std::vector<unsigned char> preimage; 1359 Availability avail = ctx.SatSHA256(node.data, preimage); 1360 return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)}; 1361 } 1362 case Fragment::RIPEMD160: { 1363 std::vector<unsigned char> preimage; 1364 Availability avail = ctx.SatRIPEMD160(node.data, preimage); 1365 return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)}; 1366 } 1367 case Fragment::HASH256: { 1368 std::vector<unsigned char> preimage; 1369 Availability avail = ctx.SatHASH256(node.data, preimage); 1370 return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)}; 1371 } 1372 case Fragment::HASH160: { 1373 std::vector<unsigned char> preimage; 1374 Availability avail = ctx.SatHASH160(node.data, preimage); 1375 return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)}; 1376 } 1377 case Fragment::AND_V: { 1378 auto& x = subres[0], &y = subres[1]; 1379 // As the dissatisfaction here only consist of a single option, it doesn't 1380 // actually need to be listed (it's not required for reasoning about malleability of 1381 // other options), and is never required (no valid miniscript relies on the ability 1382 // to satisfy the type V left subexpression). It's still listed here for 1383 // completeness, as a hypothetical (not currently implemented) satisfier that doesn't 1384 // care about malleability might in some cases prefer it still. 1385 return {(y.nsat + x.sat).SetNonCanon(), y.sat + x.sat}; 1386 } 1387 case Fragment::AND_B: { 1388 auto& x = subres[0], &y = subres[1]; 1389 // Note that it is not strictly necessary to mark the 2nd and 3rd dissatisfaction here 1390 // as malleable. While they are definitely malleable, they are also non-canonical due 1391 // to the guaranteed existence of a no-signature other dissatisfaction (the 1st) 1392 // option. Because of that, the 2nd and 3rd option will never be chosen, even if they 1393 // weren't marked as malleable. 1394 return {(y.nsat + x.nsat) | (y.sat + x.nsat).SetMalleable().SetNonCanon() | (y.nsat + x.sat).SetMalleable().SetNonCanon(), y.sat + x.sat}; 1395 } 1396 case Fragment::OR_B: { 1397 auto& x = subres[0], &z = subres[1]; 1398 // The (sat(Z) sat(X)) solution is overcomplete (attacker can change either into dsat). 1399 return {z.nsat + x.nsat, (z.nsat + x.sat) | (z.sat + x.nsat) | (z.sat + x.sat).SetMalleable().SetNonCanon()}; 1400 } 1401 case Fragment::OR_C: { 1402 auto& x = subres[0], &z = subres[1]; 1403 return {INVALID, std::move(x.sat) | (z.sat + x.nsat)}; 1404 } 1405 case Fragment::OR_D: { 1406 auto& x = subres[0], &z = subres[1]; 1407 return {z.nsat + x.nsat, std::move(x.sat) | (z.sat + x.nsat)}; 1408 } 1409 case Fragment::OR_I: { 1410 auto& x = subres[0], &z = subres[1]; 1411 return {(x.nsat + ONE) | (z.nsat + ZERO), (x.sat + ONE) | (z.sat + ZERO)}; 1412 } 1413 case Fragment::ANDOR: { 1414 auto& x = subres[0], &y = subres[1], &z = subres[2]; 1415 return {(y.nsat + x.sat).SetNonCanon() | (z.nsat + x.nsat), (y.sat + x.sat) | (z.sat + x.nsat)}; 1416 } 1417 case Fragment::WRAP_A: 1418 case Fragment::WRAP_S: 1419 case Fragment::WRAP_C: 1420 case Fragment::WRAP_N: 1421 return std::move(subres[0]); 1422 case Fragment::WRAP_D: { 1423 auto &x = subres[0]; 1424 return {ZERO, x.sat + ONE}; 1425 } 1426 case Fragment::WRAP_J: { 1427 auto &x = subres[0]; 1428 // If a dissatisfaction with a nonzero top stack element exists, an alternative dissatisfaction exists. 1429 // As the dissatisfaction logic currently doesn't keep track of this nonzeroness property, and thus even 1430 // if a dissatisfaction with a top zero element is found, we don't know whether another one with a 1431 // nonzero top stack element exists. Make the conservative assumption that whenever the subexpression is weakly 1432 // dissatisfiable, this alternative dissatisfaction exists and leads to malleability. 1433 return {InputStack(ZERO).SetMalleable(x.nsat.available != Availability::NO && !x.nsat.has_sig), std::move(x.sat)}; 1434 } 1435 case Fragment::WRAP_V: { 1436 auto &x = subres[0]; 1437 return {INVALID, std::move(x.sat)}; 1438 } 1439 case Fragment::JUST_0: return {EMPTY, INVALID}; 1440 case Fragment::JUST_1: return {INVALID, EMPTY}; 1441 } 1442 assert(false); 1443 return {INVALID, INVALID}; 1444 }; 1445 1446 auto tester = [&helper](const Node& node, std::span<InputResult> subres) -> InputResult { 1447 auto ret = helper(node, subres); 1448 1449 // Do a consistency check between the satisfaction code and the type checker 1450 // (the actual satisfaction code in ProduceInputHelper does not use GetType) 1451 1452 // For 'z' nodes, available satisfactions/dissatisfactions must have stack size 0. 1453 if (node.GetType() << "z"_mst && ret.nsat.available != Availability::NO) CHECK_NONFATAL(ret.nsat.stack.size() == 0); 1454 if (node.GetType() << "z"_mst && ret.sat.available != Availability::NO) CHECK_NONFATAL(ret.sat.stack.size() == 0); 1455 1456 // For 'o' nodes, available satisfactions/dissatisfactions must have stack size 1. 1457 if (node.GetType() << "o"_mst && ret.nsat.available != Availability::NO) CHECK_NONFATAL(ret.nsat.stack.size() == 1); 1458 if (node.GetType() << "o"_mst && ret.sat.available != Availability::NO) CHECK_NONFATAL(ret.sat.stack.size() == 1); 1459 1460 // For 'n' nodes, available satisfactions/dissatisfactions must have stack size 1 or larger. For satisfactions, 1461 // the top element cannot be 0. 1462 if (node.GetType() << "n"_mst && ret.sat.available != Availability::NO) CHECK_NONFATAL(ret.sat.stack.size() >= 1); 1463 if (node.GetType() << "n"_mst && ret.nsat.available != Availability::NO) CHECK_NONFATAL(ret.nsat.stack.size() >= 1); 1464 if (node.GetType() << "n"_mst && ret.sat.available != Availability::NO) CHECK_NONFATAL(!ret.sat.stack.back().empty()); 1465 1466 // For 'd' nodes, a dissatisfaction must exist, and they must not need a signature. If it is non-malleable, 1467 // it must be canonical. 1468 if (node.GetType() << "d"_mst) CHECK_NONFATAL(ret.nsat.available != Availability::NO); 1469 if (node.GetType() << "d"_mst) CHECK_NONFATAL(!ret.nsat.has_sig); 1470 if (node.GetType() << "d"_mst && !ret.nsat.malleable) CHECK_NONFATAL(!ret.nsat.non_canon); 1471 1472 // For 'f'/'s' nodes, dissatisfactions/satisfactions must have a signature. 1473 if (node.GetType() << "f"_mst && ret.nsat.available != Availability::NO) CHECK_NONFATAL(ret.nsat.has_sig); 1474 if (node.GetType() << "s"_mst && ret.sat.available != Availability::NO) CHECK_NONFATAL(ret.sat.has_sig); 1475 1476 // For non-malleable 'e' nodes, a non-malleable dissatisfaction must exist. 1477 if (node.GetType() << "me"_mst) CHECK_NONFATAL(ret.nsat.available != Availability::NO); 1478 if (node.GetType() << "me"_mst) CHECK_NONFATAL(!ret.nsat.malleable); 1479 1480 // For 'm' nodes, if a satisfaction exists, it must be non-malleable. 1481 if (node.GetType() << "m"_mst && ret.sat.available != Availability::NO) CHECK_NONFATAL(!ret.sat.malleable); 1482 1483 // If a non-malleable satisfaction exists, it must be canonical. 1484 if (ret.sat.available != Availability::NO && !ret.sat.malleable) CHECK_NONFATAL(!ret.sat.non_canon); 1485 1486 return ret; 1487 }; 1488 1489 return TreeEval<InputResult>(tester); 1490 } 1491 1492 public: 1493 /** Update duplicate key information in this Node. 1494 * 1495 * This uses a custom key comparator provided by the context in order to still detect duplicates 1496 * for more complicated types. 1497 */ 1498 template<typename Ctx> void DuplicateKeyCheck(const Ctx& ctx) const 1499 { 1500 // We cannot use a lambda here, as lambdas are non assignable, and the set operations 1501 // below require moving the comparators around. 1502 struct Comp { 1503 const Ctx* ctx_ptr; 1504 Comp(const Ctx& ctx) : ctx_ptr(&ctx) {} 1505 bool operator()(const Key& a, const Key& b) const { return ctx_ptr->KeyCompare(a, b); } 1506 }; 1507 1508 // state in the recursive computation: 1509 // - std::nullopt means "this node has duplicates" 1510 // - an std::set means "this node has no duplicate keys, and they are: ...". 1511 using keyset = std::set<Key, Comp>; 1512 using state = std::optional<keyset>; 1513 1514 auto upfn = [&ctx](const Node& node, std::span<state> subs) -> state { 1515 // If this node is already known to have duplicates, nothing left to do. 1516 if (node.has_duplicate_keys.has_value() && *node.has_duplicate_keys) return {}; 1517 1518 // Check if one of the children is already known to have duplicates. 1519 for (auto& sub : subs) { 1520 if (!sub.has_value()) { 1521 node.has_duplicate_keys = true; 1522 return {}; 1523 } 1524 } 1525 1526 // Start building the set of keys involved in this node and children. 1527 // Start by keys in this node directly. 1528 size_t keys_count = node.keys.size(); 1529 keyset key_set{node.keys.begin(), node.keys.end(), Comp(ctx)}; 1530 if (key_set.size() != keys_count) { 1531 // It already has duplicates; bail out. 1532 node.has_duplicate_keys = true; 1533 return {}; 1534 } 1535 1536 // Merge the keys from the children into this set. 1537 for (auto& sub : subs) { 1538 keys_count += sub->size(); 1539 // Small optimization: std::set::merge is linear in the size of the second arg but 1540 // logarithmic in the size of the first. 1541 if (key_set.size() < sub->size()) std::swap(key_set, *sub); 1542 key_set.merge(*sub); 1543 if (key_set.size() != keys_count) { 1544 node.has_duplicate_keys = true; 1545 return {}; 1546 } 1547 } 1548 1549 node.has_duplicate_keys = false; 1550 return key_set; 1551 }; 1552 1553 TreeEval<state>(upfn); 1554 } 1555 1556 //! Return the size of the script for this expression (faster than ToScript().size()). 1557 size_t ScriptSize() const { return scriptlen; } 1558 1559 //! Return the maximum number of ops needed to satisfy this script non-malleably. 1560 std::optional<uint32_t> GetOps() const { 1561 if (!ops.sat.Valid()) return {}; 1562 return ops.count + ops.sat.Value(); 1563 } 1564 1565 //! Return the number of ops in the script (not counting the dynamic ones that depend on execution). 1566 uint32_t GetStaticOps() const { return ops.count; } 1567 1568 //! Check the ops limit of this script against the consensus limit. 1569 bool CheckOpsLimit() const { 1570 if (IsTapscript(m_script_ctx)) return true; 1571 if (const auto ops = GetOps()) return *ops <= MAX_OPS_PER_SCRIPT; 1572 return true; 1573 } 1574 1575 /** Whether this node is of type B, K or W. (That is, anything but V.) */ 1576 bool IsBKW() const { 1577 return !((GetType() & "BKW"_mst) == ""_mst); 1578 } 1579 1580 /** Return the maximum number of stack elements needed to satisfy this script non-malleably. */ 1581 std::optional<uint32_t> GetStackSize() const { 1582 if (!ss.Sat().Valid()) return {}; 1583 return ss.Sat().NetDiff() + static_cast<int32_t>(IsBKW()); 1584 } 1585 1586 //! Return the maximum size of the stack during execution of this script. 1587 std::optional<uint32_t> GetExecStackSize() const { 1588 if (!ss.Sat().Valid()) return {}; 1589 return ss.Sat().Exec() + static_cast<int32_t>(IsBKW()); 1590 } 1591 1592 //! Check the maximum stack size for this script against the policy limit. 1593 bool CheckStackSize() const { 1594 // Since in Tapscript there is no standardness limit on the script and witness sizes, we may run 1595 // into the maximum stack size while executing the script. Make sure it doesn't happen. 1596 if (IsTapscript(m_script_ctx)) { 1597 if (const auto exec_ss = GetExecStackSize()) return exec_ss <= MAX_STACK_SIZE; 1598 return true; 1599 } 1600 if (const auto ss = GetStackSize()) return *ss <= MAX_STANDARD_P2WSH_STACK_ITEMS; 1601 return true; 1602 } 1603 1604 //! Whether no satisfaction exists for this node. 1605 bool IsNotSatisfiable() const { return !GetStackSize(); } 1606 1607 /** Return the maximum size in bytes of a witness to satisfy this script non-malleably. Note this does 1608 * not include the witness script push. */ 1609 std::optional<uint32_t> GetWitnessSize() const { 1610 if (!ws.sat.Valid()) return {}; 1611 return ws.sat.Value(); 1612 } 1613 1614 //! Return the expression type. 1615 Type GetType() const { return typ; } 1616 1617 //! Return the script context for this node. 1618 MiniscriptContext GetMsCtx() const { return m_script_ctx; } 1619 1620 //! Find an insane subnode which has no insane children. Nullptr if there is none. 1621 const Node* FindInsaneSub() const { 1622 return TreeEval<const Node*>([](const Node& node, std::span<const Node*> subs) -> const Node* { 1623 for (auto& sub: subs) if (sub) return sub; 1624 if (!node.IsSaneSubexpression()) return &node; 1625 return nullptr; 1626 }); 1627 } 1628 1629 //! Determine whether a Miniscript node is satisfiable. fn(node) will be invoked for all 1630 //! key, time, and hashing nodes, and should return their satisfiability. 1631 template<typename F> 1632 bool IsSatisfiable(F fn) const 1633 { 1634 // TreeEval() doesn't support bool as NodeType, so use int instead. 1635 return TreeEval<int>([&fn](const Node& node, std::span<int> subs) -> bool { 1636 switch (node.fragment) { 1637 case Fragment::JUST_0: 1638 return false; 1639 case Fragment::JUST_1: 1640 return true; 1641 case Fragment::PK_K: 1642 case Fragment::PK_H: 1643 case Fragment::MULTI: 1644 case Fragment::MULTI_A: 1645 case Fragment::AFTER: 1646 case Fragment::OLDER: 1647 case Fragment::HASH256: 1648 case Fragment::HASH160: 1649 case Fragment::SHA256: 1650 case Fragment::RIPEMD160: 1651 return bool{fn(node)}; 1652 case Fragment::ANDOR: 1653 return (subs[0] && subs[1]) || subs[2]; 1654 case Fragment::AND_V: 1655 case Fragment::AND_B: 1656 return subs[0] && subs[1]; 1657 case Fragment::OR_B: 1658 case Fragment::OR_C: 1659 case Fragment::OR_D: 1660 case Fragment::OR_I: 1661 return subs[0] || subs[1]; 1662 case Fragment::THRESH: 1663 return static_cast<uint32_t>(std::count(subs.begin(), subs.end(), true)) >= node.k; 1664 default: // wrappers 1665 assert(subs.size() >= 1); 1666 CHECK_NONFATAL(subs.size() == 1); 1667 return subs[0]; 1668 } 1669 }); 1670 } 1671 1672 //! Check whether this node is valid at all. 1673 bool IsValid() const { 1674 if (GetType() == ""_mst) return false; 1675 return ScriptSize() <= internal::MaxScriptSize(m_script_ctx); 1676 } 1677 1678 //! Check whether this node is valid as a script on its own. 1679 bool IsValidTopLevel() const { return IsValid() && GetType() << "B"_mst; } 1680 1681 //! Check whether this script can always be satisfied in a non-malleable way. 1682 bool IsNonMalleable() const { return GetType() << "m"_mst; } 1683 1684 //! Check whether this script always needs a signature. 1685 bool NeedsSignature() const { return GetType() << "s"_mst; } 1686 1687 //! Check whether there is no satisfaction path that contains both timelocks and heightlocks 1688 bool CheckTimeLocksMix() const { return GetType() << "k"_mst; } 1689 1690 //! Check whether there is no duplicate key across this fragment and all its sub-fragments. 1691 bool CheckDuplicateKey() const { return has_duplicate_keys && !*has_duplicate_keys; } 1692 1693 //! Whether successful non-malleable satisfactions are guaranteed to be valid. 1694 bool ValidSatisfactions() const { return IsValid() && CheckOpsLimit() && CheckStackSize(); } 1695 1696 //! Whether the apparent policy of this node matches its script semantics. Doesn't guarantee it is a safe script on its own. 1697 bool IsSaneSubexpression() const { return ValidSatisfactions() && IsNonMalleable() && CheckTimeLocksMix() && CheckDuplicateKey(); } 1698 1699 //! Check whether this node is safe as a script on its own. 1700 bool IsSane() const { return IsValidTopLevel() && IsSaneSubexpression() && NeedsSignature(); } 1701 1702 //! Produce a witness for this script, if possible and given the information available in the context. 1703 //! The non-malleable satisfaction is guaranteed to be valid if it exists, and ValidSatisfaction() 1704 //! is true. If IsSane() holds, this satisfaction is guaranteed to succeed in case the node's 1705 //! conditions are satisfied (private keys and hash preimages available, locktimes satisfied). 1706 template<typename Ctx> 1707 Availability Satisfy(const Ctx& ctx, std::vector<std::vector<unsigned char>>& stack, bool nonmalleable = true) const { 1708 auto ret = ProduceInput(ctx); 1709 if (nonmalleable && (ret.sat.malleable || !ret.sat.has_sig)) return Availability::NO; 1710 stack = std::move(ret.sat.stack); 1711 return ret.sat.available; 1712 } 1713 1714 //! Equality testing. 1715 bool operator==(const Node<Key>& arg) const { return Compare(*this, arg) == 0; } 1716 1717 // Constructors with various argument combinations, which bypass the duplicate key check. 1718 Node(internal::NoDupCheck, MiniscriptContext script_ctx, enum Fragment nt, std::vector<Node> sub, std::vector<unsigned char> arg, uint32_t val = 0) 1719 : fragment(nt), k(val), data(std::move(arg)), subs(std::move(sub)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {} 1720 Node(internal::NoDupCheck, MiniscriptContext script_ctx, enum Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0) 1721 : fragment(nt), k(val), data(std::move(arg)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {} 1722 Node(internal::NoDupCheck, MiniscriptContext script_ctx, enum Fragment nt, std::vector<Node> sub, std::vector<Key> key, uint32_t val = 0) 1723 : fragment(nt), k(val), keys(std::move(key)), m_script_ctx{script_ctx}, subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {} 1724 Node(internal::NoDupCheck, MiniscriptContext script_ctx, enum Fragment nt, std::vector<Key> key, uint32_t val = 0) 1725 : fragment(nt), k(val), keys(std::move(key)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {} 1726 Node(internal::NoDupCheck, MiniscriptContext script_ctx, enum Fragment nt, std::vector<Node> sub, uint32_t val = 0) 1727 : fragment(nt), k(val), subs(std::move(sub)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {} 1728 Node(internal::NoDupCheck, MiniscriptContext script_ctx, enum Fragment nt, uint32_t val = 0) 1729 : fragment(nt), k(val), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {} 1730 1731 // Constructors with various argument combinations, which do perform the duplicate key check. 1732 template <typename Ctx> Node(const Ctx& ctx, enum Fragment nt, std::vector<Node> sub, std::vector<unsigned char> arg, uint32_t val = 0) 1733 : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(sub), std::move(arg), val) { DuplicateKeyCheck(ctx); } 1734 template <typename Ctx> Node(const Ctx& ctx, enum Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0) 1735 : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(arg), val) { DuplicateKeyCheck(ctx);} 1736 template <typename Ctx> Node(const Ctx& ctx, enum Fragment nt, std::vector<Node> sub, std::vector<Key> key, uint32_t val = 0) 1737 : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(sub), std::move(key), val) { DuplicateKeyCheck(ctx); } 1738 template <typename Ctx> Node(const Ctx& ctx, enum Fragment nt, std::vector<Key> key, uint32_t val = 0) 1739 : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(key), val) { DuplicateKeyCheck(ctx); } 1740 template <typename Ctx> Node(const Ctx& ctx, enum Fragment nt, std::vector<Node> sub, uint32_t val = 0) 1741 : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(sub), val) { DuplicateKeyCheck(ctx); } 1742 template <typename Ctx> Node(const Ctx& ctx, enum Fragment nt, uint32_t val = 0) 1743 : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, val) { DuplicateKeyCheck(ctx); } 1744 1745 // Delete copy constructor and assignment operator, use Clone() instead 1746 Node(const Node&) = delete; 1747 Node& operator=(const Node&) = delete; 1748 1749 // subs is movable, circumventing recursion, so these are permitted. 1750 Node(Node&&) noexcept = default; 1751 Node& operator=(Node&&) noexcept = default; 1752 }; 1753 1754 namespace internal { 1755 1756 enum class ParseContext { 1757 /** An expression which may be begin with wrappers followed by a colon. */ 1758 WRAPPED_EXPR, 1759 /** A miniscript expression which does not begin with wrappers. */ 1760 EXPR, 1761 1762 /** SWAP wraps the top constructed node with s: */ 1763 SWAP, 1764 /** ALT wraps the top constructed node with a: */ 1765 ALT, 1766 /** CHECK wraps the top constructed node with c: */ 1767 CHECK, 1768 /** DUP_IF wraps the top constructed node with d: */ 1769 DUP_IF, 1770 /** VERIFY wraps the top constructed node with v: */ 1771 VERIFY, 1772 /** NON_ZERO wraps the top constructed node with j: */ 1773 NON_ZERO, 1774 /** ZERO_NOTEQUAL wraps the top constructed node with n: */ 1775 ZERO_NOTEQUAL, 1776 /** WRAP_U will construct an or_i(X,0) node from the top constructed node. */ 1777 WRAP_U, 1778 /** WRAP_T will construct an and_v(X,1) node from the top constructed node. */ 1779 WRAP_T, 1780 1781 /** AND_N will construct an andor(X,Y,0) node from the last two constructed nodes. */ 1782 AND_N, 1783 /** AND_V will construct an and_v node from the last two constructed nodes. */ 1784 AND_V, 1785 /** AND_B will construct an and_b node from the last two constructed nodes. */ 1786 AND_B, 1787 /** ANDOR will construct an andor node from the last three constructed nodes. */ 1788 ANDOR, 1789 /** OR_B will construct an or_b node from the last two constructed nodes. */ 1790 OR_B, 1791 /** OR_C will construct an or_c node from the last two constructed nodes. */ 1792 OR_C, 1793 /** OR_D will construct an or_d node from the last two constructed nodes. */ 1794 OR_D, 1795 /** OR_I will construct an or_i node from the last two constructed nodes. */ 1796 OR_I, 1797 1798 /** THRESH will read a wrapped expression, and then look for a COMMA. If 1799 * no comma follows, it will construct a thresh node from the appropriate 1800 * number of constructed children. Otherwise, it will recurse with another 1801 * THRESH. */ 1802 THRESH, 1803 1804 /** COMMA expects the next element to be ',' and fails if not. */ 1805 COMMA, 1806 /** CLOSE_BRACKET expects the next element to be ')' and fails if not. */ 1807 CLOSE_BRACKET, 1808 }; 1809 1810 int FindNextChar(std::span<const char> in, char m); 1811 1812 /** Parse a key expression fully contained within a fragment with the name given by 'func' */ 1813 template<typename Key, typename Ctx> 1814 std::optional<Key> ParseKey(const std::string& func, std::span<const char>& in, const Ctx& ctx) 1815 { 1816 std::span<const char> expr = script::Expr(in); 1817 if (!script::Func(func, expr)) return {}; 1818 return ctx.FromString(expr); 1819 } 1820 1821 /** Parse a hex string fully contained within a fragment with the name given by 'func' */ 1822 template<typename Ctx> 1823 std::optional<std::vector<unsigned char>> ParseHexStr(const std::string& func, std::span<const char>& in, const size_t expected_size, 1824 const Ctx& ctx) 1825 { 1826 std::span<const char> expr = script::Expr(in); 1827 if (!script::Func(func, expr)) return {}; 1828 std::string val = std::string(expr.begin(), expr.end()); 1829 if (!IsHex(val)) return {}; 1830 auto hash = ParseHex(val); 1831 if (hash.size() != expected_size) return {}; 1832 return hash; 1833 } 1834 1835 /** BuildBack pops the last two elements off `constructed` and wraps them in the specified Fragment */ 1836 template<typename Key> 1837 void BuildBack(const MiniscriptContext script_ctx, Fragment nt, std::vector<Node<Key>>& constructed, const bool reverse = false) 1838 { 1839 Node<Key> child{std::move(constructed.back())}; 1840 constructed.pop_back(); 1841 if (reverse) { 1842 constructed.back() = Node<Key>{internal::NoDupCheck{}, script_ctx, nt, Vector(std::move(child), std::move(constructed.back()))}; 1843 } else { 1844 constructed.back() = Node<Key>{internal::NoDupCheck{}, script_ctx, nt, Vector(std::move(constructed.back()), std::move(child))}; 1845 } 1846 } 1847 1848 /** 1849 * Parse a miniscript from its textual descriptor form. 1850 * This does not check whether the script is valid, let alone sane. The caller is expected to use 1851 * the `IsValidTopLevel()` and `IsSaneTopLevel()` to check for these properties on the node. 1852 */ 1853 template <typename Key, typename Ctx> 1854 inline std::optional<Node<Key>> Parse(std::span<const char> in, const Ctx& ctx) 1855 { 1856 using namespace script; 1857 1858 // Account for the minimum script size for all parsed fragments so far. It "borrows" 1 1859 // script byte from all leaf nodes, counting it instead whenever a space for a recursive 1860 // expression is added (through andor, and_*, or_*, thresh). This guarantees that all fragments 1861 // increment the script_size by at least one, except for: 1862 // - "0", "1": these leafs are only a single byte, so their subtracted-from increment is 0. 1863 // This is not an issue however, as "space" for them has to be created by combinators, 1864 // which do increment script_size. 1865 // - "v:": the v wrapper adds nothing as in some cases it results in no opcode being added 1866 // (instead transforming another opcode into its VERIFY form). However, the v: wrapper has 1867 // to be interleaved with other fragments to be valid, so this is not a concern. 1868 size_t script_size{1}; 1869 size_t max_size{internal::MaxScriptSize(ctx.MsContext())}; 1870 1871 // The two integers are used to hold state for thresh() 1872 std::vector<std::tuple<ParseContext, int64_t, int64_t>> to_parse; 1873 std::vector<Node<Key>> constructed; 1874 1875 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1); 1876 1877 // Parses a multi() or multi_a() from its string representation. Returns false on parsing error. 1878 const auto parse_multi_exp = [&](std::span<const char>& in, const bool is_multi_a) -> bool { 1879 const auto max_keys{is_multi_a ? MAX_PUBKEYS_PER_MULTI_A : MAX_PUBKEYS_PER_MULTISIG}; 1880 const auto required_ctx{is_multi_a ? MiniscriptContext::TAPSCRIPT : MiniscriptContext::P2WSH}; 1881 if (ctx.MsContext() != required_ctx) return false; 1882 // Get threshold 1883 int next_comma = FindNextChar(in, ','); 1884 if (next_comma < 1) return false; 1885 const auto k_to_integral{ToIntegral<int64_t>(std::string_view(in.data(), next_comma))}; 1886 if (!k_to_integral.has_value()) return false; 1887 const int64_t k{k_to_integral.value()}; 1888 in = in.subspan(next_comma + 1); 1889 // Get keys. It is compatible for both compressed and x-only keys. 1890 std::vector<Key> keys; 1891 while (next_comma != -1) { 1892 next_comma = FindNextChar(in, ','); 1893 int key_length = (next_comma == -1) ? FindNextChar(in, ')') : next_comma; 1894 if (key_length < 1) return false; 1895 std::span<const char> sp{in.begin(), in.begin() + key_length}; 1896 auto key = ctx.FromString(sp); 1897 if (!key) return false; 1898 keys.push_back(std::move(*key)); 1899 in = in.subspan(key_length + 1); 1900 } 1901 if (keys.size() < 1 || keys.size() > max_keys) return false; 1902 if (k < 1 || k > (int64_t)keys.size()) return false; 1903 if (is_multi_a) { 1904 // (push + xonly-key + CHECKSIG[ADD]) * n + k + OP_NUMEQUAL(VERIFY), minus one. 1905 script_size += (1 + 32 + 1) * keys.size() + BuildScript(k).size(); 1906 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI_A, std::move(keys), k); 1907 } else { 1908 script_size += 2 + (keys.size() > 16) + (k > 16) + 34 * keys.size(); 1909 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI, std::move(keys), k); 1910 } 1911 return true; 1912 }; 1913 1914 while (!to_parse.empty()) { 1915 if (script_size > max_size) return {}; 1916 1917 // Get the current context we are decoding within 1918 auto [cur_context, n, k] = to_parse.back(); 1919 to_parse.pop_back(); 1920 1921 switch (cur_context) { 1922 case ParseContext::WRAPPED_EXPR: { 1923 std::optional<size_t> colon_index{}; 1924 for (size_t i = 1; i < in.size(); ++i) { 1925 if (in[i] == ':') { 1926 colon_index = i; 1927 break; 1928 } 1929 if (in[i] < 'a' || in[i] > 'z') break; 1930 } 1931 // If there is no colon, this loop won't execute 1932 bool last_was_v{false}; 1933 for (size_t j = 0; colon_index && j < *colon_index; ++j) { 1934 if (script_size > max_size) return {}; 1935 if (in[j] == 'a') { 1936 script_size += 2; 1937 to_parse.emplace_back(ParseContext::ALT, -1, -1); 1938 } else if (in[j] == 's') { 1939 script_size += 1; 1940 to_parse.emplace_back(ParseContext::SWAP, -1, -1); 1941 } else if (in[j] == 'c') { 1942 script_size += 1; 1943 to_parse.emplace_back(ParseContext::CHECK, -1, -1); 1944 } else if (in[j] == 'd') { 1945 script_size += 3; 1946 to_parse.emplace_back(ParseContext::DUP_IF, -1, -1); 1947 } else if (in[j] == 'j') { 1948 script_size += 4; 1949 to_parse.emplace_back(ParseContext::NON_ZERO, -1, -1); 1950 } else if (in[j] == 'n') { 1951 script_size += 1; 1952 to_parse.emplace_back(ParseContext::ZERO_NOTEQUAL, -1, -1); 1953 } else if (in[j] == 'v') { 1954 // do not permit "...vv...:"; it's not valid, and also doesn't trigger early 1955 // failure as script_size isn't incremented. 1956 if (last_was_v) return {}; 1957 to_parse.emplace_back(ParseContext::VERIFY, -1, -1); 1958 } else if (in[j] == 'u') { 1959 script_size += 4; 1960 to_parse.emplace_back(ParseContext::WRAP_U, -1, -1); 1961 } else if (in[j] == 't') { 1962 script_size += 1; 1963 to_parse.emplace_back(ParseContext::WRAP_T, -1, -1); 1964 } else if (in[j] == 'l') { 1965 // The l: wrapper is equivalent to or_i(0,X) 1966 script_size += 4; 1967 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0); 1968 to_parse.emplace_back(ParseContext::OR_I, -1, -1); 1969 } else { 1970 return {}; 1971 } 1972 last_was_v = (in[j] == 'v'); 1973 } 1974 to_parse.emplace_back(ParseContext::EXPR, -1, -1); 1975 if (colon_index) in = in.subspan(*colon_index + 1); 1976 break; 1977 } 1978 case ParseContext::EXPR: { 1979 if (Const("0", in)) { 1980 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0); 1981 } else if (Const("1", in)) { 1982 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_1); 1983 } else if (Const("pk(", in, /*skip=*/false)) { 1984 std::optional<Key> key = ParseKey<Key, Ctx>("pk", in, ctx); 1985 if (!key) return {}; 1986 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_C, Vector(Node<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_K, Vector(std::move(*key))))); 1987 script_size += IsTapscript(ctx.MsContext()) ? 33 : 34; 1988 } else if (Const("pkh(", in, /*skip=*/false)) { 1989 std::optional<Key> key = ParseKey<Key, Ctx>("pkh", in, ctx); 1990 if (!key) return {}; 1991 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_C, Vector(Node<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_H, Vector(std::move(*key))))); 1992 script_size += 24; 1993 } else if (Const("pk_k(", in, /*skip=*/false)) { 1994 std::optional<Key> key = ParseKey<Key, Ctx>("pk_k", in, ctx); 1995 if (!key) return {}; 1996 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_K, Vector(std::move(*key))); 1997 script_size += IsTapscript(ctx.MsContext()) ? 32 : 33; 1998 } else if (Const("pk_h(", in, /*skip=*/false)) { 1999 std::optional<Key> key = ParseKey<Key, Ctx>("pk_h", in, ctx); 2000 if (!key) return {}; 2001 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_H, Vector(std::move(*key))); 2002 script_size += 23; 2003 } else if (Const("sha256(", in, /*skip=*/false)) { 2004 std::optional<std::vector<unsigned char>> hash = ParseHexStr("sha256", in, 32, ctx); 2005 if (!hash) return {}; 2006 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::SHA256, std::move(*hash)); 2007 script_size += 38; 2008 } else if (Const("ripemd160(", in, /*skip=*/false)) { 2009 std::optional<std::vector<unsigned char>> hash = ParseHexStr("ripemd160", in, 20, ctx); 2010 if (!hash) return {}; 2011 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::RIPEMD160, std::move(*hash)); 2012 script_size += 26; 2013 } else if (Const("hash256(", in, /*skip=*/false)) { 2014 std::optional<std::vector<unsigned char>> hash = ParseHexStr("hash256", in, 32, ctx); 2015 if (!hash) return {}; 2016 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::HASH256, std::move(*hash)); 2017 script_size += 38; 2018 } else if (Const("hash160(", in, /*skip=*/false)) { 2019 std::optional<std::vector<unsigned char>> hash = ParseHexStr("hash160", in, 20, ctx); 2020 if (!hash) return {}; 2021 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::HASH160, std::move(*hash)); 2022 script_size += 26; 2023 } else if (Const("after(", in, /*skip=*/false)) { 2024 auto expr = Expr(in); 2025 if (!Func("after", expr)) return {}; 2026 const auto num{ToIntegral<int64_t>(std::string_view(expr.begin(), expr.end()))}; 2027 if (!num.has_value() || *num < 1 || *num >= 0x80000000L) return {}; 2028 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::AFTER, *num); 2029 script_size += 1 + (*num > 16) + (*num > 0x7f) + (*num > 0x7fff) + (*num > 0x7fffff); 2030 } else if (Const("older(", in, /*skip=*/false)) { 2031 auto expr = Expr(in); 2032 if (!Func("older", expr)) return {}; 2033 const auto num{ToIntegral<int64_t>(std::string_view(expr.begin(), expr.end()))}; 2034 if (!num.has_value() || *num < 1 || *num >= 0x80000000L) return {}; 2035 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::OLDER, *num); 2036 script_size += 1 + (*num > 16) + (*num > 0x7f) + (*num > 0x7fff) + (*num > 0x7fffff); 2037 } else if (Const("multi(", in)) { 2038 if (!parse_multi_exp(in, /* is_multi_a = */false)) return {}; 2039 } else if (Const("multi_a(", in)) { 2040 if (!parse_multi_exp(in, /* is_multi_a = */true)) return {}; 2041 } else if (Const("thresh(", in)) { 2042 int next_comma = FindNextChar(in, ','); 2043 if (next_comma < 1) return {}; 2044 const auto k{ToIntegral<int64_t>(std::string_view(in.data(), next_comma))}; 2045 if (!k.has_value() || *k < 1) return {}; 2046 in = in.subspan(next_comma + 1); 2047 // n = 1 here because we read the first WRAPPED_EXPR before reaching THRESH 2048 to_parse.emplace_back(ParseContext::THRESH, 1, *k); 2049 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1); 2050 script_size += 2 + (*k > 16) + (*k > 0x7f) + (*k > 0x7fff) + (*k > 0x7fffff); 2051 } else if (Const("andor(", in)) { 2052 to_parse.emplace_back(ParseContext::ANDOR, -1, -1); 2053 to_parse.emplace_back(ParseContext::CLOSE_BRACKET, -1, -1); 2054 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1); 2055 to_parse.emplace_back(ParseContext::COMMA, -1, -1); 2056 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1); 2057 to_parse.emplace_back(ParseContext::COMMA, -1, -1); 2058 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1); 2059 script_size += 5; 2060 } else { 2061 if (Const("and_n(", in)) { 2062 to_parse.emplace_back(ParseContext::AND_N, -1, -1); 2063 script_size += 5; 2064 } else if (Const("and_b(", in)) { 2065 to_parse.emplace_back(ParseContext::AND_B, -1, -1); 2066 script_size += 2; 2067 } else if (Const("and_v(", in)) { 2068 to_parse.emplace_back(ParseContext::AND_V, -1, -1); 2069 script_size += 1; 2070 } else if (Const("or_b(", in)) { 2071 to_parse.emplace_back(ParseContext::OR_B, -1, -1); 2072 script_size += 2; 2073 } else if (Const("or_c(", in)) { 2074 to_parse.emplace_back(ParseContext::OR_C, -1, -1); 2075 script_size += 3; 2076 } else if (Const("or_d(", in)) { 2077 to_parse.emplace_back(ParseContext::OR_D, -1, -1); 2078 script_size += 4; 2079 } else if (Const("or_i(", in)) { 2080 to_parse.emplace_back(ParseContext::OR_I, -1, -1); 2081 script_size += 4; 2082 } else { 2083 return {}; 2084 } 2085 to_parse.emplace_back(ParseContext::CLOSE_BRACKET, -1, -1); 2086 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1); 2087 to_parse.emplace_back(ParseContext::COMMA, -1, -1); 2088 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1); 2089 } 2090 break; 2091 } 2092 case ParseContext::ALT: { 2093 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_A, Vector(std::move(constructed.back()))}; 2094 break; 2095 } 2096 case ParseContext::SWAP: { 2097 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_S, Vector(std::move(constructed.back()))}; 2098 break; 2099 } 2100 case ParseContext::CHECK: { 2101 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_C, Vector(std::move(constructed.back()))}; 2102 break; 2103 } 2104 case ParseContext::DUP_IF: { 2105 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_D, Vector(std::move(constructed.back()))}; 2106 break; 2107 } 2108 case ParseContext::NON_ZERO: { 2109 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_J, Vector(std::move(constructed.back()))}; 2110 break; 2111 } 2112 case ParseContext::ZERO_NOTEQUAL: { 2113 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_N, Vector(std::move(constructed.back()))}; 2114 break; 2115 } 2116 case ParseContext::VERIFY: { 2117 script_size += (constructed.back().GetType() << "x"_mst); 2118 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_V, Vector(std::move(constructed.back()))}; 2119 break; 2120 } 2121 case ParseContext::WRAP_U: { 2122 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::OR_I, Vector(std::move(constructed.back()), Node<Key>{internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0})}; 2123 break; 2124 } 2125 case ParseContext::WRAP_T: { 2126 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::AND_V, Vector(std::move(constructed.back()), Node<Key>{internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_1})}; 2127 break; 2128 } 2129 case ParseContext::AND_B: { 2130 BuildBack(ctx.MsContext(), Fragment::AND_B, constructed); 2131 break; 2132 } 2133 case ParseContext::AND_N: { 2134 auto mid = std::move(constructed.back()); 2135 constructed.pop_back(); 2136 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), Node<Key>{internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0})}; 2137 break; 2138 } 2139 case ParseContext::AND_V: { 2140 BuildBack(ctx.MsContext(), Fragment::AND_V, constructed); 2141 break; 2142 } 2143 case ParseContext::OR_B: { 2144 BuildBack(ctx.MsContext(), Fragment::OR_B, constructed); 2145 break; 2146 } 2147 case ParseContext::OR_C: { 2148 BuildBack(ctx.MsContext(), Fragment::OR_C, constructed); 2149 break; 2150 } 2151 case ParseContext::OR_D: { 2152 BuildBack(ctx.MsContext(), Fragment::OR_D, constructed); 2153 break; 2154 } 2155 case ParseContext::OR_I: { 2156 BuildBack(ctx.MsContext(), Fragment::OR_I, constructed); 2157 break; 2158 } 2159 case ParseContext::ANDOR: { 2160 auto right = std::move(constructed.back()); 2161 constructed.pop_back(); 2162 auto mid = std::move(constructed.back()); 2163 constructed.pop_back(); 2164 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), std::move(right))}; 2165 break; 2166 } 2167 case ParseContext::THRESH: { 2168 if (in.size() < 1) return {}; 2169 if (in[0] == ',') { 2170 in = in.subspan(1); 2171 to_parse.emplace_back(ParseContext::THRESH, n+1, k); 2172 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1); 2173 script_size += 2; 2174 } else if (in[0] == ')') { 2175 if (k > n) return {}; 2176 in = in.subspan(1); 2177 // Children are constructed in reverse order, so iterate from end to beginning 2178 std::vector<Node<Key>> subs; 2179 for (int i = 0; i < n; ++i) { 2180 subs.push_back(std::move(constructed.back())); 2181 constructed.pop_back(); 2182 } 2183 std::reverse(subs.begin(), subs.end()); 2184 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::THRESH, std::move(subs), k); 2185 } else { 2186 return {}; 2187 } 2188 break; 2189 } 2190 case ParseContext::COMMA: { 2191 if (in.size() < 1 || in[0] != ',') return {}; 2192 in = in.subspan(1); 2193 break; 2194 } 2195 case ParseContext::CLOSE_BRACKET: { 2196 if (in.size() < 1 || in[0] != ')') return {}; 2197 in = in.subspan(1); 2198 break; 2199 } 2200 } 2201 } 2202 2203 // Sanity checks on the produced miniscript 2204 assert(constructed.size() >= 1); 2205 CHECK_NONFATAL(constructed.size() == 1); 2206 assert(constructed[0].ScriptSize() == script_size); 2207 if (in.size() > 0) return {}; 2208 Node<Key> tl_node{std::move(constructed.front())}; 2209 tl_node.DuplicateKeyCheck(ctx); 2210 return tl_node; 2211 } 2212 2213 /** Decode a script into opcode/push pairs. 2214 * 2215 * Construct a vector with one element per opcode in the script, in reverse order. 2216 * Each element is a pair consisting of the opcode, as well as the data pushed by 2217 * the opcode (including OP_n), if any. OP_CHECKSIGVERIFY, OP_CHECKMULTISIGVERIFY, 2218 * OP_NUMEQUALVERIFY and OP_EQUALVERIFY are decomposed into OP_CHECKSIG, OP_CHECKMULTISIG, 2219 * OP_EQUAL and OP_NUMEQUAL respectively, plus OP_VERIFY. 2220 */ 2221 std::optional<std::vector<Opcode>> DecomposeScript(const CScript& script); 2222 2223 /** Determine whether the passed pair (created by DecomposeScript) is pushing a number. */ 2224 std::optional<int64_t> ParseScriptNumber(const Opcode& in); 2225 2226 enum class DecodeContext { 2227 /** A single expression of type B, K, or V. Specifically, this can't be an 2228 * and_v or an expression of type W (a: and s: wrappers). */ 2229 SINGLE_BKV_EXPR, 2230 /** Potentially multiple SINGLE_BKV_EXPRs as children of (potentially multiple) 2231 * and_v expressions. Syntactic sugar for MAYBE_AND_V + SINGLE_BKV_EXPR. */ 2232 BKV_EXPR, 2233 /** An expression of type W (a: or s: wrappers). */ 2234 W_EXPR, 2235 2236 /** SWAP expects the next element to be OP_SWAP (inside a W-type expression that 2237 * didn't end with FROMALTSTACK), and wraps the top of the constructed stack 2238 * with s: */ 2239 SWAP, 2240 /** ALT expects the next element to be TOALTSTACK (we must have already read a 2241 * FROMALTSTACK earlier), and wraps the top of the constructed stack with a: */ 2242 ALT, 2243 /** CHECK wraps the top constructed node with c: */ 2244 CHECK, 2245 /** DUP_IF wraps the top constructed node with d: */ 2246 DUP_IF, 2247 /** VERIFY wraps the top constructed node with v: */ 2248 VERIFY, 2249 /** NON_ZERO wraps the top constructed node with j: */ 2250 NON_ZERO, 2251 /** ZERO_NOTEQUAL wraps the top constructed node with n: */ 2252 ZERO_NOTEQUAL, 2253 2254 /** MAYBE_AND_V will check if the next part of the script could be a valid 2255 * miniscript sub-expression, and if so it will push AND_V and SINGLE_BKV_EXPR 2256 * to decode it and construct the and_v node. This is recursive, to deal with 2257 * multiple and_v nodes inside each other. */ 2258 MAYBE_AND_V, 2259 /** AND_V will construct an and_v node from the last two constructed nodes. */ 2260 AND_V, 2261 /** AND_B will construct an and_b node from the last two constructed nodes. */ 2262 AND_B, 2263 /** ANDOR will construct an andor node from the last three constructed nodes. */ 2264 ANDOR, 2265 /** OR_B will construct an or_b node from the last two constructed nodes. */ 2266 OR_B, 2267 /** OR_C will construct an or_c node from the last two constructed nodes. */ 2268 OR_C, 2269 /** OR_D will construct an or_d node from the last two constructed nodes. */ 2270 OR_D, 2271 2272 /** In a thresh expression, all sub-expressions other than the first are W-type, 2273 * and end in OP_ADD. THRESH_W will check for this OP_ADD and either push a W_EXPR 2274 * or a SINGLE_BKV_EXPR and jump to THRESH_E accordingly. */ 2275 THRESH_W, 2276 /** THRESH_E constructs a thresh node from the appropriate number of constructed 2277 * children. */ 2278 THRESH_E, 2279 2280 /** ENDIF signals that we are inside some sort of OP_IF structure, which could be 2281 * or_d, or_c, or_i, andor, d:, or j: wrapper, depending on what follows. We read 2282 * a BKV_EXPR and then deal with the next opcode case-by-case. */ 2283 ENDIF, 2284 /** If, inside an ENDIF context, we find an OP_NOTIF before finding an OP_ELSE, 2285 * we could either be in an or_d or an or_c node. We then check for IFDUP to 2286 * distinguish these cases. */ 2287 ENDIF_NOTIF, 2288 /** If, inside an ENDIF context, we find an OP_ELSE, then we could be in either an 2289 * or_i or an andor node. Read the next BKV_EXPR and find either an OP_IF or an 2290 * OP_NOTIF. */ 2291 ENDIF_ELSE, 2292 }; 2293 2294 //! Parse a miniscript from a bitcoin script 2295 template <typename Key, typename Ctx, typename I> 2296 inline std::optional<Node<Key>> DecodeScript(I& in, I last, const Ctx& ctx) 2297 { 2298 // The two integers are used to hold state for thresh() 2299 std::vector<std::tuple<DecodeContext, int64_t, int64_t>> to_parse; 2300 std::vector<Node<Key>> constructed; 2301 2302 // This is the top level, so we assume the type is B 2303 // (in particular, disallowing top level W expressions) 2304 to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1); 2305 2306 while (!to_parse.empty()) { 2307 // Exit early if the Miniscript is not going to be valid. 2308 if (!constructed.empty() && !constructed.back().IsValid()) return {}; 2309 2310 // Get the current context we are decoding within 2311 auto [cur_context, n, k] = to_parse.back(); 2312 to_parse.pop_back(); 2313 2314 switch(cur_context) { 2315 case DecodeContext::SINGLE_BKV_EXPR: { 2316 if (in >= last) return {}; 2317 2318 // Constants 2319 if (in[0].first == OP_1) { 2320 ++in; 2321 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_1); 2322 break; 2323 } 2324 if (in[0].first == OP_0) { 2325 ++in; 2326 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0); 2327 break; 2328 } 2329 // Public keys 2330 if (in[0].second.size() == 33 || in[0].second.size() == 32) { 2331 auto key = ctx.FromPKBytes(in[0].second.begin(), in[0].second.end()); 2332 if (!key) return {}; 2333 ++in; 2334 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_K, Vector(std::move(*key))); 2335 break; 2336 } 2337 if (last - in >= 5 && in[0].first == OP_VERIFY && in[1].first == OP_EQUAL && in[3].first == OP_HASH160 && in[4].first == OP_DUP && in[2].second.size() == 20) { 2338 auto key = ctx.FromPKHBytes(in[2].second.begin(), in[2].second.end()); 2339 if (!key) return {}; 2340 in += 5; 2341 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_H, Vector(std::move(*key))); 2342 break; 2343 } 2344 // Time locks 2345 std::optional<int64_t> num; 2346 if (last - in >= 2 && in[0].first == OP_CHECKSEQUENCEVERIFY && (num = ParseScriptNumber(in[1]))) { 2347 in += 2; 2348 if (*num < 1 || *num > 0x7FFFFFFFL) return {}; 2349 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::OLDER, *num); 2350 break; 2351 } 2352 if (last - in >= 2 && in[0].first == OP_CHECKLOCKTIMEVERIFY && (num = ParseScriptNumber(in[1]))) { 2353 in += 2; 2354 if (num < 1 || num > 0x7FFFFFFFL) return {}; 2355 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::AFTER, *num); 2356 break; 2357 } 2358 // Hashes 2359 if (last - in >= 7 && in[0].first == OP_EQUAL && in[3].first == OP_VERIFY && in[4].first == OP_EQUAL && (num = ParseScriptNumber(in[5])) && num == 32 && in[6].first == OP_SIZE) { 2360 if (in[2].first == OP_SHA256 && in[1].second.size() == 32) { 2361 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::SHA256, in[1].second); 2362 in += 7; 2363 break; 2364 } else if (in[2].first == OP_RIPEMD160 && in[1].second.size() == 20) { 2365 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::RIPEMD160, in[1].second); 2366 in += 7; 2367 break; 2368 } else if (in[2].first == OP_HASH256 && in[1].second.size() == 32) { 2369 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::HASH256, in[1].second); 2370 in += 7; 2371 break; 2372 } else if (in[2].first == OP_HASH160 && in[1].second.size() == 20) { 2373 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::HASH160, in[1].second); 2374 in += 7; 2375 break; 2376 } 2377 } 2378 // Multi 2379 if (last - in >= 3 && in[0].first == OP_CHECKMULTISIG) { 2380 if (IsTapscript(ctx.MsContext())) return {}; 2381 std::vector<Key> keys; 2382 const auto n = ParseScriptNumber(in[1]); 2383 if (!n || last - in < 3 + *n) return {}; 2384 if (*n < 1 || *n > 20) return {}; 2385 for (int i = 0; i < *n; ++i) { 2386 if (in[2 + i].second.size() != 33) return {}; 2387 auto key = ctx.FromPKBytes(in[2 + i].second.begin(), in[2 + i].second.end()); 2388 if (!key) return {}; 2389 keys.push_back(std::move(*key)); 2390 } 2391 const auto k = ParseScriptNumber(in[2 + *n]); 2392 if (!k || *k < 1 || *k > *n) return {}; 2393 in += 3 + *n; 2394 std::reverse(keys.begin(), keys.end()); 2395 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI, std::move(keys), *k); 2396 break; 2397 } 2398 // Tapscript's equivalent of multi 2399 if (last - in >= 4 && in[0].first == OP_NUMEQUAL) { 2400 if (!IsTapscript(ctx.MsContext())) return {}; 2401 // The necessary threshold of signatures. 2402 const auto k = ParseScriptNumber(in[1]); 2403 if (!k) return {}; 2404 if (*k < 1 || *k > MAX_PUBKEYS_PER_MULTI_A) return {}; 2405 if (last - in < 2 + *k * 2) return {}; 2406 std::vector<Key> keys; 2407 keys.reserve(*k); 2408 // Walk through the expected (pubkey, CHECKSIG[ADD]) pairs. 2409 for (int pos = 2;; pos += 2) { 2410 if (last - in < pos + 2) return {}; 2411 // Make sure it's indeed an x-only pubkey and a CHECKSIG[ADD], then parse the key. 2412 if (in[pos].first != OP_CHECKSIGADD && in[pos].first != OP_CHECKSIG) return {}; 2413 if (in[pos + 1].second.size() != 32) return {}; 2414 auto key = ctx.FromPKBytes(in[pos + 1].second.begin(), in[pos + 1].second.end()); 2415 if (!key) return {}; 2416 keys.push_back(std::move(*key)); 2417 // Make sure early we don't parse an arbitrary large expression. 2418 if (keys.size() > MAX_PUBKEYS_PER_MULTI_A) return {}; 2419 // OP_CHECKSIG means it was the last one to parse. 2420 if (in[pos].first == OP_CHECKSIG) break; 2421 } 2422 if (keys.size() < (size_t)*k) return {}; 2423 in += 2 + keys.size() * 2; 2424 std::reverse(keys.begin(), keys.end()); 2425 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI_A, std::move(keys), *k); 2426 break; 2427 } 2428 /** In the following wrappers, we only need to push SINGLE_BKV_EXPR rather 2429 * than BKV_EXPR, because and_v commutes with these wrappers. For example, 2430 * c:and_v(X,Y) produces the same script as and_v(X,c:Y). */ 2431 // c: wrapper 2432 if (in[0].first == OP_CHECKSIG) { 2433 ++in; 2434 to_parse.emplace_back(DecodeContext::CHECK, -1, -1); 2435 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1); 2436 break; 2437 } 2438 // v: wrapper 2439 if (in[0].first == OP_VERIFY) { 2440 ++in; 2441 to_parse.emplace_back(DecodeContext::VERIFY, -1, -1); 2442 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1); 2443 break; 2444 } 2445 // n: wrapper 2446 if (in[0].first == OP_0NOTEQUAL) { 2447 ++in; 2448 to_parse.emplace_back(DecodeContext::ZERO_NOTEQUAL, -1, -1); 2449 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1); 2450 break; 2451 } 2452 // Thresh 2453 if (last - in >= 3 && in[0].first == OP_EQUAL && (num = ParseScriptNumber(in[1]))) { 2454 if (*num < 1) return {}; 2455 in += 2; 2456 to_parse.emplace_back(DecodeContext::THRESH_W, 0, *num); 2457 break; 2458 } 2459 // OP_ENDIF can be WRAP_J, WRAP_D, ANDOR, OR_C, OR_D, or OR_I 2460 if (in[0].first == OP_ENDIF) { 2461 ++in; 2462 to_parse.emplace_back(DecodeContext::ENDIF, -1, -1); 2463 to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1); 2464 break; 2465 } 2466 /** In and_b and or_b nodes, we only look for SINGLE_BKV_EXPR, because 2467 * or_b(and_v(X,Y),Z) has script [X] [Y] [Z] OP_BOOLOR, the same as 2468 * and_v(X,or_b(Y,Z)). In this example, the former of these is invalid as 2469 * miniscript, while the latter is valid. So we leave the and_v "outside" 2470 * while decoding. */ 2471 // and_b 2472 if (in[0].first == OP_BOOLAND) { 2473 ++in; 2474 to_parse.emplace_back(DecodeContext::AND_B, -1, -1); 2475 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1); 2476 to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1); 2477 break; 2478 } 2479 // or_b 2480 if (in[0].first == OP_BOOLOR) { 2481 ++in; 2482 to_parse.emplace_back(DecodeContext::OR_B, -1, -1); 2483 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1); 2484 to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1); 2485 break; 2486 } 2487 // Unrecognised expression 2488 return {}; 2489 } 2490 case DecodeContext::BKV_EXPR: { 2491 to_parse.emplace_back(DecodeContext::MAYBE_AND_V, -1, -1); 2492 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1); 2493 break; 2494 } 2495 case DecodeContext::W_EXPR: { 2496 // a: wrapper 2497 if (in >= last) return {}; 2498 if (in[0].first == OP_FROMALTSTACK) { 2499 ++in; 2500 to_parse.emplace_back(DecodeContext::ALT, -1, -1); 2501 } else { 2502 to_parse.emplace_back(DecodeContext::SWAP, -1, -1); 2503 } 2504 to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1); 2505 break; 2506 } 2507 case DecodeContext::MAYBE_AND_V: { 2508 // If we reach a potential AND_V top-level, check if the next part of the script could be another AND_V child 2509 // These op-codes cannot end any well-formed miniscript so cannot be used in an and_v node. 2510 if (in < last && in[0].first != OP_IF && in[0].first != OP_ELSE && in[0].first != OP_NOTIF && in[0].first != OP_TOALTSTACK && in[0].first != OP_SWAP) { 2511 to_parse.emplace_back(DecodeContext::AND_V, -1, -1); 2512 // BKV_EXPR can contain more AND_V nodes 2513 to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1); 2514 } 2515 break; 2516 } 2517 case DecodeContext::SWAP: { 2518 if (in >= last || in[0].first != OP_SWAP || constructed.empty()) return {}; 2519 ++in; 2520 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_S, Vector(std::move(constructed.back()))}; 2521 break; 2522 } 2523 case DecodeContext::ALT: { 2524 if (in >= last || in[0].first != OP_TOALTSTACK || constructed.empty()) return {}; 2525 ++in; 2526 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_A, Vector(std::move(constructed.back()))}; 2527 break; 2528 } 2529 case DecodeContext::CHECK: { 2530 if (constructed.empty()) return {}; 2531 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_C, Vector(std::move(constructed.back()))}; 2532 break; 2533 } 2534 case DecodeContext::DUP_IF: { 2535 if (constructed.empty()) return {}; 2536 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_D, Vector(std::move(constructed.back()))}; 2537 break; 2538 } 2539 case DecodeContext::VERIFY: { 2540 if (constructed.empty()) return {}; 2541 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_V, Vector(std::move(constructed.back()))}; 2542 break; 2543 } 2544 case DecodeContext::NON_ZERO: { 2545 if (constructed.empty()) return {}; 2546 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_J, Vector(std::move(constructed.back()))}; 2547 break; 2548 } 2549 case DecodeContext::ZERO_NOTEQUAL: { 2550 if (constructed.empty()) return {}; 2551 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_N, Vector(std::move(constructed.back()))}; 2552 break; 2553 } 2554 case DecodeContext::AND_V: { 2555 if (constructed.size() < 2) return {}; 2556 BuildBack(ctx.MsContext(), Fragment::AND_V, constructed, /*reverse=*/true); 2557 break; 2558 } 2559 case DecodeContext::AND_B: { 2560 if (constructed.size() < 2) return {}; 2561 BuildBack(ctx.MsContext(), Fragment::AND_B, constructed, /*reverse=*/true); 2562 break; 2563 } 2564 case DecodeContext::OR_B: { 2565 if (constructed.size() < 2) return {}; 2566 BuildBack(ctx.MsContext(), Fragment::OR_B, constructed, /*reverse=*/true); 2567 break; 2568 } 2569 case DecodeContext::OR_C: { 2570 if (constructed.size() < 2) return {}; 2571 BuildBack(ctx.MsContext(), Fragment::OR_C, constructed, /*reverse=*/true); 2572 break; 2573 } 2574 case DecodeContext::OR_D: { 2575 if (constructed.size() < 2) return {}; 2576 BuildBack(ctx.MsContext(), Fragment::OR_D, constructed, /*reverse=*/true); 2577 break; 2578 } 2579 case DecodeContext::ANDOR: { 2580 if (constructed.size() < 3) return {}; 2581 Node left{std::move(constructed.back())}; 2582 constructed.pop_back(); 2583 Node right{std::move(constructed.back())}; 2584 constructed.pop_back(); 2585 Node mid{std::move(constructed.back())}; 2586 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::ANDOR, Vector(std::move(left), std::move(mid), std::move(right))}; 2587 break; 2588 } 2589 case DecodeContext::THRESH_W: { 2590 if (in >= last) return {}; 2591 if (in[0].first == OP_ADD) { 2592 ++in; 2593 to_parse.emplace_back(DecodeContext::THRESH_W, n+1, k); 2594 to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1); 2595 } else { 2596 to_parse.emplace_back(DecodeContext::THRESH_E, n+1, k); 2597 // All children of thresh have type modifier d, so cannot be and_v 2598 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1); 2599 } 2600 break; 2601 } 2602 case DecodeContext::THRESH_E: { 2603 if (k < 1 || k > n || constructed.size() < static_cast<size_t>(n)) return {}; 2604 std::vector<Node<Key>> subs; 2605 for (int i = 0; i < n; ++i) { 2606 Node sub{std::move(constructed.back())}; 2607 constructed.pop_back(); 2608 subs.push_back(std::move(sub)); 2609 } 2610 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::THRESH, std::move(subs), k); 2611 break; 2612 } 2613 case DecodeContext::ENDIF: { 2614 if (in >= last) return {}; 2615 2616 // could be andor or or_i 2617 if (in[0].first == OP_ELSE) { 2618 ++in; 2619 to_parse.emplace_back(DecodeContext::ENDIF_ELSE, -1, -1); 2620 to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1); 2621 } 2622 // could be j: or d: wrapper 2623 else if (in[0].first == OP_IF) { 2624 if (last - in >= 2 && in[1].first == OP_DUP) { 2625 in += 2; 2626 to_parse.emplace_back(DecodeContext::DUP_IF, -1, -1); 2627 } else if (last - in >= 3 && in[1].first == OP_0NOTEQUAL && in[2].first == OP_SIZE) { 2628 in += 3; 2629 to_parse.emplace_back(DecodeContext::NON_ZERO, -1, -1); 2630 } 2631 else { 2632 return {}; 2633 } 2634 // could be or_c or or_d 2635 } else if (in[0].first == OP_NOTIF) { 2636 ++in; 2637 to_parse.emplace_back(DecodeContext::ENDIF_NOTIF, -1, -1); 2638 } 2639 else { 2640 return {}; 2641 } 2642 break; 2643 } 2644 case DecodeContext::ENDIF_NOTIF: { 2645 if (in >= last) return {}; 2646 if (in[0].first == OP_IFDUP) { 2647 ++in; 2648 to_parse.emplace_back(DecodeContext::OR_D, -1, -1); 2649 } else { 2650 to_parse.emplace_back(DecodeContext::OR_C, -1, -1); 2651 } 2652 // or_c and or_d both require X to have type modifier d so, can't contain and_v 2653 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1); 2654 break; 2655 } 2656 case DecodeContext::ENDIF_ELSE: { 2657 if (in >= last) return {}; 2658 if (in[0].first == OP_IF) { 2659 ++in; 2660 BuildBack(ctx.MsContext(), Fragment::OR_I, constructed, /*reverse=*/true); 2661 } else if (in[0].first == OP_NOTIF) { 2662 ++in; 2663 to_parse.emplace_back(DecodeContext::ANDOR, -1, -1); 2664 // andor requires X to have type modifier d, so it can't be and_v 2665 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1); 2666 } else { 2667 return {}; 2668 } 2669 break; 2670 } 2671 } 2672 } 2673 if (constructed.size() != 1) return {}; 2674 Node tl_node{std::move(constructed.front())}; 2675 tl_node.DuplicateKeyCheck(ctx); 2676 // Note that due to how ComputeType works (only assign the type to the node if the 2677 // subs' types are valid) this would fail if any node of tree is badly typed. 2678 if (!tl_node.IsValidTopLevel()) return {}; 2679 return tl_node; 2680 } 2681 2682 } // namespace internal 2683 2684 template <typename Ctx> 2685 inline std::optional<Node<typename Ctx::Key>> FromString(const std::string& str, const Ctx& ctx) 2686 { 2687 return internal::Parse<typename Ctx::Key>(str, ctx); 2688 } 2689 2690 template <typename Ctx> 2691 inline std::optional<Node<typename Ctx::Key>> FromScript(const CScript& script, const Ctx& ctx) 2692 { 2693 using namespace internal; 2694 // A too large Script is necessarily invalid, don't bother parsing it. 2695 if (script.size() > MaxScriptSize(ctx.MsContext())) return {}; 2696 auto decomposed = DecomposeScript(script); 2697 if (!decomposed) return {}; 2698 auto it = decomposed->begin(); 2699 auto ret = DecodeScript<typename Ctx::Key>(it, decomposed->end(), ctx); 2700 if (!ret) return {}; 2701 if (it != decomposed->end()) return {}; 2702 return ret; 2703 } 2704 2705 } // namespace miniscript 2706 2707 #endif // BITCOIN_SCRIPT_MINISCRIPT_H