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