Branch data Line data Source code
1 : : // Copyright (c) 2019-2022 The Bitcoin Core developers
2 : : // Distributed under the MIT software license, see the accompanying
3 : : // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 : :
5 : : #ifndef BITCOIN_SCRIPT_MINISCRIPT_H
6 : : #define BITCOIN_SCRIPT_MINISCRIPT_H
7 : :
8 : : #include <algorithm>
9 : : #include <functional>
10 : : #include <numeric>
11 : : #include <memory>
12 : : #include <optional>
13 : : #include <string>
14 : : #include <vector>
15 : :
16 : : #include <assert.h>
17 : : #include <cstdlib>
18 : :
19 : : #include <policy/policy.h>
20 : : #include <primitives/transaction.h>
21 : : #include <script/script.h>
22 : : #include <span.h>
23 : : #include <util/spanparsing.h>
24 : : #include <util/strencodings.h>
25 : : #include <util/string.h>
26 : : #include <util/vector.h>
27 : :
28 : : namespace miniscript {
29 : :
30 : : /** This type encapsulates the miniscript type system properties.
31 : : *
32 : : * Every miniscript expression is one of 4 basic types, and additionally has
33 : : * a number of boolean type properties.
34 : : *
35 : : * The basic types are:
36 : : * - "B" Base:
37 : : * - Takes its inputs from the top of the stack.
38 : : * - When satisfied, pushes a nonzero value of up to 4 bytes onto the stack.
39 : : * - When dissatisfied, pushes a 0 onto the stack.
40 : : * - This is used for most expressions, and required for the top level one.
41 : : * - For example: older(n) = <n> OP_CHECKSEQUENCEVERIFY.
42 : : * - "V" Verify:
43 : : * - Takes its inputs from the top of the stack.
44 : : * - When satisfied, pushes nothing.
45 : : * - Cannot be dissatisfied.
46 : : * - This can be obtained by adding an OP_VERIFY to a B, modifying the last opcode
47 : : * of a B to its -VERIFY version (only for OP_CHECKSIG, OP_CHECKSIGVERIFY
48 : : * and OP_EQUAL), or by combining a V fragment under some conditions.
49 : : * - For example vc:pk_k(key) = <key> OP_CHECKSIGVERIFY
50 : : * - "K" Key:
51 : : * - Takes its inputs from the top of the stack.
52 : : * - Becomes a B when followed by OP_CHECKSIG.
53 : : * - Always pushes a public key onto the stack, for which a signature is to be
54 : : * provided to satisfy the expression.
55 : : * - For example pk_h(key) = OP_DUP OP_HASH160 <Hash160(key)> OP_EQUALVERIFY
56 : : * - "W" Wrapped:
57 : : * - Takes its input from one below the top of the stack.
58 : : * - When satisfied, pushes a nonzero value (like B) on top of the stack, or one below.
59 : : * - When dissatisfied, pushes 0 op top of the stack or one below.
60 : : * - Is always "OP_SWAP [B]" or "OP_TOALTSTACK [B] OP_FROMALTSTACK".
61 : : * - For example sc:pk_k(key) = OP_SWAP <key> OP_CHECKSIG
62 : : *
63 : : * There a type properties that help reasoning about correctness:
64 : : * - "z" Zero-arg:
65 : : * - Is known to always consume exactly 0 stack elements.
66 : : * - For example after(n) = <n> OP_CHECKLOCKTIMEVERIFY
67 : : * - "o" One-arg:
68 : : * - Is known to always consume exactly 1 stack element.
69 : : * - Conflicts with property 'z'
70 : : * - For example sha256(hash) = OP_SIZE 32 OP_EQUALVERIFY OP_SHA256 <hash> OP_EQUAL
71 : : * - "n" Nonzero:
72 : : * - For every way this expression can be satisfied, a satisfaction exists that never needs
73 : : * a zero top stack element.
74 : : * - Conflicts with property 'z' and with type 'W'.
75 : : * - "d" Dissatisfiable:
76 : : * - There is an easy way to construct a dissatisfaction for this expression.
77 : : * - Conflicts with type 'V'.
78 : : * - "u" Unit:
79 : : * - In case of satisfaction, an exact 1 is put on the stack (rather than just nonzero).
80 : : * - Conflicts with type 'V'.
81 : : *
82 : : * Additional type properties help reasoning about nonmalleability:
83 : : * - "e" Expression:
84 : : * - This implies property 'd', but the dissatisfaction is nonmalleable.
85 : : * - This generally requires 'e' for all subexpressions which are invoked for that
86 : : * dissatifsaction, and property 'f' for the unexecuted subexpressions in that case.
87 : : * - Conflicts with type 'V'.
88 : : * - "f" Forced:
89 : : * - Dissatisfactions (if any) for this expression always involve at least one signature.
90 : : * - Is always true for type 'V'.
91 : : * - "s" Safe:
92 : : * - Satisfactions for this expression always involve at least one signature.
93 : : * - "m" Nonmalleable:
94 : : * - For every way this expression can be satisfied (which may be none),
95 : : * a nonmalleable satisfaction exists.
96 : : * - This generally requires 'm' for all subexpressions, and 'e' for all subexpressions
97 : : * which are dissatisfied when satisfying the parent.
98 : : *
99 : : * One type property is an implementation detail:
100 : : * - "x" Expensive verify:
101 : : * - Expressions with this property have a script whose last opcode is not EQUAL, CHECKSIG, or CHECKMULTISIG.
102 : : * - Not having this property means that it can be converted to a V at no cost (by switching to the
103 : : * -VERIFY version of the last opcode).
104 : : *
105 : : * Five more type properties for representing timelock information. Spend paths
106 : : * in miniscripts containing conflicting timelocks and heightlocks cannot be spent together.
107 : : * This helps users detect if miniscript does not match the semantic behaviour the
108 : : * user expects.
109 : : * - "g" Whether the branch contains a relative time timelock
110 : : * - "h" Whether the branch contains a relative height timelock
111 : : * - "i" Whether the branch contains an absolute time timelock
112 : : * - "j" Whether the branch contains an absolute height timelock
113 : : * - "k"
114 : : * - Whether all satisfactions of this expression don't contain a mix of heightlock and timelock
115 : : * of the same type.
116 : : * - If the miniscript does not have the "k" property, the miniscript template will not match
117 : : * the user expectation of the corresponding spending policy.
118 : : * For each of these properties the subset rule holds: an expression with properties X, Y, and Z, is also
119 : : * valid in places where an X, a Y, a Z, an XY, ... is expected.
120 : : */
121 : : class Type {
122 : : //! Internal bitmap of properties (see ""_mst operator for details).
123 : : uint32_t m_flags;
124 : :
125 : : //! Internal constructor used by the ""_mst operator.
126 : 250937220 : explicit constexpr Type(uint32_t flags) : m_flags(flags) {}
127 : :
128 : : public:
129 : : //! The only way to publicly construct a Type is using this literal operator.
130 : : friend constexpr Type operator"" _mst(const char* c, size_t l);
131 : :
132 : : //! Compute the type with the union of properties.
133 : 93691635 : constexpr Type operator|(Type x) const { return Type(m_flags | x.m_flags); }
134 : :
135 : : //! Compute the type with the intersection of properties.
136 : 18013232 : constexpr Type operator&(Type x) const { return Type(m_flags & x.m_flags); }
137 : :
138 : : //! Check whether the left hand's properties are superset of the right's (= left is a subtype of right).
139 : 37271005 : constexpr bool operator<<(Type x) const { return (x.m_flags & ~m_flags) == 0; }
140 : :
141 : : //! Comparison operator to enable use in sets/maps (total ordering incompatible with <<).
142 : 494882 : constexpr bool operator<(Type x) const { return m_flags < x.m_flags; }
143 : :
144 : : //! Equality operator.
145 : 1369664 : constexpr bool operator==(Type x) const { return m_flags == x.m_flags; }
146 : :
147 : : //! The empty type if x is false, itself otherwise.
148 [ + + ]: 6398966 : constexpr Type If(bool x) const { return Type(x ? m_flags : 0); }
149 : : };
150 : :
151 : : //! Literal operator to construct Type objects.
152 : 57044117 : inline constexpr Type operator"" _mst(const char* c, size_t l) {
153 : 57044117 : Type typ{0};
154 : :
155 [ + + ]: 132833387 : for (const char *p = c; p < c + l; p++) {
156 : 75789270 : typ = typ | Type(
157 [ + + ]: 145527517 : *p == 'B' ? 1 << 0 : // Base type
158 [ + + ]: 131642778 : *p == 'V' ? 1 << 1 : // Verify type
159 [ + + ]: 118298384 : *p == 'K' ? 1 << 2 : // Key type
160 [ + + ]: 109344812 : *p == 'W' ? 1 << 3 : // Wrapped type
161 [ + + ]: 99433535 : *p == 'z' ? 1 << 4 : // Zero-arg property
162 [ + + ]: 89878811 : *p == 'o' ? 1 << 5 : // One-arg property
163 [ + + ]: 82831095 : *p == 'n' ? 1 << 6 : // Nonzero arg property
164 [ + + ]: 73468598 : *p == 'd' ? 1 << 7 : // Dissatisfiable property
165 [ + + ]: 64794511 : *p == 'u' ? 1 << 8 : // Unit property
166 [ + + ]: 56877579 : *p == 'e' ? 1 << 9 : // Expression property
167 [ + + ]: 47619847 : *p == 'f' ? 1 << 10 : // Forced property
168 [ + + ]: 38965851 : *p == 's' ? 1 << 11 : // Safe property
169 [ + + ]: 31460521 : *p == 'm' ? 1 << 12 : // Nonmalleable property
170 [ + + ]: 25603210 : *p == 'x' ? 1 << 13 : // Expensive verify
171 [ + + ]: 21136899 : *p == 'g' ? 1 << 14 : // older: contains relative time timelock (csv_time)
172 [ + + ]: 16993915 : *p == 'h' ? 1 << 15 : // older: contains relative height timelock (csv_height)
173 [ + + ]: 12856751 : *p == 'i' ? 1 << 16 : // after: contains time timelock (cltv_time)
174 [ + + ]: 8724378 : *p == 'j' ? 1 << 17 : // after: contains height timelock (cltv_height)
175 [ + - ]: 3330142 : *p == 'k' ? 1 << 18 : // does not contain a combination of height and time locks
176 [ # # # # ]: 0 : (throw std::logic_error("Unknown character in _mst literal"), 0)
177 : : );
178 : 75789270 : }
179 : :
180 : 57044117 : return typ;
181 : 0 : }
182 : :
183 : : using Opcode = std::pair<opcodetype, std::vector<unsigned char>>;
184 : :
185 : : template<typename Key> struct Node;
186 : : template<typename Key> using NodeRef = std::shared_ptr<const Node<Key>>;
187 : :
188 : : //! Construct a miniscript node as a shared_ptr.
189 : : template<typename Key, typename... Args>
190 : 1049513 : NodeRef<Key> MakeNodeRef(Args&&... args) { return std::make_shared<const Node<Key>>(std::forward<Args>(args)...); }
191 : :
192 : : //! The different node types in miniscript.
193 : : enum class Fragment {
194 : : JUST_0, //!< OP_0
195 : : JUST_1, //!< OP_1
196 : : PK_K, //!< [key]
197 : : PK_H, //!< OP_DUP OP_HASH160 [keyhash] OP_EQUALVERIFY
198 : : OLDER, //!< [n] OP_CHECKSEQUENCEVERIFY
199 : : AFTER, //!< [n] OP_CHECKLOCKTIMEVERIFY
200 : : SHA256, //!< OP_SIZE 32 OP_EQUALVERIFY OP_SHA256 [hash] OP_EQUAL
201 : : HASH256, //!< OP_SIZE 32 OP_EQUALVERIFY OP_HASH256 [hash] OP_EQUAL
202 : : RIPEMD160, //!< OP_SIZE 32 OP_EQUALVERIFY OP_RIPEMD160 [hash] OP_EQUAL
203 : : HASH160, //!< OP_SIZE 32 OP_EQUALVERIFY OP_HASH160 [hash] OP_EQUAL
204 : : WRAP_A, //!< OP_TOALTSTACK [X] OP_FROMALTSTACK
205 : : WRAP_S, //!< OP_SWAP [X]
206 : : WRAP_C, //!< [X] OP_CHECKSIG
207 : : WRAP_D, //!< OP_DUP OP_IF [X] OP_ENDIF
208 : : WRAP_V, //!< [X] OP_VERIFY (or -VERIFY version of last opcode in X)
209 : : WRAP_J, //!< OP_SIZE OP_0NOTEQUAL OP_IF [X] OP_ENDIF
210 : : WRAP_N, //!< [X] OP_0NOTEQUAL
211 : : AND_V, //!< [X] [Y]
212 : : AND_B, //!< [X] [Y] OP_BOOLAND
213 : : OR_B, //!< [X] [Y] OP_BOOLOR
214 : : OR_C, //!< [X] OP_NOTIF [Y] OP_ENDIF
215 : : OR_D, //!< [X] OP_IFDUP OP_NOTIF [Y] OP_ENDIF
216 : : OR_I, //!< OP_IF [X] OP_ELSE [Y] OP_ENDIF
217 : : ANDOR, //!< [X] OP_NOTIF [Z] OP_ELSE [Y] OP_ENDIF
218 : : THRESH, //!< [X1] ([Xn] OP_ADD)* [k] OP_EQUAL
219 : : MULTI, //!< [k] [key_n]* [n] OP_CHECKMULTISIG
220 : : // AND_N(X,Y) is represented as ANDOR(X,Y,0)
221 : : // WRAP_T(X) is represented as AND_V(X,1)
222 : : // WRAP_L(X) is represented as OR_I(0,X)
223 : : // WRAP_U(X) is represented as OR_I(X,0)
224 : : };
225 : :
226 : : enum class Availability {
227 : : NO,
228 : : YES,
229 : : MAYBE,
230 : : };
231 : :
232 : : namespace internal {
233 : :
234 : : //! Helper function for Node::CalcType.
235 : : 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);
236 : :
237 : : //! Helper function for Node::CalcScriptLen.
238 : : size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs, size_t n_keys);
239 : :
240 : : //! A helper sanitizer/checker for the output of CalcType.
241 : : Type SanitizeType(Type x);
242 : :
243 : : //! An object representing a sequence of witness stack elements.
244 : : struct InputStack {
245 : : /** Whether this stack is valid for its intended purpose (satisfaction or dissatisfaction of a Node).
246 : : * The MAYBE value is used for size estimation, when keys/preimages may actually be unavailable,
247 : : * but may be available at signing time. This makes the InputStack structure and signing logic,
248 : : * filled with dummy signatures/preimages usable for witness size estimation.
249 : : */
250 : 64242 : Availability available = Availability::YES;
251 : : //! Whether this stack contains a digital signature.
252 : 64242 : bool has_sig = false;
253 : : //! Whether this stack is malleable (can be turned into an equally valid other stack by a third party).
254 : 64242 : bool malleable = false;
255 : : //! Whether this stack is non-canonical (using a construction known to be unnecessary for satisfaction).
256 : : //! Note that this flag does not affect the satisfaction algorithm; it is only used for sanity checking.
257 : 64242 : bool non_canon = false;
258 : : //! Serialized witness size.
259 : 1384 : size_t size = 0;
260 : : //! Data elements.
261 : : std::vector<std::vector<unsigned char>> stack;
262 : : //! Construct an empty stack (valid).
263 : 2768 : InputStack() {}
264 : : //! Construct a valid single-element stack (with an element up to 75 bytes).
265 : 125716 : InputStack(std::vector<unsigned char> in) : size(in.size() + 1), stack(Vector(std::move(in))) {}
266 : : //! Change availability
267 : : InputStack& SetAvailable(Availability avail);
268 : : //! Mark this input stack as having a signature.
269 : : InputStack& SetWithSig();
270 : : //! Mark this input stack as non-canonical (known to not be necessary in non-malleable satisfactions).
271 : : InputStack& SetNonCanon();
272 : : //! Mark this input stack as malleable.
273 : : InputStack& SetMalleable(bool x = true);
274 : : //! Concatenate two input stacks.
275 : : friend InputStack operator+(InputStack a, InputStack b);
276 : : //! Choose between two potential input stacks.
277 : : friend InputStack operator|(InputStack a, InputStack b);
278 : : };
279 : :
280 : : /** A stack consisting of a single zero-length element (interpreted as 0 by the script interpreter in numeric context). */
281 : : static const auto ZERO = InputStack(std::vector<unsigned char>());
282 : : /** A stack consisting of a single malleable 32-byte 0x0000...0000 element (for dissatisfying hash challenges). */
283 : : static const auto ZERO32 = InputStack(std::vector<unsigned char>(32, 0)).SetMalleable();
284 : : /** A stack consisting of a single 0x01 element (interpreted as 1 by the script interpreted in numeric context). */
285 : : static const auto ONE = InputStack(Vector((unsigned char)1));
286 : : /** The empty stack. */
287 : : static const auto EMPTY = InputStack();
288 : : /** A stack representing the lack of any (dis)satisfactions. */
289 : : static const auto INVALID = InputStack().SetAvailable(Availability::NO);
290 : :
291 : : //! A pair of a satisfaction and a dissatisfaction InputStack.
292 : : struct InputResult {
293 : : InputStack nsat, sat;
294 : :
295 : : template<typename A, typename B>
296 [ + - + - : 146738 : InputResult(A&& in_nsat, B&& in_sat) : nsat(std::forward<A>(in_nsat)), sat(std::forward<B>(in_sat)) {}
+ - ]
297 : : };
298 : :
299 : : //! Class whose objects represent the maximum of a list of integers.
300 : : template<typename I>
301 : : struct MaxInt {
302 : : const bool valid;
303 : : const I value;
304 : :
305 : 29059774 : MaxInt() : valid(false), value(0) {}
306 : 6646066 : MaxInt(I val) : valid(true), value(val) {}
307 : :
308 : 30929053 : friend MaxInt<I> operator+(const MaxInt<I>& a, const MaxInt<I>& b) {
309 [ + + + + ]: 30929053 : if (!a.valid || !b.valid) return {};
310 : 3282606 : return a.value + b.value;
311 : 30929053 : }
312 : :
313 : 15019221 : friend MaxInt<I> operator|(const MaxInt<I>& a, const MaxInt<I>& b) {
314 [ + + ]: 15019221 : if (!a.valid) return b;
315 [ + + ]: 1617494 : if (!b.valid) return a;
316 : 1060242 : return std::max(a.value, b.value);
317 : 15019221 : }
318 : : };
319 : :
320 : : struct Ops {
321 : : //! Non-push opcodes.
322 : : uint32_t count;
323 : : //! Number of keys in possibly executed OP_CHECKMULTISIG(VERIFY)s to satisfy.
324 : : MaxInt<uint32_t> sat;
325 : : //! Number of keys in possibly executed OP_CHECKMULTISIG(VERIFY)s to dissatisfy.
326 : : MaxInt<uint32_t> dsat;
327 : :
328 : 1049513 : Ops(uint32_t in_count, MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : count(in_count), sat(in_sat), dsat(in_dsat) {};
329 : : };
330 : :
331 : : struct StackSize {
332 : : //! Maximum stack size to satisfy;
333 : : MaxInt<uint32_t> sat;
334 : : //! Maximum stack size to dissatisfy;
335 : : MaxInt<uint32_t> dsat;
336 : :
337 : 705190 : StackSize(MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : sat(in_sat), dsat(in_dsat) {};
338 : : };
339 : :
340 : : struct WitnessSize {
341 : : //! Maximum witness size to satisfy;
342 : : MaxInt<uint32_t> sat;
343 : : //! Maximum witness size to dissatisfy;
344 : : MaxInt<uint32_t> dsat;
345 : :
346 : 705190 : WitnessSize(MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : sat(in_sat), dsat(in_dsat) {};
347 : : };
348 : :
349 : : struct NoDupCheck {};
350 : :
351 : : } // namespace internal
352 : :
353 : : //! A node in a miniscript expression.
354 : : template<typename Key>
355 : : struct Node {
356 : : //! What node type this node is.
357 : : const Fragment fragment;
358 : : //! The k parameter (time for OLDER/AFTER, threshold for THRESH(_M))
359 : : const uint32_t k = 0;
360 : : //! The keys used by this expression (only for PK_K/PK_H/MULTI)
361 : : const std::vector<Key> keys;
362 : : //! The data bytes in this expression (only for HASH160/HASH256/SHA256/RIPEMD10).
363 : : const std::vector<unsigned char> data;
364 : : //! Subexpressions (for WRAP_*/AND_*/OR_*/ANDOR/THRESH)
365 : : const std::vector<NodeRef<Key>> subs;
366 : :
367 : : private:
368 : : //! Cached ops counts.
369 : : const internal::Ops ops;
370 : : //! Cached stack size bounds.
371 : : const internal::StackSize ss;
372 : : //! Cached witness size bounds.
373 : : const internal::WitnessSize ws;
374 : : //! Cached expression type (computed by CalcType and fed through SanitizeType).
375 : : const Type typ;
376 : : //! Cached script length (computed by CalcScriptLen).
377 : : const size_t scriptlen;
378 : : //! Whether a public key appears more than once in this node. This value is initialized
379 : : //! by all constructors except the NoDupCheck ones. The NoDupCheck ones skip the
380 : : //! computation, requiring it to be done manually by invoking DuplicateKeyCheck().
381 : : //! DuplicateKeyCheck(), or a non-NoDupCheck constructor, will compute has_duplicate_keys
382 : : //! for all subnodes as well.
383 : : mutable std::optional<bool> has_duplicate_keys;
384 : :
385 : :
386 : : //! Compute the length of the script for this miniscript (including children).
387 : 1049513 : size_t CalcScriptLen() const {
388 : 1049513 : size_t subsize = 0;
389 [ + + + + ]: 2037723 : for (const auto& sub : subs) {
390 : 988210 : subsize += sub->ScriptSize();
391 : : }
392 [ + + + + ]: 1049513 : Type sub0type = subs.size() > 0 ? subs[0]->GetType() : ""_mst;
393 : 1049513 : return internal::ComputeScriptLen(fragment, sub0type, subsize, k, subs.size(), keys.size());
394 : : }
395 : :
396 : : /* Apply a recursive algorithm to a Miniscript tree, without actual recursive calls.
397 : : *
398 : : * The algorithm is defined by two functions: downfn and upfn. Conceptually, the
399 : : * result can be thought of as first using downfn to compute a "state" for each node,
400 : : * from the root down to the leaves. Then upfn is used to compute a "result" for each
401 : : * node, from the leaves back up to the root, which is then returned. In the actual
402 : : * implementation, both functions are invoked in an interleaved fashion, performing a
403 : : * depth-first traversal of the tree.
404 : : *
405 : : * In more detail, it is invoked as node.TreeEvalMaybe<Result>(root, downfn, upfn):
406 : : * - root is the state of the root node, of type State.
407 : : * - downfn is a callable (State&, const Node&, size_t) -> State, which given a
408 : : * node, its state, and an index of one of its children, computes the state of that
409 : : * child. It can modify the state. Children of a given node will have downfn()
410 : : * called in order.
411 : : * - upfn is a callable (State&&, const Node&, Span<Result>) -> std::optional<Result>,
412 : : * which given a node, its state, and a Span of the results of its children,
413 : : * computes the result of the node. If std::nullopt is returned by upfn,
414 : : * TreeEvalMaybe() immediately returns std::nullopt.
415 : : * The return value of TreeEvalMaybe is the result of the root node.
416 : : *
417 : : * Result type cannot be bool due to the std::vector<bool> specialization.
418 : : */
419 : : template<typename Result, typename State, typename DownFn, typename UpFn>
420 : 27413 : std::optional<Result> TreeEvalMaybe(State root_state, DownFn downfn, UpFn upfn) const
421 : : {
422 : : /** Entries of the explicit stack tracked in this algorithm. */
423 : : struct StackElem
424 : : {
425 : : const Node& node; //!< The node being evaluated.
426 : : size_t expanded; //!< How many children of this node have been expanded.
427 : : State state; //!< The state for that node.
428 : :
429 : 1627935 : StackElem(const Node& node_, size_t exp_, State&& state_) :
430 : 1627935 : node(node_), expanded(exp_), state(std::move(state_)) {}
431 : : };
432 : : /* Stack of tree nodes being explored. */
433 : 27413 : std::vector<StackElem> stack;
434 : : /* Results of subtrees so far. Their order and mapping to tree nodes
435 : : * is implicitly defined by stack. */
436 : 27413 : std::vector<Result> results;
437 [ + - + - : 27413 : stack.emplace_back(*this, 0, std::move(root_state));
+ - + - +
- + - + -
+ - ]
438 : :
439 : : /* Here is a demonstration of the algorithm, for an example tree A(B,C(D,E),F).
440 : : * State variables are omitted for simplicity.
441 : : *
442 : : * First: stack=[(A,0)] results=[]
443 : : * stack=[(A,1),(B,0)] results=[]
444 : : * stack=[(A,1)] results=[B]
445 : : * stack=[(A,2),(C,0)] results=[B]
446 : : * stack=[(A,2),(C,1),(D,0)] results=[B]
447 : : * stack=[(A,2),(C,1)] results=[B,D]
448 : : * stack=[(A,2),(C,2),(E,0)] results=[B,D]
449 : : * stack=[(A,2),(C,2)] results=[B,D,E]
450 : : * stack=[(A,2)] results=[B,C]
451 : : * stack=[(A,3),(F,0)] results=[B,C]
452 : : * stack=[(A,3)] results=[B,C,F]
453 : : * Final: stack=[] results=[A]
454 : : */
455 [ + + + + : 3254722 : while (stack.size()) {
+ + + + +
+ + + + +
+ + ]
456 : 3227394 : const Node& node = stack.back().node;
457 [ + + + + : 3227394 : if (stack.back().expanded < node.subs.size()) {
+ + + + +
+ + + + +
+ + ]
458 : : /* We encounter a tree node with at least one unexpanded child.
459 : : * Expand it. By the time we hit this node again, the result of
460 : : * that child (and all earlier children) will be at the end of `results`. */
461 : 1600522 : size_t child_index = stack.back().expanded++;
462 [ + - + - : 1600522 : State child_state = downfn(stack.back().state, node, child_index);
+ - + - +
- + - + -
+ - ]
463 [ + - + - : 1600522 : stack.emplace_back(*node.subs[child_index], 0, std::move(child_state));
+ - + - +
- + - + -
+ - ]
464 : 1600522 : continue;
465 : : }
466 : : // Invoke upfn with the last node.subs.size() elements of results as input.
467 [ + - + - : 1626872 : assert(results.size() >= node.subs.size());
+ - + - +
- + - + -
+ - ]
468 [ + - + - : 1626872 : std::optional<Result> result{upfn(std::move(stack.back().state), node,
+ - + - +
- + - + -
+ - ]
469 [ + - + - : 1626872 : Span<Result>{results}.last(node.subs.size()))};
+ - + - +
- + - + -
+ - ]
470 : : // If evaluation returns std::nullopt, abort immediately.
471 [ + - + - : 1626872 : if (!result) return {};
+ - + - +
+ + - + -
+ - ]
472 : : // Replace the last node.subs.size() elements of results with the new result.
473 [ + - + - : 1626787 : results.erase(results.end() - node.subs.size(), results.end());
+ - + - +
- + - + -
+ - ]
474 [ + - + - : 1626787 : results.push_back(std::move(*result));
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - ]
475 : 1626787 : stack.pop_back();
476 [ - + - + : 1425429 : }
- + + + -
+ - + -
+ ]
477 : : // The final remaining results element is the root result, return it.
478 [ + - + + : 27328 : assert(results.size() == 1);
+ - + + -
+ + - + -
- + ]
479 [ + - + - : 27328 : return std::move(results[0]);
+ - + - +
- + - + -
+ - ]
480 : 27413 : }
481 : :
482 : : /** Like TreeEvalMaybe, but without downfn or State type.
483 : : * upfn takes (const Node&, Span<Result>) and returns std::optional<Result>. */
484 : : template<typename Result, typename UpFn>
485 : : std::optional<Result> TreeEvalMaybe(UpFn upfn) const
486 : : {
487 : : struct DummyState {};
488 : : return TreeEvalMaybe<Result>(DummyState{},
489 : : [](DummyState, const Node&, size_t) { return DummyState{}; },
490 : : [&upfn](DummyState, const Node& node, Span<Result> subs) {
491 : : return upfn(node, subs);
492 : : }
493 : : );
494 : : }
495 : :
496 : : /** Like TreeEvalMaybe, but always produces a result. upfn must return Result. */
497 : : template<typename Result, typename State, typename DownFn, typename UpFn>
498 : 4243 : Result TreeEval(State root_state, DownFn&& downfn, UpFn upfn) const
499 : : {
500 : : // Invoke TreeEvalMaybe with upfn wrapped to return std::optional<Result>, and then
501 : : // unconditionally dereference the result (it cannot be std::nullopt).
502 [ + - + - ]: 8486 : return std::move(*TreeEvalMaybe<Result>(std::move(root_state),
503 : 4243 : std::forward<DownFn>(downfn),
504 : 311945 : [&upfn](State&& state, const Node& node, Span<Result> subs) {
505 : 307702 : Result res{upfn(std::move(state), node, subs)};
506 [ + - + - ]: 307702 : return std::optional<Result>(std::move(res));
507 : 307702 : }
508 : : ));
509 : 0 : }
510 : :
511 : : /** Like TreeEval, but without downfn or State type.
512 : : * upfn takes (const Node&, Span<Result>) and returns Result. */
513 : : template<typename Result, typename UpFn>
514 : 19843 : Result TreeEval(UpFn upfn) const
515 : : {
516 : : struct DummyState {};
517 [ + - + - : 19843 : return std::move(*TreeEvalMaybe<Result>(DummyState{},
+ - + - ]
518 : 1074811 : [](DummyState, const Node&, size_t) { return DummyState{}; },
519 : 1114497 : [&upfn](DummyState, const Node& node, Span<Result> subs) {
520 : 1094654 : Result res{upfn(node, subs)};
521 [ + - + - : 1094654 : return std::optional<Result>(std::move(res));
+ - + - ]
522 : 893211 : }
523 : : ));
524 : 0 : }
525 : :
526 : : /** Compare two miniscript subtrees, using a non-recursive algorithm. */
527 : 2385 : friend int Compare(const Node<Key>& node1, const Node<Key>& node2)
528 : : {
529 : 2385 : std::vector<std::pair<const Node<Key>&, const Node<Key>&>> queue;
530 [ + - ]: 2385 : queue.emplace_back(node1, node2);
531 [ + + ]: 163044 : while (!queue.empty()) {
532 : 3369069 : const auto& [a, b] = queue.back();
533 : 160659 : queue.pop_back();
534 [ + - + - : 1285272 : if (std::tie(a.fragment, a.k, a.keys, a.data) < std::tie(b.fragment, b.k, b.keys, b.data)) return -1;
+ - + - +
- + - + -
+ - + - ]
535 [ + - + - : 1285272 : if (std::tie(b.fragment, b.k, b.keys, b.data) < std::tie(a.fragment, a.k, a.keys, a.data)) return 1;
+ - + - +
- + - + -
+ - + - ]
536 [ + - + - ]: 321318 : if (a.subs.size() < b.subs.size()) return -1;
537 [ + - + - ]: 321318 : if (b.subs.size() < a.subs.size()) return 1;
538 : 160659 : size_t n = a.subs.size();
539 [ + + ]: 318933 : for (size_t i = 0; i < n; ++i) {
540 [ + - + - ]: 316548 : queue.emplace_back(*a.subs[n - 1 - i], *b.subs[n - 1 - i]);
541 : 158274 : }
542 : : }
543 : 2385 : return 0;
544 : 2385 : }
545 : :
546 : : //! Compute the type for this miniscript.
547 : 1049513 : Type CalcType() const {
548 : : using namespace internal;
549 : :
550 : : // THRESH has a variable number of subexpressions
551 : 1049513 : std::vector<Type> sub_types;
552 [ + + + + ]: 1049513 : if (fragment == Fragment::THRESH) {
553 [ + + + - : 141004 : for (const auto& sub : subs) sub_types.push_back(sub->GetType());
+ + + - ]
554 : 24889 : }
555 : : // All other nodes than THRESH can be computed just from the types of the 0-3 subexpressions.
556 [ + + + - : 1049513 : Type x = subs.size() > 0 ? subs[0]->GetType() : ""_mst;
+ + + - ]
557 [ + + + - : 1049513 : Type y = subs.size() > 1 ? subs[1]->GetType() : ""_mst;
+ + + - ]
558 [ + + + - : 1049513 : Type z = subs.size() > 2 ? subs[2]->GetType() : ""_mst;
+ + + - ]
559 : :
560 [ + - + - : 1049513 : return SanitizeType(ComputeType(fragment, x, y, z, sub_types, k, data.size(), subs.size(), keys.size()));
+ - + - ]
561 : 1049513 : }
562 : :
563 : : public:
564 : : template<typename Ctx>
565 : 4243 : CScript ToScript(const Ctx& ctx) const
566 : : {
567 : : // To construct the CScript for a Miniscript object, we use the TreeEval algorithm.
568 : : // The State is a boolean: whether or not the node's script expansion is followed
569 : : // by an OP_VERIFY (which may need to be combined with the last script opcode).
570 : 303459 : auto downfn = [](bool verify, const Node& node, size_t index) {
571 : : // For WRAP_V, the subexpression is certainly followed by OP_VERIFY.
572 [ + + + + ]: 303459 : if (node.fragment == Fragment::WRAP_V) return true;
573 : : // The subexpression of WRAP_S, and the last subexpression of AND_V
574 : : // inherit the followed-by-OP_VERIFY property from the parent.
575 [ + + + + : 323701 : if (node.fragment == Fragment::WRAP_S ||
+ + + + ]
576 [ + + + + ]: 279765 : (node.fragment == Fragment::AND_V && index == 1)) return verify;
577 : 255479 : return false;
578 : 303459 : };
579 : : // The upward function computes for a node, given its followed-by-OP_VERIFY status
580 : : // and the CScripts of its child nodes, the CScript of the node.
581 : 311945 : auto upfn = [&ctx](bool verify, const Node& node, Span<CScript> subs) -> CScript {
582 [ + + + + : 307702 : switch (node.fragment) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + - + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + +
- ]
583 [ - + ]: 6911 : case Fragment::PK_K: return BuildScript(ctx.ToPKBytes(node.keys[0]));
584 [ + - - + ]: 3429 : case Fragment::PK_H: return BuildScript(OP_DUP, OP_HASH160, ctx.ToPKHBytes(node.keys[0]), OP_EQUALVERIFY);
585 : 2339 : case Fragment::OLDER: return BuildScript(node.k, OP_CHECKSEQUENCEVERIFY);
586 : 1789 : case Fragment::AFTER: return BuildScript(node.k, OP_CHECKLOCKTIMEVERIFY);
587 : 2208 : case Fragment::SHA256: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_SHA256, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL);
588 : 1711 : case Fragment::RIPEMD160: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_RIPEMD160, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL);
589 : 2248 : case Fragment::HASH256: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_HASH256, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL);
590 : 2443 : case Fragment::HASH160: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_HASH160, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL);
591 : 21209 : case Fragment::WRAP_A: return BuildScript(OP_TOALTSTACK, subs[0], OP_FROMALTSTACK);
592 : 2318 : case Fragment::WRAP_S: return BuildScript(OP_SWAP, subs[0]);
593 : 5594 : case Fragment::WRAP_C: return BuildScript(std::move(subs[0]), verify ? OP_CHECKSIGVERIFY : OP_CHECKSIG);
594 : 628 : case Fragment::WRAP_D: return BuildScript(OP_DUP, OP_IF, subs[0], OP_ENDIF);
595 : : case Fragment::WRAP_V: {
596 [ + + + + ]: 23694 : if (node.subs[0]->GetType() << "x"_mst) {
597 : 15242 : return BuildScript(std::move(subs[0]), OP_VERIFY);
598 : : } else {
599 : 8452 : return std::move(subs[0]);
600 : : }
601 : : }
602 : 3570 : case Fragment::WRAP_J: return BuildScript(OP_SIZE, OP_0NOTEQUAL, OP_IF, subs[0], OP_ENDIF);
603 : 81317 : case Fragment::WRAP_N: return BuildScript(std::move(subs[0]), OP_0NOTEQUAL);
604 : 10356 : case Fragment::JUST_1: return BuildScript(OP_1);
605 : 52545 : case Fragment::JUST_0: return BuildScript(OP_0);
606 : 21968 : case Fragment::AND_V: return BuildScript(std::move(subs[0]), subs[1]);
607 : 4507 : case Fragment::AND_B: return BuildScript(std::move(subs[0]), subs[1], OP_BOOLAND);
608 : 3483 : case Fragment::OR_B: return BuildScript(std::move(subs[0]), subs[1], OP_BOOLOR);
609 : 6084 : case Fragment::OR_D: return BuildScript(std::move(subs[0]), OP_IFDUP, OP_NOTIF, subs[1], OP_ENDIF);
610 : 3812 : case Fragment::OR_C: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[1], OP_ENDIF);
611 : 15903 : case Fragment::OR_I: return BuildScript(OP_IF, subs[0], OP_ELSE, subs[1], OP_ENDIF);
612 : 9865 : case Fragment::ANDOR: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[2], OP_ELSE, subs[1], OP_ENDIF);
613 : : case Fragment::MULTI: {
614 : 9182 : CScript script = BuildScript(node.k);
615 [ + + + + ]: 49525 : for (const auto& key : node.keys) {
616 [ + - + - : 40343 : script = BuildScript(std::move(script), ctx.ToPKBytes(key));
+ - + - ]
617 : : }
618 [ + - + - ]: 9182 : return BuildScript(std::move(script), node.keys.size(), verify ? OP_CHECKMULTISIGVERIFY : OP_CHECKMULTISIG);
619 : 9182 : }
620 : : case Fragment::THRESH: {
621 : 8589 : CScript script = std::move(subs[0]);
622 [ + + + + ]: 24020 : for (size_t i = 1; i < subs.size(); ++i) {
623 [ + - + - ]: 15431 : script = BuildScript(std::move(script), subs[i], OP_ADD);
624 : 15431 : }
625 [ + - + - ]: 8589 : return BuildScript(std::move(script), node.k, verify ? OP_EQUALVERIFY : OP_EQUAL);
626 : 8589 : }
627 : : }
628 : 0 : assert(false);
629 : 307702 : };
630 : 4243 : return TreeEval<CScript>(false, downfn, upfn);
631 : : }
632 : :
633 : : template<typename CTx>
634 : 3327 : std::optional<std::string> ToString(const CTx& ctx) const {
635 : : // To construct the std::string representation for a Miniscript object, we use
636 : : // the TreeEvalMaybe algorithm. The State is a boolean: whether the parent node is a
637 : : // wrapper. If so, non-wrapper expressions must be prefixed with a ":".
638 : 222252 : auto downfn = [](bool, const Node& node, size_t) {
639 [ + + + + : 413680 : return (node.fragment == Fragment::WRAP_A || node.fragment == Fragment::WRAP_S ||
+ - + - ]
640 [ + + + + : 204854 : node.fragment == Fragment::WRAP_D || node.fragment == Fragment::WRAP_V ||
+ - + + ]
641 [ + + + + : 187153 : node.fragment == Fragment::WRAP_J || node.fragment == Fragment::WRAP_N ||
+ + + + ]
642 [ + + + + ]: 163190 : node.fragment == Fragment::WRAP_C ||
643 [ + + + + : 159298 : (node.fragment == Fragment::AND_V && node.subs[1]->fragment == Fragment::JUST_1) ||
+ + + + ]
644 [ + + + + ]: 281530 : (node.fragment == Fragment::OR_I && node.subs[0]->fragment == Fragment::JUST_0) ||
645 [ + + + + ]: 140349 : (node.fragment == Fragment::OR_I && node.subs[1]->fragment == Fragment::JUST_0));
646 : : };
647 : : // The upward function computes for a node, given whether its parent is a wrapper,
648 : : // and the string representations of its child nodes, the string representation of the node.
649 : 227843 : auto upfn = [&ctx](bool wrapped, const Node& node, Span<std::string> subs) -> std::optional<std::string> {
650 [ + - + - ]: 224516 : std::string ret = wrapped ? ":" : "";
651 : :
652 [ + + + + : 224516 : switch (node.fragment) {
+ + + + +
+ - - + +
+ + - + +
+ ]
653 [ + - + - : 15255 : case Fragment::WRAP_A: return "a" + std::move(subs[0]);
# # # # ]
654 [ + - + - : 2143 : case Fragment::WRAP_S: return "s" + std::move(subs[0]);
# # # # ]
655 : : case Fragment::WRAP_C:
656 [ + + + + ]: 3850 : if (node.subs[0]->fragment == Fragment::PK_K) {
657 : : // pk(K) is syntactic sugar for c:pk_k(K)
658 [ + - + - ]: 1451 : auto key_str = ctx.ToString(node.subs[0]->keys[0]);
659 [ + - + - ]: 1451 : if (!key_str) return {};
660 [ + - + - : 1451 : return std::move(ret) + "pk(" + std::move(*key_str) + ")";
+ - + - +
- + - + -
+ - + - ]
661 : 1451 : }
662 [ + + + - ]: 2399 : if (node.subs[0]->fragment == Fragment::PK_H) {
663 : : // pkh(K) is syntactic sugar for c:pk_h(K)
664 [ + - + - ]: 1299 : auto key_str = ctx.ToString(node.subs[0]->keys[0]);
665 [ + - + - ]: 1299 : if (!key_str) return {};
666 [ + - + - : 1299 : return std::move(ret) + "pkh(" + std::move(*key_str) + ")";
+ - + - +
- + - + -
+ - + - ]
667 : 1299 : }
668 [ + - + - : 1100 : return "c" + std::move(subs[0]);
# # # # ]
669 [ + - + - : 1870 : case Fragment::WRAP_D: return "d" + std::move(subs[0]);
# # # # ]
670 [ + - + - : 15706 : case Fragment::WRAP_V: return "v" + std::move(subs[0]);
+ - + - ]
671 [ + - + - : 3460 : case Fragment::WRAP_J: return "j" + std::move(subs[0]);
+ - + - ]
672 [ + - + - : 20142 : case Fragment::WRAP_N: return "n" + std::move(subs[0]);
+ - + - ]
673 : : case Fragment::AND_V:
674 : : // t:X is syntactic sugar for and_v(X,1).
675 [ + + + - : 16024 : if (node.subs[1]->fragment == Fragment::JUST_1) return "t" + std::move(subs[0]);
+ - + + +
- + - ]
676 : 10141 : break;
677 : : case Fragment::OR_I:
678 [ + + + - : 23721 : if (node.subs[0]->fragment == Fragment::JUST_0) return "l" + std::move(subs[1]);
+ - + + +
- + - ]
679 [ + + + - : 14898 : if (node.subs[1]->fragment == Fragment::JUST_0) return "u" + std::move(subs[0]);
+ - + - +
- + - ]
680 : 4573 : break;
681 : 122345 : default: break;
682 : : }
683 [ + + + + : 137059 : switch (node.fragment) {
+ + + + +
+ + + + +
+ + + + +
- + + + +
+ - - - +
+ + - - -
+ - + + +
- ]
684 : : case Fragment::PK_K: {
685 [ + - + - ]: 4240 : auto key_str = ctx.ToString(node.keys[0]);
686 [ + - + + ]: 4240 : if (!key_str) return {};
687 [ + - + - : 4225 : return std::move(ret) + "pk_k(" + std::move(*key_str) + ")";
+ - + - +
- + - + -
+ - + - ]
688 : 4240 : }
689 : : case Fragment::PK_H: {
690 [ + - + - ]: 2610 : auto key_str = ctx.ToString(node.keys[0]);
691 [ + - + + ]: 2610 : if (!key_str) return {};
692 [ + - + - : 2583 : return std::move(ret) + "pk_h(" + std::move(*key_str) + ")";
+ - + - +
- + - + -
+ - + - ]
693 : 2610 : }
694 [ + - + - : 2104 : case Fragment::AFTER: return std::move(ret) + "after(" + ::ToString(node.k) + ")";
+ - + - +
- + - + -
+ - + - +
- ]
695 [ + - + - : 3369 : case Fragment::OLDER: return std::move(ret) + "older(" + ::ToString(node.k) + ")";
+ - + - +
- + - + -
+ - + - +
- ]
696 [ + - + - : 1261 : case Fragment::HASH256: return std::move(ret) + "hash256(" + HexStr(node.data) + ")";
+ - + - +
- + - + -
+ - + - +
- + - +
- ]
697 [ + - + - : 1492 : case Fragment::HASH160: return std::move(ret) + "hash160(" + HexStr(node.data) + ")";
+ - + - +
- + - # #
# # # # #
# # # #
# ]
698 [ + - + - : 1307 : case Fragment::SHA256: return std::move(ret) + "sha256(" + HexStr(node.data) + ")";
+ - + - +
- + - # #
# # # # #
# # # #
# ]
699 [ + - + - : 1002 : case Fragment::RIPEMD160: return std::move(ret) + "ripemd160(" + HexStr(node.data) + ")";
+ - + - +
- + - # #
# # # # #
# # # #
# ]
700 [ + - + - : 19724 : case Fragment::JUST_1: return std::move(ret) + "1";
+ - + - ]
701 [ + - + - : 56660 : case Fragment::JUST_0: return std::move(ret) + "0";
+ - + - ]
702 [ + - + - : 10141 : case Fragment::AND_V: return std::move(ret) + "and_v(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
+ - + - +
- + - + -
+ - + - +
- + - +
- ]
703 [ + - + - : 3411 : case Fragment::AND_B: return std::move(ret) + "and_b(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
+ - + - +
- + - # #
# # # # #
# # # #
# ]
704 [ + - + - : 1692 : case Fragment::OR_B: return std::move(ret) + "or_b(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
+ - + - +
- + - # #
# # # # #
# # # #
# ]
705 [ + - + - : 3254 : case Fragment::OR_D: return std::move(ret) + "or_d(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
+ - + - +
- + - # #
# # # # #
# # # #
# ]
706 [ + - + - : 2319 : case Fragment::OR_C: return std::move(ret) + "or_c(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
+ - + - +
- + - + -
+ - + - +
- + - +
- ]
707 [ + - + - : 4573 : case Fragment::OR_I: return std::move(ret) + "or_i(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
+ - + - +
- + - # #
# # # # #
# # # #
# ]
708 : : case Fragment::ANDOR:
709 : : // and_n(X,Y) is syntactic sugar for andor(X,Y,0).
710 [ + + + - : 6418 : if (node.subs[2]->fragment == Fragment::JUST_0) return std::move(ret) + "and_n(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
+ - + - +
- + - - +
- + # # #
# # # # #
# # # # ]
711 [ + - + - : 3417 : return std::move(ret) + "andor(" + std::move(subs[0]) + "," + std::move(subs[1]) + "," + std::move(subs[2]) + ")";
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - ]
712 : : case Fragment::MULTI: {
713 [ + - + - : 5445 : auto str = std::move(ret) + "multi(" + ::ToString(node.k);
+ - + - +
- + - ]
714 [ + + + + ]: 29456 : for (const auto& key : node.keys) {
715 [ + - + - ]: 24054 : auto key_str = ctx.ToString(key);
716 [ + - + + ]: 24054 : if (!key_str) return {};
717 [ + - + - : 24011 : str += "," + std::move(*key_str);
+ - + - +
- ]
718 [ - + + + ]: 24054 : }
719 [ + - + - : 5402 : return std::move(str) + ")";
+ - + - ]
720 : 5445 : }
721 : : case Fragment::THRESH: {
722 [ + - + - : 6037 : auto str = std::move(ret) + "thresh(" + ::ToString(node.k);
+ - + - +
- + - ]
723 [ + + + + ]: 44406 : for (auto& sub : subs) {
724 [ + - + - : 38369 : str += "," + std::move(sub);
+ - + - ]
725 : : }
726 [ + - + - : 6037 : return std::move(str) + ")";
+ - + - ]
727 : 6037 : }
728 : 0 : default: break;
729 : : }
730 : 0 : assert(false);
731 : 224516 : };
732 : :
733 : 3327 : return TreeEvalMaybe<std::string>(false, downfn, upfn);
734 : : }
735 : :
736 : : private:
737 : 1049513 : internal::Ops CalcOps() const {
738 [ + + + + : 1049513 : switch (fragment) {
+ + + + +
+ + + + +
+ + + + +
+ - + + +
+ + + + +
+ + + + +
+ + + + +
+ + - ]
739 : 78493 : case Fragment::JUST_1: return {0, 0, {}};
740 : 228611 : case Fragment::JUST_0: return {0, {}, 0};
741 : 12695 : case Fragment::PK_K: return {0, 0, 0};
742 : 7069 : case Fragment::PK_H: return {3, 0, 0};
743 : : case Fragment::OLDER:
744 : 29499 : case Fragment::AFTER: return {1, 0, {}};
745 : : case Fragment::SHA256:
746 : : case Fragment::RIPEMD160:
747 : : case Fragment::HASH256:
748 : 15099 : case Fragment::HASH160: return {4, 0, {}};
749 : 54324 : case Fragment::AND_V: return {subs[0]->ops.count + subs[1]->ops.count, subs[0]->ops.sat + subs[1]->ops.sat, {}};
750 : : case Fragment::AND_B: {
751 : 16461 : const auto count{1 + subs[0]->ops.count + subs[1]->ops.count};
752 : 16461 : const auto sat{subs[0]->ops.sat + subs[1]->ops.sat};
753 : 16461 : const auto dsat{subs[0]->ops.dsat + subs[1]->ops.dsat};
754 : 16461 : return {count, sat, dsat};
755 : : }
756 : : case Fragment::OR_B: {
757 : 10929 : const auto count{1 + subs[0]->ops.count + subs[1]->ops.count};
758 : 10929 : const auto sat{(subs[0]->ops.sat + subs[1]->ops.dsat) | (subs[1]->ops.sat + subs[0]->ops.dsat)};
759 : 10929 : const auto dsat{subs[0]->ops.dsat + subs[1]->ops.dsat};
760 : 10929 : return {count, sat, dsat};
761 : : }
762 : : case Fragment::OR_D: {
763 : 12568 : const auto count{3 + subs[0]->ops.count + subs[1]->ops.count};
764 : 12568 : const auto sat{subs[0]->ops.sat | (subs[1]->ops.sat + subs[0]->ops.dsat)};
765 : 12568 : const auto dsat{subs[0]->ops.dsat + subs[1]->ops.dsat};
766 : 12568 : return {count, sat, dsat};
767 : : }
768 : : case Fragment::OR_C: {
769 : 10054 : const auto count{2 + subs[0]->ops.count + subs[1]->ops.count};
770 : 10054 : const auto sat{subs[0]->ops.sat | (subs[1]->ops.sat + subs[0]->ops.dsat)};
771 : 10054 : return {count, sat, {}};
772 : : }
773 : : case Fragment::OR_I: {
774 : 85058 : const auto count{3 + subs[0]->ops.count + subs[1]->ops.count};
775 : 85058 : const auto sat{subs[0]->ops.sat | subs[1]->ops.sat};
776 : 85058 : const auto dsat{subs[0]->ops.dsat | subs[1]->ops.dsat};
777 : 85058 : return {count, sat, dsat};
778 : : }
779 : : case Fragment::ANDOR: {
780 : 22878 : const auto count{3 + subs[0]->ops.count + subs[1]->ops.count + subs[2]->ops.count};
781 : 22878 : const auto sat{(subs[1]->ops.sat + subs[0]->ops.sat) | (subs[0]->ops.dsat + subs[2]->ops.sat)};
782 : 22878 : const auto dsat{subs[0]->ops.dsat + subs[2]->ops.dsat};
783 : 22878 : return {count, sat, dsat};
784 : : }
785 : 16213 : case Fragment::MULTI: return {1, (uint32_t)keys.size(), (uint32_t)keys.size()};
786 : : case Fragment::WRAP_S:
787 : : case Fragment::WRAP_C:
788 : 283203 : case Fragment::WRAP_N: return {1 + subs[0]->ops.count, subs[0]->ops.sat, subs[0]->ops.dsat};
789 : 61120 : case Fragment::WRAP_A: return {2 + subs[0]->ops.count, subs[0]->ops.sat, subs[0]->ops.dsat};
790 : 15520 : case Fragment::WRAP_D: return {3 + subs[0]->ops.count, subs[0]->ops.sat, 0};
791 : 9801 : case Fragment::WRAP_J: return {4 + subs[0]->ops.count, subs[0]->ops.sat, 0};
792 : 55029 : case Fragment::WRAP_V: return {subs[0]->ops.count + (subs[0]->GetType() << "x"_mst), subs[0]->ops.sat, {}};
793 : : case Fragment::THRESH: {
794 : 24889 : uint32_t count = 0;
795 : 24889 : auto sats = Vector(internal::MaxInt<uint32_t>(0));
796 [ + + + + ]: 141004 : for (const auto& sub : subs) {
797 : 116115 : count += sub->ops.count + 1;
798 [ + - + - : 116115 : auto next_sats = Vector(sats[0] + sub->ops.dsat);
+ - + - ]
799 [ + + + - : 4895977 : for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub->ops.dsat) | (sats[j - 1] + sub->ops.sat));
+ - + - +
- + + + -
+ - + - +
- ]
800 [ + - + - : 116115 : next_sats.push_back(sats[sats.size() - 1] + sub->ops.sat);
+ - + - ]
801 : 116115 : sats = std::move(next_sats);
802 : 116115 : }
803 [ - + - + ]: 24889 : assert(k <= sats.size());
804 [ + - + - ]: 24889 : return {count, sats[k], sats[0]};
805 : 24889 : }
806 : : }
807 : 0 : assert(false);
808 : 1049513 : }
809 : :
810 : 1049513 : internal::StackSize CalcStackSize() const {
811 [ + + + + : 1049513 : switch (fragment) {
+ + + + +
+ + + + +
+ + + + -
+ + + + +
+ + + + +
+ + + + +
+ + + - ]
812 : 228611 : case Fragment::JUST_0: return {{}, 0};
813 : : case Fragment::JUST_1:
814 : : case Fragment::OLDER:
815 : 107992 : case Fragment::AFTER: return {0, {}};
816 : 12695 : case Fragment::PK_K: return {1, 1};
817 : 7069 : case Fragment::PK_H: return {2, 2};
818 : : case Fragment::SHA256:
819 : : case Fragment::RIPEMD160:
820 : : case Fragment::HASH256:
821 : 15099 : case Fragment::HASH160: return {1, {}};
822 : : case Fragment::ANDOR: {
823 : 22878 : const auto sat{(subs[0]->ss.sat + subs[1]->ss.sat) | (subs[0]->ss.dsat + subs[2]->ss.sat)};
824 : 22878 : const auto dsat{subs[0]->ss.dsat + subs[2]->ss.dsat};
825 : 22878 : return {sat, dsat};
826 : : }
827 : 54324 : case Fragment::AND_V: return {subs[0]->ss.sat + subs[1]->ss.sat, {}};
828 : 16461 : case Fragment::AND_B: return {subs[0]->ss.sat + subs[1]->ss.sat, subs[0]->ss.dsat + subs[1]->ss.dsat};
829 : : case Fragment::OR_B: {
830 : 10929 : const auto sat{(subs[0]->ss.dsat + subs[1]->ss.sat) | (subs[0]->ss.sat + subs[1]->ss.dsat)};
831 : 10929 : const auto dsat{subs[0]->ss.dsat + subs[1]->ss.dsat};
832 : 10929 : return {sat, dsat};
833 : : }
834 : 10054 : case Fragment::OR_C: return {subs[0]->ss.sat | (subs[0]->ss.dsat + subs[1]->ss.sat), {}};
835 : 12568 : case Fragment::OR_D: return {subs[0]->ss.sat | (subs[0]->ss.dsat + subs[1]->ss.sat), subs[0]->ss.dsat + subs[1]->ss.dsat};
836 : 85058 : case Fragment::OR_I: return {(subs[0]->ss.sat + 1) | (subs[1]->ss.sat + 1), (subs[0]->ss.dsat + 1) | (subs[1]->ss.dsat + 1)};
837 : 16213 : case Fragment::MULTI: return {k + 1, k + 1};
838 : : case Fragment::WRAP_A:
839 : : case Fragment::WRAP_N:
840 : : case Fragment::WRAP_S:
841 : 344323 : case Fragment::WRAP_C: return subs[0]->ss;
842 : 15520 : case Fragment::WRAP_D: return {1 + subs[0]->ss.sat, 1};
843 : 55029 : case Fragment::WRAP_V: return {subs[0]->ss.sat, {}};
844 : 9801 : case Fragment::WRAP_J: return {subs[0]->ss.sat, 1};
845 : : case Fragment::THRESH: {
846 : 24889 : auto sats = Vector(internal::MaxInt<uint32_t>(0));
847 [ + + + + ]: 141004 : for (const auto& sub : subs) {
848 [ + - + - : 116115 : auto next_sats = Vector(sats[0] + sub->ss.dsat);
+ - + - ]
849 [ + + + - : 4895977 : for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub->ss.dsat) | (sats[j - 1] + sub->ss.sat));
+ - + - +
- + + + -
+ - + - +
- ]
850 [ + - + - : 116115 : next_sats.push_back(sats[sats.size() - 1] + sub->ss.sat);
+ - + - ]
851 : 116115 : sats = std::move(next_sats);
852 : 116115 : }
853 [ - + - + ]: 24889 : assert(k <= sats.size());
854 [ + - + - ]: 24889 : return {sats[k], sats[0]};
855 : 24889 : }
856 : : }
857 : 0 : assert(false);
858 : 1049513 : }
859 : :
860 : 1049513 : internal::WitnessSize CalcWitnessSize() const {
861 [ + + + + : 1049513 : switch (fragment) {
+ + + + +
+ + + + +
+ + + + -
+ + + + +
+ + + + +
+ + + + +
+ + + - ]
862 : 228611 : case Fragment::JUST_0: return {{}, 0};
863 : : case Fragment::JUST_1:
864 : : case Fragment::OLDER:
865 : 107992 : case Fragment::AFTER: return {0, {}};
866 : 12695 : case Fragment::PK_K: return {1 + 72, 1};
867 : 7069 : case Fragment::PK_H: return {1 + 72 + 1 + 33, 1 + 1 + 33};
868 : : case Fragment::SHA256:
869 : : case Fragment::RIPEMD160:
870 : : case Fragment::HASH256:
871 : 15099 : case Fragment::HASH160: return {1 + 32, {}};
872 : : case Fragment::ANDOR: {
873 : 22878 : const auto sat{(subs[0]->ws.sat + subs[1]->ws.sat) | (subs[0]->ws.dsat + subs[2]->ws.sat)};
874 : 22878 : const auto dsat{subs[0]->ws.dsat + subs[2]->ws.dsat};
875 : 22878 : return {sat, dsat};
876 : : }
877 : 54324 : case Fragment::AND_V: return {subs[0]->ws.sat + subs[1]->ws.sat, {}};
878 : 16461 : case Fragment::AND_B: return {subs[0]->ws.sat + subs[1]->ws.sat, subs[0]->ws.dsat + subs[1]->ws.dsat};
879 : : case Fragment::OR_B: {
880 : 10929 : const auto sat{(subs[0]->ws.dsat + subs[1]->ws.sat) | (subs[0]->ws.sat + subs[1]->ws.dsat)};
881 : 10929 : const auto dsat{subs[0]->ws.dsat + subs[1]->ws.dsat};
882 : 10929 : return {sat, dsat};
883 : : }
884 : 10054 : case Fragment::OR_C: return {subs[0]->ws.sat | (subs[0]->ws.dsat + subs[1]->ws.sat), {}};
885 : 12568 : 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};
886 : 85058 : 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)};
887 : 16213 : case Fragment::MULTI: return {k * (1 + 72) + 1, k + 1};
888 : : case Fragment::WRAP_A:
889 : : case Fragment::WRAP_N:
890 : : case Fragment::WRAP_S:
891 : 344323 : case Fragment::WRAP_C: return subs[0]->ws;
892 : 15520 : case Fragment::WRAP_D: return {1 + 1 + subs[0]->ws.sat, 1};
893 : 55029 : case Fragment::WRAP_V: return {subs[0]->ws.sat, {}};
894 : 9801 : case Fragment::WRAP_J: return {subs[0]->ws.sat, 1};
895 : : case Fragment::THRESH: {
896 : 24889 : auto sats = Vector(internal::MaxInt<uint32_t>(0));
897 [ + + + + ]: 141004 : for (const auto& sub : subs) {
898 [ + - + - : 116115 : auto next_sats = Vector(sats[0] + sub->ws.dsat);
+ - + - ]
899 [ + + + - : 4895977 : for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub->ws.dsat) | (sats[j - 1] + sub->ws.sat));
+ - + - +
- + + + -
+ - + - +
- ]
900 [ + - + - : 116115 : next_sats.push_back(sats[sats.size() - 1] + sub->ws.sat);
+ - + - ]
901 : 116115 : sats = std::move(next_sats);
902 : 116115 : }
903 [ - + - + ]: 24889 : assert(k <= sats.size());
904 [ + - + - ]: 24889 : return {sats[k], sats[0]};
905 : 24889 : }
906 : : }
907 : 0 : assert(false);
908 : 1049513 : }
909 : :
910 : : template<typename Ctx>
911 : 3268 : internal::InputResult ProduceInput(const Ctx& ctx) const {
912 : : using namespace internal;
913 : :
914 : : // Internal function which is invoked for every tree node, constructing satisfaction/dissatisfactions
915 : : // given those of its subnodes.
916 : 179874 : auto helper = [&ctx](const Node& node, Span<InputResult> subres) -> InputResult {
917 [ + + + + : 176606 : switch (node.fragment) {
+ + + + +
+ + + + +
+ + + + +
+ + + +
- ]
918 : : case Fragment::PK_K: {
919 : 6116 : std::vector<unsigned char> sig;
920 [ + - ]: 6116 : Availability avail = ctx.Sign(node.keys[0], sig);
921 [ + - + - : 6116 : return {ZERO, InputStack(std::move(sig)).SetWithSig().SetAvailable(avail)};
+ - + - ]
922 : 6116 : }
923 : : case Fragment::PK_H: {
924 : 2922 : std::vector<unsigned char> key = ctx.ToPKBytes(node.keys[0]), sig;
925 [ + - ]: 2922 : Availability avail = ctx.Sign(node.keys[0], sig);
926 [ + - + - : 2922 : return {ZERO + InputStack(key), (InputStack(std::move(sig)).SetWithSig() + InputStack(key)).SetAvailable(avail)};
+ - + - +
- + - + -
+ - + - +
- + - +
- ]
927 : 2922 : }
928 : : case Fragment::MULTI: {
929 : : // sats[j] represents the best stack containing j valid signatures (out of the first i keys).
930 : : // In the loop below, these stacks are built up using a dynamic programming approach.
931 : : // sats[0] starts off being {0}, due to the CHECKMULTISIG bug that pops off one element too many.
932 : 8746 : std::vector<InputStack> sats = Vector(ZERO);
933 [ + + ]: 46580 : for (size_t i = 0; i < node.keys.size(); ++i) {
934 : 37834 : std::vector<unsigned char> sig;
935 [ + - ]: 37834 : Availability avail = ctx.Sign(node.keys[i], sig);
936 : : // Compute signature stack for just the i'th key.
937 [ + - + - : 37834 : auto sat = InputStack(std::move(sig)).SetWithSig().SetAvailable(avail);
+ - + - ]
938 : : // Compute the next sats vector: next_sats[0] is a copy of sats[0] (no signatures). All further
939 : : // next_sats[j] are equal to either the existing sats[j], or sats[j-1] plus a signature for the
940 : : // current (i'th) key. The very last element needs all signatures filled.
941 : 37834 : std::vector<InputStack> next_sats;
942 [ + - ]: 37834 : next_sats.push_back(sats[0]);
943 [ + + + - : 236126 : for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back(sats[j] | (std::move(sats[j - 1]) + sat));
+ - + - +
- + - ]
944 [ + - + - ]: 37834 : next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(sat));
945 : : // Switch over.
946 : 37834 : sats = std::move(next_sats);
947 : 37834 : }
948 : : // The dissatisfaction consists of k+1 stack elements all equal to 0.
949 [ + - ]: 8746 : InputStack nsat = ZERO;
950 [ + + + - : 38438 : for (size_t i = 0; i < node.k; ++i) nsat = std::move(nsat) + ZERO;
+ - ]
951 [ + - ]: 8746 : assert(node.k <= sats.size());
952 [ + - ]: 8746 : return {std::move(nsat), std::move(sats[node.k])};
953 : 8746 : }
954 : : case Fragment::THRESH: {
955 : : // sats[k] represents the best stack that satisfies k out of the *last* i subexpressions.
956 : : // In the loop below, these stacks are built up using a dynamic programming approach.
957 : : // sats[0] starts off empty.
958 : 6222 : std::vector<InputStack> sats = Vector(EMPTY);
959 [ + + ]: 25476 : for (size_t i = 0; i < subres.size(); ++i) {
960 : : // Introduce an alias for the i'th last satisfaction/dissatisfaction.
961 : 19254 : auto& res = subres[subres.size() - i - 1];
962 : : // Compute the next sats vector: next_sats[0] is sats[0] plus res.nsat (thus containing all dissatisfactions
963 : : // so far. next_sats[j] is either sats[j] + res.nsat (reusing j earlier satisfactions) or sats[j-1] + res.sat
964 : : // (reusing j-1 earlier satisfactions plus a new one). The very last next_sats[j] is all satisfactions.
965 : 19254 : std::vector<InputStack> next_sats;
966 [ + - + - : 19254 : next_sats.push_back(sats[0] + res.nsat);
+ - + - ]
967 [ + + + - : 269100 : for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + res.nsat) | (std::move(sats[j - 1]) + res.sat));
+ - + - +
- + - + -
+ - ]
968 [ + - + - ]: 19254 : next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(res.sat));
969 : : // Switch over.
970 : 19254 : sats = std::move(next_sats);
971 : 19254 : }
972 : : // At this point, sats[k].sat is the best satisfaction for the overall thresh() node. The best dissatisfaction
973 : : // is computed by gathering all sats[i].nsat for i != k.
974 [ + - ]: 6222 : InputStack nsat = INVALID;
975 [ + + ]: 31698 : for (size_t i = 0; i < sats.size(); ++i) {
976 : : // i==k is the satisfaction; i==0 is the canonical dissatisfaction;
977 : : // the rest are non-canonical (a no-signature dissatisfaction - the i=0
978 : : // form - is always available) and malleable (due to overcompleteness).
979 : : // Marking the solutions malleable here is not strictly necessary, as they
980 : : // should already never be picked in non-malleable solutions due to the
981 : : // availability of the i=0 form.
982 [ + + + + : 25476 : if (i != 0 && i != node.k) sats[i].SetMalleable().SetNonCanon();
+ - + - ]
983 : : // Include all dissatisfactions (even these non-canonical ones) in nsat.
984 [ + + - + ]: 25476 : if (i != node.k) nsat = std::move(nsat) | std::move(sats[i]);
985 : 25476 : }
986 [ - + ]: 6222 : assert(node.k <= sats.size());
987 [ + - ]: 6222 : return {std::move(nsat), std::move(sats[node.k])};
988 : 6222 : }
989 : : case Fragment::OLDER: {
990 [ + + ]: 1688 : return {INVALID, ctx.CheckOlder(node.k) ? EMPTY : INVALID};
991 : : }
992 : : case Fragment::AFTER: {
993 [ + + ]: 1468 : return {INVALID, ctx.CheckAfter(node.k) ? EMPTY : INVALID};
994 : : }
995 : : case Fragment::SHA256: {
996 : 1994 : std::vector<unsigned char> preimage;
997 [ + - ]: 1994 : Availability avail = ctx.SatSHA256(node.data, preimage);
998 [ + - + - : 1994 : return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)};
+ - ]
999 : 1994 : }
1000 : : case Fragment::RIPEMD160: {
1001 : 1618 : std::vector<unsigned char> preimage;
1002 [ + - ]: 1618 : Availability avail = ctx.SatRIPEMD160(node.data, preimage);
1003 [ + - + - : 1618 : return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)};
+ - ]
1004 : 1618 : }
1005 : : case Fragment::HASH256: {
1006 : 2150 : std::vector<unsigned char> preimage;
1007 [ + - ]: 2150 : Availability avail = ctx.SatHASH256(node.data, preimage);
1008 [ + - + - : 2150 : return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)};
+ - ]
1009 : 2150 : }
1010 : : case Fragment::HASH160: {
1011 : 2304 : std::vector<unsigned char> preimage;
1012 [ + - ]: 2304 : Availability avail = ctx.SatHASH160(node.data, preimage);
1013 [ + - + - : 2304 : return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)};
+ - ]
1014 : 2304 : }
1015 : : case Fragment::AND_V: {
1016 : 15266 : auto& x = subres[0], &y = subres[1];
1017 : : // As the dissatisfaction here only consist of a single option, it doesn't
1018 : : // actually need to be listed (it's not required for reasoning about malleability of
1019 : : // other options), and is never required (no valid miniscript relies on the ability
1020 : : // to satisfy the type V left subexpression). It's still listed here for
1021 : : // completeness, as a hypothetical (not currently implemented) satisfier that doesn't
1022 : : // care about malleability might in some cases prefer it still.
1023 [ + - + - : 15266 : return {(y.nsat + x.sat).SetNonCanon(), y.sat + x.sat};
+ - + - +
- + - +
- ]
1024 : : }
1025 : : case Fragment::AND_B: {
1026 : 3492 : auto& x = subres[0], &y = subres[1];
1027 : : // Note that it is not strictly necessary to mark the 2nd and 3rd dissatisfaction here
1028 : : // as malleable. While they are definitely malleable, they are also non-canonical due
1029 : : // to the guaranteed existence of a no-signature other dissatisfaction (the 1st)
1030 : : // option. Because of that, the 2nd and 3rd option will never be chosen, even if they
1031 : : // weren't marked as malleable.
1032 [ + - + - : 3492 : return {(y.nsat + x.nsat) | (y.sat + x.nsat).SetMalleable().SetNonCanon() | (y.nsat + x.sat).SetMalleable().SetNonCanon(), y.sat + x.sat};
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- ]
1033 : : }
1034 : : case Fragment::OR_B: {
1035 : 2644 : auto& x = subres[0], &z = subres[1];
1036 : : // The (sat(Z) sat(X)) solution is overcomplete (attacker can change either into dsat).
1037 [ + - + - : 2644 : return {z.nsat + x.nsat, (z.nsat + x.sat) | (z.sat + x.nsat) | (z.sat + x.sat).SetMalleable().SetNonCanon()};
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - +
- ]
1038 : : }
1039 : : case Fragment::OR_C: {
1040 : 2840 : auto& x = subres[0], &z = subres[1];
1041 [ + - + - : 2840 : return {INVALID, std::move(x.sat) | (z.sat + x.nsat)};
+ - + - +
- ]
1042 : : }
1043 : : case Fragment::OR_D: {
1044 : 5008 : auto& x = subres[0], &z = subres[1];
1045 [ + - + - : 5008 : return {z.nsat + x.nsat, std::move(x.sat) | (z.sat + x.nsat)};
+ - + - +
- + - +
- ]
1046 : : }
1047 : : case Fragment::OR_I: {
1048 : 10414 : auto& x = subres[0], &z = subres[1];
1049 [ + - + - : 10414 : return {(x.nsat + ONE) | (z.nsat + ZERO), (x.sat + ONE) | (z.sat + ZERO)};
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - ]
1050 : : }
1051 : : case Fragment::ANDOR: {
1052 : 8280 : auto& x = subres[0], &y = subres[1], &z = subres[2];
1053 [ + - + - : 8280 : return {(y.nsat + x.sat).SetNonCanon() | (z.nsat + x.nsat), (y.sat + x.sat) | (z.sat + x.nsat)};
+ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - ]
1054 : : }
1055 : : case Fragment::WRAP_A:
1056 : : case Fragment::WRAP_S:
1057 : : case Fragment::WRAP_C:
1058 : : case Fragment::WRAP_N:
1059 : 29868 : return std::move(subres[0]);
1060 : : case Fragment::WRAP_D: {
1061 : 494 : auto &x = subres[0];
1062 [ + - + - : 494 : return {ZERO, x.sat + ONE};
+ - ]
1063 : : }
1064 : : case Fragment::WRAP_J: {
1065 : 3046 : auto &x = subres[0];
1066 : : // If a dissatisfaction with a nonzero top stack element exists, an alternative dissatisfaction exists.
1067 : : // As the dissatisfaction logic currently doesn't keep track of this nonzeroness property, and thus even
1068 : : // if a dissatisfaction with a top zero element is found, we don't know whether another one with a
1069 : : // nonzero top stack element exists. Make the conservative assumption that whenever the subexpression is weakly
1070 : : // dissatisfiable, this alternative dissatisfaction exists and leads to malleability.
1071 [ + + + - : 3046 : return {InputStack(ZERO).SetMalleable(x.nsat.available != Availability::NO && !x.nsat.has_sig), std::move(x.sat)};
+ - ]
1072 : : }
1073 : : case Fragment::WRAP_V: {
1074 : 16508 : auto &x = subres[0];
1075 : 16508 : return {INVALID, std::move(x.sat)};
1076 : : }
1077 : 36088 : case Fragment::JUST_0: return {EMPTY, INVALID};
1078 : 7430 : case Fragment::JUST_1: return {INVALID, EMPTY};
1079 : : }
1080 : 0 : assert(false);
1081 : : return {INVALID, INVALID};
1082 : 176606 : };
1083 : :
1084 : 179874 : auto tester = [&helper](const Node& node, Span<InputResult> subres) -> InputResult {
1085 : 176606 : auto ret = helper(node, subres);
1086 : :
1087 : : // Do a consistency check between the satisfaction code and the type checker
1088 : : // (the actual satisfaction code in ProduceInputHelper does not use GetType)
1089 : :
1090 : : // For 'z' nodes, available satisfactions/dissatisfactions must have stack size 0.
1091 [ + - + + : 176606 : if (node.GetType() << "z"_mst && ret.nsat.available != Availability::NO) assert(ret.nsat.stack.size() == 0);
+ + + - ]
1092 [ + - + + : 176606 : if (node.GetType() << "z"_mst && ret.sat.available != Availability::NO) assert(ret.sat.stack.size() == 0);
+ + + - ]
1093 : :
1094 : : // For 'o' nodes, available satisfactions/dissatisfactions must have stack size 1.
1095 [ + - + + : 176606 : if (node.GetType() << "o"_mst && ret.nsat.available != Availability::NO) assert(ret.nsat.stack.size() == 1);
+ + + - ]
1096 [ + - + + : 176606 : if (node.GetType() << "o"_mst && ret.sat.available != Availability::NO) assert(ret.sat.stack.size() == 1);
+ + + - ]
1097 : :
1098 : : // For 'n' nodes, available satisfactions/dissatisfactions must have stack size 1 or larger. For satisfactions,
1099 : : // the top element cannot be 0.
1100 [ + - + + : 176606 : if (node.GetType() << "n"_mst && ret.sat.available != Availability::NO) assert(ret.sat.stack.size() >= 1);
+ + + - ]
1101 [ + - + + : 176606 : if (node.GetType() << "n"_mst && ret.nsat.available != Availability::NO) assert(ret.nsat.stack.size() >= 1);
+ + + - ]
1102 [ + - + + : 176606 : if (node.GetType() << "n"_mst && ret.sat.available != Availability::NO) assert(!ret.sat.stack.back().empty());
+ + + - ]
1103 : :
1104 : : // For 'd' nodes, a dissatisfaction must exist, and they must not need a signature. If it is non-malleable,
1105 : : // it must be canonical.
1106 [ + - + + : 176606 : if (node.GetType() << "d"_mst) assert(ret.nsat.available != Availability::NO);
+ - ]
1107 [ + - + + : 176606 : if (node.GetType() << "d"_mst) assert(!ret.nsat.has_sig);
+ - ]
1108 [ + - + + : 176606 : if (node.GetType() << "d"_mst && !ret.nsat.malleable) assert(!ret.nsat.non_canon);
+ + + - ]
1109 : :
1110 : : // For 'f'/'s' nodes, dissatisfactions/satisfactions must have a signature.
1111 [ + - + + : 176606 : if (node.GetType() << "f"_mst && ret.nsat.available != Availability::NO) assert(ret.nsat.has_sig);
+ + + - ]
1112 [ + - + + : 176606 : if (node.GetType() << "s"_mst && ret.sat.available != Availability::NO) assert(ret.sat.has_sig);
+ + + - ]
1113 : :
1114 : : // For non-malleable 'e' nodes, a non-malleable dissatisfaction must exist.
1115 [ + - + + : 176606 : if (node.GetType() << "me"_mst) assert(ret.nsat.available != Availability::NO);
+ - ]
1116 [ + - + + : 176606 : if (node.GetType() << "me"_mst) assert(!ret.nsat.malleable);
+ - ]
1117 : :
1118 : : // For 'm' nodes, if a satisfaction exists, it must be non-malleable.
1119 [ + - + + : 176606 : if (node.GetType() << "m"_mst && ret.sat.available != Availability::NO) assert(!ret.sat.malleable);
+ + + - ]
1120 : :
1121 : : // If a non-malleable satisfaction exists, it must be canonical.
1122 [ + + + + : 176606 : if (ret.sat.available != Availability::NO && !ret.sat.malleable) assert(!ret.sat.non_canon);
- + ]
1123 : :
1124 : 176606 : return ret;
1125 [ + - ]: 176606 : };
1126 : :
1127 : 3268 : return TreeEval<InputResult>(tester);
1128 : : }
1129 : :
1130 : : public:
1131 : : /** Update duplicate key information in this Node.
1132 : : *
1133 : : * This uses a custom key comparator provided by the context in order to still detect duplicates
1134 : : * for more complicated types.
1135 : : */
1136 : 14456 : template<typename Ctx> void DuplicateKeyCheck(const Ctx& ctx) const
1137 : : {
1138 : : // We cannot use a lambda here, as lambdas are non assignable, and the set operations
1139 : : // below require moving the comparators around.
1140 : : struct Comp {
1141 : : const Ctx* ctx_ptr;
1142 : 674873 : Comp(const Ctx& ctx) : ctx_ptr(&ctx) {}
1143 : 238229 : bool operator()(const Key& a, const Key& b) const { return ctx_ptr->KeyCompare(a, b); }
1144 : : };
1145 : :
1146 : : // state in the recursive computation:
1147 : : // - std::nullopt means "this node has duplicates"
1148 : : // - an std::set means "this node has no duplicate keys, and they are: ...".
1149 : : using keyset = std::set<Key, Comp>;
1150 : : using state = std::optional<keyset>;
1151 : :
1152 : 731061 : auto upfn = [&ctx](const Node& node, Span<state> subs) -> state {
1153 : : // If this node is already known to have duplicates, nothing left to do.
1154 [ + + + - : 716605 : if (node.has_duplicate_keys.has_value() && *node.has_duplicate_keys) return {};
- + # # -
+ # # ]
1155 : :
1156 : : // Check if one of the children is already known to have duplicates.
1157 [ + + + + : 1345603 : for (auto& sub : subs) {
+ + ]
1158 [ + + + + : 670730 : if (!sub.has_value()) {
+ + ]
1159 : 41732 : node.has_duplicate_keys = true;
1160 : 41732 : return {};
1161 : : }
1162 : : }
1163 : :
1164 : : // Start building the set of keys involved in this node and children.
1165 : : // Start by keys in this node directly.
1166 : 674873 : size_t keys_count = node.keys.size();
1167 [ + - + - : 674873 : keyset key_set{node.keys.begin(), node.keys.end(), Comp(ctx)};
+ - ]
1168 [ + + + + : 674873 : if (key_set.size() != keys_count) {
+ + ]
1169 : : // It already has duplicates; bail out.
1170 [ + - + - : 5233 : node.has_duplicate_keys = true;
+ - ]
1171 : 5233 : return {};
1172 : : }
1173 : :
1174 : : // Merge the keys from the children into this set.
1175 [ + + + + : 1275270 : for (auto& sub : subs) {
+ + ]
1176 [ + - + - : 608012 : keys_count += sub->size();
+ - ]
1177 : : // Small optimization: std::set::merge is linear in the size of the second arg but
1178 : : // logarithmic in the size of the first.
1179 [ + - + + : 608012 : if (key_set.size() < sub->size()) std::swap(key_set, *sub);
+ - + - +
+ + - + -
+ + + - ]
1180 [ + - + - : 608012 : key_set.merge(*sub);
+ - + - +
- + - ]
1181 [ + + + + : 608012 : if (key_set.size() != keys_count) {
+ + ]
1182 [ + - + - : 2382 : node.has_duplicate_keys = true;
+ - ]
1183 : 2382 : return {};
1184 : : }
1185 : : }
1186 : :
1187 [ + - + - : 667258 : node.has_duplicate_keys = false;
+ - ]
1188 [ + - + - : 667258 : return key_set;
+ - ]
1189 : 716605 : };
1190 : :
1191 : 14456 : TreeEval<state>(upfn);
1192 : 14456 : }
1193 : :
1194 : : //! Return the size of the script for this expression (faster than ToScript().size()).
1195 : 1938477 : size_t ScriptSize() const { return scriptlen; }
1196 : :
1197 : : //! Return the maximum number of ops needed to satisfy this script non-malleably.
1198 : 93095 : std::optional<uint32_t> GetOps() const {
1199 [ + + ]: 93095 : if (!ops.sat.valid) return {};
1200 : 39968 : return ops.count + ops.sat.value;
1201 : 93095 : }
1202 : :
1203 : : //! Return the number of ops in the script (not counting the dynamic ones that depend on execution).
1204 : 1954 : uint32_t GetStaticOps() const { return ops.count; }
1205 : :
1206 : : //! Check the ops limit of this script against the consensus limit.
1207 : 91461 : bool CheckOpsLimit() const {
1208 [ + + ]: 91461 : if (const auto ops = GetOps()) return *ops <= MAX_OPS_PER_SCRIPT;
1209 : 52505 : return true;
1210 : 91461 : }
1211 : :
1212 : : /** Return the maximum number of stack elements needed to satisfy this script non-malleably.
1213 : : * This does not account for the P2WSH script push. */
1214 : 91994 : std::optional<uint32_t> GetStackSize() const {
1215 [ + + ]: 91994 : if (!ss.sat.valid) return {};
1216 : 39435 : return ss.sat.value;
1217 : 91994 : }
1218 : :
1219 : : //! Check the maximum stack size for this script against the policy limit.
1220 : 91241 : bool CheckStackSize() const {
1221 [ + + ]: 91241 : if (const auto ss = GetStackSize()) return *ss <= MAX_STANDARD_P2WSH_STACK_ITEMS;
1222 : 52505 : return true;
1223 : 91241 : }
1224 : :
1225 : : //! Whether no satisfaction exists for this node.
1226 : 282 : bool IsNotSatisfiable() const { return !GetStackSize(); }
1227 : :
1228 : : /** Return the maximum size in bytes of a witness to satisfy this script non-malleably. Note this does
1229 : : * not include the witness script push. */
1230 : 302 : std::optional<uint32_t> GetWitnessSize() const {
1231 [ - + ]: 302 : if (!ws.sat.valid) return {};
1232 : 302 : return ws.sat.value;
1233 : 302 : }
1234 : :
1235 : : //! Return the expression type.
1236 : 5811864 : Type GetType() const { return typ; }
1237 : :
1238 : : //! Find an insane subnode which has no insane children. Nullptr if there is none.
1239 : 485 : const Node* FindInsaneSub() const {
1240 : 113625 : return TreeEval<const Node*>([](const Node& node, Span<const Node*> subs) -> const Node* {
1241 [ + + + + ]: 194827 : for (auto& sub: subs) if (sub) return sub;
1242 [ + + ]: 90301 : if (!node.IsSaneSubexpression()) return &node;
1243 : 88202 : return nullptr;
1244 : 113140 : });
1245 : : }
1246 : :
1247 : : //! Determine whether a Miniscript node is satisfiable. fn(node) will be invoked for all
1248 : : //! key, time, and hashing nodes, and should return their satisfiability.
1249 : : template<typename F>
1250 : 1634 : bool IsSatisfiable(F fn) const
1251 : : {
1252 : : // TreeEval() doesn't support bool as NodeType, so use int instead.
1253 : 89937 : return TreeEval<int>([&fn](const Node& node, Span<int> subs) -> bool {
1254 [ + + + + : 88303 : switch (node.fragment) {
+ + + + ]
1255 : : case Fragment::JUST_0:
1256 : 18044 : return false;
1257 : : case Fragment::JUST_1:
1258 : 3715 : return true;
1259 : : case Fragment::PK_K:
1260 : : case Fragment::PK_H:
1261 : : case Fragment::MULTI:
1262 : : case Fragment::AFTER:
1263 : : case Fragment::OLDER:
1264 : : case Fragment::HASH256:
1265 : : case Fragment::HASH160:
1266 : : case Fragment::SHA256:
1267 : : case Fragment::RIPEMD160:
1268 : 14503 : return bool{fn(node)};
1269 : : case Fragment::ANDOR:
1270 [ + + + + ]: 4140 : return (subs[0] && subs[1]) || subs[2];
1271 : : case Fragment::AND_V:
1272 : : case Fragment::AND_B:
1273 [ + + ]: 9379 : return subs[0] && subs[1];
1274 : : case Fragment::OR_B:
1275 : : case Fragment::OR_C:
1276 : : case Fragment::OR_D:
1277 : : case Fragment::OR_I:
1278 [ + + ]: 10453 : return subs[0] || subs[1];
1279 : : case Fragment::THRESH:
1280 : 3111 : return static_cast<uint32_t>(std::count(subs.begin(), subs.end(), true)) >= node.k;
1281 : : default: // wrappers
1282 [ - + ]: 24958 : assert(subs.size() == 1);
1283 : 24958 : return subs[0];
1284 : : }
1285 : 88303 : });
1286 : : }
1287 : :
1288 : : //! Check whether this node is valid at all.
1289 [ + + + + ]: 943817 : bool IsValid() const { return !(GetType() == ""_mst) && ScriptSize() <= MAX_STANDARD_P2WSH_SCRIPT_SIZE; }
1290 : :
1291 : : //! Check whether this node is valid as a script on its own.
1292 [ + + + + ]: 6852 : bool IsValidTopLevel() const { return IsValid() && GetType() << "B"_mst; }
1293 : :
1294 : : //! Check whether this script can always be satisfied in a non-malleable way.
1295 : 91106 : bool IsNonMalleable() const { return GetType() << "m"_mst; }
1296 : :
1297 : : //! Check whether this script always needs a signature.
1298 : 1050 : bool NeedsSignature() const { return GetType() << "s"_mst; }
1299 : :
1300 : : //! Check whether there is no satisfaction path that contains both timelocks and heightlocks
1301 : 89900 : bool CheckTimeLocksMix() const { return GetType() << "k"_mst; }
1302 : :
1303 : : //! Check whether there is no duplicate key across this fragment and all its sub-fragments.
1304 [ - + ]: 89784 : bool CheckDuplicateKey() const { return has_duplicate_keys && !*has_duplicate_keys; }
1305 : :
1306 : : //! Whether successful non-malleable satisfactions are guaranteed to be valid.
1307 [ + + + + ]: 92953 : bool ValidSatisfactions() const { return IsValid() && CheckOpsLimit() && CheckStackSize(); }
1308 : :
1309 : : //! Whether the apparent policy of this node matches its script semantics. Doesn't guarantee it is a safe script on its own.
1310 [ + + + + : 92594 : bool IsSaneSubexpression() const { return ValidSatisfactions() && IsNonMalleable() && CheckTimeLocksMix() && CheckDuplicateKey(); }
+ + ]
1311 : :
1312 : : //! Check whether this node is safe as a script on its own.
1313 [ + + + + ]: 2748 : bool IsSane() const { return IsValidTopLevel() && IsSaneSubexpression() && NeedsSignature(); }
1314 : :
1315 : : //! Produce a witness for this script, if possible and given the information available in the context.
1316 : : //! The non-malleable satisfaction is guaranteed to be valid if it exists, and ValidSatisfaction()
1317 : : //! is true. If IsSane() holds, this satisfaction is guaranteed to succeed in case the node's
1318 : : //! conditions are satisfied (private keys and hash preimages available, locktimes satsified).
1319 : : template<typename Ctx>
1320 : 3268 : Availability Satisfy(const Ctx& ctx, std::vector<std::vector<unsigned char>>& stack, bool nonmalleable = true) const {
1321 : 3268 : auto ret = ProduceInput(ctx);
1322 [ + + + + : 3268 : if (nonmalleable && (ret.sat.malleable || !ret.sat.has_sig)) return Availability::NO;
+ + ]
1323 : 1954 : stack = std::move(ret.sat.stack);
1324 : 1954 : return ret.sat.available;
1325 : 3268 : }
1326 : :
1327 : : //! Equality testing.
1328 : 2385 : bool operator==(const Node<Key>& arg) const { return Compare(*this, arg) == 0; }
1329 : :
1330 : : // Constructors with various argument combinations, which bypass the duplicate key check.
1331 [ + - + - : 101408 : Node(internal::NoDupCheck, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<unsigned char> arg, uint32_t val = 0) : fragment(nt), k(val), data(std::move(arg)), subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
+ - + - +
- ]
1332 [ + - + - : 10370 : Node(internal::NoDupCheck, Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0) : fragment(nt), k(val), data(std::move(arg)), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
+ - + - +
- + - + -
+ - + - +
- ]
1333 : : Node(internal::NoDupCheck, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<Key> key, uint32_t val = 0) : fragment(nt), k(val), keys(std::move(key)), subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
1334 [ + - + - : 35977 : Node(internal::NoDupCheck, Fragment nt, std::vector<Key> key, uint32_t val = 0) : fragment(nt), k(val), keys(std::move(key)), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
+ - + - +
- + - + -
+ - + - +
- ]
1335 [ + - + - : 596460 : Node(internal::NoDupCheck, Fragment nt, std::vector<NodeRef<Key>> sub, uint32_t val = 0) : fragment(nt), k(val), subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
+ - + - +
- + - + -
+ - + - +
- ]
1336 [ + - + - : 305298 : Node(internal::NoDupCheck, Fragment nt, uint32_t val = 0) : fragment(nt), k(val), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
+ - + - +
- + - + -
+ - + - +
- ]
1337 : :
1338 : : // Constructors with various argument combinations, which do perform the duplicate key check.
1339 : : template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<unsigned char> arg, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, std::move(sub), std::move(arg), val) { DuplicateKeyCheck(ctx); }
1340 : : template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, std::move(arg), val) { DuplicateKeyCheck(ctx);}
1341 : : template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<Key> key, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, std::move(sub), std::move(key), val) { DuplicateKeyCheck(ctx); }
1342 : : template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<Key> key, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, std::move(key), val) { DuplicateKeyCheck(ctx); }
1343 : : template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>> sub, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, std::move(sub), val) { DuplicateKeyCheck(ctx); }
1344 [ + - ]: 6182 : template <typename Ctx> Node(const Ctx& ctx, Fragment nt, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, val) { DuplicateKeyCheck(ctx); }
1345 : : };
1346 : :
1347 : : namespace internal {
1348 : :
1349 : : enum class ParseContext {
1350 : : /** An expression which may be begin with wrappers followed by a colon. */
1351 : : WRAPPED_EXPR,
1352 : : /** A miniscript expression which does not begin with wrappers. */
1353 : : EXPR,
1354 : :
1355 : : /** SWAP wraps the top constructed node with s: */
1356 : : SWAP,
1357 : : /** ALT wraps the top constructed node with a: */
1358 : : ALT,
1359 : : /** CHECK wraps the top constructed node with c: */
1360 : : CHECK,
1361 : : /** DUP_IF wraps the top constructed node with d: */
1362 : : DUP_IF,
1363 : : /** VERIFY wraps the top constructed node with v: */
1364 : : VERIFY,
1365 : : /** NON_ZERO wraps the top constructed node with j: */
1366 : : NON_ZERO,
1367 : : /** ZERO_NOTEQUAL wraps the top constructed node with n: */
1368 : : ZERO_NOTEQUAL,
1369 : : /** WRAP_U will construct an or_i(X,0) node from the top constructed node. */
1370 : : WRAP_U,
1371 : : /** WRAP_T will construct an and_v(X,1) node from the top constructed node. */
1372 : : WRAP_T,
1373 : :
1374 : : /** AND_N will construct an andor(X,Y,0) node from the last two constructed nodes. */
1375 : : AND_N,
1376 : : /** AND_V will construct an and_v node from the last two constructed nodes. */
1377 : : AND_V,
1378 : : /** AND_B will construct an and_b node from the last two constructed nodes. */
1379 : : AND_B,
1380 : : /** ANDOR will construct an andor node from the last three constructed nodes. */
1381 : : ANDOR,
1382 : : /** OR_B will construct an or_b node from the last two constructed nodes. */
1383 : : OR_B,
1384 : : /** OR_C will construct an or_c node from the last two constructed nodes. */
1385 : : OR_C,
1386 : : /** OR_D will construct an or_d node from the last two constructed nodes. */
1387 : : OR_D,
1388 : : /** OR_I will construct an or_i node from the last two constructed nodes. */
1389 : : OR_I,
1390 : :
1391 : : /** THRESH will read a wrapped expression, and then look for a COMMA. If
1392 : : * no comma follows, it will construct a thresh node from the appropriate
1393 : : * number of constructed children. Otherwise, it will recurse with another
1394 : : * THRESH. */
1395 : : THRESH,
1396 : :
1397 : : /** COMMA expects the next element to be ',' and fails if not. */
1398 : : COMMA,
1399 : : /** CLOSE_BRACKET expects the next element to be ')' and fails if not. */
1400 : : CLOSE_BRACKET,
1401 : : };
1402 : :
1403 : : int FindNextChar(Span<const char> in, const char m);
1404 : :
1405 : : /** Parse a key string ending at the end of the fragment's text representation. */
1406 : : template<typename Key, typename Ctx>
1407 : 8791 : std::optional<std::pair<Key, int>> ParseKeyEnd(Span<const char> in, const Ctx& ctx)
1408 : : {
1409 : 8791 : int key_size = FindNextChar(in, ')');
1410 [ + + ]: 8791 : if (key_size < 1) return {};
1411 : 8771 : auto key = ctx.FromString(in.begin(), in.begin() + key_size);
1412 [ + + ]: 8771 : if (!key) return {};
1413 : 8736 : return {{std::move(*key), key_size}};
1414 : 8791 : }
1415 : :
1416 : : /** Parse a hex string ending at the end of the fragment's text representation. */
1417 : : template<typename Ctx>
1418 : 5907 : std::optional<std::pair<std::vector<unsigned char>, int>> ParseHexStrEnd(Span<const char> in, const size_t expected_size,
1419 : : const Ctx& ctx)
1420 : : {
1421 : 5907 : int hash_size = FindNextChar(in, ')');
1422 [ + + ]: 5907 : if (hash_size < 1) return {};
1423 [ + - ]: 5895 : std::string val = std::string(in.begin(), in.begin() + hash_size);
1424 [ + - + + ]: 5895 : if (!IsHex(val)) return {};
1425 [ + - ]: 5884 : auto hash = ParseHex(val);
1426 [ + + ]: 5884 : if (hash.size() != expected_size) return {};
1427 [ + - - + ]: 5866 : return {{std::move(hash), hash_size}};
1428 : 5907 : }
1429 : :
1430 : : /** BuildBack pops the last two elements off `constructed` and wraps them in the specified Fragment */
1431 : : template<typename Key>
1432 : 120628 : void BuildBack(Fragment nt, std::vector<NodeRef<Key>>& constructed, const bool reverse = false)
1433 : : {
1434 : 120628 : NodeRef<Key> child = std::move(constructed.back());
1435 : 120628 : constructed.pop_back();
1436 [ + + + - ]: 120628 : if (reverse) {
1437 [ + - + - : 38124 : constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, nt, Vector(std::move(child), std::move(constructed.back())));
+ - + - ]
1438 : 38124 : } else {
1439 [ + - + - : 82504 : constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, nt, Vector(std::move(constructed.back()), std::move(child)));
# # # # ]
1440 : : }
1441 : 120628 : }
1442 : :
1443 : : /**
1444 : : * Parse a miniscript from its textual descriptor form.
1445 : : * This does not check whether the script is valid, let alone sane. The caller is expected to use
1446 : : * the `IsValidTopLevel()` and `IsSaneTopLevel()` to check for these properties on the node.
1447 : : */
1448 : : template<typename Key, typename Ctx>
1449 : 5585 : inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
1450 : : {
1451 : : using namespace spanparsing;
1452 : :
1453 : : // Account for the minimum script size for all parsed fragments so far. It "borrows" 1
1454 : : // script byte from all leaf nodes, counting it instead whenever a space for a recursive
1455 : : // expression is added (through andor, and_*, or_*, thresh). This guarantees that all fragments
1456 : : // increment the script_size by at least one, except for:
1457 : : // - "0", "1": these leafs are only a single byte, so their subtracted-from increment is 0.
1458 : : // This is not an issue however, as "space" for them has to be created by combinators,
1459 : : // which do increment script_size.
1460 : : // - "v:": the v wrapper adds nothing as in some cases it results in no opcode being added
1461 : : // (instead transforming another opcode into its VERIFY form). However, the v: wrapper has
1462 : : // to be interleaved with other fragments to be valid, so this is not a concern.
1463 : 5585 : size_t script_size{1};
1464 : :
1465 : : // The two integers are used to hold state for thresh()
1466 : 5585 : std::vector<std::tuple<ParseContext, int64_t, int64_t>> to_parse;
1467 : 5585 : std::vector<NodeRef<Key>> constructed;
1468 : :
1469 [ + - ]: 5585 : to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1470 : :
1471 [ + + ]: 1111884 : while (!to_parse.empty()) {
1472 [ + + ]: 1107480 : if (script_size > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
1473 : :
1474 : : // Get the current context we are decoding within
1475 : 2633965 : auto [cur_context, n, k] = to_parse.back();
1476 : 1107475 : to_parse.pop_back();
1477 : :
1478 [ + + + + : 1107475 : switch (cur_context) {
+ + + + +
+ + + + +
+ - + + +
+ + + + ]
1479 : : case ParseContext::WRAPPED_EXPR: {
1480 : 251092 : std::optional<size_t> colon_index{};
1481 [ + + ]: 759518 : for (size_t i = 1; i < in.size(); ++i) {
1482 [ + + ]: 759390 : if (in[i] == ':') {
1483 [ + - ]: 85720 : colon_index = i;
1484 : 85720 : break;
1485 : : }
1486 [ + + + + ]: 673670 : if (in[i] < 'a' || in[i] > 'z') break;
1487 : 508426 : }
1488 : : // If there is no colon, this loop won't execute
1489 : 251092 : bool last_was_v{false};
1490 [ + + + - : 630072 : for (size_t j = 0; colon_index && j < *colon_index; ++j) {
+ + ]
1491 [ + + ]: 379007 : if (script_size > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
1492 [ + + ]: 379002 : if (in[j] == 'a') {
1493 : 35872 : script_size += 2;
1494 [ + - ]: 35872 : to_parse.emplace_back(ParseContext::ALT, -1, -1);
1495 [ + + ]: 379002 : } else if (in[j] == 's') {
1496 : 24172 : script_size += 1;
1497 [ + - ]: 24172 : to_parse.emplace_back(ParseContext::SWAP, -1, -1);
1498 [ + + ]: 343130 : } else if (in[j] == 'c') {
1499 : 7122 : script_size += 1;
1500 [ + - ]: 7122 : to_parse.emplace_back(ParseContext::CHECK, -1, -1);
1501 [ + + ]: 318958 : } else if (in[j] == 'd') {
1502 : 18306 : script_size += 3;
1503 [ + - ]: 18306 : to_parse.emplace_back(ParseContext::DUP_IF, -1, -1);
1504 [ + + ]: 311836 : } else if (in[j] == 'j') {
1505 : 6982 : script_size += 4;
1506 [ + - ]: 6982 : to_parse.emplace_back(ParseContext::NON_ZERO, -1, -1);
1507 [ + + ]: 293530 : } else if (in[j] == 'n') {
1508 : 168479 : script_size += 1;
1509 [ + - ]: 168479 : to_parse.emplace_back(ParseContext::ZERO_NOTEQUAL, -1, -1);
1510 [ + + ]: 286548 : } else if (in[j] == 'v') {
1511 : : // do not permit "...vv...:"; it's not valid, and also doesn't trigger early
1512 : : // failure as script_size isn't incremented.
1513 [ + + ]: 27006 : if (last_was_v) return {};
1514 [ + - ]: 27001 : to_parse.emplace_back(ParseContext::VERIFY, -1, -1);
1515 [ + + ]: 118064 : } else if (in[j] == 'u') {
1516 : 31288 : script_size += 4;
1517 [ + - ]: 31288 : to_parse.emplace_back(ParseContext::WRAP_U, -1, -1);
1518 [ + + ]: 91063 : } else if (in[j] == 't') {
1519 : 19253 : script_size += 1;
1520 [ + - ]: 19253 : to_parse.emplace_back(ParseContext::WRAP_T, -1, -1);
1521 [ + + ]: 59775 : } else if (in[j] == 'l') {
1522 : : // The l: wrapper is equivalent to or_i(0,X)
1523 : 40505 : script_size += 4;
1524 [ + - + - ]: 40505 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_0));
1525 [ + - ]: 40505 : to_parse.emplace_back(ParseContext::OR_I, -1, -1);
1526 : 40505 : } else {
1527 : 17 : return {};
1528 : : }
1529 : 378980 : last_was_v = (in[j] == 'v');
1530 : 378980 : }
1531 [ + - ]: 251065 : to_parse.emplace_back(ParseContext::EXPR, -1, -1);
1532 [ + + + - ]: 251065 : if (colon_index) in = in.subspan(*colon_index + 1);
1533 : 251065 : break;
1534 : : }
1535 : : case ParseContext::EXPR: {
1536 [ - + - + : 251062 : if (Const("0", in)) {
+ + ]
1537 [ + - + - ]: 69667 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_0));
1538 [ + - + - : 251062 : } else if (Const("1", in)) {
+ + ]
1539 [ + - + - ]: 46426 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_1));
1540 [ + - + - : 181395 : } else if (Const("pk(", in)) {
+ + ]
1541 [ + - ]: 2260 : auto res = ParseKeyEnd<Key, Ctx>(in, ctx);
1542 [ + + ]: 2260 : if (!res) return {};
1543 [ + - ]: 4462 : auto& [key, key_size] = *res;
1544 [ + - + - : 4462 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_C, Vector(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_K, Vector(std::move(key))))));
+ - + - +
- + + ]
1545 : 2231 : in = in.subspan(key_size + 1);
1546 : 2231 : script_size += 34;
1547 [ - + - + : 134940 : } else if (Const("pkh(", in)) {
+ + ]
1548 [ + - ]: 1612 : auto res = ParseKeyEnd<Key>(in, ctx);
1549 [ + + ]: 1612 : if (!res) return {};
1550 [ + - ]: 3202 : auto& [key, key_size] = *res;
1551 [ + - + - : 3202 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_C, Vector(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_H, Vector(std::move(key))))));
+ - + - +
- + - ]
1552 : 1601 : in = in.subspan(key_size + 1);
1553 : 1601 : script_size += 24;
1554 [ + + + + : 132698 : } else if (Const("pk_k(", in)) {
+ + ]
1555 [ + - ]: 3123 : auto res = ParseKeyEnd<Key>(in, ctx);
1556 [ + + ]: 3123 : if (!res) return {};
1557 [ + - ]: 6230 : auto& [key, key_size] = *res;
1558 [ + - + - : 6230 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_K, Vector(std::move(key))));
+ - + - ]
1559 : 3115 : in = in.subspan(key_size + 1);
1560 : 3115 : script_size += 33;
1561 [ - + + + : 131089 : } else if (Const("pk_h(", in)) {
+ + ]
1562 [ + - ]: 1796 : auto res = ParseKeyEnd<Key>(in, ctx);
1563 [ + + ]: 1796 : if (!res) return {};
1564 [ + - ]: 3578 : auto& [key, key_size] = *res;
1565 [ + - + - : 3578 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_H, Vector(std::move(key))));
+ - + - ]
1566 : 1789 : in = in.subspan(key_size + 1);
1567 : 1789 : script_size += 23;
1568 [ + - + - : 127967 : } else if (Const("sha256(", in)) {
+ + ]
1569 [ + - ]: 1487 : auto res = ParseHexStrEnd(in, 32, ctx);
1570 [ + + ]: 1487 : if (!res) return {};
1571 [ + - ]: 2926 : auto& [hash, hash_size] = *res;
1572 [ + - + - : 2926 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::SHA256, std::move(hash)));
+ + ]
1573 : 1463 : in = in.subspan(hash_size + 1);
1574 : 1463 : script_size += 38;
1575 [ + + + - : 126178 : } else if (Const("ripemd160(", in)) {
+ - + + ]
1576 [ + - ]: 1174 : auto res = ParseHexStrEnd(in, 20, ctx);
1577 [ + + ]: 1174 : if (!res) return {};
1578 [ + - ]: 2338 : auto& [hash, hash_size] = *res;
1579 [ + - + - : 2338 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::RIPEMD160, std::move(hash)));
+ - ]
1580 : 1169 : in = in.subspan(hash_size + 1);
1581 : 1169 : script_size += 26;
1582 [ + + - + : 124691 : } else if (Const("hash256(", in)) {
- + + + ]
1583 [ + - ]: 1413 : auto res = ParseHexStrEnd(in, 32, ctx);
1584 [ + + ]: 1413 : if (!res) return {};
1585 [ + - ]: 2816 : auto& [hash, hash_size] = *res;
1586 [ + - + - : 2816 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::HASH256, std::move(hash)));
+ - ]
1587 : 1408 : in = in.subspan(hash_size + 1);
1588 : 1408 : script_size += 38;
1589 [ + + + - : 123517 : } else if (Const("hash160(", in)) {
+ - + + ]
1590 [ + - ]: 1833 : auto res = ParseHexStrEnd(in, 20, ctx);
1591 [ + + ]: 1833 : if (!res) return {};
1592 [ + - ]: 3652 : auto& [hash, hash_size] = *res;
1593 [ + - + - : 3652 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::HASH160, std::move(hash)));
- + ]
1594 : 1826 : in = in.subspan(hash_size + 1);
1595 : 1826 : script_size += 26;
1596 [ + + - + : 122104 : } else if (Const("after(", in)) {
- + + + ]
1597 [ + - ]: 11013 : int arg_size = FindNextChar(in, ')');
1598 [ + + ]: 11013 : if (arg_size < 1) return {};
1599 : : int64_t num;
1600 [ - + - + : 11007 : if (!ParseInt64(std::string(in.begin(), in.begin() + arg_size), &num)) return {};
+ + ]
1601 [ + + + + ]: 10981 : if (num < 1 || num >= 0x80000000L) return {};
1602 [ + - + + ]: 10976 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::AFTER, num));
1603 : 10976 : in = in.subspan(arg_size + 1);
1604 : 10976 : script_size += 1 + (num > 16) + (num > 0x7f) + (num > 0x7fff) + (num > 0x7fffff);
1605 [ - + - + : 120234 : } else if (Const("older(", in)) {
+ + ]
1606 [ + - ]: 10891 : int arg_size = FindNextChar(in, ')');
1607 [ + + ]: 10891 : if (arg_size < 1) return {};
1608 : : int64_t num;
1609 [ - + - + : 10885 : if (!ParseInt64(std::string(in.begin(), in.begin() + arg_size), &num)) return {};
+ + ]
1610 [ + + + - ]: 10850 : if (num < 1 || num >= 0x80000000L) return {};
1611 [ + - + + ]: 10845 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::OLDER, num));
1612 : 10845 : in = in.subspan(arg_size + 1);
1613 : 10845 : script_size += 1 + (num > 16) + (num > 0x7f) + (num > 0x7fff) + (num > 0x7fffff);
1614 [ - + - + : 109212 : } else if (Const("multi(", in)) {
+ + ]
1615 : : // Get threshold
1616 [ + - ]: 6951 : int next_comma = FindNextChar(in, ',');
1617 [ + + ]: 6951 : if (next_comma < 1) return {};
1618 [ - + - + : 6946 : if (!ParseInt64(std::string(in.begin(), in.begin() + next_comma), &k)) return {};
- + + + ]
1619 : 6930 : in = in.subspan(next_comma + 1);
1620 : : // Get keys
1621 : 6930 : std::vector<Key> keys;
1622 [ + + ]: 40081 : while (next_comma != -1) {
1623 [ + - ]: 33208 : next_comma = FindNextChar(in, ',');
1624 [ + + + - ]: 33208 : int key_length = (next_comma == -1) ? FindNextChar(in, ')') : next_comma;
1625 [ + + ]: 33208 : if (key_length < 1) return {};
1626 [ + - ]: 33191 : auto key = ctx.FromString(in.begin(), in.begin() + key_length);
1627 [ + + ]: 33191 : if (!key) return {};
1628 [ + - + - ]: 33151 : keys.push_back(std::move(*key));
1629 : 33151 : in = in.subspan(key_length + 1);
1630 : : }
1631 [ + - + + ]: 6873 : if (keys.size() < 1 || keys.size() > 20) return {};
1632 [ + + + + ]: 6864 : if (k < 1 || k > (int64_t)keys.size()) return {};
1633 : 13716 : script_size += 2 + (keys.size() > 16) + (k > 16) + 34 * keys.size();
1634 [ + - + - : 13716 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::MULTI, std::move(keys), k));
+ + ]
1635 [ + + - + : 98346 : } else if (Const("thresh(", in)) {
- + + + ]
1636 [ + - ]: 16611 : int next_comma = FindNextChar(in, ',');
1637 [ + + ]: 16611 : if (next_comma < 1) return {};
1638 [ - + - + : 16606 : if (!ParseInt64(std::string(in.begin(), in.begin() + next_comma), &k)) return {};
- + + + ]
1639 [ + + ]: 16581 : if (k < 1) return {};
1640 : 16576 : in = in.subspan(next_comma + 1);
1641 : : // n = 1 here because we read the first WRAPPED_EXPR before reaching THRESH
1642 [ + - + - ]: 33152 : to_parse.emplace_back(ParseContext::THRESH, 1, k);
1643 [ + - ]: 16576 : to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1644 : 66304 : script_size += 2 + (k > 16) + (k > 0x7f) + (k > 0x7fff) + (k > 0x7fffff);
1645 [ - + - + : 91381 : } else if (Const("andor(", in)) {
+ + ]
1646 [ + - ]: 5287 : to_parse.emplace_back(ParseContext::ANDOR, -1, -1);
1647 [ + - ]: 5287 : to_parse.emplace_back(ParseContext::CLOSE_BRACKET, -1, -1);
1648 [ + - ]: 5287 : to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1649 [ + - ]: 5287 : to_parse.emplace_back(ParseContext::COMMA, -1, -1);
1650 [ + - ]: 5287 : to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1651 [ + - ]: 5287 : to_parse.emplace_back(ParseContext::COMMA, -1, -1);
1652 [ + - ]: 5287 : to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1653 : 5287 : script_size += 5;
1654 : 5287 : } else {
1655 [ - + - + : 69518 : if (Const("and_n(", in)) {
+ + ]
1656 [ + - ]: 6789 : to_parse.emplace_back(ParseContext::AND_N, -1, -1);
1657 : 6789 : script_size += 5;
1658 [ - + - + : 69518 : } else if (Const("and_b(", in)) {
+ + ]
1659 [ + - ]: 14256 : to_parse.emplace_back(ParseContext::AND_B, -1, -1);
1660 : 14256 : script_size += 2;
1661 [ - + - + : 62729 : } else if (Const("and_v(", in)) {
+ + ]
1662 [ + - ]: 13899 : to_parse.emplace_back(ParseContext::AND_V, -1, -1);
1663 : 13899 : script_size += 1;
1664 [ - + - + : 48473 : } else if (Const("or_b(", in)) {
+ + ]
1665 [ + - ]: 11973 : to_parse.emplace_back(ParseContext::OR_B, -1, -1);
1666 : 11973 : script_size += 2;
1667 [ - + - + : 34574 : } else if (Const("or_c(", in)) {
+ + ]
1668 [ + - ]: 7339 : to_parse.emplace_back(ParseContext::OR_C, -1, -1);
1669 : 7339 : script_size += 3;
1670 [ - + - + : 22601 : } else if (Const("or_d(", in)) {
+ + ]
1671 [ + - ]: 7128 : to_parse.emplace_back(ParseContext::OR_D, -1, -1);
1672 : 7128 : script_size += 4;
1673 [ - + - + : 15262 : } else if (Const("or_i(", in)) {
+ + ]
1674 [ + - ]: 7651 : to_parse.emplace_back(ParseContext::OR_I, -1, -1);
1675 : 7651 : script_size += 4;
1676 : 7651 : } else {
1677 : 483 : return {};
1678 : : }
1679 [ + - ]: 69035 : to_parse.emplace_back(ParseContext::CLOSE_BRACKET, -1, -1);
1680 [ + - ]: 69035 : to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1681 [ + - ]: 69035 : to_parse.emplace_back(ParseContext::COMMA, -1, -1);
1682 [ + - ]: 69035 : to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1683 : : }
1684 : 250272 : break;
1685 : : }
1686 : : case ParseContext::ALT: {
1687 [ + - + + ]: 34387 : constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_A, Vector(std::move(constructed.back())));
1688 : 34387 : break;
1689 : : }
1690 : : case ParseContext::SWAP: {
1691 [ + - - + ]: 22615 : constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_S, Vector(std::move(constructed.back())));
1692 : 22615 : break;
1693 : : }
1694 : : case ParseContext::CHECK: {
1695 [ + - + + ]: 5907 : constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_C, Vector(std::move(constructed.back())));
1696 : 5907 : break;
1697 : : }
1698 : : case ParseContext::DUP_IF: {
1699 [ + - + + ]: 14778 : constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_D, Vector(std::move(constructed.back())));
1700 : 14778 : break;
1701 : : }
1702 : : case ParseContext::NON_ZERO: {
1703 [ + - - + ]: 6021 : constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_J, Vector(std::move(constructed.back())));
1704 : 6021 : break;
1705 : : }
1706 : : case ParseContext::ZERO_NOTEQUAL: {
1707 [ + - + + ]: 127928 : constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_N, Vector(std::move(constructed.back())));
1708 : 127928 : break;
1709 : : }
1710 : : case ParseContext::VERIFY: {
1711 [ + - + - : 26230 : script_size += (constructed.back()->GetType() << "x"_mst);
+ - ]
1712 [ + - - + ]: 26230 : constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_V, Vector(std::move(constructed.back())));
1713 : 26230 : break;
1714 : : }
1715 : : case ParseContext::WRAP_U: {
1716 [ + - - + : 27780 : constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::OR_I, Vector(std::move(constructed.back()), MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_0)));
- + ]
1717 : 27780 : break;
1718 : : }
1719 : : case ParseContext::WRAP_T: {
1720 [ + - - + : 16661 : constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::AND_V, Vector(std::move(constructed.back()), MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_1)));
- + ]
1721 : 16661 : break;
1722 : : }
1723 : : case ParseContext::AND_B: {
1724 [ + - ]: 10829 : BuildBack(Fragment::AND_B, constructed);
1725 : 10829 : break;
1726 : : }
1727 : : case ParseContext::AND_N: {
1728 : 6182 : auto mid = std::move(constructed.back());
1729 : 6182 : constructed.pop_back();
1730 [ - + - + : 6182 : constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), MakeNodeRef<Key>(ctx, Fragment::JUST_0)));
- + ]
1731 : : break;
1732 : 6182 : }
1733 : : case ParseContext::AND_V: {
1734 [ + - ]: 12891 : BuildBack(Fragment::AND_V, constructed);
1735 : 12891 : break;
1736 : : }
1737 : : case ParseContext::OR_B: {
1738 [ + - ]: 7181 : BuildBack(Fragment::OR_B, constructed);
1739 : 7181 : break;
1740 : : }
1741 : : case ParseContext::OR_C: {
1742 [ + - ]: 5729 : BuildBack(Fragment::OR_C, constructed);
1743 : 5729 : break;
1744 : : }
1745 : : case ParseContext::OR_D: {
1746 [ + - ]: 5809 : BuildBack(Fragment::OR_D, constructed);
1747 : 5809 : break;
1748 : : }
1749 : : case ParseContext::OR_I: {
1750 [ + - ]: 40065 : BuildBack(Fragment::OR_I, constructed);
1751 : 40065 : break;
1752 : : }
1753 : : case ParseContext::ANDOR: {
1754 : 4786 : auto right = std::move(constructed.back());
1755 : 4786 : constructed.pop_back();
1756 : 4786 : auto mid = std::move(constructed.back());
1757 : 4786 : constructed.pop_back();
1758 [ - + - + ]: 4786 : constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), std::move(right)));
1759 : : break;
1760 : 4786 : }
1761 : : case ParseContext::THRESH: {
1762 [ + + ]: 95341 : if (in.size() < 1) return {};
1763 [ + + ]: 95286 : if (in[0] == ',') {
1764 : 81074 : in = in.subspan(1);
1765 [ + - + - : 243222 : to_parse.emplace_back(ParseContext::THRESH, n+1, k);
+ - ]
1766 [ + - ]: 81074 : to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1767 : 81074 : script_size += 2;
1768 [ + + ]: 95286 : } else if (in[0] == ')') {
1769 [ + + + + ]: 28324 : if (k > n) return {};
1770 : 14152 : in = in.subspan(1);
1771 : : // Children are constructed in reverse order, so iterate from end to beginning
1772 : 14152 : std::vector<NodeRef<Key>> subs;
1773 [ + + + + ]: 101090 : for (int i = 0; i < n; ++i) {
1774 [ + - ]: 86938 : subs.push_back(std::move(constructed.back()));
1775 : 86938 : constructed.pop_back();
1776 : 86938 : }
1777 [ + - ]: 14152 : std::reverse(subs.begin(), subs.end());
1778 [ + - + - : 28304 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::THRESH, std::move(subs), k));
+ - ]
1779 : 14152 : } else {
1780 : 50 : return {};
1781 : : }
1782 : 95226 : break;
1783 : : }
1784 : : case ParseContext::COMMA: {
1785 [ + + + + ]: 73615 : if (in.size() < 1 || in[0] != ',') return {};
1786 : 73537 : in = in.subspan(1);
1787 : 73537 : break;
1788 : : }
1789 : : case ParseContext::CLOSE_BRACKET: {
1790 [ + + + + ]: 60586 : if (in.size() < 1 || in[0] != ')') return {};
1791 : 60420 : in = in.subspan(1);
1792 : 60420 : break;
1793 : : }
1794 : : }
1795 : : }
1796 : :
1797 : : // Sanity checks on the produced miniscript
1798 [ + - ]: 4404 : assert(constructed.size() == 1);
1799 [ + - + - ]: 4404 : assert(constructed[0]->ScriptSize() == script_size);
1800 [ + + ]: 4404 : if (in.size() > 0) return {};
1801 : 4170 : NodeRef<Key> tl_node = std::move(constructed.front());
1802 [ + - ]: 4170 : tl_node->DuplicateKeyCheck(ctx);
1803 : 4170 : return tl_node;
1804 [ + - ]: 9755 : }
1805 : :
1806 : : /** Decode a script into opcode/push pairs.
1807 : : *
1808 : : * Construct a vector with one element per opcode in the script, in reverse order.
1809 : : * Each element is a pair consisting of the opcode, as well as the data pushed by
1810 : : * the opcode (including OP_n), if any. OP_CHECKSIGVERIFY, OP_CHECKMULTISIGVERIFY,
1811 : : * and OP_EQUALVERIFY are decomposed into OP_CHECKSIG, OP_CHECKMULTISIG, OP_EQUAL
1812 : : * respectively, plus OP_VERIFY.
1813 : : */
1814 : : std::optional<std::vector<Opcode>> DecomposeScript(const CScript& script);
1815 : :
1816 : : /** Determine whether the passed pair (created by DecomposeScript) is pushing a number. */
1817 : : std::optional<int64_t> ParseScriptNumber(const Opcode& in);
1818 : :
1819 : : enum class DecodeContext {
1820 : : /** A single expression of type B, K, or V. Specifically, this can't be an
1821 : : * and_v or an expression of type W (a: and s: wrappers). */
1822 : : SINGLE_BKV_EXPR,
1823 : : /** Potentially multiple SINGLE_BKV_EXPRs as children of (potentially multiple)
1824 : : * and_v expressions. Syntactic sugar for MAYBE_AND_V + SINGLE_BKV_EXPR. */
1825 : : BKV_EXPR,
1826 : : /** An expression of type W (a: or s: wrappers). */
1827 : : W_EXPR,
1828 : :
1829 : : /** SWAP expects the next element to be OP_SWAP (inside a W-type expression that
1830 : : * didn't end with FROMALTSTACK), and wraps the top of the constructed stack
1831 : : * with s: */
1832 : : SWAP,
1833 : : /** ALT expects the next element to be TOALTSTACK (we must have already read a
1834 : : * FROMALTSTACK earlier), and wraps the top of the constructed stack with a: */
1835 : : ALT,
1836 : : /** CHECK wraps the top constructed node with c: */
1837 : : CHECK,
1838 : : /** DUP_IF wraps the top constructed node with d: */
1839 : : DUP_IF,
1840 : : /** VERIFY wraps the top constructed node with v: */
1841 : : VERIFY,
1842 : : /** NON_ZERO wraps the top constructed node with j: */
1843 : : NON_ZERO,
1844 : : /** ZERO_NOTEQUAL wraps the top constructed node with n: */
1845 : : ZERO_NOTEQUAL,
1846 : :
1847 : : /** MAYBE_AND_V will check if the next part of the script could be a valid
1848 : : * miniscript sub-expression, and if so it will push AND_V and SINGLE_BKV_EXPR
1849 : : * to decode it and construct the and_v node. This is recursive, to deal with
1850 : : * multiple and_v nodes inside each other. */
1851 : : MAYBE_AND_V,
1852 : : /** AND_V will construct an and_v node from the last two constructed nodes. */
1853 : : AND_V,
1854 : : /** AND_B will construct an and_b node from the last two constructed nodes. */
1855 : : AND_B,
1856 : : /** ANDOR will construct an andor node from the last three constructed nodes. */
1857 : : ANDOR,
1858 : : /** OR_B will construct an or_b node from the last two constructed nodes. */
1859 : : OR_B,
1860 : : /** OR_C will construct an or_c node from the last two constructed nodes. */
1861 : : OR_C,
1862 : : /** OR_D will construct an or_d node from the last two constructed nodes. */
1863 : : OR_D,
1864 : :
1865 : : /** In a thresh expression, all sub-expressions other than the first are W-type,
1866 : : * and end in OP_ADD. THRESH_W will check for this OP_ADD and either push a W_EXPR
1867 : : * or a SINGLE_BKV_EXPR and jump to THRESH_E accordingly. */
1868 : : THRESH_W,
1869 : : /** THRESH_E constructs a thresh node from the appropriate number of constructed
1870 : : * children. */
1871 : : THRESH_E,
1872 : :
1873 : : /** ENDIF signals that we are inside some sort of OP_IF structure, which could be
1874 : : * or_d, or_c, or_i, andor, d:, or j: wrapper, depending on what follows. We read
1875 : : * a BKV_EXPR and then deal with the next opcode case-by-case. */
1876 : : ENDIF,
1877 : : /** If, inside an ENDIF context, we find an OP_NOTIF before finding an OP_ELSE,
1878 : : * we could either be in an or_d or an or_c node. We then check for IFDUP to
1879 : : * distinguish these cases. */
1880 : : ENDIF_NOTIF,
1881 : : /** If, inside an ENDIF context, we find an OP_ELSE, then we could be in either an
1882 : : * or_i or an andor node. Read the next BKV_EXPR and find either an OP_IF or an
1883 : : * OP_NOTIF. */
1884 : : ENDIF_ELSE,
1885 : : };
1886 : :
1887 : : //! Parse a miniscript from a bitcoin script
1888 : : template<typename Key, typename Ctx, typename I>
1889 : 2667 : inline NodeRef<Key> DecodeScript(I& in, I last, const Ctx& ctx)
1890 : : {
1891 : : // The two integers are used to hold state for thresh()
1892 : 2667 : std::vector<std::tuple<DecodeContext, int64_t, int64_t>> to_parse;
1893 : 2667 : std::vector<NodeRef<Key>> constructed;
1894 : :
1895 : : // This is the top level, so we assume the type is B
1896 : : // (in particular, disallowing top level W expressions)
1897 [ + + + - ]: 2667 : to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
1898 : :
1899 [ + + + + ]: 773603 : while (!to_parse.empty()) {
1900 : : // Exit early if the Miniscript is not going to be valid.
1901 [ + + + + : 771413 : if (!constructed.empty() && !constructed.back()->IsValid()) return {};
+ + + + +
- + + ]
1902 : :
1903 : : // Get the current context we are decoding within
1904 : 1604349 : auto [cur_context, n, k] = to_parse.back();
1905 : 771329 : to_parse.pop_back();
1906 : :
1907 [ + + + + : 771329 : switch(cur_context) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
- + + + +
+ + + + +
+ + + + +
+ + + + +
+ + ]
1908 : : case DecodeContext::SINGLE_BKV_EXPR: {
1909 [ + + + + ]: 276184 : if (in >= last) return {};
1910 : :
1911 : : // Constants
1912 [ + + + + ]: 276132 : if (in[0].first == OP_1) {
1913 : 10446 : ++in;
1914 [ + - + - : 10446 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_1));
+ - + - ]
1915 : 10446 : break;
1916 : : }
1917 [ + + + + ]: 265686 : if (in[0].first == OP_0) {
1918 : 60133 : ++in;
1919 [ + - + - : 60133 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_0));
+ - + - ]
1920 : 60133 : break;
1921 : : }
1922 : : // Public keys
1923 [ + + + + ]: 205553 : if (in[0].second.size() == 33) {
1924 [ + - + - ]: 3529 : auto key = ctx.FromPKBytes(in[0].second.begin(), in[0].second.end());
1925 [ + + + - ]: 3529 : if (!key) return {};
1926 : 3526 : ++in;
1927 [ + - + + : 3526 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_K, Vector(std::move(*key))));
- + + - +
- + - + -
+ - ]
1928 : 3526 : break;
1929 [ + + ]: 407 : }
1930 [ + + + + : 202024 : 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) {
+ + + + +
+ + - + +
+ + + + +
+ + + +
+ ]
1931 [ + - + - ]: 1995 : auto key = ctx.FromPKHBytes(in[2].second.begin(), in[2].second.end());
1932 [ + + + - ]: 1995 : if (!key) return {};
1933 : 1995 : in += 5;
1934 [ + - + + : 1995 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_H, Vector(std::move(*key))));
- + - + +
- + - - +
- + ]
1935 : 1995 : break;
1936 : 462 : }
1937 : : // Time locks
1938 : 200029 : std::optional<int64_t> num;
1939 [ + + + + : 200029 : if (last - in >= 2 && in[0].first == OP_CHECKSEQUENCEVERIFY && (num = ParseScriptNumber(in[1]))) {
+ - + + +
+ + + + -
+ + ]
1940 : 3132 : in += 2;
1941 [ + - + + : 3132 : if (*num < 1 || *num > 0x7FFFFFFFL) return {};
+ - + - +
+ + - ]
1942 [ + - + - : 3130 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::OLDER, *num));
+ - + - +
- ]
1943 : 3130 : break;
1944 : : }
1945 [ + + + + : 196897 : if (last - in >= 2 && in[0].first == OP_CHECKLOCKTIMEVERIFY && (num = ParseScriptNumber(in[1]))) {
+ - + + +
+ + + + -
+ + ]
1946 : 2549 : in += 2;
1947 [ + - + + : 2549 : if (num < 1 || num > 0x7FFFFFFFL) return {};
+ - + + +
- + + + -
+ + ]
1948 [ + - + - : 2547 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::AFTER, *num));
+ + + - +
- ]
1949 : 2547 : break;
1950 : : }
1951 : : // Hashes
1952 [ + + + + : 194348 : 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) {
+ + + + +
- + + + -
+ + + + +
+ + + + +
+ + + - +
+ + - + +
+ + ]
1953 [ + + + - : 4511 : if (in[2].first == OP_SHA256 && in[1].second.size() == 32) {
+ + + + ]
1954 [ + - + - : 1088 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::SHA256, in[1].second));
+ - + - ]
1955 : 1088 : in += 7;
1956 : 1088 : break;
1957 [ + + + - : 3423 : } else if (in[2].first == OP_RIPEMD160 && in[1].second.size() == 20) {
+ + + + ]
1958 [ + - + - : 951 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::RIPEMD160, in[1].second));
+ - + - ]
1959 : 951 : in += 7;
1960 : 951 : break;
1961 [ + + + - : 2472 : } else if (in[2].first == OP_HASH256 && in[1].second.size() == 32) {
+ + + + ]
1962 [ + - + + : 1182 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::HASH256, in[1].second));
+ - - + ]
1963 : 1182 : in += 7;
1964 : 1182 : break;
1965 [ + - + - : 1290 : } else if (in[2].first == OP_HASH160 && in[1].second.size() == 20) {
+ + + + ]
1966 [ + - + - : 1283 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::HASH160, in[1].second));
+ - + - ]
1967 : 1283 : in += 7;
1968 : 1283 : break;
1969 : : }
1970 : 7 : }
1971 : : // Multi
1972 [ + + + + : 189844 : if (last - in >= 3 && in[0].first == OP_CHECKMULTISIG) {
+ + + + ]
1973 : 4672 : std::vector<Key> keys;
1974 [ + - + - ]: 4672 : const auto n = ParseScriptNumber(in[1]);
1975 [ + + + + : 4672 : if (!n || last - in < 3 + *n) return {};
+ - + + +
+ ]
1976 [ + + + + : 4655 : if (*n < 1 || *n > 20) return {};
+ - - + +
+ - + ]
1977 [ + + + + : 24662 : for (int i = 0; i < *n; ++i) {
+ + ]
1978 [ + + + + ]: 20025 : if (in[2 + i].second.size() != 33) return {};
1979 [ + - + - ]: 20015 : auto key = ctx.FromPKBytes(in[2 + i].second.begin(), in[2 + i].second.end());
1980 [ + + + - ]: 20015 : if (!key) return {};
1981 [ + - + - : 20014 : keys.push_back(std::move(*key));
+ - + - ]
1982 [ + - ]: 20014 : }
1983 [ + - + - : 4637 : const auto k = ParseScriptNumber(in[2 + *n]);
+ - ]
1984 [ + + + - : 4637 : if (!k || *k < 1 || *k > *n) return {};
+ - + - +
- + - + +
+ + + - ]
1985 [ + - ]: 4634 : in += 3 + *n;
1986 [ + - + - ]: 4634 : std::reverse(keys.begin(), keys.end());
1987 [ + - + - : 4634 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::MULTI, std::move(keys), *k));
+ - + - -
+ ]
1988 : 4634 : break;
1989 : 4672 : }
1990 : : /** In the following wrappers, we only need to push SINGLE_BKV_EXPR rather
1991 : : * than BKV_EXPR, because and_v commutes with these wrappers. For example,
1992 : : * c:and_v(X,Y) produces the same script as and_v(X,c:Y). */
1993 : : // c: wrapper
1994 [ + + + + ]: 185172 : if (in[0].first == OP_CHECKSIG) {
1995 : 3986 : ++in;
1996 [ + - + - ]: 3986 : to_parse.emplace_back(DecodeContext::CHECK, -1, -1);
1997 [ + - + - ]: 3986 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
1998 : 3986 : break;
1999 : : }
2000 : : // v: wrapper
2001 [ + + + + ]: 181186 : if (in[0].first == OP_VERIFY) {
2002 : 18416 : ++in;
2003 [ + - + - ]: 18416 : to_parse.emplace_back(DecodeContext::VERIFY, -1, -1);
2004 [ + - + - ]: 18416 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2005 : 18416 : break;
2006 : : }
2007 : : // n: wrapper
2008 [ + + + + ]: 162770 : if (in[0].first == OP_0NOTEQUAL) {
2009 : 117003 : ++in;
2010 [ + - + - ]: 117003 : to_parse.emplace_back(DecodeContext::ZERO_NOTEQUAL, -1, -1);
2011 [ + - + - ]: 117003 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2012 : 117003 : break;
2013 : : }
2014 : : // Thresh
2015 [ + + + + : 45767 : if (last - in >= 3 && in[0].first == OP_EQUAL && (num = ParseScriptNumber(in[1]))) {
+ - + + +
+ + + + -
+ + ]
2016 [ + - + + : 7880 : if (*num < 1) return {};
+ + ]
2017 : 7871 : in += 2;
2018 [ + - + - : 7871 : to_parse.emplace_back(DecodeContext::THRESH_W, 0, *num);
+ - ]
2019 : 7871 : break;
2020 : : }
2021 : : // OP_ENDIF can be WRAP_J, WRAP_D, ANDOR, OR_C, OR_D, or OR_I
2022 [ + + + + ]: 37887 : if (in[0].first == OP_ENDIF) {
2023 : 29647 : ++in;
2024 [ + - + - ]: 29647 : to_parse.emplace_back(DecodeContext::ENDIF, -1, -1);
2025 [ + - + - ]: 29647 : to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
2026 : 29647 : break;
2027 : : }
2028 : : /** In and_b and or_b nodes, we only look for SINGLE_BKV_EXPR, because
2029 : : * or_b(and_v(X,Y),Z) has script [X] [Y] [Z] OP_BOOLOR, the same as
2030 : : * and_v(X,or_b(Y,Z)). In this example, the former of these is invalid as
2031 : : * miniscript, while the latter is valid. So we leave the and_v "outside"
2032 : : * while decoding. */
2033 : : // and_b
2034 [ + + + + ]: 8240 : if (in[0].first == OP_BOOLAND) {
2035 : 5032 : ++in;
2036 [ + - + - ]: 5032 : to_parse.emplace_back(DecodeContext::AND_B, -1, -1);
2037 [ + - + - ]: 5032 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2038 [ + - + - ]: 5032 : to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
2039 : 5032 : break;
2040 : : }
2041 : : // or_b
2042 [ + + + + ]: 3208 : if (in[0].first == OP_BOOLOR) {
2043 : 2975 : ++in;
2044 [ + - + - ]: 2975 : to_parse.emplace_back(DecodeContext::OR_B, -1, -1);
2045 [ + - + - ]: 2975 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2046 [ + - + - ]: 2975 : to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
2047 : 2975 : break;
2048 : : }
2049 : : // Unrecognised expression
2050 : 233 : return {};
2051 : : }
2052 : : case DecodeContext::BKV_EXPR: {
2053 [ + - + - ]: 108786 : to_parse.emplace_back(DecodeContext::MAYBE_AND_V, -1, -1);
2054 [ + - + - ]: 108786 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2055 : 108786 : break;
2056 : : }
2057 : : case DecodeContext::W_EXPR: {
2058 : : // a: wrapper
2059 [ + + + + ]: 18869 : if (in >= last) return {};
2060 [ + + + + ]: 18867 : if (in[0].first == OP_FROMALTSTACK) {
2061 : 15127 : ++in;
2062 [ + - + - ]: 15127 : to_parse.emplace_back(DecodeContext::ALT, -1, -1);
2063 : 15127 : } else {
2064 [ + - + - ]: 3740 : to_parse.emplace_back(DecodeContext::SWAP, -1, -1);
2065 : : }
2066 [ + - + - ]: 18867 : to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
2067 : 18867 : break;
2068 : : }
2069 : : case DecodeContext::MAYBE_AND_V: {
2070 : : // If we reach a potential AND_V top-level, check if the next part of the script could be another AND_V child
2071 : : // These op-codes cannot end any well-formed miniscript so cannot be used in an and_v node.
2072 [ + + + + : 104409 : 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) {
+ + + + +
+ + + + +
+ + + + +
+ + + +
+ ]
2073 [ + - + - ]: 39121 : to_parse.emplace_back(DecodeContext::AND_V, -1, -1);
2074 : : // BKV_EXPR can contain more AND_V nodes
2075 [ + - + - ]: 39121 : to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
2076 : 39121 : }
2077 : 104409 : break;
2078 : : }
2079 : : case DecodeContext::SWAP: {
2080 [ + + + + : 2102 : if (in >= last || in[0].first != OP_SWAP || constructed.empty()) return {};
+ - + + +
+ + - ]
2081 : 2095 : ++in;
2082 [ + - + - : 2095 : constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_S, Vector(std::move(constructed.back())));
+ - + - ]
2083 : 2095 : break;
2084 : : }
2085 : : case DecodeContext::ALT: {
2086 [ + + + + : 14904 : if (in >= last || in[0].first != OP_TOALTSTACK || constructed.empty()) return {};
+ - + + +
+ + - ]
2087 : 14895 : ++in;
2088 [ + - + + : 14895 : constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_A, Vector(std::move(constructed.back())));
+ - + - ]
2089 : 14895 : break;
2090 : : }
2091 : : case DecodeContext::CHECK: {
2092 [ + - + - ]: 3267 : if (constructed.empty()) return {};
2093 [ + - + - : 3267 : constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_C, Vector(std::move(constructed.back())));
+ - + - ]
2094 : 3267 : break;
2095 : : }
2096 : : case DecodeContext::DUP_IF: {
2097 [ + - + - ]: 458 : if (constructed.empty()) return {};
2098 [ + - + - : 458 : constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_D, Vector(std::move(constructed.back())));
+ - + - ]
2099 : 458 : break;
2100 : : }
2101 : : case DecodeContext::VERIFY: {
2102 [ + - + - ]: 17200 : if (constructed.empty()) return {};
2103 [ + - + - : 17200 : constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_V, Vector(std::move(constructed.back())));
+ - + - ]
2104 : 17200 : break;
2105 : : }
2106 : : case DecodeContext::NON_ZERO: {
2107 [ + - + - ]: 2105 : if (constructed.empty()) return {};
2108 [ + - + - : 2105 : constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_J, Vector(std::move(constructed.back())));
+ - + - ]
2109 : 2105 : break;
2110 : : }
2111 : : case DecodeContext::ZERO_NOTEQUAL: {
2112 [ + - + - ]: 110343 : if (constructed.empty()) return {};
2113 [ + - + - : 110343 : constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_N, Vector(std::move(constructed.back())));
+ - + - ]
2114 : 110343 : break;
2115 : : }
2116 : : case DecodeContext::AND_V: {
2117 [ + - + - ]: 14434 : if (constructed.size() < 2) return {};
2118 [ + - + - ]: 14434 : BuildBack(Fragment::AND_V, constructed, /*reverse=*/true);
2119 : 14434 : break;
2120 : : }
2121 : : case DecodeContext::AND_B: {
2122 [ + - + - ]: 3774 : if (constructed.size() < 2) return {};
2123 [ + - + - ]: 3774 : BuildBack(Fragment::AND_B, constructed, /*reverse=*/true);
2124 : 3774 : break;
2125 : : }
2126 : : case DecodeContext::OR_B: {
2127 [ - + - + ]: 2344 : if (constructed.size() < 2) return {};
2128 [ + - + - ]: 2344 : BuildBack(Fragment::OR_B, constructed, /*reverse=*/true);
2129 : 2344 : break;
2130 : : }
2131 : : case DecodeContext::OR_C: {
2132 [ + - + - ]: 2677 : if (constructed.size() < 2) return {};
2133 [ + - + - ]: 2677 : BuildBack(Fragment::OR_C, constructed, /*reverse=*/true);
2134 : 2677 : break;
2135 : : }
2136 : : case DecodeContext::OR_D: {
2137 [ - + - + ]: 3921 : if (constructed.size() < 2) return {};
2138 [ + - + - ]: 3921 : BuildBack(Fragment::OR_D, constructed, /*reverse=*/true);
2139 : 3921 : break;
2140 : : }
2141 : : case DecodeContext::ANDOR: {
2142 [ + - + - ]: 7067 : if (constructed.size() < 3) return {};
2143 : 7067 : NodeRef<Key> left = std::move(constructed.back());
2144 : 7067 : constructed.pop_back();
2145 : 7067 : NodeRef<Key> right = std::move(constructed.back());
2146 : 7067 : constructed.pop_back();
2147 : 7067 : NodeRef<Key> mid = std::move(constructed.back());
2148 [ + - + - : 7067 : constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::ANDOR, Vector(std::move(left), std::move(mid), std::move(right)));
- + - + ]
2149 : : break;
2150 : 7067 : }
2151 : : case DecodeContext::THRESH_W: {
2152 [ + - + + ]: 18503 : if (in >= last) return {};
2153 [ + + + + ]: 18502 : if (in[0].first == OP_ADD) {
2154 : 10862 : ++in;
2155 [ + - + - : 32586 : to_parse.emplace_back(DecodeContext::THRESH_W, n+1, k);
+ - + - +
- + - ]
2156 [ + - + - ]: 10862 : to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
2157 : 10862 : } else {
2158 [ + - + - : 22920 : to_parse.emplace_back(DecodeContext::THRESH_E, n+1, k);
+ - + - +
- + - ]
2159 : : // All children of thresh have type modifier d, so cannot be and_v
2160 [ + - + - ]: 7640 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2161 : : }
2162 : 18502 : break;
2163 : : }
2164 : : case DecodeContext::THRESH_E: {
2165 [ + - + + : 7146 : if (k < 1 || k > n || constructed.size() < static_cast<size_t>(n)) return {};
+ + - + -
+ + - + +
+ + - + -
+ ]
2166 : 7143 : std::vector<NodeRef<Key>> subs;
2167 [ + + + + : 24687 : for (int i = 0; i < n; ++i) {
+ + + + ]
2168 : 17544 : NodeRef<Key> sub = std::move(constructed.back());
2169 : 17544 : constructed.pop_back();
2170 [ + - + - ]: 17544 : subs.push_back(std::move(sub));
2171 : 17544 : }
2172 [ - + - + : 14286 : constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::THRESH, std::move(subs), k));
+ - - + -
+ - + ]
2173 : : break;
2174 : 7143 : }
2175 : : case DecodeContext::ENDIF: {
2176 [ + + + + ]: 27834 : if (in >= last) return {};
2177 : :
2178 : : // could be andor or or_i
2179 [ + + + + ]: 27830 : if (in[0].first == OP_ELSE) {
2180 : 18504 : ++in;
2181 [ + - + - ]: 18504 : to_parse.emplace_back(DecodeContext::ENDIF_ELSE, -1, -1);
2182 [ + - + - ]: 18504 : to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
2183 : 18504 : }
2184 : : // could be j: or d: wrapper
2185 [ + + + + ]: 9326 : else if (in[0].first == OP_IF) {
2186 [ + + + + : 2573 : if (last - in >= 2 && in[1].first == OP_DUP) {
+ + + + ]
2187 : 458 : in += 2;
2188 [ + - + - ]: 458 : to_parse.emplace_back(DecodeContext::DUP_IF, -1, -1);
2189 [ + + + - : 2573 : } else if (last - in >= 3 && in[1].first == OP_0NOTEQUAL && in[2].first == OP_SIZE) {
+ + + + +
+ + + ]
2190 : 2105 : in += 3;
2191 [ + - + - ]: 2105 : to_parse.emplace_back(DecodeContext::NON_ZERO, -1, -1);
2192 : 2105 : }
2193 : : else {
2194 : 10 : return {};
2195 : : }
2196 : : // could be or_c or or_d
2197 [ + + + + ]: 9316 : } else if (in[0].first == OP_NOTIF) {
2198 : 6743 : ++in;
2199 [ + - + - ]: 6743 : to_parse.emplace_back(DecodeContext::ENDIF_NOTIF, -1, -1);
2200 : 6743 : }
2201 : : else {
2202 : 10 : return {};
2203 : : }
2204 : 27810 : break;
2205 : : }
2206 : : case DecodeContext::ENDIF_NOTIF: {
2207 [ + + + + ]: 6743 : if (in >= last) return {};
2208 [ + + + + ]: 6741 : if (in[0].first == OP_IFDUP) {
2209 : 3976 : ++in;
2210 [ + - + - ]: 3976 : to_parse.emplace_back(DecodeContext::OR_D, -1, -1);
2211 : 3976 : } else {
2212 [ + - + - ]: 2765 : to_parse.emplace_back(DecodeContext::OR_C, -1, -1);
2213 : : }
2214 : : // or_c and or_d both require X to have type modifier d so, can't contain and_v
2215 [ + - + - ]: 6741 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2216 : 6741 : break;
2217 : : }
2218 : : case DecodeContext::ENDIF_ELSE: {
2219 [ + + + + ]: 18239 : if (in >= last) return {};
2220 [ + + + + ]: 18235 : if (in[0].first == OP_IF) {
2221 : 10974 : ++in;
2222 [ + - + - ]: 10974 : BuildBack(Fragment::OR_I, constructed, /*reverse=*/true);
2223 [ + + + + ]: 18235 : } else if (in[0].first == OP_NOTIF) {
2224 : 7259 : ++in;
2225 [ + - + - ]: 7259 : to_parse.emplace_back(DecodeContext::ANDOR, -1, -1);
2226 : : // andor requires X to have type modifier d, so it can't be and_v
2227 [ + - + - ]: 7259 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2228 : 7259 : } else {
2229 : 2 : return {};
2230 : : }
2231 : 18233 : break;
2232 : : }
2233 : : }
2234 : : }
2235 [ - + - + ]: 2150 : if (constructed.size() != 1) return {};
2236 : 2150 : NodeRef<Key> tl_node = std::move(constructed.front());
2237 [ + - + - ]: 2150 : tl_node->DuplicateKeyCheck(ctx);
2238 : : // Note that due to how ComputeType works (only assign the type to the node if the
2239 : : // subs' types are valid) this would fail if any node of tree is badly typed.
2240 [ + - + + : 2150 : if (!tl_node->IsValidTopLevel()) return {};
+ - + + ]
2241 : 2107 : return tl_node;
2242 : 2667 : }
2243 : :
2244 : : } // namespace internal
2245 : :
2246 : : template<typename Ctx>
2247 : 5585 : inline NodeRef<typename Ctx::Key> FromString(const std::string& str, const Ctx& ctx) {
2248 : 5585 : return internal::Parse<typename Ctx::Key>(str, ctx);
2249 : : }
2250 : :
2251 : : template<typename Ctx>
2252 : 2691 : inline NodeRef<typename Ctx::Key> FromScript(const CScript& script, const Ctx& ctx) {
2253 : : using namespace internal;
2254 : : // A too large Script is necessarily invalid, don't bother parsing it.
2255 [ + + - + ]: 2691 : if (script.size() > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
2256 : 2688 : auto decomposed = DecomposeScript(script);
2257 [ + + + - ]: 2688 : if (!decomposed) return {};
2258 [ + - ]: 2647 : auto it = decomposed->begin();
2259 [ + - + - : 2647 : auto ret = DecodeScript<typename Ctx::Key>(it, decomposed->end(), ctx);
+ - ]
2260 [ + + + + : 2647 : if (!ret) return {};
+ - + - ]
2261 [ + + + + : 2107 : if (it != decomposed->end()) return {};
- + ]
2262 : 2085 : return ret;
2263 : 2691 : }
2264 : :
2265 : : } // namespace miniscript
2266 : :
2267 : : #endif // BITCOIN_SCRIPT_MINISCRIPT_H
|
