aboutsummaryrefslogtreecommitdiff
path: root/src/script/miniscript.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/script/miniscript.h')
-rw-r--r--src/script/miniscript.h449
1 files changed, 449 insertions, 0 deletions
diff --git a/src/script/miniscript.h b/src/script/miniscript.h
index a394aed146..2ff6b02561 100644
--- a/src/script/miniscript.h
+++ b/src/script/miniscript.h
@@ -220,6 +220,7 @@ enum class Fragment {
// WRAP_U(X) is represented as OR_I(X,0)
};
+
namespace internal {
//! Helper function for Node::CalcType.
@@ -1008,6 +1009,442 @@ inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
return tl_node;
}
+/** Decode a script into opcode/push pairs.
+ *
+ * Construct a vector with one element per opcode in the script, in reverse order.
+ * Each element is a pair consisting of the opcode, as well as the data pushed by
+ * the opcode (including OP_n), if any. OP_CHECKSIGVERIFY, OP_CHECKMULTISIGVERIFY,
+ * and OP_EQUALVERIFY are decomposed into OP_CHECKSIG, OP_CHECKMULTISIG, OP_EQUAL
+ * respectively, plus OP_VERIFY.
+ */
+bool DecomposeScript(const CScript& script, std::vector<std::pair<opcodetype, std::vector<unsigned char>>>& out);
+
+/** Determine whether the passed pair (created by DecomposeScript) is pushing a number. */
+bool ParseScriptNumber(const std::pair<opcodetype, std::vector<unsigned char>>& in, int64_t& k);
+
+enum class DecodeContext {
+ /** A single expression of type B, K, or V. Specifically, this can't be an
+ * and_v or an expression of type W (a: and s: wrappers). */
+ SINGLE_BKV_EXPR,
+ /** Potentially multiple SINGLE_BKV_EXPRs as children of (potentially multiple)
+ * and_v expressions. Syntactic sugar for MAYBE_AND_V + SINGLE_BKV_EXPR. */
+ BKV_EXPR,
+ /** An expression of type W (a: or s: wrappers). */
+ W_EXPR,
+
+ /** SWAP expects the next element to be OP_SWAP (inside a W-type expression that
+ * didn't end with FROMALTSTACK), and wraps the top of the constructed stack
+ * with s: */
+ SWAP,
+ /** ALT expects the next element to be TOALTSTACK (we must have already read a
+ * FROMALTSTACK earlier), and wraps the top of the constructed stack with a: */
+ ALT,
+ /** CHECK wraps the top constructed node with c: */
+ CHECK,
+ /** DUP_IF wraps the top constructed node with d: */
+ DUP_IF,
+ /** VERIFY wraps the top constructed node with v: */
+ VERIFY,
+ /** NON_ZERO wraps the top constructed node with j: */
+ NON_ZERO,
+ /** ZERO_NOTEQUAL wraps the top constructed node with n: */
+ ZERO_NOTEQUAL,
+
+ /** MAYBE_AND_V will check if the next part of the script could be a valid
+ * miniscript sub-expression, and if so it will push AND_V and SINGLE_BKV_EXPR
+ * to decode it and construct the and_v node. This is recursive, to deal with
+ * multiple and_v nodes inside each other. */
+ MAYBE_AND_V,
+ /** AND_V will construct an and_v node from the last two constructed nodes. */
+ AND_V,
+ /** AND_B will construct an and_b node from the last two constructed nodes. */
+ AND_B,
+ /** ANDOR will construct an andor node from the last three constructed nodes. */
+ ANDOR,
+ /** OR_B will construct an or_b node from the last two constructed nodes. */
+ OR_B,
+ /** OR_C will construct an or_c node from the last two constructed nodes. */
+ OR_C,
+ /** OR_D will construct an or_d node from the last two constructed nodes. */
+ OR_D,
+
+ /** In a thresh expression, all sub-expressions other than the first are W-type,
+ * and end in OP_ADD. THRESH_W will check for this OP_ADD and either push a W_EXPR
+ * or a SINGLE_BKV_EXPR and jump to THRESH_E accordingly. */
+ THRESH_W,
+ /** THRESH_E constructs a thresh node from the appropriate number of constructed
+ * children. */
+ THRESH_E,
+
+ /** ENDIF signals that we are inside some sort of OP_IF structure, which could be
+ * or_d, or_c, or_i, andor, d:, or j: wrapper, depending on what follows. We read
+ * a BKV_EXPR and then deal with the next opcode case-by-case. */
+ ENDIF,
+ /** If, inside an ENDIF context, we find an OP_NOTIF before finding an OP_ELSE,
+ * we could either be in an or_d or an or_c node. We then check for IFDUP to
+ * distinguish these cases. */
+ ENDIF_NOTIF,
+ /** If, inside an ENDIF context, we find an OP_ELSE, then we could be in either an
+ * or_i or an andor node. Read the next BKV_EXPR and find either an OP_IF or an
+ * OP_NOTIF. */
+ ENDIF_ELSE,
+};
+
+//! Parse a miniscript from a bitcoin script
+template<typename Key, typename Ctx, typename I>
+inline NodeRef<Key> DecodeScript(I& in, I last, const Ctx& ctx)
+{
+ // The two integers are used to hold state for thresh()
+ std::vector<std::tuple<DecodeContext, int64_t, int64_t>> to_parse;
+ std::vector<NodeRef<Key>> constructed;
+
+ // This is the top level, so we assume the type is B
+ // (in particular, disallowing top level W expressions)
+ to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
+
+ while (!to_parse.empty()) {
+ // Exit early if the Miniscript is not going to be valid.
+ if (!constructed.empty() && !constructed.back()->IsValid()) return {};
+
+ // Get the current context we are decoding within
+ auto [cur_context, n, k] = to_parse.back();
+ to_parse.pop_back();
+
+ switch(cur_context) {
+ case DecodeContext::SINGLE_BKV_EXPR: {
+ if (in >= last) return {};
+
+ // Constants
+ if (in[0].first == OP_1) {
+ ++in;
+ constructed.push_back(MakeNodeRef<Key>(Fragment::JUST_1));
+ break;
+ }
+ if (in[0].first == OP_0) {
+ ++in;
+ constructed.push_back(MakeNodeRef<Key>(Fragment::JUST_0));
+ break;
+ }
+ // Public keys
+ if (in[0].second.size() == 33) {
+ Key key;
+ if (!ctx.FromPKBytes(in[0].second.begin(), in[0].second.end(), key)) return {};
+ ++in;
+ constructed.push_back(MakeNodeRef<Key>(Fragment::PK_K, Vector(std::move(key))));
+ break;
+ }
+ 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) {
+ Key key;
+ if (!ctx.FromPKHBytes(in[2].second.begin(), in[2].second.end(), key)) return {};
+ in += 5;
+ constructed.push_back(MakeNodeRef<Key>(Fragment::PK_H, Vector(std::move(key))));
+ break;
+ }
+ // Time locks
+ if (last - in >= 2 && in[0].first == OP_CHECKSEQUENCEVERIFY && ParseScriptNumber(in[1], k)) {
+ in += 2;
+ if (k < 1 || k > 0x7FFFFFFFL) return {};
+ constructed.push_back(MakeNodeRef<Key>(Fragment::OLDER, k));
+ break;
+ }
+ if (last - in >= 2 && in[0].first == OP_CHECKLOCKTIMEVERIFY && ParseScriptNumber(in[1], k)) {
+ in += 2;
+ if (k < 1 || k > 0x7FFFFFFFL) return {};
+ constructed.push_back(MakeNodeRef<Key>(Fragment::AFTER, k));
+ break;
+ }
+ // Hashes
+ if (last - in >= 7 && in[0].first == OP_EQUAL && in[3].first == OP_VERIFY && in[4].first == OP_EQUAL && ParseScriptNumber(in[5], k) && k == 32 && in[6].first == OP_SIZE) {
+ if (in[2].first == OP_SHA256 && in[1].second.size() == 32) {
+ constructed.push_back(MakeNodeRef<Key>(Fragment::SHA256, in[1].second));
+ in += 7;
+ break;
+ } else if (in[2].first == OP_RIPEMD160 && in[1].second.size() == 20) {
+ constructed.push_back(MakeNodeRef<Key>(Fragment::RIPEMD160, in[1].second));
+ in += 7;
+ break;
+ } else if (in[2].first == OP_HASH256 && in[1].second.size() == 32) {
+ constructed.push_back(MakeNodeRef<Key>(Fragment::HASH256, in[1].second));
+ in += 7;
+ break;
+ } else if (in[2].first == OP_HASH160 && in[1].second.size() == 20) {
+ constructed.push_back(MakeNodeRef<Key>(Fragment::HASH160, in[1].second));
+ in += 7;
+ break;
+ }
+ }
+ // Multi
+ if (last - in >= 3 && in[0].first == OP_CHECKMULTISIG) {
+ std::vector<Key> keys;
+ if (!ParseScriptNumber(in[1], n)) return {};
+ if (last - in < 3 + n) return {};
+ if (n < 1 || n > 20) return {};
+ for (int i = 0; i < n; ++i) {
+ Key key;
+ if (in[2 + i].second.size() != 33) return {};
+ if (!ctx.FromPKBytes(in[2 + i].second.begin(), in[2 + i].second.end(), key)) return {};
+ keys.push_back(std::move(key));
+ }
+ if (!ParseScriptNumber(in[2 + n], k)) return {};
+ if (k < 1 || k > n) return {};
+ in += 3 + n;
+ std::reverse(keys.begin(), keys.end());
+ constructed.push_back(MakeNodeRef<Key>(Fragment::MULTI, std::move(keys), k));
+ break;
+ }
+ /** In the following wrappers, we only need to push SINGLE_BKV_EXPR rather
+ * than BKV_EXPR, because and_v commutes with these wrappers. For example,
+ * c:and_v(X,Y) produces the same script as and_v(X,c:Y). */
+ // c: wrapper
+ if (in[0].first == OP_CHECKSIG) {
+ ++in;
+ to_parse.emplace_back(DecodeContext::CHECK, -1, -1);
+ to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
+ break;
+ }
+ // v: wrapper
+ if (in[0].first == OP_VERIFY) {
+ ++in;
+ to_parse.emplace_back(DecodeContext::VERIFY, -1, -1);
+ to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
+ break;
+ }
+ // n: wrapper
+ if (in[0].first == OP_0NOTEQUAL) {
+ ++in;
+ to_parse.emplace_back(DecodeContext::ZERO_NOTEQUAL, -1, -1);
+ to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
+ break;
+ }
+ // Thresh
+ if (last - in >= 3 && in[0].first == OP_EQUAL && ParseScriptNumber(in[1], k)) {
+ if (k < 1) return {};
+ in += 2;
+ to_parse.emplace_back(DecodeContext::THRESH_W, 0, k);
+ break;
+ }
+ // OP_ENDIF can be WRAP_J, WRAP_D, ANDOR, OR_C, OR_D, or OR_I
+ if (in[0].first == OP_ENDIF) {
+ ++in;
+ to_parse.emplace_back(DecodeContext::ENDIF, -1, -1);
+ to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
+ break;
+ }
+ /** In and_b and or_b nodes, we only look for SINGLE_BKV_EXPR, because
+ * or_b(and_v(X,Y),Z) has script [X] [Y] [Z] OP_BOOLOR, the same as
+ * and_v(X,or_b(Y,Z)). In this example, the former of these is invalid as
+ * miniscript, while the latter is valid. So we leave the and_v "outside"
+ * while decoding. */
+ // and_b
+ if (in[0].first == OP_BOOLAND) {
+ ++in;
+ to_parse.emplace_back(DecodeContext::AND_B, -1, -1);
+ to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
+ to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
+ break;
+ }
+ // or_b
+ if (in[0].first == OP_BOOLOR) {
+ ++in;
+ to_parse.emplace_back(DecodeContext::OR_B, -1, -1);
+ to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
+ to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
+ break;
+ }
+ // Unrecognised expression
+ return {};
+ }
+ case DecodeContext::BKV_EXPR: {
+ to_parse.emplace_back(DecodeContext::MAYBE_AND_V, -1, -1);
+ to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
+ break;
+ }
+ case DecodeContext::W_EXPR: {
+ // a: wrapper
+ if (in >= last) return {};
+ if (in[0].first == OP_FROMALTSTACK) {
+ ++in;
+ to_parse.emplace_back(DecodeContext::ALT, -1, -1);
+ } else {
+ to_parse.emplace_back(DecodeContext::SWAP, -1, -1);
+ }
+ to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
+ break;
+ }
+ case DecodeContext::MAYBE_AND_V: {
+ // If we reach a potential AND_V top-level, check if the next part of the script could be another AND_V child
+ // These op-codes cannot end any well-formed miniscript so cannot be used in an and_v node.
+ 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) {
+ to_parse.emplace_back(DecodeContext::AND_V, -1, -1);
+ // BKV_EXPR can contain more AND_V nodes
+ to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
+ }
+ break;
+ }
+ case DecodeContext::SWAP: {
+ if (in >= last || in[0].first != OP_SWAP || constructed.empty()) return {};
+ ++in;
+ constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_S, Vector(std::move(constructed.back())));
+ break;
+ }
+ case DecodeContext::ALT: {
+ if (in >= last || in[0].first != OP_TOALTSTACK || constructed.empty()) return {};
+ ++in;
+ constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_A, Vector(std::move(constructed.back())));
+ break;
+ }
+ case DecodeContext::CHECK: {
+ if (constructed.empty()) return {};
+ constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_C, Vector(std::move(constructed.back())));
+ break;
+ }
+ case DecodeContext::DUP_IF: {
+ if (constructed.empty()) return {};
+ constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_D, Vector(std::move(constructed.back())));
+ break;
+ }
+ case DecodeContext::VERIFY: {
+ if (constructed.empty()) return {};
+ constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_V, Vector(std::move(constructed.back())));
+ break;
+ }
+ case DecodeContext::NON_ZERO: {
+ if (constructed.empty()) return {};
+ constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_J, Vector(std::move(constructed.back())));
+ break;
+ }
+ case DecodeContext::ZERO_NOTEQUAL: {
+ if (constructed.empty()) return {};
+ constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_N, Vector(std::move(constructed.back())));
+ break;
+ }
+ case DecodeContext::AND_V: {
+ if (constructed.size() < 2) return {};
+ BuildBack(Fragment::AND_V, constructed, /* reverse */ true);
+ break;
+ }
+ case DecodeContext::AND_B: {
+ if (constructed.size() < 2) return {};
+ BuildBack(Fragment::AND_B, constructed, /* reverse */ true);
+ break;
+ }
+ case DecodeContext::OR_B: {
+ if (constructed.size() < 2) return {};
+ BuildBack(Fragment::OR_B, constructed, /* reverse */ true);
+ break;
+ }
+ case DecodeContext::OR_C: {
+ if (constructed.size() < 2) return {};
+ BuildBack(Fragment::OR_C, constructed, /* reverse */ true);
+ break;
+ }
+ case DecodeContext::OR_D: {
+ if (constructed.size() < 2) return {};
+ BuildBack(Fragment::OR_D, constructed, /* reverse */ true);
+ break;
+ }
+ case DecodeContext::ANDOR: {
+ if (constructed.size() < 3) return {};
+ NodeRef<Key> left = std::move(constructed.back());
+ constructed.pop_back();
+ NodeRef<Key> right = std::move(constructed.back());
+ constructed.pop_back();
+ NodeRef<Key> mid = std::move(constructed.back());
+ constructed.back() = MakeNodeRef<Key>(Fragment::ANDOR, Vector(std::move(left), std::move(mid), std::move(right)));
+ break;
+ }
+ case DecodeContext::THRESH_W: {
+ if (in >= last) return {};
+ if (in[0].first == OP_ADD) {
+ ++in;
+ to_parse.emplace_back(DecodeContext::THRESH_W, n+1, k);
+ to_parse.emplace_back(DecodeContext::W_EXPR, -1, -1);
+ } else {
+ to_parse.emplace_back(DecodeContext::THRESH_E, n+1, k);
+ // All children of thresh have type modifier d, so cannot be and_v
+ to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
+ }
+ break;
+ }
+ case DecodeContext::THRESH_E: {
+ if (k < 1 || k > n || constructed.size() < static_cast<size_t>(n)) return {};
+ std::vector<NodeRef<Key>> subs;
+ for (int i = 0; i < n; ++i) {
+ NodeRef<Key> sub = std::move(constructed.back());
+ constructed.pop_back();
+ subs.push_back(std::move(sub));
+ }
+ constructed.push_back(MakeNodeRef<Key>(Fragment::THRESH, std::move(subs), k));
+ break;
+ }
+ case DecodeContext::ENDIF: {
+ if (in >= last) return {};
+
+ // could be andor or or_i
+ if (in[0].first == OP_ELSE) {
+ ++in;
+ to_parse.emplace_back(DecodeContext::ENDIF_ELSE, -1, -1);
+ to_parse.emplace_back(DecodeContext::BKV_EXPR, -1, -1);
+ }
+ // could be j: or d: wrapper
+ else if (in[0].first == OP_IF) {
+ if (last - in >= 2 && in[1].first == OP_DUP) {
+ in += 2;
+ to_parse.emplace_back(DecodeContext::DUP_IF, -1, -1);
+ } else if (last - in >= 3 && in[1].first == OP_0NOTEQUAL && in[2].first == OP_SIZE) {
+ in += 3;
+ to_parse.emplace_back(DecodeContext::NON_ZERO, -1, -1);
+ }
+ else {
+ return {};
+ }
+ // could be or_c or or_d
+ } else if (in[0].first == OP_NOTIF) {
+ ++in;
+ to_parse.emplace_back(DecodeContext::ENDIF_NOTIF, -1, -1);
+ }
+ else {
+ return {};
+ }
+ break;
+ }
+ case DecodeContext::ENDIF_NOTIF: {
+ if (in >= last) return {};
+ if (in[0].first == OP_IFDUP) {
+ ++in;
+ to_parse.emplace_back(DecodeContext::OR_D, -1, -1);
+ } else {
+ to_parse.emplace_back(DecodeContext::OR_C, -1, -1);
+ }
+ // or_c and or_d both require X to have type modifier d so, can't contain and_v
+ to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
+ break;
+ }
+ case DecodeContext::ENDIF_ELSE: {
+ if (in >= last) return {};
+ if (in[0].first == OP_IF) {
+ ++in;
+ BuildBack(Fragment::OR_I, constructed, /* reverse */ true);
+ } else if (in[0].first == OP_NOTIF) {
+ ++in;
+ to_parse.emplace_back(DecodeContext::ANDOR, -1, -1);
+ // andor requires X to have type modifier d, so it can't be and_v
+ to_parse.emplace_back(DecodeContext::SINGLE_BKV_EXPR, -1, -1);
+ } else {
+ return {};
+ }
+ break;
+ }
+ }
+ }
+ if (constructed.size() != 1) return {};
+ const NodeRef<Key> tl_node = std::move(constructed.front());
+ // Note that due to how ComputeType works (only assign the type to the node if the
+ // subs' types are valid) this would fail if any node of tree is badly typed.
+ if (!tl_node->IsValidTopLevel()) return {};
+ return tl_node;
+}
+
} // namespace internal
template<typename Ctx>
@@ -1015,6 +1452,18 @@ inline NodeRef<typename Ctx::Key> FromString(const std::string& str, const Ctx&
return internal::Parse<typename Ctx::Key>(str, ctx);
}
+template<typename Ctx>
+inline NodeRef<typename Ctx::Key> FromScript(const CScript& script, const Ctx& ctx) {
+ using namespace internal;
+ std::vector<std::pair<opcodetype, std::vector<unsigned char>>> decomposed;
+ if (!DecomposeScript(script, decomposed)) return {};
+ auto it = decomposed.begin();
+ auto ret = DecodeScript<typename Ctx::Key>(it, decomposed.end(), ctx);
+ if (!ret) return {};
+ if (it != decomposed.end()) return {};
+ return ret;
+}
+
} // namespace miniscript
#endif // BITCOIN_SCRIPT_MINISCRIPT_H
generated by cgit v1.2.3 (git 2.26.2) at 2024-11-07 10:59:48 +0000