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#include <script/miniscript.h>
6
7#include <primitives/transaction.h>
8#include <script/script.h>
9#include <script/solver.h>
10#include <util/check.h>
11#include <util/vector.h>
12
13#include <limits>
14#include <vector>
15
16namespace miniscript {
17namespace internal {
18
19Type SanitizeType(Type e) {
20    int num_types = (e << "K"_mst) + (e << "V"_mst) + (e << "B"_mst) + (e << "W"_mst);
21    if (num_types == 0) return ""_mst; // No valid type, don't care about the rest
22    CHECK_NONFATAL(num_types == 1); // K, V, B, W all conflict with each other
23    CHECK_NONFATAL(!(e << "z"_mst) || !(e << "o"_mst)); // z conflicts with o
24    CHECK_NONFATAL(!(e << "n"_mst) || !(e << "z"_mst)); // n conflicts with z
25    CHECK_NONFATAL(!(e << "n"_mst) || !(e << "W"_mst)); // n conflicts with W
26    CHECK_NONFATAL(!(e << "V"_mst) || !(e << "d"_mst)); // V conflicts with d
27    CHECK_NONFATAL(!(e << "K"_mst) ||  (e << "u"_mst)); // K implies u
28    CHECK_NONFATAL(!(e << "V"_mst) || !(e << "u"_mst)); // V conflicts with u
29    CHECK_NONFATAL(!(e << "e"_mst) || !(e << "f"_mst)); // e conflicts with f
30    CHECK_NONFATAL(!(e << "e"_mst) ||  (e << "d"_mst)); // e implies d
31    CHECK_NONFATAL(!(e << "V"_mst) || !(e << "e"_mst)); // V conflicts with e
32    CHECK_NONFATAL(!(e << "d"_mst) || !(e << "f"_mst)); // d conflicts with f
33    CHECK_NONFATAL(!(e << "V"_mst) ||  (e << "f"_mst)); // V implies f
34    CHECK_NONFATAL(!(e << "K"_mst) ||  (e << "s"_mst)); // K implies s
35    CHECK_NONFATAL(!(e << "z"_mst) ||  (e << "m"_mst)); // z implies m
36    return e;
37}
38
39Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Type>& sub_types, uint32_t k,
40                 size_t data_size, size_t n_subs, size_t n_keys, MiniscriptContext ms_ctx) {
41    // Sanity check on data
42    if (fragment == Fragment::SHA256 || fragment == Fragment::HASH256) {
43        CHECK_NONFATAL(data_size == 32);
44    } else if (fragment == Fragment::RIPEMD160 || fragment == Fragment::HASH160) {
45        CHECK_NONFATAL(data_size == 20);
46    } else {
47        CHECK_NONFATAL(data_size == 0);
48    }
49    // Sanity check on k
50    if (fragment == Fragment::OLDER || fragment == Fragment::AFTER) {
51        CHECK_NONFATAL(k >= 1 && k < 0x80000000UL);
52    } else if (fragment == Fragment::MULTI || fragment == Fragment::MULTI_A) {
53        CHECK_NONFATAL(k >= 1 && k <= n_keys);
54    } else if (fragment == Fragment::THRESH) {
55        CHECK_NONFATAL(k >= 1 && k <= n_subs);
56    } else {
57        CHECK_NONFATAL(k == 0);
58    }
59    // Sanity check on subs
60    if (fragment == Fragment::AND_V || fragment == Fragment::AND_B || fragment == Fragment::OR_B ||
61        fragment == Fragment::OR_C || fragment == Fragment::OR_I || fragment == Fragment::OR_D) {
62        CHECK_NONFATAL(n_subs == 2);
63    } else if (fragment == Fragment::ANDOR) {
64        CHECK_NONFATAL(n_subs == 3);
65    } else if (fragment == Fragment::WRAP_A || fragment == Fragment::WRAP_S || fragment == Fragment::WRAP_C ||
66               fragment == Fragment::WRAP_D || fragment == Fragment::WRAP_V || fragment == Fragment::WRAP_J ||
67               fragment == Fragment::WRAP_N) {
68        CHECK_NONFATAL(n_subs == 1);
69    } else if (fragment != Fragment::THRESH) {
70        CHECK_NONFATAL(n_subs == 0);
71    }
72    // Sanity check on keys
73    if (fragment == Fragment::PK_K || fragment == Fragment::PK_H) {
74        CHECK_NONFATAL(n_keys == 1);
75    } else if (fragment == Fragment::MULTI) {
76        CHECK_NONFATAL(n_keys >= 1 && n_keys <= MAX_PUBKEYS_PER_MULTISIG);
77        CHECK_NONFATAL(!IsTapscript(ms_ctx));
78    } else if (fragment == Fragment::MULTI_A) {
79        CHECK_NONFATAL(n_keys >= 1 && n_keys <= MAX_PUBKEYS_PER_MULTI_A);
80        CHECK_NONFATAL(IsTapscript(ms_ctx));
81    } else {
82        CHECK_NONFATAL(n_keys == 0);
83    }
84
85    // Below is the per-fragment logic for computing the expression types.
86    // It heavily relies on Type's << operator (where "X << a_mst" means
87    // "X has all properties listed in a").
88    switch (fragment) {
89        case Fragment::PK_K: return "Konudemsxk"_mst;
90        case Fragment::PK_H: return "Knudemsxk"_mst;
91        case Fragment::OLDER: return
92            "g"_mst.If(k & CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG) |
93            "h"_mst.If(!(k & CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG)) |
94            "Bzfmxk"_mst;
95        case Fragment::AFTER: return
96            "i"_mst.If(k >= LOCKTIME_THRESHOLD) |
97            "j"_mst.If(k < LOCKTIME_THRESHOLD) |
98            "Bzfmxk"_mst;
99        case Fragment::SHA256: return "Bonudmk"_mst;
100        case Fragment::RIPEMD160: return "Bonudmk"_mst;
101        case Fragment::HASH256: return "Bonudmk"_mst;
102        case Fragment::HASH160: return "Bonudmk"_mst;
103        case Fragment::JUST_1: return "Bzufmxk"_mst;
104        case Fragment::JUST_0: return "Bzudemsxk"_mst;
105        case Fragment::WRAP_A: return
106            "W"_mst.If(x << "B"_mst) | // W=B_x
107            (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
108            (x & "udfems"_mst) | // u=u_x, d=d_x, f=f_x, e=e_x, m=m_x, s=s_x
109            "x"_mst; // x
110        case Fragment::WRAP_S: return
111            "W"_mst.If(x << "Bo"_mst) | // W=B_x*o_x
112            (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
113            (x & "udfemsx"_mst); // u=u_x, d=d_x, f=f_x, e=e_x, m=m_x, s=s_x, x=x_x
114        case Fragment::WRAP_C: return
115            "B"_mst.If(x << "K"_mst) | // B=K_x
116            (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
117            (x & "ondfem"_mst) | // o=o_x, n=n_x, d=d_x, f=f_x, e=e_x, m=m_x
118            "us"_mst; // u, s
119        case Fragment::WRAP_D: return
120            "B"_mst.If(x << "Vz"_mst) | // B=V_x*z_x
121            "o"_mst.If(x << "z"_mst) | // o=z_x
122            "e"_mst.If(x << "f"_mst) | // e=f_x
123            (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
124            (x & "ms"_mst) | // m=m_x, s=s_x
125            // NOTE: 'd:' is 'u' under Tapscript but not P2WSH as MINIMALIF is only a policy rule there.
126            "u"_mst.If(IsTapscript(ms_ctx)) |
127            "ndx"_mst; // n, d, x
128        case Fragment::WRAP_V: return
129            "V"_mst.If(x << "B"_mst) | // V=B_x
130            (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
131            (x & "zonms"_mst) | // z=z_x, o=o_x, n=n_x, m=m_x, s=s_x
132            "fx"_mst; // f, x
133        case Fragment::WRAP_J: return
134            "B"_mst.If(x << "Bn"_mst) | // B=B_x*n_x
135            "e"_mst.If(x << "f"_mst) | // e=f_x
136            (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
137            (x & "oums"_mst) | // o=o_x, u=u_x, m=m_x, s=s_x
138            "ndx"_mst; // n, d, x
139        case Fragment::WRAP_N: return
140            (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
141            (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
142            "ux"_mst; // u, x
143        case Fragment::AND_V: return
144            (y & "KVB"_mst).If(x << "V"_mst) | // B=V_x*B_y, V=V_x*V_y, K=V_x*K_y
145            (x & "n"_mst) | (y & "n"_mst).If(x << "z"_mst) | // n=n_x+z_x*n_y
146            ((x | y) & "o"_mst).If((x | y) << "z"_mst) | // o=o_x*z_y+z_x*o_y
147            (x & y & "mz"_mst) | // m=m_x*m_y, z=z_x*z_y
148            ((x | y) & "s"_mst) | // s=s_x+s_y
149            "f"_mst.If((y << "f"_mst) || (x << "s"_mst)) | // f=f_y+s_x
150            (y & "ux"_mst) | // u=u_y, x=x_y
151            ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
152            "k"_mst.If(((x & y) << "k"_mst) &&
153                !(((x << "g"_mst) && (y << "h"_mst)) ||
154                ((x << "h"_mst) && (y << "g"_mst)) ||
155                ((x << "i"_mst) && (y << "j"_mst)) ||
156                ((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)
157        case Fragment::AND_B: return
158            (x & "B"_mst).If(y << "W"_mst) | // B=B_x*W_y
159            ((x | y) & "o"_mst).If((x | y) << "z"_mst) | // o=o_x*z_y+z_x*o_y
160            (x & "n"_mst) | (y & "n"_mst).If(x << "z"_mst) | // n=n_x+z_x*n_y
161            (x & y & "e"_mst).If((x & y) << "s"_mst) | // e=e_x*e_y*s_x*s_y
162            (x & y & "dzm"_mst) | // d=d_x*d_y, z=z_x*z_y, m=m_x*m_y
163            "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
164            ((x | y) & "s"_mst) | // s=s_x+s_y
165            "ux"_mst | // u, x
166            ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
167            "k"_mst.If(((x & y) << "k"_mst) &&
168                !(((x << "g"_mst) && (y << "h"_mst)) ||
169                ((x << "h"_mst) && (y << "g"_mst)) ||
170                ((x << "i"_mst) && (y << "j"_mst)) ||
171                ((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)
172        case Fragment::OR_B: return
173            "B"_mst.If(x << "Bd"_mst && y << "Wd"_mst) | // B=B_x*d_x*W_x*d_y
174            ((x | y) & "o"_mst).If((x | y) << "z"_mst) | // o=o_x*z_y+z_x*o_y
175            (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)
176            (x & y & "zse"_mst) | // z=z_x*z_y, s=s_x*s_y, e=e_x*e_y
177            "dux"_mst | // d, u, x
178            ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
179            (x & y & "k"_mst); // k=k_x*k_y
180        case Fragment::OR_D: return
181            (y & "B"_mst).If(x << "Bdu"_mst) | // B=B_y*B_x*d_x*u_x
182            (x & "o"_mst).If(y << "z"_mst) | // o=o_x*z_y
183            (x & y & "m"_mst).If(x << "e"_mst && (x | y) << "s"_mst) | // m=m_x*m_y*e_x*(s_x+s_y)
184            (x & y & "zs"_mst) | // z=z_x*z_y, s=s_x*s_y
185            (y & "ufde"_mst) | // u=u_y, f=f_y, d=d_y, e=e_y
186            "x"_mst | // x
187            ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
188            (x & y & "k"_mst); // k=k_x*k_y
189        case Fragment::OR_C: return
190            (y & "V"_mst).If(x << "Bdu"_mst) | // V=V_y*B_x*u_x*d_x
191            (x & "o"_mst).If(y << "z"_mst) | // o=o_x*z_y
192            (x & y & "m"_mst).If(x << "e"_mst && (x | y) << "s"_mst) | // m=m_x*m_y*e_x*(s_x+s_y)
193            (x & y & "zs"_mst) | // z=z_x*z_y, s=s_x*s_y
194            "fx"_mst | // f, x
195            ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
196            (x & y & "k"_mst); // k=k_x*k_y
197        case Fragment::OR_I: return
198            (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
199            "o"_mst.If((x & y) << "z"_mst) | // o=z_x*z_y
200            ((x | y) & "e"_mst).If((x | y) << "f"_mst) | // e=e_x*f_y+f_x*e_y
201            (x & y & "m"_mst).If((x | y) << "s"_mst) | // m=m_x*m_y*(s_x+s_y)
202            ((x | y) & "d"_mst) | // d=d_x+d_y
203            "x"_mst | // x
204            ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
205            (x & y & "k"_mst); // k=k_x*k_y
206        case Fragment::ANDOR: return
207            (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
208            (x & y & z & "z"_mst) | // z=z_x*z_y*z_z
209            ((x | (y & z)) & "o"_mst).If((x | (y & z)) << "z"_mst) | // o=o_x*z_y*z_z+z_x*o_y*o_z
210            (y & z & "u"_mst) | // u=u_y*u_z
211            (z & "f"_mst).If((x << "s"_mst) || (y << "f"_mst)) | // f=(s_x+f_y)*f_z
212            (z & "d"_mst) | // d=d_z
213            (z & "e"_mst).If(x << "s"_mst || y << "f"_mst) | // e=e_z*(s_x+f_y)
214            (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)
215            (z & (x | y) & "s"_mst) | // s=s_z*(s_x+s_y)
216            "x"_mst | // x
217            ((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
218            "k"_mst.If(((x & y & z) << "k"_mst) &&
219                !(((x << "g"_mst) && (y << "h"_mst)) ||
220                ((x << "h"_mst) && (y << "g"_mst)) ||
221                ((x << "i"_mst) && (y << "j"_mst)) ||
222                ((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)
223        case Fragment::MULTI: {
224            return "Bnudemsk"_mst;
225        }
226        case Fragment::MULTI_A: {
227            return "Budemsk"_mst;
228        }
229        case Fragment::THRESH: {
230            bool all_e = true;
231            bool all_m = true;
232            uint32_t args = 0;
233            uint32_t num_s = 0;
234            Type acc_tl = "k"_mst;
235            for (size_t i = 0; i < sub_types.size(); ++i) {
236                Type t = sub_types[i];
237                if (!(t << (i ? "Wdu"_mst : "Bdu"_mst))) return ""_mst; // Require Bdu, Wdu, Wdu, ...
238                if (!(t << "e"_mst)) all_e = false;
239                if (!(t << "m"_mst)) all_m = false;
240                if (t << "s"_mst) num_s += 1;
241                args += (t << "z"_mst) ? 0 : (t << "o"_mst) ? 1 : 2;
242                acc_tl = ((acc_tl | t) & "ghij"_mst) |
243                    // Thresh contains a combination of timelocks if it has threshold > 1 and
244                    // it contains two different children that have different types of timelocks
245                    // Note how if any of the children don't have "k", the parent also does not have "k"
246                    "k"_mst.If(((acc_tl & t) << "k"_mst) && ((k <= 1) ||
247                        ((k > 1) && !(((acc_tl << "g"_mst) && (t << "h"_mst)) ||
248                        ((acc_tl << "h"_mst) && (t << "g"_mst)) ||
249                        ((acc_tl << "i"_mst) && (t << "j"_mst)) ||
250                        ((acc_tl << "j"_mst) && (t << "i"_mst))))));