1// Copyright (c) 2019-present The Bitcoin Core developers
2// Distributed under the MIT software license, see the accompanying
3// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5#ifndef BITCOIN_SCRIPT_MINISCRIPT_H
6#define BITCOIN_SCRIPT_MINISCRIPT_H
7
8#include <consensus/consensus.h>
9#include <crypto/hex_base.h>
10#include <policy/policy.h>
11#include <script/interpreter.h>
12#include <script/parsing.h>
13#include <script/script.h>
14#include <serialize.h>
15#include <util/check.h>
16#include <util/strencodings.h>
17#include <util/string.h>
18#include <util/vector.h>
19
20#include <algorithm>
21#include <concepts>
22#include <cstddef>
23#include <cstdint>
24#include <functional>
25#include <memory>
26#include <optional>
27#include <set>
28#include <span>
29#include <stdexcept>
30#include <string>
31#include <string_view>
32#include <tuple>
33#include <utility>
34#include <variant>
35#include <vector>
36
37namespace miniscript {
38
39/** This type encapsulates the miniscript type system properties.
40 *
41 * Every miniscript expression is one of 4 basic types, and additionally has
42 * a number of boolean type properties.
43 *
44 * The basic types are:
45 * - "B" Base:
46 *   - Takes its inputs from the top of the stack.
47 *   - When satisfied, pushes a nonzero value of up to 4 bytes onto the stack.
48 *   - When dissatisfied, pushes a 0 onto the stack.
49 *   - This is used for most expressions, and required for the top level one.
50 *   - For example: older(n) = <n> OP_CHECKSEQUENCEVERIFY.
51 * - "V" Verify:
52 *   - Takes its inputs from the top of the stack.
53 *   - When satisfied, pushes nothing.
54 *   - Cannot be dissatisfied.
55 *   - This can be obtained by adding an OP_VERIFY to a B, modifying the last opcode
56 *     of a B to its -VERIFY version (only for OP_CHECKSIG, OP_CHECKSIGVERIFY,
57 *     OP_NUMEQUAL and OP_EQUAL), or by combining a V fragment under some conditions.
58 *   - For example vc:pk_k(key) = <key> OP_CHECKSIGVERIFY
59 * - "K" Key:
60 *   - Takes its inputs from the top of the stack.
61 *   - Becomes a B when followed by OP_CHECKSIG.
62 *   - Always pushes a public key onto the stack, for which a signature is to be
63 *     provided to satisfy the expression.
64 *   - For example pk_h(key) = OP_DUP OP_HASH160 <Hash160(key)> OP_EQUALVERIFY
65 * - "W" Wrapped:
66 *   - Takes its input from one below the top of the stack.
67 *   - When satisfied, pushes a nonzero value (like B) on top of the stack, or one below.
68 *   - When dissatisfied, pushes 0 op top of the stack or one below.
69 *   - Is always "OP_SWAP [B]" or "OP_TOALTSTACK [B] OP_FROMALTSTACK".
70 *   - For example sc:pk_k(key) = OP_SWAP <key> OP_CHECKSIG
71 *
72 * There are type properties that help reasoning about correctness:
73 * - "z" Zero-arg:
74 *   - Is known to always consume exactly 0 stack elements.
75 *   - For example after(n) = <n> OP_CHECKLOCKTIMEVERIFY
76 * - "o" One-arg:
77 *   - Is known to always consume exactly 1 stack element.
78 *   - Conflicts with property 'z'
79 *   - For example sha256(hash) = OP_SIZE 32 OP_EQUALVERIFY OP_SHA256 <hash> OP_EQUAL
80 * - "n" Nonzero:
81 *   - For every way this expression can be satisfied, a satisfaction exists that never needs
82 *     a zero top stack element.
83 *   - Conflicts with property 'z' and with type 'W'.
84 * - "d" Dissatisfiable:
85 *   - There is an easy way to construct a dissatisfaction for this expression.
86 *   - Conflicts with type 'V'.
87 * - "u" Unit:
88 *   - In case of satisfaction, an exact 1 is put on the stack (rather than just nonzero).
89 *   - Conflicts with type 'V'.
90 *
91 * Additional type properties help reasoning about nonmalleability:
92 * - "e" Expression:
93 *   - This implies property 'd', but the dissatisfaction is nonmalleable.
94 *   - This generally requires 'e' for all subexpressions which are invoked for that
95 *     dissatisfaction, and property 'f' for the unexecuted subexpressions in that case.
96 *   - Conflicts with type 'V'.
97 * - "f" Forced:
98 *   - Dissatisfactions (if any) for this expression always involve at least one signature.
99 *   - Is always true for type 'V'.
100 * - "s" Safe:
101 *   - Satisfactions for this expression always involve at least one signature.
102 * - "m" Nonmalleable:
103 *   - For every way this expression can be satisfied (which may be none),
104 *     a nonmalleable satisfaction exists.
105 *   - This generally requires 'm' for all subexpressions, and 'e' for all subexpressions
106 *     which are dissatisfied when satisfying the parent.
107 *
108 * One type property is an implementation detail:
109 * - "x" Expensive verify:
110 *   - Expressions with this property have a script whose last opcode is not EQUAL, CHECKSIG, or CHECKMULTISIG.
111 *   - Not having this property means that it can be converted to a V at no cost (by switching to the
112 *     -VERIFY version of the last opcode).
113 *
114 * Five more type properties for representing timelock information. Spend paths
115 * in miniscripts containing conflicting timelocks and heightlocks cannot be spent together.
116 * This helps users detect if miniscript does not match the semantic behaviour the
117 * user expects.
118 * - "g" Whether the branch contains a relative time timelock
119 * - "h" Whether the branch contains a relative height timelock
120 * - "i" Whether the branch contains an absolute time timelock
121 * - "j" Whether the branch contains an absolute height timelock
122 * - "k"
123 *   - Whether all satisfactions of this expression don't contain a mix of heightlock and timelock
124 *     of the same type.
125 *   - If the miniscript does not have the "k" property, the miniscript template will not match
126 *     the user expectation of the corresponding spending policy.
127 * For each of these properties the subset rule holds: an expression with properties X, Y, and Z, is also
128 * valid in places where an X, a Y, a Z, an XY, ... is expected.
129*/
130class Type {
131    //! Internal bitmap of properties (see ""_mst operator for details).
132    uint32_t m_flags;
133
134    //! Internal constructor used by the ""_mst operator.
135    explicit constexpr Type(uint32_t flags) : m_flags(flags) {}
136
137public:
138    //! The only way to publicly construct a Type is using this literal operator.
139    friend consteval Type operator""_mst(const char* c, size_t l);
140
141    //! Compute the type with the union of properties.
142    constexpr Type operator|(Type x) const { return Type(m_flags | x.m_flags); }
143
144    //! Compute the type with the intersection of properties.
145    constexpr Type operator&(Type x) const { return Type(m_flags & x.m_flags); }
146
147    //! Check whether the left hand's properties are superset of the right's (= left is a subtype of right).
148    constexpr bool operator<<(Type x) const { return (x.m_flags & ~m_flags) == 0; }
149
150    //! Comparison operator to enable use in sets/maps (total ordering incompatible with <<).
151    constexpr bool operator<(Type x) const { return m_flags < x.m_flags; }
152
153    //! Equality operator.
154    constexpr bool operator==(Type x) const { return m_flags == x.m_flags; }
155
156    //! The empty type if x is false, itself otherwise.
157    constexpr Type If(bool x) const { return Type(x ? m_flags : 0); }
158};
159
160//! Literal operator to construct Type objects.
161inline consteval Type operator""_mst(const char* c, size_t l)
162{
163    Type typ{0};
164
165    for (const char *p = c; p < c + l; p++) {
166        typ = typ | Type(
167            *p == 'B' ? 1 << 0 : // Base type
168            *p == 'V' ? 1 << 1 : // Verify type
169            *p == 'K' ? 1 << 2 : // Key type
170            *p == 'W' ? 1 << 3 : // Wrapped type
171            *p == 'z' ? 1 << 4 : // Zero-arg property
172            *p == 'o' ? 1 << 5 : // One-arg property
173            *p == 'n' ? 1 << 6 : // Nonzero arg property
174            *p == 'd' ? 1 << 7 : // Dissatisfiable property
175            *p == 'u' ? 1 << 8 : // Unit property
176            *p == 'e' ? 1 << 9 : // Expression property
177            *p == 'f' ? 1 << 10 : // Forced property
178            *p == 's' ? 1 << 11 : // Safe property
179            *p == 'm' ? 1 << 12 : // Nonmalleable property
180            *p == 'x' ? 1 << 13 : // Expensive verify
181            *p == 'g' ? 1 << 14 : // older: contains relative time timelock   (csv_time)
182            *p == 'h' ? 1 << 15 : // older: contains relative height timelock (csv_height)
183            *p == 'i' ? 1 << 16 : // after: contains time timelock   (cltv_time)
184            *p == 'j' ? 1 << 17 : // after: contains height timelock   (cltv_height)
185            *p == 'k' ? 1 << 18 : // does not contain a combination of height and time locks
186            (throw std::logic_error("Unknown character in _mst literal"), 0)
187        );
188    }
189
190    return typ;
191}
192
193using Opcode = std::pair<opcodetype, std::vector<unsigned char>>;
194
195template<typename Key> class Node;
196
197//! Unordered traversal of a miniscript node tree.
198template <typename Key, std::invocable<const Node<Key>&> Fn>
199void ForEachNode(const Node<Key>& root, Fn&& fn)
200{
201    std::vector<std::reference_wrapper<const Node<Key>>> stack{root};
202    while (!stack.empty()) {
203        const Node<Key>& node = stack.back();
204        std::invoke(fn, node);
205        stack.pop_back();
206        for (const auto& sub : node.Subs()) {
207            stack.emplace_back(sub);
208        }
209    }
210}
211
212//! The different node types in miniscript.
213enum class Fragment {
214    JUST_0,    //!< OP_0
215    JUST_1,    //!< OP_1
216    PK_K,      //!< [key]
217    PK_H,      //!< OP_DUP OP_HASH160 [keyhash] OP_EQUALVERIFY
218    OLDER,     //!< [n] OP_CHECKSEQUENCEVERIFY
219    AFTER,     //!< [n] OP_CHECKLOCKTIMEVERIFY
220    SHA256,    //!< OP_SIZE 32 OP_EQUALVERIFY OP_SHA256 [hash] OP_EQUAL
221    HASH256,   //!< OP_SIZE 32 OP_EQUALVERIFY OP_HASH256 [hash] OP_EQUAL
222    RIPEMD160, //!< OP_SIZE 32 OP_EQUALVERIFY OP_RIPEMD160 [hash] OP_EQUAL
223    HASH160,   //!< OP_SIZE 32 OP_EQUALVERIFY OP_HASH160 [hash] OP_EQUAL
224    WRAP_A,    //!< OP_TOALTSTACK [X] OP_FROMALTSTACK
225    WRAP_S,    //!< OP_SWAP [X]
226    WRAP_C,    //!< [X] OP_CHECKSIG
227    WRAP_D,    //!< OP_DUP OP_IF [X] OP_ENDIF
228    WRAP_V,    //!< [X] OP_VERIFY (or -VERIFY version of last opcode in X)
229    WRAP_J,    //!< OP_SIZE OP_0NOTEQUAL OP_IF [X] OP_ENDIF
230    WRAP_N,    //!< [X] OP_0NOTEQUAL
231    AND_V,     //!< [X] [Y]
232    AND_B,     //!< [X] [Y] OP_BOOLAND
233    OR_B,      //!< [X] [Y] OP_BOOLOR
234    OR_C,      //!< [X] OP_NOTIF [Y] OP_ENDIF
235    OR_D,      //!< [X] OP_IFDUP OP_NOTIF [Y] OP_ENDIF
236    OR_I,      //!< OP_IF [X] OP_ELSE [Y] OP_ENDIF
237    ANDOR,     //!< [X] OP_NOTIF [Z] OP_ELSE [Y] OP_ENDIF
238    THRESH,    //!< [X1] ([Xn] OP_ADD)* [k] OP_EQUAL
239    MULTI,     //!< [k] [key_n]* [n] OP_CHECKMULTISIG (only available within P2WSH context)
240    MULTI_A,   //!< [key_0] OP_CHECKSIG ([key_n] OP_CHECKSIGADD)* [k] OP_NUMEQUAL (only within Tapscript ctx)
241    // AND_N(X,Y) is represented as ANDOR(X,Y,0)
242    // WRAP_T(X) is represented as AND_V(X,1)
243    // WRAP_L(X) is represented as OR_I(0,X)
244    // WRAP_U(X) is represented as OR_I(X,0)
245};
246
247enum class Availability {
248    NO,
249    YES,
250    MAYBE,