Bitcoin Core  24.99.0
P2P Digital Currency
miniscript.h
Go to the documentation of this file.
1 // Copyright (c) 2019 The Bitcoin Core developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 
5 #ifndef BITCOIN_SCRIPT_MINISCRIPT_H
6 #define BITCOIN_SCRIPT_MINISCRIPT_H
7 
8 #include <algorithm>
9 #include <functional>
10 #include <numeric>
11 #include <memory>
12 #include <optional>
13 #include <string>
14 #include <vector>
15 
16 #include <assert.h>
17 #include <cstdlib>
18 
19 #include <policy/policy.h>
20 #include <primitives/transaction.h>
21 #include <script/script.h>
22 #include <span.h>
23 #include <util/spanparsing.h>
24 #include <util/strencodings.h>
25 #include <util/string.h>
26 #include <util/vector.h>
27 
28 namespace miniscript {
29 
121 class Type {
123  uint32_t m_flags;
124 
126  explicit constexpr Type(uint32_t flags) : m_flags(flags) {}
127 
128 public:
130  friend constexpr Type operator"" _mst(const char* c, size_t l);
131 
133  constexpr Type operator|(Type x) const { return Type(m_flags | x.m_flags); }
134 
136  constexpr Type operator&(Type x) const { return Type(m_flags & x.m_flags); }
137 
139  constexpr bool operator<<(Type x) const { return (x.m_flags & ~m_flags) == 0; }
140 
142  constexpr bool operator<(Type x) const { return m_flags < x.m_flags; }
143 
145  constexpr bool operator==(Type x) const { return m_flags == x.m_flags; }
146 
148  constexpr Type If(bool x) const { return Type(x ? m_flags : 0); }
149 };
150 
152 inline constexpr Type operator"" _mst(const char* c, size_t l) {
153  Type typ{0};
154 
155  for (const char *p = c; p < c + l; p++) {
156  typ = typ | Type(
157  *p == 'B' ? 1 << 0 : // Base type
158  *p == 'V' ? 1 << 1 : // Verify type
159  *p == 'K' ? 1 << 2 : // Key type
160  *p == 'W' ? 1 << 3 : // Wrapped type
161  *p == 'z' ? 1 << 4 : // Zero-arg property
162  *p == 'o' ? 1 << 5 : // One-arg property
163  *p == 'n' ? 1 << 6 : // Nonzero arg property
164  *p == 'd' ? 1 << 7 : // Dissatisfiable property
165  *p == 'u' ? 1 << 8 : // Unit property
166  *p == 'e' ? 1 << 9 : // Expression property
167  *p == 'f' ? 1 << 10 : // Forced property
168  *p == 's' ? 1 << 11 : // Safe property
169  *p == 'm' ? 1 << 12 : // Nonmalleable property
170  *p == 'x' ? 1 << 13 : // Expensive verify
171  *p == 'g' ? 1 << 14 : // older: contains relative time timelock (csv_time)
172  *p == 'h' ? 1 << 15 : // older: contains relative height timelock (csv_height)
173  *p == 'i' ? 1 << 16 : // after: contains time timelock (cltv_time)
174  *p == 'j' ? 1 << 17 : // after: contains height timelock (cltv_height)
175  *p == 'k' ? 1 << 18 : // does not contain a combination of height and time locks
176  (throw std::logic_error("Unknown character in _mst literal"), 0)
177  );
178  }
179 
180  return typ;
181 }
182 
183 using Opcode = std::pair<opcodetype, std::vector<unsigned char>>;
184 
185 template<typename Key> struct Node;
186 template<typename Key> using NodeRef = std::shared_ptr<const Node<Key>>;
187 
189 template<typename Key, typename... Args>
190 NodeRef<Key> MakeNodeRef(Args&&... args) { return std::make_shared<const Node<Key>>(std::forward<Args>(args)...); }
191 
193 enum class Fragment {
194  JUST_0,
195  JUST_1,
196  PK_K,
197  PK_H,
198  OLDER,
199  AFTER,
200  SHA256,
201  HASH256,
202  RIPEMD160,
203  HASH160,
204  WRAP_A,
205  WRAP_S,
206  WRAP_C,
207  WRAP_D,
208  WRAP_V,
209  WRAP_J,
210  WRAP_N,
211  AND_V,
212  AND_B,
213  OR_B,
214  OR_C,
215  OR_D,
216  OR_I,
217  ANDOR,
218  THRESH,
219  MULTI,
220  // AND_N(X,Y) is represented as ANDOR(X,Y,0)
221  // WRAP_T(X) is represented as AND_V(X,1)
222  // WRAP_L(X) is represented as OR_I(0,X)
223  // WRAP_U(X) is represented as OR_I(X,0)
224 };
225 
226 
227 namespace internal {
228 
230 Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Type>& sub_types, uint32_t k, size_t data_size, size_t n_subs, size_t n_keys);
231 
233 size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs, size_t n_keys);
234 
236 Type SanitizeType(Type x);
237 
239 template<typename I>
240 struct MaxInt {
241  const bool valid;
242  const I value;
243 
244  MaxInt() : valid(false), value(0) {}
245  MaxInt(I val) : valid(true), value(val) {}
246 
247  friend MaxInt<I> operator+(const MaxInt<I>& a, const MaxInt<I>& b) {
248  if (!a.valid || !b.valid) return {};
249  return a.value + b.value;
250  }
251 
252  friend MaxInt<I> operator|(const MaxInt<I>& a, const MaxInt<I>& b) {
253  if (!a.valid) return b;
254  if (!b.valid) return a;
255  return std::max(a.value, b.value);
256  }
257 };
258 
259 struct Ops {
261  uint32_t count;
266 
267  Ops(uint32_t in_count, MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : count(in_count), sat(in_sat), dsat(in_dsat) {};
268 };
269 
270 struct StackSize {
275 
276  StackSize(MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : sat(in_sat), dsat(in_dsat) {};
277 };
278 
279 struct NoDupCheck {};
280 
281 } // namespace internal
282 
284 template<typename Key>
285 struct Node {
289  const uint32_t k = 0;
291  const std::vector<Key> keys;
293  const std::vector<unsigned char> data;
295  const std::vector<NodeRef<Key>> subs;
296 
297 private:
303  const Type typ;
305  const size_t scriptlen;
311  mutable std::optional<bool> has_duplicate_keys;
312 
313 
315  size_t CalcScriptLen() const {
316  size_t subsize = 0;
317  for (const auto& sub : subs) {
318  subsize += sub->ScriptSize();
319  }
320  Type sub0type = subs.size() > 0 ? subs[0]->GetType() : ""_mst;
321  return internal::ComputeScriptLen(fragment, sub0type, subsize, k, subs.size(), keys.size());
322  }
323 
324  /* Apply a recursive algorithm to a Miniscript tree, without actual recursive calls.
325  *
326  * The algorithm is defined by two functions: downfn and upfn. Conceptually, the
327  * result can be thought of as first using downfn to compute a "state" for each node,
328  * from the root down to the leaves. Then upfn is used to compute a "result" for each
329  * node, from the leaves back up to the root, which is then returned. In the actual
330  * implementation, both functions are invoked in an interleaved fashion, performing a
331  * depth-first traversal of the tree.
332  *
333  * In more detail, it is invoked as node.TreeEvalMaybe<Result>(root, downfn, upfn):
334  * - root is the state of the root node, of type State.
335  * - downfn is a callable (State&, const Node&, size_t) -> State, which given a
336  * node, its state, and an index of one of its children, computes the state of that
337  * child. It can modify the state. Children of a given node will have downfn()
338  * called in order.
339  * - upfn is a callable (State&&, const Node&, Span<Result>) -> std::optional<Result>,
340  * which given a node, its state, and a Span of the results of its children,
341  * computes the result of the node. If std::nullopt is returned by upfn,
342  * TreeEvalMaybe() immediately returns std::nullopt.
343  * The return value of TreeEvalMaybe is the result of the root node.
344  *
345  * Result type cannot be bool due to the std::vector<bool> specialization.
346  */
347  template<typename Result, typename State, typename DownFn, typename UpFn>
348  std::optional<Result> TreeEvalMaybe(State root_state, DownFn downfn, UpFn upfn) const
349  {
351  struct StackElem
352  {
353  const Node& node;
354  size_t expanded;
355  State state;
356 
357  StackElem(const Node& node_, size_t exp_, State&& state_) :
358  node(node_), expanded(exp_), state(std::move(state_)) {}
359  };
360  /* Stack of tree nodes being explored. */
361  std::vector<StackElem> stack;
362  /* Results of subtrees so far. Their order and mapping to tree nodes
363  * is implicitly defined by stack. */
364  std::vector<Result> results;
365  stack.emplace_back(*this, 0, std::move(root_state));
366 
367  /* Here is a demonstration of the algorithm, for an example tree A(B,C(D,E),F).
368  * State variables are omitted for simplicity.
369  *
370  * First: stack=[(A,0)] results=[]
371  * stack=[(A,1),(B,0)] results=[]
372  * stack=[(A,1)] results=[B]
373  * stack=[(A,2),(C,0)] results=[B]
374  * stack=[(A,2),(C,1),(D,0)] results=[B]
375  * stack=[(A,2),(C,1)] results=[B,D]
376  * stack=[(A,2),(C,2),(E,0)] results=[B,D]
377  * stack=[(A,2),(C,2)] results=[B,D,E]
378  * stack=[(A,2)] results=[B,C]
379  * stack=[(A,3),(F,0)] results=[B,C]
380  * stack=[(A,3)] results=[B,C,F]
381  * Final: stack=[] results=[A]
382  */
383  while (stack.size()) {
384  const Node& node = stack.back().node;
385  if (stack.back().expanded < node.subs.size()) {
386  /* We encounter a tree node with at least one unexpanded child.
387  * Expand it. By the time we hit this node again, the result of
388  * that child (and all earlier children) will be at the end of `results`. */
389  size_t child_index = stack.back().expanded++;
390  State child_state = downfn(stack.back().state, node, child_index);
391  stack.emplace_back(*node.subs[child_index], 0, std::move(child_state));
392  continue;
393  }
394  // Invoke upfn with the last node.subs.size() elements of results as input.
395  assert(results.size() >= node.subs.size());
396  std::optional<Result> result{upfn(std::move(stack.back().state), node,
397  Span<Result>{results}.last(node.subs.size()))};
398  // If evaluation returns std::nullopt, abort immediately.
399  if (!result) return {};
400  // Replace the last node.subs.size() elements of results with the new result.
401  results.erase(results.end() - node.subs.size(), results.end());
402  results.push_back(std::move(*result));
403  stack.pop_back();
404  }
405  // The final remaining results element is the root result, return it.
406  assert(results.size() == 1);
407  return std::move(results[0]);
408  }
409 
412  template<typename Result, typename UpFn>
413  std::optional<Result> TreeEvalMaybe(UpFn upfn) const
414  {
415  struct DummyState {};
416  return TreeEvalMaybe<Result>(DummyState{},
417  [](DummyState, const Node&, size_t) { return DummyState{}; },
418  [&upfn](DummyState, const Node& node, Span<Result> subs) {
419  return upfn(node, subs);
420  }
421  );
422  }
423 
425  template<typename Result, typename State, typename DownFn, typename UpFn>
426  Result TreeEval(State root_state, DownFn&& downfn, UpFn upfn) const
427  {
428  // Invoke TreeEvalMaybe with upfn wrapped to return std::optional<Result>, and then
429  // unconditionally dereference the result (it cannot be std::nullopt).
430  return std::move(*TreeEvalMaybe<Result>(std::move(root_state),
431  std::forward<DownFn>(downfn),
432  [&upfn](State&& state, const Node& node, Span<Result> subs) {
433  Result res{upfn(std::move(state), node, subs)};
434  return std::optional<Result>(std::move(res));
435  }
436  ));
437  }
438 
441  template<typename Result, typename UpFn>
442  Result TreeEval(UpFn upfn) const
443  {
444  struct DummyState {};
445  return std::move(*TreeEvalMaybe<Result>(DummyState{},
446  [](DummyState, const Node&, size_t) { return DummyState{}; },
447  [&upfn](DummyState, const Node& node, Span<Result> subs) {
448  Result res{upfn(node, subs)};
449  return std::optional<Result>(std::move(res));
450  }
451  ));
452  }
453 
455  friend int Compare(const Node<Key>& node1, const Node<Key>& node2)
456  {
457  std::vector<std::pair<const Node<Key>&, const Node<Key>&>> queue;
458  queue.emplace_back(node1, node2);
459  while (!queue.empty()) {
460  const auto& [a, b] = queue.back();
461  queue.pop_back();
462  if (std::tie(a.fragment, a.k, a.keys, a.data) < std::tie(b.fragment, b.k, b.keys, b.data)) return -1;
463  if (std::tie(b.fragment, b.k, b.keys, b.data) < std::tie(a.fragment, a.k, a.keys, a.data)) return 1;
464  if (a.subs.size() < b.subs.size()) return -1;
465  if (b.subs.size() < a.subs.size()) return 1;
466  size_t n = a.subs.size();
467  for (size_t i = 0; i < n; ++i) {
468  queue.emplace_back(*a.subs[n - 1 - i], *b.subs[n - 1 - i]);
469  }
470  }
471  return 0;
472  }
473 
475  Type CalcType() const {
476  using namespace internal;
477 
478  // THRESH has a variable number of subexpressions
479  std::vector<Type> sub_types;
480  if (fragment == Fragment::THRESH) {
481  for (const auto& sub : subs) sub_types.push_back(sub->GetType());
482  }
483  // All other nodes than THRESH can be computed just from the types of the 0-3 subexpressions.
484  Type x = subs.size() > 0 ? subs[0]->GetType() : ""_mst;
485  Type y = subs.size() > 1 ? subs[1]->GetType() : ""_mst;
486  Type z = subs.size() > 2 ? subs[2]->GetType() : ""_mst;
487 
488  return SanitizeType(ComputeType(fragment, x, y, z, sub_types, k, data.size(), subs.size(), keys.size()));
489  }
490 
491 public:
492  template<typename Ctx>
493  CScript ToScript(const Ctx& ctx) const
494  {
495  // To construct the CScript for a Miniscript object, we use the TreeEval algorithm.
496  // The State is a boolean: whether or not the node's script expansion is followed
497  // by an OP_VERIFY (which may need to be combined with the last script opcode).
498  auto downfn = [](bool verify, const Node& node, size_t index) {
499  // For WRAP_V, the subexpression is certainly followed by OP_VERIFY.
500  if (node.fragment == Fragment::WRAP_V) return true;
501  // The subexpression of WRAP_S, and the last subexpression of AND_V
502  // inherit the followed-by-OP_VERIFY property from the parent.
503  if (node.fragment == Fragment::WRAP_S ||
504  (node.fragment == Fragment::AND_V && index == 1)) return verify;
505  return false;
506  };
507  // The upward function computes for a node, given its followed-by-OP_VERIFY status
508  // and the CScripts of its child nodes, the CScript of the node.
509  auto upfn = [&ctx](bool verify, const Node& node, Span<CScript> subs) -> CScript {
510  switch (node.fragment) {
511  case Fragment::PK_K: return BuildScript(ctx.ToPKBytes(node.keys[0]));
512  case Fragment::PK_H: return BuildScript(OP_DUP, OP_HASH160, ctx.ToPKHBytes(node.keys[0]), OP_EQUALVERIFY);
520  case Fragment::WRAP_S: return BuildScript(OP_SWAP, subs[0]);
521  case Fragment::WRAP_C: return BuildScript(std::move(subs[0]), verify ? OP_CHECKSIGVERIFY : OP_CHECKSIG);
523  case Fragment::WRAP_V: {
524  if (node.subs[0]->GetType() << "x"_mst) {
525  return BuildScript(std::move(subs[0]), OP_VERIFY);
526  } else {
527  return std::move(subs[0]);
528  }
529  }
531  case Fragment::WRAP_N: return BuildScript(std::move(subs[0]), OP_0NOTEQUAL);
532  case Fragment::JUST_1: return BuildScript(OP_1);
533  case Fragment::JUST_0: return BuildScript(OP_0);
534  case Fragment::AND_V: return BuildScript(std::move(subs[0]), subs[1]);
535  case Fragment::AND_B: return BuildScript(std::move(subs[0]), subs[1], OP_BOOLAND);
536  case Fragment::OR_B: return BuildScript(std::move(subs[0]), subs[1], OP_BOOLOR);
537  case Fragment::OR_D: return BuildScript(std::move(subs[0]), OP_IFDUP, OP_NOTIF, subs[1], OP_ENDIF);
538  case Fragment::OR_C: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[1], OP_ENDIF);
539  case Fragment::OR_I: return BuildScript(OP_IF, subs[0], OP_ELSE, subs[1], OP_ENDIF);
540  case Fragment::ANDOR: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[2], OP_ELSE, subs[1], OP_ENDIF);
541  case Fragment::MULTI: {
542  CScript script = BuildScript(node.k);
543  for (const auto& key : node.keys) {
544  script = BuildScript(std::move(script), ctx.ToPKBytes(key));
545  }
546  return BuildScript(std::move(script), node.keys.size(), verify ? OP_CHECKMULTISIGVERIFY : OP_CHECKMULTISIG);
547  }
548  case Fragment::THRESH: {
549  CScript script = std::move(subs[0]);
550  for (size_t i = 1; i < subs.size(); ++i) {
551  script = BuildScript(std::move(script), subs[i], OP_ADD);
552  }
553  return BuildScript(std::move(script), node.k, verify ? OP_EQUALVERIFY : OP_EQUAL);
554  }
555  }
556  assert(false);
557  };
558  return TreeEval<CScript>(false, downfn, upfn);
559  }
560 
561  template<typename CTx>
562  std::optional<std::string> ToString(const CTx& ctx) const {
563  // To construct the std::string representation for a Miniscript object, we use
564  // the TreeEvalMaybe algorithm. The State is a boolean: whether the parent node is a
565  // wrapper. If so, non-wrapper expressions must be prefixed with a ":".
566  auto downfn = [](bool, const Node& node, size_t) {
567  return (node.fragment == Fragment::WRAP_A || node.fragment == Fragment::WRAP_S ||
568  node.fragment == Fragment::WRAP_D || node.fragment == Fragment::WRAP_V ||
569  node.fragment == Fragment::WRAP_J || node.fragment == Fragment::WRAP_N ||
570  node.fragment == Fragment::WRAP_C ||
571  (node.fragment == Fragment::AND_V && node.subs[1]->fragment == Fragment::JUST_1) ||
572  (node.fragment == Fragment::OR_I && node.subs[0]->fragment == Fragment::JUST_0) ||
573  (node.fragment == Fragment::OR_I && node.subs[1]->fragment == Fragment::JUST_0));
574  };
575  // The upward function computes for a node, given whether its parent is a wrapper,
576  // and the string representations of its child nodes, the string representation of the node.
577  auto upfn = [&ctx](bool wrapped, const Node& node, Span<std::string> subs) -> std::optional<std::string> {
578  std::string ret = wrapped ? ":" : "";
579 
580  switch (node.fragment) {
581  case Fragment::WRAP_A: return "a" + std::move(subs[0]);
582  case Fragment::WRAP_S: return "s" + std::move(subs[0]);
583  case Fragment::WRAP_C:
584  if (node.subs[0]->fragment == Fragment::PK_K) {
585  // pk(K) is syntactic sugar for c:pk_k(K)
586  auto key_str = ctx.ToString(node.subs[0]->keys[0]);
587  if (!key_str) return {};
588  return std::move(ret) + "pk(" + std::move(*key_str) + ")";
589  }
590  if (node.subs[0]->fragment == Fragment::PK_H) {
591  // pkh(K) is syntactic sugar for c:pk_h(K)
592  auto key_str = ctx.ToString(node.subs[0]->keys[0]);
593  if (!key_str) return {};
594  return std::move(ret) + "pkh(" + std::move(*key_str) + ")";
595  }
596  return "c" + std::move(subs[0]);
597  case Fragment::WRAP_D: return "d" + std::move(subs[0]);
598  case Fragment::WRAP_V: return "v" + std::move(subs[0]);
599  case Fragment::WRAP_J: return "j" + std::move(subs[0]);
600  case Fragment::WRAP_N: return "n" + std::move(subs[0]);
601  case Fragment::AND_V:
602  // t:X is syntactic sugar for and_v(X,1).
603  if (node.subs[1]->fragment == Fragment::JUST_1) return "t" + std::move(subs[0]);
604  break;
605  case Fragment::OR_I:
606  if (node.subs[0]->fragment == Fragment::JUST_0) return "l" + std::move(subs[1]);
607  if (node.subs[1]->fragment == Fragment::JUST_0) return "u" + std::move(subs[0]);
608  break;
609  default: break;
610  }
611  switch (node.fragment) {
612  case Fragment::PK_K: {
613  auto key_str = ctx.ToString(node.keys[0]);
614  if (!key_str) return {};
615  return std::move(ret) + "pk_k(" + std::move(*key_str) + ")";
616  }
617  case Fragment::PK_H: {
618  auto key_str = ctx.ToString(node.keys[0]);
619  if (!key_str) return {};
620  return std::move(ret) + "pk_h(" + std::move(*key_str) + ")";
621  }
622  case Fragment::AFTER: return std::move(ret) + "after(" + ::ToString(node.k) + ")";
623  case Fragment::OLDER: return std::move(ret) + "older(" + ::ToString(node.k) + ")";
624  case Fragment::HASH256: return std::move(ret) + "hash256(" + HexStr(node.data) + ")";
625  case Fragment::HASH160: return std::move(ret) + "hash160(" + HexStr(node.data) + ")";
626  case Fragment::SHA256: return std::move(ret) + "sha256(" + HexStr(node.data) + ")";
627  case Fragment::RIPEMD160: return std::move(ret) + "ripemd160(" + HexStr(node.data) + ")";
628  case Fragment::JUST_1: return std::move(ret) + "1";
629  case Fragment::JUST_0: return std::move(ret) + "0";
630  case Fragment::AND_V: return std::move(ret) + "and_v(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
631  case Fragment::AND_B: return std::move(ret) + "and_b(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
632  case Fragment::OR_B: return std::move(ret) + "or_b(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
633  case Fragment::OR_D: return std::move(ret) + "or_d(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
634  case Fragment::OR_C: return std::move(ret) + "or_c(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
635  case Fragment::OR_I: return std::move(ret) + "or_i(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
636  case Fragment::ANDOR:
637  // and_n(X,Y) is syntactic sugar for andor(X,Y,0).
638  if (node.subs[2]->fragment == Fragment::JUST_0) return std::move(ret) + "and_n(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
639  return std::move(ret) + "andor(" + std::move(subs[0]) + "," + std::move(subs[1]) + "," + std::move(subs[2]) + ")";
640  case Fragment::MULTI: {
641  auto str = std::move(ret) + "multi(" + ::ToString(node.k);
642  for (const auto& key : node.keys) {
643  auto key_str = ctx.ToString(key);
644  if (!key_str) return {};
645  str += "," + std::move(*key_str);
646  }
647  return std::move(str) + ")";
648  }
649  case Fragment::THRESH: {
650  auto str = std::move(ret) + "thresh(" + ::ToString(node.k);
651  for (auto& sub : subs) {
652  str += "," + std::move(sub);
653  }
654  return std::move(str) + ")";
655  }
656  default: break;
657  }
658  assert(false);
659  };
660 
661  return TreeEvalMaybe<std::string>(false, downfn, upfn);
662  }
663 
664 private:
666  switch (fragment) {
667  case Fragment::JUST_1: return {0, 0, {}};
668  case Fragment::JUST_0: return {0, {}, 0};
669  case Fragment::PK_K: return {0, 0, 0};
670  case Fragment::PK_H: return {3, 0, 0};
671  case Fragment::OLDER:
672  case Fragment::AFTER: return {1, 0, {}};
673  case Fragment::SHA256:
674  case Fragment::RIPEMD160:
675  case Fragment::HASH256:
676  case Fragment::HASH160: return {4, 0, {}};
677  case Fragment::AND_V: return {subs[0]->ops.count + subs[1]->ops.count, subs[0]->ops.sat + subs[1]->ops.sat, {}};
678  case Fragment::AND_B: {
679  const auto count{1 + subs[0]->ops.count + subs[1]->ops.count};
680  const auto sat{subs[0]->ops.sat + subs[1]->ops.sat};
681  const auto dsat{subs[0]->ops.dsat + subs[1]->ops.dsat};
682  return {count, sat, dsat};
683  }
684  case Fragment::OR_B: {
685  const auto count{1 + subs[0]->ops.count + subs[1]->ops.count};
686  const auto sat{(subs[0]->ops.sat + subs[1]->ops.dsat) | (subs[1]->ops.sat + subs[0]->ops.dsat)};
687  const auto dsat{subs[0]->ops.dsat + subs[1]->ops.dsat};
688  return {count, sat, dsat};
689  }
690  case Fragment::OR_D: {
691  const auto count{3 + subs[0]->ops.count + subs[1]->ops.count};
692  const auto sat{subs[0]->ops.sat | (subs[1]->ops.sat + subs[0]->ops.dsat)};
693  const auto dsat{subs[0]->ops.dsat + subs[1]->ops.dsat};
694  return {count, sat, dsat};
695  }
696  case Fragment::OR_C: {
697  const auto count{2 + subs[0]->ops.count + subs[1]->ops.count};
698  const auto sat{subs[0]->ops.sat | (subs[1]->ops.sat + subs[0]->ops.dsat)};
699  return {count, sat, {}};
700  }
701  case Fragment::OR_I: {
702  const auto count{3 + subs[0]->ops.count + subs[1]->ops.count};
703  const auto sat{subs[0]->ops.sat | subs[1]->ops.sat};
704  const auto dsat{subs[0]->ops.dsat | subs[1]->ops.dsat};
705  return {count, sat, dsat};
706  }
707  case Fragment::ANDOR: {
708  const auto count{3 + subs[0]->ops.count + subs[1]->ops.count + subs[2]->ops.count};
709  const auto sat{(subs[1]->ops.sat + subs[0]->ops.sat) | (subs[0]->ops.dsat + subs[2]->ops.sat)};
710  const auto dsat{subs[0]->ops.dsat + subs[2]->ops.dsat};
711  return {count, sat, dsat};
712  }
713  case Fragment::MULTI: return {1, (uint32_t)keys.size(), (uint32_t)keys.size()};
714  case Fragment::WRAP_S:
715  case Fragment::WRAP_C:
716  case Fragment::WRAP_N: return {1 + subs[0]->ops.count, subs[0]->ops.sat, subs[0]->ops.dsat};
717  case Fragment::WRAP_A: return {2 + subs[0]->ops.count, subs[0]->ops.sat, subs[0]->ops.dsat};
718  case Fragment::WRAP_D: return {3 + subs[0]->ops.count, subs[0]->ops.sat, 0};
719  case Fragment::WRAP_J: return {4 + subs[0]->ops.count, subs[0]->ops.sat, 0};
720  case Fragment::WRAP_V: return {subs[0]->ops.count + (subs[0]->GetType() << "x"_mst), subs[0]->ops.sat, {}};
721  case Fragment::THRESH: {
722  uint32_t count = 0;
723  auto sats = Vector(internal::MaxInt<uint32_t>(0));
724  for (const auto& sub : subs) {
725  count += sub->ops.count + 1;
726  auto next_sats = Vector(sats[0] + sub->ops.dsat);
727  for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub->ops.dsat) | (sats[j - 1] + sub->ops.sat));
728  next_sats.push_back(sats[sats.size() - 1] + sub->ops.sat);
729  sats = std::move(next_sats);
730  }
731  assert(k <= sats.size());
732  return {count, sats[k], sats[0]};
733  }
734  }
735  assert(false);
736  }
737 
739  switch (fragment) {
740  case Fragment::JUST_0: return {{}, 0};
741  case Fragment::JUST_1:
742  case Fragment::OLDER:
743  case Fragment::AFTER: return {0, {}};
744  case Fragment::PK_K: return {1, 1};
745  case Fragment::PK_H: return {2, 2};
746  case Fragment::SHA256:
747  case Fragment::RIPEMD160:
748  case Fragment::HASH256:
749  case Fragment::HASH160: return {1, {}};
750  case Fragment::ANDOR: {
751  const auto sat{(subs[0]->ss.sat + subs[1]->ss.sat) | (subs[0]->ss.dsat + subs[2]->ss.sat)};
752  const auto dsat{subs[0]->ss.dsat + subs[2]->ss.dsat};
753  return {sat, dsat};
754  }
755  case Fragment::AND_V: return {subs[0]->ss.sat + subs[1]->ss.sat, {}};
756  case Fragment::AND_B: return {subs[0]->ss.sat + subs[1]->ss.sat, subs[0]->ss.dsat + subs[1]->ss.dsat};
757  case Fragment::OR_B: {
758  const auto sat{(subs[0]->ss.dsat + subs[1]->ss.sat) | (subs[0]->ss.sat + subs[1]->ss.dsat)};
759  const auto dsat{subs[0]->ss.dsat + subs[1]->ss.dsat};
760  return {sat, dsat};
761  }
762  case Fragment::OR_C: return {subs[0]->ss.sat | (subs[0]->ss.dsat + subs[1]->ss.sat), {}};
763  case Fragment::OR_D: return {subs[0]->ss.sat | (subs[0]->ss.dsat + subs[1]->ss.sat), subs[0]->ss.dsat + subs[1]->ss.dsat};
764  case Fragment::OR_I: return {(subs[0]->ss.sat + 1) | (subs[1]->ss.sat + 1), (subs[0]->ss.dsat + 1) | (subs[1]->ss.dsat + 1)};
765  case Fragment::MULTI: return {k + 1, k + 1};
766  case Fragment::WRAP_A:
767  case Fragment::WRAP_N:
768  case Fragment::WRAP_S:
769  case Fragment::WRAP_C: return subs[0]->ss;
770  case Fragment::WRAP_D: return {1 + subs[0]->ss.sat, 1};
771  case Fragment::WRAP_V: return {subs[0]->ss.sat, {}};
772  case Fragment::WRAP_J: return {subs[0]->ss.sat, 1};
773  case Fragment::THRESH: {
774  auto sats = Vector(internal::MaxInt<uint32_t>(0));
775  for (const auto& sub : subs) {
776  auto next_sats = Vector(sats[0] + sub->ss.dsat);
777  for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub->ss.dsat) | (sats[j - 1] + sub->ss.sat));
778  next_sats.push_back(sats[sats.size() - 1] + sub->ss.sat);
779  sats = std::move(next_sats);
780  }
781  assert(k <= sats.size());
782  return {sats[k], sats[0]};
783  }
784  }
785  assert(false);
786  }
787 
788 public:
794  template<typename Ctx> void DuplicateKeyCheck(const Ctx& ctx) const
795  {
796  // We cannot use a lambda here, as lambdas are non assignable, and the set operations
797  // below require moving the comparators around.
798  struct Comp {
799  const Ctx* ctx_ptr;
800  Comp(const Ctx& ctx) : ctx_ptr(&ctx) {}
801  bool operator()(const Key& a, const Key& b) const { return ctx_ptr->KeyCompare(a, b); }
802  };
803 
804  // state in the recursive computation:
805  // - std::nullopt means "this node has duplicates"
806  // - an std::set means "this node has no duplicate keys, and they are: ...".
807  using keyset = std::set<Key, Comp>;
808  using state = std::optional<keyset>;
809 
810  auto upfn = [&ctx](const Node& node, Span<state> subs) -> state {
811  // If this node is already known to have duplicates, nothing left to do.
812  if (node.has_duplicate_keys.has_value() && *node.has_duplicate_keys) return {};
813 
814  // Check if one of the children is already known to have duplicates.
815  for (auto& sub : subs) {
816  if (!sub.has_value()) {
817  node.has_duplicate_keys = true;
818  return {};
819  }
820  }
821 
822  // Start building the set of keys involved in this node and children.
823  // Start by keys in this node directly.
824  size_t keys_count = node.keys.size();
825  keyset key_set{node.keys.begin(), node.keys.end(), Comp(ctx)};
826  if (key_set.size() != keys_count) {
827  // It already has duplicates; bail out.
828  node.has_duplicate_keys = true;
829  return {};
830  }
831 
832  // Merge the keys from the children into this set.
833  for (auto& sub : subs) {
834  keys_count += sub->size();
835  // Small optimization: std::set::merge is linear in the size of the second arg but
836  // logarithmic in the size of the first.
837  if (key_set.size() < sub->size()) std::swap(key_set, *sub);
838  key_set.merge(*sub);
839  if (key_set.size() != keys_count) {
840  node.has_duplicate_keys = true;
841  return {};
842  }
843  }
844 
845  node.has_duplicate_keys = false;
846  return key_set;
847  };
848 
849  TreeEval<state>(upfn);
850  }
851 
853  size_t ScriptSize() const { return scriptlen; }
854 
856  uint32_t GetOps() const { return ops.count + ops.sat.value; }
857 
859  bool CheckOpsLimit() const { return GetOps() <= MAX_OPS_PER_SCRIPT; }
860 
863  uint32_t GetStackSize() const { return ss.sat.value + 1; }
864 
867 
869  Type GetType() const { return typ; }
870 
872  const Node* FindInsaneSub() const {
873  return TreeEval<const Node*>([](const Node& node, Span<const Node*> subs) -> const Node* {
874  for (auto& sub: subs) if (sub) return sub;
875  if (!node.IsSaneSubexpression()) return &node;
876  return nullptr;
877  });
878  }
879 
881  bool IsValid() const { return !(GetType() == ""_mst) && ScriptSize() <= MAX_STANDARD_P2WSH_SCRIPT_SIZE; }
882 
884  bool IsValidTopLevel() const { return IsValid() && GetType() << "B"_mst; }
885 
887  bool IsNonMalleable() const { return GetType() << "m"_mst; }
888 
890  bool NeedsSignature() const { return GetType() << "s"_mst; }
891 
893  bool CheckTimeLocksMix() const { return GetType() << "k"_mst; }
894 
897 
899  bool ValidSatisfactions() const { return IsValid() && CheckOpsLimit() && CheckStackSize(); }
900 
903 
905  bool IsSane() const { return IsValidTopLevel() && IsSaneSubexpression() && NeedsSignature(); }
906 
908  bool operator==(const Node<Key>& arg) const { return Compare(*this, arg) == 0; }
909 
910  // Constructors with various argument combinations, which bypass the duplicate key check.
911  Node(internal::NoDupCheck, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<unsigned char> arg, uint32_t val = 0) : fragment(nt), k(val), data(std::move(arg)), subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
912  Node(internal::NoDupCheck, Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0) : fragment(nt), k(val), data(std::move(arg)), ops(CalcOps()), ss(CalcStackSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
913  Node(internal::NoDupCheck, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<Key> key, uint32_t val = 0) : fragment(nt), k(val), keys(std::move(key)), subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
914  Node(internal::NoDupCheck, Fragment nt, std::vector<Key> key, uint32_t val = 0) : fragment(nt), k(val), keys(std::move(key)), ops(CalcOps()), ss(CalcStackSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
915  Node(internal::NoDupCheck, Fragment nt, std::vector<NodeRef<Key>> sub, uint32_t val = 0) : fragment(nt), k(val), subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
916  Node(internal::NoDupCheck, Fragment nt, uint32_t val = 0) : fragment(nt), k(val), ops(CalcOps()), ss(CalcStackSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
917 
918  // Constructors with various argument combinations, which do perform the duplicate key check.
919  template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<unsigned char> arg, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, std::move(sub), std::move(arg), val) { DuplicateKeyCheck(ctx); }
920  template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, std::move(arg), val) { DuplicateKeyCheck(ctx);}
921  template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<Key> key, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, std::move(sub), std::move(key), val) { DuplicateKeyCheck(ctx); }
922  template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<Key> key, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, std::move(key), val) { DuplicateKeyCheck(ctx); }
923  template <typename Ctx> Node(const Ctx& ctx, Fragment nt, std::vector<NodeRef<Key>> sub, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, std::move(sub), val) { DuplicateKeyCheck(ctx); }
924  template <typename Ctx> Node(const Ctx& ctx, Fragment nt, uint32_t val = 0) : Node(internal::NoDupCheck{}, nt, val) { DuplicateKeyCheck(ctx); }
925 };
926 
927 namespace internal {
928 
929 enum class ParseContext {
931  WRAPPED_EXPR,
933  EXPR,
934 
936  SWAP,
938  ALT,
940  CHECK,
942  DUP_IF,
944  VERIFY,
946  NON_ZERO,
950  WRAP_U,
952  WRAP_T,
953 
955  AND_N,
957  AND_V,
959  AND_B,
961  ANDOR,
963  OR_B,
965  OR_C,
967  OR_D,
969  OR_I,
970 
975  THRESH,
976 
978  COMMA,
981 };
982 
983 int FindNextChar(Span<const char> in, const char m);
984 
986 template<typename Key, typename Ctx>
987 std::optional<std::pair<Key, int>> ParseKeyEnd(Span<const char> in, const Ctx& ctx)
988 {
989  int key_size = FindNextChar(in, ')');
990  if (key_size < 1) return {};
991  auto key = ctx.FromString(in.begin(), in.begin() + key_size);
992  if (!key) return {};
993  return {{std::move(*key), key_size}};
994 }
995 
997 template<typename Ctx>
998 std::optional<std::pair<std::vector<unsigned char>, int>> ParseHexStrEnd(Span<const char> in, const size_t expected_size,
999  const Ctx& ctx)
1000 {
1001  int hash_size = FindNextChar(in, ')');
1002  if (hash_size < 1) return {};
1003  std::string val = std::string(in.begin(), in.begin() + hash_size);
1004  if (!IsHex(val)) return {};
1005  auto hash = ParseHex(val);
1006  if (hash.size() != expected_size) return {};
1007  return {{std::move(hash), hash_size}};
1008 }
1009 
1011 template<typename Key>
1012 void BuildBack(Fragment nt, std::vector<NodeRef<Key>>& constructed, const bool reverse = false)
1013 {
1014  NodeRef<Key> child = std::move(constructed.back());
1015  constructed.pop_back();
1016  if (reverse) {
1017  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, nt, Vector(std::move(child), std::move(constructed.back())));
1018  } else {
1019  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, nt, Vector(std::move(constructed.back()), std::move(child)));
1020  }
1021 }
1022 
1028 template<typename Key, typename Ctx>
1029 inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
1030 {
1031  using namespace spanparsing;
1032 
1033  // Account for the minimum script size for all parsed fragments so far. It "borrows" 1
1034  // script byte from all leaf nodes, counting it instead whenever a space for a recursive
1035  // expression is added (through andor, and_*, or_*, thresh). This guarantees that all fragments
1036  // increment the script_size by at least one, except for:
1037  // - "0", "1": these leafs are only a single byte, so their subtracted-from increment is 0.
1038  // This is not an issue however, as "space" for them has to be created by combinators,
1039  // which do increment script_size.
1040  // - "v:": the v wrapper adds nothing as in some cases it results in no opcode being added
1041  // (instead transforming another opcode into its VERIFY form). However, the v: wrapper has
1042  // to be interleaved with other fragments to be valid, so this is not a concern.
1043  size_t script_size{1};
1044 
1045  // The two integers are used to hold state for thresh()
1046  std::vector<std::tuple<ParseContext, int64_t, int64_t>> to_parse;
1047  std::vector<NodeRef<Key>> constructed;
1048 
1049  to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1050 
1051  while (!to_parse.empty()) {
1052  if (script_size > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
1053 
1054  // Get the current context we are decoding within
1055  auto [cur_context, n, k] = to_parse.back();
1056  to_parse.pop_back();
1057 
1058  switch (cur_context) {
1060  std::optional<size_t> colon_index{};
1061  for (size_t i = 1; i < in.size(); ++i) {
1062  if (in[i] == ':') {
1063  colon_index = i;
1064  break;
1065  }
1066  if (in[i] < 'a' || in[i] > 'z') break;
1067  }
1068  // If there is no colon, this loop won't execute
1069  bool last_was_v{false};
1070  for (size_t j = 0; colon_index && j < *colon_index; ++j) {
1071  if (script_size > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
1072  if (in[j] == 'a') {
1073  script_size += 2;
1074  to_parse.emplace_back(ParseContext::ALT, -1, -1);
1075  } else if (in[j] == 's') {
1076  script_size += 1;
1077  to_parse.emplace_back(ParseContext::SWAP, -1, -1);
1078  } else if (in[j] == 'c') {
1079  script_size += 1;
1080  to_parse.emplace_back(ParseContext::CHECK, -1, -1);
1081  } else if (in[j] == 'd') {
1082  script_size += 3;
1083  to_parse.emplace_back(ParseContext::DUP_IF, -1, -1);
1084  } else if (in[j] == 'j') {
1085  script_size += 4;
1086  to_parse.emplace_back(ParseContext::NON_ZERO, -1, -1);
1087  } else if (in[j] == 'n') {
1088  script_size += 1;
1089  to_parse.emplace_back(ParseContext::ZERO_NOTEQUAL, -1, -1);
1090  } else if (in[j] == 'v') {
1091  // do not permit "...vv...:"; it's not valid, and also doesn't trigger early
1092  // failure as script_size isn't incremented.
1093  if (last_was_v) return {};
1094  to_parse.emplace_back(ParseContext::VERIFY, -1, -1);
1095  } else if (in[j] == 'u') {
1096  script_size += 4;
1097  to_parse.emplace_back(ParseContext::WRAP_U, -1, -1);
1098  } else if (in[j] == 't') {
1099  script_size += 1;
1100  to_parse.emplace_back(ParseContext::WRAP_T, -1, -1);
1101  } else if (in[j] == 'l') {
1102  // The l: wrapper is equivalent to or_i(0,X)
1103  script_size += 4;
1104  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_0));
1105  to_parse.emplace_back(ParseContext::OR_I, -1, -1);
1106  } else {
1107  return {};
1108  }
1109  last_was_v = (in[j] == 'v');
1110  }
1111  to_parse.emplace_back(ParseContext::EXPR, -1, -1);
1112  if (colon_index) in = in.subspan(*colon_index + 1);
1113  break;
1114  }
1115  case ParseContext::EXPR: {
1116  if (Const("0", in)) {
1117  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_0));
1118  } else if (Const("1", in)) {
1119  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_1));
1120  } else if (Const("pk(", in)) {
1121  auto res = ParseKeyEnd<Key, Ctx>(in, ctx);
1122  if (!res) return {};
1123  auto& [key, key_size] = *res;
1124  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_C, Vector(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_K, Vector(std::move(key))))));
1125  in = in.subspan(key_size + 1);
1126  script_size += 34;
1127  } else if (Const("pkh(", in)) {
1128  auto res = ParseKeyEnd<Key>(in, ctx);
1129  if (!res) return {};
1130  auto& [key, key_size] = *res;
1131  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_C, Vector(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_H, Vector(std::move(key))))));
1132  in = in.subspan(key_size + 1);
1133  script_size += 24;
1134  } else if (Const("pk_k(", in)) {
1135  auto res = ParseKeyEnd<Key>(in, ctx);
1136  if (!res) return {};
1137  auto& [key, key_size] = *res;
1138  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_K, Vector(std::move(key))));
1139  in = in.subspan(key_size + 1);
1140  script_size += 33;
1141  } else if (Const("pk_h(", in)) {
1142  auto res = ParseKeyEnd<Key>(in, ctx);
1143  if (!res) return {};
1144  auto& [key, key_size] = *res;
1145  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_H, Vector(std::move(key))));
1146  in = in.subspan(key_size + 1);
1147  script_size += 23;
1148  } else if (Const("sha256(", in)) {
1149  auto res = ParseHexStrEnd(in, 32, ctx);
1150  if (!res) return {};
1151  auto& [hash, hash_size] = *res;
1152  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::SHA256, std::move(hash)));
1153  in = in.subspan(hash_size + 1);
1154  script_size += 38;
1155  } else if (Const("ripemd160(", in)) {
1156  auto res = ParseHexStrEnd(in, 20, ctx);
1157  if (!res) return {};
1158  auto& [hash, hash_size] = *res;
1159  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::RIPEMD160, std::move(hash)));
1160  in = in.subspan(hash_size + 1);
1161  script_size += 26;
1162  } else if (Const("hash256(", in)) {
1163  auto res = ParseHexStrEnd(in, 32, ctx);
1164  if (!res) return {};
1165  auto& [hash, hash_size] = *res;
1166  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::HASH256, std::move(hash)));
1167  in = in.subspan(hash_size + 1);
1168  script_size += 38;
1169  } else if (Const("hash160(", in)) {
1170  auto res = ParseHexStrEnd(in, 20, ctx);
1171  if (!res) return {};
1172  auto& [hash, hash_size] = *res;
1173  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::HASH160, std::move(hash)));
1174  in = in.subspan(hash_size + 1);
1175  script_size += 26;
1176  } else if (Const("after(", in)) {
1177  int arg_size = FindNextChar(in, ')');
1178  if (arg_size < 1) return {};
1179  int64_t num;
1180  if (!ParseInt64(std::string(in.begin(), in.begin() + arg_size), &num)) return {};
1181  if (num < 1 || num >= 0x80000000L) return {};
1182  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::AFTER, num));
1183  in = in.subspan(arg_size + 1);
1184  script_size += 1 + (num > 16) + (num > 0x7f) + (num > 0x7fff) + (num > 0x7fffff);
1185  } else if (Const("older(", in)) {
1186  int arg_size = FindNextChar(in, ')');
1187  if (arg_size < 1) return {};
1188  int64_t num;
1189  if (!ParseInt64(std::string(in.begin(), in.begin() + arg_size), &num)) return {};
1190  if (num < 1 || num >= 0x80000000L) return {};
1191  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::OLDER, num));
1192  in = in.subspan(arg_size + 1);
1193  script_size += 1 + (num > 16) + (num > 0x7f) + (num > 0x7fff) + (num > 0x7fffff);
1194  } else if (Const("multi(", in)) {
1195  // Get threshold
1196  int next_comma = FindNextChar(in, ',');
1197  if (next_comma < 1) return {};
1198  if (!ParseInt64(std::string(in.begin(), in.begin() + next_comma), &k)) return {};
1199  in = in.subspan(next_comma + 1);
1200  // Get keys
1201  std::vector<Key> keys;
1202  while (next_comma != -1) {
1203  next_comma = FindNextChar(in, ',');
1204  int key_length = (next_comma == -1) ? FindNextChar(in, ')') : next_comma;
1205  if (key_length < 1) return {};
1206  auto key = ctx.FromString(in.begin(), in.begin() + key_length);
1207  if (!key) return {};
1208  keys.push_back(std::move(*key));
1209  in = in.subspan(key_length + 1);
1210  }
1211  if (keys.size() < 1 || keys.size() > 20) return {};
1212  if (k < 1 || k > (int64_t)keys.size()) return {};
1213  script_size += 2 + (keys.size() > 16) + (k > 16) + 34 * keys.size();
1214  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::MULTI, std::move(keys), k));
1215  } else if (Const("thresh(", in)) {
1216  int next_comma = FindNextChar(in, ',');
1217  if (next_comma < 1) return {};
1218  if (!ParseInt64(std::string(in.begin(), in.begin() + next_comma), &k)) return {};
1219  if (k < 1) return {};
1220  in = in.subspan(next_comma + 1);
1221  // n = 1 here because we read the first WRAPPED_EXPR before reaching THRESH
1222  to_parse.emplace_back(ParseContext::THRESH, 1, k);
1223  to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1224  script_size += 2 + (k > 16) + (k > 0x7f) + (k > 0x7fff) + (k > 0x7fffff);
1225  } else if (Const("andor(", in)) {
1226  to_parse.emplace_back(ParseContext::ANDOR, -1, -1);
1227  to_parse.emplace_back(ParseContext::CLOSE_BRACKET, -1, -1);
1228  to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1229  to_parse.emplace_back(ParseContext::COMMA, -1, -1);
1230  to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1231  to_parse.emplace_back(ParseContext::COMMA, -1, -1);
1232  to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1233  script_size += 5;
1234  } else {
1235  if (Const("and_n(", in)) {
1236  to_parse.emplace_back(ParseContext::AND_N, -1, -1);
1237  script_size += 5;
1238  } else if (Const("and_b(", in)) {
1239  to_parse.emplace_back(ParseContext::AND_B, -1, -1);
1240  script_size += 2;
1241  } else if (Const("and_v(", in)) {
1242  to_parse.emplace_back(ParseContext::AND_V, -1, -1);
1243  script_size += 1;
1244  } else if (Const("or_b(", in)) {
1245  to_parse.emplace_back(ParseContext::OR_B, -1, -1);
1246  script_size += 2;
1247  } else if (Const("or_c(", in)) {
1248  to_parse.emplace_back(ParseContext::OR_C, -1, -1);
1249  script_size += 3;
1250  } else if (Const("or_d(", in)) {
1251  to_parse.emplace_back(ParseContext::OR_D, -1, -1);
1252  script_size += 4;
1253  } else if (Const("or_i(", in)) {
1254  to_parse.emplace_back(ParseContext::OR_I, -1, -1);
1255  script_size += 4;
1256  } else {
1257  return {};
1258  }
1259  to_parse.emplace_back(ParseContext::CLOSE_BRACKET, -1, -1);
1260  to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1261  to_parse.emplace_back(ParseContext::COMMA, -1, -1);
1262  to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1263  }
1264  break;
1265  }
1266  case ParseContext::ALT: {
1267  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_A, Vector(std::move(constructed.back())));
1268  break;
1269  }
1270  case ParseContext::SWAP: {
1271  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_S, Vector(std::move(constructed.back())));
1272  break;
1273  }
1274  case ParseContext::CHECK: {
1275  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_C, Vector(std::move(constructed.back())));
1276  break;
1277  }
1278  case ParseContext::DUP_IF: {
1279  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_D, Vector(std::move(constructed.back())));
1280  break;
1281  }
1282  case ParseContext::NON_ZERO: {
1283  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_J, Vector(std::move(constructed.back())));
1284  break;
1285  }
1287  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_N, Vector(std::move(constructed.back())));
1288  break;
1289  }
1290  case ParseContext::VERIFY: {
1291  script_size += (constructed.back()->GetType() << "x"_mst);
1292  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_V, Vector(std::move(constructed.back())));
1293  break;
1294  }
1295  case ParseContext::WRAP_U: {
1296  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::OR_I, Vector(std::move(constructed.back()), MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_0)));
1297  break;
1298  }
1299  case ParseContext::WRAP_T: {
1300  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::AND_V, Vector(std::move(constructed.back()), MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_1)));
1301  break;
1302  }
1303  case ParseContext::AND_B: {
1304  BuildBack(Fragment::AND_B, constructed);
1305  break;
1306  }
1307  case ParseContext::AND_N: {
1308  auto mid = std::move(constructed.back());
1309  constructed.pop_back();
1310  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), MakeNodeRef<Key>(ctx, Fragment::JUST_0)));
1311  break;
1312  }
1313  case ParseContext::AND_V: {
1314  BuildBack(Fragment::AND_V, constructed);
1315  break;
1316  }
1317  case ParseContext::OR_B: {
1318  BuildBack(Fragment::OR_B, constructed);
1319  break;
1320  }
1321  case ParseContext::OR_C: {
1322  BuildBack(Fragment::OR_C, constructed);
1323  break;
1324  }
1325  case ParseContext::OR_D: {
1326  BuildBack(Fragment::OR_D, constructed);
1327  break;
1328  }
1329  case ParseContext::OR_I: {
1330  BuildBack(Fragment::OR_I, constructed);
1331  break;
1332  }
1333  case ParseContext::ANDOR: {
1334  auto right = std::move(constructed.back());
1335  constructed.pop_back();
1336  auto mid = std::move(constructed.back());
1337  constructed.pop_back();
1338  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), std::move(right)));
1339  break;
1340  }
1341  case ParseContext::THRESH: {
1342  if (in.size() < 1) return {};
1343  if (in[0] == ',') {
1344  in = in.subspan(1);
1345  to_parse.emplace_back(ParseContext::THRESH, n+1, k);
1346  to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1347  script_size += 2;
1348  } else if (in[0] == ')') {
1349  if (k > n) return {};
1350  in = in.subspan(1);
1351  // Children are constructed in reverse order, so iterate from end to beginning
1352  std::vector<NodeRef<Key>> subs;
1353  for (int i = 0; i < n; ++i) {
1354  subs.push_back(std::move(constructed.back()));
1355  constructed.pop_back();
1356  }
1357  std::reverse(subs.begin(), subs.end());
1358  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::THRESH, std::move(subs), k));
1359  } else {
1360  return {};
1361  }
1362  break;
1363  }
1364  case ParseContext::COMMA: {
1365  if (in.size() < 1 || in[0] != ',') return {};
1366  in = in.subspan(1);
1367  break;
1368  }
1370  if (in.size() < 1 || in[0] != ')') return {};
1371  in = in.subspan(1);
1372  break;
1373  }
1374  }
1375  }
1376 
1377  // Sanity checks on the produced miniscript
1378  assert(constructed.size() == 1);
1379  assert(constructed[0]->ScriptSize() == script_size);
1380  if (in.size() > 0) return {};
1381  const NodeRef<Key> tl_node = std::move(constructed.front());
1382  tl_node->DuplicateKeyCheck(ctx);
1383  return tl_node;
1384 }
1385 
1394 std::optional<std::vector<Opcode>> DecomposeScript(const CScript& script);
1395 
1397 std::optional<int64_t> ParseScriptNumber(const Opcode& in);
1398 
1399 enum class DecodeContext {
1405  BKV_EXPR,
1407  W_EXPR,
1408 
1412  SWAP,
1415  ALT,
1417  CHECK,
1419  DUP_IF,
1421  VERIFY,
1423  NON_ZERO,
1425  ZERO_NOTEQUAL,
1426 
1431  MAYBE_AND_V,
1433  AND_V,
1435  AND_B,
1437  ANDOR,
1439  OR_B,
1441  OR_C,
1443  OR_D,
1444 
1448  THRESH_W,
1451  THRESH_E,
1452 
1456  ENDIF,
1460  ENDIF_NOTIF,
1464  ENDIF_ELSE,
1465 };
1466 
1468 template<typename Key, typename Ctx, typename I>
1469 inline NodeRef<Key> DecodeScript(I& in, I last, const Ctx& ctx)
1470 {
1471  // The two integers are used to hold state for thresh()
1472  std::vector<std::tuple<DecodeContext, int64_t, int64_t>> to_parse;
1473  std::vector<NodeRef<Key>> constructed;
1474 
1475  // This is the top level, so we assume the type is B
1476  // (in particular, disallowing top level W expressions)
1477  to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
1478 
1479  while (!to_parse.empty()) {
1480  // Exit early if the Miniscript is not going to be valid.
1481  if (!constructed.empty() && !constructed.back()->IsValid()) return {};
1482 
1483  // Get the current context we are decoding within
1484  auto [cur_context, n, k] = to_parse.back();
1485  to_parse.pop_back();
1486 
1487  switch(cur_context) {
1489  if (in >= last) return {};
1490 
1491  // Constants
1492  if (in[0].first == OP_1) {
1493  ++in;
1494  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_1));
1495  break;
1496  }
1497  if (in[0].first == OP_0) {
1498  ++in;
1499  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::JUST_0));
1500  break;
1501  }
1502  // Public keys
1503  if (in[0].second.size() == 33) {
1504  auto key = ctx.FromPKBytes(in[0].second.begin(), in[0].second.end());
1505  if (!key) return {};
1506  ++in;
1507  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_K, Vector(std::move(*key))));
1508  break;
1509  }
1510  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) {
1511  auto key = ctx.FromPKHBytes(in[2].second.begin(), in[2].second.end());
1512  if (!key) return {};
1513  in += 5;
1514  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::PK_H, Vector(std::move(*key))));
1515  break;
1516  }
1517  // Time locks
1518  std::optional<int64_t> num;
1519  if (last - in >= 2 && in[0].first == OP_CHECKSEQUENCEVERIFY && (num = ParseScriptNumber(in[1]))) {
1520  in += 2;
1521  if (*num < 1 || *num > 0x7FFFFFFFL) return {};
1522  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::OLDER, *num));
1523  break;
1524  }
1525  if (last - in >= 2 && in[0].first == OP_CHECKLOCKTIMEVERIFY && (num = ParseScriptNumber(in[1]))) {
1526  in += 2;
1527  if (num < 1 || num > 0x7FFFFFFFL) return {};
1528  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::AFTER, *num));
1529  break;
1530  }
1531  // Hashes
1532  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) {
1533  if (in[2].first == OP_SHA256 && in[1].second.size() == 32) {
1534  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::SHA256, in[1].second));
1535  in += 7;
1536  break;
1537  } else if (in[2].first == OP_RIPEMD160 && in[1].second.size() == 20) {
1538  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::RIPEMD160, in[1].second));
1539  in += 7;
1540  break;
1541  } else if (in[2].first == OP_HASH256 && in[1].second.size() == 32) {
1542  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::HASH256, in[1].second));
1543  in += 7;
1544  break;
1545  } else if (in[2].first == OP_HASH160 && in[1].second.size() == 20) {
1546  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::HASH160, in[1].second));
1547  in += 7;
1548  break;
1549  }
1550  }
1551  // Multi
1552  if (last - in >= 3 && in[0].first == OP_CHECKMULTISIG) {
1553  std::vector<Key> keys;
1554  const auto n = ParseScriptNumber(in[1]);
1555  if (!n || last - in < 3 + *n) return {};
1556  if (*n < 1 || *n > 20) return {};
1557  for (int i = 0; i < *n; ++i) {
1558  if (in[2 + i].second.size() != 33) return {};
1559  auto key = ctx.FromPKBytes(in[2 + i].second.begin(), in[2 + i].second.end());
1560  if (!key) return {};
1561  keys.push_back(std::move(*key));
1562  }
1563  const auto k = ParseScriptNumber(in[2 + *n]);
1564  if (!k || *k < 1 || *k > *n) return {};
1565  in += 3 + *n;
1566  std::reverse(keys.begin(), keys.end());
1567  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::MULTI, std::move(keys), *k));
1568  break;
1569  }
1573  // c: wrapper
1574  if (in[0].first == OP_CHECKSIG) {
1575  ++in;
1576  to_parse.emplace_back(DecodeContext::CHECK, -1, -1);
1577  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
1578  break;
1579  }
1580  // v: wrapper
1581  if (in[0].first == OP_VERIFY) {
1582  ++in;
1583  to_parse.emplace_back(DecodeContext::VERIFY, -1, -1);
1584  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
1585  break;
1586  }
1587  // n: wrapper
1588  if (in[0].first == OP_0NOTEQUAL) {
1589  ++in;
1590  to_parse.emplace_back(DecodeContext::ZERO_NOTEQUAL, -1, -1);
1591  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
1592  break;
1593  }
1594  // Thresh
1595  if (last - in >= 3 && in[0].first == OP_EQUAL && (num = ParseScriptNumber(in[1]))) {
1596  if (*num < 1) return {};
1597  in += 2;
1598  to_parse.emplace_back(DecodeContext::THRESH_W, 0, *num);
1599  break;
1600  }
1601  // OP_ENDIF can be WRAP_J, WRAP_D, ANDOR, OR_C, OR_D, or OR_I
1602  if (in[0].first == OP_ENDIF) {
1603  ++in;
1604  to_parse.emplace_back(DecodeContext::ENDIF, -1, -1);
1605  to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
1606  break;
1607  }
1613  // and_b
1614  if (in[0].first == OP_BOOLAND) {
1615  ++in;
1616  to_parse.emplace_back(DecodeContext::AND_B, -1, -1);
1617  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
1618  to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
1619  break;
1620  }
1621  // or_b
1622  if (in[0].first == OP_BOOLOR) {
1623  ++in;
1624  to_parse.emplace_back(DecodeContext::OR_B, -1, -1);
1625  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
1626  to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
1627  break;
1628  }
1629  // Unrecognised expression
1630  return {};
1631  }
1632  case DecodeContext::BKV_EXPR: {
1633  to_parse.emplace_back(DecodeContext::MAYBE_AND_V, -1, -1);
1634  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
1635  break;
1636  }
1637  case DecodeContext::W_EXPR: {
1638  // a: wrapper
1639  if (in >= last) return {};
1640  if (in[0].first == OP_FROMALTSTACK) {
1641  ++in;
1642  to_parse.emplace_back(DecodeContext::ALT, -1, -1);
1643  } else {
1644  to_parse.emplace_back(DecodeContext::SWAP, -1, -1);
1645  }
1646  to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
1647  break;
1648  }
1650  // If we reach a potential AND_V top-level, check if the next part of the script could be another AND_V child
1651  // These op-codes cannot end any well-formed miniscript so cannot be used in an and_v node.
1652  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) {
1653  to_parse.emplace_back(DecodeContext::AND_V, -1, -1);
1654  // BKV_EXPR can contain more AND_V nodes
1655  to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
1656  }
1657  break;
1658  }
1659  case DecodeContext::SWAP: {
1660  if (in >= last || in[0].first != OP_SWAP || constructed.empty()) return {};
1661  ++in;
1662  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_S, Vector(std::move(constructed.back())));
1663  break;
1664  }
1665  case DecodeContext::ALT: {
1666  if (in >= last || in[0].first != OP_TOALTSTACK || constructed.empty()) return {};
1667  ++in;
1668  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_A, Vector(std::move(constructed.back())));
1669  break;
1670  }
1671  case DecodeContext::CHECK: {
1672  if (constructed.empty()) return {};
1673  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_C, Vector(std::move(constructed.back())));
1674  break;
1675  }
1676  case DecodeContext::DUP_IF: {
1677  if (constructed.empty()) return {};
1678  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_D, Vector(std::move(constructed.back())));
1679  break;
1680  }
1681  case DecodeContext::VERIFY: {
1682  if (constructed.empty()) return {};
1683  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_V, Vector(std::move(constructed.back())));
1684  break;
1685  }
1686  case DecodeContext::NON_ZERO: {
1687  if (constructed.empty()) return {};
1688  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_J, Vector(std::move(constructed.back())));
1689  break;
1690  }
1692  if (constructed.empty()) return {};
1693  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::WRAP_N, Vector(std::move(constructed.back())));
1694  break;
1695  }
1696  case DecodeContext::AND_V: {
1697  if (constructed.size() < 2) return {};
1698  BuildBack(Fragment::AND_V, constructed, /*reverse=*/true);
1699  break;
1700  }
1701  case DecodeContext::AND_B: {
1702  if (constructed.size() < 2) return {};
1703  BuildBack(Fragment::AND_B, constructed, /*reverse=*/true);
1704  break;
1705  }
1706  case DecodeContext::OR_B: {
1707  if (constructed.size() < 2) return {};
1708  BuildBack(Fragment::OR_B, constructed, /*reverse=*/true);
1709  break;
1710  }
1711  case DecodeContext::OR_C: {
1712  if (constructed.size() < 2) return {};
1713  BuildBack(Fragment::OR_C, constructed, /*reverse=*/true);
1714  break;
1715  }
1716  case DecodeContext::OR_D: {
1717  if (constructed.size() < 2) return {};
1718  BuildBack(Fragment::OR_D, constructed, /*reverse=*/true);
1719  break;
1720  }
1721  case DecodeContext::ANDOR: {
1722  if (constructed.size() < 3) return {};
1723  NodeRef<Key> left = std::move(constructed.back());
1724  constructed.pop_back();
1725  NodeRef<Key> right = std::move(constructed.back());
1726  constructed.pop_back();
1727  NodeRef<Key> mid = std::move(constructed.back());
1728  constructed.back() = MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::ANDOR, Vector(std::move(left), std::move(mid), std::move(right)));
1729  break;
1730  }
1731  case DecodeContext::THRESH_W: {
1732  if (in >= last) return {};
1733  if (in[0].first == OP_ADD) {
1734  ++in;
1735  to_parse.emplace_back(DecodeContext::THRESH_W, n+1, k);
1736  to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
1737  } else {
1738  to_parse.emplace_back(DecodeContext::THRESH_E, n+1, k);
1739  // All children of thresh have type modifier d, so cannot be and_v
1740  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
1741  }
1742  break;
1743  }
1744  case DecodeContext::THRESH_E: {
1745  if (k < 1 || k > n || constructed.size() < static_cast<size_t>(n)) return {};
1746  std::vector<NodeRef<Key>> subs;
1747  for (int i = 0; i < n; ++i) {
1748  NodeRef<Key> sub = std::move(constructed.back());
1749  constructed.pop_back();
1750  subs.push_back(std::move(sub));
1751  }
1752  constructed.push_back(MakeNodeRef<Key>(internal::NoDupCheck{}, Fragment::THRESH, std::move(subs), k));
1753  break;
1754  }
1755  case DecodeContext::ENDIF: {
1756  if (in >= last) return {};
1757 
1758  // could be andor or or_i
1759  if (in[0].first == OP_ELSE) {
1760  ++in;
1761  to_parse.emplace_back(DecodeContext::ENDIF_ELSE, -1, -1);
1762  to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
1763  }
1764  // could be j: or d: wrapper
1765  else if (in[0].first == OP_IF) {
1766  if (last - in >= 2 && in[1].first == OP_DUP) {
1767  in += 2;
1768  to_parse.emplace_back(DecodeContext::DUP_IF, -1, -1);
1769  } else if (last - in >= 3 && in[1].first == OP_0NOTEQUAL && in[2].first == OP_SIZE) {
1770  in += 3;
1771  to_parse.emplace_back(DecodeContext::NON_ZERO, -1, -1);
1772  }
1773  else {
1774  return {};
1775  }
1776  // could be or_c or or_d
1777  } else if (in[0].first == OP_NOTIF) {
1778  ++in;
1779  to_parse.emplace_back(DecodeContext::ENDIF_NOTIF, -1, -1);
1780  }
1781  else {
1782  return {};
1783  }
1784  break;
1785  }
1787  if (in >= last) return {};
1788  if (in[0].first == OP_IFDUP) {
1789  ++in;
1790  to_parse.emplace_back(DecodeContext::OR_D, -1, -1);
1791  } else {
1792  to_parse.emplace_back(DecodeContext::OR_C, -1, -1);
1793  }
1794  // or_c and or_d both require X to have type modifier d so, can't contain and_v
1795  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
1796  break;
1797  }
1799  if (in >= last) return {};
1800  if (in[0].first == OP_IF) {
1801  ++in;
1802  BuildBack(Fragment::OR_I, constructed, /*reverse=*/true);
1803  } else if (in[0].first == OP_NOTIF) {
1804  ++in;
1805  to_parse.emplace_back(DecodeContext::ANDOR, -1, -1);
1806  // andor requires X to have type modifier d, so it can't be and_v
1807  to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
1808  } else {
1809  return {};
1810  }
1811  break;
1812  }
1813  }
1814  }
1815  if (constructed.size() != 1) return {};
1816  const NodeRef<Key> tl_node = std::move(constructed.front());
1817  tl_node->DuplicateKeyCheck(ctx);
1818  // Note that due to how ComputeType works (only assign the type to the node if the
1819  // subs' types are valid) this would fail if any node of tree is badly typed.
1820  if (!tl_node->IsValidTopLevel()) return {};
1821  return tl_node;
1822 }
1823 
1824 } // namespace internal
1825 
1826 template<typename Ctx>
1827 inline NodeRef<typename Ctx::Key> FromString(const std::string& str, const Ctx& ctx) {
1828  return internal::Parse<typename Ctx::Key>(str, ctx);
1829 }
1830 
1831 template<typename Ctx>
1832 inline NodeRef<typename Ctx::Key> FromScript(const CScript& script, const Ctx& ctx) {
1833  using namespace internal;
1834  // A too large Script is necessarily invalid, don't bother parsing it.
1835  if (script.size() > MAX_STANDARD_P2WSH_SCRIPT_SIZE) return {};
1836  auto decomposed = DecomposeScript(script);
1837  if (!decomposed) return {};
1838  auto it = decomposed->begin();
1839  auto ret = DecodeScript<typename Ctx::Key>(it, decomposed->end(), ctx);
1840  if (!ret) return {};
1841  if (it != decomposed->end()) return {};
1842  return ret;
1843 }
1844 
1845 } // namespace miniscript
1846 
1847 #endif // BITCOIN_SCRIPT_MINISCRIPT_H
int ret
int flags
Definition: bitcoin-tx.cpp:525
Serialized script, used inside transaction inputs and outputs.
Definition: script.h:411
A Span is an object that can refer to a contiguous sequence of objects.
Definition: span.h:97
constexpr std::size_t size() const noexcept
Definition: span.h:186
constexpr C * begin() const noexcept
Definition: span.h:174
CONSTEXPR_IF_NOT_DEBUG Span< C > last(std::size_t count) const noexcept
Definition: span.h:209
CONSTEXPR_IF_NOT_DEBUG Span< C > subspan(std::size_t offset) const noexcept
Definition: span.h:194
This type encapsulates the miniscript type system properties.
Definition: miniscript.h:121
constexpr bool operator<<(Type x) const
Check whether the left hand's properties are superset of the right's (= left is a subtype of right).
Definition: miniscript.h:139
uint32_t m_flags
Internal bitmap of properties (see ""_mst operator for details).
Definition: miniscript.h:123
constexpr Type(uint32_t flags)
Internal constructor used by the ""_mst operator.
Definition: miniscript.h:126
constexpr Type If(bool x) const
The empty type if x is false, itself otherwise.
Definition: miniscript.h:148
constexpr Type operator&(Type x) const
Compute the type with the intersection of properties.
Definition: miniscript.h:136
constexpr bool operator<(Type x) const
Comparison operator to enable use in sets/maps (total ordering incompatible with <<).
Definition: miniscript.h:142
constexpr Type operator|(Type x) const
Compute the type with the union of properties.
Definition: miniscript.h:133
constexpr bool operator==(Type x) const
Equality operator.
Definition: miniscript.h:145
size_type size() const
Definition: prevector.h:284
int FindNextChar(Span< const char > sp, const char m)
Definition: miniscript.cpp:331
std::optional< int64_t > ParseScriptNumber(const Opcode &in)
Determine whether the passed pair (created by DecomposeScript) is pushing a number.
Definition: miniscript.cpp:318
Type SanitizeType(Type e)
A helper sanitizer/checker for the output of CalcType.
Definition: miniscript.cpp:16
Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector< Type > &sub_types, uint32_t k, size_t data_size, size_t n_subs, size_t n_keys)
Helper function for Node::CalcType.
Definition: miniscript.cpp:36
std::optional< std::vector< Opcode > > DecomposeScript(const CScript &script)
Decode a script into opcode/push pairs.
Definition: miniscript.cpp:282
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:998
size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs, size_t n_keys)
Helper function for Node::CalcScriptLen.
Definition: miniscript.cpp:250
@ OR_I
OR_I will construct an or_i node from the last two constructed nodes.
@ VERIFY
VERIFY wraps the top constructed node with v:
@ OR_B
OR_B will construct an or_b node from the last two constructed nodes.
@ CLOSE_BRACKET
CLOSE_BRACKET expects the next element to be ')' and fails if not.
@ AND_N
AND_N will construct an andor(X,Y,0) node from the last two constructed nodes.
@ SWAP
SWAP wraps the top constructed node with s:
@ ANDOR
ANDOR will construct an andor node from the last three constructed nodes.
@ THRESH
THRESH will read a wrapped expression, and then look for a COMMA.
@ COMMA
COMMA expects the next element to be ',' and fails if not.
@ AND_V
AND_V will construct an and_v node from the last two constructed nodes.
@ CHECK
CHECK wraps the top constructed node with c:
@ DUP_IF
DUP_IF wraps the top constructed node with d:
@ OR_C
OR_C will construct an or_c node from the last two constructed nodes.
@ EXPR
A miniscript expression which does not begin with wrappers.
@ ZERO_NOTEQUAL
ZERO_NOTEQUAL wraps the top constructed node with n:
@ NON_ZERO
NON_ZERO wraps the top constructed node with j:
@ WRAP_T
WRAP_T will construct an and_v(X,1) node from the top constructed node.
@ OR_D
OR_D will construct an or_d node from the last two constructed nodes.
@ AND_B
AND_B will construct an and_b node from the last two constructed nodes.
@ ALT
ALT wraps the top constructed node with a:
@ WRAP_U
WRAP_U will construct an or_i(X,0) node from the top constructed node.
@ WRAPPED_EXPR
An expression which may be begin with wrappers followed by a colon.
std::optional< std::pair< Key, int > > ParseKeyEnd(Span< const char > in, const Ctx &ctx)
Parse a key string ending at the end of the fragment's text representation.
Definition: miniscript.h:987
NodeRef< Key > Parse(Span< const char > in, const Ctx &ctx)
Parse a miniscript from its textual descriptor form.
Definition: miniscript.h:1029
@ VERIFY
VERIFY wraps the top constructed node with v:
@ SINGLE_BKV_EXPR
A single expression of type B, K, or V.
@ OR_B
OR_B will construct an or_b node from the last two constructed nodes.
@ ENDIF_NOTIF
If, inside an ENDIF context, we find an OP_NOTIF before finding an OP_ELSE, we could either be in an ...
@ BKV_EXPR
Potentially multiple SINGLE_BKV_EXPRs as children of (potentially multiple) and_v expressions.
@ ENDIF_ELSE
If, inside an ENDIF context, we find an OP_ELSE, then we could be in either an or_i or an andor node.
@ MAYBE_AND_V
MAYBE_AND_V will check if the next part of the script could be a valid miniscript sub-expression,...
@ SWAP
SWAP expects the next element to be OP_SWAP (inside a W-type expression that didn't end with FROMALTS...
@ ANDOR
ANDOR will construct an andor node from the last three constructed nodes.
@ W_EXPR
An expression of type W (a: or s: wrappers).
@ AND_V
AND_V will construct an and_v node from the last two constructed nodes.
@ THRESH_E
THRESH_E constructs a thresh node from the appropriate number of constructed children.
@ CHECK
CHECK wraps the top constructed node with c:
@ DUP_IF
DUP_IF wraps the top constructed node with d:
@ OR_C
OR_C will construct an or_c node from the last two constructed nodes.
@ ENDIF
ENDIF signals that we are inside some sort of OP_IF structure, which could be or_d,...
@ ZERO_NOTEQUAL
ZERO_NOTEQUAL wraps the top constructed node with n:
@ NON_ZERO
NON_ZERO wraps the top constructed node with j:
@ OR_D
OR_D will construct an or_d node from the last two constructed nodes.
@ AND_B
AND_B will construct an and_b node from the last two constructed nodes.
@ ALT
ALT expects the next element to be TOALTSTACK (we must have already read a FROMALTSTACK earlier),...
@ THRESH_W
In a thresh expression, all sub-expressions other than the first are W-type, and end in OP_ADD.
void BuildBack(Fragment nt, std::vector< NodeRef< Key >> &constructed, const bool reverse=false)
BuildBack pops the last two elements off constructed and wraps them in the specified Fragment.
Definition: miniscript.h:1012
NodeRef< Key > DecodeScript(I &in, I last, const Ctx &ctx)
Parse a miniscript from a bitcoin script.
Definition: miniscript.h:1469
std::shared_ptr< const Node< Key > > NodeRef
Definition: miniscript.h:186
NodeRef< Key > MakeNodeRef(Args &&... args)
Construct a miniscript node as a shared_ptr.
Definition: miniscript.h:190
NodeRef< typename Ctx::Key > FromScript(const CScript &script, const Ctx &ctx)
Definition: miniscript.h:1832
NodeRef< typename Ctx::Key > FromString(const std::string &str, const Ctx &ctx)
Definition: miniscript.h:1827
std::pair< opcodetype, std::vector< unsigned char > > Opcode
Definition: miniscript.h:183
Fragment
The different node types in miniscript.
Definition: miniscript.h:193
@ OR_I
OP_IF [X] OP_ELSE [Y] OP_ENDIF.
@ RIPEMD160
OP_SIZE 32 OP_EQUALVERIFY OP_RIPEMD160 [hash] OP_EQUAL.
@ HASH160
OP_SIZE 32 OP_EQUALVERIFY OP_HASH160 [hash] OP_EQUAL.
@ OR_B
[X] [Y] OP_BOOLOR
@ WRAP_A
OP_TOALTSTACK [X] OP_FROMALTSTACK.
@ WRAP_V
[X] OP_VERIFY (or -VERIFY version of last opcode in X)
@ ANDOR
[X] OP_NOTIF [Z] OP_ELSE [Y] OP_ENDIF
@ THRESH
[X1] ([Xn] OP_ADD)* [k] OP_EQUAL
@ WRAP_N
[X] OP_0NOTEQUAL
@ WRAP_S
OP_SWAP [X].
@ OR_C
[X] OP_NOTIF [Y] OP_ENDIF
@ HASH256
OP_SIZE 32 OP_EQUALVERIFY OP_HASH256 [hash] OP_EQUAL.
@ OLDER
[n] OP_CHECKSEQUENCEVERIFY
@ SHA256
OP_SIZE 32 OP_EQUALVERIFY OP_SHA256 [hash] OP_EQUAL.
@ WRAP_J
OP_SIZE OP_0NOTEQUAL OP_IF [X] OP_ENDIF.
@ AFTER
[n] OP_CHECKLOCKTIMEVERIFY
@ OR_D
[X] OP_IFDUP OP_NOTIF [Y] OP_ENDIF
@ WRAP_D
OP_DUP OP_IF [X] OP_ENDIF.
@ AND_B
[X] [Y] OP_BOOLAND
@ PK_H
OP_DUP OP_HASH160 [keyhash] OP_EQUALVERIFY.
@ WRAP_C
[X] OP_CHECKSIG
@ MULTI
[k] [key_n]* [n] OP_CHECKMULTISIG
Definition: init.h:25
bool Const(const std::string &str, Span< const char > &sp)
Parse a constant.
Definition: spanparsing.cpp:15
ArgsManager args
static constexpr unsigned int MAX_STANDARD_P2WSH_STACK_ITEMS
The maximum number of witness stack items in a standard P2WSH script.
Definition: policy.h:41
static constexpr unsigned int MAX_STANDARD_P2WSH_SCRIPT_SIZE
The maximum size in bytes of a standard witnessScript.
Definition: policy.h:47
@ OP_SHA256
Definition: script.h:182
@ OP_BOOLAND
Definition: script.h:165
@ OP_CHECKMULTISIG
Definition: script.h:188
@ OP_IF
Definition: script.h:100
@ OP_SWAP
Definition: script.h:127
@ OP_CHECKSIG
Definition: script.h:186
@ OP_CHECKLOCKTIMEVERIFY
Definition: script.h:193
@ OP_EQUAL
Definition: script.h:142
@ OP_NOTIF
Definition: script.h:101
@ OP_SIZE
Definition: script.h:135
@ OP_ENDIF
Definition: script.h:105
@ OP_DUP
Definition: script.h:121
@ OP_TOALTSTACK
Definition: script.h:110
@ OP_RIPEMD160
Definition: script.h:180
@ OP_HASH256
Definition: script.h:184
@ OP_FROMALTSTACK
Definition: script.h:111
@ OP_HASH160
Definition: script.h:183
@ OP_1
Definition: script.h:79
@ OP_VERIFY
Definition: script.h:106
@ OP_ADD
Definition: script.h:157
@ OP_CHECKMULTISIGVERIFY
Definition: script.h:189
@ OP_BOOLOR
Definition: script.h:166
@ OP_ELSE
Definition: script.h:104
@ OP_CHECKSIGVERIFY
Definition: script.h:187
@ OP_0NOTEQUAL
Definition: script.h:155
@ OP_0
Definition: script.h:72
@ OP_IFDUP
Definition: script.h:118
@ OP_EQUALVERIFY
Definition: script.h:143
@ OP_CHECKSEQUENCEVERIFY
Definition: script.h:195
static const int MAX_OPS_PER_SCRIPT
Definition: script.h:27
CScript BuildScript(Ts &&... inputs)
Build a script by concatenating other scripts, or any argument accepted by CScript::operator<<.
Definition: script.h:585
static bool verify(const CScriptNum10 &bignum, const CScriptNum &scriptnum)
A node in a miniscript expression.
Definition: miniscript.h:285
const Type typ
Cached expression type (computed by CalcType and fed through SanitizeType).
Definition: miniscript.h:303
Result TreeEval(UpFn upfn) const
Like TreeEval, but without downfn or State type.
Definition: miniscript.h:442
Node(const Ctx &ctx, Fragment nt, std::vector< NodeRef< Key >> sub, std::vector< unsigned char > arg, uint32_t val=0)
Definition: miniscript.h:919
CScript ToScript(const Ctx &ctx) const
Definition: miniscript.h:493
bool CheckStackSize() const
Check the maximum stack size for this script against the policy limit.
Definition: miniscript.h:866
Node(internal::NoDupCheck, Fragment nt, std::vector< NodeRef< Key >> sub, std::vector< unsigned char > arg, uint32_t val=0)
Definition: miniscript.h:911
internal::StackSize CalcStackSize() const
Definition: miniscript.h:738
bool IsSaneSubexpression() const
Whether the apparent policy of this node matches its script semantics. Doesn't guarantee it is a safe...
Definition: miniscript.h:902
Type GetType() const
Return the expression type.
Definition: miniscript.h:869
uint32_t GetOps() const
Return the maximum number of ops needed to satisfy this script non-malleably.
Definition: miniscript.h:856
friend int Compare(const Node< Key > &node1, const Node< Key > &node2)
Compare two miniscript subtrees, using a non-recursive algorithm.
Definition: miniscript.h:455
const size_t scriptlen
Cached script length (computed by CalcScriptLen).
Definition: miniscript.h:305
std::optional< bool > has_duplicate_keys
Whether a public key appears more than once in this node.
Definition: miniscript.h:311
const uint32_t k
The k parameter (time for OLDER/AFTER, threshold for THRESH(_M))
Definition: miniscript.h:289
const std::vector< NodeRef< Key > > subs
Subexpressions (for WRAP_*‍/AND_*‍/OR_*‍/ANDOR/THRESH)
Definition: miniscript.h:295
bool NeedsSignature() const
Check whether this script always needs a signature.
Definition: miniscript.h:890
std::optional< Result > TreeEvalMaybe(UpFn upfn) const
Like TreeEvalMaybe, but without downfn or State type.
Definition: miniscript.h:413
bool CheckOpsLimit() const
Check the ops limit of this script against the consensus limit.
Definition: miniscript.h:859
const Fragment fragment
What node type this node is.
Definition: miniscript.h:287
Node(const Ctx &ctx, Fragment nt, uint32_t val=0)
Definition: miniscript.h:924
const Node * FindInsaneSub() const
Find an insane subnode which has no insane children. Nullptr if there is none.
Definition: miniscript.h:872
uint32_t GetStackSize() const
Return the maximum number of stack elements needed to satisfy this script non-malleably,...
Definition: miniscript.h:863
Result TreeEval(State root_state, DownFn &&downfn, UpFn upfn) const
Like TreeEvalMaybe, but always produces a result.
Definition: miniscript.h:426
internal::Ops CalcOps() const
Definition: miniscript.h:665
Node(const Ctx &ctx, Fragment nt, std::vector< NodeRef< Key >> sub, std::vector< Key > key, uint32_t val=0)
Definition: miniscript.h:921
Node(internal::NoDupCheck, Fragment nt, uint32_t val=0)
Definition: miniscript.h:916
Node(internal::NoDupCheck, Fragment nt, std::vector< Key > key, uint32_t val=0)
Definition: miniscript.h:914
Node(internal::NoDupCheck, Fragment nt, std::vector< NodeRef< Key >> sub, uint32_t val=0)
Definition: miniscript.h:915
size_t CalcScriptLen() const
Compute the length of the script for this miniscript (including children).
Definition: miniscript.h:315
bool IsSane() const
Check whether this node is safe as a script on its own.
Definition: miniscript.h:905
bool IsValidTopLevel() const
Check whether this node is valid as a script on its own.
Definition: miniscript.h:884
Node(internal::NoDupCheck, Fragment nt, std::vector< NodeRef< Key >> sub, std::vector< Key > key, uint32_t val=0)
Definition: miniscript.h:913
bool IsNonMalleable() const
Check whether this script can always be satisfied in a non-malleable way.
Definition: miniscript.h:887
Type CalcType() const
Compute the type for this miniscript.
Definition: miniscript.h:475
bool CheckDuplicateKey() const
Check whether there is no duplicate key across this fragment and all its sub-fragments.
Definition: miniscript.h:896
size_t ScriptSize() const
Return the size of the script for this expression (faster than ToScript().size()).
Definition: miniscript.h:853
Node(const Ctx &ctx, Fragment nt, std::vector< NodeRef< Key >> sub, uint32_t val=0)
Definition: miniscript.h:923
bool ValidSatisfactions() const
Whether successful non-malleable satisfactions are guaranteed to be valid.
Definition: miniscript.h:899
const std::vector< Key > keys
The keys used by this expression (only for PK_K/PK_H/MULTI)
Definition: miniscript.h:291
std::optional< Result > TreeEvalMaybe(State root_state, DownFn downfn, UpFn upfn) const
Definition: miniscript.h:348
std::optional< std::string > ToString(const CTx &ctx) const
Definition: miniscript.h:562
void DuplicateKeyCheck(const Ctx &ctx) const
Update duplicate key information in this Node.
Definition: miniscript.h:794
bool operator==(const Node< Key > &arg) const
Equality testing.
Definition: miniscript.h:908
bool CheckTimeLocksMix() const
Check whether there is no satisfaction path that contains both timelocks and heightlocks.
Definition: miniscript.h:893
Node(const Ctx &ctx, Fragment nt, std::vector< Key > key, uint32_t val=0)
Definition: miniscript.h:922
Node(const Ctx &ctx, Fragment nt, std::vector< unsigned char > arg, uint32_t val=0)
Definition: miniscript.h:920
const internal::Ops ops
Cached ops counts.
Definition: miniscript.h:299
bool IsValid() const
Check whether this node is valid at all.
Definition: miniscript.h:881
const std::vector< unsigned char > data
The data bytes in this expression (only for HASH160/HASH256/SHA256/RIPEMD10).
Definition: miniscript.h:293
const internal::StackSize ss
Cached stack size bounds.
Definition: miniscript.h:301
Node(internal::NoDupCheck, Fragment nt, std::vector< unsigned char > arg, uint32_t val=0)
Definition: miniscript.h:912
Class whose objects represent the maximum of a list of integers.
Definition: miniscript.h:240
friend MaxInt< I > operator|(const MaxInt< I > &a, const MaxInt< I > &b)
Definition: miniscript.h:252
friend MaxInt< I > operator+(const MaxInt< I > &a, const MaxInt< I > &b)
Definition: miniscript.h:247
Ops(uint32_t in_count, MaxInt< uint32_t > in_sat, MaxInt< uint32_t > in_dsat)
Definition: miniscript.h:267
MaxInt< uint32_t > sat
Number of keys in possibly executed OP_CHECKMULTISIG(VERIFY)s to satisfy.
Definition: miniscript.h:263
MaxInt< uint32_t > dsat
Number of keys in possibly executed OP_CHECKMULTISIG(VERIFY)s to dissatisfy.
Definition: miniscript.h:265
uint32_t count
Non-push opcodes.
Definition: miniscript.h:261
MaxInt< uint32_t > sat
Maximum stack size to satisfy;.
Definition: miniscript.h:272
MaxInt< uint32_t > dsat
Maximum stack size to dissatisfy;.
Definition: miniscript.h:274
StackSize(MaxInt< uint32_t > in_sat, MaxInt< uint32_t > in_dsat)
Definition: miniscript.h:276
static secp256k1_context * ctx
Definition: tests.c:34
static int count
Definition: tests.c:33
std::string HexStr(const Span< const uint8_t > s)
Convert a span of bytes to a lower-case hexadecimal string.
std::vector< Byte > ParseHex(std::string_view str)
Parse the hex string into bytes (uint8_t or std::byte).
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)
assert(!tx.IsCoinBase())
std::vector< typename std::common_type< Args... >::type > Vector(Args &&... args)
Construct a vector with the specified elements.
Definition: vector.h:21