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