Line data Source code
1 : // Copyright (c) 2019 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 <string>
6 : #include <vector>
7 : #include <script/script.h>
8 : #include <script/standard.h>
9 : #include <script/miniscript.h>
10 :
11 : #include <assert.h>
12 :
13 : namespace miniscript {
14 : namespace internal {
15 :
16 1080 : Type SanitizeType(Type e) {
17 1080 : int num_types = (e << "K"_mst) + (e << "V"_mst) + (e << "B"_mst) + (e << "W"_mst);
18 1080 : if (num_types == 0) return ""_mst; // No valid type, don't care about the rest
19 1049 : assert(num_types == 1); // K, V, B, W all conflict with each other
20 1049 : assert(!(e << "z"_mst) || !(e << "o"_mst)); // z conflicts with o
21 1049 : assert(!(e << "n"_mst) || !(e << "z"_mst)); // n conflicts with z
22 1049 : assert(!(e << "n"_mst) || !(e << "W"_mst)); // n conflicts with W
23 1049 : assert(!(e << "V"_mst) || !(e << "d"_mst)); // V conflicts with d
24 1049 : assert(!(e << "K"_mst) || (e << "u"_mst)); // K implies u
25 1049 : assert(!(e << "V"_mst) || !(e << "u"_mst)); // V conflicts with u
26 1049 : assert(!(e << "e"_mst) || !(e << "f"_mst)); // e conflicts with f
27 1049 : assert(!(e << "e"_mst) || (e << "d"_mst)); // e implies d
28 1049 : assert(!(e << "V"_mst) || !(e << "e"_mst)); // V conflicts with e
29 1049 : assert(!(e << "d"_mst) || !(e << "f"_mst)); // d conflicts with f
30 1049 : assert(!(e << "V"_mst) || (e << "f"_mst)); // V implies f
31 1049 : assert(!(e << "K"_mst) || (e << "s"_mst)); // K implies s
32 1049 : assert(!(e << "z"_mst) || (e << "m"_mst)); // z implies m
33 1049 : return e;
34 1080 : }
35 :
36 1084 : Type ComputeType(Fragment fragment, Type x, Type y, Type z, const std::vector<Type>& sub_types, uint32_t k, size_t data_size, size_t n_subs, size_t n_keys) {
37 : // Sanity check on data
38 1084 : if (fragment == Fragment::SHA256 || fragment == Fragment::HASH256) {
39 42 : assert(data_size == 32);
40 1084 : } else if (fragment == Fragment::RIPEMD160 || fragment == Fragment::HASH160) {
41 14 : assert(data_size == 20);
42 14 : } else {
43 1028 : assert(data_size == 0);
44 : }
45 : // Sanity check on k
46 1084 : if (fragment == Fragment::OLDER || fragment == Fragment::AFTER) {
47 120 : assert(k >= 1 && k < 0x80000000UL);
48 1084 : } else if (fragment == Fragment::MULTI) {
49 25 : assert(k >= 1 && k <= n_keys);
50 964 : } else if (fragment == Fragment::THRESH) {
51 18 : assert(k >= 1 && k <= n_subs);
52 18 : } else {
53 921 : assert(k == 0);
54 : }
55 : // Sanity check on subs
56 1943 : if (fragment == Fragment::AND_V || fragment == Fragment::AND_B || fragment == Fragment::OR_B ||
57 962 : fragment == Fragment::OR_C || fragment == Fragment::OR_I || fragment == Fragment::OR_D) {
58 245 : assert(n_subs == 2);
59 1084 : } else if (fragment == Fragment::ANDOR) {
60 34 : assert(n_subs == 3);
61 1379 : } else if (fragment == Fragment::WRAP_A || fragment == Fragment::WRAP_S || fragment == Fragment::WRAP_C ||
62 652 : fragment == Fragment::WRAP_D || fragment == Fragment::WRAP_V || fragment == Fragment::WRAP_J ||
63 540 : fragment == Fragment::WRAP_N) {
64 281 : assert(n_subs == 1);
65 805 : } else if (fragment != Fragment::THRESH) {
66 506 : assert(n_subs == 0);
67 506 : }
68 : // Sanity check on keys
69 1084 : if (fragment == Fragment::PK_K || fragment == Fragment::PK_H) {
70 92 : assert(n_keys == 1);
71 1084 : } else if (fragment == Fragment::MULTI) {
72 25 : assert(n_keys >= 1 && n_keys <= 20);
73 25 : } else {
74 967 : assert(n_keys == 0);
75 : }
76 :
77 : // Below is the per-fragment logic for computing the expression types.
78 : // It heavily relies on Type's << operator (where "X << a_mst" means
79 : // "X has all properties listed in a").
80 1084 : switch (fragment) {
81 60 : case Fragment::PK_K: return "Konudemsxk"_mst;
82 28 : case Fragment::PK_H: return "Knudemsxk"_mst;
83 47 : case Fragment::OLDER: return
84 94 : "g"_mst.If(k & CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG) |
85 94 : "h"_mst.If(!(k & CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG)) |
86 47 : "Bzfmxk"_mst;
87 69 : case Fragment::AFTER: return
88 138 : "i"_mst.If(k >= LOCKTIME_THRESHOLD) |
89 138 : "j"_mst.If(k < LOCKTIME_THRESHOLD) |
90 69 : "Bzfmxk"_mst;
91 24 : case Fragment::SHA256: return "Bonudmk"_mst;
92 8 : case Fragment::RIPEMD160: return "Bonudmk"_mst;
93 14 : case Fragment::HASH256: return "Bonudmk"_mst;
94 6 : case Fragment::HASH160: return "Bonudmk"_mst;
95 117 : case Fragment::JUST_1: return "Bzufmxk"_mst;
96 108 : case Fragment::JUST_0: return "Bzudemsxk"_mst;
97 66 : case Fragment::WRAP_A: return
98 132 : "W"_mst.If(x << "B"_mst) | // W=B_x
99 132 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
100 132 : (x & "udfems"_mst) | // u=u_x, d=d_x, f=f_x, e=e_x, m=m_x, s=s_x
101 66 : "x"_mst; // x
102 18 : case Fragment::WRAP_S: return
103 36 : "W"_mst.If(x << "Bo"_mst) | // W=B_x*o_x
104 36 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
105 18 : (x & "udfemsx"_mst); // u=u_x, d=d_x, f=f_x, e=e_x, m=m_x, s=s_x, x=x_x
106 69 : case Fragment::WRAP_C: return
107 138 : "B"_mst.If(x << "K"_mst) | // B=K_x
108 138 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
109 138 : (x & "ondfem"_mst) | // o=o_x, n=n_x, d=d_x, f=f_x, e=e_x, m=m_x
110 69 : "us"_mst; // u, s
111 6 : case Fragment::WRAP_D: return
112 12 : "B"_mst.If(x << "Vz"_mst) | // B=V_x*z_x
113 12 : "o"_mst.If(x << "z"_mst) | // o=z_x
114 12 : "e"_mst.If(x << "f"_mst) | // e=f_x
115 12 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
116 12 : (x & "ms"_mst) | // m=m_x, s=s_x
117 : // NOTE: 'd:' is not 'u' under P2WSH as MINIMALIF is only a policy rule there.
118 6 : "ndx"_mst; // n, d, x
119 96 : case Fragment::WRAP_V: return
120 192 : "V"_mst.If(x << "B"_mst) | // V=B_x
121 192 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
122 192 : (x & "zonms"_mst) | // z=z_x, o=o_x, n=n_x, m=m_x, s=s_x
123 96 : "fx"_mst; // f, x
124 10 : case Fragment::WRAP_J: return
125 20 : "B"_mst.If(x << "Bn"_mst) | // B=B_x*n_x
126 20 : "e"_mst.If(x << "f"_mst) | // e=f_x
127 20 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
128 20 : (x & "oums"_mst) | // o=o_x, u=u_x, m=m_x, s=s_x
129 10 : "ndx"_mst; // n, d, x
130 16 : case Fragment::WRAP_N: return
131 32 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
132 32 : (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
133 16 : "ux"_mst; // u, x
134 82 : case Fragment::AND_V: return
135 156 : (y & "KVB"_mst).If(x << "V"_mst) | // B=V_x*B_y, V=V_x*V_y, K=V_x*K_y
136 234 : (x & "n"_mst) | (y & "n"_mst).If(x << "z"_mst) | // n=n_x+z_x*n_y
137 156 : ((x | y) & "o"_mst).If((x | y) << "z"_mst) | // o=o_x*z_y+z_x*o_y
138 156 : (x & y & "dmz"_mst) | // d=d_x*d_y, m=m_x*m_y, z=z_x*z_y
139 95 : ((x | y) & "s"_mst) | // s=s_x+s_y
140 78 : "f"_mst.If((y << "f"_mst) || (x << "s"_mst)) | // f=f_y+s_x
141 156 : (y & "ux"_mst) | // u=u_y, x=x_y
142 152 : ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
143 152 : "k"_mst.If(((x & y) << "k"_mst) &&
144 180 : !(((x << "g"_mst) && (y << "h"_mst)) ||
145 94 : ((x << "h"_mst) && (y << "g"_mst)) ||
146 160 : ((x << "i"_mst) && (y << "j"_mst)) ||
147 74 : ((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)
148 23 : case Fragment::AND_B: return
149 54 : (x & "B"_mst).If(y << "W"_mst) | // B=B_x*W_y
150 54 : ((x | y) & "o"_mst).If((x | y) << "z"_mst) | // o=o_x*z_y+z_x*o_y
151 81 : (x & "n"_mst) | (y & "n"_mst).If(x << "z"_mst) | // n=n_x+z_x*n_y
152 54 : (x & y & "e"_mst).If((x & y) << "s"_mst) | // e=e_x*e_y*s_x*s_y
153 39 : (x & y & "dzm"_mst) | // d=d_x*d_y, z=z_x*z_y, m=m_x*m_y
154 27 : "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
155 54 : ((x | y) & "s"_mst) | // s=s_x+s_y
156 54 : "ux"_mst | // u, x
157 50 : ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
158 50 : "k"_mst.If(((x & y) << "k"_mst) &&
159 52 : !(((x << "g"_mst) && (y << "h"_mst)) ||
160 25 : ((x << "h"_mst) && (y << "g"_mst)) ||
161 42 : ((x << "i"_mst) && (y << "j"_mst)) ||
162 21 : ((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)
163 17 : case Fragment::OR_B: return
164 17 : "B"_mst.If(x << "Bd"_mst && y << "Wd"_mst) | // B=B_x*d_x*W_x*d_y
165 30 : ((x | y) & "o"_mst).If((x | y) << "z"_mst) | // o=o_x*z_y+z_x*o_y
166 17 : (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)
167 34 : (x & y & "zse"_mst) | // z=z_x*z_y, s=s_x*s_y, e=e_x*e_y
168 34 : "dux"_mst | // d, u, x
169 34 : ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
170 17 : (x & y & "k"_mst); // k=k_x*k_y
171 20 : case Fragment::OR_D: return
172 40 : (y & "B"_mst).If(x << "Bdu"_mst) | // B=B_y*B_x*d_x*u_x
173 33 : (x & "o"_mst).If(y << "z"_mst) | // o=o_x*z_y
174 20 : (x & y & "m"_mst).If(x << "e"_mst && (x | y) << "s"_mst) | // m=m_x*m_y*e_x*(s_x+s_y)
175 40 : (x & y & "zes"_mst) | // z=z_x*z_y, e=e_x*e_y, s=s_x*s_y
176 40 : (y & "ufd"_mst) | // u=u_y, f=f_y, d=d_y
177 40 : "x"_mst | // x
178 40 : ((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 20 : (x & y & "k"_mst); // k=k_x*k_y
180 12 : case Fragment::OR_C: return
181 24 : (y & "V"_mst).If(x << "Bdu"_mst) | // V=V_y*B_x*u_x*d_x
182 21 : (x & "o"_mst).If(y << "z"_mst) | // o=o_x*z_y
183 12 : (x & y & "m"_mst).If(x << "e"_mst && (x | y) << "s"_mst) | // m=m_x*m_y*e_x*(s_x+s_y)
184 24 : (x & y & "zs"_mst) | // z=z_x*z_y, s=s_x*s_y
185 24 : "fx"_mst | // f, x
186 24 : ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
187 12 : (x & y & "k"_mst); // k=k_x*k_y
188 91 : case Fragment::OR_I: return
189 182 : (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
190 182 : "o"_mst.If((x & y) << "z"_mst) | // o=z_x*z_y
191 182 : ((x | y) & "e"_mst).If((x | y) << "f"_mst) | // e=e_x*f_y+f_x*e_y
192 182 : (x & y & "m"_mst).If((x | y) << "s"_mst) | // m=m_x*m_y*(s_x+s_y)
193 182 : ((x | y) & "d"_mst) | // d=d_x+d_y
194 182 : "x"_mst | // x
195 182 : ((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 91 : (x & y & "k"_mst); // k=k_x*k_y
197 34 : case Fragment::ANDOR: return
198 68 : (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
199 68 : (x & y & z & "z"_mst) | // z=z_x*z_y*z_z
200 68 : ((x | (y & z)) & "o"_mst).If((x | (y & z)) << "z"_mst) | // o=o_x*z_y*z_z+z_x*o_y*o_z
201 52 : (y & z & "u"_mst) | // u=u_y*u_z
202 34 : (z & "f"_mst).If((x << "s"_mst) || (y << "f"_mst)) | // f=(s_x+f_y)*f_z
203 52 : (z & "d"_mst) | // d=d_z
204 55 : (x & z & "e"_mst).If(x << "s"_mst || y << "f"_mst) | // e=e_x*e_z*(s_x+f_y)
205 34 : (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)
206 68 : (z & (x | y) & "s"_mst) | // s=s_z*(s_x+s_y)
207 68 : "x"_mst | // x
208 66 : ((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
209 66 : "k"_mst.If(((x & y & z) << "k"_mst) &&
210 64 : !(((x << "g"_mst) && (y << "h"_mst)) ||
211 32 : ((x << "h"_mst) && (y << "g"_mst)) ||
212 64 : ((x << "i"_mst) && (y << "j"_mst)) ||
213 32 : ((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)
214 25 : case Fragment::MULTI: return "Bnudemsk"_mst;
215 : case Fragment::THRESH: {
216 18 : bool all_e = true;
217 18 : bool all_m = true;
218 18 : uint32_t args = 0;
219 18 : uint32_t num_s = 0;
220 18 : Type acc_tl = "k"_mst;
221 70 : for (size_t i = 0; i < sub_types.size(); ++i) {
222 53 : Type t = sub_types[i];
223 53 : if (!(t << (i ? "Wdu"_mst : "Bdu"_mst))) return ""_mst; // Require Bdu, Wdu, Wdu, ...
224 52 : if (!(t << "e"_mst)) all_e = false;
225 52 : if (!(t << "m"_mst)) all_m = false;
226 52 : if (t << "s"_mst) num_s += 1;
227 52 : args += (t << "z"_mst) ? 0 : (t << "o"_mst) ? 1 : 2;
228 102 : acc_tl = ((acc_tl | t) & "ghij"_mst) |
229 : // Thresh contains a combination of timelocks if it has threshold > 1 and
230 : // it contains two different children that have different types of timelocks
231 : // Note how if any of the children don't have "k", the parent also does not have "k"
232 136 : "k"_mst.If(((acc_tl & t) << "k"_mst) && ((k <= 1) ||
233 68 : ((k > 1) && !(((acc_tl << "g"_mst) && (t << "h"_mst)) ||
234 34 : ((acc_tl << "h"_mst) && (t << "g"_mst)) ||
235 64 : ((acc_tl << "i"_mst) && (t << "j"_mst)) ||
236 30 : ((acc_tl << "j"_mst) && (t << "i"_mst))))));
237 52 : }
238 51 : return "Bdu"_mst |
239 34 : "z"_mst.If(args == 0) | // z=all z
240 31 : "o"_mst.If(args == 1) | // o=all z except one o
241 31 : "e"_mst.If(all_e && num_s == n_subs) | // e=all e and all s
242 17 : "m"_mst.If(all_e && all_m && num_s >= n_subs - k) | // m=all e, >=(n-k) s
243 34 : "s"_mst.If(num_s >= n_subs - k + 1) | // s= >=(n-k+1) s
244 17 : acc_tl; // timelock info
245 : }
246 : }
247 0 : assert(false);
248 1084 : }
249 :
250 1080 : size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs, size_t n_keys) {
251 1080 : switch (fragment) {
252 : case Fragment::JUST_1:
253 225 : case Fragment::JUST_0: return 1;
254 60 : case Fragment::PK_K: return 34;
255 28 : case Fragment::PK_H: return 3 + 21;
256 : case Fragment::OLDER:
257 116 : case Fragment::AFTER: return 1 + BuildScript(k).size();
258 : case Fragment::HASH256:
259 38 : case Fragment::SHA256: return 4 + 2 + 33;
260 : case Fragment::HASH160:
261 14 : case Fragment::RIPEMD160: return 4 + 2 + 21;
262 25 : case Fragment::MULTI: return 1 + BuildScript(n_keys).size() + BuildScript(k).size() + 34 * n_keys;
263 78 : case Fragment::AND_V: return subsize;
264 96 : case Fragment::WRAP_V: return subsize + (sub0typ << "x"_mst);
265 : case Fragment::WRAP_S:
266 : case Fragment::WRAP_C:
267 : case Fragment::WRAP_N:
268 : case Fragment::AND_B:
269 143 : case Fragment::OR_B: return subsize + 1;
270 : case Fragment::WRAP_A:
271 78 : case Fragment::OR_C: return subsize + 2;
272 : case Fragment::WRAP_D:
273 : case Fragment::OR_D:
274 : case Fragment::OR_I:
275 151 : case Fragment::ANDOR: return subsize + 3;
276 10 : case Fragment::WRAP_J: return subsize + 4;
277 18 : case Fragment::THRESH: return subsize + n_subs + BuildScript(k).size();
278 : }
279 0 : assert(false);
280 1080 : }
281 :
282 65 : std::optional<std::vector<Opcode>> DecomposeScript(const CScript& script)
283 : {
284 65 : std::vector<Opcode> out;
285 65 : CScript::const_iterator it = script.begin(), itend = script.end();
286 945 : while (it != itend) {
287 882 : std::vector<unsigned char> push_data;
288 : opcodetype opcode;
289 882 : if (!script.GetOp(it, opcode, push_data)) {
290 0 : return {};
291 882 : } else if (opcode >= OP_1 && opcode <= OP_16) {
292 : // Deal with OP_n (GetOp does not turn them into pushes).
293 83 : push_data.assign(1, CScript::DecodeOP_N(opcode));
294 882 : } else if (opcode == OP_CHECKSIGVERIFY) {
295 : // Decompose OP_CHECKSIGVERIFY into OP_CHECKSIG OP_VERIFY
296 0 : out.emplace_back(OP_CHECKSIG, std::vector<unsigned char>());
297 0 : opcode = OP_VERIFY;
298 799 : } else if (opcode == OP_CHECKMULTISIGVERIFY) {
299 : // Decompose OP_CHECKMULTISIGVERIFY into OP_CHECKMULTISIG OP_VERIFY
300 4 : out.emplace_back(OP_CHECKMULTISIG, std::vector<unsigned char>());
301 4 : opcode = OP_VERIFY;
302 799 : } else if (opcode == OP_EQUALVERIFY) {
303 : // Decompose OP_EQUALVERIFY into OP_EQUAL OP_VERIFY
304 46 : out.emplace_back(OP_EQUAL, std::vector<unsigned char>());
305 46 : opcode = OP_VERIFY;
306 795 : } else if (IsPushdataOp(opcode)) {
307 156 : if (!CheckMinimalPush(push_data, opcode)) return {};
308 748 : } else if (it != itend && (opcode == OP_CHECKSIG || opcode == OP_CHECKMULTISIG || opcode == OP_EQUAL) && (*it == OP_VERIFY)) {
309 : // Rule out non minimal VERIFY sequences
310 1 : return {};
311 : }
312 880 : out.emplace_back(opcode, std::move(push_data));
313 882 : }
314 63 : std::reverse(out.begin(), out.end());
315 63 : return out;
316 65 : }
317 :
318 113 : std::optional<int64_t> ParseScriptNumber(const Opcode& in) {
319 113 : if (in.first == OP_0) {
320 0 : return 0;
321 : }
322 113 : if (!in.second.empty()) {
323 113 : if (IsPushdataOp(in.first) && !CheckMinimalPush(in.second, in.first)) return {};
324 : try {
325 113 : return CScriptNum(in.second, true).GetInt64();
326 0 : } catch(const scriptnum_error&) {}
327 0 : }
328 0 : return {};
329 113 : }
330 :
331 208 : int FindNextChar(Span<const char> sp, const char m)
332 : {
333 8142 : for (int i = 0; i < (int)sp.size(); ++i) {
334 8142 : if (sp[i] == m) return i;
335 : // We only search within the current parentheses
336 7947 : if (sp[i] == ')') break;
337 7934 : }
338 13 : return -1;
339 208 : }
340 :
341 : } // namespace internal
342 : } // namespace miniscript
|
