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 std::vector<std::vector<Node>> queue; 556 queue.push_back(std::move(subs)); 557 do { 558 auto flattening{std::move(queue.back())}; 559 queue.pop_back(); 560 for (Node& n : flattening) { 561 if (!n.subs.empty()) queue.push_back(std::move(n.subs)); 562 } 563 } while (!queue.empty()); 564 } 565 // NOLINTEND(misc-no-recursion) 566 567 Node<Key> Clone() const 568 { 569 // Use TreeEval() to avoid a stack-overflow due to recursion 570 auto upfn = [](const Node& node, std::span<Node> children) { 571 std::vector<Node> new_subs; 572 for (auto& child : children) { 573 // It's fine to move from children as they are new nodes having 574 // been produced by calling this function one level down. 575 new_subs.push_back(std::move(child)); 576 } 577 return Node{internal::NoDupCheck{}, node.m_script_ctx, node.fragment, std::move(new_subs), node.keys, node.data, node.k}; 578 }; 579 return TreeEval<Node>(upfn); 580 } 581 582 enum Fragment Fragment() const { return fragment; } 583 uint32_t K() const { return k; } 584 const std::vector<Key>& Keys() const { return keys; } 585 const std::vector<unsigned char>& Data() const { return data; } 586 const std::vector<Node>& Subs() const { return subs; } 587 588 private: 589 //! Cached ops counts. 590 internal::Ops ops; 591 //! Cached stack size bounds. 592 internal::StackSize ss; 593 //! Cached witness size bounds. 594 internal::WitnessSize ws; 595 //! Cached expression type (computed by CalcType and fed through SanitizeType). 596 Type typ; 597 //! Cached script length (computed by CalcScriptLen). 598 size_t scriptlen; 599 //! Whether a public key appears more than once in this node. This value is initialized 600 //! by all constructors except the NoDupCheck ones. The NoDupCheck ones skip the 601 //! computation, requiring it to be done manually by invoking DuplicateKeyCheck(). 602 //! DuplicateKeyCheck(), or a non-NoDupCheck constructor, will compute has_duplicate_keys 603 //! for all subnodes as well. 604 mutable std::optional<bool> has_duplicate_keys; 605 606 // Constructor which takes all of the data that a Node could possibly contain. 607 // This is kept private as no valid fragment has all of these arguments. 608 // Only used by Clone() 609 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) 610 : fragment(nt), k(val), keys(key), data(std::move(arg)), subs(std::move(sub)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {} 611 612 //! Compute the length of the script for this miniscript (including children). 613 size_t CalcScriptLen() const 614 { 615 size_t subsize = 0; 616 for (const auto& sub : subs) { 617 subsize += sub.ScriptSize(); 618 } 619 Type sub0type = subs.size() > 0 ? subs[0].GetType() : ""_mst; 620 return internal::ComputeScriptLen(fragment, sub0type, subsize, k, subs.size(), keys.size(), m_script_ctx); 621 } 622 623 /* Apply a recursive algorithm to a Miniscript tree, without actual recursive calls. 624 * 625 * The algorithm is defined by two functions: downfn and upfn. Conceptually, the 626 * result can be thought of as first using downfn to compute a "state" for each node, 627 * from the root down to the leaves. Then upfn is used to compute a "result" for each 628 * node, from the leaves back up to the root, which is then returned. In the actual 629 * implementation, both functions are invoked in an interleaved fashion, performing a 630 * depth-first traversal of the tree. 631 * 632 * In more detail, it is invoked as node.TreeEvalMaybe<Result>(root, downfn, upfn): 633 * - root is the state of the root node, of type State. 634 * - downfn is a callable (State&, const Node&, size_t) -> State, which given a 635 * node, its state, and an index of one of its children, computes the state of that 636 * child. It can modify the state. Children of a given node will have downfn() 637 * called in order. 638 * - upfn is a callable (State&&, const Node&, std::span<Result>) -> std::optional<Result>, 639 * which given a node, its state, and a span of the results of its children, 640 * computes the result of the node. If std::nullopt is returned by upfn, 641 * TreeEvalMaybe() immediately returns std::nullopt. 642 * The return value of TreeEvalMaybe is the result of the root node. 643 * 644 * Result type cannot be bool due to the std::vector<bool> specialization. 645 */ 646 template<typename Result, typename State, typename DownFn, typename UpFn> 647 std::optional<Result> TreeEvalMaybe(State root_state, DownFn downfn, UpFn upfn) const 648 { 649 /** Entries of the explicit stack tracked in this algorithm. */ 650 struct StackElem 651 { 652 const Node& node; //!< The node being evaluated. 653 size_t expanded; //!< How many children of this node have been expanded. 654 State state; //!< The state for that node. 655 656 StackElem(const Node& node_, size_t exp_, State&& state_) : 657 node(node_), expanded(exp_), state(std::move(state_)) {} 658 }; 659 /* Stack of tree nodes being explored. */ 660 std::vector<StackElem> stack; 661 /* Results of subtrees so far. Their order and mapping to tree nodes 662 * is implicitly defined by stack. */ 663 std::vector<Result> results; 664 stack.emplace_back(*this, 0, std::move(root_state)); 665 666 /* Here is a demonstration of the algorithm, for an example tree A(B,C(D,E),F). 667 * State variables are omitted for simplicity. 668 * 669 * First: stack=[(A,0)] results=[] 670 * stack=[(A,1),(B,0)] results=[] 671 * stack=[(A,1)] results=[B] 672 * stack=[(A,2),(C,0)] results=[B] 673 * stack=[(A,2),(C,1),(D,0)] results=[B] 674 * stack=[(A,2),(C,1)] results=[B,D] 675 * stack=[(A,2),(C,2),(E,0)] results=[B,D] 676 * stack=[(A,2),(C,2)] results=[B,D,E] 677 * stack=[(A,2)] results=[B,C] 678 * stack=[(A,3),(F,0)] results=[B,C] 679 * stack=[(A,3)] results=[B,C,F] 680 * Final: stack=[] results=[A] 681 */ 682 while (stack.size()) { 683 const Node& node = stack.back().node; 684 if (stack.back().expanded < node.subs.size()) { 685 /* We encounter a tree node with at least one unexpanded child. 686 * Expand it. By the time we hit this node again, the result of 687 * that child (and all earlier children) will be at the end of `results`. */ 688 size_t child_index = stack.back().expanded++; 689 State child_state = downfn(stack.back().state, node, child_index); 690 stack.emplace_back(node.subs[child_index], 0, std::move(child_state)); 691 continue; 692 } 693 // Invoke upfn with the last node.subs.size() elements of results as input. 694 assert(results.size() >= node.subs.size()); 695 std::optional<Result> result{upfn(std::move(stack.back().state), node, 696 std::span<Result>{results}.last(node.subs.size()))}; 697 // If evaluation returns std::nullopt, abort immediately. 698 if (!result) return {}; 699 // Replace the last node.subs.size() elements of results with the new result. 700 results.erase(results.end() - node.subs.size(), results.end()); 701 results.push_back(std::move(*result)); 702 stack.pop_back(); 703 } 704 // The final remaining results element is the root result, return it. 705 assert(results.size() >= 1); 706 CHECK_NONFATAL(results.size() == 1); 707 return std::move(results[0]); 708 } 709 710 /** Like TreeEvalMaybe, but without downfn or State type. 711 * upfn takes (const Node&, std::span<Result>) and returns std::optional<Result>. */ 712 template<typename Result, typename UpFn> 713 std::optional<Result> TreeEvalMaybe(UpFn upfn) const 714 { 715 struct DummyState {}; 716 return TreeEvalMaybe<Result>(DummyState{}, 717 [](DummyState, const Node&, size_t) { return DummyState{}; }, 718 [&upfn](DummyState, const Node& node, std::span<Result> subs) { 719 return upfn(node, subs); 720 } 721 ); 722 } 723 724 /** Like TreeEvalMaybe, but always produces a result. upfn must return Result. */ 725 template<typename Result, typename State, typename DownFn, typename UpFn> 726 Result TreeEval(State root_state, DownFn&& downfn, UpFn upfn) const 727 { 728 // Invoke TreeEvalMaybe with upfn wrapped to return std::optional<Result>, and then 729 // unconditionally dereference the result (it cannot be std::nullopt). 730 return std::move(*TreeEvalMaybe<Result>(std::move(root_state), 731 std::forward<DownFn>(downfn), 732 [&upfn](State&& state, const Node& node, std::span<Result> subs) { 733 Result res{upfn(std::move(state), node, subs)}; 734 return std::optional<Result>(std::move(res)); 735 } 736 )); 737 } 738 739 /** Like TreeEval, but without downfn or State type. 740 * upfn takes (const Node&, std::span<Result>) and returns Result. */ 741 template<typename Result, typename UpFn> 742 Result TreeEval(UpFn upfn) const 743 { 744 struct DummyState {}; 745 return std::move(*TreeEvalMaybe<Result>(DummyState{}, 746 [](DummyState, const Node&, size_t) { return DummyState{}; }, 747 [&upfn](DummyState, const Node& node, std::span<Result> subs) { 748 Result res{upfn(node, subs)}; 749 return std::optional<Result>(std::move(res)); 750 } 751 )); 752 } 753 754 /** Compare two miniscript subtrees, using a non-recursive algorithm. */ 755 friend int Compare(const Node<Key>& node1, const Node<Key>& node2) 756 { 757 std::vector<std::pair<const Node<Key>&, const Node<Key>&>> queue; 758 queue.emplace_back(node1, node2); 759 while (!queue.empty()) { 760 const auto& [a, b] = queue.back(); 761 queue.pop_back(); 762 if (std::tie(a.fragment, a.k, a.keys, a.data) < std::tie(b.fragment, b.k, b.keys, b.data)) return -1; 763 if (std::tie(b.fragment, b.k, b.keys, b.data) < std::tie(a.fragment, a.k, a.keys, a.data)) return 1; 764 if (a.subs.size() < b.subs.size()) return -1; 765 if (b.subs.size() < a.subs.size()) return 1; 766 size_t n = a.subs.size(); 767 for (size_t i = 0; i < n; ++i) { 768 queue.emplace_back(a.subs[n - 1 - i], b.subs[n - 1 - i]); 769 } 770 } 771 return 0; 772 } 773 774 //! Compute the type for this miniscript. 775 Type CalcType() const { 776 using namespace internal; 777 778 // THRESH has a variable number of subexpressions 779 std::vector<Type> sub_types; 780 if (fragment == Fragment::THRESH) { 781 for (const auto& sub : subs) sub_types.push_back(sub.GetType()); 782 } 783 // All other nodes than THRESH can be computed just from the types of the 0-3 subexpressions. 784 Type x = subs.size() > 0 ? subs[0].GetType() : ""_mst; 785 Type y = subs.size() > 1 ? subs[1].GetType() : ""_mst; 786 Type z = subs.size() > 2 ? subs[2].GetType() : ""_mst; 787 788 return SanitizeType(ComputeType(fragment, x, y, z, sub_types, k, data.size(), subs.size(), keys.size(), m_script_ctx)); 789 } 790 791 public: 792 template<typename Ctx> 793 CScript ToScript(const Ctx& ctx) const 794 { 795 // To construct the CScript for a Miniscript object, we use the TreeEval algorithm. 796 // The State is a boolean: whether or not the node's script expansion is followed 797 // by an OP_VERIFY (which may need to be combined with the last script opcode). 798 auto downfn = [](bool verify, const Node& node, size_t index) { 799 // For WRAP_V, the subexpression is certainly followed by OP_VERIFY. 800 if (node.fragment == Fragment::WRAP_V) return true; 801 // The subexpression of WRAP_S, and the last subexpression of AND_V 802 // inherit the followed-by-OP_VERIFY property from the parent. 803 if (node.fragment == Fragment::WRAP_S || 804 (node.fragment == Fragment::AND_V && index == 1)) return verify; 805 return false; 806 }; 807 // The upward function computes for a node, given its followed-by-OP_VERIFY status 808 // and the CScripts of its child nodes, the CScript of the node. 809 const bool is_tapscript{IsTapscript(m_script_ctx)}; 810 auto upfn = [&ctx, is_tapscript](bool verify, const Node& node, std::span<CScript> subs) -> CScript { 811 switch (node.fragment) { 812 case Fragment::PK_K: return BuildScript(ctx.ToPKBytes(node.keys[0])); 813 case Fragment::PK_H: return BuildScript(OP_DUP, OP_HASH160, ctx.ToPKHBytes(node.keys[0]), OP_EQUALVERIFY); 814 case Fragment::OLDER: return BuildScript(node.k, OP_CHECKSEQUENCEVERIFY); 815 case Fragment::AFTER: return BuildScript(node.k, OP_CHECKLOCKTIMEVERIFY); 816 case Fragment::SHA256: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_SHA256, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL); 817 case Fragment::RIPEMD160: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_RIPEMD160, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL); 818 case Fragment::HASH256: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_HASH256, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL); 819 case Fragment::HASH160: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_HASH160, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL); 820 case Fragment::WRAP_A: return BuildScript(OP_TOALTSTACK, subs[0], OP_FROMALTSTACK); 821 case Fragment::WRAP_S: return BuildScript(OP_SWAP, subs[0]); 822 case Fragment::WRAP_C: return BuildScript(std::move(subs[0]), verify ? OP_CHECKSIGVERIFY : OP_CHECKSIG); 823 case Fragment::WRAP_D: return BuildScript(OP_DUP, OP_IF, subs[0], OP_ENDIF); 824 case Fragment::WRAP_V: { 825 if (node.subs[0].GetType() << "x"_mst) { 826 return BuildScript(std::move(subs[0]), OP_VERIFY); 827 } else { 828 return std::move(subs[0]); 829 } 830 } 831 case Fragment::WRAP_J: return BuildScript(OP_SIZE, OP_0NOTEQUAL, OP_IF, subs[0], OP_ENDIF); 832 case Fragment::WRAP_N: return BuildScript(std::move(subs[0]), OP_0NOTEQUAL); 833 case Fragment::JUST_1: return BuildScript(OP_1); 834 case Fragment::JUST_0: return BuildScript(OP_0); 835 case Fragment::AND_V: return BuildScript(std::move(subs[0]), subs[1]); 836 case Fragment::AND_B: return BuildScript(std::move(subs[0]), subs[1], OP_BOOLAND); 837 case Fragment::OR_B: return BuildScript(std::move(subs[0]), subs[1], OP_BOOLOR); 838 case Fragment::OR_D: return BuildScript(std::move(subs[0]), OP_IFDUP, OP_NOTIF, subs[1], OP_ENDIF); 839 case Fragment::OR_C: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[1], OP_ENDIF); 840 case Fragment::OR_I: return BuildScript(OP_IF, subs[0], OP_ELSE, subs[1], OP_ENDIF); 841 case Fragment::ANDOR: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[2], OP_ELSE, subs[1], OP_ENDIF); 842 case Fragment::MULTI: { 843 CHECK_NONFATAL(!is_tapscript); 844 CScript script = BuildScript(node.k); 845 for (const auto& key : node.keys) { 846 script = BuildScript(std::move(script), ctx.ToPKBytes(key)); 847 } 848 return BuildScript(std::move(script), node.keys.size(), verify ? OP_CHECKMULTISIGVERIFY : OP_CHECKMULTISIG); 849 } 850 case Fragment::MULTI_A: { 851 CHECK_NONFATAL(is_tapscript); 852 CScript script = BuildScript(ctx.ToPKBytes(*node.keys.begin()), OP_CHECKSIG); 853 for (auto it = node.keys.begin() + 1; it != node.keys.end(); ++it) { 854 script = BuildScript(std::move(script), ctx.ToPKBytes(*it), OP_CHECKSIGADD); 855 } 856 return BuildScript(std::move(script), node.k, verify ? OP_NUMEQUALVERIFY : OP_NUMEQUAL); 857 } 858 case Fragment::THRESH: { 859 CScript script = std::move(subs[0]); 860 for (size_t i = 1; i < subs.size(); ++i) { 861 script = BuildScript(std::move(script), subs[i], OP_ADD); 862 } 863 return BuildScript(std::move(script), node.k, verify ? OP_EQUALVERIFY : OP_EQUAL); 864 } 865 } 866 assert(false); 867 }; 868 return TreeEval<CScript>(false, downfn, upfn); 869 } 870 871 template<typename CTx> 872 std::optional<std::string> ToString(const CTx& ctx) const { 873 bool dummy{false}; 874 return ToString(ctx, dummy); 875 } 876 877 template<typename CTx> 878 std::optional<std::string> ToString(const CTx& ctx, bool& has_priv_key) const { 879 // To construct the std::string representation for a Miniscript object, we use 880 // the TreeEvalMaybe algorithm. The State is a boolean: whether the parent node is a 881 // wrapper. If so, non-wrapper expressions must be prefixed with a ":". 882 auto downfn = [](bool, const Node& node, size_t) { 883 return (node.fragment == Fragment::WRAP_A || node.fragment == Fragment::WRAP_S || 884 node.fragment == Fragment::WRAP_D || node.fragment == Fragment::WRAP_V || 885 node.fragment == Fragment::WRAP_J || node.fragment == Fragment::WRAP_N || 886 node.fragment == Fragment::WRAP_C || 887 (node.fragment == Fragment::AND_V && node.subs[1].fragment == Fragment::JUST_1) || 888 (node.fragment == Fragment::OR_I && node.subs[0].fragment == Fragment::JUST_0) || 889 (node.fragment == Fragment::OR_I && node.subs[1].fragment == Fragment::JUST_0)); 890 }; 891 auto toString = [&ctx, &has_priv_key](Key key) -> std::optional<std::string> { 892 bool fragment_has_priv_key{false}; 893 auto key_str{ctx.ToString(key, fragment_has_priv_key)}; 894 if (key_str) has_priv_key = has_priv_key || fragment_has_priv_key; 895 return key_str; 896 }; 897 // The upward function computes for a node, given whether its parent is a wrapper, 898 // and the string representations of its child nodes, the string representation of the node. 899 const bool is_tapscript{IsTapscript(m_script_ctx)}; 900 auto upfn = [is_tapscript, &toString](bool wrapped, const Node& node, std::span<std::string> subs) -> std::optional<std::string> { 901 std::string ret = wrapped ? ":" : ""; 902 903 switch (node.fragment) { 904 case Fragment::WRAP_A: return "a" + std::move(subs[0]); 905 case Fragment::WRAP_S: return "s" + std::move(subs[0]); 906 case Fragment::WRAP_C: 907 if (node.subs[0].fragment == Fragment::PK_K) { 908 // pk(K) is syntactic sugar for c:pk_k(K) 909 auto key_str = toString(node.subs[0].keys[0]); 910 if (!key_str) return {}; 911 return std::move(ret) + "pk(" + std::move(*key_str) + ")"; 912 } 913 if (node.subs[0].fragment == Fragment::PK_H) { 914 // pkh(K) is syntactic sugar for c:pk_h(K) 915 auto key_str = toString(node.subs[0].keys[0]); 916 if (!key_str) return {}; 917 return std::move(ret) + "pkh(" + std::move(*key_str) + ")"; 918 } 919 return "c" + std::move(subs[0]); 920 case Fragment::WRAP_D: return "d" + std::move(subs[0]); 921 case Fragment::WRAP_V: return "v" + std::move(subs[0]); 922 case Fragment::WRAP_J: return "j" + std::move(subs[0]); 923 case Fragment::WRAP_N: return "n" + std::move(subs[0]); 924 case Fragment::AND_V: 925 // t:X is syntactic sugar for and_v(X,1). 926 if (node.subs[1].fragment == Fragment::JUST_1) return "t" + std::move(subs[0]); 927 break; 928 case Fragment::OR_I: 929 if (node.subs[0].fragment == Fragment::JUST_0) return "l" + std::move(subs[1]); 930 if (node.subs[1].fragment == Fragment::JUST_0) return "u" + std::move(subs[0]); 931 break; 932 default: break; 933 } 934 switch (node.fragment) { 935 case Fragment::PK_K: { 936 auto key_str = toString(node.keys[0]); 937 if (!key_str) return {}; 938 return std::move(ret) + "pk_k(" + std::move(*key_str) + ")"; 939 } 940 case Fragment::PK_H: { 941 auto key_str = toString(node.keys[0]); 942 if (!key_str) return {}; 943 return std::move(ret) + "pk_h(" + std::move(*key_str) + ")"; 944 } 945 case Fragment::AFTER: return std::move(ret) + "after(" + util::ToString(node.k) + ")"; 946 case Fragment::OLDER: return std::move(ret) + "older(" + util::ToString(node.k) + ")"; 947 case Fragment::HASH256: return std::move(ret) + "hash256(" + HexStr(node.data) + ")"; 948 case Fragment::HASH160: return std::move(ret) + "hash160(" + HexStr(node.data) + ")"; 949 case Fragment::SHA256: return std::move(ret) + "sha256(" + HexStr(node.data) + ")"; 950 case Fragment::RIPEMD160: return std::move(ret) + "ripemd160(" + HexStr(node.data) + ")"; 951 case Fragment::JUST_1: return std::move(ret) + "1"; 952 case Fragment::JUST_0: return std::move(ret) + "0"; 953 case Fragment::AND_V: return std::move(ret) + "and_v(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")"; 954 case Fragment::AND_B: return std::move(ret) + "and_b(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")"; 955 case Fragment::OR_B: return std::move(ret) + "or_b(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")"; 956 case Fragment::OR_D: return std::move(ret) + "or_d(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")"; 957 case Fragment::OR_C: return std::move(ret) + "or_c(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")"; 958 case Fragment::OR_I: return std::move(ret) + "or_i(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")"; 959 case Fragment::ANDOR: 960 // and_n(X,Y) is syntactic sugar for andor(X,Y,0). 961 if (node.subs[2].fragment == Fragment::JUST_0) return std::move(ret) + "and_n(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")"; 962 return std::move(ret) + "andor(" + std::move(subs[0]) + "," + std::move(subs[1]) + "," + std::move(subs[2]) + ")"; 963 case Fragment::MULTI: { 964 CHECK_NONFATAL(!is_tapscript); 965 auto str = std::move(ret) + "multi(" + util::ToString(node.k); 966 for (const auto& key : node.keys) { 967 auto key_str = toString(key); 968 if (!key_str) return {}; 969 str += "," + std::move(*key_str); 970 } 971 return std::move(str) + ")"; 972 } 973 case Fragment::MULTI_A: { 974 CHECK_NONFATAL(is_tapscript); 975 auto str = std::move(ret) + "multi_a(" + util::ToString(node.k); 976 for (const auto& key : node.keys) { 977 auto key_str = toString(key); 978 if (!key_str) return {}; 979 str += "," + std::move(*key_str); 980 } 981 return std::move(str) + ")"; 982 } 983 case Fragment::THRESH: { 984 auto str = std::move(ret) + "thresh(" + util::ToString(node.k); 985 for (auto& sub : subs) { 986 str += "," + std::move(sub); 987 } 988 return std::move(str) + ")"; 989 } 990 default: break; 991 } 992 assert(false); 993 }; 994 995 return TreeEvalMaybe<std::string>(false, downfn, upfn); 996 } 997 998 private: 999 internal::Ops CalcOps() const { 1000 switch (fragment) { 1001 case Fragment::JUST_1: return {0, 0, {}}; 1002 case Fragment::JUST_0: return {0, {}, 0}; 1003 case Fragment::PK_K: return {0, 0, 0}; 1004 case Fragment::PK_H: return {3, 0, 0}; 1005 case Fragment::OLDER: 1006 case Fragment::AFTER: return {1, 0, {}}; 1007 case Fragment::SHA256: 1008 case Fragment::RIPEMD160: 1009 case Fragment::HASH256: 1010 case Fragment::HASH160: return {4, 0, {}}; 1011 case Fragment::AND_V: return {subs[0].ops.count + subs[1].ops.count, subs[0].ops.sat + subs[1].ops.sat, {}}; 1012 case Fragment::AND_B: { 1013 const auto count{1 + subs[0].ops.count + subs[1].ops.count}; 1014 const auto sat{subs[0].ops.sat + subs[1].ops.sat}; 1015 const auto dsat{subs[0].ops.dsat + subs[1].ops.dsat}; 1016 return {count, sat, dsat}; 1017 } 1018 case Fragment::OR_B: { 1019 const auto count{1 + subs[0].ops.count + subs[1].ops.count}; 1020 const auto sat{(subs[0].ops.sat + subs[1].ops.dsat) | (subs[1].ops.sat + subs[0].ops.dsat)}; 1021 const auto dsat{subs[0].ops.dsat + subs[1].ops.dsat}; 1022 return {count, sat, dsat}; 1023 } 1024 case Fragment::OR_D: { 1025 const auto count{3 + subs[0].ops.count + subs[1].ops.count}; 1026 const auto sat{subs[0].ops.sat | (subs[1].ops.sat + subs[0].ops.dsat)}; 1027 const auto dsat{subs[0].ops.dsat + subs[1].ops.dsat}; 1028 return {count, sat, dsat}; 1029 } 1030 case Fragment::OR_C: { 1031 const auto count{2 + subs[0].ops.count + subs[1].ops.count}; 1032 const auto sat{subs[0].ops.sat | (subs[1].ops.sat + subs[0].ops.dsat)}; 1033 return {count, sat, {}}; 1034 } 1035 case Fragment::OR_I: { 1036 const auto count{3 + subs[0].ops.count + subs[1].ops.count}; 1037 const auto sat{subs[0].ops.sat | subs[1].ops.sat}; 1038 const auto dsat{subs[0].ops.dsat | subs[1].ops.dsat}; 1039 return {count, sat, dsat}; 1040 } 1041 case Fragment::ANDOR: { 1042 const auto count{3 + subs[0].ops.count + subs[1].ops.count + subs[2].ops.count}; 1043 const auto sat{(subs[1].ops.sat + subs[0].ops.sat) | (subs[0].ops.dsat + subs[2].ops.sat)}; 1044 const auto dsat{subs[0].ops.dsat + subs[2].ops.dsat}; 1045 return {count, sat, dsat}; 1046 } 1047 case Fragment::MULTI: return {1, (uint32_t)keys.size(), (uint32_t)keys.size()}; 1048 case Fragment::MULTI_A: return {(uint32_t)keys.size() + 1, 0, 0}; 1049 case Fragment::WRAP_S: 1050 case Fragment::WRAP_C: 1051 case Fragment::WRAP_N: return {1 + subs[0].ops.count, subs[0].ops.sat, subs[0].ops.dsat}; 1052 case Fragment::WRAP_A: return {2 + subs[0].ops.count, subs[0].ops.sat, subs[0].ops.dsat}; 1053 case Fragment::WRAP_D: return {3 + subs[0].ops.count, subs[0].ops.sat, 0}; 1054 case Fragment::WRAP_J: return {4 + subs[0].ops.count, subs[0].ops.sat, 0}; 1055 case Fragment::WRAP_V: return {subs[0].ops.count + (subs[0].GetType() << "x"_mst), subs[0].ops.sat, {}}; 1056 case Fragment::THRESH: { 1057 uint32_t count = 0; 1058 auto sats = Vector(internal::MaxInt<uint32_t>(0)); 1059 for (const auto& sub : subs) { 1060 count += sub.ops.count + 1; 1061 auto next_sats = Vector(sats[0] + sub.ops.dsat); 1062 for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub.ops.dsat) | (sats[j - 1] + sub.ops.sat)); 1063 next_sats.push_back(sats[sats.size() - 1] + sub.ops.sat); 1064 sats = std::move(next_sats); 1065 } 1066 assert(k < sats.size()); 1067 return {count, sats[k], sats[0]}; 1068 } 1069 } 1070 assert(false); 1071 } 1072 1073 internal::StackSize CalcStackSize() const { 1074 using namespace internal; 1075 switch (fragment) { 1076 case Fragment::JUST_0: return {{}, SatInfo::Push()}; 1077 case Fragment::JUST_1: return {SatInfo::Push(), {}}; 1078 case Fragment::OLDER: 1079 case Fragment::AFTER: return {SatInfo::Push() + SatInfo::Nop(), {}}; 1080 case Fragment::PK_K: return {SatInfo::Push()}; 1081 case Fragment::PK_H: return {SatInfo::OP_DUP() + SatInfo::Hash() + SatInfo::Push() + SatInfo::OP_EQUALVERIFY()}; 1082 case Fragment::SHA256: 1083 case Fragment::RIPEMD160: 1084 case Fragment::HASH256: 1085 case Fragment::HASH160: return { 1086 SatInfo::OP_SIZE() + SatInfo::Push() + SatInfo::OP_EQUALVERIFY() + SatInfo::Hash() + SatInfo::Push() + SatInfo::OP_EQUAL(), 1087 {} 1088 }; 1089 case Fragment::ANDOR: { 1090 const auto& x{subs[0].ss}; 1091 const auto& y{subs[1].ss}; 1092 const auto& z{subs[2].ss}; 1093 return { 1094 (x.Sat() + SatInfo::If() + y.Sat()) | (x.Dsat() + SatInfo::If() + z.Sat()), 1095 x.Dsat() + SatInfo::If() + z.Dsat() 1096 }; 1097 } 1098 case Fragment::AND_V: { 1099 const auto& x{subs[0].ss}; 1100 const auto& y{subs[1].ss}; 1101 return {x.Sat() + y.Sat(), {}}; 1102 } 1103 case Fragment::AND_B: { 1104 const auto& x{subs[0].ss}; 1105 const auto& y{subs[1].ss}; 1106 return {x.Sat() + y.Sat() + SatInfo::BinaryOp(), x.Dsat() + y.Dsat() + SatInfo::BinaryOp()}; 1107 } 1108 case Fragment::OR_B: { 1109 const auto& x{subs[0].ss}; 1110 const auto& y{subs[1].ss}; 1111 return { 1112 ((x.Sat() + y.Dsat()) | (x.Dsat() + y.Sat())) + SatInfo::BinaryOp(), 1113 x.Dsat() + y.Dsat() + SatInfo::BinaryOp() 1114 }; 1115 } 1116 case Fragment::OR_C: { 1117 const auto& x{subs[0].ss}; 1118 const auto& y{subs[1].ss}; 1119 return {(x.Sat() + SatInfo::If()) | (x.Dsat() + SatInfo::If() + y.Sat()), {}}; 1120 } 1121 case Fragment::OR_D: { 1122 const auto& x{subs[0].ss}; 1123 const auto& y{subs[1].ss}; 1124 return { 1125 (x.Sat() + SatInfo::OP_IFDUP(true) + SatInfo::If()) | (x.Dsat() + SatInfo::OP_IFDUP(false) + SatInfo::If() + y.Sat()), 1126 x.Dsat() + SatInfo::OP_IFDUP(false) + SatInfo::If() + y.Dsat() 1127 }; 1128 } 1129 case Fragment::OR_I: { 1130 const auto& x{subs[0].ss}; 1131 const auto& y{subs[1].ss}; 1132 return {SatInfo::If() + (x.Sat() | y.Sat()), SatInfo::If() + (x.Dsat() | y.Dsat())}; 1133 } 1134 // multi(k, key1, key2, ..., key_n) starts off with k+1 stack elements (a 0, plus k 1135 // signatures), then reaches n+k+3 stack elements after pushing the n keys, plus k and 1136 // n itself, and ends with 1 stack element (success or failure). Thus, it net removes 1137 // k elements (from k+1 to 1), while reaching k+n+2 more than it ends with. 1138 case Fragment::MULTI: return {SatInfo(k, k + keys.size() + 2)}; 1139 // multi_a(k, key1, key2, ..., key_n) starts off with n stack elements (the 1140 // signatures), reaches 1 more (after the first key push), and ends with 1. Thus it net 1141 // removes n-1 elements (from n to 1) while reaching n more than it ends with. 1142 case Fragment::MULTI_A: return {SatInfo(keys.size() - 1, keys.size())}; 1143 case Fragment::WRAP_A: 1144 case Fragment::WRAP_N: 1145 case Fragment::WRAP_S: return subs[0].ss; 1146 case Fragment::WRAP_C: return { 1147 subs[0].ss.Sat() + SatInfo::OP_CHECKSIG(), 1148 subs[0].ss.Dsat() + SatInfo::OP_CHECKSIG() 1149 }; 1150 case Fragment::WRAP_D: return { 1151 SatInfo::OP_DUP() + SatInfo::If() + subs[0].ss.Sat(), 1152 SatInfo::OP_DUP() + SatInfo::If() 1153 }; 1154 case Fragment::WRAP_V: return {subs[0].ss.Sat() + SatInfo::OP_VERIFY(), {}}; 1155 case Fragment::WRAP_J: return { 1156 SatInfo::OP_SIZE() + SatInfo::OP_0NOTEQUAL() + SatInfo::If() + subs[0].ss.Sat(), 1157 SatInfo::OP_SIZE() + SatInfo::OP_0NOTEQUAL() + SatInfo::If() 1158 }; 1159 case Fragment::THRESH: { 1160 // sats[j] is the SatInfo corresponding to all traces reaching j satisfactions. 1161 auto sats = Vector(SatInfo::Empty()); 1162 for (size_t i = 0; i < subs.size(); ++i) { 1163 // Loop over the subexpressions, processing them one by one. After adding 1164 // element i we need to add OP_ADD (if i>0). 1165 auto add = i ? SatInfo::BinaryOp() : SatInfo::Empty(); 1166 // Construct a variable that will become the next sats, starting with index 0. 1167 auto next_sats = Vector(sats[0] + subs[i].ss.Dsat() + add); 1168 // Then loop to construct next_sats[1..i]. 1169 for (size_t j = 1; j < sats.size(); ++j) { 1170 next_sats.push_back(((sats[j] + subs[i].ss.Dsat()) | (sats[j - 1] + subs[i].ss.Sat())) + add); 1171 } 1172 // Finally construct next_sats[i+1]. 1173 next_sats.push_back(sats[sats.size() - 1] + subs[i].ss.Sat() + add); 1174 // Switch over. 1175 sats = std::move(next_sats); 1176 } 1177 // To satisfy thresh we need k satisfactions; to dissatisfy we need 0. In both 1178 // cases a push of k and an OP_EQUAL follow. 1179 return { 1180 sats[k] + SatInfo::Push() + SatInfo::OP_EQUAL(), 1181 sats[0] + SatInfo::Push() + SatInfo::OP_EQUAL() 1182 }; 1183 } 1184 } 1185 assert(false); 1186 } 1187 1188 internal::WitnessSize CalcWitnessSize() const { 1189 const uint32_t sig_size = IsTapscript(m_script_ctx) ? 1 + 65 : 1 + 72; 1190 const uint32_t pubkey_size = IsTapscript(m_script_ctx) ? 1 + 32 : 1 + 33; 1191 switch (fragment) { 1192 case Fragment::JUST_0: return {{}, 0}; 1193 case Fragment::JUST_1: 1194 case Fragment::OLDER: 1195 case Fragment::AFTER: return {0, {}}; 1196 case Fragment::PK_K: return {sig_size, 1}; 1197 case Fragment::PK_H: return {sig_size + pubkey_size, 1 + pubkey_size}; 1198 case Fragment::SHA256: 1199 case Fragment::RIPEMD160: 1200 case Fragment::HASH256: 1201 case Fragment::HASH160: return {1 + 32, {}}; 1202 case Fragment::ANDOR: { 1203 const auto sat{(subs[0].ws.sat + subs[1].ws.sat) | (subs[0].ws.dsat + subs[2].ws.sat)}; 1204 const auto dsat{subs[0].ws.dsat + subs[2].ws.dsat}; 1205 return {sat, dsat}; 1206 } 1207 case Fragment::AND_V: return {subs[0].ws.sat + subs[1].ws.sat, {}}; 1208 case Fragment::AND_B: return {subs[0].ws.sat + subs[1].ws.sat, subs[0].ws.dsat + subs[1].ws.dsat}; 1209 case Fragment::OR_B: { 1210 const auto sat{(subs[0].ws.dsat + subs[1].ws.sat) | (subs[0].ws.sat + subs[1].ws.dsat)}; 1211 const auto dsat{subs[0].ws.dsat + subs[1].ws.dsat}; 1212 return {sat, dsat}; 1213 } 1214 case Fragment::OR_C: return {subs[0].ws.sat | (subs[0].ws.dsat + subs[1].ws.sat), {}}; 1215 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}; 1216 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)}; 1217 case Fragment::MULTI: return {k * sig_size + 1, k + 1}; 1218 case Fragment::MULTI_A: return {k * sig_size + static_cast<uint32_t>(keys.size()) - k, static_cast<uint32_t>(keys.size())}; 1219 case Fragment::WRAP_A: 1220 case Fragment::WRAP_N: 1221 case Fragment::WRAP_S: 1222 case Fragment::WRAP_C: return subs[0].ws; 1223 case Fragment::WRAP_D: return {1 + 1 + subs[0].ws.sat, 1}; 1224 case Fragment::WRAP_V: return {subs[0].ws.sat, {}}; 1225 case Fragment::WRAP_J: return {subs[0].ws.sat, 1}; 1226 case Fragment::THRESH: { 1227 auto sats = Vector(internal::MaxInt<uint32_t>(0)); 1228 for (const auto& sub : subs) { 1229 auto next_sats = Vector(sats[0] + sub.ws.dsat); 1230 for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub.ws.dsat) | (sats[j - 1] + sub.ws.sat)); 1231 next_sats.push_back(sats[sats.size() - 1] + sub.ws.sat); 1232 sats = std::move(next_sats); 1233 } 1234 assert(k < sats.size()); 1235 return {sats[k], sats[0]}; 1236 } 1237 } 1238 assert(false); 1239 } 1240 1241 template<typename Ctx> 1242 internal::InputResult ProduceInput(const Ctx& ctx) const { 1243 using namespace internal; 1244 1245 // Internal function which is invoked for every tree node, constructing satisfaction/dissatisfactions 1246 // given those of its subnodes. 1247 auto helper = [&ctx](const Node& node, std::span<InputResult> subres) -> InputResult { 1248 switch (node.fragment) { 1249 case Fragment::PK_K: { 1250 std::vector<unsigned char> sig; 1251 Availability avail = ctx.Sign(node.keys[0], sig); 1252 return {ZERO, InputStack(std::move(sig)).SetWithSig().SetAvailable(avail)}; 1253 } 1254 case Fragment::PK_H: { 1255 std::vector<unsigned char> key = ctx.ToPKBytes(node.keys[0]), sig; 1256 Availability avail = ctx.Sign(node.keys[0], sig); 1257 return {ZERO + InputStack(key), (InputStack(std::move(sig)).SetWithSig() + InputStack(key)).SetAvailable(avail)}; 1258 } 1259 case Fragment::MULTI_A: { 1260 // sats[j] represents the best stack containing j valid signatures (out of the first i keys). 1261 // In the loop below, these stacks are built up using a dynamic programming approach. 1262 std::vector<InputStack> sats = Vector(EMPTY); 1263 for (size_t i = 0; i < node.keys.size(); ++i) { 1264 // Get the signature for the i'th key in reverse order (the signature for the first key needs to 1265 // be at the top of the stack, contrary to CHECKMULTISIG's satisfaction). 1266 std::vector<unsigned char> sig; 1267 Availability avail = ctx.Sign(node.keys[node.keys.size() - 1 - i], sig); 1268 // Compute signature stack for just this key. 1269 auto sat = InputStack(std::move(sig)).SetWithSig().SetAvailable(avail); 1270 // Compute the next sats vector: next_sats[0] is a copy of sats[0] (no signatures). All further 1271 // next_sats[j] are equal to either the existing sats[j] + ZERO, or sats[j-1] plus a signature 1272 // for the current (i'th) key. The very last element needs all signatures filled. 1273 std::vector<InputStack> next_sats; 1274 next_sats.push_back(sats[0] + ZERO); 1275 for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + ZERO) | (std::move(sats[j - 1]) + sat)); 1276 next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(sat)); 1277 // Switch over. 1278 sats = std::move(next_sats); 1279 } 1280 // The dissatisfaction consists of as many empty vectors as there are keys, which is the same as 1281 // satisfying 0 keys. 1282 auto& nsat{sats[0]}; 1283 CHECK_NONFATAL(node.k != 0); 1284 assert(node.k < sats.size()); 1285 return {std::move(nsat), std::move(sats[node.k])}; 1286 } 1287 case Fragment::MULTI: { 1288 // sats[j] represents the best stack containing j valid signatures (out of the first i keys). 1289 // In the loop below, these stacks are built up using a dynamic programming approach. 1290 // sats[0] starts off being {0}, due to the CHECKMULTISIG bug that pops off one element too many. 1291 std::vector<InputStack> sats = Vector(ZERO); 1292 for (size_t i = 0; i < node.keys.size(); ++i) { 1293 std::vector<unsigned char> sig; 1294 Availability avail = ctx.Sign(node.keys[i], sig); 1295 // Compute signature stack for just the i'th key. 1296 auto sat = InputStack(std::move(sig)).SetWithSig().SetAvailable(avail); 1297 // Compute the next sats vector: next_sats[0] is a copy of sats[0] (no signatures). All further 1298 // next_sats[j] are equal to either the existing sats[j], or sats[j-1] plus a signature for the 1299 // current (i'th) key. The very last element needs all signatures filled. 1300 std::vector<InputStack> next_sats; 1301 next_sats.push_back(sats[0]); 1302 for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back(sats[j] | (std::move(sats[j - 1]) + sat)); 1303 next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(sat)); 1304 // Switch over. 1305 sats = std::move(next_sats); 1306 } 1307 // The dissatisfaction consists of k+1 stack elements all equal to 0. 1308 InputStack nsat = ZERO; 1309 for (size_t i = 0; i < node.k; ++i) nsat = std::move(nsat) + ZERO; 1310 assert(node.k < sats.size()); 1311 return {std::move(nsat), std::move(sats[node.k])}; 1312 } 1313 case Fragment::THRESH: { 1314 // sats[k] represents the best stack that satisfies k out of the *last* i subexpressions. 1315 // In the loop below, these stacks are built up using a dynamic programming approach. 1316 // sats[0] starts off empty. 1317 std::vector<InputStack> sats = Vector(EMPTY); 1318 for (size_t i = 0; i < subres.size(); ++i) { 1319 // Introduce an alias for the i'th last satisfaction/dissatisfaction. 1320 auto& res = subres[subres.size() - i - 1]; 1321 // Compute the next sats vector: next_sats[0] is sats[0] plus res.nsat (thus containing all dissatisfactions 1322 // so far. next_sats[j] is either sats[j] + res.nsat (reusing j earlier satisfactions) or sats[j-1] + res.sat 1323 // (reusing j-1 earlier satisfactions plus a new one). The very last next_sats[j] is all satisfactions. 1324 std::vector<InputStack> next_sats; 1325 next_sats.push_back(sats[0] + res.nsat); 1326 for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + res.nsat) | (std::move(sats[j - 1]) + res.sat)); 1327 next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(res.sat)); 1328 // Switch over. 1329 sats = std::move(next_sats); 1330 } 1331 // At this point, sats[k].sat is the best satisfaction for the overall thresh() node. The best dissatisfaction 1332 // is computed by gathering all sats[i].nsat for i != k. 1333 InputStack nsat = INVALID; 1334 for (size_t i = 0; i < sats.size(); ++i) { 1335 // i==k is the satisfaction; i==0 is the canonical dissatisfaction; 1336 // the rest are non-canonical (a no-signature dissatisfaction - the i=0 1337 // form - is always available) and malleable (due to overcompleteness). 1338 // Marking the solutions malleable here is not strictly necessary, as they 1339 // should already never be picked in non-malleable solutions due to the 1340 // availability of the i=0 form. 1341 if (i != 0 && i != node.k) sats[i].SetMalleable().SetNonCanon(); 1342 // Include all dissatisfactions (even these non-canonical ones) in nsat. 1343 if (i != node.k) nsat = std::move(nsat) | std::move(sats[i]); 1344 } 1345 assert(node.k < sats.size()); 1346 return {std::move(nsat), std::move(sats[node.k])}; 1347 } 1348 case Fragment::OLDER: { 1349 return {INVALID, ctx.CheckOlder(node.k) ? EMPTY : INVALID}; 1350 } 1351 case Fragment::AFTER: { 1352 return {INVALID, ctx.CheckAfter(node.k) ? EMPTY : INVALID}; 1353 } 1354 case Fragment::SHA256: { 1355 std::vector<unsigned char> preimage; 1356 Availability avail = ctx.SatSHA256(node.data, preimage); 1357 return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)}; 1358 } 1359 case Fragment::RIPEMD160: { 1360 std::vector<unsigned char> preimage; 1361 Availability avail = ctx.SatRIPEMD160(node.data, preimage); 1362 return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)}; 1363 } 1364 case Fragment::HASH256: { 1365 std::vector<unsigned char> preimage; 1366 Availability avail = ctx.SatHASH256(node.data, preimage); 1367 return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)}; 1368 } 1369 case Fragment::HASH160: { 1370 std::vector<unsigned char> preimage; 1371 Availability avail = ctx.SatHASH160(node.data, preimage); 1372 return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)}; 1373 } 1374 case Fragment::AND_V: { 1375 auto& x = subres[0], &y = subres[1]; 1376 // As the dissatisfaction here only consist of a single option, it doesn't 1377 // actually need to be listed (it's not required for reasoning about malleability of 1378 // other options), and is never required (no valid miniscript relies on the ability 1379 // to satisfy the type V left subexpression). It's still listed here for 1380 // completeness, as a hypothetical (not currently implemented) satisfier that doesn't 1381 // care about malleability might in some cases prefer it still. 1382 return {(y.nsat + x.sat).SetNonCanon(), y.sat + x.sat}; 1383 } 1384 case Fragment::AND_B: { 1385 auto& x = subres[0], &y = subres[1]; 1386 // Note that it is not strictly necessary to mark the 2nd and 3rd dissatisfaction here 1387 // as malleable. While they are definitely malleable, they are also non-canonical due 1388 // to the guaranteed existence of a no-signature other dissatisfaction (the 1st) 1389 // option. Because of that, the 2nd and 3rd option will never be chosen, even if they 1390 // weren't marked as malleable. 1391 return {(y.nsat + x.nsat) | (y.sat + x.nsat).SetMalleable().SetNonCanon() | (y.nsat + x.sat).SetMalleable().SetNonCanon(), y.sat + x.sat}; 1392 } 1393 case Fragment::OR_B: { 1394 auto& x = subres[0], &z = subres[1]; 1395 // The (sat(Z) sat(X)) solution is overcomplete (attacker can change either into dsat). 1396 return {z.nsat + x.nsat, (z.nsat + x.sat) | (z.sat + x.nsat) | (z.sat + x.sat).SetMalleable().SetNonCanon()}; 1397 } 1398 case Fragment::OR_C: { 1399 auto& x = subres[0], &z = subres[1]; 1400 return {INVALID, std::move(x.sat) | (z.sat + x.nsat)}; 1401 } 1402 case Fragment::OR_D: { 1403 auto& x = subres[0], &z = subres[1]; 1404 return {z.nsat + x.nsat, std::move(x.sat) | (z.sat + x.nsat)}; 1405 } 1406 case Fragment::OR_I: { 1407 auto& x = subres[0], &z = subres[1]; 1408 return {(x.nsat + ONE) | (z.nsat + ZERO), (x.sat + ONE) | (z.sat + ZERO)}; 1409 } 1410 case Fragment::ANDOR: { 1411 auto& x = subres[0], &y = subres[1], &z = subres[2]; 1412 return {(y.nsat + x.sat).SetNonCanon() | (z.nsat + x.nsat), (y.sat + x.sat) | (z.sat + x.nsat)}; 1413 } 1414 case Fragment::WRAP_A: 1415 case Fragment::WRAP_S: 1416 case Fragment::WRAP_C: 1417 case Fragment::WRAP_N: 1418 return std::move(subres[0]); 1419 case Fragment::WRAP_D: { 1420 auto &x = subres[0]; 1421 return {ZERO, x.sat + ONE}; 1422 } 1423 case Fragment::WRAP_J: { 1424 auto &x = subres[0]; 1425 // If a dissatisfaction with a nonzero top stack element exists, an alternative dissatisfaction exists. 1426 // As the dissatisfaction logic currently doesn't keep track of this nonzeroness property, and thus even 1427 // if a dissatisfaction with a top zero element is found, we don't know whether another one with a 1428 // nonzero top stack element exists. Make the conservative assumption that whenever the subexpression is weakly 1429 // dissatisfiable, this alternative dissatisfaction exists and leads to malleability. 1430 return {InputStack(ZERO).SetMalleable(x.nsat.available != Availability::NO && !x.nsat.has_sig), std::move(x.sat)}; 1431 } 1432 case Fragment::WRAP_V: { 1433 auto &x = subres[0]; 1434 return {INVALID, std::move(x.sat)}; 1435 } 1436 case Fragment::JUST_0: return {EMPTY, INVALID}; 1437 case Fragment::JUST_1: return {INVALID, EMPTY}; 1438 } 1439 assert(false); 1440 return {INVALID, INVALID}; 1441 }; 1442 1443 auto tester = [&helper](const Node& node, std::span<InputResult> subres) -> InputResult { 1444 auto ret = helper(node, subres); 1445 1446 // Do a consistency check between the satisfaction code and the type checker 1447 // (the actual satisfaction code in ProduceInputHelper does not use GetType) 1448 1449 // For 'z' nodes, available satisfactions/dissatisfactions must have stack size 0. 1450 if (node.GetType() << "z"_mst && ret.nsat.available != Availability::NO) CHECK_NONFATAL(ret.nsat.stack.size() == 0); 1451 if (node.GetType() << "z"_mst && ret.sat.available != Availability::NO) CHECK_NONFATAL(ret.sat.stack.size() == 0); 1452 1453 // For 'o' nodes, available satisfactions/dissatisfactions must have stack size 1. 1454 if (node.GetType() << "o"_mst && ret.nsat.available != Availability::NO) CHECK_NONFATAL(ret.nsat.stack.size() == 1); 1455 if (node.GetType() << "o"_mst && ret.sat.available != Availability::NO) CHECK_NONFATAL(ret.sat.stack.size() == 1); 1456 1457 // For 'n' nodes, available satisfactions/dissatisfactions must have stack size 1 or larger. For satisfactions, 1458 // the top element cannot be 0. 1459 if (node.GetType() << "n"_mst && ret.sat.available != Availability::NO) CHECK_NONFATAL(ret.sat.stack.size() >= 1); 1460 if (node.GetType() << "n"_mst && ret.nsat.available != Availability::NO) CHECK_NONFATAL(ret.nsat.stack.size() >= 1); 1461 if (node.GetType() << "n"_mst && ret.sat.available != Availability::NO) CHECK_NONFATAL(!ret.sat.stack.back().empty()); 1462 1463 // For 'd' nodes, a dissatisfaction must exist, and they must not need a signature. If it is non-malleable, 1464 // it must be canonical. 1465 if (node.GetType() << "d"_mst) CHECK_NONFATAL(ret.nsat.available != Availability::NO); 1466 if (node.GetType() << "d"_mst) CHECK_NONFATAL(!ret.nsat.has_sig); 1467 if (node.GetType() << "d"_mst && !ret.nsat.malleable) CHECK_NONFATAL(!ret.nsat.non_canon); 1468 1469 // For 'f'/'s' nodes, dissatisfactions/satisfactions must have a signature. 1470 if (node.GetType() << "f"_mst && ret.nsat.available != Availability::NO) CHECK_NONFATAL(ret.nsat.has_sig); 1471 if (node.GetType() << "s"_mst && ret.sat.available != Availability::NO) CHECK_NONFATAL(ret.sat.has_sig); 1472 1473 // For non-malleable 'e' nodes, a non-malleable dissatisfaction must exist. 1474 if (node.GetType() << "me"_mst) CHECK_NONFATAL(ret.nsat.available != Availability::NO); 1475 if (node.GetType() << "me"_mst) CHECK_NONFATAL(!ret.nsat.malleable); 1476 1477 // For 'm' nodes, if a satisfaction exists, it must be non-malleable. 1478 if (node.GetType() << "m"_mst && ret.sat.available != Availability::NO) CHECK_NONFATAL(!ret.sat.malleable); 1479 1480 // If a non-malleable satisfaction exists, it must be canonical. 1481 if (ret.sat.available != Availability::NO && !ret.sat.malleable) CHECK_NONFATAL(!ret.sat.non_canon); 1482 1483 return ret; 1484 }; 1485 1486 return TreeEval<InputResult>(tester); 1487 } 1488 1489 public: 1490 /** Update duplicate key information in this Node. 1491 * 1492 * This uses a custom key comparator provided by the context in order to still detect duplicates 1493 * for more complicated types. 1494 */ 1495 template<typename Ctx> void DuplicateKeyCheck(const Ctx& ctx) const 1496 { 1497 // We cannot use a lambda here, as lambdas are non assignable, and the set operations 1498 // below require moving the comparators around. 1499 struct Comp { 1500 const Ctx* ctx_ptr; 1501 Comp(const Ctx& ctx) : ctx_ptr(&ctx) {} 1502 bool operator()(const Key& a, const Key& b) const { return ctx_ptr->KeyCompare(a, b); } 1503 }; 1504 1505 // state in the recursive computation: 1506 // - std::nullopt means "this node has duplicates" 1507 // - an std::set means "this node has no duplicate keys, and they are: ...". 1508 using keyset = std::set<Key, Comp>; 1509 using state = std::optional<keyset>; 1510 1511 auto upfn = [&ctx](const Node& node, std::span<state> subs) -> state { 1512 // If this node is already known to have duplicates, nothing left to do. 1513 if (node.has_duplicate_keys.has_value() && *node.has_duplicate_keys) return {}; 1514 1515 // Check if one of the children is already known to have duplicates. 1516 for (auto& sub : subs) { 1517 if (!sub.has_value()) { 1518 node.has_duplicate_keys = true; 1519 return {}; 1520 } 1521 } 1522 1523 // Start building the set of keys involved in this node and children. 1524 // Start by keys in this node directly. 1525 size_t keys_count = node.keys.size(); 1526 keyset key_set{node.keys.begin(), node.keys.end(), Comp(ctx)}; 1527 if (key_set.size() != keys_count) { 1528 // It already has duplicates; bail out. 1529 node.has_duplicate_keys = true; 1530 return {}; 1531 } 1532 1533 // Merge the keys from the children into this set. 1534 for (auto& sub : subs) { 1535 keys_count += sub->size(); 1536 // Small optimization: std::set::merge is linear in the size of the second arg but 1537 // logarithmic in the size of the first. 1538 if (key_set.size() < sub->size()) std::swap(key_set, *sub); 1539 key_set.merge(*sub); 1540 if (key_set.size() != keys_count) { 1541 node.has_duplicate_keys = true; 1542 return {}; 1543 } 1544 } 1545 1546 node.has_duplicate_keys = false; 1547 return key_set; 1548 }; 1549 1550 TreeEval<state>(upfn); 1551 } 1552 1553 //! Return the size of the script for this expression (faster than ToScript().size()). 1554 size_t ScriptSize() const { return scriptlen; } 1555 1556 //! Return the maximum number of ops needed to satisfy this script non-malleably. 1557 std::optional<uint32_t> GetOps() const { 1558 if (!ops.sat.Valid()) return {}; 1559 return ops.count + ops.sat.Value(); 1560 } 1561 1562 //! Return the number of ops in the script (not counting the dynamic ones that depend on execution). 1563 uint32_t GetStaticOps() const { return ops.count; } 1564 1565 //! Check the ops limit of this script against the consensus limit. 1566 bool CheckOpsLimit() const { 1567 if (IsTapscript(m_script_ctx)) return true; 1568 if (const auto ops = GetOps()) return *ops <= MAX_OPS_PER_SCRIPT; 1569 return true; 1570 } 1571 1572 /** Whether this node is of type B, K or W. (That is, anything but V.) */ 1573 bool IsBKW() const { 1574 return !((GetType() & "BKW"_mst) == ""_mst); 1575 } 1576 1577 /** Return the maximum number of stack elements needed to satisfy this script non-malleably. */ 1578 std::optional<uint32_t> GetStackSize() const { 1579 if (!ss.Sat().Valid()) return {}; 1580 return ss.Sat().NetDiff() + static_cast<int32_t>(IsBKW()); 1581 } 1582 1583 //! Return the maximum size of the stack during execution of this script. 1584 std::optional<uint32_t> GetExecStackSize() const { 1585 if (!ss.Sat().Valid()) return {}; 1586 return ss.Sat().Exec() + static_cast<int32_t>(IsBKW()); 1587 } 1588 1589 //! Check the maximum stack size for this script against the policy limit. 1590 bool CheckStackSize() const { 1591 // Since in Tapscript there is no standardness limit on the script and witness sizes, we may run 1592 // into the maximum stack size while executing the script. Make sure it doesn't happen. 1593 if (IsTapscript(m_script_ctx)) { 1594 if (const auto exec_ss = GetExecStackSize()) return exec_ss <= MAX_STACK_SIZE; 1595 return true; 1596 } 1597 if (const auto ss = GetStackSize()) return *ss <= MAX_STANDARD_P2WSH_STACK_ITEMS; 1598 return true; 1599 } 1600 1601 //! Whether no satisfaction exists for this node. 1602 bool IsNotSatisfiable() const { return !GetStackSize(); } 1603 1604 /** Return the maximum size in bytes of a witness to satisfy this script non-malleably. Note this does 1605 * not include the witness script push. */ 1606 std::optional<uint32_t> GetWitnessSize() const { 1607 if (!ws.sat.Valid()) return {}; 1608 return ws.sat.Value(); 1609 } 1610 1611 //! Return the expression type. 1612 Type GetType() const { return typ; } 1613 1614 //! Return the script context for this node. 1615 MiniscriptContext GetMsCtx() const { return m_script_ctx; } 1616 1617 //! Find an insane subnode which has no insane children. Nullptr if there is none. 1618 const Node* FindInsaneSub() const { 1619 return TreeEval<const Node*>([](const Node& node, std::span<const Node*> subs) -> const Node* { 1620 for (auto& sub: subs) if (sub) return sub; 1621 if (!node.IsSaneSubexpression()) return &node; 1622 return nullptr; 1623 }); 1624 } 1625 1626 //! Determine whether a Miniscript node is satisfiable. fn(node) will be invoked for all 1627 //! key, time, and hashing nodes, and should return their satisfiability. 1628 template<typename F> 1629 bool IsSatisfiable(F fn) const 1630 { 1631 // TreeEval() doesn't support bool as NodeType, so use int instead. 1632 return TreeEval<int>([&fn](const Node& node, std::span<int> subs) -> bool { 1633 switch (node.fragment) { 1634 case Fragment::JUST_0: 1635 return false; 1636 case Fragment::JUST_1: 1637 return true; 1638 case Fragment::PK_K: 1639 case Fragment::PK_H: 1640 case Fragment::MULTI: 1641 case Fragment::MULTI_A: 1642 case Fragment::AFTER: 1643 case Fragment::OLDER: 1644 case Fragment::HASH256: 1645 case Fragment::HASH160: 1646 case Fragment::SHA256: 1647 case Fragment::RIPEMD160: 1648 return bool{fn(node)}; 1649 case Fragment::ANDOR: 1650 return (subs[0] && subs[1]) || subs[2]; 1651 case Fragment::AND_V: 1652 case Fragment::AND_B: 1653 return subs[0] && subs[1]; 1654 case Fragment::OR_B: 1655 case Fragment::OR_C: 1656 case Fragment::OR_D: 1657 case Fragment::OR_I: 1658 return subs[0] || subs[1]; 1659 case Fragment::THRESH: 1660 return static_cast<uint32_t>(std::count(subs.begin(), subs.end(), true)) >= node.k; 1661 default: // wrappers 1662 assert(subs.size() >= 1); 1663 CHECK_NONFATAL(subs.size() == 1); 1664 return subs[0]; 1665 } 1666 }); 1667 } 1668 1669 //! Check whether this node is valid at all. 1670 bool IsValid() const { 1671 if (GetType() == ""_mst) return false; 1672 return ScriptSize() <= internal::MaxScriptSize(m_script_ctx); 1673 } 1674 1675 //! Check whether this node is valid as a script on its own. 1676 bool IsValidTopLevel() const { return IsValid() && GetType() << "B"_mst; } 1677 1678 //! Check whether this script can always be satisfied in a non-malleable way. 1679 bool IsNonMalleable() const { return GetType() << "m"_mst; } 1680 1681 //! Check whether this script always needs a signature. 1682 bool NeedsSignature() const { return GetType() << "s"_mst; } 1683 1684 //! Check whether there is no satisfaction path that contains both timelocks and heightlocks 1685 bool CheckTimeLocksMix() const { return GetType() << "k"_mst; } 1686 1687 //! Check whether there is no duplicate key across this fragment and all its sub-fragments. 1688 bool CheckDuplicateKey() const { return has_duplicate_keys && !*has_duplicate_keys; } 1689 1690 //! Whether successful non-malleable satisfactions are guaranteed to be valid. 1691 bool ValidSatisfactions() const { return IsValid() && CheckOpsLimit() && CheckStackSize(); } 1692 1693 //! Whether the apparent policy of this node matches its script semantics. Doesn't guarantee it is a safe script on its own. 1694 bool IsSaneSubexpression() const { return ValidSatisfactions() && IsNonMalleable() && CheckTimeLocksMix() && CheckDuplicateKey(); } 1695 1696 //! Check whether this node is safe as a script on its own. 1697 bool IsSane() const { return IsValidTopLevel() && IsSaneSubexpression() && NeedsSignature(); } 1698 1699 //! Produce a witness for this script, if possible and given the information available in the context. 1700 //! The non-malleable satisfaction is guaranteed to be valid if it exists, and ValidSatisfaction() 1701 //! is true. If IsSane() holds, this satisfaction is guaranteed to succeed in case the node's 1702 //! conditions are satisfied (private keys and hash preimages available, locktimes satisfied). 1703 template<typename Ctx> 1704 Availability Satisfy(const Ctx& ctx, std::vector<std::vector<unsigned char>>& stack, bool nonmalleable = true) const { 1705 auto ret = ProduceInput(ctx); 1706 if (nonmalleable && (ret.sat.malleable || !ret.sat.has_sig)) return Availability::NO; 1707 stack = std::move(ret.sat.stack); 1708 return ret.sat.available; 1709 } 1710 1711 //! Equality testing. 1712 bool operator==(const Node<Key>& arg) const { return Compare(*this, arg) == 0; } 1713 1714 // Constructors with various argument combinations, which bypass the duplicate key check. 1715 Node(internal::NoDupCheck, MiniscriptContext script_ctx, enum Fragment nt, std::vector<Node> sub, std::vector<unsigned char> arg, uint32_t val = 0) 1716 : 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()) {} 1717 Node(internal::NoDupCheck, MiniscriptContext script_ctx, enum Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0) 1718 : fragment(nt), k(val), data(std::move(arg)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {} 1719 Node(internal::NoDupCheck, MiniscriptContext script_ctx, enum Fragment nt, std::vector<Node> sub, std::vector<Key> key, uint32_t val = 0) 1720 : 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()) {} 1721 Node(internal::NoDupCheck, MiniscriptContext script_ctx, enum Fragment nt, std::vector<Key> key, uint32_t val = 0) 1722 : fragment(nt), k(val), keys(std::move(key)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {} 1723 Node(internal::NoDupCheck, MiniscriptContext script_ctx, enum Fragment nt, std::vector<Node> sub, uint32_t val = 0) 1724 : fragment(nt), k(val), subs(std::move(sub)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {} 1725 Node(internal::NoDupCheck, MiniscriptContext script_ctx, enum Fragment nt, uint32_t val = 0) 1726 : fragment(nt), k(val), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {} 1727 1728 // Constructors with various argument combinations, which do perform the duplicate key check. 1729 template <typename Ctx> Node(const Ctx& ctx, enum Fragment nt, std::vector<Node> sub, std::vector<unsigned char> arg, uint32_t val = 0) 1730 : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(sub), std::move(arg), val) { DuplicateKeyCheck(ctx); } 1731 template <typename Ctx> Node(const Ctx& ctx, enum Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0) 1732 : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(arg), val) { DuplicateKeyCheck(ctx);} 1733 template <typename Ctx> Node(const Ctx& ctx, enum Fragment nt, std::vector<Node> sub, std::vector<Key> key, uint32_t val = 0) 1734 : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(sub), std::move(key), val) { DuplicateKeyCheck(ctx); } 1735 template <typename Ctx> Node(const Ctx& ctx, enum Fragment nt, std::vector<Key> key, uint32_t val = 0) 1736 : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(key), val) { DuplicateKeyCheck(ctx); } 1737 template <typename Ctx> Node(const Ctx& ctx, enum Fragment nt, std::vector<Node> sub, uint32_t val = 0) 1738 : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(sub), val) { DuplicateKeyCheck(ctx); } 1739 template <typename Ctx> Node(const Ctx& ctx, enum Fragment nt, uint32_t val = 0) 1740 : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, val) { DuplicateKeyCheck(ctx); } 1741 1742 // Delete copy constructor and assignment operator, use Clone() instead 1743 Node(const Node&) = delete; 1744 Node& operator=(const Node&) = delete; 1745 1746 // subs is movable, circumventing recursion, so these are permitted. 1747 Node(Node&&) noexcept = default; 1748 Node& operator=(Node&&) noexcept = default; 1749 }; 1750 1751 namespace internal { 1752 1753 enum class ParseContext { 1754 /** An expression which may be begin with wrappers followed by a colon. */ 1755 WRAPPED_EXPR, 1756 /** A miniscript expression which does not begin with wrappers. */ 1757 EXPR, 1758 1759 /** SWAP wraps the top constructed node with s: */ 1760 SWAP, 1761 /** ALT wraps the top constructed node with a: */ 1762 ALT, 1763 /** CHECK wraps the top constructed node with c: */ 1764 CHECK, 1765 /** DUP_IF wraps the top constructed node with d: */ 1766 DUP_IF, 1767 /** VERIFY wraps the top constructed node with v: */ 1768 VERIFY, 1769 /** NON_ZERO wraps the top constructed node with j: */ 1770 NON_ZERO, 1771 /** ZERO_NOTEQUAL wraps the top constructed node with n: */ 1772 ZERO_NOTEQUAL, 1773 /** WRAP_U will construct an or_i(X,0) node from the top constructed node. */ 1774 WRAP_U, 1775 /** WRAP_T will construct an and_v(X,1) node from the top constructed node. */ 1776 WRAP_T, 1777 1778 /** AND_N will construct an andor(X,Y,0) node from the last two constructed nodes. */ 1779 AND_N, 1780 /** AND_V will construct an and_v node from the last two constructed nodes. */ 1781 AND_V, 1782 /** AND_B will construct an and_b node from the last two constructed nodes. */ 1783 AND_B, 1784 /** ANDOR will construct an andor node from the last three constructed nodes. */ 1785 ANDOR, 1786 /** OR_B will construct an or_b node from the last two constructed nodes. */ 1787 OR_B, 1788 /** OR_C will construct an or_c node from the last two constructed nodes. */ 1789 OR_C, 1790 /** OR_D will construct an or_d node from the last two constructed nodes. */ 1791 OR_D, 1792 /** OR_I will construct an or_i node from the last two constructed nodes. */ 1793 OR_I, 1794 1795 /** THRESH will read a wrapped expression, and then look for a COMMA. If 1796 * no comma follows, it will construct a thresh node from the appropriate 1797 * number of constructed children. Otherwise, it will recurse with another 1798 * THRESH. */ 1799 THRESH, 1800 1801 /** COMMA expects the next element to be ',' and fails if not. */ 1802 COMMA, 1803 /** CLOSE_BRACKET expects the next element to be ')' and fails if not. */ 1804 CLOSE_BRACKET, 1805 }; 1806 1807 int FindNextChar(std::span<const char> in, char m); 1808 1809 /** Parse a key expression fully contained within a fragment with the name given by 'func' */ 1810 template<typename Key, typename Ctx> 1811 std::optional<Key> ParseKey(const std::string& func, std::span<const char>& in, const Ctx& ctx) 1812 { 1813 std::span<const char> expr = script::Expr(in); 1814 if (!script::Func(func, expr)) return {}; 1815 return ctx.FromString(expr); 1816 } 1817 1818 /** Parse a hex string fully contained within a fragment with the name given by 'func' */ 1819 template<typename Ctx> 1820 std::optional<std::vector<unsigned char>> ParseHexStr(const std::string& func, std::span<const char>& in, const size_t expected_size, 1821 const Ctx& ctx) 1822 { 1823 std::span<const char> expr = script::Expr(in); 1824 if (!script::Func(func, expr)) return {}; 1825 std::string val = std::string(expr.begin(), expr.end()); 1826 if (!IsHex(val)) return {}; 1827 auto hash = ParseHex(val); 1828 if (hash.size() != expected_size) return {}; 1829 return hash; 1830 } 1831 1832 /** BuildBack pops the last two elements off `constructed` and wraps them in the specified Fragment */ 1833 template<typename Key> 1834 void BuildBack(const MiniscriptContext script_ctx, Fragment nt, std::vector<Node<Key>>& constructed, const bool reverse = false) 1835 { 1836 Node<Key> child{std::move(constructed.back())}; 1837 constructed.pop_back(); 1838 if (reverse) { 1839 constructed.back() = Node<Key>{internal::NoDupCheck{}, script_ctx, nt, Vector(std::move(child), std::move(constructed.back()))}; 1840 } else { 1841 constructed.back() = Node<Key>{internal::NoDupCheck{}, script_ctx, nt, Vector(std::move(constructed.back()), std::move(child))}; 1842 } 1843 } 1844 1845 /** 1846 * Parse a miniscript from its textual descriptor form. 1847 * This does not check whether the script is valid, let alone sane. The caller is expected to use 1848 * the `IsValidTopLevel()` and `IsSaneTopLevel()` to check for these properties on the node. 1849 */ 1850 template <typename Key, typename Ctx> 1851 inline std::optional<Node<Key>> Parse(std::span<const char> in, const Ctx& ctx) 1852 { 1853 using namespace script; 1854 1855 // Account for the minimum script size for all parsed fragments so far. It "borrows" 1 1856 // script byte from all leaf nodes, counting it instead whenever a space for a recursive 1857 // expression is added (through andor, and_*, or_*, thresh). This guarantees that all fragments 1858 // increment the script_size by at least one, except for: 1859 // - "0", "1": these leafs are only a single byte, so their subtracted-from increment is 0. 1860 // This is not an issue however, as "space" for them has to be created by combinators, 1861 // which do increment script_size. 1862 // - "v:": the v wrapper adds nothing as in some cases it results in no opcode being added 1863 // (instead transforming another opcode into its VERIFY form). However, the v: wrapper has 1864 // to be interleaved with other fragments to be valid, so this is not a concern. 1865 size_t script_size{1}; 1866 size_t max_size{internal::MaxScriptSize(ctx.MsContext())}; 1867 1868 // The two integers are used to hold state for thresh() 1869 std::vector<std::tuple<ParseContext, int64_t, int64_t>> to_parse; 1870 std::vector<Node<Key>> constructed; 1871 1872 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1); 1873 1874 // Parses a multi() or multi_a() from its string representation. Returns false on parsing error. 1875 const auto parse_multi_exp = [&](std::span<const char>& in, const bool is_multi_a) -> bool { 1876 const auto max_keys{is_multi_a ? MAX_PUBKEYS_PER_MULTI_A : MAX_PUBKEYS_PER_MULTISIG}; 1877 const auto required_ctx{is_multi_a ? MiniscriptContext::TAPSCRIPT : MiniscriptContext::P2WSH}; 1878 if (ctx.MsContext() != required_ctx) return false; 1879 // Get threshold 1880 int next_comma = FindNextChar(in, ','); 1881 if (next_comma < 1) return false; 1882 const auto k_to_integral{ToIntegral<int64_t>(std::string_view(in.data(), next_comma))}; 1883 if (!k_to_integral.has_value()) return false; 1884 const int64_t k{k_to_integral.value()}; 1885 in = in.subspan(next_comma + 1); 1886 // Get keys. It is compatible for both compressed and x-only keys. 1887 std::vector<Key> keys; 1888 while (next_comma != -1) { 1889 next_comma = FindNextChar(in, ','); 1890 int key_length = (next_comma == -1) ? FindNextChar(in, ')') : next_comma; 1891 if (key_length < 1) return false; 1892 std::span<const char> sp{in.begin(), in.begin() + key_length}; 1893 auto key = ctx.FromString(sp); 1894 if (!key) return false; 1895 keys.push_back(std::move(*key)); 1896 in = in.subspan(key_length + 1); 1897 } 1898 if (keys.size() < 1 || keys.size() > max_keys) return false; 1899 if (k < 1 || k > (int64_t)keys.size()) return false; 1900 if (is_multi_a) { 1901 // (push + xonly-key + CHECKSIG[ADD]) * n + k + OP_NUMEQUAL(VERIFY), minus one. 1902 script_size += (1 + 32 + 1) * keys.size() + BuildScript(k).size(); 1903 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI_A, std::move(keys), k); 1904 } else { 1905 script_size += 2 + (keys.size() > 16) + (k > 16) + 34 * keys.size(); 1906 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI, std::move(keys), k); 1907 } 1908 return true; 1909 }; 1910 1911 while (!to_parse.empty()) { 1912 if (script_size > max_size) return {}; 1913 1914 // Get the current context we are decoding within 1915 auto [cur_context, n, k] = to_parse.back(); 1916 to_parse.pop_back(); 1917 1918 switch (cur_context) { 1919 case ParseContext::WRAPPED_EXPR: { 1920 std::optional<size_t> colon_index{}; 1921 for (size_t i = 1; i < in.size(); ++i) { 1922 if (in[i] == ':') { 1923 colon_index = i; 1924 break; 1925 } 1926 if (in[i] < 'a' || in[i] > 'z') break; 1927 } 1928 // If there is no colon, this loop won't execute 1929 bool last_was_v{false}; 1930 for (size_t j = 0; colon_index && j < *colon_index; ++j) { 1931 if (script_size > max_size) return {}; 1932 if (in[j] == 'a') { 1933 script_size += 2; 1934 to_parse.emplace_back(ParseContext::ALT, -1, -1); 1935 } else if (in[j] == 's') { 1936 script_size += 1; 1937 to_parse.emplace_back(ParseContext::SWAP, -1, -1); 1938 } else if (in[j] == 'c') { 1939 script_size += 1; 1940 to_parse.emplace_back(ParseContext::CHECK, -1, -1); 1941 } else if (in[j] == 'd') { 1942 script_size += 3; 1943 to_parse.emplace_back(ParseContext::DUP_IF, -1, -1); 1944 } else if (in[j] == 'j') { 1945 script_size += 4; 1946 to_parse.emplace_back(ParseContext::NON_ZERO, -1, -1); 1947 } else if (in[j] == 'n') { 1948 script_size += 1; 1949 to_parse.emplace_back(ParseContext::ZERO_NOTEQUAL, -1, -1); 1950 } else if (in[j] == 'v') { 1951 // do not permit "...vv...:"; it's not valid, and also doesn't trigger early 1952 // failure as script_size isn't incremented. 1953 if (last_was_v) return {}; 1954 to_parse.emplace_back(ParseContext::VERIFY, -1, -1); 1955 } else if (in[j] == 'u') { 1956 script_size += 4; 1957 to_parse.emplace_back(ParseContext::WRAP_U, -1, -1); 1958 } else if (in[j] == 't') { 1959 script_size += 1; 1960 to_parse.emplace_back(ParseContext::WRAP_T, -1, -1); 1961 } else if (in[j] == 'l') { 1962 // The l: wrapper is equivalent to or_i(0,X) 1963 script_size += 4; 1964 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0); 1965 to_parse.emplace_back(ParseContext::OR_I, -1, -1); 1966 } else { 1967 return {}; 1968 } 1969 last_was_v = (in[j] == 'v'); 1970 } 1971 to_parse.emplace_back(ParseContext::EXPR, -1, -1); 1972 if (colon_index) in = in.subspan(*colon_index + 1); 1973 break; 1974 } 1975 case ParseContext::EXPR: { 1976 if (Const("0", in)) { 1977 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0); 1978 } else if (Const("1", in)) { 1979 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_1); 1980 } else if (Const("pk(", in, /*skip=*/false)) { 1981 std::optional<Key> key = ParseKey<Key, Ctx>("pk", in, ctx); 1982 if (!key) return {}; 1983 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_C, Vector(Node<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_K, Vector(std::move(*key))))); 1984 script_size += IsTapscript(ctx.MsContext()) ? 33 : 34; 1985 } else if (Const("pkh(", in, /*skip=*/false)) { 1986 std::optional<Key> key = ParseKey<Key, Ctx>("pkh", in, ctx); 1987 if (!key) return {}; 1988 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_C, Vector(Node<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_H, Vector(std::move(*key))))); 1989 script_size += 24; 1990 } else if (Const("pk_k(", in, /*skip=*/false)) { 1991 std::optional<Key> key = ParseKey<Key, Ctx>("pk_k", in, ctx); 1992 if (!key) return {}; 1993 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_K, Vector(std::move(*key))); 1994 script_size += IsTapscript(ctx.MsContext()) ? 32 : 33; 1995 } else if (Const("pk_h(", in, /*skip=*/false)) { 1996 std::optional<Key> key = ParseKey<Key, Ctx>("pk_h", in, ctx); 1997 if (!key) return {}; 1998 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_H, Vector(std::move(*key))); 1999 script_size += 23; 2000 } else if (Const("sha256(", in, /*skip=*/false)) { 2001 std::optional<std::vector<unsigned char>> hash = ParseHexStr("sha256", in, 32, ctx); 2002 if (!hash) return {}; 2003 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::SHA256, std::move(*hash)); 2004 script_size += 38; 2005 } else if (Const("ripemd160(", in, /*skip=*/false)) { 2006 std::optional<std::vector<unsigned char>> hash = ParseHexStr("ripemd160", in, 20, ctx); 2007 if (!hash) return {}; 2008 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::RIPEMD160, std::move(*hash)); 2009 script_size += 26; 2010 } else if (Const("hash256(", in, /*skip=*/false)) { 2011 std::optional<std::vector<unsigned char>> hash = ParseHexStr("hash256", in, 32, ctx); 2012 if (!hash) return {}; 2013 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::HASH256, std::move(*hash)); 2014 script_size += 38; 2015 } else if (Const("hash160(", in, /*skip=*/false)) { 2016 std::optional<std::vector<unsigned char>> hash = ParseHexStr("hash160", in, 20, ctx); 2017 if (!hash) return {}; 2018 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::HASH160, std::move(*hash)); 2019 script_size += 26; 2020 } else if (Const("after(", in, /*skip=*/false)) { 2021 auto expr = Expr(in); 2022 if (!Func("after", expr)) return {}; 2023 const auto num{ToIntegral<int64_t>(std::string_view(expr.begin(), expr.end()))}; 2024 if (!num.has_value() || *num < 1 || *num >= 0x80000000L) return {}; 2025 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::AFTER, *num); 2026 script_size += 1 + (*num > 16) + (*num > 0x7f) + (*num > 0x7fff) + (*num > 0x7fffff); 2027 } else if (Const("older(", in, /*skip=*/false)) { 2028 auto expr = Expr(in); 2029 if (!Func("older", expr)) return {}; 2030 const auto num{ToIntegral<int64_t>(std::string_view(expr.begin(), expr.end()))}; 2031 if (!num.has_value() || *num < 1 || *num >= 0x80000000L) return {}; 2032 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::OLDER, *num); 2033 script_size += 1 + (*num > 16) + (*num > 0x7f) + (*num > 0x7fff) + (*num > 0x7fffff); 2034 } else if (Const("multi(", in)) { 2035 if (!parse_multi_exp(in, /* is_multi_a = */false)) return {}; 2036 } else if (Const("multi_a(", in)) { 2037 if (!parse_multi_exp(in, /* is_multi_a = */true)) return {}; 2038 } else if (Const("thresh(", in)) { 2039 int next_comma = FindNextChar(in, ','); 2040 if (next_comma < 1) return {}; 2041 const auto k{ToIntegral<int64_t>(std::string_view(in.data(), next_comma))}; 2042 if (!k.has_value() || *k < 1) return {}; 2043 in = in.subspan(next_comma + 1); 2044 // n = 1 here because we read the first WRAPPED_EXPR before reaching THRESH 2045 to_parse.emplace_back(ParseContext::THRESH, 1, *k); 2046 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1); 2047 script_size += 2 + (*k > 16) + (*k > 0x7f) + (*k > 0x7fff) + (*k > 0x7fffff); 2048 } else if (Const("andor(", in)) { 2049 to_parse.emplace_back(ParseContext::ANDOR, -1, -1); 2050 to_parse.emplace_back(ParseContext::CLOSE_BRACKET, -1, -1); 2051 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1); 2052 to_parse.emplace_back(ParseContext::COMMA, -1, -1); 2053 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1); 2054 to_parse.emplace_back(ParseContext::COMMA, -1, -1); 2055 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1); 2056 script_size += 5; 2057 } else { 2058 if (Const("and_n(", in)) { 2059 to_parse.emplace_back(ParseContext::AND_N, -1, -1); 2060 script_size += 5; 2061 } else if (Const("and_b(", in)) { 2062 to_parse.emplace_back(ParseContext::AND_B, -1, -1); 2063 script_size += 2; 2064 } else if (Const("and_v(", in)) { 2065 to_parse.emplace_back(ParseContext::AND_V, -1, -1); 2066 script_size += 1; 2067 } else if (Const("or_b(", in)) { 2068 to_parse.emplace_back(ParseContext::OR_B, -1, -1); 2069 script_size += 2; 2070 } else if (Const("or_c(", in)) { 2071 to_parse.emplace_back(ParseContext::OR_C, -1, -1); 2072 script_size += 3; 2073 } else if (Const("or_d(", in)) { 2074 to_parse.emplace_back(ParseContext::OR_D, -1, -1); 2075 script_size += 4; 2076 } else if (Const("or_i(", in)) { 2077 to_parse.emplace_back(ParseContext::OR_I, -1, -1); 2078 script_size += 4; 2079 } else { 2080 return {}; 2081 } 2082 to_parse.emplace_back(ParseContext::CLOSE_BRACKET, -1, -1); 2083 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1); 2084 to_parse.emplace_back(ParseContext::COMMA, -1, -1); 2085 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1); 2086 } 2087 break; 2088 } 2089 case ParseContext::ALT: { 2090 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_A, Vector(std::move(constructed.back()))}; 2091 break; 2092 } 2093 case ParseContext::SWAP: { 2094 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_S, Vector(std::move(constructed.back()))}; 2095 break; 2096 } 2097 case ParseContext::CHECK: { 2098 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_C, Vector(std::move(constructed.back()))}; 2099 break; 2100 } 2101 case ParseContext::DUP_IF: { 2102 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_D, Vector(std::move(constructed.back()))}; 2103 break; 2104 } 2105 case ParseContext::NON_ZERO: { 2106 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_J, Vector(std::move(constructed.back()))}; 2107 break; 2108 } 2109 case ParseContext::ZERO_NOTEQUAL: { 2110 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_N, Vector(std::move(constructed.back()))}; 2111 break; 2112 } 2113 case ParseContext::VERIFY: { 2114 script_size += (constructed.back().GetType() << "x"_mst); 2115 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_V, Vector(std::move(constructed.back()))}; 2116 break; 2117 } 2118 case ParseContext::WRAP_U: { 2119 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::OR_I, Vector(std::move(constructed.back()), Node<Key>{internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0})}; 2120 break; 2121 } 2122 case ParseContext::WRAP_T: { 2123 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::AND_V, Vector(std::move(constructed.back()), Node<Key>{internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_1})}; 2124 break; 2125 } 2126 case ParseContext::AND_B: { 2127 BuildBack(ctx.MsContext(), Fragment::AND_B, constructed); 2128 break; 2129 } 2130 case ParseContext::AND_N: { 2131 auto mid = std::move(constructed.back()); 2132 constructed.pop_back(); 2133 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})}; 2134 break; 2135 } 2136 case ParseContext::AND_V: { 2137 BuildBack(ctx.MsContext(), Fragment::AND_V, constructed); 2138 break; 2139 } 2140 case ParseContext::OR_B: { 2141 BuildBack(ctx.MsContext(), Fragment::OR_B, constructed); 2142 break; 2143 } 2144 case ParseContext::OR_C: { 2145 BuildBack(ctx.MsContext(), Fragment::OR_C, constructed); 2146 break; 2147 } 2148 case ParseContext::OR_D: { 2149 BuildBack(ctx.MsContext(), Fragment::OR_D, constructed); 2150 break; 2151 } 2152 case ParseContext::OR_I: { 2153 BuildBack(ctx.MsContext(), Fragment::OR_I, constructed); 2154 break; 2155 } 2156 case ParseContext::ANDOR: { 2157 auto right = std::move(constructed.back()); 2158 constructed.pop_back(); 2159 auto mid = std::move(constructed.back()); 2160 constructed.pop_back(); 2161 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), std::move(right))}; 2162 break; 2163 } 2164 case ParseContext::THRESH: { 2165 if (in.size() < 1) return {}; 2166 if (in[0] == ',') { 2167 in = in.subspan(1); 2168 to_parse.emplace_back(ParseContext::THRESH, n+1, k); 2169 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1); 2170 script_size += 2; 2171 } else if (in[0] == ')') { 2172 if (k > n) return {}; 2173 in = in.subspan(1); 2174 // Children are constructed in reverse order, so iterate from end to beginning 2175 std::vector<Node<Key>> subs; 2176 for (int i = 0; i < n; ++i) { 2177 subs.push_back(std::move(constructed.back())); 2178 constructed.pop_back(); 2179 } 2180 std::reverse(subs.begin(), subs.end()); 2181 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::THRESH, std::move(subs), k); 2182 } else { 2183 return {}; 2184 } 2185 break; 2186 } 2187 case ParseContext::COMMA: { 2188 if (in.size() < 1 || in[0] != ',') return {}; 2189 in = in.subspan(1); 2190 break; 2191 } 2192 case ParseContext::CLOSE_BRACKET: { 2193 if (in.size() < 1 || in[0] != ')') return {}; 2194 in = in.subspan(1); 2195 break; 2196 } 2197 } 2198 } 2199 2200 // Sanity checks on the produced miniscript 2201 assert(constructed.size() >= 1); 2202 CHECK_NONFATAL(constructed.size() == 1); 2203 assert(constructed[0].ScriptSize() == script_size); 2204 if (in.size() > 0) return {}; 2205 Node<Key> tl_node{std::move(constructed.front())}; 2206 tl_node.DuplicateKeyCheck(ctx); 2207 return tl_node; 2208 } 2209 2210 /** Decode a script into opcode/push pairs. 2211 * 2212 * Construct a vector with one element per opcode in the script, in reverse order. 2213 * Each element is a pair consisting of the opcode, as well as the data pushed by 2214 * the opcode (including OP_n), if any. OP_CHECKSIGVERIFY, OP_CHECKMULTISIGVERIFY, 2215 * OP_NUMEQUALVERIFY and OP_EQUALVERIFY are decomposed into OP_CHECKSIG, OP_CHECKMULTISIG, 2216 * OP_EQUAL and OP_NUMEQUAL respectively, plus OP_VERIFY. 2217 */ 2218 std::optional<std::vector<Opcode>> DecomposeScript(const CScript& script); 2219 2220 /** Determine whether the passed pair (created by DecomposeScript) is pushing a number. */ 2221 std::optional<int64_t> ParseScriptNumber(const Opcode& in); 2222 2223 enum class DecodeContext { 2224 /** A single expression of type B, K, or V. Specifically, this can't be an 2225 * and_v or an expression of type W (a: and s: wrappers). */ 2226 SINGLE_BKV_EXPR, 2227 /** Potentially multiple SINGLE_BKV_EXPRs as children of (potentially multiple) 2228 * and_v expressions. Syntactic sugar for MAYBE_AND_V + SINGLE_BKV_EXPR. */ 2229 BKV_EXPR, 2230 /** An expression of type W (a: or s: wrappers). */ 2231 W_EXPR, 2232 2233 /** SWAP expects the next element to be OP_SWAP (inside a W-type expression that 2234 * didn't end with FROMALTSTACK), and wraps the top of the constructed stack 2235 * with s: */ 2236 SWAP, 2237 /** ALT expects the next element to be TOALTSTACK (we must have already read a 2238 * FROMALTSTACK earlier), and wraps the top of the constructed stack with a: */ 2239 ALT, 2240 /** CHECK wraps the top constructed node with c: */ 2241 CHECK, 2242 /** DUP_IF wraps the top constructed node with d: */ 2243 DUP_IF, 2244 /** VERIFY wraps the top constructed node with v: */ 2245 VERIFY, 2246 /** NON_ZERO wraps the top constructed node with j: */ 2247 NON_ZERO, 2248 /** ZERO_NOTEQUAL wraps the top constructed node with n: */ 2249 ZERO_NOTEQUAL, 2250 2251 /** MAYBE_AND_V will check if the next part of the script could be a valid 2252 * miniscript sub-expression, and if so it will push AND_V and SINGLE_BKV_EXPR 2253 * to decode it and construct the and_v node. This is recursive, to deal with 2254 * multiple and_v nodes inside each other. */ 2255 MAYBE_AND_V, 2256 /** AND_V will construct an and_v node from the last two constructed nodes. */ 2257 AND_V, 2258 /** AND_B will construct an and_b node from the last two constructed nodes. */ 2259 AND_B, 2260 /** ANDOR will construct an andor node from the last three constructed nodes. */ 2261 ANDOR, 2262 /** OR_B will construct an or_b node from the last two constructed nodes. */ 2263 OR_B, 2264 /** OR_C will construct an or_c node from the last two constructed nodes. */ 2265 OR_C, 2266 /** OR_D will construct an or_d node from the last two constructed nodes. */ 2267 OR_D, 2268 2269 /** In a thresh expression, all sub-expressions other than the first are W-type, 2270 * and end in OP_ADD. THRESH_W will check for this OP_ADD and either push a W_EXPR 2271 * or a SINGLE_BKV_EXPR and jump to THRESH_E accordingly. */ 2272 THRESH_W, 2273 /** THRESH_E constructs a thresh node from the appropriate number of constructed 2274 * children. */ 2275 THRESH_E, 2276 2277 /** ENDIF signals that we are inside some sort of OP_IF structure, which could be 2278 * or_d, or_c, or_i, andor, d:, or j: wrapper, depending on what follows. We read 2279 * a BKV_EXPR and then deal with the next opcode case-by-case. */ 2280 ENDIF, 2281 /** If, inside an ENDIF context, we find an OP_NOTIF before finding an OP_ELSE, 2282 * we could either be in an or_d or an or_c node. We then check for IFDUP to 2283 * distinguish these cases. */ 2284 ENDIF_NOTIF, 2285 /** If, inside an ENDIF context, we find an OP_ELSE, then we could be in either an 2286 * or_i or an andor node. Read the next BKV_EXPR and find either an OP_IF or an 2287 * OP_NOTIF. */ 2288 ENDIF_ELSE, 2289 }; 2290 2291 //! Parse a miniscript from a bitcoin script 2292 template <typename Key, typename Ctx, typename I> 2293 inline std::optional<Node<Key>> DecodeScript(I& in, I last, const Ctx& ctx) 2294 { 2295 // The two integers are used to hold state for thresh() 2296 std::vector<std::tuple<DecodeContext, int64_t, int64_t>> to_parse; 2297 std::vector<Node<Key>> constructed; 2298 2299 // This is the top level, so we assume the type is B 2300 // (in particular, disallowing top level W expressions) 2301 to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1); 2302 2303 while (!to_parse.empty()) { 2304 // Exit early if the Miniscript is not going to be valid. 2305 if (!constructed.empty() && !constructed.back().IsValid()) return {}; 2306 2307 // Get the current context we are decoding within 2308 auto [cur_context, n, k] = to_parse.back(); 2309 to_parse.pop_back(); 2310 2311 switch(cur_context) { 2312 case DecodeContext::SINGLE_BKV_EXPR: { 2313 if (in >= last) return {}; 2314 2315 // Constants 2316 if (in[0].first == OP_1) { 2317 ++in; 2318 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_1); 2319 break; 2320 } 2321 if (in[0].first == OP_0) { 2322 ++in; 2323 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0); 2324 break; 2325 } 2326 // Public keys 2327 if (in[0].second.size() == 33 || in[0].second.size() == 32) { 2328 auto key = ctx.FromPKBytes(in[0].second.begin(), in[0].second.end()); 2329 if (!key) return {}; 2330 ++in; 2331 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_K, Vector(std::move(*key))); 2332 break; 2333 } 2334 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) { 2335 auto key = ctx.FromPKHBytes(in[2].second.begin(), in[2].second.end()); 2336 if (!key) return {}; 2337 in += 5; 2338 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_H, Vector(std::move(*key))); 2339 break; 2340 } 2341 // Time locks 2342 std::optional<int64_t> num; 2343 if (last - in >= 2 && in[0].first == OP_CHECKSEQUENCEVERIFY && (num = ParseScriptNumber(in[1]))) { 2344 in += 2; 2345 if (*num < 1 || *num > 0x7FFFFFFFL) return {}; 2346 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::OLDER, *num); 2347 break; 2348 } 2349 if (last - in >= 2 && in[0].first == OP_CHECKLOCKTIMEVERIFY && (num = ParseScriptNumber(in[1]))) { 2350 in += 2; 2351 if (num < 1 || num > 0x7FFFFFFFL) return {}; 2352 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::AFTER, *num); 2353 break; 2354 } 2355 // Hashes 2356 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) { 2357 if (in[2].first == OP_SHA256 && in[1].second.size() == 32) { 2358 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::SHA256, in[1].second); 2359 in += 7; 2360 break; 2361 } else if (in[2].first == OP_RIPEMD160 && in[1].second.size() == 20) { 2362 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::RIPEMD160, in[1].second); 2363 in += 7; 2364 break; 2365 } else if (in[2].first == OP_HASH256 && in[1].second.size() == 32) { 2366 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::HASH256, in[1].second); 2367 in += 7; 2368 break; 2369 } else if (in[2].first == OP_HASH160 && in[1].second.size() == 20) { 2370 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::HASH160, in[1].second); 2371 in += 7; 2372 break; 2373 } 2374 } 2375 // Multi 2376 if (last - in >= 3 && in[0].first == OP_CHECKMULTISIG) { 2377 if (IsTapscript(ctx.MsContext())) return {}; 2378 std::vector<Key> keys; 2379 const auto n = ParseScriptNumber(in[1]); 2380 if (!n || last - in < 3 + *n) return {}; 2381 if (*n < 1 || *n > 20) return {}; 2382 for (int i = 0; i < *n; ++i) { 2383 if (in[2 + i].second.size() != 33) return {}; 2384 auto key = ctx.FromPKBytes(in[2 + i].second.begin(), in[2 + i].second.end()); 2385 if (!key) return {}; 2386 keys.push_back(std::move(*key)); 2387 } 2388 const auto k = ParseScriptNumber(in[2 + *n]); 2389 if (!k || *k < 1 || *k > *n) return {}; 2390 in += 3 + *n; 2391 std::reverse(keys.begin(), keys.end()); 2392 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI, std::move(keys), *k); 2393 break; 2394 } 2395 // Tapscript's equivalent of multi 2396 if (last - in >= 4 && in[0].first == OP_NUMEQUAL) { 2397 if (!IsTapscript(ctx.MsContext())) return {}; 2398 // The necessary threshold of signatures. 2399 const auto k = ParseScriptNumber(in[1]); 2400 if (!k) return {}; 2401 if (*k < 1 || *k > MAX_PUBKEYS_PER_MULTI_A) return {}; 2402 if (last - in < 2 + *k * 2) return {}; 2403 std::vector<Key> keys; 2404 keys.reserve(*k); 2405 // Walk through the expected (pubkey, CHECKSIG[ADD]) pairs. 2406 for (int pos = 2;; pos += 2) { 2407 if (last - in < pos + 2) return {}; 2408 // Make sure it's indeed an x-only pubkey and a CHECKSIG[ADD], then parse the key. 2409 if (in[pos].first != OP_CHECKSIGADD && in[pos].first != OP_CHECKSIG) return {}; 2410 if (in[pos + 1].second.size() != 32) return {}; 2411 auto key = ctx.FromPKBytes(in[pos + 1].second.begin(), in[pos + 1].second.end()); 2412 if (!key) return {}; 2413 keys.push_back(std::move(*key)); 2414 // Make sure early we don't parse an arbitrary large expression. 2415 if (keys.size() > MAX_PUBKEYS_PER_MULTI_A) return {}; 2416 // OP_CHECKSIG means it was the last one to parse. 2417 if (in[pos].first == OP_CHECKSIG) break; 2418 } 2419 if (keys.size() < (size_t)*k) return {}; 2420 in += 2 + keys.size() * 2; 2421 std::reverse(keys.begin(), keys.end()); 2422 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI_A, std::move(keys), *k); 2423 break; 2424 } 2425 /** In the following wrappers, we only need to push SINGLE_BKV_EXPR rather 2426 * than BKV_EXPR, because and_v commutes with these wrappers. For example, 2427 * c:and_v(X,Y) produces the same script as and_v(X,c:Y). */ 2428 // c: wrapper 2429 if (in[0].first == OP_CHECKSIG) { 2430 ++in; 2431 to_parse.emplace_back(DecodeContext::CHECK, -1, -1); 2432 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1); 2433 break; 2434 } 2435 // v: wrapper 2436 if (in[0].first == OP_VERIFY) { 2437 ++in; 2438 to_parse.emplace_back(DecodeContext::VERIFY, -1, -1); 2439 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1); 2440 break; 2441 } 2442 // n: wrapper 2443 if (in[0].first == OP_0NOTEQUAL) { 2444 ++in; 2445 to_parse.emplace_back(DecodeContext::ZERO_NOTEQUAL, -1, -1); 2446 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1); 2447 break; 2448 } 2449 // Thresh 2450 if (last - in >= 3 && in[0].first == OP_EQUAL && (num = ParseScriptNumber(in[1]))) { 2451 if (*num < 1) return {}; 2452 in += 2; 2453 to_parse.emplace_back(DecodeContext::THRESH_W, 0, *num); 2454 break; 2455 } 2456 // OP_ENDIF can be WRAP_J, WRAP_D, ANDOR, OR_C, OR_D, or OR_I 2457 if (in[0].first == OP_ENDIF) { 2458 ++in; 2459 to_parse.emplace_back(DecodeContext::ENDIF, -1, -1); 2460 to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1); 2461 break; 2462 } 2463 /** In and_b and or_b nodes, we only look for SINGLE_BKV_EXPR, because 2464 * or_b(and_v(X,Y),Z) has script [X] [Y] [Z] OP_BOOLOR, the same as 2465 * and_v(X,or_b(Y,Z)). In this example, the former of these is invalid as 2466 * miniscript, while the latter is valid. So we leave the and_v "outside" 2467 * while decoding. */ 2468 // and_b 2469 if (in[0].first == OP_BOOLAND) { 2470 ++in; 2471 to_parse.emplace_back(DecodeContext::AND_B, -1, -1); 2472 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1); 2473 to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1); 2474 break; 2475 } 2476 // or_b 2477 if (in[0].first == OP_BOOLOR) { 2478 ++in; 2479 to_parse.emplace_back(DecodeContext::OR_B, -1, -1); 2480 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1); 2481 to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1); 2482 break; 2483 } 2484 // Unrecognised expression 2485 return {}; 2486 } 2487 case DecodeContext::BKV_EXPR: { 2488 to_parse.emplace_back(DecodeContext::MAYBE_AND_V, -1, -1); 2489 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1); 2490 break; 2491 } 2492 case DecodeContext::W_EXPR: { 2493 // a: wrapper 2494 if (in >= last) return {}; 2495 if (in[0].first == OP_FROMALTSTACK) { 2496 ++in; 2497 to_parse.emplace_back(DecodeContext::ALT, -1, -1); 2498 } else { 2499 to_parse.emplace_back(DecodeContext::SWAP, -1, -1); 2500 } 2501 to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1); 2502 break; 2503 } 2504 case DecodeContext::MAYBE_AND_V: { 2505 // If we reach a potential AND_V top-level, check if the next part of the script could be another AND_V child 2506 // These op-codes cannot end any well-formed miniscript so cannot be used in an and_v node. 2507 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) { 2508 to_parse.emplace_back(DecodeContext::AND_V, -1, -1); 2509 // BKV_EXPR can contain more AND_V nodes 2510 to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1); 2511 } 2512 break; 2513 } 2514 case DecodeContext::SWAP: { 2515 if (in >= last || in[0].first != OP_SWAP || constructed.empty()) return {}; 2516 ++in; 2517 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_S, Vector(std::move(constructed.back()))}; 2518 break; 2519 } 2520 case DecodeContext::ALT: { 2521 if (in >= last || in[0].first != OP_TOALTSTACK || constructed.empty()) return {}; 2522 ++in; 2523 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_A, Vector(std::move(constructed.back()))}; 2524 break; 2525 } 2526 case DecodeContext::CHECK: { 2527 if (constructed.empty()) return {}; 2528 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_C, Vector(std::move(constructed.back()))}; 2529 break; 2530 } 2531 case DecodeContext::DUP_IF: { 2532 if (constructed.empty()) return {}; 2533 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_D, Vector(std::move(constructed.back()))}; 2534 break; 2535 } 2536 case DecodeContext::VERIFY: { 2537 if (constructed.empty()) return {}; 2538 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_V, Vector(std::move(constructed.back()))}; 2539 break; 2540 } 2541 case DecodeContext::NON_ZERO: { 2542 if (constructed.empty()) return {}; 2543 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_J, Vector(std::move(constructed.back()))}; 2544 break; 2545 } 2546 case DecodeContext::ZERO_NOTEQUAL: { 2547 if (constructed.empty()) return {}; 2548 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_N, Vector(std::move(constructed.back()))}; 2549 break; 2550 } 2551 case DecodeContext::AND_V: { 2552 if (constructed.size() < 2) return {}; 2553 BuildBack(ctx.MsContext(), Fragment::AND_V, constructed, /*reverse=*/true); 2554 break; 2555 } 2556 case DecodeContext::AND_B: { 2557 if (constructed.size() < 2) return {}; 2558 BuildBack(ctx.MsContext(), Fragment::AND_B, constructed, /*reverse=*/true); 2559 break; 2560 } 2561 case DecodeContext::OR_B: { 2562 if (constructed.size() < 2) return {}; 2563 BuildBack(ctx.MsContext(), Fragment::OR_B, constructed, /*reverse=*/true); 2564 break; 2565 } 2566 case DecodeContext::OR_C: { 2567 if (constructed.size() < 2) return {}; 2568 BuildBack(ctx.MsContext(), Fragment::OR_C, constructed, /*reverse=*/true); 2569 break; 2570 } 2571 case DecodeContext::OR_D: { 2572 if (constructed.size() < 2) return {}; 2573 BuildBack(ctx.MsContext(), Fragment::OR_D, constructed, /*reverse=*/true); 2574 break; 2575 } 2576 case DecodeContext::ANDOR: { 2577 if (constructed.size() < 3) return {}; 2578 Node left{std::move(constructed.back())}; 2579 constructed.pop_back(); 2580 Node right{std::move(constructed.back())}; 2581 constructed.pop_back(); 2582 Node mid{std::move(constructed.back())}; 2583 constructed.back() = Node{internal::NoDupCheck{}, ctx.MsContext(), Fragment::ANDOR, Vector(std::move(left), std::move(mid), std::move(right))}; 2584 break; 2585 } 2586 case DecodeContext::THRESH_W: { 2587 if (in >= last) return {}; 2588 if (in[0].first == OP_ADD) { 2589 ++in; 2590 to_parse.emplace_back(DecodeContext::THRESH_W, n+1, k); 2591 to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1); 2592 } else { 2593 to_parse.emplace_back(DecodeContext::THRESH_E, n+1, k); 2594 // All children of thresh have type modifier d, so cannot be and_v 2595 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1); 2596 } 2597 break; 2598 } 2599 case DecodeContext::THRESH_E: { 2600 if (k < 1 || k > n || constructed.size() < static_cast<size_t>(n)) return {}; 2601 std::vector<Node<Key>> subs; 2602 for (int i = 0; i < n; ++i) { 2603 Node sub{std::move(constructed.back())}; 2604 constructed.pop_back(); 2605 subs.push_back(std::move(sub)); 2606 } 2607 constructed.emplace_back(internal::NoDupCheck{}, ctx.MsContext(), Fragment::THRESH, std::move(subs), k); 2608 break; 2609 } 2610 case DecodeContext::ENDIF: { 2611 if (in >= last) return {}; 2612 2613 // could be andor or or_i 2614 if (in[0].first == OP_ELSE) { 2615 ++in; 2616 to_parse.emplace_back(DecodeContext::ENDIF_ELSE, -1, -1); 2617 to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1); 2618 } 2619 // could be j: or d: wrapper 2620 else if (in[0].first == OP_IF) { 2621 if (last - in >= 2 && in[1].first == OP_DUP) { 2622 in += 2; 2623 to_parse.emplace_back(DecodeContext::DUP_IF, -1, -1); 2624 } else if (last - in >= 3 && in[1].first == OP_0NOTEQUAL && in[2].first == OP_SIZE) { 2625 in += 3; 2626 to_parse.emplace_back(DecodeContext::NON_ZERO, -1, -1); 2627 } 2628 else { 2629 return {}; 2630 } 2631 // could be or_c or or_d 2632 } else if (in[0].first == OP_NOTIF) { 2633 ++in; 2634 to_parse.emplace_back(DecodeContext::ENDIF_NOTIF, -1, -1); 2635 } 2636 else { 2637 return {}; 2638 } 2639 break; 2640 } 2641 case DecodeContext::ENDIF_NOTIF: { 2642 if (in >= last) return {}; 2643 if (in[0].first == OP_IFDUP) { 2644 ++in; 2645 to_parse.emplace_back(DecodeContext::OR_D, -1, -1); 2646 } else { 2647 to_parse.emplace_back(DecodeContext::OR_C, -1, -1); 2648 } 2649 // or_c and or_d both require X to have type modifier d so, can't contain and_v 2650 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1); 2651 break; 2652 } 2653 case DecodeContext::ENDIF_ELSE: { 2654 if (in >= last) return {}; 2655 if (in[0].first == OP_IF) { 2656 ++in; 2657 BuildBack(ctx.MsContext(), Fragment::OR_I, constructed, /*reverse=*/true); 2658 } else if (in[0].first == OP_NOTIF) { 2659 ++in; 2660 to_parse.emplace_back(DecodeContext::ANDOR, -1, -1); 2661 // andor requires X to have type modifier d, so it can't be and_v 2662 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1); 2663 } else { 2664 return {}; 2665 } 2666 break; 2667 } 2668 } 2669 } 2670 if (constructed.size() != 1) return {}; 2671 Node tl_node{std::move(constructed.front())}; 2672 tl_node.DuplicateKeyCheck(ctx); 2673 // Note that due to how ComputeType works (only assign the type to the node if the 2674 // subs' types are valid) this would fail if any node of tree is badly typed. 2675 if (!tl_node.IsValidTopLevel()) return {}; 2676 return tl_node; 2677 } 2678 2679 } // namespace internal 2680 2681 template <typename Ctx> 2682 inline std::optional<Node<typename Ctx::Key>> FromString(const std::string& str, const Ctx& ctx) 2683 { 2684 return internal::Parse<typename Ctx::Key>(str, ctx); 2685 } 2686 2687 template <typename Ctx> 2688 inline std::optional<Node<typename Ctx::Key>> FromScript(const CScript& script, const Ctx& ctx) 2689 { 2690 using namespace internal; 2691 // A too large Script is necessarily invalid, don't bother parsing it. 2692 if (script.size() > MaxScriptSize(ctx.MsContext())) return {}; 2693 auto decomposed = DecomposeScript(script); 2694 if (!decomposed) return {}; 2695 auto it = decomposed->begin(); 2696 auto ret = DecodeScript<typename Ctx::Key>(it, decomposed->end(), ctx); 2697 if (!ret) return {}; 2698 if (it != decomposed->end()) return {}; 2699 return ret; 2700 } 2701 2702 } // namespace miniscript 2703 2704 #endif // BITCOIN_SCRIPT_MINISCRIPT_H