Bitcoin Core  25.99.0
P2P Digital Currency
miniscript.h
Go to the documentation of this file.
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 
121 class Type {
123  uint32_t m_flags;
124 
126  explicit constexpr Type(uint32_t flags) : m_flags(flags) {}
127 
128 public:
130  friend constexpr Type operator"" _mst(const char* c, size_t l);
131 
133  constexpr Type operator|(Type x) const { return Type(m_flags | x.m_flags); }
134 
136  constexpr Type operator&(Type x) const { return Type(m_flags & x.m_flags); }
137 
139  constexpr bool operator<<(Type x) const { return (x.m_flags & ~m_flags) == 0; }
140 
142  constexpr bool operator<(Type x) const { return m_flags < x.m_flags; }
143 
145  constexpr bool operator==(Type x) const { return m_flags == x.m_flags; }
146 
148  constexpr Type If(bool x) const { return Type(x ? m_flags : 0); }
149 };
150 
152 inline constexpr Type operator"" _mst(const char* c, size_t l) {
153  Type typ{0};
154 
155  for (const char *p = c; p < c + l; p++) {
156  typ = typ | Type(
157  *p == 'B' ? 1 << 0 : // Base type
158  *p == 'V' ? 1 << 1 : // Verify type
159  *p == 'K' ? 1 << 2 : // Key type
160  *p == 'W' ? 1 << 3 : // Wrapped type
161  *p == 'z' ? 1 << 4 : // Zero-arg property
162  *p == 'o' ? 1 << 5 : // One-arg property
163  *p == 'n' ? 1 << 6 : // Nonzero arg property
164  *p == 'd' ? 1 << 7 : // Dissatisfiable property
165  *p == 'u' ? 1 << 8 : // Unit property
166  *p == 'e' ? 1 << 9 : // Expression property
167  *p == 'f' ? 1 << 10 : // Forced property
168  *p == 's' ? 1 << 11 : // Safe property
169  *p == 'm' ? 1 << 12 : // Nonmalleable property
170  *p == 'x' ? 1 << 13 : // Expensive verify
171  *p == 'g' ? 1 << 14 : // older: contains relative time timelock (csv_time)
172  *p == 'h' ? 1 << 15 : // older: contains relative height timelock (csv_height)
173  *p == 'i' ? 1 << 16 : // after: contains time timelock (cltv_time)
174  *p == 'j' ? 1 << 17 : // after: contains height timelock (cltv_height)
175  *p == 'k' ? 1 << 18 : // does not contain a combination of height and time locks
176  (throw std::logic_error("Unknown character in _mst literal"), 0)
177  );
178  }
179 
180  return typ;
181 }
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 
189 template<typename Key, typename... Args>
190 NodeRef<Key> MakeNodeRef(Args&&... args) { return std::make_shared<const Node<Key>>(std::forward<Args>(args)...); }
191 
193 enum class Fragment {
194  JUST_0,
195  JUST_1,
196  PK_K,
197  PK_H,
198  OLDER,
199  AFTER,
200  SHA256,
201  HASH256,
202  RIPEMD160,
203  HASH160,
204  WRAP_A,
205  WRAP_S,
206  WRAP_C,
207  WRAP_D,
208  WRAP_V,
209  WRAP_J,
210  WRAP_N,
211  AND_V,
212  AND_B,
213  OR_B,
214  OR_C,
215  OR_D,
216  OR_I,
217  ANDOR,
218  THRESH,
219  MULTI,
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 
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 
238 size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs, size_t n_keys);
239 
241 Type SanitizeType(Type x);
242 
244 struct InputStack {
252  bool has_sig = false;
254  bool malleable = false;
257  bool non_canon = false;
259  size_t size = 0;
261  std::vector<std::vector<unsigned char>> stack;
265  InputStack(std::vector<unsigned char> in) : size(in.size() + 1), stack(Vector(std::move(in))) {}
273  InputStack& SetMalleable(bool x = true);
278 };
279 
281 static const auto ZERO = InputStack(std::vector<unsigned char>());
283 static const auto ZERO32 = InputStack(std::vector<unsigned char>(32, 0)).SetMalleable();
285 static const auto ONE = InputStack(Vector((unsigned char)1));
287 static const auto EMPTY = InputStack();
290 
292 struct InputResult {
294 
295  template<typename A, typename B>
296  InputResult(A&& in_nsat, B&& in_sat) : nsat(std::forward<A>(in_nsat)), sat(std::forward<B>(in_sat)) {}
297 };
298 
300 template<typename I>
301 struct MaxInt {
302  const bool valid;
303  const I value;
304 
305  MaxInt() : valid(false), value(0) {}
306  MaxInt(I val) : valid(true), value(val) {}
307 
308  friend MaxInt<I> operator+(const MaxInt<I>& a, const MaxInt<I>& b) {
309  if (!a.valid || !b.valid) return {};
310  return a.value + b.value;
311  }
312 
313  friend MaxInt<I> operator|(const MaxInt<I>& a, const MaxInt<I>& b) {
314  if (!a.valid) return b;
315  if (!b.valid) return a;
316  return std::max(a.value, b.value);
317  }
318 };
319 
320 struct Ops {
322  uint32_t count;
327 
328  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 {
336 
337  StackSize(MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : sat(in_sat), dsat(in_dsat) {};
338 };
339 
340 struct WitnessSize {
345 
346  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 
354 template<typename Key>
355 struct Node {
359  const uint32_t k = 0;
361  const std::vector<Key> keys;
363  const std::vector<unsigned char> data;
365  const std::vector<NodeRef<Key>> subs;
366 
367 private:
375  const Type typ;
377  const size_t scriptlen;
383  mutable std::optional<bool> has_duplicate_keys;
384 
385 
387  size_t CalcScriptLen() const {
388  size_t subsize = 0;
389  for (const auto& sub : subs) {
390  subsize += sub->ScriptSize();
391  }
392  Type sub0type = subs.size() > 0 ? subs[0]->GetType() : ""_mst;
393  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  std::optional<Result> TreeEvalMaybe(State root_state, DownFn downfn, UpFn upfn) const
421  {
423  struct StackElem
424  {
425  const Node& node;
426  size_t expanded;
427  State state;
428 
429  StackElem(const Node& node_, size_t exp_, State&& state_) :
430  node(node_), expanded(exp_), state(std::move(state_)) {}
431  };
432  /* Stack of tree nodes being explored. */
433  std::vector<StackElem> stack;
434  /* Results of subtrees so far. Their order and mapping to tree nodes
435  * is implicitly defined by stack. */
436  std::vector<Result> results;
437  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  while (stack.size()) {
456  const Node& node = stack.back().node;
457  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  size_t child_index = stack.back().expanded++;
462  State child_state = downfn(stack.back().state, node, child_index);
463  stack.emplace_back(*node.subs[child_index], 0, std::move(child_state));
464  continue;
465  }
466  // Invoke upfn with the last node.subs.size() elements of results as input.
467  assert(results.size() >= node.subs.size());
468  std::optional<Result> result{upfn(std::move(stack.back().state), node,
469  Span<Result>{results}.last(node.subs.size()))};
470  // If evaluation returns std::nullopt, abort immediately.
471  if (!result) return {};
472  // Replace the last node.subs.size() elements of results with the new result.
473  results.erase(results.end() - node.subs.size(), results.end());
474  results.push_back(std::move(*result));
475  stack.pop_back();
476  }
477  // The final remaining results element is the root result, return it.
478  assert(results.size() == 1);
479  return std::move(results[0]);
480  }
481 
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 
497  template<typename Result, typename State, typename DownFn, typename UpFn>
498  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  return std::move(*TreeEvalMaybe<Result>(std::move(root_state),
503  std::forward<DownFn>(downfn),
504  [&upfn](State&& state, const Node& node, Span<Result> subs) {
505  Result res{upfn(std::move(state), node, subs)};
506  return std::optional<Result>(std::move(res));
507  }
508  ));
509  }
510 
513  template<typename Result, typename UpFn>
514  Result TreeEval(UpFn upfn) const
515  {
516  struct DummyState {};
517  return std::move(*TreeEvalMaybe<Result>(DummyState{},
518  [](DummyState, const Node&, size_t) { return DummyState{}; },
519  [&upfn](DummyState, const Node& node, Span<Result> subs) {
520  Result res{upfn(node, subs)};
521  return std::optional<Result>(std::move(res));
522  }
523  ));
524  }
525 
527  friend int Compare(const Node<Key>& node1, const Node<Key>& node2)
528  {
529  std::vector<std::pair<const Node<Key>&, const Node<Key>&>> queue;
530  queue.emplace_back(node1, node2);
531  while (!queue.empty()) {
532  const auto& [a, b] = queue.back();
533  queue.pop_back();
534  if (std::tie(a.fragment, a.k, a.keys, a.data) < std::tie(b.fragment, b.k, b.keys, b.data)) return -1;
535  if (std::tie(b.fragment, b.k, b.keys, b.data) < std::tie(a.fragment, a.k, a.keys, a.data)) return 1;
536  if (a.subs.size() < b.subs.size()) return -1;
537  if (b.subs.size() < a.subs.size()) return 1;
538  size_t n = a.subs.size();
539  for (size_t i = 0; i < n; ++i) {
540  queue.emplace_back(*a.subs[n - 1 - i], *b.subs[n - 1 - i]);
541  }
542  }
543  return 0;
544  }
545 
547  Type CalcType() const {
548  using namespace internal;
549 
550  // THRESH has a variable number of subexpressions
551  std::vector<Type> sub_types;
552  if (fragment == Fragment::THRESH) {
553  for (const auto& sub : subs) sub_types.push_back(sub->GetType());
554  }
555  // All other nodes than THRESH can be computed just from the types of the 0-3 subexpressions.
556  Type x = subs.size() > 0 ? subs[0]->GetType() : ""_mst;
557  Type y = subs.size() > 1 ? subs[1]->GetType() : ""_mst;
558  Type z = subs.size() > 2 ? subs[2]->GetType() : ""_mst;
559 
560  return SanitizeType(ComputeType(fragment, x, y, z, sub_types, k, data.size(), subs.size(), keys.size()));
561  }
562 
563 public:
564  template<typename Ctx>
565  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  auto downfn = [](bool verify, const Node& node, size_t index) {
571  // For WRAP_V, the subexpression is certainly followed by OP_VERIFY.
572  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  if (node.fragment == Fragment::WRAP_S ||
576  (node.fragment == Fragment::AND_V && index == 1)) return verify;
577  return false;
578  };
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  auto upfn = [&ctx](bool verify, const Node& node, Span<CScript> subs) -> CScript {
582  switch (node.fragment) {
583  case Fragment::PK_K: return BuildScript(ctx.ToPKBytes(node.keys[0]));
584  case Fragment::PK_H: return BuildScript(OP_DUP, OP_HASH160, ctx.ToPKHBytes(node.keys[0]), OP_EQUALVERIFY);
592  case Fragment::WRAP_S: return BuildScript(OP_SWAP, subs[0]);
593  case Fragment::WRAP_C: return BuildScript(std::move(subs[0]), verify ? OP_CHECKSIGVERIFY : OP_CHECKSIG);
595  case Fragment::WRAP_V: {
596  if (node.subs[0]->GetType() << "x"_mst) {
597  return BuildScript(std::move(subs[0]), OP_VERIFY);
598  } else {
599  return std::move(subs[0]);
600  }
601  }
603  case Fragment::WRAP_N: return BuildScript(std::move(subs[0]), OP_0NOTEQUAL);
604  case Fragment::JUST_1: return BuildScript(OP_1);
605  case Fragment::JUST_0: return BuildScript(OP_0);
606  case Fragment::AND_V: return BuildScript(std::move(subs[0]), subs[1]);
607  case Fragment::AND_B: return BuildScript(std::move(subs[0]), subs[1], OP_BOOLAND);
608  case Fragment::OR_B: return BuildScript(std::move(subs[0]), subs[1], OP_BOOLOR);
609  case Fragment::OR_D: return BuildScript(std::move(subs[0]), OP_IFDUP, OP_NOTIF, subs[1], OP_ENDIF);
610  case Fragment::OR_C: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[1], OP_ENDIF);
611  case Fragment::OR_I: return BuildScript(OP_IF, subs[0], OP_ELSE, subs[1], OP_ENDIF);
612  case Fragment::ANDOR: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[2], OP_ELSE, subs[1], OP_ENDIF);
613  case Fragment::MULTI: {
614  CScript script = BuildScript(node.k);
615  for (const auto& key : node.keys) {
616  script = BuildScript(std::move(script), ctx.ToPKBytes(key));
617  }
618  return BuildScript(std::move(script), node.keys.size(), verify ? OP_CHECKMULTISIGVERIFY : OP_CHECKMULTISIG);
619  }
620  case Fragment::THRESH: {
621  CScript script = std::move(subs[0]);
622  for (size_t i = 1; i < subs.size(); ++i) {
623  script = BuildScript(std::move(script), subs[i], OP_ADD);
624  }
625  return BuildScript(std::move(script), node.k, verify ? OP_EQUALVERIFY : OP_EQUAL);
626  }
627  }
628  assert(false);
629  };
630  return TreeEval<CScript>(false, downfn, upfn);
631  }
632 
633  template<typename CTx>
634  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  auto downfn = [](bool, const Node& node, size_t) {
639  return (node.fragment == Fragment::WRAP_A || node.fragment == Fragment::WRAP_S ||
640  node.fragment == Fragment::WRAP_D || node.fragment == Fragment::WRAP_V ||
641  node.fragment == Fragment::WRAP_J || node.fragment == Fragment::WRAP_N ||
642  node.fragment == Fragment::WRAP_C ||
643  (node.fragment == Fragment::AND_V && node.subs[1]->fragment == Fragment::JUST_1) ||
644  (node.fragment == Fragment::OR_I && node.subs[0]->fragment == Fragment::JUST_0) ||
645  (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  auto upfn = [&ctx](bool wrapped, const Node& node, Span<std::string> subs) -> std::optional<std::string> {
650  std::string ret = wrapped ? ":" : "";
651 
652  switch (node.fragment) {
653  case Fragment::WRAP_A: return "a" + std::move(subs[0]);
654  case Fragment::WRAP_S: return "s" + std::move(subs[0]);
655  case Fragment::WRAP_C:
656  if (node.subs[0]->fragment == Fragment::PK_K) {
657  // pk(K) is syntactic sugar for c:pk_k(K)
658  auto key_str = ctx.ToString(node.subs[0]->keys[0]);
659  if (!key_str) return {};
660  return std::move(ret) + "pk(" + std::move(*key_str) + ")";
661  }
662  if (node.subs[0]->fragment == Fragment::PK_H) {
663  // pkh(K) is syntactic sugar for c:pk_h(K)
664  auto key_str = ctx.ToString(node.subs[0]->keys[0]);
665  if (!key_str) return {};
666  return std::move(ret) + "pkh(" + std::move(*key_str) + ")";
667  }
668  return "c" + std::move(subs[0]);
669  case Fragment::WRAP_D: return "d" + std::move(subs[0]);
670  case Fragment::WRAP_V: return "v" + std::move(subs[0]);
671  case Fragment::WRAP_J: return "j" + std::move(subs[0]);
672  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  if (node.subs[1]->fragment == Fragment::JUST_1) return "t" + std::move(subs[0]);
676  break;
677  case Fragment::OR_I:
678  if (node.subs[0]->fragment == Fragment::JUST_0) return "l" + std::move(subs[1]);
679  if (node.subs[1]->fragment == Fragment::JUST_0) return "u" + std::move(subs[0]);
680  break;
681  default: break;
682  }
683  switch (node.fragment) {
684  case Fragment::PK_K: {
685  auto key_str = ctx.ToString(node.keys[0]);
686  if (!key_str) return {};
687  return std::move(ret) + "pk_k(" + std::move(*key_str) + ")";
688  }
689  case Fragment::PK_H: {
690  auto key_str = ctx.ToString(node.keys[0]);
691  if (!key_str) return {};
692  return std::move(ret) + "pk_h(" + std::move(*key_str) + ")";
693  }
694  case Fragment::AFTER: return std::move(ret) + "after(" + ::ToString(node.k) + ")";
695  case Fragment::OLDER: return std::move(ret) + "older(" + ::ToString(node.k) + ")";
696  case Fragment::HASH256: return std::move(ret) + "hash256(" + HexStr(node.data) + ")";
697  case Fragment::HASH160: return std::move(ret) + "hash160(" + HexStr(node.data) + ")";
698  case Fragment::SHA256: return std::move(ret) + "sha256(" + HexStr(node.data) + ")";
699  case Fragment::RIPEMD160: return std::move(ret) + "ripemd160(" + HexStr(node.data) + ")";
700  case Fragment::JUST_1: return std::move(ret) + "1";
701  case Fragment::JUST_0: return std::move(ret) + "0";
702  case Fragment::AND_V: return std::move(ret) + "and_v(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
703  case Fragment::AND_B: return std::move(ret) + "and_b(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
704  case Fragment::OR_B: return std::move(ret) + "or_b(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
705  case Fragment::OR_D: return std::move(ret) + "or_d(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
706  case Fragment::OR_C: return std::move(ret) + "or_c(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
707  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  if (node.subs[2]->fragment == Fragment::JUST_0) return std::move(ret) + "and_n(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
711  return std::move(ret) + "andor(" + std::move(subs[0]) + "," + std::move(subs[1]) + "," + std::move(subs[2]) + ")";
712  case Fragment::MULTI: {
713  auto str = std::move(ret) + "multi(" + ::ToString(node.k);
714  for (const auto& key : node.keys) {
715  auto key_str = ctx.ToString(key);
716  if (!key_str) return {};
717  str += "," + std::move(*key_str);
718  }
719  return std::move(str) + ")";
720  }
721  case Fragment::THRESH: {
722  auto str = std::move(ret) + "thresh(" + ::ToString(node.k);
723  for (auto& sub : subs) {
724  str += "," + std::move(sub);
725  }
726  return std::move(str) + ")";
727  }
728  default: break;
729  }
730  assert(false);
731  };
732 
733  return TreeEvalMaybe<std::string>(false, downfn, upfn);
734  }
735 
736 private:
738  switch (fragment) {
739  case Fragment::JUST_1: return {0, 0, {}};
740  case Fragment::JUST_0: return {0, {}, 0};
741  case Fragment::PK_K: return {0, 0, 0};
742  case Fragment::PK_H: return {3, 0, 0};
743  case Fragment::OLDER:
744  case Fragment::AFTER: return {1, 0, {}};
745  case Fragment::SHA256:
746  case Fragment::RIPEMD160:
747  case Fragment::HASH256:
748  case Fragment::HASH160: return {4, 0, {}};
749  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  const auto count{1 + subs[0]->ops.count + subs[1]->ops.count};
752  const auto sat{subs[0]->ops.sat + subs[1]->ops.sat};
753  const auto dsat{subs[0]->ops.dsat + subs[1]->ops.dsat};
754  return {count, sat, dsat};
755  }
756  case Fragment::OR_B: {
757  const auto count{1 + subs[0]->ops.count + subs[1]->ops.count};
758  const auto sat{(subs[0]->ops.sat + subs[1]->ops.dsat) | (subs[1]->ops.sat + subs[0]->ops.dsat)};
759  const auto dsat{subs[0]->ops.dsat + subs[1]->ops.dsat};
760  return {count, sat, dsat};
761  }
762  case Fragment::OR_D: {
763  const auto count{3 + subs[0]->ops.count + subs[1]->ops.count};
764  const auto sat{subs[0]->ops.sat | (subs[1]->ops.sat + subs[0]->ops.dsat)};
765  const auto dsat{subs[0]->ops.dsat + subs[1]->ops.dsat};
766  return {count, sat, dsat};
767  }
768  case Fragment::OR_C: {
769  const auto count{2 + subs[0]->ops.count + subs[1]->ops.count};
770  const auto sat{subs[0]->ops.sat | (subs[1]->ops.sat + subs[0]->ops.dsat)};
771  return {count, sat, {}};
772  }
773  case Fragment::OR_I: {
774  const auto count{3 + subs[0]->ops.count + subs[1]->ops.count};
775  const auto sat{subs[0]->ops.sat | subs[1]->ops.sat};
776  const auto dsat{subs[0]->ops.dsat | subs[1]->ops.dsat};
777  return {count, sat, dsat};
778  }
779  case Fragment::ANDOR: {
780  const auto count{3 + subs[0]->ops.count + subs[1]->ops.count + subs[2]->ops.count};
781  const auto sat{(subs[1]->ops.sat + subs[0]->ops.sat) | (subs[0]->ops.dsat + subs[2]->ops.sat)};
782  const auto dsat{subs[0]->ops.dsat + subs[2]->ops.dsat};
783  return {count, sat, dsat};
784  }
785  case Fragment::MULTI: return {1, (uint32_t)keys.size(), (uint32_t)keys.size()};
786  case Fragment::WRAP_S:
787  case Fragment::WRAP_C:
788  case Fragment::WRAP_N: return {1 + subs[0]->ops.count, subs[0]->ops.sat, subs[0]->ops.dsat};
789  case Fragment::WRAP_A: return {2 + subs[0]->ops.count, subs[0]->ops.sat, subs[0]->ops.dsat};
790  case Fragment::WRAP_D: return {3 + subs[0]->ops.count, subs[0]->ops.sat, 0};
791  case Fragment::WRAP_J: return {4 + subs[0]->ops.count, subs[0]->ops.sat, 0};
792  case Fragment::WRAP_V: return {subs[0]->ops.count + (subs[0]->GetType() << "x"_mst), subs[0]->ops.sat, {}};
793  case Fragment::THRESH: {
794  uint32_t count = 0;
795  auto sats = Vector(internal::MaxInt<uint32_t>(0));
796  for (const auto& sub : subs) {
797  count += sub->ops.count + 1;
798  auto next_sats = Vector(sats[0] + sub->ops.dsat);
799  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  next_sats.push_back(sats[sats.size() - 1] + sub->ops.sat);
801  sats = std::move(next_sats);
802  }
803  assert(k <= sats.size());
804  return {count, sats[k], sats[0]};
805  }
806  }
807  assert(false);
808  }
809 
811  switch (fragment) {
812  case Fragment::JUST_0: return {{}, 0};
813  case Fragment::JUST_1:
814  case Fragment::OLDER:
815  case Fragment::AFTER: return {0, {}};
816  case Fragment::PK_K: return {1, 1};
817  case Fragment::PK_H: return {2, 2};
818  case Fragment::SHA256:
819  case Fragment::RIPEMD160:
820  case Fragment::HASH256:
821  case Fragment::HASH160: return {1, {}};
822  case Fragment::ANDOR: {
823  const auto sat{(subs[0]->ss.sat + subs[1]->ss.sat) | (subs[0]->ss.dsat + subs[2]->ss.sat)};
824  const auto dsat{subs[0]->ss.dsat + subs[2]->ss.dsat};
825  return {sat, dsat};
826  }
827  case Fragment::AND_V: return {subs[0]->ss.sat + subs[1]->ss.sat, {}};
828  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  const auto sat{(subs[0]->ss.dsat + subs[1]->ss.sat) | (subs[0]->ss.sat + subs[1]->ss.dsat)};
831  const auto dsat{subs[0]->ss.dsat + subs[1]->ss.dsat};
832  return {sat, dsat};
833  }
834  case Fragment::OR_C: return {subs[0]->ss.sat | (subs[0]->ss.dsat + subs[1]->ss.sat), {}};
835  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  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  case Fragment::MULTI: return {k + 1, k + 1};
838  case Fragment::WRAP_A:
839  case Fragment::WRAP_N:
840  case Fragment::WRAP_S:
841  case Fragment::WRAP_C: return subs[0]->ss;
842  case Fragment::WRAP_D: return {1 + subs[0]->ss.sat, 1};
843  case Fragment::WRAP_V: return {subs[0]->ss.sat, {}};
844  case Fragment::WRAP_J: return {subs[0]->ss.sat, 1};
845  case Fragment::THRESH: {
846  auto sats = Vector(internal::MaxInt<uint32_t>(0));
847  for (const auto& sub : subs) {
848  auto next_sats = Vector(sats[0] + sub->ss.dsat);
849  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  next_sats.push_back(sats[sats.size() - 1] + sub->ss.sat);
851  sats = std::move(next_sats);
852  }
853  assert(k <= sats.size());
854  return {sats[k], sats[0]};
855  }
856  }
857  assert(false);
858  }
859 
861  switch (fragment) {
862  case Fragment::JUST_0: return {{}, 0};
863  case Fragment::JUST_1:
864  case Fragment::OLDER:
865  case Fragment::AFTER: return {0, {}};
866  case Fragment::PK_K: return {1 + 72, 1};
867  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  case Fragment::HASH160: return {1 + 32, {}};
872  case Fragment::ANDOR: {
873  const auto sat{(subs[0]->ws.sat + subs[1]->ws.sat) | (subs[0]->ws.dsat + subs[2]->ws.sat)};
874  const auto dsat{subs[0]->ws.dsat + subs[2]->ws.dsat};
875  return {sat, dsat};
876  }
877  case Fragment::AND_V: return {subs[0]->ws.sat + subs[1]->ws.sat, {}};
878  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  const auto sat{(subs[0]->ws.dsat + subs[1]->ws.sat) | (subs[0]->ws.sat + subs[1]->ws.dsat)};
881  const auto dsat{subs[0]->ws.dsat + subs[1]->ws.dsat};
882  return {sat, dsat};
883  }
884  case Fragment::OR_C: return {subs[0]->ws.sat | (subs[0]->ws.dsat + subs[1]->ws.sat), {}};
885  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  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  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  case Fragment::WRAP_C: return subs[0]->ws;
892  case Fragment::WRAP_D: return {1 + 1 + subs[0]->ws.sat, 1};
893  case Fragment::WRAP_V: return {subs[0]->ws.sat, {}};
894  case Fragment::WRAP_J: return {subs[0]->ws.sat, 1};
895  case Fragment::THRESH: {
896  auto sats = Vector(internal::MaxInt<uint32_t>(0));
897  for (const auto& sub : subs) {
898  auto next_sats = Vector(sats[0] + sub->ws.dsat);
899  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  next_sats.push_back(sats[sats.size() - 1] + sub->ws.sat);
901  sats = std::move(next_sats);
902  }
903  assert(k <= sats.size());
904  return {sats[k], sats[0]};
905  }
906  }
907  assert(false);
908  }
909 
910  template<typename Ctx>
911  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  auto helper = [&ctx](const Node& node, Span<InputResult> subres) -> InputResult {
917  switch (node.fragment) {
918  case Fragment::PK_K: {
919  std::vector<unsigned char> sig;
920  Availability avail = ctx.Sign(node.keys[0], sig);
921  return {ZERO, InputStack(std::move(sig)).SetWithSig().SetAvailable(avail)};
922  }
923  case Fragment::PK_H: {
924  std::vector<unsigned char> key = ctx.ToPKBytes(node.keys[0]), sig;
925  Availability avail = ctx.Sign(node.keys[0], sig);
926  return {ZERO + InputStack(key), (InputStack(std::move(sig)).SetWithSig() + InputStack(key)).SetAvailable(avail)};
927  }
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  std::vector<InputStack> sats = Vector(ZERO);
933  for (size_t i = 0; i < node.keys.size(); ++i) {
934  std::vector<unsigned char> sig;
935  Availability avail = ctx.Sign(node.keys[i], sig);
936  // Compute signature stack for just the i'th key.
937  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  std::vector<InputStack> next_sats;
942  next_sats.push_back(sats[0]);
943  for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back(sats[j] | (std::move(sats[j - 1]) + sat));
944  next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(sat));
945  // Switch over.
946  sats = std::move(next_sats);
947  }
948  // The dissatisfaction consists of k+1 stack elements all equal to 0.
949  InputStack nsat = ZERO;
950  for (size_t i = 0; i < node.k; ++i) nsat = std::move(nsat) + ZERO;
951  assert(node.k <= sats.size());
952  return {std::move(nsat), std::move(sats[node.k])};
953  }
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  std::vector<InputStack> sats = Vector(EMPTY);
959  for (size_t i = 0; i < subres.size(); ++i) {
960  // Introduce an alias for the i'th last satisfaction/dissatisfaction.
961  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  std::vector<InputStack> next_sats;
966  next_sats.push_back(sats[0] + res.nsat);
967  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  next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(res.sat));
969  // Switch over.
970  sats = std::move(next_sats);
971  }
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  InputStack nsat = INVALID;
975  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  if (i != 0 && i != node.k) sats[i].SetMalleable().SetNonCanon();
983  // Include all dissatisfactions (even these non-canonical ones) in nsat.
984  if (i != node.k) nsat = std::move(nsat) | std::move(sats[i]);
985  }
986  assert(node.k <= sats.size());
987  return {std::move(nsat), std::move(sats[node.k])};
988  }
989  case Fragment::OLDER: {
990  return {INVALID, ctx.CheckOlder(node.k) ? EMPTY : INVALID};
991  }
992  case Fragment::AFTER: {
993  return {INVALID, ctx.CheckAfter(node.k) ? EMPTY : INVALID};
994  }
995  case Fragment::SHA256: {
996  std::vector<unsigned char> preimage;
997  Availability avail = ctx.SatSHA256(node.data, preimage);
998  return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)};
999  }
1000  case Fragment::RIPEMD160: {
1001  std::vector<unsigned char> preimage;
1002  Availability avail = ctx.SatRIPEMD160(node.data, preimage);
1003  return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)};
1004  }
1005  case Fragment::HASH256: {
1006  std::vector<unsigned char> preimage;
1007  Availability avail = ctx.SatHASH256(node.data, preimage);
1008  return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)};
1009  }
1010  case Fragment::HASH160: {
1011  std::vector<unsigned char> preimage;
1012  Availability avail = ctx.SatHASH160(node.data, preimage);
1013  return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)};
1014  }
1015  case Fragment::AND_V: {
1016  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  return {(y.nsat + x.sat).SetNonCanon(), y.sat + x.sat};
1024  }
1025  case Fragment::AND_B: {
1026  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  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  auto& x = subres[0], &z = subres[1];
1036  // The (sat(Z) sat(X)) solution is overcomplete (attacker can change either into dsat).
1037  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  auto& x = subres[0], &z = subres[1];
1041  return {INVALID, std::move(x.sat) | (z.sat + x.nsat)};
1042  }
1043  case Fragment::OR_D: {
1044  auto& x = subres[0], &z = subres[1];
1045  return {z.nsat + x.nsat, std::move(x.sat) | (z.sat + x.nsat)};
1046  }
1047  case Fragment::OR_I: {
1048  auto& x = subres[0], &z = subres[1];
1049  return {(x.nsat + ONE) | (z.nsat + ZERO), (x.sat + ONE) | (z.sat + ZERO)};
1050  }
1051  case Fragment::ANDOR: {
1052  auto& x = subres[0], &y = subres[1], &z = subres[2];
1053  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  return std::move(subres[0]);
1060  case Fragment::WRAP_D: {
1061  auto &x = subres[0];
1062  return {ZERO, x.sat + ONE};
1063  }
1064  case Fragment::WRAP_J: {
1065  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  return {InputStack(ZERO).SetMalleable(x.nsat.available != Availability::NO && !x.nsat.has_sig), std::move(x.sat)};
1072  }
1073  case Fragment::WRAP_V: {
1074  auto &x = subres[0];
1075  return {INVALID, std::move(x.sat)};
1076  }
1077  case Fragment::JUST_0: return {EMPTY, INVALID};
1078  case Fragment::JUST_1: return {INVALID, EMPTY};
1079  }
1080  assert(false);
1081  return {INVALID, INVALID};
1082  };
1083 
1084  auto tester = [&helper](const Node& node, Span<InputResult> subres) -> InputResult {
1085  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  if (node.GetType() << "z"_mst && ret.nsat.available != Availability::NO) assert(ret.nsat.stack.size() == 0);
1092  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  if (node.GetType() << "o"_mst && ret.nsat.available != Availability::NO) assert(ret.nsat.stack.size() == 1);
1096  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  if (node.GetType() << "n"_mst && ret.sat.available != Availability::NO) assert(ret.sat.stack.size() >= 1);
1101  if (node.GetType() << "n"_mst && ret.nsat.available != Availability::NO) assert(ret.nsat.stack.size() >= 1);
1102  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  if (node.GetType() << "d"_mst) assert(ret.nsat.available != Availability::NO);
1107  if (node.GetType() << "d"_mst) assert(!ret.nsat.has_sig);
1108  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  if (node.GetType() << "f"_mst && ret.nsat.available != Availability::NO) assert(ret.nsat.has_sig);
1112  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  if (node.GetType() << "me"_mst) assert(ret.nsat.available != Availability::NO);
1116  if (node.GetType() << "me"_mst) assert(!ret.nsat.malleable);
1117 
1118  // For 'm' nodes, if a satisfaction exists, it must be non-malleable.
1119  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  if (ret.sat.available != Availability::NO && !ret.sat.malleable) assert(!ret.sat.non_canon);
1123 
1124  return ret;
1125  };
1126 
1127  return TreeEval<InputResult>(tester);
1128  }
1129 
1130 public:
1136  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  Comp(const Ctx& ctx) : ctx_ptr(&ctx) {}
1143  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  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  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  for (auto& sub : subs) {
1158  if (!sub.has_value()) {
1159  node.has_duplicate_keys = true;
1160  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  size_t keys_count = node.keys.size();
1167  keyset key_set{node.keys.begin(), node.keys.end(), Comp(ctx)};
1168  if (key_set.size() != keys_count) {
1169  // It already has duplicates; bail out.
1170  node.has_duplicate_keys = true;
1171  return {};
1172  }
1173 
1174  // Merge the keys from the children into this set.
1175  for (auto& sub : subs) {
1176  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  if (key_set.size() < sub->size()) std::swap(key_set, *sub);
1180  key_set.merge(*sub);
1181  if (key_set.size() != keys_count) {
1182  node.has_duplicate_keys = true;
1183  return {};
1184  }
1185  }
1186 
1187  node.has_duplicate_keys = false;
1188  return key_set;
1189  };
1190 
1191  TreeEval<state>(upfn);
1192  }
1193 
1195  size_t ScriptSize() const { return scriptlen; }
1196 
1198  std::optional<uint32_t> GetOps() const {
1199  if (!ops.sat.valid) return {};
1200  return ops.count + ops.sat.value;
1201  }
1202 
1204  uint32_t GetStaticOps() const { return ops.count; }
1205 
1207  bool CheckOpsLimit() const {
1208  if (const auto ops = GetOps()) return *ops <= MAX_OPS_PER_SCRIPT;
1209  return true;
1210  }
1211 
1214  std::optional<uint32_t> GetStackSize() const {
1215  if (!ss.sat.valid) return {};
1216  return ss.sat.value;
1217  }
1218 
1220  bool CheckStackSize() const {
1221  if (const auto ss = GetStackSize()) return *ss <= MAX_STANDARD_P2WSH_STACK_ITEMS;
1222  return true;
1223  }
1224 
1226  bool IsNotSatisfiable() const { return !GetStackSize(); }
1227 
1230  std::optional<uint32_t> GetWitnessSize() const {
1231  if (!ws.sat.valid) return {};
1232  return ws.sat.value;
1233  }
1234 
1236  Type GetType() const { return typ; }
1237 
1239  const Node* FindInsaneSub() const {
1240  return TreeEval<const Node*>([](const Node& node, Span<const Node*> subs) -> const Node* {
1241  for (auto& sub: subs) if (sub) return sub;
1242  if (!node.IsSaneSubexpression()) return &node;
1243  return nullptr;
1244  });
1245  }
1246 
1249  template<typename F>
1250  bool IsSatisfiable(F fn) const
1251  {
1252  // TreeEval() doesn't support bool as NodeType, so use int instead.
1253  return TreeEval<int>([&fn](const Node& node, Span<int> subs) -> bool {
1254  switch (node.fragment) {
1255  case Fragment::JUST_0:
1256  return false;
1257  case Fragment::JUST_1:
1258  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  return bool{fn(node)};
1269  case Fragment::ANDOR:
1270  return (subs[0] && subs[1]) || subs[2];
1271  case Fragment::AND_V:
1272  case Fragment::AND_B:
1273  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  return subs[0] || subs[1];
1279  case Fragment::THRESH:
1280  return static_cast<uint32_t>(std::count(subs.begin(), subs.end(), true)) >= node.k;
1281  default: // wrappers
1282  assert(subs.size() == 1);
1283  return subs[0];
1284  }
1285  });
1286  }
1287 
1289  bool IsValid() const { return !(GetType() == ""_mst) && ScriptSize() <= MAX_STANDARD_P2WSH_SCRIPT_SIZE; }
1290 
1292  bool IsValidTopLevel() const { return IsValid() && GetType() << "B"_mst; }
1293 
1295  bool IsNonMalleable() const { return GetType() << "m"_mst; }
1296 
1298  bool NeedsSignature() const { return GetType() << "s"_mst; }
1299 
1301  bool CheckTimeLocksMix() const { return GetType() << "k"_mst; }
1302 
1305 
1307  bool ValidSatisfactions() const { return IsValid() && CheckOpsLimit() && CheckStackSize(); }
1308 
1311 
1313  bool IsSane() const { return IsValidTopLevel() && IsSaneSubexpression() && NeedsSignature(); }
1314 
1319  template<typename Ctx>
1320  Availability Satisfy(const Ctx& ctx, std::vector<std::vector<unsigned char>>& stack, bool nonmalleable = true) const {
1321  auto ret = ProduceInput(ctx);
1322  if (nonmalleable && (ret.sat.malleable || !ret.sat.has_sig)) return Availability::NO;
1323  stack = std::move(ret.sat.stack);
1324  return ret.sat.available;
1325  }
1326 
1328  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  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  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  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  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()) {}
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  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 {
1351  WRAPPED_EXPR,
1353  EXPR,
1354 
1356  SWAP,
1358  ALT,
1360  CHECK,
1362  DUP_IF,
1364  VERIFY,
1366  NON_ZERO,
1368  ZERO_NOTEQUAL,
1370  WRAP_U,
1372  WRAP_T,
1373 
1375  AND_N,
1377  AND_V,
1379  AND_B,
1381  ANDOR,
1383  OR_B,
1385  OR_C,
1387  OR_D,
1389  OR_I,
1390 
1395  THRESH,
1396 
1398  COMMA,
1400  CLOSE_BRACKET,
1401 };
1402 
1403 int FindNextChar(Span<const char> in, const char m);
1404 
1406 template<typename Key, typename Ctx>
1407 std::optional<std::pair<Key, int>> ParseKeyEnd(Span<const char> in, const Ctx& ctx)
1408 {
1409  int key_size = FindNextChar(in, ')');
1410  if (key_size < 1) return {};
1411  auto key = ctx.FromString(in.begin(), in.begin() + key_size);
1412  if (!key) return {};
1413  return {{std::move(*key), key_size}};
1414 }
1415 
1417 template<typename Ctx>
1418 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  int hash_size = FindNextChar(in, ')');
1422  if (hash_size < 1) return {};
1423  std::string val = std::string(in.begin(), in.begin() + hash_size);
1424  if (!IsHex(val)) return {};
1425  auto hash = ParseHex(val);
1426  if (hash.size() != expected_size) return {};
1427  return {{std::move(hash), hash_size}};
1428 }
1429 
1431 template<typename Key>
1432 void BuildBack(Fragment nt, std::vector<NodeRef<Key>>& constructed, const bool reverse = false)
1433 {
1434  NodeRef<Key> child = std::move(constructed.back());
1435  constructed.pop_back();
1436  if (reverse) {
1437  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, nt, Vector(std::move(child), std::move(constructed.back())));
1438  } else {
1439  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, nt, Vector(std::move(constructed.back()), std::move(child)));
1440  }
1441 }
1442 
1448 template<typename Key, typename Ctx>
1449 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  size_t script_size{1};
1464 
1465  // The two integers are used to hold state for thresh()
1466  std::vector<std::tuple<ParseContext, int64_t, int64_t>> to_parse;
1467  std::vector<NodeRef<Key>> constructed;
1468 
1469  to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1470 
1471  while (!to_parse.empty()) {
1472  if (script_size > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
1473 
1474  // Get the current context we are decoding within
1475  auto [cur_context, n, k] = to_parse.back();
1476  to_parse.pop_back();
1477 
1478  switch (cur_context) {
1480  std::optional<size_t> colon_index{};
1481  for (size_t i = 1; i < in.size(); ++i) {
1482  if (in[i] == ':') {
1483  colon_index = i;
1484  break;
1485  }
1486  if (in[i] < 'a' || in[i] > 'z') break;
1487  }
1488  // If there is no colon, this loop won't execute
1489  bool last_was_v{false};
1490  for (size_t j = 0; colon_index && j < *colon_index; ++j) {
1491  if (script_size > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
1492  if (in[j] == 'a') {
1493  script_size += 2;
1494  to_parse.emplace_back(ParseContext::ALT, -1, -1);
1495  } else if (in[j] == 's') {
1496  script_size += 1;
1497  to_parse.emplace_back(ParseContext::SWAP, -1, -1);
1498  } else if (in[j] == 'c') {
1499  script_size += 1;
1500  to_parse.emplace_back(ParseContext::CHECK, -1, -1);
1501  } else if (in[j] == 'd') {
1502  script_size += 3;
1503  to_parse.emplace_back(ParseContext::DUP_IF, -1, -1);
1504  } else if (in[j] == 'j') {
1505  script_size += 4;
1506  to_parse.emplace_back(ParseContext::NON_ZERO, -1, -1);
1507  } else if (in[j] == 'n') {
1508  script_size += 1;
1509  to_parse.emplace_back(ParseContext::ZERO_NOTEQUAL, -1, -1);
1510  } 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  if (last_was_v) return {};
1514  to_parse.emplace_back(ParseContext::VERIFY, -1, -1);
1515  } else if (in[j] == 'u') {
1516  script_size += 4;
1517  to_parse.emplace_back(ParseContext::WRAP_U, -1, -1);
1518  } else if (in[j] == 't') {
1519  script_size += 1;
1520  to_parse.emplace_back(ParseContext::WRAP_T, -1, -1);
1521  } else if (in[j] == 'l') {
1522  // The l: wrapper is equivalent to or_i(0,X)
1523  script_size += 4;
1524  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_0));
1525  to_parse.emplace_back(ParseContext::OR_I, -1, -1);
1526  } else {
1527  return {};
1528  }
1529  last_was_v = (in[j] == 'v');
1530  }
1531  to_parse.emplace_back(ParseContext::EXPR, -1, -1);
1532  if (colon_index) in = in.subspan(*colon_index + 1);
1533  break;
1534  }
1535  case ParseContext::EXPR: {
1536  if (Const("0", in)) {
1537  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_0));
1538  } else if (Const("1", in)) {
1539  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_1));
1540  } else if (Const("pk(", in)) {
1541  auto res = ParseKeyEnd<Key, Ctx>(in, ctx);
1542  if (!res) return {};
1543  auto& [key, key_size] = *res;
1544  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_C, Vector(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_K, Vector(std::move(key))))));
1545  in = in.subspan(key_size + 1);
1546  script_size += 34;
1547  } else if (Const("pkh(", in)) {
1548  auto res = ParseKeyEnd<Key>(in, ctx);
1549  if (!res) return {};
1550  auto& [key, key_size] = *res;
1551  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_C, Vector(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_H, Vector(std::move(key))))));
1552  in = in.subspan(key_size + 1);
1553  script_size += 24;
1554  } else if (Const("pk_k(", in)) {
1555  auto res = ParseKeyEnd<Key>(in, ctx);
1556  if (!res) return {};
1557  auto& [key, key_size] = *res;
1558  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_K, Vector(std::move(key))));
1559  in = in.subspan(key_size + 1);
1560  script_size += 33;
1561  } else if (Const("pk_h(", in)) {
1562  auto res = ParseKeyEnd<Key>(in, ctx);
1563  if (!res) return {};
1564  auto& [key, key_size] = *res;
1565  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_H, Vector(std::move(key))));
1566  in = in.subspan(key_size + 1);
1567  script_size += 23;
1568  } else if (Const("sha256(", in)) {
1569  auto res = ParseHexStrEnd(in, 32, ctx);
1570  if (!res) return {};
1571  auto& [hash, hash_size] = *res;
1572  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::SHA256, std::move(hash)));
1573  in = in.subspan(hash_size + 1);
1574  script_size += 38;
1575  } else if (Const("ripemd160(", in)) {
1576  auto res = ParseHexStrEnd(in, 20, ctx);
1577  if (!res) return {};
1578  auto& [hash, hash_size] = *res;
1579  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::RIPEMD160, std::move(hash)));
1580  in = in.subspan(hash_size + 1);
1581  script_size += 26;
1582  } else if (Const("hash256(", in)) {
1583  auto res = ParseHexStrEnd(in, 32, ctx);
1584  if (!res) return {};
1585  auto& [hash, hash_size] = *res;
1586  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::HASH256, std::move(hash)));
1587  in = in.subspan(hash_size + 1);
1588  script_size += 38;
1589  } else if (Const("hash160(", in)) {
1590  auto res = ParseHexStrEnd(in, 20, ctx);
1591  if (!res) return {};
1592  auto& [hash, hash_size] = *res;
1593  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::HASH160, std::move(hash)));
1594  in = in.subspan(hash_size + 1);
1595  script_size += 26;
1596  } else if (Const("after(", in)) {
1597  int arg_size = FindNextChar(in, ')');
1598  if (arg_size < 1) return {};
1599  int64_t num;
1600  if (!ParseInt64(std::string(in.begin(), in.begin() + arg_size), &num)) return {};
1601  if (num < 1 || num >= 0x80000000L) return {};
1602  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::AFTER, num));
1603  in = in.subspan(arg_size + 1);
1604  script_size += 1 + (num > 16) + (num > 0x7f) + (num > 0x7fff) + (num > 0x7fffff);
1605  } else if (Const("older(", in)) {
1606  int arg_size = FindNextChar(in, ')');
1607  if (arg_size < 1) return {};
1608  int64_t num;
1609  if (!ParseInt64(std::string(in.begin(), in.begin() + arg_size), &num)) return {};
1610  if (num < 1 || num >= 0x80000000L) return {};
1611  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::OLDER, num));
1612  in = in.subspan(arg_size + 1);
1613  script_size += 1 + (num > 16) + (num > 0x7f) + (num > 0x7fff) + (num > 0x7fffff);
1614  } else if (Const("multi(", in)) {
1615  // Get threshold
1616  int next_comma = FindNextChar(in, ',');
1617  if (next_comma < 1) return {};
1618  if (!ParseInt64(std::string(in.begin(), in.begin() + next_comma), &k)) return {};
1619  in = in.subspan(next_comma + 1);
1620  // Get keys
1621  std::vector<Key> keys;
1622  while (next_comma != -1) {
1623  next_comma = FindNextChar(in, ',');
1624  int key_length = (next_comma == -1) ? FindNextChar(in, ')') : next_comma;
1625  if (key_length < 1) return {};
1626  auto key = ctx.FromString(in.begin(), in.begin() + key_length);
1627  if (!key) return {};
1628  keys.push_back(std::move(*key));
1629  in = in.subspan(key_length + 1);
1630  }
1631  if (keys.size() < 1 || keys.size() > 20) return {};
1632  if (k < 1 || k > (int64_t)keys.size()) return {};
1633  script_size += 2 + (keys.size() > 16) + (k > 16) + 34 * keys.size();
1634  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::MULTI, std::move(keys), k));
1635  } else if (Const("thresh(", in)) {
1636  int next_comma = FindNextChar(in, ',');
1637  if (next_comma < 1) return {};
1638  if (!ParseInt64(std::string(in.begin(), in.begin() + next_comma), &k)) return {};
1639  if (k < 1) return {};
1640  in = in.subspan(next_comma + 1);
1641  // n = 1 here because we read the first WRAPPED_EXPR before reaching THRESH
1642  to_parse.emplace_back(ParseContext::THRESH, 1, k);
1643  to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1644  script_size += 2 + (k > 16) + (k > 0x7f) + (k > 0x7fff) + (k > 0x7fffff);
1645  } else if (Const("andor(", in)) {
1646  to_parse.emplace_back(ParseContext::ANDOR, -1, -1);
1647  to_parse.emplace_back(ParseContext::CLOSE_BRACKET, -1, -1);
1648  to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1649  to_parse.emplace_back(ParseContext::COMMA, -1, -1);
1650  to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1651  to_parse.emplace_back(ParseContext::COMMA, -1, -1);
1652  to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1653  script_size += 5;
1654  } else {
1655  if (Const("and_n(", in)) {
1656  to_parse.emplace_back(ParseContext::AND_N, -1, -1);
1657  script_size += 5;
1658  } else if (Const("and_b(", in)) {
1659  to_parse.emplace_back(ParseContext::AND_B, -1, -1);
1660  script_size += 2;
1661  } else if (Const("and_v(", in)) {
1662  to_parse.emplace_back(ParseContext::AND_V, -1, -1);
1663  script_size += 1;
1664  } else if (Const("or_b(", in)) {
1665  to_parse.emplace_back(ParseContext::OR_B, -1, -1);
1666  script_size += 2;
1667  } else if (Const("or_c(", in)) {
1668  to_parse.emplace_back(ParseContext::OR_C, -1, -1);
1669  script_size += 3;
1670  } else if (Const("or_d(", in)) {
1671  to_parse.emplace_back(ParseContext::OR_D, -1, -1);
1672  script_size += 4;
1673  } else if (Const("or_i(", in)) {
1674  to_parse.emplace_back(ParseContext::OR_I, -1, -1);
1675  script_size += 4;
1676  } else {
1677  return {};
1678  }
1679  to_parse.emplace_back(ParseContext::CLOSE_BRACKET, -1, -1);
1680  to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1681  to_parse.emplace_back(ParseContext::COMMA, -1, -1);
1682  to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1683  }
1684  break;
1685  }
1686  case ParseContext::ALT: {
1687  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_A, Vector(std::move(constructed.back())));
1688  break;
1689  }
1690  case ParseContext::SWAP: {
1691  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_S, Vector(std::move(constructed.back())));
1692  break;
1693  }
1694  case ParseContext::CHECK: {
1695  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_C, Vector(std::move(constructed.back())));
1696  break;
1697  }
1698  case ParseContext::DUP_IF: {
1699  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_D, Vector(std::move(constructed.back())));
1700  break;
1701  }
1702  case ParseContext::NON_ZERO: {
1703  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_J, Vector(std::move(constructed.back())));
1704  break;
1705  }
1707  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_N, Vector(std::move(constructed.back())));
1708  break;
1709  }
1710  case ParseContext::VERIFY: {
1711  script_size += (constructed.back()->GetType() << "x"_mst);
1712  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_V, Vector(std::move(constructed.back())));
1713  break;
1714  }
1715  case ParseContext::WRAP_U: {
1716  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::OR_I, Vector(std::move(constructed.back()), MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_0)));
1717  break;
1718  }
1719  case ParseContext::WRAP_T: {
1720  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::AND_V, Vector(std::move(constructed.back()), MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_1)));
1721  break;
1722  }
1723  case ParseContext::AND_B: {
1724  BuildBack(Fragment::AND_B, constructed);
1725  break;
1726  }
1727  case ParseContext::AND_N: {
1728  auto mid = std::move(constructed.back());
1729  constructed.pop_back();
1730  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  }
1733  case ParseContext::AND_V: {
1734  BuildBack(Fragment::AND_V, constructed);
1735  break;
1736  }
1737  case ParseContext::OR_B: {
1738  BuildBack(Fragment::OR_B, constructed);
1739  break;
1740  }
1741  case ParseContext::OR_C: {
1742  BuildBack(Fragment::OR_C, constructed);
1743  break;
1744  }
1745  case ParseContext::OR_D: {
1746  BuildBack(Fragment::OR_D, constructed);
1747  break;
1748  }
1749  case ParseContext::OR_I: {
1750  BuildBack(Fragment::OR_I, constructed);
1751  break;
1752  }
1753  case ParseContext::ANDOR: {
1754  auto right = std::move(constructed.back());
1755  constructed.pop_back();
1756  auto mid = std::move(constructed.back());
1757  constructed.pop_back();
1758  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), std::move(right)));
1759  break;
1760  }
1761  case ParseContext::THRESH: {
1762  if (in.size() < 1) return {};
1763  if (in[0] == ',') {
1764  in = in.subspan(1);
1765  to_parse.emplace_back(ParseContext::THRESH, n+1, k);
1766  to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1767  script_size += 2;
1768  } else if (in[0] == ')') {
1769  if (k > n) return {};
1770  in = in.subspan(1);
1771  // Children are constructed in reverse order, so iterate from end to beginning
1772  std::vector<NodeRef<Key>> subs;
1773  for (int i = 0; i < n; ++i) {
1774  subs.push_back(std::move(constructed.back()));
1775  constructed.pop_back();
1776  }
1777  std::reverse(subs.begin(), subs.end());
1778  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::THRESH, std::move(subs), k));
1779  } else {
1780  return {};
1781  }
1782  break;
1783  }
1784  case ParseContext::COMMA: {
1785  if (in.size() < 1 || in[0] != ',') return {};
1786  in = in.subspan(1);
1787  break;
1788  }
1790  if (in.size() < 1 || in[0] != ')') return {};
1791  in = in.subspan(1);
1792  break;
1793  }
1794  }
1795  }
1796 
1797  // Sanity checks on the produced miniscript
1798  assert(constructed.size() == 1);
1799  assert(constructed[0]->ScriptSize() == script_size);
1800  if (in.size() > 0) return {};
1801  NodeRef<Key> tl_node = std::move(constructed.front());
1802  tl_node->DuplicateKeyCheck(ctx);
1803  return tl_node;
1804 }
1805 
1814 std::optional<std::vector<Opcode>> DecomposeScript(const CScript& script);
1815 
1817 std::optional<int64_t> ParseScriptNumber(const Opcode& in);
1818 
1819 enum class DecodeContext {
1825  BKV_EXPR,
1827  W_EXPR,
1828 
1832  SWAP,
1835  ALT,
1837  CHECK,
1839  DUP_IF,
1841  VERIFY,
1843  NON_ZERO,
1845  ZERO_NOTEQUAL,
1846 
1851  MAYBE_AND_V,
1853  AND_V,
1855  AND_B,
1857  ANDOR,
1859  OR_B,
1861  OR_C,
1863  OR_D,
1864 
1868  THRESH_W,
1871  THRESH_E,
1872 
1876  ENDIF,
1880  ENDIF_NOTIF,
1884  ENDIF_ELSE,
1885 };
1886 
1888 template<typename Key, typename Ctx, typename I>
1889 inline NodeRef<Key> DecodeScript(I& in, I last, const Ctx& ctx)
1890 {
1891  // The two integers are used to hold state for thresh()
1892  std::vector<std::tuple<DecodeContext, int64_t, int64_t>> to_parse;
1893  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  to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
1898 
1899  while (!to_parse.empty()) {
1900  // Exit early if the Miniscript is not going to be valid.
1901  if (!constructed.empty() && !constructed.back()->IsValid()) return {};
1902 
1903  // Get the current context we are decoding within
1904  auto [cur_context, n, k] = to_parse.back();
1905  to_parse.pop_back();
1906 
1907  switch(cur_context) {
1909  if (in >= last) return {};
1910 
1911  // Constants
1912  if (in[0].first == OP_1) {
1913  ++in;
1914  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_1));
1915  break;
1916  }
1917  if (in[0].first == OP_0) {
1918  ++in;
1919  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_0));
1920  break;
1921  }
1922  // Public keys
1923  if (in[0].second.size() == 33) {
1924  auto key = ctx.FromPKBytes(in[0].second.begin(), in[0].second.end());
1925  if (!key) return {};
1926  ++in;
1927  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_K, Vector(std::move(*key))));
1928  break;
1929  }
1930  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  auto key = ctx.FromPKHBytes(in[2].second.begin(), in[2].second.end());
1932  if (!key) return {};
1933  in += 5;
1934  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_H, Vector(std::move(*key))));
1935  break;
1936  }
1937  // Time locks
1938  std::optional<int64_t> num;
1939  if (last - in >= 2 && in[0].first == OP_CHECKSEQUENCEVERIFY && (num = ParseScriptNumber(in[1]))) {
1940  in += 2;
1941  if (*num < 1 || *num > 0x7FFFFFFFL) return {};
1942  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::OLDER, *num));
1943  break;
1944  }
1945  if (last - in >= 2 && in[0].first == OP_CHECKLOCKTIMEVERIFY && (num = ParseScriptNumber(in[1]))) {
1946  in += 2;
1947  if (num < 1 || num > 0x7FFFFFFFL) return {};
1948  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::AFTER, *num));
1949  break;
1950  }
1951  // Hashes
1952  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  if (in[2].first == OP_SHA256 && in[1].second.size() == 32) {
1954  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::SHA256, in[1].second));
1955  in += 7;
1956  break;
1957  } else if (in[2].first == OP_RIPEMD160 && in[1].second.size() == 20) {
1958  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::RIPEMD160, in[1].second));
1959  in += 7;
1960  break;
1961  } else if (in[2].first == OP_HASH256 && in[1].second.size() == 32) {
1962  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::HASH256, in[1].second));
1963  in += 7;
1964  break;
1965  } else if (in[2].first == OP_HASH160 && in[1].second.size() == 20) {
1966  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::HASH160, in[1].second));
1967  in += 7;
1968  break;
1969  }
1970  }
1971  // Multi
1972  if (last - in >= 3 && in[0].first == OP_CHECKMULTISIG) {
1973  std::vector<Key> keys;
1974  const auto n = ParseScriptNumber(in[1]);
1975  if (!n || last - in < 3 + *n) return {};
1976  if (*n < 1 || *n > 20) return {};
1977  for (int i = 0; i < *n; ++i) {
1978  if (in[2 + i].second.size() != 33) return {};
1979  auto key = ctx.FromPKBytes(in[2 + i].second.begin(), in[2 + i].second.end());
1980  if (!key) return {};
1981  keys.push_back(std::move(*key));
1982  }
1983  const auto k = ParseScriptNumber(in[2 + *n]);
1984  if (!k || *k < 1 || *k > *n) return {};
1985  in += 3 + *n;
1986  std::reverse(keys.begin(), keys.end());
1987  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::MULTI, std::move(keys), *k));
1988  break;
1989  }
1993  // c: wrapper
1994  if (in[0].first == OP_CHECKSIG) {
1995  ++in;
1996  to_parse.emplace_back(DecodeContext::CHECK, -1, -1);
1997  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
1998  break;
1999  }
2000  // v: wrapper
2001  if (in[0].first == OP_VERIFY) {
2002  ++in;
2003  to_parse.emplace_back(DecodeContext::VERIFY, -1, -1);
2004  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2005  break;
2006  }
2007  // n: wrapper
2008  if (in[0].first == OP_0NOTEQUAL) {
2009  ++in;
2010  to_parse.emplace_back(DecodeContext::ZERO_NOTEQUAL, -1, -1);
2011  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2012  break;
2013  }
2014  // Thresh
2015  if (last - in >= 3 && in[0].first == OP_EQUAL && (num = ParseScriptNumber(in[1]))) {
2016  if (*num < 1) return {};
2017  in += 2;
2018  to_parse.emplace_back(DecodeContext::THRESH_W, 0, *num);
2019  break;
2020  }
2021  // OP_ENDIF can be WRAP_J, WRAP_D, ANDOR, OR_C, OR_D, or OR_I
2022  if (in[0].first == OP_ENDIF) {
2023  ++in;
2024  to_parse.emplace_back(DecodeContext::ENDIF, -1, -1);
2025  to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
2026  break;
2027  }
2033  // and_b
2034  if (in[0].first == OP_BOOLAND) {
2035  ++in;
2036  to_parse.emplace_back(DecodeContext::AND_B, -1, -1);
2037  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2038  to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
2039  break;
2040  }
2041  // or_b
2042  if (in[0].first == OP_BOOLOR) {
2043  ++in;
2044  to_parse.emplace_back(DecodeContext::OR_B, -1, -1);
2045  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2046  to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
2047  break;
2048  }
2049  // Unrecognised expression
2050  return {};
2051  }
2052  case DecodeContext::BKV_EXPR: {
2053  to_parse.emplace_back(DecodeContext::MAYBE_AND_V, -1, -1);
2054  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2055  break;
2056  }
2057  case DecodeContext::W_EXPR: {
2058  // a: wrapper
2059  if (in >= last) return {};
2060  if (in[0].first == OP_FROMALTSTACK) {
2061  ++in;
2062  to_parse.emplace_back(DecodeContext::ALT, -1, -1);
2063  } else {
2064  to_parse.emplace_back(DecodeContext::SWAP, -1, -1);
2065  }
2066  to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
2067  break;
2068  }
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  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  to_parse.emplace_back(DecodeContext::AND_V, -1, -1);
2074  // BKV_EXPR can contain more AND_V nodes
2075  to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
2076  }
2077  break;
2078  }
2079  case DecodeContext::SWAP: {
2080  if (in >= last || in[0].first != OP_SWAP || constructed.empty()) return {};
2081  ++in;
2082  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_S, Vector(std::move(constructed.back())));
2083  break;
2084  }
2085  case DecodeContext::ALT: {
2086  if (in >= last || in[0].first != OP_TOALTSTACK || constructed.empty()) return {};
2087  ++in;
2088  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_A, Vector(std::move(constructed.back())));
2089  break;
2090  }
2091  case DecodeContext::CHECK: {
2092  if (constructed.empty()) return {};
2093  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_C, Vector(std::move(constructed.back())));
2094  break;
2095  }
2096  case DecodeContext::DUP_IF: {
2097  if (constructed.empty()) return {};
2098  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_D, Vector(std::move(constructed.back())));
2099  break;
2100  }
2101  case DecodeContext::VERIFY: {
2102  if (constructed.empty()) return {};
2103  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_V, Vector(std::move(constructed.back())));
2104  break;
2105  }
2106  case DecodeContext::NON_ZERO: {
2107  if (constructed.empty()) return {};
2108  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_J, Vector(std::move(constructed.back())));
2109  break;
2110  }
2112  if (constructed.empty()) return {};
2113  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_N, Vector(std::move(constructed.back())));
2114  break;
2115  }
2116  case DecodeContext::AND_V: {
2117  if (constructed.size() < 2) return {};
2118  BuildBack(Fragment::AND_V, constructed, /*reverse=*/true);
2119  break;
2120  }
2121  case DecodeContext::AND_B: {
2122  if (constructed.size() < 2) return {};
2123  BuildBack(Fragment::AND_B, constructed, /*reverse=*/true);
2124  break;
2125  }
2126  case DecodeContext::OR_B: {
2127  if (constructed.size() < 2) return {};
2128  BuildBack(Fragment::OR_B, constructed, /*reverse=*/true);
2129  break;
2130  }
2131  case DecodeContext::OR_C: {
2132  if (constructed.size() < 2) return {};
2133  BuildBack(Fragment::OR_C, constructed, /*reverse=*/true);
2134  break;
2135  }
2136  case DecodeContext::OR_D: {
2137  if (constructed.size() < 2) return {};
2138  BuildBack(Fragment::OR_D, constructed, /*reverse=*/true);
2139  break;
2140  }
2141  case DecodeContext::ANDOR: {
2142  if (constructed.size() < 3) return {};
2143  NodeRef<Key> left = std::move(constructed.back());
2144  constructed.pop_back();
2145  NodeRef<Key> right = std::move(constructed.back());
2146  constructed.pop_back();
2147  NodeRef<Key> mid = std::move(constructed.back());
2148  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::ANDOR, Vector(std::move(left), std::move(mid), std::move(right)));
2149  break;
2150  }
2151  case DecodeContext::THRESH_W: {
2152  if (in >= last) return {};
2153  if (in[0].first == OP_ADD) {
2154  ++in;
2155  to_parse.emplace_back(DecodeContext::THRESH_W, n+1, k);
2156  to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
2157  } else {
2158  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  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2161  }
2162  break;
2163  }
2164  case DecodeContext::THRESH_E: {
2165  if (k < 1 || k > n || constructed.size() < static_cast<size_t>(n)) return {};
2166  std::vector<NodeRef<Key>> subs;
2167  for (int i = 0; i < n; ++i) {
2168  NodeRef<Key> sub = std::move(constructed.back());
2169  constructed.pop_back();
2170  subs.push_back(std::move(sub));
2171  }
2172  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::THRESH, std::move(subs), k));
2173  break;
2174  }
2175  case DecodeContext::ENDIF: {
2176  if (in >= last) return {};
2177 
2178  // could be andor or or_i
2179  if (in[0].first == OP_ELSE) {
2180  ++in;
2181  to_parse.emplace_back(DecodeContext::ENDIF_ELSE, -1, -1);
2182  to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
2183  }
2184  // could be j: or d: wrapper
2185  else if (in[0].first == OP_IF) {
2186  if (last - in >= 2 && in[1].first == OP_DUP) {
2187  in += 2;
2188  to_parse.emplace_back(DecodeContext::DUP_IF, -1, -1);
2189  } else if (last - in >= 3 && in[1].first == OP_0NOTEQUAL && in[2].first == OP_SIZE) {
2190  in += 3;
2191  to_parse.emplace_back(DecodeContext::NON_ZERO, -1, -1);
2192  }
2193  else {
2194  return {};
2195  }
2196  // could be or_c or or_d
2197  } else if (in[0].first == OP_NOTIF) {
2198  ++in;
2199  to_parse.emplace_back(DecodeContext::ENDIF_NOTIF, -1, -1);
2200  }
2201  else {
2202  return {};
2203  }
2204  break;
2205  }
2207  if (in >= last) return {};
2208  if (in[0].first == OP_IFDUP) {
2209  ++in;
2210  to_parse.emplace_back(DecodeContext::OR_D, -1, -1);
2211  } else {
2212  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  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2216  break;
2217  }
2219  if (in >= last) return {};
2220  if (in[0].first == OP_IF) {
2221  ++in;
2222  BuildBack(Fragment::OR_I, constructed, /*reverse=*/true);
2223  } else if (in[0].first == OP_NOTIF) {
2224  ++in;
2225  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  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2228  } else {
2229  return {};
2230  }
2231  break;
2232  }
2233  }
2234  }
2235  if (constructed.size() != 1) return {};
2236  NodeRef<Key> tl_node = std::move(constructed.front());
2237  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  if (!tl_node->IsValidTopLevel()) return {};
2241  return tl_node;
2242 }
2243 
2244 } // namespace internal
2245 
2246 template<typename Ctx>
2247 inline NodeRef<typename Ctx::Key> FromString(const std::string& str, const Ctx& ctx) {
2248  return internal::Parse<typename Ctx::Key>(str, ctx);
2249 }
2250 
2251 template<typename Ctx>
2252 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  if (script.size() > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
2256  auto decomposed = DecomposeScript(script);
2257  if (!decomposed) return {};
2258  auto it = decomposed->begin();
2259  auto ret = DecodeScript<typename Ctx::Key>(it, decomposed->end(), ctx);
2260  if (!ret) return {};
2261  if (it != decomposed->end()) return {};
2262  return ret;
2263 }
2264 
2265 } // namespace miniscript
2266 
2267 #endif // BITCOIN_SCRIPT_MINISCRIPT_H
int ret
int flags
Definition: bitcoin-tx.cpp:528
ArgsManager & args
Definition: bitcoind.cpp:269
Serialized script, used inside transaction inputs and outputs.
Definition: script.h:413
A Span is an object that can refer to a contiguous sequence of objects.
Definition: span.h:97
constexpr std::size_t size() const noexcept
Definition: span.h:186
constexpr C * begin() const noexcept
Definition: span.h:174
CONSTEXPR_IF_NOT_DEBUG Span< C > last(std::size_t count) const noexcept
Definition: span.h:209
CONSTEXPR_IF_NOT_DEBUG Span< C > subspan(std::size_t offset) const noexcept
Definition: span.h:194
This type encapsulates the miniscript type system properties.
Definition: miniscript.h:121
constexpr bool operator<<(Type x) const
Check whether the left hand's properties are superset of the right's (= left is a subtype of right).
Definition: miniscript.h:139
uint32_t m_flags
Internal bitmap of properties (see ""_mst operator for details).
Definition: miniscript.h:123
constexpr Type(uint32_t flags)
Internal constructor used by the ""_mst operator.
Definition: miniscript.h:126
constexpr Type If(bool x) const
The empty type if x is false, itself otherwise.
Definition: miniscript.h:148
constexpr Type operator&(Type x) const
Compute the type with the intersection of properties.
Definition: miniscript.h:136
constexpr bool operator<(Type x) const
Comparison operator to enable use in sets/maps (total ordering incompatible with <<).
Definition: miniscript.h:142
constexpr Type operator|(Type x) const
Compute the type with the union of properties.
Definition: miniscript.h:133
constexpr bool operator==(Type x) const
Equality operator.
Definition: miniscript.h:145
size_type size() const
Definition: prevector.h:291
int FindNextChar(Span< const char > sp, const char m)
Definition: miniscript.cpp:400
std::optional< int64_t > ParseScriptNumber(const Opcode &in)
Determine whether the passed pair (created by DecomposeScript) is pushing a number.
Definition: miniscript.cpp:387
Type SanitizeType(Type e)
A helper sanitizer/checker for the output of CalcType.
Definition: miniscript.cpp:15
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)
Helper function for Node::CalcType.
Definition: miniscript.cpp:35
std::optional< std::vector< Opcode > > DecomposeScript(const CScript &script)
Decode a script into opcode/push pairs.
Definition: miniscript.cpp:351
std::optional< std::pair< std::vector< unsigned char >, int > > ParseHexStrEnd(Span< const char > in, const size_t expected_size, const Ctx &ctx)
Parse a hex string ending at the end of the fragment's text representation.
Definition: miniscript.h:1418
static const auto ONE
A stack consisting of a single 0x01 element (interpreted as 1 by the script interpreted in numeric co...
Definition: miniscript.h:285
static const auto ZERO32
A stack consisting of a single malleable 32-byte 0x0000...0000 element (for dissatisfying hash challe...
Definition: miniscript.h:283
size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs, size_t n_keys)
Helper function for Node::CalcScriptLen.
Definition: miniscript.cpp:249
static const auto ZERO
A stack consisting of a single zero-length element (interpreted as 0 by the script interpreter in num...
Definition: miniscript.h:281
@ OR_I
OR_I will construct an or_i node from the last two constructed nodes.
@ VERIFY
VERIFY wraps the top constructed node with v:
@ OR_B
OR_B will construct an or_b node from the last two constructed nodes.
@ CLOSE_BRACKET
CLOSE_BRACKET expects the next element to be ')' and fails if not.
@ AND_N
AND_N will construct an andor(X,Y,0) node from the last two constructed nodes.
@ SWAP
SWAP wraps the top constructed node with s:
@ ANDOR
ANDOR will construct an andor node from the last three constructed nodes.
@ THRESH
THRESH will read a wrapped expression, and then look for a COMMA.
@ COMMA
COMMA expects the next element to be ',' and fails if not.
@ AND_V
AND_V will construct an and_v node from the last two constructed nodes.
@ CHECK
CHECK wraps the top constructed node with c:
@ DUP_IF
DUP_IF wraps the top constructed node with d:
@ OR_C
OR_C will construct an or_c node from the last two constructed nodes.
@ EXPR
A miniscript expression which does not begin with wrappers.
@ ZERO_NOTEQUAL
ZERO_NOTEQUAL wraps the top constructed node with n:
@ NON_ZERO
NON_ZERO wraps the top constructed node with j:
@ WRAP_T
WRAP_T will construct an and_v(X,1) node from the top constructed node.
@ OR_D
OR_D will construct an or_d node from the last two constructed nodes.
@ AND_B
AND_B will construct an and_b node from the last two constructed nodes.
@ ALT
ALT wraps the top constructed node with a:
@ WRAP_U
WRAP_U will construct an or_i(X,0) node from the top constructed node.
@ WRAPPED_EXPR
An expression which may be begin with wrappers followed by a colon.
std::optional< std::pair< Key, int > > ParseKeyEnd(Span< const char > in, const Ctx &ctx)
Parse a key string ending at the end of the fragment's text representation.
Definition: miniscript.h:1407
static const auto INVALID
A stack representing the lack of any (dis)satisfactions.
Definition: miniscript.h:289
NodeRef< Key > Parse(Span< const char > in, const Ctx &ctx)
Parse a miniscript from its textual descriptor form.
Definition: miniscript.h:1449
@ VERIFY
VERIFY wraps the top constructed node with v:
@ SINGLE_BKV_EXPR
A single expression of type B, K, or V.
@ OR_B
OR_B will construct an or_b node from the last two constructed nodes.
@ ENDIF_NOTIF
If, inside an ENDIF context, we find an OP_NOTIF before finding an OP_ELSE, we could either be in an ...
@ BKV_EXPR
Potentially multiple SINGLE_BKV_EXPRs as children of (potentially multiple) and_v expressions.
@ ENDIF_ELSE
If, inside an ENDIF context, we find an OP_ELSE, then we could be in either an or_i or an andor node.
@ MAYBE_AND_V
MAYBE_AND_V will check if the next part of the script could be a valid miniscript sub-expression,...
@ SWAP
SWAP expects the next element to be OP_SWAP (inside a W-type expression that didn't end with FROMALTS...
@ ANDOR
ANDOR will construct an andor node from the last three constructed nodes.
@ W_EXPR
An expression of type W (a: or s: wrappers).
@ AND_V
AND_V will construct an and_v node from the last two constructed nodes.
@ THRESH_E
THRESH_E constructs a thresh node from the appropriate number of constructed children.
@ CHECK
CHECK wraps the top constructed node with c:
@ DUP_IF
DUP_IF wraps the top constructed node with d:
@ OR_C
OR_C will construct an or_c node from the last two constructed nodes.
@ ENDIF
ENDIF signals that we are inside some sort of OP_IF structure, which could be or_d,...
@ ZERO_NOTEQUAL
ZERO_NOTEQUAL wraps the top constructed node with n:
@ NON_ZERO
NON_ZERO wraps the top constructed node with j:
@ OR_D
OR_D will construct an or_d node from the last two constructed nodes.
@ AND_B
AND_B will construct an and_b node from the last two constructed nodes.
@ ALT
ALT expects the next element to be TOALTSTACK (we must have already read a FROMALTSTACK earlier),...
@ THRESH_W
In a thresh expression, all sub-expressions other than the first are W-type, and end in OP_ADD.
static const auto EMPTY
The empty stack.
Definition: miniscript.h:287
void BuildBack(Fragment nt, std::vector< NodeRef< Key >> &constructed, const bool reverse=false)
BuildBack pops the last two elements off constructed and wraps them in the specified Fragment.
Definition: miniscript.h:1432
NodeRef< Key > DecodeScript(I &in, I last, const Ctx &ctx)
Parse a miniscript from a bitcoin script.
Definition: miniscript.h:1889
std::shared_ptr< const Node< Key > > NodeRef
Definition: miniscript.h:186
NodeRef< Key > MakeNodeRef(Args &&... args)
Construct a miniscript node as a shared_ptr.
Definition: miniscript.h:190
NodeRef< typename Ctx::Key > FromScript(const CScript &script, const Ctx &ctx)
Definition: miniscript.h:2252
NodeRef< typename Ctx::Key > FromString(const std::string &str, const Ctx &ctx)
Definition: miniscript.h:2247
std::pair< opcodetype, std::vector< unsigned char > > Opcode
Definition: miniscript.h:183
Fragment
The different node types in miniscript.
Definition: miniscript.h:193
@ OR_I
OP_IF [X] OP_ELSE [Y] OP_ENDIF.
@ RIPEMD160
OP_SIZE 32 OP_EQUALVERIFY OP_RIPEMD160 [hash] OP_EQUAL.
@ HASH160
OP_SIZE 32 OP_EQUALVERIFY OP_HASH160 [hash] OP_EQUAL.
@ OR_B
[X] [Y] OP_BOOLOR
@ WRAP_A
OP_TOALTSTACK [X] OP_FROMALTSTACK.
@ WRAP_V
[X] OP_VERIFY (or -VERIFY version of last opcode in X)
@ ANDOR
[X] OP_NOTIF [Z] OP_ELSE [Y] OP_ENDIF
@ THRESH
[X1] ([Xn] OP_ADD)* [k] OP_EQUAL
@ WRAP_N
[X] OP_0NOTEQUAL
@ WRAP_S
OP_SWAP [X].
@ OR_C
[X] OP_NOTIF [Y] OP_ENDIF
@ HASH256
OP_SIZE 32 OP_EQUALVERIFY OP_HASH256 [hash] OP_EQUAL.
@ OLDER
[n] OP_CHECKSEQUENCEVERIFY
@ SHA256
OP_SIZE 32 OP_EQUALVERIFY OP_SHA256 [hash] OP_EQUAL.
@ WRAP_J
OP_SIZE OP_0NOTEQUAL OP_IF [X] OP_ENDIF.
@ AFTER
[n] OP_CHECKLOCKTIMEVERIFY
@ OR_D
[X] OP_IFDUP OP_NOTIF [Y] OP_ENDIF
@ WRAP_D
OP_DUP OP_IF [X] OP_ENDIF.
@ AND_B
[X] [Y] OP_BOOLAND
@ PK_H
OP_DUP OP_HASH160 [keyhash] OP_EQUALVERIFY.
@ WRAP_C
[X] OP_CHECKSIG
@ MULTI
[k] [key_n]* [n] OP_CHECKMULTISIG
Definition: init.h:25
bool Const(const std::string &str, Span< const char > &sp)
Parse a constant.
Definition: spanparsing.cpp:15
static constexpr unsigned int MAX_STANDARD_P2WSH_STACK_ITEMS
The maximum number of witness stack items in a standard P2WSH script.
Definition: policy.h:41
static constexpr unsigned int MAX_STANDARD_P2WSH_SCRIPT_SIZE
The maximum size in bytes of a standard witnessScript.
Definition: policy.h:47
@ OP_SHA256
Definition: script.h:184
@ OP_BOOLAND
Definition: script.h:167
@ OP_CHECKMULTISIG
Definition: script.h:190
@ OP_IF
Definition: script.h:102
@ OP_SWAP
Definition: script.h:129
@ OP_CHECKSIG
Definition: script.h:188
@ OP_CHECKLOCKTIMEVERIFY
Definition: script.h:195
@ OP_EQUAL
Definition: script.h:144
@ OP_NOTIF
Definition: script.h:103
@ OP_SIZE
Definition: script.h:137
@ OP_ENDIF
Definition: script.h:107
@ OP_DUP
Definition: script.h:123
@ OP_TOALTSTACK
Definition: script.h:112
@ OP_RIPEMD160
Definition: script.h:182
@ OP_HASH256
Definition: script.h:186
@ OP_FROMALTSTACK
Definition: script.h:113
@ OP_HASH160
Definition: script.h:185
@ OP_1
Definition: script.h:81
@ OP_VERIFY
Definition: script.h:108
@ OP_ADD
Definition: script.h:159
@ OP_CHECKMULTISIGVERIFY
Definition: script.h:191
@ OP_BOOLOR
Definition: script.h:168
@ OP_ELSE
Definition: script.h:106
@ OP_CHECKSIGVERIFY
Definition: script.h:189
@ OP_0NOTEQUAL
Definition: script.h:157
@ OP_0
Definition: script.h:74
@ OP_IFDUP
Definition: script.h:120
@ OP_EQUALVERIFY
Definition: script.h:145
@ OP_CHECKSEQUENCEVERIFY
Definition: script.h:197
static const int MAX_OPS_PER_SCRIPT
Definition: script.h:29
CScript BuildScript(Ts &&... inputs)
Build a script by concatenating other scripts, or any argument accepted by CScript::operator<<.
Definition: script.h:596
static bool verify(const CScriptNum10 &bignum, const CScriptNum &scriptnum)
std::vector< Byte > ParseHex(std::string_view hex_str)
Like TryParseHex, but returns an empty vector on invalid input.
Definition: strencodings.h:65
A node in a miniscript expression.
Definition: miniscript.h:355
const Type typ
Cached expression type (computed by CalcType and fed through SanitizeType).
Definition: miniscript.h:375
uint32_t GetStaticOps() const
Return the number of ops in the script (not counting the dynamic ones that depend on execution).
Definition: miniscript.h:1204
Result TreeEval(UpFn upfn) const
Like TreeEval, but without downfn or State type.
Definition: miniscript.h:514
Node(const Ctx &ctx, Fragment nt, std::vector< NodeRef< Key >> sub, std::vector< unsigned char > arg, uint32_t val=0)
Definition: miniscript.h:1339
internal::InputResult ProduceInput(const Ctx &ctx) const
Definition: miniscript.h:911
CScript ToScript(const Ctx &ctx) const
Definition: miniscript.h:565
bool CheckStackSize() const
Check the maximum stack size for this script against the policy limit.
Definition: miniscript.h:1220
Node(internal::NoDupCheck, Fragment nt, std::vector< NodeRef< Key >> sub, std::vector< unsigned char > arg, uint32_t val=0)
Definition: miniscript.h:1331
internal::StackSize CalcStackSize() const
Definition: miniscript.h:810
bool IsSaneSubexpression() const
Whether the apparent policy of this node matches its script semantics. Doesn't guarantee it is a safe...
Definition: miniscript.h:1310
Type GetType() const
Return the expression type.
Definition: miniscript.h:1236
friend int Compare(const Node< Key > &node1, const Node< Key > &node2)
Compare two miniscript subtrees, using a non-recursive algorithm.
Definition: miniscript.h:527
const size_t scriptlen
Cached script length (computed by CalcScriptLen).
Definition: miniscript.h:377
std::optional< bool > has_duplicate_keys
Whether a public key appears more than once in this node.
Definition: miniscript.h:383
const uint32_t k
The k parameter (time for OLDER/AFTER, threshold for THRESH(_M))
Definition: miniscript.h:359
const std::vector< NodeRef< Key > > subs
Subexpressions (for WRAP_*‍/AND_*‍/OR_*‍/ANDOR/THRESH)
Definition: miniscript.h:365
bool NeedsSignature() const
Check whether this script always needs a signature.
Definition: miniscript.h:1298
std::optional< Result > TreeEvalMaybe(UpFn upfn) const
Like TreeEvalMaybe, but without downfn or State type.
Definition: miniscript.h:485
bool CheckOpsLimit() const
Check the ops limit of this script against the consensus limit.
Definition: miniscript.h:1207
const Fragment fragment
What node type this node is.
Definition: miniscript.h:357
Node(const Ctx &ctx, Fragment nt, uint32_t val=0)
Definition: miniscript.h:1344
const Node * FindInsaneSub() const
Find an insane subnode which has no insane children. Nullptr if there is none.
Definition: miniscript.h:1239
internal::WitnessSize CalcWitnessSize() const
Definition: miniscript.h:860
Result TreeEval(State root_state, DownFn &&downfn, UpFn upfn) const
Like TreeEvalMaybe, but always produces a result.
Definition: miniscript.h:498
internal::Ops CalcOps() const
Definition: miniscript.h:737
Node(const Ctx &ctx, Fragment nt, std::vector< NodeRef< Key >> sub, std::vector< Key > key, uint32_t val=0)
Definition: miniscript.h:1341
std::optional< uint32_t > GetStackSize() const
Return the maximum number of stack elements needed to satisfy this script non-malleably.
Definition: miniscript.h:1214
Node(internal::NoDupCheck, Fragment nt, uint32_t val=0)
Definition: miniscript.h:1336
Availability Satisfy(const Ctx &ctx, std::vector< std::vector< unsigned char >> &stack, bool nonmalleable=true) const
Produce a witness for this script, if possible and given the information available in the context.
Definition: miniscript.h:1320
Node(internal::NoDupCheck, Fragment nt, std::vector< Key > key, uint32_t val=0)
Definition: miniscript.h:1334
Node(internal::NoDupCheck, Fragment nt, std::vector< NodeRef< Key >> sub, uint32_t val=0)
Definition: miniscript.h:1335
size_t CalcScriptLen() const
Compute the length of the script for this miniscript (including children).
Definition: miniscript.h:387
bool IsSane() const
Check whether this node is safe as a script on its own.
Definition: miniscript.h:1313
std::optional< uint32_t > GetOps() const
Return the maximum number of ops needed to satisfy this script non-malleably.
Definition: miniscript.h:1198
bool IsValidTopLevel() const
Check whether this node is valid as a script on its own.
Definition: miniscript.h:1292
bool IsNotSatisfiable() const
Whether no satisfaction exists for this node.
Definition: miniscript.h:1226
const internal::WitnessSize ws
Cached witness size bounds.
Definition: miniscript.h:373
Node(internal::NoDupCheck, Fragment nt, std::vector< NodeRef< Key >> sub, std::vector< Key > key, uint32_t val=0)
Definition: miniscript.h:1333
bool IsNonMalleable() const
Check whether this script can always be satisfied in a non-malleable way.
Definition: miniscript.h:1295
Type CalcType() const
Compute the type for this miniscript.
Definition: miniscript.h:547
bool CheckDuplicateKey() const
Check whether there is no duplicate key across this fragment and all its sub-fragments.
Definition: miniscript.h:1304
size_t ScriptSize() const
Return the size of the script for this expression (faster than ToScript().size()).
Definition: miniscript.h:1195
std::optional< uint32_t > GetWitnessSize() const
Return the maximum size in bytes of a witness to satisfy this script non-malleably.
Definition: miniscript.h:1230
Node(const Ctx &ctx, Fragment nt, std::vector< NodeRef< Key >> sub, uint32_t val=0)
Definition: miniscript.h:1343
bool ValidSatisfactions() const
Whether successful non-malleable satisfactions are guaranteed to be valid.
Definition: miniscript.h:1307
const std::vector< Key > keys
The keys used by this expression (only for PK_K/PK_H/MULTI)
Definition: miniscript.h:361
std::optional< Result > TreeEvalMaybe(State root_state, DownFn downfn, UpFn upfn) const
Definition: miniscript.h:420
std::optional< std::string > ToString(const CTx &ctx) const
Definition: miniscript.h:634
void DuplicateKeyCheck(const Ctx &ctx) const
Update duplicate key information in this Node.
Definition: miniscript.h:1136
bool operator==(const Node< Key > &arg) const
Equality testing.
Definition: miniscript.h:1328
bool CheckTimeLocksMix() const
Check whether there is no satisfaction path that contains both timelocks and heightlocks.
Definition: miniscript.h:1301
Node(const Ctx &ctx, Fragment nt, std::vector< Key > key, uint32_t val=0)
Definition: miniscript.h:1342
Node(const Ctx &ctx, Fragment nt, std::vector< unsigned char > arg, uint32_t val=0)
Definition: miniscript.h:1340
const internal::Ops ops
Cached ops counts.
Definition: miniscript.h:369
bool IsValid() const
Check whether this node is valid at all.
Definition: miniscript.h:1289
const std::vector< unsigned char > data
The data bytes in this expression (only for HASH160/HASH256/SHA256/RIPEMD10).
Definition: miniscript.h:363
const internal::StackSize ss
Cached stack size bounds.
Definition: miniscript.h:371
Node(internal::NoDupCheck, Fragment nt, std::vector< unsigned char > arg, uint32_t val=0)
Definition: miniscript.h:1332
bool IsSatisfiable(F fn) const
Determine whether a Miniscript node is satisfiable.
Definition: miniscript.h:1250
A pair of a satisfaction and a dissatisfaction InputStack.
Definition: miniscript.h:292
InputResult(A &&in_nsat, B &&in_sat)
Definition: miniscript.h:296
An object representing a sequence of witness stack elements.
Definition: miniscript.h:244
bool malleable
Whether this stack is malleable (can be turned into an equally valid other stack by a third party).
Definition: miniscript.h:254
friend InputStack operator|(InputStack a, InputStack b)
Choose between two potential input stacks.
Definition: miniscript.cpp:322
InputStack()
Construct an empty stack (valid).
Definition: miniscript.h:263
friend InputStack operator+(InputStack a, InputStack b)
Concatenate two input stacks.
Definition: miniscript.cpp:308
std::vector< std::vector< unsigned char > > stack
Data elements.
Definition: miniscript.h:261
bool has_sig
Whether this stack contains a digital signature.
Definition: miniscript.h:252
InputStack & SetAvailable(Availability avail)
Change availability.
Definition: miniscript.cpp:281
Availability available
Whether this stack is valid for its intended purpose (satisfaction or dissatisfaction of a Node).
Definition: miniscript.h:250
InputStack & SetMalleable(bool x=true)
Mark this input stack as malleable.
Definition: miniscript.cpp:303
size_t size
Serialized witness size.
Definition: miniscript.h:259
bool non_canon
Whether this stack is non-canonical (using a construction known to be unnecessary for satisfaction).
Definition: miniscript.h:257
InputStack(std::vector< unsigned char > in)
Construct a valid single-element stack (with an element up to 75 bytes).
Definition: miniscript.h:265
InputStack & SetWithSig()
Mark this input stack as having a signature.
Definition: miniscript.cpp:293
InputStack & SetNonCanon()
Mark this input stack as non-canonical (known to not be necessary in non-malleable satisfactions).
Definition: miniscript.cpp:298
Class whose objects represent the maximum of a list of integers.
Definition: miniscript.h:301
friend MaxInt< I > operator|(const MaxInt< I > &a, const MaxInt< I > &b)
Definition: miniscript.h:313
friend MaxInt< I > operator+(const MaxInt< I > &a, const MaxInt< I > &b)
Definition: miniscript.h:308
Ops(uint32_t in_count, MaxInt< uint32_t > in_sat, MaxInt< uint32_t > in_dsat)
Definition: miniscript.h:328
MaxInt< uint32_t > sat
Number of keys in possibly executed OP_CHECKMULTISIG(VERIFY)s to satisfy.
Definition: miniscript.h:324
MaxInt< uint32_t > dsat
Number of keys in possibly executed OP_CHECKMULTISIG(VERIFY)s to dissatisfy.
Definition: miniscript.h:326
uint32_t count
Non-push opcodes.
Definition: miniscript.h:322
MaxInt< uint32_t > sat
Maximum stack size to satisfy;.
Definition: miniscript.h:333
MaxInt< uint32_t > dsat
Maximum stack size to dissatisfy;.
Definition: miniscript.h:335
StackSize(MaxInt< uint32_t > in_sat, MaxInt< uint32_t > in_dsat)
Definition: miniscript.h:337
MaxInt< uint32_t > sat
Maximum witness size to satisfy;.
Definition: miniscript.h:342
MaxInt< uint32_t > dsat
Maximum witness size to dissatisfy;.
Definition: miniscript.h:344
WitnessSize(MaxInt< uint32_t > in_sat, MaxInt< uint32_t > in_dsat)
Definition: miniscript.h:346
static int count
std::string HexStr(const Span< const uint8_t > s)
Convert a span of bytes to a lower-case hexadecimal string.
bool ParseInt64(std::string_view str, int64_t *out)
Convert string to signed 64-bit integer with strict parse error feedback.
bool IsHex(std::string_view str)
#define B
Definition: util_tests.cpp:485
assert(!tx.IsCoinBase())
std::vector< typename std::common_type< Args... >::type > Vector(Args &&... args)
Construct a vector with the specified elements.
Definition: vector.h:21