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