5 #ifndef BITCOIN_SCRIPT_MINISCRIPT_H
6 #define BITCOIN_SCRIPT_MINISCRIPT_H
131 friend constexpr
Type operator"" _mst(
const char* c,
size_t l);
153 inline constexpr
Type operator"" _mst(
const char* c,
size_t l) {
156 for (
const char *p = c; p < c + l; p++) {
168 *p ==
'f' ? 1 << 10 :
169 *p ==
's' ? 1 << 11 :
170 *p ==
'm' ? 1 << 12 :
171 *p ==
'x' ? 1 << 13 :
172 *p ==
'g' ? 1 << 14 :
173 *p ==
'h' ? 1 << 15 :
174 *p ==
'i' ? 1 << 16 :
175 *p ==
'j' ? 1 << 17 :
176 *p ==
'k' ? 1 << 18 :
177 (
throw std::logic_error(
"Unknown character in _mst literal"), 0)
184 using Opcode = std::pair<opcodetype, std::vector<unsigned char>>;
186 template<
typename Key>
struct Node;
187 template<
typename Key>
using NodeRef = std::shared_ptr<const Node<Key>>;
190 template<
typename Key,
typename... Args>
306 std::vector<std::vector<unsigned char>>
stack;
340 template<
typename A,
typename B>
359 if (!a.
valid)
return b;
360 if (!b.
valid)
return a;
429 constexpr
SatInfo(int32_t in_netdiff, int32_t in_exec) noexcept :
436 if (!a.valid)
return b;
437 if (!b.valid)
return a;
439 return {std::max(a.netdiff, b.netdiff), std::max(a.exec, b.exec)};
446 if (!a.valid || !b.valid)
return {};
450 return {a.
netdiff + b.netdiff, std::max(b.exec, b.netdiff + a.exec)};
462 static constexpr
SatInfo If() noexcept {
return {1, 1}; }
468 static constexpr
SatInfo OP_IFDUP(
bool nonzero) noexcept {
return {nonzero ? -1 : 0, 0}; }
498 template<
typename Key>
503 const uint32_t
k = 0;
507 const std::vector<unsigned char>
data;
509 mutable std::vector<NodeRef<Key>>
subs;
516 while (!
subs.empty()) {
519 while (!
node->subs.empty()) {
520 subs.push_back(std::move(
node->subs.back()));
521 node->subs.pop_back();
548 for (
const auto& sub :
subs) {
549 subsize += sub->ScriptSize();
551 Type sub0type =
subs.size() > 0 ?
subs[0]->GetType() :
""_mst;
578 template<
typename Result,
typename State,
typename DownFn,
typename UpFn>
579 std::optional<Result>
TreeEvalMaybe(State root_state, DownFn downfn, UpFn upfn)
const
588 StackElem(
const Node& node_,
size_t exp_, State&& state_) :
589 node(node_), expanded(exp_), state(std::move(state_)) {}
592 std::vector<StackElem> stack;
595 std::vector<Result> results;
596 stack.emplace_back(*
this, 0, std::move(root_state));
614 while (stack.size()) {
615 const Node&
node = stack.back().node;
616 if (stack.back().expanded <
node.subs.size()) {
620 size_t child_index = stack.back().expanded++;
621 State child_state = downfn(stack.back().state,
node, child_index);
622 stack.emplace_back(*
node.subs[child_index], 0, std::move(child_state));
627 std::optional<Result> result{upfn(std::move(stack.back().state),
node,
630 if (!result)
return {};
632 results.erase(results.end() -
node.subs.size(), results.end());
633 results.push_back(std::move(*result));
637 assert(results.size() == 1);
638 return std::move(results[0]);
643 template<
typename Result,
typename UpFn>
646 struct DummyState {};
647 return TreeEvalMaybe<Result>(DummyState{},
648 [](DummyState,
const Node&, size_t) {
return DummyState{}; },
656 template<
typename Result,
typename State,
typename DownFn,
typename UpFn>
661 return std::move(*TreeEvalMaybe<Result>(std::move(root_state),
662 std::forward<DownFn>(downfn),
665 return std::optional<Result>(std::move(res));
672 template<
typename Result,
typename UpFn>
675 struct DummyState {};
676 return std::move(*TreeEvalMaybe<Result>(DummyState{},
677 [](DummyState,
const Node&, size_t) {
return DummyState{}; },
680 return std::optional<Result>(std::move(res));
688 std::vector<std::pair<const Node<Key>&,
const Node<Key>&>> queue;
689 queue.emplace_back(node1, node2);
690 while (!queue.empty()) {
691 const auto& [a, b] = queue.back();
693 if (std::tie(a.fragment, a.k, a.keys, a.data) < std::tie(b.fragment, b.k, b.keys, b.data))
return -1;
694 if (std::tie(b.fragment, b.k, b.keys, b.data) < std::tie(a.fragment, a.k, a.keys, a.data))
return 1;
695 if (a.subs.size() < b.subs.size())
return -1;
696 if (b.subs.size() < a.subs.size())
return 1;
697 size_t n = a.
subs.size();
698 for (
size_t i = 0; i < n; ++i) {
699 queue.emplace_back(*a.subs[n - 1 - i], *b.subs[n - 1 - i]);
707 using namespace internal;
710 std::vector<Type> sub_types;
712 for (
const auto& sub :
subs) sub_types.push_back(sub->GetType());
723 template<
typename Ctx>
742 switch (
node.fragment) {
756 if (
node.subs[0]->GetType() <<
"x"_mst) {
759 return std::move(
subs[0]);
776 for (
const auto& key :
node.keys) {
777 script =
BuildScript(std::move(script), ctx.ToPKBytes(key));
784 for (
auto it =
node.keys.begin() + 1; it !=
node.keys.end(); ++it) {
791 for (
size_t i = 1; i <
subs.size(); ++i) {
799 return TreeEval<CScript>(
false, downfn, upfn);
802 template<
typename CTx>
803 std::optional<std::string>
ToString(
const CTx& ctx)
const {
807 auto downfn = [](bool,
const Node&
node, size_t) {
820 std::string
ret = wrapped ?
":" :
"";
822 switch (
node.fragment) {
828 auto key_str = ctx.ToString(
node.subs[0]->keys[0]);
829 if (!key_str)
return {};
830 return std::move(
ret) +
"pk(" + std::move(*key_str) +
")";
834 auto key_str = ctx.ToString(
node.subs[0]->keys[0]);
835 if (!key_str)
return {};
836 return std::move(
ret) +
"pkh(" + std::move(*key_str) +
")";
838 return "c" + std::move(
subs[0]);
853 switch (
node.fragment) {
855 auto key_str = ctx.ToString(
node.keys[0]);
856 if (!key_str)
return {};
857 return std::move(
ret) +
"pk_k(" + std::move(*key_str) +
")";
860 auto key_str = ctx.ToString(
node.keys[0]);
861 if (!key_str)
return {};
862 return std::move(
ret) +
"pk_h(" + std::move(*key_str) +
")";
881 return std::move(
ret) +
"andor(" + std::move(
subs[0]) +
"," + std::move(
subs[1]) +
"," + std::move(
subs[2]) +
")";
885 for (
const auto& key :
node.keys) {
886 auto key_str = ctx.ToString(key);
887 if (!key_str)
return {};
888 str +=
"," + std::move(*key_str);
890 return std::move(str) +
")";
895 for (
const auto& key :
node.keys) {
896 auto key_str = ctx.ToString(key);
897 if (!key_str)
return {};
898 str +=
"," + std::move(*key_str);
900 return std::move(str) +
")";
904 for (
auto& sub :
subs) {
905 str +=
"," + std::move(sub);
907 return std::move(str) +
")";
914 return TreeEvalMaybe<std::string>(
false, downfn, upfn);
932 const auto count{1 +
subs[0]->ops.count +
subs[1]->ops.count};
933 const auto sat{
subs[0]->ops.sat +
subs[1]->ops.sat};
934 const auto dsat{
subs[0]->ops.dsat +
subs[1]->ops.dsat};
935 return {
count, sat, dsat};
938 const auto count{1 +
subs[0]->ops.count +
subs[1]->ops.count};
940 const auto dsat{
subs[0]->ops.dsat +
subs[1]->ops.dsat};
941 return {
count, sat, dsat};
944 const auto count{3 +
subs[0]->ops.count +
subs[1]->ops.count};
945 const auto sat{
subs[0]->ops.sat | (
subs[1]->ops.sat +
subs[0]->ops.dsat)};
946 const auto dsat{
subs[0]->ops.dsat +
subs[1]->ops.dsat};
947 return {
count, sat, dsat};
950 const auto count{2 +
subs[0]->ops.count +
subs[1]->ops.count};
951 const auto sat{
subs[0]->ops.sat | (
subs[1]->ops.sat +
subs[0]->ops.dsat)};
952 return {
count, sat, {}};
955 const auto count{3 +
subs[0]->ops.count +
subs[1]->ops.count};
956 const auto sat{
subs[0]->ops.sat |
subs[1]->ops.sat};
957 const auto dsat{
subs[0]->ops.dsat |
subs[1]->ops.dsat};
958 return {
count, sat, dsat};
961 const auto count{3 +
subs[0]->ops.count +
subs[1]->ops.count +
subs[2]->ops.count};
963 const auto dsat{
subs[0]->ops.dsat +
subs[2]->ops.dsat};
964 return {
count, sat, dsat};
978 for (
const auto& sub :
subs) {
979 count += sub->ops.count + 1;
980 auto next_sats =
Vector(sats[0] + sub->ops.dsat);
981 for (
size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub->ops.dsat) | (sats[j - 1] + sub->ops.sat));
982 next_sats.push_back(sats[sats.size() - 1] + sub->ops.sat);
983 sats = std::move(next_sats);
986 return {
count, sats[
k], sats[0]};
993 using namespace internal;
1009 const auto& x{
subs[0]->ss};
1010 const auto& y{
subs[1]->ss};
1011 const auto& z{
subs[2]->ss};
1013 (x.sat + SatInfo::If() + y.sat) | (x.dsat + SatInfo::If() + z.sat),
1014 x.dsat + SatInfo::If() + z.dsat
1018 const auto& x{
subs[0]->ss};
1019 const auto& y{
subs[1]->ss};
1020 return {x.sat + y.sat, {}};
1023 const auto& x{
subs[0]->ss};
1024 const auto& y{
subs[1]->ss};
1025 return {x.sat + y.sat + SatInfo::BinaryOp(), x.dsat + y.dsat + SatInfo::BinaryOp()};
1028 const auto& x{
subs[0]->ss};
1029 const auto& y{
subs[1]->ss};
1031 ((x.sat + y.dsat) | (x.dsat + y.sat)) + SatInfo::BinaryOp(),
1032 x.dsat + y.dsat + SatInfo::BinaryOp()
1036 const auto& x{
subs[0]->ss};
1037 const auto& y{
subs[1]->ss};
1038 return {(x.sat + SatInfo::If()) | (x.dsat + SatInfo::If() + y.sat), {}};
1041 const auto& x{
subs[0]->ss};
1042 const auto& y{
subs[1]->ss};
1049 const auto& x{
subs[0]->ss};
1050 const auto& y{
subs[1]->ss};
1051 return {SatInfo::If() + (x.sat | y.sat), SatInfo::If() + (x.dsat | y.dsat)};
1080 auto sats =
Vector(SatInfo::Empty());
1081 for (
size_t i = 0; i <
subs.size(); ++i) {
1084 auto add = i ? SatInfo::BinaryOp() : SatInfo::Empty();
1088 for (
size_t j = 1; j < sats.size(); ++j) {
1089 next_sats.push_back(((sats[j] +
subs[i]->
ss.
dsat) | (sats[j - 1] +
subs[i]->ss.sat)) + add);
1092 next_sats.push_back(sats[sats.size() - 1] +
subs[i]->ss.sat + add);
1094 sats = std::move(next_sats);
1123 const auto dsat{
subs[0]->ws.dsat +
subs[2]->ws.dsat};
1130 const auto dsat{
subs[0]->ws.dsat +
subs[1]->ws.dsat};
1147 for (
const auto& sub :
subs) {
1148 auto next_sats =
Vector(sats[0] + sub->ws.dsat);
1149 for (
size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub->ws.dsat) | (sats[j - 1] + sub->ws.sat));
1150 next_sats.push_back(sats[sats.size() - 1] + sub->ws.sat);
1151 sats = std::move(next_sats);
1154 return {sats[
k], sats[0]};
1160 template<
typename Ctx>
1162 using namespace internal;
1167 switch (
node.fragment) {
1169 std::vector<unsigned char> sig;
1171 return {
ZERO, InputStack(std::move(sig)).SetWithSig().SetAvailable(avail)};
1174 std::vector<unsigned char> key = ctx.ToPKBytes(
node.keys[0]), sig;
1176 return {
ZERO + InputStack(key), (InputStack(std::move(sig)).SetWithSig() + InputStack(key)).SetAvailable(avail)};
1182 for (
size_t i = 0; i <
node.keys.size(); ++i) {
1185 std::vector<unsigned char> sig;
1188 auto sat = InputStack(std::move(sig)).SetWithSig().SetAvailable(avail);
1192 std::vector<InputStack> next_sats;
1193 next_sats.push_back(sats[0] +
ZERO);
1194 for (
size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] +
ZERO) | (std::move(sats[j - 1]) + sat));
1195 next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(sat));
1197 sats = std::move(next_sats);
1201 auto& nsat{sats[0]};
1204 return {std::move(nsat), std::move(sats[
node.k])};
1211 for (
size_t i = 0; i <
node.keys.size(); ++i) {
1212 std::vector<unsigned char> sig;
1215 auto sat = InputStack(std::move(sig)).SetWithSig().SetAvailable(avail);
1219 std::vector<InputStack> next_sats;
1220 next_sats.push_back(sats[0]);
1221 for (
size_t j = 1; j < sats.size(); ++j) next_sats.push_back(sats[j] | (std::move(sats[j - 1]) + sat));
1222 next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(sat));
1224 sats = std::move(next_sats);
1227 InputStack nsat =
ZERO;
1228 for (
size_t i = 0; i <
node.k; ++i) nsat = std::move(nsat) +
ZERO;
1230 return {std::move(nsat), std::move(sats[
node.k])};
1237 for (
size_t i = 0; i < subres.size(); ++i) {
1239 auto& res = subres[subres.size() - i - 1];
1243 std::vector<InputStack> next_sats;
1244 next_sats.push_back(sats[0] + res.nsat);
1245 for (
size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + res.nsat) | (std::move(sats[j - 1]) + res.sat));
1246 next_sats.push_back(std::move(sats[sats.size() - 1]) + std::move(res.sat));
1248 sats = std::move(next_sats);
1252 InputStack nsat = INVALID;
1253 for (
size_t i = 0; i < sats.size(); ++i) {
1260 if (i != 0 && i !=
node.k) sats[i].SetMalleable().SetNonCanon();
1262 if (i !=
node.k) nsat = std::move(nsat) | std::move(sats[i]);
1265 return {std::move(nsat), std::move(sats[
node.k])};
1268 return {INVALID, ctx.CheckOlder(
node.k) ?
EMPTY : INVALID};
1271 return {INVALID, ctx.CheckAfter(
node.k) ?
EMPTY : INVALID};
1274 std::vector<unsigned char> preimage;
1276 return {
ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)};
1279 std::vector<unsigned char> preimage;
1281 return {
ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)};
1284 std::vector<unsigned char> preimage;
1286 return {
ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)};
1289 std::vector<unsigned char> preimage;
1291 return {
ZERO32, InputStack(std::move(preimage)).SetAvailable(avail)};
1294 auto& x = subres[0], &y = subres[1];
1301 return {(y.nsat + x.sat).SetNonCanon(), y.sat + x.sat};
1304 auto& x = subres[0], &y = subres[1];
1310 return {(y.nsat + x.nsat) | (y.sat + x.nsat).SetMalleable().SetNonCanon() | (y.nsat + x.sat).SetMalleable().SetNonCanon(), y.sat + x.sat};
1313 auto& x = subres[0], &z = subres[1];
1315 return {z.nsat + x.nsat, (z.nsat + x.sat) | (z.sat + x.nsat) | (z.sat + x.sat).SetMalleable().SetNonCanon()};
1318 auto& x = subres[0], &z = subres[1];
1319 return {INVALID, std::move(x.sat) | (z.sat + x.nsat)};
1322 auto& x = subres[0], &z = subres[1];
1323 return {z.nsat + x.nsat, std::move(x.sat) | (z.sat + x.nsat)};
1326 auto& x = subres[0], &z = subres[1];
1327 return {(x.nsat +
ONE) | (z.nsat +
ZERO), (x.sat +
ONE) | (z.sat +
ZERO)};
1330 auto& x = subres[0], &y = subres[1], &z = subres[2];
1331 return {(y.nsat + x.sat).SetNonCanon() | (z.nsat + x.nsat), (y.sat + x.sat) | (z.sat + x.nsat)};
1337 return std::move(subres[0]);
1339 auto &x = subres[0];
1343 auto &x = subres[0];
1349 return {InputStack(
ZERO).SetMalleable(x.nsat.available !=
Availability::NO && !x.nsat.has_sig), std::move(x.sat)};
1352 auto &x = subres[0];
1353 return {INVALID, std::move(x.sat)};
1359 return {INVALID, INVALID};
1363 auto ret = helper(
node, subres);
1386 if (
node.GetType() <<
"d"_mst && !
ret.nsat.malleable)
assert(!
ret.nsat.non_canon);
1394 if (
node.GetType() <<
"me"_mst)
assert(!
ret.nsat.malleable);
1405 return TreeEval<InputResult>(tester);
1420 Comp(
const Ctx& ctx) : ctx_ptr(&ctx) {}
1421 bool operator()(
const Key& a,
const Key& b)
const {
return ctx_ptr->KeyCompare(a, b); }
1427 using keyset = std::set<Key, Comp>;
1428 using state = std::optional<keyset>;
1432 if (
node.has_duplicate_keys.has_value() && *
node.has_duplicate_keys)
return {};
1435 for (
auto& sub :
subs) {
1436 if (!sub.has_value()) {
1437 node.has_duplicate_keys =
true;
1444 size_t keys_count =
node.keys.size();
1445 keyset key_set{
node.keys.begin(),
node.keys.end(), Comp(ctx)};
1446 if (key_set.size() != keys_count) {
1448 node.has_duplicate_keys =
true;
1453 for (
auto& sub :
subs) {
1454 keys_count += sub->size();
1457 if (key_set.size() < sub->size()) std::swap(key_set, *sub);
1458 key_set.merge(*sub);
1459 if (key_set.size() != keys_count) {
1460 node.has_duplicate_keys =
true;
1465 node.has_duplicate_keys =
false;
1469 TreeEval<state>(upfn);
1493 return !((
GetType() &
"BKW"_mst) ==
""_mst);
1539 for (
auto& sub:
subs)
if (sub)
return sub;
1540 if (!
node.IsSaneSubexpression())
return &
node;
1547 template<
typename F>
1552 switch (
node.fragment) {
1553 case Fragment::JUST_0:
1555 case Fragment::JUST_1:
1557 case Fragment::PK_K:
1558 case Fragment::PK_H:
1559 case Fragment::MULTI:
1560 case Fragment::MULTI_A:
1561 case Fragment::AFTER:
1562 case Fragment::OLDER:
1563 case Fragment::HASH256:
1564 case Fragment::HASH160:
1565 case Fragment::SHA256:
1566 case Fragment::RIPEMD160:
1567 return bool{fn(node)};
1589 if (
GetType() ==
""_mst)
return false;
1621 template<
typename Ctx>
1622 Availability Satisfy(
const Ctx& ctx, std::vector<std::vector<unsigned char>>& stack,
bool nonmalleable =
true)
const {
1625 stack = std::move(
ret.sat.stack);
1626 return ret.sat.available;
1647 template <
typename Ctx>
Node(
const Ctx& ctx,
Fragment nt, std::vector<
NodeRef<Key>> sub, std::vector<unsigned char> arg, uint32_t val = 0)
1649 template <
typename Ctx>
Node(
const Ctx& ctx,
Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0)
1653 template <
typename Ctx>
Node(
const Ctx& ctx,
Fragment nt, std::vector<Key> key, uint32_t val = 0)
1657 template <
typename Ctx>
Node(
const Ctx& ctx,
Fragment nt, uint32_t val = 0)
1661 namespace internal {
1720 template<
typename Key,
typename Ctx>
1724 if (key_size < 1)
return {};
1725 auto key = ctx.FromString(in.
begin(), in.
begin() + key_size);
1726 if (!key)
return {};
1727 return {{std::move(*key), key_size}};
1731 template<
typename Ctx>
1736 if (hash_size < 1)
return {};
1737 std::string val = std::string(in.
begin(), in.
begin() + hash_size);
1738 if (!
IsHex(val))
return {};
1740 if (hash.size() != expected_size)
return {};
1741 return {{std::move(hash), hash_size}};
1745 template<
typename Key>
1749 constructed.pop_back();
1751 constructed.back() = MakeNodeRef<Key>(
internal::NoDupCheck{}, script_ctx, nt,
Vector(std::move(child), std::move(constructed.back())));
1753 constructed.back() = MakeNodeRef<Key>(
internal::NoDupCheck{}, script_ctx, nt,
Vector(std::move(constructed.back()), std::move(child)));
1762 template<
typename Key,
typename Ctx>
1777 size_t script_size{1};
1781 std::vector<std::tuple<ParseContext, int64_t, int64_t>> to_parse;
1782 std::vector<NodeRef<Key>> constructed;
1784 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1787 const auto parse_multi_exp = [&](
Span<const char>& in,
const bool is_multi_a) ->
bool {
1790 if (ctx.MsContext() != required_ctx)
return false;
1793 if (next_comma < 1)
return false;
1796 in = in.
subspan(next_comma + 1);
1798 std::vector<Key>
keys;
1799 while (next_comma != -1) {
1801 int key_length = (next_comma == -1) ?
FindNextChar(in,
')') : next_comma;
1802 if (key_length < 1)
return false;
1803 auto key = ctx.FromString(in.
begin(), in.
begin() + key_length);
1804 if (!key)
return false;
1805 keys.push_back(std::move(*key));
1806 in = in.
subspan(key_length + 1);
1808 if (
keys.size() < 1 ||
keys.size() > max_keys)
return false;
1809 if (k < 1 || k > (int64_t)
keys.size())
return false;
1815 script_size += 2 + (
keys.size() > 16) + (
k > 16) + 34 *
keys.size();
1821 while (!to_parse.empty()) {
1822 if (script_size > max_size)
return {};
1825 auto [cur_context, n,
k] = to_parse.back();
1826 to_parse.pop_back();
1828 switch (cur_context) {
1829 case ParseContext::WRAPPED_EXPR: {
1830 std::optional<size_t> colon_index{};
1831 for (
size_t i = 1; i < in.
size(); ++i) {
1836 if (in[i] <
'a' || in[i] >
'z')
break;
1839 bool last_was_v{
false};
1840 for (
size_t j = 0; colon_index && j < *colon_index; ++j) {
1841 if (script_size > max_size)
return {};
1844 to_parse.emplace_back(ParseContext::ALT, -1, -1);
1845 }
else if (in[j] ==
's') {
1847 to_parse.emplace_back(ParseContext::SWAP, -1, -1);
1848 }
else if (in[j] ==
'c') {
1851 }
else if (in[j] ==
'd') {
1853 to_parse.emplace_back(ParseContext::DUP_IF, -1, -1);
1854 }
else if (in[j] ==
'j') {
1856 to_parse.emplace_back(ParseContext::NON_ZERO, -1, -1);
1857 }
else if (in[j] ==
'n') {
1859 to_parse.emplace_back(ParseContext::ZERO_NOTEQUAL, -1, -1);
1860 }
else if (in[j] ==
'v') {
1863 if (last_was_v)
return {};
1864 to_parse.emplace_back(ParseContext::VERIFY, -1, -1);
1865 }
else if (in[j] ==
'u') {
1867 to_parse.emplace_back(ParseContext::WRAP_U, -1, -1);
1868 }
else if (in[j] ==
't') {
1870 to_parse.emplace_back(ParseContext::WRAP_T, -1, -1);
1871 }
else if (in[j] ==
'l') {
1875 to_parse.emplace_back(ParseContext::OR_I, -1, -1);
1879 last_was_v = (in[j] ==
'v');
1881 to_parse.emplace_back(ParseContext::EXPR, -1, -1);
1882 if (colon_index) in = in.
subspan(*colon_index + 1);
1885 case ParseContext::EXPR: {
1886 if (
Const(
"0", in)) {
1888 }
else if (
Const(
"1", in)) {
1890 }
else if (
Const(
"pk(", in)) {
1891 auto res = ParseKeyEnd<Key, Ctx>(in, ctx);
1892 if (!res)
return {};
1893 auto& [key, key_size] = *res;
1895 in = in.
subspan(key_size + 1);
1896 script_size +=
IsTapscript(ctx.MsContext()) ? 33 : 34;
1897 }
else if (
Const(
"pkh(", in)) {
1898 auto res = ParseKeyEnd<Key>(in, ctx);
1899 if (!res)
return {};
1900 auto& [key, key_size] = *res;
1902 in = in.
subspan(key_size + 1);
1904 }
else if (
Const(
"pk_k(", in)) {
1905 auto res = ParseKeyEnd<Key>(in, ctx);
1906 if (!res)
return {};
1907 auto& [key, key_size] = *res;
1909 in = in.
subspan(key_size + 1);
1910 script_size +=
IsTapscript(ctx.MsContext()) ? 32 : 33;
1911 }
else if (
Const(
"pk_h(", in)) {
1912 auto res = ParseKeyEnd<Key>(in, ctx);
1913 if (!res)
return {};
1914 auto& [key, key_size] = *res;
1916 in = in.
subspan(key_size + 1);
1918 }
else if (
Const(
"sha256(", in)) {
1920 if (!res)
return {};
1921 auto& [hash, hash_size] = *res;
1923 in = in.
subspan(hash_size + 1);
1925 }
else if (
Const(
"ripemd160(", in)) {
1927 if (!res)
return {};
1928 auto& [hash, hash_size] = *res;
1930 in = in.
subspan(hash_size + 1);
1932 }
else if (
Const(
"hash256(", in)) {
1934 if (!res)
return {};
1935 auto& [hash, hash_size] = *res;
1937 in = in.
subspan(hash_size + 1);
1939 }
else if (
Const(
"hash160(", in)) {
1941 if (!res)
return {};
1942 auto& [hash, hash_size] = *res;
1944 in = in.
subspan(hash_size + 1);
1946 }
else if (
Const(
"after(", in)) {
1948 if (arg_size < 1)
return {};
1951 if (num < 1 || num >= 0x80000000L)
return {};
1953 in = in.
subspan(arg_size + 1);
1954 script_size += 1 + (num > 16) + (num > 0x7f) + (num > 0x7fff) + (num > 0x7fffff);
1955 }
else if (
Const(
"older(", in)) {
1957 if (arg_size < 1)
return {};
1960 if (num < 1 || num >= 0x80000000L)
return {};
1962 in = in.
subspan(arg_size + 1);
1963 script_size += 1 + (num > 16) + (num > 0x7f) + (num > 0x7fff) + (num > 0x7fffff);
1964 }
else if (
Const(
"multi(", in)) {
1965 if (!parse_multi_exp(in,
false))
return {};
1966 }
else if (
Const(
"multi_a(", in)) {
1967 if (!parse_multi_exp(in,
true))
return {};
1968 }
else if (
Const(
"thresh(", in)) {
1970 if (next_comma < 1)
return {};
1972 if (
k < 1)
return {};
1973 in = in.
subspan(next_comma + 1);
1975 to_parse.emplace_back(ParseContext::THRESH, 1,
k);
1976 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1977 script_size += 2 + (
k > 16) + (
k > 0x7f) + (
k > 0x7fff) + (
k > 0x7fffff);
1978 }
else if (
Const(
"andor(", in)) {
1979 to_parse.emplace_back(ParseContext::ANDOR, -1, -1);
1980 to_parse.emplace_back(ParseContext::CLOSE_BRACKET, -1, -1);
1981 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
1982 to_parse.emplace_back(ParseContext::COMMA, -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);
1988 if (
Const(
"and_n(", in)) {
1989 to_parse.emplace_back(ParseContext::AND_N, -1, -1);
1991 }
else if (
Const(
"and_b(", in)) {
1992 to_parse.emplace_back(ParseContext::AND_B, -1, -1);
1994 }
else if (
Const(
"and_v(", in)) {
1995 to_parse.emplace_back(ParseContext::AND_V, -1, -1);
1997 }
else if (
Const(
"or_b(", in)) {
1998 to_parse.emplace_back(ParseContext::OR_B, -1, -1);
2000 }
else if (
Const(
"or_c(", in)) {
2001 to_parse.emplace_back(ParseContext::OR_C, -1, -1);
2003 }
else if (
Const(
"or_d(", in)) {
2004 to_parse.emplace_back(ParseContext::OR_D, -1, -1);
2006 }
else if (
Const(
"or_i(", in)) {
2007 to_parse.emplace_back(ParseContext::OR_I, -1, -1);
2012 to_parse.emplace_back(ParseContext::CLOSE_BRACKET, -1, -1);
2013 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
2014 to_parse.emplace_back(ParseContext::COMMA, -1, -1);
2015 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
2019 case ParseContext::ALT: {
2023 case ParseContext::SWAP: {
2031 case ParseContext::DUP_IF: {
2035 case ParseContext::NON_ZERO: {
2039 case ParseContext::ZERO_NOTEQUAL: {
2043 case ParseContext::VERIFY: {
2044 script_size += (constructed.back()->GetType() <<
"x"_mst);
2048 case ParseContext::WRAP_U: {
2052 case ParseContext::WRAP_T: {
2056 case ParseContext::AND_B: {
2060 case ParseContext::AND_N: {
2061 auto mid = std::move(constructed.back());
2062 constructed.pop_back();
2066 case ParseContext::AND_V: {
2070 case ParseContext::OR_B: {
2074 case ParseContext::OR_C: {
2078 case ParseContext::OR_D: {
2082 case ParseContext::OR_I: {
2086 case ParseContext::ANDOR: {
2087 auto right = std::move(constructed.back());
2088 constructed.pop_back();
2089 auto mid = std::move(constructed.back());
2090 constructed.pop_back();
2094 case ParseContext::THRESH: {
2095 if (in.
size() < 1)
return {};
2098 to_parse.emplace_back(ParseContext::THRESH, n+1,
k);
2099 to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
2101 }
else if (in[0] ==
')') {
2102 if (
k > n)
return {};
2105 std::vector<NodeRef<Key>>
subs;
2106 for (
int i = 0; i < n; ++i) {
2107 subs.push_back(std::move(constructed.back()));
2108 constructed.pop_back();
2110 std::reverse(
subs.begin(),
subs.end());
2117 case ParseContext::COMMA: {
2118 if (in.
size() < 1 || in[0] !=
',')
return {};
2122 case ParseContext::CLOSE_BRACKET: {
2123 if (in.
size() < 1 || in[0] !=
')')
return {};
2131 assert(constructed.size() == 1);
2133 if (in.
size() > 0)
return {};
2135 tl_node->DuplicateKeyCheck(ctx);
2221 template<
typename Key,
typename Ctx,
typename I>
2225 std::vector<std::tuple<DecodeContext, int64_t, int64_t>> to_parse;
2226 std::vector<NodeRef<Key>> constructed;
2230 to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
2232 while (!to_parse.empty()) {
2234 if (!constructed.empty() && !constructed.back()->IsValid())
return {};
2237 auto [cur_context, n,
k] = to_parse.back();
2238 to_parse.pop_back();
2240 switch(cur_context) {
2241 case DecodeContext::SINGLE_BKV_EXPR: {
2242 if (in >= last)
return {};
2245 if (in[0].first ==
OP_1) {
2250 if (in[0].first ==
OP_0) {
2256 if (in[0].second.size() == 33 || in[0].second.size() == 32) {
2257 auto key = ctx.FromPKBytes(in[0].second.begin(), in[0].second.end());
2258 if (!key)
return {};
2264 auto key = ctx.FromPKHBytes(in[2].second.begin(), in[2].second.end());
2265 if (!key)
return {};
2271 std::optional<int64_t> num;
2274 if (*num < 1 || *num > 0x7FFFFFFFL)
return {};
2280 if (num < 1 || num > 0x7FFFFFFFL)
return {};
2286 if (in[2].first ==
OP_SHA256 && in[1].second.size() == 32) {
2290 }
else if (in[2].first ==
OP_RIPEMD160 && in[1].second.size() == 20) {
2294 }
else if (in[2].first ==
OP_HASH256 && in[1].second.size() == 32) {
2298 }
else if (in[2].first ==
OP_HASH160 && in[1].second.size() == 20) {
2307 std::vector<Key>
keys;
2309 if (!n || last - in < 3 + *n)
return {};
2310 if (*n < 1 || *n > 20)
return {};
2311 for (
int i = 0; i < *n; ++i) {
2312 if (in[2 + i].second.size() != 33)
return {};
2313 auto key = ctx.FromPKBytes(in[2 + i].second.begin(), in[2 + i].second.end());
2314 if (!key)
return {};
2315 keys.push_back(std::move(*key));
2318 if (!
k || *k < 1 || *k > *n)
return {};
2320 std::reverse(
keys.begin(),
keys.end());
2325 if (last - in >= 4 && in[0].first ==
OP_NUMEQUAL) {
2331 if (last - in < 2 + *
k * 2)
return {};
2332 std::vector<Key>
keys;
2335 for (
int pos = 2;; pos += 2) {
2336 if (last - in < pos + 2)
return {};
2339 if (in[pos + 1].second.size() != 32)
return {};
2340 auto key = ctx.FromPKBytes(in[pos + 1].second.begin(), in[pos + 1].second.end());
2341 if (!key)
return {};
2342 keys.push_back(std::move(*key));
2348 if (
keys.size() < (
size_t)*
k)
return {};
2349 in += 2 +
keys.size() * 2;
2350 std::reverse(
keys.begin(),
keys.end());
2361 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2367 to_parse.emplace_back(DecodeContext::VERIFY, -1, -1);
2368 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2374 to_parse.emplace_back(DecodeContext::ZERO_NOTEQUAL, -1, -1);
2375 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2380 if (*num < 1)
return {};
2382 to_parse.emplace_back(DecodeContext::THRESH_W, 0, *num);
2388 to_parse.emplace_back(DecodeContext::ENDIF, -1, -1);
2389 to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
2400 to_parse.emplace_back(DecodeContext::AND_B, -1, -1);
2401 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2402 to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
2408 to_parse.emplace_back(DecodeContext::OR_B, -1, -1);
2409 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2410 to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
2416 case DecodeContext::BKV_EXPR: {
2417 to_parse.emplace_back(DecodeContext::MAYBE_AND_V, -1, -1);
2418 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2421 case DecodeContext::W_EXPR: {
2423 if (in >= last)
return {};
2426 to_parse.emplace_back(DecodeContext::ALT, -1, -1);
2428 to_parse.emplace_back(DecodeContext::SWAP, -1, -1);
2430 to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
2433 case DecodeContext::MAYBE_AND_V: {
2437 to_parse.emplace_back(DecodeContext::AND_V, -1, -1);
2439 to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
2443 case DecodeContext::SWAP: {
2444 if (in >= last || in[0].first !=
OP_SWAP || constructed.empty())
return {};
2449 case DecodeContext::ALT: {
2450 if (in >= last || in[0].first !=
OP_TOALTSTACK || constructed.empty())
return {};
2456 if (constructed.empty())
return {};
2460 case DecodeContext::DUP_IF: {
2461 if (constructed.empty())
return {};
2465 case DecodeContext::VERIFY: {
2466 if (constructed.empty())
return {};
2470 case DecodeContext::NON_ZERO: {
2471 if (constructed.empty())
return {};
2475 case DecodeContext::ZERO_NOTEQUAL: {
2476 if (constructed.empty())
return {};
2480 case DecodeContext::AND_V: {
2481 if (constructed.size() < 2)
return {};
2485 case DecodeContext::AND_B: {
2486 if (constructed.size() < 2)
return {};
2490 case DecodeContext::OR_B: {
2491 if (constructed.size() < 2)
return {};
2495 case DecodeContext::OR_C: {
2496 if (constructed.size() < 2)
return {};
2500 case DecodeContext::OR_D: {
2501 if (constructed.size() < 2)
return {};
2505 case DecodeContext::ANDOR: {
2506 if (constructed.size() < 3)
return {};
2508 constructed.pop_back();
2510 constructed.pop_back();
2515 case DecodeContext::THRESH_W: {
2516 if (in >= last)
return {};
2517 if (in[0].first ==
OP_ADD) {
2519 to_parse.emplace_back(DecodeContext::THRESH_W, n+1,
k);
2520 to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
2522 to_parse.emplace_back(DecodeContext::THRESH_E, n+1,
k);
2524 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2528 case DecodeContext::THRESH_E: {
2529 if (k < 1 || k > n || constructed.size() <
static_cast<size_t>(n))
return {};
2530 std::vector<NodeRef<Key>>
subs;
2531 for (
int i = 0; i < n; ++i) {
2533 constructed.pop_back();
2534 subs.push_back(std::move(sub));
2539 case DecodeContext::ENDIF: {
2540 if (in >= last)
return {};
2545 to_parse.emplace_back(DecodeContext::ENDIF_ELSE, -1, -1);
2546 to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
2549 else if (in[0].first ==
OP_IF) {
2550 if (last - in >= 2 && in[1].first ==
OP_DUP) {
2552 to_parse.emplace_back(DecodeContext::DUP_IF, -1, -1);
2555 to_parse.emplace_back(DecodeContext::NON_ZERO, -1, -1);
2561 }
else if (in[0].first ==
OP_NOTIF) {
2563 to_parse.emplace_back(DecodeContext::ENDIF_NOTIF, -1, -1);
2570 case DecodeContext::ENDIF_NOTIF: {
2571 if (in >= last)
return {};
2574 to_parse.emplace_back(DecodeContext::OR_D, -1, -1);
2576 to_parse.emplace_back(DecodeContext::OR_C, -1, -1);
2579 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2582 case DecodeContext::ENDIF_ELSE: {
2583 if (in >= last)
return {};
2584 if (in[0].first ==
OP_IF) {
2587 }
else if (in[0].first ==
OP_NOTIF) {
2589 to_parse.emplace_back(DecodeContext::ANDOR, -1, -1);
2591 to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
2599 if (constructed.size() != 1)
return {};
2601 tl_node->DuplicateKeyCheck(ctx);
2604 if (!tl_node->IsValidTopLevel())
return {};
2610 template<
typename Ctx>
2612 return internal::Parse<typename Ctx::Key>(str, ctx);
2615 template<
typename Ctx>
2617 using namespace internal;
2621 if (!decomposed)
return {};
2622 auto it = decomposed->begin();
2623 auto ret = DecodeScript<typename Ctx::Key>(it, decomposed->end(), ctx);
2624 if (!
ret)
return {};
2625 if (it != decomposed->end())
return {};
#define CHECK_NONFATAL(condition)
Identity function.
Serialized script, used inside transaction inputs and outputs.
A Span is an object that can refer to a contiguous sequence of objects.
constexpr std::size_t size() const noexcept
constexpr C * begin() const noexcept
CONSTEXPR_IF_NOT_DEBUG Span< C > last(std::size_t count) const noexcept
CONSTEXPR_IF_NOT_DEBUG Span< C > subspan(std::size_t offset) const noexcept
This type encapsulates the miniscript type system properties.
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).
uint32_t m_flags
Internal bitmap of properties (see ""_mst operator for details).
constexpr Type(uint32_t flags)
Internal constructor used by the ""_mst operator.
constexpr Type If(bool x) const
The empty type if x is false, itself otherwise.
constexpr Type operator&(Type x) const
Compute the type with the intersection of properties.
constexpr bool operator<(Type x) const
Comparison operator to enable use in sets/maps (total ordering incompatible with <<).
constexpr Type operator|(Type x) const
Compute the type with the union of properties.
constexpr bool operator==(Type x) const
Equality operator.
static const int WITNESS_SCALE_FACTOR
uint256 Hash(const T &in1)
Compute the 256-bit hash of an object.
static constexpr size_t TAPROOT_CONTROL_MAX_SIZE
#define CHECK(cond)
Unconditional failure on condition failure.
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.
int FindNextChar(Span< const char > sp, const char m)
std::optional< int64_t > ParseScriptNumber(const Opcode &in)
Determine whether the passed pair (created by DecomposeScript) is pushing a number.
Type SanitizeType(Type e)
A helper sanitizer/checker for the output of CalcType.
std::optional< std::vector< Opcode > > DecomposeScript(const CScript &script)
Decode a script into opcode/push pairs.
constexpr uint32_t TX_BODY_LEEWAY_WEIGHT
Data other than the witness in a transaction. Overhead + vin count + one vin + vout count + one vout ...
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.
constexpr uint32_t TXIN_BYTES_NO_WITNESS
prevout + nSequence + scriptSig
static const auto ONE
A stack consisting of a single 0x01 element (interpreted as 1 by the script interpreted in numeric co...
static const auto ZERO32
A stack consisting of a single malleable 32-byte 0x0000...0000 element (for dissatisfying hash challe...
constexpr uint32_t MaxScriptSize(MiniscriptContext ms_ctx)
The maximum size of a script depending on the context.
constexpr uint32_t TX_OVERHEAD
nVersion + nLockTime
static const auto ZERO
A stack consisting of a single zero-length element (interpreted as 0 by the script interpreter in num...
constexpr uint32_t P2WSH_TXOUT_BYTES
nValue + script len + OP_0 + pushdata 32.
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.
@ 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.
static const auto INVALID
A stack representing the lack of any (dis)satisfactions.
NodeRef< Key > Parse(Span< const char > in, const Ctx &ctx)
Parse a miniscript from its textual descriptor form.
@ 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).
static const auto EMPTY
The empty stack.
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.
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...
NodeRef< Key > DecodeScript(I &in, I last, const Ctx &ctx)
Parse a miniscript from a bitcoin script.
std::shared_ptr< const Node< Key > > NodeRef
constexpr bool IsTapscript(MiniscriptContext ms_ctx)
Whether the context Tapscript, ensuring the only other possibility is P2WSH.
NodeRef< Key > MakeNodeRef(Args &&... args)
Construct a miniscript node as a shared_ptr.
NodeRef< typename Ctx::Key > FromScript(const CScript &script, const Ctx &ctx)
NodeRef< typename Ctx::Key > FromString(const std::string &str, const Ctx &ctx)
std::pair< opcodetype, std::vector< unsigned char > > Opcode
Fragment
The different node types in miniscript.
@ 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.
@ 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
@ 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.
@ MULTI
[k] [key_n]* [n] OP_CHECKMULTISIG (only available within P2WSH context)
bool Const(const std::string &str, Span< const char > &sp)
Parse a constant.
static constexpr unsigned int MAX_STANDARD_P2WSH_STACK_ITEMS
The maximum number of witness stack items in a standard P2WSH script.
static constexpr int32_t MAX_STANDARD_TX_WEIGHT
The maximum weight for transactions we're willing to relay/mine.
static constexpr unsigned int MAX_STANDARD_P2WSH_SCRIPT_SIZE
The maximum size in bytes of a standard witnessScript.
static constexpr unsigned int MAX_PUBKEYS_PER_MULTI_A
The limit of keys in OP_CHECKSIGADD-based scripts.
static const int MAX_STACK_SIZE
static const int MAX_OPS_PER_SCRIPT
CScript BuildScript(Ts &&... inputs)
Build a script by concatenating other scripts, or any argument accepted by CScript::operator<<.
static const int MAX_PUBKEYS_PER_MULTISIG
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...
std::vector< Byte > ParseHex(std::string_view hex_str)
Like TryParseHex, but returns an empty vector on invalid input.
A node in a miniscript expression.
const Type typ
Cached expression type (computed by CalcType and fed through SanitizeType).
uint32_t GetStaticOps() const
Return the number of ops in the script (not counting the dynamic ones that depend on execution).
Result TreeEval(UpFn upfn) const
Like TreeEval, but without downfn or State type.
bool IsBKW() const
Whether this node is of type B, K or W.
Node(const Ctx &ctx, Fragment nt, std::vector< NodeRef< Key >> sub, std::vector< unsigned char > arg, uint32_t val=0)
internal::InputResult ProduceInput(const Ctx &ctx) const
CScript ToScript(const Ctx &ctx) const
bool CheckStackSize() const
Check the maximum stack size for this script against the policy limit.
internal::StackSize CalcStackSize() const
bool IsSaneSubexpression() const
Whether the apparent policy of this node matches its script semantics. Doesn't guarantee it is a safe...
Type GetType() const
Return the expression type.
friend int Compare(const Node< Key > &node1, const Node< Key > &node2)
Compare two miniscript subtrees, using a non-recursive algorithm.
const size_t scriptlen
Cached script length (computed by CalcScriptLen).
std::optional< bool > has_duplicate_keys
Whether a public key appears more than once in this node.
const uint32_t k
The k parameter (time for OLDER/AFTER, threshold for THRESH(_M))
bool NeedsSignature() const
Check whether this script always needs a signature.
std::optional< Result > TreeEvalMaybe(UpFn upfn) const
Like TreeEvalMaybe, but without downfn or State type.
bool CheckOpsLimit() const
Check the ops limit of this script against the consensus limit.
std::vector< NodeRef< Key > > subs
Subexpressions (for WRAP_*/AND_*/OR_*/ANDOR/THRESH)
Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, std::vector< unsigned char > arg, uint32_t val=0)
const Fragment fragment
What node type this node is.
Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, std::vector< NodeRef< Key >> sub, std::vector< unsigned char > arg, uint32_t val=0)
Node(const Ctx &ctx, Fragment nt, uint32_t val=0)
std::optional< uint32_t > GetExecStackSize() const
Return the maximum size of the stack during execution of this script.
const Node * FindInsaneSub() const
Find an insane subnode which has no insane children. Nullptr if there is none.
internal::WitnessSize CalcWitnessSize() const
Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, uint32_t val=0)
Result TreeEval(State root_state, DownFn &&downfn, UpFn upfn) const
Like TreeEvalMaybe, but always produces a result.
internal::Ops CalcOps() const
Node(const Ctx &ctx, Fragment nt, std::vector< NodeRef< Key >> sub, std::vector< Key > key, uint32_t val=0)
std::optional< uint32_t > GetStackSize() const
Return the maximum number of stack elements needed to satisfy this script non-malleably.
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.
const MiniscriptContext m_script_ctx
The Script context for this node. Either P2WSH or Tapscript.
size_t CalcScriptLen() const
Compute the length of the script for this miniscript (including children).
bool IsSane() const
Check whether this node is safe as a script on its own.
std::optional< uint32_t > GetOps() const
Return the maximum number of ops needed to satisfy this script non-malleably.
bool IsValidTopLevel() const
Check whether this node is valid as a script on its own.
bool IsNotSatisfiable() const
Whether no satisfaction exists for this node.
const internal::WitnessSize ws
Cached witness size bounds.
bool IsNonMalleable() const
Check whether this script can always be satisfied in a non-malleable way.
Type CalcType() const
Compute the type for this miniscript.
bool CheckDuplicateKey() const
Check whether there is no duplicate key across this fragment and all its sub-fragments.
Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, std::vector< NodeRef< Key >> sub, std::vector< Key > key, uint32_t val=0)
size_t ScriptSize() const
Return the size of the script for this expression (faster than ToScript().size()).
std::optional< uint32_t > GetWitnessSize() const
Return the maximum size in bytes of a witness to satisfy this script non-malleably.
Node(const Ctx &ctx, Fragment nt, std::vector< NodeRef< Key >> sub, uint32_t val=0)
bool ValidSatisfactions() const
Whether successful non-malleable satisfactions are guaranteed to be valid.
const std::vector< Key > keys
The keys used by this expression (only for PK_K/PK_H/MULTI)
std::optional< Result > TreeEvalMaybe(State root_state, DownFn downfn, UpFn upfn) const
std::optional< std::string > ToString(const CTx &ctx) const
void DuplicateKeyCheck(const Ctx &ctx) const
Update duplicate key information in this Node.
Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, std::vector< NodeRef< Key >> sub, uint32_t val=0)
bool operator==(const Node< Key > &arg) const
Equality testing.
Node(internal::NoDupCheck, MiniscriptContext script_ctx, Fragment nt, std::vector< Key > key, uint32_t val=0)
bool CheckTimeLocksMix() const
Check whether there is no satisfaction path that contains both timelocks and heightlocks.
Node(const Ctx &ctx, Fragment nt, std::vector< Key > key, uint32_t val=0)
Node(const Ctx &ctx, Fragment nt, std::vector< unsigned char > arg, uint32_t val=0)
MiniscriptContext GetMsCtx() const
Return the script context for this node.
const internal::Ops ops
Cached ops counts.
bool IsValid() const
Check whether this node is valid at all.
const std::vector< unsigned char > data
The data bytes in this expression (only for HASH160/HASH256/SHA256/RIPEMD10).
const internal::StackSize ss
Cached stack size bounds.
bool IsSatisfiable(F fn) const
Determine whether a Miniscript node is satisfiable.
Class whose objects represent the maximum of a list of integers.
friend MaxInt< I > operator|(const MaxInt< I > &a, const MaxInt< I > &b)
friend MaxInt< I > operator+(const MaxInt< I > &a, const MaxInt< I > &b)
Ops(uint32_t in_count, MaxInt< uint32_t > in_sat, MaxInt< uint32_t > in_dsat)
MaxInt< uint32_t > sat
Number of keys in possibly executed OP_CHECKMULTISIG(VERIFY)s to satisfy.
MaxInt< uint32_t > dsat
Number of keys in possibly executed OP_CHECKMULTISIG(VERIFY)s to dissatisfy.
uint32_t count
Non-push opcodes.
A data structure to help the calculation of stack size limits.
static constexpr SatInfo Nop() noexcept
A script consisting of just a repurposed nop (OP_CHECKLOCKTIMEVERIFY, OP_CHECKSEQUENCEVERIFY).
const int32_t exec
Mow much higher the stack size can be during execution compared to at the end.
static constexpr SatInfo OP_CHECKSIG() noexcept
static constexpr SatInfo BinaryOp() noexcept
A script consisting of just a binary operator (OP_BOOLAND, OP_BOOLOR, OP_ADD).
static constexpr SatInfo OP_VERIFY() noexcept
static constexpr SatInfo Push() noexcept
A script consisting of a single push opcode.
static constexpr SatInfo Empty() noexcept
The empty script.
constexpr SatInfo(int32_t in_netdiff, int32_t in_exec) noexcept
Script set with a single script in it, with specified netdiff and exec.
constexpr friend SatInfo operator|(const SatInfo &a, const SatInfo &b) noexcept
Script set union.
const int32_t netdiff
How much higher the stack size at start of execution can be compared to at the end.
constexpr SatInfo() noexcept
Empty script set.
static constexpr SatInfo OP_EQUALVERIFY() noexcept
static constexpr SatInfo OP_IFDUP(bool nonzero) noexcept
const bool valid
Whether a canonical satisfaction/dissatisfaction is possible at all.
static constexpr SatInfo OP_DUP() noexcept
static constexpr SatInfo OP_0NOTEQUAL() noexcept
static constexpr SatInfo If() noexcept
A script consisting of just OP_IF or OP_NOTIF.
static constexpr SatInfo OP_EQUAL() noexcept
static constexpr SatInfo OP_SIZE() noexcept
static constexpr SatInfo Hash() noexcept
A script consisting of a single hash opcode.
constexpr friend SatInfo operator+(const SatInfo &a, const SatInfo &b) noexcept
Script set concatenation.
constexpr StackSize(SatInfo in_both) noexcept
constexpr StackSize(SatInfo in_sat, SatInfo in_dsat) noexcept
MaxInt< uint32_t > sat
Maximum witness size to satisfy;.
MaxInt< uint32_t > dsat
Maximum witness size to dissatisfy;.
WitnessSize(MaxInt< uint32_t > in_sat, MaxInt< uint32_t > in_dsat)
static const std::vector< uint8_t > EMPTY
std::string HexStr(const Span< const uint8_t > s)
Convert a span of bytes to a lower-case hexadecimal string.
bool ParseInt64(std::string_view str, int64_t *out)
Convert string to signed 64-bit integer with strict parse error feedback.
bool IsHex(std::string_view str)
std::vector< typename std::common_type< Args... >::type > Vector(Args &&... args)
Construct a vector with the specified elements.