Branch data Line data Source code
1 : : // Copyright (c) 2019-2022 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/miniscript.h>
9 : :
10 : : #include <assert.h>
11 : :
12 : : namespace miniscript {
13 : : namespace internal {
14 : :
15 : 1049513 : Type SanitizeType(Type e) {
16 : 1049513 : int num_types = (e << "K"_mst) + (e << "V"_mst) + (e << "B"_mst) + (e << "W"_mst);
17 [ + + ]: 1049513 : if (num_types == 0) return ""_mst; // No valid type, don't care about the rest
18 [ + - ]: 930454 : assert(num_types == 1); // K, V, B, W all conflict with each other
19 [ + + + - ]: 930454 : assert(!(e << "z"_mst) || !(e << "o"_mst)); // z conflicts with o
20 [ + + + - ]: 930454 : assert(!(e << "n"_mst) || !(e << "z"_mst)); // n conflicts with z
21 [ + + + - ]: 930454 : assert(!(e << "n"_mst) || !(e << "W"_mst)); // n conflicts with W
22 [ + + + - ]: 930454 : assert(!(e << "V"_mst) || !(e << "d"_mst)); // V conflicts with d
23 [ + + + - ]: 930454 : assert(!(e << "K"_mst) || (e << "u"_mst)); // K implies u
24 [ + + + - ]: 930454 : assert(!(e << "V"_mst) || !(e << "u"_mst)); // V conflicts with u
25 [ + + + - ]: 930454 : assert(!(e << "e"_mst) || !(e << "f"_mst)); // e conflicts with f
26 [ + + + - ]: 930454 : assert(!(e << "e"_mst) || (e << "d"_mst)); // e implies d
27 [ + + + - ]: 930454 : assert(!(e << "V"_mst) || !(e << "e"_mst)); // V conflicts with e
28 [ + + + - ]: 930454 : assert(!(e << "d"_mst) || !(e << "f"_mst)); // d conflicts with f
29 [ + + + - ]: 930454 : assert(!(e << "V"_mst) || (e << "f"_mst)); // V implies f
30 [ + + + - ]: 930454 : assert(!(e << "K"_mst) || (e << "s"_mst)); // K implies s
31 [ + + - + ]: 930454 : assert(!(e << "z"_mst) || (e << "m"_mst)); // z implies m
32 : 930454 : return e;
33 : 1049513 : }
34 : :
35 : 2473512 : 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) {
36 : : // Sanity check on data
37 [ + + + + ]: 2473512 : if (fragment == Fragment::SHA256 || fragment == Fragment::HASH256) {
38 [ + - ]: 13329 : assert(data_size == 32);
39 [ + + + + ]: 2473512 : } else if (fragment == Fragment::RIPEMD160 || fragment == Fragment::HASH160) {
40 [ + - ]: 7378 : assert(data_size == 20);
41 : 7378 : } else {
42 [ + - ]: 2452805 : assert(data_size == 0);
43 : : }
44 : : // Sanity check on k
45 [ + + + + ]: 2473512 : if (fragment == Fragment::OLDER || fragment == Fragment::AFTER) {
46 [ + + + - ]: 35105 : assert(k >= 1 && k < 0x80000000UL);
47 [ + + ]: 2473512 : } else if (fragment == Fragment::MULTI) {
48 [ - + + - ]: 16214 : assert(k >= 1 && k <= n_keys);
49 [ + + ]: 2438407 : } else if (fragment == Fragment::THRESH) {
50 [ - + + - ]: 212211 : assert(k >= 1 && k <= n_subs);
51 : 212211 : } else {
52 [ + - ]: 2209982 : assert(k == 0);
53 : : }
54 : : // Sanity check on subs
55 [ + + + + : 3915629 : if (fragment == Fragment::AND_V || fragment == Fragment::AND_B || fragment == Fragment::OR_B ||
+ + + + ]
56 [ + + + + ]: 1860015 : fragment == Fragment::OR_C || fragment == Fragment::OR_I || fragment == Fragment::OR_D) {
57 [ + - ]: 1223556 : assert(n_subs == 2);
58 [ + + ]: 2473512 : } else if (fragment == Fragment::ANDOR) {
59 [ + - ]: 208071 : assert(n_subs == 3);
60 [ + + + + : 2093639 : } else if (fragment == Fragment::WRAP_A || fragment == Fragment::WRAP_S || fragment == Fragment::WRAP_C ||
+ + + + ]
61 [ + + + + : 932156 : fragment == Fragment::WRAP_D || fragment == Fragment::WRAP_V || fragment == Fragment::WRAP_J ||
+ + ]
62 : 843683 : fragment == Fragment::WRAP_N) {
63 [ + - ]: 441984 : assert(n_subs == 1);
64 [ + + ]: 1041885 : } else if (fragment != Fragment::THRESH) {
65 [ - + ]: 387690 : assert(n_subs == 0);
66 : 387690 : }
67 : : // Sanity check on keys
68 [ + + + + ]: 2473512 : if (fragment == Fragment::PK_K || fragment == Fragment::PK_H) {
69 [ + - ]: 25370 : assert(n_keys == 1);
70 [ + + ]: 2473512 : } else if (fragment == Fragment::MULTI) {
71 [ - + + - ]: 16214 : assert(n_keys >= 1 && n_keys <= 20);
72 : 16214 : } else {
73 [ + - ]: 2431928 : assert(n_keys == 0);
74 : : }
75 : :
76 : : // Below is the per-fragment logic for computing the expression types.
77 : : // It heavily relies on Type's << operator (where "X << a_mst" means
78 : : // "X has all properties listed in a").
79 [ + + + + : 2473512 : switch (fragment) {
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + - ]
80 : 12696 : case Fragment::PK_K: return "Konudemsxk"_mst;
81 : 7070 : case Fragment::PK_H: return "Knudemsxk"_mst;
82 : 15026 : case Fragment::OLDER: return
83 : 30052 : "g"_mst.If(k & CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG) |
84 : 30052 : "h"_mst.If(!(k & CTxIn::SEQUENCE_LOCKTIME_TYPE_FLAG)) |
85 : 15026 : "Bzfmxk"_mst;
86 : 14475 : case Fragment::AFTER: return
87 : 28950 : "i"_mst.If(k >= LOCKTIME_THRESHOLD) |
88 : 28950 : "j"_mst.If(k < LOCKTIME_THRESHOLD) |
89 : 14475 : "Bzfmxk"_mst;
90 : 3877 : case Fragment::SHA256: return "Bonudmk"_mst;
91 : 3021 : case Fragment::RIPEMD160: return "Bonudmk"_mst;
92 : 3848 : case Fragment::HASH256: return "Bonudmk"_mst;
93 : 4357 : case Fragment::HASH160: return "Bonudmk"_mst;
94 : 78494 : case Fragment::JUST_1: return "Bzufmxk"_mst;
95 : 228612 : case Fragment::JUST_0: return "Bzudemsxk"_mst;
96 : 63249 : case Fragment::WRAP_A: return
97 : 126498 : "W"_mst.If(x << "B"_mst) | // W=B_x
98 : 126498 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
99 : 126498 : (x & "udfems"_mst) | // u=u_x, d=d_x, f=f_x, e=e_x, m=m_x, s=s_x
100 : 63249 : "x"_mst; // x
101 : 28535 : case Fragment::WRAP_S: return
102 : 57070 : "W"_mst.If(x << "Bo"_mst) | // W=B_x*o_x
103 : 57070 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
104 : 28535 : (x & "udfemsx"_mst); // u=u_x, d=d_x, f=f_x, e=e_x, m=m_x, s=s_x, x=x_x
105 : 17945 : case Fragment::WRAP_C: return
106 : 35890 : "B"_mst.If(x << "K"_mst) | // B=K_x
107 : 35890 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
108 : 35890 : (x & "ondfem"_mst) | // o=o_x, n=n_x, d=d_x, f=f_x, e=e_x, m=m_x
109 : 17945 : "us"_mst; // u, s
110 : 18713 : case Fragment::WRAP_D: return
111 : 37426 : "B"_mst.If(x << "Vz"_mst) | // B=V_x*z_x
112 : 37426 : "o"_mst.If(x << "z"_mst) | // o=z_x
113 : 37426 : "e"_mst.If(x << "f"_mst) | // e=f_x
114 : 37426 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
115 : 37426 : (x & "ms"_mst) | // m=m_x, s=s_x
116 : : // NOTE: 'd:' is not 'u' under P2WSH as MINIMALIF is only a policy rule there.
117 : 18713 : "ndx"_mst; // n, d, x
118 : 57158 : case Fragment::WRAP_V: return
119 : 114316 : "V"_mst.If(x << "B"_mst) | // V=B_x
120 : 114316 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
121 : 114316 : (x & "zonms"_mst) | // z=z_x, o=o_x, n=n_x, m=m_x, s=s_x
122 : 57158 : "fx"_mst; // f, x
123 : 12602 : case Fragment::WRAP_J: return
124 : 25204 : "B"_mst.If(x << "Bn"_mst) | // B=B_x*n_x
125 : 25204 : "e"_mst.If(x << "f"_mst) | // e=f_x
126 : 25204 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
127 : 25204 : (x & "oums"_mst) | // o=o_x, u=u_x, m=m_x, s=s_x
128 : 12602 : "ndx"_mst; // n, d, x
129 : 243782 : case Fragment::WRAP_N: return
130 : 487564 : (x & "ghijk"_mst) | // g=g_x, h=h_x, i=i_x, j=j_x, k=k_x
131 : 487564 : (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
132 : 243782 : "ux"_mst; // u, x
133 : 222965 : case Fragment::AND_V: return
134 : 453834 : (y & "KVB"_mst).If(x << "V"_mst) | // B=V_x*B_y, V=V_x*V_y, K=V_x*K_y
135 : 680751 : (x & "n"_mst) | (y & "n"_mst).If(x << "z"_mst) | // n=n_x+z_x*n_y
136 : 453834 : ((x | y) & "o"_mst).If((x | y) << "z"_mst) | // o=o_x*z_y+z_x*o_y
137 : 453834 : (x & y & "dmz"_mst) | // d=d_x*d_y, m=m_x*m_y, z=z_x*z_y
138 : 411360 : ((x | y) & "s"_mst) | // s=s_x+s_y
139 [ + + ]: 226917 : "f"_mst.If((y << "f"_mst) || (x << "s"_mst)) | // f=f_y+s_x
140 : 453834 : (y & "ux"_mst) | // u=u_y, x=x_y
141 : 270626 : ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
142 [ + + ]: 270626 : "k"_mst.If(((x & y) << "k"_mst) &&
143 [ + + + + ]: 96497 : !(((x << "g"_mst) && (y << "h"_mst)) ||
144 [ + + ]: 48836 : ((x << "h"_mst) && (y << "g"_mst)) ||
145 [ + + ]: 86363 : ((x << "i"_mst) && (y << "j"_mst)) ||
146 [ + + ]: 42604 : ((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)
147 : 188214 : case Fragment::AND_B: return
148 : 382700 : (x & "B"_mst).If(y << "W"_mst) | // B=B_x*W_y
149 : 382700 : ((x | y) & "o"_mst).If((x | y) << "z"_mst) | // o=o_x*z_y+z_x*o_y
150 : 574050 : (x & "n"_mst) | (y & "n"_mst).If(x << "z"_mst) | // n=n_x+z_x*n_y
151 : 382700 : (x & y & "e"_mst).If((x & y) << "s"_mst) | // e=e_x*e_y*s_x*s_y
152 : 375468 : (x & y & "dzm"_mst) | // d=d_x*d_y, z=z_x*z_y, m=m_x*m_y
153 [ + + + + ]: 191350 : "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
154 : 382700 : ((x | y) & "s"_mst) | // s=s_x+s_y
155 : 382700 : "ux"_mst | // u, x
156 : 204912 : ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
157 [ + + ]: 204912 : "k"_mst.If(((x & y) << "k"_mst) &&
158 [ + + + + ]: 32128 : !(((x << "g"_mst) && (y << "h"_mst)) ||
159 [ + + ]: 15430 : ((x << "h"_mst) && (y << "g"_mst)) ||
160 [ + + ]: 26015 : ((x << "i"_mst) && (y << "j"_mst)) ||
161 [ + + ]: 12625 : ((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)
162 : 192762 : case Fragment::OR_B: return
163 [ + + ]: 192762 : "B"_mst.If(x << "Bd"_mst && y << "Wd"_mst) | // B=B_x*d_x*W_x*d_y
164 : 200480 : ((x | y) & "o"_mst).If((x | y) << "z"_mst) | // o=o_x*z_y+z_x*o_y
165 [ + + ]: 192762 : (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)
166 : 385524 : (x & y & "zse"_mst) | // z=z_x*z_y, s=s_x*s_y, e=e_x*e_y
167 : 385524 : "dux"_mst | // d, u, x
168 : 385524 : ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
169 : 192762 : (x & y & "k"_mst); // k=k_x*k_y
170 : 192161 : case Fragment::OR_D: return
171 : 384322 : (y & "B"_mst).If(x << "Bdu"_mst) | // B=B_y*B_x*d_x*u_x
172 : 201845 : (x & "o"_mst).If(y << "z"_mst) | // o=o_x*z_y
173 [ + + ]: 192161 : (x & y & "m"_mst).If(x << "e"_mst && (x | y) << "s"_mst) | // m=m_x*m_y*e_x*(s_x+s_y)
174 : 384322 : (x & y & "zs"_mst) | // z=z_x*z_y, s=s_x*s_y
175 : 384322 : (y & "ufde"_mst) | // u=u_y, f=f_y, d=d_y, e=e_y
176 : 384322 : "x"_mst | // x
177 : 384322 : ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
178 : 192161 : (x & y & "k"_mst); // k=k_x*k_y
179 : 193847 : case Fragment::OR_C: return
180 : 387694 : (y & "V"_mst).If(x << "Bdu"_mst) | // V=V_y*B_x*u_x*d_x
181 : 200897 : (x & "o"_mst).If(y << "z"_mst) | // o=o_x*z_y
182 [ + + ]: 193847 : (x & y & "m"_mst).If(x << "e"_mst && (x | y) << "s"_mst) | // m=m_x*m_y*e_x*(s_x+s_y)
183 : 387694 : (x & y & "zs"_mst) | // z=z_x*z_y, s=s_x*s_y
184 : 387694 : "fx"_mst | // f, x
185 : 387694 : ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
186 : 193847 : (x & y & "k"_mst); // k=k_x*k_y
187 : 224051 : case Fragment::OR_I: return
188 : 448102 : (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
189 : 448102 : "o"_mst.If((x & y) << "z"_mst) | // o=z_x*z_y
190 : 448102 : ((x | y) & "e"_mst).If((x | y) << "f"_mst) | // e=e_x*f_y+f_x*e_y
191 : 448102 : (x & y & "m"_mst).If((x | y) << "s"_mst) | // m=m_x*m_y*(s_x+s_y)
192 : 448102 : ((x | y) & "d"_mst) | // d=d_x+d_y
193 : 448102 : "x"_mst | // x
194 : 448102 : ((x | y) & "ghij"_mst) | // g=g_x+g_y, h=h_x+h_y, i=i_x+i_y, j=j_x+j_y
195 : 224051 : (x & y & "k"_mst); // k=k_x*k_y
196 : 206593 : case Fragment::ANDOR: return
197 : 416142 : (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
198 : 416142 : (x & y & z & "z"_mst) | // z=z_x*z_y*z_z
199 : 416142 : ((x | (y & z)) & "o"_mst).If((x | (y & z)) << "z"_mst) | // o=o_x*z_y*z_z+z_x*o_y*o_z
200 : 400288 : (y & z & "u"_mst) | // u=u_y*u_z
201 [ + + ]: 208071 : (z & "f"_mst).If((x << "s"_mst) || (y << "f"_mst)) | // f=(s_x+f_y)*f_z
202 : 400288 : (z & "d"_mst) | // d=d_z
203 [ + + ]: 224777 : (z & "e"_mst).If(x << "s"_mst || y << "f"_mst) | // e=e_z*(s_x+f_y)
204 [ + + ]: 208071 : (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)
205 : 416142 : (z & (x | y) & "s"_mst) | // s=s_z*(s_x+s_y)
206 : 416142 : "x"_mst | // x
207 : 227850 : ((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
208 [ + + ]: 227850 : "k"_mst.If(((x & y & z) << "k"_mst) &&
209 [ + + + + ]: 42047 : !(((x << "g"_mst) && (y << "h"_mst)) ||
210 [ + + ]: 20790 : ((x << "h"_mst) && (y << "g"_mst)) ||
211 [ + + ]: 38655 : ((x << "i"_mst) && (y << "j"_mst)) ||
212 [ + + ]: 18932 : ((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)
213 : 16214 : case Fragment::MULTI: return "Bnudemsk"_mst;
214 : : case Fragment::THRESH: {
215 : 214679 : bool all_e = true;
216 : 214679 : bool all_m = true;
217 : 214679 : uint32_t args = 0;
218 : 214679 : uint32_t num_s = 0;
219 : 214679 : Type acc_tl = "k"_mst;
220 [ + + ]: 286777 : for (size_t i = 0; i < sub_types.size(); ++i) {
221 : 267495 : Type t = sub_types[i];
222 [ + + + + ]: 267495 : if (!(t << (i ? "Wdu"_mst : "Bdu"_mst))) return ""_mst; // Require Bdu, Wdu, Wdu, ...
223 [ + + ]: 74566 : if (!(t << "e"_mst)) all_e = false;
224 [ + + ]: 74566 : if (!(t << "m"_mst)) all_m = false;
225 [ + + ]: 74566 : if (t << "s"_mst) num_s += 1;
226 [ + + ]: 74566 : args += (t << "z"_mst) ? 0 : (t << "o"_mst) ? 1 : 2;
227 : 131502 : acc_tl = ((acc_tl | t) & "ghij"_mst) |
228 : : // Thresh contains a combination of timelocks if it has threshold > 1 and
229 : : // it contains two different children that have different types of timelocks
230 : : // Note how if any of the children don't have "k", the parent also does not have "k"
231 [ + + + + ]: 161299 : "k"_mst.If(((acc_tl & t) << "k"_mst) && ((k <= 1) ||
232 [ - + + + : 63908 : ((k > 1) && !(((acc_tl << "g"_mst) && (t << "h"_mst)) ||
+ + ]
233 [ + + ]: 31643 : ((acc_tl << "h"_mst) && (t << "g"_mst)) ||
234 [ + + ]: 59256 : ((acc_tl << "i"_mst) && (t << "j"_mst)) ||
235 [ + + ]: 29082 : ((acc_tl << "j"_mst) && (t << "i"_mst))))));
236 : 72098 : }
237 : 57846 : return "Bdu"_mst |
238 : 38564 : "z"_mst.If(args == 0) | // z=all z
239 : 32141 : "o"_mst.If(args == 1) | // o=all z except one o
240 [ + + ]: 32141 : "e"_mst.If(all_e && num_s == n_subs) | // e=all e and all s
241 [ + + + + ]: 19282 : "m"_mst.If(all_e && all_m && num_s >= n_subs - k) | // m=all e, >=(n-k) s
242 : 38564 : "s"_mst.If(num_s >= n_subs - k + 1) | // s= >=(n-k+1) s
243 : 19282 : acc_tl; // timelock info
244 : : }
245 : : }
246 : 0 : assert(false);
247 : 2462478 : }
248 : :
249 : 1167764 : size_t ComputeScriptLen(Fragment fragment, Type sub0typ, size_t subsize, uint32_t k, size_t n_subs, size_t n_keys) {
250 [ + + + + : 1167764 : switch (fragment) {
+ + + + +
+ + + + +
- ]
251 : : case Fragment::JUST_1:
252 : 336408 : case Fragment::JUST_0: return 1;
253 : 16518 : case Fragment::PK_K: return 34;
254 : 8758 : case Fragment::PK_H: return 3 + 21;
255 : : case Fragment::OLDER:
256 [ + - ]: 31514 : case Fragment::AFTER: return 1 + BuildScript(k).size();
257 : : case Fragment::HASH256:
258 : 10313 : case Fragment::SHA256: return 4 + 2 + 33;
259 : : case Fragment::HASH160:
260 : 9529 : case Fragment::RIPEMD160: return 4 + 2 + 21;
261 [ + - + - : 20937 : case Fragment::MULTI: return 1 + BuildScript(n_keys).size() + BuildScript(k).size() + 34 * n_keys;
+ - ]
262 : 68005 : case Fragment::AND_V: return subsize;
263 : 67332 : case Fragment::WRAP_V: return subsize + (sub0typ << "x"_mst);
264 : : case Fragment::WRAP_S:
265 : : case Fragment::WRAP_C:
266 : : case Fragment::WRAP_N:
267 : : case Fragment::AND_B:
268 : 321799 : case Fragment::OR_B: return subsize + 1;
269 : : case Fragment::WRAP_A:
270 : 84783 : case Fragment::OR_C: return subsize + 2;
271 : : case Fragment::WRAP_D:
272 : : case Fragment::OR_D:
273 : : case Fragment::OR_I:
274 : 151401 : case Fragment::ANDOR: return subsize + 3;
275 : 11798 : case Fragment::WRAP_J: return subsize + 4;
276 [ + - ]: 28669 : case Fragment::THRESH: return subsize + n_subs + BuildScript(k).size();
277 : : }
278 : 0 : assert(false);
279 : 1167764 : }
280 : :
281 [ + - ]: 771813 : InputStack& InputStack::SetAvailable(Availability avail) {
282 : 771640 : available = avail;
283 [ + - - + : 771813 : if (avail == Availability::NO) {
+ - + - +
+ ]
284 : 741524 : stack.clear();
285 [ + - ]: 741697 : size = std::numeric_limits<size_t>::max();
286 : 741524 : has_sig = false;
287 : 741697 : malleable = false;
288 : 741524 : non_canon = false;
289 [ + - + - ]: 741697 : }
290 : 771640 : return *this;
291 : : }
292 : :
293 : 46872 : InputStack& InputStack::SetWithSig() {
294 : 46872 : has_sig = true;
295 : 46872 : return *this;
296 : : }
297 : :
298 : 46206 : InputStack& InputStack::SetNonCanon() {
299 : 46206 : non_canon = true;
300 : 46206 : return *this;
301 : : }
302 : :
303 : 26398 : InputStack& InputStack::SetMalleable(bool x) {
304 : 26398 : malleable = x;
305 : 26398 : return *this;
306 : : }
307 : :
308 : 953064 : InputStack operator+(InputStack a, InputStack b) {
309 [ + - ]: 953064 : a.stack = Cat(std::move(a.stack), std::move(b.stack));
310 [ + + + + ]: 953064 : if (a.available != Availability::NO && b.available != Availability::NO) a.size += b.size;
311 : 953064 : a.has_sig |= b.has_sig;
312 : 953064 : a.malleable |= b.malleable;
313 : 953064 : a.non_canon |= b.non_canon;
314 [ + + + + ]: 953064 : if (a.available == Availability::NO || b.available == Availability::NO) {
315 : 716010 : a.SetAvailable(Availability::NO);
316 [ + - - + ]: 953064 : } else if (a.available == Availability::MAYBE || b.available == Availability::MAYBE) {
317 : 0 : a.SetAvailable(Availability::MAYBE);
318 : 0 : }
319 : 953064 : return a;
320 : 0 : }
321 : :
322 : 524900 : InputStack operator|(InputStack a, InputStack b) {
323 : : // If only one is invalid, pick the other one. If both are invalid, pick an arbitrary one.
324 [ + + ]: 524900 : if (a.available == Availability::NO) return b;
325 [ + + ]: 144714 : if (b.available == Availability::NO) return a;
326 : : // If only one of the solutions has a signature, we must pick the other one.
327 [ + + + + ]: 97058 : if (!a.has_sig && b.has_sig) return a;
328 [ + + + + ]: 96074 : if (!b.has_sig && a.has_sig) return b;
329 [ + + - + ]: 93712 : if (!a.has_sig && !b.has_sig) {
330 : : // If neither solution requires a signature, the result is inevitably malleable.
331 : 19368 : a.malleable = true;
332 : 19368 : b.malleable = true;
333 : 19368 : } else {
334 : : // If both options require a signature, prefer the non-malleable one.
335 [ + + + + ]: 74344 : if (b.malleable && !a.malleable) return a;
336 [ + + + + ]: 74106 : if (a.malleable && !b.malleable) return b;
337 : : }
338 : : // Between two malleable or two non-malleable solutions, pick the smaller one between
339 : : // YESes, and the bigger ones between MAYBEs. Prefer YES over MAYBE.
340 [ + - - + ]: 93362 : if (a.available == Availability::YES && b.available == Availability::YES) {
341 [ + + ]: 93362 : return std::move(a.size <= b.size ? a : b);
342 [ # # # # ]: 0 : } else if (a.available == Availability::MAYBE && b.available == Availability::MAYBE) {
343 [ # # ]: 0 : return std::move(a.size >= b.size ? a : b);
344 [ # # ]: 0 : } else if (a.available == Availability::YES) {
345 : 0 : return a;
346 : : } else {
347 : 0 : return b;
348 : : }
349 : 524900 : }
350 : :
351 : 2688 : std::optional<std::vector<Opcode>> DecomposeScript(const CScript& script)
352 : : {
353 : 2688 : std::vector<Opcode> out;
354 [ + - + - ]: 2688 : CScript::const_iterator it = script.begin(), itend = script.end();
355 [ + - + + ]: 473616 : while (it != itend) {
356 : 470969 : std::vector<unsigned char> push_data;
357 : : opcodetype opcode;
358 [ + - + + ]: 470969 : if (!script.GetOp(it, opcode, push_data)) {
359 : 24 : return {};
360 [ + + + + ]: 470945 : } else if (opcode >= OP_1 && opcode <= OP_16) {
361 : : // Deal with OP_n (GetOp does not turn them into pushes).
362 [ + - + - ]: 30261 : push_data.assign(1, CScript::DecodeOP_N(opcode));
363 [ + + ]: 470945 : } else if (opcode == OP_CHECKSIGVERIFY) {
364 : : // Decompose OP_CHECKSIGVERIFY into OP_CHECKSIG OP_VERIFY
365 [ + - ]: 1556 : out.emplace_back(OP_CHECKSIG, std::vector<unsigned char>());
366 : 1556 : opcode = OP_VERIFY;
367 [ + + ]: 440684 : } else if (opcode == OP_CHECKMULTISIGVERIFY) {
368 : : // Decompose OP_CHECKMULTISIGVERIFY into OP_CHECKMULTISIG OP_VERIFY
369 [ + - ]: 2318 : out.emplace_back(OP_CHECKMULTISIG, std::vector<unsigned char>());
370 : 2318 : opcode = OP_VERIFY;
371 [ + + ]: 439128 : } else if (opcode == OP_EQUALVERIFY) {
372 : : // Decompose OP_EQUALVERIFY into OP_EQUAL OP_VERIFY
373 [ - + ]: 10112 : out.emplace_back(OP_EQUAL, std::vector<unsigned char>());
374 : 10112 : opcode = OP_VERIFY;
375 [ + - + + ]: 436810 : } else if (IsPushdataOp(opcode)) {
376 [ + - + + ]: 40673 : if (!CheckMinimalPush(push_data, opcode)) return {};
377 [ + - + + : 426683 : } else if (it != itend && (opcode == OP_CHECKSIG || opcode == OP_CHECKMULTISIG || opcode == OP_EQUAL) && (*it == OP_VERIFY)) {
+ + + + +
+ + - +
+ ]
378 : : // Rule out non minimal VERIFY sequences
379 : 2 : return {};
380 : : }
381 [ + - ]: 470928 : out.emplace_back(opcode, std::move(push_data));
382 [ + + ]: 470969 : }
383 [ + - ]: 2647 : std::reverse(out.begin(), out.end());
384 [ + - ]: 2647 : return out;
385 : 2688 : }
386 : :
387 : 28893 : std::optional<int64_t> ParseScriptNumber(const Opcode& in) {
388 [ + + ]: 28893 : if (in.first == OP_0) {
389 : 11 : return 0;
390 : : }
391 [ + + ]: 28882 : if (!in.second.empty()) {
392 [ + + + - ]: 28831 : if (IsPushdataOp(in.first) && !CheckMinimalPush(in.second, in.first)) return {};
393 : : try {
394 [ + + + - : 28831 : return CScriptNum(in.second, true).GetInt64();
+ - ]
395 [ + - ]: 136 : } catch(const scriptnum_error&) {}
396 : 136 : }
397 : 187 : return {};
398 : 29029 : }
399 : :
400 : 100276 : int FindNextChar(Span<const char> sp, const char m)
401 : : {
402 [ + + ]: 5346084 : for (int i = 0; i < (int)sp.size(); ++i) {
403 [ + + ]: 5346003 : if (sp[i] == m) return i;
404 : : // We only search within the current parentheses
405 [ + + ]: 5252697 : if (sp[i] == ')') break;
406 : 5245808 : }
407 : 6970 : return -1;
408 : 100276 : }
409 : :
410 : : } // namespace internal
411 : : } // namespace miniscript
|
