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