Line data Source code
1 : // Copyright (c) 2019 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 <stdlib.h>
17 : #include <assert.h>
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 240332 : 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 42780 : constexpr Type operator|(Type x) const { return Type(m_flags | x.m_flags); }
134 :
135 : //! Compute the type with the intersection of properties.
136 3860 : 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 24895 : 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 : constexpr bool operator<(Type x) const { return m_flags < x.m_flags; }
143 :
144 : //! Equality operator.
145 1293 : constexpr bool operator==(Type x) const { return m_flags == x.m_flags; }
146 :
147 : //! The empty type if x is false, itself otherwise.
148 1808 : constexpr Type If(bool x) const { return Type(x ? m_flags : 0); }
149 : };
150 :
151 : //! Literal operator to construct Type objects.
152 33657 : inline constexpr Type operator"" _mst(const char* c, size_t l) {
153 33657 : Type typ{0};
154 :
155 71718 : for (const char *p = c; p < c + l; p++) {
156 38061 : typ = typ | Type(
157 73754 : *p == 'B' ? 1 << 0 : // Base type
158 65715 : *p == 'V' ? 1 << 1 : // Verify type
159 56506 : *p == 'K' ? 1 << 2 : // Key type
160 51441 : *p == 'W' ? 1 << 3 : // Wrapped type
161 46430 : *p == 'z' ? 1 << 4 : // Zero-arg property
162 41823 : *p == 'o' ? 1 << 5 : // One-arg property
163 38028 : *p == 'n' ? 1 << 6 : // Nonzero arg property
164 32867 : *p == 'd' ? 1 << 7 : // Dissatisfiable property
165 29175 : *p == 'u' ? 1 << 8 : // Unit property
166 25013 : *p == 'e' ? 1 << 9 : // Expression property
167 19926 : *p == 'f' ? 1 << 10 : // Forced property
168 16493 : *p == 's' ? 1 << 11 : // Safe property
169 13538 : *p == 'm' ? 1 << 12 : // Nonmalleable property
170 10694 : *p == 'x' ? 1 << 13 : // Expensive verify
171 8670 : *p == 'g' ? 1 << 14 : // older: contains relative time timelock (csv_time)
172 7016 : *p == 'h' ? 1 << 15 : // older: contains relative height timelock (csv_height)
173 5331 : *p == 'i' ? 1 << 16 : // after: contains time timelock (cltv_time)
174 3620 : *p == 'j' ? 1 << 17 : // after: contains height timelock (cltv_height)
175 1385 : *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 38061 : }
179 :
180 33657 : 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 1080 : 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 :
227 : namespace internal {
228 :
229 : //! Helper function for Node::CalcType.
230 : 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);
231 :
232 : //! Helper function for Node::CalcScriptLen.
233 : size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs, size_t n_keys);
234 :
235 : //! A helper sanitizer/checker for the output of CalcType.
236 : Type SanitizeType(Type x);
237 :
238 : //! Class whose objects represent the maximum of a list of integers.
239 : template<typename I>
240 : struct MaxInt {
241 : const bool valid;
242 : const I value;
243 :
244 3130 : MaxInt() : valid(false), value(0) {}
245 5934 : MaxInt(I val) : valid(true), value(val) {}
246 :
247 1460 : friend MaxInt<I> operator+(const MaxInt<I>& a, const MaxInt<I>& b) {
248 1460 : if (!a.valid || !b.valid) return {};
249 1053 : return a.value + b.value;
250 1460 : }
251 :
252 640 : friend MaxInt<I> operator|(const MaxInt<I>& a, const MaxInt<I>& b) {
253 640 : if (!a.valid) return b;
254 427 : if (!b.valid) return a;
255 238 : return std::max(a.value, b.value);
256 640 : }
257 : };
258 :
259 : struct Ops {
260 : //! Non-push opcodes.
261 : uint32_t count;
262 : //! Number of keys in possibly executed OP_CHECKMULTISIG(VERIFY)s to satisfy.
263 : MaxInt<uint32_t> sat;
264 : //! Number of keys in possibly executed OP_CHECKMULTISIG(VERIFY)s to dissatisfy.
265 : MaxInt<uint32_t> dsat;
266 :
267 2160 : Ops(uint32_t in_count, MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : count(in_count), sat(in_sat), dsat(in_dsat) {};
268 : };
269 :
270 : struct StackSize {
271 : //! Maximum stack size to satisfy;
272 : MaxInt<uint32_t> sat;
273 : //! Maximum stack size to dissatisfy;
274 : MaxInt<uint32_t> dsat;
275 :
276 1822 : StackSize(MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : sat(in_sat), dsat(in_dsat) {};
277 : };
278 :
279 : } // namespace internal
280 :
281 : //! A node in a miniscript expression.
282 : template<typename Key>
283 : struct Node {
284 : //! What node type this node is.
285 : const Fragment fragment;
286 : //! The k parameter (time for OLDER/AFTER, threshold for THRESH(_M))
287 : const uint32_t k = 0;
288 : //! The keys used by this expression (only for PK_K/PK_H/MULTI)
289 : const std::vector<Key> keys;
290 : //! The data bytes in this expression (only for HASH160/HASH256/SHA256/RIPEMD10).
291 : const std::vector<unsigned char> data;
292 : //! Subexpressions (for WRAP_*/AND_*/OR_*/ANDOR/THRESH)
293 : const std::vector<NodeRef<Key>> subs;
294 :
295 : private:
296 : //! Cached ops counts.
297 : const internal::Ops ops;
298 : //! Cached stack size bounds.
299 : const internal::StackSize ss;
300 : //! Cached expression type (computed by CalcType and fed through SanitizeType).
301 : const Type typ;
302 : //! Cached script length (computed by CalcScriptLen).
303 : const size_t scriptlen;
304 : //! Whether a public key appears more than once in this node.
305 : const bool duplicate_key;
306 :
307 : //! Compute the length of the script for this miniscript (including children).
308 1080 : size_t CalcScriptLen() const {
309 1080 : size_t subsize = 0;
310 1998 : for (const auto& sub : subs) {
311 918 : subsize += sub->ScriptSize();
312 : }
313 1080 : Type sub0type = subs.size() > 0 ? subs[0]->GetType() : ""_mst;
314 1080 : return internal::ComputeScriptLen(fragment, sub0type, subsize, k, subs.size(), keys.size());
315 : }
316 :
317 : /* Apply a recursive algorithm to a Miniscript tree, without actual recursive calls.
318 : *
319 : * The algorithm is defined by two functions: downfn and upfn. Conceptually, the
320 : * result can be thought of as first using downfn to compute a "state" for each node,
321 : * from the root down to the leaves. Then upfn is used to compute a "result" for each
322 : * node, from the leaves back up to the root, which is then returned. In the actual
323 : * implementation, both functions are invoked in an interleaved fashion, performing a
324 : * depth-first traversal of the tree.
325 : *
326 : * In more detail, it is invoked as node.TreeEvalMaybe<Result>(root, downfn, upfn):
327 : * - root is the state of the root node, of type State.
328 : * - downfn is a callable (State&, const Node&, size_t) -> State, which given a
329 : * node, its state, and an index of one of its children, computes the state of that
330 : * child. It can modify the state. Children of a given node will have downfn()
331 : * called in order.
332 : * - upfn is a callable (State&&, const Node&, Span<Result>) -> std::optional<Result>,
333 : * which given a node, its state, and a Span of the results of its children,
334 : * computes the result of the node. If std::nullopt is returned by upfn,
335 : * TreeEvalMaybe() immediately returns std::nullopt.
336 : * The return value of TreeEvalMaybe is the result of the root node.
337 : *
338 : * Result type cannot be bool due to the std::vector<bool> specialization.
339 : */
340 : template<typename Result, typename State, typename DownFn, typename UpFn>
341 1206 : std::optional<Result> TreeEvalMaybe(State root_state, DownFn downfn, UpFn upfn) const
342 : {
343 : /** Entries of the explicit stack tracked in this algorithm. */
344 : struct StackElem
345 : {
346 : const Node& node; //!< The node being evaluated.
347 : size_t expanded; //!< How many children of this node have been expanded.
348 : State state; //!< The state for that node.
349 :
350 7972 : StackElem(const Node& node_, size_t exp_, State&& state_) :
351 7972 : node(node_), expanded(exp_), state(std::move(state_)) {}
352 : };
353 : /* Stack of tree nodes being explored. */
354 1206 : std::vector<StackElem> stack;
355 : /* Results of subtrees so far. Their order and mapping to tree nodes
356 : * is implicitly defined by stack. */
357 1206 : std::vector<Result> results;
358 1206 : stack.emplace_back(*this, 0, std::move(root_state));
359 :
360 : /* Here is a demonstration of the algorithm, for an example tree A(B,C(D,E),F).
361 : * State variables are omitted for simplicity.
362 : *
363 : * First: stack=[(A,0)] results=[]
364 : * stack=[(A,1),(B,0)] results=[]
365 : * stack=[(A,1)] results=[B]
366 : * stack=[(A,2),(C,0)] results=[B]
367 : * stack=[(A,2),(C,1),(D,0)] results=[B]
368 : * stack=[(A,2),(C,1)] results=[B,D]
369 : * stack=[(A,2),(C,2),(E,0)] results=[B,D]
370 : * stack=[(A,2),(C,2)] results=[B,D,E]
371 : * stack=[(A,2)] results=[B,C]
372 : * stack=[(A,3),(F,0)] results=[B,C]
373 : * stack=[(A,3)] results=[B,C,F]
374 : * Final: stack=[] results=[A]
375 : */
376 7966 : while (stack.size()) {
377 6766 : const Node& node = stack.back().node;
378 6766 : if (stack.back().expanded < node.subs.size()) {
379 : /* We encounter a tree node with at least one unexpanded child.
380 : * Expand it. By the time we hit this node again, the result of
381 : * that child (and all earlier children) will be at the end of `results`. */
382 2780 : size_t child_index = stack.back().expanded++;
383 2780 : State child_state = downfn(stack.back().state, node, child_index);
384 2780 : stack.emplace_back(*node.subs[child_index], 0, std::move(child_state));
385 2780 : continue;
386 : }
387 : // Invoke upfn with the last node.subs.size() elements of results as input.
388 3986 : assert(results.size() >= node.subs.size());
389 3986 : std::optional<Result> result{upfn(std::move(stack.back().state), node,
390 3986 : Span<Result>{results}.last(node.subs.size()))};
391 : // If evaluation returns std::nullopt, abort immediately.
392 3986 : if (!result) return {};
393 : // Replace the last node.subs.size() elements of results with the new result.
394 3980 : results.erase(results.end() - node.subs.size(), results.end());
395 3980 : results.push_back(std::move(*result));
396 3980 : stack.pop_back();
397 3986 : }
398 : // The final remaining results element is the root result, return it.
399 1200 : assert(results.size() == 1);
400 1200 : return std::move(results[0]);
401 1206 : }
402 :
403 : /** Like TreeEvalMaybe, but without downfn or State type.
404 : * upfn takes (const Node&, Span<Result>) and returns std::optional<Result>. */
405 : template<typename Result, typename UpFn>
406 1080 : std::optional<Result> TreeEvalMaybe(UpFn upfn) const
407 : {
408 : struct DummyState {};
409 1080 : return TreeEvalMaybe<Result>(DummyState{},
410 2006 : [](DummyState, const Node&, size_t) { return DummyState{}; },
411 4166 : [&upfn](DummyState, const Node& node, Span<Result> subs) {
412 3086 : return upfn(node, subs);
413 : }
414 : );
415 : }
416 :
417 : /** Like TreeEvalMaybe, but always produces a result. upfn must return Result. */
418 : template<typename Result, typename State, typename DownFn, typename UpFn>
419 126 : Result TreeEval(State root_state, DownFn&& downfn, UpFn upfn) const
420 : {
421 : // Invoke TreeEvalMaybe with upfn wrapped to return std::optional<Result>, and then
422 : // unconditionally dereference the result (it cannot be std::nullopt).
423 252 : return std::move(*TreeEvalMaybe<Result>(std::move(root_state),
424 126 : std::forward<DownFn>(downfn),
425 1026 : [&upfn](State&& state, const Node& node, Span<Result> subs) {
426 900 : Result res{upfn(std::move(state), node, subs)};
427 900 : return std::optional<Result>(std::move(res));
428 900 : }
429 : ));
430 : }
431 :
432 : /** Compare two miniscript subtrees, using a non-recursive algorithm. */
433 : friend int Compare(const Node<Key>& node1, const Node<Key>& node2)
434 : {
435 : std::vector<std::pair<const Node<Key>&, const Node<Key>&>> queue;
436 : queue.emplace_back(node1, node2);
437 : while (!queue.empty()) {
438 : const auto& [a, b] = queue.back();
439 : queue.pop_back();
440 : if (std::tie(a.fragment, a.k, a.keys, a.data) < std::tie(b.fragment, b.k, b.keys, b.data)) return -1;
441 : if (std::tie(b.fragment, b.k, b.keys, b.data) < std::tie(a.fragment, a.k, a.keys, a.data)) return 1;
442 : if (a.subs.size() < b.subs.size()) return -1;
443 : if (b.subs.size() < a.subs.size()) return 1;
444 : size_t n = a.subs.size();
445 : for (size_t i = 0; i < n; ++i) {
446 : queue.emplace_back(*a.subs[n - 1 - i], *b.subs[n - 1 - i]);
447 : }
448 : }
449 : return 0;
450 : }
451 :
452 : //! Compute the type for this miniscript.
453 1080 : Type CalcType() const {
454 : using namespace internal;
455 :
456 : // THRESH has a variable number of subexpressions
457 1080 : std::vector<Type> sub_types;
458 1080 : if (fragment == Fragment::THRESH) {
459 71 : for (const auto& sub : subs) sub_types.push_back(sub->GetType());
460 18 : }
461 : // All other nodes than THRESH can be computed just from the types of the 0-3 subexpressions.
462 1080 : Type x = subs.size() > 0 ? subs[0]->GetType() : ""_mst;
463 1080 : Type y = subs.size() > 1 ? subs[1]->GetType() : ""_mst;
464 1080 : Type z = subs.size() > 2 ? subs[2]->GetType() : ""_mst;
465 :
466 1080 : return SanitizeType(ComputeType(fragment, x, y, z, sub_types, k, data.size(), subs.size(), keys.size()));
467 1080 : }
468 :
469 : public:
470 : template<typename Ctx>
471 126 : CScript ToScript(const Ctx& ctx) const
472 : {
473 : // To construct the CScript for a Miniscript object, we use the TreeEval algorithm.
474 : // The State is a boolean: whether or not the node's script expansion is followed
475 : // by an OP_VERIFY (which may need to be combined with the last script opcode).
476 900 : auto downfn = [](bool verify, const Node& node, size_t index) {
477 : // For WRAP_V, the subexpression is certainly followed by OP_VERIFY.
478 774 : if (node.fragment == Fragment::WRAP_V) return true;
479 : // The subexpression of WRAP_S, and the last subexpression of AND_V
480 : // inherit the followed-by-OP_VERIFY property from the parent.
481 828 : if (node.fragment == Fragment::WRAP_S ||
482 688 : (node.fragment == Fragment::AND_V && index == 1)) return verify;
483 608 : return false;
484 774 : };
485 : // The upward function computes for a node, given its followed-by-OP_VERIFY status
486 : // and the CScripts of its child nodes, the CScript of the node.
487 1026 : auto upfn = [&ctx](bool verify, const Node& node, Span<CScript> subs) -> CScript {
488 900 : switch (node.fragment) {
489 44 : case Fragment::PK_K: return BuildScript(ctx.ToPKBytes(node.keys[0]));
490 26 : case Fragment::PK_H: return BuildScript(OP_DUP, OP_HASH160, ctx.ToPKHBytes(node.keys[0]), OP_EQUALVERIFY);
491 44 : case Fragment::OLDER: return BuildScript(node.k, OP_CHECKSEQUENCEVERIFY);
492 66 : case Fragment::AFTER: return BuildScript(node.k, OP_CHECKLOCKTIMEVERIFY);
493 24 : case Fragment::SHA256: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_SHA256, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL);
494 8 : case Fragment::RIPEMD160: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_RIPEMD160, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL);
495 14 : case Fragment::HASH256: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_HASH256, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL);
496 6 : case Fragment::HASH160: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_HASH160, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL);
497 46 : case Fragment::WRAP_A: return BuildScript(OP_TOALTSTACK, subs[0], OP_FROMALTSTACK);
498 10 : case Fragment::WRAP_S: return BuildScript(OP_SWAP, subs[0]);
499 54 : case Fragment::WRAP_C: return BuildScript(std::move(subs[0]), verify ? OP_CHECKSIGVERIFY : OP_CHECKSIG);
500 4 : case Fragment::WRAP_D: return BuildScript(OP_DUP, OP_IF, subs[0], OP_ENDIF);
501 : case Fragment::WRAP_V: {
502 86 : if (node.subs[0]->GetType() << "x"_mst) {
503 64 : return BuildScript(std::move(subs[0]), OP_VERIFY);
504 : } else {
505 22 : return std::move(subs[0]);
506 : }
507 : }
508 10 : case Fragment::WRAP_J: return BuildScript(OP_SIZE, OP_0NOTEQUAL, OP_IF, subs[0], OP_ENDIF);
509 16 : case Fragment::WRAP_N: return BuildScript(std::move(subs[0]), OP_0NOTEQUAL);
510 78 : case Fragment::JUST_1: return BuildScript(OP_1);
511 88 : case Fragment::JUST_0: return BuildScript(OP_0);
512 70 : case Fragment::AND_V: return BuildScript(std::move(subs[0]), subs[1]);
513 16 : case Fragment::AND_B: return BuildScript(std::move(subs[0]), subs[1], OP_BOOLAND);
514 10 : case Fragment::OR_B: return BuildScript(std::move(subs[0]), subs[1], OP_BOOLOR);
515 16 : case Fragment::OR_D: return BuildScript(std::move(subs[0]), OP_IFDUP, OP_NOTIF, subs[1], OP_ENDIF);
516 8 : case Fragment::OR_C: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[1], OP_ENDIF);
517 86 : case Fragment::OR_I: return BuildScript(OP_IF, subs[0], OP_ELSE, subs[1], OP_ENDIF);
518 30 : case Fragment::ANDOR: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[2], OP_ELSE, subs[1], OP_ENDIF);
519 : case Fragment::MULTI: {
520 24 : CScript script = BuildScript(node.k);
521 70 : for (const auto& key : node.keys) {
522 46 : script = BuildScript(std::move(script), ctx.ToPKBytes(key));
523 : }
524 24 : return BuildScript(std::move(script), node.keys.size(), verify ? OP_CHECKMULTISIGVERIFY : OP_CHECKMULTISIG);
525 24 : }
526 : case Fragment::THRESH: {
527 16 : CScript script = std::move(subs[0]);
528 46 : for (size_t i = 1; i < subs.size(); ++i) {
529 30 : script = BuildScript(std::move(script), subs[i], OP_ADD);
530 30 : }
531 16 : return BuildScript(std::move(script), node.k, verify ? OP_EQUALVERIFY : OP_EQUAL);
532 16 : }
533 : }
534 0 : assert(false);
535 900 : };
536 126 : return TreeEval<CScript>(false, downfn, upfn);
537 : }
538 :
539 : template<typename CTx>
540 : std::optional<std::string> ToString(const CTx& ctx) const {
541 : // To construct the std::string representation for a Miniscript object, we use
542 : // the TreeEvalMaybe algorithm. The State is a boolean: whether the parent node is a
543 : // wrapper. If so, non-wrapper expressions must be prefixed with a ":".
544 : auto downfn = [](bool, const Node& node, size_t) {
545 : return (node.fragment == Fragment::WRAP_A || node.fragment == Fragment::WRAP_S ||
546 : node.fragment == Fragment::WRAP_D || node.fragment == Fragment::WRAP_V ||
547 : node.fragment == Fragment::WRAP_J || node.fragment == Fragment::WRAP_N ||
548 : node.fragment == Fragment::WRAP_C ||
549 : (node.fragment == Fragment::AND_V && node.subs[1]->fragment == Fragment::JUST_1) ||
550 : (node.fragment == Fragment::OR_I && node.subs[0]->fragment == Fragment::JUST_0) ||
551 : (node.fragment == Fragment::OR_I && node.subs[1]->fragment == Fragment::JUST_0));
552 : };
553 : // The upward function computes for a node, given whether its parent is a wrapper,
554 : // and the string representations of its child nodes, the string representation of the node.
555 : auto upfn = [&ctx](bool wrapped, const Node& node, Span<std::string> subs) -> std::optional<std::string> {
556 : std::string ret = wrapped ? ":" : "";
557 :
558 : switch (node.fragment) {
559 : case Fragment::WRAP_A: return "a" + std::move(subs[0]);
560 : case Fragment::WRAP_S: return "s" + std::move(subs[0]);
561 : case Fragment::WRAP_C:
562 : if (node.subs[0]->fragment == Fragment::PK_K) {
563 : // pk(K) is syntactic sugar for c:pk_k(K)
564 : auto key_str = ctx.ToString(node.subs[0]->keys[0]);
565 : if (!key_str) return {};
566 : return std::move(ret) + "pk(" + std::move(*key_str) + ")";
567 : }
568 : if (node.subs[0]->fragment == Fragment::PK_H) {
569 : // pkh(K) is syntactic sugar for c:pk_h(K)
570 : auto key_str = ctx.ToString(node.subs[0]->keys[0]);
571 : if (!key_str) return {};
572 : return std::move(ret) + "pkh(" + std::move(*key_str) + ")";
573 : }
574 : return "c" + std::move(subs[0]);
575 : case Fragment::WRAP_D: return "d" + std::move(subs[0]);
576 : case Fragment::WRAP_V: return "v" + std::move(subs[0]);
577 : case Fragment::WRAP_J: return "j" + std::move(subs[0]);
578 : case Fragment::WRAP_N: return "n" + std::move(subs[0]);
579 : case Fragment::AND_V:
580 : // t:X is syntactic sugar for and_v(X,1).
581 : if (node.subs[1]->fragment == Fragment::JUST_1) return "t" + std::move(subs[0]);
582 : break;
583 : case Fragment::OR_I:
584 : if (node.subs[0]->fragment == Fragment::JUST_0) return "l" + std::move(subs[1]);
585 : if (node.subs[1]->fragment == Fragment::JUST_0) return "u" + std::move(subs[0]);
586 : break;
587 : default: break;
588 : }
589 : switch (node.fragment) {
590 : case Fragment::PK_K: {
591 : auto key_str = ctx.ToString(node.keys[0]);
592 : if (!key_str) return {};
593 : return std::move(ret) + "pk_k(" + std::move(*key_str) + ")";
594 : }
595 : case Fragment::PK_H: {
596 : auto key_str = ctx.ToString(node.keys[0]);
597 : if (!key_str) return {};
598 : return std::move(ret) + "pk_h(" + std::move(*key_str) + ")";
599 : }
600 : case Fragment::AFTER: return std::move(ret) + "after(" + ::ToString(node.k) + ")";
601 : case Fragment::OLDER: return std::move(ret) + "older(" + ::ToString(node.k) + ")";
602 : case Fragment::HASH256: return std::move(ret) + "hash256(" + HexStr(node.data) + ")";
603 : case Fragment::HASH160: return std::move(ret) + "hash160(" + HexStr(node.data) + ")";
604 : case Fragment::SHA256: return std::move(ret) + "sha256(" + HexStr(node.data) + ")";
605 : case Fragment::RIPEMD160: return std::move(ret) + "ripemd160(" + HexStr(node.data) + ")";
606 : case Fragment::JUST_1: return std::move(ret) + "1";
607 : case Fragment::JUST_0: return std::move(ret) + "0";
608 : case Fragment::AND_V: return std::move(ret) + "and_v(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
609 : case Fragment::AND_B: return std::move(ret) + "and_b(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
610 : case Fragment::OR_B: return std::move(ret) + "or_b(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
611 : case Fragment::OR_D: return std::move(ret) + "or_d(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
612 : case Fragment::OR_C: return std::move(ret) + "or_c(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
613 : case Fragment::OR_I: return std::move(ret) + "or_i(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
614 : case Fragment::ANDOR:
615 : // and_n(X,Y) is syntactic sugar for andor(X,Y,0).
616 : if (node.subs[2]->fragment == Fragment::JUST_0) return std::move(ret) + "and_n(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
617 : return std::move(ret) + "andor(" + std::move(subs[0]) + "," + std::move(subs[1]) + "," + std::move(subs[2]) + ")";
618 : case Fragment::MULTI: {
619 : auto str = std::move(ret) + "multi(" + ::ToString(node.k);
620 : for (const auto& key : node.keys) {
621 : auto key_str = ctx.ToString(key);
622 : if (!key_str) return {};
623 : str += "," + std::move(*key_str);
624 : }
625 : return std::move(str) + ")";
626 : }
627 : case Fragment::THRESH: {
628 : auto str = std::move(ret) + "thresh(" + ::ToString(node.k);
629 : for (auto& sub : subs) {
630 : str += "," + std::move(sub);
631 : }
632 : return std::move(str) + ")";
633 : }
634 : default: break;
635 : }
636 : assert(false);
637 : };
638 :
639 : return TreeEvalMaybe<std::string>(false, downfn, upfn);
640 : }
641 :
642 1080 : internal::Ops CalcOps() const {
643 1080 : switch (fragment) {
644 117 : case Fragment::JUST_1: return {0, 0, {}};
645 108 : case Fragment::JUST_0: return {0, {}, 0};
646 60 : case Fragment::PK_K: return {0, 0, 0};
647 28 : case Fragment::PK_H: return {3, 0, 0};
648 : case Fragment::OLDER:
649 116 : case Fragment::AFTER: return {1, 0, {}};
650 : case Fragment::SHA256:
651 : case Fragment::RIPEMD160:
652 : case Fragment::HASH256:
653 52 : case Fragment::HASH160: return {4, 0, {}};
654 78 : case Fragment::AND_V: return {subs[0]->ops.count + subs[1]->ops.count, subs[0]->ops.sat + subs[1]->ops.sat, {}};
655 : case Fragment::AND_B: {
656 23 : const auto count{1 + subs[0]->ops.count + subs[1]->ops.count};
657 23 : const auto sat{subs[0]->ops.sat + subs[1]->ops.sat};
658 23 : const auto dsat{subs[0]->ops.dsat + subs[1]->ops.dsat};
659 23 : return {count, sat, dsat};
660 : }
661 : case Fragment::OR_B: {
662 17 : const auto count{1 + subs[0]->ops.count + subs[1]->ops.count};
663 17 : const auto sat{(subs[0]->ops.sat + subs[1]->ops.dsat) | (subs[1]->ops.sat + subs[0]->ops.dsat)};
664 17 : const auto dsat{subs[0]->ops.dsat + subs[1]->ops.dsat};
665 17 : return {count, sat, dsat};
666 : }
667 : case Fragment::OR_D: {
668 20 : const auto count{3 + subs[0]->ops.count + subs[1]->ops.count};
669 20 : const auto sat{subs[0]->ops.sat | (subs[1]->ops.sat + subs[0]->ops.dsat)};
670 20 : const auto dsat{subs[0]->ops.dsat + subs[1]->ops.dsat};
671 20 : return {count, sat, dsat};
672 : }
673 : case Fragment::OR_C: {
674 12 : const auto count{2 + subs[0]->ops.count + subs[1]->ops.count};
675 12 : const auto sat{subs[0]->ops.sat | (subs[1]->ops.sat + subs[0]->ops.dsat)};
676 12 : return {count, sat, {}};
677 : }
678 : case Fragment::OR_I: {
679 91 : const auto count{3 + subs[0]->ops.count + subs[1]->ops.count};
680 91 : const auto sat{subs[0]->ops.sat | subs[1]->ops.sat};
681 91 : const auto dsat{subs[0]->ops.dsat | subs[1]->ops.dsat};
682 91 : return {count, sat, dsat};
683 : }
684 : case Fragment::ANDOR: {
685 34 : const auto count{3 + subs[0]->ops.count + subs[1]->ops.count + subs[2]->ops.count};
686 34 : const auto sat{(subs[1]->ops.sat + subs[0]->ops.sat) | (subs[0]->ops.dsat + subs[2]->ops.sat)};
687 34 : const auto dsat{subs[0]->ops.dsat + subs[2]->ops.dsat};
688 34 : return {count, sat, dsat};
689 : }
690 25 : case Fragment::MULTI: return {1, (uint32_t)keys.size(), (uint32_t)keys.size()};
691 : case Fragment::WRAP_S:
692 : case Fragment::WRAP_C:
693 103 : case Fragment::WRAP_N: return {1 + subs[0]->ops.count, subs[0]->ops.sat, subs[0]->ops.dsat};
694 66 : case Fragment::WRAP_A: return {2 + subs[0]->ops.count, subs[0]->ops.sat, subs[0]->ops.dsat};
695 6 : case Fragment::WRAP_D: return {3 + subs[0]->ops.count, subs[0]->ops.sat, 0};
696 10 : case Fragment::WRAP_J: return {4 + subs[0]->ops.count, subs[0]->ops.sat, 0};
697 96 : case Fragment::WRAP_V: return {subs[0]->ops.count + (subs[0]->GetType() << "x"_mst), subs[0]->ops.sat, {}};
698 : case Fragment::THRESH: {
699 18 : uint32_t count = 0;
700 18 : auto sats = Vector(internal::MaxInt<uint32_t>(0));
701 71 : for (const auto& sub : subs) {
702 53 : count += sub->ops.count + 1;
703 53 : auto next_sats = Vector(sats[0] + sub->ops.dsat);
704 108 : for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub->ops.dsat) | (sats[j - 1] + sub->ops.sat));
705 53 : next_sats.push_back(sats[sats.size() - 1] + sub->ops.sat);
706 53 : sats = std::move(next_sats);
707 53 : }
708 18 : assert(k <= sats.size());
709 18 : return {count, sats[k], sats[0]};
710 18 : }
711 : }
712 0 : assert(false);
713 1080 : }
714 :
715 1080 : internal::StackSize CalcStackSize() const {
716 1080 : switch (fragment) {
717 108 : case Fragment::JUST_0: return {{}, 0};
718 : case Fragment::JUST_1:
719 : case Fragment::OLDER:
720 233 : case Fragment::AFTER: return {0, {}};
721 60 : case Fragment::PK_K: return {1, 1};
722 28 : case Fragment::PK_H: return {2, 2};
723 : case Fragment::SHA256:
724 : case Fragment::RIPEMD160:
725 : case Fragment::HASH256:
726 52 : case Fragment::HASH160: return {1, {}};
727 : case Fragment::ANDOR: {
728 34 : const auto sat{(subs[0]->ss.sat + subs[1]->ss.sat) | (subs[0]->ss.dsat + subs[2]->ss.sat)};
729 34 : const auto dsat{subs[0]->ss.dsat + subs[2]->ss.dsat};
730 34 : return {sat, dsat};
731 : }
732 78 : case Fragment::AND_V: return {subs[0]->ss.sat + subs[1]->ss.sat, {}};
733 23 : case Fragment::AND_B: return {subs[0]->ss.sat + subs[1]->ss.sat, subs[0]->ss.dsat + subs[1]->ss.dsat};
734 : case Fragment::OR_B: {
735 17 : const auto sat{(subs[0]->ss.dsat + subs[1]->ss.sat) | (subs[0]->ss.sat + subs[1]->ss.dsat)};
736 17 : const auto dsat{subs[0]->ss.dsat + subs[1]->ss.dsat};
737 17 : return {sat, dsat};
738 : }
739 12 : case Fragment::OR_C: return {subs[0]->ss.sat | (subs[0]->ss.dsat + subs[1]->ss.sat), {}};
740 20 : 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};
741 91 : 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)};
742 25 : case Fragment::MULTI: return {k + 1, k + 1};
743 : case Fragment::WRAP_A:
744 : case Fragment::WRAP_N:
745 : case Fragment::WRAP_S:
746 169 : case Fragment::WRAP_C: return subs[0]->ss;
747 6 : case Fragment::WRAP_D: return {1 + subs[0]->ss.sat, 1};
748 96 : case Fragment::WRAP_V: return {subs[0]->ss.sat, {}};
749 10 : case Fragment::WRAP_J: return {subs[0]->ss.sat, 1};
750 : case Fragment::THRESH: {
751 18 : auto sats = Vector(internal::MaxInt<uint32_t>(0));
752 71 : for (const auto& sub : subs) {
753 53 : auto next_sats = Vector(sats[0] + sub->ss.dsat);
754 108 : for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub->ss.dsat) | (sats[j - 1] + sub->ss.sat));
755 53 : next_sats.push_back(sats[sats.size() - 1] + sub->ss.sat);
756 53 : sats = std::move(next_sats);
757 53 : }
758 18 : assert(k <= sats.size());
759 18 : return {sats[k], sats[0]};
760 18 : }
761 : }
762 0 : assert(false);
763 1080 : }
764 :
765 : /** Check whether any key is repeated.
766 : * This uses a custom key comparator provided by the context in order to still detect duplicates
767 : * for more complicated types.
768 : */
769 1080 : template<typename Ctx> bool ContainsDuplicateKey(const Ctx& ctx) const {
770 : // We cannot use a lambda here, as lambdas are non assignable, and the set operations
771 : // below require moving the comparators around.
772 : struct Comp {
773 : const Ctx* ctx_ptr;
774 6172 : Comp(const Ctx& ctx) : ctx_ptr(&ctx) {}
775 298 : bool operator()(const Key& a, const Key& b) const { return ctx_ptr->KeyCompare(a, b); }
776 : };
777 : using set = std::set<Key, Comp>;
778 :
779 4166 : auto upfn = [this, &ctx](const Node& node, Span<set> subs) -> std::optional<set> {
780 3086 : if (&node != this && node.duplicate_key) return {};
781 :
782 3086 : size_t keys_count = node.keys.size();
783 3086 : set key_set{node.keys.begin(), node.keys.end(), Comp(ctx)};
784 3086 : if (key_set.size() != keys_count) return {};
785 :
786 5084 : for (auto& sub: subs) {
787 2004 : keys_count += sub.size();
788 : // Small optimization: std::set::merge is linear in the size of the second arg but
789 : // logarithmic in the size of the first.
790 2004 : if (key_set.size() < sub.size()) std::swap(key_set, sub);
791 2004 : key_set.merge(sub);
792 2004 : if (key_set.size() != keys_count) return {};
793 : }
794 :
795 3080 : return key_set;
796 3086 : };
797 :
798 1080 : return !TreeEvalMaybe<set>(upfn);
799 : }
800 :
801 : public:
802 : //! Return the size of the script for this expression (faster than ToScript().size()).
803 981 : size_t ScriptSize() const { return scriptlen; }
804 :
805 : //! Return the maximum number of ops needed to satisfy this script non-malleably.
806 67 : uint32_t GetOps() const { return ops.count + ops.sat.value; }
807 :
808 : //! Check the ops limit of this script against the consensus limit.
809 4 : bool CheckOpsLimit() const { return GetOps() <= MAX_OPS_PER_SCRIPT; }
810 :
811 : /** Return the maximum number of stack elements needed to satisfy this script non-malleably, including
812 : * the script push. */
813 63 : uint32_t GetStackSize() const { return ss.sat.value + 1; }
814 :
815 : //! Return the expression type.
816 3411 : Type GetType() const { return typ; }
817 :
818 : //! Check whether this node is valid at all.
819 1293 : bool IsValid() const { return !(GetType() == ""_mst); }
820 :
821 : //! Check whether this node is valid as a script on its own.
822 225 : bool IsValidTopLevel() const { return IsValid() && GetType() << "B"_mst; }
823 :
824 : //! Check whether this script can always be satisfied in a non-malleable way.
825 67 : bool IsNonMalleable() const { return GetType() << "m"_mst; }
826 :
827 : //! Check whether this script always needs a signature.
828 63 : bool NeedsSignature() const { return GetType() << "s"_mst; }
829 :
830 : //! Check whether there is no satisfaction path that contains both timelocks and heightlocks
831 3 : bool CheckTimeLocksMix() const { return GetType() << "k"_mst; }
832 :
833 : //! Check whether there is no duplicate key across this fragment and all its sub-fragments.
834 7 : bool CheckDuplicateKey() const { return !duplicate_key; }
835 :
836 : //! Whether successful non-malleable satisfactions are guaranteed to be valid.
837 4 : bool ValidSatisfactions() const { return IsValid() && CheckOpsLimit(); }
838 :
839 : //! Whether the apparent policy of this node matches its script semantics. Doesn't guarantee it is a safe script on its own.
840 4 : bool IsSaneSubexpression() const { return ValidSatisfactions() && IsNonMalleable() && CheckTimeLocksMix() && CheckDuplicateKey(); }
841 :
842 : //! Check whether this node is safe as a script on its own.
843 4 : bool IsSane() const { return IsValidTopLevel() && IsSaneSubexpression() && NeedsSignature(); }
844 :
845 : //! Equality testing.
846 : bool operator==(const Node<Key>& arg) const { return Compare(*this, arg) == 0; }
847 :
848 : // Constructors with various argument combinations.
849 : template <typename Ctx> Node(const Ctx& ctx, 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()), typ(CalcType()), scriptlen(CalcScriptLen()), duplicate_key(ContainsDuplicateKey(ctx)) {}
850 104 : template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0) : fragment(nt), k(val), data(std::move(arg)), ops(CalcOps()), ss(CalcStackSize()), typ(CalcType()), scriptlen(CalcScriptLen()), duplicate_key(ContainsDuplicateKey(ctx)) {}
851 : template <typename Ctx> Node(const Ctx& ctx, 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()), typ(CalcType()), scriptlen(CalcScriptLen()), duplicate_key(ContainsDuplicateKey(ctx)) {}
852 226 : template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<Key> key, uint32_t val = 0) : fragment(nt), k(val), keys(std::move(key)), ops(CalcOps()), ss(CalcStackSize()), typ(CalcType()), scriptlen(CalcScriptLen()), duplicate_key(ContainsDuplicateKey(ctx)) {}
853 1148 : template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>> sub, uint32_t val = 0) : fragment(nt), k(val), subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), typ(CalcType()), scriptlen(CalcScriptLen()), duplicate_key(ContainsDuplicateKey(ctx)) {}
854 682 : template <typename Ctx> Node(const Ctx& ctx, Fragment nt, uint32_t val = 0) : fragment(nt), k(val), ops(CalcOps()), ss(CalcStackSize()), typ(CalcType()), scriptlen(CalcScriptLen()), duplicate_key(ContainsDuplicateKey(ctx)) {}
855 : };
856 :
857 : namespace internal {
858 :
859 : enum class ParseContext {
860 : /** An expression which may be begin with wrappers followed by a colon. */
861 : WRAPPED_EXPR,
862 : /** A miniscript expression which does not begin with wrappers. */
863 : EXPR,
864 :
865 : /** SWAP wraps the top constructed node with s: */
866 : SWAP,
867 : /** ALT wraps the top constructed node with a: */
868 : ALT,
869 : /** CHECK wraps the top constructed node with c: */
870 : CHECK,
871 : /** DUP_IF wraps the top constructed node with d: */
872 : DUP_IF,
873 : /** VERIFY wraps the top constructed node with v: */
874 : VERIFY,
875 : /** NON_ZERO wraps the top constructed node with j: */
876 : NON_ZERO,
877 : /** ZERO_NOTEQUAL wraps the top constructed node with n: */
878 : ZERO_NOTEQUAL,
879 : /** WRAP_U will construct an or_i(X,0) node from the top constructed node. */
880 : WRAP_U,
881 : /** WRAP_T will construct an and_v(X,1) node from the top constructed node. */
882 : WRAP_T,
883 :
884 : /** AND_N will construct an andor(X,Y,0) node from the last two constructed nodes. */
885 : AND_N,
886 : /** AND_V will construct an and_v node from the last two constructed nodes. */
887 : AND_V,
888 : /** AND_B will construct an and_b node from the last two constructed nodes. */
889 : AND_B,
890 : /** ANDOR will construct an andor node from the last three constructed nodes. */
891 : ANDOR,
892 : /** OR_B will construct an or_b node from the last two constructed nodes. */
893 : OR_B,
894 : /** OR_C will construct an or_c node from the last two constructed nodes. */
895 : OR_C,
896 : /** OR_D will construct an or_d node from the last two constructed nodes. */
897 : OR_D,
898 : /** OR_I will construct an or_i node from the last two constructed nodes. */
899 : OR_I,
900 :
901 : /** THRESH will read a wrapped expression, and then look for a COMMA. If
902 : * no comma follows, it will construct a thresh node from the appropriate
903 : * number of constructed children. Otherwise, it will recurse with another
904 : * THRESH. */
905 : THRESH,
906 :
907 : /** COMMA expects the next element to be ',' and fails if not. */
908 : COMMA,
909 : /** CLOSE_BRACKET expects the next element to be ')' and fails if not. */
910 : CLOSE_BRACKET,
911 : };
912 :
913 : int FindNextChar(Span<const char> in, const char m);
914 :
915 : /** Parse a key string ending at the end of the fragment's text representation. */
916 : template<typename Key, typename Ctx>
917 53 : std::optional<std::pair<Key, int>> ParseKeyEnd(Span<const char> in, const Ctx& ctx)
918 : {
919 53 : int key_size = FindNextChar(in, ')');
920 53 : if (key_size < 1) return {};
921 53 : auto key = ctx.FromString(in.begin(), in.begin() + key_size);
922 53 : if (!key) return {};
923 53 : return {{std::move(*key), key_size}};
924 53 : }
925 :
926 : /** Parse a hex string ending at the end of the fragment's text representation. */
927 : template<typename Ctx>
928 26 : std::optional<std::pair<std::vector<unsigned char>, int>> ParseHexStrEnd(Span<const char> in, const size_t expected_size,
929 : const Ctx& ctx)
930 : {
931 26 : int hash_size = FindNextChar(in, ')');
932 26 : if (hash_size < 1) return {};
933 26 : std::string val = std::string(in.begin(), in.begin() + hash_size);
934 26 : if (!IsHex(val)) return {};
935 26 : auto hash = ParseHex(val);
936 26 : if (hash.size() != expected_size) return {};
937 26 : return {{std::move(hash), hash_size}};
938 26 : }
939 :
940 : /** BuildBack pops the last two elements off `constructed` and wraps them in the specified Fragment */
941 : template<typename Key, typename Ctx>
942 209 : void BuildBack(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>>& constructed, const bool reverse = false)
943 : {
944 209 : NodeRef<Key> child = std::move(constructed.back());
945 209 : constructed.pop_back();
946 209 : if (reverse) {
947 103 : constructed.back() = MakeNodeRef<Key>(ctx, nt, Vector(std::move(child), std::move(constructed.back())));
948 103 : } else {
949 106 : constructed.back() = MakeNodeRef<Key>(ctx, nt, Vector(std::move(constructed.back()), std::move(child)));
950 : }
951 209 : }
952 :
953 : //! Parse a miniscript from its textual descriptor form.
954 : template<typename Key, typename Ctx>
955 101 : inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
956 : {
957 : using namespace spanparsing;
958 :
959 : // The two integers are used to hold state for thresh()
960 101 : std::vector<std::tuple<ParseContext, int64_t, int64_t>> to_parse;
961 101 : std::vector<NodeRef<Key>> constructed;
962 :
963 101 : to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
964 :
965 1382 : while (!to_parse.empty()) {
966 : // Get the current context we are decoding within
967 1451 : auto [cur_context, n, k] = to_parse.back();
968 1287 : to_parse.pop_back();
969 :
970 1287 : switch (cur_context) {
971 : case ParseContext::WRAPPED_EXPR: {
972 358 : int colon_index = -1;
973 781 : for (int i = 1; i < (int)in.size(); ++i) {
974 781 : if (in[i] == ':') {
975 159 : colon_index = i;
976 159 : break;
977 : }
978 622 : if (in[i] < 'a' || in[i] > 'z') break;
979 423 : }
980 : // If there is no colon, this loop won't execute
981 571 : for (int j = 0; j < colon_index; ++j) {
982 213 : if (in[j] == 'a') {
983 43 : to_parse.emplace_back(ParseContext::ALT, -1, -1);
984 213 : } else if (in[j] == 's') {
985 13 : to_parse.emplace_back(ParseContext::SWAP, -1, -1);
986 170 : } else if (in[j] == 'c') {
987 31 : to_parse.emplace_back(ParseContext::CHECK, -1, -1);
988 157 : } else if (in[j] == 'd') {
989 4 : to_parse.emplace_back(ParseContext::DUP_IF, -1, -1);
990 126 : } else if (in[j] == 'j') {
991 5 : to_parse.emplace_back(ParseContext::NON_ZERO, -1, -1);
992 122 : } else if (in[j] == 'n') {
993 8 : to_parse.emplace_back(ParseContext::ZERO_NOTEQUAL, -1, -1);
994 117 : } else if (in[j] == 'v') {
995 53 : to_parse.emplace_back(ParseContext::VERIFY, -1, -1);
996 109 : } else if (in[j] == 'u') {
997 12 : to_parse.emplace_back(ParseContext::WRAP_U, -1, -1);
998 56 : } else if (in[j] == 't') {
999 22 : to_parse.emplace_back(ParseContext::WRAP_T, -1, -1);
1000 44 : } else if (in[j] == 'l') {
1001 : // The l: wrapper is equivalent to or_i(0,X)
1002 22 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::JUST_0));
1003 22 : to_parse.emplace_back(ParseContext::OR_I, -1, -1);
1004 22 : } else {
1005 0 : return {};
1006 : }
1007 213 : }
1008 358 : to_parse.emplace_back(ParseContext::EXPR, -1, -1);
1009 358 : in = in.subspan(colon_index + 1);
1010 358 : break;
1011 : }
1012 : case ParseContext::EXPR: {
1013 358 : if (Const("0", in)) {
1014 28 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::JUST_0));
1015 358 : } else if (Const("1", in)) {
1016 56 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::JUST_1));
1017 330 : } else if (Const("pk(", in)) {
1018 9 : auto res = ParseKeyEnd<Key, Ctx>(in, ctx);
1019 9 : if (!res) return {};
1020 27 : auto& [key, key_size] = *res;
1021 18 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::WRAP_C, Vector(MakeNodeRef<Key>(ctx, Fragment::PK_K, Vector(std::move(key))))));
1022 9 : in = in.subspan(key_size + 1);
1023 274 : } else if (Const("pkh(", in)) {
1024 2 : auto res = ParseKeyEnd<Key>(in, ctx);
1025 2 : if (!res) return {};
1026 6 : auto& [key, key_size] = *res;
1027 4 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::WRAP_C, Vector(MakeNodeRef<Key>(ctx, Fragment::PK_H, Vector(std::move(key))))));
1028 2 : in = in.subspan(key_size + 1);
1029 265 : } else if (Const("pk_k(", in)) {
1030 29 : auto res = ParseKeyEnd<Key>(in, ctx);
1031 29 : if (!res) return {};
1032 87 : auto& [key, key_size] = *res;
1033 58 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::PK_K, Vector(std::move(key))));
1034 29 : in = in.subspan(key_size + 1);
1035 263 : } else if (Const("pk_h(", in)) {
1036 13 : auto res = ParseKeyEnd<Key>(in, ctx);
1037 13 : if (!res) return {};
1038 39 : auto& [key, key_size] = *res;
1039 26 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::PK_H, Vector(std::move(key))));
1040 13 : in = in.subspan(key_size + 1);
1041 234 : } else if (Const("sha256(", in)) {
1042 12 : auto res = ParseHexStrEnd(in, 32, ctx);
1043 12 : if (!res) return {};
1044 36 : auto& [hash, hash_size] = *res;
1045 24 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::SHA256, std::move(hash)));
1046 12 : in = in.subspan(hash_size + 1);
1047 221 : } else if (Const("ripemd160(", in)) {
1048 4 : auto res = ParseHexStrEnd(in, 20, ctx);
1049 4 : if (!res) return {};
1050 12 : auto& [hash, hash_size] = *res;
1051 8 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::RIPEMD160, std::move(hash)));
1052 4 : in = in.subspan(hash_size + 1);
1053 209 : } else if (Const("hash256(", in)) {
1054 7 : auto res = ParseHexStrEnd(in, 32, ctx);
1055 7 : if (!res) return {};
1056 21 : auto& [hash, hash_size] = *res;
1057 14 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::HASH256, std::move(hash)));
1058 7 : in = in.subspan(hash_size + 1);
1059 205 : } else if (Const("hash160(", in)) {
1060 3 : auto res = ParseHexStrEnd(in, 20, ctx);
1061 3 : if (!res) return {};
1062 9 : auto& [hash, hash_size] = *res;
1063 6 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::HASH160, std::move(hash)));
1064 3 : in = in.subspan(hash_size + 1);
1065 198 : } else if (Const("after(", in)) {
1066 38 : int arg_size = FindNextChar(in, ')');
1067 38 : if (arg_size < 1) return {};
1068 : int64_t num;
1069 38 : if (!ParseInt64(std::string(in.begin(), in.begin() + arg_size), &num)) return {};
1070 38 : if (num < 1 || num >= 0x80000000L) return {};
1071 36 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::AFTER, num));
1072 36 : in = in.subspan(arg_size + 1);
1073 193 : } else if (Const("older(", in)) {
1074 27 : int arg_size = FindNextChar(in, ')');
1075 27 : if (arg_size < 1) return {};
1076 : int64_t num;
1077 27 : if (!ParseInt64(std::string(in.begin(), in.begin() + arg_size), &num)) return {};
1078 27 : if (num < 1 || num >= 0x80000000L) return {};
1079 25 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::OLDER, num));
1080 25 : in = in.subspan(arg_size + 1);
1081 155 : } else if (Const("multi(", in)) {
1082 : // Get threshold
1083 13 : int next_comma = FindNextChar(in, ',');
1084 13 : if (next_comma < 1) return {};
1085 13 : if (!ParseInt64(std::string(in.begin(), in.begin() + next_comma), &k)) return {};
1086 13 : in = in.subspan(next_comma + 1);
1087 : // Get keys
1088 13 : std::vector<Key> keys;
1089 39 : while (next_comma != -1) {
1090 26 : next_comma = FindNextChar(in, ',');
1091 26 : int key_length = (next_comma == -1) ? FindNextChar(in, ')') : next_comma;
1092 26 : if (key_length < 1) return {};
1093 26 : auto key = ctx.FromString(in.begin(), in.begin() + key_length);
1094 26 : if (!key) return {};
1095 26 : keys.push_back(std::move(*key));
1096 26 : in = in.subspan(key_length + 1);
1097 : }
1098 13 : if (keys.size() < 1 || keys.size() > 20) return {};
1099 13 : if (k < 1 || k > (int64_t)keys.size()) return {};
1100 26 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::MULTI, std::move(keys), k));
1101 130 : } else if (Const("thresh(", in)) {
1102 12 : int next_comma = FindNextChar(in, ',');
1103 12 : if (next_comma < 1) return {};
1104 12 : if (!ParseInt64(std::string(in.begin(), in.begin() + next_comma), &k)) return {};
1105 12 : if (k < 1) return {};
1106 11 : in = in.subspan(next_comma + 1);
1107 : // n = 1 here because we read the first WRAPPED_EXPR before reaching THRESH
1108 22 : to_parse.emplace_back(ParseContext::THRESH, 1, k);
1109 11 : to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1110 116 : } else if (Const("andor(", in)) {
1111 15 : to_parse.emplace_back(ParseContext::ANDOR, -1, -1);
1112 15 : to_parse.emplace_back(ParseContext::CLOSE_BRACKET, -1, -1);
1113 15 : to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1114 15 : to_parse.emplace_back(ParseContext::COMMA, -1, -1);
1115 15 : to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1116 15 : to_parse.emplace_back(ParseContext::COMMA, -1, -1);
1117 15 : to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1118 15 : } else {
1119 90 : if (Const("and_n(", in)) {
1120 4 : to_parse.emplace_back(ParseContext::AND_N, -1, -1);
1121 90 : } else if (Const("and_b(", in)) {
1122 15 : to_parse.emplace_back(ParseContext::AND_B, -1, -1);
1123 86 : } else if (Const("and_v(", in)) {
1124 21 : to_parse.emplace_back(ParseContext::AND_V, -1, -1);
1125 71 : } else if (Const("or_b(", in)) {
1126 12 : to_parse.emplace_back(ParseContext::OR_B, -1, -1);
1127 50 : } else if (Const("or_c(", in)) {
1128 8 : to_parse.emplace_back(ParseContext::OR_C, -1, -1);
1129 38 : } else if (Const("or_d(", in)) {
1130 12 : to_parse.emplace_back(ParseContext::OR_D, -1, -1);
1131 30 : } else if (Const("or_i(", in)) {
1132 18 : to_parse.emplace_back(ParseContext::OR_I, -1, -1);
1133 18 : } else {
1134 0 : return {};
1135 : }
1136 90 : to_parse.emplace_back(ParseContext::CLOSE_BRACKET, -1, -1);
1137 90 : to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1138 90 : to_parse.emplace_back(ParseContext::COMMA, -1, -1);
1139 90 : to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1140 : }
1141 353 : break;
1142 : }
1143 : case ParseContext::ALT: {
1144 43 : constructed.back() = MakeNodeRef<Key>(ctx, Fragment::WRAP_A, Vector(std::move(constructed.back())));
1145 43 : break;
1146 : }
1147 : case ParseContext::SWAP: {
1148 13 : constructed.back() = MakeNodeRef<Key>(ctx, Fragment::WRAP_S, Vector(std::move(constructed.back())));
1149 13 : break;
1150 : }
1151 : case ParseContext::CHECK: {
1152 31 : constructed.back() = MakeNodeRef<Key>(ctx, Fragment::WRAP_C, Vector(std::move(constructed.back())));
1153 31 : break;
1154 : }
1155 : case ParseContext::DUP_IF: {
1156 4 : constructed.back() = MakeNodeRef<Key>(ctx, Fragment::WRAP_D, Vector(std::move(constructed.back())));
1157 4 : break;
1158 : }
1159 : case ParseContext::NON_ZERO: {
1160 5 : constructed.back() = MakeNodeRef<Key>(ctx, Fragment::WRAP_J, Vector(std::move(constructed.back())));
1161 5 : break;
1162 : }
1163 : case ParseContext::ZERO_NOTEQUAL: {
1164 8 : constructed.back() = MakeNodeRef<Key>(ctx, Fragment::WRAP_N, Vector(std::move(constructed.back())));
1165 8 : break;
1166 : }
1167 : case ParseContext::VERIFY: {
1168 53 : constructed.back() = MakeNodeRef<Key>(ctx, Fragment::WRAP_V, Vector(std::move(constructed.back())));
1169 53 : break;
1170 : }
1171 : case ParseContext::WRAP_U: {
1172 10 : constructed.back() = MakeNodeRef<Key>(ctx, Fragment::OR_I, Vector(std::move(constructed.back()), MakeNodeRef<Key>(ctx, Fragment::JUST_0)));
1173 10 : break;
1174 : }
1175 : case ParseContext::WRAP_T: {
1176 22 : constructed.back() = MakeNodeRef<Key>(ctx, Fragment::AND_V, Vector(std::move(constructed.back()), MakeNodeRef<Key>(ctx, Fragment::JUST_1)));
1177 22 : break;
1178 : }
1179 : case ParseContext::AND_B: {
1180 15 : BuildBack(ctx, Fragment::AND_B, constructed);
1181 15 : break;
1182 : }
1183 : case ParseContext::AND_N: {
1184 4 : auto mid = std::move(constructed.back());
1185 4 : constructed.pop_back();
1186 4 : constructed.back() = MakeNodeRef<Key>(ctx, Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), MakeNodeRef<Key>(ctx, Fragment::JUST_0)));
1187 : break;
1188 4 : }
1189 : case ParseContext::AND_V: {
1190 21 : BuildBack(ctx, Fragment::AND_V, constructed);
1191 21 : break;
1192 : }
1193 : case ParseContext::OR_B: {
1194 12 : BuildBack(ctx, Fragment::OR_B, constructed);
1195 12 : break;
1196 : }
1197 : case ParseContext::OR_C: {
1198 8 : BuildBack(ctx, Fragment::OR_C, constructed);
1199 8 : break;
1200 : }
1201 : case ParseContext::OR_D: {
1202 12 : BuildBack(ctx, Fragment::OR_D, constructed);
1203 12 : break;
1204 : }
1205 : case ParseContext::OR_I: {
1206 38 : BuildBack(ctx, Fragment::OR_I, constructed);
1207 38 : break;
1208 : }
1209 : case ParseContext::ANDOR: {
1210 15 : auto right = std::move(constructed.back());
1211 15 : constructed.pop_back();
1212 15 : auto mid = std::move(constructed.back());
1213 15 : constructed.pop_back();
1214 15 : constructed.back() = MakeNodeRef<Key>(ctx, Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), std::move(right)));
1215 : break;
1216 15 : }
1217 : case ParseContext::THRESH: {
1218 32 : if (in.size() < 1) return {};
1219 32 : if (in[0] == ',') {
1220 21 : in = in.subspan(1);
1221 63 : to_parse.emplace_back(ParseContext::THRESH, n+1, k);
1222 21 : to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1223 32 : } else if (in[0] == ')') {
1224 22 : if (k > n) return {};
1225 10 : in = in.subspan(1);
1226 : // Children are constructed in reverse order, so iterate from end to beginning
1227 10 : std::vector<NodeRef<Key>> subs;
1228 40 : for (int i = 0; i < n; ++i) {
1229 30 : subs.push_back(std::move(constructed.back()));
1230 30 : constructed.pop_back();
1231 30 : }
1232 10 : std::reverse(subs.begin(), subs.end());
1233 20 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::THRESH, std::move(subs), k));
1234 10 : } else {
1235 0 : return {};
1236 : }
1237 31 : break;
1238 : }
1239 : case ParseContext::COMMA: {
1240 120 : if (in.size() < 1 || in[0] != ',') return {};
1241 120 : in = in.subspan(1);
1242 120 : break;
1243 : }
1244 : case ParseContext::CLOSE_BRACKET: {
1245 105 : if (in.size() < 1 || in[0] != ')') return {};
1246 105 : in = in.subspan(1);
1247 105 : break;
1248 : }
1249 : }
1250 : }
1251 :
1252 : // Sanity checks on the produced miniscript
1253 95 : assert(constructed.size() == 1);
1254 95 : if (in.size() > 0) return {};
1255 95 : const NodeRef<Key> tl_node = std::move(constructed.front());
1256 95 : if (!tl_node->IsValidTopLevel()) return {};
1257 68 : return tl_node;
1258 101 : }
1259 :
1260 : /** Decode a script into opcode/push pairs.
1261 : *
1262 : * Construct a vector with one element per opcode in the script, in reverse order.
1263 : * Each element is a pair consisting of the opcode, as well as the data pushed by
1264 : * the opcode (including OP_n), if any. OP_CHECKSIGVERIFY, OP_CHECKMULTISIGVERIFY,
1265 : * and OP_EQUALVERIFY are decomposed into OP_CHECKSIG, OP_CHECKMULTISIG, OP_EQUAL
1266 : * respectively, plus OP_VERIFY.
1267 : */
1268 : std::optional<std::vector<Opcode>> DecomposeScript(const CScript& script);
1269 :
1270 : /** Determine whether the passed pair (created by DecomposeScript) is pushing a number. */
1271 : std::optional<int64_t> ParseScriptNumber(const Opcode& in);
1272 :
1273 : enum class DecodeContext {
1274 : /** A single expression of type B, K, or V. Specifically, this can't be an
1275 : * and_v or an expression of type W (a: and s: wrappers). */
1276 : SINGLE_BKV_EXPR,
1277 : /** Potentially multiple SINGLE_BKV_EXPRs as children of (potentially multiple)
1278 : * and_v expressions. Syntactic sugar for MAYBE_AND_V + SINGLE_BKV_EXPR. */
1279 : BKV_EXPR,
1280 : /** An expression of type W (a: or s: wrappers). */
1281 : W_EXPR,
1282 :
1283 : /** SWAP expects the next element to be OP_SWAP (inside a W-type expression that
1284 : * didn't end with FROMALTSTACK), and wraps the top of the constructed stack
1285 : * with s: */
1286 : SWAP,
1287 : /** ALT expects the next element to be TOALTSTACK (we must have already read a
1288 : * FROMALTSTACK earlier), and wraps the top of the constructed stack with a: */
1289 : ALT,
1290 : /** CHECK wraps the top constructed node with c: */
1291 : CHECK,
1292 : /** DUP_IF wraps the top constructed node with d: */
1293 : DUP_IF,
1294 : /** VERIFY wraps the top constructed node with v: */
1295 : VERIFY,
1296 : /** NON_ZERO wraps the top constructed node with j: */
1297 : NON_ZERO,
1298 : /** ZERO_NOTEQUAL wraps the top constructed node with n: */
1299 : ZERO_NOTEQUAL,
1300 :
1301 : /** MAYBE_AND_V will check if the next part of the script could be a valid
1302 : * miniscript sub-expression, and if so it will push AND_V and SINGLE_BKV_EXPR
1303 : * to decode it and construct the and_v node. This is recursive, to deal with
1304 : * multiple and_v nodes inside each other. */
1305 : MAYBE_AND_V,
1306 : /** AND_V will construct an and_v node from the last two constructed nodes. */
1307 : AND_V,
1308 : /** AND_B will construct an and_b node from the last two constructed nodes. */
1309 : AND_B,
1310 : /** ANDOR will construct an andor node from the last three constructed nodes. */
1311 : ANDOR,
1312 : /** OR_B will construct an or_b node from the last two constructed nodes. */
1313 : OR_B,
1314 : /** OR_C will construct an or_c node from the last two constructed nodes. */
1315 : OR_C,
1316 : /** OR_D will construct an or_d node from the last two constructed nodes. */
1317 : OR_D,
1318 :
1319 : /** In a thresh expression, all sub-expressions other than the first are W-type,
1320 : * and end in OP_ADD. THRESH_W will check for this OP_ADD and either push a W_EXPR
1321 : * or a SINGLE_BKV_EXPR and jump to THRESH_E accordingly. */
1322 : THRESH_W,
1323 : /** THRESH_E constructs a thresh node from the appropriate number of constructed
1324 : * children. */
1325 : THRESH_E,
1326 :
1327 : /** ENDIF signals that we are inside some sort of OP_IF structure, which could be
1328 : * or_d, or_c, or_i, andor, d:, or j: wrapper, depending on what follows. We read
1329 : * a BKV_EXPR and then deal with the next opcode case-by-case. */
1330 : ENDIF,
1331 : /** If, inside an ENDIF context, we find an OP_NOTIF before finding an OP_ELSE,
1332 : * we could either be in an or_d or an or_c node. We then check for IFDUP to
1333 : * distinguish these cases. */
1334 : ENDIF_NOTIF,
1335 : /** If, inside an ENDIF context, we find an OP_ELSE, then we could be in either an
1336 : * or_i or an andor node. Read the next BKV_EXPR and find either an OP_IF or an
1337 : * OP_NOTIF. */
1338 : ENDIF_ELSE,
1339 : };
1340 :
1341 : //! Parse a miniscript from a bitcoin script
1342 : template<typename Key, typename Ctx, typename I>
1343 63 : inline NodeRef<Key> DecodeScript(I& in, I last, const Ctx& ctx)
1344 : {
1345 : // The two integers are used to hold state for thresh()
1346 63 : std::vector<std::tuple<DecodeContext, int64_t, int64_t>> to_parse;
1347 63 : std::vector<NodeRef<Key>> constructed;
1348 :
1349 : // This is the top level, so we assume the type is B
1350 : // (in particular, disallowing top level W expressions)
1351 63 : to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
1352 :
1353 1366 : while (!to_parse.empty()) {
1354 : // Exit early if the Miniscript is not going to be valid.
1355 1303 : if (!constructed.empty() && !constructed.back()->IsValid()) return {};
1356 :
1357 : // Get the current context we are decoding within
1358 1380 : auto [cur_context, n, k] = to_parse.back();
1359 1303 : to_parse.pop_back();
1360 :
1361 1303 : switch(cur_context) {
1362 : case DecodeContext::SINGLE_BKV_EXPR: {
1363 387 : if (in >= last) return {};
1364 :
1365 : // Constants
1366 387 : if (in[0].first == OP_1) {
1367 39 : ++in;
1368 39 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::JUST_1));
1369 39 : break;
1370 : }
1371 348 : if (in[0].first == OP_0) {
1372 44 : ++in;
1373 44 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::JUST_0));
1374 44 : break;
1375 : }
1376 : // Public keys
1377 304 : if (in[0].second.size() == 33) {
1378 22 : auto key = ctx.FromPKBytes(in[0].second.begin(), in[0].second.end());
1379 22 : if (!key) return {};
1380 22 : ++in;
1381 22 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::PK_K, Vector(std::move(*key))));
1382 22 : break;
1383 : }
1384 282 : 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) {
1385 13 : auto key = ctx.FromPKHBytes(in[2].second.begin(), in[2].second.end());
1386 13 : if (!key) return {};
1387 13 : in += 5;
1388 13 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::PK_H, Vector(std::move(*key))));
1389 13 : break;
1390 : }
1391 : // Time locks
1392 269 : std::optional<int64_t> num;
1393 269 : if (last - in >= 2 && in[0].first == OP_CHECKSEQUENCEVERIFY && (num = ParseScriptNumber(in[1]))) {
1394 22 : in += 2;
1395 22 : if (*num < 1 || *num > 0x7FFFFFFFL) return {};
1396 22 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::OLDER, *num));
1397 22 : break;
1398 : }
1399 247 : if (last - in >= 2 && in[0].first == OP_CHECKLOCKTIMEVERIFY && (num = ParseScriptNumber(in[1]))) {
1400 33 : in += 2;
1401 33 : if (num < 1 || num > 0x7FFFFFFFL) return {};
1402 33 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::AFTER, *num));
1403 33 : break;
1404 : }
1405 : // Hashes
1406 214 : 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) {
1407 26 : if (in[2].first == OP_SHA256 && in[1].second.size() == 32) {
1408 12 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::SHA256, in[1].second));
1409 12 : in += 7;
1410 12 : break;
1411 14 : } else if (in[2].first == OP_RIPEMD160 && in[1].second.size() == 20) {
1412 4 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::RIPEMD160, in[1].second));
1413 4 : in += 7;
1414 4 : break;
1415 10 : } else if (in[2].first == OP_HASH256 && in[1].second.size() == 32) {
1416 7 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::HASH256, in[1].second));
1417 7 : in += 7;
1418 7 : break;
1419 3 : } else if (in[2].first == OP_HASH160 && in[1].second.size() == 20) {
1420 3 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::HASH160, in[1].second));
1421 3 : in += 7;
1422 3 : break;
1423 : }
1424 0 : }
1425 : // Multi
1426 188 : if (last - in >= 3 && in[0].first == OP_CHECKMULTISIG) {
1427 12 : std::vector<Key> keys;
1428 12 : const auto n = ParseScriptNumber(in[1]);
1429 12 : if (!n || last - in < 3 + *n) return {};
1430 12 : if (*n < 1 || *n > 20) return {};
1431 35 : for (int i = 0; i < *n; ++i) {
1432 23 : if (in[2 + i].second.size() != 33) return {};
1433 23 : auto key = ctx.FromPKBytes(in[2 + i].second.begin(), in[2 + i].second.end());
1434 23 : if (!key) return {};
1435 23 : keys.push_back(std::move(*key));
1436 23 : }
1437 12 : const auto k = ParseScriptNumber(in[2 + *n]);
1438 12 : if (!k || *k < 1 || *k > *n) return {};
1439 12 : in += 3 + *n;
1440 12 : std::reverse(keys.begin(), keys.end());
1441 12 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::MULTI, std::move(keys), *k));
1442 12 : break;
1443 12 : }
1444 : /** In the following wrappers, we only need to push SINGLE_BKV_EXPR rather
1445 : * than BKV_EXPR, because and_v commutes with these wrappers. For example,
1446 : * c:and_v(X,Y) produces the same script as and_v(X,c:Y). */
1447 : // c: wrapper
1448 176 : if (in[0].first == OP_CHECKSIG) {
1449 27 : ++in;
1450 27 : to_parse.emplace_back(DecodeContext::CHECK, -1, -1);
1451 27 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
1452 27 : break;
1453 : }
1454 : // v: wrapper
1455 149 : if (in[0].first == OP_VERIFY) {
1456 43 : ++in;
1457 43 : to_parse.emplace_back(DecodeContext::VERIFY, -1, -1);
1458 43 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
1459 43 : break;
1460 : }
1461 : // n: wrapper
1462 106 : if (in[0].first == OP_0NOTEQUAL) {
1463 8 : ++in;
1464 8 : to_parse.emplace_back(DecodeContext::ZERO_NOTEQUAL, -1, -1);
1465 8 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
1466 8 : break;
1467 : }
1468 : // Thresh
1469 98 : if (last - in >= 3 && in[0].first == OP_EQUAL && (num = ParseScriptNumber(in[1]))) {
1470 8 : if (*num < 1) return {};
1471 8 : in += 2;
1472 8 : to_parse.emplace_back(DecodeContext::THRESH_W, 0, *num);
1473 8 : break;
1474 : }
1475 : // OP_ENDIF can be WRAP_J, WRAP_D, ANDOR, OR_C, OR_D, or OR_I
1476 90 : if (in[0].first == OP_ENDIF) {
1477 77 : ++in;
1478 77 : to_parse.emplace_back(DecodeContext::ENDIF, -1, -1);
1479 77 : to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
1480 77 : break;
1481 : }
1482 : /** In and_b and or_b nodes, we only look for SINGLE_BKV_EXPR, because
1483 : * or_b(and_v(X,Y),Z) has script [X] [Y] [Z] OP_BOOLOR, the same as
1484 : * and_v(X,or_b(Y,Z)). In this example, the former of these is invalid as
1485 : * miniscript, while the latter is valid. So we leave the and_v "outside"
1486 : * while decoding. */
1487 : // and_b
1488 13 : if (in[0].first == OP_BOOLAND) {
1489 8 : ++in;
1490 8 : to_parse.emplace_back(DecodeContext::AND_B, -1, -1);
1491 8 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
1492 8 : to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
1493 8 : break;
1494 : }
1495 : // or_b
1496 5 : if (in[0].first == OP_BOOLOR) {
1497 5 : ++in;
1498 5 : to_parse.emplace_back(DecodeContext::OR_B, -1, -1);
1499 5 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
1500 5 : to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
1501 5 : break;
1502 : }
1503 : // Unrecognised expression
1504 0 : return {};
1505 : }
1506 : case DecodeContext::BKV_EXPR: {
1507 261 : to_parse.emplace_back(DecodeContext::MAYBE_AND_V, -1, -1);
1508 261 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
1509 261 : break;
1510 : }
1511 : case DecodeContext::W_EXPR: {
1512 : // a: wrapper
1513 28 : if (in >= last) return {};
1514 28 : if (in[0].first == OP_FROMALTSTACK) {
1515 23 : ++in;
1516 23 : to_parse.emplace_back(DecodeContext::ALT, -1, -1);
1517 23 : } else {
1518 5 : to_parse.emplace_back(DecodeContext::SWAP, -1, -1);
1519 : }
1520 28 : to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
1521 28 : break;
1522 : }
1523 : case DecodeContext::MAYBE_AND_V: {
1524 : // If we reach a potential AND_V top-level, check if the next part of the script could be another AND_V child
1525 : // These op-codes cannot end any well-formed miniscript so cannot be used in an and_v node.
1526 261 : 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) {
1527 35 : to_parse.emplace_back(DecodeContext::AND_V, -1, -1);
1528 : // BKV_EXPR can contain more AND_V nodes
1529 35 : to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
1530 35 : }
1531 261 : break;
1532 : }
1533 : case DecodeContext::SWAP: {
1534 5 : if (in >= last || in[0].first != OP_SWAP || constructed.empty()) return {};
1535 5 : ++in;
1536 5 : constructed.back() = MakeNodeRef<Key>(ctx, Fragment::WRAP_S, Vector(std::move(constructed.back())));
1537 5 : break;
1538 : }
1539 : case DecodeContext::ALT: {
1540 23 : if (in >= last || in[0].first != OP_TOALTSTACK || constructed.empty()) return {};
1541 23 : ++in;
1542 23 : constructed.back() = MakeNodeRef<Key>(ctx, Fragment::WRAP_A, Vector(std::move(constructed.back())));
1543 23 : break;
1544 : }
1545 : case DecodeContext::CHECK: {
1546 27 : if (constructed.empty()) return {};
1547 27 : constructed.back() = MakeNodeRef<Key>(ctx, Fragment::WRAP_C, Vector(std::move(constructed.back())));
1548 27 : break;
1549 : }
1550 : case DecodeContext::DUP_IF: {
1551 2 : if (constructed.empty()) return {};
1552 2 : constructed.back() = MakeNodeRef<Key>(ctx, Fragment::WRAP_D, Vector(std::move(constructed.back())));
1553 2 : break;
1554 : }
1555 : case DecodeContext::VERIFY: {
1556 43 : if (constructed.empty()) return {};
1557 43 : constructed.back() = MakeNodeRef<Key>(ctx, Fragment::WRAP_V, Vector(std::move(constructed.back())));
1558 43 : break;
1559 : }
1560 : case DecodeContext::NON_ZERO: {
1561 5 : if (constructed.empty()) return {};
1562 5 : constructed.back() = MakeNodeRef<Key>(ctx, Fragment::WRAP_J, Vector(std::move(constructed.back())));
1563 5 : break;
1564 : }
1565 : case DecodeContext::ZERO_NOTEQUAL: {
1566 8 : if (constructed.empty()) return {};
1567 8 : constructed.back() = MakeNodeRef<Key>(ctx, Fragment::WRAP_N, Vector(std::move(constructed.back())));
1568 8 : break;
1569 : }
1570 : case DecodeContext::AND_V: {
1571 35 : if (constructed.size() < 2) return {};
1572 35 : BuildBack(ctx, Fragment::AND_V, constructed, /*reverse=*/true);
1573 35 : break;
1574 : }
1575 : case DecodeContext::AND_B: {
1576 8 : if (constructed.size() < 2) return {};
1577 8 : BuildBack(ctx, Fragment::AND_B, constructed, /*reverse=*/true);
1578 8 : break;
1579 : }
1580 : case DecodeContext::OR_B: {
1581 5 : if (constructed.size() < 2) return {};
1582 5 : BuildBack(ctx, Fragment::OR_B, constructed, /*reverse=*/true);
1583 5 : break;
1584 : }
1585 : case DecodeContext::OR_C: {
1586 4 : if (constructed.size() < 2) return {};
1587 4 : BuildBack(ctx, Fragment::OR_C, constructed, /*reverse=*/true);
1588 4 : break;
1589 : }
1590 : case DecodeContext::OR_D: {
1591 8 : if (constructed.size() < 2) return {};
1592 8 : BuildBack(ctx, Fragment::OR_D, constructed, /*reverse=*/true);
1593 8 : break;
1594 : }
1595 : case DecodeContext::ANDOR: {
1596 15 : if (constructed.size() < 3) return {};
1597 15 : NodeRef<Key> left = std::move(constructed.back());
1598 15 : constructed.pop_back();
1599 15 : NodeRef<Key> right = std::move(constructed.back());
1600 15 : constructed.pop_back();
1601 15 : NodeRef<Key> mid = std::move(constructed.back());
1602 15 : constructed.back() = MakeNodeRef<Key>(ctx, Fragment::ANDOR, Vector(std::move(left), std::move(mid), std::move(right)));
1603 : break;
1604 15 : }
1605 : case DecodeContext::THRESH_W: {
1606 23 : if (in >= last) return {};
1607 23 : if (in[0].first == OP_ADD) {
1608 15 : ++in;
1609 45 : to_parse.emplace_back(DecodeContext::THRESH_W, n+1, k);
1610 15 : to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
1611 15 : } else {
1612 24 : to_parse.emplace_back(DecodeContext::THRESH_E, n+1, k);
1613 : // All children of thresh have type modifier d, so cannot be and_v
1614 8 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
1615 : }
1616 23 : break;
1617 : }
1618 : case DecodeContext::THRESH_E: {
1619 8 : if (k < 1 || k > n || constructed.size() < static_cast<size_t>(n)) return {};
1620 8 : std::vector<NodeRef<Key>> subs;
1621 31 : for (int i = 0; i < n; ++i) {
1622 23 : NodeRef<Key> sub = std::move(constructed.back());
1623 23 : constructed.pop_back();
1624 23 : subs.push_back(std::move(sub));
1625 23 : }
1626 16 : constructed.push_back(MakeNodeRef<Key>(ctx, Fragment::THRESH, std::move(subs), k));
1627 : break;
1628 8 : }
1629 : case DecodeContext::ENDIF: {
1630 77 : if (in >= last) return {};
1631 :
1632 : // could be andor or or_i
1633 77 : if (in[0].first == OP_ELSE) {
1634 58 : ++in;
1635 58 : to_parse.emplace_back(DecodeContext::ENDIF_ELSE, -1, -1);
1636 58 : to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
1637 58 : }
1638 : // could be j: or d: wrapper
1639 19 : else if (in[0].first == OP_IF) {
1640 7 : if (last - in >= 2 && in[1].first == OP_DUP) {
1641 2 : in += 2;
1642 2 : to_parse.emplace_back(DecodeContext::DUP_IF, -1, -1);
1643 7 : } else if (last - in >= 3 && in[1].first == OP_0NOTEQUAL && in[2].first == OP_SIZE) {
1644 5 : in += 3;
1645 5 : to_parse.emplace_back(DecodeContext::NON_ZERO, -1, -1);
1646 5 : }
1647 : else {
1648 0 : return {};
1649 : }
1650 : // could be or_c or or_d
1651 19 : } else if (in[0].first == OP_NOTIF) {
1652 12 : ++in;
1653 12 : to_parse.emplace_back(DecodeContext::ENDIF_NOTIF, -1, -1);
1654 12 : }
1655 : else {
1656 0 : return {};
1657 : }
1658 77 : break;
1659 : }
1660 : case DecodeContext::ENDIF_NOTIF: {
1661 12 : if (in >= last) return {};
1662 12 : if (in[0].first == OP_IFDUP) {
1663 8 : ++in;
1664 8 : to_parse.emplace_back(DecodeContext::OR_D, -1, -1);
1665 8 : } else {
1666 4 : to_parse.emplace_back(DecodeContext::OR_C, -1, -1);
1667 : }
1668 : // or_c and or_d both require X to have type modifier d so, can't contain and_v
1669 12 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
1670 12 : break;
1671 : }
1672 : case DecodeContext::ENDIF_ELSE: {
1673 58 : if (in >= last) return {};
1674 58 : if (in[0].first == OP_IF) {
1675 43 : ++in;
1676 43 : BuildBack(ctx, Fragment::OR_I, constructed, /*reverse=*/true);
1677 58 : } else if (in[0].first == OP_NOTIF) {
1678 15 : ++in;
1679 15 : to_parse.emplace_back(DecodeContext::ANDOR, -1, -1);
1680 : // andor requires X to have type modifier d, so it can't be and_v
1681 15 : to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
1682 15 : } else {
1683 0 : return {};
1684 : }
1685 58 : break;
1686 : }
1687 : }
1688 : }
1689 63 : if (constructed.size() != 1) return {};
1690 63 : const NodeRef<Key> tl_node = std::move(constructed.front());
1691 : // Note that due to how ComputeType works (only assign the type to the node if the
1692 : // subs' types are valid) this would fail if any node of tree is badly typed.
1693 63 : if (!tl_node->IsValidTopLevel()) return {};
1694 63 : return tl_node;
1695 63 : }
1696 :
1697 : } // namespace internal
1698 :
1699 : template<typename Ctx>
1700 101 : inline NodeRef<typename Ctx::Key> FromString(const std::string& str, const Ctx& ctx) {
1701 101 : return internal::Parse<typename Ctx::Key>(str, ctx);
1702 : }
1703 :
1704 : template<typename Ctx>
1705 65 : inline NodeRef<typename Ctx::Key> FromScript(const CScript& script, const Ctx& ctx) {
1706 : using namespace internal;
1707 65 : auto decomposed = DecomposeScript(script);
1708 65 : if (!decomposed) return {};
1709 63 : auto it = decomposed->begin();
1710 63 : auto ret = DecodeScript<typename Ctx::Key>(it, decomposed->end(), ctx);
1711 63 : if (!ret) return {};
1712 63 : if (it != decomposed->end()) return {};
1713 63 : return ret;
1714 65 : }
1715 :
1716 : } // namespace miniscript
1717 :
1718 : #endif // BITCOIN_SCRIPT_MINISCRIPT_H
|
