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