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