Merge bitcoin/bitcoin#24147: Miniscript integration

2da94a4c6f55f7a3621f4a6f70902c52f735c868 fuzz: add a fuzz target for Miniscript decoding from Script (Antoine Poinsot)
f8369996e76dbc41a12f7b7eea14a7e7990a81c1 Miniscript: ops limit and stack size computation (Pieter Wuille)
2e55e88f86d0dd49b35d04af3f57e863498aabae Miniscript: conversion from script (Pieter Wuille)
1ddaa66eae67b102f5e37d212d366a5dcad4aa26 Miniscript: type system, script creation, text notation, tests (Pieter Wuille)
4fe29368c0ded0e62f437cab3a7c904f7fd3ad67 script: expose getter for CScriptNum, add a BuildScript helper (Antoine Poinsot)
f4e289f384efdda6c3f56e1e1c30820a91ac2612 script: move CheckMinimalPush from interpreter to script.h (Antoine Poinsot)
31ec6ae92a5d9910a26d90a6ff20bab27dee5826 script: make IsPushdataOp non-static (Antoine Poinsot)

Pull request description:

  Miniscript is a language for writing (a subset of) Bitcoin Scripts in a structured way.

  Miniscript permits:
  - To safely extend the Output Descriptor language to many more scripting features thanks to the typing system (composition).
  - Statical analysis of spending conditions, maximum spending cost of each branch, security properties, third-party malleability.
  - General satisfaction of any correctly typed ("valid" [0]) Miniscript. The satisfaction itself is also analyzable.
  - To extend the possibilities of external signers, because of all of the above and since it carries enough metadata.

  Miniscript guarantees:
  - That for any statically-analyzed as "safe" [0] Script, a witness can be constructed in the bounds of the consensus and standardness rules (standardness complete).
  - That unless the conditions of the Miniscript are met, no witness can be created for the Script (consensus sound).
  - Third-party malleability protection for the satisfaction of a sane Miniscript, which is too complex to summarize here.

  For more details around Miniscript (including the specifications), please refer to the [website](https://bitcoin.sipa.be/miniscript/).

  Miniscript was designed by Pieter Wuille, Andrew Poelstra and Sanket Kanjalkar.
  This PR is an updated and rebased version of #16800. See [the commit history of the Miniscript repository](https://github.com/sipa/miniscript/commits/master) for details about the changes made since September 2019 (TL;DR: bugfixes, introduction of timelock conflicts in the type system, `pk()` and `pkh()` aliases, `thresh_m` renamed to `multi`, all recursive algorithms were made non-recursive).

  This PR is also the first in a series of 3:
  - The first one (here) integrates the backbone of Miniscript.
  - The second one (#24148) introduces support for Miniscript in Output Descriptors, allowing for watch-only support of Miniscript Descriptors in the wallet.
  - The third one (#24149) implements signing for these Miniscript Descriptors, using Miniscript's satisfaction algorithm.

  Note to reviewers:
  - Miniscript is currently defined only for P2WSH. No Taproot yet.
  - Miniscript is different from the policy language (a high-level logical representation of a spending policy). A policy->Miniscript compiler is not included here.
  - The fuzz target included here is more interestingly extended in the 3rd PR to check a script's satisfaction against `VerifyScript`. I think it could be further improved by having custom mutators as we now have for multisig (see https://github.com/bitcoin/bitcoin/issues/23105). A minified corpus of Miniscript Scripts is available at https://github.com/bitcoin-core/qa-assets/pull/85.

  [0] We call "valid" any correctly-typed Miniscript. And "safe" any sane Miniscript, ie one whose satisfaction isn't malleable, which requires a key for any spending path, etc..

ACKs for top commit:
  jb55:
    ACK 2da94a4c6f55f7a3621f4a6f70902c52f735c868
  laanwj:
    Light code review ACK 2da94a4c6f55f7a3621f4a6f70902c52f735c868 (mostly reviewed the changes to the existing code and build system)

Tree-SHA512: d3ef558436cfcc699a50ad13caf1e776f7d0addddb433ee28ef38f66ea5c3e581382d8c748ccac9b51768e4b95712ed7a6112b0e3281a6551e0f325331de9167

12 files changed, 2419 insertions, 32 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index bcaad4aaa5..12e4c7d8b7 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -221,6 +221,7 @@ BITCOIN_CORE_H = \
   scheduler.h \
   script/descriptor.h \
   script/keyorigin.h \
+  script/miniscript.h \
   script/sigcache.h \
   script/sign.h \
   script/signingprovider.h \
@@ -590,6 +591,7 @@ libbitcoin_common_a_SOURCES = \
   rpc/util.cpp \
   scheduler.cpp \
   script/descriptor.cpp \
+  script/miniscript.cpp \
   script/sign.cpp \
   script/signingprovider.cpp \
   script/standard.cpp \
diff --git a/src/Makefile.test.include b/src/Makefile.test.include
index 5d25104327..9ae7886a6e 100644
--- a/src/Makefile.test.include
+++ b/src/Makefile.test.include
@@ -103,6 +103,7 @@ BITCOIN_TESTS =\
   test/merkle_tests.cpp \
   test/merkleblock_tests.cpp \
   test/miner_tests.cpp \
+  test/miniscript_tests.cpp \
   test/minisketch_tests.cpp \
   test/multisig_tests.cpp \
   test/net_peer_eviction_tests.cpp \
@@ -266,6 +267,7 @@ test_fuzz_fuzz_SOURCES = \
  test/fuzz/locale.cpp \
  test/fuzz/merkleblock.cpp \
  test/fuzz/message.cpp \
+ test/fuzz/miniscript_decode.cpp \
  test/fuzz/minisketch.cpp \
  test/fuzz/muhash.cpp \
  test/fuzz/multiplication_overflow.cpp \
diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
index 23fb9b6226..c4d13d7283 100644
--- a/src/script/interpreter.cpp
+++ b/src/script/interpreter.cpp
@@ -225,31 +225,6 @@ bool static CheckPubKeyEncoding(const valtype &vchPubKey, unsigned int flags, co
     return true;
 }
 
-bool CheckMinimalPush(const valtype& data, opcodetype opcode) {
-    // Excludes OP_1NEGATE, OP_1-16 since they are by definition minimal
-    assert(0 <= opcode && opcode <= OP_PUSHDATA4);
-    if (data.size() == 0) {
-        // Should have used OP_0.
-        return opcode == OP_0;
-    } else if (data.size() == 1 && data[0] >= 1 && data[0] <= 16) {
-        // Should have used OP_1 .. OP_16.
-        return false;
-    } else if (data.size() == 1 && data[0] == 0x81) {
-        // Should have used OP_1NEGATE.
-        return false;
-    } else if (data.size() <= 75) {
-        // Must have used a direct push (opcode indicating number of bytes pushed + those bytes).
-        return opcode == data.size();
-    } else if (data.size() <= 255) {
-        // Must have used OP_PUSHDATA.
-        return opcode == OP_PUSHDATA1;
-    } else if (data.size() <= 65535) {
-        // Must have used OP_PUSHDATA2.
-        return opcode == OP_PUSHDATA2;
-    }
-    return true;
-}
-
 int FindAndDelete(CScript& script, const CScript& b)
 {
     int nFound = 0;
diff --git a/src/script/interpreter.h b/src/script/interpreter.h
index cf1953ad22..fbd904fb7b 100644
--- a/src/script/interpreter.h
+++ b/src/script/interpreter.h
@@ -344,8 +344,6 @@ bool VerifyScript(const CScript& scriptSig, const CScript& scriptPubKey, const C
 
 size_t CountWitnessSigOps(const CScript& scriptSig, const CScript& scriptPubKey, const CScriptWitness* witness, unsigned int flags);
 
-bool CheckMinimalPush(const std::vector<unsigned char>& data, opcodetype opcode);
-
 int FindAndDelete(CScript& script, const CScript& b);
 
 #endif // BITCOIN_SCRIPT_INTERPRETER_H
diff --git a/src/script/miniscript.cpp b/src/script/miniscript.cpp
new file mode 100644
index 0000000000..d0bb937885
--- /dev/null
+++ b/src/script/miniscript.cpp
@@ -0,0 +1,348 @@
+// Copyright (c) 2019 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <string>
+#include <vector>
+#include <script/script.h>
+#include <script/standard.h>
+#include <script/miniscript.h>
+
+#include <assert.h>
+
+namespace miniscript {
+namespace internal {
+
+Type SanitizeType(Type e) {
+    int num_types = (e << "K"_mst) + (e << "V"_mst) + (e << "B"_mst) + (e << "W"_mst);
+    if (num_types == 0) return ""_mst; // No valid type, don't care about the rest
+    assert(num_types == 1); // K, V, B, W all conflict with each other
+    bool ok = // Work around a GCC 4.8 bug that breaks user-defined literals in macro calls.
+        (!(e << "z"_mst) || !(e << "o"_mst)) && // z conflicts with o
+        (!(e << "n"_mst) || !(e << "z"_mst)) && // n conflicts with z
+        (!(e << "n"_mst) || !(e << "W"_mst)) && // n conflicts with W
+        (!(e << "V"_mst) || !(e << "d"_mst)) && // V conflicts with d
+        (!(e << "K"_mst) ||  (e << "u"_mst)) && // K implies u
+        (!(e << "V"_mst) || !(e << "u"_mst)) && // V conflicts with u
+        (!(e << "e"_mst) || !(e << "f"_mst)) && // e conflicts with f
+        (!(e << "e"_mst) ||  (e << "d"_mst)) && // e implies d
+        (!(e << "V"_mst) || !(e << "e"_mst)) && // V conflicts with e
+        (!(e << "d"_mst) || !(e << "f"_mst)) && // d conflicts with f
+        (!(e << "V"_mst) ||  (e << "f"_mst)) && // V implies f
+        (!(e << "K"_mst) ||  (e << "s"_mst)) && // K implies s
+        (!(e << "z"_mst) ||  (e << "m"_mst)); // z implies m
+    assert(ok);
+    return e;
+}
+
+Type ComputeType(Fragment nodetype, 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) {
+    // Sanity check on data
+    if (nodetype == Fragment::SHA256 || nodetype == Fragment::HASH256) {
+        assert(data_size == 32);
+    } else if (nodetype == Fragment::RIPEMD160 || nodetype == Fragment::HASH160) {
+        assert(data_size == 20);
+    } else {
+        assert(data_size == 0);
+    }
+    // Sanity check on k
+    if (nodetype == Fragment::OLDER || nodetype == Fragment::AFTER) {
+        assert(k >= 1 && k < 0x80000000UL);
+    } else if (nodetype == Fragment::MULTI) {
+        assert(k >= 1 && k <= n_keys);
+    } else if (nodetype == Fragment::THRESH) {
+        assert(k >= 1 && k <= n_subs);
+    } else {
+        assert(k == 0);
+    }
+    // Sanity check on subs
+    if (nodetype == Fragment::AND_V || nodetype == Fragment::AND_B || nodetype == Fragment::OR_B ||
+        nodetype == Fragment::OR_C || nodetype == Fragment::OR_I || nodetype == Fragment::OR_D) {
+        assert(n_subs == 2);
+    } else if (nodetype == Fragment::ANDOR) {
+        assert(n_subs == 3);
+    } else if (nodetype == Fragment::WRAP_A || nodetype == Fragment::WRAP_S || nodetype == Fragment::WRAP_C ||
+               nodetype == Fragment::WRAP_D || nodetype == Fragment::WRAP_V || nodetype == Fragment::WRAP_J ||
+               nodetype == Fragment::WRAP_N) {
+        assert(n_subs == 1);
+    } else if (nodetype != Fragment::THRESH) {
+        assert(n_subs == 0);
+    }
+    // Sanity check on keys
+    if (nodetype == Fragment::PK_K || nodetype == Fragment::PK_H) {
+        assert(n_keys == 1);
+    } else if (nodetype == Fragment::MULTI) {
+        assert(n_keys >= 1 && n_keys <= 20);
+    } else {
+        assert(n_keys == 0);
+    }
+
+    // Below is the per-nodetype logic for computing the expression types.
+    // It heavily relies on Type's << operator (where "X << a_mst" means
+    // "X has all properties listed in a").
+    switch (nodetype) {
+        case Fragment::PK_K: return "Konudemsxk"_mst;
+        case Fragment::PK_H: return "Knudemsxk"_mst;
+        case Fragment::OLDER: return
+            "g"_mst.If(k & CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG) |
+            "h"_mst.If(!(k & CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG)) |
+            "Bzfmxk"_mst;
+        case Fragment::AFTER: return
+            "i"_mst.If(k >= LOCKTIME_THRESHOLD) |
+            "j"_mst.If(k < LOCKTIME_THRESHOLD) |
+            "Bzfmxk"_mst;
+        case Fragment::SHA256: return "Bonudmk"_mst;
+        case Fragment::RIPEMD160: return "Bonudmk"_mst;
+        case Fragment::HASH256: return "Bonudmk"_mst;
+        case Fragment::HASH160: return "Bonudmk"_mst;
+        case Fragment::JUST_1: return "Bzufmxk"_mst;
+        case Fragment::JUST_0: return "Bzudemsxk"_mst;
+        case Fragment::WRAP_A: return
+            "W"_mst.If(x << "B"_mst) | // W=B_x
+            (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
+            (x & "udfems"_mst) | // u=u_x, d=d_x, f=f_x, e=e_x, m=m_x, s=s_x
+            "x"_mst; // x
+        case Fragment::WRAP_S: return
+            "W"_mst.If(x << "Bo"_mst) | // W=B_x*o_x
+            (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
+            (x & "udfemsx"_mst); // u=u_x, d=d_x, f=f_x, e=e_x, m=m_x, s=s_x, x=x_x
+        case Fragment::WRAP_C: return
+            "B"_mst.If(x << "K"_mst) | // B=K_x
+            (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
+            (x & "ondfem"_mst) | // o=o_x, n=n_x, d=d_x, f=f_x, e=e_x, m=m_x
+            "us"_mst; // u, s
+        case Fragment::WRAP_D: return
+            "B"_mst.If(x << "Vz"_mst) | // B=V_x*z_x
+            "o"_mst.If(x << "z"_mst) | // o=z_x
+            "e"_mst.If(x << "f"_mst) | // e=f_x
+            (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
+            (x & "ms"_mst) | // m=m_x, s=s_x
+            "nudx"_mst; // n, u, d, x
+        case Fragment::WRAP_V: return
+            "V"_mst.If(x << "B"_mst) | // V=B_x
+            (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
+            (x & "zonms"_mst) | // z=z_x, o=o_x, n=n_x, m=m_x, s=s_x
+            "fx"_mst; // f, x
+        case Fragment::WRAP_J: return
+            "B"_mst.If(x << "Bn"_mst) | // B=B_x*n_x
+            "e"_mst.If(x << "f"_mst) | // e=f_x
+            (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
+            (x & "oums"_mst) | // o=o_x, u=u_x, m=m_x, s=s_x
+            "ndx"_mst; // n, d, x
+        case Fragment::WRAP_N: return
+            (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
+            (x & "Bzondfems"_mst) | // B=B_x, z=z_x, o=o_x, n=n_x, d=d_x, f=f_x, e=e_x, m=m_x, s=s_x
+            "ux"_mst; // u, x
+        case Fragment::AND_V: return
+            (y & "KVB"_mst).If(x << "V"_mst) | // B=V_x*B_y, V=V_x*V_y, K=V_x*K_y
+            (x & "n"_mst) | (y & "n"_mst).If(x << "z"_mst) | // n=n_x+z_x*n_y
+            ((x | y) & "o"_mst).If((x | y) << "z"_mst) | // o=o_x*z_y+z_x*o_y
+            (x & y & "dmz"_mst) | // d=d_x*d_y, m=m_x*m_y, z=z_x*z_y
+            ((x | y) & "s"_mst) | // s=s_x+s_y
+            "f"_mst.If((y << "f"_mst) || (x << "s"_mst)) | // f=f_y+s_x
+            (y & "ux"_mst) | // u=u_y, x=x_y
+            ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
+            "k"_mst.If(((x & y) << "k"_mst) &&
+                !(((x << "g"_mst) && (y << "h"_mst)) ||
+                ((x << "h"_mst) && (y << "g"_mst)) ||
+                ((x << "i"_mst) && (y << "j"_mst)) ||
+                ((x << "j"_mst) && (y << "i"_mst)))); // k=k_x*k_y*!(g_x*h_y + h_x*g_y + i_x*j_y + j_x*i_y)
+        case Fragment::AND_B: return
+            (x & "B"_mst).If(y << "W"_mst) | // B=B_x*W_y
+            ((x | y) & "o"_mst).If((x | y) << "z"_mst) | // o=o_x*z_y+z_x*o_y
+            (x & "n"_mst) | (y & "n"_mst).If(x << "z"_mst) | // n=n_x+z_x*n_y
+            (x & y & "e"_mst).If((x & y) << "s"_mst) | // e=e_x*e_y*s_x*s_y
+            (x & y & "dzm"_mst) | // d=d_x*d_y, z=z_x*z_y, m=m_x*m_y
+            "f"_mst.If(((x & y) << "f"_mst) || (x << "sf"_mst) || (y << "sf"_mst)) | // f=f_x*f_y + f_x*s_x + f_y*s_y
+            ((x | y) & "s"_mst) | // s=s_x+s_y
+            "ux"_mst | // u, x
+            ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
+            "k"_mst.If(((x & y) << "k"_mst) &&
+                !(((x << "g"_mst) && (y << "h"_mst)) ||
+                ((x << "h"_mst) && (y << "g"_mst)) ||
+                ((x << "i"_mst) && (y << "j"_mst)) ||
+                ((x << "j"_mst) && (y << "i"_mst)))); // k=k_x*k_y*!(g_x*h_y + h_x*g_y + i_x*j_y + j_x*i_y)
+        case Fragment::OR_B: return
+            "B"_mst.If(x << "Bd"_mst && y << "Wd"_mst) | // B=B_x*d_x*W_x*d_y
+            ((x | y) & "o"_mst).If((x | y) << "z"_mst) | // o=o_x*z_y+z_x*o_y
+            (x & y & "m"_mst).If((x | y) << "s"_mst && (x & y) << "e"_mst) | // m=m_x*m_y*e_x*e_y*(s_x+s_y)
+            (x & y & "zse"_mst) | // z=z_x*z_y, s=s_x*s_y, e=e_x*e_y
+            "dux"_mst | // d, u, x
+            ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
+            (x & y & "k"_mst); // k=k_x*k_y
+        case Fragment::OR_D: return
+            (y & "B"_mst).If(x << "Bdu"_mst) | // B=B_y*B_x*d_x*u_x
+            (x & "o"_mst).If(y << "z"_mst) | // o=o_x*z_y
+            (x & y & "m"_mst).If(x << "e"_mst && (x | y) << "s"_mst) | // m=m_x*m_y*e_x*(s_x+s_y)
+            (x & y & "zes"_mst) | // z=z_x*z_y, e=e_x*e_y, s=s_x*s_y
+            (y & "ufd"_mst) | // u=u_y, f=f_y, d=d_y
+            "x"_mst | // x
+            ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
+            (x & y & "k"_mst); // k=k_x*k_y
+        case Fragment::OR_C: return
+            (y & "V"_mst).If(x << "Bdu"_mst) | // V=V_y*B_x*u_x*d_x
+            (x & "o"_mst).If(y << "z"_mst) | // o=o_x*z_y
+            (x & y & "m"_mst).If(x << "e"_mst && (x | y) << "s"_mst) | // m=m_x*m_y*e_x*(s_x+s_y)
+            (x & y & "zs"_mst) | // z=z_x*z_y, s=s_x*s_y
+            "fx"_mst | // f, x
+            ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
+            (x & y & "k"_mst); // k=k_x*k_y
+        case Fragment::OR_I: return
+            (x & y & "VBKufs"_mst) | // V=V_x*V_y, B=B_x*B_y, K=K_x*K_y, u=u_x*u_y, f=f_x*f_y, s=s_x*s_y
+            "o"_mst.If((x & y) << "z"_mst) | // o=z_x*z_y
+            ((x | y) & "e"_mst).If((x | y) << "f"_mst) | // e=e_x*f_y+f_x*e_y
+            (x & y & "m"_mst).If((x | y) << "s"_mst) | // m=m_x*m_y*(s_x+s_y)
+            ((x | y) & "d"_mst) | // d=d_x+d_y
+            "x"_mst | // x
+            ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
+            (x & y & "k"_mst); // k=k_x*k_y
+        case Fragment::ANDOR: return
+            (y & z & "BKV"_mst).If(x << "Bdu"_mst) | // B=B_x*d_x*u_x*B_y*B_z, K=B_x*d_x*u_x*K_y*K_z, V=B_x*d_x*u_x*V_y*V_z
+            (x & y & z & "z"_mst) | // z=z_x*z_y*z_z
+            ((x | (y & z)) & "o"_mst).If((x | (y & z)) << "z"_mst) | // o=o_x*z_y*z_z+z_x*o_y*o_z
+            (y & z & "u"_mst) | // u=u_y*u_z
+            (z & "f"_mst).If((x << "s"_mst) || (y << "f"_mst)) | // f=(s_x+f_y)*f_z
+            (z & "d"_mst) | // d=d_z
+            (x & z & "e"_mst).If(x << "s"_mst || y << "f"_mst) | // e=e_x*e_z*(s_x+f_y)
+            (x & y & z & "m"_mst).If(x << "e"_mst && (x | y | z) << "s"_mst) | // m=m_x*m_y*m_z*e_x*(s_x+s_y+s_z)
+            (z & (x | y) & "s"_mst) | // s=s_z*(s_x+s_y)
+            "x"_mst | // x
+            ((x | y | z) & "ghij"_mst) | // g=g_x+g_y+g_z, h=h_x+h_y+h_z, i=i_x+i_y+i_z, j=j_x+j_y_j_z
+            "k"_mst.If(((x & y & z) << "k"_mst) &&
+                !(((x << "g"_mst) && (y << "h"_mst)) ||
+                ((x << "h"_mst) && (y << "g"_mst)) ||
+                ((x << "i"_mst) && (y << "j"_mst)) ||
+                ((x << "j"_mst) && (y << "i"_mst)))); // k=k_x*k_y*k_z* !(g_x*h_y + h_x*g_y + i_x*j_y + j_x*i_y)
+        case Fragment::MULTI: return "Bnudemsk"_mst;
+        case Fragment::THRESH: {
+            bool all_e = true;
+            bool all_m = true;
+            uint32_t args = 0;
+            uint32_t num_s = 0;
+            Type acc_tl = "k"_mst;
+            for (size_t i = 0; i < sub_types.size(); ++i) {
+                Type t = sub_types[i];
+                if (!(t << (i ? "Wdu"_mst : "Bdu"_mst))) return ""_mst; // Require Bdu, Wdu, Wdu, ...
+                if (!(t << "e"_mst)) all_e = false;
+                if (!(t << "m"_mst)) all_m = false;
+                if (t << "s"_mst) num_s += 1;
+                args += (t << "z"_mst) ? 0 : (t << "o"_mst) ? 1 : 2;
+                acc_tl = ((acc_tl | t) & "ghij"_mst) |
+                    // Thresh contains a combination of timelocks if it has threshold > 1 and
+                    // it contains two different children that have different types of timelocks
+                    // Note how if any of the children don't have "k", the parent also does not have "k"
+                    "k"_mst.If(((acc_tl & t) << "k"_mst) && ((k <= 1) ||
+                        ((k > 1) && !(((acc_tl << "g"_mst) && (t << "h"_mst)) ||
+                        ((acc_tl << "h"_mst) && (t << "g"_mst)) ||
+                        ((acc_tl << "i"_mst) && (t << "j"_mst)) ||
+                        ((acc_tl << "j"_mst) && (t << "i"_mst))))));
+            }
+            return "Bdu"_mst |
+                   "z"_mst.If(args == 0) | // z=all z
+                   "o"_mst.If(args == 1) | // o=all z except one o
+                   "e"_mst.If(all_e && num_s == n_subs) | // e=all e and all s
+                   "m"_mst.If(all_e && all_m && num_s >= n_subs - k) | // m=all e, >=(n-k) s
+                   "s"_mst.If(num_s >= n_subs - k + 1) |  // s= >=(n-k+1) s
+                   acc_tl; // timelock info
+            }
+    }
+    assert(false);
+    return ""_mst;
+}
+
+size_t ComputeScriptLen(Fragment nodetype, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs, size_t n_keys) {
+    switch (nodetype) {
+        case Fragment::JUST_1:
+        case Fragment::JUST_0: return 1;
+        case Fragment::PK_K: return 34;
+        case Fragment::PK_H: return 3 + 21;
+        case Fragment::OLDER:
+        case Fragment::AFTER: return 1 + BuildScript(k).size();
+        case Fragment::HASH256:
+        case Fragment::SHA256: return 4 + 2 + 33;
+        case Fragment::HASH160:
+        case Fragment::RIPEMD160: return 4 + 2 + 21;
+        case Fragment::MULTI: return 3 + (n_keys > 16) + (k > 16) + 34 * n_keys;
+        case Fragment::AND_V: return subsize;
+        case Fragment::WRAP_V: return subsize + (sub0typ << "x"_mst);
+        case Fragment::WRAP_S:
+        case Fragment::WRAP_C:
+        case Fragment::WRAP_N:
+        case Fragment::AND_B:
+        case Fragment::OR_B: return subsize + 1;
+        case Fragment::WRAP_A:
+        case Fragment::OR_C: return subsize + 2;
+        case Fragment::WRAP_D:
+        case Fragment::OR_D:
+        case Fragment::OR_I:
+        case Fragment::ANDOR: return subsize + 3;
+        case Fragment::WRAP_J: return subsize + 4;
+        case Fragment::THRESH: return subsize + n_subs + BuildScript(k).size();
+    }
+    assert(false);
+    return 0;
+}
+
+bool DecomposeScript(const CScript& script, std::vector<std::pair<opcodetype, std::vector<unsigned char>>>& out)
+{
+    out.clear();
+    CScript::const_iterator it = script.begin(), itend = script.end();
+    while (it != itend) {
+        std::vector<unsigned char> push_data;
+        opcodetype opcode;
+        if (!script.GetOp(it, opcode, push_data)) {
+            out.clear();
+            return false;
+        } else if (opcode >= OP_1 && opcode <= OP_16) {
+            // Deal with OP_n (GetOp does not turn them into pushes).
+            push_data.assign(1, CScript::DecodeOP_N(opcode));
+        } else if (opcode == OP_CHECKSIGVERIFY) {
+            // Decompose OP_CHECKSIGVERIFY into OP_CHECKSIG OP_VERIFY
+            out.emplace_back(OP_CHECKSIG, std::vector<unsigned char>());
+            opcode = OP_VERIFY;
+        } else if (opcode == OP_CHECKMULTISIGVERIFY) {
+            // Decompose OP_CHECKMULTISIGVERIFY into OP_CHECKMULTISIG OP_VERIFY
+            out.emplace_back(OP_CHECKMULTISIG, std::vector<unsigned char>());
+            opcode = OP_VERIFY;
+        } else if (opcode == OP_EQUALVERIFY) {
+            // Decompose OP_EQUALVERIFY into OP_EQUAL OP_VERIFY
+            out.emplace_back(OP_EQUAL, std::vector<unsigned char>());
+            opcode = OP_VERIFY;
+        } else if (IsPushdataOp(opcode)) {
+            if (!CheckMinimalPush(push_data, opcode)) return false;
+        } else if (it != itend && (opcode == OP_CHECKSIG || opcode == OP_CHECKMULTISIG || opcode == OP_EQUAL) && (*it == OP_VERIFY)) {
+            // Rule out non minimal VERIFY sequences
+            return false;
+        }
+        out.emplace_back(opcode, std::move(push_data));
+    }
+    std::reverse(out.begin(), out.end());
+    return true;
+}
+
+bool ParseScriptNumber(const std::pair<opcodetype, std::vector<unsigned char>>& in, int64_t& k) {
+    if (in.first == OP_0) {
+        k = 0;
+        return true;
+    }
+    if (!in.second.empty()) {
+        if (IsPushdataOp(in.first) && !CheckMinimalPush(in.second, in.first)) return false;
+        try {
+            k = CScriptNum(in.second, true).GetInt64();
+            return true;
+        } catch(const scriptnum_error&) {}
+    }
+    return false;
+}
+
+int FindNextChar(Span<const char> sp, const char m)
+{
+    for (int i = 0; i < (int)sp.size(); ++i) {
+        if (sp[i] == m) return i;
+        // We only search within the current parentheses
+        if (sp[i] == ')') break;
+    }
+    return -1;
+}
+
+} // namespace internal
+} // namespace miniscript
diff --git a/src/script/miniscript.h b/src/script/miniscript.h
new file mode 100644
index 0000000000..b54653c548
--- /dev/null
+++ b/src/script/miniscript.h
@@ -0,0 +1,1652 @@
+// Copyright (c) 2019 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#ifndef BITCOIN_SCRIPT_MINISCRIPT_H
+#define BITCOIN_SCRIPT_MINISCRIPT_H
+
+#include <algorithm>
+#include <numeric>
+#include <memory>
+#include <optional>
+#include <string>
+#include <vector>
+
+#include <stdlib.h>
+#include <assert.h>
+
+#include <policy/policy.h>
+#include <primitives/transaction.h>
+#include <script/script.h>
+#include <span.h>
+#include <util/spanparsing.h>
+#include <util/strencodings.h>
+#include <util/string.h>
+#include <util/vector.h>
+
+namespace miniscript {
+
+/** This type encapsulates the miniscript type system properties.
+ *
+ * Every miniscript expression is one of 4 basic types, and additionally has
+ * a number of boolean type properties.
+ *
+ * The basic types are:
+ * - "B" Base:
+ *   - Takes its inputs from the top of the stack.
+ *   - When satisfied, pushes a nonzero value of up to 4 bytes onto the stack.
+ *   - When dissatisfied, pushes a 0 onto the stack.
+ *   - This is used for most expressions, and required for the top level one.
+ *   - For example: older(n) = <n> OP_CHECKSEQUENCEVERIFY.
+ * - "V" Verify:
+ *   - Takes its inputs from the top of the stack.
+ *   - When satisfactied, pushes nothing.
+ *   - Cannot be dissatisfied.
+ *   - This can be obtained by adding an OP_VERIFY to a B, modifying the last opcode
+ *     of a B to its -VERIFY version (only for OP_CHECKSIG, OP_CHECKSIGVERIFY
+ *     and OP_EQUAL), or by combining a V fragment under some conditions.
+ *   - For example vc:pk_k(key) = <key> OP_CHECKSIGVERIFY
+ * - "K" Key:
+ *   - Takes its inputs from the top of the stack.
+ *   - Becomes a B when followed by OP_CHECKSIG.
+ *   - Always pushes a public key onto the stack, for which a signature is to be
+ *     provided to satisfy the expression.
+ *   - For example pk_h(key) = OP_DUP OP_HASH160 <Hash160(key)> OP_EQUALVERIFY
+ * - "W" Wrapped:
+ *   - Takes its input from one below the top of the stack.
+ *   - When satisfied, pushes a nonzero value (like B) on top of the stack, or one below.
+ *   - When dissatisfied, pushes 0 op top of the stack or one below.
+ *   - Is always "OP_SWAP [B]" or "OP_TOALTSTACK [B] OP_FROMALTSTACK".
+ *   - For example sc:pk_k(key) = OP_SWAP <key> OP_CHECKSIG
+ *
+ * There a type properties that help reasoning about correctness:
+ * - "z" Zero-arg:
+ *   - Is known to always consume exactly 0 stack elements.
+ *   - For example after(n) = <n> OP_CHECKLOCKTIMEVERIFY
+ * - "o" One-arg:
+ *   - Is known to always consume exactly 1 stack element.
+ *   - Conflicts with property 'z'
+ *   - For example sha256(hash) = OP_SIZE 32 OP_EQUALVERIFY OP_SHA256 <hash> OP_EQUAL
+ * - "n" Nonzero:
+ *   - For every way this expression can be satisfied, a satisfaction exists that never needs
+ *     a zero top stack element.
+ *   - Conflicts with property 'z' and with type 'W'.
+ * - "d" Dissatisfiable:
+ *   - There is an easy way to construct a dissatisfaction for this expression.
+ *   - Conflicts with type 'V'.
+ * - "u" Unit:
+ *   - In case of satisfaction, an exact 1 is put on the stack (rather than just nonzero).
+ *   - Conflicts with type 'V'.
+ *
+ * Additional type properties help reasoning about nonmalleability:
+ * - "e" Expression:
+ *   - This implies property 'd', but the dissatisfaction is nonmalleable.
+ *   - This generally requires 'e' for all subexpressions which are invoked for that
+ *     dissatifsaction, and property 'f' for the unexecuted subexpressions in that case.
+ *   - Conflicts with type 'V'.
+ * - "f" Forced:
+ *   - Dissatisfactions (if any) for this expression always involve at least one signature.
+ *   - Is always true for type 'V'.
+ * - "s" Safe:
+ *   - Satisfactions for this expression always involve at least one signature.
+ * - "m" Nonmalleable:
+ *   - For every way this expression can be satisfied (which may be none),
+ *     a nonmalleable satisfaction exists.
+ *   - This generally requires 'm' for all subexpressions, and 'e' for all subexpressions
+ *     which are dissatisfied when satisfying the parent.
+ *
+ * One type property is an implementation detail:
+ * - "x" Expensive verify:
+ *   - Expressions with this property have a script whose last opcode is not EQUAL, CHECKSIG, or CHECKMULTISIG.
+ *   - Not having this property means that it can be converted to a V at no cost (by switching to the
+ *     -VERIFY version of the last opcode).
+ *
+ * Five more type properties for representing timelock information. Spend paths
+ * in miniscripts containing conflicting timelocks and heightlocks cannot be spent together.
+ * This helps users detect if miniscript does not match the semantic behaviour the
+ * user expects.
+ * - "g" Whether the branch contains a relative time timelock
+ * - "h" Whether the branch contains a relative height timelock
+ * - "i" Whether the branch contains an absolute time timelock
+ * - "j" Whether the branch contains an absolute height timelock
+ * - "k"
+ *   - Whether all satisfactions of this expression don't contain a mix of heightlock and timelock
+ *     of the same type.
+ *   - If the miniscript does not have the "k" property, the miniscript template will not match
+ *     the user expectation of the corresponding spending policy.
+ * For each of these properties the subset rule holds: an expression with properties X, Y, and Z, is also
+ * valid in places where an X, a Y, a Z, an XY, ... is expected.
+*/
+class Type {
+    //! Internal bitmap of properties (see ""_mst operator for details).
+    uint32_t m_flags;
+
+    //! Internal constructor used by the ""_mst operator.
+    explicit constexpr Type(uint32_t flags) : m_flags(flags) {}
+
+public:
+    //! The only way to publicly construct a Type is using this literal operator.
+    friend constexpr Type operator"" _mst(const char* c, size_t l);
+
+    //! Compute the type with the union of properties.
+    constexpr Type operator|(Type x) const { return Type(m_flags | x.m_flags); }
+
+    //! Compute the type with the intersection of properties.
+    constexpr Type operator&(Type x) const { return Type(m_flags & x.m_flags); }
+
+    //! Check whether the left hand's properties are superset of the right's (= left is a subtype of right).
+    constexpr bool operator<<(Type x) const { return (x.m_flags & ~m_flags) == 0; }
+
+    //! Comparison operator to enable use in sets/maps (total ordering incompatible with <<).
+    constexpr bool operator<(Type x) const { return m_flags < x.m_flags; }
+
+    //! Equality operator.
+    constexpr bool operator==(Type x) const { return m_flags == x.m_flags; }
+
+    //! The empty type if x is false, itself otherwise.
+    constexpr Type If(bool x) const { return Type(x ? m_flags : 0); }
+};
+
+//! Literal operator to construct Type objects.
+inline constexpr Type operator"" _mst(const char* c, size_t l) {
+    Type typ{0};
+
+    for (const char *p = c; p < c + l; p++) {
+        typ = typ | Type(
+            *p == 'B' ? 1 << 0 : // Base type
+            *p == 'V' ? 1 << 1 : // Verify type
+            *p == 'K' ? 1 << 2 : // Key type
+            *p == 'W' ? 1 << 3 : // Wrapped type
+            *p == 'z' ? 1 << 4 : // Zero-arg property
+            *p == 'o' ? 1 << 5 : // One-arg property
+            *p == 'n' ? 1 << 6 : // Nonzero arg property
+            *p == 'd' ? 1 << 7 : // Dissatisfiable property
+            *p == 'u' ? 1 << 8 : // Unit property
+            *p == 'e' ? 1 << 9 : // Expression property
+            *p == 'f' ? 1 << 10 : // Forced property
+            *p == 's' ? 1 << 11 : // Safe property
+            *p == 'm' ? 1 << 12 : // Nonmalleable property
+            *p == 'x' ? 1 << 13 : // Expensive verify
+            *p == 'g' ? 1 << 14 : // older: contains relative time timelock   (csv_time)
+            *p == 'h' ? 1 << 15 : // older: contains relative height timelock (csv_height)
+            *p == 'i' ? 1 << 16 : // after: contains time timelock   (cltv_time)
+            *p == 'j' ? 1 << 17 : // after: contains height timelock   (cltv_height)
+            *p == 'k' ? 1 << 18 : // does not contain a combination of height and time locks
+            (throw std::logic_error("Unknown character in _mst literal"), 0)
+        );
+    }
+
+    return typ;
+}
+
+template<typename Key> struct Node;
+template<typename Key> using NodeRef = std::shared_ptr<const Node<Key>>;
+
+//! Construct a miniscript node as a shared_ptr.
+template<typename Key, typename... Args>
+NodeRef<Key> MakeNodeRef(Args&&... args) { return std::make_shared<const Node<Key>>(std::forward<Args>(args)...); }
+
+//! The different node types in miniscript.
+enum class Fragment {
+    JUST_0,    //!< OP_0
+    JUST_1,    //!< OP_1
+    PK_K,      //!< [key]
+    PK_H,      //!< OP_DUP OP_HASH160 [keyhash] OP_EQUALVERIFY
+    OLDER,     //!< [n] OP_CHECKSEQUENCEVERIFY
+    AFTER,     //!< [n] OP_CHECKLOCKTIMEVERIFY
+    SHA256,    //!< OP_SIZE 32 OP_EQUALVERIFY OP_SHA256 [hash] OP_EQUAL
+    HASH256,   //!< OP_SIZE 32 OP_EQUALVERIFY OP_HASH256 [hash] OP_EQUAL
+    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_S,    //!< OP_SWAP [X]
+    WRAP_C,    //!< [X] OP_CHECKSIG
+    WRAP_D,    //!< OP_DUP OP_IF [X] OP_ENDIF
+    WRAP_V,    //!< [X] OP_VERIFY (or -VERIFY version of last opcode in X)
+    WRAP_J,    //!< OP_SIZE OP_0NOTEQUAL OP_IF [X] OP_ENDIF
+    WRAP_N,    //!< [X] OP_0NOTEQUAL
+    AND_V,     //!< [X] [Y]
+    AND_B,     //!< [X] [Y] OP_BOOLAND
+    OR_B,      //!< [X] [Y] OP_BOOLOR
+    OR_C,      //!< [X] OP_NOTIF [Y] OP_ENDIF
+    OR_D,      //!< [X] OP_IFDUP OP_NOTIF [Y] OP_ENDIF
+    OR_I,      //!< OP_IF [X] OP_ELSE [Y] OP_ENDIF
+    ANDOR,     //!< [X] OP_NOTIF [Z] OP_ELSE [Y] OP_ENDIF
+    THRESH,    //!< [X1] ([Xn] OP_ADD)* [k] OP_EQUAL
+    MULTI,     //!< [k] [key_n]* [n] OP_CHECKMULTISIG
+    // AND_N(X,Y) is represented as ANDOR(X,Y,0)
+    // WRAP_T(X) is represented as AND_V(X,1)
+    // WRAP_L(X) is represented as OR_I(0,X)
+    // WRAP_U(X) is represented as OR_I(X,0)
+};
+
+
+namespace internal {
+
+//! Helper function for Node::CalcType.
+Type ComputeType(Fragment nodetype, 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::CalcScriptLen.
+size_t ComputeScriptLen(Fragment nodetype, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs, size_t n_keys);
+
+//! A helper sanitizer/checker for the output of CalcType.
+Type SanitizeType(Type x);
+
+//! Class whose objects represent the maximum of a list of integers.
+template<typename I>
+struct MaxInt {
+    const bool valid;
+    const I value;
+
+    MaxInt() : valid(false), value(0) {}
+    MaxInt(I val) : valid(true), value(val) {}
+
+    friend MaxInt<I> operator+(const MaxInt<I>& a, const MaxInt<I>& b) {
+        if (!a.valid || !b.valid) return {};
+        return a.value + b.value;
+    }
+
+    friend MaxInt<I> operator|(const MaxInt<I>& a, const MaxInt<I>& b) {
+        if (!a.valid) return b;
+        if (!b.valid) return a;
+        return std::max(a.value, b.value);
+    }
+};
+
+struct Ops {
+    //! Non-push opcodes.
+    uint32_t count;
+    //! Number of keys in possibly executed OP_CHECKMULTISIG(VERIFY)s to satisfy.
+    MaxInt<uint32_t> sat;
+    //! Number of keys in possibly executed OP_CHECKMULTISIG(VERIFY)s to dissatisfy.
+    MaxInt<uint32_t> dsat;
+
+    Ops(uint32_t in_count, MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : count(in_count), sat(in_sat), dsat(in_dsat) {};
+};
+
+struct StackSize {
+    //! Maximum stack size to satisfy;
+    MaxInt<uint32_t> sat;
+    //! Maximum stack size to dissatisfy;
+    MaxInt<uint32_t> dsat;
+
+    StackSize(MaxInt<uint32_t> in_sat, MaxInt<uint32_t> in_dsat) : sat(in_sat), dsat(in_dsat) {};
+};
+
+} // namespace internal
+
+//! A node in a miniscript expression.
+template<typename Key>
+struct Node {
+    //! What node type this node is.
+    const Fragment nodetype;
+    //! The k parameter (time for OLDER/AFTER, threshold for THRESH(_M))
+    const uint32_t k = 0;
+    //! The keys used by this expression (only for PK_K/PK_H/MULTI)
+    const std::vector<Key> keys;
+    //! The data bytes in this expression (only for HASH160/HASH256/SHA256/RIPEMD10).
+    const std::vector<unsigned char> data;
+    //! Subexpressions (for WRAP_*/AND_*/OR_*/ANDOR/THRESH)
+    const std::vector<NodeRef<Key>> subs;
+
+private:
+    //! Cached ops counts.
+    const internal::Ops ops;
+    //! Cached stack size bounds.
+    const internal::StackSize ss;
+    //! Cached expression type (computed by CalcType and fed through SanitizeType).
+    const Type typ;
+    //! Cached script length (computed by CalcScriptLen).
+    const size_t scriptlen;
+
+    //! Compute the length of the script for this miniscript (including children).
+    size_t CalcScriptLen() const {
+        size_t subsize = 0;
+        for (const auto& sub : subs) {
+            subsize += sub->ScriptSize();
+        }
+        Type sub0type = subs.size() > 0 ? subs[0]->GetType() : ""_mst;
+        return internal::ComputeScriptLen(nodetype, sub0type, subsize, k, subs.size(), keys.size());
+    }
+
+    /* Apply a recursive algorithm to a Miniscript tree, without actual recursive calls.
+     *
+     * The algorithm is defined by two functions: downfn and upfn. Conceptually, the
+     * result can be thought of as first using downfn to compute a "state" for each node,
+     * from the root down to the leaves. Then upfn is used to compute a "result" for each
+     * node, from the leaves back up to the root, which is then returned. In the actual
+     * implementation, both functions are invoked in an interleaved fashion, performing a
+     * depth-first traversal of the tree.
+     *
+     * In more detail, it is invoked as node.TreeEvalMaybe<Result>(root, downfn, upfn):
+     * - root is the state of the root node, of type State.
+     * - downfn is a callable (State&, const Node&, size_t) -> State, which given a
+     *   node, its state, and an index of one of its children, computes the state of that
+     *   child. It can modify the state. Children of a given node will have downfn()
+     *   called in order.
+     * - upfn is a callable (State&&, const Node&, Span<Result>) -> std::optional<Result>,
+     *   which given a node, its state, and a Span of the results of its children,
+     *   computes the result of the node. If std::nullopt is returned by upfn,
+     *   TreeEvalMaybe() immediately returns std::nullopt.
+     * The return value of TreeEvalMaybe is the result of the root node.
+     */
+    template<typename Result, typename State, typename DownFn, typename UpFn>
+    std::optional<Result> TreeEvalMaybe(State root_state, DownFn downfn, UpFn upfn) const
+    {
+        /** Entries of the explicit stack tracked in this algorithm. */
+        struct StackElem
+        {
+            const Node& node; //!< The node being evaluated.
+            size_t expanded; //!< How many children of this node have been expanded.
+            State state; //!< The state for that node.
+
+            StackElem(const Node& node_, size_t exp_, State&& state_) :
+                node(node_), expanded(exp_), state(std::move(state_)) {}
+        };
+        /* Stack of tree nodes being explored. */
+        std::vector<StackElem> stack;
+        /* Results of subtrees so far. Their order and mapping to tree nodes
+         * is implicitly defined by stack. */
+        std::vector<Result> results;
+        stack.emplace_back(*this, 0, std::move(root_state));
+
+        /* Here is a demonstration of the algorithm, for an example tree A(B,C(D,E),F).
+         * State variables are omitted for simplicity.
+         *
+         * First: stack=[(A,0)] results=[]
+         *        stack=[(A,1),(B,0)] results=[]
+         *        stack=[(A,1)] results=[B]
+         *        stack=[(A,2),(C,0)] results=[B]
+         *        stack=[(A,2),(C,1),(D,0)] results=[B]
+         *        stack=[(A,2),(C,1)] results=[B,D]
+         *        stack=[(A,2),(C,2),(E,0)] results=[B,D]
+         *        stack=[(A,2),(C,2)] results=[B,D,E]
+         *        stack=[(A,2)] results=[B,C]
+         *        stack=[(A,3),(F,0)] results=[B,C]
+         *        stack=[(A,3)] results=[B,C,F]
+         * Final: stack=[] results=[A]
+         */
+        while (stack.size()) {
+            const Node& node = stack.back().node;
+            if (stack.back().expanded < node.subs.size()) {
+                /* We encounter a tree node with at least one unexpanded child.
+                 * Expand it. By the time we hit this node again, the result of
+                 * that child (and all earlier children) will be at the end of `results`. */
+                size_t child_index = stack.back().expanded++;
+                State child_state = downfn(stack.back().state, node, child_index);
+                stack.emplace_back(*node.subs[child_index], 0, std::move(child_state));
+                continue;
+            }
+            // Invoke upfn with the last node.subs.size() elements of results as input.
+            assert(results.size() >= node.subs.size());
+            std::optional<Result> result{upfn(std::move(stack.back().state), node,
+                Span<Result>{results}.last(node.subs.size()))};
+            // If evaluation returns std::nullopt, abort immediately.
+            if (!result) return {};
+            // Replace the last node.subs.size() elements of results with the new result.
+            results.erase(results.end() - node.subs.size(), results.end());
+            results.push_back(std::move(*result));
+            stack.pop_back();
+        }
+        // The final remaining results element is the root result, return it.
+        assert(results.size() == 1);
+        return std::move(results[0]);
+    }
+
+    /** Like TreeEvalMaybe, but always produces a result. upfn must return Result. */
+    template<typename Result, typename State, typename DownFn, typename UpFn>
+    Result TreeEval(State root_state, DownFn&& downfn, UpFn upfn) const
+    {
+        // Invoke TreeEvalMaybe with upfn wrapped to return std::optional<Result>, and then
+        // unconditionally dereference the result (it cannot be std::nullopt).
+        return std::move(*TreeEvalMaybe<Result>(std::move(root_state),
+            std::forward<DownFn>(downfn),
+            [&upfn](State&& state, const Node& node, Span<Result> subs) {
+                Result res{upfn(std::move(state), node, subs)};
+                return std::optional<Result>(std::move(res));
+            }
+        ));
+    }
+
+    //! Compute the type for this miniscript.
+    Type CalcType() const {
+        using namespace internal;
+
+        // THRESH has a variable number of subexpressions
+        std::vector<Type> sub_types;
+        if (nodetype == Fragment::THRESH) {
+            for (const auto& sub : subs) sub_types.push_back(sub->GetType());
+        }
+        // All other nodes than THRESH can be computed just from the types of the 0-3 subexpressions.
+        Type x = subs.size() > 0 ? subs[0]->GetType() : ""_mst;
+        Type y = subs.size() > 1 ? subs[1]->GetType() : ""_mst;
+        Type z = subs.size() > 2 ? subs[2]->GetType() : ""_mst;
+
+        return SanitizeType(ComputeType(nodetype, x, y, z, sub_types, k, data.size(), subs.size(), keys.size()));
+    }
+
+public:
+    template<typename Ctx>
+    CScript ToScript(const Ctx& ctx) const
+    {
+        // To construct the CScript for a Miniscript object, we use the TreeEval algorithm.
+        // The State is a boolean: whether or not the node's script expansion is followed
+        // by an OP_VERIFY (which may need to be combined with the last script opcode).
+        auto downfn = [](bool verify, const Node& node, size_t index) {
+            // For WRAP_V, the subexpression is certainly followed by OP_VERIFY.
+            if (node.nodetype == Fragment::WRAP_V) return true;
+            // The subexpression of WRAP_S, and the last subexpression of AND_V
+            // inherit the followed-by-OP_VERIFY property from the parent.
+            if (node.nodetype == Fragment::WRAP_S ||
+                (node.nodetype == Fragment::AND_V && index == 1)) return verify;
+            return false;
+        };
+        // The upward function computes for a node, given its followed-by-OP_VERIFY status
+        // and the CScripts of its child nodes, the CScript of the node.
+        auto upfn = [&ctx](bool verify, const Node& node, Span<CScript> subs) -> CScript {
+            switch (node.nodetype) {
+                case Fragment::PK_K: return BuildScript(ctx.ToPKBytes(node.keys[0]));
+                case Fragment::PK_H: return BuildScript(OP_DUP, OP_HASH160, ctx.ToPKHBytes(node.keys[0]), OP_EQUALVERIFY);
+                case Fragment::OLDER: return BuildScript(node.k, OP_CHECKSEQUENCEVERIFY);
+                case Fragment::AFTER: return BuildScript(node.k, OP_CHECKLOCKTIMEVERIFY);
+                case Fragment::SHA256: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_SHA256, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL);
+                case Fragment::RIPEMD160: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_RIPEMD160, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL);
+                case Fragment::HASH256: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_HASH256, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL);
+                case Fragment::HASH160: return BuildScript(OP_SIZE, 32, OP_EQUALVERIFY, OP_HASH160, node.data, verify ? OP_EQUALVERIFY : OP_EQUAL);
+                case Fragment::WRAP_A: return BuildScript(OP_TOALTSTACK, subs[0], OP_FROMALTSTACK);
+                case Fragment::WRAP_S: return BuildScript(OP_SWAP, subs[0]);
+                case Fragment::WRAP_C: return BuildScript(std::move(subs[0]), verify ? OP_CHECKSIGVERIFY : OP_CHECKSIG);
+                case Fragment::WRAP_D: return BuildScript(OP_DUP, OP_IF, subs[0], OP_ENDIF);
+                case Fragment::WRAP_V: {
+                    if (node.subs[0]->GetType() << "x"_mst) {
+                        return BuildScript(std::move(subs[0]), OP_VERIFY);
+                    } else {
+                        return std::move(subs[0]);
+                    }
+                }
+                case Fragment::WRAP_J: return BuildScript(OP_SIZE, OP_0NOTEQUAL, OP_IF, subs[0], OP_ENDIF);
+                case Fragment::WRAP_N: return BuildScript(std::move(subs[0]), OP_0NOTEQUAL);
+                case Fragment::JUST_1: return BuildScript(OP_1);
+                case Fragment::JUST_0: return BuildScript(OP_0);
+                case Fragment::AND_V: return BuildScript(std::move(subs[0]), subs[1]);
+                case Fragment::AND_B: return BuildScript(std::move(subs[0]), subs[1], OP_BOOLAND);
+                case Fragment::OR_B: return BuildScript(std::move(subs[0]), subs[1], OP_BOOLOR);
+                case Fragment::OR_D: return BuildScript(std::move(subs[0]), OP_IFDUP, OP_NOTIF, subs[1], OP_ENDIF);
+                case Fragment::OR_C: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[1], OP_ENDIF);
+                case Fragment::OR_I: return BuildScript(OP_IF, subs[0], OP_ELSE, subs[1], OP_ENDIF);
+                case Fragment::ANDOR: return BuildScript(std::move(subs[0]), OP_NOTIF, subs[2], OP_ELSE, subs[1], OP_ENDIF);
+                case Fragment::MULTI: {
+                    CScript script = BuildScript(node.k);
+                    for (const auto& key : node.keys) {
+                        script = BuildScript(std::move(script), ctx.ToPKBytes(key));
+                    }
+                    return BuildScript(std::move(script), node.keys.size(), verify ? OP_CHECKMULTISIGVERIFY : OP_CHECKMULTISIG);
+                }
+                case Fragment::THRESH: {
+                    CScript script = std::move(subs[0]);
+                    for (size_t i = 1; i < subs.size(); ++i) {
+                        script = BuildScript(std::move(script), subs[i], OP_ADD);
+                    }
+                    return BuildScript(std::move(script), node.k, verify ? OP_EQUALVERIFY : OP_EQUAL);
+                }
+            }
+            assert(false);
+            return {};
+        };
+        return TreeEval<CScript>(false, downfn, upfn);
+    }
+
+    template<typename CTx>
+    bool ToString(const CTx& ctx, std::string& ret) const {
+        // To construct the std::string representation for a Miniscript object, we use
+        // the TreeEvalMaybe algorithm. The State is a boolean: whether the parent node is a
+        // wrapper. If so, non-wrapper expressions must be prefixed with a ":".
+        auto downfn = [](bool, const Node& node, size_t) {
+            return (node.nodetype == Fragment::WRAP_A || node.nodetype == Fragment::WRAP_S ||
+                    node.nodetype == Fragment::WRAP_D || node.nodetype == Fragment::WRAP_V ||
+                    node.nodetype == Fragment::WRAP_J || node.nodetype == Fragment::WRAP_N ||
+                    node.nodetype == Fragment::WRAP_C ||
+                    (node.nodetype == Fragment::AND_V && node.subs[1]->nodetype == Fragment::JUST_1) ||
+                    (node.nodetype == Fragment::OR_I && node.subs[0]->nodetype == Fragment::JUST_0) ||
+                    (node.nodetype == Fragment::OR_I && node.subs[1]->nodetype == Fragment::JUST_0));
+        };
+        // The upward function computes for a node, given whether its parent is a wrapper,
+        // and the string representations of its child nodes, the string representation of the node.
+        auto upfn = [&ctx](bool wrapped, const Node& node, Span<std::string> subs) -> std::optional<std::string> {
+            std::string ret = wrapped ? ":" : "";
+
+            switch (node.nodetype) {
+                case Fragment::WRAP_A: return "a" + std::move(subs[0]);
+                case Fragment::WRAP_S: return "s" + std::move(subs[0]);
+                case Fragment::WRAP_C:
+                    if (node.subs[0]->nodetype == Fragment::PK_K) {
+                        // pk(K) is syntactic sugar for c:pk_k(K)
+                        std::string key_str;
+                        if (!ctx.ToString(node.subs[0]->keys[0], key_str)) return {};
+                        return std::move(ret) + "pk(" + std::move(key_str) + ")";
+                    }
+                    if (node.subs[0]->nodetype == Fragment::PK_H) {
+                        // pkh(K) is syntactic sugar for c:pk_h(K)
+                        std::string key_str;
+                        if (!ctx.ToString(node.subs[0]->keys[0], key_str)) return {};
+                        return std::move(ret) + "pkh(" + std::move(key_str) + ")";
+                    }
+                    return "c" + std::move(subs[0]);
+                case Fragment::WRAP_D: return "d" + std::move(subs[0]);
+                case Fragment::WRAP_V: return "v" + std::move(subs[0]);
+                case Fragment::WRAP_J: return "j" + std::move(subs[0]);
+                case Fragment::WRAP_N: return "n" + std::move(subs[0]);
+                case Fragment::AND_V:
+                    // t:X is syntactic sugar for and_v(X,1).
+                    if (node.subs[1]->nodetype == Fragment::JUST_1) return "t" + std::move(subs[0]);
+                    break;
+                case Fragment::OR_I:
+                    if (node.subs[0]->nodetype == Fragment::JUST_0) return "l" + std::move(subs[1]);
+                    if (node.subs[1]->nodetype == Fragment::JUST_0) return "u" + std::move(subs[0]);
+                    break;
+                default: break;
+            }
+            switch (node.nodetype) {
+                case Fragment::PK_K: {
+                    std::string key_str;
+                    if (!ctx.ToString(node.keys[0], key_str)) return {};
+                    return std::move(ret) + "pk_k(" + std::move(key_str) + ")";
+                }
+                case Fragment::PK_H: {
+                    std::string key_str;
+                    if (!ctx.ToString(node.keys[0], key_str)) return {};
+                    return std::move(ret) + "pk_h(" + std::move(key_str) + ")";
+                }
+                case Fragment::AFTER: return std::move(ret) + "after(" + ::ToString(node.k) + ")";
+                case Fragment::OLDER: return std::move(ret) + "older(" + ::ToString(node.k) + ")";
+                case Fragment::HASH256: return std::move(ret) + "hash256(" + HexStr(node.data) + ")";
+                case Fragment::HASH160: return std::move(ret) + "hash160(" + HexStr(node.data) + ")";
+                case Fragment::SHA256: return std::move(ret) + "sha256(" + HexStr(node.data) + ")";
+                case Fragment::RIPEMD160: return std::move(ret) + "ripemd160(" + HexStr(node.data) + ")";
+                case Fragment::JUST_1: return std::move(ret) + "1";
+                case Fragment::JUST_0: return std::move(ret) + "0";
+                case Fragment::AND_V: return std::move(ret) + "and_v(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
+                case Fragment::AND_B: return std::move(ret) + "and_b(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
+                case Fragment::OR_B: return std::move(ret) + "or_b(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
+                case Fragment::OR_D: return std::move(ret) + "or_d(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
+                case Fragment::OR_C: return std::move(ret) + "or_c(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
+                case Fragment::OR_I: return std::move(ret) + "or_i(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
+                case Fragment::ANDOR:
+                    // and_n(X,Y) is syntactic sugar for andor(X,Y,0).
+                    if (node.subs[2]->nodetype == Fragment::JUST_0) return std::move(ret) + "and_n(" + std::move(subs[0]) + "," + std::move(subs[1]) + ")";
+                    return std::move(ret) + "andor(" + std::move(subs[0]) + "," + std::move(subs[1]) + "," + std::move(subs[2]) + ")";
+                case Fragment::MULTI: {
+                    auto str = std::move(ret) + "multi(" + ::ToString(node.k);
+                    for (const auto& key : node.keys) {
+                        std::string key_str;
+                        if (!ctx.ToString(key, key_str)) return {};
+                        str += "," + std::move(key_str);
+                    }
+                    return std::move(str) + ")";
+                }
+                case Fragment::THRESH: {
+                    auto str = std::move(ret) + "thresh(" + ::ToString(node.k);
+                    for (auto& sub : subs) {
+                        str += "," + std::move(sub);
+                    }
+                    return std::move(str) + ")";
+                }
+                default: assert(false);
+            }
+            return ""; // Should never be reached.
+        };
+
+        auto res = TreeEvalMaybe<std::string>(false, downfn, upfn);
+        if (res.has_value()) ret = std::move(*res);
+        return res.has_value();
+    }
+
+    internal::Ops CalcOps() const {
+        switch (nodetype) {
+            case Fragment::JUST_1: return {0, 0, {}};
+            case Fragment::JUST_0: return {0, {}, 0};
+            case Fragment::PK_K: return {0, 0, 0};
+            case Fragment::PK_H: return {3, 0, 0};
+            case Fragment::OLDER:
+            case Fragment::AFTER: return {1, 0, {}};
+            case Fragment::SHA256:
+            case Fragment::RIPEMD160:
+            case Fragment::HASH256:
+            case Fragment::HASH160: return {4, 0, {}};
+            case Fragment::AND_V: return {subs[0]->ops.count + subs[1]->ops.count, subs[0]->ops.sat + subs[1]->ops.sat, {}};
+            case Fragment::AND_B: {
+                const auto count{1 + subs[0]->ops.count + subs[1]->ops.count};
+                const auto sat{subs[0]->ops.sat + subs[1]->ops.sat};
+                const auto dsat{subs[0]->ops.dsat + subs[1]->ops.dsat};
+                return {count, sat, dsat};
+            }
+            case Fragment::OR_B: {
+                const auto count{1 + subs[0]->ops.count + subs[1]->ops.count};
+                const auto sat{(subs[0]->ops.sat + subs[1]->ops.dsat) | (subs[1]->ops.sat + subs[0]->ops.dsat)};
+                const auto dsat{subs[0]->ops.dsat + subs[1]->ops.dsat};
+                return {count, sat, dsat};
+            }
+            case Fragment::OR_D: {
+                const auto count{3 + subs[0]->ops.count + subs[1]->ops.count};
+                const auto sat{subs[0]->ops.sat | (subs[1]->ops.sat + subs[0]->ops.dsat)};
+                const auto dsat{subs[0]->ops.dsat + subs[1]->ops.dsat};
+                return {count, sat, dsat};
+            }
+            case Fragment::OR_C: {
+                const auto count{2 + subs[0]->ops.count + subs[1]->ops.count};
+                const auto sat{subs[0]->ops.sat | (subs[1]->ops.sat + subs[0]->ops.dsat)};
+                return {count, sat, {}};
+            }
+            case Fragment::OR_I: {
+                const auto count{3 + subs[0]->ops.count + subs[1]->ops.count};
+                const auto sat{subs[0]->ops.sat | subs[1]->ops.sat};
+                const auto dsat{subs[0]->ops.dsat | subs[1]->ops.dsat};
+                return {count, sat, dsat};
+            }
+            case Fragment::ANDOR: {
+                const auto count{3 + subs[0]->ops.count + subs[1]->ops.count + subs[2]->ops.count};
+                const auto sat{(subs[1]->ops.sat + subs[0]->ops.sat) | (subs[0]->ops.dsat + subs[2]->ops.sat)};
+                const auto dsat{subs[0]->ops.dsat + subs[2]->ops.dsat};
+                return {count, sat, dsat};
+            }
+            case Fragment::MULTI: return {1, (uint32_t)keys.size(), (uint32_t)keys.size()};
+            case Fragment::WRAP_S:
+            case Fragment::WRAP_C:
+            case Fragment::WRAP_N: return {1 + subs[0]->ops.count, subs[0]->ops.sat, subs[0]->ops.dsat};
+            case Fragment::WRAP_A: return {2 + subs[0]->ops.count, subs[0]->ops.sat, subs[0]->ops.dsat};
+            case Fragment::WRAP_D: return {3 + subs[0]->ops.count, subs[0]->ops.sat, 0};
+            case Fragment::WRAP_J: return {4 + subs[0]->ops.count, subs[0]->ops.sat, 0};
+            case Fragment::WRAP_V: return {subs[0]->ops.count + (subs[0]->GetType() << "x"_mst), subs[0]->ops.sat, {}};
+            case Fragment::THRESH: {
+                uint32_t count = 0;
+                auto sats = Vector(internal::MaxInt<uint32_t>(0));
+                for (const auto& sub : subs) {
+                    count += sub->ops.count + 1;
+                    auto next_sats = Vector(sats[0] + sub->ops.dsat);
+                    for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub->ops.dsat) | (sats[j - 1] + sub->ops.sat));
+                    next_sats.push_back(sats[sats.size() - 1] + sub->ops.sat);
+                    sats = std::move(next_sats);
+                }
+                assert(k <= sats.size());
+                return {count, sats[k], sats[0]};
+            }
+        }
+        assert(false);
+        return {0, {}, {}};
+    }
+
+    internal::StackSize CalcStackSize() const {
+        switch (nodetype) {
+            case Fragment::JUST_0: return {{}, 0};
+            case Fragment::JUST_1:
+            case Fragment::OLDER:
+            case Fragment::AFTER: return {0, {}};
+            case Fragment::PK_K: return {1, 1};
+            case Fragment::PK_H: return {2, 2};
+            case Fragment::SHA256:
+            case Fragment::RIPEMD160:
+            case Fragment::HASH256:
+            case Fragment::HASH160: return {1, {}};
+            case Fragment::ANDOR: {
+                const auto sat{(subs[0]->ss.sat + subs[1]->ss.sat) | (subs[0]->ss.dsat + subs[2]->ss.sat)};
+                const auto dsat{subs[0]->ss.dsat + subs[2]->ss.dsat};
+                return {sat, dsat};
+            }
+            case Fragment::AND_V: return {subs[0]->ss.sat + subs[1]->ss.sat, {}};
+            case Fragment::AND_B: return {subs[0]->ss.sat + subs[1]->ss.sat, subs[0]->ss.dsat + subs[1]->ss.dsat};
+            case Fragment::OR_B: {
+                const auto sat{(subs[0]->ss.dsat + subs[1]->ss.sat) | (subs[0]->ss.sat + subs[1]->ss.dsat)};
+                const auto dsat{subs[0]->ss.dsat + subs[1]->ss.dsat};
+                return {sat, dsat};
+            }
+            case Fragment::OR_C: return {subs[0]->ss.sat | (subs[0]->ss.dsat + subs[1]->ss.sat), {}};
+            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};
+            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)};
+            case Fragment::MULTI: return {k + 1, k + 1};
+            case Fragment::WRAP_A:
+            case Fragment::WRAP_N:
+            case Fragment::WRAP_S:
+            case Fragment::WRAP_C: return subs[0]->ss;
+            case Fragment::WRAP_D: return {1 + subs[0]->ss.sat, 1};
+            case Fragment::WRAP_V: return {subs[0]->ss.sat, {}};
+            case Fragment::WRAP_J: return {subs[0]->ss.sat, 1};
+            case Fragment::THRESH: {
+                auto sats = Vector(internal::MaxInt<uint32_t>(0));
+                for (const auto& sub : subs) {
+                    auto next_sats = Vector(sats[0] + sub->ss.dsat);
+                    for (size_t j = 1; j < sats.size(); ++j) next_sats.push_back((sats[j] + sub->ss.dsat) | (sats[j - 1] + sub->ss.sat));
+                    next_sats.push_back(sats[sats.size() - 1] + sub->ss.sat);
+                    sats = std::move(next_sats);
+                }
+                assert(k <= sats.size());
+                return {sats[k], sats[0]};
+            }
+        }
+        assert(false);
+        return {{}, {}};
+    }
+
+public:
+    //! Return the size of the script for this expression (faster than ToScript().size()).
+    size_t ScriptSize() const { return scriptlen; }
+
+    //! Return the maximum number of ops needed to satisfy this script non-malleably.
+    uint32_t GetOps() const { return ops.count + ops.sat.value; }
+
+    //! Check the ops limit of this script against the consensus limit.
+    bool CheckOpsLimit() const { return GetOps() <= MAX_OPS_PER_SCRIPT; }
+
+    /** Return the maximum number of stack elements needed to satisfy this script non-malleably, including
+     * the script push. */
+    uint32_t GetStackSize() const { return ss.sat.value + 1; }
+
+    //! Check the maximum stack size for this script against the policy limit.
+    bool CheckStackSize() const { return GetStackSize() - 1 <= MAX_STANDARD_P2WSH_STACK_ITEMS; }
+
+    //! Return the expression type.
+    Type GetType() const { return typ; }
+
+    //! Check whether this node is valid at all.
+    bool IsValid() const { return !(GetType() == ""_mst) && ScriptSize() <= MAX_STANDARD_P2WSH_SCRIPT_SIZE; }
+
+    //! Check whether this node is valid as a script on its own.
+    bool IsValidTopLevel() const { return IsValid() && GetType() << "B"_mst; }
+
+    //! Check whether this script can always be satisfied in a non-malleable way.
+    bool IsNonMalleable() const { return GetType() << "m"_mst; }
+
+    //! Check whether this script always needs a signature.
+    bool NeedsSignature() const { return GetType() << "s"_mst; }
+
+    //! Do all sanity checks.
+    bool IsSane() const { return IsValid() && GetType() << "mk"_mst && CheckOpsLimit() && CheckStackSize(); }
+
+    //! Check whether this node is safe as a script on its own.
+    bool IsSaneTopLevel() const { return IsValidTopLevel() && IsSane() && NeedsSignature(); }
+
+    //! Equality testing.
+    bool operator==(const Node<Key>& arg) const
+    {
+        if (nodetype != arg.nodetype) return false;
+        if (k != arg.k) return false;
+        if (data != arg.data) return false;
+        if (keys != arg.keys) return false;
+        if (subs.size() != arg.subs.size()) return false;
+        for (size_t i = 0; i < subs.size(); ++i) {
+            if (!(*subs[i] == *arg.subs[i])) return false;
+        }
+        assert(scriptlen == arg.scriptlen);
+        assert(typ == arg.typ);
+        return true;
+    }
+
+    // Constructors with various argument combinations.
+    Node(Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<unsigned char> arg, uint32_t val = 0) : nodetype(nt), k(val), data(std::move(arg)), subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
+    Node(Fragment nt, std::vector<unsigned char> arg, uint32_t val = 0) : nodetype(nt), k(val), data(std::move(arg)), ops(CalcOps()), ss(CalcStackSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
+    Node(Fragment nt, std::vector<NodeRef<Key>> sub, std::vector<Key> key, uint32_t val = 0) : nodetype(nt), k(val), keys(std::move(key)), subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
+    Node(Fragment nt, std::vector<Key> key, uint32_t val = 0) : nodetype(nt), k(val), keys(std::move(key)), ops(CalcOps()), ss(CalcStackSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
+    Node(Fragment nt, std::vector<NodeRef<Key>> sub, uint32_t val = 0) : nodetype(nt), k(val), subs(std::move(sub)), ops(CalcOps()), ss(CalcStackSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
+    Node(Fragment nt, uint32_t val = 0) : nodetype(nt), k(val), ops(CalcOps()), ss(CalcStackSize()), typ(CalcType()), scriptlen(CalcScriptLen()) {}
+};
+
+namespace internal {
+
+enum class ParseContext {
+    /** An expression which may be begin with wrappers followed by a colon. */
+    WRAPPED_EXPR,
+    /** A miniscript expression which does not begin with wrappers. */
+    EXPR,
+
+    /** SWAP wraps the top constructed node with s: */
+    SWAP,
+    /** ALT wraps the top constructed node 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,
+    /** WRAP_U will construct an or_i(X,0) node from the top constructed node. */
+    WRAP_U,
+    /** WRAP_T will construct an and_v(X,1) node from the top constructed node. */
+    WRAP_T,
+
+    /** AND_N will construct an andor(X,Y,0) node from the last two constructed nodes. */
+    AND_N,
+    /** 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,
+    /** OR_I will construct an or_i node from the last two constructed nodes. */
+    OR_I,
+
+    /** THRESH will read a wrapped expression, and then look for a COMMA. If
+     * no comma follows, it will construct a thresh node from the appropriate
+     * number of constructed children. Otherwise, it will recurse with another
+     * THRESH. */
+    THRESH,
+
+    /** COMMA expects the next element to be ',' and fails if not. */
+    COMMA,
+    /** CLOSE_BRACKET expects the next element to be ')' and fails if not. */
+    CLOSE_BRACKET,
+};
+
+int FindNextChar(Span<const char> in, const char m);
+
+/** Parse a key string ending with a ')' or ','. */
+template<typename Key, typename Ctx>
+std::optional<std::pair<Key, int>> ParseKeyEnd(Span<const char> in, const Ctx& ctx)
+{
+    Key key;
+    int key_size = FindNextChar(in, ')');
+    if (key_size < 1) return {};
+    if (!ctx.FromString(in.begin(), in.begin() + key_size, key)) return {};
+    return {{std::move(key), key_size}};
+}
+
+/** Parse a hex string ending at the end of the fragment's text representation. */
+template<typename Ctx>
+std::optional<std::pair<std::vector<unsigned char>, int>> ParseHexStrEnd(Span<const char> in, const size_t expected_size,
+                                                                         const Ctx& ctx)
+{
+    int hash_size = FindNextChar(in, ')');
+    if (hash_size < 1) return {};
+    std::string val = std::string(in.begin(), in.begin() + hash_size);
+    if (!IsHex(val)) return {};
+    auto hash = ParseHex(val);
+    if (hash.size() != expected_size) return {};
+    return {{std::move(hash), hash_size}};
+}
+
+/** BuildBack pops the last two elements off `constructed` and wraps them in the specified Fragment */
+template<typename Key>
+void BuildBack(Fragment nt, std::vector<NodeRef<Key>>& constructed, const bool reverse = false)
+{
+    NodeRef<Key> child = std::move(constructed.back());
+    constructed.pop_back();
+    if (reverse) {
+        constructed.back() = MakeNodeRef<Key>(nt, Vector(std::move(child), std::move(constructed.back())));
+    } else {
+        constructed.back() = MakeNodeRef<Key>(nt, Vector(std::move(constructed.back()), std::move(child)));
+    }
+}
+
+//! Parse a miniscript from its textual descriptor form.
+template<typename Key, typename Ctx>
+inline NodeRef<Key> Parse(Span<const char> in, const Ctx& ctx)
+{
+    using namespace spanparsing;
+
+    // The two integers are used to hold state for thresh()
+    std::vector<std::tuple<ParseContext, int64_t, int64_t>> to_parse;
+    std::vector<NodeRef<Key>> constructed;
+
+    to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
+
+    while (!to_parse.empty()) {
+        // Get the current context we are decoding within
+        auto [cur_context, n, k] = to_parse.back();
+        to_parse.pop_back();
+
+        switch (cur_context) {
+        case ParseContext::WRAPPED_EXPR: {
+            int colon_index = -1;
+            for (int i = 1; i < (int)in.size(); ++i) {
+                if (in[i] == ':') {
+                    colon_index = i;
+                    break;
+                }
+                if (in[i] < 'a' || in[i] > 'z') break;
+            }
+            // If there is no colon, this loop won't execute
+            for (int j = 0; j < colon_index; ++j) {
+                if (in[j] == 'a') {
+                    to_parse.emplace_back(ParseContext::ALT, -1, -1);
+                } else if (in[j] == 's') {
+                    to_parse.emplace_back(ParseContext::SWAP, -1, -1);
+                } else if (in[j] == 'c') {
+                    to_parse.emplace_back(ParseContext::CHECK, -1, -1);
+                } else if (in[j] == 'd') {
+                    to_parse.emplace_back(ParseContext::DUP_IF, -1, -1);
+                } else if (in[j] == 'j') {
+                    to_parse.emplace_back(ParseContext::NON_ZERO, -1, -1);
+                } else if (in[j] == 'n') {
+                    to_parse.emplace_back(ParseContext::ZERO_NOTEQUAL, -1, -1);
+                } else if (in[j] == 'v') {
+                    to_parse.emplace_back(ParseContext::VERIFY, -1, -1);
+                } else if (in[j] == 'u') {
+                    to_parse.emplace_back(ParseContext::WRAP_U, -1, -1);
+                } else if (in[j] == 't') {
+                    to_parse.emplace_back(ParseContext::WRAP_T, -1, -1);
+                } else if (in[j] == 'l') {
+                    // The l: wrapper is equivalent to or_i(0,X)
+                    constructed.push_back(MakeNodeRef<Key>(Fragment::JUST_0));
+                    to_parse.emplace_back(ParseContext::OR_I, -1, -1);
+                } else {
+                    return {};
+                }
+            }
+            to_parse.emplace_back(ParseContext::EXPR, -1, -1);
+            in = in.subspan(colon_index + 1);
+            break;
+        }
+        case ParseContext::EXPR: {
+            if (Const("0", in)) {
+                constructed.push_back(MakeNodeRef<Key>(Fragment::JUST_0));
+            } else if (Const("1", in)) {
+                constructed.push_back(MakeNodeRef<Key>(Fragment::JUST_1));
+            } else if (Const("pk(", in)) {
+                auto res = ParseKeyEnd<Key, Ctx>(in, ctx);
+                if (!res) return {};
+                auto& [key, key_size] = *res;
+                constructed.push_back(MakeNodeRef<Key>(Fragment::WRAP_C, Vector(MakeNodeRef<Key>(Fragment::PK_K, Vector(std::move(key))))));
+                in = in.subspan(key_size + 1);
+            } else if (Const("pkh(", in)) {
+                auto res = ParseKeyEnd<Key>(in, ctx);
+                if (!res) return {};
+                auto& [key, key_size] = *res;
+                constructed.push_back(MakeNodeRef<Key>(Fragment::WRAP_C, Vector(MakeNodeRef<Key>(Fragment::PK_H, Vector(std::move(key))))));
+                in = in.subspan(key_size + 1);
+            } else if (Const("pk_k(", in)) {
+                auto res = ParseKeyEnd<Key>(in, ctx);
+                if (!res) return {};
+                auto& [key, key_size] = *res;
+                constructed.push_back(MakeNodeRef<Key>(Fragment::PK_K, Vector(std::move(key))));
+                in = in.subspan(key_size + 1);
+            } else if (Const("pk_h(", in)) {
+                auto res = ParseKeyEnd<Key>(in, ctx);
+                if (!res) return {};
+                auto& [key, key_size] = *res;
+                constructed.push_back(MakeNodeRef<Key>(Fragment::PK_H, Vector(std::move(key))));
+                in = in.subspan(key_size + 1);
+            } else if (Const("sha256(", in)) {
+                auto res = ParseHexStrEnd(in, 32, ctx);
+                if (!res) return {};
+                auto& [hash, hash_size] = *res;
+                constructed.push_back(MakeNodeRef<Key>(Fragment::SHA256, std::move(hash)));
+                in = in.subspan(hash_size + 1);
+            } else if (Const("ripemd160(", in)) {
+                auto res = ParseHexStrEnd(in, 20, ctx);
+                if (!res) return {};
+                auto& [hash, hash_size] = *res;
+                constructed.push_back(MakeNodeRef<Key>(Fragment::RIPEMD160, std::move(hash)));
+                in = in.subspan(hash_size + 1);
+            } else if (Const("hash256(", in)) {
+                auto res = ParseHexStrEnd(in, 32, ctx);
+                if (!res) return {};
+                auto& [hash, hash_size] = *res;
+                constructed.push_back(MakeNodeRef<Key>(Fragment::HASH256, std::move(hash)));
+                in = in.subspan(hash_size + 1);
+            } else if (Const("hash160(", in)) {
+                auto res = ParseHexStrEnd(in, 20, ctx);
+                if (!res) return {};
+                auto& [hash, hash_size] = *res;
+                constructed.push_back(MakeNodeRef<Key>(Fragment::HASH160, std::move(hash)));
+                in = in.subspan(hash_size + 1);
+            } else if (Const("after(", in)) {
+                int arg_size = FindNextChar(in, ')');
+                if (arg_size < 1) return {};
+                int64_t num;
+                if (!ParseInt64(std::string(in.begin(), in.begin() + arg_size), &num)) return {};
+                if (num < 1 || num >= 0x80000000L) return {};
+                constructed.push_back(MakeNodeRef<Key>(Fragment::AFTER, num));
+                in = in.subspan(arg_size + 1);
+            } else if (Const("older(", in)) {
+                int arg_size = FindNextChar(in, ')');
+                if (arg_size < 1) return {};
+                int64_t num;
+                if (!ParseInt64(std::string(in.begin(), in.begin() + arg_size), &num)) return {};
+                if (num < 1 || num >= 0x80000000L) return {};
+                constructed.push_back(MakeNodeRef<Key>(Fragment::OLDER, num));
+                in = in.subspan(arg_size + 1);
+            } else if (Const("multi(", in)) {
+                // Get threshold
+                int next_comma = FindNextChar(in, ',');
+                if (next_comma < 1) return {};
+                if (!ParseInt64(std::string(in.begin(), in.begin() + next_comma), &k)) return {};
+                in = in.subspan(next_comma + 1);
+                // Get keys
+                std::vector<Key> keys;
+                while (next_comma != -1) {
+                    Key key;
+                    next_comma = FindNextChar(in, ',');
+                    int key_length = (next_comma == -1) ? FindNextChar(in, ')') : next_comma;
+                    if (key_length < 1) return {};
+                    if (!ctx.FromString(in.begin(), in.begin() + key_length, key)) return {};
+                    keys.push_back(std::move(key));
+                    in = in.subspan(key_length + 1);
+                }
+                if (keys.size() < 1 || keys.size() > 20) return {};
+                if (k < 1 || k > (int64_t)keys.size()) return {};
+                constructed.push_back(MakeNodeRef<Key>(Fragment::MULTI, std::move(keys), k));
+            } else if (Const("thresh(", in)) {
+                int next_comma = FindNextChar(in, ',');
+                if (next_comma < 1) return {};
+                if (!ParseInt64(std::string(in.begin(), in.begin() + next_comma), &k)) return {};
+                if (k < 1) return {};
+                in = in.subspan(next_comma + 1);
+                // n = 1 here because we read the first WRAPPED_EXPR before reaching THRESH
+                to_parse.emplace_back(ParseContext::THRESH, 1, k);
+                to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
+            } else if (Const("andor(", in)) {
+                to_parse.emplace_back(ParseContext::ANDOR, -1, -1);
+                to_parse.emplace_back(ParseContext::CLOSE_BRACKET, -1, -1);
+                to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
+                to_parse.emplace_back(ParseContext::COMMA, -1, -1);
+                to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
+                to_parse.emplace_back(ParseContext::COMMA, -1, -1);
+                to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
+            } else {
+                if (Const("and_n(", in)) {
+                    to_parse.emplace_back(ParseContext::AND_N, -1, -1);
+                } else if (Const("and_b(", in)) {
+                    to_parse.emplace_back(ParseContext::AND_B, -1, -1);
+                } else if (Const("and_v(", in)) {
+                    to_parse.emplace_back(ParseContext::AND_V, -1, -1);
+                } else if (Const("or_b(", in)) {
+                    to_parse.emplace_back(ParseContext::OR_B, -1, -1);
+                } else if (Const("or_c(", in)) {
+                    to_parse.emplace_back(ParseContext::OR_C, -1, -1);
+                } else if (Const("or_d(", in)) {
+                    to_parse.emplace_back(ParseContext::OR_D, -1, -1);
+                } else if (Const("or_i(", in)) {
+                    to_parse.emplace_back(ParseContext::OR_I, -1, -1);
+                } else {
+                    return {};
+                }
+                to_parse.emplace_back(ParseContext::CLOSE_BRACKET, -1, -1);
+                to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
+                to_parse.emplace_back(ParseContext::COMMA, -1, -1);
+                to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
+            }
+            break;
+        }
+        case ParseContext::ALT: {
+            constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_A, Vector(std::move(constructed.back())));
+            break;
+        }
+        case ParseContext::SWAP: {
+            constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_S, Vector(std::move(constructed.back())));
+            break;
+        }
+        case ParseContext::CHECK: {
+            constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_C, Vector(std::move(constructed.back())));
+            break;
+        }
+        case ParseContext::DUP_IF: {
+            constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_D, Vector(std::move(constructed.back())));
+            break;
+        }
+        case ParseContext::NON_ZERO: {
+            constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_J, Vector(std::move(constructed.back())));
+            break;
+        }
+        case ParseContext::ZERO_NOTEQUAL: {
+            constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_N, Vector(std::move(constructed.back())));
+            break;
+        }
+        case ParseContext::VERIFY: {
+            constructed.back() = MakeNodeRef<Key>(Fragment::WRAP_V, Vector(std::move(constructed.back())));
+            break;
+        }
+        case ParseContext::WRAP_U: {
+            constructed.back() = MakeNodeRef<Key>(Fragment::OR_I, Vector(std::move(constructed.back()), MakeNodeRef<Key>(Fragment::JUST_0)));
+            break;
+        }
+        case ParseContext::WRAP_T: {
+            constructed.back() = MakeNodeRef<Key>(Fragment::AND_V, Vector(std::move(constructed.back()), MakeNodeRef<Key>(Fragment::JUST_1)));
+            break;
+        }
+        case ParseContext::AND_B: {
+            BuildBack(Fragment::AND_B, constructed);
+            break;
+        }
+        case ParseContext::AND_N: {
+            auto mid = std::move(constructed.back());
+            constructed.pop_back();
+            constructed.back() = MakeNodeRef<Key>(Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), MakeNodeRef<Key>(Fragment::JUST_0)));
+            break;
+        }
+        case ParseContext::AND_V: {
+            BuildBack(Fragment::AND_V, constructed);
+            break;
+        }
+        case ParseContext::OR_B: {
+            BuildBack(Fragment::OR_B, constructed);
+            break;
+        }
+        case ParseContext::OR_C: {
+            BuildBack(Fragment::OR_C, constructed);
+            break;
+        }
+        case ParseContext::OR_D: {
+            BuildBack(Fragment::OR_D, constructed);
+            break;
+        }
+        case ParseContext::OR_I: {
+            BuildBack(Fragment::OR_I, constructed);
+            break;
+        }
+        case ParseContext::ANDOR: {
+            auto right = std::move(constructed.back());
+            constructed.pop_back();
+            auto mid = std::move(constructed.back());
+            constructed.pop_back();
+            constructed.back() = MakeNodeRef<Key>(Fragment::ANDOR, Vector(std::move(constructed.back()), std::move(mid), std::move(right)));
+            break;
+        }
+        case ParseContext::THRESH: {
+            if (in.size() < 1) return {};
+            if (in[0] == ',') {
+                in = in.subspan(1);
+                to_parse.emplace_back(ParseContext::THRESH, n+1, k);
+                to_parse.emplace_back(ParseContext::WRAPPED_EXPR, -1, -1);
+            } else if (in[0] == ')') {
+                if (k > n) return {};
+                in = in.subspan(1);
+                // Children are constructed in reverse order, so iterate from end to beginning
+                std::vector<NodeRef<Key>> subs;
+                for (int i = 0; i < n; ++i) {
+                    subs.push_back(std::move(constructed.back()));
+                    constructed.pop_back();
+                }
+                std::reverse(subs.begin(), subs.end());
+                constructed.push_back(MakeNodeRef<Key>(Fragment::THRESH, std::move(subs), k));
+            } else {
+                return {};
+            }
+            break;
+        }
+        case ParseContext::COMMA: {
+            if (in.size() < 1 || in[0] != ',') return {};
+            in = in.subspan(1);
+            break;
+        }
+        case ParseContext::CLOSE_BRACKET: {
+            if (in.size() < 1 || in[0] != ')') return {};
+            in = in.subspan(1);
+            break;
+        }
+        }
+    }
+
+    // Sanity checks on the produced miniscript
+    assert(constructed.size() == 1);
+    if (in.size() > 0) return {};
+    const NodeRef<Key> tl_node = std::move(constructed.front());
+    if (!tl_node->IsValidTopLevel()) return {};
+    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>
+inline NodeRef<typename Ctx::Key> FromString(const std::string& str, const Ctx& 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
diff --git a/src/script/script.cpp b/src/script/script.cpp
index 9a6419088b..88b4bc2f44 100644
--- a/src/script/script.cpp
+++ b/src/script/script.cpp
@@ -339,3 +339,28 @@ bool IsOpSuccess(const opcodetype& opcode)
            (opcode >= 141 && opcode <= 142) || (opcode >= 149 && opcode <= 153) ||
            (opcode >= 187 && opcode <= 254);
 }
+
+bool CheckMinimalPush(const std::vector<unsigned char>& data, opcodetype opcode) {
+    // Excludes OP_1NEGATE, OP_1-16 since they are by definition minimal
+    assert(0 <= opcode && opcode <= OP_PUSHDATA4);
+    if (data.size() == 0) {
+        // Should have used OP_0.
+        return opcode == OP_0;
+    } else if (data.size() == 1 && data[0] >= 1 && data[0] <= 16) {
+        // Should have used OP_1 .. OP_16.
+        return false;
+    } else if (data.size() == 1 && data[0] == 0x81) {
+        // Should have used OP_1NEGATE.
+        return false;
+    } else if (data.size() <= 75) {
+        // Must have used a direct push (opcode indicating number of bytes pushed + those bytes).
+        return opcode == data.size();
+    } else if (data.size() <= 255) {
+        // Must have used OP_PUSHDATA.
+        return opcode == OP_PUSHDATA1;
+    } else if (data.size() <= 65535) {
+        // Must have used OP_PUSHDATA2.
+        return opcode == OP_PUSHDATA2;
+    }
+    return true;
+}
diff --git a/src/script/script.h b/src/script/script.h
index a89c987306..3b799ad637 100644
--- a/src/script/script.h
+++ b/src/script/script.h
@@ -335,6 +335,8 @@ public:
         return m_value;
     }
 
+    int64_t GetInt64() const { return m_value; }
+
     std::vector<unsigned char> getvch() const
     {
         return serialize(m_value);
@@ -576,4 +578,31 @@ struct CScriptWitness
 /** Test for OP_SUCCESSx opcodes as defined by BIP342. */
 bool IsOpSuccess(const opcodetype& opcode);
 
+bool CheckMinimalPush(const std::vector<unsigned char>& data, opcodetype opcode);
+
+/** Build a script by concatenating other scripts, or any argument accepted by CScript::operator<<. */
+template<typename... Ts>
+CScript BuildScript(Ts&&... inputs)
+{
+    CScript ret;
+    int cnt{0};
+
+    ([&ret, &cnt] (Ts&& input) {
+        cnt++;
+        if constexpr (std::is_same_v<std::remove_cv_t<std::remove_reference_t<Ts>>, CScript>) {
+            // If it is a CScript, extend ret with it. Move or copy the first element instead.
+            if (cnt == 0) {
+                ret = std::forward<Ts>(input);
+            } else {
+                ret.insert(ret.end(), input.begin(), input.end());
+            }
+        } else {
+            // Otherwise invoke CScript::operator<<.
+            ret << input;
+        }
+    } (std::forward<Ts>(inputs)), ...);
+
+    return ret;
+}
+
 #endif // BITCOIN_SCRIPT_SCRIPT_H
diff --git a/src/script/standard.cpp b/src/script/standard.cpp
index b77c78769f..e25155d3dd 100644
--- a/src/script/standard.cpp
+++ b/src/script/standard.cpp
@@ -91,11 +91,6 @@ static constexpr bool IsSmallInteger(opcodetype opcode)
     return opcode >= OP_1 && opcode <= OP_16;
 }
 
-static constexpr bool IsPushdataOp(opcodetype opcode)
-{
-    return opcode > OP_FALSE && opcode <= OP_PUSHDATA4;
-}
-
 /** Retrieve a minimally-encoded number in range [min,max] from an (opcode, data) pair,
  *  whether it's OP_n or through a push. */
 static std::optional<int> GetScriptNumber(opcodetype opcode, valtype data, int min, int max)
diff --git a/src/script/standard.h b/src/script/standard.h
index 75bfe2db38..f0b143c52b 100644
--- a/src/script/standard.h
+++ b/src/script/standard.h
@@ -162,6 +162,11 @@ bool IsValidDestination(const CTxDestination& dest);
 /** Get the name of a TxoutType as a string */
 std::string GetTxnOutputType(TxoutType t);
 
+constexpr bool IsPushdataOp(opcodetype opcode)
+{
+    return opcode > OP_FALSE && opcode <= OP_PUSHDATA4;
+}
+
 /**
  * Parse a scriptPubKey and identify script type for standard scripts. If
  * successful, returns script type and parsed pubkeys or hashes, depending on
diff --git a/src/test/fuzz/miniscript_decode.cpp b/src/test/fuzz/miniscript_decode.cpp
new file mode 100644
index 0000000000..4cc0a1be8f
--- /dev/null
+++ b/src/test/fuzz/miniscript_decode.cpp
@@ -0,0 +1,72 @@
+// Copyright (c) 2022 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+#include <core_io.h>
+#include <hash.h>
+#include <key.h>
+#include <script/miniscript.h>
+#include <script/script.h>
+#include <span.h>
+#include <test/fuzz/FuzzedDataProvider.h>
+#include <test/fuzz/fuzz.h>
+#include <test/fuzz/util.h>
+#include <util/strencodings.h>
+
+#include <optional>
+
+using miniscript::operator""_mst;
+
+
+struct Converter {
+    typedef CPubKey Key;
+
+    bool ToString(const Key& key, std::string& ret) const {
+        ret = HexStr(key);
+        return true;
+    }
+    const std::vector<unsigned char> ToPKBytes(const Key& key) const {
+        return {key.begin(), key.end()};
+    }
+    const std::vector<unsigned char> ToPKHBytes(const Key& key) const {
+        const auto h = Hash160(key);
+        return {h.begin(), h.end()};
+    }
+
+    template<typename I>
+    bool FromString(I first, I last, Key& key) const {
+        const auto bytes = ParseHex(std::string(first, last));
+        key.Set(bytes.begin(), bytes.end());
+        return key.IsValid();
+    }
+    template<typename I>
+    bool FromPKBytes(I first, I last, CPubKey& key) const {
+        key.Set(first, last);
+        return key.IsValid();
+    }
+    template<typename I>
+    bool FromPKHBytes(I first, I last, CPubKey& key) const {
+        assert(last - first == 20);
+        return false;
+    }
+};
+
+const Converter CONVERTER;
+
+FUZZ_TARGET(miniscript_decode)
+{
+    FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
+    const std::optional<CScript> script = ConsumeDeserializable<CScript>(fuzzed_data_provider);
+    if (!script) return;
+
+    const auto ms = miniscript::FromScript(*script, CONVERTER);
+    if (!ms) return;
+
+    // We can roundtrip it to its string representation.
+    std::string ms_str;
+    assert(ms->ToString(CONVERTER, ms_str));
+    assert(*miniscript::FromString(ms_str, CONVERTER) == *ms);
+    // The Script representation must roundtrip since we parsed it this way the first time.
+    const CScript ms_script = ms->ToScript(CONVERTER);
+    assert(ms_script == *script);
+}
diff --git a/src/test/miniscript_tests.cpp b/src/test/miniscript_tests.cpp
new file mode 100644
index 0000000000..949d30dfd5
--- /dev/null
+++ b/src/test/miniscript_tests.cpp
@@ -0,0 +1,284 @@
+// Copyright (c) 2019 The Bitcoin Core developers
+// Distributed under the MIT software license, see the accompanying
+// file COPYING or http://www.opensource.org/licenses/mit-license.php.
+
+
+#include <string>
+
+#include <test/util/setup_common.h>
+#include <boost/test/unit_test.hpp>
+
+#include <hash.h>
+#include <pubkey.h>
+#include <uint256.h>
+#include <crypto/ripemd160.h>
+#include <crypto/sha256.h>
+#include <script/miniscript.h>
+
+namespace {
+
+/** TestData groups various kinds of precomputed data necessary in this test. */
+struct TestData {
+    //! The only public keys used in this test.
+    std::vector<CPubKey> pubkeys;
+    //! A map from the public keys to their CKeyIDs (faster than hashing every time).
+    std::map<CPubKey, CKeyID> pkhashes;
+    std::map<CKeyID, CPubKey> pkmap;
+
+    // Various precomputed hashes
+    std::vector<std::vector<unsigned char>> sha256;
+    std::vector<std::vector<unsigned char>> ripemd160;
+    std::vector<std::vector<unsigned char>> hash256;
+    std::vector<std::vector<unsigned char>> hash160;
+
+    TestData()
+    {
+        // We generate 255 public keys and 255 hashes of each type.
+        for (int i = 1; i <= 255; ++i) {
+            // This 32-byte array functions as both private key data and hash preimage (31 zero bytes plus any nonzero byte).
+            unsigned char keydata[32] = {0};
+            keydata[31] = i;
+
+            // Compute CPubkey and CKeyID
+            CKey key;
+            key.Set(keydata, keydata + 32, true);
+            CPubKey pubkey = key.GetPubKey();
+            CKeyID keyid = pubkey.GetID();
+            pubkeys.push_back(pubkey);
+            pkhashes.emplace(pubkey, keyid);
+            pkmap.emplace(keyid, pubkey);
+
+            // Compute various hashes
+            std::vector<unsigned char> hash;
+            hash.resize(32);
+            CSHA256().Write(keydata, 32).Finalize(hash.data());
+            sha256.push_back(hash);
+            CHash256().Write(keydata).Finalize(hash);
+            hash256.push_back(hash);
+            hash.resize(20);
+            CRIPEMD160().Write(keydata, 32).Finalize(hash.data());
+            ripemd160.push_back(hash);
+            CHash160().Write(keydata).Finalize(hash);
+            hash160.push_back(hash);
+        }
+    }
+};
+
+//! Global TestData object
+std::unique_ptr<const TestData> g_testdata;
+
+/** A class encapsulating conversion routing for CPubKey. */
+struct KeyConverter {
+    typedef CPubKey Key;
+
+    //! Convert a public key to bytes.
+    std::vector<unsigned char> ToPKBytes(const CPubKey& key) const { return {key.begin(), key.end()}; }
+
+    //! Convert a public key to its Hash160 bytes (precomputed).
+    std::vector<unsigned char> ToPKHBytes(const CPubKey& key) const
+    {
+        auto it = g_testdata->pkhashes.find(key);
+        assert(it != g_testdata->pkhashes.end());
+        return {it->second.begin(), it->second.end()};
+    }
+
+    //! Parse a public key from a range of hex characters.
+    template<typename I>
+    bool FromString(I first, I last, CPubKey& key) const {
+        auto bytes = ParseHex(std::string(first, last));
+        key.Set(bytes.begin(), bytes.end());
+        return key.IsValid();
+    }
+
+    template<typename I>
+    bool FromPKBytes(I first, I last, CPubKey& key) const {
+        key.Set(first, last);
+        return key.IsValid();
+    }
+
+    template<typename I>
+    bool FromPKHBytes(I first, I last, CPubKey& key) const {
+        assert(last - first == 20);
+        CKeyID keyid;
+        std::copy(first, last, keyid.begin());
+        auto it = g_testdata->pkmap.find(keyid);
+        assert(it != g_testdata->pkmap.end());
+        key = it->second;
+        return true;
+    }
+};
+
+//! Singleton instance of KeyConverter.
+const KeyConverter CONVERTER{};
+
+using miniscript::operator"" _mst;
+
+enum TestMode : int {
+    TESTMODE_INVALID = 0,
+    TESTMODE_VALID = 1,
+    TESTMODE_NONMAL = 2,
+    TESTMODE_NEEDSIG = 4,
+    TESTMODE_TIMELOCKMIX = 8
+};
+
+void Test(const std::string& ms, const std::string& hexscript, int mode, int opslimit = -1, int stacklimit = -1)
+{
+    auto node = miniscript::FromString(ms, CONVERTER);
+    if (mode == TESTMODE_INVALID) {
+        BOOST_CHECK_MESSAGE(!node || !node->IsValid(), "Unexpectedly valid: " + ms);
+    } else {
+        BOOST_CHECK_MESSAGE(node, "Unparseable: " + ms);
+        BOOST_CHECK_MESSAGE(node->IsValid(), "Invalid: " + ms);
+        BOOST_CHECK_MESSAGE(node->IsValidTopLevel(), "Invalid top level: " + ms);
+        auto computed_script = node->ToScript(CONVERTER);
+        BOOST_CHECK_MESSAGE(node->ScriptSize() == computed_script.size(), "Script size mismatch: " + ms);
+        if (hexscript != "?") BOOST_CHECK_MESSAGE(HexStr(computed_script) == hexscript, "Script mismatch: " + ms + " (" + HexStr(computed_script) + " vs " + hexscript + ")");
+        BOOST_CHECK_MESSAGE(node->IsNonMalleable() == !!(mode & TESTMODE_NONMAL), "Malleability mismatch: " + ms);
+        BOOST_CHECK_MESSAGE(node->NeedsSignature() == !!(mode & TESTMODE_NEEDSIG), "Signature necessity mismatch: " + ms);
+        BOOST_CHECK_MESSAGE((node->GetType() << "k"_mst) == !(mode & TESTMODE_TIMELOCKMIX), "Timelock mix mismatch: " + ms);
+        auto inferred_miniscript = miniscript::FromScript(computed_script, CONVERTER);
+        BOOST_CHECK_MESSAGE(inferred_miniscript, "Cannot infer miniscript from script: " + ms);
+        BOOST_CHECK_MESSAGE(inferred_miniscript->ToScript(CONVERTER) == computed_script, "Roundtrip failure: miniscript->script != miniscript->script->miniscript->script: " + ms);
+        if (opslimit != -1) BOOST_CHECK_MESSAGE((int)node->GetOps() == opslimit, "Ops limit mismatch: " << ms << " (" << node->GetOps() << " vs " << opslimit << ")");
+        if (stacklimit != -1) BOOST_CHECK_MESSAGE((int)node->GetStackSize() == stacklimit, "Stack limit mismatch: " << ms << " (" << node->GetStackSize() << " vs " << stacklimit << ")");
+    }
+}
+} // namespace
+
+BOOST_FIXTURE_TEST_SUITE(miniscript_tests, BasicTestingSetup)
+
+BOOST_AUTO_TEST_CASE(fixed_tests)
+{
+    g_testdata.reset(new TestData());
+
+    // Validity rules
+    Test("l:older(1)", "?", TESTMODE_VALID | TESTMODE_NONMAL); // older(1): valid
+    Test("l:older(0)", "?", TESTMODE_INVALID); // older(0): k must be at least 1
+    Test("l:older(2147483647)", "?", TESTMODE_VALID | TESTMODE_NONMAL); // older(2147483647): valid
+    Test("l:older(2147483648)", "?", TESTMODE_INVALID); // older(2147483648): k must be below 2^31
+    Test("u:after(1)", "?", TESTMODE_VALID | TESTMODE_NONMAL); // after(1): valid
+    Test("u:after(0)", "?", TESTMODE_INVALID); // after(0): k must be at least 1
+    Test("u:after(2147483647)", "?", TESTMODE_VALID | TESTMODE_NONMAL); // after(2147483647): valid
+    Test("u:after(2147483648)", "?", TESTMODE_INVALID); // after(2147483648): k must be below 2^31
+    Test("andor(0,1,1)", "?", TESTMODE_VALID | TESTMODE_NONMAL); // andor(Bdu,B,B): valid
+    Test("andor(a:0,1,1)", "?", TESTMODE_INVALID); // andor(Wdu,B,B): X must be B
+    Test("andor(0,a:1,a:1)", "?", TESTMODE_INVALID); // andor(Bdu,W,W): Y and Z must be B/V/K
+    Test("andor(1,1,1)", "?", TESTMODE_INVALID); // andor(Bu,B,B): X must be d
+    Test("andor(n:or_i(0,after(1)),1,1)", "?", TESTMODE_VALID); // andor(Bdu,B,B): valid
+    Test("andor(or_i(0,after(1)),1,1)", "?", TESTMODE_INVALID); // andor(Bd,B,B): X must be u
+    Test("c:andor(0,pk_k(03a0434d9e47f3c86235477c7b1ae6ae5d3442d49b1943c2b752a68e2a47e247c7),pk_k(036d2b085e9e382ed10b69fc311a03f8641ccfff21574de0927513a49d9a688a00))", "?", TESTMODE_VALID | TESTMODE_NONMAL | TESTMODE_NEEDSIG); // andor(Bdu,K,K): valid
+    Test("t:andor(0,v:1,v:1)", "?", TESTMODE_VALID | TESTMODE_NONMAL); // andor(Bdu,V,V): valid
+    Test("and_v(v:1,1)", "?", TESTMODE_VALID | TESTMODE_NONMAL); // and_v(V,B): valid
+    Test("t:and_v(v:1,v:1)", "?", TESTMODE_VALID | TESTMODE_NONMAL); // and_v(V,V): valid
+    Test("c:and_v(v:1,pk_k(036d2b085e9e382ed10b69fc311a03f8641ccfff21574de0927513a49d9a688a00))", "?", TESTMODE_VALID | TESTMODE_NONMAL | TESTMODE_NEEDSIG); // and_v(V,K): valid
+    Test("and_v(1,1)", "?", TESTMODE_INVALID); // and_v(B,B): X must be V
+    Test("and_v(pk_k(02352bbf4a4cdd12564f93fa332ce333301d9ad40271f8107181340aef25be59d5),1)", "?", TESTMODE_INVALID); // and_v(K,B): X must be V
+    Test("and_v(v:1,a:1)", "?", TESTMODE_INVALID); // and_v(K,W): Y must be B/V/K
+    Test("and_b(1,a:1)", "?", TESTMODE_VALID | TESTMODE_NONMAL); // and_b(B,W): valid
+    Test("and_b(1,1)", "?", TESTMODE_INVALID); // and_b(B,B): Y must W
+    Test("and_b(v:1,a:1)", "?", TESTMODE_INVALID); // and_b(V,W): X must be B
+    Test("and_b(a:1,a:1)", "?", TESTMODE_INVALID); // and_b(W,W): X must be B
+    Test("and_b(pk_k(025601570cb47f238d2b0286db4a990fa0f3ba28d1a319f5e7cf55c2a2444da7cc),a:1)", "?", TESTMODE_INVALID); // and_b(K,W): X must be B
+    Test("or_b(0,a:0)", "?", TESTMODE_VALID | TESTMODE_NONMAL | TESTMODE_NEEDSIG); // or_b(Bd,Wd): valid
+    Test("or_b(1,a:0)", "?", TESTMODE_INVALID); // or_b(B,Wd): X must be d
+    Test("or_b(0,a:1)", "?", TESTMODE_INVALID); // or_b(Bd,W): Y must be d
+    Test("or_b(0,0)", "?", TESTMODE_INVALID); // or_b(Bd,Bd): Y must W
+    Test("or_b(v:0,a:0)", "?", TESTMODE_INVALID); // or_b(V,Wd): X must be B
+    Test("or_b(a:0,a:0)", "?", TESTMODE_INVALID); // or_b(Wd,Wd): X must be B
+    Test("or_b(pk_k(025601570cb47f238d2b0286db4a990fa0f3ba28d1a319f5e7cf55c2a2444da7cc),a:0)", "?", TESTMODE_INVALID); // or_b(Kd,Wd): X must be B
+    Test("t:or_c(0,v:1)", "?", TESTMODE_VALID | TESTMODE_NONMAL); // or_c(Bdu,V): valid
+    Test("t:or_c(a:0,v:1)", "?", TESTMODE_INVALID); // or_c(Wdu,V): X must be B
+    Test("t:or_c(1,v:1)", "?", TESTMODE_INVALID); // or_c(Bu,V): X must be d
+    Test("t:or_c(n:or_i(0,after(1)),v:1)", "?", TESTMODE_VALID); // or_c(Bdu,V): valid
+    Test("t:or_c(or_i(0,after(1)),v:1)", "?", TESTMODE_INVALID); // or_c(Bd,V): X must be u
+    Test("t:or_c(0,1)", "?", TESTMODE_INVALID); // or_c(Bdu,B): Y must be V
+    Test("or_d(0,1)", "?", TESTMODE_VALID | TESTMODE_NONMAL); // or_d(Bdu,B): valid
+    Test("or_d(a:0,1)", "?", TESTMODE_INVALID); // or_d(Wdu,B): X must be B
+    Test("or_d(1,1)", "?", TESTMODE_INVALID); // or_d(Bu,B): X must be d
+    Test("or_d(n:or_i(0,after(1)),1)", "?", TESTMODE_VALID); // or_d(Bdu,B): valid
+    Test("or_d(or_i(0,after(1)),1)", "?", TESTMODE_INVALID); // or_d(Bd,B): X must be u
+    Test("or_d(0,v:1)", "?", TESTMODE_INVALID); // or_d(Bdu,V): Y must be B
+    Test("or_i(1,1)", "?", TESTMODE_VALID); // or_i(B,B): valid
+    Test("t:or_i(v:1,v:1)", "?", TESTMODE_VALID); // or_i(V,V): valid
+    Test("c:or_i(pk_k(03a0434d9e47f3c86235477c7b1ae6ae5d3442d49b1943c2b752a68e2a47e247c7),pk_k(036d2b085e9e382ed10b69fc311a03f8641ccfff21574de0927513a49d9a688a00))", "?", TESTMODE_VALID | TESTMODE_NONMAL | TESTMODE_NEEDSIG); // or_i(K,K): valid
+    Test("or_i(a:1,a:1)", "?", TESTMODE_INVALID); // or_i(W,W): X and Y must be B/V/K
+    Test("or_b(l:after(100),al:after(1000000000))", "?", TESTMODE_VALID); // or_b(timelock, heighlock) valid
+    Test("and_b(after(100),a:after(1000000000))", "?", TESTMODE_VALID | TESTMODE_NONMAL | TESTMODE_TIMELOCKMIX); // and_b(timelock, heighlock) invalid
+    Test("pk(03d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65)", "2103d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65ac", TESTMODE_VALID | TESTMODE_NONMAL | TESTMODE_NEEDSIG); // alias to c:pk_k
+    Test("pkh(03d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65)", "76a914fcd35ddacad9f2d5be5e464639441c6065e6955d88ac", TESTMODE_VALID | TESTMODE_NONMAL | TESTMODE_NEEDSIG); // alias to c:pk_h
+
+
+    // Randomly generated test set that covers the majority of type and node type combinations
+    Test("lltvln:after(1231488000)", "6300676300676300670400046749b1926869516868", TESTMODE_VALID | TESTMODE_NONMAL, 12, 4);
+    Test("uuj:and_v(v:multi(2,03d01115d548e7561b15c38f004d734633687cf4419620095bc5b0f47070afe85a,025601570cb47f238d2b0286db4a990fa0f3ba28d1a319f5e7cf55c2a2444da7cc),after(1231488000))", "6363829263522103d01115d548e7561b15c38f004d734633687cf4419620095bc5b0f47070afe85a21025601570cb47f238d2b0286db4a990fa0f3ba28d1a319f5e7cf55c2a2444da7cc52af0400046749b168670068670068", TESTMODE_VALID | TESTMODE_NONMAL | TESTMODE_NEEDSIG, 14, 6);
+    Test("or_b(un:multi(2,03daed4f2be3a8bf278e70132fb0beb7522f570e144bf615c07e996d443dee8729,024ce119c96e2fa357200b559b2f7dd5a5f02d5290aff74b03f3e471b273211c97),al:older(16))", "63522103daed4f2be3a8bf278e70132fb0beb7522f570e144bf615c07e996d443dee872921024ce119c96e2fa357200b559b2f7dd5a5f02d5290aff74b03f3e471b273211c9752ae926700686b63006760b2686c9b", TESTMODE_VALID, 14, 6);
+    Test("j:and_v(vdv:after(1567547623),older(2016))", "829263766304e7e06e5db169686902e007b268", TESTMODE_VALID | TESTMODE_NONMAL, 11, 2);
+    Test("t:and_v(vu:hash256(131772552c01444cd81360818376a040b7c3b2b7b0a53550ee3edde216cec61b),v:sha256(ec4916dd28fc4c10d78e287ca5d9cc51ee1ae73cbfde08c6b37324cbfaac8bc5))", "6382012088aa20131772552c01444cd81360818376a040b7c3b2b7b0a53550ee3edde216cec61b876700686982012088a820ec4916dd28fc4c10d78e287ca5d9cc51ee1ae73cbfde08c6b37324cbfaac8bc58851", TESTMODE_VALID | TESTMODE_NONMAL, 12, 4);
+    Test("t:andor(multi(3,02d7924d4f7d43ea965a465ae3095ff41131e5946f3c85f79e44adbcf8e27e080e,03fff97bd5755eeea420453a14355235d382f6472f8568a18b2f057a1460297556,02e493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13),v:older(4194305),v:sha256(9267d3dbed802941483f1afa2a6bc68de5f653128aca9bf1461c5d0a3ad36ed2))", "532102d7924d4f7d43ea965a465ae3095ff41131e5946f3c85f79e44adbcf8e27e080e2103fff97bd5755eeea420453a14355235d382f6472f8568a18b2f057a14602975562102e493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd1353ae6482012088a8209267d3dbed802941483f1afa2a6bc68de5f653128aca9bf1461c5d0a3ad36ed2886703010040b2696851", TESTMODE_VALID | TESTMODE_NONMAL, 13, 6);
+    Test("or_d(multi(1,02f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f9),or_b(multi(3,022f01e5e15cca351daff3843fb70f3c2f0a1bdd05e5af888a67784ef3e10a2a01,032fa2104d6b38d11b0230010559879124e42ab8dfeff5ff29dc9cdadd4ecacc3f,03d01115d548e7561b15c38f004d734633687cf4419620095bc5b0f47070afe85a),su:after(500000)))", "512102f9308a019258c31049344f85f89d5229b531c845836f99b08601f113bce036f951ae73645321022f01e5e15cca351daff3843fb70f3c2f0a1bdd05e5af888a67784ef3e10a2a0121032fa2104d6b38d11b0230010559879124e42ab8dfeff5ff29dc9cdadd4ecacc3f2103d01115d548e7561b15c38f004d734633687cf4419620095bc5b0f47070afe85a53ae7c630320a107b16700689b68", TESTMODE_VALID | TESTMODE_NONMAL, 15, 8);
+    Test("or_d(sha256(38df1c1f64a24a77b23393bca50dff872e31edc4f3b5aa3b90ad0b82f4f089b6),and_n(un:after(499999999),older(4194305)))", "82012088a82038df1c1f64a24a77b23393bca50dff872e31edc4f3b5aa3b90ad0b82f4f089b68773646304ff64cd1db19267006864006703010040b26868", TESTMODE_VALID, 16, 2);
+    Test("and_v(or_i(v:multi(2,02c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5,03774ae7f858a9411e5ef4246b70c65aac5649980be5c17891bbec17895da008cb),v:multi(2,03e60fce93b59e9ec53011aabc21c23e97b2a31369b87a5ae9c44ee89e2a6dec0a,025cbdf0646e5db4eaa398f365f2ea7a0e3d419b7e0330e39ce92bddedcac4f9bc)),sha256(d1ec675902ef1633427ca360b290b0b3045a0d9058ddb5e648b4c3c3224c5c68))", "63522102c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee52103774ae7f858a9411e5ef4246b70c65aac5649980be5c17891bbec17895da008cb52af67522103e60fce93b59e9ec53011aabc21c23e97b2a31369b87a5ae9c44ee89e2a6dec0a21025cbdf0646e5db4eaa398f365f2ea7a0e3d419b7e0330e39ce92bddedcac4f9bc52af6882012088a820d1ec675902ef1633427ca360b290b0b3045a0d9058ddb5e648b4c3c3224c5c6887", TESTMODE_VALID | TESTMODE_NONMAL | TESTMODE_NEEDSIG, 11, 6);
+    Test("j:and_b(multi(2,0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798,024ce119c96e2fa357200b559b2f7dd5a5f02d5290aff74b03f3e471b273211c97),s:or_i(older(1),older(4252898)))", "82926352210279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f8179821024ce119c96e2fa357200b559b2f7dd5a5f02d5290aff74b03f3e471b273211c9752ae7c6351b26703e2e440b2689a68", TESTMODE_VALID | TESTMODE_NEEDSIG, 14, 5);
+    Test("and_b(older(16),s:or_d(sha256(e38990d0c7fc009880a9c07c23842e886c6bbdc964ce6bdd5817ad357335ee6f),n:after(1567547623)))", "60b27c82012088a820e38990d0c7fc009880a9c07c23842e886c6bbdc964ce6bdd5817ad357335ee6f87736404e7e06e5db192689a", TESTMODE_VALID, 12, 2);
+    Test("j:and_v(v:hash160(20195b5a3d650c17f0f29f91c33f8f6335193d07),or_d(sha256(96de8fc8c256fa1e1556d41af431cace7dca68707c78dd88c3acab8b17164c47),older(16)))", "82926382012088a91420195b5a3d650c17f0f29f91c33f8f6335193d078882012088a82096de8fc8c256fa1e1556d41af431cace7dca68707c78dd88c3acab8b17164c4787736460b26868", TESTMODE_VALID, 16, 3);
+    Test("and_b(hash256(32ba476771d01e37807990ead8719f08af494723de1d228f2c2c07cc0aa40bac),a:and_b(hash256(131772552c01444cd81360818376a040b7c3b2b7b0a53550ee3edde216cec61b),a:older(1)))", "82012088aa2032ba476771d01e37807990ead8719f08af494723de1d228f2c2c07cc0aa40bac876b82012088aa20131772552c01444cd81360818376a040b7c3b2b7b0a53550ee3edde216cec61b876b51b26c9a6c9a", TESTMODE_VALID | TESTMODE_NONMAL, 15, 3);
+    Test("thresh(2,multi(2,03a0434d9e47f3c86235477c7b1ae6ae5d3442d49b1943c2b752a68e2a47e247c7,036d2b085e9e382ed10b69fc311a03f8641ccfff21574de0927513a49d9a688a00),a:multi(1,036d2b085e9e382ed10b69fc311a03f8641ccfff21574de0927513a49d9a688a00),ac:pk_k(022f01e5e15cca351daff3843fb70f3c2f0a1bdd05e5af888a67784ef3e10a2a01))", "522103a0434d9e47f3c86235477c7b1ae6ae5d3442d49b1943c2b752a68e2a47e247c721036d2b085e9e382ed10b69fc311a03f8641ccfff21574de0927513a49d9a688a0052ae6b5121036d2b085e9e382ed10b69fc311a03f8641ccfff21574de0927513a49d9a688a0051ae6c936b21022f01e5e15cca351daff3843fb70f3c2f0a1bdd05e5af888a67784ef3e10a2a01ac6c935287", TESTMODE_VALID | TESTMODE_NONMAL | TESTMODE_NEEDSIG, 13, 7);
+    Test("and_n(sha256(d1ec675902ef1633427ca360b290b0b3045a0d9058ddb5e648b4c3c3224c5c68),t:or_i(v:older(4252898),v:older(144)))", "82012088a820d1ec675902ef1633427ca360b290b0b3045a0d9058ddb5e648b4c3c3224c5c68876400676303e2e440b26967029000b269685168", TESTMODE_VALID, 14, 3);
+    Test("or_d(d:and_v(v:older(4252898),v:older(4252898)),sha256(38df1c1f64a24a77b23393bca50dff872e31edc4f3b5aa3b90ad0b82f4f089b6))", "766303e2e440b26903e2e440b26968736482012088a82038df1c1f64a24a77b23393bca50dff872e31edc4f3b5aa3b90ad0b82f4f089b68768", TESTMODE_VALID, 14, 3);
+    Test("c:and_v(or_c(sha256(9267d3dbed802941483f1afa2a6bc68de5f653128aca9bf1461c5d0a3ad36ed2),v:multi(1,02c44d12c7065d812e8acf28d7cbb19f9011ecd9e9fdf281b0e6a3b5e87d22e7db)),pk_k(03acd484e2f0c7f65309ad178a9f559abde09796974c57e714c35f110dfc27ccbe))", "82012088a8209267d3dbed802941483f1afa2a6bc68de5f653128aca9bf1461c5d0a3ad36ed28764512102c44d12c7065d812e8acf28d7cbb19f9011ecd9e9fdf281b0e6a3b5e87d22e7db51af682103acd484e2f0c7f65309ad178a9f559abde09796974c57e714c35f110dfc27ccbeac", TESTMODE_VALID | TESTMODE_NEEDSIG, 8, 3);
+    Test("c:and_v(or_c(multi(2,036d2b085e9e382ed10b69fc311a03f8641ccfff21574de0927513a49d9a688a00,02352bbf4a4cdd12564f93fa332ce333301d9ad40271f8107181340aef25be59d5),v:ripemd160(1b0f3c404d12075c68c938f9f60ebea4f74941a0)),pk_k(03fff97bd5755eeea420453a14355235d382f6472f8568a18b2f057a1460297556))", "5221036d2b085e9e382ed10b69fc311a03f8641ccfff21574de0927513a49d9a688a002102352bbf4a4cdd12564f93fa332ce333301d9ad40271f8107181340aef25be59d552ae6482012088a6141b0f3c404d12075c68c938f9f60ebea4f74941a088682103fff97bd5755eeea420453a14355235d382f6472f8568a18b2f057a1460297556ac", TESTMODE_VALID | TESTMODE_NONMAL | TESTMODE_NEEDSIG, 10, 6);
+    Test("and_v(andor(hash256(8a35d9ca92a48eaade6f53a64985e9e2afeb74dcf8acb4c3721e0dc7e4294b25),v:hash256(939894f70e6c3a25da75da0cc2071b4076d9b006563cf635986ada2e93c0d735),v:older(50000)),after(499999999))", "82012088aa208a35d9ca92a48eaade6f53a64985e9e2afeb74dcf8acb4c3721e0dc7e4294b2587640350c300b2696782012088aa20939894f70e6c3a25da75da0cc2071b4076d9b006563cf635986ada2e93c0d735886804ff64cd1db1", TESTMODE_VALID, 14, 3);
+    Test("andor(hash256(5f8d30e655a7ba0d7596bb3ddfb1d2d20390d23b1845000e1e118b3be1b3f040),j:and_v(v:hash160(3a2bff0da9d96868e66abc4427bea4691cf61ccd),older(4194305)),ripemd160(44d90e2d3714c8663b632fcf0f9d5f22192cc4c8))", "82012088aa205f8d30e655a7ba0d7596bb3ddfb1d2d20390d23b1845000e1e118b3be1b3f040876482012088a61444d90e2d3714c8663b632fcf0f9d5f22192cc4c8876782926382012088a9143a2bff0da9d96868e66abc4427bea4691cf61ccd8803010040b26868", TESTMODE_VALID, 20, 3);
+    Test("or_i(c:and_v(v:after(500000),pk_k(02c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5)),sha256(d9147961436944f43cd99d28b2bbddbf452ef872b30c8279e255e7daafc7f946))", "630320a107b1692102c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5ac6782012088a820d9147961436944f43cd99d28b2bbddbf452ef872b30c8279e255e7daafc7f9468768", TESTMODE_VALID | TESTMODE_NONMAL, 10, 3);
+    Test("thresh(2,c:pk_h(025cbdf0646e5db4eaa398f365f2ea7a0e3d419b7e0330e39ce92bddedcac4f9bc),s:sha256(e38990d0c7fc009880a9c07c23842e886c6bbdc964ce6bdd5817ad357335ee6f),a:hash160(dd69735817e0e3f6f826a9238dc2e291184f0131))", "76a9145dedfbf9ea599dd4e3ca6a80b333c472fd0b3f6988ac7c82012088a820e38990d0c7fc009880a9c07c23842e886c6bbdc964ce6bdd5817ad357335ee6f87936b82012088a914dd69735817e0e3f6f826a9238dc2e291184f0131876c935287", TESTMODE_VALID, 18, 5);
+    Test("and_n(sha256(9267d3dbed802941483f1afa2a6bc68de5f653128aca9bf1461c5d0a3ad36ed2),uc:and_v(v:older(144),pk_k(03fe72c435413d33d48ac09c9161ba8b09683215439d62b7940502bda8b202e6ce)))", "82012088a8209267d3dbed802941483f1afa2a6bc68de5f653128aca9bf1461c5d0a3ad36ed28764006763029000b2692103fe72c435413d33d48ac09c9161ba8b09683215439d62b7940502bda8b202e6ceac67006868", TESTMODE_VALID | TESTMODE_NEEDSIG, 13, 4);
+    Test("and_n(c:pk_k(03daed4f2be3a8bf278e70132fb0beb7522f570e144bf615c07e996d443dee8729),and_b(l:older(4252898),a:older(16)))", "2103daed4f2be3a8bf278e70132fb0beb7522f570e144bf615c07e996d443dee8729ac64006763006703e2e440b2686b60b26c9a68", TESTMODE_VALID | TESTMODE_NONMAL | TESTMODE_NEEDSIG | TESTMODE_TIMELOCKMIX, 12, 3);
+    Test("c:or_i(and_v(v:older(16),pk_h(02d7924d4f7d43ea965a465ae3095ff41131e5946f3c85f79e44adbcf8e27e080e)),pk_h(026a245bf6dc698504c89a20cfded60853152b695336c28063b61c65cbd269e6b4))", "6360b26976a9149fc5dbe5efdce10374a4dd4053c93af540211718886776a9142fbd32c8dd59ee7c17e66cb6ebea7e9846c3040f8868ac", TESTMODE_VALID | TESTMODE_NONMAL | TESTMODE_NEEDSIG, 12, 4);
+    Test("or_d(c:pk_h(02e493dbf1c10d80f3581e4904930b1404cc6c13900ee0758474fa94abe8c4cd13),andor(c:pk_k(024ce119c96e2fa357200b559b2f7dd5a5f02d5290aff74b03f3e471b273211c97),older(2016),after(1567547623)))", "76a914c42e7ef92fdb603af844d064faad95db9bcdfd3d88ac736421024ce119c96e2fa357200b559b2f7dd5a5f02d5290aff74b03f3e471b273211c97ac6404e7e06e5db16702e007b26868", TESTMODE_VALID | TESTMODE_NONMAL, 13, 4);
+    Test("c:andor(ripemd160(6ad07d21fd5dfc646f0b30577045ce201616b9ba),pk_h(02d7924d4f7d43ea965a465ae3095ff41131e5946f3c85f79e44adbcf8e27e080e),and_v(v:hash256(8a35d9ca92a48eaade6f53a64985e9e2afeb74dcf8acb4c3721e0dc7e4294b25),pk_h(03d01115d548e7561b15c38f004d734633687cf4419620095bc5b0f47070afe85a)))", "82012088a6146ad07d21fd5dfc646f0b30577045ce201616b9ba876482012088aa208a35d9ca92a48eaade6f53a64985e9e2afeb74dcf8acb4c3721e0dc7e4294b258876a914dd100be7d9aea5721158ebde6d6a1fd8fff93bb1886776a9149fc5dbe5efdce10374a4dd4053c93af5402117188868ac", TESTMODE_VALID | TESTMODE_NEEDSIG, 18, 4);
+    Test("c:andor(u:ripemd160(6ad07d21fd5dfc646f0b30577045ce201616b9ba),pk_h(03daed4f2be3a8bf278e70132fb0beb7522f570e144bf615c07e996d443dee8729),or_i(pk_h(022f01e5e15cca351daff3843fb70f3c2f0a1bdd05e5af888a67784ef3e10a2a01),pk_h(0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798)))", "6382012088a6146ad07d21fd5dfc646f0b30577045ce201616b9ba87670068646376a9149652d86bedf43ad264362e6e6eba6eb764508127886776a914751e76e8199196d454941c45d1b3a323f1433bd688686776a91420d637c1a6404d2227f3561fdbaff5a680dba6488868ac", TESTMODE_VALID | TESTMODE_NEEDSIG, 23, 5);
+    Test("c:or_i(andor(c:pk_h(03d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65),pk_h(022f01e5e15cca351daff3843fb70f3c2f0a1bdd05e5af888a67784ef3e10a2a01),pk_h(02c6047f9441ed7d6d3045406e95c07cd85c778e4b8cef3ca7abac09b95c709ee5)),pk_k(02d7924d4f7d43ea965a465ae3095ff41131e5946f3c85f79e44adbcf8e27e080e))", "6376a914fcd35ddacad9f2d5be5e464639441c6065e6955d88ac6476a91406afd46bcdfd22ef94ac122aa11f241244a37ecc886776a9149652d86bedf43ad264362e6e6eba6eb7645081278868672102d7924d4f7d43ea965a465ae3095ff41131e5946f3c85f79e44adbcf8e27e080e68ac", TESTMODE_VALID | TESTMODE_NONMAL | TESTMODE_NEEDSIG, 17, 6);
+    Test("thresh(1,c:pk_k(03d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65),altv:after(1000000000),altv:after(100))", "2103d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65ac6b6300670400ca9a3bb16951686c936b6300670164b16951686c935187", TESTMODE_VALID, 18, 4);
+    Test("thresh(2,c:pk_k(03d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65),ac:pk_k(03fff97bd5755eeea420453a14355235d382f6472f8568a18b2f057a1460297556),altv:after(1000000000),altv:after(100))", "2103d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65ac6b2103fff97bd5755eeea420453a14355235d382f6472f8568a18b2f057a1460297556ac6c936b6300670400ca9a3bb16951686c936b6300670164b16951686c935287", TESTMODE_VALID | TESTMODE_NONMAL | TESTMODE_TIMELOCKMIX, 22, 5);
+
+    // Misc unit tests
+    // A Script with a non minimal push is invalid
+    std::vector<unsigned char> nonminpush = ParseHex("0000210232780000feff00ffffffffffff21ff005f00ae21ae00000000060602060406564c2102320000060900fe00005f00ae21ae00100000060606060606000000000000000000000000000000000000000000000000000000000000000000");
+    const CScript nonminpush_script(nonminpush.begin(), nonminpush.end());
+    BOOST_CHECK(miniscript::FromScript(nonminpush_script, CONVERTER) == nullptr);
+    // A non-minimal VERIFY (<key> CHECKSIG VERIFY 1)
+    std::vector<unsigned char> nonminverify = ParseHex("2103a0434d9e47f3c86235477c7b1ae6ae5d3442d49b1943c2b752a68e2a47e247c7ac6951");
+    const CScript nonminverify_script(nonminverify.begin(), nonminverify.end());
+    BOOST_CHECK(miniscript::FromScript(nonminverify_script, CONVERTER) == nullptr);
+    // A threshold as large as the number of subs is valid.
+    Test("thresh(2,c:pk_k(03d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65),altv:after(100))", "2103d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65ac6b6300670164b16951686c935287", TESTMODE_VALID | TESTMODE_NEEDSIG | TESTMODE_NONMAL);
+    // A threshold of 1 is valid.
+    Test("thresh(1,c:pk_k(03d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65),sc:pk_k(03fff97bd5755eeea420453a14355235d382f6472f8568a18b2f057a1460297556))", "2103d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65ac7c2103fff97bd5755eeea420453a14355235d382f6472f8568a18b2f057a1460297556ac935187", TESTMODE_VALID | TESTMODE_NEEDSIG | TESTMODE_NONMAL);
+    // A threshold with a k larger than the number of subs is invalid
+    Test("thresh(3,c:pk_k(03d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65),sc:pk_k(03fff97bd5755eeea420453a14355235d382f6472f8568a18b2f057a1460297556))", "2103d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65ac7c2103fff97bd5755eeea420453a14355235d382f6472f8568a18b2f057a1460297556ac935187", TESTMODE_INVALID);
+    // A threshold with a k null is invalid
+    Test("thresh(0,c:pk_k(03d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65),sc:pk_k(03fff97bd5755eeea420453a14355235d382f6472f8568a18b2f057a1460297556))", "2103d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65ac7c2103fff97bd5755eeea420453a14355235d382f6472f8568a18b2f057a1460297556ac935187", TESTMODE_INVALID);
+    // For CHECKMULTISIG the OP cost is the number of keys, but the stack size is the number of sigs (+1)
+    const auto ms_multi = miniscript::FromString("multi(1,03d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65,03fff97bd5755eeea420453a14355235d382f6472f8568a18b2f057a1460297556,0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798)", CONVERTER);
+    BOOST_CHECK(ms_multi);
+    BOOST_CHECK_EQUAL(ms_multi->GetOps(), 4); // 3 pubkeys + CMS
+    BOOST_CHECK_EQUAL(ms_multi->GetStackSize(), 3); // 1 sig + dummy elem + script push
+
+    // Timelock tests
+    Test("after(100)", "?", TESTMODE_VALID | TESTMODE_NONMAL); // only heightlock
+    Test("after(1000000000)", "?", TESTMODE_VALID | TESTMODE_NONMAL); // only timelock
+    Test("or_b(l:after(100),al:after(1000000000))", "?", TESTMODE_VALID); // or_b(timelock, heighlock) valid
+    Test("and_b(after(100),a:after(1000000000))", "?", TESTMODE_VALID | TESTMODE_NONMAL | TESTMODE_TIMELOCKMIX); // and_b(timelock, heighlock) invalid
+    /* This is correctly detected as non-malleable but for the wrong reason. The type system assumes that branches 1 and 2
+       can be spent together to create a non-malleble witness, but because of mixing of timelocks they cannot be spent together.
+       But since exactly one of the two after's can be satisfied, the witness involving the key cannot be malleated.
+    */
+    Test("thresh(2,ltv:after(1000000000),altv:after(100),a:pk(03d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65))", "?", TESTMODE_VALID | TESTMODE_TIMELOCKMIX | TESTMODE_NONMAL); // thresh with k = 2
+    // This is actually non-malleable in practice, but we cannot detect it in type system. See above rationale
+    Test("thresh(1,c:pk_k(03d30199d74fb5a22d47b6e054e2f378cedacffcb89904a61d75d0dbd407143e65),altv:after(1000000000),altv:after(100))", "?", TESTMODE_VALID); // thresh with k = 1
+
+
+    g_testdata.reset();
+}
+
+BOOST_AUTO_TEST_SUITE_END()