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