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