Bitcoin Core  27.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/parsing.h>
22 #include <script/script.h>
23 #include <span.h>
24 #include <util/check.h>
25 #include <util/strencodings.h>
26 #include <util/string.h>
27 #include <util/vector.h>
28 
29 namespace miniscript {
30 
122 class Type {
124  uint32_t m_flags;
125 
127  explicit constexpr Type(uint32_t flags) noexcept : m_flags(flags) {}
128 
129 public:
131  static consteval Type Make(uint32_t flags) noexcept { return Type(flags); }
132 
134  constexpr Type operator|(Type x) const { return Type(m_flags | x.m_flags); }
135 
137  constexpr Type operator&(Type x) const { return Type(m_flags & x.m_flags); }
138 
140  constexpr bool operator<<(Type x) const { return (x.m_flags & ~m_flags) == 0; }
141 
143  constexpr bool operator<(Type x) const { return m_flags < x.m_flags; }
144 
146  constexpr bool operator==(Type x) const { return m_flags == x.m_flags; }
147 
149  constexpr Type If(bool x) const { return Type(x ? m_flags : 0); }
150 };
151 
153 inline consteval Type operator"" _mst(const char* c, size_t l) {
154  Type typ{Type::Make(0)};
155 
156  for (const char *p = c; p < c + l; p++) {
157  typ = typ | Type::Make(
158  *p == 'B' ? 1 << 0 : // Base type
159  *p == 'V' ? 1 << 1 : // Verify type
160  *p == 'K' ? 1 << 2 : // Key type
161  *p == 'W' ? 1 << 3 : // Wrapped type
162  *p == 'z' ? 1 << 4 : // Zero-arg property
163  *p == 'o' ? 1 << 5 : // One-arg property
164  *p == 'n' ? 1 << 6 : // Nonzero arg property
165  *p == 'd' ? 1 << 7 : // Dissatisfiable property
166  *p == 'u' ? 1 << 8 : // Unit property
167  *p == 'e' ? 1 << 9 : // Expression property
168  *p == 'f' ? 1 << 10 : // Forced property
169  *p == 's' ? 1 << 11 : // Safe property
170  *p == 'm' ? 1 << 12 : // Nonmalleable property
171  *p == 'x' ? 1 << 13 : // Expensive verify
172  *p == 'g' ? 1 << 14 : // older: contains relative time timelock (csv_time)
173  *p == 'h' ? 1 << 15 : // older: contains relative height timelock (csv_height)
174  *p == 'i' ? 1 << 16 : // after: contains time timelock (cltv_time)
175  *p == 'j' ? 1 << 17 : // after: contains height timelock (cltv_height)
176  *p == 'k' ? 1 << 18 : // does not contain a combination of height and time locks
177  (throw std::logic_error("Unknown character in _mst literal"), 0)
178  );
179  }
180 
181  return typ;
182 }
183 
184 using Opcode = std::pair<opcodetype, std::vector<unsigned char>>;
185 
186 template<typename Key> struct Node;
187 template<typename Key> using NodeRef = std::shared_ptr<const Node<Key>>;
188 
190 template<typename Key, typename... Args>
191 NodeRef<Key> MakeNodeRef(Args&&... args) { return std::make_shared<const Node<Key>>(std::forward<Args>(args)...); }
192 
194 enum class Fragment {
195  JUST_0,
196  JUST_1,
197  PK_K,
198  PK_H,
199  OLDER,
200  AFTER,
201  SHA256,
202  HASH256,
203  RIPEMD160,
204  HASH160,
205  WRAP_A,
206  WRAP_S,
207  WRAP_C,
208  WRAP_D,
209  WRAP_V,
210  WRAP_J,
211  WRAP_N,
212  AND_V,
213  AND_B,
214  OR_B,
215  OR_C,
216  OR_D,
217  OR_I,
218  ANDOR,
219  THRESH,
220  MULTI,
221  MULTI_A,
222  // AND_N(X,Y) is represented as ANDOR(X,Y,0)
223  // WRAP_T(X) is represented as AND_V(X,1)
224  // WRAP_L(X) is represented as OR_I(0,X)
225  // WRAP_U(X) is represented as OR_I(X,0)
226 };
227 
228 enum class Availability {
229  NO,
230  YES,
231  MAYBE,
232 };
233 
234 enum class MiniscriptContext {
235  P2WSH,
236  TAPSCRIPT,
237 };
238 
240 constexpr bool IsTapscript(MiniscriptContext ms_ctx)
241 {
242  switch (ms_ctx) {
243  case MiniscriptContext::P2WSH: return false;
244  case MiniscriptContext::TAPSCRIPT: return true;
245  }
246  assert(false);
247 }
248 
249 namespace internal {
250 
252 static constexpr uint32_t MAX_TAPMINISCRIPT_STACK_ELEM_SIZE{65};
253 
255 constexpr uint32_t TX_OVERHEAD{4 + 4};
257 constexpr uint32_t TXIN_BYTES_NO_WITNESS{36 + 4 + 1};
259 constexpr uint32_t P2WSH_TXOUT_BYTES{8 + 1 + 1 + 33};
265 constexpr uint32_t MaxScriptSize(MiniscriptContext ms_ctx)
266 {
267  if (IsTapscript(ms_ctx)) {
268  // Leaf scripts under Tapscript are not explicitly limited in size. They are only implicitly
269  // bounded by the maximum standard size of a spending transaction. Let the maximum script
270  // size conservatively be small enough such that even a maximum sized witness and a reasonably
271  // sized spending transaction can spend an output paying to this script without running into
272  // the maximum standard tx size limit.
274  return max_size - GetSizeOfCompactSize(max_size);
275  }
277 }
278 
280 Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Type>& sub_types, uint32_t k, size_t data_size, size_t n_subs, size_t n_keys, MiniscriptContext ms_ctx);
281 
283 size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs, size_t n_keys, MiniscriptContext ms_ctx);
284 
287 
289 struct InputStack {
297  bool has_sig = false;
299  bool malleable = false;
302  bool non_canon = false;
304  size_t size = 0;
306  std::vector<std::vector<unsigned char>> stack;
308  InputStack() = default;
310  InputStack(std::vector<unsigned char> in) : size(in.size() + 1), stack(Vector(std::move(in))) {}
318  InputStack& SetMalleable(bool x = true);
323 };
324 
326 static const auto ZERO = InputStack(std::vector<unsigned char>());
328 static const auto ZERO32 = InputStack(std::vector<unsigned char>(32, 0)).SetMalleable();
330 static const auto ONE = InputStack(Vector((unsigned char)1));
332 static const auto EMPTY = InputStack();
335 
337 struct InputResult {
339 
340  template<typename A, typename B>
341  InputResult(A&& in_nsat, B&& in_sat) : nsat(std::forward<A>(in_nsat)), sat(std::forward<B>(in_sat)) {}
342 };
343 
345 template<typename I>
346 struct MaxInt {
347  const bool valid;
348  const I value;
349 
350  MaxInt() : valid(false), value(0) {}
351  MaxInt(I val) : valid(true), value(val) {}
352 
353  friend MaxInt<I> operator+(const MaxInt<I>& a, const MaxInt<I>& b) {
354  if (!a.valid || !b.valid) return {};
355  return a.value + b.value;
356  }
357 
358  friend MaxInt<I> operator|(const MaxInt<I>& a, const MaxInt<I>& b) {
359  if (!a.valid) return b;
360  if (!b.valid) return a;
361  return std::max(a.value, b.value);
362  }
363 };
364 
365 struct Ops {
367  uint32_t count;
372 
373  Ops(uint32_t in_count, MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : count(in_count), sat(in_sat), dsat(in_dsat) {};
374 };
375 
417 struct SatInfo {
419  const bool valid;
421  const int32_t netdiff;
423  const int32_t exec;
424 
426  constexpr SatInfo() noexcept : valid(false), netdiff(0), exec(0) {}
427 
429  constexpr SatInfo(int32_t in_netdiff, int32_t in_exec) noexcept :
430  valid{true}, netdiff{in_netdiff}, exec{in_exec} {}
431 
433  constexpr friend SatInfo operator|(const SatInfo& a, const SatInfo& b) noexcept
434  {
435  // Union with an empty set is itself.
436  if (!a.valid) return b;
437  if (!b.valid) return a;
438  // Otherwise the netdiff and exec of the union is the maximum of the individual values.
439  return {std::max(a.netdiff, b.netdiff), std::max(a.exec, b.exec)};
440  }
441 
443  constexpr friend SatInfo operator+(const SatInfo& a, const SatInfo& b) noexcept
444  {
445  // Concatenation with an empty set yields an empty set.
446  if (!a.valid || !b.valid) return {};
447  // Otherwise, the maximum stack size difference for the combined scripts is the sum of the
448  // netdiffs, and the maximum stack size difference anywhere is either b.exec (if the
449  // maximum occurred in b) or b.netdiff+a.exec (if the maximum occurred in a).
450  return {a.netdiff + b.netdiff, std::max(b.exec, b.netdiff + a.exec)};
451  }
452 
454  static constexpr SatInfo Empty() noexcept { return {0, 0}; }
456  static constexpr SatInfo Push() noexcept { return {-1, 0}; }
458  static constexpr SatInfo Hash() noexcept { return {0, 0}; }
460  static constexpr SatInfo Nop() noexcept { return {0, 0}; }
462  static constexpr SatInfo If() noexcept { return {1, 1}; }
464  static constexpr SatInfo BinaryOp() noexcept { return {1, 1}; }
465 
466  // Scripts for specific individual opcodes.
467  static constexpr SatInfo OP_DUP() noexcept { return {-1, 0}; }
468  static constexpr SatInfo OP_IFDUP(bool nonzero) noexcept { return {nonzero ? -1 : 0, 0}; }
469  static constexpr SatInfo OP_EQUALVERIFY() noexcept { return {2, 2}; }
470  static constexpr SatInfo OP_EQUAL() noexcept { return {1, 1}; }
471  static constexpr SatInfo OP_SIZE() noexcept { return {-1, 0}; }
472  static constexpr SatInfo OP_CHECKSIG() noexcept { return {1, 1}; }
473  static constexpr SatInfo OP_0NOTEQUAL() noexcept { return {0, 0}; }
474  static constexpr SatInfo OP_VERIFY() noexcept { return {1, 1}; }
475 };
476 
477 struct StackSize {
478  const SatInfo sat, dsat;
479 
480  constexpr StackSize(SatInfo in_sat, SatInfo in_dsat) noexcept : sat(in_sat), dsat(in_dsat) {};
481  constexpr StackSize(SatInfo in_both) noexcept : sat(in_both), dsat(in_both) {};
482 };
483 
484 struct WitnessSize {
489 
490  WitnessSize(MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : sat(in_sat), dsat(in_dsat) {};
491 };
492 
493 struct NoDupCheck {};
494 
495 } // namespace internal
496 
498 template<typename Key>
499 struct Node {
503  const uint32_t k = 0;
505  const std::vector<Key> keys;
507  const std::vector<unsigned char> data;
509  mutable std::vector<NodeRef<Key>> subs;
512 
513  /* Destroy the shared pointers iteratively to avoid a stack-overflow due to recursive calls
514  * to the subs' destructors. */
515  ~Node() {
516  while (!subs.empty()) {
517  auto node = std::move(subs.back());
518  subs.pop_back();
519  while (!node->subs.empty()) {
520  subs.push_back(std::move(node->subs.back()));
521  node->subs.pop_back();
522  }
523  }
524  }
525 
526 private:
534  const Type typ;
536  const size_t scriptlen;
542  mutable std::optional<bool> has_duplicate_keys;
543 
544 
546  size_t CalcScriptLen() const {
547  size_t subsize = 0;
548  for (const auto& sub : subs) {
549  subsize += sub->ScriptSize();
550  }
551  static constexpr auto NONE_MST{""_mst};
552  Type sub0type = subs.size() > 0 ? subs[0]->GetType() : NONE_MST;
553  return internal::ComputeScriptLen(fragment, sub0type, subsize, k, subs.size(), keys.size(), m_script_ctx);
554  }
555 
556  /* Apply a recursive algorithm to a Miniscript tree, without actual recursive calls.
557  *
558  * The algorithm is defined by two functions: downfn and upfn. Conceptually, the
559  * result can be thought of as first using downfn to compute a "state" for each node,
560  * from the root down to the leaves. Then upfn is used to compute a "result" for each
561  * node, from the leaves back up to the root, which is then returned. In the actual
562  * implementation, both functions are invoked in an interleaved fashion, performing a
563  * depth-first traversal of the tree.
564  *
565  * In more detail, it is invoked as node.TreeEvalMaybe<Result>(root, downfn, upfn):
566  * - root is the state of the root node, of type State.
567  * - downfn is a callable (State&, const Node&, size_t) -> State, which given a
568  * node, its state, and an index of one of its children, computes the state of that
569  * child. It can modify the state. Children of a given node will have downfn()
570  * called in order.
571  * - upfn is a callable (State&&, const Node&, Span<Result>) -> std::optional<Result>,
572  * which given a node, its state, and a Span of the results of its children,
573  * computes the result of the node. If std::nullopt is returned by upfn,
574  * TreeEvalMaybe() immediately returns std::nullopt.
575  * The return value of TreeEvalMaybe is the result of the root node.
576  *
577  * Result type cannot be bool due to the std::vector<bool> specialization.
578  */
579  template<typename Result, typename State, typename DownFn, typename UpFn>
580  std::optional<Result> TreeEvalMaybe(State root_state, DownFn downfn, UpFn upfn) const
581  {
583  struct StackElem
584  {
585  const Node& node;
586  size_t expanded;
587  State state;
588 
589  StackElem(const Node& node_, size_t exp_, State&& state_) :
590  node(node_), expanded(exp_), state(std::move(state_)) {}
591  };
592  /* Stack of tree nodes being explored. */
593  std::vector<StackElem> stack;
594  /* Results of subtrees so far. Their order and mapping to tree nodes
595  * is implicitly defined by stack. */
596  std::vector<Result> results;
597  stack.emplace_back(*this, 0, std::move(root_state));
598 
599  /* Here is a demonstration of the algorithm, for an example tree A(B,C(D,E),F).
600  * State variables are omitted for simplicity.
601  *
602  * First: stack=[(A,0)] results=[]
603  * stack=[(A,1),(B,0)] results=[]
604  * stack=[(A,1)] results=[B]
605  * stack=[(A,2),(C,0)] results=[B]
606  * stack=[(A,2),(C,1),(D,0)] results=[B]
607  * stack=[(A,2),(C,1)] results=[B,D]
608  * stack=[(A,2),(C,2),(E,0)] results=[B,D]
609  * stack=[(A,2),(C,2)] results=[B,D,E]
610  * stack=[(A,2)] results=[B,C]
611  * stack=[(A,3),(F,0)] results=[B,C]
612  * stack=[(A,3)] results=[B,C,F]
613  * Final: stack=[] results=[A]
614  */
615  while (stack.size()) {
616  const Node& node = stack.back().node;
617  if (stack.back().expanded < node.subs.size()) {
618  /* We encounter a tree node with at least one unexpanded child.
619  * Expand it. By the time we hit this node again, the result of
620  * that child (and all earlier children) will be at the end of `results`. */
621  size_t child_index = stack.back().expanded++;
622  State child_state = downfn(stack.back().state, node, child_index);
623  stack.emplace_back(*node.subs[child_index], 0, std::move(child_state));
624  continue;
625  }
626  // Invoke upfn with the last node.subs.size() elements of results as input.
627  assert(results.size() >= node.subs.size());
628  std::optional<Result> result{upfn(std::move(stack.back().state), node,
629  Span<Result>{results}.last(node.subs.size()))};
630  // If evaluation returns std::nullopt, abort immediately.
631  if (!result) return {};
632  // Replace the last node.subs.size() elements of results with the new result.
633  results.erase(results.end() - node.subs.size(), results.end());
634  results.push_back(std::move(*result));
635  stack.pop_back();
636  }
637  // The final remaining results element is the root result, return it.
638  assert(results.size() == 1);
639  return std::move(results[0]);
640  }
641 
644  template<typename Result, typename UpFn>
645  std::optional<Result> TreeEvalMaybe(UpFn upfn) const
646  {
647  struct DummyState {};
648  return TreeEvalMaybe<Result>(DummyState{},
649  [](DummyState, const Node&, size_t) { return DummyState{}; },
650  [&upfn](DummyState, const Node& node, Span<Result> subs) {
651  return upfn(node, subs);
652  }
653  );
654  }
655 
657  template<typename Result, typename State, typename DownFn, typename UpFn>
658  Result TreeEval(State root_state, DownFn&& downfn, UpFn upfn) const
659  {
660  // Invoke TreeEvalMaybe with upfn wrapped to return std::optional<Result>, and then
661  // unconditionally dereference the result (it cannot be std::nullopt).
662  return std::move(*TreeEvalMaybe<Result>(std::move(root_state),
663  std::forward<DownFn>(downfn),
664  [&upfn](State&& state, const Node& node, Span<Result> subs) {
665  Result res{upfn(std::move(state), node, subs)};
666  return std::optional<Result>(std::move(res));
667  }
668  ));
669  }
670 
673  template<typename Result, typename UpFn>
674  Result TreeEval(UpFn upfn) const
675  {
676  struct DummyState {};
677  return std::move(*TreeEvalMaybe<Result>(DummyState{},
678  [](DummyState, const Node&, size_t) { return DummyState{}; },
679  [&upfn](DummyState, const Node& node, Span<Result> subs) {
680  Result res{upfn(node, subs)};
681  return std::optional<Result>(std::move(res));
682  }
683  ));
684  }
685 
687  friend int Compare(const Node<Key>& node1, const Node<Key>& node2)
688  {
689  std::vector<std::pair<const Node<Key>&, const Node<Key>&>> queue;
690  queue.emplace_back(node1, node2);
691  while (!queue.empty()) {
692  const auto& [a, b] = queue.back();
693  queue.pop_back();
694  if (std::tie(a.fragment, a.k, a.keys, a.data) < std::tie(b.fragment, b.k, b.keys, b.data)) return -1;
695  if (std::tie(b.fragment, b.k, b.keys, b.data) < std::tie(a.fragment, a.k, a.keys, a.data)) return 1;
696  if (a.subs.size() < b.subs.size()) return -1;
697  if (b.subs.size() < a.subs.size()) return 1;
698  size_t n = a.subs.size();
699  for (size_t i = 0; i < n; ++i) {
700  queue.emplace_back(*a.subs[n - 1 - i], *b.subs[n - 1 - i]);
701  }
702  }
703  return 0;
704  }
705 
707  Type CalcType() const {
708  using namespace internal;
709 
710  // THRESH has a variable number of subexpressions
711  std::vector<Type> sub_types;
712  if (fragment == Fragment::THRESH) {
713  for (const auto& sub : subs) sub_types.push_back(sub->GetType());
714  }
715  // All other nodes than THRESH can be computed just from the types of the 0-3 subexpressions.
716  static constexpr auto NONE_MST{""_mst};
717  Type x = subs.size() > 0 ? subs[0]->GetType() : NONE_MST;
718  Type y = subs.size() > 1 ? subs[1]->GetType() : NONE_MST;
719  Type z = subs.size() > 2 ? subs[2]->GetType() : NONE_MST;
720 
721  return SanitizeType(ComputeType(fragment, x, y, z, sub_types, k, data.size(), subs.size(), keys.size(), m_script_ctx));
722  }
723 
724 public:
725  template<typename Ctx>
726  CScript ToScript(const Ctx& ctx) const
727  {
728  // To construct the CScript for a Miniscript object, we use the TreeEval algorithm.
729  // The State is a boolean: whether or not the node's script expansion is followed
730  // by an OP_VERIFY (which may need to be combined with the last script opcode).
731  auto downfn = [](bool verify, const Node& node, size_t index) {
732  // For WRAP_V, the subexpression is certainly followed by OP_VERIFY.
733  if (node.fragment == Fragment::WRAP_V) return true;
734  // The subexpression of WRAP_S, and the last subexpression of AND_V
735  // inherit the followed-by-OP_VERIFY property from the parent.
736  if (node.fragment == Fragment::WRAP_S ||
737  (node.fragment == Fragment::AND_V && index == 1)) return verify;
738  return false;
739  };
740  // The upward function computes for a node, given its followed-by-OP_VERIFY status
741  // and the CScripts of its child nodes, the CScript of the node.
742  const bool is_tapscript{IsTapscript(m_script_ctx)};
743  auto upfn = [&ctx, is_tapscript](bool verify, const Node& node, Span<CScript> subs) -> CScript {
744  switch (node.fragment) {
745  case Fragment::PK_K: return BuildScript(ctx.ToPKBytes(node.keys[0]));
746  case Fragment::PK_H: return BuildScript(OP_DUP, OP_HASH160, ctx.ToPKHBytes(node.keys[0]), OP_EQUALVERIFY);
754  case Fragment::WRAP_S: return BuildScript(OP_SWAP, subs[0]);
755  case Fragment::WRAP_C: return BuildScript(std::move(subs[0]), verify ? OP_CHECKSIGVERIFY : OP_CHECKSIG);
757  case Fragment::WRAP_V: {
758  if (node.subs[0]->GetType() << "x"_mst) {
759  return BuildScript(std::move(subs[0]), OP_VERIFY);
760  } else {
761  return std::move(subs[0]);
762  }
763  }
765  case Fragment::WRAP_N: return BuildScript(std::move(subs[0]), OP_0NOTEQUAL);
766  case Fragment::JUST_1: return BuildScript(OP_1);
767  case Fragment::JUST_0: return BuildScript(OP_0);
768  case Fragment::AND_V: return BuildScript(std::move(subs[0]), subs[1]);
769  case Fragment::AND_B: return BuildScript(std::move(subs[0]), subs[1], OP_BOOLAND);
770  case Fragment::OR_B: return BuildScript(std::move(subs[0]), subs[1], OP_BOOLOR);
771  case Fragment::OR_D: return BuildScript(std::move(subs[0]), OP_IFDUP, OP_NOTIF, subs[1], OP_ENDIF);
772  case Fragment::OR_C: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[1], OP_ENDIF);
773  case Fragment::OR_I: return BuildScript(OP_IF, subs[0], OP_ELSE, subs[1], OP_ENDIF);
774  case Fragment::ANDOR: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[2], OP_ELSE, subs[1], OP_ENDIF);
775  case Fragment::MULTI: {
776  CHECK_NONFATAL(!is_tapscript);
778  for (const auto& key : node.keys) {
779  script = BuildScript(std::move(script), ctx.ToPKBytes(key));
780  }
781  return BuildScript(std::move(script), node.keys.size(), verify ? OP_CHECKMULTISIGVERIFY : OP_CHECKMULTISIG);
782  }
783  case Fragment::MULTI_A: {
784  CHECK_NONFATAL(is_tapscript);
785  CScript script = BuildScript(ctx.ToPKBytes(*node.keys.begin()), OP_CHECKSIG);
786  for (auto it = node.keys.begin() + 1; it != node.keys.end(); ++it) {
787  script = BuildScript(std::move(script), ctx.ToPKBytes(*it), OP_CHECKSIGADD);
788  }
789  return BuildScript(std::move(script), node.k, verify ? OP_NUMEQUALVERIFY : OP_NUMEQUAL);
790  }
791  case Fragment::THRESH: {
792  CScript script = std::move(subs[0]);
793  for (size_t i = 1; i < subs.size(); ++i) {
794  script = BuildScript(std::move(script), subs[i], OP_ADD);
795  }
796  return BuildScript(std::move(script), node.k, verify ? OP_EQUALVERIFY : OP_EQUAL);
797  }
798  }
799  assert(false);
800  };
801  return TreeEval<CScript>(false, downfn, upfn);
802  }
803 
804  template<typename CTx>
805  std::optional<std::string> ToString(const CTx& ctx) const {
806  // To construct the std::string representation for a Miniscript object, we use
807  // the TreeEvalMaybe algorithm. The State is a boolean: whether the parent node is a
808  // wrapper. If so, non-wrapper expressions must be prefixed with a ":".
809  auto downfn = [](bool, const Node& node, size_t) {
810  return (node.fragment == Fragment::WRAP_A || node.fragment == Fragment::WRAP_S ||
811  node.fragment == Fragment::WRAP_D || node.fragment == Fragment::WRAP_V ||
812  node.fragment == Fragment::WRAP_J || node.fragment == Fragment::WRAP_N ||
813  node.fragment == Fragment::WRAP_C ||
814  (node.fragment == Fragment::AND_V && node.subs[1]->fragment == Fragment::JUST_1) ||
815  (node.fragment == Fragment::OR_I && node.subs[0]->fragment == Fragment::JUST_0) ||
816  (node.fragment == Fragment::OR_I && node.subs[1]->fragment == Fragment::JUST_0));
817  };
818  // The upward function computes for a node, given whether its parent is a wrapper,
819  // and the string representations of its child nodes, the string representation of the node.
820  const bool is_tapscript{IsTapscript(m_script_ctx)};
821  auto upfn = [&ctx, is_tapscript](bool wrapped, const Node& node, Span<std::string> subs) -> std::optional<std::string> {
822  std::string ret = wrapped ? ":" : "";
823 
824  switch (node.fragment) {
825  case Fragment::WRAP_A: return "a" + std::move(subs[0]);
826  case Fragment::WRAP_S: return "s" + std::move(subs[0]);
827  case Fragment::WRAP_C:
828  if (node.subs[0]->fragment == Fragment::PK_K) {
829  // pk(K) is syntactic sugar for c:pk_k(K)
830  auto key_str = ctx.ToString(node.subs[0]->keys[0]);
831  if (!key_str) return {};
832  return std::move(ret) + "pk(" + std::move(*key_str) + ")";
833  }
834  if (node.subs[0]->fragment == Fragment::PK_H) {
835  // pkh(K) is syntactic sugar for c:pk_h(K)
836  auto key_str = ctx.ToString(node.subs[0]->keys[0]);
837  if (!key_str) return {};
838  return std::move(ret) + "pkh(" + std::move(*key_str) + ")";
839  }
840  return "c" + std::move(subs[0]);
841  case Fragment::WRAP_D: return "d" + std::move(subs[0]);
842  case Fragment::WRAP_V: return "v" + std::move(subs[0]);
843  case Fragment::WRAP_J: return "j" + std::move(subs[0]);
844  case Fragment::WRAP_N: return "n" + std::move(subs[0]);
845  case Fragment::AND_V:
846  // t:X is syntactic sugar for and_v(X,1).
847  if (node.subs[1]->fragment == Fragment::JUST_1) return "t" + std::move(subs[0]);
848  break;
849  case Fragment::OR_I:
850  if (node.subs[0]->fragment == Fragment::JUST_0) return "l" + std::move(subs[1]);
851  if (node.subs[1]->fragment == Fragment::JUST_0) return "u" + std::move(subs[0]);
852  break;
853  default: break;
854  }
855  switch (node.fragment) {
856  case Fragment::PK_K: {
857  auto key_str = ctx.ToString(node.keys[0]);
858  if (!key_str) return {};
859  return std::move(ret) + "pk_k(" + std::move(*key_str) + ")";
860  }
861  case Fragment::PK_H: {
862  auto key_str = ctx.ToString(node.keys[0]);
863  if (!key_str) return {};
864  return std::move(ret) + "pk_h(" + std::move(*key_str) + ")";
865  }
866  case Fragment::AFTER: return std::move(ret) + "after(" + util::ToString(node.k) + ")";
867  case Fragment::OLDER: return std::move(ret) + "older(" + util::ToString(node.k) + ")";
868  case Fragment::HASH256: return std::move(ret) + "hash256(" + HexStr(node.data) + ")";
869  case Fragment::HASH160: return std::move(ret) + "hash160(" + HexStr(node.data) + ")";
870  case Fragment::SHA256: return std::move(ret) + "sha256(" + HexStr(node.data) + ")";
871  case Fragment::RIPEMD160: return std::move(ret) + "ripemd160(" + HexStr(node.data) + ")";
872  case Fragment::JUST_1: return std::move(ret) + "1";
873  case Fragment::JUST_0: return std::move(ret) + "0";
874  case Fragment::AND_V: return std::move(ret) + "and_v(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
875  case Fragment::AND_B: return std::move(ret) + "and_b(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
876  case Fragment::OR_B: return std::move(ret) + "or_b(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
877  case Fragment::OR_D: return std::move(ret) + "or_d(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
878  case Fragment::OR_C: return std::move(ret) + "or_c(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
879  case Fragment::OR_I: return std::move(ret) + "or_i(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
880  case Fragment::ANDOR:
881  // and_n(X,Y) is syntactic sugar for andor(X,Y,0).
882  if (node.subs[2]->fragment == Fragment::JUST_0) return std::move(ret) + "and_n(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
883  return std::move(ret) + "andor(" + std::move(subs[0]) + "," + std::move(subs[1]) + "," + std::move(subs[2]) + ")";
884  case Fragment::MULTI: {
885  CHECK_NONFATAL(!is_tapscript);
886  auto str = std::move(ret) + "multi(" + util::ToString(node.k);
887  for (const auto& key : node.keys) {
888  auto key_str = ctx.ToString(key);
889  if (!key_str) return {};
890  str += "," + std::move(*key_str);
891  }
892  return std::move(str) + ")";
893  }
894  case Fragment::MULTI_A: {
895  CHECK_NONFATAL(is_tapscript);
896  auto str = std::move(ret) + "multi_a(" + util::ToString(node.k);
897  for (const auto& key : node.keys) {
898  auto key_str = ctx.ToString(key);
899  if (!key_str) return {};
900  str += "," + std::move(*key_str);
901  }
902  return std::move(str) + ")";
903  }
904  case Fragment::THRESH: {
905  auto str = std::move(ret) + "thresh(" + util::ToString(node.k);
906  for (auto& sub : subs) {
907  str += "," + std::move(sub);
908  }
909  return std::move(str) + ")";
910  }
911  default: break;
912  }
913  assert(false);
914  };
915 
916  return TreeEvalMaybe<std::string>(false, downfn, upfn);
917  }
918 
919 private:
921  switch (fragment) {
922  case Fragment::JUST_1: return {0, 0, {}};
923  case Fragment::JUST_0: return {0, {}, 0};
924  case Fragment::PK_K: return {0, 0, 0};
925  case Fragment::PK_H: return {3, 0, 0};
926  case Fragment::OLDER:
927  case Fragment::AFTER: return {1, 0, {}};
928  case Fragment::SHA256:
929  case Fragment::RIPEMD160:
930  case Fragment::HASH256:
931  case Fragment::HASH160: return {4, 0, {}};
932  case Fragment::AND_V: return {subs[0]->ops.count + subs[1]->ops.count, subs[0]->ops.sat + subs[1]->ops.sat, {}};
933  case Fragment::AND_B: {
934  const auto count{1 + subs[0]->ops.count + subs[1]->ops.count};
935  const auto sat{subs[0]->ops.sat + subs[1]->ops.sat};
936  const auto dsat{subs[0]->ops.dsat + subs[1]->ops.dsat};
937  return {count, sat, dsat};
938  }
939  case Fragment::OR_B: {
940  const auto count{1 + subs[0]->ops.count + subs[1]->ops.count};
941  const auto sat{(subs[0]->ops.sat + subs[1]->ops.dsat) | (subs[1]->ops.sat + subs[0]->ops.dsat)};
942  const auto dsat{subs[0]->ops.dsat + subs[1]->ops.dsat};
943  return {count, sat, dsat};
944  }
945  case Fragment::OR_D: {
946  const auto count{3 + subs[0]->ops.count + subs[1]->ops.count};
947  const auto sat{subs[0]->ops.sat | (subs[1]->ops.sat + subs[0]->ops.dsat)};
948  const auto dsat{subs[0]->ops.dsat + subs[1]->ops.dsat};
949  return {count, sat, dsat};
950  }
951  case Fragment::OR_C: {
952  const auto count{2 + subs[0]->ops.count + subs[1]->ops.count};
953  const auto sat{subs[0]->ops.sat | (subs[1]->ops.sat + subs[0]->ops.dsat)};
954  return {count, sat, {}};
955  }
956  case Fragment::OR_I: {
957  const auto count{3 + subs[0]->ops.count + subs[1]->ops.count};
958  const auto sat{subs[0]->ops.sat | subs[1]->ops.sat};
959  const auto dsat{subs[0]->ops.dsat | subs[1]->ops.dsat};
960  return {count, sat, dsat};
961  }
962  case Fragment::ANDOR: {
963  const auto count{3 + subs[0]->ops.count + subs[1]->ops.count + subs[2]->ops.count};
964  const auto sat{(subs[1]->ops.sat + subs[0]->ops.sat) | (subs[0]->ops.dsat + subs[2]->ops.sat)};
965  const auto dsat{subs[0]->ops.dsat + subs[2]->ops.dsat};
966  return {count, sat, dsat};
967  }
968  case Fragment::MULTI: return {1, (uint32_t)keys.size(), (uint32_t)keys.size()};
969  case Fragment::MULTI_A: return {(uint32_t)keys.size() + 1, 0, 0};
970  case Fragment::WRAP_S:
971  case Fragment::WRAP_C:
972  case Fragment::WRAP_N: return {1 + subs[0]->ops.count, subs[0]->ops.sat, subs[0]->ops.dsat};
973  case Fragment::WRAP_A: return {2 + subs[0]->ops.count, subs[0]->ops.sat, subs[0]->ops.dsat};
974  case Fragment::WRAP_D: return {3 + subs[0]->ops.count, subs[0]->ops.sat, 0};
975  case Fragment::WRAP_J: return {4 + subs[0]->ops.count, subs[0]->ops.sat, 0};
976  case Fragment::WRAP_V: return {subs[0]->ops.count + (subs[0]->GetType() << "x"_mst), subs[0]->ops.sat, {}};
977  case Fragment::THRESH: {
978  uint32_t count = 0;
979  auto sats = Vector(internal::MaxInt<uint32_t>(0));
980  for (const auto& sub : subs) {
981  count += sub->ops.count + 1;
982  auto next_sats = Vector(sats[0] + sub->ops.dsat);
983  for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub->ops.dsat) | (sats[j - 1] + sub->ops.sat));
984  next_sats.push_back(sats[sats.size() - 1] + sub->ops.sat);
985  sats = std::move(next_sats);
986  }
987  assert(k <= sats.size());
988  return {count, sats[k], sats[0]};
989  }
990  }
991  assert(false);
992  }
993 
995  using namespace internal;
996  switch (fragment) {
997  case Fragment::JUST_0: return {{}, SatInfo::Push()};
998  case Fragment::JUST_1: return {SatInfo::Push(), {}};
999  case Fragment::OLDER:
1000  case Fragment::AFTER: return {SatInfo::Push() + SatInfo::Nop(), {}};
1001  case Fragment::PK_K: return {SatInfo::Push()};
1002  case Fragment::PK_H: return {SatInfo::OP_DUP() + SatInfo::Hash() + SatInfo::Push() + SatInfo::OP_EQUALVERIFY()};
1003  case Fragment::SHA256:
1004  case Fragment::RIPEMD160:
1005  case Fragment::HASH256:
1006  case Fragment::HASH160: return {
1007  SatInfo::OP_SIZE() + SatInfo::Push() + SatInfo::OP_EQUALVERIFY() + SatInfo::Hash() + SatInfo::Push() + SatInfo::OP_EQUAL(),
1008  {}
1009  };
1010  case Fragment::ANDOR: {
1011  const auto& x{subs[0]->ss};
1012  const auto& y{subs[1]->ss};
1013  const auto& z{subs[2]->ss};
1014  return {
1015  (x.sat + SatInfo::If() + y.sat) | (x.dsat + SatInfo::If() + z.sat),
1016  x.dsat + SatInfo::If() + z.dsat
1017  };
1018  }
1019  case Fragment::AND_V: {
1020  const auto& x{subs[0]->ss};
1021  const auto& y{subs[1]->ss};
1022  return {x.sat + y.sat, {}};
1023  }
1024  case Fragment::AND_B: {
1025  const auto& x{subs[0]->ss};
1026  const auto& y{subs[1]->ss};
1027  return {x.sat + y.sat + SatInfo::BinaryOp(), x.dsat + y.dsat + SatInfo::BinaryOp()};
1028  }
1029  case Fragment::OR_B: {
1030  const auto& x{subs[0]->ss};
1031  const auto& y{subs[1]->ss};
1032  return {
1033  ((x.sat + y.dsat) | (x.dsat + y.sat)) + SatInfo::BinaryOp(),
1034  x.dsat + y.dsat + SatInfo::BinaryOp()
1035  };
1036  }
1037  case Fragment::OR_C: {
1038  const auto& x{subs[0]->ss};
1039  const auto& y{subs[1]->ss};
1040  return {(x.sat + SatInfo::If()) | (x.dsat + SatInfo::If() + y.sat), {}};
1041  }
1042  case Fragment::OR_D: {
1043  const auto& x{subs[0]->ss};
1044  const auto& y{subs[1]->ss};
1045  return {
1046  (x.sat + SatInfo::OP_IFDUP(true) + SatInfo::If()) | (x.dsat + SatInfo::OP_IFDUP(false) + SatInfo::If() + y.sat),
1047  x.dsat + SatInfo::OP_IFDUP(false) + SatInfo::If() + y.dsat
1048  };
1049  }
1050  case Fragment::OR_I: {
1051  const auto& x{subs[0]->ss};
1052  const auto& y{subs[1]->ss};
1053  return {SatInfo::If() + (x.sat | y.sat), SatInfo::If() + (x.dsat | y.dsat)};
1054  }
1055  // multi(k, key1, key2, ..., key_n) starts off with k+1 stack elements (a 0, plus k
1056  // signatures), then reaches n+k+3 stack elements after pushing the n keys, plus k and
1057  // n itself, and ends with 1 stack element (success or failure). Thus, it net removes
1058  // k elements (from k+1 to 1), while reaching k+n+2 more than it ends with.
1059  case Fragment::MULTI: return {SatInfo(k, k + keys.size() + 2)};
1060  // multi_a(k, key1, key2, ..., key_n) starts off with n stack elements (the
1061  // signatures), reaches 1 more (after the first key push), and ends with 1. Thus it net
1062  // removes n-1 elements (from n to 1) while reaching n more than it ends with.
1063  case Fragment::MULTI_A: return {SatInfo(keys.size() - 1, keys.size())};
1064  case Fragment::WRAP_A:
1065  case Fragment::WRAP_N:
1066  case Fragment::WRAP_S: return subs[0]->ss;
1067  case Fragment::WRAP_C: return {
1068  subs[0]->ss.sat + SatInfo::OP_CHECKSIG(),
1069  subs[0]->ss.dsat + SatInfo::OP_CHECKSIG()
1070  };
1071  case Fragment::WRAP_D: return {
1072  SatInfo::OP_DUP() + SatInfo::If() + subs[0]->ss.sat,
1073  SatInfo::OP_DUP() + SatInfo::If()
1074  };
1075  case Fragment::WRAP_V: return {subs[0]->ss.sat + SatInfo::OP_VERIFY(), {}};
1076  case Fragment::WRAP_J: return {
1077  SatInfo::OP_SIZE() + SatInfo::OP_0NOTEQUAL() + SatInfo::If() + subs[0]->ss.sat,
1078  SatInfo::OP_SIZE() + SatInfo::OP_0NOTEQUAL() + SatInfo::If()
1079  };
1080  case Fragment::THRESH: {
1081  // sats[j] is the SatInfo corresponding to all traces reaching j satisfactions.
1082  auto sats = Vector(SatInfo::Empty());
1083  for (size_t i = 0; i < subs.size(); ++i) {
1084  // Loop over the subexpressions, processing them one by one. After adding
1085  // element i we need to add OP_ADD (if i>0).
1086  auto add = i ? SatInfo::BinaryOp() : SatInfo::Empty();
1087  // Construct a variable that will become the next sats, starting with index 0.
1088  auto next_sats = Vector(sats[0] + subs[i]->ss.dsat + add);
1089  // Then loop to construct next_sats[1..i].
1090  for (size_t j = 1; j < sats.size(); ++j) {
1091  next_sats.push_back(((sats[j] + subs[i]->ss.dsat) | (sats[j - 1] + subs[i]->ss.sat)) + add);
1092  }
1093  // Finally construct next_sats[i+1].
1094  next_sats.push_back(sats[sats.size() - 1] + subs[i]->ss.sat + add);
1095  // Switch over.
1096  sats = std::move(next_sats);
1097  }
1098  // To satisfy thresh we need k satisfactions; to dissatisfy we need 0. In both
1099  // cases a push of k and an OP_EQUAL follow.
1100  return {
1101  sats[k] + SatInfo::Push() + SatInfo::OP_EQUAL(),
1102  sats[0] + SatInfo::Push() + SatInfo::OP_EQUAL()
1103  };
1104  }
1105  }
1106  assert(false);
1107  }
1108 
1110  const uint32_t sig_size = IsTapscript(m_script_ctx) ? 1 + 65 : 1 + 72;
1111  const uint32_t pubkey_size = IsTapscript(m_script_ctx) ? 1 + 32 : 1 + 33;
1112  switch (fragment) {
1113  case Fragment::JUST_0: return {{}, 0};
1114  case Fragment::JUST_1:
1115  case Fragment::OLDER:
1116  case Fragment::AFTER: return {0, {}};
1117  case Fragment::PK_K: return {sig_size, 1};
1118  case Fragment::PK_H: return {sig_size + pubkey_size, 1 + pubkey_size};
1119  case Fragment::SHA256:
1120  case Fragment::RIPEMD160:
1121  case Fragment::HASH256:
1122  case Fragment::HASH160: return {1 + 32, {}};
1123  case Fragment::ANDOR: {
1124  const auto sat{(subs[0]->ws.sat + subs[1]->ws.sat) | (subs[0]->ws.dsat + subs[2]->ws.sat)};
1125  const auto dsat{subs[0]->ws.dsat + subs[2]->ws.dsat};
1126  return {sat, dsat};
1127  }
1128  case Fragment::AND_V: return {subs[0]->ws.sat + subs[1]->ws.sat, {}};
1129  case Fragment::AND_B: return {subs[0]->ws.sat + subs[1]->ws.sat, subs[0]->ws.dsat + subs[1]->ws.dsat};
1130  case Fragment::OR_B: {
1131  const auto sat{(subs[0]->ws.dsat + subs[1]->ws.sat) | (subs[0]->ws.sat + subs[1]->ws.dsat)};
1132  const auto dsat{subs[0]->ws.dsat + subs[1]->ws.dsat};
1133  return {sat, dsat};
1134  }
1135  case Fragment::OR_C: return {subs[0]->ws.sat | (subs[0]->ws.dsat + subs[1]->ws.sat), {}};
1136  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};
1137  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)};
1138  case Fragment::MULTI: return {k * sig_size + 1, k + 1};
1139  case Fragment::MULTI_A: return {k * sig_size + static_cast<uint32_t>(keys.size()) - k, static_cast<uint32_t>(keys.size())};
1140  case Fragment::WRAP_A:
1141  case Fragment::WRAP_N:
1142  case Fragment::WRAP_S:
1143  case Fragment::WRAP_C: return subs[0]->ws;
1144  case Fragment::WRAP_D: return {1 + 1 + subs[0]->ws.sat, 1};
1145  case Fragment::WRAP_V: return {subs[0]->ws.sat, {}};
1146  case Fragment::WRAP_J: return {subs[0]->ws.sat, 1};
1147  case Fragment::THRESH: {
1148  auto sats = Vector(internal::MaxInt<uint32_t>(0));
1149  for (const auto& sub : subs) {
1150  auto next_sats = Vector(sats[0] + sub->ws.dsat);
1151  for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub->ws.dsat) | (sats[j - 1] + sub->ws.sat));
1152  next_sats.push_back(sats[sats.size() - 1] + sub->ws.sat);
1153  sats = std::move(next_sats);
1154  }
1155  assert(k <= sats.size());
1156  return {sats[k], sats[0]};
1157  }
1158  }
1159  assert(false);
1160  }
1161 
1162  template<typename Ctx>
1163  internal::InputResult ProduceInput(const Ctx& ctx) const {
1164  using namespace internal;
1165 
1166  // Internal function which is invoked for every tree node, constructing satisfaction/dissatisfactions
1167  // given those of its subnodes.
1168  auto helper = [&ctx](const Node& node, Span<InputResult> subres) -> InputResult {
1169  switch (node.fragment) {
1170  case Fragment::PK_K: {
1171  std::vector<unsigned char> sig;
1172  Availability avail = ctx.Sign(node.keys[0], sig);
1173  return {ZERO, InputStack(std::move(sig)).SetWithSig().SetAvailable(avail)};
1174  }
1175  case Fragment::PK_H: {
1176  std::vector<unsigned char> key = ctx.ToPKBytes(node.keys[0]), sig;
1177  Availability avail = ctx.Sign(node.keys[0], sig);
1178  return {ZERO + InputStack(key), (InputStack(std::move(sig)).SetWithSig() + InputStack(key)).SetAvailable(avail)};
1179  }
1180  case Fragment::MULTI_A: {
1181  // sats[j] represents the best stack containing j valid signatures (out of the first i keys).
1182  // In the loop below, these stacks are built up using a dynamic programming approach.
1183  std::vector<InputStack> sats = Vector(EMPTY);
1184  for (size_t i = 0; i < node.keys.size(); ++i) {
1185  // Get the signature for the i'th key in reverse order (the signature for the first key needs to
1186  // be at the top of the stack, contrary to CHECKMULTISIG's satisfaction).
1187  std::vector<unsigned char> sig;
1188  Availability avail = ctx.Sign(node.keys[node.keys.size() - 1 - i], sig);
1189  // Compute signature stack for just this key.
1190  auto sat = InputStack(std::move(sig)).SetWithSig().SetAvailable(avail);
1191  // Compute the next sats vector: next_sats[0] is a copy of sats[0] (no signatures). All further
1192  // next_sats[j] are equal to either the existing sats[j] + ZERO, or sats[j-1] plus a signature
1193  // for the current (i'th) key. The very last element needs all signatures filled.
1194  std::vector<InputStack> next_sats;
1195  next_sats.push_back(sats[0] + ZERO);
1196  for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + ZERO) | (std::move(sats[j - 1]) + sat));
1197  next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(sat));
1198  // Switch over.
1199  sats = std::move(next_sats);
1200  }
1201  // The dissatisfaction consists of as many empty vectors as there are keys, which is the same as
1202  // satisfying 0 keys.
1203  auto& nsat{sats[0]};
1204  assert(node.k != 0);
1205  assert(node.k <= sats.size());
1206  return {std::move(nsat), std::move(sats[node.k])};
1207  }
1208  case Fragment::MULTI: {
1209  // sats[j] represents the best stack containing j valid signatures (out of the first i keys).
1210  // In the loop below, these stacks are built up using a dynamic programming approach.
1211  // sats[0] starts off being {0}, due to the CHECKMULTISIG bug that pops off one element too many.
1212  std::vector<InputStack> sats = Vector(ZERO);
1213  for (size_t i = 0; i < node.keys.size(); ++i) {
1214  std::vector<unsigned char> sig;
1215  Availability avail = ctx.Sign(node.keys[i], sig);
1216  // Compute signature stack for just the i'th key.
1217  auto sat = InputStack(std::move(sig)).SetWithSig().SetAvailable(avail);
1218  // Compute the next sats vector: next_sats[0] is a copy of sats[0] (no signatures). All further
1219  // next_sats[j] are equal to either the existing sats[j], or sats[j-1] plus a signature for the
1220  // current (i'th) key. The very last element needs all signatures filled.
1221  std::vector<InputStack> next_sats;
1222  next_sats.push_back(sats[0]);
1223  for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back(sats[j] | (std::move(sats[j - 1]) + sat));
1224  next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(sat));
1225  // Switch over.
1226  sats = std::move(next_sats);
1227  }
1228  // The dissatisfaction consists of k+1 stack elements all equal to 0.
1229  InputStack nsat = ZERO;
1230  for (size_t i = 0; i < node.k; ++i) nsat = std::move(nsat) + ZERO;
1231  assert(node.k <= sats.size());
1232  return {std::move(nsat), std::move(sats[node.k])};
1233  }
1234  case Fragment::THRESH: {
1235  // sats[k] represents the best stack that satisfies k out of the *last* i subexpressions.
1236  // In the loop below, these stacks are built up using a dynamic programming approach.
1237  // sats[0] starts off empty.
1238  std::vector<InputStack> sats = Vector(EMPTY);
1239  for (size_t i = 0; i < subres.size(); ++i) {
1240  // Introduce an alias for the i'th last satisfaction/dissatisfaction.
1241  auto& res = subres[subres.size() - i - 1];
1242  // Compute the next sats vector: next_sats[0] is sats[0] plus res.nsat (thus containing all dissatisfactions
1243  // so far. next_sats[j] is either sats[j] + res.nsat (reusing j earlier satisfactions) or sats[j-1] + res.sat
1244  // (reusing j-1 earlier satisfactions plus a new one). The very last next_sats[j] is all satisfactions.
1245  std::vector<InputStack> next_sats;
1246  next_sats.push_back(sats[0] + res.nsat);
1247  for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + res.nsat) | (std::move(sats[j - 1]) + res.sat));
1248  next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(res.sat));
1249  // Switch over.
1250  sats = std::move(next_sats);
1251  }
1252  // At this point, sats[k].sat is the best satisfaction for the overall thresh() node. The best dissatisfaction
1253  // is computed by gathering all sats[i].nsat for i != k.
1254  InputStack nsat = INVALID;
1255  for (size_t i = 0; i < sats.size(); ++i) {
1256  // i==k is the satisfaction; i==0 is the canonical dissatisfaction;
1257  // the rest are non-canonical (a no-signature dissatisfaction - the i=0
1258  // form - is always available) and malleable (due to overcompleteness).
1259  // Marking the solutions malleable here is not strictly necessary, as they
1260  // should already never be picked in non-malleable solutions due to the
1261  // availability of the i=0 form.
1262  if (i != 0 && i != node.k) sats[i].SetMalleable().SetNonCanon();
1263  // Include all dissatisfactions (even these non-canonical ones) in nsat.
1264  if (i != node.k) nsat = std::move(nsat) | std::move(sats[i]);
1265  }
1266  assert(node.k <= sats.size());
1267  return {std::move(nsat), std::move(sats[node.k])};
1268  }
1269  case Fragment::OLDER: {
1270  return {INVALID, ctx.CheckOlder(node.k) ? EMPTY : INVALID};
1271  }
1272  case Fragment::AFTER: {
1273  return {INVALID, ctx.CheckAfter(node.k) ? EMPTY : INVALID};
1274  }
1275  case Fragment::SHA256: {
1276  std::vector<unsigned char> preimage;
1277  Availability avail = ctx.SatSHA256(node.data, preimage);
1278  return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)};
1279  }
1280  case Fragment::RIPEMD160: {
1281  std::vector<unsigned char> preimage;
1282  Availability avail = ctx.SatRIPEMD160(node.data, preimage);
1283  return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)};
1284  }
1285  case Fragment::HASH256: {
1286  std::vector<unsigned char> preimage;
1287  Availability avail = ctx.SatHASH256(node.data, preimage);
1288  return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)};
1289  }
1290  case Fragment::HASH160: {
1291  std::vector<unsigned char> preimage;
1292  Availability avail = ctx.SatHASH160(node.data, preimage);
1293  return {ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)};
1294  }
1295  case Fragment::AND_V: {
1296  auto& x = subres[0], &y = subres[1];
1297  // As the dissatisfaction here only consist of a single option, it doesn't
1298  // actually need to be listed (it's not required for reasoning about malleability of
1299  // other options), and is never required (no valid miniscript relies on the ability
1300  // to satisfy the type V left subexpression). It's still listed here for
1301  // completeness, as a hypothetical (not currently implemented) satisfier that doesn't
1302  // care about malleability might in some cases prefer it still.
1303  return {(y.nsat + x.sat).SetNonCanon(), y.sat + x.sat};
1304  }
1305  case Fragment::AND_B: {
1306  auto& x = subres[0], &y = subres[1];
1307  // Note that it is not strictly necessary to mark the 2nd and 3rd dissatisfaction here
1308  // as malleable. While they are definitely malleable, they are also non-canonical due
1309  // to the guaranteed existence of a no-signature other dissatisfaction (the 1st)
1310  // option. Because of that, the 2nd and 3rd option will never be chosen, even if they
1311  // weren't marked as malleable.
1312  return {(y.nsat + x.nsat) | (y.sat + x.nsat).SetMalleable().SetNonCanon() | (y.nsat + x.sat).SetMalleable().SetNonCanon(), y.sat + x.sat};
1313  }
1314  case Fragment::OR_B: {
1315  auto& x = subres[0], &z = subres[1];
1316  // The (sat(Z) sat(X)) solution is overcomplete (attacker can change either into dsat).
1317  return {z.nsat + x.nsat, (z.nsat + x.sat) | (z.sat + x.nsat) | (z.sat + x.sat).SetMalleable().SetNonCanon()};
1318  }
1319  case Fragment::OR_C: {
1320  auto& x = subres[0], &z = subres[1];
1321  return {INVALID, std::move(x.sat) | (z.sat + x.nsat)};
1322  }
1323  case Fragment::OR_D: {
1324  auto& x = subres[0], &z = subres[1];
1325  return {z.nsat + x.nsat, std::move(x.sat) | (z.sat + x.nsat)};
1326  }
1327  case Fragment::OR_I: {
1328  auto& x = subres[0], &z = subres[1];
1329  return {(x.nsat + ONE) | (z.nsat + ZERO), (x.sat + ONE) | (z.sat + ZERO)};
1330  }
1331  case Fragment::ANDOR: {
1332  auto& x = subres[0], &y = subres[1], &z = subres[2];
1333  return {(y.nsat + x.sat).SetNonCanon() | (z.nsat + x.nsat), (y.sat + x.sat) | (z.sat + x.nsat)};
1334  }
1335  case Fragment::WRAP_A:
1336  case Fragment::WRAP_S:
1337  case Fragment::WRAP_C:
1338  case Fragment::WRAP_N:
1339  return std::move(subres[0]);
1340  case Fragment::WRAP_D: {
1341  auto &x = subres[0];
1342  return {ZERO, x.sat + ONE};
1343  }
1344  case Fragment::WRAP_J: {
1345  auto &x = subres[0];
1346  // If a dissatisfaction with a nonzero top stack element exists, an alternative dissatisfaction exists.
1347  // As the dissatisfaction logic currently doesn't keep track of this nonzeroness property, and thus even
1348  // if a dissatisfaction with a top zero element is found, we don't know whether another one with a
1349  // nonzero top stack element exists. Make the conservative assumption that whenever the subexpression is weakly
1350  // dissatisfiable, this alternative dissatisfaction exists and leads to malleability.
1351  return {InputStack(ZERO).SetMalleable(x.nsat.available != Availability::NO && !x.nsat.has_sig), std::move(x.sat)};
1352  }
1353  case Fragment::WRAP_V: {
1354  auto &x = subres[0];
1355  return {INVALID, std::move(x.sat)};
1356  }
1357  case Fragment::JUST_0: return {EMPTY, INVALID};
1358  case Fragment::JUST_1: return {INVALID, EMPTY};
1359  }
1360  assert(false);
1361  return {INVALID, INVALID};
1362  };
1363 
1364  auto tester = [&helper](const Node& node, Span<InputResult> subres) -> InputResult {
1365  auto ret = helper(node, subres);
1366 
1367  // Do a consistency check between the satisfaction code and the type checker
1368  // (the actual satisfaction code in ProduceInputHelper does not use GetType)
1369 
1370  // For 'z' nodes, available satisfactions/dissatisfactions must have stack size 0.
1371  if (node.GetType() << "z"_mst && ret.nsat.available != Availability::NO) assert(ret.nsat.stack.size() == 0);
1372  if (node.GetType() << "z"_mst && ret.sat.available != Availability::NO) assert(ret.sat.stack.size() == 0);
1373 
1374  // For 'o' nodes, available satisfactions/dissatisfactions must have stack size 1.
1375  if (node.GetType() << "o"_mst && ret.nsat.available != Availability::NO) assert(ret.nsat.stack.size() == 1);
1376  if (node.GetType() << "o"_mst && ret.sat.available != Availability::NO) assert(ret.sat.stack.size() == 1);
1377 
1378  // For 'n' nodes, available satisfactions/dissatisfactions must have stack size 1 or larger. For satisfactions,
1379  // the top element cannot be 0.
1380  if (node.GetType() << "n"_mst && ret.sat.available != Availability::NO) assert(ret.sat.stack.size() >= 1);
1381  if (node.GetType() << "n"_mst && ret.nsat.available != Availability::NO) assert(ret.nsat.stack.size() >= 1);
1382  if (node.GetType() << "n"_mst && ret.sat.available != Availability::NO) assert(!ret.sat.stack.back().empty());
1383 
1384  // For 'd' nodes, a dissatisfaction must exist, and they must not need a signature. If it is non-malleable,
1385  // it must be canonical.
1386  if (node.GetType() << "d"_mst) assert(ret.nsat.available != Availability::NO);
1387  if (node.GetType() << "d"_mst) assert(!ret.nsat.has_sig);
1388  if (node.GetType() << "d"_mst && !ret.nsat.malleable) assert(!ret.nsat.non_canon);
1389 
1390  // For 'f'/'s' nodes, dissatisfactions/satisfactions must have a signature.
1391  if (node.GetType() << "f"_mst && ret.nsat.available != Availability::NO) assert(ret.nsat.has_sig);
1392  if (node.GetType() << "s"_mst && ret.sat.available != Availability::NO) assert(ret.sat.has_sig);
1393 
1394  // For non-malleable 'e' nodes, a non-malleable dissatisfaction must exist.
1395  if (node.GetType() << "me"_mst) assert(ret.nsat.available != Availability::NO);
1396  if (node.GetType() << "me"_mst) assert(!ret.nsat.malleable);
1397 
1398  // For 'm' nodes, if a satisfaction exists, it must be non-malleable.
1399  if (node.GetType() << "m"_mst && ret.sat.available != Availability::NO) assert(!ret.sat.malleable);
1400 
1401  // If a non-malleable satisfaction exists, it must be canonical.
1402  if (ret.sat.available != Availability::NO && !ret.sat.malleable) assert(!ret.sat.non_canon);
1403 
1404  return ret;
1405  };
1406 
1407  return TreeEval<InputResult>(tester);
1408  }
1409 
1410 public:
1416  template<typename Ctx> void DuplicateKeyCheck(const Ctx& ctx) const
1417  {
1418  // We cannot use a lambda here, as lambdas are non assignable, and the set operations
1419  // below require moving the comparators around.
1420  struct Comp {
1421  const Ctx* ctx_ptr;
1422  Comp(const Ctx& ctx) : ctx_ptr(&ctx) {}
1423  bool operator()(const Key& a, const Key& b) const { return ctx_ptr->KeyCompare(a, b); }
1424  };
1425 
1426  // state in the recursive computation:
1427  // - std::nullopt means "this node has duplicates"
1428  // - an std::set means "this node has no duplicate keys, and they are: ...".
1429  using keyset = std::set<Key, Comp>;
1430  using state = std::optional<keyset>;
1431 
1432  auto upfn = [&ctx](const Node& node, Span<state> subs) -> state {
1433  // If this node is already known to have duplicates, nothing left to do.
1434  if (node.has_duplicate_keys.has_value() && *node.has_duplicate_keys) return {};
1435 
1436  // Check if one of the children is already known to have duplicates.
1437  for (auto& sub : subs) {
1438  if (!sub.has_value()) {
1439  node.has_duplicate_keys = true;
1440  return {};
1441  }
1442  }
1443 
1444  // Start building the set of keys involved in this node and children.
1445  // Start by keys in this node directly.
1446  size_t keys_count = node.keys.size();
1447  keyset key_set{node.keys.begin(), node.keys.end(), Comp(ctx)};
1448  if (key_set.size() != keys_count) {
1449  // It already has duplicates; bail out.
1450  node.has_duplicate_keys = true;
1451  return {};
1452  }
1453 
1454  // Merge the keys from the children into this set.
1455  for (auto& sub : subs) {
1456  keys_count += sub->size();
1457  // Small optimization: std::set::merge is linear in the size of the second arg but
1458  // logarithmic in the size of the first.
1459  if (key_set.size() < sub->size()) std::swap(key_set, *sub);
1460  key_set.merge(*sub);
1461  if (key_set.size() != keys_count) {
1462  node.has_duplicate_keys = true;
1463  return {};
1464  }
1465  }
1466 
1467  node.has_duplicate_keys = false;
1468  return key_set;
1469  };
1470 
1471  TreeEval<state>(upfn);
1472  }
1473 
1475  size_t ScriptSize() const { return scriptlen; }
1476 
1478  std::optional<uint32_t> GetOps() const {
1479  if (!ops.sat.valid) return {};
1480  return ops.count + ops.sat.value;
1481  }
1482 
1484  uint32_t GetStaticOps() const { return ops.count; }
1485 
1487  bool CheckOpsLimit() const {
1488  if (IsTapscript(m_script_ctx)) return true;
1489  if (const auto ops = GetOps()) return *ops <= MAX_OPS_PER_SCRIPT;
1490  return true;
1491  }
1492 
1494  bool IsBKW() const {
1495  return !((GetType() & "BKW"_mst) == ""_mst);
1496  }
1497 
1499  std::optional<uint32_t> GetStackSize() const {
1500  if (!ss.sat.valid) return {};
1501  return ss.sat.netdiff + static_cast<int32_t>(IsBKW());
1502  }
1503 
1505  std::optional<uint32_t> GetExecStackSize() const {
1506  if (!ss.sat.valid) return {};
1507  return ss.sat.exec + static_cast<int32_t>(IsBKW());
1508  }
1509 
1511  bool CheckStackSize() const {
1512  // Since in Tapscript there is no standardness limit on the script and witness sizes, we may run
1513  // into the maximum stack size while executing the script. Make sure it doesn't happen.
1514  if (IsTapscript(m_script_ctx)) {
1515  if (const auto exec_ss = GetExecStackSize()) return exec_ss <= MAX_STACK_SIZE;
1516  return true;
1517  }
1518  if (const auto ss = GetStackSize()) return *ss <= MAX_STANDARD_P2WSH_STACK_ITEMS;
1519  return true;
1520  }
1521 
1523  bool IsNotSatisfiable() const { return !GetStackSize(); }
1524 
1527  std::optional<uint32_t> GetWitnessSize() const {
1528  if (!ws.sat.valid) return {};
1529  return ws.sat.value;
1530  }
1531 
1533  Type GetType() const { return typ; }
1534 
1537 
1539  const Node* FindInsaneSub() const {
1540  return TreeEval<const Node*>([](const Node& node, Span<const Node*> subs) -> const Node* {
1541  for (auto& sub: subs) if (sub) return sub;
1542  if (!node.IsSaneSubexpression()) return &node;
1543  return nullptr;
1544  });
1545  }
1546 
1549  template<typename F>
1550  bool IsSatisfiable(F fn) const
1551  {
1552  // TreeEval() doesn't support bool as NodeType, so use int instead.
1553  return TreeEval<int>([&fn](const Node& node, Span<int> subs) -> bool {
1554  switch (node.fragment) {
1555  case Fragment::JUST_0:
1556  return false;
1557  case Fragment::JUST_1:
1558  return true;
1559  case Fragment::PK_K:
1560  case Fragment::PK_H:
1561  case Fragment::MULTI:
1562  case Fragment::MULTI_A:
1563  case Fragment::AFTER:
1564  case Fragment::OLDER:
1565  case Fragment::HASH256:
1566  case Fragment::HASH160:
1567  case Fragment::SHA256:
1568  case Fragment::RIPEMD160:
1569  return bool{fn(node)};
1570  case Fragment::ANDOR:
1571  return (subs[0] && subs[1]) || subs[2];
1572  case Fragment::AND_V:
1573  case Fragment::AND_B:
1574  return subs[0] && subs[1];
1575  case Fragment::OR_B:
1576  case Fragment::OR_C:
1577  case Fragment::OR_D:
1578  case Fragment::OR_I:
1579  return subs[0] || subs[1];
1580  case Fragment::THRESH:
1581  return static_cast<uint32_t>(std::count(subs.begin(), subs.end(), true)) >= node.k;
1582  default: // wrappers
1583  assert(subs.size() == 1);
1584  return subs[0];
1585  }
1586  });
1587  }
1588 
1590  bool IsValid() const {
1591  if (GetType() == ""_mst) return false;
1593  }
1594 
1596  bool IsValidTopLevel() const { return IsValid() && GetType() << "B"_mst; }
1597 
1599  bool IsNonMalleable() const { return GetType() << "m"_mst; }
1600 
1602  bool NeedsSignature() const { return GetType() << "s"_mst; }
1603 
1605  bool CheckTimeLocksMix() const { return GetType() << "k"_mst; }
1606 
1609 
1611  bool ValidSatisfactions() const { return IsValid() && CheckOpsLimit() && CheckStackSize(); }
1612 
1615 
1617  bool IsSane() const { return IsValidTopLevel() && IsSaneSubexpression() && NeedsSignature(); }
1618 
1623  template<typename Ctx>
1624  Availability Satisfy(const Ctx& ctx, std::vector<std::vector<unsigned char>>& stack, bool nonmalleable = true) const {
1625  auto ret = ProduceInput(ctx);
1626  if (nonmalleable && (ret.sat.malleable || !ret.sat.has_sig)) return Availability::NO;
1627  stack = std::move(ret.sat.stack);
1628  return ret.sat.available;
1629  }
1630 
1632  bool operator==(const Node<Key>& arg) const { return Compare(*this, arg) == 0; }
1633 
1634  // Constructors with various argument combinations, which bypass the duplicate key check.
1635  Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<unsigned char> arg, uint32_t val = 0)
1636  : fragment(nt), k(val), data(std::move(arg)), subs(std::move(sub)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
1637  Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0)
1638  : fragment(nt), k(val), data(std::move(arg)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
1639  Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<Key> key, uint32_t val = 0)
1640  : fragment(nt), k(val), keys(std::move(key)), m_script_ctx{script_ctx}, subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
1641  Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, std::vector<Key> key, uint32_t val = 0)
1642  : fragment(nt), k(val), keys(std::move(key)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
1643  Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, std::vector<NodeRef<Key>> sub, uint32_t val = 0)
1644  : fragment(nt), k(val), subs(std::move(sub)), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
1645  Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, uint32_t val = 0)
1646  : fragment(nt), k(val), m_script_ctx{script_ctx}, ops(CalcOps()), ss(CalcStackSize()), ws(CalcWitnessSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
1647 
1648  // Constructors with various argument combinations, which do perform the duplicate key check.
1649  template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<unsigned char> arg, uint32_t val = 0)
1650  : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(sub), std::move(arg), val) { DuplicateKeyCheck(ctx); }
1651  template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0)
1652  : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(arg), val) { DuplicateKeyCheck(ctx);}
1653  template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<Key> key, uint32_t val = 0)
1654  : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(sub), std::move(key), val) { DuplicateKeyCheck(ctx); }
1655  template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<Key> key, uint32_t val = 0)
1656  : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(key), val) { DuplicateKeyCheck(ctx); }
1657  template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>> sub, uint32_t val = 0)
1658  : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, std::move(sub), val) { DuplicateKeyCheck(ctx); }
1659  template <typename Ctx> Node(const Ctx& ctx, Fragment nt, uint32_t val = 0)
1660  : Node(internal::NoDupCheck{}, ctx.MsContext(), nt, val) { DuplicateKeyCheck(ctx); }
1661 };
1662 
1663 namespace internal {
1664 
1665 enum class ParseContext {
1667  WRAPPED_EXPR,
1669  EXPR,
1670 
1672  SWAP,
1674  ALT,
1676  CHECK,
1678  DUP_IF,
1680  VERIFY,
1682  NON_ZERO,
1684  ZERO_NOTEQUAL,
1686  WRAP_U,
1688  WRAP_T,
1689 
1691  AND_N,
1693  AND_V,
1695  AND_B,
1697  ANDOR,
1699  OR_B,
1701  OR_C,
1703  OR_D,
1705  OR_I,
1706 
1711  THRESH,
1712 
1714  COMMA,
1716  CLOSE_BRACKET,
1717 };
1718 
1719 int FindNextChar(Span<const char> in, const char m);
1720 
1722 template<typename Key, typename Ctx>
1723 std::optional<std::pair<Key, int>> ParseKeyEnd(Span<const char> in, const Ctx& ctx)
1724 {
1725  int key_size = FindNextChar(in, ')');
1726  if (key_size < 1) return {};
1727  auto key = ctx.FromString(in.begin(), in.begin() + key_size);
1728  if (!key) return {};
1729  return {{std::move(*key), key_size}};
1730 }
1731 
1733 template<typename Ctx>
1734 std::optional<std::pair<std::vector<unsigned char>, int>> ParseHexStrEnd(Span<const char> in, const size_t expected_size,
1735  const Ctx& ctx)
1736 {
1737  int hash_size = FindNextChar(in, ')');
1738  if (hash_size < 1) return {};
1739  std::string val = std::string(in.begin(), in.begin() + hash_size);
1740  if (!IsHex(val)) return {};
1741  auto hash = ParseHex(val);
1742  if (hash.size() != expected_size) return {};
1743  return {{std::move(hash), hash_size}};
1744 }
1745 
1747 template<typename Key>
1748 void BuildBack(const MiniscriptContext script_ctx, Fragment nt, std::vector<NodeRef<Key>>& constructed, const bool reverse = false)
1749 {
1750  NodeRef<Key> child = std::move(constructed.back());
1751  constructed.pop_back();
1752  if (reverse) {
1753  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, script_ctx, nt, Vector(std::move(child), std::move(constructed.back())));
1754  } else {
1755  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, script_ctx, nt, Vector(std::move(constructed.back()), std::move(child)));
1756  }
1757 }
1758 
1764 template<typename Key, typename Ctx>
1765 inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
1766 {
1767  using namespace script;
1768 
1769  // Account for the minimum script size for all parsed fragments so far. It "borrows" 1
1770  // script byte from all leaf nodes, counting it instead whenever a space for a recursive
1771  // expression is added (through andor, and_*, or_*, thresh). This guarantees that all fragments
1772  // increment the script_size by at least one, except for:
1773  // - "0", "1": these leafs are only a single byte, so their subtracted-from increment is 0.
1774  // This is not an issue however, as "space" for them has to be created by combinators,
1775  // which do increment script_size.
1776  // - "v:": the v wrapper adds nothing as in some cases it results in no opcode being added
1777  // (instead transforming another opcode into its VERIFY form). However, the v: wrapper has
1778  // to be interleaved with other fragments to be valid, so this is not a concern.
1779  size_t script_size{1};
1780  size_t max_size{internal::MaxScriptSize(ctx.MsContext())};
1781 
1782  // The two integers are used to hold state for thresh()
1783  std::vector<std::tuple<ParseContext, int64_t, int64_t>> to_parse;
1784  std::vector<NodeRef<Key>> constructed;
1785 
1786  to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1787 
1788  // Parses a multi() or multi_a() from its string representation. Returns false on parsing error.
1789  const auto parse_multi_exp = [&](Span<const char>& in, const bool is_multi_a) -> bool {
1790  const auto max_keys{is_multi_a ? MAX_PUBKEYS_PER_MULTI_A : MAX_PUBKEYS_PER_MULTISIG};
1791  const auto required_ctx{is_multi_a ? MiniscriptContext::TAPSCRIPT : MiniscriptContext::P2WSH};
1792  if (ctx.MsContext() != required_ctx) return false;
1793  // Get threshold
1794  int next_comma = FindNextChar(in, ',');
1795  if (next_comma < 1) return false;
1796  int64_t k;
1797  if (!ParseInt64(std::string(in.begin(), in.begin() + next_comma), &k)) return false;
1798  in = in.subspan(next_comma + 1);
1799  // Get keys. It is compatible for both compressed and x-only keys.
1800  std::vector<Key> keys;
1801  while (next_comma != -1) {
1802  next_comma = FindNextChar(in, ',');
1803  int key_length = (next_comma == -1) ? FindNextChar(in, ')') : next_comma;
1804  if (key_length < 1) return false;
1805  auto key = ctx.FromString(in.begin(), in.begin() + key_length);
1806  if (!key) return false;
1807  keys.push_back(std::move(*key));
1808  in = in.subspan(key_length + 1);
1809  }
1810  if (keys.size() < 1 || keys.size() > max_keys) return false;
1811  if (k < 1 || k > (int64_t)keys.size()) return false;
1812  if (is_multi_a) {
1813  // (push + xonly-key + CHECKSIG[ADD]) * n + k + OP_NUMEQUAL(VERIFY), minus one.
1814  script_size += (1 + 32 + 1) * keys.size() + BuildScript(k).size();
1815  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI_A, std::move(keys), k));
1816  } else {
1817  script_size += 2 + (keys.size() > 16) + (k > 16) + 34 * keys.size();
1818  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI, std::move(keys), k));
1819  }
1820  return true;
1821  };
1822 
1823  while (!to_parse.empty()) {
1824  if (script_size > max_size) return {};
1825 
1826  // Get the current context we are decoding within
1827  auto [cur_context, n, k] = to_parse.back();
1828  to_parse.pop_back();
1829 
1830  switch (cur_context) {
1831  case ParseContext::WRAPPED_EXPR: {
1832  std::optional<size_t> colon_index{};
1833  for (size_t i = 1; i < in.size(); ++i) {
1834  if (in[i] == ':') {
1835  colon_index = i;
1836  break;
1837  }
1838  if (in[i] < 'a' || in[i] > 'z') break;
1839  }
1840  // If there is no colon, this loop won't execute
1841  bool last_was_v{false};
1842  for (size_t j = 0; colon_index && j < *colon_index; ++j) {
1843  if (script_size > max_size) return {};
1844  if (in[j] == 'a') {
1845  script_size += 2;
1846  to_parse.emplace_back(ParseContext::ALT, -1, -1);
1847  } else if (in[j] == 's') {
1848  script_size += 1;
1849  to_parse.emplace_back(ParseContext::SWAP, -1, -1);
1850  } else if (in[j] == 'c') {
1851  script_size += 1;
1852  to_parse.emplace_back(ParseContext::CHECK, -1, -1);
1853  } else if (in[j] == 'd') {
1854  script_size += 3;
1855  to_parse.emplace_back(ParseContext::DUP_IF, -1, -1);
1856  } else if (in[j] == 'j') {
1857  script_size += 4;
1858  to_parse.emplace_back(ParseContext::NON_ZERO, -1, -1);
1859  } else if (in[j] == 'n') {
1860  script_size += 1;
1861  to_parse.emplace_back(ParseContext::ZERO_NOTEQUAL, -1, -1);
1862  } else if (in[j] == 'v') {
1863  // do not permit "...vv...:"; it's not valid, and also doesn't trigger early
1864  // failure as script_size isn't incremented.
1865  if (last_was_v) return {};
1866  to_parse.emplace_back(ParseContext::VERIFY, -1, -1);
1867  } else if (in[j] == 'u') {
1868  script_size += 4;
1869  to_parse.emplace_back(ParseContext::WRAP_U, -1, -1);
1870  } else if (in[j] == 't') {
1871  script_size += 1;
1872  to_parse.emplace_back(ParseContext::WRAP_T, -1, -1);
1873  } else if (in[j] == 'l') {
1874  // The l: wrapper is equivalent to or_i(0,X)
1875  script_size += 4;
1876  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0));
1877  to_parse.emplace_back(ParseContext::OR_I, -1, -1);
1878  } else {
1879  return {};
1880  }
1881  last_was_v = (in[j] == 'v');
1882  }
1883  to_parse.emplace_back(ParseContext::EXPR, -1, -1);
1884  if (colon_index) in = in.subspan(*colon_index + 1);
1885  break;
1886  }
1887  case ParseContext::EXPR: {
1888  if (Const("0", in)) {
1889  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0));
1890  } else if (Const("1", in)) {
1891  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_1));
1892  } else if (Const("pk(", in)) {
1893  auto res = ParseKeyEnd<Key, Ctx>(in, ctx);
1894  if (!res) return {};
1895  auto& [key, key_size] = *res;
1896  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_C, Vector(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_K, Vector(std::move(key))))));
1897  in = in.subspan(key_size + 1);
1898  script_size += IsTapscript(ctx.MsContext()) ? 33 : 34;
1899  } else if (Const("pkh(", in)) {
1900  auto res = ParseKeyEnd<Key>(in, ctx);
1901  if (!res) return {};
1902  auto& [key, key_size] = *res;
1903  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_C, Vector(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_H, Vector(std::move(key))))));
1904  in = in.subspan(key_size + 1);
1905  script_size += 24;
1906  } else if (Const("pk_k(", in)) {
1907  auto res = ParseKeyEnd<Key>(in, ctx);
1908  if (!res) return {};
1909  auto& [key, key_size] = *res;
1910  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_K, Vector(std::move(key))));
1911  in = in.subspan(key_size + 1);
1912  script_size += IsTapscript(ctx.MsContext()) ? 32 : 33;
1913  } else if (Const("pk_h(", in)) {
1914  auto res = ParseKeyEnd<Key>(in, ctx);
1915  if (!res) return {};
1916  auto& [key, key_size] = *res;
1917  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_H, Vector(std::move(key))));
1918  in = in.subspan(key_size + 1);
1919  script_size += 23;
1920  } else if (Const("sha256(", in)) {
1921  auto res = ParseHexStrEnd(in, 32, ctx);
1922  if (!res) return {};
1923  auto& [hash, hash_size] = *res;
1924  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::SHA256, std::move(hash)));
1925  in = in.subspan(hash_size + 1);
1926  script_size += 38;
1927  } else if (Const("ripemd160(", in)) {
1928  auto res = ParseHexStrEnd(in, 20, ctx);
1929  if (!res) return {};
1930  auto& [hash, hash_size] = *res;
1931  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::RIPEMD160, std::move(hash)));
1932  in = in.subspan(hash_size + 1);
1933  script_size += 26;
1934  } else if (Const("hash256(", in)) {
1935  auto res = ParseHexStrEnd(in, 32, ctx);
1936  if (!res) return {};
1937  auto& [hash, hash_size] = *res;
1938  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::HASH256, std::move(hash)));
1939  in = in.subspan(hash_size + 1);
1940  script_size += 38;
1941  } else if (Const("hash160(", in)) {
1942  auto res = ParseHexStrEnd(in, 20, ctx);
1943  if (!res) return {};
1944  auto& [hash, hash_size] = *res;
1945  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::HASH160, std::move(hash)));
1946  in = in.subspan(hash_size + 1);
1947  script_size += 26;
1948  } else if (Const("after(", in)) {
1949  int arg_size = FindNextChar(in, ')');
1950  if (arg_size < 1) return {};
1951  int64_t num;
1952  if (!ParseInt64(std::string(in.begin(), in.begin() + arg_size), &num)) return {};
1953  if (num < 1 || num >= 0x80000000L) return {};
1954  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::AFTER, num));
1955  in = in.subspan(arg_size + 1);
1956  script_size += 1 + (num > 16) + (num > 0x7f) + (num > 0x7fff) + (num > 0x7fffff);
1957  } else if (Const("older(", in)) {
1958  int arg_size = FindNextChar(in, ')');
1959  if (arg_size < 1) return {};
1960  int64_t num;
1961  if (!ParseInt64(std::string(in.begin(), in.begin() + arg_size), &num)) return {};
1962  if (num < 1 || num >= 0x80000000L) return {};
1963  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::OLDER, num));
1964  in = in.subspan(arg_size + 1);
1965  script_size += 1 + (num > 16) + (num > 0x7f) + (num > 0x7fff) + (num > 0x7fffff);
1966  } else if (Const("multi(", in)) {
1967  if (!parse_multi_exp(in, /* is_multi_a = */false)) return {};
1968  } else if (Const("multi_a(", in)) {
1969  if (!parse_multi_exp(in, /* is_multi_a = */true)) return {};
1970  } else if (Const("thresh(", in)) {
1971  int next_comma = FindNextChar(in, ',');
1972  if (next_comma < 1) return {};
1973  if (!ParseInt64(std::string(in.begin(), in.begin() + next_comma), &k)) return {};
1974  if (k < 1) return {};
1975  in = in.subspan(next_comma + 1);
1976  // n = 1 here because we read the first WRAPPED_EXPR before reaching THRESH
1977  to_parse.emplace_back(ParseContext::THRESH, 1, k);
1978  to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1979  script_size += 2 + (k > 16) + (k > 0x7f) + (k > 0x7fff) + (k > 0x7fffff);
1980  } else if (Const("andor(", in)) {
1981  to_parse.emplace_back(ParseContext::ANDOR, -1, -1);
1982  to_parse.emplace_back(ParseContext::CLOSE_BRACKET, -1, -1);
1983  to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1984  to_parse.emplace_back(ParseContext::COMMA, -1, -1);
1985  to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1986  to_parse.emplace_back(ParseContext::COMMA, -1, -1);
1987  to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1988  script_size += 5;
1989  } else {
1990  if (Const("and_n(", in)) {
1991  to_parse.emplace_back(ParseContext::AND_N, -1, -1);
1992  script_size += 5;
1993  } else if (Const("and_b(", in)) {
1994  to_parse.emplace_back(ParseContext::AND_B, -1, -1);
1995  script_size += 2;
1996  } else if (Const("and_v(", in)) {
1997  to_parse.emplace_back(ParseContext::AND_V, -1, -1);
1998  script_size += 1;
1999  } else if (Const("or_b(", in)) {
2000  to_parse.emplace_back(ParseContext::OR_B, -1, -1);
2001  script_size += 2;
2002  } else if (Const("or_c(", in)) {
2003  to_parse.emplace_back(ParseContext::OR_C, -1, -1);
2004  script_size += 3;
2005  } else if (Const("or_d(", in)) {
2006  to_parse.emplace_back(ParseContext::OR_D, -1, -1);
2007  script_size += 4;
2008  } else if (Const("or_i(", in)) {
2009  to_parse.emplace_back(ParseContext::OR_I, -1, -1);
2010  script_size += 4;
2011  } else {
2012  return {};
2013  }
2014  to_parse.emplace_back(ParseContext::CLOSE_BRACKET, -1, -1);
2015  to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
2016  to_parse.emplace_back(ParseContext::COMMA, -1, -1);
2017  to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
2018  }
2019  break;
2020  }
2021  case ParseContext::ALT: {
2022  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_A, Vector(std::move(constructed.back())));
2023  break;
2024  }
2025  case ParseContext::SWAP: {
2026  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_S, Vector(std::move(constructed.back())));
2027  break;
2028  }
2029  case ParseContext::CHECK: {
2030  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_C, Vector(std::move(constructed.back())));
2031  break;
2032  }
2033  case ParseContext::DUP_IF: {
2034  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_D, Vector(std::move(constructed.back())));
2035  break;
2036  }
2037  case ParseContext::NON_ZERO: {
2038  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_J, Vector(std::move(constructed.back())));
2039  break;
2040  }
2041  case ParseContext::ZERO_NOTEQUAL: {
2042  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_N, Vector(std::move(constructed.back())));
2043  break;
2044  }
2045  case ParseContext::VERIFY: {
2046  script_size += (constructed.back()->GetType() << "x"_mst);
2047  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_V, Vector(std::move(constructed.back())));
2048  break;
2049  }
2050  case ParseContext::WRAP_U: {
2051  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::OR_I, Vector(std::move(constructed.back()), MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0)));
2052  break;
2053  }
2054  case ParseContext::WRAP_T: {
2055  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::AND_V, Vector(std::move(constructed.back()), MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_1)));
2056  break;
2057  }
2058  case ParseContext::AND_B: {
2059  BuildBack(ctx.MsContext(), Fragment::AND_B, constructed);
2060  break;
2061  }
2062  case ParseContext::AND_N: {
2063  auto mid = std::move(constructed.back());
2064  constructed.pop_back();
2065  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0)));
2066  break;
2067  }
2068  case ParseContext::AND_V: {
2069  BuildBack(ctx.MsContext(), Fragment::AND_V, constructed);
2070  break;
2071  }
2072  case ParseContext::OR_B: {
2073  BuildBack(ctx.MsContext(), Fragment::OR_B, constructed);
2074  break;
2075  }
2076  case ParseContext::OR_C: {
2077  BuildBack(ctx.MsContext(), Fragment::OR_C, constructed);
2078  break;
2079  }
2080  case ParseContext::OR_D: {
2081  BuildBack(ctx.MsContext(), Fragment::OR_D, constructed);
2082  break;
2083  }
2084  case ParseContext::OR_I: {
2085  BuildBack(ctx.MsContext(), Fragment::OR_I, constructed);
2086  break;
2087  }
2088  case ParseContext::ANDOR: {
2089  auto right = std::move(constructed.back());
2090  constructed.pop_back();
2091  auto mid = std::move(constructed.back());
2092  constructed.pop_back();
2093  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), std::move(right)));
2094  break;
2095  }
2096  case ParseContext::THRESH: {
2097  if (in.size() < 1) return {};
2098  if (in[0] == ',') {
2099  in = in.subspan(1);
2100  to_parse.emplace_back(ParseContext::THRESH, n+1, k);
2101  to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
2102  script_size += 2;
2103  } else if (in[0] == ')') {
2104  if (k > n) return {};
2105  in = in.subspan(1);
2106  // Children are constructed in reverse order, so iterate from end to beginning
2107  std::vector<NodeRef<Key>> subs;
2108  for (int i = 0; i < n; ++i) {
2109  subs.push_back(std::move(constructed.back()));
2110  constructed.pop_back();
2111  }
2112  std::reverse(subs.begin(), subs.end());
2113  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::THRESH, std::move(subs), k));
2114  } else {
2115  return {};
2116  }
2117  break;
2118  }
2119  case ParseContext::COMMA: {
2120  if (in.size() < 1 || in[0] != ',') return {};
2121  in = in.subspan(1);
2122  break;
2123  }
2124  case ParseContext::CLOSE_BRACKET: {
2125  if (in.size() < 1 || in[0] != ')') return {};
2126  in = in.subspan(1);
2127  break;
2128  }
2129  }
2130  }
2131 
2132  // Sanity checks on the produced miniscript
2133  assert(constructed.size() == 1);
2134  assert(constructed[0]->ScriptSize() == script_size);
2135  if (in.size() > 0) return {};
2136  NodeRef<Key> tl_node = std::move(constructed.front());
2137  tl_node->DuplicateKeyCheck(ctx);
2138  return tl_node;
2139 }
2140 
2149 std::optional<std::vector<Opcode>> DecomposeScript(const CScript& script);
2150 
2152 std::optional<int64_t> ParseScriptNumber(const Opcode& in);
2153 
2154 enum class DecodeContext {
2160  BKV_EXPR,
2162  W_EXPR,
2163 
2167  SWAP,
2170  ALT,
2172  CHECK,
2174  DUP_IF,
2176  VERIFY,
2178  NON_ZERO,
2180  ZERO_NOTEQUAL,
2181 
2186  MAYBE_AND_V,
2188  AND_V,
2190  AND_B,
2192  ANDOR,
2194  OR_B,
2196  OR_C,
2198  OR_D,
2199 
2203  THRESH_W,
2206  THRESH_E,
2207 
2211  ENDIF,
2215  ENDIF_NOTIF,
2219  ENDIF_ELSE,
2220 };
2221 
2223 template<typename Key, typename Ctx, typename I>
2224 inline NodeRef<Key> DecodeScript(I& in, I last, const Ctx& ctx)
2225 {
2226  // The two integers are used to hold state for thresh()
2227  std::vector<std::tuple<DecodeContext, int64_t, int64_t>> to_parse;
2228  std::vector<NodeRef<Key>> constructed;
2229 
2230  // This is the top level, so we assume the type is B
2231  // (in particular, disallowing top level W expressions)
2232  to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
2233 
2234  while (!to_parse.empty()) {
2235  // Exit early if the Miniscript is not going to be valid.
2236  if (!constructed.empty() && !constructed.back()->IsValid()) return {};
2237 
2238  // Get the current context we are decoding within
2239  auto [cur_context, n, k] = to_parse.back();
2240  to_parse.pop_back();
2241 
2242  switch(cur_context) {
2243  case DecodeContext::SINGLE_BKV_EXPR: {
2244  if (in >= last) return {};
2245 
2246  // Constants
2247  if (in[0].first == OP_1) {
2248  ++in;
2249  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_1));
2250  break;
2251  }
2252  if (in[0].first == OP_0) {
2253  ++in;
2254  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::JUST_0));
2255  break;
2256  }
2257  // Public keys
2258  if (in[0].second.size() == 33 || in[0].second.size() == 32) {
2259  auto key = ctx.FromPKBytes(in[0].second.begin(), in[0].second.end());
2260  if (!key) return {};
2261  ++in;
2262  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_K, Vector(std::move(*key))));
2263  break;
2264  }
2265  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) {
2266  auto key = ctx.FromPKHBytes(in[2].second.begin(), in[2].second.end());
2267  if (!key) return {};
2268  in += 5;
2269  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::PK_H, Vector(std::move(*key))));
2270  break;
2271  }
2272  // Time locks
2273  std::optional<int64_t> num;
2274  if (last - in >= 2 && in[0].first == OP_CHECKSEQUENCEVERIFY && (num = ParseScriptNumber(in[1]))) {
2275  in += 2;
2276  if (*num < 1 || *num > 0x7FFFFFFFL) return {};
2277  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::OLDER, *num));
2278  break;
2279  }
2280  if (last - in >= 2 && in[0].first == OP_CHECKLOCKTIMEVERIFY && (num = ParseScriptNumber(in[1]))) {
2281  in += 2;
2282  if (num < 1 || num > 0x7FFFFFFFL) return {};
2283  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::AFTER, *num));
2284  break;
2285  }
2286  // Hashes
2287  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) {
2288  if (in[2].first == OP_SHA256 && in[1].second.size() == 32) {
2289  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::SHA256, in[1].second));
2290  in += 7;
2291  break;
2292  } else if (in[2].first == OP_RIPEMD160 && in[1].second.size() == 20) {
2293  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::RIPEMD160, in[1].second));
2294  in += 7;
2295  break;
2296  } else if (in[2].first == OP_HASH256 && in[1].second.size() == 32) {
2297  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::HASH256, in[1].second));
2298  in += 7;
2299  break;
2300  } else if (in[2].first == OP_HASH160 && in[1].second.size() == 20) {
2301  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::HASH160, in[1].second));
2302  in += 7;
2303  break;
2304  }
2305  }
2306  // Multi
2307  if (last - in >= 3 && in[0].first == OP_CHECKMULTISIG) {
2308  if (IsTapscript(ctx.MsContext())) return {};
2309  std::vector<Key> keys;
2310  const auto n = ParseScriptNumber(in[1]);
2311  if (!n || last - in < 3 + *n) return {};
2312  if (*n < 1 || *n > 20) return {};
2313  for (int i = 0; i < *n; ++i) {
2314  if (in[2 + i].second.size() != 33) return {};
2315  auto key = ctx.FromPKBytes(in[2 + i].second.begin(), in[2 + i].second.end());
2316  if (!key) return {};
2317  keys.push_back(std::move(*key));
2318  }
2319  const auto k = ParseScriptNumber(in[2 + *n]);
2320  if (!k || *k < 1 || *k > *n) return {};
2321  in += 3 + *n;
2322  std::reverse(keys.begin(), keys.end());
2323  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI, std::move(keys), *k));
2324  break;
2325  }
2326  // Tapscript's equivalent of multi
2327  if (last - in >= 4 && in[0].first == OP_NUMEQUAL) {
2328  if (!IsTapscript(ctx.MsContext())) return {};
2329  // The necessary threshold of signatures.
2330  const auto k = ParseScriptNumber(in[1]);
2331  if (!k) return {};
2332  if (*k < 1 || *k > MAX_PUBKEYS_PER_MULTI_A) return {};
2333  if (last - in < 2 + *k * 2) return {};
2334  std::vector<Key> keys;
2335  keys.reserve(*k);
2336  // Walk through the expected (pubkey, CHECKSIG[ADD]) pairs.
2337  for (int pos = 2;; pos += 2) {
2338  if (last - in < pos + 2) return {};
2339  // Make sure it's indeed an x-only pubkey and a CHECKSIG[ADD], then parse the key.
2340  if (in[pos].first != OP_CHECKSIGADD && in[pos].first != OP_CHECKSIG) return {};
2341  if (in[pos + 1].second.size() != 32) return {};
2342  auto key = ctx.FromPKBytes(in[pos + 1].second.begin(), in[pos + 1].second.end());
2343  if (!key) return {};
2344  keys.push_back(std::move(*key));
2345  // Make sure early we don't parse an arbitrary large expression.
2346  if (keys.size() > MAX_PUBKEYS_PER_MULTI_A) return {};
2347  // OP_CHECKSIG means it was the last one to parse.
2348  if (in[pos].first == OP_CHECKSIG) break;
2349  }
2350  if (keys.size() < (size_t)*k) return {};
2351  in += 2 + keys.size() * 2;
2352  std::reverse(keys.begin(), keys.end());
2353  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::MULTI_A, std::move(keys), *k));
2354  break;
2355  }
2359  // c: wrapper
2360  if (in[0].first == OP_CHECKSIG) {
2361  ++in;
2362  to_parse.emplace_back(DecodeContext::CHECK, -1, -1);
2363  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2364  break;
2365  }
2366  // v: wrapper
2367  if (in[0].first == OP_VERIFY) {
2368  ++in;
2369  to_parse.emplace_back(DecodeContext::VERIFY, -1, -1);
2370  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2371  break;
2372  }
2373  // n: wrapper
2374  if (in[0].first == OP_0NOTEQUAL) {
2375  ++in;
2376  to_parse.emplace_back(DecodeContext::ZERO_NOTEQUAL, -1, -1);
2377  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2378  break;
2379  }
2380  // Thresh
2381  if (last - in >= 3 && in[0].first == OP_EQUAL && (num = ParseScriptNumber(in[1]))) {
2382  if (*num < 1) return {};
2383  in += 2;
2384  to_parse.emplace_back(DecodeContext::THRESH_W, 0, *num);
2385  break;
2386  }
2387  // OP_ENDIF can be WRAP_J, WRAP_D, ANDOR, OR_C, OR_D, or OR_I
2388  if (in[0].first == OP_ENDIF) {
2389  ++in;
2390  to_parse.emplace_back(DecodeContext::ENDIF, -1, -1);
2391  to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
2392  break;
2393  }
2399  // and_b
2400  if (in[0].first == OP_BOOLAND) {
2401  ++in;
2402  to_parse.emplace_back(DecodeContext::AND_B, -1, -1);
2403  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2404  to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
2405  break;
2406  }
2407  // or_b
2408  if (in[0].first == OP_BOOLOR) {
2409  ++in;
2410  to_parse.emplace_back(DecodeContext::OR_B, -1, -1);
2411  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2412  to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
2413  break;
2414  }
2415  // Unrecognised expression
2416  return {};
2417  }
2418  case DecodeContext::BKV_EXPR: {
2419  to_parse.emplace_back(DecodeContext::MAYBE_AND_V, -1, -1);
2420  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2421  break;
2422  }
2423  case DecodeContext::W_EXPR: {
2424  // a: wrapper
2425  if (in >= last) return {};
2426  if (in[0].first == OP_FROMALTSTACK) {
2427  ++in;
2428  to_parse.emplace_back(DecodeContext::ALT, -1, -1);
2429  } else {
2430  to_parse.emplace_back(DecodeContext::SWAP, -1, -1);
2431  }
2432  to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
2433  break;
2434  }
2435  case DecodeContext::MAYBE_AND_V: {
2436  // If we reach a potential AND_V top-level, check if the next part of the script could be another AND_V child
2437  // These op-codes cannot end any well-formed miniscript so cannot be used in an and_v node.
2438  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) {
2439  to_parse.emplace_back(DecodeContext::AND_V, -1, -1);
2440  // BKV_EXPR can contain more AND_V nodes
2441  to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
2442  }
2443  break;
2444  }
2445  case DecodeContext::SWAP: {
2446  if (in >= last || in[0].first != OP_SWAP || constructed.empty()) return {};
2447  ++in;
2448  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_S, Vector(std::move(constructed.back())));
2449  break;
2450  }
2451  case DecodeContext::ALT: {
2452  if (in >= last || in[0].first != OP_TOALTSTACK || constructed.empty()) return {};
2453  ++in;
2454  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_A, Vector(std::move(constructed.back())));
2455  break;
2456  }
2457  case DecodeContext::CHECK: {
2458  if (constructed.empty()) return {};
2459  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_C, Vector(std::move(constructed.back())));
2460  break;
2461  }
2462  case DecodeContext::DUP_IF: {
2463  if (constructed.empty()) return {};
2464  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_D, Vector(std::move(constructed.back())));
2465  break;
2466  }
2467  case DecodeContext::VERIFY: {
2468  if (constructed.empty()) return {};
2469  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_V, Vector(std::move(constructed.back())));
2470  break;
2471  }
2472  case DecodeContext::NON_ZERO: {
2473  if (constructed.empty()) return {};
2474  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_J, Vector(std::move(constructed.back())));
2475  break;
2476  }
2477  case DecodeContext::ZERO_NOTEQUAL: {
2478  if (constructed.empty()) return {};
2479  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::WRAP_N, Vector(std::move(constructed.back())));
2480  break;
2481  }
2482  case DecodeContext::AND_V: {
2483  if (constructed.size() < 2) return {};
2484  BuildBack(ctx.MsContext(), Fragment::AND_V, constructed, /*reverse=*/true);
2485  break;
2486  }
2487  case DecodeContext::AND_B: {
2488  if (constructed.size() < 2) return {};
2489  BuildBack(ctx.MsContext(), Fragment::AND_B, constructed, /*reverse=*/true);
2490  break;
2491  }
2492  case DecodeContext::OR_B: {
2493  if (constructed.size() < 2) return {};
2494  BuildBack(ctx.MsContext(), Fragment::OR_B, constructed, /*reverse=*/true);
2495  break;
2496  }
2497  case DecodeContext::OR_C: {
2498  if (constructed.size() < 2) return {};
2499  BuildBack(ctx.MsContext(), Fragment::OR_C, constructed, /*reverse=*/true);
2500  break;
2501  }
2502  case DecodeContext::OR_D: {
2503  if (constructed.size() < 2) return {};
2504  BuildBack(ctx.MsContext(), Fragment::OR_D, constructed, /*reverse=*/true);
2505  break;
2506  }
2507  case DecodeContext::ANDOR: {
2508  if (constructed.size() < 3) return {};
2509  NodeRef<Key> left = std::move(constructed.back());
2510  constructed.pop_back();
2511  NodeRef<Key> right = std::move(constructed.back());
2512  constructed.pop_back();
2513  NodeRef<Key> mid = std::move(constructed.back());
2514  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::ANDOR, Vector(std::move(left), std::move(mid), std::move(right)));
2515  break;
2516  }
2517  case DecodeContext::THRESH_W: {
2518  if (in >= last) return {};
2519  if (in[0].first == OP_ADD) {
2520  ++in;
2521  to_parse.emplace_back(DecodeContext::THRESH_W, n+1, k);
2522  to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
2523  } else {
2524  to_parse.emplace_back(DecodeContext::THRESH_E, n+1, k);
2525  // All children of thresh have type modifier d, so cannot be and_v
2526  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2527  }
2528  break;
2529  }
2530  case DecodeContext::THRESH_E: {
2531  if (k < 1 || k > n || constructed.size() < static_cast<size_t>(n)) return {};
2532  std::vector<NodeRef<Key>> subs;
2533  for (int i = 0; i < n; ++i) {
2534  NodeRef<Key> sub = std::move(constructed.back());
2535  constructed.pop_back();
2536  subs.push_back(std::move(sub));
2537  }
2538  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, ctx.MsContext(), Fragment::THRESH, std::move(subs), k));
2539  break;
2540  }
2541  case DecodeContext::ENDIF: {
2542  if (in >= last) return {};
2543 
2544  // could be andor or or_i
2545  if (in[0].first == OP_ELSE) {
2546  ++in;
2547  to_parse.emplace_back(DecodeContext::ENDIF_ELSE, -1, -1);
2548  to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
2549  }
2550  // could be j: or d: wrapper
2551  else if (in[0].first == OP_IF) {
2552  if (last - in >= 2 && in[1].first == OP_DUP) {
2553  in += 2;
2554  to_parse.emplace_back(DecodeContext::DUP_IF, -1, -1);
2555  } else if (last - in >= 3 && in[1].first == OP_0NOTEQUAL && in[2].first == OP_SIZE) {
2556  in += 3;
2557  to_parse.emplace_back(DecodeContext::NON_ZERO, -1, -1);
2558  }
2559  else {
2560  return {};
2561  }
2562  // could be or_c or or_d
2563  } else if (in[0].first == OP_NOTIF) {
2564  ++in;
2565  to_parse.emplace_back(DecodeContext::ENDIF_NOTIF, -1, -1);
2566  }
2567  else {
2568  return {};
2569  }
2570  break;
2571  }
2572  case DecodeContext::ENDIF_NOTIF: {
2573  if (in >= last) return {};
2574  if (in[0].first == OP_IFDUP) {
2575  ++in;
2576  to_parse.emplace_back(DecodeContext::OR_D, -1, -1);
2577  } else {
2578  to_parse.emplace_back(DecodeContext::OR_C, -1, -1);
2579  }
2580  // or_c and or_d both require X to have type modifier d so, can't contain and_v
2581  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2582  break;
2583  }
2584  case DecodeContext::ENDIF_ELSE: {
2585  if (in >= last) return {};
2586  if (in[0].first == OP_IF) {
2587  ++in;
2588  BuildBack(ctx.MsContext(), Fragment::OR_I, constructed, /*reverse=*/true);
2589  } else if (in[0].first == OP_NOTIF) {
2590  ++in;
2591  to_parse.emplace_back(DecodeContext::ANDOR, -1, -1);
2592  // andor requires X to have type modifier d, so it can't be and_v
2593  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2594  } else {
2595  return {};
2596  }
2597  break;
2598  }
2599  }
2600  }
2601  if (constructed.size() != 1) return {};
2602  NodeRef<Key> tl_node = std::move(constructed.front());
2603  tl_node->DuplicateKeyCheck(ctx);
2604  // Note that due to how ComputeType works (only assign the type to the node if the
2605  // subs' types are valid) this would fail if any node of tree is badly typed.
2606  if (!tl_node->IsValidTopLevel()) return {};
2607  return tl_node;
2608 }
2609 
2610 } // namespace internal
2611 
2612 template<typename Ctx>
2613 inline NodeRef<typename Ctx::Key> FromString(const std::string& str, const Ctx& ctx) {
2614  return internal::Parse<typename Ctx::Key>(str, ctx);
2615 }
2616 
2617 template<typename Ctx>
2618 inline NodeRef<typename Ctx::Key> FromScript(const CScript& script, const Ctx& ctx) {
2619  using namespace internal;
2620  // A too large Script is necessarily invalid, don't bother parsing it.
2621  if (script.size() > MaxScriptSize(ctx.MsContext())) return {};
2622  auto decomposed = DecomposeScript(script);
2623  if (!decomposed) return {};
2624  auto it = decomposed->begin();
2625  auto ret = DecodeScript<typename Ctx::Key>(it, decomposed->end(), ctx);
2626  if (!ret) return {};
2627  if (it != decomposed->end()) return {};
2628  return ret;
2629 }
2630 
2631 } // namespace miniscript
2632 
2633 #endif // BITCOIN_SCRIPT_MINISCRIPT_H
int ret
int flags
Definition: bitcoin-tx.cpp:533
ArgsManager & args
Definition: bitcoind.cpp:270
#define CHECK_NONFATAL(condition)
Identity function.
Definition: check.h:73
Serialized script, used inside transaction inputs and outputs.
Definition: script.h:414
A Span is an object that can refer to a contiguous sequence of objects.
Definition: span.h:98
constexpr std::size_t size() const noexcept
Definition: span.h:187
constexpr C * begin() const noexcept
Definition: span.h:175
CONSTEXPR_IF_NOT_DEBUG Span< C > last(std::size_t count) const noexcept
Definition: span.h:210
CONSTEXPR_IF_NOT_DEBUG Span< C > subspan(std::size_t offset) const noexcept
Definition: span.h:195
This type encapsulates the miniscript type system properties.
Definition: miniscript.h:122
static consteval Type Make(uint32_t flags) noexcept
Construction function used by the ""_mst operator.
Definition: miniscript.h:131
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:140
uint32_t m_flags
Internal bitmap of properties (see ""_mst operator for details).
Definition: miniscript.h:124
constexpr Type If(bool x) const
The empty type if x is false, itself otherwise.
Definition: miniscript.h:149
constexpr Type operator&(Type x) const
Compute the type with the intersection of properties.
Definition: miniscript.h:137
constexpr bool operator<(Type x) const
Comparison operator to enable use in sets/maps (total ordering incompatible with <<).
Definition: miniscript.h:143
constexpr Type operator|(Type x) const
Compute the type with the union of properties.
Definition: miniscript.h:134
constexpr bool operator==(Type x) const
Equality operator.
Definition: miniscript.h:146
constexpr Type(uint32_t flags) noexcept
Internal constructor.
Definition: miniscript.h:127
size_type size() const
Definition: prevector.h:296
static const int WITNESS_SCALE_FACTOR
Definition: consensus.h:21
uint256 Hash(const T &in1)
Compute the 256-bit hash of an object.
Definition: hash.h:75
std::string HexStr(const Span< const uint8_t > s)
Convert a span of bytes to a lower-case hexadecimal string.
Definition: hex_base.cpp:29
static constexpr size_t TAPROOT_CONTROL_MAX_SIZE
Definition: interpreter.h:236
#define CHECK(cond)
Unconditional failure on condition failure.
Definition: util.h:35
size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs, size_t n_keys, MiniscriptContext ms_ctx)
Helper function for Node::CalcScriptLen.
Definition: miniscript.cpp:262
int FindNextChar(Span< const char > sp, const char m)
Definition: miniscript.cpp:419
std::optional< int64_t > ParseScriptNumber(const Opcode &in)
Determine whether the passed pair (created by DecomposeScript) is pushing a number.
Definition: miniscript.cpp:406
Type SanitizeType(Type e)
A helper sanitizer/checker for the output of CalcType.
Definition: miniscript.cpp:16
std::optional< std::vector< Opcode > > DecomposeScript(const CScript &script)
Decode a script into opcode/push pairs.
Definition: miniscript.cpp:366
constexpr uint32_t TX_BODY_LEEWAY_WEIGHT
Data other than the witness in a transaction. Overhead + vin count + one vin + vout count + one vout ...
Definition: miniscript.h:261
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:1734
constexpr uint32_t TXIN_BYTES_NO_WITNESS
prevout + nSequence + scriptSig
Definition: miniscript.h:257
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:330
static const auto ZERO32
A stack consisting of a single malleable 32-byte 0x0000...0000 element (for dissatisfying hash challe...
Definition: miniscript.h:328
constexpr uint32_t MaxScriptSize(MiniscriptContext ms_ctx)
The maximum size of a script depending on the context.
Definition: miniscript.h:265
constexpr uint32_t TX_OVERHEAD
version + nLockTime
Definition: miniscript.h:255
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:326
constexpr uint32_t P2WSH_TXOUT_BYTES
nValue + script len + OP_0 + pushdata 32.
Definition: miniscript.h:259
void BuildBack(const MiniscriptContext script_ctx, 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:1748
@ VERIFY
VERIFY wraps the top constructed node with v:
@ 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:
@ COMMA
COMMA expects the next element to be ',' and fails if not.
@ DUP_IF
DUP_IF wraps the top constructed node with d:
@ 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.
@ 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:1723
static const auto INVALID
A stack representing the lack of any (dis)satisfactions.
Definition: miniscript.h:334
NodeRef< Key > Parse(Span< const char > in, const Ctx &ctx)
Parse a miniscript from its textual descriptor form.
Definition: miniscript.h:1765
@ SINGLE_BKV_EXPR
A single expression of type B, K, or V.
@ 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,...
@ W_EXPR
An expression of type W (a: or s: wrappers).
@ THRESH_E
THRESH_E constructs a thresh node from the appropriate number of constructed children.
@ ENDIF
ENDIF signals that we are inside some sort of OP_IF structure, which could be or_d,...
@ THRESH_W
In a thresh expression, all sub-expressions other than the first are W-type, and end in OP_ADD.
constexpr uint32_t MAX_TAPSCRIPT_SAT_SIZE
Maximum possible stack size to spend a Taproot output (excluding the script itself).
Definition: miniscript.h:263
static const auto EMPTY
The empty stack.
Definition: miniscript.h:332
Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector< Type > &sub_types, uint32_t k, size_t data_size, size_t n_subs, size_t n_keys, MiniscriptContext ms_ctx)
Helper function for Node::CalcType.
Definition: miniscript.cpp:36
static constexpr uint32_t MAX_TAPMINISCRIPT_STACK_ELEM_SIZE
The maximum size of a witness item for a Miniscript under Tapscript context. (A BIP340 signature with...
Definition: miniscript.h:252
NodeRef< Key > DecodeScript(I &in, I last, const Ctx &ctx)
Parse a miniscript from a bitcoin script.
Definition: miniscript.h:2224
std::shared_ptr< const Node< Key > > NodeRef
Definition: miniscript.h:187
constexpr bool IsTapscript(MiniscriptContext ms_ctx)
Whether the context Tapscript, ensuring the only other possibility is P2WSH.
Definition: miniscript.h:240
NodeRef< Key > MakeNodeRef(Args &&... args)
Construct a miniscript node as a shared_ptr.
Definition: miniscript.h:191
NodeRef< typename Ctx::Key > FromScript(const CScript &script, const Ctx &ctx)
Definition: miniscript.h:2618
NodeRef< typename Ctx::Key > FromString(const std::string &str, const Ctx &ctx)
Definition: miniscript.h:2613
std::pair< opcodetype, std::vector< unsigned char > > Opcode
Definition: miniscript.h:184
Fragment
The different node types in miniscript.
Definition: miniscript.h:194
@ OR_I
OP_IF [X] OP_ELSE [Y] OP_ENDIF.
@ MULTI_A
[key_0] OP_CHECKSIG ([key_n] OP_CHECKSIGADD)* [k] OP_NUMEQUAL (only within Tapscript ctx)
@ 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 (only available within P2WSH context)
Definition: messages.h:20
bool Const(const std::string &str, Span< const char > &sp)
Parse a constant.
Definition: parsing.cpp:15
std::string ToString(const T &t)
Locale-independent version of std::to_string.
Definition: string.h:148
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 int32_t MAX_STANDARD_TX_WEIGHT
The maximum weight for transactions we're willing to relay/mine.
Definition: policy.h:27
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:185
@ OP_BOOLAND
Definition: script.h:168
@ OP_CHECKMULTISIG
Definition: script.h:191
@ OP_IF
Definition: script.h:103
@ OP_SWAP
Definition: script.h:130
@ OP_CHECKSIG
Definition: script.h:189
@ OP_CHECKLOCKTIMEVERIFY
Definition: script.h:196
@ OP_EQUAL
Definition: script.h:145
@ OP_NUMEQUAL
Definition: script.h:170
@ OP_NOTIF
Definition: script.h:104
@ OP_SIZE
Definition: script.h:138
@ OP_ENDIF
Definition: script.h:108
@ OP_DUP
Definition: script.h:124
@ OP_TOALTSTACK
Definition: script.h:113
@ OP_RIPEMD160
Definition: script.h:183
@ OP_HASH256
Definition: script.h:187
@ OP_FROMALTSTACK
Definition: script.h:114
@ OP_NUMEQUALVERIFY
Definition: script.h:171
@ OP_HASH160
Definition: script.h:186
@ OP_1
Definition: script.h:82
@ OP_VERIFY
Definition: script.h:109
@ OP_ADD
Definition: script.h:160
@ OP_CHECKMULTISIGVERIFY
Definition: script.h:192
@ OP_BOOLOR
Definition: script.h:169
@ OP_CHECKSIGADD
Definition: script.h:209
@ OP_ELSE
Definition: script.h:107
@ OP_CHECKSIGVERIFY
Definition: script.h:190
@ OP_0NOTEQUAL
Definition: script.h:158
@ OP_0
Definition: script.h:75
@ OP_IFDUP
Definition: script.h:121
@ OP_EQUALVERIFY
Definition: script.h:146
@ OP_CHECKSEQUENCEVERIFY
Definition: script.h:198
static constexpr unsigned int MAX_PUBKEYS_PER_MULTI_A
The limit of keys in OP_CHECKSIGADD-based scripts.
Definition: script.h:36
static const int MAX_STACK_SIZE
Definition: script.h:42
static const int MAX_OPS_PER_SCRIPT
Definition: script.h:30
CScript BuildScript(Ts &&... inputs)
Build a script by concatenating other scripts, or any argument accepted by CScript::operator<<.
Definition: script.h:597
static const int MAX_PUBKEYS_PER_MULTISIG
Definition: script.h:33
static bool verify(const CScriptNum10 &bignum, const CScriptNum &scriptnum)
constexpr unsigned int GetSizeOfCompactSize(uint64_t nSize)
Compact Size size < 253 – 1 byte size <= USHRT_MAX – 3 bytes (253 + 2 bytes) size <= UINT_MAX – 5 byt...
Definition: serialize.h:295
std::vector< Byte > ParseHex(std::string_view hex_str)
Like TryParseHex, but returns an empty vector on invalid input.
Definition: strencodings.h:66
A node in a miniscript expression.
Definition: miniscript.h:499
const Type typ
Cached expression type (computed by CalcType and fed through SanitizeType).
Definition: miniscript.h:534
uint32_t GetStaticOps() const
Return the number of ops in the script (not counting the dynamic ones that depend on execution).
Definition: miniscript.h:1484
Result TreeEval(UpFn upfn) const
Like TreeEval, but without downfn or State type.
Definition: miniscript.h:674
bool IsBKW() const
Whether this node is of type B, K or W.
Definition: miniscript.h:1494
Node(const Ctx &ctx, Fragment nt, std::vector< NodeRef< Key >> sub, std::vector< unsigned char > arg, uint32_t val=0)
Definition: miniscript.h:1649
internal::InputResult ProduceInput(const Ctx &ctx) const
Definition: miniscript.h:1163
CScript ToScript(const Ctx &ctx) const
Definition: miniscript.h:726
bool CheckStackSize() const
Check the maximum stack size for this script against the policy limit.
Definition: miniscript.h:1511
internal::StackSize CalcStackSize() const
Definition: miniscript.h:994
bool IsSaneSubexpression() const
Whether the apparent policy of this node matches its script semantics. Doesn't guarantee it is a safe...
Definition: miniscript.h:1614
Type GetType() const
Return the expression type.
Definition: miniscript.h:1533
friend int Compare(const Node< Key > &node1, const Node< Key > &node2)
Compare two miniscript subtrees, using a non-recursive algorithm.
Definition: miniscript.h:687
const size_t scriptlen
Cached script length (computed by CalcScriptLen).
Definition: miniscript.h:536
std::optional< bool > has_duplicate_keys
Whether a public key appears more than once in this node.
Definition: miniscript.h:542
const uint32_t k
The k parameter (time for OLDER/AFTER, threshold for THRESH(_M))
Definition: miniscript.h:503
bool NeedsSignature() const
Check whether this script always needs a signature.
Definition: miniscript.h:1602
std::optional< Result > TreeEvalMaybe(UpFn upfn) const
Like TreeEvalMaybe, but without downfn or State type.
Definition: miniscript.h:645
bool CheckOpsLimit() const
Check the ops limit of this script against the consensus limit.
Definition: miniscript.h:1487
std::vector< NodeRef< Key > > subs
Subexpressions (for WRAP_*‍/AND_*‍/OR_*‍/ANDOR/THRESH)
Definition: miniscript.h:509
Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, std::vector< unsigned char > arg, uint32_t val=0)
Definition: miniscript.h:1637
const Fragment fragment
What node type this node is.
Definition: miniscript.h:501
Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, std::vector< NodeRef< Key >> sub, std::vector< unsigned char > arg, uint32_t val=0)
Definition: miniscript.h:1635
Node(const Ctx &ctx, Fragment nt, uint32_t val=0)
Definition: miniscript.h:1659
std::optional< uint32_t > GetExecStackSize() const
Return the maximum size of the stack during execution of this script.
Definition: miniscript.h:1505
const Node * FindInsaneSub() const
Find an insane subnode which has no insane children. Nullptr if there is none.
Definition: miniscript.h:1539
internal::WitnessSize CalcWitnessSize() const
Definition: miniscript.h:1109
Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, uint32_t val=0)
Definition: miniscript.h:1645
Result TreeEval(State root_state, DownFn &&downfn, UpFn upfn) const
Like TreeEvalMaybe, but always produces a result.
Definition: miniscript.h:658
internal::Ops CalcOps() const
Definition: miniscript.h:920
Node(const Ctx &ctx, Fragment nt, std::vector< NodeRef< Key >> sub, std::vector< Key > key, uint32_t val=0)
Definition: miniscript.h:1653
std::optional< uint32_t > GetStackSize() const
Return the maximum number of stack elements needed to satisfy this script non-malleably.
Definition: miniscript.h:1499
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:1624
const MiniscriptContext m_script_ctx
The Script context for this node. Either P2WSH or Tapscript.
Definition: miniscript.h:511
size_t CalcScriptLen() const
Compute the length of the script for this miniscript (including children).
Definition: miniscript.h:546
bool IsSane() const
Check whether this node is safe as a script on its own.
Definition: miniscript.h:1617
std::optional< uint32_t > GetOps() const
Return the maximum number of ops needed to satisfy this script non-malleably.
Definition: miniscript.h:1478
bool IsValidTopLevel() const
Check whether this node is valid as a script on its own.
Definition: miniscript.h:1596
bool IsNotSatisfiable() const
Whether no satisfaction exists for this node.
Definition: miniscript.h:1523
const internal::WitnessSize ws
Cached witness size bounds.
Definition: miniscript.h:532
bool IsNonMalleable() const
Check whether this script can always be satisfied in a non-malleable way.
Definition: miniscript.h:1599
Type CalcType() const
Compute the type for this miniscript.
Definition: miniscript.h:707
bool CheckDuplicateKey() const
Check whether there is no duplicate key across this fragment and all its sub-fragments.
Definition: miniscript.h:1608
Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, std::vector< NodeRef< Key >> sub, std::vector< Key > key, uint32_t val=0)
Definition: miniscript.h:1639
size_t ScriptSize() const
Return the size of the script for this expression (faster than ToScript().size()).
Definition: miniscript.h:1475
std::optional< uint32_t > GetWitnessSize() const
Return the maximum size in bytes of a witness to satisfy this script non-malleably.
Definition: miniscript.h:1527
Node(const Ctx &ctx, Fragment nt, std::vector< NodeRef< Key >> sub, uint32_t val=0)
Definition: miniscript.h:1657
bool ValidSatisfactions() const
Whether successful non-malleable satisfactions are guaranteed to be valid.
Definition: miniscript.h:1611
const std::vector< Key > keys
The keys used by this expression (only for PK_K/PK_H/MULTI)
Definition: miniscript.h:505
std::optional< Result > TreeEvalMaybe(State root_state, DownFn downfn, UpFn upfn) const
Definition: miniscript.h:580
std::optional< std::string > ToString(const CTx &ctx) const
Definition: miniscript.h:805
void DuplicateKeyCheck(const Ctx &ctx) const
Update duplicate key information in this Node.
Definition: miniscript.h:1416
Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, std::vector< NodeRef< Key >> sub, uint32_t val=0)
Definition: miniscript.h:1643
bool operator==(const Node< Key > &arg) const
Equality testing.
Definition: miniscript.h:1632
Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, std::vector< Key > key, uint32_t val=0)
Definition: miniscript.h:1641
bool CheckTimeLocksMix() const
Check whether there is no satisfaction path that contains both timelocks and heightlocks.
Definition: miniscript.h:1605
Node(const Ctx &ctx, Fragment nt, std::vector< Key > key, uint32_t val=0)
Definition: miniscript.h:1655
Node(const Ctx &ctx, Fragment nt, std::vector< unsigned char > arg, uint32_t val=0)
Definition: miniscript.h:1651
MiniscriptContext GetMsCtx() const
Return the script context for this node.
Definition: miniscript.h:1536
const internal::Ops ops
Cached ops counts.
Definition: miniscript.h:528
bool IsValid() const
Check whether this node is valid at all.
Definition: miniscript.h:1590
const std::vector< unsigned char > data
The data bytes in this expression (only for HASH160/HASH256/SHA256/RIPEMD10).
Definition: miniscript.h:507
const internal::StackSize ss
Cached stack size bounds.
Definition: miniscript.h:530
bool IsSatisfiable(F fn) const
Determine whether a Miniscript node is satisfiable.
Definition: miniscript.h:1550
A pair of a satisfaction and a dissatisfaction InputStack.
Definition: miniscript.h:337
InputResult(A &&in_nsat, B &&in_sat)
Definition: miniscript.h:341
An object representing a sequence of witness stack elements.
Definition: miniscript.h:289
bool malleable
Whether this stack is malleable (can be turned into an equally valid other stack by a third party).
Definition: miniscript.h:299
friend InputStack operator|(InputStack a, InputStack b)
Choose between two potential input stacks.
Definition: miniscript.cpp:337
friend InputStack operator+(InputStack a, InputStack b)
Concatenate two input stacks.
Definition: miniscript.cpp:323
std::vector< std::vector< unsigned char > > stack
Data elements.
Definition: miniscript.h:306
InputStack()=default
Construct an empty stack (valid).
bool has_sig
Whether this stack contains a digital signature.
Definition: miniscript.h:297
InputStack & SetAvailable(Availability avail)
Change availability.
Definition: miniscript.cpp:296
Availability available
Whether this stack is valid for its intended purpose (satisfaction or dissatisfaction of a Node).
Definition: miniscript.h:295
InputStack & SetMalleable(bool x=true)
Mark this input stack as malleable.
Definition: miniscript.cpp:318
size_t size
Serialized witness size.
Definition: miniscript.h:304
bool non_canon
Whether this stack is non-canonical (using a construction known to be unnecessary for satisfaction).
Definition: miniscript.h:302
InputStack(std::vector< unsigned char > in)
Construct a valid single-element stack (with an element up to 75 bytes).
Definition: miniscript.h:310
InputStack & SetWithSig()
Mark this input stack as having a signature.
Definition: miniscript.cpp:308
InputStack & SetNonCanon()
Mark this input stack as non-canonical (known to not be necessary in non-malleable satisfactions).
Definition: miniscript.cpp:313
Class whose objects represent the maximum of a list of integers.
Definition: miniscript.h:346
friend MaxInt< I > operator|(const MaxInt< I > &a, const MaxInt< I > &b)
Definition: miniscript.h:358
friend MaxInt< I > operator+(const MaxInt< I > &a, const MaxInt< I > &b)
Definition: miniscript.h:353
Ops(uint32_t in_count, MaxInt< uint32_t > in_sat, MaxInt< uint32_t > in_dsat)
Definition: miniscript.h:373
MaxInt< uint32_t > sat
Number of keys in possibly executed OP_CHECKMULTISIG(VERIFY)s to satisfy.
Definition: miniscript.h:369
MaxInt< uint32_t > dsat
Number of keys in possibly executed OP_CHECKMULTISIG(VERIFY)s to dissatisfy.
Definition: miniscript.h:371
uint32_t count
Non-push opcodes.
Definition: miniscript.h:367
A data structure to help the calculation of stack size limits.
Definition: miniscript.h:417
static constexpr SatInfo Nop() noexcept
A script consisting of just a repurposed nop (OP_CHECKLOCKTIMEVERIFY, OP_CHECKSEQUENCEVERIFY).
Definition: miniscript.h:460
const int32_t exec
Mow much higher the stack size can be during execution compared to at the end.
Definition: miniscript.h:423
static constexpr SatInfo OP_CHECKSIG() noexcept
Definition: miniscript.h:472
static constexpr SatInfo BinaryOp() noexcept
A script consisting of just a binary operator (OP_BOOLAND, OP_BOOLOR, OP_ADD).
Definition: miniscript.h:464
static constexpr SatInfo OP_VERIFY() noexcept
Definition: miniscript.h:474
static constexpr SatInfo Push() noexcept
A script consisting of a single push opcode.
Definition: miniscript.h:456
static constexpr SatInfo Empty() noexcept
The empty script.
Definition: miniscript.h:454
constexpr SatInfo(int32_t in_netdiff, int32_t in_exec) noexcept
Script set with a single script in it, with specified netdiff and exec.
Definition: miniscript.h:429
constexpr friend SatInfo operator|(const SatInfo &a, const SatInfo &b) noexcept
Script set union.
Definition: miniscript.h:433
const int32_t netdiff
How much higher the stack size at start of execution can be compared to at the end.
Definition: miniscript.h:421
constexpr SatInfo() noexcept
Empty script set.
Definition: miniscript.h:426
static constexpr SatInfo OP_EQUALVERIFY() noexcept
Definition: miniscript.h:469
static constexpr SatInfo OP_IFDUP(bool nonzero) noexcept
Definition: miniscript.h:468
const bool valid
Whether a canonical satisfaction/dissatisfaction is possible at all.
Definition: miniscript.h:419
static constexpr SatInfo OP_DUP() noexcept
Definition: miniscript.h:467
static constexpr SatInfo OP_0NOTEQUAL() noexcept
Definition: miniscript.h:473
static constexpr SatInfo If() noexcept
A script consisting of just OP_IF or OP_NOTIF.
Definition: miniscript.h:462
static constexpr SatInfo OP_EQUAL() noexcept
Definition: miniscript.h:470
static constexpr SatInfo OP_SIZE() noexcept
Definition: miniscript.h:471
static constexpr SatInfo Hash() noexcept
A script consisting of a single hash opcode.
Definition: miniscript.h:458
constexpr friend SatInfo operator+(const SatInfo &a, const SatInfo &b) noexcept
Script set concatenation.
Definition: miniscript.h:443
constexpr StackSize(SatInfo in_both) noexcept
Definition: miniscript.h:481
constexpr StackSize(SatInfo in_sat, SatInfo in_dsat) noexcept
Definition: miniscript.h:480
MaxInt< uint32_t > sat
Maximum witness size to satisfy;.
Definition: miniscript.h:486
MaxInt< uint32_t > dsat
Maximum witness size to dissatisfy;.
Definition: miniscript.h:488
WitnessSize(MaxInt< uint32_t > in_sat, MaxInt< uint32_t > in_dsat)
Definition: miniscript.h:490
static const std::vector< uint8_t > EMPTY
Definition: script.h:21
static int count
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:498
assert(!tx.IsCoinBase())
std::vector< typename std::common_type< Args... >::type > Vector(Args &&... args)
Construct a vector with the specified elements.
Definition: vector.h:23